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/Pass.h"
  27 #include "llvm/Support/ErrorHandling.h"
  28
  29 namespace llvm {
  30
  31 /// This is the primary alias analysis implementation.
  32 struct BasicAliasAnalysis : public ImmutablePass, public AliasAnalysis {
  33   static char ID; // Class identification, replacement for typeinfo
  34
  35 #ifndef NDEBUG
  36   static const Function *getParent(const Value *V) {
  37     if (const Instruction *inst = dyn_cast<Instruction>(V))
  38       return inst->getParent()->getParent();
  39
  40     if (const Argument *arg = dyn_cast<Argument>(V))
  41       return arg->getParent();
  42
  43     return nullptr;
  44   }
  45
  46   static bool notDifferentParent(const Value *O1, const Value *O2) {
  47
  48     const Function *F1 = getParent(O1);
  49     const Function *F2 = getParent(O2);
  50
  51     return !F1 || !F2 || F1 == F2;
  52   }
  53 #endif
  54
  55   BasicAliasAnalysis() : ImmutablePass(ID) {
  56     initializeBasicAliasAnalysisPass(*PassRegistry::getPassRegistry());
  57   }
  58
  59   bool doInitialization(Module &M) override;
  60
  61   void getAnalysisUsage(AnalysisUsage &AU) const override {
  62     AU.addRequired<AliasAnalysis>();
  63     AU.addRequired<AssumptionCacheTracker>();
  64     AU.addRequired<TargetLibraryInfoWrapperPass>();
  65   }
  66
  67   AliasResult alias(const MemoryLocation &LocA,
  68                     const MemoryLocation &LocB) override {
  69     assert(AliasCache.empty() && "AliasCache must be cleared after use!");
  70     assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
  71            "BasicAliasAnalysis doesn't support interprocedural queries.");
  72     AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr,
  73                                    LocB.Size, LocB.AATags);
  74     // AliasCache rarely has more than 1 or 2 elements, always use
  75     // shrink_and_clear so it quickly returns to the inline capacity of the
  76     // SmallDenseMap if it ever grows larger.
  77     // FIXME: This should really be shrink_to_inline_capacity_and_clear().
  78     AliasCache.shrink_and_clear();
  79     VisitedPhiBBs.clear();
  80     return Alias;
  81   }
  82
  83   ModRefInfo getModRefInfo(ImmutableCallSite CS,
  84                            const MemoryLocation &Loc) override;
  85
  86   ModRefInfo getModRefInfo(ImmutableCallSite CS1,
  87                            ImmutableCallSite CS2) override;
  88
  89   /// Chases pointers until we find a (constant global) or not.
  90   bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal) override;
  91
  92   /// Get the location associated with a pointer argument of a callsite.
  93   ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) override;
  94
  95   /// Returns the behavior when calling the given call site.
  96   FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) override;
  97
  98   /// Returns the behavior when calling the given function. For use when the
  99   /// call site is not known.
 100   FunctionModRefBehavior getModRefBehavior(const Function *F) override;
 101
 102   /// This method is used when a pass implements an analysis interface through
 103   /// multiple inheritance.  If needed, it should override this to adjust the
 104   /// this pointer as needed for the specified pass info.
 105   void *getAdjustedAnalysisPointer(const void *ID) override {
 106     if (ID == &AliasAnalysis::ID)
 107       return (AliasAnalysis *)this;
 108     return this;
 109   }
 110
 111 private:
 112   // A linear transformation of a Value; this class represents ZExt(SExt(V,
 113   // SExtBits), ZExtBits) * Scale + Offset.
 114   struct VariableGEPIndex {
 115
 116     // An opaque Value - we can't decompose this further.
 117     const Value *V;
 118
 119     // We need to track what extensions we've done as we consider the same Value
 120     // with different extensions as different variables in a GEP's linear
 121     // expression;
 122     // e.g.: if V == -1, then sext(x) != zext(x).
 123     unsigned ZExtBits;
 124     unsigned SExtBits;
 125
 126     int64_t Scale;
 127
 128     bool operator==(const VariableGEPIndex &Other) const {
 129       return V == Other.V && ZExtBits == Other.ZExtBits &&
 130              SExtBits == Other.SExtBits && Scale == Other.Scale;
 131     }
 132
 133     bool operator!=(const VariableGEPIndex &Other) const {
 134       return !operator==(Other);
 135     }
 136   };
 137
 138   /// Track alias queries to guard against recursion.
 139   typedef std::pair<MemoryLocation, MemoryLocation> LocPair;
 140   typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy;
 141   AliasCacheTy AliasCache;
 142
 143   /// Tracks phi nodes we have visited.
 144   ///
 145   /// When interpret "Value" pointer equality as value equality we need to make
 146   /// sure that the "Value" is not part of a cycle. Otherwise, two uses could
 147   /// come from different "iterations" of a cycle and see different values for
 148   /// the same "Value" pointer.
 149   ///
 150   /// The following example shows the problem:
 151   ///   %p = phi(%alloca1, %addr2)
 152   ///   %l = load %ptr
 153   ///   %addr1 = gep, %alloca2, 0, %l
 154   ///   %addr2 = gep  %alloca2, 0, (%l + 1)
 155   ///      alias(%p, %addr1) -> MayAlias !
 156   ///   store %l, ...
 157   SmallPtrSet<const BasicBlock *, 8> VisitedPhiBBs;
 158
 159   /// Tracks instructions visited by pointsToConstantMemory.
 160   SmallPtrSet<const Value *, 16> Visited;
 161
 162   static const Value *
 163   GetLinearExpression(const Value *V, APInt &Scale, APInt &Offset,
 164                       unsigned &ZExtBits, unsigned &SExtBits,
 165                       const DataLayout &DL, unsigned Depth, AssumptionCache *AC,
 166                       DominatorTree *DT, bool &NSW, bool &NUW);
 167
 168   static const Value *
 169   DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
 170                          SmallVectorImpl<VariableGEPIndex> &VarIndices,
 171                          bool &MaxLookupReached, const DataLayout &DL,
 172                          AssumptionCache *AC, DominatorTree *DT);
 173   /// \brief A Heuristic for aliasGEP that searches for a constant offset
 174   /// between the variables.
 175   ///
 176   /// GetLinearExpression has some limitations, as generally zext(%x + 1)
 177   /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
 178   /// will therefore conservatively refuse to decompose these expressions.
 179   /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
 180   /// the addition overflows.
 181   bool
 182   constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices,
 183                           uint64_t V1Size, uint64_t V2Size, int64_t BaseOffset,
 184                           const DataLayout *DL, AssumptionCache *AC,
 185                           DominatorTree *DT);
 186
 187   bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
 188
 189   void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
 190                           const SmallVectorImpl<VariableGEPIndex> &Src);
 191
 192   AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size,
 193                        const AAMDNodes &V1AAInfo, const Value *V2,
 194                        uint64_t V2Size, const AAMDNodes &V2AAInfo,
 195                        const Value *UnderlyingV1, const Value *UnderlyingV2);
 196
 197   AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize,
 198                        const AAMDNodes &PNAAInfo, const Value *V2,
 199                        uint64_t V2Size, const AAMDNodes &V2AAInfo);
 200
 201   AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize,
 202                           const AAMDNodes &SIAAInfo, const Value *V2,
 203                           uint64_t V2Size, const AAMDNodes &V2AAInfo);
 204
 205   AliasResult aliasCheck(const Value *V1, uint64_t V1Size, AAMDNodes V1AATag,
 206                          const Value *V2, uint64_t V2Size, AAMDNodes V2AATag);
 207 };
 208
 209 //===--------------------------------------------------------------------===//
 210 //
 211 // createBasicAliasAnalysisPass - This pass implements the stateless alias
 212 // analysis.
 213 //
 214 ImmutablePass *createBasicAliasAnalysisPass();
 215
 216 }
 217
 218 #endif