LLVM  15.0.0git
DomTreeUpdater.cpp
Go to the documentation of this file.
1 //===- DomTreeUpdater.cpp - 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 implements the DomTreeUpdater class, which provides a uniform way
10 // to update dominator tree related data structures.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/SmallSet.h"
17 #include "llvm/IR/Constants.h"
18 #include "llvm/IR/Instructions.h"
20 #include <algorithm>
21 #include <functional>
22 #include <utility>
23 
24 namespace llvm {
25 
26 bool DomTreeUpdater::isUpdateValid(
27  const DominatorTree::UpdateType Update) const {
28  const auto *From = Update.getFrom();
29  const auto *To = Update.getTo();
30  const auto Kind = Update.getKind();
31 
32  // Discard updates by inspecting the current state of successors of From.
33  // Since isUpdateValid() must be called *after* the Terminator of From is
34  // altered we can determine if the update is unnecessary for batch updates
35  // or invalid for a single update.
36  const bool HasEdge = llvm::is_contained(successors(From), To);
37 
38  // If the IR does not match the update,
39  // 1. In batch updates, this update is unnecessary.
40  // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid.
41  // Edge does not exist in IR.
42  if (Kind == DominatorTree::Insert && !HasEdge)
43  return false;
44 
45  // Edge exists in IR.
46  if (Kind == DominatorTree::Delete && HasEdge)
47  return false;
48 
49  return true;
50 }
51 
52 bool DomTreeUpdater::isSelfDominance(
53  const DominatorTree::UpdateType Update) const {
54  // Won't affect DomTree and PostDomTree.
55  return Update.getFrom() == Update.getTo();
56 }
57 
58 void DomTreeUpdater::applyDomTreeUpdates() {
59  // No pending DomTreeUpdates.
60  if (Strategy != UpdateStrategy::Lazy || !DT)
61  return;
62 
63  // Only apply updates not are applied by DomTree.
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.");
68  DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
69  PendDTUpdateIndex = PendUpdates.size();
70  }
71 }
72 
74  applyDomTreeUpdates();
75  applyPostDomTreeUpdates();
76  dropOutOfDateUpdates();
77 }
78 
79 void DomTreeUpdater::applyPostDomTreeUpdates() {
80  // No pending PostDomTreeUpdates.
81  if (Strategy != UpdateStrategy::Lazy || !PDT)
82  return;
83 
84  // Only apply updates not are applied by PostDomTree.
86  const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
87  const auto E = PendUpdates.end();
88  assert(I < E &&
89  "Iterator range invalid; there should be PostDomTree updates.");
91  PendPDTUpdateIndex = PendUpdates.size();
92  }
93 }
94 
95 void DomTreeUpdater::tryFlushDeletedBB() {
96  if (!hasPendingUpdates())
97  forceFlushDeletedBB();
98 }
99 
100 bool DomTreeUpdater::forceFlushDeletedBB() {
101  if (DeletedBBs.empty())
102  return false;
103 
104  for (auto *BB : DeletedBBs) {
105  // After calling deleteBB or callbackDeleteBB under Lazy UpdateStrategy,
106  // validateDeleteBB() removes all instructions of DelBB and adds an
107  // UnreachableInst as its terminator. So we check whether the BasicBlock to
108  // delete only has an UnreachableInst inside.
109  assert(BB->getInstList().size() == 1 &&
110  isa<UnreachableInst>(BB->getTerminator()) &&
111  "DelBB has been modified while awaiting deletion.");
112  BB->removeFromParent();
113  eraseDelBBNode(BB);
114  delete BB;
115  }
116  DeletedBBs.clear();
117  Callbacks.clear();
118  return true;
119 }
120 
122 
123  if (Strategy == UpdateStrategy::Eager) {
124  if (DT)
125  DT->recalculate(F);
126  if (PDT)
127  PDT->recalculate(F);
128  return;
129  }
130 
131  // There is little performance gain if we pend the recalculation under
132  // Lazy UpdateStrategy so we recalculate available trees immediately.
133 
134  // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
135  IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
136 
137  // Because all trees are going to be up-to-date after recalculation,
138  // flush awaiting deleted BasicBlocks.
139  forceFlushDeletedBB();
140  if (DT)
141  DT->recalculate(F);
142  if (PDT)
143  PDT->recalculate(F);
144 
145  // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
146  IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
147  PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
148  dropOutOfDateUpdates();
149 }
150 
153 }
154 
156  if (!DT)
157  return false;
158  return PendUpdates.size() != PendDTUpdateIndex;
159 }
160 
162  if (!PDT)
163  return false;
164  return PendUpdates.size() != PendPDTUpdateIndex;
165 }
166 
168  if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
169  return false;
170  return DeletedBBs.contains(DelBB);
171 }
172 
173 // The DT and PDT require the nodes related to updates
174 // are not deleted when update functions are called.
175 // So BasicBlock deletions must be pended when the
176 // UpdateStrategy is Lazy. When the UpdateStrategy is
177 // Eager, the BasicBlock will be deleted immediately.
179  validateDeleteBB(DelBB);
180  if (Strategy == UpdateStrategy::Lazy) {
181  DeletedBBs.insert(DelBB);
182  return;
183  }
184 
185  DelBB->removeFromParent();
186  eraseDelBBNode(DelBB);
187  delete DelBB;
188 }
189 
191  BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
192  validateDeleteBB(DelBB);
193  if (Strategy == UpdateStrategy::Lazy) {
194  Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
195  DeletedBBs.insert(DelBB);
196  return;
197  }
198 
199  DelBB->removeFromParent();
200  eraseDelBBNode(DelBB);
201  Callback(DelBB);
202  delete DelBB;
203 }
204 
205 void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) {
206  if (DT && !IsRecalculatingDomTree)
207  if (DT->getNode(DelBB))
208  DT->eraseNode(DelBB);
209 
210  if (PDT && !IsRecalculatingPostDomTree)
211  if (PDT->getNode(DelBB))
212  PDT->eraseNode(DelBB);
213 }
214 
215 void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
216  assert(DelBB && "Invalid push_back of nullptr DelBB.");
217  assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
218  // DelBB is unreachable and all its instructions are dead.
219  while (!DelBB->empty()) {
220  Instruction &I = DelBB->back();
221  // Replace used instructions with an arbitrary value (undef).
222  if (!I.use_empty())
223  I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
224  DelBB->getInstList().pop_back();
225  }
226  // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
227  // Child of Function F it must contain valid IR.
228  new UnreachableInst(DelBB->getContext(), DelBB);
229 }
230 
232  if (!DT && !PDT)
233  return;
234 
235  if (Strategy == UpdateStrategy::Lazy) {
236  PendUpdates.reserve(PendUpdates.size() + Updates.size());
237  for (const auto &U : Updates)
238  if (!isSelfDominance(U))
239  PendUpdates.push_back(U);
240 
241  return;
242  }
243 
244  if (DT)
245  DT->applyUpdates(Updates);
246  if (PDT)
247  PDT->applyUpdates(Updates);
248 }
249 
252  if (!DT && !PDT)
253  return;
254 
256  SmallVector<DominatorTree::UpdateType, 8> DeduplicatedUpdates;
257  for (const auto &U : Updates) {
258  auto Edge = std::make_pair(U.getFrom(), U.getTo());
259  // Because it is illegal to submit updates that have already been applied
260  // and updates to an edge need to be strictly ordered,
261  // it is safe to infer the existence of an edge from the first update
262  // to this edge.
263  // If the first update to an edge is "Delete", it means that the edge
264  // existed before. If the first update to an edge is "Insert", it means
265  // that the edge didn't exist before.
266  //
267  // For example, if the user submits {{Delete, A, B}, {Insert, A, B}},
268  // because
269  // 1. it is illegal to submit updates that have already been applied,
270  // i.e., user cannot delete an nonexistent edge,
271  // 2. updates to an edge need to be strictly ordered,
272  // So, initially edge A -> B existed.
273  // We can then safely ignore future updates to this edge and directly
274  // inspect the current CFG:
275  // a. If the edge still exists, because the user cannot insert an existent
276  // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and
277  // resulted in a no-op. DTU won't submit any update in this case.
278  // b. If the edge doesn't exist, we can then infer that {Delete, A, B}
279  // actually happened but {Insert, A, B} was an invalid update which never
280  // happened. DTU will submit {Delete, A, B} in this case.
281  if (!isSelfDominance(U) && Seen.count(Edge) == 0) {
282  Seen.insert(Edge);
283  // If the update doesn't appear in the CFG, it means that
284  // either the change isn't made or relevant operations
285  // result in a no-op.
286  if (isUpdateValid(U)) {
287  if (isLazy())
288  PendUpdates.push_back(U);
289  else
290  DeduplicatedUpdates.push_back(U);
291  }
292  }
293  }
294 
295  if (Strategy == UpdateStrategy::Lazy)
296  return;
297 
298  if (DT)
299  DT->applyUpdates(DeduplicatedUpdates);
300  if (PDT)
301  PDT->applyUpdates(DeduplicatedUpdates);
302 }
303 
305  assert(DT && "Invalid acquisition of a null DomTree");
306  applyDomTreeUpdates();
307  dropOutOfDateUpdates();
308  return *DT;
309 }
310 
312  assert(PDT && "Invalid acquisition of a null PostDomTree");
313  applyPostDomTreeUpdates();
314  dropOutOfDateUpdates();
315  return *PDT;
316 }
317 
318 void DomTreeUpdater::dropOutOfDateUpdates() {
320  return;
321 
322  tryFlushDeletedBB();
323 
324  // Drop all updates applied by both trees.
325  if (!DT)
326  PendDTUpdateIndex = PendUpdates.size();
327  if (!PDT)
328  PendPDTUpdateIndex = PendUpdates.size();
329 
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.");
334  PendUpdates.erase(B, E);
335  // Calculate current index.
336  PendDTUpdateIndex -= dropIndex;
337  PendPDTUpdateIndex -= dropIndex;
338 }
339 
340 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
342  raw_ostream &OS = llvm::dbgs();
343 
344  OS << "Available Trees: ";
345  if (DT || PDT) {
346  if (DT)
347  OS << "DomTree ";
348  if (PDT)
349  OS << "PostDomTree ";
350  OS << "\n";
351  } else
352  OS << "None\n";
353 
354  OS << "UpdateStrategy: ";
355  if (Strategy == UpdateStrategy::Eager) {
356  OS << "Eager\n";
357  return;
358  } else
359  OS << "Lazy\n";
360  int Index = 0;
361 
362  auto printUpdates =
365  if (begin == end)
366  OS << " None\n";
367  Index = 0;
368  for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
369  auto U = *It;
370  OS << " " << Index << " : ";
371  ++Index;
372  if (U.getKind() == DominatorTree::Insert)
373  OS << "Insert, ";
374  else
375  OS << "Delete, ";
376  BasicBlock *From = U.getFrom();
377  if (From) {
378  auto S = From->getName();
379  if (!From->hasName())
380  S = "(no name)";
381  OS << S << "(" << From << "), ";
382  } else {
383  OS << "(badref), ";
384  }
385  BasicBlock *To = U.getTo();
386  if (To) {
387  auto S = To->getName();
388  if (!To->hasName())
389  S = "(no_name)";
390  OS << S << "(" << To << ")\n";
391  } else {
392  OS << "(badref)\n";
393  }
394  }
395  };
396 
397  if (DT) {
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());
405  }
406 
407  if (PDT) {
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());
415  }
416 
417  OS << "Pending DeletedBBs:\n";
418  Index = 0;
419  for (const auto *BB : DeletedBBs) {
420  OS << " " << Index << " : ";
421  ++Index;
422  if (BB->hasName())
423  OS << BB->getName() << "(";
424  else
425  OS << "(no_name)(";
426  OS << BB << ")\n";
427  }
428 
429  OS << "Pending Callbacks:\n";
430  Index = 0;
431  for (const auto &BB : Callbacks) {
432  OS << " " << Index << " : ";
433  ++Index;
434  if (BB->hasName())
435  OS << BB->getName() << "(";
436  else
437  OS << "(no_name)(";
438  OS << BB << ")\n";
439  }
440 }
441 #endif
442 } // namespace llvm
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:494
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:724
llvm::DomTreeUpdater::deleteBB
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Definition: DomTreeUpdater.cpp:178
llvm::DominatorTreeBase::eraseNode
void eraseNode(NodeT *BB)
eraseNode - Removes a node from the dominator tree.
Definition: GenericDomTree.h:669
llvm::DomTreeUpdater::applyUpdates
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:231
llvm::Function
Definition: Function.h:60
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::Value::hasName
bool hasName() const
Definition: Value.h:261
DomTreeUpdater.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::DomTreeUpdater::hasPendingUpdates
bool hasPendingUpdates() const
Returns true if either of DT or PDT is valid and the tree has at least one update pending.
Definition: DomTreeUpdater.cpp:151
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::DominatorTreeBase< BasicBlock, false >::Insert
static constexpr UpdateKind Insert
Definition: GenericDomTree.h:242
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::ArrayRef::const_iterator
const_pointer const_iterator
Definition: ArrayRef.h:50
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:544
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::DomTreeUpdater::UpdateStrategy::Lazy
@ Lazy
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DomTreeUpdater::hasPendingPostDomTreeUpdates
bool hasPendingPostDomTreeUpdates() const
Returns true if there are PostDominatorTree updates queued.
Definition: DomTreeUpdater.cpp:161
llvm::DomTreeUpdater::callbackDeleteBB
void callbackDeleteBB(BasicBlock *DelBB, std::function< void(BasicBlock *)> Callback)
Delete DelBB.
Definition: DomTreeUpdater.cpp:190
Constants.h
llvm::DomTreeUpdater::isBBPendingDeletion
bool isBBPendingDeletion(BasicBlock *DelBB) const
Returns true if DelBB is awaiting deletion.
Definition: DomTreeUpdater.cpp:167
PostDominators.h
llvm::DomTreeUpdater::dump
LLVM_DUMP_METHOD void dump() const
Debug method to help view the internal state of this class.
Definition: DomTreeUpdater.cpp:341
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::DominatorTreeBase< BasicBlock, false >::UpdateType
cfg::Update< NodePtr > UpdateType
Definition: GenericDomTree.h:240
llvm::DomTreeUpdater::hasPendingDomTreeUpdates
bool hasPendingDomTreeUpdates() const
Returns true if there are DominatorTree updates queued.
Definition: DomTreeUpdater.cpp:155
llvm::DomTreeUpdater::recalculate
void recalculate(Function &F)
Notify DTU that the entry block was replaced.
Definition: DomTreeUpdater.cpp:121
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1769
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::SmallSet::count
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:166
llvm::BasicBlock::removeFromParent
void removeFromParent()
Unlink 'this' from the containing function, but do not delete it.
Definition: BasicBlock.cpp:128
llvm::DomTreeUpdater::getDomTree
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
Definition: DomTreeUpdater.cpp:304
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1672
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
llvm::DominatorTreeBase::recalculate
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
Definition: GenericDomTree.h:778
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
S
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
Definition: README.txt:210
llvm::DomTreeUpdater::UpdateStrategy::Eager
@ Eager
llvm::pred_empty
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:118
llvm::SmallSet::insert
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:182
llvm::DomTreeUpdater::flush
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
Definition: DomTreeUpdater.cpp:73
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:305
llvm::DomTreeUpdater::isLazy
bool isLazy() const
Returns true if the current strategy is Lazy.
Definition: DomTreeUpdater.h:51
GenericDomTree.h
llvm::DomTreeUpdater::getPostDomTree
PostDominatorTree & getPostDomTree()
Flush PostDomTree updates and return PostDomTree.
Definition: DomTreeUpdater.cpp:311
Instructions.h
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
BB
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
Definition: README.txt:39
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:644
llvm::DomTreeUpdater::applyUpdatesPermissive
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:250
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
SmallSet.h