1 /* 2 * Copyright (c) 2021-2024 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 #ifndef COMPILER_OPTIMIZER_ANALYSIS_ALIAS_ANALYSIS_H 17 #define COMPILER_OPTIMIZER_ANALYSIS_ALIAS_ANALYSIS_H 18 19 #include <unordered_map> 20 #include "optimizer/ir/graph_visitor.h" 21 #include "optimizer/pass.h" 22 #include "utils/arena_containers.h" 23 #include "utils/hash.h" 24 25 namespace ark::compiler { 26 class BasicBlock; 27 class Graph; 28 29 enum AliasType : uint8_t { 30 // Proved that references are not aliases 31 NO_ALIAS, 32 // References may or may not alias each other (cannot be proven statically) 33 MAY_ALIAS, 34 // References are proven aliases 35 MUST_ALIAS 36 }; 37 38 enum PointerType { 39 // Reference to unknown object. 40 // Valid fields: base 41 OBJECT, 42 // Constant from pool 43 // Valid fields: imm 44 POOL_CONSTANT, 45 // Object's field 46 // Valid fields: base, imm, type_ptr 47 OBJECT_FIELD, 48 // Static field of the object 49 // Valid fields: imm, type_ptr 50 STATIC_FIELD, 51 // Array pointer 52 // Valid fields 53 // * in common: base, idx 54 // * in case LoadArrayPair/StoreArrayPair: base, idx, imm 55 // * in case LoadArrayPairI/StoreArrayPairI, LoadArrayI/StoreArrayI: base, imm 56 ARRAY_ELEMENT, 57 // Dictionary pointer 58 // Valid fields: base, idx 59 DICTIONARY_ELEMENT 60 }; 61 62 class Pointer { 63 public: 64 Pointer() = default; Pointer(PointerType type,const Inst * base,const Inst * idx,uint64_t imm,const void * typePtr)65 Pointer(PointerType type, const Inst *base, const Inst *idx, uint64_t imm, const void *typePtr) 66 : type_(type), base_(base), idx_(idx), imm_(imm), typePtr_(typePtr), volatile_(false) 67 { 68 local_ = base == nullptr ? false : IsLocalAlias(base); 69 }; 70 CreateObject(const Inst * base)71 static Pointer CreateObject(const Inst *base) 72 { 73 return Pointer(OBJECT, base, nullptr, 0, nullptr); 74 } 75 CreatePoolConstant(uint32_t typeId)76 static Pointer CreatePoolConstant(uint32_t typeId) 77 { 78 return Pointer(POOL_CONSTANT, nullptr, nullptr, typeId, nullptr); 79 } 80 81 static Pointer CreateStaticField(uint32_t typeId, const void *typePtr = nullptr) 82 { 83 return Pointer(STATIC_FIELD, nullptr, nullptr, typeId, typePtr); 84 } 85 86 static Pointer CreateObjectField(const Inst *base, uint32_t typeId, const void *typePtr = nullptr) 87 { 88 return Pointer(OBJECT_FIELD, base, nullptr, typeId, typePtr); 89 } 90 91 static Pointer CreateArrayElement(const Inst *array, const Inst *idx, uint64_t imm = 0) 92 { 93 return Pointer(ARRAY_ELEMENT, array, idx, imm, nullptr); 94 } 95 96 static Pointer CreateDictionaryElement(const Inst *array, const Inst *idx, uint64_t imm = 0) 97 { 98 return Pointer(DICTIONARY_ELEMENT, array, idx, imm, nullptr); 99 } 100 GetType()101 PointerType GetType() const 102 { 103 return type_; 104 } 105 GetBase()106 const Inst *GetBase() const 107 { 108 return base_; 109 } 110 GetIdx()111 const Inst *GetIdx() const 112 { 113 return idx_; 114 } 115 GetImm()116 uint64_t GetImm() const 117 { 118 return imm_; 119 } 120 GetTypePtr()121 const void *GetTypePtr() const 122 { 123 return typePtr_; 124 } 125 IsLocal()126 bool IsLocal() const 127 { 128 return local_; 129 } 130 SetLocalVolatile(bool local,bool isVolatile)131 void SetLocalVolatile(bool local, bool isVolatile) 132 { 133 local_ = local; 134 volatile_ = isVolatile; 135 } 136 IsVolatile()137 bool IsVolatile() const 138 { 139 return volatile_; 140 } 141 SetVolatile(bool isVolatile)142 void SetVolatile(bool isVolatile) 143 { 144 volatile_ = isVolatile; 145 } 146 147 void Dump(std::ostream *out) const; 148 HasSameOffset(const Pointer & p)149 bool HasSameOffset(const Pointer &p) const 150 { 151 if (typePtr_ == nullptr && p.typePtr_ == nullptr) { 152 return imm_ == p.imm_; 153 } 154 return typePtr_ == p.typePtr_; 155 } 156 157 private: 158 /** 159 * Returns true if reference is used only in scope of current function: it 160 * must be created in the function and must not escape its scope 161 */ IsLocalAlias(const Inst * inst)162 static bool IsLocalAlias(const Inst *inst) 163 { 164 switch (inst->GetOpcode()) { 165 case Opcode::NullPtr: 166 return true; 167 case Opcode::NewArray: 168 case Opcode::MultiArray: 169 case Opcode::NewObject: 170 case Opcode::InitObject: 171 case Opcode::InitEmptyString: 172 case Opcode::InitString: 173 return !IsEscapingAlias(inst); 174 case Opcode::NullCheck: 175 case Opcode::RefTypeCheck: 176 case Opcode::ObjByIndexCheck: 177 UNREACHABLE(); 178 /* fall-through */ 179 default: 180 return false; 181 } 182 } 183 184 /** 185 * Returns true if a reference escapes the scope of current function: 186 * Various function calls, constructors and stores to another objects' fields, arrays 187 */ IsEscapingAlias(const Inst * inst)188 static bool IsEscapingAlias(const Inst *inst) 189 { 190 for (auto &user : inst->GetUsers()) { 191 switch (user.GetInst()->GetOpcode()) { 192 case Opcode::NullCheck: 193 case Opcode::RefTypeCheck: 194 case Opcode::ObjByIndexCheck: 195 if (IsEscapingAlias(user.GetInst())) { 196 return true; 197 } 198 break; 199 case Opcode::StoreObject: 200 case Opcode::StoreObjectPair: 201 case Opcode::StoreArray: 202 case Opcode::StoreArrayI: 203 case Opcode::StoreArrayPair: 204 case Opcode::StoreArrayPairI: 205 if (user.GetIndex() != 0) { 206 return true; 207 } 208 break; 209 case Opcode::StoreStatic: 210 case Opcode::StoreResolvedObjectField: 211 case Opcode::StoreResolvedObjectFieldStatic: 212 case Opcode::UnresolvedStoreStatic: 213 case Opcode::InitObject: 214 case Opcode::InitClass: 215 case Opcode::LoadAndInitClass: 216 case Opcode::UnresolvedLoadAndInitClass: 217 case Opcode::GetGlobalVarAddress: 218 case Opcode::CallResolvedStatic: 219 case Opcode::CallResolvedVirtual: 220 case Opcode::CallStatic: 221 case Opcode::CallVirtual: 222 case Opcode::CallDynamic: 223 return true; 224 case Opcode::Intrinsic: 225 if (inst->GetFlagsMask() != 0) { 226 return true; 227 } 228 break; 229 default: 230 break; 231 } 232 } 233 return false; 234 } 235 236 private: 237 PointerType type_; 238 const Inst *base_; 239 const Inst *idx_; 240 uint64_t imm_; 241 const void *typePtr_; 242 bool local_; 243 bool volatile_; 244 }; 245 246 struct PointerEqual { operatorPointerEqual247 bool operator()(Pointer const &p1, Pointer const &p2) const 248 { 249 return p1.GetType() == p2.GetType() && p1.GetBase() == p2.GetBase() && p1.GetIdx() == p2.GetIdx() && 250 p1.HasSameOffset(p2); 251 } 252 }; 253 254 struct PointerHash { operatorPointerHash255 uint32_t operator()(Pointer const &p) const 256 { 257 auto instHasher = std::hash<const Inst *> {}; 258 uint32_t hash = instHasher(p.GetBase()); 259 hash += instHasher(p.GetIdx()); 260 if (p.GetTypePtr() == nullptr) { 261 hash += std::hash<uint64_t> {}(p.GetImm()); 262 } else { 263 hash += std::hash<const void *> {}(p.GetTypePtr()); 264 } 265 return hash; 266 } 267 }; 268 269 // NOLINTNEXTLINE(fuchsia-multiple-inheritance) 270 class AliasAnalysis : public Analysis, public GraphVisitor { 271 public: 272 enum class Trilean { 273 TRUE, 274 UNKNOWN, 275 FALSE, 276 }; 277 278 using PointerPairVector = ArenaVector<std::pair<Pointer, Pointer>>; 279 280 explicit AliasAnalysis(Graph *graph); 281 NO_MOVE_SEMANTIC(AliasAnalysis); 282 NO_COPY_SEMANTIC(AliasAnalysis); 283 ~AliasAnalysis() override = default; 284 285 bool RunImpl() override; 286 GetPassName()287 const char *GetPassName() const override 288 { 289 return "AliasAnalysis"; 290 } 291 292 AliasType CheckInstAlias(Inst *mem1, Inst *mem2) const; 293 AliasType CheckRefAlias(Inst *ref1, Inst *ref2) const; 294 AliasType CheckMemAddress(const Pointer &p1, const Pointer &p2) const; 295 void Dump(std::ostream *out) const; 296 297 /** 298 * Sort IR instructions into two constraint groups: 299 * Direct: introduce the alias 300 * Copy: copy one alias to another 301 */ 302 const ArenaVector<BasicBlock *> &GetBlocksToVisit() const override; 303 304 /// Instructions that definitely are not an alias of anything. 305 static void VisitNullPtr(GraphVisitor *v, Inst *inst); 306 static void VisitLoadUndefined(GraphVisitor *v, Inst *inst); 307 static void VisitInitObject(GraphVisitor *v, Inst *inst); 308 static void VisitNewObject(GraphVisitor *v, Inst *inst); 309 static void VisitNewArray(GraphVisitor *v, Inst *inst); 310 static void VisitMultiArray(GraphVisitor *v, Inst *inst); 311 static void VisitInitEmptyString(GraphVisitor *v, Inst *inst); 312 static void VisitInitString(GraphVisitor *v, Inst *inst); 313 /** 314 * Instructions that can introduce references that are an alias of 315 * something already existed. 316 */ 317 static void VisitConstant(GraphVisitor *v, Inst *inst); 318 static void VisitParameter(GraphVisitor *v, Inst *inst); 319 static void VisitLoadImmediate(GraphVisitor *v, Inst *inst); 320 static void VisitIntrinsic(GraphVisitor *v, Inst *inst); 321 static void VisitBuiltin(GraphVisitor *v, Inst *inst); 322 static void VisitCallStatic(GraphVisitor *v, Inst *inst); 323 static void VisitCallResolvedStatic(GraphVisitor *v, Inst *inst); 324 static void VisitCallVirtual(GraphVisitor *v, Inst *inst); 325 static void VisitCallDynamic(GraphVisitor *v, Inst *inst); 326 static void VisitCallResolvedVirtual(GraphVisitor *v, Inst *inst); 327 static void VisitGetManagedClassObject(GraphVisitor *v, Inst *inst); 328 static void VisitResolveObjectFieldStatic(GraphVisitor *v, Inst *inst); 329 static void VisitBitcast(GraphVisitor *v, Inst *inst); 330 331 /// Instructions that introduce static fields (global variables). 332 static void VisitLoadStatic(GraphVisitor *v, Inst *inst); 333 static void VisitLoadResolvedObjectFieldStatic(GraphVisitor *v, Inst *inst); 334 static void VisitStoreStatic(GraphVisitor *v, Inst *inst); 335 static void VisitStoreResolvedObjectFieldStatic(GraphVisitor *v, Inst *inst); 336 static void VisitUnresolvedStoreStatic(GraphVisitor *v, Inst *inst); 337 338 /// Instructions that introduce unique constant references (global constants). 339 static void VisitLoadRuntimeClass(GraphVisitor *v, Inst *inst); 340 static void VisitLoadClass(GraphVisitor *v, Inst *inst); 341 static void VisitLoadAndInitClass(GraphVisitor *v, Inst *inst); 342 static void VisitUnresolvedLoadAndInitClass(GraphVisitor *v, Inst *inst); 343 static void VisitGetGlobalVarAddress(GraphVisitor *v, Inst *inst); 344 static void VisitLoadString(GraphVisitor *v, Inst *inst); 345 static void VisitLoadConstArray(GraphVisitor *v, Inst *inst); 346 static void VisitLoadType(GraphVisitor *v, Inst *inst); 347 static void VisitUnresolvedLoadType(GraphVisitor *v, Inst *inst); 348 static void VisitLoadObjFromConst(GraphVisitor *v, Inst *inst); 349 350 /// Instructions that introduce aliases. 351 static void VisitLoadArray(GraphVisitor *v, Inst *inst); 352 static void VisitStoreArray(GraphVisitor *v, Inst *inst); 353 static void VisitLoadArrayI(GraphVisitor *v, Inst *inst); 354 static void VisitStoreArrayI(GraphVisitor *v, Inst *inst); 355 static void VisitLoadArrayPair(GraphVisitor *v, Inst *inst); 356 static void VisitStoreArrayPair(GraphVisitor *v, Inst *inst); 357 static void VisitLoadArrayPairI(GraphVisitor *v, Inst *inst); 358 static void VisitStoreArrayPairI(GraphVisitor *v, Inst *inst); 359 static void VisitLoadObject(GraphVisitor *v, Inst *inst); 360 static void VisitLoadResolvedObjectField(GraphVisitor *v, Inst *inst); 361 static void VisitStoreObject(GraphVisitor *v, Inst *inst); 362 static void VisitStoreResolvedObjectField(GraphVisitor *v, Inst *inst); 363 static void VisitCatchPhi(GraphVisitor *v, Inst *inst); 364 static void VisitPhi(GraphVisitor *v, Inst *inst); 365 static void VisitSelect(GraphVisitor *v, Inst *inst); 366 static void VisitSelectImm(GraphVisitor *v, Inst *inst); 367 static void VisitMov(GraphVisitor *v, Inst *inst); 368 static void VisitCastAnyTypeValue(GraphVisitor *v, Inst *inst); 369 static void VisitCastValueToAnyType(GraphVisitor *v, Inst *inst); 370 static void VisitGetAnyTypeName(GraphVisitor *v, Inst *inst); 371 static void VisitLoadConstantPool(GraphVisitor *v, Inst *inst); 372 static void VisitLoadLexicalEnv(GraphVisitor *v, Inst *inst); 373 static void VisitLoadObjectPair(GraphVisitor *v, Inst *inst); 374 static void VisitStoreObjectPair(GraphVisitor *v, Inst *inst); 375 376 /// Dynamic instructions 377 static void VisitLoadObjectDynamic(GraphVisitor *v, Inst *inst); 378 static void VisitStoreObjectDynamic(GraphVisitor *v, Inst *inst); 379 static void VisitLoadFromConstantPool(GraphVisitor *v, Inst *inst); 380 381 void VisitDefault([[maybe_unused]] Inst *inst) override; 382 AddDirectEdge(const Pointer & p)383 void AddDirectEdge(const Pointer &p) 384 { 385 direct_->push_back({p, p}); 386 } 387 AddConstantDirectEdge(Inst * inst,uint32_t id)388 void AddConstantDirectEdge(Inst *inst, uint32_t id) 389 { 390 direct_->push_back({Pointer::CreateObject(inst), Pointer::CreatePoolConstant(id)}); 391 } 392 AddCopyEdge(const Pointer & from,const Pointer & to)393 void AddCopyEdge(const Pointer &from, const Pointer &to) 394 { 395 copy_->push_back({from, to}); 396 } 397 GetClearInputsSet()398 ArenaSet<Inst *> *GetClearInputsSet() 399 { 400 inputsSet_->clear(); 401 return inputsSet_; 402 } 403 404 #include "optimizer/ir/visitor.inc" 405 406 private: 407 void Init(); 408 using PointerSet = ArenaUnorderedSet<Pointer, PointerHash, PointerEqual>; 409 template <class T> 410 using PointerMap = ArenaUnorderedMap<Pointer, T, PointerHash, PointerEqual>; 411 412 void SolveConstraints(); 413 414 /* Methods to extract pointer from instruction */ 415 static bool ParseInstruction(Inst *inst, Pointer *pointer); 416 static Pointer ParseArrayElement(Inst *inst); 417 static Pointer ParsePoolConstant(Inst *inst); 418 static Pointer ParseStaticField(Inst *inst); 419 static Pointer ParseObjectField(Inst *inst); 420 static Pointer ParseDynamicField(Inst *inst); 421 422 static Trilean IsSameOffsets(const Inst *off1, const Inst *off2); 423 static AliasType AliasingTwoArrayPointers(const Pointer *p1, const Pointer *p2); 424 425 static AliasType SingleIntersectionAliasing(const Pointer &p1, const Pointer &p2, const Pointer *intersection); 426 AliasType CheckMemAddressEmptyIntersectionCase(const PointerSet &aliases1, const PointerSet &aliases2, 427 const Pointer &p1, const Pointer &p2) const; 428 void SolveConstraintsMainLoop(Pointer &ref, Pointer &edge, bool &added, PointerSet &sols); 429 void DumpChains(std::ostream *out) const; 430 void DumpDirect(std::ostream *out) const; 431 void DumpCopy(std::ostream *out) const; 432 433 private: 434 PointerMap<PointerSet> pointsTo_; 435 436 // Local containers: 437 PointerMap<ArenaVector<Pointer>> *chains_ {nullptr}; 438 PointerPairVector *direct_ {nullptr}; 439 PointerPairVector *copy_ {nullptr}; 440 ArenaSet<Inst *> *inputsSet_ {nullptr}; 441 }; 442 } // namespace ark::compiler 443 444 #endif // COMPILER_OPTIMIZER_ANALYSIS_ALIAS_ANALYSIS_H 445