Coverage Report

Created: 2018-12-09 11:54

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/include/polly/Support/ScopHelper.h
Line
Count
Source (jump to first uncovered line)
1
//===------ Support/ScopHelper.h -- Some Helper Functions for Scop. -------===//
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
// Small functions that help with LLVM-IR.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef POLLY_SUPPORT_IRHELPER_H
15
#define POLLY_SUPPORT_IRHELPER_H
16
17
#include "llvm/ADT/DenseMap.h"
18
#include "llvm/ADT/SetVector.h"
19
#include "llvm/IR/Instructions.h"
20
#include "llvm/IR/IntrinsicInst.h"
21
#include "llvm/IR/ValueHandle.h"
22
#include <tuple>
23
#include <vector>
24
25
namespace llvm {
26
class LoopInfo;
27
class Loop;
28
class ScalarEvolution;
29
class SCEV;
30
class Region;
31
class Pass;
32
class DominatorTree;
33
class RegionInfo;
34
class GetElementPtrInst;
35
} // namespace llvm
36
37
namespace polly {
38
class Scop;
39
class ScopStmt;
40
41
/// Type to remap values.
42
using ValueMapT = llvm::DenseMap<llvm::AssertingVH<llvm::Value>,
43
                                 llvm::AssertingVH<llvm::Value>>;
44
45
/// Type for a set of invariant loads.
46
using InvariantLoadsSetTy = llvm::SetVector<llvm::AssertingVH<llvm::LoadInst>>;
47
48
/// Set type for parameters.
49
using ParameterSetTy = llvm::SetVector<const llvm::SCEV *>;
50
51
/// Set of loops (used to remember loops in non-affine subregions).
52
using BoxedLoopsSetTy = llvm::SetVector<const llvm::Loop *>;
53
54
/// Utility proxy to wrap the common members of LoadInst and StoreInst.
55
///
56
/// This works like the LLVM utility class CallSite, ie. it forwards all calls
57
/// to either a LoadInst, StoreInst, MemIntrinsic or MemTransferInst.
58
/// It is similar to LLVM's utility classes IntrinsicInst, MemIntrinsic,
59
/// MemTransferInst, etc. in that it offers a common interface, but does not act
60
/// as a fake base class.
61
/// It is similar to StringRef and ArrayRef in that it holds a pointer to the
62
/// referenced object and should be passed by-value as it is small enough.
63
///
64
/// This proxy can either represent a LoadInst instance, a StoreInst instance,
65
/// a MemIntrinsic instance (memset, memmove, memcpy), a CallInst instance or a
66
/// nullptr (only creatable using the default constructor); never an Instruction
67
/// that is neither of the above mentioned. When representing a nullptr, only
68
/// the following methods are defined:
69
/// isNull(), isInstruction(), isLoad(), isStore(), ..., isMemTransferInst(),
70
/// operator bool(), operator!()
71
///
72
/// The functions isa, cast, cast_or_null, dyn_cast are modeled te resemble
73
/// those from llvm/Support/Casting.h. Partial template function specialization
74
/// is currently not supported in C++ such that those cannot be used directly.
75
/// (llvm::isa could, but then llvm:cast etc. would not have the expected
76
/// behavior)
77
class MemAccInst {
78
private:
79
  llvm::Instruction *I;
80
81
public:
82
4.74k
  MemAccInst() : I(nullptr) {}
83
36.9k
  MemAccInst(const MemAccInst &Inst) : I(Inst.I) {}
84
0
  /* implicit */ MemAccInst(llvm::LoadInst &LI) : I(&LI) {}
85
672
  /* implicit */ MemAccInst(llvm::LoadInst *LI) : I(LI) {}
86
0
  /* implicit */ MemAccInst(llvm::StoreInst &SI) : I(&SI) {}
87
421
  /* implicit */ MemAccInst(llvm::StoreInst *SI) : I(SI) {}
88
0
  /* implicit */ MemAccInst(llvm::MemIntrinsic *MI) : I(MI) {}
89
0
  /* implicit */ MemAccInst(llvm::CallInst *CI) : I(CI) {}
90
15.7k
  explicit MemAccInst(llvm::Instruction &I) : I(&I) { assert(isa(I)); }
91
4.96k
  explicit MemAccInst(llvm::Instruction *I) : I(I) { assert(isa(I)); }
92
93
20.5k
  static bool isa(const llvm::Value &V) {
94
20.5k
    return llvm::isa<llvm::LoadInst>(V) || 
llvm::isa<llvm::StoreInst>(V)12.5k
||
95
20.5k
           
llvm::isa<llvm::CallInst>(V)4.79k
||
llvm::isa<llvm::MemIntrinsic>(V)4.74k
;
96
20.5k
  }
97
1.65k
  static bool isa(const llvm::Value *V) {
98
1.65k
    return llvm::isa<llvm::LoadInst>(V) || 
llvm::isa<llvm::StoreInst>(V)821
||
99
1.65k
           
llvm::isa<llvm::CallInst>(V)3
||
llvm::isa<llvm::MemIntrinsic>(V)1
;
100
1.65k
  }
101
0
  static MemAccInst cast(llvm::Value &V) {
102
0
    return MemAccInst(llvm::cast<llvm::Instruction>(V));
103
0
  }
104
0
  static MemAccInst cast(llvm::Value *V) {
105
0
    return MemAccInst(llvm::cast<llvm::Instruction>(V));
106
0
  }
107
0
  static MemAccInst cast_or_null(llvm::Value &V) {
108
0
    return MemAccInst(llvm::cast<llvm::Instruction>(V));
109
0
  }
110
0
  static MemAccInst cast_or_null(llvm::Value *V) {
111
0
    if (!V)
112
0
      return MemAccInst();
113
0
    return MemAccInst(llvm::cast<llvm::Instruction>(V));
114
0
  }
115
20.5k
  static MemAccInst dyn_cast(llvm::Value &V) {
116
20.5k
    if (isa(V))
117
15.7k
      return MemAccInst(llvm::cast<llvm::Instruction>(V));
118
4.74k
    return MemAccInst();
119
4.74k
  }
120
1.65k
  static MemAccInst dyn_cast(llvm::Value *V) {
121
1.65k
    assert(V);
122
1.65k
    if (isa(V))
123
1.65k
      return MemAccInst(llvm::cast<llvm::Instruction>(V));
124
1
    return MemAccInst();
125
1
  }
126
127
0
  MemAccInst &operator=(const MemAccInst &Inst) {
128
0
    I = Inst.I;
129
0
    return *this;
130
0
  }
131
0
  MemAccInst &operator=(llvm::LoadInst &LI) {
132
0
    I = &LI;
133
0
    return *this;
134
0
  }
135
0
  MemAccInst &operator=(llvm::LoadInst *LI) {
136
0
    I = LI;
137
0
    return *this;
138
0
  }
139
0
  MemAccInst &operator=(llvm::StoreInst &SI) {
140
0
    I = &SI;
141
0
    return *this;
142
0
  }
143
0
  MemAccInst &operator=(llvm::StoreInst *SI) {
144
0
    I = SI;
145
0
    return *this;
146
0
  }
147
0
  MemAccInst &operator=(llvm::MemIntrinsic &MI) {
148
0
    I = &MI;
149
0
    return *this;
150
0
  }
151
0
  MemAccInst &operator=(llvm::MemIntrinsic *MI) {
152
0
    I = MI;
153
0
    return *this;
154
0
  }
155
0
  MemAccInst &operator=(llvm::CallInst &CI) {
156
0
    I = &CI;
157
0
    return *this;
158
0
  }
159
0
  MemAccInst &operator=(llvm::CallInst *CI) {
160
0
    I = CI;
161
0
    return *this;
162
0
  }
163
164
22.6k
  llvm::Instruction *get() const {
165
22.6k
    assert(I && "Unexpected nullptr!");
166
22.6k
    return I;
167
22.6k
  }
168
23.4k
  operator llvm::Instruction *() const { return asInstruction(); }
169
22.6k
  llvm::Instruction *operator->() const { return get(); }
170
171
27.8k
  explicit operator bool() const { return isInstruction(); }
172
1.63k
  bool operator!() const { return isNull(); }
173
174
10.1k
  llvm::Value *getValueOperand() const {
175
10.1k
    if (isLoad())
176
5.05k
      return asLoad();
177
5.14k
    if (isStore())
178
5.12k
      return asStore()->getValueOperand();
179
24
    if (isMemIntrinsic())
180
24
      return nullptr;
181
0
    if (isCallInst())
182
0
      return nullptr;
183
0
    llvm_unreachable("Operation not supported on nullptr");
184
0
  }
185
28.3k
  llvm::Value *getPointerOperand() const {
186
28.3k
    if (isLoad())
187
14.3k
      return asLoad()->getPointerOperand();
188
14.0k
    if (isStore())
189
13.9k
      return asStore()->getPointerOperand();
190
63
    if (isMemIntrinsic())
191
18
      return asMemIntrinsic()->getRawDest();
192
45
    if (isCallInst())
193
45
      return nullptr;
194
0
    llvm_unreachable("Operation not supported on nullptr");
195
0
  }
196
197
5
  unsigned getAlignment() const {
198
5
    if (isLoad())
199
4
      return asLoad()->getAlignment();
200
1
    if (isStore())
201
1
      return asStore()->getAlignment();
202
0
    if (isMemTransferInst())
203
0
      return std::min(asMemTransferInst()->getDestAlignment(),
204
0
                      asMemTransferInst()->getSourceAlignment());
205
0
    if (isMemIntrinsic())
206
0
      return asMemIntrinsic()->getDestAlignment();
207
0
    if (isCallInst())
208
0
      return 0;
209
0
    llvm_unreachable("Operation not supported on nullptr");
210
0
  }
211
0
  bool isVolatile() const {
212
0
    if (isLoad())
213
0
      return asLoad()->isVolatile();
214
0
    if (isStore())
215
0
      return asStore()->isVolatile();
216
0
    if (isMemIntrinsic())
217
0
      return asMemIntrinsic()->isVolatile();
218
0
    if (isCallInst())
219
0
      return false;
220
0
    llvm_unreachable("Operation not supported on nullptr");
221
0
  }
222
12.4k
  bool isSimple() const {
223
12.4k
    if (isLoad())
224
6.49k
      return asLoad()->isSimple();
225
5.93k
    if (isStore())
226
5.93k
      return asStore()->isSimple();
227
0
    if (isMemIntrinsic())
228
0
      return !asMemIntrinsic()->isVolatile();
229
0
    if (isCallInst())
230
0
      return true;
231
0
    llvm_unreachable("Operation not supported on nullptr");
232
0
  }
233
0
  llvm::AtomicOrdering getOrdering() const {
234
0
    if (isLoad())
235
0
      return asLoad()->getOrdering();
236
0
    if (isStore())
237
0
      return asStore()->getOrdering();
238
0
    if (isMemIntrinsic())
239
0
      return llvm::AtomicOrdering::NotAtomic;
240
0
    if (isCallInst())
241
0
      return llvm::AtomicOrdering::NotAtomic;
242
0
    llvm_unreachable("Operation not supported on nullptr");
243
0
  }
244
0
  bool isUnordered() const {
245
0
    if (isLoad())
246
0
      return asLoad()->isUnordered();
247
0
    if (isStore())
248
0
      return asStore()->isUnordered();
249
0
    // Copied from the Load/Store implementation of isUnordered:
250
0
    if (isMemIntrinsic())
251
0
      return !asMemIntrinsic()->isVolatile();
252
0
    if (isCallInst())
253
0
      return true;
254
0
    llvm_unreachable("Operation not supported on nullptr");
255
0
  }
256
257
2.44k
  bool isNull() const { return !I; }
258
27.8k
  bool isInstruction() const { return I; }
259
260
67.5k
  llvm::Instruction *asInstruction() const { return I; }
261
262
private:
263
50.9k
  bool isLoad() const { return I && llvm::isa<llvm::LoadInst>(I); }
264
25.1k
  bool isStore() const { return I && llvm::isa<llvm::StoreInst>(I); }
265
45
  bool isCallInst() const { return I && llvm::isa<llvm::CallInst>(I); }
266
87
  bool isMemIntrinsic() const { return I && llvm::isa<llvm::MemIntrinsic>(I); }
267
0
  bool isMemSetInst() const { return I && llvm::isa<llvm::MemSetInst>(I); }
268
0
  bool isMemTransferInst() const {
269
0
    return I && llvm::isa<llvm::MemTransferInst>(I);
270
0
  }
271
272
25.8k
  llvm::LoadInst *asLoad() const { return llvm::cast<llvm::LoadInst>(I); }
273
25.0k
  llvm::StoreInst *asStore() const { return llvm::cast<llvm::StoreInst>(I); }
274
0
  llvm::CallInst *asCallInst() const { return llvm::cast<llvm::CallInst>(I); }
275
18
  llvm::MemIntrinsic *asMemIntrinsic() const {
276
18
    return llvm::cast<llvm::MemIntrinsic>(I);
277
18
  }
278
0
  llvm::MemSetInst *asMemSetInst() const {
279
0
    return llvm::cast<llvm::MemSetInst>(I);
280
0
  }
281
0
  llvm::MemTransferInst *asMemTransferInst() const {
282
0
    return llvm::cast<llvm::MemTransferInst>(I);
283
0
  }
284
};
285
} // namespace polly
286
287
namespace llvm {
288
/// Specialize simplify_type for MemAccInst to enable dyn_cast and cast
289
///        from a MemAccInst object.
290
template <> struct simplify_type<polly::MemAccInst> {
291
  typedef Instruction *SimpleType;
292
44.0k
  static SimpleType getSimplifiedValue(polly::MemAccInst &I) {
293
44.0k
    return I.asInstruction();
294
44.0k
  }
295
};
296
} // namespace llvm
297
298
namespace polly {
299
300
/// Simplify the region to have a single unconditional entry edge and a
301
/// single exit edge.
302
///
303
/// Although this function allows DT and RI to be null, regions only work
304
/// properly if the DominatorTree (for Region::contains) and RegionInfo are kept
305
/// up-to-date.
306
///
307
/// @param R  The region to be simplified
308
/// @param DT DominatorTree to be updated.
309
/// @param LI LoopInfo to be updated.
310
/// @param RI RegionInfo to be updated.
311
void simplifyRegion(llvm::Region *R, llvm::DominatorTree *DT,
312
                    llvm::LoopInfo *LI, llvm::RegionInfo *RI);
313
314
/// Split the entry block of a function to store the newly inserted
315
///        allocations outside of all Scops.
316
///
317
/// @param EntryBlock The entry block of the current function.
318
/// @param P          The pass that currently running.
319
///
320
void splitEntryBlockForAlloca(llvm::BasicBlock *EntryBlock, llvm::Pass *P);
321
322
/// Split the entry block of a function to store the newly inserted
323
///        allocations outside of all Scops.
324
///
325
/// @param DT DominatorTree to be updated.
326
/// @param LI LoopInfo to be updated.
327
/// @param RI RegionInfo to be updated.
328
void splitEntryBlockForAlloca(llvm::BasicBlock *EntryBlock,
329
                              llvm::DominatorTree *DT, llvm::LoopInfo *LI,
330
                              llvm::RegionInfo *RI);
331
332
/// Wrapper for SCEVExpander extended to all Polly features.
333
///
334
/// This wrapper will internally call the SCEVExpander but also makes sure that
335
/// all additional features not represented in SCEV (e.g., SDiv/SRem are not
336
/// black boxes but can be part of the function) will be expanded correctly.
337
///
338
/// The parameters are the same as for the creation of a SCEVExpander as well
339
/// as the call to SCEVExpander::expandCodeFor:
340
///
341
/// @param S     The current Scop.
342
/// @param SE    The Scalar Evolution pass.
343
/// @param DL    The module data layout.
344
/// @param Name  The suffix added to the new instruction names.
345
/// @param E     The expression for which code is actually generated.
346
/// @param Ty    The type of the resulting code.
347
/// @param IP    The insertion point for the new code.
348
/// @param VMap  A remapping of values used in @p E.
349
/// @param RTCBB The last block of the RTC. Used to insert loop-invariant
350
///              instructions in rare cases.
351
llvm::Value *expandCodeFor(Scop &S, llvm::ScalarEvolution &SE,
352
                           const llvm::DataLayout &DL, const char *Name,
353
                           const llvm::SCEV *E, llvm::Type *Ty,
354
                           llvm::Instruction *IP, ValueMapT *VMap,
355
                           llvm::BasicBlock *RTCBB);
356
357
/// Check if the block is a error block.
358
///
359
/// A error block is currently any block that fulfills at least one of
360
/// the following conditions:
361
///
362
///  - It is terminated by an unreachable instruction
363
///  - It contains a call to a non-pure function that is not immediately
364
///    dominated by a loop header and that does not dominate the region exit.
365
///    This is a heuristic to pick only error blocks that are conditionally
366
///    executed and can be assumed to be not executed at all without the domains
367
///    being available.
368
///
369
/// @param BB The block to check.
370
/// @param R  The analyzed region.
371
/// @param LI The loop info analysis.
372
/// @param DT The dominator tree of the function.
373
///
374
/// @return True if the block is a error block, false otherwise.
375
bool isErrorBlock(llvm::BasicBlock &BB, const llvm::Region &R,
376
                  llvm::LoopInfo &LI, const llvm::DominatorTree &DT);
377
378
/// Return the condition for the terminator @p TI.
379
///
380
/// For unconditional branches the "i1 true" condition will be returned.
381
///
382
/// @param TI The terminator to get the condition from.
383
///
384
/// @return The condition of @p TI and nullptr if none could be extracted.
385
llvm::Value *getConditionFromTerminator(llvm::Instruction *TI);
386
387
/// Check if @p LInst can be hoisted in @p R.
388
///
389
/// @param LInst The load to check.
390
/// @param R     The analyzed region.
391
/// @param LI    The loop info.
392
/// @param SE    The scalar evolution analysis.
393
/// @param DT    The dominator tree of the function.
394
/// @param KnownInvariantLoads The invariant load set.
395
///
396
/// @return True if @p LInst can be hoisted in @p R.
397
bool isHoistableLoad(llvm::LoadInst *LInst, llvm::Region &R, llvm::LoopInfo &LI,
398
                     llvm::ScalarEvolution &SE, const llvm::DominatorTree &DT,
399
                     const InvariantLoadsSetTy &KnownInvariantLoads);
400
401
/// Return true iff @p V is an intrinsic that we ignore during code
402
///        generation.
403
bool isIgnoredIntrinsic(const llvm::Value *V);
404
405
/// Check whether a value an be synthesized by the code generator.
406
///
407
/// Some value will be recalculated only from information that is code generated
408
/// from the polyhedral representation. For such instructions we do not need to
409
/// ensure that their operands are available during code generation.
410
///
411
/// @param V The value to check.
412
/// @param S The current SCoP.
413
/// @param SE The scalar evolution database.
414
/// @param Scope Location where the value would by synthesized.
415
/// @return If the instruction I can be regenerated from its
416
///         scalar evolution representation, return true,
417
///         otherwise return false.
418
bool canSynthesize(const llvm::Value *V, const Scop &S,
419
                   llvm::ScalarEvolution *SE, llvm::Loop *Scope);
420
421
/// Return the block in which a value is used.
422
///
423
/// For normal instructions, this is the instruction's parent block. For PHI
424
/// nodes, this is the incoming block of that use, because this is where the
425
/// operand must be defined (i.e. its definition dominates this block).
426
/// Non-instructions do not use operands at a specific point such that in this
427
/// case this function returns nullptr.
428
llvm::BasicBlock *getUseBlock(const llvm::Use &U);
429
430
/// Derive the individual index expressions from a GEP instruction.
431
///
432
/// This function optimistically assumes the GEP references into a fixed size
433
/// array. If this is actually true, this function returns a list of array
434
/// subscript expressions as SCEV as well as a list of integers describing
435
/// the size of the individual array dimensions. Both lists have either equal
436
/// length or the size list is one element shorter in case there is no known
437
/// size available for the outermost array dimension.
438
///
439
/// @param GEP The GetElementPtr instruction to analyze.
440
///
441
/// @return A tuple with the subscript expressions and the dimension sizes.
442
std::tuple<std::vector<const llvm::SCEV *>, std::vector<int>>
443
getIndexExpressionsFromGEP(llvm::GetElementPtrInst *GEP,
444
                           llvm::ScalarEvolution &SE);
445
446
// If the loop is nonaffine/boxed, return the first non-boxed surrounding loop
447
// for Polly. If the loop is affine, return the loop itself.
448
//
449
// @param L             Pointer to the Loop object to analyze.
450
// @param LI            Reference to the LoopInfo.
451
// @param BoxedLoops    Set of Boxed Loops we get from the SCoP.
452
llvm::Loop *getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI,
453
                                    const BoxedLoopsSetTy &BoxedLoops);
454
455
// If the Basic Block belongs to a loop that is nonaffine/boxed, return the
456
// first non-boxed surrounding loop for Polly. If the loop is affine, return
457
// the loop itself.
458
//
459
// @param BB            Pointer to the Basic Block to analyze.
460
// @param LI            Reference to the LoopInfo.
461
// @param BoxedLoops    Set of Boxed Loops we get from the SCoP.
462
llvm::Loop *getFirstNonBoxedLoopFor(llvm::BasicBlock *BB, llvm::LoopInfo &LI,
463
                                    const BoxedLoopsSetTy &BoxedLoops);
464
465
/// Is the given instruction a call to a debug function?
466
///
467
/// A debug function can be used to insert output in Polly-optimized code which
468
/// normally does not allow function calls with side-effects. For instance, a
469
/// printf can be inserted to check whether a value still has the expected value
470
/// after Polly generated code:
471
///
472
///     int sum = 0;
473
///     for (int i = 0; i < 16; i+=1) {
474
///       sum += i;
475
///       printf("The value of sum at i=%d is %d\n", sum, i);
476
///     }
477
bool isDebugCall(llvm::Instruction *Inst);
478
479
/// Does the statement contain a call to a debug function?
480
///
481
/// Such a statement must not be removed, even if has no side-effects.
482
bool hasDebugCall(ScopStmt *Stmt);
483
} // namespace polly
484
#endif