2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Lowering of Switches if necessary or advantageous.
23 * @author Moritz Kroll
41 #define foreach_out_irn(irn, i, outirn) for (i = get_irn_n_outs(irn) - 1;\
42 i >= 0 && (outirn = get_irn_out(irn, i)); --i)
44 typedef struct walk_env {
45 unsigned spare_size; /**< the allowed spare size for table switches */
46 bool changed; /**< indicates whether a change was performed */
49 typedef struct case_data {
54 typedef struct ifcas_env {
57 ir_node **defusers; /**< the Projs pointing to the default case */
61 * Evaluate a switch and decide whether we should build a table switch.
63 * @param cond The Cond node representing the switch.
64 * @param spare_size Allowed spare size for table switches in machine words.
65 * (Default in edgfe: 128)
67 static bool should_do_table_switch(ir_node *cond, unsigned spare_size)
72 long switch_min = LONG_MAX;
73 long switch_max = LONG_MIN;
75 unsigned long num_cases = 0;
77 /* TODO: Minimum size for jump table? */
78 if (get_irn_n_outs(cond) <= 4)
81 default_pn = get_Cond_default_proj(cond);
83 foreach_out_irn(cond, i, proj) {
84 long pn = get_Proj_proj(proj);
96 * Here we have: num_cases and [switch_min, switch_max] interval.
97 * We do an if-cascade if there are too many spare numbers.
99 spare = (unsigned long) switch_max - (unsigned long) switch_min - num_cases + 1;
100 return spare < spare_size;
103 static int casecmp(const void *a, const void *b)
105 const case_data_t *cda = a;
106 const case_data_t *cdb = b;
109 * Enforce unsigned sorting. Signed comparison will behave differently for
110 * 32-bit values, depending on sizeof(long). This will make the resulting
111 * array deterministic.
113 return ((unsigned long)cda->value > (unsigned long)cdb->value) -
114 ((unsigned long)cda->value < (unsigned long)cdb->value);
118 * Creates an if cascade realizing binary search.
120 static void create_if_cascade(ifcas_env_t *env, dbg_info *dbgi, ir_node *block,
121 case_data_t *curcases, unsigned numcases)
123 ir_graph *irg = get_irn_irg(block);
128 /* Get the mode and sel node for the comparison. */
129 cmp_mode = get_irn_mode(env->sel);
131 sel_block = get_nodes_block(cmp_sel);
134 * Make sure that an unsigned comparison is used, by converting the sel
135 * node to an unsigned mode and using that mode for the constants, too.
136 * This is important, because the qsort applied to the case labels uses
137 * an unsigned comparison and both comparison methods have to match.
139 if (mode_is_signed(cmp_mode)) {
140 cmp_mode = find_unsigned_mode(cmp_mode);
141 cmp_sel = new_r_Conv(sel_block, cmp_sel, cmp_mode);
145 /* zero cases: "goto default;" */
146 env->defusers[env->defindex++] = new_Jmp();
147 } else if (numcases == 1) {
148 /* only one case: "if (sel == val) goto target else goto default;" */
149 ir_node *val = new_r_Const_long(irg, cmp_mode, curcases[0].value);
150 ir_node *cmp = new_rd_Cmp(dbgi, block, cmp_sel, val);
151 ir_node *proj = new_r_Proj(cmp, mode_b, pn_Cmp_Eq);
152 ir_node *cond = new_rd_Cond(dbgi, block, proj);
153 ir_node *trueproj = new_r_Proj(cond, mode_X, pn_Cond_true);
154 ir_node *falseproj = new_r_Proj(cond, mode_X, pn_Cond_false);
156 set_Block_cfgpred(curcases[0].target, 0, trueproj);
157 env->defusers[env->defindex++] = falseproj;
158 } else if (numcases == 2) {
159 /* only two cases: "if (sel == val[0]) goto target[0];" */
160 ir_node *val = new_r_Const_long(irg, cmp_mode, curcases[0].value);
161 ir_node *cmp = new_rd_Cmp(dbgi, block, cmp_sel, val);
162 ir_node *proj = new_r_Proj(cmp, mode_b, pn_Cmp_Eq);
163 ir_node *cond = new_rd_Cond(dbgi, block, proj);
164 ir_node *trueproj = new_r_Proj(cond, mode_X, pn_Cond_true);
165 ir_node *falseproj = new_r_Proj(cond, mode_X, pn_Cond_false);
169 set_Block_cfgpred(curcases[0].target, 0, trueproj);
172 neblock = new_r_Block(irg, 1, in);
174 /* second part: "else if (sel == val[1]) goto target[1] else goto default;" */
175 val = new_r_Const_long(irg, cmp_mode, curcases[1].value);
176 cmp = new_rd_Cmp(dbgi, neblock, cmp_sel, val);
177 proj = new_r_Proj(cmp, mode_b, pn_Cmp_Eq);
178 cond = new_rd_Cond(dbgi, neblock, proj);
179 trueproj = new_r_Proj(cond, mode_X, pn_Cond_true);
180 falseproj = new_r_Proj(cond, mode_X, pn_Cond_false);
181 set_Block_cfgpred(curcases[1].target, 0, trueproj);
182 env->defusers[env->defindex++] = falseproj;
184 /* recursive case: split cases in the middle */
185 int midcase = numcases / 2;
186 ir_node *val = new_r_Const_long(irg, cmp_mode,
187 curcases[midcase].value);
188 ir_node *cmp = new_rd_Cmp(dbgi, block, cmp_sel, val);
189 ir_node *proj = new_r_Proj(cmp, mode_b, pn_Cmp_Lt);
190 ir_node *cond = new_rd_Cond(dbgi, block, proj);
195 in[0] = new_r_Proj(cond, mode_X, pn_Cond_true);
196 ltblock = new_r_Block(irg, 1, in);
198 in[0] = new_r_Proj(cond, mode_X, pn_Cond_false);
199 geblock = new_r_Block(irg, 1, in);
201 create_if_cascade(env, dbgi, ltblock, curcases, midcase);
202 create_if_cascade(env, dbgi, geblock, curcases + midcase,
208 * Block-Walker: searches for Cond nodes with a non-boolean mode
210 static void find_cond_nodes(ir_node *block, void *ctx)
212 walk_env_t *env = ctx;
224 ir_node *defblock = NULL;
226 ifcas_env_t ifcas_env;
228 /* because we split critical blocks only blocks with 1 predecessors may
229 * contain Proj->Cond nodes */
230 if (get_Block_n_cfgpreds(block) != 1)
233 projx = get_Block_cfgpred(block, 0);
236 assert(get_irn_mode(projx) == mode_X);
238 cond = get_Proj_pred(projx);
242 sel = get_Cond_selector(cond);
243 sel_mode = get_irn_mode(sel);
245 if (sel_mode == mode_b)
248 /* the algorithms here don't work reliable for modes bigger than 32
249 * since we operate with long numbers */
250 assert(get_mode_size_bits(sel_mode) <= 32);
252 /* ok, we have found a switch cond */
254 /* no need to do anything if backend handles out-of-bounds and the switch
256 if (should_do_table_switch(cond, env->spare_size))
260 * Switch should be transformed into an if cascade.
261 * So first order the cases, so we can do a binary search on them.
265 numcases = get_irn_n_outs(cond) - 1; /* does not contain default case */
266 cases = XMALLOCN(case_data_t, numcases);
268 default_pn = get_Cond_default_proj(cond);
270 ifcas_env.defindex = 0;
271 ifcas_env.defusers = XMALLOCN(ir_node*, numcases);
273 foreach_out_irn(cond, i, proj) {
274 long pn = get_Proj_proj(proj);
275 ir_node *target = get_irn_out(proj, 0);
276 assert(get_Block_n_cfgpreds(target) == 1);
278 if (pn == default_pn) {
284 cases[j].target = target;
287 assert(j == numcases);
289 if (defblock == NULL)
290 panic("Switch %+F has no default proj", cond);
292 qsort(cases, numcases, sizeof(cases[0]), casecmp);
294 /* Now create the if cascade */
295 condblock = get_nodes_block(cond);
296 dbgi = get_irn_dbg_info(cond);
297 create_if_cascade(&ifcas_env, dbgi, condblock, cases, numcases);
299 /* Connect new default case users */
300 set_irn_in(defblock, ifcas_env.defindex, ifcas_env.defusers);
303 xfree(ifcas_env.defusers);
306 void lower_switch(ir_graph *irg, unsigned spare_size)
310 env.spare_size = spare_size;
312 remove_critical_cf_edges(irg);
313 assure_irg_outs(irg);
315 irg_block_walk_graph(irg, find_cond_nodes, NULL, &env);
318 /* control flow changed */
319 set_irg_outs_inconsistent(irg);
320 set_irg_doms_inconsistent(irg);
321 set_irg_extblk_inconsistent(irg);
322 set_irg_loopinfo_inconsistent(irg);
327 ir_graph_pass_t pass;
332 * Wrapper for running lower_switch() as a pass.
334 static int pass_wrapper(ir_graph *irg, void *context)
336 struct pass_t *pass = context;
338 lower_switch(irg, pass->spare_size);
342 /* creates a pass for lower_switch */
343 ir_graph_pass_t *lower_switch_pass(const char *name, unsigned spare_size)
345 struct pass_t *pass = XMALLOCZ(struct pass_t);
347 pass->spare_size = spare_size;
348 return def_graph_pass_constructor(
349 &pass->pass, name ? name : "lower_switch", pass_wrapper);