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 Construction of Confirm nodes
23 * @author Michael Beck
31 #include "irgraph_t.h"
35 #include "iropt_dbg.h"
36 #include "iredges_t.h"
46 typedef struct _env_t {
47 unsigned num_confirms; /**< number of inserted Confirm nodes */
48 unsigned num_consts; /**< number of constants placed */
49 unsigned num_eq; /**< number of equalities placed */
53 * Return the effective use block of a node and it's predecessor on
56 * @param node the node
57 * @param pos the position of the used input
59 * This handles correctly Phi nodes.
61 static ir_node *get_effective_use_block(ir_node *node, int pos) {
63 /* the effective use of a Phi argument is in its predecessor block */
64 node = get_nodes_block(node);
65 return get_Block_cfgpred_block(node, pos);
67 return get_nodes_block(node);
71 * Handle a CASE-branch.
73 * @param block the block which is entered by the branch
74 * @param irn the node expressing the switch value
75 * @param nr the branch label
76 * @param env statistical environment
78 * Branch labels are a simple case. We can replace the value
79 * by a Const with the branch label.
81 static void handle_case(ir_node *block, ir_node *irn, long nr, env_t *env) {
82 const ir_edge_t *edge, *next;
88 for (edge = get_irn_out_edge_first(irn); edge; edge = next) {
89 ir_node *succ = get_edge_src_irn(edge);
90 int pos = get_edge_src_pos(edge);
91 ir_node *blk = get_effective_use_block(succ, pos);
93 next = get_irn_out_edge_next(irn, edge);
95 if (block_dominates(block, blk)) {
97 * Ok, we found a user of irn that is placed
98 * in a block dominated by the branch block.
99 * We can replace the input with the Constant
104 ir_mode *mode = get_irn_mode(irn);
105 ir_type *tp = get_irn_type(irn);
106 tarval *tv = new_tarval_from_long(nr, mode);
107 c = new_r_Const_type(current_ir_graph, block, mode, tv, tp);
110 set_irn_n(succ, pos, c);
111 DBG_OPT_CONFIRM_C(irn, c);
112 // ir_printf("1 Replacing input %d of node %n with %n\n", pos, succ, c);
114 env->num_consts += 1;
120 * Handle a mode_b input of Cond nodes.
122 * @param block the block which is entered by the branch
123 * @param selector the mode_b node expressing the branch condition
124 * @param pnc the true/false condition branch
125 * @param env statistical environment
127 static void handle_modeb(ir_node *block, ir_node *selector, pn_Cond pnc, env_t *env) {
128 ir_node *cond, *old, *cond_block = NULL, *other_blk = NULL, *con = NULL;
129 ir_node *c_b = NULL, *c_o = NULL;
130 const ir_edge_t *edge, *next;
132 for (edge = get_irn_out_edge_first(selector); edge; edge = next) {
133 ir_node *user = get_edge_src_irn(edge);
134 int pos = get_edge_src_pos(edge);
135 ir_node *user_blk = get_effective_use_block(user, pos);
137 next = get_irn_out_edge_next(selector, edge);
138 if (block_dominates(block, user_blk)) {
140 * Ok, we found a usage of selector in a block
141 * dominated by the branch block.
142 * We can replace the input with true/false.
145 con = new_Const(mode_b, pnc == pn_Cond_true ? tarval_b_true : tarval_b_false);
147 old = get_irn_n(user, pos);
148 set_irn_n(user, pos, con);
149 DBG_OPT_CONFIRM_C(old, con);
151 // ir_printf("2 Replacing input %d of node %n with %n\n", pos, user, con);
153 env->num_consts += 1;
157 /* get the other block */
158 if (other_blk == NULL) {
159 /* we have already tested, that block has only ONE Cond predecessor */
160 cond = get_Proj_pred(get_Block_cfgpred(block, 0));
161 cond_block = get_nodes_block(cond);
162 foreach_out_edge(cond, edge) {
163 ir_node *proj = get_edge_src_irn(edge);
164 if (get_Proj_proj(proj) == (long)pnc)
166 edge = get_irn_out_edge_first(proj);
167 other_blk = get_edge_src_irn(edge);
173 * Note the special case here: if block is a then, there might be no else
174 * block. In that case the other_block is the user_blk itself and pred_block
175 * is the cond_block ...
177 * Best would be to introduce a block here, removing this critical edge.
178 * For some reasons I cannot repair dominance here, so I have to remove
179 * ALL critical edges...
180 * FIXME: This should not be needed if we could repair dominance ...
184 n = get_Block_n_cfgpreds(user_blk);
187 * We have found a user in a non-dominated block:
188 * check, if all its block predecessors are dominated.
189 * If yes, place a Phi.
191 for (i = n - 1; i >= 0; --i) {
192 ir_node *pred_blk = get_Block_cfgpred_block(user_blk, i);
194 if (!block_dominates(block, pred_blk) &&
195 !block_dominates(other_blk, pred_blk)) {
196 /* can't do anything */
203 NEW_ARR_A(ir_node *, in, n);
204 /* ok, ALL predecessors are either dominated by block OR other block */
206 ir_node *c_true = new_Const(mode_b, tarval_b_true);
207 ir_node *c_false = new_Const(mode_b, tarval_b_false);
208 c_b = new_r_Confirm(current_ir_graph, cond_block, selector,
209 pnc == pn_Cond_true ? c_true : c_false, pn_Cmp_Eq);
210 c_o = new_r_Confirm(current_ir_graph, cond_block, selector,
211 pnc == pn_Cond_false ? c_true : c_false, pn_Cmp_Eq);
213 for (i = n - 1; i >= 0; --i) {
214 ir_node *pred_blk = get_Block_cfgpred_block(user_blk, i);
216 if (block_dominates(block, pred_blk))
221 phi = new_r_Phi(current_ir_graph, user_blk, n, in, mode_b);
222 set_irn_n(user, pos, phi);
229 * Handle an IF-branch.
231 * @param block the block which is entered by the branch
232 * @param cmp the Cmp node expressing the branch condition
233 * @param pnc the Compare relation for taking this branch
234 * @param env statistical environment
236 static void handle_if(ir_node *block, ir_node *cmp, pn_Cmp pnc, env_t *env) {
237 ir_node *left = get_Cmp_left(cmp);
238 ir_node *right = get_Cmp_right(cmp);
241 const ir_edge_t *edge, *next;
244 if (is_Bad(left) || is_Bad(right))
247 op = get_irn_op(left);
249 /* Do not create Confirm nodes for Cmp(Const, Const) constructs.
250 These are removed anyway */
251 if (op == op_Const && is_Const(right))
254 /* try to place the constant on the right side for a Confirm */
255 if (op == op_Const || op == op_SymConst) {
261 pnc = get_inversed_pnc(pnc);
265 * First case: both values are identical.
266 * replace the left one by the right (potentially const) one.
268 if (pnc == pn_Cmp_Eq) {
269 cond_block = get_Block_cfgpred_block(block, 0);
270 for (edge = get_irn_out_edge_first(left); edge; edge = next) {
271 ir_node *user = get_edge_src_irn(edge);
272 int pos = get_edge_src_pos(edge);
273 ir_node *blk = get_effective_use_block(user, pos);
275 next = get_irn_out_edge_next(left, edge);
276 if (block_dominates(block, blk)) {
278 * Ok, we found a usage of left in a block
279 * dominated by the branch block.
280 * We can replace the input with right.
282 set_irn_n(user, pos, right);
283 DBG_OPT_CONFIRM(left, right);
285 // ir_printf("2 Replacing input %d of node %n with %n\n", pos, user, right);
288 } else if (block_dominates(blk, cond_block)) {
289 if (is_Const(right) && get_irn_pinned(user) == op_pin_state_floats) {
291 * left == Const and we found a movable user of left in a
292 * dominator of the Cond block
294 const ir_edge_t *edge, *next;
295 for (edge = get_irn_out_edge_first(user); edge; edge = next) {
296 ir_node *usr_of_usr = get_edge_src_irn(edge);
297 int npos = get_edge_src_pos(edge);
298 ir_node *blk = get_effective_use_block(usr_of_usr, npos);
300 next = get_irn_out_edge_next(user, edge);
301 if (block_dominates(block, blk)) {
303 * The user of the user is dominated by our true/false
304 * block. So, create a copy of user WITH the constant
305 * replacing it's pos'th input.
307 * This is always good for unop's and might be good
310 * If user has other user in the false/true block, code
311 * placement will move it down.
312 * If there are users in cond block or upper, we create
313 * "redundant ops", because one will have a const op,
314 * the other no const ...
316 ir_node *new_op = exact_copy(user);
317 set_nodes_block(new_op, block);
318 set_irn_n(new_op, pos, right);
319 set_irn_n(usr_of_usr, npos, new_op);
325 } else { /* not pn_Cmp_Eq cases */
328 for (edge = get_irn_out_edge_first(left); edge; edge = next) {
329 ir_node *succ = get_edge_src_irn(edge);
330 int pos = get_edge_src_pos(edge);
331 ir_node *blk = get_effective_use_block(succ, pos);
333 next = get_irn_out_edge_next(left, edge);
334 if (block_dominates(block, blk)) {
336 * Ok, we found a usage of left in a block
337 * dominated by the branch block.
338 * We can replace the input with a Confirm(left, pnc, right).
341 c = new_r_Confirm(current_ir_graph, block, left, right, pnc);
343 pos = get_edge_src_pos(edge);
344 set_irn_n(succ, pos, c);
345 // ir_printf("3 Replacing input %d of node %n with %n\n", pos, user, c);
347 env->num_confirms += 1;
354 * Pre-walker: Called for every block to insert Confirm nodes
356 static void insert_Confirm(ir_node *block, void *env) {
357 ir_node *cond, *proj, *selector;
361 * we can only handle blocks with only ONE control flow
364 if (get_Block_n_cfgpreds(block) != 1)
367 proj = get_Block_cfgpred(block, 0);
371 cond = get_Proj_pred(proj);
375 selector = get_Cond_selector(cond);
376 mode = get_irn_mode(selector);
378 if (mode == mode_b) {
382 handle_modeb(block, selector, get_Proj_proj(proj), env);
384 /* this should be an IF, check this */
385 if (! is_Proj(selector))
388 cmp = get_Proj_pred(selector);
392 pnc = get_Proj_proj(selector);
394 if (get_Proj_proj(proj) != pn_Cond_true) {
395 /* it's the false branch */
396 pnc = get_negated_pnc(pnc, mode);
398 // ir_printf("At %n using %n Confirm %=\n", block, cmp, pnc);
400 handle_if(block, cmp, pnc, env);
401 } else if (mode_is_int(mode)) {
402 long proj_nr = get_Proj_proj(proj);
404 /* this is a CASE, but we cannot handle the default case */
405 if (proj_nr == get_Cond_defaultProj(cond))
408 handle_case(block, get_Cond_selector(cond), proj_nr, env);
410 } /* insert_Confirm */
413 * Construct Confirm nodes
415 void construct_confirms(ir_graph *irg) {
417 int edges_active = edges_activated(irg);
419 remove_critical_cf_edges(irg);
421 /* we need dominance info */
424 assert(get_irg_pinned(irg) == op_pin_state_pinned &&
425 "Nodes must be placed to insert Confirms");
427 if (! edges_active) {
432 env.num_confirms = 0;
436 /* now, visit all blocks and add Confirms where possible */
437 irg_block_walk_graph(irg, insert_Confirm, NULL, &env);
439 if (env.num_confirms | env.num_consts | env.num_eq) {
440 /* we have add nodes or changed DF edges */
441 set_irg_outs_inconsistent(irg);
443 /* the new nodes are not in the loop info */
444 set_irg_loopinfo_inconsistent(irg);
448 printf("# Confirms inserted : %u\n", env.num_confirms);
449 printf("# Const replacements: %u\n", env.num_consts);
450 printf("# node equalities : %u\n", env.num_eq);
453 /* deactivate edges if they where off */
455 edges_deactivate(irg);
456 } /* construct_confirms */
460 * Post-walker: Remove Confirm nodes
462 static void rem_Confirm(ir_node *n, void *env) {
465 ir_node *value = get_Confirm_value(n);
470 * Strange: a Confirm is it's own bound. This can happen
471 * in dead blocks when Phi nodes are already removed.
473 exchange(n, new_Bad());
480 * Remove all Confirm nodes from a graph.
482 void remove_confirms(ir_graph *irg) {
483 set_opt_remove_confirm(1);
484 optimize_graph_df(irg);
485 } /* remove_confirms */