[autovect] [patch] clean up latch blocks (+rfc)

[Dorit Naishlos]

Some loop optimization passes (like tree_if_conversion, tree_vectorize,
modulo-scheduling) require that loop latch block be empty. However there
are cases in which the loop latch block isn't empty although it could be.
In the testcase included in this patch, stmts are moved into an empty latch
block by 'pass_sink_code'.

Before sink:

<L6>:;
.....
  out1_29 = out1_63 + 4B;
  out2_30 = out2_64 + 4B;
  p1_31 = p1_61 + 2B;
  p2_32 = p2_62 + 2B;
  i_33 = i_65 + 1;
  if (i_33 <= 63) goto <L11>; else goto <L8>;

<L11>:;
  goto <bb 1> (<L0>);

After sink:

Sinking p2_32 = p2_62 + 2B from bb 7 to bb 9
Sinking p1_31 = p1_61 + 2B from bb 7 to bb 9
Sinking out2_30 = out2_64 + 4B from bb 7 to bb 9
Sinking out1_29 = out1_63 + 4B from bb 7 to bb 9

<L6>:;
....
  i_33 = i_65 + 1;
  if (i_33 <= 63) goto <L11>; else goto <L8>;

<L11>:;
  out1_29 = out1_63 + 4B;
  out2_30 = out2_64 + 4B;
  p1_31 = p1_61 + 2B;
  p2_32 = p2_62 + 2B;
  goto <bb 1> (<L0>);


To fix such situations, this patch scans the latch block of loops, and
checks if the latch block can be made empty. If so, it moves all stmts from
the latch block to the "last" block of the loop (just before the exit
condition). e.g.:

The loop before:
      loop_header:
            ....
      bb_in_loop:
            if (loop_exit_condition) goto exit, else goto latch
      latch:
            CODE
            goto loop_header
      exit:

The loop after:
      loop_header:
            ....
      bb_in_loop:
            CODE
            if (loop_exit_condition) goto exit, else goto latch
      latch:
            goto loop_header
      exit:

We do that if all the stmts of the latch block are used only inside the
loop (because moving them into the new location in the loop means that they
will be executed one extra time, which will affect the program only if the
stmts are actually used outside the loop, or if these stmts have other side
effects).

Questions:
1- Is there a more appropriate place to do this cleanup?
(Another option is maybe to not allow pass_sink_code to move code into the
latch block. The problem is that 1) pass_sink_code takes place before the
loop passes, so it's probably unaware that it's moving stmts into a loop
latch. 2) there might be other causes, other than pass_sink_code, for code
to appear in latch blocks?)

2- This patch was written as a quick work around for autovect-branch. What
would require to get it into mainline?

Bootstrapped with vectorization enabled on powerpc-linux, tested on the
vectorizer testcases. Committed to autovect-branch.

thanks,
dorit

        * tree-ssa-loop-manip.c (empty_latch_block): New function.
        * tree-ssa-loop.c (tree_ssa_loop_init): Call empty_latch_block.
        * tree-flow.h (empty_latch_block): New function declaration.

(See attached file: latchpatch.txt)
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: latchpatch.txt
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20051128/526ee159/attachment.txt>