/*
- * Copyright (C) 1995-2010 University of Karlsruhe. All right reserved.
+ * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
*
* This file is part of libFirm.
*
*
* @version $Id$
*/
-
#include "config.h"
#include "iroptimize.h"
unsigned max_cc_size; /* Maximum condition chain size [nodes] */
unsigned max_branches;
-unsigned max_unrolled_loop_size; /* [nodes] */
+unsigned max_unrolled_loop_size; /* [nodes] */
unsigned allow_const_unrolling:1;
unsigned allow_invar_unrolling:1;
unsigned invar_unrolling_min_size; /* [nodes] */
/* Loop analysis informations */
typedef struct loop_info_t {
- unsigned nodes; /* node count */
- unsigned ld_st; /* load and store nodes */
- unsigned branches; /* number of conditions */
- unsigned calls; /* number of calls */
- unsigned cf_outs; /* number of cf edges which leave the loop */
- entry_edge cf_out; /* single loop leaving cf edge */
- int be_src_pos; /* position of the single own backedge in the head */
+ unsigned nodes; /* node count */
+ unsigned ld_st; /* load and store nodes */
+ unsigned branches; /* number of conditions */
+ unsigned calls; /* number of calls */
+ unsigned cf_outs; /* number of cf edges which leave the loop */
+ entry_edge cf_out; /* single loop leaving cf edge */
+ int be_src_pos; /* position of the single own backedge in the head */
/* for inversion */
- unsigned cc_size; /* nodes in the condition chain */
+ unsigned cc_size; /* nodes in the condition chain */
/* for unrolling */
- unsigned max_unroll; /* Number of unrolls satisfying max_loop_size */
- unsigned exit_cond; /* 1 if condition==true exits the loop. */
- unsigned latest_value:1; /* 1 if condition is checked against latest counter value */
- unsigned needs_backedge:1; /* 0 if loop is completely unrolled */
- unsigned decreasing:1; /* Step operation is_Sub, or step is<0 */
+ unsigned max_unroll; /* Number of unrolls satisfying max_loop_size */
+ unsigned exit_cond; /* 1 if condition==true exits the loop. */
+ unsigned latest_value:1; /* 1 if condition is checked against latest counter value */
+ unsigned needs_backedge:1; /* 0 if loop is completely unrolled */
+ unsigned decreasing:1; /* Step operation is_Sub, or step is<0 */
/* IV informations of a simple loop */
ir_node *start_val;
ir_tarval *count_tar; /* Number of loop iterations */
- ir_node *duff_cond; /* Duff mod */
- unrolling_kind_flag unroll_kind; /* constant or invariant unrolling */
+ ir_node *duff_cond; /* Duff mod */
+ unrolling_kind_flag unroll_kind; /* constant or invariant unrolling */
} loop_info_t;
/* Information about the current loop */
{
int i;
int n_cfgpreds;
- ir_graph *irg;
+ ir_graph *irg = get_irn_irg(block);
ir_node *phi;
ir_node **in;
* Dead and bad blocks. */
if (get_irn_arity(block) < 1 || is_Bad(block)) {
DB((dbg, LEVEL_5, "ssa bad %N\n", block));
- return new_Bad();
+ return new_r_Bad(irg, mode);
}
if (block == ssa_second_def_block && !first) {
return value;
}
- irg = get_irn_irg(block);
assert(block != get_irg_start_block(irg));
/* a Block with only 1 predecessor needs no Phi */
/* create a new Phi */
NEW_ARR_A(ir_node*, in, n_cfgpreds);
for (i = 0; i < n_cfgpreds; ++i)
- in[i] = new_Unknown(mode);
+ in[i] = new_r_Dummy(irg, mode);
phi = new_r_Phi(block, n_cfgpreds, in, mode);
/* Important: always keep block phi list up to date. */
/* Extends a nodes ins by node new.
* NOTE: This is slow if a node n needs to be extended more than once. */
-static void extend_irn(ir_node *n, ir_node *new, int new_is_backedge)
+static void extend_irn(ir_node *n, ir_node *newnode, int new_is_backedge)
{
ir_node **ins;
int i;
for(i = 0; i < arity; ++i) {
ins[i] = get_irn_n(n, i);
}
- ins[i] = new;
+ ins[i] = newnode;
set_irn_in(n, new_arity, ins);
* Order of ins is important for later usage.
*/
static void copy_walk(ir_node *node, walker_condition *walk_condition,
- ir_loop *set_loop)
+ ir_loop *set_loop)
{
int i;
int arity;
* Order of ins is important for later usage.
* Takes copy_index, to phase-link copy at specific index.
*/
-static void copy_walk_n(ir_node *node,
- walker_condition *walk_condition, int copy_index)
+static void copy_walk_n(ir_node *node, walker_condition *walk_condition,
+ int copy_index)
{
int i;
int arity;
/* Removes alle Blocks with non marked predecessors from the condition chain. */
static void unmark_not_allowed_cc_blocks(void)
{
- int blocks = ARR_LEN(cc_blocks);
- int i;
+ size_t blocks = ARR_LEN(cc_blocks);
+ size_t i;
for(i = 0; i < blocks; ++i) {
ir_node *block = cc_blocks[i];
* TODO: invert head for unrolling? */
static void unmark_cc_blocks(void)
{
- int blocks = ARR_LEN(cc_blocks);
- int i;
+ size_t blocks = ARR_LEN(cc_blocks);
+ size_t i;
for(i = 0; i < blocks; ++i) {
ir_node *block = cc_blocks[i];
* / A* B / |
* / /\ / ? |
* / C* => D |
- * / D Head |
+ * / D Head |
* / A \_|
* C
*/
ir_node **ins;
ir_node **phis;
ir_node *phi, *next;
- ir_node *head_cp = get_inversion_copy(loop_head);
- int arity = get_irn_arity(head_cp);
- int backedges = get_backedge_n(head_cp, 0);
- int new_arity = arity - backedges;
+ ir_node *head_cp = get_inversion_copy(loop_head);
+ ir_graph *irg = get_irn_irg(head_cp);
+ int arity = get_irn_arity(head_cp);
+ int backedges = get_backedge_n(head_cp, 0);
+ int new_arity = arity - backedges;
int pos;
int i;
ins[pos++] = get_irn_n(head_cp, i);
}
- new_head = new_Block(new_arity, ins);
+ new_head = new_r_Block(irg, new_arity, ins);
phis = NEW_ARR_F(ir_node *, 0);
ir_node **ins;
ir_node *phi, *next;
ir_node **phis;
- int arity = get_irn_arity(loop_head);
- int backedges = get_backedge_n(loop_head, 0);
- int new_arity = backedges;
+ ir_graph *irg = get_irn_irg(loop_head);
+ int arity = get_irn_arity(loop_head);
+ int backedges = get_backedge_n(loop_head, 0);
+ int new_arity = backedges;
int pos;
int i;
ins[pos++] = get_irn_n(loop_head, i);
}
- new_head = new_Block(new_arity, ins);
+ new_head = new_r_Block(irg, new_arity, ins);
phis = NEW_ARR_F(ir_node *, 0);
/* Does the loop inversion. */
static void inversion_walk(entry_edge *head_entries)
{
- int i;
+ size_t i;
/*
* The order of rewiring bottom-up is crucial.
ir_node *last_pred = get_unroll_copy(pred, unroll_nr - 1);
ins[0] = last_pred;
- ins[1] = get_irn_link(phi);
+ ins[1] = (ir_node*)get_irn_link(phi);
set_irn_in(phi, 2, ins);
DB((dbg, LEVEL_4, "Rewire ins of loophead phi %N to pred %N and duffs entry %N \n" , phi, ins[0], ins[1]));
}
static void place_copies(int copies)
{
ir_node *loophead = loop_head;
- int c, i;
+ size_t i;
+ int c;
int be_src_pos = loop_info.be_src_pos;
/* Serialize loops by fixing their head ins.
ir_node *duff_phi;
lower_phi = get_unroll_copy(phi, c + 1);
- duff_phi = get_irn_link(phi);
+ duff_phi = (ir_node*)get_irn_link(phi);
DB((dbg, LEVEL_4, "DD Link of %N is %N\n" , phi, duff_phi));
/* */
ir_node *pred = get_irn_n(phi, be_src_pos);
ir_node *last_pred;
- /* It is possible, that the value used
- * in the OWN backedge path is NOT assigned in this loop. */
- if (is_in_loop(pred))
+ /* It is possible, that the value used
+ * in the OWN backedge path is NOT assigned in this loop. */
+ if (is_in_loop(pred))
last_pred = get_unroll_copy(pred, copies);
else
last_pred = pred;
/* Copies the cur_loop several times. */
static void copy_loop(entry_edge *cur_loop_outs, int copies)
{
- int i, c;
+ int c;
ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
for (c = 0; c < copies; ++c) {
+ size_t i;
inc_irg_visited(current_ir_graph);
ir_graph *irg = get_irn_irg(op);
ir_node *block = get_nodes_block(op);
ir_node *zero = new_r_Const(irg, get_mode_null(mode));
- ir_node *cmp = new_r_Cmp(block, op, zero);
- ir_node *cond = new_r_Proj(cmp, mode_b, pn_Cmp_Lt);
+ ir_node *cmp = new_r_Cmp(block, op, zero, ir_relation_less);
ir_node *minus_op = new_r_Minus(block, op, mode);
- ir_node *mux = new_r_Mux(block, cond, op, minus_op, mode);
+ ir_node *mux = new_r_Mux(block, cmp, op, minus_op, mode);
return mux;
}
ir_mode *mode;
ir_node *block1, *count_block, *duff_block;
- ir_node *ems, *ems_divmod, *ems_mod_proj, *cmp_null,
- *cmp_proj, *ems_mode_cond, *x_true, *x_false, *const_null;
+ ir_node *ems, *ems_mod, *ems_div, *ems_mod_proj, *cmp_null,
+ *ems_mode_cond, *x_true, *x_false, *const_null;
ir_node *true_val, *false_val;
ir_node *ins[2];
ems = new_Sub(loop_info.end_val, loop_info.start_val,
get_irn_mode(loop_info.end_val));
- DB((dbg, LEVEL_4, "divmod ins %N %N\n", ems, loop_info.step));
- ems_divmod = new_r_DivMod(block1,
+ DB((dbg, LEVEL_4, "mod ins %N %N\n", ems, loop_info.step));
+ ems_mod = new_r_Mod(block1,
+ new_NoMem(),
+ ems,
+ loop_info.step,
+ mode,
+ op_pin_state_pinned);
+ ems_div = new_r_Div(block1,
new_NoMem(),
ems,
loop_info.step,
mode,
op_pin_state_pinned);
- DB((dbg, LEVEL_4, "New module node %N\n", ems_divmod));
-
- ems_mod_proj = new_r_Proj(ems_divmod, mode_Iu, pn_DivMod_res_mod);
- cmp_null = new_r_Cmp(block1, ems_mod_proj, const_null);
- cmp_proj = new_r_Proj(cmp_null, mode_b, pn_Cmp_Eq);
- ems_mode_cond = new_r_Cond(block1, cmp_proj);
+ DB((dbg, LEVEL_4, "New module node %N\n", ems_mod));
+ ems_mod_proj = new_r_Proj(ems_mod, mode_Iu, pn_Mod_res);
+ cmp_null = new_r_Cmp(block1, ems_mod_proj, const_null, ir_relation_less);
+ ems_mode_cond = new_r_Cond(block1, cmp_null);
/* ems % step == 0 */
x_true = new_r_Proj(ems_mode_cond, mode_X, pn_Cond_true);
correction = new_r_Phi(count_block, 2, ins, mode);
- count = new_r_Proj(ems_divmod, mode, pn_DivMod_res_div);
+ count = new_r_Proj(ems_div, mode, pn_Div_res);
/* (end - start) / step + correction */
count = new_Add(count, correction, mode);
- cmp_bad_count = new_r_Cmp(count_block, count, const_null);
-
/* We preconditioned the loop to be tail-controlled.
* So, if count is something 'wrong' like 0,
* negative/positive (depending on step direction),
/* Depending on step direction, we have to check for > or < 0 */
if (loop_info.decreasing == 1) {
- bad_count_neg = new_r_Proj(cmp_bad_count, mode_b, pn_Cmp_Lt);
+ cmp_bad_count = new_r_Cmp(count_block, count, const_null,
+ ir_relation_less);
} else {
- bad_count_neg = new_r_Proj(cmp_bad_count, mode_b, pn_Cmp_Gt);
+ cmp_bad_count = new_r_Cmp(count_block, count, const_null,
+ ir_relation_greater);
}
- bad_count_neg = new_r_Cond(count_block, bad_count_neg);
+ bad_count_neg = new_r_Cond(count_block, cmp_bad_count);
good_count = new_Proj(bad_count_neg, mode_X, pn_Cond_true);
bad_count = new_Proj(ems_mode_cond, mode_X, pn_Cond_false);
return 1;
}
-/* Returns the mathematically inverted pn_Cmp. */
-static pn_Cmp get_math_inverted_case(pn_Cmp proj)
-{
- switch(proj) {
- case pn_Cmp_Eq:
- return pn_Cmp_Lg;
- case pn_Cmp_Lg:
- return pn_Cmp_Eq;
- case pn_Cmp_Lt:
- return pn_Cmp_Ge;
- case pn_Cmp_Le:
- return pn_Cmp_Gt;
- case pn_Cmp_Gt:
- return pn_Cmp_Le;
- case pn_Cmp_Ge:
- return pn_Cmp_Lt;
- default:
- panic("Unhandled pn_Cmp.");
- }
-}
-
/* Returns 1 if loop exits within 2 steps of the iv.
* Norm_proj means we do not exit the loop.*/
static unsigned simulate_next(ir_tarval **count_tar,
ir_tarval *stepped, ir_tarval *step_tar, ir_tarval *end_tar,
- pn_Cmp norm_proj)
+ ir_relation norm_proj)
{
ir_tarval *next;
DB((dbg, LEVEL_4, "Loop taken if (stepped)%ld %s (end)%ld ",
get_tarval_long(stepped),
- get_pnc_string((norm_proj)),
+ get_relation_string((norm_proj)),
get_tarval_long(end_tar)));
DB((dbg, LEVEL_4, "comparing latest value %d\n", loop_info.latest_value));
DB((dbg, LEVEL_4, "Result: (stepped)%ld IS %s (end)%ld\n",
get_tarval_long(stepped),
- get_pnc_string(tarval_cmp(stepped, end_tar)),
+ get_relation_string(tarval_cmp(stepped, end_tar)),
get_tarval_long(end_tar)));
/* next step */
DB((dbg, LEVEL_4, "Loop taken if %ld %s %ld ",
get_tarval_long(next),
- get_pnc_string(norm_proj),
+ get_relation_string(norm_proj),
get_tarval_long(end_tar)));
DB((dbg, LEVEL_4, "comparing latest value %d\n", loop_info.latest_value));
static ir_node *is_simple_loop(void)
{
int arity, i;
- ir_node *loop_block, *exit_block, *projx, *cond, *projres, *loop_condition;
+ ir_node *loop_block, *exit_block, *projx, *cond, *cmp;
/* Maximum of one condition, and no endless loops. */
if (loop_info.cf_outs != 1)
/* find value on which loop exit depends */
projx = loop_info.cf_out.pred;
cond = get_irn_n(projx, 0);
- projres = get_irn_n(cond, 0);
- loop_condition = get_irn_n(projres, 0);
+ cmp = get_irn_n(cond, 0);
- if (!is_Cmp(loop_condition))
+ if (!is_Cmp(cmp))
return NULL;
- DB((dbg, LEVEL_5, "projection is %s\n", get_pnc_string(get_Proj_proj(projx))));
+ DB((dbg, LEVEL_5, "projection is %s\n", get_relation_string(get_Proj_proj(projx))));
switch(get_Proj_proj(projx)) {
case pn_Cond_false:
}
DB((dbg, LEVEL_4, "Valid Cmp.\n"));
-
- return projres;
+ return cmp;
}
/* Returns 1 if all nodes are mode_Iu or mode_Is. */
static unsigned get_unroll_decision_invariant(void)
{
- ir_node *projres, *loop_condition, *iteration_path;
- unsigned success, is_latest_val;
- ir_tarval *step_tar;
- ir_mode *mode;
+ ir_node *projres, *loop_condition, *iteration_path;
+ unsigned success, is_latest_val;
+ ir_tarval *step_tar;
+ ir_mode *mode;
/* RETURN if loop is not 'simple' */
/* TODO split. */
static unsigned get_unroll_decision_constant(void)
{
- ir_node *projres, *loop_condition, *iteration_path;
- unsigned success, is_latest_val;
- ir_tarval *start_tar, *end_tar, *step_tar, *diff_tar, *count_tar, *stepped;
- pn_Cmp proj_proj, norm_proj;
- ir_mode *mode;
+ ir_node *cmp, *iteration_path;
+ unsigned success, is_latest_val;
+ ir_tarval *start_tar, *end_tar, *step_tar, *diff_tar, *count_tar;
+ ir_tarval *stepped;
+ ir_relation proj_proj, norm_proj;
+ ir_mode *mode;
/* RETURN if loop is not 'simple' */
- projres = is_simple_loop();
- if (projres == NULL)
+ cmp = is_simple_loop();
+ if (cmp == NULL)
return 0;
/* One in of the loop condition needs to be loop invariant. => end_val
/\
*/
- loop_condition = get_irn_n(projres, 0);
-
- success = get_const_pred(loop_condition, &loop_info.end_val, &iteration_path);
+ success = get_const_pred(cmp, &loop_info.end_val, &iteration_path);
if (! success)
return 0;
DB((dbg, LEVEL_4, "stepped to %ld\n", get_tarval_long(stepped)));
- proj_proj = get_Proj_proj(projres);
+ proj_proj = get_Cmp_relation(cmp);
/* Assure that norm_proj is the stay-in-loop case. */
if (loop_info.exit_cond == 1)
- norm_proj = get_math_inverted_case(proj_proj);
+ norm_proj = get_negated_relation(proj_proj);
else
norm_proj = proj_proj;
- DB((dbg, LEVEL_4, "normalized projection %s\n", get_pnc_string(norm_proj)));
-
+ DB((dbg, LEVEL_4, "normalized projection %s\n", get_relation_string(norm_proj)));
/* Executed at most once (stay in counting loop if a Eq b) */
- if (norm_proj == pn_Cmp_Eq)
+ if (norm_proj == ir_relation_equal)
/* TODO Might be worth a warning. */
return 0;
if (opt_params.allow_invar_unrolling)
unroll_nr = get_unroll_decision_invariant();
if (unroll_nr > 1)
- loop_info.unroll_kind = invariant;
+ loop_info.unroll_kind = invariant;
}
DB((dbg, LEVEL_2, " *** Unrolling %d times ***\n", unroll_nr));
static void find_innermost_loop(ir_loop *loop)
{
/* descend into sons */
- int sons = get_loop_n_sons(loop);
+ size_t sons = get_loop_n_sons(loop);
if (sons == 0) {
ARR_APP1(ir_loop *, loops, loop);
} else {
- int s;
- for (s=0; s<sons; s++) {
+ size_t s;
+ for (s = 0; s < sons; ++s) {
find_innermost_loop(get_loop_son(loop, s));
}
}
opt_params.invar_unrolling_min_size = 20;
opt_params.max_unrolled_loop_size = 400;
opt_params.max_branches = 9999;
-
}
/* Assure preconditions are met and go through all loops. */
void loop_optimization(ir_graph *irg)
{
ir_loop *loop;
- int i, sons, nr;
+ size_t sons, nr;
+ size_t i;
set_loop_params();
projects / libfirm / blobdiff