[BPF] Implement mod operation

Implement BPF_MOD instruction to fix lack of assembly parser support mentioned in https://github.com/llvm/llvm-project/issues/55192.

Reviewed By: ast

Differential Rev

[BPF] Implement mod operation

Implement BPF_MOD instruction to fix lack of assembly parser support mentioned in https://github.com/llvm/llvm-project/issues/55192.

Reviewed By: ast

Differential Revision: https://reviews.llvm.org/D125207

show more ...

BPF: support inlining __builtin_memcmp intrinsic call

Delyan Kratunov reported an issue where __builtin_memcmp is
not inlined into simple load/compare instructions.
This is a known issue. In the cur

BPF: support inlining __builtin_memcmp intrinsic call

Delyan Kratunov reported an issue where __builtin_memcmp is
not inlined into simple load/compare instructions.
This is a known issue. In the current state, __builtin_memcmp
will be converted to memcmp call which won't work for
bpf programs.

This patch added support for expanding __builtin_memcmp with
actual loads and compares up to currently maximum 128 total loads.
The implementation is identical to PowerPC.

Differential Revision: https://reviews.llvm.org/D122676

show more ...

[llvm] Use nullptr instead of 0 (NFC)

Identified with modernize-use-nullptr.

[NFC][llvm] Inclusive language: reword and remove uses of sanity in llvm/lib/Target

Reworded removed code comments that contain `sanity check` and `sanity
test`.

BPF: implement isLegalAddressingMode() properly

Latest upstream llvm caused the kernel bpf selftest emitting the
following warnings:

In file included from progs/profiler3.c:6:
progs/profiler.in

BPF: implement isLegalAddressingMode() properly

Latest upstream llvm caused the kernel bpf selftest emitting the
following warnings:

In file included from progs/profiler3.c:6:
progs/profiler.inc.h:489:2: warning: loop not unrolled:
the optimizer was unable to perform the requested transformation;
the transformation might be disabled or specified as part of an unsupported
transformation ordering [-Wpass-failed=transform-warning]
for (int i = 0; i < MAX_PATH_DEPTH; i++) {
^

Further bisecting shows this SimplifyCFG patch ([1]) changed
the condition on how to fold branch to common dest. This caused
some unroll pragma is not honored in selftests/bpf.

The patch [1] test getUserCost() as the condition to
perform the certain basic block folding transformation.
For the above example, before the loop unroll pass, the control flow
looks like:
cond_block:
branch target: body_block, cleanup_block
body_block:
branch target: cleanup_block, end_block
end_block:
branch target: cleanup_block, end10_block
end10_block:
%add.ptr = getelementptr i8, i8* %payload.addr.0, i64 %call2
%inc = add nuw nsw i32 %i.0, 1
branch target: cond_block

In the above, %call2 is an unknown scalar.

Before patch [1], end10_block will be folded into end_block, forming
the code like
cond_block:
branch target: body_block, cleanup_block
body_block:
branch target: cleanup_block, end_block
end_block:
branch target: cleanup_block, cond_block
and the compiler is happy to perform unrolling.

With patch [1], getUserCost(), which calls getGEPCost(), which calls
isLegalAddressingMode() in TargetLoweringBase.cpp, considers IR
%add.ptr = getelementptr i8, i8* %payload.addr.0, i64 %call2
is free, so the above basic block folding transformation is not performed
and unrolling does not happen.

For BPF target, the IR
%add.ptr = getelementptr i8, i8* %payload.addr.0, i64 %call2
is not free and we don't have ld/st instruction address with 'r+r' mode.

This patch implemented a BPF hook for isLegalAddressingMode(), which is
identical to Mips isLegalAddressingMode() implementation where
the address pattern like 'r+r', 'r+r+i' or '2*r' are not allowed.
With testing kernel bpf selftests, all loop not unrolled warnings
are gone and all selftests run successfully.

[1] https://reviews.llvm.org/D108837

Differential Revision: https://reviews.llvm.org/D110789

show more ...

[BPF] add support for 32 bit registers in inline asm

Add "w" constraint type which allows selecting 32 bit registers.
32 bit registers were added in https://reviews.llvm.org/rGca31c3bb3ff149850b6648

[BPF] add support for 32 bit registers in inline asm

Add "w" constraint type which allows selecting 32 bit registers.
32 bit registers were added in https://reviews.llvm.org/rGca31c3bb3ff149850b664838fbbc7d40ce571879.

Differential Revision: https://reviews.llvm.org/D102118

show more ...

BPF: provide better error message for unsupported atomic operations

Currently, BPF backend does not support all variants of
atomic_load_{add,and,or,xor}, atomic_swap and atomic_cmp_swap
For exampl

BPF: provide better error message for unsupported atomic operations

Currently, BPF backend does not support all variants of
atomic_load_{add,and,or,xor}, atomic_swap and atomic_cmp_swap
For example, it only supports 32bit (with alu32 mode) and 64bit
operations for atomic_load_{and,or,xor}, atomic_swap and
atomic_cmp_swap. Due to historical reason, atomic_load_add is
always supported with 32bit and 64bit.

If user used an unsupported atomic operation, currently,
codegen selectiondag cannot find bpf support and will issue
a fatal error. This is not user friendly as user may mistakenly
think this is a compiler bug.

This patch added Custom rule for unsupported atomic operations
and will emit better error message during ReplaceNodeResults()
callback. The following is an example output.

$ cat t.c
short sync(short *p) {
return __sync_val_compare_and_swap (p, 2, 3);
}
$ clang -target bpf -O2 -g -c t.c
t.c:2:11: error: Unsupported atomic operations, please use 64 bit version
return __sync_val_compare_and_swap (p, 2, 3);
^
fatal error: error in backend: Cannot select: t19: i64,ch =
AtomicCmpSwap<(load store seq_cst seq_cst 2 on %ir.p)> t0, t2,
Constant:i64<2>, Constant:i64<3>, t.c:2:11
t2: i64,ch = CopyFromReg t0, Register:i64 %0
t1: i64 = Register %0
t11: i64 = Constant<2>
t10: i64 = Constant<3>
In function: sync
PLEASE submit a bug report ...

Fatal error will still happen since we did not really do proper
lowering for these unsupported atomic operations. But we do get
a much better error message.

Differential Revision: https://reviews.llvm.org/D98471

show more ...

[NFC] remove unused includes of SelectionDAGISel.h

[BPF] simplify zero extension with MOV_32_64

The current pattern matching for zext results in the following code snippet
being produced,

w1 = w0
r1 <<= 32
r1 >>= 32

Because BPF implementatio

[BPF] simplify zero extension with MOV_32_64

The current pattern matching for zext results in the following code snippet
being produced,

w1 = w0
r1 <<= 32
r1 >>= 32

Because BPF implementations require zero extension on 32bit loads this
both adds a few extra unneeded instructions but also makes it a bit
harder for the verifier to track the r1 register bounds. For example in
this verifier trace we see at the end of the snippet R2 offset is unknown.
However, if we track this correctly we see w1 should have the same bounds
as r8. R8 smax is less than U32 max value so a zero extend load should keep
the same value. Adding a max value of 800 (R8=inv(id=0,smax_value=800)) to
an off=0, as seen in R7 should create a max offset of 800. However at the
end of the snippet we note the R2 max offset is 0xffffFFFF.

R0=inv(id=0,smax_value=800)
R1_w=inv(id=0,umax_value=2147483647,var_off=(0x0; 0x7fffffff))
R6=ctx(id=0,off=0,imm=0) R7=map_value(id=0,off=0,ks=4,vs=1600,imm=0)
R8_w=inv(id=0,smax_value=800,umax_value=4294967295,var_off=(0x0; 0xffffffff))
R9=inv800 R10=fp0 fp-8=mmmm????
58: (1c) w9 -= w8
59: (bc) w1 = w8
60: (67) r1 <<= 32
61: (77) r1 >>= 32
62: (bf) r2 = r7
63: (0f) r2 += r1
64: (bf) r1 = r6
65: (bc) w3 = w9
66: (b7) r4 = 0
67: (85) call bpf_get_stack#67
R0=inv(id=0,smax_value=800)
R1_w=ctx(id=0,off=0,imm=0)
R2_w=map_value(id=0,off=0,ks=4,vs=1600,umax_value=4294967295,var_off=(0x0; 0xffffffff))
R3_w=inv(id=0,umax_value=800,var_off=(0x0; 0x3ff))
R4_w=inv0 R6=ctx(id=0,off=0,imm=0)
R7=map_value(id=0,off=0,ks=4,vs=1600,imm=0)
R8_w=inv(id=0,smax_value=800,umax_value=4294967295,var_off=(0x0; 0xffffffff))
R9_w=inv(id=0,umax_value=800,var_off=(0x0; 0x3ff))
R10=fp0 fp-8=mmmm????

After this patch R1 bounds are not smashed by the <<=32 >>=32 shift and we
get correct bounds on R2 umax_value=800.

Further it reduces 3 insns to 1.

Signed-off-by: John Fastabend <[email protected]>

Differential Revision: https://reviews.llvm.org/D73985

show more ...

[BPF] explicit warning of not supporting dynamic stack allocation

Currently, BPF does not support dynamic static allocation.
For a program like below:
extern void bar(int *);
void foo(int n) {

[BPF] explicit warning of not supporting dynamic stack allocation

Currently, BPF does not support dynamic static allocation.
For a program like below:
extern void bar(int *);
void foo(int n) {
int a[n];
bar(a);
}

The current error message looks like:
unimplemented operand
UNREACHABLE executed at /.../llvm/lib/Target/BPF/BPFISelLowering.cpp:199!

Let us make error message explicit so it will be clear to the user
what is the problem. With this patch, the error message looks like:
fatal error: error in backend: Unsupported dynamic stack allocation
...

Differential Revision: https://reviews.llvm.org/D74521

show more ...

[BPF] implement isTruncateFree and isZExtFree in BPFTargetLowering

Currently, isTruncateFree() and isZExtFree() callbacks return false
as they are not implemented in BPF backend. This may cause subo

[BPF] implement isTruncateFree and isZExtFree in BPFTargetLowering

Currently, isTruncateFree() and isZExtFree() callbacks return false
as they are not implemented in BPF backend. This may cause suboptimal
code generation. For example, if the load in the context of zero extension
has more than one use, the pattern zextload{i8,i16,i32} will
not be generated. Rather, the load will be matched first and
then the result is zero extended.

For example, in the test together with this commit, we have
I1: %0 = load i32, i32* %data_end1, align 4, !tbaa !2
I2: %conv = zext i32 %0 to i64
...
I3: %2 = load i32, i32* %data, align 4, !tbaa !7
I4: %conv2 = zext i32 %2 to i64
...
I5: %4 = trunc i64 %sub.ptr.lhs.cast to i32
I6: %conv13 = sub i32 %4, %2
...

The I1 and I2 will match to one zextloadi32 DAG node, where SUBREG_TO_REG is
used to convert a 32bit register to 64bit one. During code generation,
SUBREG_TO_REG is a noop.

The %2 in I3 is used in both I4 and I6. If isTruncateFree() is false,
the current implementation will generate a SLL_ri and SRL_ri
for the zext part during lowering.

This patch implement isTruncateFree() in the BPF backend, so for the
above example, I3 and I4 will generate a zextloadi32 DAG node with
SUBREG_TO_REG is generated during lowering to Machine IR.

isZExtFree() is also implemented as it should help code gen as well.

This patch also enables the change in https://reviews.llvm.org/D73985
since it won't kick in generates MOV_32_64 machine instruction.

Differential Revision: https://reviews.llvm.org/D74101

show more ...

[Alignment][NFC] Remove unneeded llvm:: scoping on Align types

llvm-svn: 373081

[Alignment][NFC] Use Align with TargetLowering::setPrefFunctionAlignment

Summary:
This is patch is part of a series to introduce an Alignment type.
See this thread for context: http://lists.llvm.org

[Alignment][NFC] Use Align with TargetLowering::setPrefFunctionAlignment

Summary:
This is patch is part of a series to introduce an Alignment type.
See this thread for context: http://lists.llvm.org/pipermail/llvm-dev/2019-July/133851.html
See this patch for the introduction of the type: https://reviews.llvm.org/D64790

Reviewers: courbet

Subscribers: nemanjai, javed.absar, hiraditya, kbarton, asb, rbar, johnrusso, simoncook, apazos, sabuasal, niosHD, jrtc27, MaskRay, zzheng, edward-jones, rogfer01, MartinMosbeck, brucehoult, the_o, PkmX, jocewei, jsji, s.egerton, pzheng, ychen, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D67267

llvm-svn: 371212

show more ...

[Alignment][NFC] Use Align with TargetLowering::setMinFunctionAlignment

Summary:
This is patch is part of a series to introduce an Alignment type.
See this thread for context: http://lists.llvm.org/

[Alignment][NFC] Use Align with TargetLowering::setMinFunctionAlignment

Summary:
This is patch is part of a series to introduce an Alignment type.
See this thread for context: http://lists.llvm.org/pipermail/llvm-dev/2019-July/133851.html
See this patch for the introduction of the type: https://reviews.llvm.org/D64790

Reviewers: courbet

Subscribers: jyknight, sdardis, nemanjai, javed.absar, hiraditya, kbarton, fedor.sergeev, asb, rbar, johnrusso, simoncook, apazos, sabuasal, niosHD, jrtc27, MaskRay, zzheng, edward-jones, atanasyan, rogfer01, MartinMosbeck, brucehoult, the_o, PkmX, jocewei, jsji, s.egerton, pzheng, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D67229

llvm-svn: 371200

show more ...

[LLVM][Alignment] Make functions using log of alignment explicit

Summary:
This patch renames functions that takes or returns alignment as log2, this patch will help with the transition to llvm::Alig

[LLVM][Alignment] Make functions using log of alignment explicit

Summary:
This patch renames functions that takes or returns alignment as log2, this patch will help with the transition to llvm::Align.
The renaming makes it explicit that we deal with log(alignment) instead of a power of two alignment.
A few renames uncovered dubious assignments:

- `MirParser`/`MirPrinter` was expecting powers of two but `MachineFunction` and `MachineBasicBlock` were using deal with log2(align). This patch fixes it and updates the documentation.
- `MachineBlockPlacement` exposes two flags (`align-all-blocks` and `align-all-nofallthru-blocks`) supposedly interpreted as power of two alignments, internally these values are interpreted as log2(align). This patch updates the documentation,
- `MachineFunctionexposes` exposes `align-all-functions` also interpreted as power of two alignment, internally this value is interpreted as log2(align). This patch updates the documentation,

Reviewers: lattner, thegameg, courbet

Subscribers: dschuff, arsenm, jyknight, dylanmckay, sdardis, nemanjai, jvesely, nhaehnle, javed.absar, hiraditya, kbarton, fedor.sergeev, asb, rbar, johnrusso, simoncook, apazos, sabuasal, niosHD, jrtc27, MaskRay, zzheng, edward-jones, atanasyan, rogfer01, MartinMosbeck, brucehoult, the_o, dexonsmith, PkmX, jocewei, jsji, Jim, s.egerton, llvm-commits, courbet

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D65945

llvm-svn: 371045

show more ...

Apply llvm-prefer-register-over-unsigned from clang-tidy to LLVM

Summary:
This clang-tidy check is looking for unsigned integer variables whose initializer
starts with an implicit cast from llvm::Re

Apply llvm-prefer-register-over-unsigned from clang-tidy to LLVM

Summary:
This clang-tidy check is looking for unsigned integer variables whose initializer
starts with an implicit cast from llvm::Register and changes the type of the
variable to llvm::Register (dropping the llvm:: where possible).

Partial reverts in:
X86FrameLowering.cpp - Some functions return unsigned and arguably should be MCRegister
X86FixupLEAs.cpp - Some functions return unsigned and arguably should be MCRegister
X86FrameLowering.cpp - Some functions return unsigned and arguably should be MCRegister
HexagonBitSimplify.cpp - Function takes BitTracker::RegisterRef which appears to be unsigned&
MachineVerifier.cpp - Ambiguous operator==() given MCRegister and const Register
PPCFastISel.cpp - No Register::operator-=()
PeepholeOptimizer.cpp - TargetInstrInfo::optimizeLoadInstr() takes an unsigned&
MachineTraceMetrics.cpp - MachineTraceMetrics lacks a suitable constructor

Manual fixups in:
ARMFastISel.cpp - ARMEmitLoad() now takes a Register& instead of unsigned&
HexagonSplitDouble.cpp - Ternary operator was ambiguous between unsigned/Register
HexagonConstExtenders.cpp - Has a local class named Register, used llvm::Register instead of Register.
PPCFastISel.cpp - PPCEmitLoad() now takes a Register& instead of unsigned&

Depends on D65919

Reviewers: arsenm, bogner, craig.topper, RKSimon

Reviewed By: arsenm

Subscribers: RKSimon, craig.topper, lenary, aemerson, wuzish, jholewinski, MatzeB, qcolombet, dschuff, jyknight, dylanmckay, sdardis, nemanjai, jvesely, wdng, nhaehnle, sbc100, jgravelle-google, kristof.beyls, hiraditya, aheejin, kbarton, fedor.sergeev, javed.absar, asb, rbar, johnrusso, simoncook, apazos, sabuasal, niosHD, jrtc27, MaskRay, zzheng, edward-jones, atanasyan, rogfer01, MartinMosbeck, brucehoult, the_o, tpr, PkmX, jocewei, jsji, Petar.Avramovic, asbirlea, Jim, s.egerton, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D65962

llvm-svn: 369041

show more ...

[BPF] add code-gen support for JMP32 instructions

JMP32 instructions has been added to eBPF ISA. They are 32-bit variants of
existing BPF conditional jump instructions, but the comparison happens on

[BPF] add code-gen support for JMP32 instructions

JMP32 instructions has been added to eBPF ISA. They are 32-bit variants of
existing BPF conditional jump instructions, but the comparison happens on
low 32-bit sub-register only, therefore some unnecessary extensions could
be saved.

JMP32 instructions will only be available for -mcpu=v3. Host probe hook has
been updated accordingly.

JMP32 instructions will only be enabled in code-gen when -mattr=+alu32
enabled, meaning compiling the program using sub-register mode.

For JMP32 encoding, it is a new instruction class, and is using the
reserved eBPF class number 0x6.

This patch has been tested by compiling and running kernel bpf selftests
with JMP32 enabled.

Acked-by: Yonghong Song <[email protected]>
Signed-off-by: Jiong Wang <[email protected]>
llvm-svn: 353384

show more ...

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the ne

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the new license. We checked this carefully with the
Foundation's lawyer and we believe this is the correct approach.

Essentially, all code in the project is now made available by the LLVM
project under our new license, so you will see that the license headers
include that license only. Some of our contributors have contributed
code under our old license, and accordingly, we have retained a copy of
our old license notice in the top-level files in each project and
repository.

llvm-svn: 351636

show more ...

bpf: new option -bpf-expand-memcpy-in-order to expand memcpy in order

Some BPF JIT backends would want to optimize memcpy in their own
architecture specific way.

However, at the moment, there is no

bpf: new option -bpf-expand-memcpy-in-order to expand memcpy in order

Some BPF JIT backends would want to optimize memcpy in their own
architecture specific way.

However, at the moment, there is no way for JIT backends to see memcpy
semantics in a reliable way. This is due to LLVM BPF backend is expanding
memcpy into load/store sequences and could possibly schedule them apart from
each other further. So, BPF JIT backends inside kernel can't reliably
recognize memcpy semantics by peephole BPF sequence.

This patch introduce new intrinsic expand infrastructure to memcpy.

To get stable in-order load/store sequence from memcpy, we first lower
memcpy into BPF::MEMCPY node which then expanded into in-order load/store
sequences in expandPostRAPseudo pass which will happen after instruction
scheduling. By this way, kernel JIT backends could reliably recognize
memcpy through scanning BPF sequence.

This new memcpy expand infrastructure is gated by a new option:

-bpf-expand-memcpy-in-order

Acked-by: Jakub Kicinski <[email protected]>
Signed-off-by: Jiong Wang <[email protected]>
Signed-off-by: Yonghong Song <[email protected]>
llvm-svn: 337977

show more ...

Set ADDE/ADDC/SUBE/SUBC to expand by default

Summary:
They've been deprecated in favor of UADDO/ADDCARRY or USUBO/SUBCARRY for a while.

Target that uses these opcodes are changed in order to ensure

Set ADDE/ADDC/SUBE/SUBC to expand by default

Summary:
They've been deprecated in favor of UADDO/ADDCARRY or USUBO/SUBCARRY for a while.

Target that uses these opcodes are changed in order to ensure their behavior doesn't change.

Reviewers: efriedma, craig.topper, dblaikie, bkramer

Subscribers: jholewinski, arsenm, jyknight, sdardis, nemanjai, nhaehnle, kbarton, fedor.sergeev, asb, rbar, johnrusso, simoncook, jordy.potman.lists, apazos, sabuasal, niosHD, jrtc27, zzheng, edward-jones, mgrang, atanasyan, llvm-commits

Differential Revision: https://reviews.llvm.org/D47422

llvm-svn: 333748

show more ...

bpf: fix incorrect SELECT_CC lowering

Commit 37962a331c77 ("bpf: Improve expanding logic in LowerSELECT_CC")
intended to improve code quality for certain jmp conditions. The
commit, however, has a c

bpf: fix incorrect SELECT_CC lowering

Commit 37962a331c77 ("bpf: Improve expanding logic in LowerSELECT_CC")
intended to improve code quality for certain jmp conditions. The
commit, however, has a couple of issues:
(1). In code, just swap is not enough, ConditionalCode CC
should also be swapped, otherwise incorrect code will
be generated.
(2). The ConditionalCode swap should be subject to
getHasJmpExt(). If getHasJmpExt() is False, certain
conditional codes will not be supported and swap
may generate incorrect code.

The original goal for this patch is to optimize jmp operations
which does not have JmpExt turned on. If JmpExt is on,
better code could be generated. For example, the test
select_ri.ll is introduced to demonstrate the optimization.
The same result can be achieved with -mcpu=v2 flag.

Signed-off-by: Yonghong Song <[email protected]>
Acked-by: Alexei Starovoitov <[email protected]>
llvm-svn: 329043

show more ...

[IR][CodeGen] Remove dependency on EVT from IR/Function.cpp. Move EVT to CodeGen layer.

Currently EVT is in the IR layer only because of Function.cpp needing a very small piece of the functionality

[IR][CodeGen] Remove dependency on EVT from IR/Function.cpp. Move EVT to CodeGen layer.

Currently EVT is in the IR layer only because of Function.cpp needing a very small piece of the functionality of EVT::getEVTString(). The rest of EVT is used in codegen making CodeGen a better place for it.

The previous code converted a Type* to EVT and then called getEVTString. This was only expected to handle the primitive types from Type*. Since there only a few primitive types, we can just print them as strings directly.

Differential Revision: https://reviews.llvm.org/D45017

llvm-svn: 328806

show more ...

Fix layering by moving ValueTypes.h from CodeGen to IR

ValueTypes.h is implemented in IR already.

llvm-svn: 328397

bpf: Don't expand BSWAP on i32, promote it

Currently, there is no ALU32 bswap support in eBPF ISA.

BSWAP on i32 was set to EXPAND which would need about eight instructions
for single BSWAP.

It wou

bpf: Don't expand BSWAP on i32, promote it

Currently, there is no ALU32 bswap support in eBPF ISA.

BSWAP on i32 was set to EXPAND which would need about eight instructions
for single BSWAP.

It would be more efficient to promote it to i64, then doing BSWAP on i64.
For eBPF programs, most of the promotion are zero extensions which are
likely be elimiated later by peephole optimizations.

Signed-off-by: Jiong Wang <[email protected]>
Signed-off-by: Yonghong Song <[email protected]>
llvm-svn: 327369

show more ...

bpf: Enable 32-bit subregister support for -mattr=+alu32

After all those preparation patches, now we could enable 32-bit subregister
support once -mattr=+alu32 specified.

Signed-off-by: Jiong Wang

bpf: Enable 32-bit subregister support for -mattr=+alu32

After all those preparation patches, now we could enable 32-bit subregister
support once -mattr=+alu32 specified.

Signed-off-by: Jiong Wang <[email protected]>
Reviewed-by: Yonghong Song <[email protected]>
llvm-svn: 325989

show more ...