Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Transforms/Utils/PredicateInfo.h
Line
Count
Source (jump to first uncovered line)
1
//===- PredicateInfo.h - Build PredicateInfo ----------------------*-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
///
9
/// \file
10
///  This file implements the PredicateInfo analysis, which creates an Extended
11
/// SSA form for operations used in branch comparisons and llvm.assume
12
/// comparisons.
13
///
14
/// Copies of these operations are inserted into the true/false edge (and after
15
/// assumes), and information attached to the copies.  All uses of the original
16
/// operation in blocks dominated by the true/false edge (and assume), are
17
/// replaced with uses of the copies.  This enables passes to easily and sparsely
18
/// propagate condition based info into the operations that may be affected.
19
///
20
/// Example:
21
/// %cmp = icmp eq i32 %x, 50
22
/// br i1 %cmp, label %true, label %false
23
/// true:
24
/// ret i32 %x
25
/// false:
26
/// ret i32 1
27
///
28
/// will become
29
///
30
/// %cmp = icmp eq i32, %x, 50
31
/// br i1 %cmp, label %true, label %false
32
/// true:
33
/// %x.0 = call \@llvm.ssa_copy.i32(i32 %x)
34
/// ret i32 %x.0
35
/// false:
36
/// ret i32 1
37
///
38
/// Using getPredicateInfoFor on x.0 will give you the comparison it is
39
/// dominated by (the icmp), and that you are located in the true edge of that
40
/// comparison, which tells you x.0 is 50.
41
///
42
/// In order to reduce the number of copies inserted, predicateinfo is only
43
/// inserted where it would actually be live.  This means if there are no uses of
44
/// an operation dominated by the branch edges, or by an assume, the associated
45
/// predicate info is never inserted.
46
///
47
///
48
//===----------------------------------------------------------------------===//
49
50
#ifndef LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H
51
#define LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H
52
53
#include "llvm/ADT/DenseMap.h"
54
#include "llvm/ADT/DenseSet.h"
55
#include "llvm/ADT/SmallPtrSet.h"
56
#include "llvm/ADT/SmallSet.h"
57
#include "llvm/ADT/SmallVector.h"
58
#include "llvm/ADT/ilist.h"
59
#include "llvm/ADT/ilist_node.h"
60
#include "llvm/ADT/iterator.h"
61
#include "llvm/Analysis/AssumptionCache.h"
62
#include "llvm/Analysis/OrderedInstructions.h"
63
#include "llvm/IR/BasicBlock.h"
64
#include "llvm/IR/Dominators.h"
65
#include "llvm/IR/Instructions.h"
66
#include "llvm/IR/IntrinsicInst.h"
67
#include "llvm/IR/Module.h"
68
#include "llvm/IR/OperandTraits.h"
69
#include "llvm/IR/Type.h"
70
#include "llvm/IR/Use.h"
71
#include "llvm/IR/User.h"
72
#include "llvm/IR/Value.h"
73
#include "llvm/IR/ValueHandle.h"
74
#include "llvm/Pass.h"
75
#include "llvm/PassAnalysisSupport.h"
76
#include "llvm/Support/Casting.h"
77
#include "llvm/Support/Compiler.h"
78
#include "llvm/Support/ErrorHandling.h"
79
#include <algorithm>
80
#include <cassert>
81
#include <cstddef>
82
#include <iterator>
83
#include <memory>
84
#include <utility>
85
86
namespace llvm {
87
88
class DominatorTree;
89
class Function;
90
class Instruction;
91
class MemoryAccess;
92
class LLVMContext;
93
class raw_ostream;
94
95
enum PredicateType { PT_Branch, PT_Assume, PT_Switch };
96
97
// Base class for all predicate information we provide.
98
// All of our predicate information has at least a comparison.
99
class PredicateBase : public ilist_node<PredicateBase> {
100
public:
101
  PredicateType Type;
102
  // The original operand before we renamed it.
103
  // This can be use by passes, when destroying predicateinfo, to know
104
  // whether they can just drop the intrinsic, or have to merge metadata.
105
  Value *OriginalOp;
106
  PredicateBase(const PredicateBase &) = delete;
107
  PredicateBase &operator=(const PredicateBase &) = delete;
108
  PredicateBase() = delete;
109
3.14M
  virtual ~PredicateBase() = default;
110
111
protected:
112
3.14M
  PredicateBase(PredicateType PT, Value *Op) : Type(PT), OriginalOp(Op) {}
113
};
114
115
class PredicateWithCondition : public PredicateBase {
116
public:
117
  Value *Condition;
118
140
  static bool classof(const PredicateBase *PB) {
119
140
    return PB->Type == PT_Assume || 
PB->Type == PT_Branch115
||
120
140
           
PB->Type == PT_Switch2
;
121
140
  }
122
123
protected:
124
  PredicateWithCondition(PredicateType PT, Value *Op, Value *Condition)
125
3.14M
      : PredicateBase(PT, Op), Condition(Condition) {}
126
};
127
128
// Provides predicate information for assumes.  Since assumes are always true,
129
// we simply provide the assume instruction, so you can tell your relative
130
// position to it.
131
class PredicateAssume : public PredicateWithCondition {
132
public:
133
  IntrinsicInst *AssumeInst;
134
  PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition)
135
      : PredicateWithCondition(PT_Assume, Op, Condition),
136
49
        AssumeInst(AssumeInst) {}
137
  PredicateAssume() = delete;
138
3.14M
  static bool classof(const PredicateBase *PB) {
139
3.14M
    return PB->Type == PT_Assume;
140
3.14M
  }
141
};
142
143
// Mixin class for edge predicates.  The FROM block is the block where the
144
// predicate originates, and the TO block is the block where the predicate is
145
// valid.
146
class PredicateWithEdge : public PredicateWithCondition {
147
public:
148
  BasicBlock *From;
149
  BasicBlock *To;
150
  PredicateWithEdge() = delete;
151
3.66M
  static bool classof(const PredicateBase *PB) {
152
3.66M
    return PB->Type == PT_Branch || 
PB->Type == PT_Switch10.9k
;
153
3.66M
  }
154
155
protected:
156
  PredicateWithEdge(PredicateType PType, Value *Op, BasicBlock *From,
157
                    BasicBlock *To, Value *Cond)
158
3.14M
      : PredicateWithCondition(PType, Op, Cond), From(From), To(To) {}
159
};
160
161
// Provides predicate information for branches.
162
class PredicateBranch : public PredicateWithEdge {
163
public:
164
  // If true, SplitBB is the true successor, otherwise it's the false successor.
165
  bool TrueEdge;
166
  PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB,
167
                  Value *Condition, bool TakenEdge)
168
      : PredicateWithEdge(PT_Branch, Op, BranchBB, SplitBB, Condition),
169
3.13M
        TrueEdge(TakenEdge) {}
170
  PredicateBranch() = delete;
171
611k
  static bool classof(const PredicateBase *PB) {
172
611k
    return PB->Type == PT_Branch;
173
611k
  }
174
};
175
176
class PredicateSwitch : public PredicateWithEdge {
177
public:
178
  Value *CaseValue;
179
  // This is the switch instruction.
180
  SwitchInst *Switch;
181
  PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB,
182
                  Value *CaseValue, SwitchInst *SI)
183
      : PredicateWithEdge(PT_Switch, Op, SwitchBB, TargetBB,
184
                          SI->getCondition()),
185
10.8k
        CaseValue(CaseValue), Switch(SI) {}
186
  PredicateSwitch() = delete;
187
9
  static bool classof(const PredicateBase *PB) {
188
9
    return PB->Type == PT_Switch;
189
9
  }
190
};
191
192
// This name is used in a few places, so kick it into their own namespace
193
namespace PredicateInfoClasses {
194
struct ValueDFS;
195
}
196
197
/// Encapsulates PredicateInfo, including all data associated with memory
198
/// accesses.
199
class PredicateInfo {
200
private:
201
  // Used to store information about each value we might rename.
202
  struct ValueInfo {
203
    // Information about each possible copy. During processing, this is each
204
    // inserted info. After processing, we move the uninserted ones to the
205
    // uninserted vector.
206
    SmallVector<PredicateBase *, 4> Infos;
207
    SmallVector<PredicateBase *, 4> UninsertedInfos;
208
  };
209
  // This owns the all the predicate infos in the function, placed or not.
210
  iplist<PredicateBase> AllInfos;
211
212
public:
213
  PredicateInfo(Function &, DominatorTree &, AssumptionCache &);
214
  ~PredicateInfo();
215
216
  void verifyPredicateInfo() const;
217
218
  void dump() const;
219
  void print(raw_ostream &) const;
220
221
14.1M
  const PredicateBase *getPredicateInfoFor(const Value *V) const {
222
14.1M
    return PredicateMap.lookup(V);
223
14.1M
  }
224
225
protected:
226
  // Used by PredicateInfo annotater, dumpers, and wrapper pass.
227
  friend class PredicateInfoAnnotatedWriter;
228
  friend class PredicateInfoPrinterLegacyPass;
229
230
private:
231
  void buildPredicateInfo();
232
  void processAssume(IntrinsicInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
233
  void processBranch(BranchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
234
  void processSwitch(SwitchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
235
  void renameUses(SmallPtrSetImpl<Value *> &);
236
  using ValueDFS = PredicateInfoClasses::ValueDFS;
237
  typedef SmallVectorImpl<ValueDFS> ValueDFSStack;
238
  void convertUsesToDFSOrdered(Value *, SmallVectorImpl<ValueDFS> &);
239
  Value *materializeStack(unsigned int &, ValueDFSStack &, Value *);
240
  bool stackIsInScope(const ValueDFSStack &, const ValueDFS &) const;
241
  void popStackUntilDFSScope(ValueDFSStack &, const ValueDFS &);
242
  ValueInfo &getOrCreateValueInfo(Value *);
243
  void addInfoFor(SmallPtrSetImpl<Value *> &OpsToRename, Value *Op,
244
                  PredicateBase *PB);
245
  const ValueInfo &getValueInfo(Value *) const;
246
  Function &F;
247
  DominatorTree &DT;
248
  AssumptionCache &AC;
249
  OrderedInstructions OI;
250
  // This maps from copy operands to Predicate Info. Note that it does not own
251
  // the Predicate Info, they belong to the ValueInfo structs in the ValueInfos
252
  // vector.
253
  DenseMap<const Value *, const PredicateBase *> PredicateMap;
254
  // This stores info about each operand or comparison result we make copies
255
  // of.  The real ValueInfos start at index 1, index 0 is unused so that we can
256
  // more easily detect invalid indexing.
257
  SmallVector<ValueInfo, 32> ValueInfos;
258
  // This gives the index into the ValueInfos array for a given Value.  Because
259
  // 0 is not a valid Value Info index, you can use DenseMap::lookup and tell
260
  // whether it returned a valid result.
261
  DenseMap<Value *, unsigned int> ValueInfoNums;
262
  // The set of edges along which we can only handle phi uses, due to critical
263
  // edges.
264
  DenseSet<std::pair<BasicBlock *, BasicBlock *>> EdgeUsesOnly;
265
  // The set of ssa_copy declarations we created with our custom mangling.
266
  SmallSet<AssertingVH<Function>, 20> CreatedDeclarations;
267
};
268
269
// This pass does eager building and then printing of PredicateInfo. It is used
270
// by
271
// the tests to be able to build, dump, and verify PredicateInfo.
272
class PredicateInfoPrinterLegacyPass : public FunctionPass {
273
public:
274
  PredicateInfoPrinterLegacyPass();
275
276
  static char ID;
277
  bool runOnFunction(Function &) override;
278
  void getAnalysisUsage(AnalysisUsage &AU) const override;
279
};
280
281
/// Printer pass for \c PredicateInfo.
282
class PredicateInfoPrinterPass
283
    : public PassInfoMixin<PredicateInfoPrinterPass> {
284
  raw_ostream &OS;
285
286
public:
287
0
  explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {}
288
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
289
};
290
291
/// Verifier pass for \c PredicateInfo.
292
struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> {
293
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
294
};
295
296
} // end namespace llvm
297
298
#endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H