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