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