[RFC] [parloop branch] Supporting reductions for automatic parallelization

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

Hi,

This is the patch I have to support simple reductions in the parloop 
branch.
I have not tested this patch yet, only ran it on the attached testcase.


Some notes:

One important remark is that the reductions I'm analyzing in this patch 
are only summation 
reductions (it is hard-coded in a few places, perhaps should be wrapped 
more nicely)

In the meantime I use vect_is_simple_reduction to recognize reductions. 
This is planned to be
implemented as a more generic utility, shared by auto vectorization and 
auto parallelization. 

A conflict I had was how to represent the reductions.
I decided on a per-loop representation. There should be a list of all 
reductions related to a loop.
I used a hashtable, but since typically there are only a few reductions 
per loop, maybe this is wasteful. 
the reduction list is a static variable that is cleared each time we're 
analyzing a new loop.

I added support for omp_atomic in the following places (except the obvious 
tree-parloops.c):
- Defined it as OMP_DIRECTIVE_P (tree.h)
- Added extend_omp_atomic () and added an omp region for omp_atomic 
(omp-low.c)
- Defined omp_atomic as a legal gimple statement (tree-gimple.c)
- Added a case for omp_atomic in get_expr_operands, currently it does 
nothing, but avoids failing 
   in assert for unknown cases.

Comments are welcome.
Razya

2007-08-16  Razya Ladelsky  <razya@il.ibm.com>

        * tree.h (OMP_DIRECTIVE_P): Add OMP_ATOMIC.
        * omp-low.c (expand_omp_atomic): New function.
          (expand_omp, build_omp_regions_1): Add support for OMP_ATOMIC.
        * tree-gimple.c (is_gimple_stmt): Add OMP_ATOMIC.
        * tree-parloops.c (reduction_info): New structure for reduction.
            (reduction_list): New list to represent list of reductions per 
loop.
          (reduction_info_hash, reduction_info_eq, initialize_reductions,
            create_call_for_reduction, 
            create_loads_and_stores_for_reduction): New functions.
          (loop_parallel_p): Identify reductions.
            (separate_decls_in_loop_name): Support reduction variables. 
            (separate_decls_in_loop): Add an argument, call 
            create_loads_and_stores_for_reduction for each reduction.
            (canonicalize_loop_ivs): Identify reductions.
            (transform_to_exit_first_loop): Add reduction support. Remove 
assert.
            (gen_parallel_loop): traverse reductions and call 
initialize_reductions, 
          same for create_call_for_reduction, call separate_decls_in_loop 
with 
          the new argument. 
            (parallelize_loops): Null the reduction list for each loop. 
        * tree-ssa-operands.c (get_expr_operands): Add a case for 
OMP_ATOMIC.

Attachment: reduction_diff
Description: Binary data

Attachment: parallelization-1.c
Description: Binary data