LLVM  16.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->size() == 1 && isa<UnreachableInst>(BB->getTerminator()) &&
110  "DelBB has been modified while awaiting deletion.");
111  BB->removeFromParent();
112  eraseDelBBNode(BB);
113  delete BB;
114  }
115  DeletedBBs.clear();
116  Callbacks.clear();
117  return true;
118 }
119 
121 
122  if (Strategy == UpdateStrategy::Eager) {
123  if (DT)
124  DT->recalculate(F);
125  if (PDT)
126  PDT->recalculate(F);
127  return;
128  }
129 
130  // There is little performance gain if we pend the recalculation under
131  // Lazy UpdateStrategy so we recalculate available trees immediately.
132 
133  // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
134  IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
135 
136  // Because all trees are going to be up-to-date after recalculation,
137  // flush awaiting deleted BasicBlocks.
138  forceFlushDeletedBB();
139  if (DT)
140  DT->recalculate(F);
141  if (PDT)
142  PDT->recalculate(F);
143 
144  // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
145  IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
146  PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
147  dropOutOfDateUpdates();
148 }
149 
152 }
153 
155  if (!DT)
156  return false;
157  return PendUpdates.size() != PendDTUpdateIndex;
158 }
159 
161  if (!PDT)
162  return false;
163  return PendUpdates.size() != PendPDTUpdateIndex;
164 }
165 
167  if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
168  return false;
169  return DeletedBBs.contains(DelBB);
170 }
171 
172 // The DT and PDT require the nodes related to updates
173 // are not deleted when update functions are called.
174 // So BasicBlock deletions must be pended when the
175 // UpdateStrategy is Lazy. When the UpdateStrategy is
176 // Eager, the BasicBlock will be deleted immediately.
178  validateDeleteBB(DelBB);
179  if (Strategy == UpdateStrategy::Lazy) {
180  DeletedBBs.insert(DelBB);
181  return;
182  }
183 
184  DelBB->removeFromParent();
185  eraseDelBBNode(DelBB);
186  delete DelBB;
187 }
188 
190  BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
191  validateDeleteBB(DelBB);
192  if (Strategy == UpdateStrategy::Lazy) {
193  Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
194  DeletedBBs.insert(DelBB);
195  return;
196  }
197 
198  DelBB->removeFromParent();
199  eraseDelBBNode(DelBB);
200  Callback(DelBB);
201  delete DelBB;
202 }
203 
204 void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) {
205  if (DT && !IsRecalculatingDomTree)
206  if (DT->getNode(DelBB))
207  DT->eraseNode(DelBB);
208 
209  if (PDT && !IsRecalculatingPostDomTree)
210  if (PDT->getNode(DelBB))
211  PDT->eraseNode(DelBB);
212 }
213 
214 void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
215  assert(DelBB && "Invalid push_back of nullptr DelBB.");
216  assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
217  // DelBB is unreachable and all its instructions are dead.
218  while (!DelBB->empty()) {
219  Instruction &I = DelBB->back();
220  // Replace used instructions with an arbitrary value (poison).
221  if (!I.use_empty())
222  I.replaceAllUsesWith(PoisonValue::get(I.getType()));
223  DelBB->back().eraseFromParent();
224  }
225  // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
226  // Child of Function F it must contain valid IR.
227  new UnreachableInst(DelBB->getContext(), DelBB);
228 }
229 
231  if (!DT && !PDT)
232  return;
233 
234  if (Strategy == UpdateStrategy::Lazy) {
235  PendUpdates.reserve(PendUpdates.size() + Updates.size());
236  for (const auto &U : Updates)
237  if (!isSelfDominance(U))
238  PendUpdates.push_back(U);
239 
240  return;
241  }
242 
243  if (DT)
244  DT->applyUpdates(Updates);
245  if (PDT)
246  PDT->applyUpdates(Updates);
247 }
248 
251  if (!DT && !PDT)
252  return;
253 
255  SmallVector<DominatorTree::UpdateType, 8> DeduplicatedUpdates;
256  for (const auto &U : Updates) {
257  auto Edge = std::make_pair(U.getFrom(), U.getTo());
258  // Because it is illegal to submit updates that have already been applied
259  // and updates to an edge need to be strictly ordered,
260  // it is safe to infer the existence of an edge from the first update
261  // to this edge.
262  // If the first update to an edge is "Delete", it means that the edge
263  // existed before. If the first update to an edge is "Insert", it means
264  // that the edge didn't exist before.
265  //
266  // For example, if the user submits {{Delete, A, B}, {Insert, A, B}},
267  // because
268  // 1. it is illegal to submit updates that have already been applied,
269  // i.e., user cannot delete an nonexistent edge,
270  // 2. updates to an edge need to be strictly ordered,
271  // So, initially edge A -> B existed.
272  // We can then safely ignore future updates to this edge and directly
273  // inspect the current CFG:
274  // a. If the edge still exists, because the user cannot insert an existent
275  // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and
276  // resulted in a no-op. DTU won't submit any update in this case.
277  // b. If the edge doesn't exist, we can then infer that {Delete, A, B}
278  // actually happened but {Insert, A, B} was an invalid update which never
279  // happened. DTU will submit {Delete, A, B} in this case.
280  if (!isSelfDominance(U) && Seen.count(Edge) == 0) {
281  Seen.insert(Edge);
282  // If the update doesn't appear in the CFG, it means that
283  // either the change isn't made or relevant operations
284  // result in a no-op.
285  if (isUpdateValid(U)) {
286  if (isLazy())
287  PendUpdates.push_back(U);
288  else
289  DeduplicatedUpdates.push_back(U);
290  }
291  }
292  }
293 
294  if (Strategy == UpdateStrategy::Lazy)
295  return;
296 
297  if (DT)
298  DT->applyUpdates(DeduplicatedUpdates);
299  if (PDT)
300  PDT->applyUpdates(DeduplicatedUpdates);
301 }
302 
304  assert(DT && "Invalid acquisition of a null DomTree");
305  applyDomTreeUpdates();
306  dropOutOfDateUpdates();
307  return *DT;
308 }
309 
311  assert(PDT && "Invalid acquisition of a null PostDomTree");
312  applyPostDomTreeUpdates();
313  dropOutOfDateUpdates();
314  return *PDT;
315 }
316 
317 void DomTreeUpdater::dropOutOfDateUpdates() {
319  return;
320 
321  tryFlushDeletedBB();
322 
323  // Drop all updates applied by both trees.
324  if (!DT)
325  PendDTUpdateIndex = PendUpdates.size();
326  if (!PDT)
327  PendPDTUpdateIndex = PendUpdates.size();
328 
329  const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
330  const auto B = PendUpdates.begin();
331  const auto E = PendUpdates.begin() + dropIndex;
332  assert(B <= E && "Iterator out of range.");
333  PendUpdates.erase(B, E);
334  // Calculate current index.
335  PendDTUpdateIndex -= dropIndex;
336  PendPDTUpdateIndex -= dropIndex;
337 }
338 
339 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
341  raw_ostream &OS = llvm::dbgs();
342 
343  OS << "Available Trees: ";
344  if (DT || PDT) {
345  if (DT)
346  OS << "DomTree ";
347  if (PDT)
348  OS << "PostDomTree ";
349  OS << "\n";
350  } else
351  OS << "None\n";
352 
353  OS << "UpdateStrategy: ";
354  if (Strategy == UpdateStrategy::Eager) {
355  OS << "Eager\n";
356  return;
357  } else
358  OS << "Lazy\n";
359  int Index = 0;
360 
361  auto printUpdates =
364  if (begin == end)
365  OS << " None\n";
366  Index = 0;
367  for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
368  auto U = *It;
369  OS << " " << Index << " : ";
370  ++Index;
371  if (U.getKind() == DominatorTree::Insert)
372  OS << "Insert, ";
373  else
374  OS << "Delete, ";
375  BasicBlock *From = U.getFrom();
376  if (From) {
377  auto S = From->getName();
378  if (!From->hasName())
379  S = "(no name)";
380  OS << S << "(" << From << "), ";
381  } else {
382  OS << "(badref), ";
383  }
384  BasicBlock *To = U.getTo();
385  if (To) {
386  auto S = To->getName();
387  if (!To->hasName())
388  S = "(no_name)";
389  OS << S << "(" << To << ")\n";
390  } else {
391  OS << "(badref)\n";
392  }
393  }
394  };
395 
396  if (DT) {
397  const auto I = PendUpdates.begin() + PendDTUpdateIndex;
398  assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
399  "Iterator out of range.");
400  OS << "Applied but not cleared DomTreeUpdates:\n";
401  printUpdates(PendUpdates.begin(), I);
402  OS << "Pending DomTreeUpdates:\n";
403  printUpdates(I, PendUpdates.end());
404  }
405 
406  if (PDT) {
407  const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
408  assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
409  "Iterator out of range.");
410  OS << "Applied but not cleared PostDomTreeUpdates:\n";
411  printUpdates(PendUpdates.begin(), I);
412  OS << "Pending PostDomTreeUpdates:\n";
413  printUpdates(I, PendUpdates.end());
414  }
415 
416  OS << "Pending DeletedBBs:\n";
417  Index = 0;
418  for (const auto *BB : DeletedBBs) {
419  OS << " " << Index << " : ";
420  ++Index;
421  if (BB->hasName())
422  OS << BB->getName() << "(";
423  else
424  OS << "(no_name)(";
425  OS << BB << ")\n";
426  }
427 
428  OS << "Pending Callbacks:\n";
429  Index = 0;
430  for (const auto &BB : Callbacks) {
431  OS << " " << Index << " : ";
432  ++Index;
433  if (BB->hasName())
434  OS << BB->getName() << "(";
435  else
436  OS << "(no_name)(";
437  OS << BB << ")\n";
438  }
439 }
440 #endif
441 } // 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:492
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:741
llvm::DomTreeUpdater::deleteBB
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Definition: DomTreeUpdater.cpp:177
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:230
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:1199
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:150
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:160
llvm::DomTreeUpdater::callbackDeleteBB
void callbackDeleteBB(BasicBlock *DelBB, std::function< void(BasicBlock *)> Callback)
Delete DelBB.
Definition: DomTreeUpdater.cpp:189
Constants.h
llvm::DomTreeUpdater::isBBPendingDeletion
bool isBBPendingDeletion(BasicBlock *DelBB) const
Returns true if DelBB is awaiting deletion.
Definition: DomTreeUpdater.cpp:166
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:340
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:154
llvm::DomTreeUpdater::recalculate
void recalculate(Function &F)
Notify DTU that the entry block was replaced.
Definition: DomTreeUpdater.cpp:120
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
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:53
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:165
Index
uint32_t Index
Definition: ELFObjHandler.cpp:83
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:303
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:1868
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::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:308
llvm::DomTreeUpdater::isLazy
bool isLazy() const
Returns true if the current strategy is Lazy.
Definition: DomTreeUpdater.h:51
GenericDomTree.h
llvm::SmallSet::insert
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:178
llvm::DomTreeUpdater::getPostDomTree
PostDominatorTree & getPostDomTree()
Flush PostDomTree updates and return PostDomTree.
Definition: DomTreeUpdater.cpp:310
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:667
llvm::DomTreeUpdater::applyUpdatesPermissive
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:249
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
SmallSet.h
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1732