GenericDomTree.h Source File (original) (raw)

24#ifndef LLVM_SUPPORT_GENERICDOMTREE_H

25#define LLVM_SUPPORT_GENERICDOMTREE_H

35#include

36#include

37#include

38#include

39#include <type_traits>

40#include

42namespace llvm {

44template <typename NodeT, bool IsPostDom>

48template

50}

60 NodeT *TheBB;

62 unsigned Level;

64 mutable unsigned DFSNumIn = ~0;

65 mutable unsigned DFSNumOut = ~0;

67 public:

69 : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}

88 NodeT *getBlock() const { return TheBB; }

90 unsigned getLevel() const { return Level; }

94 bool isLeaf() const { return Children.empty(); }

101 return true;

102

103 if (Level != Other->Level) return true;

104

107 const NodeT *Nd = I->getBlock();

108 OtherChildren.insert(Nd);

109 }

110

112 const NodeT *N = I->getBlock();

113 if (OtherChildren.count(N) == 0)

114 return true;

115 }

116 return false;

117 }

118

120 assert(IDom && "No immediate dominator?");

121 if (IDom == NewIDom) return;

122

123 auto I = find(IDom->Children, this);

124 assert(I != IDom->Children.end() &&

125 "Not in immediate dominator children set!");

126

127 IDom->Children.erase(I);

128

129

130 IDom = NewIDom;

131 IDom->Children.push_back(this);

132

133 UpdateLevel();

134 }

135

136

137

138

141

142private:

143

144

146 return this->DFSNumIn >= other->DFSNumIn &&

147 this->DFSNumOut <= other->DFSNumOut;

148 }

149

150 void UpdateLevel() {

152 if (Level == IDom->Level + 1) return;

153

155

156 while (!WorkStack.empty()) {

158 Current->Level = Current->IDom->Level + 1;

159

162 if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);

163 }

164 }

165 }

166};

167

168template

170 if (Node->getBlock())

172 else

173 O << " <>";

174

175 O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["

176 << Node->getLevel() << "]\n";

177

178 return O;

179}

180

181template

183 unsigned Lev) {

184 O.indent(2 * Lev) << "[" << Lev << "] " << N;

185 for (const auto &I : *N)

187}

188

189namespace DomTreeBuilder {

190

191template

193

194template

197

198template

199void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,

200 typename DomTreeT::NodePtr To);

201

202template

203void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,

204 typename DomTreeT::NodePtr To);

205

206template

208 GraphDiff<typename DomTreeT::NodePtr,

209 DomTreeT::IsPostDominator> &PreViewCFG,

210 GraphDiff<typename DomTreeT::NodePtr,

211 DomTreeT::IsPostDominator> *PostViewCFG);

212

213template

214bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);

215}

216

217

218

222 using ParentPtr = decltype(std::declval()->getParent());

223 static_assert(std::is_pointer_v,

224 "Currently NodeT's parent must be a pointer type");

225 using ParentType = std::remove_pointer_t;

226

229};

230

231

232

233

234

235template <typename NodeT, bool IsPostDom>

237 public:

238 static_assert(std::is_pointer_v<typename GraphTraits<NodeT *>::NodeRef>,

239 "Currently DominatorTreeBase supports only pointer nodes");

244 static_assert(std::is_pointer_v,

245 "Currently NodeT's parent must be a pointer type");

246 using ParentType = std::remove_pointer_t;

248

253

255

256protected:

257

259

263

264

265 std::conditional_t<!GraphHasNodeNumbers<NodeT *>,

270

274

276

277 public:

279

287

289 if (this == &RHS)

290 return *this;

291 Roots = std::move(RHS.Roots);

299 RHS.wipe();

300 return *this;

301 }

302

305

306

307

308

309

310

313

318

320

327

328

329

331

332

333

336

337 if (Roots.size() != Other.Roots.size())

338 return true;

339

340 if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))

341 return true;

342

343 size_t NumNodes = 0;

344

347 continue;

348 if (Node->compare(Other.getNode(Node->getBlock())))

349 return true;

350 NumNodes++;

351 }

352

353

354 size_t NumOtherNodes = 0;

355 for (const auto &OtherNode : Other.DomTreeNodes)

356 if (OtherNode)

357 NumOtherNodes++;

358 return NumNodes != NumOtherNodes;

359 }

360

361private:

362 std::optional getNodeIndex(const NodeT *BB) const {

364

367 "dominator tree used with outdated block numbers");

369 } else {

371 return It->second;

372 return std::nullopt;

373 }

374 }

375

376 unsigned getNodeIndexForInsert(const NodeT *BB) {

378

379 unsigned Idx = *getNodeIndex(BB);

381 unsigned Max = GraphTraits::getMaxNumber(Parent);

382 DomTreeNodes.resize(Max > Idx + 1 ? Max : Idx + 1);

383 }

384 return Idx;

385 } else {

386

387 unsigned Idx =

391 return Idx;

392 }

393 }

394

395public:

396

397

398

399

402 "cannot get DomTreeNode of block with different parent");

403 if (auto Idx = getNodeIndex(BB); Idx && *Idx < DomTreeNodes.size())

405 return nullptr;

406 }

407

408

412

413

414

415

416

417

418

419

422

423

425 Result.clear();

427 if (!RN)

428 return;

431

432 while (!WL.empty()) {

434 Result.push_back(N->getBlock());

435 WL.append(N->begin(), N->end());

436 }

437 }

438

439

440

441

444 if ( || )

445 return false;

446 if (A == B)

447 return false;

449 }

450

452

453

454

457 "This is not implemented for post dominators");

459 }

460

462

463

464

465

468

469 if (B == A)

470 return true;

471

472

474 return true;

475

476

478 return false;

479

480 if (B->getIDom() == A) return true;

481

482 if (A->getIDom() == B) return false;

483

484

485 if (A->getLevel() >= B->getLevel()) return false;

486

487

488

489#ifdef EXPENSIVE_CHECKS

491 (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&

492 "Tree walk disagrees with dfs numbers!");

493#endif

494

496 return B->DominatedBy(A);

497

498

499

503 return B->DominatedBy(A);

504 }

505

506 return dominatedBySlowTreeWalk(A, B);

507 }

508

509 bool dominates(const NodeT *A, const NodeT *B) const;

510

512 assert(this->Roots.size() == 1 && "Should always have entry node!");

513 return this->Roots[0];

514 }

515

516

517

519 assert(A && B && "Pointers are not valid");

521 "Two blocks are not in same function");

522

523

524

526 NodeT &Entry =

528 if (A == &Entry || B == &Entry)

529 return &Entry;

530 }

531

534 assert(NodeA && "A must be in the tree");

535 assert(NodeB && "B must be in the tree");

536

537

538

539 while (NodeA != NodeB) {

541

542 NodeA = NodeA->IDom;

543 }

544

546 }

547

549 const NodeT *B) const {

550

551

553 const_cast<NodeT *>(B));

554 }

555

559

560 template

562 assert(!Nodes.empty() && "Nodes list is empty!");

563

564 NodeT *NCD = *Nodes.begin();

567

568

570 return nullptr;

571 }

572

573 return NCD;

574 }

575

576

577

578

579

580

581

582

583

584

585

586

587

588

589

590

591

592

593

594

595

596

597

598

599

600

601

602

603

604

605

606

607

608

609

610

613 Updates, true);

615 }

616

617

618

619

620

621

624 if (Updates.empty()) {

627 } else {

628

629

630

631

632

636 true);

639 }

640 }

641

642

643

644

645

646

647

648

649

650

658

659

660

661

662

663

664

665

666

667

668

676

677

678

679

680

681

682

683

684

685

687 assert(getNode(BB) == nullptr && "Block already in dominator tree!");

689 assert(IDomNode && "Not immediate dominator specified for block!");

692 }

693

694

695

696

697

698

700 assert(getNode(BB) == nullptr && "Block already in dominator tree!");

702 "Cannot change root of post-dominator tree");

703 DFSInfoValid = false;

705 if (Roots.empty()) {

707 } else {

709 NodeT *OldRoot = Roots.front();

712 OldNode->IDom = NewNode;

713 OldNode->UpdateLevel();

715 }

717 }

718

719

720

721

724 assert(N && NewIDom && "Cannot change null node pointers!");

726 N->setIDom(NewIDom);

727 }

728

732

733

734

735

737 std::optional IdxOpt = getNodeIndex(BB);

739 "Removing node that isn't in dominator tree.");

741 assert(Node->isLeaf() && "Node is not a leaf node.");

742

744

745

747 if (IDom) {

748 const auto I = find(IDom->Children, Node);

749 assert(I != IDom->Children.end() &&

750 "Not in immediate dominator children set!");

751

752 std::swap(*I, IDom->Children.back());

753 IDom->Children.pop_back();

754 }

755

759

760 if (!IsPostDom) return;

761

762

764 if (RIt != Roots.end()) {

766 Roots.pop_back();

767 }

768 }

769

770

771

778

779

780

782 O << "=============================--------------------------------\n";

784 O << "Inorder PostDominator Tree: ";

785 else

786 O << "Inorder Dominator Tree: ";

788 O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";

789 O << "\n";

790

791

793 O << "Roots: ";

795 Block->printAsOperand(O, false);

796 O << " ";

797 }

798 O << "\n";

799 }

800

801public:

802

803

807 return;

808 }

809

812 32> WorkStack;

813

815 assert(( Parent || ThisRoot) && "Empty constructed DomTree");

816 if (!ThisRoot)

817 return;

818

819

820

822

823 unsigned DFSNum = 0;

824 ThisRoot->DFSNumIn = DFSNum++;

825

826 while (!WorkStack.empty()) {

828 const auto ChildIt = WorkStack.back().second;

829

830

831

832 if (ChildIt == Node->end()) {

833 Node->DFSNumOut = DFSNum++;

835 } else {

836

838 ++WorkStack.back().second;

839

841 Child->DFSNumIn = DFSNum++;

842 }

843 }

844

847 }

848

849private:

850 void updateBlockNumberEpoch() {

851

854 }

855

856public:

857

860 updateBlockNumberEpoch();

862 }

863

866 updateBlockNumberEpoch();

868 }

869

870

871 template

873 updateBlockNumberEpoch();

874

877 NewVector.resize(MaxNumber + 1);

880 continue;

881 unsigned Idx = *getNodeIndex(Node->getBlock());

882

883 if (Idx >= NewVector.size())

884 NewVector.resize(Idx + 1);

885 NewVector[Idx] = std::move(Node);

886 }

888 }

889

890

891

892

893

894

895

896

897

898

899

900

901

902

903

907

918

919protected:

921

924 auto Node = std::make_unique<DomTreeNodeBase>(BB, IDom);

926 unsigned NodeIdx = getNodeIndexForInsert(BB);

928 if (IDom)

931 }

932

933

934

935 template

938 using NodeRef = typename GraphT::NodeRef;

940 "NewBB should have a single successor!");

941 NodeRef NewBBSucc = *GraphT::child_begin(NewBB);

942

944

945 assert(!PredBlocks.empty() && "No predblocks?");

946

947 bool NewBBDominatesNewBBSucc = true;

949 if (Pred != NewBB && dominates (NewBBSucc, Pred) &&

951 NewBBDominatesNewBBSucc = false;

952 break;

953 }

954 }

955

956

957

958 NodeT *NewBBIDom = nullptr;

959 unsigned i = 0;

960 for (i = 0; i < PredBlocks.size(); ++i)

962 NewBBIDom = PredBlocks[i];

963 break;

964 }

965

966

967

968

969 if (!NewBBIDom) return;

970

971 for (i = i + 1; i < PredBlocks.size(); ++i) {

974 }

975

976

978

979

980

981 if (NewBBDominatesNewBBSucc) {

984 }

985 }

986

987 private:

993

994 const unsigned ALevel = A->getLevel();

996

997

998

999 while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel)

1000 B = IDom;

1001

1002 return B == A;

1003 }

1004

1005

1006

1007

1008

1009 void wipe() {

1015 }

1016};

1017

1018template

1020

1021template

1023

1024

1025

1026template <typename NodeT, bool IsPostDom>

1028 const NodeT *B) const {

1029 if (A == B)

1030 return true;

1031

1033}

1034template <typename NodeT, bool IsPostDom>

1036 const NodeT *A, const NodeT *B) const {

1037 if (A == B)

1038 return false;

1039

1041}

1042

1043}

1044

1045#endif

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

static msgpack::DocNode getNode(msgpack::DocNode DN, msgpack::Type Type, MCValue Val)

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

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

This file defines the DenseMap class.

This file defines the little GraphTraits template class that should be specialized by classes that...

ppc ctr loops PowerPC CTR Loops Verify

static bool dominates(InstrPosIndexes &PosIndexes, const MachineInstr &A, const MachineInstr &B)

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

void printAsOperand(OutputBuffer &OB, Prec P=Prec::Default, bool StrictlyWorse=false) const

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

bool empty() const

empty - Check if the array is empty.

Base class for the actual dominator tree node.

Definition GenericDomTree.h:53

iterator_range< iterator > children()

Definition GenericDomTree.h:83

const_iterator end() const

Definition GenericDomTree.h:78

bool isLeaf() const

Definition GenericDomTree.h:94

DomTreeNodeBase *& back()

Definition GenericDomTree.h:81

void setIDom(DomTreeNodeBase *NewIDom)

Definition GenericDomTree.h:119

typename SmallVector< DomTreeNodeBase *, 4 >::iterator iterator

Definition GenericDomTree.h:71

void clearAllChildren()

Definition GenericDomTree.h:97

DomTreeNodeBase *const & back() const

Definition GenericDomTree.h:80

iterator begin()

Definition GenericDomTree.h:75

DomTreeNodeBase * getIDom() const

Definition GenericDomTree.h:89

unsigned getDFSNumIn() const

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

Definition GenericDomTree.h:139

iterator end()

Definition GenericDomTree.h:76

size_t getNumChildren() const

Definition GenericDomTree.h:95

DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)

Definition GenericDomTree.h:68

bool compare(const DomTreeNodeBase *Other) const

Definition GenericDomTree.h:99

NodeT * getBlock() const

Definition GenericDomTree.h:88

friend class PostDominatorTree

Definition GenericDomTree.h:54

unsigned getLevel() const

Definition GenericDomTree.h:90

iterator_range< const_iterator > children() const

Definition GenericDomTree.h:84

typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator

Definition GenericDomTree.h:72

unsigned getDFSNumOut() const

Definition GenericDomTree.h:140

const_iterator begin() const

Definition GenericDomTree.h:77

void addChild(DomTreeNodeBase *C)

Definition GenericDomTree.h:92

Core dominator tree base class.

Definition GenericDomTree.h:236

DomTreeNodeTraits< BlockT > NodeTrait

Definition GenericDomTree.h:240

bool isReachableFromEntry(const DomTreeNodeBase< NodeT > *A) const

Definition GenericDomTree.h:461

void print(raw_ostream &O) const

print - Convert to human readable form

Definition GenericDomTree.h:781

typename NodeTrait::NodeType NodeType

Definition GenericDomTree.h:241

DomTreeNodeBase< NodeT > * operator[](const NodeT *BB) const

See getNode.

Definition GenericDomTree.h:409

typename SmallVectorImpl< BlockT * >::iterator root_iterator

Definition GenericDomTree.h:311

DomTreeNodeBase< NodeT > * getRootNode()

getRootNode - This returns the entry node for the CFG of the function.

Definition GenericDomTree.h:420

bool verify(VerificationLevel VL=VerificationLevel::Full) const

verify - checks if the tree is correct.

Definition GenericDomTree.h:904

void changeImmediateDominator(NodeT *BB, NodeT *NewBB)

Definition GenericDomTree.h:729

NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const

Find nearest common dominator basic block for basic block A and B.

Definition GenericDomTree.h:518

DominatorTreeBase()=default

void Split(typename GraphTraits< N >::NodeRef NewBB)

Definition GenericDomTree.h:936

iterator_range< root_iterator > roots()

Definition GenericDomTree.h:321

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

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

Definition GenericDomTree.h:722

std::remove_pointer_t< ParentPtr > ParentType

Definition GenericDomTree.h:246

void reset()

Definition GenericDomTree.h:908

DominatorTreeBase(DominatorTreeBase &&Arg)

Definition GenericDomTree.h:280

NodeT * findNearestCommonDominator(iterator_range< IteratorTy > Nodes) const

Definition GenericDomTree.h:561

bool isPostDominator() const

isPostDominator - Returns true if analysis based of postdoms

Definition GenericDomTree.h:330

size_t root_size() const

Definition GenericDomTree.h:319

bool dominates(const NodeT *A, const NodeT *B) const

Definition GenericDomTree.h:1027

const NodeT * findNearestCommonDominator(const NodeT *A, const NodeT *B) const

Definition GenericDomTree.h:548

void getDescendants(NodeT *R, SmallVectorImpl< NodeT * > &Result) const

Get all nodes dominated by R, including R itself.

Definition GenericDomTree.h:424

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

Add a new node to the dominator tree information.

Definition GenericDomTree.h:686

DomTreeNodeBase< NodeT > * createNode(NodeT *BB, DomTreeNodeBase< NodeT > *IDom=nullptr)

Definition GenericDomTree.h:922

void applyUpdates(ArrayRef< UpdateType > Updates)

Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...

Definition GenericDomTree.h:611

unsigned int SlowQueries

Definition GenericDomTree.h:272

bool DFSInfoValid

Definition GenericDomTree.h:271

void insertEdge(NodeT *From, NodeT *To)

Inform the dominator tree about a CFG edge insertion and update the tree.

Definition GenericDomTree.h:651

std::enable_if_t< GraphHasNodeNumbers< T * >, void > updateBlockNumbers()

Update dominator tree after renumbering blocks.

Definition GenericDomTree.h:872

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

dominates - Returns true iff A dominates B.

Definition GenericDomTree.h:466

iterator_range< const_root_iterator > roots() const

Definition GenericDomTree.h:324

const_root_iterator root_end() const

Definition GenericDomTree.h:317

void splitBlock(NodeT *NewBB)

splitBlock - BB is split and now it has one successor.

Definition GenericDomTree.h:772

DominatorTreeBase & operator=(DominatorTreeBase &&RHS)

Definition GenericDomTree.h:288

static constexpr UpdateKind Delete

Definition GenericDomTree.h:252

void recalculate(ParentType &Func, ArrayRef< UpdateType > Updates)

Definition GenericDomTree.h:864

NodeT * getRoot() const

Definition GenericDomTree.h:511

void updateDFSNumbers() const

updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.

Definition GenericDomTree.h:804

typename SmallVectorImpl< BlockT * >::const_iterator const_root_iterator

Definition GenericDomTree.h:312

bool compare(const DominatorTreeBase &Other) const

compare - Return false if the other dominator tree base matches this dominator tree base.

Definition GenericDomTree.h:334

DomTreeNodeBase< NodeT > * setNewRoot(NodeT *BB)

Add a new node to the forward dominator tree and make it a new root.

Definition GenericDomTree.h:699

root_iterator root_begin()

Definition GenericDomTree.h:314

DominatorTreeBase(const DominatorTreeBase &)=delete

static constexpr UpdateKind Insert

Definition GenericDomTree.h:251

const_root_iterator root_begin() const

Definition GenericDomTree.h:315

void recalculate(ParentType &Func)

recalculate - compute a dominator tree for the given function

Definition GenericDomTree.h:858

SmallVector< BlockT *, IsPostDom ? 4 :1 > Roots

Definition GenericDomTree.h:258

void eraseNode(NodeT *BB)

eraseNode - Removes a node from the dominator tree.

Definition GenericDomTree.h:736

VerificationLevel

Definition GenericDomTree.h:254

@ Basic

Definition GenericDomTree.h:254

@ Full

Definition GenericDomTree.h:254

@ Fast

Definition GenericDomTree.h:254

void deleteEdge(NodeT *From, NodeT *To)

Inform the dominator tree about a CFG edge deletion and update the tree.

Definition GenericDomTree.h:669

const DomTreeNodeBase< NodeT > * getRootNode() const

Definition GenericDomTree.h:421

std::conditional_t<!GraphHasNodeNumbers< BlockT * >, DenseMap< const BlockT *, unsigned >, std::tuple<> > NodeNumberMap

Definition GenericDomTree.h:267

DomTreeNodeBase< BlockT > * RootNode

Definition GenericDomTree.h:268

void addRoot(NodeT *BB)

Definition GenericDomTree.h:920

typename NodeTrait::NodePtr NodePtr

Definition GenericDomTree.h:242

bool isReachableFromEntry(const NodeT *A) const

isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it...

Definition GenericDomTree.h:455

cfg::Update< NodePtr > UpdateType

Definition GenericDomTree.h:249

root_iterator root_end()

Definition GenericDomTree.h:316

cfg::UpdateKind UpdateKind

Definition GenericDomTree.h:250

void applyUpdates(ArrayRef< UpdateType > Updates, ArrayRef< UpdateType > PostViewUpdates)

Definition GenericDomTree.h:622

unsigned BlockNumberEpoch

Definition GenericDomTree.h:273

DomTreeNodeStorageTy DomTreeNodes

Definition GenericDomTree.h:262

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

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

Definition GenericDomTree.h:400

bool properlyDominates(const NodeT *A, const NodeT *B) const

Definition GenericDomTree.h:1035

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

properlyDominates - Returns true iff A dominates B and A != B.

Definition GenericDomTree.h:442

bool isVirtualRoot(const DomTreeNodeBase< NodeT > *A) const

Definition GenericDomTree.h:556

typename NodeTrait::ParentPtr ParentPtr

Definition GenericDomTree.h:243

DominatorTreeBase & operator=(const DominatorTreeBase &)=delete

static constexpr bool IsPostDominator

Definition GenericDomTree.h:247

SmallVector< std::unique_ptr< DomTreeNodeBase< BlockT > > > DomTreeNodeStorageTy

Definition GenericDomTree.h:260

ParentPtr Parent

Definition GenericDomTree.h:269

size_type count(ConstPtrType Ptr) const

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

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

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

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

typename SuperClass::const_iterator const_iterator

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

typename SuperClass::iterator iterator

void push_back(const T &Elt)

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

A range adaptor for a pair of iterators.

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

@ C

The default llvm calling convention, compatible with C.

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

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.

auto find(R &&Range, const T &Val)

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

void PrintDomTree(const DomTreeNodeBase< NodeT > *N, raw_ostream &O, unsigned Lev)

Definition GenericDomTree.h:182

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

Convenience function for iterating over sub-ranges.

constexpr bool GraphHasNodeNumbers

Indicate whether a GraphTraits::getNumber() is supported.

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

Wrapper function to append range R to container C.

DominatorTreeBase< T, true > PostDomTreeBase

Definition GenericDomTree.h:1022

DominatorTreeBase< T, false > DomTreeBase

Definition GenericDomTree.h:1019

bool hasSingleElement(ContainerTy &&C)

Returns true if the given container only contains a single element.

class LLVM_GSL_OWNER SmallVector

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

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

raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)

ArrayRef(const T &OneElt) -> ArrayRef< T >

OutputIt move(R &&Range, OutputIt Out)

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

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

Implement std::hash so that hash_code can be used in STL containers.

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

Implement std::swap in terms of BitVector swap.

Default DomTreeNode traits for NodeT.

Definition GenericDomTree.h:219

NodeT NodeType

Definition GenericDomTree.h:220