lower_switch.c 7.76 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
29
30
/*
 * 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$
 */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

31
32
#include <limits.h>

33
#include "ircons.h"
Moritz Kroll's avatar
Moritz Kroll committed
34
#include "irgopt.h"
35
36
37
38
39
40
41
42
#include "irgwalk.h"
#include "irnode_t.h"
#include "irouts.h"

#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
52
	struct obstack   obst;              /**< the obstack where data is allocated on */
	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
53
54
55
56
57
typedef struct ifcas_env {
	ir_node  *sel;
	int       defindex;
	ir_node **defusers;                 /**< the Projs pointing to the default case */
} ifcas_env_t;
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

/**
 * 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? */
	if(get_irn_n_outs(cond) <= 4)
Moritz Kroll's avatar
Moritz Kroll committed
76
		return 0;
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

	default_pn = get_Cond_defaultProj(cond);

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

		if(pn < switch_min)
			switch_min = pn;
		if(pn > switch_max)
			switch_max = pn;
		num_cases++;
	}

	/*
	 * 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)
{
	return ((case_data_t *) a)->value - ((case_data_t *) b)->value;
}

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

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

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

Moritz Kroll's avatar
Moritz Kroll committed
160
161
		create_if_cascade(env, ltblock, curcases, midcase);
		create_if_cascade(env, geblock, curcases + midcase, numcases - midcase);
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
	}
}

/**
 * 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
181
	ifcas_env_t  ifcas_env;
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212

	if(get_Block_n_cfgpreds(block) != 1)
		return;

	projx = get_Block_cfgpred(block, 0);
	if(!is_Proj(projx))
		return;
	assert(get_irn_mode(projx) == mode_X);

	cond = get_Proj_pred(projx);
	if(!is_Cond(cond))
		return;

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

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

	if(should_do_table_switch(cond, env->spare_size))
		return;

	/*
	 * Switch should be transformed into an if cascade.
	 * So first order the cases, so we can do a binary search on them.
	 */

	numcases = get_irn_n_outs(cond) - 1;      // does not contain default case
	cases    = obstack_alloc(&env->obst, numcases * sizeof(*cases));

	default_pn = get_Cond_defaultProj(cond);
Moritz Kroll's avatar
Moritz Kroll committed
213
214
215
	ifcas_env.sel = sel;
	ifcas_env.defindex = 0;
	NEW_ARR_A(ir_node*, ifcas_env.defusers, numcases);
216
217
218

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

222
223
		if(pn == default_pn)
		{
Moritz Kroll's avatar
Moritz Kroll committed
224
			defblock = target;
225
226
227
228
			continue;
		}

		cases[j].value  = pn;
Moritz Kroll's avatar
Moritz Kroll committed
229
		cases[j].target = target;
230
231
		j++;
	}
Moritz Kroll's avatar
Moritz Kroll committed
232

233
234
235
236
237
	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
238
239
240
241
	create_if_cascade(&ifcas_env, condblock, cases, numcases);

	/* Connect new default case users */
	set_irn_in(defblock, ifcas_env.defindex, ifcas_env.defusers);
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263

	obstack_free(&env->obst, cases);
}

/**
 * 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)
 */
void lower_Switch(ir_graph *irg, unsigned spare_size)
{
	walk_env_t env;
	ir_graph *rem = current_ir_graph;

	current_ir_graph = irg;

	obstack_init(&env.obst);
	env.spare_size = spare_size;

Moritz Kroll's avatar
Moritz Kroll committed
264
	remove_critical_cf_edges(irg);
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
	assure_irg_outs(irg);

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

	if(env.changed) {
		/* control flow changed */
		set_irg_outs_inconsistent(irg);
		set_irg_doms_inconsistent(irg);
		set_irg_extblk_inconsistent(irg);
		set_irg_loopinfo_inconsistent(irg);
	}

	obstack_free(&env.obst, NULL);
	current_ir_graph = rem;
}