From 52334aa699fe622b6ec65834417e83f39fa0a2bc Mon Sep 17 00:00:00 2001 From: Sebastian Hack Date: Fri, 24 Feb 2006 15:57:55 +0000 Subject: [PATCH] Separated dominance frontier calculations again --- ir/be/be_t.h | 1 - ir/be/beabi.c | 112 +++++++++++++++++++++++++++-------------- ir/be/beabi.h | 5 ++ ir/be/bearch.h | 21 ++++++++ ir/be/bechordal.c | 8 ++- ir/be/bechordal_main.c | 3 +- ir/be/beirgmod.c | 2 +- ir/be/bemain.c | 21 ++++---- ir/be/benode.c | 2 +- 9 files changed, 120 insertions(+), 55 deletions(-) diff --git a/ir/be/be_t.h b/ir/be/be_t.h index 3f3ab5f31..2180d0b3e 100644 --- a/ir/be/be_t.h +++ b/ir/be/be_t.h @@ -36,7 +36,6 @@ struct _be_main_env_t { struct _be_irg_t { ir_graph *irg; struct _be_main_env_t *main_env; - struct _dom_front_info_t *dom_front; struct _be_abi_irg_t *abi; struct _arch_code_generator_t *cg; }; diff --git a/ir/be/beabi.c b/ir/be/beabi.c index 9fff1b8af..8a72f6dd4 100644 --- a/ir/be/beabi.c +++ b/ir/be/beabi.c @@ -50,6 +50,8 @@ struct _be_abi_irg_t { unsigned omit_framepointer: 1; /**< If one, the frame(base-)pointer can be used as an ordinary register. */ + + firm_dbg_module_t *dbg; /**< The debugging module. */ }; static int cmp_call_arg(const void *a, const void *b, size_t n) @@ -380,15 +382,21 @@ static void modify_irg(be_abi_irg_t *env) int max_arg = 0; int reg_params_nr = 0; - int n_reg_param = 0; + ir_node *proj_sp = NULL; int i, j, n; - ir_node *proj_sp; ir_node *frame_pointer; ir_node *reg_params, *reg_params_bl; ir_node **args, **args_repl, **return_params; const ir_edge_t *edge; + const arch_register_t *reg; + + pset *callee_save = pset_new_ptr_default(); + pset *regs = pset_new_ptr_default(); + + firm_dbg_module_t *dbg = env->dbg; + DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg)); /* Find the maximum proj number of the argument tuple proj */ foreach_out_edge(arg_tuple, edge) { @@ -407,57 +415,69 @@ static void modify_irg(be_abi_irg_t *env) ir_node *irn = get_edge_src_irn(edge); int nr = get_Proj_proj(irn); args[nr] = irn; + DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn)); } /* Get the ABI constraints from the ISA */ arch_isa_get_call_abi(isa, method_type, call); - { - const arch_register_t **callee_save = env->birg->main_env->callee_save; - int n_reg_param = 0; + /* Count the register params and add them to the number of projs for the RegParams node */ + for(i = 0; i < n_params; ++i) { + be_abi_call_arg_t *arg = get_call_arg(call, 0, i); + if(arg->in_reg) { + assert(arg->reg != sp && "cannot use stack pointer as parameter register"); + pset_insert_ptr(regs, arg->reg); + DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name)); + } + } - /* Count the register params and add them to the number of projs for the RegParams node */ - for(i = 0; i < n_params; ++i) { - be_abi_call_arg_t *arg = get_call_arg(call, 0, i); - n_reg_param += arg->in_reg; + /* Collect all callee-save registers which are not used as parameter registers. */ + for(i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) { + const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i); + for(j = 0; j < cls->n_regs; ++j) { + const arch_register_t *reg = &cls->regs[j]; + if(arch_register_type_is(reg, callee_save) && !pset_find_ptr(regs, reg)) + pset_insert_ptr(callee_save, reg); } + } + + pset_insert_ptr(callee_save, sp); - reg_params_bl = get_irg_start_block(irg); - reg_params = be_new_RegParams(irg, reg_params_bl, n_reg_param); - reg_params_nr = 0; + reg_params_bl = get_irg_start_block(irg); + reg_params = be_new_RegParams(irg, reg_params_bl, pset_count(regs) + pset_count(callee_save)); + reg_params_nr = 0; - proj_sp = new_r_Proj(irg, reg_params_bl, reg_params, sp->reg_class->mode, reg_params_nr); - be_set_constr_single_reg(reg_params, -(reg_params_nr + 1), sp); + /* + * make proj nodes for the callee save registers. + * memorize them, since Return nodes get those as inputs. + */ + for(reg = pset_first(callee_save); reg; reg = pset_next(callee_save)) { + ir_node *irn = new_r_Proj(irg, reg_params_bl, reg_params, reg->reg_class->mode, reg_params_nr); + be_set_constr_single_reg(reg_params, -(reg_params_nr + 1), reg); + obstack_ptr_grow(&env->obst, irn); reg_params_nr++; - /* Make Projs for the callee save registers. */ - for(i = 0; callee_save[i] != NULL; ++i, ++reg_params_nr) { - const arch_register_t *reg = callee_save[i]; - ir_node *irn = new_r_Proj(irg, reg_params_bl, reg_params, reg->reg_class->mode, reg_params_nr); - be_set_constr_single_reg(reg_params, -(reg_params_nr + 1), reg); + DBG((dbg, LEVEL_2, "\tcallee save proj #%d -> reg %s\n", reg_params_nr - 1, reg->name)); - /* memorize the callee save proj since they will be arguments to the Return nodes. */ - obstack_ptr_grow(&env->obst, irn); - } - - obstack_ptr_grow(&env->obst, NULL); - return_params = obstack_finish(&env->obst); + /* detect the proj of the stack register and memorize it. */ + if(reg == sp) + proj_sp = irn; } + obstack_ptr_grow(&env->obst, NULL); + return_params = obstack_finish(&env->obst); + + assert(proj_sp != NULL && "There must be a Proj for the stack pointer"); - /* If we can omit the frame pointer, the stack pointer will become the frame pointer */ + /* This is the stack pointer add/sub which allocates the frame. remind it for later fixup. */ env->init_sp = be_new_IncSP(sp, irg, reg_params_bl, proj_sp, 0, be_stack_dir_along); - /* memorize this node for later fix up */ + + /* + * if we can omit the frame pointer (use it as an ordinary register), the stack pointer becomes + * the frame pointer, else we have to copy the current stack pointer to the frame pointer + */ frame_pointer = env->omit_framepointer ? env->init_sp : be_new_Copy(sp->reg_class, irg, reg_params_bl, proj_sp); set_irg_frame(irg, frame_pointer); - /* reroute the edges from the original argument projs to the RegParam ones. */ - for(i = 0; i < max_arg; ++i) { - if(args[i]) { - assert(args_repl != NULL); - edges_reroute(args[i], args_repl[i], irg); - } - } - /* Now, introduce stack param nodes for all parameters passed on the stack */ for(i = 0; i < max_arg; ++i) { ir_node *arg_proj = args[i]; @@ -478,7 +498,7 @@ static void modify_irg(be_abi_irg_t *env) /* when the (stack) parameter is primitive, we insert a StackParam node representing the load of that parameter */ - else if(is_Primitive_type(param_type)) { + else if(is_atomic_type(param_type)) { ir_mode *mode = get_type_mode(param_type); const arch_register_class_t *cls = arch_isa_get_reg_class_for_mode(isa, mode); // TODO: Correct offset computation! @@ -494,8 +514,19 @@ static void modify_irg(be_abi_irg_t *env) } } + /* reroute the edges from the original argument projs to the RegParam ones. */ + for(i = 0; i < max_arg; ++i) { + if(args[i] != NULL) { + assert(args_repl[i] != NULL); + edges_reroute(args[i], args_repl[i], irg); + } + } + obstack_free(&env->obst, args); be_abi_call_free(call); + + del_pset(callee_save); + del_pset(regs); } static void collect_alloca_walker(ir_node *irn, void *data) @@ -512,9 +543,10 @@ be_abi_irg_t *be_abi_introduce(be_irg_t *birg) int i; ir_node **stack_allocs; - env->birg = birg; - env->stack_ops = pset_new_ptr(32); env->omit_framepointer = 1; + env->birg = birg; + env->stack_ops = pset_new_ptr(32); + env->dbg = firm_dbg_register("firm.be.abi"); obstack_init(&env->obst); /* search for stack allocation nodes and record them */ @@ -538,10 +570,12 @@ be_abi_irg_t *be_abi_introduce(be_irg_t *birg) void be_abi_fix_stack(be_abi_irg_t *env) { pset *origs = pset_new_ptr_default(); + dom_front_info_t *df = be_compute_dominance_frontiers(env->birg->irg); pset_insert_ptr(origs, env->init_sp); - be_ssa_constr_sets(env->birg->dom_front, origs, env->stack_ops); + be_ssa_constr_sets(df, origs, env->stack_ops); del_pset(origs); + be_free_dominance_frontiers(df); } diff --git a/ir/be/beabi.h b/ir/be/beabi.h index d57e8424c..fedfd4f19 100644 --- a/ir/be/beabi.h +++ b/ir/be/beabi.h @@ -6,6 +6,7 @@ #ifndef _BEABI_H #define _BEABI_H +#include "be.h" #include "bearch.h" #include "beabi_t.h" @@ -20,4 +21,8 @@ void be_abi_call_param_stack(be_abi_call_t *call, int pos); void be_abi_call_param_reg(be_abi_call_t *call, int pos, const arch_register_t *reg); void be_abi_call_res_reg(be_abi_call_t *call, int pos, const arch_register_t *reg); +be_abi_irg_t *be_abi_introduce(be_irg_t *bi); +void be_abi_fix_stack(be_abi_irg_t *abi); +void be_abi_free(be_abi_irg_t *abi); + #endif diff --git a/ir/be/bearch.h b/ir/be/bearch.h index 1083dd7fc..9c11bb2e5 100644 --- a/ir/be/bearch.h +++ b/ir/be/bearch.h @@ -251,6 +251,27 @@ struct _arch_irn_ops_if_t { */ arch_irn_flags_t (*get_flags)(const void *self, const ir_node *irn); + /** + * Check, if a node modifies the stack pointer by a constant. + * @param self The this pointer. + * @param irn The node in question. + * @return The (constant) amount by which the stack pointer is modifies + * by this node. Return 0, if irn does not touch the stack pointer. + * -n if the node modifies the sp by n against the stack's growing + * direction and n if irn modifies the stack by n along the stack's + * growing direction. + */ + int (*modifies_sp)(const void *self, const ir_node *irn); + + /** + * Set a bias for the stack pointer. + * If the node in question uses the stack pointer for indexing, it must + * consider the value of bias additionally. + * @param self The this pointer. + * @param irn The node in question. + * @param bias The bias. + */ + void (*set_stack_bias)(const void *self, ir_node *irn, int bias); }; /** diff --git a/ir/be/bechordal.c b/ir/be/bechordal.c index 750cfd468..cbc90695c 100644 --- a/ir/be/bechordal.c +++ b/ir/be/bechordal.c @@ -162,7 +162,8 @@ static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head */ static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn) { - return arch_irn_has_reg_class(env->main_env->arch_env, irn, -1, env->cls); + // return arch_irn_has_reg_class(env->main_env->arch_env, irn, -1, env->cls); + return arch_irn_consider_in_reg_alloc(env->main_env->arch_env, env->cls, irn); } #define has_limited_constr(req, irn) \ @@ -469,6 +470,7 @@ static void pressure(ir_node *block, void *env_ptr) be_chordal_alloc_env_t *alloc_env = env_ptr; be_chordal_env_t *env = alloc_env->chordal_env; + const arch_env_t *arch_env = env->main_env->arch_env; bitset_t *live = alloc_env->live; firm_dbg_module_t *dbg = env->dbg; ir_node *irn; @@ -693,10 +695,12 @@ void be_ra_chordal_color(be_chordal_env_t *chordal_env) /* Handle register targeting constraints */ dom_tree_walk_irg(irg, constraints, NULL, &env); +#if 0 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) { snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name); dump_ir_block_graph_sched(chordal_env->irg, buf); } +#endif be_numbering(irg); env.live = bitset_malloc(get_graph_node_count(chordal_env->irg)); @@ -709,6 +713,7 @@ void be_ra_chordal_color(be_chordal_env_t *chordal_env) be_numbering_done(irg); +#if 0 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) { plotter_t *plotter; @@ -717,6 +722,7 @@ void be_ra_chordal_color(be_chordal_env_t *chordal_env) draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter); plotter_free(plotter); } +#endif free(env.live); free(env.colors); diff --git a/ir/be/bechordal_main.c b/ir/be/bechordal_main.c index e60772fb4..b83293da4 100644 --- a/ir/be/bechordal_main.c +++ b/ir/be/bechordal_main.c @@ -254,7 +254,7 @@ static void be_ra_chordal_main(const be_irg_t *bi) chordal_env.irg = irg; chordal_env.dbg = firm_dbg_register("firm.be.chordal"); chordal_env.main_env = main_env; - chordal_env.dom_front = bi->dom_front; + chordal_env.dom_front = be_compute_dominance_frontiers(irg); obstack_init(&chordal_env.obst); @@ -320,6 +320,7 @@ static void be_ra_chordal_main(const be_irg_t *bi) dump(BE_CH_DUMP_LOWER, irg, NULL, "-belower-after-ra", dump_ir_block_graph_sched); obstack_free(&chordal_env.obst, NULL); + be_free_dominance_frontiers(chordal_env.dom_front); } const be_ra_t be_ra_chordal_allocator = { diff --git a/ir/be/beirgmod.c b/ir/be/beirgmod.c index b9dfe5626..87feb55ae 100644 --- a/ir/be/beirgmod.c +++ b/ir/be/beirgmod.c @@ -386,7 +386,7 @@ void be_ssa_constr_ignore(dom_front_info_t *info, int n_origs, ir_node *orig_nod ir_node *bl = get_nodes_block(copy_nodes[i]); DBG((dbg, LEVEL_1, "\t%+F in block %+F\n", copy_nodes[i], bl)); pset_insert_ptr(copies, copy_nodes[i]); - pset_insert_ptr(copy_blocks, get_nodes_block(bl)); + pset_insert_ptr(copy_blocks, get_nodes_block(copy_nodes[i])); } /* diff --git a/ir/be/bemain.c b/ir/be/bemain.c index fa665d2c0..7f873ba79 100644 --- a/ir/be/bemain.c +++ b/ir/be/bemain.c @@ -53,10 +53,11 @@ #define DUMP_INITIAL (1 << 0) -#define DUMP_SCHED (1 << 1) -#define DUMP_PREPARED (1 << 2) -#define DUMP_RA (1 << 3) -#define DUMP_FINAL (1 << 4) +#define DUMP_ABI (1 << 1) +#define DUMP_SCHED (1 << 2) +#define DUMP_PREPARED (1 << 3) +#define DUMP_RA (1 << 4) +#define DUMP_FINAL (1 << 5) /* options visible for anyone */ be_options_t be_options = { @@ -68,14 +69,13 @@ be_options_t be_options = { }; /* dump flags */ -static unsigned dump_flags = DUMP_INITIAL | DUMP_SCHED | DUMP_PREPARED | DUMP_RA | DUMP_FINAL; +static unsigned dump_flags = 2 * DUMP_FINAL - 1; /* register allocator to use. */ static const be_ra_t *ra = &be_ra_chordal_allocator; /* back end instruction set architecture to use */ static const arch_isa_if_t *isa_if = &ia32_isa_if; - #ifdef WITH_LIBCORE static lc_opt_entry_t *be_grp_root = NULL; @@ -84,6 +84,7 @@ static lc_opt_entry_t *be_grp_root = NULL; static const lc_opt_enum_mask_items_t dump_items[] = { { "none", 0 }, { "initial", DUMP_INITIAL }, + { "abi", DUMP_ABI }, { "sched", DUMP_SCHED }, { "prepared", DUMP_PREPARED }, { "regalloc", DUMP_RA }, @@ -258,8 +259,6 @@ static void prepare_graph(be_irg_t *birg) /* check, if the dominance property is fulfilled. */ be_check_dominance(irg); - /* compute the dominance frontiers. */ - birg->dom_front = be_compute_dominance_frontiers(irg); } static void be_main_loop(FILE *file_handle) @@ -297,8 +296,10 @@ static void be_main_loop(FILE *file_handle) prepare_graph(&birg); /* implement the ABI conventions. */ - // birg.abi = be_abi_introduce(&birg); + birg.abi = be_abi_introduce(&birg); + dump(DUMP_ABI, irg, "-abi", dump_ir_block_graph); + /* generate code */ arch_code_generator_prepare_graph(birg.cg); /* @@ -332,8 +333,6 @@ static void be_main_loop(FILE *file_handle) arch_code_generator_done(birg.cg); dump(DUMP_FINAL, irg, "-end", dump_ir_block_graph_sched); - - be_free_dominance_frontiers(birg.dom_front); } be_done_env(&env); diff --git a/ir/be/benode.c b/ir/be/benode.c index e61ef5b61..5ee171556 100644 --- a/ir/be/benode.c +++ b/ir/be/benode.c @@ -808,7 +808,7 @@ pset *nodes_live_at(const arch_env_t *arch_env, const arch_register_class_t *cls for(x = pset_first(live); x; x = pset_next(live)) DBG((dbg, LEVEL_1, "\tlive: %+F\n", x)); - if(arch_irn_has_reg_class(arch_env, irn, -1, cls)) + if(arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) pset_remove_ptr(live, irn); for(i = 0, n = get_irn_arity(irn); i < n; ++i) { -- 2.20.1