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

Generated by: LCOV version 1.13