X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;ds=sidebyside;f=ir%2Fbe%2Fbeprefalloc.c;h=9c759ade24b1cbe04ef509f722c88b2d1c9503a1;hb=8a1c0ad68eaba7cecab7a3abd552681ad893de3e;hp=cbe3c68c2eb5b66497a9a26a3fd2d749c8b87ac9;hpb=7a178059678ff6c6094a7cd8fac5644367417102;p=libfirm diff --git a/ir/be/beprefalloc.c b/ir/be/beprefalloc.c index cbe3c68c2..9c759ade2 100644 --- a/ir/be/beprefalloc.c +++ b/ir/be/beprefalloc.c @@ -72,6 +72,7 @@ #include "bespillutil.h" #include "beverify.h" #include "beutil.h" +#include "bestack.h" #define USE_FACTOR 1.0f #define DEF_FACTOR 1.0f @@ -86,7 +87,6 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) static struct obstack obst; static ir_graph *irg; static const arch_register_class_t *cls; -static const arch_register_req_t *default_cls_req; static be_lv_t *lv; static const ir_exec_freq *execfreqs; static unsigned n_regs; @@ -114,7 +114,7 @@ static ir_node **assignments; * the information is per firm-node. */ struct allocation_info_t { - unsigned last_uses; /**< bitset indicating last uses (input pos) */ + unsigned last_uses[2]; /**< bitset indicating last uses (input pos) */ ir_node *current_value; /**< copy of the value that should be used */ ir_node *original_value; /**< for copies point to original value */ float prefs[0]; /**< register preferences */ @@ -173,23 +173,6 @@ static block_info_t *get_block_info(ir_node *block) return info; } -/** - * Get default register requirement for the current register class - */ -static const arch_register_req_t *get_default_req_current_cls(void) -{ - if (default_cls_req == NULL) { - struct obstack *obst = get_irg_obstack(irg); - arch_register_req_t *req = OALLOCZ(obst, arch_register_req_t); - - req->type = arch_register_req_type_normal; - req->cls = cls; - - default_cls_req = req; - } - return default_cls_req; -} - /** * Link the allocation info of a node to a copy. * Afterwards, both nodes uses the same allocation info. @@ -287,21 +270,7 @@ static void give_penalties_for_limits(const ir_nodeset_t *live_nodes, static void check_defs(const ir_nodeset_t *live_nodes, float weight, ir_node *node) { - const arch_register_req_t *req; - - if (get_irn_mode(node) == mode_T) { - const ir_edge_t *edge; - foreach_out_edge(node, edge) { - ir_node *proj = get_edge_src_irn(edge); - check_defs(live_nodes, weight, proj); - } - return; - } - - if (!arch_irn_consider_in_reg_alloc(cls, node)) - return; - - req = arch_get_register_req_out(node); + const arch_register_req_t *req = arch_get_register_req_out(node); if (req->type & arch_register_req_type_limited) { const unsigned *limited = req->limited; float penalty = weight * DEF_FACTOR; @@ -361,8 +330,12 @@ static void analyze_block(ir_node *block, void *data) if (is_Phi(node)) break; - if (create_preferences) - check_defs(&live_nodes, weight, node); + if (create_preferences) { + ir_node *value; + be_foreach_definition(node, cls, value, + check_defs(&live_nodes, weight, value); + ); + } /* mark last uses */ arity = get_irn_arity(node); @@ -370,20 +343,21 @@ static void analyze_block(ir_node *block, void *data) /* the allocation info node currently only uses 1 unsigned value to mark last used inputs. So we will fail for a node with more than 32 inputs. */ - if (arity >= (int) sizeof(unsigned) * 8) { + if (arity >= (int) sizeof(info->last_uses) * 8) { panic("Node with more than %d inputs not supported yet", - (int) sizeof(unsigned) * 8); + (int) sizeof(info->last_uses) * 8); } info = get_allocation_info(node); for (i = 0; i < arity; ++i) { - ir_node *op = get_irn_n(node, i); - if (!arch_irn_consider_in_reg_alloc(cls, op)) + ir_node *op = get_irn_n(node, i); + const arch_register_req_t *req = arch_get_register_req_out(op); + if (req->cls != cls) continue; /* last usage of a value? */ if (!ir_nodeset_contains(&live_nodes, op)) { - rbitset_set(&info->last_uses, i); + rbitset_set(info->last_uses, i); } } @@ -413,26 +387,13 @@ static void analyze_block(ir_node *block, void *data) ir_nodeset_destroy(&live_nodes); } -static void congruence_def(ir_nodeset_t *live_nodes, ir_node *node) +static void congruence_def(ir_nodeset_t *live_nodes, const ir_node *node) { - const arch_register_req_t *req; - - if (get_irn_mode(node) == mode_T) { - const ir_edge_t *edge; - foreach_out_edge(node, edge) { - ir_node *def = get_edge_src_irn(edge); - congruence_def(live_nodes, def); - } - return; - } - - if (!arch_irn_consider_in_reg_alloc(cls, node)) - return; + const arch_register_req_t *req = arch_get_register_req_out(node); /* should be same constraint? */ - req = arch_get_register_req_out(node); if (req->type & arch_register_req_type_should_be_same) { - ir_node *insn = skip_Proj(node); + const ir_node *insn = skip_Proj_const(node); int arity = get_irn_arity(insn); int i; unsigned node_idx = get_irn_idx(node); @@ -485,10 +446,13 @@ static void create_congruence_class(ir_node *block, void *data) /* check should be same constraints */ sched_foreach_reverse(block, node) { + ir_node *value; if (is_Phi(node)) break; - congruence_def(&live_nodes, node); + be_foreach_definition(node, cls, value, + congruence_def(&live_nodes, value); + ); be_liveness_transfer(cls, node, &live_nodes); } @@ -605,8 +569,6 @@ static void combine_congruence_classes(void) - - /** * Assign register reg to the given node. * @@ -788,8 +750,6 @@ static void assign_reg(const ir_node *block, ir_node *node, unsigned r; assert(!is_Phi(node)); - assert(arch_irn_consider_in_reg_alloc(cls, node)); - /* preassigned register? */ reg = arch_get_irn_register(node); if (reg != NULL) { @@ -798,10 +758,12 @@ static void assign_reg(const ir_node *block, ir_node *node, return; } - /* give should_be_same boni */ - info = get_allocation_info(node); - req = arch_get_register_req_out(node); + req = arch_get_register_req_out(node); + /* ignore reqs must be preassigned */ + assert (! (req->type & arch_register_req_type_ignore)); + /* give should_be_same boni */ + info = get_allocation_info(node); in_node = skip_Proj(node); if (req->type & arch_register_req_type_should_be_same) { float weight = (float)get_block_execfreq(execfreqs, block); @@ -870,6 +832,8 @@ static void assign_reg(const ir_node *block, ir_node *node, break; } if (i >= n_regs) { + /* the common reason to hit this panic is when 1 of your nodes is not + * register pressure faithful */ panic("No register left for %+F\n", node); } @@ -1061,10 +1025,10 @@ static void permute_values(ir_nodeset_t *live_nodes, ir_node *before, */ static void free_last_uses(ir_nodeset_t *live_nodes, ir_node *node) { - allocation_info_t *info = get_allocation_info(node); - const unsigned *last_uses = &info->last_uses; - int arity = get_irn_arity(node); - int i; + allocation_info_t *info = get_allocation_info(node); + const unsigned *last_uses = info->last_uses; + int arity = get_irn_arity(node); + int i; for (i = 0; i < arity; ++i) { ir_node *op; @@ -1128,7 +1092,7 @@ static void determine_live_through_regs(unsigned *bitset, ir_node *node) ir_node *op; const arch_register_t *reg; - if (!rbitset_is_set(&info->last_uses, i)) + if (!rbitset_is_set(info->last_uses, i)) continue; op = get_irn_n(node, i); @@ -1151,6 +1115,7 @@ static void enforce_constraints(ir_nodeset_t *live_nodes, ir_node *node, hungarian_problem_t *bp; unsigned l, r; unsigned *assignment; + ir_node *value; /* construct a list of register occupied by live-through values */ unsigned *live_through_regs = NULL; @@ -1183,43 +1148,17 @@ static void enforce_constraints(ir_nodeset_t *live_nodes, ir_node *node, } /* is any of the live-throughs using a constrained output register? */ - if (get_irn_mode(node) == mode_T) { - const ir_edge_t *edge; - - foreach_out_edge(node, edge) { - ir_node *proj = get_edge_src_irn(edge); - const arch_register_req_t *req; - - if (!arch_irn_consider_in_reg_alloc(cls, proj)) - continue; - - req = arch_get_register_req_out(proj); - if (!(req->type & arch_register_req_type_limited)) - continue; - - if (live_through_regs == NULL) { - rbitset_alloca(live_through_regs, n_regs); - determine_live_through_regs(live_through_regs, node); - } - - rbitset_or(forbidden_regs, req->limited, n_regs); - if (rbitsets_have_common(req->limited, live_through_regs, n_regs)) { - good = false; - } - } - } else { - if (arch_irn_consider_in_reg_alloc(cls, node)) { - const arch_register_req_t *req = arch_get_register_req_out(node); - if (req->type & arch_register_req_type_limited) { - rbitset_alloca(live_through_regs, n_regs); - determine_live_through_regs(live_through_regs, node); - if (rbitsets_have_common(req->limited, live_through_regs, n_regs)) { - good = false; - rbitset_or(forbidden_regs, req->limited, n_regs); - } - } + be_foreach_definition(node, cls, value, + if (! (req_->type & arch_register_req_type_limited)) + continue; + if (live_through_regs == NULL) { + rbitset_alloca(live_through_regs, n_regs); + determine_live_through_regs(live_through_regs, node); } - } + rbitset_or(forbidden_regs, req_->limited, n_regs); + if (rbitsets_have_common(req_->limited, live_through_regs, n_regs)) + good = false; + ); if (good) return; @@ -1276,7 +1215,7 @@ static void enforce_constraints(ir_nodeset_t *live_nodes, ir_node *node, for (r = 0; r < n_regs; ++r) { if (rbitset_is_set(limited, r)) continue; - hungarian_remv(bp, r, current_reg); + hungarian_remove(bp, r, current_reg); } } @@ -1284,7 +1223,7 @@ static void enforce_constraints(ir_nodeset_t *live_nodes, ir_node *node, hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL); assignment = ALLOCAN(unsigned, n_regs); - res = hungarian_solve(bp, (int*) assignment, NULL, 0); + res = hungarian_solve(bp, assignment, NULL, 0); assert(res == 0); #if 0 @@ -1345,7 +1284,7 @@ static void add_phi_permutations(ir_node *block, int p) unsigned *permutation; ir_node **old_assignments; bool need_permutation; - ir_node *node; + ir_node *phi; ir_node *pred = get_Block_cfgpred_block(block, p); block_info_t *pred_info = get_block_info(pred); @@ -1361,29 +1300,36 @@ static void add_phi_permutations(ir_node *block, int p) /* check phi nodes */ need_permutation = false; - node = sched_first(block); - for ( ; is_Phi(node); node = sched_next(node)) { + phi = sched_first(block); + for ( ; is_Phi(phi); phi = sched_next(phi)) { const arch_register_t *reg; + const arch_register_t *op_reg; int regn; int a; ir_node *op; - if (!arch_irn_consider_in_reg_alloc(cls, node)) - continue; - - op = get_Phi_pred(node, p); - if (!arch_irn_consider_in_reg_alloc(cls, op)) + if (!arch_irn_consider_in_reg_alloc(cls, phi)) continue; - a = find_value_in_block_info(pred_info, op); + op = get_Phi_pred(phi, p); + a = find_value_in_block_info(pred_info, op); assert(a >= 0); - reg = arch_get_irn_register(node); + reg = arch_get_irn_register(phi); regn = arch_register_get_index(reg); - if (regn != a) { - permutation[regn] = a; - need_permutation = true; - } + /* same register? nothing to do */ + if (regn == a) + continue; + + op = pred_info->assignments[a]; + op_reg = arch_get_irn_register(op); + /* virtual or joker registers are ok too */ + if ((op_reg->type & arch_register_type_joker) + || (op_reg->type & arch_register_type_virtual)) + continue; + + permutation[regn] = a; + need_permutation = true; } if (need_permutation) { @@ -1391,30 +1337,27 @@ static void add_phi_permutations(ir_node *block, int p) old_assignments = assignments; assignments = pred_info->assignments; permute_values(NULL, be_get_end_of_block_insertion_point(pred), - permutation); + permutation); assignments = old_assignments; } /* change phi nodes to use the copied values */ - node = sched_first(block); - for ( ; is_Phi(node); node = sched_next(node)) { + phi = sched_first(block); + for ( ; is_Phi(phi); phi = sched_next(phi)) { int a; ir_node *op; - if (!arch_irn_consider_in_reg_alloc(cls, node)) + if (!arch_irn_consider_in_reg_alloc(cls, phi)) continue; - op = get_Phi_pred(node, p); - /* no need to do anything for Unknown inputs */ - if (!arch_irn_consider_in_reg_alloc(cls, op)) - continue; + op = get_Phi_pred(phi, p); /* we have permuted all values into the correct registers so we can simply query which value occupies the phis register in the predecessor */ - a = arch_register_get_index(arch_get_irn_register(node)); + a = arch_register_get_index(arch_get_irn_register(phi)); op = pred_info->assignments[a]; - set_Phi_pred(node, p, op); + set_Phi_pred(phi, p, op); } } @@ -1493,7 +1436,7 @@ static void assign_phi_registers(ir_node *block) int n_phis = 0; int n; int res; - int *assignment; + unsigned *assignment; ir_node *node; hungarian_problem_t *bp; @@ -1547,7 +1490,7 @@ static void assign_phi_registers(ir_node *block) //hungarian_print_cost_matrix(bp, 7); hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL); - assignment = ALLOCAN(int, n_regs); + assignment = ALLOCAN(unsigned, n_regs); res = hungarian_solve(bp, assignment, NULL, 0); assert(res == 0); @@ -1562,7 +1505,7 @@ static void assign_phi_registers(ir_node *block) if (!arch_irn_consider_in_reg_alloc(cls, node)) continue; - r = assignment[n++]; + r = assignment[n++]; assert(rbitset_is_set(normal_regs, r)); reg = arch_register_for_index(cls, r); DB((dbg, LEVEL_2, "Assign %+F -> %s\n", node, reg->name)); @@ -1580,14 +1523,14 @@ static void assign_phi_registers(ir_node *block) */ static void allocate_coalesce_block(ir_node *block, void *data) { - int i; - ir_nodeset_t live_nodes; - ir_node *node; - int n_preds; - block_info_t *block_info; - block_info_t **pred_block_infos; - ir_node **phi_ins; - unsigned *forbidden_regs; /**< collects registers which must + int i; + ir_nodeset_t live_nodes; + ir_node *node; + int n_preds; + block_info_t *block_info; + block_info_t **pred_block_infos; + ir_node **phi_ins; + unsigned *forbidden_regs; /**< collects registers which must not be used for optimistic splits */ (void) data; @@ -1600,8 +1543,8 @@ static void allocate_coalesce_block(ir_node *block, void *data) ir_nodeset_init(&live_nodes); /* gather regalloc infos of predecessor blocks */ - n_preds = get_Block_n_cfgpreds(block); - pred_block_infos = ALLOCAN(block_info_t*, n_preds); + n_preds = get_Block_n_cfgpreds(block); + pred_block_infos = ALLOCAN(block_info_t*, n_preds); for (i = 0; i < n_preds; ++i) { ir_node *pred = get_Block_cfgpred_block(block, i); block_info_t *pred_info = get_block_info(pred); @@ -1612,14 +1555,26 @@ static void allocate_coalesce_block(ir_node *block, void *data) /* collect live-in nodes and preassigned values */ be_lv_foreach(lv, block, be_lv_state_in, i) { - const arch_register_t *reg; - int p; - bool need_phi = false; + bool need_phi = false; + const arch_register_req_t *req; + const arch_register_t *reg; + int p; node = be_lv_get_irn(lv, block, i); - if (!arch_irn_consider_in_reg_alloc(cls, node)) + req = arch_get_register_req_out(node); + if (req->cls != cls) continue; + if (req->type & arch_register_req_type_ignore) { + allocation_info_t *info = get_allocation_info(node); + info->current_value = node; + + reg = arch_get_irn_register(node); + assert(reg != NULL); /* ignore values must be preassigned */ + use_reg(node, reg); + continue; + } + /* check all predecessors for this value, if it is not everywhere the same or unknown then we have to construct a phi (we collect the potential phi inputs here) */ @@ -1644,12 +1599,8 @@ static void allocate_coalesce_block(ir_node *block, void *data) } if (need_phi) { - ir_mode *mode = get_irn_mode(node); - const arch_register_req_t *req = get_default_req_current_cls(); - ir_node *phi; - - phi = new_r_Phi(block, n_preds, phi_ins, mode); - be_set_phi_reg_req(phi, req); + ir_mode *mode = get_irn_mode(node); + ir_node *phi = be_new_Phi(block, n_preds, phi_ins, mode, cls); DB((dbg, LEVEL_3, "Create Phi %+F (for %+F) -", phi, node)); #ifdef DEBUG_libfirm @@ -1705,6 +1656,7 @@ static void allocate_coalesce_block(ir_node *block, void *data) sched_foreach(block, node) { int i; int arity; + ir_node *value; /* phis are already assigned */ if (is_Phi(node)) @@ -1734,18 +1686,9 @@ static void allocate_coalesce_block(ir_node *block, void *data) free_last_uses(&live_nodes, node); /* assign output registers */ - /* TODO: 2 phases: first: pre-assigned ones, 2nd real regs */ - if (get_irn_mode(node) == mode_T) { - const ir_edge_t *edge; - foreach_out_edge(node, edge) { - ir_node *proj = get_edge_src_irn(edge); - if (!arch_irn_consider_in_reg_alloc(cls, proj)) - continue; - assign_reg(block, proj, forbidden_regs); - } - } else if (arch_irn_consider_in_reg_alloc(cls, node)) { - assign_reg(block, node, forbidden_regs); - } + be_foreach_definition_(node, cls, value, + assign_reg(block, value, forbidden_regs); + ); } ir_nodeset_destroy(&live_nodes); @@ -1956,7 +1899,7 @@ static void spill(void) static void be_pref_alloc(ir_graph *new_irg) { const arch_env_t *arch_env = be_get_irg_arch_env(new_irg); - int n_cls = arch_env_get_n_reg_class(arch_env); + int n_cls = arch_env->n_register_classes; int c; obstack_init(&obst); @@ -1968,8 +1911,7 @@ static void be_pref_alloc(ir_graph *new_irg) determine_block_order(); for (c = 0; c < n_cls; ++c) { - cls = arch_env_get_reg_class(arch_env, c); - default_cls_req = NULL; + cls = &arch_env->register_classes[c]; if (arch_register_class_flags(cls) & arch_register_class_flag_manual_ra) continue; @@ -1977,16 +1919,16 @@ static void be_pref_alloc(ir_graph *new_irg) n_regs = arch_register_class_n_regs(cls); normal_regs = rbitset_malloc(n_regs); - be_abi_set_non_ignore_regs(be_get_irg_abi(irg), cls, normal_regs); + be_set_allocatable_regs(irg, cls, normal_regs); spill(); /* verify schedule and register pressure */ be_timer_push(T_VERIFY); - if (be_get_irg_options(irg)->vrfy_option == BE_VRFY_WARN) { + if (be_get_irg_options(irg)->verify_option == BE_VERIFY_WARN) { be_verify_schedule(irg); be_verify_register_pressure(irg, cls); - } else if (be_get_irg_options(irg)->vrfy_option == BE_VRFY_ASSERT) { + } else if (be_get_irg_options(irg)->verify_option == BE_VERIFY_ASSERT) { assert(be_verify_schedule(irg) && "Schedule verification failed"); assert(be_verify_register_pressure(irg, cls) && "Register pressure verification failed"); @@ -2007,13 +1949,13 @@ static void be_pref_alloc(ir_graph *new_irg) } be_timer_push(T_RA_SPILL_APPLY); - be_abi_fix_stack_nodes(be_get_irg_abi(irg)); + be_abi_fix_stack_nodes(irg); be_timer_pop(T_RA_SPILL_APPLY); be_timer_push(T_VERIFY); - if (be_get_irg_options(irg)->vrfy_option == BE_VRFY_WARN) { + if (be_get_irg_options(irg)->verify_option == BE_VERIFY_WARN) { be_verify_register_allocation(irg); - } else if (be_get_irg_options(irg)->vrfy_option == BE_VRFY_ASSERT) { + } else if (be_get_irg_options(irg)->verify_option == BE_VERIFY_ASSERT) { assert(be_verify_register_allocation(irg) && "Register allocation invalid"); }