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"
30 #include "basic-block.h"
32 #include "diagnostic.h"
33 #include "tree-flow.h"
34 #include "tree-pass.h"
35 #include "tree-dump.h"
36 #include "langhooks.h"
37 #include "pointer-set.h"
40 static unsigned int tree_ssa_phiopt (void);
41 static unsigned int tree_ssa_phiopt_worker (bool);
42 static bool conditional_replacement (basic_block
, basic_block
,
43 edge
, edge
, gimple
, tree
, tree
);
44 static bool value_replacement (basic_block
, basic_block
,
45 edge
, edge
, gimple
, tree
, tree
);
46 static bool minmax_replacement (basic_block
, basic_block
,
47 edge
, edge
, gimple
, tree
, tree
);
48 static bool abs_replacement (basic_block
, basic_block
,
49 edge
, edge
, gimple
, tree
, tree
);
50 static bool cond_store_replacement (basic_block
, basic_block
, edge
, edge
,
51 struct pointer_set_t
*);
52 static struct pointer_set_t
* get_non_trapping (void);
53 static void replace_phi_edge_with_variable (basic_block
, edge
, gimple
, tree
);
55 /* This pass tries to replaces an if-then-else block with an
56 assignment. We have four kinds of transformations. Some of these
57 transformations are also performed by the ifcvt RTL optimizer.
59 Conditional Replacement
60 -----------------------
62 This transformation, implemented in conditional_replacement,
66 if (cond) goto bb2; else goto bb1;
69 x = PHI <0 (bb1), 1 (bb0), ...>;
77 x = PHI <x' (bb0), ...>;
79 We remove bb1 as it becomes unreachable. This occurs often due to
80 gimplification of conditionals.
85 This transformation, implemented in value_replacement, replaces
88 if (a != b) goto bb2; else goto bb1;
91 x = PHI <a (bb1), b (bb0), ...>;
97 x = PHI <b (bb0), ...>;
99 This opportunity can sometimes occur as a result of other
105 This transformation, implemented in abs_replacement, replaces
108 if (a >= 0) goto bb2; else goto bb1;
112 x = PHI <x (bb1), a (bb0), ...>;
119 x = PHI <x' (bb0), ...>;
124 This transformation, minmax_replacement replaces
127 if (a <= b) goto bb2; else goto bb1;
130 x = PHI <b (bb1), a (bb0), ...>;
137 x = PHI <x' (bb0), ...>;
139 A similar transformation is done for MAX_EXPR. */
142 tree_ssa_phiopt (void)
144 return tree_ssa_phiopt_worker (false);
147 /* This pass tries to transform conditional stores into unconditional
148 ones, enabling further simplifications with the simpler then and else
149 blocks. In particular it replaces this:
152 if (cond) goto bb2; else goto bb1;
160 if (cond) goto bb1; else goto bb2;
164 condtmp = PHI <RHS, condtmp'>
167 This transformation can only be done under several constraints,
171 tree_ssa_cs_elim (void)
173 return tree_ssa_phiopt_worker (true);
176 /* For conditional store replacement we need a temporary to
177 put the old contents of the memory in. */
178 static tree condstoretemp
;
180 /* The core routine of conditional store replacement and normal
181 phi optimizations. Both share much of the infrastructure in how
182 to match applicable basic block patterns. DO_STORE_ELIM is true
183 when we want to do conditional store replacement, false otherwise. */
185 tree_ssa_phiopt_worker (bool do_store_elim
)
188 basic_block
*bb_order
;
190 bool cfgchanged
= false;
191 struct pointer_set_t
*nontrap
= 0;
195 condstoretemp
= NULL_TREE
;
196 /* Calculate the set of non-trapping memory accesses. */
197 nontrap
= get_non_trapping ();
200 /* Search every basic block for COND_EXPR we may be able to optimize.
202 We walk the blocks in order that guarantees that a block with
203 a single predecessor is processed before the predecessor.
204 This ensures that we collapse inner ifs before visiting the
205 outer ones, and also that we do not try to visit a removed
207 bb_order
= blocks_in_phiopt_order ();
208 n
= n_basic_blocks
- NUM_FIXED_BLOCKS
;
210 for (i
= 0; i
< n
; i
++)
212 gimple cond_stmt
, phi
;
213 basic_block bb1
, bb2
;
219 cond_stmt
= last_stmt (bb
);
220 /* Check to see if the last statement is a GIMPLE_COND. */
222 || gimple_code (cond_stmt
) != GIMPLE_COND
)
225 e1
= EDGE_SUCC (bb
, 0);
227 e2
= EDGE_SUCC (bb
, 1);
230 /* We cannot do the optimization on abnormal edges. */
231 if ((e1
->flags
& EDGE_ABNORMAL
) != 0
232 || (e2
->flags
& EDGE_ABNORMAL
) != 0)
235 /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
236 if (EDGE_COUNT (bb1
->succs
) == 0
238 || EDGE_COUNT (bb2
->succs
) == 0)
241 /* Find the bb which is the fall through to the other. */
242 if (EDGE_SUCC (bb1
, 0)->dest
== bb2
)
244 else if (EDGE_SUCC (bb2
, 0)->dest
== bb1
)
246 basic_block bb_tmp
= bb1
;
256 e1
= EDGE_SUCC (bb1
, 0);
258 /* Make sure that bb1 is just a fall through. */
259 if (!single_succ_p (bb1
)
260 || (e1
->flags
& EDGE_FALLTHRU
) == 0)
263 /* Also make sure that bb1 only have one predecessor and that it
265 if (!single_pred_p (bb1
)
266 || single_pred (bb1
) != bb
)
271 /* bb1 is the middle block, bb2 the join block, bb the split block,
272 e1 the fallthrough edge from bb1 to bb2. We can't do the
273 optimization if the join block has more than two predecessors. */
274 if (EDGE_COUNT (bb2
->preds
) > 2)
276 if (cond_store_replacement (bb1
, bb2
, e1
, e2
, nontrap
))
281 gimple_seq phis
= phi_nodes (bb2
);
283 /* Check to make sure that there is only one PHI node.
284 TODO: we could do it with more than one iff the other PHI nodes
285 have the same elements for these two edges. */
286 if (! gimple_seq_singleton_p (phis
))
289 phi
= gsi_stmt (gsi_start (phis
));
290 arg0
= gimple_phi_arg_def (phi
, e1
->dest_idx
);
291 arg1
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
293 /* Something is wrong if we cannot find the arguments in the PHI
295 gcc_assert (arg0
!= NULL
&& arg1
!= NULL
);
297 /* Do the replacement of conditional if it can be done. */
298 if (conditional_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
))
300 else if (value_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
))
302 else if (abs_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
))
304 else if (minmax_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
))
312 pointer_set_destroy (nontrap
);
313 /* If the CFG has changed, we should cleanup the CFG. */
314 if (cfgchanged
&& do_store_elim
)
316 /* In cond-store replacement we have added some loads on edges
317 and new VOPS (as we moved the store, and created a load). */
318 gsi_commit_edge_inserts ();
319 return TODO_cleanup_cfg
| TODO_update_ssa_only_virtuals
;
322 return TODO_cleanup_cfg
;
326 /* Returns the list of basic blocks in the function in an order that guarantees
327 that if a block X has just a single predecessor Y, then Y is after X in the
331 blocks_in_phiopt_order (void)
334 basic_block
*order
= XNEWVEC (basic_block
, n_basic_blocks
);
335 unsigned n
= n_basic_blocks
- NUM_FIXED_BLOCKS
;
337 sbitmap visited
= sbitmap_alloc (last_basic_block
);
339 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
340 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
342 sbitmap_zero (visited
);
344 MARK_VISITED (ENTRY_BLOCK_PTR
);
350 /* Walk the predecessors of x as long as they have precisely one
351 predecessor and add them to the list, so that they get stored
354 single_pred_p (y
) && !VISITED_P (single_pred (y
));
357 for (y
= x
, i
= n
- np
;
358 single_pred_p (y
) && !VISITED_P (single_pred (y
));
359 y
= single_pred (y
), i
++)
367 gcc_assert (i
== n
- 1);
371 sbitmap_free (visited
);
380 /* Return TRUE if block BB has no executable statements, otherwise return
384 empty_block_p (basic_block bb
)
386 /* BB must have no executable statements. */
387 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
390 if (is_gimple_debug (gsi_stmt (gsi
)))
391 gsi_next_nondebug (&gsi
);
392 return gsi_end_p (gsi
);
395 /* Replace PHI node element whose edge is E in block BB with variable NEW.
396 Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
397 is known to have two edges, one of which must reach BB). */
400 replace_phi_edge_with_variable (basic_block cond_block
,
401 edge e
, gimple phi
, tree new_tree
)
403 basic_block bb
= gimple_bb (phi
);
404 basic_block block_to_remove
;
405 gimple_stmt_iterator gsi
;
407 /* Change the PHI argument to new. */
408 SET_USE (PHI_ARG_DEF_PTR (phi
, e
->dest_idx
), new_tree
);
410 /* Remove the empty basic block. */
411 if (EDGE_SUCC (cond_block
, 0)->dest
== bb
)
413 EDGE_SUCC (cond_block
, 0)->flags
|= EDGE_FALLTHRU
;
414 EDGE_SUCC (cond_block
, 0)->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
415 EDGE_SUCC (cond_block
, 0)->probability
= REG_BR_PROB_BASE
;
416 EDGE_SUCC (cond_block
, 0)->count
+= EDGE_SUCC (cond_block
, 1)->count
;
418 block_to_remove
= EDGE_SUCC (cond_block
, 1)->dest
;
422 EDGE_SUCC (cond_block
, 1)->flags
|= EDGE_FALLTHRU
;
423 EDGE_SUCC (cond_block
, 1)->flags
424 &= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
425 EDGE_SUCC (cond_block
, 1)->probability
= REG_BR_PROB_BASE
;
426 EDGE_SUCC (cond_block
, 1)->count
+= EDGE_SUCC (cond_block
, 0)->count
;
428 block_to_remove
= EDGE_SUCC (cond_block
, 0)->dest
;
430 delete_basic_block (block_to_remove
);
432 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
433 gsi
= gsi_last_bb (cond_block
);
434 gsi_remove (&gsi
, true);
436 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
438 "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
443 /* The function conditional_replacement does the main work of doing the
444 conditional replacement. Return true if the replacement is done.
445 Otherwise return false.
446 BB is the basic block where the replacement is going to be done on. ARG0
447 is argument 0 from PHI. Likewise for ARG1. */
450 conditional_replacement (basic_block cond_bb
, basic_block middle_bb
,
451 edge e0
, edge e1
, gimple phi
,
452 tree arg0
, tree arg1
)
455 gimple stmt
, new_stmt
;
457 gimple_stmt_iterator gsi
;
458 edge true_edge
, false_edge
;
459 tree new_var
, new_var2
;
461 /* FIXME: Gimplification of complex type is too hard for now. */
462 if (TREE_CODE (TREE_TYPE (arg0
)) == COMPLEX_TYPE
463 || TREE_CODE (TREE_TYPE (arg1
)) == COMPLEX_TYPE
)
466 /* The PHI arguments have the constants 0 and 1, then convert
467 it to the conditional. */
468 if ((integer_zerop (arg0
) && integer_onep (arg1
))
469 || (integer_zerop (arg1
) && integer_onep (arg0
)))
474 if (!empty_block_p (middle_bb
))
477 /* At this point we know we have a GIMPLE_COND with two successors.
478 One successor is BB, the other successor is an empty block which
479 falls through into BB.
481 There is a single PHI node at the join point (BB) and its arguments
482 are constants (0, 1).
484 So, given the condition COND, and the two PHI arguments, we can
485 rewrite this PHI into non-branching code:
487 dest = (COND) or dest = COND'
489 We use the condition as-is if the argument associated with the
490 true edge has the value one or the argument associated with the
491 false edge as the value zero. Note that those conditions are not
492 the same since only one of the outgoing edges from the GIMPLE_COND
493 will directly reach BB and thus be associated with an argument. */
495 stmt
= last_stmt (cond_bb
);
496 result
= PHI_RESULT (phi
);
498 /* To handle special cases like floating point comparison, it is easier and
499 less error-prone to build a tree and gimplify it on the fly though it is
501 cond
= fold_build2 (gimple_cond_code (stmt
), boolean_type_node
,
502 gimple_cond_lhs (stmt
), gimple_cond_rhs (stmt
));
504 /* We need to know which is the true edge and which is the false
505 edge so that we know when to invert the condition below. */
506 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
507 if ((e0
== true_edge
&& integer_zerop (arg0
))
508 || (e0
== false_edge
&& integer_onep (arg0
))
509 || (e1
== true_edge
&& integer_zerop (arg1
))
510 || (e1
== false_edge
&& integer_onep (arg1
)))
511 cond
= fold_build1 (TRUTH_NOT_EXPR
, TREE_TYPE (cond
), cond
);
513 /* Insert our new statements at the end of conditional block before the
515 gsi
= gsi_for_stmt (stmt
);
516 new_var
= force_gimple_operand_gsi (&gsi
, cond
, true, NULL
, true,
519 if (!useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (new_var
)))
521 source_location locus_0
, locus_1
;
523 new_var2
= create_tmp_var (TREE_TYPE (result
), NULL
);
524 add_referenced_var (new_var2
);
525 new_stmt
= gimple_build_assign_with_ops (CONVERT_EXPR
, new_var2
,
527 new_var2
= make_ssa_name (new_var2
, new_stmt
);
528 gimple_assign_set_lhs (new_stmt
, new_var2
);
529 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
532 /* Set the locus to the first argument, unless is doesn't have one. */
533 locus_0
= gimple_phi_arg_location (phi
, 0);
534 locus_1
= gimple_phi_arg_location (phi
, 1);
535 if (locus_0
== UNKNOWN_LOCATION
)
537 gimple_set_location (new_stmt
, locus_0
);
540 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, new_var
);
542 /* Note that we optimized this PHI. */
546 /* The function value_replacement does the main work of doing the value
547 replacement. Return true if the replacement is done. Otherwise return
549 BB is the basic block where the replacement is going to be done on. ARG0
550 is argument 0 from the PHI. Likewise for ARG1. */
553 value_replacement (basic_block cond_bb
, basic_block middle_bb
,
554 edge e0
, edge e1
, gimple phi
,
555 tree arg0
, tree arg1
)
558 edge true_edge
, false_edge
;
561 /* If the type says honor signed zeros we cannot do this
563 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1
))))
566 if (!empty_block_p (middle_bb
))
569 cond
= last_stmt (cond_bb
);
570 code
= gimple_cond_code (cond
);
572 /* This transformation is only valid for equality comparisons. */
573 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
576 /* We need to know which is the true edge and which is the false
577 edge so that we know if have abs or negative abs. */
578 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
580 /* At this point we know we have a COND_EXPR with two successors.
581 One successor is BB, the other successor is an empty block which
582 falls through into BB.
584 The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
586 There is a single PHI node at the join point (BB) with two arguments.
588 We now need to verify that the two arguments in the PHI node match
589 the two arguments to the equality comparison. */
591 if ((operand_equal_for_phi_arg_p (arg0
, gimple_cond_lhs (cond
))
592 && operand_equal_for_phi_arg_p (arg1
, gimple_cond_rhs (cond
)))
593 || (operand_equal_for_phi_arg_p (arg1
, gimple_cond_lhs (cond
))
594 && operand_equal_for_phi_arg_p (arg0
, gimple_cond_rhs (cond
))))
599 /* For NE_EXPR, we want to build an assignment result = arg where
600 arg is the PHI argument associated with the true edge. For
601 EQ_EXPR we want the PHI argument associated with the false edge. */
602 e
= (code
== NE_EXPR
? true_edge
: false_edge
);
604 /* Unfortunately, E may not reach BB (it may instead have gone to
605 OTHER_BLOCK). If that is the case, then we want the single outgoing
606 edge from OTHER_BLOCK which reaches BB and represents the desired
607 path from COND_BLOCK. */
608 if (e
->dest
== middle_bb
)
609 e
= single_succ_edge (e
->dest
);
611 /* Now we know the incoming edge to BB that has the argument for the
612 RHS of our new assignment statement. */
618 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, arg
);
620 /* Note that we optimized this PHI. */
626 /* The function minmax_replacement does the main work of doing the minmax
627 replacement. Return true if the replacement is done. Otherwise return
629 BB is the basic block where the replacement is going to be done on. ARG0
630 is argument 0 from the PHI. Likewise for ARG1. */
633 minmax_replacement (basic_block cond_bb
, basic_block middle_bb
,
634 edge e0
, edge e1
, gimple phi
,
635 tree arg0
, tree arg1
)
638 gimple cond
, new_stmt
;
639 edge true_edge
, false_edge
;
640 enum tree_code cmp
, minmax
, ass_code
;
641 tree smaller
, larger
, arg_true
, arg_false
;
642 gimple_stmt_iterator gsi
, gsi_from
;
644 type
= TREE_TYPE (PHI_RESULT (phi
));
646 /* The optimization may be unsafe due to NaNs. */
647 if (HONOR_NANS (TYPE_MODE (type
)))
650 cond
= last_stmt (cond_bb
);
651 cmp
= gimple_cond_code (cond
);
652 result
= PHI_RESULT (phi
);
654 /* This transformation is only valid for order comparisons. Record which
655 operand is smaller/larger if the result of the comparison is true. */
656 if (cmp
== LT_EXPR
|| cmp
== LE_EXPR
)
658 smaller
= gimple_cond_lhs (cond
);
659 larger
= gimple_cond_rhs (cond
);
661 else if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
663 smaller
= gimple_cond_rhs (cond
);
664 larger
= gimple_cond_lhs (cond
);
669 /* We need to know which is the true edge and which is the false
670 edge so that we know if have abs or negative abs. */
671 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
673 /* Forward the edges over the middle basic block. */
674 if (true_edge
->dest
== middle_bb
)
675 true_edge
= EDGE_SUCC (true_edge
->dest
, 0);
676 if (false_edge
->dest
== middle_bb
)
677 false_edge
= EDGE_SUCC (false_edge
->dest
, 0);
681 gcc_assert (false_edge
== e1
);
687 gcc_assert (false_edge
== e0
);
688 gcc_assert (true_edge
== e1
);
693 if (empty_block_p (middle_bb
))
695 if (operand_equal_for_phi_arg_p (arg_true
, smaller
)
696 && operand_equal_for_phi_arg_p (arg_false
, larger
))
700 if (smaller < larger)
706 else if (operand_equal_for_phi_arg_p (arg_false
, smaller
)
707 && operand_equal_for_phi_arg_p (arg_true
, larger
))
714 /* Recognize the following case, assuming d <= u:
720 This is equivalent to
725 gimple assign
= last_and_only_stmt (middle_bb
);
726 tree lhs
, op0
, op1
, bound
;
729 || gimple_code (assign
) != GIMPLE_ASSIGN
)
732 lhs
= gimple_assign_lhs (assign
);
733 ass_code
= gimple_assign_rhs_code (assign
);
734 if (ass_code
!= MAX_EXPR
&& ass_code
!= MIN_EXPR
)
736 op0
= gimple_assign_rhs1 (assign
);
737 op1
= gimple_assign_rhs2 (assign
);
739 if (true_edge
->src
== middle_bb
)
741 /* We got here if the condition is true, i.e., SMALLER < LARGER. */
742 if (!operand_equal_for_phi_arg_p (lhs
, arg_true
))
745 if (operand_equal_for_phi_arg_p (arg_false
, larger
))
749 if (smaller < larger)
751 r' = MAX_EXPR (smaller, bound)
753 r = PHI <r', larger> --> to be turned to MIN_EXPR. */
754 if (ass_code
!= MAX_EXPR
)
758 if (operand_equal_for_phi_arg_p (op0
, smaller
))
760 else if (operand_equal_for_phi_arg_p (op1
, smaller
))
765 /* We need BOUND <= LARGER. */
766 if (!integer_nonzerop (fold_build2 (LE_EXPR
, boolean_type_node
,
770 else if (operand_equal_for_phi_arg_p (arg_false
, smaller
))
774 if (smaller < larger)
776 r' = MIN_EXPR (larger, bound)
778 r = PHI <r', smaller> --> to be turned to MAX_EXPR. */
779 if (ass_code
!= MIN_EXPR
)
783 if (operand_equal_for_phi_arg_p (op0
, larger
))
785 else if (operand_equal_for_phi_arg_p (op1
, larger
))
790 /* We need BOUND >= SMALLER. */
791 if (!integer_nonzerop (fold_build2 (GE_EXPR
, boolean_type_node
,
800 /* We got here if the condition is false, i.e., SMALLER > LARGER. */
801 if (!operand_equal_for_phi_arg_p (lhs
, arg_false
))
804 if (operand_equal_for_phi_arg_p (arg_true
, larger
))
808 if (smaller > larger)
810 r' = MIN_EXPR (smaller, bound)
812 r = PHI <r', larger> --> to be turned to MAX_EXPR. */
813 if (ass_code
!= MIN_EXPR
)
817 if (operand_equal_for_phi_arg_p (op0
, smaller
))
819 else if (operand_equal_for_phi_arg_p (op1
, smaller
))
824 /* We need BOUND >= LARGER. */
825 if (!integer_nonzerop (fold_build2 (GE_EXPR
, boolean_type_node
,
829 else if (operand_equal_for_phi_arg_p (arg_true
, smaller
))
833 if (smaller > larger)
835 r' = MAX_EXPR (larger, bound)
837 r = PHI <r', smaller> --> to be turned to MIN_EXPR. */
838 if (ass_code
!= MAX_EXPR
)
842 if (operand_equal_for_phi_arg_p (op0
, larger
))
844 else if (operand_equal_for_phi_arg_p (op1
, larger
))
849 /* We need BOUND <= SMALLER. */
850 if (!integer_nonzerop (fold_build2 (LE_EXPR
, boolean_type_node
,
858 /* Move the statement from the middle block. */
859 gsi
= gsi_last_bb (cond_bb
);
860 gsi_from
= gsi_last_nondebug_bb (middle_bb
);
861 gsi_move_before (&gsi_from
, &gsi
);
864 /* Emit the statement to compute min/max. */
865 result
= duplicate_ssa_name (PHI_RESULT (phi
), NULL
);
866 new_stmt
= gimple_build_assign_with_ops (minmax
, result
, arg0
, arg1
);
867 gsi
= gsi_last_bb (cond_bb
);
868 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
870 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, result
);
874 /* The function absolute_replacement does the main work of doing the absolute
875 replacement. Return true if the replacement is done. Otherwise return
877 bb is the basic block where the replacement is going to be done on. arg0
878 is argument 0 from the phi. Likewise for arg1. */
881 abs_replacement (basic_block cond_bb
, basic_block middle_bb
,
882 edge e0 ATTRIBUTE_UNUSED
, edge e1
,
883 gimple phi
, tree arg0
, tree arg1
)
886 gimple new_stmt
, cond
;
887 gimple_stmt_iterator gsi
;
888 edge true_edge
, false_edge
;
893 enum tree_code cond_code
;
895 /* If the type says honor signed zeros we cannot do this
897 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1
))))
900 /* OTHER_BLOCK must have only one executable statement which must have the
901 form arg0 = -arg1 or arg1 = -arg0. */
903 assign
= last_and_only_stmt (middle_bb
);
904 /* If we did not find the proper negation assignment, then we can not
909 /* If we got here, then we have found the only executable statement
910 in OTHER_BLOCK. If it is anything other than arg = -arg1 or
911 arg1 = -arg0, then we can not optimize. */
912 if (gimple_code (assign
) != GIMPLE_ASSIGN
)
915 lhs
= gimple_assign_lhs (assign
);
917 if (gimple_assign_rhs_code (assign
) != NEGATE_EXPR
)
920 rhs
= gimple_assign_rhs1 (assign
);
922 /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */
923 if (!(lhs
== arg0
&& rhs
== arg1
)
924 && !(lhs
== arg1
&& rhs
== arg0
))
927 cond
= last_stmt (cond_bb
);
928 result
= PHI_RESULT (phi
);
930 /* Only relationals comparing arg[01] against zero are interesting. */
931 cond_code
= gimple_cond_code (cond
);
932 if (cond_code
!= GT_EXPR
&& cond_code
!= GE_EXPR
933 && cond_code
!= LT_EXPR
&& cond_code
!= LE_EXPR
)
936 /* Make sure the conditional is arg[01] OP y. */
937 if (gimple_cond_lhs (cond
) != rhs
)
940 if (FLOAT_TYPE_P (TREE_TYPE (gimple_cond_rhs (cond
)))
941 ? real_zerop (gimple_cond_rhs (cond
))
942 : integer_zerop (gimple_cond_rhs (cond
)))
947 /* We need to know which is the true edge and which is the false
948 edge so that we know if have abs or negative abs. */
949 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
951 /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
952 will need to negate the result. Similarly for LT_EXPR/LE_EXPR if
953 the false edge goes to OTHER_BLOCK. */
954 if (cond_code
== GT_EXPR
|| cond_code
== GE_EXPR
)
959 if (e
->dest
== middle_bb
)
964 result
= duplicate_ssa_name (result
, NULL
);
968 tree tmp
= create_tmp_var (TREE_TYPE (result
), NULL
);
969 add_referenced_var (tmp
);
970 lhs
= make_ssa_name (tmp
, NULL
);
975 /* Build the modify expression with abs expression. */
976 new_stmt
= gimple_build_assign_with_ops (ABS_EXPR
, lhs
, rhs
, NULL
);
978 gsi
= gsi_last_bb (cond_bb
);
979 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
983 /* Get the right GSI. We want to insert after the recently
984 added ABS_EXPR statement (which we know is the first statement
986 new_stmt
= gimple_build_assign_with_ops (NEGATE_EXPR
, result
, lhs
, NULL
);
988 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
991 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, result
);
993 /* Note that we optimized this PHI. */
997 /* Auxiliary functions to determine the set of memory accesses which
998 can't trap because they are preceded by accesses to the same memory
999 portion. We do that for INDIRECT_REFs, so we only need to track
1000 the SSA_NAME of the pointer indirectly referenced. The algorithm
1001 simply is a walk over all instructions in dominator order. When
1002 we see an INDIRECT_REF we determine if we've already seen a same
1003 ref anywhere up to the root of the dominator tree. If we do the
1004 current access can't trap. If we don't see any dominating access
1005 the current access might trap, but might also make later accesses
1006 non-trapping, so we remember it. We need to be careful with loads
1007 or stores, for instance a load might not trap, while a store would,
1008 so if we see a dominating read access this doesn't mean that a later
1009 write access would not trap. Hence we also need to differentiate the
1010 type of access(es) seen.
1012 ??? We currently are very conservative and assume that a load might
1013 trap even if a store doesn't (write-only memory). This probably is
1014 overly conservative. */
1016 /* A hash-table of SSA_NAMEs, and in which basic block an INDIRECT_REF
1017 through it was seen, which would constitute a no-trap region for
1026 /* The hash table for remembering what we've seen. */
1027 static htab_t seen_ssa_names
;
1029 /* The set of INDIRECT_REFs which can't trap. */
1030 static struct pointer_set_t
*nontrap_set
;
1032 /* The hash function, based on the pointer to the pointer SSA_NAME. */
1034 name_to_bb_hash (const void *p
)
1036 const_tree n
= ((const struct name_to_bb
*)p
)->ssa_name
;
1037 return htab_hash_pointer (n
) ^ ((const struct name_to_bb
*)p
)->store
;
1040 /* The equality function of *P1 and *P2. SSA_NAMEs are shared, so
1041 it's enough to simply compare them for equality. */
1043 name_to_bb_eq (const void *p1
, const void *p2
)
1045 const struct name_to_bb
*n1
= (const struct name_to_bb
*)p1
;
1046 const struct name_to_bb
*n2
= (const struct name_to_bb
*)p2
;
1048 return n1
->ssa_name
== n2
->ssa_name
&& n1
->store
== n2
->store
;
1051 /* We see the expression EXP in basic block BB. If it's an interesting
1052 expression (an INDIRECT_REF through an SSA_NAME) possibly insert the
1053 expression into the set NONTRAP or the hash table of seen expressions.
1054 STORE is true if this expression is on the LHS, otherwise it's on
1057 add_or_mark_expr (basic_block bb
, tree exp
,
1058 struct pointer_set_t
*nontrap
, bool store
)
1060 if (INDIRECT_REF_P (exp
)
1061 && TREE_CODE (TREE_OPERAND (exp
, 0)) == SSA_NAME
)
1063 tree name
= TREE_OPERAND (exp
, 0);
1064 struct name_to_bb map
;
1066 struct name_to_bb
*n2bb
;
1067 basic_block found_bb
= 0;
1069 /* Try to find the last seen INDIRECT_REF through the same
1070 SSA_NAME, which can trap. */
1071 map
.ssa_name
= name
;
1074 slot
= htab_find_slot (seen_ssa_names
, &map
, INSERT
);
1075 n2bb
= (struct name_to_bb
*) *slot
;
1077 found_bb
= n2bb
->bb
;
1079 /* If we've found a trapping INDIRECT_REF, _and_ it dominates EXP
1080 (it's in a basic block on the path from us to the dominator root)
1081 then we can't trap. */
1082 if (found_bb
&& found_bb
->aux
== (void *)1)
1084 pointer_set_insert (nontrap
, exp
);
1088 /* EXP might trap, so insert it into the hash table. */
1095 n2bb
= XNEW (struct name_to_bb
);
1096 n2bb
->ssa_name
= name
;
1098 n2bb
->store
= store
;
1105 /* Called by walk_dominator_tree, when entering the block BB. */
1107 nt_init_block (struct dom_walk_data
*data ATTRIBUTE_UNUSED
, basic_block bb
)
1109 gimple_stmt_iterator gsi
;
1110 /* Mark this BB as being on the path to dominator root. */
1113 /* And walk the statements in order. */
1114 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1116 gimple stmt
= gsi_stmt (gsi
);
1118 if (is_gimple_assign (stmt
))
1120 add_or_mark_expr (bb
, gimple_assign_lhs (stmt
), nontrap_set
, true);
1121 add_or_mark_expr (bb
, gimple_assign_rhs1 (stmt
), nontrap_set
, false);
1122 if (get_gimple_rhs_num_ops (gimple_assign_rhs_code (stmt
)) > 1)
1123 add_or_mark_expr (bb
, gimple_assign_rhs2 (stmt
), nontrap_set
,
1129 /* Called by walk_dominator_tree, when basic block BB is exited. */
1131 nt_fini_block (struct dom_walk_data
*data ATTRIBUTE_UNUSED
, basic_block bb
)
1133 /* This BB isn't on the path to dominator root anymore. */
1137 /* This is the entry point of gathering non trapping memory accesses.
1138 It will do a dominator walk over the whole function, and it will
1139 make use of the bb->aux pointers. It returns a set of trees
1140 (the INDIRECT_REFs itself) which can't trap. */
1141 static struct pointer_set_t
*
1142 get_non_trapping (void)
1144 struct pointer_set_t
*nontrap
;
1145 struct dom_walk_data walk_data
;
1147 nontrap
= pointer_set_create ();
1148 seen_ssa_names
= htab_create (128, name_to_bb_hash
, name_to_bb_eq
,
1150 /* We're going to do a dominator walk, so ensure that we have
1151 dominance information. */
1152 calculate_dominance_info (CDI_DOMINATORS
);
1154 /* Setup callbacks for the generic dominator tree walker. */
1155 nontrap_set
= nontrap
;
1156 walk_data
.dom_direction
= CDI_DOMINATORS
;
1157 walk_data
.initialize_block_local_data
= NULL
;
1158 walk_data
.before_dom_children
= nt_init_block
;
1159 walk_data
.after_dom_children
= nt_fini_block
;
1160 walk_data
.global_data
= NULL
;
1161 walk_data
.block_local_data_size
= 0;
1163 init_walk_dominator_tree (&walk_data
);
1164 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1165 fini_walk_dominator_tree (&walk_data
);
1166 htab_delete (seen_ssa_names
);
1171 /* Do the main work of conditional store replacement. We already know
1172 that the recognized pattern looks like so:
1175 if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
1178 fallthrough (edge E0)
1182 We check that MIDDLE_BB contains only one store, that that store
1183 doesn't trap (not via NOTRAP, but via checking if an access to the same
1184 memory location dominates us) and that the store has a "simple" RHS. */
1187 cond_store_replacement (basic_block middle_bb
, basic_block join_bb
,
1188 edge e0
, edge e1
, struct pointer_set_t
*nontrap
)
1190 gimple assign
= last_and_only_stmt (middle_bb
);
1191 tree lhs
, rhs
, name
;
1192 gimple newphi
, new_stmt
;
1193 gimple_stmt_iterator gsi
;
1194 source_location locus
;
1195 enum tree_code code
;
1197 /* Check if middle_bb contains of only one store. */
1199 || gimple_code (assign
) != GIMPLE_ASSIGN
)
1202 locus
= gimple_location (assign
);
1203 lhs
= gimple_assign_lhs (assign
);
1204 rhs
= gimple_assign_rhs1 (assign
);
1205 if (!INDIRECT_REF_P (lhs
))
1208 /* RHS is either a single SSA_NAME or a constant. */
1209 code
= gimple_assign_rhs_code (assign
);
1210 if (get_gimple_rhs_class (code
) != GIMPLE_SINGLE_RHS
1211 || (code
!= SSA_NAME
&& !is_gimple_min_invariant (rhs
)))
1213 /* Prove that we can move the store down. We could also check
1214 TREE_THIS_NOTRAP here, but in that case we also could move stores,
1215 whose value is not available readily, which we want to avoid. */
1216 if (!pointer_set_contains (nontrap
, lhs
))
1219 /* Now we've checked the constraints, so do the transformation:
1220 1) Remove the single store. */
1221 mark_symbols_for_renaming (assign
);
1222 gsi
= gsi_for_stmt (assign
);
1223 gsi_remove (&gsi
, true);
1225 /* 2) Create a temporary where we can store the old content
1226 of the memory touched by the store, if we need to. */
1227 if (!condstoretemp
|| TREE_TYPE (lhs
) != TREE_TYPE (condstoretemp
))
1229 condstoretemp
= create_tmp_var (TREE_TYPE (lhs
), "cstore");
1230 get_var_ann (condstoretemp
);
1231 if (TREE_CODE (TREE_TYPE (lhs
)) == COMPLEX_TYPE
1232 || TREE_CODE (TREE_TYPE (lhs
)) == VECTOR_TYPE
)
1233 DECL_GIMPLE_REG_P (condstoretemp
) = 1;
1235 add_referenced_var (condstoretemp
);
1237 /* 3) Insert a load from the memory of the store to the temporary
1238 on the edge which did not contain the store. */
1239 lhs
= unshare_expr (lhs
);
1240 new_stmt
= gimple_build_assign (condstoretemp
, lhs
);
1241 name
= make_ssa_name (condstoretemp
, new_stmt
);
1242 gimple_assign_set_lhs (new_stmt
, name
);
1243 gimple_set_location (new_stmt
, locus
);
1244 mark_symbols_for_renaming (new_stmt
);
1245 gsi_insert_on_edge (e1
, new_stmt
);
1247 /* 4) Create a PHI node at the join block, with one argument
1248 holding the old RHS, and the other holding the temporary
1249 where we stored the old memory contents. */
1250 newphi
= create_phi_node (condstoretemp
, join_bb
);
1251 add_phi_arg (newphi
, rhs
, e0
, locus
);
1252 add_phi_arg (newphi
, name
, e1
, locus
);
1254 lhs
= unshare_expr (lhs
);
1255 new_stmt
= gimple_build_assign (lhs
, PHI_RESULT (newphi
));
1256 mark_symbols_for_renaming (new_stmt
);
1258 /* 5) Insert that PHI node. */
1259 gsi
= gsi_after_labels (join_bb
);
1260 if (gsi_end_p (gsi
))
1262 gsi
= gsi_last_bb (join_bb
);
1263 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
1266 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
1271 /* Always do these optimizations if we have SSA
1272 trees to work on. */
1279 struct gimple_opt_pass pass_phiopt
=
1283 "phiopt", /* name */
1284 gate_phiopt
, /* gate */
1285 tree_ssa_phiopt
, /* execute */
1288 0, /* static_pass_number */
1289 TV_TREE_PHIOPT
, /* tv_id */
1290 PROP_cfg
| PROP_ssa
, /* properties_required */
1291 0, /* properties_provided */
1292 0, /* properties_destroyed */
1293 0, /* todo_flags_start */
1298 | TODO_verify_stmts
/* todo_flags_finish */
1305 return flag_tree_cselim
;
1308 struct gimple_opt_pass pass_cselim
=
1312 "cselim", /* name */
1313 gate_cselim
, /* gate */
1314 tree_ssa_cs_elim
, /* execute */
1317 0, /* static_pass_number */
1318 TV_TREE_PHIOPT
, /* tv_id */
1319 PROP_cfg
| PROP_ssa
, /* properties_required */
1320 0, /* properties_provided */
1321 0, /* properties_destroyed */
1322 0, /* todo_flags_start */
1327 | TODO_verify_stmts
/* todo_flags_finish */