Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 1 | //===--- BlockGenerators.cpp - 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 implements the BlockGenerator and VectorBlockGenerator classes, |
| 11 | // which generate sequential code and vectorized code for a polyhedral |
| 12 | // statement, respectively. |
| 13 | // |
| 14 | //===----------------------------------------------------------------------===// |
| 15 | |
Hongbin Zheng | 8a84661 | 2012-04-25 13:18:28 +0000 | [diff] [blame] | 16 | #include "polly/CodeGen/BlockGenerators.h" |
Tobias Grosser | 8362818 | 2013-05-07 08:11:54 +0000 | [diff] [blame] | 17 | #include "polly/CodeGen/CodeGeneration.h" |
Johannes Doerfert | a63b257 | 2014-08-03 01:51:59 +0000 | [diff] [blame] | 18 | #include "polly/CodeGen/IslExprBuilder.h" |
Tobias Grosser | 86bc93a | 2015-09-06 08:47:57 +0000 | [diff] [blame] | 19 | #include "polly/CodeGen/RuntimeDebugBuilder.h" |
Tobias Grosser | 637bd63 | 2013-05-07 07:31:10 +0000 | [diff] [blame] | 20 | #include "polly/Options.h" |
Tobias Grosser | 5624d3c | 2015-12-21 12:38:56 +0000 | [diff] [blame] | 21 | #include "polly/ScopInfo.h" |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 22 | #include "polly/Support/GICHelper.h" |
Sebastian Pop | 97cb813 | 2013-03-18 20:21:13 +0000 | [diff] [blame] | 23 | #include "polly/Support/SCEVValidator.h" |
Tobias Grosser | ecfe21b | 2013-03-20 18:03:18 +0000 | [diff] [blame] | 24 | #include "polly/Support/ScopHelper.h" |
Tobias Grosser | e71c6ab | 2012-04-27 16:36:14 +0000 | [diff] [blame] | 25 | #include "llvm/Analysis/LoopInfo.h" |
Johannes Doerfert | f32d651 | 2015-03-01 18:45:58 +0000 | [diff] [blame] | 26 | #include "llvm/Analysis/RegionInfo.h" |
Tobias Grosser | e71c6ab | 2012-04-27 16:36:14 +0000 | [diff] [blame] | 27 | #include "llvm/Analysis/ScalarEvolution.h" |
Tobias Grosser | 030237d | 2014-02-21 15:06:05 +0000 | [diff] [blame] | 28 | #include "llvm/IR/IntrinsicInst.h" |
Tobias Grosser | c989506 | 2015-03-10 15:24:33 +0000 | [diff] [blame] | 29 | #include "llvm/IR/Module.h" |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 30 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
Tobias Grosser | 1b9d25a | 2015-09-27 11:17:22 +0000 | [diff] [blame] | 31 | #include "llvm/Transforms/Utils/Local.h" |
Johannes Doerfert | f32d651 | 2015-03-01 18:45:58 +0000 | [diff] [blame] | 32 | #include "isl/aff.h" |
| 33 | #include "isl/ast.h" |
Johannes Doerfert | f32d651 | 2015-03-01 18:45:58 +0000 | [diff] [blame] | 34 | #include "isl/ast_build.h" |
Tobias Grosser | ba0d092 | 2015-05-09 09:13:42 +0000 | [diff] [blame] | 35 | #include "isl/set.h" |
Johannes Doerfert | f32d651 | 2015-03-01 18:45:58 +0000 | [diff] [blame] | 36 | #include <deque> |
| 37 | |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 38 | using namespace llvm; |
| 39 | using namespace polly; |
| 40 | |
Tobias Grosser | 878aba4 | 2014-10-22 23:22:41 +0000 | [diff] [blame] | 41 | static cl::opt<bool> Aligned("enable-polly-aligned", |
| 42 | cl::desc("Assumed aligned memory accesses."), |
| 43 | cl::Hidden, cl::init(false), cl::ZeroOrMore, |
| 44 | cl::cat(PollyCategory)); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 45 | |
Tobias Grosser | 86bc93a | 2015-09-06 08:47:57 +0000 | [diff] [blame] | 46 | static cl::opt<bool> DebugPrinting( |
| 47 | "polly-codegen-add-debug-printing", |
| 48 | cl::desc("Add printf calls that show the values loaded/stored."), |
| 49 | cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory)); |
| 50 | |
Johannes Doerfert | b4f08eb | 2015-02-23 13:51:35 +0000 | [diff] [blame] | 51 | BlockGenerator::BlockGenerator(PollyIRBuilder &B, LoopInfo &LI, |
| 52 | ScalarEvolution &SE, DominatorTree &DT, |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 53 | ScalarAllocaMapTy &ScalarMap, |
| 54 | ScalarAllocaMapTy &PHIOpMap, |
| 55 | EscapeUsersAllocaMapTy &EscapeMap, |
Tobias Grosser | f4bb7a6 | 2015-10-04 10:18:32 +0000 | [diff] [blame] | 56 | ValueMapT &GlobalMap, |
Johannes Doerfert | b4f08eb | 2015-02-23 13:51:35 +0000 | [diff] [blame] | 57 | IslExprBuilder *ExprBuilder) |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 58 | : Builder(B), LI(LI), SE(SE), ExprBuilder(ExprBuilder), DT(DT), |
| 59 | EntryBB(nullptr), PHIOpMap(PHIOpMap), ScalarMap(ScalarMap), |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 60 | EscapeMap(EscapeMap), GlobalMap(GlobalMap) {} |
Tobias Grosser | e71c6ab | 2012-04-27 16:36:14 +0000 | [diff] [blame] | 61 | |
Tobias Grosser | 2f1acac | 2015-10-04 10:18:45 +0000 | [diff] [blame] | 62 | Value *BlockGenerator::trySynthesizeNewValue(ScopStmt &Stmt, Value *Old, |
Tobias Grosser | 33cb9f9 | 2015-09-30 11:56:19 +0000 | [diff] [blame] | 63 | ValueMapT &BBMap, |
| 64 | LoopToScevMapT <S, |
| 65 | Loop *L) const { |
Johannes Doerfert | 42df8d1 | 2015-12-22 19:08:01 +0000 | [diff] [blame] | 66 | if (!SE.isSCEVable(Old->getType())) |
| 67 | return nullptr; |
Johannes Doerfert | e69e114 | 2015-08-18 11:56:00 +0000 | [diff] [blame] | 68 | |
Johannes Doerfert | 42df8d1 | 2015-12-22 19:08:01 +0000 | [diff] [blame] | 69 | const SCEV *Scev = SE.getSCEVAtScope(Old, L); |
| 70 | if (!Scev) |
| 71 | return nullptr; |
Johannes Doerfert | e69e114 | 2015-08-18 11:56:00 +0000 | [diff] [blame] | 72 | |
Johannes Doerfert | 42df8d1 | 2015-12-22 19:08:01 +0000 | [diff] [blame] | 73 | if (isa<SCEVCouldNotCompute>(Scev)) |
| 74 | return nullptr; |
Tobias Grosser | e71c6ab | 2012-04-27 16:36:14 +0000 | [diff] [blame] | 75 | |
Sanjoy Das | 03bcb91 | 2016-05-29 07:33:16 +0000 | [diff] [blame^] | 76 | const SCEV *NewScev = SCEVLoopAddRecRewriter::rewrite(Scev, LTS, SE); |
Johannes Doerfert | 42df8d1 | 2015-12-22 19:08:01 +0000 | [diff] [blame] | 77 | ValueMapT VTV; |
| 78 | VTV.insert(BBMap.begin(), BBMap.end()); |
| 79 | VTV.insert(GlobalMap.begin(), GlobalMap.end()); |
Tobias Grosser | e71c6ab | 2012-04-27 16:36:14 +0000 | [diff] [blame] | 80 | |
Johannes Doerfert | 42df8d1 | 2015-12-22 19:08:01 +0000 | [diff] [blame] | 81 | Scop &S = *Stmt.getParent(); |
Johannes Doerfert | 3f52e35 | 2016-05-23 12:38:05 +0000 | [diff] [blame] | 82 | const DataLayout &DL = S.getFunction().getParent()->getDataLayout(); |
Johannes Doerfert | 42df8d1 | 2015-12-22 19:08:01 +0000 | [diff] [blame] | 83 | auto IP = Builder.GetInsertPoint(); |
| 84 | |
| 85 | assert(IP != Builder.GetInsertBlock()->end() && |
| 86 | "Only instructions can be insert points for SCEVExpander"); |
| 87 | Value *Expanded = |
| 88 | expandCodeFor(S, SE, DL, "polly", NewScev, Old->getType(), &*IP, &VTV); |
| 89 | |
| 90 | BBMap[Old] = Expanded; |
| 91 | return Expanded; |
Tobias Grosser | 33cb9f9 | 2015-09-30 11:56:19 +0000 | [diff] [blame] | 92 | } |
| 93 | |
Tobias Grosser | 2f1acac | 2015-10-04 10:18:45 +0000 | [diff] [blame] | 94 | Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap, |
| 95 | LoopToScevMapT <S, Loop *L) const { |
Tobias Grosser | 9bd0dad | 2015-12-14 16:19:59 +0000 | [diff] [blame] | 96 | // Constants that do not reference any named value can always remain |
Michael Kruse | 5bbc0e1 | 2015-12-14 23:41:32 +0000 | [diff] [blame] | 97 | // unchanged. Handle them early to avoid expensive map lookups. We do not take |
Tobias Grosser | 9bd0dad | 2015-12-14 16:19:59 +0000 | [diff] [blame] | 98 | // the fast-path for external constants which are referenced through globals |
| 99 | // as these may need to be rewritten when distributing code accross different |
| 100 | // LLVM modules. |
| 101 | if (isa<Constant>(Old) && !isa<GlobalValue>(Old)) |
Tobias Grosser | 6f764bb | 2015-12-14 16:19:54 +0000 | [diff] [blame] | 102 | return Old; |
Tobias Grosser | 33cb9f9 | 2015-09-30 11:56:19 +0000 | [diff] [blame] | 103 | |
Johannes Doerfert | 28f8ac1 | 2015-12-22 19:08:24 +0000 | [diff] [blame] | 104 | // Inline asm is like a constant to us. |
| 105 | if (isa<InlineAsm>(Old)) |
| 106 | return Old; |
| 107 | |
Tobias Grosser | 33cb9f9 | 2015-09-30 11:56:19 +0000 | [diff] [blame] | 108 | if (Value *New = GlobalMap.lookup(Old)) { |
| 109 | if (Value *NewRemapped = GlobalMap.lookup(New)) |
| 110 | New = NewRemapped; |
| 111 | if (Old->getType()->getScalarSizeInBits() < |
| 112 | New->getType()->getScalarSizeInBits()) |
| 113 | New = Builder.CreateTruncOrBitCast(New, Old->getType()); |
| 114 | |
| 115 | return New; |
| 116 | } |
| 117 | |
| 118 | if (Value *New = BBMap.lookup(Old)) |
| 119 | return New; |
| 120 | |
| 121 | if (Value *New = trySynthesizeNewValue(Stmt, Old, BBMap, LTS, L)) |
| 122 | return New; |
| 123 | |
Tobias Grosser | 16371ac | 2014-11-05 20:48:56 +0000 | [diff] [blame] | 124 | // A scop-constant value defined by a global or a function parameter. |
| 125 | if (isa<GlobalValue>(Old) || isa<Argument>(Old)) |
Tobias Grosser | 6f764bb | 2015-12-14 16:19:54 +0000 | [diff] [blame] | 126 | return Old; |
Tobias Grosser | 16371ac | 2014-11-05 20:48:56 +0000 | [diff] [blame] | 127 | |
| 128 | // A scop-constant value defined by an instruction executed outside the scop. |
| 129 | if (const Instruction *Inst = dyn_cast<Instruction>(Old)) |
Johannes Doerfert | 952b530 | 2016-05-23 12:40:48 +0000 | [diff] [blame] | 130 | if (!Stmt.getParent()->contains(Inst->getParent())) |
Tobias Grosser | 6f764bb | 2015-12-14 16:19:54 +0000 | [diff] [blame] | 131 | return Old; |
Tobias Grosser | 16371ac | 2014-11-05 20:48:56 +0000 | [diff] [blame] | 132 | |
| 133 | // The scalar dependence is neither available nor SCEVCodegenable. |
Hongbin Zheng | 5b463ce | 2013-07-25 09:12:07 +0000 | [diff] [blame] | 134 | llvm_unreachable("Unexpected scalar dependence in region!"); |
Tobias Grosser | 5a56cbf | 2014-04-16 07:33:47 +0000 | [diff] [blame] | 135 | return nullptr; |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 136 | } |
| 137 | |
Tobias Grosser | 2f1acac | 2015-10-04 10:18:45 +0000 | [diff] [blame] | 138 | void BlockGenerator::copyInstScalar(ScopStmt &Stmt, Instruction *Inst, |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 139 | ValueMapT &BBMap, LoopToScevMapT <S) { |
Tobias Grosser | 030237d | 2014-02-21 15:06:05 +0000 | [diff] [blame] | 140 | // We do not generate debug intrinsics as we did not investigate how to |
| 141 | // copy them correctly. At the current state, they just crash the code |
| 142 | // generation as the meta-data operands are not correctly copied. |
| 143 | if (isa<DbgInfoIntrinsic>(Inst)) |
| 144 | return; |
| 145 | |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 146 | Instruction *NewInst = Inst->clone(); |
| 147 | |
| 148 | // Replace old operands with the new ones. |
Tobias Grosser | 91f5b26 | 2014-06-04 08:06:40 +0000 | [diff] [blame] | 149 | for (Value *OldOperand : Inst->operands()) { |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 150 | Value *NewOperand = |
Johannes Doerfert | 2c3ffc0 | 2016-02-16 12:36:14 +0000 | [diff] [blame] | 151 | getNewValue(Stmt, OldOperand, BBMap, LTS, getLoopForStmt(Stmt)); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 152 | |
| 153 | if (!NewOperand) { |
Tobias Grosser | c14582f | 2013-02-05 18:01:29 +0000 | [diff] [blame] | 154 | assert(!isa<StoreInst>(NewInst) && |
| 155 | "Store instructions are always needed!"); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 156 | delete NewInst; |
| 157 | return; |
| 158 | } |
| 159 | |
| 160 | NewInst->replaceUsesOfWith(OldOperand, NewOperand); |
| 161 | } |
| 162 | |
| 163 | Builder.Insert(NewInst); |
| 164 | BBMap[Inst] = NewInst; |
| 165 | |
| 166 | if (!NewInst->getType()->isVoidTy()) |
| 167 | NewInst->setName("p_" + Inst->getName()); |
| 168 | } |
| 169 | |
Michael Kruse | 70131d3 | 2016-01-27 17:09:17 +0000 | [diff] [blame] | 170 | Value * |
| 171 | BlockGenerator::generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst, |
| 172 | ValueMapT &BBMap, LoopToScevMapT <S, |
| 173 | isl_id_to_ast_expr *NewAccesses) { |
Tobias Grosser | 0921477 | 2015-12-15 23:49:53 +0000 | [diff] [blame] | 174 | const MemoryAccess &MA = Stmt.getArrayAccessFor(Inst); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 175 | |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 176 | isl_ast_expr *AccessExpr = isl_id_to_ast_expr_get(NewAccesses, MA.getId()); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 177 | |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 178 | if (AccessExpr) { |
| 179 | AccessExpr = isl_ast_expr_address_of(AccessExpr); |
Tobias Grosser | 98b3ee5 | 2015-09-29 06:44:38 +0000 | [diff] [blame] | 180 | auto Address = ExprBuilder->create(AccessExpr); |
| 181 | |
| 182 | // Cast the address of this memory access to a pointer type that has the |
| 183 | // same element type as the original access, but uses the address space of |
| 184 | // the newly generated pointer. |
| 185 | auto OldPtrTy = MA.getAccessValue()->getType()->getPointerTo(); |
| 186 | auto NewPtrTy = Address->getType(); |
| 187 | OldPtrTy = PointerType::get(OldPtrTy->getElementType(), |
| 188 | NewPtrTy->getPointerAddressSpace()); |
| 189 | |
Tobias Grosser | d840fc7 | 2016-02-04 13:18:42 +0000 | [diff] [blame] | 190 | if (OldPtrTy != NewPtrTy) |
Tobias Grosser | 98b3ee5 | 2015-09-29 06:44:38 +0000 | [diff] [blame] | 191 | Address = Builder.CreateBitOrPointerCast(Address, OldPtrTy); |
Tobias Grosser | 98b3ee5 | 2015-09-29 06:44:38 +0000 | [diff] [blame] | 192 | return Address; |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 193 | } |
| 194 | |
Michael Kruse | 70131d3 | 2016-01-27 17:09:17 +0000 | [diff] [blame] | 195 | return getNewValue(Stmt, Inst.getPointerOperand(), BBMap, LTS, |
Johannes Doerfert | 2c3ffc0 | 2016-02-16 12:36:14 +0000 | [diff] [blame] | 196 | getLoopForStmt(Stmt)); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 197 | } |
| 198 | |
Johannes Doerfert | 2c3ffc0 | 2016-02-16 12:36:14 +0000 | [diff] [blame] | 199 | Loop *BlockGenerator::getLoopForStmt(const ScopStmt &Stmt) const { |
Michael Kruse | 375cb5f | 2016-02-24 22:08:24 +0000 | [diff] [blame] | 200 | auto *StmtBB = Stmt.getEntryBlock(); |
Johannes Doerfert | 2c3ffc0 | 2016-02-16 12:36:14 +0000 | [diff] [blame] | 201 | return LI.getLoopFor(StmtBB); |
Tobias Grosser | 369430f | 2013-03-22 23:42:53 +0000 | [diff] [blame] | 202 | } |
| 203 | |
Tobias Grosser | 2f1acac | 2015-10-04 10:18:45 +0000 | [diff] [blame] | 204 | Value *BlockGenerator::generateScalarLoad(ScopStmt &Stmt, LoadInst *Load, |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 205 | ValueMapT &BBMap, LoopToScevMapT <S, |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 206 | isl_id_to_ast_expr *NewAccesses) { |
Johannes Doerfert | c1db67e | 2015-09-29 23:47:21 +0000 | [diff] [blame] | 207 | if (Value *PreloadLoad = GlobalMap.lookup(Load)) |
| 208 | return PreloadLoad; |
| 209 | |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 210 | Value *NewPointer = |
Michael Kruse | 70131d3 | 2016-01-27 17:09:17 +0000 | [diff] [blame] | 211 | generateLocationAccessed(Stmt, Load, BBMap, LTS, NewAccesses); |
Johannes Doerfert | 8790145 | 2014-10-02 16:22:19 +0000 | [diff] [blame] | 212 | Value *ScalarLoad = Builder.CreateAlignedLoad( |
| 213 | NewPointer, Load->getAlignment(), Load->getName() + "_p_scalar_"); |
Tobias Grosser | 86bc93a | 2015-09-06 08:47:57 +0000 | [diff] [blame] | 214 | |
| 215 | if (DebugPrinting) |
| 216 | RuntimeDebugBuilder::createCPUPrinter(Builder, "Load from ", NewPointer, |
| 217 | ": ", ScalarLoad, "\n"); |
| 218 | |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 219 | return ScalarLoad; |
| 220 | } |
| 221 | |
Tobias Grosser | 2f1acac | 2015-10-04 10:18:45 +0000 | [diff] [blame] | 222 | void BlockGenerator::generateScalarStore(ScopStmt &Stmt, StoreInst *Store, |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 223 | ValueMapT &BBMap, LoopToScevMapT <S, |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 224 | isl_id_to_ast_expr *NewAccesses) { |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 225 | Value *NewPointer = |
Michael Kruse | 70131d3 | 2016-01-27 17:09:17 +0000 | [diff] [blame] | 226 | generateLocationAccessed(Stmt, Store, BBMap, LTS, NewAccesses); |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 227 | Value *ValueOperand = getNewValue(Stmt, Store->getValueOperand(), BBMap, LTS, |
Johannes Doerfert | 2c3ffc0 | 2016-02-16 12:36:14 +0000 | [diff] [blame] | 228 | getLoopForStmt(Stmt)); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 229 | |
Tobias Grosser | 86bc93a | 2015-09-06 08:47:57 +0000 | [diff] [blame] | 230 | if (DebugPrinting) |
| 231 | RuntimeDebugBuilder::createCPUPrinter(Builder, "Store to ", NewPointer, |
| 232 | ": ", ValueOperand, "\n"); |
| 233 | |
Tobias Grosser | c186ac7 | 2015-08-11 08:13:15 +0000 | [diff] [blame] | 234 | Builder.CreateAlignedStore(ValueOperand, NewPointer, Store->getAlignment()); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 235 | } |
| 236 | |
Johannes Doerfert | 5dced26 | 2015-12-22 19:08:49 +0000 | [diff] [blame] | 237 | bool BlockGenerator::canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst) { |
Johannes Doerfert | 2c3ffc0 | 2016-02-16 12:36:14 +0000 | [diff] [blame] | 238 | Loop *L = getLoopForStmt(Stmt); |
Johannes Doerfert | 5dced26 | 2015-12-22 19:08:49 +0000 | [diff] [blame] | 239 | return (Stmt.isBlockStmt() || !Stmt.getRegion()->contains(L)) && |
Johannes Doerfert | 0f0d209b | 2016-05-23 12:47:09 +0000 | [diff] [blame] | 240 | canSynthesize(Inst, *Stmt.getParent(), &LI, &SE, L); |
Johannes Doerfert | 5dced26 | 2015-12-22 19:08:49 +0000 | [diff] [blame] | 241 | } |
| 242 | |
Tobias Grosser | 2f1acac | 2015-10-04 10:18:45 +0000 | [diff] [blame] | 243 | void BlockGenerator::copyInstruction(ScopStmt &Stmt, Instruction *Inst, |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 244 | ValueMapT &BBMap, LoopToScevMapT <S, |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 245 | isl_id_to_ast_expr *NewAccesses) { |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 246 | // Terminator instructions control the control flow. They are explicitly |
| 247 | // expressed in the clast and do not need to be copied. |
| 248 | if (Inst->isTerminator()) |
| 249 | return; |
| 250 | |
Johannes Doerfert | 5dced26 | 2015-12-22 19:08:49 +0000 | [diff] [blame] | 251 | // Synthesizable statements will be generated on-demand. |
| 252 | if (canSyntheziseInStmt(Stmt, Inst)) |
Tobias Grosser | e71c6ab | 2012-04-27 16:36:14 +0000 | [diff] [blame] | 253 | return; |
| 254 | |
Tobias Grosser | 9646e3f | 2015-10-04 10:18:39 +0000 | [diff] [blame] | 255 | if (auto *Load = dyn_cast<LoadInst>(Inst)) { |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 256 | Value *NewLoad = generateScalarLoad(Stmt, Load, BBMap, LTS, NewAccesses); |
Sebastian Pop | 3d94fed | 2013-05-24 18:46:02 +0000 | [diff] [blame] | 257 | // Compute NewLoad before its insertion in BBMap to make the insertion |
| 258 | // deterministic. |
Sebastian Pop | 753d43f | 2013-05-24 17:16:02 +0000 | [diff] [blame] | 259 | BBMap[Load] = NewLoad; |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 260 | return; |
| 261 | } |
| 262 | |
Tobias Grosser | 9646e3f | 2015-10-04 10:18:39 +0000 | [diff] [blame] | 263 | if (auto *Store = dyn_cast<StoreInst>(Inst)) { |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 264 | generateScalarStore(Stmt, Store, BBMap, LTS, NewAccesses); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 265 | return; |
| 266 | } |
| 267 | |
Tobias Grosser | 9646e3f | 2015-10-04 10:18:39 +0000 | [diff] [blame] | 268 | if (auto *PHI = dyn_cast<PHINode>(Inst)) { |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 269 | copyPHIInstruction(Stmt, PHI, BBMap, LTS); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 270 | return; |
| 271 | } |
| 272 | |
Johannes Doerfert | 3f500fa | 2015-01-25 18:07:30 +0000 | [diff] [blame] | 273 | // Skip some special intrinsics for which we do not adjust the semantics to |
| 274 | // the new schedule. All others are handled like every other instruction. |
Tobias Grosser | 9c0ffe3 | 2015-08-30 16:57:15 +0000 | [diff] [blame] | 275 | if (isIgnoredIntrinsic(Inst)) |
| 276 | return; |
Johannes Doerfert | 3f500fa | 2015-01-25 18:07:30 +0000 | [diff] [blame] | 277 | |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 278 | copyInstScalar(Stmt, Inst, BBMap, LTS); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 279 | } |
| 280 | |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 281 | void BlockGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT <S, |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 282 | isl_id_to_ast_expr *NewAccesses) { |
Johannes Doerfert | 275a175 | 2015-02-24 16:16:32 +0000 | [diff] [blame] | 283 | assert(Stmt.isBlockStmt() && |
| 284 | "Only block statements can be copied by the block generator"); |
| 285 | |
| 286 | ValueMapT BBMap; |
| 287 | |
Johannes Doerfert | be9c911 | 2015-02-06 21:39:31 +0000 | [diff] [blame] | 288 | BasicBlock *BB = Stmt.getBasicBlock(); |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 289 | copyBB(Stmt, BB, BBMap, LTS, NewAccesses); |
Johannes Doerfert | 275a175 | 2015-02-24 16:16:32 +0000 | [diff] [blame] | 290 | } |
| 291 | |
Johannes Doerfert | 514f6ef | 2015-02-27 18:29:04 +0000 | [diff] [blame] | 292 | BasicBlock *BlockGenerator::splitBB(BasicBlock *BB) { |
Duncan P. N. Exon Smith | b8f58b5 | 2015-11-06 22:56:54 +0000 | [diff] [blame] | 293 | BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(), |
| 294 | &*Builder.GetInsertPoint(), &DT, &LI); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 295 | CopyBB->setName("polly.stmt." + BB->getName()); |
Johannes Doerfert | 514f6ef | 2015-02-27 18:29:04 +0000 | [diff] [blame] | 296 | return CopyBB; |
| 297 | } |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 298 | |
Johannes Doerfert | 514f6ef | 2015-02-27 18:29:04 +0000 | [diff] [blame] | 299 | BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 300 | ValueMapT &BBMap, LoopToScevMapT <S, |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 301 | isl_id_to_ast_expr *NewAccesses) { |
Johannes Doerfert | 514f6ef | 2015-02-27 18:29:04 +0000 | [diff] [blame] | 302 | BasicBlock *CopyBB = splitBB(BB); |
Duncan P. N. Exon Smith | b8f58b5 | 2015-11-06 22:56:54 +0000 | [diff] [blame] | 303 | Builder.SetInsertPoint(&CopyBB->front()); |
Michael Kruse | 225f0d1 | 2015-10-17 21:36:00 +0000 | [diff] [blame] | 304 | generateScalarLoads(Stmt, BBMap); |
| 305 | |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 306 | copyBB(Stmt, BB, CopyBB, BBMap, LTS, NewAccesses); |
Michael Kruse | 225f0d1 | 2015-10-17 21:36:00 +0000 | [diff] [blame] | 307 | |
| 308 | // After a basic block was copied store all scalars that escape this block in |
| 309 | // their alloca. |
| 310 | generateScalarStores(Stmt, LTS, BBMap); |
Johannes Doerfert | 514f6ef | 2015-02-27 18:29:04 +0000 | [diff] [blame] | 311 | return CopyBB; |
| 312 | } |
| 313 | |
| 314 | void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB, |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 315 | ValueMapT &BBMap, LoopToScevMapT <S, |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 316 | isl_id_to_ast_expr *NewAccesses) { |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 317 | EntryBB = &CopyBB->getParent()->getEntryBlock(); |
| 318 | |
Tobias Grosser | 91f5b26 | 2014-06-04 08:06:40 +0000 | [diff] [blame] | 319 | for (Instruction &Inst : *BB) |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 320 | copyInstruction(Stmt, &Inst, BBMap, LTS, NewAccesses); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 321 | } |
| 322 | |
Tobias Grosser | 64c0ff4 | 2015-08-31 05:52:24 +0000 | [diff] [blame] | 323 | Value *BlockGenerator::getOrCreateAlloca(Value *ScalarBase, |
| 324 | ScalarAllocaMapTy &Map, |
Tobias Grosser | 64c0ff4 | 2015-08-31 05:52:24 +0000 | [diff] [blame] | 325 | const char *NameExt) { |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 326 | // If no alloca was found create one and insert it in the entry block. |
Tobias Grosser | e9cb5a0 | 2015-10-03 17:19:49 +0000 | [diff] [blame] | 327 | if (!Map.count(ScalarBase)) { |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 328 | auto *Ty = ScalarBase->getType(); |
Tobias Grosser | b09455d | 2015-09-18 06:01:11 +0000 | [diff] [blame] | 329 | auto NewAddr = new AllocaInst(Ty, ScalarBase->getName() + NameExt); |
Tobias Grosser | 64c0ff4 | 2015-08-31 05:52:24 +0000 | [diff] [blame] | 330 | EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock(); |
Duncan P. N. Exon Smith | b8f58b5 | 2015-11-06 22:56:54 +0000 | [diff] [blame] | 331 | NewAddr->insertBefore(&*EntryBB->getFirstInsertionPt()); |
Tobias Grosser | e9cb5a0 | 2015-10-03 17:19:49 +0000 | [diff] [blame] | 332 | Map[ScalarBase] = NewAddr; |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 333 | } |
| 334 | |
Tobias Grosser | e9cb5a0 | 2015-10-03 17:19:49 +0000 | [diff] [blame] | 335 | auto Addr = Map[ScalarBase]; |
| 336 | |
Tobias Grosser | 5c7f16b | 2016-01-24 14:16:59 +0000 | [diff] [blame] | 337 | if (auto NewAddr = GlobalMap.lookup(Addr)) |
| 338 | return NewAddr; |
Tobias Grosser | 64c0ff4 | 2015-08-31 05:52:24 +0000 | [diff] [blame] | 339 | |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 340 | return Addr; |
| 341 | } |
| 342 | |
Johannes Doerfert | 800e17a | 2016-02-02 14:16:01 +0000 | [diff] [blame] | 343 | Value *BlockGenerator::getOrCreateAlloca(const MemoryAccess &Access) { |
Tobias Grosser | a535dff | 2015-12-13 19:59:01 +0000 | [diff] [blame] | 344 | if (Access.isPHIKind()) |
Tobias Grosser | b8d27aa | 2015-10-18 00:51:13 +0000 | [diff] [blame] | 345 | return getOrCreatePHIAlloca(Access.getBaseAddr()); |
| 346 | else |
| 347 | return getOrCreateScalarAlloca(Access.getBaseAddr()); |
Tobias Grosser | a4f0988 | 2015-10-17 22:16:00 +0000 | [diff] [blame] | 348 | } |
| 349 | |
| 350 | Value *BlockGenerator::getOrCreateAlloca(const ScopArrayInfo *Array) { |
Tobias Grosser | a535dff | 2015-12-13 19:59:01 +0000 | [diff] [blame] | 351 | if (Array->isPHIKind()) |
Tobias Grosser | a4f0988 | 2015-10-17 22:16:00 +0000 | [diff] [blame] | 352 | return getOrCreatePHIAlloca(Array->getBasePtr()); |
Tobias Grosser | f8d55f7 | 2015-08-29 18:12:03 +0000 | [diff] [blame] | 353 | else |
Tobias Grosser | a4f0988 | 2015-10-17 22:16:00 +0000 | [diff] [blame] | 354 | return getOrCreateScalarAlloca(Array->getBasePtr()); |
Tobias Grosser | f8d55f7 | 2015-08-29 18:12:03 +0000 | [diff] [blame] | 355 | } |
| 356 | |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 357 | Value *BlockGenerator::getOrCreateScalarAlloca(Value *ScalarBase) { |
| 358 | return getOrCreateAlloca(ScalarBase, ScalarMap, ".s2a"); |
Tobias Grosser | b79a67d | 2015-08-28 08:23:35 +0000 | [diff] [blame] | 359 | } |
| 360 | |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 361 | Value *BlockGenerator::getOrCreatePHIAlloca(Value *ScalarBase) { |
| 362 | return getOrCreateAlloca(ScalarBase, PHIOpMap, ".phiops"); |
Tobias Grosser | b79a67d | 2015-08-28 08:23:35 +0000 | [diff] [blame] | 363 | } |
| 364 | |
Johannes Doerfert | 38a012c | 2016-05-23 09:14:07 +0000 | [diff] [blame] | 365 | void BlockGenerator::handleOutsideUsers(const Scop &S, Instruction *Inst) { |
Tobias Grosser | 2985400 | 2015-08-30 15:03:59 +0000 | [diff] [blame] | 366 | // If there are escape users we get the alloca for this instruction and put it |
| 367 | // in the EscapeMap for later finalization. Lastly, if the instruction was |
| 368 | // copied multiple times we already did this and can exit. |
Michael Kruse | acb6ade | 2015-08-18 17:25:48 +0000 | [diff] [blame] | 369 | if (EscapeMap.count(Inst)) |
| 370 | return; |
Johannes Doerfert | e69e114 | 2015-08-18 11:56:00 +0000 | [diff] [blame] | 371 | |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 372 | EscapeUserVectorTy EscapeUsers; |
| 373 | for (User *U : Inst->users()) { |
| 374 | |
| 375 | // Non-instruction user will never escape. |
| 376 | Instruction *UI = dyn_cast<Instruction>(U); |
| 377 | if (!UI) |
| 378 | continue; |
| 379 | |
Johannes Doerfert | 952b530 | 2016-05-23 12:40:48 +0000 | [diff] [blame] | 380 | if (S.contains(UI)) |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 381 | continue; |
| 382 | |
| 383 | EscapeUsers.push_back(UI); |
| 384 | } |
| 385 | |
| 386 | // Exit if no escape uses were found. |
| 387 | if (EscapeUsers.empty()) |
| 388 | return; |
| 389 | |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 390 | // Get or create an escape alloca for this instruction. |
Johannes Doerfert | 38a012c | 2016-05-23 09:14:07 +0000 | [diff] [blame] | 391 | auto *ScalarAddr = getOrCreateScalarAlloca(Inst); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 392 | |
| 393 | // Remember that this instruction has escape uses and the escape alloca. |
| 394 | EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers)); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 395 | } |
| 396 | |
Michael Kruse | 225f0d1 | 2015-10-17 21:36:00 +0000 | [diff] [blame] | 397 | void BlockGenerator::generateScalarLoads(ScopStmt &Stmt, ValueMapT &BBMap) { |
| 398 | for (MemoryAccess *MA : Stmt) { |
Tobias Grosser | a535dff | 2015-12-13 19:59:01 +0000 | [diff] [blame] | 399 | if (MA->isArrayKind() || MA->isWrite()) |
Tobias Grosser | d4dd6ec | 2015-07-27 17:57:58 +0000 | [diff] [blame] | 400 | continue; |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 401 | |
Michael Kruse | e2bccbb | 2015-09-18 19:59:43 +0000 | [diff] [blame] | 402 | auto *Address = getOrCreateAlloca(*MA); |
Michael Kruse | eac9726 | 2016-02-24 22:08:14 +0000 | [diff] [blame] | 403 | assert((!isa<Instruction>(Address) || |
| 404 | DT.dominates(cast<Instruction>(Address)->getParent(), |
| 405 | Builder.GetInsertBlock())) && |
| 406 | "Domination violation"); |
Michael Kruse | e2bccbb | 2015-09-18 19:59:43 +0000 | [diff] [blame] | 407 | BBMap[MA->getBaseAddr()] = |
Tobias Grosser | 2fc50df | 2015-08-30 19:51:01 +0000 | [diff] [blame] | 408 | Builder.CreateLoad(Address, Address->getName() + ".reload"); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 409 | } |
| 410 | } |
| 411 | |
Michael Kruse | 225f0d1 | 2015-10-17 21:36:00 +0000 | [diff] [blame] | 412 | void BlockGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT <S, |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 413 | ValueMapT &BBMap) { |
Tobias Grosser | f2cdd14 | 2016-01-26 10:01:35 +0000 | [diff] [blame] | 414 | Loop *L = LI.getLoopFor(Stmt.getBasicBlock()); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 415 | |
Michael Kruse | 225f0d1 | 2015-10-17 21:36:00 +0000 | [diff] [blame] | 416 | assert(Stmt.isBlockStmt() && "Region statements need to use the " |
| 417 | "generateScalarStores() function in the " |
| 418 | "RegionGenerator"); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 419 | |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 420 | for (MemoryAccess *MA : Stmt) { |
Tobias Grosser | a535dff | 2015-12-13 19:59:01 +0000 | [diff] [blame] | 421 | if (MA->isArrayKind() || MA->isRead()) |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 422 | continue; |
| 423 | |
Johannes Doerfert | d86f215 | 2015-08-17 10:58:17 +0000 | [diff] [blame] | 424 | Value *Val = MA->getAccessValue(); |
Michael Kruse | ee6a4fc | 2016-01-26 13:33:27 +0000 | [diff] [blame] | 425 | if (MA->isAnyPHIKind()) { |
| 426 | assert(MA->getIncoming().size() >= 1 && |
| 427 | "Block statements have exactly one exiting block, or multiple but " |
| 428 | "with same incoming block and value"); |
| 429 | assert(std::all_of(MA->getIncoming().begin(), MA->getIncoming().end(), |
| 430 | [&](std::pair<BasicBlock *, Value *> p) -> bool { |
| 431 | return p.first == Stmt.getBasicBlock(); |
| 432 | }) && |
| 433 | "Incoming block must be statement's block"); |
| 434 | Val = MA->getIncoming()[0].second; |
| 435 | } |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 436 | auto *Address = getOrCreateAlloca(*MA); |
Johannes Doerfert | d86f215 | 2015-08-17 10:58:17 +0000 | [diff] [blame] | 437 | |
Tobias Grosser | f2cdd14 | 2016-01-26 10:01:35 +0000 | [diff] [blame] | 438 | Val = getNewValue(Stmt, Val, BBMap, LTS, L); |
Michael Kruse | eac9726 | 2016-02-24 22:08:14 +0000 | [diff] [blame] | 439 | assert((!isa<Instruction>(Val) || |
| 440 | DT.dominates(cast<Instruction>(Val)->getParent(), |
| 441 | Builder.GetInsertBlock())) && |
| 442 | "Domination violation"); |
| 443 | assert((!isa<Instruction>(Address) || |
| 444 | DT.dominates(cast<Instruction>(Address)->getParent(), |
| 445 | Builder.GetInsertBlock())) && |
| 446 | "Domination violation"); |
Tobias Grosser | 9224522 | 2015-07-28 14:53:44 +0000 | [diff] [blame] | 447 | Builder.CreateStore(Val, Address); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 448 | } |
| 449 | } |
| 450 | |
Tobias Grosser | c0091a7 | 2015-08-30 19:19:34 +0000 | [diff] [blame] | 451 | void BlockGenerator::createScalarInitialization(Scop &S) { |
Johannes Doerfert | ef74443 | 2016-05-23 12:42:38 +0000 | [diff] [blame] | 452 | BasicBlock *ExitBB = S.getExit(); |
Johannes Doerfert | 188542f | 2015-11-09 00:21:21 +0000 | [diff] [blame] | 453 | |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 454 | // The split block __just before__ the region and optimized region. |
Johannes Doerfert | ef74443 | 2016-05-23 12:42:38 +0000 | [diff] [blame] | 455 | BasicBlock *SplitBB = S.getEnteringBlock(); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 456 | BranchInst *SplitBBTerm = cast<BranchInst>(SplitBB->getTerminator()); |
| 457 | assert(SplitBBTerm->getNumSuccessors() == 2 && "Bad region entering block!"); |
| 458 | |
| 459 | // Get the start block of the __optimized__ region. |
| 460 | BasicBlock *StartBB = SplitBBTerm->getSuccessor(0); |
Johannes Doerfert | ef74443 | 2016-05-23 12:42:38 +0000 | [diff] [blame] | 461 | if (StartBB == S.getEntry()) |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 462 | StartBB = SplitBBTerm->getSuccessor(1); |
| 463 | |
Johannes Doerfert | fb19dd6 | 2015-09-26 20:57:59 +0000 | [diff] [blame] | 464 | Builder.SetInsertPoint(StartBB->getTerminator()); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 465 | |
Tobias Grosser | c0091a7 | 2015-08-30 19:19:34 +0000 | [diff] [blame] | 466 | for (auto &Pair : S.arrays()) { |
| 467 | auto &Array = Pair.second; |
| 468 | if (Array->getNumberOfDimensions() != 0) |
| 469 | continue; |
Tobias Grosser | a535dff | 2015-12-13 19:59:01 +0000 | [diff] [blame] | 470 | if (Array->isPHIKind()) { |
Tobias Grosser | c0091a7 | 2015-08-30 19:19:34 +0000 | [diff] [blame] | 471 | // For PHI nodes, the only values we need to store are the ones that |
| 472 | // reach the PHI node from outside the region. In general there should |
| 473 | // only be one such incoming edge and this edge should enter through |
| 474 | // 'SplitBB'. |
| 475 | auto PHI = cast<PHINode>(Array->getBasePtr()); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 476 | |
Tobias Grosser | c0091a7 | 2015-08-30 19:19:34 +0000 | [diff] [blame] | 477 | for (auto BI = PHI->block_begin(), BE = PHI->block_end(); BI != BE; BI++) |
Johannes Doerfert | 952b530 | 2016-05-23 12:40:48 +0000 | [diff] [blame] | 478 | if (!S.contains(*BI) && *BI != SplitBB) |
Tobias Grosser | c0091a7 | 2015-08-30 19:19:34 +0000 | [diff] [blame] | 479 | llvm_unreachable("Incoming edges from outside the scop should always " |
| 480 | "come from SplitBB"); |
| 481 | |
| 482 | int Idx = PHI->getBasicBlockIndex(SplitBB); |
| 483 | if (Idx < 0) |
| 484 | continue; |
| 485 | |
| 486 | Value *ScalarValue = PHI->getIncomingValue(Idx); |
| 487 | |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 488 | Builder.CreateStore(ScalarValue, getOrCreatePHIAlloca(PHI)); |
Tobias Grosser | c0091a7 | 2015-08-30 19:19:34 +0000 | [diff] [blame] | 489 | continue; |
| 490 | } |
| 491 | |
| 492 | auto *Inst = dyn_cast<Instruction>(Array->getBasePtr()); |
| 493 | |
Johannes Doerfert | 952b530 | 2016-05-23 12:40:48 +0000 | [diff] [blame] | 494 | if (Inst && S.contains(Inst)) |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 495 | continue; |
| 496 | |
Johannes Doerfert | 188542f | 2015-11-09 00:21:21 +0000 | [diff] [blame] | 497 | // PHI nodes that are not marked as such in their SAI object are either exit |
| 498 | // PHI nodes we model as common scalars but without initialization, or |
| 499 | // incoming phi nodes that need to be initialized. Check if the first is the |
| 500 | // case for Inst and do not create and initialize memory if so. |
| 501 | if (auto *PHI = dyn_cast_or_null<PHINode>(Inst)) |
| 502 | if (!S.hasSingleExitEdge() && PHI->getBasicBlockIndex(ExitBB) >= 0) |
| 503 | continue; |
Johannes Doerfert | 717b866 | 2015-09-08 21:44:27 +0000 | [diff] [blame] | 504 | |
Tobias Grosser | c0091a7 | 2015-08-30 19:19:34 +0000 | [diff] [blame] | 505 | Builder.CreateStore(Array->getBasePtr(), |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 506 | getOrCreateScalarAlloca(Array->getBasePtr())); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 507 | } |
| 508 | } |
| 509 | |
Johannes Doerfert | ef74443 | 2016-05-23 12:42:38 +0000 | [diff] [blame] | 510 | void BlockGenerator::createScalarFinalization(Scop &S) { |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 511 | // The exit block of the __unoptimized__ region. |
Johannes Doerfert | ef74443 | 2016-05-23 12:42:38 +0000 | [diff] [blame] | 512 | BasicBlock *ExitBB = S.getExitingBlock(); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 513 | // The merge block __just after__ the region and the optimized region. |
Johannes Doerfert | ef74443 | 2016-05-23 12:42:38 +0000 | [diff] [blame] | 514 | BasicBlock *MergeBB = S.getExit(); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 515 | |
| 516 | // The exit block of the __optimized__ region. |
| 517 | BasicBlock *OptExitBB = *(pred_begin(MergeBB)); |
| 518 | if (OptExitBB == ExitBB) |
| 519 | OptExitBB = *(++pred_begin(MergeBB)); |
| 520 | |
| 521 | Builder.SetInsertPoint(OptExitBB->getTerminator()); |
| 522 | for (const auto &EscapeMapping : EscapeMap) { |
| 523 | // Extract the escaping instruction and the escaping users as well as the |
| 524 | // alloca the instruction was demoted to. |
| 525 | Instruction *EscapeInst = EscapeMapping.getFirst(); |
| 526 | const auto &EscapeMappingValue = EscapeMapping.getSecond(); |
| 527 | const EscapeUserVectorTy &EscapeUsers = EscapeMappingValue.second; |
Tobias Grosser | 64c0ff4 | 2015-08-31 05:52:24 +0000 | [diff] [blame] | 528 | Value *ScalarAddr = EscapeMappingValue.first; |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 529 | |
| 530 | // Reload the demoted instruction in the optimized version of the SCoP. |
Johannes Doerfert | d8b6ad2 | 2015-10-18 12:36:42 +0000 | [diff] [blame] | 531 | Value *EscapeInstReload = |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 532 | Builder.CreateLoad(ScalarAddr, EscapeInst->getName() + ".final_reload"); |
Johannes Doerfert | d8b6ad2 | 2015-10-18 12:36:42 +0000 | [diff] [blame] | 533 | EscapeInstReload = |
| 534 | Builder.CreateBitOrPointerCast(EscapeInstReload, EscapeInst->getType()); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 535 | |
| 536 | // Create the merge PHI that merges the optimized and unoptimized version. |
| 537 | PHINode *MergePHI = PHINode::Create(EscapeInst->getType(), 2, |
| 538 | EscapeInst->getName() + ".merge"); |
Duncan P. N. Exon Smith | b8f58b5 | 2015-11-06 22:56:54 +0000 | [diff] [blame] | 539 | MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt()); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 540 | |
| 541 | // Add the respective values to the merge PHI. |
| 542 | MergePHI->addIncoming(EscapeInstReload, OptExitBB); |
| 543 | MergePHI->addIncoming(EscapeInst, ExitBB); |
| 544 | |
| 545 | // The information of scalar evolution about the escaping instruction needs |
| 546 | // to be revoked so the new merged instruction will be used. |
| 547 | if (SE.isSCEVable(EscapeInst->getType())) |
| 548 | SE.forgetValue(EscapeInst); |
| 549 | |
| 550 | // Replace all uses of the demoted instruction with the merge PHI. |
| 551 | for (Instruction *EUser : EscapeUsers) |
| 552 | EUser->replaceUsesOfWith(EscapeInst, MergePHI); |
| 553 | } |
| 554 | } |
| 555 | |
Tobias Grosser | ffa2446 | 2015-10-17 08:54:13 +0000 | [diff] [blame] | 556 | void BlockGenerator::findOutsideUsers(Scop &S) { |
Tobias Grosser | ffa2446 | 2015-10-17 08:54:13 +0000 | [diff] [blame] | 557 | for (auto &Pair : S.arrays()) { |
| 558 | auto &Array = Pair.second; |
| 559 | |
| 560 | if (Array->getNumberOfDimensions() != 0) |
| 561 | continue; |
| 562 | |
Tobias Grosser | a535dff | 2015-12-13 19:59:01 +0000 | [diff] [blame] | 563 | if (Array->isPHIKind()) |
Tobias Grosser | ffa2446 | 2015-10-17 08:54:13 +0000 | [diff] [blame] | 564 | continue; |
| 565 | |
| 566 | auto *Inst = dyn_cast<Instruction>(Array->getBasePtr()); |
| 567 | |
| 568 | if (!Inst) |
| 569 | continue; |
| 570 | |
| 571 | // Scop invariant hoisting moves some of the base pointers out of the scop. |
| 572 | // We can ignore these, as the invariant load hoisting already registers the |
| 573 | // relevant outside users. |
Johannes Doerfert | 952b530 | 2016-05-23 12:40:48 +0000 | [diff] [blame] | 574 | if (!S.contains(Inst)) |
Tobias Grosser | ffa2446 | 2015-10-17 08:54:13 +0000 | [diff] [blame] | 575 | continue; |
| 576 | |
Johannes Doerfert | 38a012c | 2016-05-23 09:14:07 +0000 | [diff] [blame] | 577 | handleOutsideUsers(S, Inst); |
Tobias Grosser | ffa2446 | 2015-10-17 08:54:13 +0000 | [diff] [blame] | 578 | } |
| 579 | } |
| 580 | |
Tobias Grosser | 27d742d | 2015-10-24 17:41:29 +0000 | [diff] [blame] | 581 | void BlockGenerator::createExitPHINodeMerges(Scop &S) { |
| 582 | if (S.hasSingleExitEdge()) |
| 583 | return; |
| 584 | |
Johannes Doerfert | ef74443 | 2016-05-23 12:42:38 +0000 | [diff] [blame] | 585 | auto *ExitBB = S.getExitingBlock(); |
| 586 | auto *MergeBB = S.getExit(); |
Tobias Grosser | 27d742d | 2015-10-24 17:41:29 +0000 | [diff] [blame] | 587 | auto *AfterMergeBB = MergeBB->getSingleSuccessor(); |
| 588 | BasicBlock *OptExitBB = *(pred_begin(MergeBB)); |
| 589 | if (OptExitBB == ExitBB) |
| 590 | OptExitBB = *(++pred_begin(MergeBB)); |
| 591 | |
| 592 | Builder.SetInsertPoint(OptExitBB->getTerminator()); |
| 593 | |
| 594 | for (auto &Pair : S.arrays()) { |
| 595 | auto &SAI = Pair.second; |
| 596 | auto *Val = SAI->getBasePtr(); |
| 597 | |
Michael Kruse | faedfcb | 2016-03-03 17:20:43 +0000 | [diff] [blame] | 598 | // Only Value-like scalars need a merge PHI. Exit block PHIs receive either |
| 599 | // the original PHI's value or the reloaded incoming values from the |
| 600 | // generated code. An llvm::Value is merged between the original code's |
| 601 | // value or the generated one. |
| 602 | if (!SAI->isValueKind() && !SAI->isExitPHIKind()) |
| 603 | continue; |
| 604 | |
Tobias Grosser | 27d742d | 2015-10-24 17:41:29 +0000 | [diff] [blame] | 605 | PHINode *PHI = dyn_cast<PHINode>(Val); |
| 606 | if (!PHI) |
| 607 | continue; |
| 608 | |
Tobias Grosser | a3f6eda | 2015-10-24 19:01:09 +0000 | [diff] [blame] | 609 | if (PHI->getParent() != AfterMergeBB) |
Tobias Grosser | 27d742d | 2015-10-24 17:41:29 +0000 | [diff] [blame] | 610 | continue; |
Tobias Grosser | 27d742d | 2015-10-24 17:41:29 +0000 | [diff] [blame] | 611 | |
| 612 | std::string Name = PHI->getName(); |
| 613 | Value *ScalarAddr = getOrCreateScalarAlloca(PHI); |
| 614 | Value *Reload = Builder.CreateLoad(ScalarAddr, Name + ".ph.final_reload"); |
| 615 | Reload = Builder.CreateBitOrPointerCast(Reload, PHI->getType()); |
| 616 | Value *OriginalValue = PHI->getIncomingValueForBlock(MergeBB); |
Michael Kruse | faedfcb | 2016-03-03 17:20:43 +0000 | [diff] [blame] | 617 | assert((!isa<Instruction>(OriginalValue) || |
| 618 | cast<Instruction>(OriginalValue)->getParent() != MergeBB) && |
| 619 | "Original value must no be one we just generated."); |
Tobias Grosser | 27d742d | 2015-10-24 17:41:29 +0000 | [diff] [blame] | 620 | auto *MergePHI = PHINode::Create(PHI->getType(), 2, Name + ".ph.merge"); |
Duncan P. N. Exon Smith | b8f58b5 | 2015-11-06 22:56:54 +0000 | [diff] [blame] | 621 | MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt()); |
Tobias Grosser | 27d742d | 2015-10-24 17:41:29 +0000 | [diff] [blame] | 622 | MergePHI->addIncoming(Reload, OptExitBB); |
| 623 | MergePHI->addIncoming(OriginalValue, ExitBB); |
| 624 | int Idx = PHI->getBasicBlockIndex(MergeBB); |
| 625 | PHI->setIncomingValue(Idx, MergePHI); |
| 626 | } |
| 627 | } |
| 628 | |
Tobias Grosser | ffa2446 | 2015-10-17 08:54:13 +0000 | [diff] [blame] | 629 | void BlockGenerator::finalizeSCoP(Scop &S) { |
| 630 | findOutsideUsers(S); |
Tobias Grosser | c0091a7 | 2015-08-30 19:19:34 +0000 | [diff] [blame] | 631 | createScalarInitialization(S); |
Tobias Grosser | 27d742d | 2015-10-24 17:41:29 +0000 | [diff] [blame] | 632 | createExitPHINodeMerges(S); |
Johannes Doerfert | ef74443 | 2016-05-23 12:42:38 +0000 | [diff] [blame] | 633 | createScalarFinalization(S); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 634 | } |
| 635 | |
Johannes Doerfert | be9c911 | 2015-02-06 21:39:31 +0000 | [diff] [blame] | 636 | VectorBlockGenerator::VectorBlockGenerator(BlockGenerator &BlockGen, |
Johannes Doerfert | be9c911 | 2015-02-06 21:39:31 +0000 | [diff] [blame] | 637 | std::vector<LoopToScevMapT> &VLTS, |
| 638 | isl_map *Schedule) |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 639 | : BlockGenerator(BlockGen), VLTS(VLTS), Schedule(Schedule) { |
Sebastian Pop | a00a029 | 2012-12-18 07:46:06 +0000 | [diff] [blame] | 640 | assert(Schedule && "No statement domain provided"); |
| 641 | } |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 642 | |
Tobias Grosser | 2f1acac | 2015-10-04 10:18:45 +0000 | [diff] [blame] | 643 | Value *VectorBlockGenerator::getVectorValue(ScopStmt &Stmt, Value *Old, |
Tobias Grosser | e602a07 | 2013-05-07 07:30:56 +0000 | [diff] [blame] | 644 | ValueMapT &VectorMap, |
| 645 | VectorValueMapT &ScalarMaps, |
| 646 | Loop *L) { |
Hongbin Zheng | fe11e28 | 2013-06-29 13:22:15 +0000 | [diff] [blame] | 647 | if (Value *NewValue = VectorMap.lookup(Old)) |
| 648 | return NewValue; |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 649 | |
| 650 | int Width = getVectorWidth(); |
| 651 | |
| 652 | Value *Vector = UndefValue::get(VectorType::get(Old->getType(), Width)); |
| 653 | |
| 654 | for (int Lane = 0; Lane < Width; Lane++) |
Tobias Grosser | c14582f | 2013-02-05 18:01:29 +0000 | [diff] [blame] | 655 | Vector = Builder.CreateInsertElement( |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 656 | Vector, getNewValue(Stmt, Old, ScalarMaps[Lane], VLTS[Lane], L), |
Tobias Grosser | 7242ad9 | 2013-02-22 08:07:06 +0000 | [diff] [blame] | 657 | Builder.getInt32(Lane)); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 658 | |
| 659 | VectorMap[Old] = Vector; |
| 660 | |
| 661 | return Vector; |
| 662 | } |
| 663 | |
| 664 | Type *VectorBlockGenerator::getVectorPtrTy(const Value *Val, int Width) { |
| 665 | PointerType *PointerTy = dyn_cast<PointerType>(Val->getType()); |
| 666 | assert(PointerTy && "PointerType expected"); |
| 667 | |
| 668 | Type *ScalarType = PointerTy->getElementType(); |
| 669 | VectorType *VectorType = VectorType::get(ScalarType, Width); |
| 670 | |
| 671 | return PointerType::getUnqual(VectorType); |
| 672 | } |
| 673 | |
Johannes Doerfert | be9c911 | 2015-02-06 21:39:31 +0000 | [diff] [blame] | 674 | Value *VectorBlockGenerator::generateStrideOneLoad( |
Tobias Grosser | 2f1acac | 2015-10-04 10:18:45 +0000 | [diff] [blame] | 675 | ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps, |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 676 | __isl_keep isl_id_to_ast_expr *NewAccesses, bool NegativeStride = false) { |
Tobias Grosser | 0dd463f | 2014-03-19 19:27:24 +0000 | [diff] [blame] | 677 | unsigned VectorWidth = getVectorWidth(); |
Tobias Grosser | 9646e3f | 2015-10-04 10:18:39 +0000 | [diff] [blame] | 678 | auto *Pointer = Load->getPointerOperand(); |
Tobias Grosser | 0dd463f | 2014-03-19 19:27:24 +0000 | [diff] [blame] | 679 | Type *VectorPtrType = getVectorPtrTy(Pointer, VectorWidth); |
| 680 | unsigned Offset = NegativeStride ? VectorWidth - 1 : 0; |
| 681 | |
Michael Kruse | 8f25b0c | 2016-02-25 15:52:43 +0000 | [diff] [blame] | 682 | Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[Offset], |
| 683 | VLTS[Offset], NewAccesses); |
Tobias Grosser | c14582f | 2013-02-05 18:01:29 +0000 | [diff] [blame] | 684 | Value *VectorPtr = |
| 685 | Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr"); |
| 686 | LoadInst *VecLoad = |
| 687 | Builder.CreateLoad(VectorPtr, Load->getName() + "_p_vec_full"); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 688 | if (!Aligned) |
| 689 | VecLoad->setAlignment(8); |
| 690 | |
Tobias Grosser | 0dd463f | 2014-03-19 19:27:24 +0000 | [diff] [blame] | 691 | if (NegativeStride) { |
| 692 | SmallVector<Constant *, 16> Indices; |
| 693 | for (int i = VectorWidth - 1; i >= 0; i--) |
| 694 | Indices.push_back(ConstantInt::get(Builder.getInt32Ty(), i)); |
| 695 | Constant *SV = llvm::ConstantVector::get(Indices); |
| 696 | Value *RevVecLoad = Builder.CreateShuffleVector( |
| 697 | VecLoad, VecLoad, SV, Load->getName() + "_reverse"); |
| 698 | return RevVecLoad; |
| 699 | } |
| 700 | |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 701 | return VecLoad; |
| 702 | } |
| 703 | |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 704 | Value *VectorBlockGenerator::generateStrideZeroLoad( |
Tobias Grosser | 2f1acac | 2015-10-04 10:18:45 +0000 | [diff] [blame] | 705 | ScopStmt &Stmt, LoadInst *Load, ValueMapT &BBMap, |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 706 | __isl_keep isl_id_to_ast_expr *NewAccesses) { |
Tobias Grosser | 9646e3f | 2015-10-04 10:18:39 +0000 | [diff] [blame] | 707 | auto *Pointer = Load->getPointerOperand(); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 708 | Type *VectorPtrType = getVectorPtrTy(Pointer, 1); |
Michael Kruse | 70131d3 | 2016-01-27 17:09:17 +0000 | [diff] [blame] | 709 | Value *NewPointer = |
| 710 | generateLocationAccessed(Stmt, Load, BBMap, VLTS[0], NewAccesses); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 711 | Value *VectorPtr = Builder.CreateBitCast(NewPointer, VectorPtrType, |
| 712 | Load->getName() + "_p_vec_p"); |
Tobias Grosser | c14582f | 2013-02-05 18:01:29 +0000 | [diff] [blame] | 713 | LoadInst *ScalarLoad = |
| 714 | Builder.CreateLoad(VectorPtr, Load->getName() + "_p_splat_one"); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 715 | |
| 716 | if (!Aligned) |
| 717 | ScalarLoad->setAlignment(8); |
| 718 | |
Tobias Grosser | c14582f | 2013-02-05 18:01:29 +0000 | [diff] [blame] | 719 | Constant *SplatVector = Constant::getNullValue( |
| 720 | VectorType::get(Builder.getInt32Ty(), getVectorWidth())); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 721 | |
Tobias Grosser | c14582f | 2013-02-05 18:01:29 +0000 | [diff] [blame] | 722 | Value *VectorLoad = Builder.CreateShuffleVector( |
| 723 | ScalarLoad, ScalarLoad, SplatVector, Load->getName() + "_p_splat"); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 724 | return VectorLoad; |
| 725 | } |
| 726 | |
Johannes Doerfert | be9c911 | 2015-02-06 21:39:31 +0000 | [diff] [blame] | 727 | Value *VectorBlockGenerator::generateUnknownStrideLoad( |
Tobias Grosser | 2f1acac | 2015-10-04 10:18:45 +0000 | [diff] [blame] | 728 | ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps, |
Johannes Doerfert | 09e3697 | 2015-10-07 20:17:36 +0000 | [diff] [blame] | 729 | __isl_keep isl_id_to_ast_expr *NewAccesses) { |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 730 | int VectorWidth = getVectorWidth(); |
Tobias Grosser | 9646e3f | 2015-10-04 10:18:39 +0000 | [diff] [blame] | 731 | auto *Pointer = Load->getPointerOperand(); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 732 | VectorType *VectorType = VectorType::get( |
Tobias Grosser | c14582f | 2013-02-05 18:01:29 +0000 | [diff] [blame] | 733 | dyn_cast<PointerType>(Pointer->getType())->getElementType(), VectorWidth); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 734 | |
| 735 | Value *Vector = UndefValue::get(VectorType); |
| 736 | |
| 737 | for (int i = 0; i < VectorWidth; i++) { |
Michael Kruse | 70131d3 | 2016-01-27 17:09:17 +0000 | [diff] [blame] | 738 | Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[i], |
| 739 | VLTS[i], NewAccesses); |
Tobias Grosser | c14582f | 2013-02-05 18:01:29 +0000 | [diff] [blame] | 740 | Value *ScalarLoad = |
| 741 | Builder.CreateLoad(NewPointer, Load->getName() + "_p_scalar_"); |
| 742 | Vector = Builder.CreateInsertElement( |
| 743 | Vector, ScalarLoad, Builder.getInt32(i), Load->getName() + "_p_vec_"); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 744 | } |
| 745 | |
| 746 | return Vector; |
| 747 | } |
| 748 | |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 749 | void VectorBlockGenerator::generateLoad( |
Tobias Grosser | 2f1acac | 2015-10-04 10:18:45 +0000 | [diff] [blame] | 750 | ScopStmt &Stmt, LoadInst *Load, ValueMapT &VectorMap, |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 751 | VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) { |
Johannes Doerfert | c1db67e | 2015-09-29 23:47:21 +0000 | [diff] [blame] | 752 | if (Value *PreloadLoad = GlobalMap.lookup(Load)) { |
| 753 | VectorMap[Load] = Builder.CreateVectorSplat(getVectorWidth(), PreloadLoad, |
| 754 | Load->getName() + "_p"); |
| 755 | return; |
| 756 | } |
| 757 | |
Tobias Grosser | 2873645 | 2015-03-23 07:00:36 +0000 | [diff] [blame] | 758 | if (!VectorType::isValidElementType(Load->getType())) { |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 759 | for (int i = 0; i < getVectorWidth(); i++) |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 760 | ScalarMaps[i][Load] = |
| 761 | generateScalarLoad(Stmt, Load, ScalarMaps[i], VLTS[i], NewAccesses); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 762 | return; |
| 763 | } |
| 764 | |
Tobias Grosser | 184a492 | 2015-12-15 23:50:01 +0000 | [diff] [blame] | 765 | const MemoryAccess &Access = Stmt.getArrayAccessFor(Load); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 766 | |
Tobias Grosser | 9549398 | 2014-04-18 09:46:35 +0000 | [diff] [blame] | 767 | // Make sure we have scalar values available to access the pointer to |
| 768 | // the data location. |
| 769 | extractScalarValues(Load, VectorMap, ScalarMaps); |
| 770 | |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 771 | Value *NewLoad; |
Sebastian Pop | a00a029 | 2012-12-18 07:46:06 +0000 | [diff] [blame] | 772 | if (Access.isStrideZero(isl_map_copy(Schedule))) |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 773 | NewLoad = generateStrideZeroLoad(Stmt, Load, ScalarMaps[0], NewAccesses); |
Sebastian Pop | a00a029 | 2012-12-18 07:46:06 +0000 | [diff] [blame] | 774 | else if (Access.isStrideOne(isl_map_copy(Schedule))) |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 775 | NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses); |
Tobias Grosser | 0dd463f | 2014-03-19 19:27:24 +0000 | [diff] [blame] | 776 | else if (Access.isStrideX(isl_map_copy(Schedule), -1)) |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 777 | NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses, true); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 778 | else |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 779 | NewLoad = generateUnknownStrideLoad(Stmt, Load, ScalarMaps, NewAccesses); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 780 | |
| 781 | VectorMap[Load] = NewLoad; |
| 782 | } |
| 783 | |
Tobias Grosser | 2f1acac | 2015-10-04 10:18:45 +0000 | [diff] [blame] | 784 | void VectorBlockGenerator::copyUnaryInst(ScopStmt &Stmt, UnaryInstruction *Inst, |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 785 | ValueMapT &VectorMap, |
| 786 | VectorValueMapT &ScalarMaps) { |
| 787 | int VectorWidth = getVectorWidth(); |
Johannes Doerfert | be9c911 | 2015-02-06 21:39:31 +0000 | [diff] [blame] | 788 | Value *NewOperand = getVectorValue(Stmt, Inst->getOperand(0), VectorMap, |
Johannes Doerfert | 2c3ffc0 | 2016-02-16 12:36:14 +0000 | [diff] [blame] | 789 | ScalarMaps, getLoopForStmt(Stmt)); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 790 | |
| 791 | assert(isa<CastInst>(Inst) && "Can not generate vector code for instruction"); |
| 792 | |
| 793 | const CastInst *Cast = dyn_cast<CastInst>(Inst); |
| 794 | VectorType *DestType = VectorType::get(Inst->getType(), VectorWidth); |
| 795 | VectorMap[Inst] = Builder.CreateCast(Cast->getOpcode(), NewOperand, DestType); |
| 796 | } |
| 797 | |
Tobias Grosser | 2f1acac | 2015-10-04 10:18:45 +0000 | [diff] [blame] | 798 | void VectorBlockGenerator::copyBinaryInst(ScopStmt &Stmt, BinaryOperator *Inst, |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 799 | ValueMapT &VectorMap, |
| 800 | VectorValueMapT &ScalarMaps) { |
Johannes Doerfert | 2c3ffc0 | 2016-02-16 12:36:14 +0000 | [diff] [blame] | 801 | Loop *L = getLoopForStmt(Stmt); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 802 | Value *OpZero = Inst->getOperand(0); |
| 803 | Value *OpOne = Inst->getOperand(1); |
| 804 | |
| 805 | Value *NewOpZero, *NewOpOne; |
Johannes Doerfert | be9c911 | 2015-02-06 21:39:31 +0000 | [diff] [blame] | 806 | NewOpZero = getVectorValue(Stmt, OpZero, VectorMap, ScalarMaps, L); |
| 807 | NewOpOne = getVectorValue(Stmt, OpOne, VectorMap, ScalarMaps, L); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 808 | |
Tobias Grosser | 1bb59b0 | 2012-12-29 23:47:38 +0000 | [diff] [blame] | 809 | Value *NewInst = Builder.CreateBinOp(Inst->getOpcode(), NewOpZero, NewOpOne, |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 810 | Inst->getName() + "p_vec"); |
| 811 | VectorMap[Inst] = NewInst; |
| 812 | } |
| 813 | |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 814 | void VectorBlockGenerator::copyStore( |
Tobias Grosser | 2f1acac | 2015-10-04 10:18:45 +0000 | [diff] [blame] | 815 | ScopStmt &Stmt, StoreInst *Store, ValueMapT &VectorMap, |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 816 | VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) { |
Tobias Grosser | 184a492 | 2015-12-15 23:50:01 +0000 | [diff] [blame] | 817 | const MemoryAccess &Access = Stmt.getArrayAccessFor(Store); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 818 | |
Tobias Grosser | 9646e3f | 2015-10-04 10:18:39 +0000 | [diff] [blame] | 819 | auto *Pointer = Store->getPointerOperand(); |
Johannes Doerfert | be9c911 | 2015-02-06 21:39:31 +0000 | [diff] [blame] | 820 | Value *Vector = getVectorValue(Stmt, Store->getValueOperand(), VectorMap, |
Johannes Doerfert | 2c3ffc0 | 2016-02-16 12:36:14 +0000 | [diff] [blame] | 821 | ScalarMaps, getLoopForStmt(Stmt)); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 822 | |
Tobias Grosser | 50fd701 | 2014-04-17 23:13:49 +0000 | [diff] [blame] | 823 | // Make sure we have scalar values available to access the pointer to |
| 824 | // the data location. |
| 825 | extractScalarValues(Store, VectorMap, ScalarMaps); |
| 826 | |
Sebastian Pop | a00a029 | 2012-12-18 07:46:06 +0000 | [diff] [blame] | 827 | if (Access.isStrideOne(isl_map_copy(Schedule))) { |
Johannes Doerfert | 1947f86 | 2014-10-08 20:18:32 +0000 | [diff] [blame] | 828 | Type *VectorPtrType = getVectorPtrTy(Pointer, getVectorWidth()); |
Michael Kruse | 70131d3 | 2016-01-27 17:09:17 +0000 | [diff] [blame] | 829 | Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[0], |
| 830 | VLTS[0], NewAccesses); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 831 | |
Tobias Grosser | c14582f | 2013-02-05 18:01:29 +0000 | [diff] [blame] | 832 | Value *VectorPtr = |
| 833 | Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr"); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 834 | StoreInst *Store = Builder.CreateStore(Vector, VectorPtr); |
| 835 | |
| 836 | if (!Aligned) |
| 837 | Store->setAlignment(8); |
| 838 | } else { |
| 839 | for (unsigned i = 0; i < ScalarMaps.size(); i++) { |
Tobias Grosser | 1bb59b0 | 2012-12-29 23:47:38 +0000 | [diff] [blame] | 840 | Value *Scalar = Builder.CreateExtractElement(Vector, Builder.getInt32(i)); |
Michael Kruse | 70131d3 | 2016-01-27 17:09:17 +0000 | [diff] [blame] | 841 | Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[i], |
| 842 | VLTS[i], NewAccesses); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 843 | Builder.CreateStore(Scalar, NewPointer); |
| 844 | } |
| 845 | } |
| 846 | } |
| 847 | |
| 848 | bool VectorBlockGenerator::hasVectorOperands(const Instruction *Inst, |
| 849 | ValueMapT &VectorMap) { |
Tobias Grosser | 91f5b26 | 2014-06-04 08:06:40 +0000 | [diff] [blame] | 850 | for (Value *Operand : Inst->operands()) |
| 851 | if (VectorMap.count(Operand)) |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 852 | return true; |
| 853 | return false; |
| 854 | } |
| 855 | |
| 856 | bool VectorBlockGenerator::extractScalarValues(const Instruction *Inst, |
| 857 | ValueMapT &VectorMap, |
| 858 | VectorValueMapT &ScalarMaps) { |
| 859 | bool HasVectorOperand = false; |
| 860 | int VectorWidth = getVectorWidth(); |
| 861 | |
Tobias Grosser | 91f5b26 | 2014-06-04 08:06:40 +0000 | [diff] [blame] | 862 | for (Value *Operand : Inst->operands()) { |
| 863 | ValueMapT::iterator VecOp = VectorMap.find(Operand); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 864 | |
| 865 | if (VecOp == VectorMap.end()) |
| 866 | continue; |
| 867 | |
| 868 | HasVectorOperand = true; |
| 869 | Value *NewVector = VecOp->second; |
| 870 | |
| 871 | for (int i = 0; i < VectorWidth; ++i) { |
| 872 | ValueMapT &SM = ScalarMaps[i]; |
| 873 | |
| 874 | // If there is one scalar extracted, all scalar elements should have |
| 875 | // already been extracted by the code here. So no need to check for the |
| 876 | // existance of all of them. |
Tobias Grosser | 91f5b26 | 2014-06-04 08:06:40 +0000 | [diff] [blame] | 877 | if (SM.count(Operand)) |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 878 | break; |
| 879 | |
Tobias Grosser | 91f5b26 | 2014-06-04 08:06:40 +0000 | [diff] [blame] | 880 | SM[Operand] = |
| 881 | Builder.CreateExtractElement(NewVector, Builder.getInt32(i)); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 882 | } |
| 883 | } |
| 884 | |
| 885 | return HasVectorOperand; |
| 886 | } |
| 887 | |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 888 | void VectorBlockGenerator::copyInstScalarized( |
Tobias Grosser | 2f1acac | 2015-10-04 10:18:45 +0000 | [diff] [blame] | 889 | ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap, |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 890 | VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) { |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 891 | bool HasVectorOperand; |
| 892 | int VectorWidth = getVectorWidth(); |
| 893 | |
| 894 | HasVectorOperand = extractScalarValues(Inst, VectorMap, ScalarMaps); |
| 895 | |
| 896 | for (int VectorLane = 0; VectorLane < getVectorWidth(); VectorLane++) |
Johannes Doerfert | be9c911 | 2015-02-06 21:39:31 +0000 | [diff] [blame] | 897 | BlockGenerator::copyInstruction(Stmt, Inst, ScalarMaps[VectorLane], |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 898 | VLTS[VectorLane], NewAccesses); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 899 | |
| 900 | if (!VectorType::isValidElementType(Inst->getType()) || !HasVectorOperand) |
| 901 | return; |
| 902 | |
| 903 | // Make the result available as vector value. |
| 904 | VectorType *VectorType = VectorType::get(Inst->getType(), VectorWidth); |
| 905 | Value *Vector = UndefValue::get(VectorType); |
| 906 | |
| 907 | for (int i = 0; i < VectorWidth; i++) |
| 908 | Vector = Builder.CreateInsertElement(Vector, ScalarMaps[i][Inst], |
| 909 | Builder.getInt32(i)); |
| 910 | |
| 911 | VectorMap[Inst] = Vector; |
| 912 | } |
| 913 | |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 914 | int VectorBlockGenerator::getVectorWidth() { return VLTS.size(); } |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 915 | |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 916 | void VectorBlockGenerator::copyInstruction( |
Tobias Grosser | 2f1acac | 2015-10-04 10:18:45 +0000 | [diff] [blame] | 917 | ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap, |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 918 | VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) { |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 919 | // Terminator instructions control the control flow. They are explicitly |
| 920 | // expressed in the clast and do not need to be copied. |
| 921 | if (Inst->isTerminator()) |
| 922 | return; |
| 923 | |
Johannes Doerfert | 5dced26 | 2015-12-22 19:08:49 +0000 | [diff] [blame] | 924 | if (canSyntheziseInStmt(Stmt, Inst)) |
Tobias Grosser | e71c6ab | 2012-04-27 16:36:14 +0000 | [diff] [blame] | 925 | return; |
| 926 | |
Tobias Grosser | 9646e3f | 2015-10-04 10:18:39 +0000 | [diff] [blame] | 927 | if (auto *Load = dyn_cast<LoadInst>(Inst)) { |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 928 | generateLoad(Stmt, Load, VectorMap, ScalarMaps, NewAccesses); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 929 | return; |
| 930 | } |
| 931 | |
| 932 | if (hasVectorOperands(Inst, VectorMap)) { |
Tobias Grosser | 9646e3f | 2015-10-04 10:18:39 +0000 | [diff] [blame] | 933 | if (auto *Store = dyn_cast<StoreInst>(Inst)) { |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 934 | copyStore(Stmt, Store, VectorMap, ScalarMaps, NewAccesses); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 935 | return; |
| 936 | } |
| 937 | |
Tobias Grosser | 9646e3f | 2015-10-04 10:18:39 +0000 | [diff] [blame] | 938 | if (auto *Unary = dyn_cast<UnaryInstruction>(Inst)) { |
Johannes Doerfert | be9c911 | 2015-02-06 21:39:31 +0000 | [diff] [blame] | 939 | copyUnaryInst(Stmt, Unary, VectorMap, ScalarMaps); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 940 | return; |
| 941 | } |
| 942 | |
Tobias Grosser | 9646e3f | 2015-10-04 10:18:39 +0000 | [diff] [blame] | 943 | if (auto *Binary = dyn_cast<BinaryOperator>(Inst)) { |
Johannes Doerfert | be9c911 | 2015-02-06 21:39:31 +0000 | [diff] [blame] | 944 | copyBinaryInst(Stmt, Binary, VectorMap, ScalarMaps); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 945 | return; |
| 946 | } |
| 947 | |
| 948 | // Falltrough: We generate scalar instructions, if we don't know how to |
| 949 | // generate vector code. |
| 950 | } |
| 951 | |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 952 | copyInstScalarized(Stmt, Inst, VectorMap, ScalarMaps, NewAccesses); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 953 | } |
| 954 | |
Tobias Grosser | a69d4f0 | 2015-12-15 23:49:58 +0000 | [diff] [blame] | 955 | void VectorBlockGenerator::generateScalarVectorLoads( |
| 956 | ScopStmt &Stmt, ValueMapT &VectorBlockMap) { |
| 957 | for (MemoryAccess *MA : Stmt) { |
| 958 | if (MA->isArrayKind() || MA->isWrite()) |
| 959 | continue; |
| 960 | |
| 961 | auto *Address = getOrCreateAlloca(*MA); |
| 962 | Type *VectorPtrType = getVectorPtrTy(Address, 1); |
| 963 | Value *VectorPtr = Builder.CreateBitCast(Address, VectorPtrType, |
| 964 | Address->getName() + "_p_vec_p"); |
| 965 | auto *Val = Builder.CreateLoad(VectorPtr, Address->getName() + ".reload"); |
| 966 | Constant *SplatVector = Constant::getNullValue( |
| 967 | VectorType::get(Builder.getInt32Ty(), getVectorWidth())); |
| 968 | |
| 969 | Value *VectorVal = Builder.CreateShuffleVector( |
| 970 | Val, Val, SplatVector, Address->getName() + "_p_splat"); |
| 971 | VectorBlockMap[MA->getBaseAddr()] = VectorVal; |
Tobias Grosser | a69d4f0 | 2015-12-15 23:49:58 +0000 | [diff] [blame] | 972 | } |
| 973 | } |
| 974 | |
| 975 | void VectorBlockGenerator::verifyNoScalarStores(ScopStmt &Stmt) { |
| 976 | for (MemoryAccess *MA : Stmt) { |
| 977 | if (MA->isArrayKind() || MA->isRead()) |
| 978 | continue; |
| 979 | |
| 980 | llvm_unreachable("Scalar stores not expected in vector loop"); |
| 981 | } |
| 982 | } |
| 983 | |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 984 | void VectorBlockGenerator::copyStmt( |
| 985 | ScopStmt &Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses) { |
Johannes Doerfert | 275a175 | 2015-02-24 16:16:32 +0000 | [diff] [blame] | 986 | assert(Stmt.isBlockStmt() && "TODO: Only block statements can be copied by " |
| 987 | "the vector block generator"); |
| 988 | |
Johannes Doerfert | be9c911 | 2015-02-06 21:39:31 +0000 | [diff] [blame] | 989 | BasicBlock *BB = Stmt.getBasicBlock(); |
Duncan P. N. Exon Smith | b8f58b5 | 2015-11-06 22:56:54 +0000 | [diff] [blame] | 990 | BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(), |
| 991 | &*Builder.GetInsertPoint(), &DT, &LI); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 992 | CopyBB->setName("polly.stmt." + BB->getName()); |
Duncan P. N. Exon Smith | b8f58b5 | 2015-11-06 22:56:54 +0000 | [diff] [blame] | 993 | Builder.SetInsertPoint(&CopyBB->front()); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 994 | |
| 995 | // Create two maps that store the mapping from the original instructions of |
| 996 | // the old basic block to their copies in the new basic block. Those maps |
| 997 | // are basic block local. |
| 998 | // |
| 999 | // As vector code generation is supported there is one map for scalar values |
| 1000 | // and one for vector values. |
| 1001 | // |
| 1002 | // In case we just do scalar code generation, the vectorMap is not used and |
| 1003 | // the scalarMap has just one dimension, which contains the mapping. |
| 1004 | // |
| 1005 | // In case vector code generation is done, an instruction may either appear |
| 1006 | // in the vector map once (as it is calculating >vectorwidth< values at a |
| 1007 | // time. Or (if the values are calculated using scalar operations), it |
| 1008 | // appears once in every dimension of the scalarMap. |
| 1009 | VectorValueMapT ScalarBlockMap(getVectorWidth()); |
| 1010 | ValueMapT VectorBlockMap; |
| 1011 | |
Tobias Grosser | a69d4f0 | 2015-12-15 23:49:58 +0000 | [diff] [blame] | 1012 | generateScalarVectorLoads(Stmt, VectorBlockMap); |
| 1013 | |
Tobias Grosser | 91f5b26 | 2014-06-04 08:06:40 +0000 | [diff] [blame] | 1014 | for (Instruction &Inst : *BB) |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 1015 | copyInstruction(Stmt, &Inst, VectorBlockMap, ScalarBlockMap, NewAccesses); |
Tobias Grosser | a69d4f0 | 2015-12-15 23:49:58 +0000 | [diff] [blame] | 1016 | |
| 1017 | verifyNoScalarStores(Stmt); |
Hongbin Zheng | 3b11a16 | 2012-04-25 13:16:49 +0000 | [diff] [blame] | 1018 | } |
Johannes Doerfert | 275a175 | 2015-02-24 16:16:32 +0000 | [diff] [blame] | 1019 | |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1020 | BasicBlock *RegionGenerator::repairDominance(BasicBlock *BB, |
| 1021 | BasicBlock *BBCopy) { |
Johannes Doerfert | 514f6ef | 2015-02-27 18:29:04 +0000 | [diff] [blame] | 1022 | |
| 1023 | BasicBlock *BBIDom = DT.getNode(BB)->getIDom()->getBlock(); |
| 1024 | BasicBlock *BBCopyIDom = BlockMap.lookup(BBIDom); |
| 1025 | |
| 1026 | if (BBCopyIDom) |
| 1027 | DT.changeImmediateDominator(BBCopy, BBCopyIDom); |
| 1028 | |
| 1029 | return BBCopyIDom; |
| 1030 | } |
| 1031 | |
Michael Kruse | f33c125 | 2016-02-25 14:08:48 +0000 | [diff] [blame] | 1032 | // This is to determine whether an llvm::Value (defined in @p BB) is usable when |
| 1033 | // leaving a subregion. The straight-forward DT.dominates(BB, R->getExitBlock()) |
| 1034 | // does not work in cases where the exit block has edges from outside the |
| 1035 | // region. In that case the llvm::Value would never be usable in in the exit |
| 1036 | // block. The RegionGenerator however creates an new exit block ('ExitBBCopy') |
| 1037 | // for the subregion's exiting edges only. We need to determine whether an |
| 1038 | // llvm::Value is usable in there. We do this by checking whether it dominates |
| 1039 | // all exiting blocks individually. |
| 1040 | static bool isDominatingSubregionExit(const DominatorTree &DT, Region *R, |
| 1041 | BasicBlock *BB) { |
| 1042 | for (auto ExitingBB : predecessors(R->getExit())) { |
| 1043 | // Check for non-subregion incoming edges. |
| 1044 | if (!R->contains(ExitingBB)) |
| 1045 | continue; |
| 1046 | |
| 1047 | if (!DT.dominates(BB, ExitingBB)) |
| 1048 | return false; |
| 1049 | } |
| 1050 | |
| 1051 | return true; |
| 1052 | } |
| 1053 | |
| 1054 | // Find the direct dominator of the subregion's exit block if the subregion was |
| 1055 | // simplified. |
| 1056 | static BasicBlock *findExitDominator(DominatorTree &DT, Region *R) { |
| 1057 | BasicBlock *Common = nullptr; |
| 1058 | for (auto ExitingBB : predecessors(R->getExit())) { |
| 1059 | // Check for non-subregion incoming edges. |
| 1060 | if (!R->contains(ExitingBB)) |
| 1061 | continue; |
| 1062 | |
| 1063 | // First exiting edge. |
| 1064 | if (!Common) { |
| 1065 | Common = ExitingBB; |
| 1066 | continue; |
| 1067 | } |
| 1068 | |
| 1069 | Common = DT.findNearestCommonDominator(Common, ExitingBB); |
| 1070 | } |
| 1071 | |
| 1072 | assert(Common && R->contains(Common)); |
| 1073 | return Common; |
| 1074 | } |
| 1075 | |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 1076 | void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT <S, |
Tobias Grosser | 2d1ed0b | 2015-08-27 07:28:16 +0000 | [diff] [blame] | 1077 | isl_id_to_ast_expr *IdToAstExp) { |
Johannes Doerfert | 275a175 | 2015-02-24 16:16:32 +0000 | [diff] [blame] | 1078 | assert(Stmt.isRegionStmt() && |
Tobias Grosser | d3f2183 | 2015-08-01 06:26:51 +0000 | [diff] [blame] | 1079 | "Only region statements can be copied by the region generator"); |
Johannes Doerfert | 275a175 | 2015-02-24 16:16:32 +0000 | [diff] [blame] | 1080 | |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1081 | // Forget all old mappings. |
| 1082 | BlockMap.clear(); |
| 1083 | RegionMaps.clear(); |
| 1084 | IncompletePHINodeMap.clear(); |
| 1085 | |
Michael Kruse | 225f0d1 | 2015-10-17 21:36:00 +0000 | [diff] [blame] | 1086 | // Collection of all values related to this subregion. |
| 1087 | ValueMapT ValueMap; |
| 1088 | |
Johannes Doerfert | 275a175 | 2015-02-24 16:16:32 +0000 | [diff] [blame] | 1089 | // The region represented by the statement. |
| 1090 | Region *R = Stmt.getRegion(); |
| 1091 | |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1092 | // Create a dedicated entry for the region where we can reload all demoted |
| 1093 | // inputs. |
| 1094 | BasicBlock *EntryBB = R->getEntry(); |
Duncan P. N. Exon Smith | b8f58b5 | 2015-11-06 22:56:54 +0000 | [diff] [blame] | 1095 | BasicBlock *EntryBBCopy = SplitBlock(Builder.GetInsertBlock(), |
| 1096 | &*Builder.GetInsertPoint(), &DT, &LI); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1097 | EntryBBCopy->setName("polly.stmt." + EntryBB->getName() + ".entry"); |
Duncan P. N. Exon Smith | b8f58b5 | 2015-11-06 22:56:54 +0000 | [diff] [blame] | 1098 | Builder.SetInsertPoint(&EntryBBCopy->front()); |
Johannes Doerfert | 514f6ef | 2015-02-27 18:29:04 +0000 | [diff] [blame] | 1099 | |
Michael Kruse | c993739 | 2015-11-09 23:33:40 +0000 | [diff] [blame] | 1100 | ValueMapT &EntryBBMap = RegionMaps[EntryBBCopy]; |
| 1101 | generateScalarLoads(Stmt, EntryBBMap); |
Michael Kruse | 225f0d1 | 2015-10-17 21:36:00 +0000 | [diff] [blame] | 1102 | |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1103 | for (auto PI = pred_begin(EntryBB), PE = pred_end(EntryBB); PI != PE; ++PI) |
| 1104 | if (!R->contains(*PI)) |
| 1105 | BlockMap[*PI] = EntryBBCopy; |
Johannes Doerfert | 275a175 | 2015-02-24 16:16:32 +0000 | [diff] [blame] | 1106 | |
| 1107 | // Iterate over all blocks in the region in a breadth-first search. |
| 1108 | std::deque<BasicBlock *> Blocks; |
| 1109 | SmallPtrSet<BasicBlock *, 8> SeenBlocks; |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1110 | Blocks.push_back(EntryBB); |
| 1111 | SeenBlocks.insert(EntryBB); |
Johannes Doerfert | 275a175 | 2015-02-24 16:16:32 +0000 | [diff] [blame] | 1112 | |
| 1113 | while (!Blocks.empty()) { |
| 1114 | BasicBlock *BB = Blocks.front(); |
| 1115 | Blocks.pop_front(); |
| 1116 | |
Johannes Doerfert | 514f6ef | 2015-02-27 18:29:04 +0000 | [diff] [blame] | 1117 | // First split the block and update dominance information. |
| 1118 | BasicBlock *BBCopy = splitBB(BB); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1119 | BasicBlock *BBCopyIDom = repairDominance(BB, BBCopy); |
| 1120 | |
Michael Kruse | c993739 | 2015-11-09 23:33:40 +0000 | [diff] [blame] | 1121 | // Get the mapping for this block and initialize it with either the scalar |
| 1122 | // loads from the generated entering block (which dominates all blocks of |
| 1123 | // this subregion) or the maps of the immediate dominator, if part of the |
| 1124 | // subregion. The latter necessarily includes the former. |
| 1125 | ValueMapT *InitBBMap; |
| 1126 | if (BBCopyIDom) { |
| 1127 | assert(RegionMaps.count(BBCopyIDom)); |
| 1128 | InitBBMap = &RegionMaps[BBCopyIDom]; |
| 1129 | } else |
| 1130 | InitBBMap = &EntryBBMap; |
| 1131 | auto Inserted = RegionMaps.insert(std::make_pair(BBCopy, *InitBBMap)); |
| 1132 | ValueMapT &RegionMap = Inserted.first->second; |
Johannes Doerfert | 514f6ef | 2015-02-27 18:29:04 +0000 | [diff] [blame] | 1133 | |
Johannes Doerfert | 275a175 | 2015-02-24 16:16:32 +0000 | [diff] [blame] | 1134 | // Copy the block with the BlockGenerator. |
Duncan P. N. Exon Smith | b8f58b5 | 2015-11-06 22:56:54 +0000 | [diff] [blame] | 1135 | Builder.SetInsertPoint(&BBCopy->front()); |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 1136 | copyBB(Stmt, BB, BBCopy, RegionMap, LTS, IdToAstExp); |
Johannes Doerfert | 275a175 | 2015-02-24 16:16:32 +0000 | [diff] [blame] | 1137 | |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1138 | // In order to remap PHI nodes we store also basic block mappings. |
| 1139 | BlockMap[BB] = BBCopy; |
| 1140 | |
| 1141 | // Add values to incomplete PHI nodes waiting for this block to be copied. |
| 1142 | for (const PHINodePairTy &PHINodePair : IncompletePHINodeMap[BB]) |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 1143 | addOperandToPHI(Stmt, PHINodePair.first, PHINodePair.second, BB, LTS); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1144 | IncompletePHINodeMap[BB].clear(); |
| 1145 | |
Johannes Doerfert | 275a175 | 2015-02-24 16:16:32 +0000 | [diff] [blame] | 1146 | // And continue with new successors inside the region. |
| 1147 | for (auto SI = succ_begin(BB), SE = succ_end(BB); SI != SE; SI++) |
| 1148 | if (R->contains(*SI) && SeenBlocks.insert(*SI).second) |
| 1149 | Blocks.push_back(*SI); |
Michael Kruse | ebffcbe | 2015-11-09 22:37:29 +0000 | [diff] [blame] | 1150 | |
| 1151 | // Remember value in case it is visible after this subregion. |
Michael Kruse | f33c125 | 2016-02-25 14:08:48 +0000 | [diff] [blame] | 1152 | if (isDominatingSubregionExit(DT, R, BB)) |
Michael Kruse | ebffcbe | 2015-11-09 22:37:29 +0000 | [diff] [blame] | 1153 | ValueMap.insert(RegionMap.begin(), RegionMap.end()); |
Johannes Doerfert | 275a175 | 2015-02-24 16:16:32 +0000 | [diff] [blame] | 1154 | } |
| 1155 | |
| 1156 | // Now create a new dedicated region exit block and add it to the region map. |
Duncan P. N. Exon Smith | b8f58b5 | 2015-11-06 22:56:54 +0000 | [diff] [blame] | 1157 | BasicBlock *ExitBBCopy = SplitBlock(Builder.GetInsertBlock(), |
| 1158 | &*Builder.GetInsertPoint(), &DT, &LI); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1159 | ExitBBCopy->setName("polly.stmt." + R->getExit()->getName() + ".exit"); |
Johannes Doerfert | 514f6ef | 2015-02-27 18:29:04 +0000 | [diff] [blame] | 1160 | BlockMap[R->getExit()] = ExitBBCopy; |
| 1161 | |
Michael Kruse | f33c125 | 2016-02-25 14:08:48 +0000 | [diff] [blame] | 1162 | BasicBlock *ExitDomBBCopy = BlockMap.lookup(findExitDominator(DT, R)); |
| 1163 | assert(ExitDomBBCopy && "Common exit dominator must be within region; at " |
| 1164 | "least the entry node must match"); |
| 1165 | DT.changeImmediateDominator(ExitBBCopy, ExitDomBBCopy); |
Johannes Doerfert | 275a175 | 2015-02-24 16:16:32 +0000 | [diff] [blame] | 1166 | |
| 1167 | // As the block generator doesn't handle control flow we need to add the |
| 1168 | // region control flow by hand after all blocks have been copied. |
| 1169 | for (BasicBlock *BB : SeenBlocks) { |
| 1170 | |
Johannes Doerfert | 514f6ef | 2015-02-27 18:29:04 +0000 | [diff] [blame] | 1171 | BasicBlock *BBCopy = BlockMap[BB]; |
Johannes Doerfert | e114dc0 | 2015-09-14 11:15:58 +0000 | [diff] [blame] | 1172 | TerminatorInst *TI = BB->getTerminator(); |
| 1173 | if (isa<UnreachableInst>(TI)) { |
| 1174 | while (!BBCopy->empty()) |
| 1175 | BBCopy->begin()->eraseFromParent(); |
| 1176 | new UnreachableInst(BBCopy->getContext(), BBCopy); |
| 1177 | continue; |
| 1178 | } |
| 1179 | |
Johannes Doerfert | 275a175 | 2015-02-24 16:16:32 +0000 | [diff] [blame] | 1180 | Instruction *BICopy = BBCopy->getTerminator(); |
| 1181 | |
Johannes Doerfert | 514f6ef | 2015-02-27 18:29:04 +0000 | [diff] [blame] | 1182 | ValueMapT &RegionMap = RegionMaps[BBCopy]; |
| 1183 | RegionMap.insert(BlockMap.begin(), BlockMap.end()); |
| 1184 | |
Tobias Grosser | 45e7944 | 2015-08-01 09:07:57 +0000 | [diff] [blame] | 1185 | Builder.SetInsertPoint(BICopy); |
Johannes Doerfert | 9a132f3 | 2015-09-28 09:33:22 +0000 | [diff] [blame] | 1186 | copyInstScalar(Stmt, TI, RegionMap, LTS); |
Johannes Doerfert | 275a175 | 2015-02-24 16:16:32 +0000 | [diff] [blame] | 1187 | BICopy->eraseFromParent(); |
| 1188 | } |
| 1189 | |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1190 | // Add counting PHI nodes to all loops in the region that can be used as |
| 1191 | // replacement for SCEVs refering to the old loop. |
| 1192 | for (BasicBlock *BB : SeenBlocks) { |
| 1193 | Loop *L = LI.getLoopFor(BB); |
Tobias Grosser | bc29e0b | 2015-11-12 07:34:09 +0000 | [diff] [blame] | 1194 | if (L == nullptr || L->getHeader() != BB || !R->contains(L)) |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1195 | continue; |
| 1196 | |
| 1197 | BasicBlock *BBCopy = BlockMap[BB]; |
| 1198 | Value *NullVal = Builder.getInt32(0); |
| 1199 | PHINode *LoopPHI = |
| 1200 | PHINode::Create(Builder.getInt32Ty(), 2, "polly.subregion.iv"); |
| 1201 | Instruction *LoopPHIInc = BinaryOperator::CreateAdd( |
| 1202 | LoopPHI, Builder.getInt32(1), "polly.subregion.iv.inc"); |
Duncan P. N. Exon Smith | b8f58b5 | 2015-11-06 22:56:54 +0000 | [diff] [blame] | 1203 | LoopPHI->insertBefore(&BBCopy->front()); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1204 | LoopPHIInc->insertBefore(BBCopy->getTerminator()); |
| 1205 | |
| 1206 | for (auto *PredBB : make_range(pred_begin(BB), pred_end(BB))) { |
| 1207 | if (!R->contains(PredBB)) |
| 1208 | continue; |
| 1209 | if (L->contains(PredBB)) |
| 1210 | LoopPHI->addIncoming(LoopPHIInc, BlockMap[PredBB]); |
| 1211 | else |
| 1212 | LoopPHI->addIncoming(NullVal, BlockMap[PredBB]); |
| 1213 | } |
| 1214 | |
| 1215 | for (auto *PredBBCopy : make_range(pred_begin(BBCopy), pred_end(BBCopy))) |
| 1216 | if (LoopPHI->getBasicBlockIndex(PredBBCopy) < 0) |
| 1217 | LoopPHI->addIncoming(NullVal, PredBBCopy); |
| 1218 | |
| 1219 | LTS[L] = SE.getUnknown(LoopPHI); |
| 1220 | } |
| 1221 | |
Michael Kruse | 225f0d1 | 2015-10-17 21:36:00 +0000 | [diff] [blame] | 1222 | // Continue generating code in the exit block. |
Duncan P. N. Exon Smith | b8f58b5 | 2015-11-06 22:56:54 +0000 | [diff] [blame] | 1223 | Builder.SetInsertPoint(&*ExitBBCopy->getFirstInsertionPt()); |
Michael Kruse | 225f0d1 | 2015-10-17 21:36:00 +0000 | [diff] [blame] | 1224 | |
| 1225 | // Write values visible to other statements. |
| 1226 | generateScalarStores(Stmt, LTS, ValueMap); |
Tobias Grosser | 3e95602 | 2015-10-26 20:41:53 +0000 | [diff] [blame] | 1227 | BlockMap.clear(); |
| 1228 | RegionMaps.clear(); |
| 1229 | IncompletePHINodeMap.clear(); |
Johannes Doerfert | 275a175 | 2015-02-24 16:16:32 +0000 | [diff] [blame] | 1230 | } |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1231 | |
Michael Kruse | ee6a4fc | 2016-01-26 13:33:27 +0000 | [diff] [blame] | 1232 | PHINode *RegionGenerator::buildExitPHI(MemoryAccess *MA, LoopToScevMapT <S, |
| 1233 | ValueMapT &BBMap, Loop *L) { |
| 1234 | ScopStmt *Stmt = MA->getStatement(); |
| 1235 | Region *SubR = Stmt->getRegion(); |
| 1236 | auto Incoming = MA->getIncoming(); |
| 1237 | |
| 1238 | PollyIRBuilder::InsertPointGuard IPGuard(Builder); |
| 1239 | PHINode *OrigPHI = cast<PHINode>(MA->getAccessInstruction()); |
| 1240 | BasicBlock *NewSubregionExit = Builder.GetInsertBlock(); |
| 1241 | |
| 1242 | // This can happen if the subregion is simplified after the ScopStmts |
| 1243 | // have been created; simplification happens as part of CodeGeneration. |
| 1244 | if (OrigPHI->getParent() != SubR->getExit()) { |
| 1245 | BasicBlock *FormerExit = SubR->getExitingBlock(); |
| 1246 | if (FormerExit) |
| 1247 | NewSubregionExit = BlockMap.lookup(FormerExit); |
| 1248 | } |
| 1249 | |
| 1250 | PHINode *NewPHI = PHINode::Create(OrigPHI->getType(), Incoming.size(), |
| 1251 | "polly." + OrigPHI->getName(), |
| 1252 | NewSubregionExit->getFirstNonPHI()); |
| 1253 | |
| 1254 | // Add the incoming values to the PHI. |
| 1255 | for (auto &Pair : Incoming) { |
| 1256 | BasicBlock *OrigIncomingBlock = Pair.first; |
| 1257 | BasicBlock *NewIncomingBlock = BlockMap.lookup(OrigIncomingBlock); |
| 1258 | Builder.SetInsertPoint(NewIncomingBlock->getTerminator()); |
| 1259 | assert(RegionMaps.count(NewIncomingBlock)); |
| 1260 | ValueMapT *LocalBBMap = &RegionMaps[NewIncomingBlock]; |
| 1261 | |
| 1262 | Value *OrigIncomingValue = Pair.second; |
| 1263 | Value *NewIncomingValue = |
| 1264 | getNewValue(*Stmt, OrigIncomingValue, *LocalBBMap, LTS, L); |
| 1265 | NewPHI->addIncoming(NewIncomingValue, NewIncomingBlock); |
| 1266 | } |
| 1267 | |
| 1268 | return NewPHI; |
| 1269 | } |
| 1270 | |
| 1271 | Value *RegionGenerator::getExitScalar(MemoryAccess *MA, LoopToScevMapT <S, |
| 1272 | ValueMapT &BBMap) { |
| 1273 | ScopStmt *Stmt = MA->getStatement(); |
| 1274 | |
| 1275 | // TODO: Add some test cases that ensure this is really the right choice. |
| 1276 | Loop *L = LI.getLoopFor(Stmt->getRegion()->getExit()); |
| 1277 | |
| 1278 | if (MA->isAnyPHIKind()) { |
| 1279 | auto Incoming = MA->getIncoming(); |
| 1280 | assert(!Incoming.empty() && |
| 1281 | "PHI WRITEs must have originate from at least one incoming block"); |
| 1282 | |
| 1283 | // If there is only one incoming value, we do not need to create a PHI. |
| 1284 | if (Incoming.size() == 1) { |
| 1285 | Value *OldVal = Incoming[0].second; |
| 1286 | return getNewValue(*Stmt, OldVal, BBMap, LTS, L); |
| 1287 | } |
| 1288 | |
| 1289 | return buildExitPHI(MA, LTS, BBMap, L); |
| 1290 | } |
| 1291 | |
| 1292 | // MK_Value accesses leaving the subregion must dominate the exit block; just |
| 1293 | // pass the copied value |
| 1294 | Value *OldVal = MA->getAccessValue(); |
| 1295 | return getNewValue(*Stmt, OldVal, BBMap, LTS, L); |
| 1296 | } |
| 1297 | |
Michael Kruse | 225f0d1 | 2015-10-17 21:36:00 +0000 | [diff] [blame] | 1298 | void RegionGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT <S, |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 1299 | ValueMapT &BBMap) { |
Tobias Grosser | 7529690 | 2015-08-21 19:23:21 +0000 | [diff] [blame] | 1300 | assert(Stmt.getRegion() && |
| 1301 | "Block statements need to use the generateScalarStores() " |
| 1302 | "function in the BlockGenerator"); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1303 | |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1304 | for (MemoryAccess *MA : Stmt) { |
Tobias Grosser | a535dff | 2015-12-13 19:59:01 +0000 | [diff] [blame] | 1305 | if (MA->isArrayKind() || MA->isRead()) |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1306 | continue; |
| 1307 | |
Michael Kruse | ee6a4fc | 2016-01-26 13:33:27 +0000 | [diff] [blame] | 1308 | Value *NewVal = getExitScalar(MA, LTS, BBMap); |
| 1309 | Value *Address = getOrCreateAlloca(*MA); |
Michael Kruse | eac9726 | 2016-02-24 22:08:14 +0000 | [diff] [blame] | 1310 | assert((!isa<Instruction>(NewVal) || |
| 1311 | DT.dominates(cast<Instruction>(NewVal)->getParent(), |
| 1312 | Builder.GetInsertBlock())) && |
| 1313 | "Domination violation"); |
| 1314 | assert((!isa<Instruction>(Address) || |
| 1315 | DT.dominates(cast<Instruction>(Address)->getParent(), |
| 1316 | Builder.GetInsertBlock())) && |
| 1317 | "Domination violation"); |
Michael Kruse | ee6a4fc | 2016-01-26 13:33:27 +0000 | [diff] [blame] | 1318 | Builder.CreateStore(NewVal, Address); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1319 | } |
| 1320 | } |
| 1321 | |
| 1322 | void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, const PHINode *PHI, |
| 1323 | PHINode *PHICopy, BasicBlock *IncomingBB, |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1324 | LoopToScevMapT <S) { |
| 1325 | Region *StmtR = Stmt.getRegion(); |
| 1326 | |
| 1327 | // If the incoming block was not yet copied mark this PHI as incomplete. |
| 1328 | // Once the block will be copied the incoming value will be added. |
| 1329 | BasicBlock *BBCopy = BlockMap[IncomingBB]; |
| 1330 | if (!BBCopy) { |
| 1331 | assert(StmtR->contains(IncomingBB) && |
| 1332 | "Bad incoming block for PHI in non-affine region"); |
| 1333 | IncompletePHINodeMap[IncomingBB].push_back(std::make_pair(PHI, PHICopy)); |
| 1334 | return; |
| 1335 | } |
| 1336 | |
| 1337 | Value *OpCopy = nullptr; |
| 1338 | if (StmtR->contains(IncomingBB)) { |
| 1339 | assert(RegionMaps.count(BBCopy) && |
| 1340 | "Incoming PHI block did not have a BBMap"); |
| 1341 | ValueMapT &BBCopyMap = RegionMaps[BBCopy]; |
| 1342 | |
| 1343 | Value *Op = PHI->getIncomingValueForBlock(IncomingBB); |
Michael Kruse | dc12222 | 2015-10-19 09:19:25 +0000 | [diff] [blame] | 1344 | |
Johannes Doerfert | 6ba9271 | 2016-04-01 11:25:47 +0000 | [diff] [blame] | 1345 | // If the current insert block is different from the PHIs incoming block |
| 1346 | // change it, otherwise do not. |
| 1347 | auto IP = Builder.GetInsertPoint(); |
| 1348 | if (IP->getParent() != BBCopy) |
| 1349 | Builder.SetInsertPoint(BBCopy->getTerminator()); |
Johannes Doerfert | 2c3ffc0 | 2016-02-16 12:36:14 +0000 | [diff] [blame] | 1350 | OpCopy = getNewValue(Stmt, Op, BBCopyMap, LTS, getLoopForStmt(Stmt)); |
Johannes Doerfert | 6ba9271 | 2016-04-01 11:25:47 +0000 | [diff] [blame] | 1351 | if (IP->getParent() != BBCopy) |
| 1352 | Builder.SetInsertPoint(&*IP); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1353 | } else { |
| 1354 | |
| 1355 | if (PHICopy->getBasicBlockIndex(BBCopy) >= 0) |
| 1356 | return; |
| 1357 | |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 1358 | Value *PHIOpAddr = getOrCreatePHIAlloca(const_cast<PHINode *>(PHI)); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1359 | OpCopy = new LoadInst(PHIOpAddr, PHIOpAddr->getName() + ".reload", |
| 1360 | BlockMap[IncomingBB]->getTerminator()); |
| 1361 | } |
| 1362 | |
| 1363 | assert(OpCopy && "Incoming PHI value was not copied properly"); |
| 1364 | assert(BBCopy && "Incoming PHI block was not copied properly"); |
| 1365 | PHICopy->addIncoming(OpCopy, BBCopy); |
| 1366 | } |
| 1367 | |
Tobias Grosser | 2b809d1 | 2016-02-21 15:44:34 +0000 | [diff] [blame] | 1368 | void RegionGenerator::copyPHIInstruction(ScopStmt &Stmt, PHINode *PHI, |
| 1369 | ValueMapT &BBMap, |
| 1370 | LoopToScevMapT <S) { |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1371 | unsigned NumIncoming = PHI->getNumIncomingValues(); |
| 1372 | PHINode *PHICopy = |
| 1373 | Builder.CreatePHI(PHI->getType(), NumIncoming, "polly." + PHI->getName()); |
| 1374 | PHICopy->moveBefore(PHICopy->getParent()->getFirstNonPHI()); |
| 1375 | BBMap[PHI] = PHICopy; |
| 1376 | |
| 1377 | for (unsigned u = 0; u < NumIncoming; u++) |
Tobias Grosser | bc13260 | 2015-09-05 09:56:54 +0000 | [diff] [blame] | 1378 | addOperandToPHI(Stmt, PHI, PHICopy, PHI->getIncomingBlock(u), LTS); |
Johannes Doerfert | ecff11d | 2015-05-22 23:43:58 +0000 | [diff] [blame] | 1379 | } |