[Bug tree-optimization/23744] VRP does not merge discontinuous ranges of PHIs

[Bug tree-optimization/23744] VRP does not merge discontinuous ranges of PHIs

[pinskia at gcc dot gnu dot org]

------- Comment #2 from pinskia at gcc dot gnu dot org  2006-03-05 17:28 -------
Here is a new testcase so that we don't thread the jump as we currently do:
int g(int i, int j)
{
  int t = 0;
  int i1;
  if (i == j)
    t = 3;
  for(i1=0;i1<10000;i1++) h();
  if (t != 5)
    return 0;
  else
    return 1;
}


-- 


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

[Bug tree-optimization/23744] VRP does not merge discontinuous ranges of PHIs

[baldrick at free dot fr]

------- Comment #3 from baldrick at free dot fr  2006-04-16 20:35 -------
Created an attachment (id=11281)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=11281&action=view)
correct vrp_meet of VR_RANGEs


-- 


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

[Bug tree-optimization/23744] VRP does not merge discontinuous ranges of PHIs

[baldrick at free dot fr]

------- Comment #4 from baldrick at free dot fr  2006-04-16 20:50 -------
Does this patch fix it for you?  It looks more complicated
than it is (most of the patch is comment tweaks and white
space changes due to indentation change).  The real change
is to remove the check
  if (value_ranges_intersect_p (vr0, vr1))
for the case of VR_RANGE meet VR_RANGE.  Also, rather than
immediately setting the range to VR_VARYING if the interval
endpoints cannot be compared at compile time, instead the
no_meet logic is executed.  If the endpoints can't be
compared, then previously the call to value_ranges_intersect_p
would return false, and control would pass to no_meet, so this
preserves the previous logic, which matters for PR21090 for
example.

When working in the lattic of intervals ordered by reverse
set inclusion, the meet of two intervals A and B is, by definition,
the smallest interval containing both A and B.  [Normally this
would be called the join rather than the meet, but it's the meet
here because we consider smaller intervals to be bigger :)]
This smallest interval is the convex hull of A and B, or in
other words, if A=[a1,a2] and B=[b1,b2], then A meet B is
[min(a1,a2), max(b1,b2)].  This is exactly the interval that
vrp_meet calculates, except for some reason is only wants to
calculate it if A and B intersect; if they don't intersect it
gives up and goes all the way up to VR_VARYING.  By removing
the intersection check, vrp_meet now always calculates the
convex hull of two VR_RANGEs.

In your case, A=[0,0] and B=[3,3].  Because they don't intersect,
before vrp_meet would return VR_VARYING, which amount to [-INF,INF].
Now it returns [0,3].

While I was there, I tweaked the comments to the other cases,
like VR_ANTI_RANGE vs VR_ANTI_RANGE, because they are wrong,
mathematically speaking.  However, they are right in the case
when each anti-range is just anti-one-point, like ~[0,0], which
seems to be the main case of interest to VRP.  That's the reason
I didn't change the code.

This patch survives a bootstrap with all default languages plus Ada.
I ran the regression suite, but forgot to run it without this patch
beforehand, so now I don't know if the failures are due to this patch
or not, d'oh!


-- 

baldrick at free dot fr changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |baldrick at free dot fr


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

[Bug tree-optimization/23744] VRP does not merge discontinuous ranges of PHIs

[pinskia at gcc dot gnu dot org]

------- Comment #5 from pinskia at gcc dot gnu dot org  2006-05-01 06:19 -------
PR 25643 shows why this is even more important than just the testcase below.


-- 


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

[Bug tree-optimization/23744] VRP does not merge discontinuous ranges of PHIs

[patchapp at dberlin dot org]

------- Comment #6 from patchapp at dberlin dot org  2006-05-05 15:55 -------
Subject: Bug number PR23744

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-05/msg00200.html


-- 


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

[Bug tree-optimization/23744] VRP does not merge discontinuous ranges of PHIs

[baldrick at gcc dot gnu dot org]

------- Comment #7 from baldrick at gcc dot gnu dot org  2006-11-29 16:00 -------
Subject: Bug 23744

Author: baldrick
Date: Wed Nov 29 16:00:07 2006
New Revision: 119320

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=119320
Log:
        PR tree-optimization/23744
        * tree-vrp.c (vrp_meet): do not require ranges to intersect.
        * testsuite/gcc.dg/tree-ssa/pr23744.c: new test.
        * testsuite/gcc.dg/tree-ssa/update-threading.c: xfail.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/pr23744.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/gcc.dg/tree-ssa/update-threading.c
    trunk/gcc/tree-vrp.c


-- 


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

[Bug tree-optimization/23744] VRP does not merge discontinuous ranges of PHIs

[pinskia at gcc dot gnu dot org]

------- Comment #8 from pinskia at gcc dot gnu dot org  2006-11-30 11:07 -------
Fixed.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.3.0


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

[Bug tree-optimization/23744] VRP does not merge discontinuous ranges of PHIs

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-09-17 02:10 -------
Confirmed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-09-17 02:10:20
               date|                            |


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