Re: Revision 107218 changed addressing mode generation

[Richard Guenther <richard dot guenther at gmail dot com>]

On Thu, Mar 26, 2009 at 1:39 AM, Bernd Schmidt <bernds_cb1@t-online.de> wrote:
> Revision 107218, which introduced fold_plusminus_mult_expr, changed the way
> we are folding certain constants.
>
> Breakpoint 7, fold_plusminus_mult_expr (code=PLUS_EXPR, type=0xb7b0c000,
> arg0=0xb6b8ebd0, arg1=0xb6b8c7a8)
> 7389 ? ?{
> (gdb) p arg0
> $48 = (tree) 0xb6b8ebd0
> (gdb) pt
> ?<mult_expr 0xb6b8ebd0
> ? ?type <integer_type 0xb7b0c000 long unsigned int public unsigned sizetype
> SI
> ? ? ? ?size <integer_cst 0xb7afc444 constant invariant 32>
> ? ? ? ?unit size <integer_cst 0xb7afc230 constant invariant 4>
> ? ? ? ?align 32 symtab 0 alias set -1 canonical type 0xb7b16270 precision 32
> min <integer_cst 0xb7afc4d0 0> max <integer_cst 0xb7afc9bc -1>>
>
> ? ?arg 0 <bit_and_expr 0xb6b8ebac type <integer_type 0xb7b0c000 long
> unsigned int>
>
> ? ? ? ?arg 0 <nop_expr 0xb69845c0 type <integer_type 0xb7b0c000 long
> unsigned int>
> ? ? ? ? ? ?arg 0 <var_decl 0xb6b8d9f8 work.384>>
> ? ? ? ?arg 1 <integer_cst 0xb723f40c constant invariant 63>> arg 1
> <integer_cst 0xb7afc230 4>>
> (gdb) p arg1
> $49 = (tree) 0xb6b8c7a8
> (gdb) pt
> ?<integer_cst 0xb6b8c7a8 type <integer_type 0xb7b0c000 long unsigned int>
> constant invariant 1792>
>
> Instead of generating a PLUS around the MULT, this falls into the last arm
> of the if statement (with the maybe_same code) and produces a MULT of a
> PLUS. ?This behaviour is different from what fold-const did in 4.1. ?In some
> cases, the new code causes less efficient addressing modes to be generated
> on the Blackfin.
>
> I can make the problem go away with the patch below. ?Richard, is that maybe
> what you originally intended here?

I think it would make sense to only apply the canonicalization if we
do not increase the number of multiplications.  Thus,

  i * 2 + 4  -> (i + 2) * 2       is ok, but
  i * 4 + 2  -> (i * 2 + 1) * 2  is not (we do this)
  i * 4 + j * 2  -> (i * 2 + j) * 2  is ok
  i * 4 + j * 6 -> (i * 2 + j * 3) * 2  is not (we do not do this)

I think this was the original intent (well, the original intent was do
commonize the various places we do this kind of folding into one
place and generalize it).

Can you try to work out a patch that only disables the
i * 4 + 2  -> (i * 2 + 1) * 2 folding and keeps the i * 2 + 4  -> (i + 2) * 2
one (and add a testcase checking for these cases?).

The idea behind these foldings is to re-instantiate induction variable
uses that come from a[i + 1] written as pointer arithmetic which in
turn should help induction variable analysis.

Thus, would the following work for you?

Index: gcc/fold-const.c
===================================================================
--- gcc/fold-const.c    (revision 145056)
+++ gcc/fold-const.c    (working copy)
@@ -7490,7 +7490,12 @@ fold_plusminus_mult_expr (enum tree_code
       else
        maybe_same = arg11;

-      if (exact_log2 (abs (int11)) > 0 && int01 % int11 == 0)
+      if (exact_log2 (abs (int11)) > 0
+         && int01 % int11 == 0
+         /* The remainder should not be a constant, otherwise we
+            end up folding i * 4 + 2 to (i * 2 + 1) * 2 which has
+            increased the number of multiplications necessary.  */
+         && TREE_CODE (arg10) != INTEGER_CST)
         {
          alt0 = fold_build2 (MULT_EXPR, TREE_TYPE (arg00), arg00,
                              build_int_cst (TREE_TYPE (arg00),

(I would be curious if lifting the exact_log2 () restriction would be
useful - at the moment we do not canonicalize i * 3 + j * 6 or
(i + j * 2) * 3 so we won't do CSE if both of these appear)

Thanks,
Richard.

>
> Bernd
> --
> This footer brought to you by insane German lawmakers.
> Analog Devices GmbH ? ? ?Wilhelm-Wagenfeld-Str. 6 ? ? ?80807 Muenchen
> Sitz der Gesellschaft Muenchen, Registergericht Muenchen HRB 40368
> Geschaeftsfuehrer Thomas Wessel, William A. Martin, Margaret Seif
>
> Index: gcc-4.3/gcc/fold-const.c
> ===================================================================
> --- gcc-4.3/gcc/fold-const.c ? ?(revision 3231)
> +++ gcc-4.3/gcc/fold-const.c ? ?(working copy)
> @@ -7445,9 +7445,11 @@ fold_plusminus_mult_expr (enum tree_code
>
> ? /* No identical multiplicands; see if we can find a common
> ? ? ?power-of-two factor in non-power-of-two multiplies. ?This
> - ? ? can help in multi-dimensional array access. ?*/
> - ?else if (host_integerp (arg01, 0)
> - ? ? ? ? ?&& host_integerp (arg11, 0))
> + ? ? can help in multi-dimensional array access. ?Don't do this
> + ? ? if one of our arguments was a constant. ?*/
> + ?else if (host_integerp (arg01, 0) && host_integerp (arg11, 0)
> + ? ? ? ? ?&& TREE_CODE (arg0) != INTEGER_CST
> + ? ? ? ? ?&& TREE_CODE (arg1) != INTEGER_CST)
> ? ? {
> ? ? ? HOST_WIDE_INT int01, int11, tmp;
> ? ? ? bool swap = false;
>
>