Richard Guenther - Re: [PATCH] Make VRP recognize range tests (unsigned)a + CST <= CST2 (original) (raw)

This is the mail archive of the gcc-patches@gcc.gnu.orgmailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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 ; else goto ; :; if (k_15 <= 41) goto ; else goto ; :; 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

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]