Clarify semantic of reserved registers.

[MatzeB]

Summary

This commit should clarify semantics and issues related to reserved registers. Extend the machine verifier to check for the super register rule.

[arsenm]

include/llvm/Target/TargetRegisterInfo.h

492

s/life/live

[MatzeB]

This is an early patch to get the discussion going. Some things are still missing:

• A bunch of targets violate the superreg rule (e.g. AArch64 reserving XZR but not tuples like %XZR_X0). AArch64, ARM, Hexagon, Mips and PowerPC currently fail the verifier. So far it looks like actual target bugs to me.

• I think we should add this rule: "If a reserved subregister has subregister at least one subregister (or register unit) must be reserved", yes?

[arsenm]

In D26648#595163, @MatzeB wrote:

This is an early patch to get the discussion going. Some things are still missing:

• A bunch of targets violate the superreg rule (e.g. AArch64 reserving XZR but not tuples like %XZR_X0). AArch64, ARM, Hexagon, Mips and PowerPC currently fail the verifier. So far it looks like actual target bugs to me.

• I think we should add this rule: "If a reserved subregister has subregister at least one subregister (or register unit) must be reserved", yes?

AMDGPU has hit bugs from only reserving the super register before, and not the subregisters

[MatzeB]

Update comment, include the "at least 1 subregister must be reserved rule".

For the next version: I will add the check for the 1 subregister reserved rule; I'll move the checking from the machine verifier into MachineRegisterInfo::freezeReserved() (under #ifndef NDEBUG of course).

[qcolombet]

Hi Matthias,

Thanks for clarifying that. That could lead to subtle bugs :).

I miss one thing in this patch: a helper function that given a set of reserved registers adds the super registers (transitively). Then hint in the comment that TargetRegisterInfo::getReservedRegs could use such helper.

Cheers,
-Quentin

include/llvm/Target/TargetRegisterInfo.h

496

Looks good to me.

[MatzeB]

In D26648#595284, @qcolombet wrote:

Hi Matthias,

Thanks for clarifying that. That could lead to subtle bugs :).

I miss one thing in this patch: a helper function that given a set of reserved registers adds the super registers (transitively). Then hint in the comment that TargetRegisterInfo::getReservedRegs could use such helper.

Indeed, I am currently fixing the existing targets and added such a function for them anyway. BTW: It seems most of the problems are benign, a common pattern is the 64bit registers not getting reserved in 32bit mode. That should be fine as you probably won't see a 64bit operand in 32bit mode anyway. However fixing it properly is worth it so we can add the checking/assert.

Cheers,
-Quentin

[MatzeB]

These new rules break existing use in Mips :-(

Mips has 32bit floatregs F0-F31, each pair forms a double reg (F0+F1=D0, F2+F3=D1, ...). There is an option in the mips backend that aims at disabling the odd F registers, so 32bit float values only end up in F0, F2, F4, ... In this case it is actually expected that the register allocator still assigns the D0-D15 as usual even though the would indirectly use F1,F3,...

Is there another way to handle this in the mips target?

[escha]

Thanks for looking into this painful little bundle of nested semantic problems.

[sdardis]

@MatzeB Yes, we could rework the floating point register set definitions and instruction definitions to use difference register classes depending the floating point ABI used. Unfortunately this requires six register classes in that case, three for the no odd single precision case and 3 more for the case where odd single precisions are available. Those register classes would eliminate the need to reserve the odd registers for no-oddsp.

That's a non-trivial change which will take some time as other plumbing may need to be fixed/changed.

Some background:
The difficulty/delay arises in that MIPS has several different FPU configurations: 32bit FPUs supporting 64bit operations using a pair of single precision registers, and full 64bit FPUs. We have two floating pointing ABIs: nooddsp where the odd single precision registers are not to be used at all, and oddsp where all single precision registers can be used.

[MatzeB]

In D26648#595589, @sdardis wrote:

@MatzeB Yes, we could rework the floating point register set definitions and instruction definitions to use difference register classes depending the floating point ABI used. Unfortunately this requires six register classes in that case, three for the no odd single precision case and 3 more for the case where odd single precisions are available. Those register classes would eliminate the need to reserve the odd registers for no-oddsp.

That's a non-trivial change which will take some time as other plumbing may need to be fixed/changed.

Some background:
The difficulty/delay arises in that MIPS has several different FPU configurations: 32bit FPUs supporting 64bit operations using a pair of single precision registers, and full 64bit FPUs. We have two floating pointing ABIs: nooddsp where the odd single precision registers are not to be used at all, and oddsp where all single precision registers can be used.

Hi,

after working on this for a while I think the proposed rules here should rather be guidelines. They are the right thing in many situations, but not all. I reworked the commit in a way that backends can call assertAllSuperRegsMarked() at their own discretion.

[MatzeB]

• Make the rules less strict, marking superregs is only a recommendation now
• Add convenience functions so that it is easy in a target to mark all super regs and to verify whether all super regs are marked
• Fix a bug where AArch64 did not reserve tuples containing the zero register

[MatzeB]

Cleanup, remove some accidentally included changes.

[kparzysz]

include/llvm/Target/TargetRegisterInfo.h

493

If it's ignored by liveness tracking, then there is no meaning to "live" or "dead". Maybe you could rephrase it (and the previous bullet) as something like "is ignored from the liveness point of view".

496

This should be a standalone sentence, not a bullet in the list.

[MatzeB]

include/llvm/Target/TargetRegisterInfo.h

493

If you take a usual liveness definition of the value will potentially be read, then they are very much live.
It's just the actual implementation of liveness tracking in LLVM that decides to not track the liveness (we avoid adding special rules for reserved regs for little gain).

496

ok.

[arsenm]

lib/CodeGen/TargetRegisterInfo.cpp

43–47

This is almost the same as SIRegisterInfo::reserveRegisterTuples, except that uses MCRegAliasIterator. Is there any real difference?

[MatzeB]

lib/CodeGen/TargetRegisterInfo.cpp

43–47

Given that there are no arbitrary alias definitions in your target (I see no Aliases = in your tablegen files) it has the same effect as long as you only apply it to lowest level registers and not to a tuple.

[qcolombet]

include/llvm/Target/TargetRegisterInfo.h

950

We miss a return here or change the comment.

950

What about cases where we have mixed uses:

• Reserved as name; only the tagged name must be reserved (e.g., x86, mips, like you told me about)
• Reserved by ABI; all the super reg must be marked as reserved

This API does not all to check that.

[MatzeB]

• Add a way to specify a list of exceptions for assertSuperRegsMarked() so we can use it in situations like X86 as well.

[MatzeB]

Fix problem in assertAllSuperRegsMarked() exception handling.

[MatzeB]

ping

[qcolombet]

Hi Matthias,

LGTM.
One suggestion though.

Cheers,
-Quentin

include/llvm/Target/TargetRegisterInfo.h

950

I'd change the API a bit:

• Rename in checkAllSuperRegsMarked
• Return bool
• Have the users assert on that bool.

The rationale is that in release build assert(checkAllSuperRegsMarked) can be optimized out, but assertAllSuperRegsMarked would still cause a call to an empty function.

[MatzeB]

include/llvm/Target/TargetRegisterInfo.h

950

Actually my first version returned a bool and had the assert() on the caller. I changed my mind because I wanted the display a message listing the register causing the problem and writing to stderr in a check function felt wrong. Would you think writing to stderr is fine anyway? Or should I just get rid of the message and have people figure out the problematic register in a debugger?

include/llvm/Target/TargetRegisterInfo.h

public:
   bool regmaskSubsetEqual(const uint32_t *mask0, const uint32_t *mask1) const;
 
   /// Return all the call-preserved register masks defined for this target.
   virtual ArrayRef<const uint32_t *> getRegMasks() const = 0;
   virtual ArrayRef<const char *> getRegMaskNames() const = 0;
 
   /// Returns a bitset indexed by physical register number indicating if a
   /// register is a special register that has particular uses and should be
-  /// considered unavailable at all times, e.g. SP, RA. This is
-  /// used by register scavenger to determine what registers are free.
+  /// considered unavailable at all times, e.g. stack pointer, return address.
+  /// A reserved register:
+  /// - is not allocatable
+  /// - is considered always live
+  /// - is ignored by liveness tracking
+  /// - It is often necessary to reserve the super registers of a reserved
+  ///   register as well, to avoid them getting allocated indirectly. You may
+  ///   use markSuperRegs() and assertAllSuperRegsMarked() in this case.
   virtual BitVector getReservedRegs(const MachineFunction &MF) const = 0;
 
   /// Returns true if PhysReg is unallocatable and constant throughout the
   /// function.  Used by MachineRegisterInfo::isConstantPhysReg().
   virtual bool isConstantPhysReg(unsigned PhysReg) const { return false; }
 
   /// Prior to adding the live-out mask to a stackmap or patchpoint
   /// instruction, provide the target the opportunity to adjust it (mainly to
public:
   { return true; }
 
   //===--------------------------------------------------------------------===//
   /// Debug information queries.
 
   /// getFrameRegister - This method should return the register used as a base
   /// for values allocated in the current stack frame.
   virtual unsigned getFrameRegister(const MachineFunction &MF) const = 0;
+
+  /// Mark a register and all its aliases as reserved in the given set.
+  void markSuperRegs(BitVector &RegisterSet, unsigned Reg) const;
+
+  /// Returns true if for every register in the set all super registers are part
+  /// of the set as well.
+  void assertAllSuperRegsMarked(const BitVector &RegisterSet) const;
 };
 
 
 //===----------------------------------------------------------------------===//
 //                           SuperRegClassIterator
 //===----------------------------------------------------------------------===//
 //
 // Iterate over the possible super-registers for a given register class. The

lib/CodeGen/MachineVerifier.cpp

for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
       markReachable(*SuI);
   }
 }
 
 void MachineVerifier::visitMachineFunctionBefore() {
   lastIndex = SlotIndex();
   regsReserved = MRI->getReservedRegs();
 
-  // A sub-register of a reserved register is also reserved
-  for (int Reg = regsReserved.find_first(); Reg>=0;
-       Reg = regsReserved.find_next(Reg)) {
-    for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
-      // FIXME: This should probably be:
-      // assert(regsReserved.test(*SubRegs) && "Non-reserved sub-register");
-      regsReserved.set(*SubRegs);
-    }
-  }
-
   markReachable(&MF->front());
 
   // Build a set of the basic blocks in the function.
   FunctionBlocks.clear();
   for (const auto &MBB : *MF) {
     FunctionBlocks.insert(&MBB);
     BBInfo &MInfo = MBBInfoMap[&MBB];
 

lib/CodeGen/TargetRegisterInfo.cpp

TargetRegisterInfo::TargetRegisterInfo(const TargetRegisterInfoDesc *ID,
   : InfoDesc(ID), SubRegIndexNames(SRINames),
     SubRegIndexLaneMasks(SRILaneMasks),
     RegClassBegin(RCB), RegClassEnd(RCE),
     CoveringLanes(SRICoveringLanes) {
 }
 
 TargetRegisterInfo::~TargetRegisterInfo() {}
 
+void TargetRegisterInfo::markSuperRegs(BitVector &RegisterSet, unsigned Reg)
+    const {
+  for (MCSuperRegIterator AI(Reg, this, true); AI.isValid(); ++AI)
+    RegisterSet.set(*AI);
+}
+
+void TargetRegisterInfo::assertAllSuperRegsMarked(const BitVector &RegisterSet)
+    const {
+#ifndef NDEBUG
+  // Check that all super registers of reserved regs are reserved as well.
+  BitVector Checked(getNumRegs());
+  for (int Reg = RegisterSet.find_first(); Reg>=0;
+       Reg = RegisterSet.find_next(Reg)) {
+    if (Checked[Reg])
+      continue;
+    for (MCSuperRegIterator SR(Reg, this); SR.isValid(); ++SR) {
+      if (!RegisterSet[*SR]) {
+        errs() << "Error: Super register " << PrintReg(*SR, this)
+               << " of reserved register " << PrintReg(Reg, this)
+               << " is not reserved.\n";
+        report_fatal_error("Invalid register info.");
+      }
+
+      // We transitively check superregs. So we can remember this for later
+      // to avoid compiletime explosion in deep register hierarchies.
+      Checked.set(*SR);
+    }
+  }
+#endif
+}
+
 namespace llvm {
 
 Printable PrintReg(unsigned Reg, const TargetRegisterInfo *TRI,
                    unsigned SubIdx) {
   return Printable([Reg, TRI, SubIdx](raw_ostream &OS) {
     if (!Reg)
       OS << "%noreg";
     else if (TargetRegisterInfo::isStackSlot(Reg))

lib/Target/AArch64/AArch64RegisterInfo.cpp

 }
 
 BitVector
 AArch64RegisterInfo::getReservedRegs(const MachineFunction &MF) const {
   const AArch64FrameLowering *TFI = getFrameLowering(MF);
 
   // FIXME: avoid re-calculating this every time.
   BitVector Reserved(getNumRegs());
-  Reserved.set(AArch64::SP);
-  Reserved.set(AArch64::XZR);
-  Reserved.set(AArch64::WSP);
-  Reserved.set(AArch64::WZR);
+  markSuperRegs(Reserved, AArch64::SP);
+  markSuperRegs(Reserved, AArch64::XZR);
+  markSuperRegs(Reserved, AArch64::WSP);
+  markSuperRegs(Reserved, AArch64::WZR);
 
   if (TFI->hasFP(MF) || TT.isOSDarwin()) {
-    Reserved.set(AArch64::FP);
-    Reserved.set(AArch64::W29);
+    markSuperRegs(Reserved, AArch64::FP);
+    markSuperRegs(Reserved, AArch64::W29);
   }
 
   if (MF.getSubtarget<AArch64Subtarget>().isX18Reserved()) {
-    Reserved.set(AArch64::X18); // Platform register
-    Reserved.set(AArch64::W18);
+    markSuperRegs(Reserved, AArch64::X18); // Platform register
+    markSuperRegs(Reserved, AArch64::W18);
   }
 
   if (hasBasePointer(MF)) {
-    Reserved.set(AArch64::X19);
-    Reserved.set(AArch64::W19);
+    markSuperRegs(Reserved, AArch64::X19);
+    markSuperRegs(Reserved, AArch64::W19);
   }
 
+  assertAllSuperRegsMarked(Reserved);
   return Reserved;
 }
 
 bool AArch64RegisterInfo::isReservedReg(const MachineFunction &MF,
                                       unsigned Reg) const {
   const AArch64FrameLowering *TFI = getFrameLowering(MF);
 
   switch (Reg) {

lib/Target/ARM/ARMBaseRegisterInfo.cpp

 
 BitVector ARMBaseRegisterInfo::
 getReservedRegs(const MachineFunction &MF) const {
   const ARMSubtarget &STI = MF.getSubtarget<ARMSubtarget>();
   const ARMFrameLowering *TFI = getFrameLowering(MF);
 
   // FIXME: avoid re-calculating this every time.
   BitVector Reserved(getNumRegs());
-  Reserved.set(ARM::SP);
-  Reserved.set(ARM::PC);
-  Reserved.set(ARM::FPSCR);
-  Reserved.set(ARM::APSR_NZCV);
+  markSuperRegs(Reserved, ARM::SP);
+  markSuperRegs(Reserved, ARM::PC);
+  markSuperRegs(Reserved, ARM::FPSCR);
+  markSuperRegs(Reserved, ARM::APSR_NZCV);
   if (TFI->hasFP(MF))
-    Reserved.set(getFramePointerReg(STI));
+    markSuperRegs(Reserved, getFramePointerReg(STI));
   if (hasBasePointer(MF))
-    Reserved.set(BasePtr);
+    markSuperRegs(Reserved, BasePtr);
   // Some targets reserve R9.
   if (STI.isR9Reserved())
-    Reserved.set(ARM::R9);
+    markSuperRegs(Reserved, ARM::R9);
   // Reserve D16-D31 if the subtarget doesn't support them.
   if (!STI.hasVFP3() || STI.hasD16()) {
     static_assert(ARM::D31 == ARM::D16 + 15, "Register list not consecutive!");
-    Reserved.set(ARM::D16, ARM::D31 + 1);
+    for (unsigned R = 0; R < 16; ++R)
+      markSuperRegs(Reserved, ARM::D16 + R);
   }
   const TargetRegisterClass *RC  = &ARM::GPRPairRegClass;
   for(TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I!=E; ++I)
     for (MCSubRegIterator SI(*I, this); SI.isValid(); ++SI)
-      if (Reserved.test(*SI)) Reserved.set(*I);
+      if (Reserved.test(*SI)) markSuperRegs(Reserved, *I);
 
+  assertAllSuperRegsMarked(Reserved);
   return Reserved;
 }
 
 const TargetRegisterClass *
 ARMBaseRegisterInfo::getLargestLegalSuperClass(const TargetRegisterClass *RC,
                                                const MachineFunction &) const {
   const TargetRegisterClass *Super = RC;
   TargetRegisterClass::sc_iterator I = RC->getSuperClasses();