Coverage Report

Created: 2019-04-25 15:07

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