include/llvm/Analysis/BasicAliasAnalysis.h

   1 //===- BasicAliasAnalysis.h - Stateless, local Alias Analysis ---*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 /// \file
  10 /// This is the interface for LLVM's primary stateless and local alias analysis.
  11 ///
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ANALYSIS_BASICALIASANALYSIS_H
  15 #define LLVM_ANALYSIS_BASICALIASANALYSIS_H
  16
  17 #include "llvm/ADT/SmallPtrSet.h"
  18 #include "llvm/Analysis/AliasAnalysis.h"
  19 #include "llvm/Analysis/AssumptionCache.h"
  20 #include "llvm/Analysis/TargetLibraryInfo.h"
  21 #include "llvm/IR/Function.h"
  22 #include "llvm/IR/GetElementPtrTypeIterator.h"
  23 #include "llvm/IR/Instruction.h"
  24 #include "llvm/IR/LLVMContext.h"
  25 #include "llvm/IR/Module.h"
  26 #include "llvm/IR/PassManager.h"
  27 #include "llvm/Support/ErrorHandling.h"
  28
  29 namespace llvm {
  30 class AssumptionCache;
  31 class DominatorTree;
  32 class LoopInfo;
  33
  34 /// This is the AA result object for the basic, local, and stateless alias
  35 /// analysis. It implements the AA query interface in an entirely stateless
  36 /// manner. As one consequence, it is never invalidated. While it does retain
  37 /// some storage, that is used as an optimization and not to preserve
  38 /// information from query to query.
  39 class BasicAAResult : public AAResultBase<BasicAAResult> {
  40   friend AAResultBase<BasicAAResult>;
  41
  42   const DataLayout &DL;
  43   AssumptionCache &AC;
  44   DominatorTree *DT;
  45   LoopInfo *LI;
  46
  47 public:
  48   BasicAAResult(const DataLayout &DL, const TargetLibraryInfo &TLI,
  49                 AssumptionCache &AC, DominatorTree *DT = nullptr,
  50                 LoopInfo *LI = nullptr)
  51       : AAResultBase(TLI), DL(DL), AC(AC), DT(DT), LI(LI) {}
  52
  53   BasicAAResult(const BasicAAResult &Arg)
  54       : AAResultBase(Arg), DL(Arg.DL), AC(Arg.AC), DT(Arg.DT), LI(Arg.LI) {}
  55   BasicAAResult(BasicAAResult &&Arg)
  56       : AAResultBase(std::move(Arg)), DL(Arg.DL), AC(Arg.AC), DT(Arg.DT),
  57         LI(Arg.LI) {}
  58
  59   /// Handle invalidation events from the new pass manager.
  60   ///
  61   /// By definition, this result is stateless and so remains valid.
  62   bool invalidate(Function &, const PreservedAnalyses &) { return false; }
  63
  64   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
  65
  66   ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);
  67
  68   ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2);
  69
  70   /// Chases pointers until we find a (constant global) or not.
  71   bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal);
  72
  73   /// Get the location associated with a pointer argument of a callsite.
  74   ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
  75
  76   /// Returns the behavior when calling the given call site.
  77   FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
  78
  79   /// Returns the behavior when calling the given function. For use when the
  80   /// call site is not known.
  81   FunctionModRefBehavior getModRefBehavior(const Function *F);
  82
  83 private:
  84   // A linear transformation of a Value; this class represents ZExt(SExt(V,
  85   // SExtBits), ZExtBits) * Scale + Offset.
  86   struct VariableGEPIndex {
  87
  88     // An opaque Value - we can't decompose this further.
  89     const Value *V;
  90
  91     // We need to track what extensions we've done as we consider the same Value
  92     // with different extensions as different variables in a GEP's linear
  93     // expression;
  94     // e.g.: if V == -1, then sext(x) != zext(x).
  95     unsigned ZExtBits;
  96     unsigned SExtBits;
  97
  98     int64_t Scale;
  99
 100     bool operator==(const VariableGEPIndex &Other) const {
 101       return V == Other.V && ZExtBits == Other.ZExtBits &&
 102              SExtBits == Other.SExtBits && Scale == Other.Scale;
 103     }
 104
 105     bool operator!=(const VariableGEPIndex &Other) const {
 106       return !operator==(Other);
 107     }
 108   };
 109
 110   /// Track alias queries to guard against recursion.
 111   typedef std::pair<MemoryLocation, MemoryLocation> LocPair;
 112   typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy;
 113   AliasCacheTy AliasCache;
 114
 115   /// Tracks phi nodes we have visited.
 116   ///
 117   /// When interpret "Value" pointer equality as value equality we need to make
 118   /// sure that the "Value" is not part of a cycle. Otherwise, two uses could
 119   /// come from different "iterations" of a cycle and see different values for
 120   /// the same "Value" pointer.
 121   ///
 122   /// The following example shows the problem:
 123   ///   %p = phi(%alloca1, %addr2)
 124   ///   %l = load %ptr
 125   ///   %addr1 = gep, %alloca2, 0, %l
 126   ///   %addr2 = gep  %alloca2, 0, (%l + 1)
 127   ///      alias(%p, %addr1) -> MayAlias !
 128   ///   store %l, ...
 129   SmallPtrSet<const BasicBlock *, 8> VisitedPhiBBs;
 130
 131   /// Tracks instructions visited by pointsToConstantMemory.
 132   SmallPtrSet<const Value *, 16> Visited;
 133
 134   static const Value *
 135   GetLinearExpression(const Value *V, APInt &Scale, APInt &Offset,
 136                       unsigned &ZExtBits, unsigned &SExtBits,
 137                       const DataLayout &DL, unsigned Depth, AssumptionCache *AC,
 138                       DominatorTree *DT, bool &NSW, bool &NUW);
 139
 140   static const Value *
 141   DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
 142                          SmallVectorImpl<VariableGEPIndex> &VarIndices,
 143                          bool &MaxLookupReached, const DataLayout &DL,
 144                          AssumptionCache *AC, DominatorTree *DT);
 145   /// \brief A Heuristic for aliasGEP that searches for a constant offset
 146   /// between the variables.
 147   ///
 148   /// GetLinearExpression has some limitations, as generally zext(%x + 1)
 149   /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
 150   /// will therefore conservatively refuse to decompose these expressions.
 151   /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
 152   /// the addition overflows.
 153   bool
 154   constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices,
 155                           uint64_t V1Size, uint64_t V2Size, int64_t BaseOffset,
 156                           AssumptionCache *AC, DominatorTree *DT);
 157
 158   bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
 159
 160   void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
 161                           const SmallVectorImpl<VariableGEPIndex> &Src);
 162
 163   AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size,
 164                        const AAMDNodes &V1AAInfo, const Value *V2,
 165                        uint64_t V2Size, const AAMDNodes &V2AAInfo,
 166                        const Value *UnderlyingV1, const Value *UnderlyingV2);
 167
 168   AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize,
 169                        const AAMDNodes &PNAAInfo, const Value *V2,
 170                        uint64_t V2Size, const AAMDNodes &V2AAInfo);
 171
 172   AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize,
 173                           const AAMDNodes &SIAAInfo, const Value *V2,
 174                           uint64_t V2Size, const AAMDNodes &V2AAInfo);
 175
 176   AliasResult aliasCheck(const Value *V1, uint64_t V1Size, AAMDNodes V1AATag,
 177                          const Value *V2, uint64_t V2Size, AAMDNodes V2AATag);
 178 };
 179
 180 /// Analysis pass providing a never-invalidated alias analysis result.
 181 class BasicAA {
 182 public:
 183   typedef BasicAAResult Result;
 184
 185   /// \brief Opaque, unique identifier for this analysis pass.
 186   static void *ID() { return (void *)&PassID; }
 187
 188   BasicAAResult run(Function &F, AnalysisManager<Function> *AM);
 189
 190   /// \brief Provide access to a name for this pass for debugging purposes.
 191   static StringRef name() { return "BasicAliasAnalysis"; }
 192
 193 private:
 194   static char PassID;
 195 };
 196
 197 /// Legacy wrapper pass to provide the BasicAAResult object.
 198 class BasicAAWrapperPass : public FunctionPass {
 199   std::unique_ptr<BasicAAResult> Result;
 200
 201   virtual void anchor();
 202
 203 public:
 204   static char ID;
 205
 206   BasicAAWrapperPass();
 207
 208   BasicAAResult &getResult() { return *Result; }
 209   const BasicAAResult &getResult() const { return *Result; }
 210
 211   bool runOnFunction(Function &F) override;
 212   void getAnalysisUsage(AnalysisUsage &AU) const override;
 213 };
 214
 215 FunctionPass *createBasicAAWrapperPass();
 216
 217 /// A helper for the legacy pass manager to create a \c BasicAAResult object
 218 /// populated to the best of our ability for a particular function when inside
 219 /// of a \c ModulePass or a \c CallGraphSCCPass.
 220 BasicAAResult createLegacyPMBasicAAResult(Pass &P, Function &F);
 221 }
 222
 223 #endif