c3fb2e1cee
Add jump table (switch statement and computed goto) support for BPF
backend.
A `gotox <reg>` insn is implemented and the `<reg>` holds the target
insn where the gotox will go.
For a switch statement like
```
...
switch (ctx->x) {
case 1: ret_user = 18; break;
case 20: ret_user = 6; break;
case 16: ret_user = 9; break;
case 6: ret_user = 16; break;
case 8: ret_user = 14; break;
case 30: ret_user = 2; break;
default: ret_user = 1; break;
}
...
```
and the final binary
```
The final binary:
4: 67 01 00 00 03 00 00 00 r1 <<= 0x3
5: 18 02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r2 = 0x0 ll
0000000000000028: R_BPF_64_64 BPF.JT.0.0
7: 0f 12 00 00 00 00 00 00 r2 += r1
...
Symbol table:
4: 0000000000000000 240 OBJECT GLOBAL DEFAULT 4 BPF.JT.0.0
5: 0000000000000000 4 OBJECT GLOBAL DEFAULT 6 ret_user
6: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND bar
7: 00000000000000f0 256 OBJECT GLOBAL DEFAULT 4 BPF.JT.0.1
and
[ 4] .jumptables PROGBITS 0000000000000000 0001c8 0001f0 00 0 0 1
```
Note that for the above example, `-mllvm -bpf-min-jump-table-entries=5`
should be in compilation flags as the current default
bpf-min-jump-table-entries is 13. For example.
```
clang --target=bpf -mcpu=v4 -O2 -mllvm -bpf-min-jump-table-entries=5 -S -g test.c
```
For computed goto like
```
int foo(int a, int b) {
__label__ l1, l2, l3, l4;
void *jt1[] = {[0]=&&l1, [1]=&&l2};
void *jt2[] = {[0]=&&l3, [1]=&&l4};
int ret = 0;
goto *jt1[a % 2];
l1: ret += 1;
l2: ret += 3;
goto *jt2[b % 2];
l3: ret += 5;
l4: ret += 7;
return ret;
}
```
The final binary:
```
12: bf 23 20 00 00 00 00 00 r3 = (s32)r2
13: 67 03 00 00 03 00 00 00 r3 <<= 0x3
14: 18 02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r2 = 0x0 ll
0000000000000070: R_BPF_64_64 BPF.JT.0.0
16: 0f 32 00 00 00 00 00 00 r2 += r3
17: bf 11 20 00 00 00 00 00 r1 = (s32)r1
18: 67 01 00 00 03 00 00 00 r1 <<= 0x3
19: 18 03 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r3 = 0x0 ll
0000000000000098: R_BPF_64_64 BPF.JT.0.1
21: 0f 13 00 00 00 00 00 00 r3 += r1
[ 4] .jumptables PROGBITS 0000000000000000 000160 000020 00 0 0 1
4: 0000000000000000 16 OBJECT GLOBAL DEFAULT 4 BPF.JT.0.0
5: 0000000000000010 16 OBJECT GLOBAL DEFAULT 4 BPF.JT.0.1
```
A more complicated test with both switch-statement triggered jump table
and compute gotos:
```
$ cat test3.c
struct simple_ctx {
int x;
int y;
int z;
};
int ret_user, ret_user2;
void bar(void);
int foo(struct simple_ctx *ctx, struct simple_ctx *ctx2, int a, int b)
{
__label__ l1, l2, l3, l4;
void *jt1[] = {[0]=&&l1, [1]=&&l2};
void *jt2[] = {[0]=&&l3, [1]=&&l4};
int ret = 0;
goto *jt1[a % 2];
l1: ret += 1;
l2: ret += 3;
goto *jt2[b % 2];
l3: ret += 5;
l4: ret += 7;
bar();
switch (ctx->x) {
case 1: ret_user = 18; break;
case 20: ret_user = 6; break;
case 16: ret_user = 9; break;
case 6: ret_user = 16; break;
case 8: ret_user = 14; break;
case 30: ret_user = 2; break;
default: ret_user = 1; break;
}
return ret;
}
```
Compile with
```
clang --target=bpf -mcpu=v4 -O2 -S test3.c
clang --target=bpf -mcpu=v4 -O2 -c test3.c
```
The binary:
```
/* For computed goto */
13: bf 42 20 00 00 00 00 00 r2 = (s32)r4
14: 67 02 00 00 03 00 00 00 r2 <<= 0x3
15: 18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0x0 ll
0000000000000078: R_BPF_64_64 BPF.JT.0.1
17: 0f 21 00 00 00 00 00 00 r1 += r2
18: bf 32 20 00 00 00 00 00 r2 = (s32)r3
19: 67 02 00 00 03 00 00 00 r2 <<= 0x3
20: 18 03 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r3 = 0x0 ll
00000000000000a0: R_BPF_64_64 BPF.JT.0.2
22: 0f 23 00 00 00 00 00 00 r3 += r2
/* For switch statement */
39: 67 01 00 00 03 00 00 00 r1 <<= 0x3
40: 18 02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r2 = 0x0 ll
0000000000000140: R_BPF_64_64 BPF.JT.0.0
42: 0f 12 00 00 00 00 00 00 r2 += r1
```
You can see jump table symbols are all different.
91 lines
2.9 KiB
C++
91 lines
2.9 KiB
C++
//=-- BPFMCInstLower.cpp - Convert BPF MachineInstr to an MCInst ------------=//
|
|
//
|
|
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
|
|
// See https://llvm.org/LICENSE.txt for license information.
|
|
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This file contains code to lower BPF MachineInstrs to their corresponding
|
|
// MCInst records.
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#include "BPFMCInstLower.h"
|
|
#include "BPFAsmPrinter.h"
|
|
#include "BPFISelLowering.h"
|
|
#include "llvm/CodeGen/AsmPrinter.h"
|
|
#include "llvm/CodeGen/MachineBasicBlock.h"
|
|
#include "llvm/CodeGen/MachineInstr.h"
|
|
#include "llvm/MC/MCAsmInfo.h"
|
|
#include "llvm/MC/MCContext.h"
|
|
#include "llvm/MC/MCExpr.h"
|
|
#include "llvm/MC/MCInst.h"
|
|
#include "llvm/MC/MCStreamer.h"
|
|
#include "llvm/Support/ErrorHandling.h"
|
|
#include "llvm/Support/raw_ostream.h"
|
|
using namespace llvm;
|
|
|
|
MCSymbol *
|
|
BPFMCInstLower::GetGlobalAddressSymbol(const MachineOperand &MO) const {
|
|
return Printer.getSymbol(MO.getGlobal());
|
|
}
|
|
|
|
MCSymbol *
|
|
BPFMCInstLower::GetExternalSymbolSymbol(const MachineOperand &MO) const {
|
|
return Printer.GetExternalSymbolSymbol(MO.getSymbolName());
|
|
}
|
|
|
|
MCOperand BPFMCInstLower::LowerSymbolOperand(const MachineOperand &MO,
|
|
MCSymbol *Sym) const {
|
|
|
|
const MCExpr *Expr = MCSymbolRefExpr::create(Sym, Ctx);
|
|
|
|
if (!MO.isJTI() && MO.getOffset())
|
|
llvm_unreachable("unknown symbol op");
|
|
|
|
return MCOperand::createExpr(Expr);
|
|
}
|
|
|
|
void BPFMCInstLower::Lower(const MachineInstr *MI, MCInst &OutMI) const {
|
|
OutMI.setOpcode(MI->getOpcode());
|
|
|
|
for (const MachineOperand &MO : MI->operands()) {
|
|
MCOperand MCOp;
|
|
switch (MO.getType()) {
|
|
default:
|
|
MI->print(errs());
|
|
llvm_unreachable("unknown operand type");
|
|
case MachineOperand::MO_Register:
|
|
// Ignore all implicit register operands.
|
|
if (MO.isImplicit())
|
|
continue;
|
|
MCOp = MCOperand::createReg(MO.getReg());
|
|
break;
|
|
case MachineOperand::MO_Immediate:
|
|
MCOp = MCOperand::createImm(MO.getImm());
|
|
break;
|
|
case MachineOperand::MO_MachineBasicBlock:
|
|
MCOp = MCOperand::createExpr(
|
|
MCSymbolRefExpr::create(MO.getMBB()->getSymbol(), Ctx));
|
|
break;
|
|
case MachineOperand::MO_RegisterMask:
|
|
continue;
|
|
case MachineOperand::MO_ExternalSymbol:
|
|
MCOp = LowerSymbolOperand(MO, GetExternalSymbolSymbol(MO));
|
|
break;
|
|
case MachineOperand::MO_GlobalAddress:
|
|
MCOp = LowerSymbolOperand(MO, GetGlobalAddressSymbol(MO));
|
|
break;
|
|
case MachineOperand::MO_ConstantPoolIndex:
|
|
MCOp = LowerSymbolOperand(MO, Printer.GetCPISymbol(MO.getIndex()));
|
|
break;
|
|
case MachineOperand::MO_JumpTableIndex:
|
|
MCOp = LowerSymbolOperand(MO, Printer.getJTPublicSymbol(MO.getIndex()));
|
|
break;
|
|
}
|
|
|
|
OutMI.addOperand(MCOp);
|
|
}
|
|
}
|