[PATCH] outer-loop parallelization support

[Razya Ladelsky <RAZYA at il dot ibm dot com>]

Hi,

This patch enables the parallelization of outer-loops.
For the analysis part, the changes were trivial: 
removing the innermost constraint for the analysis part, and  ignoring 
double reductions (will need extra support)
when considering reductions of outer loops.
The code generation part was a little trickier, as there were more forms 
of loops that 
are now being considered, and they needed special care. 
The  most interesting changes were in gimple_duplicate_sese_tail. 
I documented  these special cases in details in the code.

Bootstrap with autopar enabled passed successfully, and the testsuite 
(with autopar enabled)
showed no additional regressions. 
I tested also the libgomp.graphite suite, thereby exercised also 
graphite-autopar.
 
OK for mainline? 

Thanks,
Razya

2009-10-11  Razya Ladelsky  <razya@il.ibm.com>

        * cfgloopmanip.c  (duplicate_subloops): Export.
        * tree-parloops.c (loop_parallel_p): Dump if loop is innermost.
        (transform_to_exit_first_loop): Duplicate bbs starting from header 

        up to loop->latch instead of exit->src.
        Initialize control variable to the correct number of iterations.
        (gather_scalar_reductions): Do not register double reductions.
        (parallelize_loops): Dump which loop is tested. 
        Indicate whether the parallelized loop is inner or not. 
        Remove the innermost-loop requirement.
        * cfgloop.h (duplicate_subloops): Export.
        * tree-cfg.c (add_phi_args_after_redirect): New function.
        (bb_in_region): New function.
        (gimple_duplicate_sese_tail): Remove the no-subloops constraint.
        Call duplicate_subloops.
        Update number of iterations at the exit condition.
        Don't redirect nexits always to the loop exit. 
        Redirect copied edges from latch to the loop exit.
        * ../libgomp/testsuite/libgomp.graphite/force-parallel-2.c: Change 

        number of times "2 loops carried no dependency" appears in dump.
        * testsuite/gcc.dg/autopar/outer-1.c: New testcase.
        * testsuite/gcc.dg/autopar/outer-2.c: New testcase.

Attachment: outer-1.c
Description: Binary data

Attachment: outer-2.c
Description: Binary data

Attachment: autopar_outer.txt
Description: Text document