X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Floop.c;h=d1e1a5ca67a6fa54285f3f99379033141da5479b;hb=c1c777ab401f028f3bfef31836da00c3f3fc5e0c;hp=5bdfbbe8a59aa8d69ae69a59112ac7171db66115;hpb=9d3c8631459f431c313160dab5778e8a7b88dd92;p=libfirm diff --git a/ir/opt/loop.c b/ir/opt/loop.c index 5bdfbbe8a..d1e1a5ca6 100644 --- a/ir/opt/loop.c +++ b/ir/opt/loop.c @@ -1,5 +1,5 @@ /* - * 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. * @@ -24,7 +24,6 @@ * * @version $Id$ */ - #include "config.h" #include "iroptimize.h" @@ -168,7 +167,7 @@ unsigned count_proj:1; /* Count projections */ 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] */ @@ -179,23 +178,23 @@ static loop_opt_params_t opt_params; /* 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; @@ -206,8 +205,8 @@ typedef struct loop_info_t { 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 */ @@ -583,7 +582,7 @@ static unsigned is_nodes_block_marked(ir_node* node) /* 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; @@ -609,7 +608,7 @@ static void extend_irn(ir_node *n, ir_node *new, int new_is_backedge) 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); @@ -703,7 +702,7 @@ static ir_node *copy_node(ir_node *node) * 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; @@ -785,8 +784,8 @@ static void copy_walk(ir_node *node, walker_condition *walk_condition, * 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; @@ -860,8 +859,8 @@ static void copy_walk_n(ir_node *node, /* 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]; @@ -889,8 +888,8 @@ static void unmark_not_allowed_cc_blocks(void) * 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]; @@ -1021,7 +1020,7 @@ static unsigned find_condition_chain(ir_node *block) * / A* B / | * / /\ / ? | * / C* => D | - * / D Head | + * / D Head | * / A \_| * C */ @@ -1059,10 +1058,10 @@ static void fix_copy_inversion(void) 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; @@ -1114,9 +1113,9 @@ static void fix_head_inversion(void) 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; @@ -1180,7 +1179,7 @@ static void fix_head_inversion(void) /* 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. @@ -1434,7 +1433,7 @@ static void unrolling_fix_loop_head_inv(void) 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])); } @@ -1463,7 +1462,8 @@ static void correct_phis(ir_node *node, void *env) 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. @@ -1523,7 +1523,7 @@ static void place_copies(int copies) 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)); /* */ @@ -1562,9 +1562,9 @@ static void place_copies(int copies) 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; @@ -1579,11 +1579,12 @@ static void place_copies(int copies) /* 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); @@ -1674,7 +1675,7 @@ static void create_duffs_block(void) 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]; @@ -1683,6 +1684,7 @@ static void create_duffs_block(void) 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)); @@ -1695,7 +1697,6 @@ static void create_duffs_block(void) /* 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); @@ -1712,17 +1713,23 @@ static void create_duffs_block(void) 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); @@ -1766,7 +1773,7 @@ static void create_duffs_block(void) 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); @@ -2162,10 +2169,10 @@ static unsigned are_mode_I(ir_node *n1, ir_node* n2, ir_node *n3) 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' */ @@ -2369,11 +2376,11 @@ static unsigned get_preferred_factor_constant(ir_tarval *count_tar) /* 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(); @@ -2529,7 +2536,7 @@ static unsigned get_unroll_decision_constant(void) 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); @@ -2611,7 +2618,7 @@ static void unroll_loop(void) 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)); @@ -2714,13 +2721,13 @@ static void init_analyze(ir_loop *loop) 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