Coverage Report

Created: 2017-04-27 19:33

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/include/polly/ScopInfo.h
Line
Count
Source (jump to first uncovered line)
1
//===------ polly/ScopInfo.h -----------------------------------*- 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
// Store the polyhedral model representation of a static control flow region,
11
// also called SCoP (Static Control Part).
12
//
13
// This representation is shared among several tools in the polyhedral
14
// community, which are e.g. CLooG, Pluto, Loopo, Graphite.
15
//
16
//===----------------------------------------------------------------------===//
17
18
#ifndef POLLY_SCOP_INFO_H
19
#define POLLY_SCOP_INFO_H
20
21
#include "polly/ScopDetection.h"
22
#include "polly/Support/SCEVAffinator.h"
23
24
#include "llvm/ADT/MapVector.h"
25
#include "llvm/Analysis/RegionPass.h"
26
#include "isl/aff.h"
27
#include "isl/ctx.h"
28
#include "isl/set.h"
29
30
#include <deque>
31
#include <forward_list>
32
33
using namespace llvm;
34
35
namespace llvm {
36
class AssumptionCache;
37
class Loop;
38
class LoopInfo;
39
class PHINode;
40
class ScalarEvolution;
41
class SCEV;
42
class SCEVAddRecExpr;
43
class Type;
44
} // namespace llvm
45
46
struct isl_ctx;
47
struct isl_map;
48
struct isl_basic_map;
49
struct isl_id;
50
struct isl_set;
51
struct isl_union_set;
52
struct isl_union_map;
53
struct isl_space;
54
struct isl_ast_build;
55
struct isl_constraint;
56
struct isl_pw_aff;
57
struct isl_pw_multi_aff;
58
struct isl_schedule;
59
60
namespace polly {
61
62
class MemoryAccess;
63
class Scop;
64
class ScopStmt;
65
class ScopBuilder;
66
67
//===---------------------------------------------------------------------===//
68
69
/// Enumeration of assumptions Polly can take.
70
enum AssumptionKind {
71
  ALIASING,
72
  INBOUNDS,
73
  WRAPPING,
74
  UNSIGNED,
75
  PROFITABLE,
76
  ERRORBLOCK,
77
  COMPLEXITY,
78
  INFINITELOOP,
79
  INVARIANTLOAD,
80
  DELINEARIZATION,
81
};
82
83
/// Enum to distinguish between assumptions and restrictions.
84
enum AssumptionSign { AS_ASSUMPTION, AS_RESTRICTION };
85
86
/// The different memory kinds used in Polly.
87
///
88
/// We distinguish between arrays and various scalar memory objects. We use
89
/// the term ``array'' to describe memory objects that consist of a set of
90
/// individual data elements arranged in a multi-dimensional grid. A scalar
91
/// memory object describes an individual data element and is used to model
92
/// the definition and uses of llvm::Values.
93
///
94
/// The polyhedral model does traditionally not reason about SSA values. To
95
/// reason about llvm::Values we model them "as if" they were zero-dimensional
96
/// memory objects, even though they were not actually allocated in (main)
97
/// memory.  Memory for such objects is only alloca[ed] at CodeGeneration
98
/// time. To relate the memory slots used during code generation with the
99
/// llvm::Values they belong to the new names for these corresponding stack
100
/// slots are derived by appending suffixes (currently ".s2a" and ".phiops")
101
/// to the name of the original llvm::Value. To describe how def/uses are
102
/// modeled exactly we use these suffixes here as well.
103
///
104
/// There are currently four different kinds of memory objects:
105
enum class MemoryKind {
106
  /// MemoryKind::Array: Models a one or multi-dimensional array
107
  ///
108
  /// A memory object that can be described by a multi-dimensional array.
109
  /// Memory objects of this type are used to model actual multi-dimensional
110
  /// arrays as they exist in LLVM-IR, but they are also used to describe
111
  /// other objects:
112
  ///   - A single data element allocated on the stack using 'alloca' is
113
  ///     modeled as a one-dimensional, single-element array.
114
  ///   - A single data element allocated as a global variable is modeled as
115
  ///     one-dimensional, single-element array.
116
  ///   - Certain multi-dimensional arrays with variable size, which in
117
  ///     LLVM-IR are commonly expressed as a single-dimensional access with a
118
  ///     complicated access function, are modeled as multi-dimensional
119
  ///     memory objects (grep for "delinearization").
120
  Array,
121
122
  /// MemoryKind::Value: Models an llvm::Value
123
  ///
124
  /// Memory objects of type MemoryKind::Value are used to model the data flow
125
  /// induced by llvm::Values. For each llvm::Value that is used across
126
  /// BasicBocks one ScopArrayInfo object is created. A single memory WRITE
127
  /// stores the llvm::Value at its definition into the memory object and at
128
  /// each use of the llvm::Value (ignoring trivial intra-block uses) a
129
  /// corresponding READ is added. For instance, the use/def chain of a
130
  /// llvm::Value %V depicted below
131
  ///              ______________________
132
  ///              |DefBB:              |
133
  ///              |  %V = float op ... |
134
  ///              ----------------------
135
  ///               |                  |
136
  /// _________________               _________________
137
  /// |UseBB1:        |               |UseBB2:        |
138
  /// |  use float %V |               |  use float %V |
139
  /// -----------------               -----------------
140
  ///
141
  /// is modeled as if the following memory accesses occured:
142
  ///
143
  ///                        __________________________
144
  ///                        |entry:                  |
145
  ///                        |  %V.s2a = alloca float |
146
  ///                        --------------------------
147
  ///                                     |
148
  ///                    ___________________________________
149
  ///                    |DefBB:                           |
150
  ///                    |  store %float %V, float* %V.s2a |
151
  ///                    -----------------------------------
152
  ///                           |                   |
153
  /// ____________________________________ ___________________________________
154
  /// |UseBB1:                           | |UseBB2:                          |
155
  /// |  %V.reload1 = load float* %V.s2a | |  %V.reload2 = load float* %V.s2a|
156
  /// |  use float %V.reload1            | |  use float %V.reload2           |
157
  /// ------------------------------------ -----------------------------------
158
  ///
159
  Value,
160
161
  /// MemoryKind::PHI: Models PHI nodes within the SCoP
162
  ///
163
  /// Besides the MemoryKind::Value memory object used to model the normal
164
  /// llvm::Value dependences described above, PHI nodes require an additional
165
  /// memory object of type MemoryKind::PHI to describe the forwarding of values
166
  /// to
167
  /// the PHI node.
168
  ///
169
  /// As an example, a PHIInst instructions
170
  ///
171
  /// %PHI = phi float [ %Val1, %IncomingBlock1 ], [ %Val2, %IncomingBlock2 ]
172
  ///
173
  /// is modeled as if the accesses occured this way:
174
  ///
175
  ///                    _______________________________
176
  ///                    |entry:                       |
177
  ///                    |  %PHI.phiops = alloca float |
178
  ///                    -------------------------------
179
  ///                           |              |
180
  /// __________________________________  __________________________________
181
  /// |IncomingBlock1:                 |  |IncomingBlock2:                 |
182
  /// |  ...                           |  |  ...                           |
183
  /// |  store float %Val1 %PHI.phiops |  |  store float %Val2 %PHI.phiops |
184
  /// |  br label % JoinBlock          |  |  br label %JoinBlock           |
185
  /// ----------------------------------  ----------------------------------
186
  ///                             \            /
187
  ///                              \          /
188
  ///               _________________________________________
189
  ///               |JoinBlock:                             |
190
  ///               |  %PHI = load float, float* PHI.phiops |
191
  ///               -----------------------------------------
192
  ///
193
  /// Note that there can also be a scalar write access for %PHI if used in a
194
  /// different BasicBlock, i.e. there can be a memory object %PHI.phiops as
195
  /// well as a memory object %PHI.s2a.
196
  PHI,
197
198
  /// MemoryKind::ExitPHI: Models PHI nodes in the SCoP's exit block
199
  ///
200
  /// For PHI nodes in the Scop's exit block a special memory object kind is
201
  /// used. The modeling used is identical to MemoryKind::PHI, with the
202
  /// exception
203
  /// that there are no READs from these memory objects. The PHINode's
204
  /// llvm::Value is treated as a value escaping the SCoP. WRITE accesses
205
  /// write directly to the escaping value's ".s2a" alloca.
206
  ExitPHI
207
};
208
209
/// Maps from a loop to the affine function expressing its backedge taken count.
210
/// The backedge taken count already enough to express iteration domain as we
211
/// only allow loops with canonical induction variable.
212
/// A canonical induction variable is:
213
/// an integer recurrence that starts at 0 and increments by one each time
214
/// through the loop.
215
typedef std::map<const Loop *, const SCEV *> LoopBoundMapType;
216
217
typedef std::vector<std::unique_ptr<MemoryAccess>> AccFuncVector;
218
219
/// A class to store information about arrays in the SCoP.
220
///
221
/// Objects are accessible via the ScoP, MemoryAccess or the id associated with
222
/// the MemoryAccess access function.
223
///
224
class ScopArrayInfo {
225
public:
226
  /// Construct a ScopArrayInfo object.
227
  ///
228
  /// @param BasePtr        The array base pointer.
229
  /// @param ElementType    The type of the elements stored in the array.
230
  /// @param IslCtx         The isl context used to create the base pointer id.
231
  /// @param DimensionSizes A vector containing the size of each dimension.
232
  /// @param Kind           The kind of the array object.
233
  /// @param DL             The data layout of the module.
234
  /// @param S              The scop this array object belongs to.
235
  /// @param BaseName       The optional name of this memory reference.
236
  ScopArrayInfo(Value *BasePtr, Type *ElementType, isl_ctx *IslCtx,
237
                ArrayRef<const SCEV *> DimensionSizes, MemoryKind Kind,
238
                const DataLayout &DL, Scop *S, const char *BaseName = nullptr);
239
240
  ///  Update the element type of the ScopArrayInfo object.
241
  ///
242
  ///  Memory accesses referencing this ScopArrayInfo object may use
243
  ///  different element sizes. This function ensures the canonical element type
244
  ///  stored is small enough to model accesses to the current element type as
245
  ///  well as to @p NewElementType.
246
  ///
247
  ///  @param NewElementType An element type that is used to access this array.
248
  void updateElementType(Type *NewElementType);
249
250
  ///  Update the sizes of the ScopArrayInfo object.
251
  ///
252
  ///  A ScopArrayInfo object may be created without all outer dimensions being
253
  ///  available. This function is called when new memory accesses are added for
254
  ///  this ScopArrayInfo object. It verifies that sizes are compatible and adds
255
  ///  additional outer array dimensions, if needed.
256
  ///
257
  ///  @param Sizes       A vector of array sizes where the rightmost array
258
  ///                     sizes need to match the innermost array sizes already
259
  ///                     defined in SAI.
260
  ///  @param CheckConsistency Update sizes, even if new sizes are inconsistent
261
  ///                          with old sizes
262
  bool updateSizes(ArrayRef<const SCEV *> Sizes, bool CheckConsistency = true);
263
264
  /// Destructor to free the isl id of the base pointer.
265
  ~ScopArrayInfo();
266
267
  /// Set the base pointer to @p BP.
268
5
  void setBasePtr(Value *BP) { BasePtr = BP; }
269
270
  /// Return the base pointer.
271
4.56k
  Value *getBasePtr() const { return BasePtr; }
272
273
  /// For indirect accesses return the origin SAI of the BP, else null.
274
2
  const ScopArrayInfo *getBasePtrOriginSAI() const { return BasePtrOriginSAI; }
275
276
  /// The set of derived indirect SAIs for this origin SAI.
277
109
  const SmallSetVector<ScopArrayInfo *, 2> &getDerivedSAIs() const {
278
109
    return DerivedSAIs;
279
109
  }
280
281
  /// Return the number of dimensions.
282
13.6k
  unsigned getNumberOfDimensions() const {
283
13.6k
    if (
Kind == MemoryKind::PHI || 13.6k
Kind == MemoryKind::ExitPHI12.8k
||
284
12.6k
        Kind == MemoryKind::Value)
285
2.23k
      return 0;
286
11.3k
    return DimensionSizes.size();
287
13.6k
  }
288
289
  /// Return the size of dimension @p dim as SCEV*.
290
  //
291
  //  Scalars do not have array dimensions and the first dimension of
292
  //  a (possibly multi-dimensional) array also does not carry any size
293
  //  information, in case the array is not newly created.
294
1.57k
  const SCEV *getDimensionSize(unsigned Dim) const {
295
1.57k
    assert(Dim < getNumberOfDimensions() && "Invalid dimension");
296
1.57k
    return DimensionSizes[Dim];
297
1.57k
  }
298
299
  /// Return the size of dimension @p dim as isl_pw_aff.
300
  //
301
  //  Scalars do not have array dimensions and the first dimension of
302
  //  a (possibly multi-dimensional) array also does not carry any size
303
  //  information, in case the array is not newly created.
304
680
  __isl_give isl_pw_aff *getDimensionSizePw(unsigned Dim) const {
305
680
    assert(Dim < getNumberOfDimensions() && "Invalid dimension");
306
680
    return isl_pw_aff_copy(DimensionSizesPw[Dim]);
307
680
  }
308
309
  /// Get the canonical element type of this array.
310
  ///
311
  /// @returns The canonical element type of this array.
312
2.53k
  Type *getElementType() const { return ElementType; }
313
314
  /// Get element size in bytes.
315
  int getElemSizeInBytes() const;
316
317
  /// Get the name of this memory reference.
318
  std::string getName() const;
319
320
  /// Return the isl id for the base pointer.
321
  __isl_give isl_id *getBasePtrId() const;
322
323
  /// Return what kind of memory this represents.
324
752
  MemoryKind getKind() const { return Kind; }
325
326
  /// Is this array info modeling an llvm::Value?
327
48
  bool isValueKind() const { return Kind == MemoryKind::Value; }
328
329
  /// Is this array info modeling special PHI node memory?
330
  ///
331
  /// During code generation of PHI nodes, there is a need for two kinds of
332
  /// virtual storage. The normal one as it is used for all scalar dependences,
333
  /// where the result of the PHI node is stored and later loaded from as well
334
  /// as a second one where the incoming values of the PHI nodes are stored
335
  /// into and reloaded when the PHI is executed. As both memories use the
336
  /// original PHI node as virtual base pointer, we have this additional
337
  /// attribute to distinguish the PHI node specific array modeling from the
338
  /// normal scalar array modeling.
339
410
  bool isPHIKind() const { return Kind == MemoryKind::PHI; }
340
341
  /// Is this array info modeling an MemoryKind::ExitPHI?
342
117
  bool isExitPHIKind() const { return Kind == MemoryKind::ExitPHI; }
343
344
  /// Is this array info modeling an array?
345
20
  bool isArrayKind() const { return Kind == MemoryKind::Array; }
346
347
  /// Dump a readable representation to stderr.
348
  void dump() const;
349
350
  /// Print a readable representation to @p OS.
351
  ///
352
  /// @param SizeAsPwAff Print the size as isl_pw_aff
353
  void print(raw_ostream &OS, bool SizeAsPwAff = false) const;
354
355
  /// Access the ScopArrayInfo associated with an access function.
356
  static const ScopArrayInfo *
357
  getFromAccessFunction(__isl_keep isl_pw_multi_aff *PMA);
358
359
  /// Access the ScopArrayInfo associated with an isl Id.
360
  static const ScopArrayInfo *getFromId(__isl_take isl_id *Id);
361
362
  /// Get the space of this array access.
363
  __isl_give isl_space *getSpace() const;
364
365
  /// If the array is read only
366
  bool isReadOnly();
367
368
private:
369
71
  void addDerivedSAI(ScopArrayInfo *DerivedSAI) {
370
71
    DerivedSAIs.insert(DerivedSAI);
371
71
  }
372
373
  /// For indirect accesses this is the SAI of the BP origin.
374
  const ScopArrayInfo *BasePtrOriginSAI;
375
376
  /// For origin SAIs the set of derived indirect SAIs.
377
  SmallSetVector<ScopArrayInfo *, 2> DerivedSAIs;
378
379
  /// The base pointer.
380
  AssertingVH<Value> BasePtr;
381
382
  /// The canonical element type of this array.
383
  ///
384
  /// The canonical element type describes the minimal accessible element in
385
  /// this array. Not all elements accessed, need to be of the very same type,
386
  /// but the allocation size of the type of the elements loaded/stored from/to
387
  /// this array needs to be a multiple of the allocation size of the canonical
388
  /// type.
389
  Type *ElementType;
390
391
  /// The isl id for the base pointer.
392
  isl_id *Id;
393
394
  /// The sizes of each dimension as SCEV*.
395
  SmallVector<const SCEV *, 4> DimensionSizes;
396
397
  /// The sizes of each dimension as isl_pw_aff.
398
  SmallVector<isl_pw_aff *, 4> DimensionSizesPw;
399
400
  /// The type of this scop array info object.
401
  ///
402
  /// We distinguish between SCALAR, PHI and ARRAY objects.
403
  MemoryKind Kind;
404
405
  /// The data layout of the module.
406
  const DataLayout &DL;
407
408
  /// The scop this SAI object belongs to.
409
  Scop &S;
410
};
411
412
/// Represent memory accesses in statements.
413
class MemoryAccess {
414
  friend class Scop;
415
  friend class ScopStmt;
416
417
public:
418
  /// The access type of a memory access
419
  ///
420
  /// There are three kind of access types:
421
  ///
422
  /// * A read access
423
  ///
424
  /// A certain set of memory locations are read and may be used for internal
425
  /// calculations.
426
  ///
427
  /// * A must-write access
428
  ///
429
  /// A certain set of memory locations is definitely written. The old value is
430
  /// replaced by a newly calculated value. The old value is not read or used at
431
  /// all.
432
  ///
433
  /// * A may-write access
434
  ///
435
  /// A certain set of memory locations may be written. The memory location may
436
  /// contain a new value if there is actually a write or the old value may
437
  /// remain, if no write happens.
438
  enum AccessType {
439
    READ = 0x1,
440
    MUST_WRITE = 0x2,
441
    MAY_WRITE = 0x3,
442
  };
443
444
  /// Reduction access type
445
  ///
446
  /// Commutative and associative binary operations suitable for reductions
447
  enum ReductionType {
448
    RT_NONE, ///< Indicate no reduction at all
449
    RT_ADD,  ///< Addition
450
    RT_MUL,  ///< Multiplication
451
    RT_BOR,  ///< Bitwise Or
452
    RT_BXOR, ///< Bitwise XOr
453
    RT_BAND, ///< Bitwise And
454
  };
455
456
private:
457
  MemoryAccess(const MemoryAccess &) = delete;
458
  const MemoryAccess &operator=(const MemoryAccess &) = delete;
459
460
  /// A unique identifier for this memory access.
461
  ///
462
  /// The identifier is unique between all memory accesses belonging to the same
463
  /// scop statement.
464
  isl_id *Id;
465
466
  /// What is modeled by this MemoryAccess.
467
  /// @see MemoryKind
468
  MemoryKind Kind;
469
470
  /// Whether it a reading or writing access, and if writing, whether it
471
  /// is conditional (MAY_WRITE).
472
  enum AccessType AccType;
473
474
  /// Reduction type for reduction like accesses, RT_NONE otherwise
475
  ///
476
  /// An access is reduction like if it is part of a load-store chain in which
477
  /// both access the same memory location (use the same LLVM-IR value
478
  /// as pointer reference). Furthermore, between the load and the store there
479
  /// is exactly one binary operator which is known to be associative and
480
  /// commutative.
481
  ///
482
  /// TODO:
483
  ///
484
  /// We can later lift the constraint that the same LLVM-IR value defines the
485
  /// memory location to handle scops such as the following:
486
  ///
487
  ///    for i
488
  ///      for j
489
  ///        sum[i+j] = sum[i] + 3;
490
  ///
491
  /// Here not all iterations access the same memory location, but iterations
492
  /// for which j = 0 holds do. After lifting the equality check in ScopBuilder,
493
  /// subsequent transformations do not only need check if a statement is
494
  /// reduction like, but they also need to verify that that the reduction
495
  /// property is only exploited for statement instances that load from and
496
  /// store to the same data location. Doing so at dependence analysis time
497
  /// could allow us to handle the above example.
498
  ReductionType RedType = RT_NONE;
499
500
  /// Parent ScopStmt of this access.
501
  ScopStmt *Statement;
502
503
  /// The domain under which this access is not modeled precisely.
504
  ///
505
  /// The invalid domain for an access describes all parameter combinations
506
  /// under which the statement looks to be executed but is in fact not because
507
  /// some assumption/restriction makes the access invalid.
508
  isl_set *InvalidDomain;
509
510
  // Properties describing the accessed array.
511
  // TODO: It might be possible to move them to ScopArrayInfo.
512
  // @{
513
514
  /// The base address (e.g., A for A[i+j]).
515
  ///
516
  /// The #BaseAddr of a memory access of kind MemoryKind::Array is the base
517
  /// pointer of the memory access.
518
  /// The #BaseAddr of a memory access of kind MemoryKind::PHI or
519
  /// MemoryKind::ExitPHI is the PHI node itself.
520
  /// The #BaseAddr of a memory access of kind MemoryKind::Value is the
521
  /// instruction defining the value.
522
  AssertingVH<Value> BaseAddr;
523
524
  /// An unique name of the accessed array.
525
  std::string BaseName;
526
527
  /// Type a single array element wrt. this access.
528
  Type *ElementType;
529
530
  /// Size of each dimension of the accessed array.
531
  SmallVector<const SCEV *, 4> Sizes;
532
  // @}
533
534
  // Properties describing the accessed element.
535
  // @{
536
537
  /// The access instruction of this memory access.
538
  ///
539
  /// For memory accesses of kind MemoryKind::Array the access instruction is
540
  /// the Load or Store instruction performing the access.
541
  ///
542
  /// For memory accesses of kind MemoryKind::PHI or MemoryKind::ExitPHI the
543
  /// access instruction of a load access is the PHI instruction. The access
544
  /// instruction of a PHI-store is the incoming's block's terminator
545
  /// instruction.
546
  ///
547
  /// For memory accesses of kind MemoryKind::Value the access instruction of a
548
  /// load access is nullptr because generally there can be multiple
549
  /// instructions in the statement using the same llvm::Value. The access
550
  /// instruction of a write access is the instruction that defines the
551
  /// llvm::Value.
552
  Instruction *AccessInstruction;
553
554
  /// Incoming block and value of a PHINode.
555
  SmallVector<std::pair<BasicBlock *, Value *>, 4> Incoming;
556
557
  /// The value associated with this memory access.
558
  ///
559
  ///  - For array memory accesses (MemoryKind::Array) it is the loaded result
560
  ///    or the stored value. If the access instruction is a memory intrinsic it
561
  ///    the access value is also the memory intrinsic.
562
  ///  - For accesses of kind MemoryKind::Value it is the access instruction
563
  ///    itself.
564
  ///  - For accesses of kind MemoryKind::PHI or MemoryKind::ExitPHI it is the
565
  ///    PHI node itself (for both, READ and WRITE accesses).
566
  ///
567
  AssertingVH<Value> AccessValue;
568
569
  /// Are all the subscripts affine expression?
570
  bool IsAffine;
571
572
  /// Subscript expression for each dimension.
573
  SmallVector<const SCEV *, 4> Subscripts;
574
575
  /// Relation from statement instances to the accessed array elements.
576
  ///
577
  /// In the common case this relation is a function that maps a set of loop
578
  /// indices to the memory address from which a value is loaded/stored:
579
  ///
580
  ///      for i
581
  ///        for j
582
  ///    S:     A[i + 3 j] = ...
583
  ///
584
  ///    => { S[i,j] -> A[i + 3j] }
585
  ///
586
  /// In case the exact access function is not known, the access relation may
587
  /// also be a one to all mapping { S[i,j] -> A[o] } describing that any
588
  /// element accessible through A might be accessed.
589
  ///
590
  /// In case of an access to a larger element belonging to an array that also
591
  /// contains smaller elements, the access relation models the larger access
592
  /// with multiple smaller accesses of the size of the minimal array element
593
  /// type:
594
  ///
595
  ///      short *A;
596
  ///
597
  ///      for i
598
  ///    S:     A[i] = *((double*)&A[4 * i]);
599
  ///
600
  ///    => { S[i] -> A[i]; S[i] -> A[o] : 4i <= o <= 4i + 3 }
601
  isl_map *AccessRelation;
602
603
  /// Updated access relation read from JSCOP file.
604
  isl_map *NewAccessRelation;
605
  // @}
606
607
  __isl_give isl_basic_map *createBasicAccessMap(ScopStmt *Statement);
608
609
  void assumeNoOutOfBound();
610
611
  /// Compute bounds on an over approximated  access relation.
612
  ///
613
  /// @param ElementSize The size of one element accessed.
614
  void computeBoundsOnAccessRelation(unsigned ElementSize);
615
616
  /// Get the original access function as read from IR.
617
  __isl_give isl_map *getOriginalAccessRelation() const;
618
619
  /// Return the space in which the access relation lives in.
620
  __isl_give isl_space *getOriginalAccessRelationSpace() const;
621
622
  /// Get the new access function imported or set by a pass
623
  __isl_give isl_map *getNewAccessRelation() const;
624
625
  /// Fold the memory access to consider parameteric offsets
626
  ///
627
  /// To recover memory accesses with array size parameters in the subscript
628
  /// expression we post-process the delinearization results.
629
  ///
630
  /// We would normally recover from an access A[exp0(i) * N + exp1(i)] into an
631
  /// array A[][N] the 2D access A[exp0(i)][exp1(i)]. However, another valid
632
  /// delinearization is A[exp0(i) - 1][exp1(i) + N] which - depending on the
633
  /// range of exp1(i) - may be preferrable. Specifically, for cases where we
634
  /// know exp1(i) is negative, we want to choose the latter expression.
635
  ///
636
  /// As we commonly do not have any information about the range of exp1(i),
637
  /// we do not choose one of the two options, but instead create a piecewise
638
  /// access function that adds the (-1, N) offsets as soon as exp1(i) becomes
639
  /// negative. For a 2D array such an access function is created by applying
640
  /// the piecewise map:
641
  ///
642
  /// [i,j] -> [i, j] :      j >= 0
643
  /// [i,j] -> [i-1, j+N] :  j <  0
644
  ///
645
  /// We can generalize this mapping to arbitrary dimensions by applying this
646
  /// piecewise mapping pairwise from the rightmost to the leftmost access
647
  /// dimension. It would also be possible to cover a wider range by introducing
648
  /// more cases and adding multiple of Ns to these cases. However, this has
649
  /// not yet been necessary.
650
  /// The introduction of different cases necessarily complicates the memory
651
  /// access function, but cases that can be statically proven to not happen
652
  /// will be eliminated later on.
653
  void foldAccessRelation();
654
655
  /// Create the access relation for the underlying memory intrinsic.
656
  void buildMemIntrinsicAccessRelation();
657
658
  /// Assemble the access relation from all available information.
659
  ///
660
  /// In particular, used the information passes in the constructor and the
661
  /// parent ScopStmt set by setStatment().
662
  ///
663
  /// @param SAI Info object for the accessed array.
664
  void buildAccessRelation(const ScopArrayInfo *SAI);
665
666
  /// Carry index overflows of dimensions with constant size to the next higher
667
  /// dimension.
668
  ///
669
  /// For dimensions that have constant size, modulo the index by the size and
670
  /// add up the carry (floored division) to the next higher dimension. This is
671
  /// how overflow is defined in row-major order.
672
  /// It happens e.g. when ScalarEvolution computes the offset to the base
673
  /// pointer and would algebraically sum up all lower dimensions' indices of
674
  /// constant size.
675
  ///
676
  /// Example:
677
  ///   float (*A)[4];
678
  ///   A[1][6] -> A[2][2]
679
  void wrapConstantDimensions();
680
681
public:
682
  /// Create a new MemoryAccess.
683
  ///
684
  /// @param Stmt       The parent statement.
685
  /// @param AccessInst The instruction doing the access.
686
  /// @param BaseAddr   The accessed array's address.
687
  /// @param ElemType   The type of the accessed array elements.
688
  /// @param AccType    Whether read or write access.
689
  /// @param IsAffine   Whether the subscripts are affine expressions.
690
  /// @param Kind       The kind of memory accessed.
691
  /// @param Subscripts Subscipt expressions
692
  /// @param Sizes      Dimension lengths of the accessed array.
693
  /// @param BaseName   Name of the acessed array.
694
  MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, AccessType AccType,
695
               Value *BaseAddress, Type *ElemType, bool Affine,
696
               ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
697
               Value *AccessValue, MemoryKind Kind, StringRef BaseName);
698
699
  /// Create a new MemoryAccess that corresponds to @p AccRel.
700
  ///
701
  /// Along with @p Stmt and @p AccType it uses information about dimension
702
  /// lengths of the accessed array, the type of the accessed array elements,
703
  /// the name of the accessed array that is derived from the object accessible
704
  /// via @p AccRel.
705
  ///
706
  /// @param Stmt       The parent statement.
707
  /// @param AccType    Whether read or write access.
708
  /// @param AccRel     The access relation that describes the memory access.
709
  MemoryAccess(ScopStmt *Stmt, AccessType AccType, __isl_take isl_map *AccRel);
710
711
  ~MemoryAccess();
712
713
  /// Add a new incoming block/value pairs for this PHI/ExitPHI access.
714
  ///
715
  /// @param IncomingBlock The PHI's incoming block.
716
  /// @param IncomingValue The value when reacing the PHI from the @p
717
  ///                      IncomingBlock.
718
336
  void addIncoming(BasicBlock *IncomingBlock, Value *IncomingValue) {
719
336
    assert(!isRead());
720
336
    assert(isAnyPHIKind());
721
336
    Incoming.emplace_back(std::make_pair(IncomingBlock, IncomingValue));
722
336
  }
723
724
  /// Return the list of possible PHI/ExitPHI values.
725
  ///
726
  /// After code generation moves some PHIs around during region simplification,
727
  /// we cannot reliably locate the original PHI node and its incoming values
728
  /// anymore. For this reason we remember these explicitly for all PHI-kind
729
  /// accesses.
730
77
  ArrayRef<std::pair<BasicBlock *, Value *>> getIncoming() const {
731
77
    assert(isAnyPHIKind());
732
77
    return Incoming;
733
77
  }
734
735
  /// Get the type of a memory access.
736
0
  enum AccessType getType() { return AccType; }
737
738
  /// Is this a reduction like access?
739
2.30k
  bool isReductionLike() const { return RedType != RT_NONE; }
740
741
  /// Is this a read memory access?
742
13.3k
  bool isRead() const { return AccType == MemoryAccess::READ; }
743
744
  /// Is this a must-write memory access?
745
3.03k
  bool isMustWrite() const { return AccType == MemoryAccess::MUST_WRITE; }
746
747
  /// Is this a may-write memory access?
748
2.59k
  bool isMayWrite() const { return AccType == MemoryAccess::MAY_WRITE; }
749
750
  /// Is this a write memory access?
751
2.98k
  bool isWrite() const 
{ return isMustWrite() || 2.98k
isMayWrite()1.69k
; }
752
753
  /// Is this a memory intrinsic access (memcpy, memset, memmove)?
754
512
  bool isMemoryIntrinsic() const {
755
512
    return isa<MemIntrinsic>(getAccessInstruction());
756
512
  }
757
758
  /// Check if a new access relation was imported or set by a pass.
759
15.3k
  bool hasNewAccessRelation() const { return NewAccessRelation; }
760
761
  /// Return the newest access relation of this access.
762
  ///
763
  /// There are two possibilities:
764
  ///   1) The original access relation read from the LLVM-IR.
765
  ///   2) A new access relation imported from a json file or set by another
766
  ///      pass (e.g., for privatization).
767
  ///
768
  /// As 2) is by construction "newer" than 1) we return the new access
769
  /// relation if present.
770
  ///
771
12.1k
  __isl_give isl_map *getLatestAccessRelation() const {
772
77
    return hasNewAccessRelation() ? getNewAccessRelation()
773
12.0k
                                  : getOriginalAccessRelation();
774
12.1k
  }
775
776
  /// Old name of getLatestAccessRelation().
777
12.0k
  __isl_give isl_map *getAccessRelation() const {
778
12.0k
    return getLatestAccessRelation();
779
12.0k
  }
780
781
  /// Get an isl map describing the memory address accessed.
782
  ///
783
  /// In most cases the memory address accessed is well described by the access
784
  /// relation obtained with getAccessRelation. However, in case of arrays
785
  /// accessed with types of different size the access relation maps one access
786
  /// to multiple smaller address locations. This method returns an isl map that
787
  /// relates each dynamic statement instance to the unique memory location
788
  /// that is loaded from / stored to.
789
  ///
790
  /// For an access relation { S[i] -> A[o] : 4i <= o <= 4i + 3 } this method
791
  /// will return the address function { S[i] -> A[4i] }.
792
  ///
793
  /// @returns The address function for this memory access.
794
  __isl_give isl_map *getAddressFunction() const;
795
796
  /// Return the access relation after the schedule was applied.
797
  __isl_give isl_pw_multi_aff *
798
  applyScheduleToAccessRelation(__isl_take isl_union_map *Schedule) const;
799
800
  /// Get an isl string representing the access function read from IR.
801
  std::string getOriginalAccessRelationStr() const;
802
803
  /// Get an isl string representing a new access function, if available.
804
  std::string getNewAccessRelationStr() const;
805
806
  /// Get the base address of this access (e.g. A for A[i+j]) when
807
  /// detected.
808
5.18k
  Value *getOriginalBaseAddr() const {
809
5.18k
    assert(!getOriginalScopArrayInfo() /* may noy yet be initialized */ ||
810
5.18k
           getOriginalScopArrayInfo()->getBasePtr() == BaseAddr);
811
5.18k
    return BaseAddr;
812
5.18k
  }
813
814
  /// Get the base address of this access (e.g. A for A[i+j]) after a
815
  /// potential change by setNewAccessRelation().
816
11
  Value *getLatestBaseAddr() const {
817
11
    return getLatestScopArrayInfo()->getBasePtr();
818
11
  }
819
820
  /// Old name for getOriginalBaseAddr().
821
61
  Value *getBaseAddr() const { return getOriginalBaseAddr(); }
822
823
  /// Get the detection-time base array isl_id for this access.
824
  __isl_give isl_id *getOriginalArrayId() const;
825
826
  /// Get the base array isl_id for this access, modifiable through
827
  /// setNewAccessRelation().
828
  __isl_give isl_id *getLatestArrayId() const;
829
830
  /// Old name of getOriginalArrayId().
831
14.2k
  __isl_give isl_id *getArrayId() const { return getOriginalArrayId(); }
832
833
  /// Get the detection-time ScopArrayInfo object for the base address.
834
  const ScopArrayInfo *getOriginalScopArrayInfo() const;
835
836
  /// Get the ScopArrayInfo object for the base address, or the one set
837
  /// by setNewAccessRelation().
838
  const ScopArrayInfo *getLatestScopArrayInfo() const;
839
840
  /// Legacy name of getOriginalScopArrayInfo().
841
14.2k
  const ScopArrayInfo *getScopArrayInfo() const {
842
14.2k
    return getOriginalScopArrayInfo();
843
14.2k
  }
844
845
  /// Return a string representation of the access's reduction type.
846
  const std::string getReductionOperatorStr() const;
847
848
  /// Return a string representation of the reduction type @p RT.
849
  static const std::string getReductionOperatorStr(ReductionType RT);
850
851
0
  const std::string &getBaseName() const { return BaseName; }
852
853
  /// Return the element type of the accessed array wrt. this access.
854
7.07k
  Type *getElementType() const { return ElementType; }
855
856
  /// Return the access value of this memory access.
857
1.61k
  Value *getAccessValue() const { return AccessValue; }
858
859
  /// Return the access instruction of this memory access.
860
32.2k
  Instruction *getAccessInstruction() const { return AccessInstruction; }
861
862
  /// Return the number of access function subscript.
863
5
  unsigned getNumSubscripts() const { return Subscripts.size(); }
864
865
  /// Return the access function subscript in the dimension @p Dim.
866
2.32k
  const SCEV *getSubscript(unsigned Dim) const { return Subscripts[Dim]; }
867
868
  /// Compute the isl representation for the SCEV @p E wrt. this access.
869
  ///
870
  /// Note that this function will also adjust the invalid context accordingly.
871
  __isl_give isl_pw_aff *getPwAff(const SCEV *E);
872
873
  /// Get the invalid domain for this access.
874
342
  __isl_give isl_set *getInvalidDomain() const {
875
342
    return isl_set_copy(InvalidDomain);
876
342
  }
877
878
  /// Get the invalid context for this access.
879
342
  __isl_give isl_set *getInvalidContext() const {
880
342
    return isl_set_params(getInvalidDomain());
881
342
  }
882
883
  /// Get the stride of this memory access in the specified Schedule. Schedule
884
  /// is a map from the statement to a schedule where the innermost dimension is
885
  /// the dimension of the innermost loop containing the statement.
886
  __isl_give isl_set *getStride(__isl_take const isl_map *Schedule) const;
887
888
  /// Is the stride of the access equal to a certain width? Schedule is a map
889
  /// from the statement to a schedule where the innermost dimension is the
890
  /// dimension of the innermost loop containing the statement.
891
  bool isStrideX(__isl_take const isl_map *Schedule, int StrideWidth) const;
892
893
  /// Is consecutive memory accessed for a given statement instance set?
894
  /// Schedule is a map from the statement to a schedule where the innermost
895
  /// dimension is the dimension of the innermost loop containing the
896
  /// statement.
897
  bool isStrideOne(__isl_take const isl_map *Schedule) const;
898
899
  /// Is always the same memory accessed for a given statement instance set?
900
  /// Schedule is a map from the statement to a schedule where the innermost
901
  /// dimension is the dimension of the innermost loop containing the
902
  /// statement.
903
  bool isStrideZero(__isl_take const isl_map *Schedule) const;
904
905
  /// Return the kind when this access was first detected.
906
29.3k
  MemoryKind getOriginalKind() const {
907
29.3k
    assert(!getOriginalScopArrayInfo() /* not yet initialized */ ||
908
29.3k
           getOriginalScopArrayInfo()->getKind() == Kind);
909
29.3k
    return Kind;
910
29.3k
  }
911
912
  /// Return the kind considering a potential setNewAccessRelation.
913
752
  MemoryKind getLatestKind() const {
914
752
    return getLatestScopArrayInfo()->getKind();
915
752
  }
916
917
  /// Whether this is an access of an explicit load or store in the IR.
918
10.5k
  bool isOriginalArrayKind() const {
919
10.5k
    return getOriginalKind() == MemoryKind::Array;
920
10.5k
  }
921
922
  /// Whether storage memory is either an custom .s2a/.phiops alloca
923
  /// (false) or an existing pointer into an array (true).
924
686
  bool isLatestArrayKind() const {
925
686
    return getLatestKind() == MemoryKind::Array;
926
686
  }
927
928
  /// Old name of isOriginalArrayKind.
929
9.13k
  bool isArrayKind() const { return isOriginalArrayKind(); }
930
931
  /// Whether this access is an array to a scalar memory object, without
932
  /// considering changes by setNewAccessRelation.
933
  ///
934
  /// Scalar accesses are accesses to MemoryKind::Value, MemoryKind::PHI or
935
  /// MemoryKind::ExitPHI.
936
5.79k
  bool isOriginalScalarKind() const {
937
5.79k
    return getOriginalKind() != MemoryKind::Array;
938
5.79k
  }
939
940
  /// Whether this access is an array to a scalar memory object, also
941
  /// considering changes by setNewAccessRelation.
942
66
  bool isLatestScalarKind() const {
943
66
    return getLatestKind() != MemoryKind::Array;
944
66
  }
945
946
  /// Old name of isOriginalScalarKind.
947
5.79k
  bool isScalarKind() const { return isOriginalScalarKind(); }
948
949
  /// Was this MemoryAccess detected as a scalar dependences?
950
5.05k
  bool isOriginalValueKind() const {
951
5.05k
    return getOriginalKind() == MemoryKind::Value;
952
5.05k
  }
953
954
  /// Is this MemoryAccess currently modeling scalar dependences?
955
0
  bool isLatestValueKind() const {
956
0
    return getLatestKind() == MemoryKind::Value;
957
0
  }
958
959
  /// Old name of isOriginalValueKind().
960
4.76k
  bool isValueKind() const { return isOriginalValueKind(); }
961
962
  /// Was this MemoryAccess detected as a special PHI node access?
963
4.37k
  bool isOriginalPHIKind() const {
964
4.37k
    return getOriginalKind() == MemoryKind::PHI;
965
4.37k
  }
966
967
  /// Is this MemoryAccess modeling special PHI node accesses, also
968
  /// considering a potential change by setNewAccessRelation?
969
0
  bool isLatestPHIKind() const { return getLatestKind() == MemoryKind::PHI; }
970
971
  /// Old name of isOriginalPHIKind.
972
3.52k
  bool isPHIKind() const { return isOriginalPHIKind(); }
973
974
  /// Was this MemoryAccess detected as the accesses of a PHI node in the
975
  /// SCoP's exit block?
976
3.55k
  bool isOriginalExitPHIKind() const {
977
3.55k
    return getOriginalKind() == MemoryKind::ExitPHI;
978
3.55k
  }
979
980
  /// Is this MemoryAccess modeling the accesses of a PHI node in the
981
  /// SCoP's exit block? Can be changed to an array access using
982
  /// setNewAccessRelation().
983
0
  bool isLatestExitPHIKind() const {
984
0
    return getLatestKind() == MemoryKind::ExitPHI;
985
0
  }
986
987
  /// Old name of isOriginalExitPHIKind().
988
3.21k
  bool isExitPHIKind() const { return isOriginalExitPHIKind(); }
989
990
  /// Was this access detected as one of the two PHI types?
991
848
  bool isOriginalAnyPHIKind() const {
992
349
    return isOriginalPHIKind() || isOriginalExitPHIKind();
993
848
  }
994
995
  /// Does this access orginate from one of the two PHI types? Can be
996
  /// changed to an array access using setNewAccessRelation().
997
0
  bool isLatestAnyPHIKind() const {
998
0
    return isLatestPHIKind() || isLatestExitPHIKind();
999
0
  }
1000
1001
  /// Old name of isOriginalAnyPHIKind().
1002
562
  bool isAnyPHIKind() const { return isOriginalAnyPHIKind(); }
1003
1004
  /// Get the statement that contains this memory access.
1005
16.4k
  ScopStmt *getStatement() const { return Statement; }
1006
1007
  /// Get the reduction type of this access
1008
1.55k
  ReductionType getReductionType() const { return RedType; }
1009
1010
  /// Update the original access relation.
1011
  ///
1012
  /// We need to update the original access relation during scop construction,
1013
  /// when unifying the memory accesses that access the same scop array info
1014
  /// object. After the scop has been constructed, the original access relation
1015
  /// should not be changed any more. Instead setNewAccessRelation should
1016
  /// be called.
1017
  void setAccessRelation(__isl_take isl_map *AccessRelation);
1018
1019
  /// Set the updated access relation read from JSCOP file.
1020
  void setNewAccessRelation(__isl_take isl_map *NewAccessRelation);
1021
1022
  /// Mark this a reduction like access
1023
522
  void markAsReductionLike(ReductionType RT) { RedType = RT; }
1024
1025
  /// Align the parameters in the access relation to the scop context
1026
  void realignParams();
1027
1028
  /// Update the dimensionality of the memory access.
1029
  ///
1030
  /// During scop construction some memory accesses may not be constructed with
1031
  /// their full dimensionality, but outer dimensions may have been omitted if
1032
  /// they took the value 'zero'. By updating the dimensionality of the
1033
  /// statement we add additional zero-valued dimensions to match the
1034
  /// dimensionality of the ScopArrayInfo object that belongs to this memory
1035
  /// access.
1036
  void updateDimensionality();
1037
1038
  /// Get identifier for the memory access.
1039
  ///
1040
  /// This identifier is unique for all accesses that belong to the same scop
1041
  /// statement.
1042
  __isl_give isl_id *getId() const;
1043
1044
  /// Print the MemoryAccess.
1045
  ///
1046
  /// @param OS The output stream the MemoryAccess is printed to.
1047
  void print(raw_ostream &OS) const;
1048
1049
  /// Print the MemoryAccess to stderr.
1050
  void dump() const;
1051
1052
  /// Is the memory access affine?
1053
8.15k
  bool isAffine() const { return IsAffine; }
1054
};
1055
1056
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
1057
                              MemoryAccess::ReductionType RT);
1058
1059
/// Ordered list type to hold accesses.
1060
using MemoryAccessList = std::forward_list<MemoryAccess *>;
1061
1062
/// Helper structure for invariant memory accesses.
1063
struct InvariantAccess {
1064
  /// The memory access that is (partially) invariant.
1065
  MemoryAccess *MA;
1066
1067
  /// The context under which the access is not invariant.
1068
  isl_set *NonHoistableCtx;
1069
};
1070
1071
/// Ordered container type to hold invariant accesses.
1072
using InvariantAccessesTy = SmallVector<InvariantAccess, 8>;
1073
1074
/// Type for equivalent invariant accesses and their domain context.
1075
struct InvariantEquivClassTy {
1076
1077
  /// The pointer that identifies this equivalence class
1078
  const SCEV *IdentifyingPointer;
1079
1080
  /// Memory accesses now treated invariant
1081
  ///
1082
  /// These memory accesses access the pointer location that identifies
1083
  /// this equivalence class. They are treated as invariant and hoisted during
1084
  /// code generation.
1085
  MemoryAccessList InvariantAccesses;
1086
1087
  /// The execution context under which the memory location is accessed
1088
  ///
1089
  /// It is the union of the execution domains of the memory accesses in the
1090
  /// InvariantAccesses list.
1091
  isl_set *ExecutionContext;
1092
1093
  /// The type of the invariant access
1094
  ///
1095
  /// It is used to differentiate between differently typed invariant loads from
1096
  /// the same location.
1097
  Type *AccessType;
1098
};
1099
1100
/// Type for invariant accesses equivalence classes.
1101
using InvariantEquivClassesTy = SmallVector<InvariantEquivClassTy, 8>;
1102
1103
/// Statement of the Scop
1104
///
1105
/// A Scop statement represents an instruction in the Scop.
1106
///
1107
/// It is further described by its iteration domain, its schedule and its data
1108
/// accesses.
1109
/// At the moment every statement represents a single basic block of LLVM-IR.
1110
class ScopStmt {
1111
public:
1112
  ScopStmt(const ScopStmt &) = delete;
1113
  const ScopStmt &operator=(const ScopStmt &) = delete;
1114
1115
  /// Create the ScopStmt from a BasicBlock.
1116
  ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop);
1117
1118
  /// Create an overapproximating ScopStmt for the region @p R.
1119
  ScopStmt(Scop &parent, Region &R, Loop *SurroundingLoop);
1120
1121
  /// Create a copy statement.
1122
  ///
1123
  /// @param Stmt       The parent statement.
1124
  /// @param SourceRel  The source location.
1125
  /// @param TargetRel  The target location.
1126
  /// @param Domain     The original domain under which copy statement whould
1127
  ///                   be executed.
1128
  ScopStmt(Scop &parent, __isl_take isl_map *SourceRel,
1129
           __isl_take isl_map *TargetRel, __isl_take isl_set *Domain);
1130
1131
  /// Initialize members after all MemoryAccesses have been added.
1132
  void init(LoopInfo &LI);
1133
1134
private:
1135
  /// Polyhedral description
1136
  //@{
1137
1138
  /// The Scop containing this ScopStmt
1139
  Scop &Parent;
1140
1141
  /// The domain under which this statement is not modeled precisely.
1142
  ///
1143
  /// The invalid domain for a statement describes all parameter combinations
1144
  /// under which the statement looks to be executed but is in fact not because
1145
  /// some assumption/restriction makes the statement/scop invalid.
1146
  isl_set *InvalidDomain;
1147
1148
  /// The iteration domain describes the set of iterations for which this
1149
  /// statement is executed.
1150
  ///
1151
  /// Example:
1152
  ///     for (i = 0; i < 100 + b; ++i)
1153
  ///       for (j = 0; j < i; ++j)
1154
  ///         S(i,j);
1155
  ///
1156
  /// 'S' is executed for different values of i and j. A vector of all
1157
  /// induction variables around S (i, j) is called iteration vector.
1158
  /// The domain describes the set of possible iteration vectors.
1159
  ///
1160
  /// In this case it is:
1161
  ///
1162
  ///     Domain: 0 <= i <= 100 + b
1163
  ///             0 <= j <= i
1164
  ///
1165
  /// A pair of statement and iteration vector (S, (5,3)) is called statement
1166
  /// instance.
1167
  isl_set *Domain;
1168
1169
  /// The memory accesses of this statement.
1170
  ///
1171
  /// The only side effects of a statement are its memory accesses.
1172
  typedef SmallVector<MemoryAccess *, 8> MemoryAccessVec;
1173
  MemoryAccessVec MemAccs;
1174
1175
  /// Mapping from instructions to (scalar) memory accesses.
1176
  DenseMap<const Instruction *, MemoryAccessList> InstructionToAccess;
1177
1178
  /// The set of values defined elsewhere required in this ScopStmt and
1179
  ///        their MemoryKind::Value READ MemoryAccesses.
1180
  DenseMap<Value *, MemoryAccess *> ValueReads;
1181
1182
  /// The set of values defined in this ScopStmt that are required
1183
  ///        elsewhere, mapped to their MemoryKind::Value WRITE MemoryAccesses.
1184
  DenseMap<Instruction *, MemoryAccess *> ValueWrites;
1185
1186
  /// Map from PHI nodes to its incoming value when coming from this
1187
  ///        statement.
1188
  ///
1189
  /// Non-affine subregions can have multiple exiting blocks that are incoming
1190
  /// blocks of the PHI nodes. This map ensures that there is only one write
1191
  /// operation for the complete subregion. A PHI selecting the relevant value
1192
  /// will be inserted.
1193
  DenseMap<PHINode *, MemoryAccess *> PHIWrites;
1194
1195
  //@}
1196
1197
  /// A SCoP statement represents either a basic block (affine/precise case) or
1198
  /// a whole region (non-affine case).
1199
  ///
1200
  /// Only one of the following two members will therefore be set and indicate
1201
  /// which kind of statement this is.
1202
  ///
1203
  ///{
1204
1205
  /// The BasicBlock represented by this statement (in the affine case).
1206
  BasicBlock *BB;
1207
1208
  /// The region represented by this statement (in the non-affine case).
1209
  Region *R;
1210
1211
  ///}
1212
1213
  /// The isl AST build for the new generated AST.
1214
  isl_ast_build *Build;
1215
1216
  SmallVector<Loop *, 4> NestLoops;
1217
1218
  std::string BaseName;
1219
1220
  /// The closest loop that contains this statement.
1221
  Loop *SurroundingLoop;
1222
1223
  /// Build the statement.
1224
  //@{
1225
  void buildDomain();
1226
1227
  /// Fill NestLoops with loops surrounding this statement.
1228
  void collectSurroundingLoops();
1229
1230
  /// Build the access relation of all memory accesses.
1231
  void buildAccessRelations();
1232
1233
  /// Detect and mark reductions in the ScopStmt
1234
  void checkForReductions();
1235
1236
  /// Collect loads which might form a reduction chain with @p StoreMA
1237
  void
1238
  collectCandiateReductionLoads(MemoryAccess *StoreMA,
1239
                                llvm::SmallVectorImpl<MemoryAccess *> &Loads);
1240
  //@}
1241
1242
public:
1243
  ~ScopStmt();
1244
1245
  /// Get an isl_ctx pointer.
1246
  isl_ctx *getIslCtx() const;
1247
1248
  /// Get the iteration domain of this ScopStmt.
1249
  ///
1250
  /// @return The iteration domain of this ScopStmt.
1251
  __isl_give isl_set *getDomain() const;
1252
1253
  /// Get the space of the iteration domain
1254
  ///
1255
  /// @return The space of the iteration domain
1256
  __isl_give isl_space *getDomainSpace() const;
1257
1258
  /// Get the id of the iteration domain space
1259
  ///
1260
  /// @return The id of the iteration domain space
1261
  __isl_give isl_id *getDomainId() const;
1262
1263
  /// Get an isl string representing this domain.
1264
  std::string getDomainStr() const;
1265
1266
  /// Get the schedule function of this ScopStmt.
1267
  ///
1268
  /// @return The schedule function of this ScopStmt, if it does not contain
1269
  /// extension nodes, and nullptr, otherwise.
1270
  __isl_give isl_map *getSchedule() const;
1271
1272
  /// Get an isl string representing this schedule.
1273
  ///
1274
  /// @return An isl string representing this schedule, if it does not contain
1275
  /// extension nodes, and an empty string, otherwise.
1276
  std::string getScheduleStr() const;
1277
1278
  /// Get the invalid domain for this statement.
1279
8.61k
  __isl_give isl_set *getInvalidDomain() const {
1280
8.61k
    return isl_set_copy(InvalidDomain);
1281
8.61k
  }
1282
1283
  /// Get the invalid context for this statement.
1284
206
  __isl_give isl_set *getInvalidContext() const {
1285
206
    return isl_set_params(getInvalidDomain());
1286
206
  }
1287
1288
  /// Set the invalid context for this statement to @p ID.
1289
  void setInvalidDomain(__isl_take isl_set *ID);
1290
1291
  /// Get the BasicBlock represented by this ScopStmt (if any).
1292
  ///
1293
  /// @return The BasicBlock represented by this ScopStmt, or null if the
1294
  ///         statement represents a region.
1295
23.5k
  BasicBlock *getBasicBlock() const { return BB; }
1296
1297
  /// Return true if this statement represents a single basic block.
1298
29.3k
  bool isBlockStmt() const { return BB != nullptr; }
1299
1300
  /// Return true if this is a copy statement.
1301
709
  bool isCopyStmt() const 
{ return BB == nullptr && 709
R == nullptr73
; }
1302
1303
  /// Get the region represented by this ScopStmt (if any).
1304
  ///
1305
  /// @return The region represented by this ScopStmt, or null if the statement
1306
  ///         represents a basic block.
1307
2.26k
  Region *getRegion() const { return R; }
1308
1309
  /// Return true if this statement represents a whole region.
1310
6.80k
  bool isRegionStmt() const { return R != nullptr; }
1311
1312
  /// Return a BasicBlock from this statement.
1313
  ///
1314
  /// For block statements, it returns the BasicBlock itself. For subregion
1315
  /// statements, return its entry block.
1316
  BasicBlock *getEntryBlock() const;
1317
1318
  /// Return whether @p L is boxed within this statement.
1319
1.53k
  bool contains(const Loop *L) const {
1320
1.53k
    // Block statements never contain loops.
1321
1.53k
    if (isBlockStmt())
1322
1.44k
      return false;
1323
1.53k
1324
99
    return getRegion()->contains(L);
1325
1.53k
  }
1326
1327
  /// Return whether this statement contains @p BB.
1328
12
  bool contains(BasicBlock *BB) const {
1329
12
    if (isCopyStmt())
1330
0
      return false;
1331
12
    
if (12
isBlockStmt()12
)
1332
0
      return BB == getBasicBlock();
1333
12
    return getRegion()->contains(BB);
1334
12
  }
1335
1336
  /// Return the closest innermost loop that contains this statement, but is not
1337
  /// contained in it.
1338
  ///
1339
  /// For block statement, this is just the loop that contains the block. Region
1340
  /// statements can contain boxed loops, so getting the loop of one of the
1341
  /// region's BBs might return such an inner loop. For instance, the region's
1342
  /// entry could be a header of a loop, but the region might extend to BBs
1343
  /// after the loop exit. Similarly, the region might only contain parts of the
1344
  /// loop body and still include the loop header.
1345
  ///
1346
  /// Most of the time the surrounding loop is the top element of #NestLoops,
1347
  /// except when it is empty. In that case it return the loop that the whole
1348
  /// SCoP is contained in. That can be nullptr if there is no such loop.
1349
15.7k
  Loop *getSurroundingLoop() const {
1350
15.7k
    assert(!isCopyStmt() &&
1351
15.7k
           "No surrounding loop for artificially created statements");
1352
15.7k
    return SurroundingLoop;
1353
15.7k
  }
1354
1355
  /// Return true if this statement does not contain any accesses.
1356
5.92k
  bool isEmpty() const { return MemAccs.empty(); }
1357
1358
  /// Return the only array access for @p Inst, if existing.
1359
  ///
1360
  /// @param Inst The instruction for which to look up the access.
1361
  /// @returns The unique array memory access related to Inst or nullptr if
1362
  ///          no array access exists
1363
1.63k
  MemoryAccess *getArrayAccessOrNULLFor(const Instruction *Inst) const {
1364
1.63k
    auto It = InstructionToAccess.find(Inst);
1365
1.63k
    if (It == InstructionToAccess.end())
1366
192
      return nullptr;
1367
1.63k
1368
1.44k
    MemoryAccess *ArrayAccess = nullptr;
1369
1.44k
1370
1.44k
    for (auto Access : It->getSecond()) {
1371
1.44k
      if (!Access->isArrayKind())
1372
0
        continue;
1373
1.44k
1374
1.44k
      assert(!ArrayAccess && "More then one array access for instruction");
1375
1.44k
1376
1.44k
      ArrayAccess = Access;
1377
1.44k
    }
1378
1.44k
1379
1.44k
    return ArrayAccess;
1380
1.63k
  }
1381
1382
  /// Return the only array access for @p Inst.
1383
  ///
1384
  /// @param Inst The instruction for which to look up the access.
1385
  /// @returns The unique array memory access related to Inst.
1386
989
  MemoryAccess &getArrayAccessFor(const Instruction *Inst) const {
1387
989
    MemoryAccess *ArrayAccess = getArrayAccessOrNULLFor(Inst);
1388
989
1389
989
    assert(ArrayAccess && "No array access found for instruction!");
1390
989
    return *ArrayAccess;
1391
989
  }
1392
1393
  /// Return the MemoryAccess that writes the value of an instruction
1394
  ///        defined in this statement, or nullptr if not existing, respectively
1395
  ///        not yet added.
1396
298
  MemoryAccess *lookupValueWriteOf(Instruction *Inst) const {
1397
298
    assert((isRegionStmt() && R->contains(Inst)) ||
1398
298
           (!isRegionStmt() && Inst->getParent() == BB));
1399
298
    return ValueWrites.lookup(Inst);
1400
298
  }
1401
1402
  /// Return the MemoryAccess that reloads a value, or nullptr if not
1403
  ///        existing, respectively not yet added.
1404
273
  MemoryAccess *lookupValueReadOf(Value *Inst) const {
1405
273
    return ValueReads.lookup(Inst);
1406
273
  }
1407
1408
  /// Return the PHI write MemoryAccess for the incoming values from any
1409
  ///        basic block in this ScopStmt, or nullptr if not existing,
1410
  ///        respectively not yet added.
1411
336
  MemoryAccess *lookupPHIWriteOf(PHINode *PHI) const {
1412
336
    assert(isBlockStmt() || R->getExit() == PHI->getParent());
1413
336
    return PHIWrites.lookup(PHI);
1414
336
  }
1415
1416
  /// Add @p Access to this statement's list of accesses.
1417
  void addAccess(MemoryAccess *Access);
1418
1419
  /// Remove a MemoryAccess from this statement.
1420
  ///
1421
  /// Note that scalar accesses that are caused by MA will
1422
  /// be eliminated too.
1423
  void removeMemoryAccess(MemoryAccess *MA);
1424
1425
  /// Remove @p MA from this statement.
1426
  ///
1427
  /// In contrast to removeMemoryAccess(), no other access will be eliminated.
1428
  void removeSingleMemoryAccess(MemoryAccess *MA);
1429
1430
  typedef MemoryAccessVec::iterator iterator;
1431
  typedef MemoryAccessVec::const_iterator const_iterator;
1432
1433
16.4k
  iterator begin() { return MemAccs.begin(); }
1434
16.5k
  iterator end() { return MemAccs.end(); }
1435
40
  const_iterator begin() const { return MemAccs.begin(); }
1436
40
  const_iterator end() const { return MemAccs.end(); }
1437
3.92k
  size_t size() const { return MemAccs.size(); }
1438
1439
  unsigned getNumIterators() const;
1440
1441
27.5k
  Scop *getParent() { return &Parent; }
1442
871
  const Scop *getParent() const { return &Parent; }
1443
1444
  const char *getBaseName() const;
1445
1446
  /// Set the isl AST build.
1447
369
  void setAstBuild(__isl_keep isl_ast_build *B) { Build = B; }
1448
1449
  /// Get the isl AST build.
1450
0
  __isl_keep isl_ast_build *getAstBuild() const { return Build; }
1451
1452
  /// Restrict the domain of the statement.
1453
  ///
1454
  /// @param NewDomain The new statement domain.
1455
  void restrictDomain(__isl_take isl_set *NewDomain);
1456
1457
  /// Compute the isl representation for the SCEV @p E in this stmt.
1458
  ///
1459
  /// @param E           The SCEV that should be translated.
1460
  /// @param NonNegative Flag to indicate the @p E has to be non-negative.
1461
  ///
1462
  /// Note that this function will also adjust the invalid context accordingly.
1463
  __isl_give isl_pw_aff *getPwAff(const SCEV *E, bool NonNegative = false);
1464
1465
  /// Get the loop for a dimension.
1466
  ///
1467
  /// @param Dimension The dimension of the induction variable
1468
  /// @return The loop at a certain dimension.
1469
  Loop *getLoopForDimension(unsigned Dimension) const;
1470
1471
  /// Align the parameters in the statement to the scop context
1472
  void realignParams();
1473
1474
  /// Print the ScopStmt.
1475
  ///
1476
  /// @param OS The output stream the ScopStmt is printed to.
1477
  void print(raw_ostream &OS) const;
1478
1479
  /// Print the ScopStmt to stderr.
1480
  void dump() const;
1481
};
1482
1483
/// Print ScopStmt S to raw_ostream O.
1484
630
static inline raw_ostream &operator<<(raw_ostream &O, const ScopStmt &S) {
1485
630
  S.print(O);
1486
630
  return O;
1487
630
}
Unexecuted instantiation: DependenceInfo.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: DeLICM.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: FlattenSchedule.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: ScheduleOptimizer.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: DeadCodeElimination.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: ScopHelper.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: RegisterPasses.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: SCEVValidator.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: SCEVAffinator.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: JSONExporter.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: Utils.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: IRBuilder.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: CodeGeneration.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: IslNodeBuilder.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: IslExprBuilder.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: IslAst.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: BlockGenerators.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: PruneUnprofitable.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: ScopPass.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: ScopBuilder.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
ScopInfo.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Line
Count
Source
1484
630
static inline raw_ostream &operator<<(raw_ostream &O, const ScopStmt &S) {
1485
630
  S.print(O);
1486
630
  return O;
1487
630
}
Unexecuted instantiation: PolyhedralInfo.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
Unexecuted instantiation: Simplify.cpp:polly::operator<<(llvm::raw_ostream&, polly::ScopStmt const&)
1488
1489
/// Static Control Part
1490
///
1491
/// A Scop is the polyhedral representation of a control flow region detected
1492
/// by the Scop detection. It is generated by translating the LLVM-IR and
1493
/// abstracting its effects.
1494
///
1495
/// A Scop consists of a set of:
1496
///
1497
///   * A set of statements executed in the Scop.
1498
///
1499
///   * A set of global parameters
1500
///   Those parameters are scalar integer values, which are constant during
1501
///   execution.
1502
///
1503
///   * A context
1504
///   This context contains information about the values the parameters
1505
///   can take and relations between different parameters.
1506
class Scop {
1507
public:
1508
  /// Type to represent a pair of minimal/maximal access to an array.
1509
  using MinMaxAccessTy = std::pair<isl_pw_multi_aff *, isl_pw_multi_aff *>;
1510
1511
  /// Vector of minimal/maximal accesses to different arrays.
1512
  using MinMaxVectorTy = SmallVector<MinMaxAccessTy, 4>;
1513
1514
  /// Pair of minimal/maximal access vectors representing
1515
  /// read write and read only accesses
1516
  using MinMaxVectorPairTy = std::pair<MinMaxVectorTy, MinMaxVectorTy>;
1517
1518
  /// Vector of pair of minimal/maximal access vectors representing
1519
  /// non read only and read only accesses for each alias group.
1520
  using MinMaxVectorPairVectorTy = SmallVector<MinMaxVectorPairTy, 4>;
1521
1522
private:
1523
  Scop(const Scop &) = delete;
1524
  const Scop &operator=(const Scop &) = delete;
1525
1526
  ScalarEvolution *SE;
1527
1528
  /// The underlying Region.
1529
  Region &R;
1530
1531
  // Access functions of the SCoP.
1532
  //
1533
  // This owns all the MemoryAccess objects of the Scop created in this pass.
1534
  AccFuncVector AccessFunctions;
1535
1536
  /// Flag to indicate that the scheduler actually optimized the SCoP.
1537
  bool IsOptimized;
1538
1539
  /// True if the underlying region has a single exiting block.
1540
  bool HasSingleExitEdge;
1541
1542
  /// Flag to remember if the SCoP contained an error block or not.
1543
  bool HasErrorBlock;
1544
1545
  /// Max loop depth.
1546
  unsigned MaxLoopDepth;
1547
1548
  /// Number of copy statements.
1549
  unsigned CopyStmtsNum;
1550
1551
  typedef std::list<ScopStmt> StmtSet;
1552
  /// The statements in this Scop.
1553
  StmtSet Stmts;
1554
1555
  /// Parameters of this Scop
1556
  ParameterSetTy Parameters;
1557
1558
  /// Mapping from parameters to their ids.
1559
  DenseMap<const SCEV *, isl_id *> ParameterIds;
1560
1561
  /// The context of the SCoP created during SCoP detection.
1562
  ScopDetection::DetectionContext &DC;
1563
1564
  /// Isl context.
1565
  ///
1566
  /// We need a shared_ptr with reference counter to delete the context when all
1567
  /// isl objects are deleted. We will distribute the shared_ptr to all objects
1568
  /// that use the context to create isl objects, and increase the reference
1569
  /// counter. By doing this, we guarantee that the context is deleted when we
1570
  /// delete the last object that creates isl objects with the context.
1571
  std::shared_ptr<isl_ctx> IslCtx;
1572
1573
  /// A map from basic blocks to SCoP statements.
1574
  DenseMap<BasicBlock *, ScopStmt *> StmtMap;
1575
1576
  /// A map from basic blocks to their domains.
1577
  DenseMap<BasicBlock *, isl_set *> DomainMap;
1578
1579
  /// Constraints on parameters.
1580
  isl_set *Context;
1581
1582
  /// The affinator used to translate SCEVs to isl expressions.
1583
  SCEVAffinator Affinator;
1584
1585
  typedef std::map<std::pair<AssertingVH<const Value>, MemoryKind>,
1586
                   std::unique_ptr<ScopArrayInfo>>
1587
      ArrayInfoMapTy;
1588
1589
  typedef StringMap<std::unique_ptr<ScopArrayInfo>> ArrayNameMapTy;
1590
1591
  typedef SetVector<ScopArrayInfo *> ArrayInfoSetTy;
1592
1593
  /// A map to remember ScopArrayInfo objects for all base pointers.
1594
  ///
1595
  /// As PHI nodes may have two array info objects associated, we add a flag
1596
  /// that distinguishes between the PHI node specific ArrayInfo object
1597
  /// and the normal one.
1598
  ArrayInfoMapTy ScopArrayInfoMap;
1599
1600
  /// A map to remember ScopArrayInfo objects for all names of memory
1601
  ///        references.
1602
  ArrayNameMapTy ScopArrayNameMap;
1603
1604
  /// A set to remember ScopArrayInfo objects.
1605
  /// @see Scop::ScopArrayInfoMap
1606
  ArrayInfoSetTy ScopArrayInfoSet;
1607
1608
  /// The assumptions under which this scop was built.
1609
  ///
1610
  /// When constructing a scop sometimes the exact representation of a statement
1611
  /// or condition would be very complex, but there is a common case which is a
1612
  /// lot simpler, but which is only valid under certain assumptions. The
1613
  /// assumed context records the assumptions taken during the construction of
1614
  /// this scop and that need to be code generated as a run-time test.
1615
  isl_set *AssumedContext;
1616
1617
  /// The restrictions under which this SCoP was built.
1618
  ///
1619
  /// The invalid context is similar to the assumed context as it contains
1620
  /// constraints over the parameters. However, while we need the constraints
1621
  /// in the assumed context to be "true" the constraints in the invalid context
1622
  /// need to be "false". Otherwise they behave the same.
1623
  isl_set *InvalidContext;
1624
1625
  /// Helper struct to remember assumptions.
1626
  struct Assumption {
1627
1628
    /// The kind of the assumption (e.g., WRAPPING).
1629
    AssumptionKind Kind;
1630
1631
    /// Flag to distinguish assumptions and restrictions.
1632
    AssumptionSign Sign;
1633
1634
    /// The valid/invalid context if this is an assumption/restriction.
1635
    isl_set *Set;
1636
1637
    /// The location that caused this assumption.
1638
    DebugLoc Loc;
1639
1640
    /// An optional block whose domain can simplify the assumption.
1641
    BasicBlock *BB;
1642
  };
1643
1644
  /// Collection to hold taken assumptions.
1645
  ///
1646
  /// There are two reasons why we want to record assumptions first before we
1647
  /// add them to the assumed/invalid context:
1648
  ///   1) If the SCoP is not profitable or otherwise invalid without the
1649
  ///      assumed/invalid context we do not have to compute it.
1650
  ///   2) Information about the context are gathered rather late in the SCoP
1651
  ///      construction (basically after we know all parameters), thus the user
1652
  ///      might see overly complicated assumptions to be taken while they will
1653
  ///      only be simplified later on.
1654
  SmallVector<Assumption, 8> RecordedAssumptions;
1655
1656
  /// The schedule of the SCoP
1657
  ///
1658
  /// The schedule of the SCoP describes the execution order of the statements
1659
  /// in the scop by assigning each statement instance a possibly
1660
  /// multi-dimensional execution time. The schedule is stored as a tree of
1661
  /// schedule nodes.
1662
  ///
1663
  /// The most common nodes in a schedule tree are so-called band nodes. Band
1664
  /// nodes map statement instances into a multi dimensional schedule space.
1665
  /// This space can be seen as a multi-dimensional clock.
1666
  ///
1667
  /// Example:
1668
  ///
1669
  /// <S,(5,4)>  may be mapped to (5,4) by this schedule:
1670
  ///
1671
  /// s0 = i (Year of execution)
1672
  /// s1 = j (Day of execution)
1673
  ///
1674
  /// or to (9, 20) by this schedule:
1675
  ///
1676
  /// s0 = i + j (Year of execution)
1677
  /// s1 = 20 (Day of execution)
1678
  ///
1679
  /// The order statement instances are executed is defined by the
1680
  /// schedule vectors they are mapped to. A statement instance
1681
  /// <A, (i, j, ..)> is executed before a statement instance <B, (i', ..)>, if
1682
  /// the schedule vector of A is lexicographic smaller than the schedule
1683
  /// vector of B.
1684
  ///
1685
  /// Besides band nodes, schedule trees contain additional nodes that specify
1686
  /// a textual ordering between two subtrees or filter nodes that filter the
1687
  /// set of statement instances that will be scheduled in a subtree. There
1688
  /// are also several other nodes. A full description of the different nodes
1689
  /// in a schedule tree is given in the isl manual.
1690
  isl_schedule *Schedule;
1691
1692
  /// The set of minimal/maximal accesses for each alias group.
1693
  ///
1694
  /// When building runtime alias checks we look at all memory instructions and
1695
  /// build so called alias groups. Each group contains a set of accesses to
1696
  /// different base arrays which might alias with each other. However, between
1697
  /// alias groups there is no aliasing possible.
1698
  ///
1699
  /// In a program with int and float pointers annotated with tbaa information
1700
  /// we would probably generate two alias groups, one for the int pointers and
1701
  /// one for the float pointers.
1702
  ///
1703
  /// During code generation we will create a runtime alias check for each alias
1704
  /// group to ensure the SCoP is executed in an alias free environment.
1705
  MinMaxVectorPairVectorTy MinMaxAliasGroups;
1706
1707
  /// Mapping from invariant loads to the representing invariant load of
1708
  ///        their equivalence class.
1709
  ValueToValueMap InvEquivClassVMap;
1710
1711
  /// List of invariant accesses.
1712
  InvariantEquivClassesTy InvariantEquivClasses;
1713
1714
  /// Scop constructor; invoked from ScopBuilder::buildScop.
1715
  Scop(Region &R, ScalarEvolution &SE, LoopInfo &LI,
1716
       ScopDetection::DetectionContext &DC);
1717
1718
  //@}
1719
1720
  /// Initialize this ScopBuilder.
1721
  void init(AliasAnalysis &AA, AssumptionCache &AC, DominatorTree &DT,
1722
            LoopInfo &LI);
1723
1724
  /// Propagate domains that are known due to graph properties.
1725
  ///
1726
  /// As a CFG is mostly structured we use the graph properties to propagate
1727
  /// domains without the need to compute all path conditions. In particular, if
1728
  /// a block A dominates a block B and B post-dominates A we know that the
1729
  /// domain of B is a superset of the domain of A. As we do not have
1730
  /// post-dominator information available here we use the less precise region
1731
  /// information. Given a region R, we know that the exit is always executed if
1732
  /// the entry was executed, thus the domain of the exit is a superset of the
1733
  /// domain of the entry. In case the exit can only be reached from within the
1734
  /// region the domains are in fact equal. This function will use this property
1735
  /// to avoid the generation of condition constraints that determine when a
1736
  /// branch is taken. If @p BB is a region entry block we will propagate its
1737
  /// domain to the region exit block. Additionally, we put the region exit
1738
  /// block in the @p FinishedExitBlocks set so we can later skip edges from
1739
  /// within the region to that block.
1740
  ///
1741
  /// @param BB The block for which the domain is currently propagated.
1742
  /// @param BBLoop The innermost affine loop surrounding @p BB.
1743
  /// @param FinishedExitBlocks Set of region exits the domain was set for.
1744
  /// @param LI The LoopInfo for the current function.
1745
  ///
1746
  void propagateDomainConstraintsToRegionExit(
1747
      BasicBlock *BB, Loop *BBLoop,
1748
      SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, LoopInfo &LI);
1749
1750
  /// Compute the union of predecessor domains for @p BB.
1751
  ///
1752
  /// To compute the union of all domains of predecessors of @p BB this
1753
  /// function applies similar reasoning on the CFG structure as described for
1754
  ///   @see propagateDomainConstraintsToRegionExit
1755
  ///
1756
  /// @param BB     The block for which the predecessor domains are collected.
1757
  /// @param Domain The domain under which BB is executed.
1758
  /// @param DT     The DominatorTree for the current function.
1759
  /// @param LI     The LoopInfo for the current function.
1760
  ///
1761
  /// @returns The domain under which @p BB is executed.
1762
  __isl_give isl_set *
1763
  getPredecessorDomainConstraints(BasicBlock *BB, __isl_keep isl_set *Domain,
1764
                                  DominatorTree &DT, LoopInfo &LI);
1765
1766
  /// Add loop carried constraints to the header block of the loop @p L.
1767
  ///
1768
  /// @param L  The loop to process.
1769
  /// @param LI The LoopInfo for the current function.
1770
  ///
1771
  /// @returns True if there was no problem and false otherwise.
1772
  bool addLoopBoundsToHeaderDomain(Loop *L, LoopInfo &LI);
1773
1774
  /// Compute the branching constraints for each basic block in @p R.
1775
  ///
1776
  /// @param R  The region we currently build branching conditions for.
1777
  /// @param DT The DominatorTree for the current function.
1778
  /// @param LI The LoopInfo for the current function.
1779
  ///
1780
  /// @returns True if there was no problem and false otherwise.
1781
  bool buildDomainsWithBranchConstraints(Region *R, DominatorTree &DT,
1782
                                         LoopInfo &LI);
1783
1784
  /// Propagate the domain constraints through the region @p R.
1785
  ///
1786
  /// @param R  The region we currently build branching conditions for.
1787
  /// @param DT The DominatorTree for the current function.
1788
  /// @param LI The LoopInfo for the current function.
1789
  ///
1790
  /// @returns True if there was no problem and false otherwise.
1791
  bool propagateDomainConstraints(Region *R, DominatorTree &DT, LoopInfo &LI);
1792
1793
  /// Propagate invalid domains of statements through @p R.
1794
  ///
1795
  /// This method will propagate invalid statement domains through @p R and at
1796
  /// the same time add error block domains to them. Additionally, the domains
1797
  /// of error statements and those only reachable via error statements will be
1798
  /// replaced by an empty set. Later those will be removed completely.
1799
  ///
1800
  /// @param R  The currently traversed region.
1801
  /// @param DT The DominatorTree for the current function.
1802
  /// @param LI The LoopInfo for the current function.
1803
  ///
1804
  /// @returns True if there was no problem and false otherwise.
1805
  bool propagateInvalidStmtDomains(Region *R, DominatorTree &DT, LoopInfo &LI);
1806
1807
  /// Compute the domain for each basic block in @p R.
1808
  ///
1809
  /// @param R  The region we currently traverse.
1810
  /// @param DT The DominatorTree for the current function.
1811
  /// @param LI The LoopInfo for the current function.
1812
  ///
1813
  /// @returns True if there was no problem and false otherwise.
1814
  bool buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI);
1815
1816
  /// Add parameter constraints to @p C that imply a non-empty domain.
1817
  __isl_give isl_set *addNonEmptyDomainConstraints(__isl_take isl_set *C) const;
1818
1819
  /// Return the access for the base ptr of @p MA if any.
1820
  MemoryAccess *lookupBasePtrAccess(MemoryAccess *MA);
1821
1822
  /// Check if the base ptr of @p MA is in the SCoP but not hoistable.
1823
  bool hasNonHoistableBasePtrInScop(MemoryAccess *MA,
1824
                                    __isl_keep isl_union_map *Writes);
1825
1826
  /// Create equivalence classes for required invariant accesses.
1827
  ///
1828
  /// These classes will consolidate multiple required invariant loads from the
1829
  /// same address in order to keep the number of dimensions in the SCoP
1830
  /// description small. For each such class equivalence class only one
1831
  /// representing element, hence one required invariant load, will be chosen
1832
  /// and modeled as parameter. The method
1833
  /// Scop::getRepresentingInvariantLoadSCEV() will replace each element from an
1834
  /// equivalence class with the representing element that is modeled. As a
1835
  /// consequence Scop::getIdForParam() will only return an id for the
1836
  /// representing element of each equivalence class, thus for each required
1837
  /// invariant location.
1838
  void buildInvariantEquivalenceClasses();
1839
1840
  /// Return the context under which the access cannot be hoisted.
1841
  ///
1842
  /// @param Access The access to check.
1843
  /// @param Writes The set of all memory writes in the scop.
1844
  ///
1845
  /// @return Return the context under which the access cannot be hoisted or a
1846
  ///         nullptr if it cannot be hoisted at all.
1847
  __isl_give isl_set *getNonHoistableCtx(MemoryAccess *Access,
1848
                                         __isl_keep isl_union_map *Writes);
1849
1850
  /// Verify that all required invariant loads have been hoisted.
1851
  ///
1852
  /// Invariant load hoisting is not guaranteed to hoist all loads that were
1853
  /// assumed to be scop invariant during scop detection. This function checks
1854
  /// for cases where the hoisting failed, but where it would have been
1855
  /// necessary for our scop modeling to be correct. In case of insufficent
1856
  /// hoisting the scop is marked as invalid.
1857
  ///
1858
  /// In the example below Bound[1] is required to be invariant:
1859
  ///
1860
  /// for (int i = 1; i < Bound[0]; i++)
1861
  ///   for (int j = 1; j < Bound[1]; j++)
1862
  ///     ...
1863
  ///
1864
  void verifyInvariantLoads();
1865
1866
  /// Hoist invariant memory loads and check for required ones.
1867
  ///
1868
  /// We first identify "common" invariant loads, thus loads that are invariant
1869
  /// and can be hoisted. Then we check if all required invariant loads have
1870
  /// been identified as (common) invariant. A load is a required invariant load
1871
  /// if it was assumed to be invariant during SCoP detection, e.g., to assume
1872
  /// loop bounds to be affine or runtime alias checks to be placeable. In case
1873
  /// a required invariant load was not identified as (common) invariant we will
1874
  /// drop this SCoP. An example for both "common" as well as required invariant
1875
  /// loads is given below:
1876
  ///
1877
  /// for (int i = 1; i < *LB[0]; i++)
1878
  ///   for (int j = 1; j < *LB[1]; j++)
1879
  ///     A[i][j] += A[0][0] + (*V);
1880
  ///
1881
  /// Common inv. loads: V, A[0][0], LB[0], LB[1]
1882
  /// Required inv. loads: LB[0], LB[1], (V, if it may alias with A or LB)
1883
  ///
1884
  void hoistInvariantLoads();
1885
1886
  /// Add invariant loads listed in @p InvMAs with the domain of @p Stmt.
1887
  void addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs);
1888
1889
  /// Create an id for @p Param and store it in the ParameterIds map.
1890
  void createParameterId(const SCEV *Param);
1891
1892
  /// Build the Context of the Scop.
1893
  void buildContext();
1894
1895
  /// Add user provided parameter constraints to context (source code).
1896
  void addUserAssumptions(AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI);
1897
1898
  /// Add user provided parameter constraints to context (command line).
1899
  void addUserContext();
1900
1901
  /// Add the bounds of the parameters to the context.
1902
  void addParameterBounds();
1903
1904
  /// Simplify the assumed and invalid context.
1905
  void simplifyContexts();
1906
1907
  /// Get the representing SCEV for @p S if applicable, otherwise @p S.
1908
  ///
1909
  /// Invariant loads of the same location are put in an equivalence class and
1910
  /// only one of them is chosen as a representing element that will be
1911
  /// modeled as a parameter. The others have to be normalized, i.e.,
1912
  /// replaced by the representing element of their equivalence class, in order
1913
  /// to get the correct parameter value, e.g., in the SCEVAffinator.
1914
  ///
1915
  /// @param S The SCEV to normalize.
1916
  ///
1917
  /// @return The representing SCEV for invariant loads or @p S if none.
1918
  const SCEV *getRepresentingInvariantLoadSCEV(const SCEV *S);
1919
1920
  /// Create a new SCoP statement for @p BB.
1921
  ///
1922
  /// A new statement for @p BB will be created and added to the statement
1923
  /// vector
1924
  /// and map.
1925
  ///
1926
  /// @param BB              The basic block we build the statement for.
1927
  /// @param SurroundingLoop The loop the created statement is contained in.
1928
  void addScopStmt(BasicBlock *BB, Loop *SurroundingLoop);
1929
1930
  /// Create a new SCoP statement for @p R.
1931
  ///
1932
  /// A new statement for @p R will be created and added to the statement vector
1933
  /// and map.
1934
  ///
1935
  /// @param R               The region we build the statement for.
1936
  /// @param SurroundingLoop The loop the created statement is contained in.
1937
  void addScopStmt(Region *R, Loop *SurroundingLoop);
1938
1939
  /// Update access dimensionalities.
1940
  ///
1941
  /// When detecting memory accesses different accesses to the same array may
1942
  /// have built with different dimensionality, as outer zero-values dimensions
1943
  /// may not have been recognized as separate dimensions. This function goes
1944
  /// again over all memory accesses and updates their dimensionality to match
1945
  /// the dimensionality of the underlying ScopArrayInfo object.
1946
  void updateAccessDimensionality();
1947
1948
  /// Fold size constants to the right.
1949
  ///
1950
  /// In case all memory accesses in a given dimension are multiplied with a
1951
  /// common constant, we can remove this constant from the individual access
1952
  /// functions and move it to the size of the memory access. We do this as this
1953
  /// increases the size of the innermost dimension, consequently widens the
1954
  /// valid range the array subscript in this dimension can evaluate to, and
1955
  /// as a result increases the likelyhood that our delinearization is
1956
  /// correct.
1957
  ///
1958
  /// Example:
1959
  ///
1960
  ///    A[][n]
1961
  ///    S[i,j] -> A[2i][2j+1]
1962
  ///    S[i,j] -> A[2i][2j]
1963
  ///
1964
  ///    =>
1965
  ///
1966
  ///    A[][2n]
1967
  ///    S[i,j] -> A[i][2j+1]
1968
  ///    S[i,j] -> A[i][2j]
1969
  ///
1970
  /// Constants in outer dimensions can arise when the elements of a parametric
1971
  /// multi-dimensional array are not elementar data types, but e.g.,
1972
  /// structures.
1973
  void foldSizeConstantsToRight();
1974
1975
  /// Fold memory accesses to handle parametric offset.
1976
  ///
1977
  /// As a post-processing step, we 'fold' memory accesses to parameteric
1978
  /// offsets in the access functions. @see MemoryAccess::foldAccess for
1979
  /// details.
1980
  void foldAccessRelations();
1981
1982
  /// Assume that all memory accesses are within bounds.
1983
  ///
1984
  /// After we have built a model of all memory accesses, we need to assume
1985
  /// that the model we built matches reality -- aka. all modeled memory
1986
  /// accesses always remain within bounds. We do this as last step, after
1987
  /// all memory accesses have been modeled and canonicalized.
1988
  void assumeNoOutOfBounds();
1989
1990
  /// Finalize all access relations.
1991
  ///
1992
  /// When building up access relations, temporary access relations that
1993
  /// correctly represent each individual access are constructed. However, these
1994
  /// access relations can be inconsistent or non-optimal when looking at the
1995
  /// set of accesses as a whole. This function finalizes the memory accesses
1996
  /// and constructs a globally consistent state.
1997
  void finalizeAccesses();
1998
1999
  /// Construct the schedule of this SCoP.
2000
  ///
2001
  /// @param LI The LoopInfo for the current function.
2002
  void buildSchedule(LoopInfo &LI);
2003
2004
  /// A loop stack element to keep track of per-loop information during
2005
  ///        schedule construction.
2006
  typedef struct LoopStackElement {
2007
    // The loop for which we keep information.
2008
    Loop *L;
2009
2010
    // The (possibly incomplete) schedule for this loop.
2011
    isl_schedule *Schedule;
2012
2013
    // The number of basic blocks in the current loop, for which a schedule has
2014
    // already been constructed.
2015
    unsigned NumBlocksProcessed;
2016
2017
    LoopStackElement(Loop *L, __isl_give isl_schedule *S,
2018
                     unsigned NumBlocksProcessed)
2019
2.19k
        : L(L), Schedule(S), NumBlocksProcessed(NumBlocksProcessed) {}
2020
  } LoopStackElementTy;
2021
2022
  /// The loop stack used for schedule construction.
2023
  ///
2024
  /// The loop stack keeps track of schedule information for a set of nested
2025
  /// loops as well as an (optional) 'nullptr' loop that models the outermost
2026
  /// schedule dimension. The loops in a loop stack always have a parent-child
2027
  /// relation where the loop at position n is the parent of the loop at
2028
  /// position n + 1.
2029
  typedef SmallVector<LoopStackElementTy, 4> LoopStackTy;
2030
2031
  /// Construct schedule information for a given Region and add the
2032
  ///        derived information to @p LoopStack.
2033
  ///
2034
  /// Given a Region we derive schedule information for all RegionNodes
2035
  /// contained in this region ensuring that the assigned execution times
2036
  /// correctly model the existing control flow relations.
2037
  ///
2038
  /// @param R              The region which to process.
2039
  /// @param LoopStack      A stack of loops that are currently under
2040
  ///                       construction.
2041
  /// @param LI The LoopInfo for the current function.
2042
  void buildSchedule(Region *R, LoopStackTy &LoopStack, LoopInfo &LI);
2043
2044
  /// Build Schedule for the region node @p RN and add the derived
2045
  ///        information to @p LoopStack.
2046
  ///
2047
  /// In case @p RN is a BasicBlock or a non-affine Region, we construct the
2048
  /// schedule for this @p RN and also finalize loop schedules in case the
2049
  /// current @p RN completes the loop.
2050
  ///
2051
  /// In case @p RN is a not-non-affine Region, we delegate the construction to
2052
  /// buildSchedule(Region *R, ...).
2053
  ///
2054
  /// @param RN             The RegionNode region traversed.
2055
  /// @param LoopStack      A stack of loops that are currently under
2056
  ///                       construction.
2057
  /// @param LI The LoopInfo for the current function.
2058
  void buildSchedule(RegionNode *RN, LoopStackTy &LoopStack, LoopInfo &LI);
2059
2060
  /// Collect all memory access relations of a given type.
2061
  ///
2062
  /// @param Predicate A predicate function that returns true if an access is
2063
  ///                  of a given type.
2064
  ///
2065
  /// @returns The set of memory accesses in the scop that match the predicate.
2066
  __isl_give isl_union_map *
2067
  getAccessesOfType(std::function<bool(MemoryAccess &)> Predicate);
2068
2069
  /// @name Helper functions for printing the Scop.
2070
  ///
2071
  //@{
2072
  void printContext(raw_ostream &OS) const;
2073
  void printArrayInfo(raw_ostream &OS) const;
2074
  void printStatements(raw_ostream &OS) const;
2075
  void printAliasAssumptions(raw_ostream &OS) const;
2076
  //@}
2077
2078
  friend class ScopBuilder;
2079
2080
public:
2081
  ~Scop();
2082
2083
  /// Get the count of copy statements added to this Scop.
2084
  ///
2085
  /// @return The count of copy statements added to this Scop.
2086
18
  unsigned getCopyStmtsNum() { return CopyStmtsNum; }
2087
2088
  /// Create a new copy statement.
2089
  ///
2090
  /// A new statement will be created and added to the statement vector.
2091
  ///
2092
  /// @param Stmt       The parent statement.
2093
  /// @param SourceRel  The source location.
2094
  /// @param TargetRel  The target location.
2095
  /// @param Domain     The original domain under which copy statement whould
2096
  ///                   be executed.
2097
  ScopStmt *addScopStmt(__isl_take isl_map *SourceRel,
2098
                        __isl_take isl_map *TargetRel,
2099
                        __isl_take isl_set *Domain);
2100
2101
  /// Add the access function to all MemoryAccess objects of the Scop
2102
  ///        created in this pass.
2103
3.91k
  void addAccessFunction(MemoryAccess *Access) {
2104
3.91k
    AccessFunctions.emplace_back(Access);
2105
3.91k
  }
2106
2107
  ScalarEvolution *getSE() const;
2108
2109
  /// Get the count of parameters used in this Scop.
2110
  ///
2111
  /// @return The count of parameters used in this Scop.
2112
983
  size_t getNumParams() const { return Parameters.size(); }
2113
2114
  /// Take a list of parameters and add the new ones to the scop.
2115
  void addParams(const ParameterSetTy &NewParameters);
2116
2117
  /// Return an iterator range containing the scop parameters.
2118
257
  iterator_range<ParameterSetTy::iterator> parameters() const {
2119
257
    return make_range(Parameters.begin(), Parameters.end());
2120
257
  }
2121
2122
  /// Return whether this scop is empty, i.e. contains no statements that
2123
  /// could be executed.
2124
3
  bool isEmpty() const { return Stmts.empty(); }
2125
2126
  typedef ArrayInfoSetTy::iterator array_iterator;
2127
  typedef ArrayInfoSetTy::const_iterator const_array_iterator;
2128
  typedef iterator_range<ArrayInfoSetTy::iterator> array_range;
2129
  typedef iterator_range<ArrayInfoSetTy::const_iterator> const_array_range;
2130
2131
2.62k
  inline array_iterator array_begin() { return ScopArrayInfoSet.begin(); }
2132
2133
2.62k
  inline array_iterator array_end() { return ScopArrayInfoSet.end(); }
2134
2135
760
  inline const_array_iterator array_begin() const {
2136
760
    return ScopArrayInfoSet.begin();
2137
760
  }
2138
2139
760
  inline const_array_iterator array_end() const {
2140
760
    return ScopArrayInfoSet.end();
2141
760
  }
2142
2143
2.36k
  inline array_range arrays() {
2144
2.36k
    return array_range(array_begin(), array_end());
2145
2.36k
  }
2146
2147
760
  inline const_array_range arrays() const {
2148
760
    return const_array_range(array_begin(), array_end());
2149
760
  }
2150
2151
  /// Return the isl_id that represents a certain parameter.
2152
  ///
2153
  /// @param Parameter A SCEV that was recognized as a Parameter.
2154
  ///
2155
  /// @return The corresponding isl_id or NULL otherwise.
2156
  __isl_give isl_id *getIdForParam(const SCEV *Parameter);
2157
2158
  /// Get the maximum region of this static control part.
2159
  ///
2160
  /// @return The maximum region of this static control part.
2161
18.1k
  inline const Region &getRegion() const { return R; }
2162
32.3k
  inline Region &getRegion() { return R; }
2163
2164
  /// Return the function this SCoP is in.
2165
6.81k
  Function &getFunction() const { return *R.getEntry()->getParent(); }
2166
2167
  /// Check if @p L is contained in the SCoP.
2168
9.34k
  bool contains(const Loop *L) const { return R.contains(L); }
2169
2170
  /// Check if @p BB is contained in the SCoP.
2171
17.1k
  bool contains(const BasicBlock *BB) const { return R.contains(BB); }
2172
2173
  /// Check if @p I is contained in the SCoP.
2174
633
  bool contains(const Instruction *I) const { return R.contains(I); }
2175
2176
  /// Return the unique exit block of the SCoP.
2177
2.37k
  BasicBlock *getExit() const { return R.getExit(); }
2178
2179
  /// Return the unique exiting block of the SCoP if any.
2180
577
  BasicBlock *getExitingBlock() const { return R.getExitingBlock(); }
2181
2182
  /// Return the unique entry block of the SCoP.
2183
3.72k
  BasicBlock *getEntry() const { return R.getEntry(); }
2184
2185
  /// Return the unique entering block of the SCoP if any.
2186
781
  BasicBlock *getEnteringBlock() const { return R.getEnteringBlock(); }
2187
2188
  /// Return true if @p BB is the exit block of the SCoP.
2189
1.54k
  bool isExit(BasicBlock *BB) const { return getExit() == BB; }
2190
2191
  /// Return a range of all basic blocks in the SCoP.
2192
2.35k
  Region::block_range blocks() const { return R.blocks(); }
2193
2194
  /// Return true if and only if @p BB dominates the SCoP.
2195
  bool isDominatedBy(const DominatorTree &DT, BasicBlock *BB) const;
2196
2197
  /// Get the maximum depth of the loop.
2198
  ///
2199
  /// @return The maximum depth of the loop.
2200
1.26k
  inline unsigned getMaxLoopDepth() const { return MaxLoopDepth; }
2201
2202
  /// Return the invariant equivalence class for @p Val if any.
2203
  InvariantEquivClassTy *lookupInvariantEquivClass(Value *Val);
2204
2205
  /// Return the set of invariant accesses.
2206
262
  InvariantEquivClassesTy &getInvariantAccesses() {
2207
262
    return InvariantEquivClasses;
2208
262
  }
2209
2210
  /// Check if the scop has any invariant access.
2211
0
  bool hasInvariantAccesses() { return !InvariantEquivClasses.empty(); }
2212
2213
  /// Mark the SCoP as optimized by the scheduler.
2214
30
  void markAsOptimized() { IsOptimized = true; }
2215
2216
  /// Check if the SCoP has been optimized by the scheduler.
2217
0
  bool isOptimized() const { return IsOptimized; }
2218
2219
  /// Get the name of this Scop.
2220
  std::string getNameStr() const;
2221
2222
  /// Get the constraint on parameter of this Scop.
2223
  ///
2224
  /// @return The constraint on parameter of this Scop.
2225
  __isl_give isl_set *getContext() const;
2226
  __isl_give isl_space *getParamSpace() const;
2227
2228
  /// Get the assumed context for this Scop.
2229
  ///
2230
  /// @return The assumed context of this Scop.
2231
  __isl_give isl_set *getAssumedContext() const;
2232
2233
  /// Return true if the optimized SCoP can be executed.
2234
  ///
2235
  /// In addition to the runtime check context this will also utilize the domain
2236
  /// constraints to decide it the optimized version can actually be executed.
2237
  ///
2238
  /// @returns True if the optimized SCoP can be executed.
2239
  bool hasFeasibleRuntimeContext() const;
2240
2241
  /// Check if the assumption in @p Set is trivial or not.
2242
  ///
2243
  /// @param Set  The relations between parameters that are assumed to hold.
2244
  /// @param Sign Enum to indicate if the assumptions in @p Set are positive
2245
  ///             (needed/assumptions) or negative (invalid/restrictions).
2246
  ///
2247
  /// @returns True if the assumption @p Set is not trivial.
2248
  bool isEffectiveAssumption(__isl_keep isl_set *Set, AssumptionSign Sign);
2249
2250
  /// Track and report an assumption.
2251
  ///
2252
  /// Use 'clang -Rpass-analysis=polly-scops' or 'opt
2253
  /// -pass-remarks-analysis=polly-scops' to output the assumptions.
2254
  ///
2255
  /// @param Kind The assumption kind describing the underlying cause.
2256
  /// @param Set  The relations between parameters that are assumed to hold.
2257
  /// @param Loc  The location in the source that caused this assumption.
2258
  /// @param Sign Enum to indicate if the assumptions in @p Set are positive
2259
  ///             (needed/assumptions) or negative (invalid/restrictions).
2260
  ///
2261
  /// @returns True if the assumption is not trivial.
2262
  bool trackAssumption(AssumptionKind Kind, __isl_keep isl_set *Set,
2263
                       DebugLoc Loc, AssumptionSign Sign);
2264
2265
  /// Add assumptions to assumed context.
2266
  ///
2267
  /// The assumptions added will be assumed to hold during the execution of the
2268
  /// scop. However, as they are generally not statically provable, at code
2269
  /// generation time run-time checks will be generated that ensure the
2270
  /// assumptions hold.
2271
  ///
2272
  /// WARNING: We currently exploit in simplifyAssumedContext the knowledge
2273
  ///          that assumptions do not change the set of statement instances
2274
  ///          executed.
2275
  ///
2276
  /// @param Kind The assumption kind describing the underlying cause.
2277
  /// @param Set  The relations between parameters that are assumed to hold.
2278
  /// @param Loc  The location in the source that caused this assumption.
2279
  /// @param Sign Enum to indicate if the assumptions in @p Set are positive
2280
  ///             (needed/assumptions) or negative (invalid/restrictions).
2281
  void addAssumption(AssumptionKind Kind, __isl_take isl_set *Set, DebugLoc Loc,
2282
                     AssumptionSign Sign);
2283
2284
  /// Record an assumption for later addition to the assumed context.
2285
  ///
2286
  /// This function will add the assumption to the RecordedAssumptions. This
2287
  /// collection will be added (@see addAssumption) to the assumed context once
2288
  /// all paramaters are known and the context is fully build.
2289
  ///
2290
  /// @param Kind The assumption kind describing the underlying cause.
2291
  /// @param Set  The relations between parameters that are assumed to hold.
2292
  /// @param Loc  The location in the source that caused this assumption.
2293
  /// @param Sign Enum to indicate if the assumptions in @p Set are positive
2294
  ///             (needed/assumptions) or negative (invalid/restrictions).
2295
  /// @param BB   The block in which this assumption was taken. If it is
2296
  ///             set, the domain of that block will be used to simplify the
2297
  ///             actual assumption in @p Set once it is added. This is useful
2298
  ///             if the assumption was created prior to the domain.
2299
  void recordAssumption(AssumptionKind Kind, __isl_take isl_set *Set,
2300
                        DebugLoc Loc, AssumptionSign Sign,
2301
                        BasicBlock *BB = nullptr);
2302
2303
  /// Add all recorded assumptions to the assumed context.
2304
  void addRecordedAssumptions();
2305
2306
  /// Mark the scop as invalid.
2307
  ///
2308
  /// This method adds an assumption to the scop that is always invalid. As a
2309
  /// result, the scop will not be optimized later on. This function is commonly
2310
  /// called when a condition makes it impossible (or too compile time
2311
  /// expensive) to process this scop any further.
2312
  ///
2313
  /// @param Kind The assumption kind describing the underlying cause.
2314
  /// @param Loc  The location in the source that triggered .
2315
  void invalidate(AssumptionKind Kind, DebugLoc Loc);
2316
2317
  /// Get the invalid context for this Scop.
2318
  ///
2319
  /// @return The invalid context of this Scop.
2320
  __isl_give isl_set *getInvalidContext() const;
2321
2322
  /// Return true if and only if the InvalidContext is trivial (=empty).
2323
411
  bool hasTrivialInvalidContext() const {
2324
411
    return isl_set_is_empty(InvalidContext);
2325
411
  }
2326
2327
  /// A vector of memory accesses that belong to an alias group.
2328
  typedef SmallVector<MemoryAccess *, 4> AliasGroupTy;
2329
2330
  /// A vector of alias groups.
2331
  typedef SmallVector<Scop::AliasGroupTy, 4> AliasGroupVectorTy;
2332
2333
  /// Build the alias checks for this SCoP.
2334
  bool buildAliasChecks(AliasAnalysis &AA);
2335
2336
  /// Build all alias groups for this SCoP.
2337
  ///
2338
  /// @returns True if __no__ error occurred, false otherwise.
2339
  bool buildAliasGroups(AliasAnalysis &AA);
2340
2341
  /// Build alias groups for all memory accesses in the Scop.
2342
  ///
2343
  /// Using the alias analysis and an alias set tracker we build alias sets
2344
  /// for all memory accesses inside the Scop. For each alias set we then map
2345
  /// the aliasing pointers back to the memory accesses we know, thus obtain
2346
  /// groups of memory accesses which might alias. We also collect the set of
2347
  /// arrays through which memory is written.
2348
  ///
2349
  /// @param AA A reference to the alias analysis.
2350
  ///
2351
  /// @returns A pair consistent of a vector of alias groups and a set of arrays
2352
  ///          through which memory is written.
2353
  std::tuple<AliasGroupVectorTy, DenseSet<const ScopArrayInfo *>>
2354
  buildAliasGroupsForAccesses(AliasAnalysis &AA);
2355
2356
  ///  Split alias groups by iteration domains.
2357
  ///
2358
  ///  We split each group based on the domains of the minimal/maximal accesses.
2359
  ///  That means two minimal/maximal accesses are only in a group if their
2360
  ///  access domains intersect. Otherwise, they are in different groups.
2361
  ///
2362
  ///  @param AliasGroups The alias groups to split
2363
  void splitAliasGroupsByDomain(AliasGroupVectorTy &AliasGroups);
2364
2365
  /// Build a given alias group and its access data.
2366
  ///
2367
  /// @param AliasGroup     The alias group to build.
2368
  /// @param HasWriteAccess A set of arrays through which memory is not only
2369
  ///                       read, but also written.
2370
  ///
2371
  /// @returns True if __no__ error occurred, false otherwise.
2372
  bool buildAliasGroup(Scop::AliasGroupTy &AliasGroup,
2373
                       DenseSet<const ScopArrayInfo *> HasWriteAccess);
2374
2375
  /// Return all alias groups for this SCoP.
2376
411
  const MinMaxVectorPairVectorTy &getAliasGroups() const {
2377
411
    return MinMaxAliasGroups;
2378
411
  }
2379
2380
  /// Get an isl string representing the context.
2381
  std::string getContextStr() const;
2382
2383
  /// Get an isl string representing the assumed context.
2384
  std::string getAssumedContextStr() const;
2385
2386
  /// Get an isl string representing the invalid context.
2387
  std::string getInvalidContextStr() const;
2388
2389
  /// Return the ScopStmt for the given @p BB or nullptr if there is
2390
  ///        none.
2391
  ScopStmt *getStmtFor(BasicBlock *BB) const;
2392
2393
  /// Return the ScopStmt that represents the Region @p R, or nullptr if
2394
  ///        it is not represented by any statement in this Scop.
2395
  ScopStmt *getStmtFor(Region *R) const;
2396
2397
  /// Return the ScopStmt that represents @p RN; can return nullptr if
2398
  ///        the RegionNode is not within the SCoP or has been removed due to
2399
  ///        simplifications.
2400
  ScopStmt *getStmtFor(RegionNode *RN) const;
2401
2402
  /// Return the ScopStmt an instruction belongs to, or nullptr if it
2403
  ///        does not belong to any statement in this Scop.
2404
4.31k
  ScopStmt *getStmtFor(Instruction *Inst) const {
2405
4.31k
    return getStmtFor(Inst->getParent());
2406
4.31k
  }
2407
2408
  /// Return the number of statements in the SCoP.
2409
38
  size_t getSize() const { return Stmts.size(); }
2410
2411
  /// @name Statements Iterators
2412
  ///
2413
  /// These iterators iterate over all statements of this Scop.
2414
  //@{
2415
  typedef StmtSet::iterator iterator;
2416
  typedef StmtSet::const_iterator const_iterator;
2417
2418
8.30k
  iterator begin() { return Stmts.begin(); }
2419
8.30k
  iterator end() { return Stmts.end(); }
2420
9.48k
  const_iterator begin() const { return Stmts.begin(); }
2421
9.48k
  const_iterator end() const { return Stmts.end(); }
2422
2423
  typedef StmtSet::reverse_iterator reverse_iterator;
2424
  typedef StmtSet::const_reverse_iterator const_reverse_iterator;
2425
2426
0
  reverse_iterator rbegin() { return Stmts.rbegin(); }
2427
0
  reverse_iterator rend() { return Stmts.rend(); }
2428
0
  const_reverse_iterator rbegin() const { return Stmts.rbegin(); }
2429
0
  const_reverse_iterator rend() const { return Stmts.rend(); }
2430
  //@}
2431
2432
  /// Return the set of required invariant loads.
2433
10.6k
  const InvariantLoadsSetTy &getRequiredInvariantLoads() const {
2434
10.6k
    return DC.RequiredILS;
2435
10.6k
  }
2436
2437
  /// Add @p LI to the set of required invariant loads.
2438
55
  void addRequiredInvariantLoad(LoadInst *LI) { DC.RequiredILS.insert(LI); }
2439
2440
  /// Return true if and only if @p LI is a required invariant load.
2441
31
  bool isRequiredInvariantLoad(LoadInst *LI) const {
2442
31
    return getRequiredInvariantLoads().count(LI);
2443
31
  }
2444
2445
  /// Return the set of boxed (thus overapproximated) loops.
2446
97
  const BoxedLoopsSetTy &getBoxedLoops() const { return DC.BoxedLoopsSet; }
2447
2448
  /// Return true if and only if @p R is a non-affine subregion.
2449
9.54k
  bool isNonAffineSubRegion(const Region *R) {
2450
9.54k
    return DC.NonAffineSubRegionSet.count(R);
2451
9.54k
  }
2452
2453
2.72k
  const MapInsnToMemAcc &getInsnToMemAccMap() const { return DC.InsnToMemAcc; }
2454
2455
  /// Return the (possibly new) ScopArrayInfo object for @p Access.
2456
  ///
2457
  /// @param ElementType The type of the elements stored in this array.
2458
  /// @param Kind        The kind of the array info object.
2459
  /// @param BaseName    The optional name of this memory reference.
2460
  const ScopArrayInfo *getOrCreateScopArrayInfo(Value *BasePtr,
2461
                                                Type *ElementType,
2462
                                                ArrayRef<const SCEV *> Sizes,
2463
                                                MemoryKind Kind,
2464
                                                const char *BaseName = nullptr);
2465
2466
  /// Create an array and return the corresponding ScopArrayInfo object.
2467
  ///
2468
  /// @param ElementType The type of the elements stored in this array.
2469
  /// @param BaseName    The name of this memory reference.
2470
  /// @param Sizes       The sizes of dimensions.
2471
  const ScopArrayInfo *createScopArrayInfo(Type *ElementType,
2472
                                           const std::string &BaseName,
2473
                                           const std::vector<unsigned> &Sizes);
2474
2475
  /// Return the cached ScopArrayInfo object for @p BasePtr.
2476
  ///
2477
  /// @param BasePtr   The base pointer the object has been stored for.
2478
  /// @param Kind      The kind of array info object.
2479
  const ScopArrayInfo *getScopArrayInfo(Value *BasePtr, MemoryKind Kind);
2480
2481
  /// Invalidate ScopArrayInfo object for base address.
2482
  ///
2483
  /// @param BasePtr The base pointer of the ScopArrayInfo object to invalidate.
2484
  /// @param Kind    The Kind of the ScopArrayInfo object.
2485
0
  void invalidateScopArrayInfo(Value *BasePtr, MemoryKind Kind) {
2486
0
    auto It = ScopArrayInfoMap.find(std::make_pair(BasePtr, Kind));
2487
0
    if (It == ScopArrayInfoMap.end())
2488
0
      return;
2489
0
    ScopArrayInfoSet.remove(It->second.get());
2490
0
    ScopArrayInfoMap.erase(It);
2491
0
  }
2492
2493
  void setContext(__isl_take isl_set *NewContext);
2494
2495
  /// Align the parameters in the statement to the scop context
2496
  void realignParams();
2497
2498
  /// Return true if this SCoP can be profitably optimized.
2499
  ///
2500
  /// @param ScalarsAreUnprofitable Never consider statements with scalar writes
2501
  ///                               as profitably optimizable.
2502
  ///
2503
  /// @return Whether this SCoP can be profitably optimized.
2504
  bool isProfitable(bool ScalarsAreUnprofitable) const;
2505
2506
  /// Return true if the SCoP contained at least one error block.
2507
901
  bool hasErrorBlock() const { return HasErrorBlock; }
2508
2509
  /// Return true if the underlying region has a single exiting block.
2510
1.27k
  bool hasSingleExitEdge() const { return HasSingleExitEdge; }
2511
2512
  /// Print the static control part.
2513
  ///
2514
  /// @param OS The output stream the static control part is printed to.
2515
  void print(raw_ostream &OS) const;
2516
2517
  /// Print the ScopStmt to stderr.
2518
  void dump() const;
2519
2520
  /// Get the isl context of this static control part.
2521
  ///
2522
  /// @return The isl context of this static control part.
2523
  isl_ctx *getIslCtx() const;
2524
2525
  /// Directly return the shared_ptr of the context.
2526
932
  const std::shared_ptr<isl_ctx> &getSharedIslCtx() const { return IslCtx; }
2527
2528
  /// Compute the isl representation for the SCEV @p E
2529
  ///
2530
  /// @param E  The SCEV that should be translated.
2531
  /// @param BB An (optional) basic block in which the isl_pw_aff is computed.
2532
  ///           SCEVs known to not reference any loops in the SCoP can be
2533
  ///           passed without a @p BB.
2534
  /// @param NonNegative Flag to indicate the @p E has to be non-negative.
2535
  ///
2536
  /// Note that this function will always return a valid isl_pw_aff. However, if
2537
  /// the translation of @p E was deemed to complex the SCoP is invalidated and
2538
  /// a dummy value of appropriate dimension is returned. This allows to bail
2539
  /// for complex cases without "error handling code" needed on the users side.
2540
  __isl_give PWACtx getPwAff(const SCEV *E, BasicBlock *BB = nullptr,
2541
                             bool NonNegative = false);
2542
2543
  /// Compute the isl representation for the SCEV @p E
2544
  ///
2545
  /// This function is like @see Scop::getPwAff() but strips away the invalid
2546
  /// domain part associated with the piecewise affine function.
2547
  __isl_give isl_pw_aff *getPwAffOnly(const SCEV *E, BasicBlock *BB = nullptr);
2548
2549
  /// Return the domain of @p Stmt.
2550
  ///
2551
  /// @param Stmt The statement for which the conditions should be returned.
2552
  __isl_give isl_set *getDomainConditions(const ScopStmt *Stmt) const;
2553
2554
  /// Return the domain of @p BB.
2555
  ///
2556
  /// @param BB The block for which the conditions should be returned.
2557
  __isl_give isl_set *getDomainConditions(BasicBlock *BB) const;
2558
2559
  /// Get a union set containing the iteration domains of all statements.
2560
  __isl_give isl_union_set *getDomains() const;
2561
2562
  /// Get a union map of all may-writes performed in the SCoP.
2563
  __isl_give isl_union_map *getMayWrites();
2564
2565
  /// Get a union map of all must-writes performed in the SCoP.
2566
  __isl_give isl_union_map *getMustWrites();
2567
2568
  /// Get a union map of all writes performed in the SCoP.
2569
  __isl_give isl_union_map *getWrites();
2570
2571
  /// Get a union map of all reads performed in the SCoP.
2572
  __isl_give isl_union_map *getReads();
2573
2574
  /// Get a union map of all memory accesses performed in the SCoP.
2575
  __isl_give isl_union_map *getAccesses();
2576
2577
  /// Get the schedule of all the statements in the SCoP.
2578
  ///
2579
  /// @return The schedule of all the statements in the SCoP, if the schedule of
2580
  /// the Scop does not contain extension nodes, and nullptr, otherwise.
2581
  __isl_give isl_union_map *getSchedule() const;
2582
2583
  /// Get a schedule tree describing the schedule of all statements.
2584
  __isl_give isl_schedule *getScheduleTree() const;
2585
2586
  /// Update the current schedule
2587
  ///
2588
  /// NewSchedule The new schedule (given as a flat union-map).
2589
  void setSchedule(__isl_take isl_union_map *NewSchedule);
2590
2591
  /// Update the current schedule
2592
  ///
2593
  /// NewSchedule The new schedule (given as schedule tree).
2594
  void setScheduleTree(__isl_take isl_schedule *NewSchedule);
2595
2596
  /// Intersects the domains of all statements in the SCoP.
2597
  ///
2598
  /// @return true if a change was made
2599
  bool restrictDomains(__isl_take isl_union_set *Domain);
2600
2601
  /// Get the depth of a loop relative to the outermost loop in the Scop.
2602
  ///
2603
  /// This will return
2604
  ///    0 if @p L is an outermost loop in the SCoP
2605
  ///   >0 for other loops in the SCoP
2606
  ///   -1 if @p L is nullptr or there is no outermost loop in the SCoP
2607
  int getRelativeLoopDepth(const Loop *L) const;
2608
2609
  /// Find the ScopArrayInfo associated with an isl Id
2610
  ///        that has name @p Name.
2611
  ScopArrayInfo *getArrayInfoByName(const std::string BaseName);
2612
2613
  /// Check whether @p Schedule contains extension nodes.
2614
  ///
2615
  /// @return true if @p Schedule contains extension nodes.
2616
  static bool containsExtensionNode(__isl_keep isl_schedule *Schedule);
2617
2618
  /// Simplify the SCoP representation.
2619
  ///
2620
  /// @param AfterHoisting Whether it is called after invariant load hoisting.
2621
  ///                      When true, also removes statements without
2622
  ///                      side-effects.
2623
  void simplifySCoP(bool AfterHoisting);
2624
};
2625
2626
/// Print Scop scop to raw_ostream O.
2627
0
static inline raw_ostream &operator<<(raw_ostream &O, const Scop &scop) {
2628
0
  scop.print(O);
2629
0
  return O;
2630
0
}
Unexecuted instantiation: Simplify.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: DeLICM.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: FlattenSchedule.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: ScheduleOptimizer.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: DeadCodeElimination.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: ScopHelper.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: RegisterPasses.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: SCEVValidator.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: SCEVAffinator.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: JSONExporter.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: Utils.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: IRBuilder.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: CodeGeneration.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: IslNodeBuilder.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: IslExprBuilder.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: IslAst.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: BlockGenerators.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: PruneUnprofitable.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: ScopPass.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: ScopBuilder.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: ScopInfo.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: PolyhedralInfo.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
Unexecuted instantiation: DependenceInfo.cpp:polly::operator<<(llvm::raw_ostream&, polly::Scop const&)
2631
2632
/// The legacy pass manager's analysis pass to compute scop information
2633
///        for a region.
2634
class ScopInfoRegionPass : public RegionPass {
2635
  /// The Scop pointer which is used to construct a Scop.
2636
  std::unique_ptr<Scop> S;
2637
2638
public:
2639
  static char ID; // Pass identification, replacement for typeid
2640
2641
877
  ScopInfoRegionPass() : RegionPass(ID) {}
2642
877
  ~ScopInfoRegionPass() {}
2643
2644
  /// Build Scop object, the Polly IR of static control
2645
  ///        part for the current SESE-Region.
2646
  ///
2647
  /// @return If the current region is a valid for a static control part,
2648
  ///         return the Polly IR representing this static control part,
2649
  ///         return null otherwise.
2650
4.89k
  Scop *getScop() { return S.get(); }
2651
0
  const Scop *getScop() const { return S.get(); }
2652
2653
  /// Calculate the polyhedral scop information for a given Region.
2654
  bool runOnRegion(Region *R, RGPassManager &RGM) override;
2655
2656
3.24k
  void releaseMemory() override { S.reset(); }
2657
2658
  void print(raw_ostream &O, const Module *M = nullptr) const override;
2659
2660
  void getAnalysisUsage(AnalysisUsage &AU) const override;
2661
};
2662
2663
//===----------------------------------------------------------------------===//
2664
/// The legacy pass manager's analysis pass to compute scop information
2665
///        for the whole function.
2666
///
2667
/// This pass will maintain a map of the maximal region within a scop to its
2668
/// scop object for all the feasible scops present in a function.
2669
/// This pass is an alternative to the ScopInfoRegionPass in order to avoid a
2670
/// region pass manager.
2671
class ScopInfoWrapperPass : public FunctionPass {
2672
2673
public:
2674
  using RegionToScopMapTy = DenseMap<Region *, std::unique_ptr<Scop>>;
2675
  using iterator = RegionToScopMapTy::iterator;
2676
  using const_iterator = RegionToScopMapTy::const_iterator;
2677
2678
private:
2679
  /// A map of Region to its Scop object containing
2680
  ///        Polly IR of static control part
2681
  RegionToScopMapTy RegionToScopMap;
2682
2683
public:
2684
  static char ID; // Pass identification, replacement for typeid
2685
2686
44
  ScopInfoWrapperPass() : FunctionPass(ID) {}
2687
44
  ~ScopInfoWrapperPass() {}
2688
2689
  /// Get the Scop object for the given Region
2690
  ///
2691
  /// @return If the given region is the maximal region within a scop, return
2692
  ///         the scop object. If the given region is a subregion, return a
2693
  ///         nullptr. Top level region containing the entry block of a function
2694
  ///         is not considered in the scop creation.
2695
0
  Scop *getScop(Region *R) const {
2696
0
    auto MapIt = RegionToScopMap.find(R);
2697
0
    if (MapIt != RegionToScopMap.end())
2698
0
      return MapIt->second.get();
2699
0
    return nullptr;
2700
0
  }
2701
2702
59
  iterator begin() { return RegionToScopMap.begin(); }
2703
59
  iterator end() { return RegionToScopMap.end(); }
2704
0
  const_iterator begin() const { return RegionToScopMap.begin(); }
2705
0
  const_iterator end() const { return RegionToScopMap.end(); }
2706
2707
  /// Calculate all the polyhedral scops for a given function.
2708
  bool runOnFunction(Function &F) override;
2709
2710
49
  void releaseMemory() override { RegionToScopMap.clear(); }
2711
2712
  void print(raw_ostream &O, const Module *M = nullptr) const override;
2713
2714
  void getAnalysisUsage(AnalysisUsage &AU) const override;
2715
};
2716
2717
} // end namespace polly
2718
2719
namespace llvm {
2720
class PassRegistry;
2721
void initializeScopInfoRegionPassPass(llvm::PassRegistry &);
2722
void initializeScopInfoWrapperPassPass(llvm::PassRegistry &);
2723
} // namespace llvm
2724
2725
#endif