Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Vectorize/VPlan.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- VPlan.cpp - Vectorizer Plan ----------------------------------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
///
9
/// \file
10
/// This is the LLVM vectorization plan. It represents a candidate for
11
/// vectorization, allowing to plan and optimize how to vectorize a given loop
12
/// before generating LLVM-IR.
13
/// The vectorizer uses vectorization plans to estimate the costs of potential
14
/// candidates and if profitable to execute the desired plan, generating vector
15
/// LLVM-IR code.
16
///
17
//===----------------------------------------------------------------------===//
18
19
#include "VPlan.h"
20
#include "VPlanDominatorTree.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/InstrTypes.h"
29
#include "llvm/IR/Instruction.h"
30
#include "llvm/IR/Instructions.h"
31
#include "llvm/IR/Type.h"
32
#include "llvm/IR/Value.h"
33
#include "llvm/Support/Casting.h"
34
#include "llvm/Support/Debug.h"
35
#include "llvm/Support/ErrorHandling.h"
36
#include "llvm/Support/GenericDomTreeConstruction.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
extern cl::opt<bool> EnableVPlanNativePath;
47
48
#define DEBUG_TYPE "vplan"
49
50
0
raw_ostream &llvm::operator<<(raw_ostream &OS, const VPValue &V) {
51
0
  if (const VPInstruction *Instr = dyn_cast<VPInstruction>(&V))
52
0
    Instr->print(OS);
53
0
  else
54
0
    V.printAsOperand(OS);
55
0
  return OS;
56
0
}
57
58
/// \return the VPBasicBlock that is the entry of Block, possibly indirectly.
59
0
const VPBasicBlock *VPBlockBase::getEntryBasicBlock() const {
60
0
  const VPBlockBase *Block = this;
61
0
  while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
62
0
    Block = Region->getEntry();
63
0
  return cast<VPBasicBlock>(Block);
64
0
}
65
66
123
VPBasicBlock *VPBlockBase::getEntryBasicBlock() {
67
123
  VPBlockBase *Block = this;
68
137
  while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
69
14
    Block = Region->getEntry();
70
123
  return cast<VPBasicBlock>(Block);
71
123
}
72
73
/// \return the VPBasicBlock that is the exit of Block, possibly indirectly.
74
0
const VPBasicBlock *VPBlockBase::getExitBasicBlock() const {
75
0
  const VPBlockBase *Block = this;
76
0
  while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
77
0
    Block = Region->getExit();
78
0
  return cast<VPBasicBlock>(Block);
79
0
}
80
81
5.74k
VPBasicBlock *VPBlockBase::getExitBasicBlock() {
82
5.74k
  VPBlockBase *Block = this;
83
6.06k
  while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
84
325
    Block = Region->getExit();
85
5.74k
  return cast<VPBasicBlock>(Block);
86
5.74k
}
87
88
2.58k
VPBlockBase *VPBlockBase::getEnclosingBlockWithSuccessors() {
89
2.58k
  if (!Successors.empty() || 
!Parent325
)
90
2.25k
    return this;
91
325
  assert(Parent->getExit() == this &&
92
325
         "Block w/o successors not the exit of its parent.");
93
325
  return Parent->getEnclosingBlockWithSuccessors();
94
325
}
95
96
6.68k
VPBlockBase *VPBlockBase::getEnclosingBlockWithPredecessors() {
97
6.68k
  if (!Predecessors.empty() || 
!Parent948
)
98
5.74k
    return this;
99
948
  assert(Parent->getEntry() == this &&
100
948
         "Block w/o predecessors not the entry of its parent.");
101
948
  return Parent->getEnclosingBlockWithPredecessors();
102
948
}
103
104
41.3k
void VPBlockBase::deleteCFG(VPBlockBase *Entry) {
105
41.3k
  SmallVector<VPBlockBase *, 8> Blocks;
106
41.3k
  for (VPBlockBase *Block : depth_first(Entry))
107
56.5k
    Blocks.push_back(Block);
108
41.3k
109
41.3k
  for (VPBlockBase *Block : Blocks)
110
56.5k
    delete Block;
111
41.3k
}
112
113
BasicBlock *
114
1.91k
VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) {
115
1.91k
  // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.
116
1.91k
  // Pred stands for Predessor. Prev stands for Previous - last visited/created.
117
1.91k
  BasicBlock *PrevBB = CFG.PrevBB;
118
1.91k
  BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(),
119
1.91k
                                         PrevBB->getParent(), CFG.LastBB);
120
1.91k
  LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n');
121
1.91k
122
1.91k
  // Hook up the new basic block to its predecessors.
123
2.86k
  for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
124
2.86k
    VPBasicBlock *PredVPBB = PredVPBlock->getExitBasicBlock();
125
2.86k
    auto &PredVPSuccessors = PredVPBB->getSuccessors();
126
2.86k
    BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB];
127
2.86k
128
2.86k
    // In outer loop vectorization scenario, the predecessor BBlock may not yet
129
2.86k
    // be visited(backedge). Mark the VPBasicBlock for fixup at the end of
130
2.86k
    // vectorization. We do not encounter this case in inner loop vectorization
131
2.86k
    // as we start out by building a loop skeleton with the vector loop header
132
2.86k
    // and latch blocks. As a result, we never enter this function for the
133
2.86k
    // header block in the non VPlan-native path.
134
2.86k
    if (!PredBB) {
135
7
      assert(EnableVPlanNativePath &&
136
7
             "Unexpected null predecessor in non VPlan-native path");
137
7
      CFG.VPBBsToFix.push_back(PredVPBB);
138
7
      continue;
139
7
    }
140
2.86k
141
2.86k
    assert(PredBB && "Predecessor basic-block not found building successor.");
142
2.86k
    auto *PredBBTerminator = PredBB->getTerminator();
143
2.86k
    LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n');
144
2.86k
    if (isa<UnreachableInst>(PredBBTerminator)) {
145
956
      assert(PredVPSuccessors.size() == 1 &&
146
956
             "Predecessor ending w/o branch must have single successor.");
147
956
      PredBBTerminator->eraseFromParent();
148
956
      BranchInst::Create(NewBB, PredBB);
149
1.90k
    } else {
150
1.90k
      assert(PredVPSuccessors.size() == 2 &&
151
1.90k
             "Predecessor ending with branch must have two successors.");
152
1.90k
      unsigned idx = PredVPSuccessors.front() == this ? 
0956
:
1949
;
153
1.90k
      assert(!PredBBTerminator->getSuccessor(idx) &&
154
1.90k
             "Trying to reset an existing successor block.");
155
1.90k
      PredBBTerminator->setSuccessor(idx, NewBB);
156
1.90k
    }
157
2.86k
  }
158
1.91k
  return NewBB;
159
1.91k
}
160
161
20.8k
void VPBasicBlock::execute(VPTransformState *State) {
162
20.8k
  bool Replica = State->Instance &&
163
20.8k
                 
!(2.84k
State->Instance->Part == 02.84k
&&
State->Instance->Lane == 01.95k
);
164
20.8k
  VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB;
165
20.8k
  VPBlockBase *SingleHPred = nullptr;
166
20.8k
  BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible.
167
20.8k
168
20.8k
  // 1. Create an IR basic block, or reuse the last one if possible.
169
20.8k
  // The last IR basic block is reused, as an optimization, in three cases:
170
20.8k
  // A. the first VPBB reuses the loop header BB - when PrevVPBB is null;
171
20.8k
  // B. when the current VPBB has a single (hierarchical) predecessor which
172
20.8k
  //    is PrevVPBB and the latter has a single (hierarchical) successor; and
173
20.8k
  // C. when the current VPBB is an entry of a region replica - where PrevVPBB
174
20.8k
  //    is the exit of this region from a previous instance, or the predecessor
175
20.8k
  //    of this region.
176
20.8k
  if (PrevVPBB && /* A */
177
20.8k
      
!(3.82k
(SingleHPred = getSingleHierarchicalPredecessor())3.82k
&&
178
3.82k
        
SingleHPred->getExitBasicBlock() == PrevVPBB2.87k
&&
179
3.82k
        
PrevVPBB->getSingleHierarchicalSuccessor()2.25k
) && /* B */
180
20.8k
      
!(2.53k
Replica2.53k
&&
getPredecessors().empty()1.86k
)) { /* C */
181
1.91k
    NewBB = createEmptyBasicBlock(State->CFG);
182
1.91k
    State->Builder.SetInsertPoint(NewBB);
183
1.91k
    // Temporarily terminate with unreachable until CFG is rewired.
184
1.91k
    UnreachableInst *Terminator = State->Builder.CreateUnreachable();
185
1.91k
    State->Builder.SetInsertPoint(Terminator);
186
1.91k
    // Register NewBB in its loop. In innermost loops its the same for all BB's.
187
1.91k
    Loop *L = State->LI->getLoopFor(State->CFG.LastBB);
188
1.91k
    L->addBasicBlockToLoop(NewBB, *State->LI);
189
1.91k
    State->CFG.PrevBB = NewBB;
190
1.91k
  }
191
20.8k
192
20.8k
  // 2. Fill the IR basic block with IR instructions.
193
20.8k
  LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB:" << getName()
194
20.8k
                    << " in BB:" << NewBB->getName() << '\n');
195
20.8k
196
20.8k
  State->CFG.VPBB2IRBB[this] = NewBB;
197
20.8k
  State->CFG.PrevVPBB = this;
198
20.8k
199
20.8k
  for (VPRecipeBase &Recipe : Recipes)
200
99.9k
    Recipe.execute(*State);
201
20.8k
202
20.8k
  VPValue *CBV;
203
20.8k
  if (EnableVPlanNativePath && 
(CBV = getCondBit())23
) {
204
15
    Value *IRCBV = CBV->getUnderlyingValue();
205
15
    assert(IRCBV && "Unexpected null underlying value for condition bit");
206
15
207
15
    // Condition bit value in a VPBasicBlock is used as the branch selector. In
208
15
    // the VPlan-native path case, since all branches are uniform we generate a
209
15
    // branch instruction using the condition value from vector lane 0 and dummy
210
15
    // successors. The successors are fixed later when the successor blocks are
211
15
    // visited.
212
15
    Value *NewCond = State->Callback.getOrCreateVectorValues(IRCBV, 0);
213
15
    NewCond = State->Builder.CreateExtractElement(NewCond,
214
15
                                                  State->Builder.getInt32(0));
215
15
216
15
    // Replace the temporary unreachable terminator with the new conditional
217
15
    // branch.
218
15
    auto *CurrentTerminator = NewBB->getTerminator();
219
15
    assert(isa<UnreachableInst>(CurrentTerminator) &&
220
15
           "Expected to replace unreachable terminator with conditional "
221
15
           "branch.");
222
15
    auto *CondBr = BranchInst::Create(NewBB, nullptr, NewCond);
223
15
    CondBr->setSuccessor(0, nullptr);
224
15
    ReplaceInstWithInst(CurrentTerminator, CondBr);
225
15
  }
226
20.8k
227
20.8k
  LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB);
228
20.8k
}
229
230
332
void VPRegionBlock::execute(VPTransformState *State) {
231
332
  ReversePostOrderTraversal<VPBlockBase *> RPOT(Entry);
232
332
233
332
  if (!isReplicator()) {
234
7
    // Visit the VPBlocks connected to "this", starting from it.
235
37
    for (VPBlockBase *Block : RPOT) {
236
37
      if (EnableVPlanNativePath) {
237
37
        // The inner loop vectorization path does not represent loop preheader
238
37
        // and exit blocks as part of the VPlan. In the VPlan-native path, skip
239
37
        // vectorizing loop preheader block. In future, we may replace this
240
37
        // check with the check for loop preheader.
241
37
        if (Block->getNumPredecessors() == 0)
242
7
          continue;
243
30
244
30
        // Skip vectorizing loop exit block. In future, we may replace this
245
30
        // check with the check for loop exit.
246
30
        if (Block->getNumSuccessors() == 0)
247
7
          continue;
248
23
      }
249
23
250
23
      LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
251
23
      Block->execute(State);
252
23
    }
253
7
    return;
254
7
  }
255
325
256
325
  assert(!State->Instance && "Replicating a Region with non-null instance.");
257
325
258
325
  // Enter replicating mode.
259
325
  State->Instance = {0, 0};
260
325
261
891
  for (unsigned Part = 0, UF = State->UF; Part < UF; 
++Part566
) {
262
566
    State->Instance->Part = Part;
263
1.51k
    for (unsigned Lane = 0, VF = State->VF; Lane < VF; 
++Lane948
) {
264
948
      State->Instance->Lane = Lane;
265
948
      // Visit the VPBlocks connected to \p this, starting from it.
266
2.84k
      for (VPBlockBase *Block : RPOT) {
267
2.84k
        LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
268
2.84k
        Block->execute(State);
269
2.84k
      }
270
948
    }
271
566
  }
272
325
273
325
  // Exit replicating mode.
274
325
  State->Instance.reset();
275
325
}
276
277
81
void VPRecipeBase::insertBefore(VPRecipeBase *InsertPos) {
278
81
  Parent = InsertPos->getParent();
279
81
  Parent->getRecipeList().insert(InsertPos->getIterator(), this);
280
81
}
281
282
110
iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() {
283
110
  return getParent()->getRecipeList().erase(getIterator());
284
110
}
285
286
void VPInstruction::generateInstruction(VPTransformState &State,
287
495
                                        unsigned Part) {
288
495
  IRBuilder<> &Builder = State.Builder;
289
495
290
495
  if (Instruction::isBinaryOp(getOpcode())) {
291
142
    Value *A = State.get(getOperand(0), Part);
292
142
    Value *B = State.get(getOperand(1), Part);
293
142
    Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B);
294
142
    State.set(this, V, Part);
295
142
    return;
296
142
  }
297
353
298
353
  switch (getOpcode()) {
299
353
  case VPInstruction::Not: {
300
335
    Value *A = State.get(getOperand(0), Part);
301
335
    Value *V = Builder.CreateNot(A);
302
335
    State.set(this, V, Part);
303
335
    break;
304
353
  }
305
353
  case VPInstruction::ICmpULE: {
306
18
    Value *IV = State.get(getOperand(0), Part);
307
18
    Value *TC = State.get(getOperand(1), Part);
308
18
    Value *V = Builder.CreateICmpULE(IV, TC);
309
18
    State.set(this, V, Part);
310
18
    break;
311
353
  }
312
353
  default:
313
0
    llvm_unreachable("Unsupported opcode for instruction");
314
353
  }
315
353
}
316
317
288
void VPInstruction::execute(VPTransformState &State) {
318
288
  assert(!State.Instance && "VPInstruction executing an Instance");
319
783
  for (unsigned Part = 0; Part < State.UF; 
++Part495
)
320
495
    generateInstruction(State, Part);
321
288
}
322
323
0
void VPInstruction::print(raw_ostream &O, const Twine &Indent) const {
324
0
  O << " +\n" << Indent << "\"EMIT ";
325
0
  print(O);
326
0
  O << "\\l\"";
327
0
}
328
329
0
void VPInstruction::print(raw_ostream &O) const {
330
0
  printAsOperand(O);
331
0
  O << " = ";
332
0
333
0
  switch (getOpcode()) {
334
0
  case VPInstruction::Not:
335
0
    O << "not";
336
0
    break;
337
0
  case VPInstruction::ICmpULE:
338
0
    O << "icmp ule";
339
0
    break;
340
0
  case VPInstruction::SLPLoad:
341
0
    O << "combined load";
342
0
    break;
343
0
  case VPInstruction::SLPStore:
344
0
    O << "combined store";
345
0
    break;
346
0
  default:
347
0
    O << Instruction::getOpcodeName(getOpcode());
348
0
  }
349
0
350
0
  for (const VPValue *Operand : operands()) {
351
0
    O << " ";
352
0
    Operand->printAsOperand(O);
353
0
  }
354
0
}
355
356
/// Generate the code inside the body of the vectorized loop. Assumes a single
357
/// LoopVectorBody basic-block was created for this. Introduce additional
358
/// basic-blocks as needed, and fill them all.
359
17.0k
void VPlan::execute(VPTransformState *State) {
360
17.0k
  // -1. Check if the backedge taken count is needed, and if so build it.
361
17.0k
  if (BackedgeTakenCount && 
BackedgeTakenCount->getNumUsers()18
) {
362
18
    Value *TC = State->TripCount;
363
18
    IRBuilder<> Builder(State->CFG.PrevBB->getTerminator());
364
18
    auto *TCMO = Builder.CreateSub(TC, ConstantInt::get(TC->getType(), 1),
365
18
                                   "trip.count.minus.1");
366
18
    Value2VPValue[TCMO] = BackedgeTakenCount;
367
18
  }
368
17.0k
369
17.0k
  // 0. Set the reverse mapping from VPValues to Values for code generation.
370
17.0k
  for (auto &Entry : Value2VPValue)
371
356
    State->VPValue2Value[Entry.second] = Entry.first;
372
17.0k
373
17.0k
  BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
374
17.0k
  BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
375
17.0k
  assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
376
17.0k
377
17.0k
  // 1. Make room to generate basic-blocks inside loop body if needed.
378
17.0k
  BasicBlock *VectorLatchBB = VectorHeaderBB->splitBasicBlock(
379
17.0k
      VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch");
380
17.0k
  Loop *L = State->LI->getLoopFor(VectorHeaderBB);
381
17.0k
  L->addBasicBlockToLoop(VectorLatchBB, *State->LI);
382
17.0k
  // Remove the edge between Header and Latch to allow other connections.
383
17.0k
  // Temporarily terminate with unreachable until CFG is rewired.
384
17.0k
  // Note: this asserts the generated code's assumption that
385
17.0k
  // getFirstInsertionPt() can be dereferenced into an Instruction.
386
17.0k
  VectorHeaderBB->getTerminator()->eraseFromParent();
387
17.0k
  State->Builder.SetInsertPoint(VectorHeaderBB);
388
17.0k
  UnreachableInst *Terminator = State->Builder.CreateUnreachable();
389
17.0k
  State->Builder.SetInsertPoint(Terminator);
390
17.0k
391
17.0k
  // 2. Generate code in loop body.
392
17.0k
  State->CFG.PrevVPBB = nullptr;
393
17.0k
  State->CFG.PrevBB = VectorHeaderBB;
394
17.0k
  State->CFG.LastBB = VectorLatchBB;
395
17.0k
396
17.0k
  for (VPBlockBase *Block : depth_first(Entry))
397
18.3k
    Block->execute(State);
398
17.0k
399
17.0k
  // Setup branch terminator successors for VPBBs in VPBBsToFix based on
400
17.0k
  // VPBB's successors.
401
17.0k
  for (auto VPBB : State->CFG.VPBBsToFix) {
402
7
    assert(EnableVPlanNativePath &&
403
7
           "Unexpected VPBBsToFix in non VPlan-native path");
404
7
    BasicBlock *BB = State->CFG.VPBB2IRBB[VPBB];
405
7
    assert(BB && "Unexpected null basic block for VPBB");
406
7
407
7
    unsigned Idx = 0;
408
7
    auto *BBTerminator = BB->getTerminator();
409
7
410
14
    for (VPBlockBase *SuccVPBlock : VPBB->getHierarchicalSuccessors()) {
411
14
      VPBasicBlock *SuccVPBB = SuccVPBlock->getEntryBasicBlock();
412
14
      BBTerminator->setSuccessor(Idx, State->CFG.VPBB2IRBB[SuccVPBB]);
413
14
      ++Idx;
414
14
    }
415
7
  }
416
17.0k
417
17.0k
  // 3. Merge the temporary latch created with the last basic-block filled.
418
17.0k
  BasicBlock *LastBB = State->CFG.PrevBB;
419
17.0k
  // Connect LastBB to VectorLatchBB to facilitate their merge.
420
17.0k
  assert((EnableVPlanNativePath ||
421
17.0k
          isa<UnreachableInst>(LastBB->getTerminator())) &&
422
17.0k
         "Expected InnerLoop VPlan CFG to terminate with unreachable");
423
17.0k
  assert((!EnableVPlanNativePath || isa<BranchInst>(LastBB->getTerminator())) &&
424
17.0k
         "Expected VPlan CFG to terminate with branch in NativePath");
425
17.0k
  LastBB->getTerminator()->eraseFromParent();
426
17.0k
  BranchInst::Create(VectorLatchBB, LastBB);
427
17.0k
428
17.0k
  // Merge LastBB with Latch.
429
17.0k
  bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI);
430
17.0k
  (void)Merged;
431
17.0k
  assert(Merged && "Could not merge last basic block with latch.");
432
17.0k
  VectorLatchBB = LastBB;
433
17.0k
434
17.0k
  // We do not attempt to preserve DT for outer loop vectorization currently.
435
17.0k
  if (!EnableVPlanNativePath)
436
17.0k
    updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB);
437
17.0k
}
438
439
void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
440
17.0k
                                BasicBlock *LoopLatchBB) {
441
17.0k
  BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor();
442
17.0k
  assert(LoopHeaderBB && "Loop preheader does not have a single successor.");
443
17.0k
  DT->addNewBlock(LoopHeaderBB, LoopPreHeaderBB);
444
17.0k
  // The vector body may be more than a single basic-block by this point.
445
17.0k
  // Update the dominator tree information inside the vector body by propagating
446
17.0k
  // it from header to latch, expecting only triangular control-flow, if any.
447
17.0k
  BasicBlock *PostDomSucc = nullptr;
448
18.0k
  for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; 
BB = PostDomSucc948
) {
449
948
    // Get the list of successors of this block.
450
948
    std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
451
948
    assert(Succs.size() <= 2 &&
452
948
           "Basic block in vector loop has more than 2 successors.");
453
948
    PostDomSucc = Succs[0];
454
948
    if (Succs.size() == 1) {
455
0
      assert(PostDomSucc->getSinglePredecessor() &&
456
0
             "PostDom successor has more than one predecessor.");
457
0
      DT->addNewBlock(PostDomSucc, BB);
458
0
      continue;
459
0
    }
460
948
    BasicBlock *InterimSucc = Succs[1];
461
948
    if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
462
948
      PostDomSucc = Succs[1];
463
948
      InterimSucc = Succs[0];
464
948
    }
465
948
    assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
466
948
           "One successor of a basic block does not lead to the other.");
467
948
    assert(InterimSucc->getSinglePredecessor() &&
468
948
           "Interim successor has more than one predecessor.");
469
948
    assert(PostDomSucc->hasNPredecessors(2) &&
470
948
           "PostDom successor has more than two predecessors.");
471
948
    DT->addNewBlock(InterimSucc, BB);
472
948
    DT->addNewBlock(PostDomSucc, BB);
473
948
  }
474
17.0k
}
475
476
0
const Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
477
0
  return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
478
0
         Twine(getOrCreateBID(Block));
479
0
}
480
481
0
const Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
482
0
  const std::string &Name = Block->getName();
483
0
  if (!Name.empty())
484
0
    return Name;
485
0
  return "VPB" + Twine(getOrCreateBID(Block));
486
0
}
487
488
0
void VPlanPrinter::dump() {
489
0
  Depth = 1;
490
0
  bumpIndent(0);
491
0
  OS << "digraph VPlan {\n";
492
0
  OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
493
0
  if (!Plan.getName().empty())
494
0
    OS << "\\n" << DOT::EscapeString(Plan.getName());
495
0
  if (!Plan.Value2VPValue.empty() || Plan.BackedgeTakenCount) {
496
0
    OS << ", where:";
497
0
    if (Plan.BackedgeTakenCount)
498
0
      OS << "\\n"
499
0
         << *Plan.getOrCreateBackedgeTakenCount() << " := BackedgeTakenCount";
500
0
    for (auto Entry : Plan.Value2VPValue) {
501
0
      OS << "\\n" << *Entry.second;
502
0
      OS << DOT::EscapeString(" := ");
503
0
      Entry.first->printAsOperand(OS, false);
504
0
    }
505
0
  }
506
0
  OS << "\"]\n";
507
0
  OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
508
0
  OS << "edge [fontname=Courier, fontsize=30]\n";
509
0
  OS << "compound=true\n";
510
0
511
0
  for (VPBlockBase *Block : depth_first(Plan.getEntry()))
512
0
    dumpBlock(Block);
513
0
514
0
  OS << "}\n";
515
0
}
516
517
0
void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
518
0
  if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
519
0
    dumpBasicBlock(BasicBlock);
520
0
  else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
521
0
    dumpRegion(Region);
522
0
  else
523
0
    llvm_unreachable("Unsupported kind of VPBlock.");
524
0
}
525
526
void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
527
0
                            bool Hidden, const Twine &Label) {
528
0
  // Due to "dot" we print an edge between two regions as an edge between the
529
0
  // exit basic block and the entry basic of the respective regions.
530
0
  const VPBlockBase *Tail = From->getExitBasicBlock();
531
0
  const VPBlockBase *Head = To->getEntryBasicBlock();
532
0
  OS << Indent << getUID(Tail) << " -> " << getUID(Head);
533
0
  OS << " [ label=\"" << Label << '\"';
534
0
  if (Tail != From)
535
0
    OS << " ltail=" << getUID(From);
536
0
  if (Head != To)
537
0
    OS << " lhead=" << getUID(To);
538
0
  if (Hidden)
539
0
    OS << "; splines=none";
540
0
  OS << "]\n";
541
0
}
542
543
0
void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
544
0
  auto &Successors = Block->getSuccessors();
545
0
  if (Successors.size() == 1)
546
0
    drawEdge(Block, Successors.front(), false, "");
547
0
  else if (Successors.size() == 2) {
548
0
    drawEdge(Block, Successors.front(), false, "T");
549
0
    drawEdge(Block, Successors.back(), false, "F");
550
0
  } else {
551
0
    unsigned SuccessorNumber = 0;
552
0
    for (auto *Successor : Successors)
553
0
      drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
554
0
  }
555
0
}
556
557
0
void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
558
0
  OS << Indent << getUID(BasicBlock) << " [label =\n";
559
0
  bumpIndent(1);
560
0
  OS << Indent << "\"" << DOT::EscapeString(BasicBlock->getName()) << ":\\n\"";
561
0
  bumpIndent(1);
562
0
563
0
  // Dump the block predicate.
564
0
  const VPValue *Pred = BasicBlock->getPredicate();
565
0
  if (Pred) {
566
0
    OS << " +\n" << Indent << " \"BlockPredicate: ";
567
0
    if (const VPInstruction *PredI = dyn_cast<VPInstruction>(Pred)) {
568
0
      PredI->printAsOperand(OS);
569
0
      OS << " (" << DOT::EscapeString(PredI->getParent()->getName())
570
0
         << ")\\l\"";
571
0
    } else
572
0
      Pred->printAsOperand(OS);
573
0
  }
574
0
575
0
  for (const VPRecipeBase &Recipe : *BasicBlock)
576
0
    Recipe.print(OS, Indent);
577
0
578
0
  // Dump the condition bit.
579
0
  const VPValue *CBV = BasicBlock->getCondBit();
580
0
  if (CBV) {
581
0
    OS << " +\n" << Indent << " \"CondBit: ";
582
0
    if (const VPInstruction *CBI = dyn_cast<VPInstruction>(CBV)) {
583
0
      CBI->printAsOperand(OS);
584
0
      OS << " (" << DOT::EscapeString(CBI->getParent()->getName()) << ")\\l\"";
585
0
    } else {
586
0
      CBV->printAsOperand(OS);
587
0
      OS << "\"";
588
0
    }
589
0
  }
590
0
591
0
  bumpIndent(-2);
592
0
  OS << "\n" << Indent << "]\n";
593
0
  dumpEdges(BasicBlock);
594
0
}
595
596
0
void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
597
0
  OS << Indent << "subgraph " << getUID(Region) << " {\n";
598
0
  bumpIndent(1);
599
0
  OS << Indent << "fontname=Courier\n"
600
0
     << Indent << "label=\""
601
0
     << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
602
0
     << DOT::EscapeString(Region->getName()) << "\"\n";
603
0
  // Dump the blocks of the region.
604
0
  assert(Region->getEntry() && "Region contains no inner blocks.");
605
0
  for (const VPBlockBase *Block : depth_first(Region->getEntry()))
606
0
    dumpBlock(Block);
607
0
  bumpIndent(-1);
608
0
  OS << Indent << "}\n";
609
0
  dumpEdges(Region);
610
0
}
611
612
0
void VPlanPrinter::printAsIngredient(raw_ostream &O, Value *V) {
613
0
  std::string IngredientString;
614
0
  raw_string_ostream RSO(IngredientString);
615
0
  if (auto *Inst = dyn_cast<Instruction>(V)) {
616
0
    if (!Inst->getType()->isVoidTy()) {
617
0
      Inst->printAsOperand(RSO, false);
618
0
      RSO << " = ";
619
0
    }
620
0
    RSO << Inst->getOpcodeName() << " ";
621
0
    unsigned E = Inst->getNumOperands();
622
0
    if (E > 0) {
623
0
      Inst->getOperand(0)->printAsOperand(RSO, false);
624
0
      for (unsigned I = 1; I < E; ++I)
625
0
        Inst->getOperand(I)->printAsOperand(RSO << ", ", false);
626
0
    }
627
0
  } else // !Inst
628
0
    V->printAsOperand(RSO, false);
629
0
  RSO.flush();
630
0
  O << DOT::EscapeString(IngredientString);
631
0
}
632
633
0
void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent) const {
634
0
  O << " +\n" << Indent << "\"WIDEN\\l\"";
635
0
  for (auto &Instr : make_range(Begin, End))
636
0
    O << " +\n" << Indent << "\"  " << VPlanIngredient(&Instr) << "\\l\"";
637
0
}
638
639
void VPWidenIntOrFpInductionRecipe::print(raw_ostream &O,
640
0
                                          const Twine &Indent) const {
641
0
  O << " +\n" << Indent << "\"WIDEN-INDUCTION";
642
0
  if (Trunc) {
643
0
    O << "\\l\"";
644
0
    O << " +\n" << Indent << "\"  " << VPlanIngredient(IV) << "\\l\"";
645
0
    O << " +\n" << Indent << "\"  " << VPlanIngredient(Trunc) << "\\l\"";
646
0
  } else
647
0
    O << " " << VPlanIngredient(IV) << "\\l\"";
648
0
}
649
650
0
void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
651
0
  O << " +\n" << Indent << "\"WIDEN-PHI " << VPlanIngredient(Phi) << "\\l\"";
652
0
}
653
654
0
void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent) const {
655
0
  O << " +\n" << Indent << "\"BLEND ";
656
0
  Phi->printAsOperand(O, false);
657
0
  O << " =";
658
0
  if (!User) {
659
0
    // Not a User of any mask: not really blending, this is a
660
0
    // single-predecessor phi.
661
0
    O << " ";
662
0
    Phi->getIncomingValue(0)->printAsOperand(O, false);
663
0
  } else {
664
0
    for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) {
665
0
      O << " ";
666
0
      Phi->getIncomingValue(I)->printAsOperand(O, false);
667
0
      O << "/";
668
0
      User->getOperand(I)->printAsOperand(O);
669
0
    }
670
0
  }
671
0
  O << "\\l\"";
672
0
}
673
674
0
void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent) const {
675
0
  O << " +\n"
676
0
    << Indent << "\"" << (IsUniform ? "CLONE " : "REPLICATE ")
677
0
    << VPlanIngredient(Ingredient);
678
0
  if (AlsoPack)
679
0
    O << " (S->V)";
680
0
  O << "\\l\"";
681
0
}
682
683
0
void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
684
0
  O << " +\n"
685
0
    << Indent << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst)
686
0
    << "\\l\"";
687
0
}
688
689
void VPWidenMemoryInstructionRecipe::print(raw_ostream &O,
690
0
                                           const Twine &Indent) const {
691
0
  O << " +\n" << Indent << "\"WIDEN " << VPlanIngredient(&Instr);
692
0
  if (User) {
693
0
    O << ", ";
694
0
    User->getOperand(0)->printAsOperand(O);
695
0
  }
696
0
  O << "\\l\"";
697
0
}
698
699
template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
700
701
34
void VPValue::replaceAllUsesWith(VPValue *New) {
702
34
  for (VPUser *User : users())
703
0
    for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I)
704
0
      if (User->getOperand(I) == this)
705
0
        User->setOperand(I, New);
706
34
}
707
708
void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region,
709
                                          Old2NewTy &Old2New,
710
12
                                          InterleavedAccessInfo &IAI) {
711
12
  ReversePostOrderTraversal<VPBlockBase *> RPOT(Region->getEntry());
712
38
  for (VPBlockBase *Base : RPOT) {
713
38
    visitBlock(Base, Old2New, IAI);
714
38
  }
715
12
}
716
717
void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
718
38
                                         InterleavedAccessInfo &IAI) {
719
38
  if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) {
720
256
    for (VPRecipeBase &VPI : *VPBB) {
721
256
      assert(isa<VPInstruction>(&VPI) && "Can only handle VPInstructions");
722
256
      auto *VPInst = cast<VPInstruction>(&VPI);
723
256
      auto *Inst = cast<Instruction>(VPInst->getUnderlyingValue());
724
256
      auto *IG = IAI.getInterleaveGroup(Inst);
725
256
      if (!IG)
726
175
        continue;
727
81
728
81
      auto NewIGIter = Old2New.find(IG);
729
81
      if (NewIGIter == Old2New.end())
730
41
        Old2New[IG] = new InterleaveGroup<VPInstruction>(
731
41
            IG->getFactor(), IG->isReverse(), IG->getAlignment());
732
81
733
81
      if (Inst == IG->getInsertPos())
734
41
        Old2New[IG]->setInsertPos(VPInst);
735
81
736
81
      InterleaveGroupMap[VPInst] = Old2New[IG];
737
81
      InterleaveGroupMap[VPInst]->insertMember(
738
81
          VPInst, IG->getIndex(Inst),
739
81
          IG->isReverse() ? 
(-1) * int(IG->getFactor())0
: IG->getFactor());
740
81
    }
741
38
  } else 
if (VPRegionBlock *0
Region0
= dyn_cast<VPRegionBlock>(Block))
742
0
    visitRegion(Region, Old2New, IAI);
743
0
  else
744
0
    llvm_unreachable("Unsupported kind of VPBlock.");
745
38
}
746
747
VPInterleavedAccessInfo::VPInterleavedAccessInfo(VPlan &Plan,
748
12
                                                 InterleavedAccessInfo &IAI) {
749
12
  Old2NewTy Old2New;
750
12
  visitRegion(cast<VPRegionBlock>(Plan.getEntry()), Old2New, IAI);
751
12
}