lower_switch.c 12.4 KB
Newer Older
1
/*
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

/**
 * @file
 * @brief   Lowering of Switches if necessary or advantageous.
 * @author  Moritz Kroll
 * @version $Id$
 */
#include "config.h"

28
#include <limits.h>
29
#include <stdbool.h>
30

31
#include "array_t.h"
32
#include "ircons.h"
Moritz Kroll's avatar
Moritz Kroll committed
33
#include "irgopt.h"
34
35
36
#include "irgwalk.h"
#include "irnode_t.h"
#include "irouts.h"
Michael Beck's avatar
Michael Beck committed
37
#include "irpass_t.h"
38
#include "lowering.h"
39
#include "error.h"
40
#include "irnodeset.h"
41

42
#define foreach_out_irn(irn, i, outirn) for (i = get_irn_n_outs(irn) - 1;\
43
44
	i >= 0 && (outirn = get_irn_out(irn, i)); --i)

45
46
47
48
49
typedef struct walk_env_t {
	unsigned      spare_size; /**< the allowed spare size for table switches */
	bool          allow_out_of_bounds;
	bool          changed;    /**< indicates whether a change was performed */
	ir_nodeset_t  processed;
50
51
} walk_env_t;

52
typedef struct case_data_t {
53
54
55
56
	long     value;
	ir_node *target;
} case_data_t;

57
typedef struct cond_env_t {
Moritz Kroll's avatar
Moritz Kroll committed
58
	ir_node  *sel;
59
60
61
62
	long      switch_min;
	long      switch_max;
	ir_node  *default_block;
	unsigned  num_cases;
63
	ir_node **defusers;           /**< the Projs pointing to the default case */
64
} cond_env_t;
65

66
static void analyse_switch(cond_env_t *env, ir_node *cond)
67
{
68
69
70
71
72
	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;
73
74
75
76
77
	int      i;
	ir_node *proj;

	foreach_out_irn(cond, i, proj) {
		long pn = get_Proj_proj(proj);
78
79
80
81
		if (pn == default_pn) {
			ir_node *target = get_irn_out(proj, 0);
			assert(default_block == NULL || default_block == target);
			default_block = target;
82
			continue;
83
		}
84

85
		if (pn < switch_min)
86
			switch_min = pn;
87
		if (pn > switch_max)
88
			switch_max = pn;
89
		++num_cases;
90
	}
91
	assert(default_block != NULL);
92

93
94
95
96
	env->switch_min    = switch_min;
	env->switch_max    = switch_max;
	env->num_cases     = num_cases;
	env->default_block = default_block;
97
98
99
100
}

static int casecmp(const void *a, const void *b)
{
101
102
	const case_data_t *cda = (const case_data_t*)a;
	const case_data_t *cdb = (const case_data_t*)b;
103
104
105
106
107
108
109
110

	/*
	 * Enforce unsigned sorting. Signed comparison will behave differently for
	 * 32-bit values, depending on sizeof(long). This will make the resulting
	 * array deterministic.
	 */
	return ((unsigned long)cda->value > (unsigned long)cdb->value) -
	       ((unsigned long)cda->value < (unsigned long)cdb->value);
111
112
113
114
115
}

/**
 * Creates an if cascade realizing binary search.
 */
116
static void create_if_cascade(cond_env_t *env, dbg_info *dbgi, ir_node *block,
117
                              case_data_t *curcases, unsigned numcases)
118
{
119
	ir_graph *irg = get_irn_irg(block);
120
121
122
    ir_mode  *cmp_mode;
    ir_node  *cmp_sel;
    ir_node  *sel_block;
123
124
125
126
127
128
129
130
131
132
133
134

    /* 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.
     */
135
    if (mode_is_signed(cmp_mode)) {
136
137
138
139
        cmp_mode = find_unsigned_mode(cmp_mode);
        cmp_sel  = new_r_Conv(sel_block, cmp_sel, cmp_mode);
    }

140
141
	if (numcases == 0) {
		/* zero cases: "goto default;" */
142
		ARR_APP1(ir_node*, env->defusers, new_r_Jmp(block));
143
	} else if (numcases == 1) {
144
		/* only one case: "if (sel == val) goto target else goto default;" */
145
		ir_node *val       = new_r_Const_long(irg, cmp_mode, curcases[0].value);
146
147
148
		ir_node *cmp       = new_rd_Cmp(dbgi, block, cmp_sel, val,
		                                ir_relation_equal);
		ir_node *cond      = new_rd_Cond(dbgi, block, cmp);
149
150
151
152
		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);
153
		ARR_APP1(ir_node*, env->defusers, falseproj);
154
	} else if (numcases == 2) {
155
		/* only two cases: "if (sel == val[0]) goto target[0];" */
156
		ir_node *val       = new_r_Const_long(irg, cmp_mode, curcases[0].value);
157
158
159
		ir_node *cmp       = new_rd_Cmp(dbgi, block, cmp_sel, val,
		                                ir_relation_equal);
		ir_node *cond      = new_rd_Cond(dbgi, block, cmp);
160
161
		ir_node *trueproj  = new_r_Proj(cond, mode_X, pn_Cond_true);
		ir_node *falseproj = new_r_Proj(cond, mode_X, pn_Cond_false);
162
163
164
		ir_node *in[1];
		ir_node *neblock;

165
166
167
168
		set_Block_cfgpred(curcases[0].target, 0, trueproj);

		in[0] = falseproj;
		neblock = new_r_Block(irg, 1, in);
169

170
		/* second part: "else if (sel == val[1]) goto target[1] else goto default;" */
171
		val       = new_r_Const_long(irg, cmp_mode, curcases[1].value);
172
173
		cmp       = new_rd_Cmp(dbgi, neblock, cmp_sel, val, ir_relation_equal);
		cond      = new_rd_Cond(dbgi, neblock, cmp);
174
175
176
		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);
177
		ARR_APP1(ir_node*, env->defusers, falseproj);
178
179
180
	} else {
		/* recursive case: split cases in the middle */
		int midcase = numcases / 2;
181
182
		ir_node *val  = new_r_Const_long(irg, cmp_mode,
		                                 curcases[midcase].value);
183
184
		ir_node *cmp  = new_rd_Cmp(dbgi, block, cmp_sel, val, ir_relation_less);
		ir_node *cond = new_rd_Cond(dbgi, block, cmp);
185
186
187
188
		ir_node *in[1];
		ir_node *ltblock;
		ir_node *geblock;

189
190
		in[0]   = new_r_Proj(cond, mode_X, pn_Cond_true);
		ltblock = new_r_Block(irg, 1, in);
191

192
193
		in[0]   = new_r_Proj(cond, mode_X, pn_Cond_false);
		geblock = new_r_Block(irg, 1, in);
194

195
196
197
		create_if_cascade(env, dbgi, ltblock, curcases, midcase);
		create_if_cascade(env, dbgi, geblock, curcases + midcase,
		                  numcases - midcase);
198
199
200
	}
}

201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
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;
218
	size_t         n_default_preds;
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
	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;
Matthias Braun's avatar
Matthias Braun committed
235
		set_Cond_selector(cond, sel);
236
237
238
239
	}

	/* check for out-of-bounds */
	max_const  = new_r_Const_long(irg, cmp_mode, env->switch_max);
240
	cmp        = new_rd_Cmp(dbgi, block, sel, max_const, ir_relation_less_equal);
241
	oob_cond   = new_rd_Cond(dbgi, block, cmp);
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
	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) {
274
		size_t i;
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292

		/* 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);
}

293
294
295
296
297
/**
 * Block-Walker: searches for Cond nodes with a non-boolean mode
 */
static void find_cond_nodes(ir_node *block, void *ctx)
{
298
	walk_env_t  *env = (walk_env_t *)ctx;
299
300
301
302
303
	ir_node     *projx;
	ir_node     *cond;
	ir_node     *sel;
	ir_mode     *sel_mode;
	long         default_pn;
304
305
306
	int          i;
	unsigned     j = 0;
	unsigned     numcases;
307
308
309
310
	ir_node     *proj;
	case_data_t *cases;
	ir_node     *condblock;
	ir_node     *defblock = NULL;
311
	dbg_info    *dbgi;
312
313
	cond_env_t   cond_env;
	unsigned long spare;
314

315
316
	/* because we split critical blocks only blocks with 1 predecessors may
	 * contain Proj->Cond nodes */
317
	if (get_Block_n_cfgpreds(block) != 1)
318
319
320
		return;

	projx = get_Block_cfgpred(block, 0);
321
	if (!is_Proj(projx))
322
323
324
325
		return;
	assert(get_irn_mode(projx) == mode_X);

	cond = get_Proj_pred(projx);
326
	if (!is_Cond(cond))
327
328
329
330
331
		return;

	sel      = get_Cond_selector(cond);
	sel_mode = get_irn_mode(sel);

332
	if (sel_mode == mode_b)
333
334
		return;

335
336
337
338
	if (ir_nodeset_contains(&env->processed, cond))
		return;
	ir_nodeset_insert(&env->processed, cond);

339
340
341
342
	/* 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);

343
	analyse_switch(&cond_env, cond);
344

345
346
347
348
349
350
351
352
353
354
355
356
357
358
	/*
	 * 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;
		}
359
		return;
360
	}
361
362
363
364
365

	/*
	 * Switch should be transformed into an if cascade.
	 * So first order the cases, so we can do a binary search on them.
	 */
366
	env->changed = true;
367

368
369
	numcases = get_irn_n_outs(cond) - 1; /* does not contain default case */
	cases    = XMALLOCN(case_data_t, numcases);
370

371
372
373
	default_pn        = get_Cond_default_proj(cond);
	cond_env.sel      = sel;
	cond_env.defusers = NEW_ARR_F(ir_node*, 0);
374
375
376

	foreach_out_irn(cond, i, proj) {
		long pn = get_Proj_proj(proj);
Moritz Kroll's avatar
Moritz Kroll committed
377
		ir_node *target = get_irn_out(proj, 0);
378
		assert(get_Block_n_cfgpreds(target) == 1);
Moritz Kroll's avatar
Moritz Kroll committed
379

380
		if (pn == default_pn) {
Moritz Kroll's avatar
Moritz Kroll committed
381
			defblock = target;
382
383
384
385
			continue;
		}

		cases[j].value  = pn;
Moritz Kroll's avatar
Moritz Kroll committed
386
		cases[j].target = target;
387
388
		j++;
	}
389
390
391
392
	assert(j == numcases);

	if (defblock == NULL)
		panic("Switch %+F has no default proj", cond);
Moritz Kroll's avatar
Moritz Kroll committed
393

394
	qsort(cases, numcases, sizeof(cases[0]), casecmp);
395
396
397

	/* Now create the if cascade */
	condblock = get_nodes_block(cond);
398
	dbgi      = get_irn_dbg_info(cond);
399
	create_if_cascade(&cond_env, dbgi, condblock, cases, numcases);
Moritz Kroll's avatar
Moritz Kroll committed
400
401

	/* Connect new default case users */
402
	set_irn_in(defblock, ARR_LEN(cond_env.defusers), cond_env.defusers);
403
404

	xfree(cases);
405
	DEL_ARR_F(cond_env.defusers);
406
407
}

408
void lower_switch(ir_graph *irg, unsigned spare_size, int allow_out_of_bounds)
409
410
{
	walk_env_t env;
411
412
	env.changed             = false;
	env.spare_size          = spare_size;
413
414
	env.allow_out_of_bounds = allow_out_of_bounds;
	ir_nodeset_init(&env.processed);
415

Moritz Kroll's avatar
Moritz Kroll committed
416
	remove_critical_cf_edges(irg);
417
418
419
	assure_irg_outs(irg);

	irg_block_walk_graph(irg, find_cond_nodes, NULL, &env);
420
	ir_nodeset_destroy(&env.processed);
421

422
	if (env.changed) {
423
424
425
426
427
		/* control flow changed */
		set_irg_doms_inconsistent(irg);
		set_irg_extblk_inconsistent(irg);
	}
}