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