1 //===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines two classes: AliasSetTracker and AliasSet. These interfaces 10 // are used to classify a collection of memory locations into a maximal number 11 // of disjoint sets. Each AliasSet object constructed by the AliasSetTracker 12 // object refers to memory disjoint from the other sets. 13 // 14 // An AliasSetTracker can only be used on immutable IR. 15 // 16 //===----------------------------------------------------------------------===// 17 18 #ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H 19 #define LLVM_ANALYSIS_ALIASSETTRACKER_H 20 21 #include "llvm/ADT/DenseMap.h" 22 #include "llvm/ADT/SmallVector.h" 23 #include "llvm/ADT/ilist.h" 24 #include "llvm/ADT/ilist_node.h" 25 #include "llvm/Analysis/MemoryLocation.h" 26 #include "llvm/IR/PassManager.h" 27 #include "llvm/IR/ValueHandle.h" 28 #include "llvm/Support/Compiler.h" 29 #include <cassert> 30 #include <vector> 31 32 namespace llvm { 33 34 class AliasResult; 35 class AliasSetTracker; 36 class AnyMemSetInst; 37 class AnyMemTransferInst; 38 class BasicBlock; 39 class BatchAAResults; 40 class Function; 41 class Instruction; 42 class StoreInst; 43 class LoadInst; 44 enum class ModRefInfo : uint8_t; 45 class raw_ostream; 46 class VAArgInst; 47 class Value; 48 49 class AliasSet : public ilist_node<AliasSet> { 50 friend class AliasSetTracker; 51 52 // Forwarding pointer. 53 AliasSet *Forward = nullptr; 54 55 /// Memory locations in this alias set. 56 SmallVector<MemoryLocation, 0> MemoryLocs; 57 58 /// All instructions without a specific address in this alias set. 59 std::vector<AssertingVH<Instruction>> UnknownInsts; 60 61 /// Number of nodes pointing to this AliasSet plus the number of AliasSets 62 /// forwarding to it. 63 unsigned RefCount : 27; 64 65 // Signifies that this set should be considered to alias any pointer. 66 // Use when the tracker holding this set is saturated. 67 unsigned AliasAny : 1; 68 69 /// The kinds of access this alias set models. 70 /// 71 /// We keep track of whether this alias set merely refers to the locations of 72 /// memory (and not any particular access), whether it modifies or references 73 /// the memory, or whether it does both. The lattice goes from "NoAccess" to 74 /// either RefAccess or ModAccess, then to ModRefAccess as necessary. 75 enum AccessLattice { 76 NoAccess = 0, 77 RefAccess = 1, 78 ModAccess = 2, 79 ModRefAccess = RefAccess | ModAccess 80 }; 81 unsigned Access : 2; 82 83 /// The kind of alias relationship between pointers of the set. 84 /// 85 /// These represent conservatively correct alias results between any members 86 /// of the set. We represent these independently of the values of alias 87 /// results in order to pack it into a single bit. Lattice goes from 88 /// MustAlias to MayAlias. 89 enum AliasLattice { 90 SetMustAlias = 0, SetMayAlias = 1 91 }; 92 unsigned Alias : 1; 93 addRef()94 void addRef() { ++RefCount; } 95 dropRef(AliasSetTracker & AST)96 void dropRef(AliasSetTracker &AST) { 97 assert(RefCount >= 1 && "Invalid reference count detected!"); 98 if (--RefCount == 0) 99 removeFromTracker(AST); 100 } 101 102 public: 103 AliasSet(const AliasSet &) = delete; 104 AliasSet &operator=(const AliasSet &) = delete; 105 106 /// Accessors... isRef()107 bool isRef() const { return Access & RefAccess; } isMod()108 bool isMod() const { return Access & ModAccess; } isMustAlias()109 bool isMustAlias() const { return Alias == SetMustAlias; } isMayAlias()110 bool isMayAlias() const { return Alias == SetMayAlias; } 111 112 /// Return true if this alias set should be ignored as part of the 113 /// AliasSetTracker object. isForwardingAliasSet()114 bool isForwardingAliasSet() const { return Forward; } 115 116 /// Merge the specified alias set into this alias set. 117 LLVM_ABI void mergeSetIn(AliasSet &AS, AliasSetTracker &AST, 118 BatchAAResults &BatchAA); 119 120 // Alias Set iteration - Allow access to all of the memory locations which are 121 // part of this alias set. 122 using iterator = SmallVectorImpl<MemoryLocation>::const_iterator; begin()123 iterator begin() const { return MemoryLocs.begin(); } end()124 iterator end() const { return MemoryLocs.end(); } 125 size()126 unsigned size() const { return MemoryLocs.size(); } 127 128 /// Retrieve the pointer values for the memory locations in this alias set. 129 /// The order matches that of the memory locations, but duplicate pointer 130 /// values are omitted. 131 using PointerVector = SmallVector<const Value *, 8>; 132 LLVM_ABI PointerVector getPointers() const; 133 134 LLVM_ABI void print(raw_ostream &OS) const; 135 LLVM_ABI void dump() const; 136 137 private: 138 // Can only be created by AliasSetTracker. AliasSet()139 AliasSet() 140 : RefCount(0), AliasAny(false), Access(NoAccess), Alias(SetMustAlias) {} 141 142 LLVM_ABI void removeFromTracker(AliasSetTracker &AST); 143 144 void addMemoryLocation(AliasSetTracker &AST, const MemoryLocation &MemLoc, 145 bool KnownMustAlias = false); 146 void addUnknownInst(Instruction *I, BatchAAResults &AA); 147 148 public: 149 /// If the specified memory location "may" (or must) alias one of the members 150 /// in the set return the appropriate AliasResult. Otherwise return NoAlias. 151 LLVM_ABI AliasResult aliasesMemoryLocation(const MemoryLocation &MemLoc, 152 BatchAAResults &AA) const; 153 154 LLVM_ABI ModRefInfo aliasesUnknownInst(const Instruction *Inst, 155 BatchAAResults &AA) const; 156 }; 157 158 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) { 159 AS.print(OS); 160 return OS; 161 } 162 163 class AliasSetTracker { 164 BatchAAResults &AA; 165 ilist<AliasSet> AliasSets; 166 167 using PointerMapType = DenseMap<AssertingVH<const Value>, AliasSet *>; 168 169 // Map from pointer values to the alias set holding one or more memory 170 // locations with that pointer value. 171 PointerMapType PointerMap; 172 173 public: 174 /// Create an empty collection of AliasSets, and use the specified alias 175 /// analysis object to disambiguate load and store addresses. AliasSetTracker(BatchAAResults & AA)176 explicit AliasSetTracker(BatchAAResults &AA) : AA(AA) {} ~AliasSetTracker()177 ~AliasSetTracker() { clear(); } 178 179 /// These methods are used to add different types of instructions to the alias 180 /// sets. Adding a new instruction can result in one of three actions 181 /// happening: 182 /// 183 /// 1. If the instruction doesn't alias any other sets, create a new set. 184 /// 2. If the instruction aliases exactly one set, add it to the set 185 /// 3. If the instruction aliases multiple sets, merge the sets, and add 186 /// the instruction to the result. 187 /// 188 LLVM_ABI void add(const MemoryLocation &Loc); 189 LLVM_ABI void add(LoadInst *LI); 190 LLVM_ABI void add(StoreInst *SI); 191 LLVM_ABI void add(VAArgInst *VAAI); 192 LLVM_ABI void add(AnyMemSetInst *MSI); 193 LLVM_ABI void add(AnyMemTransferInst *MTI); 194 LLVM_ABI void 195 add(Instruction *I); // Dispatch to one of the other add methods... 196 LLVM_ABI void add(BasicBlock &BB); // Add all instructions in basic block 197 LLVM_ABI void 198 add(const AliasSetTracker &AST); // Add alias relations from another AST 199 LLVM_ABI void addUnknown(Instruction *I); 200 201 LLVM_ABI void clear(); 202 203 /// Return the alias sets that are active. getAliasSets()204 const ilist<AliasSet> &getAliasSets() const { return AliasSets; } 205 206 /// Return the alias set which contains the specified memory location. If 207 /// the memory location aliases two or more existing alias sets, will have 208 /// the effect of merging those alias sets before the single resulting alias 209 /// set is returned. 210 LLVM_ABI AliasSet &getAliasSetFor(const MemoryLocation &MemLoc); 211 212 /// Return the underlying alias analysis object used by this tracker. getAliasAnalysis()213 BatchAAResults &getAliasAnalysis() const { return AA; } 214 215 using iterator = ilist<AliasSet>::iterator; 216 using const_iterator = ilist<AliasSet>::const_iterator; 217 begin()218 const_iterator begin() const { return AliasSets.begin(); } end()219 const_iterator end() const { return AliasSets.end(); } 220 begin()221 iterator begin() { return AliasSets.begin(); } end()222 iterator end() { return AliasSets.end(); } 223 224 LLVM_ABI void print(raw_ostream &OS) const; 225 LLVM_ABI void dump() const; 226 227 private: 228 friend class AliasSet; 229 230 // The total number of memory locations contained in all alias sets. 231 unsigned TotalAliasSetSize = 0; 232 233 // A non-null value signifies this AST is saturated. A saturated AST lumps 234 // all elements into a single "May" set. 235 AliasSet *AliasAnyAS = nullptr; 236 237 void removeAliasSet(AliasSet *AS); 238 239 // Update an alias set field to point to its real destination. If the field is 240 // pointing to a set that has been merged with another set and is forwarding, 241 // the field is updated to point to the set obtained by following the 242 // forwarding links. The Forward fields of intermediate alias sets are 243 // collapsed as well, and alias set reference counts are updated to reflect 244 // the new situation. collapseForwardingIn(AliasSet * & AS)245 void collapseForwardingIn(AliasSet *&AS) { 246 if (AS->Forward) { 247 collapseForwardingIn(AS->Forward); 248 // Swap out AS for AS->Forward, while updating reference counts. 249 AliasSet *NewAS = AS->Forward; 250 NewAS->addRef(); 251 AS->dropRef(*this); 252 AS = NewAS; 253 } 254 } 255 256 AliasSet &addMemoryLocation(MemoryLocation Loc, AliasSet::AccessLattice E); 257 AliasSet *mergeAliasSetsForMemoryLocation(const MemoryLocation &MemLoc, 258 AliasSet *PtrAS, 259 bool &MustAliasAll); 260 261 /// Merge all alias sets into a single set that is considered to alias 262 /// any memory location or instruction. 263 AliasSet &mergeAllAliasSets(); 264 265 AliasSet *findAliasSetForUnknownInst(Instruction *Inst); 266 }; 267 268 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) { 269 AST.print(OS); 270 return OS; 271 } 272 273 class AliasSetsPrinterPass : public PassInfoMixin<AliasSetsPrinterPass> { 274 raw_ostream &OS; 275 276 public: 277 LLVM_ABI explicit AliasSetsPrinterPass(raw_ostream &OS); 278 LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); isRequired()279 static bool isRequired() { return true; } 280 }; 281 282 } // end namespace llvm 283 284 #endif // LLVM_ANALYSIS_ALIASSETTRACKER_H 285