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
21 * @file ir/opt/ifconv.c
22 * @brief If conversion
23 * @author Christoph Mallon
30 #include "iroptimize.h"
46 DEBUG_ONLY(static firm_dbg_module_t *dbg);
48 /** allow every Mux to be created. */
49 static int default_allow_ifconv(ir_node *sel, ir_node* phi_list, int i, int j)
61 static const ir_settings_if_conv_t default_info = {
62 0, /* doesn't matter for Mux */
67 * Returns non-zero if a Block can be emptied.
69 static int can_empty_block(ir_node *block) {
70 return get_Block_mark(block) == 0;
74 static ir_node* walk_to_projx(ir_node* start, const ir_node* dependency)
79 /* No need to find the conditional block if this block cannot be emptied and
80 * therefore not moved */
81 if (!can_empty_block(start)) return NULL;
83 arity = get_irn_arity(start);
84 for (i = 0; i < arity; ++i) {
85 ir_node* pred = get_irn_n(start, i);
86 ir_node* pred_block = get_nodes_block(pred);
88 if (pred_block == dependency) {
90 assert(get_irn_mode(pred) == mode_X);
97 assert(get_irn_mode(pred) == mode_X);
101 if (is_cdep_on(pred_block, dependency)) {
102 return walk_to_projx(pred_block, dependency);
110 * Copies the DAG starting at node to the ith predecessor block of src_block
111 * -if the node isn't in the src_block, this is a nop and the node is returned
112 * -if the node is a phi in the src_block, the ith predecessor of the phi is
114 * otherwise returns the copy of the passed node
116 static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
123 if (get_nodes_block(node) != src_block) return node;
124 if (get_irn_op(node) == op_Phi) return get_irn_n(node, i);
126 copy = exact_copy(node);
127 dst_block = get_nodes_block(get_irn_n(src_block, i));
128 set_nodes_block(copy, dst_block);
130 DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
131 node, dst_block, copy));
133 arity = get_irn_arity(node);
134 for (j = 0; j < arity; ++j) {
135 set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
136 DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, get_irn_n(copy, j)));
143 * Remove predecessors i and j from node and add predecessor new_pred
145 static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
147 int arity = get_irn_arity(node);
152 NEW_ARR_A(ir_node *, ins, arity - 1);
155 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(node, k);
156 for (++k; k < j; ++k) ins[l++] = get_irn_n(node, k);
157 for (++k; k < arity; ++k) ins[l++] = get_irn_n(node, k);
159 assert(l == arity - 1);
160 set_irn_in(node, l, ins);
165 * Remove the jth predecessors from the ith predecessor of block and add it to block
167 static void split_block(ir_node* block, int i, int j)
169 ir_node* pred_block = get_nodes_block(get_irn_n(block, i));
170 int arity = get_irn_arity(block);
177 DB((dbg, LEVEL_1, "Splitting predecessor %d of predecessor %d of %+F\n", j, i, block));
179 NEW_ARR_A(ir_node*, ins, arity + 1);
181 for (phi = get_Block_phis(block); phi != NULL; phi = get_Phi_next(phi)) {
182 ir_node* copy = copy_to(get_irn_n(phi, i), pred_block, j);
184 for (k = 0; k < i; ++k) ins[k] = get_irn_n(phi, k);
186 for (; k < arity; ++k) ins[k] = get_irn_n(phi, k);
187 ins[k] = get_irn_n(phi, i);
189 set_irn_in(phi, arity + 1, ins);
192 for (k = 0; k < i; ++k) ins[k] = get_irn_n(block, k);
193 ins[k++] = get_irn_n(pred_block, j);
194 for (; k < arity; ++k) ins[k] = get_irn_n(block, k);
195 ins[k] = get_irn_n(block, i);
197 set_irn_in(block, arity + 1, ins);
199 new_pred_arity = get_irn_arity(pred_block) - 1;
200 NEW_ARR_A(ir_node*, pred_ins, new_pred_arity);
202 for (phi = get_Block_phis(pred_block); phi != NULL; phi = next) {
203 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(phi, k);
204 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(phi, k + 1);
205 assert(k == new_pred_arity);
206 next = get_Phi_next(phi);
207 if (new_pred_arity > 1) {
208 set_irn_in(phi, new_pred_arity, pred_ins);
210 exchange(phi, pred_ins[0]);
214 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(pred_block, k);
215 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(pred_block, k + 1);
216 assert(k == new_pred_arity);
217 if (new_pred_arity > 1) {
218 set_irn_in(pred_block, new_pred_arity, pred_ins);
220 exchange(pred_block, get_nodes_block(pred_ins[0]));
225 static void prepare_path(ir_node* block, int i, const ir_node* dependency)
227 ir_node* pred = get_nodes_block(get_irn_n(block, i));
231 DB((dbg, LEVEL_1, "Preparing predecessor %d of %+F\n", i, block));
233 pred_arity = get_irn_arity(pred);
234 for (j = 0; j < pred_arity; ++j) {
235 ir_node* pred_pred = get_nodes_block(get_irn_n(pred, j));
237 if (is_cdep_on(pred_pred, dependency)) {
238 prepare_path(pred, j, dependency);
239 split_block(block, i, j);
246 static void if_conv_walker(ir_node* block, void* env)
248 ir_settings_if_conv_t* opt_info = env;
252 /* Bail out, if there are no Phis at all */
253 if (get_Block_phis(block) == NULL) return;
256 arity = get_irn_arity(block);
257 for (i = 0; i < arity; ++i) {
261 pred0 = get_Block_cfgpred_block(block, i);
262 for (cdep = find_cdep(pred0); cdep != NULL; cdep = cdep->next) {
263 const ir_node* dependency = cdep->node;
264 ir_node* projx0 = walk_to_projx(pred0, dependency);
268 if (projx0 == NULL) continue;
270 cond = get_Proj_pred(projx0);
274 /* We only handle boolean decisions, no switches */
275 if (get_irn_mode(get_Cond_selector(cond)) != mode_b) continue;
277 for (j = i + 1; j < arity; ++j) {
285 pred1 = get_Block_cfgpred_block(block, j);
287 if (!is_cdep_on(pred1, dependency)) continue;
289 projx1 = walk_to_projx(pred1, dependency);
291 if (projx1 == NULL) continue;
293 phi = get_Block_phis(block);
294 if (!opt_info->allow_ifconv(get_Cond_selector(cond), phi, i, j)) continue;
296 DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n",
300 prepare_path(block, i, dependency);
301 prepare_path(block, j, dependency);
302 arity = get_irn_arity(block);
304 sel = get_Cond_selector(cond);
306 mux_block = get_nodes_block(cond);
307 cond_dbg = get_irn_dbg_info(cond);
309 ir_node* val_i = get_irn_n(phi, i);
310 ir_node* val_j = get_irn_n(phi, j);
314 if (val_i == val_j) {
316 DB((dbg, LEVEL_2, "Generating no Mux, because both values are equal\n"));
320 /* Something is very fishy if two predecessors of a PhiM point into
321 * one block, but not at the same memory node
323 assert(get_irn_mode(phi) != mode_M);
324 if (get_Proj_proj(projx0) == pn_Cond_true) {
332 mux = new_rd_Mux(cond_dbg, current_ir_graph, mux_block, sel, f, t, get_irn_mode(phi));
333 DB((dbg, LEVEL_2, "Generating %+F for %+F\n", mux, phi));
336 next_phi = get_Phi_next(phi);
341 rewire(phi, i, j, mux);
345 } while (phi != NULL);
347 exchange(get_nodes_block(get_irn_n(block, i)), mux_block);
348 exchange(get_nodes_block(get_irn_n(block, j)), mux_block);
353 DB((dbg, LEVEL_1, "Welding block %+F and %+F\n", block, mux_block));
354 /* copy the block-info from the Mux-block to the block before merging */
356 mark = get_Block_mark(mux_block) | get_Block_mark(block);
357 set_Block_mark(block, mark);
358 set_Block_phis(block, get_Block_phis(mux_block));
360 set_irn_in(block, get_irn_arity(mux_block), get_irn_in(mux_block) + 1);
361 exchange_cdep(mux_block, block);
362 exchange(mux_block, block);
364 DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, mux_block));
365 mark = get_Block_mark(mux_block) | get_Block_mark(block);
366 /* mark both block just to be sure, should be enough to mark mux_block */
367 set_Block_mark(mux_block, mark);
368 exchange(block, mux_block);
372 rewire(block, i, j, new_r_Jmp(current_ir_graph, mux_block));
381 * Block walker: clear block mark and Phi list
383 static void init_block_link(ir_node *block, void *env)
386 set_Block_mark(block, 0);
387 set_Block_phis(block, NULL);
392 * Daisy-chain all phis in a block
393 * If a non-movable node is encountered set the has_pinned flag in its block.
395 static void collect_phis(ir_node *node, void *env) {
399 ir_node *block = get_nodes_block(node);
401 add_Block_phi(block, node);
403 if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
405 * Ignore control flow nodes, these will be removed.
406 * This ignores Raise. That is surely bad. FIXME.
408 if (!is_cfop(node)) {
409 ir_node *block = get_nodes_block(node);
411 DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
412 set_Block_mark(block, 1);
418 static void optimise_muxs_0(ir_node* mux, void* env)
425 if (!is_Mux(mux)) return;
427 t = get_Mux_true(mux);
428 f = get_Mux_false(mux);
430 DB((dbg, LEVEL_3, "Simplify %+F T=%+F F=%+F\n", mux, t, f));
433 DB((dbg, LEVEL_3, "Replace Mux with unknown operand by %+F\n", f));
438 DB((dbg, LEVEL_3, "Replace Mux with unknown operand by %+F\n", t));
444 ir_graph* irg = current_ir_graph;
445 ir_node* block = get_nodes_block(mux);
446 ir_mode* mode = get_irn_mode(mux);
447 ir_node* c0 = get_Mux_sel(mux);
448 ir_node* c1 = get_Mux_sel(t);
449 ir_node* t1 = get_Mux_true(t);
450 ir_node* f1 = get_Mux_false(t);
452 /* Mux(c0, Mux(c1, x, y), y) -> typical if (c0 && c1) x else y */
453 ir_node* and_ = new_r_And(irg, block, c0, c1, mode_b);
454 ir_node* new_mux = new_r_Mux(irg, block, and_, f1, t1, mode);
455 exchange(mux, new_mux);
456 } else if (f == t1) {
457 /* Mux(c0, Mux(c1, x, y), x) */
458 ir_node* not_c1 = new_r_Not(irg, block, c1, mode_b);
459 ir_node* and_ = new_r_And(irg, block, c0, not_c1, mode_b);
460 ir_node* new_mux = new_r_Mux(irg, block, and_, t1, f1, mode);
461 exchange(mux, new_mux);
463 } else if (is_Mux(f)) {
464 ir_graph* irg = current_ir_graph;
465 ir_node* block = get_nodes_block(mux);
466 ir_mode* mode = get_irn_mode(mux);
467 ir_node* c0 = get_Mux_sel(mux);
468 ir_node* c1 = get_Mux_sel(f);
469 ir_node* t1 = get_Mux_true(f);
470 ir_node* f1 = get_Mux_false(f);
472 /* Mux(c0, x, Mux(c1, x, y)) -> typical if (c0 || c1) x else y */
473 ir_node* or_ = new_r_Or(irg, block, c0, c1, mode_b);
474 ir_node* new_mux = new_r_Mux(irg, block, or_, f1, t1, mode);
475 exchange(mux, new_mux);
476 } else if (t == f1) {
477 /* Mux(c0, x, Mux(c1, y, x)) */
478 ir_node* not_c1 = new_r_Not(irg, block, c1, mode_b);
479 ir_node* or_ = new_r_Or(irg, block, c0, not_c1, mode_b);
480 ir_node* new_mux = new_r_Mux(irg, block, or_, t1, f1, mode);
481 exchange(mux, new_mux);
487 static void optimise_muxs_1(ir_node* mux, void* env)
495 if (!is_Mux(mux)) return;
497 t = get_Mux_true(mux);
498 f = get_Mux_false(mux);
500 DB((dbg, LEVEL_3, "Simplify %+F T=%+F F=%+F\n", mux, t, f));
502 mode = get_irn_mode(mux);
504 if (is_Const(t) && is_Const(f) && (mode_is_int(mode))) {
505 ir_node* block = get_nodes_block(mux);
506 ir_node* c = get_Mux_sel(mux);
507 tarval* tv_t = get_Const_tarval(t);
508 tarval* tv_f = get_Const_tarval(f);
509 if (tarval_is_one(tv_t) && tarval_is_null(tv_f)) {
510 ir_node* conv = new_r_Conv(current_ir_graph, block, c, mode, 0);
512 } else if (tarval_is_null(tv_t) && tarval_is_one(tv_f)) {
513 ir_node* not_ = new_r_Not(current_ir_graph, block, c, mode_b);
514 ir_node* conv = new_r_Conv(current_ir_graph, block, not_, mode, 0);
521 void opt_if_conv(ir_graph *irg, const ir_settings_if_conv_t *params)
523 ir_settings_if_conv_t p;
525 /* get the parameters */
526 p = (params != NULL ? *params : default_info);
528 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
530 DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
532 normalize_one_return(irg);
533 remove_critical_cf_edges(irg);
538 ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_PHI_LIST);
540 irg_block_walk_graph(irg, init_block_link, NULL, NULL);
541 irg_walk_graph(irg, collect_phis, NULL, NULL);
542 irg_block_walk_graph(irg, NULL, if_conv_walker, &p);
544 ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_PHI_LIST);
546 local_optimize_graph(irg);
548 irg_walk_graph(irg, NULL, optimise_muxs_0, NULL);
550 irg_walk_graph(irg, NULL, optimise_muxs_1, NULL);
553 /* TODO: graph might be changed, handle more graceful */
554 set_irg_outs_inconsistent(irg);
555 set_irg_extblk_inconsistent(irg);
556 set_irg_loopinfo_inconsistent(irg);