1 /* Optimization of PHI nodes by converting them into straightline code.
2 Copyright (C) 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
31 #include "basic-block.h"
33 #include "diagnostic.h"
34 #include "tree-flow.h"
35 #include "tree-pass.h"
36 #include "tree-dump.h"
37 #include "langhooks.h"
39 static void tree_ssa_phiopt (void);
40 static bool conditional_replacement (basic_block, basic_block, basic_block,
41 edge, edge, tree, tree, tree);
42 static bool value_replacement (basic_block, basic_block, basic_block,
43 edge, edge, tree, tree, tree);
44 static bool abs_replacement (basic_block, basic_block, basic_block,
45 edge, edge, tree, tree, tree);
46 static void replace_phi_edge_with_variable (basic_block, basic_block, edge,
49 /* This pass eliminates PHI nodes which can be trivially implemented as
50 an assignment from a conditional expression. i.e. if we have something
54 if (cond) goto bb2; else goto bb1;
57 x = PHI (0 (bb1), 1 (bb0)
59 We can rewrite that as:
66 bb1 will become unreachable and bb0 and bb2 will almost always
67 be merged into a single block. This occurs often due to gimplification
70 Also done is the following optimization:
73 if (a != b) goto bb2; else goto bb1;
76 x = PHI (a (bb1), b (bb0))
78 We can rewrite that as:
85 This can sometimes occur as a result of other optimizations. A
86 similar transformation is done by the ifcvt RTL optimizer.
88 This pass also eliminates PHI nodes which are really absolute
89 values. i.e. if we have something like:
92 if (a >= 0) goto bb2; else goto bb1;
96 x = PHI (x (bb1), a (bb0));
98 We can rewrite that as:
105 bb1 will become unreachable and bb0 and bb2 will almost always be merged
106 into a single block. Similar transformations are done by the ifcvt
110 tree_ssa_phiopt (void)
113 bool removed_phis = false;
115 /* Search every basic block for COND_EXPR we may be able to optimize
116 in reverse order so we can find more. */
117 FOR_EACH_BB_REVERSE (bb)
121 basic_block bb1, bb2;
124 cond_expr = last_stmt (bb);
125 /* Check to see if the last statement is a COND_EXPR. */
127 || TREE_CODE (cond_expr) != COND_EXPR)
130 e1 = EDGE_SUCC (bb, 0);
132 e2 = EDGE_SUCC (bb, 1);
135 /* We cannot do the optimization on abnormal edges. */
136 if ((e1->flags & EDGE_ABNORMAL) != 0
137 || (e2->flags & EDGE_ABNORMAL) != 0)
140 /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
141 if (EDGE_COUNT (bb1->succs) < 1
143 || EDGE_COUNT (bb2->succs) < 1)
146 /* Find the bb which is the fall through to the other. */
147 if (EDGE_SUCC (bb1, 0)->dest == bb2)
149 else if (EDGE_SUCC (bb2, 0)->dest == bb1)
151 basic_block bb_tmp = bb1;
161 e1 = EDGE_SUCC (bb1, 0);
163 /* Make sure that bb1 is just a fall through. */
164 if (EDGE_COUNT (bb1->succs) > 1
165 || (e1->flags & EDGE_FALLTHRU) == 0)
168 /* Also make that bb1 only have one pred and it is bb. */
169 if (EDGE_COUNT (bb1->preds) > 1
170 || EDGE_PRED (bb1, 0)->src != bb)
173 phi = phi_nodes (bb2);
175 /* Check to make sure that there is only one PHI node.
176 TODO: we could do it with more than one iff the other PHI nodes
177 have the same elements for these two edges. */
178 if (phi && PHI_CHAIN (phi) == NULL)
180 tree arg0 = NULL, arg1 = NULL;
182 arg0 = PHI_ARG_DEF_TREE (phi, e1->dest_idx);
183 arg1 = PHI_ARG_DEF_TREE (phi, e2->dest_idx);
185 /* We know something is wrong if we cannot find the edges in the PHI
187 gcc_assert (arg0 != NULL && arg1 != NULL);
189 /* Do the replacement of conditional if it can be done. */
190 if (conditional_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1)
191 || value_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1)
192 || abs_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1))
194 /* We have done the replacement so we need to rebuild the
195 cfg when this pass is complete. */
202 /* Return TRUE if block BB has no executable statements, otherwise return
205 empty_block_p (basic_block bb)
207 block_stmt_iterator bsi;
209 /* BB must have no executable statements. */
210 bsi = bsi_start (bb);
211 while (!bsi_end_p (bsi)
212 && (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR
213 || IS_EMPTY_STMT (bsi_stmt (bsi))))
216 if (!bsi_end_p (bsi))
222 /* Replace PHI node element whoes edge is E in block BB with variable NEW.
223 Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
224 is known to have two edges, one of which must reach BB). */
227 replace_phi_edge_with_variable (basic_block cond_block, basic_block bb,
228 edge e, tree phi, tree new)
230 basic_block block_to_remove;
231 block_stmt_iterator bsi;
233 /* Change the PHI argument to new. */
234 PHI_ARG_DEF_TREE (phi, e->dest_idx) = new;
236 /* Remove the empty basic block. */
237 if (EDGE_SUCC (cond_block, 0)->dest == bb)
239 EDGE_SUCC (cond_block, 0)->flags |= EDGE_FALLTHRU;
240 EDGE_SUCC (cond_block, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
242 block_to_remove = EDGE_SUCC (cond_block, 1)->dest;
246 EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU;
247 EDGE_SUCC (cond_block, 1)->flags
248 &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
250 block_to_remove = EDGE_SUCC (cond_block, 0)->dest;
252 delete_basic_block (block_to_remove);
254 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
255 bsi = bsi_last (cond_block);
258 if (dump_file && (dump_flags & TDF_DETAILS))
260 "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
265 /* The function conditional_replacement does the main work of doing the
266 conditional replacement. Return true if the replacement is done.
267 Otherwise return false.
268 BB is the basic block where the replacement is going to be done on. ARG0
269 is argument 0 from PHI. Likewise for ARG1. */
272 conditional_replacement (basic_block cond_bb, basic_block middle_bb,
273 basic_block phi_bb, edge e0, edge e1, tree phi,
274 tree arg0, tree arg1)
277 tree old_result = NULL;
279 block_stmt_iterator bsi;
280 edge true_edge, false_edge;
284 /* The PHI arguments have the constants 0 and 1, then convert
285 it to the conditional. */
286 if ((integer_zerop (arg0) && integer_onep (arg1))
287 || (integer_zerop (arg1) && integer_onep (arg0)))
292 if (!empty_block_p (middle_bb))
295 /* If the condition is not a naked SSA_NAME and its type does not
296 match the type of the result, then we have to create a new
297 variable to optimize this case as it would likely create
298 non-gimple code when the condition was converted to the
300 cond = COND_EXPR_COND (last_stmt (cond_bb));
301 result = PHI_RESULT (phi);
302 if (TREE_CODE (cond) != SSA_NAME
303 && !lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
305 new_var = make_rename_temp (TREE_TYPE (cond), NULL);
310 /* If the condition was a naked SSA_NAME and the type is not the
311 same as the type of the result, then convert the type of the
313 if (!lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
314 cond = fold_convert (TREE_TYPE (result), cond);
316 /* We need to know which is the true edge and which is the false
317 edge so that we know when to invert the condition below. */
318 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
320 /* Insert our new statement at the end of conditional block before the
322 bsi = bsi_last (cond_bb);
323 bsi_insert_before (&bsi, build_empty_stmt (), BSI_NEW_STMT);
328 if (!COMPARISON_CLASS_P (old_result))
331 new1 = build (TREE_CODE (old_result), TREE_TYPE (old_result),
332 TREE_OPERAND (old_result, 0),
333 TREE_OPERAND (old_result, 1));
335 new1 = build (MODIFY_EXPR, TREE_TYPE (old_result), new_var, new1);
336 bsi_insert_after (&bsi, new1, BSI_NEW_STMT);
339 new_var1 = duplicate_ssa_name (PHI_RESULT (phi), NULL);
342 /* At this point we know we have a COND_EXPR with two successors.
343 One successor is BB, the other successor is an empty block which
344 falls through into BB.
346 There is a single PHI node at the join point (BB) and its arguments
347 are constants (0, 1).
349 So, given the condition COND, and the two PHI arguments, we can
350 rewrite this PHI into non-branching code:
352 dest = (COND) or dest = COND'
354 We use the condition as-is if the argument associated with the
355 true edge has the value one or the argument associated with the
356 false edge as the value zero. Note that those conditions are not
357 the same since only one of the outgoing edges from the COND_EXPR
358 will directly reach BB and thus be associated with an argument. */
359 if ((e0 == true_edge && integer_onep (arg0))
360 || (e0 == false_edge && integer_zerop (arg0))
361 || (e1 == true_edge && integer_onep (arg1))
362 || (e1 == false_edge && integer_zerop (arg1)))
364 new = build (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
368 tree cond1 = invert_truthvalue (cond);
371 /* If what we get back is a conditional expression, there is no
372 way that it can be gimple. */
373 if (TREE_CODE (cond) == COND_EXPR)
375 release_ssa_name (new_var1);
379 /* If what we get back is not gimple try to create it as gimple by
380 using a temporary variable. */
381 if (is_gimple_cast (cond)
382 && !is_gimple_val (TREE_OPERAND (cond, 0)))
384 tree temp = TREE_OPERAND (cond, 0);
385 tree new_var_1 = make_rename_temp (TREE_TYPE (temp), NULL);
386 new = build (MODIFY_EXPR, TREE_TYPE (new_var_1), new_var_1, temp);
387 bsi_insert_after (&bsi, new, BSI_NEW_STMT);
388 cond = fold_convert (TREE_TYPE (result), new_var_1);
391 if (TREE_CODE (cond) == TRUTH_NOT_EXPR
392 && !is_gimple_val (TREE_OPERAND (cond, 0)))
394 release_ssa_name (new_var1);
398 new = build (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
401 bsi_insert_after (&bsi, new, BSI_NEW_STMT);
403 SSA_NAME_DEF_STMT (new_var1) = new;
405 replace_phi_edge_with_variable (cond_bb, phi_bb, e1, phi, new_var1);
407 /* Note that we optimized this PHI. */
411 /* The function value_replacement does the main work of doing the value
412 replacement. Return true if the replacement is done. Otherwise return
414 BB is the basic block where the replacement is going to be done on. ARG0
415 is argument 0 from the PHI. Likewise for ARG1. */
418 value_replacement (basic_block cond_bb, basic_block middle_bb,
419 basic_block phi_bb, edge e0, edge e1, tree phi,
420 tree arg0, tree arg1)
424 edge true_edge, false_edge;
426 /* If the type says honor signed zeros we cannot do this
428 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
431 if (!empty_block_p (middle_bb))
434 cond = COND_EXPR_COND (last_stmt (cond_bb));
435 result = PHI_RESULT (phi);
437 /* This transformation is only valid for equality comparisons. */
438 if (TREE_CODE (cond) != NE_EXPR && TREE_CODE (cond) != EQ_EXPR)
441 /* We need to know which is the true edge and which is the false
442 edge so that we know if have abs or negative abs. */
443 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
445 /* At this point we know we have a COND_EXPR with two successors.
446 One successor is BB, the other successor is an empty block which
447 falls through into BB.
449 The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
451 There is a single PHI node at the join point (BB) with two arguments.
453 We now need to verify that the two arguments in the PHI node match
454 the two arguments to the equality comparison. */
456 if ((operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 0))
457 && operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 1)))
458 || (operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 0))
459 && operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 1))))
464 /* For NE_EXPR, we want to build an assignment result = arg where
465 arg is the PHI argument associated with the true edge. For
466 EQ_EXPR we want the PHI argument associated with the false edge. */
467 e = (TREE_CODE (cond) == NE_EXPR ? true_edge : false_edge);
469 /* Unfortunately, E may not reach BB (it may instead have gone to
470 OTHER_BLOCK). If that is the case, then we want the single outgoing
471 edge from OTHER_BLOCK which reaches BB and represents the desired
472 path from COND_BLOCK. */
473 if (e->dest == middle_bb)
474 e = EDGE_SUCC (e->dest, 0);
476 /* Now we know the incoming edge to BB that has the argument for the
477 RHS of our new assignment statement. */
483 replace_phi_edge_with_variable (cond_bb, phi_bb, e1, phi, arg);
485 /* Note that we optimized this PHI. */
491 /* The function absolute_replacement does the main work of doing the absolute
492 replacement. Return true if the replacement is done. Otherwise return
494 bb is the basic block where the replacement is going to be done on. arg0
495 is argument 0 from the phi. Likewise for arg1. */
498 abs_replacement (basic_block cond_bb, basic_block middle_bb,
499 basic_block phi_bb, edge e0 ATTRIBUTE_UNUSED, edge e1,
500 tree phi, tree arg0, tree arg1)
504 block_stmt_iterator bsi;
505 edge true_edge, false_edge;
508 tree rhs = NULL, lhs = NULL;
510 enum tree_code cond_code;
512 /* If the type says honor signed zeros we cannot do this
514 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
517 /* OTHER_BLOCK must have only one executable statement which must have the
518 form arg0 = -arg1 or arg1 = -arg0. */
519 bsi = bsi_start (middle_bb);
520 while (!bsi_end_p (bsi))
522 tree stmt = bsi_stmt (bsi);
524 /* Empty statements and labels are uninteresting. */
525 if (TREE_CODE (stmt) == LABEL_EXPR
526 || IS_EMPTY_STMT (stmt))
532 /* If we found the assignment, but it was not the only executable
533 statement in OTHER_BLOCK, then we can not optimize. */
537 /* If we got here, then we have found the first executable statement
538 in OTHER_BLOCK. If it is anything other than arg = -arg1 or
539 arg1 = -arg0, then we can not optimize. */
540 if (TREE_CODE (stmt) == MODIFY_EXPR)
542 lhs = TREE_OPERAND (stmt, 0);
543 rhs = TREE_OPERAND (stmt, 1);
545 if (TREE_CODE (rhs) == NEGATE_EXPR)
547 rhs = TREE_OPERAND (rhs, 0);
549 /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */
550 if ((lhs == arg0 && rhs == arg1)
551 || (lhs == arg1 && rhs == arg0))
566 /* If we did not find the proper negation assignment, then we can not
571 cond = COND_EXPR_COND (last_stmt (cond_bb));
572 result = PHI_RESULT (phi);
574 /* Only relationals comparing arg[01] against zero are interesting. */
575 cond_code = TREE_CODE (cond);
576 if (cond_code != GT_EXPR && cond_code != GE_EXPR
577 && cond_code != LT_EXPR && cond_code != LE_EXPR)
580 /* Make sure the conditional is arg[01] OP y. */
581 if (TREE_OPERAND (cond, 0) != rhs)
584 if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))
585 ? real_zerop (TREE_OPERAND (cond, 1))
586 : integer_zerop (TREE_OPERAND (cond, 1)))
591 /* We need to know which is the true edge and which is the false
592 edge so that we know if have abs or negative abs. */
593 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
595 /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
596 will need to negate the result. Similarly for LT_EXPR/LE_EXPR if
597 the false edge goes to OTHER_BLOCK. */
598 if (cond_code == GT_EXPR || cond_code == GE_EXPR)
603 if (e->dest == middle_bb)
608 result = duplicate_ssa_name (result, NULL);
611 lhs = make_rename_temp (TREE_TYPE (result), NULL);
615 /* Build the modify expression with abs expression. */
616 new = build (MODIFY_EXPR, TREE_TYPE (lhs),
617 lhs, build1 (ABS_EXPR, TREE_TYPE (lhs), rhs));
619 bsi = bsi_last (cond_bb);
620 bsi_insert_before (&bsi, new, BSI_NEW_STMT);
624 /* Get the right BSI. We want to insert after the recently
625 added ABS_EXPR statement (which we know is the first statement
627 new = build (MODIFY_EXPR, TREE_TYPE (result),
628 result, build1 (NEGATE_EXPR, TREE_TYPE (lhs), lhs));
630 bsi_insert_after (&bsi, new, BSI_NEW_STMT);
633 SSA_NAME_DEF_STMT (result) = new;
634 replace_phi_edge_with_variable (cond_bb, phi_bb, e1, phi, result);
636 /* Note that we optimized this PHI. */
641 /* Always do these optimizations if we have SSA
649 struct tree_opt_pass pass_phiopt =
652 gate_phiopt, /* gate */
653 tree_ssa_phiopt, /* execute */
656 0, /* static_pass_number */
657 TV_TREE_PHIOPT, /* tv_id */
658 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
659 0, /* properties_provided */
660 0, /* properties_destroyed */
661 0, /* todo_flags_start */
662 TODO_cleanup_cfg | TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */
663 | TODO_verify_ssa | TODO_rename_vars
664 | TODO_verify_flow | TODO_verify_stmts,