From 88997ba27f0c9974e9e0907f528c2bbe67bed9c1 Mon Sep 17 00:00:00 2001 From: Andrea Di Biagio Date: Wed, 16 May 2018 12:33:09 +0000 Subject: [PATCH] [llvm-mca] Fix perf regression after r332390. Revision 332390 introduced a FetchStage class in llvm-mca. By design, FetchStage owns all the instructions in-flight in the OoO Backend. Before this change, new instructions were added to a DenseMap indexed by instruction id. The problem with using a DenseMap is that elements are not ordered by key. This was causing a massive slow down in method FetchStage::postExecute(), which searches for instructions retired that can be deleted. This patch replaces the DenseMap with a std::map ordered by instruction index. At the end of every cycle, we search for the first instruction which is not marked as "retired", and we remove all the previous instructions before it. This works well because instructions are retired in-order. Before this patch, a debug build of llvm-mca (on my Ryzen linux machine) took ~8.0 seconds to simulate 3000 iterations of a x86 dot-product (a `vmulps, vpermilps, vaddps, vpermilps, vaddps` sequence). With this patch, it now takes ~0.8s to run all the 3000 iterations. llvm-svn: 332461 --- llvm/tools/llvm-mca/FetchStage.cpp | 10 +++++++--- llvm/tools/llvm-mca/FetchStage.h | 6 ++---- 2 files changed, 9 insertions(+), 7 deletions(-) diff --git a/llvm/tools/llvm-mca/FetchStage.cpp b/llvm/tools/llvm-mca/FetchStage.cpp index b582b4e..a1da841 100644 --- a/llvm/tools/llvm-mca/FetchStage.cpp +++ b/llvm/tools/llvm-mca/FetchStage.cpp @@ -31,8 +31,12 @@ bool FetchStage::execute(InstRef &IR) { } void FetchStage::postExecute(const InstRef &IR) { - // Reclaim instructions that have been retired. - llvm::remove_if(Instructions, - [](InstMapPr &Pr) { return Pr.getSecond()->isRetired(); }); + // Find the first instruction which hasn't been retired. + const InstMap::iterator It = + llvm::find_if(Instructions, [](const InstMap::value_type &KeyValuePair) { + return !KeyValuePair.second->isRetired(); + }); + if (It != Instructions.begin()) + Instructions.erase(Instructions.begin(), It); SM.updateNext(); } diff --git a/llvm/tools/llvm-mca/FetchStage.h b/llvm/tools/llvm-mca/FetchStage.h index 93de961..687c597 100644 --- a/llvm/tools/llvm-mca/FetchStage.h +++ b/llvm/tools/llvm-mca/FetchStage.h @@ -20,14 +20,12 @@ #include "Instruction.h" #include "SourceMgr.h" #include "Stage.h" -#include "llvm/ADT/DenseMap.h" +#include namespace mca { class FetchStage : public Stage { - using InstMap = llvm::DenseMap>; - using InstMapPr = - llvm::detail::DenseMapPair>; + using InstMap = std::map>; InstMap Instructions; InstrBuilder &IB; SourceMgr &SM; -- 2.7.4