Movatterモバイル変換

Go to the documentation of this file.

1//===-- SPIRVStructurizer.cpp ----------------------*- C++ -*-===//

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//===----------------------------------------------------------------------===//

11#include "Analysis/SPIRVConvergenceRegionAnalysis.h"

12#include "SPIRV.h"

13#include "SPIRVStructurizerWrapper.h"

14#include "SPIRVSubtarget.h"

15#include "SPIRVTargetMachine.h"

16#include "SPIRVUtils.h"

17#include "llvm/ADT/DenseMap.h"

18#include "llvm/ADT/SmallPtrSet.h"

19#include "llvm/Analysis/LoopInfo.h"

20#include "llvm/CodeGen/IntrinsicLowering.h"

21#include "llvm/IR/CFG.h"

22#include "llvm/IR/Dominators.h"

23#include "llvm/IR/IRBuilder.h"

24#include "llvm/IR/IntrinsicInst.h"

25#include "llvm/IR/Intrinsics.h"

26#include "llvm/IR/IntrinsicsSPIRV.h"

27#include "llvm/IR/LegacyPassManager.h"

28#include "llvm/InitializePasses.h"

29#include "llvm/PassRegistry.h"

30#include "llvm/Transforms/Utils.h"

31#include "llvm/Transforms/Utils/Cloning.h"

32#include "llvm/Transforms/Utils/LoopSimplify.h"

33#include "llvm/Transforms/Utils/LowerMemIntrinsics.h"

34#include <queue>

35#include <stack>

36#include <unordered_set>

38using namespacellvm;

39using namespaceSPIRV;

41namespacellvm {

43voidinitializeSPIRVStructurizerPass(PassRegistry &);

45namespace{

47usingBlockSet = std::unordered_set<BasicBlock *>;

48usingEdge = std::pair<BasicBlock *, BasicBlock *>;

50// Helper function to do a partial order visit from the block |Start|, calling

51// |Op| on each visited node.

52void partialOrderVisit(BasicBlock &Start,

53 std::function<bool(BasicBlock *)>Op) {

54PartialOrderingVisitor V(*Start.getParent());

55V.partialOrderVisit(Start,Op);

56}

58// Returns the exact convergence region in the tree defined by `Node` for which

59// `BB` is the header, nullptr otherwise.

60constConvergenceRegion *getRegionForHeader(constConvergenceRegion *Node,

61BasicBlock *BB) {

62if (Node->Entry == BB)

63returnNode;

65for (auto *Child :Node->Children) {

66constauto *CR = getRegionForHeader(Child, BB);

67if (CR !=nullptr)

68return CR;

69 }

70returnnullptr;

71}

73// Returns the single BasicBlock exiting the convergence region `CR`,

74// nullptr if no such exit exists.

75BasicBlock *getExitFor(constConvergenceRegion *CR) {

76 std::unordered_set<BasicBlock *> ExitTargets;

77for (BasicBlock *Exit : CR->Exits) {

78for (BasicBlock *Successor :successors(Exit)) {

79if (CR->Blocks.count(Successor) == 0)

80 ExitTargets.insert(Successor);

81 }

82 }

84assert(ExitTargets.size() <= 1);

85if (ExitTargets.size() == 0)

86returnnullptr;

88return *ExitTargets.begin();

89}

91// Returns the merge block designated by I if I is a merge instruction, nullptr

92// otherwise.

93BasicBlock *getDesignatedMergeBlock(Instruction *I) {

94IntrinsicInst *II = dyn_cast_or_null<IntrinsicInst>(I);

95if (II ==nullptr)

96returnnullptr;

98if (II->getIntrinsicID() != Intrinsic::spv_loop_merge &&

99II->getIntrinsicID() != Intrinsic::spv_selection_merge)

100returnnullptr;

101

102BlockAddress *BA = cast<BlockAddress>(II->getOperand(0));

103return BA->getBasicBlock();

104}

105

106// Returns the continue block designated by I if I is an OpLoopMerge, nullptr

107// otherwise.

108BasicBlock *getDesignatedContinueBlock(Instruction *I) {

109IntrinsicInst *II = dyn_cast_or_null<IntrinsicInst>(I);

110if (II ==nullptr)

111returnnullptr;

112

113if (II->getIntrinsicID() != Intrinsic::spv_loop_merge)

114returnnullptr;

115

116BlockAddress *BA = cast<BlockAddress>(II->getOperand(1));

117return BA->getBasicBlock();

118}

119

120// Returns true if Header has one merge instruction which designated Merge as

121// merge block.

122bool isDefinedAsSelectionMergeBy(BasicBlock &Header,BasicBlock &Merge) {

123for (auto &I : Header) {

124BasicBlock *MB = getDesignatedMergeBlock(&I);

125if (MB == &Merge)

126returntrue;

127 }

128returnfalse;

129}

130

131// Returns true if the BB has one OpLoopMerge instruction.

132bool hasLoopMergeInstruction(BasicBlock &BB) {

133for (auto &I : BB)

134if (getDesignatedContinueBlock(&I))

135returntrue;

136returnfalse;

137}

138

139// Returns true is I is an OpSelectionMerge or OpLoopMerge instruction, false

140// otherwise.

141bool isMergeInstruction(Instruction *I) {

142return getDesignatedMergeBlock(I) !=nullptr;

143}

144

145// Returns all blocks in F having at least one OpLoopMerge or OpSelectionMerge

146// instruction.

147SmallPtrSet<BasicBlock *, 2> getHeaderBlocks(Function &F) {

148SmallPtrSet<BasicBlock *, 2> Output;

149for (BasicBlock &BB :F) {

150for (Instruction &I : BB) {

151if (getDesignatedMergeBlock(&I) !=nullptr)

152 Output.insert(&BB);

153 }

154 }

155return Output;

156}

157

158// Returns all basic blocks in |F| referenced by at least 1

159// OpSelectionMerge/OpLoopMerge instruction.

160SmallPtrSet<BasicBlock *, 2> getMergeBlocks(Function &F) {

161SmallPtrSet<BasicBlock *, 2> Output;

162for (BasicBlock &BB :F) {

163for (Instruction &I : BB) {

164BasicBlock *MB = getDesignatedMergeBlock(&I);

165if (MB !=nullptr)

166 Output.insert(MB);

167 }

168 }

169return Output;

170}

171

172// Return all the merge instructions contained in BB.

173// Note: the SPIR-V spec doesn't allow a single BB to contain more than 1 merge

174// instruction, but this can happen while we structurize the CFG.

175std::vector<Instruction *> getMergeInstructions(BasicBlock &BB) {

176 std::vector<Instruction *> Output;

177for (Instruction &I : BB)

178if (isMergeInstruction(&I))

179 Output.push_back(&I);

180return Output;

181}

182

183// Returns all basic blocks in |F| referenced as continue target by at least 1

184// OpLoopMerge instruction.

185SmallPtrSet<BasicBlock *, 2> getContinueBlocks(Function &F) {

186SmallPtrSet<BasicBlock *, 2> Output;

187for (BasicBlock &BB :F) {

188for (Instruction &I : BB) {

189BasicBlock *MB = getDesignatedContinueBlock(&I);

190if (MB !=nullptr)

191 Output.insert(MB);

192 }

193 }

194return Output;

195}

196

197// Do a preorder traversal of the CFG starting from the BB |Start|.

198// point. Calls |op| on each basic block encountered during the traversal.

199voidvisit(BasicBlock &Start, std::function<bool(BasicBlock *)>op) {

200 std::stack<BasicBlock *> ToVisit;

201SmallPtrSet<BasicBlock *, 8> Seen;

202

203 ToVisit.push(&Start);

204 Seen.insert(ToVisit.top());

205while (ToVisit.size() != 0) {

206BasicBlock *BB = ToVisit.top();

207 ToVisit.pop();

208

209if (!op(BB))

210continue;

211

212for (auto Succ :successors(BB)) {

213if (Seen.contains(Succ))

214continue;

215 ToVisit.push(Succ);

216 Seen.insert(Succ);

217 }

218 }

219}

220

221// Replaces the conditional and unconditional branch targets of |BB| by

222// |NewTarget| if the target was |OldTarget|. This function also makes sure the

223// associated merge instruction gets updated accordingly.

224void replaceIfBranchTargets(BasicBlock *BB,BasicBlock *OldTarget,

225BasicBlock *NewTarget) {

226auto *BI = cast<BranchInst>(BB->getTerminator());

227

228// 1. Replace all matching successors.

229for (size_t i = 0; i < BI->getNumSuccessors(); i++) {

230if (BI->getSuccessor(i) == OldTarget)

231 BI->setSuccessor(i, NewTarget);

232 }

233

234// Branch was unconditional, no fixup required.

235if (BI->isUnconditional())

236return;

237

238// Branch had 2 successors, maybe now both are the same?

239if (BI->getSuccessor(0) != BI->getSuccessor(1))

240return;

241

242// Note: we may end up here because the original IR had such branches.

243// This means Target is not necessarily equal to NewTarget.

244IRBuilder<> Builder(BB);

245 Builder.SetInsertPoint(BI);

246 Builder.CreateBr(BI->getSuccessor(0));

247 BI->eraseFromParent();

248

249// The branch was the only instruction, nothing else to do.

250if (BB->size() == 1)

251return;

252

253// Otherwise, we need to check: was there an OpSelectionMerge before this

254// branch? If we removed the OpBranchConditional, we must also remove the

255// OpSelectionMerge. This is not valid for OpLoopMerge:

256IntrinsicInst *II =

257 dyn_cast<IntrinsicInst>(BB->getTerminator()->getPrevNode());

258if (!II ||II->getIntrinsicID() != Intrinsic::spv_selection_merge)

259return;

260

261Constant *C = cast<Constant>(II->getOperand(0));

262II->eraseFromParent();

263if (!C->isConstantUsed())

264C->destroyConstant();

265}

266

267// Replaces the target of branch instruction in |BB| with |NewTarget| if it

268// was |OldTarget|. This function also fixes the associated merge instruction.

269// Note: this function does not simplify branching instructions, it only updates

270// targets. See also: simplifyBranches.

271void replaceBranchTargets(BasicBlock *BB,BasicBlock *OldTarget,

272BasicBlock *NewTarget) {

273auto *T = BB->getTerminator();

274if (isa<ReturnInst>(T))

275return;

276

277if (isa<BranchInst>(T))

278return replaceIfBranchTargets(BB, OldTarget, NewTarget);

279

280if (auto *SI = dyn_cast<SwitchInst>(T)) {

281for (size_t i = 0; i <SI->getNumSuccessors(); i++) {

282if (SI->getSuccessor(i) == OldTarget)

283SI->setSuccessor(i, NewTarget);

284 }

285return;

286 }

287

288assert(false &&"Unhandled terminator type.");

289}

290

291}// anonymous namespace

292

293// Given a reducible CFG, produces a structurized CFG in the SPIR-V sense,

294// adding merge instructions when required.

295classSPIRVStructurizer :publicFunctionPass {

296

297structDivergentConstruct;

298// Represents a list of condition/loops/switch constructs.

299// See SPIR-V 2.11.2. Structured Control-flow Constructs for the list of

300// constructs.

301usingConstructList = std::vector<std::unique_ptr<DivergentConstruct>>;

302

303// Represents a divergent construct in the SPIR-V sense.

304// Such constructs are represented by a header (entry), a merge block (exit),

305// and possibly a continue block (back-edge). A construct can contain other

306// constructs, but their boundaries do not cross.

307structDivergentConstruct {

308BasicBlock *Header =nullptr;

309BasicBlock *Merge =nullptr;

310BasicBlock *Continue =nullptr;

311

312 DivergentConstruct *Parent =nullptr;

313 ConstructList Children;

314 };

315

316// An helper class to clean the construct boundaries.

317// It is used to gather the list of blocks that should belong to each

318// divergent construct, and possibly modify CFG edges when exits would cross

319// the boundary of multiple constructs.

320structSplitter {

321Function &F;

322LoopInfo &LI;

323DomTreeBuilder::BBDomTree DT;

324DomTreeBuilder::BBPostDomTree PDT;

325

326 Splitter(Function &F,LoopInfo &LI) :F(F), LI(LI) { invalidate(); }

327

328void invalidate() {

329 PDT.recalculate(F);

330 DT.recalculate(F);

331 }

332

333// Returns the list of blocks that belong to a SPIR-V loop construct,

334// including the continue construct.

335 std::vector<BasicBlock *> getLoopConstructBlocks(BasicBlock *Header,

336BasicBlock *Merge) {

337assert(DT.dominates(Header,Merge));

338 std::vector<BasicBlock *> Output;

339 partialOrderVisit(*Header, [&](BasicBlock *BB) {

340if (BB ==Merge)

341returnfalse;

342if (DT.dominates(Merge, BB) || !DT.dominates(Header, BB))

343returnfalse;

344 Output.push_back(BB);

345returntrue;

346 });

347return Output;

348 }

349

350// Returns the list of blocks that belong to a SPIR-V selection construct.

351 std::vector<BasicBlock *>

352 getSelectionConstructBlocks(DivergentConstruct *Node) {

353assert(DT.dominates(Node->Header, Node->Merge));

354 BlockSet OutsideBlocks;

355 OutsideBlocks.insert(Node->Merge);

356

357for (DivergentConstruct *It = Node->Parent; It !=nullptr;

358 It = It->Parent) {

359 OutsideBlocks.insert(It->Merge);

360if (It->Continue)

361 OutsideBlocks.insert(It->Continue);

362 }

363

364 std::vector<BasicBlock *> Output;

365 partialOrderVisit(*Node->Header, [&](BasicBlock *BB) {

366 if (OutsideBlocks.count(BB) != 0)

367 return false;

368 if (DT.dominates(Node->Merge, BB) || !DT.dominates(Node->Header, BB))

369 return false;

370 Output.push_back(BB);

371 return true;

372 });

373return Output;

374 }

375

376// Returns the list of blocks that belong to a SPIR-V switch construct.

377 std::vector<BasicBlock *> getSwitchConstructBlocks(BasicBlock *Header,

378BasicBlock *Merge) {

379assert(DT.dominates(Header,Merge));

380

381 std::vector<BasicBlock *> Output;

382 partialOrderVisit(*Header, [&](BasicBlock *BB) {

383// the blocks structurally dominated by a switch header,

384if (!DT.dominates(Header, BB))

385returnfalse;

386// excluding blocks structurally dominated by the switch header’s merge

387// block.

388if (DT.dominates(Merge, BB) || BB ==Merge)

389returnfalse;

390 Output.push_back(BB);

391returntrue;

392 });

393return Output;

394 }

395

396// Returns the list of blocks that belong to a SPIR-V case construct.

397 std::vector<BasicBlock *> getCaseConstructBlocks(BasicBlock *Target,

398BasicBlock *Merge) {

399assert(DT.dominates(Target,Merge));

400

401 std::vector<BasicBlock *> Output;

402 partialOrderVisit(*Target, [&](BasicBlock *BB) {

403// the blocks structurally dominated by an OpSwitch Target or Default

404// block

405if (!DT.dominates(Target, BB))

406returnfalse;

407// excluding the blocks structurally dominated by the OpSwitch

408// construct’s corresponding merge block.

409if (DT.dominates(Merge, BB) || BB ==Merge)

410returnfalse;

411 Output.push_back(BB);

412returntrue;

413 });

414return Output;

415 }

416

417// Splits the given edges by recreating proxy nodes so that the destination

418// has unique incoming edges from this region.

419//

420// clang-format off

421//

422// In SPIR-V, constructs must have a single exit/merge.

423// Given nodes A and B in the construct, a node C outside, and the following edges.

424// A -> C

425// B -> C

426//

427// In such cases, we must create a new exit node D, that belong to the construct to make is viable:

428// A -> D -> C

429// B -> D -> C

430//

431// This is fine (assuming C has no PHI nodes), but requires handling the merge instruction here.

432// By adding a proxy node, we create a regular divergent shape which can easily be regularized later on.

433// A -> D -> D1 -> C

434// B -> D -> D2 -> C

435//

436// A, B, D belongs to the construct. D is the exit. D1 and D2 are empty.

437//

438// clang-format on

439 std::vector<Edge>

440 createAliasBlocksForComplexEdges(std::vector<Edge> Edges) {

441 std::unordered_set<BasicBlock *> Seen;

442 std::vector<Edge> Output;

443 Output.reserve(Edges.size());

444

445for (auto &[Src, Dst] : Edges) {

446auto [Iterator, Inserted] = Seen.insert(Src);

447if (!Inserted) {

448// Src already a source node. Cannot have 2 edges from A to B.

449// Creating alias source block.

450BasicBlock *NewSrc =BasicBlock::Create(

451F.getContext(), Src->getName() +".new.src", &F);

452 replaceBranchTargets(Src, Dst, NewSrc);

453IRBuilder<> Builder(NewSrc);

454 Builder.CreateBr(Dst);

455 Src = NewSrc;

456 }

457

458 Output.emplace_back(Src, Dst);

459 }

460

461return Output;

462 }

463

464AllocaInst *CreateVariable(Function &F,Type *Type,

465BasicBlock::iterator Position) {

466constDataLayout &DL =F.getDataLayout();

467returnnewAllocaInst(Type,DL.getAllocaAddrSpace(),nullptr,"reg",

468 Position);

469 }

470

471// Given a construct defined by |Header|, and a list of exiting edges

472// |Edges|, creates a new single exit node, fixing up those edges.

473BasicBlock *createSingleExitNode(BasicBlock *Header,

474 std::vector<Edge> &Edges) {

475

476 std::vector<Edge> FixedEdges = createAliasBlocksForComplexEdges(Edges);

477

478 std::vector<BasicBlock *> Dsts;

479 std::unordered_map<BasicBlock *, ConstantInt *> DstToIndex;

480auto NewExit =BasicBlock::Create(F.getContext(),

481 Header->getName() +".new.exit", &F);

482IRBuilder<> ExitBuilder(NewExit);

483for (auto &[Src, Dst] : FixedEdges) {

484if (DstToIndex.count(Dst) != 0)

485continue;

486 DstToIndex.emplace(Dst, ExitBuilder.getInt32(DstToIndex.size()));

487 Dsts.push_back(Dst);

488 }

489

490if (Dsts.size() == 1) {

491for (auto &[Src, Dst] : FixedEdges) {

492 replaceBranchTargets(Src, Dst, NewExit);

493 }

494 ExitBuilder.CreateBr(Dsts[0]);

495return NewExit;

496 }

497

498AllocaInst *Variable = CreateVariable(F, ExitBuilder.getInt32Ty(),

499F.begin()->getFirstInsertionPt());

500for (auto &[Src, Dst] : FixedEdges) {

501IRBuilder<> B2(Src);

502 B2.SetInsertPoint(Src->getFirstInsertionPt());

503 B2.CreateStore(DstToIndex[Dst], Variable);

504 replaceBranchTargets(Src, Dst, NewExit);

505 }

506

507llvm::Value *Load =

508 ExitBuilder.CreateLoad(ExitBuilder.getInt32Ty(), Variable);

509

510// If we can avoid an OpSwitch, generate an OpBranch. Reason is some

511// OpBranch are allowed to exist without a new OpSelectionMerge if one of

512// the branch is the parent's merge node, while OpSwitches are not.

513if (Dsts.size() == 2) {

514Value *Condition =

515 ExitBuilder.CreateCmp(CmpInst::ICMP_EQ, DstToIndex[Dsts[0]], Load);

516 ExitBuilder.CreateCondBr(Condition, Dsts[0], Dsts[1]);

517return NewExit;

518 }

519

520SwitchInst *Sw = ExitBuilder.CreateSwitch(Load, Dsts[0], Dsts.size() - 1);

521for (auto It = Dsts.begin() + 1; It != Dsts.end(); ++It) {

522 Sw->addCase(DstToIndex[*It], *It);

523 }

524return NewExit;

525 }

526 };

527

528 /// Create a value in BB set to the value associated with the branch the block

529 /// terminator will take.

530Value *createExitVariable(

531BasicBlock *BB,

532constDenseMap<BasicBlock *, ConstantInt *> &TargetToValue) {

533auto *T = BB->getTerminator();

534if (isa<ReturnInst>(T))

535returnnullptr;

536

537IRBuilder<> Builder(BB);

538 Builder.SetInsertPoint(T);

539

540if (auto *BI = dyn_cast<BranchInst>(T)) {

541

542BasicBlock *LHSTarget = BI->getSuccessor(0);

543BasicBlock *RHSTarget =

544 BI->isConditional() ? BI->getSuccessor(1) :nullptr;

545

546Value *LHS = TargetToValue.count(LHSTarget) != 0

547 ? TargetToValue.at(LHSTarget)

548 :nullptr;

549Value *RHS = TargetToValue.count(RHSTarget) != 0

550 ? TargetToValue.at(RHSTarget)

551 :nullptr;

552

553if (LHS ==nullptr ||RHS ==nullptr)

554returnLHS ==nullptr ?RHS :LHS;

555return Builder.CreateSelect(BI->getCondition(),LHS,RHS);

556 }

557

558// TODO: add support for switch cases.

559llvm_unreachable("Unhandled terminator type.");

560 }

561

562// Creates a new basic block in F with a single OpUnreachable instruction.

563BasicBlock *CreateUnreachable(Function &F) {

564BasicBlock *BB =BasicBlock::Create(F.getContext(),"unreachable", &F);

565IRBuilder<> Builder(BB);

566 Builder.CreateUnreachable();

567return BB;

568 }

569

570// Add OpLoopMerge instruction on cycles.

571bool addMergeForLoops(Function &F) {

572LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();

573auto *TopLevelRegion =

574 getAnalysis<SPIRVConvergenceRegionAnalysisWrapperPass>()

575 .getRegionInfo()

576 .getTopLevelRegion();

577

578boolModified =false;

579for (auto &BB :F) {

580// Not a loop header. Ignoring for now.

581if (!LI.isLoopHeader(&BB))

582continue;

583auto *L = LI.getLoopFor(&BB);

584

585// This loop header is not the entrance of a convergence region. Ignoring

586// this block.

587auto *CR = getRegionForHeader(TopLevelRegion, &BB);

588if (CR ==nullptr)

589continue;

590

591IRBuilder<> Builder(&BB);

592

593auto *Merge = getExitFor(CR);

594// We are indeed in a loop, but there are no exits (infinite loop).

595// This could be caused by a bad shader, but also could be an artifact

596// from an earlier optimization. It is not always clear if structurally

597// reachable means runtime reachable, so we cannot error-out. What we must

598// do however is to make is legal on the SPIR-V point of view, hence

599// adding an unreachable merge block.

600if (Merge ==nullptr) {

601BranchInst *Br = cast<BranchInst>(BB.getTerminator());

602assert(Br &&

603"This assumes the branch is not a switch. Maybe that's wrong?");

604assert(cast<BranchInst>(BB.getTerminator())->isUnconditional());

605

606Merge = CreateUnreachable(F);

607 Builder.SetInsertPoint(Br);

608 Builder.CreateCondBr(Builder.getFalse(),Merge, Br->getSuccessor(0));

609 Br->eraseFromParent();

610 }

611

612auto *Continue = L->getLoopLatch();

613

614 Builder.SetInsertPoint(BB.getTerminator());

615auto MergeAddress =BlockAddress::get(Merge->getParent(),Merge);

616auto ContinueAddress =BlockAddress::get(Continue->getParent(),Continue);

617SmallVector<Value *, 2> Args = {MergeAddress, ContinueAddress};

618

619 Builder.CreateIntrinsic(Intrinsic::spv_loop_merge, {}, {Args});

620Modified =true;

621 }

622

623returnModified;

624 }

625

626// Adds an OpSelectionMerge to the immediate dominator or each node with an

627// in-degree of 2 or more which is not already the merge target of an

628// OpLoopMerge/OpSelectionMerge.

629bool addMergeForNodesWithMultiplePredecessors(Function &F) {

630DomTreeBuilder::BBDomTree DT;

631 DT.recalculate(F);

632

633boolModified =false;

634for (auto &BB :F) {

635if (pred_size(&BB) <= 1)

636continue;

637

638if (hasLoopMergeInstruction(BB) &&pred_size(&BB) <= 2)

639continue;

640

641assert(DT.getNode(&BB)->getIDom());

642BasicBlock *Header = DT.getNode(&BB)->getIDom()->getBlock();

643

644if (isDefinedAsSelectionMergeBy(*Header, BB))

645continue;

646

647IRBuilder<> Builder(Header);

648 Builder.SetInsertPoint(Header->getTerminator());

649

650auto MergeAddress =BlockAddress::get(BB.getParent(), &BB);

651createOpSelectMerge(&Builder, MergeAddress);

652

653Modified =true;

654 }

655

656returnModified;

657 }

658

659// When a block has multiple OpSelectionMerge/OpLoopMerge instructions, sorts

660// them to put the "largest" first. A merge instruction is defined as larger

661// than another when its target merge block post-dominates the other target's

662// merge block. (This ordering should match the nesting ordering of the source

663// HLSL).

664bool sortSelectionMerge(Function &F,BasicBlock &Block) {

665 std::vector<Instruction *> MergeInstructions;

666for (Instruction &I :Block)

667if (isMergeInstruction(&I))

668 MergeInstructions.push_back(&I);

669

670if (MergeInstructions.size() <= 1)

671returnfalse;

672

673Instruction *InsertionPoint = *MergeInstructions.begin();

674

675PartialOrderingVisitor Visitor(F);

676 std::sort(MergeInstructions.begin(), MergeInstructions.end(),

677 [&Visitor](Instruction *Left,Instruction *Right) {

678 if (Left == Right)

679 return false;

680 BasicBlock *RightMerge = getDesignatedMergeBlock(Right);

681 BasicBlock *LeftMerge = getDesignatedMergeBlock(Left);

682 return !Visitor.compare(RightMerge, LeftMerge);

683 });

684

685for (Instruction *I : MergeInstructions) {

686I->moveBefore(InsertionPoint->getIterator());

687InsertionPoint =I;

688 }

689

690returntrue;

691 }

692

693// Sorts selection merge headers in |F|.

694// A is sorted before B if the merge block designated by B is an ancestor of

695// the one designated by A.

696bool sortSelectionMergeHeaders(Function &F) {

697boolModified =false;

698for (BasicBlock &BB :F) {

699Modified |= sortSelectionMerge(F, BB);

700 }

701returnModified;

702 }

703

704// Split basic blocks containing multiple OpLoopMerge/OpSelectionMerge

705// instructions so each basic block contains only a single merge instruction.

706bool splitBlocksWithMultipleHeaders(Function &F) {

707 std::stack<BasicBlock *> Work;

708for (auto &BB :F) {

709 std::vector<Instruction *> MergeInstructions = getMergeInstructions(BB);

710if (MergeInstructions.size() <= 1)

711continue;

712 Work.push(&BB);

713 }

714

715constboolModified = Work.size() > 0;

716while (Work.size() > 0) {

717BasicBlock *Header = Work.top();

718 Work.pop();

719

720 std::vector<Instruction *> MergeInstructions =

721 getMergeInstructions(*Header);

722for (unsigned i = 1; i < MergeInstructions.size(); i++) {

723BasicBlock *NewBlock =

724 Header->splitBasicBlock(MergeInstructions[i],"new.header");

725

726if (getDesignatedContinueBlock(MergeInstructions[0]) ==nullptr) {

727BasicBlock *Unreachable = CreateUnreachable(F);

728

729BranchInst *BI = cast<BranchInst>(Header->getTerminator());

730IRBuilder<> Builder(Header);

731 Builder.SetInsertPoint(BI);

732 Builder.CreateCondBr(Builder.getTrue(), NewBlock, Unreachable);

733 BI->eraseFromParent();

734 }

735

736 Header = NewBlock;

737 }

738 }

739

740returnModified;

741 }

742

743// Adds an OpSelectionMerge to each block with an out-degree >= 2 which

744// doesn't already have an OpSelectionMerge.

745bool addMergeForDivergentBlocks(Function &F) {

746DomTreeBuilder::BBPostDomTree PDT;

747 PDT.recalculate(F);

748boolModified =false;

749

750auto MergeBlocks = getMergeBlocks(F);

751auto ContinueBlocks = getContinueBlocks(F);

752

753for (auto &BB :F) {

754if (getMergeInstructions(BB).size() != 0)

755continue;

756

757 std::vector<BasicBlock *> Candidates;

758for (BasicBlock *Successor :successors(&BB)) {

759if (MergeBlocks.contains(Successor))

760continue;

761if (ContinueBlocks.contains(Successor))

762continue;

763 Candidates.push_back(Successor);

764 }

765

766if (Candidates.size() <= 1)

767continue;

768

769Modified =true;

770BasicBlock *Merge = Candidates[0];

771

772auto MergeAddress =BlockAddress::get(Merge->getParent(),Merge);

773IRBuilder<> Builder(&BB);

774 Builder.SetInsertPoint(BB.getTerminator());

775createOpSelectMerge(&Builder, MergeAddress);

776 }

777

778returnModified;

779 }

780

781// Gather all the exit nodes for the construct header by |Header| and

782// containing the blocks |Construct|.

783 std::vector<Edge> getExitsFrom(const BlockSet &Construct,

784BasicBlock &Header) {

785 std::vector<Edge> Output;

786visit(Header, [&](BasicBlock *Item) {

787if (Construct.count(Item) == 0)

788returnfalse;

789

790for (BasicBlock *Successor :successors(Item)) {

791if (Construct.count(Successor) == 0)

792 Output.emplace_back(Item,Successor);

793 }

794returntrue;

795 });

796

797return Output;

798 }

799

800// Build a divergent construct tree searching from |BB|.

801// If |Parent| is not null, this tree is attached to the parent's tree.

802void constructDivergentConstruct(BlockSet &Visited, Splitter &S,

803BasicBlock *BB, DivergentConstruct *Parent) {

804if (Visited.count(BB) != 0)

805return;

806 Visited.insert(BB);

807

808auto MIS = getMergeInstructions(*BB);

809if (MIS.size() == 0) {

810for (BasicBlock *Successor :successors(BB))

811 constructDivergentConstruct(Visited, S,Successor, Parent);

812return;

813 }

814

815assert(MIS.size() == 1);

816Instruction *MI = MIS[0];

817

818BasicBlock *Merge = getDesignatedMergeBlock(MI);

819BasicBlock *Continue = getDesignatedContinueBlock(MI);

820

821auto Output = std::make_unique<DivergentConstruct>();

822 Output->Header = BB;

823 Output->Merge =Merge;

824 Output->Continue =Continue;

825 Output->Parent = Parent;

826

827 constructDivergentConstruct(Visited, S,Merge, Parent);

828if (Continue)

829 constructDivergentConstruct(Visited, S,Continue, Output.get());

830

831for (BasicBlock *Successor :successors(BB))

832 constructDivergentConstruct(Visited, S,Successor, Output.get());

833

834if (Parent)

835 Parent->Children.emplace_back(std::move(Output));

836 }

837

838// Returns the blocks belonging to the divergent construct |Node|.

839 BlockSet getConstructBlocks(Splitter &S, DivergentConstruct *Node) {

840assert(Node->Header && Node->Merge);

841

842if (Node->Continue) {

843auto LoopBlocks = S.getLoopConstructBlocks(Node->Header, Node->Merge);

844return BlockSet(LoopBlocks.begin(), LoopBlocks.end());

845 }

846

847auto SelectionBlocks = S.getSelectionConstructBlocks(Node);

848return BlockSet(SelectionBlocks.begin(), SelectionBlocks.end());

849 }

850

851// Fixup the construct |Node| to respect a set of rules defined by the SPIR-V

852// spec.

853bool fixupConstruct(Splitter &S, DivergentConstruct *Node) {

854boolModified =false;

855for (auto &Child : Node->Children)

856Modified |= fixupConstruct(S, Child.get());

857

858// This construct is the root construct. Does not represent any real

859// construct, just a way to access the first level of the forest.

860if (Node->Parent ==nullptr)

861returnModified;

862

863// This node's parent is the root. Meaning this is a top-level construct.

864// There can be multiple exists, but all are guaranteed to exit at most 1

865// construct since we are at first level.

866if (Node->Parent->Header ==nullptr)

867returnModified;

868

869// Health check for the structure.

870assert(Node->Header && Node->Merge);

871assert(Node->Parent->Header && Node->Parent->Merge);

872

873 BlockSet ConstructBlocks = getConstructBlocks(S, Node);

874auto Edges = getExitsFrom(ConstructBlocks, *Node->Header);

875

876// No edges exiting the construct.

877if (Edges.size() < 1)

878returnModified;

879

880bool HasBadEdge = Node->Merge == Node->Parent->Merge ||

881 Node->Merge == Node->Parent->Continue;

882// BasicBlock *Target = Edges[0].second;

883for (auto &[Src, Dst] : Edges) {

884// - Breaking from a selection construct: S is a selection construct, S is

885// the innermost structured

886// control-flow construct containing A, and B is the merge block for S

887// - Breaking from the innermost loop: S is the innermost loop construct

888// containing A,

889// and B is the merge block for S

890if (Node->Merge == Dst)

891continue;

892

893// Entering the innermost loop’s continue construct: S is the innermost

894// loop construct containing A, and B is the continue target for S

895if (Node->Continue == Dst)

896continue;

897

898// TODO: what about cases branching to another case in the switch? Seems

899// to work, but need to double check.

900 HasBadEdge =true;

901 }

902

903if (!HasBadEdge)

904returnModified;

905

906// Create a single exit node gathering all exit edges.

907BasicBlock *NewExit = S.createSingleExitNode(Node->Header, Edges);

908

909// Fixup this construct's merge node to point to the new exit.

910// Note: this algorithm fixes inner-most divergence construct first. So

911// recursive structures sharing a single merge node are fixed from the

912// inside toward the outside.

913auto MergeInstructions = getMergeInstructions(*Node->Header);

914assert(MergeInstructions.size() == 1);

915Instruction *I = MergeInstructions[0];

916BlockAddress *BA = cast<BlockAddress>(I->getOperand(0));

917if (BA->getBasicBlock() == Node->Merge) {

918auto MergeAddress =BlockAddress::get(NewExit->getParent(), NewExit);

919I->setOperand(0, MergeAddress);

920 }

921

922// Clean up of the possible dangling BockAddr operands to prevent MIR

923// comments about "address of removed block taken".

924if (!BA->isConstantUsed())

925 BA->destroyConstant();

926

927 Node->Merge = NewExit;

928// Regenerate the dom trees.

929 S.invalidate();

930returntrue;

931 }

932

933bool splitCriticalEdges(Function &F) {

934LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();

935 Splitter S(F, LI);

936

937 DivergentConstruct Root;

938 BlockSet Visited;

939 constructDivergentConstruct(Visited, S, &*F.begin(), &Root);

940return fixupConstruct(S, &Root);

941 }

942

943// Simplify branches when possible:

944// - if the 2 sides of a conditional branch are the same, transforms it to an

945// unconditional branch.

946// - if a switch has only 2 distinct successors, converts it to a conditional

947// branch.

948bool simplifyBranches(Function &F) {

949boolModified =false;

950

951for (BasicBlock &BB :F) {

952SwitchInst *SI = dyn_cast<SwitchInst>(BB.getTerminator());

953if (!SI)

954continue;

955if (SI->getNumCases() > 1)

956continue;

957

958Modified =true;

959IRBuilder<> Builder(&BB);

960 Builder.SetInsertPoint(SI);

961

962if (SI->getNumCases() == 0) {

963 Builder.CreateBr(SI->getDefaultDest());

964 }else {

965Value *Condition =

966 Builder.CreateCmp(CmpInst::ICMP_EQ, SI->getCondition(),

967 SI->case_begin()->getCaseValue());

968 Builder.CreateCondBr(Condition, SI->case_begin()->getCaseSuccessor(),

969 SI->getDefaultDest());

970 }

971 SI->eraseFromParent();

972 }

973

974returnModified;

975 }

976

977// Makes sure every case target in |F| is unique. If 2 cases branch to the

978// same basic block, one of the targets is updated so it jumps to a new basic

979// block ending with a single unconditional branch to the original target.

980bool splitSwitchCases(Function &F) {

981boolModified =false;

982

983for (BasicBlock &BB :F) {

984SwitchInst *SI = dyn_cast<SwitchInst>(BB.getTerminator());

985if (!SI)

986continue;

987

988 BlockSet Seen;

989 Seen.insert(SI->getDefaultDest());

990

991auto It = SI->case_begin();

992while (It != SI->case_end()) {

993BasicBlock *Target = It->getCaseSuccessor();

994if (Seen.count(Target) == 0) {

995 Seen.insert(Target);

996 ++It;

997continue;

998 }

999

1000Modified =true;

1001BasicBlock *NewTarget =

1002BasicBlock::Create(F.getContext(),"new.sw.case", &F);

1003IRBuilder<> Builder(NewTarget);

1004 Builder.CreateBr(Target);

1005 SI->addCase(It->getCaseValue(), NewTarget);

1006 It = SI->removeCase(It);

1007 }

1008 }

1009

1010returnModified;

1011 }

1012

1013// Removes blocks not contributing to any structured CFG. This assumes there

1014// is no PHI nodes.

1015bool removeUselessBlocks(Function &F) {

1016 std::vector<BasicBlock *>ToRemove;

1017

1018auto MergeBlocks = getMergeBlocks(F);

1019auto ContinueBlocks = getContinueBlocks(F);

1020

1021for (BasicBlock &BB :F) {

1022if (BB.size() != 1)

1023continue;

1024

1025if (isa<ReturnInst>(BB.getTerminator()))

1026continue;

1027

1028if (MergeBlocks.count(&BB) != 0 || ContinueBlocks.count(&BB) != 0)

1029continue;

1030

1031if (BB.getUniqueSuccessor() ==nullptr)

1032continue;

1033

1034BasicBlock *Successor = BB.getUniqueSuccessor();

1035 std::vector<BasicBlock *> Predecessors(predecessors(&BB).begin(),

1036predecessors(&BB).end());

1037for (BasicBlock *Predecessor : Predecessors)

1038 replaceBranchTargets(Predecessor, &BB,Successor);

1039ToRemove.push_back(&BB);

1040 }

1041

1042for (BasicBlock *BB :ToRemove)

1043 BB->eraseFromParent();

1044

1045returnToRemove.size() != 0;

1046 }

1047

1048bool addHeaderToRemainingDivergentDAG(Function &F) {

1049boolModified =false;

1050

1051auto MergeBlocks = getMergeBlocks(F);

1052auto ContinueBlocks = getContinueBlocks(F);

1053auto HeaderBlocks = getHeaderBlocks(F);

1054

1055DomTreeBuilder::BBDomTree DT;

1056DomTreeBuilder::BBPostDomTree PDT;

1057 PDT.recalculate(F);

1058 DT.recalculate(F);

1059

1060for (BasicBlock &BB :F) {

1061if (HeaderBlocks.count(&BB) != 0)

1062continue;

1063if (succ_size(&BB) < 2)

1064continue;

1065

1066size_t CandidateEdges = 0;

1067for (BasicBlock *Successor :successors(&BB)) {

1068if (MergeBlocks.count(Successor) != 0 ||

1069 ContinueBlocks.count(Successor) != 0)

1070continue;

1071if (HeaderBlocks.count(Successor) != 0)

1072continue;

1073 CandidateEdges += 1;

1074 }

1075

1076if (CandidateEdges <= 1)

1077continue;

1078

1079BasicBlock *Header = &BB;

1080BasicBlock *Merge = PDT.getNode(&BB)->getIDom()->getBlock();

1081

1082bool HasBadBlock =false;

1083visit(*Header, [&](constBasicBlock *Node) {

1084if (DT.dominates(Header, Node))

1085returnfalse;

1086if (PDT.dominates(Merge, Node))

1087returnfalse;

1088if (Node == Header || Node ==Merge)

1089returntrue;

1090

1091 HasBadBlock |= MergeBlocks.count(Node) != 0 ||

1092 ContinueBlocks.count(Node) != 0 ||

1093 HeaderBlocks.count(Node) != 0;

1094return !HasBadBlock;

1095 });

1096

1097if (HasBadBlock)

1098continue;

1099

1100Modified =true;

1101

1102if (Merge ==nullptr) {

1103Merge = *successors(Header).begin();

1104IRBuilder<> Builder(Header);

1105 Builder.SetInsertPoint(Header->getTerminator());

1106

1107auto MergeAddress =BlockAddress::get(Merge->getParent(),Merge);

1108createOpSelectMerge(&Builder, MergeAddress);

1109continue;

1110 }

1111

1112Instruction *SplitInstruction =Merge->getTerminator();

1113if (isMergeInstruction(SplitInstruction->getPrevNode()))

1114 SplitInstruction = SplitInstruction->getPrevNode();

1115BasicBlock *NewMerge =

1116Merge->splitBasicBlockBefore(SplitInstruction,"new.merge");

1117

1118IRBuilder<> Builder(Header);

1119 Builder.SetInsertPoint(Header->getTerminator());

1120

1121auto MergeAddress =BlockAddress::get(NewMerge->getParent(), NewMerge);

1122createOpSelectMerge(&Builder, MergeAddress);

1123 }

1124

1125returnModified;

1126 }

1127

1128public:

1129staticcharID;

1130

1131SPIRVStructurizer() :FunctionPass(ID) {

1132initializeSPIRVStructurizerPass(*PassRegistry::getPassRegistry());

1133 };

1134

1135virtualboolrunOnFunction(Function &F) override{

1136boolModified =false;

1137

1138// In LLVM, Switches are allowed to have several cases branching to the same

1139// basic block. This is allowed in SPIR-V, but can make structurizing SPIR-V

1140// harder, so first remove edge cases.

1141Modified |= splitSwitchCases(F);

1142

1143// LLVM allows conditional branches to have both side jumping to the same

1144// block. It also allows switched to have a single default, or just one

1145// case. Cleaning this up now.

1146Modified |= simplifyBranches(F);

1147

1148// At this state, we should have a reducible CFG with cycles.

1149// STEP 1: Adding OpLoopMerge instructions to loop headers.

1150Modified |= addMergeForLoops(F);

1151

1152// STEP 2: adding OpSelectionMerge to each node with an in-degree >= 2.

1153Modified |= addMergeForNodesWithMultiplePredecessors(F);

1154

1155// STEP 3:

1156// Sort selection merge, the largest construct goes first.

1157// This simplifies the next step.

1158Modified |= sortSelectionMergeHeaders(F);

1159

1160// STEP 4: As this stage, we can have a single basic block with multiple

1161// OpLoopMerge/OpSelectionMerge instructions. Splitting this block so each

1162// BB has a single merge instruction.

1163Modified |= splitBlocksWithMultipleHeaders(F);

1164

1165// STEP 5: In the previous steps, we added merge blocks the loops and

1166// natural merge blocks (in-degree >= 2). What remains are conditions with

1167// an exiting branch (return, unreachable). In such case, we must start from

1168// the header, and add headers to divergent construct with no headers.

1169Modified |= addMergeForDivergentBlocks(F);

1170

1171// STEP 6: At this stage, we have several divergent construct defines by a

1172// header and a merge block. But their boundaries have no constraints: a

1173// construct exit could be outside of the parents' construct exit. Such

1174// edges are called critical edges. What we need is to split those edges

1175// into several parts. Each part exiting the parent's construct by its merge

1176// block.

1177Modified |= splitCriticalEdges(F);

1178

1179// STEP 7: The previous steps possibly created a lot of "proxy" blocks.

1180// Blocks with a single unconditional branch, used to create a valid

1181// divergent construct tree. Some nodes are still requires (e.g: nodes

1182// allowing a valid exit through the parent's merge block). But some are

1183// left-overs of past transformations, and could cause actual validation

1184// issues. E.g: the SPIR-V spec allows a construct to break to the parents

1185// loop construct without an OpSelectionMerge, but this requires a straight

1186// jump. If a proxy block lies between the conditional branch and the

1187// parent's merge, the CFG is not valid.

1188Modified |= removeUselessBlocks(F);

1189

1190// STEP 8: Final fix-up steps: our tree boundaries are correct, but some

1191// blocks are branching with no header. Those are often simple conditional

1192// branches with 1 or 2 returning edges. Adding a header for those.

1193Modified |= addHeaderToRemainingDivergentDAG(F);

1194

1195// STEP 9: sort basic blocks to match both the LLVM & SPIR-V requirements.

1196Modified |=sortBlocks(F);

1197

1198returnModified;

1199 }

1200

1201voidgetAnalysisUsage(AnalysisUsage &AU) const override{

1202 AU.addRequired<DominatorTreeWrapperPass>();

1203 AU.addRequired<LoopInfoWrapperPass>();

1204 AU.addRequired<SPIRVConvergenceRegionAnalysisWrapperPass>();

1205

1206 AU.addPreserved<SPIRVConvergenceRegionAnalysisWrapperPass>();

1207FunctionPass::getAnalysisUsage(AU);

1208 }

1209

1210voidcreateOpSelectMerge(IRBuilder<> *Builder,BlockAddress *MergeAddress) {

1211Instruction *BBTerminatorInst = Builder->GetInsertBlock()->getTerminator();

1212

1213MDNode *MDNode = BBTerminatorInst->getMetadata("hlsl.controlflow.hint");

1214

1215ConstantInt *BranchHint = llvm::ConstantInt::get(Builder->getInt32Ty(), 0);

1216

1217if (MDNode) {

1218assert(MDNode->getNumOperands() == 2 &&

1219"invalid metadata hlsl.controlflow.hint");

1220 BranchHint = mdconst::extract<ConstantInt>(MDNode->getOperand(1));

1221

1222assert(BranchHint &&"invalid metadata value for hlsl.controlflow.hint");

1223 }

1224

1225llvm::SmallVector<llvm::Value *, 2> Args = {MergeAddress, BranchHint};

1226

1227 Builder->CreateIntrinsic(Intrinsic::spv_selection_merge,

1228 {MergeAddress->getType()}, {Args});

1229 }

1230};

1231}// namespace llvm

1232

1233charSPIRVStructurizer::ID = 0;

1234

1235INITIALIZE_PASS_BEGIN(SPIRVStructurizer,"spirv-structurizer",

1236"structurize SPIRV",false,false)

1237INITIALIZE_PASS_DEPENDENCY(LoopSimplify)

1238INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)

1239INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)

1240INITIALIZE_PASS_DEPENDENCY(SPIRVConvergenceRegionAnalysisWrapperPass)

1241

1242INITIALIZE_PASS_END(SPIRVStructurizer, "spirv-structurizer",

1243 "structurizeSPIRV",false,false)

1244

1245FunctionPass *llvm::createSPIRVStructurizerPass() {

1246returnnewSPIRVStructurizer();

1247}

1248

1249PreservedAnalyses SPIRVStructurizerWrapper::run(Function &F,

1250FunctionAnalysisManager &AF) {

1251

1252auto FPM =legacy::FunctionPassManager(F.getParent());

1253 FPM.add(createSPIRVStructurizerPass());

1254

1255if (!FPM.run(F))

1256returnPreservedAnalyses::all();

1257PreservedAnalyses PA;

1258 PA.preserveSet<CFGAnalyses>();

1259return PA;

1260}

for

for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))

Definition:AArch64ExpandPseudoInsts.cpp:115

ToRemove

ReachingDefAnalysis InstSet & ToRemove

Definition:ARMLowOverheadLoops.cpp:531

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Definition:ARMSLSHardening.cpp:73

Cloning.h

DenseMap.h

This file defines the DenseMap class.

Dominators.h

#define op(i)

IRBuilder.h

IRTranslator LLVM IR MI

Definition:IRTranslator.cpp:112

CFG.h

This file provides various utilities for inspecting and working with the control flow graph in LLVM I...

LoopDeletionResult::Modified

@ Modified

LoopInfo.h

LoopSimplify.h

LowerMemIntrinsics.h

#define F(x, y, z)

Definition:MD5.cpp:55

#define I(x, y, z)

Definition:MD5.cpp:58

uint64_t IntrinsicInst * II

Definition:NVVMIntrRange.cpp:51

if(PassOpts->AAPipeline)

Definition:PassBuilderBindings.cpp:64

PassRegistry.h

INITIALIZE_PASS_DEPENDENCY

#define INITIALIZE_PASS_DEPENDENCY(depName)

Definition:PassSupport.h:55

INITIALIZE_PASS_END

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

Definition:PassSupport.h:57

INITIALIZE_PASS_BEGIN

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

Definition:PassSupport.h:52

Merge

R600 Clause Merge

Definition:R600ClauseMergePass.cpp:70

assert

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

SPIRVConvergenceRegionAnalysis.h

visit

void visit(MachineFunction &MF, MachineBasicBlock &Start, std::function< void(MachineBasicBlock *)> op)

Definition:SPIRVPostLegalizer.cpp:132

SPIRVStructurizerWrapper.h

structurizer

spirv structurizer

Definition:SPIRVStructurizer.cpp:1242

SPIRV

spirv structurize SPIRV

Definition:SPIRVStructurizer.cpp:1243

This file defines the SmallPtrSet class.

Utils.h

RHS

Value * RHS

Definition:X86PartialReduction.cpp:74

LHS

Value * LHS

Definition:X86PartialReduction.cpp:73

Node

Definition:ItaniumDemangle.h:163

llvm::AllocaInst

an instruction to allocate memory on the stack

Definition:Instructions.h:63

llvm::AnalysisManager

A container for analyses that lazily runs them and caches their results.

Definition:PassManager.h:253

llvm::AnalysisUsage

Represent the analysis usage information of a pass.

Definition:PassAnalysisSupport.h:47

llvm::AnalysisUsage::addRequired

AnalysisUsage & addRequired()

Definition:PassAnalysisSupport.h:75

llvm::AnalysisUsage::addPreserved

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

Definition:PassAnalysisSupport.h:98

llvm::BasicBlock

LLVM Basic Block Representation.

Definition:BasicBlock.h:61

llvm::BasicBlock::Create

static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)

Creates a new BasicBlock.

Definition:BasicBlock.h:213

llvm::BasicBlock::getUniqueSuccessor

const BasicBlock * getUniqueSuccessor() const

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

Definition:BasicBlock.cpp:509

llvm::BasicBlock::getParent

const Function * getParent() const

Return the enclosing method, or null if none.

Definition:BasicBlock.h:220

llvm::BasicBlock::eraseFromParent

SymbolTableList< BasicBlock >::iterator eraseFromParent()

Unlink 'this' from the containing function and delete it.

Definition:BasicBlock.cpp:279

llvm::BasicBlock::iterator

InstListType::iterator iterator

Instruction iterators...

Definition:BasicBlock.h:177

llvm::BasicBlock::size

size_t size() const

Definition:BasicBlock.h:472

llvm::BasicBlock::getTerminator

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.h:240

llvm::BlockAddress

The address of a basic block.

Definition:Constants.h:893

llvm::BlockAddress::getBasicBlock

BasicBlock * getBasicBlock() const

Definition:Constants.h:924

llvm::BlockAddress::get

static BlockAddress * get(Function *F, BasicBlock *BB)

Return a BlockAddress for the specified function and basic block.

Definition:Constants.cpp:1897

llvm::BranchInst

Conditional or Unconditional Branch instruction.

Definition:Instructions.h:3016

llvm::BranchInst::getSuccessor

BasicBlock * getSuccessor(unsigned i) const

Definition:Instructions.h:3104

llvm::CFGAnalyses

Represents analyses that only rely on functions' control flow.

Definition:Analysis.h:72

llvm::CmpInst::ICMP_EQ

@ ICMP_EQ

equal

Definition:InstrTypes.h:694

llvm::ConstantInt

This is the shared class of boolean and integer constants.

Definition:Constants.h:83

llvm::Constant

This is an important base class in LLVM.

Definition:Constant.h:42

llvm::Constant::isConstantUsed

bool isConstantUsed() const

Return true if the constant has users other than constant expressions and other dangling things.

Definition:Constants.cpp:639

llvm::Constant::destroyConstant

void destroyConstant()

Called if some element of this constant is no longer valid.

Definition:Constants.cpp:489

llvm::DWARFExpression::Operation

This class represents an Operation in the Expression.

Definition:DWARFExpression.h:32

llvm::DataLayout

A parsed version of the target data layout string in and methods for querying it.

Definition:DataLayout.h:63

llvm::DenseMapBase::count

size_type count(const_arg_type_t< KeyT > Val) const

Return 1 if the specified key is in the map, 0 otherwise.

Definition:DenseMap.h:152

llvm::DenseMapBase::at

const ValueT & at(const_arg_type_t< KeyT > Val) const

at - Return the entry for the specified key, or abort if no such entry exists.

Definition:DenseMap.h:202

llvm::DenseMap

Definition:DenseMap.h:727

llvm::DomTreeNodeBase::getIDom

DomTreeNodeBase * getIDom() const

Definition:GenericDomTree.h:90

llvm::DomTreeNodeBase::getBlock

NodeT * getBlock() const

Definition:GenericDomTree.h:89

llvm::DominatorTreeBase

Core dominator tree base class.

Definition:GenericDomTree.h:237

llvm::DominatorTreeBase::dominates

bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const

dominates - Returns true iff A dominates B.

Definition:GenericDomTree.h:467

llvm::DominatorTreeBase::recalculate

void recalculate(ParentType &Func)

recalculate - compute a dominator tree for the given function

Definition:GenericDomTree.h:859

llvm::DominatorTreeBase::getNode

DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const

getNode - return the (Post)DominatorTree node for the specified basic block.

Definition:GenericDomTree.h:401

llvm::DominatorTreeWrapperPass

Legacy analysis pass which computes a DominatorTree.

Definition:Dominators.h:317

llvm::DominatorTree::dominates

bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

Definition:Dominators.cpp:122

llvm::FunctionPass

FunctionPass class - This class is used to implement most global optimizations.

Definition:Pass.h:310

llvm::Function

Definition:Function.h:63

llvm::IRBuilderBase::CreateUnreachable

UnreachableInst * CreateUnreachable()

Definition:IRBuilder.h:1306

llvm::IRBuilderBase::getTrue

ConstantInt * getTrue()

Get the constant value for i1 true.

Definition:IRBuilder.h:485

llvm::IRBuilderBase::CreateSelect

Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)

Definition:IRBuilder.cpp:1053

llvm::IRBuilderBase::getInt32Ty

IntegerType * getInt32Ty()

Fetch the type representing a 32-bit integer.

Definition:IRBuilder.h:545

llvm::IRBuilderBase::GetInsertBlock

BasicBlock * GetInsertBlock() const

Definition:IRBuilder.h:193

llvm::IRBuilderBase::CreateIntrinsic

CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, FMFSource FMFSource={}, const Twine &Name="")

Create a call to intrinsic ID with Args, mangled using Types.

Definition:IRBuilder.cpp:900

llvm::IRBuilderBase::getInt32

ConstantInt * getInt32(uint32_t C)

Get a constant 32-bit value.

Definition:IRBuilder.h:505

llvm::IRBuilderBase::CreateCmp

Value * CreateCmp(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)

Definition:IRBuilder.h:2404

llvm::IRBuilderBase::CreateSwitch

SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)

Create a switch instruction with the specified value, default dest, and with a hint for the number of...

Definition:IRBuilder.h:1187

llvm::IRBuilderBase::CreateCondBr

BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)

Create a conditional 'br Cond, TrueDest, FalseDest' instruction.

Definition:IRBuilder.h:1164

llvm::IRBuilderBase::CreateLoad

LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)

Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...

Definition:IRBuilder.h:1798

llvm::IRBuilderBase::CreateStore

StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)

Definition:IRBuilder.h:1811

llvm::IRBuilderBase::getFalse

ConstantInt * getFalse()

Get the constant value for i1 false.

Definition:IRBuilder.h:490

llvm::IRBuilderBase::CreateBr

BranchInst * CreateBr(BasicBlock *Dest)

Create an unconditional 'br label X' instruction.

Definition:IRBuilder.h:1158

llvm::IRBuilderBase::SetInsertPoint

void SetInsertPoint(BasicBlock *TheBB)

This specifies that created instructions should be appended to the end of the specified block.

Definition:IRBuilder.h:199

llvm::IRBuilder

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

Definition:IRBuilder.h:2705

llvm::Instruction

Definition:Instruction.h:68

llvm::Instruction::eraseFromParent

InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

Definition:Instruction.cpp:94

llvm::Instruction::getMetadata

MDNode * getMetadata(unsigned KindID) const

Get the metadata of given kind attached to this Instruction.

Definition:Instruction.h:407

llvm::IntrinsicInst

A wrapper class for inspecting calls to intrinsic functions.

Definition:IntrinsicInst.h:48

llvm::LoopInfoBase::isLoopHeader

bool isLoopHeader(const BlockT *BB) const

Definition:GenericLoopInfo.h:619

llvm::LoopInfoBase::getLoopFor

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

Definition:GenericLoopInfo.h:606

llvm::LoopInfoWrapperPass

The legacy pass manager's analysis pass to compute loop information.

Definition:LoopInfo.h:593

llvm::LoopInfo

Definition:LoopInfo.h:407

llvm::MDNode

Metadata node.

Definition:Metadata.h:1073

llvm::MDNode::getOperand

const MDOperand & getOperand(unsigned I) const

Definition:Metadata.h:1434

llvm::MDNode::getNumOperands

unsigned getNumOperands() const

Return number of MDNode operands.

Definition:Metadata.h:1440

llvm::PartialOrderingVisitor

Definition:SPIRVUtils.h:69

llvm::PassRegistry

PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...

Definition:PassRegistry.h:37

llvm::PassRegistry::getPassRegistry

static PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

Definition:PassRegistry.cpp:24

llvm::Pass::getAnalysisUsage

virtual void getAnalysisUsage(AnalysisUsage &) const

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

Definition:Pass.cpp:98

llvm::PreservedAnalyses

A set of analyses that are preserved following a run of a transformation pass.

Definition:Analysis.h:111

llvm::PreservedAnalyses::all

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

Definition:Analysis.h:117

llvm::PreservedAnalyses::preserveSet

void preserveSet()

Mark an analysis set as preserved.

Definition:Analysis.h:146

llvm::SPIRVConvergenceRegionAnalysisWrapperPass

Definition:SPIRVConvergenceRegionAnalysis.h:141

llvm::SPIRVStructurizerWrapper::run

PreservedAnalyses run(Function &M, FunctionAnalysisManager &AM)

Definition:SPIRVStructurizer.cpp:1249

llvm::SPIRVStructurizer

Definition:SPIRVStructurizer.cpp:295

llvm::SPIRVStructurizer::getAnalysisUsage

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

Definition:SPIRVStructurizer.cpp:1201

llvm::SPIRVStructurizer::SPIRVStructurizer

SPIRVStructurizer()

Definition:SPIRVStructurizer.cpp:1131

llvm::SPIRVStructurizer::createOpSelectMerge

void createOpSelectMerge(IRBuilder<> *Builder, BlockAddress *MergeAddress)

Definition:SPIRVStructurizer.cpp:1210

llvm::SPIRVStructurizer::runOnFunction

virtual bool runOnFunction(Function &F) override

runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.

Definition:SPIRVStructurizer.cpp:1135

llvm::SPIRVStructurizer::ID

static char ID

Definition:SPIRVStructurizer.cpp:1129

llvm::SPIRV::ConvergenceRegion

Definition:SPIRVConvergenceRegionAnalysis.h:42

llvm::SPIRV::ConvergenceRegion::Exits

SmallPtrSet< BasicBlock *, 2 > Exits

Definition:SPIRVConvergenceRegionAnalysis.h:56

llvm::SPIRV::ConvergenceRegion::Blocks

SmallPtrSet< BasicBlock *, 8 > Blocks

Definition:SPIRVConvergenceRegionAnalysis.h:58

llvm::SmallPtrSetImplBase::reserve

void reserve(size_type NumEntries)

Definition:SmallPtrSet.h:112

llvm::SmallPtrSetImpl::insert

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

Definition:SmallPtrSet.h:384

llvm::SmallPtrSetImpl::contains

bool contains(ConstPtrType Ptr) const

Definition:SmallPtrSet.h:458

llvm::SmallPtrSet

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

Definition:SmallPtrSet.h:519

llvm::SmallVector

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

Definition:SmallVector.h:1196

llvm::SwitchInst

Multiway switch.

Definition:Instructions.h:3154

llvm::SwitchInst::addCase

void addCase(ConstantInt *OnVal, BasicBlock *Dest)

Add an entry to the switch instruction.

Definition:Instructions.cpp:4011

llvm::Target

Target - Wrapper for Target specific information.

Definition:TargetRegistry.h:144

llvm::Type

The instances of the Type class are immutable: once they are created, they are never changed.

Definition:Type.h:45

llvm::Value

LLVM Value Representation.

Definition:Value.h:74

llvm::Value::getType

Type * getType() const

All values are typed, get the type of this value.

Definition:Value.h:255

llvm::ilist_node_with_parent::getPrevNode

NodeTy * getPrevNode()

Definition:ilist_node.h:339

llvm::legacy::FunctionPassManager

FunctionPassManager manages FunctionPasses.

Definition:LegacyPassManager.h:71

unsigned

llvm_unreachable

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

Definition:ErrorHandling.h:143

false

Definition:StackSlotColoring.cpp:193

llvm::CallingConv::C

@ C

The default llvm calling convention, compatible with C.

Definition:CallingConv.h:34

llvm::M68k::MemAddrModeKind::V

@ V

llvm::SIEncodingFamily::SI

@ SI

Definition:SIDefines.h:36

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::createSPIRVStructurizerPass

FunctionPass * createSPIRVStructurizerPass()

Definition:SPIRVStructurizer.cpp:1245

llvm::PseudoProbeType::Block

@ Block

llvm::size

auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)

Get the size of a range.

Definition:STLExtras.h:1697

llvm::Successor

@ Successor

Definition:SIMachineScheduler.h:35

llvm::AlignStyle::Right

@ Right

llvm::AlignStyle::Left

@ Left

llvm::successors

auto successors(const MachineBasicBlock *BB)

Definition:MachineBasicBlock.h:1376

llvm::sortBlocks

bool sortBlocks(Function &F)

Definition:SPIRVUtils.cpp:679

llvm::pred_size

auto pred_size(const MachineBasicBlock *BB)

Definition:MachineBasicBlock.h:1381

llvm::succ_size

auto succ_size(const MachineBasicBlock *BB)

Definition:MachineBasicBlock.h:1380

llvm::initializeSPIRVStructurizerPass

void initializeSPIRVStructurizerPass(PassRegistry &)

llvm::predecessors

auto predecessors(const MachineBasicBlock *BB)

Definition:MachineBasicBlock.h:1377

llvm::Continue

@ Continue

Definition:DWP.h:21

InsertionPoint

Definition:CFIFixup.cpp:129