/* High-level loop manipulation functions.
|
/* High-level loop manipulation functions.
|
Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
|
Copyright (C) 2004, 2005, 2006, 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
|
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
|
under the terms of the GNU General Public License as published by the
|
Free Software Foundation; either version 3, or (at your option) any
|
Free Software Foundation; either version 3, or (at your option) any
|
later version.
|
later version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT
|
GCC is distributed in the hope that it will be useful, but WITHOUT
|
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
ANY 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 "tree.h"
|
#include "tree.h"
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "tm_p.h"
|
#include "tm_p.h"
|
#include "hard-reg-set.h"
|
#include "hard-reg-set.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "output.h"
|
#include "output.h"
|
#include "diagnostic.h"
|
#include "diagnostic.h"
|
#include "tree-flow.h"
|
#include "tree-flow.h"
|
#include "tree-dump.h"
|
#include "tree-dump.h"
|
#include "timevar.h"
|
#include "timevar.h"
|
#include "cfgloop.h"
|
#include "cfgloop.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
#include "cfglayout.h"
|
#include "cfglayout.h"
|
#include "tree-scalar-evolution.h"
|
#include "tree-scalar-evolution.h"
|
#include "params.h"
|
#include "params.h"
|
|
|
/* Creates an induction variable with value BASE + STEP * iteration in LOOP.
|
/* Creates an induction variable with value BASE + STEP * iteration in LOOP.
|
It is expected that neither BASE nor STEP are shared with other expressions
|
It is expected that neither BASE nor STEP are shared with other expressions
|
(unless the sharing rules allow this). Use VAR as a base var_decl for it
|
(unless the sharing rules allow this). Use VAR as a base var_decl for it
|
(if NULL, a new temporary will be created). The increment will occur at
|
(if NULL, a new temporary will be created). The increment will occur at
|
INCR_POS (after it if AFTER is true, before it otherwise). INCR_POS and
|
INCR_POS (after it if AFTER is true, before it otherwise). INCR_POS and
|
AFTER can be computed using standard_iv_increment_position. The ssa versions
|
AFTER can be computed using standard_iv_increment_position. The ssa versions
|
of the variable before and after increment will be stored in VAR_BEFORE and
|
of the variable before and after increment will be stored in VAR_BEFORE and
|
VAR_AFTER (unless they are NULL). */
|
VAR_AFTER (unless they are NULL). */
|
|
|
void
|
void
|
create_iv (tree base, tree step, tree var, struct loop *loop,
|
create_iv (tree base, tree step, tree var, struct loop *loop,
|
block_stmt_iterator *incr_pos, bool after,
|
block_stmt_iterator *incr_pos, bool after,
|
tree *var_before, tree *var_after)
|
tree *var_before, tree *var_after)
|
{
|
{
|
tree stmt, initial, step1, stmts;
|
tree stmt, initial, step1, stmts;
|
tree vb, va;
|
tree vb, va;
|
enum tree_code incr_op = PLUS_EXPR;
|
enum tree_code incr_op = PLUS_EXPR;
|
edge pe = loop_preheader_edge (loop);
|
edge pe = loop_preheader_edge (loop);
|
|
|
if (!var)
|
if (!var)
|
{
|
{
|
var = create_tmp_var (TREE_TYPE (base), "ivtmp");
|
var = create_tmp_var (TREE_TYPE (base), "ivtmp");
|
add_referenced_var (var);
|
add_referenced_var (var);
|
}
|
}
|
|
|
vb = make_ssa_name (var, NULL_TREE);
|
vb = make_ssa_name (var, NULL_TREE);
|
if (var_before)
|
if (var_before)
|
*var_before = vb;
|
*var_before = vb;
|
va = make_ssa_name (var, NULL_TREE);
|
va = make_ssa_name (var, NULL_TREE);
|
if (var_after)
|
if (var_after)
|
*var_after = va;
|
*var_after = va;
|
|
|
/* For easier readability of the created code, produce MINUS_EXPRs
|
/* For easier readability of the created code, produce MINUS_EXPRs
|
when suitable. */
|
when suitable. */
|
if (TREE_CODE (step) == INTEGER_CST)
|
if (TREE_CODE (step) == INTEGER_CST)
|
{
|
{
|
if (TYPE_UNSIGNED (TREE_TYPE (step)))
|
if (TYPE_UNSIGNED (TREE_TYPE (step)))
|
{
|
{
|
step1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
|
step1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
|
if (tree_int_cst_lt (step1, step))
|
if (tree_int_cst_lt (step1, step))
|
{
|
{
|
incr_op = MINUS_EXPR;
|
incr_op = MINUS_EXPR;
|
step = step1;
|
step = step1;
|
}
|
}
|
}
|
}
|
else
|
else
|
{
|
{
|
bool ovf;
|
bool ovf;
|
|
|
if (!tree_expr_nonnegative_warnv_p (step, &ovf)
|
if (!tree_expr_nonnegative_warnv_p (step, &ovf)
|
&& may_negate_without_overflow_p (step))
|
&& may_negate_without_overflow_p (step))
|
{
|
{
|
incr_op = MINUS_EXPR;
|
incr_op = MINUS_EXPR;
|
step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
|
step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* Gimplify the step if necessary. We put the computations in front of the
|
/* Gimplify the step if necessary. We put the computations in front of the
|
loop (i.e. the step should be loop invariant). */
|
loop (i.e. the step should be loop invariant). */
|
step = force_gimple_operand (step, &stmts, true, var);
|
step = force_gimple_operand (step, &stmts, true, var);
|
if (stmts)
|
if (stmts)
|
bsi_insert_on_edge_immediate_loop (pe, stmts);
|
bsi_insert_on_edge_immediate_loop (pe, stmts);
|
|
|
stmt = build2 (MODIFY_EXPR, void_type_node, va,
|
stmt = build2 (MODIFY_EXPR, void_type_node, va,
|
build2 (incr_op, TREE_TYPE (base),
|
build2 (incr_op, TREE_TYPE (base),
|
vb, step));
|
vb, step));
|
SSA_NAME_DEF_STMT (va) = stmt;
|
SSA_NAME_DEF_STMT (va) = stmt;
|
if (after)
|
if (after)
|
bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT);
|
bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT);
|
else
|
else
|
bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT);
|
bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT);
|
|
|
initial = force_gimple_operand (base, &stmts, true, var);
|
initial = force_gimple_operand (base, &stmts, true, var);
|
if (stmts)
|
if (stmts)
|
bsi_insert_on_edge_immediate_loop (pe, stmts);
|
bsi_insert_on_edge_immediate_loop (pe, stmts);
|
|
|
stmt = create_phi_node (vb, loop->header);
|
stmt = create_phi_node (vb, loop->header);
|
SSA_NAME_DEF_STMT (vb) = stmt;
|
SSA_NAME_DEF_STMT (vb) = stmt;
|
add_phi_arg (stmt, initial, loop_preheader_edge (loop));
|
add_phi_arg (stmt, initial, loop_preheader_edge (loop));
|
add_phi_arg (stmt, va, loop_latch_edge (loop));
|
add_phi_arg (stmt, va, loop_latch_edge (loop));
|
}
|
}
|
|
|
/* Add exit phis for the USE on EXIT. */
|
/* Add exit phis for the USE on EXIT. */
|
|
|
static void
|
static void
|
add_exit_phis_edge (basic_block exit, tree use)
|
add_exit_phis_edge (basic_block exit, tree use)
|
{
|
{
|
tree phi, def_stmt = SSA_NAME_DEF_STMT (use);
|
tree phi, def_stmt = SSA_NAME_DEF_STMT (use);
|
basic_block def_bb = bb_for_stmt (def_stmt);
|
basic_block def_bb = bb_for_stmt (def_stmt);
|
struct loop *def_loop;
|
struct loop *def_loop;
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
/* Check that some of the edges entering the EXIT block exits a loop in
|
/* Check that some of the edges entering the EXIT block exits a loop in
|
that USE is defined. */
|
that USE is defined. */
|
FOR_EACH_EDGE (e, ei, exit->preds)
|
FOR_EACH_EDGE (e, ei, exit->preds)
|
{
|
{
|
def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father);
|
def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father);
|
if (!flow_bb_inside_loop_p (def_loop, e->dest))
|
if (!flow_bb_inside_loop_p (def_loop, e->dest))
|
break;
|
break;
|
}
|
}
|
|
|
if (!e)
|
if (!e)
|
return;
|
return;
|
|
|
phi = create_phi_node (use, exit);
|
phi = create_phi_node (use, exit);
|
create_new_def_for (PHI_RESULT (phi), phi, PHI_RESULT_PTR (phi));
|
create_new_def_for (PHI_RESULT (phi), phi, PHI_RESULT_PTR (phi));
|
FOR_EACH_EDGE (e, ei, exit->preds)
|
FOR_EACH_EDGE (e, ei, exit->preds)
|
add_phi_arg (phi, use, e);
|
add_phi_arg (phi, use, e);
|
}
|
}
|
|
|
/* Add exit phis for VAR that is used in LIVEIN.
|
/* Add exit phis for VAR that is used in LIVEIN.
|
Exits of the loops are stored in EXITS. */
|
Exits of the loops are stored in EXITS. */
|
|
|
static void
|
static void
|
add_exit_phis_var (tree var, bitmap livein, bitmap exits)
|
add_exit_phis_var (tree var, bitmap livein, bitmap exits)
|
{
|
{
|
bitmap def;
|
bitmap def;
|
unsigned index;
|
unsigned index;
|
basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
|
basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
|
|
if (is_gimple_reg (var))
|
if (is_gimple_reg (var))
|
bitmap_clear_bit (livein, def_bb->index);
|
bitmap_clear_bit (livein, def_bb->index);
|
else
|
else
|
bitmap_set_bit (livein, def_bb->index);
|
bitmap_set_bit (livein, def_bb->index);
|
|
|
def = BITMAP_ALLOC (NULL);
|
def = BITMAP_ALLOC (NULL);
|
bitmap_set_bit (def, def_bb->index);
|
bitmap_set_bit (def, def_bb->index);
|
compute_global_livein (livein, def);
|
compute_global_livein (livein, def);
|
BITMAP_FREE (def);
|
BITMAP_FREE (def);
|
|
|
EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi)
|
EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi)
|
{
|
{
|
add_exit_phis_edge (BASIC_BLOCK (index), var);
|
add_exit_phis_edge (BASIC_BLOCK (index), var);
|
}
|
}
|
}
|
}
|
|
|
/* Add exit phis for the names marked in NAMES_TO_RENAME.
|
/* Add exit phis for the names marked in NAMES_TO_RENAME.
|
Exits of the loops are stored in EXITS. Sets of blocks where the ssa
|
Exits of the loops are stored in EXITS. Sets of blocks where the ssa
|
names are used are stored in USE_BLOCKS. */
|
names are used are stored in USE_BLOCKS. */
|
|
|
static void
|
static void
|
add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits)
|
add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
|
|
EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
|
{
|
{
|
add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
|
add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
|
}
|
}
|
}
|
}
|
|
|
/* Returns a bitmap of all loop exit edge targets. */
|
/* Returns a bitmap of all loop exit edge targets. */
|
|
|
static bitmap
|
static bitmap
|
get_loops_exits (void)
|
get_loops_exits (void)
|
{
|
{
|
bitmap exits = BITMAP_ALLOC (NULL);
|
bitmap exits = BITMAP_ALLOC (NULL);
|
basic_block bb;
|
basic_block bb;
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
if (e->src != ENTRY_BLOCK_PTR
|
if (e->src != ENTRY_BLOCK_PTR
|
&& !flow_bb_inside_loop_p (e->src->loop_father, bb))
|
&& !flow_bb_inside_loop_p (e->src->loop_father, bb))
|
{
|
{
|
bitmap_set_bit (exits, bb->index);
|
bitmap_set_bit (exits, bb->index);
|
break;
|
break;
|
}
|
}
|
}
|
}
|
|
|
return exits;
|
return exits;
|
}
|
}
|
|
|
/* For USE in BB, if it is used outside of the loop it is defined in,
|
/* For USE in BB, if it is used outside of the loop it is defined in,
|
mark it for rewrite. Record basic block BB where it is used
|
mark it for rewrite. Record basic block BB where it is used
|
to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap. */
|
to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap. */
|
|
|
static void
|
static void
|
find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks,
|
find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks,
|
bitmap need_phis)
|
bitmap need_phis)
|
{
|
{
|
unsigned ver;
|
unsigned ver;
|
basic_block def_bb;
|
basic_block def_bb;
|
struct loop *def_loop;
|
struct loop *def_loop;
|
|
|
if (TREE_CODE (use) != SSA_NAME)
|
if (TREE_CODE (use) != SSA_NAME)
|
return;
|
return;
|
|
|
/* We don't need to keep virtual operands in loop-closed form. */
|
/* We don't need to keep virtual operands in loop-closed form. */
|
if (!is_gimple_reg (use))
|
if (!is_gimple_reg (use))
|
return;
|
return;
|
|
|
ver = SSA_NAME_VERSION (use);
|
ver = SSA_NAME_VERSION (use);
|
def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
|
def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
|
if (!def_bb)
|
if (!def_bb)
|
return;
|
return;
|
def_loop = def_bb->loop_father;
|
def_loop = def_bb->loop_father;
|
|
|
/* If the definition is not inside loop, it is not interesting. */
|
/* If the definition is not inside loop, it is not interesting. */
|
if (!def_loop->outer)
|
if (!def_loop->outer)
|
return;
|
return;
|
|
|
if (!use_blocks[ver])
|
if (!use_blocks[ver])
|
use_blocks[ver] = BITMAP_ALLOC (NULL);
|
use_blocks[ver] = BITMAP_ALLOC (NULL);
|
bitmap_set_bit (use_blocks[ver], bb->index);
|
bitmap_set_bit (use_blocks[ver], bb->index);
|
|
|
bitmap_set_bit (need_phis, ver);
|
bitmap_set_bit (need_phis, ver);
|
}
|
}
|
|
|
/* For uses in STMT, mark names that are used outside of the loop they are
|
/* For uses in STMT, mark names that are used outside of the loop they are
|
defined to rewrite. Record the set of blocks in that the ssa
|
defined to rewrite. Record the set of blocks in that the ssa
|
names are defined to USE_BLOCKS and the ssa names themselves to
|
names are defined to USE_BLOCKS and the ssa names themselves to
|
NEED_PHIS. */
|
NEED_PHIS. */
|
|
|
static void
|
static void
|
find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks, bitmap need_phis)
|
find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks, bitmap need_phis)
|
{
|
{
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
tree var;
|
tree var;
|
basic_block bb = bb_for_stmt (stmt);
|
basic_block bb = bb_for_stmt (stmt);
|
|
|
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
|
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
|
find_uses_to_rename_use (bb, var, use_blocks, need_phis);
|
find_uses_to_rename_use (bb, var, use_blocks, need_phis);
|
}
|
}
|
|
|
/* Marks names that are used in BB and outside of the loop they are
|
/* Marks names that are used in BB and outside of the loop they are
|
defined in for rewrite. Records the set of blocks in that the ssa
|
defined in for rewrite. Records the set of blocks in that the ssa
|
names are defined to USE_BLOCKS. Record the SSA names that will
|
names are defined to USE_BLOCKS. Record the SSA names that will
|
need exit PHIs in NEED_PHIS. */
|
need exit PHIs in NEED_PHIS. */
|
|
|
static void
|
static void
|
find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis)
|
find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis)
|
{
|
{
|
block_stmt_iterator bsi;
|
block_stmt_iterator bsi;
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
tree phi;
|
tree phi;
|
|
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
|
find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
|
find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
|
use_blocks, need_phis);
|
use_blocks, need_phis);
|
|
|
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
|
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
|
find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks, need_phis);
|
find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks, need_phis);
|
}
|
}
|
|
|
/* Marks names that are used outside of the loop they are defined in
|
/* Marks names that are used outside of the loop they are defined in
|
for rewrite. Records the set of blocks in that the ssa
|
for rewrite. Records the set of blocks in that the ssa
|
names are defined to USE_BLOCKS. If CHANGED_BBS is not NULL,
|
names are defined to USE_BLOCKS. If CHANGED_BBS is not NULL,
|
scan only blocks in this set. */
|
scan only blocks in this set. */
|
|
|
static void
|
static void
|
find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis)
|
find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
unsigned index;
|
unsigned index;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
|
|
if (changed_bbs && !bitmap_empty_p (changed_bbs))
|
if (changed_bbs && !bitmap_empty_p (changed_bbs))
|
{
|
{
|
EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi)
|
EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi)
|
{
|
{
|
find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks, need_phis);
|
find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks, need_phis);
|
}
|
}
|
}
|
}
|
else
|
else
|
{
|
{
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
find_uses_to_rename_bb (bb, use_blocks, need_phis);
|
find_uses_to_rename_bb (bb, use_blocks, need_phis);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
|
/* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
|
phi nodes to ensure that no variable is used outside the loop it is
|
phi nodes to ensure that no variable is used outside the loop it is
|
defined in.
|
defined in.
|
|
|
This strengthening of the basic ssa form has several advantages:
|
This strengthening of the basic ssa form has several advantages:
|
|
|
1) Updating it during unrolling/peeling/versioning is trivial, since
|
1) Updating it during unrolling/peeling/versioning is trivial, since
|
we do not need to care about the uses outside of the loop.
|
we do not need to care about the uses outside of the loop.
|
2) The behavior of all uses of an induction variable is the same.
|
2) The behavior of all uses of an induction variable is the same.
|
Without this, you need to distinguish the case when the variable
|
Without this, you need to distinguish the case when the variable
|
is used outside of the loop it is defined in, for example
|
is used outside of the loop it is defined in, for example
|
|
|
for (i = 0; i < 100; i++)
|
for (i = 0; i < 100; i++)
|
{
|
{
|
for (j = 0; j < 100; j++)
|
for (j = 0; j < 100; j++)
|
{
|
{
|
k = i + j;
|
k = i + j;
|
use1 (k);
|
use1 (k);
|
}
|
}
|
use2 (k);
|
use2 (k);
|
}
|
}
|
|
|
Looking from the outer loop with the normal SSA form, the first use of k
|
Looking from the outer loop with the normal SSA form, the first use of k
|
is not well-behaved, while the second one is an induction variable with
|
is not well-behaved, while the second one is an induction variable with
|
base 99 and step 1.
|
base 99 and step 1.
|
|
|
If CHANGED_BBS is not NULL, we look for uses outside loops only in
|
If CHANGED_BBS is not NULL, we look for uses outside loops only in
|
the basic blocks in this set.
|
the basic blocks in this set.
|
|
|
UPDATE_FLAG is used in the call to update_ssa. See
|
UPDATE_FLAG is used in the call to update_ssa. See
|
TODO_update_ssa* for documentation. */
|
TODO_update_ssa* for documentation. */
|
|
|
void
|
void
|
rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
|
rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
|
{
|
{
|
bitmap loop_exits = get_loops_exits ();
|
bitmap loop_exits = get_loops_exits ();
|
bitmap *use_blocks;
|
bitmap *use_blocks;
|
unsigned i, old_num_ssa_names;
|
unsigned i, old_num_ssa_names;
|
bitmap names_to_rename = BITMAP_ALLOC (NULL);
|
bitmap names_to_rename = BITMAP_ALLOC (NULL);
|
|
|
/* If the pass has caused the SSA form to be out-of-date, update it
|
/* If the pass has caused the SSA form to be out-of-date, update it
|
now. */
|
now. */
|
update_ssa (update_flag);
|
update_ssa (update_flag);
|
|
|
old_num_ssa_names = num_ssa_names;
|
old_num_ssa_names = num_ssa_names;
|
use_blocks = XCNEWVEC (bitmap, old_num_ssa_names);
|
use_blocks = XCNEWVEC (bitmap, old_num_ssa_names);
|
|
|
/* Find the uses outside loops. */
|
/* Find the uses outside loops. */
|
find_uses_to_rename (changed_bbs, use_blocks, names_to_rename);
|
find_uses_to_rename (changed_bbs, use_blocks, names_to_rename);
|
|
|
/* Add the PHI nodes on exits of the loops for the names we need to
|
/* Add the PHI nodes on exits of the loops for the names we need to
|
rewrite. */
|
rewrite. */
|
add_exit_phis (names_to_rename, use_blocks, loop_exits);
|
add_exit_phis (names_to_rename, use_blocks, loop_exits);
|
|
|
for (i = 0; i < old_num_ssa_names; i++)
|
for (i = 0; i < old_num_ssa_names; i++)
|
BITMAP_FREE (use_blocks[i]);
|
BITMAP_FREE (use_blocks[i]);
|
free (use_blocks);
|
free (use_blocks);
|
BITMAP_FREE (loop_exits);
|
BITMAP_FREE (loop_exits);
|
BITMAP_FREE (names_to_rename);
|
BITMAP_FREE (names_to_rename);
|
|
|
/* Fix up all the names found to be used outside their original
|
/* Fix up all the names found to be used outside their original
|
loops. */
|
loops. */
|
update_ssa (TODO_update_ssa);
|
update_ssa (TODO_update_ssa);
|
}
|
}
|
|
|
/* Check invariants of the loop closed ssa form for the USE in BB. */
|
/* Check invariants of the loop closed ssa form for the USE in BB. */
|
|
|
static void
|
static void
|
check_loop_closed_ssa_use (basic_block bb, tree use)
|
check_loop_closed_ssa_use (basic_block bb, tree use)
|
{
|
{
|
tree def;
|
tree def;
|
basic_block def_bb;
|
basic_block def_bb;
|
|
|
if (TREE_CODE (use) != SSA_NAME || !is_gimple_reg (use))
|
if (TREE_CODE (use) != SSA_NAME || !is_gimple_reg (use))
|
return;
|
return;
|
|
|
def = SSA_NAME_DEF_STMT (use);
|
def = SSA_NAME_DEF_STMT (use);
|
def_bb = bb_for_stmt (def);
|
def_bb = bb_for_stmt (def);
|
gcc_assert (!def_bb
|
gcc_assert (!def_bb
|
|| flow_bb_inside_loop_p (def_bb->loop_father, bb));
|
|| flow_bb_inside_loop_p (def_bb->loop_father, bb));
|
}
|
}
|
|
|
/* Checks invariants of loop closed ssa form in statement STMT in BB. */
|
/* Checks invariants of loop closed ssa form in statement STMT in BB. */
|
|
|
static void
|
static void
|
check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
|
check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
|
{
|
{
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
tree var;
|
tree var;
|
|
|
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
|
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
|
check_loop_closed_ssa_use (bb, var);
|
check_loop_closed_ssa_use (bb, var);
|
}
|
}
|
|
|
/* Checks that invariants of the loop closed ssa form are preserved. */
|
/* Checks that invariants of the loop closed ssa form are preserved. */
|
|
|
void
|
void
|
verify_loop_closed_ssa (void)
|
verify_loop_closed_ssa (void)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
block_stmt_iterator bsi;
|
block_stmt_iterator bsi;
|
tree phi;
|
tree phi;
|
unsigned i;
|
unsigned i;
|
|
|
if (current_loops == NULL)
|
if (current_loops == NULL)
|
return;
|
return;
|
|
|
verify_ssa (false);
|
verify_ssa (false);
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
|
for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
|
check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
|
check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
|
PHI_ARG_DEF (phi, i));
|
PHI_ARG_DEF (phi, i));
|
|
|
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
|
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
|
check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
|
check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
|
}
|
}
|
}
|
}
|
|
|
/* Split loop exit edge EXIT. The things are a bit complicated by a need to
|
/* Split loop exit edge EXIT. The things are a bit complicated by a need to
|
preserve the loop closed ssa form. */
|
preserve the loop closed ssa form. */
|
|
|
void
|
void
|
split_loop_exit_edge (edge exit)
|
split_loop_exit_edge (edge exit)
|
{
|
{
|
basic_block dest = exit->dest;
|
basic_block dest = exit->dest;
|
basic_block bb = loop_split_edge_with (exit, NULL);
|
basic_block bb = loop_split_edge_with (exit, NULL);
|
tree phi, new_phi, new_name, name;
|
tree phi, new_phi, new_name, name;
|
use_operand_p op_p;
|
use_operand_p op_p;
|
|
|
for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
|
{
|
{
|
op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb));
|
op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb));
|
|
|
name = USE_FROM_PTR (op_p);
|
name = USE_FROM_PTR (op_p);
|
|
|
/* If the argument of the phi node is a constant, we do not need
|
/* If the argument of the phi node is a constant, we do not need
|
to keep it inside loop. */
|
to keep it inside loop. */
|
if (TREE_CODE (name) != SSA_NAME)
|
if (TREE_CODE (name) != SSA_NAME)
|
continue;
|
continue;
|
|
|
/* Otherwise create an auxiliary phi node that will copy the value
|
/* Otherwise create an auxiliary phi node that will copy the value
|
of the ssa name out of the loop. */
|
of the ssa name out of the loop. */
|
new_name = duplicate_ssa_name (name, NULL);
|
new_name = duplicate_ssa_name (name, NULL);
|
new_phi = create_phi_node (new_name, bb);
|
new_phi = create_phi_node (new_name, bb);
|
SSA_NAME_DEF_STMT (new_name) = new_phi;
|
SSA_NAME_DEF_STMT (new_name) = new_phi;
|
add_phi_arg (new_phi, name, exit);
|
add_phi_arg (new_phi, name, exit);
|
SET_USE (op_p, new_name);
|
SET_USE (op_p, new_name);
|
}
|
}
|
}
|
}
|
|
|
/* Insert statement STMT to the edge E and update the loop structures.
|
/* Insert statement STMT to the edge E and update the loop structures.
|
Returns the newly created block (if any). */
|
Returns the newly created block (if any). */
|
|
|
basic_block
|
basic_block
|
bsi_insert_on_edge_immediate_loop (edge e, tree stmt)
|
bsi_insert_on_edge_immediate_loop (edge e, tree stmt)
|
{
|
{
|
basic_block src, dest, new_bb;
|
basic_block src, dest, new_bb;
|
struct loop *loop_c;
|
struct loop *loop_c;
|
|
|
src = e->src;
|
src = e->src;
|
dest = e->dest;
|
dest = e->dest;
|
|
|
loop_c = find_common_loop (src->loop_father, dest->loop_father);
|
loop_c = find_common_loop (src->loop_father, dest->loop_father);
|
|
|
new_bb = bsi_insert_on_edge_immediate (e, stmt);
|
new_bb = bsi_insert_on_edge_immediate (e, stmt);
|
|
|
if (!new_bb)
|
if (!new_bb)
|
return NULL;
|
return NULL;
|
|
|
add_bb_to_loop (new_bb, loop_c);
|
add_bb_to_loop (new_bb, loop_c);
|
if (dest->loop_father->latch == src)
|
if (dest->loop_father->latch == src)
|
dest->loop_father->latch = new_bb;
|
dest->loop_father->latch = new_bb;
|
|
|
return new_bb;
|
return new_bb;
|
}
|
}
|
|
|
/* Returns the basic block in that statements should be emitted for induction
|
/* Returns the basic block in that statements should be emitted for induction
|
variables incremented at the end of the LOOP. */
|
variables incremented at the end of the LOOP. */
|
|
|
basic_block
|
basic_block
|
ip_end_pos (struct loop *loop)
|
ip_end_pos (struct loop *loop)
|
{
|
{
|
return loop->latch;
|
return loop->latch;
|
}
|
}
|
|
|
/* Returns the basic block in that statements should be emitted for induction
|
/* Returns the basic block in that statements should be emitted for induction
|
variables incremented just before exit condition of a LOOP. */
|
variables incremented just before exit condition of a LOOP. */
|
|
|
basic_block
|
basic_block
|
ip_normal_pos (struct loop *loop)
|
ip_normal_pos (struct loop *loop)
|
{
|
{
|
tree last;
|
tree last;
|
basic_block bb;
|
basic_block bb;
|
edge exit;
|
edge exit;
|
|
|
if (!single_pred_p (loop->latch))
|
if (!single_pred_p (loop->latch))
|
return NULL;
|
return NULL;
|
|
|
bb = single_pred (loop->latch);
|
bb = single_pred (loop->latch);
|
last = last_stmt (bb);
|
last = last_stmt (bb);
|
if (TREE_CODE (last) != COND_EXPR)
|
if (TREE_CODE (last) != COND_EXPR)
|
return NULL;
|
return NULL;
|
|
|
exit = EDGE_SUCC (bb, 0);
|
exit = EDGE_SUCC (bb, 0);
|
if (exit->dest == loop->latch)
|
if (exit->dest == loop->latch)
|
exit = EDGE_SUCC (bb, 1);
|
exit = EDGE_SUCC (bb, 1);
|
|
|
if (flow_bb_inside_loop_p (loop, exit->dest))
|
if (flow_bb_inside_loop_p (loop, exit->dest))
|
return NULL;
|
return NULL;
|
|
|
return bb;
|
return bb;
|
}
|
}
|
|
|
/* Stores the standard position for induction variable increment in LOOP
|
/* Stores the standard position for induction variable increment in LOOP
|
(just before the exit condition if it is available and latch block is empty,
|
(just before the exit condition if it is available and latch block is empty,
|
end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if
|
end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if
|
the increment should be inserted after *BSI. */
|
the increment should be inserted after *BSI. */
|
|
|
void
|
void
|
standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi,
|
standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi,
|
bool *insert_after)
|
bool *insert_after)
|
{
|
{
|
basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
|
basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
|
tree last = last_stmt (latch);
|
tree last = last_stmt (latch);
|
|
|
if (!bb
|
if (!bb
|
|| (last && TREE_CODE (last) != LABEL_EXPR))
|
|| (last && TREE_CODE (last) != LABEL_EXPR))
|
{
|
{
|
*bsi = bsi_last (latch);
|
*bsi = bsi_last (latch);
|
*insert_after = true;
|
*insert_after = true;
|
}
|
}
|
else
|
else
|
{
|
{
|
*bsi = bsi_last (bb);
|
*bsi = bsi_last (bb);
|
*insert_after = false;
|
*insert_after = false;
|
}
|
}
|
}
|
}
|
|
|
/* Copies phi node arguments for duplicated blocks. The index of the first
|
/* Copies phi node arguments for duplicated blocks. The index of the first
|
duplicated block is FIRST_NEW_BLOCK. */
|
duplicated block is FIRST_NEW_BLOCK. */
|
|
|
static void
|
static void
|
copy_phi_node_args (unsigned first_new_block)
|
copy_phi_node_args (unsigned first_new_block)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
|
|
for (i = first_new_block; i < (unsigned) last_basic_block; i++)
|
for (i = first_new_block; i < (unsigned) last_basic_block; i++)
|
BASIC_BLOCK (i)->flags |= BB_DUPLICATED;
|
BASIC_BLOCK (i)->flags |= BB_DUPLICATED;
|
|
|
for (i = first_new_block; i < (unsigned) last_basic_block; i++)
|
for (i = first_new_block; i < (unsigned) last_basic_block; i++)
|
add_phi_args_after_copy_bb (BASIC_BLOCK (i));
|
add_phi_args_after_copy_bb (BASIC_BLOCK (i));
|
|
|
for (i = first_new_block; i < (unsigned) last_basic_block; i++)
|
for (i = first_new_block; i < (unsigned) last_basic_block; i++)
|
BASIC_BLOCK (i)->flags &= ~BB_DUPLICATED;
|
BASIC_BLOCK (i)->flags &= ~BB_DUPLICATED;
|
}
|
}
|
|
|
|
|
/* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also
|
/* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also
|
updates the PHI nodes at start of the copied region. In order to
|
updates the PHI nodes at start of the copied region. In order to
|
achieve this, only loops whose exits all lead to the same location
|
achieve this, only loops whose exits all lead to the same location
|
are handled.
|
are handled.
|
|
|
Notice that we do not completely update the SSA web after
|
Notice that we do not completely update the SSA web after
|
duplication. The caller is responsible for calling update_ssa
|
duplication. The caller is responsible for calling update_ssa
|
after the loop has been duplicated. */
|
after the loop has been duplicated. */
|
|
|
bool
|
bool
|
tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
|
tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
|
struct loops *loops,
|
struct loops *loops,
|
unsigned int ndupl, sbitmap wont_exit,
|
unsigned int ndupl, sbitmap wont_exit,
|
edge orig, edge *to_remove,
|
edge orig, edge *to_remove,
|
unsigned int *n_to_remove, int flags)
|
unsigned int *n_to_remove, int flags)
|
{
|
{
|
unsigned first_new_block;
|
unsigned first_new_block;
|
|
|
if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
|
if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
|
return false;
|
return false;
|
if (!(loops->state & LOOPS_HAVE_PREHEADERS))
|
if (!(loops->state & LOOPS_HAVE_PREHEADERS))
|
return false;
|
return false;
|
|
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
verify_loop_closed_ssa ();
|
verify_loop_closed_ssa ();
|
#endif
|
#endif
|
|
|
first_new_block = last_basic_block;
|
first_new_block = last_basic_block;
|
if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit,
|
if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit,
|
orig, to_remove, n_to_remove, flags))
|
orig, to_remove, n_to_remove, flags))
|
return false;
|
return false;
|
|
|
/* Readd the removed phi args for e. */
|
/* Readd the removed phi args for e. */
|
flush_pending_stmts (e);
|
flush_pending_stmts (e);
|
|
|
/* Copy the phi node arguments. */
|
/* Copy the phi node arguments. */
|
copy_phi_node_args (first_new_block);
|
copy_phi_node_args (first_new_block);
|
|
|
scev_reset ();
|
scev_reset ();
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Build if (COND) goto THEN_LABEL; else goto ELSE_LABEL; */
|
/* Build if (COND) goto THEN_LABEL; else goto ELSE_LABEL; */
|
|
|
static tree
|
static tree
|
build_if_stmt (tree cond, tree then_label, tree else_label)
|
build_if_stmt (tree cond, tree then_label, tree else_label)
|
{
|
{
|
return build3 (COND_EXPR, void_type_node,
|
return build3 (COND_EXPR, void_type_node,
|
cond,
|
cond,
|
build1 (GOTO_EXPR, void_type_node, then_label),
|
build1 (GOTO_EXPR, void_type_node, then_label),
|
build1 (GOTO_EXPR, void_type_node, else_label));
|
build1 (GOTO_EXPR, void_type_node, else_label));
|
}
|
}
|
|
|
/* Returns true if we can unroll LOOP FACTOR times. Number
|
/* Returns true if we can unroll LOOP FACTOR times. Number
|
of iterations of the loop is returned in NITER. */
|
of iterations of the loop is returned in NITER. */
|
|
|
bool
|
bool
|
can_unroll_loop_p (struct loop *loop, unsigned factor,
|
can_unroll_loop_p (struct loop *loop, unsigned factor,
|
struct tree_niter_desc *niter)
|
struct tree_niter_desc *niter)
|
{
|
{
|
edge exit;
|
edge exit;
|
|
|
/* Check whether unrolling is possible. We only want to unroll loops
|
/* Check whether unrolling is possible. We only want to unroll loops
|
for that we are able to determine number of iterations. We also
|
for that we are able to determine number of iterations. We also
|
want to split the extra iterations of the loop from its end,
|
want to split the extra iterations of the loop from its end,
|
therefore we require that the loop has precisely one
|
therefore we require that the loop has precisely one
|
exit. */
|
exit. */
|
|
|
exit = single_dom_exit (loop);
|
exit = single_dom_exit (loop);
|
if (!exit)
|
if (!exit)
|
return false;
|
return false;
|
|
|
if (!number_of_iterations_exit (loop, exit, niter, false)
|
if (!number_of_iterations_exit (loop, exit, niter, false)
|
|| niter->cmp == ERROR_MARK
|
|| niter->cmp == ERROR_MARK
|
/* Scalar evolutions analysis might have copy propagated
|
/* Scalar evolutions analysis might have copy propagated
|
the abnormal ssa names into these expressions, hence
|
the abnormal ssa names into these expressions, hence
|
emiting the computations based on them during loop
|
emiting the computations based on them during loop
|
unrolling might create overlapping life ranges for
|
unrolling might create overlapping life ranges for
|
them, and failures in out-of-ssa. */
|
them, and failures in out-of-ssa. */
|
|| contains_abnormal_ssa_name_p (niter->may_be_zero)
|
|| contains_abnormal_ssa_name_p (niter->may_be_zero)
|
|| contains_abnormal_ssa_name_p (niter->control.base)
|
|| contains_abnormal_ssa_name_p (niter->control.base)
|
|| contains_abnormal_ssa_name_p (niter->control.step)
|
|| contains_abnormal_ssa_name_p (niter->control.step)
|
|| contains_abnormal_ssa_name_p (niter->bound))
|
|| contains_abnormal_ssa_name_p (niter->bound))
|
return false;
|
return false;
|
|
|
/* And of course, we must be able to duplicate the loop. */
|
/* And of course, we must be able to duplicate the loop. */
|
if (!can_duplicate_loop_p (loop))
|
if (!can_duplicate_loop_p (loop))
|
return false;
|
return false;
|
|
|
/* The final loop should be small enough. */
|
/* The final loop should be small enough. */
|
if (tree_num_loop_insns (loop) * factor
|
if (tree_num_loop_insns (loop) * factor
|
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS))
|
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS))
|
return false;
|
return false;
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Determines the conditions that control execution of LOOP unrolled FACTOR
|
/* Determines the conditions that control execution of LOOP unrolled FACTOR
|
times. DESC is number of iterations of LOOP. ENTER_COND is set to
|
times. DESC is number of iterations of LOOP. ENTER_COND is set to
|
condition that must be true if the main loop can be entered.
|
condition that must be true if the main loop can be entered.
|
EXIT_BASE, EXIT_STEP, EXIT_CMP and EXIT_BOUND are set to values describing
|
EXIT_BASE, EXIT_STEP, EXIT_CMP and EXIT_BOUND are set to values describing
|
how the exit from the unrolled loop should be controlled. */
|
how the exit from the unrolled loop should be controlled. */
|
|
|
static void
|
static void
|
determine_exit_conditions (struct loop *loop, struct tree_niter_desc *desc,
|
determine_exit_conditions (struct loop *loop, struct tree_niter_desc *desc,
|
unsigned factor, tree *enter_cond,
|
unsigned factor, tree *enter_cond,
|
tree *exit_base, tree *exit_step,
|
tree *exit_base, tree *exit_step,
|
enum tree_code *exit_cmp, tree *exit_bound)
|
enum tree_code *exit_cmp, tree *exit_bound)
|
{
|
{
|
tree stmts;
|
tree stmts;
|
tree base = desc->control.base;
|
tree base = desc->control.base;
|
tree step = desc->control.step;
|
tree step = desc->control.step;
|
tree bound = desc->bound;
|
tree bound = desc->bound;
|
tree type = TREE_TYPE (base);
|
tree type = TREE_TYPE (base);
|
tree bigstep, delta;
|
tree bigstep, delta;
|
tree min = lower_bound_in_type (type, type);
|
tree min = lower_bound_in_type (type, type);
|
tree max = upper_bound_in_type (type, type);
|
tree max = upper_bound_in_type (type, type);
|
enum tree_code cmp = desc->cmp;
|
enum tree_code cmp = desc->cmp;
|
tree cond = boolean_true_node, assum;
|
tree cond = boolean_true_node, assum;
|
|
|
*enter_cond = boolean_false_node;
|
*enter_cond = boolean_false_node;
|
*exit_base = NULL_TREE;
|
*exit_base = NULL_TREE;
|
*exit_step = NULL_TREE;
|
*exit_step = NULL_TREE;
|
*exit_cmp = ERROR_MARK;
|
*exit_cmp = ERROR_MARK;
|
*exit_bound = NULL_TREE;
|
*exit_bound = NULL_TREE;
|
gcc_assert (cmp != ERROR_MARK);
|
gcc_assert (cmp != ERROR_MARK);
|
|
|
/* We only need to be correct when we answer question
|
/* We only need to be correct when we answer question
|
"Do at least FACTOR more iterations remain?" in the unrolled loop.
|
"Do at least FACTOR more iterations remain?" in the unrolled loop.
|
Thus, transforming BASE + STEP * i <> BOUND to
|
Thus, transforming BASE + STEP * i <> BOUND to
|
BASE + STEP * i < BOUND is ok. */
|
BASE + STEP * i < BOUND is ok. */
|
if (cmp == NE_EXPR)
|
if (cmp == NE_EXPR)
|
{
|
{
|
if (tree_int_cst_sign_bit (step))
|
if (tree_int_cst_sign_bit (step))
|
cmp = GT_EXPR;
|
cmp = GT_EXPR;
|
else
|
else
|
cmp = LT_EXPR;
|
cmp = LT_EXPR;
|
}
|
}
|
else if (cmp == LT_EXPR)
|
else if (cmp == LT_EXPR)
|
{
|
{
|
gcc_assert (!tree_int_cst_sign_bit (step));
|
gcc_assert (!tree_int_cst_sign_bit (step));
|
}
|
}
|
else if (cmp == GT_EXPR)
|
else if (cmp == GT_EXPR)
|
{
|
{
|
gcc_assert (tree_int_cst_sign_bit (step));
|
gcc_assert (tree_int_cst_sign_bit (step));
|
}
|
}
|
else
|
else
|
gcc_unreachable ();
|
gcc_unreachable ();
|
|
|
/* The main body of the loop may be entered iff:
|
/* The main body of the loop may be entered iff:
|
|
|
1) desc->may_be_zero is false.
|
1) desc->may_be_zero is false.
|
2) it is possible to check that there are at least FACTOR iterations
|
2) it is possible to check that there are at least FACTOR iterations
|
of the loop, i.e., BOUND - step * FACTOR does not overflow.
|
of the loop, i.e., BOUND - step * FACTOR does not overflow.
|
3) # of iterations is at least FACTOR */
|
3) # of iterations is at least FACTOR */
|
|
|
if (!zero_p (desc->may_be_zero))
|
if (!zero_p (desc->may_be_zero))
|
cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
|
cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
|
invert_truthvalue (desc->may_be_zero),
|
invert_truthvalue (desc->may_be_zero),
|
cond);
|
cond);
|
|
|
bigstep = fold_build2 (MULT_EXPR, type, step,
|
bigstep = fold_build2 (MULT_EXPR, type, step,
|
build_int_cst_type (type, factor));
|
build_int_cst_type (type, factor));
|
delta = fold_build2 (MINUS_EXPR, type, bigstep, step);
|
delta = fold_build2 (MINUS_EXPR, type, bigstep, step);
|
if (cmp == LT_EXPR)
|
if (cmp == LT_EXPR)
|
assum = fold_build2 (GE_EXPR, boolean_type_node,
|
assum = fold_build2 (GE_EXPR, boolean_type_node,
|
bound,
|
bound,
|
fold_build2 (PLUS_EXPR, type, min, delta));
|
fold_build2 (PLUS_EXPR, type, min, delta));
|
else
|
else
|
assum = fold_build2 (LE_EXPR, boolean_type_node,
|
assum = fold_build2 (LE_EXPR, boolean_type_node,
|
bound,
|
bound,
|
fold_build2 (PLUS_EXPR, type, max, delta));
|
fold_build2 (PLUS_EXPR, type, max, delta));
|
cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
|
cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
|
|
|
bound = fold_build2 (MINUS_EXPR, type, bound, delta);
|
bound = fold_build2 (MINUS_EXPR, type, bound, delta);
|
assum = fold_build2 (cmp, boolean_type_node, base, bound);
|
assum = fold_build2 (cmp, boolean_type_node, base, bound);
|
cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
|
cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
|
|
|
cond = force_gimple_operand (unshare_expr (cond), &stmts, false, NULL_TREE);
|
cond = force_gimple_operand (unshare_expr (cond), &stmts, false, NULL_TREE);
|
if (stmts)
|
if (stmts)
|
bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
|
bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
|
/* cond now may be a gimple comparison, which would be OK, but also any
|
/* cond now may be a gimple comparison, which would be OK, but also any
|
other gimple rhs (say a && b). In this case we need to force it to
|
other gimple rhs (say a && b). In this case we need to force it to
|
operand. */
|
operand. */
|
if (!is_gimple_condexpr (cond))
|
if (!is_gimple_condexpr (cond))
|
{
|
{
|
cond = force_gimple_operand (cond, &stmts, true, NULL_TREE);
|
cond = force_gimple_operand (cond, &stmts, true, NULL_TREE);
|
if (stmts)
|
if (stmts)
|
bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
|
bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
|
}
|
}
|
*enter_cond = cond;
|
*enter_cond = cond;
|
|
|
base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE);
|
base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE);
|
if (stmts)
|
if (stmts)
|
bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
|
bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
|
bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE);
|
bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE);
|
if (stmts)
|
if (stmts)
|
bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
|
bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
|
|
|
*exit_base = base;
|
*exit_base = base;
|
*exit_step = bigstep;
|
*exit_step = bigstep;
|
*exit_cmp = cmp;
|
*exit_cmp = cmp;
|
*exit_bound = bound;
|
*exit_bound = bound;
|
}
|
}
|
|
|
/* Unroll LOOP FACTOR times. LOOPS is the loops tree. DESC describes
|
/* Unroll LOOP FACTOR times. LOOPS is the loops tree. DESC describes
|
number of iterations of LOOP. EXIT is the exit of the loop to that
|
number of iterations of LOOP. EXIT is the exit of the loop to that
|
DESC corresponds.
|
DESC corresponds.
|
|
|
If N is number of iterations of the loop and MAY_BE_ZERO is the condition
|
If N is number of iterations of the loop and MAY_BE_ZERO is the condition
|
under that loop exits in the first iteration even if N != 0,
|
under that loop exits in the first iteration even if N != 0,
|
|
|
while (1)
|
while (1)
|
{
|
{
|
x = phi (init, next);
|
x = phi (init, next);
|
|
|
pre;
|
pre;
|
if (st)
|
if (st)
|
break;
|
break;
|
post;
|
post;
|
}
|
}
|
|
|
becomes (with possibly the exit conditions formulated a bit differently,
|
becomes (with possibly the exit conditions formulated a bit differently,
|
avoiding the need to create a new iv):
|
avoiding the need to create a new iv):
|
|
|
if (MAY_BE_ZERO || N < FACTOR)
|
if (MAY_BE_ZERO || N < FACTOR)
|
goto rest;
|
goto rest;
|
|
|
do
|
do
|
{
|
{
|
x = phi (init, next);
|
x = phi (init, next);
|
|
|
pre;
|
pre;
|
post;
|
post;
|
pre;
|
pre;
|
post;
|
post;
|
...
|
...
|
pre;
|
pre;
|
post;
|
post;
|
N -= FACTOR;
|
N -= FACTOR;
|
|
|
} while (N >= FACTOR);
|
} while (N >= FACTOR);
|
|
|
rest:
|
rest:
|
init' = phi (init, x);
|
init' = phi (init, x);
|
|
|
while (1)
|
while (1)
|
{
|
{
|
x = phi (init', next);
|
x = phi (init', next);
|
|
|
pre;
|
pre;
|
if (st)
|
if (st)
|
break;
|
break;
|
post;
|
post;
|
} */
|
} */
|
|
|
void
|
void
|
tree_unroll_loop (struct loops *loops, struct loop *loop, unsigned factor,
|
tree_unroll_loop (struct loops *loops, struct loop *loop, unsigned factor,
|
edge exit, struct tree_niter_desc *desc)
|
edge exit, struct tree_niter_desc *desc)
|
{
|
{
|
tree dont_exit, exit_if, ctr_before, ctr_after;
|
tree dont_exit, exit_if, ctr_before, ctr_after;
|
tree enter_main_cond, exit_base, exit_step, exit_bound;
|
tree enter_main_cond, exit_base, exit_step, exit_bound;
|
enum tree_code exit_cmp;
|
enum tree_code exit_cmp;
|
tree phi_old_loop, phi_new_loop, phi_rest, init, next, new_init, var;
|
tree phi_old_loop, phi_new_loop, phi_rest, init, next, new_init, var;
|
struct loop *new_loop;
|
struct loop *new_loop;
|
basic_block rest, exit_bb;
|
basic_block rest, exit_bb;
|
edge old_entry, new_entry, old_latch, precond_edge, new_exit;
|
edge old_entry, new_entry, old_latch, precond_edge, new_exit;
|
edge nonexit, new_nonexit;
|
edge nonexit, new_nonexit;
|
block_stmt_iterator bsi;
|
block_stmt_iterator bsi;
|
use_operand_p op;
|
use_operand_p op;
|
bool ok;
|
bool ok;
|
unsigned est_niter;
|
unsigned est_niter;
|
unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
|
unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
|
sbitmap wont_exit;
|
sbitmap wont_exit;
|
|
|
est_niter = expected_loop_iterations (loop);
|
est_niter = expected_loop_iterations (loop);
|
determine_exit_conditions (loop, desc, factor,
|
determine_exit_conditions (loop, desc, factor,
|
&enter_main_cond, &exit_base, &exit_step,
|
&enter_main_cond, &exit_base, &exit_step,
|
&exit_cmp, &exit_bound);
|
&exit_cmp, &exit_bound);
|
|
|
new_loop = loop_version (loops, loop, enter_main_cond, NULL, true);
|
new_loop = loop_version (loops, loop, enter_main_cond, NULL, true);
|
gcc_assert (new_loop != NULL);
|
gcc_assert (new_loop != NULL);
|
update_ssa (TODO_update_ssa);
|
update_ssa (TODO_update_ssa);
|
|
|
/* Unroll the loop and remove the old exits. */
|
/* Unroll the loop and remove the old exits. */
|
dont_exit = ((exit->flags & EDGE_TRUE_VALUE)
|
dont_exit = ((exit->flags & EDGE_TRUE_VALUE)
|
? boolean_false_node
|
? boolean_false_node
|
: boolean_true_node);
|
: boolean_true_node);
|
if (exit == EDGE_SUCC (exit->src, 0))
|
if (exit == EDGE_SUCC (exit->src, 0))
|
nonexit = EDGE_SUCC (exit->src, 1);
|
nonexit = EDGE_SUCC (exit->src, 1);
|
else
|
else
|
nonexit = EDGE_SUCC (exit->src, 0);
|
nonexit = EDGE_SUCC (exit->src, 0);
|
nonexit->probability = REG_BR_PROB_BASE;
|
nonexit->probability = REG_BR_PROB_BASE;
|
exit->probability = 0;
|
exit->probability = 0;
|
nonexit->count += exit->count;
|
nonexit->count += exit->count;
|
exit->count = 0;
|
exit->count = 0;
|
exit_if = last_stmt (exit->src);
|
exit_if = last_stmt (exit->src);
|
COND_EXPR_COND (exit_if) = dont_exit;
|
COND_EXPR_COND (exit_if) = dont_exit;
|
update_stmt (exit_if);
|
update_stmt (exit_if);
|
|
|
wont_exit = sbitmap_alloc (factor);
|
wont_exit = sbitmap_alloc (factor);
|
sbitmap_ones (wont_exit);
|
sbitmap_ones (wont_exit);
|
ok = tree_duplicate_loop_to_header_edge
|
ok = tree_duplicate_loop_to_header_edge
|
(loop, loop_latch_edge (loop), loops, factor - 1,
|
(loop, loop_latch_edge (loop), loops, factor - 1,
|
wont_exit, NULL, NULL, NULL, DLTHE_FLAG_UPDATE_FREQ);
|
wont_exit, NULL, NULL, NULL, DLTHE_FLAG_UPDATE_FREQ);
|
free (wont_exit);
|
free (wont_exit);
|
gcc_assert (ok);
|
gcc_assert (ok);
|
update_ssa (TODO_update_ssa);
|
update_ssa (TODO_update_ssa);
|
|
|
/* Prepare the cfg and update the phi nodes. */
|
/* Prepare the cfg and update the phi nodes. */
|
rest = loop_preheader_edge (new_loop)->src;
|
rest = loop_preheader_edge (new_loop)->src;
|
precond_edge = single_pred_edge (rest);
|
precond_edge = single_pred_edge (rest);
|
loop_split_edge_with (loop_latch_edge (loop), NULL);
|
loop_split_edge_with (loop_latch_edge (loop), NULL);
|
exit_bb = single_pred (loop->latch);
|
exit_bb = single_pred (loop->latch);
|
|
|
new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
|
new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
|
new_exit->count = loop_preheader_edge (loop)->count;
|
new_exit->count = loop_preheader_edge (loop)->count;
|
est_niter = est_niter / factor + 1;
|
est_niter = est_niter / factor + 1;
|
new_exit->probability = REG_BR_PROB_BASE / est_niter;
|
new_exit->probability = REG_BR_PROB_BASE / est_niter;
|
|
|
new_nonexit = single_pred_edge (loop->latch);
|
new_nonexit = single_pred_edge (loop->latch);
|
new_nonexit->flags = EDGE_TRUE_VALUE;
|
new_nonexit->flags = EDGE_TRUE_VALUE;
|
new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability;
|
new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability;
|
|
|
old_entry = loop_preheader_edge (loop);
|
old_entry = loop_preheader_edge (loop);
|
new_entry = loop_preheader_edge (new_loop);
|
new_entry = loop_preheader_edge (new_loop);
|
old_latch = loop_latch_edge (loop);
|
old_latch = loop_latch_edge (loop);
|
for (phi_old_loop = phi_nodes (loop->header),
|
for (phi_old_loop = phi_nodes (loop->header),
|
phi_new_loop = phi_nodes (new_loop->header);
|
phi_new_loop = phi_nodes (new_loop->header);
|
phi_old_loop;
|
phi_old_loop;
|
phi_old_loop = PHI_CHAIN (phi_old_loop),
|
phi_old_loop = PHI_CHAIN (phi_old_loop),
|
phi_new_loop = PHI_CHAIN (phi_new_loop))
|
phi_new_loop = PHI_CHAIN (phi_new_loop))
|
{
|
{
|
init = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_entry);
|
init = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_entry);
|
op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop, new_entry);
|
op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop, new_entry);
|
gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
|
gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
|
next = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_latch);
|
next = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_latch);
|
|
|
/* Prefer using original variable as a base for the new ssa name.
|
/* Prefer using original variable as a base for the new ssa name.
|
This is necessary for virtual ops, and useful in order to avoid
|
This is necessary for virtual ops, and useful in order to avoid
|
losing debug info for real ops. */
|
losing debug info for real ops. */
|
if (TREE_CODE (next) == SSA_NAME)
|
if (TREE_CODE (next) == SSA_NAME)
|
var = SSA_NAME_VAR (next);
|
var = SSA_NAME_VAR (next);
|
else if (TREE_CODE (init) == SSA_NAME)
|
else if (TREE_CODE (init) == SSA_NAME)
|
var = SSA_NAME_VAR (init);
|
var = SSA_NAME_VAR (init);
|
else
|
else
|
{
|
{
|
var = create_tmp_var (TREE_TYPE (init), "unrinittmp");
|
var = create_tmp_var (TREE_TYPE (init), "unrinittmp");
|
add_referenced_var (var);
|
add_referenced_var (var);
|
}
|
}
|
|
|
new_init = make_ssa_name (var, NULL_TREE);
|
new_init = make_ssa_name (var, NULL_TREE);
|
phi_rest = create_phi_node (new_init, rest);
|
phi_rest = create_phi_node (new_init, rest);
|
SSA_NAME_DEF_STMT (new_init) = phi_rest;
|
SSA_NAME_DEF_STMT (new_init) = phi_rest;
|
|
|
add_phi_arg (phi_rest, init, precond_edge);
|
add_phi_arg (phi_rest, init, precond_edge);
|
add_phi_arg (phi_rest, next, new_exit);
|
add_phi_arg (phi_rest, next, new_exit);
|
SET_USE (op, new_init);
|
SET_USE (op, new_init);
|
}
|
}
|
|
|
/* Finally create the new counter for number of iterations and add the new
|
/* Finally create the new counter for number of iterations and add the new
|
exit instruction. */
|
exit instruction. */
|
bsi = bsi_last (exit_bb);
|
bsi = bsi_last (exit_bb);
|
create_iv (exit_base, exit_step, NULL_TREE, loop,
|
create_iv (exit_base, exit_step, NULL_TREE, loop,
|
&bsi, true, &ctr_before, &ctr_after);
|
&bsi, true, &ctr_before, &ctr_after);
|
exit_if = build_if_stmt (build2 (exit_cmp, boolean_type_node, ctr_after,
|
exit_if = build_if_stmt (build2 (exit_cmp, boolean_type_node, ctr_after,
|
exit_bound),
|
exit_bound),
|
tree_block_label (loop->latch),
|
tree_block_label (loop->latch),
|
tree_block_label (rest));
|
tree_block_label (rest));
|
bsi_insert_after (&bsi, exit_if, BSI_NEW_STMT);
|
bsi_insert_after (&bsi, exit_if, BSI_NEW_STMT);
|
|
|
verify_flow_info ();
|
verify_flow_info ();
|
verify_dominators (CDI_DOMINATORS);
|
verify_dominators (CDI_DOMINATORS);
|
verify_loop_structure (loops);
|
verify_loop_structure (loops);
|
verify_loop_closed_ssa ();
|
verify_loop_closed_ssa ();
|
}
|
}
|
|
|
