1 /* Optimization of PHI nodes by converting them into straightline code.
2 Copyright (C) 2004-2021 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
24 #include "insn-codes.h"
29 #include "tree-pass.h"
32 #include "optabs-tree.h"
33 #include "insn-config.h"
34 #include "gimple-pretty-print.h"
35 #include "fold-const.h"
36 #include "stor-layout.h"
39 #include "gimple-iterator.h"
40 #include "gimplify-me.h"
45 #include "tree-data-ref.h"
46 #include "tree-scalar-evolution.h"
47 #include "tree-inline.h"
48 #include "case-cfn-macros.h"
50 #include "gimple-fold.h"
51 #include "internal-fn.h"
52 #include "gimple-range.h"
53 #include "gimple-match.h"
56 static unsigned int tree_ssa_phiopt_worker (bool, bool, bool);
57 static bool two_value_replacement (basic_block
, basic_block
, edge
, gphi
*,
59 static bool match_simplify_replacement (basic_block
, basic_block
,
60 edge
, edge
, gphi
*, tree
, tree
, bool);
61 static gphi
*factor_out_conditional_conversion (edge
, edge
, gphi
*, tree
, tree
,
63 static int value_replacement (basic_block
, basic_block
,
64 edge
, edge
, gphi
*, tree
, tree
);
65 static bool minmax_replacement (basic_block
, basic_block
,
66 edge
, edge
, gphi
*, tree
, tree
);
67 static bool spaceship_replacement (basic_block
, basic_block
,
68 edge
, edge
, gphi
*, tree
, tree
);
69 static bool cond_removal_in_builtin_zero_pattern (basic_block
, basic_block
,
72 static bool cond_store_replacement (basic_block
, basic_block
, edge
, edge
,
74 static bool cond_if_else_store_replacement (basic_block
, basic_block
, basic_block
);
75 static hash_set
<tree
> * get_non_trapping ();
76 static void replace_phi_edge_with_variable (basic_block
, edge
, gphi
*, tree
);
77 static void hoist_adjacent_loads (basic_block
, basic_block
,
78 basic_block
, basic_block
);
79 static bool gate_hoist_loads (void);
81 /* This pass tries to transform conditional stores into unconditional
82 ones, enabling further simplifications with the simpler then and else
83 blocks. In particular it replaces this:
86 if (cond) goto bb2; else goto bb1;
94 if (cond) goto bb1; else goto bb2;
98 condtmp = PHI <RHS, condtmp'>
101 This transformation can only be done under several constraints,
102 documented below. It also replaces:
105 if (cond) goto bb2; else goto bb1;
116 if (cond) goto bb3; else goto bb1;
119 condtmp = PHI <RHS1, RHS2>
123 tree_ssa_cs_elim (void)
126 /* ??? We are not interested in loop related info, but the following
127 will create it, ICEing as we didn't init loops with pre-headers.
128 An interfacing issue of find_data_references_in_bb. */
129 loop_optimizer_init (LOOPS_NORMAL
);
131 todo
= tree_ssa_phiopt_worker (true, false, false);
133 loop_optimizer_finalize ();
137 /* Return the singleton PHI in the SEQ of PHIs for edges E0 and E1. */
140 single_non_singleton_phi_for_edges (gimple_seq seq
, edge e0
, edge e1
)
142 gimple_stmt_iterator i
;
144 if (gimple_seq_singleton_p (seq
))
145 return as_a
<gphi
*> (gsi_stmt (gsi_start (seq
)));
146 for (i
= gsi_start (seq
); !gsi_end_p (i
); gsi_next (&i
))
148 gphi
*p
= as_a
<gphi
*> (gsi_stmt (i
));
149 /* If the PHI arguments are equal then we can skip this PHI. */
150 if (operand_equal_for_phi_arg_p (gimple_phi_arg_def (p
, e0
->dest_idx
),
151 gimple_phi_arg_def (p
, e1
->dest_idx
)))
154 /* If we already have a PHI that has the two edge arguments are
155 different, then return it is not a singleton for these PHIs. */
164 /* The core routine of conditional store replacement and normal
165 phi optimizations. Both share much of the infrastructure in how
166 to match applicable basic block patterns. DO_STORE_ELIM is true
167 when we want to do conditional store replacement, false otherwise.
168 DO_HOIST_LOADS is true when we want to hoist adjacent loads out
169 of diamond control flow patterns, false otherwise. */
171 tree_ssa_phiopt_worker (bool do_store_elim
, bool do_hoist_loads
, bool early_p
)
174 basic_block
*bb_order
;
176 bool cfgchanged
= false;
177 hash_set
<tree
> *nontrap
= 0;
179 calculate_dominance_info (CDI_DOMINATORS
);
182 /* Calculate the set of non-trapping memory accesses. */
183 nontrap
= get_non_trapping ();
185 /* Search every basic block for COND_EXPR we may be able to optimize.
187 We walk the blocks in order that guarantees that a block with
188 a single predecessor is processed before the predecessor.
189 This ensures that we collapse inner ifs before visiting the
190 outer ones, and also that we do not try to visit a removed
192 bb_order
= single_pred_before_succ_order ();
193 n
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
;
195 for (i
= 0; i
< n
; i
++)
199 basic_block bb1
, bb2
;
205 cond_stmt
= last_stmt (bb
);
206 /* Check to see if the last statement is a GIMPLE_COND. */
208 || gimple_code (cond_stmt
) != GIMPLE_COND
)
211 e1
= EDGE_SUCC (bb
, 0);
213 e2
= EDGE_SUCC (bb
, 1);
216 /* We cannot do the optimization on abnormal edges. */
217 if ((e1
->flags
& EDGE_ABNORMAL
) != 0
218 || (e2
->flags
& EDGE_ABNORMAL
) != 0)
221 /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
222 if (EDGE_COUNT (bb1
->succs
) == 0
224 || EDGE_COUNT (bb2
->succs
) == 0)
227 /* Find the bb which is the fall through to the other. */
228 if (EDGE_SUCC (bb1
, 0)->dest
== bb2
)
230 else if (EDGE_SUCC (bb2
, 0)->dest
== bb1
)
232 std::swap (bb1
, bb2
);
235 else if (do_store_elim
236 && EDGE_SUCC (bb1
, 0)->dest
== EDGE_SUCC (bb2
, 0)->dest
)
238 basic_block bb3
= EDGE_SUCC (bb1
, 0)->dest
;
240 if (!single_succ_p (bb1
)
241 || (EDGE_SUCC (bb1
, 0)->flags
& EDGE_FALLTHRU
) == 0
242 || !single_succ_p (bb2
)
243 || (EDGE_SUCC (bb2
, 0)->flags
& EDGE_FALLTHRU
) == 0
244 || EDGE_COUNT (bb3
->preds
) != 2)
246 if (cond_if_else_store_replacement (bb1
, bb2
, bb3
))
250 else if (do_hoist_loads
251 && EDGE_SUCC (bb1
, 0)->dest
== EDGE_SUCC (bb2
, 0)->dest
)
253 basic_block bb3
= EDGE_SUCC (bb1
, 0)->dest
;
255 if (!FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt
)))
256 && single_succ_p (bb1
)
257 && single_succ_p (bb2
)
258 && single_pred_p (bb1
)
259 && single_pred_p (bb2
)
260 && EDGE_COUNT (bb
->succs
) == 2
261 && EDGE_COUNT (bb3
->preds
) == 2
262 /* If one edge or the other is dominant, a conditional move
263 is likely to perform worse than the well-predicted branch. */
264 && !predictable_edge_p (EDGE_SUCC (bb
, 0))
265 && !predictable_edge_p (EDGE_SUCC (bb
, 1)))
266 hoist_adjacent_loads (bb
, bb1
, bb2
, bb3
);
272 e1
= EDGE_SUCC (bb1
, 0);
274 /* Make sure that bb1 is just a fall through. */
275 if (!single_succ_p (bb1
)
276 || (e1
->flags
& EDGE_FALLTHRU
) == 0)
279 /* Also make sure that bb1 only have one predecessor and that it
281 if (!single_pred_p (bb1
)
282 || single_pred (bb1
) != bb
)
287 /* bb1 is the middle block, bb2 the join block, bb the split block,
288 e1 the fallthrough edge from bb1 to bb2. We can't do the
289 optimization if the join block has more than two predecessors. */
290 if (EDGE_COUNT (bb2
->preds
) > 2)
292 if (cond_store_replacement (bb1
, bb2
, e1
, e2
, nontrap
))
297 gimple_seq phis
= phi_nodes (bb2
);
298 gimple_stmt_iterator gsi
;
299 bool candorest
= true;
301 /* Value replacement can work with more than one PHI
302 so try that first. */
304 for (gsi
= gsi_start (phis
); !gsi_end_p (gsi
); gsi_next (&gsi
))
306 phi
= as_a
<gphi
*> (gsi_stmt (gsi
));
307 arg0
= gimple_phi_arg_def (phi
, e1
->dest_idx
);
308 arg1
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
309 if (value_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
) == 2)
320 phi
= single_non_singleton_phi_for_edges (phis
, e1
, e2
);
324 arg0
= gimple_phi_arg_def (phi
, e1
->dest_idx
);
325 arg1
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
327 /* Something is wrong if we cannot find the arguments in the PHI
329 gcc_assert (arg0
!= NULL_TREE
&& arg1
!= NULL_TREE
);
331 gphi
*newphi
= factor_out_conditional_conversion (e1
, e2
, phi
,
337 /* factor_out_conditional_conversion may create a new PHI in
338 BB2 and eliminate an existing PHI in BB2. Recompute values
339 that may be affected by that change. */
340 arg0
= gimple_phi_arg_def (phi
, e1
->dest_idx
);
341 arg1
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
342 gcc_assert (arg0
!= NULL_TREE
&& arg1
!= NULL_TREE
);
345 /* Do the replacement of conditional if it can be done. */
346 if (!early_p
&& two_value_replacement (bb
, bb1
, e2
, phi
, arg0
, arg1
))
348 else if (match_simplify_replacement (bb
, bb1
, e1
, e2
, phi
,
353 && cond_removal_in_builtin_zero_pattern (bb
, bb1
, e1
, e2
,
356 else if (minmax_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
))
358 else if (spaceship_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
))
367 /* If the CFG has changed, we should cleanup the CFG. */
368 if (cfgchanged
&& do_store_elim
)
370 /* In cond-store replacement we have added some loads on edges
371 and new VOPS (as we moved the store, and created a load). */
372 gsi_commit_edge_inserts ();
373 return TODO_cleanup_cfg
| TODO_update_ssa_only_virtuals
;
376 return TODO_cleanup_cfg
;
380 /* Replace PHI node element whose edge is E in block BB with variable NEW.
381 Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
382 is known to have two edges, one of which must reach BB). */
385 replace_phi_edge_with_variable (basic_block cond_block
,
386 edge e
, gphi
*phi
, tree new_tree
)
388 basic_block bb
= gimple_bb (phi
);
389 basic_block block_to_remove
;
390 gimple_stmt_iterator gsi
;
391 tree phi_result
= PHI_RESULT (phi
);
393 /* Duplicate range info if they are the only things setting the target PHI.
394 This is needed as later on, the new_tree will be replacing
395 The assignement of the PHI.
406 And _4 gets propagated into the use of a_3 and losing the range info.
407 This can't be done for more than 2 incoming edges as the propagation
409 The new_tree needs to be defined in the same basic block as the conditional. */
410 if (TREE_CODE (new_tree
) == SSA_NAME
411 && EDGE_COUNT (gimple_bb (phi
)->preds
) == 2
412 && INTEGRAL_TYPE_P (TREE_TYPE (phi_result
))
413 && !SSA_NAME_RANGE_INFO (new_tree
)
414 && SSA_NAME_RANGE_INFO (phi_result
)
415 && gimple_bb (SSA_NAME_DEF_STMT (new_tree
)) == cond_block
416 && dbg_cnt (phiopt_edge_range
))
417 duplicate_ssa_name_range_info (new_tree
,
418 SSA_NAME_RANGE_TYPE (phi_result
),
419 SSA_NAME_RANGE_INFO (phi_result
));
421 /* Change the PHI argument to new. */
422 SET_USE (PHI_ARG_DEF_PTR (phi
, e
->dest_idx
), new_tree
);
424 /* Remove the empty basic block. */
425 if (EDGE_SUCC (cond_block
, 0)->dest
== bb
)
427 EDGE_SUCC (cond_block
, 0)->flags
|= EDGE_FALLTHRU
;
428 EDGE_SUCC (cond_block
, 0)->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
429 EDGE_SUCC (cond_block
, 0)->probability
= profile_probability::always ();
431 block_to_remove
= EDGE_SUCC (cond_block
, 1)->dest
;
435 EDGE_SUCC (cond_block
, 1)->flags
|= EDGE_FALLTHRU
;
436 EDGE_SUCC (cond_block
, 1)->flags
437 &= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
438 EDGE_SUCC (cond_block
, 1)->probability
= profile_probability::always ();
440 block_to_remove
= EDGE_SUCC (cond_block
, 0)->dest
;
442 delete_basic_block (block_to_remove
);
444 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
445 gsi
= gsi_last_bb (cond_block
);
446 gsi_remove (&gsi
, true);
448 statistics_counter_event (cfun
, "Replace PHI with variable", 1);
450 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
452 "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
457 /* PR66726: Factor conversion out of COND_EXPR. If the arguments of the PHI
458 stmt are CONVERT_STMT, factor out the conversion and perform the conversion
459 to the result of PHI stmt. COND_STMT is the controlling predicate.
460 Return the newly-created PHI, if any. */
463 factor_out_conditional_conversion (edge e0
, edge e1
, gphi
*phi
,
464 tree arg0
, tree arg1
, gimple
*cond_stmt
)
466 gimple
*arg0_def_stmt
= NULL
, *arg1_def_stmt
= NULL
, *new_stmt
;
467 tree new_arg0
= NULL_TREE
, new_arg1
= NULL_TREE
;
470 gimple_stmt_iterator gsi
, gsi_for_def
;
471 location_t locus
= gimple_location (phi
);
472 enum tree_code convert_code
;
474 /* Handle only PHI statements with two arguments. TODO: If all
475 other arguments to PHI are INTEGER_CST or if their defining
476 statement have the same unary operation, we can handle more
477 than two arguments too. */
478 if (gimple_phi_num_args (phi
) != 2)
481 /* First canonicalize to simplify tests. */
482 if (TREE_CODE (arg0
) != SSA_NAME
)
484 std::swap (arg0
, arg1
);
488 if (TREE_CODE (arg0
) != SSA_NAME
489 || (TREE_CODE (arg1
) != SSA_NAME
490 && TREE_CODE (arg1
) != INTEGER_CST
))
493 /* Check if arg0 is an SSA_NAME and the stmt which defines arg0 is
495 arg0_def_stmt
= SSA_NAME_DEF_STMT (arg0
);
496 if (!gimple_assign_cast_p (arg0_def_stmt
))
499 /* Use the RHS as new_arg0. */
500 convert_code
= gimple_assign_rhs_code (arg0_def_stmt
);
501 new_arg0
= gimple_assign_rhs1 (arg0_def_stmt
);
502 if (convert_code
== VIEW_CONVERT_EXPR
)
504 new_arg0
= TREE_OPERAND (new_arg0
, 0);
505 if (!is_gimple_reg_type (TREE_TYPE (new_arg0
)))
508 if (TREE_CODE (new_arg0
) == SSA_NAME
509 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_arg0
))
512 if (TREE_CODE (arg1
) == SSA_NAME
)
514 /* Check if arg1 is an SSA_NAME and the stmt which defines arg1
516 arg1_def_stmt
= SSA_NAME_DEF_STMT (arg1
);
517 if (!is_gimple_assign (arg1_def_stmt
)
518 || gimple_assign_rhs_code (arg1_def_stmt
) != convert_code
)
521 /* Either arg1_def_stmt or arg0_def_stmt should be conditional. */
522 if (dominated_by_p (CDI_DOMINATORS
, gimple_bb (phi
), gimple_bb (arg0_def_stmt
))
523 && dominated_by_p (CDI_DOMINATORS
,
524 gimple_bb (phi
), gimple_bb (arg1_def_stmt
)))
527 /* Use the RHS as new_arg1. */
528 new_arg1
= gimple_assign_rhs1 (arg1_def_stmt
);
529 if (convert_code
== VIEW_CONVERT_EXPR
)
530 new_arg1
= TREE_OPERAND (new_arg1
, 0);
531 if (TREE_CODE (new_arg1
) == SSA_NAME
532 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_arg1
))
537 /* arg0_def_stmt should be conditional. */
538 if (dominated_by_p (CDI_DOMINATORS
, gimple_bb (phi
), gimple_bb (arg0_def_stmt
)))
540 /* If arg1 is an INTEGER_CST, fold it to new type. */
541 if (INTEGRAL_TYPE_P (TREE_TYPE (new_arg0
))
542 && int_fits_type_p (arg1
, TREE_TYPE (new_arg0
)))
544 if (gimple_assign_cast_p (arg0_def_stmt
))
546 /* For the INTEGER_CST case, we are just moving the
547 conversion from one place to another, which can often
548 hurt as the conversion moves further away from the
549 statement that computes the value. So, perform this
550 only if new_arg0 is an operand of COND_STMT, or
551 if arg0_def_stmt is the only non-debug stmt in
552 its basic block, because then it is possible this
553 could enable further optimizations (minmax replacement
554 etc.). See PR71016. */
555 if (new_arg0
!= gimple_cond_lhs (cond_stmt
)
556 && new_arg0
!= gimple_cond_rhs (cond_stmt
)
557 && gimple_bb (arg0_def_stmt
) == e0
->src
)
559 gsi
= gsi_for_stmt (arg0_def_stmt
);
560 gsi_prev_nondebug (&gsi
);
561 if (!gsi_end_p (gsi
))
564 = dyn_cast
<gassign
*> (gsi_stmt (gsi
)))
566 tree lhs
= gimple_assign_lhs (assign
);
567 enum tree_code ass_code
568 = gimple_assign_rhs_code (assign
);
569 if (ass_code
!= MAX_EXPR
&& ass_code
!= MIN_EXPR
)
571 if (lhs
!= gimple_assign_rhs1 (arg0_def_stmt
))
573 gsi_prev_nondebug (&gsi
);
574 if (!gsi_end_p (gsi
))
580 gsi
= gsi_for_stmt (arg0_def_stmt
);
581 gsi_next_nondebug (&gsi
);
582 if (!gsi_end_p (gsi
))
585 new_arg1
= fold_convert (TREE_TYPE (new_arg0
), arg1
);
594 /* If arg0/arg1 have > 1 use, then this transformation actually increases
595 the number of expressions evaluated at runtime. */
596 if (!has_single_use (arg0
)
597 || (arg1_def_stmt
&& !has_single_use (arg1
)))
600 /* If types of new_arg0 and new_arg1 are different bailout. */
601 if (!types_compatible_p (TREE_TYPE (new_arg0
), TREE_TYPE (new_arg1
)))
604 /* Create a new PHI stmt. */
605 result
= PHI_RESULT (phi
);
606 temp
= make_ssa_name (TREE_TYPE (new_arg0
), NULL
);
607 newphi
= create_phi_node (temp
, gimple_bb (phi
));
609 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
611 fprintf (dump_file
, "PHI ");
612 print_generic_expr (dump_file
, gimple_phi_result (phi
));
614 " changed to factor conversion out from COND_EXPR.\n");
615 fprintf (dump_file
, "New stmt with CAST that defines ");
616 print_generic_expr (dump_file
, result
);
617 fprintf (dump_file
, ".\n");
620 /* Remove the old cast(s) that has single use. */
621 gsi_for_def
= gsi_for_stmt (arg0_def_stmt
);
622 gsi_remove (&gsi_for_def
, true);
623 release_defs (arg0_def_stmt
);
627 gsi_for_def
= gsi_for_stmt (arg1_def_stmt
);
628 gsi_remove (&gsi_for_def
, true);
629 release_defs (arg1_def_stmt
);
632 add_phi_arg (newphi
, new_arg0
, e0
, locus
);
633 add_phi_arg (newphi
, new_arg1
, e1
, locus
);
635 /* Create the conversion stmt and insert it. */
636 if (convert_code
== VIEW_CONVERT_EXPR
)
638 temp
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (result
), temp
);
639 new_stmt
= gimple_build_assign (result
, temp
);
642 new_stmt
= gimple_build_assign (result
, convert_code
, temp
);
643 gsi
= gsi_after_labels (gimple_bb (phi
));
644 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
646 /* Remove the original PHI stmt. */
647 gsi
= gsi_for_stmt (phi
);
648 gsi_remove (&gsi
, true);
650 statistics_counter_event (cfun
, "factored out cast", 1);
656 # x_5 in range [cst1, cst2] where cst2 = cst1 + 1
657 if (x_5 op cstN) # where op is == or != and N is 1 or 2
663 # r_6 = PHI<cst3(2), cst4(3)> # where cst3 == cst4 + 1 or cst4 == cst3 + 1
665 to r_6 = x_5 + (min (cst3, cst4) - cst1) or
666 r_6 = (min (cst3, cst4) + cst1) - x_5 depending on op, N and which
667 of cst3 and cst4 is smaller. */
670 two_value_replacement (basic_block cond_bb
, basic_block middle_bb
,
671 edge e1
, gphi
*phi
, tree arg0
, tree arg1
)
673 /* Only look for adjacent integer constants. */
674 if (!INTEGRAL_TYPE_P (TREE_TYPE (arg0
))
675 || !INTEGRAL_TYPE_P (TREE_TYPE (arg1
))
676 || TREE_CODE (arg0
) != INTEGER_CST
677 || TREE_CODE (arg1
) != INTEGER_CST
678 || (tree_int_cst_lt (arg0
, arg1
)
679 ? wi::to_widest (arg0
) + 1 != wi::to_widest (arg1
)
680 : wi::to_widest (arg1
) + 1 != wi::to_widest (arg0
)))
683 if (!empty_block_p (middle_bb
))
686 gimple
*stmt
= last_stmt (cond_bb
);
687 tree lhs
= gimple_cond_lhs (stmt
);
688 tree rhs
= gimple_cond_rhs (stmt
);
690 if (TREE_CODE (lhs
) != SSA_NAME
691 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
692 || TREE_CODE (rhs
) != INTEGER_CST
)
695 switch (gimple_cond_code (stmt
))
704 /* Defer boolean x ? 0 : {1,-1} or x ? {1,-1} : 0 to
705 match_simplify_replacement. */
706 if (TREE_CODE (TREE_TYPE (lhs
)) == BOOLEAN_TYPE
707 && (integer_zerop (arg0
)
708 || integer_zerop (arg1
)
709 || TREE_CODE (TREE_TYPE (arg0
)) == BOOLEAN_TYPE
710 || (TYPE_PRECISION (TREE_TYPE (arg0
))
711 <= TYPE_PRECISION (TREE_TYPE (lhs
)))))
716 get_range_query (cfun
)->range_of_expr (r
, lhs
);
718 if (r
.kind () == VR_RANGE
)
720 min
= r
.lower_bound ();
721 max
= r
.upper_bound ();
725 int prec
= TYPE_PRECISION (TREE_TYPE (lhs
));
726 signop sgn
= TYPE_SIGN (TREE_TYPE (lhs
));
727 min
= wi::min_value (prec
, sgn
);
728 max
= wi::max_value (prec
, sgn
);
731 || (wi::to_wide (rhs
) != min
732 && wi::to_wide (rhs
) != max
))
735 /* We need to know which is the true edge and which is the false
736 edge so that we know when to invert the condition below. */
737 edge true_edge
, false_edge
;
738 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
739 if ((gimple_cond_code (stmt
) == EQ_EXPR
)
740 ^ (wi::to_wide (rhs
) == max
)
741 ^ (e1
== false_edge
))
742 std::swap (arg0
, arg1
);
745 if (TYPE_PRECISION (TREE_TYPE (lhs
)) == TYPE_PRECISION (TREE_TYPE (arg0
)))
747 /* Avoid performing the arithmetics in bool type which has different
748 semantics, otherwise prefer unsigned types from the two with
749 the same precision. */
750 if (TREE_CODE (TREE_TYPE (arg0
)) == BOOLEAN_TYPE
751 || !TYPE_UNSIGNED (TREE_TYPE (arg0
)))
752 type
= TREE_TYPE (lhs
);
754 type
= TREE_TYPE (arg0
);
756 else if (TYPE_PRECISION (TREE_TYPE (lhs
)) > TYPE_PRECISION (TREE_TYPE (arg0
)))
757 type
= TREE_TYPE (lhs
);
759 type
= TREE_TYPE (arg0
);
761 min
= wide_int::from (min
, TYPE_PRECISION (type
),
762 TYPE_SIGN (TREE_TYPE (lhs
)));
763 wide_int a
= wide_int::from (wi::to_wide (arg0
), TYPE_PRECISION (type
),
764 TYPE_SIGN (TREE_TYPE (arg0
)));
766 wi::overflow_type ovf
;
767 if (tree_int_cst_lt (arg0
, arg1
))
771 if (!TYPE_UNSIGNED (type
))
773 /* lhs is known to be in range [min, min+1] and we want to add a
774 to it. Check if that operation can overflow for those 2 values
775 and if yes, force unsigned type. */
776 wi::add (min
+ (wi::neg_p (a
) ? 0 : 1), a
, SIGNED
, &ovf
);
778 type
= unsigned_type_for (type
);
785 if (!TYPE_UNSIGNED (type
))
787 /* lhs is known to be in range [min, min+1] and we want to subtract
788 it from a. Check if that operation can overflow for those 2
789 values and if yes, force unsigned type. */
790 wi::sub (a
, min
+ (wi::neg_p (min
) ? 0 : 1), SIGNED
, &ovf
);
792 type
= unsigned_type_for (type
);
796 tree arg
= wide_int_to_tree (type
, a
);
797 gimple_seq stmts
= NULL
;
798 lhs
= gimple_convert (&stmts
, type
, lhs
);
800 if (code
== PLUS_EXPR
)
801 new_rhs
= gimple_build (&stmts
, PLUS_EXPR
, type
, lhs
, arg
);
803 new_rhs
= gimple_build (&stmts
, MINUS_EXPR
, type
, arg
, lhs
);
804 new_rhs
= gimple_convert (&stmts
, TREE_TYPE (arg0
), new_rhs
);
805 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
806 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
808 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, new_rhs
);
810 /* Note that we optimized this PHI. */
814 /* Return TRUE if SEQ/OP pair should be allowed during early phiopt.
815 Currently this is to allow MIN/MAX and ABS/NEGATE and constants. */
817 phiopt_early_allow (gimple_seq
&seq
, gimple_match_op
&op
)
819 /* Don't allow functions. */
820 if (!op
.code
.is_tree_code ())
822 tree_code code
= (tree_code
)op
.code
;
824 /* For non-empty sequence, only allow one statement. */
825 if (!gimple_seq_empty_p (seq
))
827 /* Check to make sure op was already a SSA_NAME. */
828 if (code
!= SSA_NAME
)
830 if (!gimple_seq_singleton_p (seq
))
832 gimple
*stmt
= gimple_seq_first_stmt (seq
);
833 /* Only allow assignments. */
834 if (!is_gimple_assign (stmt
))
836 if (gimple_assign_lhs (stmt
) != op
.ops
[0])
838 code
= gimple_assign_rhs_code (stmt
);
860 /* gimple_simplify_phiopt is like gimple_simplify but designed for PHIOPT.
861 Return NULL if nothing can be simplified or the resulting simplified value
862 with parts pushed if EARLY_P was true. Also rejects non allowed tree code
864 Takes the comparison from COMP_STMT and two args, ARG0 and ARG1 and tries
865 to simplify CMP ? ARG0 : ARG1.
866 Also try to simplify (!CMP) ? ARG1 : ARG0 if the non-inverse failed. */
868 gimple_simplify_phiopt (bool early_p
, tree type
, gimple
*comp_stmt
,
869 tree arg0
, tree arg1
,
873 gimple_seq seq1
= NULL
;
874 enum tree_code comp_code
= gimple_cond_code (comp_stmt
);
875 location_t loc
= gimple_location (comp_stmt
);
876 tree cmp0
= gimple_cond_lhs (comp_stmt
);
877 tree cmp1
= gimple_cond_rhs (comp_stmt
);
878 /* To handle special cases like floating point comparison, it is easier and
879 less error-prone to build a tree and gimplify it on the fly though it is
881 Don't use fold_build2 here as that might create (bool)a instead of just
883 tree cond
= build2_loc (loc
, comp_code
, boolean_type_node
,
885 gimple_match_op
op (gimple_match_cond::UNCOND
,
886 COND_EXPR
, type
, cond
, arg0
, arg1
);
888 if (op
.resimplify (&seq1
, follow_all_ssa_edges
))
890 /* Early we want only to allow some generated tree codes. */
892 || phiopt_early_allow (seq1
, op
))
894 result
= maybe_push_res_to_seq (&op
, &seq1
);
897 gimple_seq_add_seq_without_update (seq
, seq1
);
902 gimple_seq_discard (seq1
);
905 /* Try the inverted comparison, that is !COMP ? ARG1 : ARG0. */
906 comp_code
= invert_tree_comparison (comp_code
, HONOR_NANS (cmp0
));
908 if (comp_code
== ERROR_MARK
)
911 cond
= build2_loc (loc
,
912 comp_code
, boolean_type_node
,
914 gimple_match_op
op1 (gimple_match_cond::UNCOND
,
915 COND_EXPR
, type
, cond
, arg1
, arg0
);
917 if (op1
.resimplify (&seq1
, follow_all_ssa_edges
))
919 /* Early we want only to allow some generated tree codes. */
921 || phiopt_early_allow (seq1
, op1
))
923 result
= maybe_push_res_to_seq (&op1
, &seq1
);
926 gimple_seq_add_seq_without_update (seq
, seq1
);
931 gimple_seq_discard (seq1
);
936 /* The function match_simplify_replacement does the main work of doing the
937 replacement using match and simplify. Return true if the replacement is done.
938 Otherwise return false.
939 BB is the basic block where the replacement is going to be done on. ARG0
940 is argument 0 from PHI. Likewise for ARG1. */
943 match_simplify_replacement (basic_block cond_bb
, basic_block middle_bb
,
944 edge e0
, edge e1
, gphi
*phi
,
945 tree arg0
, tree arg1
, bool early_p
)
948 gimple_stmt_iterator gsi
;
949 edge true_edge
, false_edge
;
950 gimple_seq seq
= NULL
;
952 gimple
*stmt_to_move
= NULL
;
954 /* Special case A ? B : B as this will always simplify to B. */
955 if (operand_equal_for_phi_arg_p (arg0
, arg1
))
958 /* If the basic block only has a cheap preparation statement,
959 allow it and move it once the transformation is done. */
960 if (!empty_block_p (middle_bb
))
962 stmt_to_move
= last_and_only_stmt (middle_bb
);
966 if (gimple_vuse (stmt_to_move
))
969 if (gimple_could_trap_p (stmt_to_move
)
970 || gimple_has_side_effects (stmt_to_move
))
973 if (gimple_uses_undefined_value_p (stmt_to_move
))
976 /* Allow assignments and not no calls.
977 As const calls don't match any of the above, yet they could
978 still have some side-effects - they could contain
979 gimple_could_trap_p statements, like floating point
980 exceptions or integer division by zero. See PR70586.
981 FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
982 should handle this. */
983 if (!is_gimple_assign (stmt_to_move
))
986 tree lhs
= gimple_assign_lhs (stmt_to_move
);
990 /* Allow only a statement which feeds into the phi. */
991 if (!lhs
|| TREE_CODE (lhs
) != SSA_NAME
992 || !single_imm_use (lhs
, &use_p
, &use_stmt
)
997 /* At this point we know we have a GIMPLE_COND with two successors.
998 One successor is BB, the other successor is an empty block which
999 falls through into BB.
1001 There is a single PHI node at the join point (BB).
1003 So, given the condition COND, and the two PHI arguments, match and simplify
1004 can happen on (COND) ? arg0 : arg1. */
1006 stmt
= last_stmt (cond_bb
);
1008 /* We need to know which is the true edge and which is the false
1009 edge so that we know when to invert the condition below. */
1010 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
1011 if (e1
== true_edge
|| e0
== false_edge
)
1012 std::swap (arg0
, arg1
);
1014 tree type
= TREE_TYPE (gimple_phi_result (phi
));
1015 result
= gimple_simplify_phiopt (early_p
, type
, stmt
,
1021 gsi
= gsi_last_bb (cond_bb
);
1022 /* Insert the sequence generated from gimple_simplify_phiopt. */
1024 gsi_insert_seq_before (&gsi
, seq
, GSI_CONTINUE_LINKING
);
1026 /* If there was a statement to move and the result of the statement
1027 is going to be used, move it to right before the original
1030 && (gimple_assign_lhs (stmt_to_move
) == result
1031 || !has_single_use (gimple_assign_lhs (stmt_to_move
))))
1033 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1035 fprintf (dump_file
, "statement un-sinked:\n");
1036 print_gimple_stmt (dump_file
, stmt_to_move
, 0,
1037 TDF_VOPS
|TDF_MEMSYMS
);
1039 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt_to_move
);
1040 gsi_move_before (&gsi1
, &gsi
);
1041 reset_flow_sensitive_info (gimple_assign_lhs (stmt_to_move
));
1044 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, result
);
1046 /* Add Statistic here even though replace_phi_edge_with_variable already
1047 does it as we want to be able to count when match-simplify happens vs
1049 statistics_counter_event (cfun
, "match-simplify PHI replacement", 1);
1051 /* Note that we optimized this PHI. */
1055 /* Update *ARG which is defined in STMT so that it contains the
1056 computed value if that seems profitable. Return true if the
1057 statement is made dead by that rewriting. */
1060 jump_function_from_stmt (tree
*arg
, gimple
*stmt
)
1062 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1063 if (code
== ADDR_EXPR
)
1065 /* For arg = &p->i transform it to p, if possible. */
1066 tree rhs1
= gimple_assign_rhs1 (stmt
);
1068 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs1
, 0),
1071 && TREE_CODE (tem
) == MEM_REF
1072 && known_eq (mem_ref_offset (tem
) + offset
, 0))
1074 *arg
= TREE_OPERAND (tem
, 0);
1078 /* TODO: Much like IPA-CP jump-functions we want to handle constant
1079 additions symbolically here, and we'd need to update the comparison
1080 code that compares the arg + cst tuples in our caller. For now the
1081 code above exactly handles the VEC_BASE pattern from vec.h. */
1085 /* RHS is a source argument in a BIT_AND_EXPR which feeds a conditional
1086 of the form SSA_NAME NE 0.
1088 If RHS is fed by a simple EQ_EXPR comparison of two values, see if
1089 the two input values of the EQ_EXPR match arg0 and arg1.
1091 If so update *code and return TRUE. Otherwise return FALSE. */
1094 rhs_is_fed_for_value_replacement (const_tree arg0
, const_tree arg1
,
1095 enum tree_code
*code
, const_tree rhs
)
1097 /* Obviously if RHS is not an SSA_NAME, we can't look at the defining
1099 if (TREE_CODE (rhs
) == SSA_NAME
)
1101 gimple
*def1
= SSA_NAME_DEF_STMT (rhs
);
1103 /* Verify the defining statement has an EQ_EXPR on the RHS. */
1104 if (is_gimple_assign (def1
) && gimple_assign_rhs_code (def1
) == EQ_EXPR
)
1106 /* Finally verify the source operands of the EQ_EXPR are equal
1107 to arg0 and arg1. */
1108 tree op0
= gimple_assign_rhs1 (def1
);
1109 tree op1
= gimple_assign_rhs2 (def1
);
1110 if ((operand_equal_for_phi_arg_p (arg0
, op0
)
1111 && operand_equal_for_phi_arg_p (arg1
, op1
))
1112 || (operand_equal_for_phi_arg_p (arg0
, op1
)
1113 && operand_equal_for_phi_arg_p (arg1
, op0
)))
1115 /* We will perform the optimization. */
1116 *code
= gimple_assign_rhs_code (def1
);
1124 /* Return TRUE if arg0/arg1 are equal to the rhs/lhs or lhs/rhs of COND.
1126 Also return TRUE if arg0/arg1 are equal to the source arguments of a
1127 an EQ comparison feeding a BIT_AND_EXPR which feeds COND.
1129 Return FALSE otherwise. */
1132 operand_equal_for_value_replacement (const_tree arg0
, const_tree arg1
,
1133 enum tree_code
*code
, gimple
*cond
)
1136 tree lhs
= gimple_cond_lhs (cond
);
1137 tree rhs
= gimple_cond_rhs (cond
);
1139 if ((operand_equal_for_phi_arg_p (arg0
, lhs
)
1140 && operand_equal_for_phi_arg_p (arg1
, rhs
))
1141 || (operand_equal_for_phi_arg_p (arg1
, lhs
)
1142 && operand_equal_for_phi_arg_p (arg0
, rhs
)))
1145 /* Now handle more complex case where we have an EQ comparison
1146 which feeds a BIT_AND_EXPR which feeds COND.
1148 First verify that COND is of the form SSA_NAME NE 0. */
1149 if (*code
!= NE_EXPR
|| !integer_zerop (rhs
)
1150 || TREE_CODE (lhs
) != SSA_NAME
)
1153 /* Now ensure that SSA_NAME is set by a BIT_AND_EXPR. */
1154 def
= SSA_NAME_DEF_STMT (lhs
);
1155 if (!is_gimple_assign (def
) || gimple_assign_rhs_code (def
) != BIT_AND_EXPR
)
1158 /* Now verify arg0/arg1 correspond to the source arguments of an
1159 EQ comparison feeding the BIT_AND_EXPR. */
1161 tree tmp
= gimple_assign_rhs1 (def
);
1162 if (rhs_is_fed_for_value_replacement (arg0
, arg1
, code
, tmp
))
1165 tmp
= gimple_assign_rhs2 (def
);
1166 if (rhs_is_fed_for_value_replacement (arg0
, arg1
, code
, tmp
))
1172 /* Returns true if ARG is a neutral element for operation CODE
1173 on the RIGHT side. */
1176 neutral_element_p (tree_code code
, tree arg
, bool right
)
1183 return integer_zerop (arg
);
1190 case POINTER_PLUS_EXPR
:
1191 return right
&& integer_zerop (arg
);
1194 return integer_onep (arg
);
1196 case TRUNC_DIV_EXPR
:
1198 case FLOOR_DIV_EXPR
:
1199 case ROUND_DIV_EXPR
:
1200 case EXACT_DIV_EXPR
:
1201 return right
&& integer_onep (arg
);
1204 return integer_all_onesp (arg
);
1211 /* Returns true if ARG is an absorbing element for operation CODE. */
1214 absorbing_element_p (tree_code code
, tree arg
, bool right
, tree rval
)
1219 return integer_all_onesp (arg
);
1223 return integer_zerop (arg
);
1229 return !right
&& integer_zerop (arg
);
1231 case TRUNC_DIV_EXPR
:
1233 case FLOOR_DIV_EXPR
:
1234 case ROUND_DIV_EXPR
:
1235 case EXACT_DIV_EXPR
:
1236 case TRUNC_MOD_EXPR
:
1238 case FLOOR_MOD_EXPR
:
1239 case ROUND_MOD_EXPR
:
1241 && integer_zerop (arg
)
1242 && tree_single_nonzero_warnv_p (rval
, NULL
));
1249 /* The function value_replacement does the main work of doing the value
1250 replacement. Return non-zero if the replacement is done. Otherwise return
1251 0. If we remove the middle basic block, return 2.
1252 BB is the basic block where the replacement is going to be done on. ARG0
1253 is argument 0 from the PHI. Likewise for ARG1. */
1256 value_replacement (basic_block cond_bb
, basic_block middle_bb
,
1257 edge e0
, edge e1
, gphi
*phi
, tree arg0
, tree arg1
)
1259 gimple_stmt_iterator gsi
;
1261 edge true_edge
, false_edge
;
1262 enum tree_code code
;
1263 bool empty_or_with_defined_p
= true;
1265 /* If the type says honor signed zeros we cannot do this
1267 if (HONOR_SIGNED_ZEROS (arg1
))
1270 /* If there is a statement in MIDDLE_BB that defines one of the PHI
1271 arguments, then adjust arg0 or arg1. */
1272 gsi
= gsi_start_nondebug_after_labels_bb (middle_bb
);
1273 while (!gsi_end_p (gsi
))
1275 gimple
*stmt
= gsi_stmt (gsi
);
1277 gsi_next_nondebug (&gsi
);
1278 if (!is_gimple_assign (stmt
))
1280 if (gimple_code (stmt
) != GIMPLE_PREDICT
1281 && gimple_code (stmt
) != GIMPLE_NOP
)
1282 empty_or_with_defined_p
= false;
1285 /* Now try to adjust arg0 or arg1 according to the computation
1286 in the statement. */
1287 lhs
= gimple_assign_lhs (stmt
);
1289 && jump_function_from_stmt (&arg0
, stmt
))
1291 && jump_function_from_stmt (&arg1
, stmt
)))
1292 empty_or_with_defined_p
= false;
1295 cond
= last_stmt (cond_bb
);
1296 code
= gimple_cond_code (cond
);
1298 /* This transformation is only valid for equality comparisons. */
1299 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1302 /* We need to know which is the true edge and which is the false
1303 edge so that we know if have abs or negative abs. */
1304 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
1306 /* At this point we know we have a COND_EXPR with two successors.
1307 One successor is BB, the other successor is an empty block which
1308 falls through into BB.
1310 The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
1312 There is a single PHI node at the join point (BB) with two arguments.
1314 We now need to verify that the two arguments in the PHI node match
1315 the two arguments to the equality comparison. */
1317 if (operand_equal_for_value_replacement (arg0
, arg1
, &code
, cond
))
1322 /* For NE_EXPR, we want to build an assignment result = arg where
1323 arg is the PHI argument associated with the true edge. For
1324 EQ_EXPR we want the PHI argument associated with the false edge. */
1325 e
= (code
== NE_EXPR
? true_edge
: false_edge
);
1327 /* Unfortunately, E may not reach BB (it may instead have gone to
1328 OTHER_BLOCK). If that is the case, then we want the single outgoing
1329 edge from OTHER_BLOCK which reaches BB and represents the desired
1330 path from COND_BLOCK. */
1331 if (e
->dest
== middle_bb
)
1332 e
= single_succ_edge (e
->dest
);
1334 /* Now we know the incoming edge to BB that has the argument for the
1335 RHS of our new assignment statement. */
1341 /* If the middle basic block was empty or is defining the
1342 PHI arguments and this is a single phi where the args are different
1343 for the edges e0 and e1 then we can remove the middle basic block. */
1344 if (empty_or_with_defined_p
1345 && single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi
)),
1348 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, arg
);
1349 /* Note that we optimized this PHI. */
1354 statistics_counter_event (cfun
, "Replace PHI with variable/value_replacement", 1);
1356 /* Replace the PHI arguments with arg. */
1357 SET_PHI_ARG_DEF (phi
, e0
->dest_idx
, arg
);
1358 SET_PHI_ARG_DEF (phi
, e1
->dest_idx
, arg
);
1359 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1361 fprintf (dump_file
, "PHI ");
1362 print_generic_expr (dump_file
, gimple_phi_result (phi
));
1363 fprintf (dump_file
, " reduced for COND_EXPR in block %d to ",
1365 print_generic_expr (dump_file
, arg
);
1366 fprintf (dump_file
, ".\n");
1373 /* Now optimize (x != 0) ? x + y : y to just x + y. */
1374 gsi
= gsi_last_nondebug_bb (middle_bb
);
1375 if (gsi_end_p (gsi
))
1378 gimple
*assign
= gsi_stmt (gsi
);
1379 if (!is_gimple_assign (assign
)
1380 || gimple_assign_rhs_class (assign
) != GIMPLE_BINARY_RHS
1381 || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0
))
1382 && !POINTER_TYPE_P (TREE_TYPE (arg0
))))
1385 /* Punt if there are (degenerate) PHIs in middle_bb, there should not be. */
1386 if (!gimple_seq_empty_p (phi_nodes (middle_bb
)))
1389 /* Allow up to 2 cheap preparation statements that prepare argument
1397 iftmp.0_6 = x_5(D) r<< _1;
1399 # iftmp.0_2 = PHI <iftmp.0_6(3), x_5(D)(2)>
1410 # _2 = PHI <x_5(D)(2), _6(3)> */
1411 gimple
*prep_stmt
[2] = { NULL
, NULL
};
1413 for (prep_cnt
= 0; ; prep_cnt
++)
1415 gsi_prev_nondebug (&gsi
);
1416 if (gsi_end_p (gsi
))
1419 gimple
*g
= gsi_stmt (gsi
);
1420 if (gimple_code (g
) == GIMPLE_LABEL
)
1423 if (prep_cnt
== 2 || !is_gimple_assign (g
))
1426 tree lhs
= gimple_assign_lhs (g
);
1427 tree rhs1
= gimple_assign_rhs1 (g
);
1428 use_operand_p use_p
;
1430 if (TREE_CODE (lhs
) != SSA_NAME
1431 || TREE_CODE (rhs1
) != SSA_NAME
1432 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
1433 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
1434 || !single_imm_use (lhs
, &use_p
, &use_stmt
)
1435 || use_stmt
!= (prep_cnt
? prep_stmt
[prep_cnt
- 1] : assign
))
1437 switch (gimple_assign_rhs_code (g
))
1445 if (TREE_CODE (gimple_assign_rhs2 (g
)) != INTEGER_CST
)
1451 prep_stmt
[prep_cnt
] = g
;
1454 /* Only transform if it removes the condition. */
1455 if (!single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi
)), e0
, e1
))
1458 /* Size-wise, this is always profitable. */
1459 if (optimize_bb_for_speed_p (cond_bb
)
1460 /* The special case is useless if it has a low probability. */
1461 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
1462 && EDGE_PRED (middle_bb
, 0)->probability
< profile_probability::even ()
1463 /* If assign is cheap, there is no point avoiding it. */
1464 && estimate_num_insns_seq (bb_seq (middle_bb
), &eni_time_weights
)
1465 >= 3 * estimate_num_insns (cond
, &eni_time_weights
))
1468 tree lhs
= gimple_assign_lhs (assign
);
1469 tree rhs1
= gimple_assign_rhs1 (assign
);
1470 tree rhs2
= gimple_assign_rhs2 (assign
);
1471 enum tree_code code_def
= gimple_assign_rhs_code (assign
);
1472 tree cond_lhs
= gimple_cond_lhs (cond
);
1473 tree cond_rhs
= gimple_cond_rhs (cond
);
1475 /* Propagate the cond_rhs constant through preparation stmts,
1476 make sure UB isn't invoked while doing that. */
1477 for (int i
= prep_cnt
- 1; i
>= 0; --i
)
1479 gimple
*g
= prep_stmt
[i
];
1480 tree grhs1
= gimple_assign_rhs1 (g
);
1481 if (!operand_equal_for_phi_arg_p (cond_lhs
, grhs1
))
1483 cond_lhs
= gimple_assign_lhs (g
);
1484 cond_rhs
= fold_convert (TREE_TYPE (grhs1
), cond_rhs
);
1485 if (TREE_CODE (cond_rhs
) != INTEGER_CST
1486 || TREE_OVERFLOW (cond_rhs
))
1488 if (gimple_assign_rhs_class (g
) == GIMPLE_BINARY_RHS
)
1490 cond_rhs
= int_const_binop (gimple_assign_rhs_code (g
), cond_rhs
,
1491 gimple_assign_rhs2 (g
));
1492 if (TREE_OVERFLOW (cond_rhs
))
1495 cond_rhs
= fold_convert (TREE_TYPE (cond_lhs
), cond_rhs
);
1496 if (TREE_CODE (cond_rhs
) != INTEGER_CST
1497 || TREE_OVERFLOW (cond_rhs
))
1501 if (((code
== NE_EXPR
&& e1
== false_edge
)
1502 || (code
== EQ_EXPR
&& e1
== true_edge
))
1505 && operand_equal_for_phi_arg_p (rhs2
, cond_lhs
)
1506 && neutral_element_p (code_def
, cond_rhs
, true))
1508 && operand_equal_for_phi_arg_p (rhs1
, cond_lhs
)
1509 && neutral_element_p (code_def
, cond_rhs
, false))
1510 || (operand_equal_for_phi_arg_p (arg1
, cond_rhs
)
1511 && ((operand_equal_for_phi_arg_p (rhs2
, cond_lhs
)
1512 && absorbing_element_p (code_def
, cond_rhs
, true, rhs2
))
1513 || (operand_equal_for_phi_arg_p (rhs1
, cond_lhs
)
1514 && absorbing_element_p (code_def
,
1515 cond_rhs
, false, rhs2
))))))
1517 gsi
= gsi_for_stmt (cond
);
1518 /* Moving ASSIGN might change VR of lhs, e.g. when moving u_6
1526 # RANGE [0, 4294967294]
1527 u_6 = n_5 + 4294967295;
1530 # u_3 = PHI <u_6(3), 4294967295(2)> */
1531 reset_flow_sensitive_info (lhs
);
1532 gimple_stmt_iterator gsi_from
;
1533 for (int i
= prep_cnt
- 1; i
>= 0; --i
)
1535 tree plhs
= gimple_assign_lhs (prep_stmt
[i
]);
1536 reset_flow_sensitive_info (plhs
);
1537 gsi_from
= gsi_for_stmt (prep_stmt
[i
]);
1538 gsi_move_before (&gsi_from
, &gsi
);
1540 gsi_from
= gsi_for_stmt (assign
);
1541 gsi_move_before (&gsi_from
, &gsi
);
1542 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, lhs
);
1549 /* The function minmax_replacement does the main work of doing the minmax
1550 replacement. Return true if the replacement is done. Otherwise return
1552 BB is the basic block where the replacement is going to be done on. ARG0
1553 is argument 0 from the PHI. Likewise for ARG1. */
1556 minmax_replacement (basic_block cond_bb
, basic_block middle_bb
,
1557 edge e0
, edge e1
, gphi
*phi
, tree arg0
, tree arg1
)
1560 edge true_edge
, false_edge
;
1561 enum tree_code minmax
, ass_code
;
1562 tree smaller
, larger
, arg_true
, arg_false
;
1563 gimple_stmt_iterator gsi
, gsi_from
;
1565 tree type
= TREE_TYPE (PHI_RESULT (phi
));
1567 /* The optimization may be unsafe due to NaNs. */
1568 if (HONOR_NANS (type
) || HONOR_SIGNED_ZEROS (type
))
1571 gcond
*cond
= as_a
<gcond
*> (last_stmt (cond_bb
));
1572 enum tree_code cmp
= gimple_cond_code (cond
);
1573 tree rhs
= gimple_cond_rhs (cond
);
1575 /* Turn EQ/NE of extreme values to order comparisons. */
1576 if ((cmp
== NE_EXPR
|| cmp
== EQ_EXPR
)
1577 && TREE_CODE (rhs
) == INTEGER_CST
1578 && INTEGRAL_TYPE_P (TREE_TYPE (rhs
)))
1580 if (wi::eq_p (wi::to_wide (rhs
), wi::min_value (TREE_TYPE (rhs
))))
1582 cmp
= (cmp
== EQ_EXPR
) ? LT_EXPR
: GE_EXPR
;
1583 rhs
= wide_int_to_tree (TREE_TYPE (rhs
),
1584 wi::min_value (TREE_TYPE (rhs
)) + 1);
1586 else if (wi::eq_p (wi::to_wide (rhs
), wi::max_value (TREE_TYPE (rhs
))))
1588 cmp
= (cmp
== EQ_EXPR
) ? GT_EXPR
: LE_EXPR
;
1589 rhs
= wide_int_to_tree (TREE_TYPE (rhs
),
1590 wi::max_value (TREE_TYPE (rhs
)) - 1);
1594 /* This transformation is only valid for order comparisons. Record which
1595 operand is smaller/larger if the result of the comparison is true. */
1596 tree alt_smaller
= NULL_TREE
;
1597 tree alt_larger
= NULL_TREE
;
1598 if (cmp
== LT_EXPR
|| cmp
== LE_EXPR
)
1600 smaller
= gimple_cond_lhs (cond
);
1602 /* If we have smaller < CST it is equivalent to smaller <= CST-1.
1603 Likewise smaller <= CST is equivalent to smaller < CST+1. */
1604 if (TREE_CODE (larger
) == INTEGER_CST
1605 && INTEGRAL_TYPE_P (TREE_TYPE (larger
)))
1609 wi::overflow_type overflow
;
1610 wide_int alt
= wi::sub (wi::to_wide (larger
), 1,
1611 TYPE_SIGN (TREE_TYPE (larger
)),
1614 alt_larger
= wide_int_to_tree (TREE_TYPE (larger
), alt
);
1618 wi::overflow_type overflow
;
1619 wide_int alt
= wi::add (wi::to_wide (larger
), 1,
1620 TYPE_SIGN (TREE_TYPE (larger
)),
1623 alt_larger
= wide_int_to_tree (TREE_TYPE (larger
), alt
);
1627 else if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
1630 larger
= gimple_cond_lhs (cond
);
1631 /* If we have larger > CST it is equivalent to larger >= CST+1.
1632 Likewise larger >= CST is equivalent to larger > CST-1. */
1633 if (TREE_CODE (smaller
) == INTEGER_CST
1634 && INTEGRAL_TYPE_P (TREE_TYPE (smaller
)))
1636 wi::overflow_type overflow
;
1639 wide_int alt
= wi::add (wi::to_wide (smaller
), 1,
1640 TYPE_SIGN (TREE_TYPE (smaller
)),
1643 alt_smaller
= wide_int_to_tree (TREE_TYPE (smaller
), alt
);
1647 wide_int alt
= wi::sub (wi::to_wide (smaller
), 1,
1648 TYPE_SIGN (TREE_TYPE (smaller
)),
1651 alt_smaller
= wide_int_to_tree (TREE_TYPE (smaller
), alt
);
1658 /* Handle the special case of (signed_type)x < 0 being equivalent
1659 to x > MAX_VAL(signed_type) and (signed_type)x >= 0 equivalent
1660 to x <= MAX_VAL(signed_type). */
1661 if ((cmp
== GE_EXPR
|| cmp
== LT_EXPR
)
1662 && INTEGRAL_TYPE_P (type
)
1663 && TYPE_UNSIGNED (type
)
1664 && integer_zerop (rhs
))
1666 tree op
= gimple_cond_lhs (cond
);
1667 if (TREE_CODE (op
) == SSA_NAME
1668 && INTEGRAL_TYPE_P (TREE_TYPE (op
))
1669 && !TYPE_UNSIGNED (TREE_TYPE (op
)))
1671 gimple
*def_stmt
= SSA_NAME_DEF_STMT (op
);
1672 if (gimple_assign_cast_p (def_stmt
))
1674 tree op1
= gimple_assign_rhs1 (def_stmt
);
1675 if (INTEGRAL_TYPE_P (TREE_TYPE (op1
))
1676 && TYPE_UNSIGNED (TREE_TYPE (op1
))
1677 && (TYPE_PRECISION (TREE_TYPE (op
))
1678 == TYPE_PRECISION (TREE_TYPE (op1
)))
1679 && useless_type_conversion_p (type
, TREE_TYPE (op1
)))
1681 wide_int w1
= wi::max_value (TREE_TYPE (op
));
1682 wide_int w2
= wi::add (w1
, 1);
1686 smaller
= wide_int_to_tree (TREE_TYPE (op1
), w1
);
1687 alt_smaller
= wide_int_to_tree (TREE_TYPE (op1
), w2
);
1688 alt_larger
= NULL_TREE
;
1693 larger
= wide_int_to_tree (TREE_TYPE (op1
), w1
);
1694 alt_larger
= wide_int_to_tree (TREE_TYPE (op1
), w2
);
1695 alt_smaller
= NULL_TREE
;
1702 /* We need to know which is the true edge and which is the false
1703 edge so that we know if have abs or negative abs. */
1704 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
1706 /* Forward the edges over the middle basic block. */
1707 if (true_edge
->dest
== middle_bb
)
1708 true_edge
= EDGE_SUCC (true_edge
->dest
, 0);
1709 if (false_edge
->dest
== middle_bb
)
1710 false_edge
= EDGE_SUCC (false_edge
->dest
, 0);
1712 if (true_edge
== e0
)
1714 gcc_assert (false_edge
== e1
);
1720 gcc_assert (false_edge
== e0
);
1721 gcc_assert (true_edge
== e1
);
1726 if (empty_block_p (middle_bb
))
1728 if ((operand_equal_for_phi_arg_p (arg_true
, smaller
)
1730 && operand_equal_for_phi_arg_p (arg_true
, alt_smaller
)))
1731 && (operand_equal_for_phi_arg_p (arg_false
, larger
)
1733 && operand_equal_for_phi_arg_p (arg_true
, alt_larger
))))
1737 if (smaller < larger)
1743 else if ((operand_equal_for_phi_arg_p (arg_false
, smaller
)
1745 && operand_equal_for_phi_arg_p (arg_false
, alt_smaller
)))
1746 && (operand_equal_for_phi_arg_p (arg_true
, larger
)
1748 && operand_equal_for_phi_arg_p (arg_true
, alt_larger
))))
1755 /* Recognize the following case, assuming d <= u:
1761 This is equivalent to
1766 gimple
*assign
= last_and_only_stmt (middle_bb
);
1767 tree lhs
, op0
, op1
, bound
;
1770 || gimple_code (assign
) != GIMPLE_ASSIGN
)
1773 lhs
= gimple_assign_lhs (assign
);
1774 ass_code
= gimple_assign_rhs_code (assign
);
1775 if (ass_code
!= MAX_EXPR
&& ass_code
!= MIN_EXPR
)
1777 op0
= gimple_assign_rhs1 (assign
);
1778 op1
= gimple_assign_rhs2 (assign
);
1780 if (true_edge
->src
== middle_bb
)
1782 /* We got here if the condition is true, i.e., SMALLER < LARGER. */
1783 if (!operand_equal_for_phi_arg_p (lhs
, arg_true
))
1786 if (operand_equal_for_phi_arg_p (arg_false
, larger
)
1788 && operand_equal_for_phi_arg_p (arg_false
, alt_larger
)))
1792 if (smaller < larger)
1794 r' = MAX_EXPR (smaller, bound)
1796 r = PHI <r', larger> --> to be turned to MIN_EXPR. */
1797 if (ass_code
!= MAX_EXPR
)
1801 if (operand_equal_for_phi_arg_p (op0
, smaller
)
1803 && operand_equal_for_phi_arg_p (op0
, alt_smaller
)))
1805 else if (operand_equal_for_phi_arg_p (op1
, smaller
)
1807 && operand_equal_for_phi_arg_p (op1
, alt_smaller
)))
1812 /* We need BOUND <= LARGER. */
1813 if (!integer_nonzerop (fold_build2 (LE_EXPR
, boolean_type_node
,
1817 else if (operand_equal_for_phi_arg_p (arg_false
, smaller
)
1819 && operand_equal_for_phi_arg_p (arg_false
, alt_smaller
)))
1823 if (smaller < larger)
1825 r' = MIN_EXPR (larger, bound)
1827 r = PHI <r', smaller> --> to be turned to MAX_EXPR. */
1828 if (ass_code
!= MIN_EXPR
)
1832 if (operand_equal_for_phi_arg_p (op0
, larger
)
1834 && operand_equal_for_phi_arg_p (op0
, alt_larger
)))
1836 else if (operand_equal_for_phi_arg_p (op1
, larger
)
1838 && operand_equal_for_phi_arg_p (op1
, alt_larger
)))
1843 /* We need BOUND >= SMALLER. */
1844 if (!integer_nonzerop (fold_build2 (GE_EXPR
, boolean_type_node
,
1853 /* We got here if the condition is false, i.e., SMALLER > LARGER. */
1854 if (!operand_equal_for_phi_arg_p (lhs
, arg_false
))
1857 if (operand_equal_for_phi_arg_p (arg_true
, larger
)
1859 && operand_equal_for_phi_arg_p (arg_true
, alt_larger
)))
1863 if (smaller > larger)
1865 r' = MIN_EXPR (smaller, bound)
1867 r = PHI <r', larger> --> to be turned to MAX_EXPR. */
1868 if (ass_code
!= MIN_EXPR
)
1872 if (operand_equal_for_phi_arg_p (op0
, smaller
)
1874 && operand_equal_for_phi_arg_p (op0
, alt_smaller
)))
1876 else if (operand_equal_for_phi_arg_p (op1
, smaller
)
1878 && operand_equal_for_phi_arg_p (op1
, alt_smaller
)))
1883 /* We need BOUND >= LARGER. */
1884 if (!integer_nonzerop (fold_build2 (GE_EXPR
, boolean_type_node
,
1888 else if (operand_equal_for_phi_arg_p (arg_true
, smaller
)
1890 && operand_equal_for_phi_arg_p (arg_true
, alt_smaller
)))
1894 if (smaller > larger)
1896 r' = MAX_EXPR (larger, bound)
1898 r = PHI <r', smaller> --> to be turned to MIN_EXPR. */
1899 if (ass_code
!= MAX_EXPR
)
1903 if (operand_equal_for_phi_arg_p (op0
, larger
))
1905 else if (operand_equal_for_phi_arg_p (op1
, larger
))
1910 /* We need BOUND <= SMALLER. */
1911 if (!integer_nonzerop (fold_build2 (LE_EXPR
, boolean_type_node
,
1919 /* Move the statement from the middle block. */
1920 gsi
= gsi_last_bb (cond_bb
);
1921 gsi_from
= gsi_last_nondebug_bb (middle_bb
);
1922 reset_flow_sensitive_info (SINGLE_SSA_TREE_OPERAND (gsi_stmt (gsi_from
),
1924 gsi_move_before (&gsi_from
, &gsi
);
1927 /* Emit the statement to compute min/max. */
1928 gimple_seq stmts
= NULL
;
1929 tree phi_result
= PHI_RESULT (phi
);
1930 result
= gimple_build (&stmts
, minmax
, TREE_TYPE (phi_result
), arg0
, arg1
);
1932 gsi
= gsi_last_bb (cond_bb
);
1933 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
1935 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, result
);
1940 /* Return true if the only executable statement in BB is a GIMPLE_COND. */
1943 cond_only_block_p (basic_block bb
)
1945 /* BB must have no executable statements. */
1946 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1949 while (!gsi_end_p (gsi
))
1951 gimple
*stmt
= gsi_stmt (gsi
);
1952 if (is_gimple_debug (stmt
))
1954 else if (gimple_code (stmt
) == GIMPLE_NOP
1955 || gimple_code (stmt
) == GIMPLE_PREDICT
1956 || gimple_code (stmt
) == GIMPLE_COND
)
1965 /* Attempt to optimize (x <=> y) cmp 0 and similar comparisons.
1966 For strong ordering <=> try to match something like:
1967 <bb 2> : // cond3_bb (== cond2_bb)
1968 if (x_4(D) != y_5(D))
1974 if (x_4(D) < y_5(D))
1979 <bb 4> : // middle_bb
1982 # iftmp.0_2 = PHI <1(4), 0(2), -1(3)>
1983 _1 = iftmp.0_2 == 0;
1985 and for partial ordering <=> something like:
1987 <bb 2> : // cond3_bb
1988 if (a_3(D) == b_5(D))
1989 goto <bb 6>; [50.00%]
1991 goto <bb 3>; [50.00%]
1993 <bb 3> [local count: 536870913]: // cond2_bb
1994 if (a_3(D) < b_5(D))
1995 goto <bb 6>; [50.00%]
1997 goto <bb 4>; [50.00%]
1999 <bb 4> [local count: 268435456]: // cond_bb
2000 if (a_3(D) > b_5(D))
2001 goto <bb 6>; [50.00%]
2003 goto <bb 5>; [50.00%]
2005 <bb 5> [local count: 134217728]: // middle_bb
2007 <bb 6> [local count: 1073741824]: // phi_bb
2008 # SR.27_4 = PHI <0(2), -1(3), 1(4), 2(5)>
2009 _2 = SR.27_4 > 0; */
2012 spaceship_replacement (basic_block cond_bb
, basic_block middle_bb
,
2013 edge e0
, edge e1
, gphi
*phi
,
2014 tree arg0
, tree arg1
)
2016 tree phires
= PHI_RESULT (phi
);
2017 if (!INTEGRAL_TYPE_P (TREE_TYPE (phires
))
2018 || TYPE_UNSIGNED (TREE_TYPE (phires
))
2019 || !tree_fits_shwi_p (arg0
)
2020 || !tree_fits_shwi_p (arg1
)
2021 || !IN_RANGE (tree_to_shwi (arg0
), -1, 2)
2022 || !IN_RANGE (tree_to_shwi (arg1
), -1, 2))
2025 basic_block phi_bb
= gimple_bb (phi
);
2026 gcc_assert (phi_bb
== e0
->dest
&& phi_bb
== e1
->dest
);
2027 if (!IN_RANGE (EDGE_COUNT (phi_bb
->preds
), 3, 4))
2030 use_operand_p use_p
;
2032 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (phires
))
2034 if (!single_imm_use (phires
, &use_p
, &use_stmt
))
2038 gimple
*orig_use_stmt
= use_stmt
;
2039 tree orig_use_lhs
= NULL_TREE
;
2040 int prec
= TYPE_PRECISION (TREE_TYPE (phires
));
2041 if (is_gimple_assign (use_stmt
)
2042 && gimple_assign_rhs_code (use_stmt
) == BIT_AND_EXPR
2043 && TREE_CODE (gimple_assign_rhs2 (use_stmt
)) == INTEGER_CST
2044 && (wi::to_wide (gimple_assign_rhs2 (use_stmt
))
2045 == wi::shifted_mask (1, prec
- 1, false, prec
)))
2047 /* For partial_ordering result operator>= with unspec as second
2048 argument is (res & 1) == res, folded by match.pd into
2050 orig_use_lhs
= gimple_assign_lhs (use_stmt
);
2051 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs
))
2053 if (EDGE_COUNT (phi_bb
->preds
) != 4)
2055 if (!single_imm_use (orig_use_lhs
, &use_p
, &use_stmt
))
2058 if (gimple_code (use_stmt
) == GIMPLE_COND
)
2060 cmp
= gimple_cond_code (use_stmt
);
2061 lhs
= gimple_cond_lhs (use_stmt
);
2062 rhs
= gimple_cond_rhs (use_stmt
);
2064 else if (is_gimple_assign (use_stmt
))
2066 if (gimple_assign_rhs_class (use_stmt
) == GIMPLE_BINARY_RHS
)
2068 cmp
= gimple_assign_rhs_code (use_stmt
);
2069 lhs
= gimple_assign_rhs1 (use_stmt
);
2070 rhs
= gimple_assign_rhs2 (use_stmt
);
2072 else if (gimple_assign_rhs_code (use_stmt
) == COND_EXPR
)
2074 tree cond
= gimple_assign_rhs1 (use_stmt
);
2075 if (!COMPARISON_CLASS_P (cond
))
2077 cmp
= TREE_CODE (cond
);
2078 lhs
= TREE_OPERAND (cond
, 0);
2079 rhs
= TREE_OPERAND (cond
, 1);
2098 if (lhs
!= (orig_use_lhs
? orig_use_lhs
: phires
)
2099 || !tree_fits_shwi_p (rhs
)
2100 || !IN_RANGE (tree_to_shwi (rhs
), -1, 1))
2104 if ((cmp
!= EQ_EXPR
&& cmp
!= NE_EXPR
) || !integer_zerop (rhs
))
2106 /* As for -ffast-math we assume the 2 return to be
2107 impossible, canonicalize (res & ~1) == 0 into
2108 res >= 0 and (res & ~1) != 0 as res < 0. */
2109 cmp
= cmp
== EQ_EXPR
? GE_EXPR
: LT_EXPR
;
2112 if (!empty_block_p (middle_bb
))
2115 gcond
*cond1
= as_a
<gcond
*> (last_stmt (cond_bb
));
2116 enum tree_code cmp1
= gimple_cond_code (cond1
);
2127 tree lhs1
= gimple_cond_lhs (cond1
);
2128 tree rhs1
= gimple_cond_rhs (cond1
);
2129 /* The optimization may be unsafe due to NaNs. */
2130 if (HONOR_NANS (TREE_TYPE (lhs1
)))
2132 if (TREE_CODE (lhs1
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs1
))
2134 if (TREE_CODE (rhs1
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
))
2137 if (!single_pred_p (cond_bb
) || !cond_only_block_p (cond_bb
))
2140 basic_block cond2_bb
= single_pred (cond_bb
);
2141 if (EDGE_COUNT (cond2_bb
->succs
) != 2)
2143 edge cond2_phi_edge
;
2144 if (EDGE_SUCC (cond2_bb
, 0)->dest
== cond_bb
)
2146 if (EDGE_SUCC (cond2_bb
, 1)->dest
!= phi_bb
)
2148 cond2_phi_edge
= EDGE_SUCC (cond2_bb
, 1);
2150 else if (EDGE_SUCC (cond2_bb
, 0)->dest
!= phi_bb
)
2153 cond2_phi_edge
= EDGE_SUCC (cond2_bb
, 0);
2154 tree arg2
= gimple_phi_arg_def (phi
, cond2_phi_edge
->dest_idx
);
2155 if (!tree_fits_shwi_p (arg2
))
2157 gimple
*cond2
= last_stmt (cond2_bb
);
2158 if (cond2
== NULL
|| gimple_code (cond2
) != GIMPLE_COND
)
2160 enum tree_code cmp2
= gimple_cond_code (cond2
);
2161 tree lhs2
= gimple_cond_lhs (cond2
);
2162 tree rhs2
= gimple_cond_rhs (cond2
);
2165 if (!operand_equal_p (rhs2
, rhs1
, 0))
2167 if ((cmp2
== EQ_EXPR
|| cmp2
== NE_EXPR
)
2168 && TREE_CODE (rhs1
) == INTEGER_CST
2169 && TREE_CODE (rhs2
) == INTEGER_CST
)
2171 /* For integers, we can have cond2 x == 5
2172 and cond1 x < 5, x <= 4, x <= 5, x < 6,
2173 x > 5, x >= 6, x >= 5 or x > 4. */
2174 if (tree_int_cst_lt (rhs1
, rhs2
))
2176 if (wi::ne_p (wi::to_wide (rhs1
) + 1, wi::to_wide (rhs2
)))
2178 if (cmp1
== LE_EXPR
)
2180 else if (cmp1
== GT_EXPR
)
2187 gcc_checking_assert (tree_int_cst_lt (rhs2
, rhs1
));
2188 if (wi::ne_p (wi::to_wide (rhs2
) + 1, wi::to_wide (rhs1
)))
2190 if (cmp1
== LT_EXPR
)
2192 else if (cmp1
== GE_EXPR
)
2203 else if (lhs2
== rhs1
)
2212 basic_block cond3_bb
= cond2_bb
;
2213 edge cond3_phi_edge
= cond2_phi_edge
;
2214 gimple
*cond3
= cond2
;
2215 enum tree_code cmp3
= cmp2
;
2218 if (EDGE_COUNT (phi_bb
->preds
) == 4)
2220 if (absu_hwi (tree_to_shwi (arg2
)) != 1)
2222 if (e1
->flags
& EDGE_TRUE_VALUE
)
2224 if (tree_to_shwi (arg0
) != 2
2225 || absu_hwi (tree_to_shwi (arg1
)) != 1
2226 || wi::to_widest (arg1
) == wi::to_widest (arg2
))
2229 else if (tree_to_shwi (arg1
) != 2
2230 || absu_hwi (tree_to_shwi (arg0
)) != 1
2231 || wi::to_widest (arg0
) == wi::to_widest (arg1
))
2243 /* if (x < y) goto phi_bb; else fallthru;
2244 if (x > y) goto phi_bb; else fallthru;
2247 is ok, but if x and y are swapped in one of the comparisons,
2248 or the comparisons are the same and operands not swapped,
2249 or the true and false edges are swapped, it is not. */
2251 ^ (((cond2_phi_edge
->flags
2252 & ((cmp2
== LT_EXPR
|| cmp2
== LE_EXPR
)
2253 ? EDGE_TRUE_VALUE
: EDGE_FALSE_VALUE
)) != 0)
2255 & ((cmp1
== LT_EXPR
|| cmp1
== LE_EXPR
)
2256 ? EDGE_TRUE_VALUE
: EDGE_FALSE_VALUE
)) != 0)))
2258 if (!single_pred_p (cond2_bb
) || !cond_only_block_p (cond2_bb
))
2260 cond3_bb
= single_pred (cond2_bb
);
2261 if (EDGE_COUNT (cond2_bb
->succs
) != 2)
2263 if (EDGE_SUCC (cond3_bb
, 0)->dest
== cond2_bb
)
2265 if (EDGE_SUCC (cond3_bb
, 1)->dest
!= phi_bb
)
2267 cond3_phi_edge
= EDGE_SUCC (cond3_bb
, 1);
2269 else if (EDGE_SUCC (cond3_bb
, 0)->dest
!= phi_bb
)
2272 cond3_phi_edge
= EDGE_SUCC (cond3_bb
, 0);
2273 arg3
= gimple_phi_arg_def (phi
, cond3_phi_edge
->dest_idx
);
2274 cond3
= last_stmt (cond3_bb
);
2275 if (cond3
== NULL
|| gimple_code (cond3
) != GIMPLE_COND
)
2277 cmp3
= gimple_cond_code (cond3
);
2278 lhs3
= gimple_cond_lhs (cond3
);
2279 rhs3
= gimple_cond_rhs (cond3
);
2282 if (!operand_equal_p (rhs3
, rhs1
, 0))
2285 else if (lhs3
== rhs1
)
2293 else if (absu_hwi (tree_to_shwi (arg0
)) != 1
2294 || absu_hwi (tree_to_shwi (arg1
)) != 1
2295 || wi::to_widest (arg0
) == wi::to_widest (arg1
))
2298 if (!integer_zerop (arg3
) || (cmp3
!= EQ_EXPR
&& cmp3
!= NE_EXPR
))
2300 if ((cond3_phi_edge
->flags
& (cmp3
== EQ_EXPR
2301 ? EDGE_TRUE_VALUE
: EDGE_FALSE_VALUE
)) == 0)
2304 /* lhs1 one_cmp rhs1 results in phires of 1. */
2305 enum tree_code one_cmp
;
2306 if ((cmp1
== LT_EXPR
|| cmp1
== LE_EXPR
)
2307 ^ (!integer_onep ((e1
->flags
& EDGE_TRUE_VALUE
) ? arg1
: arg0
)))
2312 enum tree_code res_cmp
;
2316 if (integer_zerop (rhs
))
2318 else if (integer_minus_onep (rhs
))
2319 res_cmp
= one_cmp
== LT_EXPR
? GT_EXPR
: LT_EXPR
;
2320 else if (integer_onep (rhs
))
2326 if (integer_zerop (rhs
))
2328 else if (integer_minus_onep (rhs
))
2329 res_cmp
= one_cmp
== LT_EXPR
? LE_EXPR
: GE_EXPR
;
2330 else if (integer_onep (rhs
))
2331 res_cmp
= one_cmp
== LT_EXPR
? GE_EXPR
: LE_EXPR
;
2336 if (integer_onep (rhs
))
2337 res_cmp
= one_cmp
== LT_EXPR
? GE_EXPR
: LE_EXPR
;
2338 else if (integer_zerop (rhs
))
2339 res_cmp
= one_cmp
== LT_EXPR
? GT_EXPR
: LT_EXPR
;
2344 if (integer_zerop (rhs
))
2345 res_cmp
= one_cmp
== LT_EXPR
? GE_EXPR
: LE_EXPR
;
2346 else if (integer_minus_onep (rhs
))
2347 res_cmp
= one_cmp
== LT_EXPR
? GT_EXPR
: LT_EXPR
;
2352 if (integer_minus_onep (rhs
))
2353 res_cmp
= one_cmp
== LT_EXPR
? LE_EXPR
: GE_EXPR
;
2354 else if (integer_zerop (rhs
))
2360 if (integer_zerop (rhs
))
2361 res_cmp
= one_cmp
== LT_EXPR
? LE_EXPR
: GE_EXPR
;
2362 else if (integer_onep (rhs
))
2371 if (gimple_code (use_stmt
) == GIMPLE_COND
)
2373 gcond
*use_cond
= as_a
<gcond
*> (use_stmt
);
2374 gimple_cond_set_code (use_cond
, res_cmp
);
2375 gimple_cond_set_lhs (use_cond
, lhs1
);
2376 gimple_cond_set_rhs (use_cond
, rhs1
);
2378 else if (gimple_assign_rhs_class (use_stmt
) == GIMPLE_BINARY_RHS
)
2380 gimple_assign_set_rhs_code (use_stmt
, res_cmp
);
2381 gimple_assign_set_rhs1 (use_stmt
, lhs1
);
2382 gimple_assign_set_rhs2 (use_stmt
, rhs1
);
2386 tree cond
= build2 (res_cmp
, TREE_TYPE (gimple_assign_rhs1 (use_stmt
)),
2388 gimple_assign_set_rhs1 (use_stmt
, cond
);
2390 update_stmt (use_stmt
);
2392 if (MAY_HAVE_DEBUG_BIND_STMTS
)
2394 use_operand_p use_p
;
2395 imm_use_iterator iter
;
2396 bool has_debug_uses
= false;
2397 FOR_EACH_IMM_USE_FAST (use_p
, iter
, phires
)
2399 gimple
*use_stmt
= USE_STMT (use_p
);
2400 if (orig_use_lhs
&& use_stmt
== orig_use_stmt
)
2402 gcc_assert (is_gimple_debug (use_stmt
));
2403 has_debug_uses
= true;
2408 if (!has_debug_uses
)
2409 FOR_EACH_IMM_USE_FAST (use_p
, iter
, orig_use_lhs
)
2411 gimple
*use_stmt
= USE_STMT (use_p
);
2412 gcc_assert (is_gimple_debug (use_stmt
));
2413 has_debug_uses
= true;
2415 gimple_stmt_iterator gsi
= gsi_for_stmt (orig_use_stmt
);
2416 tree zero
= build_zero_cst (TREE_TYPE (orig_use_lhs
));
2417 gimple_assign_set_rhs_with_ops (&gsi
, INTEGER_CST
, zero
);
2418 update_stmt (orig_use_stmt
);
2423 /* If there are debug uses, emit something like:
2424 # DEBUG D#1 => i_2(D) > j_3(D) ? 1 : -1
2425 # DEBUG D#2 => i_2(D) == j_3(D) ? 0 : D#1
2426 where > stands for the comparison that yielded 1
2427 and replace debug uses of phi result with that D#2.
2428 Ignore the value of 2, because if NaNs aren't expected,
2429 all floating point numbers should be comparable. */
2430 gimple_stmt_iterator gsi
= gsi_after_labels (gimple_bb (phi
));
2431 tree type
= TREE_TYPE (phires
);
2432 tree temp1
= make_node (DEBUG_EXPR_DECL
);
2433 DECL_ARTIFICIAL (temp1
) = 1;
2434 TREE_TYPE (temp1
) = type
;
2435 SET_DECL_MODE (temp1
, TYPE_MODE (type
));
2436 tree t
= build2 (one_cmp
, boolean_type_node
, lhs1
, rhs2
);
2437 t
= build3 (COND_EXPR
, type
, t
, build_one_cst (type
),
2438 build_int_cst (type
, -1));
2439 gimple
*g
= gimple_build_debug_bind (temp1
, t
, phi
);
2440 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2441 tree temp2
= make_node (DEBUG_EXPR_DECL
);
2442 DECL_ARTIFICIAL (temp2
) = 1;
2443 TREE_TYPE (temp2
) = type
;
2444 SET_DECL_MODE (temp2
, TYPE_MODE (type
));
2445 t
= build2 (EQ_EXPR
, boolean_type_node
, lhs1
, rhs2
);
2446 t
= build3 (COND_EXPR
, type
, t
, build_zero_cst (type
), temp1
);
2447 g
= gimple_build_debug_bind (temp2
, t
, phi
);
2448 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2449 replace_uses_by (phires
, temp2
);
2451 replace_uses_by (orig_use_lhs
, temp2
);
2457 gimple_stmt_iterator gsi
= gsi_for_stmt (orig_use_stmt
);
2458 gsi_remove (&gsi
, true);
2461 gimple_stmt_iterator psi
= gsi_for_stmt (phi
);
2462 remove_phi_node (&psi
, true);
2463 statistics_counter_event (cfun
, "spaceship replacement", 1);
2468 /* Optimize x ? __builtin_fun (x) : C, where C is __builtin_fun (0).
2478 _2 = (unsigned long) b_4(D);
2479 _9 = __builtin_popcountl (_2);
2481 _9 = __builtin_popcountl (b_4(D));
2484 c_12 = PHI <0(2), _9(3)>
2488 _2 = (unsigned long) b_4(D);
2489 _9 = __builtin_popcountl (_2);
2491 _9 = __builtin_popcountl (b_4(D));
2496 Similarly for __builtin_clz or __builtin_ctz if
2497 C?Z_DEFINED_VALUE_AT_ZERO is 2, optab is present and
2498 instead of 0 above it uses the value from that macro. */
2501 cond_removal_in_builtin_zero_pattern (basic_block cond_bb
,
2502 basic_block middle_bb
,
2503 edge e1
, edge e2
, gphi
*phi
,
2504 tree arg0
, tree arg1
)
2507 gimple_stmt_iterator gsi
, gsi_from
;
2509 gimple
*cast
= NULL
;
2513 _2 = (unsigned long) b_4(D);
2514 _9 = __builtin_popcountl (_2);
2516 _9 = __builtin_popcountl (b_4(D));
2517 are the only stmts in the middle_bb. */
2519 gsi
= gsi_start_nondebug_after_labels_bb (middle_bb
);
2520 if (gsi_end_p (gsi
))
2522 cast
= gsi_stmt (gsi
);
2523 gsi_next_nondebug (&gsi
);
2524 if (!gsi_end_p (gsi
))
2526 call
= gsi_stmt (gsi
);
2527 gsi_next_nondebug (&gsi
);
2528 if (!gsi_end_p (gsi
))
2537 /* Check that we have a popcount/clz/ctz builtin. */
2538 if (!is_gimple_call (call
) || gimple_call_num_args (call
) != 1)
2541 arg
= gimple_call_arg (call
, 0);
2542 lhs
= gimple_get_lhs (call
);
2544 if (lhs
== NULL_TREE
)
2547 combined_fn cfn
= gimple_call_combined_fn (call
);
2548 internal_fn ifn
= IFN_LAST
;
2552 case CFN_BUILT_IN_BSWAP16
:
2553 case CFN_BUILT_IN_BSWAP32
:
2554 case CFN_BUILT_IN_BSWAP64
:
2555 case CFN_BUILT_IN_BSWAP128
:
2561 if (INTEGRAL_TYPE_P (TREE_TYPE (arg
)))
2563 tree type
= TREE_TYPE (arg
);
2564 if (direct_internal_fn_supported_p (IFN_CLZ
, type
, OPTIMIZE_FOR_BOTH
)
2565 && CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type
),
2574 if (INTEGRAL_TYPE_P (TREE_TYPE (arg
)))
2576 tree type
= TREE_TYPE (arg
);
2577 if (direct_internal_fn_supported_p (IFN_CTZ
, type
, OPTIMIZE_FOR_BOTH
)
2578 && CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type
),
2586 case CFN_BUILT_IN_CLRSB
:
2587 val
= TYPE_PRECISION (integer_type_node
) - 1;
2589 case CFN_BUILT_IN_CLRSBL
:
2590 val
= TYPE_PRECISION (long_integer_type_node
) - 1;
2592 case CFN_BUILT_IN_CLRSBLL
:
2593 val
= TYPE_PRECISION (long_long_integer_type_node
) - 1;
2601 /* We have a cast stmt feeding popcount/clz/ctz builtin. */
2602 /* Check that we have a cast prior to that. */
2603 if (gimple_code (cast
) != GIMPLE_ASSIGN
2604 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (cast
)))
2606 /* Result of the cast stmt is the argument to the builtin. */
2607 if (arg
!= gimple_assign_lhs (cast
))
2609 arg
= gimple_assign_rhs1 (cast
);
2612 cond
= last_stmt (cond_bb
);
2614 /* Cond_bb has a check for b_4 [!=|==] 0 before calling the popcount/clz/ctz
2616 if (gimple_code (cond
) != GIMPLE_COND
2617 || (gimple_cond_code (cond
) != NE_EXPR
2618 && gimple_cond_code (cond
) != EQ_EXPR
)
2619 || !integer_zerop (gimple_cond_rhs (cond
))
2620 || arg
!= gimple_cond_lhs (cond
))
2624 if ((e2
->flags
& EDGE_TRUE_VALUE
2625 && gimple_cond_code (cond
) == NE_EXPR
)
2626 || (e1
->flags
& EDGE_TRUE_VALUE
2627 && gimple_cond_code (cond
) == EQ_EXPR
))
2629 std::swap (arg0
, arg1
);
2633 /* Check PHI arguments. */
2635 || TREE_CODE (arg1
) != INTEGER_CST
2636 || wi::to_wide (arg1
) != val
)
2639 /* And insert the popcount/clz/ctz builtin and cast stmt before the
2641 gsi
= gsi_last_bb (cond_bb
);
2644 gsi_from
= gsi_for_stmt (cast
);
2645 gsi_move_before (&gsi_from
, &gsi
);
2646 reset_flow_sensitive_info (gimple_get_lhs (cast
));
2648 gsi_from
= gsi_for_stmt (call
);
2649 if (ifn
== IFN_LAST
|| gimple_call_internal_p (call
))
2650 gsi_move_before (&gsi_from
, &gsi
);
2653 /* For __builtin_c[lt]z* force .C[LT]Z ifn, because only
2654 the latter is well defined at zero. */
2655 call
= gimple_build_call_internal (ifn
, 1, gimple_call_arg (call
, 0));
2656 gimple_call_set_lhs (call
, lhs
);
2657 gsi_insert_before (&gsi
, call
, GSI_SAME_STMT
);
2658 gsi_remove (&gsi_from
, true);
2660 reset_flow_sensitive_info (lhs
);
2662 /* Now update the PHI and remove unneeded bbs. */
2663 replace_phi_edge_with_variable (cond_bb
, e2
, phi
, lhs
);
2667 /* Auxiliary functions to determine the set of memory accesses which
2668 can't trap because they are preceded by accesses to the same memory
2669 portion. We do that for MEM_REFs, so we only need to track
2670 the SSA_NAME of the pointer indirectly referenced. The algorithm
2671 simply is a walk over all instructions in dominator order. When
2672 we see an MEM_REF we determine if we've already seen a same
2673 ref anywhere up to the root of the dominator tree. If we do the
2674 current access can't trap. If we don't see any dominating access
2675 the current access might trap, but might also make later accesses
2676 non-trapping, so we remember it. We need to be careful with loads
2677 or stores, for instance a load might not trap, while a store would,
2678 so if we see a dominating read access this doesn't mean that a later
2679 write access would not trap. Hence we also need to differentiate the
2680 type of access(es) seen.
2682 ??? We currently are very conservative and assume that a load might
2683 trap even if a store doesn't (write-only memory). This probably is
2684 overly conservative.
2686 We currently support a special case that for !TREE_ADDRESSABLE automatic
2687 variables, it could ignore whether something is a load or store because the
2688 local stack should be always writable. */
2690 /* A hash-table of references (MEM_REF/ARRAY_REF/COMPONENT_REF), and in which
2691 basic block an *_REF through it was seen, which would constitute a
2692 no-trap region for same accesses.
2694 Size is needed to support 2 MEM_REFs of different types, like
2695 MEM<double>(s_1) and MEM<long>(s_1), which would compare equal with
2705 /* Hashtable helpers. */
2707 struct refs_hasher
: free_ptr_hash
<ref_to_bb
>
2709 static inline hashval_t
hash (const ref_to_bb
*);
2710 static inline bool equal (const ref_to_bb
*, const ref_to_bb
*);
2713 /* Used for quick clearing of the hash-table when we see calls.
2714 Hash entries with phase < nt_call_phase are invalid. */
2715 static unsigned int nt_call_phase
;
2717 /* The hash function. */
2720 refs_hasher::hash (const ref_to_bb
*n
)
2722 inchash::hash hstate
;
2723 inchash::add_expr (n
->exp
, hstate
, OEP_ADDRESS_OF
);
2724 hstate
.add_hwi (n
->size
);
2725 return hstate
.end ();
2728 /* The equality function of *P1 and *P2. */
2731 refs_hasher::equal (const ref_to_bb
*n1
, const ref_to_bb
*n2
)
2733 return operand_equal_p (n1
->exp
, n2
->exp
, OEP_ADDRESS_OF
)
2734 && n1
->size
== n2
->size
;
2737 class nontrapping_dom_walker
: public dom_walker
2740 nontrapping_dom_walker (cdi_direction direction
, hash_set
<tree
> *ps
)
2741 : dom_walker (direction
), m_nontrapping (ps
), m_seen_refs (128)
2744 virtual edge
before_dom_children (basic_block
);
2745 virtual void after_dom_children (basic_block
);
2749 /* We see the expression EXP in basic block BB. If it's an interesting
2750 expression (an MEM_REF through an SSA_NAME) possibly insert the
2751 expression into the set NONTRAP or the hash table of seen expressions.
2752 STORE is true if this expression is on the LHS, otherwise it's on
2754 void add_or_mark_expr (basic_block
, tree
, bool);
2756 hash_set
<tree
> *m_nontrapping
;
2758 /* The hash table for remembering what we've seen. */
2759 hash_table
<refs_hasher
> m_seen_refs
;
2762 /* Called by walk_dominator_tree, when entering the block BB. */
2764 nontrapping_dom_walker::before_dom_children (basic_block bb
)
2768 gimple_stmt_iterator gsi
;
2770 /* If we haven't seen all our predecessors, clear the hash-table. */
2771 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2772 if ((((size_t)e
->src
->aux
) & 2) == 0)
2778 /* Mark this BB as being on the path to dominator root and as visited. */
2779 bb
->aux
= (void*)(1 | 2);
2781 /* And walk the statements in order. */
2782 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2784 gimple
*stmt
= gsi_stmt (gsi
);
2786 if ((gimple_code (stmt
) == GIMPLE_ASM
&& gimple_vdef (stmt
))
2787 || (is_gimple_call (stmt
)
2788 && (!nonfreeing_call_p (stmt
) || !nonbarrier_call_p (stmt
))))
2790 else if (gimple_assign_single_p (stmt
) && !gimple_has_volatile_ops (stmt
))
2792 add_or_mark_expr (bb
, gimple_assign_lhs (stmt
), true);
2793 add_or_mark_expr (bb
, gimple_assign_rhs1 (stmt
), false);
2799 /* Called by walk_dominator_tree, when basic block BB is exited. */
2801 nontrapping_dom_walker::after_dom_children (basic_block bb
)
2803 /* This BB isn't on the path to dominator root anymore. */
2807 /* We see the expression EXP in basic block BB. If it's an interesting
2812 possibly insert the expression into the set NONTRAP or the hash table
2813 of seen expressions. STORE is true if this expression is on the LHS,
2814 otherwise it's on the RHS. */
2816 nontrapping_dom_walker::add_or_mark_expr (basic_block bb
, tree exp
, bool store
)
2820 if ((TREE_CODE (exp
) == MEM_REF
|| TREE_CODE (exp
) == ARRAY_REF
2821 || TREE_CODE (exp
) == COMPONENT_REF
)
2822 && (size
= int_size_in_bytes (TREE_TYPE (exp
))) > 0)
2824 struct ref_to_bb map
;
2826 struct ref_to_bb
*r2bb
;
2827 basic_block found_bb
= 0;
2831 tree base
= get_base_address (exp
);
2832 /* Only record a LOAD of a local variable without address-taken, as
2833 the local stack is always writable. This allows cselim on a STORE
2834 with a dominating LOAD. */
2835 if (!auto_var_p (base
) || TREE_ADDRESSABLE (base
))
2839 /* Try to find the last seen *_REF, which can trap. */
2842 slot
= m_seen_refs
.find_slot (&map
, INSERT
);
2844 if (r2bb
&& r2bb
->phase
>= nt_call_phase
)
2845 found_bb
= r2bb
->bb
;
2847 /* If we've found a trapping *_REF, _and_ it dominates EXP
2848 (it's in a basic block on the path from us to the dominator root)
2849 then we can't trap. */
2850 if (found_bb
&& (((size_t)found_bb
->aux
) & 1) == 1)
2852 m_nontrapping
->add (exp
);
2856 /* EXP might trap, so insert it into the hash table. */
2859 r2bb
->phase
= nt_call_phase
;
2864 r2bb
= XNEW (struct ref_to_bb
);
2865 r2bb
->phase
= nt_call_phase
;
2875 /* This is the entry point of gathering non trapping memory accesses.
2876 It will do a dominator walk over the whole function, and it will
2877 make use of the bb->aux pointers. It returns a set of trees
2878 (the MEM_REFs itself) which can't trap. */
2879 static hash_set
<tree
> *
2880 get_non_trapping (void)
2883 hash_set
<tree
> *nontrap
= new hash_set
<tree
>;
2885 nontrapping_dom_walker (CDI_DOMINATORS
, nontrap
)
2886 .walk (cfun
->cfg
->x_entry_block_ptr
);
2888 clear_aux_for_blocks ();
2892 /* Do the main work of conditional store replacement. We already know
2893 that the recognized pattern looks like so:
2896 if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
2899 fallthrough (edge E0)
2903 We check that MIDDLE_BB contains only one store, that that store
2904 doesn't trap (not via NOTRAP, but via checking if an access to the same
2905 memory location dominates us, or the store is to a local addressable
2906 object) and that the store has a "simple" RHS. */
2909 cond_store_replacement (basic_block middle_bb
, basic_block join_bb
,
2910 edge e0
, edge e1
, hash_set
<tree
> *nontrap
)
2912 gimple
*assign
= last_and_only_stmt (middle_bb
);
2913 tree lhs
, rhs
, name
, name2
;
2916 gimple_stmt_iterator gsi
;
2919 /* Check if middle_bb contains of only one store. */
2921 || !gimple_assign_single_p (assign
)
2922 || gimple_has_volatile_ops (assign
))
2925 /* And no PHI nodes so all uses in the single stmt are also
2926 available where we insert to. */
2927 if (!gimple_seq_empty_p (phi_nodes (middle_bb
)))
2930 locus
= gimple_location (assign
);
2931 lhs
= gimple_assign_lhs (assign
);
2932 rhs
= gimple_assign_rhs1 (assign
);
2933 if ((!REFERENCE_CLASS_P (lhs
)
2935 || !is_gimple_reg_type (TREE_TYPE (lhs
)))
2938 /* Prove that we can move the store down. We could also check
2939 TREE_THIS_NOTRAP here, but in that case we also could move stores,
2940 whose value is not available readily, which we want to avoid. */
2941 if (!nontrap
->contains (lhs
))
2943 /* If LHS is an access to a local variable without address-taken
2944 (or when we allow data races) and known not to trap, we could
2945 always safely move down the store. */
2946 tree base
= get_base_address (lhs
);
2947 if (!auto_var_p (base
)
2948 || (TREE_ADDRESSABLE (base
) && !flag_store_data_races
)
2949 || tree_could_trap_p (lhs
))
2953 /* Now we've checked the constraints, so do the transformation:
2954 1) Remove the single store. */
2955 gsi
= gsi_for_stmt (assign
);
2956 unlink_stmt_vdef (assign
);
2957 gsi_remove (&gsi
, true);
2958 release_defs (assign
);
2960 /* Make both store and load use alias-set zero as we have to
2961 deal with the case of the store being a conditional change
2962 of the dynamic type. */
2963 lhs
= unshare_expr (lhs
);
2965 while (handled_component_p (*basep
))
2966 basep
= &TREE_OPERAND (*basep
, 0);
2967 if (TREE_CODE (*basep
) == MEM_REF
2968 || TREE_CODE (*basep
) == TARGET_MEM_REF
)
2969 TREE_OPERAND (*basep
, 1)
2970 = fold_convert (ptr_type_node
, TREE_OPERAND (*basep
, 1));
2972 *basep
= build2 (MEM_REF
, TREE_TYPE (*basep
),
2973 build_fold_addr_expr (*basep
),
2974 build_zero_cst (ptr_type_node
));
2976 /* 2) Insert a load from the memory of the store to the temporary
2977 on the edge which did not contain the store. */
2978 name
= make_temp_ssa_name (TREE_TYPE (lhs
), NULL
, "cstore");
2979 new_stmt
= gimple_build_assign (name
, lhs
);
2980 gimple_set_location (new_stmt
, locus
);
2981 lhs
= unshare_expr (lhs
);
2983 /* Set the no-warning bit on the rhs of the load to avoid uninit
2985 tree rhs1
= gimple_assign_rhs1 (new_stmt
);
2986 suppress_warning (rhs1
, OPT_Wuninitialized
);
2988 gsi_insert_on_edge (e1
, new_stmt
);
2990 /* 3) Create a PHI node at the join block, with one argument
2991 holding the old RHS, and the other holding the temporary
2992 where we stored the old memory contents. */
2993 name2
= make_temp_ssa_name (TREE_TYPE (lhs
), NULL
, "cstore");
2994 newphi
= create_phi_node (name2
, join_bb
);
2995 add_phi_arg (newphi
, rhs
, e0
, locus
);
2996 add_phi_arg (newphi
, name
, e1
, locus
);
2998 new_stmt
= gimple_build_assign (lhs
, PHI_RESULT (newphi
));
3000 /* 4) Insert that PHI node. */
3001 gsi
= gsi_after_labels (join_bb
);
3002 if (gsi_end_p (gsi
))
3004 gsi
= gsi_last_bb (join_bb
);
3005 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
3008 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
3010 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3012 fprintf (dump_file
, "\nConditional store replacement happened!");
3013 fprintf (dump_file
, "\nReplaced the store with a load.");
3014 fprintf (dump_file
, "\nInserted a new PHI statement in joint block:\n");
3015 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
);
3017 statistics_counter_event (cfun
, "conditional store replacement", 1);
3022 /* Do the main work of conditional store replacement. */
3025 cond_if_else_store_replacement_1 (basic_block then_bb
, basic_block else_bb
,
3026 basic_block join_bb
, gimple
*then_assign
,
3027 gimple
*else_assign
)
3029 tree lhs_base
, lhs
, then_rhs
, else_rhs
, name
;
3030 location_t then_locus
, else_locus
;
3031 gimple_stmt_iterator gsi
;
3035 if (then_assign
== NULL
3036 || !gimple_assign_single_p (then_assign
)
3037 || gimple_clobber_p (then_assign
)
3038 || gimple_has_volatile_ops (then_assign
)
3039 || else_assign
== NULL
3040 || !gimple_assign_single_p (else_assign
)
3041 || gimple_clobber_p (else_assign
)
3042 || gimple_has_volatile_ops (else_assign
))
3045 lhs
= gimple_assign_lhs (then_assign
);
3046 if (!is_gimple_reg_type (TREE_TYPE (lhs
))
3047 || !operand_equal_p (lhs
, gimple_assign_lhs (else_assign
), 0))
3050 lhs_base
= get_base_address (lhs
);
3051 if (lhs_base
== NULL_TREE
3052 || (!DECL_P (lhs_base
) && TREE_CODE (lhs_base
) != MEM_REF
))
3055 then_rhs
= gimple_assign_rhs1 (then_assign
);
3056 else_rhs
= gimple_assign_rhs1 (else_assign
);
3057 then_locus
= gimple_location (then_assign
);
3058 else_locus
= gimple_location (else_assign
);
3060 /* Now we've checked the constraints, so do the transformation:
3061 1) Remove the stores. */
3062 gsi
= gsi_for_stmt (then_assign
);
3063 unlink_stmt_vdef (then_assign
);
3064 gsi_remove (&gsi
, true);
3065 release_defs (then_assign
);
3067 gsi
= gsi_for_stmt (else_assign
);
3068 unlink_stmt_vdef (else_assign
);
3069 gsi_remove (&gsi
, true);
3070 release_defs (else_assign
);
3072 /* 2) Create a PHI node at the join block, with one argument
3073 holding the old RHS, and the other holding the temporary
3074 where we stored the old memory contents. */
3075 name
= make_temp_ssa_name (TREE_TYPE (lhs
), NULL
, "cstore");
3076 newphi
= create_phi_node (name
, join_bb
);
3077 add_phi_arg (newphi
, then_rhs
, EDGE_SUCC (then_bb
, 0), then_locus
);
3078 add_phi_arg (newphi
, else_rhs
, EDGE_SUCC (else_bb
, 0), else_locus
);
3080 new_stmt
= gimple_build_assign (lhs
, PHI_RESULT (newphi
));
3082 /* 3) Insert that PHI node. */
3083 gsi
= gsi_after_labels (join_bb
);
3084 if (gsi_end_p (gsi
))
3086 gsi
= gsi_last_bb (join_bb
);
3087 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
3090 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
3092 statistics_counter_event (cfun
, "if-then-else store replacement", 1);
3097 /* Return the single store in BB with VDEF or NULL if there are
3098 other stores in the BB or loads following the store. */
3101 single_trailing_store_in_bb (basic_block bb
, tree vdef
)
3103 if (SSA_NAME_IS_DEFAULT_DEF (vdef
))
3105 gimple
*store
= SSA_NAME_DEF_STMT (vdef
);
3106 if (gimple_bb (store
) != bb
3107 || gimple_code (store
) == GIMPLE_PHI
)
3110 /* Verify there is no other store in this BB. */
3111 if (!SSA_NAME_IS_DEFAULT_DEF (gimple_vuse (store
))
3112 && gimple_bb (SSA_NAME_DEF_STMT (gimple_vuse (store
))) == bb
3113 && gimple_code (SSA_NAME_DEF_STMT (gimple_vuse (store
))) != GIMPLE_PHI
)
3116 /* Verify there is no load or store after the store. */
3117 use_operand_p use_p
;
3118 imm_use_iterator imm_iter
;
3119 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_vdef (store
))
3120 if (USE_STMT (use_p
) != store
3121 && gimple_bb (USE_STMT (use_p
)) == bb
)
3127 /* Conditional store replacement. We already know
3128 that the recognized pattern looks like so:
3131 if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
3141 fallthrough (edge E0)
3145 We check that it is safe to sink the store to JOIN_BB by verifying that
3146 there are no read-after-write or write-after-write dependencies in
3147 THEN_BB and ELSE_BB. */
3150 cond_if_else_store_replacement (basic_block then_bb
, basic_block else_bb
,
3151 basic_block join_bb
)
3153 vec
<data_reference_p
> then_datarefs
, else_datarefs
;
3154 vec
<ddr_p
> then_ddrs
, else_ddrs
;
3155 gimple
*then_store
, *else_store
;
3156 bool found
, ok
= false, res
;
3157 struct data_dependence_relation
*ddr
;
3158 data_reference_p then_dr
, else_dr
;
3160 tree then_lhs
, else_lhs
;
3161 basic_block blocks
[3];
3163 /* Handle the case with single store in THEN_BB and ELSE_BB. That is
3164 cheap enough to always handle as it allows us to elide dependence
3167 for (gphi_iterator si
= gsi_start_phis (join_bb
); !gsi_end_p (si
);
3169 if (virtual_operand_p (gimple_phi_result (si
.phi ())))
3176 tree then_vdef
= PHI_ARG_DEF_FROM_EDGE (vphi
, single_succ_edge (then_bb
));
3177 tree else_vdef
= PHI_ARG_DEF_FROM_EDGE (vphi
, single_succ_edge (else_bb
));
3178 gimple
*then_assign
= single_trailing_store_in_bb (then_bb
, then_vdef
);
3181 gimple
*else_assign
= single_trailing_store_in_bb (else_bb
, else_vdef
);
3183 return cond_if_else_store_replacement_1 (then_bb
, else_bb
, join_bb
,
3184 then_assign
, else_assign
);
3187 /* If either vectorization or if-conversion is disabled then do
3188 not sink any stores. */
3189 if (param_max_stores_to_sink
== 0
3190 || (!flag_tree_loop_vectorize
&& !flag_tree_slp_vectorize
)
3191 || !flag_tree_loop_if_convert
)
3194 /* Find data references. */
3195 then_datarefs
.create (1);
3196 else_datarefs
.create (1);
3197 if ((find_data_references_in_bb (NULL
, then_bb
, &then_datarefs
)
3199 || !then_datarefs
.length ()
3200 || (find_data_references_in_bb (NULL
, else_bb
, &else_datarefs
)
3202 || !else_datarefs
.length ())
3204 free_data_refs (then_datarefs
);
3205 free_data_refs (else_datarefs
);
3209 /* Find pairs of stores with equal LHS. */
3210 auto_vec
<gimple
*, 1> then_stores
, else_stores
;
3211 FOR_EACH_VEC_ELT (then_datarefs
, i
, then_dr
)
3213 if (DR_IS_READ (then_dr
))
3216 then_store
= DR_STMT (then_dr
);
3217 then_lhs
= gimple_get_lhs (then_store
);
3218 if (then_lhs
== NULL_TREE
)
3222 FOR_EACH_VEC_ELT (else_datarefs
, j
, else_dr
)
3224 if (DR_IS_READ (else_dr
))
3227 else_store
= DR_STMT (else_dr
);
3228 else_lhs
= gimple_get_lhs (else_store
);
3229 if (else_lhs
== NULL_TREE
)
3232 if (operand_equal_p (then_lhs
, else_lhs
, 0))
3242 then_stores
.safe_push (then_store
);
3243 else_stores
.safe_push (else_store
);
3246 /* No pairs of stores found. */
3247 if (!then_stores
.length ()
3248 || then_stores
.length () > (unsigned) param_max_stores_to_sink
)
3250 free_data_refs (then_datarefs
);
3251 free_data_refs (else_datarefs
);
3255 /* Compute and check data dependencies in both basic blocks. */
3256 then_ddrs
.create (1);
3257 else_ddrs
.create (1);
3258 if (!compute_all_dependences (then_datarefs
, &then_ddrs
,
3260 || !compute_all_dependences (else_datarefs
, &else_ddrs
,
3263 free_dependence_relations (then_ddrs
);
3264 free_dependence_relations (else_ddrs
);
3265 free_data_refs (then_datarefs
);
3266 free_data_refs (else_datarefs
);
3269 blocks
[0] = then_bb
;
3270 blocks
[1] = else_bb
;
3271 blocks
[2] = join_bb
;
3272 renumber_gimple_stmt_uids_in_blocks (blocks
, 3);
3274 /* Check that there are no read-after-write or write-after-write dependencies
3276 FOR_EACH_VEC_ELT (then_ddrs
, i
, ddr
)
3278 struct data_reference
*dra
= DDR_A (ddr
);
3279 struct data_reference
*drb
= DDR_B (ddr
);
3281 if (DDR_ARE_DEPENDENT (ddr
) != chrec_known
3282 && ((DR_IS_READ (dra
) && DR_IS_WRITE (drb
)
3283 && gimple_uid (DR_STMT (dra
)) > gimple_uid (DR_STMT (drb
)))
3284 || (DR_IS_READ (drb
) && DR_IS_WRITE (dra
)
3285 && gimple_uid (DR_STMT (drb
)) > gimple_uid (DR_STMT (dra
)))
3286 || (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))))
3288 free_dependence_relations (then_ddrs
);
3289 free_dependence_relations (else_ddrs
);
3290 free_data_refs (then_datarefs
);
3291 free_data_refs (else_datarefs
);
3296 /* Check that there are no read-after-write or write-after-write dependencies
3298 FOR_EACH_VEC_ELT (else_ddrs
, i
, ddr
)
3300 struct data_reference
*dra
= DDR_A (ddr
);
3301 struct data_reference
*drb
= DDR_B (ddr
);
3303 if (DDR_ARE_DEPENDENT (ddr
) != chrec_known
3304 && ((DR_IS_READ (dra
) && DR_IS_WRITE (drb
)
3305 && gimple_uid (DR_STMT (dra
)) > gimple_uid (DR_STMT (drb
)))
3306 || (DR_IS_READ (drb
) && DR_IS_WRITE (dra
)
3307 && gimple_uid (DR_STMT (drb
)) > gimple_uid (DR_STMT (dra
)))
3308 || (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))))
3310 free_dependence_relations (then_ddrs
);
3311 free_dependence_relations (else_ddrs
);
3312 free_data_refs (then_datarefs
);
3313 free_data_refs (else_datarefs
);
3318 /* Sink stores with same LHS. */
3319 FOR_EACH_VEC_ELT (then_stores
, i
, then_store
)
3321 else_store
= else_stores
[i
];
3322 res
= cond_if_else_store_replacement_1 (then_bb
, else_bb
, join_bb
,
3323 then_store
, else_store
);
3327 free_dependence_relations (then_ddrs
);
3328 free_dependence_relations (else_ddrs
);
3329 free_data_refs (then_datarefs
);
3330 free_data_refs (else_datarefs
);
3335 /* Return TRUE if STMT has a VUSE whose corresponding VDEF is in BB. */
3338 local_mem_dependence (gimple
*stmt
, basic_block bb
)
3340 tree vuse
= gimple_vuse (stmt
);
3346 def
= SSA_NAME_DEF_STMT (vuse
);
3347 return (def
&& gimple_bb (def
) == bb
);
3350 /* Given a "diamond" control-flow pattern where BB0 tests a condition,
3351 BB1 and BB2 are "then" and "else" blocks dependent on this test,
3352 and BB3 rejoins control flow following BB1 and BB2, look for
3353 opportunities to hoist loads as follows. If BB3 contains a PHI of
3354 two loads, one each occurring in BB1 and BB2, and the loads are
3355 provably of adjacent fields in the same structure, then move both
3356 loads into BB0. Of course this can only be done if there are no
3357 dependencies preventing such motion.
3359 One of the hoisted loads will always be speculative, so the
3360 transformation is currently conservative:
3362 - The fields must be strictly adjacent.
3363 - The two fields must occupy a single memory block that is
3364 guaranteed to not cross a page boundary.
3366 The last is difficult to prove, as such memory blocks should be
3367 aligned on the minimum of the stack alignment boundary and the
3368 alignment guaranteed by heap allocation interfaces. Thus we rely
3369 on a parameter for the alignment value.
3371 Provided a good value is used for the last case, the first
3372 restriction could possibly be relaxed. */
3375 hoist_adjacent_loads (basic_block bb0
, basic_block bb1
,
3376 basic_block bb2
, basic_block bb3
)
3378 int param_align
= param_l1_cache_line_size
;
3379 unsigned param_align_bits
= (unsigned) (param_align
* BITS_PER_UNIT
);
3382 /* Walk the phis in bb3 looking for an opportunity. We are looking
3383 for phis of two SSA names, one each of which is defined in bb1 and
3385 for (gsi
= gsi_start_phis (bb3
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3387 gphi
*phi_stmt
= gsi
.phi ();
3388 gimple
*def1
, *def2
;
3389 tree arg1
, arg2
, ref1
, ref2
, field1
, field2
;
3390 tree tree_offset1
, tree_offset2
, tree_size2
, next
;
3391 int offset1
, offset2
, size2
;
3393 gimple_stmt_iterator gsi2
;
3394 basic_block bb_for_def1
, bb_for_def2
;
3396 if (gimple_phi_num_args (phi_stmt
) != 2
3397 || virtual_operand_p (gimple_phi_result (phi_stmt
)))
3400 arg1
= gimple_phi_arg_def (phi_stmt
, 0);
3401 arg2
= gimple_phi_arg_def (phi_stmt
, 1);
3403 if (TREE_CODE (arg1
) != SSA_NAME
3404 || TREE_CODE (arg2
) != SSA_NAME
3405 || SSA_NAME_IS_DEFAULT_DEF (arg1
)
3406 || SSA_NAME_IS_DEFAULT_DEF (arg2
))
3409 def1
= SSA_NAME_DEF_STMT (arg1
);
3410 def2
= SSA_NAME_DEF_STMT (arg2
);
3412 if ((gimple_bb (def1
) != bb1
|| gimple_bb (def2
) != bb2
)
3413 && (gimple_bb (def2
) != bb1
|| gimple_bb (def1
) != bb2
))
3416 /* Check the mode of the arguments to be sure a conditional move
3417 can be generated for it. */
3418 if (optab_handler (movcc_optab
, TYPE_MODE (TREE_TYPE (arg1
)))
3419 == CODE_FOR_nothing
)
3422 /* Both statements must be assignments whose RHS is a COMPONENT_REF. */
3423 if (!gimple_assign_single_p (def1
)
3424 || !gimple_assign_single_p (def2
)
3425 || gimple_has_volatile_ops (def1
)
3426 || gimple_has_volatile_ops (def2
))
3429 ref1
= gimple_assign_rhs1 (def1
);
3430 ref2
= gimple_assign_rhs1 (def2
);
3432 if (TREE_CODE (ref1
) != COMPONENT_REF
3433 || TREE_CODE (ref2
) != COMPONENT_REF
)
3436 /* The zeroth operand of the two component references must be
3437 identical. It is not sufficient to compare get_base_address of
3438 the two references, because this could allow for different
3439 elements of the same array in the two trees. It is not safe to
3440 assume that the existence of one array element implies the
3441 existence of a different one. */
3442 if (!operand_equal_p (TREE_OPERAND (ref1
, 0), TREE_OPERAND (ref2
, 0), 0))
3445 field1
= TREE_OPERAND (ref1
, 1);
3446 field2
= TREE_OPERAND (ref2
, 1);
3448 /* Check for field adjacency, and ensure field1 comes first. */
3449 for (next
= DECL_CHAIN (field1
);
3450 next
&& TREE_CODE (next
) != FIELD_DECL
;
3451 next
= DECL_CHAIN (next
))
3456 for (next
= DECL_CHAIN (field2
);
3457 next
&& TREE_CODE (next
) != FIELD_DECL
;
3458 next
= DECL_CHAIN (next
))
3464 std::swap (field1
, field2
);
3465 std::swap (def1
, def2
);
3468 bb_for_def1
= gimple_bb (def1
);
3469 bb_for_def2
= gimple_bb (def2
);
3471 /* Check for proper alignment of the first field. */
3472 tree_offset1
= bit_position (field1
);
3473 tree_offset2
= bit_position (field2
);
3474 tree_size2
= DECL_SIZE (field2
);
3476 if (!tree_fits_uhwi_p (tree_offset1
)
3477 || !tree_fits_uhwi_p (tree_offset2
)
3478 || !tree_fits_uhwi_p (tree_size2
))
3481 offset1
= tree_to_uhwi (tree_offset1
);
3482 offset2
= tree_to_uhwi (tree_offset2
);
3483 size2
= tree_to_uhwi (tree_size2
);
3484 align1
= DECL_ALIGN (field1
) % param_align_bits
;
3486 if (offset1
% BITS_PER_UNIT
!= 0)
3489 /* For profitability, the two field references should fit within
3490 a single cache line. */
3491 if (align1
+ offset2
- offset1
+ size2
> param_align_bits
)
3494 /* The two expressions cannot be dependent upon vdefs defined
3496 if (local_mem_dependence (def1
, bb_for_def1
)
3497 || local_mem_dependence (def2
, bb_for_def2
))
3500 /* The conditions are satisfied; hoist the loads from bb1 and bb2 into
3501 bb0. We hoist the first one first so that a cache miss is handled
3502 efficiently regardless of hardware cache-fill policy. */
3503 gsi2
= gsi_for_stmt (def1
);
3504 gsi_move_to_bb_end (&gsi2
, bb0
);
3505 gsi2
= gsi_for_stmt (def2
);
3506 gsi_move_to_bb_end (&gsi2
, bb0
);
3507 statistics_counter_event (cfun
, "hoisted loads", 1);
3509 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3512 "\nHoisting adjacent loads from %d and %d into %d: \n",
3513 bb_for_def1
->index
, bb_for_def2
->index
, bb0
->index
);
3514 print_gimple_stmt (dump_file
, def1
, 0, TDF_VOPS
|TDF_MEMSYMS
);
3515 print_gimple_stmt (dump_file
, def2
, 0, TDF_VOPS
|TDF_MEMSYMS
);
3520 /* Determine whether we should attempt to hoist adjacent loads out of
3521 diamond patterns in pass_phiopt. Always hoist loads if
3522 -fhoist-adjacent-loads is specified and the target machine has
3523 both a conditional move instruction and a defined cache line size. */
3526 gate_hoist_loads (void)
3528 return (flag_hoist_adjacent_loads
== 1
3529 && param_l1_cache_line_size
3530 && HAVE_conditional_move
);
3533 /* This pass tries to replaces an if-then-else block with an
3534 assignment. We have four kinds of transformations. Some of these
3535 transformations are also performed by the ifcvt RTL optimizer.
3537 Conditional Replacement
3538 -----------------------
3540 This transformation, implemented in match_simplify_replacement,
3544 if (cond) goto bb2; else goto bb1;
3547 x = PHI <0 (bb1), 1 (bb0), ...>;
3555 x = PHI <x' (bb0), ...>;
3557 We remove bb1 as it becomes unreachable. This occurs often due to
3558 gimplification of conditionals.
3563 This transformation, implemented in value_replacement, replaces
3566 if (a != b) goto bb2; else goto bb1;
3569 x = PHI <a (bb1), b (bb0), ...>;
3575 x = PHI <b (bb0), ...>;
3577 This opportunity can sometimes occur as a result of other
3581 Another case caught by value replacement looks like this:
3587 if (t3 != 0) goto bb1; else goto bb2;
3603 This transformation, implemented in match_simplify_replacement, replaces
3606 if (a >= 0) goto bb2; else goto bb1;
3610 x = PHI <x (bb1), a (bb0), ...>;
3617 x = PHI <x' (bb0), ...>;
3622 This transformation, minmax_replacement replaces
3625 if (a <= b) goto bb2; else goto bb1;
3628 x = PHI <b (bb1), a (bb0), ...>;
3633 x' = MIN_EXPR (a, b)
3635 x = PHI <x' (bb0), ...>;
3637 A similar transformation is done for MAX_EXPR.
3640 This pass also performs a fifth transformation of a slightly different
3643 Factor conversion in COND_EXPR
3644 ------------------------------
3646 This transformation factors the conversion out of COND_EXPR with
3647 factor_out_conditional_conversion.
3650 if (a <= CST) goto <bb 3>; else goto <bb 4>;
3654 tmp = PHI <tmp, CST>
3657 if (a <= CST) goto <bb 3>; else goto <bb 4>;
3663 Adjacent Load Hoisting
3664 ----------------------
3666 This transformation replaces
3669 if (...) goto bb2; else goto bb1;
3671 x1 = (<expr>).field1;
3674 x2 = (<expr>).field2;
3681 x1 = (<expr>).field1;
3682 x2 = (<expr>).field2;
3683 if (...) goto bb2; else goto bb1;
3690 The purpose of this transformation is to enable generation of conditional
3691 move instructions such as Intel CMOVE or PowerPC ISEL. Because one of
3692 the loads is speculative, the transformation is restricted to very
3693 specific cases to avoid introducing a page fault. We are looking for
3701 where left and right are typically adjacent pointers in a tree structure. */
3705 const pass_data pass_data_phiopt
=
3707 GIMPLE_PASS
, /* type */
3708 "phiopt", /* name */
3709 OPTGROUP_NONE
, /* optinfo_flags */
3710 TV_TREE_PHIOPT
, /* tv_id */
3711 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3712 0, /* properties_provided */
3713 0, /* properties_destroyed */
3714 0, /* todo_flags_start */
3715 0, /* todo_flags_finish */
3718 class pass_phiopt
: public gimple_opt_pass
3721 pass_phiopt (gcc::context
*ctxt
)
3722 : gimple_opt_pass (pass_data_phiopt
, ctxt
), early_p (false)
3725 /* opt_pass methods: */
3726 opt_pass
* clone () { return new pass_phiopt (m_ctxt
); }
3727 void set_pass_param (unsigned n
, bool param
)
3729 gcc_assert (n
== 0);
3732 virtual bool gate (function
*) { return flag_ssa_phiopt
; }
3733 virtual unsigned int execute (function
*)
3735 return tree_ssa_phiopt_worker (false,
3736 !early_p
? gate_hoist_loads () : false,
3742 }; // class pass_phiopt
3747 make_pass_phiopt (gcc::context
*ctxt
)
3749 return new pass_phiopt (ctxt
);
3754 const pass_data pass_data_cselim
=
3756 GIMPLE_PASS
, /* type */
3757 "cselim", /* name */
3758 OPTGROUP_NONE
, /* optinfo_flags */
3759 TV_TREE_PHIOPT
, /* tv_id */
3760 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3761 0, /* properties_provided */
3762 0, /* properties_destroyed */
3763 0, /* todo_flags_start */
3764 0, /* todo_flags_finish */
3767 class pass_cselim
: public gimple_opt_pass
3770 pass_cselim (gcc::context
*ctxt
)
3771 : gimple_opt_pass (pass_data_cselim
, ctxt
)
3774 /* opt_pass methods: */
3775 virtual bool gate (function
*) { return flag_tree_cselim
; }
3776 virtual unsigned int execute (function
*) { return tree_ssa_cs_elim (); }
3778 }; // class pass_cselim
3783 make_pass_cselim (gcc::context
*ctxt
)
3785 return new pass_cselim (ctxt
);