Coverage Report

Created: 2017-10-03 07:32

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