X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fcombo.c;h=0c2b981668551333bd048d951ac492c1a9705b53;hb=6596239a5116d8b13257f7976b57c9de619a606e;hp=ce3d34492e990f755a73ba64d49bb36751d29703;hpb=9a6f244bb751c61fbf103e11c361c9f4a07c0642;p=libfirm diff --git a/ir/opt/combo.c b/ir/opt/combo.c index ce3d34492..0c2b98166 100644 --- a/ir/opt/combo.c +++ b/ir/opt/combo.c @@ -37,7 +37,6 @@ #include "irflag.h" #include "ircons.h" #include "list.h" -#include "array.h" #include "set.h" #include "pmap.h" #include "obstack.h" @@ -126,6 +125,7 @@ struct node_t { struct partition_t { list_head entries; /**< The head of partition node list. */ list_head cprop; /**< The head of partition.cprop list. */ + list_head split_list; /**< Double-linked list of entries that must be processed by split_by(). */ partition_t *wl_next; /**< Next entry in the work list if any. */ partition_t *touched_next; /**< Points to the next partition in the touched set. */ partition_t *cprop_next; /**< Points to the next partition in the cprop list. */ @@ -164,6 +164,11 @@ typedef void *(*what_func)(const node_t *node, environment_t *env); #define get_irn_node(irn) ((node_t *)get_irn_link(irn)) #define set_irn_node(irn, node) set_irn_link(irn, node) +/* we do NOT use tarval_unreachable here, instead we use Top for this purpose */ +#undef tarval_unreachable +#define tarval_unreachable tarval_top + + /** The debug module handle. */ DEBUG_ONLY(static firm_dbg_module_t *dbg;) @@ -218,14 +223,10 @@ static void verify_type(const lattice_elem_t old_type, const lattice_elem_t new_ /* from Top down-to is always allowed */ return; } - if (old_type.tv == tarval_unreachable) { - if (new_type.tv == tarval_reachable) { - /* U -> R */ - return; - } + if (old_type.tv == tarval_reachable) { panic("verify_type(): wrong translation from %+F to %+F", old_type, new_type); } - if (new_type.tv == tarval_bottom) { + if (new_type.tv == tarval_bottom || new_type.tv == tarval_reachable) { /* bottom reached */ return; } @@ -235,13 +236,6 @@ static void verify_type(const lattice_elem_t old_type, const lattice_elem_t new_ #define verify_type(old_type, new_type) #endif -/** - * Return the "top" value depending on the mode - */ -static tarval *get_top_value(const ir_mode *mode) { - return (mode == mode_X || mode == mode_BB) ? tarval_unreachable : tarval_top; -} - /** * Compare two pointer values of a listmap. */ @@ -340,7 +334,7 @@ static void sort_irn_outs(node_t *node) { if (n_outs > 1) { qsort(&irn->out[1], n_outs, sizeof(irn->out[0]), cmp_def_use_edge); } - node->max_user_input = irn->out[n_outs + 1].pos; + node->max_user_input = irn->out[n_outs].pos; } /* sort_irn_outs */ /** @@ -391,6 +385,7 @@ static INLINE partition_t *new_partition(environment_t *env) { INIT_LIST_HEAD(&part->entries); INIT_LIST_HEAD(&part->cprop); + INIT_LIST_HEAD(&part->split_list); part->wl_next = NULL; part->touched_next = NULL; part->cprop_next = NULL; @@ -444,14 +439,13 @@ static INLINE lattice_elem_t get_partition_type(const partition_t *X) { static node_t *create_partition_node(ir_node *irn, partition_t *part, environment_t *env) { /* create a partition node and place it in the partition */ node_t *node = obstack_alloc(&env->obst, sizeof(*node)); - ir_mode *mode = get_irn_mode(irn); INIT_LIST_HEAD(&node->node_list); INIT_LIST_HEAD(&node->cprop_list); node->node = irn; node->part = part; node->next = NULL; - node->type.tv = get_top_value(mode); + node->type.tv = tarval_top; node->max_user_input = 0; node->next_edge = 0; node->on_touched = 0; @@ -673,7 +667,7 @@ static void add_node_to_cprop(node_t *y, environment_t *env) { /** * Check whether a type is neither Top or a constant. - * Note: U, R are NOT constants! + * Note: U is handled like Top here, R is a constant. * * @param type the type to check */ @@ -740,7 +734,7 @@ static void cause_splits(environment_t *env) { y = get_irn_node(succ); if (is_constant_type(y->type)) { code = get_irn_opcode(succ); - if (code == iro_Sub || (code == iro_Proj && is_Cmp(get_Proj_pred(succ)))) + if (code == iro_Sub || code == iro_Cmp) add_node_to_cprop(y, env); } @@ -779,13 +773,13 @@ static void cause_splits(environment_t *env) { * * @param X the partition to split * @param What a function returning an Id for every node of the partition X - * @param P an flexible array to store the result partitions or NULL + * @param P a list head to store the result partitions * @param env the environment * - * @return if P != NULL P will be filled with the resulting partitions and returned + * @return P */ -static partition_t **split_by_what(partition_t *X, what_func What, - partition_t **P, environment_t *env) { +static list_head *split_by_what(partition_t *X, what_func What, + list_head *P, environment_t *env) { node_t *x, *S; listmap_t map; listmap_entry_t *iter; @@ -819,14 +813,10 @@ static partition_t **split_by_what(partition_t *X, what_func What, /* Add SPLIT( X, S ) to P. */ DB((dbg, LEVEL_2, "Split part%d by what\n", X->nr)); R = split(X, S, env); - if (P != NULL) { - ARR_APP1(partition_t *, P, R); - } + list_add(&R->split_list, P); } /* Add X to P. */ - if (P != NULL) { - ARR_APP1(partition_t *, P, X); - } + list_add(&X->split_list, P); listmap_term(&map); return P; @@ -903,40 +893,69 @@ static int is_type_constant(lattice_elem_t type) { * @param env the environment */ static void split_by(partition_t *X, environment_t *env) { - partition_t **P = NEW_ARR_F(partition_t *, 0); - int i, j, k; + list_head hP; + list_head *P = &hP; + int input; + INIT_LIST_HEAD(P); DB((dbg, LEVEL_2, "WHAT = lambda n.(n.type) on part%d\n", X->nr)); P = split_by_what(X, lambda_type, P, env); - for (i = ARR_LEN(P) - 1; i >= 0; --i) { - partition_t *Y = P[i]; + do { + partition_t *Y = list_entry(P->next, partition_t, split_list); + list_del(&Y->split_list); if (Y->n_nodes > 1) { lattice_elem_t type = get_partition_type(Y); - /* we do not want split the TOP, unreachable or constant partitions */ - if (type.tv != tarval_top && type.tv != tarval_unreachable && !is_type_constant(type)) { - partition_t **Q = NEW_ARR_F(partition_t *, 0); + /* we do not want split the TOP or constant partitions */ + if (type.tv != tarval_top && !is_type_constant(type)) { + list_head hQ; + list_head *Q = &hQ; + INIT_LIST_HEAD(Q); DB((dbg, LEVEL_2, "WHAT = lambda n.(n.opcode) on part%d\n", Y->nr)); Q = split_by_what(Y, lambda_opcode, Q, env); - for (j = ARR_LEN(Q) - 1; j >= 0; --j) { - partition_t *Z = Q[j]; - - for (k = Z->max_arity - 1; k >= -1; --k) { - if (Z->n_nodes > 1) { - env->lambda_input = k; - DB((dbg, LEVEL_2, "WHAT = lambda n.(n[%d].partition) on part%d\n", k, Z->nr)); - split_by_what(Z, lambda_partition, NULL, env); + do { + list_head hR, hS; + partition_t *Z = list_entry(Q->next, partition_t, split_list); + int max_arity = Z->max_arity; + list_head *R = &hR, *S = &hS, *T; + + list_del(&Z->split_list); + + if (Z->n_nodes > 1) { + INIT_LIST_HEAD(R); + INIT_LIST_HEAD(S); + + /* + * BEWARE: during splitting by input 2 for instance we might + * create new partitions which are different by input 1, so collect + * them and split further. + */ + list_add(&Z->split_list, R); + for (input = max_arity - 1; input >= -1; --input) { + do { + partition_t *Z_prime = list_entry(R->next, partition_t, split_list); + + list_del(&Z_prime->split_list); + if (Z_prime->n_nodes > 1) { + env->lambda_input = input; + DB((dbg, LEVEL_2, "WHAT = lambda n.(n[%d].partition) on part%d\n", input, Z_prime->nr)); + S = split_by_what(Z_prime, lambda_partition, S, env); + } else { + list_add(&Z_prime->split_list, S); + } + } while (!list_empty(R)); + T = R; + R = S; + S = T; } } - } - DEL_ARR_F(Q); + } while (!list_empty(Q)); } } - } - DEL_ARR_F(P); + } while (!list_empty(P)); } /* split_by */ /** @@ -947,18 +966,11 @@ static void split_by(partition_t *X, environment_t *env) { static void default_compute(node_t *node) { int i; ir_node *irn = node->node; - tarval *top = tarval_top; - - if (get_irn_mode(node->node) == mode_X) - top = tarval_unreachable; - - if (get_irn_pinned(irn) == op_pin_state_pinned) { - node_t *block = get_irn_node(get_nodes_block(irn)); + node_t *block = get_irn_node(get_nodes_block(irn)); - if (block->type.tv == tarval_unreachable) { - node->type.tv = top; - return; - } + if (block->type.tv == tarval_unreachable) { + node->type.tv = tarval_top; + return; } /* if any of the data inputs have type top, the result is type top */ @@ -967,7 +979,7 @@ static void default_compute(node_t *node) { node_t *p = get_irn_node(pred); if (p->type.tv == tarval_top) { - node->type.tv = top; + node->type.tv = tarval_top; return; } } @@ -996,9 +1008,34 @@ static void compute_Block(node_t *node) { return; } } - node->type.tv = tarval_unreachable; + node->type.tv = tarval_top; } /* compute_Block */ +/** + * (Re-)compute the type for a Bad node. + * + * @param node the node + */ +static void compute_Bad(node_t *node) { + /* Bad nodes ALWAYS compute Top */ + node->type.tv = tarval_top; +} /* compute_Bad */ + +/** + * (Re-)compute the type for an Unknown node. + * + * @param node the node + */ +static void compute_Unknown(node_t *node) { + /* While Unknown nodes compute Top, but this is dangerous: + * a if (unknown) would lead to BOTH control flows unreachable. + * While this is correct in the given semantics, it would destroy the Firm + * graph. + * For now, we compute bottom here. + */ + node->type.tv = tarval_bottom; +} /* compute_Unknown */ + /** * (Re-)compute the type for a Jmp node. * @@ -1175,17 +1212,46 @@ static void compute_Sub(node_t *node) { } } else if (r->part == l->part && (!mode_is_float(get_irn_mode(l->node)))) { - /* - * BEWARE: a - a is NOT always 0 for floating Point values, as - * NaN op NaN = NaN, so we must check this here. - */ - ir_mode *mode = get_irn_mode(sub); - node->type.tv = get_mode_null(mode); + if (node->type.tv == tarval_top) { + /* + * BEWARE: a - a is NOT always 0 for floating Point values, as + * NaN op NaN = NaN, so we must check this here. + */ + ir_mode *mode = get_irn_mode(sub); + node->type.tv = get_mode_null(mode); + } else { + node->type.tv = tarval_bottom; + } } else { node->type.tv = tarval_bottom; } } /* compute_Sub */ +/** + * (Re-)compute the type for Cmp. + * + * @param node the node + */ +static void compute_Cmp(node_t *node) { + ir_node *cmp = node->node; + node_t *l = get_irn_node(get_Cmp_left(cmp)); + node_t *r = get_irn_node(get_Cmp_right(cmp)); + lattice_elem_t a = l->type; + lattice_elem_t b = r->type; + + if (a.tv == tarval_top || b.tv == tarval_top) { + node->type.tv = tarval_top; + } else if (is_con(a) && is_con(b)) { + /* both nodes are constants, we can propbably do something */ + node->type.tv = tarval_b_true; + } else if (r->part == l->part) { + /* both nodes congruent, we can probably do something */ + node->type.tv = tarval_b_true; + } else { + node->type.tv = tarval_bottom; + } +} /* compute_Proj_Cmp */ + /** * (Re-)compute the type for a Proj(Cmp). * @@ -1206,11 +1272,15 @@ static void compute_Proj_Cmp(node_t *node, ir_node *cmp) { default_compute(node); } else if (r->part == l->part && (!mode_is_float(get_irn_mode(l->node)) || pnc == pn_Cmp_Lt || pnc == pn_Cmp_Gt)) { - /* - * BEWARE: a == a is NOT always True for floating Point values, as - * NaN != NaN is defined, so we must check this here. - */ - node->type.tv = new_tarval_from_long(pnc & pn_Cmp_Eq, mode_b); + if (node->type.tv == tarval_top) { + /* + * BEWARE: a == a is NOT always True for floating Point values, as + * NaN != NaN is defined, so we must check this here. + */ + node->type.tv = new_tarval_from_long(pnc & pn_Cmp_Eq, mode_b); + } else { + node->type.tv = tarval_bottom; + } } else { node->type.tv = tarval_bottom; } @@ -1299,14 +1369,21 @@ static void compute_Proj(node_t *node) { node_t *block = get_irn_node(get_nodes_block(skip_Proj(proj))); ir_node *pred = get_Proj_pred(proj); + if (get_Proj_proj(proj) == pn_Start_X_initial_exec && is_Start(pred)) { + /* The initial_exec node is ALWAYS reachable. */ + node->type.tv = tarval_reachable; + return; + } + if (block->type.tv == tarval_unreachable) { - /* a Proj node in an unreachable block computes Top - except if it's the initial_exec node. */ - if (get_Proj_proj(proj) != pn_Start_X_initial_exec || - ! is_Start(pred)) { - node->type.tv = get_top_value(mode); - return; - } + /* a Proj in a unreachable Block stay Top */ + node->type.tv = tarval_top; + return; + } + if (get_irn_node(pred)->type.tv == tarval_top) { + /* if the predecessor is Top, its Proj follow */ + node->type.tv = tarval_top; + return; } if (mode == mode_M) { @@ -1325,7 +1402,8 @@ static void compute_Proj(node_t *node) { switch (get_irn_opcode(pred)) { case iro_Start: - /* the Proj_X from the Start is always reachable */ + /* the Proj_X from the Start is always reachable. + However this is already handled at the top. */ node->type.tv = tarval_reachable; break; case iro_Cond: @@ -1336,6 +1414,28 @@ static void compute_Proj(node_t *node) { } } /* compute_Proj */ +/** + * (Re-)compute the type for a Confirm-Nodes. + * + * @param node the node + */ +static void compute_Confirm(node_t *node) { + ir_node *confirm = node->node; + node_t *pred = get_irn_node(get_Confirm_value(confirm)); + + if (get_Confirm_cmp(confirm) == pn_Cmp_Eq) { + node_t *bound = get_irn_node(get_Confirm_bound(confirm)); + + if (is_con(bound->type)) { + /* is equal to a constant */ + node->type = bound->type; + return; + } + } + /* a Confirm is a copy OR a Const */ + node->type = pred->type; +} /* compute_Confirm */ + /** * (Re-)compute the type for a given node. * @@ -1363,9 +1463,9 @@ static void propagate(environment_t *env) { while (env->cprop != NULL) { /* remove the first partition X from cprop */ - X = env->cprop; + X = env->cprop; X->on_cprop = 0; - env->cprop = X->cprop_next; + env->cprop = X->cprop_next; DB((dbg, LEVEL_2, "Propagate type on part%d\n", X->nr)); fallen = NULL; @@ -1432,54 +1532,171 @@ static ir_node *get_leader(node_t *node) { return get_first_node(part)->node; } return node->node; +} /* get_leader */ + +/** + * Return non-zero if the control flow predecessor node pred + * is the only reachable control flow exit of its block. + * + * @param pred the control flow exit + */ +static int can_exchange(ir_node *pred) { + if (is_Start(pred)) + return 0; + else if (is_Jmp(pred)) + return 1; + else if (get_irn_mode(pred) == mode_T) { + int i, k; + + /* if the predecessor block has more than one + reachable outputs we cannot remove the block */ + k = 0; + for (i = get_irn_n_outs(pred) - 1; i >= 0; --i) { + ir_node *proj = get_irn_out(pred, i); + node_t *node; + + /* skip non-control flow Proj's */ + if (get_irn_mode(proj) != mode_X) + continue; + + node = get_irn_node(proj); + if (node->type.tv == tarval_reachable) { + if (++k > 1) + return 0; + } + } + return 1; + } + return 0; } /** - * Post-Walker, apply the analysis results; + * Block Post-Walker, apply the analysis results on control flow by + * shortening Phi's and Block inputs. */ -static void apply_result(ir_node *irn, void *ctx) { - node_t *node = get_irn_node(irn); +static void apply_cf(ir_node *block, void *ctx) { + node_t *node = get_irn_node(block); + int i, j, k, n; + ir_node **ins, **in_X; + ir_node *phi, *next; (void) ctx; - if (is_Block(irn)) { - if (irn == get_irg_end_block(current_ir_graph)) { - /* the EndBlock is always reachable even if the analysis - finds out the opposite :-) */ - return; + if (block == get_irg_end_block(current_ir_graph) || + block == get_irg_start_block(current_ir_graph)) { + /* the EndBlock is always reachable even if the analysis + finds out the opposite :-) */ + return; + } + if (node->type.tv == tarval_unreachable) { + /* mark dead blocks */ + set_Block_dead(block); + return; + } + + n = get_Block_n_cfgpreds(block); + + if (n == 1) { + /* only one predecessor combine */ + ir_node *pred = skip_Proj(get_Block_cfgpred(block, 0)); + + if (can_exchange(pred)) + exchange(block, get_nodes_block(pred)); + return; + } + + NEW_ARR_A(ir_node *, in_X, n); + k = 0; + for (i = 0; i < n; ++i) { + ir_node *pred = get_Block_cfgpred(block, i); + node_t *node = get_irn_node(pred); + + if (node->type.tv == tarval_reachable) { + in_X[k++] = pred; } + } + if (k >= n) + return; + + NEW_ARR_A(ir_node *, ins, n); + for (phi = get_Block_phis(block); phi != NULL; phi = next) { + node_t *node = get_irn_node(phi); - if (node->type.tv == tarval_unreachable) { - /* mark dead blocks */ - set_Block_dead(irn); + next = get_Phi_next(phi); + if (is_tarval(node->type.tv) && tarval_is_constant(node->type.tv)) { + /* this Phi is replaced by a constant */ + tarval *tv = node->type.tv; + ir_node *c = new_r_Const(current_ir_graph, block, get_tarval_mode(tv), tv); + + set_irn_node(c, node); + node->node = c; + DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", phi, c)); + exchange(phi, c); + } else { + j = 0; + for (i = 0; i < n; ++i) { + node_t *pred = get_irn_node(get_Block_cfgpred(block, i)); + + if (pred->type.tv == tarval_reachable) { + ins[j++] = get_Phi_pred(phi, i); + } + } + if (j <= 1) { + /* this Phi is replaced by a single predecessor */ + ir_node *s = ins[0]; + + node->node = s; + DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", phi, s)); + exchange(phi, s); + } else { + set_irn_in(phi, j, ins); + } } - } else if (is_End(irn)) { - /* do not touch the End node */ + } + + if (k <= 1) { + /* this Block has only one live predecessor */ + ir_node *pred = skip_Proj(in_X[0]); + + if (can_exchange(pred)) + exchange(block, get_nodes_block(pred)); + } else { + set_irn_in(block, k, in_X); + } +} + +/** + * Post-Walker, apply the analysis results; + */ +static void apply_result(ir_node *irn, void *ctx) { + node_t *node = get_irn_node(irn); + + (void) ctx; + if (is_Block(irn) || is_End(irn) || is_Bad(irn)) { + /* blocks already handled, do not touch the End node */ } else { node_t *block = get_irn_node(get_nodes_block(irn)); if (block->type.tv == tarval_unreachable) { - if (! is_Bad(irn)) { - ir_node *bad = get_irg_bad(current_ir_graph); - - /* here, bad might already have a node, but this can be safely ignored - as long as bad has at least ONE valid node */ - set_irn_node(bad, node); - node->node = bad; - DB((dbg, LEVEL_1, "%+F is unreachable\n", irn)); - exchange(irn, bad); - } + ir_node *bad = get_irg_bad(current_ir_graph); + + /* here, bad might already have a node, but this can be safely ignored + as long as bad has at least ONE valid node */ + set_irn_node(bad, node); + node->node = bad; + DB((dbg, LEVEL_1, "%+F is unreachable\n", irn)); + exchange(irn, bad); + } + else if (node->type.tv == tarval_unreachable) { + ir_node *bad = get_irg_bad(current_ir_graph); + + /* see comment above */ + set_irn_node(bad, node); + node->node = bad; + DB((dbg, LEVEL_1, "%+F is unreachable\n", irn)); + exchange(irn, bad); } else if (get_irn_mode(irn) == mode_X) { - if (node->type.tv == tarval_unreachable) { - ir_node *bad = get_irg_bad(current_ir_graph); - - /* see comment above */ - set_irn_node(bad, node); - node->node = bad; - DB((dbg, LEVEL_1, "%+F is unreachable\n", irn)); - exchange(irn, bad); - } - else if (is_Proj(irn)) { + if (is_Proj(irn)) { /* leave or Jmp */ ir_node *cond = get_Proj_pred(irn); @@ -1529,8 +1746,7 @@ static void apply_result(ir_node *irn, void *ctx) { } } } -} /* static void apply_result(ir_node *irn, void *ctx) { - */ +} /* apply_result */ #define SET(code) op_##code->ops.generic = (op_func)compute_##code @@ -1548,12 +1764,16 @@ static void set_compute_functions(void) { /* set specific functions */ SET(Block); + SET(Unknown); + SET(Bad); SET(Jmp); SET(Phi); SET(Add); SET(Sub); SET(SymConst); + SET(Cmp); SET(Proj); + SET(Confirm); SET(End); } /* set_compute_functions */ @@ -1619,12 +1839,16 @@ void combo(ir_graph *irg) { dump_all_partitions(&env); +#if 0 set_dump_node_vcgattr_hook(dump_partition_hook); dump_ir_block_graph(irg, "-partition"); set_dump_node_vcgattr_hook(NULL); - +#else + (void)dump_partition_hook; +#endif /* apply the result */ + irg_block_walk_graph(irg, NULL, apply_cf, &env); irg_walk_graph(irg, NULL, apply_result, &env); pmap_destroy(env.type2id_map);