Subzero: Optimize a common live range overlap calculation.

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 280 matching lines @@
 bool operator==(const RegWeight &A, const RegWeight &B);
 
 // 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) {}
+  LiveRange() : Weight(0), IsNonpoints(false) {}
 
   void reset() {
     Range.clear();
     Weight.setWeight(0);

[jvoung (off chromium), 2014/10/04 05:06:34]

Seems like reset() should reset IsNonpoints ?

[Jim Stichnoth, 2014/10/04 12:44:08]

Done.

   }
   void addSegment(InstNumberT Start, InstNumberT End);
 
   bool endsBefore(const LiveRange &Other) const;
   bool overlaps(const LiveRange &Other) const;
   bool overlaps(InstNumberT OtherBegin) const;
   bool containsValue(InstNumberT Value) const;
   bool isEmpty() const { return Range.empty(); }
   InstNumberT getStart() const {
     return Range.empty() ? -1 : Range.begin()->first;
@@ skipping 12 matching lines @@
 
 private:
   typedef std::pair<InstNumberT, InstNumberT> RangeElementType;
 #ifdef USE_SET
   typedef std::set<RangeElementType> RangeType;
 #else
   typedef std::list<RangeElementType> RangeType;
 #endif
   RangeType Range;
   RegWeight Weight;
+  // IsNonpoints keeps track of whether the live range contains at
+  // least one interval where Start!=End.  If it is empty or has the
+  // form [x,x),[y,y),...,[z,z), then overlaps(InstNumberT) is
+  // trivially false.
+  bool IsNonpoints;
 };
 
 Ostream &operator<<(Ostream &Str, const LiveRange &L);
 
 // Variable represents an operand that is register-allocated or
 // stack-allocated.  If it is register-allocated, it will ultimately
 // have a non-negative RegNum field.
 class Variable : public Operand {
   Variable(const Variable &) = delete;
   Variable &operator=(const Variable &) = delete;
@@ skipping 211 matching lines @@
   const Cfg *Func;
   std::vector<VariableTracking> Metadata;
   const static InstDefList NoDefinitions;
   VariablesMetadata(const VariablesMetadata &) = delete;
   VariablesMetadata &operator=(const VariablesMetadata &) = delete;
 };
 
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICEOPERAND_H