StructurizeCFG.cpp Source File (original) (raw)

51#include

52#include

54using namespace llvm;

57#define DEBUG_TYPE "structurizecfg"

62namespace {

65 "structurizecfg-skip-uniform-regions",

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

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

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

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

91using MaybeCondBranchWeights = std::optional;

93class CondBranchWeights {

99public:

100 static MaybeCondBranchWeights tryParse(const BranchInst &Br) {

102

105 return std::nullopt;

106

107 return CondBranchWeights(T, F);

108 }

109

110 static void setMetadata(BranchInst &Br,

111 const MaybeCondBranchWeights &Weights) {

113 if (!Weights)

114 return;

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

117 }

118

119 CondBranchWeights invert() const {

120 return CondBranchWeights{FalseWeight, TrueWeight};

121 }

122};

123

124struct PredInfo {

126 MaybeCondBranchWeights Weights;

127};

128

133

134

135

136

137struct SubGraphTraits {

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

140

141

142

143 class WrappedSuccIterator

145 WrappedSuccIterator, BaseSuccIterator,

146 std::iterator_traits::iterator_category, NodeRef,

147 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

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;

175 filter);

176 }

177

180 }

181

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;

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 Val2BBMap HoistedValues;

307

309

310 void hoistZeroCostElseBlockPhiValues(BasicBlock *ElseBB, BasicBlock *ThenBB);

311

314

315 void orderNodes();

316

318

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

320

322

323 void collectInfos();

324

326

327 void simplifyConditions();

328

330

332

333 void findUndefBlocks(BasicBlock *PHIBlock,

336

339

340 void setPhiValues();

341

342 void simplifyAffectedPhis();

343

344 void simplifyHoistedPhis();

345

347

349 bool IncludeDominator);

350

352

353 std::pair<BasicBlock *, DebugLoc> needPrefix(bool NeedEmpty);

354

356

358

360

362

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

364

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

366

367 void createFlow();

368

369 void rebuildSSA();

370

371public:

372 void init(Region *R);

375};

376

377class StructurizeCFGLegacyPass : public RegionPass {

378 bool SkipUniformRegions;

379

380public:

381 static char ID;

382

383 explicit StructurizeCFGLegacyPass(bool SkipUniformRegions_ = false)

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

386 SkipUniformRegions = ForceSkipUniformRegions.getValue();

388 }

389

391 StructurizeCFG SCFG;

392 SCFG.init(R);

393 if (SkipUniformRegions) {

395 getAnalysis().getUniformityInfo();

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

397 return false;

398 }

399 Function *F = R->getEntry()->getParent();

401 &getAnalysis().getTTI(*F);

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

403 return SCFG.run(R, DT, TTI);

404 }

405

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

407

408 void getAnalysisUsage(AnalysisUsage &AU) const override {

409 if (SkipUniformRegions)

414

417 }

418};

419

420}

421

422char StructurizeCFGLegacyPass::ID = 0;

423

425 "Structurize the CFG", false, false)

431

432

433

434

438 return false;

439

440

443 Cost.isValid()

444 ? Cost.getValue()

446 if (CostVal != 0)

447 return false;

448

449

450 for (auto &Op : I->operands()) {

451 if (auto *OpI = dyn_cast(Op)) {

452

453 if (!DT->dominates(OpI->getParent(), HoistTo))

454 return false;

455 }

456 }

457

458 return true;

459}

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474void StructurizeCFG::hoistZeroCostElseBlockPhiValues(BasicBlock *ElseBB,

476

479

480 if (!ElseSucc || !CommonDominator)

481 return;

483 for (PHINode &Phi : ElseSucc->phis()) {

484 Value *ElseVal = Phi.getIncomingValueForBlock(ElseBB);

486 if (!Inst || !isHoistableInstruction(Inst, ElseBB, CommonDominator))

487 continue;

488 Inst->removeFromParent();

489 Inst->insertInto(CommonDominator, Term->getIterator());

490 HoistedValues[Inst] = CommonDominator;

491 }

492}

493

494

495

496

497void StructurizeCFG::orderNodes() {

498 Order.resize(std::distance(GraphTraits<Region *>::nodes_begin(ParentRegion),

499 GraphTraits<Region *>::nodes_end(ParentRegion)));

500 if (Order.empty())

501 return;

502

503 SmallDenseSet<RegionNode *> Nodes;

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

505

506

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

509 while (true) {

510

511 for (auto SCCI =

513 EntryNode);

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

515 auto &SCC = *SCCI;

516

517

518

519

520 unsigned Size = SCC.size();

521 if (Size > 2)

523

524

525 for (const auto &N : SCC) {

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

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

528 }

529 }

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

531

532

533 if (WorkList.empty())

534 break;

535

537

538

539

540

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

543

544

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

546 EntryNode.second = &Nodes;

547 }

548}

549

550

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

552 if (N->isSubRegion()) {

553

555 if (Visited.count(Exit))

557

558 } else {

559

562 for (BasicBlock *Succ : Term->successors())

563 if (Visited.count(Succ))

564 Loops[Succ] = BB;

565 }

566}

567

568

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

570 bool Invert) {

571 Value *Cond = Invert ? BoolFalse : BoolTrue;

572 MaybeCondBranchWeights Weights;

573

574 if (Term->isConditional()) {

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

577

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

580 if (Weights)

581 Weights = Weights->invert();

582 }

583 }

584 return {Cond, Weights};

585}

586

587

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

593

595

597 continue;

598

600 if (R == ParentRegion) {

601

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

605 if (Succ != BB)

606 continue;

607

608 if (Visited.count(P)) {

609

610 if (Term->isConditional()) {

611

615 hoistZeroCostElseBlockPhiValues(Succ, Other);

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

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

618 continue;

619 }

620 }

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

622 } else {

623

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

625 }

626 }

627 } else {

628

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

630 R = R->getParent();

631

632

633 if (*R == *N)

634 continue;

635

637 if (Visited.count(Entry))

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

639 else

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

641 }

642 }

643}

644

645

646void StructurizeCFG::collectInfos() {

647

648 Predicates.clear();

649

650

652 LoopPreds.clear();

653

654

655 Visited.clear();

656

657 for (RegionNode *RN : reverse(Order)) {

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

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

661

662

663 gatherPredicates(RN);

664

665

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

667

668

669 analyzeLoops(RN);

670 }

671}

672

673

674void StructurizeCFG::insertConditions(bool Loops, SSAUpdaterBulk &PhiInserter) {

675 BranchVector &Conds = Loops ? LoopConds : Conditions;

677

678 for (BranchInst *Term : Conds) {

680

684

688

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

690

691 NearestCommonDominator Dominator(DT);

692 Dominator.addBlock(Parent);

693

694 PredInfo ParentInfo{nullptr, std::nullopt};

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

696 if (BB == Parent) {

697 ParentInfo = PI;

698 break;

699 }

701 Dominator.addAndRememberBlock(BB);

702 }

703

704 if (ParentInfo.Pred) {

705 Term->setCondition(ParentInfo.Pred);

706 CondBranchWeights::setMetadata(*Term, ParentInfo.Weights);

707 } else {

708 if (!Dominator.resultIsRememberedBlock())

710

711 PhiInserter.AddUse(Variable, &Term->getOperandUse(0));

712 }

713 }

714}

715

716

717void StructurizeCFG::simplifyConditions() {

720 auto &Preds = I.second;

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

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

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

727 PI.Pred->replaceAllUsesWith(InvertedCmp);

729 }

730 }

731 }

732 }

733 for (auto *I : InstToErase)

734 I->eraseFromParent();

735}

736

737

738

739void StructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) {

741 for (PHINode &Phi : To->phis()) {

742 bool Recorded = false;

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

745 Map[&Phi].push_back(std::make_pair(From, Deleted));

746 if (!Recorded) {

747 AffectedPhis.push_back(&Phi);

748 Recorded = true;

749 }

750 }

751 }

752}

753

754

755void StructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) {

756 for (PHINode &Phi : To->phis()) {

759 }

760 AddedPhis[To].push_back(From);

761}

762

763

764

765

766

767void StructurizeCFG::findUndefBlocks(

768 BasicBlock *PHIBlock, const SmallPtrSet<BasicBlock *, 8> &Incomings,

770

771

772

773

774

775

776

777

778

779

780

781

782

783

784

785

786

787

788

789

790

791

792

793

794 SmallPtrSet<BasicBlock *, 8> VisitedBlock;

795 SmallVector<BasicBlock *, 8> Stack;

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

800 }

801 } else {

803 }

804

805

806

807

808

809 while ( Stack .empty()) {

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

812 continue;

813

814 if (FlowSet.contains(Current))

816 else if (!Incomings.contains(Current))

818 }

819}

820

821

822

823

824

825

826

827void StructurizeCFG::mergeIfCompatible(

828 EquivalenceClasses<PHINode *> &PhiClasses, PHINode *A, PHINode *B) {

831

832 if (ItA == ItB)

833 return;

834

835 PHINode *LeaderA = *ItA;

836 PHINode *LeaderB = *ItB;

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

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

839

840 DenseMap<BasicBlock *, Value *> Mergeable(IncomingA.begin(), IncomingA.end());

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

842 auto BBIt = Mergeable.find(BB);

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

844 return;

845

846

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

848 }

849

850

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

853}

854

855

856void StructurizeCFG::setPhiValues() {

858 SSAUpdater Updater(&InsertedPhis);

859 DenseMap<BasicBlock *, SmallVector<BasicBlock *>> UndefBlksMap;

860

861

862

863

864

865

866

867

868

869

870

871

872

873

874

875

876

877

878

879

880

881

882 EquivalenceClasses<PHINode *> PhiClasses;

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

884 auto OldPhiIt = DeletedPhis.find(To);

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

886 continue;

887

888 PhiMap &BlkPhis = OldPhiIt->second;

890 SmallPtrSet<BasicBlock *, 8> Incomings;

891

892

893 if (!BlkPhis.empty()) {

895 findUndefBlocks(To, Incomings, UndefBlks);

896 }

897

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

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

901

902

905 }

906

907 for (auto *OtherPhi : IncomingPHIs) {

908

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

910 continue;

911 mergeIfCompatible(PhiClasses, Phi, OtherPhi);

912 }

913 }

914 }

915

916 for (const auto &AddedPhi : AddedPhis) {

918 const BBVector &From = AddedPhi.second;

919

920 auto It = DeletedPhis.find(To);

921 if (It == DeletedPhis.end())

922 continue;

923

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

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

930 Updater.AddAvailableValue(To, Poison);

931

932

933 auto LeaderIt = PhiClasses.findLeader(Phi);

934 bool UseIncomingOfLeader =

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

936 const auto &IncomingMap =

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

938 : Incoming;

939

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

942 Updater.AddAvailableValue(BB, V);

945 }

946

947 for (auto UB : UndefBlks) {

948

949

950

951

952 if (any_of(ConstantPreds,

953 [&](BasicBlock *CP) { return DT->dominates(CP, UB); }))

954 continue;

955

956 if (Updater.HasValueForBlock(UB))

957 continue;

958

959 Updater.AddAvailableValue(UB, Poison);

960 }

961

962 for (BasicBlock *FI : From)

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

964 AffectedPhis.push_back(Phi);

965 }

966 }

967

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

969}

970

971

972

973void StructurizeCFG::simplifyHoistedPhis() {

974 for (WeakVH VH : AffectedPhis) {

976 if (!Phi || Phi->getNumIncomingValues() != 2)

977 continue;

978

979 for (int i = 0; i < 2; i++) {

980 Value *V = Phi->getIncomingValue(i);

981 auto BBIt = HoistedValues.find(V);

982

983 if (BBIt == HoistedValues.end())

984 continue;

985

986 Value *OtherV = Phi->getIncomingValue(!i);

988 if (!OtherPhi)

989 continue;

990

991 int PoisonValBBIdx = -1;

994 continue;

995 PoisonValBBIdx = i;

996 break;

997 }

998 if (PoisonValBBIdx == -1 ||

1001 continue;

1002

1005 Phi->setIncomingValue(i, OtherV);

1006 }

1007 }

1008}

1009

1010void StructurizeCFG::simplifyAffectedPhis() {

1012 do {

1015 Q.DT = DT;

1016

1017

1018 Q.CanUseUndef = false;

1019 for (WeakVH VH : AffectedPhis) {

1022 Phi->replaceAllUsesWith(NewValue);

1023 Phi->eraseFromParent();

1025 }

1026 }

1027 }

1029}

1030

1031

1032DebugLoc StructurizeCFG::killTerminator(BasicBlock *BB) {

1034 if (!Term)

1036

1037 for (BasicBlock *Succ : successors(BB))

1038 delPhiValues(BB, Succ);

1039

1041 Term->eraseFromParent();

1042 return DL;

1043}

1044

1045

1046void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit,

1047 bool IncludeDominator) {

1048 if (Node->isSubRegion()) {

1052

1053

1054

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

1057 continue;

1058

1059

1060 delPhiValues(BB, OldExit);

1062 addPhiValues(BB, NewExit);

1063

1064

1065 if (IncludeDominator) {

1066 if (!Dominator)

1067 Dominator = BB;

1068 else

1070 }

1071 }

1072

1073

1074 if (Dominator)

1076

1077

1079 } else {

1084 addPhiValues(BB, NewExit);

1085 if (IncludeDominator)

1087 }

1088}

1089

1090

1091BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) {

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

1096 Func, Insert);

1097 FlowSet.insert(Flow);

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

1100 return Flow;

1101}

1102

1103

1104

1105std::pair<BasicBlock *, DebugLoc> StructurizeCFG::needPrefix(bool NeedEmpty) {

1107

1109 DebugLoc DL = killTerminator(Entry);

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

1112 }

1113

1114

1116

1117

1118 changeExit(PrevNode, Flow, true);

1121}

1122

1123

1124BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow,

1125 bool ExitUseAllowed) {

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

1127 return getNextFlow(Flow);

1128

1131 addPhiValues(Flow, Exit);

1132 return Exit;

1133}

1134

1135

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

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

1138 : nullptr;

1139}

1140

1141

1142bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) {

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

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

1146 });

1147}

1148

1149

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

1152 bool Dominated = false;

1153

1154

1155 if (!PrevNode)

1156 return true;

1157

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

1159 if (PI.Pred != BoolTrue)

1160 return false;

1161

1163 Dominated = true;

1164 }

1165

1166

1167 return Dominated;

1168}

1169

1170

1171void StructurizeCFG::wireFlow(bool ExitUseAllowed,

1172 BasicBlock *LoopEnd) {

1173 RegionNode *Node = Order.pop_back_val();

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

1175

1176 if (isPredictableTrue(Node)) {

1177

1178 if (PrevNode) {

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

1180 }

1181 PrevNode = Node;

1182 } else {

1183

1184 auto [Flow, DL] = needPrefix(false);

1185

1186

1189

1190

1193 Conditions.push_back(Br);

1194 addPhiValues(Flow, Entry);

1196

1197 PrevNode = Node;

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

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

1200 handleLoops(false, LoopEnd);

1201 }

1202

1203 changeExit(PrevNode, Next, false);

1204 setPrevNode(Next);

1205 }

1206}

1207

1208void StructurizeCFG::handleLoops(bool ExitUseAllowed,

1209 BasicBlock *LoopEnd) {

1210 RegionNode *Node = Order.back();

1212

1213 if ( Loops .count(LoopStart)) {

1214 wireFlow(ExitUseAllowed, LoopEnd);

1215 return;

1216 }

1217

1218 if (!isPredictableTrue(Node))

1219 LoopStart = needPrefix(true).first;

1220

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

1222 wireFlow(false, LoopEnd);

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

1224 handleLoops(false, LoopEnd);

1225 }

1226

1228

1229

1231 std::tie(LoopEnd, DL) = needPrefix(false);

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

1235 LoopConds.push_back(Br);

1236 addPhiValues(LoopEnd, LoopStart);

1237 setPrevNode(Next);

1238}

1239

1240

1241

1242void StructurizeCFG::createFlow() {

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

1245

1246 AffectedPhis.clear();

1247 DeletedPhis.clear();

1248 AddedPhis.clear();

1249 Conditions.clear();

1250 LoopConds.clear();

1251

1252 PrevNode = nullptr;

1253 Visited.clear();

1254

1255 while (!Order.empty()) {

1256 handleLoops(EntryDominatesExit, nullptr);

1257 }

1258

1259 if (PrevNode)

1260 changeExit(PrevNode, Exit, EntryDominatesExit);

1261 else

1262 assert(EntryDominatesExit);

1263}

1264

1265

1266

1267void StructurizeCFG::rebuildSSA() {

1268 SSAUpdater Updater;

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

1270 for (Instruction &I : *BB) {

1271 bool Initialized = false;

1272

1273

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

1277 continue;

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

1280 continue;

1281 }

1282

1284 continue;

1285

1286 if (!Initialized) {

1291 Initialized = true;

1292 }

1294 }

1295 }

1296}

1297

1300

1301 bool SubRegionsAreUniform = true;

1302

1303 unsigned ConditionalDirectChildren = 0;

1304

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

1306 if (->isSubRegion()) {

1309 continue;

1310

1312 return false;

1313

1314

1315 ConditionalDirectChildren++;

1316

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

1319 } else {

1320

1321

1322

1323

1324

1325

1326

1327

1328

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

1332 continue;

1333

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

1335

1336 if (!RelaxedUniformRegions)

1337 return false;

1338

1339 SubRegionsAreUniform = false;

1340 break;

1341 }

1342 }

1343 }

1344 }

1345

1346

1347

1348

1349

1350

1351

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

1353}

1354

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

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

1357

1362

1363 this->UA = nullptr;

1364}

1365

1366bool StructurizeCFG::makeUniformRegion(Region *R, UniformityInfo &UA) {

1367 if (R->isTopLevelRegion())

1368 return false;

1369

1370 this->UA = &UA;

1371

1372

1373

1374

1375

1376 unsigned UniformMDKindID =

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

1378

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

1381 << '\n');

1382

1383

1384

1385

1386

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

1388 for (RegionNode *E : R->elements()) {

1389 if (E->isSubRegion())

1390 continue;

1391

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

1393 Term->setMetadata(UniformMDKindID, MD);

1394 }

1395

1396 return true;

1397 }

1398 return false;

1399}

1400

1401

1402bool StructurizeCFG::run(Region *R, DominatorTree *DT,

1403 const TargetTransformInfo *TTI) {

1404

1405

1406

1407

1408

1409 if (R->isTopLevelRegion() || isa(R->getEntry()->getTerminator()))

1410 return false;

1411

1412 this->DT = DT;

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

1415

1416 ParentRegion = R;

1417

1418 orderNodes();

1419 collectInfos();

1420 createFlow();

1421

1422 SSAUpdaterBulk PhiInserter;

1423 insertConditions(false, PhiInserter);

1424 insertConditions(true, PhiInserter);

1426

1427 setPhiValues();

1428 simplifyHoistedPhis();

1429 simplifyConditions();

1430 simplifyAffectedPhis();

1431 rebuildSSA();

1432

1433

1434 Order.clear();

1435 Visited.clear();

1436 DeletedPhis.clear();

1437 AddedPhis.clear();

1438 Predicates.clear();

1439 Conditions.clear();

1441 LoopPreds.clear();

1442 LoopConds.clear();

1443 FlowSet.clear();

1444

1445 return true;

1446}

1447

1449 return new StructurizeCFGLegacyPass(SkipUniformRegions);

1450}

1451

1453 Regions.push_back(&R);

1454 for (const auto &E : R)

1456}

1457

1459 : SkipUniformRegions(SkipUniformRegions_) {

1460 if (ForceSkipUniformRegions.getNumOccurrences())

1461 SkipUniformRegions = ForceSkipUniformRegions.getValue();

1462}

1463

1467 OS, MapClassName2PassName);

1468 if (SkipUniformRegions)

1469 OS << "";

1470}

1471

1474

1480 if (SkipUniformRegions)

1482

1483 std::vector<Region *> Regions;

1485 while (!Regions.empty()) {

1486 Region *R = Regions.back();

1487 Regions.pop_back();

1488

1489 StructurizeCFG SCFG;

1490 SCFG.init(R);

1491

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

1493 Changed = true;

1494 continue;

1495 }

1496

1498 }

1503 return PA;

1504}

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

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

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

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

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

DenseMap< BasicBlock *, Instruction * > BBPredicates

This file defines the DenseMap class.

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

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

SmallDenseMap< const PHINode *, PhiInfo, 16 > PhiMap

const char FlowBlockName[]

Definition StructurizeCFG.cpp:60

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

Definition StructurizeCFG.cpp:1298

This pass exposes codegen information to IR-level passes.

LLVM IR instance of the generic uniformity analysis.

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.

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 * getSingleSuccessor() const

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

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

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 LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)

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

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

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

const ECValue & 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 findLeader(const ElemTy &V) const

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

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

const DataLayout & getDataLayout() const

Get the data layout of the module this function belongs to.

LLVMContext & getContext() const

getContext - Return a reference to the LLVMContext associated with this function.

bool isUniform(ConstValueRefT V) const

Whether V is uniform/non-divergent.

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.

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.

void setIncomingValue(unsigned i, Value *V)

BasicBlock * getIncomingBlock(unsigned i) const

Return incoming basic block number i.

Value * getIncomingValue(unsigned i) const

Return incoming value number x.

unsigned getNumIncomingValues() const

Return the number of incoming edges.

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

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

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

RegionNodeT * getBBNode(BlockT *BB) const

Get the BasicBlock RegionNode for a BasicBlock.

bool contains(const BlockT *BB) const

Check if the region contains a BasicBlock.

RegionInfoT * getRegionInfo() const

Return the RegionInfo object, that belongs to this Region.

BlockT * getEntry() const

Get the entry BasicBlock of the Region.

Analysis pass that exposes the RegionInfo for a function.

RegionT * getRegionFor(BlockT *BB) const

Get the smallest region that contains a BasicBlock.

bool isSubRegion() const

Is this RegionNode a subregion?

BlockT * getEntry() const

Get the entry BasicBlock of this RegionNode.

A pass that runs on each Region in a function.

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

LLVM_ABI unsigned AddVariable(StringRef Name, Type *Ty)

Add a new variable to the SSA rewriter.

LLVM_ABI void AddAvailableValue(unsigned Var, BasicBlock *BB, Value *V)

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

LLVM_ABI void AddUse(unsigned Var, Use *U)

Record a use of the symbolic value.

LLVM_ABI_FOR_TEST void RewriteAndOptimizeAllUses(DominatorTree &DT)

Rewrite all uses and simplify the inserted PHI nodes.

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

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.

void insert_range(Range &&R)

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.

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.

Analysis pass providing the TargetTransformInfo.

Wrapper pass for TargetTransformInfo.

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

@ TCK_Latency

The latency of instruction.

@ TCC_Expensive

The cost of a 'div' instruction on x86.

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

Analysis pass which computes UniformityInfo.

Legacy analysis pass which computes a CycleInfo.

LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)

Replace uses of one Value with another.

LLVM Value Representation.

int getNumOccurrences() const

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

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.

static scc_iterator begin(const GraphT &G)

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.

@ BasicBlock

Various leaf nodes.

BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)

Matches a register not-ed by a G_XOR.

OneUse_match< SubPat > m_OneUse(const SubPat &SP)

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

bind_ty< Instruction > m_Instruction(Instruction *&I)

Match an instruction, capturing it if we match.

initializer< Ty > init(const Ty &Val)

@ User

could "use" a pointer

NodeAddr< PhiNode * > Phi

NodeAddr< NodeBase * > Node

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

GenericUniformityInfo< SSAContext > UniformityInfo

FunctionAddr VTableAddr Value

bool all_of(R &&range, UnaryPredicate P)

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

decltype(auto) dyn_cast(const From &Val)

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

APInt operator*(APInt a, uint64_t RHS)

auto successors(const MachineBasicBlock *BB)

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

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

LLVM_ABI Pass * createStructurizeCFGPass(bool SkipUniformRegions=false)

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

Definition StructurizeCFG.cpp:1448

detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&...Ranges)

Returns a concatenated range across two or more ranges.

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

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

LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected, bool ElideAllZero=false)

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

auto dyn_cast_or_null(const Y &Val)

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)

LLVM_ABI raw_ostream & dbgs()

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

auto make_first_range(ContainerTy &&c)

Given a container of pairs, return a range over the first elements.

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

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

FunctionAddr VTableAddr Next

DWARFExpression::Operation Op

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

Extract branch weights from MD_prof metadata.

decltype(auto) cast(const From &Val)

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

auto predecessors(const MachineBasicBlock *BB)

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

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

LLVM_ABI Value * invertCondition(Value *Condition)

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

filter_iterator_impl< WrappedIteratorT, PredicateT, detail::fwd_or_bidi_tag< WrappedIteratorT > > filter_iterator

Defines filter_iterator to a suitable specialization of filter_iterator_impl, based on the underlying...

LLVM_ABI void initializeStructurizeCFGLegacyPassPass(PassRegistry &)

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

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

Definition StructurizeCFG.cpp:1464

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition StructurizeCFG.cpp:1472

StructurizeCFGPass(bool SkipUniformRegions=false)

Definition StructurizeCFG.cpp:1458