LLVM  9.0.0svn
VPlanHCFGBuilder.cpp
Go to the documentation of this file.
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"
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.
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  : 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 void PlainCFGBuilder::setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB) {
85  // Collect VPBB predecessors.
86  for (BasicBlock *Pred : predecessors(BB))
87  VPBBPreds.push_back(getOrCreateVPBB(Pred));
88 
89  VPBB->setPredecessors(VPBBPreds);
90 }
91 
92 // Add operands to VPInstructions representing phi nodes from the input IR.
93 void PlainCFGBuilder::fixPhiNodes() {
94  for (auto *Phi : PhisToFix) {
95  assert(IRDef2VPValue.count(Phi) && "Missing VPInstruction for PHINode.");
96  VPValue *VPVal = IRDef2VPValue[Phi];
97  assert(isa<VPInstruction>(VPVal) && "Expected VPInstruction for phi node.");
98  auto *VPPhi = cast<VPInstruction>(VPVal);
99  assert(VPPhi->getNumOperands() == 0 &&
100  "Expected VPInstruction with no operands.");
101 
102  for (Value *Op : Phi->operands())
103  VPPhi->addOperand(getOrCreateVPOperand(Op));
104  }
105 }
106 
107 // Create a new empty VPBasicBlock for an incoming BasicBlock or retrieve an
108 // existing one if it was already created.
109 VPBasicBlock *PlainCFGBuilder::getOrCreateVPBB(BasicBlock *BB) {
110  auto BlockIt = BB2VPBB.find(BB);
111  if (BlockIt != BB2VPBB.end())
112  // Retrieve existing VPBB.
113  return BlockIt->second;
114 
115  // Create new VPBB.
116  LLVM_DEBUG(dbgs() << "Creating VPBasicBlock for " << BB->getName() << "\n");
117  VPBasicBlock *VPBB = new VPBasicBlock(BB->getName());
118  BB2VPBB[BB] = VPBB;
119  VPBB->setParent(TopRegion);
120  return VPBB;
121 }
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 VPValue *PlainCFGBuilder::getOrCreateVPOperand(Value *IRVal) {
166  auto VPValIt = IRDef2VPValue.find(IRVal);
167  if (VPValIt != IRDef2VPValue.end())
168  // Operand has an associated VPInstruction or VPValue that was previously
169  // created.
170  return VPValIt->second;
171 
172  // Operand doesn't have a previously created VPInstruction/VPValue. This
173  // means that operand is:
174  // A) a definition external to VPlan,
175  // B) any other Value without specific representation in VPlan.
176  // For now, we use VPValue to represent A and B and classify both as external
177  // definitions. We may introduce specific VPValue subclasses for them in the
178  // future.
179  assert(isExternalDef(IRVal) && "Expected external definition as operand.");
180 
181  // A and B: Create VPValue and add it to the pool of external definitions and
182  // to the Value->VPValue map.
183  VPValue *NewVPVal = new VPValue(IRVal);
184  Plan.addExternalDef(NewVPVal);
185  IRDef2VPValue[IRVal] = NewVPVal;
186  return NewVPVal;
187 }
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  BasicBlock *BB) {
194  VPIRBuilder.setInsertPoint(VPBB);
195  for (Instruction &InstRef : *BB) {
196  Instruction *Inst = &InstRef;
197 
198  // There shouldn't be any VPValue for Inst at this point. Otherwise, we
199  // visited Inst when we shouldn't, breaking the RPO traversal order.
200  assert(!IRDef2VPValue.count(Inst) &&
201  "Instruction shouldn't have been visited.");
202 
203  if (auto *Br = dyn_cast<BranchInst>(Inst)) {
204  // Branch instruction is not explicitly represented in VPlan but we need
205  // to represent its condition bit when it's conditional.
206  if (Br->isConditional())
207  getOrCreateVPOperand(Br->getCondition());
208 
209  // Skip the rest of the Instruction processing for Branch instructions.
210  continue;
211  }
212 
213  VPInstruction *NewVPInst;
214  if (auto *Phi = dyn_cast<PHINode>(Inst)) {
215  // Phi node's operands may have not been visited at this point. We create
216  // an empty VPInstruction that we will fix once the whole plain CFG has
217  // been built.
218  NewVPInst = cast<VPInstruction>(VPIRBuilder.createNaryOp(
219  Inst->getOpcode(), {} /*No operands*/, Inst));
220  PhisToFix.push_back(Phi);
221  } else {
222  // Translate LLVM-IR operands into VPValue operands and set them in the
223  // new VPInstruction.
224  SmallVector<VPValue *, 4> VPOperands;
225  for (Value *Op : Inst->operands())
226  VPOperands.push_back(getOrCreateVPOperand(Op));
227 
228  // Build VPInstruction for any arbitraty Instruction without specific
229  // representation in VPlan.
230  NewVPInst = cast<VPInstruction>(
231  VPIRBuilder.createNaryOp(Inst->getOpcode(), VPOperands, Inst));
232  }
233 
234  IRDef2VPValue[Inst] = NewVPInst;
235  }
236 }
237 
238 // Main interface to build the plain CFG.
239 VPRegionBlock *PlainCFGBuilder::buildPlainCFG() {
240  // 1. Create the Top Region. It will be the parent of all VPBBs.
241  TopRegion = new VPRegionBlock("TopRegion", false /*isReplicator*/);
242 
243  // 2. Scan the body of the loop in a topological order to visit each basic
244  // block after having visited its predecessor basic blocks. Create a VPBB for
245  // each BB and link it to its successor and predecessor VPBBs. Note that
246  // predecessors must be set in the same order as they are in the incomming IR.
247  // Otherwise, there might be problems with existing phi nodes and algorithm
248  // based on predecessors traversal.
249 
250  // Loop PH needs to be explicitly visited since it's not taken into account by
251  // LoopBlocksDFS.
252  BasicBlock *PreheaderBB = TheLoop->getLoopPreheader();
253  assert((PreheaderBB->getTerminator()->getNumSuccessors() == 1) &&
254  "Unexpected loop preheader");
255  VPBasicBlock *PreheaderVPBB = getOrCreateVPBB(PreheaderBB);
256  createVPInstructionsForVPBB(PreheaderVPBB, PreheaderBB);
257  // Create empty VPBB for Loop H so that we can link PH->H.
258  VPBlockBase *HeaderVPBB = getOrCreateVPBB(TheLoop->getHeader());
259  // Preheader's predecessors will be set during the loop RPO traversal below.
260  PreheaderVPBB->setOneSuccessor(HeaderVPBB);
261 
262  LoopBlocksRPO RPO(TheLoop);
263  RPO.perform(LI);
264 
265  for (BasicBlock *BB : RPO) {
266  // Create or retrieve the VPBasicBlock for this BB and create its
267  // VPInstructions.
268  VPBasicBlock *VPBB = getOrCreateVPBB(BB);
269  createVPInstructionsForVPBB(VPBB, BB);
270 
271  // Set VPBB successors. We create empty VPBBs for successors if they don't
272  // exist already. Recipes will be created when the successor is visited
273  // during the RPO traversal.
274  Instruction *TI = BB->getTerminator();
275  assert(TI && "Terminator expected.");
276  unsigned NumSuccs = TI->getNumSuccessors();
277 
278  if (NumSuccs == 1) {
279  VPBasicBlock *SuccVPBB = getOrCreateVPBB(TI->getSuccessor(0));
280  assert(SuccVPBB && "VPBB Successor not found.");
281  VPBB->setOneSuccessor(SuccVPBB);
282  } else if (NumSuccs == 2) {
283  VPBasicBlock *SuccVPBB0 = getOrCreateVPBB(TI->getSuccessor(0));
284  assert(SuccVPBB0 && "Successor 0 not found.");
285  VPBasicBlock *SuccVPBB1 = getOrCreateVPBB(TI->getSuccessor(1));
286  assert(SuccVPBB1 && "Successor 1 not found.");
287 
288  // Get VPBB's condition bit.
289  assert(isa<BranchInst>(TI) && "Unsupported terminator!");
290  auto *Br = cast<BranchInst>(TI);
291  Value *BrCond = Br->getCondition();
292  // Look up the branch condition to get the corresponding VPValue
293  // representing the condition bit in VPlan (which may be in another VPBB).
294  assert(IRDef2VPValue.count(BrCond) &&
295  "Missing condition bit in IRDef2VPValue!");
296  VPValue *VPCondBit = IRDef2VPValue[BrCond];
297 
298  // Link successors using condition bit.
299  VPBB->setTwoSuccessors(SuccVPBB0, SuccVPBB1, VPCondBit);
300  } else
301  llvm_unreachable("Number of successors not supported.");
302 
303  // Set VPBB predecessors in the same order as they are in the incoming BB.
304  setVPBBPredsFromBB(VPBB, BB);
305  }
306 
307  // 3. Process outermost loop exit. We created an empty VPBB for the loop
308  // single exit BB during the RPO traversal of the loop body but Instructions
309  // weren't visited because it's not part of the the loop.
310  BasicBlock *LoopExitBB = TheLoop->getUniqueExitBlock();
311  assert(LoopExitBB && "Loops with multiple exits are not supported.");
312  VPBasicBlock *LoopExitVPBB = BB2VPBB[LoopExitBB];
313  createVPInstructionsForVPBB(LoopExitVPBB, LoopExitBB);
314  // Loop exit was already set as successor of the loop exiting BB.
315  // We only set its predecessor VPBB now.
316  setVPBBPredsFromBB(LoopExitVPBB, LoopExitBB);
317 
318  // 4. The whole CFG has been built at this point so all the input Values must
319  // have a VPlan couterpart. Fix VPlan phi nodes by adding their corresponding
320  // VPlan operands.
321  fixPhiNodes();
322 
323  // 5. Final Top Region setup. Set outermost loop pre-header and single exit as
324  // Top Region entry and exit.
325  TopRegion->setEntry(PreheaderVPBB);
326  TopRegion->setExit(LoopExitVPBB);
327  return TopRegion;
328 }
329 
330 VPRegionBlock *VPlanHCFGBuilder::buildPlainCFG() {
331  PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan);
332  return PCFGBuilder.buildPlainCFG();
333 }
334 
335 // Public interface to build a H-CFG.
337  // Build Top Region enclosing the plain CFG and set it as VPlan entry.
338  VPRegionBlock *TopRegion = buildPlainCFG();
339  Plan.setEntry(TopRegion);
340  LLVM_DEBUG(Plan.setName("HCFGBuilder: Plain CFG\n"); dbgs() << Plan);
341 
342  Verifier.verifyHierarchicalCFG(TopRegion);
343 
344  // Compute plain CFG dom tree for VPLInfo.
345  VPDomTree.recalculate(*TopRegion);
346  LLVM_DEBUG(dbgs() << "Dominator Tree after building the plain CFG.\n";
347  VPDomTree.print(dbgs()));
348 
349  // Compute VPLInfo and keep it in Plan.
350  VPLoopInfo &VPLInfo = Plan.getVPLoopInfo();
351  VPLInfo.analyze(VPDomTree);
352  LLVM_DEBUG(dbgs() << "VPLoop Info After buildPlainCFG:\n";
353  VPLInfo.print(dbgs()));
354 }
This class represents lattice values for constants.
Definition: AllocatorList.h:23
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:1147
void buildHierarchicalCFG()
Build H-CFG for TheLoop and update Plan accordingly.
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:1067
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
This file provides a LoopVectorizationPlanner class.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
#define P(N)
void setOneSuccessor(VPBlockBase *Successor)
Set a given VPBlockBase Successor as the single successor of this VPBlockBase.
Definition: VPlan.h:505
VPlan-based builder utility analogous to IRBuilder.
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
Definition: LoopInfoImpl.h:553
op_range operands()
Definition: User.h:237
void setPredecessors(ArrayRef< VPBlockBase *> NewPreds)
Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.
Definition: VPlan.h:526
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:982
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This file defines the VPlanHCFGBuilder class which contains the public interface (buildHierarchicalCF...
void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse, VPValue *Condition)
Set two given VPBlockBases IfTrue and IfFalse to be the two successors of this VPBlockBase.
Definition: VPlan.h:514
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:333
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:124
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:464
verify safepoint Safepoint IR Verifier
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:172
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:72
rpo Deduce function attributes in RPO
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopIterator.h:180
#define LLVM_DEBUG(X)
Definition: Debug.h:122
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:628
void setParent(VPRegionBlock *P)
Definition: VPlan.h:411
const BasicBlock * getParent() const
Definition: Instruction.h:66