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