File: | lib/Transforms/Vectorize/VPlan.cpp |
Warning: | line 297, column 15 Value stored to 'VectorLatchBB' during its initialization is never read |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- VPlan.cpp - Vectorizer Plan ----------------------------------------===// |
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 | /// \file |
11 | /// This is the LLVM vectorization plan. It represents a candidate for |
12 | /// vectorization, allowing to plan and optimize how to vectorize a given loop |
13 | /// before generating LLVM-IR. |
14 | /// The vectorizer uses vectorization plans to estimate the costs of potential |
15 | /// candidates and if profitable to execute the desired plan, generating vector |
16 | /// LLVM-IR code. |
17 | /// |
18 | //===----------------------------------------------------------------------===// |
19 | |
20 | #include "VPlan.h" |
21 | #include "llvm/ADT/DepthFirstIterator.h" |
22 | #include "llvm/ADT/PostOrderIterator.h" |
23 | #include "llvm/ADT/SmallVector.h" |
24 | #include "llvm/ADT/Twine.h" |
25 | #include "llvm/Analysis/LoopInfo.h" |
26 | #include "llvm/IR/BasicBlock.h" |
27 | #include "llvm/IR/CFG.h" |
28 | #include "llvm/IR/Dominators.h" |
29 | #include "llvm/IR/InstrTypes.h" |
30 | #include "llvm/IR/Instruction.h" |
31 | #include "llvm/IR/Instructions.h" |
32 | #include "llvm/IR/Type.h" |
33 | #include "llvm/IR/Value.h" |
34 | #include "llvm/Support/Casting.h" |
35 | #include "llvm/Support/Debug.h" |
36 | #include "llvm/Support/ErrorHandling.h" |
37 | #include "llvm/Support/GraphWriter.h" |
38 | #include "llvm/Support/raw_ostream.h" |
39 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
40 | #include <cassert> |
41 | #include <iterator> |
42 | #include <string> |
43 | #include <vector> |
44 | |
45 | using namespace llvm; |
46 | |
47 | #define DEBUG_TYPE"vplan" "vplan" |
48 | |
49 | raw_ostream &llvm::operator<<(raw_ostream &OS, const VPValue &V) { |
50 | if (const VPInstruction *Instr = dyn_cast<VPInstruction>(&V)) |
51 | Instr->print(OS); |
52 | else |
53 | V.printAsOperand(OS); |
54 | return OS; |
55 | } |
56 | |
57 | /// \return the VPBasicBlock that is the entry of Block, possibly indirectly. |
58 | const VPBasicBlock *VPBlockBase::getEntryBasicBlock() const { |
59 | const VPBlockBase *Block = this; |
60 | while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block)) |
61 | Block = Region->getEntry(); |
62 | return cast<VPBasicBlock>(Block); |
63 | } |
64 | |
65 | VPBasicBlock *VPBlockBase::getEntryBasicBlock() { |
66 | VPBlockBase *Block = this; |
67 | while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block)) |
68 | Block = Region->getEntry(); |
69 | return cast<VPBasicBlock>(Block); |
70 | } |
71 | |
72 | /// \return the VPBasicBlock that is the exit of Block, possibly indirectly. |
73 | const VPBasicBlock *VPBlockBase::getExitBasicBlock() const { |
74 | const VPBlockBase *Block = this; |
75 | while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block)) |
76 | Block = Region->getExit(); |
77 | return cast<VPBasicBlock>(Block); |
78 | } |
79 | |
80 | VPBasicBlock *VPBlockBase::getExitBasicBlock() { |
81 | VPBlockBase *Block = this; |
82 | while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block)) |
83 | Block = Region->getExit(); |
84 | return cast<VPBasicBlock>(Block); |
85 | } |
86 | |
87 | VPBlockBase *VPBlockBase::getEnclosingBlockWithSuccessors() { |
88 | if (!Successors.empty() || !Parent) |
89 | return this; |
90 | assert(Parent->getExit() == this &&(static_cast <bool> (Parent->getExit() == this && "Block w/o successors not the exit of its parent.") ? void ( 0) : __assert_fail ("Parent->getExit() == this && \"Block w/o successors not the exit of its parent.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 91, __extension__ __PRETTY_FUNCTION__)) |
91 | "Block w/o successors not the exit of its parent.")(static_cast <bool> (Parent->getExit() == this && "Block w/o successors not the exit of its parent.") ? void ( 0) : __assert_fail ("Parent->getExit() == this && \"Block w/o successors not the exit of its parent.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 91, __extension__ __PRETTY_FUNCTION__)); |
92 | return Parent->getEnclosingBlockWithSuccessors(); |
93 | } |
94 | |
95 | VPBlockBase *VPBlockBase::getEnclosingBlockWithPredecessors() { |
96 | if (!Predecessors.empty() || !Parent) |
97 | return this; |
98 | assert(Parent->getEntry() == this &&(static_cast <bool> (Parent->getEntry() == this && "Block w/o predecessors not the entry of its parent.") ? void (0) : __assert_fail ("Parent->getEntry() == this && \"Block w/o predecessors not the entry of its parent.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 99, __extension__ __PRETTY_FUNCTION__)) |
99 | "Block w/o predecessors not the entry of its parent.")(static_cast <bool> (Parent->getEntry() == this && "Block w/o predecessors not the entry of its parent.") ? void (0) : __assert_fail ("Parent->getEntry() == this && \"Block w/o predecessors not the entry of its parent.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 99, __extension__ __PRETTY_FUNCTION__)); |
100 | return Parent->getEnclosingBlockWithPredecessors(); |
101 | } |
102 | |
103 | void VPBlockBase::deleteCFG(VPBlockBase *Entry) { |
104 | SmallVector<VPBlockBase *, 8> Blocks; |
105 | for (VPBlockBase *Block : depth_first(Entry)) |
106 | Blocks.push_back(Block); |
107 | |
108 | for (VPBlockBase *Block : Blocks) |
109 | delete Block; |
110 | } |
111 | |
112 | BasicBlock * |
113 | VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) { |
114 | // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks. |
115 | // Pred stands for Predessor. Prev stands for Previous - last visited/created. |
116 | BasicBlock *PrevBB = CFG.PrevBB; |
117 | BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(), |
118 | PrevBB->getParent(), CFG.LastBB); |
119 | LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("vplan")) { dbgs() << "LV: created " << NewBB-> getName() << '\n'; } } while (false); |
120 | |
121 | // Hook up the new basic block to its predecessors. |
122 | for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) { |
123 | VPBasicBlock *PredVPBB = PredVPBlock->getExitBasicBlock(); |
124 | auto &PredVPSuccessors = PredVPBB->getSuccessors(); |
125 | BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB]; |
126 | assert(PredBB && "Predecessor basic-block not found building successor.")(static_cast <bool> (PredBB && "Predecessor basic-block not found building successor." ) ? void (0) : __assert_fail ("PredBB && \"Predecessor basic-block not found building successor.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 126, __extension__ __PRETTY_FUNCTION__)); |
127 | auto *PredBBTerminator = PredBB->getTerminator(); |
128 | LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("vplan")) { dbgs() << "LV: draw edge from" << PredBB ->getName() << '\n'; } } while (false); |
129 | if (isa<UnreachableInst>(PredBBTerminator)) { |
130 | assert(PredVPSuccessors.size() == 1 &&(static_cast <bool> (PredVPSuccessors.size() == 1 && "Predecessor ending w/o branch must have single successor.") ? void (0) : __assert_fail ("PredVPSuccessors.size() == 1 && \"Predecessor ending w/o branch must have single successor.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 131, __extension__ __PRETTY_FUNCTION__)) |
131 | "Predecessor ending w/o branch must have single successor.")(static_cast <bool> (PredVPSuccessors.size() == 1 && "Predecessor ending w/o branch must have single successor.") ? void (0) : __assert_fail ("PredVPSuccessors.size() == 1 && \"Predecessor ending w/o branch must have single successor.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 131, __extension__ __PRETTY_FUNCTION__)); |
132 | PredBBTerminator->eraseFromParent(); |
133 | BranchInst::Create(NewBB, PredBB); |
134 | } else { |
135 | assert(PredVPSuccessors.size() == 2 &&(static_cast <bool> (PredVPSuccessors.size() == 2 && "Predecessor ending with branch must have two successors.") ? void (0) : __assert_fail ("PredVPSuccessors.size() == 2 && \"Predecessor ending with branch must have two successors.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 136, __extension__ __PRETTY_FUNCTION__)) |
136 | "Predecessor ending with branch must have two successors.")(static_cast <bool> (PredVPSuccessors.size() == 2 && "Predecessor ending with branch must have two successors.") ? void (0) : __assert_fail ("PredVPSuccessors.size() == 2 && \"Predecessor ending with branch must have two successors.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 136, __extension__ __PRETTY_FUNCTION__)); |
137 | unsigned idx = PredVPSuccessors.front() == this ? 0 : 1; |
138 | assert(!PredBBTerminator->getSuccessor(idx) &&(static_cast <bool> (!PredBBTerminator->getSuccessor (idx) && "Trying to reset an existing successor block." ) ? void (0) : __assert_fail ("!PredBBTerminator->getSuccessor(idx) && \"Trying to reset an existing successor block.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 139, __extension__ __PRETTY_FUNCTION__)) |
139 | "Trying to reset an existing successor block.")(static_cast <bool> (!PredBBTerminator->getSuccessor (idx) && "Trying to reset an existing successor block." ) ? void (0) : __assert_fail ("!PredBBTerminator->getSuccessor(idx) && \"Trying to reset an existing successor block.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 139, __extension__ __PRETTY_FUNCTION__)); |
140 | PredBBTerminator->setSuccessor(idx, NewBB); |
141 | } |
142 | } |
143 | return NewBB; |
144 | } |
145 | |
146 | void VPBasicBlock::execute(VPTransformState *State) { |
147 | bool Replica = State->Instance && |
148 | !(State->Instance->Part == 0 && State->Instance->Lane == 0); |
149 | VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB; |
150 | VPBlockBase *SingleHPred = nullptr; |
151 | BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible. |
152 | |
153 | // 1. Create an IR basic block, or reuse the last one if possible. |
154 | // The last IR basic block is reused, as an optimization, in three cases: |
155 | // A. the first VPBB reuses the loop header BB - when PrevVPBB is null; |
156 | // B. when the current VPBB has a single (hierarchical) predecessor which |
157 | // is PrevVPBB and the latter has a single (hierarchical) successor; and |
158 | // C. when the current VPBB is an entry of a region replica - where PrevVPBB |
159 | // is the exit of this region from a previous instance, or the predecessor |
160 | // of this region. |
161 | if (PrevVPBB && /* A */ |
162 | !((SingleHPred = getSingleHierarchicalPredecessor()) && |
163 | SingleHPred->getExitBasicBlock() == PrevVPBB && |
164 | PrevVPBB->getSingleHierarchicalSuccessor()) && /* B */ |
165 | !(Replica && getPredecessors().empty())) { /* C */ |
166 | NewBB = createEmptyBasicBlock(State->CFG); |
167 | State->Builder.SetInsertPoint(NewBB); |
168 | // Temporarily terminate with unreachable until CFG is rewired. |
169 | UnreachableInst *Terminator = State->Builder.CreateUnreachable(); |
170 | State->Builder.SetInsertPoint(Terminator); |
171 | // Register NewBB in its loop. In innermost loops its the same for all BB's. |
172 | Loop *L = State->LI->getLoopFor(State->CFG.LastBB); |
173 | L->addBasicBlockToLoop(NewBB, *State->LI); |
174 | State->CFG.PrevBB = NewBB; |
175 | } |
176 | |
177 | // 2. Fill the IR basic block with IR instructions. |
178 | LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB:" << getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("vplan")) { dbgs() << "LV: vectorizing VPBB:" << getName() << " in BB:" << NewBB->getName() << '\n'; } } while (false) |
179 | << " in BB:" << NewBB->getName() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("vplan")) { dbgs() << "LV: vectorizing VPBB:" << getName() << " in BB:" << NewBB->getName() << '\n'; } } while (false); |
180 | |
181 | State->CFG.VPBB2IRBB[this] = NewBB; |
182 | State->CFG.PrevVPBB = this; |
183 | |
184 | for (VPRecipeBase &Recipe : Recipes) |
185 | Recipe.execute(*State); |
186 | |
187 | LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("vplan")) { dbgs() << "LV: filled BB:" << *NewBB ; } } while (false); |
188 | } |
189 | |
190 | void VPRegionBlock::execute(VPTransformState *State) { |
191 | ReversePostOrderTraversal<VPBlockBase *> RPOT(Entry); |
192 | |
193 | if (!isReplicator()) { |
194 | // Visit the VPBlocks connected to "this", starting from it. |
195 | for (VPBlockBase *Block : RPOT) { |
196 | LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("vplan")) { dbgs() << "LV: VPBlock in RPO " << Block ->getName() << '\n'; } } while (false); |
197 | Block->execute(State); |
198 | } |
199 | return; |
200 | } |
201 | |
202 | assert(!State->Instance && "Replicating a Region with non-null instance.")(static_cast <bool> (!State->Instance && "Replicating a Region with non-null instance." ) ? void (0) : __assert_fail ("!State->Instance && \"Replicating a Region with non-null instance.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 202, __extension__ __PRETTY_FUNCTION__)); |
203 | |
204 | // Enter replicating mode. |
205 | State->Instance = {0, 0}; |
206 | |
207 | for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part) { |
208 | State->Instance->Part = Part; |
209 | for (unsigned Lane = 0, VF = State->VF; Lane < VF; ++Lane) { |
210 | State->Instance->Lane = Lane; |
211 | // Visit the VPBlocks connected to \p this, starting from it. |
212 | for (VPBlockBase *Block : RPOT) { |
213 | LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("vplan")) { dbgs() << "LV: VPBlock in RPO " << Block ->getName() << '\n'; } } while (false); |
214 | Block->execute(State); |
215 | } |
216 | } |
217 | } |
218 | |
219 | // Exit replicating mode. |
220 | State->Instance.reset(); |
221 | } |
222 | |
223 | void VPRecipeBase::insertBefore(VPRecipeBase *InsertPos) { |
224 | Parent = InsertPos->getParent(); |
225 | Parent->getRecipeList().insert(InsertPos->getIterator(), this); |
226 | } |
227 | |
228 | iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() { |
229 | return getParent()->getRecipeList().erase(getIterator()); |
230 | } |
231 | |
232 | void VPInstruction::generateInstruction(VPTransformState &State, |
233 | unsigned Part) { |
234 | IRBuilder<> &Builder = State.Builder; |
235 | |
236 | if (Instruction::isBinaryOp(getOpcode())) { |
237 | Value *A = State.get(getOperand(0), Part); |
238 | Value *B = State.get(getOperand(1), Part); |
239 | Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B); |
240 | State.set(this, V, Part); |
241 | return; |
242 | } |
243 | |
244 | switch (getOpcode()) { |
245 | case VPInstruction::Not: { |
246 | Value *A = State.get(getOperand(0), Part); |
247 | Value *V = Builder.CreateNot(A); |
248 | State.set(this, V, Part); |
249 | break; |
250 | } |
251 | default: |
252 | llvm_unreachable("Unsupported opcode for instruction")::llvm::llvm_unreachable_internal("Unsupported opcode for instruction" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 252); |
253 | } |
254 | } |
255 | |
256 | void VPInstruction::execute(VPTransformState &State) { |
257 | assert(!State.Instance && "VPInstruction executing an Instance")(static_cast <bool> (!State.Instance && "VPInstruction executing an Instance" ) ? void (0) : __assert_fail ("!State.Instance && \"VPInstruction executing an Instance\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 257, __extension__ __PRETTY_FUNCTION__)); |
258 | for (unsigned Part = 0; Part < State.UF; ++Part) |
259 | generateInstruction(State, Part); |
260 | } |
261 | |
262 | void VPInstruction::print(raw_ostream &O, const Twine &Indent) const { |
263 | O << " +\n" << Indent << "\"EMIT "; |
264 | print(O); |
265 | O << "\\l\""; |
266 | } |
267 | |
268 | void VPInstruction::print(raw_ostream &O) const { |
269 | printAsOperand(O); |
270 | O << " = "; |
271 | |
272 | switch (getOpcode()) { |
273 | case VPInstruction::Not: |
274 | O << "not"; |
275 | break; |
276 | default: |
277 | O << Instruction::getOpcodeName(getOpcode()); |
278 | } |
279 | |
280 | for (const VPValue *Operand : operands()) { |
281 | O << " "; |
282 | Operand->printAsOperand(O); |
283 | } |
284 | } |
285 | |
286 | /// Generate the code inside the body of the vectorized loop. Assumes a single |
287 | /// LoopVectorBody basic-block was created for this. Introduce additional |
288 | /// basic-blocks as needed, and fill them all. |
289 | void VPlan::execute(VPTransformState *State) { |
290 | // 0. Set the reverse mapping from VPValues to Values for code generation. |
291 | for (auto &Entry : Value2VPValue) |
292 | State->VPValue2Value[Entry.second] = Entry.first; |
293 | |
294 | BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB; |
295 | BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor(); |
296 | assert(VectorHeaderBB && "Loop preheader does not have a single successor.")(static_cast <bool> (VectorHeaderBB && "Loop preheader does not have a single successor." ) ? void (0) : __assert_fail ("VectorHeaderBB && \"Loop preheader does not have a single successor.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 296, __extension__ __PRETTY_FUNCTION__)); |
297 | BasicBlock *VectorLatchBB = VectorHeaderBB; |
Value stored to 'VectorLatchBB' during its initialization is never read | |
298 | |
299 | // 1. Make room to generate basic-blocks inside loop body if needed. |
300 | VectorLatchBB = VectorHeaderBB->splitBasicBlock( |
301 | VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch"); |
302 | Loop *L = State->LI->getLoopFor(VectorHeaderBB); |
303 | L->addBasicBlockToLoop(VectorLatchBB, *State->LI); |
304 | // Remove the edge between Header and Latch to allow other connections. |
305 | // Temporarily terminate with unreachable until CFG is rewired. |
306 | // Note: this asserts the generated code's assumption that |
307 | // getFirstInsertionPt() can be dereferenced into an Instruction. |
308 | VectorHeaderBB->getTerminator()->eraseFromParent(); |
309 | State->Builder.SetInsertPoint(VectorHeaderBB); |
310 | UnreachableInst *Terminator = State->Builder.CreateUnreachable(); |
311 | State->Builder.SetInsertPoint(Terminator); |
312 | |
313 | // 2. Generate code in loop body. |
314 | State->CFG.PrevVPBB = nullptr; |
315 | State->CFG.PrevBB = VectorHeaderBB; |
316 | State->CFG.LastBB = VectorLatchBB; |
317 | |
318 | for (VPBlockBase *Block : depth_first(Entry)) |
319 | Block->execute(State); |
320 | |
321 | // 3. Merge the temporary latch created with the last basic-block filled. |
322 | BasicBlock *LastBB = State->CFG.PrevBB; |
323 | // Connect LastBB to VectorLatchBB to facilitate their merge. |
324 | assert(isa<UnreachableInst>(LastBB->getTerminator()) &&(static_cast <bool> (isa<UnreachableInst>(LastBB-> getTerminator()) && "Expected VPlan CFG to terminate with unreachable" ) ? void (0) : __assert_fail ("isa<UnreachableInst>(LastBB->getTerminator()) && \"Expected VPlan CFG to terminate with unreachable\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 325, __extension__ __PRETTY_FUNCTION__)) |
325 | "Expected VPlan CFG to terminate with unreachable")(static_cast <bool> (isa<UnreachableInst>(LastBB-> getTerminator()) && "Expected VPlan CFG to terminate with unreachable" ) ? void (0) : __assert_fail ("isa<UnreachableInst>(LastBB->getTerminator()) && \"Expected VPlan CFG to terminate with unreachable\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 325, __extension__ __PRETTY_FUNCTION__)); |
326 | LastBB->getTerminator()->eraseFromParent(); |
327 | BranchInst::Create(VectorLatchBB, LastBB); |
328 | |
329 | // Merge LastBB with Latch. |
330 | bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI); |
331 | (void)Merged; |
332 | assert(Merged && "Could not merge last basic block with latch.")(static_cast <bool> (Merged && "Could not merge last basic block with latch." ) ? void (0) : __assert_fail ("Merged && \"Could not merge last basic block with latch.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 332, __extension__ __PRETTY_FUNCTION__)); |
333 | VectorLatchBB = LastBB; |
334 | |
335 | updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB); |
336 | } |
337 | |
338 | void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB, |
339 | BasicBlock *LoopLatchBB) { |
340 | BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor(); |
341 | assert(LoopHeaderBB && "Loop preheader does not have a single successor.")(static_cast <bool> (LoopHeaderBB && "Loop preheader does not have a single successor." ) ? void (0) : __assert_fail ("LoopHeaderBB && \"Loop preheader does not have a single successor.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 341, __extension__ __PRETTY_FUNCTION__)); |
342 | DT->addNewBlock(LoopHeaderBB, LoopPreHeaderBB); |
343 | // The vector body may be more than a single basic-block by this point. |
344 | // Update the dominator tree information inside the vector body by propagating |
345 | // it from header to latch, expecting only triangular control-flow, if any. |
346 | BasicBlock *PostDomSucc = nullptr; |
347 | for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) { |
348 | // Get the list of successors of this block. |
349 | std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB)); |
350 | assert(Succs.size() <= 2 &&(static_cast <bool> (Succs.size() <= 2 && "Basic block in vector loop has more than 2 successors." ) ? void (0) : __assert_fail ("Succs.size() <= 2 && \"Basic block in vector loop has more than 2 successors.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 351, __extension__ __PRETTY_FUNCTION__)) |
351 | "Basic block in vector loop has more than 2 successors.")(static_cast <bool> (Succs.size() <= 2 && "Basic block in vector loop has more than 2 successors." ) ? void (0) : __assert_fail ("Succs.size() <= 2 && \"Basic block in vector loop has more than 2 successors.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 351, __extension__ __PRETTY_FUNCTION__)); |
352 | PostDomSucc = Succs[0]; |
353 | if (Succs.size() == 1) { |
354 | assert(PostDomSucc->getSinglePredecessor() &&(static_cast <bool> (PostDomSucc->getSinglePredecessor () && "PostDom successor has more than one predecessor." ) ? void (0) : __assert_fail ("PostDomSucc->getSinglePredecessor() && \"PostDom successor has more than one predecessor.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 355, __extension__ __PRETTY_FUNCTION__)) |
355 | "PostDom successor has more than one predecessor.")(static_cast <bool> (PostDomSucc->getSinglePredecessor () && "PostDom successor has more than one predecessor." ) ? void (0) : __assert_fail ("PostDomSucc->getSinglePredecessor() && \"PostDom successor has more than one predecessor.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 355, __extension__ __PRETTY_FUNCTION__)); |
356 | DT->addNewBlock(PostDomSucc, BB); |
357 | continue; |
358 | } |
359 | BasicBlock *InterimSucc = Succs[1]; |
360 | if (PostDomSucc->getSingleSuccessor() == InterimSucc) { |
361 | PostDomSucc = Succs[1]; |
362 | InterimSucc = Succs[0]; |
363 | } |
364 | assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&(static_cast <bool> (InterimSucc->getSingleSuccessor () == PostDomSucc && "One successor of a basic block does not lead to the other." ) ? void (0) : __assert_fail ("InterimSucc->getSingleSuccessor() == PostDomSucc && \"One successor of a basic block does not lead to the other.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 365, __extension__ __PRETTY_FUNCTION__)) |
365 | "One successor of a basic block does not lead to the other.")(static_cast <bool> (InterimSucc->getSingleSuccessor () == PostDomSucc && "One successor of a basic block does not lead to the other." ) ? void (0) : __assert_fail ("InterimSucc->getSingleSuccessor() == PostDomSucc && \"One successor of a basic block does not lead to the other.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 365, __extension__ __PRETTY_FUNCTION__)); |
366 | assert(InterimSucc->getSinglePredecessor() &&(static_cast <bool> (InterimSucc->getSinglePredecessor () && "Interim successor has more than one predecessor." ) ? void (0) : __assert_fail ("InterimSucc->getSinglePredecessor() && \"Interim successor has more than one predecessor.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 367, __extension__ __PRETTY_FUNCTION__)) |
367 | "Interim successor has more than one predecessor.")(static_cast <bool> (InterimSucc->getSinglePredecessor () && "Interim successor has more than one predecessor." ) ? void (0) : __assert_fail ("InterimSucc->getSinglePredecessor() && \"Interim successor has more than one predecessor.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 367, __extension__ __PRETTY_FUNCTION__)); |
368 | assert(pred_size(PostDomSucc) == 2 &&(static_cast <bool> (pred_size(PostDomSucc) == 2 && "PostDom successor has more than two predecessors.") ? void ( 0) : __assert_fail ("pred_size(PostDomSucc) == 2 && \"PostDom successor has more than two predecessors.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 369, __extension__ __PRETTY_FUNCTION__)) |
369 | "PostDom successor has more than two predecessors.")(static_cast <bool> (pred_size(PostDomSucc) == 2 && "PostDom successor has more than two predecessors.") ? void ( 0) : __assert_fail ("pred_size(PostDomSucc) == 2 && \"PostDom successor has more than two predecessors.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 369, __extension__ __PRETTY_FUNCTION__)); |
370 | DT->addNewBlock(InterimSucc, BB); |
371 | DT->addNewBlock(PostDomSucc, BB); |
372 | } |
373 | } |
374 | |
375 | const Twine VPlanPrinter::getUID(const VPBlockBase *Block) { |
376 | return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") + |
377 | Twine(getOrCreateBID(Block)); |
378 | } |
379 | |
380 | const Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) { |
381 | const std::string &Name = Block->getName(); |
382 | if (!Name.empty()) |
383 | return Name; |
384 | return "VPB" + Twine(getOrCreateBID(Block)); |
385 | } |
386 | |
387 | void VPlanPrinter::dump() { |
388 | Depth = 1; |
389 | bumpIndent(0); |
390 | OS << "digraph VPlan {\n"; |
391 | OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan"; |
392 | if (!Plan.getName().empty()) |
393 | OS << "\\n" << DOT::EscapeString(Plan.getName()); |
394 | if (!Plan.Value2VPValue.empty()) { |
395 | OS << ", where:"; |
396 | for (auto Entry : Plan.Value2VPValue) { |
397 | OS << "\\n" << *Entry.second; |
398 | OS << DOT::EscapeString(" := "); |
399 | Entry.first->printAsOperand(OS, false); |
400 | } |
401 | } |
402 | OS << "\"]\n"; |
403 | OS << "node [shape=rect, fontname=Courier, fontsize=30]\n"; |
404 | OS << "edge [fontname=Courier, fontsize=30]\n"; |
405 | OS << "compound=true\n"; |
406 | |
407 | for (VPBlockBase *Block : depth_first(Plan.getEntry())) |
408 | dumpBlock(Block); |
409 | |
410 | OS << "}\n"; |
411 | } |
412 | |
413 | void VPlanPrinter::dumpBlock(const VPBlockBase *Block) { |
414 | if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block)) |
415 | dumpBasicBlock(BasicBlock); |
416 | else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block)) |
417 | dumpRegion(Region); |
418 | else |
419 | llvm_unreachable("Unsupported kind of VPBlock.")::llvm::llvm_unreachable_internal("Unsupported kind of VPBlock." , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 419); |
420 | } |
421 | |
422 | void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To, |
423 | bool Hidden, const Twine &Label) { |
424 | // Due to "dot" we print an edge between two regions as an edge between the |
425 | // exit basic block and the entry basic of the respective regions. |
426 | const VPBlockBase *Tail = From->getExitBasicBlock(); |
427 | const VPBlockBase *Head = To->getEntryBasicBlock(); |
428 | OS << Indent << getUID(Tail) << " -> " << getUID(Head); |
429 | OS << " [ label=\"" << Label << '\"'; |
430 | if (Tail != From) |
431 | OS << " ltail=" << getUID(From); |
432 | if (Head != To) |
433 | OS << " lhead=" << getUID(To); |
434 | if (Hidden) |
435 | OS << "; splines=none"; |
436 | OS << "]\n"; |
437 | } |
438 | |
439 | void VPlanPrinter::dumpEdges(const VPBlockBase *Block) { |
440 | auto &Successors = Block->getSuccessors(); |
441 | if (Successors.size() == 1) |
442 | drawEdge(Block, Successors.front(), false, ""); |
443 | else if (Successors.size() == 2) { |
444 | drawEdge(Block, Successors.front(), false, "T"); |
445 | drawEdge(Block, Successors.back(), false, "F"); |
446 | } else { |
447 | unsigned SuccessorNumber = 0; |
448 | for (auto *Successor : Successors) |
449 | drawEdge(Block, Successor, false, Twine(SuccessorNumber++)); |
450 | } |
451 | } |
452 | |
453 | void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) { |
454 | OS << Indent << getUID(BasicBlock) << " [label =\n"; |
455 | bumpIndent(1); |
456 | OS << Indent << "\"" << DOT::EscapeString(BasicBlock->getName()) << ":\\n\""; |
457 | bumpIndent(1); |
458 | for (const VPRecipeBase &Recipe : *BasicBlock) |
459 | Recipe.print(OS, Indent); |
460 | |
461 | // Dump the condition bit. |
462 | const VPValue *CBV = BasicBlock->getCondBit(); |
463 | if (CBV) { |
464 | OS << " +\n" << Indent << " \"CondBit: "; |
465 | if (const VPInstruction *CBI = dyn_cast<VPInstruction>(CBV)) { |
466 | CBI->printAsOperand(OS); |
467 | OS << " (" << DOT::EscapeString(CBI->getParent()->getName()) << ")\\l\""; |
468 | } else |
469 | CBV->printAsOperand(OS); |
470 | } |
471 | |
472 | bumpIndent(-2); |
473 | OS << "\n" << Indent << "]\n"; |
474 | dumpEdges(BasicBlock); |
475 | } |
476 | |
477 | void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) { |
478 | OS << Indent << "subgraph " << getUID(Region) << " {\n"; |
479 | bumpIndent(1); |
480 | OS << Indent << "fontname=Courier\n" |
481 | << Indent << "label=\"" |
482 | << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ") |
483 | << DOT::EscapeString(Region->getName()) << "\"\n"; |
484 | // Dump the blocks of the region. |
485 | assert(Region->getEntry() && "Region contains no inner blocks.")(static_cast <bool> (Region->getEntry() && "Region contains no inner blocks." ) ? void (0) : __assert_fail ("Region->getEntry() && \"Region contains no inner blocks.\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp" , 485, __extension__ __PRETTY_FUNCTION__)); |
486 | for (const VPBlockBase *Block : depth_first(Region->getEntry())) |
487 | dumpBlock(Block); |
488 | bumpIndent(-1); |
489 | OS << Indent << "}\n"; |
490 | dumpEdges(Region); |
491 | } |
492 | |
493 | void VPlanPrinter::printAsIngredient(raw_ostream &O, Value *V) { |
494 | std::string IngredientString; |
495 | raw_string_ostream RSO(IngredientString); |
496 | if (auto *Inst = dyn_cast<Instruction>(V)) { |
497 | if (!Inst->getType()->isVoidTy()) { |
498 | Inst->printAsOperand(RSO, false); |
499 | RSO << " = "; |
500 | } |
501 | RSO << Inst->getOpcodeName() << " "; |
502 | unsigned E = Inst->getNumOperands(); |
503 | if (E > 0) { |
504 | Inst->getOperand(0)->printAsOperand(RSO, false); |
505 | for (unsigned I = 1; I < E; ++I) |
506 | Inst->getOperand(I)->printAsOperand(RSO << ", ", false); |
507 | } |
508 | } else // !Inst |
509 | V->printAsOperand(RSO, false); |
510 | RSO.flush(); |
511 | O << DOT::EscapeString(IngredientString); |
512 | } |
513 | |
514 | void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent) const { |
515 | O << " +\n" << Indent << "\"WIDEN\\l\""; |
516 | for (auto &Instr : make_range(Begin, End)) |
517 | O << " +\n" << Indent << "\" " << VPlanIngredient(&Instr) << "\\l\""; |
518 | } |
519 | |
520 | void VPWidenIntOrFpInductionRecipe::print(raw_ostream &O, |
521 | const Twine &Indent) const { |
522 | O << " +\n" << Indent << "\"WIDEN-INDUCTION"; |
523 | if (Trunc) { |
524 | O << "\\l\""; |
525 | O << " +\n" << Indent << "\" " << VPlanIngredient(IV) << "\\l\""; |
526 | O << " +\n" << Indent << "\" " << VPlanIngredient(Trunc) << "\\l\""; |
527 | } else |
528 | O << " " << VPlanIngredient(IV) << "\\l\""; |
529 | } |
530 | |
531 | void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent) const { |
532 | O << " +\n" << Indent << "\"WIDEN-PHI " << VPlanIngredient(Phi) << "\\l\""; |
533 | } |
534 | |
535 | void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent) const { |
536 | O << " +\n" << Indent << "\"BLEND "; |
537 | Phi->printAsOperand(O, false); |
538 | O << " ="; |
539 | if (!User) { |
540 | // Not a User of any mask: not really blending, this is a |
541 | // single-predecessor phi. |
542 | O << " "; |
543 | Phi->getIncomingValue(0)->printAsOperand(O, false); |
544 | } else { |
545 | for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) { |
546 | O << " "; |
547 | Phi->getIncomingValue(I)->printAsOperand(O, false); |
548 | O << "/"; |
549 | User->getOperand(I)->printAsOperand(O); |
550 | } |
551 | } |
552 | O << "\\l\""; |
553 | } |
554 | |
555 | void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent) const { |
556 | O << " +\n" |
557 | << Indent << "\"" << (IsUniform ? "CLONE " : "REPLICATE ") |
558 | << VPlanIngredient(Ingredient); |
559 | if (AlsoPack) |
560 | O << " (S->V)"; |
561 | O << "\\l\""; |
562 | } |
563 | |
564 | void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent) const { |
565 | O << " +\n" |
566 | << Indent << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst) |
567 | << "\\l\""; |
568 | } |
569 | |
570 | void VPWidenMemoryInstructionRecipe::print(raw_ostream &O, |
571 | const Twine &Indent) const { |
572 | O << " +\n" << Indent << "\"WIDEN " << VPlanIngredient(&Instr); |
573 | if (User) { |
574 | O << ", "; |
575 | User->getOperand(0)->printAsOperand(O); |
576 | } |
577 | O << "\\l\""; |
578 | } |