1 /* 2 * Copyright (c) 2025 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_VISITOR_H 17 #define COMPILER_OPTIMIZER_ANALYSIS_ALIAS_VISITOR_H 18 19 #include "optimizer/ir/graph.h" 20 #include "optimizer/ir/graph_visitor.h" 21 #include "utils/arena_containers.h" 22 23 namespace ark::compiler { 24 25 enum PointerType { 26 // Reference to unknown object. 27 // Valid fields: base 28 OBJECT, 29 // Constant from pool 30 // Valid fields: imm 31 POOL_CONSTANT, 32 // Object's field 33 // Valid fields: base, imm, type_ptr 34 OBJECT_FIELD, 35 // Static field of the object 36 // Valid fields: imm, type_ptr 37 STATIC_FIELD, 38 // Array pointer 39 // Valid fields 40 // * in common: base, idx 41 // * in case LoadArrayPair/StoreArrayPair: base, idx, imm 42 // * in case LoadArrayPairI/StoreArrayPairI, LoadArrayI/StoreArrayI: base, imm 43 ARRAY_ELEMENT, 44 // Dictionary pointer 45 // Valid fields: base, idx 46 DICTIONARY_ELEMENT, 47 // Valid fields: base, idx, imm 48 RAW_OFFSET, 49 // Can be any other type of offset, so can alias with all of them. 50 // Valid fields: base 51 UNKNOWN_OFFSET 52 }; 53 54 class PointerOffset { 55 protected: PointerOffset(PointerType type,uint64_t imm,const void * typePtr)56 PointerOffset(PointerType type, uint64_t imm, const void *typePtr) : type_(type), imm_(imm), typePtr_(typePtr) {}; 57 PointerOffset() = default; 58 59 public: 60 // Used for fields with offset not known in compile-time CreateUnknownOffset()61 static PointerOffset CreateUnknownOffset() 62 { 63 return {UNKNOWN_OFFSET, 0, nullptr}; 64 } 65 66 // Used for default fields in TypePropagation CreateDefaultField()67 static PointerOffset CreateDefaultField() 68 { 69 return {UNKNOWN_OFFSET, 1, nullptr}; 70 } 71 GetType()72 PointerType GetType() const 73 { 74 return type_; 75 } 76 GetImm()77 uint64_t GetImm() const 78 { 79 return imm_; 80 } 81 GetTypePtr()82 const void *GetTypePtr() const 83 { 84 return typePtr_; 85 } 86 87 struct Hash { operatorHash88 uint32_t operator()(PointerOffset const &p) const 89 { 90 if (p.GetTypePtr() == nullptr) { 91 return std::hash<uint64_t> {}(p.GetImm()) ^ std::hash<PointerType> {}(p.type_); 92 } 93 return std::hash<const void *> {}(p.GetTypePtr()); 94 } 95 }; 96 97 bool operator==(const PointerOffset &p) const 98 { 99 return GetType() == p.GetType() && HasSameOffset(p); 100 } 101 HasSameOffset(const PointerOffset & p)102 bool HasSameOffset(const PointerOffset &p) const 103 { 104 if (typePtr_ == nullptr && p.typePtr_ == nullptr) { 105 return imm_ == p.imm_; 106 } 107 return typePtr_ == p.typePtr_; 108 } 109 110 void Dump(std::ostream *out) const; 111 112 template <class T> 113 using Map = ArenaUnorderedMap<PointerOffset, T, Hash>; 114 115 private: 116 PointerType type_ = OBJECT; 117 uint64_t imm_ = 0; 118 const void *typePtr_ {nullptr}; 119 }; 120 121 std::ostream &operator<<(std::ostream &out, const PointerOffset &p); 122 123 class Pointer : private PointerOffset { 124 private: Pointer(PointerType type,const Inst * base,const Inst * idx,uint64_t imm,const void * typePtr)125 Pointer(PointerType type, const Inst *base, const Inst *idx, uint64_t imm, const void *typePtr) 126 : PointerOffset(type, imm, typePtr), base_(base), idx_(idx) {}; 127 128 public: Pointer(const Inst * base,const PointerOffset & offset)129 Pointer(const Inst *base, const PointerOffset &offset) : PointerOffset(offset), base_(base) {} 130 Pointer() = default; 131 132 using PointerOffset::GetImm; 133 using PointerOffset::GetType; 134 using PointerOffset::GetTypePtr; 135 CreateObject(const Inst * base)136 static Pointer CreateObject(const Inst *base) 137 { 138 ASSERT(base != nullptr); 139 ASSERT(base->IsReferenceOrAny() || base->GetBasicBlock()->GetGraph()->IsDynamicMethod() || base->IsConst() || 140 base->GetType() == DataType::POINTER); 141 return Pointer(OBJECT, base, nullptr, 0, nullptr); 142 } 143 CreatePoolConstant(uint32_t typeId)144 static Pointer CreatePoolConstant(uint32_t typeId) 145 { 146 return Pointer(POOL_CONSTANT, nullptr, nullptr, typeId, nullptr); 147 } 148 149 static Pointer CreateStaticField(uint32_t typeId, const void *typePtr = nullptr) 150 { 151 return Pointer(STATIC_FIELD, nullptr, nullptr, typeId, typePtr); 152 } 153 154 static Pointer CreateObjectField(const Inst *base, uint32_t typeId, const void *typePtr = nullptr) 155 { 156 ASSERT(base != nullptr); 157 return Pointer(OBJECT_FIELD, base, nullptr, typeId, typePtr); 158 } 159 160 static Pointer CreateArrayElement(const Inst *array, const Inst *idx, uint64_t imm = 0) 161 { 162 ASSERT(array != nullptr); 163 return Pointer(ARRAY_ELEMENT, array, idx, imm, nullptr); 164 } 165 166 static Pointer CreateRawOffset(const Inst *obj, const Inst *idx, uint64_t imm = 0) 167 { 168 ASSERT(obj != nullptr); 169 return Pointer(RAW_OFFSET, obj, idx, imm, nullptr); 170 } 171 172 static Pointer CreateDictionaryElement(const Inst *array, const Inst *idx, uint64_t imm = 0) 173 { 174 ASSERT(array != nullptr); 175 return Pointer(DICTIONARY_ELEMENT, array, idx, imm, nullptr); 176 } 177 CreateUnknownOffset(const Inst * obj)178 static Pointer CreateUnknownOffset(const Inst *obj) 179 { 180 return Pointer(UNKNOWN_OFFSET, obj, nullptr, 0, nullptr); 181 } 182 GetBase()183 const Inst *GetBase() const 184 { 185 return base_; 186 } 187 GetIdx()188 const Inst *GetIdx() const 189 { 190 return idx_; 191 } 192 193 void Dump(std::ostream *out) const; 194 195 bool IsNotEscapingAlias() const; 196 197 /// Returns true if reference is created in the current function 198 bool IsLocalCreatedAlias() const; 199 200 struct Hash { operatorHash201 uint32_t operator()(Pointer const &p) const 202 { 203 auto instHasher = std::hash<const Inst *> {}; 204 uint32_t hash = instHasher(p.GetBase()); 205 hash += instHasher(p.GetIdx()); 206 if (p.GetTypePtr() == nullptr) { 207 hash += std::hash<uint64_t> {}(p.GetImm()); 208 } else { 209 hash += std::hash<const void *> {}(p.GetTypePtr()); 210 } 211 return hash; 212 } 213 }; 214 215 bool operator==(const Pointer &p) const 216 { 217 auto ret = PointerOffset::operator==(p) && GetBase() == p.GetBase() && GetIdx() == p.GetIdx(); 218 return ret; 219 } 220 HasSameOffset(const Pointer & p)221 bool HasSameOffset(const Pointer &p) const 222 { 223 return PointerOffset::HasSameOffset(p); 224 } 225 IsObject()226 bool IsObject() const 227 { 228 return GetType() == OBJECT; 229 } 230 GetOffset()231 PointerOffset GetOffset() const 232 { 233 // copy the base class PointerOffset 234 return {static_cast<const PointerOffset &>(*this)}; 235 } 236 DropIdx()237 Pointer DropIdx() const 238 { 239 if (idx_ == nullptr) { 240 return *this; 241 } 242 ASSERT(GetTypePtr() == nullptr); 243 if (!idx_->IsConst() || GetType() == DICTIONARY_ELEMENT) { 244 return CreateUnknownOffset(base_); 245 } 246 ASSERT(GetType() == ARRAY_ELEMENT || GetType() == RAW_OFFSET); 247 auto newImm = GetImm() + idx_->CastToConstant()->GetIntValue(); 248 return {GetType(), base_, nullptr, newImm, GetTypePtr()}; 249 } 250 251 using Set = ArenaUnorderedSet<Pointer, Hash>; 252 template <class T> 253 using Map = ArenaUnorderedMap<Pointer, T, Hash>; 254 255 private: 256 /** 257 * Returns true if a reference escapes the scope of current function: 258 * Various function calls, constructors and stores to another objects' fields, arrays 259 */ 260 static bool IsEscapingAlias(const Inst *inst); 261 262 private: 263 const Inst *base_ {nullptr}; 264 const Inst *idx_ {nullptr}; 265 }; 266 267 std::ostream &operator<<(std::ostream &out, const Pointer &p); 268 269 class AliasVisitor : public GraphVisitor { 270 public: 271 void Init(ArenaAllocator *allocator); 272 GetClearInputsSet()273 ArenaSet<Inst *> *GetClearInputsSet() 274 { 275 ASSERT(inputsSet_ != nullptr); 276 inputsSet_->clear(); 277 return inputsSet_; 278 } 279 280 static bool ParseInstruction(Inst *inst, Pointer *pointer); 281 282 /** 283 * Sort IR instructions into two constraint groups: 284 * Direct: introduce the alias 285 * Copy: copy one alias to another 286 */ 287 288 /// Instructions that definitely are not an alias of anything. 289 static void VisitNullPtr(GraphVisitor *v, Inst *inst); 290 static void VisitLoadUniqueObject(GraphVisitor *v, Inst *inst); 291 static void VisitLoadUndefined(GraphVisitor *v, Inst *inst); 292 static void VisitInitObject(GraphVisitor *v, Inst *inst); 293 static void VisitNewObject(GraphVisitor *v, Inst *inst); 294 static void VisitNewArray(GraphVisitor *v, Inst *inst); 295 static void VisitMultiArray(GraphVisitor *v, Inst *inst); 296 static void VisitInitEmptyString(GraphVisitor *v, Inst *inst); 297 static void VisitInitString(GraphVisitor *v, Inst *inst); 298 /** 299 * Instructions that can introduce references that are an alias of 300 * something already existed. 301 */ 302 static void VisitConstant(GraphVisitor *v, Inst *inst); 303 static void VisitParameter(GraphVisitor *v, Inst *inst); 304 static void VisitLiveIn(GraphVisitor *v, Inst *inst); 305 static void VisitLoadImmediate(GraphVisitor *v, Inst *inst); 306 static void VisitBitcast(GraphVisitor *v, Inst *inst); 307 static void VisitIntrinsic(GraphVisitor *v, Inst *inst); 308 static void VisitBuiltin(GraphVisitor *v, Inst *inst); 309 static void VisitCallStatic(GraphVisitor *v, Inst *inst); 310 static void VisitCallResolvedStatic(GraphVisitor *v, Inst *inst); 311 static void VisitCallVirtual(GraphVisitor *v, Inst *inst); 312 static void VisitCallResolvedVirtual(GraphVisitor *v, Inst *inst); 313 static void VisitCallDynamic(GraphVisitor *v, Inst *inst); 314 static void VisitCallNative(GraphVisitor *v, Inst *inst); 315 static void VisitCall(GraphVisitor *v, Inst *inst); 316 static void VisitGetManagedClassObject(GraphVisitor *v, Inst *inst); 317 static void VisitResolveObjectFieldStatic(GraphVisitor *v, Inst *inst); 318 319 /// Instructions that introduce static fields (global variables). 320 static void VisitLoadStatic(GraphVisitor *v, Inst *inst); 321 static void VisitLoadResolvedObjectFieldStatic(GraphVisitor *v, Inst *inst); 322 static void VisitStoreStatic(GraphVisitor *v, Inst *inst); 323 static void VisitStoreResolvedObjectFieldStatic(GraphVisitor *v, Inst *inst); 324 static void VisitUnresolvedStoreStatic(GraphVisitor *v, Inst *inst); 325 326 /// Instructions that introduce unique constant references (global constants). 327 static void VisitLoadRuntimeClass(GraphVisitor *v, Inst *inst); 328 static void VisitLoadClass(GraphVisitor *v, Inst *inst); 329 static void VisitLoadAndInitClass(GraphVisitor *v, Inst *inst); 330 static void VisitUnresolvedLoadAndInitClass(GraphVisitor *v, Inst *inst); 331 static void VisitGetGlobalVarAddress(GraphVisitor *v, Inst *inst); 332 static void VisitLoadString(GraphVisitor *v, Inst *inst); 333 static void VisitLoadConstArray(GraphVisitor *v, Inst *inst); 334 static void VisitLoadType(GraphVisitor *v, Inst *inst); 335 static void VisitUnresolvedLoadType(GraphVisitor *v, Inst *inst); 336 static void VisitLoadObjFromConst(GraphVisitor *v, Inst *inst); 337 338 /// Instructions that introduce aliases. 339 static void VisitLoadArray(GraphVisitor *v, Inst *inst); 340 static void VisitStoreArray(GraphVisitor *v, Inst *inst); 341 static void VisitLoadArrayI(GraphVisitor *v, Inst *inst); 342 static void VisitStoreArrayI(GraphVisitor *v, Inst *inst); 343 static void VisitLoadArrayPair(GraphVisitor *v, Inst *inst); 344 static void VisitStoreArrayPair(GraphVisitor *v, Inst *inst); 345 static void VisitLoadArrayPairI(GraphVisitor *v, Inst *inst); 346 static void VisitStoreArrayPairI(GraphVisitor *v, Inst *inst); 347 static void VisitLoadObject(GraphVisitor *v, Inst *inst); 348 static void VisitLoadResolvedObjectField(GraphVisitor *v, Inst *inst); 349 static void VisitStoreObject(GraphVisitor *v, Inst *inst); 350 static void VisitStoreResolvedObjectField(GraphVisitor *v, Inst *inst); 351 static void VisitLoad(GraphVisitor *v, Inst *inst); 352 static void VisitLoadNative(GraphVisitor *v, Inst *inst); 353 static void VisitStore(GraphVisitor *v, Inst *inst); 354 static void VisitStoreNative(GraphVisitor *v, Inst *inst); 355 static void VisitLoadI(GraphVisitor *v, Inst *inst); 356 static void VisitStoreI(GraphVisitor *v, Inst *inst); 357 static void VisitCatchPhi(GraphVisitor *v, Inst *inst); 358 static void VisitPhi(GraphVisitor *v, Inst *inst); 359 static void VisitSelect(GraphVisitor *v, Inst *inst); 360 static void VisitSelectImm(GraphVisitor *v, Inst *inst); 361 static void VisitMov(GraphVisitor *v, Inst *inst); 362 static void VisitRefTypeCheck(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 static void VisitLoadObjectPair(GraphVisitor *v, Inst *inst); 369 static void VisitStoreObjectPair(GraphVisitor *v, Inst *inst); 370 371 /// Dynamic instructions 372 static void VisitLoadObjectDynamic(GraphVisitor *v, Inst *inst); 373 static void VisitStoreObjectDynamic(GraphVisitor *v, Inst *inst); 374 static void VisitLoadFromConstantPool(GraphVisitor *v, Inst *inst); 375 376 void VisitDefault([[maybe_unused]] Inst *inst) override; 377 378 protected: 379 virtual void AddDirectEdge(const Pointer &p) = 0; 380 virtual void AddConstantDirectEdge(Inst *inst, uint32_t id) = 0; 381 virtual void AddCopyEdge(const Pointer &from, const Pointer &to) = 0; 382 virtual void AddPseudoCopyEdge(const Pointer &base, const Pointer &field) = 0; SetVolatile(const Pointer & pointer,Inst * memInst)383 virtual void SetVolatile([[maybe_unused]] const Pointer &pointer, [[maybe_unused]] Inst *memInst) {} VisitHeapInv(Inst * inst)384 virtual void VisitHeapInv([[maybe_unused]] Inst *inst) {} Escape(const Inst * inst)385 virtual void Escape([[maybe_unused]] const Inst *inst) {} 386 virtual void VisitAllocation([[maybe_unused]] Inst *inst) = 0; 387 388 #include "optimizer/ir/visitor.inc" 389 390 private: 391 void EscapeInputsAndInv(Inst *inst); 392 393 private: 394 ArenaSet<Inst *> *inputsSet_ {nullptr}; 395 }; 396 397 } // namespace ark::compiler 398 399 #endif // COMPILER_OPTIMIZER_ANALYSIS_ALIAS_VISITOR_H 400