Go to the documentation of this file.
26 bool DomTreeUpdater::isUpdateValid(
28 const auto *
From = Update.getFrom();
29 const auto *To = Update.getTo();
30 const auto Kind = Update.getKind();
52 bool DomTreeUpdater::isSelfDominance(
55 return Update.getFrom() == Update.getTo();
58 void DomTreeUpdater::applyDomTreeUpdates() {
65 const auto I = PendUpdates.begin() + PendDTUpdateIndex;
66 const auto E = PendUpdates.end();
67 assert(
I <
E &&
"Iterator range invalid; there should be DomTree updates.");
69 PendDTUpdateIndex = PendUpdates.size();
74 applyDomTreeUpdates();
75 applyPostDomTreeUpdates();
76 dropOutOfDateUpdates();
79 void DomTreeUpdater::applyPostDomTreeUpdates() {
86 const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
87 const auto E = PendUpdates.end();
89 "Iterator range invalid; there should be PostDomTree updates.");
91 PendPDTUpdateIndex = PendUpdates.size();
95 void DomTreeUpdater::tryFlushDeletedBB() {
97 forceFlushDeletedBB();
100 bool DomTreeUpdater::forceFlushDeletedBB() {
101 if (DeletedBBs.empty())
104 for (
auto *
BB : DeletedBBs) {
109 assert(
BB->getInstList().size() == 1 &&
110 isa<UnreachableInst>(
BB->getTerminator()) &&
111 "DelBB has been modified while awaiting deletion.");
112 BB->removeFromParent();
135 IsRecalculatingDomTree = IsRecalculatingPostDomTree =
true;
139 forceFlushDeletedBB();
146 IsRecalculatingDomTree = IsRecalculatingPostDomTree =
false;
147 PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
148 dropOutOfDateUpdates();
158 return PendUpdates.size() != PendDTUpdateIndex;
164 return PendUpdates.size() != PendPDTUpdateIndex;
170 return DeletedBBs.contains(DelBB);
179 validateDeleteBB(DelBB);
181 DeletedBBs.insert(DelBB);
186 eraseDelBBNode(DelBB);
192 validateDeleteBB(DelBB);
194 Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
195 DeletedBBs.insert(DelBB);
200 eraseDelBBNode(DelBB);
205 void DomTreeUpdater::eraseDelBBNode(
BasicBlock *DelBB) {
206 if (DT && !IsRecalculatingDomTree)
210 if (PDT && !IsRecalculatingPostDomTree)
215 void DomTreeUpdater::validateDeleteBB(
BasicBlock *DelBB) {
216 assert(DelBB &&
"Invalid push_back of nullptr DelBB.");
219 while (!DelBB->empty()) {
220 Instruction &
I = DelBB->back();
224 DelBB->getInstList().pop_back();
228 new UnreachableInst(DelBB->getContext(), DelBB);
236 PendUpdates.
reserve(PendUpdates.size() + Updates.
size());
237 for (
const auto &U : Updates)
238 if (!isSelfDominance(U))
239 PendUpdates.push_back(U);
257 for (
const auto &U : Updates) {
258 auto Edge = std::make_pair(U.getFrom(), U.getTo());
281 if (!isSelfDominance(U) && Seen.
count(Edge) == 0) {
286 if (isUpdateValid(U)) {
288 PendUpdates.push_back(U);
290 DeduplicatedUpdates.push_back(U);
305 assert(DT &&
"Invalid acquisition of a null DomTree");
306 applyDomTreeUpdates();
307 dropOutOfDateUpdates();
312 assert(PDT &&
"Invalid acquisition of a null PostDomTree");
313 applyPostDomTreeUpdates();
314 dropOutOfDateUpdates();
318 void DomTreeUpdater::dropOutOfDateUpdates() {
326 PendDTUpdateIndex = PendUpdates.size();
328 PendPDTUpdateIndex = PendUpdates.size();
330 const size_t dropIndex =
std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
331 const auto B = PendUpdates.begin();
332 const auto E = PendUpdates.begin() + dropIndex;
333 assert(
B <=
E &&
"Iterator out of range.");
336 PendDTUpdateIndex -= dropIndex;
337 PendPDTUpdateIndex -= dropIndex;
340 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
344 OS <<
"Available Trees: ";
349 OS <<
"PostDomTree ";
354 OS <<
"UpdateStrategy: ";
368 for (
auto It =
begin, ItEnd =
end; It != ItEnd; ++It) {
370 OS <<
" " << Index <<
" : ";
378 auto S =
From->getName();
379 if (!
From->hasName())
381 OS <<
S <<
"(" <<
From <<
"), ";
390 OS <<
S <<
"(" << To <<
")\n";
398 const auto I = PendUpdates.begin() + PendDTUpdateIndex;
399 assert(PendUpdates.begin() <=
I &&
I <= PendUpdates.end() &&
400 "Iterator out of range.");
401 OS <<
"Applied but not cleared DomTreeUpdates:\n";
402 printUpdates(PendUpdates.begin(),
I);
403 OS <<
"Pending DomTreeUpdates:\n";
404 printUpdates(
I, PendUpdates.end());
408 const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
409 assert(PendUpdates.begin() <=
I &&
I <= PendUpdates.end() &&
410 "Iterator out of range.");
411 OS <<
"Applied but not cleared PostDomTreeUpdates:\n";
412 printUpdates(PendUpdates.begin(),
I);
413 OS <<
"Pending PostDomTreeUpdates:\n";
414 printUpdates(
I, PendUpdates.end());
417 OS <<
"Pending DeletedBBs:\n";
419 for (
const auto *
BB : DeletedBBs) {
420 OS <<
" " << Index <<
" : ";
423 OS <<
BB->getName() <<
"(";
429 OS <<
"Pending Callbacks:\n";
431 for (
const auto &
BB : Callbacks) {
432 OS <<
" " << Index <<
" : ";
435 OS <<
BB->getName() <<
"(";
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This is an optimization pass for GlobalISel generic memory operations.
iterator erase(const_iterator CI)
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
void eraseNode(NodeT *BB)
eraseNode - Removes a node from the dominator tree.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool hasPendingUpdates() const
Returns true if either of DT or PDT is valid and the tree has at least one update pending.
const_iterator end(StringRef path)
Get end iterator over path.
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
static constexpr UpdateKind Insert
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
auto successors(MachineBasicBlock *BB)
const_pointer const_iterator
void applyUpdates(ArrayRef< UpdateType > Updates)
Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...
LLVM Basic Block Representation.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool hasPendingPostDomTreeUpdates() const
Returns true if there are PostDominatorTree updates queued.
void callbackDeleteBB(BasicBlock *DelBB, std::function< void(BasicBlock *)> Callback)
Delete DelBB.
bool isBBPendingDeletion(BasicBlock *DelBB) const
Returns true if DelBB is awaiting deletion.
LLVM_DUMP_METHOD void dump() const
Debug method to help view the internal state of this class.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
cfg::Update< NodePtr > UpdateType
bool hasPendingDomTreeUpdates() const
Returns true if there are DominatorTree updates queued.
void recalculate(Function &F)
Notify DTU that the entry block was replaced.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This class implements an extremely fast bulk output stream that can only output to a stream.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
void removeFromParent()
Unlink 'this' from the containing function, but do not delete it.
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
@ BasicBlock
Various leaf nodes.
print Print MemDeps of function
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
bool pred_empty(const BasicBlock *BB)
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
StringRef getName() const
Return a constant reference to the value's name.
bool isLazy() const
Returns true if the current strategy is Lazy.
PostDominatorTree & getPostDomTree()
Flush PostDomTree updates and return PostDomTree.
size_t size() const
size - Get the array size.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
BlockVerifier::State From
void reserve(size_type N)
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
static constexpr UpdateKind Delete