Index: include/llvm/IR/DomTreeUpdater.h =================================================================== --- include/llvm/IR/DomTreeUpdater.h +++ include/llvm/IR/DomTreeUpdater.h @@ -15,6 +15,7 @@ #ifndef LLVM_DOMTREEUPDATER_H #define LLVM_DOMTREEUPDATER_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,17 @@ /// \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 +601,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 +628,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 +814,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,74 @@ //===----------------------------------------------------------------------===// #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 DiffTimer("Diff", "Diff", DTUTimerGroup); +static Timer DeduplicateTimer("Deduplicate", "Deduplicate", DTUTimerGroup); + bool DomTreeUpdater::isUpdateValid( const DominatorTree::UpdateType Update) const { #ifdef NDEBUG assert(!isAuto() && "Auto UpdateStrategy should not go into this function."); #endif + ++NumInvalidPruned; const auto *From = Update.getFrom(); const auto *To = Update.getTo(); const auto Kind = Update.getKind(); @@ -47,12 +102,13 @@ // Edge exists in IR. if (Kind == DominatorTree::Delete && HasEdge) return false; - + --NumInvalidPruned; return true; } std::vector DomTreeUpdater::diffCFG(CFG &PrevCFG, CFG &NewCFG) { + DiffTimer.startTimer(); CFG DiffCFG; std::vector Updates; std::set_difference(PrevCFG.begin(), PrevCFG.end(), NewCFG.begin(), @@ -68,6 +124,7 @@ for (auto &Edge : DiffCFG) if (Edge.first != Edge.second) // Discard self dominance. Updates.push_back({DominatorTree::Insert, Edge.first, Edge.second}); + DiffTimer.stopTimer(); return Updates; } @@ -88,6 +145,7 @@ SnapshotedBB = &Func->getEntryBlock(); // Do the full snapshot. + SnapshotTimer.startTimer(); Graph.clear(); for (BasicBlock &BB : Func->getBasicBlockList()) for (auto *Addr : successors(&BB)) @@ -95,6 +153,7 @@ // Deduplicate llvm::sort(Graph.begin(), Graph.end()); Graph.erase(std::unique(Graph.begin(), Graph.end()), Graph.end()); + SnapshotTimer.stopTimer(); } bool DomTreeUpdater::isSelfDominance( @@ -123,17 +182,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; } @@ -148,7 +210,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(); } } @@ -173,7 +237,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(); } } @@ -207,10 +273,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; } @@ -231,27 +305,35 @@ applyAutoUpdates(); return; } - } - if (DT) - DT->recalculate(F); - if (PDT) - PDT->recalculate(F); + 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; + // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes. + IsRecalculatingDomTree = IsRecalculatingPostDomTree = false; - if (!isAuto()) - PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size(); + if (!isAuto()) + PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size(); - dropOutOfDateUpdates(); + dropOutOfDateUpdates(); - if (isAuto()) { - // The tree is updated. - snapshotCFG(SnapshotedCFG); - NeedCalculate = false; + if (isAuto()) { + // The tree is updated. + snapshotCFG(SnapshotedCFG); + NeedCalculate = false; } } +} bool DomTreeUpdater::hasPendingUpdates() const { return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates(); @@ -367,6 +449,8 @@ } 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 @@ -379,20 +463,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() { @@ -436,14 +530,20 @@ } 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) { @@ -459,19 +559,28 @@ 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) { @@ -495,14 +604,20 @@ } 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) { @@ -518,19 +633,28 @@ 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() { @@ -543,6 +667,7 @@ if (isAuto()) return; + DeduplicateTimer.startTimer(); // Drop all updates applied by both trees. if (!DT) PendDTUpdateIndex = PendUpdates.size(); @@ -559,6 +684,7 @@ // Calculate current index. PendDTUpdateIndex -= dropIndex; PendPDTUpdateIndex -= dropIndex; + DeduplicateTimer.stopTimer(); } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) @@ -683,9 +809,13 @@ snapshotCFG(CurrentCFG); auto Updates = diffCFG(SnapshotedCFG, CurrentCFG); SnapshotedCFG = std::move(CurrentCFG); + DTUApplyUpdatesTimer.startTimer(); if (DT) DT->applyUpdates(Updates); + DTUApplyUpdatesTimer.stopTimer(); + PDTUApplyUpdatesTimer.startTimer(); if (PDT) PDT->applyUpdates(Updates); + PDTUApplyUpdatesTimer.stopTimer(); } } // namespace llvm