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

Generated by: LCOV version 1.13