Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Transforms/Vectorize/VPlan.cpp
Line
Count
Source (jump to first uncovered line)
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/PostOrderIterator.h"
22
#include "llvm/Analysis/LoopInfo.h"
23
#include "llvm/IR/BasicBlock.h"
24
#include "llvm/IR/Dominators.h"
25
#include "llvm/Support/GraphWriter.h"
26
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
27
28
using namespace llvm;
29
30
#define DEBUG_TYPE "vplan"
31
32
/// \return the VPBasicBlock that is the entry of Block, possibly indirectly.
33
0
const VPBasicBlock *VPBlockBase::getEntryBasicBlock() const {
34
0
  const VPBlockBase *Block = this;
35
0
  while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
36
0
    Block = Region->getEntry();
37
0
  return cast<VPBasicBlock>(Block);
38
0
}
39
40
0
VPBasicBlock *VPBlockBase::getEntryBasicBlock() {
41
0
  VPBlockBase *Block = this;
42
0
  while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
43
0
    Block = Region->getEntry();
44
0
  return cast<VPBasicBlock>(Block);
45
0
}
46
47
/// \return the VPBasicBlock that is the exit of Block, possibly indirectly.
48
0
const VPBasicBlock *VPBlockBase::getExitBasicBlock() const {
49
0
  const VPBlockBase *Block = this;
50
0
  while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
51
0
    Block = Region->getExit();
52
0
  return cast<VPBasicBlock>(Block);
53
0
}
54
55
2.93k
VPBasicBlock *VPBlockBase::getExitBasicBlock() {
56
2.93k
  VPBlockBase *Block = this;
57
3.07k
  while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
58
135
    Block = Region->getExit();
59
2.93k
  return cast<VPBasicBlock>(Block);
60
2.93k
}
61
62
1.29k
VPBlockBase *VPBlockBase::getEnclosingBlockWithSuccessors() {
63
1.29k
  if (
!Successors.empty() || 1.29k
!Parent135
)
64
1.15k
    return this;
65
1.29k
  assert(Parent->getExit() == this &&
66
135
         "Block w/o successors not the exit of its parent.");
67
135
  return Parent->getEnclosingBlockWithSuccessors();
68
135
}
69
70
3.41k
VPBlockBase *VPBlockBase::getEnclosingBlockWithPredecessors() {
71
3.41k
  if (
!Predecessors.empty() || 3.41k
!Parent478
)
72
2.93k
    return this;
73
3.41k
  assert(Parent->getEntry() == this &&
74
478
         "Block w/o predecessors not the entry of its parent.");
75
478
  return Parent->getEnclosingBlockWithPredecessors();
76
478
}
77
78
54.8k
void VPBlockBase::deleteCFG(VPBlockBase *Entry) {
79
54.8k
  SmallVector<VPBlockBase *, 8> Blocks;
80
54.8k
  for (VPBlockBase *Block : depth_first(Entry))
81
57.4k
    Blocks.push_back(Block);
82
54.8k
83
54.8k
  for (VPBlockBase *Block : Blocks)
84
57.4k
    delete Block;
85
54.8k
}
86
87
BasicBlock *
88
956
VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) {
89
956
  // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.
90
956
  // Pred stands for Predessor. Prev stands for Previous - last visited/created.
91
956
  BasicBlock *PrevBB = CFG.PrevBB;
92
956
  BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(),
93
956
                                         PrevBB->getParent(), CFG.LastBB);
94
956
  DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n');
95
956
96
956
  // Hook up the new basic block to its predecessors.
97
1.43k
  for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
98
1.43k
    VPBasicBlock *PredVPBB = PredVPBlock->getExitBasicBlock();
99
1.43k
    auto &PredVPSuccessors = PredVPBB->getSuccessors();
100
1.43k
    BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB];
101
1.43k
    assert(PredBB && "Predecessor basic-block not found building successor.");
102
1.43k
    auto *PredBBTerminator = PredBB->getTerminator();
103
1.43k
    DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n');
104
1.43k
    if (
isa<UnreachableInst>(PredBBTerminator)1.43k
) {
105
478
      assert(PredVPSuccessors.size() == 1 &&
106
478
             "Predecessor ending w/o branch must have single successor.");
107
478
      PredBBTerminator->eraseFromParent();
108
478
      BranchInst::Create(NewBB, PredBB);
109
1.43k
    } else {
110
956
      assert(PredVPSuccessors.size() == 2 &&
111
956
             "Predecessor ending with branch must have two successors.");
112
956
      unsigned idx = PredVPSuccessors.front() == this ? 
0478
:
1478
;
113
956
      assert(!PredBBTerminator->getSuccessor(idx) &&
114
956
             "Trying to reset an existing successor block.");
115
956
      PredBBTerminator->setSuccessor(idx, NewBB);
116
956
    }
117
1.43k
  }
118
956
  return NewBB;
119
956
}
120
121
26.5k
void VPBasicBlock::execute(VPTransformState *State) {
122
26.5k
  bool Replica = State->Instance &&
123
1.43k
                 
!(State->Instance->Part == 0 && 1.43k
State->Instance->Lane == 01.20k
);
124
26.5k
  VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB;
125
26.5k
  VPBlockBase *SingleHPred = nullptr;
126
26.5k
  BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible.
127
26.5k
128
26.5k
  // 1. Create an IR basic block, or reuse the last one if possible.
129
26.5k
  // The last IR basic block is reused, as an optimization, in three cases:
130
26.5k
  // A. the first VPBB reuses the loop header BB - when PrevVPBB is null;
131
26.5k
  // B. when the current VPBB has a single (hierarchical) predecessor which
132
26.5k
  //    is PrevVPBB and the latter has a single (hierarchical) successor; and
133
26.5k
  // C. when the current VPBB is an entry of a region replica - where PrevVPBB
134
26.5k
  //    is the exit of this region from a previous instance, or the predecessor
135
26.5k
  //    of this region.
136
26.5k
  if (PrevVPBB && /* A */
137
1.97k
      !((SingleHPred = getSingleHierarchicalPredecessor()) &&
138
1.50k
        SingleHPred->getExitBasicBlock() == PrevVPBB &&
139
1.97k
        PrevVPBB->getSingleHierarchicalSuccessor()) && /* B */
140
26.5k
      
!(Replica && 1.29k
getPredecessors().empty()1.02k
)) { /* C */
141
956
142
956
    NewBB = createEmptyBasicBlock(State->CFG);
143
956
    State->Builder.SetInsertPoint(NewBB);
144
956
    // Temporarily terminate with unreachable until CFG is rewired.
145
956
    UnreachableInst *Terminator = State->Builder.CreateUnreachable();
146
956
    State->Builder.SetInsertPoint(Terminator);
147
956
    // Register NewBB in its loop. In innermost loops its the same for all BB's.
148
956
    Loop *L = State->LI->getLoopFor(State->CFG.LastBB);
149
956
    L->addBasicBlockToLoop(NewBB, *State->LI);
150
956
    State->CFG.PrevBB = NewBB;
151
956
  }
152
26.5k
153
26.5k
  // 2. Fill the IR basic block with IR instructions.
154
26.5k
  DEBUG(dbgs() << "LV: vectorizing VPBB:" << getName()
155
26.5k
               << " in BB:" << NewBB->getName() << '\n');
156
26.5k
157
26.5k
  State->CFG.VPBB2IRBB[this] = NewBB;
158
26.5k
  State->CFG.PrevVPBB = this;
159
26.5k
160
26.5k
  for (VPRecipeBase &Recipe : Recipes)
161
154k
    Recipe.execute(*State);
162
26.5k
163
26.5k
  DEBUG(dbgs() << "LV: filled BB:" << *NewBB);
164
26.5k
}
165
166
135
void VPRegionBlock::execute(VPTransformState *State) {
167
135
  ReversePostOrderTraversal<VPBlockBase *> RPOT(Entry);
168
135
169
135
  if (
!isReplicator()135
) {
170
0
    // Visit the VPBlocks connected to "this", starting from it.
171
0
    for (VPBlockBase *Block : RPOT) {
172
0
      DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
173
0
      Block->execute(State);
174
0
    }
175
0
    return;
176
0
  }
177
135
178
135
  assert(!State->Instance && "Replicating a Region with non-null instance.");
179
135
180
135
  // Enter replicating mode.
181
135
  State->Instance = {0, 0};
182
135
183
321
  for (unsigned Part = 0, UF = State->UF; 
Part < UF321
;
++Part186
) {
184
186
    State->Instance->Part = Part;
185
664
    for (unsigned Lane = 0, VF = State->VF; 
Lane < VF664
;
++Lane478
) {
186
478
      State->Instance->Lane = Lane;
187
478
      // Visit the VPBlocks connected to \p this, starting from it.
188
1.43k
      for (VPBlockBase *Block : RPOT) {
189
1.43k
        DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
190
1.43k
        Block->execute(State);
191
1.43k
      }
192
478
    }
193
186
  }
194
135
195
135
  // Exit replicating mode.
196
135
  State->Instance.reset();
197
135
}
198
199
/// Generate the code inside the body of the vectorized loop. Assumes a single
200
/// LoopVectorBody basic-block was created for this. Introduce additional
201
/// basic-blocks as needed, and fill them all.
202
24.6k
void VPlan::execute(VPTransformState *State) {
203
24.6k
  BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
204
24.6k
  BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
205
24.6k
  assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
206
24.6k
  BasicBlock *VectorLatchBB = VectorHeaderBB;
207
24.6k
208
24.6k
  // 1. Make room to generate basic-blocks inside loop body if needed.
209
24.6k
  VectorLatchBB = VectorHeaderBB->splitBasicBlock(
210
24.6k
      VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch");
211
24.6k
  Loop *L = State->LI->getLoopFor(VectorHeaderBB);
212
24.6k
  L->addBasicBlockToLoop(VectorLatchBB, *State->LI);
213
24.6k
  // Remove the edge between Header and Latch to allow other connections.
214
24.6k
  // Temporarily terminate with unreachable until CFG is rewired.
215
24.6k
  // Note: this asserts the generated code's assumption that
216
24.6k
  // getFirstInsertionPt() can be dereferenced into an Instruction.
217
24.6k
  VectorHeaderBB->getTerminator()->eraseFromParent();
218
24.6k
  State->Builder.SetInsertPoint(VectorHeaderBB);
219
24.6k
  UnreachableInst *Terminator = State->Builder.CreateUnreachable();
220
24.6k
  State->Builder.SetInsertPoint(Terminator);
221
24.6k
222
24.6k
  // 2. Generate code in loop body.
223
24.6k
  State->CFG.PrevVPBB = nullptr;
224
24.6k
  State->CFG.PrevBB = VectorHeaderBB;
225
24.6k
  State->CFG.LastBB = VectorLatchBB;
226
24.6k
227
24.6k
  for (VPBlockBase *Block : depth_first(Entry))
228
25.2k
    Block->execute(State);
229
24.6k
230
24.6k
  // 3. Merge the temporary latch created with the last basic-block filled.
231
24.6k
  BasicBlock *LastBB = State->CFG.PrevBB;
232
24.6k
  // Connect LastBB to VectorLatchBB to facilitate their merge.
233
24.6k
  assert(isa<UnreachableInst>(LastBB->getTerminator()) &&
234
24.6k
         "Expected VPlan CFG to terminate with unreachable");
235
24.6k
  LastBB->getTerminator()->eraseFromParent();
236
24.6k
  BranchInst::Create(VectorLatchBB, LastBB);
237
24.6k
238
24.6k
  // Merge LastBB with Latch.
239
24.6k
  bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI);
240
24.6k
  (void)Merged;
241
24.6k
  assert(Merged && "Could not merge last basic block with latch.");
242
24.6k
  VectorLatchBB = LastBB;
243
24.6k
244
24.6k
  updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB);
245
24.6k
}
246
247
void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
248
24.6k
                                BasicBlock *LoopLatchBB) {
249
24.6k
  BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor();
250
24.6k
  assert(LoopHeaderBB && "Loop preheader does not have a single successor.");
251
24.6k
  DT->addNewBlock(LoopHeaderBB, LoopPreHeaderBB);
252
24.6k
  // The vector body may be more than a single basic-block by this point.
253
24.6k
  // Update the dominator tree information inside the vector body by propagating
254
24.6k
  // it from header to latch, expecting only triangular control-flow, if any.
255
24.6k
  BasicBlock *PostDomSucc = nullptr;
256
25.0k
  for (auto *BB = LoopHeaderBB; 
BB != LoopLatchBB25.0k
;
BB = PostDomSucc478
) {
257
478
    // Get the list of successors of this block.
258
478
    std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
259
478
    assert(Succs.size() <= 2 &&
260
478
           "Basic block in vector loop has more than 2 successors.");
261
478
    PostDomSucc = Succs[0];
262
478
    if (
Succs.size() == 1478
) {
263
0
      assert(PostDomSucc->getSinglePredecessor() &&
264
0
             "PostDom successor has more than one predecessor.");
265
0
      DT->addNewBlock(PostDomSucc, BB);
266
0
      continue;
267
0
    }
268
478
    BasicBlock *InterimSucc = Succs[1];
269
478
    if (
PostDomSucc->getSingleSuccessor() == InterimSucc478
) {
270
478
      PostDomSucc = Succs[1];
271
478
      InterimSucc = Succs[0];
272
478
    }
273
478
    assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
274
478
           "One successor of a basic block does not lead to the other.");
275
478
    assert(InterimSucc->getSinglePredecessor() &&
276
478
           "Interim successor has more than one predecessor.");
277
478
    assert(std::distance(pred_begin(PostDomSucc), pred_end(PostDomSucc)) == 2 &&
278
478
           "PostDom successor has more than two predecessors.");
279
478
    DT->addNewBlock(InterimSucc, BB);
280
478
    DT->addNewBlock(PostDomSucc, BB);
281
478
  }
282
24.6k
}
283
284
0
const Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
285
0
  return (isa<VPRegionBlock>(Block) ? 
"cluster_N"0
:
"N"0
) +
286
0
         Twine(getOrCreateBID(Block));
287
0
}
288
289
0
const Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
290
0
  const std::string &Name = Block->getName();
291
0
  if (!Name.empty())
292
0
    return Name;
293
0
  return "VPB" + Twine(getOrCreateBID(Block));
294
0
}
295
296
0
void VPlanPrinter::dump() {
297
0
  Depth = 1;
298
0
  bumpIndent(0);
299
0
  OS << "digraph VPlan {\n";
300
0
  OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
301
0
  if (!Plan.getName().empty())
302
0
    OS << "\\n" << DOT::EscapeString(Plan.getName());
303
0
  OS << "\"]\n";
304
0
  OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
305
0
  OS << "edge [fontname=Courier, fontsize=30]\n";
306
0
  OS << "compound=true\n";
307
0
308
0
  for (VPBlockBase *Block : depth_first(Plan.getEntry()))
309
0
    dumpBlock(Block);
310
0
311
0
  OS << "}\n";
312
0
}
313
314
0
void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
315
0
  if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
316
0
    dumpBasicBlock(BasicBlock);
317
0
  else 
if (const VPRegionBlock *0
Region0
= dyn_cast<VPRegionBlock>(Block))
318
0
    dumpRegion(Region);
319
0
  else
320
0
    llvm_unreachable("Unsupported kind of VPBlock.");
321
0
}
322
323
void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
324
0
                            bool Hidden, const Twine &Label) {
325
0
  // Due to "dot" we print an edge between two regions as an edge between the
326
0
  // exit basic block and the entry basic of the respective regions.
327
0
  const VPBlockBase *Tail = From->getExitBasicBlock();
328
0
  const VPBlockBase *Head = To->getEntryBasicBlock();
329
0
  OS << Indent << getUID(Tail) << " -> " << getUID(Head);
330
0
  OS << " [ label=\"" << Label << '\"';
331
0
  if (Tail != From)
332
0
    OS << " ltail=" << getUID(From);
333
0
  if (Head != To)
334
0
    OS << " lhead=" << getUID(To);
335
0
  if (Hidden)
336
0
    OS << "; splines=none";
337
0
  OS << "]\n";
338
0
}
339
340
0
void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
341
0
  auto &Successors = Block->getSuccessors();
342
0
  if (Successors.size() == 1)
343
0
    drawEdge(Block, Successors.front(), false, "");
344
0
  else 
if (0
Successors.size() == 20
) {
345
0
    drawEdge(Block, Successors.front(), false, "T");
346
0
    drawEdge(Block, Successors.back(), false, "F");
347
0
  } else {
348
0
    unsigned SuccessorNumber = 0;
349
0
    for (auto *Successor : Successors)
350
0
      drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
351
0
  }
352
0
}
353
354
0
void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
355
0
  OS << Indent << getUID(BasicBlock) << " [label =\n";
356
0
  bumpIndent(1);
357
0
  OS << Indent << "\"" << DOT::EscapeString(BasicBlock->getName()) << ":\\n\"";
358
0
  bumpIndent(1);
359
0
  for (const VPRecipeBase &Recipe : *BasicBlock)
360
0
    Recipe.print(OS, Indent);
361
0
  bumpIndent(-2);
362
0
  OS << "\n" << Indent << "]\n";
363
0
  dumpEdges(BasicBlock);
364
0
}
365
366
0
void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
367
0
  OS << Indent << "subgraph " << getUID(Region) << " {\n";
368
0
  bumpIndent(1);
369
0
  OS << Indent << "fontname=Courier\n"
370
0
     << Indent << "label=\""
371
0
     << DOT::EscapeString(Region->isReplicator() ? 
"<xVFxUF> "0
:
"<x1> "0
)
372
0
     << DOT::EscapeString(Region->getName()) << "\"\n";
373
0
  // Dump the blocks of the region.
374
0
  assert(Region->getEntry() && "Region contains no inner blocks.");
375
0
  for (const VPBlockBase *Block : depth_first(Region->getEntry()))
376
0
    dumpBlock(Block);
377
0
  bumpIndent(-1);
378
0
  OS << Indent << "}\n";
379
0
  dumpEdges(Region);
380
0
}
381
382
0
void VPlanPrinter::printAsIngredient(raw_ostream &O, Value *V) {
383
0
  std::string IngredientString;
384
0
  raw_string_ostream RSO(IngredientString);
385
0
  if (auto *
Inst0
= dyn_cast<Instruction>(V)) {
386
0
    if (
!Inst->getType()->isVoidTy()0
) {
387
0
      Inst->printAsOperand(RSO, false);
388
0
      RSO << " = ";
389
0
    }
390
0
    RSO << Inst->getOpcodeName() << " ";
391
0
    unsigned E = Inst->getNumOperands();
392
0
    if (
E > 00
) {
393
0
      Inst->getOperand(0)->printAsOperand(RSO, false);
394
0
      for (unsigned I = 1; 
I < E0
;
++I0
)
395
0
        Inst->getOperand(I)->printAsOperand(RSO << ", ", false);
396
0
    }
397
0
  } else // !Inst
398
0
    V->printAsOperand(RSO, false);
399
0
  RSO.flush();
400
0
  O << DOT::EscapeString(IngredientString);
401
0
}