Coverage Report

Created: 2019-06-16 23:17

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