[patch] Predictive commoning, updated

[Dorit Nuzman]

Hi Zdenek,

First of all: Wow.

Second, about:
>    However, this second analysis delivers somewhat different results (it
>    only analyses the behavior of the memory reference in the innermost
>    loop, not any deeper loop nest);

this is something I just discovered in the context of outer-loop
vectorization, and that surprized me too. I thought the intention is that
find_data_references_in_loop(loop) would compute the DRs relative to the
loop in question, rather than always relative to the immediately containing
loop. We'd certainly need that for the outer-loop work. E.g., for the
following testcase (operating, say, on shorts):

      loop1: for (i=0; i<N; i++)
      loop2:     for (j=0; j<M; j+=4)
                     s += in[i+j];

the DR for in[i+j] when computed relative to the inner loop (by
find_data_references_in_loop(loop2)) would look roughly like this:
      DR_BASE:    &in
      DR_OFFSET:  i*2B
      DR_STEP:    16B

and the DR for in[i+j] when computed relative to the outer loop (by
find_data_references_in_loop(loop1)) would look roughly like this:
      DR_BASE:    &in
      DR_OFFSET:  0
      DR_STEP:    2B

I haven't looked into your patch yet, but from your description it sounds
like with this cleanup datarefs will always return the first DR above
(which is apparently what datarefs had also done before, unfortunately).
What are your thoughts on fixing/extending the datarefs analysis in that
direction? (is it easy/difficult, how would you envision doing that? I'd be
intersted in doing this, and would appreciate any thoughts/hints).

thanks!

dorit