[MachineVerifier] add checks for INLINEASM_BR

[nickdesaulniers]

Summary

Test for a case we observed after the initial implementation of D129997
landed, in which case we observed a crash while building the ppc64le
Linux kernel. In that case, we had one block with two exits, both to the
same successor. Removing one of the exits corrupted the
successor/predecessor lists.

So when we have an INLINEASM_BR, check a few things for each indirect
target:

1. that it exists.
2. that it is listed in our successors.
3. that its predecessor list contains the parent MBB of INLINEASM_BR.

This would have caught the regression discovered after D129997 landed,
after the pass that was problematic (early-tailduplication) rather than
getting a stack trace in a later pass (regalloc) that doesn't understand
the anomaly and crashes.

[nickdesaulniers]

• add early continue to reduce nesting one level

[nickdesaulniers]

• add two comments in the mir test about the messed up successor/predecessor lists

[arsenm]

llvm/lib/CodeGen/MachineVerifier.cpp

882

Why is this based on the IR block?

899–902

This is !MBB->isSuccessor

899–904

I'd expect CFG checks to go with the others in visitMachineBasicBlockBefore

906–908

this is !MBB->isPredecessor

[nickdesaulniers]

• replace llvm::none_of with MachineBasicBlock::{isSuccessor|isPredecessor}

llvm/lib/CodeGen/MachineVerifier.cpp

882

Because AFAIK, there is no corresponding BlockAddress Constant in the MIR level, so the MachineInst uses a BlockAddress Constant which is just a tuple of (Function, BasicBlock). What would be helpful here would be if BlockAddress Constants were lowered to something new (doesn't exist, yet) that is a tuple of (MachineFunction, MachineBasicBlock).

The existing design seems brittle, because IIUC, there's a one-to-many relationship between BasicBlock and MachineBasicBlock. A MachineBasicBlock can refer to a single BasicBlock.

Perhaps that's why in my TODO below that we _don't_ have a mapping of BasicBlock to MachineBasicBlock; because they are not one-to-one (unless I'm wrong).

899–904

Perhaps, but consider that INLINEASM_BR are relatively rare constructs to see in the wild; I think it might be more efficient to do such scans only when they are encountered.

[nickdesaulniers]

llvm/lib/CodeGen/MachineVerifier.cpp

882

MachineOperand::getMBB() is almost what I want here, but that corresponds to a different MachineOperandType (MO_MachineBasicBlock) than what is being used for INLINEASM_BR (MO_BlockAddress). Maybe MO_BlockAddress needs to die?

[nickdesaulniers]

llvm/lib/CodeGen/MachineVerifier.cpp

882

Because AFAIK, there is no corresponding BlockAddress Constant in the MIR level

So that's wrong; there _is_ a corresponding MachineOperandType: MO_MachineBasicBlock. It's just that INLINEASM_BR doesn't use those.

[nickdesaulniers]

llvm/lib/CodeGen/MachineVerifier.cpp

887–888

I'm probably thinking of FunctionLoweringInfo. Not sure how to access one of those from MachineVerifier, if it's even possible.

[efriedma]

llvm/lib/CodeGen/MachineVerifier.cpp

882

It probably makes sense to change INLINEASM_BR to use MO_MachineBasicBlock operands instead of MO_BlockAddress operands; that basically corresponds to the IR change we made to remove blockaddress operands.

(Re: the one-to-many thing, see D124697.)

[arsenm]

llvm/lib/CodeGen/MachineVerifier.cpp

887–888

FunctionLowering is for the initial DAG/MIR construction only. I would avoid referring to the underlying IR in any way if possible

[nickdesaulniers]

llvm/lib/CodeGen/MachineVerifier.cpp

882

Something like:

diff --git a/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp b/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
index c312fca616a5..3d2ff957eb77 100644
--- a/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
@@ -5287,14 +5287,15 @@ TargetLowering::ParseConstraints(const DataLayout &DL,
     case InlineAsm::isInput:
       OpInfo.CallOperandVal = Call.getArgOperand(ArgNo);
       break;
-    case InlineAsm::isLabel:
-      OpInfo.CallOperandVal =
-          cast<CallBrInst>(&Call)->getBlockAddressForIndirectDest(LabelNo);
+    case InlineAsm::isLabel: {
+      const BlockAddress *BA =
+        cast<CallBrInst>(&Call)->getBlockAddressForIndirectDest(LabelNo);
+      OpInfo.CallOperandVal = BA->getBasicBlock();
       OpInfo.ConstraintVT =
-          getAsmOperandValueType(DL, OpInfo.CallOperandVal->getType())
-              .getSimpleVT();
+        getAsmOperandValueType(DL, BA->getType()).getSimpleVT();
       ++LabelNo;
       continue;
+    }
     case InlineAsm::isClobber:
       // Nothing to do.
       break;

seems to work. I need to update a few tests

Failed Tests (13):
  LLVM :: CodeGen/AArch64/callbr-asm-label.ll
  LLVM :: CodeGen/AArch64/callbr-asm-obj-file.ll
  LLVM :: CodeGen/X86/callbr-asm-bb-exports.ll
  LLVM :: CodeGen/X86/callbr-asm-destinations.ll
  LLVM :: CodeGen/X86/callbr-asm-instr-scheduling.ll
  LLVM :: CodeGen/X86/callbr-asm-label-addr.ll
  LLVM :: CodeGen/X86/callbr-asm-obj-file.ll
  LLVM :: CodeGen/X86/callbr-asm-outputs.ll
  LLVM :: CodeGen/X86/callbr-asm-sink.ll
  LLVM :: CodeGen/X86/callbr-asm.ll
  LLVM :: CodeGen/X86/inline-asm-pic.ll
  LLVM :: CodeGen/X86/shrinkwrap-callbr.ll
  LLVM :: CodeGen/X86/tail-dup-asm-goto.ll

but it just looks like now we emit jmp .LBB0_2 rather than jmp .Ltmp0. I haven't verified that's correct but it seems innocuous; will do so after lunch, update tests, and post patch.

[nickdesaulniers]

llvm/lib/CodeGen/MachineVerifier.cpp

882

IIRC, I think we added code to retain/emit symbols like .Ltmp0: for # Block address taken. We _might_ be able to remove that with this change. Maybe not, NBD either way.

[nickdesaulniers]

llvm/lib/CodeGen/MachineVerifier.cpp

882

ah, llvm/test/CodeGen/AArch64/callbr-asm-obj-file.ll demonstrates that retaining the label needs to be moved from the .Ltmp ones to the .LBBX ones. WIP

[nickdesaulniers]

llvm/lib/CodeGen/MachineVerifier.cpp

882

Ok, that's actually a small but nice cleanup to AsmPrinter::emitBasicBlockStart (llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp).

[nickdesaulniers]

llvm/lib/CodeGen/MachineVerifier.cpp

882

It probably makes sense to change INLINEASM_BR to use MO_MachineBasicBlock operands instead of MO_BlockAddress operands; that basically corresponds to the IR change we made to remove blockaddress operands.

One thing I can't figure out...INLINEASM_BR is constructed from SelectionDAGBuilder::visitInlineAsm llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp. But AFAICT there's not SDNode

882

It probably makes sense to change INLINEASM_BR to use MO_MachineBasicBlock operands instead of MO_BlockAddress operands; that basically corresponds to the IR change we made to remove blockaddress operands.

It seems like there's no corresponding SDValue for MO_MachineBasicBlock, IIUC? So I _think_ the operand has to remain an IR BasicBlock?

[efriedma]

llvm/lib/CodeGen/MachineVerifier.cpp

882

SelectionDAG::getBasicBlock() builds an SDValue for an MBB.

[nickdesaulniers]

llvm/lib/CodeGen/MachineVerifier.cpp

882

ah, ok then, I guess I was getting confused since in MIR we have:

INLINEASM_BR &"xorl $0, $0; jmp ${1:l}" [attdialect], $0:[reguse:GR32], %5:gr32, $1:[imm], %bb.2, $2:[clobber], implicit-def early-clobber $df, $3:[clobber], implicit-def early-clobber $fpsw, $4:[clobber], implicit-def early-clobber $eflags

i.e. the operand is %bb.2 which is confusing; it looks like a reference back to the IR BasicBlock, rather than the MIR MachineBasicBlock...

[nickdesaulniers]

• rebase

[nickdesaulniers]

Bumping for review

[efriedma]

llvm/lib/CodeGen/MachineVerifier.cpp

897

I don't think you need to check both isSuccessor and isPredecessor; we should have other checks that verify the predecessor lists are consistent with the successor lists.

[nickdesaulniers]

llvm/lib/CodeGen/MachineVerifier.cpp

897

If you comment out these checks, then run llc -run-pass=none -verify-machineinstrs /android0/llvm-project/llvm/test/MachineVerifier/verify-inlineasmbr.mir -o -, you'll find that MachineVerify makes not such qualms about inconsistent predecessor or successor lists, despite BOTH being wrong.

[efriedma]

llvm/lib/CodeGen/MachineVerifier.cpp

897

All I'm trying to say is that if you try to construct a testcase where the isSuccessor check succeeds, but the isPredecessor check fails, you'll get some other error.

[nickdesaulniers]

llvm/lib/CodeGen/MachineVerifier.cpp

897

I suspect the verifier will spot other things wrong later during its analysis, but if either list is corrupt, I feel strongly that we should eagerly diagnose that ASAP. It makes for a significantly improved debugging experience if the verifier spots corrupted pred/succ lists ASAP.

[nickdesaulniers]

llvm/lib/CodeGen/MachineVerifier.cpp

897

I was thinking more about your point last night; if I may restate what I perceive to be the distinction another way.

Your latest point sounds like if ONE of either the predecessor list or successor list in incorrect, the MachineVerifier will catch that.

Granted.

But what happens if BOTH are wrong, simultaneously?

Because that is precisely what happened in D129997. The MachineVerifier did not catch that.

For MachineInstrs that imply control flow, we should verify that their parent MachineBasicBlock's successor list contains the MachineInstrs MachineBasicBlock operand AND that operand's predecessor list contains this MachineInstrs parent MachineBasicBlock. This patch does such checking only for the rare cases of INLINEASM_BR, but I'd go so far as to suggest this should be done for ALL branching instructions (or maybe any instruction that has a MachineBasicBlock as an operand).

Stated a third way, if MBB A has a jump to MBB B, we should check that:

1. B is in A's successor list.
2. A is in B's predecessor list.

It _might_ be that MachineVerifier can catch imbalanced cases where ONE of the above does not hold, but currently, if BOTH don't hold MachineVerifier misses that.

Removing an edge between A and B without also removing the branching instruction in A (where that instruction branches to B) is a great way to get into the above anomalous conditions, which is what happened in D129997.

899–904

Further, visitMachineBasicBlockBefore walks the successor and predecessor lists and uses analyzeBranch, so it already assumes those lists are well formed. For IR verification, that's a dangerous assumption to make. In D129997, those lists were fundamentally untrustworthy.

(I also don't think that analyzeBranch works with INLINEASM_BR).

[efriedma]

LGTM

llvm/lib/CodeGen/MachineVerifier.cpp

897

It's not really a big deal either way, in any case.

[nickdesaulniers]

llvm/lib/CodeGen/MachineVerifier.cpp

897

thank you for the review!

llvm/lib/CodeGen/MachineVerifier.cpp

if (OpNo < MI->getNumOperands() && MI->getOperand(OpNo).isMetadata())
     ++OpNo;
 
   // All trailing operands must be implicit registers.
   for (unsigned e = MI->getNumOperands(); OpNo < e; ++OpNo) {
     const MachineOperand &MO = MI->getOperand(OpNo);
     if (!MO.isReg() || !MO.isImplicit())
       report("Expected implicit register after groups", &MO, OpNo);
   }
+
+  if (MI->getOpcode() == TargetOpcode::INLINEASM_BR) {
+    const MachineBasicBlock *MBB = MI->getParent();
+
+    for (unsigned i = InlineAsm::MIOp_FirstOperand, e = MI->getNumOperands();
+         i != e; ++i) {
+      const MachineOperand &MO = MI->getOperand(i);
+      if (MO.isBlockAddress()) {
+        const BasicBlock *IndirectTarget =
+            MO.getBlockAddress()->getBasicBlock();
+
+        // Check the successor & predecessor lists look ok, assume they are
+        // not. Find the indirect target without going through the successors.
+        const MachineBasicBlock *IndirectTargetMBB = nullptr;
+        // TODO: do we have a mapping of BasicBlocks to MachineBasicBlocks
+        // already?
+        for (const MachineBasicBlock &MBB : *MBB->getParent())
+          if (MBB.getBasicBlock() == IndirectTarget) {
+            IndirectTargetMBB = &MBB;
+            break;
+          }
+        if (!IndirectTargetMBB) {
+          report("INLINEASM_BR indirect target does not exist", &MO, i);
+          break;
+        }
+
+        if (llvm::none_of(MBB->successors(),
+                          [IndirectTargetMBB](const MachineBasicBlock *Succ) {
+                            return Succ == IndirectTargetMBB;
+                          }))
+          report("INLINEASM_BR indirect target missing from successor list",
+                 &MO, i);
+
+        if (llvm::none_of(
+                IndirectTargetMBB->predecessors(),
+                [MBB](const MachineBasicBlock *Pred) { return Pred == MBB; }))
+          report("INLINEASM_BR indirect target predecessor list missing parent",
+                 &MO, i);
+      }
+    }
+  }
 }
 
 bool MachineVerifier::verifyAllRegOpsScalar(const MachineInstr &MI,
                                             const MachineRegisterInfo &MRI) {
   if (none_of(MI.explicit_operands(), [&MRI](const MachineOperand &Op) {
         if (!Op.isReg())
           return false;
         const auto Reg = Op.getReg();

llvm/test/MachineVerifier/verify-inlineasmbr.mir

+# RUN: not --crash llc -run-pass=none -verify-machineinstrs %s 2>&1 \
+# RUN:  | FileCheck %s
+# REQUIRES: powerpc-registered-target
+
+# Test for a case we observed after the initial implementation of D129997
+# landed, in which case we observed a crash while building the ppc64le Linux
+# kernel. In that case, we had one block with two exits, both to the same
+# successor. Removing one of the exits corrupted the successor/predecessor
+# lists.
+
+# CHECK: *** Bad machine code: INLINEASM_BR indirect target missing from successor list ***
+# CHECK-NEXT: - function:    ceph_con_v2_try_read
+# CHECK-NEXT: - basic block: %bb.3 if.else.i.i
+# CHECK-NEXT: - instruction: INLINEASM_BR &"" [sideeffect] [attdialect], $0:[imm], blockaddress(@ceph_con_v2_try_read, %ir-block.if.end.i)
+# CHECK-NEXT: - operand 3:   blockaddress(@ceph_con_v2_try_read, %ir-block.if.end.i)
+
+# CHECK: *** Bad machine code: INLINEASM_BR indirect target predecessor list missing parent ***
+# CHECK-NEXT: - function:    ceph_con_v2_try_read
+# CHECK-NEXT: - basic block: %bb.3 if.else.i.i
+# CHECK-NEXT: - instruction: INLINEASM_BR &"" [sideeffect] [attdialect], $0:[imm], blockaddress(@ceph_con_v2_try_read, %ir-block.if.end.i)
+# CHECK-NEXT: - operand 3:   blockaddress(@ceph_con_v2_try_read, %ir-block.if.end.i)
+
+--- |
+  target datalayout = "e-m:e-i64:64-n32:64-S128-v256:256:256-v512:512:512"
+  target triple = "powerpc64le-unknown-linux-gnu"
+  
+  ; Function Attrs: argmemonly nocallback nofree nosync nounwind willreturn
+  declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture) #0
+  
+  define void @ceph_con_v2_try_read(i32 %__trans_tmp_3.sroa.0.0.copyload, i1 %tobool.not.i.i) {
+  entry:
+    %skip.i.i = alloca i32, i32 0, align 4
+    %cond = icmp eq i32 %__trans_tmp_3.sroa.0.0.copyload, 0
+    br label %for.cond
+  
+  for.cond:                                         ; preds = %for.cond, %process_message_header.exit.i, %if.end.i, %entry
+    br i1 %cond, label %sw.bb, label %for.cond
+  
+  sw.bb:                                            ; preds = %for.cond
+    %call.i.i2 = call i32 null(ptr %skip.i.i)
+    br i1 %tobool.not.i.i, label %if.else.i.i, label %process_message_header.exit.i
+  
+  if.else.i.i:                                      ; preds = %sw.bb
+    callbr void asm sideeffect "", "!i"()
+            to label %if.end.i [label %if.end.i]
+  
+  process_message_header.exit.i:                    ; preds = %sw.bb
+    call void @llvm.lifetime.end.p0(i64 0, ptr %skip.i.i)
+    br label %for.cond
+  
+  if.end.i:                                         ; preds = %if.else.i.i, %if.else.i.i
+    call void @llvm.lifetime.end.p0(i64 0, ptr %skip.i.i)
+    br label %for.cond
+  }
+  
+  attributes #0 = { argmemonly nocallback nofree nosync nounwind willreturn }
+
+...
+---
+name:            ceph_con_v2_try_read
+alignment:       16
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+hasWinCFI:       false
+callsEHReturn:   false
+callsUnwindInit: false
+hasEHCatchret:   false
+hasEHScopes:     false
+hasEHFunclets:   false
+failsVerification: false
+tracksDebugUserValues: false
+registers:
+  - { id: 0, class: crbitrc, preferred-register: '' }
+  - { id: 1, class: g8rc, preferred-register: '' }
+  - { id: 2, class: g8rc, preferred-register: '' }
+  - { id: 3, class: crbitrc, preferred-register: '' }
+  - { id: 4, class: gprc, preferred-register: '' }
+  - { id: 5, class: crrc, preferred-register: '' }
+  - { id: 6, class: g8rc, preferred-register: '' }
+  - { id: 7, class: g8rc, preferred-register: '' }
+  - { id: 8, class: g8rc, preferred-register: '' }
+  - { id: 9, class: g8rc, preferred-register: '' }
+  - { id: 10, class: g8rc, preferred-register: '' }
+liveins:
+  - { reg: '$x3', virtual-reg: '%1' }
+  - { reg: '$x4', virtual-reg: '%2' }
+frameInfo:
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       0
+  offsetAdjustment: 0
+  maxAlignment:    4
+  adjustsStack:    false
+  hasCalls:        true
+  stackProtector:  ''
+  functionContext: ''
+  maxCallFrameSize: 4294967295
+  cvBytesOfCalleeSavedRegisters: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+  hasTailCall:     false
+  localFrameSize:  0
+  savePoint:       ''
+  restorePoint:    ''
+fixedStack:      []
+stack:
+  - { id: 0, name: skip.i.i, type: default, offset: 0, size: 1, alignment: 4, 
+      stack-id: default, callee-saved-register: '', callee-saved-restored: true, 
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+callSites:       []
+debugValueSubstitutions: []
+constants:       []
+machineFunctionInfo: {}
+body:             |
+  bb.0.entry:
+    successors: %bb.1(0x80000000)
+    liveins: $x3, $x4
+  
+    %2:g8rc = COPY $x4
+    %1:g8rc = COPY $x3
+    %10:g8rc = ANDI8_rec %2, 1, implicit-def $cr0
+    %3:crbitrc = COPY $cr0gt
+    %4:gprc = COPY %1.sub_32
+    %5:crrc = CMPWI killed %4, 0
+    %0:crbitrc = COPY %5.sub_eq
+  
+  bb.1.for.cond:
+    successors: %bb.2(0x30000000), %bb.1(0x50000000)
+  
+    BCn %0, %bb.1
+    B %bb.2
+  
+  bb.2.sw.bb:
+    successors: %bb.3(0x40000000), %bb.4(0x40000000)
+  
+    ADJCALLSTACKDOWN 32, 0, implicit-def dead $r1, implicit $r1
+    %6:g8rc = COPY $x2
+    STD %6, 24, $x1 :: (store (s64) into stack + 24)
+    %7:g8rc = ADDI8 %stack.0.skip.i.i, 0
+    %8:g8rc = LI8 0
+    $x3 = COPY %7
+    $x12 = COPY %8
+    MTCTR8 %8, implicit-def $ctr8
+    BCTRL8_LDinto_toc 24, $x1, csr_ppc64_altivec, implicit-def dead $lr8, implicit-def dead $x2, implicit $ctr8, implicit $rm, implicit $x3, implicit $x12, implicit $x2, implicit-def $r1, implicit-def $x3
+    ADJCALLSTACKUP 32, 0, implicit-def dead $r1, implicit $r1
+    %9:g8rc = COPY $x3
+    BCn %3, %bb.4
+    B %bb.3
+  
+  bb.3.if.else.i.i:
+    successors: %bb.1(0x80000000)
+  
+    INLINEASM_BR &"", 1 /* sideeffect attdialect */, 13 /* imm */, blockaddress(@ceph_con_v2_try_read, %ir-block.if.end.i)
+    LIFETIME_END %stack.0.skip.i.i
+    B %bb.1
+  
+  bb.4.process_message_header.exit.i:
+    successors: %bb.1(0x80000000)
+  
+    LIFETIME_END %stack.0.skip.i.i
+    B %bb.1
+  
+  bb.5.if.end.i (address-taken, inlineasm-br-indirect-target):
+    successors: %bb.1(0x80000000)
+  
+    LIFETIME_END %stack.0.skip.i.i
+    B %bb.1
+
+...