[Bug tree-optimization/23286] missed fully redundant expression

[Bug tree-optimization/23286] missed fully redundant expression

[bonzini at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |4.1.0


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

[Bug tree-optimization/23286] New: missed fully redundant expression

[bonzini at gcc dot gnu dot org]

In this code, a <<= 1 is fully redundant

  unsigned short f(unsigned short a)
  {
    if (a & 0x8000)
      a <<= 1, a = a ^ 0x1021;
    else
      a <<= 1;

    return a;
  }

the body should be turned into

  unsigned short f(unsigned short a)
  {
    unsigned short b = a << 1;
    if (a & 0x8000)
      a = b, a = a ^ 0x1021;
    else
      a = b;
  
    return a;
  }

or something similar.  However PRE leaves the GIMPLE unchanged:

f (a)
{
  int D.1267;
  short int a.0;
<bb 0>:
  a.0_3 = (short int) a_2;
  if (a.0_3 < 0) goto <L0>; else goto <L1>;

<L0>:;
  a_7 = a_2 << 1;
  a_8 = a_7 ^ 4129;
  goto <bb 3> (<L2>);
<L1>:;
  a_6 = a_2 << 1;

  # a_1 = PHI <a_8(1), a_6(2)>;
<L2>:;
  D.1267_4 = (int) a_1;
  return D.1267_4;
}

On PPC, this is only caught after reload.

Paolo

-- 
           Summary: missed fully redundant expression
           Product: gcc
           Version: 4.1.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: bonzini at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug tree-optimization/23286] missed fully redundant expression

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-08 18:42 -------
Confirmed, for some reason the following is caught though:
  unsigned short f(unsigned short a)
  {
    unsigned short b = a <<1;
    if (a & 0x8000)
      a <<= 1, a = a ^ 0x1021;
    else
      a = b;

    return a;
  }
as a<<1 is caught being redundant.  FRE catches the above on the mainline.

Hmm there is only one VH for the expression:
Created value VH.0 for a_2
Created value VH.1 for (short int) VH.0
Created value VH.2 for VH.0 << 1
Created value VH.3 for VH.2 ^ 4129
Created value VH.4 for a_1
Created value VH.5 for (int) VH.4
Created value VH.6 for <retval>_5
exp_gen[-1] := {  }
tmp_gen[-1] := { a_2 (VH.0)  }
avail_out[-1] := { a_2 (VH.0)  }
exp_gen[0] := { a_2 (VH.0) , (short int) VH.0 (VH.1)  }
tmp_gen[0] := { a.0_3 (VH.1)  }
avail_out[0] := { a_2 (VH.0) , a.0_3 (VH.1)  }
exp_gen[1] := { a_2 (VH.0) , VH.0 << 1 (VH.2) , VH.2 ^ 4129 (VH.3)  }
tmp_gen[1] := { a_7 (VH.2) , a_8 (VH.3)  }
avail_out[1] := { a_2 (VH.0) , a.0_3 (VH.1) , a_7 (VH.2) , a_8 (VH.3)  }
exp_gen[2] := { a_2 (VH.0) , VH.0 << 1 (VH.2)  }
tmp_gen[2] := { a_6 (VH.2)  }
avail_out[2] := { a_2 (VH.0) , a.0_3 (VH.1) , a_6 (VH.2)  }
exp_gen[3] := { a_1 (VH.4) , (int) VH.4 (VH.5)  }
tmp_gen[3] := { D.1280_4 (VH.5) , <retval>_5 (VH.6)  }
avail_out[3] := { a_1 (VH.4) , a_2 (VH.0) , a.0_3 (VH.1) , D.1280_4 (VH.5) , <retval>_5 (VH.6)  }
exp_gen[-2] := {  }
tmp_gen[-2] := {  }
avail_out[-2] := {  }


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dberlin at gcc dot gnu dot
                   |                            |org
           Severity|normal                      |enhancement
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-08-08 18:42:33
               date|                            |


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

[Bug tree-optimization/23286] missed fully redundant expression

[dberlin at gcc dot gnu dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-08-08 18:53 -------
(In reply to comment #1)
> Confirmed, for some reason the following is caught though:
because it's a fully redundant expression, that is available when we go to
eliminate, as opposed to the original, which would require hoisting, and is
*not* partially redundant.

> Hmm there is only one VH for the expression:

As one would expect.

This is not a missed optimization for PRE.
PRE is not a generic hoister.
In fact, in this case, it doesn't actually save anything but size to perform
this "optimization".
All it will do is make b live over the use of a, adding another register to
allocate that has a conflict.
I don't see this as a bug at all, except maybe at -Os.
Even then, it's a a hoisting issue, using very busy expressions, not a PRE issue.

-- 


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

[Bug tree-optimization/23286] missed fully redundant expression

[dberlin at gcc dot gnu dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-08-08 18:56 -------
(In reply to comment #1)
> Confirmed, for some reason the following is caught though:

If you thought about it, you'd notice that your example below has two
computations of a = b along the if branch, which is not optimal.
The original has one computation on each path which is already optimal.
>   unsigned short f(unsigned short a)
>   {
>     unsigned short b = a <<1;
>     if (a & 0x8000)
>       a <<= 1, a = a ^ 0x1021;
>     else
>       a = b;
> 
>     return a;
>   }


-- 


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

[Bug tree-optimization/23286] missed fully redundant expression

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-08 19:34 -------
This is basically PR 15559 which was marked as invalid.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |15559


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

[Bug tree-optimization/23286] missed fully redundant expression

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-08 19:36 -------
and a dup of bug 5738 really.

I almost want to close this fully as a dup of bug 5738.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |5738


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

[Bug tree-optimization/23286] missed fully redundant expression

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-08 19:54 -------
Here is a stupid testcase which can be sped up by pulling the reduandant expressions up:
int ii;
static inline int f(int i, int ii)
{
  return i/ ii;
}

int h(int) __attribute__((pure,const));

int g(int i)
{
  int j, j1 = i;
  for (j = 0; j <1000; j++)
    {
      int ii1 = ii;
      if (h(j))
        i = j1/ii1 + 2;
      else
        i = j1/ii1;
    }
  return i;
}

As we then pull the division before the loop.  As I said this was stupid as this was made up and I don't 
know how often this happens in real life.

-- 


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

[Bug tree-optimization/23286] missed fully redundant expression

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-08-08 20:29 -------
Subject: Re:  missed fully redundant expression

On Mon, 2005-08-08 at 19:54 +0000, pinskia at gcc dot gnu dot org wrote:
> ------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-08 19:54 -------
> Here is a stupid testcase which can be sped up by pulling the reduandant expressions up:
> int ii;
> static inline int f(int i, int ii)
> {
>   return i/ ii;
> }
> 
> int h(int) __attribute__((pure,const));
> 
> int g(int i)
> {
>   int j, j1 = i;
>   for (j = 0; j <1000; j++)
>     {
>       int ii1 = ii;
>       if (h(j))
>         i = j1/ii1 + 2;
>       else
>         i = j1/ii1;
>     }
>   return i;
> }
> 

Yes, if we hoisted this, we would then pull it out of the loop.




-- 


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

[Bug tree-optimization/23286] missed fully redundant expression

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-08-08 20:40 -------
Subject: Re:  missed fully redundant expression

On Mon, 2005-08-08 at 19:54 +0000, pinskia at gcc dot gnu dot org wrote:
> ------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-08 19:54 -------
> Here is a stupid testcase which can be sped up by pulling the reduandant expressions up:
> int ii;
> static inline int f(int i, int ii)
> {
>   return i/ ii;
> }
> 
> int h(int) __attribute__((pure,const));
> 
> int g(int i)
> {
>   int j, j1 = i;
>   for (j = 0; j <1000; j++)
>     {
>       int ii1 = ii;
>       if (h(j))
>         i = j1/ii1 + 2;
>       else
>         i = j1/ii1;
>     }
>   return i;
> }
> 
You are also going to have to hoist the ii1 = ii because it has a vuse.




-- 


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

[Bug tree-optimization/23286] missed fully redundant expression

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-29 12:33 -------
*** Bug 23619 has been marked as a duplicate of this bug. ***

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rakdver at gcc dot gnu dot
                   |                            |org


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