From 3fc3581455283da528a83ae84bce579992182c55 Mon Sep 17 00:00:00 2001 From: Sebastian Hack Date: Fri, 24 Jun 2005 11:11:47 +0000 Subject: [PATCH] Added block successor edges to the iredges module. [r6120] --- ir/ir/irargs.c | 31 ++++++++++++++++++ ir/ir/iredges.c | 82 ++++++++++++++++++++++++++++++++++++++--------- ir/ir/iredges.h | 35 +++++++++++++++++++- ir/ir/iredges_t.h | 70 +++++++++++++++++++++++++++++++++++++++- ir/ir/irnode.c | 3 ++ ir/ir/irnode_t.h | 2 ++ ir/ir/irop.c | 9 ++++++ 7 files changed, 215 insertions(+), 17 deletions(-) diff --git a/ir/ir/irargs.c b/ir/ir/irargs.c index dc559a9a1..0e01f79be 100644 --- a/ir/ir/irargs.c +++ b/ir/ir/irargs.c @@ -14,6 +14,8 @@ # include "config.h" #endif +#include "bitset.h" + #include #include @@ -35,6 +37,33 @@ static int firm_get_arg_type_int(const arg_occ_t *occ) { return arg_type_int; } + +static int bitset_get_arg_type(const arg_occ_t *occ) { + return arg_type_ptr; +} + +static int bitset_emit(appendable_t *app, const arg_occ_t *occ, const arg_value_t *arg) +{ + int res = 2; + bitset_t *b = arg->v_ptr; + bitset_pos_t p; + char buf[32]; + const char *prefix = ""; + + arg_append(app, occ, "[", 1); + for(p = bitset_next_set(b, 0); p != -1; p = bitset_next_set(b, p)) { + int n; + + n = snprintf(buf, sizeof(buf), "%s%d", prefix, (int) p); + arg_append(app, occ, buf, n); + prefix = ", "; + res += n; + } + arg_append(app, occ, "]", 1); + + return res; +} + /** * emit a Firm object */ @@ -165,6 +194,7 @@ arg_env_t *firm_get_arg_env(void) static arg_handler_t firm_handler = { firm_get_arg_type, firm_emit }; static arg_handler_t ident_handler = { firm_get_arg_type, firm_emit_ident }; static arg_handler_t indent_handler = { firm_get_arg_type_int, firm_emit_indent }; + static arg_handler_t bitset_handler = { bitset_get_arg_type, bitset_emit }; static struct { const char *name; @@ -193,6 +223,7 @@ arg_env_t *firm_get_arg_env(void) arg_register(env, "firm:ident", 'I', &ident_handler); arg_register(env, "firm:indent", 'D', &indent_handler); + /* arg_register(env, "firm:bitset", 'b', &bitset_handler); */ } return env; diff --git a/ir/ir/iredges.c b/ir/ir/iredges.c index 146f1f329..2a7395cd0 100644 --- a/ir/ir/iredges.c +++ b/ir/ir/iredges.c @@ -3,6 +3,7 @@ * @author Sebastian Hack * @date 14.1.2005 */ + #ifdef HAVE_CONFIG_H #include "config.h" #endif @@ -71,34 +72,55 @@ void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir * Only do something, if the old and new target differ. */ if(tgt != old_tgt) { + int is_block_edge = is_Block(src); set *edges = _get_irg_edge_info(irg)->edges; - ir_edge_t templ; + ir_block_edge_t space; + ir_edge_t *templ = (ir_edge_t *) &space; ir_edge_t *edge; + size_t size; + + /* + * This is scray, but: + * If two entries in a set do not have the same size, they are + * treated as unequal, ignoring the comparison function. + * So, edges from blocks have extra storage (they are + * ir_block_edge_t's). + */ + size = is_block_edge ? sizeof(ir_block_edge_t) : sizeof(ir_edge_t); /* Initialize the edge template to search in the set. */ + memset(templ, 0, size); #ifdef DEBUG_libfirm - templ.src_nr = get_irn_node_nr(src); + templ->src_nr = get_irn_node_nr(src); #endif - templ.src = src; - templ.pos = pos; - templ.invalid = 0; - templ.present = 0; - INIT_LIST_HEAD(&templ.list); + templ->src = src; + templ->pos = pos; + templ->invalid = 0; + templ->present = 0; /* * If the target is NULL, the edge shall be deleted. */ if(tgt == NULL) { /* search the edge in the set. */ - edge = set_find(edges, &templ, sizeof(templ), edge_hash(&templ)); + edge = set_find(edges, templ, size, edge_hash(templ)); /* mark the edge invalid if it was found */ if(edge) { + ir_block_edge_t *block_edge = (ir_block_edge_t *) edge; + msg = "deleting"; list_del(&edge->list); edge->invalid = 1; edge->pos = -2; edge->src = NULL; + + /* + * If the edge is a cf edge, we delete it also + * from the list of all block successor edges. + */ + if(is_block_edge) + list_del(&block_edge->succ_list); } /* If the edge was not found issue a warning on the debug stream */ @@ -116,6 +138,16 @@ void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir else { struct list_head *head = _get_irn_outs_head(tgt); + /* + * The list head in the block of the edges target. + * Therein all control flow edges directed at that block + * are recorded. + */ + struct list_head *succ_head = + is_block_edge ? _get_block_succ_head(get_nodes_block(tgt)) : NULL; + + ir_block_edge_t *block_edge; + if(!node_is_in_irgs_storage(irg, tgt)) return; @@ -126,7 +158,8 @@ void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir * insert the edge, if it is not yet in the set or return * the instance in the set. */ - edge = set_insert(edges, &templ, sizeof(templ), edge_hash(&templ)); + edge = set_insert(edges, templ, size, edge_hash(templ)); + block_edge = (ir_block_edge_t *) edge; #ifdef DEBUG_libfirm assert(!edge->invalid && "Invalid edge encountered"); @@ -136,6 +169,11 @@ void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir if(old_tgt) { msg = "redirecting"; list_move(&edge->list, head); + + /* If the edge is a cf edge, move it from the successor list. */ + if(is_block_edge) + list_move(&block_edge->succ_list, succ_head); + _get_irn_edge_info(old_tgt)->out_count -= 1; } @@ -143,6 +181,13 @@ void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir else { msg = "adding"; list_add(&edge->list, head); + + /* + * If the edge is cf edge, enter it into the successor list + * of the target node's block. + */ + if(is_block_edge) + list_add(&block_edge->succ_list, succ_head); } _get_irn_edge_info(tgt)->out_count += 1; @@ -179,7 +224,6 @@ void edges_invalidate(ir_node *irn, ir_graph *irg) edges_node_deleted(irn, irg); } - static void build_edges_walker(ir_node *irn, void *data) { ir_graph *irg = data; @@ -245,17 +289,19 @@ static void verify_set_presence(ir_node *irn, void *data) int i, n; for(i = 0, n = get_irn_arity(irn) + not_a_block; i < n; ++i) { - ir_edge_t templ; + ir_block_edge_t space; + ir_edge_t *templ = (ir_edge_t *) &space; ir_edge_t *e; + size_t size = not_a_block ? sizeof(ir_edge_t) : sizeof(ir_block_edge_t); - templ.src = irn; - templ.pos = i - not_a_block; + templ->src = irn; + templ->pos = i - not_a_block; - e = set_find(edges, &templ, sizeof(templ), edge_hash(&templ)); + e = set_find(edges, templ, size, edge_hash(templ)); if(e != NULL) e->present = 1; else - DBG((dbg, LEVEL_DEFAULT, "edge %n,%d is missing\n", irn, templ.pos)); + DBG((dbg, LEVEL_DEFAULT, "edge %n,%d is missing\n", irn, templ->pos)); } } @@ -321,4 +367,10 @@ int (get_edge_src_pos)(const ir_edge_t *edge) return _get_edge_src_pos(edge); } +int (get_irn_n_edges)(const ir_node *irn) +{ + return _get_irn_n_edges(irn); +} + + #endif /* FIRM_EDGES_INPLACE */ diff --git a/ir/ir/iredges.h b/ir/ir/iredges.h index 169b47fd0..5f2b11da8 100644 --- a/ir/ir/iredges.h +++ b/ir/ir/iredges.h @@ -15,6 +15,11 @@ typedef struct _ir_edge_t ir_edge_t; #endif +#ifndef _IR_BLOCK_EDGE_TYPEDEF_ +#define _IR_BLOCK_EDGE_TYPEDEF_ +typedef struct _ir_block_edge_t ir_block_edge_t; +#endif + /** * Get the first edge pointing to some node. * @note There is no order on out edges. First in this context only @@ -42,6 +47,15 @@ const ir_edge_t *get_irn_out_edge_next(const ir_node *irn, #define foreach_out_edge(irn,edge) \ for(edge = get_irn_out_edge_first(irn); edge; edge = get_irn_out_edge_next(irn, edge)) +/** + * A convenience iteration macro for all control flow edges + * leaving a block, and thus are cf successor edges. + * @param bl The block. + * @param edge An @c ir_edge_t pointer which is set to the current edge. + */ +#define foreach_block_succ(bl,edge) \ + for(edge = get_block_succ_first(bl); edge; edge = get_block_succ_next(bl, edge)) + /* * Get the source node of an edge. * @param edge The edge. @@ -49,6 +63,13 @@ const ir_edge_t *get_irn_out_edge_next(const ir_node *irn, */ ir_node *get_edge_src_irn(const ir_edge_t *edge); +/** + * Get the number of edges pointing to a node. + * @param irn The node. + * @return The number of edges pointing to this node. + */ +int get_irn_n_edges(const ir_node *irn); + /** * Get the position of an edge. * @param edge. @@ -56,11 +77,23 @@ ir_node *get_edge_src_irn(const ir_edge_t *edge); */ extern int get_edge_src_pos(const ir_edge_t *edge); +/** + * Check, if the out edges are activated. + * @param irg The graph. + * @return 1, if the edges are present for the given irg, 0 if not. + */ extern int edges_activated(const ir_graph *irg); +/** + * Activate the edges for an irg. + * @param irg The graph to activate the edges for. + **/ extern void edges_activate(ir_graph *irg); +/** + * Deactivate the edges for an irg. + * @param irg The graph. + */ extern void edges_deactivate(ir_graph *irg); - #endif /* _FIRM_EDGES_H */ diff --git a/ir/ir/iredges_t.h b/ir/ir/iredges_t.h index cb8d35021..613c8494c 100644 --- a/ir/ir/iredges_t.h +++ b/ir/ir/iredges_t.h @@ -42,9 +42,22 @@ struct _ir_edge_t { #endif ir_node *src; /**< The source node of the edge. */ int pos; /**< The position of the edge at @p src. */ - struct list_head list; /**< The list head to queue all out edges at a node. */ unsigned invalid : 1; /**< edges that are removed are marked invalid. */ unsigned present : 1; /**< Used by the verifier. Don't rely on its content. */ + struct list_head list; /**< The list head to queue all out edges at a node. */ +}; + +/** + * A block edge inherits from a normal edge. + * They represent edges leading from a block to a control flow node + * and are used to quickly find all control flow successors of + * a block. + */ +struct _ir_block_edge_t { + struct _ir_edge_t edge; /**< The inherited data. */ + struct list_head succ_list; /**< List element listing all + control flow edges to the + successors of a block. */ }; /** Accessor for private irn info. */ @@ -59,6 +72,12 @@ struct _ir_edge_t { */ #define _get_irn_outs_head(irn) (&_get_irn_edge_info(irn)->outs_head) +/** + * Convenience macro to get the succ_head from a block_attr + * struct. + */ +#define _get_block_succ_head(bl) (&((bl)->attr.block.succ_head)) + /** * Get the first edge pointing to some node. * @note There is no order on out edges. First in this context only @@ -84,6 +103,43 @@ static INLINE const ir_edge_t *_get_irn_out_edge_next(const ir_node *irn, const return next == _get_irn_outs_head(irn) ? NULL : list_entry(next, ir_edge_t, list); } +/** + * Get the first successor edge of a block. + * A successor edge is an edge originated from another block, pointing + * to a mode_X node in the given block and is thus a control flow + * successor edge. + * @param irn The block. + * @return The first successor edge of the block. + */ +static INLINE const ir_edge_t *_get_block_succ_first(const ir_node *irn) +{ + const struct list_head *head; + + assert(is_Block(irn) && "Node must be a block here"); + head = _get_block_succ_head(irn); + return (ir_edge_t *) (list_empty(head) ? NULL : + list_entry(head->next, ir_block_edge_t, succ_list)); +} + +/** + * Get the next block successor edge. + * @see See _get_block_succ_first() for details. + * @param irn The block. + * @param last The last edge. + * @return The next edge, or NULL if there is no further. + */ +static INLINE const ir_edge_t *_get_block_succ_next(const ir_node *irn, const ir_edge_t *last) +{ + const ir_block_edge_t *block_edge; + struct list_head *next; + + assert(is_Block(irn) && "Node must be a block here"); + block_edge = (const ir_block_edge_t *) last; + next = block_edge->succ_list.next; + return (ir_edge_t *) (next == _get_block_succ_head(irn) ? NULL : + list_entry(next, ir_block_edge_t, succ_list)); +} + /** * Get the source node of an edge. * @param edge The edge. @@ -104,6 +160,16 @@ static INLINE int _get_edge_src_pos(const ir_edge_t *edge) return edge ? edge->pos : -1; } +/** + * Get the number of edges pointing to a node. + * @param irn The node. + * @return The number of edges pointing to this node. + */ +static INLINE int _get_irn_n_edges(const ir_node *irn) +{ + return _get_irn_edge_info(irn)->out_count; +} + static INLINE int _edges_activated(const ir_graph *irg) { return _get_irg_edge_info(irg)->activated; @@ -137,6 +203,8 @@ extern void init_edges(void); #define get_irn_out_edge_first(irn) _get_irn_out_edge_first(irn) #define get_irn_out_edge_next(irn,last) _get_irn_out_edge_next(irn, last) +#define get_block_succ_first(irn) _get_block_succ_first(irn) +#define get_block_succ_next(irn,last) _get_block_succ_next(irn, last) #define get_edge_src_irn(edge) _get_edge_src_irn(edge) #define get_edge_src_pos(edge) _get_edge_src_pos(edge) #define edges_activated(irg) _edges_activated(irg) diff --git a/ir/ir/irnode.c b/ir/ir/irnode.c index 7ddc7d81c..2a1b14895 100644 --- a/ir/ir/irnode.c +++ b/ir/ir/irnode.c @@ -162,6 +162,9 @@ new_ir_node (dbg_info *db, ir_graph *irg, ir_node *block, ir_op *op, ir_mode *mo int not_a_block = is_no_Block(res); INIT_LIST_HEAD(&res->edge_info.outs_head); + if(!not_a_block) + INIT_LIST_HEAD(&res->attr.block.succ_head); + for (i = 0, n = arity + not_a_block; i < n; ++i) edges_notify_edge(res, i - not_a_block, res->in[i], NULL, irg); diff --git a/ir/ir/irnode_t.h b/ir/ir/irnode_t.h index 900615493..6599ead57 100644 --- a/ir/ir/irnode_t.h +++ b/ir/ir/irnode_t.h @@ -68,6 +68,8 @@ typedef struct { @@@ @todo Ev. replace by bitfield! */ ir_extblk *extblk; /**< the extended basic block this block belongs to */ + struct list_head succ_head; /**< A list head for all successor edges of a block. */ + } block_attr; /** Start attributes */ diff --git a/ir/ir/irop.c b/ir/ir/irop.c index ee3e553dd..67bdb35ea 100644 --- a/ir/ir/irop.c +++ b/ir/ir/irop.c @@ -119,12 +119,21 @@ call_copy_attr(const ir_node *old_node, ir_node *new_node) { remove_Call_callee_arr(new_node); } +static void +block_copy_attr(const ir_node *old_node, ir_node *new_node) +{ + default_copy_attr(old_node, new_node); + INIT_LIST_HEAD(&new_node->attr.block.succ_head); +} + /** * Sets the copy_attr operation for an ir_op */ static ir_op *firm_set_default_copy_attr(ir_op *op) { if (op->code == iro_Call) op->copy_attr = call_copy_attr; + else if (op->code == iro_Block) + op->copy_attr = block_copy_attr; else op->copy_attr = default_copy_attr; -- 2.20.1