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,40 @@ #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 +576,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 +602,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 +629,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 +815,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,16 +13,68 @@ //===----------------------------------------------------------------------===// #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); + bool DomTreeUpdater::isUpdateValid( const DominatorTree::UpdateType Update) const { + ++NumInvalidPruned; const auto *From = Update.getFrom(); const auto *To = Update.getTo(); const auto Kind = Update.getKind(); @@ -44,7 +96,7 @@ // Edge exists in IR. if (Kind == DominatorTree::Delete && HasEdge) return false; - + --NumInvalidPruned; return true; } @@ -74,17 +126,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; } @@ -99,7 +154,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(); } } @@ -121,7 +178,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(); } } @@ -155,10 +214,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; } @@ -171,10 +238,18 @@ // Because all trees are going to be up-to-date after recalculation, // flush awaiting deleted BasicBlocks. forceFlushDeletedBB(); - 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; @@ -283,17 +358,25 @@ 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() { @@ -325,10 +408,14 @@ 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; } @@ -346,10 +433,14 @@ 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; } @@ -371,10 +462,14 @@ 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; } @@ -392,10 +487,14 @@ 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; }