Home | History | Annotate | Download | only in Scalar 
      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/IntrinsicInst.h"
     29 #include "llvm/IR/PassManager.h"
     30 
     31 namespace llvm {
     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 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     VN.erase(I);
     56     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   class ValueTable {
     69     DenseMap<Value *, uint32_t> valueNumbering;
     70     DenseMap<Expression, uint32_t> expressionNumbering;
     71     AliasAnalysis *AA;
     72     MemoryDependenceResults *MD;
     73     DominatorTree *DT;
     74 
     75     uint32_t nextValueNumber;
     76 
     77     Expression createExpr(Instruction *I);
     78     Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
     79                              Value *LHS, Value *RHS);
     80     Expression createExtractvalueExpr(ExtractValueInst *EI);
     81     uint32_t lookupOrAddCall(CallInst *C);
     82 
     83   public:
     84     ValueTable();
     85     ValueTable(const ValueTable &Arg);
     86     ValueTable(ValueTable &&Arg);
     87     ~ValueTable();
     88 
     89     uint32_t lookupOrAdd(Value *V);
     90     uint32_t lookup(Value *V) const;
     91     uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
     92                             Value *LHS, Value *RHS);
     93     bool exists(Value *V) const;
     94     void add(Value *V, uint32_t num);
     95     void clear();
     96     void erase(Value *v);
     97     void setAliasAnalysis(AliasAnalysis *A) { AA = A; }
     98     AliasAnalysis *getAliasAnalysis() const { return AA; }
     99     void setMemDep(MemoryDependenceResults *M) { MD = M; }
    100     void setDomTree(DominatorTree *D) { DT = D; }
    101     uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
    102     void verifyRemoved(const Value *) const;
    103   };
    104 
    105 private:
    106   friend class gvn::GVNLegacyPass;
    107   friend struct DenseMapInfo<Expression>;
    108 
    109   MemoryDependenceResults *MD;
    110   DominatorTree *DT;
    111   const TargetLibraryInfo *TLI;
    112   AssumptionCache *AC;
    113   SetVector<BasicBlock *> DeadBlocks;
    114   OptimizationRemarkEmitter *ORE;
    115 
    116   ValueTable VN;
    117 
    118   /// A mapping from value numbers to lists of Value*'s that
    119   /// have that value number.  Use findLeader to query it.
    120   struct LeaderTableEntry {
    121     Value *Val;
    122     const BasicBlock *BB;
    123     LeaderTableEntry *Next;
    124   };
    125   DenseMap<uint32_t, LeaderTableEntry> LeaderTable;
    126   BumpPtrAllocator TableAllocator;
    127 
    128   // Block-local map of equivalent values to their leader, does not
    129   // propagate to any successors. Entries added mid-block are applied
    130   // to the remaining instructions in the block.
    131   SmallMapVector<llvm::Value *, llvm::Constant *, 4> ReplaceWithConstMap;
    132   SmallVector<Instruction *, 8> InstrsToErase;
    133 
    134   typedef SmallVector<NonLocalDepResult, 64> LoadDepVect;
    135   typedef SmallVector<gvn::AvailableValueInBlock, 64> AvailValInBlkVect;
    136   typedef SmallVector<BasicBlock *, 64> UnavailBlkVect;
    137 
    138   bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
    139                const TargetLibraryInfo &RunTLI, AAResults &RunAA,
    140                MemoryDependenceResults *RunMD, LoopInfo *LI,
    141                OptimizationRemarkEmitter *ORE);
    142 
    143   /// Push a new Value to the LeaderTable onto the list for its value number.
    144   void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
    145     LeaderTableEntry &Curr = LeaderTable[N];
    146     if (!Curr.Val) {
    147       Curr.Val = V;
    148       Curr.BB = BB;
    149       return;
    150     }
    151 
    152     LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
    153     Node->Val = V;
    154     Node->BB = BB;
    155     Node->Next = Curr.Next;
    156     Curr.Next = Node;
    157   }
    158 
    159   /// Scan the list of values corresponding to a given
    160   /// value number, and remove the given instruction if encountered.
    161   void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
    162     LeaderTableEntry *Prev = nullptr;
    163     LeaderTableEntry *Curr = &LeaderTable[N];
    164 
    165     while (Curr && (Curr->Val != I || Curr->BB != BB)) {
    166       Prev = Curr;
    167       Curr = Curr->Next;
    168     }
    169 
    170     if (!Curr)
    171       return;
    172 
    173     if (Prev) {
    174       Prev->Next = Curr->Next;
    175     } else {
    176       if (!Curr->Next) {
    177         Curr->Val = nullptr;
    178         Curr->BB = nullptr;
    179       } else {
    180         LeaderTableEntry *Next = Curr->Next;
    181         Curr->Val = Next->Val;
    182         Curr->BB = Next->BB;
    183         Curr->Next = Next->Next;
    184       }
    185     }
    186   }
    187 
    188   // List of critical edges to be split between iterations.
    189   SmallVector<std::pair<TerminatorInst *, unsigned>, 4> toSplit;
    190 
    191   // Helper functions of redundant load elimination
    192   bool processLoad(LoadInst *L);
    193   bool processNonLocalLoad(LoadInst *L);
    194   bool processAssumeIntrinsic(IntrinsicInst *II);
    195   /// Given a local dependency (Def or Clobber) determine if a value is
    196   /// available for the load.  Returns true if an value is known to be
    197   /// available and populates Res.  Returns false otherwise.
    198   bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
    199                                Value *Address, gvn::AvailableValue &Res);
    200   /// Given a list of non-local dependencies, determine if a value is
    201   /// available for the load in each specified block.  If it is, add it to
    202   /// ValuesPerBlock.  If not, add it to UnavailableBlocks.
    203   void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
    204                                AvailValInBlkVect &ValuesPerBlock,
    205                                UnavailBlkVect &UnavailableBlocks);
    206   bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
    207                       UnavailBlkVect &UnavailableBlocks);
    208 
    209   // Other helper routines
    210   bool processInstruction(Instruction *I);
    211   bool processBlock(BasicBlock *BB);
    212   void dump(DenseMap<uint32_t, Value *> &d);
    213   bool iterateOnFunction(Function &F);
    214   bool performPRE(Function &F);
    215   bool performScalarPRE(Instruction *I);
    216   bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
    217                                  unsigned int ValNo);
    218   Value *findLeader(const BasicBlock *BB, uint32_t num);
    219   void cleanupGlobalSets();
    220   void verifyRemoved(const Instruction *I) const;
    221   bool splitCriticalEdges();
    222   BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
    223   bool replaceOperandsWithConsts(Instruction *I) const;
    224   bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
    225                          bool DominatesByEdge);
    226   bool processFoldableCondBr(BranchInst *BI);
    227   void addDeadBlock(BasicBlock *BB);
    228   void assignValNumForDeadCode();
    229 };
    230 
    231 /// Create a legacy GVN pass. This also allows parameterizing whether or not
    232 /// loads are eliminated by the pass.
    233 FunctionPass *createGVNPass(bool NoLoads = false);
    234 
    235 /// \brief A simple and fast domtree-based GVN pass to hoist common expressions
    236 /// from sibling branches.
    237 struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
    238   /// \brief Run the pass over the function.
    239   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
    240 };
    241 
    242 }
    243 
    244 #endif
    245