Re: [RFC] propagating loop dependences from trees to RTL (for SMS)

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

> As a follow up to http://gcc.gnu.org/ml/gcc/2005-04/msg00461.html
> 
> I would like to improve SMS by passing data dependencies information
> computed in tree-level to rtl-level SMS. Currently data-dependency graph
> built for use by SMS has an edge for every two data references (i.e. it's
> too conservative). I want to check for every loop, using functions defined
> in tree-data-ref.c, if there are data dependencies in the loop. The problem
> is how to pass this information to SMS (note - we're only trying to convey
> whether there are no dependencies at all in the loop - i.e. one bit of
> information). The alternatives being considered are:
> 
> 1. Introduce a new BB bit flag and set it for the header BB of a loop that
> has no data dependencies. This approach already works, but only if the old
> loop optimizer (pass_loop_optimize) is disabled (otherwise the bit doesn't
> survive). One potential problem is that the loop header BB may change
> between the tree-level and SMS as result of some optimization pass (can
> that really happen?)

yes -- jump threading may change loop structures, although this is
fairly easy to prevent.  Loop optimizations can of course alter the
structure of loops, but they should be able to preserve this type of
informations.

> 2. Use a bitmap (as suggested in
> http://gcc.gnu.org/ml/gcc-patches/2005-03/msg01353.html) that is indexed
> using the BB index.  In my case I need to define and use the property within different
> functions. I can define a static function
>  "set_and_check_nodeps(bb_loop_header)" and define a bitmap there.
>  Like the previous solution, The problem that can arise is that some
> intermediate optimizations can change the header of the loop. By the way,
> is it guaranteed that a BB keeps the same index throught the entire
> compilation?

No -- basic blocks are "compacted" from time to time, to fill in holes
created by removal of dead blocks.  Also, basic block numbers might
change due to basic block splitting/merging in some optimizations.

> 3. Use insn_notes - introduce a new note "NOTE_INSN_NO_DEPS_IN_LOOP" to be
> inserted after the "NOTE_INSN_LOOP_BEG" for relevant loops.

NOTE_INSN_LOOP_BEG should most definitely disappear in 4.2, and
introducing insn notes seems like a bad idea to me.

> 4. Other ideas?

Preserving the information about loops throughout the optimizations, and
just keeping this information attached at the loop description would by
far be the cleanest approach -- admitedly also the one that requires the
greatest amount of work.

Zdenek