[Bug tree-optimization/24028] New: CCP is broken

[Bug tree-optimization/24028] New: CCP is broken

[kazu at gcc dot gnu dot org]

Consider:

int
foo (int a)
{
  int b;
  int c;

  b = 0;
  if (b)
    c = a;
  else
    c = 9;

  return c;
}

At the end of CCP, we should see "return 9;".
However, we don't.

Here is the SSA form right before CCP.

foo (a)
{
  int c;
  int b;
  int D.1612;

<bb 0>:
  b_2 = 0;
  if (b_2 != 0) goto <L0>; else goto <L1>;

<L0>:;
  c_7 = a_6;
  goto <bb 3> (<L2>);

<L1>:;
  c_5 = 9;

  # c_1 = PHI <c_7(1), c_5(2)>;
<L2>:;
  c_3 = c_1;
  return c_3;

}

Here is a part of the output from CCP.

Simulating block 3

Visiting statement:
c_3 = c_1;

Lattice value changed to VARYING.  Adding SSA edges to worklist.

Note that c_3 is considered VARYING even though it should have
a constant value of 9.

This is really strange because CCP does not visit block 1 (or <L0>).
So when evaluating the PHI node

  # c_1 = PHI <c_7(1), c_5(2)>;

c_1 should get 9, and CCP does know that c_5 is equal to 9.

-- 
           Summary: CCP is broken
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: kazu at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug tree-optimization/24028] CCP is broken

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-09-23 05:25 -------
Confirmed, here is a better testcase which shows the issue:
int
foo (int a)
{
  int b;
  int c;


  b = 0;
  if (b)
    c = a;
  else
    c = 9;
  c++;

  if (c != 10)
     __builtin_abort();

  return c;
}

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dberlin at gcc dot gnu dot
                   |                            |org, dnovillo at gcc dot gnu
                   |                            |dot org
           Severity|normal                      |enhancement
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-09-23 05:25:25
               date|                            |


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

[Bug tree-optimization/24028] CCP is broken

[kazu at gcc dot gnu dot org]

------- Additional Comments From kazu at gcc dot gnu dot org  2005-09-23 05:29 -------
The reason why CCP thinks that the result of the PHI node is varying is
because ccp_initialize thinks that a PHI node is varying if at least
one of PHI argument is varying.

The problem is that the edge that the varying PHI argument is on may not be
executable, in which case we pessimistically think that the result of
the PHI node is varying.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |kazu at gcc dot gnu dot org
                   |dot org                     |
           Severity|enhancement                 |normal
             Status|NEW                         |ASSIGNED


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

[Bug tree-optimization/24028] CCP is broken

[dnovillo at redhat dot com]

------- Additional Comments From dnovillo at redhat dot com  2005-09-23 12:30 -------
Subject: Re:  CCP is broken

On September 23, 2005 01:29, kazu at gcc dot gnu dot org wrote:
> ------- Additional Comments From kazu at gcc dot gnu dot org 
> 2005-09-23 05:29 ------- The reason why CCP thinks that the result of
> the PHI node is varying is because ccp_initialize thinks that a PHI
> node is varying if at least one of PHI argument is varying.
>
This is very related to 23588. The heuristics to speed up propagation 
are crippling the propagator.  likely_value and ccp_initialize are the 
main functions to start fixing.


-- 


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

[Bug tree-optimization/24028] CCP is broken

[kazu at gcc dot gnu dot org]

------- Additional Comments From kazu at gcc dot gnu dot org  2005-09-24 04:29 -------
I tried the following code in ccp_initialize.

  for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
    {
      tree var = PHI_RESULT (phi);
      DONT_SIMULATE_AGAIN (phi) = (!do_store_ccp
                                   && !is_gimple_reg (var));
    }

I am seeing 0.1% slow down while compiling cc1-i files.  I ran
unpatched and patched compilers 5 times each, with the best and worst
cases thrown away.


-- 


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

[Bug tree-optimization/24028] CCP is broken

[kazu at gcc dot gnu dot org]

------- Additional Comments From kazu at gcc dot gnu dot org  2005-09-25 02:57 -------
By the way, unpatched cc1 propagated 95619 constants while compiling cc1-i files.
Patched one propagated 96482 constants in the ccp run (that is, not store-ccp).
So there is a 0.9% improvement.


-- 


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

[Bug tree-optimization/24028] CCP is broken

[steven at gcc dot gnu dot org]

------- Comment #8 from steven at gcc dot gnu dot org  2008-06-01 09:41 -------
This is now optimized by VRP, CCP, store-CCP, DOM, PRE, and TER.  It's hard to
break that test case!


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.4.0


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

[Bug tree-optimization/24028] CCP is broken

[kazu at gcc dot gnu dot org]

------- Comment #7 from kazu at gcc dot gnu dot org  2006-02-05 21:43 -------
Last time I came up with a patch, it introduced 0.1% or so of slow down.
I'll try my patch again when I get a chance.


-- 


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

[Bug tree-optimization/24028] CCP is broken

[pinskia at gcc dot gnu dot org]

------- Comment #6 from pinskia at gcc dot gnu dot org  2006-02-05 21:26 -------
Any news on this one?


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2005-12-26 22:22:14         |2006-02-05 21:26:16
               date|                            |


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