Coding style. No significant functionality. Abandon linear scan style

in favor of the widespread llvm style. Capitalize variables and add
newlines for visual parsing. Rename variables for readability.
And other cleanup.


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

4 files changed, 548 insertions, 524 deletions

diff --git a/lib/CodeGen/LiveIntervalUnion.cpp b/lib/CodeGen/LiveIntervalUnion.cpp
index 46e83f80f8..3da201e0cc 100644
--- a/lib/CodeGen/LiveIntervalUnion.cpp
+++ b/lib/CodeGen/LiveIntervalUnion.cpp
@@ -21,85 +21,92 @@
 #include <algorithm>
 using namespace llvm;
 
-// Find the first segment in the range [segBegin,segments_.end()) that
-// intersects with seg. If no intersection is found, return the first segI
-// such that segI.start >= seg.end
+// Find the first segment in the range [SegBegin,Segments.end()) that
+// intersects with LS. If no intersection is found, return the first SI
+// such that SI.start >= LS.End.
 //
 // This logic is tied to the underlying LiveSegments data structure. For now, we
 // use set::upper_bound to find the nearest starting position,
 // then reverse iterate to find the first overlap.
 //
-// Upon entry we have segBegin.start < seg.end
-// seg   |--...
-//        \   .
-// lvr ...-|
-// 
-// After set::upper_bound, we have segI.start >= seg.start:
-// seg   |--...
-//      /
-// lvr |--...
+// Upon entry we have SegBegin.Start < LS.End
+// SegBegin   |--...
+//             \   .
+//       LS ...-|
+//
+// After set::upper_bound, we have SI.start >= LS.start:
+// SI   |--...
+//     /
+// LS |--...
 //
 // Assuming intervals are disjoint, if an intersection exists, it must be the
 // segment found or the one immediately preceeding it. We continue reverse
 // iterating to return the first overlapping segment.
 LiveIntervalUnion::SegmentIter
-LiveIntervalUnion::upperBound(SegmentIter segBegin,
-                              const LiveSegment &seg) {
-  assert(seg.end > segBegin->start && "segment iterator precondition");
-  // get the next LIU segment such that segI->start is not less than seg.start
-  // 
-  // FIXME: Once we have a B+tree, we can make good use of segBegin as a hint to
+LiveIntervalUnion::upperBound(SegmentIter SegBegin,
+                              const LiveSegment &LS) {
+  assert(LS.End > SegBegin->Start && "segment iterator precondition");
+
+  // Get the next LIU segment such that segI->Start is not less than seg.Start
+  //
+  // FIXME: Once we have a B+tree, we can make good use of SegBegin as a hint to
   // upper_bound. For now, we're forced to search again from the root each time.
-  SegmentIter segI = segments_.upper_bound(seg);
-  while (segI != segBegin) {
-    --segI;
-    if (seg.start >= segI->end)
-      return ++segI;
+  SegmentIter SI = Segments.upper_bound(LS);
+  while (SI != SegBegin) {
+    --SI;
+    if (LS.Start >= SI->End)
+      return ++SI;
   }
-  return segI;
+  return SI;
 }
 
 // Merge a LiveInterval's segments. Guarantee no overlaps.
 //
-// Consider coalescing adjacent segments to save space, even though it makes
-// extraction more complicated.
-void LiveIntervalUnion::unify(LiveInterval &lvr) {
-  // Insert each of the virtual register's live segments into the map
-  SegmentIter segPos = segments_.begin();
-  for (LiveInterval::iterator lvrI = lvr.begin(), lvrEnd = lvr.end();
-       lvrI != lvrEnd; ++lvrI ) {
-    LiveSegment segment(lvrI->start, lvrI->end, &lvr);
-    segPos = segments_.insert(segPos, segment);
-    assert(*segPos == segment && "need equal val for equal key");
+// After implementing B+tree, segments will be coalesced.
+void LiveIntervalUnion::unify(LiveInterval &VirtReg) {
+
+  // Insert each of the virtual register's live segments into the map.
+  SegmentIter SegPos = Segments.begin();
+  for (LiveInterval::iterator VirtRegI = VirtReg.begin(),
+         VirtRegEnd = VirtReg.end();
+       VirtRegI != VirtRegEnd; ++VirtRegI ) {
+
+    LiveSegment Seg(*VirtRegI, &VirtReg);
+    SegPos = Segments.insert(SegPos, Seg);
+
+    assert(*SegPos == Seg && "need equal val for equal key");
 #ifndef NDEBUG
-    // check for overlap (inductively)
-    if (segPos != segments_.begin()) {
-      assert(llvm::prior(segPos)->end <= segment.start &&
-             "overlapping segments" );
+    // Check for overlap (inductively).
+    if (SegPos != Segments.begin()) {
+      assert(llvm::prior(SegPos)->End <= Seg.Start && "overlapping segments" );
     }
-    SegmentIter nextPos = llvm::next(segPos);
-    if (nextPos != segments_.end())
-      assert(segment.end <= nextPos->start && "overlapping segments" );
+    SegmentIter NextPos = llvm::next(SegPos);
+    if (NextPos != Segments.end())
+      assert(Seg.End <= NextPos->Start && "overlapping segments" );
 #endif // NDEBUG
   }
 }
 
 // Remove a live virtual register's segments from this union.
-void LiveIntervalUnion::extract(const LiveInterval &lvr) {
+void LiveIntervalUnion::extract(const LiveInterval &VirtReg) {
+
   // Remove each of the virtual register's live segments from the map.
-  SegmentIter segPos = segments_.begin();
-  for (LiveInterval::const_iterator lvrI = lvr.begin(), lvrEnd = lvr.end();
-       lvrI != lvrEnd; ++lvrI) {
-    LiveSegment seg(lvrI->start, lvrI->end, const_cast<LiveInterval*>(&lvr));
-    segPos = upperBound(segPos, seg);
-    assert(segPos != segments_.end() && "missing lvr segment");
-    segments_.erase(segPos++);
+  SegmentIter SegPos = Segments.begin();
+  for (LiveInterval::const_iterator VirtRegI = VirtReg.begin(),
+         VirtRegEnd = VirtReg.end();
+       VirtRegI != VirtRegEnd; ++VirtRegI) {
+
+    LiveSegment Seg(*VirtRegI, const_cast<LiveInterval*>(&VirtReg));
+    SegPos = upperBound(SegPos, Seg);
+    assert(SegPos != Segments.end() && "missing VirtReg segment");
+
+    Segments.erase(SegPos++);
   }
 }
 
-raw_ostream& llvm::operator<<(raw_ostream& os, const LiveSegment &ls) {
-  return os << '[' << ls.start << ',' << ls.end << ':' <<
-    ls.liveVirtReg->reg << ")";
+raw_ostream& llvm::operator<<(raw_ostream& OS, const LiveSegment &LS) {
+  return OS << '[' << LS.Start << ',' << LS.End << ':' <<
+    LS.VirtReg->reg << ")";
 }
 
 void LiveSegment::dump() const {
@@ -107,35 +114,35 @@ void LiveSegment::dump() const {
 }
 
 void
-LiveIntervalUnion::print(raw_ostream &os,
-                         const AbstractRegisterDescription *rdesc) const {
-  os << "LIU ";
-  if (rdesc != NULL)
-    os << rdesc->getName(repReg_);
+LiveIntervalUnion::print(raw_ostream &OS,
+                         const AbstractRegisterDescription *RegDesc) const {
+  OS << "LIU ";
+  if (RegDesc != NULL)
+    OS << RegDesc->getName(RepReg);
   else {
-    os << repReg_;
+    OS << RepReg;
   }
-  for (LiveSegments::const_iterator segI = segments_.begin(),
-         segEnd = segments_.end(); segI != segEnd; ++segI) {
-    dbgs() << " " << *segI;
+  for (LiveSegments::const_iterator SI = Segments.begin(),
+         SegEnd = Segments.end(); SI != SegEnd; ++SI) {
+    dbgs() << " " << *SI;
   }
-  os << "\n";
+  OS << "\n";
 }
 
-void LiveIntervalUnion::dump(const AbstractRegisterDescription *rdesc) const {
-  print(dbgs(), rdesc);
+void LiveIntervalUnion::dump(const AbstractRegisterDescription *RegDesc) const {
+  print(dbgs(), RegDesc);
 }
 
 #ifndef NDEBUG
 // Verify the live intervals in this union and add them to the visited set.
-void LiveIntervalUnion::verify(LvrBitSet& visitedVRegs) {
-  SegmentIter segI = segments_.begin();
-  SegmentIter segEnd = segments_.end();
-  if (segI == segEnd) return;
-  visitedVRegs.set(segI->liveVirtReg->reg);
-  for (++segI; segI != segEnd; ++segI) {
-    visitedVRegs.set(segI->liveVirtReg->reg);
-    assert(llvm::prior(segI)->end <= segI->start && "overlapping segments" );
+void LiveIntervalUnion::verify(LiveVirtRegBitSet& VisitedVRegs) {
+  SegmentIter SI = Segments.begin();
+  SegmentIter SegEnd = Segments.end();
+  if (SI == SegEnd) return;
+  VisitedVRegs.set(SI->VirtReg->reg);
+  for (++SI; SI != SegEnd; ++SI) {
+    VisitedVRegs.set(SI->VirtReg->reg);
+    assert(llvm::prior(SI)->End <= SI->Start && "overlapping segments" );
   }
 }
 #endif //!NDEBUG
@@ -146,147 +153,164 @@ void LiveIntervalUnion::verify(LvrBitSet& visitedVRegs) {
 // (LiveInterval), and the other in this LiveIntervalUnion. The caller (Query)
 // is responsible for advancing the LiveIntervalUnion segments to find a
 // "notable" intersection, which requires query-specific logic.
-// 
+//
 // This design assumes only a fast mechanism for intersecting a single live
 // virtual register segment with a set of LiveIntervalUnion segments.  This may
-// be ok since most LVRs have very few segments.  If we had a data
+// be ok since most VIRTREGs have very few segments.  If we had a data
 // structure that optimizd MxN intersection of segments, then we would bypass
 // the loop that advances within the LiveInterval.
 //
-// If no intersection exists, set lvrI = lvrEnd, and set segI to the first
+// If no intersection exists, set VirtRegI = VirtRegEnd, and set SI to the first
 // segment whose start point is greater than LiveInterval's end point.
 //
 // Assumes that segments are sorted by start position in both
 // LiveInterval and LiveSegments.
-void LiveIntervalUnion::Query::findIntersection(InterferenceResult &ir) const {
-  LiveInterval::iterator lvrEnd = lvr_->end();
-  SegmentIter liuEnd = liu_->end();
-  while (ir.liuSegI_ != liuEnd) {
+void LiveIntervalUnion::Query::findIntersection(InterferenceResult &IR) const {
+
+  // Search until reaching the end of the LiveUnion segments.
+  LiveInterval::iterator VirtRegEnd = VirtReg->end();
+  SegmentIter LiveUnionEnd = LiveUnion->end();
+  while (IR.LiveUnionI != LiveUnionEnd) {
+
     // Slowly advance the live virtual reg iterator until we surpass the next
-    // segment in this union. If this is ever used for coalescing of fixed
-    // registers and we have a live vreg with thousands of segments, then use
-    // upper bound instead.
-    while (ir.lvrSegI_ != lvrEnd && ir.lvrSegI_->end <= ir.liuSegI_->start)
-      ++ir.lvrSegI_;
-    if (ir.lvrSegI_ == lvrEnd)
-      break;
-    // lvrSegI_ may have advanced far beyond liuSegI_,
+    // segment in LiveUnion.
+    //
+    // Note: If this is ever used for coalescing of fixed registers and we have
+    // a live vreg with thousands of segments, then change this code to use
+    // upperBound instead.
+    while (IR.VirtRegI != VirtRegEnd &&
+           IR.VirtRegI->end <= IR.LiveUnionI->Start)
+      ++IR.VirtRegI;
+    if (IR.VirtRegI == VirtRegEnd)
+      break; // Retain current (nonoverlapping) LiveUnionI
+
+    // VirtRegI may have advanced far beyond LiveUnionI,
     // do a fast intersection test to "catch up"
-    LiveSegment seg(ir.lvrSegI_->start, ir.lvrSegI_->end, lvr_);
-    ir.liuSegI_ = liu_->upperBound(ir.liuSegI_, seg);
-    // Check if no liuSegI_ exists with lvrSegI_->start < liuSegI_.end
-    if (ir.liuSegI_ == liuEnd)
+    LiveSegment Seg(*IR.VirtRegI, VirtReg);
+    IR.LiveUnionI = LiveUnion->upperBound(IR.LiveUnionI, Seg);
+
+    // Check if no LiveUnionI exists with VirtRegI->Start < LiveUnionI.end
+    if (IR.LiveUnionI == LiveUnionEnd)
       break;
-    if (ir.liuSegI_->start < ir.lvrSegI_->end) {
-      assert(overlap(*ir.lvrSegI_, *ir.liuSegI_) && "upperBound postcondition");
+    if (IR.LiveUnionI->Start < IR.VirtRegI->end) {
+      assert(overlap(*IR.VirtRegI, *IR.LiveUnionI) &&
+             "upperBound postcondition");
       break;
     }
   }
-  if (ir.liuSegI_ == liuEnd)
-    ir.lvrSegI_ = lvrEnd;
+  if (IR.LiveUnionI == LiveUnionEnd)
+    IR.VirtRegI = VirtRegEnd;
 }
 
 // Find the first intersection, and cache interference info
-// (retain segment iterators into both lvr_ and liu_).
+// (retain segment iterators into both VirtReg and LiveUnion).
 LiveIntervalUnion::InterferenceResult
 LiveIntervalUnion::Query::firstInterference() {
-  if (firstInterference_ != LiveIntervalUnion::InterferenceResult()) {
-    return firstInterference_;
+  if (FirstInterference != LiveIntervalUnion::InterferenceResult()) {
+    return FirstInterference;
   }
-  firstInterference_ = InterferenceResult(lvr_->begin(), liu_->begin());
-  findIntersection(firstInterference_);
-  return firstInterference_;
+  FirstInterference = InterferenceResult(VirtReg->begin(), LiveUnion->begin());
+  findIntersection(FirstInterference);
+  return FirstInterference;
 }
 
 // Treat the result as an iterator and advance to the next interfering pair
 // of segments. This is a plain iterator with no filter.
-bool LiveIntervalUnion::Query::nextInterference(InterferenceResult &ir) const {
-  assert(isInterference(ir) && "iteration past end of interferences");
-  // Advance either the lvr or liu segment to ensure that we visit all unique
-  // overlapping pairs.
-  if (ir.lvrSegI_->end < ir.liuSegI_->end) {
-    if (++ir.lvrSegI_ == lvr_->end())
+bool LiveIntervalUnion::Query::nextInterference(InterferenceResult &IR) const {
+  assert(isInterference(IR) && "iteration past end of interferences");
+
+  // Advance either the VirtReg or LiveUnion segment to ensure that we visit all
+  // unique overlapping pairs.
+  if (IR.VirtRegI->end < IR.LiveUnionI->End) {
+    if (++IR.VirtRegI == VirtReg->end())
       return false;
   }
   else {
-    if (++ir.liuSegI_ == liu_->end()) {
-      ir.lvrSegI_ = lvr_->end();
+    if (++IR.LiveUnionI == LiveUnion->end()) {
+      IR.VirtRegI = VirtReg->end();
       return false;
     }
   }
-  if (overlap(*ir.lvrSegI_, *ir.liuSegI_))
+  // Short-circuit findIntersection() if possible.
+  if (overlap(*IR.VirtRegI, *IR.LiveUnionI))
     return true;
-  // find the next intersection
-  findIntersection(ir);
-  return isInterference(ir);
+
+  // Find the next intersection.
+  findIntersection(IR);
+  return isInterference(IR);
 }
 
-// Scan the vector of interfering virtual registers in this union. Assuming it's
+// Scan the vector of interfering virtual registers in this union. Assume it's
 // quite small.
-bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *lvr) const {
+bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const {
   SmallVectorImpl<LiveInterval*>::const_iterator I =
-    std::find(interferingVRegs_.begin(), interferingVRegs_.end(), lvr);
-  return I != interferingVRegs_.end();
+    std::find(InterferingVRegs.begin(), InterferingVRegs.end(), VirtReg);
+  return I != InterferingVRegs.end();
 }
 
 // Count the number of virtual registers in this union that interfere with this
-// query's live virtual register. 
-// 
-// The number of times that we either advance ir.lvrSegI_ or call
-// liu_.upperBound() will be no more than the number of holes in
-// lvr_. So each invocation of collectInterferingVirtReg() takes
-// time proportional to |lvr-holes| * time(liu_.upperBound()).
+// query's live virtual register.
+//
+// The number of times that we either advance IR.VirtRegI or call
+// LiveUnion.upperBound() will be no more than the number of holes in
+// VirtReg. So each invocation of collectInterferingVRegs() takes
+// time proportional to |VirtReg Holes| * time(LiveUnion.upperBound()).
 //
 // For comments on how to speed it up, see Query::findIntersection().
 unsigned LiveIntervalUnion::Query::
-collectInterferingVRegs(unsigned maxInterferingRegs) {
-  InterferenceResult ir = firstInterference();
-  LiveInterval::iterator lvrEnd = lvr_->end();
-  SegmentIter liuEnd = liu_->end();
-  LiveInterval *recentInterferingVReg = NULL;
-  while (ir.liuSegI_ != liuEnd) {
+collectInterferingVRegs(unsigned MaxInterferingRegs) {
+  InterferenceResult IR = firstInterference();
+  LiveInterval::iterator VirtRegEnd = VirtReg->end();
+  SegmentIter LiveUnionEnd = LiveUnion->end();
+  LiveInterval *RecentInterferingVReg = NULL;
+  while (IR.LiveUnionI != LiveUnionEnd) {
     // Advance the union's iterator to reach an unseen interfering vreg.
     do {
-      if (ir.liuSegI_->liveVirtReg == recentInterferingVReg)
+      if (IR.LiveUnionI->VirtReg == RecentInterferingVReg)
         continue;
 
-      if (!isSeenInterference(ir.liuSegI_->liveVirtReg))
+      if (!isSeenInterference(IR.LiveUnionI->VirtReg))
         break;
 
       // Cache the most recent interfering vreg to bypass isSeenInterference.
-      recentInterferingVReg = ir.liuSegI_->liveVirtReg;
+      RecentInterferingVReg = IR.LiveUnionI->VirtReg;
 
-    } while( ++ir.liuSegI_ != liuEnd);
-    if (ir.liuSegI_ == liuEnd)
+    } while( ++IR.LiveUnionI != LiveUnionEnd);
+    if (IR.LiveUnionI == LiveUnionEnd)
       break;
 
-    // Advance the live vreg reg iterator until surpassing the next
-    // segment in this union. If this is ever used for coalescing of fixed
-    // registers and we have a live vreg with thousands of segments, then use
-    // upper bound instead.
-    while (ir.lvrSegI_ != lvrEnd && ir.lvrSegI_->end <= ir.liuSegI_->start)
-      ++ir.lvrSegI_;
-    if (ir.lvrSegI_ == lvrEnd)
+    // Advance the VirtReg iterator until surpassing the next segment in
+    // LiveUnion.
+    //
+    // Note: If this is ever used for coalescing of fixed registers and we have
+    // a live virtual register with thousands of segments, then use upperBound
+    // instead.
+    while (IR.VirtRegI != VirtRegEnd &&
+           IR.VirtRegI->end <= IR.LiveUnionI->Start)
+      ++IR.VirtRegI;
+    if (IR.VirtRegI == VirtRegEnd)
       break;
 
     // Check for intersection with the union's segment.
-    if (overlap(*ir.lvrSegI_, *ir.liuSegI_)) {
-      if (!ir.liuSegI_->liveVirtReg->isSpillable())
-        seenUnspillableVReg_ = true;
-      
-      interferingVRegs_.push_back(ir.liuSegI_->liveVirtReg);
-      if (interferingVRegs_.size() == maxInterferingRegs)
-        return maxInterferingRegs;
+    if (overlap(*IR.VirtRegI, *IR.LiveUnionI)) {
+
+      if (!IR.LiveUnionI->VirtReg->isSpillable())
+        SeenUnspillableVReg = true;
+
+      InterferingVRegs.push_back(IR.LiveUnionI->VirtReg);
+      if (InterferingVRegs.size() == MaxInterferingRegs)
+        return MaxInterferingRegs;
 
       // Cache the most recent interfering vreg to bypass isSeenInterference.
-      recentInterferingVReg = ir.liuSegI_->liveVirtReg;
-      ++ir.liuSegI_;
+      RecentInterferingVReg = IR.LiveUnionI->VirtReg;
+      ++IR.LiveUnionI;
       continue;
     }
-    // lvrSegI_ may have advanced far beyond liuSegI_,
+    // VirtRegI may have advanced far beyond LiveUnionI,
     // do a fast intersection test to "catch up"
-    LiveSegment seg(ir.lvrSegI_->start, ir.lvrSegI_->end, lvr_);
-    ir.liuSegI_ = liu_->upperBound(ir.liuSegI_, seg);
+    LiveSegment Seg(*IR.VirtRegI, VirtReg);
+    IR.LiveUnionI = LiveUnion->upperBound(IR.LiveUnionI, Seg);
   }
-  return interferingVRegs_.size();
+  SeenAllInterferences = true;
+  return InterferingVRegs.size();
 }
diff --git a/lib/CodeGen/LiveIntervalUnion.h b/lib/CodeGen/LiveIntervalUnion.h
index 38f6ac3abd..153ee2d669 100644
--- a/lib/CodeGen/LiveIntervalUnion.h
+++ b/lib/CodeGen/LiveIntervalUnion.h
@@ -26,7 +26,7 @@ namespace llvm {
 #ifndef NDEBUG
 // forward declaration
 template <unsigned Element> class SparseBitVector;
-typedef SparseBitVector<128> LvrBitSet;
+typedef SparseBitVector<128> LiveVirtRegBitSet;
 #endif
 
 /// A LiveSegment is a copy of a LiveRange object used within
@@ -37,52 +37,54 @@ typedef SparseBitVector<128> LvrBitSet;
 /// interval within a virtual register's liveness. To limit confusion, in this
 /// file we refer it as a live segment.
 ///
-/// Note: This currently represents a half-open interval [start,end).
+/// Note: This currently represents a half-open interval [Start,End).
 /// If LiveRange is modified to represent a closed interval, so should this.
 struct LiveSegment {
-  SlotIndex start;
-  SlotIndex end;
-  LiveInterval *liveVirtReg;
+  SlotIndex Start;
+  SlotIndex End;
+  LiveInterval *VirtReg;
 
-  LiveSegment(SlotIndex s, SlotIndex e, LiveInterval *lvr)
-    : start(s), end(e), liveVirtReg(lvr) {}
+  LiveSegment(const LiveRange& LR, LiveInterval *VReg)
+    : Start(LR.start), End(LR.end), VirtReg(VReg) {}
 
-  bool operator==(const LiveSegment &ls) const {
-    return start == ls.start && end == ls.end && liveVirtReg == ls.liveVirtReg;
+  bool operator==(const LiveSegment &LS) const {
+    return Start == LS.Start && End == LS.End && VirtReg == LS.VirtReg;
   }
 
-  bool operator!=(const LiveSegment &ls) const {
-    return !operator==(ls);
+  bool operator!=(const LiveSegment &LS) const {
+    return !operator==(LS);
   }
 
   // Order segments by starting point only--we expect them to be disjoint.
-  bool operator<(const LiveSegment &ls) const { return start < ls.start; }
+  bool operator<(const LiveSegment &LS) const { return Start < LS.Start; }
 
   void dump() const;
-  void print(raw_ostream &os) const;
+  void print(raw_ostream &OS) const;
 };
 
-inline bool operator<(SlotIndex V, const LiveSegment &ls) {
-  return V < ls.start;
+inline bool operator<(SlotIndex Idx, const LiveSegment &LS) {
+  return Idx < LS.Start;
 }
 
-inline bool operator<(const LiveSegment &ls, SlotIndex V) {
-  return ls.start < V;
+inline bool operator<(const LiveSegment &LS, SlotIndex Idx) {
+  return LS.Start < Idx;
 }
 
 /// Compare a live virtual register segment to a LiveIntervalUnion segment.
-inline bool overlap(const LiveRange &lvrSeg, const LiveSegment &liuSeg) {
-  return lvrSeg.start < liuSeg.end && liuSeg.start < lvrSeg.end;
+inline bool overlap(const LiveRange &VirtRegSegment,
+                    const LiveSegment &LiveUnionSegment) {
+  return VirtRegSegment.start < LiveUnionSegment.End &&
+    LiveUnionSegment.Start < VirtRegSegment.end;
 }
 
 template <> struct isPodLike<LiveSegment> { static const bool value = true; };
 
-raw_ostream& operator<<(raw_ostream& os, const LiveSegment &ls);
+raw_ostream& operator<<(raw_ostream& OS, const LiveSegment &LS);
 
 /// Abstraction to provide info for the representative register.
 class AbstractRegisterDescription {
 public:
-  virtual const char *getName(unsigned reg) const = 0;
+  virtual const char *getName(unsigned Reg) const = 0;
   virtual ~AbstractRegisterDescription() {}
 };
 
@@ -92,7 +94,7 @@ public:
 /// eventually make exceptions to handle value-based interference.
 class LiveIntervalUnion {
   // A set of live virtual register segments that supports fast insertion,
-  // intersection, and removal. 
+  // intersection, and removal.
   //
   // FIXME: std::set is a placeholder until we decide how to
   // efficiently represent it. Probably need to roll our own B-tree.
@@ -103,7 +105,7 @@ class LiveIntervalUnion {
   // This is traditionally known as a live range, but we refer is as a live
   // virtual register to avoid confusing it with the misnamed LiveRange
   // class.
-  typedef std::vector<LiveInterval*> LiveVirtRegs;
+  typedef std::vector<LiveInterval*> LiveVRegs;
 
 public:
   // SegmentIter can advance to the next segment ordered by starting position
@@ -115,41 +117,41 @@ public:
   class Query;
 
 private:
-  unsigned repReg_;        // representative register number
-  LiveSegments segments_;  // union of virtual reg segements
+  unsigned RepReg;        // representative register number
+  LiveSegments Segments;  // union of virtual reg segements
 
 public:
   // default ctor avoids placement new
-  LiveIntervalUnion() : repReg_(0) {}
+  LiveIntervalUnion() : RepReg(0) {}
 
   // Initialize the union by associating it with a representative register
   // number.
-  void init(unsigned repReg) { repReg_ = repReg; }
+  void init(unsigned Reg) { RepReg = Reg; }
 
   // Iterate over all segments in the union of live virtual registers ordered
   // by their starting position.
-  SegmentIter begin() { return segments_.begin(); }
-  SegmentIter end() { return segments_.end(); }
+  SegmentIter begin() { return Segments.begin(); }
+  SegmentIter end() { return Segments.end(); }
 
   // Return an iterator to the first segment after or including begin that
-  // intersects with lvrSeg.
-  SegmentIter upperBound(SegmentIter begin, const LiveSegment &seg);
+  // intersects with LS.
+  SegmentIter upperBound(SegmentIter SegBegin, const LiveSegment &LS);
 
   // Add a live virtual register to this union and merge its segments.
-  // Holds a nonconst reference to the LVR for later maniplution.
-  void unify(LiveInterval &lvr);
+  // Holds a nonconst reference to the VirtReg for later maniplution.
+  void unify(LiveInterval &VirtReg);
 
   // Remove a live virtual register's segments from this union.
-  void extract(const LiveInterval &lvr);
+  void extract(const LiveInterval &VirtReg);
 
-  void dump(const AbstractRegisterDescription *regInfo) const;
+  void dump(const AbstractRegisterDescription *RegDesc) const;
+
+  // If tri != NULL, use it to decode RepReg
+  void print(raw_ostream &OS, const AbstractRegisterDescription *RegDesc) const;
 
-  // If tri != NULL, use it to decode repReg_
-  void print(raw_ostream &os, const AbstractRegisterDescription *rdesc) const;
-  
 #ifndef NDEBUG
   // Verify the live intervals in this union and add them to the visited set.
-  void verify(LvrBitSet& visitedVRegs);
+  void verify(LiveVirtRegBitSet& VisitedVRegs);
 #endif
 
   /// Cache a single interference test result in the form of two intersecting
@@ -159,85 +161,89 @@ public:
   class InterferenceResult {
     friend class Query;
 
-    LiveInterval::iterator lvrSegI_; // current position in _lvr
-    SegmentIter liuSegI_;            // current position in _liu
-    
+    LiveInterval::iterator VirtRegI; // current position in VirtReg
+    SegmentIter LiveUnionI;          // current position in LiveUnion
+
     // Internal ctor.
-    InterferenceResult(LiveInterval::iterator lvrSegI, SegmentIter liuSegI)
-      : lvrSegI_(lvrSegI), liuSegI_(liuSegI) {}
+    InterferenceResult(LiveInterval::iterator VRegI, SegmentIter UnionI)
+      : VirtRegI(VRegI), LiveUnionI(UnionI) {}
 
   public:
     // Public default ctor.
-    InterferenceResult(): lvrSegI_(), liuSegI_() {}
+    InterferenceResult(): VirtRegI(), LiveUnionI() {}
 
     // Note: this interface provides raw access to the iterators because the
     // result has no way to tell if it's valid to dereference them.
 
-    // Access the lvr segment. 
-    LiveInterval::iterator lvrSegPos() const { return lvrSegI_; }
+    // Access the VirtReg segment.
+    LiveInterval::iterator virtRegPos() const { return VirtRegI; }
 
-    // Access the liu segment.
-    SegmentIter liuSegPos() const { return liuSegI_; }
+    // Access the LiveUnion segment.
+    SegmentIter liveUnionPos() const { return LiveUnionI; }
 
-    bool operator==(const InterferenceResult &ir) const {
-      return lvrSegI_ == ir.lvrSegI_ && liuSegI_ == ir.liuSegI_;
+    bool operator==(const InterferenceResult &IR) const {
+      return VirtRegI == IR.VirtRegI && LiveUnionI == IR.LiveUnionI;
     }
-    bool operator!=(const InterferenceResult &ir) const {
-      return !operator==(ir);
+    bool operator!=(const InterferenceResult &IR) const {
+      return !operator==(IR);
     }
   };
 
   /// Query interferences between a single live virtual register and a live
   /// interval union.
   class Query {
-    LiveIntervalUnion *liu_;
-    LiveInterval *lvr_;
-    InterferenceResult firstInterference_;
-    SmallVector<LiveInterval*,4> interferingVRegs_;
-    bool seenUnspillableVReg_;
+    LiveIntervalUnion *LiveUnion;
+    LiveInterval *VirtReg;
+    InterferenceResult FirstInterference;
+    SmallVector<LiveInterval*,4> InterferingVRegs;
+    bool SeenAllInterferences;
+    bool SeenUnspillableVReg;
 
   public:
-    Query(): liu_(), lvr_() {}
+    Query(): LiveUnion(), VirtReg() {}
 
-    Query(LiveInterval *lvr, LiveIntervalUnion *liu):
-      liu_(liu), lvr_(lvr), seenUnspillableVReg_(false) {}
+    Query(LiveInterval *VReg, LiveIntervalUnion *LIU):
+      LiveUnion(LIU), VirtReg(VReg), SeenAllInterferences(false),
+      SeenUnspillableVReg(false)
+    {}
 
     void clear() {
-      liu_ = NULL;
-      lvr_ = NULL;
-      firstInterference_ = InterferenceResult();
-      interferingVRegs_.clear();
-      seenUnspillableVReg_ = false;
+      LiveUnion = NULL;
+      VirtReg = NULL;
+      FirstInterference = InterferenceResult();
+      InterferingVRegs.clear();
+      SeenAllInterferences = false;
+      SeenUnspillableVReg = false;
     }
-    
-    void init(LiveInterval *lvr, LiveIntervalUnion *liu) {
-      if (lvr_ == lvr) {
+
+    void init(LiveInterval *VReg, LiveIntervalUnion *LIU) {
+      if (VirtReg == VReg) {
         // We currently allow query objects to be reused acrossed live virtual
         // registers, but always for the same live interval union.
-        assert(liu_ == liu && "inconsistent initialization");
+        assert(LiveUnion == LIU && "inconsistent initialization");
         // Retain cached results, e.g. firstInterference.
         return;
       }
-      liu_ = liu;
-      lvr_ = lvr;
-      // Clear cached results.
-      firstInterference_ = InterferenceResult();
-      interferingVRegs_.clear();
-      seenUnspillableVReg_ = false;
+      clear();
+      LiveUnion = LIU;
+      VirtReg = VReg;
     }
 
-    LiveInterval &lvr() const { assert(lvr_ && "uninitialized"); return *lvr_; }
+    LiveInterval &virtReg() const {
+      assert(VirtReg && "uninitialized");
+      return *VirtReg;
+    }
 
-    bool isInterference(const InterferenceResult &ir) const {
-      if (ir.lvrSegI_ != lvr_->end()) {
-        assert(overlap(*ir.lvrSegI_, *ir.liuSegI_) &&
+    bool isInterference(const InterferenceResult &IR) const {
+      if (IR.VirtRegI != VirtReg->end()) {
+        assert(overlap(*IR.VirtRegI, *IR.LiveUnionI) &&
                "invalid segment iterators");
         return true;
       }
       return false;
     }
 
-    // Does this live virtual register interfere with the union.
+    // Does this live virtual register interfere with the union?
     bool checkInterference() { return isInterference(firstInterference()); }
 
     // Get the first pair of interfering segments, or a noninterfering result.
@@ -246,32 +252,33 @@ public:
 
     // Treat the result as an iterator and advance to the next interfering pair
     // of segments. Visiting each unique interfering pairs means that the same
-    // lvr or liu segment may be visited multiple times.
-    bool nextInterference(InterferenceResult &ir) const;
+    // VirtReg or LiveUnion segment may be visited multiple times.
+    bool nextInterference(InterferenceResult &IR) const;
 
     // Count the virtual registers in this union that interfere with this
     // query's live virtual register, up to maxInterferingRegs.
-    unsigned collectInterferingVRegs(unsigned maxInterferingRegs = UINT_MAX);
+    unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX);
 
     // Was this virtual register visited during collectInterferingVRegs?
-    bool isSeenInterference(LiveInterval *lvr) const;
+    bool isSeenInterference(LiveInterval *VReg) const;
+
+    // Did collectInterferingVRegs collect all interferences?
+    bool seenAllInterferences() const { return SeenAllInterferences; }
 
     // Did collectInterferingVRegs encounter an unspillable vreg?
-    bool seenUnspillableVReg() const {
-      return seenUnspillableVReg_;
-    }
+    bool seenUnspillableVReg() const { return SeenUnspillableVReg; }
 
     // Vector generated by collectInterferingVRegs.
     const SmallVectorImpl<LiveInterval*> &interferingVRegs() const {
-      return interferingVRegs_;
+      return InterferingVRegs;
     }
-    
+
   private:
     Query(const Query&);          // DO NOT IMPLEMENT
     void operator=(const Query&); // DO NOT IMPLEMENT
-    
+
     // Private interface for queries
-    void findIntersection(InterferenceResult &ir) const;
+    void findIntersection(InterferenceResult &IR) const;
   };
 };
 
diff --git a/lib/CodeGen/RegAllocBase.h b/lib/CodeGen/RegAllocBase.h
index c8c78567f8..8044a19238 100644
--- a/lib/CodeGen/RegAllocBase.h
+++ b/lib/CodeGen/RegAllocBase.h
@@ -11,11 +11,11 @@
 // register allocation algorithm and interface for extending it. It provides the
 // building blocks on which to construct other experimental allocators and test
 // the validity of two principles:
-// 
+//
 // - If virtual and physical register liveness is modeled using intervals, then
 // on-the-fly interference checking is cheap. Furthermore, interferences can be
 // lazily cached and reused.
-// 
+//
 // - Register allocation complexity, and generated code performance is
 // determined by the effectiveness of live range splitting rather than optimal
 // coloring.
@@ -52,8 +52,8 @@ class Spiller;
 // The default is to simply compare spill weights.
 struct LessSpillWeightPriority
   : public std::binary_function<LiveInterval,LiveInterval, bool> {
-  bool operator()(const LiveInterval *left, const LiveInterval *right) const {
-    return left->weight < right->weight;
+  bool operator()(const LiveInterval *Left, const LiveInterval *Right) const {
+    return Left->weight < Right->weight;
   }
 };
 
@@ -65,41 +65,40 @@ class LiveVirtRegQueue;
 /// RegAllocBase provides the register allocation driver and interface that can
 /// be extended to add interesting heuristics.
 ///
-/// More sophisticated allocators must override the selectOrSplit() method to
-/// implement live range splitting and must specify a comparator to determine
-/// register assignment priority. LessSpillWeightPriority is provided as a
-/// standard comparator.
+/// Register allocators must override the selectOrSplit() method to implement
+/// live range splitting. LessSpillWeightPriority is provided as a standard
+/// comparator, but we may add an interface to override it if necessary.
 class RegAllocBase {
 protected:
   // Array of LiveIntervalUnions indexed by physical register.
-  class LIUArray {
-    unsigned nRegs_;
-    OwningArrayPtr<LiveIntervalUnion> array_;
+  class LiveUnionArray {
+    unsigned NumRegs;
+    OwningArrayPtr<LiveIntervalUnion> Array;
   public:
-    LIUArray(): nRegs_(0) {}
+    LiveUnionArray(): NumRegs(0) {}
 
-    unsigned numRegs() const { return nRegs_; }
+    unsigned numRegs() const { return NumRegs; }
 
-    void init(unsigned nRegs);
+    void init(unsigned NRegs);
 
     void clear();
-    
-    LiveIntervalUnion& operator[](unsigned physReg) {
-      assert(physReg <  nRegs_ && "physReg out of bounds");
-      return array_[physReg];
+
+    LiveIntervalUnion& operator[](unsigned PhysReg) {
+      assert(PhysReg <  NumRegs && "physReg out of bounds");
+      return Array[PhysReg];
     }
   };
-  
-  const TargetRegisterInfo *tri_;
-  VirtRegMap *vrm_;
-  LiveIntervals *lis_;
-  LIUArray physReg2liu_;
+
+  const TargetRegisterInfo *TRI;
+  VirtRegMap *VRM;
+  LiveIntervals *LIS;
+  LiveUnionArray PhysReg2LiveUnion;
 
   // Current queries, one per physreg. They must be reinitialized each time we
   // query on a new live virtual register.
-  OwningArrayPtr<LiveIntervalUnion::Query> queries_;
+  OwningArrayPtr<LiveIntervalUnion::Query> Queries;
 
-  RegAllocBase(): tri_(0), vrm_(0), lis_(0) {}
+  RegAllocBase(): TRI(0), VRM(0), LIS(0) {}
 
   virtual ~RegAllocBase() {}
 
@@ -108,13 +107,13 @@ protected:
 
   // Get an initialized query to check interferences between lvr and preg.  Note
   // that Query::init must be called at least once for each physical register
-  // before querying a new live virtual register. This ties queries_ and
-  // physReg2liu_ together.
-  LiveIntervalUnion::Query &query(LiveInterval &lvr, unsigned preg) {<