From 9aa29a4c23d6d593f8aab15bdc26835558d84910 Mon Sep 17 00:00:00 2001 From: David Blaikie Date: Wed, 4 Mar 2015 01:15:53 +0000 Subject: [PATCH] Recommit r231175: Change LiveStackAnalysis::SS2IntervalMap from std::map to std::unordered_map The order of this container was needed at one point - so, at that point create a temporary array of pointers, sort those, then iterate them. This keeps lookup efficient (& the lesser issue, of allowing the use of emplace... ), object identity preserved, and ordered iteration in the one place that requires it. While this has no functional change, I realize it does mean allocating an extra data structure and performing a sort - so if this looks suspect to anyone regarding perf characteristics, I'm all ears. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@231189 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveStackAnalysis.h | 3 ++- lib/CodeGen/StackSlotColoring.cpp | 12 ++++++++++-- 2 files changed, 12 insertions(+), 3 deletions(-) diff --git a/include/llvm/CodeGen/LiveStackAnalysis.h b/include/llvm/CodeGen/LiveStackAnalysis.h index df683983fa5..f495507c66e 100644 --- a/include/llvm/CodeGen/LiveStackAnalysis.h +++ b/include/llvm/CodeGen/LiveStackAnalysis.h @@ -21,6 +21,7 @@ #include "llvm/Support/Allocator.h" #include "llvm/Target/TargetRegisterInfo.h" #include +#include namespace llvm { @@ -33,7 +34,7 @@ namespace llvm { /// S2IMap - Stack slot indices to live interval mapping. /// - typedef std::map SS2IntervalMap; + typedef std::unordered_map SS2IntervalMap; SS2IntervalMap S2IMap; /// S2RCMap - Stack slot indices to register class mapping. diff --git a/lib/CodeGen/StackSlotColoring.cpp b/lib/CodeGen/StackSlotColoring.cpp index cc72e5e51f2..a5a175f2c8f 100644 --- a/lib/CodeGen/StackSlotColoring.cpp +++ b/lib/CodeGen/StackSlotColoring.cpp @@ -184,10 +184,18 @@ void StackSlotColoring::InitializeSlots() { UsedColors.resize(LastFI); Assignments.resize(LastFI); + typedef std::iterator_traits::value_type Pair; + SmallVector Intervals; + Intervals.reserve(LS->getNumIntervals()); + for (auto &I : *LS) + Intervals.push_back(&I); + std::sort(Intervals.begin(), Intervals.end(), + [](Pair *LHS, Pair *RHS) { return LHS->first < RHS->first; }); + // Gather all spill slots into a list. DEBUG(dbgs() << "Spill slot intervals:\n"); - for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) { - LiveInterval &li = i->second; + for (auto *I : Intervals) { + LiveInterval &li = I->second; DEBUG(li.dump()); int FI = TargetRegisterInfo::stackSlot2Index(li.reg); if (MFI->isDeadObjectIndex(FI)) -- 2.34.1