[Bug tree-optimization/32120] missed PRE/FRE of a*2+4 and (a+2)*2

[Bug tree-optimization/32120] missed PRE/FRE of a*2+4 and (a+2)*2

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|rguenth at gcc dot gnu.org  |pinskia at gcc dot gnu.org

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-03-03 23:44:05 UTC ---
I am taking over since this is related to combine branch.

[Bug tree-optimization/32120] missed PRE/FRE of a*2+4 and (a+2)*2

[pinskia at gcc dot gnu.org]

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

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-03-04 00:45:50 UTC ---
I might even have a patch for my tree combine branch later today.  I still have
to connect up ssa_combine to SCCVN but that should not be hard.

[Bug tree-optimization/32120] missed PRE/FRE of a*2+4 and (a+2)*2

[dberlin at gcc dot gnu.org]

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

--- Comment #8 from Daniel Berlin <dberlin at gcc dot gnu.org> 2012-03-05 17:20:36 UTC ---
I still have an unfinished patch to convert SCCVN to
http://dl.acm.org/citation.cfm?id=512536

This actually makes it significantly easier to integrate better
congruence finding (and lets us use predicates properly during value
numbering).
It also was significantly faster in large functions (also functiojns
containing large SCC's) due to a significantly better iteration
strategy (it will only iterate values that are changing, while SCCVN
will iterate all values in an SCC).

I'm happy to attach the patch if you like :)


On Sat, Mar 3, 2012 at 7:45 PM, pinskia at gcc dot gnu.org
<gcc-bugzilla@gcc.gnu.org> wrote:
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32120
>
> --- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-03-04 00:45:50 UTC ---
> I might even have a patch for my tree combine branch later today.  I still have
> to connect up ssa_combine to SCCVN but that should not be hard.
>
> --
> Configure bugmail: http://gcc.gnu.org/bugzilla/userprefs.cgi?tab=email
> ------- You are receiving this mail because: -------
> You are on the CC list for the bug.

[Bug tree-optimization/32120] missed PRE/FRE of a*2+4 and (a+2)*2

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |matz at gcc dot gnu.org

--- Comment #9 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-03-05 17:32:52 UTC ---
(In reply to comment #8)
> I still have an unfinished patch to convert SCCVN to
> http://dl.acm.org/citation.cfm?id=512536
> 
> This actually makes it significantly easier to integrate better
> congruence finding (and lets us use predicates properly during value
> numbering).
> It also was significantly faster in large functions (also functiojns
> containing large SCC's) due to a significantly better iteration
> strategy (it will only iterate values that are changing, while SCCVN
> will iterate all values in an SCC).
> 
> I'm happy to attach the patch if you like :)

I think you sent it to me once and Micha has implemented the predication
bits ontop of it (well, sort of IIRC).

Richard.

[Bug tree-optimization/32120] missed PRE/FRE of a*2+4 and (a+2)*2

[matz at gcc dot gnu.org]

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

--- Comment #10 from Michael Matz <matz at gcc dot gnu.org> 2012-03-06 12:06:08 UTC ---
(In reply to comment #9)
> (In reply to comment #8)
> > I still have an unfinished patch to convert SCCVN to
> > http://dl.acm.org/citation.cfm?id=512536
> > 
> > I'm happy to attach the patch if you like :)
> 
> I think you sent it to me once and Micha has implemented the predication
> bits ontop of it (well, sort of IIRC).

Yep, and I'm supposed to finish it up finally until the GCC cauldron :)

[Bug tree-optimization/32120] missed PRE/FRE of a*2+4 and (a+2)*2

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |NEW
             Blocks|22586                       |
         Depends on|                            |22586

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-03-13 03:20:53 UTC ---
I am not working on this any more.  This really should be done correctly in
FRE/PRE when looking up SSA_NAME * 4, and SSA_NAME is defined by a PLUS_EXPR
with a constant, lookup the inner most SSA_NAME *4.  Which is what PR 22586 is
talking about.

I might work towards that but not with my tree combine branch.

[Bug tree-optimization/32120] missed PRE/FRE of a*2+4 and (a+2)*2

[wschmidt at gcc dot gnu.org]

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

William J. Schmidt <wschmidt at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |wschmidt at gcc dot gnu.org
         Resolution|                            |FIXED

--- Comment #12 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2012-06-27 21:47:49 UTC ---
Fixed by the new strength reduction pass.

[Bug tree-optimization/32120] New: missed PRE/FRE of a*2+4 and (a+2)*2

[pinskia at gcc dot gnu dot org]

A testcase which we should optimize all the way to return true:
int f(int a, int b)
{
  int c = a+2;
  int d = c*2;
  int e = a*2;
  int f = e+4;
  return d == f;
}


-- 
           Summary: missed PRE/FRE of a*2+4 and (a+2)*2
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: pinskia at gcc dot gnu dot org


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

[Bug tree-optimization/32120] missed PRE/FRE of a*2+4 and (a+2)*2

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2007-05-28 10:27 -------
Confirmed.  Maybe fixed by sccvn.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dberlin at gcc dot gnu dot
                   |                            |org, rguenth at gcc dot gnu
                   |                            |dot org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-05-28 10:27:18
               date|                            |


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

[Bug tree-optimization/32120] missed PRE/FRE of a*2+4 and (a+2)*2

[pinskia at gcc dot gnu dot org]

------- Comment #2 from pinskia at gcc dot gnu dot org  2007-06-10 02:23 -------
I have noticed this more and more on the pointer plus branch, why it shows up
there more I don't know.


-- 


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

[Bug tree-optimization/32120] missed PRE/FRE of a*2+4 and (a+2)*2

[dberlin at gcc dot gnu dot org]

------- Comment #3 from dberlin at gcc dot gnu dot org  2007-06-10 03:31 -------
It won't be fixed by sccvn, at least not initially.
SCCVN has very strict rules about what expressions it decides are worth trying
to keep around to simplify other expressions.

Right now, we only keep those for which fold_binary returns two non-recursive
expressions, to control expand into infinite sized trees.

Even if you change this to keep around those which produce constants for one
operand, fold_binary returns null when given (a_1 * 2) + 4

You could work around this by also keeping around those expressions whose
valuized expansion ends up being  different than the original expression.

The following rewritten simplify_binary_expression, based on what it is
tree-ssa-sccvn.c that is about to be committed will do it.

(We don't bother simplifying comparisons, leaving it to another pass, feel free
to add support. They just don't occur enough and const/copyprop will figure it
out when we replace the supporting values)

/* Simplify the binary expression RHS, and return the result if
   simplified. */

static tree
simplify_binary_expression (tree rhs)
{
  tree result = NULL_TREE;
  tree op0 = TREE_OPERAND (rhs, 0);
  tree op1 = TREE_OPERAND (rhs, 1);
  tree oldop0 = op0;
  tree oldop1 = op1;
  bool valueized0 = false;
  bool valueized1 = false;

  /* This will not catch every single case we could combine, but will
     catch those with constants.  The goal here is to simultaneously
     combine constants between expressions, but avoid infinite
     expansion of expressions during simplification.  */
  if (TREE_CODE (op0) == SSA_NAME)
    {
      if (VN_INFO (op0)->has_constants)
        {
          valueized0 = true;
          op0 = valueize_expr (VN_INFO (op0)->expr);
        }
      else if (SSA_VAL (op0) != VN_TOP && SSA_VAL (op0) != op0)
        op0 = VN_INFO (op0)->valnum;      
    }

  if (TREE_CODE (op1) == SSA_NAME)
    {
      if (VN_INFO (op1)->has_constants)
        {
          valueized1 = true;
          op1 = valueize_expr (VN_INFO (op1)->expr);
        }
      else if (SSA_VAL (op1) != VN_TOP && SSA_VAL (op1) != op1)
        op1 = VN_INFO (op1)->valnum;
    }
  result = fold_binary (TREE_CODE (rhs), TREE_TYPE (rhs), op0, op1);

  /* Make sure result is not a complex expression consiting
     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)
    {
      if (is_gimple_min_invariant (result))
        return result;
      else if (SSA_VAR_P (result))
        return result;
      else if (EXPR_P (result))
        {
          switch (TREE_CODE_CLASS (TREE_CODE (result)))
            {
            case tcc_unary:
              {
                tree op0 = TREE_OPERAND (result, 0);
                if (!EXPR_P (op0))
                  return result;
              }
              break;
            case tcc_binary:
              {
                tree op0 = TREE_OPERAND (result, 0);
                tree op1 = TREE_OPERAND (result, 1);
                if ((!EXPR_P (op0) && !EXPR_P (op1))
                    || (is_gimple_min_invariant (op0) 
                        || is_gimple_min_invariant (op1)))
                  return result;
              }
              break;
            default:
              break;
            }
        }
    }
  else if ((op0 != oldop0 && valueized0) || (op1 != oldop1 && valueized1))
    {
      /* Canonicalized to the valuized expression */
      return fold_build2 (TREE_CODE (rhs), TREE_TYPE (rhs), op0, op1);
    }

  return NULL_TREE;
}


-- 


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

[Bug tree-optimization/32120] missed PRE/FRE of a*2+4 and (a+2)*2

[pinskia at gcc dot gnu dot org]

------- Comment #4 from pinskia at gcc dot gnu dot org  2007-06-29 03:05 -------
Note we should also optimize:
int f(int a, int b)
{
  int c = a+4;
  int d = c*2;
  int e = a*2;
  int f = e+4;
  return f+d;
}

into "a*2 + 12;" (or "(a+6)*2" ) so that only one mutliplication is there.


-- 


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

[Bug tree-optimization/32120] missed PRE/FRE of a*2+4 and (a+2)*2

[rguenth at gcc dot gnu dot org]

------- Comment #5 from rguenth at gcc dot gnu dot org  2008-04-29 09:55 -------
For the testcase in comment #4 after FRE we have

  c_2 = a_1(D) + 4;
  d_3 = c_2 * 2;
  e_4 = a_1(D) * 2;
  f_5 = e_4 + 4;
  D.1557_6 = f_5 + d_3;
  return D.1557_6;

And a patched reassoc pass then produces

  c_2 = a_1(D) + a_1(D);
  D.1565_8 = c_2 + 4;
  D.1565_9 = D.1565_8 * 2;
  D.1557_6 = 4 + D.1565_9;
  return D.1557_6;

which is ((a + a) + 4) * 2 + 4.

The original testcase gets optimized to

  return (a + 2) * 2 == a * 2 + 4;

which makes this bug related to PR15255 which is about missing foldings.

tree-ssa-reassoc should also transform (a + C1) * C2 to a * 2 + C3.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |15255
         AssignedTo|unassigned at gcc dot gnu   |rguenth at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2007-05-28 10:27:18         |2008-04-29 09:55:58
               date|                            |


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