Movatterモバイル変換

Go to the documentation of this file.

1//===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===//

2//

3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

4// See https://llvm.org/LICENSE.txt for license information.

5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

6//

7//===----------------------------------------------------------------------===//

8/// \file

9///

10/// This file defines a set of templates that efficiently compute a dominator

11/// tree over a generic graph. This is used typically in LLVM for fast

12/// dominance queries on the CFG, but is fully generic w.r.t. the underlying

13/// graph types.

14///

15/// Unlike ADT/* graph algorithms, generic dominator tree has more requirements

16/// on the graph's NodeRef. The NodeRef should be a pointer and,

17/// either NodeRef->getParent() must return the parent node that is also a

18/// pointer or DomTreeNodeTraits needs to be specialized.

19///

20/// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits.

21///

22//===----------------------------------------------------------------------===//

24#ifndef LLVM_SUPPORT_GENERICDOMTREE_H

25#define LLVM_SUPPORT_GENERICDOMTREE_H

27#include "llvm/ADT/DenseMap.h"

28#include "llvm/ADT/GraphTraits.h"

29#include "llvm/ADT/STLExtras.h"

30#include "llvm/ADT/SmallPtrSet.h"

31#include "llvm/ADT/SmallVector.h"

32#include "llvm/Support/CFGDiff.h"

33#include "llvm/Support/CFGUpdate.h"

34#include "llvm/Support/raw_ostream.h"

35#include <algorithm>

36#include <cassert>

37#include <cstddef>

38#include <iterator>

39#include <memory>

40#include <type_traits>

41#include <utility>

43namespacellvm {

45template <typename NodeT,bool IsPostDom>

46classDominatorTreeBase;

48namespaceDomTreeBuilder {

49template <typename DomTreeT>

50structSemiNCAInfo;

51}// namespace DomTreeBuilder

53/// Base class for the actual dominator tree node.

54template <class NodeT>classDomTreeNodeBase {

55friendclassPostDominatorTree;

56friendclassDominatorTreeBase<NodeT,false>;

57friendclassDominatorTreeBase<NodeT,true>;

58friendstructDomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT,false>>;

59friendstructDomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT,true>>;

61 NodeT *TheBB;

62DomTreeNodeBase *IDom;

63unsigned Level;

64SmallVector<DomTreeNodeBase *, 4> Children;

65mutableunsigned DFSNumIn = ~0;

66mutableunsigned DFSNumOut = ~0;

68public:

69DomTreeNodeBase(NodeT *BB,DomTreeNodeBase *iDom)

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

72usingiterator =typenameSmallVector<DomTreeNodeBase *, 4>::iterator;

73usingconst_iterator =

74typenameSmallVector<DomTreeNodeBase *, 4>::const_iterator;

76iterator begin() {return Children.begin(); }

77iterator end() {return Children.end(); }

78const_iterator begin() const{return Children.begin(); }

79const_iterator end() const{return Children.end(); }

81DomTreeNodeBase *const &back() const{return Children.back(); }

82DomTreeNodeBase *&back() {return Children.back(); }

84iterator_range<iterator>children() {returnmake_range(begin(),end()); }

85iterator_range<const_iterator>children() const{

86returnmake_range(begin(),end());

87 }

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

90DomTreeNodeBase *getIDom() const{return IDom; }

91unsignedgetLevel() const{return Level; }

93voidaddChild(DomTreeNodeBase *C) { Children.push_back(C); }

95boolisLeaf() const{return Children.empty(); }

96size_tgetNumChildren() const{return Children.size(); }

98voidclearAllChildren() { Children.clear(); }

100boolcompare(constDomTreeNodeBase *Other) const{

101if (getNumChildren() !=Other->getNumChildren())

102returntrue;

103

104if (Level !=Other->Level)returntrue;

105

106SmallPtrSet<const NodeT *, 4> OtherChildren;

107for (constDomTreeNodeBase *I : *Other) {

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

109 OtherChildren.insert(Nd);

110 }

111

112for (constDomTreeNodeBase *I : *this) {

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

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

115returntrue;

116 }

117returnfalse;

118 }

119

120voidsetIDom(DomTreeNodeBase *NewIDom) {

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

122if (IDom == NewIDom)return;

123

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

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

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

127// I am no longer your child...

128 IDom->Children.erase(I);

129

130// Switch to new dominator

131 IDom = NewIDom;

132 IDom->Children.push_back(this);

133

134 UpdateLevel();

135 }

136

137 /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes

138 /// in the dominator tree. They are only guaranteed valid if

139 /// updateDFSNumbers() has been called.

140unsignedgetDFSNumIn() const{return DFSNumIn; }

141unsignedgetDFSNumOut() const{return DFSNumOut; }

142

143private:

144// Return true if this node is dominated by other. Use this only if DFS info

145// is valid.

146bool DominatedBy(constDomTreeNodeBase *other) const{

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

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

149 }

150

151void UpdateLevel() {

152assert(IDom);

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

154

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

156

157while (!WorkStack.empty()) {

158DomTreeNodeBase *Current = WorkStack.pop_back_val();

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

160

161for (DomTreeNodeBase *C : *Current) {

162assert(C->IDom);

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

164 }

165 }

166 }

167};

168

169template <class NodeT>

170raw_ostream &operator<<(raw_ostream &O,constDomTreeNodeBase<NodeT> *Node) {

171if (Node->getBlock())

172Node->getBlock()->printAsOperand(O,false);

173else

174 O <<" <<exit node>>";

175

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

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

178

179return O;

180}

181

182template <class NodeT>

183voidPrintDomTree(constDomTreeNodeBase<NodeT> *N,raw_ostream &O,

184unsigned Lev) {

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

186for (constauto &I : *N)

187 PrintDomTree<NodeT>(I, O, Lev + 1);

188}

189

190namespaceDomTreeBuilder {

191// The routines below are provided in a separate header but referenced here.

192template <typename DomTreeT>

193voidCalculate(DomTreeT &DT);

194

195template <typename DomTreeT>

196voidCalculateWithUpdates(DomTreeT &DT,

197 ArrayRef<typename DomTreeT::UpdateType> Updates);

198

199template <typename DomTreeT>

200voidInsertEdge(DomTreeT &DT,typename DomTreeT::NodePtrFrom,

201typename DomTreeT::NodePtr To);

202

203template <typename DomTreeT>

204voidDeleteEdge(DomTreeT &DT,typename DomTreeT::NodePtrFrom,

205typename DomTreeT::NodePtr To);

206

207template <typename DomTreeT>

208voidApplyUpdates(DomTreeT &DT,

209 GraphDiff<typename DomTreeT::NodePtr,

210 DomTreeT::IsPostDominator> &PreViewCFG,

211 GraphDiff<typename DomTreeT::NodePtr,

212 DomTreeT::IsPostDominator> *PostViewCFG);

213

214template <typename DomTreeT>

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

216}// namespace DomTreeBuilder

217

218/// Default DomTreeNode traits for NodeT. The default implementation assume a

219/// Function-like NodeT. Can be specialized to support different node types.

220template <typename NodeT>structDomTreeNodeTraits {

221usingNodeType = NodeT;

222usingNodePtr = NodeT *;

223usingParentPtr =decltype(std::declval<NodePtr>()->getParent());

224static_assert(std::is_pointer_v<ParentPtr>,

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

226usingParentType = std::remove_pointer_t<ParentPtr>;

227

228static NodeT *getEntryNode(ParentPtr Parent) {return &Parent->front(); }

229staticParentPtr getParent(NodePtr BB) {return BB->getParent(); }

230};

231

232/// Core dominator tree base class.

233///

234/// This class is a generic template over graph nodes. It is instantiated for

235/// various graphs in the LLVM IR or in the code generator.

236template <typename NodeT,bool IsPostDom>

237classDominatorTreeBase {

238public:

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

240"Currently DominatorTreeBase supports only pointer nodes");

241usingNodeTrait =DomTreeNodeTraits<NodeT>;

242usingNodeType =typenameNodeTrait::NodeType;

243usingNodePtr =typenameNodeTrait::NodePtr;

244usingParentPtr =typenameNodeTrait::ParentPtr;

245static_assert(std::is_pointer_v<ParentPtr>,

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

247usingParentType = std::remove_pointer_t<ParentPtr>;

248staticconstexprboolIsPostDominator = IsPostDom;

249

250usingUpdateType =cfg::Update<NodePtr>;

251usingUpdateKind =cfg::UpdateKind;

252staticconstexprUpdateKind Insert = UpdateKind::Insert;

253staticconstexprUpdateKind Delete = UpdateKind::Delete;

254

255enum classVerificationLevel {Fast,Basic,Full };

256

257protected:

258// Dominators always have a single root, postdominators can have more.

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

260

261usingDomTreeNodeStorageTy =

262SmallVector<std::unique_ptr<DomTreeNodeBase<NodeT>>>;

263DomTreeNodeStorageTy DomTreeNodes;

264// For graphs where blocks don't have numbers, create a numbering here.

265// TODO: use an empty struct with [[no_unique_address]] in C++20.

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

267DenseMap<const NodeT *, unsigned>, std::tuple<>>

268NodeNumberMap;

269DomTreeNodeBase<NodeT> *RootNode =nullptr;

270ParentPtr Parent =nullptr;

271

272mutableboolDFSInfoValid =false;

273mutableunsignedintSlowQueries = 0;

274unsignedBlockNumberEpoch = 0;

275

276friendstructDomTreeBuilder::SemiNCAInfo<DominatorTreeBase>;

277

278public:

279DominatorTreeBase() =default;

280

281DominatorTreeBase(DominatorTreeBase &&Arg)

282 :Roots(std::move(Arg.Roots)),DomTreeNodes(std::move(Arg.DomTreeNodes)),

283NodeNumberMap(std::move(Arg.NodeNumberMap)),RootNode(Arg.RootNode),

284Parent(Arg.Parent),DFSInfoValid(Arg.DFSInfoValid),

285SlowQueries(Arg.SlowQueries),BlockNumberEpoch(Arg.BlockNumberEpoch) {

286 Arg.wipe();

287 }

288

289DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {

290if (this == &RHS)

291return *this;

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

293DomTreeNodes = std::move(RHS.DomTreeNodes);

294NodeNumberMap = std::move(RHS.NodeNumberMap);

295RootNode =RHS.RootNode;

296Parent =RHS.Parent;

297DFSInfoValid =RHS.DFSInfoValid;

298SlowQueries =RHS.SlowQueries;

299BlockNumberEpoch =RHS.BlockNumberEpoch;

300RHS.wipe();

301return *this;

302 }

303

304DominatorTreeBase(constDominatorTreeBase &) =delete;

305DominatorTreeBase &operator=(constDominatorTreeBase &) =delete;

306

307 /// Iteration over roots.

308 ///

309 /// This may include multiple blocks if we are computing post dominators.

310 /// For forward dominators, this will always be a single block (the entry

311 /// block).

312usingroot_iterator =typenameSmallVectorImpl<NodeT *>::iterator;

313usingconst_root_iterator =typenameSmallVectorImpl<NodeT *>::const_iterator;

314

315root_iterator root_begin() {returnRoots.begin(); }

316const_root_iterator root_begin() const{returnRoots.begin(); }

317root_iterator root_end() {returnRoots.end(); }

318const_root_iterator root_end() const{returnRoots.end(); }

319

320size_troot_size() const{returnRoots.size(); }

321

322iterator_range<root_iterator>roots() {

323returnmake_range(root_begin(),root_end());

324 }

325iterator_range<const_root_iterator>roots() const{

326returnmake_range(root_begin(),root_end());

327 }

328

329 /// isPostDominator - Returns true if analysis based of postdoms

330 ///

331boolisPostDominator() const{returnIsPostDominator; }

332

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

334 /// dominator tree base. Otherwise return true.

335boolcompare(constDominatorTreeBase &Other) const{

336if (Parent !=Other.Parent)returntrue;

337

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

339returntrue;

340

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

342returntrue;

343

344size_t NumNodes = 0;

345// All nodes we have must exist and be equal in the other tree.

346for (constauto &Node :DomTreeNodes) {

347if (!Node)

348continue;

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

350returntrue;

351 NumNodes++;

352 }

353

354// If the other tree has more nodes than we have, they're not equal.

355size_t NumOtherNodes = 0;

356for (constauto &OtherNode :Other.DomTreeNodes)

357if (OtherNode)

358 NumOtherNodes++;

359return NumNodes != NumOtherNodes;

360 }

361

362private:

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

364ifconstexpr (GraphHasNodeNumbers<NodeT *>) {

365// BB can be nullptr, map nullptr to index 0.

366assert(BlockNumberEpoch ==

367GraphTraits<ParentPtr>::getNumberEpoch(Parent) &&

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

369return BB ?GraphTraits<const NodeT *>::getNumber(BB) + 1 : 0;

370 }else {

371if (auto It =NodeNumberMap.find(BB); It !=NodeNumberMap.end())

372return It->second;

373return std::nullopt;

374 }

375 }

376

377unsigned getNodeIndexForInsert(const NodeT *BB) {

378ifconstexpr (GraphHasNodeNumbers<NodeT *>) {

379// getNodeIndex will never fail if nodes have getNumber().

380unsignedIdx = *getNodeIndex(BB);

381if (Idx >=DomTreeNodes.size()) {

382unsignedMax = GraphTraits<ParentPtr>::getMaxNumber(Parent);

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

384 }

385returnIdx;

386 }else {

387// We might already have a number stored for BB.

388unsignedIdx =

389NodeNumberMap.try_emplace(BB,DomTreeNodes.size()).first->second;

390if (Idx >=DomTreeNodes.size())

391DomTreeNodes.resize(Idx + 1);

392returnIdx;

393 }

394 }

395

396public:

397 /// getNode - return the (Post)DominatorTree node for the specified basic

398 /// block. This is the same as using operator[] on this class. The result

399 /// may (but is not required to) be null for a forward (backwards)

400 /// statically unreachable block.

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

402assert((!BB ||Parent ==NodeTrait::getParent(const_cast<NodeT *>(BB))) &&

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

404if (autoIdx = getNodeIndex(BB);Idx && *Idx <DomTreeNodes.size())

405returnDomTreeNodes[*Idx].get();

406returnnullptr;

407 }

408

409 /// See getNode.

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

411returngetNode(BB);

412 }

413

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

415 /// this tree represents the post-dominance relations for a function, however,

416 /// this root may be a node with the block == NULL. This is the case when

417 /// there are multiple exit nodes from a particular function. Consumers of

418 /// post-dominance information must be capable of dealing with this

419 /// possibility.

420 ///

421DomTreeNodeBase<NodeT> *getRootNode() {returnRootNode; }

422constDomTreeNodeBase<NodeT> *getRootNode() const{returnRootNode; }

423

424 /// Get all nodes dominated by R, including R itself.

425voidgetDescendants(NodeT *R,SmallVectorImpl<NodeT *> &Result) const{

426 Result.clear();

427constDomTreeNodeBase<NodeT> *RN =getNode(R);

428if (!RN)

429return;// If R is unreachable, it will not be present in the DOM tree.

430SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;

431 WL.push_back(RN);

432

433while (!WL.empty()) {

434constDomTreeNodeBase<NodeT> *N = WL.pop_back_val();

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

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

437 }

438 }

439

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

441 /// Note that this is not a constant time operation!

442 ///

443boolproperlyDominates(constDomTreeNodeBase<NodeT> *A,

444constDomTreeNodeBase<NodeT> *B) const{

445if (!A || !B)

446returnfalse;

447if (A ==B)

448returnfalse;

449returndominates(A,B);

450 }

451

452boolproperlyDominates(const NodeT *A,const NodeT *B)const;

453

454 /// isReachableFromEntry - Return true if A is dominated by the entry

455 /// block of the function containing it.

456boolisReachableFromEntry(const NodeT *A) const{

457assert(!this->isPostDominator() &&

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

459returnisReachableFromEntry(getNode(A));

460 }

461

462boolisReachableFromEntry(constDomTreeNodeBase<NodeT> *A) const{returnA; }

463

464 /// dominates - Returns true iff A dominates B. Note that this is not a

465 /// constant time operation!

466 ///

467booldominates(constDomTreeNodeBase<NodeT> *A,

468constDomTreeNodeBase<NodeT> *B) const{

469// A node trivially dominates itself.

470if (B ==A)

471returntrue;

472

473// An unreachable node is dominated by anything.

474if (!isReachableFromEntry(B))

475returntrue;

476

477// And dominates nothing.

478if (!isReachableFromEntry(A))

479returnfalse;

480

481if (B->getIDom() ==A)returntrue;

482

483if (A->getIDom() ==B)returnfalse;

484

485// A can only dominate B if it is higher in the tree.

486if (A->getLevel() >=B->getLevel())returnfalse;

487

488// Compare the result of the tree walk and the dfs numbers, if expensive

489// checks are enabled.

490#ifdef EXPENSIVE_CHECKS

491assert((!DFSInfoValid ||

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

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

494#endif

495

496if (DFSInfoValid)

497returnB->DominatedBy(A);

498

499// If we end up with too many slow queries, just update the

500// DFS numbers on the theory that we are going to keep querying.

501SlowQueries++;

502if (SlowQueries > 32) {

503updateDFSNumbers();

504returnB->DominatedBy(A);

505 }

506

507return dominatedBySlowTreeWalk(A,B);

508 }

509

510booldominates(const NodeT *A,const NodeT *B)const;

511

512 NodeT *getRoot() const{

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

514return this->Roots[0];

515 }

516

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

518 /// must have tree nodes.

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

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

521assert(NodeTrait::getParent(A) ==NodeTrait::getParent(B) &&

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

523

524// If either A or B is a entry block then it is nearest common dominator

525// (for forward-dominators).

526if (!isPostDominator()) {

527 NodeT &Entry =

528 *DomTreeNodeTraits<NodeT>::getEntryNode(NodeTrait::getParent(A));

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

530return &Entry;

531 }

532

533DomTreeNodeBase<NodeT> *NodeA =getNode(A);

534DomTreeNodeBase<NodeT> *NodeB =getNode(B);

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

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

537

538// Use level information to go up the tree until the levels match. Then

539// continue going up til we arrive at the same node.

540while (NodeA != NodeB) {

541if (NodeA->getLevel() < NodeB->getLevel())std::swap(NodeA, NodeB);

542

543 NodeA = NodeA->IDom;

544 }

545

546return NodeA->getBlock();

547 }

548

549const NodeT *findNearestCommonDominator(const NodeT *A,

550const NodeT *B) const{

551// Cast away the const qualifiers here. This is ok since

552// const is re-introduced on the return type.

553returnfindNearestCommonDominator(const_cast<NodeT *>(A),

554const_cast<NodeT *>(B));

555 }

556

557boolisVirtualRoot(constDomTreeNodeBase<NodeT> *A) const{

558returnisPostDominator() && !A->getBlock();

559 }

560

561template <typename IteratorTy>

562 NodeT *findNearestCommonDominator(iterator_range<IteratorTy> Nodes) const{

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

564

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

566for (NodeT *Node :llvm::drop_begin(Nodes)) {

567 NCD =findNearestCommonDominator(NCD,Node);

568

569// Stop when the root is reached.

570if (isVirtualRoot(getNode(NCD)))

571returnnullptr;

572 }

573

574return NCD;

575 }

576

577//===--------------------------------------------------------------------===//

578// API to update (Post)DominatorTree information based on modifications to

579// the CFG...

580

581 /// Inform the dominator tree about a sequence of CFG edge insertions and

582 /// deletions and perform a batch update on the tree.

583 ///

584 /// This function should be used when there were multiple CFG updates after

585 /// the last dominator tree update. It takes care of performing the updates

586 /// in sync with the CFG and optimizes away the redundant operations that

587 /// cancel each other.

588 /// The functions expects the sequence of updates to be balanced. Eg.:

589 /// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because

590 /// logically it results in a single insertions.

591 /// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make

592 /// sense to insert the same edge twice.

593 ///

594 /// What's more, the functions assumes that it's safe to ask every node in the

595 /// CFG about its children and inverse children. This implies that deletions

596 /// of CFG edges must not delete the CFG nodes before calling this function.

597 ///

598 /// The applyUpdates function can reorder the updates and remove redundant

599 /// ones internally (as long as it is done in a deterministic fashion). The

600 /// batch updater is also able to detect sequences of zero and exactly one

601 /// update -- it's optimized to do less work in these cases.

602 ///

603 /// Note that for postdominators it automatically takes care of applying

604 /// updates on reverse edges internally (so there's no need to swap the

605 /// From and To pointers when constructing DominatorTree::UpdateType).

606 /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>

607 /// with the same template parameter T.

608 ///

609 /// \param Updates An ordered sequence of updates to perform. The current CFG

610 /// and the reverse of these updates provides the pre-view of the CFG.

611 ///

612voidapplyUpdates(ArrayRef<UpdateType> Updates) {

613GraphDiff<NodePtr, IsPostDominator> PreViewCFG(

614 Updates,/*ReverseApplyUpdates=*/true);

615DomTreeBuilder::ApplyUpdates(*this, PreViewCFG,nullptr);

616 }

617

618 /// \param Updates An ordered sequence of updates to perform. The current CFG

619 /// and the reverse of these updates provides the pre-view of the CFG.

620 /// \param PostViewUpdates An ordered sequence of update to perform in order

621 /// to obtain a post-view of the CFG. The DT will be updated assuming the

622 /// obtained PostViewCFG is the desired end state.

623voidapplyUpdates(ArrayRef<UpdateType> Updates,

624ArrayRef<UpdateType> PostViewUpdates) {

625if (Updates.empty()) {

626GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates);

627DomTreeBuilder::ApplyUpdates(*this, PostViewCFG, &PostViewCFG);

628 }else {

629// PreViewCFG needs to merge Updates and PostViewCFG. The updates in

630// Updates need to be reversed, and match the direction in PostViewCFG.

631// The PostViewCFG is created with updates reversed (equivalent to changes

632// made to the CFG), so the PreViewCFG needs all the updates reverse

633// applied.

634SmallVector<UpdateType> AllUpdates(Updates);

635append_range(AllUpdates, PostViewUpdates);

636GraphDiff<NodePtr, IsPostDom> PreViewCFG(AllUpdates,

637/*ReverseApplyUpdates=*/true);

638GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates);

639DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, &PostViewCFG);

640 }

641 }

642

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

644 ///

645 /// This function has to be called just before or just after making the update

646 /// on the actual CFG. There cannot be any other updates that the dominator

647 /// tree doesn't know about.

648 ///

649 /// Note that for postdominators it automatically takes care of inserting

650 /// a reverse edge internally (so there's no need to swap the parameters).

651 ///

652voidinsertEdge(NodeT *From, NodeT *To) {

653assert(From);

654assert(To);

655assert(NodeTrait::getParent(From) ==Parent);

656assert(NodeTrait::getParent(To) ==Parent);

657DomTreeBuilder::InsertEdge(*this,From, To);

658 }

659

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

661 ///

662 /// This function has to be called just after making the update on the actual

663 /// CFG. An internal functions checks if the edge doesn't exist in the CFG in

664 /// DEBUG mode. There cannot be any other updates that the

665 /// dominator tree doesn't know about.

666 ///

667 /// Note that for postdominators it automatically takes care of deleting

668 /// a reverse edge internally (so there's no need to swap the parameters).

669 ///

670voiddeleteEdge(NodeT *From, NodeT *To) {

671assert(From);

672assert(To);

673assert(NodeTrait::getParent(From) ==Parent);

674assert(NodeTrait::getParent(To) ==Parent);

675DomTreeBuilder::DeleteEdge(*this,From, To);

676 }

677

678 /// Add a new node to the dominator tree information.

679 ///

680 /// This creates a new node as a child of DomBB dominator node, linking it

681 /// into the children list of the immediate dominator.

682 ///

683 /// \param BB New node in CFG.

684 /// \param DomBB CFG node that is dominator for BB.

685 /// \returns New dominator tree node that represents new CFG node.

686 ///

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

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

689DomTreeNodeBase<NodeT> *IDomNode =getNode(DomBB);

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

691DFSInfoValid =false;

692returncreateNode(BB, IDomNode);

693 }

694

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

696 ///

697 /// \param BB New node in CFG.

698 /// \returns New dominator tree node that represents new CFG node.

699 ///

700DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) {

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

702assert(!this->isPostDominator() &&

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

704 DFSInfoValid =false;

705DomTreeNodeBase<NodeT> *NewNode =createNode(BB);

706if (Roots.empty()) {

707addRoot(BB);

708 }else {

709assert(Roots.size() == 1);

710 NodeT *OldRoot =Roots.front();

711DomTreeNodeBase<NodeT> *OldNode =getNode(OldRoot);

712 NewNode->addChild(OldNode);

713 OldNode->IDom = NewNode;

714 OldNode->UpdateLevel();

715Roots[0] = BB;

716 }

717returnRootNode = NewNode;

718 }

719

720 /// changeImmediateDominator - This method is used to update the dominator

721 /// tree information when a node's immediate dominator changes.

722 ///

723voidchangeImmediateDominator(DomTreeNodeBase<NodeT> *N,

724DomTreeNodeBase<NodeT> *NewIDom) {

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

726DFSInfoValid =false;

727N->setIDom(NewIDom);

728 }

729

730voidchangeImmediateDominator(NodeT *BB, NodeT *NewBB) {

731changeImmediateDominator(getNode(BB),getNode(NewBB));

732 }

733

734 /// eraseNode - Removes a node from the dominator tree. Block must not

735 /// dominate any other blocks. Removes node from its immediate dominator's

736 /// children list. Deletes dominator node associated with basic block BB.

737voideraseNode(NodeT *BB) {

738 std::optional<unsigned> IdxOpt = getNodeIndex(BB);

739assert(IdxOpt &&DomTreeNodes[*IdxOpt] &&

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

741DomTreeNodeBase<NodeT> *Node =DomTreeNodes[*IdxOpt].get();

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

743

744DFSInfoValid =false;

745

746// Remove node from immediate dominator's children list.

747DomTreeNodeBase<NodeT> *IDom =Node->getIDom();

748if (IDom) {

749constautoI =find(IDom->Children,Node);

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

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

752// I am no longer your child...

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

754 IDom->Children.pop_back();

755 }

756

757DomTreeNodes[*IdxOpt] =nullptr;

758ifconstexpr (!GraphHasNodeNumbers<NodeT *>)

759NodeNumberMap.erase(BB);

760

761if (!IsPostDom)return;

762

763// Remember to update PostDominatorTree roots.

764auto RIt =llvm::find(Roots, BB);

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

766std::swap(*RIt,Roots.back());

767Roots.pop_back();

768 }

769 }

770

771 /// splitBlock - BB is split and now it has one successor. Update dominator

772 /// tree to reflect this change.

773voidsplitBlock(NodeT *NewBB) {

774if (IsPostDominator)

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

776else

777 Split<NodeT *>(NewBB);

778 }

779

780 /// print - Convert to human readable form

781 ///

782voidprint(raw_ostream &O) const{

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

784if (IsPostDominator)

785 O <<"Inorder PostDominator Tree: ";

786else

787 O <<"Inorder Dominator Tree: ";

788if (!DFSInfoValid)

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

790 O <<"\n";

791

792// The postdom tree can have a null root if there are no returns.

793if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);

794 O <<"Roots: ";

795for (constNodePtr Block :Roots) {

796Block->printAsOperand(O,false);

797 O <<" ";

798 }

799 O <<"\n";

800 }

801

802public:

803 /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking

804 /// dominator tree in dfs order.

805voidupdateDFSNumbers() const{

806if (DFSInfoValid) {

807SlowQueries = 0;

808return;

809 }

810

811SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,

812typenameDomTreeNodeBase<NodeT>::const_iterator>,

813 32> WorkStack;

814

815constDomTreeNodeBase<NodeT> *ThisRoot =getRootNode();

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

817if (!ThisRoot)

818return;

819

820// Both dominators and postdominators have a single root node. In the case

821// case of PostDominatorTree, this node is a virtual root.

822 WorkStack.push_back({ThisRoot, ThisRoot->begin()});

823

824unsigned DFSNum = 0;

825 ThisRoot->DFSNumIn = DFSNum++;

826

827while (!WorkStack.empty()) {

828constDomTreeNodeBase<NodeT> *Node = WorkStack.back().first;

829constauto ChildIt = WorkStack.back().second;

830

831// If we visited all of the children of this node, "recurse" back up the

832// stack setting the DFOutNum.

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

834Node->DFSNumOut = DFSNum++;

835 WorkStack.pop_back();

836 }else {

837// Otherwise, recursively visit this child.

838constDomTreeNodeBase<NodeT> *Child = *ChildIt;

839 ++WorkStack.back().second;

840

841 WorkStack.push_back({Child, Child->begin()});

842 Child->DFSNumIn = DFSNum++;

843 }

844 }

845

846SlowQueries = 0;

847DFSInfoValid =true;

848 }

849

850private:

851void updateBlockNumberEpoch() {

852// Nothing to do for graphs that don't number their blocks.

853ifconstexpr (GraphHasNodeNumbers<NodeT *>)

854BlockNumberEpoch =GraphTraits<ParentPtr>::getNumberEpoch(Parent);

855 }

856

857public:

858 /// recalculate - compute a dominator tree for the given function

859voidrecalculate(ParentType &Func) {

860Parent = &Func;

861 updateBlockNumberEpoch();

862DomTreeBuilder::Calculate(*this);

863 }

864

865voidrecalculate(ParentType &Func,ArrayRef<UpdateType> Updates) {

866Parent = &Func;

867 updateBlockNumberEpoch();

868DomTreeBuilder::CalculateWithUpdates(*this, Updates);

869 }

870

871 /// Update dominator tree after renumbering blocks.

872template <typename T = NodeT>

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

874 updateBlockNumberEpoch();

875

876unsigned MaxNumber =GraphTraits<ParentPtr>::getMaxNumber(Parent);

877DomTreeNodeStorageTy NewVector;

878 NewVector.resize(MaxNumber + 1);// +1, because index 0 is for nullptr

879for (auto &Node :DomTreeNodes) {

880if (!Node)

881continue;

882unsignedIdx = *getNodeIndex(Node->getBlock());

883// getMaxNumber is not necessarily supported

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

885 NewVector.resize(Idx + 1);

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

887 }

888DomTreeNodes = std::move(NewVector);

889 }

890

891 /// verify - checks if the tree is correct. There are 3 level of verification:

892 /// - Full -- verifies if the tree is correct by making sure all the

893 /// properties (including the parent and the sibling property)

894 /// hold.

895 /// Takes O(N^3) time.

896 ///

897 /// - Basic -- checks if the tree is correct, but compares it to a freshly

898 /// constructed tree instead of checking the sibling property.

899 /// Takes O(N^2) time.

900 ///

901 /// - Fast -- checks basic tree structure and compares it with a freshly

902 /// constructed tree.

903 /// Takes O(N^2) time worst case, but is faster in practise (same

904 /// as tree construction).

905boolverify(VerificationLevel VL =VerificationLevel::Full) const{

906returnDomTreeBuilder::Verify(*this, VL);

907 }

908

909voidreset() {

910DomTreeNodes.clear();

911ifconstexpr (!GraphHasNodeNumbers<NodeT *>)

912NodeNumberMap.clear();

913Roots.clear();

914RootNode =nullptr;

915Parent =nullptr;

916DFSInfoValid =false;

917SlowQueries = 0;

918 }

919

920protected:

921voidaddRoot(NodeT *BB) { this->Roots.push_back(BB); }

922

923DomTreeNodeBase<NodeT> *createNode(NodeT *BB,

924DomTreeNodeBase<NodeT> *IDom =nullptr) {

925autoNode = std::make_unique<DomTreeNodeBase<NodeT>>(BB, IDom);

926auto *NodePtr =Node.get();

927unsigned NodeIdx = getNodeIndexForInsert(BB);

928DomTreeNodes[NodeIdx] = std::move(Node);

929if (IDom)

930 IDom->addChild(NodePtr);

931returnNodePtr;

932 }

933

934// NewBB is split and now it has one successor. Update dominator tree to

935// reflect this change.

936template <class N>

937voidSplit(typenameGraphTraits<N>::NodeRef NewBB) {

938usingGraphT =GraphTraits<N>;

939usingNodeRef =typename GraphT::NodeRef;

940assert(llvm::hasSingleElement(children<N>(NewBB)) &&

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

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

943

944SmallVector<NodeRef, 4> PredBlocks(inverse_children<N>(NewBB));

945

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

947

948bool NewBBDominatesNewBBSucc =true;

949for (auto *Pred : inverse_children<N>(NewBBSucc)) {

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

951isReachableFromEntry(Pred)) {

952 NewBBDominatesNewBBSucc =false;

953break;

954 }

955 }

956

957// Find NewBB's immediate dominator and create new dominator tree node for

958// NewBB.

959 NodeT *NewBBIDom =nullptr;

960unsigned i = 0;

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

962if (isReachableFromEntry(PredBlocks[i])) {

963 NewBBIDom = PredBlocks[i];

964break;

965 }

966

967// It's possible that none of the predecessors of NewBB are reachable;

968// in that case, NewBB itself is unreachable, so nothing needs to be

969// changed.

970if (!NewBBIDom)return;

971

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

973if (isReachableFromEntry(PredBlocks[i]))

974 NewBBIDom =findNearestCommonDominator(NewBBIDom, PredBlocks[i]);

975 }

976

977// Create the new dominator tree node... and set the idom of NewBB.

978DomTreeNodeBase<NodeT> *NewBBNode =addNewBlock(NewBB, NewBBIDom);

979

980// If NewBB strictly dominates other blocks, then it is now the immediate

981// dominator of NewBBSucc. Update the dominator tree as appropriate.

982if (NewBBDominatesNewBBSucc) {

983DomTreeNodeBase<NodeT> *NewBBSuccNode =getNode(NewBBSucc);

984changeImmediateDominator(NewBBSuccNode, NewBBNode);

985 }

986 }

987

988private:

989bool dominatedBySlowTreeWalk(constDomTreeNodeBase<NodeT> *A,

990constDomTreeNodeBase<NodeT> *B) const{

991assert(A !=B);

992assert(isReachableFromEntry(B));

993assert(isReachableFromEntry(A));

994

995constunsigned ALevel =A->getLevel();

996constDomTreeNodeBase<NodeT> *IDom;

997

998// Don't walk nodes above A's subtree. When we reach A's level, we must

999// either find A or be in some other subtree not dominated by A.

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

1001B = IDom;// Walk up the tree

1002

1003returnB ==A;

1004 }

1005

1006 /// Wipe this tree's state without releasing any resources.

1007 ///

1008 /// This is essentially a post-move helper only. It leaves the object in an

1009 /// assignable and destroyable state, but otherwise invalid.

1010void wipe() {

1011DomTreeNodes.clear();

1012ifconstexpr (!GraphHasNodeNumbers<NodeT *>)

1013NodeNumberMap.clear();

1014RootNode =nullptr;

1015Parent =nullptr;

1016 }

1017};

1018

1019template <typename T>

1020usingDomTreeBase =DominatorTreeBase<T, false>;

1021

1022template <typename T>

1023usingPostDomTreeBase =DominatorTreeBase<T, true>;

1024

1025// These two functions are declared out of line as a workaround for building

1026// with old (< r147295) versions of clang because of pr11642.

1027template <typename NodeT,bool IsPostDom>

1028boolDominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A,

1029const NodeT *B) const{

1030if (A ==B)

1031returntrue;

1032

1033returndominates(getNode(A),getNode(B));

1034}

1035template <typename NodeT,bool IsPostDom>

1036boolDominatorTreeBase<NodeT, IsPostDom>::properlyDominates(

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

1038if (A ==B)

1039returnfalse;

1040

1041returndominates(getNode(A),getNode(B));

1042}

1043

1044}// end namespace llvm

1045

1046#endif// LLVM_SUPPORT_GENERICDOMTREE_H

getNode

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

Definition:AMDGPUDelayedMCExpr.cpp:15

true

basic Basic Alias true

Definition:BasicAliasAnalysis.cpp:1981

From

BlockVerifier::State From

Definition:BlockVerifier.cpp:57

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

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

CFGDiff.h

CFGUpdate.h

Idx

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

Definition:DeadArgumentElimination.cpp:353

DenseMap.h

This file defines the DenseMap class.

GraphTraits.h

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

#define I(x, y, z)

Definition:MD5.cpp:58

Verify

ppc ctr loops PowerPC CTR Loops Verify

Definition:PPCCTRLoopsVerify.cpp:73

dominates

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

Definition:RegAllocFast.cpp:485

assert

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

STLExtras.h

This file contains some templates that are useful if you are working with the STL at all.

SmallPtrSet.h

This file defines the SmallPtrSet class.

SmallVector.h

This file defines the SmallVector class.

RHS

Value * RHS

Definition:X86PartialReduction.cpp:74

Node

Definition:ItaniumDemangle.h:163

Node::printAsOperand

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

Definition:ItaniumDemangle.h:272

llvm::ArrayRef

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

Definition:ArrayRef.h:41

llvm::ArrayRef::empty

bool empty() const

empty - Check if the array is empty.

Definition:ArrayRef.h:163

llvm::DenseMap

Definition:DenseMap.h:727

llvm::DomTreeNodeBase

Base class for the actual dominator tree node.

Definition:GenericDomTree.h:54

llvm::DomTreeNodeBase::children

iterator_range< iterator > children()

Definition:GenericDomTree.h:84

llvm::DomTreeNodeBase::end

const_iterator end() const

Definition:GenericDomTree.h:79

llvm::DomTreeNodeBase::isLeaf

bool isLeaf() const

Definition:GenericDomTree.h:95

llvm::DomTreeNodeBase::back

DomTreeNodeBase *& back()

Definition:GenericDomTree.h:82

llvm::DomTreeNodeBase::setIDom

void setIDom(DomTreeNodeBase *NewIDom)

Definition:GenericDomTree.h:120

llvm::DomTreeNodeBase::iterator

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

Definition:GenericDomTree.h:72

llvm::DomTreeNodeBase::clearAllChildren

void clearAllChildren()

Definition:GenericDomTree.h:98

llvm::DomTreeNodeBase::back

DomTreeNodeBase *const & back() const

Definition:GenericDomTree.h:81

llvm::DomTreeNodeBase::begin

iterator begin()

Definition:GenericDomTree.h:76

llvm::DomTreeNodeBase::getIDom

DomTreeNodeBase * getIDom() const

Definition:GenericDomTree.h:90

llvm::DomTreeNodeBase::getDFSNumIn

unsigned getDFSNumIn() const

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

Definition:GenericDomTree.h:140

llvm::DomTreeNodeBase::end

iterator end()

Definition:GenericDomTree.h:77

llvm::DomTreeNodeBase::getNumChildren

size_t getNumChildren() const

Definition:GenericDomTree.h:96

llvm::DomTreeNodeBase::DomTreeNodeBase

DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)

Definition:GenericDomTree.h:69

llvm::DomTreeNodeBase::compare

bool compare(const DomTreeNodeBase *Other) const

Definition:GenericDomTree.h:100

llvm::DomTreeNodeBase::getBlock

NodeT * getBlock() const

Definition:GenericDomTree.h:89

llvm::DomTreeNodeBase::getLevel

unsigned getLevel() const

Definition:GenericDomTree.h:91

llvm::DomTreeNodeBase::children

iterator_range< const_iterator > children() const

Definition:GenericDomTree.h:85

llvm::DomTreeNodeBase::getDFSNumOut

unsigned getDFSNumOut() const

Definition:GenericDomTree.h:141

llvm::DomTreeNodeBase::const_iterator

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

Definition:GenericDomTree.h:74

llvm::DomTreeNodeBase::begin

const_iterator begin() const

Definition:GenericDomTree.h:78

llvm::DomTreeNodeBase::addChild

void addChild(DomTreeNodeBase *C)

Definition:GenericDomTree.h:93

llvm::DominatorTreeBase

Core dominator tree base class.

Definition:GenericDomTree.h:237

llvm::DominatorTreeBase::isReachableFromEntry

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

Definition:GenericDomTree.h:462

llvm::DominatorTreeBase::print

void print(raw_ostream &O) const

print - Convert to human readable form

Definition:GenericDomTree.h:782

llvm::DominatorTreeBase::NodeType

typename NodeTrait::NodeType NodeType

Definition:GenericDomTree.h:242

llvm::DominatorTreeBase::operator[]

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

See getNode.

Definition:GenericDomTree.h:410

llvm::DominatorTreeBase::root_iterator

typename SmallVectorImpl< NodeT * >::iterator root_iterator

Iteration over roots.

Definition:GenericDomTree.h:312

llvm::DominatorTreeBase::getRootNode

DomTreeNodeBase< NodeT > * getRootNode()

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

Definition:GenericDomTree.h:421

llvm::DominatorTreeBase::verify

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

verify - checks if the tree is correct.

Definition:GenericDomTree.h:905

llvm::DominatorTreeBase::changeImmediateDominator

void changeImmediateDominator(NodeT *BB, NodeT *NewBB)

Definition:GenericDomTree.h:730

llvm::DominatorTreeBase::findNearestCommonDominator

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

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

Definition:GenericDomTree.h:519

llvm::DominatorTreeBase::DominatorTreeBase

DominatorTreeBase()=default

llvm::DominatorTreeBase::Split

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

Definition:GenericDomTree.h:937

llvm::DominatorTreeBase::roots

iterator_range< root_iterator > roots()

Definition:GenericDomTree.h:322

llvm::DominatorTreeBase::changeImmediateDominator

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

llvm::DominatorTreeBase::ParentType

std::remove_pointer_t< ParentPtr > ParentType

Definition:GenericDomTree.h:247

llvm::DominatorTreeBase::reset

void reset()

Definition:GenericDomTree.h:909

llvm::DominatorTreeBase::DominatorTreeBase

DominatorTreeBase(DominatorTreeBase &&Arg)

Definition:GenericDomTree.h:281

llvm::DominatorTreeBase::findNearestCommonDominator

NodeT * findNearestCommonDominator(iterator_range< IteratorTy > Nodes) const

Definition:GenericDomTree.h:562

llvm::DominatorTreeBase::isPostDominator

bool isPostDominator() const

isPostDominator - Returns true if analysis based of postdoms

Definition:GenericDomTree.h:331

llvm::DominatorTreeBase::root_size

size_t root_size() const

Definition:GenericDomTree.h:320

llvm::DominatorTreeBase::findNearestCommonDominator

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

Definition:GenericDomTree.h:549

llvm::DominatorTreeBase::getDescendants

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

Get all nodes dominated by R, including R itself.

Definition:GenericDomTree.h:425

llvm::DominatorTreeBase::addNewBlock

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

Add a new node to the dominator tree information.

Definition:GenericDomTree.h:687

llvm::DominatorTreeBase::createNode

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

Definition:GenericDomTree.h:923

llvm::DominatorTreeBase::applyUpdates

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

llvm::DominatorTreeBase::SlowQueries

unsigned int SlowQueries

Definition:GenericDomTree.h:273

llvm::DominatorTreeBase::DFSInfoValid

bool DFSInfoValid

Definition:GenericDomTree.h:272

llvm::DominatorTreeBase::insertEdge

void insertEdge(NodeT *From, NodeT *To)

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

Definition:GenericDomTree.h:652

llvm::DominatorTreeBase::updateBlockNumbers

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

Update dominator tree after renumbering blocks.

Definition:GenericDomTree.h:873

llvm::DominatorTreeBase::dominates

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

dominates - Returns true iff A dominates B.

Definition:GenericDomTree.h:467

llvm::DominatorTreeBase::roots

iterator_range< const_root_iterator > roots() const

Definition:GenericDomTree.h:325

llvm::DominatorTreeBase::root_end

const_root_iterator root_end() const

Definition:GenericDomTree.h:318

llvm::DominatorTreeBase::splitBlock

void splitBlock(NodeT *NewBB)

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

Definition:GenericDomTree.h:773

llvm::DominatorTreeBase::operator=

DominatorTreeBase & operator=(DominatorTreeBase &&RHS)

Definition:GenericDomTree.h:289

llvm::DominatorTreeBase::Delete

static constexpr UpdateKind Delete

Definition:GenericDomTree.h:253

llvm::DominatorTreeBase::recalculate

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

Definition:GenericDomTree.h:865

llvm::DominatorTreeBase::getRoot

NodeT * getRoot() const

Definition:GenericDomTree.h:512

llvm::DominatorTreeBase::updateDFSNumbers

void updateDFSNumbers() const

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

Definition:GenericDomTree.h:805

llvm::DominatorTreeBase::const_root_iterator

typename SmallVectorImpl< NodeT * >::const_iterator const_root_iterator

Definition:GenericDomTree.h:313

llvm::DominatorTreeBase::compare

bool compare(const DominatorTreeBase &Other) const

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

Definition:GenericDomTree.h:335

llvm::DominatorTreeBase::setNewRoot

DomTreeNodeBase< NodeT > * setNewRoot(NodeT *BB)

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

Definition:GenericDomTree.h:700

llvm::DominatorTreeBase::root_begin

root_iterator root_begin()

Definition:GenericDomTree.h:315

llvm::DominatorTreeBase::DominatorTreeBase

DominatorTreeBase(const DominatorTreeBase &)=delete

llvm::DominatorTreeBase::Insert

static constexpr UpdateKind Insert

Definition:GenericDomTree.h:252

llvm::DominatorTreeBase::root_begin

const_root_iterator root_begin() const

Definition:GenericDomTree.h:316

llvm::DominatorTreeBase::recalculate

void recalculate(ParentType &Func)

recalculate - compute a dominator tree for the given function

Definition:GenericDomTree.h:859

llvm::DominatorTreeBase::Roots

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

Definition:GenericDomTree.h:259

llvm::DominatorTreeBase::eraseNode

void eraseNode(NodeT *BB)

eraseNode - Removes a node from the dominator tree.

Definition:GenericDomTree.h:737

llvm::DominatorTreeBase::VerificationLevel

VerificationLevel

Definition:GenericDomTree.h:255

llvm::DominatorTreeBase::VerificationLevel::Basic

@ Basic

llvm::DominatorTreeBase::VerificationLevel::Full

@ Full

llvm::DominatorTreeBase::VerificationLevel::Fast

@ Fast

llvm::DominatorTreeBase::deleteEdge

void deleteEdge(NodeT *From, NodeT *To)

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

Definition:GenericDomTree.h:670

llvm::DominatorTreeBase::getRootNode

const DomTreeNodeBase< NodeT > * getRootNode() const

Definition:GenericDomTree.h:422

llvm::DominatorTreeBase::NodeNumberMap

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

Definition:GenericDomTree.h:268

llvm::DominatorTreeBase::RootNode

DomTreeNodeBase< NodeT > * RootNode

Definition:GenericDomTree.h:269

llvm::DominatorTreeBase::addRoot

void addRoot(NodeT *BB)

Definition:GenericDomTree.h:921

llvm::DominatorTreeBase::NodePtr

typename NodeTrait::NodePtr NodePtr

Definition:GenericDomTree.h:243

llvm::DominatorTreeBase::isReachableFromEntry

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

llvm::DominatorTreeBase::root_end

root_iterator root_end()

Definition:GenericDomTree.h:317

llvm::DominatorTreeBase::applyUpdates

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

Definition:GenericDomTree.h:623

llvm::DominatorTreeBase::BlockNumberEpoch

unsigned BlockNumberEpoch

Definition:GenericDomTree.h:274

llvm::DominatorTreeBase::DomTreeNodes

DomTreeNodeStorageTy DomTreeNodes

Definition:GenericDomTree.h:263

llvm::DominatorTreeBase::getNode

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

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

Definition:GenericDomTree.h:401

llvm::DominatorTreeBase::properlyDominates

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

Definition:GenericDomTree.h:1036

llvm::DominatorTreeBase::properlyDominates

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

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

Definition:GenericDomTree.h:443

llvm::DominatorTreeBase::isVirtualRoot

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

Definition:GenericDomTree.h:557

llvm::DominatorTreeBase::ParentPtr

typename NodeTrait::ParentPtr ParentPtr

Definition:GenericDomTree.h:244

llvm::DominatorTreeBase::operator=

DominatorTreeBase & operator=(const DominatorTreeBase &)=delete

llvm::DominatorTreeBase::IsPostDominator

static constexpr bool IsPostDominator

Definition:GenericDomTree.h:248

llvm::DominatorTreeBase::Parent

ParentPtr Parent

Definition:GenericDomTree.h:270

llvm::GraphDiff

Definition:CFGDiff.h:57

llvm::PostDominatorTree

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

Definition:PostDominators.h:28

llvm::SmallPtrSetImpl::count

size_type count(ConstPtrType Ptr) const

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

Definition:SmallPtrSet.h:452

llvm::SmallPtrSetImpl::insert

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

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

Definition:SmallPtrSet.h:384

llvm::SmallPtrSet

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

Definition:SmallPtrSet.h:519

llvm::SmallVectorBase::empty

bool empty() const

Definition:SmallVector.h:81

llvm::SmallVectorBase::size

size_t size() const

Definition:SmallVector.h:78

llvm::SmallVectorImpl

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

Definition:SmallVector.h:573

llvm::SmallVectorImpl::pop_back_val

T pop_back_val()

Definition:SmallVector.h:673

llvm::SmallVectorImpl::const_iterator

typename SuperClass::const_iterator const_iterator

Definition:SmallVector.h:578

llvm::SmallVectorImpl::append

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

Definition:SmallVector.h:683

llvm::SmallVectorImpl::clear

void clear()

Definition:SmallVector.h:610

llvm::SmallVectorImpl::iterator

typename SuperClass::iterator iterator

Definition:SmallVector.h:577

llvm::SmallVectorImpl::resize

void resize(size_type N)

Definition:SmallVector.h:638

llvm::SmallVectorTemplateBase::pop_back

void pop_back()

Definition:SmallVector.h:425

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition:SmallVector.h:413

llvm::SmallVectorTemplateCommon::end

iterator end()

Definition:SmallVector.h:269

llvm::SmallVectorTemplateCommon::front

reference front()

Definition:SmallVector.h:299

llvm::SmallVectorTemplateCommon::begin

iterator begin()

Definition:SmallVector.h:267

llvm::SmallVectorTemplateCommon::back

reference back()

Definition:SmallVector.h:308

llvm::SmallVector

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

Definition:SmallVector.h:1196

llvm::cfg::Update

Definition:CFGUpdate.h:28

llvm::iterator_range

A range adaptor for a pair of iterators.

Definition:iterator_range.h:42

llvm::iterator_range::empty

bool empty() const

Definition:iterator_range.h:66

llvm::iterator_range::begin

IteratorT begin() const

Definition:iterator_range.h:64

llvm::raw_ostream

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

Definition:raw_ostream.h:52

false

Definition:StackSlotColoring.cpp:193

llvm::CallingConv::C

@ C

The default llvm calling convention, compatible with C.

Definition:CallingConv.h:34

llvm::DomTreeBuilder::Verify

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

Definition:GenericDomTreeConstruction.h:1591

llvm::DomTreeBuilder::CalculateWithUpdates

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

Definition:GenericDomTreeConstruction.h:1557

llvm::DomTreeBuilder::DeleteEdge

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

Definition:GenericDomTreeConstruction.h:1575

llvm::DomTreeBuilder::Calculate

void Calculate(DomTreeT &DT)

Definition:GenericDomTreeConstruction.h:1552

llvm::DomTreeBuilder::ApplyUpdates

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

Definition:GenericDomTreeConstruction.h:1582

llvm::DomTreeBuilder::InsertEdge

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

Definition:GenericDomTreeConstruction.h:1568

llvm::cfg::UpdateKind

UpdateKind

Definition:CFGUpdate.h:26

llvm::pdb::DbgHeaderType::Max

@ Max

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18