LCOV - code coverage report
Current view: top level - include/llvm/Transforms/Scalar - GVN.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 32 34 94.1 %
Date: 2017-09-14 15:23:50 Functions: 7 8 87.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- GVN.h - Eliminate redundant values and loads -------------*- 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 file provides the interface for LLVM's Global Value Numbering pass
      11             : /// which eliminates fully redundant instructions. It also does somewhat Ad-Hoc
      12             : /// PRE and dead load elimination.
      13             : ///
      14             : //===----------------------------------------------------------------------===//
      15             : 
      16             : #ifndef LLVM_TRANSFORMS_SCALAR_GVN_H
      17             : #define LLVM_TRANSFORMS_SCALAR_GVN_H
      18             : 
      19             : #include "llvm/ADT/DenseMap.h"
      20             : #include "llvm/ADT/MapVector.h"
      21             : #include "llvm/ADT/SetVector.h"
      22             : #include "llvm/ADT/SmallPtrSet.h"
      23             : #include "llvm/Analysis/AliasAnalysis.h"
      24             : #include "llvm/Analysis/AssumptionCache.h"
      25             : #include "llvm/Analysis/LoopInfo.h"
      26             : #include "llvm/Analysis/MemoryDependenceAnalysis.h"
      27             : #include "llvm/IR/Dominators.h"
      28             : #include "llvm/IR/PassManager.h"
      29             : 
      30             : namespace llvm {
      31             : class IntrinsicInst;
      32             : class OptimizationRemarkEmitter;
      33             : 
      34             : /// A private "module" namespace for types and utilities used by GVN. These
      35             : /// are implementation details and should not be used by clients.
      36             : namespace gvn LLVM_LIBRARY_VISIBILITY {
      37             : struct AvailableValue;
      38             : struct AvailableValueInBlock;
      39             : class GVNLegacyPass;
      40             : }
      41             : 
      42             : /// The core GVN pass object.
      43             : ///
      44             : /// FIXME: We should have a good summary of the GVN algorithm implemented by
      45             : /// this particular pass here.
      46       19549 : class GVN : public PassInfoMixin<GVN> {
      47             : public:
      48             : 
      49             :   /// \brief Run the pass over the function.
      50             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
      51             : 
      52             :   /// This removes the specified instruction from
      53             :   /// our various maps and marks it for deletion.
      54             :   void markInstructionForDeletion(Instruction *I) {
      55       12194 :     VN.erase(I);
      56       12194 :     InstrsToErase.push_back(I);
      57             :   }
      58             : 
      59             :   DominatorTree &getDominatorTree() const { return *DT; }
      60             :   AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
      61             :   MemoryDependenceResults &getMemDep() const { return *MD; }
      62             : 
      63             :   struct Expression;
      64             : 
      65             :   /// This class holds the mapping between values and value numbers.  It is used
      66             :   /// as an efficient mechanism to determine the expression-wise equivalence of
      67             :   /// two values.
      68        9734 :   class ValueTable {
      69             :     DenseMap<Value *, uint32_t> valueNumbering;
      70             :     DenseMap<Expression, uint32_t> expressionNumbering;
      71             : 
      72             :     // Expressions is the vector of Expression. ExprIdx is the mapping from
      73             :     // value number to the index of Expression in Expressions. We use it
      74             :     // instead of a DenseMap because filling such mapping is faster than
      75             :     // filling a DenseMap and the compile time is a little better.
      76             :     uint32_t nextExprNumber;
      77             :     std::vector<Expression> Expressions;
      78             :     std::vector<uint32_t> ExprIdx;
      79             :     // Value number to PHINode mapping. Used for phi-translate in scalarpre.
      80             :     DenseMap<uint32_t, PHINode *> NumberingPhi;
      81             :     // Cache for phi-translate in scalarpre.
      82             :     typedef DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>
      83             :         PhiTranslateMap;
      84             :     PhiTranslateMap PhiTranslateTable;
      85             : 
      86             :     AliasAnalysis *AA;
      87             :     MemoryDependenceResults *MD;
      88             :     DominatorTree *DT;
      89             : 
      90             :     uint32_t nextValueNumber;
      91             : 
      92             :     Expression createExpr(Instruction *I);
      93             :     Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
      94             :                              Value *LHS, Value *RHS);
      95             :     Expression createExtractvalueExpr(ExtractValueInst *EI);
      96             :     uint32_t lookupOrAddCall(CallInst *C);
      97             :     uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,
      98             :                               uint32_t Num, GVN &Gvn);
      99             :     std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
     100             :     bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVN &Gvn);
     101             : 
     102             :   public:
     103             :     ValueTable();
     104             :     ValueTable(const ValueTable &Arg);
     105             :     ValueTable(ValueTable &&Arg);
     106             :     ~ValueTable();
     107             : 
     108             :     uint32_t lookupOrAdd(Value *V);
     109             :     uint32_t lookup(Value *V, bool Verify = true) const;
     110             :     uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
     111             :                             Value *LHS, Value *RHS);
     112             :     uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,
     113             :                           uint32_t Num, GVN &Gvn);
     114             :     void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
     115             :     bool exists(Value *V) const;
     116             :     void add(Value *V, uint32_t num);
     117             :     void clear();
     118             :     void erase(Value *v);
     119       33059 :     void setAliasAnalysis(AliasAnalysis *A) { AA = A; }
     120             :     AliasAnalysis *getAliasAnalysis() const { return AA; }
     121       33059 :     void setMemDep(MemoryDependenceResults *M) { MD = M; }
     122       33059 :     void setDomTree(DominatorTree *D) { DT = D; }
     123             :     uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
     124             :     void verifyRemoved(const Value *) const;
     125             :   };
     126             : 
     127             : private:
     128             :   friend class gvn::GVNLegacyPass;
     129             :   friend struct DenseMapInfo<Expression>;
     130             : 
     131             :   MemoryDependenceResults *MD;
     132             :   DominatorTree *DT;
     133             :   const TargetLibraryInfo *TLI;
     134             :   AssumptionCache *AC;
     135             :   SetVector<BasicBlock *> DeadBlocks;
     136             :   OptimizationRemarkEmitter *ORE;
     137             : 
     138             :   ValueTable VN;
     139             : 
     140             :   /// A mapping from value numbers to lists of Value*'s that
     141             :   /// have that value number.  Use findLeader to query it.
     142             :   struct LeaderTableEntry {
     143             :     Value *Val;
     144             :     const BasicBlock *BB;
     145             :     LeaderTableEntry *Next;
     146             :   };
     147             :   DenseMap<uint32_t, LeaderTableEntry> LeaderTable;
     148             :   BumpPtrAllocator TableAllocator;
     149             : 
     150             :   // Block-local map of equivalent values to their leader, does not
     151             :   // propagate to any successors. Entries added mid-block are applied
     152             :   // to the remaining instructions in the block.
     153             :   SmallMapVector<llvm::Value *, llvm::Constant *, 4> ReplaceWithConstMap;
     154             :   SmallVector<Instruction *, 8> InstrsToErase;
     155             : 
     156             :   // Map the block to reversed postorder traversal number. It is used to
     157             :   // find back edge easily.
     158             :   DenseMap<const BasicBlock *, uint32_t> BlockRPONumber;
     159             : 
     160             :   typedef SmallVector<NonLocalDepResult, 64> LoadDepVect;
     161             :   typedef SmallVector<gvn::AvailableValueInBlock, 64> AvailValInBlkVect;
     162             :   typedef SmallVector<BasicBlock *, 64> UnavailBlkVect;
     163             : 
     164             :   bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
     165             :                const TargetLibraryInfo &RunTLI, AAResults &RunAA,
     166             :                MemoryDependenceResults *RunMD, LoopInfo *LI,
     167             :                OptimizationRemarkEmitter *ORE);
     168             : 
     169             :   /// Push a new Value to the LeaderTable onto the list for its value number.
     170     2040504 :   void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
     171     4081008 :     LeaderTableEntry &Curr = LeaderTable[N];
     172     2040504 :     if (!Curr.Val) {
     173     1920635 :       Curr.Val = V;
     174     1920635 :       Curr.BB = BB;
     175     1920635 :       return;
     176             :     }
     177             : 
     178      239738 :     LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
     179      119869 :     Node->Val = V;
     180      119869 :     Node->BB = BB;
     181      119869 :     Node->Next = Curr.Next;
     182      119869 :     Curr.Next = Node;
     183             :   }
     184             : 
     185             :   /// Scan the list of values corresponding to a given
     186             :   /// value number, and remove the given instruction if encountered.
     187        1890 :   void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
     188        1890 :     LeaderTableEntry *Prev = nullptr;
     189        3780 :     LeaderTableEntry *Curr = &LeaderTable[N];
     190             : 
     191       15932 :     while (Curr && (Curr->Val != I || Curr->BB != BB)) {
     192        7021 :       Prev = Curr;
     193        7021 :       Curr = Curr->Next;
     194             :     }
     195             : 
     196        1890 :     if (!Curr)
     197             :       return;
     198             : 
     199        1889 :     if (Prev) {
     200        1768 :       Prev->Next = Curr->Next;
     201             :     } else {
     202         121 :       if (!Curr->Next) {
     203           0 :         Curr->Val = nullptr;
     204           0 :         Curr->BB = nullptr;
     205             :       } else {
     206         121 :         LeaderTableEntry *Next = Curr->Next;
     207         121 :         Curr->Val = Next->Val;
     208         121 :         Curr->BB = Next->BB;
     209         121 :         Curr->Next = Next->Next;
     210             :       }
     211             :     }
     212             :   }
     213             : 
     214             :   // List of critical edges to be split between iterations.
     215             :   SmallVector<std::pair<TerminatorInst *, unsigned>, 4> toSplit;
     216             : 
     217             :   // Helper functions of redundant load elimination
     218             :   bool processLoad(LoadInst *L);
     219             :   bool processNonLocalLoad(LoadInst *L);
     220             :   bool processAssumeIntrinsic(IntrinsicInst *II);
     221             :   /// Given a local dependency (Def or Clobber) determine if a value is
     222             :   /// available for the load.  Returns true if an value is known to be
     223             :   /// available and populates Res.  Returns false otherwise.
     224             :   bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
     225             :                                Value *Address, gvn::AvailableValue &Res);
     226             :   /// Given a list of non-local dependencies, determine if a value is
     227             :   /// available for the load in each specified block.  If it is, add it to
     228             :   /// ValuesPerBlock.  If not, add it to UnavailableBlocks.
     229             :   void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
     230             :                                AvailValInBlkVect &ValuesPerBlock,
     231             :                                UnavailBlkVect &UnavailableBlocks);
     232             :   bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
     233             :                       UnavailBlkVect &UnavailableBlocks);
     234             : 
     235             :   // Other helper routines
     236             :   bool processInstruction(Instruction *I);
     237             :   bool processBlock(BasicBlock *BB);
     238             :   void dump(DenseMap<uint32_t, Value *> &d) const;
     239             :   bool iterateOnFunction(Function &F);
     240             :   bool performPRE(Function &F);
     241             :   bool performScalarPRE(Instruction *I);
     242             :   bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
     243             :                                  BasicBlock *Curr, unsigned int ValNo);
     244             :   Value *findLeader(const BasicBlock *BB, uint32_t num);
     245             :   void cleanupGlobalSets();
     246             :   void verifyRemoved(const Instruction *I) const;
     247             :   bool splitCriticalEdges();
     248             :   BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
     249             :   bool replaceOperandsWithConsts(Instruction *I) const;
     250             :   bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
     251             :                          bool DominatesByEdge);
     252             :   bool processFoldableCondBr(BranchInst *BI);
     253             :   void addDeadBlock(BasicBlock *BB);
     254             :   void assignValNumForDeadCode();
     255             :   void assignBlockRPONumber(Function &F);
     256             : };
     257             : 
     258             : /// Create a legacy GVN pass. This also allows parameterizing whether or not
     259             : /// loads are eliminated by the pass.
     260             : FunctionPass *createGVNPass(bool NoLoads = false);
     261             : 
     262             : /// \brief A simple and fast domtree-based GVN pass to hoist common expressions
     263             : /// from sibling branches.
     264             : struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
     265             :   /// \brief Run the pass over the function.
     266             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     267             : };
     268             : /// \brief Uses an "inverted" value numbering to decide the similarity of
     269             : /// expressions and sinks similar expressions into successors.
     270             : struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {
     271             :   /// \brief Run the pass over the function.
     272             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     273             : };
     274             : }
     275             : 
     276             : #endif

Generated by: LCOV version 1.13