Re: Value Range Propagation Patch -- Part 2 of 2

[John Wehle <john at feith dot com>]

> 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. :-)

> 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'll change the style used in the code.

> 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.

> 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.

> 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.

> > +   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 returned.
Also get_jump_table_offset is only called when it's known that insn is a
table jump.

> I believe that you can also end up with a NULL table since we could have a
> jump to the last insn in the chain (that's how returns look early in
> rtl generation).

Not a problem since ! (table = NEXT_INSN (label)) tests for this condition
and will cause the rest of the "if" to be skipped and NULL_RTX to be returned.

> So the GET_CODE (table) might segfault in some cases.

I don't believe so.  See above.

> It might be better to write a series of simple conditionals rather than one
> large conditional.

If you feel strongly about this then I'll break it up.

> > +   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.

> Presumably the code later in that function is just trying to compute the
> original index if the value it finds isn't simple? 

Not exactly.  Get_jump_table_offset is trying to * locate * the RTL
expression which describes the offset into the jump table given the
jump insn as the starting point.  It understands the various RTL
sequences generated by the backends.  For example:

(note 216 199 201 [bb 1] NOTE_INSN_BASIC_BLOCK)

(insn 201 216 203 (set (reg:SI 27)
        (label_ref:SI 206)) 41 {*movsi_1} (nil)
    (expr_list:REG_LABEL (code_label 206 205 207 15 "" "" [2 uses])
        (expr_list:REG_EQUAL (label_ref:SI 206)
            (nil))))

(insn 203 201 204 (set (reg:SI 28)
        (mem/u:SI (plus:SI (mult:SI (reg/v:SI 26)
                    (const_int 4 [0x4]))
                (reg:SI 27)) 0)) 41 {*movsi_1} (nil)
    (nil))

(jump_insn 204 203 205 (parallel[ 
            (set (pc)
                (reg:SI 28))
            (use (label_ref 206))
        ] ) 475 {tablejump} (nil)
    (nil))

Starting with jump_insn 204 (which is the actual table jump) and working
backwards we discover that the jump (register 28) is calculated by adding
register 27 with 4 times register 26.  Looking at the contents of register
27 we find a label_ref which means that 4 times register 26 must be the
offset into the table.  (mult:SI (reg/v:SI 26) (const_int 4 [0x4])) will
be returned to record_value_range_jump which passes it to compute_value_range
in order to compute the actual offset.

> That function really does need some comments explaining what it is trying
> to do.  I can make educated guesses about it's behavior, but we're better
> off not leaving it to folks to guess the code's intent.

Agreed.

> > +   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. :-)

>> +   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.

-- John

PS: The posted patch no longer applies cleanly to the current tree in CVS.
    Let me known if you want a current version emailed to you.
-------------------------------------------------------------------------
|   Feith Systems  |   Voice: 1-215-646-8000  |  Email: john@feith.com  |
|    John Wehle    |     Fax: 1-215-540-5495  |                         |
-------------------------------------------------------------------------