LLVM 20.0.0git
DomTreeUpdater.h
Go to the documentation of this file.
1//===- DomTreeUpdater.h - DomTree/Post DomTree Updater ----------*- 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//
9// This file defines the DomTreeUpdater class, which provides a uniform way to
10// update dominator tree related data structures.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ANALYSIS_DOMTREEUPDATER_H
15#define LLVM_ANALYSIS_DOMTREEUPDATER_H
16
18#include "llvm/IR/Dominators.h"
19#include "llvm/IR/ValueHandle.h"
21#include <functional>
22#include <vector>
23
24namespace llvm {
25
26class PostDominatorTree;
27
29 : public GenericDomTreeUpdater<DomTreeUpdater, DominatorTree,
30 PostDominatorTree> {
33
34public:
35 using Base =
37 using Base::Base;
38
40
41 ///@{
42 /// \name Mutation APIs
43 ///
44 /// These methods provide APIs for submitting updates to the DominatorTree and
45 /// the PostDominatorTree.
46 ///
47 /// Note: There are two strategies to update the DominatorTree and the
48 /// PostDominatorTree:
49 /// 1. Eager UpdateStrategy: Updates are submitted and then flushed
50 /// immediately.
51 /// 2. Lazy UpdateStrategy: Updates are submitted but only flushed when you
52 /// explicitly call Flush APIs. It is recommended to use this update strategy
53 /// when you submit a bunch of updates multiple times which can then
54 /// add up to a large number of updates between two queries on the
55 /// DominatorTree. The incremental updater can reschedule the updates or
56 /// decide to recalculate the dominator tree in order to speedup the updating
57 /// process depending on the number of updates.
58 ///
59 /// Although GenericDomTree provides several update primitives,
60 /// it is not encouraged to use these APIs directly.
61
62 /// Delete DelBB. DelBB will be removed from its Parent and
63 /// erased from available trees if it exists and finally get deleted.
64 /// Under Eager UpdateStrategy, DelBB will be processed immediately.
65 /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
66 /// all available trees are up-to-date. Assert if any instruction of DelBB is
67 /// modified while awaiting deletion. When both DT and PDT are nullptrs, DelBB
68 /// will be queued until flush() is called.
69 void deleteBB(BasicBlock *DelBB);
70
71 /// Delete DelBB. DelBB will be removed from its Parent and
72 /// erased from available trees if it exists. Then the callback will
73 /// be called. Finally, DelBB will be deleted.
74 /// Under Eager UpdateStrategy, DelBB will be processed immediately.
75 /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
76 /// all available trees are up-to-date. Assert if any instruction of DelBB is
77 /// modified while awaiting deletion. Multiple callbacks can be queued for one
78 /// DelBB under Lazy UpdateStrategy.
79 void callbackDeleteBB(BasicBlock *DelBB,
80 std::function<void(BasicBlock *)> Callback);
81
82 ///@}
83
84private:
85 class CallBackOnDeletion final : public CallbackVH {
86 public:
87 CallBackOnDeletion(BasicBlock *V,
88 std::function<void(BasicBlock *)> Callback)
89 : CallbackVH(V), DelBB(V), Callback_(Callback) {}
90
91 private:
92 BasicBlock *DelBB = nullptr;
93 std::function<void(BasicBlock *)> Callback_;
94
95 void deleted() override {
96 Callback_(DelBB);
98 }
99 };
100
101 std::vector<CallBackOnDeletion> Callbacks;
102
103 /// First remove all the instructions of DelBB and then make sure DelBB has a
104 /// valid terminator instruction which is necessary to have when DelBB still
105 /// has to be inside of its parent Function while awaiting deletion under Lazy
106 /// UpdateStrategy to prevent other routines from asserting the state of the
107 /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors.
108 void validateDeleteBB(BasicBlock *DelBB);
109
110 /// Returns true if at least one BasicBlock is deleted.
111 bool forceFlushDeletedBB();
112
113 /// Debug method to help view the internal state of this class.
114 LLVM_DUMP_METHOD void dump() const;
115};
116
117extern template class GenericDomTreeUpdater<DomTreeUpdater, DominatorTree,
118 PostDominatorTree>;
119
120extern template void
121GenericDomTreeUpdater<DomTreeUpdater, DominatorTree,
122 PostDominatorTree>::recalculate(Function &F);
123} // namespace llvm
124
125#endif // LLVM_ANALYSIS_DOMTREEUPDATER_H
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:533
#define F(x, y, z)
Definition: MD5.cpp:55
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:383
virtual void deleted()
Callback for Value destruction.
Definition: ValueHandle.h:414
void callbackDeleteBB(BasicBlock *DelBB, std::function< void(BasicBlock *)> Callback)
Delete DelBB.
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18