diff options
| -rw-r--r-- | gcc/ChangeLog | 39 | ||||
| -rw-r--r-- | gcc/Makefile.in | 6 | ||||
| -rw-r--r-- | gcc/builtins.def | 3 | ||||
| -rw-r--r-- | gcc/common.opt | 4 | ||||
| -rw-r--r-- | gcc/doc/invoke.texi | 10 | ||||
| -rw-r--r-- | gcc/doc/passes.texi | 3 | ||||
| -rw-r--r-- | gcc/omp-low.c | 46 | ||||
| -rw-r--r-- | gcc/passes.c | 1 | ||||
| -rw-r--r-- | gcc/testsuite/ChangeLog | 4 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/parallelization-1.c | 33 | ||||
| -rw-r--r-- | gcc/timevar.def | 1 | ||||
| -rw-r--r-- | gcc/tracer.c | 2 | ||||
| -rw-r--r-- | gcc/tree-cfg.c | 287 | ||||
| -rw-r--r-- | gcc/tree-flow.h | 8 | ||||
| -rw-r--r-- | gcc/tree-parloops.c | 1148 | ||||
| -rw-r--r-- | gcc/tree-pass.h | 1 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-manip.c | 6 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop.c | 36 | ||||
| -rw-r--r-- | gcc/tree-ssa-operands.c | 50 | ||||
| -rw-r--r-- | gcc/tree-ssa-operands.h | 1 |
20 files changed, 1635 insertions, 54 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 2f6520faa3b..20731824010 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,42 @@ +2007-09-15 Zdenek Dvorak <ook@ucw.cz> + + * tree-parloops.c: New file. + * tree-ssa-operands.h (free_stmt_operands): Declare. + * tree-ssa-loop-manip.c (split_loop_exit_edge): Return the new basic + block. + * tree-pass.h (pass_parallelize_loops): Declare. + * omp-low.c (expand_omp_parallel, expand_omp_for): Update SSA form for + virtual operands. + (build_omp_regions_1): Allow analysing just a single OMP region and + its subregions. + ( build_omp_regions_root, omp_expand_local): New functions. + (build_omp_regions): Add argument to build_omp_regions_1 call. + * builtins.def (DEF_GOMP_BUILTIN): Initialize OMP builtins when + autoparallelization is run. + * timevar.def (TV_TREE_PARALLELIZE_LOOPS): New. + * tree-ssa-loop.c (gate_tree_parallelize_loops, tree_parallelize_loops, + pass_parallelize_loops): New. + * common.opt (ftree-parallelize-loops): New. + * tree-flow.h (omp_expand_local, tree_duplicate_sese_tail, + parallelize_loops): Declare. + (add_phi_args_after_copy, split_loop_exit_edge): Declaration changed. + * Makefile.in (tree-parloops.o): Added. + * tree-cfg.c (add_phi_args_after_copy_edge, tree_duplicate_sese_tail): + New functions. + (add_phi_args_after_copy_bb): Use add_phi_args_after_copy_edge. + (add_phi_args_after_copy): Call add_phi_args_after_copy_edge for + one extra edge as well. + (tree_duplicate_sese_region): Add argument to add_phi_args_after_copy. + Use VEC_free to free doms vector. + (move_block_to_fn): Update loop info. Remove phi nodes for virtual + operands. Recompute operand caches in the new function. + (move_sese_region_to_fn): Update loop info. + * passes.c (init_optimization_passes): Add pass_parallelize_loops. + * tree-ssa-operands.c (free_stmt_operands): New function. + + * doc/passes.texi: Document autoparallelization. + * doc/invoke.texi (-ftree-parallelize-loops): New option. + 2007-09-15 John David Anglin <dave.anglin@nrc-cnrc.gc.ca> PR target/33062 diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 4069f79288c..2e522d59931 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1153,6 +1153,7 @@ OBJS-common = \ tree-object-size.o \ tree-optimize.o \ tree-outof-ssa.o \ + tree-parloops.o \ tree-phinodes.o \ tree-predcom.o \ tree-pretty-print.o \ @@ -2270,6 +2271,9 @@ tree-loop-linear.o: tree-loop-linear.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \ $(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \ tree-pass.h $(TREE_DATA_REF_H) $(SCEV_H) $(EXPR_H) $(LAMBDA_H) \ $(TARGET_H) tree-chrec.h $(OBSTACK_H) +tree-parloops.o: tree-parloops.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ + $(TREE_FLOW_H) $(TREE_H) $(RTL_H) $(CFGLOOP_H) $(TREE_DATA_REF_H) $(GGC_H) \ + $(DIAGNOSTIC_H) tree-pass.h $(SCEV_H) langhooks.h gt-tree-parloops.h tree-stdarg.o: tree-stdarg.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ $(TREE_H) $(FUNCTION_H) $(DIAGNOSTIC_H) $(TREE_FLOW_H) tree-pass.h \ tree-stdarg.h $(TARGET_H) langhooks.h @@ -3091,7 +3095,7 @@ GTFILES = $(srcdir)/input.h $(srcdir)/coretypes.h \ $(srcdir)/tree-ssa-operands.h \ $(srcdir)/tree-profile.c $(srcdir)/tree-nested.c \ $(srcdir)/ipa-reference.c $(srcdir)/tree-ssa-structalias.h \ - $(srcdir)/tree-ssa-structalias.c \ + $(srcdir)/tree-ssa-structalias.c $(srcdir)/tree-parloops.c \ $(srcdir)/omp-low.c $(srcdir)/varpool.c \ $(srcdir)/targhooks.c $(out_file) $(srcdir)/passes.c $(srcdir)/cgraphunit.c \ @all_gtfiles@ diff --git a/gcc/builtins.def b/gcc/builtins.def index b8b739b6bc5..c3c8b2fa351 100644 --- a/gcc/builtins.def +++ b/gcc/builtins.def @@ -139,7 +139,8 @@ along with GCC; see the file COPYING3. If not see #undef DEF_GOMP_BUILTIN #define DEF_GOMP_BUILTIN(ENUM, NAME, TYPE, ATTRS) \ DEF_BUILTIN (ENUM, "__builtin_" NAME, BUILT_IN_NORMAL, TYPE, TYPE, \ - false, true, true, ATTRS, false, flag_openmp) + false, true, true, ATTRS, false, \ + (flag_openmp || flag_tree_parallelize_loops)) /* Define an attribute list for math functions that are normally "impure" because some of them may write into global memory for diff --git a/gcc/common.opt b/gcc/common.opt index 909c57bf0ac..4d9f9b85e4d 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -1088,6 +1088,10 @@ ftree-loop-optimize Common Report Var(flag_tree_loop_optimize) Init(1) Optimization Enable loop optimizations on tree level +ftree-parallelize-loops= +Common Report Joined UInteger Var(flag_tree_parallelize_loops) Init(1) +Enable automatic parallelization of loops + ftree-pre Common Report Var(flag_tree_pre) Optimization Enable SSA-PRE optimization on trees diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index af58bfeb86e..228be529505 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -358,7 +358,7 @@ Objective-C and Objective-C++ Dialects}. -fvariable-expansion-in-unroller -ftree-reassoc @gol -ftree-pre -ftree-ccp -ftree-dce -ftree-loop-optimize @gol -ftree-loop-linear -ftree-loop-im -ftree-loop-ivcanon -fivopts @gol --fcheck-data-deps @gol +-fcheck-data-deps -ftree-parallelize-loops @gol -ftree-dominator-opts -ftree-dse -ftree-copyrename -ftree-sink @gol -ftree-ch -ftree-sra -ftree-ter -ftree-fre -ftree-vectorize @gol -ftree-vect-loop-version -fvect-cost-model -ftree-salias -fipa-pta -fweb @gol @@ -5744,6 +5744,14 @@ in connection with unrolling. Perform induction variable optimizations (strength reduction, induction variable merging and induction variable elimination) on trees. +@item -ftree-parallelize-loops=n +@opindex ftree-parallelize-loops=n +Parallelize loops, i.e., split their iteration space to run in n threads. +This is only possible for loops whose iterations are independent +and can be arbitrarily reordered. The optimization is only +profitable on multiprocessor machines, for loops that are CPU-intensive, +rather than constrained e.g. by memory bandwidth. + @item -ftree-sra Perform scalar replacement of aggregates. This pass replaces structure references with scalars to prevent committing structures to memory too diff --git a/gcc/doc/passes.texi b/gcc/doc/passes.texi index b4eef6047b3..2f354394e99 100644 --- a/gcc/doc/passes.texi +++ b/gcc/doc/passes.texi @@ -438,6 +438,9 @@ The pass is implemented in @file{tree-vectorizer.c} (the main driver and general utilities), @file{tree-vect-analyze.c} and @file{tree-vect-transform.c}. Analysis of data references is in @file{tree-data-ref.c}. +Autoparallelization. This pass splits the loop iteration space to run +into several threads. The pass is implemented in @file{tree-parloops.c}. + @item Tree level if-conversion for vectorizer This pass applies if-conversion to simple loops to help vectorizer. diff --git a/gcc/omp-low.c b/gcc/omp-low.c index 57f36509c67..421b5c62863 100644 --- a/gcc/omp-low.c +++ b/gcc/omp-low.c @@ -2600,6 +2600,7 @@ expand_omp_parallel (struct omp_region *region) /* Emit a library call to launch the children threads. */ expand_parallel_call (region, new_bb, entry_stmt, ws_args); + update_ssa (TODO_update_ssa_only_virtuals); } @@ -3282,6 +3283,8 @@ expand_omp_for (struct omp_region *region) int next_ix = BUILT_IN_GOMP_LOOP_STATIC_NEXT + fn_index; expand_omp_for_generic (region, &fd, start_ix, next_ix); } + + update_ssa (TODO_update_ssa_only_virtuals); } @@ -3591,10 +3594,13 @@ expand_omp (struct omp_region *region) /* Helper for build_omp_regions. Scan the dominator tree starting at - block BB. PARENT is the region that contains BB. */ + block BB. PARENT is the region that contains BB. If SINGLE_TREE is + true, the function ends once a single tree is built (otherwise, whole + forest of OMP constructs may be built). */ static void -build_omp_regions_1 (basic_block bb, struct omp_region *parent) +build_omp_regions_1 (basic_block bb, struct omp_region *parent, + bool single_tree) { block_stmt_iterator si; tree stmt; @@ -3643,12 +3649,44 @@ build_omp_regions_1 (basic_block bb, struct omp_region *parent) } } + if (single_tree && !parent) + return; + for (son = first_dom_son (CDI_DOMINATORS, bb); son; son = next_dom_son (CDI_DOMINATORS, son)) - build_omp_regions_1 (son, parent); + build_omp_regions_1 (son, parent, single_tree); +} + +/* Builds the tree of OMP regions rooted at ROOT, storing it to + root_omp_region. */ + +static void +build_omp_regions_root (basic_block root) +{ + gcc_assert (root_omp_region == NULL); + build_omp_regions_1 (root, NULL, true); + gcc_assert (root_omp_region != NULL); } +/* Expands omp construct (and its subconstructs) starting in HEAD. */ + +void +omp_expand_local (basic_block head) +{ + build_omp_regions_root (head); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\nOMP region tree\n\n"); + dump_omp_region (dump_file, root_omp_region, 0); + fprintf (dump_file, "\n"); + } + + remove_exit_barriers (root_omp_region); + expand_omp (root_omp_region); + + free_omp_regions (); +} /* Scan the CFG and build a tree of OMP regions. Return the root of the OMP region tree. */ @@ -3658,7 +3696,7 @@ build_omp_regions (void) { gcc_assert (root_omp_region == NULL); calculate_dominance_info (CDI_DOMINATORS); - build_omp_regions_1 (ENTRY_BLOCK_PTR, NULL); + build_omp_regions_1 (ENTRY_BLOCK_PTR, NULL, false); } diff --git a/gcc/passes.c b/gcc/passes.c index 0bcb7c7b302..74f48a83401 100644 --- a/gcc/passes.c +++ b/gcc/passes.c @@ -629,6 +629,7 @@ init_optimization_passes (void) NEXT_PASS (pass_dce_loop); } NEXT_PASS (pass_complete_unroll); + NEXT_PASS (pass_parallelize_loops); NEXT_PASS (pass_loop_prefetch); NEXT_PASS (pass_iv_optimize); NEXT_PASS (pass_tree_loop_done); diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 073027f0ecf..a46d3355eb1 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2007-09-15 Zdenek Dvorak <ook@ucw.cz> + + * gcc.dg/tree-ssa/parallelization-1.c: New test. + 2007-09-15 Dorit Nuzman <dorit@il.ibm.com> * gcc.dg/vect/pr33373b.c: New test. diff --git a/gcc/testsuite/gcc.dg/tree-ssa/parallelization-1.c b/gcc/testsuite/gcc.dg/tree-ssa/parallelization-1.c new file mode 100644 index 00000000000..ee62ff666b8 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/parallelization-1.c @@ -0,0 +1,33 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -ftree-parallelize-loops=4 -fdump-tree-parloops-details -fdump-tree-final_cleanup" } */ + +void abort (void); + +void parloop (int N) +{ + int i; + int x[10000000]; + + for (i = 0; i < N; i++) + x[i] = i + 3; + + for (i = 0; i < N; i++) + { + if (x[i] != i + 3) + abort (); + } +} + +int main(void) +{ + parloop(10000000); + + return 0; +} + +/* Check that the first loop in parloop got parallelized. */ + +/* { dg-final { scan-tree-dump-times "SUCCESS: may be parallelized" 1 "parloops" } } */ +/* { dg-final { scan-tree-dump-times "loopfn" 5 "final_cleanup" } } */ +/* { dg-final { cleanup-tree-dump "parloops" } } */ +/* { dg-final { cleanup-tree-dump "final_cleanup" } } */ diff --git a/gcc/timevar.def b/gcc/timevar.def index a2d73b3205e..e503894677b 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -120,6 +120,7 @@ DEFTIMEVAR (TV_TREE_LOOP_IVCANON , "tree canonical iv") DEFTIMEVAR (TV_SCEV_CONST , "scev constant prop") DEFTIMEVAR (TV_TREE_LOOP_UNSWITCH , "tree loop unswitching") DEFTIMEVAR (TV_COMPLETE_UNROLL , "complete unrolling") +DEFTIMEVAR (TV_TREE_PARALLELIZE_LOOPS, "tree parallelize loops") DEFTIMEVAR (TV_TREE_VECTORIZATION , "tree vectorization") DEFTIMEVAR (TV_TREE_LINEAR_TRANSFORM , "tree loop linear") DEFTIMEVAR (TV_CHECK_DATA_DEPS , "tree check data dependences") diff --git a/gcc/tracer.c b/gcc/tracer.c index ca505490639..e82238201fe 100644 --- a/gcc/tracer.c +++ b/gcc/tracer.c @@ -310,7 +310,7 @@ tail_duplicate (void) copy = duplicate_block (bb2, e, bb); flush_pending_stmts (e); - add_phi_args_after_copy (©, 1); + add_phi_args_after_copy (©, 1, NULL); /* Reconsider the original copy of block we've duplicated. Removing the most common predecessor may make it to be diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index e41307b6ed5..3de20cc57e6 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -5009,6 +5009,52 @@ tree_duplicate_bb (basic_block bb) return new_bb; } +/* Adds phi node arguments for edge E_COPY after basic block duplication. */ + +static void +add_phi_args_after_copy_edge (edge e_copy) +{ + basic_block bb, bb_copy = e_copy->src, dest; + edge e; + edge_iterator ei; + tree phi, phi_copy, phi_next, def; + + if (!phi_nodes (e_copy->dest)) + return; + + bb = bb_copy->flags & BB_DUPLICATED ? get_bb_original (bb_copy) : bb_copy; + + if (e_copy->dest->flags & BB_DUPLICATED) + dest = get_bb_original (e_copy->dest); + else + dest = e_copy->dest; + + e = find_edge (bb, dest); + if (!e) + { + /* During loop unrolling the target of the latch edge is copied. + In this case we are not looking for edge to dest, but to + duplicated block whose original was dest. */ + FOR_EACH_EDGE (e, ei, bb->succs) + { + if ((e->dest->flags & BB_DUPLICATED) + && get_bb_original (e->dest) == dest) + break; + } + + gcc_assert (e != NULL); + } + + for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest); + phi; + phi = phi_next, phi_copy = PHI_CHAIN (phi_copy)) + { + phi_next = PHI_CHAIN (phi); + def = PHI_ARG_DEF_FROM_EDGE (phi, e); + add_phi_arg (phi_copy, def, e_copy); + } +} + /* Basic block BB_COPY was created by code duplication. Add phi node arguments for edges going out of BB_COPY. The blocks that were @@ -5017,54 +5063,23 @@ tree_duplicate_bb (basic_block bb) void add_phi_args_after_copy_bb (basic_block bb_copy) { - basic_block bb, dest; - edge e, e_copy; edge_iterator ei; - tree phi, phi_copy, phi_next, def; - - bb = get_bb_original (bb_copy); + edge e_copy; FOR_EACH_EDGE (e_copy, ei, bb_copy->succs) { - if (!phi_nodes (e_copy->dest)) - continue; - - if (e_copy->dest->flags & BB_DUPLICATED) - dest = get_bb_original (e_copy->dest); - else - dest = e_copy->dest; - - e = find_edge (bb, dest); - if (!e) - { - /* During loop unrolling the target of the latch edge is copied. - In this case we are not looking for edge to dest, but to - duplicated block whose original was dest. */ - FOR_EACH_EDGE (e, ei, bb->succs) - if ((e->dest->flags & BB_DUPLICATED) - && get_bb_original (e->dest) == dest) - break; - - gcc_assert (e != NULL); - } - - for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest); - phi; - phi = phi_next, phi_copy = PHI_CHAIN (phi_copy)) - { - phi_next = PHI_CHAIN (phi); - def = PHI_ARG_DEF_FROM_EDGE (phi, e); - add_phi_arg (phi_copy, def, e_copy); - } + add_phi_args_after_copy_edge (e_copy); } } /* Blocks in REGION_COPY array of length N_REGION were created by duplication of basic blocks. Add phi node arguments for edges - going from these blocks. */ + going from these blocks. If E_COPY is not NULL, also add + phi node arguments for its destination.*/ void -add_phi_args_after_copy (basic_block *region_copy, unsigned n_region) +add_phi_args_after_copy (basic_block *region_copy, unsigned n_region, + edge e_copy) { unsigned i; @@ -5073,6 +5088,8 @@ add_phi_args_after_copy (basic_block *region_copy, unsigned n_region) for (i = 0; i < n_region; i++) add_phi_args_after_copy_bb (region_copy[i]); + if (e_copy) + add_phi_args_after_copy_edge (e_copy); for (i = 0; i < n_region; i++) region_copy[i]->flags &= ~BB_DUPLICATED; @@ -5210,10 +5227,180 @@ tree_duplicate_sese_region (edge entry, edge exit, set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src); VEC_safe_push (basic_block, heap, doms, get_bb_original (entry->dest)); iterate_fix_dominators (CDI_DOMINATORS, doms, false); - free (doms); + VEC_free (basic_block, heap, doms); /* Add the other PHI node arguments. */ - add_phi_args_after_copy (region_copy, n_region); + add_phi_args_after_copy (region_copy, n_region, NULL); + + /* Update the SSA web. */ + update_ssa (TODO_update_ssa); + + if (free_region_copy) + free (region_copy); + + free_original_copy_tables (); + return true; +} + +/* Duplicates REGION consisting of N_REGION blocks. The new blocks + are stored to REGION_COPY in the same order in that they appear + in REGION, if REGION_COPY is not NULL. ENTRY is the entry to + the region, EXIT an exit from it. The condition guarding EXIT + is moved to ENTRY. Returns true if duplication succeeds, false + otherwise. + + For example, + + some_code; + if (cond) + A; + else + B; + + is transformed to + + if (cond) + { + some_code; + A; + } + else + { + some_code; + B; + } +*/ + +bool +tree_duplicate_sese_tail (edge entry, edge exit, + basic_block *region, unsigned n_region, + basic_block *region_copy) +{ + unsigned i; + bool free_region_copy = false; + struct loop *loop = exit->dest->loop_father; + struct loop *orig_loop = entry->dest->loop_father; + basic_block switch_bb, entry_bb, nentry_bb; + VEC (basic_block, heap) *doms; + int total_freq = 0, exit_freq = 0; + gcov_type total_count = 0, exit_count = 0; + edge exits[2], nexits[2], e; + block_stmt_iterator bsi; + tree cond; + edge sorig, snew; + + gcc_assert (EDGE_COUNT (exit->src->succs) == 2); + exits[0] = exit; + exits[1] = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit); + + if (!can_copy_bbs_p (region, n_region)) + return false; + + /* Some sanity checking. Note that we do not check for all possible + missuses of the functions. I.e. if you ask to copy something weird + (e.g., in the example, if there is a jump from inside to the middle + of some_code, or come_code defines some of the values used in cond) + it will work, but the resulting code will not be correct. */ + for (i = 0; i < n_region; i++) + { + /* We do not handle subloops, i.e. all the blocks must belong to the + same loop. */ + if (region[i]->loop_father != orig_loop) + return false; + + if (region[i] == orig_loop->latch) + return false; + } + + initialize_original_copy_tables (); + set_loop_copy (orig_loop, loop); + + if (!region_copy) + { + region_copy = XNEWVEC (basic_block, n_region); + free_region_copy = true; + } + + gcc_assert (!need_ssa_update_p ()); + + /* Record blocks outside the region that are dominated by something + inside. */ + doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region); + + if (exit->src->count) + { + total_count = exit->src->count; + exit_count = exit->count; + /* Fix up corner cases, to avoid division by zero or creation of negative + frequencies. */ + if (exit_count > total_count) + exit_count = total_count; + } + else + { + total_freq = exit->src->frequency; + exit_freq = EDGE_FREQUENCY (exit); + /* Fix up corner cases, to avoid division by zero or creation of negative + frequencies. */ + if (total_freq == 0) + total_freq = 1; + if (exit_freq > total_freq) + exit_freq = total_freq; + } + + copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop, + split_edge_bb_loc (exit)); + if (total_count) + { + scale_bbs_frequencies_gcov_type (region, n_region, + total_count - exit_count, + total_count); + scale_bbs_frequencies_gcov_type (region_copy, n_region, exit_count, + total_count); + } + else + { + scale_bbs_frequencies_int (region, n_region, total_freq - exit_freq, + total_freq); + scale_bbs_frequencies_int (region_copy, n_region, exit_freq, total_freq); + } + + /* Create the switch block, and put the exit condition to it. */ + entry_bb = entry->dest; + nentry_bb = get_bb_copy (entry_bb); + if (!last_stmt (entry->src) + || !stmt_ends_bb_p (last_stmt (entry->src))) + switch_bb = entry->src; + else + switch_bb = split_edge (entry); + set_immediate_dominator (CDI_DOMINATORS, nentry_bb, switch_bb); + + bsi = bsi_last (switch_bb); + cond = last_stmt (exit->src); + gcc_assert (TREE_CODE (cond) == COND_EXPR); + bsi_insert_after (&bsi, unshare_expr (cond), BSI_NEW_STMT); + + sorig = single_succ_edge (switch_bb); + sorig->flags = exits[1]->flags; + snew = make_edge (switch_bb, nentry_bb, exits[0]->flags); + + /* Register the new edge from SWITCH_BB in loop exit lists. */ + rescan_loop_exit (snew, true, false); + + /* Add the PHI node arguments. */ + add_phi_args_after_copy (region_copy, n_region, snew); + + /* Get rid of now superfluous conditions and associated edges (and phi node + arguments). */ + e = redirect_edge_and_branch (exits[0], exits[1]->dest); + PENDING_STMT (e) = NULL_TREE; + e = redirect_edge_and_branch (nexits[1], nexits[0]->dest); + PENDING_STMT (e) = NULL_TREE; + + /* Anything that is outside of the region, but was dominated by something + inside needs to update dominance info. */ + iterate_fix_dominators (CDI_DOMINATORS, doms, false); + VEC_free (basic_block, heap, doms); /* Update the SSA web. */ update_ssa (TODO_update_ssa); @@ -5456,10 +5643,12 @@ move_block_to_fn (struct function *dest_cfun, basic_block bb, block_stmt_iterator si; struct move_stmt_d d; unsigned old_len, new_len; - tree phi; + tree phi, next_phi; /* Remove BB from dominance structures. */ delete_from_dominance_info (CDI_DOMINATORS, bb); + if (current_loops) + remove_bb_from_loops (bb); /* Link BB to the new linked list. */ move_block_after (bb, after); @@ -5494,14 +5683,20 @@ move_block_to_fn (struct function *dest_cfun, basic_block bb, bb->index, bb); /* Remap the variables in phi nodes. */ - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + for (phi = phi_nodes (bb); phi; phi = next_phi) { use_operand_p use; tree op = PHI_RESULT (phi); ssa_op_iter oi; + next_phi = PHI_CHAIN (phi); if (!is_gimple_reg (op)) - continue; + { + /* Remove the phi nodes for virtual operands (alias analysis will be + run for the new function, anyway). */ + remove_phi_node (phi, NULL, true); + continue; + } SET_PHI_RESULT (phi, replace_ssa_name (op, vars_map, dest_cfun->decl)); FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE) @@ -5569,7 +5764,12 @@ move_block_to_fn (struct function *dest_cfun, basic_block bb, gimple_remove_stmt_histograms (cfun, stmt); } + /* We cannot leave any operands allocated from the operand caches of + the current function. */ + free_stmt_operands (stmt); + push_cfun (dest_cfun); update_stmt (stmt); + pop_cfun (); } } @@ -5658,6 +5858,7 @@ move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb, edge_iterator ei; htab_t new_label_map; struct pointer_map_t *vars_map; + struct loop *loop = entry_bb->loop_father; /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE region. */ @@ -5786,6 +5987,8 @@ move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb, /* Back in the original function, the SESE region has disappeared, create a new basic block in its place. */ bb = create_empty_bb (entry_pred[0]); + if (current_loops) + add_bb_to_loop (bb, loop); for (i = 0; i < num_entry_edges; i++) { e = make_edge (entry_pred[i], bb, entry_flag[i]); diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index 636a6f0ba55..518e4f2236e 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -704,6 +704,7 @@ extern struct omp_region *root_omp_region; extern struct omp_region *new_omp_region (basic_block, enum tree_code, struct omp_region *); extern void free_omp_regions (void); +void omp_expand_local (basic_block); extern tree find_omp_clause (tree, enum tree_code); tree copy_var_decl (tree, tree, tree); @@ -753,8 +754,10 @@ extern tree tree_block_label (basic_block); extern void extract_true_false_edges_from_block (basic_block, edge *, edge *); extern bool tree_duplicate_sese_region (edge, edge, basic_block *, unsigned, basic_block *); +extern bool tree_duplicate_sese_tail (edge, edge, basic_block *, unsigned, + basic_block *); extern void add_phi_args_after_copy_bb (basic_block); -extern void add_phi_args_after_copy (basic_block *, unsigned); +extern void add_phi_args_after_copy (basic_block *, unsigned, edge); extern bool tree_purge_dead_abnormal_call_edges (basic_block); extern bool tree_purge_dead_eh_edges (basic_block); extern bool tree_purge_all_dead_eh_edges (const_bitmap); @@ -971,6 +974,7 @@ unsigned int tree_ssa_prefetch_arrays (void); unsigned int remove_empty_loops (void); void tree_ssa_iv_optimize (void); unsigned tree_predictive_commoning (void); +bool parallelize_loops (void); bool number_of_iterations_exit (struct loop *, edge, struct tree_niter_desc *niter, bool); @@ -992,7 +996,7 @@ void verify_loop_closed_ssa (void); bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *); void create_iv (tree, tree, tree, struct loop *, block_stmt_iterator *, bool, tree *, tree *); -void split_loop_exit_edge (edge); +basic_block split_loop_exit_edge (edge); unsigned force_expr_to_var_cost (tree); void standard_iv_increment_position (struct loop *, block_stmt_iterator *, bool *); diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c new file mode 100644 index 00000000000..aca2b74c31a --- /dev/null +++ b/gcc/tree-parloops.c @@ -0,0 +1,1148 @@ +/* Loop autoparallelization. + Copyright (C) 2006 Free Software Foundation, Inc. + Contributed by Sebastian Pop <pop@cri.ensmp.fr> and + Zdenek Dvorak <dvorakz@suse.cz>. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to the Free +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "tree.h" +#include "rtl.h" +#include "tree-flow.h" +#include "cfgloop.h" +#include "ggc.h" +#include "tree-data-ref.h" +#include "diagnostic.h" +#include "tree-pass.h" +#include "tree-scalar-evolution.h" +#include "hashtab.h" +#include "langhooks.h" + +/* This pass tries to distribute iterations of loops into several threads. + The implementation is straightforward -- for each loop we test whether its + iterations are independent, and if it is the case (and some additional + conditions regarding profitability and correctness are satisfied), we + add OMP_PARALLEL and OMP_FOR codes and let omp expansion machinery do + its job. + + The most of the complexity is in bringing the code into shape expected + by the omp expanders: + -- for OMP_FOR, ensuring that the loop has only one induction variable + and that the exit test is at the start of the loop body + -- for OMP_PARALLEL, replacing the references to local addressable + variables by accesses through pointers, and breaking up ssa chains + by storing the values incoming to the parallelized loop to a structure + passed to the new function as an argument (something similar is done + in omp gimplification, unfortunately only a small part of the code + can be shared). + + TODO: + -- if there are several parallelizable loops in a function, it may be + possible to generate the threads just once (using synchronization to + ensure that cross-loop dependences are obeyed). + -- handling of common scalar dependence patterns (accumulation, ...) + -- handling of non-innermost loops */ + +/* Minimal number of iterations of a loop that should be executed in each + thread. */ +#define MIN_PER_THREAD 100 + +/* Element of hashtable of names to copy. */ + +struct name_to_copy_elt +{ + unsigned version; /* The version of the name to copy. */ + tree new_name; /* The new name used in the copy. */ + tree field; /* The field of the structure used to pass the + value. */ +}; + +/* Equality and hash functions for hashtab code. */ + +static int +name_to_copy_elt_eq (const void *aa, const void *bb) +{ + struct name_to_copy_elt *a = (struct name_to_copy_elt *) aa; + struct name_to_copy_elt *b = (struct name_to_copy_elt *) bb; + + return a->version == b->version; +} + +static hashval_t +name_to_copy_elt_hash (const void *aa) +{ + struct name_to_copy_elt *a = (struct name_to_copy_elt *) aa; + + return (hashval_t) a->version; +} + +/* Returns true if the iterations of LOOP are independent on each other (that + is, if we can execute them in parallel), and if LOOP satisfies other + conditions that we need to be able to parallelize it. Description of number + of iterations is stored to NITER. */ + +static bool +loop_parallel_p (struct loop *loop, struct tree_niter_desc *niter) +{ + edge exit = single_dom_exit (loop); + VEC (ddr_p, heap) *dependence_relations; + VEC (data_reference_p, heap) *datarefs; + lambda_trans_matrix trans; + bool ret = false; + tree phi; + + /* Only consider innermost loops with just one exit. The innermost-loop + restriction is not necessary, but it makes things simpler. */ + if (loop->inner || !exit) + return false; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\nConsidering loop %d\n", loop->num); + + /* We need to know # of iterations, and there should be no uses of values + defined inside loop outside of it, unless the values are invariants of + the loop. */ + if (!number_of_iterations_exit (loop, exit, niter, false)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " FAILED: number of iterations not known\n"); + return false; + } + + for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi)) + { + tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit); + + if (is_gimple_reg (val)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " FAILED: value used outside loop\n"); + return false; + } + } + + /* The iterations of the loop may communicate only through bivs whose + iteration space can be distributed efficiently. */ + for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi)) + { + tree def = PHI_RESULT (phi); + affine_iv iv; + + if (is_gimple_reg (def) + && !simple_iv (loop, phi, def, &iv, true)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + " FAILED: scalar dependency between iterations\n"); + return false; + } + } + + /* We need to version the loop to verify assumptions in runtime. */ + if (!can_duplicate_loop_p (loop)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " FAILED: cannot be duplicated\n"); + return false; + } + + /* Check for problems with dependences. If the loop can be reversed, + the iterations are independent. */ + datarefs = VEC_alloc (data_reference_p, heap, 10); + dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10); + compute_data_dependences_for_loop (loop, true, &datarefs, + &dependence_relations); + if (dump_file && (dump_flags & TDF_DETAILS)) + dump_data_dependence_relations (dump_file, dependence_relations); + + trans = lambda_trans_matrix_new (1, 1); + LTM_MATRIX (trans)[0][0] = -1; + + if (lambda_transform_legal_p (trans, 1, dependence_relations)) + { + ret = true; + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " SUCCESS: may be parallelized\n"); + } + else if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " FAILED: data dependencies exist across iterations\n"); + + free_dependence_relations (dependence_relations); + free_data_refs (datarefs); + + return ret; +} + +/* Assigns the address of VAR in TYPE to an ssa name, and returns this name. + The assignment statement is placed before LOOP. DECL_ADDRESS maps decls + to their addresses that can be reused. */ + +static tree +take_address_of (tree var, tree type, struct loop *loop, htab_t decl_address) +{ + int uid = DECL_UID (var); + void **dslot; + struct int_tree_map ielt, *nielt; + tree name, bvar, stmt; + edge entry = loop_preheader_edge (loop); + + ielt.uid = uid; + dslot = htab_find_slot_with_hash (decl_address, &ielt, uid, INSERT); + if (!*dslot) + { + bvar = create_tmp_var (type, get_name (var)); + add_referenced_var (bvar); + stmt = build_gimple_modify_stmt (bvar, + fold_convert (type, + build_addr (var, current_function_decl))); + name = make_ssa_name (bvar, stmt); + GIMPLE_STMT_OPERAND (stmt, 0) = name; + bsi_insert_on_edge_immediate (entry, stmt); + + nielt = XNEW (struct int_tree_map); + nielt->uid = uid; + nielt->to = name; + *dslot = nielt; + + return name; + } + + name = ((struct int_tree_map *) *dslot)->to; + if (TREE_TYPE (name) == type) + return name; + + bvar = SSA_NAME_VAR (name); + stmt = build_gimple_modify_stmt (bvar, + fold_convert (type, name)); + name = make_ssa_name (bvar, stmt); + GIMPLE_STMT_OPERAND (stmt, 0) = name; + bsi_insert_on_edge_immediate (entry, stmt); + + return name; +} + +/* Eliminates references to local variables in *TP out of LOOP. DECL_ADDRESS + contains addresses of the references that had their address taken already. + If the expression is changed, CHANGED is set to true. Callback for + walk_tree. */ + +struct elv_data +{ + struct loop *loop; + htab_t decl_address; + bool changed; +}; + +static tree +eliminate_local_variables_1 (tree *tp, int *walk_subtrees, void *data) +{ + struct elv_data *dta = data; + tree t = *tp, var, addr, addr_type, type; + + if (DECL_P (t)) + { + *walk_subtrees = 0; + + if (!SSA_VAR_P (t) || DECL_EXTERNAL (t)) + return NULL_TREE; + + type = TREE_TYPE (t); + addr_type = build_pointer_type (type); + addr = take_address_of (t, addr_type, dta->loop, dta->decl_address); + *tp = build1 (INDIRECT_REF, TREE_TYPE (*tp), addr); + + dta->changed = true; + return NULL_TREE; + } + + if (TREE_CODE (t) == ADDR_EXPR) + { + var = TREE_OPERAND (t, 0); + if (!DECL_P (var)) + return NULL_TREE; + + *walk_subtrees = 0; + if (!SSA_VAR_P (var) || DECL_EXTERNAL (var)) + return NULL_TREE; + + addr_type = TREE_TYPE (t); + addr = take_address_of (var, addr_type, dta->loop, dta->decl_address); + *tp = addr; + + dta->changed = true; + return NULL_TREE; + } + + if (!EXPR_P (t) + && !GIMPLE_STMT_P (t)) + *walk_subtrees = 0; + + return NULL_TREE; +} + +/* Moves the references to local variables in STMT from LOOP. DECL_ADDRESS + contains addresses for the references for that we have already taken + them. */ + +static void +eliminate_local_variables_stmt (struct loop *loop, tree stmt, + htab_t decl_address) +{ + struct elv_data dta; + + dta.loop = loop; + dta.decl_address = decl_address; + dta.changed = false; + + walk_tree (&stmt, eliminate_local_variables_1, &dta, NULL); + + if (dta.changed) + update_stmt (stmt); +} + +/* Eliminates the references to local variables from LOOP. This includes: + + 1) Taking address of a local variable -- these are moved out of the loop + (and temporary variable is created to hold the address if necessary). + 2) Dereferencing a local variable -- these are replaced with indirect + references. */ + +static void +eliminate_local_variables (struct loop *loop) +{ + basic_block bb, *body = get_loop_body (loop); + unsigned i; + block_stmt_iterator bsi; + htab_t decl_address = htab_create (10, int_tree_map_hash, int_tree_map_eq, + free); + + /* Find and rename the ssa names defined outside of loop. */ + for (i = 0; i < loop->num_nodes; i++) + { + bb = body[i]; + + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + eliminate_local_variables_stmt (loop, bsi_stmt (bsi), decl_address); + } + + htab_delete (decl_address); +} + +/* If COPY_NAME_P is true, creates and returns a duplicate of NAME. + The copies are stored to NAME_COPIES, if NAME was already duplicated, + its duplicate stored in NAME_COPIES is returned. + + Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also + duplicated, storing the copies in DECL_COPIES. */ + +static tree +separate_decls_in_loop_name (tree name, + htab_t name_copies, htab_t decl_copies, + bool copy_name_p) +{ + tree copy, var, var_copy; + unsigned idx, uid, nuid; + struct int_tree_map ielt, *nielt; + struct name_to_copy_elt elt, *nelt; + void **slot, **dslot; + + if (TREE_CODE (name) != SSA_NAME) + return name; + + idx = SSA_NAME_VERSION (name); + elt.version = idx; + slot = htab_find_slot_with_hash (name_copies, &elt, idx, + copy_name_p ? INSERT : NO_INSERT); + if (slot && *slot) + return ((struct name_to_copy_elt *) *slot)->new_name; + + var = SSA_NAME_VAR (name); + uid = DECL_UID (var); + ielt.uid = uid; + dslot = htab_find_slot_with_hash (decl_copies, &ielt, uid, INSERT); + if (!*dslot) + { + var_copy = create_tmp_var (TREE_TYPE (var), get_name (var)); + add_referenced_var (var_copy); + nielt = XNEW (struct int_tree_map); + nielt->uid = uid; + nielt->to = var_copy; + *dslot = nielt; + + /* Ensure that when we meet this decl next time, we won't duplicate + it again. */ + nuid = DECL_UID (var_copy); + ielt.uid = nuid; + dslot = htab_find_slot_with_hash (decl_copies, &ielt, nuid, INSERT); + gcc_assert (!*dslot); + nielt = XNEW (struct int_tree_map); + nielt->uid = nuid; + nielt->to = var_copy; + *dslot = nielt; + } + else + var_copy = ((struct int_tree_map *) *dslot)->to; + + if (copy_name_p) + { + copy = duplicate_ssa_name (name, NULL_TREE); + nelt = XNEW (struct name_to_copy_elt); + nelt->version = idx; + nelt->new_name = copy; + nelt->field = NULL_TREE; + *slot = nelt; + } + else + { + gcc_assert (!slot); + copy = name; + } + + SSA_NAME_VAR (copy) = var_copy; + return copy; +} + +/* Finds the ssa names used in STMT that are defined outside of LOOP and + replaces such ssa names with their duplicates. The duplicates are stored to + NAME_COPIES. Base decls of all ssa names used in STMT + (including those defined in LOOP) are replaced with the new temporary + variables; the replacement decls are stored in DECL_COPIES. */ + +static void +separate_decls_in_loop_stmt (struct loop *loop, tree stmt, + htab_t name_copies, htab_t decl_copies) +{ + use_operand_p use; + def_operand_p def; + ssa_op_iter oi; + tree name, copy; + bool copy_name_p; + + mark_virtual_ops_for_renaming (stmt); + + FOR_EACH_PHI_OR_STMT_DEF (def, stmt, oi, SSA_OP_DEF) + { + name = DEF_FROM_PTR (def); + gcc_assert (TREE_CODE (name) == SSA_NAME); + copy = separate_decls_in_loop_name (name, name_copies, decl_copies, + false); + gcc_assert (copy == name); + } + + FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE) + { + name = USE_FROM_PTR (use); + if (TREE_CODE (name) != SSA_NAME) + continue; + + copy_name_p = expr_invariant_in_loop_p (loop, name); + copy = separate_decls_in_loop_name (name, name_copies, decl_copies, + copy_name_p); + SET_USE (use, copy); + } +} + +/* Callback for htab_traverse. Adds a field corresponding to a ssa name + described in SLOT to the type passed in DATA. */ + +static int +add_field_for_name (void **slot, void *data) +{ + struct name_to_copy_elt *elt = *slot; + tree type = data; + tree name = ssa_name (elt->version); + tree var = SSA_NAME_VAR (name); + tree field = build_decl (FIELD_DECL, DECL_NAME (var), TREE_TYPE (var)); + + insert_field_into_struct (type, field); + elt->field = field; + return 1; +} + +/* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and + store to a field of STORE in STORE_BB for the ssa name and its duplicate + specified in SLOT. */ + +struct clsn_data +{ + tree store; + tree load; + + basic_block store_bb; + basic_block load_bb; +}; + +static int +create_loads_and_stores_for_name (void **slot, void *data) +{ + struct name_to_copy_elt *elt = *slot; + struct clsn_data *clsn_data = data; + tree stmt; + block_stmt_iterator bsi; + tree type = TREE_TYPE (elt->new_name); + tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load)); + tree load_struct; + + bsi = bsi_last (clsn_data->store_bb); + stmt = build_gimple_modify_stmt ( + build3 (COMPONENT_REF, type, clsn_data->store, elt->field, + NULL_TREE), + ssa_name (elt->version)); + mark_virtual_ops_for_renaming (stmt); + bsi_insert_after (&bsi, stmt, BSI_NEW_STMT); + + bsi = bsi_last (clsn_data->load_bb); + load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load); + stmt = build_gimple_modify_stmt ( + elt->new_name, + build3 (COMPONENT_REF, type, load_struct, elt->field, + NULL_TREE)); + SSA_NAME_DEF_STMT (elt->new_name) = stmt; + bsi_insert_after (&bsi, stmt, BSI_NEW_STMT); + + return 1; +} + +/* Moves all the variables used in LOOP and defined outside of it (including + the initial values of loop phi nodes, and *PER_THREAD if it is a ssa + name) to a structure created for this purpose. The code + + while (1) + { + use (a); + use (b); + } + + is transformed this way: + + bb0: + old.a = a; + old.b = b; + + bb1: + a' = new->a; + b' = new->b; + while (1) + { + use (a'); + use (b'); + } + + `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The + pointer `new' is intentionally not initialized (the loop will be split to a + separate function later, and `new' will be initialized from its arguments). + */ + +static void +separate_decls_in_loop (struct loop *loop, tree *arg_struct, + tree *new_arg_struct) +{ + basic_block bb1 = split_edge (loop_preheader_edge (loop)); + basic_block bb0 = single_pred (bb1); + htab_t name_copies = htab_create (10, name_to_copy_elt_hash, + name_to_copy_elt_eq, free); + htab_t decl_copies = htab_create (10, int_tree_map_hash, int_tree_map_eq, + free); + basic_block bb, *body = get_loop_body (loop); + unsigned i; + tree phi, type, type_name, nvar; + block_stmt_iterator bsi; + struct clsn_data clsn_data; + + /* Find and rename the ssa names defined outside of loop. */ + for (i = 0; i < loop->num_nodes; i++) + { + bb = body[i]; + + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + separate_decls_in_loop_stmt (loop, phi, name_copies, decl_copies); + + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + separate_decls_in_loop_stmt (loop, bsi_stmt (bsi), name_copies, + decl_copies); + } + free (body); + + if (htab_elements (name_copies) == 0) + { + /* It may happen that there is nothing to copy (if there are only + loop carried and external variables in the loop). */ + *arg_struct = NULL; + *new_arg_struct = NULL; + } + else + { + /* Create the type for the structure to store the ssa names to. */ + type = lang_hooks.types.make_type (RECORD_TYPE); + type_name = build_decl (TYPE_DECL, create_tmp_var_name (".paral_data"), + type); + TYPE_NAME (type) = type_name; + + htab_traverse (name_copies, add_field_for_name, type); + layout_type (type); + + /* Create the loads and stores. */ + *arg_struct = create_tmp_var (type, ".paral_data_store"); + add_referenced_var (*arg_struct); + nvar = create_tmp_var (build_pointer_type (type), ".paral_data_load"); + add_referenced_var (nvar); + *new_arg_struct = make_ssa_name (nvar, NULL_TREE); + + clsn_data.store = *arg_struct; + clsn_data.load = *new_arg_struct; + clsn_data.store_bb = bb0; + clsn_data.load_bb = bb1; + htab_traverse (name_copies, create_loads_and_stores_for_name, + &clsn_data); + } + + htab_delete (decl_copies); + htab_delete (name_copies); +} + +/* Bitmap containing uids of functions created by parallelization. We cannot + allocate it from the default obstack, as it must live across compilation + of several functions; we make it gc allocated instead. */ + +static GTY(()) bitmap parallelized_functions; + +/* Returns true if FN was created by create_loop_fn. */ + +static bool +parallelized_function_p (tree fn) +{ + if (!parallelized_functions || !DECL_ARTIFICIAL (fn)) + return false; + + return bitmap_bit_p (parallelized_functions, DECL_UID (fn)); +} + +/* Creates and returns an empty function that will receive the body of + a parallelized loop. */ + +static tree +create_loop_fn (void) +{ + char buf[100]; + char *tname; + tree decl, type, name, t; + struct function *act_cfun = cfun; + static unsigned loopfn_num; + + snprintf (buf, 100, "%s.$loopfn", current_function_name ()); + ASM_FORMAT_PRIVATE_NAME (tname, buf, loopfn_num++); + clean_symbol_name (tname); + name = get_identifier (tname); + type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE); + + decl = build_decl (FUNCTION_DECL, name, type); + if (!parallelized_functions) + parallelized_functions = BITMAP_GGC_ALLOC (); + bitmap_set_bit (parallelized_functions, DECL_UID (decl)); + + TREE_STATIC (decl) = 1; + TREE_USED (decl) = 1; + DECL_ARTIFICIAL (decl) = 1; + DECL_IGNORED_P (decl) = 0; + TREE_PUBLIC (decl) = 0; + DECL_UNINLINABLE (decl) = 1; + DECL_EXTERNAL (decl) = 0; + DECL_CONTEXT (decl) = NULL_TREE; + DECL_INITIAL (decl) = make_node (BLOCK); + + t = build_decl (RESULT_DECL, NULL_TREE, void_type_node); + DECL_ARTIFICIAL (t) = 1; + DECL_IGNORED_P (t) = 1; + DECL_RESULT (decl) = t; + + t = build_decl (PARM_DECL, get_identifier (".paral_data_param"), + ptr_type_node); + DECL_ARTIFICIAL (t) = 1; + DECL_ARG_TYPE (t) = ptr_type_node; + DECL_CONTEXT (t) = decl; + TREE_USED (t) = 1; + DECL_ARGUMENTS (decl) = t; + + allocate_struct_function (decl); + + /* The call to allocate_struct_function clobbers CFUN, so we need to restore + it. */ + cfun = act_cfun; + + return decl; +} + +/* Bases all the induction variables in LOOP on a single induction variable + (unsigned with base 0 and step 1), whose final value is compared with + NIT. The induction variable is incremented in the loop latch. */ + +static void +canonicalize_loop_ivs (struct loop *loop, tree nit) +{ + unsigned precision = TYPE_PRECISION (TREE_TYPE (nit)); + tree phi, prev, res, type, var_before, val, atype, t, next; + block_stmt_iterator bsi; + bool ok; + affine_iv iv; + edge exit = single_dom_exit (loop); + + for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi)) + { + res = PHI_RESULT (phi); + + if (is_gimple_reg (res) + && TYPE_PRECISION (TREE_TYPE (res)) > precision) + precision = TYPE_PRECISION (TREE_TYPE (res)); + } + + type = lang_hooks.types.type_for_size (precision, 1); + + bsi = bsi_last (loop->latch); + create_iv (build_int_cst_type (type, 0), build_int_cst (type, 1), NULL_TREE, + loop, &bsi, true, &var_before, NULL); + + bsi = bsi_after_labels (loop->header); + prev = NULL; + for (phi = phi_nodes (loop->header); phi; phi = next) + { + next = PHI_CHAIN (phi); + res = PHI_RESULT (phi); + + if (!is_gimple_reg (res) + || res == var_before) + { + prev = phi; + continue; + } + + ok = simple_iv (loop, phi, res, &iv, true); + gcc_assert (ok); + + remove_phi_node (phi, prev, false); + + atype = TREE_TYPE (res); + val = fold_build2 (PLUS_EXPR, atype, + unshare_expr (iv.base), + fold_build2 (MULT_EXPR, atype, + unshare_expr (iv.step), + fold_convert (atype, var_before))); + val = force_gimple_operand_bsi (&bsi, val, false, NULL_TREE, true, + BSI_SAME_STMT); + t = build_gimple_modify_stmt (res, val); + bsi_insert_before (&bsi, t, BSI_SAME_STMT); + SSA_NAME_DEF_STMT (res) = t; + } + + t = last_stmt (exit->src); + /* Make the loop exit if the control condition is not satisfied. */ + if (exit->flags & EDGE_TRUE_VALUE) + { + edge te, fe; + + extract_true_false_edges_from_block (exit->src, &te, &fe); + te->flags = EDGE_FALSE_VALUE; + fe->flags = EDGE_TRUE_VALUE; + } + COND_EXPR_COND (t) = build2 (LT_EXPR, boolean_type_node, var_before, nit); +} + +/* Moves the exit condition of LOOP to the beginning of its header, and + duplicates the part of the last iteration that gets disabled to the + exit of the loop. NIT is the number of iterations of the loop + (used to initialize the variables in the duplicated part). + + TODO: the common case is that latch of the loop is empty and immediatelly + follows the loop exit. In this case, it would be better not to copy the + body of the loop, but only move the entry of the loop directly before the + exit check and increase the number of iterations of the loop by one. + This may need some additional preconditioning in case NIT = ~0. */ + +static void +transform_to_exit_first_loop (struct loop *loop, tree nit) +{ + basic_block *bbs, *nbbs, ex_bb, orig_header; + unsigned n; + bool ok; + edge exit = single_dom_exit (loop), hpred; + tree phi, nphi, cond, control, control_name, res, t, cond_stmt; + block_stmt_iterator bsi; + + split_block_after_labels (loop->header); + orig_header = single_succ (loop->header); + hpred = single_succ_edge (loop->header); + + cond_stmt = last_stmt (exit->src); + cond = COND_EXPR_COND (cond_stmt); + control = TREE_OPERAND (cond, 0); + gcc_assert (TREE_OPERAND (cond, 1) == nit); + + /* Make sure that we have phi nodes on exit for all loop header phis + (create_parallel_loop requires that). */ + for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi)) + { + res = PHI_RESULT (phi); + t = make_ssa_name (SSA_NAME_VAR (res), phi); + SET_PHI_RESULT (phi, t); + + nphi = create_phi_node (res, orig_header); + SSA_NAME_DEF_STMT (res) = nphi; + add_phi_arg (nphi, t, hpred); + + if (res == control) + { + TREE_OPERAND (cond, 0) = t; + update_stmt (cond_stmt); + control = t; + } + } + + bbs = get_loop_body_in_dom_order (loop); + for (n = 0; bbs[n] != exit->src; n++) + continue; + nbbs = XNEWVEC (basic_block, n); + ok = tree_duplicate_sese_tail (single_succ_edge (loop->header), exit, + bbs + 1, n, nbbs); + gcc_assert (ok); + free (bbs); + ex_bb = nbbs[0]; + free (nbbs); + + /* The only gimple reg that should be copied out of the loop is the + control variable. */ + control_name = NULL_TREE; + for (phi = phi_nodes (ex_bb); phi; phi = PHI_CHAIN (phi)) + { + res = PHI_RESULT (phi); + if (!is_gimple_reg (res)) + continue; + + gcc_assert (control_name == NULL_TREE + && SSA_NAME_VAR (res) == SSA_NAME_VAR (control)); + control_name = res; + } + gcc_assert (control_name != NULL_TREE); + phi = SSA_NAME_DEF_STMT (control_name); + remove_phi_node (phi, NULL_TREE, false); + + /* Initialize the control variable to NIT. */ + bsi = bsi_after_labels (ex_bb); + t = build_gimple_modify_stmt (control_name, nit); + bsi_insert_before (&bsi, t, BSI_NEW_STMT); + SSA_NAME_DEF_STMT (control_name) = t; +} + +/* Create the parallel constructs for LOOP as described in gen_parallel_loop. + LOOP_FN and DATA are the arguments of OMP_PARALLEL. + NEW_DATA is the variable that should be initialized from the argument + of LOOP_FN. N_THREADS is the requested number of threads. Returns the + basic block containing OMP_PARALLEL tree. */ + +static basic_block +create_parallel_loop (struct loop *loop, tree loop_fn, tree data, + tree new_data, unsigned n_threads) +{ + block_stmt_iterator bsi; + basic_block bb, paral_bb, for_bb, ex_bb; + tree t, param, res, for_stmt; + tree cvar, cvar_init, initvar, cvar_next, cvar_base, cond, phi, type; + edge exit, nexit, guard, end, e; + + /* Prepare the OMP_PARALLEL statement. */ + bb = loop_preheader_edge (loop)->src; + paral_bb = single_pred (bb); + bsi = bsi_last (paral_bb); + + t = build_omp_clause (OMP_CLAUSE_NUM_THREADS); + OMP_CLAUSE_NUM_THREADS_EXPR (t) + = build_int_cst (integer_type_node, n_threads); + t = build4 (OMP_PARALLEL, void_type_node, NULL_TREE, t, + loop_fn, data); + + bsi_insert_after (&bsi, t, BSI_NEW_STMT); + + /* Initialize NEW_DATA. */ + if (data) + { + bsi = bsi_after_labels (bb); + + param = make_ssa_name (DECL_ARGUMENTS (loop_fn), NULL_TREE); + t = build_gimple_modify_stmt (param, build_fold_addr_expr (data)); + bsi_insert_before (&bsi, t, BSI_SAME_STMT); + SSA_NAME_DEF_STMT (param) = t; + + t = build_gimple_modify_stmt (new_data, + fold_convert (TREE_TYPE (new_data), param)); + bsi_insert_before (&bsi, t, BSI_SAME_STMT); + SSA_NAME_DEF_STMT (new_data) = t; + } + + /* Emit OMP_RETURN for OMP_PARALLEL. */ + bb = split_loop_exit_edge (single_dom_exit (loop)); + bsi = bsi_last (bb); + bsi_insert_after (&bsi, make_node (OMP_RETURN), BSI_NEW_STMT); + + /* Extract data for OMP_FOR. */ + gcc_assert (loop->header == single_dom_exit (loop)->src); + cond = COND_EXPR_COND (last_stmt (loop->header)); + + cvar = TREE_OPERAND (cond, 0); + cvar_base = SSA_NAME_VAR (cvar); + phi = SSA_NAME_DEF_STMT (cvar); + cvar_init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); + initvar = make_ssa_name (cvar_base, NULL_TREE); + SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)), + initvar); + cvar_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); + + bsi = bsi_last (loop->latch); + gcc_assert (bsi_stmt (bsi) == SSA_NAME_DEF_STMT (cvar_next)); + bsi_remove (&bsi, true); + + /* Prepare cfg. */ + for_bb = split_edge (loop_preheader_edge (loop)); + ex_bb = split_loop_exit_edge (single_dom_exit (loop)); + extract_true_false_edges_from_block (loop->header, &nexit, &exit); + gcc_assert (exit == single_dom_exit (loop)); + + guard = make_edge (for_bb, ex_bb, 0); + single_succ_edge (loop->latch)->flags = 0; + end = make_edge (loop->latch, ex_bb, EDGE_FALLTHRU); + for (phi = phi_nodes (ex_bb); phi; phi = PHI_CHAIN (phi)) + { + res = PHI_RESULT (phi); + gcc_assert (!is_gimple_reg (phi)); + t = SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi, exit)); + add_phi_arg (phi, PHI_ARG_DEF_FROM_EDGE (t, loop_preheader_edge (loop)), + guard); + add_phi_arg (phi, PHI_ARG_DEF_FROM_EDGE (t, loop_latch_edge (loop)), + end); + } + e = redirect_edge_and_branch (exit, nexit->dest); + PENDING_STMT (e) = NULL; + + /* Emit OMP_FOR. */ + TREE_OPERAND (cond, 0) = cvar_base; + type = TREE_TYPE (cvar); + t = build_omp_clause (OMP_CLAUSE_SCHEDULE); + OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC; + + for_stmt = make_node (OMP_FOR); + TREE_TYPE (for_stmt) = void_type_node; + OMP_FOR_CLAUSES (for_stmt) = t; + OMP_FOR_INIT (for_stmt) = build_gimple_modify_stmt (initvar, cvar_init); + OMP_FOR_COND (for_stmt) = cond; + OMP_FOR_INCR (for_stmt) = build_gimple_modify_stmt ( + cvar_base, + build2 (PLUS_EXPR, type, + cvar_base, + build_int_cst (type, 1))); + OMP_FOR_BODY (for_stmt) = NULL_TREE; + OMP_FOR_PRE_BODY (for_stmt) = NULL_TREE; + + bsi = bsi_last (for_bb); + bsi_insert_after (&bsi, for_stmt, BSI_NEW_STMT); + SSA_NAME_DEF_STMT (initvar) = for_stmt; + + /* Emit OMP_CONTINUE. */ + bsi = bsi_last (loop->latch); + t = build2 (OMP_CONTINUE, void_type_node, cvar_next, cvar); + bsi_insert_after (&bsi, t, BSI_NEW_STMT); + SSA_NAME_DEF_STMT (cvar_next) = t; + + /* Emit OMP_RETURN for OMP_FOR. */ + bsi = bsi_last (ex_bb); + bsi_insert_after (&bsi, make_node (OMP_RETURN), BSI_NEW_STMT); + + return paral_bb; +} + +/* Generates code to execute the iterations of LOOP in N_THREADS threads in + parallel. NITER describes number of iterations of LOOP. */ + +static void +gen_parallel_loop (struct loop *loop, unsigned n_threads, + struct tree_niter_desc *niter) +{ + struct loop *nloop; + tree many_iterations_cond, type, nit; + tree stmts, arg_struct, new_arg_struct; + basic_block parallel_head; + unsigned prob; + + /* From + + --------------------------------------------------------------------- + loop + { + IV = phi (INIT, IV + STEP) + BODY1; + if (COND) + break; + BODY2; + } + --------------------------------------------------------------------- + + with # of iterations NITER (possibly with MAY_BE_ZERO assumption), + we generate the following code: + + --------------------------------------------------------------------- + + if (MAY_BE_ZERO + || NITER < MIN_PER_THREAD * N_THREADS) + goto original; + + BODY1; + store all local loop-invariant variables used in body of the loop to DATA. + OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA); + load the variables from DATA. + OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static)) + BODY2; + BODY1; + OMP_CONTINUE; + OMP_RETURN -- OMP_FOR + OMP_RETURN -- OMP_PARALLEL + goto end; + + original: + loop + { + IV = phi (INIT, IV + STEP) + BODY1; + if (COND) + break; + BODY2; + } + + end: + + */ + + /* Create two versions of the loop -- in the old one, we know that the + number of iterations is large enough, and we will transform it into the + loop that will be split to loop_fn, the new one will be used for the + remaining iterations. */ + + type = TREE_TYPE (niter->niter); + nit = force_gimple_operand (unshare_expr (niter->niter), &stmts, true, + NULL_TREE); + if (stmts) + bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts); + + many_iterations_cond = + fold_build2 (GE_EXPR, boolean_type_node, + nit, build_int_cst (type, MIN_PER_THREAD * n_threads)); + many_iterations_cond + = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, + invert_truthvalue (unshare_expr (niter->may_be_zero)), + many_iterations_cond); + many_iterations_cond + = force_gimple_operand (many_iterations_cond, &stmts, + false, NULL_TREE); + if (stmts) + bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts); + if (!is_gimple_condexpr (many_iterations_cond)) + { + many_iterations_cond + = force_gimple_operand (many_iterations_cond, &stmts, + true, NULL_TREE); + if (stmts) + bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts); + } + + initialize_original_copy_tables (); + + /* We assume that the loop usually iterates a lot. */ + prob = 4 * REG_BR_PROB_BASE / 5; + nloop = loop_version (loop, many_iterations_cond, NULL, + prob, prob, REG_BR_PROB_BASE - prob, true); + update_ssa (TODO_update_ssa); + free_original_copy_tables (); + + /* Base all the induction variables in LOOP on a single control one. */ + canonicalize_loop_ivs (loop, nit); + + /* Ensure that the exit condition is the first statement in the loop. */ + transform_to_exit_first_loop (loop, nit); + + /* Eliminate the references to local variables from the loop. */ + eliminate_local_variables (loop); + + /* In the old loop, move all variables non-local to the loop to a structure + and back, and create separate decls for the variables used in loop. */ + separate_decls_in_loop (loop, &arg_struct, &new_arg_struct); + + /* Create the parallel constructs. */ + parallel_head = create_parallel_loop (loop, create_loop_fn (), arg_struct, + new_arg_struct, n_threads); + + scev_reset (); + + /* Cancel the loop (it is simpler to do it here rather than to teach the + expander to do it). */ + cancel_loop_tree (loop); + + /* Expand the parallel constructs. We do it directly here instead of running + a separate expand_omp pass, since it is more efficient, and less likely to + cause troubles with further analyses not being able to deal with the + OMP trees. */ + omp_expand_local (parallel_head); +} + +/* Detect parallel loops and generate parallel code using libgomp + primitives. Returns true if some loop was parallelized, false + otherwise. */ + +bool +parallelize_loops (void) +{ + unsigned n_threads = flag_tree_parallelize_loops; + bool changed = false; + struct loop *loop; + struct tree_niter_desc niter_desc; + loop_iterator li; + + /* Do not parallelize loops in the functions created by parallelization. */ + if (parallelized_function_p (cfun->decl)) + return false; + + FOR_EACH_LOOP (li, loop, 0) + { + if (/* Do not bother with loops in cold areas. */ + !maybe_hot_bb_p (loop->header) + /* Or loops that roll too little. */ + || expected_loop_iterations (loop) <= n_threads + /* And of course, the loop must be parallelizable. */ + || !can_duplicate_loop_p (loop) + || !loop_parallel_p (loop, &niter_desc)) + continue; + + changed = true; + gen_parallel_loop (loop, n_threads, &niter_desc); + verify_flow_info (); + verify_dominators (CDI_DOMINATORS); + verify_loop_structure (); + verify_loop_closed_ssa (); + } + + return changed; +} + +#include "gt-tree-parloops.h" diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index df879d85d9f..b19d3d05931 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -268,6 +268,7 @@ extern struct tree_opt_pass pass_record_bounds; extern struct tree_opt_pass pass_if_conversion; extern struct tree_opt_pass pass_vectorize; extern struct tree_opt_pass pass_complete_unroll; +extern struct tree_opt_pass pass_parallelize_loops; extern struct tree_opt_pass pass_loop_prefetch; extern struct tree_opt_pass pass_iv_optimize; extern struct tree_opt_pass pass_tree_loop_done; diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c index 2ac9d1bdb63..91aac3eb354 100644 --- a/gcc/tree-ssa-loop-manip.c +++ b/gcc/tree-ssa-loop-manip.c @@ -454,9 +454,9 @@ verify_loop_closed_ssa (void) } /* Split loop exit edge EXIT. The things are a bit complicated by a need to - preserve the loop closed ssa form. */ + preserve the loop closed ssa form. The newly created block is returned. */ -void +basic_block split_loop_exit_edge (edge exit) { basic_block dest = exit->dest; @@ -483,6 +483,8 @@ split_loop_exit_edge (edge exit) add_phi_arg (new_phi, name, exit); SET_USE (op_p, new_name); } + + return bb; } /* Returns the basic block in that statements should be emitted for induction diff --git a/gcc/tree-ssa-loop.c b/gcc/tree-ssa-loop.c index aed2a4dcc8a..240058a739e 100644 --- a/gcc/tree-ssa-loop.c +++ b/gcc/tree-ssa-loop.c @@ -468,6 +468,42 @@ struct tree_opt_pass pass_complete_unroll = 0 /* letter */ }; +/* Parallelization. */ + +static bool +gate_tree_parallelize_loops (void) +{ + return flag_tree_parallelize_loops != 1; +} + +static unsigned +tree_parallelize_loops (void) +{ + if (number_of_loops () <= 1) + return 0; + + if (parallelize_loops ()) + return TODO_cleanup_cfg | TODO_rebuild_alias; + return 0; +} + +struct tree_opt_pass pass_parallelize_loops = +{ + "parloops", /* name */ + gate_tree_parallelize_loops, /* gate */ + tree_parallelize_loops, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_PARALLELIZE_LOOPS, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ + 0 /* letter */ +}; + /* Prefetching. */ static unsigned int diff --git a/gcc/tree-ssa-operands.c b/gcc/tree-ssa-operands.c index 5c7a9e0b89d..3a944efa0b3 100644 --- a/gcc/tree-ssa-operands.c +++ b/gcc/tree-ssa-operands.c @@ -2450,6 +2450,56 @@ build_ssa_operands (tree stmt) ann->references_memory = true; } +/* Releases the operands of STMT back to their freelists, and clears + the stmt operand lists. */ + +void +free_stmt_operands (tree stmt) +{ + def_optype_p defs = DEF_OPS (stmt), last_def; + use_optype_p uses = USE_OPS (stmt), last_use; + voptype_p vuses = VUSE_OPS (stmt); + voptype_p vdefs = VDEF_OPS (stmt), vdef, next_vdef; + unsigned i; + + if (defs) + { + for (last_def = defs; last_def->next; last_def = last_def->next) + continue; + last_def->next = gimple_ssa_operands (cfun)->free_defs; + gimple_ssa_operands (cfun)->free_defs = defs; + DEF_OPS (stmt) = NULL; + } + + if (uses) + { + for (last_use = uses; last_use->next; last_use = last_use->next) + delink_imm_use (USE_OP_PTR (last_use)); + delink_imm_use (USE_OP_PTR (last_use)); + last_use->next = gimple_ssa_operands (cfun)->free_uses; + gimple_ssa_operands (cfun)->free_uses = uses; + USE_OPS (stmt) = NULL; + } + + if (vuses) + { + for (i = 0; i < VUSE_NUM (vuses); i++) + delink_imm_use (VUSE_OP_PTR (vuses, i)); + add_vop_to_freelist (vuses); + VUSE_OPS (stmt) = NULL; + } + + if (vdefs) + { + for (vdef = vdefs; vdef; vdef = next_vdef) + { + next_vdef = vdef->next; + delink_imm_use (VDEF_OP_PTR (vdef, 0)); + add_vop_to_freelist (vdef); + } + VDEF_OPS (stmt) = NULL; + } +} /* Free any operands vectors in OPS. */ diff --git a/gcc/tree-ssa-operands.h b/gcc/tree-ssa-operands.h index f5855f2a2e5..4dc344e9307 100644 --- a/gcc/tree-ssa-operands.h +++ b/gcc/tree-ssa-operands.h @@ -206,6 +206,7 @@ extern void init_ssa_operands (void); extern void fini_ssa_operands (void); extern void free_ssa_operands (stmt_operands_p); extern void update_stmt_operands (tree); +extern void free_stmt_operands (tree); extern bool verify_imm_links (FILE *f, tree var); extern void copy_virtual_operands (tree, tree); |