/* Loop optimizer initialization routines and RTL loop optimization passes.
|
/* Loop optimizer initialization routines and RTL loop optimization passes.
|
Copyright (C) 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
|
Copyright (C) 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify it under
|
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
|
the terms of the GNU General Public License as published by the Free
|
Software Foundation; either version 3, or (at your option) any later
|
Software Foundation; either version 3, or (at your option) any later
|
version.
|
version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
for more details.
|
for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "hard-reg-set.h"
|
#include "hard-reg-set.h"
|
#include "obstack.h"
|
#include "obstack.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "cfgloop.h"
|
#include "cfgloop.h"
|
#include "cfglayout.h"
|
#include "cfglayout.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
#include "timevar.h"
|
#include "timevar.h"
|
#include "flags.h"
|
#include "flags.h"
|
|
|
|
|
/* Initialize loop optimizer. This is used by the tree and RTL loop
|
/* Initialize loop optimizer. This is used by the tree and RTL loop
|
optimizers. FLAGS specify what properties to compute and/or ensure for
|
optimizers. FLAGS specify what properties to compute and/or ensure for
|
loops. */
|
loops. */
|
|
|
struct loops *
|
struct loops *
|
loop_optimizer_init (unsigned flags)
|
loop_optimizer_init (unsigned flags)
|
{
|
{
|
struct loops *loops = XCNEW (struct loops);
|
struct loops *loops = XCNEW (struct loops);
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
static bool first_time = true;
|
static bool first_time = true;
|
|
|
if (first_time)
|
if (first_time)
|
{
|
{
|
first_time = false;
|
first_time = false;
|
init_set_costs ();
|
init_set_costs ();
|
}
|
}
|
|
|
/* Avoid annoying special cases of edges going to exit
|
/* Avoid annoying special cases of edges going to exit
|
block. */
|
block. */
|
|
|
for (ei = ei_start (EXIT_BLOCK_PTR->preds); (e = ei_safe_edge (ei)); )
|
for (ei = ei_start (EXIT_BLOCK_PTR->preds); (e = ei_safe_edge (ei)); )
|
if ((e->flags & EDGE_FALLTHRU) && !single_succ_p (e->src))
|
if ((e->flags & EDGE_FALLTHRU) && !single_succ_p (e->src))
|
split_edge (e);
|
split_edge (e);
|
else
|
else
|
ei_next (&ei);
|
ei_next (&ei);
|
|
|
/* Find the loops. */
|
/* Find the loops. */
|
|
|
if (flow_loops_find (loops) <= 1)
|
if (flow_loops_find (loops) <= 1)
|
{
|
{
|
/* No loops. */
|
/* No loops. */
|
flow_loops_free (loops);
|
flow_loops_free (loops);
|
free (loops);
|
free (loops);
|
|
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
/* Not going to update these. */
|
/* Not going to update these. */
|
free (loops->cfg.rc_order);
|
free (loops->cfg.rc_order);
|
loops->cfg.rc_order = NULL;
|
loops->cfg.rc_order = NULL;
|
free (loops->cfg.dfs_order);
|
free (loops->cfg.dfs_order);
|
loops->cfg.dfs_order = NULL;
|
loops->cfg.dfs_order = NULL;
|
|
|
/* Create pre-headers. */
|
/* Create pre-headers. */
|
if (flags & LOOPS_HAVE_PREHEADERS)
|
if (flags & LOOPS_HAVE_PREHEADERS)
|
create_preheaders (loops, CP_SIMPLE_PREHEADERS);
|
create_preheaders (loops, CP_SIMPLE_PREHEADERS);
|
|
|
/* Force all latches to have only single successor. */
|
/* Force all latches to have only single successor. */
|
if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
|
if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
|
force_single_succ_latches (loops);
|
force_single_succ_latches (loops);
|
|
|
/* Mark irreducible loops. */
|
/* Mark irreducible loops. */
|
if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
|
if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
|
mark_irreducible_loops (loops);
|
mark_irreducible_loops (loops);
|
|
|
if (flags & LOOPS_HAVE_MARKED_SINGLE_EXITS)
|
if (flags & LOOPS_HAVE_MARKED_SINGLE_EXITS)
|
mark_single_exit_loops (loops);
|
mark_single_exit_loops (loops);
|
|
|
/* Dump loops. */
|
/* Dump loops. */
|
flow_loops_dump (loops, dump_file, NULL, 1);
|
flow_loops_dump (loops, dump_file, NULL, 1);
|
|
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
verify_dominators (CDI_DOMINATORS);
|
verify_dominators (CDI_DOMINATORS);
|
verify_loop_structure (loops);
|
verify_loop_structure (loops);
|
#endif
|
#endif
|
|
|
return loops;
|
return loops;
|
}
|
}
|
|
|
/* Finalize loop optimizer. */
|
/* Finalize loop optimizer. */
|
void
|
void
|
loop_optimizer_finalize (struct loops *loops)
|
loop_optimizer_finalize (struct loops *loops)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
|
|
if (!loops)
|
if (!loops)
|
return;
|
return;
|
|
|
for (i = 1; i < loops->num; i++)
|
for (i = 1; i < loops->num; i++)
|
if (loops->parray[i])
|
if (loops->parray[i])
|
free_simple_loop_desc (loops->parray[i]);
|
free_simple_loop_desc (loops->parray[i]);
|
|
|
/* Clean up. */
|
/* Clean up. */
|
flow_loops_free (loops);
|
flow_loops_free (loops);
|
free (loops);
|
free (loops);
|
|
|
/* Checking. */
|
/* Checking. */
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
verify_flow_info ();
|
verify_flow_info ();
|
#endif
|
#endif
|
}
|
}
|
|
|
|
|
/* Gate for the RTL loop superpass. The actual passes are subpasses.
|
/* Gate for the RTL loop superpass. The actual passes are subpasses.
|
See passes.c for more on that. */
|
See passes.c for more on that. */
|
|
|
static bool
|
static bool
|
gate_handle_loop2 (void)
|
gate_handle_loop2 (void)
|
{
|
{
|
return (optimize > 0
|
return (optimize > 0
|
&& (flag_move_loop_invariants
|
&& (flag_move_loop_invariants
|
|| flag_unswitch_loops
|
|| flag_unswitch_loops
|
|| flag_peel_loops
|
|| flag_peel_loops
|
|| flag_unroll_loops
|
|| flag_unroll_loops
|
#ifdef HAVE_doloop_end
|
#ifdef HAVE_doloop_end
|
|| (flag_branch_on_count_reg && HAVE_doloop_end)
|
|| (flag_branch_on_count_reg && HAVE_doloop_end)
|
#endif
|
#endif
|
));
|
));
|
}
|
}
|
|
|
struct tree_opt_pass pass_loop2 =
|
struct tree_opt_pass pass_loop2 =
|
{
|
{
|
"loop2", /* name */
|
"loop2", /* name */
|
gate_handle_loop2, /* gate */
|
gate_handle_loop2, /* gate */
|
NULL, /* execute */
|
NULL, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_LOOP, /* tv_id */
|
TV_LOOP, /* tv_id */
|
0, /* properties_required */
|
0, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_dump_func |
|
TODO_dump_func |
|
TODO_ggc_collect, /* todo_flags_finish */
|
TODO_ggc_collect, /* todo_flags_finish */
|
'L' /* letter */
|
'L' /* letter */
|
};
|
};
|
|
|
|
|
/* Initialization of the RTL loop passes. */
|
/* Initialization of the RTL loop passes. */
|
static unsigned int
|
static unsigned int
|
rtl_loop_init (void)
|
rtl_loop_init (void)
|
{
|
{
|
if (dump_file)
|
if (dump_file)
|
dump_flow_info (dump_file, dump_flags);
|
dump_flow_info (dump_file, dump_flags);
|
|
|
/* Initialize structures for layout changes. */
|
/* Initialize structures for layout changes. */
|
cfg_layout_initialize (0);
|
cfg_layout_initialize (0);
|
|
|
current_loops = loop_optimizer_init (LOOPS_NORMAL);
|
current_loops = loop_optimizer_init (LOOPS_NORMAL);
|
return 0;
|
return 0;
|
}
|
}
|
|
|
struct tree_opt_pass pass_rtl_loop_init =
|
struct tree_opt_pass pass_rtl_loop_init =
|
{
|
{
|
"loop2_init", /* name */
|
"loop2_init", /* name */
|
NULL, /* gate */
|
NULL, /* gate */
|
rtl_loop_init, /* execute */
|
rtl_loop_init, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_LOOP, /* tv_id */
|
TV_LOOP, /* tv_id */
|
0, /* properties_required */
|
0, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_dump_func, /* todo_flags_finish */
|
TODO_dump_func, /* todo_flags_finish */
|
'L' /* letter */
|
'L' /* letter */
|
};
|
};
|
|
|
|
|
/* Finalization of the RTL loop passes. */
|
/* Finalization of the RTL loop passes. */
|
static unsigned int
|
static unsigned int
|
rtl_loop_done (void)
|
rtl_loop_done (void)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
|
|
if (current_loops)
|
if (current_loops)
|
loop_optimizer_finalize (current_loops);
|
loop_optimizer_finalize (current_loops);
|
|
|
free_dominance_info (CDI_DOMINATORS);
|
free_dominance_info (CDI_DOMINATORS);
|
|
|
/* Finalize layout changes. */
|
/* Finalize layout changes. */
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
if (bb->next_bb != EXIT_BLOCK_PTR)
|
if (bb->next_bb != EXIT_BLOCK_PTR)
|
bb->aux = bb->next_bb;
|
bb->aux = bb->next_bb;
|
cfg_layout_finalize ();
|
cfg_layout_finalize ();
|
|
|
cleanup_cfg (CLEANUP_EXPENSIVE);
|
cleanup_cfg (CLEANUP_EXPENSIVE);
|
delete_trivially_dead_insns (get_insns (), max_reg_num ());
|
delete_trivially_dead_insns (get_insns (), max_reg_num ());
|
reg_scan (get_insns (), max_reg_num ());
|
reg_scan (get_insns (), max_reg_num ());
|
if (dump_file)
|
if (dump_file)
|
dump_flow_info (dump_file, dump_flags);
|
dump_flow_info (dump_file, dump_flags);
|
|
|
current_loops = NULL;
|
current_loops = NULL;
|
return 0;
|
return 0;
|
}
|
}
|
|
|
struct tree_opt_pass pass_rtl_loop_done =
|
struct tree_opt_pass pass_rtl_loop_done =
|
{
|
{
|
"loop2_done", /* name */
|
"loop2_done", /* name */
|
NULL, /* gate */
|
NULL, /* gate */
|
rtl_loop_done, /* execute */
|
rtl_loop_done, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_LOOP, /* tv_id */
|
TV_LOOP, /* tv_id */
|
0, /* properties_required */
|
0, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_dump_func, /* todo_flags_finish */
|
TODO_dump_func, /* todo_flags_finish */
|
'L' /* letter */
|
'L' /* letter */
|
};
|
};
|
|
|
|
|
/* Loop invariant code motion. */
|
/* Loop invariant code motion. */
|
static bool
|
static bool
|
gate_rtl_move_loop_invariants (void)
|
gate_rtl_move_loop_invariants (void)
|
{
|
{
|
return flag_move_loop_invariants;
|
return flag_move_loop_invariants;
|
}
|
}
|
|
|
static unsigned int
|
static unsigned int
|
rtl_move_loop_invariants (void)
|
rtl_move_loop_invariants (void)
|
{
|
{
|
if (current_loops)
|
if (current_loops)
|
move_loop_invariants (current_loops);
|
move_loop_invariants (current_loops);
|
return 0;
|
return 0;
|
}
|
}
|
|
|
struct tree_opt_pass pass_rtl_move_loop_invariants =
|
struct tree_opt_pass pass_rtl_move_loop_invariants =
|
{
|
{
|
"loop2_invariant", /* name */
|
"loop2_invariant", /* name */
|
gate_rtl_move_loop_invariants, /* gate */
|
gate_rtl_move_loop_invariants, /* gate */
|
rtl_move_loop_invariants, /* execute */
|
rtl_move_loop_invariants, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_LOOP, /* tv_id */
|
TV_LOOP, /* tv_id */
|
0, /* properties_required */
|
0, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_dump_func, /* todo_flags_finish */
|
TODO_dump_func, /* todo_flags_finish */
|
'L' /* letter */
|
'L' /* letter */
|
};
|
};
|
|
|
|
|
/* Loop unswitching for RTL. */
|
/* Loop unswitching for RTL. */
|
static bool
|
static bool
|
gate_rtl_unswitch (void)
|
gate_rtl_unswitch (void)
|
{
|
{
|
return flag_unswitch_loops;
|
return flag_unswitch_loops;
|
}
|
}
|
|
|
static unsigned int
|
static unsigned int
|
rtl_unswitch (void)
|
rtl_unswitch (void)
|
{
|
{
|
if (current_loops)
|
if (current_loops)
|
unswitch_loops (current_loops);
|
unswitch_loops (current_loops);
|
return 0;
|
return 0;
|
}
|
}
|
|
|
struct tree_opt_pass pass_rtl_unswitch =
|
struct tree_opt_pass pass_rtl_unswitch =
|
{
|
{
|
"loop2_unswitch", /* name */
|
"loop2_unswitch", /* name */
|
gate_rtl_unswitch, /* gate */
|
gate_rtl_unswitch, /* gate */
|
rtl_unswitch, /* execute */
|
rtl_unswitch, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_LOOP, /* tv_id */
|
TV_LOOP, /* tv_id */
|
0, /* properties_required */
|
0, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_dump_func, /* todo_flags_finish */
|
TODO_dump_func, /* todo_flags_finish */
|
'L' /* letter */
|
'L' /* letter */
|
};
|
};
|
|
|
|
|
/* Loop unswitching for RTL. */
|
/* Loop unswitching for RTL. */
|
static bool
|
static bool
|
gate_rtl_unroll_and_peel_loops (void)
|
gate_rtl_unroll_and_peel_loops (void)
|
{
|
{
|
return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
|
return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
|
}
|
}
|
|
|
static unsigned int
|
static unsigned int
|
rtl_unroll_and_peel_loops (void)
|
rtl_unroll_and_peel_loops (void)
|
{
|
{
|
if (current_loops)
|
if (current_loops)
|
{
|
{
|
int flags = 0;
|
int flags = 0;
|
|
|
if (flag_peel_loops)
|
if (flag_peel_loops)
|
flags |= UAP_PEEL;
|
flags |= UAP_PEEL;
|
if (flag_unroll_loops)
|
if (flag_unroll_loops)
|
flags |= UAP_UNROLL;
|
flags |= UAP_UNROLL;
|
if (flag_unroll_all_loops)
|
if (flag_unroll_all_loops)
|
flags |= UAP_UNROLL_ALL;
|
flags |= UAP_UNROLL_ALL;
|
|
|
unroll_and_peel_loops (current_loops, flags);
|
unroll_and_peel_loops (current_loops, flags);
|
}
|
}
|
return 0;
|
return 0;
|
}
|
}
|
|
|
struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
|
struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
|
{
|
{
|
"loop2_unroll", /* name */
|
"loop2_unroll", /* name */
|
gate_rtl_unroll_and_peel_loops, /* gate */
|
gate_rtl_unroll_and_peel_loops, /* gate */
|
rtl_unroll_and_peel_loops, /* execute */
|
rtl_unroll_and_peel_loops, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_LOOP, /* tv_id */
|
TV_LOOP, /* tv_id */
|
0, /* properties_required */
|
0, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_dump_func, /* todo_flags_finish */
|
TODO_dump_func, /* todo_flags_finish */
|
'L' /* letter */
|
'L' /* letter */
|
};
|
};
|
|
|
|
|
/* The doloop optimization. */
|
/* The doloop optimization. */
|
static bool
|
static bool
|
gate_rtl_doloop (void)
|
gate_rtl_doloop (void)
|
{
|
{
|
#ifdef HAVE_doloop_end
|
#ifdef HAVE_doloop_end
|
return (flag_branch_on_count_reg && HAVE_doloop_end);
|
return (flag_branch_on_count_reg && HAVE_doloop_end);
|
#else
|
#else
|
return 0;
|
return 0;
|
#endif
|
#endif
|
}
|
}
|
|
|
static unsigned int
|
static unsigned int
|
rtl_doloop (void)
|
rtl_doloop (void)
|
{
|
{
|
#ifdef HAVE_doloop_end
|
#ifdef HAVE_doloop_end
|
if (current_loops)
|
if (current_loops)
|
doloop_optimize_loops (current_loops);
|
doloop_optimize_loops (current_loops);
|
#endif
|
#endif
|
return 0;
|
return 0;
|
}
|
}
|
|
|
struct tree_opt_pass pass_rtl_doloop =
|
struct tree_opt_pass pass_rtl_doloop =
|
{
|
{
|
"loop2_doloop", /* name */
|
"loop2_doloop", /* name */
|
gate_rtl_doloop, /* gate */
|
gate_rtl_doloop, /* gate */
|
rtl_doloop, /* execute */
|
rtl_doloop, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_LOOP, /* tv_id */
|
TV_LOOP, /* tv_id */
|
0, /* properties_required */
|
0, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_dump_func, /* todo_flags_finish */
|
TODO_dump_func, /* todo_flags_finish */
|
'L' /* letter */
|
'L' /* letter */
|
};
|
};
|
|
|
|
|
