[Bug tree-optimization/37242] New: missed load PRE-like opportunity

[Bug tree-optimization/37242] New: missed load PRE-like opportunity

[bonzini at gnu dot org]

In the attached code, the if-conversion opportunity in PR37240 does not benefit
a Pentium 4.  However, there is another optimization possible on both systems,
namely changing

    while ((maxIdx += maxIdx) < last) {
        if (numbers[maxIdx] < numbers[maxIdx + 1]) maxIdx++;
        if (tmp >= numbers[maxIdx]) break;
        numbers[top] = numbers[maxIdx];
        top = maxIdx;
    }

to

    while ((maxIdx += maxIdx) < last) {
        int a = numbers[maxIdx], b = numbers[maxIdx + 1];
        if (a < b) maxIdx++, a = b;
        if (tmp >= a) break;
        numbers[top] = a;
        top = maxIdx;
    }

It seems to me that numbers[maxIdx] is partially redundant (it is available if
maxIdx++ is not executed).  If an additional load of numbers[maxIdx + 1] is
inserted in the "then" branch, it can also be found to be fully redundant so
that copy propagation generates the optimized code.

This gives a ~3% performance increase on i686-pc-linux-gnu for this benchmark.


-- 
           Summary: missed load PRE-like opportunity
           Product: gcc
           Version: 4.3.2
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: bonzini at gnu dot org
GCC target triplet: i686-pc-linux-gnu
 BugsThisDependsOn: 37239


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed load PRE-like opportunity

[bonzini at gnu dot org]

------- Comment #1 from bonzini at gnu dot org  2008-08-26 11:55 -------
Created an attachment (id=16150)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16150&action=view)
benchmark

same as the attachment to 37240


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity

[bonzini at gnu dot org]

------- Comment #2 from bonzini at gnu dot org  2008-08-26 12:02 -------
This is missed because this:

  maxIdx.1_15 = (unsigned int) maxIdx_59;
  D.1923_20 = maxIdx.1_15 + 1;
  D.1924_21 = D.1923_20 * 4;
  D.1925_22 = numbers_9(D) + D.1924_21;

and this:

  maxIdx_24 = maxIdx_59 + 1;
  pretmp.36_86 = (unsigned int) maxIdx_24;
  pretmp.36_88 = pretmp.36_86 * 4;
  pretmp.38_90 = numbers_9(D) + pretmp.36_88;

do not match.  The first has the arithmetic done as unsigned, the second as
signed.  This could be due to array indexing lowered to POINTER_PLUS_EXPR.


-- 

bonzini at gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org, pinskia at gcc dot gnu
                   |                            |dot org
            Summary|missed load PRE-like        |missed FRE opportunity
                   |opportunity                 |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[pinskia at gcc dot gnu dot org]

------- Comment #3 from pinskia at gcc dot gnu dot org  2008-08-26 21:16 -------
>This could be due to array indexing lowered to POINTER_PLUS_EXPR.

Array indexing is never lowered using POINTER_PLUS_EXPR, only for pointers it
is.  Though it looks like
we are doing the math in unsigned in one case but signed in another but we
don't consider them the same for PRE.

Simple testcase:
int f(int a)
{
  unsigned b = a;
  b++;
  a++;
  return a + b;
}
We should just get return a*2 + 2; (which we do at the RTL level) but we get:
  b = (unsigned int) a;
  return (int) ((b + 1) + (unsigned int) (a + 1));


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2008-08-26 21:16:06
               date|                            |
            Summary|missed FRE opportunity      |missed FRE opportunity
                   |                            |because of signedness of
                   |                            |addition


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[bonzini at gnu dot org]

------- Comment #4 from bonzini at gnu dot org  2008-08-27 06:41 -------
Minimized testcase:

int m(int *y, int x)
{
  int a = y[x + 1];
  int b = y[++x];
  return a - b;
}

should be optimized to "return 0"


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[bonzini at gnu dot org]

------- Comment #5 from bonzini at gnu dot org  2008-08-27 07:14 -------
With this patch:

Index: fold-const.c
===================================================================
--- fold-const.c        (revision 139423)
+++ fold-const.c        (working copy)
@@ -7868,7 +7868,11 @@ fold_unary (enum tree_code code, tree ty
         very likely don't have maximal range for their precision and this
         transformation effectively doesn't preserve non-maximal ranges.  */
       if (TREE_CODE (type) == INTEGER_TYPE
-         && TREE_CODE (op0) == BIT_AND_EXPR
+         && (TREE_CODE (op0) == BIT_AND_EXPR
+             || TREE_CODE (op0) == BIT_IOR_EXPR
+             || TREE_CODE (op0) == BIT_XOR_EXPR
+             || TREE_CODE (op0) == PLUS_EXPR
+             || TREE_CODE (op0) == MINUS_EXPR)
          && TREE_CODE (TREE_OPERAND (op0, 1)) == INTEGER_CST)
        {
          tree and = op0;
@@ -7906,7 +7910,7 @@ fold_unary (enum tree_code code, tree ty
              tem = force_fit_type_double (type, TREE_INT_CST_LOW (and1),
                                           TREE_INT_CST_HIGH (and1), 0,
                                           TREE_OVERFLOW (and1));
-             return fold_build2 (BIT_AND_EXPR, type,
+             return fold_build2 (TREE_CODE (op0), type,
                                  fold_convert (type, and0), tem);
            }
        }

I can fold "(unsigned) (x + 1)" to "(unsigned) x + 1". The problem is that TER
does not fold the trees it creates.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[bonzini at gnu dot org]

------- Comment #6 from bonzini at gnu dot org  2008-08-27 07:15 -------
s/TER does not fold/SCCVN does not accept/


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[rguenther at suse dot de]

------- Comment #7 from rguenther at suse dot de  2008-08-27 09:40 -------
Subject: Re:  missed FRE opportunity because of
 signedness of addition

On Wed, 27 Aug 2008, bonzini at gnu dot org wrote:

> 
> 
> ------- Comment #4 from bonzini at gnu dot org  2008-08-27 06:41 -------
> Minimized testcase:
> 
> int m(int *y, int x)
> {
>   int a = y[x + 1];
>   int b = y[++x];
>   return a - b;
> }
> 
> should be optimized to "return 0"

Because fold folds (unsigned)(x + 1) to (unsigned)x + 1 but doesn't
touch (unsigned) ++x which gets gimplified to a signed addition.

Richard.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[bonzini at gnu dot org]

------- Comment #8 from bonzini at gnu dot org  2008-08-27 17:50 -------
Subject: Re:  missed FRE opportunity because
 of signedness of addition

Maybe we can lookup the non-GIMPLE operands in simplify_unary_expression
and replace them with existing SSA_NAMES if they have been value numbered.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[rguenther at suse dot de]

------- Comment #9 from rguenther at suse dot de  2008-08-27 19:12 -------
Subject: Re:  missed FRE opportunity because of
 signedness of addition

On Wed, 27 Aug 2008, bonzini at gnu dot org wrote:

> ------- Comment #8 from bonzini at gnu dot org  2008-08-27 17:50 -------
> Subject: Re:  missed FRE opportunity because
>  of signedness of addition
> 
> Maybe we can lookup the non-GIMPLE operands in simplify_unary_expression
> and replace them with existing SSA_NAMES if they have been value numbered.

So when we see

pretmp.36_86 = (unsigned int) maxIdx_24;

we do not even simplify it to (unsigned int)maxIdx_59 + 1.

So much for the fold theory...  instead we come from

#9  0x080b75dd in pointer_int_sum (resultcode=PLUS_EXPR, ptrop=0xb7c9d57c, 
    intop=0xb7ca37a0) at /home/richard/src/trunk/gcc/c-common.c:3361
3361      ret = fold_build2 (POINTER_PLUS_EXPR, result_type, ptrop, 
intop);
(gdb) call debug_generic_expr (ptrop)
y + 4
(gdb) call debug_generic_expr (intop)
(unsigned int) ((unsigned int) x * 4)

go through y p+ (4 + (unsigned int) ((unsigned int) x * 4)) which we
fold by fold_plusminus_mult_expr to ((unsigned int) x + 1) * 4.

I saw your patch that adds this folding.  And indeed we should
be able to lookup (unsigned int) x + 1 in two steps.

I may look into this at some point.

Richard.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[bonzini at gnu dot org]

------- Comment #10 from bonzini at gnu dot org  2008-08-27 19:53 -------
Yet another piece of the puzzle:
Index: tree-ssa-sccvn.c
===================================================================
--- tree-ssa-sccvn.c    (revision 139423)
+++ tree-ssa-sccvn.c    (working copy)
@@ -2052,6 +2052,40 @@ valueize_expr (tree expr)
   return expr;
 }

+static tree
+make_expression_gimple (tree t)
+{
+  enum gimple_rhs_class grc = get_gimple_rhs_class (TREE_CODE (t));
+  tree op0 = NULL, op1 = NULL;
+
+  switch (grc)
+    {
+    case GIMPLE_UNARY_RHS:
+      op0 = TREE_OPERAND (t, 0);
+      if (!is_gimple_val (op0))
+        op0 = vn_nary_op_lookup (op0, NULL);
+      if (op0)
+        return build1 (TREE_CODE (t), TREE_TYPE (t), op0);
+      break;
+
+    case GIMPLE_BINARY_RHS:
+      op0 = TREE_OPERAND (t, 0);
+      op1 = TREE_OPERAND (t, 1);
+      if (!is_gimple_val (op0))
+        op0 = vn_nary_op_lookup (op0, NULL);
+      if (!is_gimple_val (op1))
+        op1 = vn_nary_op_lookup (op1, NULL);
+      if (op0 && op1)
+        return build2 (TREE_CODE (t), TREE_TYPE (t), op0, op1);
+      break;
+
+    default:
+      break;
+    }
+
+  return NULL;
+}
+
 /* Simplify the binary expression RHS, and return the result if
    simplified. */

@@ -2100,10 +2134,14 @@ simplify_binary_expression (gimple stmt)
      of operators of operators (IE (a + b) + (a + c))
      Otherwise, we will end up with unbounded expressions if
      fold does anything at all.  */
-  if (result && valid_gimple_rhs_p (result))
-    return result;
+  if (result)
+    {
+      STRIP_USELESS_TYPE_CONVERSION (result);
+      if (!valid_gimple_rhs_p (result))
+        result = make_expression_gimple (result);
+    }

-  return NULL_TREE;
+  return result;
 }

 /* Simplify the unary expression RHS, and return the result if
@@ -2153,11 +2191,11 @@ simplify_unary_expression (gimple stmt)
   if (result)
     {
       STRIP_USELESS_TYPE_CONVERSION (result);
-      if (valid_gimple_rhs_p (result))
-        return result;
+      if (!valid_gimple_rhs_p (result))
+        result = make_expression_gimple (result);
     }

-  return NULL_TREE;
+  return result;
 }

 /* Try to simplify RHS using equivalences and constant folding.  */

However it still does not work because the two "unsigned" types do not match.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[rguenther at suse dot de]

------- Comment #11 from rguenther at suse dot de  2008-08-27 20:17 -------
Subject: Re:  missed FRE opportunity because of
 signedness of addition

On Wed, 27 Aug 2008, bonzini at gnu dot org wrote:

> Yet another piece of the puzzle:
> Index: tree-ssa-sccvn.c
> ===================================================================
> --- tree-ssa-sccvn.c    (revision 139423)
> +++ tree-ssa-sccvn.c    (working copy)
> @@ -2052,6 +2052,40 @@ valueize_expr (tree expr)
>    return expr;
>  }
> 
> +static tree
> +make_expression_gimple (tree t)
> +{
> +  enum gimple_rhs_class grc = get_gimple_rhs_class (TREE_CODE (t));
> +  tree op0 = NULL, op1 = NULL;
> +
> +  switch (grc)
> +    {
> +    case GIMPLE_UNARY_RHS:
> +      op0 = TREE_OPERAND (t, 0);
> +      if (!is_gimple_val (op0))
> +        op0 = vn_nary_op_lookup (op0, NULL);
> +      if (op0)
> +        return build1 (TREE_CODE (t), TREE_TYPE (t), op0);

A good idea to lookup this final expression before building it.

> +      break;
> +
> +    case GIMPLE_BINARY_RHS:
> +      op0 = TREE_OPERAND (t, 0);
> +      op1 = TREE_OPERAND (t, 1);
> +      if (!is_gimple_val (op0))
> +        op0 = vn_nary_op_lookup (op0, NULL);
> +      if (!is_gimple_val (op1))
> +        op1 = vn_nary_op_lookup (op1, NULL);
> +      if (op0 && op1)
> +        return build2 (TREE_CODE (t), TREE_TYPE (t), op0, op1);

Likewise.

> +      break;
> +
> +    default:
> +      break;
> +    }
> +
> +  return NULL;
> +}
> +
>  /* Simplify the binary expression RHS, and return the result if
>     simplified. */
> 
> @@ -2100,10 +2134,14 @@ simplify_binary_expression (gimple stmt)
>       of operators of operators (IE (a + b) + (a + c))
>       Otherwise, we will end up with unbounded expressions if
>       fold does anything at all.  */
> -  if (result && valid_gimple_rhs_p (result))
> -    return result;
> +  if (result)
> +    {
> +      STRIP_USELESS_TYPE_CONVERSION (result);
> +      if (!valid_gimple_rhs_p (result))
> +        result = make_expression_gimple (result);
> +    }
> 
> -  return NULL_TREE;
> +  return result;
>  }
> 
>  /* Simplify the unary expression RHS, and return the result if
> @@ -2153,11 +2191,11 @@ simplify_unary_expression (gimple stmt)
>    if (result)
>      {
>        STRIP_USELESS_TYPE_CONVERSION (result);
> -      if (valid_gimple_rhs_p (result))
> -        return result;
> +      if (!valid_gimple_rhs_p (result))
> +        result = make_expression_gimple (result);
>      }
> 
> -  return NULL_TREE;
> +  return result;
>  }
> 
>  /* Try to simplify RHS using equivalences and constant folding.  */
> 
> However it still does not work because the two "unsigned" types do not match.

What do they look like?

Richard.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[bonzini at gnu dot org]

------- Comment #12 from bonzini at gnu dot org  2008-08-28 06:09 -------
I have a patch for the minimal testcase, but not for the full PRE testcase.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[bonzini at gnu dot org]

------- Comment #13 from bonzini at gnu dot org  2008-08-28 06:16 -------
Answering to your comment #11, one is a sizetype and one is not.  But it is
enough to extend my fold-const.c patch to MULT_EXPRs in order to catch it.

Also, the problem with the full testcase is that PRE is not cascading "enough".
 Adding another PRE pass right after the first catches it.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[rguenther at suse dot de]

------- Comment #14 from rguenther at suse dot de  2008-08-28 08:02 -------
Subject: Re:  missed FRE opportunity because of
 signedness of addition

On Thu, 28 Aug 2008, bonzini at gnu dot org wrote:

> ------- Comment #13 from bonzini at gnu dot org  2008-08-28 06:16 -------
> Answering to your comment #11, one is a sizetype and one is not.  But it is
> enough to extend my fold-const.c patch to MULT_EXPRs in order to catch it.
> 
> Also, the problem with the full testcase is that PRE is not cascading "enough".
>  Adding another PRE pass right after the first catches it.

That would be a bug unless its a very weird case.  PRE iterates
insertion for this case for example.

Richard.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[bonzini at gnu dot org]

------- Comment #15 from bonzini at gnu dot org  2008-08-28 08:42 -------
I think that PRE does not try to simplify expressions that it inserts.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[rguenther at suse dot de]

------- Comment #16 from rguenther at suse dot de  2008-08-28 08:45 -------
Subject: Re:  missed FRE opportunity because of
 signedness of addition

On Thu, 28 Aug 2008, bonzini at gnu dot org wrote:

> ------- Comment #15 from bonzini at gnu dot org  2008-08-28 08:42 -------
> I think that PRE does not try to simplify expressions that it inserts.

Correct.  PRE does minimal expression simplification during PHI 
translation, but that's it.  Note that gimple expressions itself
never simplify apart from constant folding, the simplify_*_expression
routines in SCCVN instead combine multiple expressions.

Is the optimization the second PRE run does a full redundancy removal
or a new partial redundancy?

Richard.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[bonzini at gnu dot org]

------- Comment #17 from bonzini at gnu dot org  2008-08-28 08:56 -------
full redundancy.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[bonzini at gnu dot org]

------- Comment #18 from bonzini at gnu dot org  2008-08-28 08:57 -------
Just let me finish fixing a "side bug" that is exposed by my patch, then I'll
post a RFC.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[matt at use dot net]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

Matt Hargett <matt at use dot net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |matt at use dot net

--- Comment #19 from Matt Hargett <matt at use dot net> 2011-04-27 17:57:34 UTC ---
This appears to be fixed in 4.6.0. Mark as resolved?

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

--- Comment #20 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-04-28 09:51:13 UTC ---
The testcases in comment #3 and #4 do not seem to be fixed with 4.6.0.

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

--- Comment #21 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-04-18 22:50:42 UTC ---
I have a patch.

[Bug tree-optimization/37242] missed FRE opportunity because of signedness of addition

[matt at use dot net]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37242

--- Comment #22 from Matt Hargett <matt at use dot net> 2012-06-29 00:20:17 UTC ---
Hey Andrew, any word on your patch?