Skip to content

Commit ce698a5

Browse files
committedAug 11, 2018
[Dominators] Remove the DeferredDominance class
Summary: After converting all existing passes to use the new DomTreeUpdater interface, there isn't any usage of the original DeferredDominance class. Thus, we can safely remove it from the codebase. Reviewers: kuhar, brzycki, dmgreen, davide, grosser Reviewed By: kuhar, brzycki Subscribers: mgorny, llvm-commits Differential Revision: https://reviews.llvm.org/D49747 llvm-svn: 339502
1 parent f7111d1 commit ce698a5

File tree

4 files changed

+0
-623
lines changed

4 files changed

+0
-623
lines changed
 

‎llvm/include/llvm/IR/Dominators.h

-88
Original file line numberDiff line numberDiff line change
@@ -276,94 +276,6 @@ class DominatorTreeWrapperPass : public FunctionPass {
276276

277277
void print(raw_ostream &OS, const Module *M = nullptr) const override;
278278
};
279-
280-
//===-------------------------------------
281-
/// Class to defer updates to a DominatorTree.
282-
///
283-
/// Definition: Applying updates to every edge insertion and deletion is
284-
/// expensive and not necessary. When one needs the DominatorTree for analysis
285-
/// they can request a flush() to perform a larger batch update. This has the
286-
/// advantage of the DominatorTree inspecting the set of updates to find
287-
/// duplicates or unnecessary subtree updates.
288-
///
289-
/// The scope of DeferredDominance operates at a Function level.
290-
///
291-
/// It is not necessary for the user to scrub the updates for duplicates or
292-
/// updates that point to the same block (Delete, BB_A, BB_A). Performance
293-
/// can be gained if the caller attempts to batch updates before submitting
294-
/// to applyUpdates(ArrayRef) in cases where duplicate edge requests will
295-
/// occur.
296-
///
297-
/// It is required for the state of the LLVM IR to be applied *before*
298-
/// submitting updates. The update routines must analyze the current state
299-
/// between a pair of (From, To) basic blocks to determine if the update
300-
/// needs to be queued.
301-
/// Example (good):
302-
/// TerminatorInstructionBB->removeFromParent();
303-
/// DDT->deleteEdge(BB, Successor);
304-
/// Example (bad):
305-
/// DDT->deleteEdge(BB, Successor);
306-
/// TerminatorInstructionBB->removeFromParent();
307-
class DeferredDominance {
308-
public:
309-
DeferredDominance(DominatorTree &DT_) : DT(DT_) {}
310-
311-
/// Queues multiple updates and discards duplicates.
312-
void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates);
313-
314-
/// Helper method for a single edge insertion. It's almost always
315-
/// better to batch updates and call applyUpdates to quickly remove duplicate
316-
/// edges. This is best used when there is only a single insertion needed to
317-
/// update Dominators.
318-
void insertEdge(BasicBlock *From, BasicBlock *To);
319-
320-
/// Helper method for a single edge deletion. It's almost always better
321-
/// to batch updates and call applyUpdates to quickly remove duplicate edges.
322-
/// This is best used when there is only a single deletion needed to update
323-
/// Dominators.
324-
void deleteEdge(BasicBlock *From, BasicBlock *To);
325-
326-
/// Delays the deletion of a basic block until a flush() event.
327-
void deleteBB(BasicBlock *DelBB);
328-
329-
/// Returns true if DelBB is awaiting deletion at a flush() event.
330-
bool pendingDeletedBB(BasicBlock *DelBB);
331-
332-
/// Returns true if pending DT updates are queued for a flush() event.
333-
bool pending();
334-
335-
/// Flushes all pending updates and block deletions. Returns a
336-
/// correct DominatorTree reference to be used by the caller for analysis.
337-
DominatorTree &flush();
338-
339-
/// Drops all internal state and forces a (slow) recalculation of the
340-
/// DominatorTree based on the current state of the LLVM IR in F. This should
341-
/// only be used in corner cases such as the Entry block of F being deleted.
342-
void recalculate(Function &F);
343-
344-
/// Debug method to help view the state of pending updates.
345-
LLVM_DUMP_METHOD void dump() const;
346-
347-
private:
348-
DominatorTree &DT;
349-
SmallVector<DominatorTree::UpdateType, 16> PendUpdates;
350-
SmallPtrSet<BasicBlock *, 8> DeletedBBs;
351-
352-
/// Apply an update (Kind, From, To) to the internal queued updates. The
353-
/// update is only added when determined to be necessary. Checks for
354-
/// self-domination, unnecessary updates, duplicate requests, and balanced
355-
/// pairs of requests are all performed. Returns true if the update is
356-
/// queued and false if it is discarded.
357-
bool applyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From,
358-
BasicBlock *To);
359-
360-
/// Performs all pending basic block deletions. We have to defer the deletion
361-
/// of these blocks until after the DominatorTree updates are applied. The
362-
/// internal workings of the DominatorTree code expect every update's From
363-
/// and To blocks to exist and to be a member of the same Function.
364-
bool flushDelBB();
365-
};
366-
367279
} // end namespace llvm
368280

369281
#endif // LLVM_IR_DOMINATORS_H

‎llvm/lib/IR/Dominators.cpp

-190
Original file line numberDiff line numberDiff line change
@@ -372,193 +372,3 @@ void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
372372
DT.print(OS);
373373
}
374374

375-
//===----------------------------------------------------------------------===//
376-
// DeferredDominance Implementation
377-
//===----------------------------------------------------------------------===//
378-
//
379-
// The implementation details of the DeferredDominance class which allows
380-
// one to queue updates to a DominatorTree.
381-
//
382-
//===----------------------------------------------------------------------===//
383-
384-
/// Queues multiple updates and discards duplicates.
385-
void DeferredDominance::applyUpdates(
386-
ArrayRef<DominatorTree::UpdateType> Updates) {
387-
SmallVector<DominatorTree::UpdateType, 8> Seen;
388-
for (auto U : Updates)
389-
// Avoid duplicates to applyUpdate() to save on analysis.
390-
if (std::none_of(Seen.begin(), Seen.end(),
391-
[U](DominatorTree::UpdateType S) { return S == U; })) {
392-
Seen.push_back(U);
393-
applyUpdate(U.getKind(), U.getFrom(), U.getTo());
394-
}
395-
}
396-
397-
/// Helper method for a single edge insertion. It's almost always better
398-
/// to batch updates and call applyUpdates to quickly remove duplicate edges.
399-
/// This is best used when there is only a single insertion needed to update
400-
/// Dominators.
401-
void DeferredDominance::insertEdge(BasicBlock *From, BasicBlock *To) {
402-
applyUpdate(DominatorTree::Insert, From, To);
403-
}
404-
405-
/// Helper method for a single edge deletion. It's almost always better
406-
/// to batch updates and call applyUpdates to quickly remove duplicate edges.
407-
/// This is best used when there is only a single deletion needed to update
408-
/// Dominators.
409-
void DeferredDominance::deleteEdge(BasicBlock *From, BasicBlock *To) {
410-
applyUpdate(DominatorTree::Delete, From, To);
411-
}
412-
413-
/// Delays the deletion of a basic block until a flush() event.
414-
void DeferredDominance::deleteBB(BasicBlock *DelBB) {
415-
assert(DelBB && "Invalid push_back of nullptr DelBB.");
416-
assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
417-
// DelBB is unreachable and all its instructions are dead.
418-
while (!DelBB->empty()) {
419-
Instruction &I = DelBB->back();
420-
// Replace used instructions with an arbitrary value (undef).
421-
if (!I.use_empty())
422-
I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
423-
DelBB->getInstList().pop_back();
424-
}
425-
// Make sure DelBB has a valid terminator instruction. As long as DelBB is a
426-
// Child of Function F it must contain valid IR.
427-
new UnreachableInst(DelBB->getContext(), DelBB);
428-
DeletedBBs.insert(DelBB);
429-
}
430-
431-
/// Returns true if DelBB is awaiting deletion at a flush() event.
432-
bool DeferredDominance::pendingDeletedBB(BasicBlock *DelBB) {
433-
if (DeletedBBs.empty())
434-
return false;
435-
return DeletedBBs.count(DelBB) != 0;
436-
}
437-
438-
/// Returns true if pending DT updates are queued for a flush() event.
439-
bool DeferredDominance::pending() { return !PendUpdates.empty(); }
440-
441-
/// Flushes all pending updates and block deletions. Returns a
442-
/// correct DominatorTree reference to be used by the caller for analysis.
443-
DominatorTree &DeferredDominance::flush() {
444-
// Updates to DT must happen before blocks are deleted below. Otherwise the
445-
// DT traversal will encounter badref blocks and assert.
446-
if (!PendUpdates.empty()) {
447-
DT.applyUpdates(PendUpdates);
448-
PendUpdates.clear();
449-
}
450-
flushDelBB();
451-
return DT;
452-
}
453-
454-
/// Drops all internal state and forces a (slow) recalculation of the
455-
/// DominatorTree based on the current state of the LLVM IR in F. This should
456-
/// only be used in corner cases such as the Entry block of F being deleted.
457-
void DeferredDominance::recalculate(Function &F) {
458-
// flushDelBB must be flushed before the recalculation. The state of the IR
459-
// must be consistent before the DT traversal algorithm determines the
460-
// actual DT.
461-
if (flushDelBB() || !PendUpdates.empty()) {
462-
DT.recalculate(F);
463-
PendUpdates.clear();
464-
}
465-
}
466-
467-
/// Debug method to help view the state of pending updates.
468-
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
469-
LLVM_DUMP_METHOD void DeferredDominance::dump() const {
470-
raw_ostream &OS = llvm::dbgs();
471-
OS << "PendUpdates:\n";
472-
int I = 0;
473-
for (auto U : PendUpdates) {
474-
OS << " " << I << " : ";
475-
++I;
476-
if (U.getKind() == DominatorTree::Insert)
477-
OS << "Insert, ";
478-
else
479-
OS << "Delete, ";
480-
BasicBlock *From = U.getFrom();
481-
if (From) {
482-
auto S = From->getName();
483-
if (!From->hasName())
484-
S = "(no name)";
485-
OS << S << "(" << From << "), ";
486-
} else {
487-
OS << "(badref), ";
488-
}
489-
BasicBlock *To = U.getTo();
490-
if (To) {
491-
auto S = To->getName();
492-
if (!To->hasName())
493-
S = "(no_name)";
494-
OS << S << "(" << To << ")\n";
495-
} else {
496-
OS << "(badref)\n";
497-
}
498-
}
499-
OS << "DeletedBBs:\n";
500-
I = 0;
501-
for (auto BB : DeletedBBs) {
502-
OS << " " << I << " : ";
503-
++I;
504-
if (BB->hasName())
505-
OS << BB->getName() << "(";
506-
else
507-
OS << "(no_name)(";
508-
OS << BB << ")\n";
509-
}
510-
}
511-
#endif
512-
513-
/// Apply an update (Kind, From, To) to the internal queued updates. The
514-
/// update is only added when determined to be necessary. Checks for
515-
/// self-domination, unnecessary updates, duplicate requests, and balanced
516-
/// pairs of requests are all performed. Returns true if the update is
517-
/// queued and false if it is discarded.
518-
bool DeferredDominance::applyUpdate(DominatorTree::UpdateKind Kind,
519-
BasicBlock *From, BasicBlock *To) {
520-
if (From == To)
521-
return false; // Cannot dominate self; discard update.
522-
523-
// Discard updates by inspecting the current state of successors of From.
524-
// Since applyUpdate() must be called *after* the Terminator of From is
525-
// altered we can determine if the update is unnecessary.
526-
bool HasEdge = std::any_of(succ_begin(From), succ_end(From),
527-
[To](BasicBlock *B) { return B == To; });
528-
if (Kind == DominatorTree::Insert && !HasEdge)
529-
return false; // Unnecessary Insert: edge does not exist in IR.
530-
if (Kind == DominatorTree::Delete && HasEdge)
531-
return false; // Unnecessary Delete: edge still exists in IR.
532-
533-
// Analyze pending updates to determine if the update is unnecessary.
534-
DominatorTree::UpdateType Update = {Kind, From, To};
535-
DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
536-
? DominatorTree::Insert
537-
: DominatorTree::Delete,
538-
From, To};
539-
for (auto I = PendUpdates.begin(), E = PendUpdates.end(); I != E; ++I) {
540-
if (Update == *I)
541-
return false; // Discard duplicate updates.
542-
if (Invert == *I) {
543-
// Update and Invert are both valid (equivalent to a no-op). Remove
544-
// Invert from PendUpdates and discard the Update.
545-
PendUpdates.erase(I);
546-
return false;
547-
}
548-
}
549-
PendUpdates.push_back(Update); // Save the valid update.
550-
return true;
551-
}
552-
553-
/// Performs all pending basic block deletions. We have to defer the deletion
554-
/// of these blocks until after the DominatorTree updates are applied. The
555-
/// internal workings of the DominatorTree code expect every update's From
556-
/// and To blocks to exist and to be a member of the same Function.
557-
bool DeferredDominance::flushDelBB() {
558-
if (DeletedBBs.empty())
559-
return false;
560-
for (auto *BB : DeletedBBs)
561-
BB->eraseFromParent();
562-
DeletedBBs.clear();
563-
return true;
564-
}

‎llvm/unittests/IR/CMakeLists.txt

-1
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,6 @@ add_llvm_unittest(IRTests
1515
ConstantsTest.cpp
1616
DebugInfoTest.cpp
1717
DebugTypeODRUniquingTest.cpp
18-
DeferredDominanceTest.cpp
1918
DominatorTreeTest.cpp
2019
DominatorTreeBatchUpdatesTest.cpp
2120
DomTreeUpdaterTest.cpp

‎llvm/unittests/IR/DeferredDominanceTest.cpp

-344
This file was deleted.

0 commit comments

Comments
 (0)
Please sign in to comment.