Re: [4.5] Find more autoinc addressing for induction variables

[Steven Bosscher <stevenb dot gcc at gmail dot com>]

On Thu, May 14, 2009 at 1:16 AM, Bernd Schmidt <bernds_cb1@t-online.de> wrote:
>> Perhaps I missed it, but did you address Paolo's comment
>> (http://gcc.gnu.org/ml/gcc-patches/2009-02/msg00736.html), for example
>> by looking at what this does to compilation times?
>
> Paolo suggested enabling it at -O2 only. ?I'd be happy to make that change
> if someone wants to approve it under that condition. ?However, I was hoping
> for a more substantive review that goes towards approving or rejecting the
> patch.

+/* Try to detect situations where we have a loop, and one of the induction
+   variables can be used for autoincrement addressing.  We look for a control
+   flow graph that looks like this:
+      A
+      |
+      B <---\
+      |     |
+      ...   |
+      |     |
+      C ----/
+      |
+      ...
+   with arbitrary structure in the middle.  A must dominate B, which must
+   dominate C.
...
+   The final condition that must be satisfied is that there is no path from B
+   to B that does not go through either A or C, and likewise that there is no
+   path from C to C that does not go through A or B.  This ensures that before

If I understand this correctly, then the verify_path check is this the same as:
* A must dominate B
* B must dominate C
* C must post-dominate B

Calculating post-dominators is probably cheaper than this verify_path function.

But maybe you just want to do something easier, maybe using flow_loops_find.


> I'm puzzled that we were promised all this shiny new df infrastructure and
> now it's supposedly too expensive to use?

It's just an expensive problem, whether DF does it or you do it by
hand.  You've never been a fan of DF but there is no reason to pretend
being "puzzled" when you bloody well know how hard these problems are,
given some of your past work (regrename comes to mind ;-)

To calculate the chains for the whole function, when you really only
need it for induction variables, just makes me wonder if that's really
worth the cost.  Perhaps there is a simpler way.  Maybe the loop-iv.c
stuff, but I haven't looked in enough detail to tell...  Or since the
pass runs after pass_web (live range splitting for pseudos), you can
probably get away with just using reg-def and reg-use chains (which
are always available).

As it is, IMHO the pass looks very costly and the verify_path bits are
a bit confusing.

Ciao!
Steven