From 9b24fe0ec0f4412c790ee4a7c6fc022fd28064a1 Mon Sep 17 00:00:00 2001 From: Sebastian Hack Date: Thu, 16 Jun 2005 11:52:00 +0000 Subject: [PATCH] Recent version :-) --- ir/be/bechordal_draw.c | 17 +--- ir/be/becopyheur.c | 5 +- ir/be/beirgmod.c | 82 ++++++++++++----- ir/be/beirgmod.h | 41 ++++++++- ir/be/belive.c | 204 ++++++++++++++++++----------------------- ir/be/belive_t.h | 122 ++++++++++++++---------- ir/be/bemain.c | 44 ++++++++- ir/be/benode.c | 10 +- ir/be/besched_t.h | 8 +- ir/be/bessadestr.c | 6 +- ir/be/beutil.c | 22 +++++ ir/be/beutil.h | 7 ++ 12 files changed, 353 insertions(+), 215 deletions(-) diff --git a/ir/be/bechordal_draw.c b/ir/be/bechordal_draw.c index 3ded8becd..1b31a561c 100644 --- a/ir/be/bechordal_draw.c +++ b/ir/be/bechordal_draw.c @@ -16,6 +16,7 @@ #include #include "pmap.h" +#include "pset.h" #include "irgwalk.h" #include "irprintf.h" @@ -305,7 +306,7 @@ static void draw_block(ir_node *bl, void *data) static const color_t black = { 0, 0, 0 }; const draw_chordal_env_t *env = data; - pset *live_in = get_live_in(bl); + pset *live_in = put_live_in(bl, pset_new_ptr_default()); ir_node *irn; border_t *b; struct list_head *head = get_block_border_head(env->chordal_env, bl); @@ -371,19 +372,7 @@ static void draw_block(ir_node *bl, void *data) } } -#if 0 - if(dom) { - struct block_dims *dom_dims = pmap_get(env->block_dims, dom); - rect_t line; - - line.x = dims->box.x; - line.y = dims->box.y; - line.w = dom_dims->box.x; - line.h = dom_dims->box.y; - - env->plotter->vtab->line(env->plotter, &line); - } -#endif + del_pset(live_in); } static void draw(draw_chordal_env_t *env, const rect_t *start_box) diff --git a/ir/be/becopyheur.c b/ir/be/becopyheur.c index 022fe854b..55092fea2 100644 --- a/ir/be/becopyheur.c +++ b/ir/be/becopyheur.c @@ -237,7 +237,7 @@ static ir_node *qnode_color_irn(const qnode_t *qn, ir_node *irn, int col, const /* first check for a conflicting node which is 'living in' the irns block */ { ir_node *n; - pset *live_ins = get_live_in(irn_bl); + pset *live_ins = put_live_in(irn_bl, pset_new_ptr_default()); for (n = pset_first(live_ins); n; n = pset_next(live_ins)) if (arch_irn_has_reg_class(arch_env, n, arch_pos_make_out(0), cls) && n != trigger && qnode_get_new_color(qn, n) == col @@ -247,7 +247,8 @@ static ir_node *qnode_color_irn(const qnode_t *qn, ir_node *irn, int col, const obstack_ptr_grow(&confl_ob, n); pset_break(live_ins); break; - } + } + del_pset(live_ins); } /* setup the queue of blocks. */ diff --git a/ir/be/beirgmod.c b/ir/be/beirgmod.c index 85f233f28..03d760be6 100644 --- a/ir/be/beirgmod.c +++ b/ir/be/beirgmod.c @@ -9,6 +9,7 @@ #include "pset.h" #include "pmap.h" #include "util.h" +#include "debug.h" #include "irflag_t.h" #include "ircons_t.h" @@ -25,6 +26,8 @@ #include "beirgmod.h" +#define DBG_MODULE firm_dbg_register("firm.be.irgmod") + struct _dom_front_info_t { pmap *df_map; }; @@ -33,8 +36,16 @@ static void compute_df_local(ir_node *bl, void *data) { pmap *df_map = ((dom_front_info_t *) data)->df_map; ir_node *idom = get_Block_idom(bl); + pset *df = pmap_get(df_map, bl); int i, n; + /* + * Create a new dom frot set for this node, + * if none exists. + */ + if(!df) + pmap_insert(df_map, bl, pset_new_ptr(16)); + for(i = 0, n = get_irn_arity(bl); i < n; ++i) { /* The predecessor block */ @@ -42,16 +53,12 @@ static void compute_df_local(ir_node *bl, void *data) /* The dominance frontier set of the predecessor. */ pset *df = pmap_get(df_map, pred); + if(!df) { + df = pset_new_ptr(16); + pmap_insert(df_map, pred, df); + } - /* - * Create the dominance frontier set of the predecessor - * if it didn't exist. - */ - if(!df) { - df = pset_new_ptr(16); - pmap_insert(df_map, pred, df); - } - + assert(df && "dom front set must have been created for this node"); if(pred != idom && bl) pset_insert_ptr(df, bl); @@ -67,7 +74,7 @@ static void compute_df_up(ir_node *bl, void *data) ir_node *w; pset *df = pmap_get(df_map, y); - for(w = pset_first(df); df; w = pset_next(df)) + for(w = pset_first(df); w; w = pset_next(df)) if(!block_dominates(bl, w) || bl == w) pset_insert_ptr(df, w); } @@ -79,8 +86,11 @@ dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg) info->df_map = pmap_create(); - /* Perhaps both can we interwined */ - dom_tree_walk_irg(irg, compute_df_local, NULL, info); + /* + * This must be called as a post walker, since the dom front sets + * of all predecessors must be created when a block is reached. + */ + dom_tree_walk_irg(irg, NULL, compute_df_local, info); dom_tree_walk_irg(irg, NULL, compute_df_up, info); return info; } @@ -132,6 +142,7 @@ static void place_phi_functions(ir_node *orig, pset *copies, pset *phi_blocks = pset_new_ptr(8); ir_node **ins = NULL; void *it; + firm_dbg_module_t *dbg = DBG_MODULE; /* * Allocate an array for all blocks where the copies and the original @@ -151,8 +162,10 @@ static void place_phi_functions(ir_node *orig, pset *copies, for(it = pset_first(copies), i = 1; it; it = pset_next(copies)) { ir_node *copy_block = get_nodes_block(it); - assert(block_dominates(orig_block, copy_block) - && "The block of the copy must be dominated by the block of the value"); + if(!block_dominates(orig_block, copy_block)) { + assert(block_dominates(orig_block, copy_block) + && "The block of the copy must be dominated by the block of the value"); + } pdeq_putr(worklist, it); orig_blocks[i++] = copy_block; @@ -177,10 +190,11 @@ static void place_phi_functions(ir_node *orig, pset *copies, */ ins = realloc(ins, n_preds * sizeof(ins[0])); for(i = 0; i < n_preds; ++i) - ins[0] = orig; + ins[0] = new_Unknown(mode); /* Insert phi node */ phi = new_r_Phi(irg, bl, n_preds, ins, mode); + DBG((dbg, LEVEL_2, " inserting phi in block %+F\n", bl)); /* * The phi node itself is also a copy of the original @@ -245,6 +259,7 @@ static void place_phi_functions(ir_node *orig, pset *copies, static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blocks) { ir_node *curr_bl; + ir_node *start_irn; curr_bl = get_nodes_block(usage); @@ -259,6 +274,7 @@ static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blo * Traverse the dominance tree upwards from the * predecessor block of the usage. */ + start_irn = usage; while(curr_bl != NULL) { /* @@ -269,18 +285,18 @@ static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blo ir_node *irn; /* Look at each instruction from last to first. */ - sched_foreach_reverse(curr_bl, irn) { + for(irn = start_irn; !is_Block(irn); irn = sched_prev(irn)) { /* Take the first copy we find. */ if(pset_find_ptr(copies, irn)) return irn; } - - assert(0 && "We must have encountered a copy"); } /* If were not done yet, look in the immediate dominator */ curr_bl = get_Block_idom(curr_bl); + if(curr_bl) + start_irn = sched_last(curr_bl); } return NULL; @@ -288,10 +304,15 @@ static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blo static void fix_usages(ir_node *orig, pset *copies, pset *copy_blocks) { - int i; + int i = 0; int n_outs = 0; const ir_edge_t *edge; - const ir_edge_t **outs; + firm_dbg_module_t *dbg = DBG_MODULE; + + struct { + ir_node *irn; + int pos; + } *outs; /* Count the number of outs. */ foreach_out_edge(orig, edge) @@ -302,20 +323,26 @@ static void fix_usages(ir_node *orig, pset *copies, pset *copy_blocks) * This is neccessary, since the outs would be modified while * interating on them what could bring the outs module in trouble. */ + DBG((dbg, LEVEL_2, " Users of %+F\n", orig)); outs = malloc(n_outs * sizeof(outs[0])); - foreach_out_edge(orig, edge) - outs[i++] = edge; + foreach_out_edge(orig, edge) { + outs[i].irn = get_edge_src_irn(edge); + outs[i].pos = get_edge_src_pos(edge); + DBG((dbg, LEVEL_2, " %+F(%d)\n", outs[i].irn, outs[i].pos)); + i += 1; + } /* * Search the valid def for each out and set it. */ for(i = 0; i < n_outs; ++i) { ir_node *def; - ir_node *irn = get_edge_src_irn(outs[i]); - int pos = get_edge_src_pos(outs[i]); + ir_node *irn = outs[i].irn; + int pos = outs[i].pos; def = search_def(irn, pos, copies, copy_blocks); - set_irn_n(irn, pos, def); + if(def != NULL) + set_irn_n(irn, pos, def); } free(outs); @@ -327,9 +354,14 @@ void be_introduce_copies(dom_front_info_t *info, ir_node *orig, int n, ir_node * pset *copy_blocks = pset_new_ptr(2 * n); int save_optimize = get_optimize(); int i; + firm_dbg_module_t *dbg = DBG_MODULE; + firm_dbg_set_mask(dbg, -1); + DBG((dbg, LEVEL_1, "Introducing following copies of %+F\n", orig)); /* Fill the sets. */ for(i = 0; i < n; ++i) { + DBG((dbg, LEVEL_1, + " %+F in block %+F\n", copy_nodes[i], get_nodes_block(copy_nodes[i]))); pset_insert_ptr(copies, copy_nodes[i]); pset_insert_ptr(copy_blocks, get_nodes_block(copy_nodes[i])); } diff --git a/ir/be/beirgmod.h b/ir/be/beirgmod.h index 6d5240c4e..15b7de7bf 100644 --- a/ir/be/beirgmod.h +++ b/ir/be/beirgmod.h @@ -10,13 +10,52 @@ #ifndef _BEIRGMOD_H #define _BEIRGMOD_H +/* + * Forward type declaration. + */ typedef struct _dom_front_info_t dom_front_info_t; +/** + * Compute the dominance frontiers for a given graph. + * @param irg The graphs. + * @return A pointer to the dominance frontier information. + */ dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg); + +/** + * Get the dominance frontier of a block. + * @param info A pointer to the dominance frontier information. + * @param block The block whose dominance frontier you want. + * @return A set containing the all blocks in the dominance frontier of @p block. + */ pset *be_get_dominance_frontier(dom_front_info_t *info, ir_node *block); + +/** + * Free some dominance frontier information. + * @param info Some dominance frontier information. + */ void be_free_dominance_frontiers(dom_front_info_t *info); +/** + * Introduce several copies for one node. + * + * A copy in this context means, that you want to introduce several new + * abstract values (in Firm: nodes) for which you know, that they + * represent the same concrete value. This is the case if you + * - copy + * - spill and reload + * - rematerialize + * a value. + * + * This function reroutes all uses of the original value to the copies in the + * corresponding dominance subtrees and creates Phi functions if neccessary. + * + * @param info Dominance frontier information. + * @param orig The node for which you want to introduce copies. + * @param n The number of copies ypu introduce. + * @param copies An array of nodes which are copies of @p orig. + */ void be_introduce_copies(dom_front_info_t *info, ir_node *orig, - int n, ir_node *copy_nodes[]); + int n, ir_node *copies[]); #endif diff --git a/ir/be/belive.c b/ir/be/belive.c index bf9626610..ed6cd7ff3 100644 --- a/ir/be/belive.c +++ b/ir/be/belive.c @@ -15,36 +15,31 @@ #include "beutil.h" #include "belive_t.h" -#define DEFAULT_LIVE_SET_SIZE 8 - FIRM_IMPL2(is_live_in, int, const ir_node *, const ir_node *) FIRM_IMPL2(is_live_out, int, const ir_node *, const ir_node *) FIRM_IMPL2(is_live_end, int, const ir_node *, const ir_node *) /** The offset of the liveness information in a firm node. */ -size_t live_irn_data_offset = 0; +size_t live_irg_data_offset = 0; void be_liveness_init(void) { - live_irn_data_offset = register_additional_node_data(sizeof(live_info_t)); + live_irg_data_offset = register_additional_graph_data(sizeof(irn_live_t)); } static INLINE void mark_live_in(ir_node *block, const ir_node *irn) { - block_live_info_t *info = get_block_live_info(block); - pset_insert_ptr(info->in, irn); + _get_or_set_live(block, irn, live_state_in); } static INLINE void mark_live_out(ir_node *block, const ir_node *irn) { - block_live_info_t *info = get_block_live_info(block); - pset_insert_ptr(info->out, irn); + _get_or_set_live(block, irn, live_state_out); } static INLINE void mark_live_end(ir_node *block, const ir_node *irn) { - block_live_info_t *info = get_block_live_info(block); - pset_insert_ptr(info->end, irn); + _get_or_set_live(block, irn, live_state_end); } /** @@ -58,30 +53,30 @@ static INLINE void mark_live_end(ir_node *block, const ir_node *irn) * of the block. */ static void live_end_at_block(ir_node *def, ir_node *block, - pset *visited, int is_true_out) + pset *visited, int is_true_out) { - mark_live_end(block, def); - if(is_true_out) - mark_live_out(block, def); + mark_live_end(block, def); + if(is_true_out) + mark_live_out(block, def); - if(!pset_find_ptr(visited, block)) { + if(!pset_find_ptr(visited, block)) { - pset_insert_ptr(visited, block); + pset_insert_ptr(visited, block); - /* - * If this block is not the definition block, we have to go up - * further. - */ - if(get_nodes_block(def) != block) { - int i, n; + /* + * If this block is not the definition block, we have to go up + * further. + */ + if(get_nodes_block(def) != block) { + int i, n; - mark_live_in(block, def); + mark_live_in(block, def); - for(i = 0, n = get_irn_arity(block); i < n; ++i) - live_end_at_block(def, get_nodes_block(get_irn_n(block, i)), visited, 1); - } + for(i = 0, n = get_irn_arity(block); i < n; ++i) + live_end_at_block(def, get_nodes_block(get_irn_n(block, i)), visited, 1); + } - } + } } /** @@ -93,98 +88,81 @@ static void live_end_at_block(ir_node *def, ir_node *block, */ static void liveness_for_node(ir_node *irn, void *env) { - int i, n; - ir_node *def_block; - pset *visited; - - /* Don't compute liveness information for non-data nodes. */ - if(!is_data_node(irn)) - return; - - visited = pset_new_ptr(512); - def_block = get_nodes_block(irn); - - /* Go over all uses of the value */ - for(i = 0, n = get_irn_n_outs(irn); i < n; ++i) { - ir_node *use = get_irn_out(irn, i); - ir_node *use_block; - - /* - * If the usage is no data node, skip this use, since it does not - * affect the liveness of the node. - */ - if(!is_data_node(use)) - continue; - - /* Get the block where the usage is in. */ - use_block = get_nodes_block(use); - - /* - * If the use is a phi function, determine the corresponding block - * through which the value reaches the phi function and mark the - * value as live out of that block. - */ - if(is_Phi(use)) { - int i, n; - - /* Mark the node as a phi operand, since a use by a phi was found. */ - get_node_live_info(irn)->is_phi_op = 1; - - for(i = 0, n = get_irn_arity(use); i < n; ++i) { - if(get_irn_n(use, i) == irn) { - ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i)); - live_end_at_block(irn, pred_block, visited, 0); - } - } - } - - /* - * Else, the value is live in at this block. Mark it and call live - * out on the predecessors. - */ - else if(def_block != use_block) { - int i, n; - - mark_live_in(use_block, irn); - - for(i = 0, n = get_irn_arity(use_block); i < n; ++i) { - ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i)); - live_end_at_block(irn, pred_block, visited, 1); - } - } - } - - del_pset(visited); + int i, n; + ir_node *def_block; + pset *visited; + + /* Don't compute liveness information for non-data nodes. */ + if(!is_data_node(irn)) + return; + + visited = pset_new_ptr(512); + def_block = get_nodes_block(irn); + + /* Go over all uses of the value */ + for(i = 0, n = get_irn_n_outs(irn); i < n; ++i) { + ir_node *use = get_irn_out(irn, i); + ir_node *use_block; + + /* + * If the usage is no data node, skip this use, since it does not + * affect the liveness of the node. + */ + if(!is_data_node(use)) + continue; + + /* Get the block where the usage is in. */ + use_block = get_nodes_block(use); + + /* + * If the use is a phi function, determine the corresponding block + * through which the value reaches the phi function and mark the + * value as live out of that block. + */ + if(is_Phi(use)) { + int i, n; + + /* Mark the node as a phi operand, since a use by a phi was found. */ + /* get_node_live_info(irn)->is_phi_op = 1; */ + + for(i = 0, n = get_irn_arity(use); i < n; ++i) { + if(get_irn_n(use, i) == irn) { + ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i)); + live_end_at_block(irn, pred_block, visited, 0); + } + } + } + + /* + * Else, the value is live in at this block. Mark it and call live + * out on the predecessors. + */ + else if(def_block != use_block) { + int i, n; + + mark_live_in(use_block, irn); + + for(i = 0, n = get_irn_arity(use_block); i < n; ++i) { + ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i)); + live_end_at_block(irn, pred_block, visited, 1); + } + } + } + + del_pset(visited); } -static void create_sets(ir_node *block, void *env) +static int cmp_irn_live(const void *a, const void *b, size_t size) { - block_live_info_t *info = get_block_live_info(block); - info->in = pset_new_ptr(DEFAULT_LIVE_SET_SIZE); - info->out = pset_new_ptr(DEFAULT_LIVE_SET_SIZE); - info->end = pset_new_ptr(DEFAULT_LIVE_SET_SIZE); -} + const irn_live_t *p = a; + const irn_live_t *q = b; - -static void liveness_dump(ir_node *block, void *env) -{ - FILE *f = env; - block_live_info_t *info = get_block_live_info(block); - - assert(is_Block(block) && "Need a block here"); - ir_fprintf(f, "liveness at block %n\n", block); - ir_fprintf(f, "\tlive in: %*n\n", pset_iterator, info->in); - ir_fprintf(f, "\tlive out: %*n\n", pset_iterator, info->out); - ir_fprintf(f, "\tlive end: %*n\n", pset_iterator, info->end); -} - -void be_liveness_dump(FILE *f, ir_graph *irg) -{ - irg_block_walk_graph(irg, liveness_dump, NULL, f); + return !(p->block == q->block && p->irn == q->irn); } void be_liveness(ir_graph *irg) { - irg_block_walk_graph(irg, create_sets, NULL, NULL); - irg_walk_graph(irg, liveness_for_node, NULL, NULL); + irg_live_info_t *live_info = get_irg_live_info(irg); + live_info->live = new_set(cmp_irn_live, 8192); + irg_walk_graph(irg, liveness_for_node, NULL, NULL); } diff --git a/ir/be/belive_t.h b/ir/be/belive_t.h index d46af6d7d..f80851151 100644 --- a/ir/be/belive_t.h +++ b/ir/be/belive_t.h @@ -9,90 +9,118 @@ #include "config.h" +#include "irgraph_t.h" + #include "belive.h" #include "pset.h" +#include "set.h" +#include "list.h" +#include "hashptr.h" -typedef struct _block_live_info_t { - pset *in; /**< The set of all values live in at that block. */ - pset *out; /**< The set of all values live out. */ - pset *end; /**< The set of all values live at the end - of the block (contains all live out). */ -} block_live_info_t; +typedef enum _live_state_t { + live_state_in = 1, + live_state_end = 2, + live_state_out = 6, + live_state_block = 8, +} live_state_t; -typedef struct _node_live_info_t { - int is_phi_op; /**< Marks the node as a phi operand. */ -} node_live_info_t; +typedef struct _irn_live_t { + const ir_node *block; + const ir_node *irn; + unsigned state; + struct _irn_live_t *next; +} irn_live_t; -typedef struct _live_info_t { - union { - block_live_info_t block; - node_live_info_t node; - } v; -} live_info_t; +typedef struct _irg_live_info_t { + set *live; +} irg_live_info_t; -extern size_t live_irn_data_offset; +extern size_t live_irg_data_offset; -#define get_irn_live_info(irn) get_irn_data(irn, live_info_t, live_irn_data_offset) -#define get_live_info_irn(inf) get_irn_data_base(inf, live_irn_data_offset) +#define get_irg_live_info(irg) (get_irg_data(irg, irg_live_info_t, live_irg_data_offset)) -#define get_block_live_info(irn) (&(get_irn_live_info(irn)->v.block)) -#define get_node_live_info(irn) (&(get_irn_live_info(irn)->v.node)) +#define HASH_PTR_PAIR(x,y) (HASH_PTR(x) + 37 * HASH_PTR(y)) -static INLINE int _is_phi_operand(const ir_node *irn) +static INLINE irn_live_t *_get_or_set_live(const ir_node *block, const ir_node *irn, int state) { - assert(!is_Block(irn) && "No block node allowed here"); - return get_node_live_info(irn)->is_phi_op; + irg_live_info_t *live_info = get_irg_live_info(get_irn_irg(block)); + irn_live_t *live, templ; + + templ.block = block; + templ.irn = irn; + templ.state = -1; + templ.next = NULL; + + live = set_insert(live_info->live, &templ, sizeof(templ), HASH_PTR_PAIR(block, irn)); + if(live->state == -1) { + + if(!is_Block(irn)) { + irn_live_t *bl_live = _get_or_set_live(block, block, live_state_block); + live->next = bl_live->next; + bl_live->next = live; + } + + live->state = state; + } + + live->state |= state; + + return live; } static INLINE int _is_live_in(const ir_node *block, const ir_node *irn) { - block_live_info_t *info = get_block_live_info(block); - - assert(is_Block(block) && "Need a block here"); - return pset_find_ptr(info->in, irn) != NULL; + return (_get_or_set_live(block, irn, 0)->state & live_state_in) != 0; } static INLINE int _is_live_out(const ir_node *block, const ir_node *irn) { - block_live_info_t *info = get_block_live_info(block); - - assert(is_Block(block) && "Need a block here"); - return pset_find_ptr(info->out, irn) != NULL; + return (_get_or_set_live(block, irn, 0)->state & live_state_out) != 0; } static INLINE int _is_live_end(const ir_node *block, const ir_node *irn) { - block_live_info_t *info = get_block_live_info(block); + return (_get_or_set_live(block, irn, 0)->state & live_state_end) != 0; +} + +#define live_foreach(block, live_info) \ + for(live_info = _get_or_set_live(block, block, 0)->next; live_info; live_info = live_info->next) - assert(is_Block(block) && "Need a block here"); - return pset_find_ptr(info->end, irn) != NULL; +static INLINE void _put_live(const ir_node *block, int state, pset *s) +{ + irn_live_t *live; + + live_foreach(block, live) { + if(live->state & state) + pset_insert_ptr(s, live->irn); + } } -static INLINE pset *_get_live_in(const ir_node *block) +static INLINE pset *_put_live_in(const ir_node *block, pset *s) { - assert(is_Block(block) && "Need a block here"); - return get_block_live_info(block)->in; + _put_live(block, live_state_in, s); + return s; } -static INLINE pset *_get_live_out(const ir_node *block) +static INLINE pset *_put_live_out(const ir_node *block, pset *s) { - assert(is_Block(block) && "Need a block here"); - return get_block_live_info(block)->out; + _put_live(block, live_state_out, s); + return s; } -static INLINE pset *_get_live_end(const ir_node *block) +static INLINE pset *_put_live_end(const ir_node *block, pset *s) { - assert(is_Block(block) && "Need a block here"); - return get_block_live_info(block)->end; + _put_live(block, live_state_end, s); + return s; } -#define is_phi_operand(irn) _is_phi_operand(irn) + #define is_live_in(bl,irn) _is_live_in(bl, irn) #define is_live_out(bl,irn) _is_live_out(bl, irn) #define is_live_end(bl,irn) _is_live_end(bl, irn) -#define get_live_in(bl) _get_live_in(bl) -#define get_live_out(bl) _get_live_out(bl) -#define get_live_end(bl) _get_live_end(bl) +#define put_live_in(bl,s) _put_live_in(bl, s) +#define put_live_out(bl,s) _put_live_out(bl, s) +#define put_live_end(bl,s) _put_live_end(bl, s) /** * Initialize the liveness module. diff --git a/ir/be/bemain.c b/ir/be/bemain.c index a0971d9d3..298a48934 100644 --- a/ir/be/bemain.c +++ b/ir/be/bemain.c @@ -17,6 +17,8 @@ #include "irgraph.h" #include "irdump.h" #include "phiclass.h" +#include "irdom_t.h" +#include "iredges_t.h" #include "be_t.h" #include "bechordal_t.h" @@ -32,6 +34,7 @@ #include "bessadestr.h" #include "bearch_firm.h" #include "benode_t.h" +#include "beirgmod.h" #include "beasm_dump_globals.h" #include "beasm_asm_gnu.h" @@ -72,7 +75,8 @@ static be_main_env_t *be_init_env(be_main_env_t *env) return env; } -be_main_session_env_t *be_init_session_env(be_main_session_env_t *env, +static be_main_session_env_t * +be_init_session_env(be_main_session_env_t *env, be_main_env_t *main_env, ir_graph *irg) { env->main_env = main_env; @@ -81,6 +85,32 @@ be_main_session_env_t *be_init_session_env(be_main_session_env_t *env, return env; } +static void prepare_graph(be_main_session_env_t *s) +{ + /* + * Duplicate consts in each block + * (This is just for the firm dummy backend) + */ + // localize_consts(s->irg); + + /* Remove critical edges */ + remove_critical_cf_edges(s->irg); + + /* Compute the dominance information. */ + free_dom_and_peace(s->irg); + compute_doms(s->irg); + + /* Compute the dominance frontiers */ + s->dom_front = be_compute_dominance_frontiers(s->irg); + + /* Ensure, that the ir_edges are computed. */ + edges_assure(s->irg); + + dump_dominator_information(true); + dump_ir_block_graph(s->irg, "-prepared"); + dump_dominator_information(false); +} + static void be_main_loop(void) { int i, n; @@ -96,11 +126,12 @@ static void be_main_loop(void) ir_graph *irg = get_irp_irg(i); be_main_session_env_t session; + /* Init the session. */ be_init_session_env(&session, &env, irg); - remove_critical_cf_edges(irg); + /* Compute some analyses and prepare the graph for backend use. */ + prepare_graph(&session); - localize_consts(irg); #ifdef DUMP_LOCALIZED dump_consts_local(0); dump_ir_block_graph(irg, "-local-const"); @@ -110,17 +141,22 @@ static void be_main_loop(void) /* Schedule the graphs. */ list_sched(irg, trivial_selector); + /* Verify the schedule */ + sched_verify_irg(irg); + /* Liveness analysis */ be_liveness(irg); + dump_ir_block_graph_sched(irg, "-sched"); copystat_reset(); copystat_collect_irg(irg, env.arch_env); + /* Perform the following for each register class. */ for(j = 0, m = isa->get_n_reg_class(); j < m; ++j) { be_chordal_env_t *chordal_env; const arch_register_class_t *cls = isa->get_reg_class(j); - chordal_env = be_ra_chordal(irg, env.arch_env, cls); + chordal_env = be_ra_chordal(irg, env.arch_env, cls); #ifdef DUMP_ALLOCATED dump_allocated_irg(env.arch_env, irg, ""); diff --git a/ir/be/benode.c b/ir/be/benode.c index 5adbad837..84d69c0c6 100644 --- a/ir/be/benode.c +++ b/ir/be/benode.c @@ -325,14 +325,11 @@ ir_node *insert_Perm_after(const be_main_session_env_t *env, const arch_env_t *arch_env = env->main_env->arch_env; ir_node *bl = is_Block(pos) ? pos : get_nodes_block(pos); ir_graph *irg = get_irn_irg(bl); - pset *live_end = get_live_end(bl); - pset *live = pset_new_ptr_default(); + pset *live = put_live_end(bl, pset_new_ptr_default()); ir_node *curr, *irn, *perm, **nodes; int i, n; - /* put all live ends in the live set. */ - for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) - pset_insert_ptr(live, irn); + ir_printf("Insert Perm after: %+F\n", pos); sched_foreach_reverse(bl, irn) { @@ -356,10 +353,11 @@ ir_node *insert_Perm_after(const be_main_session_env_t *env, for(irn = pset_first(live), i = 0; irn; irn = pset_next(live), i++) nodes[i] = irn; - curr = perm = new_Perm(env->main_env->node_factory, cls, irg, bl, n, nodes); + perm = new_Perm(env->main_env->node_factory, cls, irg, bl, n, nodes); sched_add_after(pos, perm); free(nodes); + curr = perm; for(i = 0; i < n; ++i) { ir_node *copies[1]; ir_node *perm_op = get_irn_n(perm, i); diff --git a/ir/be/besched_t.h b/ir/be/besched_t.h index 64167ea35..5f9bbb42e 100644 --- a/ir/be/besched_t.h +++ b/ir/be/besched_t.h @@ -176,8 +176,10 @@ static INLINE void _sched_set_time_stamp(ir_node *irn) */ static INLINE ir_node *_sched_add_before(ir_node *before, ir_node *irn) { - list_add_tail(&get_irn_sched_info(irn)->list, &get_irn_sched_info(before)->list); + sched_info_t *info = get_irn_sched_info(irn); + list_add_tail(&info->list, &get_irn_sched_info(before)->list); _sched_set_time_stamp(irn); + info->scheduled = 1; return irn; } @@ -189,8 +191,10 @@ static INLINE ir_node *_sched_add_before(ir_node *before, ir_node *irn) */ static INLINE ir_node *_sched_add_after(ir_node *after, ir_node *irn) { - list_add(&get_irn_sched_info(irn)->list, &get_irn_sched_info(after)->list); + sched_info_t *info = get_irn_sched_info(irn); + list_add(&info->list, &get_irn_sched_info(after)->list); _sched_set_time_stamp(irn); + info->scheduled = 1; return irn; } diff --git a/ir/be/bessadestr.c b/ir/be/bessadestr.c index b4b1d44a9..26e70f73d 100644 --- a/ir/be/bessadestr.c +++ b/ir/be/bessadestr.c @@ -15,7 +15,9 @@ #include "pmap.h" #include "irnode.h" #include "iredges_t.h" +#include "irdump.h" #include "be_t.h" +#include "beutil.h" #include "bechordal_t.h" #include "bearch.h" #include "benode_t.h" @@ -81,6 +83,7 @@ static void adjust_arguments(be_main_session_env_t *session, be_chordal_env_t *c ir_node *arg, *perm, *proj; const arch_register_t *phi_reg, *arg_reg, *proj_reg; const ir_edge_t *edge; + ir_node *phi_block = get_nodes_block(phi); assert(is_Phi(phi) && "Can only handle phi-destruction :)"); @@ -91,7 +94,7 @@ static void adjust_arguments(be_main_session_env_t *session, be_chordal_env_t *c arg_reg = get_reg(arg); /* if registers don't match ...*/ if (phi_reg != arg_reg) { - perm = get_perm(session, chordal_env, get_nodes_block(arg)); + perm = get_perm(session, chordal_env, get_nodes_block(get_irn_n(phi_block, i))); /* adjust assigned registers for the projs */ foreach_out_edge(perm, edge) { proj = get_edge_src_irn(edge); @@ -150,6 +153,7 @@ void be_ssa_destruction(be_main_session_env_t *session, be_chordal_env_t *chorda adjust_arguments(session, chordal_env, curr->irn); } } + dump_ir_block_graph_sched(session->irg, "-ssa-destr"); del_set(b2p); checker(chordal_env); } diff --git a/ir/be/beutil.c b/ir/be/beutil.c index 4b75cdc39..53c868c45 100644 --- a/ir/be/beutil.c +++ b/ir/be/beutil.c @@ -6,6 +6,7 @@ #include "irgraph.h" #include "irgwalk.h" +#include "irdump_t.h" #include "ircons.h" #include "iropt.h" #include "irgopt.h" @@ -111,3 +112,24 @@ void localize_consts(ir_graph *irg) irg_walk_graph(irg, localize_const_walker, NULL, NULL); dead_node_elimination(irg); } + +static int sched_edge_hook(FILE *F, ir_node *irn) +{ + if(sched_is_scheduled(irn) && sched_has_prev(irn)) { + ir_node *prev = sched_prev(irn); + fprintf(F, "edge:{sourcename:\""); + PRINT_NODEID(irn); + fprintf(F, "\" targetname:\""); + PRINT_NODEID(prev); + fprintf(F, "\" color:magenta}\n"); + } + return 1; +} + +void dump_ir_block_graph_sched(ir_graph *irg, const char *suffix) { + DUMP_NODE_EDGE_FUNC old = get_dump_node_edge_hook(); + + set_dump_node_edge_hook(sched_edge_hook); + dump_ir_block_graph(irg, suffix); + set_dump_node_edge_hook(old); +} diff --git a/ir/be/beutil.h b/ir/be/beutil.h index 7420f4400..dcb18b1a6 100644 --- a/ir/be/beutil.h +++ b/ir/be/beutil.h @@ -69,4 +69,11 @@ static INLINE FILE *ffopen(const char *base, const char *ext, const char *mode) return out; } +/** + * Dump a graph with schedule edges. + * @param irg The graph. + * @param suffix A suffix to its file name. + */ +void dump_ir_block_graph_sched(ir_graph *irg, const char *suffix); + #endif -- 2.20.1