Subzero: Use std::vector<> instead of std::list for live range segments.

src/IceOperand.cpp

 //===- subzero/src/IceOperand.cpp - High-level operand implementation -----===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the Operand class and its target-independent
@@ skipping 15 matching lines @@
 
 bool operator<(const RegWeight &A, const RegWeight &B) {
   return A.getWeight() < B.getWeight();
 }
 bool operator<=(const RegWeight &A, const RegWeight &B) { return !(B < A); }
 bool operator==(const RegWeight &A, const RegWeight &B) {
   return !(B < A) && !(A < B);
 }
 
 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;
   }
   // 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;
   assert(Start >= CurrentEnd);
   // Check for merge opportunity.
   if (Start == CurrentEnd) {
     Range.back().second = End;
     return;
   }
   Range.push_back(RangeElementType(Start, End));
-#endif
 }
 
 // Returns true if this live range ends before Other's live range
 // starts.  This means that the highest instruction number in this
 // live range is less than or equal to the lowest instruction number
 // of the Other live range.
 bool LiveRange::endsBefore(const LiveRange &Other) const {
   // Neither range should be empty, but let's be graceful.
   if (Range.empty() || Other.Range.empty())
     return true;
@@ skipping 420 matching lines @@
   if (!ALLOW_DUMP)
     return Str;
   if (W.getWeight() == RegWeight::Inf)
     Str << "Inf";
   else
     Str << W.getWeight();
   return Str;
 }
 
 } // end of namespace Ice