X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbenewalloc.c;h=003032ccff7c2daaad65267a747b39b21be4084d;hb=b18d422d6aa7b0beba67c13ad5cc07a5c7a067a2;hp=49b9300a97543334f320cafdbd3a9637d4258c19;hpb=873b4e57824655620b79f91e89763d3664a555f0;p=libfirm diff --git a/ir/be/benewalloc.c b/ir/be/benewalloc.c index 49b9300a9..003032ccf 100644 --- a/ir/be/benewalloc.c +++ b/ir/be/benewalloc.c @@ -80,12 +80,13 @@ #include "beverify.h" #include "beutil.h" -#define USE_FACTOR 1.0f -#define DEF_FACTOR 1.0f -#define NEIGHBOR_FACTOR 0.2f -#define AFF_SHOULD_BE_SAME 0.5f -#define AFF_PHI 1.0f -#define SPLIT_DELTA 1.0f +#define USE_FACTOR 1.0f +#define DEF_FACTOR 1.0f +#define NEIGHBOR_FACTOR 0.2f +#define AFF_SHOULD_BE_SAME 0.5f +#define AFF_PHI 1.0f +#define SPLIT_DELTA 1.0f +#define MAX_OPTIMISTIC_SPLIT_RECURSION 0 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) @@ -101,6 +102,16 @@ static unsigned *normal_regs; static int *congruence_classes; static ir_node **block_order; static int n_block_order; +static int create_preferences = true; +static int create_congruence_classes = true; +static int propagate_phi_registers = true; + +static const lc_opt_table_entry_t options[] = { + LC_OPT_ENT_BOOL("prefs", "use preference based coloring", &create_preferences), + LC_OPT_ENT_BOOL("congruences", "create congruence classes", &create_congruence_classes), + LC_OPT_ENT_BOOL("prop_phi", "propagate phi registers", &propagate_phi_registers), + LC_OPT_LAST +}; /** currently active assignments (while processing a basic block) * maps registers to values(their current copies) */ @@ -149,6 +160,11 @@ static allocation_info_t *get_allocation_info(ir_node *node) return info; } +static allocation_info_t *try_get_allocation_info(const ir_node *node) +{ + return (allocation_info_t*) get_irn_link(node); +} + /** * Get allocation information for a basic block */ @@ -247,7 +263,7 @@ static void give_penalties_for_limits(const ir_nodeset_t *live_nodes, n_allowed = rbitset_popcnt(limited, n_regs); if (n_allowed > 1) { /* only create a very weak penalty if multiple regs are allowed */ - penalty = (penalty * 0.8) / n_allowed; + penalty = (penalty * 0.8f) / n_allowed; } foreach_ir_nodeset(live_nodes, neighbor, iter) { allocation_info_t *neighbor_info; @@ -353,7 +369,8 @@ static void analyze_block(ir_node *block, void *data) if (is_Phi(node)) break; - check_defs(&live_nodes, weight, node); + if (create_preferences) + check_defs(&live_nodes, weight, node); /* mark last uses */ arity = get_irn_arity(node); @@ -380,22 +397,24 @@ static void analyze_block(ir_node *block, void *data) be_liveness_transfer(cls, node, &live_nodes); - /* update weights based on usage constraints */ - for (i = 0; i < arity; ++i) { - const arch_register_req_t *req; - const unsigned *limited; - ir_node *op = get_irn_n(node, i); + if (create_preferences) { + /* update weights based on usage constraints */ + for (i = 0; i < arity; ++i) { + const arch_register_req_t *req; + const unsigned *limited; + ir_node *op = get_irn_n(node, i); - if (!arch_irn_consider_in_reg_alloc(cls, op)) - continue; + if (!arch_irn_consider_in_reg_alloc(cls, op)) + continue; - req = arch_get_register_req(node, i); - if (!(req->type & arch_register_req_type_limited)) - continue; + req = arch_get_register_req(node, i); + if (!(req->type & arch_register_req_type_limited)) + continue; - limited = req->limited; - give_penalties_for_limits(&live_nodes, weight * USE_FACTOR, limited, - op); + limited = req->limited; + give_penalties_for_limits(&live_nodes, weight * USE_FACTOR, limited, + op); + } } } @@ -602,6 +621,7 @@ static void combine_congruence_classes(void) /* merge preferences */ irg_walk_graph(irg, merge_congruence_prefs, NULL, NULL); irg_walk_graph(irg, set_congruence_prefs, NULL, NULL); + free(congruence_classes); } @@ -667,13 +687,15 @@ static void fill_sort_candidates(reg_pref_t *regprefs, static bool try_optimistic_split(ir_node *to_split, ir_node *before, float pref, float pref_delta, - unsigned *output_regs) + unsigned *forbidden_regs, int recursion) { + const arch_register_t *from_reg; const arch_register_t *reg; ir_node *original_insn; ir_node *block; ir_node *copy; unsigned r; + unsigned from_r; unsigned i; allocation_info_t *info = get_allocation_info(to_split); reg_pref_t *prefs; @@ -689,41 +711,85 @@ static bool try_optimistic_split(ir_node *to_split, ir_node *before, if (arch_irn_get_flags(original_insn) & arch_irn_flags_dont_spill) return false; + from_reg = arch_get_irn_register(to_split); + from_r = arch_register_get_index(from_reg); + block = get_nodes_block(before); + split_threshold = get_block_execfreq(execfreqs, block) * SPLIT_DELTA; + + if (pref_delta < split_threshold*0.5) + return false; + /* find the best free position where we could move to */ prefs = ALLOCAN(reg_pref_t, n_regs); fill_sort_candidates(prefs, info); for (i = 0; i < n_regs; ++i) { + float apref; + float apref_delta; + bool res; + bool old_source_state; + + /* we need a normal register which is not an output register + an different from the current register of to_split */ r = prefs[i].num; if (!rbitset_is_set(normal_regs, r)) continue; - if (rbitset_is_set(output_regs, r)) + if (rbitset_is_set(forbidden_regs, r)) + continue; + if (r == from_r) continue; + + /* is the split worth it? */ + delta = pref_delta + prefs[i].pref; + if (delta < split_threshold) { + DB((dbg, LEVEL_3, "Not doing optimistical split of %+F (depth %d), win %f too low\n", + to_split, recursion, delta)); + return false; + } + + /* if the register is free then we can do the split */ if (assignments[r] == NULL) break; + + /* otherwise we might try recursively calling optimistic_split */ + if (recursion+1 > MAX_OPTIMISTIC_SPLIT_RECURSION) + continue; + + apref = prefs[i].pref; + apref_delta = i+1 < n_regs ? apref - prefs[i+1].pref : 0; + apref_delta += pref_delta - split_threshold; + + /* our source register isn't a usefull destination for recursive + splits */ + old_source_state = rbitset_is_set(forbidden_regs, from_r); + rbitset_set(forbidden_regs, from_r); + /* try recursive split */ + res = try_optimistic_split(assignments[r], before, apref, + apref_delta, forbidden_regs, recursion+1); + /* restore our destination */ + if (old_source_state) { + rbitset_set(forbidden_regs, from_r); + } else { + rbitset_clear(forbidden_regs, from_r); + } + + if (res) + break; } - if (i >= n_regs) { - return false; - } - /* TODO: use execfreq somehow... */ - block = get_nodes_block(before); - delta = pref_delta + prefs[i].pref; - split_threshold = get_block_execfreq(execfreqs, block) * SPLIT_DELTA; - if (delta < split_threshold) { - DB((dbg, LEVEL_3, "Not doing optimistical split, win %f too low\n", - delta)); + if (i >= n_regs) return false; - } - reg = arch_register_for_index(cls, r); + reg = arch_register_for_index(cls, r); copy = be_new_Copy(cls, block, to_split); mark_as_copy_of(copy, to_split); - free_reg_of_value(to_split); + /* hacky, but correct here */ + if (assignments[arch_register_get_index(from_reg)] == to_split) + free_reg_of_value(to_split); use_reg(copy, reg); sched_add_before(before, copy); DB((dbg, LEVEL_3, - "Optimistic live-range split %+F move %+F -> %s before %+F (win %f)\n", - copy, to_split, reg->name, before, delta)); + "Optimistic live-range split %+F move %+F(%s) -> %s before %+F (win %f, depth %d)\n", + copy, to_split, from_reg->name, reg->name, before, delta, recursion)); return true; } @@ -731,7 +797,7 @@ static bool try_optimistic_split(ir_node *to_split, ir_node *before, * Determine and assign a register for node @p node */ static void assign_reg(const ir_node *block, ir_node *node, - unsigned *output_regs) + unsigned *forbidden_regs) { const arch_register_t *reg; allocation_info_t *info; @@ -742,6 +808,7 @@ static void assign_reg(const ir_node *block, ir_node *node, const unsigned *allowed_regs; unsigned r; + assert(!is_Phi(node)); assert(arch_irn_consider_in_reg_alloc(cls, node)); /* preassigned register? */ @@ -806,21 +873,22 @@ static void assign_reg(const ir_node *block, ir_node *node, } for (i = 0; i < n_regs; ++i) { + float pref, delta; + ir_node *before; + bool res; + r = reg_prefs[i].num; if (!rbitset_is_set(allowed_regs, r)) continue; if (assignments[r] == NULL) break; - if (!is_Phi(node)) { - float pref = reg_prefs[i].pref; - float delta = i+1 < n_regs ? pref - reg_prefs[i+1].pref : 0; - ir_node *before = skip_Proj(node); - bool res = try_optimistic_split(assignments[r], before, - pref, delta, - output_regs); - if (res) - break; - } + pref = reg_prefs[i].pref; + delta = i+1 < n_regs ? pref - reg_prefs[i+1].pref : 0; + before = skip_Proj(node); + res = try_optimistic_split(assignments[r], before, + pref, delta, forbidden_regs, 0); + if (res) + break; } if (i >= n_regs) { panic("No register left for %+F\n", node); @@ -1042,12 +1110,11 @@ static void rewire_inputs(ir_node *node) for (i = 0; i < arity; ++i) { ir_node *op = get_irn_n(node, i); - allocation_info_t *info; + allocation_info_t *info = try_get_allocation_info(op); - if (!arch_irn_consider_in_reg_alloc(cls, op)) + if (info == NULL) continue; - info = get_allocation_info(op); info = get_allocation_info(info->original_value); if (info->current_value != op) { set_irn_n(node, i, info->current_value); @@ -1098,7 +1165,7 @@ static void determine_live_through_regs(unsigned *bitset, ir_node *node) * @param node the current node */ static void enforce_constraints(ir_nodeset_t *live_nodes, ir_node *node, - unsigned *output_regs) + unsigned *forbidden_regs) { int arity = get_irn_arity(node); int i, res; @@ -1156,7 +1223,7 @@ static void enforce_constraints(ir_nodeset_t *live_nodes, ir_node *node, determine_live_through_regs(live_through_regs, node); } - rbitset_or(output_regs, req->limited, n_regs); + rbitset_or(forbidden_regs, req->limited, n_regs); if (rbitsets_have_common(req->limited, live_through_regs, n_regs)) { good = false; } @@ -1169,7 +1236,7 @@ static void enforce_constraints(ir_nodeset_t *live_nodes, ir_node *node, determine_live_through_regs(live_through_regs, node); if (rbitsets_have_common(req->limited, live_through_regs, n_regs)) { good = false; - rbitset_or(output_regs, req->limited, n_regs); + rbitset_or(forbidden_regs, req->limited, n_regs); } } } @@ -1203,7 +1270,7 @@ static void enforce_constraints(ir_nodeset_t *live_nodes, ir_node *node, continue; /* livethrough values may not use constrainted output registers */ if (rbitset_is_set(live_through_regs, l) - && rbitset_is_set(output_regs, r)) + && rbitset_is_set(forbidden_regs, r)) continue; hungarian_add(bp, r, l, l == r ? 9 : 8); @@ -1329,7 +1396,7 @@ static void add_phi_permutations(ir_node *block, int p) if (!arch_irn_consider_in_reg_alloc(cls, op)) continue; - a = find_value_in_block_info(pred_info, op); + a = find_value_in_block_info(pred_info, op); assert(a >= 0); reg = arch_get_irn_register(node); @@ -1414,9 +1481,9 @@ static void adapt_phi_prefs(ir_node *phi) */ static void propagate_phi_register(ir_node *phi, unsigned assigned_r) { - int i; - ir_node *block = get_nodes_block(phi); - int arity = get_irn_arity(phi); + int i; + ir_node *block = get_nodes_block(phi); + int arity = get_irn_arity(phi); for (i = 0; i < arity; ++i) { ir_node *op = get_Phi_pred(phi, i); @@ -1431,12 +1498,11 @@ static void propagate_phi_register(ir_node *phi, unsigned assigned_r) /* promote the prefered register */ for (r = 0; r < n_regs; ++r) { - if (r == assigned_r) { - info->prefs[r] = AFF_PHI * weight; - } else { - info->prefs[r] -= AFF_PHI * weight; + if (info->prefs[r] > -weight) { + info->prefs[r] = -weight; } } + info->prefs[assigned_r] = weight; if (is_Phi(op)) propagate_phi_register(op, assigned_r); @@ -1524,7 +1590,8 @@ static void assign_phi_registers(ir_node *block) use_reg(node, reg); /* adapt preferences for phi inputs */ - propagate_phi_register(node, r); + if (propagate_phi_registers) + propagate_phi_register(node, r); } } @@ -1536,14 +1603,13 @@ static void allocate_coalesce_block(ir_node *block, void *data) { int i; ir_nodeset_t live_nodes; - ir_nodeset_iterator_t iter; ir_node *node; int n_preds; block_info_t *block_info; block_info_t **pred_block_infos; ir_node **phi_ins; - unsigned *output_regs; /**< collects registers which must not - be used for optimistic splits */ + unsigned *forbidden_regs; /**< collects registers which must + not be used for optimistic splits */ (void) data; DB((dbg, LEVEL_2, "* Block %+F\n", block)); @@ -1602,17 +1668,19 @@ static void allocate_coalesce_block(ir_node *block, void *data) ir_mode *mode = get_irn_mode(node); const arch_register_req_t *req = get_default_req_current_cls(); ir_node *phi; - int i; phi = new_r_Phi(block, n_preds, phi_ins, mode); be_set_phi_reg_req(phi, req); DB((dbg, LEVEL_3, "Create Phi %+F (for %+F) -", phi, node)); #ifdef DEBUG_libfirm - for (i = 0; i < n_preds; ++i) { - DB((dbg, LEVEL_3, " %+F", phi_ins[i])); + { + int i; + for (i = 0; i < n_preds; ++i) { + DB((dbg, LEVEL_3, " %+F", phi_ins[i])); + } + DB((dbg, LEVEL_3, "\n")); } - DB((dbg, LEVEL_3, "\n")); #endif mark_as_copy_of(phi, node); sched_add_after(block, phi); @@ -1631,11 +1699,6 @@ static void allocate_coalesce_block(ir_node *block, void *data) /* if the node already has a register assigned use it */ reg = arch_get_irn_register(node); if (reg != NULL) { - /* TODO: consult pred-block infos here. The value could be copied - away in some/all predecessor blocks. We need to construct - phi-nodes in this case. - We even need to construct some Phi_0 like constructs in cases - where the predecessor allocation is not determined yet. */ use_reg(node, reg); } @@ -1643,25 +1706,26 @@ static void allocate_coalesce_block(ir_node *block, void *data) ir_nodeset_insert(&live_nodes, node); } - rbitset_alloca(output_regs, n_regs); + rbitset_alloca(forbidden_regs, n_regs); /* handle phis... */ assign_phi_registers(block); - /* assign regs for live-in values */ - foreach_ir_nodeset(&live_nodes, node, iter) { - const arch_register_t *reg = arch_get_irn_register(node); - if (reg != NULL) - continue; - - assign_reg(block, node, output_regs); - /* shouldn't happen if we color in dominance order */ - assert (!is_Phi(node)); + /* all live-ins must have a register */ +#ifdef DEBUG_libfirm + { + ir_nodeset_iterator_t iter; + foreach_ir_nodeset(&live_nodes, node, iter) { + const arch_register_t *reg = arch_get_irn_register(node); + assert(reg != NULL); + } } +#endif /* assign instructions in the block */ sched_foreach(block, node) { - unsigned r; + int i; + int arity; /* phis are already assigned */ if (is_Phi(node)) @@ -1670,16 +1734,23 @@ static void allocate_coalesce_block(ir_node *block, void *data) rewire_inputs(node); /* enforce use constraints */ - rbitset_clear_all(output_regs, n_regs); - enforce_constraints(&live_nodes, node, output_regs); - /* we may not use registers occupied here for optimistic splits */ - for (r = 0; r < n_regs; ++r) { - if (assignments[r] != NULL) - rbitset_set(output_regs, r); - } + rbitset_clear_all(forbidden_regs, n_regs); + enforce_constraints(&live_nodes, node, forbidden_regs); rewire_inputs(node); + /* we may not use registers used for inputs for optimistic splits */ + arity = get_irn_arity(node); + for (i = 0; i < arity; ++i) { + ir_node *op = get_irn_n(node, i); + const arch_register_t *reg; + if (!arch_irn_consider_in_reg_alloc(cls, op)) + continue; + + reg = arch_get_irn_register(op); + rbitset_set(forbidden_regs, arch_register_get_index(reg)); + } + /* free registers of values last used at this instruction */ free_last_uses(&live_nodes, node); @@ -1691,10 +1762,10 @@ static void allocate_coalesce_block(ir_node *block, void *data) ir_node *proj = get_edge_src_irn(edge); if (!arch_irn_consider_in_reg_alloc(cls, proj)) continue; - assign_reg(block, proj, output_regs); + assign_reg(block, proj, forbidden_regs); } } else if (arch_irn_consider_in_reg_alloc(cls, node)) { - assign_reg(block, node, output_regs); + assign_reg(block, node, forbidden_regs); } } @@ -1851,15 +1922,16 @@ static void be_straight_alloc_cls(void) lv = be_assure_liveness(birg); be_liveness_assure_sets(lv); - be_liveness_assure_chk(lv); ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK); DB((dbg, LEVEL_2, "=== Allocating registers of %s ===\n", cls->name)); be_clear_links(irg); + irg_block_walk_graph(irg, NULL, analyze_block, NULL); - combine_congruence_classes(); + if (create_congruence_classes) + combine_congruence_classes(); for (i = 0; i < n_block_order; ++i) { ir_node *block = block_order[i]; @@ -1981,10 +2053,12 @@ void be_init_straight_alloc(void) static be_ra_t be_ra_straight = { be_straight_alloc, }; - - FIRM_DBG_REGISTER(dbg, "firm.be.straightalloc"); + lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be"); + lc_opt_entry_t *straightalloc_group = lc_opt_get_grp(be_grp, "straightalloc"); + lc_opt_add_table(straightalloc_group, options); be_register_allocator("straight", &be_ra_straight); + FIRM_DBG_REGISTER(dbg, "firm.be.straightalloc"); } BE_REGISTER_MODULE_CONSTRUCTOR(be_init_straight_alloc);