[Bug tree-optimization/26406] New: Fowardprop does harm for VRP to figure out if a point is non zero

[Bug tree-optimization/26406] New: Fowardprop does harm for VRP to figure out if a point is non zero

[pinskia at gcc dot gnu dot org]

Example:
int *f(int *b)
{
  int * a = new int[104];
  *a = 1;
  if (a == 0)
    return b;
  return a;
}
-----
Found this while looking into tramp3d.


-- 
           Summary: Fowardprop does harm for VRP to figure out if a point is
                    non zero
           Product: gcc
           Version: 4.2.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
OtherBugsDependingO 22501
             nThis:


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

[Bug tree-optimization/26406] Fowardprop does harm for VRP to figure out if a point is non zero

[pinskia at gcc dot gnu dot org]

------- Comment #1 from pinskia at gcc dot gnu dot org  2006-02-21 21:45 -------
It shows up in Intersector<Dim>::Intersector via inlining.


-- 


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

[Bug tree-optimization/26406] Fowardprop does harm for VRP to figure out if a point is non zero

[steven at gcc dot gnu dot org]

------- Comment #2 from steven at gcc dot gnu dot org  2006-02-22 07:35 -------
Confirmed.

Before forwprop1:

  D.2354_2 = operator new [] (416);
  a_3 = (int *) D.2354_2;
  *a_3 = 1;
  if (a_3 == 0B) goto <L0>; else goto <L1>;

After forwprop1:
  D.2354_2 = operator new [] (416);
  a_3 = (int *) D.2354_2;
  *a_3 = 1;
  if (D.2354_2 == 0B) goto <L0>; else goto <L1>;

Now VRP can't see that D.2354_2 is non-NULL:

ASSERT_EXPRs to be inserted

Assertions to be inserted for a_3
        *a_3 = 1
        BB #2
        PREDICATE: a_3 ne_expr 0B

(...)

Visiting conditional with predicate: D.2354_2 == 0B
With known ranges
        D.2354_2: VARYING

(...)

b_1: VARYING
D.2354_2: VARYING
a_3: VARYING
<retval>_4: VARYING
a_5: ~[0B, 0B]  EQUIVALENCES: { a_3 a_11 } (2 elements)
b_6: VARYING
b_7: [b_6, b_6]  EQUIVALENCES: { b_6 } (1 elements)
a_11: ~[0B, 0B]  EQUIVALENCES: { a_3 } (1 elements)

So D.2354_2 stays VARYING and this blocks us from optimizing away the
condition:
  D.2354_2 = operator new [] (416);
  a_3 = (int *) D.2354_2;
  *a_3 = 1;
  if (D.2354_2 == 0B) goto <L0>; else goto <L1>;


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dnovillo at gcc dot gnu dot
                   |                            |org, law at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2006-02-22 07:35:56
               date|                            |


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

[Bug tree-optimization/26406] Fowardprop does harm for VRP to figure out if a point is non zero

[rguenth at gcc dot gnu dot org]

------- Comment #3 from rguenth at gcc dot gnu dot org  2006-02-22 10:05 -------
Interesting.  a_3 is not single use, so we shouldn't do this.  Investigating.


-- 

rguenth at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/26406] Fowardprop does harm for VRP to figure out if a point is non zero

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2006-02-22 10:32 -------
find_equivalent_equality_comparison through simplify_cond,
forward_propagate_into_cond does this.  I have a patch which restricts forwprop
to using single-use names.  Though I wonder if this is appropriate and we
rather should teach VRP to infer range information for D.2354_2 from a_3.


-- 


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

[Bug tree-optimization/26406] Fowardprop does harm for VRP to figure out if a point is non zero

[rguenth at gcc dot gnu dot org]

------- Comment #5 from rguenth at gcc dot gnu dot org  2006-02-22 12:47 -------
Of course we have the other case where we _have_ to propagate to optimize away
the test (gcc.dg/tree-ssa/20030807-2.c):

foo(int n)
{
  int *space = (int *)__builtin_alloca (n);

  if (space == 0)
    abort ();
  else
    bar (space);
}

where there is a 2nd use of space:

foo (n)
{
  int * space;
  void * D.1899;
  long unsigned int D.1898;

<bb 2>:
  D.1898_2 = (long unsigned int) n_1;
  D.1899_3 = __builtin_alloca (D.1898_2);
  space_4 = (int *) D.1899_3;
  if (space_4 == 0B) goto <L0>; else goto <L1>;

<L0>:;
  abort ();

<L1>:;
  bar (space_4);
  return;

}

So I think extending VRP is the only way to get both testcases optimized.


-- 


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

[Bug tree-optimization/26406] Fowardprop does harm for VRP to figure out if a point is non zero

[rguenth at gcc dot gnu dot org]

------- Comment #6 from rguenth at gcc dot gnu dot org  2006-02-22 12:49 -------
Created an attachment (id=10891)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=10891&action=view)
patch restricting forwprop

Patch that apart from regressing gcc.dg/tree-ssa/20030807-2.c bootstrapped and
tested ok.


-- 


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

[Bug tree-optimization/26406] Fowardprop does harm for VRP to figure out if a point is non zero

[pinskia at gcc dot gnu dot org]

------- Comment #7 from pinskia at gcc dot gnu dot org  2006-02-22 12:58 -------
(In reply to comment #6)
> Patch that apart from regressing gcc.dg/tree-ssa/20030807-2.c bootstrapped and
> tested ok.
There is no regressions here as this test is already failing before your patch,
see PR 26344.


-- 


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

[Bug tree-optimization/26406] Fowardprop does harm for VRP to figure out if a point is non zero

[patchapp at dberlin dot org]

------- Comment #8 from patchapp at dberlin dot org  2006-02-22 13:10 -------
Subject: Bug number PR26406

A patch for this bug has been added to the patch tracker.
The mailing list url for the patch is
http://gcc.gnu.org/ml/gcc-patches/2006-02/msg01754.html


-- 


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

[Bug tree-optimization/26406] Fowardprop does harm for VRP to figure out if a point is non zero

[law at redhat dot com]

------- Comment #9 from law at redhat dot com  2006-02-22 15:24 -------
Subject: Re:  Fowardprop does harm for VRP to
        figure out if a point is non zero

On Wed, 2006-02-22 at 10:32 +0000, rguenth at gcc dot gnu dot org wrote:
> 
> ------- Comment #4 from rguenth at gcc dot gnu dot org  2006-02-22 10:32 -------
> find_equivalent_equality_comparison through simplify_cond,
> forward_propagate_into_cond does this.  I have a patch which restricts forwprop
> to using single-use names.  Though I wonder if this is appropriate and we
> rather should teach VRP to infer range information for D.2354_2 from a_3.
Please don't.  I'm already aware of this issue and looking at a better
solution.

jeff


-- 


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

[Bug tree-optimization/26406] Fowardprop does harm for VRP to figure out if a point is non zero

[law at redhat dot com]

------- Comment #10 from law at redhat dot com  2006-02-22 16:22 -------
Subject: Re:  Fowardprop does harm for VRP to
        figure out if a point is non zero

On Wed, 2006-02-22 at 12:47 +0000, rguenth at gcc dot gnu dot org wrote:
A little history...

DOM was pretty clever in that it had the ability to backwards
propagate some non-null ranges.  That code was written to make
DOM's non-null tracking relatively immune to things like comparison
simplification.  It was quick, simple and relatively effective.

We *really* don't want to do that in VRP.  First it violates a
fundamental principle designed to ensure VRP terminates.  Namely
that we don't move backward in the lattice.  ie, we don't allow
VR_VARYING -> VR_RANGE/VR_ANTI_RANGE state transitions.

I briefly toyed with the idea of doing the backward range
propagation after all the forward propagation was done, but
before substitution/simplifications.  There's a handful of
implementation issues with this approach and it will likely
result in a measurable compile-time hit due to the extra
ASSERT_EXPRs.  It's something I'm still pondering, but it's
not my favored solution ATM.


What I'm seriously looking at and still evaluating is 
delaying the forwprop pass.  For the initial stuff I looked
at it seems like a *much* better solution -- not only does
it allow VRP to catch more of the non-null stuff, but it
seems to help forwprop and the following DOM pass as well.
I'll be returning to this once we've reached closure on the
Ada regressions.

jeff


-- 


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

[Bug tree-optimization/26406] Fowardprop does harm for VRP to figure out if a point is non zero

[rguenth at gcc dot gnu dot org]

------- Comment #11 from rguenth at gcc dot gnu dot org  2006-02-22 20:55 -------
So I suppose VRP cannot see "backwards" for

  i_2 = j_1;
  if (i_2 == 0)
    return j_1;

?  (of course copyprop would clean this up, but suppose for a moment this
gets to VRP)

If it can see that i_1 is zero at the point of the return statement then we
can teach VRP to take

  a_1 = (T *)x_1;

simply as copy, canonicalizing all pointer types to (void*) for the sake
of VRP (which would also avoid generating extra permanent integer constants
with various types in the pool).


-- 


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

[Bug tree-optimization/26406] Fowardprop does harm for VRP to figure out if a point is non zero

[law at redhat dot com]

------- Comment #12 from law at redhat dot com  2006-02-22 21:45 -------
Subject: Re:  Fowardprop does harm for VRP to
        figure out if a point is non zero

On Wed, 2006-02-22 at 20:55 +0000, rguenth at gcc dot gnu dot org wrote:
> 
> ------- Comment #11 from rguenth at gcc dot gnu dot org  2006-02-22 20:55 -------
> So I suppose VRP cannot see "backwards" for
> 
>   i_2 = j_1;
>   if (i_2 == 0)
>     return j_1;
> 
> ?  (of course copyprop would clean this up, but suppose for a moment this
> gets to VRP)
Nope, it can't.  It's not just the lack of backwards propagation,
but also the fact that i is unused in the subgraphs after the
conditional, so VRP won't record any information for either i or j
in this kind of example.

Fixing VRP to gather data for "i" in this example would result in
a pretty significant compile-time hit.

I'll note this was one of the reasons why we moved copyprop to
run immediately before VRP -- copies in the IL were hiding a
nontrivial number of detectable and useful ranges.

jeff


-- 


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

[Bug tree-optimization/26406] [4.2 Regression] Forwardprop does harm for VRP to figure out if a point is non zero

[pinskia at gcc dot gnu dot org]

------- Comment #13 from pinskia at gcc dot gnu dot org  2006-02-25 15:49 -------
This is a regression in fact.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|enhancement                 |normal
      Known to fail|                            |4.2.0
      Known to work|                            |4.1.0
            Summary|Forwardprop does harm for   |[4.2 Regression] Forwardprop
                   |VRP to figure out if a point|does harm for VRP to figure
                   |is non zero                 |out if a point is non zero
   Target Milestone|---                         |4.2.0


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

[Bug tree-optimization/26406] [4.2 Regression] Forwardprop does harm for VRP to figure out if a point is non zero

[pinskia at gcc dot gnu dot org]

------- Comment #14 from pinskia at gcc dot gnu dot org  2006-02-25 17:31 -------
Why is forward prop doing this in the first place, this actually causes
increased register pressure for sure, at least for non one use variables?


-- 


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

[Bug tree-optimization/26406] [4.2 Regression] Forwardprop does harm for VRP to figure out if a point is non zero

[law at redhat dot com]

------- Comment #15 from law at redhat dot com  2006-02-25 18:31 -------
Subject: Re:  [4.2 Regression] Forwardprop
        does harm for VRP to figure out if a point is non zero

On Sat, 2006-02-25 at 17:31 +0000, pinskia at gcc dot gnu dot org wrote:
> 
> ------- Comment #14 from pinskia at gcc dot gnu dot org  2006-02-25 17:31 -------
> Why is forward prop doing this in the first place, this actually causes
> increased register pressure for sure, at least for non one use variables?
Because in the case of multiple-use it's removing a partial
redundancy.

I've already stated I believe I have a way to fix this.  Please
be patient, there are more pressing matters to deal with first.

jeff


-- 


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

[Bug tree-optimization/26406] [4.2 Regression] Forwardprop does harm for VRP to figure out if a point is non zero

[law at redhat dot com]

------- Comment #16 from law at redhat dot com  2006-03-08 16:43 -------
C++ version of the problems in 26344.  Fixing 26344 will fix this bug as well.

*** This bug has been marked as a duplicate of 26344 ***


-- 

law at redhat dot com changed:

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


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