lower_switch.c 9.38 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
/*
 * 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"

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

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

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

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

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

/**
 * 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)
 */
67
static bool should_do_table_switch(ir_node *cond, unsigned spare_size)
68
69
70
71
{
	long     default_pn;
	int      i;
	ir_node *proj;
72
73
74
75
	long switch_min = LONG_MAX;
	long switch_max = LONG_MIN;
	unsigned long spare;
	unsigned long num_cases = 0;
76
77

	/* TODO: Minimum size for jump table? */
78
	if (get_irn_n_outs(cond) <= 4)
79
		return false;
80

81
	default_pn = get_Cond_default_proj(cond);
82
83
84

	foreach_out_irn(cond, i, proj) {
		long pn = get_Proj_proj(proj);
85
		if (pn == default_pn)
86
87
			continue;

88
		if (pn < switch_min)
89
			switch_min = pn;
90
		if (pn > switch_max)
91
			switch_max = pn;
92
		++num_cases;
93
94
95
96
97
98
99
100
101
102
103
104
	}

	/*
	 * 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)
{
105
106
	const case_data_t *cda = a;
	const case_data_t *cdb = b;
107
108
109
110
111
112
113
114

	/*
	 * 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);
115
116
117
118
119
}

/**
 * Creates an if cascade realizing binary search.
 */
120
121
static void create_if_cascade(ifcas_env_t *env, dbg_info *dbgi, ir_node *block,
                              case_data_t *curcases, unsigned numcases)
122
{
123
	ir_graph *irg = get_irn_irg(block);
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
    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.
     */
139
    if (mode_is_signed(cmp_mode)) {
140
141
142
143
        cmp_mode = find_unsigned_mode(cmp_mode);
        cmp_sel  = new_r_Conv(sel_block, cmp_sel, cmp_mode);
    }

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
151
152
153
154
155
156
157
		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);
		env->defusers[env->defindex++] = falseproj;
158
	} else if (numcases == 2) {
159
		/* only two cases: "if (sel == val[0]) goto target[0];" */
160
161
162
163
164
165
		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);
166
167
168
		ir_node *in[1];
		ir_node *neblock;

169
170
171
172
		set_Block_cfgpred(curcases[0].target, 0, trueproj);

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

174
		/* second part: "else if (sel == val[1]) goto target[1] else goto default;" */
175
176
177
178
179
180
181
182
		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);
		env->defusers[env->defindex++] = falseproj;
183
184
185
	} else {
		/* recursive case: split cases in the middle */
		int midcase = numcases / 2;
186
187
188
189
190
		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);
191
192
193
194
		ir_node *in[1];
		ir_node *ltblock;
		ir_node *geblock;

195
196
		in[0]   = new_r_Proj(cond, mode_X, pn_Cond_true);
		ltblock = new_r_Block(irg, 1, in);
197

198
199
		in[0]   = new_r_Proj(cond, mode_X, pn_Cond_false);
		geblock = new_r_Block(irg, 1, in);
200

201
202
203
		create_if_cascade(env, dbgi, ltblock, curcases, midcase);
		create_if_cascade(env, dbgi, geblock, curcases + midcase,
		                  numcases - midcase);
204
205
206
207
208
209
210
211
212
213
214
215
216
217
	}
}

/**
 * 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;
218
219
220
	int          i;
	unsigned     j = 0;
	unsigned     numcases;
221
222
223
224
	ir_node     *proj;
	case_data_t *cases;
	ir_node     *condblock;
	ir_node     *defblock = NULL;
225
	dbg_info    *dbgi;
Moritz Kroll's avatar
Moritz Kroll committed
226
	ifcas_env_t  ifcas_env;
227

228
229
	/* because we split critical blocks only blocks with 1 predecessors may
	 * contain Proj->Cond nodes */
230
	if (get_Block_n_cfgpreds(block) != 1)
231
232
233
		return;

	projx = get_Block_cfgpred(block, 0);
234
	if (!is_Proj(projx))
235
236
237
238
		return;
	assert(get_irn_mode(projx) == mode_X);

	cond = get_Proj_pred(projx);
239
	if (!is_Cond(cond))
240
241
242
243
244
		return;

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

245
	if (sel_mode == mode_b)
246
247
		return;

248
249
250
251
252
253
254
255
	/* 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);

	/* ok, we have found a switch cond */

	/* no need to do anything if backend handles out-of-bounds and the switch
	 * is small enough */
256
	if (should_do_table_switch(cond, env->spare_size))
257
258
259
260
261
262
		return;

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

265
266
	numcases = get_irn_n_outs(cond) - 1; /* does not contain default case */
	cases    = XMALLOCN(case_data_t, numcases);
267

268
269
	default_pn         = get_Cond_default_proj(cond);
	ifcas_env.sel      = sel;
Moritz Kroll's avatar
Moritz Kroll committed
270
	ifcas_env.defindex = 0;
271
	ifcas_env.defusers = XMALLOCN(ir_node*, numcases);
272
273
274

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

278
		if (pn == default_pn) {
Moritz Kroll's avatar
Moritz Kroll committed
279
			defblock = target;
280
281
282
283
			continue;
		}

		cases[j].value  = pn;
Moritz Kroll's avatar
Moritz Kroll committed
284
		cases[j].target = target;
285
286
		j++;
	}
287
288
289
290
	assert(j == numcases);

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

292
	qsort(cases, numcases, sizeof(cases[0]), casecmp);
293
294
295

	/* Now create the if cascade */
	condblock = get_nodes_block(cond);
296
297
	dbgi      = get_irn_dbg_info(cond);
	create_if_cascade(&ifcas_env, dbgi, condblock, cases, numcases);
Moritz Kroll's avatar
Moritz Kroll committed
298
299
300

	/* Connect new default case users */
	set_irn_in(defblock, ifcas_env.defindex, ifcas_env.defusers);
301
302
303

	xfree(cases);
	xfree(ifcas_env.defusers);
304
305
}

306
void lower_switch(ir_graph *irg, unsigned spare_size)
307
308
{
	walk_env_t env;
309
310
	env.changed             = false;
	env.spare_size          = spare_size;
311

Moritz Kroll's avatar
Moritz Kroll committed
312
	remove_critical_cf_edges(irg);
313
314
315
316
	assure_irg_outs(irg);

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

317
	if (env.changed) {
318
319
320
321
322
323
324
		/* control flow changed */
		set_irg_outs_inconsistent(irg);
		set_irg_doms_inconsistent(irg);
		set_irg_extblk_inconsistent(irg);
		set_irg_loopinfo_inconsistent(irg);
	}
}