[BPF] Remove 'may_goto 0' instructions

[yonghong-song]

Emil Tsalapatis from Meta reported such a case where 'may_goto 0' insn is generated by clang compiler. But 'may_goto 0' insn is actually a no-op so it makes sense to remove that in llvm. The patch is also able to handle the following code pattern

   ...
   may_goto 2
   may_goto 1
   may_goto 0
   ...

where three may_goto insns can all be removed.

[4ast]

wouldn't it be cleaner to do after inline asm was processed into proper insns ? Instead of string match?

[eddyz87]

I agree with Alexei, this should be done at machine instruction level.

[eddyz87]

On the other hand, after assembly instructions are compiled, there is no way to distinguish may_goto +0 from may_goto <param>, where param is 0. Removal of explicit may_goto +0 goes against what we do for goto +0.

[eddyz87]

Also, I'm not sure there is a good hook to attach to. When using gdb to break and see where assembler is called to parse the inline assembly, it looks like parsed instruction is written directly to the output stream:

    at /home/eddy/work/llvm-project/llvm/lib/Target/BPF/AsmParser/BPFAsmParser.cpp:309
309	  MCInst Inst;
(gdb) bt
#0  (anonymous namespace)::BPFAsmParser::matchAndEmitInstruction (this=0x350df0, IDLoc=..., Opcode=<optimized out>, Operands=..., Out=..., ErrorInfo=@0x7fffffff1ca0: 0, MatchingInlineAsm=<optimized out>)
    at /home/eddy/work/llvm-project/llvm/lib/Target/BPF/AsmParser/BPFAsmParser.cpp:309
#1  0x00007ffff71ba292 in (anonymous namespace)::AsmParser::parseAndMatchAndEmitTargetInstruction (this=this@entry=0x290af0, Info=..., IDVal=..., ID=..., IDLoc=...) at /home/eddy/work/llvm-project/llvm/lib/MC/MCParser/AsmParser.cpp:2390
#2  0x00007ffff71ade4c in (anonymous namespace)::AsmParser::parseStatement (this=0x290af0, Info=..., SI=0x0) at /home/eddy/work/llvm-project/llvm/lib/MC/MCParser/AsmParser.cpp:2323
#3  0x00007ffff71a78d1 in (anonymous namespace)::AsmParser::Run (this=0x290af0, NoInitialTextSection=<optimized out>, NoFinalize=true) at /home/eddy/work/llvm-project/llvm/lib/MC/MCParser/AsmParser.cpp:1005
#4  0x00007ffff4570327 in llvm::AsmPrinter::emitInlineAsm (this=this@entry=0x373770, Str=..., STI=..., MCOptions=..., LocMDNode=LocMDNode@entry=0x30cf58, Dialect=llvm::InlineAsm::AD_ATT)
    at /home/eddy/work/llvm-project/llvm/lib/CodeGen/AsmPrinter/AsmPrinterInlineAsm.cpp:129
#5  0x00007ffff4571560 in llvm::AsmPrinter::emitInlineAsm (this=0x373770, MI=0x3847a8) at /home/eddy/work/llvm-project/llvm/lib/CodeGen/AsmPrinter/AsmPrinterInlineAsm.cpp:418
#6  0x00007ffff45593a7 in llvm::AsmPrinter::emitFunctionBody (this=0x373770) at /home/eddy/work/llvm-project/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp:1879
#7  0x00007ffff7f6cc15 in llvm::AsmPrinter::runOnMachineFunction (this=0x373770, MF=...) at /home/eddy/work/llvm-project/llvm/include/llvm/CodeGen/AsmPrinter.h:389

The parsing is done late in the pipeline and it's result is written directly either to object stream or to text output. So the only place seem to be BPFAsmParser::matchAndEmitInstruction() where some post-processing could be done.

[yonghong-song]

matchAndEmitInstruction() handles one instruction only. So this is not a good place to do 'may_goto 0' elimination work.

[yonghong-song]

I checked other targets (X86, Arm) etc. They also parse and processes asm strings. For example, in ARM/ARMISelLowering.cpp,

ARM/ARMISelLowering.cpp:

bool ARMTargetLowering::ExpandInlineAsm(CallInst *CI) const {
  // Looking for "rev" which is V6+.
  if (!Subtarget->hasV6Ops())
    return false;

  InlineAsm *IA = cast<InlineAsm>(CI->getCalledOperand());
  StringRef AsmStr = IA->getAsmString();
  SmallVector<StringRef, 4> AsmPieces;
  SplitString(AsmStr, AsmPieces, ";\n");

  switch (AsmPieces.size()) {
  default: return false;
  case 1:
    AsmStr = AsmPieces[0];
    AsmPieces.clear();
    SplitString(AsmStr, AsmPieces, " \t,");

    // rev $0, $1
    if (AsmPieces.size() == 3 &&
        AsmPieces[0] == "rev" && AsmPieces[1] == "$0" && AsmPieces[2] == "$1" &&
        IA->getConstraintString().compare(0, 4, "=l,l") == 0) {
      IntegerType *Ty = dyn_cast<IntegerType>(CI->getType());
      if (Ty && Ty->getBitWidth() == 32)
        return IntrinsicLowering::LowerToByteSwap(CI);
    }
    break;
  }

  return false;
}

So use one of backend passes might be the better choice.

[eddyz87]

I get a compiler crash with the following test case:

$ cat test.c
void bar() {
  asm volatile goto ("may_goto %l[lbl];"::::lbl);
  asm volatile("may_goto +0;");
 lbl:
  return;
}
$ clang -O2 --target=bpf -S test.c -o - 2>&1 | head -n20
clang: /home/eddy/work/llvm-project/llvm/include/llvm/CodeGen/MachineInstr.h:590: MachineOperand &llvm::MachineInstr::getOperand(unsigned int): Assertion `i < getNumOperands() && "getOperand() out of range!"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.	Program arguments: clang -O2 --target=bpf -S test.c -o -
1.	<eof> parser at end of file
2.	Code generation
3.	Running pass 'Function Pass Manager' on module 'test.c'.
4.	Running pass 'BPF PreEmit Peephole Optimization' on function '@bar'
 #0 0x00007fd5e35fe388 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /home/eddy/work/llvm-project/llvm/lib/Support/Unix/Signals.inc:794:13
 #1 0x00007fd5e35fc260 llvm::sys::RunSignalHandlers() /home/eddy/work/llvm-project/llvm/lib/Support/Signals.cpp:106:18
 #2 0x00007fd5e353e7d6 (anonymous namespace)::CrashRecoveryContextImpl::HandleCrash(int, unsigned long) /home/eddy/work/llvm-project/llvm/lib/Support/CrashRecoveryContext.cpp:73:5
 #3 0x00007fd5e353e7d6 CrashRecoverySignalHandler(int) /home/eddy/work/llvm-project/llvm/lib/Support/CrashRecoveryContext.cpp:390:51
 #4 0x00007fd5e2e26090 __restore_rt (/lib64/libc.so.6+0x1a090)
 #5 0x00007fd5e2e7f0f4 __pthread_kill_implementation /usr/src/debug/glibc-2.40-17.fc41.x86_64/nptl/pthread_kill.c:44:76
 #6 0x00007fd5e2e25fde gsignal /usr/src/debug/glibc-2.40-17.fc41.x86_64/signal/../sysdeps/posix/raise.c:27:6
 #7 0x00007fd5e2e0d942 abort /usr/src/debug/glibc-2.40-17.fc41.x86_64/stdlib/abort.c:81:7
 #8 0x00007fd5e2e0d85e _nl_load_domain.cold /usr/src/debug/glibc-2.40-17.fc41.x86_64/intl/loadmsgcat.c:1177:9
 #9 0x00007fd5e2e1e107 (/lib64/libc.so.6+0x12107)
#10 0x00007fd5e9e2355a (anonymous namespace)::BPFMIPreEmitPeephole::runOnMachineFunction(llvm::MachineFunction&) /home/eddy/work/llvm-project/llvm/lib/Target/BPF/BPFMIPeephole.cpp:0:0
#11 0x00007fd5e75b31d7 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /home/eddy/work/llvm-project/llvm/lib/CodeGen/MachineFunctionPass.cpp:0:13

[eddyz87]

And the following example appears to be miscompiled:

$ cat test.c
void bar() {
  asm volatile goto ("may_goto %l[lbl];"::::lbl);
  asm volatile goto ("may_goto %l[lbl];"::::lbl);
  asm volatile goto ("may_goto %l[lbl];"::::lbl);
  asm volatile goto ("r0 = 42;");
 lbl:
  return;
}
$ clang -O2 --target=bpf -S test.c -o - 2>&1 | head -n20
	.file	"test.c"
	.text
	.globl	bar                             # -- Begin function bar
	.p2align	3
	.type	bar,@function
bar:                                    # @bar
# %bb.0:                                # %entry
	#APP
	may_goto LBB0_4

	#NO_APP
# %bb.1:                                # %asm.fallthrough
	#APP
	may_goto LBB0_4

	#NO_APP
# %bb.2:                                # %asm.fallthrough1
	#APP
	may_goto LBB0_4

(Note the disappearance of the "r0 = 42;").

[yonghong-song]

@eddyz87 Thanks for the error cases and suggestion to avoid ToErase variable. Will investigate all these issues.

[yonghong-song]

Updated a new revision to address @eddyz87 reported issues. Specifically, the changes are:

• Check INLINEASM_BR instead of INLINEASM, this is the source of errors reported by @eddyz87 earlier
• Use llvm::make_early_inc_range for better code