* - supports all Firm direct (by a data edge) identities except Mux
* (Mux can be a 2-input or 1-input identity, only 2-input is implemented yet)
* - supports Confirm nodes (handle them like Copies but do NOT remove them)
+ * - let Cmp nodes calculate Top like all othe data nodes: this would let
+ * Mux nodes to calculate Unknown instead of taking the true result
+ * - let Cond(Top) always select FALSE/default: This is tricky. Nodes are only reavaluated
+ * IFF the predecessor changed its type. Because nodes are initialized with Top
+ * this never happens, let all Proj(Cond) be unreachable.
+ * We avoid this condition by the same way we work around Phi: whenever a Block
+ * node is placed on the list, place its Cond nodes (and because they are Tuple
+ * all its Proj-nodes either on the cprop list)
+ * Especially, this changes the meaning of Click's example:
+ *
+ * int main() {
+ * int x;
+ *
+ * if (x == 2)
+ * printf("x == 2\n");
+ * if (x == 3)
+ * printf("x == 3\n");
+ * }
+ *
+ * Would print:
+ * x == 2
+ * x == 3
+ *
+ * using Click's version while is silent with our.
* - support for global congruences is implemented but not tested yet
*
* Note further that we use the terminology from Click's work here, which is different
* in some cases from Firm terminology. Especially, Click's type is a
* Firm tarval/entity, nevertheless we call it type here for "maximum compatibility".
*/
-#ifdef HAVE_CONFIG_H
-# include "config.h"
-#endif
+#include "config.h"
#include <assert.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;
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. */
+ node_t *cond; /**< if this is a Block node, points to its Cond if any */
};
/**
pmap *type2id_map; /**< The type->id map. */
int end_idx; /**< -1 for local and 0 for global congruences. */
int lambda_input; /**< Captured argument for lambda_partition(). */
- char nonstd_cond; /**< Set, if a Condb note has a non-Cmp predecessor. */
char modified; /**< Set, if the graph was modified. */
char commutative; /**< Set, if commutation nodes should be handled specially. */
#ifdef DEBUG_libfirm
}
first = 0;
} else {
- assert(key.code == get_irn_opcode(irn));
- assert(key.mode == get_irn_mode(irn));
- assert(key.arity == get_irn_arity(irn));
+ assert(key.code == get_irn_opcode(irn));
+ assert(key.mode == get_irn_mode(irn));
+ assert(key.arity == get_irn_arity(irn));
switch (get_irn_opcode(irn)) {
case iro_Proj:
} /* check_opcode */
static void check_all_partitions(environment_t *env) {
+#ifdef DEBUG_libfirm
partition_t *P;
node_t *node;
-#ifdef DEBUG_libfirm
for (P = env->dbg_list; P != NULL; P = P->dbg_next) {
check_partition(P);
if (! P->type_is_T_or_C)
#endif /* CHECK_PARTITIONS */
#ifdef DEBUG_libfirm
-static INLINE lattice_elem_t get_partition_type(const partition_t *X);
+static inline lattice_elem_t get_partition_type(const partition_t *X);
/**
* Dump partition to output.
DB((dbg, LEVEL_2, "\n}\n"));
} /* dump_split_list */
+/**
+ * Dump partition and type for a node.
+ */
+static int dump_partition_hook(FILE *F, ir_node *n, ir_node *local) {
+ ir_node *irn = local != NULL ? local : n;
+ node_t *node = get_irn_node(irn);
+
+ ir_fprintf(F, "info2 : \"partition %u type %+F\"\n", node->part->nr, node->type);
+ return 1;
+} /* dump_partition_hook */
+
#else
#define dump_partition(msg, part)
#define dump_race_list(msg, list)
*
* @return the associated type of this node
*/
-static INLINE lattice_elem_t get_node_type(const ir_node *irn) {
+static inline lattice_elem_t get_node_type(const ir_node *irn) {
return get_irn_node(irn)->type;
} /* get_node_type */
*
* @return the associated type of this node
*/
-static INLINE tarval *get_node_tarval(const ir_node *irn) {
+static inline tarval *get_node_tarval(const ir_node *irn) {
lattice_elem_t type = get_node_type(irn);
if (is_tarval(type.tv))
/**
* Add a partition to the worklist.
*/
-static INLINE void add_to_worklist(partition_t *X, environment_t *env) {
+static inline void add_to_worklist(partition_t *X, environment_t *env) {
assert(X->on_worklist == 0);
DB((dbg, LEVEL_2, "Adding part%d to worklist\n", X->nr));
X->wl_next = env->worklist;
*
* @return a newly allocated partition
*/
-static INLINE partition_t *new_partition(environment_t *env) {
+static inline partition_t *new_partition(environment_t *env) {
partition_t *part = obstack_alloc(&env->obst, sizeof(*part));
INIT_LIST_HEAD(&part->Leader);
/**
* Get the first node from a partition.
*/
-static INLINE node_t *get_first_node(const partition_t *X) {
+static inline node_t *get_first_node(const partition_t *X) {
return list_entry(X->Leader.next, node_t, node_list);
} /* get_first_node */
*
* @return the type of the first element of the partition
*/
-static INLINE lattice_elem_t get_partition_type(const partition_t *X) {
+static inline lattice_elem_t get_partition_type(const partition_t *X) {
const node_t *first = get_first_node(X);
return first->type;
} /* get_partition_type */
node->is_follower = 0;
node->by_all_const = 0;
node->flagged = 0;
+ node->cond = NULL;
set_irn_node(irn, node);
list_add_tail(&node->node_list, &part->Leader);
if (is_Phi(irn)) {
add_Block_phi(get_nodes_block(irn), irn);
} else if (is_Cond(irn)) {
- /* check if all Cond's have a Cmp predecessor. */
- if (get_irn_mode(irn) == mode_b && !is_Cmp(skip_Proj(get_Cond_selector(irn))))
- env->nonstd_cond = 1;
+ node_t *block = get_irn_node(get_nodes_block(irn));
+
+ /* link every block with its Cond node if any */
+ block->cond = node;
}
} /* create_initial_partitions */
* @param y a node
* @param env the environment
*/
-static INLINE void add_to_touched(node_t *y, environment_t *env) {
+static inline void add_to_touched(node_t *y, environment_t *env) {
if (y->on_touched == 0) {
partition_t *part = y->part;
node_t *p = get_irn_node(phi);
add_to_cprop(p, env);
}
+ /* same for Conds: they must be re-evaluated due to the way we handle Top */
+ if (y->cond != NULL)
+ add_to_cprop(y->cond, env);
}
} /* add_to_cprop */
partition_t *X = *pX;
partition_t *X_prime;
list_head tmp;
- step_env env1, env2, *winner;
+ step_env senv[2];
node_t *g, *h, *node, *t;
- int max_input, transitions;
+ int max_input, transitions, winner, shf;
unsigned n;
DEBUG_ONLY(static int run = 0;)
/* restore X.Leader */
list_splice(&tmp, &X->Leader);
- env1.initial = g;
- env1.unwalked = NULL;
- env1.walked = NULL;
- env1.index = 0;
- env1.side = 1;
+ senv[0].initial = g;
+ senv[0].unwalked = NULL;
+ senv[0].walked = NULL;
+ senv[0].index = 0;
+ senv[0].side = 1;
- env2.initial = h;
- env2.unwalked = NULL;
- env2.walked = NULL;
- env2.index = 0;
- env2.side = 2;
+ senv[1].initial = h;
+ senv[1].unwalked = NULL;
+ senv[1].walked = NULL;
+ senv[1].index = 0;
+ senv[1].side = 2;
+ /*
+ * Some informations on the race that are not stated clearly in Click's
+ * thesis.
+ * 1) A follower stays on the side that reach him first.
+ * 2) If the other side reches a follower, if will be converted to
+ * a leader. /This must be done after the race is over, else the
+ * edges we are iterating on are renumbered./
+ * 3) /New leader might end up on both sides./
+ * 4) /If one side ends up with new Leaders, we must ensure that
+ * they can split out by opcode, hence we have to put _every_
+ * partition with new Leader nodes on the cprop list, as
+ * opcode splitting is done by split_by() at the end of
+ * constant propagation./
+ */
for (;;) {
- if (step(&env1)) {
- winner = &env1;
+ if (step(&senv[0])) {
+ winner = 0;
break;
}
- if (step(&env2)) {
- winner = &env2;
+ if (step(&senv[1])) {
+ winner = 1;
break;
}
}
- assert(winner->initial == NULL);
- assert(winner->unwalked == NULL);
+ assert(senv[winner].initial == NULL);
+ assert(senv[winner].unwalked == NULL);
/* clear flags from walked/unwalked */
- transitions = clear_flags(env1.unwalked);
- transitions |= clear_flags(env1.walked);
- transitions |= clear_flags(env2.unwalked);
- transitions |= clear_flags(env2.walked);
+ shf = winner;
+ transitions = clear_flags(senv[0].unwalked) << shf;
+ transitions |= clear_flags(senv[0].walked) << shf;
+ shf ^= 1;
+ transitions |= clear_flags(senv[1].unwalked) << shf;
+ transitions |= clear_flags(senv[1].walked) << shf;
- dump_race_list("winner ", winner->walked);
+ dump_race_list("winner ", senv[winner].walked);
/* Move walked_{winner} to a new partition, X'. */
X_prime = new_partition(env);
max_input = 0;
n = 0;
- for (node = winner->walked; node != NULL; node = node->race_next) {
+ for (node = senv[winner].walked; node != NULL; node = node->race_next) {
list_del(&node->node_list);
node->part = X_prime;
if (node->is_follower) {
list_for_each_entry_safe(node_t, node, t, &X_prime->Follower, node_list) {
if (identity(node) == node) {
follower_to_leader(node);
- transitions = 1;
+ transitions |= 1;
}
}
* If there where follower to leader transitions, ensure that the nodes
* can be split out if necessary.
*/
- if (transitions) {
- /* place partitions on the cprop list */
+ if (transitions & 1) {
+ /* place winner partition on the cprop list */
if (X_prime->on_cprop == 0) {
X_prime->cprop_next = env->cprop;
env->cprop = X_prime;
X_prime->on_cprop = 1;
}
}
+ if (transitions & 2) {
+ /* place other partition on the cprop list */
+ if (X->on_cprop == 0) {
+ X->cprop_next = env->cprop;
+ env->cprop = X;
+ X->on_cprop = 1;
+ }
+ }
dump_partition("Now ", X);
dump_partition("Created new ", X_prime);
/* we have to ensure that the partition containing g is returned */
- if (winner == &env2) {
+ if (winner != 0) {
*pX = X_prime;
return X;
}
} /* lambda_commutative_partition */
/**
- * Returns true if a type is a constant.
+ * Returns true if a type is a constant (and NOT Top
+ * or Bottom).
*/
static int is_con(const lattice_elem_t type) {
/* be conservative */
node->type = block->type;
} /* compute_Jmp */
+/**
+ * (Re-)compute the type for the Return node.
+ *
+ * @param node the node
+ */
+static void compute_Return(node_t *node) {
+ /* The Return node is NOT dead if it is in a reachable block.
+ * This is already checked in compute(). so we can return
+ * Reachable here. */
+ node->type.tv = tarval_reachable;
+} /* compute_Return */
+
/**
* (Re-)compute the type for the End node.
*
static void compute_End(node_t *node) {
/* the End node is NOT dead of course */
node->type.tv = tarval_reachable;
-}
+} /* compute_End */
/**
* (Re-)compute the type for a SymConst node.
lattice_elem_t b = r->type;
if (a.tv == tarval_top || b.tv == tarval_top) {
-#ifdef WITH_UNKNOWN
- /*
- * Top is congruent to any other value, we can
- * calculate the compare result.
- */
- node->type.tv = tarval_b_true;
-#else
node->type.tv = tarval_top;
-#endif
- } else if (is_con(a) && is_con(b)) {
- /* both nodes are constants, we can probably 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 if (is_con(a) && is_con(b)) {
+ /* both nodes are constants, we can probably do something */
+ node->type.tv = tarval_b_true;
} else {
node->type.tv = tarval_bottom;
}
-} /* compute_Proj_Cmp */
+} /* compute_Cmp */
/**
* (Re-)compute the type for a Proj(Cmp).
tarval *tv;
if (a.tv == tarval_top || b.tv == tarval_top) {
-#ifdef WITH_UNKNOWN
- /* see above */
- tv = new_tarval_from_long((pnc & pn_Cmp_Eq) ^ pn_Cmp_Eq, mode_b);
- goto not_equal;
-#else
- node->type.tv = tarval_top;
-#endif
+ node->type.tv = tarval_undefined;
} else if (is_con(a) && is_con(b)) {
default_compute(node);
node->by_all_const = 1;
* BEWARE: a == a is NOT always True for floating Point values, as
* NaN != NaN is defined, so we must check this here.
*/
- tv = new_tarval_from_long(pnc & pn_Cmp_Eq, mode_b);
-#ifdef WITH_UNKNOWN
-not_equal:
-#endif
+ tv = pnc & pn_Cmp_Eq ? tarval_b_true: tarval_b_false;
/* if the node was ONCE evaluated by all constants, but now
this breaks AND we get from the argument partitions a different
node->type.tv = tarval_reachable;
} else {
assert(selector->type.tv == tarval_top);
+ /* any condition based on Top is "!=" */
node->type.tv = tarval_unreachable;
}
} else {
node->type.tv = tarval_reachable;
} else {
assert(selector->type.tv == tarval_top);
- node->type.tv = tarval_unreachable;
+ /* any condition based on Top is "!=" */
+ node->type.tv = tarval_reachable;
}
}
} else {
if (selector->type.tv == tarval_bottom) {
node->type.tv = tarval_reachable;
} else if (selector->type.tv == tarval_top) {
- node->type.tv = tarval_unreachable;
+ if (pnc == get_Cond_defaultProj(cond)) {
+ /* a switch based of Top is always "default" */
+ node->type.tv = tarval_reachable;
+ } else
+ node->type.tv = tarval_unreachable;
} else {
long value = get_tarval_long(selector->type.tv);
if (pnc == get_Cond_defaultProj(cond)) {
node->type.tv = tarval_top;
return;
}
- if (get_irn_node(pred)->type.tv == tarval_top) {
+ if (get_irn_node(pred)->type.tv == tarval_top && !is_Cond(pred)) {
/* if the predecessor is Top, its Proj follow */
node->type.tv = tarval_top;
return;
* @param node the node
*/
static void compute(node_t *node) {
+ ir_node *irn = node->node;
compute_func func;
- if (is_no_Block(node->node)) {
- node_t *block = get_irn_node(get_nodes_block(node->node));
+ if (is_no_Block(irn)) {
+ /* for pinned nodes, check its control input */
+ if (get_irn_pinned(skip_Proj(irn)) == op_pin_state_pinned) {
+ node_t *block = get_irn_node(get_nodes_block(irn));
- if (block->type.tv == tarval_unreachable) {
- node->type.tv = tarval_top;
- return;
+ if (block->type.tv == tarval_unreachable) {
+ node->type.tv = tarval_top;
+ return;
+ }
}
}
}
} /* apply_cf */
+/**
+ * Exchange a node by its leader.
+ * Beware: in rare cases the mode might be wrong here, for instance
+ * AddP(x, NULL) is a follower of x, but with different mode.
+ * Fix it here.
+ */
+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
+ * 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. */
+ ir_node *block = get_nodes_block(leader);
+ dbg_info *dbg = get_irn_dbg_info(irn);
+
+ leader = new_rd_Conv(dbg, current_ir_graph, block, leader, mode);
+ }
+ exchange(irn, leader);
+}
+
/**
* Post-Walker, apply the analysis results;
*/
node->node = c;
DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", irn, c));
DBG_OPT_COMBO(irn, c, FS_OPT_COMBO_CONST);
- exchange(irn, c);
+ exchange_leader(irn, c);
env->modified = 1;
}
} else if (is_entity(node->type.sym.entity_p)) {
DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", irn, symc));
DBG_OPT_COMBO(irn, symc, FS_OPT_COMBO_CONST);
- exchange(irn, symc);
+ exchange_leader(irn, symc);
env->modified = 1;
}
} else if (is_Confirm(irn)) {
ir_node *leader = get_leader(node);
if (leader != irn) {
- DB((dbg, LEVEL_1, "%+F from part%d is replaced by %+F\n", irn, node->part->nr, leader));
- if (node->is_follower)
- DBG_OPT_COMBO(irn, leader, FS_OPT_COMBO_FOLLOWER);
- else
- DBG_OPT_COMBO(irn, leader, FS_OPT_COMBO_CONGRUENT);
- exchange(irn, leader);
- env->modified = 1;
+ int non_strict_phi = 0;
+
+ /*
+ * Beware: Do not remove Phi(Unknown, ..., x, ..., Unknown)
+ * as this might create non-strict programs.
+ */
+ if (node->is_follower && is_Phi(irn) && !is_Unknown(leader)) {
+ int i;
+
+ for (i = get_Phi_n_preds(irn) - 1; i >= 0; --i) {
+ ir_node *pred = get_Phi_pred(irn, i);
+
+ if (is_Unknown(pred)) {
+ non_strict_phi = 1;
+ break;
+ }
+ }
+ }
+ if (! non_strict_phi) {
+ DB((dbg, LEVEL_1, "%+F from part%d is replaced by %+F\n", irn, node->part->nr, leader));
+ if (node->is_follower)
+ DBG_OPT_COMBO(irn, leader, FS_OPT_COMBO_FOLLOWER);
+ else
+ DBG_OPT_COMBO(irn, leader, FS_OPT_COMBO_CONGRUENT);
+ exchange_leader(irn, leader);
+ env->modified = 1;
+ }
}
}
}
SET(Cmp);
SET(Proj);
SET(Confirm);
+ SET(Return);
SET(End);
if (op_Max != NULL)
} /* set_compute_functions */
-static int dump_partition_hook(FILE *F, ir_node *n, ir_node *local) {
-#ifdef DEBUG_libfirm
- ir_node *irn = local != NULL ? local : n;
- node_t *node = get_irn_node(irn);
-
- ir_fprintf(F, "info2 : \"partition %u type %+F\"\n", node->part->nr, node->type);
- return 1;
-#endif
-}
-
void combo(ir_graph *irg) {
environment_t env;
ir_node *initial_bl;
env.type2id_map = pmap_create();
env.end_idx = get_opt_global_cse() ? 0 : -1;
env.lambda_input = 0;
- env.nonstd_cond = 0;
env.commutative = 1;
env.modified = 0;
add_to_worklist(env.initial, &env);
irg_walk_graph(irg, init_block_phis, create_initial_partitions, &env);
+ /* set the hook: from now, every node has a partition and a type */
+ DEBUG_ONLY(set_dump_node_vcgattr_hook(dump_partition_hook));
+
#ifdef WITH_UNKNOWN
- tarval_UNKNOWN = env.nonstd_cond ? tarval_bad : tarval_top;
+ tarval_UNKNOWN = tarval_top;
#else
tarval_UNKNOWN = tarval_bad;
#endif
check_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 */
ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
+ /* remove the partition hook */
+ DEBUG_ONLY(set_dump_node_vcgattr_hook(NULL));
+
pmap_destroy(env.type2id_map);
del_set(env.opcode2id_map);
obstack_free(&env.obst, NULL);
projects / libfirm / blobdiff