From: Jakub Kicinski <jakub.kicinski@netronome.com>
To: alexei.starovoitov@gmail.com, daniel@iogearbox.net
Cc: Song Liu <songliubraving@fb.com>,
oss-drivers@netronome.com, netdev@vger.kernel.org,
Jiong Wang <jiong.wang@netronome.com>
Subject: [PATCH bpf-next v2 6/6] nfp: bpf: migrate to advanced reciprocal divide in reciprocal_div.h
Date: Fri, 6 Jul 2018 15:13:23 -0700 [thread overview]
Message-ID: <20180706221323.31688-7-jakub.kicinski@netronome.com> (raw)
In-Reply-To: <20180706221323.31688-1-jakub.kicinski@netronome.com>
From: Jiong Wang <jiong.wang@netronome.com>
As we are doing JIT, we would want to use the advanced version of the
reciprocal divide (reciprocal_value_adv) to trade performance with host.
We could reduce the required ALU instructions from 4 to 2 or 1.
Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
Reviewed-by: Jakub Kicinski <jakub.kicinski@netronome.com>
---
drivers/net/ethernet/netronome/nfp/bpf/jit.c | 64 ++++++++++++++++----
1 file changed, 53 insertions(+), 11 deletions(-)
diff --git a/drivers/net/ethernet/netronome/nfp/bpf/jit.c b/drivers/net/ethernet/netronome/nfp/bpf/jit.c
index 7c9ee3d85907..1d9e36835404 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/jit.c
+++ b/drivers/net/ethernet/netronome/nfp/bpf/jit.c
@@ -1497,8 +1497,8 @@ wrp_mul(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta,
static int wrp_div_imm(struct nfp_prog *nfp_prog, u8 dst, u64 imm)
{
swreg dst_both = reg_both(dst), dst_a = reg_a(dst), dst_b = reg_a(dst);
- struct reciprocal_value rvalue;
- swreg tmp_b = imm_b(nfp_prog);
+ struct reciprocal_value_adv rvalue;
+ u8 pre_shift, exp;
swreg magic;
if (imm > U32_MAX) {
@@ -1506,16 +1506,58 @@ static int wrp_div_imm(struct nfp_prog *nfp_prog, u8 dst, u64 imm)
return 0;
}
- rvalue = reciprocal_value(imm);
+ /* NOTE: because we are using "reciprocal_value_adv" which doesn't
+ * support "divisor > (1u << 31)", we need to JIT separate NFP sequence
+ * to handle such case which actually equals to the result of unsigned
+ * comparison "dst >= imm" which could be calculated using the following
+ * NFP sequence:
+ *
+ * alu[--, dst, -, imm]
+ * immed[imm, 0]
+ * alu[dst, imm, +carry, 0]
+ *
+ */
+ if (imm > 1U << 31) {
+ swreg tmp_b = ur_load_imm_any(nfp_prog, imm, imm_b(nfp_prog));
+
+ emit_alu(nfp_prog, reg_none(), dst_a, ALU_OP_SUB, tmp_b);
+ wrp_immed(nfp_prog, imm_a(nfp_prog), 0);
+ emit_alu(nfp_prog, dst_both, imm_a(nfp_prog), ALU_OP_ADD_C,
+ reg_imm(0));
+ return 0;
+ }
+
+ rvalue = reciprocal_value_adv(imm, 32);
+ exp = rvalue.exp;
+ if (rvalue.is_wide_m && !(imm & 1)) {
+ pre_shift = fls(imm & -imm) - 1;
+ rvalue = reciprocal_value_adv(imm >> pre_shift, 32 - pre_shift);
+ } else {
+ pre_shift = 0;
+ }
magic = ur_load_imm_any(nfp_prog, rvalue.m, imm_b(nfp_prog));
- wrp_mul_u32(nfp_prog, imm_both(nfp_prog), reg_none(), dst_a, magic,
- true);
- emit_alu(nfp_prog, dst_both, dst_a, ALU_OP_SUB, tmp_b);
- emit_shf(nfp_prog, dst_both, reg_none(), SHF_OP_NONE, dst_b,
- SHF_SC_R_SHF, rvalue.sh1);
- emit_alu(nfp_prog, dst_both, dst_a, ALU_OP_ADD, tmp_b);
- emit_shf(nfp_prog, dst_both, reg_none(), SHF_OP_NONE, dst_b,
- SHF_SC_R_SHF, rvalue.sh2);
+ if (imm == 1U << exp) {
+ emit_shf(nfp_prog, dst_both, reg_none(), SHF_OP_NONE, dst_b,
+ SHF_SC_R_SHF, exp);
+ } else if (rvalue.is_wide_m) {
+ wrp_mul_u32(nfp_prog, imm_both(nfp_prog), reg_none(), dst_a,
+ magic, true);
+ emit_alu(nfp_prog, dst_both, dst_a, ALU_OP_SUB,
+ imm_b(nfp_prog));
+ emit_shf(nfp_prog, dst_both, reg_none(), SHF_OP_NONE, dst_b,
+ SHF_SC_R_SHF, 1);
+ emit_alu(nfp_prog, dst_both, dst_a, ALU_OP_ADD,
+ imm_b(nfp_prog));
+ emit_shf(nfp_prog, dst_both, reg_none(), SHF_OP_NONE, dst_b,
+ SHF_SC_R_SHF, rvalue.sh - 1);
+ } else {
+ if (pre_shift)
+ emit_shf(nfp_prog, dst_both, reg_none(), SHF_OP_NONE,
+ dst_b, SHF_SC_R_SHF, pre_shift);
+ wrp_mul_u32(nfp_prog, dst_both, reg_none(), dst_a, magic, true);
+ emit_shf(nfp_prog, dst_both, reg_none(), SHF_OP_NONE,
+ dst_b, SHF_SC_R_SHF, rvalue.sh);
+ }
return 0;
}
--
2.17.1
next prev parent reply other threads:[~2018-07-06 22:14 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-07-06 22:13 [PATCH bpf-next v2 0/6] nfp: bpf: add multiplication and divide support on NFP JIT Jakub Kicinski
2018-07-06 22:13 ` [PATCH bpf-next v2 1/6] lib: reciprocal_div: implement the improved algorithm on the paper mentioned Jakub Kicinski
2018-07-06 22:13 ` [PATCH bpf-next v2 2/6] nfp: bpf: rename umin/umax to umin_src/umax_src Jakub Kicinski
2018-07-06 22:13 ` [PATCH bpf-next v2 3/6] nfp: bpf: copy range info for all operands of all ALU operations Jakub Kicinski
2018-07-06 22:13 ` [PATCH bpf-next v2 4/6] nfp: bpf: support u16 and u32 multiplications Jakub Kicinski
2018-07-06 22:13 ` [PATCH bpf-next v2 5/6] nfp: bpf: support u32 divide using reciprocal_div.h Jakub Kicinski
2018-07-06 22:13 ` Jakub Kicinski [this message]
2018-07-06 23:49 ` [PATCH bpf-next v2 0/6] nfp: bpf: add multiplication and divide support on NFP JIT Daniel Borkmann
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20180706221323.31688-7-jakub.kicinski@netronome.com \
--to=jakub.kicinski@netronome.com \
--cc=alexei.starovoitov@gmail.com \
--cc=daniel@iogearbox.net \
--cc=jiong.wang@netronome.com \
--cc=netdev@vger.kernel.org \
--cc=oss-drivers@netronome.com \
--cc=songliubraving@fb.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox