MachineSink: permit sinking into INLINEASM_BR indirect targets

[nickdesaulniers]

Summary

Fixes a kernel panic for 4.4 LTS x86_64 Linux kernels.

Fixes: D79794
Link: https://github.com/ClangBuiltLinux/linux/issues/1085
Signed-off-by: Nick Desaulniers <[e-mail]>

[nickdesaulniers]

From the comment, there's obviously more we want to do here. Posting what I have for today since it's EOD. Will iterate on feedback tomorrow.

[void]

I'm confused by this change. The original code *should* be correct. That it's resulting in this issue is another thing.

My first question is, why are we trying to sink instructions into the entry block?

[void]

Without this change, the "ADD64ri8" instruction is before the INLINEASM_BR before machine sinking.

[jyknight]

It looks like the issue shown in this test-case appears in Two-Address instruction pass, not Machine Sink.

We go from:

bb.0 (%ir-block.1):
  successors: %bb.2(0x80000000), %bb.1(0x00000000); %bb.2(100.00%), %bb.1(0.00%)
  liveins: $rdi
  %1:gr64 = COPY killed $rdi
  %0:gr64 = nuw ADD64ri8 %1:gr64(tied-def 0), 24, implicit-def dead $eflags
  INLINEASM_BR &"# $0 $1 $2" [sideeffect] [mayload] [maystore] [attdialect], $0:[mem:m], killed %1:gr64, 1, $noreg, 24, $noreg, $1:[imm], 1, $2:[imm], blockaddress(@klist_dec_and_del, %ir-block.4), $
3:[clobber], implicit-def dead early-clobber $df, $4:[clobber], implicit-def early-clobber $fpsw, $5:[clobber], implicit-def dead early-clobber $eflags
  JMP_1 %bb.2

bb.1 (%ir-block.4, address-taken):
; predecessors: %bb.0
  successors: %bb.2(0x80000000); %bb.2(100.00%)

  MOV64mi32 killed %0:gr64, 1, $noreg, -24, $noreg, 0 :: (store 8 into %ir.6)

bb.2 (%ir-block.7):
; predecessors: %bb.0, %bb.1

  RET 0, undef $eax

then replace the ADD64ri8 with a LEA64r -- but place it _after_ the INLINEASM_BR,

 bb.0 (%ir-block.1):
   successors: %bb.2(0x80000000), %bb.1(0x00000000); %bb.2(100.00%), %bb.1(0.00%)
   liveins: $rdi
   %1:gr64 = COPY killed $rdi
-  %0:gr64 = nuw ADD64ri8 %1:gr64(tied-def 0), 24, implicit-def dead $eflags
-  INLINEASM_BR &"# $0 $1 $2" [sideeffect] [mayload] [maystore] [attdialect], $0:[mem:m], killed %1:gr64, 1, $noreg, 24, $noreg, $1:[imm], 1, $2:[imm], blockaddress(@klist_dec_and_del, %ir-block.4), $3:[clobber], implicit-def dead early-clobber $df, $4:[clobber], implicit-def early-clobber $fpsw, $5:[clobber], implicit-def dead early-clobber $eflags
+  INLINEASM_BR &"# $0 $1 $2" [sideeffect] [mayload] [maystore] [attdialect], $0:[mem:m], %1:gr64, 1, $noreg, 24, $noreg, $1:[imm], 1, $2:[imm], blockaddress(@klist_dec_and_del, %ir-block.4), $3:[clobber], implicit-def dead early-clobber $df, $4:[clobber], implicit-def early-clobber $fpsw, $5:[clobber], implicit-def dead early-clobber $eflags
+  %0:gr64 = LEA64r killed %1:gr64, 1, $noreg, 24, $noreg
   JMP_1 %bb.2

[void]

I think this might be a better fix:

diff --git a/llvm/lib/CodeGen/TwoAddressInstructionPass.cpp b/llvm/lib/CodeGen/TwoAddressInstructionPass.cpp
index de336abe607..d21407a60eb 100644
--- a/llvm/lib/CodeGen/TwoAddressInstructionPass.cpp
+++ b/llvm/lib/CodeGen/TwoAddressInstructionPass.cpp
@@ -888,6 +888,7 @@ rescheduleMIBelowKill(MachineBasicBlock::iterator &mi,
     return false;
 
   if (KillMI->hasUnmodeledSideEffects() || KillMI->isCall() ||
+      KillMI->getOpcode() == TargetOpcode::INLINEASM_BR ||
       KillMI->isBranch() || KillMI->isTerminator())
     // Don't move pass calls, etc.
     return false;
@@ -948,6 +949,7 @@ rescheduleMIBelowKill(MachineBasicBlock::iterator &mi,
       return false;
     ++NumVisited;
     if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
+        OtherMI.getOpcode() == TargetOpcode::INLINEASM_BR ||
         OtherMI.isBranch() || OtherMI.isTerminator())
       // Don't move pass calls, etc.
       return false;
@@ -1122,6 +1124,7 @@ rescheduleKillAboveMI(MachineBasicBlock::iterator &mi,
       return false;
     ++NumVisited;
     if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
+        OtherMI.getOpcode() == TargetOpcode::INLINEASM_BR ||
         OtherMI.isBranch() || OtherMI.isTerminator())
       // Don't move pass calls, etc.
       return false;

[void]

Here are a few other places to contemplate similar changes:

diff --git a/llvm/lib/CodeGen/MachineCSE.cpp b/llvm/lib/CodeGen/MachineCSE.cpp
index 09531276bc1..a6873c7acba 100644
--- a/llvm/lib/CodeGen/MachineCSE.cpp
+++ b/llvm/lib/CodeGen/MachineCSE.cpp
@@ -404,6 +404,7 @@ bool MachineCSE::isCSECandidate(MachineInstr *MI) {
 
   // Ignore stuff that we obviously can't move.
   if (MI->mayStore() || MI->isCall() || MI->isTerminator() ||
+      MI->getOpcode() == TargetOpcode::INLINEASM_BR ||
       MI->mayRaiseFPException() || MI->hasUnmodeledSideEffects())
     return false;
 
diff --git a/llvm/lib/CodeGen/ReachingDefAnalysis.cpp b/llvm/lib/CodeGen/ReachingDefAnalysis.cpp
index 5bd8b4b8e27..90e829c925e 100644
--- a/llvm/lib/CodeGen/ReachingDefAnalysis.cpp
+++ b/llvm/lib/CodeGen/ReachingDefAnalysis.cpp
@@ -519,6 +519,7 @@ MachineInstr* ReachingDefAnalysis::getLocalLiveOutMIDef(MachineBasicBlock *MBB,
 static bool mayHaveSideEffects(MachineInstr &MI) {
   return MI.mayLoadOrStore() || MI.mayRaiseFPException() ||
          MI.hasUnmodeledSideEffects() || MI.isTerminator() ||
+         MI.getOpcode() == TargetOpcode::INLINEASM_BR ||
          MI.isCall() || MI.isBarrier() || MI.isBranch() || MI.isReturn();
 }

[nickdesaulniers]

In https://github.com/ClangBuiltLinux/linux/issues/1085#issuecomment-656347490 @void suggested trying to mark INLINEASM_BR MCInsts as IsBarrier. Based on the latest recommendations, I'm wondering if IsCall is more appropriate?

[nickdesaulniers]

In D83523#2146520, @void wrote:

I think this might be a better fix:

It seems that none of those fix the provided test case. :-(

[nickdesaulniers]

In D83523#2147995, @nickdesaulniers wrote:

In D83523#2146520, @void wrote:

I think this might be a better fix:

It seems that none of those fix the provided test case. :-(

Ah, right, because the test case is still testing machinesink. Let me change it to twoaddressinstruction and retest.

[jyknight]

INLINEASM_BR already returns true for hasUnmodeledSideEffects(), so the diff above doesn't change anything.

The bug is in TwoAddressInstructinoPass::sink3AddrInstruction, which doesn't query _ANY_ of these predicates. I've just uploaded https://reviews.llvm.org/D83708 to remove the function entirely.

[nickdesaulniers]

• change to twoaddressinstruction

[nickdesaulniers]

Abandoning in preference to D83708.

llvm/lib/CodeGen/TwoAddressInstructionPass.cpp

for (MachineOperand &UseMO : MRI->use_nodbg_operands(SavedReg)) {
       break;
     }
   }
 
   // If we find the instruction that kills SavedReg, and it is in an
   // appropriate location, we can try to sink the current instruction
   // past it.
   if (!KillMI || KillMI->getParent() != MBB || KillMI == MI ||
-      MachineBasicBlock::iterator(KillMI) == OldPos || KillMI->isTerminator())
+      MachineBasicBlock::iterator(KillMI) == OldPos || KillMI->isTerminator() ||
+      KillMI->getOpcode() == TargetOpcode::INLINEASM_BR)
     return false;
 
   // If any of the definitions are used by another instruction between the
   // position and the kill use, then it's not safe to sink it.
   //
   // FIXME: This can be sped up if there is an easy way to query whether an
   // instruction is before or after another instruction. Then we can use
   // MachineRegisterInfo def / use instead.
rescheduleMIBelowKill(MachineBasicBlock::iterator &mi,
   } else {
     KillMI = LV->getVarInfo(Reg).findKill(MBB);
   }
   if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike())
     // Don't mess with copies, they may be coalesced later.
     return false;
 
   if (KillMI->hasUnmodeledSideEffects() || KillMI->isCall() ||
-      KillMI->isBranch() || KillMI->isTerminator())
+      KillMI->isBranch() || KillMI->isTerminator() ||
+      KillMI->getOpcode() == TargetOpcode::INLINEASM_BR)
     // Don't move pass calls, etc.
     return false;
 
   unsigned DstReg;
   if (isTwoAddrUse(*KillMI, Reg, DstReg))
     return false;
 
   bool SeenStore = true;
rescheduleMIBelowKill(MachineBasicBlock::iterator &mi,
   for (MachineInstr &OtherMI : make_range(End, KillPos)) {
     // Debug instructions cannot be counted against the limit.
     if (OtherMI.isDebugInstr())
       continue;
     if (NumVisited > 10)  // FIXME: Arbitrary limit to reduce compile time cost.
       return false;
     ++NumVisited;
     if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
-        OtherMI.isBranch() || OtherMI.isTerminator())
+        OtherMI.isBranch() || OtherMI.isTerminator() ||
+        OtherMI.getOpcode() == TargetOpcode::INLINEASM_BR)
       // Don't move pass calls, etc.
       return false;
     for (const MachineOperand &MO : OtherMI.operands()) {
       if (!MO.isReg())
         continue;
       Register MOReg = MO.getReg();
       if (!MOReg)
         continue;
for (MachineInstr &OtherMI :
        make_range(mi, MachineBasicBlock::iterator(KillMI))) {
     // Debug instructions cannot be counted against the limit.
     if (OtherMI.isDebugInstr())
       continue;
     if (NumVisited > 10)  // FIXME: Arbitrary limit to reduce compile time cost.
       return false;
     ++NumVisited;
     if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
-        OtherMI.isBranch() || OtherMI.isTerminator())
+        OtherMI.isBranch() || OtherMI.isTerminator() ||
+        OtherMI.getOpcode() == TargetOpcode::INLINEASM_BR)
       // Don't move pass calls, etc.
       return false;
     SmallVector<unsigned, 2> OtherDefs;
     for (const MachineOperand &MO : OtherMI.operands()) {
       if (!MO.isReg())
         continue;
       Register MOReg = MO.getReg();
       if (!MOReg)

llvm/test/CodeGen/X86/twoaddr-inlineasm_br.ll

+; RUN: llc -O2 $1 -print-after=twoaddressinstruction -stop-after=twoaddressinstruction -o /dev/null 2>&1 %s | FileCheck %s
+%struct1 = type { i8*, %struct2, %struct3 }
+%struct2 = type { %struct2*, %struct2* }
+%struct3 = type { %struct4 }
+%struct4 = type { i32 }
+%struct5 = type { %struct6, %struct2, void (%struct1*)*, void (%struct1*)* }
+%struct6 = type { i32 }
+
+define i32 @klist_dec_and_del(%struct1* %0) {
+  %2 = getelementptr inbounds %struct1, %struct1* %0, i64 0, i32 2
+  %3 = getelementptr inbounds %struct3, %struct3* %2, i64 0, i32 0, i32 0
+; The LEA should not be sunk past the INLINEASM_BR, otherwise the execution of
+; the LEA becomes conditional on whether the INLINEASM_BR branches or not,
+; which would be incorrect.
+; CHECK: %0:gr64 = LEA64r %1:gr64, 1, $noreg, 24, $noreg
+; CHECK-NEXT: INLINEASM_BR &"" [sideeffect] [mayload] [maystore] [attdialect], $0:[mem:m], killed %1:gr64, 1, $noreg, 24, $noreg, $1:[imm], 1, $2:[imm], blockaddress(@klist_dec_and_del, %ir-block.4), $3:[clobber], implicit-def dead early-clobber $df, $4:[clobber], implicit-def early-clobber $fpsw, $5:[clobber], implicit-def dead early-clobber $eflags
+  callbr void asm sideeffect "", "*m,er,X,~{memory},~{dirflag},~{fpsr},~{flags}"(i32* %3, i32 1, i8* blockaddress(@klist_dec_and_del, %4))
+          to label %8 [label %4]
+
+4:                                                ; preds = %1
+  %5 = getelementptr %struct3, %struct3* %2, i64 -6
+  br label %6
+
+6:                                                ; preds = %4
+  %7 = bitcast %struct3* %5 to %struct5**
+  store %struct5* null, %struct5** %7, align 8
+  br label %8
+
+8:                                                ; preds = %6, %1
+  ret i32 undef
+}