LLVM  13.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/Instructions.h"
19 #include <algorithm>
20 #include <functional>
21 #include <utility>
22 
23 namespace llvm {
24 
25 bool DomTreeUpdater::isUpdateValid(
26  const DominatorTree::UpdateType Update) const {
27  const auto *From = Update.getFrom();
28  const auto *To = Update.getTo();
29  const auto Kind = Update.getKind();
30 
31  // Discard updates by inspecting the current state of successors of From.
32  // Since isUpdateValid() must be called *after* the Terminator of From is
33  // altered we can determine if the update is unnecessary for batch updates
34  // or invalid for a single update.
35  const bool HasEdge = llvm::is_contained(successors(From), To);
36 
37  // If the IR does not match the update,
38  // 1. In batch updates, this update is unnecessary.
39  // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid.
40  // Edge does not exist in IR.
41  if (Kind == DominatorTree::Insert && !HasEdge)
42  return false;
43 
44  // Edge exists in IR.
45  if (Kind == DominatorTree::Delete && HasEdge)
46  return false;
47 
48  return true;
49 }
50 
51 bool DomTreeUpdater::isSelfDominance(
52  const DominatorTree::UpdateType Update) const {
53  // Won't affect DomTree and PostDomTree.
54  return Update.getFrom() == Update.getTo();
55 }
56 
57 void DomTreeUpdater::applyDomTreeUpdates() {
58  // No pending DomTreeUpdates.
59  if (Strategy != UpdateStrategy::Lazy || !DT)
60  return;
61 
62  // Only apply updates not are applied by DomTree.
64  const auto I = PendUpdates.begin() + PendDTUpdateIndex;
65  const auto E = PendUpdates.end();
66  assert(I < E && "Iterator range invalid; there should be DomTree updates.");
67  DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
68  PendDTUpdateIndex = PendUpdates.size();
69  }
70 }
71 
73  applyDomTreeUpdates();
74  applyPostDomTreeUpdates();
75  dropOutOfDateUpdates();
76 }
77 
78 void DomTreeUpdater::applyPostDomTreeUpdates() {
79  // No pending PostDomTreeUpdates.
80  if (Strategy != UpdateStrategy::Lazy || !PDT)
81  return;
82 
83  // Only apply updates not are applied by PostDomTree.
85  const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
86  const auto E = PendUpdates.end();
87  assert(I < E &&
88  "Iterator range invalid; there should be PostDomTree updates.");
90  PendPDTUpdateIndex = PendUpdates.size();
91  }
92 }
93 
94 void DomTreeUpdater::tryFlushDeletedBB() {
95  if (!hasPendingUpdates())
96  forceFlushDeletedBB();
97 }
98 
99 bool DomTreeUpdater::forceFlushDeletedBB() {
100  if (DeletedBBs.empty())
101  return false;
102 
103  for (auto *BB : DeletedBBs) {
104  // After calling deleteBB or callbackDeleteBB under Lazy UpdateStrategy,
105  // validateDeleteBB() removes all instructions of DelBB and adds an
106  // UnreachableInst as its terminator. So we check whether the BasicBlock to
107  // delete only has an UnreachableInst inside.
108  assert(BB->getInstList().size() == 1 &&
109  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 (undef).
221  if (!I.use_empty())
222  I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
223  DelBB->getInstList().pop_back();
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  for (const auto &U : Updates)
236  if (!isSelfDominance(U))
237  PendUpdates.push_back(U);
238 
239  return;
240  }
241 
242  if (DT)
243  DT->applyUpdates(Updates);
244  if (PDT)
245  PDT->applyUpdates(Updates);
246 }
247 
250  if (!DT && !PDT)
251  return;
252 
254  SmallVector<DominatorTree::UpdateType, 8> DeduplicatedUpdates;
255  for (const auto &U : Updates) {
256  auto Edge = std::make_pair(U.getFrom(), U.getTo());
257  // Because it is illegal to submit updates that have already been applied
258  // and updates to an edge need to be strictly ordered,
259  // it is safe to infer the existence of an edge from the first update
260  // to this edge.
261  // If the first update to an edge is "Delete", it means that the edge
262  // existed before. If the first update to an edge is "Insert", it means
263  // that the edge didn't exist before.
264  //
265  // For example, if the user submits {{Delete, A, B}, {Insert, A, B}},
266  // because
267  // 1. it is illegal to submit updates that have already been applied,
268  // i.e., user cannot delete an nonexistent edge,
269  // 2. updates to an edge need to be strictly ordered,
270  // So, initially edge A -> B existed.
271  // We can then safely ignore future updates to this edge and directly
272  // inspect the current CFG:
273  // a. If the edge still exists, because the user cannot insert an existent
274  // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and
275  // resulted in a no-op. DTU won't submit any update in this case.
276  // b. If the edge doesn't exist, we can then infer that {Delete, A, B}
277  // actually happened but {Insert, A, B} was an invalid update which never
278  // happened. DTU will submit {Delete, A, B} in this case.
279  if (!isSelfDominance(U) && Seen.count(Edge) == 0) {
280  Seen.insert(Edge);
281  // If the update doesn't appear in the CFG, it means that
282  // either the change isn't made or relevant operations
283  // result in a no-op.
284  if (isUpdateValid(U)) {
285  if (isLazy())
286  PendUpdates.push_back(U);
287  else
288  DeduplicatedUpdates.push_back(U);
289  }
290  }
291  }
292 
293  if (Strategy == UpdateStrategy::Lazy)
294  return;
295 
296  if (DT)
297  DT->applyUpdates(DeduplicatedUpdates);
298  if (PDT)
299  PDT->applyUpdates(DeduplicatedUpdates);
300 }
301 
303  assert(DT && "Invalid acquisition of a null DomTree");
304  applyDomTreeUpdates();
305  dropOutOfDateUpdates();
306  return *DT;
307 }
308 
310  assert(PDT && "Invalid acquisition of a null PostDomTree");
311  applyPostDomTreeUpdates();
312  dropOutOfDateUpdates();
313  return *PDT;
314 }
315 
316 void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) {
317 
318 #ifndef NDEBUG
319  assert(isUpdateValid({DominatorTree::Insert, From, To}) &&
320  "Inserted edge does not appear in the CFG");
321 #endif
322 
323  if (!DT && !PDT)
324  return;
325 
326  // Won't affect DomTree and PostDomTree; discard update.
327  if (From == To)
328  return;
329 
330  if (Strategy == UpdateStrategy::Eager) {
331  if (DT)
332  DT->insertEdge(From, To);
333  if (PDT)
334  PDT->insertEdge(From, To);
335  return;
336  }
337 
338  PendUpdates.push_back({DominatorTree::Insert, From, To});
339 }
340 
341 void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
342  if (From == To)
343  return;
344 
345  if (!DT && !PDT)
346  return;
347 
348  if (!isUpdateValid({DominatorTree::Insert, From, To}))
349  return;
350 
351  if (Strategy == UpdateStrategy::Eager) {
352  if (DT)
353  DT->insertEdge(From, To);
354  if (PDT)
355  PDT->insertEdge(From, To);
356  return;
357  }
358 
359  PendUpdates.push_back({DominatorTree::Insert, From, To});
360 }
361 
362 void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
363 
364 #ifndef NDEBUG
365  assert(isUpdateValid({DominatorTree::Delete, From, To}) &&
366  "Deleted edge still exists in the CFG!");
367 #endif
368 
369  if (!DT && !PDT)
370  return;
371 
372  // Won't affect DomTree and PostDomTree; discard update.
373  if (From == To)
374  return;
375 
376  if (Strategy == UpdateStrategy::Eager) {
377  if (DT)
378  DT->deleteEdge(From, To);
379  if (PDT)
380  PDT->deleteEdge(From, To);
381  return;
382  }
383 
384  PendUpdates.push_back({DominatorTree::Delete, From, To});
385 }
386 
387 void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
388  if (From == To)
389  return;
390 
391  if (!DT && !PDT)
392  return;
393 
394  if (!isUpdateValid({DominatorTree::Delete, From, To}))
395  return;
396 
397  if (Strategy == UpdateStrategy::Eager) {
398  if (DT)
399  DT->deleteEdge(From, To);
400  if (PDT)
401  PDT->deleteEdge(From, To);
402  return;
403  }
404 
405  PendUpdates.push_back({DominatorTree::Delete, From, To});
406 }
407 
408 void DomTreeUpdater::dropOutOfDateUpdates() {
410  return;
411 
412  tryFlushDeletedBB();
413 
414  // Drop all updates applied by both trees.
415  if (!DT)
416  PendDTUpdateIndex = PendUpdates.size();
417  if (!PDT)
418  PendPDTUpdateIndex = PendUpdates.size();
419 
420  const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
421  const auto B = PendUpdates.begin();
422  const auto E = PendUpdates.begin() + dropIndex;
423  assert(B <= E && "Iterator out of range.");
424  PendUpdates.erase(B, E);
425  // Calculate current index.
426  PendDTUpdateIndex -= dropIndex;
427  PendPDTUpdateIndex -= dropIndex;
428 }
429 
430 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
432  raw_ostream &OS = llvm::dbgs();
433 
434  OS << "Available Trees: ";
435  if (DT || PDT) {
436  if (DT)
437  OS << "DomTree ";
438  if (PDT)
439  OS << "PostDomTree ";
440  OS << "\n";
441  } else
442  OS << "None\n";
443 
444  OS << "UpdateStrategy: ";
445  if (Strategy == UpdateStrategy::Eager) {
446  OS << "Eager\n";
447  return;
448  } else
449  OS << "Lazy\n";
450  int Index = 0;
451 
452  auto printUpdates =
455  if (begin == end)
456  OS << " None\n";
457  Index = 0;
458  for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
459  auto U = *It;
460  OS << " " << Index << " : ";
461  ++Index;
462  if (U.getKind() == DominatorTree::Insert)
463  OS << "Insert, ";
464  else
465  OS << "Delete, ";
466  BasicBlock *From = U.getFrom();
467  if (From) {
468  auto S = From->getName();
469  if (!From->hasName())
470  S = "(no name)";
471  OS << S << "(" << From << "), ";
472  } else {
473  OS << "(badref), ";
474  }
475  BasicBlock *To = U.getTo();
476  if (To) {
477  auto S = To->getName();
478  if (!To->hasName())
479  S = "(no_name)";
480  OS << S << "(" << To << ")\n";
481  } else {
482  OS << "(badref)\n";
483  }
484  }
485  };
486 
487  if (DT) {
488  const auto I = PendUpdates.begin() + PendDTUpdateIndex;
489  assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
490  "Iterator out of range.");
491  OS << "Applied but not cleared DomTreeUpdates:\n";
492  printUpdates(PendUpdates.begin(), I);
493  OS << "Pending DomTreeUpdates:\n";
494  printUpdates(I, PendUpdates.end());
495  }
496 
497  if (PDT) {
498  const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
499  assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
500  "Iterator out of range.");
501  OS << "Applied but not cleared PostDomTreeUpdates:\n";
502  printUpdates(PendUpdates.begin(), I);
503  OS << "Pending PostDomTreeUpdates:\n";
504  printUpdates(I, PendUpdates.end());
505  }
506 
507  OS << "Pending DeletedBBs:\n";
508  Index = 0;
509  for (const auto *BB : DeletedBBs) {
510  OS << " " << Index << " : ";
511  ++Index;
512  if (BB->hasName())
513  OS << BB->getName() << "(";
514  else
515  OS << "(no_name)(";
516  OS << BB << ")\n";
517  }
518 
519  OS << "Pending Callbacks:\n";
520  Index = 0;
521  for (const auto &BB : Callbacks) {
522  OS << " " << Index << " : ";
523  ++Index;
524  if (BB->hasName())
525  OS << BB->getName() << "(";
526  else
527  OS << "(no_name)(";
528  OS << BB << ")\n";
529  }
530 }
531 #endif
532 } // namespace llvm
llvm::EngineKind::Kind
Kind
Definition: ExecutionEngine.h:524
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:498
llvm
This class represents lattice values for constants.
Definition: AllocatorList.h:23
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:705
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:61
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::Value::hasName
bool hasName() const
Definition: Value.h:252
DomTreeUpdater.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
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:233
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
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:134
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:260
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:56
llvm::DomTreeUpdater::UpdateStrategy::Lazy
@ Lazy
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
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
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:431
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::DominatorTreeBase::insertEdge
void insertEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge insertion and update the tree.
Definition: GenericDomTree.h:584
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
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:50
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1751
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:164
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
llvm::BasicBlock::removeFromParent
void removeFromParent()
Unlink 'this' from the containing function, but do not delete it.
Definition: BasicBlock.cpp:125
llvm::DomTreeUpdater::getDomTree
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
Definition: DomTreeUpdater.cpp:302
I
#define I(x, y, z)
Definition: MD5.cpp:59
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:1563
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:64
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
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:339
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:117
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:180
llvm::DomTreeUpdater::flush
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
Definition: DomTreeUpdater.cpp:72
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:295
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:309
Instructions.h
llvm::ArrayRef::const_iterator
const T * const_iterator
Definition: ArrayRef.h:44
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::DomTreeUpdater::applyUpdatesPermissive
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:248
llvm::DominatorTreeBase::deleteEdge
void deleteEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge deletion and update the tree.
Definition: GenericDomTree.h:602
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
SmallSet.h