Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- VPlanHCFGBuilder.cpp ----------------------------------------------===//
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 file implements the construction of a VPlan-based Hierarchical CFG
11
/// (H-CFG) for an incoming IR. This construction comprises the following
12
/// components and steps:
13
//
14
/// 1. PlainCFGBuilder class: builds a plain VPBasicBlock-based CFG that
15
/// faithfully represents the CFG in the incoming IR. A VPRegionBlock (Top
16
/// Region) is created to enclose and serve as parent of all the VPBasicBlocks
17
/// in the plain CFG.
18
/// NOTE: At this point, there is a direct correspondence between all the
19
/// VPBasicBlocks created for the initial plain CFG and the incoming
20
/// BasicBlocks. However, this might change in the future.
21
///
22
//===----------------------------------------------------------------------===//
23
24
#include "VPlanHCFGBuilder.h"
25
#include "LoopVectorizationPlanner.h"
26
#include "llvm/Analysis/LoopIterator.h"
27
28
#define DEBUG_TYPE "loop-vectorize"
29
30
using namespace llvm;
31
32
namespace {
33
// Class that is used to build the plain CFG for the incoming IR.
34
class PlainCFGBuilder {
35
private:
36
  // The outermost loop of the input loop nest considered for vectorization.
37
  Loop *TheLoop;
38
39
  // Loop Info analysis.
40
  LoopInfo *LI;
41
42
  // Vectorization plan that we are working on.
43
  VPlan &Plan;
44
45
  // Output Top Region.
46
  VPRegionBlock *TopRegion = nullptr;
47
48
  // Builder of the VPlan instruction-level representation.
49
  VPBuilder VPIRBuilder;
50
51
  // NOTE: The following maps are intentionally destroyed after the plain CFG
52
  // construction because subsequent VPlan-to-VPlan transformation may
53
  // invalidate them.
54
  // Map incoming BasicBlocks to their newly-created VPBasicBlocks.
55
  DenseMap<BasicBlock *, VPBasicBlock *> BB2VPBB;
56
  // Map incoming Value definitions to their newly-created VPValues.
57
  DenseMap<Value *, VPValue *> IRDef2VPValue;
58
59
  // Hold phi node's that need to be fixed once the plain CFG has been built.
60
  SmallVector<PHINode *, 8> PhisToFix;
61
62
  // Utility functions.
63
  void setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB);
64
  void fixPhiNodes();
65
  VPBasicBlock *getOrCreateVPBB(BasicBlock *BB);
66
#ifndef NDEBUG
67
  bool isExternalDef(Value *Val);
68
#endif
69
  VPValue *getOrCreateVPOperand(Value *IRVal);
70
  void createVPInstructionsForVPBB(VPBasicBlock *VPBB, BasicBlock *BB);
71
72
public:
73
  PlainCFGBuilder(Loop *Lp, LoopInfo *LI, VPlan &P)
74
25
      : TheLoop(Lp), LI(LI), Plan(P) {}
75
76
  // Build the plain CFG and return its Top Region.
77
  VPRegionBlock *buildPlainCFG();
78
};
79
} // anonymous namespace
80
81
// Set predecessors of \p VPBB in the same order as they are in \p BB. \p VPBB
82
// must have no predecessors.
83
86
void PlainCFGBuilder::setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB) {
84
86
  SmallVector<VPBlockBase *, 8> VPBBPreds;
85
86
  // Collect VPBB predecessors.
86
86
  for (BasicBlock *Pred : predecessors(BB))
87
127
    VPBBPreds.push_back(getOrCreateVPBB(Pred));
88
86
89
86
  VPBB->setPredecessors(VPBBPreds);
90
86
}
91
92
// Add operands to VPInstructions representing phi nodes from the input IR.
93
25
void PlainCFGBuilder::fixPhiNodes() {
94
36
  for (auto *Phi : PhisToFix) {
95
36
    assert(IRDef2VPValue.count(Phi) && "Missing VPInstruction for PHINode.");
96
36
    VPValue *VPVal = IRDef2VPValue[Phi];
97
36
    assert(isa<VPInstruction>(VPVal) && "Expected VPInstruction for phi node.");
98
36
    auto *VPPhi = cast<VPInstruction>(VPVal);
99
36
    assert(VPPhi->getNumOperands() == 0 &&
100
36
           "Expected VPInstruction with no operands.");
101
36
102
36
    for (Value *Op : Phi->operands())
103
71
      VPPhi->addOperand(getOrCreateVPOperand(Op));
104
36
  }
105
25
}
106
107
// Create a new empty VPBasicBlock for an incoming BasicBlock or retrieve an
108
// existing one if it was already created.
109
340
VPBasicBlock *PlainCFGBuilder::getOrCreateVPBB(BasicBlock *BB) {
110
340
  auto BlockIt = BB2VPBB.find(BB);
111
340
  if (BlockIt != BB2VPBB.end())
112
229
    // Retrieve existing VPBB.
113
229
    return BlockIt->second;
114
111
115
111
  // Create new VPBB.
116
111
  LLVM_DEBUG(dbgs() << "Creating VPBasicBlock for " << BB->getName() << "\n");
117
111
  VPBasicBlock *VPBB = new VPBasicBlock(BB->getName());
118
111
  BB2VPBB[BB] = VPBB;
119
111
  VPBB->setParent(TopRegion);
120
111
  return VPBB;
121
111
}
122
123
#ifndef NDEBUG
124
// Return true if \p Val is considered an external definition. An external
125
// definition is either:
126
// 1. A Value that is not an Instruction. This will be refined in the future.
127
// 2. An Instruction that is outside of the CFG snippet represented in VPlan,
128
// i.e., is not part of: a) the loop nest, b) outermost loop PH and, c)
129
// outermost loop exits.
130
bool PlainCFGBuilder::isExternalDef(Value *Val) {
131
  // All the Values that are not Instructions are considered external
132
  // definitions for now.
133
  Instruction *Inst = dyn_cast<Instruction>(Val);
134
  if (!Inst)
135
    return true;
136
137
  BasicBlock *InstParent = Inst->getParent();
138
  assert(InstParent && "Expected instruction parent.");
139
140
  // Check whether Instruction definition is in loop PH.
141
  BasicBlock *PH = TheLoop->getLoopPreheader();
142
  assert(PH && "Expected loop pre-header.");
143
144
  if (InstParent == PH)
145
    // Instruction definition is in outermost loop PH.
146
    return false;
147
148
  // Check whether Instruction definition is in the loop exit.
149
  BasicBlock *Exit = TheLoop->getUniqueExitBlock();
150
  assert(Exit && "Expected loop with single exit.");
151
  if (InstParent == Exit) {
152
    // Instruction definition is in outermost loop exit.
153
    return false;
154
  }
155
156
  // Check whether Instruction definition is in loop body.
157
  return !TheLoop->contains(Inst);
158
}
159
#endif
160
161
// Create a new VPValue or retrieve an existing one for the Instruction's
162
// operand \p IRVal. This function must only be used to create/retrieve VPValues
163
// for *Instruction's operands* and not to create regular VPInstruction's. For
164
// the latter, please, look at 'createVPInstructionsForVPBB'.
165
861
VPValue *PlainCFGBuilder::getOrCreateVPOperand(Value *IRVal) {
166
861
  auto VPValIt = IRDef2VPValue.find(IRVal);
167
861
  if (VPValIt != IRDef2VPValue.end())
168
679
    // Operand has an associated VPInstruction or VPValue that was previously
169
679
    // created.
170
679
    return VPValIt->second;
171
182
172
182
  // Operand doesn't have a previously created VPInstruction/VPValue. This
173
182
  // means that operand is:
174
182
  //   A) a definition external to VPlan,
175
182
  //   B) any other Value without specific representation in VPlan.
176
182
  // For now, we use VPValue to represent A and B and classify both as external
177
182
  // definitions. We may introduce specific VPValue subclasses for them in the
178
182
  // future.
179
182
  assert(isExternalDef(IRVal) && "Expected external definition as operand.");
180
182
181
182
  // A and B: Create VPValue and add it to the pool of external definitions and
182
182
  // to the Value->VPValue map.
183
182
  VPValue *NewVPVal = new VPValue(IRVal);
184
182
  Plan.addExternalDef(NewVPVal);
185
182
  IRDef2VPValue[IRVal] = NewVPVal;
186
182
  return NewVPVal;
187
182
}
188
189
// Create new VPInstructions in a VPBasicBlock, given its BasicBlock
190
// counterpart. This function must be invoked in RPO so that the operands of a
191
// VPInstruction in \p BB have been visited before (except for Phi nodes).
192
void PlainCFGBuilder::createVPInstructionsForVPBB(VPBasicBlock *VPBB,
193
111
                                                  BasicBlock *BB) {
194
111
  VPIRBuilder.setInsertPoint(VPBB);
195
503
  for (Instruction &InstRef : *BB) {
196
503
    Instruction *Inst = &InstRef;
197
503
198
503
    // There shouldn't be any VPValue for Inst at this point. Otherwise, we
199
503
    // visited Inst when we shouldn't, breaking the RPO traversal order.
200
503
    assert(!IRDef2VPValue.count(Inst) &&
201
503
           "Instruction shouldn't have been visited.");
202
503
203
503
    if (auto *Br = dyn_cast<BranchInst>(Inst)) {
204
87
      // Branch instruction is not explicitly represented in VPlan but we need
205
87
      // to represent its condition bit when it's conditional.
206
87
      if (Br->isConditional())
207
41
        getOrCreateVPOperand(Br->getCondition());
208
87
209
87
      // Skip the rest of the Instruction processing for Branch instructions.
210
87
      continue;
211
87
    }
212
416
213
416
    VPInstruction *NewVPInst;
214
416
    if (auto *Phi = dyn_cast<PHINode>(Inst)) {
215
36
      // Phi node's operands may have not been visited at this point. We create
216
36
      // an empty VPInstruction that we will fix once the whole plain CFG has
217
36
      // been built.
218
36
      NewVPInst = cast<VPInstruction>(VPIRBuilder.createNaryOp(
219
36
          Inst->getOpcode(), {} /*No operands*/, Inst));
220
36
      PhisToFix.push_back(Phi);
221
380
    } else {
222
380
      // Translate LLVM-IR operands into VPValue operands and set them in the
223
380
      // new VPInstruction.
224
380
      SmallVector<VPValue *, 4> VPOperands;
225
380
      for (Value *Op : Inst->operands())
226
749
        VPOperands.push_back(getOrCreateVPOperand(Op));
227
380
228
380
      // Build VPInstruction for any arbitraty Instruction without specific
229
380
      // representation in VPlan.
230
380
      NewVPInst = cast<VPInstruction>(
231
380
          VPIRBuilder.createNaryOp(Inst->getOpcode(), VPOperands, Inst));
232
380
    }
233
416
234
416
    IRDef2VPValue[Inst] = NewVPInst;
235
416
  }
236
111
}
237
238
// Main interface to build the plain CFG.
239
25
VPRegionBlock *PlainCFGBuilder::buildPlainCFG() {
240
25
  // 1. Create the Top Region. It will be the parent of all VPBBs.
241
25
  TopRegion = new VPRegionBlock("TopRegion", false /*isReplicator*/);
242
25
243
25
  // 2. Scan the body of the loop in a topological order to visit each basic
244
25
  // block after having visited its predecessor basic blocks. Create a VPBB for
245
25
  // each BB and link it to its successor and predecessor VPBBs. Note that
246
25
  // predecessors must be set in the same order as they are in the incomming IR.
247
25
  // Otherwise, there might be problems with existing phi nodes and algorithm
248
25
  // based on predecessors traversal.
249
25
250
25
  // Loop PH needs to be explicitly visited since it's not taken into account by
251
25
  // LoopBlocksDFS.
252
25
  BasicBlock *PreheaderBB = TheLoop->getLoopPreheader();
253
25
  assert((PreheaderBB->getTerminator()->getNumSuccessors() == 1) &&
254
25
         "Unexpected loop preheader");
255
25
  VPBasicBlock *PreheaderVPBB = getOrCreateVPBB(PreheaderBB);
256
25
  createVPInstructionsForVPBB(PreheaderVPBB, PreheaderBB);
257
25
  // Create empty VPBB for Loop H so that we can link PH->H.
258
25
  VPBlockBase *HeaderVPBB = getOrCreateVPBB(TheLoop->getHeader());
259
25
  // Preheader's predecessors will be set during the loop RPO traversal below.
260
25
  PreheaderVPBB->setOneSuccessor(HeaderVPBB);
261
25
262
25
  LoopBlocksRPO RPO(TheLoop);
263
25
  RPO.perform(LI);
264
25
265
61
  for (BasicBlock *BB : RPO) {
266
61
    // Create or retrieve the VPBasicBlock for this BB and create its
267
61
    // VPInstructions.
268
61
    VPBasicBlock *VPBB = getOrCreateVPBB(BB);
269
61
    createVPInstructionsForVPBB(VPBB, BB);
270
61
271
61
    // Set VPBB successors. We create empty VPBBs for successors if they don't
272
61
    // exist already. Recipes will be created when the successor is visited
273
61
    // during the RPO traversal.
274
61
    Instruction *TI = BB->getTerminator();
275
61
    assert(TI && "Terminator expected.");
276
61
    unsigned NumSuccs = TI->getNumSuccessors();
277
61
278
61
    if (NumSuccs == 1) {
279
20
      VPBasicBlock *SuccVPBB = getOrCreateVPBB(TI->getSuccessor(0));
280
20
      assert(SuccVPBB && "VPBB Successor not found.");
281
20
      VPBB->setOneSuccessor(SuccVPBB);
282
41
    } else if (NumSuccs == 2) {
283
41
      VPBasicBlock *SuccVPBB0 = getOrCreateVPBB(TI->getSuccessor(0));
284
41
      assert(SuccVPBB0 && "Successor 0 not found.");
285
41
      VPBasicBlock *SuccVPBB1 = getOrCreateVPBB(TI->getSuccessor(1));
286
41
      assert(SuccVPBB1 && "Successor 1 not found.");
287
41
288
41
      // Get VPBB's condition bit.
289
41
      assert(isa<BranchInst>(TI) && "Unsupported terminator!");
290
41
      auto *Br = cast<BranchInst>(TI);
291
41
      Value *BrCond = Br->getCondition();
292
41
      // Look up the branch condition to get the corresponding VPValue
293
41
      // representing the condition bit in VPlan (which may be in another VPBB).
294
41
      assert(IRDef2VPValue.count(BrCond) &&
295
41
             "Missing condition bit in IRDef2VPValue!");
296
41
      VPValue *VPCondBit = IRDef2VPValue[BrCond];
297
41
298
41
      // Link successors using condition bit.
299
41
      VPBB->setTwoSuccessors(SuccVPBB0, SuccVPBB1, VPCondBit);
300
41
    } else
301
41
      
llvm_unreachable0
("Number of successors not supported.");
302
61
303
61
    // Set VPBB predecessors in the same order as they are in the incoming BB.
304
61
    setVPBBPredsFromBB(VPBB, BB);
305
61
  }
306
25
307
25
  // 3. Process outermost loop exit. We created an empty VPBB for the loop
308
25
  // single exit BB during the RPO traversal of the loop body but Instructions
309
25
  // weren't visited because it's not part of the the loop.
310
25
  BasicBlock *LoopExitBB = TheLoop->getUniqueExitBlock();
311
25
  assert(LoopExitBB && "Loops with multiple exits are not supported.");
312
25
  VPBasicBlock *LoopExitVPBB = BB2VPBB[LoopExitBB];
313
25
  createVPInstructionsForVPBB(LoopExitVPBB, LoopExitBB);
314
25
  // Loop exit was already set as successor of the loop exiting BB.
315
25
  // We only set its predecessor VPBB now.
316
25
  setVPBBPredsFromBB(LoopExitVPBB, LoopExitBB);
317
25
318
25
  // 4. The whole CFG has been built at this point so all the input Values must
319
25
  // have a VPlan couterpart. Fix VPlan phi nodes by adding their corresponding
320
25
  // VPlan operands.
321
25
  fixPhiNodes();
322
25
323
25
  // 5. Final Top Region setup. Set outermost loop pre-header and single exit as
324
25
  // Top Region entry and exit.
325
25
  TopRegion->setEntry(PreheaderVPBB);
326
25
  TopRegion->setExit(LoopExitVPBB);
327
25
  return TopRegion;
328
25
}
329
330
25
VPRegionBlock *VPlanHCFGBuilder::buildPlainCFG() {
331
25
  PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan);
332
25
  return PCFGBuilder.buildPlainCFG();
333
25
}
334
335
// Public interface to build a H-CFG.
336
24
void VPlanHCFGBuilder::buildHierarchicalCFG() {
337
24
  // Build Top Region enclosing the plain CFG and set it as VPlan entry.
338
24
  VPRegionBlock *TopRegion = buildPlainCFG();
339
24
  Plan.setEntry(TopRegion);
340
24
  LLVM_DEBUG(Plan.setName("HCFGBuilder: Plain CFG\n"); dbgs() << Plan);
341
24
342
24
  Verifier.verifyHierarchicalCFG(TopRegion);
343
24
344
24
  // Compute plain CFG dom tree for VPLInfo.
345
24
  VPDomTree.recalculate(*TopRegion);
346
24
  LLVM_DEBUG(dbgs() << "Dominator Tree after building the plain CFG.\n";
347
24
             VPDomTree.print(dbgs()));
348
24
349
24
  // Compute VPLInfo and keep it in Plan.
350
24
  VPLoopInfo &VPLInfo = Plan.getVPLoopInfo();
351
24
  VPLInfo.analyze(VPDomTree);
352
24
  LLVM_DEBUG(dbgs() << "VPLoop Info After buildPlainCFG:\n";
353
24
             VPLInfo.print(dbgs()));
354
24
}