[Bug tree-optimization/23588] New: CCP not fully propagating constants

[Bug tree-optimization/23588] New: CCP not fully propagating constants

[dberlin at gcc dot gnu dot org]

Consider
int main(int a, int b, int c, int d)
{
  d = -1;
  int e = (a | b) | (c | d);
  int f = (c | a) | (b | d);
 return e | f;
}

Because d == -1, the whole thing folds to return -1;

CCP doesn't do this however.
It takes:
  # BLOCK 0
  # PRED: ENTRY (fallthru)
  d_1 = -1;
  D.1285_4 = a_2 | b_3;
  D.1286_6 = c_5 | d_1;
  e_7 = D.1285_4 | D.1286_6;
  D.1287_8 = c_5 | a_2;
  D.1288_9 = b_3 | d_1;
  f_10 = D.1287_8 | D.1288_9;
  D.1289_12 = e_7 | f_10;
  return D.1289_12;
  # SUCC: EXIT

and turns it into
main (a, b, c, d)
{
  int f;
  int e;
  int D.1289;
  int D.1288;
  int D.1287;
  int D.1286;
  int D.1285;

  # BLOCK 0
  # PRED: ENTRY (fallthru,exec)
  d_1 = -1;
  D.1285_4 = a_2 | b_3;
  D.1286_6 = -1;
  e_7 = D.1285_4 | D.1286_6;
  D.1287_8 = c_5 | a_2;
  D.1288_9 = -1;
  f_10 = D.1287_8 | D.1288_9;
  D.1289_12 = e_7 | f_10;
  return D.1289_12;
  # SUCC: EXIT

}

(note that it's not actually following the use edges, or it would have folded it
all the way)

The propagation looks broken:

;; Function main (main)

Immediate_uses:

d_1 : -->2 uses.
D.1288_9 = b_3 | d_1;
D.1286_6 = c_5 | d_1;

a_2 : -->2 uses.
D.1287_8 = c_5 | a_2;
D.1285_4 = a_2 | b_3;

b_3 : -->2 uses.
D.1288_9 = b_3 | d_1;
D.1285_4 = a_2 | b_3;

D.1285_4 : --> single use.
e_7 = D.1285_4 | D.1286_6;

c_5 : -->2 uses.
D.1287_8 = c_5 | a_2;
D.1286_6 = c_5 | d_1;

D.1286_6 : --> single use.
e_7 = D.1285_4 | D.1286_6;

e_7 : --> single use.
D.1289_12 = e_7 | f_10;

D.1287_8 : --> single use.
f_10 = D.1287_8 | D.1288_9;

D.1288_9 : --> single use.
f_10 = D.1287_8 | D.1288_9;

f_10 : --> single use.
D.1289_12 = e_7 | f_10;

D.1289_12 : --> single use.
return D.1289_12;

<retval>_13 : --> no uses.

Simulating block 0

Visiting statement:
d_1 = -1;

Lattice value changed to CONSTANT -1.  Adding SSA edges to worklist.

Substituing values and folding statements

Folded statement: D.1286_6 = c_5 | d_1;
            into: D.1286_6 = -1;

Folded statement: D.1288_9 = b_3 | d_1;
            into: D.1288_9 = -1;

Constants propagated:      2
Copies propagated:         0
Predicates folded:         0


If it had actually added the ssa edges to the worklist, followed them, and
folded the statements containing the new constant, it would have gotten the
right answer.

-- 
           Summary: CCP not fully propagating constants
           Product: gcc
           Version: 4.1.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: dberlin at gcc dot gnu dot org
                CC: dnovillo at gcc dot gnu dot org,gcc-bugs at gcc dot gnu
                    dot org


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

[Bug tree-optimization/23588] CCP not fully propagating constants

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-27 03:31 -------
Confirmed.  The same thing happens with s/-1/0/ s/|/&/ .

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-08-27 03:31:22
               date|                            |


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

[Bug tree-optimization/23588] CCP not fully propagating constants

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-09-07 03:46 -------
The first thing is that ccp_initialize sets DONT_SIMULATE_AGAIN on the statement so don't simulate 
that statement and then we don't call fold_ccp on them.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization


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

[Bug tree-optimization/23588] CCP not fully propagating constants

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-09-07 03:51 -------
(In reply to comment #2)
> The first thing is that ccp_initialize sets DONT_SIMULATE_AGAIN on the statement so don't simulate 
> that statement and then we don't call fold_ccp on them.

And then we hit an assert if we change evaluate_stmt to be always call fold_ccp.
The assert is in set_lattice_value, when we are changing from VARRYING to CONSTANT which should be 
a valid transition.

-- 


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

[Bug tree-optimization/23588] CCP not fully propagating constants

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-09-07 04:19 -------
(In reply to comment #3)
> And then we hit an assert if we change evaluate_stmt to be always call fold_ccp.
> The assert is in set_lattice_value, when we are changing from VARRYING to CONSTANT which should 
> be  a valid transition.

Only if the VARRYING is the default state.
Before the TCB, this was allowed:
/* VARYING -> CONSTANT is an invalid state transition, except
 for objects which start off in a VARYING state.  */

-- 


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

[Bug tree-optimization/23588] CCP not fully propagating constants

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-09-07 13:36 -------
Subject: Re:  CCP not fully propagating
	constants

On Wed, 2005-09-07 at 04:19 +0000, pinskia at gcc dot gnu dot org wrote:
> ------- Additional Comments From pinskia at gcc dot gnu dot org  2005-09-07 04:19 -------
> (In reply to comment #3)
> > And then we hit an assert if we change evaluate_stmt to be always call fold_ccp.
> > The assert is in set_lattice_value, when we are changing from VARRYING to CONSTANT which should 
> > be  a valid transition.
> 
> Only if the VARRYING is the default state.
> Before the TCB, this was allowed:
> /* VARYING -> CONSTANT is an invalid state transition, except
>  for objects which start off in a VARYING state.  */
> 

VARYING->CONSTANT should actually never happen, regardless of what the
comment says.

We shouldn't set it to VARYING in the first place if we think it has a
chance of becoming CONSTANT.

So i imagine get_default_value or whatever needs to be more
foregiving :)





-- 


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

[Bug tree-optimization/23588] CCP not fully propagating constants

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-09-21 15:02 -------
Let's fix this. 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |steven at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2005-08-27 03:31:22         |2005-09-21 15:02:13
               date|                            |


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