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

562

563

564

565

566

567

568

569

570

571

572

573

574

575

576

577

578

579

580

581

582

583

584

585

586

587

588

589

590

591

592

593

594

595

598 Updates, true);

600 }

601

602

603

604

605

606

609 if (Updates.empty()) {

612 } else {

613

614

615

616

617

621 true);

624 }

625 }

626

627

628

629

630

631

632

633

634

635

642 }

643

644

645

646

647

648

649

650

651

652

653

660 }

661

662

663

664

665

666

667

668

669

670

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

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

677 }

678

679

680

681

682

683

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

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

688 DFSInfoValid = false;

692 } else {

697 OldNode->IDom = NewNode;

698 OldNode->UpdateLevel();

700 }

702 }

703

704

705

706

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

711 N->setIDom(NewIDom);

712 }

713

716 }

717

718

719

720

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

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

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

727

729

730

732 if (IDom) {

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

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

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

736

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

738 IDom->Children.pop_back();

739 }

740

742 if constexpr (!GraphHasNodeNumbers<NodeT *>)

744

745 if (!IsPostDom) return;

746

747

752 }

753 }

754

755

756

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

760 else

761 Split<NodeT *>(NewBB);

762 }

763

764

765

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

769 O << "Inorder PostDominator Tree: ";

770 else

771 O << "Inorder Dominator Tree: ";

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

774 O << "\n";

775

776

778 O << "Roots: ";

780 Block->printAsOperand(O, false);

781 O << " ";

782 }

783 O << "\n";

784 }

785

786public:

787

788

792 return;

793 }

794

797 32> WorkStack;

798

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

801 if (!ThisRoot)

802 return;

803

804

805

807

808 unsigned DFSNum = 0;

809 ThisRoot->DFSNumIn = DFSNum++;

810

811 while (!WorkStack.empty()) {

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

814

815

816

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

818 Node->DFSNumOut = DFSNum++;

820 } else {

821

823 ++WorkStack.back().second;

824

826 Child->DFSNumIn = DFSNum++;

827 }

828 }

829

832 }

833

834private:

835 void updateBlockNumberEpoch() {

836

837 if constexpr (GraphHasNodeNumbers<NodeT *>)

839 }

840

841public:

842

845 updateBlockNumberEpoch();

847 }

848

851 updateBlockNumberEpoch();

853 }

854

855

856 template

858 updateBlockNumberEpoch();

859

862 NewVector.resize(MaxNumber + 1);

865 continue;

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

867

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

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

871 }

873 }

874

875

876

877

878

879

880

881

882

883

884

885

886

887

888

891 }

892

895 if constexpr (!GraphHasNodeNumbers<NodeT *>)

902 }

903

904protected:

906

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

911 unsigned NodeIdx = getNodeIndexForInsert(BB);

913 if (IDom)

916 }

917

918

919

920 template

923 using NodeRef = typename GraphT::NodeRef;

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

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

927

929

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

931

932 bool NewBBDominatesNewBBSucc = true;

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

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

936 NewBBDominatesNewBBSucc = false;

937 break;

938 }

939 }

940

941

942

943 NodeT *NewBBIDom = nullptr;

944 unsigned i = 0;

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

947 NewBBIDom = PredBlocks[i];

948 break;

949 }

950

951

952

953

954 if (!NewBBIDom) return;

955

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

959 }

960

961

963

964

965

966 if (NewBBDominatesNewBBSucc) {

969 }

970 }

971

972 private:

978

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

981

982

983

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

985 B = IDom;

986

987 return B == A;

988 }

989

990

991

992

993

994 void wipe() {

996 if constexpr (!GraphHasNodeNumbers<NodeT *>)

1000 }

1001};

1002

1003template

1005

1006template

1008

1009

1010

1011template <typename NodeT, bool IsPostDom>

1013 const NodeT *B) const {

1014 if (A == B)

1015 return true;

1016

1018}

1019template <typename NodeT, bool IsPostDom>

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

1022 if (A == B)

1023 return false;

1024

1026}

1027

1028}

1029

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

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