VirtRegMap: Add undef flag when reading undefined subregisters.

[MatzeB]

As for a testcase: I couldn't create a test with any no in-tree target where the undef reads wouldn't be optimized away earlier.

[qcolombet]

Hi Matthias,

LGTM with a couple of comments.

Cheers,
-Quentin

lib/CodeGen/RegisterCoalescer.cpp

2637

Not a big deal, but I’d do the API update as a separate commit.
Now, it feels kind of strange to have a coalescer change given we are fixing the VirtRegMap :).

lib/CodeGen/VirtRegMap.cpp

301

Add a message in the assert, like precondition is violated, subreg must be != 0.

include/llvm/Target/TargetRegisterInfo.h

public:
   /// bit, the corresponding sub-registers may not overlap, but it can be
   /// assumed that they usually will.
   /// SubIdx == 0 is allowed, it has the lane mask ~0u.
   unsigned 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 there may be cases where:
+  ///    getSubReg(Reg,A) does not overlap getSubReg(Reg,B)
+  /// but we still have
+  ///    (getSubRegIndexLaneMask(A) & getSubRegIndexLaneMask(B)) != 0.
+  /// (Currently this only happens when the target has more than 31 disjunct
+  ///  subregister indices)
+  static bool isImpreciseLaneMask(unsigned 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

lib/CodeGen/RegisterCoalescer.cpp

if (RHS.hasSubRanges() || LHS.hasSubRanges()) {
     }
     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((CP.getNewRC()->getLaneMask() & 0x80000000u)
+      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);

lib/CodeGen/VirtRegMap.cpp

class VirtRegRewriter : public MachineFunctionPass {
   MachineRegisterInfo *MRI;
   SlotIndexes *Indexes;
   LiveIntervals *LIS;
   VirtRegMap *VRM;
   SparseSet<unsigned> PhysRegs;
 
   void rewrite();
   void addMBBLiveIns();
+  bool readsUndefSubreg(const MachineOperand &MO) const;
 public:
   static char ID;
   VirtRegRewriter() : MachineFunctionPass(ID) {}
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   bool runOnMachineFunction(MachineFunction&) override;
 };
void VirtRegRewriter::addMBBLiveIns() {
   }
 
   // Sort and unique MBB LiveIns as we've not checked if SubReg/PhysReg were in
   // each MBB's LiveIns set before calling addLiveIn on them.
   for (MachineBasicBlock &MBB : *MF)
     MBB.sortUniqueLiveIns();
 }
 
+/// Return true if the given machine operand \p MO - which must be a subregister
+/// use - only reads undefined lanes.
+bool VirtRegRewriter::readsUndefSubreg(const MachineOperand &MO) const {
+  // Shortcut if the operand is already marked undef.
+  if (MO.isUndef())
+    return true;
+
+  unsigned Reg = MO.getReg();
+  unsigned SubRegIdx = MO.getSubReg();
+  assert(SubRegIdx != 0);
+  const MachineInstr &MI = *MO.getParent();
+  SlotIndex BaseIndex = LIS->getInstructionIndex(&MI);
+  const LiveInterval &LI = LIS->getInterval(Reg);
+  // This code is only meant to handle reading undefined subregisters which
+  // we couldn't properly detect before.
+  assert(LI.liveAt(BaseIndex) &&
+         "Reads of completely dead register should be marked undef already");
+  unsigned UseMask = TRI->getSubRegIndexLaneMask(SubRegIdx);
+  // See if any of the relevant subregister liveranges is defined at this point.
+  for (const LiveInterval::SubRange &SR : LI.subranges()) {
+    if ((SR.LaneMask & UseMask) == 0)
+      continue;
+    if (SR.liveAt(BaseIndex))
+      return false;
+  }
+  return true;
+}
+
 void VirtRegRewriter::rewrite() {
   bool NoSubRegLiveness = !MRI->subRegLivenessEnabled();
   SmallVector<unsigned, 8> SuperDeads;
   SmallVector<unsigned, 8> SuperDefs;
   SmallVector<unsigned, 8> SuperKills;
   SmallPtrSet<const MachineInstr *, 4> NoReturnInsts;
 
   // Here we have a SparseSet to hold which PhysRegs are actually encountered
for (MachineBasicBlock::instr_iterator
           continue;
         unsigned VirtReg = MO.getReg();
         unsigned PhysReg = VRM->getPhys(VirtReg);
         assert(PhysReg != VirtRegMap::NO_PHYS_REG &&
                "Instruction uses unmapped VirtReg");
         assert(!MRI->isReserved(PhysReg) && "Reserved register assignment");
 
         // Preserve semantics of sub-register operands.
-        if (MO.getSubReg()) {
+        unsigned SubReg = MO.getSubReg();
+        if (SubReg != 0) {
+          if (NoSubRegLiveness) {
             // A virtual register kill refers to the whole register, so we may
             // have to add <imp-use,kill> operands for the super-register.  A
             // partial redef always kills and redefines the super-register.
-          if (NoSubRegLiveness && MO.readsReg()
-              && (MO.isDef() || MO.isKill()))
+            if (MO.readsReg() && (MO.isDef() || MO.isKill()))
               SuperKills.push_back(PhysReg);
 
-          if (MO.isDef()) {
-            // 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.
-            MO.setIsUndef(false);
-
             // Also add implicit defs for the super-register.
-            if (NoSubRegLiveness) {
-              if (MO.isDead())
-                SuperDeads.push_back(PhysReg);
-              else
-                SuperDefs.push_back(PhysReg);
+          } else {
+            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.
+              unsigned 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())
+            MO.setIsUndef(false);
+
           // PhysReg operands cannot have subregister indexes.
-          PhysReg = TRI->getSubReg(PhysReg, MO.getSubReg());
+          PhysReg = TRI->getSubReg(PhysReg, SubReg);
           assert(PhysReg && "Invalid SubReg for physical register");
           MO.setSubReg(0);
         }
         // Rewrite. Note we could have used MachineOperand::substPhysReg(), but
         // we need the inlining here.
         MO.setReg(PhysReg);
       }