#include "debug.h"
#include "array_t.h"
#include "error.h"
+#include "irnodeset.h"
#include "tv_t.h"
/* define this to check the consistency of partitions */
#define CHECK_PARTITIONS
-
-/* allow optimization of non-strict programs */
-#define WITH_UNKNOWN
-
typedef struct node_t node_t;
typedef struct partition_t partition_t;
typedef struct opcode_key_t opcode_key_t;
union {
long proj; /**< For Proj nodes, its proj number */
ir_entity *ent; /**< For Sel Nodes, its entity */
+ int intVal; /**< For Conv/Div Nodes: strict/remainderless */
} u;
};
unsigned on_cprop:1; /**< Set, if this node is on the partition.cprop list. */
unsigned on_fallen:1; /**< Set, if this node is on the fallen list. */
unsigned is_follower:1; /**< Set, if this node is a follower. */
- unsigned by_all_const:1; /**< Set, if this node was once evaluated by all constants. */
unsigned flagged:2; /**< 2 Bits, set if this node was visited by race 1 or 2. */
};
partition_t *initial; /**< The initial partition. */
set *opcode2id_map; /**< The opcodeMode->id map. */
pmap *type2id_map; /**< The type->id map. */
+ ir_node **kept_memory; /**< Array of memory nodes that must be kept. */
int end_idx; /**< -1 for local and 0 for global congruences. */
int lambda_input; /**< Captured argument for lambda_partition(). */
- char modified; /**< Set, if the graph was modified. */
- char commutative; /**< Set, if commutation nodes should be handled specially. */
+ unsigned modified:1; /**< Set, if the graph was modified. */
+ unsigned unopt_cf:1; /**< If set, control flow is not optimized due to Unknown. */
+ /* options driving the optimization */
+ unsigned commutative:1; /**< Set, if commutation nodes should be handled specially. */
+ unsigned opt_unknown:1; /**< Set, if non-strict programs should be optimized. */
#ifdef DEBUG_libfirm
partition_t *dbg_list; /**< List of all partitions. */
#endif
/** Type of the what function. */
typedef void *(*what_func)(const node_t *node, environment_t *env);
-#define get_irn_node(follower) ((node_t *)get_irn_link(follower))
-#define set_irn_node(follower, node) set_irn_link(follower, node)
+#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
/** Next partition number. */
DEBUG_ONLY(static unsigned part_nr = 0);
-/** The tarval returned by Unknown nodes. */
-#ifdef WITH_UNKNOWN
-#define tarval_UNKNOWN tarval_top
-#else
-#define tarval_UNKNOWN tarval_bad
-#endif
+/** The tarval returned by Unknown nodes: set to either tarval_bad OR tarval_top. */
+static tarval *tarval_UNKNOWN;
/* forward */
static node_t *identity(node_t *node);
case iro_Sel:
key.u.ent = get_Sel_entity(irn);
break;
+ case iro_Conv:
+ key.u.intVal = get_Conv_strict(irn);
+ break;
+ case iro_Div:
+ key.u.intVal = is_Div_remainderless(irn);
+ break;
default:
break;
}
case iro_Sel:
assert(key.u.ent == get_Sel_entity(irn));
break;
+ case iro_Conv:
+ assert(key.u.intVal == get_Conv_strict(irn));
+ break;
+ case iro_Div:
+ assert(key.u.intVal == is_Div_remainderless(irn));
+ break;
default:
break;
}
/**
* Verify that a type transition is monotone
*/
-static void do_verify_type(const lattice_elem_t old_type, node_t *node) {
+static void verify_type(const lattice_elem_t old_type, node_t *node) {
if (old_type.tv == node->type.tv) {
/* no change */
return;
panic("combo: wrong translation from %+F to %+F on node %+F", old_type, node->type, node->node);
} /* verify_type */
-#define decl_verify(node) lattice_elem_t old_type = (node)->type;
-#define verify_type(node) do_verify_type(old_type, node)
#else
-#define decl_verify(node) (void)0;
-#define verify_type(node)
+#define verify_type(old_type, node)
#endif
/**
(void) size;
return o1->code != o2->code || o1->mode != o2->mode ||
o1->arity != o2->arity ||
- o1->u.proj != o2->u.proj || o1->u.ent != o2->u.ent;
+ o1->u.proj != o2->u.proj || o1->u.ent != o2->u.ent ||
+ o1->u.intVal != o2->u.intVal;
} /* cmp_opcode */
/**
node->on_cprop = 0;
node->on_fallen = 0;
node->is_follower = 0;
- node->by_all_const = 0;
node->flagged = 0;
set_irn_node(irn, node);
/* Add y to y.partition.cprop. */
if (y->on_cprop == 0) {
partition_t *Y = y->part;
+ ir_node *irn = y->node;
- /* place Conds and its Proj nodes on the cprop_X list */
- if (is_Cond(skip_Proj(y->node)))
+ /* place Conds and all its Projs on the cprop_X list */
+ if (is_Cond(skip_Proj(irn)))
list_add_tail(&y->cprop_list, &Y->cprop_X);
else
list_add_tail(&y->cprop_list, &Y->cprop);
/**
* Collect commutative nodes to the touched list.
*
+ * @param X the partition of the list
* @param list the list which contains the nodes that must be evaluated
* @param env the environment
*/
-static void collect_commutative_touched(list_head *list, environment_t *env) {
+static void collect_commutative_touched(partition_t *X, list_head *list, environment_t *env) {
+ int first = 1;
+ int both_input = 0;
node_t *x, *y;
list_for_each_entry(node_t, x, list, node_list) {
/* Partitions of constants should not be split simply because their Nodes have unequal
functions or incongruent inputs. */
if (type_is_neither_top_nor_const(y->type)) {
- add_to_touched(y, env);
+ int other_idx = edge->pos ^ 1;
+ node_t *other = get_irn_node(get_irn_n(succ, other_idx));
+ int equal = X == other->part;
+
+ /*
+ * Note: op(a, a) is NOT congruent to op(a, b).
+ * So, either all touch nodes must have both inputs congruent,
+ * or not. We decide this by the first occurred node.
+ */
+ if (first) {
+ first = 0;
+ both_input = equal;
+ }
+ if (both_input == equal)
+ add_to_touched(y, env);
}
}
}
/* empty the touched set: already done, just clear the list */
env->touched = NULL;
- collect_commutative_touched(&X->Leader, env);
- collect_commutative_touched(&X->Follower, env);
+ collect_commutative_touched(X, &X->Leader, env);
+ collect_commutative_touched(X, &X->Follower, env);
for (Z = env->touched; Z != NULL; Z = N) {
node_t *e;
case iro_Sel:
key.u.ent = get_Sel_entity(irn);
break;
+ case iro_Conv:
+ key.u.intVal = get_Conv_strict(irn);
+ break;
+ case iro_Div:
+ key.u.intVal = is_Div_remainderless(irn);
+ break;
default:
break;
}
static void default_compute(node_t *node) {
int i;
ir_node *irn = node->node;
- node_t *block = get_irn_node(get_nodes_block(irn));
-
- 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 */
for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
node->type.tv = tarval_reachable;
} /* compute_End */
+/**
+ * (Re-)compute the type for a Call.
+ *
+ * @param node the node
+ */
+static void compute_Call(node_t *node) {
+ /*
+ * A Call computes always bottom, even if it has Unknown
+ * predecessors.
+ */
+ node->type.tv = tarval_bottom;
+} /* compute_Call */
+
/**
* (Re-)compute the type for a SymConst node.
*
} else {
node->type.tv = tarval_bottom;
}
- node->by_all_const = 1;
} else if (r->part == l->part &&
(!mode_is_float(get_irn_mode(l->node)))) {
/*
this breaks AND we get from the argument partitions a different
result, switch to bottom.
This happens because initially all nodes are in the same partition ... */
- if (node->by_all_const && node->type.tv != tv)
+ if (node->type.tv != tv)
tv = tarval_bottom;
node->type.tv = tv;
} else {
} else {
node->type.tv = tarval_bottom;
}
- node->by_all_const = 1;
} else if (r->part == l->part) {
ir_mode *mode = get_irn_mode(eor);
tv = get_mode_null(mode);
this breaks AND we get from the argument partitions a different
result, switch to bottom.
This happens because initially all nodes are in the same partition ... */
- if (node->by_all_const && node->type.tv != tv)
+ if (node->type.tv != tv)
tv = tarval_bottom;
node->type.tv = tv;
} else {
node->type.tv = tarval_undefined;
} else if (is_con(a) && is_con(b)) {
default_compute(node);
- node->by_all_const = 1;
} else if (r->part == l->part &&
(!mode_is_float(get_irn_mode(l->node)) || pnc == pn_Cmp_Lt || pnc == pn_Cmp_Gt)) {
/*
this breaks AND we get from the argument partitions a different
result, switch to bottom.
This happens because initially all nodes are in the same partition ... */
- if (node->by_all_const && node->type.tv != tv)
+ if (node->type.tv != tv)
tv = tarval_bottom;
node->type.tv = tv;
} else {
*
* Note that this even happens with Click's original algorithm, if
* Cmp(x, 0) is evaluated to True first and later changed to False
- * if x was Top first tiome and later Const ...
+ * if x was Top first and later changed to a Const ...
* It is unclear how Click solved that problem ...
+ *
+ * However, in rare cases even this does not help, if a Top reaches
+ * a compare through a Phi, than Proj(Cond) is evaluated changing
+ * the type of the Phi to something other.
+ * So, we take the last resort and bind the type to R once
+ * it is calculated.
+ *
+ * (This might be even the way Click works around the whole problem).
+ *
+ * Finally, we may miss some optimization possibilities due to this:
+ *
+ * x = phi(Top, y)
+ * if (x == 0)
+ *
+ * If Top reaches the if first, than we decide for != here.
+ * If y later is evaluated to 0, we cannot revert this decision
+ * and must live with both outputs enabled. If this happens,
+ * we get an unresolved if (true) in the code ...
+ *
+ * In Click's version where this decision is done at the Cmp,
+ * the Cmp is NOT optimized away than (if y evaluated to 1
+ * for instance) and we get a if (1 == 0) here ...
+ *
+ * Both solutions are suboptimal.
+ * At least, we could easily detect this problem and run
+ * cf_opt() (or even combo) again :-(
*/
+ if (node->type.tv == tarval_reachable)
+ return;
+
if (get_irn_mode(sel) == mode_b) {
/* an IF */
if (pnc == pn_Cond_true) {
node->type.tv = tarval_reachable;
} else {
assert(selector->type.tv == tarval_top);
- /* any condition based on Top is "!=" */
- node->type.tv = tarval_unreachable;
+ if (tarval_UNKNOWN == tarval_top) {
+ /* any condition based on Top is "!=" */
+ node->type.tv = tarval_unreachable;
+ } else {
+ node->type.tv = tarval_unreachable;
+ }
}
} else {
assert(pnc == pn_Cond_false);
node->type.tv = tarval_reachable;
} else {
assert(selector->type.tv == tarval_top);
- /* any condition based on Top is "!=" */
- node->type.tv = tarval_reachable;
+ if (tarval_UNKNOWN == tarval_top) {
+ /* any condition based on Top is "!=" */
+ node->type.tv = tarval_reachable;
+ } else {
+ node->type.tv = tarval_unreachable;
+ }
}
}
} else {
if (selector->type.tv == tarval_bottom) {
node->type.tv = tarval_reachable;
} else if (selector->type.tv == tarval_top) {
- if (pnc == get_Cond_defaultProj(cond)) {
+ if (tarval_UNKNOWN == tarval_top &&
+ pnc == get_Cond_defaultProj(cond)) {
/* a switch based of Top is always "default" */
node->type.tv = tarval_reachable;
- } else
+ } else {
node->type.tv = tarval_unreachable;
+ }
} else {
long value = get_tarval_long(selector->type.tv);
if (pnc == get_Cond_defaultProj(cond)) {
static void compute(node_t *node) {
ir_node *irn = node->node;
compute_func func;
- decl_verify(node);
+
+#ifndef VERIFY_MONOTONE
+ /*
+ * Once a node reaches bottom, the type cannot fall further
+ * in the lattice and we can stop computation.
+ * Do not take this exit if the monotony verifier is
+ * enabled to catch errors.
+ */
+ if (node->type.tv == tarval_bottom)
+ return;
+#endif
if (is_no_Block(irn)) {
/* for pinned nodes, check its control input */
if (block->type.tv == tarval_unreachable) {
node->type.tv = tarval_top;
- goto end;
+ return;
}
}
}
func = (compute_func)node->node->op->ops.generic;
if (func != NULL)
func(node);
-end:
- verify_type(node);
} /* compute */
/*
compute(x);
if (x->type.tv != old_type.tv) {
DB((dbg, LEVEL_2, "node %+F has changed type from %+F to %+F\n", x->node, old_type, x->type));
+ verify_type(old_type, x);
if (x->on_fallen == 0) {
/* Add x to fallen. Nodes might fall from T -> const -> _|_, so check that they are
return node->node;
} /* get_leader */
+/**
+ * Returns non-zero if a mode_T node has only one reachable output.
+ */
+static int only_one_reachable_proj(ir_node *n) {
+ int i, k = 0;
+
+ for (i = get_irn_n_outs(n) - 1; i >= 0; --i) {
+ ir_node *proj = get_irn_out(n, 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;
+} /* only_one_reachable_proj */
+
/**
* Return non-zero if the control flow predecessor node pred
* is the only reachable control flow exit of its block.
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 only_one_reachable_proj(pred);
}
return 0;
} /* can_exchange */
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);
+ ir_node *c = new_Const(tv);
set_irn_node(c, node);
node->node = c;
static void exchange_leader(ir_node *irn, ir_node *leader) {
ir_mode *mode = get_irn_mode(irn);
if (mode != get_irn_mode(leader)) {
- /* The conv is a no-op, so we are fre to place in
+ /* The conv is a no-op, so we are free to place it
* either in the block of the leader OR in irn's block.
* Probably placing it into leaders block might reduce
* the number of Conv due to CSE. */
leader = new_rd_Conv(dbg, current_ir_graph, block, leader, mode);
}
exchange(irn, leader);
-}
+} /* exchange_leader */
+
+/**
+ * Check, if all users of a mode_M node are dead. Use
+ * the Def-Use edges for this purpose, as they still
+ * reflect the situation.
+ */
+static int all_users_are_dead(const ir_node *irn) {
+ int i, n = get_irn_n_outs(irn);
+
+ for (i = 1; i <= n; ++i) {
+ const ir_node *succ = irn->out[i].use;
+ const node_t *block = get_irn_node(get_nodes_block(succ));
+ const node_t *node;
+
+ if (block->type.tv == tarval_unreachable) {
+ /* block is unreachable */
+ continue;
+ }
+ node = get_irn_node(succ);
+ if (node->type.tv != tarval_top) {
+ /* found a reachable user */
+ return 0;
+ }
+ }
+ /* all users are unreachable */
+ return 1;
+} /* all_user_are_dead */
+
+/**
+ * Walker: Find reachable mode_M nodes that have only
+ * unreachable users. These nodes must be kept later.
+ */
+static void find_kept_memory(ir_node *irn, void *ctx) {
+ environment_t *env = ctx;
+ node_t *node, *block;
+
+ if (get_irn_mode(irn) != mode_M)
+ return;
+
+ block = get_irn_node(get_nodes_block(irn));
+ if (block->type.tv == tarval_unreachable)
+ return;
+
+ node = get_irn_node(irn);
+ if (node->type.tv == tarval_top)
+ return;
+
+ /* ok, we found a live memory node. */
+ if (all_users_are_dead(irn)) {
+ DB((dbg, LEVEL_1, "%+F must be kept\n", irn));
+ ARR_APP1(ir_node *, env->kept_memory, irn);
+ }
+} /* find_kept_memory */
/**
* Post-Walker, apply the analysis results;
DB((dbg, LEVEL_1, "%+F is unreachable\n", irn));
exchange(irn, bad);
env->modified = 1;
- }
- else if (node->type.tv == tarval_top) {
- /* don't kick away Unknown's, they might be still needed */
- if (! is_Unknown(irn)) {
- ir_mode *mode = get_irn_mode(irn);
- ir_node *unk = new_r_Unknown(current_ir_graph, mode);
+ } else if (node->type.tv == tarval_top) {
+ ir_mode *mode = get_irn_mode(irn);
+
+ if (mode == mode_M) {
+ /* never kill a mode_M node */
+ if (is_Proj(irn)) {
+ ir_node *pred = get_Proj_pred(irn);
+ node_t *pnode = get_irn_node(pred);
+
+ if (pnode->type.tv == tarval_top) {
+ /* skip the predecessor */
+ ir_node *mem = get_memop_mem(pred);
+ node->node = mem;
+ DB((dbg, LEVEL_1, "%+F computes Top, replaced by %+F\n", irn, mem));
+ exchange(irn, mem);
+ env->modified = 1;
+ }
+ }
+ /* leave other nodes, especially PhiM */
+ } else if (mode == mode_T) {
+ /* Do not kill mode_T nodes, kill their Projs */
+ } else if (! is_Unknown(irn)) {
+ /* don't kick away Unknown's, they might be still needed */
+ ir_node *unk = new_r_Unknown(current_ir_graph, mode);
/* control flow should already be handled at apply_cf() */
assert(mode != mode_X);
ir_node *cond = get_Proj_pred(irn);
if (is_Cond(cond)) {
- node_t *sel = get_irn_node(get_Cond_selector(cond));
-
- if (is_tarval(sel->type.tv) && tarval_is_constant(sel->type.tv)) {
- /* Cond selector is a constant and the Proj is reachable, make a Jmp */
- ir_node *jmp = new_r_Jmp(current_ir_graph, block->node);
+ if (only_one_reachable_proj(cond)) {
+ ir_node *jmp = new_r_Jmp(current_ir_graph, block->node);
set_irn_node(jmp, node);
node->node = jmp;
DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", irn, jmp));
DBG_OPT_COMBO(irn, jmp, FS_OPT_COMBO_CF);
exchange(irn, jmp);
env->modified = 1;
+ } else {
+ node_t *sel = get_irn_node(get_Cond_selector(cond));
+ tarval *tv = sel->type.tv;
+
+ if (is_tarval(tv) && tarval_is_constant(tv)) {
+ /* The selector is a constant, but more
+ * than one output is active: An unoptimized
+ * case found. */
+ env->unopt_cf = 1;
+ }
}
}
}
*/
if (! is_Const(irn) && get_irn_mode(irn) != mode_T) {
/* can be replaced by a constant */
- ir_node *c = new_r_Const(current_ir_graph, block->node, get_tarval_mode(tv), tv);
+ ir_node *c = new_Const(tv);
set_irn_node(c, node);
node->node = c;
DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", irn, c));
SET(Confirm);
SET(Return);
SET(End);
+ SET(Call);
if (op_Max != NULL)
SET(Max);
if (op_Min != NULL)
SET(Min);
-
} /* set_compute_functions */
+/**
+ * Add memory keeps.
+ */
+static void add_memory_keeps(ir_node **kept_memory, int len) {
+ ir_node *end = get_irg_end(current_ir_graph);
+ int i;
+ ir_nodeset_t set;
+
+ ir_nodeset_init(&set);
+
+ /* check, if those nodes are already kept */
+ for (i = get_End_n_keepalives(end) - 1; i >= 0; --i)
+ ir_nodeset_insert(&set, get_End_keepalive(end, i));
+
+ for (i = len - 1; i >= 0; --i) {
+ ir_node *ka = kept_memory[i];
+
+ if (! ir_nodeset_contains(&set, ka)) {
+ add_End_keepalive(end, ka);
+ }
+ }
+ ir_nodeset_destroy(&set);
+} /* add_memory_keeps */
+
void combo(ir_graph *irg) {
environment_t env;
ir_node *initial_bl;
node_t *start;
ir_graph *rem = current_ir_graph;
+ int len;
current_ir_graph = irg;
#endif
env.opcode2id_map = new_set(cmp_opcode, iro_Last * 4);
env.type2id_map = pmap_create();
+ env.kept_memory = NEW_ARR_F(ir_node *, 0);
env.end_idx = get_opt_global_cse() ? 0 : -1;
env.lambda_input = 0;
- env.commutative = 1;
env.modified = 0;
+ env.unopt_cf = 0;
+ /* options driving the optimization */
+ env.commutative = 1;
+ env.opt_unknown = 1;
assure_irg_outs(irg);
assure_cf_loop(irg);
set_compute_functions();
DEBUG_ONLY(part_nr = 0);
- ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
+ ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
+
+ if (env.opt_unknown)
+ tarval_UNKNOWN = tarval_top;
+ else
+ tarval_UNKNOWN = tarval_bad;
/* create the initial partition and place it on the work list */
env.initial = new_partition(&env);
#endif
/* apply the result */
+
+ /* check, which nodes must be kept */
+ irg_walk_graph(irg, NULL, find_kept_memory, &env);
+
+ /* kill unreachable control flow */
irg_block_walk_graph(irg, NULL, apply_cf, &env);
/* Kill keep-alives of dead blocks: this speeds up apply_result()
* and fixes assertion because dead cf to dead blocks is NOT removed by
apply_end(get_irg_end(irg), &env);
irg_walk_graph(irg, NULL, apply_result, &env);
+ len = ARR_LEN(env.kept_memory);
+ if (len > 0)
+ add_memory_keeps(env.kept_memory, len);
+
+ if (env.unopt_cf) {
+ DB((dbg, LEVEL_1, "Unoptimized Control Flow left"));
+ }
+
if (env.modified) {
/* control flow might changed */
set_irg_outs_inconsistent(irg);
set_irg_loopinfo_inconsistent(irg);
}
- ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
+ ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
/* remove the partition hook */
DEBUG_ONLY(set_dump_node_vcgattr_hook(NULL));
+ DEL_ARR_F(env.kept_memory);
pmap_destroy(env.type2id_map);
del_set(env.opcode2id_map);
obstack_free(&env.obst, NULL);
projects / libfirm / blobdiff