Value Range Propagation Patch -- Part 2 of 2

[Jeffrey A Law]

  In message <200004130517.BAA29305@jwlab.FEITH.COM>you write:
  > > At a high level some comments at the start of vrp.c about how it works
  > > would b greatly appreciated.  I was able to figure most of it out by
  > > inspection, but it would have helped to have some high level overview
  > > of the optimization pass.
  > 
  > Agreed.  Things were dragging out so I figured I should post what I had
  > so to at least get some feedback as to how off base I might be. :-)
:( (things are dragging out)

:-)  Most of the base ideas seem good to me.


  > > Is there any reason to use *(table + index) instead of table[offset]?
  > 
  > No.  I just tend to use *(variable + offset) when variable is a pointer
  > and variable[offset] when variable is an array.  I take it that:
  > 
  >   reg_vr_table[prvrp->regno] = prvrp->vr;
  > 
  > is preferred over:
  > 
  >   *(reg_vr_table + prvrp->regno) = prvrp->vr;
I personally don't have a strong preference, but it appears that we tend to
use array notation quite a bit more often than pointer notion for this kind
of thing.

  > I'll change the style used in the code.
THanks.

  > > Presumably you're using tree nodes to record value ranges because you can
  > > then call into routines in fold-const.c and friends to do simplifications
  > ?
  > 
  > Yes.
OK.


  > > Any reason you didn't use fold_ranges/merge_ranges & friends?  It would
  > > require some tweaks, but might simplify the code.
  > 
  > I looked briefly at them, however it didn't look like a good fit.
OK.

  > > Did you give any thought to providing analogous routines in RTL?
  > 
  > Not a lot.  I don't know that the current RTL easily lends itself
  > to things like producing a result and overflow indicator when adding
  > two numbers.  The tree nodes seem the closest fit to the type of things
  > I was looking to do.
Ah, I hadn't thought about overflow issues.    FWIW, I wish I had thought
of the idea of jus building up a tree node for this stuff :-)  I could have
used it a couple years ago to solve an unpleasant problem on of Cygnus's
customers ran into.


  > > > +   if (GET_CODE (insn) != JUMP_INSN
  > > > +       || ! (label = JUMP_LABEL (insn))
  > > > +       || ! (table = NEXT_INSN (label))
  > > > +       || GET_CODE (table) != JUMP_INSN
  > > > +       || (GET_CODE (PATTERN (table)) != ADDR_VEC
  > > > + 	  && GET_CODE (PATTERN (table)) != ADDR_DIFF_VEC)
  > > > +       || ! (set = single_set (insn)))
  > > > +     return NULL_RTX;
  > >
  > > Few notes.  It is possible for JUMP_LABEL to be null.  For example a
  > > return insn will have a null jump label.
  > 
  > Not a problem since ! (label = JUMP_LABEL (insn)) tests for this condition
  > and will cause the rest of the "if" to be skipped and NULL_RTX to be return
  > ed.
Doh! :-)

  > > It might be better to write a series of simple conditionals rather than o
  > ne
  > > large conditional.
  > 
  > If you feel strongly about this then I'll break it up.
As a general rule, yes.  What makes me lean that direction was what happened
to jump.c -- we ended up with conditionals that were more than a page long
and impossible to unravel (which is one reason I'm *so* happy with the new
if conversion code Richard wrote).

  > > > +   x = SET_SRC (set);
  > > > + 
  > > > +   if (GET_CODE (x) == IF_THEN_ELSE
  > > > +       && GET_CODE (XEXP (x, 2)) == LABEL_REF)
  > > > +     x = XEXP (x, 1);
  > > > + 
  > > > +   for (old_x = NULL_RTX; GET_CODE (x) == REG && x != old_x;
  > > > +        old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0))
  > > > +     ;
  > >
  > > Presumably you're trying to find the register that holds the index with
  > > this code?  A comment might make the intent of this code clearer.
  > 
  > Not so much with this code specifically.  More so with the entire routine.
OK, then you might have comments explaining the steps you're taking towards
that goal.  You might use the explanation you gave me in your response as
a starting point.


  > 
  > > > +   abnormal = (int *)alloca(n_basic_blocks * sizeof(int));
  > > > +   ignore = (int *)alloca(n_basic_blocks * sizeof(int));
  > > > +   order = (int *)alloca(n_basic_blocks * sizeof(int));
  > > > +   visited = (int *)alloca(n_basic_blocks * sizeof(int));
  > >
  > > Whitespace between the function name and the open paren for its argument
  > > list.
  > 
  > Whoops.  Sorry.
  > 
  > > We're also trying to avoid alloca, so using an xmalloc + free pair
  > > would probably be better.
  > 
  > Didn't realize that.  I thought alloca was okay if the amount of memory
  > was likely to be reasonable (though I guess that begs the question of
  > what is reasonable. :-)
:-)  We decided things scaled based on n_basic_blocks wasn't reasonable :-)


  > >> +   compute_value_range_bb_order (order, abnormal, dom);
  > > I doubt this is really necessary.  Or more correctly I doubt ordering of
  > > basic blocks is all that important to most code.  It can be shown that
  > > the number of iterations of a dataflow problem is bounded by the nesting
  > > of backedges in the cfg.
  > 
  > Initially I didn't order the blocks, however during the development cycle
  > it appeared that ordering the blocks with the current algorithm simplified
  > certain things.  I'll re-examine this issue and get back to you.
You might look at the patch recently posted to speed up one of Brad's
testcases.  I can see how topo sorts might speed up the convergence of
dataflow, but I don't see how it necessarily simplifies things.  Presumably
I need to read the code more closely.

FWIW, I'd been assuming you were using iterative dataflow analysis to 
propagate range information around the CFG.  I need to double check and
see if that's indeed what you're doing.

jeff