Bug Summary

File:lib/Transforms/Vectorize/VPlan.cpp
Warning:line 288, 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~svn329677/build-llvm/lib/Transforms/Vectorize -I /build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Vectorize -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn329677/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/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/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-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn329677/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-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-04-11-031539-24776-1 -x c++ /build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Vectorize/VPlan.cpp
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~svn329677/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~svn329677/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~svn329677/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~svn329677/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 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~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 126, __extension__ __PRETTY_FUNCTION__))
;
127 auto *PredBBTerminator = PredBB->getTerminator();
128 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~svn329677/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~svn329677/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~svn329677/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~svn329677/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~svn329677/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~svn329677/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 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 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 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~svn329677/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 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 VPInstruction::generateInstruction(VPTransformState &State,
224 unsigned Part) {
225 IRBuilder<> &Builder = State.Builder;
226
227 if (Instruction::isBinaryOp(getOpcode())) {
228 Value *A = State.get(getOperand(0), Part);
229 Value *B = State.get(getOperand(1), Part);
230 Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B);
231 State.set(this, V, Part);
232 return;
233 }
234
235 switch (getOpcode()) {
236 case VPInstruction::Not: {
237 Value *A = State.get(getOperand(0), Part);
238 Value *V = Builder.CreateNot(A);
239 State.set(this, V, Part);
240 break;
241 }
242 default:
243 llvm_unreachable("Unsupported opcode for instruction")::llvm::llvm_unreachable_internal("Unsupported opcode for instruction"
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 243)
;
244 }
245}
246
247void VPInstruction::execute(VPTransformState &State) {
248 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~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 248, __extension__ __PRETTY_FUNCTION__))
;
249 for (unsigned Part = 0; Part < State.UF; ++Part)
250 generateInstruction(State, Part);
251}
252
253void VPInstruction::print(raw_ostream &O, const Twine &Indent) const {
254 O << " +\n" << Indent << "\"EMIT ";
255 print(O);
256 O << "\\l\"";
257}
258
259void VPInstruction::print(raw_ostream &O) const {
260 printAsOperand(O);
261 O << " = ";
262
263 switch (getOpcode()) {
264 case VPInstruction::Not:
265 O << "not";
266 break;
267 default:
268 O << Instruction::getOpcodeName(getOpcode());
269 }
270
271 for (const VPValue *Operand : operands()) {
272 O << " ";
273 Operand->printAsOperand(O);
274 }
275}
276
277/// Generate the code inside the body of the vectorized loop. Assumes a single
278/// LoopVectorBody basic-block was created for this. Introduce additional
279/// basic-blocks as needed, and fill them all.
280void VPlan::execute(VPTransformState *State) {
281 // 0. Set the reverse mapping from VPValues to Values for code generation.
282 for (auto &Entry : Value2VPValue)
283 State->VPValue2Value[Entry.second] = Entry.first;
284
285 BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
286 BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
287 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~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 287, __extension__ __PRETTY_FUNCTION__))
;
288 BasicBlock *VectorLatchBB = VectorHeaderBB;
Value stored to 'VectorLatchBB' during its initialization is never read
289
290 // 1. Make room to generate basic-blocks inside loop body if needed.
291 VectorLatchBB = VectorHeaderBB->splitBasicBlock(
292 VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch");
293 Loop *L = State->LI->getLoopFor(VectorHeaderBB);
294 L->addBasicBlockToLoop(VectorLatchBB, *State->LI);
295 // Remove the edge between Header and Latch to allow other connections.
296 // Temporarily terminate with unreachable until CFG is rewired.
297 // Note: this asserts the generated code's assumption that
298 // getFirstInsertionPt() can be dereferenced into an Instruction.
299 VectorHeaderBB->getTerminator()->eraseFromParent();
300 State->Builder.SetInsertPoint(VectorHeaderBB);
301 UnreachableInst *Terminator = State->Builder.CreateUnreachable();
302 State->Builder.SetInsertPoint(Terminator);
303
304 // 2. Generate code in loop body.
305 State->CFG.PrevVPBB = nullptr;
306 State->CFG.PrevBB = VectorHeaderBB;
307 State->CFG.LastBB = VectorLatchBB;
308
309 for (VPBlockBase *Block : depth_first(Entry))
310 Block->execute(State);
311
312 // 3. Merge the temporary latch created with the last basic-block filled.
313 BasicBlock *LastBB = State->CFG.PrevBB;
314 // Connect LastBB to VectorLatchBB to facilitate their merge.
315 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~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 316, __extension__ __PRETTY_FUNCTION__))
316 "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~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 316, __extension__ __PRETTY_FUNCTION__))
;
317 LastBB->getTerminator()->eraseFromParent();
318 BranchInst::Create(VectorLatchBB, LastBB);
319
320 // Merge LastBB with Latch.
321 bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI);
322 (void)Merged;
323 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~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 323, __extension__ __PRETTY_FUNCTION__))
;
324 VectorLatchBB = LastBB;
325
326 updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB);
327}
328
329void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
330 BasicBlock *LoopLatchBB) {
331 BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor();
332 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~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 332, __extension__ __PRETTY_FUNCTION__))
;
333 DT->addNewBlock(LoopHeaderBB, LoopPreHeaderBB);
334 // The vector body may be more than a single basic-block by this point.
335 // Update the dominator tree information inside the vector body by propagating
336 // it from header to latch, expecting only triangular control-flow, if any.
337 BasicBlock *PostDomSucc = nullptr;
338 for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
339 // Get the list of successors of this block.
340 std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
341 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~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 342, __extension__ __PRETTY_FUNCTION__))
342 "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~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 342, __extension__ __PRETTY_FUNCTION__))
;
343 PostDomSucc = Succs[0];
344 if (Succs.size() == 1) {
345 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~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 346, __extension__ __PRETTY_FUNCTION__))
346 "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~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 346, __extension__ __PRETTY_FUNCTION__))
;
347 DT->addNewBlock(PostDomSucc, BB);
348 continue;
349 }
350 BasicBlock *InterimSucc = Succs[1];
351 if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
352 PostDomSucc = Succs[1];
353 InterimSucc = Succs[0];
354 }
355 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~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 356, __extension__ __PRETTY_FUNCTION__))
356 "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~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 356, __extension__ __PRETTY_FUNCTION__))
;
357 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~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 358, __extension__ __PRETTY_FUNCTION__))
358 "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~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 358, __extension__ __PRETTY_FUNCTION__))
;
359 assert(std::distance(pred_begin(PostDomSucc), pred_end(PostDomSucc)) == 2 &&(static_cast <bool> (std::distance(pred_begin(PostDomSucc
), pred_end(PostDomSucc)) == 2 && "PostDom successor has more than two predecessors."
) ? void (0) : __assert_fail ("std::distance(pred_begin(PostDomSucc), pred_end(PostDomSucc)) == 2 && \"PostDom successor has more than two predecessors.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 360, __extension__ __PRETTY_FUNCTION__))
360 "PostDom successor has more than two predecessors.")(static_cast <bool> (std::distance(pred_begin(PostDomSucc
), pred_end(PostDomSucc)) == 2 && "PostDom successor has more than two predecessors."
) ? void (0) : __assert_fail ("std::distance(pred_begin(PostDomSucc), pred_end(PostDomSucc)) == 2 && \"PostDom successor has more than two predecessors.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 360, __extension__ __PRETTY_FUNCTION__))
;
361 DT->addNewBlock(InterimSucc, BB);
362 DT->addNewBlock(PostDomSucc, BB);
363 }
364}
365
366const Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
367 return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
368 Twine(getOrCreateBID(Block));
369}
370
371const Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
372 const std::string &Name = Block->getName();
373 if (!Name.empty())
374 return Name;
375 return "VPB" + Twine(getOrCreateBID(Block));
376}
377
378void VPlanPrinter::dump() {
379 Depth = 1;
380 bumpIndent(0);
381 OS << "digraph VPlan {\n";
382 OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
383 if (!Plan.getName().empty())
384 OS << "\\n" << DOT::EscapeString(Plan.getName());
385 if (!Plan.Value2VPValue.empty()) {
386 OS << ", where:";
387 for (auto Entry : Plan.Value2VPValue) {
388 OS << "\\n" << *Entry.second;
389 OS << DOT::EscapeString(" := ");
390 Entry.first->printAsOperand(OS, false);
391 }
392 }
393 OS << "\"]\n";
394 OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
395 OS << "edge [fontname=Courier, fontsize=30]\n";
396 OS << "compound=true\n";
397
398 for (VPBlockBase *Block : depth_first(Plan.getEntry()))
399 dumpBlock(Block);
400
401 OS << "}\n";
402}
403
404void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
405 if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
406 dumpBasicBlock(BasicBlock);
407 else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
408 dumpRegion(Region);
409 else
410 llvm_unreachable("Unsupported kind of VPBlock.")::llvm::llvm_unreachable_internal("Unsupported kind of VPBlock."
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 410)
;
411}
412
413void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
414 bool Hidden, const Twine &Label) {
415 // Due to "dot" we print an edge between two regions as an edge between the
416 // exit basic block and the entry basic of the respective regions.
417 const VPBlockBase *Tail = From->getExitBasicBlock();
418 const VPBlockBase *Head = To->getEntryBasicBlock();
419 OS << Indent << getUID(Tail) << " -> " << getUID(Head);
420 OS << " [ label=\"" << Label << '\"';
421 if (Tail != From)
422 OS << " ltail=" << getUID(From);
423 if (Head != To)
424 OS << " lhead=" << getUID(To);
425 if (Hidden)
426 OS << "; splines=none";
427 OS << "]\n";
428}
429
430void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
431 auto &Successors = Block->getSuccessors();
432 if (Successors.size() == 1)
433 drawEdge(Block, Successors.front(), false, "");
434 else if (Successors.size() == 2) {
435 drawEdge(Block, Successors.front(), false, "T");
436 drawEdge(Block, Successors.back(), false, "F");
437 } else {
438 unsigned SuccessorNumber = 0;
439 for (auto *Successor : Successors)
440 drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
441 }
442}
443
444void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
445 OS << Indent << getUID(BasicBlock) << " [label =\n";
446 bumpIndent(1);
447 OS << Indent << "\"" << DOT::EscapeString(BasicBlock->getName()) << ":\\n\"";
448 bumpIndent(1);
449 for (const VPRecipeBase &Recipe : *BasicBlock)
450 Recipe.print(OS, Indent);
451 bumpIndent(-2);
452 OS << "\n" << Indent << "]\n";
453 dumpEdges(BasicBlock);
454}
455
456void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
457 OS << Indent << "subgraph " << getUID(Region) << " {\n";
458 bumpIndent(1);
459 OS << Indent << "fontname=Courier\n"
460 << Indent << "label=\""
461 << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
462 << DOT::EscapeString(Region->getName()) << "\"\n";
463 // Dump the blocks of the region.
464 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~svn329677/lib/Transforms/Vectorize/VPlan.cpp"
, 464, __extension__ __PRETTY_FUNCTION__))
;
465 for (const VPBlockBase *Block : depth_first(Region->getEntry()))
466 dumpBlock(Block);
467 bumpIndent(-1);
468 OS << Indent << "}\n";
469 dumpEdges(Region);
470}
471
472void VPlanPrinter::printAsIngredient(raw_ostream &O, Value *V) {
473 std::string IngredientString;
474 raw_string_ostream RSO(IngredientString);
475 if (auto *Inst = dyn_cast<Instruction>(V)) {
476 if (!Inst->getType()->isVoidTy()) {
477 Inst->printAsOperand(RSO, false);
478 RSO << " = ";
479 }
480 RSO << Inst->getOpcodeName() << " ";
481 unsigned E = Inst->getNumOperands();
482 if (E > 0) {
483 Inst->getOperand(0)->printAsOperand(RSO, false);
484 for (unsigned I = 1; I < E; ++I)
485 Inst->getOperand(I)->printAsOperand(RSO << ", ", false);
486 }
487 } else // !Inst
488 V->printAsOperand(RSO, false);
489 RSO.flush();
490 O << DOT::EscapeString(IngredientString);
491}
492
493void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent) const {
494 O << " +\n" << Indent << "\"WIDEN\\l\"";
495 for (auto &Instr : make_range(Begin, End))
496 O << " +\n" << Indent << "\" " << VPlanIngredient(&Instr) << "\\l\"";
497}
498
499void VPWidenIntOrFpInductionRecipe::print(raw_ostream &O,
500 const Twine &Indent) const {
501 O << " +\n" << Indent << "\"WIDEN-INDUCTION";
502 if (Trunc) {
503 O << "\\l\"";
504 O << " +\n" << Indent << "\" " << VPlanIngredient(IV) << "\\l\"";
505 O << " +\n" << Indent << "\" " << VPlanIngredient(Trunc) << "\\l\"";
506 } else
507 O << " " << VPlanIngredient(IV) << "\\l\"";
508}
509
510void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
511 O << " +\n" << Indent << "\"WIDEN-PHI " << VPlanIngredient(Phi) << "\\l\"";
512}
513
514void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent) const {
515 O << " +\n" << Indent << "\"BLEND ";
516 Phi->printAsOperand(O, false);
517 O << " =";
518 if (!User) {
519 // Not a User of any mask: not really blending, this is a
520 // single-predecessor phi.
521 O << " ";
522 Phi->getIncomingValue(0)->printAsOperand(O, false);
523 } else {
524 for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) {
525 O << " ";
526 Phi->getIncomingValue(I)->printAsOperand(O, false);
527 O << "/";
528 User->getOperand(I)->printAsOperand(O);
529 }
530 }
531 O << "\\l\"";
532}
533
534void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent) const {
535 O << " +\n"
536 << Indent << "\"" << (IsUniform ? "CLONE " : "REPLICATE ")
537 << VPlanIngredient(Ingredient);
538 if (AlsoPack)
539 O << " (S->V)";
540 O << "\\l\"";
541}
542
543void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
544 O << " +\n"
545 << Indent << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst)
546 << "\\l\"";
547}
548
549void VPWidenMemoryInstructionRecipe::print(raw_ostream &O,
550 const Twine &Indent) const {
551 O << " +\n" << Indent << "\"WIDEN " << VPlanIngredient(&Instr);
552 if (User) {
553 O << ", ";
554 User->getOperand(0)->printAsOperand(O);
555 }
556 O << "\\l\"";
557}