X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Flower%2Flower_switch.c;h=95296ec1bee20d13b7daf1a886518ea1852d736c;hb=847c1b62a1eae1e8055645996049f7f5db0a0d8b;hp=e44bd5fdef0461811a796843eb93a8df812e4ee1;hpb=ae9fd2c229cc7f4c724ce9ccc9263c16d77670fe;p=libfirm

diff --git a/ir/lower/lower_switch.c b/ir/lower/lower_switch.c
index e44bd5fde..95296ec1b 100644
--- a/ir/lower/lower_switch.c
+++ b/ir/lower/lower_switch.c
@@ -21,7 +21,6 @@
  * @file
  * @brief   Lowering of Switches if necessary or advantageous.
  * @author  Moritz Kroll
- * @version $Id$
  */
 #include "config.h"
 
@@ -43,120 +42,339 @@
 	i >= 0 && (outirn = get_irn_out(irn, i)); --i)
 
 typedef struct walk_env_t {
+	ir_nodeset_t  processed;
+	ir_mode      *selector_mode;
 	unsigned      spare_size; /**< the allowed spare size for table switches */
-	bool          allow_out_of_bounds;
+	unsigned      small_switch;
 	bool          changed;    /**< indicates whether a change was performed */
-	ir_nodeset_t  processed;
 } walk_env_t;
 
 typedef struct case_data_t {
-	long     value;
-	ir_node *target;
+	const ir_switch_table_entry *entry;
+	ir_node                     *target;
 } case_data_t;
 
-typedef struct cond_env_t {
-	ir_node  *sel;
-	long      switch_min;
-	long      switch_max;
-	ir_node  *default_block;
-	unsigned  num_cases;
-	ir_node **defusers;           /**< the Projs pointing to the default case */
-} cond_env_t;
+typedef struct switch_info_t {
+	ir_node     *switchn;
+	ir_tarval   *switch_min;
+	ir_tarval   *switch_max;
+	ir_node     *default_block;
+	unsigned     num_cases;
+	case_data_t *cases;
+	ir_node    **defusers;    /**< the Projs pointing to the default case */
+} switch_info_t;
 
-static void analyse_switch(cond_env_t *env, ir_node *cond)
+/**
+ * analyze enough to decide if we should lower the switch
+ */
+static void analyse_switch0(switch_info_t *info, ir_node *switchn)
 {
-	long     default_pn    = get_Cond_default_proj(cond);
-	long     switch_min    = LONG_MAX;
-	long     switch_max    = LONG_MIN;
-	ir_node *default_block = NULL;
-	unsigned num_cases     = 0;
-	int      i;
-	ir_node *proj;
-
-	foreach_out_irn(cond, i, proj) {
-		long pn = get_Proj_proj(proj);
-		if (pn == default_pn) {
-			ir_node *target = get_irn_out(proj, 0);
-			assert(default_block == NULL || default_block == target);
-			default_block = target;
+	const ir_switch_table *table      = get_Switch_table(switchn);
+	size_t                 n_entries  = ir_switch_table_get_n_entries(table);
+	ir_mode               *mode       = get_irn_mode(get_Switch_selector(switchn));
+	ir_tarval             *switch_min = get_mode_max(mode);
+	ir_tarval             *switch_max = get_mode_min(mode);
+	unsigned               num_cases  = 0;
+
+	for (size_t e = 0; e < n_entries; ++e) {
+		const ir_switch_table_entry *entry
+			= ir_switch_table_get_entry_const(table, e);
+		if (entry->pn == 0)
 			continue;
-		}
 
-		if (pn < switch_min)
-			switch_min = pn;
-		if (pn > switch_max)
-			switch_max = pn;
+		if (tarval_cmp(entry->min, switch_min) == ir_relation_less)
+			switch_min = entry->min;
+		if (tarval_cmp(entry->max, switch_max) == ir_relation_greater)
+			switch_max = entry->max;
+
 		++num_cases;
 	}
-	assert(default_block != NULL);
 
-	env->switch_min    = switch_min;
-	env->switch_max    = switch_max;
-	env->num_cases     = num_cases;
-	env->default_block = default_block;
+	info->switchn    = switchn;
+	info->switch_min = switch_min;
+	info->switch_max = switch_max;
+	info->num_cases  = num_cases;
 }
 
 static int casecmp(const void *a, const void *b)
 {
-	const case_data_t *cda = (const case_data_t*)a;
-	const case_data_t *cdb = (const case_data_t*)b;
+	const case_data_t           *cda = (const case_data_t*)a;
+	const case_data_t           *cdb = (const case_data_t*)b;
+	const ir_switch_table_entry *ea  = cda->entry;
+	const ir_switch_table_entry *eb  = cdb->entry;
+
+	if (ea == eb)
+		return 0;
+
+	if (tarval_cmp(ea->max, eb->min) == ir_relation_less)
+		return -1;
+	/* cases must be non overlapping, so the only remaining case is greater */
+	assert(tarval_cmp(ea->min, eb->max) == ir_relation_greater);
+	return 1;
+}
+
+/**
+ * Analyse the stuff that anayse_switch0() left out
+ */
+static void analyse_switch1(switch_info_t *info)
+{
+	const ir_node         *switchn   = info->switchn;
+	const ir_switch_table *table     = get_Switch_table(switchn);
+	size_t                 n_entries = ir_switch_table_get_n_entries(table);
+	unsigned               n_outs    = get_Switch_n_outs(switchn);
+	ir_node              **targets   = XMALLOCNZ(ir_node*, n_outs);
+	unsigned               num_cases = info->num_cases;
+	case_data_t           *cases     = XMALLOCN(case_data_t, num_cases);
+	unsigned               c         = 0;
+	size_t                 e;
+	int                    i;
+	ir_node               *proj;
+
+	foreach_out_irn(switchn, i, proj) {
+		long     pn     = get_Proj_proj(proj);
+		ir_node *target = get_irn_out(proj, 0);
+
+		assert((unsigned)pn < n_outs);
+		assert(targets[(unsigned)pn] == NULL);
+		targets[(unsigned)pn] = target;
+	}
+
+	for (e = 0; e < n_entries; ++e) {
+		const ir_switch_table_entry *entry
+			= ir_switch_table_get_entry_const(table, e);
+		if (entry->pn == 0)
+			continue;
+
+		cases[c].entry  = entry;
+		cases[c].target = targets[entry->pn];
+		++c;
+	}
+	assert(c == num_cases);
 
 	/*
-	 * Enforce unsigned sorting. Signed comparison will behave differently for
-	 * 32-bit values, depending on sizeof(long). This will make the resulting
-	 * array deterministic.
+	 * Switch should be transformed into an if cascade.
+	 * So first order the cases, so we can do a binary search on them.
 	 */
-	return ((unsigned long)cda->value > (unsigned long)cdb->value) -
-	       ((unsigned long)cda->value < (unsigned long)cdb->value);
+	qsort(cases, num_cases, sizeof(cases[0]), casecmp);
+
+	info->default_block = targets[pn_Switch_default];
+	info->cases         = cases;
+	free(targets);
+}
+
+static void normalize_table(ir_node *switchn, ir_mode *new_mode,
+                            ir_tarval *delta)
+{
+	ir_switch_table *table     = get_Switch_table(switchn);
+	size_t           n_entries = ir_switch_table_get_n_entries(table);
+	size_t           e;
+	/* adapt switch_table */
+	for (e = 0; e < n_entries; ++e) {
+		ir_switch_table_entry *entry = ir_switch_table_get_entry(table, e);
+		ir_tarval *min = entry->min;
+
+		if (entry->pn == 0)
+			continue;
+
+		min = tarval_convert_to(min, new_mode);
+		if (delta != NULL)
+			min = tarval_sub(min, delta, NULL);
+
+		if (entry->min == entry->max) {
+			entry->min = min;
+			entry->max = min;
+		} else {
+			ir_tarval *max = entry->max;
+			max = tarval_convert_to(max, new_mode);
+			if (delta != NULL)
+				max = tarval_sub(max, delta, NULL);
+			entry->min = min;
+			entry->max = max;
+		}
+	}
+}
+
+static void create_out_of_bounds_check(switch_info_t *info)
+{
+	ir_node    *switchn       = info->switchn;
+	ir_graph   *irg           = get_irn_irg(switchn);
+	dbg_info   *dbgi          = get_irn_dbg_info(switchn);
+	ir_node    *selector      = get_Switch_selector(switchn);
+	ir_node    *block         = get_nodes_block(switchn);
+	ir_node   **default_preds = NEW_ARR_F(ir_node*, 0);
+	ir_node    *default_block = NULL;
+	ir_node    *max_const;
+	ir_node    *proj_true;
+	ir_node    *proj_false;
+	ir_node    *cmp;
+	ir_node    *oob_cond;
+	ir_node    *in[1];
+	ir_node    *new_block;
+	int         i;
+	ir_node    *proj;
+	size_t      n_default_preds;
+
+	assert(tarval_is_null(info->switch_min));
+
+	/* check for out-of-bounds */
+	max_const  = new_r_Const(irg, info->switch_max);
+	cmp        = new_rd_Cmp(dbgi, block, selector, max_const, ir_relation_less_equal);
+	oob_cond   = new_rd_Cond(dbgi, block, cmp);
+	proj_true  = new_r_Proj(oob_cond, mode_X, pn_Cond_true);
+	proj_false = new_r_Proj(oob_cond, mode_X, pn_Cond_false);
+
+	ARR_APP1(ir_node*, default_preds, proj_false);
+
+	/* create new block containing the switch */
+	in[0] = proj_true;
+	new_block = new_r_Block(irg, 1, in);
+	set_nodes_block(switchn, new_block);
+
+	/* adjust projs */
+	foreach_out_irn(switchn, i, proj) {
+		long pn = get_Proj_proj(proj);
+		if (pn == pn_Switch_default) {
+			assert(default_block == NULL);
+			default_block = get_irn_out(proj, 0);
+			ARR_APP1(ir_node*, default_preds, proj);
+		}
+		set_nodes_block(proj, new_block);
+	}
+
+	/* adapt default block */
+	n_default_preds = ARR_LEN(default_preds);
+	if (n_default_preds > 1) {
+		/* create new intermediate blocks so we don't have critical edges */
+		size_t p;
+		for (p = 0; p < n_default_preds; ++p) {
+			ir_node *pred = default_preds[p];
+			ir_node *split_block;
+			ir_node *block_in[1];
+
+			block_in[0] = pred;
+			split_block = new_r_Block(irg, 1, block_in);
+
+			default_preds[p] = new_r_Jmp(split_block);
+		}
+	}
+	set_irn_in(default_block, n_default_preds, default_preds);
+
+	DEL_ARR_F(default_preds);
+
+	clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
+}
+
+/**
+ * normalize switch to work on an unsigned input with the first case at 0
+ */
+static void normalize_switch(switch_info_t *info, ir_mode *selector_mode)
+{
+	ir_node   *switchn         = info->switchn;
+	ir_graph  *irg             = get_irn_irg(switchn);
+	ir_node   *block           = get_nodes_block(switchn);
+	ir_node   *selector        = get_Switch_selector(switchn);
+	ir_mode   *mode            = get_irn_mode(selector);
+	ir_tarval *delta           = NULL;
+	bool       needs_normalize = false;
+
+	ir_tarval *min = info->switch_min;
+	if (mode_is_signed(mode)) {
+		mode             = find_unsigned_mode(mode);
+		selector         = new_r_Conv(block, selector, mode);
+		min              = tarval_convert_to(min, mode);
+		info->switch_min = min;
+		info->switch_max = tarval_convert_to(info->switch_max, mode);
+		needs_normalize  = true;
+	}
+
+	/* normalize so switch_min is at 0 */
+	if (min != get_mode_null(mode)) {
+		ir_node  *min_const = new_r_Const(irg, min);
+		dbg_info *dbgi      = get_irn_dbg_info(switchn);
+		selector = new_rd_Sub(dbgi, block, selector, min_const, mode);
+
+		info->switch_max = tarval_sub(info->switch_max, min, mode);
+		info->switch_min = get_mode_null(mode);
+		delta            = min;
+
+		needs_normalize = true;
+	}
+
+	/* if we have a selector_mode set, then the we will have a switch node,
+	 * we have to construct an out-of-bounds check then and after that convert
+	 * the switch/selector to the backends desired switch mode */
+	if (selector_mode != NULL) {
+		set_Switch_selector(switchn, selector);
+		create_out_of_bounds_check(info);
+
+		selector = new_r_Conv(block, selector, selector_mode);
+		mode     = selector_mode;
+		info->switch_min = tarval_convert_to(info->switch_min, mode);
+		info->switch_max = tarval_convert_to(info->switch_max, mode);
+		if (delta != NULL)
+			delta = tarval_convert_to(delta, mode);
+		needs_normalize = true;
+	}
+
+	if (needs_normalize) {
+		set_Switch_selector(switchn, selector);
+		normalize_table(switchn, mode, delta);
+	}
+}
+
+/**
+ * Create an if (selector == caseval) Cond node (and handle the special case
+ * of ranged cases)
+ */
+static ir_node *create_case_cond(const ir_switch_table_entry *entry,
+                                 dbg_info *dbgi, ir_node *block,
+                                 ir_node *selector)
+{
+	ir_graph *irg      = get_irn_irg(block);
+	ir_node  *minconst = new_r_Const(irg, entry->min);
+	ir_node  *cmp;
+
+	if (entry->min == entry->max) {
+		cmp = new_rd_Cmp(dbgi, block, selector, minconst, ir_relation_equal);
+	} else {
+		ir_tarval *adjusted_max = tarval_sub(entry->max, entry->min, NULL);
+		ir_node   *sub          = new_rd_Sub(dbgi, block, selector, minconst,
+		                                     get_tarval_mode(adjusted_max));
+		ir_node   *maxconst     = new_r_Const(irg, adjusted_max);
+		cmp = new_rd_Cmp(dbgi, block, sub, maxconst, ir_relation_less_equal);
+	}
+
+	return new_rd_Cond(dbgi, block, cmp);
 }
 
 /**
  * Creates an if cascade realizing binary search.
  */
-static void create_if_cascade(cond_env_t *env, dbg_info *dbgi, ir_node *block,
+static void create_if_cascade(switch_info_t *info, ir_node *block,
                               case_data_t *curcases, unsigned numcases)
 {
-	ir_graph *irg = get_irn_irg(block);
-    ir_mode  *cmp_mode;
-    ir_node  *cmp_sel;
-    ir_node  *sel_block;
-
-    /* Get the mode and sel node for the comparison. */
-    cmp_mode  = get_irn_mode(env->sel);
-    cmp_sel   = env->sel;
-    sel_block = get_nodes_block(cmp_sel);
-
-    /*
-     * Make sure that an unsigned comparison is used, by converting the sel
-     * node to an unsigned mode and using that mode for the constants, too.
-     * This is important, because the qsort applied to the case labels uses
-     * an unsigned comparison and both comparison methods have to match.
-     */
-    if (mode_is_signed(cmp_mode)) {
-        cmp_mode = find_unsigned_mode(cmp_mode);
-        cmp_sel  = new_r_Conv(sel_block, cmp_sel, cmp_mode);
-    }
+	ir_graph      *irg      = get_irn_irg(block);
+	const ir_node *switchn  = info->switchn;
+	dbg_info      *dbgi     = get_irn_dbg_info(switchn);
+	ir_node       *selector = get_Switch_selector(switchn);
 
 	if (numcases == 0) {
 		/* zero cases: "goto default;" */
-		ARR_APP1(ir_node*, env->defusers, new_r_Jmp(block));
+		ARR_APP1(ir_node*, info->defusers, new_r_Jmp(block));
 	} else if (numcases == 1) {
-		/* only one case: "if (sel == val) goto target else goto default;" */
-		ir_node *val       = new_r_Const_long(irg, cmp_mode, curcases[0].value);
-		ir_node *cmp       = new_rd_Cmp(dbgi, block, cmp_sel, val,
-		                                ir_relation_equal);
-		ir_node *cond      = new_rd_Cond(dbgi, block, cmp);
+		/*only one case: "if (sel == val) goto target else goto default;"*/
+		const ir_switch_table_entry *entry = curcases[0].entry;
+		ir_node *cond      = create_case_cond(entry, dbgi, block, selector);
 		ir_node *trueproj  = new_r_Proj(cond, mode_X, pn_Cond_true);
 		ir_node *falseproj = new_r_Proj(cond, mode_X, pn_Cond_false);
 
 		set_Block_cfgpred(curcases[0].target, 0, trueproj);
-		ARR_APP1(ir_node*, env->defusers, falseproj);
+		ARR_APP1(ir_node*, info->defusers, falseproj);
 	} else if (numcases == 2) {
 		/* only two cases: "if (sel == val[0]) goto target[0];" */
-		ir_node *val       = new_r_Const_long(irg, cmp_mode, curcases[0].value);
-		ir_node *cmp       = new_rd_Cmp(dbgi, block, cmp_sel, val,
-		                                ir_relation_equal);
-		ir_node *cond      = new_rd_Cond(dbgi, block, cmp);
+		const ir_switch_table_entry *entry0 = curcases[0].entry;
+		const ir_switch_table_entry *entry1 = curcases[1].entry;
+		ir_node *cond      = create_case_cond(entry0, dbgi, block, selector);
 		ir_node *trueproj  = new_r_Proj(cond, mode_X, pn_Cond_true);
 		ir_node *falseproj = new_r_Proj(cond, mode_X, pn_Cond_false);
 		ir_node *in[1];
@@ -168,19 +386,17 @@ static void create_if_cascade(cond_env_t *env, dbg_info *dbgi, ir_node *block,
 		neblock = new_r_Block(irg, 1, in);
 
 		/* second part: "else if (sel == val[1]) goto target[1] else goto default;" */
-		val       = new_r_Const_long(irg, cmp_mode, curcases[1].value);
-		cmp       = new_rd_Cmp(dbgi, neblock, cmp_sel, val, ir_relation_equal);
-		cond      = new_rd_Cond(dbgi, neblock, cmp);
+		cond      = create_case_cond(entry1, dbgi, neblock, selector);
 		trueproj  = new_r_Proj(cond, mode_X, pn_Cond_true);
 		falseproj = new_r_Proj(cond, mode_X, pn_Cond_false);
 		set_Block_cfgpred(curcases[1].target, 0, trueproj);
-		ARR_APP1(ir_node*, env->defusers, falseproj);
+		ARR_APP1(ir_node*, info->defusers, falseproj);
 	} else {
 		/* recursive case: split cases in the middle */
-		int midcase = numcases / 2;
-		ir_node *val  = new_r_Const_long(irg, cmp_mode,
-		                                 curcases[midcase].value);
-		ir_node *cmp  = new_rd_Cmp(dbgi, block, cmp_sel, val, ir_relation_less);
+		unsigned midcase = numcases / 2;
+		const ir_switch_table_entry *entry = curcases[midcase].entry;
+		ir_node *val = new_r_Const(irg, entry->min);
+		ir_node *cmp = new_rd_Cmp(dbgi, block, selector, val, ir_relation_less);
 		ir_node *cond = new_rd_Cond(dbgi, block, cmp);
 		ir_node *in[1];
 		ir_node *ltblock;
@@ -192,125 +408,20 @@ static void create_if_cascade(cond_env_t *env, dbg_info *dbgi, ir_node *block,
 		in[0]   = new_r_Proj(cond, mode_X, pn_Cond_false);
 		geblock = new_r_Block(irg, 1, in);
 
-		create_if_cascade(env, dbgi, ltblock, curcases, midcase);
-		create_if_cascade(env, dbgi, geblock, curcases + midcase,
-		                  numcases - midcase);
+		create_if_cascade(info, ltblock, curcases, midcase);
+		create_if_cascade(info, geblock, curcases + midcase, numcases - midcase);
 	}
 }
 
-static void create_out_of_bounds_check(cond_env_t *env, ir_node *cond)
-{
-	ir_graph      *irg           = get_irn_irg(cond);
-	dbg_info      *dbgi          = get_irn_dbg_info(cond);
-	ir_node       *sel           = get_Cond_selector(cond);
-	ir_node       *block         = get_nodes_block(cond);
-	ir_mode       *cmp_mode      = get_irn_mode(sel);
-	ir_node      **default_preds = NEW_ARR_F(ir_node*, 0);
-	unsigned long  default_pn    = get_Cond_default_proj(cond);
-	long           delta         = 0;
-	ir_node       *max_const;
-	ir_node       *proj_true;
-	ir_node       *proj_false;
-	ir_node       *cmp;
-	ir_node       *oob_cond;
-	ir_node       *in[1];
-	ir_node       *new_block;
-	size_t         n_default_preds;
-	int            i;
-	ir_node       *proj;
-
-	if (mode_is_signed(cmp_mode)) {
-		cmp_mode = find_unsigned_mode(cmp_mode);
-		sel      = new_r_Conv(block, sel, cmp_mode);
-	}
-
-	/* normalize so switch_min is at 0 */
-	if (env->switch_min != 0) {
-		ir_node *min_const  = new_r_Const_long(irg, cmp_mode, env->switch_min);
-		sel = new_rd_Sub(dbgi, block, sel, min_const, cmp_mode);
-
-		delta            = env->switch_min;
-		env->switch_min  = 0;
-		env->switch_max -= delta;
-		set_Cond_selector(cond, sel);
-	}
-
-	/* check for out-of-bounds */
-	max_const  = new_r_Const_long(irg, cmp_mode, env->switch_max);
-	cmp        = new_rd_Cmp(dbgi, block, sel, max_const, ir_relation_less_equal);
-	oob_cond   = new_rd_Cond(dbgi, block, cmp);
-	proj_true  = new_r_Proj(oob_cond, mode_X, pn_Cond_true);
-	proj_false = new_r_Proj(oob_cond, mode_X, pn_Cond_false);
-
-	ARR_APP1(ir_node*, default_preds, proj_false);
-
-	/* create new block containing the cond */
-	in[0] = proj_true;
-	new_block = new_r_Block(irg, 1, in);
-	set_nodes_block(cond, new_block);
-
-	/* adapt projs */
-	foreach_out_irn(cond, i, proj) {
-		unsigned long pn     = get_Proj_proj(proj);
-		unsigned long new_pn = pn - delta;
-		if (pn == default_pn) {
-			/* we might have to choose a new default_pn */
-			if (pn < (unsigned long) env->switch_max) {
-				new_pn = env->switch_max + 1;
-				set_Cond_default_proj(cond, new_pn);
-			} else {
-				new_pn = default_pn;
-			}
-			ARR_APP1(ir_node*, default_preds, proj);
-		}
-
-		set_Proj_proj(proj, new_pn);
-		set_nodes_block(proj, new_block);
-	}
-
-	/* adapt default block */
-	n_default_preds = ARR_LEN(default_preds);
-	if (n_default_preds > 1) {
-		size_t i;
-
-		/* create new intermediate blocks so we don't have critical edges */
-		for (i = 0; i < n_default_preds; ++i) {
-			ir_node *proj = default_preds[i];
-			ir_node *block;
-			ir_node *in[1];
-
-			in[0] = proj;
-			block = new_r_Block(irg, 1, in);
-
-			default_preds[i] = new_r_Jmp(block);
-		}
-	}
-	set_irn_in(env->default_block, n_default_preds, default_preds);
-
-	DEL_ARR_F(default_preds);
-}
-
 /**
- * Block-Walker: searches for Cond nodes with a non-boolean mode
+ * Block-Walker: searches for Switch nodes
  */
-static void find_cond_nodes(ir_node *block, void *ctx)
+static void find_switch_nodes(ir_node *block, void *ctx)
 {
-	walk_env_t  *env = (walk_env_t *)ctx;
-	ir_node     *projx;
-	ir_node     *cond;
-	ir_node     *sel;
-	ir_mode     *sel_mode;
-	long         default_pn;
-	int          i;
-	unsigned     j = 0;
-	unsigned     numcases;
-	ir_node     *proj;
-	case_data_t *cases;
-	ir_node     *condblock;
-	ir_node     *defblock = NULL;
-	dbg_info    *dbgi;
-	cond_env_t   cond_env;
-	unsigned long spare;
+	walk_env_t   *env = (walk_env_t *)ctx;
+	ir_node      *projx;
+	ir_node      *switchn;
+	switch_info_t info;
 
 	/* because we split critical blocks only blocks with 1 predecessors may
 	 * contain Proj->Cond nodes */
@@ -322,107 +433,72 @@ static void find_cond_nodes(ir_node *block, void *ctx)
 		return;
 	assert(get_irn_mode(projx) == mode_X);
 
-	cond = get_Proj_pred(projx);
-	if (!is_Cond(cond))
+	switchn = get_Proj_pred(projx);
+	if (!is_Switch(switchn))
 		return;
 
-	sel      = get_Cond_selector(cond);
-	sel_mode = get_irn_mode(sel);
-
-	if (sel_mode == mode_b)
+	if (ir_nodeset_contains(&env->processed, switchn))
 		return;
+	ir_nodeset_insert(&env->processed, switchn);
 
-	if (ir_nodeset_contains(&env->processed, cond))
-		return;
-	ir_nodeset_insert(&env->processed, cond);
-
-	/* the algorithms here don't work reliable for modes bigger than 32
-	 * since we operate with long numbers */
-	assert(get_mode_size_bits(sel_mode) <= 32);
-
-	analyse_switch(&cond_env, cond);
+	analyse_switch0(&info, switchn);
 
 	/*
 	 * Here we have: num_cases and [switch_min, switch_max] interval.
 	 * We do an if-cascade if there are too many spare numbers.
 	 */
-	spare = (unsigned long) cond_env.switch_max
-		- (unsigned long) cond_env.switch_min
-		- (unsigned long) cond_env.num_cases + 1;
-	if (spare < env->spare_size) {
-		/* we won't decompose the switch. But we might have to add
-		 * out-of-bounds checking */
-		if (!env->allow_out_of_bounds) {
-			create_out_of_bounds_check(&cond_env, cond);
-			env->changed = true;
-		}
+	ir_mode   *mode  = get_irn_mode(get_Switch_selector(switchn));
+	ir_tarval *spare = tarval_sub(info.switch_max, info.switch_min, mode);
+	mode  = find_unsigned_mode(mode);
+	spare = tarval_convert_to(spare, mode);
+	ir_tarval *num_cases_minus_one
+		= new_tarval_from_long(info.num_cases-1, mode);
+	spare = tarval_sub(spare, num_cases_minus_one, mode);
+	ir_tarval *spare_size = new_tarval_from_long(env->spare_size, mode);
+	bool lower_switch = (info.num_cases <= env->small_switch
+	 || (tarval_cmp(spare, spare_size) & ir_relation_greater_equal));
+
+	if (!lower_switch) {
+		/* we won't decompose the switch. But we must add an out-of-bounds
+		 * check */
+		normalize_switch(&info, env->selector_mode);
 		return;
 	}
 
-	/*
-	 * Switch should be transformed into an if cascade.
-	 * So first order the cases, so we can do a binary search on them.
-	 */
-	env->changed = true;
-
-	numcases = get_irn_n_outs(cond) - 1; /* does not contain default case */
-	cases    = XMALLOCN(case_data_t, numcases);
-
-	default_pn        = get_Cond_default_proj(cond);
-	cond_env.sel      = sel;
-	cond_env.defusers = NEW_ARR_F(ir_node*, 0);
-
-	foreach_out_irn(cond, i, proj) {
-		long pn = get_Proj_proj(proj);
-		ir_node *target = get_irn_out(proj, 0);
-		assert(get_Block_n_cfgpreds(target) == 1);
-
-		if (pn == default_pn) {
-			defblock = target;
-			continue;
-		}
-
-		cases[j].value  = pn;
-		cases[j].target = target;
-		j++;
-	}
-	assert(j == numcases);
-
-	if (defblock == NULL)
-		panic("Switch %+F has no default proj", cond);
-
-	qsort(cases, numcases, sizeof(cases[0]), casecmp);
+	normalize_switch(&info, NULL);
+	analyse_switch1(&info);
 
 	/* Now create the if cascade */
-	condblock = get_nodes_block(cond);
-	dbgi      = get_irn_dbg_info(cond);
-	create_if_cascade(&cond_env, dbgi, condblock, cases, numcases);
+	env->changed  = true;
+	info.defusers = NEW_ARR_F(ir_node*, 0);
+	block         = get_nodes_block(switchn);
+	create_if_cascade(&info, block, info.cases, info.num_cases);
 
 	/* Connect new default case users */
-	set_irn_in(defblock, ARR_LEN(cond_env.defusers), cond_env.defusers);
+	set_irn_in(info.default_block, ARR_LEN(info.defusers), info.defusers);
 
-	xfree(cases);
-	DEL_ARR_F(cond_env.defusers);
+	DEL_ARR_F(info.defusers);
+	xfree(info.cases);
+	clear_irg_properties(get_irn_irg(block), IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES
+	                                  | IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
 }
 
-void lower_switch(ir_graph *irg, unsigned spare_size, int allow_out_of_bounds)
+void lower_switch(ir_graph *irg, unsigned small_switch, unsigned spare_size,
+                  ir_mode *selector_mode)
 {
+	if (mode_is_signed(selector_mode))
+		panic("expected unsigned mode for switch selector");
+
 	walk_env_t env;
-	env.changed             = false;
+	env.selector_mode       = selector_mode;
 	env.spare_size          = spare_size;
-	env.allow_out_of_bounds = allow_out_of_bounds;
+	env.small_switch        = small_switch;
+	env.changed             = false;
 	ir_nodeset_init(&env.processed);
 
 	remove_critical_cf_edges(irg);
 	assure_irg_outs(irg);
 
-	irg_block_walk_graph(irg, find_cond_nodes, NULL, &env);
+	irg_block_walk_graph(irg, find_switch_nodes, NULL, &env);
 	ir_nodeset_destroy(&env.processed);
-
-	if (env.changed) {
-		/* control flow changed */
-		set_irg_doms_inconsistent(irg);
-		set_irg_extblk_inconsistent(irg);
-		set_irg_loopinfo_inconsistent(irg);
-	}
 }