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   /// BasicAliasAnalysis - 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,
  73                                      LocB.Ptr, 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     /// pointsToConstantMemory - Chase pointers until we find a (constant
  90     /// global) or not.
  91     bool pointsToConstantMemory(const MemoryLocation &Loc,
  92                                 bool OrLocal) override;
  93
  94     /// Get the location associated with a pointer argument of a callsite.
  95     ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) override;
  96
  97     /// getModRefBehavior - Return the behavior when calling the given
  98     /// call site.
  99     FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) override;
 100
 101     /// getModRefBehavior - Return the behavior when calling the given function.
 102     /// For use when the call site is not known.
 103     FunctionModRefBehavior getModRefBehavior(const Function *F) override;
 104
 105     /// getAdjustedAnalysisPointer - This method is used when a pass implements
 106     /// an analysis interface through multiple inheritance.  If needed, it
 107     /// should override this to adjust the this pointer as needed for the
 108     /// specified pass info.
 109     void *getAdjustedAnalysisPointer(const void *ID) override {
 110       if (ID == &AliasAnalysis::ID)
 111         return (AliasAnalysis*)this;
 112       return this;
 113     }
 114
 115   private:
 116     enum ExtensionKind {
 117       EK_NotExtended,
 118       EK_SignExt,
 119       EK_ZeroExt
 120     };
 121
 122     struct VariableGEPIndex {
 123       const Value *V;
 124       ExtensionKind Extension;
 125       int64_t Scale;
 126
 127       bool operator==(const VariableGEPIndex &Other) const {
 128         return V == Other.V && Extension == Other.Extension &&
 129           Scale == Other.Scale;
 130       }
 131
 132       bool operator!=(const VariableGEPIndex &Other) const {
 133         return !operator==(Other);
 134       }
 135     };
 136
 137     // AliasCache - Track alias queries to guard against recursion.
 138     typedef std::pair<MemoryLocation, MemoryLocation> LocPair;
 139     typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy;
 140     AliasCacheTy AliasCache;
 141
 142     /// \brief Track phi nodes we have visited. When interpret "Value" pointer
 143     /// equality as value equality we need to make sure that the "Value" is not
 144     /// part of a cycle. Otherwise, two uses could come from different
 145     /// "iterations" of a cycle and see different values for the same "Value"
 146     /// pointer.
 147     /// The following example shows the problem:
 148     ///   %p = phi(%alloca1, %addr2)
 149     ///   %l = load %ptr
 150     ///   %addr1 = gep, %alloca2, 0, %l
 151     ///   %addr2 = gep  %alloca2, 0, (%l + 1)
 152     ///      alias(%p, %addr1) -> MayAlias !
 153     ///   store %l, ...
 154     SmallPtrSet<const BasicBlock*, 8> VisitedPhiBBs;
 155
 156     // Visited - Track instructions visited by pointsToConstantMemory.
 157     SmallPtrSet<const Value*, 16> Visited;
 158
 159     static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
 160                                       ExtensionKind &Extension,
 161                                       const DataLayout &DL, unsigned Depth,
 162                                       AssumptionCache *AC, DominatorTree *DT);
 163
 164     static const Value *
 165     DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
 166                            SmallVectorImpl<VariableGEPIndex> &VarIndices,
 167                            bool &MaxLookupReached, const DataLayout &DL,
 168                            AssumptionCache *AC, DominatorTree *DT);
 169
 170     /// \brief Check whether two Values can be considered equivalent.
 171     ///
 172     /// In addition to pointer equivalence of \p V1 and \p V2 this checks
 173     /// whether they can not be part of a cycle in the value graph by looking at
 174     /// all visited phi nodes an making sure that the phis cannot reach the
 175     /// value. We have to do this because we are looking through phi nodes (That
 176     /// is we say noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB).
 177     bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
 178
 179     /// \brief Dest and Src are the variable indices from two decomposed
 180     /// GetElementPtr instructions GEP1 and GEP2 which have common base
 181     /// pointers.  Subtract the GEP2 indices from GEP1 to find the symbolic
 182     /// difference between the two pointers.
 183     void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
 184                             const SmallVectorImpl<VariableGEPIndex> &Src);
 185
 186     // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP
 187     // instruction against another.
 188     AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size,
 189                          const AAMDNodes &V1AAInfo,
 190                          const Value *V2, uint64_t V2Size,
 191                          const AAMDNodes &V2AAInfo,
 192                          const Value *UnderlyingV1, const Value *UnderlyingV2);
 193
 194     // aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI
 195     // instruction against another.
 196     AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize,
 197                          const AAMDNodes &PNAAInfo,
 198                          const Value *V2, uint64_t V2Size,
 199                          const AAMDNodes &V2AAInfo);
 200
 201     /// aliasSelect - Disambiguate a Select instruction against another value.
 202     AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize,
 203                             const AAMDNodes &SIAAInfo,
 204                             const Value *V2, uint64_t V2Size,
 205                             const AAMDNodes &V2AAInfo);
 206
 207     AliasResult aliasCheck(const Value *V1, uint64_t V1Size,
 208                            AAMDNodes V1AATag,
 209                            const Value *V2, uint64_t V2Size,
 210                            AAMDNodes V2AATag);
 211   };
 212
 213
 214   //===--------------------------------------------------------------------===//
 215   //
 216   // createBasicAliasAnalysisPass - This pass implements the stateless alias
 217   // analysis.
 218   //
 219   ImmutablePass *createBasicAliasAnalysisPass();
 220
 221 }
 222
 223 #endif