EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2026-05-10 08:48:11
0001 //===-BlockGenerators.h - Helper to generate code for statements-*- C++ -*-===// 0002 // 0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 0004 // See https://llvm.org/LICENSE.txt for license information. 0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 0006 // 0007 //===----------------------------------------------------------------------===// 0008 // 0009 // This file defines the BlockGenerator and VectorBlockGenerator classes, which 0010 // generate sequential code and vectorized code for a polyhedral statement, 0011 // respectively. 0012 // 0013 //===----------------------------------------------------------------------===// 0014 0015 #ifndef POLLY_BLOCK_GENERATORS_H 0016 #define POLLY_BLOCK_GENERATORS_H 0017 0018 #include "polly/CodeGen/IRBuilder.h" 0019 #include "polly/Support/ScopHelper.h" 0020 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 0021 #include "isl/isl-noexceptions.h" 0022 0023 namespace polly { 0024 using llvm::AllocaInst; 0025 using llvm::ArrayRef; 0026 using llvm::AssertingVH; 0027 using llvm::BasicBlock; 0028 using llvm::BinaryOperator; 0029 using llvm::CmpInst; 0030 using llvm::DataLayout; 0031 using llvm::DenseMap; 0032 using llvm::DominatorTree; 0033 using llvm::Function; 0034 using llvm::Instruction; 0035 using llvm::LoadInst; 0036 using llvm::Loop; 0037 using llvm::LoopInfo; 0038 using llvm::LoopToScevMapT; 0039 using llvm::MapVector; 0040 using llvm::PHINode; 0041 using llvm::ScalarEvolution; 0042 using llvm::SetVector; 0043 using llvm::SmallVector; 0044 using llvm::StoreInst; 0045 using llvm::StringRef; 0046 using llvm::Type; 0047 using llvm::UnaryInstruction; 0048 using llvm::Value; 0049 0050 class MemoryAccess; 0051 class ScopArrayInfo; 0052 class IslExprBuilder; 0053 0054 /// Generate a new basic block for a polyhedral statement. 0055 class BlockGenerator { 0056 public: 0057 typedef llvm::SmallVector<ValueMapT, 8> VectorValueMapT; 0058 0059 /// Map types to resolve scalar dependences. 0060 /// 0061 ///@{ 0062 using AllocaMapTy = DenseMap<const ScopArrayInfo *, AssertingVH<AllocaInst>>; 0063 0064 /// Simple vector of instructions to store escape users. 0065 using EscapeUserVectorTy = SmallVector<Instruction *, 4>; 0066 0067 /// Map type to resolve escaping users for scalar instructions. 0068 /// 0069 /// @see The EscapeMap member. 0070 using EscapeUsersAllocaMapTy = 0071 MapVector<Instruction *, 0072 std::pair<AssertingVH<Value>, EscapeUserVectorTy>>; 0073 0074 ///@} 0075 0076 /// Create a generator for basic blocks. 0077 /// 0078 /// @param Builder The LLVM-IR Builder used to generate the statement. The 0079 /// code is generated at the location, the Builder points 0080 /// to. 0081 /// @param LI The loop info for the current function 0082 /// @param SE The scalar evolution info for the current function 0083 /// @param DT The dominator tree of this function. 0084 /// @param ScalarMap Map from scalars to their demoted location. 0085 /// @param EscapeMap Map from scalars to their escape users and locations. 0086 /// @param GlobalMap A mapping from llvm::Values used in the original scop 0087 /// region to a new set of llvm::Values. Each reference to 0088 /// an original value appearing in this mapping is replaced 0089 /// with the new value it is mapped to. 0090 /// @param ExprBuilder An expression builder to generate new access functions. 0091 /// @param StartBlock The first basic block after the RTC. 0092 BlockGenerator(PollyIRBuilder &Builder, LoopInfo &LI, ScalarEvolution &SE, 0093 DominatorTree &DT, AllocaMapTy &ScalarMap, 0094 EscapeUsersAllocaMapTy &EscapeMap, ValueMapT &GlobalMap, 0095 IslExprBuilder *ExprBuilder, BasicBlock *StartBlock); 0096 0097 /// Copy the basic block. 0098 /// 0099 /// This copies the entire basic block and updates references to old values 0100 /// with references to new values, as defined by GlobalMap. 0101 /// 0102 /// @param Stmt The block statement to code generate. 0103 /// @param LTS A map from old loops to new induction variables as 0104 /// SCEVs. 0105 /// @param NewAccesses A map from memory access ids to new ast expressions, 0106 /// which may contain new access expressions for certain 0107 /// memory accesses. 0108 void copyStmt(ScopStmt &Stmt, LoopToScevMapT <S, 0109 isl_id_to_ast_expr *NewAccesses); 0110 0111 /// Remove a ScopArrayInfo's allocation from the ScalarMap. 0112 /// 0113 /// This function allows to remove values from the ScalarMap. This is useful 0114 /// if the corresponding alloca instruction will be deleted (or moved into 0115 /// another module), as without removing these values the underlying 0116 /// AssertingVH will trigger due to us still keeping reference to this 0117 /// scalar. 0118 /// 0119 /// @param Array The array for which the alloca was generated. 0120 void freeScalarAlloc(ScopArrayInfo *Array) { ScalarMap.erase(Array); } 0121 0122 /// Return the alloca for @p Access. 0123 /// 0124 /// If no alloca was mapped for @p Access a new one is created. 0125 /// 0126 /// @param Access The memory access for which to generate the alloca. 0127 /// 0128 /// @returns The alloca for @p Access or a replacement value taken from 0129 /// GlobalMap. 0130 Value *getOrCreateAlloca(const MemoryAccess &Access); 0131 0132 /// Return the alloca for @p Array. 0133 /// 0134 /// If no alloca was mapped for @p Array a new one is created. 0135 /// 0136 /// @param Array The array for which to generate the alloca. 0137 /// 0138 /// @returns The alloca for @p Array or a replacement value taken from 0139 /// GlobalMap. 0140 Value *getOrCreateAlloca(const ScopArrayInfo *Array); 0141 0142 /// Finalize the code generation for the SCoP @p S. 0143 /// 0144 /// This will initialize and finalize the scalar variables we demoted during 0145 /// the code generation. 0146 /// 0147 /// @see createScalarInitialization(Scop &) 0148 /// @see createScalarFinalization(Region &) 0149 void finalizeSCoP(Scop &S); 0150 0151 /// An empty destructor 0152 virtual ~BlockGenerator() {} 0153 0154 BlockGenerator(const BlockGenerator &) = default; 0155 0156 protected: 0157 PollyIRBuilder &Builder; 0158 LoopInfo &LI; 0159 ScalarEvolution &SE; 0160 IslExprBuilder *ExprBuilder; 0161 0162 /// The dominator tree of this function. 0163 DominatorTree &DT; 0164 0165 /// Relates to the region where the code is emitted into. 0166 /// @{ 0167 DominatorTree *GenDT; 0168 LoopInfo *GenLI; 0169 ScalarEvolution *GenSE; 0170 /// @} 0171 0172 public: 0173 /// Map to resolve scalar dependences for PHI operands and scalars. 0174 /// 0175 /// When translating code that contains scalar dependences as they result from 0176 /// inter-block scalar dependences (including the use of data carrying PHI 0177 /// nodes), we do not directly regenerate in-register SSA code, but instead 0178 /// allocate some stack memory through which these scalar values are passed. 0179 /// Only a later pass of -mem2reg will then (re)introduce in-register 0180 /// computations. 0181 /// 0182 /// To keep track of the memory location(s) used to store the data computed by 0183 /// a given SSA instruction, we use the map 'ScalarMap'. ScalarMap maps a 0184 /// given ScopArrayInfo to the junk of stack allocated memory, that is 0185 /// used for code generation. 0186 /// 0187 /// Up to two different ScopArrayInfo objects are associated with each 0188 /// llvm::Value: 0189 /// 0190 /// MemoryType::Value objects are used for normal scalar dependences that go 0191 /// from a scalar definition to its use. Such dependences are lowered by 0192 /// directly writing the value an instruction computes into the corresponding 0193 /// chunk of memory and reading it back from this chunk of memory right before 0194 /// every use of this original scalar value. The memory allocations for 0195 /// MemoryType::Value objects end with '.s2a'. 0196 /// 0197 /// MemoryType::PHI (and MemoryType::ExitPHI) objects are used to model PHI 0198 /// nodes. For each PHI nodes we introduce, besides the Array of type 0199 /// MemoryType::Value, a second chunk of memory into which we write at the end 0200 /// of each basic block preceding the PHI instruction the value passed 0201 /// through this basic block. At the place where the PHI node is executed, we 0202 /// replace the PHI node with a load from the corresponding MemoryType::PHI 0203 /// memory location. The memory allocations for MemoryType::PHI end with 0204 /// '.phiops'. 0205 /// 0206 /// Example: 0207 /// 0208 /// Input C Code 0209 /// ============ 0210 /// 0211 /// S1: x1 = ... 0212 /// for (i=0...N) { 0213 /// S2: x2 = phi(x1, add) 0214 /// S3: add = x2 + 42; 0215 /// } 0216 /// S4: print(x1) 0217 /// print(x2) 0218 /// print(add) 0219 /// 0220 /// 0221 /// Unmodified IR IR After expansion 0222 /// ============= ================== 0223 /// 0224 /// S1: x1 = ... S1: x1 = ... 0225 /// x1.s2a = s1 0226 /// x2.phiops = s1 0227 /// | | 0228 /// | <--<--<--<--< | <--<--<--<--< 0229 /// | / \ | / \ . 0230 /// V V \ V V \ . 0231 /// S2: x2 = phi (x1, add) | S2: x2 = x2.phiops | 0232 /// | x2.s2a = x2 | 0233 /// | | 0234 /// S3: add = x2 + 42 | S3: add = x2 + 42 | 0235 /// | add.s2a = add | 0236 /// | x2.phiops = add | 0237 /// | \ / | \ / 0238 /// | \ / | \ / 0239 /// | >-->-->-->--> | >-->-->-->--> 0240 /// V V 0241 /// 0242 /// S4: x1 = x1.s2a 0243 /// S4: ... = x1 ... = x1 0244 /// x2 = x2.s2a 0245 /// ... = x2 ... = x2 0246 /// add = add.s2a 0247 /// ... = add ... = add 0248 /// 0249 /// ScalarMap = { x1:Value -> x1.s2a, x2:Value -> x2.s2a, 0250 /// add:Value -> add.s2a, x2:PHI -> x2.phiops } 0251 /// 0252 /// ??? Why does a PHI-node require two memory chunks ??? 0253 /// 0254 /// One may wonder why a PHI node requires two memory chunks and not just 0255 /// all data is stored in a single location. The following example tries 0256 /// to store all data in .s2a and drops the .phiops location: 0257 /// 0258 /// S1: x1 = ... 0259 /// x1.s2a = s1 0260 /// x2.s2a = s1 // use .s2a instead of .phiops 0261 /// | 0262 /// | <--<--<--<--< 0263 /// | / \ . 0264 /// V V \ . 0265 /// S2: x2 = x2.s2a | // value is same as above, but read 0266 /// | // from .s2a 0267 /// | 0268 /// x2.s2a = x2 | // store into .s2a as normal 0269 /// | 0270 /// S3: add = x2 + 42 | 0271 /// add.s2a = add | 0272 /// x2.s2a = add | // use s2a instead of .phiops 0273 /// | \ / // !!! This is wrong, as x2.s2a now 0274 /// | >-->-->-->--> // contains add instead of x2. 0275 /// V 0276 /// 0277 /// S4: x1 = x1.s2a 0278 /// ... = x1 0279 /// x2 = x2.s2a // !!! We now read 'add' instead of 0280 /// ... = x2 // 'x2' 0281 /// add = add.s2a 0282 /// ... = add 0283 /// 0284 /// As visible in the example, the SSA value of the PHI node may still be 0285 /// needed _after_ the basic block, which could conceptually branch to the 0286 /// PHI node, has been run and has overwritten the PHI's old value. Hence, a 0287 /// single memory location is not enough to code-generate a PHI node. 0288 /// 0289 /// Memory locations used for the special PHI node modeling. 0290 AllocaMapTy &ScalarMap; 0291 0292 /// Map from instructions to their escape users as well as the alloca. 0293 EscapeUsersAllocaMapTy &EscapeMap; 0294 0295 /// A map from llvm::Values referenced in the old code to a new set of 0296 /// llvm::Values, which is used to replace these old values during 0297 /// code generation. 0298 ValueMapT &GlobalMap; 0299 0300 /// The first basic block after the RTC. 0301 BasicBlock *StartBlock; 0302 0303 /// Split @p BB to create a new one we can use to clone @p BB in. 0304 BasicBlock *splitBB(BasicBlock *BB); 0305 0306 /// Change the function that code is emitted into. 0307 void switchGeneratedFunc(Function *GenFn, DominatorTree *GenDT, 0308 LoopInfo *GenLI, ScalarEvolution *GenSE); 0309 0310 /// Copy the given basic block. 0311 /// 0312 /// @param Stmt The statement to code generate. 0313 /// @param BB The basic block to code generate. 0314 /// @param BBMap A mapping from old values to their new values in this 0315 /// block. 0316 /// @param LTS A map from old loops to new induction variables as 0317 /// SCEVs. 0318 /// @param NewAccesses A map from memory access ids to new ast expressions, 0319 /// which may contain new access expressions for certain 0320 /// memory accesses. 0321 /// 0322 /// @returns The copy of the basic block. 0323 BasicBlock *copyBB(ScopStmt &Stmt, BasicBlock *BB, ValueMapT &BBMap, 0324 LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses); 0325 0326 /// Copy the given basic block. 0327 /// 0328 /// @param Stmt The statement to code generate. 0329 /// @param BB The basic block to code generate. 0330 /// @param BBCopy The new basic block to generate code in. 0331 /// @param BBMap A mapping from old values to their new values in this 0332 /// block. 0333 /// @param LTS A map from old loops to new induction variables as 0334 /// SCEVs. 0335 /// @param NewAccesses A map from memory access ids to new ast expressions, 0336 /// which may contain new access expressions for certain 0337 /// memory accesses. 0338 void copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *BBCopy, 0339 ValueMapT &BBMap, LoopToScevMapT <S, 0340 isl_id_to_ast_expr *NewAccesses); 0341 0342 /// Generate reload of scalars demoted to memory and needed by @p Stmt. 0343 /// 0344 /// @param Stmt The statement we generate code for. 0345 /// @param LTS A mapping from loops virtual canonical induction 0346 /// variable to their new values. 0347 /// @param BBMap A mapping from old values to their new values in this block. 0348 /// @param NewAccesses A map from memory access ids to new ast expressions. 0349 void generateScalarLoads(ScopStmt &Stmt, LoopToScevMapT <S, 0350 ValueMapT &BBMap, 0351 __isl_keep isl_id_to_ast_expr *NewAccesses); 0352 0353 /// When statement tracing is enabled, build the print instructions for 0354 /// printing the current statement instance. 0355 /// 0356 /// The printed output looks like: 0357 /// 0358 /// Stmt1(0) 0359 /// 0360 /// If printing of scalars is enabled, it also appends the value of each 0361 /// scalar to the line: 0362 /// 0363 /// Stmt1(0) %i=1 %sum=5 0364 /// 0365 /// @param Stmt The statement we generate code for. 0366 /// @param LTS A mapping from loops virtual canonical induction 0367 /// variable to their new values. 0368 /// @param BBMap A mapping from old values to their new values in this block. 0369 void generateBeginStmtTrace(ScopStmt &Stmt, LoopToScevMapT <S, 0370 ValueMapT &BBMap); 0371 0372 /// Generate instructions that compute whether one instance of @p Set is 0373 /// executed. 0374 /// 0375 /// @param Stmt The statement we generate code for. 0376 /// @param Subdomain A set in the space of @p Stmt's domain. Elements not in 0377 /// @p Stmt's domain are ignored. 0378 /// 0379 /// @return An expression of type i1, generated into the current builder 0380 /// position, that evaluates to 1 if the executed instance is part of 0381 /// @p Set. 0382 Value *buildContainsCondition(ScopStmt &Stmt, const isl::set &Subdomain); 0383 0384 /// Generate code that executes in a subset of @p Stmt's domain. 0385 /// 0386 /// @param Stmt The statement we generate code for. 0387 /// @param Subdomain The condition for some code to be executed. 0388 /// @param Subject A name for the code that is executed 0389 /// conditionally. Used to name new basic blocks and 0390 /// instructions. 0391 /// @param GenThenFunc Callback which generates the code to be executed 0392 /// when the current executed instance is in @p Set. The 0393 /// IRBuilder's position is moved to within the block that 0394 /// executes conditionally for this callback. 0395 void generateConditionalExecution(ScopStmt &Stmt, const isl::set &Subdomain, 0396 StringRef Subject, 0397 const std::function<void()> &GenThenFunc); 0398 0399 /// Generate the scalar stores for the given statement. 0400 /// 0401 /// After the statement @p Stmt was copied all inner-SCoP scalar dependences 0402 /// starting in @p Stmt (hence all scalar write accesses in @p Stmt) need to 0403 /// be demoted to memory. 0404 /// 0405 /// @param Stmt The statement we generate code for. 0406 /// @param LTS A mapping from loops virtual canonical induction 0407 /// variable to their new values 0408 /// (for values recalculated in the new ScoP, but not 0409 /// within this basic block) 0410 /// @param BBMap A mapping from old values to their new values in this block. 0411 /// @param NewAccesses A map from memory access ids to new ast expressions. 0412 virtual void generateScalarStores(ScopStmt &Stmt, LoopToScevMapT <S, 0413 ValueMapT &BBMap, 0414 __isl_keep isl_id_to_ast_expr *NewAccesses); 0415 0416 /// Handle users of @p Array outside the SCoP. 0417 /// 0418 /// @param S The current SCoP. 0419 /// @param Inst The ScopArrayInfo to handle. 0420 void handleOutsideUsers(const Scop &S, ScopArrayInfo *Array); 0421 0422 /// Find scalar statements that have outside users. 0423 /// 0424 /// We register these scalar values to later update subsequent scalar uses of 0425 /// these values to either use the newly computed value from within the scop 0426 /// (if the scop was executed) or the unchanged original code (if the run-time 0427 /// check failed). 0428 /// 0429 /// @param S The scop for which to find the outside users. 0430 void findOutsideUsers(Scop &S); 0431 0432 /// Initialize the memory of demoted scalars. 0433 /// 0434 /// @param S The scop for which to generate the scalar initializers. 0435 void createScalarInitialization(Scop &S); 0436 0437 /// Create exit PHI node merges for PHI nodes with more than two edges 0438 /// from inside the scop. 0439 /// 0440 /// For scops which have a PHI node in the exit block that has more than two 0441 /// incoming edges from inside the scop region, we require some special 0442 /// handling to understand which of the possible values will be passed to the 0443 /// PHI node from inside the optimized version of the scop. To do so ScopInfo 0444 /// models the possible incoming values as write accesses of the ScopStmts. 0445 /// 0446 /// This function creates corresponding code to reload the computed outgoing 0447 /// value from the stack slot it has been stored into and to pass it on to the 0448 /// PHI node in the original exit block. 0449 /// 0450 /// @param S The scop for which to generate the exiting PHI nodes. 0451 void createExitPHINodeMerges(Scop &S); 0452 0453 /// Promote the values of demoted scalars after the SCoP. 0454 /// 0455 /// If a scalar value was used outside the SCoP we need to promote the value 0456 /// stored in the memory cell allocated for that scalar and combine it with 0457 /// the original value in the non-optimized SCoP. 0458 void createScalarFinalization(Scop &S); 0459 0460 /// Try to synthesize a new value 0461 /// 0462 /// Given an old value, we try to synthesize it in a new context from its 0463 /// original SCEV expression. We start from the original SCEV expression, 0464 /// then replace outdated parameter and loop references, and finally 0465 /// expand it to code that computes this updated expression. 0466 /// 0467 /// @param Stmt The statement to code generate 0468 /// @param Old The old Value 0469 /// @param BBMap A mapping from old values to their new values 0470 /// (for values recalculated within this basic block) 0471 /// @param LTS A mapping from loops virtual canonical induction 0472 /// variable to their new values 0473 /// (for values recalculated in the new ScoP, but not 0474 /// within this basic block) 0475 /// @param L The loop that surrounded the instruction that referenced 0476 /// this value in the original code. This loop is used to 0477 /// evaluate the scalar evolution at the right scope. 0478 /// 0479 /// @returns o A newly synthesized value. 0480 /// o NULL, if synthesizing the value failed. 0481 Value *trySynthesizeNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap, 0482 LoopToScevMapT <S, Loop *L) const; 0483 0484 /// Get the new version of a value. 0485 /// 0486 /// Given an old value, we first check if a new version of this value is 0487 /// available in the BBMap or GlobalMap. In case it is not and the value can 0488 /// be recomputed using SCEV, we do so. If we can not recompute a value 0489 /// using SCEV, but we understand that the value is constant within the scop, 0490 /// we return the old value. If the value can still not be derived, this 0491 /// function will assert. 0492 /// 0493 /// @param Stmt The statement to code generate. 0494 /// @param Old The old Value. 0495 /// @param BBMap A mapping from old values to their new values 0496 /// (for values recalculated within this basic block). 0497 /// @param LTS A mapping from loops virtual canonical induction 0498 /// variable to their new values 0499 /// (for values recalculated in the new ScoP, but not 0500 /// within this basic block). 0501 /// @param L The loop that surrounded the instruction that referenced 0502 /// this value in the original code. This loop is used to 0503 /// evaluate the scalar evolution at the right scope. 0504 /// 0505 /// @returns o The old value, if it is still valid. 0506 /// o The new value, if available. 0507 /// o NULL, if no value is found. 0508 Value *getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap, 0509 LoopToScevMapT <S, Loop *L) const; 0510 0511 void copyInstScalar(ScopStmt &Stmt, Instruction *Inst, ValueMapT &BBMap, 0512 LoopToScevMapT <S); 0513 0514 /// Get the innermost loop that surrounds the statement @p Stmt. 0515 Loop *getLoopForStmt(const ScopStmt &Stmt) const; 0516 0517 /// Generate the operand address 0518 /// @param NewAccesses A map from memory access ids to new ast expressions, 0519 /// which may contain new access expressions for certain 0520 /// memory accesses. 0521 Value *generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst, 0522 ValueMapT &BBMap, LoopToScevMapT <S, 0523 isl_id_to_ast_expr *NewAccesses); 0524 0525 /// Generate the operand address. 0526 /// 0527 /// @param Stmt The statement to generate code for. 0528 /// @param L The innermost loop that surrounds the statement. 0529 /// @param Pointer If the access expression is not changed (ie. not found 0530 /// in @p LTS), use this Pointer from the original code 0531 /// instead. 0532 /// @param BBMap A mapping from old values to their new values. 0533 /// @param LTS A mapping from loops virtual canonical induction 0534 /// variable to their new values. 0535 /// @param NewAccesses Ahead-of-time generated access expressions. 0536 /// @param Id Identifier of the MemoryAccess to generate. 0537 /// @param ExpectedType The type the returned value should have. 0538 /// 0539 /// @return The generated address. 0540 Value *generateLocationAccessed(ScopStmt &Stmt, Loop *L, Value *Pointer, 0541 ValueMapT &BBMap, LoopToScevMapT <S, 0542 isl_id_to_ast_expr *NewAccesses, 0543 __isl_take isl_id *Id, Type *ExpectedType); 0544 0545 /// Generate the pointer value that is accesses by @p Access. 0546 /// 0547 /// For write accesses, generate the target address. For read accesses, 0548 /// generate the source address. 0549 /// The access can be either an array access or a scalar access. In the first 0550 /// case, the returned address will point to an element into that array. In 0551 /// the scalar case, an alloca is used. 0552 /// If a new AccessRelation is set for the MemoryAccess, the new relation will 0553 /// be used. 0554 /// 0555 /// @param Access The access to generate a pointer for. 0556 /// @param L The innermost loop that surrounds the statement. 0557 /// @param LTS A mapping from loops virtual canonical induction 0558 /// variable to their new values. 0559 /// @param BBMap A mapping from old values to their new values. 0560 /// @param NewAccesses A map from memory access ids to new ast expressions. 0561 /// 0562 /// @return The generated address. 0563 Value *getImplicitAddress(MemoryAccess &Access, Loop *L, LoopToScevMapT <S, 0564 ValueMapT &BBMap, 0565 __isl_keep isl_id_to_ast_expr *NewAccesses); 0566 0567 /// @param NewAccesses A map from memory access ids to new ast expressions, 0568 /// which may contain new access expressions for certain 0569 /// memory accesses. 0570 Value *generateArrayLoad(ScopStmt &Stmt, LoadInst *load, ValueMapT &BBMap, 0571 LoopToScevMapT <S, 0572 isl_id_to_ast_expr *NewAccesses); 0573 0574 /// @param NewAccesses A map from memory access ids to new ast expressions, 0575 /// which may contain new access expressions for certain 0576 /// memory accesses. 0577 void generateArrayStore(ScopStmt &Stmt, StoreInst *store, ValueMapT &BBMap, 0578 LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses); 0579 0580 /// Copy a single PHI instruction. 0581 /// 0582 /// The implementation in the BlockGenerator is trivial, however it allows 0583 /// subclasses to handle PHIs different. 0584 virtual void copyPHIInstruction(ScopStmt &, PHINode *, ValueMapT &, 0585 LoopToScevMapT &) {} 0586 0587 /// Copy a single Instruction. 0588 /// 0589 /// This copies a single Instruction and updates references to old values 0590 /// with references to new values, as defined by GlobalMap and BBMap. 0591 /// 0592 /// @param Stmt The statement to code generate. 0593 /// @param Inst The instruction to copy. 0594 /// @param BBMap A mapping from old values to their new values 0595 /// (for values recalculated within this basic block). 0596 /// @param GlobalMap A mapping from old values to their new values 0597 /// (for values recalculated in the new ScoP, but not 0598 /// within this basic block). 0599 /// @param LTS A mapping from loops virtual canonical induction 0600 /// variable to their new values 0601 /// (for values recalculated in the new ScoP, but not 0602 /// within this basic block). 0603 /// @param NewAccesses A map from memory access ids to new ast expressions, 0604 /// which may contain new access expressions for certain 0605 /// memory accesses. 0606 void copyInstruction(ScopStmt &Stmt, Instruction *Inst, ValueMapT &BBMap, 0607 LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses); 0608 0609 /// Helper to determine if @p Inst can be synthesized in @p Stmt. 0610 /// 0611 /// @returns false, iff @p Inst can be synthesized in @p Stmt. 0612 bool canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst); 0613 0614 /// Remove dead instructions generated for BB 0615 /// 0616 /// @param BB The basic block code for which code has been generated. 0617 /// @param BBMap A local map from old to new instructions. 0618 void removeDeadInstructions(BasicBlock *BB, ValueMapT &BBMap); 0619 0620 /// Invalidate the scalar evolution expressions for a scop. 0621 /// 0622 /// This function invalidates the scalar evolution results for all 0623 /// instructions that are part of a given scop, and the loops 0624 /// surrounding the users of merge blocks. This is necessary to ensure that 0625 /// later scops do not obtain scalar evolution expressions that reference 0626 /// values that earlier dominated the later scop, but have been moved in the 0627 /// conditional part of an earlier scop and consequently do not any more 0628 /// dominate the later scop. 0629 /// 0630 /// @param S The scop to invalidate. 0631 void invalidateScalarEvolution(Scop &S); 0632 }; 0633 0634 /// Generator for new versions of polyhedral region statements. 0635 class RegionGenerator final : public BlockGenerator { 0636 public: 0637 /// Create a generator for regions. 0638 /// 0639 /// @param BlockGen A generator for basic blocks. 0640 RegionGenerator(BlockGenerator &BlockGen) : BlockGenerator(BlockGen) {} 0641 0642 virtual ~RegionGenerator() {} 0643 0644 /// Copy the region statement @p Stmt. 0645 /// 0646 /// This copies the entire region represented by @p Stmt and updates 0647 /// references to old values with references to new values, as defined by 0648 /// GlobalMap. 0649 /// 0650 /// @param Stmt The statement to code generate. 0651 /// @param LTS A map from old loops to new induction variables as SCEVs. 0652 void copyStmt(ScopStmt &Stmt, LoopToScevMapT <S, 0653 __isl_keep isl_id_to_ast_expr *IdToAstExp); 0654 0655 private: 0656 /// A map from old to the first new block in the region, that was created to 0657 /// model the old basic block. 0658 DenseMap<BasicBlock *, BasicBlock *> StartBlockMap; 0659 0660 /// A map from old to the last new block in the region, that was created to 0661 /// model the old basic block. 0662 DenseMap<BasicBlock *, BasicBlock *> EndBlockMap; 0663 0664 /// The "BBMaps" for the whole region (one for each block). In case a basic 0665 /// block is code generated to multiple basic blocks (e.g., for partial 0666 /// writes), the StartBasic is used as index for the RegionMap. 0667 DenseMap<BasicBlock *, ValueMapT> RegionMaps; 0668 0669 /// Mapping to remember PHI nodes that still need incoming values. 0670 using PHINodePairTy = std::pair<PHINode *, PHINode *>; 0671 DenseMap<BasicBlock *, SmallVector<PHINodePairTy, 4>> IncompletePHINodeMap; 0672 0673 /// Repair the dominance tree after we created a copy block for @p BB. 0674 /// 0675 /// @returns The immediate dominator in the DT for @p BBCopy if in the region. 0676 BasicBlock *repairDominance(BasicBlock *BB, BasicBlock *BBCopy); 0677 0678 /// Add the new operand from the copy of @p IncomingBB to @p PHICopy. 0679 /// 0680 /// PHI nodes, which may have (multiple) edges that enter from outside the 0681 /// non-affine subregion and even from outside the scop, are code generated as 0682 /// follows: 0683 /// 0684 /// # Original 0685 /// 0686 /// Region: %A-> %exit 0687 /// NonAffine Stmt: %nonaffB -> %D (includes %nonaffB, %nonaffC) 0688 /// 0689 /// pre: 0690 /// %val = add i64 1, 1 0691 /// 0692 /// A: 0693 /// br label %nonaff 0694 /// 0695 /// nonaffB: 0696 /// %phi = phi i64 [%val, %A], [%valC, %nonAffC], [%valD, %D] 0697 /// %cmp = <nonaff> 0698 /// br i1 %cmp, label %C, label %nonaffC 0699 /// 0700 /// nonaffC: 0701 /// %valC = add i64 1, 1 0702 /// br i1 undef, label %D, label %nonaffB 0703 /// 0704 /// D: 0705 /// %valD = ... 0706 /// %exit_cond = <loopexit> 0707 /// br i1 %exit_cond, label %nonaffB, label %exit 0708 /// 0709 /// exit: 0710 /// ... 0711 /// 0712 /// - %start and %C enter from outside the non-affine region. 0713 /// - %nonaffC enters from within the non-affine region. 0714 /// 0715 /// # New 0716 /// 0717 /// polly.A: 0718 /// store i64 %val, i64* %phi.phiops 0719 /// br label %polly.nonaffA.entry 0720 /// 0721 /// polly.nonaffB.entry: 0722 /// %phi.phiops.reload = load i64, i64* %phi.phiops 0723 /// br label %nonaffB 0724 /// 0725 /// polly.nonaffB: 0726 /// %polly.phi = [%phi.phiops.reload, %nonaffB.entry], 0727 /// [%p.valC, %polly.nonaffC] 0728 /// 0729 /// polly.nonaffC: 0730 /// %p.valC = add i64 1, 1 0731 /// br i1 undef, label %polly.D, label %polly.nonaffB 0732 /// 0733 /// polly.D: 0734 /// %p.valD = ... 0735 /// store i64 %p.valD, i64* %phi.phiops 0736 /// %p.exit_cond = <loopexit> 0737 /// br i1 %p.exit_cond, label %polly.nonaffB, label %exit 0738 /// 0739 /// Values that enter the PHI from outside the non-affine region are stored 0740 /// into the stack slot %phi.phiops by statements %polly.A and %polly.D and 0741 /// reloaded in %polly.nonaffB.entry, a basic block generated before the 0742 /// actual non-affine region. 0743 /// 0744 /// When generating the PHI node of the non-affine region in %polly.nonaffB, 0745 /// incoming edges from outside the region are combined into a single branch 0746 /// from %polly.nonaffB.entry which has as incoming value the value reloaded 0747 /// from the %phi.phiops stack slot. Incoming edges from within the region 0748 /// refer to the copied instructions (%p.valC) and basic blocks 0749 /// (%polly.nonaffC) of the non-affine region. 0750 /// 0751 /// @param Stmt The statement to code generate. 0752 /// @param PHI The original PHI we copy. 0753 /// @param PHICopy The copy of @p PHI. 0754 /// @param IncomingBB An incoming block of @p PHI. 0755 /// @param LTS A map from old loops to new induction variables as 0756 /// SCEVs. 0757 void addOperandToPHI(ScopStmt &Stmt, PHINode *PHI, PHINode *PHICopy, 0758 BasicBlock *IncomingBB, LoopToScevMapT <S); 0759 0760 /// Create a PHI that combines the incoming values from all incoming blocks 0761 /// that are in the subregion. 0762 /// 0763 /// PHIs in the subregion's exit block can have incoming edges from within and 0764 /// outside the subregion. This function combines the incoming values from 0765 /// within the subregion to appear as if there is only one incoming edge from 0766 /// the subregion (an additional exit block is created by RegionGenerator). 0767 /// This is to avoid that a value is written to the .phiops location without 0768 /// leaving the subregion because the exiting block as an edge back into the 0769 /// subregion. 0770 /// 0771 /// @param MA The WRITE of MemoryKind::PHI/MemoryKind::ExitPHI for a PHI in 0772 /// the subregion's exit block. 0773 /// @param LTS Virtual induction variable mapping. 0774 /// @param BBMap A mapping from old values to their new values in this block. 0775 /// @param L Loop surrounding this region statement. 0776 /// 0777 /// @returns The constructed PHI node. 0778 PHINode *buildExitPHI(MemoryAccess *MA, LoopToScevMapT <S, ValueMapT &BBMap, 0779 Loop *L); 0780 0781 /// @param Return the new value of a scalar write, creating a PHINode if 0782 /// necessary. 0783 /// 0784 /// @param MA A scalar WRITE MemoryAccess. 0785 /// @param LTS Virtual induction variable mapping. 0786 /// @param BBMap A mapping from old values to their new values in this block. 0787 /// 0788 /// @returns The effective value of @p MA's written value when leaving the 0789 /// subregion. 0790 /// @see buildExitPHI 0791 Value *getExitScalar(MemoryAccess *MA, LoopToScevMapT <S, ValueMapT &BBMap); 0792 0793 /// Generate the scalar stores for the given statement. 0794 /// 0795 /// After the statement @p Stmt was copied all inner-SCoP scalar dependences 0796 /// starting in @p Stmt (hence all scalar write accesses in @p Stmt) need to 0797 /// be demoted to memory. 0798 /// 0799 /// @param Stmt The statement we generate code for. 0800 /// @param LTS A mapping from loops virtual canonical induction variable to 0801 /// their new values (for values recalculated in the new ScoP, 0802 /// but not within this basic block) 0803 /// @param BBMap A mapping from old values to their new values in this block. 0804 /// @param LTS A mapping from loops virtual canonical induction variable to 0805 /// their new values. 0806 void 0807 generateScalarStores(ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMAp, 0808 __isl_keep isl_id_to_ast_expr *NewAccesses) override; 0809 0810 /// Copy a single PHI instruction. 0811 /// 0812 /// This copies a single PHI instruction and updates references to old values 0813 /// with references to new values, as defined by GlobalMap and BBMap. 0814 /// 0815 /// @param Stmt The statement to code generate. 0816 /// @param PHI The PHI instruction to copy. 0817 /// @param BBMap A mapping from old values to their new values 0818 /// (for values recalculated within this basic block). 0819 /// @param LTS A map from old loops to new induction variables as SCEVs. 0820 void copyPHIInstruction(ScopStmt &Stmt, PHINode *Inst, ValueMapT &BBMap, 0821 LoopToScevMapT <S) override; 0822 }; 0823 } // namespace polly 0824 #endif
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|