[BranchFolding] assert when removing INLINEASM_BR indirect targets

[nickdesaulniers]

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.

[efriedma]

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]

• inline comment, as per @efriedma

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]

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.

[nickdesaulniers]

• prefer llvm_unreachable to assert(false), as per @efriedma

[nickdesaulniers]

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?

[nickdesaulniers]

llvm/lib/CodeGen/BranchFolding.cpp

171

Or a more precise error string in the llvm_unreachable?

[nickdesaulniers]

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]

• delete transferInlineAsmBrIndirectTargets so that we can use isInlineAsmBrIndirectTarget correctly.

[efriedma]

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]

In D78234#1987870, @efriedma wrote:

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?

[efriedma]

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.

[nickdesaulniers]

In D78234#1989382, @efriedma wrote:

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.

[efriedma]

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.

[nickdesaulniers]

In D78234#1989777, @efriedma wrote:

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.

[arsenm]

Is this still relevant?

[nickdesaulniers]

llvm/lib/CodeGen/BranchFolding.cpp

177

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

llvm/include/llvm/CodeGen/MachineBasicBlock.h

bool isInlineAsmBrIndirectTarget(const MachineBasicBlock *Tgt) const {
     return InlineAsmBrIndirectTargets.count(Tgt);
   }
 
   /// Indicates if this is the indirect dest of an INLINEASM_BR.
   void addInlineAsmBrIndirectTarget(const MachineBasicBlock *Tgt) {
     InlineAsmBrIndirectTargets.insert(Tgt);
   }
 
-  /// Transfers indirect targets to INLINEASM_BR's copy block.
-  void transferInlineAsmBrIndirectTargets(MachineBasicBlock *CopyBB) {
-    for (auto *Target : InlineAsmBrIndirectTargets)
-      CopyBB->addInlineAsmBrIndirectTarget(Target);
-    return InlineAsmBrIndirectTargets.clear();
-  }
-
   /// Returns true if this is the default dest of an INLINEASM_BR.
   bool isInlineAsmBrDefaultTarget() const {
     return InlineAsmBrDefaultTarget;
   }
 
   /// Indicates if this is the default deft of an INLINEASM_BR.
   void setInlineAsmBrDefaultTarget() {
     InlineAsmBrDefaultTarget = true;

llvm/lib/CodeGen/BranchFolding.cpp

BranchFolder::BranchFolder(bool defaultEnableTailMerge, bool CommonHoist,
   case cl::BOU_TRUE: EnableTailMerge = true; break;
   case cl::BOU_FALSE: EnableTailMerge = false; break;
   }
 }
 
 void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) {
   assert(MBB->pred_empty() && "MBB must be dead!");
   LLVM_DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
+#ifndef NDEBUG
+  if (MBB->hasAddressTaken())
+    for (const MachineBasicBlock &Pred : *MBB->getParent())
+      // Iterating Pred.terminators() may be unreliable in this case.
+      // MachineBasicBlock#getFirstTerminator() iterates backwards through the
+      // MachineBasicBlock's MachineInstrs to the first non-Terminal, then
+      // moves forward one and returns that. If a non-terminator gets inserted
+      // after the INLINEASM_BR, perhaps by accident, then
+      // MachineBasicBlock#getFirstTerminator() and
+      // MachineBasicBlock#terminators() will not return the INLINEASM_BR
+      // terminator.
+      for (const MachineInstr &I : Pred)
+        if (I.getOpcode() == TargetOpcode::INLINEASM_BR)
+          for (const MachineOperand &Op : I.operands())
+            if (Op.isBlockAddress() && Pred.isInlineAsmBrIndirectTarget(MBB) &&
+                Op.getBlockAddress()->getBasicBlock() == MBB->getBasicBlock())
+              llvm_unreachable(
+                  "Removing MBB that's an indirect target of INLINEASM_BR");
+#endif
 
   MachineFunction *MF = MBB->getParent();
   // drop all successors.
   while (!MBB->succ_empty())
     MBB->removeSuccessor(MBB->succ_end()-1);
 
   // Avoid matching if this pointer gets reused.
   TriedMerging.erase(MBB);

llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp

for (const auto &MI : *CopyBB)
             CopyBB->addLiveIn(reg);
             break;
           }
         }
 
     CopyBB->normalizeSuccProbs();
     BB->normalizeSuccProbs();
 
-    BB->transferInlineAsmBrIndirectTargets(CopyBB);
-
     InsertPos = CopyBB->end();
     return CopyBB;
   }
 
   InsertPos = Emitter.getInsertPos();
   return Emitter.getBlock();
 }
 
 /// Return the basic block label.
 std::string ScheduleDAGSDNodes::getDAGName() const {
   return "sunit-dag." + BB->getFullName();
 }