Coverage Report

Created: 2019-02-20 07:29

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