Bug Summary

File:lib/Transforms/Vectorize/VPlan.cpp
Warning:line 297, column 15
Value stored to 'VectorLatchBB' during its initialization is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name VPlan.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/lib/Transforms/Vectorize -I /build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn338205/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/lib/gcc/x86_64-linux-gnu/8/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/lib/Transforms/Vectorize -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-07-29-043837-17923-1 -x c++ /build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Vectorize/VPlan.cpp -faddrsig
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
45using namespace llvm;
46
47#define DEBUG_TYPE"vplan" "vplan"
48
49raw_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.
58const 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
65VPBasicBlock *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.
73const 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
80VPBasicBlock *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
87VPBlockBase *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
95VPBlockBase *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
103void 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
112BasicBlock *
113VPBasicBlock::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
146void 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
190void 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
223void VPRecipeBase::insertBefore(VPRecipeBase *InsertPos) {
224 Parent = InsertPos->getParent();
225 Parent->getRecipeList().insert(InsertPos->getIterator(), this);
226}
227
228iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() {
229 return getParent()->getRecipeList().erase(getIterator());
230}
231
232void 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
256void 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
262void VPInstruction::print(raw_ostream &O, const Twine &Indent) const {
263 O << " +\n" << Indent << "\"EMIT ";
264 print(O);
265 O << "\\l\"";
266}
267
268void 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.
289void 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
338void 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
375const Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
376 return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
377 Twine(getOrCreateBID(Block));
378}
379
380const 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
387void 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
413void 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
422void 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
439void 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
453void 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
477void 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
493void 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
514void 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
520void 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
531void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
532 O << " +\n" << Indent << "\"WIDEN-PHI " << VPlanIngredient(Phi) << "\\l\"";
533}
534
535void 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
555void 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
564void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
565 O << " +\n"
566 << Indent << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst)
567 << "\\l\"";
568}
569
570void 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}