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