This is an archive of the discontinued LLVM Phabricator instance.

[MachineVerifier] add checks for INLINEASM_BR
ClosedPublic

Authored by nickdesaulniers on Jul 21 2022, 10:21 AM.

Details

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.

Diff Detail

Event Timeline

Herald added a project: Restricted Project. · View Herald TranscriptJul 21 2022, 10:21 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
nickdesaulniers requested review of this revision.Jul 21 2022, 10:21 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 21 2022, 10:21 AM
  • add early continue to reduce nesting one level
  • add two comments in the mir test about the messed up successor/predecessor lists
arsenm added inline comments.Jul 21 2022, 10:32 AM
llvm/lib/CodeGen/MachineVerifier.cpp
889

Why is this based on the IR block?

906–909

This is !MBB->isSuccessor

906–911

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

913–915

this is !MBB->isPredecessor

nickdesaulniers marked 2 inline comments as done.
  • replace llvm::none_of with MachineBasicBlock::{isSuccessor|isPredecessor}
llvm/lib/CodeGen/MachineVerifier.cpp
889

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).

906–911

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.

llvm/lib/CodeGen/MachineVerifier.cpp
889

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?

llvm/lib/CodeGen/MachineVerifier.cpp
889

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.

llvm/lib/CodeGen/MachineVerifier.cpp
894–895

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

efriedma added inline comments.Jul 21 2022, 11:25 AM
llvm/lib/CodeGen/MachineVerifier.cpp
889

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 added inline comments.Jul 21 2022, 11:26 AM
llvm/lib/CodeGen/MachineVerifier.cpp
894–895

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

llvm/lib/CodeGen/MachineVerifier.cpp
889

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.

llvm/lib/CodeGen/MachineVerifier.cpp
889

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.

llvm/lib/CodeGen/MachineVerifier.cpp
889

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

llvm/lib/CodeGen/MachineVerifier.cpp
889

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

llvm/lib/CodeGen/MachineVerifier.cpp
889

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

889

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 added inline comments.Jul 22 2022, 11:24 AM
llvm/lib/CodeGen/MachineVerifier.cpp
889

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

llvm/lib/CodeGen/MachineVerifier.cpp
889

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...

efriedma added inline comments.Aug 17 2022, 3:15 PM
llvm/lib/CodeGen/MachineVerifier.cpp
904

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.

llvm/lib/CodeGen/MachineVerifier.cpp
904

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 added inline comments.Aug 17 2022, 3:56 PM
llvm/lib/CodeGen/MachineVerifier.cpp
904

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.

llvm/lib/CodeGen/MachineVerifier.cpp
904

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.

llvm/lib/CodeGen/MachineVerifier.cpp
904

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.

906–911

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 accepted this revision.Aug 19 2022, 12:33 PM

LGTM

llvm/lib/CodeGen/MachineVerifier.cpp
904

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

This revision is now accepted and ready to land.Aug 19 2022, 12:33 PM
This revision was automatically updated to reflect the committed changes.
llvm/lib/CodeGen/MachineVerifier.cpp
904

thank you for the review!