From 6a590737355e82d83729198715e3fff11b0c6f9e Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Tue, 3 Jul 2012 13:46:45 +0000 Subject: [PATCH] Part of r159527. Splitted into series of patches and gone with fixed PR13256: IntegersSubsetMapping - Replaced type of Items field from std::list with std::map. In neares future I'll test it with DenseMap and do the correspond replacement if possible. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159659 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubsetMapping.h | 36 +++---------------- .../SelectionDAG/SelectionDAGBuilder.cpp | 15 ++++---- lib/Transforms/Utils/LowerSwitch.cpp | 9 ++--- 3 files changed, 18 insertions(+), 42 deletions(-) diff --git a/include/llvm/Support/IntegersSubsetMapping.h b/include/llvm/Support/IntegersSubsetMapping.h index 458adbe2223..eb434cd285c 100644 --- a/include/llvm/Support/IntegersSubsetMapping.h +++ b/include/llvm/Support/IntegersSubsetMapping.h @@ -58,22 +58,15 @@ public: protected: - typedef std::list CaseItems; + typedef std::map CaseItems; typedef typename CaseItems::iterator CaseItemIt; typedef typename CaseItems::const_iterator CaseItemConstIt; // TODO: Change unclean CRS prefixes to SubsetMap for example. typedef std::map CRSMap; typedef typename CRSMap::iterator CRSMapIt; - - struct ClustersCmp { - bool operator()(const Cluster &C1, const Cluster &C2) { - return C1.first < C2.first; - } - }; CaseItems Items; - bool Sorted; bool SingleNumbersOnly; bool isIntersected(CaseItemIt& LItem, CaseItemIt& RItem) { @@ -92,18 +85,6 @@ protected: return LItem->first.getHigh() >= RLow; } - void sort() { - if (!Sorted) { - std::vector clustersVector; - clustersVector.reserve(Items.size()); - clustersVector.insert(clustersVector.begin(), Items.begin(), Items.end()); - std::sort(clustersVector.begin(), clustersVector.end(), ClustersCmp()); - Items.clear(); - Items.insert(Items.begin(), clustersVector.begin(), clustersVector.end()); - Sorted = true; - } - } - enum DiffProcessState { L_OPENED, INTERSECT_OPENED, @@ -300,15 +281,11 @@ public: typedef std::pair Case; typedef std::list Cases; - IntegersSubsetMapping() { - Sorted = false; - SingleNumbersOnly = true; - } + IntegersSubsetMapping() : SingleNumbersOnly(true) {} bool verify(RangeIterator& errItem) { if (Items.empty()) return true; - sort(); for (CaseItemIt j = Items.begin(), i = j++, e = Items.end(); j != e; i = j++) { if (isIntersected(i, j) && i->second != j->second) { @@ -318,11 +295,10 @@ public: } return true; } - + void optimize() { if (Items.size() < 2) return; - sort(); CaseItems OldItems = Items; Items.clear(); const IntTy *Low = &OldItems.begin()->first.getLow(); @@ -347,8 +323,6 @@ public: } RangeEx R(*Low, *High, Weight); add(R, Successor); - // We recollected the Items, but we kept it sorted. - Sorted = true; } /// Adds a constant value. @@ -367,7 +341,7 @@ public: add(REx, S); } void add(const RangeEx &R, SuccessorClass *S = 0) { - Items.push_back(std::make_pair(R, S)); + Items.insert(std::make_pair(R, S)); if (!R.isSingleNumber()) SingleNumbersOnly = false; } @@ -382,7 +356,7 @@ public: } void add(self& RHS) { - Items.insert(Items.end(), RHS.Items.begin(), RHS.Items.end()); + Items.insert(RHS.Items.begin(), RHS.Items.end()); if (!RHS.SingleNumbersOnly) SingleNumbersOnly = false; } diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index 42b9099cdc3..2d074079ccf 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -2450,22 +2450,23 @@ size_t SelectionDAGBuilder::Clusterify(CaseVector& Cases, size_t numCmps = 0; for (Clusterifier::RangeIterator i = TheClusterifier.begin(), e = TheClusterifier.end(); i != e; ++i, ++numCmps) { - Clusterifier::Cluster &C = *i; + const Clusterifier::RangeEx &R = i->first; + MachineBasicBlock *MBB = i->second; unsigned W = 0; if (BPI) { - W = BPI->getEdgeWeight(SI.getParent(), C.second->getBasicBlock()); + W = BPI->getEdgeWeight(SI.getParent(), MBB->getBasicBlock()); if (!W) W = 16; - W *= C.first.Weight; - BPI->setEdgeWeight(SI.getParent(), C.second->getBasicBlock(), W); + W *= R.Weight; + BPI->setEdgeWeight(SI.getParent(), MBB->getBasicBlock(), W); } // FIXME: Currently work with ConstantInt based numbers. // Changing it to APInt based is a pretty heavy for this commit. - Cases.push_back(Case(C.first.getLow().toConstantInt(), - C.first.getHigh().toConstantInt(), C.second, W)); + Cases.push_back(Case(R.getLow().toConstantInt(), + R.getHigh().toConstantInt(), MBB, W)); - if (C.first.getLow() != C.first.getHigh()) + if (R.getLow() != R.getHigh()) // A range counts double, since it requires two compares. ++numCmps; } diff --git a/lib/Transforms/Utils/LowerSwitch.cpp b/lib/Transforms/Utils/LowerSwitch.cpp index 1547439b5c6..d2bd9d02846 100644 --- a/lib/Transforms/Utils/LowerSwitch.cpp +++ b/lib/Transforms/Utils/LowerSwitch.cpp @@ -238,13 +238,14 @@ unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { size_t numCmps = 0; for (IntegersSubsetToBB::RangeIterator i = TheClusterifier.begin(), e = TheClusterifier.end(); i != e; ++i, ++numCmps) { - IntegersSubsetToBB::Cluster &C = *i; + const IntegersSubsetToBB::RangeTy &R = i->first; + BasicBlock *S = i->second; // FIXME: Currently work with ConstantInt based numbers. // Changing it to APInt based is a pretty heavy for this commit. - Cases.push_back(CaseRange(C.first.getLow().toConstantInt(), - C.first.getHigh().toConstantInt(), C.second)); - if (C.first.isSingleNumber()) + Cases.push_back(CaseRange(R.getLow().toConstantInt(), + R.getHigh().toConstantInt(), S)); + if (R.isSingleNumber()) // A range counts double, since it requires two compares. ++numCmps; } -- 2.34.1