/* Loop optimizer initialization routines and RTL loop optimization passes.
|
/* Loop optimizer initialization routines and RTL loop optimization passes.
|
Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008
|
Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008
|
Free Software Foundation, Inc.
|
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"
|
#include "df.h"
|
#include "df.h"
|
#include "ggc.h"
|
#include "ggc.h"
|
|
|
|
|
/* Initialize loop structures. This is used by the tree and RTL loop
|
/* Initialize loop structures. 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. */
|
|
|
void
|
void
|
loop_optimizer_init (unsigned flags)
|
loop_optimizer_init (unsigned flags)
|
{
|
{
|
struct loops *loops;
|
struct loops *loops;
|
|
|
gcc_assert (!current_loops);
|
gcc_assert (!current_loops);
|
loops = GGC_CNEW (struct loops);
|
loops = GGC_CNEW (struct loops);
|
|
|
/* Find the loops. */
|
/* Find the loops. */
|
|
|
flow_loops_find (loops);
|
flow_loops_find (loops);
|
current_loops = loops;
|
current_loops = loops;
|
|
|
if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
|
if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
|
{
|
{
|
/* If the loops may have multiple latches, we cannot canonicalize
|
/* If the loops may have multiple latches, we cannot canonicalize
|
them further (and most of the loop manipulation functions will
|
them further (and most of the loop manipulation functions will
|
not work). However, we avoid modifying cfg, which some
|
not work). However, we avoid modifying cfg, which some
|
passes may want. */
|
passes may want. */
|
gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
|
gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
|
| LOOPS_HAVE_RECORDED_EXITS)) == 0);
|
| LOOPS_HAVE_RECORDED_EXITS)) == 0);
|
loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
|
loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
|
}
|
}
|
else
|
else
|
disambiguate_loops_with_multiple_latches ();
|
disambiguate_loops_with_multiple_latches ();
|
|
|
/* Create pre-headers. */
|
/* Create pre-headers. */
|
if (flags & LOOPS_HAVE_PREHEADERS)
|
if (flags & LOOPS_HAVE_PREHEADERS)
|
{
|
{
|
int cp_flags = CP_SIMPLE_PREHEADERS;
|
int cp_flags = CP_SIMPLE_PREHEADERS;
|
|
|
if (flags & LOOPS_HAVE_FALLTHRU_PREHEADERS)
|
if (flags & LOOPS_HAVE_FALLTHRU_PREHEADERS)
|
cp_flags |= CP_FALLTHRU_PREHEADERS;
|
cp_flags |= CP_FALLTHRU_PREHEADERS;
|
|
|
create_preheaders (cp_flags);
|
create_preheaders (cp_flags);
|
}
|
}
|
|
|
/* 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 ();
|
force_single_succ_latches ();
|
|
|
/* Mark irreducible loops. */
|
/* Mark irreducible loops. */
|
if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
|
if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
|
mark_irreducible_loops ();
|
mark_irreducible_loops ();
|
|
|
if (flags & LOOPS_HAVE_RECORDED_EXITS)
|
if (flags & LOOPS_HAVE_RECORDED_EXITS)
|
record_loop_exits ();
|
record_loop_exits ();
|
|
|
/* Dump loops. */
|
/* Dump loops. */
|
flow_loops_dump (dump_file, NULL, 1);
|
flow_loops_dump (dump_file, NULL, 1);
|
|
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
verify_dominators (CDI_DOMINATORS);
|
verify_dominators (CDI_DOMINATORS);
|
verify_loop_structure ();
|
verify_loop_structure ();
|
#endif
|
#endif
|
}
|
}
|
|
|
/* Finalize loop structures. */
|
/* Finalize loop structures. */
|
|
|
void
|
void
|
loop_optimizer_finalize (void)
|
loop_optimizer_finalize (void)
|
{
|
{
|
loop_iterator li;
|
loop_iterator li;
|
struct loop *loop;
|
struct loop *loop;
|
basic_block bb;
|
basic_block bb;
|
|
|
gcc_assert (current_loops != NULL);
|
gcc_assert (current_loops != NULL);
|
|
|
FOR_EACH_LOOP (li, loop, 0)
|
FOR_EACH_LOOP (li, loop, 0)
|
{
|
{
|
free_simple_loop_desc (loop);
|
free_simple_loop_desc (loop);
|
}
|
}
|
|
|
/* Clean up. */
|
/* Clean up. */
|
if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
|
if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
|
release_recorded_exits ();
|
release_recorded_exits ();
|
flow_loops_free (current_loops);
|
flow_loops_free (current_loops);
|
ggc_free (current_loops);
|
ggc_free (current_loops);
|
current_loops = NULL;
|
current_loops = NULL;
|
|
|
FOR_ALL_BB (bb)
|
FOR_ALL_BB (bb)
|
{
|
{
|
bb->loop_father = NULL;
|
bb->loop_father = NULL;
|
}
|
}
|
|
|
/* Checking. */
|
/* Checking. */
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
/* FIXME: no point to verify flow info after bundling on ia64. Use this
|
/* FIXME: no point to verify flow info after bundling on ia64. Use this
|
hack for achieving this. */
|
hack for achieving this. */
|
if (!reload_completed)
|
if (!reload_completed)
|
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 rtl_opt_pass pass_loop2 =
|
struct rtl_opt_pass pass_loop2 =
|
{
|
{
|
{
|
{
|
RTL_PASS,
|
RTL_PASS,
|
"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 */
|
}
|
}
|
};
|
};
|
|
|
|
|
/* 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)
|
{
|
{
|
gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
|
gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
|
|
|
if (dump_file)
|
if (dump_file)
|
dump_flow_info (dump_file, dump_flags);
|
dump_flow_info (dump_file, dump_flags);
|
|
|
loop_optimizer_init (LOOPS_NORMAL);
|
loop_optimizer_init (LOOPS_NORMAL);
|
return 0;
|
return 0;
|
}
|
}
|
|
|
struct rtl_opt_pass pass_rtl_loop_init =
|
struct rtl_opt_pass pass_rtl_loop_init =
|
{
|
{
|
{
|
{
|
RTL_PASS,
|
RTL_PASS,
|
"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_verify_rtl_sharing /* todo_flags_finish */
|
TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */
|
}
|
}
|
};
|
};
|
|
|
|
|
/* 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)
|
{
|
{
|
loop_optimizer_finalize ();
|
loop_optimizer_finalize ();
|
free_dominance_info (CDI_DOMINATORS);
|
free_dominance_info (CDI_DOMINATORS);
|
|
|
cleanup_cfg (0);
|
cleanup_cfg (0);
|
if (dump_file)
|
if (dump_file)
|
dump_flow_info (dump_file, dump_flags);
|
dump_flow_info (dump_file, dump_flags);
|
|
|
return 0;
|
return 0;
|
}
|
}
|
|
|
struct rtl_opt_pass pass_rtl_loop_done =
|
struct rtl_opt_pass pass_rtl_loop_done =
|
{
|
{
|
{
|
{
|
RTL_PASS,
|
RTL_PASS,
|
"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_verify_rtl_sharing /* todo_flags_finish */
|
TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */
|
}
|
}
|
};
|
};
|
|
|
|
|
/* 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 (number_of_loops () > 1)
|
if (number_of_loops () > 1)
|
move_loop_invariants ();
|
move_loop_invariants ();
|
return 0;
|
return 0;
|
}
|
}
|
|
|
struct rtl_opt_pass pass_rtl_move_loop_invariants =
|
struct rtl_opt_pass pass_rtl_move_loop_invariants =
|
{
|
{
|
{
|
{
|
RTL_PASS,
|
RTL_PASS,
|
"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_MOVE_INVARIANTS, /* tv_id */
|
TV_LOOP_MOVE_INVARIANTS, /* 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_df_verify |
|
TODO_df_verify |
|
TODO_df_finish | TODO_verify_rtl_sharing |
|
TODO_df_finish | TODO_verify_rtl_sharing |
|
TODO_dump_func /* todo_flags_finish */
|
TODO_dump_func /* todo_flags_finish */
|
}
|
}
|
};
|
};
|
|
|
|
|
/* 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 (number_of_loops () > 1)
|
if (number_of_loops () > 1)
|
unswitch_loops ();
|
unswitch_loops ();
|
return 0;
|
return 0;
|
}
|
}
|
|
|
struct rtl_opt_pass pass_rtl_unswitch =
|
struct rtl_opt_pass pass_rtl_unswitch =
|
{
|
{
|
{
|
{
|
RTL_PASS,
|
RTL_PASS,
|
"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_UNSWITCH, /* tv_id */
|
TV_LOOP_UNSWITCH, /* 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_verify_rtl_sharing, /* todo_flags_finish */
|
TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
|
}
|
}
|
};
|
};
|
|
|
|
|
/* 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 (number_of_loops () > 1)
|
if (number_of_loops () > 1)
|
{
|
{
|
int flags = 0;
|
int flags = 0;
|
if (dump_file)
|
if (dump_file)
|
df_dump (dump_file);
|
df_dump (dump_file);
|
|
|
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 (flags);
|
unroll_and_peel_loops (flags);
|
}
|
}
|
return 0;
|
return 0;
|
}
|
}
|
|
|
struct rtl_opt_pass pass_rtl_unroll_and_peel_loops =
|
struct rtl_opt_pass pass_rtl_unroll_and_peel_loops =
|
{
|
{
|
{
|
{
|
RTL_PASS,
|
RTL_PASS,
|
"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_UNROLL, /* tv_id */
|
TV_LOOP_UNROLL, /* 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_verify_rtl_sharing, /* todo_flags_finish */
|
TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
|
}
|
}
|
};
|
};
|
|
|
|
|
/* 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 (number_of_loops () > 1)
|
if (number_of_loops () > 1)
|
doloop_optimize_loops ();
|
doloop_optimize_loops ();
|
#endif
|
#endif
|
return 0;
|
return 0;
|
}
|
}
|
|
|
struct rtl_opt_pass pass_rtl_doloop =
|
struct rtl_opt_pass pass_rtl_doloop =
|
{
|
{
|
{
|
{
|
RTL_PASS,
|
RTL_PASS,
|
"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_DOLOOP, /* tv_id */
|
TV_LOOP_DOLOOP, /* 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_verify_rtl_sharing /* todo_flags_finish */
|
TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */
|
}
|
}
|
};
|
};
|
|
|
|
|
