X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeabihelper.c;h=95c0635a4ad1dc635f18dc1b01e3767c2d6ab5ee;hb=b42d141b27222454d6176f233327c594d71be554;hp=40890a639df6731eee3216547dca27dde504448d;hpb=a0792e93ac867d761c40c9f5492975c1b3124d27;p=libfirm diff --git a/ir/be/beabihelper.c b/ir/be/beabihelper.c index 40890a639..95c0635a4 100644 --- a/ir/be/beabihelper.c +++ b/ir/be/beabihelper.c @@ -34,63 +34,87 @@ #include "iredges.h" #include "irgwalk.h" #include "irphase_t.h" -#include "height.h" +#include "heights.h" +/** + * An entry in the register state map. + */ typedef struct reg_flag_t { - const arch_register_t *reg; /**< register at an input position. - may be NULL in case of memory input */ - arch_irn_flags_t flags; + const arch_register_t *reg; /**< register at an input position. + may be NULL in case of memory input */ + arch_register_req_type_t flags; /**< requirement flags for this register. */ } reg_flag_t; /** * A register state mapping keeps track of the symbol values (=firm nodes) - * to registers. This is usefull when constructing straight line code - * which like the function prolog or epilog in some architectures. + * to registers. This is useful when constructing straight line code + * like the function prolog or epilog in some architectures. */ typedef struct register_state_mapping_t { ir_node **value_map; /**< mapping of state indices to values */ - int **reg_index_map; /**< mapping of regclass,regnum to an index + size_t **reg_index_map; /**< mapping of regclass,regnum to an index into the value_map */ reg_flag_t *regs; /**< registers (and memory values) that form a state */ ir_node *last_barrier; } register_state_mapping_t; +/** + * The environment for all helper functions. + */ struct beabi_helper_env_t { - ir_graph *irg; - register_state_mapping_t prolog; - register_state_mapping_t epilog; - ir_phase *stack_order; + ir_graph *irg; /**< the graph we operate on */ + register_state_mapping_t prolog; /**< the register state map for the prolog */ + register_state_mapping_t epilog; /**< the register state map for the epilog */ + ir_phase *stack_order; /**< a phase to handle stack dependencies. */ }; +/** + * Create a new empty register state map for the given + * architecture. + * + * @param rsm the register state map to be initialized + * @param arch_env the architecture environment + * + * After this call, the register map is initialized to empty. + */ static void prepare_rsm(register_state_mapping_t *rsm, const arch_env_t *arch_env) { - unsigned n_reg_classes = arch_env_get_n_reg_class(arch_env); + unsigned n_reg_classes = arch_env->n_register_classes; unsigned c; - reg_flag_t memory = { NULL, 0 }; + reg_flag_t memory = { NULL, arch_register_req_type_none }; rsm->regs = NEW_ARR_F(reg_flag_t, 0); /* memory input at 0 */ ARR_APP1(reg_flag_t, rsm->regs, memory); rsm->value_map = NULL; - rsm->reg_index_map = XMALLOCN(int*, n_reg_classes); + rsm->reg_index_map = XMALLOCN(size_t*, n_reg_classes); for (c = 0; c < n_reg_classes; ++c) { - const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, c); + const arch_register_class_t *cls = &arch_env->register_classes[c]; unsigned n_regs = arch_register_class_n_regs(cls); unsigned r; - rsm->reg_index_map[c] = XMALLOCN(int, n_regs); + rsm->reg_index_map[c] = XMALLOCN(size_t, n_regs); for (r = 0; r < n_regs; ++r) { - rsm->reg_index_map[c][r] = -1; + rsm->reg_index_map[c][r] = (size_t)-1; } } } +/** + * Destroy a register state map for the given + * architecture. + * + * @param rsm the register state map to be destroyed + * @param arch_env the architecture environment + * + * After this call, the register map is initialized to empty. + */ static void free_rsm(register_state_mapping_t *rsm, const arch_env_t *arch_env) { - unsigned n_reg_classes = arch_env_get_n_reg_class(arch_env); + unsigned n_reg_classes = arch_env->n_register_classes; unsigned c; for (c = 0; c < n_reg_classes; ++c) { @@ -107,20 +131,26 @@ static void free_rsm(register_state_mapping_t *rsm, const arch_env_t *arch_env) rsm->value_map = NULL; } +/** + * Remove all registers from a register state map. + * + * @param rsm the register state map to be destroyed + * @param arch_env the architecture environment + */ static void rsm_clear_regs(register_state_mapping_t *rsm, const arch_env_t *arch_env) { - unsigned n_reg_classes = arch_env_get_n_reg_class(arch_env); + unsigned n_reg_classes = arch_env->n_register_classes; unsigned c; - reg_flag_t memory = { NULL, 0 }; + reg_flag_t memory = { NULL, arch_register_req_type_none }; for (c = 0; c < n_reg_classes; ++c) { - const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, c); + const arch_register_class_t *cls = &arch_env->register_classes[c]; unsigned n_regs = arch_register_class_n_regs(cls); unsigned r; for (r = 0; r < n_regs; ++r) { - rsm->reg_index_map[c][r] = -1; + rsm->reg_index_map[c][r] = (size_t)-1; } } ARR_RESIZE(reg_flag_t, rsm->regs, 0); @@ -132,60 +162,88 @@ static void rsm_clear_regs(register_state_mapping_t *rsm, } } -static void rsm_add_reg(register_state_mapping_t *rsm, - const arch_register_t *reg, arch_irn_flags_t flags) +/** + * Add a register and its constraint flags to a register state map + * and return its index inside the map. + */ +static int rsm_add_reg(register_state_mapping_t *rsm, + const arch_register_t *reg, + arch_register_req_type_t flags) { - int input_idx = ARR_LEN(rsm->regs); + size_t input_idx = ARR_LEN(rsm->regs); int cls_idx = reg->reg_class->index; int reg_idx = reg->index; reg_flag_t regflag = { reg, flags }; /* we must not have used get_value yet */ - assert(rsm->reg_index_map[cls_idx][reg_idx] == -1); + assert(rsm->reg_index_map[cls_idx][reg_idx] == (size_t)-1); rsm->reg_index_map[cls_idx][reg_idx] = input_idx; ARR_APP1(reg_flag_t, rsm->regs, regflag); -} + if (rsm->value_map != NULL) { + ARR_APP1(ir_node*, rsm->value_map, NULL); + assert(ARR_LEN(rsm->value_map) == ARR_LEN(rsm->regs)); + } + return input_idx; +} -static ir_node *rsm_get_value(register_state_mapping_t *rsm, int index) +/** + * Retrieve the ir_node stored at the given index in the register state map. + */ +static ir_node *rsm_get_value(register_state_mapping_t *rsm, size_t index) { - assert(0 <= index && index < ARR_LEN(rsm->value_map)); + assert(index < ARR_LEN(rsm->value_map)); return rsm->value_map[index]; } +/** + * Retrieve the ir_node occupying the given register in the register state map. + */ static ir_node *rsm_get_reg_value(register_state_mapping_t *rsm, const arch_register_t *reg) { - int cls_idx = reg->reg_class->index; - int reg_idx = reg->index; - int input_idx = rsm->reg_index_map[cls_idx][reg_idx]; + int cls_idx = reg->reg_class->index; + int reg_idx = reg->index; + size_t input_idx = rsm->reg_index_map[cls_idx][reg_idx]; return rsm_get_value(rsm, input_idx); } -static void rsm_set_value(register_state_mapping_t *rsm, int index, +/** + * Enter a ir_node at the given index in the register state map. + */ +static void rsm_set_value(register_state_mapping_t *rsm, size_t index, ir_node *value) { - assert(0 <= index && index < ARR_LEN(rsm->value_map)); + assert(index < ARR_LEN(rsm->value_map)); rsm->value_map[index] = value; } +/** + * Enter a ir_node at the given register in the register state map. + */ static void rsm_set_reg_value(register_state_mapping_t *rsm, const arch_register_t *reg, ir_node *value) { - int cls_idx = reg->reg_class->index; - int reg_idx = reg->index; - int input_idx = rsm->reg_index_map[cls_idx][reg_idx]; + int cls_idx = reg->reg_class->index; + int reg_idx = reg->index; + size_t input_idx = rsm->reg_index_map[cls_idx][reg_idx]; rsm_set_value(rsm, input_idx, value); } +/** + * Create a Barrier from the registers stored at a register state map. + * + * @param rsm the register state map + * @param block the block to create the Barrier on + */ static ir_node *rsm_create_barrier(register_state_mapping_t *rsm, ir_node *block) { - int n_barrier_outs = ARR_LEN(rsm->regs); + size_t n_barrier_outs = ARR_LEN(rsm->regs); ir_node **in = rsm->value_map; ir_node *barrier; - int o; + size_t o; assert(ARR_LEN(rsm->value_map) == n_barrier_outs); @@ -199,7 +257,7 @@ static ir_node *rsm_create_barrier(register_state_mapping_t *rsm, arch_set_out_register_req(barrier, o, arch_no_register_req); proj = new_r_Proj(barrier, mode_M, o); } else { - be_set_constr_single_reg_in(barrier, o, reg, 0); + be_set_constr_single_reg_in(barrier, o, reg, arch_register_req_type_none); be_set_constr_single_reg_out(barrier, o, reg, regflag->flags); proj = new_r_Proj(barrier, reg->reg_class->mode, o); } @@ -235,11 +293,11 @@ void be_abihelper_finish(beabi_helper_env_t *env) if (env->epilog.reg_index_map != NULL) { free_rsm(&env->epilog, arch_env); } - free(env); + xfree(env); } void be_prolog_add_reg(beabi_helper_env_t *env, const arch_register_t *reg, - arch_irn_flags_t flags) + arch_register_req_type_t flags) { rsm_add_reg(&env->prolog, reg, flags); } @@ -315,10 +373,10 @@ void be_epilog_begin(beabi_helper_env_t *env) } void be_epilog_add_reg(beabi_helper_env_t *env, const arch_register_t *reg, - arch_irn_flags_t flags, ir_node *value) + arch_register_req_type_t flags, ir_node *value) { - rsm_add_reg(&env->epilog, reg, flags); - ARR_APP1(ir_node*, env->epilog.value_map, value); + int index = rsm_add_reg(&env->epilog, reg, flags); + rsm_set_value(&env->epilog, index, value); } void be_epilog_set_reg_value(beabi_helper_env_t *env, @@ -351,11 +409,11 @@ ir_node *be_epilog_create_barrier(beabi_helper_env_t *env, ir_node *block) ir_node *be_epilog_create_return(beabi_helper_env_t *env, dbg_info *dbgi, ir_node *block) { - int n_return_in = ARR_LEN(env->epilog.regs); + size_t n_return_in = ARR_LEN(env->epilog.regs); ir_node **in = env->epilog.value_map; int n_res = 1; /* TODO */ unsigned pop = 0; /* TODO */ - int i; + size_t i; ir_node *ret; assert(ARR_LEN(env->epilog.value_map) == n_return_in); @@ -366,7 +424,8 @@ ir_node *be_epilog_create_return(beabi_helper_env_t *env, dbg_info *dbgi, const reg_flag_t *regflag = &env->epilog.regs[i]; const arch_register_t *reg = regflag->reg; if (reg != NULL) { - be_set_constr_single_reg_in(ret, i, reg, 0); + be_set_constr_single_reg_in(ret, i, reg, + arch_register_req_type_none); } } @@ -379,7 +438,7 @@ ir_node *be_epilog_create_return(beabi_helper_env_t *env, dbg_info *dbgi, static void add_missing_keep_walker(ir_node *node, void *data) { int n_outs, i; - unsigned found_projs = 0; + unsigned *found_projs; const ir_edge_t *edge; ir_mode *mode = get_irn_mode(node); ir_node *last_keep; @@ -391,21 +450,22 @@ static void add_missing_keep_walker(ir_node *node, void *data) if (n_outs <= 0) return; - assert(n_outs < (int) sizeof(unsigned) * 8); + rbitset_alloca(found_projs, n_outs); foreach_out_edge(node, edge) { ir_node *succ = get_edge_src_irn(edge); + ir_mode *mode = get_irn_mode(succ); int pn; /* The node could be kept */ if (is_End(succ) || is_Anchor(succ)) continue; - if (get_irn_mode(succ) == mode_M) + if (mode == mode_M || mode == mode_X) continue; pn = get_Proj_proj(succ); assert(pn < n_outs); - found_projs |= 1 << pn; + rbitset_set(found_projs, pn); } @@ -417,7 +477,7 @@ static void add_missing_keep_walker(ir_node *node, void *data) const arch_register_req_t *req; const arch_register_class_t *cls; - if (found_projs & (1 << i)) { + if (rbitset_is_set(found_projs, i)) { continue; } @@ -446,16 +506,21 @@ void be_add_missing_keeps(ir_graph *irg) } - +/** + * Link the node into its block list as a new head. + */ static void collect_node(ir_node *node) { ir_node *block = get_nodes_block(node); - ir_node *old = get_irn_link(block); + ir_node *old = (ir_node*)get_irn_link(block); set_irn_link(node, old); set_irn_link(block, node); } +/** + * Post-walker: link all nodes that probably access the stack into lists of their block. + */ static void link_ops_in_block_walker(ir_node *node, void *data) { (void) data; @@ -476,11 +541,12 @@ static void link_ops_in_block_walker(ir_node *node, void *data) break; case iro_Builtin: if (get_Builtin_kind(node) == ir_bk_return_address) { - ir_node *param = get_Builtin_param(node, 0); - tarval *tv = get_Const_tarval(param); /* must be Const */ - long value = get_tarval_long(tv); + ir_node *param = get_Builtin_param(node, 0); + ir_tarval *tv = get_Const_tarval(param); /* must be Const */ + long value = get_tarval_long(tv); if (value > 0) { - /* we need esp for the climbframe algo */ + /* not the return address of the current function: + * we need the stack pointer for the frame climbing */ collect_node(node); } } @@ -490,7 +556,7 @@ static void link_ops_in_block_walker(ir_node *node, void *data) } } -static heights_t *heights; +static ir_heights_t *heights; /** * Check if a node is somehow data dependent on another one. @@ -506,17 +572,18 @@ static int dependent_on(const ir_node *n1, const ir_node *n2) return heights_reachable_in_block(heights, n1, n2); } +/** + * Classical qsort() comparison function behavior: + * + * 0 if both elements are equal, no node depend on the other + * +1 if first depends on second (first is greater) + * -1 if second depends on first (second is greater) +*/ static int cmp_call_dependency(const void *c1, const void *c2) { const ir_node *n1 = *(const ir_node **) c1; const ir_node *n2 = *(const ir_node **) c2; - /* - Classical qsort() comparison function behavior: - 0 if both elements are equal - 1 if second is "smaller" that first - -1 if first is "smaller" that second - */ if (dependent_on(n1, n2)) return 1; @@ -528,16 +595,20 @@ static int cmp_call_dependency(const void *c1, const void *c2) return get_irn_idx(n2) - get_irn_idx(n1); } +/** + * Block-walker: sorts dependencies and remember them into a phase + */ static void process_ops_in_block(ir_node *block, void *data) { - ir_phase *phase = data; + ir_phase *phase = (ir_phase*)data; unsigned n; unsigned n_nodes; ir_node *node; ir_node **nodes; n_nodes = 0; - for (node = get_irn_link(block); node != NULL; node = get_irn_link(node)) { + for (node = (ir_node*)get_irn_link(block); node != NULL; + node = (ir_node*)get_irn_link(node)) { ++n_nodes; } @@ -546,30 +617,37 @@ static void process_ops_in_block(ir_node *block, void *data) nodes = XMALLOCN(ir_node*, n_nodes); n = 0; - for (node = get_irn_link(block); node != NULL; node = get_irn_link(node)) { - nodes[n++] = node;; + for (node = (ir_node*)get_irn_link(block); node != NULL; + node = (ir_node*)get_irn_link(node)) { + nodes[n++] = node; } assert(n == n_nodes); /* order nodes according to their data dependencies */ qsort(nodes, n_nodes, sizeof(nodes[0]), cmp_call_dependency); + /* remember the calculated dependency into a phase */ for (n = n_nodes-1; n > 0; --n) { ir_node *node = nodes[n]; ir_node *pred = nodes[n-1]; phase_set_irn_data(phase, node, pred); } + xfree(nodes); } void be_collect_stacknodes(beabi_helper_env_t *env) { ir_graph *irg = env->irg; + + /* collect all potential^stack accessing nodes */ irg_walk_graph(irg, firm_clear_link, link_ops_in_block_walker, NULL); assert(env->stack_order == NULL); env->stack_order = new_phase(irg, phase_irn_init_default); + /* use heights to create a total order for those nodes: this order is stored + * in the created phase */ heights = heights_new(irg); irg_block_walk_graph(irg, NULL, process_ops_in_block, env->stack_order); heights_free(heights); @@ -577,5 +655,5 @@ void be_collect_stacknodes(beabi_helper_env_t *env) ir_node *be_get_stack_pred(const beabi_helper_env_t *env, const ir_node *node) { - return phase_get_irn_data(env->stack_order, node); + return (ir_node*)phase_get_irn_data(env->stack_order, node); }