[Bug tree-optimization/30105] New: missed PRE

[Bug tree-optimization/30105] New: missed PRE

[dann at godzilla dot ics dot uci dot edu]

The following 2 functions should be compiled to the same assembly. 
This is one of Briggs' compiler benchmarks.

void motion_test2(int *data)
{
  int j;
  int i = 1;
  if (data[1]) {
    data[data[2]] = 2;
    j = data[0] + data[3];
    i = i + j;
  }
  data[4] = data[0] + data[3];
  data[5] = i;
}
void motion_result2(int *data)
{
  int j;
  int i = 1;
  if (data[1]) {
    data[data[2]] = 2;
    j = data[0] + data[3];
    i = i + j;
  }
  else
    j = data[0] + data[3];
  data[4] = j;
  data[5] = i;
}


-- 
           Summary: missed PRE
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: dann at godzilla dot ics dot uci dot edu


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

[Bug tree-optimization/30105] missed code hoisting

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2006-12-07 14:20 -------
Confirmed (but it's not PRE).


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org
           Severity|normal                      |enhancement
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
           Keywords|                            |missed-optimization
   Last reconfirmed|0000-00-00 00:00:00         |2006-12-07 14:20:28
               date|                            |
            Summary|missed PRE                  |missed code hoisting


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

[Bug tree-optimization/30105] missed PRE (add)

[pinskia at gcc dot gnu dot org]

------- Comment #2 from pinskia at gcc dot gnu dot org  2006-12-07 18:18 -------
Actually this is a PRE opertunity.
if we look into .102t.final_cleanup, we notice we did the load PRE:
<L2>:;
  prephitmp.32 = *data;
  prephitmp.38 = *(data + 12B);
  i = 1;
  goto <bb 5> (<L1>);

<L0>:;
  *((int *) ((unsigned int) *(data + 8B) * 4) + data) = 2;
  prephitmp.32 = *data;
  prephitmp.38 = *(data + 12B);
  i = prephitmp.32 + 1 + prephitmp.38;

<L1>:;
  *(data + 16B) = prephitmp.38 + prephitmp.32;

but did not do the other part of the pre for the add.
I think this is a reassiocation issue:
<L0>:
  ...
  j_15 = D.1620_12 + 1;
  i_16 = j_15 + D.1622_14;

  # prephitmp.32_37 = PHI <pretmp.31_36(5), D.1622_14(3)>;
  # prephitmp.32_35 = PHI <pretmp.31_34(5), D.1620_12(3)>;
  # prephitmp.30_33 = PHI <pretmp.29_32(5), D.1621_13(3)>;
  # i_1 = PHI <1(5), i_16(3)>;
<L1>:;
....
  D.1620_18 = prephitmp.32_35;
  D.1621_19 = prephitmp.30_33;
  D.1622_20 = prephitmp.32_37;
  D.1624_21 = D.1622_20 + D.1620_18;


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|missed code hoisting        |missed PRE (add)


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

[Bug tree-optimization/30105] reassoc can sometimes get in the way of PRE

[pinskia at gcc dot gnu dot org]

------- Comment #3 from pinskia at gcc dot gnu dot org  2006-12-09 06:51 -------
This is just an reassiocation issue, if we have a_1 + b_2 + 1, we change it to
be a_1 + 1 + b_2  which seems wrong.  I wonder if we are trying to put the
constant first but when calling fold, it puts it second in the first
expression.
  j_15 = D.1620_12 + 1;
  i_16 = j_15 + D.1622_14;


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dberlin at gcc dot gnu dot
                   |                            |org
            Summary|missed PRE (add)            |reassoc can sometimes get in
                   |                            |the way of PRE


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

[Bug tree-optimization/30105] reassoc can sometimes get in the way of PRE

[dberlin at gcc dot gnu dot org]

------- Comment #4 from dberlin at gcc dot gnu dot org  2006-12-09 14:40 -------
Uh, before declaring it a reassociation issue, why don't you try turning off
reassoc and see if it actually fixes the problem.

As long as reassoc rewrites it the same everywhere, it would still be PRE'd.


-- 


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

[Bug tree-optimization/30105] reassoc can sometimes get in the way of PRE

[dberlin at gcc dot gnu dot org]

------- Comment #5 from dberlin at gcc dot gnu dot org  2006-12-09 15:06 -------
(In reply to comment #1)
> Confirmed (but it's not PRE).
> 

This actually is a case of PRE, because data[0] + data[3] is partially
redundant.

But according to the results, we *did* do the load PRE here.

In fact, PRE does the address calculation elimination too.

Replaced *data_3 with prephitmp.26_35 in D.1635_18 = *data_3;
Replaced data_3 + 12B with prephitmp.24_33 in D.1636_19 = data_3 + 12B;
Replaced *D.1636_19 with prephitmp.26_37 in D.1637_20 = *D.1636_19;

The above is the perfect, expected, PRE result for this testcase.

The real difference in assembly here is because in motion result duplicates the
actual addition, and we just leave it as the result of a phi merge of the two
variables.

IE motion_results produces

j = blah1 + blah2

in both the if and else block, and merge the j result

motion_test2 keeps one copy of

j = blah1 + blah2
in the main code path, and merges the blah1 and blah2 results

The second is smaller, and no more or less efficient since the addition is
calculated on both paths anyway.

Both are valid results, and what RTL does with them is it's business.

I don't believe you can claim they should generate identical assembly.

The actual thing this testcase is trying to test, that load-PRE is performed,
has succeeded.
Thus i am closing this bug as WORKSFORME.
If you see something *actually wrong* with the result, rather than just
disassembly, please feel free to reopen.


-- 

dberlin at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |WORKSFORME


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

[Bug tree-optimization/30105] reassoc can sometimes get in the way of PRE

[dann at godzilla dot ics dot uci dot edu]

------- Comment #6 from dann at godzilla dot ics dot uci dot edu  2006-12-12 06:07 -------
(In reply to comment #5)
> (In reply to comment #1)
> > Confirmed (but it's not PRE).
> > 

> The second is smaller, and no more or less efficient since the addition is
> calculated on both paths anyway.
> 
> Both are valid results, and what RTL does with them is it's business.
> 
> I don't believe you can claim they should generate identical assembly.
> 
> The actual thing this testcase is trying to test, that load-PRE is performed,
> has succeeded.
> Thus i am closing this bug as WORKSFORME.
> If you see something *actually wrong* with the result, rather than just
> disassembly, please feel free to reopen.

Here is a slightly modified example that shows that there's still a PRE
opportunity 

void motion_test22(int * data, int i)
{
  int j;
  if (data[1]) {
    data[data[2]] = 2;
    j = data[0] *   data[3];
    i = i *  j;
  }
  data[4] = data[0] * data[3];
  data[5] = i;
}

<L0>:;
  *((int *) ((unsigned int) *(data + 8B) * 4) + data) = 2;
  prephitmp.26 = *data;
  prephitmp.31 = *(data + 12B);
  i = prephitmp.26 * i * prephitmp.31;

<L1>:;
  *(data + 16B) = prephitmp.31 * prephitmp.26;
  *(data + 20B) = i;
  return;

There are 3 multiplications on the L0-L1 path. It should be possible
to only have 2 multiplications on that path.


-- 

dann at godzilla dot ics dot uci dot edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|WORKSFORME                  |


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

[Bug tree-optimization/30105] reassoc can sometimes get in the way of PRE

[dberlin at dberlin dot org]

------- Comment #7 from dberlin at gcc dot gnu dot org  2006-12-12 16:49 -------
Subject: Re:  reassoc can sometimes get in the way of PRE

>
> Here is a slightly modified example that shows that there's still a PRE
> opportunity
>
> void motion_test22(int * data, int i)
> {
>   int j;
>   if (data[1]) {
>     data[data[2]] = 2;
>     j = data[0] *   data[3];
>     i = i *  j;
>   }
>   data[4] = data[0] * data[3];
>   data[5] = i;
> }
>
> <L0>:;
>   *((int *) ((unsigned int) *(data + 8B) * 4) + data) = 2;
>   prephitmp.26 = *data;
>   prephitmp.31 = *(data + 12B);
>   i = prephitmp.26 * i * prephitmp.31;
>
> <L1>:;
>   *(data + 16B) = prephitmp.31 * prephitmp.26;
>   *(data + 20B) = i;
>   return;
>
> There are 3 multiplications on the L0-L1 path. It should be possible
> to only have 2 multiplications on that path.

now *this* is a reassoc (or VN) problem.
It's not easy to see how to fix it, we can't always guess the right ordering.


-- 


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

[Bug tree-optimization/30105] reassoc can sometimes get in the way of PRE

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
         Resolution|                            |FIXED

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-02-08 23:09:06 UTC ---
Both testcases work in 4.6.0 and above so closing as fixed.

[Bug tree-optimization/30105] reassoc can sometimes get in the way of PRE

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.6.0