X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Firouts.c;h=c95fd431f064f676b045629e682ba26c4ebfb5c7;hb=a6888dd0c74a74aa5ec89d4542e402bda7cd61cb;hp=c2084b157d7886658faff0ad75f407b2cbd4a3cd;hpb=1a26f4853c07d1ecd68a097409dd602edfe29eff;p=libfirm diff --git a/ir/ana/irouts.c b/ir/ana/irouts.c index c2084b157..c95fd431f 100644 --- a/ir/ana/irouts.c +++ b/ir/ana/irouts.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. * @@ -22,7 +22,6 @@ * @brief Compute and access out edges (also called def-use edges). * @author Goetz Lindenmaier, Michael Beck * @date 1.2002 - * @version $Id$ */ #include "config.h" @@ -34,15 +33,10 @@ #include "irgraph_t.h" #include "irprog_t.h" #include "irgwalk.h" -#include "irtools.h" +#include "util.h" #include "irprintf.h" #include "error.h" - -#ifdef DEBUG_libfirm -/* Note: ir_node.out_valid and ir_graph.n_outs are only present when DEBUG_libfirm is defined */ -/* Accesses to out_valid and n_outs are fenced out to avoid breakage - when compiling with neither DEBUG_libfirm or NDEBUG defined */ -#endif /* defined DEBUG_libfirm */ +#include "ircons.h" /*--------------------------------------------------------------------*/ /** Accessing the out datastructures **/ @@ -63,33 +57,30 @@ int get_irn_outs_computed(const ir_node *node) return node->out != NULL; } -/* returns the number of successors of the node: */ int get_irn_n_outs(const ir_node *node) { assert(node && node->kind == k_ir_node); #ifdef DEBUG_libfirm - /* assert(node->out_valid); */ + assert(node->out_valid); #endif /* defined DEBUG_libfirm */ /* we misuse the first for the size info of the out array */ return node->out[0].pos; } -/* Access successor n */ ir_node *get_irn_out(const ir_node *def, int pos) { assert(pos >= 0 && pos < get_irn_n_outs(def)); #ifdef DEBUG_libfirm - /* assert(def->out_valid); */ + assert(def->out_valid); #endif /* defined DEBUG_libfirm */ return def->out[pos+1].use; } -/* Access successor n */ ir_node *get_irn_out_ex(const ir_node *def, int pos, int *in_pos) { assert(pos >= 0 && pos < get_irn_n_outs(def)); #ifdef DEBUG_libfirm - /* assert(def->out_valid); */ + assert(def->out_valid); #endif /* defined DEBUG_libfirm */ *in_pos = def->out[pos+1].pos; return def->out[pos+1].use; @@ -100,13 +91,12 @@ void set_irn_out(ir_node *def, int pos, ir_node *use, int in_pos) assert(def && use); assert(pos >= 0 && pos < get_irn_n_outs(def)); #ifdef DEBUG_libfirm - def->out_valid = 1; /* assume that this function is used correctly */ + assert(def->out_valid); #endif /* defined DEBUG_libfirm */ def->out[pos+1].use = use; def->out[pos+1].pos = in_pos; } -/* Return the number of control flow successors, ignore keep-alives. */ int get_Block_n_cfg_outs(const ir_node *bl) { int i, n_cfg_outs = 0; @@ -116,13 +106,12 @@ int get_Block_n_cfg_outs(const ir_node *bl) #endif /* defined DEBUG_libfirm */ for (i = 1; i <= bl->out[0].pos; ++i) { ir_node *succ = bl->out[i].use; - if (get_irn_mode(succ) == mode_X && !is_End(succ)) + if (get_irn_mode(succ) == mode_X && !is_End(succ) && !is_Bad(succ)) n_cfg_outs += succ->out[0].pos; } return n_cfg_outs; } -/* Return the number of control flow successors, honor keep-alives. */ int get_Block_n_cfg_outs_ka(const ir_node *bl) { int i, n_cfg_outs = 0; @@ -133,7 +122,8 @@ int get_Block_n_cfg_outs_ka(const ir_node *bl) for (i = 1; i <= bl->out[0].pos; ++i) { ir_node *succ = bl->out[i].use; if (get_irn_mode(succ) == mode_X) { - + if (is_Bad(succ)) + continue; if (is_End(succ)) { /* ignore End if we are in the Endblock */ if (get_nodes_block(succ) == bl) @@ -147,7 +137,6 @@ int get_Block_n_cfg_outs_ka(const ir_node *bl) return n_cfg_outs; } -/* Access predecessor n, ignore keep-alives. */ ir_node *get_Block_cfg_out(const ir_node *bl, int pos) { int i; @@ -157,7 +146,7 @@ ir_node *get_Block_cfg_out(const ir_node *bl, int pos) #endif /* defined DEBUG_libfirm */ for (i = 1; i <= bl->out[0].pos; ++i) { ir_node *succ = bl->out[i].use; - if (get_irn_mode(succ) == mode_X && !is_End(succ)) { + if (get_irn_mode(succ) == mode_X && !is_End(succ) && !is_Bad(succ)) { int n_outs = succ->out[0].pos; if (pos < n_outs) return succ->out[pos + 1].use; @@ -168,7 +157,6 @@ ir_node *get_Block_cfg_out(const ir_node *bl, int pos) return NULL; } -/* Access predecessor n, honor keep-alives. */ ir_node *get_Block_cfg_out_ka(const ir_node *bl, int pos) { int i, n_outs; @@ -179,6 +167,8 @@ ir_node *get_Block_cfg_out_ka(const ir_node *bl, int pos) for (i = 1; i <= bl->out[0].pos; ++i) { ir_node *succ = bl->out[i].use; if (get_irn_mode(succ) == mode_X) { + if (is_Bad(succ)) + continue; if (is_End(succ)) { ir_node *end_bl = get_nodes_block(succ); if (end_bl == bl) { @@ -203,7 +193,8 @@ ir_node *get_Block_cfg_out_ka(const ir_node *bl, int pos) } static void irg_out_walk_2(ir_node *node, irg_walk_func *pre, - irg_walk_func *post, void *env) { + irg_walk_func *post, void *env) +{ int i, n; ir_node *succ; @@ -223,19 +214,20 @@ static void irg_out_walk_2(ir_node *node, irg_walk_func *pre, if (post) post(node, env); } -void irg_out_walk(ir_node *node, - irg_walk_func *pre, irg_walk_func *post, - void *env) { +void irg_out_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, + void *env) +{ assert(node); - if (get_irg_outs_state(current_ir_graph) != outs_none) { - inc_irg_visited (current_ir_graph); + ir_graph *irg = get_irn_irg(node); + if (irg_has_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUTS)) { + inc_irg_visited (irg); irg_out_walk_2(node, pre, post, env); } } -static void irg_out_block_walk2(ir_node *bl, - irg_walk_func *pre, irg_walk_func *post, - void *env) { +static void irg_out_block_walk2(ir_node *bl, irg_walk_func *pre, + irg_walk_func *post, void *env) +{ int i, n; if (!Block_block_visited(bl)) { @@ -256,11 +248,9 @@ static void irg_out_block_walk2(ir_node *bl, } } -/* Walks only over Block nodes in the graph. Has it's own visited - flag, so that it can be interleaved with the other walker. */ -void irg_out_block_walk(ir_node *node, - irg_walk_func *pre, irg_walk_func *post, - void *env) { +void irg_out_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, + void *env) +{ assert(is_Block(node) || (get_irn_mode(node) == mode_X)); @@ -305,7 +295,7 @@ static int _count_outs(ir_node *n) int start, i, res, irn_arity; mark_irn_visited(n); - n->out = INT_TO_PTR(1); /* Space for array size. */ + n->out = (ir_def_use_edge*) INT_TO_PTR(1); /* Space for array size. */ start = is_Block(n) ? 0 : -1; irn_arity = get_irn_arity(n); @@ -325,7 +315,7 @@ static int _count_outs(ir_node *n) res += _count_outs(skipped_pred); /*count my Def-Use edges */ - skipped_pred->out = INT_TO_PTR(PTR_TO_INT(skipped_pred->out) + 1); + skipped_pred->out = (ir_def_use_edge*) INT_TO_PTR(PTR_TO_INT(skipped_pred->out) + 1); } return res; } @@ -344,10 +334,10 @@ static int count_outs(ir_graph *irg) /* Now handle anchored nodes. We need the out count of those even if they are not visible. */ - for (i = anchor_last - 1; i >= 0; --i) { + for (i = anchor_last; i >= anchor_first; --i) { n = get_irg_anchor(irg, i); if (!irn_visited_else_mark(n)) { - n->out = INT_TO_PTR(1); + n->out = (ir_def_use_edge*) INT_TO_PTR(1); ++res; } } @@ -364,7 +354,8 @@ static int count_outs(ir_graph *irg) */ static ir_def_use_edge *_set_out_edges(ir_node *use, ir_def_use_edge *free) { - int n_outs, start, i, irn_arity, pos; + int start, i, irn_arity, pos; + size_t n_outs; mark_irn_visited(use); @@ -412,16 +403,16 @@ static ir_def_use_edge *_set_out_edges(ir_node *use, ir_def_use_edge *free) static ir_def_use_edge *set_out_edges(ir_graph *irg, ir_def_use_edge *free) { ir_node *n; - int i, n_outs; + int i; inc_irg_visited(irg); free = _set_out_edges(get_irg_end(irg), free); /* handle anchored nodes */ - for (i = anchor_last - 1; i >= 0; --i) { + for (i = anchor_last; i >= anchor_first; --i) { n = get_irg_anchor(irg, i); if (!irn_visited_else_mark(n)) { - n_outs = PTR_TO_INT(n->out); + size_t n_outs = PTR_TO_INT(n->out); n->out = free; #ifdef DEBUG_libfirm n->out_valid = 1; @@ -433,7 +424,6 @@ static ir_def_use_edge *set_out_edges(ir_graph *irg, ir_def_use_edge *free) return free; } -/* compute the outs for a given graph */ void compute_irg_outs(ir_graph *irg) { ir_graph *rem = current_ir_graph; @@ -445,8 +435,7 @@ void compute_irg_outs(ir_graph *irg) /* Update graph state */ assert(get_irg_phase_state(current_ir_graph) != phase_building); - if (current_ir_graph->outs_state != outs_none) - free_irg_outs(current_ir_graph); + free_irg_outs(current_ir_graph); /* This first iteration counts the overall number of out edges and the number of out edges for each node. */ @@ -465,181 +454,33 @@ void compute_irg_outs(ir_graph *irg) /* Check how much memory we have used */ assert (end == (irg->outs + n_out_edges)); - current_ir_graph->outs_state = outs_consistent; + add_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUTS); current_ir_graph = rem; } void assure_irg_outs(ir_graph *irg) { - if (get_irg_outs_state(irg) != outs_consistent) + if (! irg_has_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUTS)) compute_irg_outs(irg); } void compute_irp_outs(void) { - int i; - for (i = get_irp_n_irgs() -1; i >= 0; --i) + size_t i, n; + for (i = 0, n = get_irp_n_irgs(); i < n; ++i) compute_irg_outs(get_irp_irg(i)); } void free_irp_outs(void) { - int i; - for (i = get_irp_n_irgs() -1; i >= 0; --i) + size_t i, n; + for (i = 0, n = get_irp_n_irgs(); i < n; ++i) free_irg_outs(get_irp_irg(i)); } - -/*------------------------------------------------------------* - * This computes the outedges for in interprocedural graph. * - * There is one quirk: * - * The number of the outedges for each node is saved in * - * the first member of the ir_node** array. Maybe we should * - * change this to make it more portable... * - *------------------------------------------------------------*/ - - -#ifdef INTERPROCEDURAL_VIEW -/** - * Inits the number of outedges for each node - * before counting. - */ -static void init_count(ir_node * node, void *env) -{ - (void) env; - node->out = (ir_node **) 1; /* 1 for the array size */ -} - - -/** - * Adjusts the out edge count for its predecessors - * and adds the current arity to the overall count, - * which is saved in "env" - */ -static void node_arity_count(ir_node * node, void * env) -{ - int *anz = (int *) env, arity, n_outs, i, start; - ir_node *succ; - - arity = get_irn_arity(node); - start = (is_Block(node)) ? 0 : -1; - - n_outs = 1 + arity + (-start); // ((is_Block(node)) ? 0 : 1); // Why + 1?? - *anz += n_outs; - - for (i = start; i < arity; i++) { - succ = get_irn_n(node, i); - succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1); - } -} - -/* - * Inits all nodes for setting the outedges - * Returns the overall count of edges - */ -int count_ip_outs(void) -{ - int res = 0; - - cg_walk(init_count, node_arity_count, &res); - - return(res); -} - -static int dummy_count = 0, global_count; /* Only for debugging */ - -/** - * For each node: Sets the pointer to array - * in which the outedges are written later. - * The current array start is transported in env - */ -static void set_array_pointer(ir_node *node, void *env) -{ - int n_outs; - ir_node ***free = (ir_node ***) env; - - /* Allocate my array */ - n_outs = PTR_TO_INT(node->out); /* We wrote the count here in count_ip_outs */ - dummy_count += n_outs; - assert(dummy_count <= global_count && "More outedges than initially counted!"); - node -> out = *free; - *free = &((*free)[n_outs]); - /* We count the successors again, the space will be sufficient. - We use this counter to remember the position for the next back - edge. */ - node -> out[0] = (ir_node *) 0; -} - - -/** - * Adds an outedge from the predecessor to the - * current node. - */ -static void set_out_pointer(ir_node * node, void *env) -{ - int i, arity = get_irn_arity(node); - ir_node *succ; - int start = (!is_Block(node)) ? -1 : 0; - (void) env; - - for (i = start; i < arity; ++i) { - succ = get_irn_n(node, i); - succ->out[get_irn_n_outs(succ)+1] = node; - succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1); - } -} - - -/* - * Sets the outedges for all nodes. - */ -void set_ip_outs(void) -{ - ir_node **outedge_array = get_irp_ip_outedges(); - cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array); -} - - - -/* - * Counts the outedges, allocates memory to save the - * outedges and fills this outedge array in interprocedural - * view! - */ -void compute_ip_outs(void) -{ - int n_out_edges; - ir_node **out_edges; - - assert(get_irp_ip_view_state() == ip_view_valid && - "Cannot construct outs for invalid ip view."); - - if (irp->outs_state != outs_none) { - free_ip_outs(); - } - - global_count = n_out_edges = count_ip_outs(); - out_edges = XMALLOCNZ(ir_node*, n_out_edges); - set_irp_ip_outedges(out_edges); - set_ip_outs(); -} - -void free_ip_outs(void) -{ - ir_node **out_edges = get_irp_ip_outedges(); - if (out_edges != NULL) { - free(out_edges); - set_irp_ip_outedges(NULL); - } - irp->outs_state = outs_none; -} -#endif - - void free_irg_outs(ir_graph *irg) { /* current_ir_graph->outs_state = outs_none; */ - irg->outs_state = outs_none; if (irg->outs) { #ifdef DEBUG_libfirm @@ -658,48 +499,3 @@ void free_irg_outs(ir_graph *irg) irg_walk_graph (irg, reset_outs, NULL, NULL); #endif /* defined DEBUG_libfirm */ } - -static void check_out_edges(ir_node *irn, void *env) -{ - int i, j, pos; - int *pError = env; - int error = *pError; - int last = is_Block(irn) ? 0 : -1; - - /* check forward: every input must have an out edge */ - for (i = get_irn_arity(irn) - 1; i >= last; --i) { - ir_node *pred = get_irn_n(irn, i); - - for (j = get_irn_n_outs(pred) - 1; j >= 0; --j) { - ir_node *user = get_irn_out_ex(pred, j, &pos); - - if (user == irn && pos == i) { - break; - } - } - if (j < 0) { - ir_fprintf(stderr, "Missing out edge from %+F input %d to %+F", irn, i, pred); - ++error; - } - } - - /* checking backward */ - for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) { - ir_node *user = get_irn_out_ex(irn, i, &pos); - - if (get_irn_n(user, pos) != irn) { - ir_fprintf(stderr, "Spurious out edge from %+F output %d to %+F", irn, i, user); - ++error; - } - } - *pError = error; -} - -/* verify outs edges. */ -void verify_outs(ir_graph *irg) -{ - int errors = 0; - irg_walk_graph(irg, NULL, check_out_edges, &errors); - if (errors > 0) - panic("Out edges are corrupt"); -}