Coverage Report

Created: 2017-11-21 16:49

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/include/polly/Support/VirtualInstruction.h
Line
Count
Source (jump to first uncovered line)
1
//===------ VirtualInstruction.cpp ------------------------------*- 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
// Tools for determining which instructions are within a statement and the
11
// nature of their operands.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#ifndef POLLY_SUPPORT_VIRTUALINSTRUCTION_H
16
#define POLLY_SUPPORT_VIRTUALINSTRUCTION_H
17
18
#include "polly/ScopInfo.h"
19
20
namespace polly {
21
22
/// Determine the nature of a value's use within a statement.
23
///
24
/// These are not always representable by llvm::Use. For instance, scalar write
25
/// MemoryAccesses do use a value, but are not associated with an instruction's
26
/// argument.
27
///
28
/// Despite its name it is not tied to virtual instructions (although it works
29
/// fine with them), but to promote consistent handling of values used in
30
/// statements.
31
class VirtualUse {
32
public:
33
  /// The different types of uses. Handling usually differentiates a lot between
34
  /// these; one can use a switch to handle each case (and get warned by the
35
  /// compiler if one is not handled).
36
  enum UseKind {
37
    // An llvm::Constant.
38
    Constant,
39
40
    // An llvm::BasicBlock.
41
    Block,
42
43
    // A value that can be generated using ScopExpander.
44
    Synthesizable,
45
46
    // A load that always reads the same value throughout the SCoP (address and
47
    // the value located there a SCoP-invariant) and has been hoisted in front
48
    // of the SCoP.
49
    Hoisted,
50
51
    // Definition before the SCoP and not synthesizable. Can be an instruction
52
    // outside the SCoP, a function argument or a global value. Whether there is
53
    // a scalar MemoryAccess in this statement for reading it depends on the
54
    // -polly-analyze-read-only-scalars switch.
55
    ReadOnly,
56
57
    // A definition within the same statement. No MemoryAccess between
58
    // definition and use are necessary.
59
    Intra,
60
61
    // Definition in another statement. There is a scalar MemoryAccess that
62
    // makes it available in this statement.
63
    Inter
64
  };
65
66
private:
67
  /// The statement where a value is used.
68
  ScopStmt *User;
69
70
  /// The value that is used.
71
  Value *Val;
72
73
  /// The type of value use.
74
  UseKind Kind;
75
76
  /// The value represented as llvm::SCEV expression.
77
  const SCEV *ScevExpr;
78
79
  /// If this is an inter-statement (or read-only) use, contains the
80
  /// MemoryAccess that makes the value available in this statement. In case of
81
  /// intra-statement uses, can contain a MemoryKind::Array access. In all other
82
  /// cases, it is a nullptr.
83
  MemoryAccess *InputMA;
84
85
  VirtualUse(ScopStmt *User, Value *Val, UseKind Kind, const SCEV *ScevExpr,
86
             MemoryAccess *InputMA)
87
5.28k
      : User(User), Val(Val), Kind(Kind), ScevExpr(ScevExpr), InputMA(InputMA) {
88
5.28k
  }
89
90
public:
91
  /// Get a VirtualUse for an llvm::Use.
92
  ///
93
  /// @param S       The Scop object.
94
  /// @param U       The llvm::Use the get information for.
95
  /// @param LI      The LoopInfo analysis. Needed to determine whether the
96
  ///                value is synthesizable.
97
  /// @param Virtual Whether to ignore existing MemoryAcccess.
98
  ///
99
  /// @return The VirtualUse representing the same use as @p U.
100
  static VirtualUse create(Scop *S, const Use &U, LoopInfo *LI, bool Virtual);
101
102
  /// Get a VirtualUse for any kind of use of a value within a statement.
103
  ///
104
  /// @param S         The Scop object.
105
  /// @param UserStmt  The statement in which @p Val is used. Can be nullptr, in
106
  ///                  which case it assumed that the statement has been
107
  ///                  removed, which is only possible if no instruction in it
108
  ///                  had side-effects or computes a value used by another
109
  ///                  statement.
110
  /// @param UserScope Loop scope in which the value is used. Needed to
111
  ///                  determine whether the value is synthesizable.
112
  /// @param Val       The value being used.
113
  /// @param Virtual   Whether to use (and prioritize over instruction location)
114
  ///                  information about MemoryAccesses.
115
  ///
116
  /// @return A VirtualUse object that gives information about @p Val's use in
117
  ///         @p UserStmt.
118
  static VirtualUse create(Scop *S, ScopStmt *UserStmt, Loop *UserScope,
119
                           Value *Val, bool Virtual);
120
121
  static VirtualUse create(ScopStmt *UserStmt, Loop *UserScope, Value *Val,
122
1.15k
                           bool Virtual) {
123
1.15k
    return create(UserStmt->getParent(), UserStmt, UserScope, Val, Virtual);
124
1.15k
  }
125
126
0
  bool isConstant() const { return Kind == Constant; }
127
0
  bool isBlock() const { return Kind == Block; }
128
0
  bool isSynthesizable() const { return Kind == Synthesizable; }
129
0
  bool isHoisted() const { return Kind == Hoisted; }
130
0
  bool isReadOnly() const { return Kind == ReadOnly; }
131
0
  bool isIntra() const { return Kind == Intra; }
132
122
  bool isInter() const { return Kind == Inter; }
133
134
  /// Return user statement.
135
90
  ScopStmt *getUser() const { return User; }
136
137
  /// Return the used value.
138
90
  llvm::Value *getValue() const { return Val; }
139
140
  /// Return the type of use.
141
5.28k
  UseKind getKind() const { return Kind; }
142
143
  /// Return the ScalarEvolution representation of @p Val.
144
1
  const SCEV *getScevExpr() const { return ScevExpr; }
145
146
  /// Return the MemoryAccess that makes the value available in this statement,
147
  /// if any.
148
7
  MemoryAccess *getMemoryAccess() const { return InputMA; }
149
150
  /// Print a description of this object.
151
  ///
152
  /// @param OS           Stream to print to.
153
  /// @param Reproducible If true, ensures that the output is stable between
154
  ///                     runs and is suitable to check in regression tests.
155
  ///                     This excludes printing e.g. pointer values. If false,
156
  ///                     the output should not be used for regression tests,
157
  ///                     but may contain more information useful in debugger
158
  ///                     sessions.
159
  void print(raw_ostream &OS, bool Reproducible = true) const;
160
161
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
162
  void dump() const;
163
#endif
164
};
165
166
/// An iterator for virtual operands.
167
class VirtualOperandIterator
168
    : public std::iterator<std::forward_iterator_tag, VirtualUse> {
169
  friend class VirtualInstruction;
170
  friend class VirtualUse;
171
172
  using super = std::iterator<std::forward_iterator_tag, VirtualUse>;
173
  using Self = VirtualOperandIterator;
174
175
  ScopStmt *User;
176
  User::op_iterator U;
177
178
  VirtualOperandIterator(ScopStmt *User, User::op_iterator U)
179
216
      : User(User), U(U) {}
180
181
public:
182
  using pointer = typename super::pointer;
183
  using reference = typename super::reference;
184
185
0
  inline bool operator==(const Self &that) const {
186
0
    assert(this->User == that.User);
187
0
    return this->U == that.U;
188
0
  }
189
190
287
  inline bool operator!=(const Self &that) const {
191
287
    assert(this->User == that.User);
192
287
    return this->U != that.U;
193
287
  }
194
195
179
  VirtualUse operator*() const {
196
179
    return VirtualUse::create(User, User->getSurroundingLoop(), U->get(), true);
197
179
  }
198
199
0
  Use *operator->() const { return U; }
200
201
179
  Self &operator++() {
202
179
    U++;
203
179
    return *this;
204
179
  }
205
206
0
  Self operator++(int) {
207
0
    Self tmp = *this;
208
0
    ++*this;
209
0
    return tmp;
210
0
  }
211
};
212
213
/// This class represents a "virtual instruction", an instruction in a ScopStmt,
214
/// effectively a ScopStmt/Instruction-pair.
215
///
216
/// An instructions can be moved between statements (e.g. to avoid a scalar
217
/// dependency) and even can be contained in multiple statements (for instance,
218
/// to recompute a value instead of transferring it), hence 'virtual'. This
219
/// class is required to represent such instructions that are not in their
220
/// 'physical' location anymore.
221
///
222
/// A statement can currently not contain the same instructions multiple times
223
/// (that is, from different loop iterations). Therefore, a
224
/// ScopStmt/Instruction-pair uniquely identifies a virtual instructions.
225
/// ScopStmt::getInstruction() can contain the same instruction multiple times,
226
/// but they necessarily compute the same value.
227
class VirtualInstruction {
228
  friend class VirtualOperandIterator;
229
  friend struct llvm::DenseMapInfo<VirtualInstruction>;
230
231
private:
232
  /// The statement this virtual instruction is in.
233
  ScopStmt *Stmt = nullptr;
234
235
  /// The instruction of a statement.
236
  Instruction *Inst = nullptr;
237
238
public:
239
901
  VirtualInstruction() {}
240
241
  /// Create a new virtual instruction of an instruction @p Inst in @p Stmt.
242
  VirtualInstruction(ScopStmt *Stmt, Instruction *Inst)
243
271
      : Stmt(Stmt), Inst(Inst) {
244
271
    assert(Stmt && Inst);
245
271
  }
246
247
108
  VirtualOperandIterator operand_begin() const {
248
108
    return VirtualOperandIterator(Stmt, Inst->op_begin());
249
108
  }
250
251
108
  VirtualOperandIterator operand_end() const {
252
108
    return VirtualOperandIterator(Stmt, Inst->op_end());
253
108
  }
254
255
  /// Returns a list of virtual operands.
256
  ///
257
  /// Virtual operands, like virtual instructions, need to encode the ScopStmt
258
  /// they are in.
259
108
  llvm::iterator_range<VirtualOperandIterator> operands() const {
260
108
    return {operand_begin(), operand_end()};
261
108
  }
262
263
  /// Return the SCoP everything is contained in.
264
0
  Scop *getScop() const { return Stmt->getParent(); }
265
266
  /// Return the ScopStmt this virtual instruction is in.
267
5.62k
  ScopStmt *getStmt() const { return Stmt; }
268
269
  /// Return the instruction in the statement.
270
4.11k
  Instruction *getInstruction() const { return Inst; }
271
272
  /// Print a description of this object.
273
  ///
274
  /// @param OS           Stream to print to.
275
  /// @param Reproducible If true, ensures that the output is stable between
276
  ///                     runs and is suitable for checks in regression tests.
277
  ///                     This excludes printing e.g., pointer values. If false,
278
  ///                     the output should not be used for regression tests,
279
  ///                     but may contain more information useful in debugger
280
  ///                     sessions.
281
  void print(raw_ostream &OS, bool Reproducible = true) const;
282
283
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
284
  void dump() const;
285
#endif
286
};
287
288
0
static inline bool operator==(VirtualInstruction LHS, VirtualInstruction RHS) {
289
0
  return LHS.getStmt() == RHS.getStmt() &&
290
0
         LHS.getInstruction() == RHS.getInstruction();
291
0
}
Unexecuted instantiation: ScopBuilder.cpp:polly::operator==(polly::VirtualInstruction, polly::VirtualInstruction)
Unexecuted instantiation: BlockGenerators.cpp:polly::operator==(polly::VirtualInstruction, polly::VirtualInstruction)
Unexecuted instantiation: VirtualInstruction.cpp:polly::operator==(polly::VirtualInstruction, polly::VirtualInstruction)
Unexecuted instantiation: ForwardOpTree.cpp:polly::operator==(polly::VirtualInstruction, polly::VirtualInstruction)
Unexecuted instantiation: ZoneAlgo.cpp:polly::operator==(polly::VirtualInstruction, polly::VirtualInstruction)
Unexecuted instantiation: Simplify.cpp:polly::operator==(polly::VirtualInstruction, polly::VirtualInstruction)
292
293
/// Find all reachable instructions and accesses.
294
///
295
/// @param S              The SCoP to find everything reachable in.
296
/// @param LI             LoopInfo required for analysis.
297
/// @param UsedInsts[out] Receives all reachable instructions.
298
/// @param UsedAccs[out]  Receives all reachable accesses.
299
/// @param OnlyLocal      If non-nullptr, activates local mode: The SCoP is
300
///                       assumed to consist only of this statement and is
301
///                       conservatively correct. Does not require walking the
302
///                       whole SCoP.
303
void markReachable(Scop *S, LoopInfo *LI,
304
                   DenseSet<VirtualInstruction> &UsedInsts,
305
                   DenseSet<MemoryAccess *> &UsedAccs,
306
                   ScopStmt *OnlyLocal = nullptr);
307
308
} // namespace polly
309
310
namespace llvm {
311
/// Support VirtualInstructions in llvm::DenseMaps.
312
template <> struct DenseMapInfo<polly::VirtualInstruction> {
313
public:
314
  static bool isEqual(polly::VirtualInstruction LHS,
315
2.57k
                      polly::VirtualInstruction RHS) {
316
2.57k
    return DenseMapInfo<polly::ScopStmt *>::isEqual(LHS.getStmt(),
317
2.57k
                                                    RHS.getStmt()) &&
318
2.57k
           DenseMapInfo<Instruction *>::isEqual(LHS.getInstruction(),
319
1.82k
                                                RHS.getInstruction());
320
2.57k
  }
321
322
435
  static polly::VirtualInstruction getTombstoneKey() {
323
435
    polly::VirtualInstruction TombstoneKey;
324
435
    TombstoneKey.Stmt = DenseMapInfo<polly::ScopStmt *>::getTombstoneKey();
325
435
    TombstoneKey.Inst = DenseMapInfo<Instruction *>::getTombstoneKey();
326
435
    return TombstoneKey;
327
435
  }
328
329
466
  static polly::VirtualInstruction getEmptyKey() {
330
466
    polly::VirtualInstruction EmptyKey;
331
466
    EmptyKey.Stmt = DenseMapInfo<polly::ScopStmt *>::getEmptyKey();
332
466
    EmptyKey.Inst = DenseMapInfo<Instruction *>::getEmptyKey();
333
466
    return EmptyKey;
334
466
  }
335
336
316
  static unsigned getHashValue(polly::VirtualInstruction Val) {
337
316
    return DenseMapInfo<std::pair<polly::ScopStmt *, Instruction *>>::
338
316
        getHashValue(std::make_pair(Val.getStmt(), Val.getInstruction()));
339
316
  }
340
};
341
} // namespace llvm
342
343
#endif /* POLLY_SUPPORT_VIRTUALINSTRUCTION_H */