+/*
+ * Identity functions: Note that one might thing that identity() is just a
+ * synonym for equivalent_node(). While this is true, we cannot use it for the algorithm
+ * here, because it expects that the identity node is one of the inputs, which is NOT
+ * always true for equivalent_node() which can handle (and does sometimes) DAGs.
+ * So, we have our own implementation, which copies some parts of equivalent_node()
+ */
+
+/**
+ * Calculates the Identity for Phi nodes
+ */
+static node_t *identity_Phi(node_t *node)
+{
+ ir_node *phi = node->node;
+ ir_node *block = get_nodes_block(phi);
+ node_t *n_part = NULL;
+ int i;
+
+ for (i = get_Phi_n_preds(phi) - 1; i >= 0; --i) {
+ node_t *pred_X = get_irn_node(get_Block_cfgpred(block, i));
+
+ if (pred_X->type.tv == tarval_reachable) {
+ node_t *pred = get_irn_node(get_Phi_pred(phi, i));
+
+ if (n_part == NULL)
+ n_part = pred;
+ else if (n_part->part != pred->part) {
+ /* incongruent inputs, not a follower */
+ return node;
+ }
+ }
+ }
+ /* if n_part is NULL here, all inputs path are dead, the Phi computes
+ * tarval_top, is in the TOP partition and should NOT being split! */
+ assert(n_part != NULL);
+ return n_part;
+} /* identity_Phi */
+
+/**
+ * Calculates the Identity for commutative 0 neutral nodes.
+ */
+static node_t *identity_comm_zero_binop(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 *zero;
+
+ /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
+ if (mode_is_float(mode) && (get_irg_fp_model(current_ir_graph) & fp_strict_algebraic))
+ return node;
+
+ /* node: no input should be tarval_top, else the binop would be also
+ * Top and not being split. */
+ zero = get_mode_null(mode);
+ if (a->type.tv == zero)
+ return b;
+ if (b->type.tv == zero)
+ return a;
+ return node;
+} /* identity_comm_zero_binop */
+
+/**
+ * Calculates the Identity for Shift nodes.
+ */
+static node_t *identity_shift(node_t *node)
+{
+ ir_node *op = node->node;
+ node_t *b = get_irn_node(get_binop_right(op));
+ ir_mode *mode = get_irn_mode(b->node);
+ tarval *zero;
+
+ /* node: no input should be tarval_top, else the binop would be also
+ * Top and not being split. */
+ zero = get_mode_null(mode);
+ if (b->type.tv == zero)
+ return get_irn_node(get_binop_left(op));
+ return node;
+} /* identity_shift */
+
+/**
+ * Calculates the Identity for Mul nodes.
+ */
+static node_t *identity_Mul(node_t *node)
+{
+ ir_node *op = node->node;
+ node_t *a = get_irn_node(get_Mul_left(op));
+ node_t *b = get_irn_node(get_Mul_right(op));
+ ir_mode *mode = get_irn_mode(op);
+ tarval *one;
+
+ /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
+ if (mode_is_float(mode) && (get_irg_fp_model(current_ir_graph) & fp_strict_algebraic))
+ return node;
+
+ /* node: no input should be tarval_top, else the binop would be also
+ * Top and not being split. */
+ one = get_mode_one(mode);
+ if (a->type.tv == one)
+ return b;
+ if (b->type.tv == one)
+ return a;
+ return node;
+} /* identity_Mul */
+
+/**
+ * Calculates the Identity for Sub nodes.
+ */
+static node_t *identity_Sub(node_t *node)
+{
+ ir_node *sub = node->node;
+ node_t *b = get_irn_node(get_Sub_right(sub));
+ ir_mode *mode = get_irn_mode(sub);
+
+ /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
+ if (mode_is_float(mode) && (get_irg_fp_model(current_ir_graph) & fp_strict_algebraic))
+ return node;
+
+ /* node: no input should be tarval_top, else the binop would be also
+ * Top and not being split. */
+ if (b->type.tv == get_mode_null(mode))
+ return get_irn_node(get_Sub_left(sub));
+ return node;
+} /* identity_Sub */
+
+/**
+ * Calculates the Identity for And nodes.
+ */
+static node_t *identity_And(node_t *node)
+{
+ ir_node *and = node->node;
+ node_t *a = get_irn_node(get_And_left(and));
+ node_t *b = get_irn_node(get_And_right(and));
+ tarval *neutral = get_mode_all_one(get_irn_mode(and));
+
+ /* node: no input should be tarval_top, else the And would be also
+ * Top and not being split. */
+ if (a->type.tv == neutral)
+ return b;
+ if (b->type.tv == neutral)
+ return a;
+ return node;
+} /* identity_And */
+
+/**
+ * Calculates the Identity for Confirm nodes.
+ */
+static node_t *identity_Confirm(node_t *node)
+{
+ ir_node *confirm = node->node;
+
+ /* a Confirm is always a Copy */
+ return get_irn_node(get_Confirm_value(confirm));
+} /* identity_Confirm */
+
+/**
+ * Calculates the Identity for Mux nodes.
+ */
+static node_t *identity_Mux(node_t *node)
+{
+ ir_node *mux = node->node;
+ node_t *t = get_irn_node(get_Mux_true(mux));
+ node_t *f = get_irn_node(get_Mux_false(mux));
+ /*node_t *sel; */
+
+ if (t->part == f->part)
+ return t;
+
+ /* for now, the 1-input identity is not supported */
+#if 0
+ sel = get_irn_node(get_Mux_sel(mux));
+
+ /* Mux sel input is mode_b, so it is always a tarval */
+ if (sel->type.tv == tarval_b_true)
+ return t;
+ if (sel->type.tv == tarval_b_false)
+ return f;
+#endif
+ return node;
+} /* identity_Mux */
+
+/**
+ * Calculates the Identity for nodes.
+ */
+static node_t *identity(node_t *node)
+{
+ ir_node *irn = node->node;
+
+ switch (get_irn_opcode(irn)) {
+ case iro_Phi:
+ return identity_Phi(node);
+ case iro_Mul:
+ return identity_Mul(node);
+ case iro_Add:
+ case iro_Or:
+ case iro_Eor:
+ return identity_comm_zero_binop(node);
+ case iro_Shr:
+ case iro_Shl:
+ case iro_Shrs:
+ case iro_Rotl:
+ return identity_shift(node);
+ case iro_And:
+ return identity_And(node);
+ case iro_Sub:
+ return identity_Sub(node);
+ case iro_Confirm:
+ return identity_Confirm(node);
+ case iro_Mux:
+ return identity_Mux(node);
+ default:
+ return node;
+ }
+} /* identity */
+
+/**
+ * Node follower is a (new) follower of leader, segregate Leader
+ * out edges.
+ */
+static void segregate_def_use_chain_1(const ir_node *follower, node_t *leader)
+{
+ ir_node *l = leader->node;
+ int j, i, n = get_irn_n_outs(l);
+
+ DB((dbg, LEVEL_2, "%+F is a follower of %+F\n", follower, leader->node));
+ /* The leader edges must remain sorted, but follower edges can
+ be unsorted. */
+ for (i = leader->n_followers + 1; i <= n; ++i) {
+ if (l->out[i].use == follower) {
+ ir_def_use_edge t = l->out[i];
+
+ for (j = i - 1; j >= leader->n_followers + 1; --j)
+ l->out[j + 1] = l->out[j];
+ ++leader->n_followers;
+ l->out[leader->n_followers] = t;
+ break;
+ }
+ }
+} /* segregate_def_use_chain_1 */
+
+/**
+ * Node follower is a (new) follower segregate its Leader
+ * out edges.
+ *
+ * @param follower the follower IR node
+ */
+static void segregate_def_use_chain(const ir_node *follower)
+{
+ int i;
+
+ for (i = get_irn_arity(follower) - 1; i >= 0; --i) {
+ node_t *pred = get_irn_node(get_irn_n(follower, i));
+
+ segregate_def_use_chain_1(follower, pred);
+ }
+} /* segregate_def_use_chain */
+