This is an archive of the discontinued LLVM Phabricator instance.

[BranchFolding] assert when removing INLINEASM_BR indirect targets
Changes PlannedPublic

Authored by nickdesaulniers on Apr 15 2020, 12:40 PM.

Details

Summary

Twice now, we've had to debug pretty awful codegen bugs where the
indirect target of an INLINEASM_BR was removed by BranchFolding.

  1. https://reviews.llvm.org/D76961
  2. https://reviews.llvm.org/D77849

In both cases, this was a cascaded failure caused earlier, and not
necessarily BranchFolding's fault. For that reason, I don't think it's
appropriate to always guard against removing MachineBasicBlocks that
have their address taken; this is indicative of something else going
wrong earlier.

Rather than proceed to generate jumps to blocks that have been removed,
which is quite hard to debug (the generated code), add an assertion to
help catch and hint at similar failures in the future.

The first conditional added is false for all tests currently in tree,
but this exceptional case is true for the test case in D77849. When
D77849 is resolved this exceptional cases should hopefully never be
true, but the assertion is still useful to catch regressions or help
find if there's more bugs lying in wait.

D78166 is also related, and will cause the assertions added in
D78166 to fire before this added assertion, for the test case in
D77849.

Diff Detail

Event Timeline

Herald added a project: Restricted Project. · View Herald TranscriptApr 15 2020, 12:40 PM
nickdesaulniers edited the summary of this revision. (Show Details)Apr 15 2020, 12:41 PM
efriedma added inline comments.Apr 15 2020, 12:50 PM
llvm/lib/CodeGen/BranchFolding.cpp
168

It would be better to expand the comment, instead of incorporating the review by reference.

171

Op.isBlockAddress() check isn't sufficient to filter out all the relevant cases, I think. It's possible to pass a blockaddress to an asm that isn't a valid destination according to the IR.

173

llvm_unreachable?

I'm a little concerned iterating over the entire function is going to be expensive, but we probably erase address-taken blocks pretty rarely.

nickdesaulniers marked an inline comment as done.
llvm/lib/CodeGen/BranchFolding.cpp
171

That's right, and we don't have a great way of checking that one MachineBasicBlock is the indirect successor to another MachineBasicBlock's INLINEASM_BR.

Looking at MachineBasicBlock#isInlineAsmBrIndirectTarget looks like what we might want, but the call to MachineBasicBlock#transferInlineAsmBrIndirectTargets in ScheduleDAGSDNodes::EmitSchedule looks kind of fishy to me.

I tried adding MBB->isSuccessor(&Pred) && but this fails because the predecessor/successor list is messed up (from the commit description of https://reviews.llvm.org/D77849).

Backing up, regardless of the BlockAddress being an indirect successor of the INLINEASM_BR as opposed to just input, wouldn't removing the target MachineBasicBlock be bad either way? Even if it was the operand of any instruction, and we remove the corresponding basic block, that sounds bad.

173

Not sure what you mean by llvm_unreachable? Was that a suggestion for a change to this patch, or a joke about this case being impossible?

Yes, it's relatively expensive. But:

  1. we only do this for assertion builds.
  2. the initial check MBB->hasAddressTaken() is exceptional, and almost always false (except for the test case from D77849). Once D78166 lands (after this, is my plan), then this should always be false, modulo LLVM having more bugs, or regressions.

Which I think justifies having "expensive" assertions. It's "expensive" in terms of work it has to do in an extremely exceptional case, but quite cheap relative to my time (and I think Linus Torvalds' time) debugging runtime issues of code generated from this exceptional case.

efriedma added inline comments.Apr 15 2020, 3:06 PM
llvm/lib/CodeGen/BranchFolding.cpp
171

Well, suppose we have an indirectbr, but we prove it dead, and erase it. Then we have a "dangling" blockaddress that can't really be used for anything; by itself, that shouldn't justify keeping the block alive. (In other places, I think we replace it with a constant "-1".)

This is why, like I mentioned before, we should have a "successor" list on INLINEASM_BR that doesn't use blockaddress operands, so we can avoid confusion like this.

173

assert(false) is essentially equivalent to llvm_unreachable().

Yes, I think the cost here is okay.

  • prefer llvm_unreachable to assert(false), as per @efriedma
nickdesaulniers marked 3 inline comments as done.Apr 15 2020, 4:04 PM
nickdesaulniers added inline comments.
llvm/lib/CodeGen/BranchFolding.cpp
171

by itself, that shouldn't justify keeping the block alive.

This patch doesn't keep the MachineBasicBlock alive. I also don't advocate for keeping the MachineBasicBlock alive.

When you fail this assertion, the solution is not "we should keep the MachineBasicBlock alive," it's "we should figure out why we proved a MachineBasicBlock dead when it clearly has a BlockAddress that references it, as that is weird and likely a bug."

Maybe I can reflect that sentiment via an additional comment added to this patch, so that future travelers that may experience this assertion (hopefully never) understand the intent and how best to proceed?

llvm/lib/CodeGen/BranchFolding.cpp
171

Or a more precise error string in the llvm_unreachable?

nickdesaulniers added inline comments.
llvm/lib/CodeGen/BranchFolding.cpp
171

In another branch, I tried deleting MachineBasicBlock::transferInlineAsmBrIndirectTargets(). All tests in tree pass. So I think I'll roll that change into this one, then I can use MachineBasicBlock#isInlineAsmBrIndirectTarget properly here.

Following up on the RFC discussion, I found @craig.topper 's comment (https://reviews.llvm.org/D53765?id=184024#inline-508610) on the RFC which had setIsAsmGotoTarget (which I suspect didn't persist when INLINEASM_BR was created), though was added as addInlineAsmBrIndirectTarget recently).

@void @efriedma any preference on me making that change in this patch vs in a separate patch, first?

nickdesaulniers planned changes to this revision.Apr 16 2020, 1:03 PM
nickdesaulniers marked 6 inline comments as done.
  • delete transferInlineAsmBrIndirectTargets so that we can use isInlineAsmBrIndirectTarget correctly.

InlineAsmBrIndirectTargets seems like a bug waiting to happen: if we split a block for whatever reason (for example, lowering a cmov), I think the InlineAsmBrIndirectTargets will remain attached to the wrong block.

nickdesaulniers added a comment.EditedApr 16 2020, 5:30 PM

InlineAsmBrIndirectTargets seems like a bug waiting to happen: if we split a block for whatever reason (for example, lowering a cmov), I think the InlineAsmBrIndirectTargets will remain attached to the wrong block.

I agree, there was a certain asymmetry in API between LLVM IR and MIR that I couldn't quite put my finger on, but your comment helps highlight it for me.

For LLVM IR, CallBrInst tracks its default and indirect targets. ie. the Instruction tracks these, not the BasicBlock, so manipulations to the BasicBlock can't lose this information. You don't ask "is this BasicBlock an indirect target of this BasicBlock," you ask "is this BasicBlock an indirect target of this CallBrInst?"

For MIR, MachineBasicBlock tracks its default and indirect targets. ie. the MachineBasicBlock tracks these, not the MachineInstr, so (as you point out) manipulations to the MachineBasicBlock could corrupt their default+indirect targets. Currently, we can ask "is this MachineBasicBlock an indirect target of this MachineBasicBlock," but we *should* match the symmetry of the LLVM IR and change this to be able to ask "is this MachineBasicBlock an indirect target of the MachineInstr?"

Does that sound right?

One thing that also seems asymmetrical to me is the subclassing that occurs at the LLVM IR level (CallBrInst inherits from CallBase inherits from Instruction), but at the MIR level we just have MachineInstr with OpCodes to differentiate kinds of instructions. It seems unfortunate to move these lists or sets of basic blocks to every MachineInstr, even if the vast majority are never INLINEASM_BR. Should I just subclass the MachineInstr, or will that lead to other headaches?

The reason MachineBasicBlock has its own method to query successors is that there isn't any consistent way to query the successors based on MachineInstrs. Almost all branches are target-specific instruction, and a basic block can have more than one terminator. It's kind of fragile in certain situations, but it mostly works.

The reason I'm concerned here is that the InlineAsmBrIndirectTargets map doesn't cooperate with the other mechanism for tracking successors, so operations like splitting a basic block won't update it.

If we're going to store more information on the MachineInstr, I'd prefer to store it in the form of Operands, not some custom data structure.

If we're going to store more information on the MachineInstr, I'd prefer to store it in the form of Operands, not some custom data structure.

That sounds like you really really want MachineBasicBlocks as MachineOperands for INLINEASM_BR, as opposed to BlockAddresses?

The reason I'm concerned here is that the InlineAsmBrIndirectTargets map doesn't cooperate with the other mechanism for tracking successors, so operations like splitting a basic block won't update it.

Though MachineBasicBlock MachineOperands still doesn't necessarily integrate with successor tracking.

That sounds like you really really want MachineBasicBlocks as MachineOperands for INLINEASM_BR, as opposed to BlockAddresses?

Yes. :)

Though MachineBasicBlock MachineOperands still doesn't necessarily integrate with successor tracking.

It doesn't really need to. Any code that doesn't understand INLINEASM_BR will do the right thing anyway. There are other branch instructions that target-independent code can't analyze.

That sounds like you really really want MachineBasicBlocks as MachineOperands for INLINEASM_BR, as opposed to BlockAddresses?

Yes. :)

Ok, do note that BlockAddresses are used from IR down through AsmPrinter, so targeting replacing them first in INLINEASM_BR I think means that we'll have to recreate the BlockAddresses at some point. Once they're gone in MIR, we can remove them from callbr in LLVM IR.

Is this still relevant?

Herald added a project: Restricted Project. · View Herald TranscriptNov 17 2022, 2:32 PM
nickdesaulniers planned changes to this revision.Nov 18 2022, 9:20 AM
nickdesaulniers added inline comments.
llvm/lib/CodeGen/BranchFolding.cpp
177

I think we use just basic blocks now in inlineasm_br, not block addresses.