Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Transforms/Scalar/GVN.h
Line
Count
Source (jump to first uncovered line)
1
//===- GVN.h - Eliminate redundant values and loads -------------*- C++ -*-===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
/// \file
9
/// This file provides the interface for LLVM's Global Value Numbering pass
10
/// which eliminates fully redundant instructions. It also does somewhat Ad-Hoc
11
/// PRE and dead load elimination.
12
///
13
//===----------------------------------------------------------------------===//
14
15
#ifndef LLVM_TRANSFORMS_SCALAR_GVN_H
16
#define LLVM_TRANSFORMS_SCALAR_GVN_H
17
18
#include "llvm/ADT/DenseMap.h"
19
#include "llvm/ADT/MapVector.h"
20
#include "llvm/ADT/PostOrderIterator.h"
21
#include "llvm/ADT/SetVector.h"
22
#include "llvm/ADT/SmallVector.h"
23
#include "llvm/Analysis/AliasAnalysis.h"
24
#include "llvm/Analysis/InstructionPrecedenceTracking.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/IR/ValueHandle.h"
30
#include "llvm/Support/Allocator.h"
31
#include "llvm/Support/Compiler.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
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
298k
  void markInstructionForDeletion(Instruction *I) {
78
298k
    VN.erase(I);
79
298k
    InstrsToErase.push_back(I);
80
298k
  }
81
82
15.9k
  DominatorTree &getDominatorTree() const { return *DT; }
83
0
  AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
84
8.37k
  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
  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
465k
    void setAliasAnalysis(AliasAnalysis *A) { AA = A; }
144
0
    AliasAnalysis *getAliasAnalysis() const { return AA; }
145
465k
    void setMemDep(MemoryDependenceResults *M) { MD = M; }
146
465k
    void setDomTree(DominatorTree *D) { DT = D; }
147
18.1M
    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
  ImplicitControlFlowTracking *ICF;
162
163
  ValueTable VN;
164
165
  /// A mapping from value numbers to lists of Value*'s that
166
  /// have that value number.  Use findLeader to query it.
167
  struct LeaderTableEntry {
168
    Value *Val;
169
    const BasicBlock *BB;
170
    LeaderTableEntry *Next;
171
  };
172
  DenseMap<uint32_t, LeaderTableEntry> LeaderTable;
173
  BumpPtrAllocator TableAllocator;
174
175
  // Block-local map of equivalent values to their leader, does not
176
  // propagate to any successors. Entries added mid-block are applied
177
  // to the remaining instructions in the block.
178
  SmallMapVector<Value *, Constant *, 4> ReplaceWithConstMap;
179
  SmallVector<Instruction *, 8> InstrsToErase;
180
181
  // Map the block to reversed postorder traversal number. It is used to
182
  // find back edge easily.
183
  DenseMap<AssertingVH<BasicBlock>, uint32_t> BlockRPONumber;
184
185
  // This is set 'true' initially and also when new blocks have been added to
186
  // the function being analyzed. This boolean is used to control the updating
187
  // of BlockRPONumber prior to accessing the contents of BlockRPONumber.
188
  bool InvalidBlockRPONumbers = true;
189
190
  using LoadDepVect = SmallVector<NonLocalDepResult, 64>;
191
  using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;
192
  using UnavailBlkVect = SmallVector<BasicBlock *, 64>;
193
194
  bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
195
               const TargetLibraryInfo &RunTLI, AAResults &RunAA,
196
               MemoryDependenceResults *RunMD, LoopInfo *LI,
197
               OptimizationRemarkEmitter *ORE);
198
199
  /// Push a new Value to the LeaderTable onto the list for its value number.
200
22.8M
  void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
201
22.8M
    LeaderTableEntry &Curr = LeaderTable[N];
202
22.8M
    if (!Curr.Val) {
203
18.5M
      Curr.Val = V;
204
18.5M
      Curr.BB = BB;
205
18.5M
      return;
206
18.5M
    }
207
4.31M
208
4.31M
    LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
209
4.31M
    Node->Val = V;
210
4.31M
    Node->BB = BB;
211
4.31M
    Node->Next = Curr.Next;
212
4.31M
    Curr.Next = Node;
213
4.31M
  }
214
215
  /// Scan the list of values corresponding to a given
216
  /// value number, and remove the given instruction if encountered.
217
12.4k
  void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
218
12.4k
    LeaderTableEntry *Prev = nullptr;
219
12.4k
    LeaderTableEntry *Curr = &LeaderTable[N];
220
12.4k
221
58.6k
    while (Curr && 
(58.6k
Curr->Val != I58.6k
||
Curr->BB != BB12.4k
)) {
222
46.2k
      Prev = Curr;
223
46.2k
      Curr = Curr->Next;
224
46.2k
    }
225
12.4k
226
12.4k
    if (!Curr)
227
1
      return;
228
12.4k
229
12.4k
    if (Prev) {
230
8.70k
      Prev->Next = Curr->Next;
231
8.70k
    } else {
232
3.69k
      if (!Curr->Next) {
233
0
        Curr->Val = nullptr;
234
0
        Curr->BB = nullptr;
235
3.69k
      } else {
236
3.69k
        LeaderTableEntry *Next = Curr->Next;
237
3.69k
        Curr->Val = Next->Val;
238
3.69k
        Curr->BB = Next->BB;
239
3.69k
        Curr->Next = Next->Next;
240
3.69k
      }
241
3.69k
    }
242
12.4k
  }
243
244
  // List of critical edges to be split between iterations.
245
  SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit;
246
247
  // Helper functions of redundant load elimination
248
  bool processLoad(LoadInst *L);
249
  bool processNonLocalLoad(LoadInst *L);
250
  bool processAssumeIntrinsic(IntrinsicInst *II);
251
252
  /// Given a local dependency (Def or Clobber) determine if a value is
253
  /// available for the load.  Returns true if an value is known to be
254
  /// available and populates Res.  Returns false otherwise.
255
  bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
256
                               Value *Address, gvn::AvailableValue &Res);
257
258
  /// Given a list of non-local dependencies, determine if a value is
259
  /// available for the load in each specified block.  If it is, add it to
260
  /// ValuesPerBlock.  If not, add it to UnavailableBlocks.
261
  void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
262
                               AvailValInBlkVect &ValuesPerBlock,
263
                               UnavailBlkVect &UnavailableBlocks);
264
265
  bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
266
                      UnavailBlkVect &UnavailableBlocks);
267
268
  // Other helper routines
269
  bool processInstruction(Instruction *I);
270
  bool processBlock(BasicBlock *BB);
271
  void dump(DenseMap<uint32_t, Value *> &d) const;
272
  bool iterateOnFunction(Function &F);
273
  bool performPRE(Function &F);
274
  bool performScalarPRE(Instruction *I);
275
  bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
276
                                 BasicBlock *Curr, unsigned int ValNo);
277
  Value *findLeader(const BasicBlock *BB, uint32_t num);
278
  void cleanupGlobalSets();
279
  void fillImplicitControlFlowInfo(BasicBlock *BB);
280
  void verifyRemoved(const Instruction *I) const;
281
  bool splitCriticalEdges();
282
  BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
283
  bool replaceOperandsWithConsts(Instruction *I) const;
284
  bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
285
                         bool DominatesByEdge);
286
  bool processFoldableCondBr(BranchInst *BI);
287
  void addDeadBlock(BasicBlock *BB);
288
  void assignValNumForDeadCode();
289
  void assignBlockRPONumber(Function &F);
290
};
291
292
/// Create a legacy GVN pass. This also allows parameterizing whether or not
293
/// loads are eliminated by the pass.
294
FunctionPass *createGVNPass(bool NoLoads = false);
295
296
/// A simple and fast domtree-based GVN pass to hoist common expressions
297
/// from sibling branches.
298
struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
299
  /// Run the pass over the function.
300
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
301
};
302
303
/// Uses an "inverted" value numbering to decide the similarity of
304
/// expressions and sinks similar expressions into successors.
305
struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {
306
  /// Run the pass over the function.
307
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
308
};
309
310
} // end namespace llvm
311
312
#endif // LLVM_TRANSFORMS_SCALAR_GVN_H