#include <assert.h>
#include "iroptimize.h"
-#include "archop.h"
#include "irflag.h"
#include "ircons.h"
#include "list.h"
#include "debug.h"
#include "array_t.h"
#include "error.h"
+#include "irnodeset.h"
#include "tv_t.h"
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;
};
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(). */
unsigned modified:1; /**< Set, if the graph was modified. */
/** 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
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;
}
(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 */
/**
if (is_tarval(pred->type.tv) && tarval_is_all_one(pred->type.tv))
return 0;
break;
- case iro_Min:
- case iro_Max:
- /* all inputs are followers */
- return 1;
default:
assert(!"opcode not implemented yet");
break;
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;
}
int i;
ir_node *block = node->node;
- if (block == get_irg_start_block(current_ir_graph)) {
- /* start block is always reachable */
+ if (block == get_irg_start_block(current_ir_graph) || has_Block_label(block)) {
+ /* start block and labelled blocks are always reachable */
node->type.tv = tarval_reachable;
return;
}
node->type = pred->type;
} /* compute_Confirm */
-/**
- * (Re-)compute the type for a Max.
- *
- * @param node the node
- */
-static void compute_Max(node_t *node) {
- ir_node *op = node->node;
- node_t *l = get_irn_node(get_binop_left(op));
- node_t *r = get_irn_node(get_binop_right(op));
- 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 probably do something */
- if (a.tv == b.tv) {
- /* this case handles SymConsts as well */
- node->type = a;
- } else {
- ir_mode *mode = get_irn_mode(op);
- tarval *tv_min = get_mode_min(mode);
-
- if (a.tv == tv_min)
- node->type = b;
- else if (b.tv == tv_min)
- node->type = a;
- else if (is_tarval(a.tv) && is_tarval(b.tv)) {
- if (tarval_cmp(a.tv, b.tv) & pn_Cmp_Gt)
- node->type.tv = a.tv;
- else
- node->type.tv = b.tv;
- } else {
- node->type.tv = tarval_bad;
- }
- }
- } else if (r->part == l->part) {
- /* both nodes congruent, we can probably do something */
- node->type = a;
- } else {
- node->type.tv = tarval_bottom;
- }
-} /* compute_Max */
-
-/**
- * (Re-)compute the type for a Min.
- *
- * @param node the node
- */
-static void compute_Min(node_t *node) {
- ir_node *op = node->node;
- node_t *l = get_irn_node(get_binop_left(op));
- node_t *r = get_irn_node(get_binop_right(op));
- 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 probably do something */
- if (a.tv == b.tv) {
- /* this case handles SymConsts as well */
- node->type = a;
- } else {
- ir_mode *mode = get_irn_mode(op);
- tarval *tv_max = get_mode_max(mode);
-
- if (a.tv == tv_max)
- node->type = b;
- else if (b.tv == tv_max)
- node->type = a;
- else if (is_tarval(a.tv) && is_tarval(b.tv)) {
- if (tarval_cmp(a.tv, b.tv) & pn_Cmp_Gt)
- node->type.tv = a.tv;
- else
- node->type.tv = b.tv;
- } else {
- node->type.tv = tarval_bad;
- }
- }
- } else if (r->part == l->part) {
- /* both nodes congruent, we can probably do something */
- node->type = a;
- } else {
- node->type.tv = tarval_bottom;
- }
-} /* compute_Min */
-
/**
* (Re-)compute the type for a given node.
*
return node;
} /* identity_Mux */
-/**
- * Calculates the Identity for Min nodes.
- */
-static node_t *identity_Min(node_t *node) {
- ir_node *op = node->node;
- node_t *a = get_irn_node(get_binop_left(op));
- node_t *b = get_irn_node(get_binop_right(op));
- ir_mode *mode = get_irn_mode(op);
- tarval *tv_max;
-
- if (a->part == b->part) {
- /* leader of multiple predecessors */
- return a;
- }
-
- /* works even with NaN */
- tv_max = get_mode_max(mode);
- if (a->type.tv == tv_max)
- return b;
- if (b->type.tv == tv_max)
- return a;
- return node;
-} /* identity_Min */
-
-/**
- * Calculates the Identity for Max nodes.
- */
-static node_t *identity_Max(node_t *node) {
- ir_node *op = node->node;
- node_t *a = get_irn_node(get_binop_left(op));
- node_t *b = get_irn_node(get_binop_right(op));
- ir_mode *mode = get_irn_mode(op);
- tarval *tv_min;
-
- if (a->part == b->part) {
- /* leader of multiple predecessors */
- return a;
- }
-
- /* works even with NaN */
- tv_min = get_mode_min(mode);
- if (a->type.tv == tv_min)
- return b;
- if (b->type.tv == tv_min)
- return a;
- return node;
-} /* identity_Max */
-
/**
* Calculates the Identity for nodes.
*/
return identity_Confirm(node);
case iro_Mux:
return identity_Mux(node);
- case iro_Min:
- return identity_Min(node);
- case iro_Max:
- return identity_Max(node);
default:
return node;
}
* 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
+ * @param pred the control flow exit
+ * @param block the destination block
*/
-static int can_exchange(ir_node *pred) {
- if (is_Start(pred))
+static int can_exchange(ir_node *pred, ir_node *block) {
+ if (is_Start(pred) || has_Block_label(block))
return 0;
else if (is_Jmp(pred))
return 1;
/* only one predecessor combine */
ir_node *pred = skip_Proj(get_Block_cfgpred(block, 0));
- if (can_exchange(pred)) {
+ if (can_exchange(pred, block)) {
ir_node *new_block = get_nodes_block(pred);
DB((dbg, LEVEL_1, "Fuse %+F with %+F\n", block, new_block));
DBG_OPT_COMBO(block, new_block, FS_OPT_COMBO_CF);
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;
/* this Block has only one live predecessor */
ir_node *pred = skip_Proj(in_X[0]);
- if (can_exchange(pred)) {
+ if (can_exchange(pred, block)) {
ir_node *new_block = get_nodes_block(pred);
DBG_OPT_COMBO(block, new_block, FS_OPT_COMBO_CF);
exchange(block, new_block);
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;
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));
+ node_t *block = get_irn_node(get_nodes_block(irn));
if (block->type.tv == tarval_unreachable) {
ir_node *bad = get_irg_bad(current_ir_graph);
*/
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(Return);
SET(End);
SET(Call);
+} /* set_compute_functions */
- if (op_Max != NULL)
- SET(Max);
- if (op_Min != NULL)
- SET(Min);
+/**
+ * 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;
-} /* set_compute_functions */
+ 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.modified = 0;
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;
#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"));
}
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);