From f749db8c76a4dbc8db2e92aadc39ba8241b6d02f Mon Sep 17 00:00:00 2001
From: Andreas Zwinkau <zwinkau@kit.edu>
Date: Thu, 5 May 2011 16:00:04 +0200
Subject: [PATCH] optimize_graph_df removes all Bads now

---
 ir/ir/irgopt.c | 104 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 104 insertions(+)

diff --git a/ir/ir/irgopt.c b/ir/ir/irgopt.c
index a4c454bda..1af16dd69 100644
--- a/ir/ir/irgopt.c
+++ b/ir/ir/irgopt.c
@@ -171,6 +171,107 @@ static void opt_walker(ir_node *n, void *env)
 	}
 }
 
+static void clear_block_phis(ir_node *node, void *env) {
+	(void) env;
+	if (is_Block(node)) {
+		set_Block_phis(node, NULL);
+	}
+}
+
+static void collect_block_phis(ir_node *node, void *env) {
+	(void) env;
+	if (is_Phi(node)) {
+		add_Block_phi(get_nodes_block(node), node);
+	}
+}
+
+static int count_non_bads(ir_node *node) {
+	int arity = get_irn_arity(node);
+	int count = 0;
+	int i;
+	for (i=0; i<arity; ++i) {
+		if (!is_Bad(get_irn_n(node, i)))
+			count++;
+	}
+	return count;
+}
+
+static void block_remove_bads(ir_node *block, int *changed) {
+	int i, j;
+	ir_node **new_in;
+	const int max = get_irn_arity(block);
+	const int new_max = count_non_bads(block);
+	assert (max >= new_max);
+
+	if (is_Bad(block) || max == new_max) return;
+
+	new_in = ALLOCAN(ir_node*, new_max);
+	*changed = 1;
+
+	assert (get_Block_dom_depth(block) >= 0);
+
+	/* 1. Create a new block without Bad inputs */
+	j = 0;
+	for (i = 0; i < max; ++i) {
+		ir_node *block_pred = get_irn_n(block, i);
+		if (!is_Bad(block_pred)) {
+			new_in[j++] = block_pred;
+		}
+	}
+	assert (j == new_max);
+
+	/* If the end block is unreachable, it might have zero predecessors. */
+	ir_node *end_block = get_irg_end_block(get_irn_irg(block));
+	if (new_max == 0 && block == end_block) {
+		set_irn_in(block, new_max, new_in);
+		return;
+	}
+
+	ir_node *new_block =  new_r_Block(get_irn_irg(block), new_max, new_in);
+
+	/* 2. Remove inputs on Phis, where the block input is Bad. */
+	ir_node *phi = get_Block_phis(block);
+	if (phi != NULL) {
+		do {
+			ir_node* next = get_Phi_next(phi);
+			if (get_irn_arity(phi) != new_max) {
+				j = 0;
+				for (i = 0; i < max; ++i) {
+					ir_node *block_pred = get_irn_n(block, i);
+
+					if (!is_Bad(block_pred)) {
+						ir_node *pred = get_irn_n(phi, i);
+						new_in[j++] = pred;
+					}
+				}
+				assert (j == new_max);
+
+				ir_node *new_phi = new_r_Phi(new_block, new_max, new_in, get_irn_mode(phi));
+				exchange(phi, new_phi);
+			}
+			phi = next;
+		} while (phi != NULL);
+	}
+
+	exchange(block, new_block);
+}
+
+/* Remove Bad nodes from Phi and Block inputs.
+ *
+ * Precondition: No unreachable code.
+ * Postcondition: No Bad nodes.
+ */
+static int remove_Bads(ir_graph *irg) {
+	int changed = 0;
+	/* build phi list per block */
+	irg_walk_graph(irg, clear_block_phis, collect_block_phis, NULL);
+
+	/* actually remove Bads */
+	irg_block_walk_graph(irg, NULL, (void (*)(struct ir_node *, void *)) block_remove_bads, &changed);
+
+	return changed;
+}
+
 /* Applies local optimizations to all nodes in the graph until fixpoint. */
 int optimize_graph_df(ir_graph *irg)
 {
@@ -232,6 +333,9 @@ int optimize_graph_df(ir_graph *irg)
 	end = get_irg_end(irg);
 	remove_End_Bads_and_doublets(end);
 
+	if (remove_Bads(irg))
+		edges_deactivate(irg);
+
 	clear_irg_state(irg, IR_GRAPH_STATE_BAD_BLOCK);
 
 	current_ir_graph = rem;
-- 
2.20.1