VPlanHCFGBuilder.cpp Source File (original) (raw)

28#define DEBUG_TYPE "loop-vectorize"

30using namespace llvm;

32namespace {

34class PlainCFGBuilder {

35private:

37 Loop *TheLoop;

65 void fixPhiNodes();

67#ifndef NDEBUG

68 bool isExternalDef(Value *Val);

69#endif

73public:

75 : TheLoop(Lp), LI(LI), Plan(P) {}

78 void buildPlainCFG();

79};

80}

87 Loop *LoopForBB = LI->getLoopFor(BB);

88 if (!SinglePred || LI->getLoopFor(SinglePred) == LoopForBB)

89 return nullptr;

92 assert(SinglePred == LI->getLoopFor(SinglePred)->getLoopLatch() &&

93 "SinglePred must be the only loop latch");

94 return SinglePred;

95 };

96 if (auto *LatchBB = GetLatchOfExit(BB)) {

97 auto *PredRegion = getOrCreateVPBB(LatchBB)->getParent();

98 assert(VPBB == cast(PredRegion->getSingleSuccessor()) &&

99 "successor must already be set for PredRegion; it must have VPBB "

100 "as single successor");

102 return;

103 }

104

107 VPBBPreds.push_back(getOrCreateVPBB(Pred));

109}

110

112 return L && BB == L->getHeader();

113}

114

117

118 Loop *LoopOfBB = LI->getLoopFor(BB);

120}

121

122

123void PlainCFGBuilder::fixPhiNodes() {

124 for (auto *Phi : PhisToFix) {

125 assert(IRDef2VPValue.count(Phi) && "Missing VPInstruction for PHINode.");

127 assert(isa(VPVal) &&

128 "Expected WidenPHIRecipe for phi node.");

129 auto *VPPhi = cast(VPVal);

130 assert(VPPhi->getNumOperands() == 0 &&

131 "Expected VPInstruction with no operands.");

132

133 Loop *L = LI->getLoopFor(Phi->getParent());

135

136

137 assert(Phi->getNumOperands() == 2);

138 BasicBlock *LoopPred = L->getLoopPredecessor();

139 VPPhi->addIncoming(

140 getOrCreateVPOperand(Phi->getIncomingValueForBlock(LoopPred)),

141 BB2VPBB[LoopPred]);

142 BasicBlock *LoopLatch = L->getLoopLatch();

143 VPPhi->addIncoming(

144 getOrCreateVPOperand(Phi->getIncomingValueForBlock(LoopLatch)),

145 BB2VPBB[LoopLatch]);

146 continue;

147 }

148

149 for (unsigned I = 0; I != Phi->getNumOperands(); ++I)

150 VPPhi->addIncoming(getOrCreateVPOperand(Phi->getIncomingValue(I)),

151 BB2VPBB[Phi->getIncomingBlock(I)]);

152 }

153}

154

157}

158

159

161 if (L->getLoopDepth() < OuterLoop->getLoopDepth())

162 return false;

163 const Loop *P = L;

164 while (P) {

165 if (P == OuterLoop)

166 return true;

167 P = P->getParentLoop();

168 }

169 return false;

170}

171

172

173

174

175

177 if (auto *VPBB = BB2VPBB.lookup(BB)) {

178

179 return VPBB;

180 }

181

182

186 BB2VPBB[BB] = VPBB;

187

188

189 Loop *LoopOfBB = LI->getLoopFor(BB);

191 return VPBB;

192

193 auto *RegionOfVPBB = Loop2Region.lookup(LoopOfBB);

195 assert(RegionOfVPBB &&

196 "Region should have been created by visiting header earlier");

198 return VPBB;

199 }

200

201 assert(!RegionOfVPBB &&

202 "First visit of a header basic block expects to register its region.");

203

204 if (LoopOfBB == TheLoop) {

205 RegionOfVPBB = Plan.getVectorLoopRegion();

206 } else {

207 RegionOfVPBB = Plan.createVPRegionBlock(Name.str(), false );

208 RegionOfVPBB->setParent(Loop2Region[LoopOfBB->getParentLoop()]);

209 }

210 RegionOfVPBB->setEntry(VPBB);

211 Loop2Region[LoopOfBB] = RegionOfVPBB;

212 return VPBB;

213}

214

215#ifndef NDEBUG

216

217

218

219

220

221

222bool PlainCFGBuilder::isExternalDef(Value *Val) {

223

224

225 Instruction *Inst = dyn_cast(Val);

226 if (!Inst)

227 return true;

228

230 assert(InstParent && "Expected instruction parent.");

231

232

233 BasicBlock *PH = TheLoop->getLoopPreheader();

234 assert(PH && "Expected loop pre-header.");

235

236 if (InstParent == PH)

237

238 return false;

239

240

242 assert(Exit && "Expected loop with single exit.");

243 if (InstParent == Exit) {

244

245 return false;

246 }

247

248

249 return !TheLoop->contains(Inst);

250}

251#endif

252

253

254

255

256

257VPValue *PlainCFGBuilder::getOrCreateVPOperand(Value *IRVal) {

258 auto VPValIt = IRDef2VPValue.find(IRVal);

259 if (VPValIt != IRDef2VPValue.end())

260

261

262 return VPValIt->second;

263

264

265

266

267

268

269

270

271 assert(isExternalDef(IRVal) && "Expected external definition as operand.");

272

273

274

275 VPValue *NewVPVal = Plan.getOrAddLiveIn(IRVal);

276 IRDef2VPValue[IRVal] = NewVPVal;

277 return NewVPVal;

278}

279

280

281

282

283void PlainCFGBuilder::createVPInstructionsForVPBB(VPBasicBlock *VPBB,

285 VPIRBuilder.setInsertPoint(VPBB);

288

289

290

291 assert(!IRDef2VPValue.count(Inst) &&

292 "Instruction shouldn't have been visited.");

293

294 if (auto *Br = dyn_cast(Inst)) {

295

296

297 if (Br->isConditional()) {

298 VPValue *Cond = getOrCreateVPOperand(Br->getCondition());

300 }

301

302

303 continue;

304 }

305

307 if (auto *Phi = dyn_cast(Inst)) {

308

309

310

312 VPBB->appendRecipe(cast(NewVPV));

313 PhisToFix.push_back(Phi);

314 } else {

315

316

319 VPOperands.push_back(getOrCreateVPOperand(Op));

320

321

322

323 NewVPV = cast(

324 VPIRBuilder.createNaryOp(Inst->getOpcode(), VPOperands, Inst));

325 }

326

327 IRDef2VPValue[Inst] = NewVPV;

328 }

329}

330

331

332void PlainCFGBuilder::buildPlainCFG() {

333

334

335

336

337 VPRegionBlock *TheRegion = Plan.getVectorLoopRegion();

338 BasicBlock *ThePreheaderBB = TheLoop->getLoopPreheader();

340 "Unexpected loop preheader");

341 auto *VectorPreheaderVPBB =

343

344

345

346

347 BB2VPBB[ThePreheaderBB] = VectorPreheaderVPBB;

348 BasicBlock *LoopExitBB = TheLoop->getUniqueExitBlock();

349 Loop2Region[LI->getLoopFor(TheLoop->getHeader())] = TheRegion;

350 assert(LoopExitBB && "Loops with multiple exits are not supported.");

351 BB2VPBB[LoopExitBB] = cast(TheRegion->getSingleSuccessor());

352

353

354

357 BB2VPBB[TheLoop->getHeader()] = VectorHeaderVPBB;

360 if (TheLoop->getHeader() != TheLoop->getLoopLatch())

361 BB2VPBB[TheLoop->getLoopLatch()] = VectorLatchVPBB;

362 else

363 TheRegion->setExiting(VectorHeaderVPBB);

364

365

366

367

368

369

370

371

372

373

374 for (auto &I : *ThePreheaderBB) {

375 if (I.getType()->isVoidTy())

376 continue;

377 IRDef2VPValue[&I] = Plan.getOrAddLiveIn(&I);

378 }

379

381 RPO.perform(LI);

382

384

385

388 createVPInstructionsForVPBB(VPBB, BB);

389 Loop *LoopForBB = LI->getLoopFor(BB);

390

392 setVPBBPredsFromBB(VPBB, BB);

393 } else {

394

395

396 assert(isHeaderVPBB(VPBB) && "isHeaderBB and isHeaderVPBB disagree");

397 if (TheRegion != Region)

398 setRegionPredsFromBB(Region, BB);

399 }

400

401

402

403

404 auto *BI = cast(BB->getTerminator());

405 unsigned NumSuccs = succ_size(BB);

406 if (NumSuccs == 1) {

411 continue;

412 }

413 assert(BI->isConditional() && NumSuccs == 2 && BI->isConditional() &&

414 "block must have conditional branch with 2 successors");

415

416

417 assert(IRDef2VPValue.contains(BI->getCondition()) &&

418 "Missing condition bit in IRDef2VPValue!");

419 VPBasicBlock *Successor0 = getOrCreateVPBB(BI->getSuccessor(0));

420 VPBasicBlock *Successor1 = getOrCreateVPBB(BI->getSuccessor(1));

421 if (!LoopForBB || BB != LoopForBB->getLoopLatch()) {

423 continue;

424 }

425

426

427

428

429 if (TheRegion != Region) {

431 : Successor0);

432 Region->setExiting(VPBB);

433 }

434 }

435

436

437

438

439 fixPhiNodes();

440}

441

442void VPlanHCFGBuilder::buildPlainCFG() {

443 PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan);

444 PCFGBuilder.buildPlainCFG();

445}

446

447

449

450 buildPlainCFG();

452

453

455 LLVM_DEBUG(dbgs() << "Dominator Tree after building the plain CFG.\n";

457}

This file provides a LoopVectorizationPlanner class.

const SmallVectorImpl< MachineOperand > & Cond

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

static bool isHeaderBB(BasicBlock *BB, Loop *L)

static bool doesContainLoop(const Loop *L, const Loop *OuterLoop)

Return true of L loop is contained within OuterLoop.

static bool isHeaderVPBB(VPBasicBlock *VPBB)

This file defines the VPlanHCFGBuilder class which contains the public interface (buildHierarchicalCF...

LLVM Basic Block Representation.

iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const

Return a const iterator range over the instructions in the block, skipping any debug instructions.

const BasicBlock * getSinglePredecessor() const

Return the predecessor of this block if it has a single predecessor block.

const BasicBlock * getSingleSuccessor() const

Return the successor of this block if it has a single successor.

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...

This class represents an Operation in the Expression.

void print(raw_ostream &O) const

print - Convert to human readable form

void recalculate(ParentType &Func)

recalculate - compute a dominator tree for the given function

unsigned getNumSuccessors() const LLVM_READONLY

Return the number of successors that this instruction has.

unsigned getOpcode() const

Returns a member of one of the enums like Instruction::Add.

BlockT * getLoopLatch() const

If there is a single latch block for this loop, return it.

unsigned getLoopDepth() const

Return the nesting level of this loop.

BlockT * getLoopPredecessor() const

If the given loop's header has exactly one unique predecessor outside the loop, return it.

LoopT * getParentLoop() const

Return the parent loop if it exists or nullptr for top level loops.

Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...

Represents a single loop in the control flow graph.

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

StringRef - Represent a constant reference to a string, i.e.

VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.

void appendRecipe(VPRecipeBase *Recipe)

Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe.

VPBlockBase is the building block of the Hierarchical Control-Flow Graph.

VPRegionBlock * getParent()

const VPBasicBlock * getExitingBasicBlock() const

void setPredecessors(ArrayRef< VPBlockBase * > NewPreds)

Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.

void clearSuccessors()

Remove all the successors of this block.

void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse)

Set two given VPBlockBases IfTrue and IfFalse to be the two successors of this VPBlockBase.

VPBlockBase * getSinglePredecessor() const

void clearPredecessors()

Remove all the predecessor of this block.

const VPBasicBlock * getEntryBasicBlock() const

void setOneSuccessor(VPBlockBase *Successor)

Set a given VPBlockBase Successor as the single successor of this VPBlockBase.

void setParent(VPRegionBlock *P)

VPBlockBase * getSingleSuccessor() const

VPlan-based builder utility analogous to IRBuilder.

VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...

const VPBlockBase * getEntry() const

void setExiting(VPBlockBase *ExitingBlock)

Set ExitingBlock as the exiting VPBlockBase of this VPRegionBlock.

A recipe for handling phis that are widened in the vector loop.

void buildHierarchicalCFG()

Build H-CFG for TheLoop and update Plan accordingly.

VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...

void setName(const Twine &newName)

LLVM Value Representation.

StringRef getName() const

Return a constant reference to the value's name.

const ParentTy * getParent() const

NodeAddr< PhiNode * > Phi

This is an optimization pass for GlobalISel generic memory operations.

raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

auto succ_size(const MachineBasicBlock *BB)

auto predecessors(const MachineBasicBlock *BB)