X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Ftree-ssa-loop.c;h=2ea58f690430adf85f6d8fe2d580ad7a0d3f2e07;hp=8ec9c3de3491915bef61bfdf08ccd1bc78904ac3;hb=f4c4e2a28c55e1e22bc38dfdd3d5fc219abcb283;hpb=0332ea549d3bdd32d3010e61d7842194327f8661 diff --git a/gcc/tree-ssa-loop.c b/gcc/tree-ssa-loop.c index 8ec9c3de349..2ea58f69043 100644 --- a/gcc/tree-ssa-loop.c +++ b/gcc/tree-ssa-loop.c @@ -1,11 +1,11 @@ /* Loop optimizations over tree-ssa. - Copyright (C) 2003 Free Software Foundation, Inc. + Copyright (C) 2003, 2005, 2006, 2007 Free Software Foundation, Inc. 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 +Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT @@ -14,9 +14,8 @@ 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, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" @@ -38,48 +37,20 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "tree-inline.h" #include "tree-scalar-evolution.h" -/* The loop tree currently optimized. */ - -struct loops *current_loops; - -/* Initializes the loop structures. DUMP is the file to that the details - about the analysis should be dumped. */ - -static struct loops * -tree_loop_optimizer_init (FILE *dump) -{ - struct loops *loops = loop_optimizer_init (dump); - - if (!loops) - return NULL; - - /* Creation of preheaders may create redundant phi nodes if the loop is - entered by more than one edge, but the initial value of the induction - variable is the same on all of them. */ - kill_redundant_phi_nodes (); - rewrite_into_ssa (false); - bitmap_clear (vars_to_rename); - - rewrite_into_loop_closed_ssa (); -#ifdef ENABLE_CHECKING - verify_loop_closed_ssa (); -#endif - - return loops; -} - /* The loop superpass. */ static bool -gate_loop (void) +gate_tree_loop (void) { return flag_tree_loop_optimize != 0; } -struct tree_opt_pass pass_loop = +struct gimple_opt_pass pass_tree_loop = { + { + GIMPLE_PASS, "loop", /* name */ - gate_loop, /* gate */ + gate_tree_loop, /* gate */ NULL, /* execute */ NULL, /* sub */ NULL, /* next */ @@ -89,51 +60,55 @@ struct tree_opt_pass pass_loop = 0, /* properties_provided */ 0, /* properties_destroyed */ TODO_ggc_collect, /* todo_flags_start */ - TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect, /* todo_flags_finish */ - 0 /* letter */ + TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect /* todo_flags_finish */ + } }; /* Loop optimizer initialization. */ -static void +static unsigned int tree_ssa_loop_init (void) { - current_loops = tree_loop_optimizer_init (dump_file); - if (!current_loops) - return; + loop_optimizer_init (LOOPS_NORMAL + | LOOPS_HAVE_RECORDED_EXITS); + rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); - /* Find the loops that are exited just through a single edge. */ - mark_single_exit_loops (current_loops); + if (number_of_loops () <= 1) + return 0; - scev_initialize (current_loops); + scev_initialize (); + return 0; } -struct tree_opt_pass pass_loop_init = +struct gimple_opt_pass pass_tree_loop_init = { + { + GIMPLE_PASS, "loopinit", /* name */ NULL, /* gate */ tree_ssa_loop_init, /* execute */ NULL, /* sub */ NULL, /* next */ 0, /* static_pass_number */ - 0, /* tv_id */ + TV_TREE_LOOP_INIT, /* tv_id */ PROP_cfg, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_dump_func, /* todo_flags_finish */ - 0 /* letter */ + TODO_dump_func | TODO_verify_loops /* todo_flags_finish */ + } }; /* Loop invariant motion pass. */ -static void +static unsigned int tree_ssa_loop_im (void) { - if (!current_loops) - return; + if (number_of_loops () <= 1) + return 0; - tree_ssa_lim (current_loops); + tree_ssa_lim (); + return 0; } static bool @@ -142,8 +117,10 @@ gate_tree_ssa_loop_im (void) return flag_tree_loop_im != 0; } -struct tree_opt_pass pass_lim = +struct gimple_opt_pass pass_lim = { + { + GIMPLE_PASS, "lim", /* name */ gate_tree_ssa_loop_im, /* gate */ tree_ssa_loop_im, /* execute */ @@ -155,19 +132,19 @@ struct tree_opt_pass pass_lim = 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_dump_func, /* todo_flags_finish */ - 0 /* letter */ + TODO_dump_func | TODO_verify_loops /* todo_flags_finish */ + } }; /* Loop unswitching pass. */ -static void +static unsigned int tree_ssa_loop_unswitch (void) { - if (!current_loops) - return; + if (number_of_loops () <= 1) + return 0; - tree_ssa_unswitch_loops (current_loops); + return tree_ssa_unswitch_loops (); } static bool @@ -176,8 +153,10 @@ gate_tree_ssa_loop_unswitch (void) return flag_unswitch_loops != 0; } -struct tree_opt_pass pass_unswitch = +struct gimple_opt_pass pass_tree_unswitch = { + { + GIMPLE_PASS, "unswitch", /* name */ gate_tree_ssa_loop_unswitch, /* gate */ tree_ssa_loop_unswitch, /* execute */ @@ -189,30 +168,70 @@ struct tree_opt_pass pass_unswitch = 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_dump_func, /* todo_flags_finish */ - 0 /* letter */ + TODO_ggc_collect | TODO_dump_func + | TODO_verify_loops /* todo_flags_finish */ + } +}; + +/* Predictive commoning. */ + +static unsigned +run_tree_predictive_commoning (void) +{ + if (!current_loops) + return 0; + + tree_predictive_commoning (); + return 0; +} + +static bool +gate_tree_predictive_commoning (void) +{ + return flag_predictive_commoning != 0; +} + +struct gimple_opt_pass pass_predcom = +{ + { + GIMPLE_PASS, + "pcom", /* name */ + gate_tree_predictive_commoning, /* gate */ + run_tree_predictive_commoning, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_PREDCOM, /* tv_id */ + PROP_cfg, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | TODO_verify_loops + | TODO_update_ssa_only_virtuals /* todo_flags_finish */ + } }; /* Loop autovectorization. */ -static void +static unsigned int tree_vectorize (void) { - if (!current_loops) - return; + if (number_of_loops () <= 1) + return 0; - bitmap_clear (vars_to_rename); - vectorize_loops (current_loops); + return vectorize_loops (); } static bool gate_tree_vectorize (void) { - return flag_tree_vectorize != 0; + return flag_tree_vectorize; } -struct tree_opt_pass pass_vectorize = +struct gimple_opt_pass pass_vectorize = { + { + GIMPLE_PASS, "vect", /* name */ gate_tree_vectorize, /* gate */ tree_vectorize, /* execute */ @@ -223,21 +242,22 @@ struct tree_opt_pass pass_vectorize = PROP_cfg | PROP_ssa, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - TODO_dump_func, /* todo_flags_finish */ - 0 /* letter */ + TODO_verify_loops, /* todo_flags_start */ + TODO_dump_func | TODO_update_ssa + | TODO_ggc_collect /* todo_flags_finish */ + } }; - /* Loop nest optimizations. */ -static void +static unsigned int tree_linear_transform (void) { - if (!current_loops) - return; + if (number_of_loops () <= 1) + return 0; - linear_transform_loops (current_loops); + linear_transform_loops (); + return 0; } static bool @@ -246,8 +266,10 @@ gate_tree_linear_transform (void) return flag_tree_loop_linear != 0; } -struct tree_opt_pass pass_linear_transform = +struct gimple_opt_pass pass_linear_transform = { + { + GIMPLE_PASS, "ltrans", /* name */ gate_tree_linear_transform, /* gate */ tree_linear_transform, /* execute */ @@ -259,19 +281,102 @@ struct tree_opt_pass pass_linear_transform = 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_dump_func, /* todo_flags_finish */ - 0 /* letter */ + TODO_dump_func | TODO_verify_loops + | TODO_update_ssa_only_virtuals + | TODO_ggc_collect /* todo_flags_finish */ + } +}; + +/* GRAPHITE optimizations. */ + +static unsigned int +graphite_transforms (void) +{ + if (!current_loops) + return 0; + + graphite_transform_loops (); + + return 0; +} + +static bool +gate_graphite_transforms (void) +{ + /* Enable -fgraphite pass if any one of the graphite optimization flags + is turned on. */ + if (flag_loop_block || flag_loop_interchange || flag_loop_strip_mine + || flag_graphite_identity) + flag_graphite = 1; + + return flag_graphite != 0; +} + +struct gimple_opt_pass pass_graphite_transforms = +{ + { + GIMPLE_PASS, + "graphite", /* name */ + gate_graphite_transforms, /* gate */ + graphite_transforms, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_GRAPHITE_TRANSFORMS, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_verify_loops /* todo_flags_finish */ + } +}; + +/* Check the correctness of the data dependence analyzers. */ + +static unsigned int +check_data_deps (void) +{ + if (number_of_loops () <= 1) + return 0; + + tree_check_data_deps (); + return 0; +} + +static bool +gate_check_data_deps (void) +{ + return flag_check_data_deps != 0; +} + +struct gimple_opt_pass pass_check_data_deps = +{ + { + GIMPLE_PASS, + "ckdd", /* name */ + gate_check_data_deps, /* gate */ + check_data_deps, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_CHECK_DATA_DEPS, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func /* todo_flags_finish */ + } }; /* Canonical induction variable creation pass. */ -static void +static unsigned int tree_ssa_loop_ivcanon (void) { - if (!current_loops) - return; + if (number_of_loops () <= 1) + return 0; - canonicalize_induction_variables (current_loops); + return canonicalize_induction_variables (); } static bool @@ -280,8 +385,10 @@ gate_tree_ssa_loop_ivcanon (void) return flag_tree_loop_ivcanon != 0; } -struct tree_opt_pass pass_iv_canon = +struct gimple_opt_pass pass_iv_canon = { + { + GIMPLE_PASS, "ivcanon", /* name */ gate_tree_ssa_loop_ivcanon, /* gate */ tree_ssa_loop_ivcanon, /* execute */ @@ -293,24 +400,87 @@ struct tree_opt_pass pass_iv_canon = 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_dump_func, /* todo_flags_finish */ - 0 /* letter */ + TODO_dump_func | TODO_verify_loops /* todo_flags_finish */ + } +}; + +/* Propagation of constants using scev. */ + +static bool +gate_scev_const_prop (void) +{ + return flag_tree_scev_cprop; +} + +struct gimple_opt_pass pass_scev_cprop = +{ + { + GIMPLE_PASS, + "sccp", /* name */ + gate_scev_const_prop, /* gate */ + scev_const_prop, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_SCEV_CONST, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | TODO_cleanup_cfg + | TODO_update_ssa_only_virtuals + /* todo_flags_finish */ + } +}; + +/* Remove empty loops. */ + +static unsigned int +tree_ssa_empty_loop (void) +{ + if (number_of_loops () <= 1) + return 0; + + return remove_empty_loops (); +} + +struct gimple_opt_pass pass_empty_loop = +{ + { + GIMPLE_PASS, + "empty", /* name */ + NULL, /* gate */ + tree_ssa_empty_loop, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_COMPLETE_UNROLL, /* 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_ggc_collect /* todo_flags_finish */ + } }; /* Record bounds on numbers of iterations of loops. */ -static void +static unsigned int tree_ssa_loop_bounds (void) { - if (!current_loops) - return; + if (number_of_loops () <= 1) + return 0; - estimate_numbers_of_iterations (current_loops); + estimate_numbers_of_iterations (); scev_reset (); + return 0; } -struct tree_opt_pass pass_record_bounds = +struct gimple_opt_pass pass_record_bounds = { + { + GIMPLE_PASS, NULL, /* name */ NULL, /* gate */ tree_ssa_loop_bounds, /* execute */ @@ -322,29 +492,33 @@ struct tree_opt_pass pass_record_bounds = 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - 0, /* todo_flags_finish */ - 0 /* letter */ + 0 /* todo_flags_finish */ + } }; /* Complete unrolling of loops. */ -static void +static unsigned int tree_complete_unroll (void) { - if (!current_loops) - return; + if (number_of_loops () <= 1) + return 0; - tree_unroll_loops_completely (current_loops); + return tree_unroll_loops_completely (flag_unroll_loops + || flag_peel_loops + || optimize >= 3, true); } static bool gate_tree_complete_unroll (void) { - return flag_unroll_loops != 0; + return true; } -struct tree_opt_pass pass_complete_unroll = +struct gimple_opt_pass pass_complete_unroll = { + { + GIMPLE_PASS, "cunroll", /* name */ gate_tree_complete_unroll, /* gate */ tree_complete_unroll, /* execute */ @@ -356,19 +530,142 @@ struct tree_opt_pass pass_complete_unroll = 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_dump_func, /* todo_flags_finish */ - 0 /* letter */ + TODO_dump_func | TODO_verify_loops + | TODO_ggc_collect /* todo_flags_finish */ + } +}; + +/* Complete unrolling of inner loops. */ + +static unsigned int +tree_complete_unroll_inner (void) +{ + unsigned ret = 0; + + loop_optimizer_init (LOOPS_NORMAL + | LOOPS_HAVE_RECORDED_EXITS); + if (number_of_loops () > 1) + { + scev_initialize (); + ret = tree_unroll_loops_completely (optimize >= 3, false); + free_numbers_of_iterations_estimates (); + scev_finalize (); + } + loop_optimizer_finalize (); + + return ret; +} + +static bool +gate_tree_complete_unroll_inner (void) +{ + return optimize >= 2; +} + +struct gimple_opt_pass pass_complete_unrolli = +{ + { + GIMPLE_PASS, + "cunrolli", /* name */ + gate_tree_complete_unroll_inner, /* gate */ + tree_complete_unroll_inner, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_COMPLETE_UNROLL, /* 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_ggc_collect /* todo_flags_finish */ + } +}; + +/* 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 gimple_opt_pass pass_parallelize_loops = +{ + { + GIMPLE_PASS, + "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 */ + } +}; + +/* Prefetching. */ + +static unsigned int +tree_ssa_loop_prefetch (void) +{ + if (number_of_loops () <= 1) + return 0; + + return tree_ssa_prefetch_arrays (); +} + +static bool +gate_tree_ssa_loop_prefetch (void) +{ + return flag_prefetch_loop_arrays != 0; +} + +struct gimple_opt_pass pass_loop_prefetch = +{ + { + GIMPLE_PASS, + "aprefetch", /* name */ + gate_tree_ssa_loop_prefetch, /* gate */ + tree_ssa_loop_prefetch, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_PREFETCH, /* 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 */ + } }; /* Induction variable optimizations. */ -static void +static unsigned int tree_ssa_loop_ivopts (void) { - if (!current_loops) - return; + if (number_of_loops () <= 1) + return 0; - tree_ssa_iv_optimize (current_loops); + tree_ssa_iv_optimize (); + return 0; } static bool @@ -377,8 +674,10 @@ gate_tree_ssa_loop_ivopts (void) return flag_ivopts != 0; } -struct tree_opt_pass pass_iv_optimize = +struct gimple_opt_pass pass_iv_optimize = { + { + GIMPLE_PASS, "ivopts", /* name */ gate_tree_ssa_loop_ivopts, /* gate */ tree_ssa_loop_ivopts, /* execute */ @@ -390,44 +689,37 @@ struct tree_opt_pass pass_iv_optimize = 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_dump_func, /* todo_flags_finish */ - 0 /* letter */ + TODO_dump_func | TODO_verify_loops + | TODO_update_ssa | TODO_ggc_collect /* todo_flags_finish */ + } }; /* Loop optimizer finalization. */ -static void +static unsigned int tree_ssa_loop_done (void) { - if (!current_loops) - return; - -#ifdef ENABLE_CHECKING - verify_loop_closed_ssa (); -#endif - - free_numbers_of_iterations_estimates (current_loops); + free_numbers_of_iterations_estimates (); scev_finalize (); - loop_optimizer_finalize (current_loops, - (dump_flags & TDF_DETAILS ? dump_file : NULL)); - current_loops = NULL; - cleanup_tree_cfg (); + loop_optimizer_finalize (); + return 0; } -struct tree_opt_pass pass_loop_done = +struct gimple_opt_pass pass_tree_loop_done = { + { + GIMPLE_PASS, "loopdone", /* name */ NULL, /* gate */ tree_ssa_loop_done, /* execute */ NULL, /* sub */ NULL, /* next */ 0, /* static_pass_number */ - 0, /* tv_id */ + TV_TREE_LOOP_FINI, /* tv_id */ PROP_cfg, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_dump_func, /* todo_flags_finish */ - 0 /* letter */ + TODO_cleanup_cfg | TODO_dump_func /* todo_flags_finish */ + } }; -