LLVM  14.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  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::insertEdge(BasicBlock *From, BasicBlock *To) {
318 
319 #ifndef NDEBUG
320  assert(isUpdateValid({DominatorTree::Insert, From, To}) &&
321  "Inserted edge does not appear in the CFG");
322 #endif
323 
324  if (!DT && !PDT)
325  return;
326 
327  // Won't affect DomTree and PostDomTree; discard update.
328  if (From == To)
329  return;
330 
331  if (Strategy == UpdateStrategy::Eager) {
332  if (DT)
333  DT->insertEdge(From, To);
334  if (PDT)
335  PDT->insertEdge(From, To);
336  return;
337  }
338 
339  PendUpdates.push_back({DominatorTree::Insert, From, To});
340 }
341 
342 void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
343  if (From == To)
344  return;
345 
346  if (!DT && !PDT)
347  return;
348 
349  if (!isUpdateValid({DominatorTree::Insert, From, To}))
350  return;
351 
352  if (Strategy == UpdateStrategy::Eager) {
353  if (DT)
354  DT->insertEdge(From, To);
355  if (PDT)
356  PDT->insertEdge(From, To);
357  return;
358  }
359 
360  PendUpdates.push_back({DominatorTree::Insert, From, To});
361 }
362 
363 void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
364 
365 #ifndef NDEBUG
366  assert(isUpdateValid({DominatorTree::Delete, From, To}) &&
367  "Deleted edge still exists in the CFG!");
368 #endif
369 
370  if (!DT && !PDT)
371  return;
372 
373  // Won't affect DomTree and PostDomTree; discard update.
374  if (From == To)
375  return;
376 
377  if (Strategy == UpdateStrategy::Eager) {
378  if (DT)
379  DT->deleteEdge(From, To);
380  if (PDT)
381  PDT->deleteEdge(From, To);
382  return;
383  }
384 
385  PendUpdates.push_back({DominatorTree::Delete, From, To});
386 }
387 
388 void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
389  if (From == To)
390  return;
391 
392  if (!DT && !PDT)
393  return;
394 
395  if (!isUpdateValid({DominatorTree::Delete, From, To}))
396  return;
397 
398  if (Strategy == UpdateStrategy::Eager) {
399  if (DT)
400  DT->deleteEdge(From, To);
401  if (PDT)
402  PDT->deleteEdge(From, To);
403  return;
404  }
405 
406  PendUpdates.push_back({DominatorTree::Delete, From, To});
407 }
408 
409 void DomTreeUpdater::dropOutOfDateUpdates() {
411  return;
412 
413  tryFlushDeletedBB();
414 
415  // Drop all updates applied by both trees.
416  if (!DT)
417  PendDTUpdateIndex = PendUpdates.size();
418  if (!PDT)
419  PendPDTUpdateIndex = PendUpdates.size();
420 
421  const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
422  const auto B = PendUpdates.begin();
423  const auto E = PendUpdates.begin() + dropIndex;
424  assert(B <= E && "Iterator out of range.");
425  PendUpdates.erase(B, E);
426  // Calculate current index.
427  PendDTUpdateIndex -= dropIndex;
428  PendPDTUpdateIndex -= dropIndex;
429 }
430 
431 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
433  raw_ostream &OS = llvm::dbgs();
434 
435  OS << "Available Trees: ";
436  if (DT || PDT) {
437  if (DT)
438  OS << "DomTree ";
439  if (PDT)
440  OS << "PostDomTree ";
441  OS << "\n";
442  } else
443  OS << "None\n";
444 
445  OS << "UpdateStrategy: ";
446  if (Strategy == UpdateStrategy::Eager) {
447  OS << "Eager\n";
448  return;
449  } else
450  OS << "Lazy\n";
451  int Index = 0;
452 
453  auto printUpdates =
456  if (begin == end)
457  OS << " None\n";
458  Index = 0;
459  for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
460  auto U = *It;
461  OS << " " << Index << " : ";
462  ++Index;
463  if (U.getKind() == DominatorTree::Insert)
464  OS << "Insert, ";
465  else
466  OS << "Delete, ";
467  BasicBlock *From = U.getFrom();
468  if (From) {
469  auto S = From->getName();
470  if (!From->hasName())
471  S = "(no name)";
472  OS << S << "(" << From << "), ";
473  } else {
474  OS << "(badref), ";
475  }
476  BasicBlock *To = U.getTo();
477  if (To) {
478  auto S = To->getName();
479  if (!To->hasName())
480  S = "(no_name)";
481  OS << S << "(" << To << ")\n";
482  } else {
483  OS << "(badref)\n";
484  }
485  }
486  };
487 
488  if (DT) {
489  const auto I = PendUpdates.begin() + PendDTUpdateIndex;
490  assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
491  "Iterator out of range.");
492  OS << "Applied but not cleared DomTreeUpdates:\n";
493  printUpdates(PendUpdates.begin(), I);
494  OS << "Pending DomTreeUpdates:\n";
495  printUpdates(I, PendUpdates.end());
496  }
497 
498  if (PDT) {
499  const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
500  assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
501  "Iterator out of range.");
502  OS << "Applied but not cleared PostDomTreeUpdates:\n";
503  printUpdates(PendUpdates.begin(), I);
504  OS << "Pending PostDomTreeUpdates:\n";
505  printUpdates(I, PendUpdates.end());
506  }
507 
508  OS << "Pending DeletedBBs:\n";
509  Index = 0;
510  for (const auto *BB : DeletedBBs) {
511  OS << " " << Index << " : ";
512  ++Index;
513  if (BB->hasName())
514  OS << BB->getName() << "(";
515  else
516  OS << "(no_name)(";
517  OS << BB << ")\n";
518  }
519 
520  OS << "Pending Callbacks:\n";
521  Index = 0;
522  for (const auto &BB : Callbacks) {
523  OS << " " << Index << " : ";
524  ++Index;
525  if (BB->hasName())
526  OS << BB->getName() << "(";
527  else
528  OS << "(no_name)(";
529  OS << BB << ")\n";
530  }
531 }
532 #endif
533 } // 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:506
llvm
This file implements support for optimizing divisions by a constant.
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:62
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:262
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:262
llvm::ArrayRef::const_iterator
const_pointer const_iterator
Definition: ArrayRef.h:51
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: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
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:432
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:53
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1796
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: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:129
llvm::DomTreeUpdater::getDomTree
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
Definition: DomTreeUpdater.cpp:303
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:1616
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: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: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:119
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:309
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:310
Instructions.h
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
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:624
llvm::DomTreeUpdater::applyUpdatesPermissive
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:249
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