GenericDomTreeConstruction.h Source File (original) (raw)

37#ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H

38#define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H

46#include

47#include

49#define DEBUG_TYPE "dom-tree-builder"

51namespace llvm {

52namespace DomTreeBuilder {

54template

56 using NodePtr = typename DomTreeT::NodePtr;

57 using NodeT = typename DomTreeT::NodeType;

59 using RootsT = decltype(DomTreeT::Roots);

60 static constexpr bool IsPostDom = DomTreeT::IsPostDominator;

71 };

82 using UpdateT = typename DomTreeT::UpdateType;

83 using UpdateKind = typename DomTreeT::UpdateKind;

96 };

100

101

103

105 NumToNode = {nullptr};

107

108

109 }

110

111 template

113 if (BUI)

114 return BUI->PreViewCFG.template getChildren(N);

115 return getChildren(N);

116 }

117

118 template

120 using DirectedNodeT =

121 std::conditional_t<Inversed, Inverse, NodePtr>;

122 auto R = children(N);

124

125

127 return Res;

128 }

129

131 if constexpr (GraphHasNodeNumbers) {

134 unsigned Max = 0;

135 if (BB)

136 Max = GraphTraits<decltype(BB->getParent())>::getMaxNumber(

137 BB->getParent());

138

140 }

142 } else {

144 }

145 }

146

148

151

152

153

155

156 assert(IDom || DT.getNode(nullptr));

158

159

160

161 return DT.createNode(BB, IDomNode);

162 }

163

165

168

171

173 if (!BP.N)

174 O << "nullptr";

175 else

176 BP.N->printAsOperand(O, false);

177

178 return O;

179 }

180 };

181

183

184

185

186

187

188

189

190

191

192

193

194 template

195 unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,

196 unsigned AttachToNum,

201

202 while (!WorkList.empty()) {

203 const auto [BB, ParentNum] = WorkList.pop_back_val();

205 BBInfo.ReverseChildren.push_back(ParentNum);

206

207

208 if (BBInfo.DFSNum != 0) continue;

209 BBInfo.Parent = ParentNum;

210 BBInfo.DFSNum = BBInfo.Semi = BBInfo.Label = ++LastNum;

212

214 auto Successors = getChildren(BB, BatchUpdates);

215 if (SuccOrder && Successors.size() > 1)

217 Successors.begin(), Successors.end(), [=](NodePtr A, NodePtr B) {

218 return SuccOrder->find(A)->second < SuccOrder->find(B)->second;

219 });

220

221 for (const NodePtr Succ : Successors) {

222 if (!Condition(BB, Succ)) continue;

223

224 WorkList.push_back({Succ, LastNum});

225 }

226 }

227

228 return LastNum;

229 }

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244 unsigned eval(unsigned V, unsigned LastLinked,

247 InfoRec *VInfo = NumToInfo[V];

248 if (VInfo->Parent < LastLinked)

249 return VInfo->Label;

250

251

252 assert(Stack.empty());

253 do {

254 Stack.push_back(VInfo);

255 VInfo = NumToInfo[VInfo->Parent];

256 } while (VInfo->Parent >= LastLinked);

257

258

259

260 const InfoRec *PInfo = VInfo;

261 const InfoRec *PLabelInfo = NumToInfo[PInfo->Label];

262 do {

263 VInfo = Stack.pop_back_val();

265 const InfoRec *VLabelInfo = NumToInfo[VInfo->Label];

266 if (PLabelInfo->Semi < VLabelInfo->Semi)

268 else

269 PLabelInfo = VLabelInfo;

270 PInfo = VInfo;

271 } while (!Stack.empty());

272 return VInfo->Label;

273 }

274

275

279 NumToInfo.reserve(NextDFSNum);

280

281 for (unsigned i = 1; i < NextDFSNum; ++i) {

284 VInfo.IDom = NumToNode[VInfo.Parent];

286 }

287

288

290 for (unsigned i = NextDFSNum - 1; i >= 2; --i) {

291 auto &WInfo = *NumToInfo[i];

292

293

294 WInfo.Semi = WInfo.Parent;

295 for (unsigned N : WInfo.ReverseChildren) {

296 unsigned SemiU = NumToInfo[eval(N, i + 1, EvalStack, NumToInfo)]->Semi;

297 if (SemiU < WInfo.Semi) WInfo.Semi = SemiU;

298 }

299 }

300

301

302

303

304

305 for (unsigned i = 2; i < NextDFSNum; ++i) {

306 auto &WInfo = *NumToInfo[i];

307 assert(WInfo.Semi != 0);

308 const unsigned SDomNum = NumToInfo[WInfo.Semi]->DFSNum;

309 NodePtr WIDomCandidate = WInfo.IDom;

310 while (true) {

311 auto &WIDomCandidateInfo = getNodeInfo(WIDomCandidate);

312 if (WIDomCandidateInfo.DFSNum <= SDomNum)

313 break;

314 WIDomCandidate = WIDomCandidateInfo.IDom;

315 }

316

317 WInfo.IDom = WIDomCandidate;

318 }

319 }

320

321

322

323

324

325

327 assert(IsPostDom && "Only postdominators have a virtual root");

329

331 BBInfo.DFSNum = BBInfo.Semi = BBInfo.Label = 1;

332

334 }

335

336

337

338

340 assert(N && "N must be a valid node");

341 return !getChildren(N, BUI).empty();

342 }

343

345 assert(DT.Parent && "Parent not set");

347 }

348

349

350

351

353 assert(DT.Parent && "Parent pointer is not set");

355

356

359 return Roots;

360 }

361

363

364

366 unsigned Num = 1;

367

368 LLVM_DEBUG(dbgs() << "\t\tLooking for trivial roots\n");

369

370

371

372 unsigned Total = 0;

373

374

375

376

377

380

382 Roots.push_back(N);

383

386 << "\n");

389 }

390 }

391

392 LLVM_DEBUG(dbgs() << "\t\tLooking for non-trivial roots\n");

393

394

395

396

397 bool HasNonTrivialRoots = false;

398

399

400 if (Total + 1 != Num) {

401 HasNonTrivialRoots = true;

402

403

404

405

406

407

408 std::optional SuccOrder;

409 auto InitSuccOrderOnce = [&]() {

411 for (const auto Node : nodes(DT.Parent))

413 for (const auto Succ : getChildren(Node, SNCA.BatchUpdates))

414 SuccOrder->try_emplace(Succ, 0);

415

416

417 unsigned NodeNum = 0;

418 for (const auto Node : nodes(DT.Parent)) {

419 ++NodeNum;

420 auto Order = SuccOrder->find(Node);

421 if (Order != SuccOrder->end()) {

422 assert(Order->second == 0);

423 Order->second = NodeNum;

424 }

425 }

426 };

427

428

429

430

431

432

433

434

439

440

441

442

443

444

445

446

447

448

450

451 if (!SuccOrder)

452 InitSuccOrderOnce();

454

455 const unsigned NewNum =

458 LLVM_DEBUG(dbgs() << "\t\t\tFound a new furthest away node "

459 << "(non-trivial root): "

461 Roots.push_back(FurthestAway);

462 LLVM_DEBUG(dbgs() << "\t\t\tPrev DFSNum: " << Num << ", new DFSNum: "

463 << NewNum << "\n\t\t\tRemoving DFS info\n");

464 for (unsigned i = NewNum; i > Num; --i) {

466 LLVM_DEBUG(dbgs() << "\t\t\t\tRemoving DFS info for "

470 }

471 const unsigned PrevNum = Num;

474 for (unsigned i = PrevNum + 1; i <= Num; ++i)

477 }

478 }

479 }

480

485

486 assert((Total + 1 == Num) && "Everything should have been visited");

487

488

490

493 : Roots) dbgs()

496

497 return Roots;

498 }

499

500

501

502

503

504

505

506

507

510 assert(IsPostDom && "This function is for postdominators only");

512

514

515 for (unsigned i = 0; i < Roots.size(); ++i) {

516 auto &Root = Roots[i];

517

520 << " remains a root\n");

522

524

525

526 for (unsigned x = 2; x <= Num; ++x) {

528

529

530

532 LLVM_DEBUG(dbgs() << "\tForward DFS walk found another root "

536 Roots.pop_back();

537

538

539

540 --i;

541 break;

542 }

543 }

544 }

545 }

546

547 template

548 void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {

550 assert(DT.Roots.size() == 1 && "Dominators should have a singe root");

551 runDFS(DT.Roots[0], 0, DC, 0);

552 return;

553 }

554

556 unsigned Num = 1;

557 for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 1);

558 }

559

561 auto *Parent = DT.Parent;

562 DT.reset();

563 DT.Parent = Parent;

564

565

566

570 PostViewBUI = BUI;

571 }

572

573

575

576

577

578 DT.Roots = FindRoots(DT, PostViewBUI);

580

582 if (BUI) {

585 dbgs() << "DomTree recalculated, skipping future batch updates\n");

586 }

587

588 if (DT.Roots.empty()) return;

589

590

591

592

594

595 DT.RootNode = DT.createNode(Root);

597 }

598

600

602

604 if (DT.getNode(W))

605 continue;

606

608

609

611

612

613

614 DT.createNode(W, IDomNode);

615 }

616 }

617

625 }

626 }

627

628

632 return LHS->getLevel() < RHS->getLevel();

633 }

634 };

635

636

637

638 std::priority_queue<TreeNodePtr, SmallVector<TreeNodePtr, 8>,

639 Compare>

643#if LLVM_ENABLE_ABI_BREAKING_CHECKS

645#endif

646 };

647

651 "From has to be a valid CFG node or a virtual root");

652 assert(To && "Cannot be a nullptr");

656

657 if (!FromTN) {

658

660

661

662 TreeNodePtr VirtualRoot = DT.getNode(nullptr);

663 FromTN = DT.createNode(From, VirtualRoot);

664 DT.Roots.push_back(From);

665 }

666

667 DT.DFSInfoValid = false;

668

670 if (!ToTN)

672 else

674 }

675

676

677

681 assert(IsPostDom && "This function is only for postdominators");

682

683

684 if (!DT.isVirtualRoot(To->getIDom())) return false;

685

687 return false;

688

690 << " is no longer a root\n\t\tRebuilding the tree!!!\n");

691

693 return true;

694 }

695

698 if (A.size() != B.size())

699 return false;

702 if (Set.count(N) == 0)

703 return false;

704 return true;

705 }

706

707

708

709

711 assert(IsPostDom && "This function is only for postdominators");

712

713

715 return HasForwardSuccessors(N, BUI);

716 }))

717 return;

718

719

722

723

724

725

726

727 LLVM_DEBUG(dbgs() << "Roots are different in updated trees\n"

728 << "The entire tree needs to be rebuilt\n");

729

730

732 }

733 }

734

735

741

742

743

746 ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock())

747 : nullptr;

748 assert(NCDBlock || DT.isPostDominator());

749 const TreeNodePtr NCD = DT.getNode(NCDBlock);

751

753 const unsigned NCDLevel = NCD->getLevel();

754

755

756

757

758

759

760

761

762

763

764

765 if (NCDLevel + 1 >= To->getLevel())

766 return;

767

770 II.Bucket.push(To);

771 II.Visited.insert(To);

772

773 while (.Bucket.empty()) {

775 II.Bucket.pop();

776 II.Affected.push_back(TN);

777

778 const unsigned CurrentLevel = TN->getLevel();

780 "as affected, CurrentLevel " << CurrentLevel << "\n");

781

782 assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!");

783

784 while (true) {

785

786

787

788

789

790

791

792

793 for (const NodePtr Succ : getChildren(TN->getBlock(), BUI)) {

794 const TreeNodePtr SuccTN = DT.getNode(Succ);

796 "Unreachable successor found at reachable insertion");

797 const unsigned SuccLevel = SuccTN->getLevel();

798

800 << ", level = " << SuccLevel << "\n");

801

802

803

804

805

806

807

808

809 if (SuccLevel <= NCDLevel + 1 || .Visited.insert(SuccTN).second)

810 continue;

811

812 if (SuccLevel > CurrentLevel) {

813

814

815 LLVM_DEBUG(dbgs() << "\t\tMarking visited not affected "

817 UnaffectedOnCurrentLevel.push_back(SuccTN);

818#if LLVM_ENABLE_ABI_BREAKING_CHECKS

819 II.VisitedUnaffected.push_back(SuccTN);

820#endif

821 } else {

822

823

825 << " to a Bucket\n");

826 II.Bucket.push(SuccTN);

827 }

828 }

829

830 if (UnaffectedOnCurrentLevel.empty())

831 break;

832 TN = UnaffectedOnCurrentLevel.pop_back_val();

834 }

835 }

836

837

839 }

840

841

845

850 }

851

852#if LLVM_ENABLE_ABI_BREAKING_CHECKS && !defined(NDEBUG)

853 for (const TreeNodePtr TN : II.VisitedUnaffected)

855 "TN should have been updated by an affected ancestor");

856#endif

857

859 }

860

861

866

867

869

871

874 << "\n");

875

876

877

878 for (const auto &Edge : DiscoveredEdgesToReachable) {

879 LLVM_DEBUG(dbgs() << "\tInserting discovered connecting edge "

882 InsertReachable(DT, BUI, DT.getNode(Edge.first), Edge.second);

883 }

884 }

885

886

891 &DiscoveredConnectingEdges) {

892 assert(!DT.getNode(Root) && "Root must not be reachable");

893

894

895 auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From,

898 if (!ToTN) return true;

899

900 DiscoveredConnectingEdges.push_back({From, ToTN});

901 return false;

902 };

903

905 SNCA.runDFS(Root, 0, UnreachableDescender, 0);

908

909 LLVM_DEBUG(dbgs() << "After adding unreachable nodes\n");

910 }

911

914 assert(From && To && "Cannot disconnect nullptrs");

917

918#if LLVM_ENABLE_ABI_BREAKING_CHECKS

919

920

921

922 auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) {

923 auto Successors = getChildren(Of, BUI);

925 };

926 (void)IsSuccessor;

927 assert(!IsSuccessor(To, From) && "Deleted edge still exists in the CFG!");

928#endif

929

931

932 if (!FromTN) return;

933

935 if (!ToTN) {

938 << ") already unreachable -- there is no edge to delete\n");

939 return;

940 }

941

942 const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);

943 const TreeNodePtr NCD = DT.getNode(NCDBlock);

944

945

946 if (ToTN != NCD) {

947 DT.DFSInfoValid = false;

948

952

953

954

957 else

959 }

960

962 }

963

964

971

972

973

975 DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock());

976 assert(ToIDom || DT.isPostDominator());

977 const TreeNodePtr ToIDomTN = DT.getNode(ToIDom);

980

981

982 if (!PrevIDomSubTree) {

983 LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");

985 return;

986 }

987

988

989 const unsigned Level = ToIDomTN->getLevel();

990 auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {

991 return DT.getNode(To)->getLevel() > Level;

992 };

993

995 << "\n");

996

998 SNCA.runDFS(ToIDom, 0, DescendBelow, 0);

1002 }

1003

1004

1005

1009 << "\n");

1011 for (const NodePtr Pred : getChildren<!IsPostDom>(TNB, BUI)) {

1013 if (!DT.getNode(Pred)) continue;

1014

1015 const NodePtr Support = DT.findNearestCommonDominator(TNB, Pred);

1017 if (Support != TNB) {

1019 << " is reachable from support "

1021 return true;

1022 }

1023 }

1024

1025 return false;

1026 }

1027

1028

1029

1032 LLVM_DEBUG(dbgs() << "Deleting unreachable subtree "

1036

1038

1039

1040

1041 LLVM_DEBUG(dbgs() << "\tDeletion made a region reverse-unreachable\n");

1043 << "\n");

1044 DT.Roots.push_back(ToTN->getBlock());

1046 return;

1047 }

1048

1050 const unsigned Level = ToTN->getLevel();

1051

1052

1053

1054 auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {

1057 if (TN->getLevel() > Level) return true;

1060

1061 return false;

1062 };

1063

1065 unsigned LastDFSNum =

1066 SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0);

1067

1069

1070

1071

1072 for (const NodePtr N : AffectedQueue) {

1074 const NodePtr NCDBlock =

1075 DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock());

1076 assert(NCDBlock || DT.isPostDominator());

1077 const TreeNodePtr NCD = DT.getNode(NCDBlock);

1079

1083 if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD;

1084 }

1085

1086

1087 if (!MinNode->getIDom()) {

1088 LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");

1090 return;

1091 }

1092

1093

1094

1095 for (unsigned i = LastDFSNum; i > 0; --i) {

1098 << "\n");

1099 DT.eraseNode(N);

1100 }

1101

1102

1103 if (MinNode == ToTN) return;

1104

1105 LLVM_DEBUG(dbgs() << "DeleteUnreachable: running DFS with MinNode = "

1107 const unsigned MinLevel = MinNode->getLevel();

1111

1112

1113 auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) {

1114 const TreeNodePtr ToTN = DT.getNode(To);

1115 return ToTN && ToTN->getLevel() > MinLevel;

1116 };

1117 SNCA.runDFS(MinNode->getBlock(), 0, DescendBelow, 0);

1118

1121

1122

1125 }

1126

1127

1128

1129

1130

1133

1134

1136 if (NumUpdates == 0)

1137 return;

1138

1139

1140

1141 if (NumUpdates == 1) {

1143 if (!PostViewCFG) {

1144 if (Update.getKind() == UpdateKind::Insert)

1145 InsertEdge(DT, nullptr, Update.getFrom(), Update.getTo());

1146 else

1147 DeleteEdge(DT, nullptr, Update.getFrom(), Update.getTo());

1148 } else {

1150 if (Update.getKind() == UpdateKind::Insert)

1151 InsertEdge(DT, &BUI, Update.getFrom(), Update.getTo());

1152 else

1153 DeleteEdge(DT, &BUI, Update.getFrom(), Update.getTo());

1154 }

1155 return;

1156 }

1157

1159

1160

1161

1162

1163

1164

1165

1166

1167 if (DT.DomTreeNodes.size() <= 100) {

1168 if (BUI.NumLegalized > DT.DomTreeNodes.size())

1170 } else if (BUI.NumLegalized > DT.DomTreeNodes.size() / 40)

1172

1173

1174

1175

1178 }

1179

1181

1183#if 0

1184

1185

1186

1189#endif

1190

1191 if (CurrentUpdate.getKind() == UpdateKind::Insert)

1192 InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());

1193 else

1194 DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());

1195 }

1196

1197

1198

1199

1200

1201

1202

1203

1204

1205

1207 if (!DT.Parent && !DT.Roots.empty()) {

1208 errs() << "Tree has no parent but has roots!\n";

1210 return false;

1211 }

1212

1214 if (DT.Roots.empty()) {

1215 errs() << "Tree doesn't have a root!\n";

1217 return false;

1218 }

1219

1221 errs() << "Tree's root is not its parent's entry node!\n";

1223 return false;

1224 }

1225 }

1226

1229 errs() << "Tree has different roots than freshly computed ones!\n";

1230 errs() << "\tPDT roots: ";

1232 errs() << "\n\tComputed roots: ";

1233 for (const NodePtr N : ComputedRoots)

1235 errs() << "\n";

1237 return false;

1238 }

1239

1240 return true;

1241 }

1242

1243

1244

1248

1249 for (auto &NodeToTN : DT.DomTreeNodes) {

1251 if (!TN)

1252 continue;

1254

1255

1256 if (DT.isVirtualRoot(TN)) continue;

1257

1260 << " not found by DFS walk!\n";

1262

1263 return false;

1264 }

1265 }

1266

1268 if (N && !DT.getNode(N)) {

1270 << " not found in the DomTree!\n";

1272

1273 return false;

1274 }

1275 }

1276

1277 return true;

1278 }

1279

1280

1281

1282

1284 for (auto &NodeToTN : DT.DomTreeNodes) {

1286 if (!TN)

1287 continue;

1289 if (!BB) continue;

1290

1292 if (!IDom && TN->getLevel() != 0) {

1294 << " has a nonzero level " << TN->getLevel() << "!\n";

1296

1297 return false;

1298 }

1299

1302 << TN->getLevel() << " while its IDom "

1304 << IDom->getLevel() << "!\n";

1306

1307 return false;

1308 }

1309 }

1310

1311 return true;

1312 }

1313

1314

1315

1316

1318 if (!DT.DFSInfoValid || !DT.Parent)

1319 return true;

1320

1321 const NodePtr RootBB = IsPostDom ? nullptr : *DT.root_begin();

1322 const TreeNodePtr Root = DT.getNode(RootBB);

1323

1324 auto PrintNodeAndDFSNums = [](const TreeNodePtr TN) {

1326 << TN->getDFSNumOut() << '}';

1327 };

1328

1329

1330

1332 errs() << "DFSIn number for the tree root is not:\n\t";

1333 PrintNodeAndDFSNums(Root);

1334 errs() << '\n';

1336 return false;

1337 }

1338

1339

1340

1341 for (const auto &NodeToTN : DT.DomTreeNodes) {

1344 continue;

1345

1346

1347 if (Node->isLeaf()) {

1348 if (Node->getDFSNumIn() + 1 != Node->getDFSNumOut()) {

1349 errs() << "Tree leaf should have DFSOut = DFSIn + 1:\n\t";

1350 PrintNodeAndDFSNums(Node);

1351 errs() << '\n';

1353 return false;

1354 }

1355

1356 continue;

1357 }

1358

1359

1360

1364 });

1365

1366 auto PrintChildrenError = [Node, &Children, PrintNodeAndDFSNums](

1369

1370 errs() << "Incorrect DFS numbers for:\n\tParent ";

1371 PrintNodeAndDFSNums(Node);

1372

1373 errs() << "\n\tChild ";

1374 PrintNodeAndDFSNums(FirstCh);

1375

1376 if (SecondCh) {

1377 errs() << "\n\tSecond child ";

1378 PrintNodeAndDFSNums(SecondCh);

1379 }

1380

1381 errs() << "\nAll children: ";

1383 PrintNodeAndDFSNums(Ch);

1384 errs() << ", ";

1385 }

1386

1387 errs() << '\n';

1389 };

1390

1391 if (Children.front()->getDFSNumIn() != Node->getDFSNumIn() + 1) {

1392 PrintChildrenError(Children.front(), nullptr);

1393 return false;

1394 }

1395

1396 if (Children.back()->getDFSNumOut() + 1 != Node->getDFSNumOut()) {

1397 PrintChildrenError(Children.back(), nullptr);

1398 return false;

1399 }

1400

1401 for (size_t i = 0, e = Children.size() - 1; i != e; ++i) {

1402 if (Children[i]->getDFSNumOut() + 1 != Children[i + 1]->getDFSNumIn()) {

1403 PrintChildrenError(Children[i], Children[i + 1]);

1404 return false;

1405 }

1406 }

1407 }

1408

1409 return true;

1410 }

1411

1412

1413

1414

1415

1416

1417

1418

1419

1420

1421

1422

1423

1424

1425

1426

1427

1428

1429

1430

1431

1432

1433

1434

1435

1436

1437

1438

1439

1440

1441

1442

1443

1444

1445

1446

1447

1448

1449

1450

1451

1452

1453

1454

1456 for (auto &NodeToTN : DT.DomTreeNodes) {

1458 if (!TN)

1459 continue;

1461 if (!BB || TN->isLeaf())

1462 continue;

1463

1464 LLVM_DEBUG(dbgs() << "Verifying parent property of node "

1468 return From != BB && To != BB;

1469 });

1470

1475 << " is removed!\n";

1477

1478 return false;

1479 }

1480 }

1481

1482 return true;

1483 }

1484

1485

1486

1487

1488

1489

1490

1492 for (auto &NodeToTN : DT.DomTreeNodes) {

1494 if (!TN)

1495 continue;

1497 if (!BB || TN->isLeaf())

1498 continue;

1499

1502 NodePtr BBN = N->getBlock();

1504 return From != BBN && To != BBN;

1505 });

1506

1508 if (S == N) continue;

1509

1513 << " is removed!\n";

1515

1516 return false;

1517 }

1518 }

1519 }

1520 }

1521

1522 return true;

1523 }

1524

1525

1526

1527

1528

1529

1530

1531

1533 DomTreeT FreshTree;

1534 FreshTree.recalculate(*DT.Parent);

1535 const bool Different = DT.compare(FreshTree);

1536

1537 if (Different) {

1538 errs() << (DT.isPostDominator() ? "Post" : "")

1539 << "DominatorTree is different than a freshly computed one!\n"

1540 << "\tCurrent:\n";

1541 DT.print(errs());

1542 errs() << "\n\tFreshly computed tree:\n";

1543 FreshTree.print(errs());

1545 }

1546

1547 return !Different;

1548 }

1549};

1550

1551template

1554}

1555

1556template

1559

1560

1562 Updates, true);

1565}

1566

1567template

1569 typename DomTreeT::NodePtr To) {

1572}

1573

1574template

1576 typename DomTreeT::NodePtr To) {

1579}

1580

1581template

1583 GraphDiff<typename DomTreeT::NodePtr,

1584 DomTreeT::IsPostDominator> &PreViewCFG,

1585 GraphDiff<typename DomTreeT::NodePtr,

1586 DomTreeT::IsPostDominator> *PostViewCFG) {

1588}

1589

1590template

1591bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) {

1593

1594

1595

1597 return false;

1598

1599

1602 return false;

1603

1604

1605 if (VL == DomTreeT::VerificationLevel::Basic ||

1606 VL == DomTreeT::VerificationLevel::Full)

1608 return false;

1609 if (VL == DomTreeT::VerificationLevel::Full)

1611 return false;

1612

1613 return true;

1614}

1615

1616}

1617}

1618

1619#undef DEBUG_TYPE

1620

1621#endif

Unify divergent function exit nodes

BlockVerifier::State From

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

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

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 DenseSet and SmallDenseSet classes.

This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.

This file defines a set of templates that efficiently compute a dominator tree over a generic graph.

Loop::LoopBounds::Direction Direction

uint64_t IntrinsicInst * II

ppc ctr loops PowerPC CTR Loops Verify

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

This file defines the SmallPtrSet class.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

Base class for the actual dominator tree node.

iterator_range< iterator > children()

void setIDom(DomTreeNodeBase *NewIDom)

DomTreeNodeBase * getIDom() const

unsigned getDFSNumIn() const

getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.

unsigned getLevel() const

cfg::Update< NodePtr > popUpdateForIncrementalUpdates()

unsigned getNumLegalizedUpdates() const

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.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void reserve(size_type N)

void push_back(const T &Elt)

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

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

void CalculateWithUpdates(DomTreeT &DT, ArrayRef< typename DomTreeT::UpdateType > Updates)

void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)

void Calculate(DomTreeT &DT)

void ApplyUpdates(DomTreeT &DT, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > &PreViewCFG, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > *PostViewCFG)

void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)

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.

void erase(Container &C, ValueType V)

Wrapper function to remove a value from a container:

void sort(IteratorTy Start, IteratorTy End)

raw_ostream & dbgs()

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

bool none_of(R &&Range, UnaryPredicate P)

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

raw_fd_ostream & errs()

This returns a reference to a raw_ostream for standard error.

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

BatchUpdateInfo(GraphDiffT &PreViewCFG, GraphDiffT *PostViewCFG=nullptr)

const size_t NumLegalized

friend raw_ostream & operator<<(raw_ostream &O, const BlockNamePrinter &BP)

BlockNamePrinter(NodePtr Block)

BlockNamePrinter(TreeNodePtr TN)

SmallVector< unsigned, 4 > ReverseChildren

bool operator()(TreeNodePtr LHS, TreeNodePtr RHS) const

std::priority_queue< TreeNodePtr, SmallVector< TreeNodePtr, 8 >, Compare > Bucket

SmallVector< TreeNodePtr, 8 > Affected

SmallDenseSet< TreeNodePtr, 8 > Visited

SemiNCAInfo(BatchUpdatePtr BUI)

static SmallVector< NodePtr, 8 > getChildren(NodePtr N)

static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr NCD, InsertionInfo &II)

static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr From, const NodePtr To)

NodePtr getIDom(NodePtr BB)

InfoRec & getNodeInfo(NodePtr BB)

void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC)

DenseMap< NodePtr, unsigned > NodeOrderMap

static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI)

static SmallVector< NodePtr, 8 > getChildren(NodePtr N, BatchUpdatePtr BUI)

static void ComputeUnreachableDominators(DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root, const TreeNodePtr Incoming, SmallVectorImpl< std::pair< NodePtr, TreeNodePtr > > &DiscoveredConnectingEdges)

static bool VerifyLevels(const DomTreeT &DT)

decltype(DomTreeT::Roots) RootsT

bool verifyReachability(const DomTreeT &DT)

unsigned eval(unsigned V, unsigned LastLinked, SmallVectorImpl< InfoRec * > &Stack, ArrayRef< InfoRec * > NumToInfo)

static bool IsSameAsFreshTree(const DomTreeT &DT)

static constexpr bool IsPostDom

typename DomTreeT::NodePtr NodePtr

static void ApplyUpdates(DomTreeT &DT, GraphDiffT &PreViewCFG, GraphDiffT *PostViewCFG)

typename DomTreeT::UpdateKind UpdateKind

static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const TreeNodePtr To)

bool verifySiblingProperty(const DomTreeT &DT)

typename DomTreeT::NodeType NodeT

void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo)

static NodePtr GetEntryNode(const DomTreeT &DT)

static bool AlwaysDescend(NodePtr, NodePtr)

static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI)

SmallVector< NodePtr, 64 > NumToNode

unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition, unsigned AttachToNum, const NodeOrderMap *SuccOrder=nullptr)

static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr FromTN, const TreeNodePtr ToTN)

static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI, RootsT &Roots)

static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr TN)

static bool isPermutation(const SmallVectorImpl< NodePtr > &A, const SmallVectorImpl< NodePtr > &B)

static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI)

TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT)

typename DomTreeT::UpdateType UpdateT

static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const TreeNodePtr To)

static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI)

static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const NodePtr To)

static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI)

static bool VerifyDFSNumbers(const DomTreeT &DT)

static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr ToTN)

void attachNewSubtree(DomTreeT &DT, const TreeNodePtr AttachTo)

static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr From, const NodePtr To)

BatchUpdateInfo * BatchUpdates

bool verifyParentProperty(const DomTreeT &DT)

bool verifyRoots(const DomTreeT &DT)

std::conditional_t< GraphHasNodeNumbers< NodePtr >, SmallVector< InfoRec, 64 >, DenseMap< NodePtr, InfoRec > > NodeInfos

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