1 /* Optimization of PHI nodes by converting them into straightline code.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
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"
30 #include "tree-flow.h"
31 #include "tree-pass.h"
32 #include "langhooks.h"
33 #include "pointer-set.h"
36 #include "tree-data-ref.h"
37 #include "gimple-pretty-print.h"
38 #include "insn-config.h"
42 #ifndef HAVE_conditional_move
43 #define HAVE_conditional_move (0)
46 static unsigned int tree_ssa_phiopt (void);
47 static unsigned int tree_ssa_phiopt_worker (bool, bool);
48 static bool conditional_replacement (basic_block
, basic_block
,
49 edge
, edge
, gimple
, tree
, tree
);
50 static int value_replacement (basic_block
, basic_block
,
51 edge
, edge
, gimple
, tree
, tree
);
52 static bool minmax_replacement (basic_block
, basic_block
,
53 edge
, edge
, gimple
, tree
, tree
);
54 static bool abs_replacement (basic_block
, basic_block
,
55 edge
, edge
, gimple
, tree
, tree
);
56 static bool cond_store_replacement (basic_block
, basic_block
, edge
, edge
,
57 struct pointer_set_t
*);
58 static bool cond_if_else_store_replacement (basic_block
, basic_block
, basic_block
);
59 static struct pointer_set_t
* get_non_trapping (void);
60 static void replace_phi_edge_with_variable (basic_block
, edge
, gimple
, tree
);
61 static void hoist_adjacent_loads (basic_block
, basic_block
,
62 basic_block
, basic_block
);
63 static bool gate_hoist_loads (void);
65 /* This pass tries to replaces an if-then-else block with an
66 assignment. We have four kinds of transformations. Some of these
67 transformations are also performed by the ifcvt RTL optimizer.
69 Conditional Replacement
70 -----------------------
72 This transformation, implemented in conditional_replacement,
76 if (cond) goto bb2; else goto bb1;
79 x = PHI <0 (bb1), 1 (bb0), ...>;
87 x = PHI <x' (bb0), ...>;
89 We remove bb1 as it becomes unreachable. This occurs often due to
90 gimplification of conditionals.
95 This transformation, implemented in value_replacement, replaces
98 if (a != b) goto bb2; else goto bb1;
101 x = PHI <a (bb1), b (bb0), ...>;
107 x = PHI <b (bb0), ...>;
109 This opportunity can sometimes occur as a result of other
115 This transformation, implemented in abs_replacement, replaces
118 if (a >= 0) goto bb2; else goto bb1;
122 x = PHI <x (bb1), a (bb0), ...>;
129 x = PHI <x' (bb0), ...>;
134 This transformation, minmax_replacement replaces
137 if (a <= b) goto bb2; else goto bb1;
140 x = PHI <b (bb1), a (bb0), ...>;
147 x = PHI <x' (bb0), ...>;
149 A similar transformation is done for MAX_EXPR.
152 This pass also performs a fifth transformation of a slightly different
155 Adjacent Load Hoisting
156 ----------------------
158 This transformation replaces
161 if (...) goto bb2; else goto bb1;
163 x1 = (<expr>).field1;
166 x2 = (<expr>).field2;
173 x1 = (<expr>).field1;
174 x2 = (<expr>).field2;
175 if (...) goto bb2; else goto bb1;
182 The purpose of this transformation is to enable generation of conditional
183 move instructions such as Intel CMOVE or PowerPC ISEL. Because one of
184 the loads is speculative, the transformation is restricted to very
185 specific cases to avoid introducing a page fault. We are looking for
193 where left and right are typically adjacent pointers in a tree structure. */
196 tree_ssa_phiopt (void)
198 return tree_ssa_phiopt_worker (false, gate_hoist_loads ());
201 /* This pass tries to transform conditional stores into unconditional
202 ones, enabling further simplifications with the simpler then and else
203 blocks. In particular it replaces this:
206 if (cond) goto bb2; else goto bb1;
214 if (cond) goto bb1; else goto bb2;
218 condtmp = PHI <RHS, condtmp'>
221 This transformation can only be done under several constraints,
222 documented below. It also replaces:
225 if (cond) goto bb2; else goto bb1;
236 if (cond) goto bb3; else goto bb1;
239 condtmp = PHI <RHS1, RHS2>
243 tree_ssa_cs_elim (void)
245 return tree_ssa_phiopt_worker (true, false);
248 /* Return the singleton PHI in the SEQ of PHIs for edges E0 and E1. */
251 single_non_singleton_phi_for_edges (gimple_seq seq
, edge e0
, edge e1
)
253 gimple_stmt_iterator i
;
255 if (gimple_seq_singleton_p (seq
))
256 return gsi_stmt (gsi_start (seq
));
257 for (i
= gsi_start (seq
); !gsi_end_p (i
); gsi_next (&i
))
259 gimple p
= gsi_stmt (i
);
260 /* If the PHI arguments are equal then we can skip this PHI. */
261 if (operand_equal_for_phi_arg_p (gimple_phi_arg_def (p
, e0
->dest_idx
),
262 gimple_phi_arg_def (p
, e1
->dest_idx
)))
265 /* If we already have a PHI that has the two edge arguments are
266 different, then return it is not a singleton for these PHIs. */
275 /* For conditional store replacement we need a temporary to
276 put the old contents of the memory in. */
277 static tree condstoretemp
;
279 /* The core routine of conditional store replacement and normal
280 phi optimizations. Both share much of the infrastructure in how
281 to match applicable basic block patterns. DO_STORE_ELIM is true
282 when we want to do conditional store replacement, false otherwise.
283 DO_HOIST_LOADS is true when we want to hoist adjacent loads out
284 of diamond control flow patterns, false otherwise. */
286 tree_ssa_phiopt_worker (bool do_store_elim
, bool do_hoist_loads
)
289 basic_block
*bb_order
;
291 bool cfgchanged
= false;
292 struct pointer_set_t
*nontrap
= 0;
296 condstoretemp
= NULL_TREE
;
297 /* Calculate the set of non-trapping memory accesses. */
298 nontrap
= get_non_trapping ();
301 /* Search every basic block for COND_EXPR we may be able to optimize.
303 We walk the blocks in order that guarantees that a block with
304 a single predecessor is processed before the predecessor.
305 This ensures that we collapse inner ifs before visiting the
306 outer ones, and also that we do not try to visit a removed
308 bb_order
= blocks_in_phiopt_order ();
309 n
= n_basic_blocks
- NUM_FIXED_BLOCKS
;
311 for (i
= 0; i
< n
; i
++)
313 gimple cond_stmt
, phi
;
314 basic_block bb1
, bb2
;
320 cond_stmt
= last_stmt (bb
);
321 /* Check to see if the last statement is a GIMPLE_COND. */
323 || gimple_code (cond_stmt
) != GIMPLE_COND
)
326 e1
= EDGE_SUCC (bb
, 0);
328 e2
= EDGE_SUCC (bb
, 1);
331 /* We cannot do the optimization on abnormal edges. */
332 if ((e1
->flags
& EDGE_ABNORMAL
) != 0
333 || (e2
->flags
& EDGE_ABNORMAL
) != 0)
336 /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
337 if (EDGE_COUNT (bb1
->succs
) == 0
339 || EDGE_COUNT (bb2
->succs
) == 0)
342 /* Find the bb which is the fall through to the other. */
343 if (EDGE_SUCC (bb1
, 0)->dest
== bb2
)
345 else if (EDGE_SUCC (bb2
, 0)->dest
== bb1
)
347 basic_block bb_tmp
= bb1
;
354 else if (do_store_elim
355 && EDGE_SUCC (bb1
, 0)->dest
== EDGE_SUCC (bb2
, 0)->dest
)
357 basic_block bb3
= EDGE_SUCC (bb1
, 0)->dest
;
359 if (!single_succ_p (bb1
)
360 || (EDGE_SUCC (bb1
, 0)->flags
& EDGE_FALLTHRU
) == 0
361 || !single_succ_p (bb2
)
362 || (EDGE_SUCC (bb2
, 0)->flags
& EDGE_FALLTHRU
) == 0
363 || EDGE_COUNT (bb3
->preds
) != 2)
365 if (cond_if_else_store_replacement (bb1
, bb2
, bb3
))
369 else if (do_hoist_loads
370 && EDGE_SUCC (bb1
, 0)->dest
== EDGE_SUCC (bb2
, 0)->dest
)
372 basic_block bb3
= EDGE_SUCC (bb1
, 0)->dest
;
374 if (!FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt
)))
375 && single_succ_p (bb1
)
376 && single_succ_p (bb2
)
377 && single_pred_p (bb1
)
378 && single_pred_p (bb2
)
379 && EDGE_COUNT (bb
->succs
) == 2
380 && EDGE_COUNT (bb3
->preds
) == 2
381 /* If one edge or the other is dominant, a conditional move
382 is likely to perform worse than the well-predicted branch. */
383 && !predictable_edge_p (EDGE_SUCC (bb
, 0))
384 && !predictable_edge_p (EDGE_SUCC (bb
, 1)))
385 hoist_adjacent_loads (bb
, bb1
, bb2
, bb3
);
391 e1
= EDGE_SUCC (bb1
, 0);
393 /* Make sure that bb1 is just a fall through. */
394 if (!single_succ_p (bb1
)
395 || (e1
->flags
& EDGE_FALLTHRU
) == 0)
398 /* Also make sure that bb1 only have one predecessor and that it
400 if (!single_pred_p (bb1
)
401 || single_pred (bb1
) != bb
)
406 /* bb1 is the middle block, bb2 the join block, bb the split block,
407 e1 the fallthrough edge from bb1 to bb2. We can't do the
408 optimization if the join block has more than two predecessors. */
409 if (EDGE_COUNT (bb2
->preds
) > 2)
411 if (cond_store_replacement (bb1
, bb2
, e1
, e2
, nontrap
))
416 gimple_seq phis
= phi_nodes (bb2
);
417 gimple_stmt_iterator gsi
;
418 bool candorest
= true;
420 /* Value replacement can work with more than one PHI
421 so try that first. */
422 for (gsi
= gsi_start (phis
); !gsi_end_p (gsi
); gsi_next (&gsi
))
424 phi
= gsi_stmt (gsi
);
425 arg0
= gimple_phi_arg_def (phi
, e1
->dest_idx
);
426 arg1
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
427 if (value_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
) == 2)
438 phi
= single_non_singleton_phi_for_edges (phis
, e1
, e2
);
442 arg0
= gimple_phi_arg_def (phi
, e1
->dest_idx
);
443 arg1
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
445 /* Something is wrong if we cannot find the arguments in the PHI
447 gcc_assert (arg0
!= NULL
&& arg1
!= NULL
);
449 /* Do the replacement of conditional if it can be done. */
450 if (conditional_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
))
452 else if (abs_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
))
454 else if (minmax_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
))
462 pointer_set_destroy (nontrap
);
463 /* If the CFG has changed, we should cleanup the CFG. */
464 if (cfgchanged
&& do_store_elim
)
466 /* In cond-store replacement we have added some loads on edges
467 and new VOPS (as we moved the store, and created a load). */
468 gsi_commit_edge_inserts ();
469 return TODO_cleanup_cfg
| TODO_update_ssa_only_virtuals
;
472 return TODO_cleanup_cfg
;
476 /* Returns the list of basic blocks in the function in an order that guarantees
477 that if a block X has just a single predecessor Y, then Y is after X in the
481 blocks_in_phiopt_order (void)
484 basic_block
*order
= XNEWVEC (basic_block
, n_basic_blocks
);
485 unsigned n
= n_basic_blocks
- NUM_FIXED_BLOCKS
;
487 sbitmap visited
= sbitmap_alloc (last_basic_block
);
489 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
490 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
492 sbitmap_zero (visited
);
494 MARK_VISITED (ENTRY_BLOCK_PTR
);
500 /* Walk the predecessors of x as long as they have precisely one
501 predecessor and add them to the list, so that they get stored
504 single_pred_p (y
) && !VISITED_P (single_pred (y
));
507 for (y
= x
, i
= n
- np
;
508 single_pred_p (y
) && !VISITED_P (single_pred (y
));
509 y
= single_pred (y
), i
++)
517 gcc_assert (i
== n
- 1);
521 sbitmap_free (visited
);
530 /* Return TRUE if block BB has no executable statements, otherwise return
534 empty_block_p (basic_block bb
)
536 /* BB must have no executable statements. */
537 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
542 if (is_gimple_debug (gsi_stmt (gsi
)))
543 gsi_next_nondebug (&gsi
);
544 return gsi_end_p (gsi
);
547 /* Replace PHI node element whose edge is E in block BB with variable NEW.
548 Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
549 is known to have two edges, one of which must reach BB). */
552 replace_phi_edge_with_variable (basic_block cond_block
,
553 edge e
, gimple phi
, tree new_tree
)
555 basic_block bb
= gimple_bb (phi
);
556 basic_block block_to_remove
;
557 gimple_stmt_iterator gsi
;
559 /* Change the PHI argument to new. */
560 SET_USE (PHI_ARG_DEF_PTR (phi
, e
->dest_idx
), new_tree
);
562 /* Remove the empty basic block. */
563 if (EDGE_SUCC (cond_block
, 0)->dest
== bb
)
565 EDGE_SUCC (cond_block
, 0)->flags
|= EDGE_FALLTHRU
;
566 EDGE_SUCC (cond_block
, 0)->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
567 EDGE_SUCC (cond_block
, 0)->probability
= REG_BR_PROB_BASE
;
568 EDGE_SUCC (cond_block
, 0)->count
+= EDGE_SUCC (cond_block
, 1)->count
;
570 block_to_remove
= EDGE_SUCC (cond_block
, 1)->dest
;
574 EDGE_SUCC (cond_block
, 1)->flags
|= EDGE_FALLTHRU
;
575 EDGE_SUCC (cond_block
, 1)->flags
576 &= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
577 EDGE_SUCC (cond_block
, 1)->probability
= REG_BR_PROB_BASE
;
578 EDGE_SUCC (cond_block
, 1)->count
+= EDGE_SUCC (cond_block
, 0)->count
;
580 block_to_remove
= EDGE_SUCC (cond_block
, 0)->dest
;
582 delete_basic_block (block_to_remove
);
584 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
585 gsi
= gsi_last_bb (cond_block
);
586 gsi_remove (&gsi
, true);
588 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
590 "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
595 /* The function conditional_replacement does the main work of doing the
596 conditional replacement. Return true if the replacement is done.
597 Otherwise return false.
598 BB is the basic block where the replacement is going to be done on. ARG0
599 is argument 0 from PHI. Likewise for ARG1. */
602 conditional_replacement (basic_block cond_bb
, basic_block middle_bb
,
603 edge e0
, edge e1
, gimple phi
,
604 tree arg0
, tree arg1
)
607 gimple stmt
, new_stmt
;
609 gimple_stmt_iterator gsi
;
610 edge true_edge
, false_edge
;
611 tree new_var
, new_var2
;
614 /* FIXME: Gimplification of complex type is too hard for now. */
615 /* We aren't prepared to handle vectors either (and it is a question
616 if it would be worthwhile anyway). */
617 if (!(INTEGRAL_TYPE_P (TREE_TYPE (arg0
))
618 || POINTER_TYPE_P (TREE_TYPE (arg0
)))
619 || !(INTEGRAL_TYPE_P (TREE_TYPE (arg1
))
620 || POINTER_TYPE_P (TREE_TYPE (arg1
))))
623 /* The PHI arguments have the constants 0 and 1, or 0 and -1, then
624 convert it to the conditional. */
625 if ((integer_zerop (arg0
) && integer_onep (arg1
))
626 || (integer_zerop (arg1
) && integer_onep (arg0
)))
628 else if ((integer_zerop (arg0
) && integer_all_onesp (arg1
))
629 || (integer_zerop (arg1
) && integer_all_onesp (arg0
)))
634 if (!empty_block_p (middle_bb
))
637 /* At this point we know we have a GIMPLE_COND with two successors.
638 One successor is BB, the other successor is an empty block which
639 falls through into BB.
641 There is a single PHI node at the join point (BB) and its arguments
642 are constants (0, 1) or (0, -1).
644 So, given the condition COND, and the two PHI arguments, we can
645 rewrite this PHI into non-branching code:
647 dest = (COND) or dest = COND'
649 We use the condition as-is if the argument associated with the
650 true edge has the value one or the argument associated with the
651 false edge as the value zero. Note that those conditions are not
652 the same since only one of the outgoing edges from the GIMPLE_COND
653 will directly reach BB and thus be associated with an argument. */
655 stmt
= last_stmt (cond_bb
);
656 result
= PHI_RESULT (phi
);
658 /* To handle special cases like floating point comparison, it is easier and
659 less error-prone to build a tree and gimplify it on the fly though it is
661 cond
= fold_build2_loc (gimple_location (stmt
),
662 gimple_cond_code (stmt
), boolean_type_node
,
663 gimple_cond_lhs (stmt
), gimple_cond_rhs (stmt
));
665 /* We need to know which is the true edge and which is the false
666 edge so that we know when to invert the condition below. */
667 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
668 if ((e0
== true_edge
&& integer_zerop (arg0
))
669 || (e0
== false_edge
&& !integer_zerop (arg0
))
670 || (e1
== true_edge
&& integer_zerop (arg1
))
671 || (e1
== false_edge
&& !integer_zerop (arg1
)))
672 cond
= fold_build1_loc (gimple_location (stmt
),
673 TRUTH_NOT_EXPR
, TREE_TYPE (cond
), cond
);
677 cond
= fold_convert_loc (gimple_location (stmt
),
678 TREE_TYPE (result
), cond
);
679 cond
= fold_build1_loc (gimple_location (stmt
),
680 NEGATE_EXPR
, TREE_TYPE (cond
), cond
);
683 /* Insert our new statements at the end of conditional block before the
685 gsi
= gsi_for_stmt (stmt
);
686 new_var
= force_gimple_operand_gsi (&gsi
, cond
, true, NULL
, true,
689 if (!useless_type_conversion_p (TREE_TYPE (result
), TREE_TYPE (new_var
)))
691 source_location locus_0
, locus_1
;
693 new_var2
= create_tmp_var (TREE_TYPE (result
), NULL
);
694 add_referenced_var (new_var2
);
695 new_stmt
= gimple_build_assign_with_ops (CONVERT_EXPR
, new_var2
,
697 new_var2
= make_ssa_name (new_var2
, new_stmt
);
698 gimple_assign_set_lhs (new_stmt
, new_var2
);
699 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
702 /* Set the locus to the first argument, unless is doesn't have one. */
703 locus_0
= gimple_phi_arg_location (phi
, 0);
704 locus_1
= gimple_phi_arg_location (phi
, 1);
705 if (locus_0
== UNKNOWN_LOCATION
)
707 gimple_set_location (new_stmt
, locus_0
);
710 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, new_var
);
712 /* Note that we optimized this PHI. */
716 /* Update *ARG which is defined in STMT so that it contains the
717 computed value if that seems profitable. Return true if the
718 statement is made dead by that rewriting. */
721 jump_function_from_stmt (tree
*arg
, gimple stmt
)
723 enum tree_code code
= gimple_assign_rhs_code (stmt
);
724 if (code
== ADDR_EXPR
)
726 /* For arg = &p->i transform it to p, if possible. */
727 tree rhs1
= gimple_assign_rhs1 (stmt
);
728 HOST_WIDE_INT offset
;
729 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs1
, 0),
732 && TREE_CODE (tem
) == MEM_REF
734 (double_int_add (mem_ref_offset (tem
),
735 shwi_to_double_int (offset
))))
737 *arg
= TREE_OPERAND (tem
, 0);
741 /* TODO: Much like IPA-CP jump-functions we want to handle constant
742 additions symbolically here, and we'd need to update the comparison
743 code that compares the arg + cst tuples in our caller. For now the
744 code above exactly handles the VEC_BASE pattern from vec.h. */
748 /* The function value_replacement does the main work of doing the value
749 replacement. Return non-zero if the replacement is done. Otherwise return
750 0. If we remove the middle basic block, return 2.
751 BB is the basic block where the replacement is going to be done on. ARG0
752 is argument 0 from the PHI. Likewise for ARG1. */
755 value_replacement (basic_block cond_bb
, basic_block middle_bb
,
756 edge e0
, edge e1
, gimple phi
,
757 tree arg0
, tree arg1
)
759 gimple_stmt_iterator gsi
;
761 edge true_edge
, false_edge
;
763 bool emtpy_or_with_defined_p
= true;
765 /* If the type says honor signed zeros we cannot do this
767 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1
))))
770 /* If there is a statement in MIDDLE_BB that defines one of the PHI
771 arguments, then adjust arg0 or arg1. */
772 gsi
= gsi_after_labels (middle_bb
);
773 if (!gsi_end_p (gsi
) && is_gimple_debug (gsi_stmt (gsi
)))
774 gsi_next_nondebug (&gsi
);
775 while (!gsi_end_p (gsi
))
777 gimple stmt
= gsi_stmt (gsi
);
779 gsi_next_nondebug (&gsi
);
780 if (!is_gimple_assign (stmt
))
782 emtpy_or_with_defined_p
= false;
785 /* Now try to adjust arg0 or arg1 according to the computation
787 lhs
= gimple_assign_lhs (stmt
);
789 && jump_function_from_stmt (&arg0
, stmt
))
791 && jump_function_from_stmt (&arg1
, stmt
)))
792 emtpy_or_with_defined_p
= false;
795 cond
= last_stmt (cond_bb
);
796 code
= gimple_cond_code (cond
);
798 /* This transformation is only valid for equality comparisons. */
799 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
802 /* We need to know which is the true edge and which is the false
803 edge so that we know if have abs or negative abs. */
804 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
806 /* At this point we know we have a COND_EXPR with two successors.
807 One successor is BB, the other successor is an empty block which
808 falls through into BB.
810 The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
812 There is a single PHI node at the join point (BB) with two arguments.
814 We now need to verify that the two arguments in the PHI node match
815 the two arguments to the equality comparison. */
817 if ((operand_equal_for_phi_arg_p (arg0
, gimple_cond_lhs (cond
))
818 && operand_equal_for_phi_arg_p (arg1
, gimple_cond_rhs (cond
)))
819 || (operand_equal_for_phi_arg_p (arg1
, gimple_cond_lhs (cond
))
820 && operand_equal_for_phi_arg_p (arg0
, gimple_cond_rhs (cond
))))
825 /* For NE_EXPR, we want to build an assignment result = arg where
826 arg is the PHI argument associated with the true edge. For
827 EQ_EXPR we want the PHI argument associated with the false edge. */
828 e
= (code
== NE_EXPR
? true_edge
: false_edge
);
830 /* Unfortunately, E may not reach BB (it may instead have gone to
831 OTHER_BLOCK). If that is the case, then we want the single outgoing
832 edge from OTHER_BLOCK which reaches BB and represents the desired
833 path from COND_BLOCK. */
834 if (e
->dest
== middle_bb
)
835 e
= single_succ_edge (e
->dest
);
837 /* Now we know the incoming edge to BB that has the argument for the
838 RHS of our new assignment statement. */
844 /* If the middle basic block was empty or is defining the
845 PHI arguments and this is a single phi where the args are different
846 for the edges e0 and e1 then we can remove the middle basic block. */
847 if (emtpy_or_with_defined_p
848 && single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi
)),
851 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, arg
);
852 /* Note that we optimized this PHI. */
857 /* Replace the PHI arguments with arg. */
858 SET_PHI_ARG_DEF (phi
, e0
->dest_idx
, arg
);
859 SET_PHI_ARG_DEF (phi
, e1
->dest_idx
, arg
);
860 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
862 fprintf (dump_file
, "PHI ");
863 print_generic_expr (dump_file
, gimple_phi_result (phi
), 0);
864 fprintf (dump_file
, " reduced for COND_EXPR in block %d to ",
866 print_generic_expr (dump_file
, arg
, 0);
867 fprintf (dump_file
, ".\n");
876 /* The function minmax_replacement does the main work of doing the minmax
877 replacement. Return true if the replacement is done. Otherwise return
879 BB is the basic block where the replacement is going to be done on. ARG0
880 is argument 0 from the PHI. Likewise for ARG1. */
883 minmax_replacement (basic_block cond_bb
, basic_block middle_bb
,
884 edge e0
, edge e1
, gimple phi
,
885 tree arg0
, tree arg1
)
888 gimple cond
, new_stmt
;
889 edge true_edge
, false_edge
;
890 enum tree_code cmp
, minmax
, ass_code
;
891 tree smaller
, larger
, arg_true
, arg_false
;
892 gimple_stmt_iterator gsi
, gsi_from
;
894 type
= TREE_TYPE (PHI_RESULT (phi
));
896 /* The optimization may be unsafe due to NaNs. */
897 if (HONOR_NANS (TYPE_MODE (type
)))
900 cond
= last_stmt (cond_bb
);
901 cmp
= gimple_cond_code (cond
);
903 /* This transformation is only valid for order comparisons. Record which
904 operand is smaller/larger if the result of the comparison is true. */
905 if (cmp
== LT_EXPR
|| cmp
== LE_EXPR
)
907 smaller
= gimple_cond_lhs (cond
);
908 larger
= gimple_cond_rhs (cond
);
910 else if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
912 smaller
= gimple_cond_rhs (cond
);
913 larger
= gimple_cond_lhs (cond
);
918 /* We need to know which is the true edge and which is the false
919 edge so that we know if have abs or negative abs. */
920 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
922 /* Forward the edges over the middle basic block. */
923 if (true_edge
->dest
== middle_bb
)
924 true_edge
= EDGE_SUCC (true_edge
->dest
, 0);
925 if (false_edge
->dest
== middle_bb
)
926 false_edge
= EDGE_SUCC (false_edge
->dest
, 0);
930 gcc_assert (false_edge
== e1
);
936 gcc_assert (false_edge
== e0
);
937 gcc_assert (true_edge
== e1
);
942 if (empty_block_p (middle_bb
))
944 if (operand_equal_for_phi_arg_p (arg_true
, smaller
)
945 && operand_equal_for_phi_arg_p (arg_false
, larger
))
949 if (smaller < larger)
955 else if (operand_equal_for_phi_arg_p (arg_false
, smaller
)
956 && operand_equal_for_phi_arg_p (arg_true
, larger
))
963 /* Recognize the following case, assuming d <= u:
969 This is equivalent to
974 gimple assign
= last_and_only_stmt (middle_bb
);
975 tree lhs
, op0
, op1
, bound
;
978 || gimple_code (assign
) != GIMPLE_ASSIGN
)
981 lhs
= gimple_assign_lhs (assign
);
982 ass_code
= gimple_assign_rhs_code (assign
);
983 if (ass_code
!= MAX_EXPR
&& ass_code
!= MIN_EXPR
)
985 op0
= gimple_assign_rhs1 (assign
);
986 op1
= gimple_assign_rhs2 (assign
);
988 if (true_edge
->src
== middle_bb
)
990 /* We got here if the condition is true, i.e., SMALLER < LARGER. */
991 if (!operand_equal_for_phi_arg_p (lhs
, arg_true
))
994 if (operand_equal_for_phi_arg_p (arg_false
, larger
))
998 if (smaller < larger)
1000 r' = MAX_EXPR (smaller, bound)
1002 r = PHI <r', larger> --> to be turned to MIN_EXPR. */
1003 if (ass_code
!= MAX_EXPR
)
1007 if (operand_equal_for_phi_arg_p (op0
, smaller
))
1009 else if (operand_equal_for_phi_arg_p (op1
, smaller
))
1014 /* We need BOUND <= LARGER. */
1015 if (!integer_nonzerop (fold_build2 (LE_EXPR
, boolean_type_node
,
1019 else if (operand_equal_for_phi_arg_p (arg_false
, smaller
))
1023 if (smaller < larger)
1025 r' = MIN_EXPR (larger, bound)
1027 r = PHI <r', smaller> --> to be turned to MAX_EXPR. */
1028 if (ass_code
!= MIN_EXPR
)
1032 if (operand_equal_for_phi_arg_p (op0
, larger
))
1034 else if (operand_equal_for_phi_arg_p (op1
, larger
))
1039 /* We need BOUND >= SMALLER. */
1040 if (!integer_nonzerop (fold_build2 (GE_EXPR
, boolean_type_node
,
1049 /* We got here if the condition is false, i.e., SMALLER > LARGER. */
1050 if (!operand_equal_for_phi_arg_p (lhs
, arg_false
))
1053 if (operand_equal_for_phi_arg_p (arg_true
, larger
))
1057 if (smaller > larger)
1059 r' = MIN_EXPR (smaller, bound)
1061 r = PHI <r', larger> --> to be turned to MAX_EXPR. */
1062 if (ass_code
!= MIN_EXPR
)
1066 if (operand_equal_for_phi_arg_p (op0
, smaller
))
1068 else if (operand_equal_for_phi_arg_p (op1
, smaller
))
1073 /* We need BOUND >= LARGER. */
1074 if (!integer_nonzerop (fold_build2 (GE_EXPR
, boolean_type_node
,
1078 else if (operand_equal_for_phi_arg_p (arg_true
, smaller
))
1082 if (smaller > larger)
1084 r' = MAX_EXPR (larger, bound)
1086 r = PHI <r', smaller> --> to be turned to MIN_EXPR. */
1087 if (ass_code
!= MAX_EXPR
)
1091 if (operand_equal_for_phi_arg_p (op0
, larger
))
1093 else if (operand_equal_for_phi_arg_p (op1
, larger
))
1098 /* We need BOUND <= SMALLER. */
1099 if (!integer_nonzerop (fold_build2 (LE_EXPR
, boolean_type_node
,
1107 /* Move the statement from the middle block. */
1108 gsi
= gsi_last_bb (cond_bb
);
1109 gsi_from
= gsi_last_nondebug_bb (middle_bb
);
1110 gsi_move_before (&gsi_from
, &gsi
);
1113 /* Emit the statement to compute min/max. */
1114 result
= duplicate_ssa_name (PHI_RESULT (phi
), NULL
);
1115 new_stmt
= gimple_build_assign_with_ops (minmax
, result
, arg0
, arg1
);
1116 gsi
= gsi_last_bb (cond_bb
);
1117 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
1119 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, result
);
1123 /* The function absolute_replacement does the main work of doing the absolute
1124 replacement. Return true if the replacement is done. Otherwise return
1126 bb is the basic block where the replacement is going to be done on. arg0
1127 is argument 0 from the phi. Likewise for arg1. */
1130 abs_replacement (basic_block cond_bb
, basic_block middle_bb
,
1131 edge e0 ATTRIBUTE_UNUSED
, edge e1
,
1132 gimple phi
, tree arg0
, tree arg1
)
1135 gimple new_stmt
, cond
;
1136 gimple_stmt_iterator gsi
;
1137 edge true_edge
, false_edge
;
1142 enum tree_code cond_code
;
1144 /* If the type says honor signed zeros we cannot do this
1146 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1
))))
1149 /* OTHER_BLOCK must have only one executable statement which must have the
1150 form arg0 = -arg1 or arg1 = -arg0. */
1152 assign
= last_and_only_stmt (middle_bb
);
1153 /* If we did not find the proper negation assignment, then we can not
1158 /* If we got here, then we have found the only executable statement
1159 in OTHER_BLOCK. If it is anything other than arg = -arg1 or
1160 arg1 = -arg0, then we can not optimize. */
1161 if (gimple_code (assign
) != GIMPLE_ASSIGN
)
1164 lhs
= gimple_assign_lhs (assign
);
1166 if (gimple_assign_rhs_code (assign
) != NEGATE_EXPR
)
1169 rhs
= gimple_assign_rhs1 (assign
);
1171 /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */
1172 if (!(lhs
== arg0
&& rhs
== arg1
)
1173 && !(lhs
== arg1
&& rhs
== arg0
))
1176 cond
= last_stmt (cond_bb
);
1177 result
= PHI_RESULT (phi
);
1179 /* Only relationals comparing arg[01] against zero are interesting. */
1180 cond_code
= gimple_cond_code (cond
);
1181 if (cond_code
!= GT_EXPR
&& cond_code
!= GE_EXPR
1182 && cond_code
!= LT_EXPR
&& cond_code
!= LE_EXPR
)
1185 /* Make sure the conditional is arg[01] OP y. */
1186 if (gimple_cond_lhs (cond
) != rhs
)
1189 if (FLOAT_TYPE_P (TREE_TYPE (gimple_cond_rhs (cond
)))
1190 ? real_zerop (gimple_cond_rhs (cond
))
1191 : integer_zerop (gimple_cond_rhs (cond
)))
1196 /* We need to know which is the true edge and which is the false
1197 edge so that we know if have abs or negative abs. */
1198 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
1200 /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
1201 will need to negate the result. Similarly for LT_EXPR/LE_EXPR if
1202 the false edge goes to OTHER_BLOCK. */
1203 if (cond_code
== GT_EXPR
|| cond_code
== GE_EXPR
)
1208 if (e
->dest
== middle_bb
)
1213 result
= duplicate_ssa_name (result
, NULL
);
1217 tree tmp
= create_tmp_var (TREE_TYPE (result
), NULL
);
1218 add_referenced_var (tmp
);
1219 lhs
= make_ssa_name (tmp
, NULL
);
1224 /* Build the modify expression with abs expression. */
1225 new_stmt
= gimple_build_assign_with_ops (ABS_EXPR
, lhs
, rhs
, NULL
);
1227 gsi
= gsi_last_bb (cond_bb
);
1228 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
1232 /* Get the right GSI. We want to insert after the recently
1233 added ABS_EXPR statement (which we know is the first statement
1235 new_stmt
= gimple_build_assign_with_ops (NEGATE_EXPR
, result
, lhs
, NULL
);
1237 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
1240 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, result
);
1242 /* Note that we optimized this PHI. */
1246 /* Auxiliary functions to determine the set of memory accesses which
1247 can't trap because they are preceded by accesses to the same memory
1248 portion. We do that for MEM_REFs, so we only need to track
1249 the SSA_NAME of the pointer indirectly referenced. The algorithm
1250 simply is a walk over all instructions in dominator order. When
1251 we see an MEM_REF we determine if we've already seen a same
1252 ref anywhere up to the root of the dominator tree. If we do the
1253 current access can't trap. If we don't see any dominating access
1254 the current access might trap, but might also make later accesses
1255 non-trapping, so we remember it. We need to be careful with loads
1256 or stores, for instance a load might not trap, while a store would,
1257 so if we see a dominating read access this doesn't mean that a later
1258 write access would not trap. Hence we also need to differentiate the
1259 type of access(es) seen.
1261 ??? We currently are very conservative and assume that a load might
1262 trap even if a store doesn't (write-only memory). This probably is
1263 overly conservative. */
1265 /* A hash-table of SSA_NAMEs, and in which basic block an MEM_REF
1266 through it was seen, which would constitute a no-trap region for
1270 unsigned int ssa_name_ver
;
1272 HOST_WIDE_INT offset
, size
;
1276 /* The hash table for remembering what we've seen. */
1277 static htab_t seen_ssa_names
;
1279 /* The set of MEM_REFs which can't trap. */
1280 static struct pointer_set_t
*nontrap_set
;
1282 /* The hash function. */
1284 name_to_bb_hash (const void *p
)
1286 const struct name_to_bb
*n
= (const struct name_to_bb
*) p
;
1287 return n
->ssa_name_ver
^ (((hashval_t
) n
->store
) << 31)
1288 ^ (n
->offset
<< 6) ^ (n
->size
<< 3);
1291 /* The equality function of *P1 and *P2. */
1293 name_to_bb_eq (const void *p1
, const void *p2
)
1295 const struct name_to_bb
*n1
= (const struct name_to_bb
*)p1
;
1296 const struct name_to_bb
*n2
= (const struct name_to_bb
*)p2
;
1298 return n1
->ssa_name_ver
== n2
->ssa_name_ver
1299 && n1
->store
== n2
->store
1300 && n1
->offset
== n2
->offset
1301 && n1
->size
== n2
->size
;
1304 /* We see the expression EXP in basic block BB. If it's an interesting
1305 expression (an MEM_REF through an SSA_NAME) possibly insert the
1306 expression into the set NONTRAP or the hash table of seen expressions.
1307 STORE is true if this expression is on the LHS, otherwise it's on
1310 add_or_mark_expr (basic_block bb
, tree exp
,
1311 struct pointer_set_t
*nontrap
, bool store
)
1315 if (TREE_CODE (exp
) == MEM_REF
1316 && TREE_CODE (TREE_OPERAND (exp
, 0)) == SSA_NAME
1317 && host_integerp (TREE_OPERAND (exp
, 1), 0)
1318 && (size
= int_size_in_bytes (TREE_TYPE (exp
))) > 0)
1320 tree name
= TREE_OPERAND (exp
, 0);
1321 struct name_to_bb map
;
1323 struct name_to_bb
*n2bb
;
1324 basic_block found_bb
= 0;
1326 /* Try to find the last seen MEM_REF through the same
1327 SSA_NAME, which can trap. */
1328 map
.ssa_name_ver
= SSA_NAME_VERSION (name
);
1331 map
.offset
= tree_low_cst (TREE_OPERAND (exp
, 1), 0);
1334 slot
= htab_find_slot (seen_ssa_names
, &map
, INSERT
);
1335 n2bb
= (struct name_to_bb
*) *slot
;
1337 found_bb
= n2bb
->bb
;
1339 /* If we've found a trapping MEM_REF, _and_ it dominates EXP
1340 (it's in a basic block on the path from us to the dominator root)
1341 then we can't trap. */
1342 if (found_bb
&& found_bb
->aux
== (void *)1)
1344 pointer_set_insert (nontrap
, exp
);
1348 /* EXP might trap, so insert it into the hash table. */
1355 n2bb
= XNEW (struct name_to_bb
);
1356 n2bb
->ssa_name_ver
= SSA_NAME_VERSION (name
);
1358 n2bb
->store
= store
;
1359 n2bb
->offset
= map
.offset
;
1367 /* Called by walk_dominator_tree, when entering the block BB. */
1369 nt_init_block (struct dom_walk_data
*data ATTRIBUTE_UNUSED
, basic_block bb
)
1371 gimple_stmt_iterator gsi
;
1372 /* Mark this BB as being on the path to dominator root. */
1375 /* And walk the statements in order. */
1376 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1378 gimple stmt
= gsi_stmt (gsi
);
1380 if (gimple_assign_single_p (stmt
))
1382 add_or_mark_expr (bb
, gimple_assign_lhs (stmt
), nontrap_set
, true);
1383 add_or_mark_expr (bb
, gimple_assign_rhs1 (stmt
), nontrap_set
, false);
1388 /* Called by walk_dominator_tree, when basic block BB is exited. */
1390 nt_fini_block (struct dom_walk_data
*data ATTRIBUTE_UNUSED
, basic_block bb
)
1392 /* This BB isn't on the path to dominator root anymore. */
1396 /* This is the entry point of gathering non trapping memory accesses.
1397 It will do a dominator walk over the whole function, and it will
1398 make use of the bb->aux pointers. It returns a set of trees
1399 (the MEM_REFs itself) which can't trap. */
1400 static struct pointer_set_t
*
1401 get_non_trapping (void)
1403 struct pointer_set_t
*nontrap
;
1404 struct dom_walk_data walk_data
;
1406 nontrap
= pointer_set_create ();
1407 seen_ssa_names
= htab_create (128, name_to_bb_hash
, name_to_bb_eq
,
1409 /* We're going to do a dominator walk, so ensure that we have
1410 dominance information. */
1411 calculate_dominance_info (CDI_DOMINATORS
);
1413 /* Setup callbacks for the generic dominator tree walker. */
1414 nontrap_set
= nontrap
;
1415 walk_data
.dom_direction
= CDI_DOMINATORS
;
1416 walk_data
.initialize_block_local_data
= NULL
;
1417 walk_data
.before_dom_children
= nt_init_block
;
1418 walk_data
.after_dom_children
= nt_fini_block
;
1419 walk_data
.global_data
= NULL
;
1420 walk_data
.block_local_data_size
= 0;
1422 init_walk_dominator_tree (&walk_data
);
1423 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1424 fini_walk_dominator_tree (&walk_data
);
1425 htab_delete (seen_ssa_names
);
1430 /* Do the main work of conditional store replacement. We already know
1431 that the recognized pattern looks like so:
1434 if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
1437 fallthrough (edge E0)
1441 We check that MIDDLE_BB contains only one store, that that store
1442 doesn't trap (not via NOTRAP, but via checking if an access to the same
1443 memory location dominates us) and that the store has a "simple" RHS. */
1446 cond_store_replacement (basic_block middle_bb
, basic_block join_bb
,
1447 edge e0
, edge e1
, struct pointer_set_t
*nontrap
)
1449 gimple assign
= last_and_only_stmt (middle_bb
);
1450 tree lhs
, rhs
, name
;
1451 gimple newphi
, new_stmt
;
1452 gimple_stmt_iterator gsi
;
1453 source_location locus
;
1455 /* Check if middle_bb contains of only one store. */
1457 || !gimple_assign_single_p (assign
))
1460 locus
= gimple_location (assign
);
1461 lhs
= gimple_assign_lhs (assign
);
1462 rhs
= gimple_assign_rhs1 (assign
);
1463 if (TREE_CODE (lhs
) != MEM_REF
1464 || TREE_CODE (TREE_OPERAND (lhs
, 0)) != SSA_NAME
1465 || !is_gimple_reg_type (TREE_TYPE (lhs
)))
1468 /* Prove that we can move the store down. We could also check
1469 TREE_THIS_NOTRAP here, but in that case we also could move stores,
1470 whose value is not available readily, which we want to avoid. */
1471 if (!pointer_set_contains (nontrap
, lhs
))
1474 /* Now we've checked the constraints, so do the transformation:
1475 1) Remove the single store. */
1476 gsi
= gsi_for_stmt (assign
);
1477 unlink_stmt_vdef (assign
);
1478 gsi_remove (&gsi
, true);
1479 release_defs (assign
);
1481 /* 2) Create a temporary where we can store the old content
1482 of the memory touched by the store, if we need to. */
1483 if (!condstoretemp
|| TREE_TYPE (lhs
) != TREE_TYPE (condstoretemp
))
1484 condstoretemp
= create_tmp_reg (TREE_TYPE (lhs
), "cstore");
1485 add_referenced_var (condstoretemp
);
1487 /* 3) Insert a load from the memory of the store to the temporary
1488 on the edge which did not contain the store. */
1489 lhs
= unshare_expr (lhs
);
1490 new_stmt
= gimple_build_assign (condstoretemp
, lhs
);
1491 name
= make_ssa_name (condstoretemp
, new_stmt
);
1492 gimple_assign_set_lhs (new_stmt
, name
);
1493 gimple_set_location (new_stmt
, locus
);
1494 gsi_insert_on_edge (e1
, new_stmt
);
1496 /* 4) Create a PHI node at the join block, with one argument
1497 holding the old RHS, and the other holding the temporary
1498 where we stored the old memory contents. */
1499 newphi
= create_phi_node (condstoretemp
, join_bb
);
1500 add_phi_arg (newphi
, rhs
, e0
, locus
);
1501 add_phi_arg (newphi
, name
, e1
, locus
);
1503 lhs
= unshare_expr (lhs
);
1504 new_stmt
= gimple_build_assign (lhs
, PHI_RESULT (newphi
));
1506 /* 5) Insert that PHI node. */
1507 gsi
= gsi_after_labels (join_bb
);
1508 if (gsi_end_p (gsi
))
1510 gsi
= gsi_last_bb (join_bb
);
1511 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
1514 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
1519 /* Do the main work of conditional store replacement. */
1522 cond_if_else_store_replacement_1 (basic_block then_bb
, basic_block else_bb
,
1523 basic_block join_bb
, gimple then_assign
,
1526 tree lhs_base
, lhs
, then_rhs
, else_rhs
;
1527 source_location then_locus
, else_locus
;
1528 gimple_stmt_iterator gsi
;
1529 gimple newphi
, new_stmt
;
1531 if (then_assign
== NULL
1532 || !gimple_assign_single_p (then_assign
)
1533 || gimple_clobber_p (then_assign
)
1534 || else_assign
== NULL
1535 || !gimple_assign_single_p (else_assign
)
1536 || gimple_clobber_p (else_assign
))
1539 lhs
= gimple_assign_lhs (then_assign
);
1540 if (!is_gimple_reg_type (TREE_TYPE (lhs
))
1541 || !operand_equal_p (lhs
, gimple_assign_lhs (else_assign
), 0))
1544 lhs_base
= get_base_address (lhs
);
1545 if (lhs_base
== NULL_TREE
1546 || (!DECL_P (lhs_base
) && TREE_CODE (lhs_base
) != MEM_REF
))
1549 then_rhs
= gimple_assign_rhs1 (then_assign
);
1550 else_rhs
= gimple_assign_rhs1 (else_assign
);
1551 then_locus
= gimple_location (then_assign
);
1552 else_locus
= gimple_location (else_assign
);
1554 /* Now we've checked the constraints, so do the transformation:
1555 1) Remove the stores. */
1556 gsi
= gsi_for_stmt (then_assign
);
1557 unlink_stmt_vdef (then_assign
);
1558 gsi_remove (&gsi
, true);
1559 release_defs (then_assign
);
1561 gsi
= gsi_for_stmt (else_assign
);
1562 unlink_stmt_vdef (else_assign
);
1563 gsi_remove (&gsi
, true);
1564 release_defs (else_assign
);
1566 /* 2) Create a temporary where we can store the old content
1567 of the memory touched by the store, if we need to. */
1568 if (!condstoretemp
|| TREE_TYPE (lhs
) != TREE_TYPE (condstoretemp
))
1569 condstoretemp
= create_tmp_reg (TREE_TYPE (lhs
), "cstore");
1570 add_referenced_var (condstoretemp
);
1572 /* 3) Create a PHI node at the join block, with one argument
1573 holding the old RHS, and the other holding the temporary
1574 where we stored the old memory contents. */
1575 newphi
= create_phi_node (condstoretemp
, join_bb
);
1576 add_phi_arg (newphi
, then_rhs
, EDGE_SUCC (then_bb
, 0), then_locus
);
1577 add_phi_arg (newphi
, else_rhs
, EDGE_SUCC (else_bb
, 0), else_locus
);
1579 new_stmt
= gimple_build_assign (lhs
, PHI_RESULT (newphi
));
1581 /* 4) Insert that PHI node. */
1582 gsi
= gsi_after_labels (join_bb
);
1583 if (gsi_end_p (gsi
))
1585 gsi
= gsi_last_bb (join_bb
);
1586 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
1589 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
1594 /* Conditional store replacement. We already know
1595 that the recognized pattern looks like so:
1598 if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
1608 fallthrough (edge E0)
1612 We check that it is safe to sink the store to JOIN_BB by verifying that
1613 there are no read-after-write or write-after-write dependencies in
1614 THEN_BB and ELSE_BB. */
1617 cond_if_else_store_replacement (basic_block then_bb
, basic_block else_bb
,
1618 basic_block join_bb
)
1620 gimple then_assign
= last_and_only_stmt (then_bb
);
1621 gimple else_assign
= last_and_only_stmt (else_bb
);
1622 VEC (data_reference_p
, heap
) *then_datarefs
, *else_datarefs
;
1623 VEC (ddr_p
, heap
) *then_ddrs
, *else_ddrs
;
1624 gimple then_store
, else_store
;
1625 bool found
, ok
= false, res
;
1626 struct data_dependence_relation
*ddr
;
1627 data_reference_p then_dr
, else_dr
;
1629 tree then_lhs
, else_lhs
;
1630 VEC (gimple
, heap
) *then_stores
, *else_stores
;
1631 basic_block blocks
[3];
1633 if (MAX_STORES_TO_SINK
== 0)
1636 /* Handle the case with single statement in THEN_BB and ELSE_BB. */
1637 if (then_assign
&& else_assign
)
1638 return cond_if_else_store_replacement_1 (then_bb
, else_bb
, join_bb
,
1639 then_assign
, else_assign
);
1641 /* Find data references. */
1642 then_datarefs
= VEC_alloc (data_reference_p
, heap
, 1);
1643 else_datarefs
= VEC_alloc (data_reference_p
, heap
, 1);
1644 if ((find_data_references_in_bb (NULL
, then_bb
, &then_datarefs
)
1646 || !VEC_length (data_reference_p
, then_datarefs
)
1647 || (find_data_references_in_bb (NULL
, else_bb
, &else_datarefs
)
1649 || !VEC_length (data_reference_p
, else_datarefs
))
1651 free_data_refs (then_datarefs
);
1652 free_data_refs (else_datarefs
);
1656 /* Find pairs of stores with equal LHS. */
1657 then_stores
= VEC_alloc (gimple
, heap
, 1);
1658 else_stores
= VEC_alloc (gimple
, heap
, 1);
1659 FOR_EACH_VEC_ELT (data_reference_p
, then_datarefs
, i
, then_dr
)
1661 if (DR_IS_READ (then_dr
))
1664 then_store
= DR_STMT (then_dr
);
1665 then_lhs
= gimple_get_lhs (then_store
);
1668 FOR_EACH_VEC_ELT (data_reference_p
, else_datarefs
, j
, else_dr
)
1670 if (DR_IS_READ (else_dr
))
1673 else_store
= DR_STMT (else_dr
);
1674 else_lhs
= gimple_get_lhs (else_store
);
1676 if (operand_equal_p (then_lhs
, else_lhs
, 0))
1686 VEC_safe_push (gimple
, heap
, then_stores
, then_store
);
1687 VEC_safe_push (gimple
, heap
, else_stores
, else_store
);
1690 /* No pairs of stores found. */
1691 if (!VEC_length (gimple
, then_stores
)
1692 || VEC_length (gimple
, then_stores
) > (unsigned) MAX_STORES_TO_SINK
)
1694 free_data_refs (then_datarefs
);
1695 free_data_refs (else_datarefs
);
1696 VEC_free (gimple
, heap
, then_stores
);
1697 VEC_free (gimple
, heap
, else_stores
);
1701 /* Compute and check data dependencies in both basic blocks. */
1702 then_ddrs
= VEC_alloc (ddr_p
, heap
, 1);
1703 else_ddrs
= VEC_alloc (ddr_p
, heap
, 1);
1704 if (!compute_all_dependences (then_datarefs
, &then_ddrs
, NULL
, false)
1705 || !compute_all_dependences (else_datarefs
, &else_ddrs
, NULL
, false))
1707 free_dependence_relations (then_ddrs
);
1708 free_dependence_relations (else_ddrs
);
1709 free_data_refs (then_datarefs
);
1710 free_data_refs (else_datarefs
);
1711 VEC_free (gimple
, heap
, then_stores
);
1712 VEC_free (gimple
, heap
, else_stores
);
1715 blocks
[0] = then_bb
;
1716 blocks
[1] = else_bb
;
1717 blocks
[2] = join_bb
;
1718 renumber_gimple_stmt_uids_in_blocks (blocks
, 3);
1720 /* Check that there are no read-after-write or write-after-write dependencies
1722 FOR_EACH_VEC_ELT (ddr_p
, then_ddrs
, i
, ddr
)
1724 struct data_reference
*dra
= DDR_A (ddr
);
1725 struct data_reference
*drb
= DDR_B (ddr
);
1727 if (DDR_ARE_DEPENDENT (ddr
) != chrec_known
1728 && ((DR_IS_READ (dra
) && DR_IS_WRITE (drb
)
1729 && gimple_uid (DR_STMT (dra
)) > gimple_uid (DR_STMT (drb
)))
1730 || (DR_IS_READ (drb
) && DR_IS_WRITE (dra
)
1731 && gimple_uid (DR_STMT (drb
)) > gimple_uid (DR_STMT (dra
)))
1732 || (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))))
1734 free_dependence_relations (then_ddrs
);
1735 free_dependence_relations (else_ddrs
);
1736 free_data_refs (then_datarefs
);
1737 free_data_refs (else_datarefs
);
1738 VEC_free (gimple
, heap
, then_stores
);
1739 VEC_free (gimple
, heap
, else_stores
);
1744 /* Check that there are no read-after-write or write-after-write dependencies
1746 FOR_EACH_VEC_ELT (ddr_p
, else_ddrs
, i
, ddr
)
1748 struct data_reference
*dra
= DDR_A (ddr
);
1749 struct data_reference
*drb
= DDR_B (ddr
);
1751 if (DDR_ARE_DEPENDENT (ddr
) != chrec_known
1752 && ((DR_IS_READ (dra
) && DR_IS_WRITE (drb
)
1753 && gimple_uid (DR_STMT (dra
)) > gimple_uid (DR_STMT (drb
)))
1754 || (DR_IS_READ (drb
) && DR_IS_WRITE (dra
)
1755 && gimple_uid (DR_STMT (drb
)) > gimple_uid (DR_STMT (dra
)))
1756 || (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))))
1758 free_dependence_relations (then_ddrs
);
1759 free_dependence_relations (else_ddrs
);
1760 free_data_refs (then_datarefs
);
1761 free_data_refs (else_datarefs
);
1762 VEC_free (gimple
, heap
, then_stores
);
1763 VEC_free (gimple
, heap
, else_stores
);
1768 /* Sink stores with same LHS. */
1769 FOR_EACH_VEC_ELT (gimple
, then_stores
, i
, then_store
)
1771 else_store
= VEC_index (gimple
, else_stores
, i
);
1772 res
= cond_if_else_store_replacement_1 (then_bb
, else_bb
, join_bb
,
1773 then_store
, else_store
);
1777 free_dependence_relations (then_ddrs
);
1778 free_dependence_relations (else_ddrs
);
1779 free_data_refs (then_datarefs
);
1780 free_data_refs (else_datarefs
);
1781 VEC_free (gimple
, heap
, then_stores
);
1782 VEC_free (gimple
, heap
, else_stores
);
1787 /* Return TRUE if STMT has a VUSE whose corresponding VDEF is in BB. */
1790 local_mem_dependence (gimple stmt
, basic_block bb
)
1792 tree vuse
= gimple_vuse (stmt
);
1798 def
= SSA_NAME_DEF_STMT (vuse
);
1799 return (def
&& gimple_bb (def
) == bb
);
1802 /* Given a "diamond" control-flow pattern where BB0 tests a condition,
1803 BB1 and BB2 are "then" and "else" blocks dependent on this test,
1804 and BB3 rejoins control flow following BB1 and BB2, look for
1805 opportunities to hoist loads as follows. If BB3 contains a PHI of
1806 two loads, one each occurring in BB1 and BB2, and the loads are
1807 provably of adjacent fields in the same structure, then move both
1808 loads into BB0. Of course this can only be done if there are no
1809 dependencies preventing such motion.
1811 One of the hoisted loads will always be speculative, so the
1812 transformation is currently conservative:
1814 - The fields must be strictly adjacent.
1815 - The two fields must occupy a single memory block that is
1816 guaranteed to not cross a page boundary.
1818 The last is difficult to prove, as such memory blocks should be
1819 aligned on the minimum of the stack alignment boundary and the
1820 alignment guaranteed by heap allocation interfaces. Thus we rely
1821 on a parameter for the alignment value.
1823 Provided a good value is used for the last case, the first
1824 restriction could possibly be relaxed. */
1827 hoist_adjacent_loads (basic_block bb0
, basic_block bb1
,
1828 basic_block bb2
, basic_block bb3
)
1830 int param_align
= PARAM_VALUE (PARAM_L1_CACHE_LINE_SIZE
);
1831 unsigned param_align_bits
= (unsigned) (param_align
* BITS_PER_UNIT
);
1832 gimple_stmt_iterator gsi
;
1834 /* Walk the phis in bb3 looking for an opportunity. We are looking
1835 for phis of two SSA names, one each of which is defined in bb1 and
1837 for (gsi
= gsi_start_phis (bb3
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1839 gimple phi_stmt
= gsi_stmt (gsi
);
1840 gimple def1
, def2
, defswap
;
1841 tree arg1
, arg2
, ref1
, ref2
, field1
, field2
, fieldswap
;
1842 tree tree_offset1
, tree_offset2
, tree_size2
, next
;
1843 int offset1
, offset2
, size2
;
1845 gimple_stmt_iterator gsi2
;
1846 basic_block bb_for_def1
, bb_for_def2
;
1848 if (gimple_phi_num_args (phi_stmt
) != 2)
1851 arg1
= gimple_phi_arg_def (phi_stmt
, 0);
1852 arg2
= gimple_phi_arg_def (phi_stmt
, 1);
1854 if (TREE_CODE (arg1
) != SSA_NAME
1855 || TREE_CODE (arg2
) != SSA_NAME
1856 || SSA_NAME_IS_DEFAULT_DEF (arg1
)
1857 || SSA_NAME_IS_DEFAULT_DEF (arg2
)
1858 || !is_gimple_reg (arg1
)
1859 || !is_gimple_reg (arg2
))
1862 def1
= SSA_NAME_DEF_STMT (arg1
);
1863 def2
= SSA_NAME_DEF_STMT (arg2
);
1865 if ((gimple_bb (def1
) != bb1
|| gimple_bb (def2
) != bb2
)
1866 && (gimple_bb (def2
) != bb1
|| gimple_bb (def1
) != bb2
))
1869 /* Check the mode of the arguments to be sure a conditional move
1870 can be generated for it. */
1871 if (!optab_handler (cmov_optab
, TYPE_MODE (TREE_TYPE (arg1
))))
1874 /* Both statements must be assignments whose RHS is a COMPONENT_REF. */
1875 if (!gimple_assign_single_p (def1
)
1876 || !gimple_assign_single_p (def2
))
1879 ref1
= gimple_assign_rhs1 (def1
);
1880 ref2
= gimple_assign_rhs1 (def2
);
1882 if (TREE_CODE (ref1
) != COMPONENT_REF
1883 || TREE_CODE (ref2
) != COMPONENT_REF
)
1886 /* The zeroth operand of the two component references must be
1887 identical. It is not sufficient to compare get_base_address of
1888 the two references, because this could allow for different
1889 elements of the same array in the two trees. It is not safe to
1890 assume that the existence of one array element implies the
1891 existence of a different one. */
1892 if (!operand_equal_p (TREE_OPERAND (ref1
, 0), TREE_OPERAND (ref2
, 0), 0))
1895 field1
= TREE_OPERAND (ref1
, 1);
1896 field2
= TREE_OPERAND (ref2
, 1);
1898 /* Check for field adjacency, and ensure field1 comes first. */
1899 for (next
= DECL_CHAIN (field1
);
1900 next
&& TREE_CODE (next
) != FIELD_DECL
;
1901 next
= DECL_CHAIN (next
))
1906 for (next
= DECL_CHAIN (field2
);
1907 next
&& TREE_CODE (next
) != FIELD_DECL
;
1908 next
= DECL_CHAIN (next
))
1922 bb_for_def1
= gimple_bb (def1
);
1923 bb_for_def2
= gimple_bb (def2
);
1925 /* Check for proper alignment of the first field. */
1926 tree_offset1
= bit_position (field1
);
1927 tree_offset2
= bit_position (field2
);
1928 tree_size2
= DECL_SIZE (field2
);
1930 if (!host_integerp (tree_offset1
, 1)
1931 || !host_integerp (tree_offset2
, 1)
1932 || !host_integerp (tree_size2
, 1))
1935 offset1
= TREE_INT_CST_LOW (tree_offset1
);
1936 offset2
= TREE_INT_CST_LOW (tree_offset2
);
1937 size2
= TREE_INT_CST_LOW (tree_size2
);
1938 align1
= DECL_ALIGN (field1
) % param_align_bits
;
1940 if (offset1
% BITS_PER_UNIT
!= 0)
1943 /* For profitability, the two field references should fit within
1944 a single cache line. */
1945 if (align1
+ offset2
- offset1
+ size2
> param_align_bits
)
1948 /* The two expressions cannot be dependent upon vdefs defined
1950 if (local_mem_dependence (def1
, bb_for_def1
)
1951 || local_mem_dependence (def2
, bb_for_def2
))
1954 /* The conditions are satisfied; hoist the loads from bb1 and bb2 into
1955 bb0. We hoist the first one first so that a cache miss is handled
1956 efficiently regardless of hardware cache-fill policy. */
1957 gsi2
= gsi_for_stmt (def1
);
1958 gsi_move_to_bb_end (&gsi2
, bb0
);
1959 gsi2
= gsi_for_stmt (def2
);
1960 gsi_move_to_bb_end (&gsi2
, bb0
);
1962 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1965 "\nHoisting adjacent loads from %d and %d into %d: \n",
1966 bb_for_def1
->index
, bb_for_def2
->index
, bb0
->index
);
1967 print_gimple_stmt (dump_file
, def1
, 0, TDF_VOPS
|TDF_MEMSYMS
);
1968 print_gimple_stmt (dump_file
, def2
, 0, TDF_VOPS
|TDF_MEMSYMS
);
1973 /* Determine whether we should attempt to hoist adjacent loads out of
1974 diamond patterns in pass_phiopt. Always hoist loads if
1975 -fhoist-adjacent-loads is specified and the target machine has
1976 both a conditional move instruction and a defined cache line size. */
1979 gate_hoist_loads (void)
1981 return (flag_hoist_adjacent_loads
== 1
1982 && PARAM_VALUE (PARAM_L1_CACHE_LINE_SIZE
)
1983 && HAVE_conditional_move
);
1986 /* Always do these optimizations if we have SSA
1987 trees to work on. */
1994 struct gimple_opt_pass pass_phiopt
=
1998 "phiopt", /* name */
1999 gate_phiopt
, /* gate */
2000 tree_ssa_phiopt
, /* execute */
2003 0, /* static_pass_number */
2004 TV_TREE_PHIOPT
, /* tv_id */
2005 PROP_cfg
| PROP_ssa
, /* properties_required */
2006 0, /* properties_provided */
2007 0, /* properties_destroyed */
2008 0, /* todo_flags_start */
2012 | TODO_verify_stmts
/* todo_flags_finish */
2019 return flag_tree_cselim
;
2022 struct gimple_opt_pass pass_cselim
=
2026 "cselim", /* name */
2027 gate_cselim
, /* gate */
2028 tree_ssa_cs_elim
, /* execute */
2031 0, /* static_pass_number */
2032 TV_TREE_PHIOPT
, /* tv_id */
2033 PROP_cfg
| PROP_ssa
, /* properties_required */
2034 0, /* properties_provided */
2035 0, /* properties_destroyed */
2036 0, /* todo_flags_start */
2040 | TODO_verify_stmts
/* todo_flags_finish */