3 * File name: ir/opt/cfopt.c
4 * Purpose: Partial condition evaluation
5 * Author: Christoph Mallon, Matthias Braun
6 * Created: 10. Sep. 2006
8 * Copyright: (c) 1998-2006 Universität Karlsruhe
9 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
26 #include "iredges_t.h"
30 DEBUG_ONLY(static firm_dbg_module_t *dbg);
34 * Add the new predecessor x to node node, which is either a Block or a Phi
36 static void add_pred(ir_node* node, ir_node* x)
42 assert(is_Block(node) || is_Phi(node));
44 n = get_irn_arity(node);
45 NEW_ARR_A(ir_node*, ins, n + 1);
46 for (i = 0; i < n; i++) ins[i] = get_irn_n(node, i);
48 set_irn_in(node, n + 1, ins);
52 * Remove predecessor j from node, which is either a Block or a Phi
53 * returns true if only one predecessor is left
55 static int remove_pred(ir_node* node, int j)
59 assert(is_Block(node) || is_Phi(node));
61 n = get_irn_arity(node);
63 ir_node* pred = get_irn_n(node, 1 - j);
66 pred = get_nodes_block(pred);
67 ir_fprintf(stderr, "Exchaning %+F with %+F\n", node, pred);
68 //set_irn_in(node, get_irn_arity(pred), get_irn_in(pred) + 1);
69 //exchange(node, pred);
70 edges_reroute(node, pred, current_ir_graph);
79 NEW_ARR_A(ir_node*, ins, n - 1);
80 for (i = 0; i < j; i++) ins[i] = get_irn_n(node, i);
81 for (i++; i < n; i++) ins[i - 1] = get_irn_n(node, i);
82 set_irn_in(node, n - 1, ins);
87 static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode)
95 assert(!is_Bad(block));
97 // already processed this block?
98 if(irn_visited(block)) {
99 ir_node *value = (ir_node*) get_irn_link(block);
103 // blocks with only 1 pred need no phi
104 n_cfgpreds = get_Block_n_cfgpreds(block);
105 if(n_cfgpreds == 1) {
106 ir_node *pred_block = get_Block_cfgpred_block(block, 0);
107 ir_node *value = search_def_and_create_phis(pred_block, mode);
109 set_irn_link(block, value);
110 mark_irn_visited(block);
115 in = alloca(sizeof(in[0]) * n_cfgpreds);
116 for(i = 0; i < n_cfgpreds; ++i)
117 in[i] = new_Unknown(mode);
119 irg = get_irn_irg(block);
120 phi = new_r_Phi(irg, block, n_cfgpreds, in, mode);
121 set_irn_link(block, phi);
122 mark_irn_visited(block);
125 for(i = 0; i < n_cfgpreds; ++i) {
126 ir_node *pred_block = get_Block_cfgpred_block(block, i);
129 pred_val = search_def_and_create_phis(pred_block, mode);
130 set_irn_n(phi, i, pred_val);
137 * Given a set of values this function constructs SSA-form for all users of the
138 * values (the user are determined through the out-edges of the values).
140 static void construct_ssa(ir_node * const *blocks, ir_node * const *vals, int n_vals)
148 irg = get_irn_irg(vals[0]);
149 inc_irg_visited(irg);
151 mode = get_irn_mode(vals[0]);
152 for(i = 0; i < n_vals; ++i) {
153 ir_node *value = vals[i];
154 ir_node *value_block = blocks[i];
156 assert(get_irn_mode(value) == mode);
158 set_irn_link(value_block, value);
159 mark_irn_visited(value_block);
162 for(i = 0; i < n_vals; ++i) {
163 const ir_edge_t *edge, *next;
164 ir_node *value = vals[i];
166 // this can happen when fixing phi preds, we mustn't fix the users
167 if(get_nodes_block(value) != blocks[i]) {
171 foreach_out_edge_safe(value, edge, next) {
172 ir_node *user = get_edge_src_irn(edge);
173 int j = get_edge_src_pos(edge);
174 ir_node *user_block = get_nodes_block(user);
178 if(get_irn_op(user) == op_End)
182 ir_node *pred_block = get_Block_cfgpred_block(user_block, j);
183 newval = search_def_and_create_phis(pred_block, mode);
185 newval = search_def_and_create_phis(user_block, mode);
188 // don't fix newly created phis from the SSA construction
190 set_irn_n(user, j, newval);
198 * Compare node compares two Const nodes
199 * Returns true if this direction is taken
201 static int handle_const_const(ir_node* cnst_left, cnst_right, pn_Cmp pnc)
211 static int handle_phi_const(ir_node* block, ir_node* cond_block, ir_node* phi, ir_node* cnst, pn_Cmp pnc)
219 tv_cnst = get_Const_tarval(cnst);
220 n_phi = get_Phi_n_preds(phi);
221 for (j = 0; j < n_phi; j++) {
222 const ir_edge_t *edge, *next;
228 pred = get_Phi_pred(phi, j);
229 // TODO handle Phi cascades
233 tv_phi = get_Const_tarval(pred);
235 cmp_val = tarval_cmp(tv_phi, tv_cnst);
236 if (cmp_val == pn_Cmp_False) continue;
237 if ((cmp_val & pnc) != cmp_val) continue;
241 "> Found condition evaluation candidate %+F->%+F predecessor %d\n",
245 add_pred(block, get_Block_cfgpred(cond_block, j));
246 // split critical edges
247 /*if(get_irn_arity(block) == 2)*/ {
252 in[0] = get_Block_cfgpred(block, 0);
253 new_block = new_r_Block(current_ir_graph, 1, in);
254 new_jmp = new_r_Jmp(current_ir_graph, new_block);
255 set_Block_cfgpred(block, 0, new_jmp);
258 pred_block = get_Block_cfgpred_block(cond_block, j);
260 /* Look at all nodes in the cond_block and copy them into pred */
261 foreach_out_edge(cond_block, edge) {
262 ir_node *node = get_edge_src_irn(edge);
265 // ignore these as SSA construction would fail on ProjX
266 if (is_Proj(node) && get_irn_mode(node) == mode_X)
269 // we can evaluate Phis right now, all other nodes get copied
271 copy = get_Phi_pred(node, j);
273 copy = exact_copy(node);
274 set_nodes_block(copy, pred_block);
277 set_irn_link(node, copy);
280 /* fix data-flow (and reconstruct SSA if needed) */
281 foreach_out_edge(cond_block, edge) {
285 ir_node *node = get_edge_src_irn(edge);
286 assert(get_nodes_block(node) == cond_block);
287 if (is_Proj(node) && get_irn_mode(node) == mode_X)
290 blocks[0] = cond_block;
292 blocks[1] = pred_block;
293 vals[1] = get_irn_link(node);
294 construct_ssa(blocks, vals, 2);
298 foreach_out_edge_safe(cond_block, edge, next) {
299 ir_node *node = get_edge_src_irn(edge);
302 remove_pred(node, j);
306 remove_pred(cond_block, j);
308 if (remove_pred(cond_block, j))
310 // the phi got shortened
318 irg = get_irn_irg(block);
319 set_irg_doms_inconsistent(irg);
320 set_irg_extblk_inconsistent(irg);
321 set_irg_loopinfo_inconsistent(irg);
330 static void cond_eval(ir_node* block, void* env)
335 n_block = get_Block_n_cfgpreds(block);
336 for (i = 0; i < n_block; i++) {
346 pred = get_Block_cfgpred(block, i);
347 if (!is_Proj(pred)) continue;
350 pred = get_Proj_pred(projx);
351 if (!is_Cond(pred)) continue;
354 pred = get_Cond_selector(cond);
355 assert(is_Proj(pred));
356 // TODO handle switches
357 if (get_irn_mode(pred) != mode_b) continue;
358 pnc = get_Proj_proj(pred);
360 cmp = get_Proj_pred(pred);
363 left = get_Cmp_left(cmp);
364 right = get_Cmp_right(cmp);
365 assert(get_irn_mode(left) == get_irn_mode(right));
367 if (get_Proj_proj(projx) == 0) {
368 pnc = get_negated_pnc(pnc, get_irn_mode(left));
371 #if 0 // TODO implement
372 if (is_Const(left) && is_Const(right)) {
373 if (!handle_const_const()) {
380 cond_block = get_nodes_block(cond);
381 if (is_Phi(left) && is_Const(right)) {
382 if (get_nodes_block(left) != cond_block) continue;
383 handle_phi_const(block, cond_block, left, right, pnc);
386 if (is_Const(left) && is_Phi(right)) {
387 if (get_nodes_block(right) != cond_block) continue;
388 handle_phi_const(block, cond_block, right, left, get_inversed_pnc(pnc));
392 if (is_Phi(left) && is_Phi(right)) {
400 void opt_cond_eval(ir_graph* irg)
402 FIRM_DBG_REGISTER(dbg, "firm.opt.condeval");
403 firm_dbg_set_mask(dbg, SET_LEVEL_5);
405 DB((dbg, LEVEL_1, "===> Performing condition evaluation on %+F\n", irg));
407 if(edges_activated(irg))
408 edges_deactivate(irg);
410 remove_critical_cf_edges(irg);
412 normalize_proj_nodes(irg);
414 irg_block_walk_graph(irg, cond_eval, NULL, NULL);
416 irg_block_walk_graph(irg, NULL, cond_eval, NULL);
417 irg_block_walk_graph(irg, NULL, cond_eval, NULL);
418 irg_block_walk_graph(irg, NULL, cond_eval, NULL);