1 /* Optimization of PHI nodes by converting them into straightline code.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation,
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
29 #include "basic-block.h"
31 #include "tree-flow.h"
32 #include "tree-pass.h"
33 #include "tree-dump.h"
34 #include "langhooks.h"
35 #include "pointer-set.h"
38 static unsigned int tree_ssa_phiopt (void);
39 static unsigned int tree_ssa_phiopt_worker (bool);
40 static bool conditional_replacement (basic_block
, basic_block
,
41 edge
, edge
, gimple
, tree
, tree
);
42 static bool value_replacement (basic_block
, basic_block
,
43 edge
, edge
, gimple
, tree
, tree
);
44 static bool minmax_replacement (basic_block
, basic_block
,
45 edge
, edge
, gimple
, tree
, tree
);
46 static bool abs_replacement (basic_block
, basic_block
,
47 edge
, edge
, gimple
, tree
, tree
);
48 static bool cond_store_replacement (basic_block
, basic_block
, edge
, edge
,
49 struct pointer_set_t
*);
50 static struct pointer_set_t
* get_non_trapping (void);
51 static void replace_phi_edge_with_variable (basic_block
, edge
, gimple
, tree
);
53 /* This pass tries to replaces an if-then-else block with an
54 assignment. We have four kinds of transformations. Some of these
55 transformations are also performed by the ifcvt RTL optimizer.
57 Conditional Replacement
58 -----------------------
60 This transformation, implemented in conditional_replacement,
64 if (cond) goto bb2; else goto bb1;
67 x = PHI <0 (bb1), 1 (bb0), ...>;
75 x = PHI <x' (bb0), ...>;
77 We remove bb1 as it becomes unreachable. This occurs often due to
78 gimplification of conditionals.
83 This transformation, implemented in value_replacement, replaces
86 if (a != b) goto bb2; else goto bb1;
89 x = PHI <a (bb1), b (bb0), ...>;
95 x = PHI <b (bb0), ...>;
97 This opportunity can sometimes occur as a result of other
103 This transformation, implemented in abs_replacement, replaces
106 if (a >= 0) goto bb2; else goto bb1;
110 x = PHI <x (bb1), a (bb0), ...>;
117 x = PHI <x' (bb0), ...>;
122 This transformation, minmax_replacement replaces
125 if (a <= b) goto bb2; else goto bb1;
128 x = PHI <b (bb1), a (bb0), ...>;
135 x = PHI <x' (bb0), ...>;
137 A similar transformation is done for MAX_EXPR. */
140 tree_ssa_phiopt (void)
142 return tree_ssa_phiopt_worker (false);
145 /* This pass tries to transform conditional stores into unconditional
146 ones, enabling further simplifications with the simpler then and else
147 blocks. In particular it replaces this:
150 if (cond) goto bb2; else goto bb1;
158 if (cond) goto bb1; else goto bb2;
162 condtmp = PHI <RHS, condtmp'>
165 This transformation can only be done under several constraints,
169 tree_ssa_cs_elim (void)
171 return tree_ssa_phiopt_worker (true);
174 /* For conditional store replacement we need a temporary to
175 put the old contents of the memory in. */
176 static tree condstoretemp
;
178 /* The core routine of conditional store replacement and normal
179 phi optimizations. Both share much of the infrastructure in how
180 to match applicable basic block patterns. DO_STORE_ELIM is true
181 when we want to do conditional store replacement, false otherwise. */
183 tree_ssa_phiopt_worker (bool do_store_elim
)
186 basic_block
*bb_order
;
188 bool cfgchanged
= false;
189 struct pointer_set_t
*nontrap
= 0;
193 condstoretemp
= NULL_TREE
;
194 /* Calculate the set of non-trapping memory accesses. */
195 nontrap
= get_non_trapping ();
198 /* Search every basic block for COND_EXPR we may be able to optimize.
200 We walk the blocks in order that guarantees that a block with
201 a single predecessor is processed before the predecessor.
202 This ensures that we collapse inner ifs before visiting the
203 outer ones, and also that we do not try to visit a removed
205 bb_order
= blocks_in_phiopt_order ();
206 n
= n_basic_blocks
- NUM_FIXED_BLOCKS
;
208 for (i
= 0; i
< n
; i
++)
210 gimple cond_stmt
, phi
;
211 basic_block bb1
, bb2
;
217 cond_stmt
= last_stmt (bb
);
218 /* Check to see if the last statement is a GIMPLE_COND. */
220 || gimple_code (cond_stmt
) != GIMPLE_COND
)
223 e1
= EDGE_SUCC (bb
, 0);
225 e2
= EDGE_SUCC (bb
, 1);
228 /* We cannot do the optimization on abnormal edges. */
229 if ((e1
->flags
& EDGE_ABNORMAL
) != 0
230 || (e2
->flags
& EDGE_ABNORMAL
) != 0)
233 /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
234 if (EDGE_COUNT (bb1
->succs
) == 0
236 || EDGE_COUNT (bb2
->succs
) == 0)
239 /* Find the bb which is the fall through to the other. */
240 if (EDGE_SUCC (bb1
, 0)->dest
== bb2
)
242 else if (EDGE_SUCC (bb2
, 0)->dest
== bb1
)
244 basic_block bb_tmp
= bb1
;
254 e1
= EDGE_SUCC (bb1
, 0);
256 /* Make sure that bb1 is just a fall through. */
257 if (!single_succ_p (bb1
)
258 || (e1
->flags
& EDGE_FALLTHRU
) == 0)
261 /* Also make sure that bb1 only have one predecessor and that it
263 if (!single_pred_p (bb1
)
264 || single_pred (bb1
) != bb
)
269 /* bb1 is the middle block, bb2 the join block, bb the split block,
270 e1 the fallthrough edge from bb1 to bb2. We can't do the
271 optimization if the join block has more than two predecessors. */
272 if (EDGE_COUNT (bb2
->preds
) > 2)
274 if (cond_store_replacement (bb1
, bb2
, e1
, e2
, nontrap
))
279 gimple_seq phis
= phi_nodes (bb2
);
281 /* Check to make sure that there is only one PHI node.
282 TODO: we could do it with more than one iff the other PHI nodes
283 have the same elements for these two edges. */
284 if (! gimple_seq_singleton_p (phis
))
287 phi
= gsi_stmt (gsi_start (phis
));
288 arg0
= gimple_phi_arg_def (phi
, e1
->dest_idx
);
289 arg1
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
291 /* Something is wrong if we cannot find the arguments in the PHI
293 gcc_assert (arg0
!= NULL
&& arg1
!= NULL
);
295 /* Do the replacement of conditional if it can be done. */
296 if (conditional_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
))
298 else if (value_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
))
300 else if (abs_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
))
302 else if (minmax_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
))
310 pointer_set_destroy (nontrap
);
311 /* If the CFG has changed, we should cleanup the CFG. */
312 if (cfgchanged
&& do_store_elim
)
314 /* In cond-store replacement we have added some loads on edges
315 and new VOPS (as we moved the store, and created a load). */
316 gsi_commit_edge_inserts ();
317 return TODO_cleanup_cfg
| TODO_update_ssa_only_virtuals
;
320 return TODO_cleanup_cfg
;
324 /* Returns the list of basic blocks in the function in an order that guarantees
325 that if a block X has just a single predecessor Y, then Y is after X in the
329 blocks_in_phiopt_order (void)
332 basic_block
*order
= XNEWVEC (basic_block
, n_basic_blocks
);
333 unsigned n
= n_basic_blocks
- NUM_FIXED_BLOCKS
;
335 sbitmap visited
= sbitmap_alloc (last_basic_block
);
337 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
338 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
340 sbitmap_zero (visited
);
342 MARK_VISITED (ENTRY_BLOCK_PTR
);
348 /* Walk the predecessors of x as long as they have precisely one
349 predecessor and add them to the list, so that they get stored
352 single_pred_p (y
) && !VISITED_P (single_pred (y
));
355 for (y
= x
, i
= n
- np
;
356 single_pred_p (y
) && !VISITED_P (single_pred (y
));
357 y
= single_pred (y
), i
++)
365 gcc_assert (i
== n
- 1);
369 sbitmap_free (visited
);
378 /* Return TRUE if block BB has no executable statements, otherwise return
382 empty_block_p (basic_block bb
)
384 /* BB must have no executable statements. */
385 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
388 if (is_gimple_debug (gsi_stmt (gsi
)))
389 gsi_next_nondebug (&gsi
);
390 return gsi_end_p (gsi
);
393 /* Replace PHI node element whose edge is E in block BB with variable NEW.
394 Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
395 is known to have two edges, one of which must reach BB). */
398 replace_phi_edge_with_variable (basic_block cond_block
,
399 edge e
, gimple phi
, tree new_tree
)
401 basic_block bb
= gimple_bb (phi
);
402 basic_block block_to_remove
;
403 gimple_stmt_iterator gsi
;
405 /* Change the PHI argument to new. */
406 SET_USE (PHI_ARG_DEF_PTR (phi
, e
->dest_idx
), new_tree
);
408 /* Remove the empty basic block. */
409 if (EDGE_SUCC (cond_block
, 0)->dest
== bb
)
411 EDGE_SUCC (cond_block
, 0)->flags
|= EDGE_FALLTHRU
;
412 EDGE_SUCC (cond_block
, 0)->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
413 EDGE_SUCC (cond_block
, 0)->probability
= REG_BR_PROB_BASE
;
414 EDGE_SUCC (cond_block
, 0)->count
+= EDGE_SUCC (cond_block
, 1)->count
;
416 block_to_remove
= EDGE_SUCC (cond_block
, 1)->dest
;
420 EDGE_SUCC (cond_block
, 1)->flags
|= EDGE_FALLTHRU
;
421 EDGE_SUCC (cond_block
, 1)->flags
422 &= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
423 EDGE_SUCC (cond_block
, 1)->probability
= REG_BR_PROB_BASE
;
424 EDGE_SUCC (cond_block
, 1)->count
+= EDGE_SUCC (cond_block
, 0)->count
;
426 block_to_remove
= EDGE_SUCC (cond_block
, 0)->dest
;
428 delete_basic_block (block_to_remove
);
430 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
431 gsi
= gsi_last_bb (cond_block
);
432 gsi_remove (&gsi
, true);
434 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
436 "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
441 /* The function conditional_replacement does the main work of doing the
442 conditional replacement. Return true if the replacement is done.
443 Otherwise return false.
444 BB is the basic block where the replacement is going to be done on. ARG0
445 is argument 0 from PHI. Likewise for ARG1. */
448 conditional_replacement (basic_block cond_bb
, basic_block middle_bb
,
449 edge e0
, edge e1
, gimple phi
,
450 tree arg0
, tree arg1
)
453 gimple stmt
, new_stmt
;
455 gimple_stmt_iterator gsi
;
456 edge true_edge
, false_edge
;
457 tree new_var
, new_var2
;
459 /* FIXME: Gimplification of complex type is too hard for now. */
460 if (TREE_CODE (TREE_TYPE (arg0
)) == COMPLEX_TYPE
461 || TREE_CODE (TREE_TYPE (arg1
)) == COMPLEX_TYPE
)
464 /* The PHI arguments have the constants 0 and 1, then convert
465 it to the conditional. */
466 if ((integer_zerop (arg0
) && integer_onep (arg1
))
467 || (integer_zerop (arg1
) && integer_onep (arg0
)))
472 if (!empty_block_p (middle_bb
))
475 /* At this point we know we have a GIMPLE_COND with two successors.
476 One successor is BB, the other successor is an empty block which
477 falls through into BB.
479 There is a single PHI node at the join point (BB) and its arguments
480 are constants (0, 1).
482 So, given the condition COND, and the two PHI arguments, we can
483 rewrite this PHI into non-branching code:
485 dest = (COND) or dest = COND'
487 We use the condition as-is if the argument associated with the
488 true edge has the value one or the argument associated with the
489 false edge as the value zero. Note that those conditions are not
490 the same since only one of the outgoing edges from the GIMPLE_COND
491 will directly reach BB and thus be associated with an argument. */
493 stmt
= last_stmt (cond_bb
);
494 result
= PHI_RESULT (phi
);
496 /* To handle special cases like floating point comparison, it is easier and
497 less error-prone to build a tree and gimplify it on the fly though it is
499 cond
= fold_build2 (gimple_cond_code (stmt
), boolean_type_node
,
500 gimple_cond_lhs (stmt
), gimple_cond_rhs (stmt
));
502 /* We need to know which is the true edge and which is the false
503 edge so that we know when to invert the condition below. */
504 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
505 if ((e0
== true_edge
&& integer_zerop (arg0
))
506 || (e0
== false_edge
&& integer_onep (arg0
))
507 || (e1
== true_edge
&& integer_zerop (arg1
))
508 || (e1
== false_edge
&& integer_onep (arg1
)))
509 cond
= fold_build1 (TRUTH_NOT_EXPR
, TREE_TYPE (cond
), cond
);
511 /* Insert our new statements at the end of conditional block before the
513 gsi
= gsi_for_stmt (stmt
);
514 new_var
= force_gimple_operand_gsi (&gsi
, cond
, true, NULL
, true,
517 if (!useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (new_var
)))
519 source_location locus_0
, locus_1
;
521 new_var2
= create_tmp_var (TREE_TYPE (result
), NULL
);
522 add_referenced_var (new_var2
);
523 new_stmt
= gimple_build_assign_with_ops (CONVERT_EXPR
, new_var2
,
525 new_var2
= make_ssa_name (new_var2
, new_stmt
);
526 gimple_assign_set_lhs (new_stmt
, new_var2
);
527 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
530 /* Set the locus to the first argument, unless is doesn't have one. */
531 locus_0
= gimple_phi_arg_location (phi
, 0);
532 locus_1
= gimple_phi_arg_location (phi
, 1);
533 if (locus_0
== UNKNOWN_LOCATION
)
535 gimple_set_location (new_stmt
, locus_0
);
538 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, new_var
);
540 /* Note that we optimized this PHI. */
544 /* The function value_replacement does the main work of doing the value
545 replacement. Return true if the replacement is done. Otherwise return
547 BB is the basic block where the replacement is going to be done on. ARG0
548 is argument 0 from the PHI. Likewise for ARG1. */
551 value_replacement (basic_block cond_bb
, basic_block middle_bb
,
552 edge e0
, edge e1
, gimple phi
,
553 tree arg0
, tree arg1
)
556 edge true_edge
, false_edge
;
559 /* If the type says honor signed zeros we cannot do this
561 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1
))))
564 if (!empty_block_p (middle_bb
))
567 cond
= last_stmt (cond_bb
);
568 code
= gimple_cond_code (cond
);
570 /* This transformation is only valid for equality comparisons. */
571 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
574 /* We need to know which is the true edge and which is the false
575 edge so that we know if have abs or negative abs. */
576 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
578 /* At this point we know we have a COND_EXPR with two successors.
579 One successor is BB, the other successor is an empty block which
580 falls through into BB.
582 The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
584 There is a single PHI node at the join point (BB) with two arguments.
586 We now need to verify that the two arguments in the PHI node match
587 the two arguments to the equality comparison. */
589 if ((operand_equal_for_phi_arg_p (arg0
, gimple_cond_lhs (cond
))
590 && operand_equal_for_phi_arg_p (arg1
, gimple_cond_rhs (cond
)))
591 || (operand_equal_for_phi_arg_p (arg1
, gimple_cond_lhs (cond
))
592 && operand_equal_for_phi_arg_p (arg0
, gimple_cond_rhs (cond
))))
597 /* For NE_EXPR, we want to build an assignment result = arg where
598 arg is the PHI argument associated with the true edge. For
599 EQ_EXPR we want the PHI argument associated with the false edge. */
600 e
= (code
== NE_EXPR
? true_edge
: false_edge
);
602 /* Unfortunately, E may not reach BB (it may instead have gone to
603 OTHER_BLOCK). If that is the case, then we want the single outgoing
604 edge from OTHER_BLOCK which reaches BB and represents the desired
605 path from COND_BLOCK. */
606 if (e
->dest
== middle_bb
)
607 e
= single_succ_edge (e
->dest
);
609 /* Now we know the incoming edge to BB that has the argument for the
610 RHS of our new assignment statement. */
616 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, arg
);
618 /* Note that we optimized this PHI. */
624 /* The function minmax_replacement does the main work of doing the minmax
625 replacement. Return true if the replacement is done. Otherwise return
627 BB is the basic block where the replacement is going to be done on. ARG0
628 is argument 0 from the PHI. Likewise for ARG1. */
631 minmax_replacement (basic_block cond_bb
, basic_block middle_bb
,
632 edge e0
, edge e1
, gimple phi
,
633 tree arg0
, tree arg1
)
636 gimple cond
, new_stmt
;
637 edge true_edge
, false_edge
;
638 enum tree_code cmp
, minmax
, ass_code
;
639 tree smaller
, larger
, arg_true
, arg_false
;
640 gimple_stmt_iterator gsi
, gsi_from
;
642 type
= TREE_TYPE (PHI_RESULT (phi
));
644 /* The optimization may be unsafe due to NaNs. */
645 if (HONOR_NANS (TYPE_MODE (type
)))
648 cond
= last_stmt (cond_bb
);
649 cmp
= gimple_cond_code (cond
);
650 result
= PHI_RESULT (phi
);
652 /* This transformation is only valid for order comparisons. Record which
653 operand is smaller/larger if the result of the comparison is true. */
654 if (cmp
== LT_EXPR
|| cmp
== LE_EXPR
)
656 smaller
= gimple_cond_lhs (cond
);
657 larger
= gimple_cond_rhs (cond
);
659 else if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
661 smaller
= gimple_cond_rhs (cond
);
662 larger
= gimple_cond_lhs (cond
);
667 /* We need to know which is the true edge and which is the false
668 edge so that we know if have abs or negative abs. */
669 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
671 /* Forward the edges over the middle basic block. */
672 if (true_edge
->dest
== middle_bb
)
673 true_edge
= EDGE_SUCC (true_edge
->dest
, 0);
674 if (false_edge
->dest
== middle_bb
)
675 false_edge
= EDGE_SUCC (false_edge
->dest
, 0);
679 gcc_assert (false_edge
== e1
);
685 gcc_assert (false_edge
== e0
);
686 gcc_assert (true_edge
== e1
);
691 if (empty_block_p (middle_bb
))
693 if (operand_equal_for_phi_arg_p (arg_true
, smaller
)
694 && operand_equal_for_phi_arg_p (arg_false
, larger
))
698 if (smaller < larger)
704 else if (operand_equal_for_phi_arg_p (arg_false
, smaller
)
705 && operand_equal_for_phi_arg_p (arg_true
, larger
))
712 /* Recognize the following case, assuming d <= u:
718 This is equivalent to
723 gimple assign
= last_and_only_stmt (middle_bb
);
724 tree lhs
, op0
, op1
, bound
;
727 || gimple_code (assign
) != GIMPLE_ASSIGN
)
730 lhs
= gimple_assign_lhs (assign
);
731 ass_code
= gimple_assign_rhs_code (assign
);
732 if (ass_code
!= MAX_EXPR
&& ass_code
!= MIN_EXPR
)
734 op0
= gimple_assign_rhs1 (assign
);
735 op1
= gimple_assign_rhs2 (assign
);
737 if (true_edge
->src
== middle_bb
)
739 /* We got here if the condition is true, i.e., SMALLER < LARGER. */
740 if (!operand_equal_for_phi_arg_p (lhs
, arg_true
))
743 if (operand_equal_for_phi_arg_p (arg_false
, larger
))
747 if (smaller < larger)
749 r' = MAX_EXPR (smaller, bound)
751 r = PHI <r', larger> --> to be turned to MIN_EXPR. */
752 if (ass_code
!= MAX_EXPR
)
756 if (operand_equal_for_phi_arg_p (op0
, smaller
))
758 else if (operand_equal_for_phi_arg_p (op1
, smaller
))
763 /* We need BOUND <= LARGER. */
764 if (!integer_nonzerop (fold_build2 (LE_EXPR
, boolean_type_node
,
768 else if (operand_equal_for_phi_arg_p (arg_false
, smaller
))
772 if (smaller < larger)
774 r' = MIN_EXPR (larger, bound)
776 r = PHI <r', smaller> --> to be turned to MAX_EXPR. */
777 if (ass_code
!= MIN_EXPR
)
781 if (operand_equal_for_phi_arg_p (op0
, larger
))
783 else if (operand_equal_for_phi_arg_p (op1
, larger
))
788 /* We need BOUND >= SMALLER. */
789 if (!integer_nonzerop (fold_build2 (GE_EXPR
, boolean_type_node
,
798 /* We got here if the condition is false, i.e., SMALLER > LARGER. */
799 if (!operand_equal_for_phi_arg_p (lhs
, arg_false
))
802 if (operand_equal_for_phi_arg_p (arg_true
, larger
))
806 if (smaller > larger)
808 r' = MIN_EXPR (smaller, bound)
810 r = PHI <r', larger> --> to be turned to MAX_EXPR. */
811 if (ass_code
!= MIN_EXPR
)
815 if (operand_equal_for_phi_arg_p (op0
, smaller
))
817 else if (operand_equal_for_phi_arg_p (op1
, smaller
))
822 /* We need BOUND >= LARGER. */
823 if (!integer_nonzerop (fold_build2 (GE_EXPR
, boolean_type_node
,
827 else if (operand_equal_for_phi_arg_p (arg_true
, smaller
))
831 if (smaller > larger)
833 r' = MAX_EXPR (larger, bound)
835 r = PHI <r', smaller> --> to be turned to MIN_EXPR. */
836 if (ass_code
!= MAX_EXPR
)
840 if (operand_equal_for_phi_arg_p (op0
, larger
))
842 else if (operand_equal_for_phi_arg_p (op1
, larger
))
847 /* We need BOUND <= SMALLER. */
848 if (!integer_nonzerop (fold_build2 (LE_EXPR
, boolean_type_node
,
856 /* Move the statement from the middle block. */
857 gsi
= gsi_last_bb (cond_bb
);
858 gsi_from
= gsi_last_nondebug_bb (middle_bb
);
859 gsi_move_before (&gsi_from
, &gsi
);
862 /* Emit the statement to compute min/max. */
863 result
= duplicate_ssa_name (PHI_RESULT (phi
), NULL
);
864 new_stmt
= gimple_build_assign_with_ops (minmax
, result
, arg0
, arg1
);
865 gsi
= gsi_last_bb (cond_bb
);
866 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
868 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, result
);
872 /* The function absolute_replacement does the main work of doing the absolute
873 replacement. Return true if the replacement is done. Otherwise return
875 bb is the basic block where the replacement is going to be done on. arg0
876 is argument 0 from the phi. Likewise for arg1. */
879 abs_replacement (basic_block cond_bb
, basic_block middle_bb
,
880 edge e0 ATTRIBUTE_UNUSED
, edge e1
,
881 gimple phi
, tree arg0
, tree arg1
)
884 gimple new_stmt
, cond
;
885 gimple_stmt_iterator gsi
;
886 edge true_edge
, false_edge
;
891 enum tree_code cond_code
;
893 /* If the type says honor signed zeros we cannot do this
895 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1
))))
898 /* OTHER_BLOCK must have only one executable statement which must have the
899 form arg0 = -arg1 or arg1 = -arg0. */
901 assign
= last_and_only_stmt (middle_bb
);
902 /* If we did not find the proper negation assignment, then we can not
907 /* If we got here, then we have found the only executable statement
908 in OTHER_BLOCK. If it is anything other than arg = -arg1 or
909 arg1 = -arg0, then we can not optimize. */
910 if (gimple_code (assign
) != GIMPLE_ASSIGN
)
913 lhs
= gimple_assign_lhs (assign
);
915 if (gimple_assign_rhs_code (assign
) != NEGATE_EXPR
)
918 rhs
= gimple_assign_rhs1 (assign
);
920 /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */
921 if (!(lhs
== arg0
&& rhs
== arg1
)
922 && !(lhs
== arg1
&& rhs
== arg0
))
925 cond
= last_stmt (cond_bb
);
926 result
= PHI_RESULT (phi
);
928 /* Only relationals comparing arg[01] against zero are interesting. */
929 cond_code
= gimple_cond_code (cond
);
930 if (cond_code
!= GT_EXPR
&& cond_code
!= GE_EXPR
931 && cond_code
!= LT_EXPR
&& cond_code
!= LE_EXPR
)
934 /* Make sure the conditional is arg[01] OP y. */
935 if (gimple_cond_lhs (cond
) != rhs
)
938 if (FLOAT_TYPE_P (TREE_TYPE (gimple_cond_rhs (cond
)))
939 ? real_zerop (gimple_cond_rhs (cond
))
940 : integer_zerop (gimple_cond_rhs (cond
)))
945 /* We need to know which is the true edge and which is the false
946 edge so that we know if have abs or negative abs. */
947 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
949 /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
950 will need to negate the result. Similarly for LT_EXPR/LE_EXPR if
951 the false edge goes to OTHER_BLOCK. */
952 if (cond_code
== GT_EXPR
|| cond_code
== GE_EXPR
)
957 if (e
->dest
== middle_bb
)
962 result
= duplicate_ssa_name (result
, NULL
);
966 tree tmp
= create_tmp_var (TREE_TYPE (result
), NULL
);
967 add_referenced_var (tmp
);
968 lhs
= make_ssa_name (tmp
, NULL
);
973 /* Build the modify expression with abs expression. */
974 new_stmt
= gimple_build_assign_with_ops (ABS_EXPR
, lhs
, rhs
, NULL
);
976 gsi
= gsi_last_bb (cond_bb
);
977 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
981 /* Get the right GSI. We want to insert after the recently
982 added ABS_EXPR statement (which we know is the first statement
984 new_stmt
= gimple_build_assign_with_ops (NEGATE_EXPR
, result
, lhs
, NULL
);
986 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
989 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, result
);
991 /* Note that we optimized this PHI. */
995 /* Auxiliary functions to determine the set of memory accesses which
996 can't trap because they are preceded by accesses to the same memory
997 portion. We do that for INDIRECT_REFs, so we only need to track
998 the SSA_NAME of the pointer indirectly referenced. The algorithm
999 simply is a walk over all instructions in dominator order. When
1000 we see an INDIRECT_REF we determine if we've already seen a same
1001 ref anywhere up to the root of the dominator tree. If we do the
1002 current access can't trap. If we don't see any dominating access
1003 the current access might trap, but might also make later accesses
1004 non-trapping, so we remember it. We need to be careful with loads
1005 or stores, for instance a load might not trap, while a store would,
1006 so if we see a dominating read access this doesn't mean that a later
1007 write access would not trap. Hence we also need to differentiate the
1008 type of access(es) seen.
1010 ??? We currently are very conservative and assume that a load might
1011 trap even if a store doesn't (write-only memory). This probably is
1012 overly conservative. */
1014 /* A hash-table of SSA_NAMEs, and in which basic block an INDIRECT_REF
1015 through it was seen, which would constitute a no-trap region for
1024 /* The hash table for remembering what we've seen. */
1025 static htab_t seen_ssa_names
;
1027 /* The set of INDIRECT_REFs which can't trap. */
1028 static struct pointer_set_t
*nontrap_set
;
1030 /* The hash function, based on the pointer to the pointer SSA_NAME. */
1032 name_to_bb_hash (const void *p
)
1034 const_tree n
= ((const struct name_to_bb
*)p
)->ssa_name
;
1035 return htab_hash_pointer (n
) ^ ((const struct name_to_bb
*)p
)->store
;
1038 /* The equality function of *P1 and *P2. SSA_NAMEs are shared, so
1039 it's enough to simply compare them for equality. */
1041 name_to_bb_eq (const void *p1
, const void *p2
)
1043 const struct name_to_bb
*n1
= (const struct name_to_bb
*)p1
;
1044 const struct name_to_bb
*n2
= (const struct name_to_bb
*)p2
;
1046 return n1
->ssa_name
== n2
->ssa_name
&& n1
->store
== n2
->store
;
1049 /* We see the expression EXP in basic block BB. If it's an interesting
1050 expression (an INDIRECT_REF through an SSA_NAME) possibly insert the
1051 expression into the set NONTRAP or the hash table of seen expressions.
1052 STORE is true if this expression is on the LHS, otherwise it's on
1055 add_or_mark_expr (basic_block bb
, tree exp
,
1056 struct pointer_set_t
*nontrap
, bool store
)
1058 if (INDIRECT_REF_P (exp
)
1059 && TREE_CODE (TREE_OPERAND (exp
, 0)) == SSA_NAME
)
1061 tree name
= TREE_OPERAND (exp
, 0);
1062 struct name_to_bb map
;
1064 struct name_to_bb
*n2bb
;
1065 basic_block found_bb
= 0;
1067 /* Try to find the last seen INDIRECT_REF through the same
1068 SSA_NAME, which can trap. */
1069 map
.ssa_name
= name
;
1072 slot
= htab_find_slot (seen_ssa_names
, &map
, INSERT
);
1073 n2bb
= (struct name_to_bb
*) *slot
;
1075 found_bb
= n2bb
->bb
;
1077 /* If we've found a trapping INDIRECT_REF, _and_ it dominates EXP
1078 (it's in a basic block on the path from us to the dominator root)
1079 then we can't trap. */
1080 if (found_bb
&& found_bb
->aux
== (void *)1)
1082 pointer_set_insert (nontrap
, exp
);
1086 /* EXP might trap, so insert it into the hash table. */
1093 n2bb
= XNEW (struct name_to_bb
);
1094 n2bb
->ssa_name
= name
;
1096 n2bb
->store
= store
;
1103 /* Called by walk_dominator_tree, when entering the block BB. */
1105 nt_init_block (struct dom_walk_data
*data ATTRIBUTE_UNUSED
, basic_block bb
)
1107 gimple_stmt_iterator gsi
;
1108 /* Mark this BB as being on the path to dominator root. */
1111 /* And walk the statements in order. */
1112 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1114 gimple stmt
= gsi_stmt (gsi
);
1116 if (is_gimple_assign (stmt
))
1118 add_or_mark_expr (bb
, gimple_assign_lhs (stmt
), nontrap_set
, true);
1119 add_or_mark_expr (bb
, gimple_assign_rhs1 (stmt
), nontrap_set
, false);
1120 if (get_gimple_rhs_num_ops (gimple_assign_rhs_code (stmt
)) > 1)
1121 add_or_mark_expr (bb
, gimple_assign_rhs2 (stmt
), nontrap_set
,
1127 /* Called by walk_dominator_tree, when basic block BB is exited. */
1129 nt_fini_block (struct dom_walk_data
*data ATTRIBUTE_UNUSED
, basic_block bb
)
1131 /* This BB isn't on the path to dominator root anymore. */
1135 /* This is the entry point of gathering non trapping memory accesses.
1136 It will do a dominator walk over the whole function, and it will
1137 make use of the bb->aux pointers. It returns a set of trees
1138 (the INDIRECT_REFs itself) which can't trap. */
1139 static struct pointer_set_t
*
1140 get_non_trapping (void)
1142 struct pointer_set_t
*nontrap
;
1143 struct dom_walk_data walk_data
;
1145 nontrap
= pointer_set_create ();
1146 seen_ssa_names
= htab_create (128, name_to_bb_hash
, name_to_bb_eq
,
1148 /* We're going to do a dominator walk, so ensure that we have
1149 dominance information. */
1150 calculate_dominance_info (CDI_DOMINATORS
);
1152 /* Setup callbacks for the generic dominator tree walker. */
1153 nontrap_set
= nontrap
;
1154 walk_data
.dom_direction
= CDI_DOMINATORS
;
1155 walk_data
.initialize_block_local_data
= NULL
;
1156 walk_data
.before_dom_children
= nt_init_block
;
1157 walk_data
.after_dom_children
= nt_fini_block
;
1158 walk_data
.global_data
= NULL
;
1159 walk_data
.block_local_data_size
= 0;
1161 init_walk_dominator_tree (&walk_data
);
1162 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1163 fini_walk_dominator_tree (&walk_data
);
1164 htab_delete (seen_ssa_names
);
1169 /* Do the main work of conditional store replacement. We already know
1170 that the recognized pattern looks like so:
1173 if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
1176 fallthrough (edge E0)
1180 We check that MIDDLE_BB contains only one store, that that store
1181 doesn't trap (not via NOTRAP, but via checking if an access to the same
1182 memory location dominates us) and that the store has a "simple" RHS. */
1185 cond_store_replacement (basic_block middle_bb
, basic_block join_bb
,
1186 edge e0
, edge e1
, struct pointer_set_t
*nontrap
)
1188 gimple assign
= last_and_only_stmt (middle_bb
);
1189 tree lhs
, rhs
, name
;
1190 gimple newphi
, new_stmt
;
1191 gimple_stmt_iterator gsi
;
1192 source_location locus
;
1193 enum tree_code code
;
1195 /* Check if middle_bb contains of only one store. */
1197 || gimple_code (assign
) != GIMPLE_ASSIGN
)
1200 locus
= gimple_location (assign
);
1201 lhs
= gimple_assign_lhs (assign
);
1202 rhs
= gimple_assign_rhs1 (assign
);
1203 if (!INDIRECT_REF_P (lhs
))
1206 /* RHS is either a single SSA_NAME or a constant. */
1207 code
= gimple_assign_rhs_code (assign
);
1208 if (get_gimple_rhs_class (code
) != GIMPLE_SINGLE_RHS
1209 || (code
!= SSA_NAME
&& !is_gimple_min_invariant (rhs
)))
1211 /* Prove that we can move the store down. We could also check
1212 TREE_THIS_NOTRAP here, but in that case we also could move stores,
1213 whose value is not available readily, which we want to avoid. */
1214 if (!pointer_set_contains (nontrap
, lhs
))
1217 /* Now we've checked the constraints, so do the transformation:
1218 1) Remove the single store. */
1219 mark_symbols_for_renaming (assign
);
1220 gsi
= gsi_for_stmt (assign
);
1221 gsi_remove (&gsi
, true);
1223 /* 2) Create a temporary where we can store the old content
1224 of the memory touched by the store, if we need to. */
1225 if (!condstoretemp
|| TREE_TYPE (lhs
) != TREE_TYPE (condstoretemp
))
1227 condstoretemp
= create_tmp_reg (TREE_TYPE (lhs
), "cstore");
1228 get_var_ann (condstoretemp
);
1230 add_referenced_var (condstoretemp
);
1232 /* 3) Insert a load from the memory of the store to the temporary
1233 on the edge which did not contain the store. */
1234 lhs
= unshare_expr (lhs
);
1235 new_stmt
= gimple_build_assign (condstoretemp
, lhs
);
1236 name
= make_ssa_name (condstoretemp
, new_stmt
);
1237 gimple_assign_set_lhs (new_stmt
, name
);
1238 gimple_set_location (new_stmt
, locus
);
1239 mark_symbols_for_renaming (new_stmt
);
1240 gsi_insert_on_edge (e1
, new_stmt
);
1242 /* 4) Create a PHI node at the join block, with one argument
1243 holding the old RHS, and the other holding the temporary
1244 where we stored the old memory contents. */
1245 newphi
= create_phi_node (condstoretemp
, join_bb
);
1246 add_phi_arg (newphi
, rhs
, e0
, locus
);
1247 add_phi_arg (newphi
, name
, e1
, locus
);
1249 lhs
= unshare_expr (lhs
);
1250 new_stmt
= gimple_build_assign (lhs
, PHI_RESULT (newphi
));
1251 mark_symbols_for_renaming (new_stmt
);
1253 /* 5) Insert that PHI node. */
1254 gsi
= gsi_after_labels (join_bb
);
1255 if (gsi_end_p (gsi
))
1257 gsi
= gsi_last_bb (join_bb
);
1258 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
1261 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
1266 /* Always do these optimizations if we have SSA
1267 trees to work on. */
1274 struct gimple_opt_pass pass_phiopt
=
1278 "phiopt", /* name */
1279 gate_phiopt
, /* gate */
1280 tree_ssa_phiopt
, /* execute */
1283 0, /* static_pass_number */
1284 TV_TREE_PHIOPT
, /* tv_id */
1285 PROP_cfg
| PROP_ssa
, /* properties_required */
1286 0, /* properties_provided */
1287 0, /* properties_destroyed */
1288 0, /* todo_flags_start */
1293 | TODO_verify_stmts
/* todo_flags_finish */
1300 return flag_tree_cselim
;
1303 struct gimple_opt_pass pass_cselim
=
1307 "cselim", /* name */
1308 gate_cselim
, /* gate */
1309 tree_ssa_cs_elim
, /* execute */
1312 0, /* static_pass_number */
1313 TV_TREE_PHIOPT
, /* tv_id */
1314 PROP_cfg
| PROP_ssa
, /* properties_required */
1315 0, /* properties_provided */
1316 0, /* properties_destroyed */
1317 0, /* todo_flags_start */
1322 | TODO_verify_stmts
/* todo_flags_finish */