/* Induction variable canonicalization.
- Copyright (C) 2004, 2005, 2007, 2008 Free Software Foundation, Inc.
-
+ Copyright (C) 2004, 2005, 2007, 2008, 2010
+ 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 3, 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 COPYING3. If not see
<http://www.gnu.org/licenses/>. */
/* This pass detects the loops that iterate a constant number of times,
- adds a canonical induction variable (step -1, tested against 0)
+ adds a canonical induction variable (step -1, tested against 0)
and replaces the exit test. This enables the less powerful rtl
level analysis to use this information.
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
-#include "rtl.h"
#include "tm_p.h"
-#include "hard-reg-set.h"
#include "basic-block.h"
-#include "output.h"
-#include "diagnostic.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "cfgloop.h"
#include "tree-pass.h"
-#include "ggc.h"
#include "tree-chrec.h"
#include "tree-scalar-evolution.h"
#include "params.h"
if (is_gimple_min_invariant (op))
return true;
-
+
/* We can still fold accesses to constant arrays when index is known. */
if (TREE_CODE (op) != SSA_NAME)
{
fprintf (dump_file, "size: %i-%i, last_iteration: %i-%i\n", size->overall,
size->eliminated_by_peeling, size->last_iteration,
size->last_iteration_eliminated_by_peeling);
-
+
free (body);
}
}
/* Tries to unroll LOOP completely, i.e. NITER times.
- UL determines which loops we are allowed to unroll.
+ UL determines which loops we are allowed to unroll.
EXIT is the exit of the loop that should be eliminated. */
static bool
}
/* Adds a canonical induction variable to LOOP if suitable.
- CREATE_IV is true if we may create a new iv. UL determines
+ CREATE_IV is true if we may create a new iv. UL determines
which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
- to determine the number of iterations of a loop by direct evaluation.
+ to determine the number of iterations of a loop by direct evaluation.
Returns true if cfg is changed. */
static bool
loop_iterator li;
struct loop *loop;
bool changed = false;
-
+
FOR_EACH_LOOP (li, loop, 0)
{
changed |= canonicalize_loop_induction_variables (loop,
struct loop *loop;
bool changed;
enum unroll_level ul;
+ int iteration = 0;
do
{
scev_reset ();
}
}
- while (changed);
-
- return 0;
-}
-
-/* Checks whether LOOP is empty. */
-
-static bool
-empty_loop_p (struct loop *loop)
-{
- edge exit;
- basic_block *body;
- gimple_stmt_iterator gsi;
- unsigned i;
-
- /* If the loop has multiple exits, it is too hard for us to handle.
- Similarly, if the exit is not dominating, we cannot determine
- whether the loop is not infinite. */
- exit = single_dom_exit (loop);
- if (!exit)
- return false;
-
- /* The loop must be finite. */
- if (!finite_loop_p (loop))
- return false;
-
- /* Values of all loop exit phi nodes must be invariants. */
- for (gsi = gsi_start(phi_nodes (exit->dest)); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- gimple phi = gsi_stmt (gsi);
- tree def;
-
- if (!is_gimple_reg (PHI_RESULT (phi)))
- continue;
-
- def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
-
- if (!expr_invariant_in_loop_p (loop, def))
- return false;
- }
-
- /* And there should be no memory modifying or from other reasons
- unremovable statements. */
- body = get_loop_body (loop);
- for (i = 0; i < loop->num_nodes; i++)
- {
- /* Irreducible region might be infinite. */
- if (body[i]->flags & BB_IRREDUCIBLE_LOOP)
- {
- free (body);
- return false;
- }
-
- for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- gimple stmt = gsi_stmt (gsi);
-
- if (gimple_vdef (stmt)
- || gimple_has_volatile_ops (stmt))
- {
- free (body);
- return false;
- }
-
- /* Also, asm statements and calls may have side effects and we
- cannot change the number of times they are executed. */
- switch (gimple_code (stmt))
- {
- case GIMPLE_CALL:
- if (gimple_has_side_effects (stmt))
- {
- free (body);
- return false;
- }
- break;
-
- case GIMPLE_ASM:
- /* We cannot remove volatile assembler. */
- if (gimple_asm_volatile_p (stmt))
- {
- free (body);
- return false;
- }
- break;
-
- default:
- break;
- }
- }
- }
- free (body);
-
- return true;
-}
-
-/* Remove LOOP by making it exit in the first iteration. */
-
-static void
-remove_empty_loop (struct loop *loop)
-{
- edge exit = single_dom_exit (loop), non_exit;
- gimple cond_stmt = last_stmt (exit->src);
- basic_block *body;
- unsigned n_before, freq_in, freq_h;
- gcov_type exit_count = exit->count;
-
- if (dump_file)
- fprintf (dump_file, "Removing empty loop %d\n", loop->num);
-
- non_exit = EDGE_SUCC (exit->src, 0);
- if (non_exit == exit)
- non_exit = EDGE_SUCC (exit->src, 1);
-
- if (exit->flags & EDGE_TRUE_VALUE)
- gimple_cond_make_true (cond_stmt);
- else
- gimple_cond_make_false (cond_stmt);
- update_stmt (cond_stmt);
-
- /* Let us set the probabilities of the edges coming from the exit block. */
- exit->probability = REG_BR_PROB_BASE;
- non_exit->probability = 0;
- non_exit->count = 0;
-
- /* Update frequencies and counts. Everything before
- the exit needs to be scaled FREQ_IN/FREQ_H times,
- where FREQ_IN is the frequency of the entry edge
- and FREQ_H is the frequency of the loop header.
- Everything after the exit has zero frequency. */
- freq_h = loop->header->frequency;
- freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop));
- if (freq_h != 0)
- {
- body = get_loop_body_in_dom_order (loop);
- for (n_before = 1; n_before <= loop->num_nodes; n_before++)
- if (body[n_before - 1] == exit->src)
- break;
- scale_bbs_frequencies_int (body, n_before, freq_in, freq_h);
- scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before,
- 0, 1);
- free (body);
- }
-
- /* Number of executions of exit is not changed, thus we need to restore
- the original value. */
- exit->count = exit_count;
-}
-
-/* Removes LOOP if it is empty. Returns true if LOOP is removed. CHANGED
- is set to true if LOOP or any of its subloops is removed. */
+ while (changed
+ && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS));
-static bool
-try_remove_empty_loop (struct loop *loop, bool *changed)
-{
- bool nonempty_subloop = false;
- struct loop *sub;
-
- /* First, all subloops must be removed. */
- for (sub = loop->inner; sub; sub = sub->next)
- nonempty_subloop |= !try_remove_empty_loop (sub, changed);
-
- if (nonempty_subloop || !empty_loop_p (loop))
- return false;
-
- remove_empty_loop (loop);
- *changed = true;
- return true;
-}
-
-/* Remove the empty loops. */
-
-unsigned int
-remove_empty_loops (void)
-{
- bool changed = false;
- struct loop *loop;
-
- for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
- try_remove_empty_loop (loop, &changed);
-
- if (changed)
- {
- scev_reset ();
- return TODO_cleanup_cfg;
- }
return 0;
}
-
OSDN Git Service
