From 5d0d1e350a30772fd70798b5733bb060febd7b0d Mon Sep 17 00:00:00 2001 From: Alkis Evlogimenos Date: Wed, 8 Sep 2004 03:01:50 +0000 Subject: [PATCH] Use a DenseMap for mapping reg->reg. This improves the LiveInterval analysis running time from 2.7869secs to 2.5226secs on 176.gcc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16244 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveIntervalAnalysis.h | 13 +++++++------ lib/CodeGen/LiveIntervalAnalysis.cpp | 8 +++++--- lib/CodeGen/LiveIntervalAnalysis.h | 13 +++++++------ 3 files changed, 19 insertions(+), 15 deletions(-) diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 73d730a647e..b90be627041 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -20,6 +20,7 @@ #ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H #define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H +#include "llvm/ADT/DenseMap.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "LiveInterval.h" @@ -44,7 +45,7 @@ namespace llvm { typedef std::map Reg2IntervalMap; Reg2IntervalMap r2iMap_; - typedef std::map Reg2RegMap; + typedef DenseMap Reg2RegMap; Reg2RegMap r2rMap_; std::vector allocatableRegs_; @@ -171,11 +172,11 @@ namespace llvm { } /// rep - returns the representative of this register - unsigned rep(unsigned reg) { - Reg2RegMap::iterator it = r2rMap_.find(reg); - if (it != r2rMap_.end()) - return it->second = rep(it->second); - return reg; + unsigned rep(unsigned Reg) { + unsigned Rep = r2rMap_[Reg]; + if (Rep) + return r2rMap_[Reg] = rep(Rep); + return Reg; } void printRegName(unsigned reg) const; diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 3ebd9075860..e0fefc3870f 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -619,6 +619,8 @@ namespace { void LiveIntervals::joinIntervals() { DEBUG(std::cerr << "********** JOINING INTERVALS ***********\n"); + // reserve space for the reg2reg map + r2rMap_.grow(mf_->getSSARegMap()->getLastVirtReg()); const LoopInfo &LI = getAnalysis(); if (LI.begin() == LI.end()) { @@ -644,9 +646,9 @@ void LiveIntervals::joinIntervals() { } DEBUG(std::cerr << "*** Register mapping ***\n"); - DEBUG(for (std::map::iterator I = r2rMap_.begin(), - E = r2rMap_.end(); I != E; ++I) - std::cerr << " reg " << I->first << " -> reg " << I->second << "\n";); + DEBUG(for (int i = 0, e = r2rMap_.size(); i != e; ++i) + if (r2rMap_[i]) + std::cerr << " reg " << i << " -> reg " << r2rMap_[i] << "\n"); } /// Return true if the two specified registers belong to different register diff --git a/lib/CodeGen/LiveIntervalAnalysis.h b/lib/CodeGen/LiveIntervalAnalysis.h index 73d730a647e..b90be627041 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.h +++ b/lib/CodeGen/LiveIntervalAnalysis.h @@ -20,6 +20,7 @@ #ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H #define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H +#include "llvm/ADT/DenseMap.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "LiveInterval.h" @@ -44,7 +45,7 @@ namespace llvm { typedef std::map Reg2IntervalMap; Reg2IntervalMap r2iMap_; - typedef std::map Reg2RegMap; + typedef DenseMap Reg2RegMap; Reg2RegMap r2rMap_; std::vector allocatableRegs_; @@ -171,11 +172,11 @@ namespace llvm { } /// rep - returns the representative of this register - unsigned rep(unsigned reg) { - Reg2RegMap::iterator it = r2rMap_.find(reg); - if (it != r2rMap_.end()) - return it->second = rep(it->second); - return reg; + unsigned rep(unsigned Reg) { + unsigned Rep = r2rMap_[Reg]; + if (Rep) + return r2rMap_[Reg] = rep(Rep); + return Reg; } void printRegName(unsigned reg) const; -- 2.34.1