lower_switch.c 9.3 KB
Newer Older
1
2
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
28
/*
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
 *
 * 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"

29
30
#include <limits.h>

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
39
40
41
42

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

typedef struct walk_env {
Moritz Kroll's avatar
Moritz Kroll committed
43
	unsigned         spare_size;        /**< the allowed spare size for table switches */
44
45
46
47
48
49
50
51
	int              changed;           /**< indicates whether a change was performed */
} walk_env_t;

typedef struct case_data {
	long     value;
	ir_node *target;
} case_data_t;

Moritz Kroll's avatar
Moritz Kroll committed
52
53
54
55
56
typedef struct ifcas_env {
	ir_node  *sel;
	int       defindex;
	ir_node **defusers;                 /**< the Projs pointing to the default case */
} ifcas_env_t;
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

/**
 * Evaluate a switch and decide whether we should build a table switch.
 *
 * @param cond       The Cond node representing the switch.
 * @param spare_size Allowed spare size for table switches in machine words.
 *                   (Default in edgfe: 128)
 */
static int should_do_table_switch(ir_node *cond, unsigned spare_size)
{
	long     default_pn;
	int      i;
	ir_node *proj;
	long switch_min = LONG_MAX, switch_max = LONG_MIN;
	unsigned long spare, num_cases = 0;

	/* TODO: Minimum size for jump table? */
74
	if (get_irn_n_outs(cond) <= 4)
Moritz Kroll's avatar
Moritz Kroll committed
75
		return 0;
76

77
	default_pn = get_Cond_default_proj(cond);
78
79
80

	foreach_out_irn(cond, i, proj) {
		long pn = get_Proj_proj(proj);
81
		if (pn == default_pn)
82
83
			continue;

84
		if (pn < switch_min)
85
			switch_min = pn;
86
		if (pn > switch_max)
87
			switch_max = pn;
88
		++num_cases;
89
90
91
92
93
94
95
96
97
98
99
100
	}

	/*
	 * 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) switch_max - (unsigned long) switch_min - num_cases + 1;
	return spare < spare_size;
}

static int casecmp(const void *a, const void *b)
{
101
102
	const case_data_t *cda = a;
	const case_data_t *cdb = 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.
 */
Moritz Kroll's avatar
Moritz Kroll committed
116
117
static void create_if_cascade(ifcas_env_t *env, ir_node *curblock,
                              case_data_t *curcases, int numcases)
118
{
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
    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);
    }

140
	assert(numcases >= 0);
141

142
143
	set_cur_block(curblock);

144
145
146
147
	if (numcases == 0) {
		/* zero cases: "goto default;" */
		env->defusers[env->defindex++] = new_Jmp();
	} else if (numcases == 1) {
148
		/* only one case: "if(sel == val) goto target else goto default;" */
149
150
		ir_node *val  = new_Const_long(cmp_mode, curcases[0].value);
		ir_node *cmp  = new_Cmp(cmp_sel, val);
151
152
		ir_node *proj = new_Proj(cmp, mode_b, pn_Cmp_Eq);
		ir_node *cond = new_Cond(proj);
Moritz Kroll's avatar
Moritz Kroll committed
153
154
		set_Block_cfgpred(curcases[0].target, 0, new_Proj(cond, mode_X, pn_Cond_true));
		env->defusers[env->defindex++] = new_Proj(cond, mode_X, pn_Cond_false);
155
	} else if (numcases == 2) {
156
		/* only two cases: "if(sel == val[0]) goto target[0];" */
157
158
		ir_node *val  = new_Const_long(cmp_mode, curcases[0].value);
		ir_node *cmp  = new_Cmp(cmp_sel, val);
159
160
161
162
163
		ir_node *proj = new_Proj(cmp, mode_b, pn_Cmp_Eq);
		ir_node *cond = new_Cond(proj);
		ir_node *in[1];
		ir_node *neblock;

Moritz Kroll's avatar
Moritz Kroll committed
164
		set_Block_cfgpred(curcases[0].target, 0, new_Proj(cond, mode_X, pn_Cond_true));
165
166
		in[0] = new_Proj(cond, mode_X, pn_Cond_false);
		neblock = new_Block(1, in);
Matthias Braun's avatar
Matthias Braun committed
167
		set_cur_block(neblock);
168
169

		/* second part: "else if(sel == val[1]) goto target[1] else goto default;" */
170
171
		val  = new_Const_long(cmp_mode, curcases[1].value);
		cmp  = new_Cmp(cmp_sel, val);
172
173
		proj = new_Proj(cmp, mode_b, pn_Cmp_Eq);
		cond = new_Cond(proj);
Moritz Kroll's avatar
Moritz Kroll committed
174
175
		set_Block_cfgpred(curcases[1].target, 0, new_Proj(cond, mode_X, pn_Cond_true));
		env->defusers[env->defindex++] = new_Proj(cond, mode_X, pn_Cond_false);
176
177
178
	} else {
		/* recursive case: split cases in the middle */
		int midcase = numcases / 2;
179
180
		ir_node *val  = new_Const_long(cmp_mode, curcases[midcase].value);
		ir_node *cmp  = new_Cmp(cmp_sel, val);
181
182
183
184
185
186
187
188
189
190
191
192
		ir_node *proj = new_Proj(cmp, mode_b, pn_Cmp_Lt);
		ir_node *cond = new_Cond(proj);
		ir_node *in[1];
		ir_node *ltblock;
		ir_node *geblock;

		in[0] = new_Proj(cond, mode_X, pn_Cond_true);
		ltblock = new_Block(1, in);

		set_cur_block(curblock);
		in[0] = new_Proj(cond, mode_X, pn_Cond_false);
		geblock = new_Block(1, in);
Matthias Braun's avatar
Matthias Braun committed
193
		set_cur_block(geblock);
194

Moritz Kroll's avatar
Moritz Kroll committed
195
196
		create_if_cascade(env, ltblock, curcases, midcase);
		create_if_cascade(env, geblock, curcases + midcase, numcases - midcase);
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
	}
}

/**
 * Block-Walker: searches for Cond nodes with a non-boolean mode
 */
static void find_cond_nodes(ir_node *block, void *ctx)
{
	walk_env_t  *env = ctx;
	ir_node     *projx;
	ir_node     *cond;
	ir_node     *sel;
	ir_mode     *sel_mode;
	long         default_pn;
	int          i, j = 0, numcases;
	ir_node     *proj;
	case_data_t *cases;
	ir_node     *condblock;
	ir_node     *defblock = NULL;
Moritz Kroll's avatar
Moritz Kroll committed
216
	ifcas_env_t  ifcas_env;
217

218
	if (get_Block_n_cfgpreds(block) != 1)
219
220
221
		return;

	projx = get_Block_cfgpred(block, 0);
222
	if (!is_Proj(projx))
223
224
225
226
		return;
	assert(get_irn_mode(projx) == mode_X);

	cond = get_Proj_pred(projx);
227
	if (!is_Cond(cond))
228
229
230
231
232
		return;

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

233
	if (sel_mode == mode_b)    /* not a switch? */
234
235
		return;

236
	if (should_do_table_switch(cond, env->spare_size))
237
238
239
240
241
242
		return;

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

	numcases = get_irn_n_outs(cond) - 1;      // does not contain default case
246
	NEW_ARR_A(case_data_t, cases, numcases);
247

248
	default_pn = get_Cond_default_proj(cond);
Moritz Kroll's avatar
Moritz Kroll committed
249
250
251
	ifcas_env.sel = sel;
	ifcas_env.defindex = 0;
	NEW_ARR_A(ir_node*, ifcas_env.defusers, numcases);
252
253
254

	foreach_out_irn(cond, i, proj) {
		long pn = get_Proj_proj(proj);
Moritz Kroll's avatar
Moritz Kroll committed
255
256
257
		ir_node *target = get_irn_out(proj, 0);
		assert(get_Block_n_cfgpreds(target) == 1 && "Encountered critical edge in switch");

258
		if (pn == default_pn) {
Moritz Kroll's avatar
Moritz Kroll committed
259
			defblock = target;
260
261
262
263
			continue;
		}

		cases[j].value  = pn;
Moritz Kroll's avatar
Moritz Kroll committed
264
		cases[j].target = target;
265
266
		j++;
	}
Moritz Kroll's avatar
Moritz Kroll committed
267

268
269
270
271
272
	assert(defblock != NULL && "Switch without default proj");
	qsort(cases, numcases, sizeof(*cases), casecmp);

	/* Now create the if cascade */
	condblock = get_nodes_block(cond);
Moritz Kroll's avatar
Moritz Kroll committed
273
274
275
276
	create_if_cascade(&ifcas_env, condblock, cases, numcases);

	/* Connect new default case users */
	set_irn_in(defblock, ifcas_env.defindex, ifcas_env.defusers);
277
278
279
280
281
282
283
284
285
286
}

/**
 * Lowers all Switches (Cond nodes with non-boolean mode) depending on spare_size.
 * They will either remain the same or be converted into if-cascades.
 *
 * @param irg        The ir graph to be lowered.
 * @param spare_size Allowed spare size for table switches in machine words.
 *                   (Default in edgfe: 128)
 */
287
void lower_switch(ir_graph *irg, unsigned spare_size)
288
289
290
291
292
293
{
	walk_env_t env;
	ir_graph *rem = current_ir_graph;

	current_ir_graph = irg;

294
	env.changed    = 0;
295
296
	env.spare_size = spare_size;

Moritz Kroll's avatar
Moritz Kroll committed
297
	remove_critical_cf_edges(irg);
298
299
300
301
	assure_irg_outs(irg);

	irg_block_walk_graph(irg, find_cond_nodes, NULL, &env);

302
	if (env.changed) {
303
304
305
306
307
308
309
310
		/* control flow changed */
		set_irg_outs_inconsistent(irg);
		set_irg_doms_inconsistent(irg);
		set_irg_extblk_inconsistent(irg);
		set_irg_loopinfo_inconsistent(irg);
	}
	current_ir_graph = rem;
}
Michael Beck's avatar
Michael Beck committed
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334

struct pass_t {
	ir_graph_pass_t pass;
	unsigned        spare_size;
};

/**
 * Wrapper for running lower_switch() as a pass.
 */
static int pass_wrapper(ir_graph *irg, void *context) {
	struct pass_t *pass = context;

	lower_switch(irg, pass->spare_size);
	return 0;
}

/* creates a pass for lower_switch */
ir_graph_pass_t *lower_switch_pass(const char *name, unsigned spare_size) {
	struct pass_t *pass = XMALLOCZ(struct pass_t);

	pass->spare_size = spare_size;
	return def_graph_pass_constructor(
		&pass->pass, name ? name : "lower_switch", pass_wrapper);
}