X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeprefalloc.c;h=5a80f9ccba00b7430edf6ebedc38cc8ea9be0232;hb=ee2ce90606e3b629b45482964a70a71a46aa6966;hp=a99d2ac0c9e1037d0336e2d88cba9e702d99bdc3;hpb=efdb09dd64658e15cd9fd2599884bfe72bba7fd2;p=libfirm diff --git a/ir/be/beprefalloc.c b/ir/be/beprefalloc.c index a99d2ac0c..5a80f9ccb 100644 --- a/ir/be/beprefalloc.c +++ b/ir/be/beprefalloc.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -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,14 +87,13 @@ 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; static unsigned *normal_regs; static int *congruence_classes; static ir_node **block_order; -static int n_block_order; +static size_t n_block_order; static int create_preferences = true; static int create_congruence_classes = true; static int propagate_phi_registers = true; @@ -141,7 +141,7 @@ typedef struct block_info_t block_info_t; */ static allocation_info_t *get_allocation_info(ir_node *node) { - allocation_info_t *info = get_irn_link(node); + allocation_info_t *info = (allocation_info_t*)get_irn_link(node); if (info == NULL) { info = OALLOCFZ(&obst, allocation_info_t, prefs, n_regs); info->current_value = node; @@ -162,7 +162,7 @@ static allocation_info_t *try_get_allocation_info(const ir_node *node) */ static block_info_t *get_block_info(ir_node *block) { - block_info_t *info = get_irn_link(block); + block_info_t *info = (block_info_t*)get_irn_link(block); assert(is_Block(block)); if (info == NULL) { @@ -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. @@ -235,7 +218,7 @@ static void give_penalties_for_limits(const ir_nodeset_t *live_nodes, { ir_nodeset_iterator_t iter; unsigned r; - unsigned n_allowed; + size_t n_allowed; allocation_info_t *info = get_allocation_info(node); ir_node *neighbor; @@ -367,8 +350,9 @@ static void analyze_block(ir_node *block, void *data) 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? */ @@ -651,12 +635,12 @@ static bool try_optimistic_split(ir_node *to_split, ir_node *before, ir_node *original_insn; ir_node *block; ir_node *copy; - unsigned r; + unsigned r = 0; unsigned from_r; unsigned i; allocation_info_t *info = get_allocation_info(to_split); reg_pref_t *prefs; - float delta; + float delta = 0; float split_threshold; (void) pref; @@ -763,11 +747,9 @@ static void assign_reg(const ir_node *block, ir_node *node, ir_node *in_node; unsigned i; const unsigned *allowed_regs; - unsigned r; + unsigned r = 0; assert(!is_Phi(node)); - assert(arch_irn_consider_in_reg_alloc(cls, node)); - /* preassigned register? */ reg = arch_get_irn_register(node); if (reg != NULL) { @@ -776,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); @@ -810,7 +794,7 @@ static void assign_reg(const ir_node *block, ir_node *node, /* create list of register candidates and sort by their preference */ DB((dbg, LEVEL_2, "Candidates for %+F:", node)); - reg_prefs = alloca(n_regs * sizeof(reg_prefs[0])); + reg_prefs = ALLOCAN(reg_pref_t, n_regs); fill_sort_candidates(reg_prefs, info); for (i = 0; i < n_regs; ++i) { unsigned num = reg_prefs[i].num; @@ -875,7 +859,7 @@ static void assign_reg(const ir_node *block, ir_node *node, * First we count how many destinations a single value has. At the same time * we can be sure that each destination register has at most 1 source register * (it can have 0 which means we don't care what value is in it). - * We ignore all fullfilled permuations (like 7->7) + * We ignore all fulfilled permuations (like 7->7) * In a first pass we create as much copy instructions as possible as they * are generally cheaper than exchanges. We do this by counting into how many * destinations a register has to be copied (in the example it's 2 for register @@ -883,8 +867,8 @@ static void assign_reg(const ir_node *block, ir_node *node, * We can then create a copy into every destination register when the usecount * of that register is 0 (= noone else needs the value in the register). * - * After this step we should have cycles left. We implement a cyclic permutation - * of n registers with n-1 transpositions. + * After this step we should only have cycles left. We implement a cyclic + * permutation of n registers with n-1 transpositions. * * @param live_nodes the set of live nodes, updated due to live range split * @param before the node before we add the permutation @@ -1041,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; @@ -1255,7 +1239,7 @@ static void enforce_constraints(ir_nodeset_t *live_nodes, ir_node *node, permute_values(live_nodes, node, assignment); } -/** test wether a node @p n is a copy of the value of node @p of */ +/** test whether a node @p n is a copy of the value of node @p of */ static bool is_copy_of(ir_node *value, ir_node *test_value) { allocation_info_t *test_info; @@ -1300,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); @@ -1316,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) { @@ -1346,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); } } @@ -1535,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; @@ -1555,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); @@ -1567,13 +1555,25 @@ 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 @@ -1599,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 @@ -1690,8 +1686,7 @@ 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 */ - be_foreach_definition(node, cls, value, + be_foreach_definition_(node, cls, value, assign_reg(block, value, forbidden_regs); ); } @@ -1732,22 +1727,22 @@ struct block_costs_t { static int cmp_block_costs(const void *d1, const void *d2) { - const ir_node * const *block1 = d1; - const ir_node * const *block2 = d2; - const block_costs_t *info1 = get_irn_link(*block1); - const block_costs_t *info2 = get_irn_link(*block2); + const ir_node * const *block1 = (const ir_node**)d1; + const ir_node * const *block2 = (const ir_node**)d2; + const block_costs_t *info1 = (const block_costs_t*)get_irn_link(*block1); + const block_costs_t *info2 = (const block_costs_t*)get_irn_link(*block2); return QSORT_CMP(info2->costs, info1->costs); } static void determine_block_order(void) { - int i; + size_t i; ir_node **blocklist = be_get_cfgpostorder(irg); - int n_blocks = ARR_LEN(blocklist); + size_t n_blocks = ARR_LEN(blocklist); int dfs_num = 0; pdeq *worklist = new_pdeq(); ir_node **order = XMALLOCN(ir_node*, n_blocks); - int order_p = 0; + size_t order_p = 0; /* clear block links... */ for (i = 0; i < n_blocks; ++i) { @@ -1758,9 +1753,9 @@ static void determine_block_order(void) /* walk blocks in reverse postorder, the costs for each block are the * sum of the costs of its predecessors (excluding the costs on backedges * which we can't determine) */ - for (i = n_blocks-1; i >= 0; --i) { + for (i = n_blocks; i > 0;) { block_costs_t *cost_info; - ir_node *block = blocklist[i]; + ir_node *block = blocklist[--i]; float execfreq = (float)get_block_execfreq(execfreqs, block); float costs = execfreq; @@ -1768,7 +1763,7 @@ static void determine_block_order(void) int p; for (p = 0; p < n_cfgpreds; ++p) { ir_node *pred_block = get_Block_cfgpred_block(block, p); - block_costs_t *pred_costs = get_irn_link(pred_block); + block_costs_t *pred_costs = (block_costs_t*)get_irn_link(pred_block); /* we don't have any info for backedges */ if (pred_costs == NULL) continue; @@ -1795,7 +1790,7 @@ static void determine_block_order(void) /* continually add predecessors with highest costs to worklist * (without using backedges) */ do { - block_costs_t *info = get_irn_link(block); + block_costs_t *info = (block_costs_t*)get_irn_link(block); ir_node *best_pred = NULL; float best_costs = -1; int n_cfgpred = get_Block_n_cfgpreds(block); @@ -1805,7 +1800,7 @@ static void determine_block_order(void) mark_Block_block_visited(block); for (i = 0; i < n_cfgpred; ++i) { ir_node *pred_block = get_Block_cfgpred_block(block, i); - block_costs_t *pred_info = get_irn_link(pred_block); + block_costs_t *pred_info = (block_costs_t*)get_irn_link(pred_block); /* ignore backedges */ if (pred_info->dfs_num > info->dfs_num) @@ -1821,7 +1816,7 @@ static void determine_block_order(void) /* now put all nodes in the worklist in our final order */ while (!pdeq_empty(worklist)) { - ir_node *pblock = pdeq_getr(worklist); + ir_node *pblock = (ir_node*)pdeq_getr(worklist); assert(order_p < n_blocks); order[order_p++] = pblock; } @@ -1845,7 +1840,7 @@ static void determine_block_order(void) */ static void be_pref_alloc_cls(void) { - int i; + size_t i; lv = be_assure_liveness(irg); be_liveness_assure_sets(lv); @@ -1904,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); @@ -1916,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; @@ -1925,7 +1919,7 @@ 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(); @@ -1970,7 +1964,7 @@ static void be_pref_alloc(ir_graph *new_irg) obstack_free(&obst, NULL); } -BE_REGISTER_MODULE_CONSTRUCTOR(be_init_pref_alloc); +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_pref_alloc) void be_init_pref_alloc(void) { static be_ra_t be_ra_pref = {