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