Value Range Propagation Patch -- Part 2 of 2

[John Wehle]

> I'd make a distinction between correct and desired.

I agree with that there is a distinction.

> Regardless of the order of the basic blocks we should still get correct code.

The basic implementation can produce correct code without ordering the
basic blocks.  The current implementation actually makes use of knowing the
ordering to flow the current value range for some registers through the blocks
without having to wait for the next iteration.  Making use of knowledge about
the ordering was a design decision which reduces the number of iterations
required and produces more desirable results.

> Whether or not we get the desired code depends on a few factors like whether
> or not we do the optimistic initialization vs pessimistic initialization.

Currently pessimistic initialization is used and the desired result (for
the example in my earlier email) is attained through using knowledge of
the basic block ordering.  I'll have to think more on the issue of applying
optimistic initialization to value range propagation.

> My "objection" to bb ordering is that it shouldn't be necessary for
> correctness, only for possibly improving the compile time or compile speed
> and that I'd prefer to use more standard ways of dealing with issues than
> inventing new ones, the standard way to deal with the minimal vs maximal
> solution is tweaking the initial state or moving to a stronger algorithm
> for identifying and removing unreachable code like conditional constant
> propagation.

I certainly appreciate the basis of your objection and the concept of
favoring standard techniques is certainly a good one (non-standard techniques
make maintenance harder and are harder to characterize).  Making use of
the ordering wasn't required for correctness, however it does reduce the
number of iterations required and also improved the quality of the solution
(thus it appeared to be desirable).  I'll have to think more on how to
improve the quality of the solution by applying the techniques you mention
and without making use of knowledge about the ordering.

> If the code is not correct regardless of the ordering of blocks, then the
> implementation is wrong.

Umm ... there was a design decision made to order the blocks and to take
advantage of that ordering.  I'm not sure how the implementation can be
considered wrong if it currently depends on something it knows to be
true. :-)  If:

              for (rvrp = bb_reg_vr_table[bb]; rvrp; rvrp = rvrp->next)
                if (! TEST_BIT (bb_reg_vr_unknown[bb], rvrp->regno))
                  reg_vr_table[rvrp->regno] = rvrp->vr;

is removed from value_range_prop than the implementation will produce
correct code regardless of the ordering of the blocks, however it'll
require more iterations and in some cases produce less optimal results.

>> What do you see as things which need to happen in order for this to be
>> a useful addition to GCC?
>
> I already think it is.  Sorry if I wasn't explicit about that.  I'm just
> trying to work through why you did certain things and suggest alternatives
> if certain implementation decisions aren't what I expected given what I've
> read and know about some of this stuff.

Fair enough (and I do honestly appreciate the suggestions).  What I'm trying
to get clear in my mind is what I need to do in order for it make sense
to add this optimization to the source tree so that other people can take
advantage of it, beat up on it, and perhaps help improve it.  What it sounds
like is that you're still evaluating it and in the meantime I should look at
the pointers in your email to see if I can modify the implementation so that
it produces the desired results without using inside knowledge regarding the
ordering (which your gut tells you is unnecessary).  It also sounds like the
current approach isn't forbidden, it's just not desirable if I can find time
to come up with a more standard approach.

Do any other issues come to mind at the moment?  Some of the code style
issues were hopefully addressed in:

  Value Range Propagation Patch (Version 2)

which I emailed May 1.

-- John
-------------------------------------------------------------------------
|   Feith Systems  |   Voice: 1-215-646-8000  |  Email: john@feith.com  |
|    John Wehle    |     Fax: 1-215-540-5495  |                         |
-------------------------------------------------------------------------