Re: Value Range Propagation Pass Status

[Jeffrey A Law <law at cygnus dot com>]

  In message <200002040035.TAA22792@jwlab.FEITH.COM>you write:
  > I've been working on a pass (when time has allowed :-) to track
  > and make use of value ranges associated with pseudo registers.
Cool.


  > I have reasonably solid code which bootstraps on alpha, i386,
  > powerpc, and sparc.  Make check has been run on i386, powerpc,
  > and sparc with no regression.  A slightly older version of the
  > code was bootstrapped on hppa and make check ran with no regressions.
Even better.


  > Things to do before submitting:
  > 
  >   1) Currently the code exists as a patch to gcse.c and runs as part of gcs
  > e.
  >      It needs to exist on its own and be moved into a seperate file.  Any
  >      recommendations on when value range propagation should be done?  I was
  >      thinking of running it twice.  Once before gcse and once after loop.
I'd suggest running it just before or just after gcse.

In those cases where value range propagation is useful it is usually going
to be removing unnecessary conditional branches and shrinking the span of
a tablejump.

Removing branches like this is generally going to help basic block optimizers
like local cse, scheduling, combine, etc.  Thus we want it to run before our
last local cse pass.

I doubt there's much benefit in running it twice.  I suspect we can get 99%
of the benefit by running it once, probably before loop.

  >   2) The code needs documentation.
Always important.

  >   3) Possibly handle some additional cases.
What's most important at this phase is to have a code base that we can
understand and easily extend.  Ultimately the kind of question we want to
be able to answer is:

  What are the possible values pseudo X can have at the end of block BB?

There are cases where we'd want that information at the insn level, but
those are relatively rare I suspect (and can be derived from the info we
compute for the start/end of a basic block).

Once we can answer those questions we need to be able to make decisions
based on that information.   ie, given pseudo X has a set of potential values
S, is there any value in S that satisfies some condition C (for example, is
there a value in S that satisfies X > 5?).

  >   4) Some of the backend casesi patterns could use tweaking in order to
  >      allow the value range pass to determine what cases will never be
  >      reached.
  > 
  > Actually, items 3 and 4 can probably be done after submitting the current
  > code.  If there's interest I can post the existing code so that people can
  > kick the tires and comment.
Agreed. 

You might find additional simple examples of code which can be helped
by value range propagation at the nullstone site.  I also vaguely remember
a series of papers on value range propagation, possible from the compiler
group at Rice.
jeff