[PATCH] bpf: Handle constants in TARGET_RTX_COSTS

[Jose E. Marchesi]

Hi Vineet.
Thanks for the patch.

> Current TARGET_RTX_COSTS is just a stub to keep the build happy and bpf
> ends up getting the "default cost model" which tends to reuse registers
> as much as possible.
>
> A common theme is when a function is returning a constant. If a prio reg
> is known to have that same constant value by control flow analysis, gcc
> tends to use that reg for returning vs. using the constant return.
>
> While there's nothing wrong with this, it sometimes leads to additional
> sign-extensions and other corner cases which trip up the bpf kernel verifier
> bounds checking for return reg. The verifier improvements are being worked
> on but lets adjust the cost model anyways so that constants are favored
> and anyhow this seems like valid change anyways.
>
> For accompanying test const-cost-model.c, at -O2
>
>                Before            |     After
>  --------------------------------+------------------------------
>     r1 = 4                       |  r1 = 4
>     call bpf_copy_from_user_str  |  call bpf_copy_from_user_str
>     r1 = (s32) r0                |  ...
>     ...                          |  r1 = 4
>     call bpf_copy_from_user_str  |  call bpf_copy_from_user_str
>
> The core change is reporting cost as 0 for CONST_INT.
>
> However reporting all constants unconditionally free skews synth_mult()
> and expand_divmod(): a multiply/divide by a constant gets implemented as a
> sequence of shifts/adds (or a magic-number multiply) instead of BPF's
> native single-instruction mul/div. So the constant cost now depends on the
> outer code and not free inside mul/div/mod.
>
> Additionally mul/div/mod are costed as a single instruction so the native
> op is preferred. Where the operation has no insn (e.g. a 64-bit signed divide
> before -mcpu=v4) expand_divmod() still falls back to a libcall.
>
> This causes 3 additioanl bpf kernel selftests to pass (as of v7.2)
>
> | -Summary: 596/5387 PASSED, 123 SKIPPED, 114 FAILED
> | +Summary: 599/5421 PASSED, 123 SKIPPED, 111 FAILED
> |  #77      cgroup_xattr:OK
> |  #112     exe_ctx:OK
> |  #220     mem_rdonly_untrusted:OK
>
> gcc/ChangeLog:
>
> 	* config/bpf/bpf.cc (bpf_rtx_costs): Handle CONST_INT based on the
> 	outer code, and cost MULT/DIV/UDIV/MOD/UMOD as a single instruction
> 	so the native operation is preferred over a synthesized shift/add or
> 	magic-multiply sequence.
>
> gcc/testsuite/ChangeLog:
>
> 	* gcc.target/bpf/const-cost-model.c: New test prefers const.
> 	* gcc.target/bpf/const-cost-model-2.c: New test prefers const.
> 	* gcc.target/bpf/divmod-libcall-2.c: Use actual signed 'long'
> 	dividend vs. prior unsigned int forced cast as long than be
> 	provably non-negative 	and the new cost model could emit the native
> 	usigned	divide eliding the libcall potentially failing the test.
>
> Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
> ---
>  gcc/config/bpf/bpf.cc                         | 57 +++++++++++++++++--
>  .../gcc.target/bpf/const-cost-model-2.c       | 36 ++++++++++++
>  .../gcc.target/bpf/const-cost-model.c         | 42 ++++++++++++++
>  .../gcc.target/bpf/divmod-libcall-2.c         | 19 +++++--
>  4 files changed, 144 insertions(+), 10 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.target/bpf/const-cost-model-2.c
>  create mode 100644 gcc/testsuite/gcc.target/bpf/const-cost-model.c
>
> diff --git a/gcc/config/bpf/bpf.cc b/gcc/config/bpf/bpf.cc
> index 89a4917cd0a0..c267323d7ca0 100644
> --- a/gcc/config/bpf/bpf.cc
> +++ b/gcc/config/bpf/bpf.cc
> @@ -602,14 +602,63 @@ bpf_legitimate_address_p (machine_mode mode,
>     `rtx_cost' should recurse.  */
>  
>  static bool
> -bpf_rtx_costs (rtx x ATTRIBUTE_UNUSED,
> +bpf_rtx_costs (rtx x,
>  	       enum machine_mode mode ATTRIBUTE_UNUSED,
> -	       int outer_code ATTRIBUTE_UNUSED,
> +	       int outer_code,
>  	       int opno ATTRIBUTE_UNUSED,
> -               int *total ATTRIBUTE_UNUSED,
> +	       int *total,
>  	       bool speed ATTRIBUTE_UNUSED)
>  {
> -  /* To be written.  */
> +  switch (GET_CODE (x))
> +    {
> +    case CONST_INT:
> +      {
> +	HOST_WIDE_INT val = INTVAL (x);
> +	/* BPF ALU instructions take a signed 32-bit immediate operand.  */
> +	bool imm32 = (val == (HOST_WIDE_INT) (int32_t) val);

I would prefer if you would define a BPF_IMM32 macro in bpf.h and then
use it as well in the imm32_operand predicate in predicates.md.

> +
> +	switch (outer_code)
> +	  {
> +	  /* Do not report a free constant when it is the operand of a
> +	     multiply, divide or modulo.  A zero-cost constant misleads
> +	     synth_mult () and expand_divmod () into implementing the
> +	     operation as a sequence of shifts/adds (or a magic-number
> +	     multiply) instead of BPF's native single-instruction mul/div,
> +	     which is cheaper here.  */
> +	  case MULT:
> +	  case DIV:
> +	  case UDIV:
> +	  case MOD:
> +	  case UMOD:
> +	    *total = COSTS_N_INSNS (1);
> +	    break;

I am confused.  If I am reading rtlanal.cc:rtx_cost properly, the value
stored here in *total will be added to the operation's cost, which is
now 1.  This means the total cost calculated for mult,div,etc rtx that
operate on imm32 operands will be > 1, which would be bigger than the 1
they would get when they operate on registers (register rtx get cost 0
by default in rtx_cost).  Is that what you want?

> +
> +	  default:
> +	    /* An immediate operand is free; a wider constant needs an
> +	       extra LD_IMM64.  */
> +	    *total = imm32 ? 0 : COSTS_N_INSNS (1);

Ok this makes instructions with imm32 operands as fast as costly as
instructions operating on source register.

> +	  }
> +
> +	return true;
> +      }
> +
> +    case MULT:
> +    case DIV:
> +    case UDIV:
> +    case MOD:
> +    case UMOD:
> +      /* BPF implements these as a single instruction, so keep the native
> +	 operation cheaper than any synthesized shift/add or magic-multiply
> +	 sequence.  This only influences the choice between available
> +	 alternatives; where the operation has no insn (e.g. a 64-bit signed
> +	 divide before -mcpu=v4) expand_divmod () still falls back to a
> +	 libcall.  Return false so the operand costs are still added.  */
> +      *total = COSTS_N_INSNS (1);
> +      return false;
> +
> +    default:
> +      return false;
> +    }
>    return false;
>  }
>  
> diff --git a/gcc/testsuite/gcc.target/bpf/const-cost-model-2.c b/gcc/testsuite/gcc.target/bpf/const-cost-model-2.c
> new file mode 100644
> index 000000000000..ab37de27b566
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/bpf/const-cost-model-2.c
> @@ -0,0 +1,36 @@
> +/* Verift that function return values are const 0 and 1 and not reg.
> +   Extracted from BPF selftest sockopt_multi.c  */
> +
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -mcpu=v4" } */
> +
> +struct bpf_sockopt {
> +   int level, optname, optlen, retval;
> +   void *optval_end, *optval;
> +};
> +
> +typedef unsigned char u8;
> +
> +int getsockopt_child(struct bpf_sockopt *ctx)
> +{
> + u8 *optval_end = ctx->optval_end;
> + u8 *optval = ctx->optval;
> +
> +//  if (ctx->optname != 1)
> +//    goto out;
> + 
> + if (ctx->level != 0 || ctx->optname != 1)
> +  goto out;
> +
> + if (optval[0] != 0x80)
> +  return 0;
> +
> + ctx->retval = 0;
> + return 1;
> +
> +out:
> + return 1;
> +}
> +
> +/* { dg-final { scan-assembler-not   {\*\(u32 \*\) \(r.\+12\) = r.} } } */
> +/* { dg-final { scan-assembler-times {\*\(u32 \*\) \(r.\+12\) = 0} 1 } } */
> diff --git a/gcc/testsuite/gcc.target/bpf/const-cost-model.c b/gcc/testsuite/gcc.target/bpf/const-cost-model.c
> new file mode 100644
> index 000000000000..8cf2fb584922
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/bpf/const-cost-model.c
> @@ -0,0 +1,42 @@
> +/* Verify that arg const 4 to 2nd call is const and not reg r0 which is
> +   ret value of first call.
> +   Extracted from BPF selftest attach_probe.c  */
> +
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -mcpu=v4" } */
> +
> +extern int bpf_copy_from_user_str(int dst__sz);
> +
> +_Bool verify_sleepable_user_copy_str(void)
> +{
> + int ret;
> + char data_short_pad[4];
> +
> + ret = bpf_copy_from_user_str(sizeof(data_short_pad));
> +
> + if (ret != 4)
> +  return false;
> +
> + ret = bpf_copy_from_user_str(sizeof(data_short_pad));
> +
> + if (ret != 4)
> +  return false;
> +
> +  return true;
> +}
> +
> +/* Original generated code
> +	r1 = 4
> +	call	bpf_copy_from_user_str
> +	r1 = (s32) r0
> +    ...
> +	call	bpf_copy_from_user_str
> +
> +   Now generated
> +	r1 = 4
> +	call	bpf_copy_from_user_str
> +    ...
> +	r1 = 4
> +	call	bpf_copy_from_user_str  */
> +
> +/* { dg-final { scan-assembler-times {r1 = 4} 2 } } */
> diff --git a/gcc/testsuite/gcc.target/bpf/divmod-libcall-2.c b/gcc/testsuite/gcc.target/bpf/divmod-libcall-2.c
> index 792d689395a2..c93c084344f1 100644
> --- a/gcc/testsuite/gcc.target/bpf/divmod-libcall-2.c
> +++ b/gcc/testsuite/gcc.target/bpf/divmod-libcall-2.c
> @@ -1,16 +1,23 @@
> +/* Counterpart to divmod-libcall-1.c, exercising the path where the
> +   __divdi3/__moddi3 libcall is actually used (so the .global decl is
> +   emitted).  The dividend 'x' is a plain signed 'long' and can be negative,
> +   so this is a real signed 64-bit divide: before -mcpu=v4 there is no signed
> +   divide insn and no magic-multiply sequence (BPF has no highpart multiply),
> +   so the libcall is the only option.  */
> +
>  /* { dg-do compile } */
>  /* { dg-options "-O2 -mcpu=v3" } */
>  /* { dg-final { scan-assembler "global\t__divdi3" } } */
>  /* { dg-final { scan-assembler "global\t__moddi3" } } */
>  
> -int
> -foo (unsigned int len)
> +long
> +foo (long x)
>  {
> -  return ((long)len) * 234 / 5;
> +  return x * 234 / 5;
>  }
>  
> -int
> -bar (unsigned int len)
> +long
> +bar (long x)
>  {
> -  return ((long)len) * 234 % 5;
> +  return x * 234 % 5;
>  }