Home | History | Annotate | Download | only in Analysis 
      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
    224