1 //===-BlockGenerators.h - Helper to generate code for statements-*- 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 // This file defines the BlockGenerator and VectorBlockGenerator classes, which 10 // generate sequential code and vectorized code for a polyhedral statement, 11 // respectively. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef POLLY_BLOCK_GENERATORS_H 16 #define POLLY_BLOCK_GENERATORS_H 17 18 #include "polly/CodeGen/IRBuilder.h" 19 #include "polly/Support/ScopHelper.h" 20 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 21 #include "isl/isl-noexceptions.h" 22 23 namespace polly { 24 using llvm::AllocaInst; 25 using llvm::ArrayRef; 26 using llvm::AssertingVH; 27 using llvm::BasicBlock; 28 using llvm::BinaryOperator; 29 using llvm::CmpInst; 30 using llvm::DataLayout; 31 using llvm::DenseMap; 32 using llvm::DominatorTree; 33 using llvm::Function; 34 using llvm::Instruction; 35 using llvm::LoadInst; 36 using llvm::Loop; 37 using llvm::LoopInfo; 38 using llvm::LoopToScevMapT; 39 using llvm::MapVector; 40 using llvm::PHINode; 41 using llvm::ScalarEvolution; 42 using llvm::SetVector; 43 using llvm::SmallVector; 44 using llvm::StoreInst; 45 using llvm::StringRef; 46 using llvm::Type; 47 using llvm::UnaryInstruction; 48 using llvm::Value; 49 50 class MemoryAccess; 51 class ScopArrayInfo; 52 class IslExprBuilder; 53 54 /// Generate a new basic block for a polyhedral statement. 55 class BlockGenerator { 56 public: 57 typedef llvm::SmallVector<ValueMapT, 8> VectorValueMapT; 58 59 /// Map types to resolve scalar dependences. 60 /// 61 ///@{ 62 using AllocaMapTy = DenseMap<const ScopArrayInfo *, AssertingVH<AllocaInst>>; 63 64 /// Simple vector of instructions to store escape users. 65 using EscapeUserVectorTy = SmallVector<Instruction *, 4>; 66 67 /// Map type to resolve escaping users for scalar instructions. 68 /// 69 /// @see The EscapeMap member. 70 using EscapeUsersAllocaMapTy = 71 MapVector<Instruction *, 72 std::pair<AssertingVH<Value>, EscapeUserVectorTy>>; 73 74 ///@} 75 76 /// Create a generator for basic blocks. 77 /// 78 /// @param Builder The LLVM-IR Builder used to generate the statement. The 79 /// code is generated at the location, the Builder points 80 /// to. 81 /// @param LI The loop info for the current function 82 /// @param SE The scalar evolution info for the current function 83 /// @param DT The dominator tree of this function. 84 /// @param ScalarMap Map from scalars to their demoted location. 85 /// @param EscapeMap Map from scalars to their escape users and locations. 86 /// @param GlobalMap A mapping from llvm::Values used in the original scop 87 /// region to a new set of llvm::Values. Each reference to 88 /// an original value appearing in this mapping is replaced 89 /// with the new value it is mapped to. 90 /// @param ExprBuilder An expression builder to generate new access functions. 91 /// @param StartBlock The first basic block after the RTC. 92 BlockGenerator(PollyIRBuilder &Builder, LoopInfo &LI, ScalarEvolution &SE, 93 DominatorTree &DT, AllocaMapTy &ScalarMap, 94 EscapeUsersAllocaMapTy &EscapeMap, ValueMapT &GlobalMap, 95 IslExprBuilder *ExprBuilder, BasicBlock *StartBlock); 96 97 /// Copy the basic block. 98 /// 99 /// This copies the entire basic block and updates references to old values 100 /// with references to new values, as defined by GlobalMap. 101 /// 102 /// @param Stmt The block statement to code generate. 103 /// @param LTS A map from old loops to new induction variables as 104 /// SCEVs. 105 /// @param NewAccesses A map from memory access ids to new ast expressions, 106 /// which may contain new access expressions for certain 107 /// memory accesses. 108 void copyStmt(ScopStmt &Stmt, LoopToScevMapT <S, 109 isl_id_to_ast_expr *NewAccesses); 110 111 /// Remove a ScopArrayInfo's allocation from the ScalarMap. 112 /// 113 /// This function allows to remove values from the ScalarMap. This is useful 114 /// if the corresponding alloca instruction will be deleted (or moved into 115 /// another module), as without removing these values the underlying 116 /// AssertingVH will trigger due to us still keeping reference to this 117 /// scalar. 118 /// 119 /// @param Array The array for which the alloca was generated. 120 void freeScalarAlloc(ScopArrayInfo *Array) { ScalarMap.erase(Array); } 121 122 /// Return the alloca for @p Access. 123 /// 124 /// If no alloca was mapped for @p Access a new one is created. 125 /// 126 /// @param Access The memory access for which to generate the alloca. 127 /// 128 /// @returns The alloca for @p Access or a replacement value taken from 129 /// GlobalMap. 130 Value *getOrCreateAlloca(const MemoryAccess &Access); 131 132 /// Return the alloca for @p Array. 133 /// 134 /// If no alloca was mapped for @p Array a new one is created. 135 /// 136 /// @param Array The array for which to generate the alloca. 137 /// 138 /// @returns The alloca for @p Array or a replacement value taken from 139 /// GlobalMap. 140 Value *getOrCreateAlloca(const ScopArrayInfo *Array); 141 142 /// Finalize the code generation for the SCoP @p S. 143 /// 144 /// This will initialize and finalize the scalar variables we demoted during 145 /// the code generation. 146 /// 147 /// @see createScalarInitialization(Scop &) 148 /// @see createScalarFinalization(Region &) 149 void finalizeSCoP(Scop &S); 150 151 /// An empty destructor 152 virtual ~BlockGenerator() {} 153 154 BlockGenerator(const BlockGenerator &) = default; 155 156 protected: 157 PollyIRBuilder &Builder; 158 LoopInfo &LI; 159 ScalarEvolution &SE; 160 IslExprBuilder *ExprBuilder; 161 162 /// The dominator tree of this function. 163 DominatorTree &DT; 164 165 /// Relates to the region where the code is emitted into. 166 /// @{ 167 DominatorTree *GenDT; 168 LoopInfo *GenLI; 169 ScalarEvolution *GenSE; 170 /// @} 171 172 public: 173 /// Map to resolve scalar dependences for PHI operands and scalars. 174 /// 175 /// When translating code that contains scalar dependences as they result from 176 /// inter-block scalar dependences (including the use of data carrying PHI 177 /// nodes), we do not directly regenerate in-register SSA code, but instead 178 /// allocate some stack memory through which these scalar values are passed. 179 /// Only a later pass of -mem2reg will then (re)introduce in-register 180 /// computations. 181 /// 182 /// To keep track of the memory location(s) used to store the data computed by 183 /// a given SSA instruction, we use the map 'ScalarMap'. ScalarMap maps a 184 /// given ScopArrayInfo to the junk of stack allocated memory, that is 185 /// used for code generation. 186 /// 187 /// Up to two different ScopArrayInfo objects are associated with each 188 /// llvm::Value: 189 /// 190 /// MemoryType::Value objects are used for normal scalar dependences that go 191 /// from a scalar definition to its use. Such dependences are lowered by 192 /// directly writing the value an instruction computes into the corresponding 193 /// chunk of memory and reading it back from this chunk of memory right before 194 /// every use of this original scalar value. The memory allocations for 195 /// MemoryType::Value objects end with '.s2a'. 196 /// 197 /// MemoryType::PHI (and MemoryType::ExitPHI) objects are used to model PHI 198 /// nodes. For each PHI nodes we introduce, besides the Array of type 199 /// MemoryType::Value, a second chunk of memory into which we write at the end 200 /// of each basic block preceding the PHI instruction the value passed 201 /// through this basic block. At the place where the PHI node is executed, we 202 /// replace the PHI node with a load from the corresponding MemoryType::PHI 203 /// memory location. The memory allocations for MemoryType::PHI end with 204 /// '.phiops'. 205 /// 206 /// Example: 207 /// 208 /// Input C Code 209 /// ============ 210 /// 211 /// S1: x1 = ... 212 /// for (i=0...N) { 213 /// S2: x2 = phi(x1, add) 214 /// S3: add = x2 + 42; 215 /// } 216 /// S4: print(x1) 217 /// print(x2) 218 /// print(add) 219 /// 220 /// 221 /// Unmodified IR IR After expansion 222 /// ============= ================== 223 /// 224 /// S1: x1 = ... S1: x1 = ... 225 /// x1.s2a = s1 226 /// x2.phiops = s1 227 /// | | 228 /// | <--<--<--<--< | <--<--<--<--< 229 /// | / \ | / \ . 230 /// V V \ V V \ . 231 /// S2: x2 = phi (x1, add) | S2: x2 = x2.phiops | 232 /// | x2.s2a = x2 | 233 /// | | 234 /// S3: add = x2 + 42 | S3: add = x2 + 42 | 235 /// | add.s2a = add | 236 /// | x2.phiops = add | 237 /// | \ / | \ / 238 /// | \ / | \ / 239 /// | >-->-->-->--> | >-->-->-->--> 240 /// V V 241 /// 242 /// S4: x1 = x1.s2a 243 /// S4: ... = x1 ... = x1 244 /// x2 = x2.s2a 245 /// ... = x2 ... = x2 246 /// add = add.s2a 247 /// ... = add ... = add 248 /// 249 /// ScalarMap = { x1:Value -> x1.s2a, x2:Value -> x2.s2a, 250 /// add:Value -> add.s2a, x2:PHI -> x2.phiops } 251 /// 252 /// ??? Why does a PHI-node require two memory chunks ??? 253 /// 254 /// One may wonder why a PHI node requires two memory chunks and not just 255 /// all data is stored in a single location. The following example tries 256 /// to store all data in .s2a and drops the .phiops location: 257 /// 258 /// S1: x1 = ... 259 /// x1.s2a = s1 260 /// x2.s2a = s1 // use .s2a instead of .phiops 261 /// | 262 /// | <--<--<--<--< 263 /// | / \ . 264 /// V V \ . 265 /// S2: x2 = x2.s2a | // value is same as above, but read 266 /// | // from .s2a 267 /// | 268 /// x2.s2a = x2 | // store into .s2a as normal 269 /// | 270 /// S3: add = x2 + 42 | 271 /// add.s2a = add | 272 /// x2.s2a = add | // use s2a instead of .phiops 273 /// | \ / // !!! This is wrong, as x2.s2a now 274 /// | >-->-->-->--> // contains add instead of x2. 275 /// V 276 /// 277 /// S4: x1 = x1.s2a 278 /// ... = x1 279 /// x2 = x2.s2a // !!! We now read 'add' instead of 280 /// ... = x2 // 'x2' 281 /// add = add.s2a 282 /// ... = add 283 /// 284 /// As visible in the example, the SSA value of the PHI node may still be 285 /// needed _after_ the basic block, which could conceptually branch to the 286 /// PHI node, has been run and has overwritten the PHI's old value. Hence, a 287 /// single memory location is not enough to code-generate a PHI node. 288 /// 289 /// Memory locations used for the special PHI node modeling. 290 AllocaMapTy &ScalarMap; 291 292 /// Map from instructions to their escape users as well as the alloca. 293 EscapeUsersAllocaMapTy &EscapeMap; 294 295 /// A map from llvm::Values referenced in the old code to a new set of 296 /// llvm::Values, which is used to replace these old values during 297 /// code generation. 298 ValueMapT &GlobalMap; 299 300 /// The first basic block after the RTC. 301 BasicBlock *StartBlock; 302 303 /// Split @p BB to create a new one we can use to clone @p BB in. 304 BasicBlock *splitBB(BasicBlock *BB); 305 306 /// Change the function that code is emitted into. 307 void switchGeneratedFunc(Function *GenFn, DominatorTree *GenDT, 308 LoopInfo *GenLI, ScalarEvolution *GenSE); 309 310 /// Copy the given basic block. 311 /// 312 /// @param Stmt The statement to code generate. 313 /// @param BB The basic block to code generate. 314 /// @param BBMap A mapping from old values to their new values in this 315 /// block. 316 /// @param LTS A map from old loops to new induction variables as 317 /// SCEVs. 318 /// @param NewAccesses A map from memory access ids to new ast expressions, 319 /// which may contain new access expressions for certain 320 /// memory accesses. 321 /// 322 /// @returns The copy of the basic block. 323 BasicBlock *copyBB(ScopStmt &Stmt, BasicBlock *BB, ValueMapT &BBMap, 324 LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses); 325 326 /// Copy the given basic block. 327 /// 328 /// @param Stmt The statement to code generate. 329 /// @param BB The basic block to code generate. 330 /// @param BBCopy The new basic block to generate code in. 331 /// @param BBMap A mapping from old values to their new values in this 332 /// block. 333 /// @param LTS A map from old loops to new induction variables as 334 /// SCEVs. 335 /// @param NewAccesses A map from memory access ids to new ast expressions, 336 /// which may contain new access expressions for certain 337 /// memory accesses. 338 void copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *BBCopy, 339 ValueMapT &BBMap, LoopToScevMapT <S, 340 isl_id_to_ast_expr *NewAccesses); 341 342 /// Generate reload of scalars demoted to memory and needed by @p Stmt. 343 /// 344 /// @param Stmt The statement we generate code for. 345 /// @param LTS A mapping from loops virtual canonical induction 346 /// variable to their new values. 347 /// @param BBMap A mapping from old values to their new values in this block. 348 /// @param NewAccesses A map from memory access ids to new ast expressions. 349 void generateScalarLoads(ScopStmt &Stmt, LoopToScevMapT <S, 350 ValueMapT &BBMap, 351 __isl_keep isl_id_to_ast_expr *NewAccesses); 352 353 /// When statement tracing is enabled, build the print instructions for 354 /// printing the current statement instance. 355 /// 356 /// The printed output looks like: 357 /// 358 /// Stmt1(0) 359 /// 360 /// If printing of scalars is enabled, it also appends the value of each 361 /// scalar to the line: 362 /// 363 /// Stmt1(0) %i=1 %sum=5 364 /// 365 /// @param Stmt The statement we generate code for. 366 /// @param LTS A mapping from loops virtual canonical induction 367 /// variable to their new values. 368 /// @param BBMap A mapping from old values to their new values in this block. 369 void generateBeginStmtTrace(ScopStmt &Stmt, LoopToScevMapT <S, 370 ValueMapT &BBMap); 371 372 /// Generate instructions that compute whether one instance of @p Set is 373 /// executed. 374 /// 375 /// @param Stmt The statement we generate code for. 376 /// @param Subdomain A set in the space of @p Stmt's domain. Elements not in 377 /// @p Stmt's domain are ignored. 378 /// 379 /// @return An expression of type i1, generated into the current builder 380 /// position, that evaluates to 1 if the executed instance is part of 381 /// @p Set. 382 Value *buildContainsCondition(ScopStmt &Stmt, const isl::set &Subdomain); 383 384 /// Generate code that executes in a subset of @p Stmt's domain. 385 /// 386 /// @param Stmt The statement we generate code for. 387 /// @param Subdomain The condition for some code to be executed. 388 /// @param Subject A name for the code that is executed 389 /// conditionally. Used to name new basic blocks and 390 /// instructions. 391 /// @param GenThenFunc Callback which generates the code to be executed 392 /// when the current executed instance is in @p Set. The 393 /// IRBuilder's position is moved to within the block that 394 /// executes conditionally for this callback. 395 void generateConditionalExecution(ScopStmt &Stmt, const isl::set &Subdomain, 396 StringRef Subject, 397 const std::function<void()> &GenThenFunc); 398 399 /// Generate the scalar stores for the given statement. 400 /// 401 /// After the statement @p Stmt was copied all inner-SCoP scalar dependences 402 /// starting in @p Stmt (hence all scalar write accesses in @p Stmt) need to 403 /// be demoted to memory. 404 /// 405 /// @param Stmt The statement we generate code for. 406 /// @param LTS A mapping from loops virtual canonical induction 407 /// variable to their new values 408 /// (for values recalculated in the new ScoP, but not 409 /// within this basic block) 410 /// @param BBMap A mapping from old values to their new values in this block. 411 /// @param NewAccesses A map from memory access ids to new ast expressions. 412 virtual void generateScalarStores(ScopStmt &Stmt, LoopToScevMapT <S, 413 ValueMapT &BBMap, 414 __isl_keep isl_id_to_ast_expr *NewAccesses); 415 416 /// Handle users of @p Array outside the SCoP. 417 /// 418 /// @param S The current SCoP. 419 /// @param Inst The ScopArrayInfo to handle. 420 void handleOutsideUsers(const Scop &S, ScopArrayInfo *Array); 421 422 /// Find scalar statements that have outside users. 423 /// 424 /// We register these scalar values to later update subsequent scalar uses of 425 /// these values to either use the newly computed value from within the scop 426 /// (if the scop was executed) or the unchanged original code (if the run-time 427 /// check failed). 428 /// 429 /// @param S The scop for which to find the outside users. 430 void findOutsideUsers(Scop &S); 431 432 /// Initialize the memory of demoted scalars. 433 /// 434 /// @param S The scop for which to generate the scalar initializers. 435 void createScalarInitialization(Scop &S); 436 437 /// Create exit PHI node merges for PHI nodes with more than two edges 438 /// from inside the scop. 439 /// 440 /// For scops which have a PHI node in the exit block that has more than two 441 /// incoming edges from inside the scop region, we require some special 442 /// handling to understand which of the possible values will be passed to the 443 /// PHI node from inside the optimized version of the scop. To do so ScopInfo 444 /// models the possible incoming values as write accesses of the ScopStmts. 445 /// 446 /// This function creates corresponding code to reload the computed outgoing 447 /// value from the stack slot it has been stored into and to pass it on to the 448 /// PHI node in the original exit block. 449 /// 450 /// @param S The scop for which to generate the exiting PHI nodes. 451 void createExitPHINodeMerges(Scop &S); 452 453 /// Promote the values of demoted scalars after the SCoP. 454 /// 455 /// If a scalar value was used outside the SCoP we need to promote the value 456 /// stored in the memory cell allocated for that scalar and combine it with 457 /// the original value in the non-optimized SCoP. 458 void createScalarFinalization(Scop &S); 459 460 /// Try to synthesize a new value 461 /// 462 /// Given an old value, we try to synthesize it in a new context from its 463 /// original SCEV expression. We start from the original SCEV expression, 464 /// then replace outdated parameter and loop references, and finally 465 /// expand it to code that computes this updated expression. 466 /// 467 /// @param Stmt The statement to code generate 468 /// @param Old The old Value 469 /// @param BBMap A mapping from old values to their new values 470 /// (for values recalculated within this basic block) 471 /// @param LTS A mapping from loops virtual canonical induction 472 /// variable to their new values 473 /// (for values recalculated in the new ScoP, but not 474 /// within this basic block) 475 /// @param L The loop that surrounded the instruction that referenced 476 /// this value in the original code. This loop is used to 477 /// evaluate the scalar evolution at the right scope. 478 /// 479 /// @returns o A newly synthesized value. 480 /// o NULL, if synthesizing the value failed. 481 Value *trySynthesizeNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap, 482 LoopToScevMapT <S, Loop *L) const; 483 484 /// Get the new version of a value. 485 /// 486 /// Given an old value, we first check if a new version of this value is 487 /// available in the BBMap or GlobalMap. In case it is not and the value can 488 /// be recomputed using SCEV, we do so. If we can not recompute a value 489 /// using SCEV, but we understand that the value is constant within the scop, 490 /// we return the old value. If the value can still not be derived, this 491 /// function will assert. 492 /// 493 /// @param Stmt The statement to code generate. 494 /// @param Old The old Value. 495 /// @param BBMap A mapping from old values to their new values 496 /// (for values recalculated within this basic block). 497 /// @param LTS A mapping from loops virtual canonical induction 498 /// variable to their new values 499 /// (for values recalculated in the new ScoP, but not 500 /// within this basic block). 501 /// @param L The loop that surrounded the instruction that referenced 502 /// this value in the original code. This loop is used to 503 /// evaluate the scalar evolution at the right scope. 504 /// 505 /// @returns o The old value, if it is still valid. 506 /// o The new value, if available. 507 /// o NULL, if no value is found. 508 Value *getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap, 509 LoopToScevMapT <S, Loop *L) const; 510 511 void copyInstScalar(ScopStmt &Stmt, Instruction *Inst, ValueMapT &BBMap, 512 LoopToScevMapT <S); 513 514 /// Get the innermost loop that surrounds the statement @p Stmt. 515 Loop *getLoopForStmt(const ScopStmt &Stmt) const; 516 517 /// Generate the operand address 518 /// @param NewAccesses A map from memory access ids to new ast expressions, 519 /// which may contain new access expressions for certain 520 /// memory accesses. 521 Value *generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst, 522 ValueMapT &BBMap, LoopToScevMapT <S, 523 isl_id_to_ast_expr *NewAccesses); 524 525 /// Generate the operand address. 526 /// 527 /// @param Stmt The statement to generate code for. 528 /// @param L The innermost loop that surrounds the statement. 529 /// @param Pointer If the access expression is not changed (ie. not found 530 /// in @p LTS), use this Pointer from the original code 531 /// instead. 532 /// @param BBMap A mapping from old values to their new values. 533 /// @param LTS A mapping from loops virtual canonical induction 534 /// variable to their new values. 535 /// @param NewAccesses Ahead-of-time generated access expressions. 536 /// @param Id Identifier of the MemoryAccess to generate. 537 /// @param ExpectedType The type the returned value should have. 538 /// 539 /// @return The generated address. 540 Value *generateLocationAccessed(ScopStmt &Stmt, Loop *L, Value *Pointer, 541 ValueMapT &BBMap, LoopToScevMapT <S, 542 isl_id_to_ast_expr *NewAccesses, 543 __isl_take isl_id *Id, Type *ExpectedType); 544 545 /// Generate the pointer value that is accesses by @p Access. 546 /// 547 /// For write accesses, generate the target address. For read accesses, 548 /// generate the source address. 549 /// The access can be either an array access or a scalar access. In the first 550 /// case, the returned address will point to an element into that array. In 551 /// the scalar case, an alloca is used. 552 /// If a new AccessRelation is set for the MemoryAccess, the new relation will 553 /// be used. 554 /// 555 /// @param Access The access to generate a pointer for. 556 /// @param L The innermost loop that surrounds the statement. 557 /// @param LTS A mapping from loops virtual canonical induction 558 /// variable to their new values. 559 /// @param BBMap A mapping from old values to their new values. 560 /// @param NewAccesses A map from memory access ids to new ast expressions. 561 /// 562 /// @return The generated address. 563 Value *getImplicitAddress(MemoryAccess &Access, Loop *L, LoopToScevMapT <S, 564 ValueMapT &BBMap, 565 __isl_keep isl_id_to_ast_expr *NewAccesses); 566 567 /// @param NewAccesses A map from memory access ids to new ast expressions, 568 /// which may contain new access expressions for certain 569 /// memory accesses. 570 Value *generateArrayLoad(ScopStmt &Stmt, LoadInst *load, ValueMapT &BBMap, 571 LoopToScevMapT <S, 572 isl_id_to_ast_expr *NewAccesses); 573 574 /// @param NewAccesses A map from memory access ids to new ast expressions, 575 /// which may contain new access expressions for certain 576 /// memory accesses. 577 void generateArrayStore(ScopStmt &Stmt, StoreInst *store, ValueMapT &BBMap, 578 LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses); 579 580 /// Copy a single PHI instruction. 581 /// 582 /// The implementation in the BlockGenerator is trivial, however it allows 583 /// subclasses to handle PHIs different. 584 virtual void copyPHIInstruction(ScopStmt &, PHINode *, ValueMapT &, 585 LoopToScevMapT &) {} 586 587 /// Copy a single Instruction. 588 /// 589 /// This copies a single Instruction and updates references to old values 590 /// with references to new values, as defined by GlobalMap and BBMap. 591 /// 592 /// @param Stmt The statement to code generate. 593 /// @param Inst The instruction to copy. 594 /// @param BBMap A mapping from old values to their new values 595 /// (for values recalculated within this basic block). 596 /// @param GlobalMap A mapping from old values to their new values 597 /// (for values recalculated in the new ScoP, but not 598 /// within this basic block). 599 /// @param LTS A mapping from loops virtual canonical induction 600 /// variable to their new values 601 /// (for values recalculated in the new ScoP, but not 602 /// within this basic block). 603 /// @param NewAccesses A map from memory access ids to new ast expressions, 604 /// which may contain new access expressions for certain 605 /// memory accesses. 606 void copyInstruction(ScopStmt &Stmt, Instruction *Inst, ValueMapT &BBMap, 607 LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses); 608 609 /// Helper to determine if @p Inst can be synthesized in @p Stmt. 610 /// 611 /// @returns false, iff @p Inst can be synthesized in @p Stmt. 612 bool canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst); 613 614 /// Remove dead instructions generated for BB 615 /// 616 /// @param BB The basic block code for which code has been generated. 617 /// @param BBMap A local map from old to new instructions. 618 void removeDeadInstructions(BasicBlock *BB, ValueMapT &BBMap); 619 620 /// Invalidate the scalar evolution expressions for a scop. 621 /// 622 /// This function invalidates the scalar evolution results for all 623 /// instructions that are part of a given scop, and the loops 624 /// surrounding the users of merge blocks. This is necessary to ensure that 625 /// later scops do not obtain scalar evolution expressions that reference 626 /// values that earlier dominated the later scop, but have been moved in the 627 /// conditional part of an earlier scop and consequently do not any more 628 /// dominate the later scop. 629 /// 630 /// @param S The scop to invalidate. 631 void invalidateScalarEvolution(Scop &S); 632 }; 633 634 /// Generator for new versions of polyhedral region statements. 635 class RegionGenerator final : public BlockGenerator { 636 public: 637 /// Create a generator for regions. 638 /// 639 /// @param BlockGen A generator for basic blocks. 640 RegionGenerator(BlockGenerator &BlockGen) : BlockGenerator(BlockGen) {} 641 642 virtual ~RegionGenerator() {} 643 644 /// Copy the region statement @p Stmt. 645 /// 646 /// This copies the entire region represented by @p Stmt and updates 647 /// references to old values with references to new values, as defined by 648 /// GlobalMap. 649 /// 650 /// @param Stmt The statement to code generate. 651 /// @param LTS A map from old loops to new induction variables as SCEVs. 652 void copyStmt(ScopStmt &Stmt, LoopToScevMapT <S, 653 __isl_keep isl_id_to_ast_expr *IdToAstExp); 654 655 private: 656 /// A map from old to the first new block in the region, that was created to 657 /// model the old basic block. 658 DenseMap<BasicBlock *, BasicBlock *> StartBlockMap; 659 660 /// A map from old to the last new block in the region, that was created to 661 /// model the old basic block. 662 DenseMap<BasicBlock *, BasicBlock *> EndBlockMap; 663 664 /// The "BBMaps" for the whole region (one for each block). In case a basic 665 /// block is code generated to multiple basic blocks (e.g., for partial 666 /// writes), the StartBasic is used as index for the RegionMap. 667 DenseMap<BasicBlock *, ValueMapT> RegionMaps; 668 669 /// Mapping to remember PHI nodes that still need incoming values. 670 using PHINodePairTy = std::pair<PHINode *, PHINode *>; 671 DenseMap<BasicBlock *, SmallVector<PHINodePairTy, 4>> IncompletePHINodeMap; 672 673 /// Repair the dominance tree after we created a copy block for @p BB. 674 /// 675 /// @returns The immediate dominator in the DT for @p BBCopy if in the region. 676 BasicBlock *repairDominance(BasicBlock *BB, BasicBlock *BBCopy); 677 678 /// Add the new operand from the copy of @p IncomingBB to @p PHICopy. 679 /// 680 /// PHI nodes, which may have (multiple) edges that enter from outside the 681 /// non-affine subregion and even from outside the scop, are code generated as 682 /// follows: 683 /// 684 /// # Original 685 /// 686 /// Region: %A-> %exit 687 /// NonAffine Stmt: %nonaffB -> %D (includes %nonaffB, %nonaffC) 688 /// 689 /// pre: 690 /// %val = add i64 1, 1 691 /// 692 /// A: 693 /// br label %nonaff 694 /// 695 /// nonaffB: 696 /// %phi = phi i64 [%val, %A], [%valC, %nonAffC], [%valD, %D] 697 /// %cmp = <nonaff> 698 /// br i1 %cmp, label %C, label %nonaffC 699 /// 700 /// nonaffC: 701 /// %valC = add i64 1, 1 702 /// br i1 undef, label %D, label %nonaffB 703 /// 704 /// D: 705 /// %valD = ... 706 /// %exit_cond = <loopexit> 707 /// br i1 %exit_cond, label %nonaffB, label %exit 708 /// 709 /// exit: 710 /// ... 711 /// 712 /// - %start and %C enter from outside the non-affine region. 713 /// - %nonaffC enters from within the non-affine region. 714 /// 715 /// # New 716 /// 717 /// polly.A: 718 /// store i64 %val, i64* %phi.phiops 719 /// br label %polly.nonaffA.entry 720 /// 721 /// polly.nonaffB.entry: 722 /// %phi.phiops.reload = load i64, i64* %phi.phiops 723 /// br label %nonaffB 724 /// 725 /// polly.nonaffB: 726 /// %polly.phi = [%phi.phiops.reload, %nonaffB.entry], 727 /// [%p.valC, %polly.nonaffC] 728 /// 729 /// polly.nonaffC: 730 /// %p.valC = add i64 1, 1 731 /// br i1 undef, label %polly.D, label %polly.nonaffB 732 /// 733 /// polly.D: 734 /// %p.valD = ... 735 /// store i64 %p.valD, i64* %phi.phiops 736 /// %p.exit_cond = <loopexit> 737 /// br i1 %p.exit_cond, label %polly.nonaffB, label %exit 738 /// 739 /// Values that enter the PHI from outside the non-affine region are stored 740 /// into the stack slot %phi.phiops by statements %polly.A and %polly.D and 741 /// reloaded in %polly.nonaffB.entry, a basic block generated before the 742 /// actual non-affine region. 743 /// 744 /// When generating the PHI node of the non-affine region in %polly.nonaffB, 745 /// incoming edges from outside the region are combined into a single branch 746 /// from %polly.nonaffB.entry which has as incoming value the value reloaded 747 /// from the %phi.phiops stack slot. Incoming edges from within the region 748 /// refer to the copied instructions (%p.valC) and basic blocks 749 /// (%polly.nonaffC) of the non-affine region. 750 /// 751 /// @param Stmt The statement to code generate. 752 /// @param PHI The original PHI we copy. 753 /// @param PHICopy The copy of @p PHI. 754 /// @param IncomingBB An incoming block of @p PHI. 755 /// @param LTS A map from old loops to new induction variables as 756 /// SCEVs. 757 void addOperandToPHI(ScopStmt &Stmt, PHINode *PHI, PHINode *PHICopy, 758 BasicBlock *IncomingBB, LoopToScevMapT <S); 759 760 /// Create a PHI that combines the incoming values from all incoming blocks 761 /// that are in the subregion. 762 /// 763 /// PHIs in the subregion's exit block can have incoming edges from within and 764 /// outside the subregion. This function combines the incoming values from 765 /// within the subregion to appear as if there is only one incoming edge from 766 /// the subregion (an additional exit block is created by RegionGenerator). 767 /// This is to avoid that a value is written to the .phiops location without 768 /// leaving the subregion because the exiting block as an edge back into the 769 /// subregion. 770 /// 771 /// @param MA The WRITE of MemoryKind::PHI/MemoryKind::ExitPHI for a PHI in 772 /// the subregion's exit block. 773 /// @param LTS Virtual induction variable mapping. 774 /// @param BBMap A mapping from old values to their new values in this block. 775 /// @param L Loop surrounding this region statement. 776 /// 777 /// @returns The constructed PHI node. 778 PHINode *buildExitPHI(MemoryAccess *MA, LoopToScevMapT <S, ValueMapT &BBMap, 779 Loop *L); 780 781 /// @param Return the new value of a scalar write, creating a PHINode if 782 /// necessary. 783 /// 784 /// @param MA A scalar WRITE MemoryAccess. 785 /// @param LTS Virtual induction variable mapping. 786 /// @param BBMap A mapping from old values to their new values in this block. 787 /// 788 /// @returns The effective value of @p MA's written value when leaving the 789 /// subregion. 790 /// @see buildExitPHI 791 Value *getExitScalar(MemoryAccess *MA, LoopToScevMapT <S, ValueMapT &BBMap); 792 793 /// Generate the scalar stores for the given statement. 794 /// 795 /// After the statement @p Stmt was copied all inner-SCoP scalar dependences 796 /// starting in @p Stmt (hence all scalar write accesses in @p Stmt) need to 797 /// be demoted to memory. 798 /// 799 /// @param Stmt The statement we generate code for. 800 /// @param LTS A mapping from loops virtual canonical induction variable to 801 /// their new values (for values recalculated in the new ScoP, 802 /// but not within this basic block) 803 /// @param BBMap A mapping from old values to their new values in this block. 804 /// @param LTS A mapping from loops virtual canonical induction variable to 805 /// their new values. 806 void 807 generateScalarStores(ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMAp, 808 __isl_keep isl_id_to_ast_expr *NewAccesses) override; 809 810 /// Copy a single PHI instruction. 811 /// 812 /// This copies a single PHI instruction and updates references to old values 813 /// with references to new values, as defined by GlobalMap and BBMap. 814 /// 815 /// @param Stmt The statement to code generate. 816 /// @param PHI The PHI instruction to copy. 817 /// @param BBMap A mapping from old values to their new values 818 /// (for values recalculated within this basic block). 819 /// @param LTS A map from old loops to new induction variables as SCEVs. 820 void copyPHIInstruction(ScopStmt &Stmt, PHINode *Inst, ValueMapT &BBMap, 821 LoopToScevMapT <S) override; 822 }; 823 } // namespace polly 824 #endif 825