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