Coverage Report

Created: 2019-02-23 12:57

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