Re: Simple Value Range Propagation

[Josef Zlomek <zlomj9am at artax dot karlin dot mff dot cuni dot cz>]

> 	I would like GCC to have a VRP optimization, but I still do not
> understand why the proposals always record such detailed, accurate
> information, which requires a slow, heavy-weight implementation.  I do not
> see it in other production compilers.

I do not see why my VRP is heavy-weight, it really is very simple.
Is 2% of compile time (measured on combine.c and insn-attrtab.c) too much?
It takes as much time as any data-flow problem using fast "hybrid search"
algorithm (faster than iterative dataflow).

When my VRP (completelly new, I have not seen the original VRP patches before)
sees a insn
(set (reg) (const_int)), it remembers the constant
(set (reg1) (reg2)) it copies the range
and for each BB which ends with a condition (returned by get_condition ())
it updates the ranges on the outgoing edges according to a condition,
for example
 (eq (reg1) (reg2))
    ----> then edge: range(reg1) = range(reg1) intersection range(reg2)

 (lt (reg1) (reg2)
    ----> then edge:
       range(reg1) = range(reg1)
                     intersect [-INF, MIN (higher(reg1),higher(reg2) - 1)]
       range(reg2) = range(reg2) 
                     intersect [MAX (lower(reg2, lower(reg1) + 1), INF]
    ----> else edge:
       range(reg1) = range(reg1)
                     intetrsec [MAX (lower(reg1), lower(reg2), INF]
       range(reg2) = range(reg2)
                     intetrsec [-INF, MIN (higher(reg1), higher(reg2)]

where lower(r) is the lower bound for r,
INF is infinity.

Example of code and what my VRP finds out:

for (i = 0; i < 1000; i++)
  CODE;
CODE2;

flowgraph:
   BB 0 .............. (i = 0)
    |
 >>BB 1 ............... ( i < 1000)
^   |  \
^  BB 2 \  ............. (CODE; i++)
\   |   |
 <</    |
        |
      BB 3 ................ (CODE2);

On the beginning, range for i (some pseudoregister) is [-INF,INF] (more
exactly: [min_val_for_type, max_val_for_type]

First iteration:
BB0 out: i = [0,0]
BB1 in:  i = [0,0] union [-inf,inf] = [-inf, inf]
BB1 out: i = [-inf, inf]
edge 1->2 (then edge):   [-inf, 999]
edge 1->3 (else edge):   [1000,inf]
BB2 in,out = [-inf,999]
BB3 in,out = [1000,inf]

Second (here the last) iteration:
BB1 in: i = [0,0] union [-inf, 999] = [-inf, 999]
BB1 out: i = [-inf,999]
the rest does not change so the data flow stops.

Regards,

Josef