From 31235e5b9494080153b545226864659206bff19b Mon Sep 17 00:00:00 2001 From: Lenny Maiorani Date: Sat, 20 Sep 2014 13:29:20 +0000 Subject: [PATCH] Using a deque to manage the stack of nodes is faster here. Vector is slow due to many reallocations as the size regularly changes in unpredictable ways. See the investigation provided on the mailing list for more information: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@218182 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/EarlyCSE.cpp | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) diff --git a/lib/Transforms/Scalar/EarlyCSE.cpp b/lib/Transforms/Scalar/EarlyCSE.cpp index 21ef34772d7..131a8cb3dcb 100644 --- a/lib/Transforms/Scalar/EarlyCSE.cpp +++ b/lib/Transforms/Scalar/EarlyCSE.cpp @@ -26,7 +26,7 @@ #include "llvm/Support/RecyclingAllocator.h" #include "llvm/Target/TargetLibraryInfo.h" #include "llvm/Transforms/Utils/Local.h" -#include +#include using namespace llvm; #define DEBUG_TYPE "early-cse" @@ -560,7 +560,11 @@ bool EarlyCSE::runOnFunction(Function &F) { if (skipOptnoneFunction(F)) return false; - std::vector nodesToProcess; + // Note, deque is being used here because there is significant performance gains + // over vector when the container becomes very large due to the specific access + // patterns. For more information see the mailing list discussion on this: + // http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html + std::deque nodesToProcess; DataLayoutPass *DLP = getAnalysisIfAvailable(); DL = DLP ? &DLP->getDataLayout() : nullptr; -- 2.34.1