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

1 files changed, 178 insertions, 154 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();
 }