1 /* 2 * Copyright (c) 2021-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_ANALYSIS_H 17 #define COMPILER_OPTIMIZER_ANALYSIS_ALIAS_ANALYSIS_H 18 19 #include "alias_visitor.h" 20 #include "optimizer/ir/graph_visitor.h" 21 #include "optimizer/pass.h" 22 #include "utils/arena_containers.h" 23 24 namespace ark::compiler { 25 class BasicBlock; 26 class Graph; 27 28 enum AliasType : uint8_t { 29 // Proved that references are not aliases 30 NO_ALIAS, 31 // References may or may not alias each other (cannot be proven statically) 32 MAY_ALIAS, 33 // References are proven aliases 34 MUST_ALIAS, 35 // Variation of MAY_ALIAS 36 ALIAS_IF_BASE_EQUALS, 37 }; 38 39 class PointerWithInfo; 40 41 struct PointerInfo { 42 Pointer::Set pointsTo; 43 bool local; 44 bool isVolatile; 45 }; 46 47 class PointerWithInfo : private std::pair<const Pointer, PointerInfo> { 48 private: 49 using Base = std::pair<const Pointer, PointerInfo>; SetLocal(bool isLocal)50 void SetLocal(bool isLocal) 51 { 52 second.local = isLocal; 53 } 54 55 public: 56 // PointerWithInfo(const std::pair<const Pointer, PointerInfo> &pair) {} 57 PointerWithInfo() = delete; 58 NO_COPY_SEMANTIC(PointerWithInfo); 59 NO_MOVE_SEMANTIC(PointerWithInfo); 60 ~PointerWithInfo() = delete; 61 FromPair(Base & base)62 static PointerWithInfo &FromPair(Base &base) 63 { 64 return static_cast<PointerWithInfo &>(base); 65 } 66 FromPair(const Base & base)67 static const PointerWithInfo &FromPair(const Base &base) 68 { 69 return static_cast<const PointerWithInfo &>(base); 70 } 71 GetPointer()72 const Pointer &GetPointer() const 73 { 74 return first; 75 } 76 GetType()77 PointerType GetType() const 78 { 79 return GetPointer().GetType(); 80 } 81 GetBase()82 const Inst *GetBase() const 83 { 84 return GetPointer().GetBase(); 85 } 86 GetIdx()87 const Inst *GetIdx() const 88 { 89 return GetPointer().GetIdx(); 90 } 91 GetImm()92 uint64_t GetImm() const 93 { 94 return GetPointer().GetImm(); 95 } 96 GetTypePtr()97 const void *GetTypePtr() const 98 { 99 return GetPointer().GetTypePtr(); 100 } 101 102 // true if all aliases are created locally and don't escape IsLocal()103 bool IsLocal() const 104 { 105 return second.local; 106 } 107 108 // true if all aliases are created locally 109 bool IsLocalCreated() const; 110 IsVolatile()111 bool IsVolatile() const 112 { 113 return second.isVolatile; 114 } 115 PointsTo()116 const Pointer::Set &PointsTo() const 117 { 118 return second.pointsTo; 119 } 120 SetVolatile(bool isVolatile)121 void SetVolatile(bool isVolatile) 122 { 123 second.isVolatile = isVolatile; 124 } 125 UpdateLocal(bool sourceIsLocal)126 bool UpdateLocal(bool sourceIsLocal) 127 { 128 if (IsLocal() && !sourceIsLocal) { 129 SetLocal(false); 130 return true; 131 } 132 return false; 133 } 134 Insert(Pointer p)135 bool Insert(Pointer p) 136 { 137 return second.pointsTo.insert(p).second; 138 } 139 }; 140 141 // NOLINTNEXTLINE(fuchsia-multiple-inheritance) 142 class AliasAnalysis : public Analysis, public AliasVisitor { 143 public: 144 enum class Trilean { 145 TRUE, 146 UNKNOWN, 147 FALSE, 148 }; 149 150 using PointerPairVector = ArenaVector<std::pair<Pointer, Pointer>>; 151 152 explicit AliasAnalysis(Graph *graph); 153 NO_MOVE_SEMANTIC(AliasAnalysis); 154 NO_COPY_SEMANTIC(AliasAnalysis); 155 ~AliasAnalysis() override = default; 156 157 bool RunImpl() override; 158 GetPassName()159 const char *GetPassName() const override 160 { 161 return "AliasAnalysis"; 162 } 163 164 template <bool REFINED = false> 165 AliasType CheckInstAlias(Inst *mem1, Inst *mem2) const; 166 AliasType CheckRefAlias(Inst *ref1, Inst *ref2) const; 167 void Dump(std::ostream *out) const; 168 169 const ArenaVector<BasicBlock *> &GetBlocksToVisit() const override; 170 171 const PointerWithInfo &GetPointerInfo(const Pointer &pointer) const; 172 PointerWithInfo &GetPointerInfo(const Pointer &pointer); 173 174 protected: AddDirectEdge(const Pointer & p)175 void AddDirectEdge(const Pointer &p) override 176 { 177 direct_->push_back({p, p}); 178 } 179 VisitAllocation(Inst * inst)180 void VisitAllocation(Inst *inst) override 181 { 182 AddDirectEdge(Pointer::CreateObject(inst)); 183 } 184 185 void AddConstantDirectEdge(Inst *inst, uint32_t id) override; 186 AddCopyEdge(const Pointer & from,const Pointer & to)187 void AddCopyEdge(const Pointer &from, const Pointer &to) override 188 { 189 copy_->push_back({from, to}); 190 AddEscapeEdge(to, from); 191 } 192 AddPseudoCopyEdge(const Pointer & base,const Pointer & field)193 void AddPseudoCopyEdge(const Pointer &base, const Pointer &field) override 194 { 195 copy_->push_back({base, field}); 196 AddEscapeEdge(base, field); 197 AddEscapeEdge(field, base); 198 } 199 200 void SetVolatile(const Pointer &pointer, Inst *memInst) override; 201 202 private: 203 void Init(); 204 void CreatePointerInfo(const Pointer &pointer, bool isVolatile = false); 205 206 void FindEscapingPointers(); 207 void AddEscapeEdge(const Pointer &from, const Pointer &to); 208 void PropagateEscaped(const ArenaVector<Pointer> &escaping, ArenaVector<const PointerWithInfo *> &worklist); 209 void SolveConstraints(); 210 211 static Trilean IsSameOffsets(const Inst *off1, const Inst *off2); 212 static AliasType AliasingTwoArrayPointers(const Pointer *p1, const Pointer *p2); 213 214 template <bool REFINED = false> 215 AliasType CheckMemAddress(const Pointer &p1, const Pointer &p2, bool isVolatile) const; 216 template <bool REFINED = false> 217 AliasType SingleIntersectionAliasing(const Pointer &p1, const Pointer &p2, const PointerWithInfo *commonBase, 218 bool isVolatile) const; 219 AliasType CheckMemAddressEmptyIntersectionCase(const PointerWithInfo &base1, const PointerWithInfo &base2, 220 const Pointer &p1, const Pointer &p2) const; 221 void SolveConstraintsMainLoop(const PointerWithInfo *ref, PointerWithInfo *edge, bool &added); 222 void DumpChains(std::ostream *out) const; 223 void DumpDirect(std::ostream *out) const; 224 void DumpCopy(std::ostream *out) const; 225 226 private: 227 ArenaUnorderedMap<Pointer, PointerInfo, Pointer::Hash> pointerInfo_; 228 229 // Local containers: 230 Pointer::Map<ArenaVector<Pointer>> *chains_ {nullptr}; 231 Pointer::Map<ArenaVector<Pointer>> *reverseChains_ {nullptr}; 232 PointerPairVector *direct_ {nullptr}; 233 PointerPairVector *copy_ {nullptr}; 234 }; 235 } // namespace ark::compiler 236 237 #endif // COMPILER_OPTIMIZER_ANALYSIS_ALIAS_ANALYSIS_H 238