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

src/IceOperand.h

 //===- subzero/src/IceOperand.h - High-level operands -----------*- C++ -*-===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file declares the Operand class and its target-independent
@@ skipping 308 matching lines @@
 
 // LiveRange is a set of instruction number intervals representing
 // a variable's live range.  Generally there is one interval per basic
 // block where the variable is live, but adjacent intervals get
 // coalesced into a single interval.  LiveRange also includes a
 // weight, in case e.g. we want a live range to have higher weight
 // inside a loop.
 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;
 
   void reset() {
     Range.clear();
     Weight.setWeight(0);
     untrim();
   }
   void addSegment(InstNumberT Start, InstNumberT End);
 
   bool endsBefore(const LiveRange &Other) const;
   bool overlaps(const LiveRange &Other, bool UseTrimmed = false) const;
   bool overlapsInst(InstNumberT OtherBegin, bool UseTrimmed = false) const;
   bool containsValue(InstNumberT Value, bool IsDest) const;
   bool isEmpty() const { return Range.empty(); }
   InstNumberT getStart() const {
     return Range.empty() ? -1 : Range.begin()->first;
   }
 
   void untrim() { TrimmedBegin = Range.begin(); }
   void trim(InstNumberT Lower);
 
   RegWeight getWeight() const { return Weight; }
   void setWeight(const RegWeight &NewWeight) { Weight = NewWeight; }
   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.
   // Since the linear-scan algorithm always calls it as overlaps(Cur)
   // and Cur advances monotonically according to live range start, we
   // can optimize overlaps() by ignoring all segments that end before
   // the start of Cur's range.  The linear-scan code enables this by
   // calling trim() on the ranges of interest as Cur advances.  Note
   // that linear-scan also has to initialize TrimmedBegin at the
   // beginning by calling untrim().
@@ skipping 256 matching lines @@
 private:
   const Cfg *Func;
   MetadataKind Kind;
   std::vector<VariableTracking> Metadata;
   const static InstDefList NoDefinitions;
 };
 
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICEOPERAND_H