X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillbelady2.c;h=b48b8dc8d2c8cd6cfab4570305b924a9df3fced8;hb=505d3662efed6efbca2c43eea2fe23b87816b285;hp=58fd6e4265c2e2b2963ba7c9915731fd180d2609;hpb=bc000a2f2ad1e1e7ca6b0eb832a8f4a8173fd301;p=libfirm diff --git a/ir/be/bespillbelady2.c b/ir/be/bespillbelady2.c index 58fd6e426..b48b8dc8d 100644 --- a/ir/be/bespillbelady2.c +++ b/ir/be/bespillbelady2.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -58,7 +58,6 @@ #include "beutil.h" #include "bearch_t.h" -#include "bespillbelady.h" #include "besched_t.h" #include "beirgmod.h" #include "belive_t.h" @@ -68,10 +67,10 @@ #include "beloopana.h" #include "beirg_t.h" #include "bemodule.h" +#include "bespill.h" -#include -#include -#include +#include "lc_opts.h" +#include "lc_opts_enum.h" #define DBG_SPILL 1 #define DBG_WSETS 2 @@ -128,15 +127,16 @@ typedef struct _belady_env_t { be_lv_t *lv; ir_exec_freq *ef; - ir_node **blocks; /**< Array of all blocks. */ - int n_blocks; /**< Number of blocks in the graph. */ - int n_regs; /**< number of regs in this reg-class */ - workset_t *ws; /**< the main workset used while processing a block. ob-allocated */ - ir_node *instr; /**< current instruction */ - int instr_nr; /**< current instruction number (relative to block start) */ + ir_node **blocks; /**< Array of all blocks. */ + int n_blocks; /**< Number of blocks in the graph. */ + int n_regs; /**< number of regs in this reg-class */ + workset_t *ws; /**< the main workset used while processing a block. ob-allocated */ + ir_node *instr; /**< current instruction */ + int instr_nr; /**< current instruction number (relative to block start) */ - spill_env_t *senv; /**< see bespill.h */ - bitset_t *spilled; /**< bitset to keep all the irns which have already been spilled. */ + spill_env_t *senv; /**< see bespill.h */ + bitset_t *spilled; /**< bitset to keep all the irns which have already been spilled. */ + ir_nodeset_t *extra_spilled; /** All nodes for which a special spill location has been computed. */ } belady_env_t; @@ -292,6 +292,7 @@ typedef struct _block_info_t { real (non-phi) node. At the beginning of the global pass, this is 0. */ struct list_head br_head; /**< List head for all bring_in variables. */ + int free_at_jump; /**< registers free at jump. */ } block_info_t; @@ -306,7 +307,8 @@ static INLINE void *new_block_info(belady_env_t *bel, int id) res->bl = bl; res->id = id; res->exec_freq = get_block_execfreq(bel->ef, bl); - res->reload_cost = bel->arch->isa->reload_cost * res->exec_freq; + res->reload_cost = bel->arch->reload_cost * res->exec_freq; + res->free_at_jump = bel->n_regs; INIT_LIST_HEAD(&res->br_head); set_irn_link(bl, res); return res; @@ -334,7 +336,7 @@ typedef struct _next_use_t { or NULL. */ } next_use_t; -static void *next_use_init(ir_phase *phase, ir_node *irn, void *old) +static void *next_use_init(ir_phase *phase, const ir_node *irn, void *old) { (void) phase; (void) irn; @@ -437,6 +439,8 @@ struct _bring_in_t { int is_remat : 1; /**< Is rematerializable. */ int sect_pressure; /**< Offset to maximum pressure in block. */ struct list_head list; + struct list_head sect_list; + bring_in_t *sect_head; }; static INLINE bring_in_t *new_bring_in(block_info_t *bi, ir_node *irn, const next_use_t *use) @@ -450,8 +454,10 @@ static INLINE bring_in_t *new_bring_in(block_info_t *bi, ir_node *irn, const nex br->is_remat = be_is_rematerializable(bi->bel->senv, irn, use->irn); br->pressure_so_far = bi->pressure; br->sect_pressure = bi->front_pressure; + br->sect_head = br; INIT_LIST_HEAD(&br->list); + INIT_LIST_HEAD(&br->sect_list); list_add_tail(&br->list, &bi->br_head); return br; } @@ -604,7 +610,7 @@ static void displace(block_info_t *bi, workset_t *new_vals, int is_usage) { } } } else { - assert(is_usage || "Defined value already in workset?!?"); + assert(is_usage && "Defined value already in workset?!?"); DBG((dbg, DBG_DECIDE, "\t\tskip %+F\n", val)); } } @@ -729,6 +735,13 @@ static void belady(belady_env_t *env, int id) { DBG((dbg, DBG_DECIDE, "\t* defs\n")); displace(block_info, new_vals, 0); + if (is_op_forking(get_irn_op(env->instr))) { + for (i = get_irn_arity(env->instr) - 1; i >= 0; --i) { + ir_node *op = get_irn_n(env->instr, i); + block_info->free_at_jump -= arch_irn_consider_in_reg_alloc(env->arch, env->cls, op); + } + } + env->instr_nr++; } @@ -951,7 +964,7 @@ static double can_make_available_at_end(global_end_state_t *ges, ir_node *bl, ir */ { - int n_regs = bi->bel->n_regs; + int n_regs = bi->free_at_jump; int len = workset_get_length(end); int slot = -1; int i; @@ -1101,9 +1114,18 @@ static void materialize_and_commit_end_state(global_end_state_t *ges) for (ia = ges->ia_top; ia != NULL; ia = ia->next) { switch (ia->act) { case irn_act_live_through: - if (is_local_phi(ia->bl, ia->irn)) { - bitset_add_irn(ges->succ_phis, ia->irn); - DBG((dbg, DBG_GLOBAL, "\t\tlive through phi kept alive: %+F\n", ia->irn)); + { + block_info_t *bi = get_block_info(ia->bl); + bring_in_t *iter; + + if (is_local_phi(ia->bl, ia->irn)) { + bitset_add_irn(ges->succ_phis, ia->irn); + DBG((dbg, DBG_GLOBAL, "\t\tlive through phi kept alive: %+F\n", ia->irn)); + } + + list_for_each_entry_reverse(bring_in_t, iter, &bi->br_head, list) + ++iter->sect_pressure; + ++bi->front_pressure; } break; case irn_act_reload: @@ -1128,7 +1150,6 @@ static void materialize_and_commit_end_state(global_end_state_t *ges) DBG((dbg, DBG_GLOBAL, "\t\told pressure: %d, new pressure: %d, end length: %d\n", bi->pressure, bs->pressure, workset_get_length(bs->end_state))); bi->pressure = bs->pressure; - /* TODO: commit front pressure */ bitset_set(ges->committed, bi->id); } } @@ -1195,7 +1216,7 @@ static int get_block_max_pressure(const block_info_t *bi) */ static void optimize_variable(global_end_state_t *ges, bring_in_t *br) { - block_info_t *bi = br->bi; + block_info_t *bi = br->bi; ir_node *irn = br->irn; ir_node *bl = bi->bl; belady_env_t *env = ges->env; @@ -1208,9 +1229,11 @@ static void optimize_variable(global_end_state_t *ges, bring_in_t *br) assert(front_pressure <= k); assert(pressure_upto_use <= k); - DBG((dbg, DBG_GLOBAL, "fixing %+F at %+F (%f), front pr: %d, pr to use: %d, first use: %u\n", + DBG((dbg, DBG_GLOBAL, "fixing %+F at %+F (%f), front pr: %d, pr to use: %d, first use: %x\n", irn, bl, bi->exec_freq, front_pressure, pressure_upto_use, br->first_use)); + // assert(!is_local_phi(bl, irn) || !bitset_contains_irn(ges->succ_phis, irn)); + /* * if we cannot bring the value to the use, let's see ifit would be worthwhile * to bring the value to the beginning of the block to have a better spill @@ -1219,8 +1242,10 @@ static void optimize_variable(global_end_state_t *ges, bring_in_t *br) * better _spilled_here will return a node where the value can be spilled after * or NULL if this block does not provide a better spill location. */ - if (pressure_upto_use >= k && front_pressure < k) +#if 1 + if (pressure_upto_use >= k && front_pressure < k && !bitset_contains_irn(env->spilled, irn)) better_spill_loc = better_spilled_here(br); +#endif /* * If either we can bring the value to the use or we should try @@ -1283,6 +1308,7 @@ static void optimize_variable(global_end_state_t *ges, bring_in_t *br) /* the costs were acceptable... */ if (bring_in_costs < local_costs) { + int check = 0; bring_in_t *iter; /* @@ -1295,16 +1321,15 @@ static void optimize_variable(global_end_state_t *ges, bring_in_t *br) if (is_local_phi(bl, irn)) bitset_add_irn(ges->succ_phis, irn); - pressure_inc = bi->pressure - pressure_inc; - assert(pressure_inc >= 0); - - DBG((dbg, DBG_GLOBAL, "\t-> bring it in\n")); + DBG((dbg, DBG_GLOBAL, "\t-> bring it in.", pressure_inc)); /* second half of case 2 */ if (pressure_upto_use >= k) { DBG((dbg, DBG_GLOBAL, "\t-> use blocked. local reload: %+F, try spill at: %+F\n", br->first_use, better_spill_loc)); - be_add_reload2(env->senv, irn, br->first_use, better_spill_loc, env->cls, 1); + be_add_reload(env->senv, irn, br->first_use, env->cls, 1); + be_add_spill(env->senv, irn, better_spill_loc); + ir_nodeset_insert(env->extra_spilled, irn); } /* @@ -1314,18 +1339,24 @@ static void optimize_variable(global_end_state_t *ges, bring_in_t *br) * the pressure by one more as the nrought in value starts to count. * Finally, adjust the front pressure as well. */ + pressure_inc = 0; list_for_each_entry_reverse(bring_in_t, iter, &bi->br_head, list) { if (iter == br) pressure_inc += pressure_upto_use < k; iter->sect_pressure += pressure_inc; + check = MAX(check, iter->sect_pressure); + DBG((dbg, DBG_GLOBAL, "\tinc section pressure of %+F by %d to %d\n", iter->first_use, pressure_inc, iter->sect_pressure)); } bi->front_pressure += pressure_inc; + assert(MAX(check, bi->front_pressure) <= bi->pressure); + DBG((dbg, DBG_GLOBAL, "\t-> result: p: %d, fp: %d\n", bi->pressure, bi->front_pressure)); } /* case 3: nothing worked. insert normal reload and rollback. */ else { DBG((dbg, DBG_GLOBAL, "\t-> bring in was too expensive. local reload: %+F\n", br->first_use)); be_add_reload(env->senv, irn, br->first_use, env->cls, 1); + bitset_add_irn(env->spilled, irn); trans_rollback(ges, &trans); } } @@ -1334,6 +1365,7 @@ static void optimize_variable(global_end_state_t *ges, bring_in_t *br) else { DBG((dbg, DBG_GLOBAL, "\t-> can\'t do anything but reload before %+F\n", br->first_use)); be_add_reload(env->senv, irn, br->first_use, env->cls, 1); + bitset_add_irn(env->spilled, irn); } DBG((dbg, DBG_GLOBAL, "\n")); @@ -1363,10 +1395,15 @@ static bring_in_t **determine_global_order(belady_env_t *env) return res; } + + + static void global_assign(belady_env_t *env) { + ir_nodeset_iterator_t iter; global_end_state_t ges; bring_in_t **br; + ir_node *irn; int i, j; /* @@ -1415,6 +1452,10 @@ static void global_assign(belady_env_t *env) be_spill_phi(env->senv, irn); } } + + /* check dominance for specially spilled nodes. */ + foreach_ir_nodeset (env->extra_spilled, irn, iter) + make_spill_locations_dominate_irn(env->senv, irn); } static void collect_blocks(ir_node *bl, void *data) @@ -1457,6 +1498,7 @@ void be_spill_belady(be_irg_t *birg, const arch_register_class_t *cls) env.senv = be_new_spill_env(birg); env.ef = be_get_birg_exec_freq(birg); env.spilled = bitset_irg_obstack_alloc(&env.ob, irg); + env.extra_spilled = ir_nodeset_new(64); env.n_blocks = 0; irg_block_walk_graph(irg, NULL, collect_blocks, &env); @@ -1475,11 +1517,21 @@ void be_spill_belady(be_irg_t *birg, const arch_register_class_t *cls) global_assign(&env); + /* check dominance for specially spilled nodes. */ + { + ir_nodeset_iterator_t iter; + ir_node *irn; + + foreach_ir_nodeset (env.extra_spilled, irn, iter) + make_spill_locations_dominate_irn(env.senv, irn); + } + /* Insert spill/reload nodes into the graph and fix usages */ be_insert_spills_reloads(env.senv); /* clean up */ be_delete_spill_env(env.senv); + ir_nodeset_del(env.extra_spilled); obstack_free(&env.ob, NULL); }