lower_switch.c 8.42 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
	return (cda->value > cdb->value) - (cda->value < cdb->value);
104
105
106
107
108
}

/**
 * Creates an if cascade realizing binary search.
 */
Moritz Kroll's avatar
Moritz Kroll committed
109
110
static void create_if_cascade(ifcas_env_t *env, ir_node *curblock,
                              case_data_t *curcases, int numcases)
111
{
112
	assert(numcases >= 0);
113

114
115
	set_cur_block(curblock);

116
117
118
119
	if (numcases == 0) {
		/* zero cases: "goto default;" */
		env->defusers[env->defindex++] = new_Jmp();
	} else if (numcases == 1) {
120
		/* only one case: "if(sel == val) goto target else goto default;" */
Moritz Kroll's avatar
Moritz Kroll committed
121
122
		ir_node *val  = new_Const_long(get_irn_mode(env->sel), curcases[0].value);
		ir_node *cmp  = new_Cmp(env->sel, val);
123
124
		ir_node *proj = new_Proj(cmp, mode_b, pn_Cmp_Eq);
		ir_node *cond = new_Cond(proj);
Moritz Kroll's avatar
Moritz Kroll committed
125
126
		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);
127
	} else if (numcases == 2) {
128
		/* only two cases: "if(sel == val[0]) goto target[0];" */
Moritz Kroll's avatar
Moritz Kroll committed
129
130
		ir_node *val  = new_Const_long(get_irn_mode(env->sel), curcases[0].value);
		ir_node *cmp  = new_Cmp(env->sel, val);
131
132
133
134
135
		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
136
		set_Block_cfgpred(curcases[0].target, 0, new_Proj(cond, mode_X, pn_Cond_true));
137
138
		in[0] = new_Proj(cond, mode_X, pn_Cond_false);
		neblock = new_Block(1, in);
Matthias Braun's avatar
Matthias Braun committed
139
		set_cur_block(neblock);
140
141

		/* second part: "else if(sel == val[1]) goto target[1] else goto default;" */
Moritz Kroll's avatar
Moritz Kroll committed
142
143
		val  = new_Const_long(get_irn_mode(env->sel), curcases[1].value);
		cmp  = new_Cmp(env->sel, val);
144
145
		proj = new_Proj(cmp, mode_b, pn_Cmp_Eq);
		cond = new_Cond(proj);
Moritz Kroll's avatar
Moritz Kroll committed
146
147
		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);
148
149
150
	} else {
		/* recursive case: split cases in the middle */
		int midcase = numcases / 2;
Moritz Kroll's avatar
Moritz Kroll committed
151
152
		ir_node *val  = new_Const_long(get_irn_mode(env->sel), curcases[midcase].value);
		ir_node *cmp  = new_Cmp(env->sel, val);
153
154
155
156
157
158
159
160
161
162
163
164
		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
165
		set_cur_block(geblock);
166

Moritz Kroll's avatar
Moritz Kroll committed
167
168
		create_if_cascade(env, ltblock, curcases, midcase);
		create_if_cascade(env, geblock, curcases + midcase, numcases - midcase);
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
	}
}

/**
 * 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
188
	ifcas_env_t  ifcas_env;
189

190
	if (get_Block_n_cfgpreds(block) != 1)
191
192
193
		return;

	projx = get_Block_cfgpred(block, 0);
194
	if (!is_Proj(projx))
195
196
197
198
		return;
	assert(get_irn_mode(projx) == mode_X);

	cond = get_Proj_pred(projx);
199
	if (!is_Cond(cond))
200
201
202
203
204
		return;

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

205
	if (sel_mode == mode_b)    /* not a switch? */
206
207
		return;

208
	if (should_do_table_switch(cond, env->spare_size))
209
210
211
212
213
214
		return;

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

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

220
	default_pn = get_Cond_default_proj(cond);
Moritz Kroll's avatar
Moritz Kroll committed
221
222
223
	ifcas_env.sel = sel;
	ifcas_env.defindex = 0;
	NEW_ARR_A(ir_node*, ifcas_env.defusers, numcases);
224
225
226

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

230
		if (pn == default_pn) {
Moritz Kroll's avatar
Moritz Kroll committed
231
			defblock = target;
232
233
234
235
			continue;
		}

		cases[j].value  = pn;
Moritz Kroll's avatar
Moritz Kroll committed
236
		cases[j].target = target;
237
238
		j++;
	}
Moritz Kroll's avatar
Moritz Kroll committed
239

240
241
242
243
244
	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
245
246
247
248
	create_if_cascade(&ifcas_env, condblock, cases, numcases);

	/* Connect new default case users */
	set_irn_in(defblock, ifcas_env.defindex, ifcas_env.defusers);
249
250
251
252
253
254
255
256
257
258
}

/**
 * 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)
 */
259
void lower_switch(ir_graph *irg, unsigned spare_size)
260
261
262
263
264
265
{
	walk_env_t env;
	ir_graph *rem = current_ir_graph;

	current_ir_graph = irg;

266
	env.changed    = 0;
267
268
	env.spare_size = spare_size;

Moritz Kroll's avatar
Moritz Kroll committed
269
	remove_critical_cf_edges(irg);
270
271
272
273
	assure_irg_outs(irg);

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

274
	if (env.changed) {
275
276
277
278
279
280
281
282
		/* 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
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306

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