-/* Loop optimizer initialization routines.
+/* Loop optimizer initialization routines and RTL loop optimization passes.
Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
This file is part of GCC.
#include "timevar.h"
#include "flags.h"
-/* Initialize loop optimizer. */
+\f
+/* Initialize loop structures. This is used by the tree and RTL loop
+ optimizers. FLAGS specify what properties to compute and/or ensure for
+ loops. */
-struct loops *
-loop_optimizer_init (FILE *dumpfile)
+void
+loop_optimizer_init (unsigned flags)
{
- struct loops *loops = xcalloc (1, sizeof (struct loops));
- edge e;
- edge_iterator ei;
- static bool first_time = true;
-
- if (first_time)
- {
- first_time = false;
- init_set_costs ();
- }
-
- /* Avoid annoying special cases of edges going to exit
- block. */
+ struct loops *loops;
- for (ei = ei_start (EXIT_BLOCK_PTR->preds); (e = ei_safe_edge (ei)); )
- if ((e->flags & EDGE_FALLTHRU) && !single_succ_p (e->src))
- split_edge (e);
- else
- ei_next (&ei);
+ gcc_assert (!current_loops);
+ loops = XCNEW (struct loops);
/* Find the loops. */
- if (flow_loops_find (loops) <= 1)
- {
- /* No loops. */
- flow_loops_free (loops);
- free (loops);
+ flow_loops_find (loops);
+ current_loops = loops;
- return NULL;
+ if (number_of_loops () <= 1)
+ {
+ /* No loops (the 1 returned by number_of_loops corresponds to the fake
+ loop that we put as a root of the loop tree). */
+ loop_optimizer_finalize ();
+ return;
}
- /* Not going to update these. */
- free (loops->cfg.rc_order);
- loops->cfg.rc_order = NULL;
- free (loops->cfg.dfs_order);
- loops->cfg.dfs_order = NULL;
+ if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
+ {
+ /* If the loops may have multiple latches, we cannot canonicalize
+ them further (and most of the loop manipulation functions will
+ not work). However, we avoid modifying cfg, which some
+ passes may want. */
+ gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
+ | LOOPS_HAVE_RECORDED_EXITS)) == 0);
+ current_loops->state = LOOPS_MAY_HAVE_MULTIPLE_LATCHES;
+ }
+ else
+ disambiguate_loops_with_multiple_latches ();
/* Create pre-headers. */
- create_preheaders (loops, CP_SIMPLE_PREHEADERS);
+ if (flags & LOOPS_HAVE_PREHEADERS)
+ create_preheaders (CP_SIMPLE_PREHEADERS);
/* Force all latches to have only single successor. */
- force_single_succ_latches (loops);
+ if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
+ force_single_succ_latches ();
/* Mark irreducible loops. */
- mark_irreducible_loops (loops);
+ if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
+ mark_irreducible_loops ();
+
+ if (flags & LOOPS_HAVE_RECORDED_EXITS)
+ record_loop_exits ();
/* Dump loops. */
- flow_loops_dump (loops, dumpfile, NULL, 1);
+ flow_loops_dump (dump_file, NULL, 1);
#ifdef ENABLE_CHECKING
verify_dominators (CDI_DOMINATORS);
- verify_loop_structure (loops);
+ verify_loop_structure ();
#endif
-
- return loops;
}
-/* Finalize loop optimizer. */
+/* Finalize loop structures. */
+
void
-loop_optimizer_finalize (struct loops *loops, FILE *dumpfile)
+loop_optimizer_finalize (void)
{
- unsigned i;
+ loop_iterator li;
+ struct loop *loop;
+ basic_block bb;
- if (!loops)
+ if (!current_loops)
return;
- for (i = 1; i < loops->num; i++)
- if (loops->parray[i])
- free_simple_loop_desc (loops->parray[i]);
-
- /* Another dump. */
- flow_loops_dump (loops, dumpfile, NULL, 1);
+ FOR_EACH_LOOP (li, loop, 0)
+ {
+ free_simple_loop_desc (loop);
+ }
/* Clean up. */
- flow_loops_free (loops);
- free (loops);
+ if (current_loops->state & LOOPS_HAVE_RECORDED_EXITS)
+ release_recorded_exits ();
+ flow_loops_free (current_loops);
+ free (current_loops);
+ current_loops = NULL;
+
+ FOR_ALL_BB (bb)
+ {
+ bb->loop_father = NULL;
+ }
/* Checking. */
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
}
+
\f
+/* Gate for the RTL loop superpass. The actual passes are subpasses.
+ See passes.c for more on that. */
+
static bool
gate_handle_loop2 (void)
{
- return (optimize > 0 && flag_loop_optimize2
+ return (optimize > 0
&& (flag_move_loop_invariants
|| flag_unswitch_loops
|| flag_peel_loops
|| flag_unroll_loops
- || flag_branch_on_count_reg));
+#ifdef HAVE_doloop_end
+ || (flag_branch_on_count_reg && HAVE_doloop_end)
+#endif
+ ));
}
-/* Perform loop optimizations. It might be better to do them a bit
- sooner, but we want the profile feedback to work more
- efficiently. */
-static void
-rest_of_handle_loop2 (void)
+struct tree_opt_pass pass_loop2 =
{
- struct loops *loops;
- basic_block bb;
+ "loop2", /* name */
+ gate_handle_loop2, /* gate */
+ NULL, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_LOOP, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func |
+ TODO_ggc_collect, /* todo_flags_finish */
+ 'L' /* letter */
+};
+\f
+/* Initialization of the RTL loop passes. */
+static unsigned int
+rtl_loop_init (void)
+{
+ gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
+
if (dump_file)
- dump_flow_info (dump_file);
+ dump_flow_info (dump_file, dump_flags);
- /* Initialize structures for layout changes. */
- cfg_layout_initialize (0);
+ loop_optimizer_init (LOOPS_NORMAL);
+ return 0;
+}
- loops = loop_optimizer_init (dump_file);
+struct tree_opt_pass pass_rtl_loop_init =
+{
+ "loop2_init", /* name */
+ NULL, /* gate */
+ rtl_loop_init, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_LOOP, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func, /* todo_flags_finish */
+ 'L' /* letter */
+};
- if (loops)
- {
- /* The optimizations: */
- if (flag_move_loop_invariants)
- move_loop_invariants (loops);
+\f
+/* Finalization of the RTL loop passes. */
- if (flag_unswitch_loops)
- unswitch_loops (loops);
+static unsigned int
+rtl_loop_done (void)
+{
+ loop_optimizer_finalize ();
+ free_dominance_info (CDI_DOMINATORS);
- if (flag_peel_loops || flag_unroll_loops)
- unroll_and_peel_loops (loops,
- (flag_peel_loops ? UAP_PEEL : 0) |
- (flag_unroll_loops ? UAP_UNROLL : 0) |
- (flag_unroll_all_loops ? UAP_UNROLL_ALL : 0));
+ cleanup_cfg (CLEANUP_EXPENSIVE);
+ delete_trivially_dead_insns (get_insns (), max_reg_num ());
+ reg_scan (get_insns (), max_reg_num ());
+ if (dump_file)
+ dump_flow_info (dump_file, dump_flags);
-#ifdef HAVE_doloop_end
- if (flag_branch_on_count_reg && HAVE_doloop_end)
- doloop_optimize_loops (loops);
-#endif /* HAVE_doloop_end */
+ return 0;
+}
+
+struct tree_opt_pass pass_rtl_loop_done =
+{
+ "loop2_done", /* name */
+ NULL, /* gate */
+ rtl_loop_done, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_LOOP, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func, /* todo_flags_finish */
+ 'L' /* letter */
+};
+
+\f
+/* Loop invariant code motion. */
+static bool
+gate_rtl_move_loop_invariants (void)
+{
+ return flag_move_loop_invariants;
+}
+
+static unsigned int
+rtl_move_loop_invariants (void)
+{
+ if (current_loops)
+ move_loop_invariants ();
+ return 0;
+}
+
+struct tree_opt_pass pass_rtl_move_loop_invariants =
+{
+ "loop2_invariant", /* name */
+ gate_rtl_move_loop_invariants, /* gate */
+ rtl_move_loop_invariants, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_LOOP, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func, /* todo_flags_finish */
+ 'L' /* letter */
+};
+
+\f
+/* Loop unswitching for RTL. */
+static bool
+gate_rtl_unswitch (void)
+{
+ return flag_unswitch_loops;
+}
+
+static unsigned int
+rtl_unswitch (void)
+{
+ if (current_loops)
+ unswitch_loops ();
+ return 0;
+}
+
+struct tree_opt_pass pass_rtl_unswitch =
+{
+ "loop2_unswitch", /* name */
+ gate_rtl_unswitch, /* gate */
+ rtl_unswitch, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_LOOP, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func, /* todo_flags_finish */
+ 'L' /* letter */
+};
- loop_optimizer_finalize (loops, dump_file);
+\f
+/* Loop unswitching for RTL. */
+static bool
+gate_rtl_unroll_and_peel_loops (void)
+{
+ return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
+}
+
+static unsigned int
+rtl_unroll_and_peel_loops (void)
+{
+ if (current_loops)
+ {
+ int flags = 0;
+
+ if (flag_peel_loops)
+ flags |= UAP_PEEL;
+ if (flag_unroll_loops)
+ flags |= UAP_UNROLL;
+ if (flag_unroll_all_loops)
+ flags |= UAP_UNROLL_ALL;
+
+ unroll_and_peel_loops (flags);
}
+ return 0;
+}
- free_dominance_info (CDI_DOMINATORS);
+struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
+{
+ "loop2_unroll", /* name */
+ gate_rtl_unroll_and_peel_loops, /* gate */
+ rtl_unroll_and_peel_loops, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_LOOP, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func, /* todo_flags_finish */
+ 'L' /* letter */
+};
- /* Finalize layout changes. */
- FOR_EACH_BB (bb)
- if (bb->next_bb != EXIT_BLOCK_PTR)
- bb->aux = bb->next_bb;
- cfg_layout_finalize ();
+\f
+/* The doloop optimization. */
+static bool
+gate_rtl_doloop (void)
+{
+#ifdef HAVE_doloop_end
+ return (flag_branch_on_count_reg && HAVE_doloop_end);
+#else
+ return 0;
+#endif
+}
- cleanup_cfg (CLEANUP_EXPENSIVE);
- delete_trivially_dead_insns (get_insns (), max_reg_num ());
- reg_scan (get_insns (), max_reg_num ());
- if (dump_file)
- dump_flow_info (dump_file);
+static unsigned int
+rtl_doloop (void)
+{
+#ifdef HAVE_doloop_end
+ if (current_loops)
+ doloop_optimize_loops ();
+#endif
+ return 0;
}
-struct tree_opt_pass pass_loop2 =
+struct tree_opt_pass pass_rtl_doloop =
{
- "loop2", /* name */
- gate_handle_loop2, /* gate */
- rest_of_handle_loop2, /* execute */
+ "loop2_doloop", /* name */
+ gate_rtl_doloop, /* gate */
+ rtl_doloop, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func |
- TODO_ggc_collect, /* todo_flags_finish */
+ TODO_dump_func, /* todo_flags_finish */
'L' /* letter */
};