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 S The current SCoP. 390 /// @param Inst The current instruction we check. 391 void handleOutsideUsers(const Scop &S, Instruction *Inst); 392 393 /// @brief Find scalar statements that have outside users. 394 /// 395 /// We register these scalar values to later update subsequent scalar uses of 396 /// these values to either use the newly computed value from within the scop 397 /// (if the scop was executed) or the unchanged original code (if the run-time 398 /// check failed). 399 /// 400 /// @param S The scop for which to find the outside users. 401 void findOutsideUsers(Scop &S); 402 403 /// @brief Initialize the memory of demoted scalars. 404 /// 405 /// @param S The scop for which to generate the scalar initializers. 406 void createScalarInitialization(Scop &S); 407 408 /// @brief Create exit PHI node merges for PHI nodes with more than two edges 409 /// from inside the scop. 410 /// 411 /// For scops which have a PHI node in the exit block that has more than two 412 /// incoming edges from inside the scop region, we require some special 413 /// handling to understand which of the possible values will be passed to the 414 /// PHI node from inside the optimized version of the scop. To do so ScopInfo 415 /// models the possible incoming values as write accesses of the ScopStmts. 416 /// 417 /// This function creates corresponding code to reload the computed outgoing 418 /// value from the stack slot it has been stored into and to pass it on to the 419 /// PHI node in the original exit block. 420 /// 421 /// @param S The scop for which to generate the exiting PHI nodes. 422 void createExitPHINodeMerges(Scop &S); 423 424 /// @brief Promote the values of demoted scalars after the SCoP. 425 /// 426 /// If a scalar value was used outside the SCoP we need to promote the value 427 /// stored in the memory cell allocated for that scalar and combine it with 428 /// the original value in the non-optimized SCoP. 429 void createScalarFinalization(Scop &S); 430 431 /// @brief Try to synthesize a new value 432 /// 433 /// Given an old value, we try to synthesize it in a new context from its 434 /// original SCEV expression. We start from the original SCEV expression, 435 /// then replace outdated parameter and loop references, and finally 436 /// expand it to code that computes this updated expression. 437 /// 438 /// @param Stmt The statement to code generate 439 /// @param Old The old Value 440 /// @param BBMap A mapping from old values to their new values 441 /// (for values recalculated within this basic block) 442 /// @param LTS A mapping from loops virtual canonical induction 443 /// variable to their new values 444 /// (for values recalculated in the new ScoP, but not 445 /// within this basic block) 446 /// @param L The loop that surrounded the instruction that referenced 447 /// this value in the original code. This loop is used to 448 /// evaluate the scalar evolution at the right scope. 449 /// 450 /// @returns o A newly synthesized value. 451 /// o NULL, if synthesizing the value failed. 452 Value *trySynthesizeNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap, 453 LoopToScevMapT <S, Loop *L) const; 454 455 /// @brief Get the new version of a value. 456 /// 457 /// Given an old value, we first check if a new version of this value is 458 /// available in the BBMap or GlobalMap. In case it is not and the value can 459 /// be recomputed using SCEV, we do so. If we can not recompute a value 460 /// using SCEV, but we understand that the value is constant within the scop, 461 /// we return the old value. If the value can still not be derived, this 462 /// function will assert. 463 /// 464 /// @param Stmt The statement to code generate. 465 /// @param Old The old Value. 466 /// @param BBMap A mapping from old values to their new values 467 /// (for values recalculated within this basic block). 468 /// @param LTS A mapping from loops virtual canonical induction 469 /// variable to their new values 470 /// (for values recalculated in the new ScoP, but not 471 /// within this basic block). 472 /// @param L The loop that surrounded the instruction that referenced 473 /// this value in the original code. This loop is used to 474 /// evaluate the scalar evolution at the right scope. 475 /// 476 /// @returns o The old value, if it is still valid. 477 /// o The new value, if available. 478 /// o NULL, if no value is found. 479 Value *getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap, 480 LoopToScevMapT <S, Loop *L) const; 481 482 void copyInstScalar(ScopStmt &Stmt, Instruction *Inst, ValueMapT &BBMap, 483 LoopToScevMapT <S); 484 485 /// @brief Get the innermost loop that surrounds the statement @p Stmt. 486 Loop *getLoopForStmt(const ScopStmt &Stmt) const; 487 488 /// @brief Generate the operand address 489 /// @param NewAccesses A map from memory access ids to new ast expressions, 490 /// which may contain new access expressions for certain 491 /// memory accesses. 492 Value *generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst, 493 ValueMapT &BBMap, LoopToScevMapT <S, 494 isl_id_to_ast_expr *NewAccesses); 495 496 /// @param NewAccesses A map from memory access ids to new ast expressions, 497 /// which may contain new access expressions for certain 498 /// memory accesses. 499 Value *generateScalarLoad(ScopStmt &Stmt, LoadInst *load, ValueMapT &BBMap, 500 LoopToScevMapT <S, 501 isl_id_to_ast_expr *NewAccesses); 502 503 /// @param NewAccesses A map from memory access ids to new ast expressions, 504 /// which may contain new access expressions for certain 505 /// memory accesses. 506 void generateScalarStore(ScopStmt &Stmt, StoreInst *store, ValueMapT &BBMap, 507 LoopToScevMapT <S, 508 isl_id_to_ast_expr *NewAccesses); 509 510 /// @brief Copy a single PHI instruction. 511 /// 512 /// The implementation in the BlockGenerator is trivial, however it allows 513 /// subclasses to handle PHIs different. 514 virtual void copyPHIInstruction(ScopStmt &, PHINode *, ValueMapT &, 515 LoopToScevMapT &) {} 516 517 /// @brief Copy a single Instruction. 518 /// 519 /// This copies a single Instruction and updates references to old values 520 /// with references to new values, as defined by GlobalMap and BBMap. 521 /// 522 /// @param Stmt The statement to code generate. 523 /// @param Inst The instruction to copy. 524 /// @param BBMap A mapping from old values to their new values 525 /// (for values recalculated within this basic block). 526 /// @param GlobalMap A mapping from old values to their new values 527 /// (for values recalculated in the new ScoP, but not 528 /// within this basic block). 529 /// @param LTS A mapping from loops virtual canonical induction 530 /// variable to their new values 531 /// (for values recalculated in the new ScoP, but not 532 /// within this basic block). 533 /// @param NewAccesses A map from memory access ids to new ast expressions, 534 /// which may contain new access expressions for certain 535 /// memory accesses. 536 void copyInstruction(ScopStmt &Stmt, Instruction *Inst, ValueMapT &BBMap, 537 LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses); 538 539 /// @brief Helper to determine if @p Inst can be synthezised in @p Stmt. 540 /// 541 /// @returns false, iff @p Inst can be synthesized in @p Stmt. 542 bool canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst); 543 }; 544 545 /// @brief Generate a new vector basic block for a polyhedral statement. 546 /// 547 /// The only public function exposed is generate(). 548 class VectorBlockGenerator : BlockGenerator { 549 public: 550 /// @brief Generate a new vector basic block for a ScoPStmt. 551 /// 552 /// This code generation is similar to the normal, scalar code generation, 553 /// except that each instruction is code generated for several vector lanes 554 /// at a time. If possible instructions are issued as actual vector 555 /// instructions, but e.g. for address calculation instructions we currently 556 /// generate scalar instructions for each vector lane. 557 /// 558 /// @param BlockGen A block generator object used as parent. 559 /// @param Stmt The statement to code generate. 560 /// @param VLTS A mapping from loops virtual canonical induction 561 /// variable to their new values 562 /// (for values recalculated in the new ScoP, but not 563 /// within this basic block), one for each lane. 564 /// @param Schedule A map from the statement to a schedule where the 565 /// innermost dimension is the dimension of the innermost 566 /// loop containing the statemenet. 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 static void generate(BlockGenerator &BlockGen, ScopStmt &Stmt, 571 std::vector<LoopToScevMapT> &VLTS, 572 __isl_keep isl_map *Schedule, 573 __isl_keep isl_id_to_ast_expr *NewAccesses) { 574 VectorBlockGenerator Generator(BlockGen, VLTS, Schedule); 575 Generator.copyStmt(Stmt, NewAccesses); 576 } 577 578 private: 579 // This is a vector of loop->scev maps. The first map is used for the first 580 // vector lane, ... 581 // Each map, contains information about Instructions in the old ScoP, which 582 // are recalculated in the new SCoP. When copying the basic block, we replace 583 // all referenes to the old instructions with their recalculated values. 584 // 585 // For example, when the code generator produces this AST: 586 // 587 // for (int c1 = 0; c1 <= 1023; c1 += 1) 588 // for (int c2 = 0; c2 <= 1023; c2 += VF) 589 // for (int lane = 0; lane <= VF; lane += 1) 590 // Stmt(c2 + lane + 3, c1); 591 // 592 // VLTS[lane] contains a map: 593 // "outer loop in the old loop nest" -> SCEV("c2 + lane + 3"), 594 // "inner loop in the old loop nest" -> SCEV("c1"). 595 std::vector<LoopToScevMapT> &VLTS; 596 597 // A map from the statement to a schedule where the innermost dimension is the 598 // dimension of the innermost loop containing the statemenet. 599 isl_map *Schedule; 600 601 VectorBlockGenerator(BlockGenerator &BlockGen, 602 std::vector<LoopToScevMapT> &VLTS, 603 __isl_keep isl_map *Schedule); 604 605 int getVectorWidth(); 606 607 Value *getVectorValue(ScopStmt &Stmt, Value *Old, ValueMapT &VectorMap, 608 VectorValueMapT &ScalarMaps, Loop *L); 609 610 Type *getVectorPtrTy(const Value *V, int Width); 611 612 /// @brief Load a vector from a set of adjacent scalars 613 /// 614 /// In case a set of scalars is known to be next to each other in memory, 615 /// create a vector load that loads those scalars 616 /// 617 /// %vector_ptr= bitcast double* %p to <4 x double>* 618 /// %vec_full = load <4 x double>* %vector_ptr 619 /// 620 /// @param Stmt The statement to code generate. 621 /// @param NegativeStride This is used to indicate a -1 stride. In such 622 /// a case we load the end of a base address and 623 /// shuffle the accesses in reverse order into the 624 /// vector. By default we would do only positive 625 /// strides. 626 /// 627 /// @param NewAccesses A map from memory access ids to new ast 628 /// expressions, which may contain new access 629 /// expressions for certain memory accesses. 630 Value *generateStrideOneLoad(ScopStmt &Stmt, LoadInst *Load, 631 VectorValueMapT &ScalarMaps, 632 __isl_keep isl_id_to_ast_expr *NewAccesses, 633 bool NegativeStride); 634 635 /// @brief Load a vector initialized from a single scalar in memory 636 /// 637 /// In case all elements of a vector are initialized to the same 638 /// scalar value, this value is loaded and shuffeled into all elements 639 /// of the vector. 640 /// 641 /// %splat_one = load <1 x double>* %p 642 /// %splat = shufflevector <1 x double> %splat_one, <1 x 643 /// double> %splat_one, <4 x i32> zeroinitializer 644 /// 645 /// @param NewAccesses A map from memory access ids to new ast expressions, 646 /// which may contain new access expressions for certain 647 /// memory accesses. 648 Value *generateStrideZeroLoad(ScopStmt &Stmt, LoadInst *Load, 649 ValueMapT &BBMap, 650 __isl_keep isl_id_to_ast_expr *NewAccesses); 651 652 /// @brief Load a vector from scalars distributed in memory 653 /// 654 /// In case some scalars a distributed randomly in memory. Create a vector 655 /// by loading each scalar and by inserting one after the other into the 656 /// vector. 657 /// 658 /// %scalar_1= load double* %p_1 659 /// %vec_1 = insertelement <2 x double> undef, double %scalar_1, i32 0 660 /// %scalar 2 = load double* %p_2 661 /// %vec_2 = insertelement <2 x double> %vec_1, double %scalar_1, i32 1 662 /// 663 /// @param NewAccesses A map from memory access ids to new ast expressions, 664 /// which may contain new access expressions for certain 665 /// memory accesses. 666 Value *generateUnknownStrideLoad(ScopStmt &Stmt, LoadInst *Load, 667 VectorValueMapT &ScalarMaps, 668 __isl_keep isl_id_to_ast_expr *NewAccesses); 669 670 /// @param NewAccesses A map from memory access ids to new ast expressions, 671 /// which may contain new access expressions for certain 672 /// memory accesses. 673 void generateLoad(ScopStmt &Stmt, LoadInst *Load, ValueMapT &VectorMap, 674 VectorValueMapT &ScalarMaps, 675 __isl_keep isl_id_to_ast_expr *NewAccesses); 676 677 void copyUnaryInst(ScopStmt &Stmt, UnaryInstruction *Inst, 678 ValueMapT &VectorMap, VectorValueMapT &ScalarMaps); 679 680 void copyBinaryInst(ScopStmt &Stmt, BinaryOperator *Inst, 681 ValueMapT &VectorMap, VectorValueMapT &ScalarMaps); 682 683 /// @param NewAccesses A map from memory access ids to new ast expressions, 684 /// which may contain new access expressions for certain 685 /// memory accesses. 686 void copyStore(ScopStmt &Stmt, StoreInst *Store, ValueMapT &VectorMap, 687 VectorValueMapT &ScalarMaps, 688 __isl_keep isl_id_to_ast_expr *NewAccesses); 689 690 /// @param NewAccesses A map from memory access ids to new ast expressions, 691 /// which may contain new access expressions for certain 692 /// memory accesses. 693 void copyInstScalarized(ScopStmt &Stmt, Instruction *Inst, 694 ValueMapT &VectorMap, VectorValueMapT &ScalarMaps, 695 __isl_keep isl_id_to_ast_expr *NewAccesses); 696 697 bool extractScalarValues(const Instruction *Inst, ValueMapT &VectorMap, 698 VectorValueMapT &ScalarMaps); 699 700 bool hasVectorOperands(const Instruction *Inst, ValueMapT &VectorMap); 701 702 /// @brief Generate vector loads for scalars. 703 /// 704 /// @param Stmt The scop statement for which to generate the loads. 705 /// @param VectorBlockMap A map that will be updated to relate the original 706 /// values with the newly generated vector loads. 707 void generateScalarVectorLoads(ScopStmt &Stmt, ValueMapT &VectorBlockMap); 708 709 /// @brief Verify absence of scalar stores. 710 /// 711 /// @param Stmt The scop statement to check for scalar stores. 712 void verifyNoScalarStores(ScopStmt &Stmt); 713 714 /// @param NewAccesses A map from memory access ids to new ast expressions, 715 /// which may contain new access expressions for certain 716 /// memory accesses. 717 void copyInstruction(ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap, 718 VectorValueMapT &ScalarMaps, 719 __isl_keep isl_id_to_ast_expr *NewAccesses); 720 721 /// @param NewAccesses A map from memory access ids to new ast expressions, 722 /// which may contain new access expressions for certain 723 /// memory accesses. 724 void copyStmt(ScopStmt &Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses); 725 }; 726 727 /// @brief Generator for new versions of polyhedral region statements. 728 class RegionGenerator : public BlockGenerator { 729 public: 730 /// @brief Create a generator for regions. 731 /// 732 /// @param BlockGen A generator for basic blocks. 733 RegionGenerator(BlockGenerator &BlockGen) : BlockGenerator(BlockGen) {} 734 735 virtual ~RegionGenerator(){}; 736 737 /// @brief Copy the region statement @p Stmt. 738 /// 739 /// This copies the entire region represented by @p Stmt and updates 740 /// references to old values with references to new values, as defined by 741 /// GlobalMap. 742 /// 743 /// @param Stmt The statement to code generate. 744 /// @param LTS A map from old loops to new induction variables as SCEVs. 745 void copyStmt(ScopStmt &Stmt, LoopToScevMapT <S, 746 __isl_keep isl_id_to_ast_expr *IdToAstExp); 747 748 private: 749 /// @brief A map from old to new blocks in the region. 750 DenseMap<BasicBlock *, BasicBlock *> BlockMap; 751 752 /// @brief The "BBMaps" for the whole region (one for each block). 753 DenseMap<BasicBlock *, ValueMapT> RegionMaps; 754 755 /// @brief Mapping to remember PHI nodes that still need incoming values. 756 using PHINodePairTy = std::pair<const PHINode *, PHINode *>; 757 DenseMap<BasicBlock *, SmallVector<PHINodePairTy, 4>> IncompletePHINodeMap; 758 759 /// @brief Repair the dominance tree after we created a copy block for @p BB. 760 /// 761 /// @returns The immediate dominator in the DT for @p BBCopy if in the region. 762 BasicBlock *repairDominance(BasicBlock *BB, BasicBlock *BBCopy); 763 764 /// @brief Add the new operand from the copy of @p IncomingBB to @p PHICopy. 765 /// 766 /// @param Stmt The statement to code generate. 767 /// @param PHI The original PHI we copy. 768 /// @param PHICopy The copy of @p PHI. 769 /// @param IncomingBB An incoming block of @p PHI. 770 /// @param LTS A map from old loops to new induction variables as 771 /// SCEVs. 772 void addOperandToPHI(ScopStmt &Stmt, const PHINode *PHI, PHINode *PHICopy, 773 BasicBlock *IncomingBB, LoopToScevMapT <S); 774 775 /// @brief Create a PHI that combines the incoming values from all incoming 776 /// blocks that are in the subregion. 777 /// 778 /// PHIs in the subregion's exit block can have incoming edges from within and 779 /// outside the subregion. This function combines the incoming values from 780 /// within the subregion to appear as if there is only one incoming edge from 781 /// the subregion (an additional exit block is created by RegionGenerator). 782 /// This is to avoid that a value is written to the .phiops location without 783 /// leaving the subregion because the exiting block as an edge back into the 784 /// subregion. 785 /// 786 /// @param MA The WRITE of MK_PHI/MK_ExitPHI for a PHI in the subregion's 787 /// exit block. 788 /// @param LTS Virtual induction variable mapping. 789 /// @param BBMap A mapping from old values to their new values in this block. 790 /// @param L Loop surrounding this region statement. 791 /// 792 /// @returns The constructed PHI node. 793 PHINode *buildExitPHI(MemoryAccess *MA, LoopToScevMapT <S, ValueMapT &BBMap, 794 Loop *L); 795 796 /// @param Return the new value of a scalar write, creating a PHINode if 797 /// necessary. 798 /// 799 /// @param MA A scalar WRITE MemoryAccess. 800 /// @param LTS Virtual induction variable mapping. 801 /// @param BBMap A mapping from old values to their new values in this block. 802 /// 803 /// @returns The effective value of @p MA's written value when leaving the 804 /// subregion. 805 /// @see buildExitPHI 806 Value *getExitScalar(MemoryAccess *MA, LoopToScevMapT <S, ValueMapT &BBMap); 807 808 /// @brief Generate the scalar stores for the given statement. 809 /// 810 /// After the statement @p Stmt was copied all inner-SCoP scalar dependences 811 /// starting in @p Stmt (hence all scalar write accesses in @p Stmt) need to 812 /// be demoted to memory. 813 /// 814 /// @param Stmt The statement we generate code for. 815 /// @param LTS A mapping from loops virtual canonical induction variable to 816 /// their new values (for values recalculated in the new ScoP, 817 /// but not within this basic block) 818 /// @param BBMap A mapping from old values to their new values in this block. 819 virtual void generateScalarStores(ScopStmt &Stmt, LoopToScevMapT <S, 820 ValueMapT &BBMAp) override; 821 822 /// @brief Copy a single PHI instruction. 823 /// 824 /// This copies a single PHI instruction and updates references to old values 825 /// with references to new values, as defined by GlobalMap and BBMap. 826 /// 827 /// @param Stmt The statement to code generate. 828 /// @param PHI The PHI instruction to copy. 829 /// @param BBMap A mapping from old values to their new values 830 /// (for values recalculated within this basic block). 831 /// @param LTS A map from old loops to new induction variables as SCEVs. 832 virtual void copyPHIInstruction(ScopStmt &Stmt, PHINode *Inst, 833 ValueMapT &BBMap, 834 LoopToScevMapT <S) override; 835 }; 836 } 837 #endif 838