Coverage Report

Created: 2017-08-18 19:41

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