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