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