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   enum ExtensionKind { EK_NotExtended, EK_SignExt, EK_ZeroExt };
 113
 114   struct VariableGEPIndex {
 115     const Value *V;
 116     ExtensionKind Extension;
 117     int64_t Scale;
 118
 119     bool operator==(const VariableGEPIndex &Other) const {
 120       return V == Other.V && Extension == Other.Extension &&
 121              Scale == Other.Scale;
 122     }
 123
 124     bool operator!=(const VariableGEPIndex &Other) const {
 125       return !operator==(Other);
 126     }
 127   };
 128
 129   /// Track alias queries to guard against recursion.
 130   typedef std::pair<MemoryLocation, MemoryLocation> LocPair;
 131   typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy;
 132   AliasCacheTy AliasCache;
 133
 134   /// Tracks phi nodes we have visited.
 135   ///
 136   /// When interpret "Value" pointer equality as value equality we need to make
 137   /// sure that the "Value" is not part of a cycle. Otherwise, two uses could
 138   /// come from different "iterations" of a cycle and see different values for
 139   /// the same "Value" pointer.
 140   ///
 141   /// The following example shows the problem:
 142   ///   %p = phi(%alloca1, %addr2)
 143   ///   %l = load %ptr
 144   ///   %addr1 = gep, %alloca2, 0, %l
 145   ///   %addr2 = gep  %alloca2, 0, (%l + 1)
 146   ///      alias(%p, %addr1) -> MayAlias !
 147   ///   store %l, ...
 148   SmallPtrSet<const BasicBlock *, 8> VisitedPhiBBs;
 149
 150   /// Tracks instructions visited by pointsToConstantMemory.
 151   SmallPtrSet<const Value *, 16> Visited;
 152
 153   static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
 154                                     ExtensionKind &Extension,
 155                                     const DataLayout &DL, unsigned Depth,
 156                                     AssumptionCache *AC, DominatorTree *DT);
 157
 158   static const Value *
 159   DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
 160                          SmallVectorImpl<VariableGEPIndex> &VarIndices,
 161                          bool &MaxLookupReached, const DataLayout &DL,
 162                          AssumptionCache *AC, DominatorTree *DT);
 163
 164   bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
 165
 166   void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
 167                           const SmallVectorImpl<VariableGEPIndex> &Src);
 168
 169   AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size,
 170                        const AAMDNodes &V1AAInfo, const Value *V2,
 171                        uint64_t V2Size, const AAMDNodes &V2AAInfo,
 172                        const Value *UnderlyingV1, const Value *UnderlyingV2);
 173
 174   AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize,
 175                        const AAMDNodes &PNAAInfo, const Value *V2,
 176                        uint64_t V2Size, const AAMDNodes &V2AAInfo);
 177
 178   AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize,
 179                           const AAMDNodes &SIAAInfo, const Value *V2,
 180                           uint64_t V2Size, const AAMDNodes &V2AAInfo);
 181
 182   AliasResult aliasCheck(const Value *V1, uint64_t V1Size, AAMDNodes V1AATag,
 183                          const Value *V2, uint64_t V2Size, AAMDNodes V2AATag);
 184 };
 185
 186 //===--------------------------------------------------------------------===//
 187 //
 188 // createBasicAliasAnalysisPass - This pass implements the stateless alias
 189 // analysis.
 190 //
 191 ImmutablePass *createBasicAliasAnalysisPass();
 192
 193 }
 194
 195 #endif