Subzero: Use std::vector<> instead of std::list for live range segments.
This generally uses less memory and fewer allocations.
Also removes the commented-out alternative implementation using std::set<>, which would almost certainly never be a good idea here.
BUG= none
R=jvoung@chromium.org
Review URL: https://codereview.chromium.org/734053006
diff --git a/src/IceDefs.h b/src/IceDefs.h
index 5d9dd4c..25e761d 100644
--- a/src/IceDefs.h
+++ b/src/IceDefs.h
@@ -23,7 +23,6 @@
#include <limits>
#include <list>
#include <map>
-#include <set>
#include <string>
#include <vector>
#include "llvm/ADT/ArrayRef.h"
diff --git a/src/IceOperand.cpp b/src/IceOperand.cpp
index 3aaecac..d7ea10b 100644
--- a/src/IceOperand.cpp
+++ b/src/IceOperand.cpp
@@ -33,37 +33,6 @@
}
void LiveRange::addSegment(InstNumberT Start, InstNumberT End) {
-#ifdef USE_SET
- RangeElementType Element(Start, End);
- RangeType::iterator Next = Range.lower_bound(Element);
- assert(Next == Range.upper_bound(Element)); // Element not already present
-
- // Beginning of code that merges contiguous segments. TODO: change
- // "if(true)" to "if(false)" to see if this extra optimization code
- // gives any performance gain, or is just destabilizing.
- if (true) {
- RangeType::iterator FirstDelete = Next;
- RangeType::iterator Prev = Next;
- bool hasPrev = (Next != Range.begin());
- bool hasNext = (Next != Range.end());
- if (hasPrev)
- --Prev;
- // See if Element and Next should be joined.
- if (hasNext && End == Next->first) {
- Element.second = Next->second;
- ++Next;
- }
- // See if Prev and Element should be joined.
- if (hasPrev && Prev->second == Start) {
- Element.first = Prev->first;
- FirstDelete = Prev;
- }
- Range.erase(FirstDelete, Next);
- }
- // End of code that merges contiguous segments.
-
- Range.insert(Next, Element);
-#else
if (Range.empty()) {
Range.push_back(RangeElementType(Start, End));
return;
@@ -71,7 +40,10 @@
// Special case for faking in-arg liveness.
if (End < Range.front().first) {
assert(Start < 0);
- Range.push_front(RangeElementType(Start, End));
+ // This is inefficient with Range as a std::vector, but there are
+ // generally very few arguments compared to the total number of
+ // variables with non-empty live ranges.
+ Range.insert(Range.begin(), RangeElementType(Start, End));
return;
}
InstNumberT CurrentEnd = Range.back().second;
@@ -82,7 +54,6 @@
return;
}
Range.push_back(RangeElementType(Start, End));
-#endif
}
// Returns true if this live range ends before Other's live range
diff --git a/src/IceOperand.h b/src/IceOperand.h
index d477ae0..c99b9d7 100644
--- a/src/IceOperand.h
+++ b/src/IceOperand.h
@@ -326,6 +326,13 @@
class LiveRange {
public:
LiveRange() : Weight(0) {}
+ // Special constructor for building a kill set. The advantage is
+ // that we can reserve the right amount of space in advance.
+ LiveRange(const std::vector<InstNumberT> &Kills) : Weight(0) {
+ Range.reserve(Kills.size());
+ for (InstNumberT I : Kills)
+ addSegment(I, I);
+ }
LiveRange(const LiveRange &) = default;
LiveRange &operator=(const LiveRange &) = default;
@@ -353,19 +360,9 @@
void addWeight(uint32_t Delta) { Weight.addWeight(Delta); }
void dump(Ostream &Str) const;
- // Defining USE_SET uses std::set to hold the segments instead of
- // std::list. Using std::list will be slightly faster, but is more
- // restrictive because new segments cannot be added in the middle.
-
- //#define USE_SET
-
private:
typedef std::pair<InstNumberT, InstNumberT> RangeElementType;
-#ifdef USE_SET
- typedef std::set<RangeElementType> RangeType;
-#else
- typedef std::list<RangeElementType> RangeType;
-#endif
+ typedef std::vector<RangeElementType> RangeType;
RangeType Range;
RegWeight Weight;
// TrimmedBegin is an optimization for the overlaps() computation.
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index 8a1656b..bd4ca05 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -268,9 +268,7 @@
VariablesMetadata *VMetadata = Func->getVMetadata();
// Build a LiveRange representing the Kills list.
- LiveRange KillsRange;
- for (InstNumberT I : Kills)
- KillsRange.addSegment(I, I);
+ LiveRange KillsRange(Kills);
KillsRange.untrim();
// RegUses[I] is the number of live ranges (variables) that register
