SPIRVStructurizer.cpp Source File (original) (raw)

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

31#include

32#include <unordered_set>

34using namespace llvm;

35using namespace SPIRV;

37using BlockSet = std::unordered_set<BasicBlock *>;

38using Edge = std::pair<BasicBlock *, BasicBlock *>;

45 V.partialOrderVisit(Start, std::move(Op));

46}

52 if (Node->Entry == BB)

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

57 if (CR != nullptr)

58 return CR;

59 }

60 return nullptr;

61}

66 std::unordered_set<BasicBlock *> ExitTargets;

71 }

72 }

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

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

76 return nullptr;

78 return *ExitTargets.begin();

79}

85 if (II == nullptr)

86 return nullptr;

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

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

90 return nullptr;

94}

100 if (II == nullptr)

101 return nullptr;

102

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

104 return nullptr;

105

108}

109

110

111

113 for (auto &I : Header) {

115 if (MB == &Merge)

116 return true;

117 }

118 return false;

119}

120

121

123 for (auto &I : BB)

125 return true;

126 return false;

127}

128

129

130

134

135

136

143 }

144 }

145 return Output;

146}

147

148

149

155 if (MB != nullptr)

157 }

158 }

159 return Output;

160}

161

162

163

164

166 std::vector<Instruction *> Output;

169 Output.push_back(&I);

170 return Output;

171}

172

173

174

180 if (MB != nullptr)

182 }

183 }

184 return Output;

185}

186

187

188

190 std::stack<BasicBlock *> ToVisit;

192

193 ToVisit.push(&Start);

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

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

197 ToVisit.pop();

198

199 if ((BB))

200 continue;

201

204 continue;

205 ToVisit.push(Succ);

207 }

208 }

209}

210

211

212

213

217

218

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

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

221 BI->setSuccessor(i, NewTarget);

222 }

223

224

225 if (BI->isUnconditional())

226 return;

227

228

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

230 return;

231

232

233

235 Builder.SetInsertPoint(BI);

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

237 BI->eraseFromParent();

238

239

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

241 return;

242

243

244

245

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

249 return;

250

252 II->eraseFromParent();

253 if (->isConstantUsed())

254 C->destroyConstant();

255}

256

257

258

259

260

265 return;

266

269

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

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

273 SI->setSuccessor(i, NewTarget);

274 }

275 return;

276 }

277

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

279}

280

281namespace {

282

283

284class SPIRVStructurizer : public FunctionPass {

285 struct DivergentConstruct;

286

287

288

289 using ConstructList = std::vector<std::unique_ptr>;

290

291

292

293

294

295 struct DivergentConstruct {

299

300 DivergentConstruct *Parent = nullptr;

301 ConstructList Children;

302 };

303

304

305

306

307

308 struct Splitter {

310 LoopInfo &LI;

313

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

315

316 void invalidate() {

317 PDT.recalculate(F);

318 DT.recalculate(F);

319 }

320

321

322

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

324 BasicBlock *Merge) {

326 std::vector<BasicBlock *> Output;

329 return false;

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

331 return false;

332 Output.push_back(BB);

333 return true;

334 });

335 return Output;

336 }

337

338

339 std::vector<BasicBlock *>

340 getSelectionConstructBlocks(DivergentConstruct *Node) {

343 OutsideBlocks.insert(Node->Merge);

344

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

346 It = It->Parent) {

347 OutsideBlocks.insert(It->Merge);

348 if (It->Continue)

349 OutsideBlocks.insert(It->Continue);

350 }

351

352 std::vector<BasicBlock *> Output;

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

355 return false;

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

357 return false;

358 Output.push_back(BB);

359 return true;

360 });

361 return Output;

362 }

363

364

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

366 BasicBlock *Merge) {

368

369 std::vector<BasicBlock *> Output;

371

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

373 return false;

374

375

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

377 return false;

378 Output.push_back(BB);

379 return true;

380 });

381 return Output;

382 }

383

384

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

386 BasicBlock *Merge) {

388

389 std::vector<BasicBlock *> Output;

391

392

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

394 return false;

395

396

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

398 return false;

399 Output.push_back(BB);

400 return true;

401 });

402 return Output;

403 }

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427 std::vector

428 createAliasBlocksForComplexEdges(std::vector Edges) {

429 std::unordered_set<BasicBlock *> Seen;

430 std::vector Output;

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

432

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

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

435 if (!Inserted) {

436

437

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

442 Builder.CreateBr(Dst);

443 Src = NewSrc;

444 }

445

446 Output.emplace_back(Src, Dst);

447 }

448

449 return Output;

450 }

451

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

454 const DataLayout &DL = F.getDataLayout();

455 return new AllocaInst(Type, DL.getAllocaAddrSpace(), nullptr, "reg",

456 Position);

457 }

458

459

460

461 BasicBlock *createSingleExitNode(BasicBlock *Header,

462 std::vector &Edges) {

463

464 std::vector FixedEdges = createAliasBlocksForComplexEdges(Edges);

465

466 std::vector<BasicBlock *> Dsts;

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

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

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

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

473 continue;

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

475 Dsts.push_back(Dst);

476 }

477

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

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

481 }

482 ExitBuilder.CreateBr(Dsts[0]);

483 return NewExit;

484 }

485

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

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

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

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

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

493 }

494

495 Value *Load = ExitBuilder.CreateLoad(ExitBuilder.getInt32Ty(), Variable);

496

497

498

499

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

501 Value *Condition =

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

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

504 return NewExit;

505 }

506

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

508 for (BasicBlock *BB : drop_begin(Dsts))

509 Sw->addCase(DstToIndex[BB], BB);

510 return NewExit;

511 }

512 };

513

514

515

516 Value *createExitVariable(

517 BasicBlock *BB,

518 const DenseMap<BasicBlock *, ConstantInt *> &TargetToValue) {

521 return nullptr;

522

524 Builder.SetInsertPoint(T);

525

527

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

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

531

534

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

536 return LHS == nullptr ? RHS : LHS;

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

538 }

539

540

542 }

543

544

545 BasicBlock *CreateUnreachable(Function &F) {

548 Builder.CreateUnreachable();

549 return BB;

550 }

551

552

553 bool addMergeForLoops(Function &F) {

554 LoopInfo &LI = getAnalysis().getLoopInfo();

555 auto *TopLevelRegion =

556 getAnalysis()

557 .getRegionInfo()

558 .getTopLevelRegion();

559

561 for (auto &BB : F) {

562

564 continue;

566

567

568

570 if (CR == nullptr)

571 continue;

572

574

576

577

578

579

580

581

582 if (Merge == nullptr) {

585

586 Merge = CreateUnreachable(F);

587 Builder.SetInsertPoint(Br);

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

590 }

591

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

593

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

600 for (unsigned Imm : LoopControlImms)

601 Args.emplace_back(ConstantInt::get(Builder.getInt32Ty(), Imm));

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

604 }

605

607 }

608

609

610

611

612 bool addMergeForNodesWithMultiplePredecessors(Function &F) {

615

617 for (auto &BB : F) {

619 continue;

620

622 continue;

623

626

628 continue;

629

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

632

634 createOpSelectMerge(&Builder, MergeAddress);

635

637 }

638

640 }

641

642

643

644

645

646

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

648 std::vector<Instruction *> MergeInstructions;

649 for (Instruction &I : Block)

651 MergeInstructions.push_back(&I);

652

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

654 return false;

655

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

657

658 PartialOrderingVisitor Visitor(F);

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

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

661 if (Left == Right)

662 return false;

663 BasicBlock *RightMerge = getDesignatedMergeBlock(Right);

664 BasicBlock *LeftMerge = getDesignatedMergeBlock(Left);

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

666 });

667

668 for (Instruction *I : MergeInstructions) {

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

670 InsertionPoint = I;

671 }

672

673 return true;

674 }

675

676

677

678

679 bool sortSelectionMergeHeaders(Function &F) {

681 for (BasicBlock &BB : F) {

682 Modified |= sortSelectionMerge(F, BB);

683 }

685 }

686

687

688

689 bool splitBlocksWithMultipleHeaders(Function &F) {

690 std::stack<BasicBlock *> Work;

691 for (auto &BB : F) {

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

694 continue;

695 Work.push(&BB);

696 }

697

698 const bool Modified = Work.size() > 0;

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

701 Work.pop();

702

703 std::vector<Instruction *> MergeInstructions =

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

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

708

710 BasicBlock *Unreachable = CreateUnreachable(F);

711

714 Builder.SetInsertPoint(BI);

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

717 }

718

719 Header = NewBlock;

720 }

721 }

722

724 }

725

726

727

728 bool addMergeForDivergentBlocks(Function &F) {

732

735

736 for (auto &BB : F) {

738 continue;

739

740 std::vector<BasicBlock *> Candidates;

742 if (MergeBlocks.contains(Successor))

743 continue;

744 if (ContinueBlocks.contains(Successor))

745 continue;

747 }

748

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

750 continue;

751

754

758 createOpSelectMerge(&Builder, MergeAddress);

759 }

760

762 }

763

764

765

766 std::vector getExitsFrom(const BlockSet &Construct,

767 BasicBlock &Header) {

768 std::vector Output;

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

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

771 return false;

772

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

775 Output.emplace_back(Item, Successor);

776 }

777 return true;

778 });

779

780 return Output;

781 }

782

783

784

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

786 BasicBlock *BB, DivergentConstruct *Parent) {

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

788 return;

789 Visited.insert(BB);

790

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

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

795 return;

796 }

797

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

800

803

804 auto Output = std::make_unique();

805 Output->Header = BB;

806 Output->Merge = Merge;

808 Output->Parent = Parent;

809

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

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

813

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

816

817 if (Parent)

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

819 }

820

821

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

824

825 if (Node->Continue) {

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

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

828 }

829

830 auto SelectionBlocks = S.getSelectionConstructBlocks(Node);

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

832 }

833

834

835

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

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

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

840

841

842

843 if (Node->Parent == nullptr)

845

846

847

848

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

851

852

855

856 BlockSet ConstructBlocks = getConstructBlocks(S, Node);

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

858

859

860 if (Edges.size() < 1)

862

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

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

865

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

867

868

869

870

871

872

873 if (Node->Merge == Dst)

874 continue;

875

876

877

878 if (Node->Continue == Dst)

879 continue;

880

881

882

883 HasBadEdge = true;

884 }

885

886 if (!HasBadEdge)

888

889

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

891

892

893

894

895

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

902 I->setOperand(0, MergeAddress);

903 }

904

905

906

909

910 Node->Merge = NewExit;

911

912 S.invalidate();

913 return true;

914 }

915

916 bool splitCriticalEdges(Function &F) {

917 LoopInfo &LI = getAnalysis().getLoopInfo();

918 Splitter S(F, LI);

919

920 DivergentConstruct Root;

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

923 return fixupConstruct(S, &Root);

924 }

925

926

927

928

929

930

931 bool simplifyBranches(Function &F) {

933

934 for (BasicBlock &BB : F) {

936 if (!SI)

937 continue;

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

939 continue;

940

943 Builder.SetInsertPoint(SI);

944

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

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

947 } else {

948 Value *Condition =

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

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

952 SI->getDefaultDest());

953 }

954 SI->eraseFromParent();

955 }

956

958 }

959

960

961

962

963 bool splitSwitchCases(Function &F) {

965

966 for (BasicBlock &BB : F) {

968 if (!SI)

969 continue;

970

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

973

974 auto It = SI->case_begin();

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

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

978 Seen.insert(Target);

979 ++It;

980 continue;

981 }

982

987 Builder.CreateBr(Target);

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

989 It = SI->removeCase(It);

990 }

991 }

992

994 }

995

996

997

998 bool removeUselessBlocks(Function &F) {

999 std::vector<BasicBlock *> ToRemove;

1000

1003

1004 for (BasicBlock &BB : F) {

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

1006 continue;

1007

1009 continue;

1010

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

1012 continue;

1013

1015 continue;

1016

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

1020 for (BasicBlock *Predecessor : Predecessors)

1023 }

1024

1025 for (BasicBlock *BB : ToRemove)

1027

1028 return ToRemove.size() != 0;

1029 }

1030

1031 bool addHeaderToRemainingDivergentDAG(Function &F) {

1033

1037

1042

1043 for (BasicBlock &BB : F) {

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

1045 continue;

1047 continue;

1048

1049 size_t CandidateEdges = 0;

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

1052 ContinueBlocks.count(Successor) != 0)

1053 continue;

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

1055 continue;

1056 CandidateEdges += 1;

1057 }

1058

1059 if (CandidateEdges <= 1)

1060 continue;

1061

1064

1065 bool HasBadBlock = false;

1066 visit(*Header, [&](const BasicBlock *Node) {

1068 return false;

1070 return false;

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

1072 return true;

1073

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

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

1076 HeaderBlocks.count(Node) != 0;

1077 return !HasBadBlock;

1078 });

1079

1080 if (HasBadBlock)

1081 continue;

1082

1084

1085 if (Merge == nullptr) {

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

1089

1091 createOpSelectMerge(&Builder, MergeAddress);

1092 continue;

1093 }

1094

1097 SplitInstruction = SplitInstruction->getPrevNode();

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

1100

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

1103

1105 createOpSelectMerge(&Builder, MergeAddress);

1106 }

1107

1109 }

1110

1111public:

1112 static char ID;

1113

1114 SPIRVStructurizer() : FunctionPass(ID) {}

1115

1118

1119

1120

1121

1122 Modified |= splitSwitchCases(F);

1123

1124

1125

1126

1127 Modified |= simplifyBranches(F);

1128

1129

1130

1131 Modified |= addMergeForLoops(F);

1132

1133

1134 Modified |= addMergeForNodesWithMultiplePredecessors(F);

1135

1136

1137

1138

1139 Modified |= sortSelectionMergeHeaders(F);

1140

1141

1142

1143

1144 Modified |= splitBlocksWithMultipleHeaders(F);

1145

1146

1147

1148

1149

1150 Modified |= addMergeForDivergentBlocks(F);

1151

1152

1153

1154

1155

1156

1157

1158 Modified |= splitCriticalEdges(F);

1159

1160

1161

1162

1163

1164

1165

1166

1167

1168

1169 Modified |= removeUselessBlocks(F);

1170

1171

1172

1173

1174 Modified |= addHeaderToRemainingDivergentDAG(F);

1175

1176

1178

1180 }

1181

1182 void getAnalysisUsage(AnalysisUsage &AU) const override {

1183 AU.addRequired();

1185 AU.addRequired();

1186

1187 AU.addPreserved();

1188 FunctionPass::getAnalysisUsage(AU);

1189 }

1190

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

1193

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

1195

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

1197

1198 if (MDNode) {

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

1202 }

1203

1204 SmallVector<Value *, 2> Args = {MergeAddress, BranchHint};

1205

1206 Builder->CreateIntrinsic(Intrinsic::spv_selection_merge,

1208 }

1209};

1210}

1211

1212char SPIRVStructurizer::ID = 0;

1213

1215 "structurize SPIRV", false, false)

1220

1223

1225 return new SPIRVStructurizer();

1226}

1227

1230

1233

1234 if (!FPM.run(F))

1238 return PA;

1239}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

ReachingDefInfo InstSet & ToRemove

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

This file defines the DenseMap class.

static bool runOnFunction(Function &F, bool PostInlining)

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

uint64_t IntrinsicInst * II

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

static BasicBlock * getDesignatedMergeBlock(Instruction *I)

Definition SPIRVStructurizer.cpp:83

static void visit(BasicBlock &Start, std::function< bool(BasicBlock *)> op)

Definition SPIRVStructurizer.cpp:189

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

Definition SPIRVStructurizer.cpp:165

static BasicBlock * getDesignatedContinueBlock(Instruction *I)

Definition SPIRVStructurizer.cpp:98

std::unordered_set< BasicBlock * > BlockSet

Definition SPIRVStructurizer.cpp:37

static const ConvergenceRegion * getRegionForHeader(const ConvergenceRegion *Node, BasicBlock *BB)

Definition SPIRVStructurizer.cpp:51

static bool hasLoopMergeInstruction(BasicBlock &BB)

Definition SPIRVStructurizer.cpp:122

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

Definition SPIRVStructurizer.cpp:175

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

Definition SPIRVStructurizer.cpp:150

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

Definition SPIRVStructurizer.cpp:137

static bool isDefinedAsSelectionMergeBy(BasicBlock &Header, BasicBlock &Merge)

Definition SPIRVStructurizer.cpp:112

static void replaceBranchTargets(BasicBlock *BB, BasicBlock *OldTarget, BasicBlock *NewTarget)

Definition SPIRVStructurizer.cpp:261

static void partialOrderVisit(BasicBlock &Start, std::function< bool(BasicBlock *)> Op)

Definition SPIRVStructurizer.cpp:42

static bool isMergeInstruction(Instruction *I)

Definition SPIRVStructurizer.cpp:131

static BasicBlock * getExitFor(const ConvergenceRegion *CR)

Definition SPIRVStructurizer.cpp:65

static void replaceIfBranchTargets(BasicBlock *BB, BasicBlock *OldTarget, BasicBlock *NewTarget)

Definition SPIRVStructurizer.cpp:214

This file defines the SmallPtrSet class.

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

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

LLVM Basic Block Representation.

const Function * getParent() const

Return the enclosing method, or null if none.

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

Creates a new BasicBlock.

LLVM_ABI const BasicBlock * getUniqueSuccessor() const

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

LLVM_ABI SymbolTableList< BasicBlock >::iterator eraseFromParent()

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

InstListType::iterator iterator

Instruction iterators...

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

The address of a basic block.

BasicBlock * getBasicBlock() const

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

Return a BlockAddress for the specified function and basic block.

BasicBlock * getSuccessor(unsigned i) const

bool isUnconditional() const

Represents analyses that only rely on functions' control flow.

This is an important base class in LLVM.

LLVM_ABI bool isConstantUsed() const

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

LLVM_ABI void destroyConstant()

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

ValueT lookup(const_arg_type_t< KeyT > Val) const

lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...

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

dominates - Returns true iff A dominates B.

void recalculate(ParentType &Func)

recalculate - compute a dominator tree for the given function

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

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

Legacy analysis pass which computes a DominatorTree.

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

IntegerType * getInt32Ty()

Fetch the type representing a 32-bit integer.

BasicBlock * GetInsertBlock() const

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

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

LLVM_ABI InstListType::iterator eraseFromParent()

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

MDNode * getMetadata(unsigned KindID) const

Get the metadata of given kind attached to this Instruction.

A wrapper class for inspecting calls to intrinsic functions.

bool isLoopHeader(const BlockT *BB) const

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

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

const MDOperand & getOperand(unsigned I) const

unsigned getNumOperands() const

Return number of MDNode operands.

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

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

PreservedAnalyses & preserveSet()

Mark an analysis set as preserved.

PreservedAnalyses run(Function &M, FunctionAnalysisManager &AM)

Definition SPIRVStructurizer.cpp:1228

SmallPtrSet< BasicBlock *, 2 > Exits

SmallPtrSet< BasicBlock *, 8 > Blocks

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

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

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

bool contains(ConstPtrType Ptr) const

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

LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest)

Add an entry to the switch instruction.

Type * getType() const

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

self_iterator getIterator()

FunctionPassManager manages FunctionPasses.

#define llvm_unreachable(msg)

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

constexpr char Args[]

Key for Kernel::Metadata::mArgs.

@ C

The default llvm calling convention, compatible with C.

PostDomTreeBase< BasicBlock > BBPostDomTree

DomTreeBase< BasicBlock > BBDomTree

@ BasicBlock

Various leaf nodes.

std::enable_if_t< detail::IsValidPointer< X, Y >::value, X * > extract(Y &&MD)

Extract a Value from Metadata.

NodeAddr< NodeBase * > Node

friend class Instruction

Iterator for Instructions in a `BasicBlock.

LLVM_ABI iterator begin() const

This is an optimization pass for GlobalISel generic memory operations.

auto drop_begin(T &&RangeOrContainer, size_t N=1)

Return a range covering RangeOrContainer with the first N elements excluded.

FunctionAddr VTableAddr Value

FunctionPass * createSPIRVStructurizerPass()

Definition SPIRVStructurizer.cpp:1224

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.

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

auto successors(const MachineBasicBlock *BB)

bool sortBlocks(Function &F)

auto pred_size(const MachineBasicBlock *BB)

SmallVector< unsigned, 1 > getSpirvLoopControlOperandsFromLoopMetadata(Loop *L)

auto dyn_cast_or_null(const Y &Val)

auto succ_size(const MachineBasicBlock *BB)

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >

DWARFExpression::Operation Op

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

auto predecessors(const MachineBasicBlock *BB)

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.