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