vrp?

[Daniel Berlin]

On Wednesday, February 12, 2003, at 02:03  AM, Steven Bosscher wrote:

> Op wo 12-02-2003, om 07:58 schreef Richard Henderson:
>> Any idea what the state of the last value-range propagation patch is?
>>
>> I've been looking at killing the cse-follow-jumps nonsense from cse.c,
>> and one case we're missing by removing it is
>>
>> 	if (x == 0)
>> 	  foo ();
>> 	else if (x == 0)
>> 	  bar ();
>>
>> The current cse code marks (x != 0) true on the else branch of the
>> first if.  But our current gcse code has no way to make (x = NOT(0))
>> available on an edge.
>>
>> I wouldn't think we'd need too terribly strong VRP to replace what
>> cse.c does now, but given how often this shows up within gcc source
>> itself I don't think I can kill what we have without a replacement.
>
> There's an ssa-based VRP algorithm[1] that I mentioned to Diego a while
> ago.  Basically it's an extension of sparse-CCP and it provides branch
> probablilities. Diego said it was on the TODO list with Redhat...  Does
> that help?

There's an even stronger algorithm that subsumes GVN, sparse CCP, does 
value/predicate inference,  and would handle this case easily:

The paper is titled "A Sparse Algorithm for Predicated Global Value 
Numbering" (it's misleading, since their algorithm does a lot more).
http://doi.acm.org/10.1145/512529.512536

Actually doesn't look too bad in pseudocode.

And hey, any algorithm that can determine:

01 routine R(integer X, integer Y , integer Z)
02 returns integer
03 I <- 1
04 J <-  1
05 while (true)
06 	if (J > 9) break
07 	J <- J + 1
08 	if (I != 1) I <- 2
09 	if (Y = X)
10 		P <- 0
11 		if (X >= 1)
12 			if (I != 1) P <- 2 else if (X <= 9) P <- I
13 		Q <- 0
14 		if (I <= Y )
15 		  if (9 >= Y ) Q <- 1
16 		if (Z > I)
17 		  I <- P + (X + 2) + (Z < 1) - (I + Y ) - Q
18 return (I)

always returns 1 is okay in my book
:)


> Greetz
> Steven
>
>
> [1] http://www.pattosoft.com.au/jason/Papers/ValueRangeProp/
>