Fix/Redo computeMainRangeFromSubranges()

[MatzeB]

Summary

Fix/Redo computeMainRangeFromSubranges()

Contrary to my initial assumption there are cases where we need
additional phi-defs when constructing the main liverange from subranges.
Redo the implementation in LiveRangeCalc and utilize the SSA
construction facilities there. The downside is that this is more
expensive than before, the upside is simplified easier to undertsand
code that reuses existing infrastructure for the SSA construction.

I was not able to create a testcase for this for trunk as the cases
where this happens require somewhat "independent" subranges in different
control flow parts. With the normal instruction selection those get
lowered to different vregs in my tries. I only hit these cases for some
register coalescer changes I am prepare where
computeMainRangeFromSubranges() would be called after/during coalescing.

[qcolombet]

Hi Matthias,

What is the impact of this on the compile time? (Release without asserts).

Although I like the cleanup, I want to be sure we do not dramatically decrease the compile time.

Thanks,
-Quentin

[MatzeB]

Abandoning this revision for now:

• In the current pipeline where live intervals are calculated immediately after PhiElimination and TwoAddress calculation the structures are so simple that the current code is good enough. So no need for this yet.
• When doing things differently like recomputing whole live ranges in the register coalescer instead of updating them, a patch like this is necessary, but it turned out this is not enough. Without having detailed information about undef uses at the subregister level we still run into problems. So this approach can only work in combination with a scheme to mark partially undef uses.

include/llvm/CodeGen/LiveInterval.h

public:
     /// Constructs a new LiveRange object.
     LiveRange(bool UseSegmentSet = false) : segmentSet(nullptr) {
       if (UseSegmentSet)
         segmentSet = new SegmentSet();
     }
 
     /// Constructs a new LiveRange object by copying segments and valnos from
     /// another LiveRange.
-    LiveRange(const LiveRange &Other, BumpPtrAllocator &Allocator)
+    LiveRange(const LiveRange &Other, VNInfo::Allocator &Allocator)
         : segmentSet(nullptr) {
-      assert(Other.segmentSet == nullptr &&
-             "Copying of LiveRanges with active SegmentSets is not supported");
-
-      // Duplicate valnos.
-      for (const VNInfo *VNI : Other.valnos) {
-        createValueCopy(VNI, Allocator);
-      }
-      // Now we can copy segments and remap their valnos.
-      for (const Segment &S : Other.segments) {
-        segments.push_back(Segment(S.start, S.end, valnos[S.valno->id]));
-      }
+      copyFrom(Other, Allocator);
     }
 
     ~LiveRange() { delete segmentSet; }
 
     /// advanceTo - Advance the specified iterator to point to the Segment
     /// containing the specified position, or end() if the position is past the
     /// end of the range.  If no Segment contains this position, but the
     /// position is in a hole, this method returns an iterator pointing to the
VNInfo *getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator) {
       return VNI;
     }
 
     /// createDeadDef - Make sure the range has a value defined at Def.
     /// If one already exists, return it. Otherwise allocate a new value and
     /// add liveness for a dead def.
     VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator);
 
-    /// Create a copy of the given value. The new value will be identical except
-    /// for the Value number.
-    VNInfo *createValueCopy(const VNInfo *orig,
-                            VNInfo::Allocator &VNInfoAllocator) {
-      VNInfo *VNI =
-        new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig);
-      valnos.push_back(VNI);
-      return VNI;
-    }
+    /// Copy range @p Other into this range. This is done by duplicating the
+    /// value numbers and recreating all segments with these numbers.
+    void copyFrom(const LiveRange &Other, VNInfo::Allocator &Allocator);
 
     /// RenumberValues - Renumber all values in order of appearance and remove
     /// unused values.
     void RenumberValues();
 
     /// MergeValueNumberInto - This method is called when two value numbers
     /// are found to be equivalent.  This eliminates V1, replacing all
     /// segments with the V1 value number with the V2 value number.  This can
public:
 
     /// Removes all subregister liveness information.
     void clearSubRanges();
 
     /// Removes all subranges without any segments (subranges without segments
     /// are not considered valid and should only exist temporarily).
     void removeEmptySubRanges();
 
-    /// Construct main live range by merging the SubRanges of @p LI.
-    void constructMainRangeFromSubranges(const SlotIndexes &Indexes,
-                                         VNInfo::Allocator &VNIAllocator);
-
     /// getSize - Returns the sum of sizes of all the LiveRange's.
     ///
     unsigned getSize() const;
 
     /// isSpillable - Can this interval be spilled?
     bool isSpillable() const {
       return weight != llvm::huge_valf;
     }

lib/CodeGen/LiveInterval.cpp

VNInfo *LiveRange::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) {
   }
 
   // Now that V1 is dead, remove it.
   markValNoForDeletion(V1);
 
   return V2;
 }
 
+void LiveRange::copyFrom(const LiveRange &Other, VNInfo::Allocator &Allocator) {
+  assert(valnos.empty() && segments.empty() && "this range must be empty");
+  assert(Other.segmentSet == nullptr &&
+         "Copying of LiveRanges with active SegmentSets is not supported");
+
+  // Duplicate valnos.
+  for (const VNInfo *VNI : Other.valnos)
+    getNextValue(VNI->def, Allocator);
+  // Now we can copy segments and remap their valnos.
+  for (const Segment &S : Other.segments)
+    segments.push_back(Segment(S.start, S.end, valnos[S.valno->id]));
+}
+
 void LiveRange::flushSegmentSet() {
   assert(segmentSet != nullptr && "segment set must have been created");
   assert(
       segments.empty() &&
       "segment set can be used only initially before switching to the array");
   segments.append(segmentSet->begin(), segmentSet->end());
   delete segmentSet;
   segmentSet = nullptr;

 void LiveInterval::clearSubRanges() {
   for (SubRange *I = SubRanges, *Next; I != nullptr; I = Next) {
     Next = I->Next;
     freeSubRange(I);
   }
   SubRanges = nullptr;
 }
 
-/// Helper function for constructMainRangeFromSubranges(): Search the CFG
-/// backwards until we find a place covered by a LiveRange segment that actually
-/// has a valno set.
-static VNInfo *searchForVNI(const SlotIndexes &Indexes, LiveRange &LR,
-    const MachineBasicBlock *MBB,
-    SmallPtrSetImpl<const MachineBasicBlock*> &Visited) {
-  // We start the search at the end of MBB.
-  SlotIndex EndIdx = Indexes.getMBBEndIdx(MBB);
-  // In our use case we can't live the area covered by the live segments without
-  // finding an actual VNI def.
-  LiveRange::iterator I = LR.find(EndIdx.getPrevSlot());
-  assert(I != LR.end());
-  LiveRange::Segment &S = *I;
-  if (S.valno != nullptr)
-    return S.valno;
-
-  VNInfo *VNI = nullptr;
-  // Continue at predecessors (we could even go to idom with domtree available).
-  for (const MachineBasicBlock *Pred : MBB->predecessors()) {
-    // Avoid going in circles.
-    if (!Visited.insert(Pred).second)
-      continue;
-
-    VNI = searchForVNI(Indexes, LR, Pred, Visited);
-    if (VNI != nullptr) {
-      S.valno = VNI;
-      break;
-    }
-  }
-
-  return VNI;
-}
-
-static void determineMissingVNIs(const SlotIndexes &Indexes, LiveInterval &LI) {
-  SmallPtrSet<const MachineBasicBlock*, 5> Visited;
-  for (LiveRange::Segment &S : LI.segments) {
-    if (S.valno != nullptr)
-      continue;
-    // This can only happen at the begin of a basic block.
-    assert(S.start.isBlock() && "valno should only be missing at block begin");
-
-    Visited.clear();
-    const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(S.start);
-    for (const MachineBasicBlock *Pred : MBB->predecessors()) {
-      VNInfo *VNI = searchForVNI(Indexes, LI, Pred, Visited);
-      if (VNI != nullptr) {
-        S.valno = VNI;
-        break;
-      }
-    }
-    assert(S.valno != nullptr && "could not determine valno");
-  }
-}
-
-void LiveInterval::constructMainRangeFromSubranges(
-    const SlotIndexes &Indexes, VNInfo::Allocator &VNIAllocator) {
-  // The basic observations on which this algorithm is based:
-  // - Each Def/ValNo in a subrange must have a corresponding def on the main
-  //   range, but not further defs/valnos are necessary.
-  // - If any of the subranges is live at a point the main liverange has to be
-  //   live too, conversily if no subrange is live the main range mustn't be
-  //   live either.
-  // We do this by scannig through all the subranges simultaneously creating new
-  // segments in the main range as segments start/ends come up in the subranges.
-  assert(hasSubRanges() && "expected subranges to be present");
-  assert(segments.empty() && valnos.empty() && "expected empty main range");
-
-  // Collect subrange, iterator pairs for the walk and determine first and last
-  // SlotIndex involved.
-  SmallVector<std::pair<const SubRange*, const_iterator>, 4> SRs;
-  SlotIndex First;
-  SlotIndex Last;
-  for (const SubRange &SR : subranges()) {
-    if (SR.empty())
-      continue;
-    SRs.push_back(std::make_pair(&SR, SR.begin()));
-    if (!First.isValid() || SR.segments.front().start < First)
-      First = SR.segments.front().start;
-    if (!Last.isValid() || SR.segments.back().end > Last)
-      Last = SR.segments.back().end;
-  }
-
-  // Walk over all subranges simultaneously.
-  Segment CurrentSegment;
-  bool ConstructingSegment = false;
-  bool NeedVNIFixup = false;
-  unsigned ActiveMask = 0;
-  SlotIndex Pos = First;
-  while (true) {
-    SlotIndex NextPos = Last;
-    enum {
-      NOTHING,
-      BEGIN_SEGMENT,
-      END_SEGMENT,
-    } Event = NOTHING;
-    // Which subregister lanes are affected by the current event.
-    unsigned EventMask = 0;
-    // Whether a BEGIN_SEGMENT is also a valno definition point.
-    bool IsDef = false;
-    // Find the next begin or end of a subrange segment. Combine masks if we
-    // have multiple begins/ends at the same position. Ends take precedence over
-    // Begins.
-    for (auto &SRP : SRs) {
-      const SubRange &SR = *SRP.first;
-      const_iterator &I = SRP.second;
-      // Advance iterator of subrange to a segment involving Pos; the earlier
-      // segments are already merged at this point.
-      while (I != SR.end() &&
-             (I->end < Pos ||
-              (I->end == Pos && (ActiveMask & SR.LaneMask) == 0)))
-        ++I;
-      if (I == SR.end())
-        continue;
-      if ((ActiveMask & SR.LaneMask) == 0 &&
-          Pos <= I->start && I->start <= NextPos) {
-        // Merge multiple begins at the same position.
-        if (I->start == NextPos && Event == BEGIN_SEGMENT) {
-          EventMask |= SR.LaneMask;
-          IsDef |= I->valno->def == I->start;
-        } else if (I->start < NextPos || Event != END_SEGMENT) {
-          Event = BEGIN_SEGMENT;
-          NextPos = I->start;
-          EventMask = SR.LaneMask;
-          IsDef = I->valno->def == I->start;
-        }
-      }
-      if ((ActiveMask & SR.LaneMask) != 0 &&
-          Pos <= I->end && I->end <= NextPos) {
-        // Merge multiple ends at the same position.
-        if (I->end == NextPos && Event == END_SEGMENT)
-          EventMask |= SR.LaneMask;
-        else {
-          Event = END_SEGMENT;
-          NextPos = I->end;
-          EventMask = SR.LaneMask;
-        }
-      }
-    }
-
-    // Advance scan position.
-    Pos = NextPos;
-    if (Event == BEGIN_SEGMENT) {
-      if (ConstructingSegment && IsDef) {
-        // Finish previous segment because we have to start a new one.
-        CurrentSegment.end = Pos;
-        append(CurrentSegment);
-        ConstructingSegment = false;
-      }
-
-      // Start a new segment if necessary.
-      if (!ConstructingSegment) {
-        // Determine value number for the segment.
-        VNInfo *VNI;
-        if (IsDef) {
-          VNI = getNextValue(Pos, VNIAllocator);
-        } else {
-          // We have to reuse an existing value number, if we are lucky
-          // then we already passed one of the predecessor blocks and determined
-          // its value number (with blocks in reverse postorder this would be
-          // always true but we have no such guarantee).
-          assert(Pos.isBlock());
-          const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(Pos);
-          // See if any of the predecessor blocks has a lower number and a VNI
-          for (const MachineBasicBlock *Pred : MBB->predecessors()) {
-            SlotIndex PredEnd = Indexes.getMBBEndIdx(Pred);
-            VNI = getVNInfoBefore(PredEnd);
-            if (VNI != nullptr)
-              break;
-          }
-          // Def will come later: We have to do an extra fixup pass.
-          if (VNI == nullptr)
-            NeedVNIFixup = true;
-        }
-
-        CurrentSegment.start = Pos;
-        CurrentSegment.valno = VNI;
-        ConstructingSegment = true;
-      }
-      ActiveMask |= EventMask;
-    } else if (Event == END_SEGMENT) {
-      assert(ConstructingSegment);
-      // Finish segment if no lane is active anymore.
-      ActiveMask &= ~EventMask;
-      if (ActiveMask == 0) {
-        CurrentSegment.end = Pos;
-        append(CurrentSegment);
-        ConstructingSegment = false;
-      }
-    } else {
-      // We reached the end of the last subranges and can stop.
-      assert(Event == NOTHING);
-      break;
-    }
-  }
-
-  // We might not be able to assign new valnos for all segments if the basic
-  // block containing the definition comes after a segment using the valno.
-  // Do a fixup pass for this uncommon case.
-  if (NeedVNIFixup)
-    determineMissingVNIs(Indexes, *this);
-
-  assert(ActiveMask == 0 && !ConstructingSegment && "all segments ended");
-  verify();
-}
-
 unsigned LiveInterval::getSize() const {
   unsigned Sum = 0;
   for (const Segment &S : segments)
     Sum += S.start.distance(S.end);
   return Sum;
 }
 
 raw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange::Segment &S) {

lib/CodeGen/LiveRangeCalc.h

public:
   /// calculateValues - Calculate the value that will be live-in to each block
   /// added with addLiveInBlock.  Add PHI-def values as needed to preserve SSA
   /// form.  Add liveness to all live-in blocks up to the Kill point, or the
   /// whole block for live-through blocks.
   ///
   /// Every predecessor of a live-in block must have been given a value with
   /// setLiveOutValue, the value may be null for live-trough blocks.
   void calculateValues();
+
+  /// Construct main live range by merging the SubRanges of @p LI.
+  void computeMainRangeFromSubranges(LiveInterval &LI);
 };
 
 } // end namespace llvm
 
 #endif

lib/CodeGen/LiveRangeCalc.cpp

 //===---- LiveRangeCalc.cpp - Calculate live ranges -----------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Implementation of the LiveRangeCalc class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "LiveRangeCalc.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/Support/Debug.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "regalloc"
 
 void LiveRangeCalc::resetLiveOutMap() {
   unsigned NumBlocks = MF->getNumBlockIDs();
   Seen.clear();
void LiveRangeCalc::calculate(LiveInterval &LI) {
   // Step 2: Extend live segments to all uses, constructing SSA form as
   // necessary.
   if (LI.hasSubRanges()) {
     for (LiveInterval::SubRange &S : LI.subranges()) {
       resetLiveOutMap();
       extendToUses(S, Reg, S.LaneMask);
     }
     LI.clear();
-    LI.constructMainRangeFromSubranges(*Indexes, *Alloc);
+    computeMainRangeFromSubranges(LI);
   } else {
     resetLiveOutMap();
     extendToUses(LI, Reg, ~0u);
   }
 }
 
 
 void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) {
for (LiveInBlock &I : LiveIn) {
         if (LOP.first == IDomValue.first)
           continue;
         ++Changes;
         LOP = IDomValue;
       }
     }
   } while (Changes);
 }
+
+void LiveRangeCalc::computeMainRangeFromSubranges(LiveInterval &LI) {
+  // The basic observations on which this algorithm is based:
+  // - Each Def/ValNo in a subrange must have a corresponding def on the main
+  //   range.
+  // - If any of the subranges is live at a point the main liverange has to be
+  //   live too, conversily where no subrange is live the main range mustn't be
+  //   live either.
+  assert(LI.hasSubRanges() && "expected subranges to be present");
+  assert(LI.segments.empty() && LI.valnos.empty() &&
+         "expected empty main range");
+
+  // Shortcut: If we only have a single subrange, then we can simply copy that
+  // to the main range and are done.
+  auto I = LI.subrange_begin();
+  ++I;
+  if (I == LI.subrange_end()) {
+    LI.copyFrom(*LI.subrange_begin(), *Alloc);
+    return;
+  }
+
+  // Recreate all defpoints of the subregister ranges in the main liverange. We
+  // also search for subregister defs without read-undef that should be regarded
+  // as uses later.
+  SmallVector<SlotIndex, 4> AdditionalUses;
+  for (const LiveInterval::SubRange &SR : LI.subranges()) {
+    for (const VNInfo *VNI : SR.valnos) {
+      // We can ignore PHI defs, they will be recreated during SSA construction.
+      if (VNI->isPHIDef())
+        continue;
+      LI.createDeadDef(VNI->def, *Alloc);
+      // If another subregister crosses the def point, then this must be a
+      // subreg def without a read-undef marker.
+      for (LiveInterval::SubRange &SR2 : LI.subranges()) {
+        if (&SR2 == &SR)
+          continue;
+        LiveQueryResult LRQ = SR2.Query(VNI->def);
+        if (LRQ.valueIn() != nullptr && LRQ.valueIn() == LRQ.valueOut())
+          AdditionalUses.push_back(VNI->def);
+      }
+    }
+  }
+
+  // Consider all subrange live segment endpoints and the previously collected
+  // subreg-defs as uses and construct SSA form as necessary.
+  resetLiveOutMap();
+  LiveIn.clear();
+  for (const LiveInterval::SubRange &SR : LI.subranges()) {
+    for (const LiveRange::Segment &S : SR.segments)
+      extend(LI, S.end, 0);
+  }
+  for (const SlotIndex &I : AdditionalUses)
+    extend(LI, I, 0);
+
+  LI.verify();
+}