No *reserved* physical registers in the VirtRegMap

[npjdesres]

Summary

(0) RegAllocPBQP: Since getRawAllocationOrder() may return a collection that includes reserved physical registers, iterate to find an un-reserved physical register.

(1) VirtRegMap: Enforce the invariant: "no reserved physical registers" in assignVirt2Phys(). Previously, this was checked only after the fact in VirtRegRewriter::rewrite.

(2) MachineVerifier: updated the test per MatzeB's review.

(3) +testcase

[MatzeB]

• The changes look fine to me (with an adjustment to the MachineVerifier change).
• Patches should be uploaded with full context (see http://www.llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface) to ease reviews next time.
• Try to use clang-format to adhere to llvms coding conventions (see also nitpicks below)
• I'd be fine committing the VirtRegMap/MachineVerifier fixes right away with the nitpicks addressed
• We usually add a testcase for bugfixes like the PBQP one, is there any way to create a testcase for llvm trunk to check the PBQP problem? You probably need to find a target having a register class starting with a reserved register, .mir tests should allow it to just run regallocpbqp + virtregmap. (If there is no such targets then we are probably out of luck).

include/llvm/CodeGen/VirtRegMap.h

105

looking at this we could also change unsigned physReg to MCPhysReg PhysReg to make the intention even more obvious.

lib/CodeGen/MachineVerifier.cpp

1966

I think the actual bug here is a few lines earlier where it says if (!PVNI && LaneMask.none()). I think this should better read:

// All predecessors must have a live-out value. However for a phi instruction with subregister intervals
// only one of the subregisters (not necessarily the current one) needs to be defined.
if (!PVNI && (LaneMask.none() || !IsPhi)) { ... }

lib/CodeGen/RegAllocPBQP.cpp

742

We add a space after for, and if. Could also use: for (unsigned CandidateReg : RawPRegOrder) { ... }

lib/CodeGen/VirtRegMap.cpp

81

No space after (

[npjdesres]

I am addressing your comments. I might be able to make a mips testcase...

Perhaps you expected this, but running these files through clang-format makes for very large diffs.

[MatzeB]

In D33947#774322, @npjdesres wrote:

I am addressing your comments. I might be able to make a mips testcase...

Perhaps you expected this, but running these files through clang-format makes for very large diffs.

Yes llvm code certainly isn't clang-format clean and we don't tend to clean up sourcefiles after the fact.
However new code added/code changed should adhere to our style guidelines.

You can probably consider it more of an independent 3rd party you can refer to when criticizing style in reviews rather than something we mechanically pipe all of sourcecode through :)
There are scripts like clang/tools/clang-format/git-clang-format that apply clang format just to the lines changed in a file. I personally tend to just use clang-format as a reference/learning tool.

[npjdesres]

Updated the patch to clang-format style guidelines. Updated the test in MachineVerifier.

I do not yet have a testcase. While trying to create a testcase for mips, I uncovered a different bug in the mips backend :-/ I'll submit a fix for the new bug shortly...

[npjdesres]

Added testcase.

The testcase assert-fails in VirtRegRewriter::rewrite before this patch.

After this patch the testcase lowers successfully.

[MatzeB]

LGTM

test/CodeGen/Generic/pbqp-reserved-physreg.ll

36–38

I assume the llvm.ident / !0 is not relevant for the test and can be removed.

[npjdesres]

Remove superfluous ident metadata from testcase.

MatzeB - thanks for the review. I don't have commit access. Would you mind? Thanks.

[MatzeB]

Thanks! I moved the testcase to test/CodeGen/Mips (it would fail in the generic directory for people/bots that have the mips target disabled in their build configuration).

[lhames]

Late to the party here, but this is great work - thanks!

include/llvm/CodeGen/VirtRegMap.h

public:
     /// virtual register
     unsigned getPhys(unsigned virtReg) const {
       assert(TargetRegisterInfo::isVirtualRegister(virtReg));
       return Virt2PhysMap[virtReg];
     }
 
     /// @brief creates a mapping for the specified virtual register to
     /// the specified physical register
-    void assignVirt2Phys(unsigned virtReg, unsigned physReg) {
-      assert(TargetRegisterInfo::isVirtualRegister(virtReg) &&
-             TargetRegisterInfo::isPhysicalRegister(physReg));
-      assert(Virt2PhysMap[virtReg] == NO_PHYS_REG &&
-             "attempt to assign physical register to already mapped "
-             "virtual register");
-      Virt2PhysMap[virtReg] = physReg;
-    }
+    void assignVirt2Phys(unsigned virtReg, MCPhysReg physReg);
 
     /// @brief clears the specified virtual register's, physical
     /// register mapping
     void clearVirt(unsigned virtReg) {
       assert(TargetRegisterInfo::isVirtualRegister(virtReg));
       assert(Virt2PhysMap[virtReg] != NO_PHYS_REG &&
              "attempt to clear a not assigned virtual register");
       Virt2PhysMap[virtReg] = NO_PHYS_REG;

lib/CodeGen/MachineVerifier.cpp

auto VerifyStackMapConstant = [&](unsigned Offset) {
         report("stack map constant to STATEPOINT not well formed!", MI);
     };
     const unsigned VarStart = StatepointOpers(MI).getVarIdx();
     VerifyStackMapConstant(VarStart + StatepointOpers::CCOffset);
     VerifyStackMapConstant(VarStart + StatepointOpers::FlagsOffset);
     VerifyStackMapConstant(VarStart + StatepointOpers::NumDeoptOperandsOffset);
 
     // TODO: verify we have properly encoded deopt arguments
-   
   };
 }
 
 void
 MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
   const MachineInstr *MI = MO->getParent();
   const MCInstrDesc &MCID = MI->getDesc();
   unsigned NumDefs = MCID.getNumDefs();
bool IsPHI = VNI->isPHIDef() &&
       VNI->def == LiveInts->getMBBStartIdx(&*MFI);
 
     // Check that VNI is live-out of all predecessors.
     for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(),
          PE = MFI->pred_end(); PI != PE; ++PI) {
       SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI);
       const VNInfo *PVNI = LR.getVNInfoBefore(PEnd);
 
-      // All predecessors must have a live-out value if this is not a
-      // subregister liverange.
-      if (!PVNI && LaneMask.none()) {
+      // All predecessors must have a live-out value. However for a phi
+      // instruction with subregister intervals
+      // only one of the subregisters (not necessarily the current one) needs to
+      // be defined.
+      if (!PVNI && (LaneMask.none() || !IsPHI) ) {
         report("Register not marked live out of predecessor", *PI);
         report_context(LR, Reg, LaneMask);
         report_context(*VNI);
         errs() << " live into BB#" << MFI->getNumber()
                << '@' << LiveInts->getMBBStartIdx(&*MFI) << ", not live before "
                << PEnd << '\n';
         continue;
       }
 
       // Only PHI-defs can take different predecessor values.
       if (!IsPHI && PVNI != VNI) {
         report("Different value live out of predecessor", *PI);
         report_context(LR, Reg, LaneMask);
         errs() << "Valno #" << PVNI->id << " live out of BB#"
                << (*PI)->getNumber() << '@' << PEnd << "\nValno #" << VNI->id
                << " live into BB#" << MFI->getNumber() << '@'
                << LiveInts->getMBBStartIdx(&*MFI) << '\n';
       }
     }
     if (&*MFI == EndMBB)
       break;

lib/CodeGen/RegAllocPBQP.cpp

for (RegSet::const_iterator
          I = EmptyIntervalVRegs.begin(), E = EmptyIntervalVRegs.end();
          I != E; ++I) {
     LiveInterval &LI = LIS.getInterval(*I);
 
     unsigned PReg = MRI.getSimpleHint(LI.reg);
 
     if (PReg == 0) {
       const TargetRegisterClass &RC = *MRI.getRegClass(LI.reg);
-      PReg = RC.getRawAllocationOrder(MF).front();
+      const ArrayRef<MCPhysReg> RawPRegOrder = RC.getRawAllocationOrder(MF);
+      for (unsigned CandidateReg : RawPRegOrder) {
+        if (!VRM.getRegInfo().isReserved(CandidateReg)) {
+          PReg = CandidateReg;
+          break;
+        }
+      }
+      assert(PReg &&
+             "No un-reserved physical registers in this register class");
     }
 
     VRM.assignVirt2Phys(LI.reg, PReg);
   }
 }
 
 void RegAllocPBQP::postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS) {
   VRegSpiller.postOptimization();

lib/CodeGen/VirtRegMap.cpp

 
 void VirtRegMap::grow() {
   unsigned NumRegs = MF->getRegInfo().getNumVirtRegs();
   Virt2PhysMap.resize(NumRegs);
   Virt2StackSlotMap.resize(NumRegs);
   Virt2SplitMap.resize(NumRegs);
 }
 
+void VirtRegMap::assignVirt2Phys(unsigned virtReg, MCPhysReg physReg) {
+  assert(TargetRegisterInfo::isVirtualRegister(virtReg) &&
+         TargetRegisterInfo::isPhysicalRegister(physReg));
+  assert(Virt2PhysMap[virtReg] == NO_PHYS_REG &&
+         "attempt to assign physical register to already mapped "
+         "virtual register");
+  assert(!getRegInfo().isReserved(physReg) &&
+         "Attempt to map virtReg to a reserved physReg");
+  Virt2PhysMap[virtReg] = physReg;
+}
+
 unsigned VirtRegMap::createSpillSlot(const TargetRegisterClass *RC) {
   unsigned Size = TRI->getSpillSize(*RC);
   unsigned Align = TRI->getSpillAlignment(*RC);
   int SS = MF->getFrameInfo().CreateSpillStackObject(Size, Align);
   ++NumSpillSlots;
   return SS;
 }
 

test/CodeGen/Generic/pbqp-reserved-physreg.ll

+; RUN: llc -march=mips -regalloc=pbqp <%s > %t
+; ModuleID = 'bugpoint-reduced-simplified.bc'
+
+; Function Attrs: nounwind
+define void @ham.928() local_unnamed_addr #0 align 2 {
+bb:
+  switch i32 undef, label %bb35 [
+    i32 1, label %bb18
+    i32 0, label %bb19
+    i32 3, label %bb20
+    i32 2, label %bb21
+    i32 4, label %bb17
+  ]
+
+bb17:                                             ; preds = %bb
+  unreachable
+
+bb18:                                             ; preds = %bb
+  unreachable
+
+bb19:                                             ; preds = %bb
+  unreachable
+
+bb20:                                             ; preds = %bb
+  unreachable
+
+bb21:                                             ; preds = %bb
+  unreachable
+
+bb35:                                             ; preds = %bb
+  unreachable
+}
+
+attributes #0 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="generic" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"DESRES-37 clang version 4.0.0  (based on LLVM 4.0.0)"}