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

40#include <type_traits>

41#include

43namespace llvm {

45template <typename NodeT, bool IsPostDom>

46class DominatorTreeBase;

48namespace DomTreeBuilder {

49template

50struct SemiNCAInfo;

51}

61 NodeT *TheBB;

63 unsigned Level;

65 mutable unsigned DFSNumIn = ~0;

66 mutable unsigned DFSNumOut = ~0;

68 public:

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

87 }

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

91 unsigned getLevel() const { return Level; }

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

102 return true;

103

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

105

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

109 OtherChildren.insert(Nd);

110 }

111

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

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

115 return true;

116 }

117 return false;

118 }

119

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

122 if (IDom == NewIDom) return;

123

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

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

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

127

128 IDom->Children.erase(I);

129

130

131 IDom = NewIDom;

132 IDom->Children.push_back(this);

133

134 UpdateLevel();

135 }

136

137

138

139

142

143private:

144

145

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

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

149 }

150

151 void UpdateLevel() {

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

154

155 SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};

156

157 while (!WorkStack.empty()) {

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

160

161 for (DomTreeNodeBase *C : *Current) {

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

164 }

165 }

166 }

167};

168

169template

171 if (Node->getBlock())

173 else

174 O << " <>";

175

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

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

178

179 return O;

180}

181

182template

184 unsigned Lev) {

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

186 for (const auto &I : *N)

187 PrintDomTree(I, O, Lev + 1);

188}

189

190namespace DomTreeBuilder {

191

192template

194

195template

197 ArrayRef Updates);

198

199template

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

201 typename DomTreeT::NodePtr To);

202

203template

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

205 typename DomTreeT::NodePtr To);

206

207template

209 GraphDiff<typename DomTreeT::NodePtr,

210 DomTreeT::IsPostDominator> &PreViewCFG,

211 GraphDiff<typename DomTreeT::NodePtr,

212 DomTreeT::IsPostDominator> *PostViewCFG);

213

214template

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

216}

217

218

219

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

224 static_assert(std::is_pointer_v,

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

226 using ParentType = std::remove_pointer_t;

227

230};

231

232

233

234

235

236template <typename NodeT, bool IsPostDom>

238 public:

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

240 "Currently DominatorTreeBase supports only pointer nodes");

245 static_assert(std::is_pointer_v,

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

247 using ParentType = std::remove_pointer_t;

249

254

256

257protected:

258

260

264

265

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

271

275

277

278 public:

280

286 Arg.wipe();

287 }

288

290 if (this == &RHS)

291 return *this;

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

300 RHS.wipe();

301 return *this;

302 }

303

306

307

308

309

310

311

314

319

321

324 }

327 }

328

329

330

332

333

334

337

339 return true;

340

342 return true;

343

344 size_t NumNodes = 0;

345

348 continue;

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

350 return true;

351 NumNodes++;

352 }

353

354

355 size_t NumOtherNodes = 0;

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

357 if (OtherNode)

358 NumOtherNodes++;

359 return NumNodes != NumOtherNodes;

360 }

361

362private:

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

364 if constexpr (GraphHasNodeNumbers<NodeT *>) {

365

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

370 } else {

372 return It->second;

373 return std::nullopt;

374 }

375 }

376

377 unsigned getNodeIndexForInsert(const NodeT *BB) {

378 if constexpr (GraphHasNodeNumbers<NodeT *>) {

379

380 unsigned Idx = *getNodeIndex(BB);

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

384 }

385 return Idx;

386 } else {

387

388 unsigned Idx =

392 return Idx;

393 }

394 }

395

396public:

397

398

399

400

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

406 return nullptr;

407 }

408

409

412 }

413

414

415

416

417

418

419

420

423

424

426 Result.clear();

428 if (!RN)

429 return;

432

433 while (!WL.empty()) {

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

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

437 }

438 }

439

440

441

442

445 if ( || )

446 return false;

447 if (A == B)

448 return false;

450 }

451

453

454

455

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

460 }

461

463

464

465

466

469

470 if (B == A)

471 return true;

472

473

475 return true;

476

477

479 return false;

480

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

482

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

484

485

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

487

488

489

490#ifdef EXPENSIVE_CHECKS

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

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

494#endif

495

497 return B->DominatedBy(A);

498

499

500

504 return B->DominatedBy(A);

505 }

506

507 return dominatedBySlowTreeWalk(A, B);

508 }

509

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

511

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

514 return this->Roots[0];

515 }

516

517

518

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

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

523

524

525

527 NodeT &Entry =

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

530 return &Entry;

531 }

532

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

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

537

538

539

540 while (NodeA != NodeB) {

542

543 NodeA = NodeA->IDom;

544 }

545

547 }

548

550 const NodeT *B) const {

551

552

554 const_cast<NodeT *>(B));

555 }

556

559 }

560

561 template

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

564

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

568

569

571 return nullptr;

572 }

573

574 return NCD;

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

611

614 Updates, true);

616 }

617

618

619

620

621

622

625 if (Updates.empty()) {

628 } else {

629

630

631

632

633

637 true);

640 }

641 }

642

643

644

645

646

647

648

649

650

651

658 }

659

660

661

662

663

664

665

666

667

668

669

676 }

677

678

679

680

681

682

683

684

685

686

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

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

693 }

694

695

696

697

698

699

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

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

704 DFSInfoValid = false;

708 } else {

713 OldNode->IDom = NewNode;

714 OldNode->UpdateLevel();

716 }

718 }

719

720

721

722

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

727 N->setIDom(NewIDom);

728 }

729

732 }

733

734

735

736

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

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

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

743

745

746

748 if (IDom) {

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

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

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

752

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

754 IDom->Children.pop_back();

755 }

756

758 if constexpr (!GraphHasNodeNumbers<NodeT *>)

760

761 if (!IsPostDom) return;

762

763

768 }

769 }

770

771

772

775 Split<Inverse<NodeT *>>(NewBB);

776 else

777 Split<NodeT *>(NewBB);

778 }

779

780

781

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

785 O << "Inorder PostDominator Tree: ";

786 else

787 O << "Inorder Dominator Tree: ";

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

790 O << "\n";

791

792

794 O << "Roots: ";

796 Block->printAsOperand(O, false);

797 O << " ";

798 }

799 O << "\n";

800 }

801

802public:

803

804

808 return;

809 }

810

813 32> WorkStack;

814

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

817 if (!ThisRoot)

818 return;

819

820

821

823

824 unsigned DFSNum = 0;

825 ThisRoot->DFSNumIn = DFSNum++;

826

827 while (!WorkStack.empty()) {

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

830

831

832

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

834 Node->DFSNumOut = DFSNum++;

836 } else {

837

839 ++WorkStack.back().second;

840

842 Child->DFSNumIn = DFSNum++;

843 }

844 }

845

848 }

849

850private:

851 void updateBlockNumberEpoch() {

852

853 if constexpr (GraphHasNodeNumbers<NodeT *>)

855 }

856

857public:

858

861 updateBlockNumberEpoch();

863 }

864

867 updateBlockNumberEpoch();

869 }

870

871

872 template

874 updateBlockNumberEpoch();

875

878 NewVector.resize(MaxNumber + 1);

881 continue;

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

883

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

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

887 }

889 }

890

891

892

893

894

895

896

897

898

899

900

901

902

903

904

907 }

908

911 if constexpr (!GraphHasNodeNumbers<NodeT *>)

918 }

919

920protected:

922

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

927 unsigned NodeIdx = getNodeIndexForInsert(BB);

929 if (IDom)

932 }

933

934

935

936 template

939 using NodeRef = typename GraphT::NodeRef;

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

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

943

945

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

947

948 bool NewBBDominatesNewBBSucc = true;

949 for (auto *Pred : inverse_children(NewBBSucc)) {

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

952 NewBBDominatesNewBBSucc = false;

953 break;

954 }

955 }

956

957

958

959 NodeT *NewBBIDom = nullptr;

960 unsigned i = 0;

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

963 NewBBIDom = PredBlocks[i];

964 break;

965 }

966

967

968

969

970 if (!NewBBIDom) return;

971

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

975 }

976

977

979

980

981

982 if (NewBBDominatesNewBBSucc) {

985 }

986 }

987

988 private:

994

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

997

998

999

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

1001 B = IDom;

1002

1003 return B == A;

1004 }

1005

1006

1007

1008

1009

1010 void wipe() {

1012 if constexpr (!GraphHasNodeNumbers<NodeT *>)

1016 }

1017};

1018

1019template

1021

1022template

1024

1025

1026

1027template <typename NodeT, bool IsPostDom>

1029 const NodeT *B) const {

1030 if (A == B)

1031 return true;

1032

1034}

1035template <typename NodeT, bool IsPostDom>

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

1038 if (A == B)

1039 return false;

1040

1042}

1043

1044}

1045

1046#endif

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

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

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

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.

iterator_range< iterator > children()

const_iterator end() const

DomTreeNodeBase *& back()

void setIDom(DomTreeNodeBase *NewIDom)

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

DomTreeNodeBase *const & back() const

DomTreeNodeBase * getIDom() const

unsigned getDFSNumIn() const

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

size_t getNumChildren() const

DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)

bool compare(const DomTreeNodeBase *Other) const

unsigned getLevel() const

iterator_range< const_iterator > children() const

unsigned getDFSNumOut() const

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

const_iterator begin() const

void addChild(DomTreeNodeBase *C)

Core dominator tree base class.

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

void print(raw_ostream &O) const

print - Convert to human readable form

typename NodeTrait::NodeType NodeType

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

See getNode.

typename SmallVectorImpl< NodeT * >::iterator root_iterator

Iteration over roots.

DomTreeNodeBase< NodeT > * getRootNode()

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

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

verify - checks if the tree is correct.

void changeImmediateDominator(NodeT *BB, NodeT *NewBB)

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

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

DominatorTreeBase()=default

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

iterator_range< root_iterator > roots()

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

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

std::remove_pointer_t< ParentPtr > ParentType

DominatorTreeBase(DominatorTreeBase &&Arg)

NodeT * findNearestCommonDominator(iterator_range< IteratorTy > Nodes) const

bool isPostDominator() const

isPostDominator - Returns true if analysis based of postdoms

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

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

Get all nodes dominated by R, including R itself.

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

Add a new node to the dominator tree information.

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

void applyUpdates(ArrayRef< UpdateType > Updates)

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

void insertEdge(NodeT *From, NodeT *To)

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

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

Update dominator tree after renumbering blocks.

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

dominates - Returns true iff A dominates B.

iterator_range< const_root_iterator > roots() const

const_root_iterator root_end() const

void splitBlock(NodeT *NewBB)

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

DominatorTreeBase & operator=(DominatorTreeBase &&RHS)

static constexpr UpdateKind Delete

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

void updateDFSNumbers() const

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

typename SmallVectorImpl< NodeT * >::const_iterator const_root_iterator

bool compare(const DominatorTreeBase &Other) const

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

DomTreeNodeBase< NodeT > * setNewRoot(NodeT *BB)

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

root_iterator root_begin()

DominatorTreeBase(const DominatorTreeBase &)=delete

static constexpr UpdateKind Insert

const_root_iterator root_begin() const

void recalculate(ParentType &Func)

recalculate - compute a dominator tree for the given function

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

void eraseNode(NodeT *BB)

eraseNode - Removes a node from the dominator tree.

void deleteEdge(NodeT *From, NodeT *To)

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

const DomTreeNodeBase< NodeT > * getRootNode() const

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

DomTreeNodeBase< NodeT > * RootNode

typename NodeTrait::NodePtr NodePtr

bool isReachableFromEntry(const NodeT *A) const

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

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

unsigned BlockNumberEpoch

DomTreeNodeStorageTy DomTreeNodes

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

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

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

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

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

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

typename NodeTrait::ParentPtr ParentPtr

DominatorTreeBase & operator=(const DominatorTreeBase &)=delete

static constexpr bool IsPostDominator

PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...

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)

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.

bool hasSingleElement(ContainerTy &&C)

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

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

OutputIt move(R &&Range, OutputIt Out)

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

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.

static NodeT * getEntryNode(ParentPtr Parent)

std::remove_pointer_t< ParentPtr > ParentType

static ParentPtr getParent(NodePtr BB)

decltype(std::declval< NodePtr >() ->getParent()) ParentPtr

typename GraphType::UnknownGraphTypeError NodeRef