Index: include/llvm/IR/DomTreeUpdater.h =================================================================== --- include/llvm/IR/DomTreeUpdater.h +++ include/llvm/IR/DomTreeUpdater.h @@ -17,6 +17,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/Statistic.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Instructions.h" Index: include/llvm/Support/GenericDomTree.h =================================================================== --- include/llvm/Support/GenericDomTree.h +++ include/llvm/Support/GenericDomTree.h @@ -24,6 +24,14 @@ #ifndef LLVM_SUPPORT_GENERICDOMTREE_H #define LLVM_SUPPORT_GENERICDOMTREE_H +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/Timer.h" +#include "llvm/Support/raw_ostream.h" #include #include #include @@ -32,16 +40,38 @@ #include #include #include -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/PointerIntPair.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/Support/raw_ostream.h" - namespace llvm { +struct Timers; + +inline Timers *&GetTimers() { + static Timers *TimersPtr = nullptr; + return TimersPtr; +} + +struct Timers { + Timer &DTApplyUpdatesTimer, &DTInsertEdgeTimer, &DTDeleteEdgeTimer, + &DTRecalculateTimer, &PDTApplyUpdatesTimer, &PDTInsertEdgeTimer, + &PDTDeleteEdgeTimer, &PDTRecalculateTimer; + + Timers(Timer &DTApplyUpdatesTimer_, Timer &DTInsertEdgeTimer_, + Timer &DTDeleteEdgeTimer_, Timer &DTRecalculateTimer_, + Timer &PDTApplyUpdatesTimer_, Timer &PDTInsertEdgeTimer_, + Timer &PDTDeleteEdgeTimer_, Timer &PDTRecalculateTimer_) + : DTApplyUpdatesTimer(DTApplyUpdatesTimer_), + DTInsertEdgeTimer(DTInsertEdgeTimer_), + DTDeleteEdgeTimer(DTDeleteEdgeTimer_), + DTRecalculateTimer(DTRecalculateTimer_), + PDTApplyUpdatesTimer(PDTApplyUpdatesTimer_), + PDTInsertEdgeTimer(PDTInsertEdgeTimer_), + PDTDeleteEdgeTimer(PDTDeleteEdgeTimer_), + PDTRecalculateTimer(PDTRecalculateTimer_) { + + llvm::GetTimers() = this; + } + static Timers *getTimers() { return GetTimers(); } +}; + template class DominatorTreeBase; @@ -544,7 +574,16 @@ /// \param Updates An unordered sequence of updates to perform. /// void applyUpdates(ArrayRef Updates) { + if (!Timers::getTimers()) { + DomTreeBuilder::ApplyUpdates(*this, Updates); + return; + } + Timer *T = &Timers::getTimers()->DTApplyUpdatesTimer; + if (this->isPostDominator()) + T = &Timers::getTimers()->PDTApplyUpdatesTimer; + T->startTimer(); DomTreeBuilder::ApplyUpdates(*this, Updates); + T->stopTimer(); } /// Inform the dominator tree about a CFG edge insertion and update the tree. @@ -561,7 +600,16 @@ assert(To); assert(From->getParent() == Parent); assert(To->getParent() == Parent); + if (!Timers::getTimers()) { + DomTreeBuilder::InsertEdge(*this, From, To); + return; + } + Timer *T = &Timers::getTimers()->DTInsertEdgeTimer; + if (this->isPostDominator()) + T = &Timers::getTimers()->PDTInsertEdgeTimer; + T->startTimer(); DomTreeBuilder::InsertEdge(*this, From, To); + T->stopTimer(); } /// Inform the dominator tree about a CFG edge deletion and update the tree. @@ -579,7 +627,16 @@ assert(To); assert(From->getParent() == Parent); assert(To->getParent() == Parent); + if (!Timers::getTimers()) { + DomTreeBuilder::DeleteEdge(*this, From, To); + return; + } + Timer *T = &Timers::getTimers()->DTDeleteEdgeTimer; + if (this->isPostDominator()) + T = &Timers::getTimers()->PDTDeleteEdgeTimer; + T->startTimer(); DomTreeBuilder::DeleteEdge(*this, From, To); + T->stopTimer(); } /// Add a new node to the dominator tree information. @@ -756,7 +813,16 @@ /// recalculate - compute a dominator tree for the given function void recalculate(ParentType &Func) { Parent = &Func; + if (!Timers::getTimers()) { + DomTreeBuilder::Calculate(*this); + return; + } + Timer *T = &Timers::getTimers()->DTRecalculateTimer; + if (this->isPostDominator()) + T = &Timers::getTimers()->PDTRecalculateTimer; + T->startTimer(); DomTreeBuilder::Calculate(*this); + T->stopTimer(); } /// verify - checks if the tree is correct. There are 3 level of verification: Index: lib/IR/DomTreeUpdater.cpp =================================================================== --- lib/IR/DomTreeUpdater.cpp +++ lib/IR/DomTreeUpdater.cpp @@ -13,19 +13,76 @@ //===----------------------------------------------------------------------===// #include "llvm/IR/DomTreeUpdater.h" +#include "llvm/ADT/Statistic.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/IR/Dominators.h" #include "llvm/Support/GenericDomTree.h" +#include "llvm/Support/Timer.h" #include #include - namespace llvm { +#define DEBUG_TYPE "DTU-stats" + +STATISTIC(NumNoopPruned, "Number of no-ops removed"); +STATISTIC(NumDuplicatePruned, "Number of duplicates removed"); +STATISTIC(NumInvalidPruned, "Number of invalid updates discarded"); +STATISTIC(NumRecalculate, "Number of recalculations requested"); +STATISTIC(NumLazyUpdate, "Number of lazy updates applied"); + +#undef DEBUG_TYPE + +static TimerGroup DTTimerGroup("DomTree Timer", "DomTree Calculation"); +static Timer DTApplyUpdatesTimer("domtree-au", "apply-updates -- DomTree", + DTTimerGroup); +static Timer DTInsertEdgeTimer("domtree-ie", "insert-edge -- DomTree", + DTTimerGroup); +static Timer DTDeleteEdgeTimer("domtree-de", "delete-edge -- DomTree", + DTTimerGroup); +static Timer DTRecalculateTimer("domtree-re", "recalculate -- DomTree", + DTTimerGroup); +static Timer PDTApplyUpdatesTimer("pdomtree-au", "apply-updates -- PostDomTree", + DTTimerGroup); +static Timer PDTInsertEdgeTimer("pdomtree-ie", "insert-edge -- PostDomTree", + DTTimerGroup); +static Timer PDTDeleteEdgeTimer("pdomtree-de", "delete-edge -- PostDomTree", + DTTimerGroup); +static Timer PDTRecalculateTimer("pdomtree-re", "recalculate -- PostDomTree", + DTTimerGroup); +static Timers DTTimers(DTApplyUpdatesTimer, DTInsertEdgeTimer, + DTDeleteEdgeTimer, DTRecalculateTimer, + PDTApplyUpdatesTimer, PDTInsertEdgeTimer, + PDTDeleteEdgeTimer, PDTRecalculateTimer); +static TimerGroup DTUTimerGroup("DTU Timer", "DTU timing"); +static Timer DTUApplyUpdatesTimer("domtree-au", "apply-updates -- DomTree", + DTUTimerGroup); +static Timer DTUInsertEdgeTimer("domtree-ie", "insert-edge -- DomTree", + DTUTimerGroup); +static Timer DTUDeleteEdgeTimer("domtree-de", "delete-edge -- DomTree", + DTUTimerGroup); +static Timer DTURecalculateTimer("domtree-re", "recalculate -- DomTree", + DTUTimerGroup); +static Timer PDTUApplyUpdatesTimer("pdomtree-au", + "apply-updates -- PostDomTree", + DTUTimerGroup); +static Timer PDTUInsertEdgeTimer("pdomtree-ie", "insert-edge -- PostDomTree", + DTUTimerGroup); +static Timer PDTUDeleteEdgeTimer("pdomtree-de", "delete-edge -- PostDomTree", + DTUTimerGroup); +static Timer PDTURecalculateTimer("pdomtree-re", "recalculate -- PostDomTree", + DTUTimerGroup); +static Timer SnapshotTimer("Snapshot", "Snapshot", DTUTimerGroup); +static Timer SnapshotSortTimer("SnapshotSort", "SnapshotSort", DTUTimerGroup); +static Timer PendPushTimer("PendPush", "PendPush", DTUTimerGroup); +static Timer DiffTimer("Diff", "Diff", DTUTimerGroup); +static Timer DeduplicateTimer("Deduplicate", "Deduplicate", DTUTimerGroup); + bool DomTreeUpdater::isUpdateValid( const DominatorTree::UpdateType Update) const { #ifdef NDEBUG assert(!isAuto()); #endif + ++NumInvalidPruned; const auto *From = Update.getFrom(); const auto *To = Update.getTo(); const auto Kind = Update.getKind(); @@ -47,11 +104,12 @@ // Edge exists in IR. if (Kind == DominatorTree::Delete && HasEdge) return false; - + --NumInvalidPruned; return true; } std::vector DomTreeUpdater::diffCFG() { + DiffTimer.startTimer(); auto getNewCFG = [&](BasicBlock *BB) { std::vector Ret; @@ -94,6 +152,7 @@ } PendPoints.clear(); + DiffTimer.stopTimer(); NeedCalculate = false; return Updates; @@ -103,7 +162,9 @@ if (!DT && !PDT) return; + PendPushTimer.startTimer(); Graph.clear(); + PendPushTimer.stopTimer(); if (!Func) { if (DT) @@ -114,6 +175,7 @@ SnapshotedBB = &Func->getEntryBlock(); + SnapshotTimer.startTimer(); for (BasicBlock &BB : Func->getBasicBlockList()) { Graph[&BB].first = false; // Not sorted. auto &I = Graph[&BB].second; @@ -121,6 +183,7 @@ for (auto *Addr : successors(&BB)) I.push_back(Addr); } + SnapshotTimer.stopTimer(); } bool DomTreeUpdater::isSelfDominance( @@ -149,17 +212,20 @@ assert(I <= E && "Iterator out of range."); for (; I != E; ++I) { - if (Update == *I) + if (Update == *I) { + ++NumDuplicatePruned; return false; // Discard duplicate updates. - + } if (Invert == *I) { // Update and Invert are both valid (equivalent to a no-op). Remove // Invert from PendUpdates and discard the Update. + ++NumNoopPruned; + --NumLazyUpdate; PendUpdates.erase(I); return false; } } - + ++NumLazyUpdate; PendUpdates.push_back(Update); // Save the valid update. return true; } @@ -174,7 +240,9 @@ const auto I = PendUpdates.begin() + PendDTUpdateIndex; const auto E = PendUpdates.end(); assert(I < E && "Iterator range invalid; there should be DomTree updates."); + DTUApplyUpdatesTimer.startTimer(); DT->applyUpdates(ArrayRef(I, E)); + DTUApplyUpdatesTimer.stopTimer(); PendDTUpdateIndex = PendUpdates.size(); } } @@ -199,7 +267,9 @@ const auto E = PendUpdates.end(); assert(I < E && "Iterator range invalid; there should be PostDomTree updates."); + PDTUApplyUpdatesTimer.startTimer(); PDT->applyUpdates(ArrayRef(I, E)); + PDTUApplyUpdatesTimer.stopTimer(); PendPDTUpdateIndex = PendUpdates.size(); } } @@ -233,10 +303,18 @@ void DomTreeUpdater::recalculate(Function &F) { if (Strategy == UpdateStrategy::Eager) { + if (DT) + ++NumRecalculate; + if (PDT) + ++NumRecalculate; + DTURecalculateTimer.startTimer(); if (DT) DT->recalculate(F); + DTURecalculateTimer.stopTimer(); + PDTURecalculateTimer.startTimer(); if (PDT) PDT->recalculate(F); + PDTURecalculateTimer.stopTimer(); return; } @@ -258,10 +336,18 @@ } } + if (DT) + ++NumRecalculate; + if (PDT) + ++NumRecalculate; + DTURecalculateTimer.startTimer(); if (DT) DT->recalculate(F); + DTURecalculateTimer.stopTimer(); + PDTURecalculateTimer.startTimer(); if (PDT) PDT->recalculate(F); + PDTURecalculateTimer.stopTimer(); // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes. IsRecalculatingDomTree = IsRecalculatingPostDomTree = false; @@ -355,9 +441,11 @@ if (PDT->getNode(DelBB)) PDT->eraseNode(DelBB); + PendPushTimer.startTimer(); // Delete this FromBB in case of memory leak. if (isAuto()) SnapshotedCFG.erase(DelBB); + PendPushTimer.stopTimer(); } void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) { @@ -386,16 +474,20 @@ if (Updates.empty()) return; + PendPushTimer.startTimer(); for (auto &Update : Updates) if (Update.getFrom() != Update.getTo()) PendPoints.insert(Update.getFrom()); if (!PendPoints.empty()) NeedCalculate = true; + PendPushTimer.stopTimer(); return; } if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) { + if (isLazy()) + DeduplicateTimer.startTimer(); SmallVector Seen; for (const auto U : Updates) // For Lazy UpdateStrategy, avoid duplicates to applyLazyUpdate() to save @@ -408,20 +500,30 @@ if (Strategy == UpdateStrategy::Lazy) applyLazyUpdate(U.getKind(), U.getFrom(), U.getTo()); } + if (isLazy()) + DeduplicateTimer.stopTimer(); if (Strategy == UpdateStrategy::Lazy) return; + DTUApplyUpdatesTimer.startTimer(); if (DT) DT->applyUpdates(Seen); + DTUApplyUpdatesTimer.stopTimer(); + PDTUApplyUpdatesTimer.startTimer(); if (PDT) PDT->applyUpdates(Seen); + PDTUApplyUpdatesTimer.stopTimer(); return; } + DTUApplyUpdatesTimer.startTimer(); if (DT) DT->applyUpdates(Updates); + DTUApplyUpdatesTimer.stopTimer(); + PDTUApplyUpdatesTimer.startTimer(); if (PDT) PDT->applyUpdates(Updates); + PDTUApplyUpdatesTimer.stopTimer(); } DominatorTree &DomTreeUpdater::getDomTree() { @@ -460,19 +562,27 @@ if (isAuto()) { NeedCalculate = true; + PendPushTimer.startTimer(); PendPoints.insert(From); + PendPushTimer.stopTimer(); return; } if (Strategy == UpdateStrategy::Eager) { + DTUInsertEdgeTimer.startTimer(); if (DT) DT->insertEdge(From, To); + DTUInsertEdgeTimer.stopTimer(); + PDTUInsertEdgeTimer.startTimer(); if (PDT) PDT->insertEdge(From, To); + PDTUInsertEdgeTimer.stopTimer(); return; } + DeduplicateTimer.startTimer(); applyLazyUpdate(DominatorTree::Insert, From, To); + DeduplicateTimer.stopTimer(); } void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) { @@ -484,23 +594,34 @@ if (isAuto()) { NeedCalculate = true; + PendPushTimer.startTimer(); PendPoints.insert(From); + PendPushTimer.stopTimer(); return; } + DeduplicateTimer.startTimer(); if (!isUpdateValid({DominatorTree::Insert, From, To})) { + DeduplicateTimer.stopTimer(); return; } + DeduplicateTimer.stopTimer(); if (Strategy == UpdateStrategy::Eager) { + DTUInsertEdgeTimer.startTimer(); if (DT) DT->insertEdge(From, To); + DTUInsertEdgeTimer.stopTimer(); + PDTUInsertEdgeTimer.startTimer(); if (PDT) PDT->insertEdge(From, To); + PDTUInsertEdgeTimer.stopTimer(); return; } + DeduplicateTimer.startTimer(); applyLazyUpdate(DominatorTree::Insert, From, To); + DeduplicateTimer.stopTimer(); } void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) { @@ -519,19 +640,27 @@ if (isAuto()) { NeedCalculate = true; + PendPushTimer.startTimer(); PendPoints.insert(From); + PendPushTimer.stopTimer(); return; } if (Strategy == UpdateStrategy::Eager) { + DTUDeleteEdgeTimer.startTimer(); if (DT) DT->deleteEdge(From, To); + DTUDeleteEdgeTimer.stopTimer(); + PDTUDeleteEdgeTimer.startTimer(); if (PDT) PDT->deleteEdge(From, To); + PDTUDeleteEdgeTimer.stopTimer(); return; } + DeduplicateTimer.startTimer(); applyLazyUpdate(DominatorTree::Delete, From, To); + DeduplicateTimer.stopTimer(); } void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) { @@ -543,23 +672,34 @@ if (isAuto()) { NeedCalculate = true; + PendPushTimer.startTimer(); PendPoints.insert(From); + PendPushTimer.stopTimer(); return; } + DeduplicateTimer.startTimer(); if (!isUpdateValid({DominatorTree::Delete, From, To})) { + DeduplicateTimer.stopTimer(); return; } + DeduplicateTimer.stopTimer(); if (Strategy == UpdateStrategy::Eager) { + DTUDeleteEdgeTimer.startTimer(); if (DT) DT->deleteEdge(From, To); + DTUDeleteEdgeTimer.stopTimer(); + PDTUDeleteEdgeTimer.startTimer(); if (PDT) PDT->deleteEdge(From, To); + PDTUDeleteEdgeTimer.stopTimer(); return; } + DeduplicateTimer.startTimer(); applyLazyUpdate(DominatorTree::Delete, From, To); + DeduplicateTimer.stopTimer(); } void DomTreeUpdater::dropOutOfDateUpdates() { @@ -582,7 +722,9 @@ const auto B = PendUpdates.begin(); const auto E = PendUpdates.begin() + dropIndex; assert(B <= E && "Iterator out of range."); + DeduplicateTimer.startTimer(); PendUpdates.erase(B, E); + DeduplicateTimer.stopTimer(); // Calculate current index. PendDTUpdateIndex -= dropIndex; PendPDTUpdateIndex -= dropIndex; @@ -706,9 +848,13 @@ // diffCFG will reset NeedCalculate. auto Updates = diffCFG(); + DTUApplyUpdatesTimer.startTimer(); if (DT) DT->applyUpdates(Updates); + DTUApplyUpdatesTimer.stopTimer(); + PDTUApplyUpdatesTimer.startTimer(); if (PDT) PDT->applyUpdates(Updates); + PDTUApplyUpdatesTimer.stopTimer(); } } // namespace llvm