Assume lane masks are precise

[MatzeB]

Summary

Assuming I get no complains in the E-Mail thread (http://lists.llvm.org/pipermail/llvm-dev/2015-November/092238.html) lane masks should be changed to be precise.

Allowing imprecise lane masks in case of more than 32 sub register lanes
lead to some tricky corner cases, and I need another bugfix for another
one. Instead I rather declare lane masks as precise and let tablegen
abort if we do not have enough bits.

This does not affect any in-tree target, even AMDGPU only needs 16 lanes
at the moment. If the 32 lanes turn out to be a problem in the future,
then we can easily change the LaneBitmask typedef to uint64_t.

[qcolombet]

Hi Matthias,

There are a few one line blocks with {} after your change that you should fix, but other than that LGTM!

Cheers,
-Quentin

llvm/trunk/include/llvm/Target/TargetRegisterInfo.h

 class BitVector;
 class MachineFunction;
 class RegScavenger;
 template<class T> class SmallVectorImpl;
 class VirtRegMap;
 class raw_ostream;
 class LiveRegMatrix;
 
-/// A bitmask representing the parts of a register are alive.
+/// A bitmask representing the covering of a register with sub-registers.
 ///
+/// This is typically used to track liveness at sub-register granularity.
 /// Lane masks for sub-register indices are similar to register units for
 /// physical registers. The individual bits in a lane mask can't be assigned
 /// any specific meaning. They can be used to check if two sub-register
 /// indices overlap.
 ///
-/// If the target has a register such that:
+/// Iff the target has a register such that:
 ///
 ///   getSubReg(Reg, A) overlaps getSubReg(Reg, B)
 ///
 /// then:
 ///
 ///   (getSubRegIndexLaneMask(A) & getSubRegIndexLaneMask(B)) != 0
-///
-/// The converse is not necessarily true. If two lane masks have a common
-/// bit, the corresponding sub-registers may not overlap, but it can be
-/// assumed that they usually will.
 typedef unsigned LaneBitmask;
 
 class TargetRegisterClass {
 public:
   typedef const MCPhysReg* iterator;
   typedef const MCPhysReg* const_iterator;
   typedef const MVT::SimpleValueType* vt_iterator;
   typedef const TargetRegisterClass* const * sc_iterator;
public:
   /// SubIdx \see LaneBitmask.
   ///
   /// SubIdx == 0 is allowed, it has the lane mask ~0u.
   LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const {
     assert(SubIdx < getNumSubRegIndices() && "This is not a subregister index");
     return SubRegIndexLaneMasks[SubIdx];
   }
 
-  /// Returns true if the given lane mask is imprecise.
-  ///
-  /// LaneMasks as given by getSubRegIndexLaneMask() have a limited number of
-  /// bits, so for targets with more than 31 disjunct subregister indices there
-  /// may be cases where:
-  ///    getSubReg(Reg,A) does not overlap getSubReg(Reg,B)
-  /// but we still have
-  ///    (getSubRegIndexLaneMask(A) & getSubRegIndexLaneMask(B)) != 0.
-  /// This function returns true in those cases.
-  static bool isImpreciseLaneMask(LaneBitmask LaneMask) {
-    return LaneMask & 0x80000000u;
-  }
-
   /// The lane masks returned by getSubRegIndexLaneMask() above can only be
   /// used to determine if sub-registers overlap - they can't be used to
   /// determine if a set of sub-registers completely cover another
   /// sub-register.
   ///
   /// The X86 general purpose registers have two lanes corresponding to the
   /// sub_8bit and sub_8bit_hi sub-registers. Both sub_32bit and sub_16bit have
   /// lane masks '3', but the sub_16bit sub-register doesn't fully cover the

llvm/trunk/lib/CodeGen/RegisterCoalescer.cpp

class RegisterCoalescer : public MachineFunctionPass,
     /// Attempt joining with a reserved physreg.
     bool joinReservedPhysReg(CoalescerPair &CP);
 
     /// Add the LiveRange @p ToMerge as a subregister liverange of @p LI.
     /// Subranges in @p LI which only partially interfere with the desired
     /// LaneMask are split as necessary. @p LaneMask are the lanes that
     /// @p ToMerge will occupy in the coalescer register. @p LI has its subrange
     /// lanemasks already adjusted to the coalesced register.
-    /// @returns false if live range conflicts couldn't get resolved.
-    bool mergeSubRangeInto(LiveInterval &LI, const LiveRange &ToMerge,
+    void mergeSubRangeInto(LiveInterval &LI, const LiveRange &ToMerge,
                            LaneBitmask LaneMask, CoalescerPair &CP);
 
     /// Join the liveranges of two subregisters. Joins @p RRange into
     /// @p LRange, @p RRange may be invalid afterwards.
-    /// @returns false if live range conflicts couldn't get resolved.
-    bool joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
+    void joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
                           LaneBitmask LaneMask, const CoalescerPair &CP);
 
     /// We found a non-trivially-coalescable copy. If the source value number is
     /// defined by a copy from the destination reg see if we can merge these two
     /// destination reg valno# into a single value number, eliminating a copy.
     /// This returns true if an interval was modified.
     bool adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI);
 
case CR_Erase: {
       break;
     }
     default:
       break;
     }
   }
 }
 
-bool RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
+void RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
                                          LaneBitmask LaneMask,
                                          const CoalescerPair &CP) {
   SmallVector<VNInfo*, 16> NewVNInfo;
   JoinVals RHSVals(RRange, CP.getSrcReg(), CP.getSrcIdx(), LaneMask,
                    NewVNInfo, CP, LIS, TRI, true, true);
   JoinVals LHSVals(LRange, CP.getDstReg(), CP.getDstIdx(), LaneMask,
                    NewVNInfo, CP, LIS, TRI, true, true);
 
   // Compute NewVNInfo and resolve conflicts (see also joinVirtRegs())
   // We should be able to resolve all conflicts here as we could successfully do
   // it on the mainrange already. There is however a problem when multiple
   // ranges get mapped to the "overflow" lane mask bit which creates unexpected
   // interferences.
   if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) {
-    DEBUG(dbgs() << "*** Couldn't join subrange!\n");
-    return false;
+    // We already determined that it is legal to merge the intervals, so this
+    // should never fail.
+    llvm_unreachable("*** Couldn't join subrange!\n");
   }
   if (!LHSVals.resolveConflicts(RHSVals) ||
       !RHSVals.resolveConflicts(LHSVals)) {
-    DEBUG(dbgs() << "*** Couldn't join subrange!\n");
-    return false;
+    // We already determined that it is legal to merge the intervals, so this
+    // should never fail.
+    llvm_unreachable("*** Couldn't join subrange!\n");
   }
 
   // The merging algorithm in LiveInterval::join() can't handle conflicting
   // value mappings, so we need to remove any live ranges that overlap a
   // CR_Replace resolution. Collect a set of end points that can be used to
   // restore the live range after joining.
   SmallVector<SlotIndex, 8> EndPoints;
   LHSVals.pruneValues(RHSVals, EndPoints, false);
   RHSVals.pruneValues(LHSVals, EndPoints, false);
 
   LHSVals.removeImplicitDefs();
   RHSVals.removeImplicitDefs();
 
   LRange.verify();
   RRange.verify();
 
   // Join RRange into LHS.
   LRange.join(RRange, LHSVals.getAssignments(), RHSVals.getAssignments(),
               NewVNInfo);
 
   DEBUG(dbgs() << "\t\tjoined lanes: " << LRange << "\n");
   if (EndPoints.empty())
-    return true;
+    return;
 
   // Recompute the parts of the live range we had to remove because of
   // CR_Replace conflicts.
   DEBUG(dbgs() << "\t\trestoring liveness to " << EndPoints.size()
                << " points: " << LRange << '\n');
   LIS->extendToIndices(LRange, EndPoints);
-  return true;
 }
 
-bool RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI,
+void RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI,
                                           const LiveRange &ToMerge,
                                           LaneBitmask LaneMask,
                                           CoalescerPair &CP) {
   BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
   for (LiveInterval::SubRange &R : LI.subranges()) {
     LaneBitmask RMask = R.LaneMask;
     // LaneMask of subregisters common to subrange R and ToMerge.
     LaneBitmask Common = RMask & LaneMask;
if (LRest != 0) {
       // Duplicate SubRange for newly merged common stuff.
       CommonRange = LI.createSubRangeFrom(Allocator, Common, R);
     } else {
       // Reuse the existing range.
       R.LaneMask = Common;
       CommonRange = &R;
     }
     LiveRange RangeCopy(ToMerge, Allocator);
-    if (!joinSubRegRanges(*CommonRange, RangeCopy, Common, CP))
-      return false;
+    joinSubRegRanges(*CommonRange, RangeCopy, Common, CP);
     LaneMask &= ~RMask;
   }
 
   if (LaneMask != 0) {
     DEBUG(dbgs() << "\t\tNew Lane " << PrintLaneMask(LaneMask) << '\n');
     LI.createSubRangeFrom(Allocator, LaneMask, ToMerge);
   }
-  return true;
 }
 
 bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) {
   SmallVector<VNInfo*, 16> NewVNInfo;
   LiveInterval &RHS = LIS->getInterval(CP.getSrcReg());
   LiveInterval &LHS = LIS->getInterval(CP.getDstReg());
   bool TrackSubRegLiveness = MRI->shouldTrackSubRegLiveness(*CP.getNewRC());
   JoinVals RHSVals(RHS, CP.getSrcReg(), CP.getSrcIdx(), 0, NewVNInfo, CP, LIS,
if (!LHS.hasSubRanges()) {
         R.LaneMask = Mask;
       }
     }
     DEBUG(dbgs() << "\t\tLHST = " << PrintReg(CP.getDstReg())
                  << ' ' << LHS << '\n');
 
     // Determine lanemasks of RHS in the coalesced register and merge subranges.
     unsigned SrcIdx = CP.getSrcIdx();
-    bool Abort = false;
     if (!RHS.hasSubRanges()) {
       LaneBitmask Mask = SrcIdx == 0 ? CP.getNewRC()->getLaneMask()
                                      : TRI->getSubRegIndexLaneMask(SrcIdx);
-      if (!mergeSubRangeInto(LHS, RHS, Mask, CP))
-        Abort = true;
+      mergeSubRangeInto(LHS, RHS, Mask, CP);
     } else {
       // Pair up subranges and merge.
       for (LiveInterval::SubRange &R : RHS.subranges()) {
         LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(SrcIdx, R.LaneMask);
-        if (!mergeSubRangeInto(LHS, R, Mask, CP)) {
-          Abort = true;
-          break;
-        }
+        mergeSubRangeInto(LHS, R, Mask, CP);
       }
     }
-    if (Abort) {
-      // This shouldn't have happened :-(
-      // However we are aware of at least one existing problem where we
-      // can't merge subranges when multiple ranges end up in the
-      // "overflow bit" 32. As a workaround we drop all subregister ranges
-      // which means we loose some precision but are back to a well defined
-      // state.
-      assert(TargetRegisterInfo::isImpreciseLaneMask(
-             CP.getNewRC()->getLaneMask())
-             && "SubRange merge should only fail when merging into bit 32.");
-      DEBUG(dbgs() << "\tSubrange join aborted!\n");
-      LHS.clearSubRanges();
-      RHS.clearSubRanges();
-    } else {
-      DEBUG(dbgs() << "\tJoined SubRanges " << LHS << "\n");
 
-      LHSVals.pruneSubRegValues(LHS, ShrinkMask);
-      RHSVals.pruneSubRegValues(LHS, ShrinkMask);
-    }
-  }
 
   // The merging algorithm in LiveInterval::join() can't handle conflicting
   // value mappings, so we need to remove any live ranges that overlap a
   // CR_Replace resolution. Collect a set of end points that can be used to
   // restore the live range after joining.
   SmallVector<SlotIndex, 8> EndPoints;
   LHSVals.pruneValues(RHSVals, EndPoints, true);
   RHSVals.pruneValues(LHSVals, EndPoints, true);

llvm/trunk/lib/CodeGen/VirtRegMap.cpp

for (MachineBasicBlock::instr_iterator
             if (MO.isUse()) {
               if (readsUndefSubreg(MO))
                 // We need to add an <undef> flag if the subregister is
                 // completely undefined (and we are not adding super-register
                 // defs).
                 MO.setIsUndef(true);
             } else if (!MO.isDead()) {
               assert(MO.isDef());
-              // Things get tricky when we ran out of lane mask bits and
-              // merged multiple lanes into the overflow bit: In this case
-              // our subregister liveness tracking isn't precise and we can't
-              // know what subregister parts are undefined, fall back to the
-              // implicit super-register def then.
-              LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg);
-              if (TargetRegisterInfo::isImpreciseLaneMask(LaneMask))
-                SuperDefs.push_back(PhysReg);
             }
           }
 
           // The <def,undef> flag only makes sense for sub-register defs, and
           // we are substituting a full physreg.  An <imp-use,kill> operand
           // from the SuperKills list will represent the partial read of the
           // super-register.
           if (MO.isDef())

llvm/trunk/utils/TableGen/CodeGenRegisters.cpp

 // some registers, but not in others. That shouldn't happen a lot.
 void CodeGenRegBank::computeSubRegLaneMasks() {
   // First assign individual bits to all the leaf indices.
   unsigned Bit = 0;
   // Determine mask of lanes that cover their registers.
   CoveringLanes = ~0u;
   for (auto &Idx : SubRegIndices) {
     if (Idx.getComposites().empty()) {
+      if (Bit > 32) {
+        PrintFatalError(
+          Twine("Ran out of lanemask bits to represent subregister ")
+          + Idx.getName());
+      }
       Idx.LaneMask = 1u << Bit;
-      // Share bit 31 in the unlikely case there are more than 32 leafs.
-      //
-      // Sharing bits is harmless; it allows graceful degradation in targets
-      // with more than 32 vector lanes. They simply get a limited resolution
-      // view of lanes beyond the 32nd.
-      //
-      // See also the comment for getSubRegIndexLaneMask().
-      if (Bit < 31)
-        ++Bit;
-      else
-        // Once bit 31 is shared among multiple leafs, the 'lane' it represents
-        // is no longer covering its registers.
-        CoveringLanes &= ~(1u << Bit);
     } else {
       Idx.LaneMask = 0;
     }
   }
 
   // Compute transformation sequences for composeSubRegIndexLaneMask. The idea
   // here is that for each possible target subregister we look at the leafs
   // in the subregister graph that compose for this target and create