lower_switch.c 12.6 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
146
147
148
149
150
151
152
		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_node *proj      = new_r_Proj(cmp, mode_b, pn_Cmp_Eq);
		ir_node *cond      = new_rd_Cond(dbgi, block, proj);
		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
157
158
159
160
161
		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_node *proj      = new_r_Proj(cmp, mode_b, pn_Cmp_Eq);
		ir_node *cond      = new_rd_Cond(dbgi, block, proj);
		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
172
173
174
175
176
177
		val       = new_r_Const_long(irg, cmp_mode, curcases[1].value);
		cmp       = new_rd_Cmp(dbgi, neblock, cmp_sel, val);
		proj      = new_r_Proj(cmp, mode_b, pn_Cmp_Eq);
		cond      = new_rd_Cond(dbgi, neblock, proj);
		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);
178
		ARR_APP1(ir_node*, env->defusers, falseproj);
179
180
181
	} else {
		/* recursive case: split cases in the middle */
		int midcase = numcases / 2;
182
183
184
185
186
		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_node *proj = new_r_Proj(cmp, mode_b, pn_Cmp_Lt);
		ir_node *cond = new_rd_Cond(dbgi, block, proj);
187
188
189
190
		ir_node *in[1];
		ir_node *ltblock;
		ir_node *geblock;

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

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

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

203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
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       *proj_cmp;
	ir_node       *oob_cond;
	ir_node       *in[1];
	ir_node       *new_block;
221
	size_t         n_default_preds;
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
	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
238
		set_Cond_selector(cond, sel);
239
240
241
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
274
275
276
277
	}

	/* 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);
	proj_cmp   = new_r_Proj(cmp, mode_b, pn_Cmp_Le);
	oob_cond   = new_rd_Cond(dbgi, block, proj_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) {
278
		size_t i;
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296

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

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

319
320
	/* because we split critical blocks only blocks with 1 predecessors may
	 * contain Proj->Cond nodes */
321
	if (get_Block_n_cfgpreds(block) != 1)
322
323
324
		return;

	projx = get_Block_cfgpred(block, 0);
325
	if (!is_Proj(projx))
326
327
328
329
		return;
	assert(get_irn_mode(projx) == mode_X);

	cond = get_Proj_pred(projx);
330
	if (!is_Cond(cond))
331
332
333
334
335
		return;

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

336
	if (sel_mode == mode_b)
337
338
		return;

339
340
341
342
	if (ir_nodeset_contains(&env->processed, cond))
		return;
	ir_nodeset_insert(&env->processed, cond);

343
344
345
346
	/* 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);

347
	analyse_switch(&cond_env, cond);
348

349
350
351
352
353
354
355
356
357
358
359
360
361
362
	/*
	 * 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;
		}
363
		return;
364
	}
365
366
367
368
369

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

372
373
	numcases = get_irn_n_outs(cond) - 1; /* does not contain default case */
	cases    = XMALLOCN(case_data_t, numcases);
374

375
376
377
	default_pn        = get_Cond_default_proj(cond);
	cond_env.sel      = sel;
	cond_env.defusers = NEW_ARR_F(ir_node*, 0);
378
379
380

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

384
		if (pn == default_pn) {
Moritz Kroll's avatar
Moritz Kroll committed
385
			defblock = target;
386
387
388
389
			continue;
		}

		cases[j].value  = pn;
Moritz Kroll's avatar
Moritz Kroll committed
390
		cases[j].target = target;
391
392
		j++;
	}
393
394
395
396
	assert(j == numcases);

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

398
	qsort(cases, numcases, sizeof(cases[0]), casecmp);
399
400
401

	/* Now create the if cascade */
	condblock = get_nodes_block(cond);
402
	dbgi      = get_irn_dbg_info(cond);
403
	create_if_cascade(&cond_env, dbgi, condblock, cases, numcases);
Moritz Kroll's avatar
Moritz Kroll committed
404
405

	/* Connect new default case users */
406
	set_irn_in(defblock, ARR_LEN(cond_env.defusers), cond_env.defusers);
407
408

	xfree(cases);
409
	DEL_ARR_F(cond_env.defusers);
410
411
}

412
void lower_switch(ir_graph *irg, unsigned spare_size, int allow_out_of_bounds)
413
414
{
	walk_env_t env;
415
416
	env.changed             = false;
	env.spare_size          = spare_size;
417
418
	env.allow_out_of_bounds = allow_out_of_bounds;
	ir_nodeset_init(&env.processed);
419

Moritz Kroll's avatar
Moritz Kroll committed
420
	remove_critical_cf_edges(irg);
421
422
423
	assure_irg_outs(irg);

	irg_block_walk_graph(irg, find_cond_nodes, NULL, &env);
424
	ir_nodeset_destroy(&env.processed);
425

426
	if (env.changed) {
427
428
429
430
431
432
433
		/* control flow changed */
		set_irg_outs_inconsistent(irg);
		set_irg_doms_inconsistent(irg);
		set_irg_extblk_inconsistent(irg);
		set_irg_loopinfo_inconsistent(irg);
	}
}