MIR Statepoint refactoring. Part 2: Operand folding.

[dantrushin]

Summary

Add support for Statepoint operand folding (replacing VReg with
memory operand). This allowed for InlineSpiller only, because it
knows how to reload tied def VReg after it was turned into memory
operand. Other callers (e.g. peephole) cannot do such reload.
We do this by un-tieing operand we want to fold in InlineSpiller
and allowing to fold only untied operands.

Full change set is available at D81603.

[reames]

I can't wrap my head around why untieing operands would be correct here. It seems like we could end up with a use folded, but a def not leaving to invalid codegen? Can you either expand on the justification or discuss offline?

[dantrushin]

In D81646#2091262, @reames wrote:

I can't wrap my head around why untieing operands would be correct here. It seems like we could end up with a use folded, but a def not leaving to invalid codegen? Can you either expand on the justification or discuss offline?

The key point here is that we have two-address form at this point (not SSA, i.e. register on both sides is the same: vreg1 = STATEPOINT vreg1<tied-def0>).
foldMemoryOperand is called from spillAroundUses in InlineSpiller. And this method (besides few other optimizations) for every VReg use tries to fold register into memory operand or, if unsuccessful, inserts reload before instruction.
In some sense it turns VReg into StackSlot. And since Def of stack slot is invisible to LLVM (just like with old statepoint), it "magically" works.

[reames]

In D81646#2092782, @dantrushin wrote:

In D81646#2091262, @reames wrote:

I can't wrap my head around why untieing operands would be correct here. It seems like we could end up with a use folded, but a def not leaving to invalid codegen? Can you either expand on the justification or discuss offline?

The key point here is that we have two-address form at this point (not SSA, i.e. register on both sides is the same: vreg1 = STATEPOINT vreg1<tied-def0>).
foldMemoryOperand is called from spillAroundUses in InlineSpiller. And this method (besides few other optimizations) for every VReg use tries to fold register into memory operand or, if unsuccessful, inserts reload before instruction.
In some sense it turns VReg into StackSlot. And since Def of stack slot is invisible to LLVM (just like with old statepoint), it "magically" works.

But you're converting an instruction which defines a vreg to one which doesn't. If the original definition vreg had uses, isn't this a miscompile?

vreg1 = statepoint .... vreg1 (tied)
vreg2 = ADDri vreg1, 20

>

statepoint ... [FI]
vreg2 = ADDri vreg1, 20 <-- What's the value of vreg1 here?

We could insert a fill after the folded statepoint, but I don't see code which does that?

[dantrushin]

InlineSpiller::spillAroundUses folds/spills ALL concurrences of vreg1 , so it will turn

vreg1 = statepoint .... vreg1 (tied)
vreg2 = ADDri vreg1, 20

into

statepoint ... [FI]
vreg2 = ADDmi [FI], 20

In case folding fails, it will insert reload before use.

[dantrushin]

Add test demonstrating statepoint operand folding.

[reames]

LGTM. I sat down today to write a cleaner patch, and in the process convinced myself this was in fact correct. I will post a separate cleanup once this lands as I think we can have the foldMemoryOperand impl structured much more cleanly for tied operands, but doing so involves a slightly deeper rewrite of some x86 specific code than is reasonable to ask for here.

Please address the inline comments in this review when landing.

I would also encourage - but not require - you to fix 46916 in a separate patch before landing this. I see that the tied argument propagation herein should fix that, but splitting the patch into "fold deopt w/vregs present" and "fold vreg gc operand" would make it much easier for anyone following along.

llvm/lib/CodeGen/InlineSpiller.cpp

813

Please add a comment explaining assumption here.

llvm/lib/CodeGen/TargetInstrInfo.cpp

502–511

Please add an assert that DefToFoldIdx == e. That is, there's at most one def op per fold operation. The code below would miscompile a multiple def fold.

506

I don't believe this line or comment are necessary. Please remove if make check passes; if not, I will handle in follow up.

optimizeMemoryInst (the peephole entry point) rejects all defs, not just tied defs.

[dantrushin]

peephole.mir7 KBDownload

Attached test will explode if isTied check is removed as suggested.
Essential part is:

%10:gr64 = MOV64rm killed %9, 1, $noreg, 0, $noreg :: (load 8 from %ir.p0, addrspace 1)
%6:gr64, %7:gr64 = STATEPOINT 0, 0, 0, @foo, 2, 0, 2, 0, 2, 0, %8, %8(tied-def 0), killed %10, %0(tied-def 1), ...

It is synthetic (i.e. we do no generate such MIR from any IR), but still not invalid

llvm/lib/CodeGen/TargetInstrInfo.cpp

506

I don't believe this line or comment are necessary. Please remove if make check passes; if not, I will handle in follow up.

optimizeMemoryInst (the peephole entry point) rejects all defs, not just tied defs.

The possible path is:

PeepholeOptimizer::runOnMachineFunction (!isLoadFoldable() branch) ->
X86InstrInfo::optimizeLoadInstr ->
TargetInstrInfo::foldMemoryOperand ->
TargetInstrInfo::foldPatchpoint (here)

The fact this path is not exercised now is implementation detail (it did with earlier versions of ISEL patch).
I think we should keep this check to stay on the safe side.

[dantrushin]

https://reviews.llvm.org/rGd21ce4082181

llvm/lib/CodeGen/InlineSpiller.cpp

foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>> Ops,
   // Don't attempt folding in bundles.
   MachineInstr *MI = Ops.front().first;
   if (Ops.back().first != MI || MI->isBundled())
     return false;
 
   bool WasCopy = MI->isCopy();
   unsigned ImpReg = 0;
 
+  bool UntieRegs = MI->getOpcode() == TargetOpcode::STATEPOINT;
+
   // Spill subregs if the target allows it.
   // We always want to spill subregs for stackmap/patchpoint pseudos.
   bool SpillSubRegs = TII.isSubregFoldable() ||
                       MI->getOpcode() == TargetOpcode::STATEPOINT ||
                       MI->getOpcode() == TargetOpcode::PATCHPOINT ||
                       MI->getOpcode() == TargetOpcode::STACKMAP;
 
   // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied
   // operands.
   SmallVector<unsigned, 8> FoldOps;
   for (const auto &OpPair : Ops) {
     unsigned Idx = OpPair.second;
     assert(MI == OpPair.first && "Instruction conflict during operand folding");
     MachineOperand &MO = MI->getOperand(Idx);
     if (MO.isImplicit()) {
       ImpReg = MO.getReg();
       continue;
     }
 
+    if (UntieRegs && MO.isTied())
+      MI->untieRegOperand(Idx);
+
     if (!SpillSubRegs && MO.getSubReg())
       return false;
     // We cannot fold a load instruction into a def.
     if (LoadMI && MO.isDef())
       return false;
     // Tied use operands should not be passed to foldMemoryOperand.
     if (!MI->isRegTiedToDefOperand(Idx))
       FoldOps.push_back(Idx);

llvm/lib/CodeGen/TargetInstrInfo.cpp

 void TargetInstrInfo::getNoop(MCInst &NopInst) const {
   llvm_unreachable("Not implemented");
 }
 
 static MachineInstr *foldPatchpoint(MachineFunction &MF, MachineInstr &MI,
                                     ArrayRef<unsigned> Ops, int FrameIndex,
                                     const TargetInstrInfo &TII) {
   unsigned StartIdx = 0;
+  unsigned NumDefs = 0;
   switch (MI.getOpcode()) {
   case TargetOpcode::STACKMAP: {
     // StackMapLiveValues are foldable
     StartIdx = StackMapOpers(&MI).getVarIdx();
     break;
   }
   case TargetOpcode::PATCHPOINT: {
     // For PatchPoint, the call args are not foldable (even if reported in the
     // stackmap e.g. via anyregcc).
     StartIdx = PatchPointOpers(&MI).getVarIdx();
     break;
   }
   case TargetOpcode::STATEPOINT: {
     // For statepoints, fold deopt and gc arguments, but not call arguments.
     StartIdx = StatepointOpers(&MI).getVarIdx();
+    NumDefs = MI.getNumDefs();
     break;
   }
   default:
     llvm_unreachable("unexpected stackmap opcode");
   }
 
+  unsigned DefToFoldIdx = MI.getNumOperands();
+
   // Return false if any operands requested for folding are not foldable (not
   // part of the stackmap's live values).
   for (unsigned Op : Ops) {
-    if (Op < StartIdx)
+    if (Op < NumDefs)
+      DefToFoldIdx = Op;
+    else if (Op < StartIdx)
+      return nullptr;
+    // When called from regalloc (InlineSpiller), operands must be untied,
+    // and regalloc will take care of (re)loading operand from memory.
+    // But when called from other places (e.g. peephole pass),
+    // we cannot fold operand which are tied - callers are unaware they
+    // need to reload destination register.
+    if (MI.getOperand(Op).isTied())
       return nullptr;
   }
 
   MachineInstr *NewMI =
       MF.CreateMachineInstr(TII.get(MI.getOpcode()), MI.getDebugLoc(), true);
   MachineInstrBuilder MIB(MF, NewMI);
 
   // No need to fold return, the meta data, and function arguments
   for (unsigned i = 0; i < StartIdx; ++i)
+    if (i != DefToFoldIdx)
       MIB.add(MI.getOperand(i));
 
-  for (unsigned i = StartIdx; i < MI.getNumOperands(); ++i) {
+  for (unsigned i = StartIdx, e = MI.getNumOperands(); i < e; ++i) {
     MachineOperand &MO = MI.getOperand(i);
+    unsigned TiedTo = e;
+    (void)MI.isRegTiedToDefOperand(i, &TiedTo);
+
     if (is_contained(Ops, i)) {
+      assert(TiedTo == e && "Cannot fold tied operands");
       unsigned SpillSize;
       unsigned SpillOffset;
       // Compute the spill slot size and offset.
       const TargetRegisterClass *RC =
         MF.getRegInfo().getRegClass(MO.getReg());
       bool Valid =
           TII.getStackSlotRange(RC, MO.getSubReg(), SpillSize, SpillOffset, MF);
       if (!Valid)
         report_fatal_error("cannot spill patchpoint subregister operand");
       MIB.addImm(StackMaps::IndirectMemRefOp);
       MIB.addImm(SpillSize);
       MIB.addFrameIndex(FrameIndex);
       MIB.addImm(SpillOffset);
-    }
-    else
+    } else {
       MIB.add(MO);
+      if (TiedTo < e) {
+        assert(TiedTo < NumDefs && "Bad tied operand");
+        if (TiedTo > DefToFoldIdx)
+          --TiedTo;
+        NewMI->tieOperands(TiedTo, NewMI->getNumOperands() - 1);
+      }
+    }
   }
   return NewMI;
 }
 
 MachineInstr *TargetInstrInfo::foldMemoryOperand(MachineInstr &MI,
                                                  ArrayRef<unsigned> Ops, int FI,
                                                  LiveIntervals *LIS,
                                                  VirtRegMap *VRM) const {