tree-ssa-loop-ivcanon.c [plain text]
#include "config.h"
#include "system.h"
#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-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"
#include "flags.h"
#include "tree-inline.h"
static void
create_canonical_iv (struct loop *loop, edge exit, tree niter)
{
edge in;
tree cond, type, var;
block_stmt_iterator incr_at;
enum tree_code cmp;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num);
print_generic_expr (dump_file, niter, TDF_SLIM);
fprintf (dump_file, " iterations.\n");
}
cond = last_stmt (exit->src);
in = EDGE_SUCC (exit->src, 0);
if (in == exit)
in = EDGE_SUCC (exit->src, 1);
type = TREE_TYPE (niter);
niter = fold (build2 (PLUS_EXPR, type,
niter,
build_int_cst (type, 1)));
incr_at = bsi_last (in->src);
create_iv (niter,
fold_convert (type, integer_minus_one_node),
NULL_TREE, loop,
&incr_at, false, NULL, &var);
cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
COND_EXPR_COND (cond) = build2 (cmp, boolean_type_node,
var,
build_int_cst (type, 0));
modify_stmt (cond);
}
unsigned
tree_num_loop_insns (struct loop *loop)
{
basic_block *body = get_loop_body (loop);
block_stmt_iterator bsi;
unsigned size = 1, i;
for (i = 0; i < loop->num_nodes; i++)
for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
size += estimate_num_insns (bsi_stmt (bsi));
free (body);
return size;
}
static bool
try_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED,
struct loop *loop,
edge exit, tree niter,
bool completely_unroll)
{
unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll;
tree old_cond, cond, dont_exit, do_exit;
if (loop->inner)
return false;
if (!host_integerp (niter, 1))
return false;
n_unroll = tree_low_cst (niter, 1);
max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
if (n_unroll > max_unroll)
return false;
if (n_unroll)
{
if (!completely_unroll)
return false;
ninsns = tree_num_loop_insns (loop);
if (n_unroll * ninsns
> (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
return false;
}
if (exit->flags & EDGE_TRUE_VALUE)
{
dont_exit = boolean_false_node;
do_exit = boolean_true_node;
}
else
{
dont_exit = boolean_true_node;
do_exit = boolean_false_node;
}
cond = last_stmt (exit->src);
if (n_unroll)
{
old_cond = COND_EXPR_COND (cond);
COND_EXPR_COND (cond) = dont_exit;
modify_stmt (cond);
if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
loops, n_unroll, NULL,
NULL, NULL, NULL, 0))
{
COND_EXPR_COND (cond) = old_cond;
return false;
}
}
COND_EXPR_COND (cond) = do_exit;
modify_stmt (cond);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num);
return true;
}
static bool
canonicalize_loop_induction_variables (struct loops *loops, struct loop *loop,
bool create_iv, bool completely_unroll,
bool try_eval)
{
edge exit = NULL;
tree niter;
niter = number_of_iterations_in_loop (loop);
if (TREE_CODE (niter) == INTEGER_CST)
{
exit = loop->single_exit;
if (!just_once_each_iteration_p (loop, exit->src))
return false;
niter = fold (build2 (MINUS_EXPR, TREE_TYPE (niter), niter,
build_int_cst (TREE_TYPE (niter), 1)));
}
else
{
if (!loop->single_exit)
niter = find_loop_niter (loop, &exit);
if (try_eval
&& (chrec_contains_undetermined (niter)
|| TREE_CODE (niter) != INTEGER_CST))
niter = find_loop_niter_by_eval (loop, &exit);
if (chrec_contains_undetermined (niter)
|| TREE_CODE (niter) != INTEGER_CST)
return false;
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Loop %d iterates ", loop->num);
print_generic_expr (dump_file, niter, TDF_SLIM);
fprintf (dump_file, " times.\n");
}
if (try_unroll_loop_completely (loops, loop, exit, niter, completely_unroll))
return true;
if (create_iv)
create_canonical_iv (loop, exit, niter);
return false;
}
void
canonicalize_induction_variables (struct loops *loops)
{
unsigned i;
struct loop *loop;
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
if (loop)
canonicalize_loop_induction_variables (loops, loop, true, false, true);
}
scev_reset ();
#if 0
if (changed)
cleanup_tree_cfg_loop ();
#endif
}
void
tree_unroll_loops_completely (struct loops *loops)
{
unsigned i;
struct loop *loop;
bool changed = false;
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
if (!loop)
continue;
changed |= canonicalize_loop_induction_variables (loops, loop,
false, true,
!flag_tree_loop_ivcanon);
}
scev_reset ();
#if 0
if (changed)
cleanup_tree_cfg_loop ();
#endif
}