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"
enum unroll_level
{
UL_SINGLE_ITER,
UL_NO_GROWTH,
UL_ALL
};
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,
build_int_cst (type, -1),
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));
update_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 unsigned HOST_WIDE_INT
estimated_unrolled_size (unsigned HOST_WIDE_INT ninsns,
unsigned HOST_WIDE_INT nunroll)
{
HOST_WIDE_INT unr_insns = 2 * ((HOST_WIDE_INT) ninsns - 4) / 3;
if (unr_insns <= 0)
unr_insns = 1;
unr_insns *= (nunroll + 1);
return unr_insns;
}
static bool
try_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED,
struct loop *loop,
edge exit, tree niter,
enum unroll_level ul)
{
unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
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 (ul == UL_SINGLE_ITER)
return false;
ninsns = tree_num_loop_insns (loop);
if (n_unroll * ninsns
> (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
return false;
if (ul == UL_NO_GROWTH)
{
unr_insns = estimated_unrolled_size (ninsns, n_unroll);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " Loop size: %d\n", (int) ninsns);
fprintf (dump_file, " Estimated size after unrolling: %d\n",
(int) unr_insns);
}
if (unr_insns > ninsns)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Not unrolling loop %d:\n", loop->num);
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)
{
sbitmap wont_exit;
edge *edges_to_remove = XNEWVEC (edge, n_unroll);
unsigned int n_to_remove = 0;
old_cond = COND_EXPR_COND (cond);
COND_EXPR_COND (cond) = dont_exit;
update_stmt (cond);
initialize_original_copy_tables ();
wont_exit = sbitmap_alloc (n_unroll + 1);
sbitmap_ones (wont_exit);
RESET_BIT (wont_exit, 0);
if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
loops, n_unroll, wont_exit,
exit, edges_to_remove,
&n_to_remove,
DLTHE_FLAG_UPDATE_FREQ
| DLTHE_FLAG_COMPLETTE_PEEL))
{
COND_EXPR_COND (cond) = old_cond;
update_stmt (cond);
free_original_copy_tables ();
free (wont_exit);
free (edges_to_remove);
return false;
}
free (wont_exit);
free (edges_to_remove);
free_original_copy_tables ();
}
COND_EXPR_COND (cond) = do_exit;
update_stmt (cond);
update_ssa (TODO_update_ssa);
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, enum unroll_level ul,
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, ul))
return true;
if (create_iv)
create_canonical_iv (loop, exit, niter);
return false;
}
unsigned int
canonicalize_induction_variables (struct loops *loops)
{
unsigned i;
struct loop *loop;
bool changed = false;
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
if (loop)
changed |= canonicalize_loop_induction_variables (loops, loop,
true, UL_SINGLE_ITER,
true);
}
scev_reset ();
if (changed)
return TODO_cleanup_cfg;
return 0;
}
unsigned int
tree_unroll_loops_completely (struct loops *loops, bool may_increase_size)
{
unsigned i;
struct loop *loop;
bool changed = false;
enum unroll_level ul;
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
if (!loop)
continue;
if (may_increase_size && maybe_hot_bb_p (loop->header))
ul = UL_ALL;
else
ul = UL_NO_GROWTH;
changed |= canonicalize_loop_induction_variables (loops, loop,
false, ul,
!flag_tree_loop_ivcanon);
}
scev_reset ();
if (changed)
return TODO_cleanup_cfg;
return 0;
}
static bool
empty_loop_p (struct loop *loop)
{
edge exit;
struct tree_niter_desc niter;
tree phi, def;
basic_block *body;
block_stmt_iterator bsi;
unsigned i;
tree stmt;
exit = single_dom_exit (loop);
if (!exit)
return false;
if (!number_of_iterations_exit (loop, exit, &niter, false))
return false;
for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
{
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;
}
body = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
{
if (body[i]->flags & BB_IRREDUCIBLE_LOOP)
{
free (body);
return false;
}
for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
{
stmt = bsi_stmt (bsi);
if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)
|| stmt_ann (stmt)->has_volatile_ops)
{
free (body);
return false;
}
switch (TREE_CODE (stmt))
{
case RETURN_EXPR:
case MODIFY_EXPR:
stmt = get_call_expr_in (stmt);
if (!stmt)
break;
case CALL_EXPR:
if (TREE_SIDE_EFFECTS (stmt))
{
free (body);
return false;
}
break;
case ASM_EXPR:
if (ASM_VOLATILE_P (stmt))
{
free (body);
return false;
}
break;
default:
break;
}
}
}
free (body);
return true;
}
static void
remove_empty_loop (struct loop *loop)
{
edge exit = single_dom_exit (loop), non_exit;
tree cond_stmt = last_stmt (exit->src);
tree do_exit;
basic_block *body;
unsigned n_before, freq_in, freq_h;
gcov_type exit_count = exit->count;
non_exit = EDGE_SUCC (exit->src, 0);
if (non_exit == exit)
non_exit = EDGE_SUCC (exit->src, 1);
if (exit->flags & EDGE_TRUE_VALUE)
do_exit = boolean_true_node;
else
do_exit = boolean_false_node;
COND_EXPR_COND (cond_stmt) = do_exit;
update_stmt (cond_stmt);
exit->probability = REG_BR_PROB_BASE;
non_exit->probability = 0;
non_exit->count = 0;
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);
}
exit->count = exit_count;
}
static bool
try_remove_empty_loop (struct loop *loop, bool *changed)
{
bool nonempty_subloop = false;
struct loop *sub;
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;
}
unsigned int
remove_empty_loops (struct loops *loops)
{
bool changed = false;
struct loop *loop;
for (loop = loops->tree_root->inner; loop; loop = loop->next)
try_remove_empty_loop (loop, &changed);
if (changed)
{
scev_reset ();
return TODO_cleanup_cfg;
}
return 0;
}