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   const TargetLibraryInfo &TLI;
     44   AssumptionCache &AC;
     45   DominatorTree *DT;
     46   LoopInfo *LI;
     47 
     48 public:
     49   BasicAAResult(const DataLayout &DL, const TargetLibraryInfo &TLI,
     50                 AssumptionCache &AC, DominatorTree *DT = nullptr,
     51                 LoopInfo *LI = nullptr)
     52       : AAResultBase(), DL(DL), TLI(TLI), AC(AC), DT(DT), LI(LI) {}
     53 
     54   BasicAAResult(const BasicAAResult &Arg)
     55       : AAResultBase(Arg), DL(Arg.DL), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT),
     56         LI(Arg.LI) {}
     57   BasicAAResult(BasicAAResult &&Arg)
     58       : AAResultBase(std::move(Arg)), DL(Arg.DL), TLI(Arg.TLI), AC(Arg.AC),
     59         DT(Arg.DT), LI(Arg.LI) {}
     60 
     61   /// Handle invalidation events from the new pass manager.
     62   ///
     63   /// By definition, this result is stateless and so remains valid.
     64   bool invalidate(Function &, const PreservedAnalyses &) { return false; }
     65 
     66   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
     67 
     68   ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);
     69 
     70   ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2);
     71 
     72   /// Chases pointers until we find a (constant global) or not.
     73   bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal);
     74 
     75   /// Get the location associated with a pointer argument of a callsite.
     76   ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
     77 
     78   /// Returns the behavior when calling the given call site.
     79   FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
     80 
     81   /// Returns the behavior when calling the given function. For use when the
     82   /// call site is not known.
     83   FunctionModRefBehavior getModRefBehavior(const Function *F);
     84 
     85 private:
     86   // A linear transformation of a Value; this class represents ZExt(SExt(V,
     87   // SExtBits), ZExtBits) * Scale + Offset.
     88   struct VariableGEPIndex {
     89 
     90     // An opaque Value - we can't decompose this further.
     91     const Value *V;
     92 
     93     // We need to track what extensions we've done as we consider the same Value
     94     // with different extensions as different variables in a GEP's linear
     95     // expression;
     96     // e.g.: if V == -1, then sext(x) != zext(x).
     97     unsigned ZExtBits;
     98     unsigned SExtBits;
     99 
    100     int64_t Scale;
    101 
    102     bool operator==(const VariableGEPIndex &Other) const {
    103       return V == Other.V && ZExtBits == Other.ZExtBits &&
    104              SExtBits == Other.SExtBits && Scale == Other.Scale;
    105     }
    106 
    107     bool operator!=(const VariableGEPIndex &Other) const {
    108       return !operator==(Other);
    109     }
    110   };
    111 
    112   // Represents the internal structure of a GEP, decomposed into a base pointer,
    113   // constant offsets, and variable scaled indices.
    114   struct DecomposedGEP {
    115     // Base pointer of the GEP
    116     const Value *Base;
    117     // Total constant offset w.r.t the base from indexing into structs
    118     int64_t StructOffset;
    119     // Total constant offset w.r.t the base from indexing through
    120     // pointers/arrays/vectors
    121     int64_t OtherOffset;
    122     // Scaled variable (non-constant) indices.
    123     SmallVector<VariableGEPIndex, 4> VarIndices;
    124   };
    125 
    126   /// Track alias queries to guard against recursion.
    127   typedef std::pair<MemoryLocation, MemoryLocation> LocPair;
    128   typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy;
    129   AliasCacheTy AliasCache;
    130 
    131   /// Tracks phi nodes we have visited.
    132   ///
    133   /// When interpret "Value" pointer equality as value equality we need to make
    134   /// sure that the "Value" is not part of a cycle. Otherwise, two uses could
    135   /// come from different "iterations" of a cycle and see different values for
    136   /// the same "Value" pointer.
    137   ///
    138   /// The following example shows the problem:
    139   ///   %p = phi(%alloca1, %addr2)
    140   ///   %l = load %ptr
    141   ///   %addr1 = gep, %alloca2, 0, %l
    142   ///   %addr2 = gep  %alloca2, 0, (%l + 1)
    143   ///      alias(%p, %addr1) -> MayAlias !
    144   ///   store %l, ...
    145   SmallPtrSet<const BasicBlock *, 8> VisitedPhiBBs;
    146 
    147   /// Tracks instructions visited by pointsToConstantMemory.
    148   SmallPtrSet<const Value *, 16> Visited;
    149 
    150   static const Value *
    151   GetLinearExpression(const Value *V, APInt &Scale, APInt &Offset,
    152                       unsigned &ZExtBits, unsigned &SExtBits,
    153                       const DataLayout &DL, unsigned Depth, AssumptionCache *AC,
    154                       DominatorTree *DT, bool &NSW, bool &NUW);
    155 
    156   static bool DecomposeGEPExpression(const Value *V, DecomposedGEP &Decomposed,
    157       const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT);
    158 
    159   static bool isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
    160       const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
    161       uint64_t ObjectAccessSize);
    162 
    163   /// \brief A Heuristic for aliasGEP that searches for a constant offset
    164   /// between the variables.
    165   ///
    166   /// GetLinearExpression has some limitations, as generally zext(%x + 1)
    167   /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
    168   /// will therefore conservatively refuse to decompose these expressions.
    169   /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
    170   /// the addition overflows.
    171   bool
    172   constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices,
    173                           uint64_t V1Size, uint64_t V2Size, int64_t BaseOffset,
    174                           AssumptionCache *AC, DominatorTree *DT);
    175 
    176   bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
    177 
    178   void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
    179                           const SmallVectorImpl<VariableGEPIndex> &Src);
    180 
    181   AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size,
    182                        const AAMDNodes &V1AAInfo, const Value *V2,
    183                        uint64_t V2Size, const AAMDNodes &V2AAInfo,
    184                        const Value *UnderlyingV1, const Value *UnderlyingV2);
    185 
    186   AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize,
    187                        const AAMDNodes &PNAAInfo, const Value *V2,
    188                        uint64_t V2Size, const AAMDNodes &V2AAInfo);
    189 
    190   AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize,
    191                           const AAMDNodes &SIAAInfo, const Value *V2,
    192                           uint64_t V2Size, const AAMDNodes &V2AAInfo);
    193 
    194   AliasResult aliasCheck(const Value *V1, uint64_t V1Size, AAMDNodes V1AATag,
    195                          const Value *V2, uint64_t V2Size, AAMDNodes V2AATag);
    196 };
    197 
    198 /// Analysis pass providing a never-invalidated alias analysis result.
    199 class BasicAA : public AnalysisInfoMixin<BasicAA> {
    200   friend AnalysisInfoMixin<BasicAA>;
    201   static char PassID;
    202 
    203 public:
    204   typedef BasicAAResult Result;
    205 
    206   BasicAAResult run(Function &F, AnalysisManager<Function> &AM);
    207 };
    208 
    209 /// Legacy wrapper pass to provide the BasicAAResult object.
    210 class BasicAAWrapperPass : public FunctionPass {
    211   std::unique_ptr<BasicAAResult> Result;
    212 
    213   virtual void anchor();
    214 
    215 public:
    216   static char ID;
    217 
    218   BasicAAWrapperPass();
    219 
    220   BasicAAResult &getResult() { return *Result; }
    221   const BasicAAResult &getResult() const { return *Result; }
    222 
    223   bool runOnFunction(Function &F) override;
    224   void getAnalysisUsage(AnalysisUsage &AU) const override;
    225 };
    226 
    227 FunctionPass *createBasicAAWrapperPass();
    228 
    229 /// A helper for the legacy pass manager to create a \c BasicAAResult object
    230 /// populated to the best of our ability for a particular function when inside
    231 /// of a \c ModulePass or a \c CallGraphSCCPass.
    232 BasicAAResult createLegacyPMBasicAAResult(Pass &P, Function &F);
    233 }
    234 
    235 #endif
    236