StructurizeCFG.cpp Source File (original) (raw)

50#include

51#include

53using namespace llvm;

56#define DEBUG_TYPE "structurizecfg"

61namespace {

64 "structurizecfg-skip-uniform-regions",

66 cl::desc("Force whether the StructurizeCFG pass skips uniform regions"),

70 RelaxedUniformRegions("structurizecfg-relaxed-uniform-regions", cl::Hidden,

71 cl::desc("Allow relaxed uniform region checks"),

76using BBValuePair = std::pair<BasicBlock *, Value *>;

90using MaybeCondBranchWeights = std::optional;

92class CondBranchWeights {

98public:

99 static MaybeCondBranchWeights tryParse(const BranchInst &Br) {

101

104 return std::nullopt;

105

106 return CondBranchWeights(T, F);

107 }

108

109 static void setMetadata(BranchInst &Br,

110 const MaybeCondBranchWeights &Weights) {

112 if (!Weights)

113 return;

114 uint32_t Arr[] = {Weights->TrueWeight, Weights->FalseWeight};

116 }

117

118 CondBranchWeights invert() const {

119 return CondBranchWeights{FalseWeight, TrueWeight};

120 }

121};

122

123struct PredInfo {

125 MaybeCondBranchWeights Weights;

126};

127

131

133

134

135

136

137struct SubGraphTraits {

138 using NodeRef = std::pair<RegionNode *, SmallDenseSet<RegionNode *> *>;

140

141

142

143 class WrappedSuccIterator

145 WrappedSuccIterator, BaseSuccIterator,

146 typename std::iterator_traits::iterator_category,

147 NodeRef, std::ptrdiff_t, NodeRef *, NodeRef> {

149

150 public:

153

154 NodeRef operator*() const { return {*I, Nodes}; }

155 };

156

157 static bool filterAll(const NodeRef &N) { return true; }

158 static bool filterSet(const NodeRef &N) { return N.second->count(N.first); }

159

160 using ChildIteratorType =

162

163 static NodeRef getEntryNode(Region *R) {

165 }

166

167 static NodeRef getEntryNode(NodeRef N) { return N; }

168

170 auto *filter = N.second ? &filterSet : &filterAll;

172 make_range(

175 filter);

176 }

177

178 static ChildIteratorType child_begin(const NodeRef &N) {

180 }

181

182 static ChildIteratorType child_end(const NodeRef &N) {

184 }

185};

186

187

188

189

190

191

192class NearestCommonDominator {

195 bool ResultIsRemembered = false;

196

197

198 void addBlock(BasicBlock *BB, bool Remember) {

199 if (!Result) {

200 Result = BB;

201 ResultIsRemembered = Remember;

202 return;

203 }

204

206 if (NewResult != Result)

207 ResultIsRemembered = false;

208 if (NewResult == BB)

209 ResultIsRemembered |= Remember;

210 Result = NewResult;

211 }

212

213public:

214 explicit NearestCommonDominator(DominatorTree *DomTree) : DT(DomTree) {}

215

217 addBlock(BB, false);

218 }

219

220 void addAndRememberBlock(BasicBlock *BB) {

221 addBlock(BB, true);

222 }

223

224

225

226 BasicBlock *result() { return Result; }

227

228

229

230 bool resultIsRememberedBlock() { return ResultIsRemembered; }

231};

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279class StructurizeCFG {

283 Value *BoolPoison;

284

286 Region *ParentRegion;

287

290

292 BBSet Visited;

293 BBSet FlowSet;

294

296 BBPhiMap DeletedPhis;

297 BB2BBVecMap AddedPhis;

298

299 PredMap Predicates;

300 BranchVector Conditions;

301

303 PredMap LoopPreds;

304 BranchVector LoopConds;

305

306 BranchDebugLocMap TermDL;

307

309

310 void orderNodes();

311

313

314 PredInfo buildCondition(BranchInst *Term, unsigned Idx, bool Invert);

315

317

318 void collectInfos();

319

320 void insertConditions(bool Loops);

321

322 void simplifyConditions();

323

325

327

328 void findUndefBlocks(BasicBlock *PHIBlock,

331

334

335 void setPhiValues();

336

337 void simplifyAffectedPhis();

338

340

342 bool IncludeDominator);

343

345

346 BasicBlock *needPrefix(bool NeedEmpty);

347

349

351

353

355

356 void wireFlow(bool ExitUseAllowed, BasicBlock *LoopEnd);

357

358 void handleLoops(bool ExitUseAllowed, BasicBlock *LoopEnd);

359

360 void createFlow();

361

362 void rebuildSSA();

363

364public:

365 void init(Region *R);

368};

369

370class StructurizeCFGLegacyPass : public RegionPass {

371 bool SkipUniformRegions;

372

373public:

374 static char ID;

375

376 explicit StructurizeCFGLegacyPass(bool SkipUniformRegions_ = false)

377 : RegionPass(ID), SkipUniformRegions(SkipUniformRegions_) {

379 SkipUniformRegions = ForceSkipUniformRegions.getValue();

381 }

382

384 StructurizeCFG SCFG;

385 SCFG.init(R);

386 if (SkipUniformRegions) {

388 getAnalysis().getUniformityInfo();

389 if (SCFG.makeUniformRegion(R, UA))

390 return false;

391 }

392 DominatorTree *DT = &getAnalysis().getDomTree();

393 return SCFG.run(R, DT);

394 }

395

396 StringRef getPassName() const override { return "Structurize control flow"; }

397

399 if (SkipUniformRegions)

402

405 }

406};

407

408}

409

410char StructurizeCFGLegacyPass::ID = 0;

411

413 "Structurize the CFG", false, false)

419

420

421

422

423void StructurizeCFG::orderNodes() {

426 if (Order.empty())

427 return;

428

430 auto EntryNode = SubGraphTraits::getEntryNode(ParentRegion);

431

432

434 unsigned I = 0, E = Order.size();

435 while (true) {

436

437 for (auto SCCI =

439 EntryNode);

440 !SCCI.isAtEnd(); ++SCCI) {

441 auto &SCC = *SCCI;

442

443

444

445

446 unsigned Size = SCC.size();

447 if (Size > 2)

449

450

451 for (const auto &N : SCC) {

452 assert(I < E && "SCC size mismatch!");

453 Order[I++] = N.first;

454 }

455 }

456 assert(I == E && "SCC size mismatch!");

457

458

459 if (WorkList.empty())

460 break;

461

463

464

465

466

468 Nodes.insert(Order.begin() + I, Order.begin() + E - 1);

469

470

471 EntryNode.first = Order[E - 1];

472 EntryNode.second = &Nodes;

473 }

474}

475

476

477void StructurizeCFG::analyzeLoops(RegionNode *N) {

478 if (N->isSubRegion()) {

479

481 if (Visited.count(Exit))

483

484 } else {

485

488

490 if (Visited.count(Succ))

491 Loops[Succ] = BB;

492 }

493}

494

495

496PredInfo StructurizeCFG::buildCondition(BranchInst *Term, unsigned Idx,

497 bool Invert) {

498 Value *Cond = Invert ? BoolFalse : BoolTrue;

499 MaybeCondBranchWeights Weights;

500

501 if (Term->isConditional()) {

503 Weights = CondBranchWeights::tryParse(*Term);

504

505 if (Idx != (unsigned)Invert) {

507 if (Weights)

508 Weights = Weights->invert();

509 }

510 }

511 return {Cond, Weights};

512}

513

514

515void StructurizeCFG::gatherPredicates(RegionNode *N) {

516 RegionInfo *RI = ParentRegion->getRegionInfo();

520

522

523 if (!ParentRegion->contains(P))

524 continue;

525

527 if (R == ParentRegion) {

528

530 for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {

532 if (Succ != BB)

533 continue;

534

535 if (Visited.count(P)) {

536

537 if (Term->isConditional()) {

538

542

543 Pred[Other] = {BoolFalse, std::nullopt};

544 Pred[P] = {BoolTrue, std::nullopt};

545 continue;

546 }

547 }

548 Pred[P] = buildCondition(Term, i, false);

549 } else {

550

551 LPred[P] = buildCondition(Term, i, true);

552 }

553 }

554 } else {

555

556 while (R->getParent() != ParentRegion)

557 R = R->getParent();

558

559

560 if (*R == *N)

561 continue;

562

564 if (Visited.count(Entry))

565 Pred[Entry] = {BoolTrue, std::nullopt};

566 else

567 LPred[Entry] = {BoolFalse, std::nullopt};

568 }

569 }

570}

571

572

573void StructurizeCFG::collectInfos() {

574

575 Predicates.clear();

576

577

579 LoopPreds.clear();

580

581

582 Visited.clear();

583

586 << (RN->isSubRegion() ? "SubRegion with entry: " : "")

587 << RN->getEntry()->getName() << "\n");

588

589

590 gatherPredicates(RN);

591

592

593 Visited.insert(RN->getEntry());

594

595

596 analyzeLoops(RN);

597 }

598

599

600 TermDL.clear();

601

604 TermDL[&BB] = DL;

605 }

606}

607

608

609void StructurizeCFG::insertConditions(bool Loops) {

610 BranchVector &Conds = Loops ? LoopConds : Conditions;

613

616

620

621 BBPredicates &Preds = Loops ? LoopPreds[SuccFalse] : Predicates[SuccTrue];

622

623 if (Preds.size() == 1 && Preds.begin()->first == Parent) {

624 auto &PI = Preds.begin()->second;

625 Term->setCondition(PI.Pred);

626 CondBranchWeights::setMetadata(*Term, PI.Weights);

627 } else {

630

631 NearestCommonDominator Dominator(DT);

632 Dominator.addBlock(Parent);

633

634 for (auto [BB, PI] : Preds) {

635 assert(BB != Parent);

637 Dominator.addAndRememberBlock(BB);

638 }

639

640 if (!Dominator.resultIsRememberedBlock())

642

644 }

645 }

646}

647

648

649void StructurizeCFG::simplifyConditions() {

651 for (auto &I : concatPredMap::value\_type(Predicates, LoopPreds)) {

652 auto &Preds = I.second;

653 for (auto [BB, PI] : Preds) {

656 !PI.Pred->use_empty()) {

657 if (auto *InvertedCmp = dyn_cast(Inverted)) {

658 InvertedCmp->setPredicate(InvertedCmp->getInversePredicate());

660 InstToErase.push_back(cast(PI.Pred));

661 }

662 }

663 }

664 }

665 for (auto *I : InstToErase)

666 I->eraseFromParent();

667}

668

669

670

672 PhiMap &Map = DeletedPhis[To];

674 bool Recorded = false;

675 while (Phi.getBasicBlockIndex(From) != -1) {

678 if (!Recorded) {

679 AffectedPhis.push_back(&Phi);

680 Recorded = true;

681 }

682 }

683 }

684}

685

686

691 }

692 AddedPhis[To].push_back(From);

693}

694

695

696

697

698

699void StructurizeCFG::findUndefBlocks(

702

703

704

705

706

707

708

709

710

711

712

713

714

715

716

717

718

719

720

721

722

723

724

725

728 if (PHIBlock == ParentRegion->getExit()) {

730 if (ParentRegion->contains(P))

732 }

733 } else {

735 }

736

737

738

739

740

741 while ( Stack .empty()) {

743 if (!VisitedBlock.insert(Current).second)

744 continue;

745

746 if (FlowSet.contains(Current)) {

749 } else if (!Incomings.contains(Current)) {

751 }

752 }

753}

754

755

756

757

758

759

760

761void StructurizeCFG::mergeIfCompatible(

765

766 if (ItA == ItB)

767 return;

768

771 BBValueVector &IncomingA = DeletedPhis[LeaderA->getParent()][LeaderA];

772 BBValueVector &IncomingB = DeletedPhis[LeaderB->getParent()][LeaderB];

773

775 for (auto [BB, V] : IncomingB) {

776 auto BBIt = Mergeable.find(BB);

777 if (BBIt != Mergeable.end() && BBIt->second != V)

778 return;

779

780

781 Mergeable.insert({BB, V});

782 }

783

784

785 IncomingA.assign(Mergeable.begin(), Mergeable.end());

787}

788

789

790void StructurizeCFG::setPhiValues() {

794

795

796

797

798

799

800

801

802

803

804

805

806

807

808

809

810

811

812

813

814

815

817 for (const auto &[To, From] : AddedPhis) {

818 auto OldPhiIt = DeletedPhis.find(To);

819 if (OldPhiIt == DeletedPhis.end())

820 continue;

821

822 PhiMap &BlkPhis = OldPhiIt->second;

825

826

827 if (!BlkPhis.empty()) {

828 for (const auto &VI : BlkPhis.front().second)

830 findUndefBlocks(To, Incomings, UndefBlks);

831 }

832

833 for (const auto &[Phi, Incomings] : OldPhiIt->second) {

835 for (const auto &[BB, V] : Incomings) {

836

837

838 if (PHINode *P = dyn_cast(V))

840 }

841

842 for (auto *OtherPhi : IncomingPHIs) {

843

844 if (!DeletedPhis.contains(OtherPhi->getParent()))

845 continue;

846 mergeIfCompatible(PhiClasses, Phi, OtherPhi);

847 }

848 }

849 }

850

851 for (const auto &AddedPhi : AddedPhis) {

853 const BBVector &From = AddedPhi.second;

854

855 if (!DeletedPhis.count(To))

856 continue;

857

858 PhiMap &Map = DeletedPhis[To];

860 for (const auto &[Phi, Incoming] : Map) {

862 Updater.Initialize(Phi->getType(), "");

863 Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);

864 Updater.AddAvailableValue(To, Undef);

865

866

867 auto LeaderIt = PhiClasses.findLeader(Phi);

868 bool UseIncomingOfLeader =

869 LeaderIt != PhiClasses.member_end() && *LeaderIt != Phi;

870 const auto &IncomingMap =

871 UseIncomingOfLeader ? DeletedPhis[(*LeaderIt)->getParent()][*LeaderIt]

873

875 for (const auto &[BB, V] : IncomingMap) {

876 Updater.AddAvailableValue(BB, V);

877 if (isa(V))

879 }

880

881 for (auto UB : UndefBlks) {

882

883

884

885

886 if (any_of(ConstantPreds,

888 continue;

889

890 if (Updater.HasValueForBlock(UB))

891 continue;

892

893 Updater.AddAvailableValue(UB, Undef);

894 }

895

897 Phi->setIncomingValueForBlock(FI, Updater.GetValueAtEndOfBlock(FI));

898 AffectedPhis.push_back(Phi);

899 }

900 }

901

902 AffectedPhis.append(InsertedPhis.begin(), InsertedPhis.end());

903}

904

905void StructurizeCFG::simplifyAffectedPhis() {

906 bool Changed;

907 do {

908 Changed = false;

910 Q.DT = DT;

911

912

913 Q.CanUseUndef = false;

914 for (WeakVH VH : AffectedPhis) {

915 if (auto Phi = dyn_cast_or_null(VH)) {

917 Phi->replaceAllUsesWith(NewValue);

918 Phi->eraseFromParent();

919 Changed = true;

920 }

921 }

922 }

923 } while (Changed);

924}

925

926

927void StructurizeCFG::killTerminator(BasicBlock *BB) {

929 if (!Term)

930 return;

931

933 delPhiValues(BB, Succ);

934

935 Term->eraseFromParent();

936}

937

938

940 bool IncludeDominator) {

941 if (Node->isSubRegion()) {

945

946

947

949 if (!SubRegion->contains(BB))

950 continue;

951

952

953 delPhiValues(BB, OldExit);

955 addPhiValues(BB, NewExit);

956

957

958 if (IncludeDominator) {

959 if (!Dominator)

960 Dominator = BB;

961 else

963 }

964 }

965

966

967 if (Dominator)

969

970

972 } else {

974 killTerminator(BB);

977 addPhiValues(BB, NewExit);

978 if (IncludeDominator)

980 }

981}

982

983

986 BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() :

987 Order.back()->getEntry();

989 Func, Insert);

990 FlowSet.insert(Flow);

991

992

993

995 TermDL[Flow] = std::move(DL);

996

998 ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion);

1000}

1001

1002

1003BasicBlock *StructurizeCFG::needPrefix(bool NeedEmpty) {

1005

1006 if (!PrevNode->isSubRegion()) {

1007 killTerminator(Entry);

1008 if (!NeedEmpty || Entry->getFirstInsertionPt() == Entry->end())

1010 }

1011

1012

1014

1015

1016 changeExit(PrevNode, Flow, true);

1017 PrevNode = ParentRegion->getBBNode(Flow);

1018 return Flow;

1019}

1020

1021

1023 bool ExitUseAllowed) {

1024 if (!Order.empty() || !ExitUseAllowed)

1025 return getNextFlow(Flow);

1026

1029 addPhiValues(Flow, Exit);

1030 return Exit;

1031}

1032

1033

1034void StructurizeCFG::setPrevNode(BasicBlock *BB) {

1035 PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB)

1036 : nullptr;

1037}

1038

1039

1042 return llvm::all_of(Preds, [&](std::pair<BasicBlock *, PredInfo> Pred) {

1043 return DT->dominates(BB, Pred.first);

1044 });

1045}

1046

1047

1048bool StructurizeCFG::isPredictableTrue(RegionNode *Node) {

1050 bool Dominated = false;

1051

1052

1053 if (!PrevNode)

1054 return true;

1055

1056 for (auto [BB, PI] : Preds) {

1057 if (PI.Pred != BoolTrue)

1058 return false;

1059

1060 if (!Dominated && DT->dominates(BB, PrevNode->getEntry()))

1061 Dominated = true;

1062 }

1063

1064

1065 return Dominated;

1066}

1067

1068

1069void StructurizeCFG::wireFlow(bool ExitUseAllowed,

1072 Visited.insert(Node->getEntry());

1073

1074 if (isPredictableTrue(Node)) {

1075

1076 if (PrevNode) {

1077 changeExit(PrevNode, Node->getEntry(), true);

1078 }

1079 PrevNode = Node;

1080 } else {

1081

1083

1084

1086 BasicBlock *Next = needPostfix(Flow, ExitUseAllowed);

1087

1088

1091 Conditions.push_back(Br);

1092 addPhiValues(Flow, Entry);

1094

1095 PrevNode = Node;

1096 while (!Order.empty() && !Visited.count(LoopEnd) &&

1097 dominatesPredicates(Entry, Order.back())) {

1098 handleLoops(false, LoopEnd);

1099 }

1100

1101 changeExit(PrevNode, Next, false);

1102 setPrevNode(Next);

1103 }

1104}

1105

1106void StructurizeCFG::handleLoops(bool ExitUseAllowed,

1110

1111 if ( Loops .count(LoopStart)) {

1112 wireFlow(ExitUseAllowed, LoopEnd);

1113 return;

1114 }

1115

1116 if (!isPredictableTrue(Node))

1117 LoopStart = needPrefix(true);

1118

1119 LoopEnd = Loops[Node->getEntry()];

1120 wireFlow(false, LoopEnd);

1121 while (!Visited.count(LoopEnd)) {

1122 handleLoops(false, LoopEnd);

1123 }

1124

1126

1127

1128 LoopEnd = needPrefix(false);

1129 BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed);

1132 LoopConds.push_back(Br);

1133 addPhiValues(LoopEnd, LoopStart);

1134 setPrevNode(Next);

1135}

1136

1137

1138

1139void StructurizeCFG::createFlow() {

1141 bool EntryDominatesExit = DT->dominates(ParentRegion->getEntry(), Exit);

1142

1143 AffectedPhis.clear();

1144 DeletedPhis.clear();

1145 AddedPhis.clear();

1146 Conditions.clear();

1147 LoopConds.clear();

1148

1149 PrevNode = nullptr;

1150 Visited.clear();

1151

1152 while (!Order.empty()) {

1153 handleLoops(EntryDominatesExit, nullptr);

1154 }

1155

1156 if (PrevNode)

1157 changeExit(PrevNode, Exit, EntryDominatesExit);

1158 else

1159 assert(EntryDominatesExit);

1160}

1161

1162

1163

1164void StructurizeCFG::rebuildSSA() {

1166 for (BasicBlock *BB : ParentRegion->blocks())

1168 bool Initialized = false;

1169

1170

1173 if (User->getParent() == BB) {

1174 continue;

1175 } else if (PHINode *UserPN = dyn_cast(User)) {

1176 if (UserPN->getIncomingBlock(U) == BB)

1177 continue;

1178 }

1179

1181 continue;

1182

1183 if (!Initialized) {

1188 Initialized = true;

1189 }

1191 }

1192 }

1193}

1194

1197

1198 bool SubRegionsAreUniform = true;

1199

1200 unsigned ConditionalDirectChildren = 0;

1201

1202 for (auto *E : R->elements()) {

1203 if (!E->isSubRegion()) {

1204 auto Br = dyn_cast(E->getEntry()->getTerminator());

1206 continue;

1207

1209 return false;

1210

1211

1212 ConditionalDirectChildren++;

1213

1215 << " has uniform terminator\n");

1216 } else {

1217

1218

1219

1220

1221

1222

1223

1224

1225

1226 for (auto *BB : E->getNodeAs<Region>()->blocks()) {

1227 auto Br = dyn_cast(BB->getTerminator());

1229 continue;

1230

1231 if (!Br->getMetadata(UniformMDKindID)) {

1232

1233 if (!RelaxedUniformRegions)

1234 return false;

1235

1236 SubRegionsAreUniform = false;

1237 break;

1238 }

1239 }

1240 }

1241 }

1242

1243

1244

1245

1246

1247

1248

1249 return SubRegionsAreUniform || (ConditionalDirectChildren <= 1);

1250}

1251

1252void StructurizeCFG::init(Region *R) {

1253 LLVMContext &Context = R->getEntry()->getContext();

1254

1259

1260 this->UA = nullptr;

1261}

1262

1264 if (R->isTopLevelRegion())

1265 return false;

1266

1267 this->UA = &UA;

1268

1269

1270

1271

1272

1273 unsigned UniformMDKindID =

1274 R->getEntry()->getContext().getMDKindID("structurizecfg.uniform");

1275

1277 LLVM_DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R

1278 << '\n');

1279

1280

1281

1282

1283

1284 MDNode *MD = MDNode::get(R->getEntry()->getParent()->getContext(), {});

1286 if (E->isSubRegion())

1287 continue;

1288

1289 if (Instruction *Term = E->getEntry()->getTerminator())

1290 Term->setMetadata(UniformMDKindID, MD);

1291 }

1292

1293 return true;

1294 }

1295 return false;

1296}

1297

1298

1300 if (R->isTopLevelRegion())

1301 return false;

1302

1303 this->DT = DT;

1304

1305 Func = R->getEntry()->getParent();

1307

1308 ParentRegion = R;

1309

1310 orderNodes();

1311 collectInfos();

1312 createFlow();

1313 insertConditions(false);

1314 insertConditions(true);

1315 setPhiValues();

1316 simplifyConditions();

1317 simplifyAffectedPhis();

1318 rebuildSSA();

1319

1320

1321 Order.clear();

1322 Visited.clear();

1323 DeletedPhis.clear();

1324 AddedPhis.clear();

1325 Predicates.clear();

1326 Conditions.clear();

1328 LoopPreds.clear();

1329 LoopConds.clear();

1330 FlowSet.clear();

1331 TermDL.clear();

1332

1333 return true;

1334}

1335

1337 return new StructurizeCFGLegacyPass(SkipUniformRegions);

1338}

1339

1341 Regions.push_back(&R);

1342 for (const auto &E : R)

1344}

1345

1347 : SkipUniformRegions(SkipUniformRegions_) {

1348 if (ForceSkipUniformRegions.getNumOccurrences())

1349 SkipUniformRegions = ForceSkipUniformRegions.getValue();

1350}

1351

1355 OS, MapClassName2PassName);

1356 if (SkipUniformRegions)

1357 OS << "";

1358}

1359

1362

1363 bool Changed = false;

1366

1368 if (SkipUniformRegions)

1370

1371 std::vector<Region *> Regions;

1373 while (!Regions.empty()) {

1374 Region *R = Regions.back();

1375 Regions.pop_back();

1376

1377 StructurizeCFG SCFG;

1378 SCFG.init(R);

1379

1380 if (SkipUniformRegions && SCFG.makeUniformRegion(R, *UI)) {

1381 Changed = true;

1382 continue;

1383 }

1384

1385 Changed |= SCFG.run(R, DT);

1386 }

1387 if (!Changed)

1391 return PA;

1392}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

BlockVerifier::State From

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

This file contains the declarations for the subclasses of Constant, which represent the different fla...

Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx

This file defines the DenseMap class.

std::optional< std::vector< StOtherPiece > > Other

Generic implementation of equivalence classes through the use Tarjan's efficient union-find algorithm...

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

This header defines various interfaces for pass management in LLVM.

This defines the Use class.

This file implements a map that provides insertion order iteration.

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

This file contains the declarations for profiling metadata utility functions.

const SmallVectorImpl< MachineOperand > & Cond

static void addRegionIntoQueue(Region &R, std::deque< Region * > &RQ)

This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...

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

This file defines the SmallPtrSet class.

This file defines the SmallSet class.

This file defines the SmallVector class.

static void addRegionIntoQueue(Region &R, std::vector< Region * > &Regions)

const char FlowBlockName[]

static bool hasOnlyUniformBranches(Region *R, unsigned UniformMDKindID, const UniformityInfo &UA)

LLVM IR instance of the generic uniformity analysis.

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

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

Represent the analysis usage information of a pass.

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

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

LLVM Basic Block Representation.

iterator_range< const_phi_iterator > phis() const

Returns a range that iterates over the phis in the basic block.

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

Creates a new BasicBlock.

const Function * getParent() const

Return the enclosing method, or null if none.

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

Conditional or Unconditional Branch instruction.

bool isConditional() const

static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)

This is the shared class of boolean and integer constants.

static ConstantInt * getTrue(LLVMContext &Context)

static ConstantInt * getFalse(LLVMContext &Context)

size_type count(const_arg_type_t< KeyT > Val) const

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

Analysis pass which computes a DominatorTree.

void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)

changeImmediateDominator - This method is used to update the dominator tree information when a node's...

DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)

Add a new node to the dominator tree information.

Legacy analysis pass which computes a DominatorTree.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const

Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...

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

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

EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...

member_iterator findLeader(iterator I) const

findLeader - Given a value in the set, return a member iterator for the equivalence class it is in.

iterator insert(const ElemTy &Data)

insert - Insert a new value into the union/find set, ignoring the request if the value already exists...

member_iterator member_end() const

member_iterator unionSets(const ElemTy &V1, const ElemTy &V2)

union - Merge the two equivalence sets for the specified values, inserting them if they do not alread...

const BasicBlock & getEntryBlock() const

bool isUniform(ConstValueRefT V) const

Whether V is uniform/non-divergent.

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

MDNode * getMetadata(unsigned KindID) const

Get the metadata of given kind attached to this Instruction.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

This is an important class for using LLVM in a threaded context.

static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)

This class implements a map that also provides access to all stored values in a deterministic order.

static PassRegistry * getPassRegistry()

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

Pass interface - Implemented by all 'passes'.

virtual void getAnalysisUsage(AnalysisUsage &) const

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

virtual StringRef getPassName() const

getPassName - Return a nice clean name for a pass.

static PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

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.

void preserve()

Mark an analysis as preserved.

The pass manager to schedule RegionPasses.

void replaceExit(BlockT *BB)

Replace the exit basic block of the region with the new basic block.

block_range blocks()

Returns a range view of the basic blocks in the region.

BlockT * getExit() const

Get the exit BasicBlock of the Region.

bool contains(const BlockT *BB) const

Check if the region contains a BasicBlock.

Analysis pass that exposes the RegionInfo for a function.

RegionT * getRegionFor(BlockT *BB) const

Get the smallest region that contains a BasicBlock.

A pass that runs on each Region in a function.

virtual bool runOnRegion(Region *R, RGPassManager &RGM)=0

Run the pass on a specific Region.

Helper class for SSA formation on a set of values defined in multiple blocks.

void RewriteUseAfterInsertions(Use &U)

Rewrite a use like RewriteUse but handling in-block definitions.

void Initialize(Type *Ty, StringRef Name)

Reset this object to get ready for a new set of SSA updates with type 'Ty'.

Value * GetValueInMiddleOfBlock(BasicBlock *BB)

Construct SSA form, materializing a value that is live in the middle of the specified block.

void AddAvailableValue(BasicBlock *BB, Value *V)

Indicate that a rewritten value is available in the specified block with the specified value.

Implements a dense probed hash-table based set with some number of buckets stored inline.

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

SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...

bool contains(const T &V) const

Check if the SmallSet contains the given element.

std::pair< const_iterator, bool > insert(const T &V)

insert - Insert an element into the set if it isn't already there.

reference emplace_back(ArgTypes &&... Args)

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.

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

static IntegerType * getInt1Ty(LLVMContext &C)

static UndefValue * get(Type *T)

Static factory methods - Return an 'undef' object of the specified type.

Analysis pass which computes UniformityInfo.

Legacy analysis pass which computes a CycleInfo.

A Use represents the edge between a Value definition and its users.

bool replaceUsesOfWith(Value *From, Value *To)

Replace uses of one Value with another.

LLVM Value Representation.

void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

A nullable Value handle that is nullable.

int getNumOccurrences() const

std::pair< iterator, bool > insert(const ValueT &V)

Specialization of filter_iterator_base for forward iteration only.

An efficient, type-erasing, non-owning reference to a callable.

const ParentTy * getParent() const

CRTP base class for adapting an iterator to a different type.

A range adaptor for a pair of iterators.

This class implements an extremely fast bulk output stream that can only output to a stream.

Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.

bool isAtEnd() const

Direct loop termination test which is more efficient than comparison with end().

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

bool match(Val *V, const Pattern &P)

bind_ty< Instruction > m_Instruction(Instruction *&I)

Match an instruction, capturing it if we match.

OneUse_match< T > m_OneUse(const T &SubPattern)

BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)

Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.

@ Undef

Value of the register doesn't matter.

initializer< Ty > init(const Ty &Val)

NodeAddr< PhiNode * > Phi

NodeAddr< FuncNode * > Func

This is an optimization pass for GlobalISel generic memory operations.

bool all_of(R &&range, UnaryPredicate P)

Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.

APInt operator*(APInt a, uint64_t RHS)

bool hasOnlySimpleTerminator(const Function &F)

auto successors(const MachineBasicBlock *BB)

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

Pass * createStructurizeCFGPass(bool SkipUniformRegions=false)

When SkipUniformRegions is true the structizer will not structurize regions that only contain uniform...

Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)

See if we can compute a simplified version of this instruction.

void initializeStructurizeCFGLegacyPassPass(PassRegistry &)

bool any_of(R &&range, UnaryPredicate P)

Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.

auto reverse(ContainerTy &&C)

void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected)

Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...

raw_ostream & dbgs()

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

iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)

Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...

bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)

Extract branch weights from MD_prof metadata.

auto predecessors(const MachineBasicBlock *BB)

iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)

Value * invertCondition(Value *Condition)

Invert the given true/false value, possibly reusing an existing copy.

Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...

A CRTP mix-in to automatically provide informational APIs needed for passes.

void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

StructurizeCFGPass(bool SkipUniformRegions=false)