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) 64 : AAResultBase(), DL(DL), F(F), TLI(TLI), AC(AC), DT(DT), PV(PV) {} 65 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) {} 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 119 /// True if all operations in this expression are NSW. 120 bool IsNSW; 121 122 void dump() const { 123 print(dbgs()); 124 dbgs() << "\n"; 125 } 126 void print(raw_ostream &OS) const { 127 OS << "(V=" << V->getName() 128 << ", zextbits=" << ZExtBits 129 << ", sextbits=" << SExtBits 130 << ", scale=" << Scale << ")"; 131 } 132 }; 133 134 // Represents the internal structure of a GEP, decomposed into a base pointer, 135 // constant offsets, and variable scaled indices. 136 struct DecomposedGEP { 137 // Base pointer of the GEP 138 const Value *Base; 139 // Total constant offset from base. 140 APInt Offset; 141 // Scaled variable (non-constant) indices. 142 SmallVector<VariableGEPIndex, 4> VarIndices; 143 // Is GEP index scale compile-time constant. 144 bool HasCompileTimeConstantScale; 145 // Are all operations inbounds GEPs or non-indexing operations? 146 // (None iff expression doesn't involve any geps) 147 Optional<bool> InBounds; 148 149 void dump() const { 150 print(dbgs()); 151 dbgs() << "\n"; 152 } 153 void print(raw_ostream &OS) const { 154 OS << "(DecomposedGEP Base=" << Base->getName() 155 << ", Offset=" << Offset 156 << ", VarIndices=["; 157 for (size_t i = 0; i < VarIndices.size(); i++) { 158 if (i != 0) 159 OS << ", "; 160 VarIndices[i].print(OS); 161 } 162 OS << "], HasCompileTimeConstantScale=" << HasCompileTimeConstantScale 163 << ")"; 164 } 165 }; 166 167 /// Tracks phi nodes we have visited. 168 /// 169 /// When interpret "Value" pointer equality as value equality we need to make 170 /// sure that the "Value" is not part of a cycle. Otherwise, two uses could 171 /// come from different "iterations" of a cycle and see different values for 172 /// the same "Value" pointer. 173 /// 174 /// The following example shows the problem: 175 /// %p = phi(%alloca1, %addr2) 176 /// %l = load %ptr 177 /// %addr1 = gep, %alloca2, 0, %l 178 /// %addr2 = gep %alloca2, 0, (%l + 1) 179 /// alias(%p, %addr1) -> MayAlias ! 180 /// store %l, ... 181 SmallPtrSet<const BasicBlock *, 8> VisitedPhiBBs; 182 183 /// Tracks instructions visited by pointsToConstantMemory. 184 SmallPtrSet<const Value *, 16> Visited; 185 186 static DecomposedGEP 187 DecomposeGEPExpression(const Value *V, const DataLayout &DL, 188 AssumptionCache *AC, DominatorTree *DT); 189 190 static bool isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp, 191 const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject, 192 LocationSize ObjectAccessSize); 193 194 /// A Heuristic for aliasGEP that searches for a constant offset 195 /// between the variables. 196 /// 197 /// GetLinearExpression has some limitations, as generally zext(%x + 1) 198 /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression 199 /// will therefore conservatively refuse to decompose these expressions. 200 /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if 201 /// the addition overflows. 202 bool 203 constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices, 204 LocationSize V1Size, LocationSize V2Size, 205 const APInt &BaseOffset, AssumptionCache *AC, 206 DominatorTree *DT); 207 208 bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2); 209 210 void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest, 211 const SmallVectorImpl<VariableGEPIndex> &Src); 212 213 AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size, 214 const Value *V2, LocationSize V2Size, 215 const Value *UnderlyingV1, const Value *UnderlyingV2, 216 AAQueryInfo &AAQI); 217 218 AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize, 219 const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI); 220 221 AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize, 222 const Value *V2, LocationSize V2Size, 223 AAQueryInfo &AAQI); 224 225 AliasResult aliasCheck(const Value *V1, LocationSize V1Size, 226 const Value *V2, LocationSize V2Size, 227 AAQueryInfo &AAQI); 228 229 AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size, 230 const Value *V2, LocationSize V2Size, 231 AAQueryInfo &AAQI, const Value *O1, 232 const Value *O2); 233 }; 234 235 /// Analysis pass providing a never-invalidated alias analysis result. 236 class BasicAA : public AnalysisInfoMixin<BasicAA> { 237 friend AnalysisInfoMixin<BasicAA>; 238 239 static AnalysisKey Key; 240 241 public: 242 using Result = BasicAAResult; 243 244 BasicAAResult run(Function &F, FunctionAnalysisManager &AM); 245 }; 246 247 /// Legacy wrapper pass to provide the BasicAAResult object. 248 class BasicAAWrapperPass : public FunctionPass { 249 std::unique_ptr<BasicAAResult> Result; 250 251 virtual void anchor(); 252 253 public: 254 static char ID; 255 256 BasicAAWrapperPass(); 257 258 BasicAAResult &getResult() { return *Result; } 259 const BasicAAResult &getResult() const { return *Result; } 260 261 bool runOnFunction(Function &F) override; 262 void getAnalysisUsage(AnalysisUsage &AU) const override; 263 }; 264 265 FunctionPass *createBasicAAWrapperPass(); 266 267 /// A helper for the legacy pass manager to create a \c BasicAAResult object 268 /// populated to the best of our ability for a particular function when inside 269 /// of a \c ModulePass or a \c CallGraphSCCPass. 270 BasicAAResult createLegacyPMBasicAAResult(Pass &P, Function &F); 271 272 /// This class is a functor to be used in legacy module or SCC passes for 273 /// computing AA results for a function. We store the results in fields so that 274 /// they live long enough to be queried, but we re-use them each time. 275 class LegacyAARGetter { 276 Pass &P; 277 Optional<BasicAAResult> BAR; 278 Optional<AAResults> AAR; 279 280 public: 281 LegacyAARGetter(Pass &P) : P(P) {} 282 AAResults &operator()(Function &F) { 283 BAR.emplace(createLegacyPMBasicAAResult(P, F)); 284 AAR.emplace(createLegacyPMAAResults(P, F, *BAR)); 285 return *AAR; 286 } 287 }; 288 289 } // end namespace llvm 290 291 #endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H 292