/*
- * 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 */
/* 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);
+ int arity = get_irn_arity(head_cp);
+ int backedges = get_backedge_n(head_cp, 0);
+ int new_arity = arity - backedges;
int pos;
int i;
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;
+ int arity = get_irn_arity(loop_head);
+ int backedges = get_backedge_n(loop_head, 0);
+ int new_arity = backedges;
int pos;
int i;
/* 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_mode *mode;
ir_node *block1, *count_block, *duff_block;
- ir_node *ems, *ems_divmod, *ems_mod_proj, *cmp_null,
+ ir_node *ems, *ems_mod, *ems_div, *ems_mod_proj, *cmp_null,
*cmp_proj, *ems_mode_cond, *x_true, *x_false, *const_null;
ir_node *true_val, *false_val;
ir_node *ins[2];
ir_node *count, *correction, *unroll_c;
ir_node *cmp_bad_count, *good_count, *bad_count, *count_phi, *bad_count_neg;
+ ir_node *phi;
mode = get_irn_mode(loop_info.end_val);
const_null = new_Const(get_mode_null(mode));
/* Create loop entry phis in first duff block
* as it becomes the loops preheader */
- ir_node *phi;
for_each_phi(loop_head, phi) {
/* Returns phis pred if phi would have arity 1*/
ir_node *new_phi = clone_phis_sans_bes(phi, loop_head, block1);
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));
+ DB((dbg, LEVEL_4, "New module node %N\n", ems_mod));
- ems_mod_proj = new_r_Proj(ems_divmod, mode_Iu, pn_DivMod_res_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);
cmp_proj = new_r_Proj(cmp_null, mode_b, pn_Cmp_Eq);
ems_mode_cond = new_r_Cond(block1, cmp_proj);
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);
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 *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;
/* RETURN if loop is not 'simple' */
projres = is_simple_loop();
DB((dbg, LEVEL_4, "stepped to %ld\n", get_tarval_long(stepped)));
- proj_proj = get_Proj_proj(projres);
+ proj_proj = get_Proj_pn_cmp(projres);
/* Assure that norm_proj is the stay-in-loop case. */
if (loop_info.exit_cond == 1)
norm_proj = get_math_inverted_case(proj_proj);
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();