Re: [PATCH] Fix PR55011

[Michael Matz]

Hi,

On Tue, 23 Oct 2012, Richard Biener wrote:

> > So, one question, are you claiming that a VRP worker like this:
> > 
> >VR derive_new_range_from_operation (VR a, VR b)
> > 
> > is _ever_ allowed to return UNDEFINED when a or b is something else than 
> > UNDEFINED?  You seem to claim so AFAIU, but at the same time admit that 
> > this results in oscillation, and hence needs fixing up in the routine that 
> > uses the above result to install the lattice value in the map.  I'm 
> > obviously saying that the above worker is not allowed to return UNDEFINED.
> 
> Yes.  Do you say it never may return a RANGE if either a or b is
> VARYING?

It may not do so if the recorded lattice value for the return ssa name was 
already BOTTOM.  But I think I see were you're getting at; you say the old 
lattice value is not available to derive_new_range_from_operation, so that 
one simply isn't capable of doing the right thing?

But this is about BOTTOM vs. RANGE, not about TOP; I think the workers 
should indeed not be allowed to return TOP, which would create an 
unsymmetry between TOP and BOTTOM, but there we are.

OTOH, when the old lattice value isn't available, I indeed also see no 
other way than your current patch, so let's transform my complaint into 
just a general unhappiness with how VRP is implemented :)


Ciao,
Michael.

Re: [PATCH] Fix PR55011

[Richard Biener]

On Tue, 23 Oct 2012, Michael Matz wrote:

> Hi,
> 
> On Tue, 23 Oct 2012, Richard Biener wrote:
> 
> > > > > ... for this.  We should never "produce" UNDEFINED when the input 
> > > > > wasn't 
> > > > > UNDEFINED already.
> > > > 
> > > > Why?
> > > 
> > > Because doing so _always_ means an invalid lattice transition.  UNDEFINED 
> > > is TOP, anything not UNDEFINED is not TOP.  So going from something to 
> > > UNDEFINED is always going upward the lattice and hence in the wrong 
> > > direction.
> > 
> > Um, what do you mean with "input" then?  Certainly intersecting
> > [2, 4] and [6, 8] yields UNDEFINED.
> 
> Huh?  It should yield VARYING, i.e. BOTTOM, not UNDEFINED, aka TOP.  
> That's the whole point I'm trying to make.  You're fixing up this very 
> bug.

I suppose we can argue about this one.  When using VARYING here
this VARYING can leak out from unreachable paths in the CFG.

> > > > We shouldn't update the lattice this way, yes, but that is what
> > > > the patch ensures.
> > > 
> > > An assert ensures.  A work around works around a problem.  I say that the 
> > > problem is in those routines that produced the "new" UNDEFINED range in 
> > > the first place, and it's not update_value_range's job to fix that after 
> > > the fact.
> > 
> > It is.  See how CCPs set_lattice_vlaue adjusts the input as well.
> 
> It actually does what I say update_value_range should do.  It _asserts_ a 
> valid transition, and the fixup before is correctly marked with a ??? 
> comment about the improperty of the place of such fixing up.
> 
> > It's just not convenient to repeat the adjustments everywhere.
> 
> Sure.  If the workers were correct there would be no need to do any 
> adjustments.
> 
> > > > The workers only compute a new value-range
> > > > for a stmt based on input value ranges.
> > > 
> > > And if they produce UNDEFINED when the input wasn't so, then _that's_ 
> > > where the bug is.
> > 
> > See above.
> 
> Hmm?  See above.
> 
> > > I'm not sure I understand.  You claim that the workers have to produce 
> > > UNDEFINED from non-UNDEFINED in some cases, otherwise we oscillate?  
> > > That sounds strange.  Or do you mean that we oscillate without your 
> > > patch to update_value_range?  That I believe, it's the natural result 
> > > of going a lattice the wrong way, but I say that update_value_range is 
> > > not the place to silently fix invalid transitions.
> > 
> > No, I mean that going up the lattice results in oscillation.
> 
> And that's why the workers are not supposed to do that.  They can't 
> willy-nilly create new UNDEFINED/TOP lattice values.  Somehow we have a 
> disconnect in this discussion over some very basic property, let's try to 
> clean this up first.

Well, consider 0 * VARYING.  That's still [0, 0], not VARYING.
Workers should compute the best approximation for a range of
an operation, otherwise we cannot use them to build up operations
by pieces (like we do for -b).

> So, one question, are you claiming that a VRP worker like this:
> 
>VR derive_new_range_from_operation (VR a, VR b)
> 
> is _ever_ allowed to return UNDEFINED when a or b is something else than 
> UNDEFINED?  You seem to claim so AFAIU, but at the same time admit that 
> this results in oscillation, and hence needs fixing up in the routine that 
> uses the above result to install the lattice value in the map.  I'm 
> obviously saying that the above worker is not allowed to return UNDEFINED.

Yes.  Do you say it never may return a RANGE if either a or b is
VARYING?

The whole point is that we have both derive_new_range_from_operation
and update_lattice_value.  Only the latter knows how we iterate
and that this iteration restricts the values we may update the
lattice with.  derive_new_range_from_operation is supposed to be
generally useful.

Richard.

-- 
Richard Biener 
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend

Re: [PATCH] Fix PR55011

[Michael Matz]

Hi,

On Tue, 23 Oct 2012, Richard Biener wrote:

> > > > ... for this.  We should never "produce" UNDEFINED when the input 
> > > > wasn't 
> > > > UNDEFINED already.
> > > 
> > > Why?
> > 
> > Because doing so _always_ means an invalid lattice transition.  UNDEFINED 
> > is TOP, anything not UNDEFINED is not TOP.  So going from something to 
> > UNDEFINED is always going upward the lattice and hence in the wrong 
> > direction.
> 
> Um, what do you mean with "input" then?  Certainly intersecting
> [2, 4] and [6, 8] yields UNDEFINED.

Huh?  It should yield VARYING, i.e. BOTTOM, not UNDEFINED, aka TOP.  
That's the whole point I'm trying to make.  You're fixing up this very 
bug.

> > > We shouldn't update the lattice this way, yes, but that is what
> > > the patch ensures.
> > 
> > An assert ensures.  A work around works around a problem.  I say that the 
> > problem is in those routines that produced the "new" UNDEFINED range in 
> > the first place, and it's not update_value_range's job to fix that after 
> > the fact.
> 
> It is.  See how CCPs set_lattice_vlaue adjusts the input as well.

It actually does what I say update_value_range should do.  It _asserts_ a 
valid transition, and the fixup before is correctly marked with a ??? 
comment about the improperty of the place of such fixing up.

> It's just not convenient to repeat the adjustments everywhere.

Sure.  If the workers were correct there would be no need to do any 
adjustments.

> > > The workers only compute a new value-range
> > > for a stmt based on input value ranges.
> > 
> > And if they produce UNDEFINED when the input wasn't so, then _that's_ 
> > where the bug is.
> 
> See above.

Hmm?  See above.

> > I'm not sure I understand.  You claim that the workers have to produce 
> > UNDEFINED from non-UNDEFINED in some cases, otherwise we oscillate?  
> > That sounds strange.  Or do you mean that we oscillate without your 
> > patch to update_value_range?  That I believe, it's the natural result 
> > of going a lattice the wrong way, but I say that update_value_range is 
> > not the place to silently fix invalid transitions.
> 
> No, I mean that going up the lattice results in oscillation.

And that's why the workers are not supposed to do that.  They can't 
willy-nilly create new UNDEFINED/TOP lattice values.  Somehow we have a 
disconnect in this discussion over some very basic property, let's try to 
clean this up first.

So, one question, are you claiming that a VRP worker like this:

   VR derive_new_range_from_operation (VR a, VR b)

is _ever_ allowed to return UNDEFINED when a or b is something else than 
UNDEFINED?  You seem to claim so AFAIU, but at the same time admit that 
this results in oscillation, and hence needs fixing up in the routine that 
uses the above result to install the lattice value in the map.  I'm 
obviously saying that the above worker is not allowed to return UNDEFINED.


Ciao,
Michael.

Re: [PATCH] Fix PR55011

[Richard Biener]

On Mon, 22 Oct 2012, Michael Matz wrote:

> Hi,
> 
> On Mon, 22 Oct 2012, Richard Biener wrote:
> 
> > On Mon, 22 Oct 2012, Michael Matz wrote:
> > 
> > > Hi,
> > > 
> > > On Mon, 22 Oct 2012, Richard Biener wrote:
> > > 
> > > > 
> > > > This fixes PR55011, it seems nothing checks for invalid lattice
> > > > transitions in VRP,
> > > 
> > > That makes sense, because the individual parts of VRP that produce new 
> > > ranges are supposed to not generate invalid transitions.  So if anything 
> > > such checking should be an assert and the causes be fixed.
> > 
> > No, the checking should be done in update_value_range 
> 
> Exactly.  And that's the routine you're changing, but you aren't adding 
> checking, you silently "fix" invalid transitions.  What I tried to say 
> is that the one calling update_value_range with new_vr being UNDEFINED is 
> wrong, and update_value_range shouldn't fix it, but assert, so that this 
> wrong caller may be fixed.

Callers do not look at the lattice value they
change and it would not be convenient to do so in the various places.
I re-word your complaint to "the function has a wrong name" then,
which even I would not agree with.  update_value_range is told to
update the lattice value-range from lhs with the information from the 
given range.

> > which copies the new VR over to the lattice.  The job of that function 
> > is also to detect lattice changes.
> 
> Sure, but not to fix invalid input.

The input isn't invalid.  The input cannot be put into the lattice
just because that would be an invalid transition.

> > > > so the following adds that
> > > 
> > > It's a work around ...
> > 
> > No.
> > 
> > > > since we now can produce a lot more UNDEFINED than before
> > > 
> > > ... for this.  We should never "produce" UNDEFINED when the input wasn't 
> > > UNDEFINED already.
> > 
> > Why?
> 
> Because doing so _always_ means an invalid lattice transition.  UNDEFINED 
> is TOP, anything not UNDEFINED is not TOP.  So going from something to 
> UNDEFINED is always going upward the lattice and hence in the wrong 
> direction.

Um, what do you mean with "input" then?  Certainly intersecting
[2, 4] and [6, 8] yields UNDEFINED.  And the "input"s are not
UNDEFINED.

> > We shouldn't update the lattice this way, yes, but that is what
> > the patch ensures.
> 
> An assert ensures.  A work around works around a problem.  I say that the 
> problem is in those routines that produced the "new" UNDEFINED range in 
> the first place, and it's not update_value_range's job to fix that after 
> the fact.

It is.  See how CCPs set_lattice_vlaue adjusts the input as well.
It's just not convenient to repeat the adjustments everywhere.

> > The workers only compute a new value-range
> > for a stmt based on input value ranges.
> 
> And if they produce UNDEFINED when the input wasn't so, then _that's_ 
> where the bug is.

See above.

> > > > not doing so triggers issues.
> > > 
> > > Hmm?
> > 
> > It oscillates and thus never finishes.
> 
> I'm not sure I understand.  You claim that the workers have to produce 
> UNDEFINED from non-UNDEFINED in some cases, otherwise we oscillate?  That 
> sounds strange.  Or do you mean that we oscillate without your patch to 
> update_value_range?  That I believe, it's the natural result of going a 
> lattice the wrong way, but I say that update_value_range is not the place 
> to silently fix invalid transitions.

No, I mean that going up the lattice results in oscillation.

richard.

Re: [PATCH] Fix PR55011

[Michael Matz]

Hi,

On Mon, 22 Oct 2012, Richard Biener wrote:

> On Mon, 22 Oct 2012, Michael Matz wrote:
> 
> > Hi,
> > 
> > On Mon, 22 Oct 2012, Richard Biener wrote:
> > 
> > > 
> > > This fixes PR55011, it seems nothing checks for invalid lattice
> > > transitions in VRP,
> > 
> > That makes sense, because the individual parts of VRP that produce new 
> > ranges are supposed to not generate invalid transitions.  So if anything 
> > such checking should be an assert and the causes be fixed.
> 
> No, the checking should be done in update_value_range 

Exactly.  And that's the routine you're changing, but you aren't adding 
checking, you silently "fix" invalid transitions.  What I tried to say 
is that the one calling update_value_range with new_vr being UNDEFINED is 
wrong, and update_value_range shouldn't fix it, but assert, so that this 
wrong caller may be fixed.

> which copies the new VR over to the lattice.  The job of that function 
> is also to detect lattice changes.

Sure, but not to fix invalid input.

> > > so the following adds that
> > 
> > It's a work around ...
> 
> No.
> 
> > > since we now can produce a lot more UNDEFINED than before
> > 
> > ... for this.  We should never "produce" UNDEFINED when the input wasn't 
> > UNDEFINED already.
> 
> Why?

Because doing so _always_ means an invalid lattice transition.  UNDEFINED 
is TOP, anything not UNDEFINED is not TOP.  So going from something to 
UNDEFINED is always going upward the lattice and hence in the wrong 
direction.

> We shouldn't update the lattice this way, yes, but that is what
> the patch ensures.

An assert ensures.  A work around works around a problem.  I say that the 
problem is in those routines that produced the "new" UNDEFINED range in 
the first place, and it's not update_value_range's job to fix that after 
the fact.

> The workers only compute a new value-range
> for a stmt based on input value ranges.

And if they produce UNDEFINED when the input wasn't so, then _that's_ 
where the bug is.

> > > not doing so triggers issues.
> > 
> > Hmm?
> 
> It oscillates and thus never finishes.

I'm not sure I understand.  You claim that the workers have to produce 
UNDEFINED from non-UNDEFINED in some cases, otherwise we oscillate?  That 
sounds strange.  Or do you mean that we oscillate without your patch to 
update_value_range?  That I believe, it's the natural result of going a 
lattice the wrong way, but I say that update_value_range is not the place 
to silently fix invalid transitions.


Ciao,
Michael.

Re: [PATCH] Fix PR55011

[Richard Biener]

On Mon, 22 Oct 2012, Michael Matz wrote:

> Hi,
> 
> On Mon, 22 Oct 2012, Richard Biener wrote:
> 
> > 
> > This fixes PR55011, it seems nothing checks for invalid lattice
> > transitions in VRP,
> 
> That makes sense, because the individual parts of VRP that produce new 
> ranges are supposed to not generate invalid transitions.  So if anything 
> such checking should be an assert and the causes be fixed.

No, the checking should be done in update_value_range which copies
the new VR over to the lattice.  The job of that function is also
to detect lattice changes.

> > so the following adds that
> 
> It's a work around ...

No.

> > since we now can produce a lot more UNDEFINED than before
> 
> ... for this.  We should never "produce" UNDEFINED when the input wasn't 
> UNDEFINED already.

Why?  We shouldn't update the lattice this way, yes, but that is what
the patch ensures.  The workers only compute a new value-range
for a stmt based on input value ranges.

> > not doing so triggers issues.
> 
> Hmm?

It oscillates and thus never finishes.

Richard.

Re: [PATCH] Fix PR55011

[Michael Matz]

Hi,

On Mon, 22 Oct 2012, Richard Biener wrote:

> 
> This fixes PR55011, it seems nothing checks for invalid lattice
> transitions in VRP,

That makes sense, because the individual parts of VRP that produce new 
ranges are supposed to not generate invalid transitions.  So if anything 
such checking should be an assert and the causes be fixed.

> so the following adds that

It's a work around ...

> since we now can produce a lot more UNDEFINED than before

... for this.  We should never "produce" UNDEFINED when the input wasn't 
UNDEFINED already.

> not doing so triggers issues.

Hmm?


Ciao,
Michael.

[PATCH] Fix PR55011

[Richard Biener]

This fixes PR55011, it seems nothing checks for invalid lattice
transitions in VRP, so the following adds that since we now
can produce a lot more UNDEFINED than before not doing so triggers
issues.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.

Richard.

2012-10-22  Richard Biener  

PR tree-optimization/55011
* tree-vrp.c (update_value_range): For invalid lattice transitions
drop to VARYING.

* gcc.dg/torture/pr55011.c: New testcase.

Index: gcc/tree-vrp.c
===
*** gcc/tree-vrp.c  (revision 192671)
--- gcc/tree-vrp.c  (working copy)
*** update_value_range (const_tree var, valu
*** 819,826 
   || !vrp_bitmap_equal_p (old_vr->equiv, new_vr->equiv);
  
if (is_new)
! set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
!new_vr->equiv);
  
BITMAP_FREE (new_vr->equiv);
  
--- 819,837 
   || !vrp_bitmap_equal_p (old_vr->equiv, new_vr->equiv);
  
if (is_new)
! {
!   /* Do not allow transitions up the lattice.  The following
!  is slightly more awkward than just new_vr->type < old_vr->type
!because VR_RANGE and VR_ANTI_RANGE need to be considered
!the same.  We may not have is_new when transitioning to
!UNDEFINED or from VARYING.  */
!   if (new_vr->type == VR_UNDEFINED
! || old_vr->type == VR_VARYING)
!   set_value_range_to_varying (old_vr);
!   else
!   set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
!new_vr->equiv);
! }
  
BITMAP_FREE (new_vr->equiv);
  
Index: gcc/testsuite/gcc.dg/torture/pr55011.c
===
*** gcc/testsuite/gcc.dg/torture/pr55011.c  (revision 0)
--- gcc/testsuite/gcc.dg/torture/pr55011.c  (working copy)
***
*** 0 
--- 1,22 
+ /* { dg-do compile } */
+ 
+ char a;
+ 
+ void f(void)
+ {
+   char b = 2;
+ 
+   for(;;)
+ {
+   unsigned short s = 1, *p = &s, *i;
+ 
+   for(*i = 0; *i < 4; ++*i)
+   if(a | (*p /= (b += !!a)) <= 63739)
+ return;
+ 
+   if(!s)
+   a = 0;
+ 
+   for(;;);
+ }
+ }