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