1 //===- BasicAliasAnalysis.h - Stateless, local Alias Analysis ---*- 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 /// \file 9 /// This is the interface for LLVM's primary stateless and local alias analysis. 10 /// 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_ANALYSIS_BASICALIASANALYSIS_H 14 #define LLVM_ANALYSIS_BASICALIASANALYSIS_H 15 16 #include "llvm/ADT/DenseMap.h" 17 #include "llvm/ADT/Optional.h" 18 #include "llvm/ADT/SmallPtrSet.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include "llvm/Analysis/AliasAnalysis.h" 21 #include "llvm/IR/PassManager.h" 22 #include "llvm/Pass.h" 23 #include <algorithm> 24 #include <cstdint> 25 #include <memory> 26 #include <utility> 27 28 namespace llvm { 29 30 struct AAMDNodes; 31 class APInt; 32 class AssumptionCache; 33 class BasicBlock; 34 class DataLayout; 35 class DominatorTree; 36 class Function; 37 class GEPOperator; 38 class PHINode; 39 class SelectInst; 40 class TargetLibraryInfo; 41 class PhiValues; 42 class Value; 43 44 /// This is the AA result object for the basic, local, and stateless alias 45 /// analysis. It implements the AA query interface in an entirely stateless 46 /// manner. As one consequence, it is never invalidated due to IR changes. 47 /// While it does retain some storage, that is used as an optimization and not 48 /// to preserve information from query to query. However it does retain handles 49 /// to various other analyses and must be recomputed when those analyses are. 50 class BasicAAResult : public AAResultBase<BasicAAResult> { 51 friend AAResultBase<BasicAAResult>; 52 53 const DataLayout &DL; 54 const Function &F; 55 const TargetLibraryInfo &TLI; 56 AssumptionCache &AC; 57 DominatorTree *DT; 58 PhiValues *PV; 59 60 public: 61 BasicAAResult(const DataLayout &DL, const Function &F, 62 const TargetLibraryInfo &TLI, AssumptionCache &AC, 63 DominatorTree *DT = nullptr, PhiValues *PV = nullptr) AAResultBase()64 : AAResultBase(), DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), PV(PV) {} 65 BasicAAResult(const BasicAAResult & Arg)66 BasicAAResult(const BasicAAResult &Arg) 67 : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC), 68 DT(Arg.DT), PV(Arg.PV) {} BasicAAResult(BasicAAResult && Arg)69 BasicAAResult(BasicAAResult &&Arg) 70 : AAResultBase(std::move(Arg)), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), 71 AC(Arg.AC), DT(Arg.DT), PV(Arg.PV) {} 72 73 /// Handle invalidation events in the new pass manager. 74 bool invalidate(Function &Fn, const PreservedAnalyses &PA, 75 FunctionAnalysisManager::Invalidator &Inv); 76 77 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, 78 AAQueryInfo &AAQI); 79 80 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, 81 AAQueryInfo &AAQI); 82 83 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, 84 AAQueryInfo &AAQI); 85 86 /// Chases pointers until we find a (constant global) or not. 87 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, 88 bool OrLocal); 89 90 /// Get the location associated with a pointer argument of a callsite. 91 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx); 92 93 /// Returns the behavior when calling the given call site. 94 FunctionModRefBehavior getModRefBehavior(const CallBase *Call); 95 96 /// Returns the behavior when calling the given function. For use when the 97 /// call site is not known. 98 FunctionModRefBehavior getModRefBehavior(const Function *Fn); 99 100 private: 101 // A linear transformation of a Value; this class represents ZExt(SExt(V, 102 // SExtBits), ZExtBits) * Scale + Offset. 103 struct VariableGEPIndex { 104 // An opaque Value - we can't decompose this further. 105 const Value *V; 106 107 // We need to track what extensions we've done as we consider the same Value 108 // with different extensions as different variables in a GEP's linear 109 // expression; 110 // e.g.: if V == -1, then sext(x) != zext(x). 111 unsigned ZExtBits; 112 unsigned SExtBits; 113 114 APInt Scale; 115 116 // Context instruction to use when querying information about this index. 117 const Instruction *CxtI; 118 dumpVariableGEPIndex119 void dump() const { 120 print(dbgs()); 121 dbgs() << "\n"; 122 } printVariableGEPIndex123 void print(raw_ostream &OS) const { 124 OS << "(V=" << V->getName() 125 << ", zextbits=" << ZExtBits 126 << ", sextbits=" << SExtBits 127 << ", scale=" << Scale << ")"; 128 } 129 }; 130 131 // Represents the internal structure of a GEP, decomposed into a base pointer, 132 // constant offsets, and variable scaled indices. 133 struct DecomposedGEP { 134 // Base pointer of the GEP 135 const Value *Base; 136 // Total constant offset from base. 137 APInt Offset; 138 // Scaled variable (non-constant) indices. 139 SmallVector<VariableGEPIndex, 4> VarIndices; 140 // Is GEP index scale compile-time constant. 141 bool HasCompileTimeConstantScale; 142 // Are all operations inbounds GEPs or non-indexing operations? 143 // (None iff expression doesn't involve any geps) 144 Optional<bool> InBounds; 145 dumpDecomposedGEP146 void dump() const { 147 print(dbgs()); 148 dbgs() << "\n"; 149 } printDecomposedGEP150 void print(raw_ostream &OS) const { 151 OS << "(DecomposedGEP Base=" << Base->getName() 152 << ", Offset=" << Offset 153 << ", VarIndices=["; 154 for (size_t i = 0; i < VarIndices.size(); i++) { 155 if (i != 0) 156 OS << ", "; 157 VarIndices[i].print(OS); 158 } 159 OS << "], HasCompileTimeConstantScale=" << HasCompileTimeConstantScale 160 << ")"; 161 } 162 }; 163 164 /// Tracks phi nodes we have visited. 165 /// 166 /// When interpret "Value" pointer equality as value equality we need to make 167 /// sure that the "Value" is not part of a cycle. Otherwise, two uses could 168 /// come from different "iterations" of a cycle and see different values for 169 /// the same "Value" pointer. 170 /// 171 /// The following example shows the problem: 172 /// %p = phi(%alloca1, %addr2) 173 /// %l = load %ptr 174 /// %addr1 = gep, %alloca2, 0, %l 175 /// %addr2 = gep %alloca2, 0, (%l + 1) 176 /// alias(%p, %addr1) -> MayAlias ! 177 /// store %l, ... 178 SmallPtrSet<const BasicBlock *, 8> VisitedPhiBBs; 179 180 /// Tracks instructions visited by pointsToConstantMemory. 181 SmallPtrSet<const Value *, 16> Visited; 182 183 static DecomposedGEP 184 DecomposeGEPExpression(const Value *V, const DataLayout &DL, 185 AssumptionCache *AC, DominatorTree *DT); 186 187 static bool isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp, 188 const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject, 189 LocationSize ObjectAccessSize); 190 191 /// A Heuristic for aliasGEP that searches for a constant offset 192 /// between the variables. 193 /// 194 /// GetLinearExpression has some limitations, as generally zext(%x + 1) 195 /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression 196 /// will therefore conservatively refuse to decompose these expressions. 197 /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if 198 /// the addition overflows. 199 bool 200 constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices, 201 LocationSize V1Size, LocationSize V2Size, 202 const APInt &BaseOffset, AssumptionCache *AC, 203 DominatorTree *DT); 204 205 bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2); 206 207 void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest, 208 const SmallVectorImpl<VariableGEPIndex> &Src); 209 210 AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size, 211 const Value *V2, LocationSize V2Size, 212 const Value *UnderlyingV1, const Value *UnderlyingV2, 213 AAQueryInfo &AAQI); 214 215 AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize, 216 const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI); 217 218 AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize, 219 const Value *V2, LocationSize V2Size, 220 AAQueryInfo &AAQI); 221 222 AliasResult aliasCheck(const Value *V1, LocationSize V1Size, 223 const Value *V2, LocationSize V2Size, 224 AAQueryInfo &AAQI); 225 226 AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size, 227 const Value *V2, LocationSize V2Size, 228 AAQueryInfo &AAQI, const Value *O1, 229 const Value *O2); 230 }; 231 232 /// Analysis pass providing a never-invalidated alias analysis result. 233 class BasicAA : public AnalysisInfoMixin<BasicAA> { 234 friend AnalysisInfoMixin<BasicAA>; 235 236 static AnalysisKey Key; 237 238 public: 239 using Result = BasicAAResult; 240 241 BasicAAResult run(Function &F, FunctionAnalysisManager &AM); 242 }; 243 244 /// Legacy wrapper pass to provide the BasicAAResult object. 245 class BasicAAWrapperPass : public FunctionPass { 246 std::unique_ptr<BasicAAResult> Result; 247 248 virtual void anchor(); 249 250 public: 251 static char ID; 252 253 BasicAAWrapperPass(); 254 getResult()255 BasicAAResult &getResult() { return *Result; } getResult()256 const BasicAAResult &getResult() const { return *Result; } 257 258 bool runOnFunction(Function &F) override; 259 void getAnalysisUsage(AnalysisUsage &AU) const override; 260 }; 261 262 FunctionPass *createBasicAAWrapperPass(); 263 264 /// A helper for the legacy pass manager to create a \c BasicAAResult object 265 /// populated to the best of our ability for a particular function when inside 266 /// of a \c ModulePass or a \c CallGraphSCCPass. 267 BasicAAResult createLegacyPMBasicAAResult(Pass &P, Function &F); 268 269 /// This class is a functor to be used in legacy module or SCC passes for 270 /// computing AA results for a function. We store the results in fields so that 271 /// they live long enough to be queried, but we re-use them each time. 272 class LegacyAARGetter { 273 Pass &P; 274 Optional<BasicAAResult> BAR; 275 Optional<AAResults> AAR; 276 277 public: LegacyAARGetter(Pass & P)278 LegacyAARGetter(Pass &P) : P(P) {} operator()279 AAResults &operator()(Function &F) { 280 BAR.emplace(createLegacyPMBasicAAResult(P, F)); 281 AAR.emplace(createLegacyPMAAResults(P, F, *BAR)); 282 return *AAR; 283 } 284 }; 285 286 } // end namespace llvm 287 288 #endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H 289