1 //===- polly/ScopBuilder.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 // Create a polyhedral description for a static control flow region. 10 // 11 // The pass creates a polyhedral description of the Scops detected by the SCoP 12 // detection derived from their LLVM-IR code. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #ifndef POLLY_SCOPBUILDER_H 17 #define POLLY_SCOPBUILDER_H 18 19 #include "polly/ScopInfo.h" 20 #include "polly/Support/ScopHelper.h" 21 #include "llvm/ADT/ArrayRef.h" 22 #include "llvm/ADT/SetVector.h" 23 24 namespace polly { 25 26 class ScopDetection; 27 28 /// Command line switch whether to model read-only accesses. 29 extern bool ModelReadOnlyScalars; 30 31 /// Build the Polly IR (Scop and ScopStmt) on a Region. 32 class ScopBuilder { 33 34 /// The AliasAnalysis to build AliasSetTracker. 35 AliasAnalysis &AA; 36 37 /// Target data for element size computing. 38 const DataLayout &DL; 39 40 /// DominatorTree to reason about guaranteed execution. 41 DominatorTree &DT; 42 43 /// LoopInfo for information about loops. 44 LoopInfo &LI; 45 46 /// Valid Regions for Scop 47 ScopDetection &SD; 48 49 /// The ScalarEvolution to help building Scop. 50 ScalarEvolution &SE; 51 52 /// An optimization diagnostic interface to add optimization remarks. 53 OptimizationRemarkEmitter &ORE; 54 55 /// Set of instructions that might read any memory location. 56 SmallVector<std::pair<ScopStmt *, Instruction *>, 16> GlobalReads; 57 58 /// Set of all accessed array base pointers. 59 SmallSetVector<Value *, 16> ArrayBasePointers; 60 61 // The Scop 62 std::unique_ptr<Scop> scop; 63 64 // Methods for pattern matching against Fortran code generated by dragonegg. 65 // @{ 66 67 /// Try to match for the descriptor of a Fortran array whose allocation 68 /// is not visible. That is, we can see the load/store into the memory, but 69 /// we don't actually know where the memory is allocated. If ALLOCATE had been 70 /// called on the Fortran array, then we will see the lowered malloc() call. 71 /// If not, this is dubbed as an "invisible allocation". 72 /// 73 /// "<descriptor>" is the descriptor of the Fortran array. 74 /// 75 /// Pattern match for "@descriptor": 76 /// 1. %mem = load double*, double** bitcast (%"struct.array1_real(kind=8)"* 77 /// <descriptor> to double**), align 32 78 /// 79 /// 2. [%slot = getelementptr inbounds i8, i8* %mem, i64 <index>] 80 /// 2 is optional because if you are writing to the 0th index, you don't 81 /// need a GEP. 82 /// 83 /// 3.1 store/load <memtype> <val>, <memtype>* %slot 84 /// 3.2 store/load <memtype> <val>, <memtype>* %mem 85 /// 86 /// @see polly::MemoryAccess, polly::ScopArrayInfo 87 /// 88 /// @note assumes -polly-canonicalize has been run. 89 /// 90 /// @param Inst The LoadInst/StoreInst that accesses the memory. 91 /// 92 /// @returns Reference to <descriptor> on success, nullptr on failure. 93 Value *findFADAllocationInvisible(MemAccInst Inst); 94 95 /// Try to match for the descriptor of a Fortran array whose allocation 96 /// call is visible. When we have a Fortran array, we try to look for a 97 /// Fortran array where we can see the lowered ALLOCATE call. ALLOCATE 98 /// is materialized as a malloc(...) which we pattern match for. 99 /// 100 /// Pattern match for "%untypedmem": 101 /// 1. %untypedmem = i8* @malloc(...) 102 /// 103 /// 2. %typedmem = bitcast i8* %untypedmem to <memtype> 104 /// 105 /// 3. [%slot = getelementptr inbounds i8, i8* %typedmem, i64 <index>] 106 /// 3 is optional because if you are writing to the 0th index, you don't 107 /// need a GEP. 108 /// 109 /// 4.1 store/load <memtype> <val>, <memtype>* %slot, align 8 110 /// 4.2 store/load <memtype> <val>, <memtype>* %mem, align 8 111 /// 112 /// @see polly::MemoryAccess, polly::ScopArrayInfo 113 /// 114 /// @note assumes -polly-canonicalize has been run. 115 /// 116 /// @param Inst The LoadInst/StoreInst that accesses the memory. 117 /// 118 /// @returns Reference to %untypedmem on success, nullptr on failure. 119 Value *findFADAllocationVisible(MemAccInst Inst); 120 121 // @} 122 123 // Build the SCoP for Region @p R. 124 void buildScop(Region &R, AssumptionCache &AC); 125 126 /// Adjust the dimensions of @p Dom that was constructed for @p OldL 127 /// to be compatible to domains constructed for loop @p NewL. 128 /// 129 /// This function assumes @p NewL and @p OldL are equal or there is a CFG 130 /// edge from @p OldL to @p NewL. 131 isl::set adjustDomainDimensions(isl::set Dom, Loop *OldL, Loop *NewL); 132 133 /// Compute the domain for each basic block in @p R. 134 /// 135 /// @param R The region we currently traverse. 136 /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current 137 /// region. 138 /// 139 /// @returns True if there was no problem and false otherwise. 140 bool buildDomains(Region *R, 141 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap); 142 143 /// Compute the branching constraints for each basic block in @p R. 144 /// 145 /// @param R The region we currently build branching conditions 146 /// for. 147 /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current 148 /// region. 149 /// 150 /// @returns True if there was no problem and false otherwise. 151 bool buildDomainsWithBranchConstraints( 152 Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap); 153 154 /// Build the conditions sets for the terminator @p TI in the @p Domain. 155 /// 156 /// This will fill @p ConditionSets with the conditions under which control 157 /// will be moved from @p TI to its successors. Hence, @p ConditionSets will 158 /// have as many elements as @p TI has successors. 159 bool buildConditionSets(BasicBlock *BB, Instruction *TI, Loop *L, 160 __isl_keep isl_set *Domain, 161 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap, 162 SmallVectorImpl<__isl_give isl_set *> &ConditionSets); 163 164 /// Build the conditions sets for the branch condition @p Condition in 165 /// the @p Domain. 166 /// 167 /// This will fill @p ConditionSets with the conditions under which control 168 /// will be moved from @p TI to its successors. Hence, @p ConditionSets will 169 /// have as many elements as @p TI has successors. If @p TI is nullptr the 170 /// context under which @p Condition is true/false will be returned as the 171 /// new elements of @p ConditionSets. 172 bool buildConditionSets(BasicBlock *BB, Value *Condition, Instruction *TI, 173 Loop *L, __isl_keep isl_set *Domain, 174 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap, 175 SmallVectorImpl<__isl_give isl_set *> &ConditionSets); 176 177 /// Build the conditions sets for the switch @p SI in the @p Domain. 178 /// 179 /// This will fill @p ConditionSets with the conditions under which control 180 /// will be moved from @p SI to its successors. Hence, @p ConditionSets will 181 /// have as many elements as @p SI has successors. 182 bool buildConditionSets(BasicBlock *BB, SwitchInst *SI, Loop *L, 183 __isl_keep isl_set *Domain, 184 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap, 185 SmallVectorImpl<__isl_give isl_set *> &ConditionSets); 186 187 /// Build condition sets for unsigned ICmpInst(s). 188 /// Special handling is required for unsigned operands to ensure that if 189 /// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst 190 /// it should wrap around. 191 /// 192 /// @param IsStrictUpperBound holds information on the predicate relation 193 /// between TestVal and UpperBound, i.e, 194 /// TestVal < UpperBound OR TestVal <= UpperBound 195 __isl_give isl_set *buildUnsignedConditionSets( 196 BasicBlock *BB, Value *Condition, __isl_keep isl_set *Domain, 197 const SCEV *SCEV_TestVal, const SCEV *SCEV_UpperBound, 198 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap, 199 bool IsStrictUpperBound); 200 201 /// Propagate the domain constraints through the region @p R. 202 /// 203 /// @param R The region we currently build branching 204 /// conditions for. 205 /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current 206 /// region. 207 /// 208 /// @returns True if there was no problem and false otherwise. 209 bool propagateDomainConstraints( 210 Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap); 211 212 /// Propagate domains that are known due to graph properties. 213 /// 214 /// As a CFG is mostly structured we use the graph properties to propagate 215 /// domains without the need to compute all path conditions. In particular, 216 /// if a block A dominates a block B and B post-dominates A we know that the 217 /// domain of B is a superset of the domain of A. As we do not have 218 /// post-dominator information available here we use the less precise region 219 /// information. Given a region R, we know that the exit is always executed 220 /// if the entry was executed, thus the domain of the exit is a superset of 221 /// the domain of the entry. In case the exit can only be reached from 222 /// within the region the domains are in fact equal. This function will use 223 /// this property to avoid the generation of condition constraints that 224 /// determine when a branch is taken. If @p BB is a region entry block we 225 /// will propagate its domain to the region exit block. Additionally, we put 226 /// the region exit block in the @p FinishedExitBlocks set so we can later 227 /// skip edges from within the region to that block. 228 /// 229 /// @param BB The block for which the domain is currently 230 /// propagated. 231 /// @param BBLoop The innermost affine loop surrounding @p BB. 232 /// @param FinishedExitBlocks Set of region exits the domain was set for. 233 /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current 234 /// region. 235 void propagateDomainConstraintsToRegionExit( 236 BasicBlock *BB, Loop *BBLoop, 237 SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, 238 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap); 239 240 /// Propagate invalid domains of statements through @p R. 241 /// 242 /// This method will propagate invalid statement domains through @p R and at 243 /// the same time add error block domains to them. Additionally, the domains 244 /// of error statements and those only reachable via error statements will 245 /// be replaced by an empty set. Later those will be removed completely. 246 /// 247 /// @param R The currently traversed region. 248 /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current 249 /// region. 250 // 251 /// @returns True if there was no problem and false otherwise. 252 bool propagateInvalidStmtDomains( 253 Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap); 254 255 /// Compute the union of predecessor domains for @p BB. 256 /// 257 /// To compute the union of all domains of predecessors of @p BB this 258 /// function applies similar reasoning on the CFG structure as described for 259 /// @see propagateDomainConstraintsToRegionExit 260 /// 261 /// @param BB The block for which the predecessor domains are collected. 262 /// @param Domain The domain under which BB is executed. 263 /// 264 /// @returns The domain under which @p BB is executed. 265 isl::set getPredecessorDomainConstraints(BasicBlock *BB, isl::set Domain); 266 267 /// Add loop carried constraints to the header block of the loop @p L. 268 /// 269 /// @param L The loop to process. 270 /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current 271 /// region. 272 /// 273 /// @returns True if there was no problem and false otherwise. 274 bool addLoopBoundsToHeaderDomain( 275 Loop *L, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap); 276 277 /// Compute the isl representation for the SCEV @p E in this BB. 278 /// 279 /// @param BB The BB for which isl representation is to be 280 /// computed. 281 /// @param InvalidDomainMap A map of BB to their invalid domains. 282 /// @param E The SCEV that should be translated. 283 /// @param NonNegative Flag to indicate the @p E has to be 284 /// non-negative. 285 /// 286 /// Note that this function will also adjust the invalid context 287 /// accordingly. 288 __isl_give isl_pw_aff * 289 getPwAff(BasicBlock *BB, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap, 290 const SCEV *E, bool NonNegative = false); 291 292 /// Create equivalence classes for required invariant accesses. 293 /// 294 /// These classes will consolidate multiple required invariant loads from the 295 /// same address in order to keep the number of dimensions in the SCoP 296 /// description small. For each such class equivalence class only one 297 /// representing element, hence one required invariant load, will be chosen 298 /// and modeled as parameter. The method 299 /// Scop::getRepresentingInvariantLoadSCEV() will replace each element from an 300 /// equivalence class with the representing element that is modeled. As a 301 /// consequence Scop::getIdForParam() will only return an id for the 302 /// representing element of each equivalence class, thus for each required 303 /// invariant location. 304 void buildInvariantEquivalenceClasses(); 305 306 /// Try to build a multi-dimensional fixed sized MemoryAccess from the 307 /// Load/Store instruction. 308 /// 309 /// @param Inst The Load/Store instruction that access the memory 310 /// @param Stmt The parent statement of the instruction 311 /// 312 /// @returns True if the access could be built, False otherwise. 313 bool buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt); 314 315 /// Try to build a multi-dimensional parametric sized MemoryAccess. 316 /// from the Load/Store instruction. 317 /// 318 /// @param Inst The Load/Store instruction that access the memory 319 /// @param Stmt The parent statement of the instruction 320 /// 321 /// @returns True if the access could be built, False otherwise. 322 bool buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt); 323 324 /// Try to build a MemoryAccess for a memory intrinsic. 325 /// 326 /// @param Inst The instruction that access the memory 327 /// @param Stmt The parent statement of the instruction 328 /// 329 /// @returns True if the access could be built, False otherwise. 330 bool buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt); 331 332 /// Try to build a MemoryAccess for a call instruction. 333 /// 334 /// @param Inst The call instruction that access the memory 335 /// @param Stmt The parent statement of the instruction 336 /// 337 /// @returns True if the access could be built, False otherwise. 338 bool buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt); 339 340 /// Build a single-dimensional parametric sized MemoryAccess 341 /// from the Load/Store instruction. 342 /// 343 /// @param Inst The Load/Store instruction that access the memory 344 /// @param Stmt The parent statement of the instruction 345 void buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt); 346 347 /// Finalize all access relations. 348 /// 349 /// When building up access relations, temporary access relations that 350 /// correctly represent each individual access are constructed. However, these 351 /// access relations can be inconsistent or non-optimal when looking at the 352 /// set of accesses as a whole. This function finalizes the memory accesses 353 /// and constructs a globally consistent state. 354 void finalizeAccesses(); 355 356 /// Update access dimensionalities. 357 /// 358 /// When detecting memory accesses different accesses to the same array may 359 /// have built with different dimensionality, as outer zero-values dimensions 360 /// may not have been recognized as separate dimensions. This function goes 361 /// again over all memory accesses and updates their dimensionality to match 362 /// the dimensionality of the underlying ScopArrayInfo object. 363 void updateAccessDimensionality(); 364 365 /// Fold size constants to the right. 366 /// 367 /// In case all memory accesses in a given dimension are multiplied with a 368 /// common constant, we can remove this constant from the individual access 369 /// functions and move it to the size of the memory access. We do this as this 370 /// increases the size of the innermost dimension, consequently widens the 371 /// valid range the array subscript in this dimension can evaluate to, and 372 /// as a result increases the likelihood that our delinearization is 373 /// correct. 374 /// 375 /// Example: 376 /// 377 /// A[][n] 378 /// S[i,j] -> A[2i][2j+1] 379 /// S[i,j] -> A[2i][2j] 380 /// 381 /// => 382 /// 383 /// A[][2n] 384 /// S[i,j] -> A[i][2j+1] 385 /// S[i,j] -> A[i][2j] 386 /// 387 /// Constants in outer dimensions can arise when the elements of a parametric 388 /// multi-dimensional array are not elementary data types, but e.g., 389 /// structures. 390 void foldSizeConstantsToRight(); 391 392 /// Fold memory accesses to handle parametric offset. 393 /// 394 /// As a post-processing step, we 'fold' memory accesses to parametric 395 /// offsets in the access functions. @see MemoryAccess::foldAccess for 396 /// details. 397 void foldAccessRelations(); 398 399 /// Assume that all memory accesses are within bounds. 400 /// 401 /// After we have built a model of all memory accesses, we need to assume 402 /// that the model we built matches reality -- aka. all modeled memory 403 /// accesses always remain within bounds. We do this as last step, after 404 /// all memory accesses have been modeled and canonicalized. 405 void assumeNoOutOfBounds(); 406 407 /// Mark arrays that have memory accesses with FortranArrayDescriptor. 408 void markFortranArrays(); 409 410 /// Build the alias checks for this SCoP. 411 bool buildAliasChecks(); 412 413 /// A vector of memory accesses that belong to an alias group. 414 using AliasGroupTy = SmallVector<MemoryAccess *, 4>; 415 416 /// A vector of alias groups. 417 using AliasGroupVectorTy = SmallVector<AliasGroupTy, 4>; 418 419 /// Build a given alias group and its access data. 420 /// 421 /// @param AliasGroup The alias group to build. 422 /// @param HasWriteAccess A set of arrays through which memory is not only 423 /// read, but also written. 424 // 425 /// @returns True if __no__ error occurred, false otherwise. 426 bool buildAliasGroup(AliasGroupTy &AliasGroup, 427 DenseSet<const ScopArrayInfo *> HasWriteAccess); 428 429 /// Build all alias groups for this SCoP. 430 /// 431 /// @returns True if __no__ error occurred, false otherwise. 432 bool buildAliasGroups(); 433 434 /// Build alias groups for all memory accesses in the Scop. 435 /// 436 /// Using the alias analysis and an alias set tracker we build alias sets 437 /// for all memory accesses inside the Scop. For each alias set we then map 438 /// the aliasing pointers back to the memory accesses we know, thus obtain 439 /// groups of memory accesses which might alias. We also collect the set of 440 /// arrays through which memory is written. 441 /// 442 /// @returns A pair consistent of a vector of alias groups and a set of arrays 443 /// through which memory is written. 444 std::tuple<AliasGroupVectorTy, DenseSet<const ScopArrayInfo *>> 445 buildAliasGroupsForAccesses(); 446 447 /// Split alias groups by iteration domains. 448 /// 449 /// We split each group based on the domains of the minimal/maximal accesses. 450 /// That means two minimal/maximal accesses are only in a group if their 451 /// access domains intersect. Otherwise, they are in different groups. 452 /// 453 /// @param AliasGroups The alias groups to split 454 void splitAliasGroupsByDomain(AliasGroupVectorTy &AliasGroups); 455 456 /// Build an instance of MemoryAccess from the Load/Store instruction. 457 /// 458 /// @param Inst The Load/Store instruction that access the memory 459 /// @param Stmt The parent statement of the instruction 460 void buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt); 461 462 /// Analyze and extract the cross-BB scalar dependences (or, dataflow 463 /// dependencies) of an instruction. 464 /// 465 /// @param UserStmt The statement @p Inst resides in. 466 /// @param Inst The instruction to be analyzed. 467 void buildScalarDependences(ScopStmt *UserStmt, Instruction *Inst); 468 469 /// Build the escaping dependences for @p Inst. 470 /// 471 /// Search for uses of the llvm::Value defined by @p Inst that are not 472 /// within the SCoP. If there is such use, add a SCALAR WRITE such that 473 /// it is available after the SCoP as escaping value. 474 /// 475 /// @param Inst The instruction to be analyzed. 476 void buildEscapingDependences(Instruction *Inst); 477 478 /// Create MemoryAccesses for the given PHI node in the given region. 479 /// 480 /// @param PHIStmt The statement @p PHI resides in. 481 /// @param PHI The PHI node to be handled 482 /// @param NonAffineSubRegion The non affine sub-region @p PHI is in. 483 /// @param IsExitBlock Flag to indicate that @p PHI is in the exit BB. 484 void buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI, 485 Region *NonAffineSubRegion, bool IsExitBlock = false); 486 487 /// Build the access functions for the subregion @p SR. 488 void buildAccessFunctions(); 489 490 /// Should an instruction be modeled in a ScopStmt. 491 /// 492 /// @param Inst The instruction to check. 493 /// @param L The loop in which context the instruction is looked at. 494 /// 495 /// @returns True if the instruction should be modeled. 496 bool shouldModelInst(Instruction *Inst, Loop *L); 497 498 /// Create one or more ScopStmts for @p BB. 499 /// 500 /// Consecutive instructions are associated to the same statement until a 501 /// separator is found. 502 void buildSequentialBlockStmts(BasicBlock *BB, bool SplitOnStore = false); 503 504 /// Create one or more ScopStmts for @p BB using equivalence classes. 505 /// 506 /// Instructions of a basic block that belong to the same equivalence class 507 /// are added to the same statement. 508 void buildEqivClassBlockStmts(BasicBlock *BB); 509 510 /// Create ScopStmt for all BBs and non-affine subregions of @p SR. 511 /// 512 /// @param SR A subregion of @p R. 513 /// 514 /// Some of the statements might be optimized away later when they do not 515 /// access any memory and thus have no effect. 516 void buildStmts(Region &SR); 517 518 /// Build the access functions for the statement @p Stmt in or represented by 519 /// @p BB. 520 /// 521 /// @param Stmt Statement to add MemoryAccesses to. 522 /// @param BB A basic block in @p R. 523 /// @param NonAffineSubRegion The non affine sub-region @p BB is in. 524 void buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB, 525 Region *NonAffineSubRegion = nullptr); 526 527 /// Create a new MemoryAccess object and add it to #AccFuncMap. 528 /// 529 /// @param Stmt The statement where the access takes place. 530 /// @param Inst The instruction doing the access. It is not necessarily 531 /// inside @p BB. 532 /// @param AccType The kind of access. 533 /// @param BaseAddress The accessed array's base address. 534 /// @param ElemType The type of the accessed array elements. 535 /// @param Affine Whether all subscripts are affine expressions. 536 /// @param AccessValue Value read or written. 537 /// @param Subscripts Access subscripts per dimension. 538 /// @param Sizes The array dimension's sizes. 539 /// @param Kind The kind of memory accessed. 540 /// 541 /// @return The created MemoryAccess, or nullptr if the access is not within 542 /// the SCoP. 543 MemoryAccess *addMemoryAccess(ScopStmt *Stmt, Instruction *Inst, 544 MemoryAccess::AccessType AccType, 545 Value *BaseAddress, Type *ElemType, bool Affine, 546 Value *AccessValue, 547 ArrayRef<const SCEV *> Subscripts, 548 ArrayRef<const SCEV *> Sizes, MemoryKind Kind); 549 550 /// Create a MemoryAccess that represents either a LoadInst or 551 /// StoreInst. 552 /// 553 /// @param Stmt The statement to add the MemoryAccess to. 554 /// @param MemAccInst The LoadInst or StoreInst. 555 /// @param AccType The kind of access. 556 /// @param BaseAddress The accessed array's base address. 557 /// @param ElemType The type of the accessed array elements. 558 /// @param IsAffine Whether all subscripts are affine expressions. 559 /// @param Subscripts Access subscripts per dimension. 560 /// @param Sizes The array dimension's sizes. 561 /// @param AccessValue Value read or written. 562 /// 563 /// @see MemoryKind 564 void addArrayAccess(ScopStmt *Stmt, MemAccInst MemAccInst, 565 MemoryAccess::AccessType AccType, Value *BaseAddress, 566 Type *ElemType, bool IsAffine, 567 ArrayRef<const SCEV *> Subscripts, 568 ArrayRef<const SCEV *> Sizes, Value *AccessValue); 569 570 /// Create a MemoryAccess for writing an llvm::Instruction. 571 /// 572 /// The access will be created at the position of @p Inst. 573 /// 574 /// @param Inst The instruction to be written. 575 /// 576 /// @see ensureValueRead() 577 /// @see MemoryKind 578 void ensureValueWrite(Instruction *Inst); 579 580 /// Ensure an llvm::Value is available in the BB's statement, creating a 581 /// MemoryAccess for reloading it if necessary. 582 /// 583 /// @param V The value expected to be loaded. 584 /// @param UserStmt Where to reload the value. 585 /// 586 /// @see ensureValueStore() 587 /// @see MemoryKind 588 void ensureValueRead(Value *V, ScopStmt *UserStmt); 589 590 /// Create a write MemoryAccess for the incoming block of a phi node. 591 /// 592 /// Each of the incoming blocks write their incoming value to be picked in the 593 /// phi's block. 594 /// 595 /// @param PHI PHINode under consideration. 596 /// @param IncomingStmt The statement to add the MemoryAccess to. 597 /// @param IncomingBlock Some predecessor block. 598 /// @param IncomingValue @p PHI's value when coming from @p IncomingBlock. 599 /// @param IsExitBlock When true, uses the .s2a alloca instead of the 600 /// .phiops one. Required for values escaping through a 601 /// PHINode in the SCoP region's exit block. 602 /// @see addPHIReadAccess() 603 /// @see MemoryKind 604 void ensurePHIWrite(PHINode *PHI, ScopStmt *IncomintStmt, 605 BasicBlock *IncomingBlock, Value *IncomingValue, 606 bool IsExitBlock); 607 608 /// Add user provided parameter constraints to context (command line). 609 void addUserContext(); 610 611 /// Add user provided parameter constraints to context (source code). 612 void addUserAssumptions(AssumptionCache &AC, 613 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap); 614 615 /// Add all recorded assumptions to the assumed context. 616 void addRecordedAssumptions(); 617 618 /// Create a MemoryAccess for reading the value of a phi. 619 /// 620 /// The modeling assumes that all incoming blocks write their incoming value 621 /// to the same location. Thus, this access will read the incoming block's 622 /// value as instructed by this @p PHI. 623 /// 624 /// @param PHIStmt Statement @p PHI resides in. 625 /// @param PHI PHINode under consideration; the READ access will be added 626 /// here. 627 /// 628 /// @see ensurePHIWrite() 629 /// @see MemoryKind 630 void addPHIReadAccess(ScopStmt *PHIStmt, PHINode *PHI); 631 632 /// Wrapper function to calculate minimal/maximal accesses to each array. 633 bool calculateMinMaxAccess(AliasGroupTy AliasGroup, 634 Scop::MinMaxVectorTy &MinMaxAccesses); 635 /// Build the domain of @p Stmt. 636 void buildDomain(ScopStmt &Stmt); 637 638 /// Fill NestLoops with loops surrounding @p Stmt. 639 void collectSurroundingLoops(ScopStmt &Stmt); 640 641 /// Check for reductions in @p Stmt. 642 /// 643 /// Iterate over all store memory accesses and check for valid binary 644 /// reduction like chains. For all candidates we check if they have the same 645 /// base address and there are no other accesses which overlap with them. The 646 /// base address check rules out impossible reductions candidates early. The 647 /// overlap check, together with the "only one user" check in 648 /// collectCandidateReductionLoads, guarantees that none of the intermediate 649 /// results will escape during execution of the loop nest. We basically check 650 /// here that no other memory access can access the same memory as the 651 /// potential reduction. 652 void checkForReductions(ScopStmt &Stmt); 653 654 /// Verify that all required invariant loads have been hoisted. 655 /// 656 /// Invariant load hoisting is not guaranteed to hoist all loads that were 657 /// assumed to be scop invariant during scop detection. This function checks 658 /// for cases where the hoisting failed, but where it would have been 659 /// necessary for our scop modeling to be correct. In case of insufficient 660 /// hoisting the scop is marked as invalid. 661 /// 662 /// In the example below Bound[1] is required to be invariant: 663 /// 664 /// for (int i = 1; i < Bound[0]; i++) 665 /// for (int j = 1; j < Bound[1]; j++) 666 /// ... 667 void verifyInvariantLoads(); 668 669 /// Hoist invariant memory loads and check for required ones. 670 /// 671 /// We first identify "common" invariant loads, thus loads that are invariant 672 /// and can be hoisted. Then we check if all required invariant loads have 673 /// been identified as (common) invariant. A load is a required invariant load 674 /// if it was assumed to be invariant during SCoP detection, e.g., to assume 675 /// loop bounds to be affine or runtime alias checks to be placeable. In case 676 /// a required invariant load was not identified as (common) invariant we will 677 /// drop this SCoP. An example for both "common" as well as required invariant 678 /// loads is given below: 679 /// 680 /// for (int i = 1; i < *LB[0]; i++) 681 /// for (int j = 1; j < *LB[1]; j++) 682 /// A[i][j] += A[0][0] + (*V); 683 /// 684 /// Common inv. loads: V, A[0][0], LB[0], LB[1] 685 /// Required inv. loads: LB[0], LB[1], (V, if it may alias with A or LB) 686 void hoistInvariantLoads(); 687 688 /// Add invariant loads listed in @p InvMAs with the domain of @p Stmt. 689 void addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs); 690 691 /// Check if @p MA can always be hoisted without execution context. 692 bool canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty, 693 bool MAInvalidCtxIsEmpty, 694 bool NonHoistableCtxIsEmpty); 695 696 /// Return true if and only if @p LI is a required invariant load. isRequiredInvariantLoad(LoadInst * LI)697 bool isRequiredInvariantLoad(LoadInst *LI) const { 698 return scop->getRequiredInvariantLoads().count(LI); 699 } 700 701 /// Check if the base ptr of @p MA is in the SCoP but not hoistable. 702 bool hasNonHoistableBasePtrInScop(MemoryAccess *MA, isl::union_map Writes); 703 704 /// Return the context under which the access cannot be hoisted. 705 /// 706 /// @param Access The access to check. 707 /// @param Writes The set of all memory writes in the scop. 708 /// 709 /// @return Return the context under which the access cannot be hoisted or a 710 /// nullptr if it cannot be hoisted at all. 711 isl::set getNonHoistableCtx(MemoryAccess *Access, isl::union_map Writes); 712 713 /// Collect loads which might form a reduction chain with @p StoreMA. 714 /// 715 /// Check if the stored value for @p StoreMA is a binary operator with one or 716 /// two loads as operands. If the binary operand is commutative & associative, 717 /// used only once (by @p StoreMA) and its load operands are also used only 718 /// once, we have found a possible reduction chain. It starts at an operand 719 /// load and includes the binary operator and @p StoreMA. 720 /// 721 /// Note: We allow only one use to ensure the load and binary operator cannot 722 /// escape this block or into any other store except @p StoreMA. 723 void collectCandidateReductionLoads(MemoryAccess *StoreMA, 724 SmallVectorImpl<MemoryAccess *> &Loads); 725 726 /// Build the access relation of all memory accesses of @p Stmt. 727 void buildAccessRelations(ScopStmt &Stmt); 728 729 /// Canonicalize arrays with base pointers from the same equivalence class. 730 /// 731 /// Some context: in our normal model we assume that each base pointer is 732 /// related to a single specific memory region, where memory regions 733 /// associated with different base pointers are disjoint. Consequently we do 734 /// not need to compute additional data dependences that model possible 735 /// overlaps of these memory regions. To verify our assumption we compute 736 /// alias checks that verify that modeled arrays indeed do not overlap. In 737 /// case an overlap is detected the runtime check fails and we fall back to 738 /// the original code. 739 /// 740 /// In case of arrays where the base pointers are know to be identical, 741 /// because they are dynamically loaded by accesses that are in the same 742 /// invariant load equivalence class, such run-time alias check would always 743 /// be false. 744 /// 745 /// This function makes sure that we do not generate consistently failing 746 /// run-time checks for code that contains distinct arrays with known 747 /// equivalent base pointers. It identifies for each invariant load 748 /// equivalence class a single canonical array and canonicalizes all memory 749 /// accesses that reference arrays that have base pointers that are known to 750 /// be equal to the base pointer of such a canonical array to this canonical 751 /// array. 752 /// 753 /// We currently do not canonicalize arrays for which certain memory accesses 754 /// have been hoisted as loop invariant. 755 void canonicalizeDynamicBasePtrs(); 756 757 /// Construct the schedule of this SCoP. 758 void buildSchedule(); 759 760 /// A loop stack element to keep track of per-loop information during 761 /// schedule construction. 762 using LoopStackElementTy = struct LoopStackElement { 763 // The loop for which we keep information. 764 Loop *L; 765 766 // The (possibly incomplete) schedule for this loop. 767 isl::schedule Schedule; 768 769 // The number of basic blocks in the current loop, for which a schedule has 770 // already been constructed. 771 unsigned NumBlocksProcessed; 772 LoopStackElementLoopStackElement773 LoopStackElement(Loop *L, isl::schedule S, unsigned NumBlocksProcessed) 774 : L(L), Schedule(S), NumBlocksProcessed(NumBlocksProcessed) {} 775 }; 776 777 /// The loop stack used for schedule construction. 778 /// 779 /// The loop stack keeps track of schedule information for a set of nested 780 /// loops as well as an (optional) 'nullptr' loop that models the outermost 781 /// schedule dimension. The loops in a loop stack always have a parent-child 782 /// relation where the loop at position n is the parent of the loop at 783 /// position n + 1. 784 using LoopStackTy = SmallVector<LoopStackElementTy, 4>; 785 786 /// Construct schedule information for a given Region and add the 787 /// derived information to @p LoopStack. 788 /// 789 /// Given a Region we derive schedule information for all RegionNodes 790 /// contained in this region ensuring that the assigned execution times 791 /// correctly model the existing control flow relations. 792 /// 793 /// @param R The region which to process. 794 /// @param LoopStack A stack of loops that are currently under 795 /// construction. 796 void buildSchedule(Region *R, LoopStackTy &LoopStack); 797 798 /// Build Schedule for the region node @p RN and add the derived 799 /// information to @p LoopStack. 800 /// 801 /// In case @p RN is a BasicBlock or a non-affine Region, we construct the 802 /// schedule for this @p RN and also finalize loop schedules in case the 803 /// current @p RN completes the loop. 804 /// 805 /// In case @p RN is a not-non-affine Region, we delegate the construction to 806 /// buildSchedule(Region *R, ...). 807 /// 808 /// @param RN The RegionNode region traversed. 809 /// @param LoopStack A stack of loops that are currently under 810 /// construction. 811 void buildSchedule(RegionNode *RN, LoopStackTy &LoopStack); 812 813 public: 814 explicit ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA, 815 const DataLayout &DL, DominatorTree &DT, LoopInfo &LI, 816 ScopDetection &SD, ScalarEvolution &SE, 817 OptimizationRemarkEmitter &ORE); 818 ScopBuilder(const ScopBuilder &) = delete; 819 ScopBuilder &operator=(const ScopBuilder &) = delete; 820 ~ScopBuilder() = default; 821 822 /// Try to build the Polly IR of static control part on the current 823 /// SESE-Region. 824 /// 825 /// @return Give up the ownership of the scop object or static control part 826 /// for the region getScop()827 std::unique_ptr<Scop> getScop() { return std::move(scop); } 828 }; 829 } // end namespace polly 830 831 #endif // POLLY_SCOPBUILDER_H 832