1 /* Optimization of PHI nodes by converting them into straightline code.
2 Copyright (C) 2004 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
, tree
, tree
, tree
);
41 static bool value_replacement (basic_block
, tree
, tree
, tree
);
42 static bool abs_replacement (basic_block
, tree
, tree
, tree
);
43 static void replace_phi_with_stmt (block_stmt_iterator
, basic_block
,
44 basic_block
, tree
, tree
);
45 static bool candidate_bb_for_phi_optimization (basic_block
,
48 static bool empty_block_p (basic_block
);
50 /* This pass eliminates PHI nodes which can be trivially implemented as
51 an assignment from a conditional expression. ie if we have something
55 if (cond) goto bb2; else goto bb1;
58 x = PHI (0 (bb1), 1 (bb0)
60 We can rewrite that as:
67 bb1 will become unreachable and bb0 and bb2 will almost always
68 be merged into a single block. This occurs often due to gimplification
71 Also done is the following optimization:
74 if (a != b) goto bb2; else goto bb1;
77 x = PHI (a (bb1), b (bb0))
79 We can rewrite that as:
86 This can sometimes occur as a result of other optimizations. A
87 similar transformation is done by the ifcvt RTL optimizer.
89 This pass also eliminates PHI nodes which are really absolute
90 values. i.e. if we have something like:
93 if (a >= 0) goto bb2; else goto bb1;
97 x = PHI (x (bb1), a (bb0));
99 We can rewrite that as:
106 bb1 will become unreachable and bb0 and bb2 will almost always be merged
107 into a single block. Similar transformations are done by the ifcvt
111 tree_ssa_phiopt (void)
114 bool removed_phis
= false;
116 /* Search every basic block for PHI nodes we may be able to optimize. */
119 tree arg0
, arg1
, phi
;
121 /* We're searching for blocks with one PHI node which has two
123 phi
= phi_nodes (bb
);
124 if (phi
&& PHI_CHAIN (phi
) == NULL
125 && PHI_NUM_ARGS (phi
) == 2)
127 arg0
= PHI_ARG_DEF (phi
, 0);
128 arg1
= PHI_ARG_DEF (phi
, 1);
130 /* Do the replacement of conditional if it can be done. */
131 if (conditional_replacement (bb
, phi
, arg0
, arg1
)
132 || value_replacement (bb
, phi
, arg0
, arg1
)
133 || abs_replacement (bb
, phi
, arg0
, arg1
))
135 /* We have done the replacement so we need to rebuild the
136 cfg when this pass is complete. */
142 /* If we removed any PHIs, then we have unreachable blocks and blocks
143 which need to be merged in the CFG. */
148 /* Return TRUE if block BB has no executable statements, otherwise return
151 empty_block_p (basic_block bb
)
153 block_stmt_iterator bsi
;
155 /* BB must have no executable statements. */
156 bsi
= bsi_start (bb
);
157 while (!bsi_end_p (bsi
)
158 && (TREE_CODE (bsi_stmt (bsi
)) == LABEL_EXPR
159 || IS_EMPTY_STMT (bsi_stmt (bsi
))))
162 if (!bsi_end_p (bsi
))
168 /* BB is a basic block which has only one PHI node with precisely two
171 Examine both of BB's predecessors to see if one ends with a
172 COND_EXPR and the other is a successor of the COND_EXPR. If so, then
173 we may be able to optimize PHI nodes at the start of BB.
175 If so, mark store the block with the COND_EXPR into COND_BLOCK_P
176 and the other block into OTHER_BLOCK_P and return true, otherwise
180 candidate_bb_for_phi_optimization (basic_block bb
,
181 basic_block
*cond_block_p
,
182 basic_block
*other_block_p
)
185 basic_block cond_block
, other_block
;
187 /* One of the alternatives must come from a block ending with
189 last0
= last_stmt (bb
->pred
->src
);
190 last1
= last_stmt (bb
->pred
->pred_next
->src
);
191 if (last0
&& TREE_CODE (last0
) == COND_EXPR
)
193 cond_block
= bb
->pred
->src
;
194 other_block
= bb
->pred
->pred_next
->src
;
196 else if (last1
&& TREE_CODE (last1
) == COND_EXPR
)
198 other_block
= bb
->pred
->src
;
199 cond_block
= bb
->pred
->pred_next
->src
;
204 /* COND_BLOCK must have precisely two successors. We indirectly
205 verify that those successors are BB and OTHER_BLOCK. */
206 if (!cond_block
->succ
207 || !cond_block
->succ
->succ_next
208 || cond_block
->succ
->succ_next
->succ_next
209 || (cond_block
->succ
->flags
& EDGE_ABNORMAL
) != 0
210 || (cond_block
->succ
->succ_next
->flags
& EDGE_ABNORMAL
) != 0)
213 /* OTHER_BLOCK must have a single predecessor which is COND_BLOCK,
214 OTHER_BLOCK must have a single successor which is BB and
215 OTHER_BLOCK must have no PHI nodes. */
216 if (!other_block
->pred
217 || other_block
->pred
->src
!= cond_block
218 || other_block
->pred
->pred_next
219 || !other_block
->succ
220 || other_block
->succ
->dest
!= bb
221 || other_block
->succ
->succ_next
222 || phi_nodes (other_block
))
225 *cond_block_p
= cond_block
;
226 *other_block_p
= other_block
;
227 /* Everything looks OK. */
231 /* Replace PHI in block BB with statement NEW. NEW is inserted after
232 BSI. Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
233 is known to have two edges, one of which must reach BB). */
236 replace_phi_with_stmt (block_stmt_iterator bsi
, basic_block bb
,
237 basic_block cond_block
, tree phi
, tree
new)
239 basic_block block_to_remove
;
241 /* Insert our new statement at the head of our block. */
242 bsi_insert_after (&bsi
, new, BSI_NEW_STMT
);
244 /* Register our new statement as the defining statement for
246 SSA_NAME_DEF_STMT (PHI_RESULT (phi
)) = new;
248 /* Remove the now useless PHI node.
250 We do not want to use remove_phi_node since that releases the
251 SSA_NAME as well and the SSA_NAME is still being used. */
252 release_phi_node (phi
);
253 bb_ann (bb
)->phi_nodes
= NULL
;
255 /* Remove the empty basic block. */
256 if (cond_block
->succ
->dest
== bb
)
258 cond_block
->succ
->flags
|= EDGE_FALLTHRU
;
259 cond_block
->succ
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
261 block_to_remove
= cond_block
->succ
->succ_next
->dest
;
265 cond_block
->succ
->succ_next
->flags
|= EDGE_FALLTHRU
;
266 cond_block
->succ
->succ_next
->flags
267 &= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
269 block_to_remove
= cond_block
->succ
->dest
;
271 delete_basic_block (block_to_remove
);
273 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
274 bsi
= bsi_last (cond_block
);
277 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
279 "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
284 /* The function conditional_replacement does the main work of doing the
285 conditional replacement. Return true if the replacement is done.
286 Otherwise return false.
287 BB is the basic block where the replacement is going to be done on. ARG0
288 is argument 0 from PHI. Likewise for ARG1. */
291 conditional_replacement (basic_block bb
, tree phi
, tree arg0
, tree arg1
)
294 tree old_result
= NULL
;
295 basic_block other_block
= NULL
;
296 basic_block cond_block
= NULL
;
298 block_stmt_iterator bsi
;
299 edge true_edge
, false_edge
;
302 /* The PHI arguments have the constants 0 and 1, then convert
303 it to the conditional. */
304 if ((integer_zerop (arg0
) && integer_onep (arg1
))
305 || (integer_zerop (arg1
) && integer_onep (arg0
)))
310 if (!candidate_bb_for_phi_optimization (bb
, &cond_block
, &other_block
)
311 || !empty_block_p (other_block
))
314 /* If the condition is not a naked SSA_NAME and its type does not
315 match the type of the result, then we have to create a new
316 variable to optimize this case as it would likely create
317 non-gimple code when the condition was converted to the
319 cond
= COND_EXPR_COND (last_stmt (cond_block
));
320 result
= PHI_RESULT (phi
);
321 if (TREE_CODE (cond
) != SSA_NAME
322 && !lang_hooks
.types_compatible_p (TREE_TYPE (cond
), TREE_TYPE (result
)))
324 new_var
= make_rename_temp (TREE_TYPE (cond
), NULL
);
329 /* If the condition was a naked SSA_NAME and the type is not the
330 same as the type of the result, then convert the type of the
332 if (!lang_hooks
.types_compatible_p (TREE_TYPE (cond
), TREE_TYPE (result
)))
333 cond
= fold_convert (TREE_TYPE (result
), cond
);
335 /* We need to know which is the true edge and which is the false
336 edge so that we know when to invert the condition below. */
337 extract_true_false_edges_from_block (cond_block
, &true_edge
, &false_edge
);
339 /* Insert our new statement at the head of our block. */
340 bsi
= bsi_start (bb
);
345 if (TREE_CODE_CLASS (TREE_CODE (old_result
)) != '<')
348 new1
= build (TREE_CODE (old_result
), TREE_TYPE (result
),
349 TREE_OPERAND (old_result
, 0),
350 TREE_OPERAND (old_result
, 1));
352 new1
= build (MODIFY_EXPR
, TREE_TYPE (result
), new_var
, new1
);
353 bsi_insert_after (&bsi
, new1
, BSI_NEW_STMT
);
356 /* At this point we know we have a COND_EXPR with two successors.
357 One successor is BB, the other successor is an empty block which
358 falls through into BB.
360 There is a single PHI node at the join point (BB) and its arguments
361 are constants (0, 1).
363 So, given the condition COND, and the two PHI arguments, we can
364 rewrite this PHI into non-branching code:
366 dest = (COND) or dest = COND'
368 We use the condition as-is if the argument associated with the
369 true edge has the value one or the argument associated with the
370 false edge as the value zero. Note that those conditions are not
371 the same since only one of the outgoing edges from the COND_EXPR
372 will directly reach BB and thus be associated with an argument. */
373 if ((PHI_ARG_EDGE (phi
, 0) == true_edge
&& integer_onep (arg0
))
374 || (PHI_ARG_EDGE (phi
, 0) == false_edge
&& integer_zerop (arg0
))
375 || (PHI_ARG_EDGE (phi
, 1) == true_edge
&& integer_onep (arg1
))
376 || (PHI_ARG_EDGE (phi
, 1) == false_edge
&& integer_zerop (arg1
)))
378 new = build (MODIFY_EXPR
, TREE_TYPE (PHI_RESULT (phi
)),
379 PHI_RESULT (phi
), cond
);
383 tree cond1
= invert_truthvalue (cond
);
386 /* If what we get back is a conditional expression, there is no
387 way that it can be gimple. */
388 if (TREE_CODE (cond
) == COND_EXPR
)
391 /* If what we get back is not gimple try to create it as gimple by
392 using a temporary variable. */
393 if (is_gimple_cast (cond
)
394 && !is_gimple_val (TREE_OPERAND (cond
, 0)))
396 tree temp
= TREE_OPERAND (cond
, 0);
397 tree new_var_1
= make_rename_temp (TREE_TYPE (temp
), NULL
);
398 new = build (MODIFY_EXPR
, TREE_TYPE (new_var_1
), new_var_1
, temp
);
399 bsi_insert_after (&bsi
, new, BSI_NEW_STMT
);
400 cond
= fold_convert (TREE_TYPE (result
), new_var_1
);
403 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
404 && !is_gimple_val (TREE_OPERAND (cond
, 0)))
407 new = build (MODIFY_EXPR
, TREE_TYPE (PHI_RESULT (phi
)),
408 PHI_RESULT (phi
), cond
);
411 replace_phi_with_stmt (bsi
, bb
, cond_block
, phi
, new);
413 /* Note that we optimized this PHI. */
417 /* The function value_replacement does the main work of doing the value
418 replacement. Return true if the replacement is done. Otherwise return
420 BB is the basic block where the replacement is going to be done on. ARG0
421 is argument 0 from the PHI. Likewise for ARG1. */
424 value_replacement (basic_block bb
, tree phi
, tree arg0
, tree arg1
)
427 basic_block other_block
= NULL
;
428 basic_block cond_block
= NULL
;
430 edge true_edge
, false_edge
;
432 /* If the type says honor signed zeros we cannot do this
434 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1
))))
437 if (!candidate_bb_for_phi_optimization (bb
, &cond_block
, &other_block
)
438 || !empty_block_p (other_block
))
441 cond
= COND_EXPR_COND (last_stmt (cond_block
));
442 result
= PHI_RESULT (phi
);
444 /* This transformation is only valid for equality comparisons. */
445 if (TREE_CODE (cond
) != NE_EXPR
&& TREE_CODE (cond
) != EQ_EXPR
)
448 /* We need to know which is the true edge and which is the false
449 edge so that we know if have abs or negative abs. */
450 extract_true_false_edges_from_block (cond_block
, &true_edge
, &false_edge
);
452 /* At this point we know we have a COND_EXPR with two successors.
453 One successor is BB, the other successor is an empty block which
454 falls through into BB.
456 The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
458 There is a single PHI node at the join point (BB) with two arguments.
460 We now need to verify that the two arguments in the PHI node match
461 the two arguments to the equality comparison. */
463 if ((operand_equal_p (arg0
, TREE_OPERAND (cond
, 0), 0)
464 && operand_equal_p (arg1
, TREE_OPERAND (cond
, 1), 0))
465 || (operand_equal_p (arg1
, TREE_OPERAND (cond
, 0), 0)
466 && operand_equal_p (arg0
, TREE_OPERAND (cond
, 1), 0)))
471 /* For NE_EXPR, we want to build an assignment result = arg where
472 arg is the PHI argument associated with the true edge. For
473 EQ_EXPR we want the PHI argument associated with the false edge. */
474 e
= (TREE_CODE (cond
) == NE_EXPR
? true_edge
: false_edge
);
476 /* Unfortunately, E may not reach BB (it may instead have gone to
477 OTHER_BLOCK). If that is the case, then we want the single outgoing
478 edge from OTHER_BLOCK which reaches BB and represents the desired
479 path from COND_BLOCK. */
480 if (e
->dest
== other_block
)
483 /* Now we know the incoming edge to BB that has the argument for the
484 RHS of our new assignment statement. */
485 if (PHI_ARG_EDGE (phi
, 0) == e
)
490 /* Build the new assignment. */
491 new = build (MODIFY_EXPR
, TREE_TYPE (result
), result
, arg
);
493 replace_phi_with_stmt (bsi_start (bb
), bb
, cond_block
, phi
, new);
495 /* Note that we optimized this PHI. */
501 /* The function absolute_replacement does the main work of doing the absolute
502 replacement. Return true if the replacement is done. Otherwise return
504 bb is the basic block where the replacement is going to be done on. arg0
505 is argument 0 from the phi. Likewise for arg1. */
507 abs_replacement (basic_block bb
, tree phi
, tree arg0
, tree arg1
)
510 basic_block other_block
= NULL
;
511 basic_block cond_block
= NULL
;
513 block_stmt_iterator bsi
;
514 edge true_edge
, false_edge
;
517 tree rhs
= NULL
, lhs
= NULL
;
519 enum tree_code cond_code
;
521 /* If the type says honor signed zeros we cannot do this
523 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1
))))
526 if (!candidate_bb_for_phi_optimization (bb
, &cond_block
, &other_block
))
529 /* OTHER_BLOCK must have only one executable statement which must have the
530 form arg0 = -arg1 or arg1 = -arg0. */
531 bsi
= bsi_start (other_block
);
532 while (!bsi_end_p (bsi
))
534 tree stmt
= bsi_stmt (bsi
);
536 /* Empty statements and labels are uninteresting. */
537 if (TREE_CODE (stmt
) == LABEL_EXPR
538 || IS_EMPTY_STMT (stmt
))
544 /* If we found the assignment, but it was not the only executable
545 statement in OTHER_BLOCK, then we can not optimize. */
549 /* If we got here, then we have found the first executable statement
550 in OTHER_BLOCK. If it is anything other than arg = -arg1 or
551 arg1 = -arg0, then we can not optimize. */
552 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
554 lhs
= TREE_OPERAND (stmt
, 0);
555 rhs
= TREE_OPERAND (stmt
, 1);
557 if (TREE_CODE (rhs
) == NEGATE_EXPR
)
559 rhs
= TREE_OPERAND (rhs
, 0);
561 /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */
562 if ((lhs
== arg0
&& rhs
== arg1
)
563 || (lhs
== arg1
&& rhs
== arg0
))
578 /* If we did not find the proper negation assignment, then we can not
583 cond
= COND_EXPR_COND (last_stmt (cond_block
));
584 result
= PHI_RESULT (phi
);
586 /* Only relationals comparing arg[01] against zero are interesting. */
587 cond_code
= TREE_CODE (cond
);
588 if (cond_code
!= GT_EXPR
&& cond_code
!= GE_EXPR
589 && cond_code
!= LT_EXPR
&& cond_code
!= LE_EXPR
)
592 /* Make sure the conditional is arg[01] OP y. */
593 if (TREE_OPERAND (cond
, 0) != rhs
)
596 if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (cond
, 1)))
597 ? real_zerop (TREE_OPERAND (cond
, 1))
598 : integer_zerop (TREE_OPERAND (cond
, 1)))
603 /* We need to know which is the true edge and which is the false
604 edge so that we know if have abs or negative abs. */
605 extract_true_false_edges_from_block (cond_block
, &true_edge
, &false_edge
);
607 /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
608 will need to negate the result. Similarly for LT_EXPR/LE_EXPR if
609 the false edge goes to OTHER_BLOCK. */
610 if (cond_code
== GT_EXPR
|| cond_code
== GE_EXPR
)
615 if (e
->dest
== other_block
)
621 lhs
= make_rename_temp (TREE_TYPE (result
), NULL
);
625 /* Build the modify expression with abs expression. */
626 new = build (MODIFY_EXPR
, TREE_TYPE (lhs
),
627 lhs
, build1 (ABS_EXPR
, TREE_TYPE (lhs
), rhs
));
629 replace_phi_with_stmt (bsi_start (bb
), bb
, cond_block
, phi
, new);
634 /* Get the right BSI. We want to insert after the recently
635 added ABS_EXPR statement (which we know is the first statement
637 bsi
= bsi_start (bb
);
639 new = build (MODIFY_EXPR
, TREE_TYPE (result
),
640 result
, build1 (NEGATE_EXPR
, TREE_TYPE (lhs
), lhs
));
642 bsi_insert_after (&bsi
, new, BSI_NEW_STMT
);
644 /* Register the new statement as defining the temporary -- this is
645 normally done by replace_phi_with_stmt, but the link will be wrong
646 if we had to negate the resulting value. */
647 SSA_NAME_DEF_STMT (result
) = new;
650 /* Note that we optimized this PHI. */
655 /* Always do these optimizations if we have SSA
663 struct tree_opt_pass pass_phiopt
=
666 gate_phiopt
, /* gate */
667 tree_ssa_phiopt
, /* execute */
670 0, /* static_pass_number */
671 TV_TREE_PHIOPT
, /* tv_id */
672 PROP_cfg
| PROP_ssa
, /* properties_required */
673 0, /* properties_provided */
674 0, /* properties_destroyed */
675 0, /* todo_flags_start */
676 TODO_dump_func
| TODO_ggc_collect
/* todo_flags_finish */
677 | TODO_verify_ssa
| TODO_rename_vars