Re: [PATCH] Make VRP recognize range tests (unsigned)a + CST <= CST2

[Richard Guenther <rguenther at suse dot de>]

On Thu, 8 Feb 2007, Diego Novillo wrote:

> Richard Guenther wrote on 02/06/07 07:56:
> > This patch makes VRP recognize range and anti-range tests.  It does so
> > by allowing more flexible ASSERT_EXPRs (which is neccessary for the
> > anti-range case) like
> > 
> >  ASSERT_EXPR <a_1, (unsigned)a_1 + 5 > 13>
> > 
> > and derive ranges and anti-ranges from such directly.
> > 
> I don't really like where this is going.  VRP does not need more complexity.
> Though it triggers 30,000 times more, are there any perceivable benefits in
> runtime or code size?

See my followup mail - no earthshaking improvements.  But one would need
to test with bounds-checking code.

> Instead of supporting the more complex expression (unsigned)a_1 + 5 > 13
> why not convert that to a_1 > 8?  We certainly can ignore the cast.

That's not the same.  Consider the two cases in

int foo (int a)
{
  if (a > 8)
    return a < -5;
  if ((unsigned)a + 5 > 13)
    return a < -5;
}

in the second if () we can fold a < -5 to true because

  (unsigned)a + 5 > 13

is equivalent to

  if (a < -5 || a > 8)

in fact, the range folding in fold() folds the latter expression to

  if ((unsigned)a + 5 > 13)

if optimizing.

> One thing that I kind of liked about the patch is the extension to the idea of
> emitting ASSERTs  based on seemingly useless predicates.  In one of your
> testcases, we have:

Now this is exactly the point with the patch, to get back that
a < -5 || a > 8  predicate and register the anti-range associated with
it.

>    i.0_3 = (unsigned int) i_2(D);
>    D.1974_4 = i.0_3 + 4294967295;
>    D.1975_5 = D.1974_4 <= 4;
>    D.1976_7 = k_6(D) > 9;
>    D.1977_8 = D.1975_5 && D.1976_7;
>    if (D.1977_8) goto <L0>; else goto <L4>;
>  <L0>:;
>    if (k_15 <= 41) goto <L1>; else goto <L4>;
>  <L1>:;
>    k_14 = ASSERT_EXPR <k_15, k_15 <= 41>;
>    D.1978_9 = i_2(D) + k_14;
> 
> For i_2, your patch inserts:
> 
> i_14 = ASSERT_EXPR <i_2(D), (unsigned int) i_2(D) + 4294967295 <= 4>
> 
> since we are already working recursively at finding these comparisons, why not
> just canonicalize them?

Those are already canonicalized - with the other proposed but non-working
patch (it's attached in the PR) I tried to achieve the same by registering
two asserts, so doing

  if (a_1 < -5 || a_1 > 8)
    {
       a_2 = ASSERT_EXPR <a_1, a_1 < -5>
       a_3 = ASSERT_EXPR <a_2, a_2 > 8>
       ...
    }

and merge this special case (of assertions that contradict each other)
to an anti-range in extract_range_from_assert.  Unfortunately this breaks
down somehow (I didn't manage to isolate a testcase unfortunately).  For
range-tests this scheme of course works, like

  if (a_1 > -5 && a_1 < 8)
    {
      a_2 = ASSERT_EXPR <a_1, a_1 > -5 >
      a_3 = ASSERT_EXPR <a_2, a_2 < 8 >
      ...
    }
  else
    {
      ???  (same case as for the anti-range asserts)
    }

we can easily merge those two asserts in extract_range_from_assert.

I concluded that allowing the more complex expressions in ASSERT isn't
worse than registering two asserts.  The only thing is that I need
an extra field in struct assert_locus_d.

Note that the same scheme works for unsigned variables.

Thanks,
Richard.

-- 
Richard Guenther <rguenther@suse.de>
Novell / SUSE Labs