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