LCOV - code coverage report
Current view: top level - include/llvm/Analysis - BasicAliasAnalysis.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 16 16 100.0 %
Date: 2017-09-14 15:23:50 Functions: 5 6 83.3 %
Legend: Lines: hit not hit

          Line data    Source code
       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/DenseMap.h"
      18             : #include "llvm/ADT/Optional.h"
      19             : #include "llvm/ADT/SmallPtrSet.h"
      20             : #include "llvm/ADT/SmallVector.h"
      21             : #include "llvm/Analysis/AliasAnalysis.h"
      22             : #include "llvm/Analysis/AssumptionCache.h"
      23             : #include "llvm/Analysis/MemoryLocation.h"
      24             : #include "llvm/IR/CallSite.h"
      25             : #include "llvm/IR/PassManager.h"
      26             : #include "llvm/Pass.h"
      27             : #include <algorithm>
      28             : #include <cstdint>
      29             : #include <memory>
      30             : #include <utility>
      31             : 
      32             : namespace llvm {
      33             : 
      34             : struct AAMDNodes;
      35             : class APInt;
      36             : class AssumptionCache;
      37             : class BasicBlock;
      38             : class DataLayout;
      39             : class DominatorTree;
      40             : class Function;
      41             : class GEPOperator;
      42             : class LoopInfo;
      43             : class PHINode;
      44             : class SelectInst;
      45             : class TargetLibraryInfo;
      46             : class Value;
      47             : 
      48             : /// This is the AA result object for the basic, local, and stateless alias
      49             : /// analysis. It implements the AA query interface in an entirely stateless
      50             : /// manner. As one consequence, it is never invalidated due to IR changes.
      51             : /// While it does retain some storage, that is used as an optimization and not
      52             : /// to preserve information from query to query. However it does retain handles
      53             : /// to various other analyses and must be recomputed when those analyses are.
      54     4144984 : class BasicAAResult : public AAResultBase<BasicAAResult> {
      55             :   friend AAResultBase<BasicAAResult>;
      56             : 
      57             :   const DataLayout &DL;
      58             :   const TargetLibraryInfo &TLI;
      59             :   AssumptionCache &AC;
      60             :   DominatorTree *DT;
      61             :   LoopInfo *LI;
      62             : 
      63             : public:
      64             :   BasicAAResult(const DataLayout &DL, const TargetLibraryInfo &TLI,
      65             :                 AssumptionCache &AC, DominatorTree *DT = nullptr,
      66             :                 LoopInfo *LI = nullptr)
      67     3625976 :       : AAResultBase(), DL(DL), TLI(TLI), AC(AC), DT(DT), LI(LI) {}
      68             : 
      69             :   BasicAAResult(const BasicAAResult &Arg)
      70             :       : AAResultBase(Arg), DL(Arg.DL), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT),
      71             :         LI(Arg.LI) {}
      72      130005 :   BasicAAResult(BasicAAResult &&Arg)
      73      650025 :       : AAResultBase(std::move(Arg)), DL(Arg.DL), TLI(Arg.TLI), AC(Arg.AC),
      74     1170045 :         DT(Arg.DT), LI(Arg.LI) {}
      75             : 
      76             :   /// Handle invalidation events in the new pass manager.
      77             :   bool invalidate(Function &F, const PreservedAnalyses &PA,
      78             :                   FunctionAnalysisManager::Invalidator &Inv);
      79             : 
      80             :   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
      81             : 
      82             :   ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);
      83             : 
      84             :   ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2);
      85             : 
      86             :   /// Chases pointers until we find a (constant global) or not.
      87             :   bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal);
      88             : 
      89             :   /// Get the location associated with a pointer argument of a callsite.
      90             :   ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
      91             : 
      92             :   /// Returns the behavior when calling the given call site.
      93             :   FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
      94             : 
      95             :   /// Returns the behavior when calling the given function. For use when the
      96             :   /// call site is not known.
      97             :   FunctionModRefBehavior getModRefBehavior(const Function *F);
      98             : 
      99             : private:
     100             :   // A linear transformation of a Value; this class represents ZExt(SExt(V,
     101             :   // SExtBits), ZExtBits) * Scale + Offset.
     102             :   struct VariableGEPIndex {
     103             :     // An opaque Value - we can't decompose this further.
     104             :     const Value *V;
     105             : 
     106             :     // We need to track what extensions we've done as we consider the same Value
     107             :     // with different extensions as different variables in a GEP's linear
     108             :     // expression;
     109             :     // e.g.: if V == -1, then sext(x) != zext(x).
     110             :     unsigned ZExtBits;
     111             :     unsigned SExtBits;
     112             : 
     113             :     int64_t Scale;
     114             : 
     115             :     bool operator==(const VariableGEPIndex &Other) const {
     116         118 :       return V == Other.V && ZExtBits == Other.ZExtBits &&
     117         118 :              SExtBits == Other.SExtBits && Scale == Other.Scale;
     118             :     }
     119             : 
     120             :     bool operator!=(const VariableGEPIndex &Other) const {
     121             :       return !operator==(Other);
     122             :     }
     123             :   };
     124             : 
     125             :   // Represents the internal structure of a GEP, decomposed into a base pointer,
     126             :   // constant offsets, and variable scaled indices.
     127    22680088 :   struct DecomposedGEP {
     128             :     // Base pointer of the GEP
     129             :     const Value *Base;
     130             :     // Total constant offset w.r.t the base from indexing into structs
     131             :     int64_t StructOffset;
     132             :     // Total constant offset w.r.t the base from indexing through
     133             :     // pointers/arrays/vectors
     134             :     int64_t OtherOffset;
     135             :     // Scaled variable (non-constant) indices.
     136             :     SmallVector<VariableGEPIndex, 4> VarIndices;
     137             :   };
     138             : 
     139             :   /// Track alias queries to guard against recursion.
     140             :   using LocPair = std::pair<MemoryLocation, MemoryLocation>;
     141             :   using AliasCacheTy = SmallDenseMap<LocPair, AliasResult, 8>;
     142             :   AliasCacheTy AliasCache;
     143             : 
     144             :   /// Tracks phi nodes we have visited.
     145             :   ///
     146             :   /// When interpret "Value" pointer equality as value equality we need to make
     147             :   /// sure that the "Value" is not part of a cycle. Otherwise, two uses could
     148             :   /// come from different "iterations" of a cycle and see different values for
     149             :   /// the same "Value" pointer.
     150             :   ///
     151             :   /// The following example shows the problem:
     152             :   ///   %p = phi(%alloca1, %addr2)
     153             :   ///   %l = load %ptr
     154             :   ///   %addr1 = gep, %alloca2, 0, %l
     155             :   ///   %addr2 = gep  %alloca2, 0, (%l + 1)
     156             :   ///      alias(%p, %addr1) -> MayAlias !
     157             :   ///   store %l, ...
     158             :   SmallPtrSet<const BasicBlock *, 8> VisitedPhiBBs;
     159             : 
     160             :   /// Tracks instructions visited by pointsToConstantMemory.
     161             :   SmallPtrSet<const Value *, 16> Visited;
     162             : 
     163             :   static const Value *
     164             :   GetLinearExpression(const Value *V, APInt &Scale, APInt &Offset,
     165             :                       unsigned &ZExtBits, unsigned &SExtBits,
     166             :                       const DataLayout &DL, unsigned Depth, AssumptionCache *AC,
     167             :                       DominatorTree *DT, bool &NSW, bool &NUW);
     168             : 
     169             :   static bool DecomposeGEPExpression(const Value *V, DecomposedGEP &Decomposed,
     170             :       const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT);
     171             : 
     172             :   static bool isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
     173             :       const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
     174             :       uint64_t ObjectAccessSize);
     175             : 
     176             :   /// \brief A Heuristic for aliasGEP that searches for a constant offset
     177             :   /// between the variables.
     178             :   ///
     179             :   /// GetLinearExpression has some limitations, as generally zext(%x + 1)
     180             :   /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
     181             :   /// will therefore conservatively refuse to decompose these expressions.
     182             :   /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
     183             :   /// the addition overflows.
     184             :   bool
     185             :   constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices,
     186             :                           uint64_t V1Size, uint64_t V2Size, int64_t BaseOffset,
     187             :                           AssumptionCache *AC, DominatorTree *DT);
     188             : 
     189             :   bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
     190             : 
     191             :   void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
     192             :                           const SmallVectorImpl<VariableGEPIndex> &Src);
     193             : 
     194             :   AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size,
     195             :                        const AAMDNodes &V1AAInfo, const Value *V2,
     196             :                        uint64_t V2Size, const AAMDNodes &V2AAInfo,
     197             :                        const Value *UnderlyingV1, const Value *UnderlyingV2);
     198             : 
     199             :   AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize,
     200             :                        const AAMDNodes &PNAAInfo, const Value *V2,
     201             :                        uint64_t V2Size, const AAMDNodes &V2AAInfo,
     202             :                        const Value *UnderV2);
     203             : 
     204             :   AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize,
     205             :                           const AAMDNodes &SIAAInfo, const Value *V2,
     206             :                           uint64_t V2Size, const AAMDNodes &V2AAInfo,
     207             :                           const Value *UnderV2);
     208             : 
     209             :   AliasResult aliasCheck(const Value *V1, uint64_t V1Size, AAMDNodes V1AATag,
     210             :                          const Value *V2, uint64_t V2Size, AAMDNodes V2AATag,
     211             :                          const Value *O1 = nullptr, const Value *O2 = nullptr);
     212             : };
     213             : 
     214             : /// Analysis pass providing a never-invalidated alias analysis result.
     215             : class BasicAA : public AnalysisInfoMixin<BasicAA> {
     216             :   friend AnalysisInfoMixin<BasicAA>;
     217             : 
     218             :   static AnalysisKey Key;
     219             : 
     220             : public:
     221             :   using Result = BasicAAResult;
     222             : 
     223             :   BasicAAResult run(Function &F, FunctionAnalysisManager &AM);
     224             : };
     225             : 
     226             : /// Legacy wrapper pass to provide the BasicAAResult object.
     227      118396 : class BasicAAWrapperPass : public FunctionPass {
     228             :   std::unique_ptr<BasicAAResult> Result;
     229             : 
     230             :   virtual void anchor();
     231             : 
     232             : public:
     233             :   static char ID;
     234             : 
     235             :   BasicAAWrapperPass();
     236             : 
     237     1467004 :   BasicAAResult &getResult() { return *Result; }
     238             :   const BasicAAResult &getResult() const { return *Result; }
     239             : 
     240             :   bool runOnFunction(Function &F) override;
     241             :   void getAnalysisUsage(AnalysisUsage &AU) const override;
     242             : };
     243             : 
     244             : FunctionPass *createBasicAAWrapperPass();
     245             : 
     246             : /// A helper for the legacy pass manager to create a \c BasicAAResult object
     247             : /// populated to the best of our ability for a particular function when inside
     248             : /// of a \c ModulePass or a \c CallGraphSCCPass.
     249             : BasicAAResult createLegacyPMBasicAAResult(Pass &P, Function &F);
     250             : 
     251             : /// This class is a functor to be used in legacy module or SCC passes for
     252             : /// computing AA results for a function. We store the results in fields so that
     253             : /// they live long enough to be queried, but we re-use them each time.
     254      621312 : class LegacyAARGetter {
     255             :   Pass &P;
     256             :   Optional<BasicAAResult> BAR;
     257             :   Optional<AAResults> AAR;
     258             : 
     259             : public:
     260      621312 :   LegacyAARGetter(Pass &P) : P(P) {}
     261      128681 :   AAResults &operator()(Function &F) {
     262      128681 :     BAR.emplace(createLegacyPMBasicAAResult(P, F));
     263      257362 :     AAR.emplace(createLegacyPMAAResults(P, F, *BAR));
     264      257362 :     return *AAR;
     265             :   }
     266             : };
     267             : 
     268             : } // end namespace llvm
     269             : 
     270             : #endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H

Generated by: LCOV version 1.13