Rename LiveRange to LiveInterval::Segment

The Segment struct contains a single interval; multiple instances of this struct
are used to construct a live range, but the struct is not a live range by
itself.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@192392 91177308-0d34-0410-b5e6-96231b3b80d8

13 files changed, 242 insertions, 240 deletions

diff --git a/lib/CodeGen/InlineSpiller.cpp b/lib/CodeGen/InlineSpiller.cpp
index 13db5f44cb..2ee67555a6 100644
--- a/lib/CodeGen/InlineSpiller.cpp
+++ b/lib/CodeGen/InlineSpiller.cpp
@@ -1295,8 +1295,8 @@ void InlineSpiller::spillAll() {
 
   assert(StackInt->getNumValNums() == 1 && "Bad stack interval values");
   for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i)
-    StackInt->MergeRangesInAsValue(LIS.getInterval(RegsToSpill[i]),
-                                   StackInt->getValNumInfo(0));
+    StackInt->MergeSegmentsInAsValue(LIS.getInterval(RegsToSpill[i]),
+                                     StackInt->getValNumInfo(0));
   DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n');
 
   // Spill around uses of all RegsToSpill.
diff --git a/lib/CodeGen/LiveDebugVariables.cpp b/lib/CodeGen/LiveDebugVariables.cpp
index 4b8395bae7..c1f6fd57de 100644
--- a/lib/CodeGen/LiveDebugVariables.cpp
+++ b/lib/CodeGen/LiveDebugVariables.cpp
@@ -510,14 +510,14 @@ void UserValue::extendDef(SlotIndex Idx, unsigned LocNo,
     // Limit to VNI's live range.
     bool ToEnd = true;
     if (LI && VNI) {
-      LiveRange *Range = LI->getLiveRangeContaining(Start);
-      if (!Range || Range->valno != VNI) {
+      LiveInterval::Segment *Segment = LI->getSegmentContaining(Start);
+      if (!Segment || Segment->valno != VNI) {
         if (Kills)
           Kills->push_back(Start);
         continue;
       }
-      if (Range->end < Stop)
-        Stop = Range->end, ToEnd = false;
+      if (Segment->end < Stop)
+        Stop = Segment->end, ToEnd = false;
     }
 
     // There could already be a short def at Start.
diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index 2d5f781ff1..2b72825b49 100644
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -7,14 +7,14 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// This file implements the LiveRange and LiveInterval classes.  Given some
+// This file implements the LiveInterval class.  Given some
 // numbering of each the machine instructions an interval [i, j) is said to be a
 // live interval for register v if there is no instruction with number j' > j
 // such that v is live at j' and there is no instruction with number i' < i such
 // that v is live at i'. In this implementation intervals can have holes,
 // i.e. an interval might look like [1,20), [50,65), [1000,1001).  Each
-// individual range is represented as an instance of LiveRange, and the whole
-// interval is represented as an instance of LiveInterval.
+// individual segment is represented as an instance of Segment, and the whole
+// range is represented as an instance of LiveInterval.
 //
 //===----------------------------------------------------------------------===//
 
@@ -55,7 +55,7 @@ VNInfo *LiveInterval::createDeadDef(SlotIndex Def,
   iterator I = find(Def);
   if (I == end()) {
     VNInfo *VNI = getNextValue(Def, VNInfoAllocator);
-    ranges.push_back(LiveRange(Def, Def.getDeadSlot(), VNI));
+    segments.push_back(Segment(Def, Def.getDeadSlot(), VNI));
     return VNI;
   }
   if (SlotIndex::isSameInstr(Def, I->start)) {
@@ -73,7 +73,7 @@ VNInfo *LiveInterval::createDeadDef(SlotIndex Def,
   }
   assert(SlotIndex::isEarlierInstr(Def, I->start) && "Already live at def");
   VNInfo *VNI = getNextValue(Def, VNInfoAllocator);
-  ranges.insert(I, LiveRange(Def, Def.getDeadSlot(), VNI));
+  segments.insert(I, Segment(Def, Def.getDeadSlot(), VNI));
   return VNI;
 }
 
@@ -178,7 +178,7 @@ bool LiveInterval::overlaps(const LiveInterval &Other,
   }
 }
 
-/// overlaps - Return true if the live interval overlaps a range specified
+/// overlaps - Return true if the live interval overlaps a segment specified
 /// by [Start, End).
 bool LiveInterval::overlaps(SlotIndex Start, SlotIndex End) const {
   assert(Start < End && "Invalid range");
@@ -209,129 +209,128 @@ void LiveInterval::RenumberValues() {
     VNInfo *VNI = I->valno;
     if (!Seen.insert(VNI))
       continue;
-    assert(!VNI->isUnused() && "Unused valno used by live range");
+    assert(!VNI->isUnused() && "Unused valno used by live segment");
     VNI->id = (unsigned)valnos.size();
     valnos.push_back(VNI);
   }
 }
 
-/// extendIntervalEndTo - This method is used when we want to extend the range
-/// specified by I to end at the specified endpoint.  To do this, we should
-/// merge and eliminate all ranges that this will overlap with.  The iterator is
-/// not invalidated.
-void LiveInterval::extendIntervalEndTo(iterator I, SlotIndex NewEnd) {
-  assert(I != end() && "Not a valid interval!");
+/// This method is used when we want to extend the segment specified by I to end
+/// at the specified endpoint.  To do this, we should merge and eliminate all
+/// segments that this will overlap with.  The iterator is not invalidated.
+void LiveInterval::extendSegmentEndTo(iterator I, SlotIndex NewEnd) {
+  assert(I != end() && "Not a valid segment!");
   VNInfo *ValNo = I->valno;
 
-  // Search for the first interval that we can't merge with.
+  // Search for the first segment that we can't merge with.
   iterator MergeTo = llvm::next(I);
   for (; MergeTo != end() && NewEnd >= MergeTo->end; ++MergeTo) {
     assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
   }
 
-  // If NewEnd was in the middle of an interval, make sure to get its endpoint.
+  // If NewEnd was in the middle of an segment, make sure to get its endpoint.
   I->end = std::max(NewEnd, prior(MergeTo)->end);
 
-  // If the newly formed range now touches the range after it and if they have
-  // the same value number, merge the two ranges into one range.
+  // If the newly formed segment now touches the segment after it and if they
+  // have the same value number, merge the two segments into one segment.
   if (MergeTo != end() && MergeTo->start <= I->end &&
       MergeTo->valno == ValNo) {
     I->end = MergeTo->end;
     ++MergeTo;
   }
 
-  // Erase any dead ranges.
-  ranges.erase(llvm::next(I), MergeTo);
+  // Erase any dead segments.
+  segments.erase(llvm::next(I), MergeTo);
 }
 
 
-/// extendIntervalStartTo - This method is used when we want to extend the range
-/// specified by I to start at the specified endpoint.  To do this, we should
-/// merge and eliminate all ranges that this will overlap with.
+/// This method is used when we want to extend the segment specified by I to
+/// start at the specified endpoint.  To do this, we should merge and eliminate
+/// all segments that this will overlap with.
 LiveInterval::iterator
-LiveInterval::extendIntervalStartTo(iterator I, SlotIndex NewStart) {
-  assert(I != end() && "Not a valid interval!");
+LiveInterval::extendSegmentStartTo(iterator I, SlotIndex NewStart) {
+  assert(I != end() && "Not a valid segment!");
   VNInfo *ValNo = I->valno;
 
-  // Search for the first interval that we can't merge with.
+  // Search for the first segment that we can't merge with.
   iterator MergeTo = I;
   do {
     if (MergeTo == begin()) {
       I->start = NewStart;
-      ranges.erase(MergeTo, I);
+      segments.erase(MergeTo, I);
       return I;
     }
     assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
     --MergeTo;
   } while (NewStart <= MergeTo->start);
 
-  // If we start in the middle of another interval, just delete a range and
-  // extend that interval.
+  // If we start in the middle of another segment, just delete a range and
+  // extend that segment.
   if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) {
     MergeTo->end = I->end;
   } else {
-    // Otherwise, extend the interval right after.
+    // Otherwise, extend the segment right after.
     ++MergeTo;
     MergeTo->start = NewStart;
     MergeTo->end = I->end;
   }
 
-  ranges.erase(llvm::next(MergeTo), llvm::next(I));
+  segments.erase(llvm::next(MergeTo), llvm::next(I));
   return MergeTo;
 }
 
 LiveInterval::iterator
-LiveInterval::addRangeFrom(LiveRange LR, iterator From) {
-  SlotIndex Start = LR.start, End = LR.end;
+LiveInterval::addSegmentFrom(Segment S, iterator From) {
+  SlotIndex Start = S.start, End = S.end;
   iterator it = std::upper_bound(From, end(), Start);
 
-  // If the inserted interval starts in the middle or right at the end of
-  // another interval, just extend that interval to contain the range of LR.
+  // If the inserted segment starts in the middle or right at the end of
+  // another segment, just extend that segment to contain the segment of S.
   if (it != begin()) {
     iterator B = prior(it);
-    if (LR.valno == B->valno) {
+    if (S.valno == B->valno) {
       if (B->start <= Start && B->end >= Start) {
-        extendIntervalEndTo(B, End);
+        extendSegmentEndTo(B, End);
         return B;
       }
     } else {
-      // Check to make sure that we are not overlapping two live ranges with
+      // Check to make sure that we are not overlapping two live segments with
       // different valno's.
       assert(B->end <= Start &&
-             "Cannot overlap two LiveRanges with differing ValID's"
+             "Cannot overlap two segments with differing ValID's"
              " (did you def the same reg twice in a MachineInstr?)");
     }
   }
 
-  // Otherwise, if this range ends in the middle of, or right next to, another
-  // interval, merge it into that interval.
+  // Otherwise, if this segment ends in the middle of, or right next to, another
+  // segment, merge it into that segment.
   if (it != end()) {
-    if (LR.valno == it->valno) {
+    if (S.valno == it->valno) {
       if (it->start <= End) {
-        it = extendIntervalStartTo(it, Start);
+        it = extendSegmentStartTo(it, Start);
 
-        // If LR is a complete superset of an interval, we may need to grow its
+        // If S is a complete superset of a segment, we may need to grow its
         // endpoint as well.
         if (End > it->end)
-          extendIntervalEndTo(it, End);
+          extendSegmentEndTo(it, End);
         return it;
       }
     } else {
-      // Check to make sure that we are not overlapping two live ranges with
+      // Check to make sure that we are not overlapping two live segments with
       // different valno's.
       assert(it->start >= End &&
-             "Cannot overlap two LiveRanges with differing ValID's");
+             "Cannot overlap two segments with differing ValID's");
     }
   }
 
-  // Otherwise, this is just a new range that doesn't interact with anything.
+  // Otherwise, this is just a new segment that doesn't interact with anything.
   // Insert it.
-  return ranges.insert(it, LR);
+  return segments.insert(it, S);
 }
 
 /// extendInBlock - If this interval is live before Kill in the basic
 /// block that starts at StartIdx, extend it to be live up to Kill and return
-/// the value. If there is no live range before Kill, return NULL.
+/// the value. If there is no segment before Kill, return NULL.
 VNInfo *LiveInterval::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) {
   if (empty())
     return 0;
@@ -342,20 +341,21 @@ VNInfo *LiveInterval::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) {
   if (I->end <= StartIdx)
     return 0;
   if (I->end < Kill)
-    extendIntervalEndTo(I, Kill);
+    extendSegmentEndTo(I, Kill);
   return I->valno;
 }
 
-/// removeRange - Remove the specified range from this interval.  Note that
-/// the range must be in a single LiveRange in its entirety.
-void LiveInterval::removeRange(SlotIndex Start, SlotIndex End,
-                               bool RemoveDeadValNo) {
-  // Find the LiveRange containing this span.
+/// Remove the specified segment from this interval.  Note that the segment must
+/// be in a single Segment in its entirety.
+void LiveInterval::removeSegment(SlotIndex Start, SlotIndex End,
+                                 bool RemoveDeadValNo) {
+  // Find the Segment containing this span.
   iterator I = find(Start);
-  assert(I != end() && "Range is not in interval!");
-  assert(I->containsRange(Start, End) && "Range is not entirely in interval!");
+  assert(I != end() && "Segment is not in interval!");
+  assert(I->containsInterval(Start, End)
+         && "Segment is not entirely in interval!");
 
-  // If the span we are removing is at the start of the LiveRange, adjust it.
+  // If the span we are removing is at the start of the Segment, adjust it.
   VNInfo *ValNo = I->valno;
   if (I->start == Start) {
     if (I->end == End) {
@@ -373,28 +373,28 @@ void LiveInterval::removeRange(SlotIndex Start, SlotIndex End,
         }
       }
 
-      ranges.erase(I);  // Removed the whole LiveRange.
+      segments.erase(I);  // Removed the whole Segment.
     } else
       I->start = End;
     return;
   }
 
-  // Otherwise if the span we are removing is at the end of the LiveRange,
+  // Otherwise if the span we are removing is at the end of the Segment,
   // adjust the other way.
   if (I->end == End) {
     I->end = Start;
     return;
   }
 
-  // Otherwise, we are splitting the LiveRange into two pieces.
+  // Otherwise, we are splitting the Segment into two pieces.
   SlotIndex OldEnd = I->end;
   I->end = Start;   // Trim the old interval.
 
   // Insert the new one.
-  ranges.insert(llvm::next(I), LiveRange(End, OldEnd, ValNo));
+  segments.insert(llvm::next(I), Segment(End, OldEnd, ValNo));
 }
 
-/// removeValNo - Remove all the ranges defined by the specified value#.
+/// removeValNo - Remove all the segments defined by the specified value#.
 /// Also remove the value# from value# list.
 void LiveInterval::removeValNo(VNInfo *ValNo) {
   if (empty()) return;
@@ -403,7 +403,7 @@ void LiveInterval::removeValNo(VNInfo *ValNo) {
   do {
     --I;
     if (I->valno == ValNo)
-      ranges.erase(I);
+      segments.erase(I);
   } while (I != E);
   // Now that ValNo is dead, remove it.
   markValNoForDeletion(ValNo);
@@ -418,8 +418,8 @@ void LiveInterval::join(LiveInterval &Other,
                         SmallVectorImpl<VNInfo *> &NewVNInfo) {
   verify();
 
-  // Determine if any of our live range values are mapped.  This is uncommon, so
-  // we want to avoid the interval scan if not.
+  // Determine if any of our values are mapped.  This is uncommon, so we want
+  // to avoid the interval scan if not.
   bool MustMapCurValNos = false;
   unsigned NumVals = getNumValNums();
   unsigned NumNewVals = NewVNInfo.size();
@@ -444,7 +444,7 @@ void LiveInterval::join(LiveInterval &Other,
       assert(nextValNo != 0 && "Huh?");
 
       // If this live range has the same value # as its immediate predecessor,
-      // and if they are neighbors, remove one LiveRange.  This happens when we
+      // and if they are neighbors, remove one Segment.  This happens when we
       // have [0,4:0)[4,7:1) and map 0/1 onto the same value #.
       if (OutIt->valno == nextValNo && OutIt->end == I->start) {
         OutIt->end = I->end;
@@ -458,9 +458,9 @@ void LiveInterval::join(LiveInterval &Other,
         }
       }
     }
-    // If we merge some live ranges, chop off the end.
+    // If we merge some segments, chop off the end.
     ++OutIt;
-    ranges.erase(OutIt, end());
+    segments.erase(OutIt, end());
   }
 
   // Rewrite Other values before changing the VNInfo ids.
@@ -486,28 +486,28 @@ void LiveInterval::join(LiveInterval &Other,
   if (NumNewVals < NumVals)
     valnos.resize(NumNewVals);  // shrinkify
 
-  // Okay, now insert the RHS live ranges into the LHS.
+  // Okay, now insert the RHS live segments into the LHS.
   LiveRangeUpdater Updater(this);
   for (iterator I = Other.begin(), E = Other.end(); I != E; ++I)
     Updater.add(*I);
 }
 
-/// MergeRangesInAsValue - Merge all of the intervals in RHS into this live
-/// interval as the specified value number.  The LiveRanges in RHS are
-/// allowed to overlap with LiveRanges in the current interval, but only if
-/// the overlapping LiveRanges have the specified value number.
-void LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS,
-                                        VNInfo *LHSValNo) {
+/// Merge all of the segments in RHS into this live interval as the specified
+/// value number.  The segments in RHS are allowed to overlap with segments in
+/// the current interval, but only if the overlapping segments have the
+/// specified value number.
+void LiveInterval::MergeSegmentsInAsValue(const LiveInterval &RHS,
+                                          VNInfo *LHSValNo) {
   LiveRangeUpdater Updater(this);
   for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I)
     Updater.add(I->start, I->end, LHSValNo);
 }
 
-/// MergeValueInAsValue - Merge all of the live ranges of a specific val#
+/// MergeValueInAsValue - Merge all of the live segments of a specific val#
 /// in RHS into this live interval as the specified value number.
-/// The LiveRanges in RHS are allowed to overlap with LiveRanges in the
+/// The segments in RHS are allowed to overlap with segments in the
 /// current interval, it will replace the value numbers of the overlaped
-/// live ranges with the specified value number.
+/// segments with the specified value number.
 void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS,
                                        const VNInfo *RHSValNo,
                                        VNInfo *LHSValNo) {
@@ -519,7 +519,7 @@ void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS,
 
 /// MergeValueNumberInto - This method is called when two value nubmers
 /// are found to be equivalent.  This eliminates V1, replacing all
-/// LiveRanges with the V1 value number with the V2 value number.  This can
+/// segments with the V1 value number with the V2 value number.  This can
 /// cause merging of V1/V2 values numbers and compaction of the value space.
 VNInfo* LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) {
   assert(V1 != V2 && "Identical value#'s are always equivalent!");
@@ -535,37 +535,37 @@ VNInfo* LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) {
     std::swap(V1, V2);
   }
 
-  // Merge V1 live ranges into V2.
+  // Merge V1 segments into V2.
   for (iterator I = begin(); I != end(); ) {
-    iterator LR = I++;
-    if (LR->valno != V1) continue;  // Not a V1 LiveRange.
+    iterator S = I++;
+    if (S->valno != V1) continue;  // Not a V1 Segment.
 
     // Okay, we found a V1 live range.  If it had a previous, touching, V2 live
     // range, extend it.
-    if (LR != begin()) {
-      iterator Prev = LR-1;
-      if (Prev->valno == V2 && Prev->end == LR->start) {
-        Prev->end = LR->end;
+    if (S != begin()) {
+      iterator Prev = S-1;
+      if (Prev->valno == V2 && Prev->end == S->start) {
+        Prev->end = S->end;
 
         // Erase this live-range.
-        ranges.erase(LR);
+        segments.erase(S);
         I = Prev+1;
-        LR = Prev;
+        S = Prev;
       }
     }
 
     // Okay, now we have a V1 or V2 live range that is maximally merged forward.
     // Ensure that it is a V2 live-range.
-    LR->valno = V2;
+    S->valno = V2;
 
-    // If we can merge it into later V2 live ranges, do so now.  We ignore any
-    // following V1 live ranges, as they will be merged in subsequent iterations
+    // If we can merge it into later V2 segments, do so now.  We ignore any
+    // following V1 segments, as they will be merged in subsequent iterations
     // of the loop.
     if (I != end()) {
-      if (I->start == LR->end && I->valno == V2) {
-        LR->end = I->end;
-        ranges.erase(I);
-        I = LR+1;
+      if (I->start == S->end && I->valno == V2) {
+        S->end = I->end;
+        segments.erase(I);
+        I = S+1;
       }
     }
   }
@@ -583,12 +583,12 @@ unsigned LiveInterval::getSize() const {
   return Sum;
 }
 
-raw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange &LR) {
-  return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")";
+raw_ostream& llvm::operator<<(raw_ostream& os, const LiveInterval::Segment &S) {
+  return os << '[' << S.start << ',' << S.end << ':' << S.valno->id << ")";
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-void LiveRange::dump() const {
+void LiveInterval::Segment::dump() const {
   dbgs() << *this << "\n";
 }
 #endif
@@ -647,10 +647,6 @@ void LiveInterval::verify() const {
 #endif
 
 
-void LiveRange::print(raw_ostream &os) const {
-  os << *this;
-}
-
 //===----------------------------------------------------------------------===//
 //                           LiveRangeUpdater class
 //===----------------------------------------------------------------------===//
@@ -709,8 +705,9 @@ void LiveRangeUpdater::dump() const
 }
 
 // Determine if A and B should be coalesced.
-static inline bool coalescable(const LiveRange &A, const LiveRange &B) {
-  assert(A.start <= B.start && "Unordered live ranges.");
+static inline bool coalescable(const LiveInterval::Segment &A,
+                               const LiveInterval::Segment &B) {
+  assert(A.start <= B.start && "Unordered live segments.");
   if (A.end == B.start)
     return A.valno == B.valno;
   if (A.end < B.start)
@@ -719,7 +716,7 @@ static inline bool coalescable(const LiveRange &A, const LiveRange &B) {
   return true;
 }
 
-void LiveRangeUpdater::add(LiveRange Seg) {
+void LiveRangeUpdater::add(LiveInterval::Segment Seg) {
   assert(LI && "Cannot add to a null destination");
 
   // Flush the state if Start moves backwards.
@@ -788,7 +785,7 @@ void LiveRangeUpdater::add(LiveRange Seg) {
 
   // Finally, append to LI or Spills.
   if (WriteI == E) {
-    LI->ranges.push_back(Seg);
+    LI->segments.push_back(Seg);
     WriteI = ReadI = LI->end();
   } else
     Spills.push_back(Seg);
@@ -829,7 +826,7 @@ void LiveRangeUpdater::flush() {
 
   // Nothing to merge?
   if (Spills.empty()) {
-    LI->ranges.erase(WriteI, ReadI);
+    LI->segments.erase(WriteI, ReadI);
     LI->verify();
     return;
   }
@@ -839,12 +836,13 @@ void LiveRangeUpdater::flush() {
   if (GapSize < Spills.size()) {
     // The gap is too small. Make some room.
     size_t WritePos = WriteI - LI->begin();
-    LI->ranges.insert(ReadI, Spills.size() - GapSize, LiveRange());
+    LI->segments.insert(ReadI, Spills.size() - GapSize,
+                        LiveInterval::Segment());
     // This also invalidated ReadI, but it is recomputed below.
     WriteI = LI->begin() + WritePos;
   } else {
     // Shrink the gap if necessary.
-    LI->ranges.erase(WriteI + Spills.size(), ReadI);
+    LI->segments.erase(WriteI + Spills.size(), ReadI);
   }
   ReadI = WriteI + Spills.size();
   mergeSpills();
@@ -933,11 +931,11 @@ void ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[],
     if (unsigned eq = EqClass[I->valno->id]) {
       assert((LIV[eq]->empty() || LIV[eq]->expiredAt(I->start)) &&
              "New intervals should be empty");
-      LIV[eq]->ranges.push_back(*I);
+      LIV[eq]->segments.push_back(*I);
     } else
       *J++ = *I;
   }
-  LI.ranges.erase(J, E);
+  LI.segments.erase(J, E);
 
   // Transfer VNInfos to their new owners and renumber them.
   unsigned j = 0, e = LI.getNumValNums();
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index dd22a47b56..1c1b1f72d1 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -355,7 +355,8 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li,
     VNInfo *VNI = *I;
     if (VNI->isUnused())
       continue;
-    NewLI.addRange(LiveRange(VNI->def, VNI->def.getDeadSlot(), VNI));
+    NewLI.addSegment(LiveInterval::Segment(VNI->def, VNI->def.getDeadSlot(),
+                                           VNI));
   }
 
   // Keep track of the PHIs that are in use.
@@ -391,7 +392,7 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li,
 
     // VNI is live-in to MBB.
     DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
-    NewLI.addRange(LiveRange(BlockStart, Idx, VNI));
+    NewLI.addSegment(LiveInterval::Segment(BlockStart, Idx, VNI));
 
     // Make sure VNI is live-out from the predecessors.
     for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
@@ -412,14 +413,14 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li,
     VNInfo *VNI = *I;
     if (VNI->isUnused())
       continue;
-    LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def);
-    assert(LII != NewLI.end() && "Missing live range for PHI");
+    LiveInterval::iterator LII = NewLI.FindSegmentContaining(VNI->def);
+    assert(LII != NewLI.end() && "Missing segment for PHI");
     if (LII->end != VNI->def.getDeadSlot())
       continue;
     if (VNI->isPHIDef()) {
       // This is a dead PHI. Remove it.
       VNI->markUnused();
-      NewLI.removeRange(*LII);
+      NewLI.removeSegment(*LII);
       DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
       CanSeparate = true;
     } else {
@@ -434,8 +435,8 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li,
     }
   }
 
-  // Move the trimmed ranges back.
-  li->ranges.swap(NewLI.ranges);
+  // Move the trimmed segments back.
+  li->segments.swap(NewLI.segments);
   DEBUG(dbgs() << "Shrunk: " << *li << '\n');
   return CanSeparate;
 }
@@ -461,13 +462,13 @@ void LiveIntervals::pruneValue(LiveInterval *LI, SlotIndex Kill,
 
   // If VNI isn't live out from KillMBB, the value is trivially pruned.
   if (LRQ.endPoint() < MBBEnd) {
-    LI->removeRange(Kill, LRQ.endPoint());
+    LI->removeSegment(Kill, LRQ.endPoint());
     if (EndPoints) EndPoints->push_back(LRQ.endPoint());
     return;
   }
 
   // VNI is live out of KillMBB.
-  LI->removeRange(Kill, MBBEnd);
+  LI->removeSegment(Kill, MBBEnd);
   if (EndPoints) EndPoints->push_back(MBBEnd);
 
   // Find all blocks that are reachable from KillMBB without leaving VNI's live
@@ -487,21 +488,21 @@ void LiveIntervals::pruneValue(LiveInterval *LI, SlotIndex Kill,
       tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);
       LiveRangeQuery LRQ(*LI, MBBStart);
       if (LRQ.valueIn() != VNI) {
-        // This block isn't part of the VNI live range. Prune the search.
+        // This block isn't part of the VNI segment. Prune the search.
         I.skipChildren();
         continue;
       }
 
       // Prune the search if VNI is killed in MBB.
       if (LRQ.endPoint() < MBBEnd) {
-        LI->removeRange(MBBStart, LRQ.endPoint());
+        LI->removeSegment(MBBStart, LRQ.endPoint());
         if (EndPoints) EndPoints->push_back(LRQ.endPoint());
         I.skipChildren();
         continue;
       }
 
       // VNI is live through MBB.
-      LI->removeRange(MBBStart, MBBEnd);
+      LI->removeSegment(MBBStart, MBBEnd);
       if (EndPoints) EndPoints->push_back(MBBEnd);
       ++I;
     }
@@ -535,7 +536,8 @@ void LiveIntervals::addKillFlags(const VirtRegMap *VRM) {
       RU.push_back(std::make_pair(RUInt, RUInt->find(LI->begin()->end)));
     }
 
-    // Every instruction that kills Reg corresponds to a live range end point.
+    // Every instruction that kills Reg corresponds to a segment range end
+    // point.
     for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE;
          ++RI) {
       // A block index indicates an MBB edge.
@@ -623,18 +625,18 @@ LiveIntervals::getSpillWeight(bool isDef, bool isUse, BlockFrequency freq) {
   return (isDef + isUse) * (freq.getFrequency() * Scale);
 }
 
-LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
-                                                  MachineInstr* startInst) {
+LiveInterval::Segment
+LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr* startInst) {
   LiveInterval& Interval = createEmptyInterval(reg);
   VNInfo* VN = Interval.getNextValue(
     SlotIndex(getInstructionIndex(startInst).getRegSlot()),
     getVNInfoAllocator());
-  LiveRange LR(
+  LiveInterval::Segment S(
      SlotIndex(getInstructionIndex(startInst).getRegSlot()),
      getMBBEndIdx(startInst->getParent()), VN);
-  Interval.addRange(LR);
+  Interval.addSegment(S);
 
-  return LR;
+  return S;
 }
 
 
@@ -798,7 +800,7 @@ private:
   ///    Move def to NewIdx, possibly across another live value.
   ///
   /// 4. Def at OldIdx AND at NewIdx:
-  ///    Remove live range [OldIdx;NewIdx) and value defined at OldIdx.
+  ///    Remove segment [OldIdx;NewIdx) and value defined at OldIdx.
   ///    (Happens when bundling multiple defs together).
   ///
   /// 5. Value read at OldIdx, killed before NewIdx:
@@ -868,7 +870,8 @@ private:
     // intermediate ranges up.
     assert(NewI != I && "Inconsistent iterators");
     std::copy(llvm::next(I), NewI, I);
-    *llvm::prior(NewI) = LiveRange(DefVNI->def, NewIdx.getDeadSlot(), DefVNI);
+    *llvm::prior(NewI)
+      = LiveInterval::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI);
   }
 
   /// Update LI to reflect an instruction has been moved upwards from OldIdx
@@ -949,7 +952,7 @@ private:
     // DefVNI is a dead def. It may have been moved across other values in LI,
     // so move I up to NewI. Slide [NewI;I) down one position.
     std::copy_backward(NewI, I, llvm::next(I));
-    *NewI = LiveRange(DefVNI->def, NewIdx.getDeadSlot(), DefVNI);
+    *NewI = LiveInterval::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI);
   }
 
   void updateRegMaskSlots() {
@@ -1119,9 +1122,9 @@ LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB,
               if (LII != LI.begin())
                 prevStart = llvm::prior(LII)->start;
 
-              // FIXME: This could be more efficient if there was a removeRange
-              // method that returned an iterator.
-              LI.removeRange(*LII, true);
+              // FIXME: This could be more efficient if there was a
+              // removeSegment method that returned an iterator.
+              LI.removeSegment(*LII, true);
               if (prevStart.isValid())
                 LII = LI.find(prevStart);
               else
@@ -1140,13 +1143,14 @@ LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB,
           if (!lastUseIdx.isValid()) {
             VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(),
                                           VNInfoAllocator);
-            LiveRange LR(instrIdx.getRegSlot(), instrIdx.getDeadSlot(), VNI);
-            LII = LI.addRange(LR);
+            LiveInterval::Segment S(instrIdx.getRegSlot(),
+                                    instrIdx.getDeadSlot(), VNI);
+            LII = LI.addSegment(S);
           } else if (LII->start != instrIdx.getRegSlot()) {
             VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(),
                                           VNInfoAllocator);
-            LiveRange LR(instrIdx.getRegSlot(), lastUseIdx, VNI);
-            LII = LI.addRange(LR);
+            LiveInterval::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI);
+            LII = LI.addSegment(S);
           }
 
           if (MO.getSubReg() && !MO.isUndef())
diff --git a/lib/CodeGen/LiveRangeCalc.cpp b/lib/CodeGen/LiveRangeCalc.cpp
index dede490d91..bd9c8d0301 100644
--- a/lib/CodeGen/LiveRangeCalc.cpp
+++ b/lib/CodeGen/LiveRangeCalc.cpp
@@ -355,9 +355,9 @@ void LiveRangeCalc::updateSSA() {
 
         // Add liveness since updateLiveIns now skips this node.
         if (I->Kill.isValid())
-          I->LI->addRange(LiveRange(Start, I->Kill, VNI));
+          I->LI->addSegment(LiveInterval::Segment(Start, I->Kill, VNI));
         else {
-          I->LI->addRange(LiveRange(Start, End, VNI));
+          I->LI->addSegment(LiveInterval::Segment(Start, End, VNI));
           LOP = LiveOutPair(VNI, Node);
         }
       } else if (IDomValue.first) {
diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp
index 5633271712..ca71e3bf80 100644
--- a/lib/CodeGen/MachineBasicBlock.cpp
+++ b/lib/CodeGen/MachineBasicBlock.cpp
@@ -861,7 +861,7 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) {
           LiveInterval &LI = LIS->getInterval(Reg);
           VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
           assert(VNI && "PHI sources should be live out of their predecessors.");
-          LI.addRange(LiveRange(StartIndex, EndIndex, VNI));
+          LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
         }
       }
     }
@@ -880,9 +880,9 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) {
       if (isLiveOut && isLastMBB) {
         VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
         assert(VNI && "LiveInterval should have VNInfo where it is live.");
-        LI.addRange(LiveRange(StartIndex, EndIndex, VNI));
+        LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
       } else if (!isLiveOut && !isLastMBB) {
-        LI.removeRange(StartIndex, EndIndex);
+        LI.removeSegment(StartIndex, EndIndex);
       }
     }
 
diff --git a/lib/CodeGen/MachineVerifier.cpp b/lib/CodeGen/MachineVerifier.cpp
index a3c49de5cc..e3c4432581 100644
--- a/lib/CodeGen/MachineVerifier.cpp
+++ b/lib/CodeGen/MachineVerifier.cpp
@@ -1004,7 +1004,7 @@ void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) {
           if (const LiveInterval *LI = LiveInts->getCachedRegUnit(*Units)) {
             LiveRangeQuery LRQ(*LI, UseIdx);
             if (!LRQ.valueIn()) {
-              report("No live range at use", MO, MONum);
+              report("No live segment at use", MO, MONum);
               *OS << UseIdx << " is not live in " << PrintRegUnit(*Units, TRI)
                   << ' ' << *LI << '\n';
             }
@@ -1022,7 +1022,7 @@ void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) {
           const LiveInterval &LI = LiveInts->getInterval(Reg);
           LiveRangeQuery LRQ(LI, UseIdx);
           if (!LRQ.valueIn()) {
-            report("No live range at use", MO, MONum);
+            report("No live segment at use", MO, MONum);
             *OS << UseIdx << " is not live in " << LI << '\n';
           }
           // Check for extra kill flags.
@@ -1071,7 +1071,7 @@ void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) {
         llvm::next(MRI->def_begin(Reg)) != MRI->def_end())
       report("Multiple virtual register defs in SSA form", MO, MONum);
 
-    // Check LiveInts for a live range, but only for virtual registers.
+    // Check LiveInts for a live segment, but only for virtual registers.
     if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) &&
         !LiveInts->isNotInMIMap(MI)) {
       SlotIndex DefIdx = LiveInts->getInstructionIndex(MI);
@@ -1086,7 +1086,7 @@ void MachineVerifier::checkLiveness(const MachineOperand *MO, unsigned MONum) {
               << DefIdx << " in " << LI << '\n';
           }
         } else {
-          report("No live range at def", MO, MONum);
+          report("No live segment at def", MO, MONum);
           *OS << DefIdx << " is not live in " << LI << '\n';
         }
       } else {
@@ -1353,7 +1353,7 @@ void MachineVerifier::verifyLiveIntervalValue(const LiveInterval &LI,
   }
 
   if (DefVNI != VNI) {
-    report("Live range at def has different valno", MF, LI);
+    report("Live segment at def has different valno", MF, LI);
     *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
         << " where valno #" << DefVNI->id << " is live\n";
     return;
@@ -1425,15 +1425,15 @@ void
 MachineVerifier::verifyLiveIntervalSegment(const LiveInterval &LI,
                                            LiveInterval::const_iterator I) {
   const VNInfo *VNI = I->valno;
-  assert(VNI && "Live range has no valno");
+  assert(VNI && "Live segment has no valno");
 
   if (VNI->id >= LI.getNumValNums() || VNI != LI.getValNumInfo(VNI->id)) {
-    report("Foreign valno in live range", MF, LI);
+    report("Foreign valno in live segment", MF, LI);
     *OS << *I << " has a bad valno\n";
   }
 
   if (VNI->isUnused()) {
-    report("Live range valno is marked unused", MF, LI);
+    report("Live segment valno is marked unused", MF, LI);
     *OS << *I << '\n';
   }
 
@@ -1503,7 +1503,7 @@ MachineVerifier::verifyLiveIntervalSegment(const LiveInterval &LI,
   // The following checks only apply to virtual registers. Physreg liveness
   // is too weird to check.
   if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
-    // A live range can end with either a redefinition, a kill flag on a
+    // A live segment can end with either a redefinition, a kill flag on a
     // use, or a dead flag on a def.
     bool hasRead = false;
     bool hasDeadDef = false;
@@ -1519,12 +1519,11 @@ MachineVerifier::verifyLiveIntervalSegment(const LiveInterval &LI,
     if (I->end.isDead()) {
       if (!hasDeadDef) {
         report("Instruction doesn't have a dead def operand", MI);
-        I->print(*OS);
-        *OS << " in " << LI << '\n';
+        *OS << *I << " in " << LI << '\n';
       }
     } else {
       if (!hasRead) {
-        report("Instruction ending live range doesn't read the register", MI);
+        report("Instruction ending live segment doesn't read the register", MI);
         *OS << *I << " in " << LI << '\n';
       }
     }
@@ -1532,7 +1531,7 @@ MachineVerifier::verifyLiveIntervalSegment(const LiveInterval &LI,
 
   // Now check all the basic blocks in this live segment.
   MachineFunction::const_iterator MFI = MBB;
-  // Is this live range the beginning of a non-PHIDef VN?
+  // Is this live segment the beginning of a non-PHIDef VN?
   if (I->start == VNI->def && !VNI->isPHIDef()) {
     // Not live-in to any blocks.
     if (MBB == EndMBB)
diff --git a/lib/CodeGen/PHIElimination.cpp b/lib/CodeGen/PHIElimination.cpp
index e6ffb714aa..dcd9072295 100644
--- a/lib/CodeGen/PHIElimination.cpp
+++ b/lib/CodeGen/PHIElimination.cpp
@@ -318,9 +318,9 @@ void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
       if (!IncomingVNI)
         IncomingVNI = IncomingLI.getNextValue(MBBStartIndex,
                                               LIS->getVNInfoAllocator());
-      IncomingLI.addRange(LiveRange(MBBStartIndex,
-                                    DestCopyIndex.getRegSlot(),
-                                    IncomingVNI));
+      IncomingLI.addSegment(LiveInterval::Segment(MBBStartIndex,
+                                                  DestCopyIndex.getRegSlot(),
+                                                  IncomingVNI));
     }
 
     LiveInterval &DestLI = LIS->getInterval(DestReg);
@@ -332,14 +332,14 @@ void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
       // the copy instruction.
       VNInfo *OrigDestVNI = DestLI.getVNInfoAt(MBBStartIndex);
       assert(OrigDestVNI && "PHI destination should be live at block entry.");
-      DestLI.removeRange(MBBStartIndex, MBBStartIndex.getDeadSlot());
+      DestLI.removeSegment(MBBStartIndex, MBBStartIndex.getDeadSlot());
       DestLI.createDeadDef(DestCopyIndex.getRegSlot(),
                            LIS->getVNInfoAllocator());
       DestLI.removeValNo(OrigDestVNI);
     } else {
       // Otherwise, remove the region from the beginning of MBB to the copy
       // instruction from DestReg's live interval.
-      DestLI.removeRange(MBBStartIndex, DestCopyIndex.getRegSlot());
+      DestLI.removeSegment(MBBStartIndex, DestCopyIndex.getRegSlot());
       VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot());
       assert(DestVNI && "PHI destination should be live at its definition.");
       DestVNI->def = DestCopyIndex.getRegSlot();
@@ -460,7 +460,7 @@ void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
     if (LIS) {
       if (NewSrcInstr) {
         LIS->InsertMachineInstrInMaps(NewSrcInstr);
-        LIS->addLiveRangeToEndOfBlock(IncomingReg, NewSrcInstr);
+        LIS->addSegmentToEndOfBlock(IncomingReg, NewSrcInstr);
       }
 
       if (!SrcUndef &&
@@ -511,8 +511,8 @@ void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
                  "Cannot find kill instruction");
 
           SlotIndex LastUseIndex = LIS->getInstructionIndex(KillInst);
-          SrcLI.removeRange(LastUseIndex.getRegSlot(),
-                            LIS->getMBBEndIdx(&opBlock));
+          SrcLI.removeSegment(LastUseIndex.getRegSlot(),
+                              LIS->getMBBEndIdx(&opBlock));
         }
       }
     }
diff --git a/lib/CodeGen/RegisterCoalescer.cpp b/lib/CodeGen/RegisterCoalescer.cpp
index 4c992617d4..ef54663987 100644
--- a/lib/CodeGen/RegisterCoalescer.cpp
+++ b/lib/CodeGen/RegisterCoalescer.cpp
@@ -436,9 +436,9 @@ bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP,
 
   // BValNo is a value number in B that is defined by a copy from A.  'B1' in
   // the example above.
-  LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
-  if (BLR == IntB.end()) return false;
-  VNInfo *BValNo = BLR->valno;
+  LiveInterval::iterator BS = IntB.FindSegmentContaining(CopyIdx);
+  if (BS == IntB.end()) return false;
+  VNInfo *BValNo = BS->valno;
 
   // Get the location that B is defined at.  Two options: either this value has
   // an unknown definition point or it is defined at CopyIdx.  If unknown, we
@@ -447,10 +447,10 @@ bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP,
 
   // AValNo is the value number in A that defines the copy, A3 in the example.
   SlotIndex CopyUseIdx = CopyIdx.getRegSlot(true);
-  LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx);
-  // The live range might not exist after fun with physreg coalescing.
-  if (ALR == IntA.end()) return false;
-  VNInfo *AValNo = ALR->valno;
+  LiveInterval::iterator AS = IntA.FindSegmentContaining(CopyUseIdx);
+  // The live segment might not exist after fun with physreg coalescing.
+  if (AS == IntA.end()) return false;
+  VNInfo *AValNo = AS->valno;
 
   // If AValNo is defined as a copy from IntB, we can potentially process this.
   // Get the instruction that defines this value number.
@@ -459,54 +459,54 @@ bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP,
   if (!CP.isCoalescable(ACopyMI) || !ACopyMI->isFullCopy())
     return false;
 
-  // Get the LiveRange in IntB that this value number starts with.
-  LiveInterval::iterator ValLR =
-    IntB.FindLiveRangeContaining(AValNo->def.getPrevSlot());
-  if (ValLR == IntB.end())
+  // Get the Segment in IntB that this value number starts with.
+  LiveInterval::iterator ValS =
+    IntB.FindSegmentContaining(AValNo->def.getPrevSlot());
+  if (ValS == IntB.end())
     return false;
 
-  // Make sure that the end of the live range is inside the same block as
+  // Make sure that the end of the live segment is inside the same block as
   // CopyMI.
-  MachineInstr *ValLREndInst =
-    LIS->getInstructionFromIndex(ValLR->end.getPrevSlot());
-  if (!ValLREndInst || ValLREndInst->getParent() != CopyMI->getParent())
+  MachineInstr *ValSEndInst =
+    LIS->getInstructionFromIndex(ValS->end.getPrevSlot());
+  if (!ValSEndInst || ValSEndInst->getParent() != CopyMI->getParent())
     return false;
 
-  // Okay, we now know that ValLR ends in the same block that the CopyMI
-  // live-range starts.  If there are no intervening live ranges between them in
-  // IntB, we can merge them.
-  if (ValLR+1 != BLR) return false;
+  // Okay, we now know that ValS ends in the same block that the CopyMI
+  // live-range starts.  If there are no intervening live segments between them
+  // in IntB, we can merge them.
+  if (ValS+1 != BS) return false;
 
   DEBUG(dbgs() << "Extending: " << PrintReg(IntB.reg, TRI));
 
-  SlotIndex FillerStart = ValLR->end, FillerEnd = BLR->start;
+  SlotIndex FillerStart = ValS->end, FillerEnd = BS->start;
   // We are about to delete CopyMI, so need to remove it as the 'instruction
   // that defines this value #'. Update the valnum with the new defining
   // instruction #.
   BValNo->def = FillerStart;
 
   // Okay, we can merge them.  We need to insert a new liverange:
-  // [ValLR.end, BLR.begin) of either value number, then we merge the
+  // [ValS.end, BS.begin) of either value number, then we merge the
   // two value numbers.
-  IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo));
+  IntB.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, BValNo));
 
   // Okay, merge "B1" into the same value number as "B0".
-  if (BValNo != ValLR->valno)
-    IntB.MergeValueNumberInto(BValNo, ValLR->valno);
+  if (BValNo != ValS->valno)
+    IntB.MergeValueNumberInto(BValNo, ValS->valno);
   DEBUG(dbgs() << "   result = " << IntB << '\n');
 
   // If the source instruction was killing the source register before the
   // merge, unset the isKill marker given the live range has been extended.
-  int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true);
+  int UIdx = ValSEndInst->findRegisterUseOperandIdx(IntB.reg, true);
   if (UIdx != -1) {
-    ValLREndInst->getOperand(UIdx).setIsKill(false);
+    ValSEndInst->getOperand(UIdx).setIsKill(false);
   }
 
   // Rewrite the copy. If the copy instruction was killing the destination
   // register before the merge, find the last use and trim the live range. That
   // will also add the isKill marker.
   CopyMI->substituteRegister(IntA.reg, IntB.reg, 0, *TRI);
-  if (ALR->end == CopyIdx)
+  if (AS->end == CopyIdx)
     LIS->shrinkToUses(&IntA);
 
   ++numExtends;
@@ -627,8 +627,8 @@ bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP,
        UE = MRI->use_nodbg_end(); UI != UE; ++UI) {
     MachineInstr *UseMI = &*UI;
     SlotIndex UseIdx = LIS->getInstructionIndex(UseMI);
-    LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
-    if (ULR == IntA.end() || ULR->valno != AValNo)
+    LiveInterval::iterator US = IntA.FindSegmentContaining(UseIdx);
+    if (US == IntA.end() || US->valno != AValNo)
       continue;
     // If this use is tied to a def, we can't rewrite the register.
     if (UseMI->isRegTiedToDefOperand(UI.getOperandNo()))
@@ -679,8 +679,8 @@ bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP,
       continue;
     }
     SlotIndex UseIdx = LIS->getInstructionIndex(UseMI).getRegSlot(true);
-    LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
-    if (ULR == IntA.end() || ULR->valno != AValNo)
+    LiveInterval::iterator US = IntA.FindSegmentContaining(UseIdx);
+    if (US == IntA.end() || US->valno != AValNo)
       continue;
     // Kill flags are no longer accurate. They are recomputed after RA.
     UseMO.setIsKill(false);
@@ -710,14 +710,14 @@ bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP,
     UseMI->eraseFromParent();
   }
 
-  // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition
+  // Extend BValNo by merging in IntA live segments of AValNo. Val# definition
   // is updated.
   VNInfo *ValNo = BValNo;
   ValNo->def = AValNo->def;
   for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
        AI != AE; ++AI) {
     if (AI->valno != AValNo) continue;
-    IntB.addRange(LiveRange(AI->start, AI->end, ValNo));
+    IntB.addSegment(LiveInterval::Segment(AI->start, AI->end, ValNo));
   }
   DEBUG(dbgs() << "\t\textended: " << IntB << '\n');
 
@@ -1107,7 +1107,8 @@ bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) {
     if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
       return true;
 
-    // If we can eliminate the copy without merging the live ranges, do so now.
+    // If we can eliminate the copy without merging the live segments, do so
+    // now.
     if (!CP.isPartial() && !CP.isPhys()) {
       if (adjustCopiesBackFrom(CP, CopyMI) ||
           removeCopyByCommutingDef(CP, CopyMI)) {
diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index be1bfa0d6a..b17b644b70 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -214,7 +214,7 @@ bool SplitAnalysis::calcLiveBlockInfo() {
 
       // When not live in, the first use should be a def.
       if (!BI.LiveIn) {
-        assert(LVI->start == LVI->valno->def && "Dangling LiveRange start");
+        assert(LVI->start == LVI->valno->def && "Dangling Segment start");
         assert(LVI->start == BI.FirstInstr && "First instr should be a def");
         BI.FirstDef = BI.FirstInstr;
       }
@@ -245,8 +245,8 @@ bool SplitAnalysis::calcLiveBlockInfo() {
           BI.FirstInstr = BI.FirstDef = LVI->start;
         }
 
-        // A LiveRange that starts in the middle of the block must be a def.
-        assert(LVI->start == LVI->valno->def && "Dangling LiveRange start");
+        // A Segment that starts in the middle of the block must be a def.
+        assert(LVI->start == LVI->valno->def && "Dangling Segment start");
         if (!BI.FirstDef)
           BI.FirstDef = LVI->start;
       }
@@ -395,14 +395,14 @@ VNInfo *SplitEditor::defValue(unsigned RegIdx,
   // If the previous value was a simple mapping, add liveness for it now.
   if (VNInfo *OldVNI = InsP.first->second.getPointer()) {
     SlotIndex Def = OldVNI->def;
-    LI->addRange(LiveRange(Def, Def.getDeadSlot(), OldVNI));
+    LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), OldVNI));
     // No longer a simple mapping.  Switch to a complex, non-forced mapping.
     InsP.first->second = ValueForcePair();
   }
 
   // This is a complex mapping, add liveness for VNI
   SlotIndex Def = VNI->def;
-  LI->addRange(LiveRange(Def, Def.getDeadSlot(), VNI));
+  LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI));
 
   return VNI;
 }
@@ -423,7 +423,7 @@ void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI) {
   // by a trivial live range.
   SlotIndex Def = VNI->def;
   LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
-  LI->addRange(LiveRange(Def, Def.getDeadSlot(), VNI));
+  LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI));
   // Mark as complex mapped, forced.
   VFP = ValueForcePair(0, true);
 }
@@ -868,7 +868,7 @@ bool SplitEditor::transferValues() {
       ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));
       if (VNInfo *VNI = VFP.getPointer()) {
         DEBUG(dbgs() << ':' << VNI->id);
-        LI->addRange(LiveRange(Start, End, VNI));
+        LI->addSegment(LiveInterval::Segment(Start, End, VNI));
         Start = End;
         continue;
       }
diff --git a/lib/CodeGen/StackColoring.cpp b/lib/CodeGen/StackColoring.cpp
index 1bbaea2237..3dbc0508aa 100644
--- a/lib/CodeGen/StackColoring.cpp
+++ b/lib/CodeGen/StackColoring.cpp
@@ -450,14 +450,14 @@ void StackColoring::calculateLiveIntervals(unsigned NumSlots) {
       SlotIndex F = Finishes[i];
       if (S < F) {
         // We have a single consecutive region.
-        Intervals[i]->addRange(LiveRange(S, F, ValNum));
+        Intervals[i]->addSegment(LiveInterval::Segment(S, F, ValNum));
       } else {
         // We have two non consecutive regions. This happens when
         // LIFETIME_START appears after the LIFETIME_END marker.
         SlotIndex NewStart = Indexes->getMBBStartIdx(MBB);
         SlotIndex NewFin = Indexes->getMBBEndIdx(MBB);
-        Intervals[i]->addRange(LiveRange(NewStart, F, ValNum));
-        Intervals[i]->addRange(LiveRange(S, NewFin, ValNum));
+        Intervals[i]->addSegment(LiveInterval::Segment(NewStart, F, ValNum));
+        Intervals[i]->addSegment(LiveInterval::Segment(S, NewFin, ValNum));
       }
     }
   }
@@ -763,7 +763,7 @@ bool StackColoring::runOnMachineFunction(MachineFunction &Func) {
         // Merge disjoint slots.
         if (!First->overlaps(*Second)) {
           Changed = true;
-          First->MergeRangesInAsValue(*Second, First->getValNumInfo(0));
+          First->MergeSegmentsInAsValue(*Second, First->getValNumInfo(0));
           SlotRemap[SecondSlot] = FirstSlot;
           SortedSlots[J] = -1;
           DEBUG(dbgs()<<"Merging #"<<FirstSlot<<" and slots #"<<
diff --git a/lib/CodeGen/StrongPHIElimination.cpp b/lib/CodeGen/StrongPHIElimination.cpp
index 79146eb374..b3cf6cc2af 100644
--- a/lib/CodeGen/StrongPHIElimination.cpp
+++ b/lib/CodeGen/StrongPHIElimination.cpp
@@ -347,16 +347,16 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &MF) {
     assert(DestLI.size() == 1
            && "PHI destination copy's live interval should be a single live "
                "range from the beginning of the BB to the copy instruction.");
-    LiveRange *DestLR = DestLI.begin();
-    VNInfo *NewVNI = NewLI.getVNInfoAt(DestLR->start);
+    LiveInterval::Segment *DestS = DestLI.begin();
+    VNInfo *NewVNI = NewLI.getVNInfoAt(DestS->start);
     if (!NewVNI) {
-      NewVNI = NewLI.createValueCopy(DestLR->valno, LI->getVNInfoAllocator());
+      NewVNI = NewLI.createValueCopy(DestS->valno, LI->getVNInfoAllocator());
       MachineInstr *CopyInstr = I->second;
       CopyInstr->getOperand(1).setIsKill(true);
     }
 
-    LiveRange NewLR(DestLR->start, DestLR->end, NewVNI);
-    NewLI.addRange(NewLR);
+    LiveInterval::Segment NewS(DestS->start, DestS->end, NewVNI);
+    NewLI.addSegment(NewS);
 
     LI->removeInterval(DestReg);
     MRI->replaceRegWith(DestReg, NewReg);
@@ -389,7 +389,7 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &MF) {
     MachineOperand *LastUse = findLastUse(MBB, SrcReg);
     assert(LastUse);
     SlotIndex LastUseIndex = LI->getInstructionIndex(LastUse->getParent());
-    SrcLI.removeRange(LastUseIndex.getRegSlot(), LI->getMBBEndIdx(MBB));
+    SrcLI.removeSegment(LastUseIndex.getRegSlot(), LI->getMBBEndIdx(MBB));
     LastUse->setIsKill(true);
   }
 
@@ -702,7 +702,7 @@ void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI,
 
       // addLiveRangeToEndOfBlock() also adds the phikill flag to the VNInfo for
       // the newly added range.
-      LI->addLiveRangeToEndOfBlock(CopyReg, CopyInstr);
+      LI->addSegmentToEndOfBlock(CopyReg, CopyInstr);
       InsertedSrcCopySet.insert(std::make_pair(PredBB, SrcReg));
 
       addReg(CopyReg);
@@ -732,7 +732,7 @@ void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI,
     SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
     SlotIndex NextInstrIndex = PHIIndex.getNextIndex();
     if (SrcLI.liveAt(MBBStartIndex) && SrcLI.expiredAt(NextInstrIndex))
-      SrcLI.removeRange(MBBStartIndex, PHIIndex, true);
+      SrcLI.removeSegment(MBBStartIndex, PHIIndex, true);
   }
 
   unsigned DestReg = PHI->getOperand(0).getReg();
@@ -752,9 +752,9 @@ void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI,
     // beginning of the basic block.
     SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
     DestVNI->def = MBBStartIndex;
-    DestLI.addRange(LiveRange(MBBStartIndex,
-                              PHIIndex.getRegSlot(),
-                              DestVNI));
+    DestLI.addSegment(LiveInterval::Segment(MBBStartIndex,
+                                            PHIIndex.getRegSlot(),
+                                            DestVNI));
     return;
   }
 
@@ -777,15 +777,15 @@ void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI,
   SlotIndex DestCopyIndex = LI->getInstructionIndex(CopyInstr);
   VNInfo *CopyVNI = CopyLI.getNextValue(MBBStartIndex,
                                         LI->getVNInfoAllocator());
-  CopyLI.addRange(LiveRange(MBBStartIndex,
-                            DestCopyIndex.getRegSlot(),
-                            CopyVNI));
+  CopyLI.addSegment(LiveInterval::Segment(MBBStartIndex,
+                                          DestCopyIndex.getRegSlot(),
+                                          CopyVNI));
 
   // Adjust DestReg's live interval to adjust for its new definition at
   // CopyInstr.
   LiveInterval &DestLI = LI->createEmptyInterval(DestReg);
   SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
-  DestLI.removeRange(PHIIndex.getRegSlot(), DestCopyIndex.getRegSlot());
+  DestLI.removeSegment(PHIIndex.getRegSlot(), DestCopyIndex.getRegSlot());
 
   VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot());
   assert(DestVNI);
@@ -803,10 +803,10 @@ void StrongPHIElimination::MergeLIsAndRename(unsigned Reg, unsigned NewReg) {
 
   // Merge the live ranges of the two registers.
   DenseMap<VNInfo*, VNInfo*> VNMap;
-  for (LiveInterval::iterator LRI = OldLI.begin(), LRE = OldLI.end();
-       LRI != LRE; ++LRI) {
-    LiveRange OldLR = *LRI;
-    VNInfo *OldVN = OldLR.valno;
+  for (LiveInterval::iterator SI = OldLI.begin(), SE = OldLI.end();
+       SI != SE; ++SI) {
+    LiveInterval::Segment OldS = *SI;
+    VNInfo *OldVN = OldS.valno;
 
     VNInfo *&NewVN = VNMap[OldVN];
     if (!NewVN) {
@@ -814,8 +814,8 @@ void StrongPHIElimination::MergeLIsAndRename(unsigned Reg, unsigned NewReg) {
       VNMap[OldVN] = NewVN;
     }
 
-    LiveRange LR(OldLR.start, OldLR.end, NewVN);
-    NewLI.addRange(LR);
+    LiveInterval::Segment S(OldS.start, OldS.end, NewVN);
+    NewLI.addSegment(S);
   }
 
   // Remove the LiveInterval for the register being renamed and replace all
diff --git a/lib/CodeGen/TwoAddressInstructionPass.cpp b/lib/CodeGen/TwoAddressInstructionPass.cpp
index c52e6756c7..b9a6b479c3 100644
--- a/lib/CodeGen/TwoAddressInstructionPass.cpp
+++ b/lib/CodeGen/TwoAddressInstructionPass.cpp
@@ -1400,7 +1400,7 @@ TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI,
         VNInfo *VNI = LI.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator());
         SlotIndex endIdx =
           LIS->getInstructionIndex(MI).getRegSlot(IsEarlyClobber);
-        LI.addRange(LiveRange(LastCopyIdx, endIdx, VNI));
+        LI.addSegment(LiveInterval::Segment(LastCopyIdx, endIdx, VNI));
       }
     }
 
@@ -1457,7 +1457,7 @@ TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI,
 
       SlotIndex UseIdx = MIIdx.getRegSlot(IsEarlyClobber);
       if (I->end == UseIdx)
-        LI.removeRange(LastCopyIdx, UseIdx);
+        LI.removeSegment(LastCopyIdx, UseIdx);
     }
 
   } else if (RemovedKillFlag) {