LCOV - code coverage report
Current view: top level - include/llvm/Analysis - BasicAliasAnalysis.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 15 15 100.0 %
Date: 2018-06-17 00:07:59 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     2363984 : 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     1042706 :       : 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      139546 :   BasicAAResult(BasicAAResult &&Arg)
      73      558184 :       : AAResultBase(std::move(Arg)), DL(Arg.DL), TLI(Arg.TLI), AC(Arg.AC),
      74      558184 :         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         592 :       return V == Other.V && ZExtBits == Other.ZExtBits &&
     117         592 :              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     3086203 :   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             :       LocationSize ObjectAccessSize);
     175             : 
     176             :   /// 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             :                           LocationSize V1Size, LocationSize V2Size,
     187             :                           int64_t BaseOffset, AssumptionCache *AC,
     188             :                           DominatorTree *DT);
     189             : 
     190             :   bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
     191             : 
     192             :   void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
     193             :                           const SmallVectorImpl<VariableGEPIndex> &Src);
     194             : 
     195             :   AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
     196             :                        const AAMDNodes &V1AAInfo, const Value *V2,
     197             :                        LocationSize V2Size, const AAMDNodes &V2AAInfo,
     198             :                        const Value *UnderlyingV1, const Value *UnderlyingV2);
     199             : 
     200             :   AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,
     201             :                        const AAMDNodes &PNAAInfo, const Value *V2,
     202             :                        LocationSize V2Size, const AAMDNodes &V2AAInfo,
     203             :                        const Value *UnderV2);
     204             : 
     205             :   AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,
     206             :                           const AAMDNodes &SIAAInfo, const Value *V2,
     207             :                           LocationSize V2Size, const AAMDNodes &V2AAInfo,
     208             :                           const Value *UnderV2);
     209             : 
     210             :   AliasResult aliasCheck(const Value *V1, LocationSize V1Size,
     211             :                          AAMDNodes V1AATag, const Value *V2,
     212             :                          LocationSize V2Size, AAMDNodes V2AATag,
     213             :                          const Value *O1 = nullptr, const Value *O2 = nullptr);
     214             : };
     215             : 
     216             : /// Analysis pass providing a never-invalidated alias analysis result.
     217             : class BasicAA : public AnalysisInfoMixin<BasicAA> {
     218             :   friend AnalysisInfoMixin<BasicAA>;
     219             : 
     220             :   static AnalysisKey Key;
     221             : 
     222             : public:
     223             :   using Result = BasicAAResult;
     224             : 
     225             :   BasicAAResult run(Function &F, FunctionAnalysisManager &AM);
     226             : };
     227             : 
     228             : /// Legacy wrapper pass to provide the BasicAAResult object.
     229      144856 : class BasicAAWrapperPass : public FunctionPass {
     230             :   std::unique_ptr<BasicAAResult> Result;
     231             : 
     232             :   virtual void anchor();
     233             : 
     234             : public:
     235             :   static char ID;
     236             : 
     237             :   BasicAAWrapperPass();
     238             : 
     239             :   BasicAAResult &getResult() { return *Result; }
     240             :   const BasicAAResult &getResult() const { return *Result; }
     241             : 
     242             :   bool runOnFunction(Function &F) override;
     243             :   void getAnalysisUsage(AnalysisUsage &AU) const override;
     244             : };
     245             : 
     246             : FunctionPass *createBasicAAWrapperPass();
     247             : 
     248             : /// A helper for the legacy pass manager to create a \c BasicAAResult object
     249             : /// populated to the best of our ability for a particular function when inside
     250             : /// of a \c ModulePass or a \c CallGraphSCCPass.
     251             : BasicAAResult createLegacyPMBasicAAResult(Pass &P, Function &F);
     252             : 
     253             : /// This class is a functor to be used in legacy module or SCC passes for
     254             : /// computing AA results for a function. We store the results in fields so that
     255             : /// they live long enough to be queried, but we re-use them each time.
     256      647586 : class LegacyAARGetter {
     257             :   Pass &P;
     258             :   Optional<BasicAAResult> BAR;
     259             :   Optional<AAResults> AAR;
     260             : 
     261             : public:
     262      323793 :   LegacyAARGetter(Pass &P) : P(P) {}
     263      138011 :   AAResults &operator()(Function &F) {
     264      138011 :     BAR.emplace(createLegacyPMBasicAAResult(P, F));
     265      276024 :     AAR.emplace(createLegacyPMAAResults(P, F, *BAR));
     266      138012 :     return *AAR;
     267             :   }
     268             : };
     269             : 
     270             : } // end namespace llvm
     271             : 
     272             : #endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H

Generated by: LCOV version 1.13