From a41c693d22cee2804a2aa5ab5cac00d942f3b3ce Mon Sep 17 00:00:00 2001
From: Matthias Braun <matze@braunis.de>
Date: Mon, 11 Sep 2006 12:36:42 +0000
Subject: [PATCH] SSA construction code for condeval optimisation

[r8211]
---
 ir/opt/condeval.c | 104 +++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 94 insertions(+), 10 deletions(-)

diff --git a/ir/opt/condeval.c b/ir/opt/condeval.c
index 639a17b21..4be3477c6 100644
--- a/ir/opt/condeval.c
+++ b/ir/opt/condeval.c
@@ -2,23 +2,105 @@
 #include "config.h"
 #endif
 
-#ifdef HAVE_ALLOCA_H
-#include <alloca.h>
-#endif
-#ifdef HAVE_MALLOC_H
-#include <malloc.h>
-#endif
-
 #include <assert.h>
 #include "array.h"
 #include "debug.h"
 #include "ircons.h"
 #include "irgwalk.h"
 #include "irnode.h"
+#include "iredges.h"
 #include "tv.h"
 
 DEBUG_ONLY(static firm_dbg_module_t *dbg);
 
+static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) {
+	int i;
+	int n_cfgpreds;
+	ir_graph *irg;
+	ir_node *phi;
+	ir_node **in;
+
+	assert(!is_Bad(block));
+
+	// already processed this block?
+	if(irn_visited(block)) {
+		ir_node *value = (ir_node*) get_irn_link(block);
+		return value;
+	}
+
+	// blocks with only 1 pred need no phi
+	n_cfgpreds = get_Block_n_cfgpreds(block);
+	if(n_cfgpreds == 1) {
+		ir_node *pred_block = get_Block_cfgpred_block(block, 0);
+		ir_node *value = search_def_and_create_phis(pred_block, mode);
+
+		set_irn_link(block, value);
+		mark_irn_visited(block);
+		return value;
+	}
+
+	// create a new phi
+	in = alloca(sizeof(in[0]) * n_cfgpreds);
+	for(i = 0; i < n_cfgpreds; ++i)
+		in[i] = new_Unknown(mode);
+
+	irg = get_irn_irg(block);
+	phi = new_r_Phi(irg, block, n_cfgpreds, in, mode);
+	set_irn_link(block, phi);
+	mark_irn_visited(block);
+
+	// set phi preds
+	for(i = 0; i < n_cfgpreds; ++i) {
+		ir_node *pred_block = get_Block_cfgpred_block(block, i);
+		ir_node *pred_val;
+
+		pred_val = search_def_and_create_phis(pred_block, mode);
+		set_irn_n(phi, i, pred_val);
+	}
+
+	return phi;
+}
+
+/**
+ * Given a set of values this function constructs SSA-form for all users of the
+ * values (the user are determined through the out-edges of the values).
+ */
+static void construct_ssa(ir_node * const *vals, int n_vals) {
+	int i;
+	ir_graph *irg;
+	ir_mode *mode;
+
+	assert(n_vals > 0);
+
+	irg = get_irn_irg(vals[0]);
+	inc_irg_visited(irg);
+
+	mode = get_irn_mode(vals[0]);
+	for(i = 0; i < n_vals; ++i) {
+		ir_node *value = vals[i];
+		ir_node *value_block = get_nodes_block(value);
+
+		assert(get_irn_mode(value) == mode);
+
+		set_irn_link(value_block, value);
+		mark_irn_visited(value_block);
+	}
+
+	for(i = 0; i < n_vals; ++i) {
+		const ir_edge_t *edge;
+		ir_node *value = vals[i];
+
+		foreach_out_edge(value, edge) {
+			ir_node *user = get_edge_src_irn(edge);
+			ir_node *user_block = get_nodes_block(user);
+			ir_node *newval;
+
+			newval = search_def_and_create_phis(user_block, mode);
+			set_irn_n(user, get_edge_src_pos(edge), newval);
+		}
+	}
+}
+
 /**
  * Block-walker:
  */
@@ -37,6 +119,7 @@ static void cond_eval(ir_node* block, void* env)
 		ir_node* cond_block;
 		ir_node* phi;
 		ir_node* cnst;
+		tarval *tv_cnst;
 		pn_Cmp pnc;
 		int n_phi;
 		int j;
@@ -74,16 +157,18 @@ static void cond_eval(ir_node* block, void* env)
 		} else {
 			continue;
 		}
+		tv_cnst = get_Const_tarval(cnst);
 
 		cond_block = get_nodes_block(cond);
 		if (get_nodes_block(phi) != cond_block) continue;
 
-		if (get_Proj_proj(projx) == 0) pnc = get_negated_pnc(pnc, get_irn_mode(cnst));
+		if (get_Proj_proj(projx) == 0) {
+			pnc = get_negated_pnc(pnc, get_irn_mode(cnst));
+		}
 
 		n_phi = get_Phi_n_preds(phi);
 		for (j = 0; j < n_phi; j++) {
 			tarval* tv_phi;
-			tarval* tv_cnst;
 			ir_node** ins;
 			int k;
 			pn_Cmp cmp_val;
@@ -93,7 +178,6 @@ static void cond_eval(ir_node* block, void* env)
 			if (!is_Const(pred)) continue;
 
 			tv_phi  = get_Const_tarval(pred);
-			tv_cnst = get_Const_tarval(cnst);
 
 			cmp_val = tarval_cmp(tv_phi, tv_cnst);
 			if (cmp_val == pn_Cmp_False)
-- 
2.20.1