1 /* Optimization of PHI nodes by converting them into straightline code.
2 Copyright (C) 2004-2024 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"
55 #include "tree-ssa-propagate.h"
56 #include "tree-ssa-dce.h"
58 /* Return the singleton PHI in the SEQ of PHIs for edges E0 and E1. */
61 single_non_singleton_phi_for_edges (gimple_seq seq
, edge e0
, edge e1
)
63 gimple_stmt_iterator i
;
65 for (i
= gsi_start (seq
); !gsi_end_p (i
); gsi_next (&i
))
67 gphi
*p
= as_a
<gphi
*> (gsi_stmt (i
));
68 /* If the PHI arguments are equal then we can skip this PHI. */
69 if (operand_equal_for_phi_arg_p (gimple_phi_arg_def (p
, e0
->dest_idx
),
70 gimple_phi_arg_def (p
, e1
->dest_idx
)))
73 /* Punt on virtual phis with different arguments from the edges. */
74 if (virtual_operand_p (gimple_phi_result (p
)))
77 /* If we already have a PHI that has the two edge arguments are
78 different, then return it is not a singleton for these PHIs. */
87 /* Replace PHI node element whose edge is E in block BB with variable NEW.
88 Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
89 is known to have two edges, one of which must reach BB). */
92 replace_phi_edge_with_variable (basic_block cond_block
,
93 edge e
, gphi
*phi
, tree new_tree
,
94 bitmap dce_ssa_names
= nullptr)
96 basic_block bb
= gimple_bb (phi
);
97 gimple_stmt_iterator gsi
;
98 tree phi_result
= PHI_RESULT (phi
);
99 bool deleteboth
= false;
101 /* Duplicate range info if they are the only things setting the target PHI.
102 This is needed as later on, the new_tree will be replacing
103 The assignement of the PHI.
114 And _4 gets propagated into the use of a_3 and losing the range info.
115 This can't be done for more than 2 incoming edges as the propagation
117 The new_tree needs to be defined in the same basic block as the conditional. */
118 if (TREE_CODE (new_tree
) == SSA_NAME
119 && EDGE_COUNT (gimple_bb (phi
)->preds
) == 2
120 && INTEGRAL_TYPE_P (TREE_TYPE (phi_result
))
121 && !SSA_NAME_RANGE_INFO (new_tree
)
122 && SSA_NAME_RANGE_INFO (phi_result
)
123 && gimple_bb (SSA_NAME_DEF_STMT (new_tree
)) == cond_block
124 && dbg_cnt (phiopt_edge_range
))
125 duplicate_ssa_name_range_info (new_tree
, phi_result
);
127 /* Change the PHI argument to new. */
128 SET_USE (PHI_ARG_DEF_PTR (phi
, e
->dest_idx
), new_tree
);
130 /* Remove the empty basic block. */
131 edge edge_to_remove
= NULL
, keep_edge
= NULL
;
132 if (EDGE_SUCC (cond_block
, 0)->dest
== bb
)
134 edge_to_remove
= EDGE_SUCC (cond_block
, 1);
135 keep_edge
= EDGE_SUCC (cond_block
, 0);
137 else if (EDGE_SUCC (cond_block
, 1)->dest
== bb
)
139 edge_to_remove
= EDGE_SUCC (cond_block
, 0);
140 keep_edge
= EDGE_SUCC (cond_block
, 1);
142 else if ((keep_edge
= find_edge (cond_block
, e
->src
)))
144 basic_block bb1
= EDGE_SUCC (cond_block
, 0)->dest
;
145 basic_block bb2
= EDGE_SUCC (cond_block
, 1)->dest
;
146 if (single_pred_p (bb1
) && single_pred_p (bb2
)
147 && single_succ_p (bb1
) && single_succ_p (bb2
)
148 && empty_block_p (bb1
) && empty_block_p (bb2
))
154 if (edge_to_remove
&& EDGE_COUNT (edge_to_remove
->dest
->preds
) == 1)
156 e
->flags
|= EDGE_FALLTHRU
;
157 e
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
158 e
->probability
= profile_probability::always ();
159 delete_basic_block (edge_to_remove
->dest
);
161 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
162 gsi
= gsi_last_bb (cond_block
);
163 gsi_remove (&gsi
, true);
167 basic_block bb1
= EDGE_SUCC (cond_block
, 0)->dest
;
168 basic_block bb2
= EDGE_SUCC (cond_block
, 1)->dest
;
170 edge newedge
= redirect_edge_and_branch (keep_edge
, bb
);
172 /* The new edge should be the same. */
173 gcc_assert (newedge
== keep_edge
);
175 keep_edge
->flags
|= EDGE_FALLTHRU
;
176 keep_edge
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
177 keep_edge
->probability
= profile_probability::always ();
179 /* Copy the edge's phi entry from the old one. */
180 copy_phi_arg_into_existing_phi (e
, keep_edge
);
182 /* Delete the old 2 empty basic blocks */
183 delete_basic_block (bb1
);
184 delete_basic_block (bb2
);
186 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
187 gsi
= gsi_last_bb (cond_block
);
188 gsi_remove (&gsi
, true);
192 /* If there are other edges into the middle block make
193 CFG cleanup deal with the edge removal to avoid
194 updating dominators here in a non-trivial way. */
195 gcond
*cond
= as_a
<gcond
*> (*gsi_last_bb (cond_block
));
196 if (keep_edge
->flags
& EDGE_FALSE_VALUE
)
197 gimple_cond_make_false (cond
);
198 else if (keep_edge
->flags
& EDGE_TRUE_VALUE
)
199 gimple_cond_make_true (cond
);
203 simple_dce_from_worklist (dce_ssa_names
);
205 statistics_counter_event (cfun
, "Replace PHI with variable", 1);
207 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
209 "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
214 /* PR66726: Factor operations out of COND_EXPR. If the arguments of the PHI
215 stmt are CONVERT_STMT, factor out the conversion and perform the conversion
216 to the result of PHI stmt. COND_STMT is the controlling predicate.
217 Return the newly-created PHI, if any. */
220 factor_out_conditional_operation (edge e0
, edge e1
, gphi
*phi
,
221 tree arg0
, tree arg1
, gimple
*cond_stmt
)
223 gimple
*arg0_def_stmt
= NULL
, *arg1_def_stmt
= NULL
, *new_stmt
;
224 tree new_arg0
= NULL_TREE
, new_arg1
= NULL_TREE
;
227 gimple_stmt_iterator gsi
, gsi_for_def
;
228 location_t locus
= gimple_location (phi
);
229 enum tree_code op_code
;
231 /* Handle only PHI statements with two arguments. TODO: If all
232 other arguments to PHI are INTEGER_CST or if their defining
233 statement have the same unary operation, we can handle more
234 than two arguments too. */
235 if (gimple_phi_num_args (phi
) != 2)
238 /* First canonicalize to simplify tests. */
239 if (TREE_CODE (arg0
) != SSA_NAME
)
241 std::swap (arg0
, arg1
);
245 if (TREE_CODE (arg0
) != SSA_NAME
246 || (TREE_CODE (arg1
) != SSA_NAME
247 && TREE_CODE (arg1
) != INTEGER_CST
))
250 /* Check if arg0 is an SSA_NAME and the stmt which defines arg0 is
251 an unary operation. */
252 arg0_def_stmt
= SSA_NAME_DEF_STMT (arg0
);
253 if (!is_gimple_assign (arg0_def_stmt
)
254 || (gimple_assign_rhs_class (arg0_def_stmt
) != GIMPLE_UNARY_RHS
255 && gimple_assign_rhs_code (arg0_def_stmt
) != VIEW_CONVERT_EXPR
))
258 /* Use the RHS as new_arg0. */
259 op_code
= gimple_assign_rhs_code (arg0_def_stmt
);
260 new_arg0
= gimple_assign_rhs1 (arg0_def_stmt
);
261 if (op_code
== VIEW_CONVERT_EXPR
)
263 new_arg0
= TREE_OPERAND (new_arg0
, 0);
264 if (!is_gimple_reg_type (TREE_TYPE (new_arg0
)))
267 if (TREE_CODE (new_arg0
) == SSA_NAME
268 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_arg0
))
271 if (TREE_CODE (arg1
) == SSA_NAME
)
273 /* Check if arg1 is an SSA_NAME and the stmt which defines arg1
274 is an unary operation. */
275 arg1_def_stmt
= SSA_NAME_DEF_STMT (arg1
);
276 if (!is_gimple_assign (arg1_def_stmt
)
277 || gimple_assign_rhs_code (arg1_def_stmt
) != op_code
)
280 /* Either arg1_def_stmt or arg0_def_stmt should be conditional. */
281 if (dominated_by_p (CDI_DOMINATORS
, gimple_bb (phi
), gimple_bb (arg0_def_stmt
))
282 && dominated_by_p (CDI_DOMINATORS
,
283 gimple_bb (phi
), gimple_bb (arg1_def_stmt
)))
286 /* Use the RHS as new_arg1. */
287 new_arg1
= gimple_assign_rhs1 (arg1_def_stmt
);
288 if (op_code
== VIEW_CONVERT_EXPR
)
289 new_arg1
= TREE_OPERAND (new_arg1
, 0);
290 if (TREE_CODE (new_arg1
) == SSA_NAME
291 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_arg1
))
296 /* TODO: handle more than just casts here. */
297 if (!gimple_assign_cast_p (arg0_def_stmt
))
300 /* arg0_def_stmt should be conditional. */
301 if (dominated_by_p (CDI_DOMINATORS
, gimple_bb (phi
), gimple_bb (arg0_def_stmt
)))
303 /* If arg1 is an INTEGER_CST, fold it to new type. */
304 if (INTEGRAL_TYPE_P (TREE_TYPE (new_arg0
))
305 && (int_fits_type_p (arg1
, TREE_TYPE (new_arg0
))
306 || (TYPE_PRECISION (TREE_TYPE (new_arg0
))
307 == TYPE_PRECISION (TREE_TYPE (arg1
)))))
309 if (gimple_assign_cast_p (arg0_def_stmt
))
311 /* For the INTEGER_CST case, we are just moving the
312 conversion from one place to another, which can often
313 hurt as the conversion moves further away from the
314 statement that computes the value. So, perform this
315 only if new_arg0 is an operand of COND_STMT, or
316 if arg0_def_stmt is the only non-debug stmt in
317 its basic block, because then it is possible this
318 could enable further optimizations (minmax replacement
320 Note no-op conversions don't have this issue as
321 it will not generate any zero/sign extend in that case. */
322 if ((TYPE_PRECISION (TREE_TYPE (new_arg0
))
323 != TYPE_PRECISION (TREE_TYPE (arg1
)))
324 && new_arg0
!= gimple_cond_lhs (cond_stmt
)
325 && new_arg0
!= gimple_cond_rhs (cond_stmt
)
326 && gimple_bb (arg0_def_stmt
) == e0
->src
)
328 gsi
= gsi_for_stmt (arg0_def_stmt
);
329 gsi_prev_nondebug (&gsi
);
330 if (!gsi_end_p (gsi
))
333 = dyn_cast
<gassign
*> (gsi_stmt (gsi
)))
335 tree lhs
= gimple_assign_lhs (assign
);
336 enum tree_code ass_code
337 = gimple_assign_rhs_code (assign
);
338 if (ass_code
!= MAX_EXPR
&& ass_code
!= MIN_EXPR
)
340 if (lhs
!= gimple_assign_rhs1 (arg0_def_stmt
))
342 gsi_prev_nondebug (&gsi
);
343 if (!gsi_end_p (gsi
))
349 gsi
= gsi_for_stmt (arg0_def_stmt
);
350 gsi_next_nondebug (&gsi
);
351 if (!gsi_end_p (gsi
))
354 new_arg1
= fold_convert (TREE_TYPE (new_arg0
), arg1
);
356 /* Drop the overlow that fold_convert might add. */
357 if (TREE_OVERFLOW (new_arg1
))
358 new_arg1
= drop_tree_overflow (new_arg1
);
367 /* If arg0/arg1 have > 1 use, then this transformation actually increases
368 the number of expressions evaluated at runtime. */
369 if (!has_single_use (arg0
)
370 || (arg1_def_stmt
&& !has_single_use (arg1
)))
373 /* If types of new_arg0 and new_arg1 are different bailout. */
374 if (!types_compatible_p (TREE_TYPE (new_arg0
), TREE_TYPE (new_arg1
)))
377 /* Create a new PHI stmt. */
378 result
= PHI_RESULT (phi
);
379 temp
= make_ssa_name (TREE_TYPE (new_arg0
), NULL
);
380 newphi
= create_phi_node (temp
, gimple_bb (phi
));
382 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
384 fprintf (dump_file
, "PHI ");
385 print_generic_expr (dump_file
, gimple_phi_result (phi
));
387 " changed to factor operation out from COND_EXPR.\n");
388 fprintf (dump_file
, "New stmt with OPERATION that defines ");
389 print_generic_expr (dump_file
, result
);
390 fprintf (dump_file
, ".\n");
393 /* Remove the old operation(s) that has single use. */
394 gsi_for_def
= gsi_for_stmt (arg0_def_stmt
);
395 gsi_remove (&gsi_for_def
, true);
396 release_defs (arg0_def_stmt
);
400 gsi_for_def
= gsi_for_stmt (arg1_def_stmt
);
401 gsi_remove (&gsi_for_def
, true);
402 release_defs (arg1_def_stmt
);
405 add_phi_arg (newphi
, new_arg0
, e0
, locus
);
406 add_phi_arg (newphi
, new_arg1
, e1
, locus
);
408 /* Create the operation stmt and insert it. */
409 if (op_code
== VIEW_CONVERT_EXPR
)
411 temp
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (result
), temp
);
412 new_stmt
= gimple_build_assign (result
, temp
);
415 new_stmt
= gimple_build_assign (result
, op_code
, temp
);
416 gsi
= gsi_after_labels (gimple_bb (phi
));
417 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
419 /* Remove the original PHI stmt. */
420 gsi
= gsi_for_stmt (phi
);
421 gsi_remove (&gsi
, true);
423 statistics_counter_event (cfun
, "factored out operation", 1);
429 /* Return TRUE if SEQ/OP pair should be allowed during early phiopt.
430 Currently this is to allow MIN/MAX and ABS/NEGATE and constants. */
432 phiopt_early_allow (gimple_seq
&seq
, gimple_match_op
&op
)
434 /* Don't allow functions. */
435 if (!op
.code
.is_tree_code ())
437 tree_code code
= (tree_code
)op
.code
;
439 /* For non-empty sequence, only allow one statement
440 except for MIN/MAX, allow max 2 statements,
441 each with MIN/MAX. */
442 if (!gimple_seq_empty_p (seq
))
444 if (code
== MIN_EXPR
|| code
== MAX_EXPR
)
446 if (!gimple_seq_singleton_p (seq
))
449 gimple
*stmt
= gimple_seq_first_stmt (seq
);
450 /* Only allow assignments. */
451 if (!is_gimple_assign (stmt
))
453 code
= gimple_assign_rhs_code (stmt
);
454 return code
== MIN_EXPR
|| code
== MAX_EXPR
;
456 /* Check to make sure op was already a SSA_NAME. */
457 if (code
!= SSA_NAME
)
459 if (!gimple_seq_singleton_p (seq
))
461 gimple
*stmt
= gimple_seq_first_stmt (seq
);
462 /* Only allow assignments. */
463 if (!is_gimple_assign (stmt
))
465 if (gimple_assign_lhs (stmt
) != op
.ops
[0])
467 code
= gimple_assign_rhs_code (stmt
);
489 /* gimple_simplify_phiopt is like gimple_simplify but designed for PHIOPT.
490 Return NULL if nothing can be simplified or the resulting simplified value
491 with parts pushed if EARLY_P was true. Also rejects non allowed tree code
493 Takes the comparison from COMP_STMT and two args, ARG0 and ARG1 and tries
494 to simplify CMP ? ARG0 : ARG1.
495 Also try to simplify (!CMP) ? ARG1 : ARG0 if the non-inverse failed. */
497 gimple_simplify_phiopt (bool early_p
, tree type
, gimple
*comp_stmt
,
498 tree arg0
, tree arg1
,
501 gimple_seq seq1
= NULL
;
502 enum tree_code comp_code
= gimple_cond_code (comp_stmt
);
503 location_t loc
= gimple_location (comp_stmt
);
504 tree cmp0
= gimple_cond_lhs (comp_stmt
);
505 tree cmp1
= gimple_cond_rhs (comp_stmt
);
506 /* To handle special cases like floating point comparison, it is easier and
507 less error-prone to build a tree and gimplify it on the fly though it is
509 Don't use fold_build2 here as that might create (bool)a instead of just
511 tree cond
= build2_loc (loc
, comp_code
, boolean_type_node
,
514 if (dump_file
&& (dump_flags
& TDF_FOLDING
))
516 fprintf (dump_file
, "\nphiopt match-simplify trying:\n\t");
517 print_generic_expr (dump_file
, cond
);
518 fprintf (dump_file
, " ? ");
519 print_generic_expr (dump_file
, arg0
);
520 fprintf (dump_file
, " : ");
521 print_generic_expr (dump_file
, arg1
);
522 fprintf (dump_file
, "\n");
525 gimple_match_op
op (gimple_match_cond::UNCOND
,
526 COND_EXPR
, type
, cond
, arg0
, arg1
);
528 if (op
.resimplify (&seq1
, follow_all_ssa_edges
))
530 bool allowed
= !early_p
|| phiopt_early_allow (seq1
, op
);
531 tree result
= maybe_push_res_to_seq (&op
, &seq1
);
532 if (dump_file
&& (dump_flags
& TDF_FOLDING
))
534 fprintf (dump_file
, "\nphiopt match-simplify back:\n");
536 print_gimple_seq (dump_file
, seq1
, 0, TDF_VOPS
|TDF_MEMSYMS
);
537 fprintf (dump_file
, "result: ");
539 print_generic_expr (dump_file
, result
);
541 fprintf (dump_file
, " (none)");
542 fprintf (dump_file
, "\n");
544 fprintf (dump_file
, "rejected because early\n");
546 /* Early we want only to allow some generated tree codes. */
547 if (allowed
&& result
)
549 if (loc
!= UNKNOWN_LOCATION
)
550 annotate_all_with_location (seq1
, loc
);
551 gimple_seq_add_seq_without_update (seq
, seq1
);
555 gimple_seq_discard (seq1
);
558 /* Try the inverted comparison, that is !COMP ? ARG1 : ARG0. */
559 comp_code
= invert_tree_comparison (comp_code
, HONOR_NANS (cmp0
));
561 if (comp_code
== ERROR_MARK
)
564 cond
= build2_loc (loc
,
565 comp_code
, boolean_type_node
,
568 if (dump_file
&& (dump_flags
& TDF_FOLDING
))
570 fprintf (dump_file
, "\nphiopt match-simplify trying:\n\t");
571 print_generic_expr (dump_file
, cond
);
572 fprintf (dump_file
, " ? ");
573 print_generic_expr (dump_file
, arg1
);
574 fprintf (dump_file
, " : ");
575 print_generic_expr (dump_file
, arg0
);
576 fprintf (dump_file
, "\n");
579 gimple_match_op
op1 (gimple_match_cond::UNCOND
,
580 COND_EXPR
, type
, cond
, arg1
, arg0
);
582 if (op1
.resimplify (&seq1
, follow_all_ssa_edges
))
584 bool allowed
= !early_p
|| phiopt_early_allow (seq1
, op1
);
585 tree result
= maybe_push_res_to_seq (&op1
, &seq1
);
586 if (dump_file
&& (dump_flags
& TDF_FOLDING
))
588 fprintf (dump_file
, "\nphiopt match-simplify back:\n");
590 print_gimple_seq (dump_file
, seq1
, 0, TDF_VOPS
|TDF_MEMSYMS
);
591 fprintf (dump_file
, "result: ");
593 print_generic_expr (dump_file
, result
);
595 fprintf (dump_file
, " (none)");
596 fprintf (dump_file
, "\n");
598 fprintf (dump_file
, "rejected because early\n");
600 /* Early we want only to allow some generated tree codes. */
601 if (allowed
&& result
)
603 if (loc
!= UNKNOWN_LOCATION
)
604 annotate_all_with_location (seq1
, loc
);
605 gimple_seq_add_seq_without_update (seq
, seq1
);
609 gimple_seq_discard (seq1
);
614 /* empty_bb_or_one_feeding_into_p returns true if bb was empty basic block
615 or it has one cheap preparation statement that feeds into the PHI
616 statement and it sets STMT to that statement. */
618 empty_bb_or_one_feeding_into_p (basic_block bb
,
623 gimple
*stmt_to_move
= nullptr;
626 if (empty_block_p (bb
))
629 if (!single_pred_p (bb
))
632 /* The middle bb cannot have phi nodes as we don't
633 move those assignments yet. */
634 if (!gimple_seq_empty_p (phi_nodes (bb
)))
637 gimple_stmt_iterator gsi
;
639 gsi
= gsi_start_nondebug_after_labels_bb (bb
);
640 while (!gsi_end_p (gsi
))
642 gimple
*s
= gsi_stmt (gsi
);
643 gsi_next_nondebug (&gsi
);
644 /* Skip over Predict and nop statements. */
645 if (gimple_code (s
) == GIMPLE_PREDICT
646 || gimple_code (s
) == GIMPLE_NOP
)
648 /* If there is more one statement return false. */
654 /* The only statement here was a Predict or a nop statement
659 if (gimple_vuse (stmt_to_move
))
662 if (gimple_could_trap_p (stmt_to_move
)
663 || gimple_has_side_effects (stmt_to_move
))
668 FOR_EACH_SSA_TREE_OPERAND (use
, stmt_to_move
, it
, SSA_OP_USE
)
669 if (ssa_name_maybe_undef_p (use
))
672 /* Allow assignments but allow some builtin/internal calls.
673 As const calls don't match any of the above, yet they could
674 still have some side-effects - they could contain
675 gimple_could_trap_p statements, like floating point
676 exceptions or integer division by zero. See PR70586.
677 FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
679 Allow some known builtin/internal calls that are known not to
680 trap: logical functions (e.g. bswap and bit counting). */
681 if (!is_gimple_assign (stmt_to_move
))
683 if (!is_gimple_call (stmt_to_move
))
685 combined_fn cfn
= gimple_call_combined_fn (stmt_to_move
);
690 case CFN_BUILT_IN_BSWAP16
:
691 case CFN_BUILT_IN_BSWAP32
:
692 case CFN_BUILT_IN_BSWAP64
:
693 case CFN_BUILT_IN_BSWAP128
:
699 case CFN_BUILT_IN_CLRSB
:
700 case CFN_BUILT_IN_CLRSBL
:
701 case CFN_BUILT_IN_CLRSBLL
:
702 lhs
= gimple_call_lhs (stmt_to_move
);
707 lhs
= gimple_assign_lhs (stmt_to_move
);
712 /* Allow only a statement which feeds into the other stmt. */
713 if (!lhs
|| TREE_CODE (lhs
) != SSA_NAME
714 || !single_imm_use (lhs
, &use_p
, &use_stmt
)
722 /* Move STMT to before GSI and insert its defining
723 name into INSERTED_EXPRS bitmap. */
725 move_stmt (gimple
*stmt
, gimple_stmt_iterator
*gsi
, auto_bitmap
&inserted_exprs
)
729 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
731 fprintf (dump_file
, "statement un-sinked:\n");
732 print_gimple_stmt (dump_file
, stmt
, 0,
733 TDF_VOPS
|TDF_MEMSYMS
);
736 tree name
= gimple_get_lhs (stmt
);
737 // Mark the name to be renamed if there is one.
738 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (name
));
739 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt
);
740 gsi_move_before (&gsi1
, gsi
);
741 reset_flow_sensitive_info (name
);
744 /* RAII style class to temporarily remove flow sensitive
745 from ssa names defined by a gimple statement. */
746 class auto_flow_sensitive
749 auto_flow_sensitive (gimple
*s
);
750 ~auto_flow_sensitive ();
752 auto_vec
<std::pair
<tree
, flow_sensitive_info_storage
>, 2> stack
;
755 /* Constructor for auto_flow_sensitive. Saves
756 off the ssa names' flow sensitive information
757 that was defined by gimple statement S and
758 resets it to be non-flow based ones. */
760 auto_flow_sensitive::auto_flow_sensitive (gimple
*s
)
766 FOR_EACH_SSA_TREE_OPERAND (def
, s
, it
, SSA_OP_DEF
)
768 flow_sensitive_info_storage storage
;
769 storage
.save_and_clear (def
);
770 stack
.safe_push (std::make_pair (def
, storage
));
774 /* Deconstructor, restores the flow sensitive information
775 for the SSA names that had been saved off. */
777 auto_flow_sensitive::~auto_flow_sensitive ()
780 p
.second
.restore (p
.first
);
783 /* The function match_simplify_replacement does the main work of doing the
784 replacement using match and simplify. Return true if the replacement is done.
785 Otherwise return false.
786 BB is the basic block where the replacement is going to be done on. ARG0
787 is argument 0 from PHI. Likewise for ARG1. */
790 match_simplify_replacement (basic_block cond_bb
, basic_block middle_bb
,
791 basic_block middle_bb_alt
,
792 edge e0
, edge e1
, gphi
*phi
,
793 tree arg0
, tree arg1
, bool early_p
,
797 gimple_stmt_iterator gsi
;
798 edge true_edge
, false_edge
;
799 gimple_seq seq
= NULL
;
801 gimple
*stmt_to_move
= NULL
;
802 gimple
*stmt_to_move_alt
= NULL
;
803 tree arg_true
, arg_false
;
805 /* Special case A ? B : B as this will always simplify to B. */
806 if (operand_equal_for_phi_arg_p (arg0
, arg1
))
809 /* If the basic block only has a cheap preparation statement,
810 allow it and move it once the transformation is done. */
811 if (!empty_bb_or_one_feeding_into_p (middle_bb
, phi
, stmt_to_move
))
815 && middle_bb
!= middle_bb_alt
816 && !empty_bb_or_one_feeding_into_p (middle_bb_alt
, phi
,
820 /* At this point we know we have a GIMPLE_COND with two successors.
821 One successor is BB, the other successor is an empty block which
822 falls through into BB.
824 There is a single PHI node at the join point (BB).
826 So, given the condition COND, and the two PHI arguments, match and simplify
827 can happen on (COND) ? arg0 : arg1. */
829 stmt
= last_nondebug_stmt (cond_bb
);
831 /* We need to know which is the true edge and which is the false
832 edge so that we know when to invert the condition below. */
833 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
835 /* Forward the edges over the middle basic block. */
836 if (true_edge
->dest
== middle_bb
)
837 true_edge
= EDGE_SUCC (true_edge
->dest
, 0);
838 if (false_edge
->dest
== middle_bb
)
839 false_edge
= EDGE_SUCC (false_edge
->dest
, 0);
841 /* When THREEWAY_P then e1 will point to the edge of the final transition
842 from middle-bb to end. */
846 gcc_assert (false_edge
== e1
);
852 gcc_assert (false_edge
== e0
);
854 gcc_assert (true_edge
== e1
);
859 /* Do not make conditional undefs unconditional. */
860 if ((TREE_CODE (arg_true
) == SSA_NAME
861 && ssa_name_maybe_undef_p (arg_true
))
862 || (TREE_CODE (arg_false
) == SSA_NAME
863 && ssa_name_maybe_undef_p (arg_false
)))
866 tree type
= TREE_TYPE (gimple_phi_result (phi
));
868 auto_flow_sensitive
s1(stmt_to_move
);
869 auto_flow_sensitive
s_alt(stmt_to_move_alt
);
871 result
= gimple_simplify_phiopt (early_p
, type
, stmt
,
878 if (dump_file
&& (dump_flags
& TDF_FOLDING
))
879 fprintf (dump_file
, "accepted the phiopt match-simplify.\n");
881 auto_bitmap exprs_maybe_dce
;
883 /* Mark the cond statements' lhs/rhs as maybe dce. */
884 if (TREE_CODE (gimple_cond_lhs (stmt
)) == SSA_NAME
885 && !SSA_NAME_IS_DEFAULT_DEF (gimple_cond_lhs (stmt
)))
886 bitmap_set_bit (exprs_maybe_dce
,
887 SSA_NAME_VERSION (gimple_cond_lhs (stmt
)));
888 if (TREE_CODE (gimple_cond_rhs (stmt
)) == SSA_NAME
889 && !SSA_NAME_IS_DEFAULT_DEF (gimple_cond_rhs (stmt
)))
890 bitmap_set_bit (exprs_maybe_dce
,
891 SSA_NAME_VERSION (gimple_cond_rhs (stmt
)));
893 gsi
= gsi_last_bb (cond_bb
);
894 /* Insert the sequence generated from gimple_simplify_phiopt. */
897 // Mark the lhs of the new statements maybe for dce
898 gimple_stmt_iterator gsi1
= gsi_start (seq
);
899 for (; !gsi_end_p (gsi1
); gsi_next (&gsi1
))
901 gimple
*stmt
= gsi_stmt (gsi1
);
902 tree name
= gimple_get_lhs (stmt
);
903 if (name
&& TREE_CODE (name
) == SSA_NAME
)
904 bitmap_set_bit (exprs_maybe_dce
, SSA_NAME_VERSION (name
));
906 gsi_insert_seq_before (&gsi
, seq
, GSI_CONTINUE_LINKING
);
909 /* If there was a statement to move, move it to right before
910 the original conditional. */
911 move_stmt (stmt_to_move
, &gsi
, exprs_maybe_dce
);
912 move_stmt (stmt_to_move_alt
, &gsi
, exprs_maybe_dce
);
914 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, result
, exprs_maybe_dce
);
916 /* Add Statistic here even though replace_phi_edge_with_variable already
917 does it as we want to be able to count when match-simplify happens vs
919 statistics_counter_event (cfun
, "match-simplify PHI replacement", 1);
921 /* Note that we optimized this PHI. */
925 /* Update *ARG which is defined in STMT so that it contains the
926 computed value if that seems profitable. Return true if the
927 statement is made dead by that rewriting. */
930 jump_function_from_stmt (tree
*arg
, gimple
*stmt
)
932 enum tree_code code
= gimple_assign_rhs_code (stmt
);
933 if (code
== ADDR_EXPR
)
935 /* For arg = &p->i transform it to p, if possible. */
936 tree rhs1
= gimple_assign_rhs1 (stmt
);
938 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs1
, 0),
941 && TREE_CODE (tem
) == MEM_REF
942 && known_eq (mem_ref_offset (tem
) + offset
, 0))
944 *arg
= TREE_OPERAND (tem
, 0);
948 /* TODO: Much like IPA-CP jump-functions we want to handle constant
949 additions symbolically here, and we'd need to update the comparison
950 code that compares the arg + cst tuples in our caller. For now the
951 code above exactly handles the VEC_BASE pattern from vec.h. */
955 /* RHS is a source argument in a BIT_AND_EXPR which feeds a conditional
956 of the form SSA_NAME NE 0.
958 If RHS is fed by a simple EQ_EXPR comparison of two values, see if
959 the two input values of the EQ_EXPR match arg0 and arg1.
961 If so update *code and return TRUE. Otherwise return FALSE. */
964 rhs_is_fed_for_value_replacement (const_tree arg0
, const_tree arg1
,
965 enum tree_code
*code
, const_tree rhs
)
967 /* Obviously if RHS is not an SSA_NAME, we can't look at the defining
969 if (TREE_CODE (rhs
) == SSA_NAME
)
971 gimple
*def1
= SSA_NAME_DEF_STMT (rhs
);
973 /* Verify the defining statement has an EQ_EXPR on the RHS. */
974 if (is_gimple_assign (def1
) && gimple_assign_rhs_code (def1
) == EQ_EXPR
)
976 /* Finally verify the source operands of the EQ_EXPR are equal
978 tree op0
= gimple_assign_rhs1 (def1
);
979 tree op1
= gimple_assign_rhs2 (def1
);
980 if ((operand_equal_for_phi_arg_p (arg0
, op0
)
981 && operand_equal_for_phi_arg_p (arg1
, op1
))
982 || (operand_equal_for_phi_arg_p (arg0
, op1
)
983 && operand_equal_for_phi_arg_p (arg1
, op0
)))
985 /* We will perform the optimization. */
986 *code
= gimple_assign_rhs_code (def1
);
994 /* Return TRUE if arg0/arg1 are equal to the rhs/lhs or lhs/rhs of COND.
996 Also return TRUE if arg0/arg1 are equal to the source arguments of a
997 an EQ comparison feeding a BIT_AND_EXPR which feeds COND.
999 Return FALSE otherwise. */
1002 operand_equal_for_value_replacement (const_tree arg0
, const_tree arg1
,
1003 enum tree_code
*code
, gimple
*cond
)
1006 tree lhs
= gimple_cond_lhs (cond
);
1007 tree rhs
= gimple_cond_rhs (cond
);
1009 if ((operand_equal_for_phi_arg_p (arg0
, lhs
)
1010 && operand_equal_for_phi_arg_p (arg1
, rhs
))
1011 || (operand_equal_for_phi_arg_p (arg1
, lhs
)
1012 && operand_equal_for_phi_arg_p (arg0
, rhs
)))
1015 /* Now handle more complex case where we have an EQ comparison
1016 which feeds a BIT_AND_EXPR which feeds COND.
1018 First verify that COND is of the form SSA_NAME NE 0. */
1019 if (*code
!= NE_EXPR
|| !integer_zerop (rhs
)
1020 || TREE_CODE (lhs
) != SSA_NAME
)
1023 /* Now ensure that SSA_NAME is set by a BIT_AND_EXPR. */
1024 def
= SSA_NAME_DEF_STMT (lhs
);
1025 if (!is_gimple_assign (def
) || gimple_assign_rhs_code (def
) != BIT_AND_EXPR
)
1028 /* Now verify arg0/arg1 correspond to the source arguments of an
1029 EQ comparison feeding the BIT_AND_EXPR. */
1031 tree tmp
= gimple_assign_rhs1 (def
);
1032 if (rhs_is_fed_for_value_replacement (arg0
, arg1
, code
, tmp
))
1035 tmp
= gimple_assign_rhs2 (def
);
1036 if (rhs_is_fed_for_value_replacement (arg0
, arg1
, code
, tmp
))
1042 /* Returns true if ARG is a neutral element for operation CODE
1043 on the RIGHT side. */
1046 neutral_element_p (tree_code code
, tree arg
, bool right
)
1053 return integer_zerop (arg
);
1060 case POINTER_PLUS_EXPR
:
1061 return right
&& integer_zerop (arg
);
1064 return integer_onep (arg
);
1066 case TRUNC_DIV_EXPR
:
1068 case FLOOR_DIV_EXPR
:
1069 case ROUND_DIV_EXPR
:
1070 case EXACT_DIV_EXPR
:
1071 return right
&& integer_onep (arg
);
1074 return integer_all_onesp (arg
);
1081 /* Returns true if ARG is an absorbing element for operation CODE. */
1084 absorbing_element_p (tree_code code
, tree arg
, bool right
, tree rval
)
1089 return integer_all_onesp (arg
);
1093 return integer_zerop (arg
);
1099 return !right
&& integer_zerop (arg
);
1101 case TRUNC_DIV_EXPR
:
1103 case FLOOR_DIV_EXPR
:
1104 case ROUND_DIV_EXPR
:
1105 case EXACT_DIV_EXPR
:
1106 case TRUNC_MOD_EXPR
:
1108 case FLOOR_MOD_EXPR
:
1109 case ROUND_MOD_EXPR
:
1111 && integer_zerop (arg
)
1112 && tree_single_nonzero_warnv_p (rval
, NULL
));
1119 /* The function value_replacement does the main work of doing the value
1120 replacement. Return non-zero if the replacement is done. Otherwise return
1121 0. If we remove the middle basic block, return 2.
1122 BB is the basic block where the replacement is going to be done on. ARG0
1123 is argument 0 from the PHI. Likewise for ARG1. */
1126 value_replacement (basic_block cond_bb
, basic_block middle_bb
,
1127 edge e0
, edge e1
, gphi
*phi
, tree arg0
, tree arg1
)
1129 gimple_stmt_iterator gsi
;
1130 edge true_edge
, false_edge
;
1131 enum tree_code code
;
1132 bool empty_or_with_defined_p
= true;
1134 /* Virtual operands don't need to be handled. */
1135 if (virtual_operand_p (arg1
))
1138 /* Special case A ? B : B as this will always simplify to B. */
1139 if (operand_equal_for_phi_arg_p (arg0
, arg1
))
1142 gcond
*cond
= as_a
<gcond
*> (*gsi_last_bb (cond_bb
));
1143 code
= gimple_cond_code (cond
);
1145 /* This transformation is only valid for equality comparisons. */
1146 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1149 /* Do not make conditional undefs unconditional. */
1150 if ((TREE_CODE (arg0
) == SSA_NAME
1151 && ssa_name_maybe_undef_p (arg0
))
1152 || (TREE_CODE (arg1
) == SSA_NAME
1153 && ssa_name_maybe_undef_p (arg1
)))
1156 /* If the type says honor signed zeros we cannot do this
1158 if (HONOR_SIGNED_ZEROS (arg1
))
1161 /* If there is a statement in MIDDLE_BB that defines one of the PHI
1162 arguments, then adjust arg0 or arg1. */
1163 gsi
= gsi_start_nondebug_after_labels_bb (middle_bb
);
1164 while (!gsi_end_p (gsi
))
1166 gimple
*stmt
= gsi_stmt (gsi
);
1168 gsi_next_nondebug (&gsi
);
1169 if (!is_gimple_assign (stmt
))
1171 if (gimple_code (stmt
) != GIMPLE_PREDICT
1172 && gimple_code (stmt
) != GIMPLE_NOP
)
1173 empty_or_with_defined_p
= false;
1176 /* Now try to adjust arg0 or arg1 according to the computation
1177 in the statement. */
1178 lhs
= gimple_assign_lhs (stmt
);
1180 && jump_function_from_stmt (&arg0
, stmt
))
1182 && jump_function_from_stmt (&arg1
, stmt
)))
1183 empty_or_with_defined_p
= false;
1186 /* We need to know which is the true edge and which is the false
1187 edge so that we know if have abs or negative abs. */
1188 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
1190 /* At this point we know we have a COND_EXPR with two successors.
1191 One successor is BB, the other successor is an empty block which
1192 falls through into BB.
1194 The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
1196 There is a single PHI node at the join point (BB) with two arguments.
1198 We now need to verify that the two arguments in the PHI node match
1199 the two arguments to the equality comparison. */
1201 bool equal_p
= operand_equal_for_value_replacement (arg0
, arg1
, &code
, cond
);
1202 bool maybe_equal_p
= false;
1204 && empty_or_with_defined_p
1205 && TREE_CODE (gimple_cond_rhs (cond
)) == INTEGER_CST
1206 && (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond
), arg0
)
1207 ? TREE_CODE (arg1
) == INTEGER_CST
1208 : (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond
), arg1
)
1209 && TREE_CODE (arg0
) == INTEGER_CST
)))
1210 maybe_equal_p
= true;
1211 if (equal_p
|| maybe_equal_p
)
1216 /* For NE_EXPR, we want to build an assignment result = arg where
1217 arg is the PHI argument associated with the true edge. For
1218 EQ_EXPR we want the PHI argument associated with the false edge. */
1219 e
= (code
== NE_EXPR
? true_edge
: false_edge
);
1221 /* Unfortunately, E may not reach BB (it may instead have gone to
1222 OTHER_BLOCK). If that is the case, then we want the single outgoing
1223 edge from OTHER_BLOCK which reaches BB and represents the desired
1224 path from COND_BLOCK. */
1225 if (e
->dest
== middle_bb
)
1226 e
= single_succ_edge (e
->dest
);
1228 /* Now we know the incoming edge to BB that has the argument for the
1229 RHS of our new assignment statement. */
1235 /* If the middle basic block was empty or is defining the
1236 PHI arguments and this is a single phi where the args are different
1237 for the edges e0 and e1 then we can remove the middle basic block. */
1238 if (empty_or_with_defined_p
1239 && single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi
)),
1242 use_operand_p use_p
;
1245 /* Even if arg0/arg1 isn't equal to second operand of cond, we
1246 can optimize away the bb if we can prove it doesn't care whether
1247 phi result is arg0/arg1 or second operand of cond. Consider:
1248 <bb 2> [local count: 118111600]:
1250 goto <bb 4>; [97.00%]
1252 goto <bb 3>; [3.00%]
1254 <bb 3> [local count: 3540129]:
1256 <bb 4> [local count: 118111600]:
1257 # i_6 = PHI <i_2(D)(3), 6(2)>
1259 Here, carg is 4, oarg is 6, crhs is 0, and because
1260 (4 != 0) == (6 != 0), we don't care if i_6 is 4 or 6, both
1261 have the same outcome. So, we can optimize this to:
1263 If the single imm use of phi result >, >=, < or <=, similarly
1264 we can check if both carg and oarg compare the same against
1265 crhs using ccode. */
1267 && TREE_CODE (arg
) != INTEGER_CST
1268 && single_imm_use (gimple_phi_result (phi
), &use_p
, &use_stmt
))
1270 enum tree_code ccode
= ERROR_MARK
;
1271 tree clhs
= NULL_TREE
, crhs
= NULL_TREE
;
1272 tree carg
= gimple_cond_rhs (cond
);
1273 tree oarg
= e0
== e
? arg1
: arg0
;
1274 if (is_gimple_assign (use_stmt
)
1275 && (TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt
))
1278 ccode
= gimple_assign_rhs_code (use_stmt
);
1279 clhs
= gimple_assign_rhs1 (use_stmt
);
1280 crhs
= gimple_assign_rhs2 (use_stmt
);
1282 else if (gimple_code (use_stmt
) == GIMPLE_COND
)
1284 ccode
= gimple_cond_code (use_stmt
);
1285 clhs
= gimple_cond_lhs (use_stmt
);
1286 crhs
= gimple_cond_rhs (use_stmt
);
1288 if (ccode
!= ERROR_MARK
1289 && clhs
== gimple_phi_result (phi
)
1290 && TREE_CODE (crhs
) == INTEGER_CST
)
1295 if (!tree_int_cst_equal (crhs
, carg
)
1296 && !tree_int_cst_equal (crhs
, oarg
))
1300 if (tree_int_cst_lt (crhs
, carg
)
1301 == tree_int_cst_lt (crhs
, oarg
))
1305 if (tree_int_cst_le (crhs
, carg
)
1306 == tree_int_cst_le (crhs
, oarg
))
1310 if (tree_int_cst_lt (carg
, crhs
)
1311 == tree_int_cst_lt (oarg
, crhs
))
1315 if (tree_int_cst_le (carg
, crhs
)
1316 == tree_int_cst_le (oarg
, crhs
))
1324 tree phires
= gimple_phi_result (phi
);
1325 if (SSA_NAME_RANGE_INFO (phires
))
1327 /* After the optimization PHI result can have value
1328 which it couldn't have previously. */
1330 if (get_global_range_query ()->range_of_expr (r
, phires
,
1333 wide_int warg
= wi::to_wide (carg
);
1334 int_range
<2> tmp (TREE_TYPE (carg
), warg
, warg
);
1336 reset_flow_sensitive_info (phires
);
1337 set_range_info (phires
, r
);
1340 reset_flow_sensitive_info (phires
);
1343 if (equal_p
&& MAY_HAVE_DEBUG_BIND_STMTS
)
1345 imm_use_iterator imm_iter
;
1346 tree phires
= gimple_phi_result (phi
);
1347 tree temp
= NULL_TREE
;
1348 bool reset_p
= false;
1350 /* Add # DEBUG D#1 => arg != carg ? arg : oarg. */
1351 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, phires
)
1353 if (!is_gimple_debug (use_stmt
))
1355 if (temp
== NULL_TREE
)
1357 if (!single_pred_p (middle_bb
)
1358 || EDGE_COUNT (gimple_bb (phi
)->preds
) != 2)
1360 /* But only if middle_bb has a single
1361 predecessor and phi bb has two, otherwise
1362 we could use a SSA_NAME not usable in that
1363 place or wrong-debug. */
1367 gimple_stmt_iterator gsi
1368 = gsi_after_labels (gimple_bb (phi
));
1369 tree type
= TREE_TYPE (phires
);
1370 temp
= build_debug_expr_decl (type
);
1371 tree t
= build2 (NE_EXPR
, boolean_type_node
,
1373 t
= build3 (COND_EXPR
, type
, t
, arg
, oarg
);
1374 gimple
*g
= gimple_build_debug_bind (temp
, t
, phi
);
1375 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
1377 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1378 replace_exp (use_p
, temp
);
1379 update_stmt (use_stmt
);
1382 reset_debug_uses (phi
);
1387 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, arg
);
1388 /* Note that we optimized this PHI. */
1394 if (!single_pred_p (middle_bb
))
1396 statistics_counter_event (cfun
, "Replace PHI with "
1397 "variable/value_replacement", 1);
1399 /* Replace the PHI arguments with arg. */
1400 SET_PHI_ARG_DEF (phi
, e0
->dest_idx
, arg
);
1401 SET_PHI_ARG_DEF (phi
, e1
->dest_idx
, arg
);
1402 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1404 fprintf (dump_file
, "PHI ");
1405 print_generic_expr (dump_file
, gimple_phi_result (phi
));
1406 fprintf (dump_file
, " reduced for COND_EXPR in block %d to ",
1408 print_generic_expr (dump_file
, arg
);
1409 fprintf (dump_file
, ".\n");
1415 if (!single_pred_p (middle_bb
))
1418 /* Now optimize (x != 0) ? x + y : y to just x + y. */
1419 gsi
= gsi_last_nondebug_bb (middle_bb
);
1420 if (gsi_end_p (gsi
))
1423 gimple
*assign
= gsi_stmt (gsi
);
1424 if (!is_gimple_assign (assign
)
1425 || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0
))
1426 && !POINTER_TYPE_P (TREE_TYPE (arg0
))))
1429 if (gimple_assign_rhs_class (assign
) != GIMPLE_BINARY_RHS
)
1431 /* If last stmt of the middle_bb is a conversion, handle it like
1432 a preparation statement through constant evaluation with
1434 enum tree_code sc
= gimple_assign_rhs_code (assign
);
1435 if (CONVERT_EXPR_CODE_P (sc
))
1441 /* Punt if there are (degenerate) PHIs in middle_bb, there should not be. */
1442 if (!gimple_seq_empty_p (phi_nodes (middle_bb
)))
1445 /* Allow up to 2 cheap preparation statements that prepare argument
1453 iftmp.0_6 = x_5(D) r<< _1;
1455 # iftmp.0_2 = PHI <iftmp.0_6(3), x_5(D)(2)>
1466 # _2 = PHI <x_5(D)(2), _6(3)> */
1467 gimple
*prep_stmt
[2] = { NULL
, NULL
};
1469 for (prep_cnt
= 0; ; prep_cnt
++)
1471 if (prep_cnt
|| assign
)
1472 gsi_prev_nondebug (&gsi
);
1473 if (gsi_end_p (gsi
))
1476 gimple
*g
= gsi_stmt (gsi
);
1477 if (gimple_code (g
) == GIMPLE_LABEL
)
1480 if (prep_cnt
== 2 || !is_gimple_assign (g
))
1483 tree lhs
= gimple_assign_lhs (g
);
1484 tree rhs1
= gimple_assign_rhs1 (g
);
1485 use_operand_p use_p
;
1487 if (TREE_CODE (lhs
) != SSA_NAME
1488 || TREE_CODE (rhs1
) != SSA_NAME
1489 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
1490 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
1491 || !single_imm_use (lhs
, &use_p
, &use_stmt
)
1492 || ((prep_cnt
|| assign
)
1493 && use_stmt
!= (prep_cnt
? prep_stmt
[prep_cnt
- 1] : assign
)))
1495 switch (gimple_assign_rhs_code (g
))
1503 if (TREE_CODE (gimple_assign_rhs2 (g
)) != INTEGER_CST
)
1509 prep_stmt
[prep_cnt
] = g
;
1512 /* Only transform if it removes the condition. */
1513 if (!single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi
)), e0
, e1
))
1516 /* Size-wise, this is always profitable. */
1517 if (optimize_bb_for_speed_p (cond_bb
)
1518 /* The special case is useless if it has a low probability. */
1519 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
1520 && EDGE_PRED (middle_bb
, 0)->probability
< profile_probability::even ()
1521 /* If assign is cheap, there is no point avoiding it. */
1522 && estimate_num_insns_seq (bb_seq (middle_bb
), &eni_time_weights
)
1523 >= 3 * estimate_num_insns (cond
, &eni_time_weights
))
1526 tree cond_lhs
= gimple_cond_lhs (cond
);
1527 tree cond_rhs
= gimple_cond_rhs (cond
);
1529 /* Propagate the cond_rhs constant through preparation stmts,
1530 make sure UB isn't invoked while doing that. */
1531 for (int i
= prep_cnt
- 1; i
>= 0; --i
)
1533 gimple
*g
= prep_stmt
[i
];
1534 tree grhs1
= gimple_assign_rhs1 (g
);
1535 if (!operand_equal_for_phi_arg_p (cond_lhs
, grhs1
))
1537 cond_lhs
= gimple_assign_lhs (g
);
1538 cond_rhs
= fold_convert (TREE_TYPE (grhs1
), cond_rhs
);
1539 if (TREE_CODE (cond_rhs
) != INTEGER_CST
1540 || TREE_OVERFLOW (cond_rhs
))
1542 if (gimple_assign_rhs_class (g
) == GIMPLE_BINARY_RHS
)
1544 cond_rhs
= int_const_binop (gimple_assign_rhs_code (g
), cond_rhs
,
1545 gimple_assign_rhs2 (g
));
1546 if (TREE_OVERFLOW (cond_rhs
))
1549 cond_rhs
= fold_convert (TREE_TYPE (cond_lhs
), cond_rhs
);
1550 if (TREE_CODE (cond_rhs
) != INTEGER_CST
1551 || TREE_OVERFLOW (cond_rhs
))
1555 tree lhs
, rhs1
, rhs2
;
1556 enum tree_code code_def
;
1559 lhs
= gimple_assign_lhs (assign
);
1560 rhs1
= gimple_assign_rhs1 (assign
);
1561 rhs2
= gimple_assign_rhs2 (assign
);
1562 code_def
= gimple_assign_rhs_code (assign
);
1566 gcc_assert (prep_cnt
> 0);
1570 code_def
= ERROR_MARK
;
1573 if (((code
== NE_EXPR
&& e1
== false_edge
)
1574 || (code
== EQ_EXPR
&& e1
== true_edge
))
1577 && operand_equal_for_phi_arg_p (arg1
, cond_rhs
))
1580 && operand_equal_for_phi_arg_p (rhs2
, cond_lhs
)
1581 && neutral_element_p (code_def
, cond_rhs
, true))
1584 && operand_equal_for_phi_arg_p (rhs1
, cond_lhs
)
1585 && neutral_element_p (code_def
, cond_rhs
, false))
1587 && operand_equal_for_phi_arg_p (arg1
, cond_rhs
)
1588 && ((operand_equal_for_phi_arg_p (rhs2
, cond_lhs
)
1589 && absorbing_element_p (code_def
, cond_rhs
, true, rhs2
))
1590 || (operand_equal_for_phi_arg_p (rhs1
, cond_lhs
)
1591 && absorbing_element_p (code_def
,
1592 cond_rhs
, false, rhs2
))))))
1594 gsi
= gsi_for_stmt (cond
);
1595 /* Moving ASSIGN might change VR of lhs, e.g. when moving u_6
1603 # RANGE [0, 4294967294]
1604 u_6 = n_5 + 4294967295;
1607 # u_3 = PHI <u_6(3), 4294967295(2)> */
1608 reset_flow_sensitive_info (lhs
);
1609 gimple_stmt_iterator gsi_from
;
1610 for (int i
= prep_cnt
- 1; i
>= 0; --i
)
1612 tree plhs
= gimple_assign_lhs (prep_stmt
[i
]);
1613 reset_flow_sensitive_info (plhs
);
1614 gsi_from
= gsi_for_stmt (prep_stmt
[i
]);
1615 gsi_move_before (&gsi_from
, &gsi
);
1619 gsi_from
= gsi_for_stmt (assign
);
1620 gsi_move_before (&gsi_from
, &gsi
);
1622 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, lhs
);
1629 /* If VAR is an SSA_NAME that points to a BIT_NOT_EXPR then return the TREE for
1630 the value being inverted. */
1633 strip_bit_not (tree var
)
1635 if (TREE_CODE (var
) != SSA_NAME
)
1638 gimple
*assign
= SSA_NAME_DEF_STMT (var
);
1639 if (gimple_code (assign
) != GIMPLE_ASSIGN
)
1642 if (gimple_assign_rhs_code (assign
) != BIT_NOT_EXPR
)
1645 return gimple_assign_rhs1 (assign
);
1648 /* Invert a MIN to a MAX or a MAX to a MIN expression CODE. */
1651 invert_minmax_code (enum tree_code code
)
1663 /* The function minmax_replacement does the main work of doing the minmax
1664 replacement. Return true if the replacement is done. Otherwise return
1666 BB is the basic block where the replacement is going to be done on. ARG0
1667 is argument 0 from the PHI. Likewise for ARG1.
1669 If THREEWAY_P then expect the BB to be laid out in diamond shape with each
1670 BB containing only a MIN or MAX expression. */
1673 minmax_replacement (basic_block cond_bb
, basic_block middle_bb
, basic_block alt_middle_bb
,
1674 edge e0
, edge e1
, gphi
*phi
, tree arg0
, tree arg1
, bool threeway_p
)
1677 edge true_edge
, false_edge
;
1678 enum tree_code minmax
, ass_code
;
1679 tree smaller
, larger
, arg_true
, arg_false
;
1680 gimple_stmt_iterator gsi
, gsi_from
;
1682 tree type
= TREE_TYPE (PHI_RESULT (phi
));
1684 gcond
*cond
= as_a
<gcond
*> (*gsi_last_bb (cond_bb
));
1685 enum tree_code cmp
= gimple_cond_code (cond
);
1686 tree rhs
= gimple_cond_rhs (cond
);
1688 /* Turn EQ/NE of extreme values to order comparisons. */
1689 if ((cmp
== NE_EXPR
|| cmp
== EQ_EXPR
)
1690 && TREE_CODE (rhs
) == INTEGER_CST
1691 && INTEGRAL_TYPE_P (TREE_TYPE (rhs
)))
1693 if (wi::eq_p (wi::to_wide (rhs
), wi::min_value (TREE_TYPE (rhs
))))
1695 cmp
= (cmp
== EQ_EXPR
) ? LT_EXPR
: GE_EXPR
;
1696 rhs
= wide_int_to_tree (TREE_TYPE (rhs
),
1697 wi::min_value (TREE_TYPE (rhs
)) + 1);
1699 else if (wi::eq_p (wi::to_wide (rhs
), wi::max_value (TREE_TYPE (rhs
))))
1701 cmp
= (cmp
== EQ_EXPR
) ? GT_EXPR
: LE_EXPR
;
1702 rhs
= wide_int_to_tree (TREE_TYPE (rhs
),
1703 wi::max_value (TREE_TYPE (rhs
)) - 1);
1707 /* This transformation is only valid for order comparisons. Record which
1708 operand is smaller/larger if the result of the comparison is true. */
1709 tree alt_smaller
= NULL_TREE
;
1710 tree alt_larger
= NULL_TREE
;
1711 if (cmp
== LT_EXPR
|| cmp
== LE_EXPR
)
1713 smaller
= gimple_cond_lhs (cond
);
1715 /* If we have smaller < CST it is equivalent to smaller <= CST-1.
1716 Likewise smaller <= CST is equivalent to smaller < CST+1. */
1717 if (TREE_CODE (larger
) == INTEGER_CST
1718 && INTEGRAL_TYPE_P (TREE_TYPE (larger
)))
1722 wi::overflow_type overflow
;
1723 wide_int alt
= wi::sub (wi::to_wide (larger
), 1,
1724 TYPE_SIGN (TREE_TYPE (larger
)),
1727 alt_larger
= wide_int_to_tree (TREE_TYPE (larger
), alt
);
1731 wi::overflow_type overflow
;
1732 wide_int alt
= wi::add (wi::to_wide (larger
), 1,
1733 TYPE_SIGN (TREE_TYPE (larger
)),
1736 alt_larger
= wide_int_to_tree (TREE_TYPE (larger
), alt
);
1740 else if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
1743 larger
= gimple_cond_lhs (cond
);
1744 /* If we have larger > CST it is equivalent to larger >= CST+1.
1745 Likewise larger >= CST is equivalent to larger > CST-1. */
1746 if (TREE_CODE (smaller
) == INTEGER_CST
1747 && INTEGRAL_TYPE_P (TREE_TYPE (smaller
)))
1749 wi::overflow_type overflow
;
1752 wide_int alt
= wi::add (wi::to_wide (smaller
), 1,
1753 TYPE_SIGN (TREE_TYPE (smaller
)),
1756 alt_smaller
= wide_int_to_tree (TREE_TYPE (smaller
), alt
);
1760 wide_int alt
= wi::sub (wi::to_wide (smaller
), 1,
1761 TYPE_SIGN (TREE_TYPE (smaller
)),
1764 alt_smaller
= wide_int_to_tree (TREE_TYPE (smaller
), alt
);
1771 /* Handle the special case of (signed_type)x < 0 being equivalent
1772 to x > MAX_VAL(signed_type) and (signed_type)x >= 0 equivalent
1773 to x <= MAX_VAL(signed_type). */
1774 if ((cmp
== GE_EXPR
|| cmp
== LT_EXPR
)
1775 && INTEGRAL_TYPE_P (type
)
1776 && TYPE_UNSIGNED (type
)
1777 && integer_zerop (rhs
))
1779 tree op
= gimple_cond_lhs (cond
);
1780 if (TREE_CODE (op
) == SSA_NAME
1781 && INTEGRAL_TYPE_P (TREE_TYPE (op
))
1782 && !TYPE_UNSIGNED (TREE_TYPE (op
)))
1784 gimple
*def_stmt
= SSA_NAME_DEF_STMT (op
);
1785 if (gimple_assign_cast_p (def_stmt
))
1787 tree op1
= gimple_assign_rhs1 (def_stmt
);
1788 if (INTEGRAL_TYPE_P (TREE_TYPE (op1
))
1789 && TYPE_UNSIGNED (TREE_TYPE (op1
))
1790 && (TYPE_PRECISION (TREE_TYPE (op
))
1791 == TYPE_PRECISION (TREE_TYPE (op1
)))
1792 && useless_type_conversion_p (type
, TREE_TYPE (op1
)))
1794 wide_int w1
= wi::max_value (TREE_TYPE (op
));
1795 wide_int w2
= wi::add (w1
, 1);
1799 smaller
= wide_int_to_tree (TREE_TYPE (op1
), w1
);
1800 alt_smaller
= wide_int_to_tree (TREE_TYPE (op1
), w2
);
1801 alt_larger
= NULL_TREE
;
1806 larger
= wide_int_to_tree (TREE_TYPE (op1
), w1
);
1807 alt_larger
= wide_int_to_tree (TREE_TYPE (op1
), w2
);
1808 alt_smaller
= NULL_TREE
;
1815 /* We need to know which is the true edge and which is the false
1816 edge so that we know if have abs or negative abs. */
1817 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
1819 /* Forward the edges over the middle basic block. */
1820 if (true_edge
->dest
== middle_bb
)
1821 true_edge
= EDGE_SUCC (true_edge
->dest
, 0);
1822 if (false_edge
->dest
== middle_bb
)
1823 false_edge
= EDGE_SUCC (false_edge
->dest
, 0);
1825 /* When THREEWAY_P then e1 will point to the edge of the final transition
1826 from middle-bb to end. */
1827 if (true_edge
== e0
)
1830 gcc_assert (false_edge
== e1
);
1836 gcc_assert (false_edge
== e0
);
1838 gcc_assert (true_edge
== e1
);
1843 if (empty_block_p (middle_bb
)
1845 || empty_block_p (alt_middle_bb
)))
1847 if ((operand_equal_for_phi_arg_p (arg_true
, smaller
)
1849 && operand_equal_for_phi_arg_p (arg_true
, alt_smaller
)))
1850 && (operand_equal_for_phi_arg_p (arg_false
, larger
)
1852 && operand_equal_for_phi_arg_p (arg_true
, alt_larger
))))
1856 if (smaller < larger)
1862 else if ((operand_equal_for_phi_arg_p (arg_false
, smaller
)
1864 && operand_equal_for_phi_arg_p (arg_false
, alt_smaller
)))
1865 && (operand_equal_for_phi_arg_p (arg_true
, larger
)
1867 && operand_equal_for_phi_arg_p (arg_true
, alt_larger
))))
1872 else if (HONOR_NANS (type
) || HONOR_SIGNED_ZEROS (type
))
1873 /* The optimization may be unsafe due to NaNs. */
1875 else if (middle_bb
!= alt_middle_bb
&& threeway_p
)
1877 /* Recognize the following case:
1879 if (smaller < larger)
1880 a = MIN (smaller, c);
1882 b = MIN (larger, c);
1885 This is equivalent to
1887 a = MIN (smaller, c);
1888 x = MIN (larger, a); */
1890 gimple
*assign
= last_and_only_stmt (middle_bb
);
1891 tree lhs
, op0
, op1
, bound
;
1892 tree alt_lhs
, alt_op0
, alt_op1
;
1893 bool invert
= false;
1895 /* When THREEWAY_P then e1 will point to the edge of the final transition
1896 from middle-bb to end. */
1897 if (true_edge
== e0
)
1898 gcc_assert (false_edge
== EDGE_PRED (e1
->src
, 0));
1900 gcc_assert (true_edge
== EDGE_PRED (e1
->src
, 0));
1902 bool valid_minmax_p
= false;
1903 gimple_stmt_iterator it1
1904 = gsi_start_nondebug_after_labels_bb (middle_bb
);
1905 gimple_stmt_iterator it2
1906 = gsi_start_nondebug_after_labels_bb (alt_middle_bb
);
1907 if (gsi_one_nondebug_before_end_p (it1
)
1908 && gsi_one_nondebug_before_end_p (it2
))
1910 gimple
*stmt1
= gsi_stmt (it1
);
1911 gimple
*stmt2
= gsi_stmt (it2
);
1912 if (is_gimple_assign (stmt1
) && is_gimple_assign (stmt2
))
1914 enum tree_code code1
= gimple_assign_rhs_code (stmt1
);
1915 enum tree_code code2
= gimple_assign_rhs_code (stmt2
);
1916 valid_minmax_p
= (code1
== MIN_EXPR
|| code1
== MAX_EXPR
)
1917 && (code2
== MIN_EXPR
|| code2
== MAX_EXPR
);
1921 if (!valid_minmax_p
)
1925 || gimple_code (assign
) != GIMPLE_ASSIGN
)
1928 lhs
= gimple_assign_lhs (assign
);
1929 ass_code
= gimple_assign_rhs_code (assign
);
1930 if (ass_code
!= MAX_EXPR
&& ass_code
!= MIN_EXPR
)
1933 op0
= gimple_assign_rhs1 (assign
);
1934 op1
= gimple_assign_rhs2 (assign
);
1936 assign
= last_and_only_stmt (alt_middle_bb
);
1938 || gimple_code (assign
) != GIMPLE_ASSIGN
)
1941 alt_lhs
= gimple_assign_lhs (assign
);
1942 if (ass_code
!= gimple_assign_rhs_code (assign
))
1945 if (!operand_equal_for_phi_arg_p (lhs
, arg_true
)
1946 || !operand_equal_for_phi_arg_p (alt_lhs
, arg_false
))
1949 alt_op0
= gimple_assign_rhs1 (assign
);
1950 alt_op1
= gimple_assign_rhs2 (assign
);
1952 if ((operand_equal_for_phi_arg_p (op0
, smaller
)
1954 && operand_equal_for_phi_arg_p (op0
, alt_smaller
)))
1955 && (operand_equal_for_phi_arg_p (alt_op0
, larger
)
1957 && operand_equal_for_phi_arg_p (alt_op0
, alt_larger
))))
1959 /* We got here if the condition is true, i.e., SMALLER < LARGER. */
1960 if (!operand_equal_for_phi_arg_p (op1
, alt_op1
))
1963 if ((arg0
= strip_bit_not (op0
)) != NULL
1964 && (arg1
= strip_bit_not (alt_op0
)) != NULL
1965 && (bound
= strip_bit_not (op1
)) != NULL
)
1968 ass_code
= invert_minmax_code (ass_code
);
1979 else if ((operand_equal_for_phi_arg_p (op0
, larger
)
1981 && operand_equal_for_phi_arg_p (op0
, alt_larger
)))
1982 && (operand_equal_for_phi_arg_p (alt_op0
, smaller
)
1984 && operand_equal_for_phi_arg_p (alt_op0
, alt_smaller
))))
1986 /* We got here if the condition is true, i.e., SMALLER > LARGER. */
1987 if (!operand_equal_for_phi_arg_p (op1
, alt_op1
))
1990 if ((arg0
= strip_bit_not (op0
)) != NULL
1991 && (arg1
= strip_bit_not (alt_op0
)) != NULL
1992 && (bound
= strip_bit_not (op1
)) != NULL
)
1995 ass_code
= invert_minmax_code (ass_code
);
2009 /* Emit the statement to compute min/max. */
2010 location_t locus
= gimple_location (last_nondebug_stmt (cond_bb
));
2011 gimple_seq stmts
= NULL
;
2012 tree phi_result
= PHI_RESULT (phi
);
2013 result
= gimple_build (&stmts
, locus
, minmax
, TREE_TYPE (phi_result
),
2015 result
= gimple_build (&stmts
, locus
, ass_code
, TREE_TYPE (phi_result
),
2018 result
= gimple_build (&stmts
, locus
, BIT_NOT_EXPR
, TREE_TYPE (phi_result
),
2021 gsi
= gsi_last_bb (cond_bb
);
2022 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2024 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, result
);
2028 else if (!threeway_p
2029 || empty_block_p (alt_middle_bb
))
2031 /* Recognize the following case, assuming d <= u:
2037 This is equivalent to
2042 gimple
*assign
= last_and_only_stmt (middle_bb
);
2043 tree lhs
, op0
, op1
, bound
;
2045 if (!single_pred_p (middle_bb
))
2049 || gimple_code (assign
) != GIMPLE_ASSIGN
)
2052 lhs
= gimple_assign_lhs (assign
);
2053 ass_code
= gimple_assign_rhs_code (assign
);
2054 if (ass_code
!= MAX_EXPR
&& ass_code
!= MIN_EXPR
)
2056 op0
= gimple_assign_rhs1 (assign
);
2057 op1
= gimple_assign_rhs2 (assign
);
2059 if (true_edge
->src
== middle_bb
)
2061 /* We got here if the condition is true, i.e., SMALLER < LARGER. */
2062 if (!operand_equal_for_phi_arg_p (lhs
, arg_true
))
2065 if (operand_equal_for_phi_arg_p (arg_false
, larger
)
2067 && operand_equal_for_phi_arg_p (arg_false
, alt_larger
)))
2071 if (smaller < larger)
2073 r' = MAX_EXPR (smaller, bound)
2075 r = PHI <r', larger> --> to be turned to MIN_EXPR. */
2076 if (ass_code
!= MAX_EXPR
)
2080 if (operand_equal_for_phi_arg_p (op0
, smaller
)
2082 && operand_equal_for_phi_arg_p (op0
, alt_smaller
)))
2084 else if (operand_equal_for_phi_arg_p (op1
, smaller
)
2086 && operand_equal_for_phi_arg_p (op1
, alt_smaller
)))
2091 /* We need BOUND <= LARGER. */
2092 if (!integer_nonzerop (fold_build2 (LE_EXPR
, boolean_type_node
,
2096 else if (operand_equal_for_phi_arg_p (arg_false
, smaller
)
2098 && operand_equal_for_phi_arg_p (arg_false
, alt_smaller
)))
2102 if (smaller < larger)
2104 r' = MIN_EXPR (larger, bound)
2106 r = PHI <r', smaller> --> to be turned to MAX_EXPR. */
2107 if (ass_code
!= MIN_EXPR
)
2111 if (operand_equal_for_phi_arg_p (op0
, larger
)
2113 && operand_equal_for_phi_arg_p (op0
, alt_larger
)))
2115 else if (operand_equal_for_phi_arg_p (op1
, larger
)
2117 && operand_equal_for_phi_arg_p (op1
, alt_larger
)))
2122 /* We need BOUND >= SMALLER. */
2123 if (!integer_nonzerop (fold_build2 (GE_EXPR
, boolean_type_node
,
2132 /* We got here if the condition is false, i.e., SMALLER > LARGER. */
2133 if (!operand_equal_for_phi_arg_p (lhs
, arg_false
))
2136 if (operand_equal_for_phi_arg_p (arg_true
, larger
)
2138 && operand_equal_for_phi_arg_p (arg_true
, alt_larger
)))
2142 if (smaller > larger)
2144 r' = MIN_EXPR (smaller, bound)
2146 r = PHI <r', larger> --> to be turned to MAX_EXPR. */
2147 if (ass_code
!= MIN_EXPR
)
2151 if (operand_equal_for_phi_arg_p (op0
, smaller
)
2153 && operand_equal_for_phi_arg_p (op0
, alt_smaller
)))
2155 else if (operand_equal_for_phi_arg_p (op1
, smaller
)
2157 && operand_equal_for_phi_arg_p (op1
, alt_smaller
)))
2162 /* We need BOUND >= LARGER. */
2163 if (!integer_nonzerop (fold_build2 (GE_EXPR
, boolean_type_node
,
2167 else if (operand_equal_for_phi_arg_p (arg_true
, smaller
)
2169 && operand_equal_for_phi_arg_p (arg_true
, alt_smaller
)))
2173 if (smaller > larger)
2175 r' = MAX_EXPR (larger, bound)
2177 r = PHI <r', smaller> --> to be turned to MIN_EXPR. */
2178 if (ass_code
!= MAX_EXPR
)
2182 if (operand_equal_for_phi_arg_p (op0
, larger
))
2184 else if (operand_equal_for_phi_arg_p (op1
, larger
))
2189 /* We need BOUND <= SMALLER. */
2190 if (!integer_nonzerop (fold_build2 (LE_EXPR
, boolean_type_node
,
2198 /* Move the statement from the middle block. */
2199 gsi
= gsi_last_bb (cond_bb
);
2200 gsi_from
= gsi_last_nondebug_bb (middle_bb
);
2201 reset_flow_sensitive_info (SINGLE_SSA_TREE_OPERAND (gsi_stmt (gsi_from
),
2203 gsi_move_before (&gsi_from
, &gsi
);
2208 /* Emit the statement to compute min/max. */
2209 gimple_seq stmts
= NULL
;
2210 tree phi_result
= PHI_RESULT (phi
);
2212 /* When we can't use a MIN/MAX_EXPR still make sure the expression
2213 stays in a form to be recognized by ISA that map to IEEE x > y ? x : y
2214 semantics (that's not IEEE max semantics). */
2215 if (HONOR_NANS (type
) || HONOR_SIGNED_ZEROS (type
))
2217 result
= gimple_build (&stmts
, cmp
, boolean_type_node
,
2218 gimple_cond_lhs (cond
), rhs
);
2219 result
= gimple_build (&stmts
, COND_EXPR
, TREE_TYPE (phi_result
),
2220 result
, arg_true
, arg_false
);
2223 result
= gimple_build (&stmts
, minmax
, TREE_TYPE (phi_result
), arg0
, arg1
);
2225 gsi
= gsi_last_bb (cond_bb
);
2226 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2228 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, result
);
2233 /* Attempt to optimize (x <=> y) cmp 0 and similar comparisons.
2234 For strong ordering <=> try to match something like:
2235 <bb 2> : // cond3_bb (== cond2_bb)
2236 if (x_4(D) != y_5(D))
2242 if (x_4(D) < y_5(D))
2247 <bb 4> : // middle_bb
2250 # iftmp.0_2 = PHI <1(4), 0(2), -1(3)>
2251 _1 = iftmp.0_2 == 0;
2253 and for partial ordering <=> something like:
2255 <bb 2> : // cond3_bb
2256 if (a_3(D) == b_5(D))
2257 goto <bb 6>; [50.00%]
2259 goto <bb 3>; [50.00%]
2261 <bb 3> [local count: 536870913]: // cond2_bb
2262 if (a_3(D) < b_5(D))
2263 goto <bb 6>; [50.00%]
2265 goto <bb 4>; [50.00%]
2267 <bb 4> [local count: 268435456]: // cond_bb
2268 if (a_3(D) > b_5(D))
2269 goto <bb 6>; [50.00%]
2271 goto <bb 5>; [50.00%]
2273 <bb 5> [local count: 134217728]: // middle_bb
2275 <bb 6> [local count: 1073741824]: // phi_bb
2276 # SR.27_4 = PHI <0(2), -1(3), 1(4), 2(5)>
2277 _2 = SR.27_4 > 0; */
2280 spaceship_replacement (basic_block cond_bb
, basic_block middle_bb
,
2281 edge e0
, edge e1
, gphi
*phi
,
2282 tree arg0
, tree arg1
)
2284 tree phires
= PHI_RESULT (phi
);
2285 if (!INTEGRAL_TYPE_P (TREE_TYPE (phires
))
2286 || TYPE_UNSIGNED (TREE_TYPE (phires
))
2287 || !tree_fits_shwi_p (arg0
)
2288 || !tree_fits_shwi_p (arg1
)
2289 || !IN_RANGE (tree_to_shwi (arg0
), -1, 2)
2290 || !IN_RANGE (tree_to_shwi (arg1
), -1, 2))
2293 basic_block phi_bb
= gimple_bb (phi
);
2294 gcc_assert (phi_bb
== e0
->dest
&& phi_bb
== e1
->dest
);
2295 if (!IN_RANGE (EDGE_COUNT (phi_bb
->preds
), 3, 4))
2298 use_operand_p use_p
;
2300 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (phires
))
2302 if (!single_imm_use (phires
, &use_p
, &use_stmt
))
2306 gimple
*orig_use_stmt
= use_stmt
;
2307 tree orig_use_lhs
= NULL_TREE
;
2308 int prec
= TYPE_PRECISION (TREE_TYPE (phires
));
2309 bool is_cast
= false;
2311 /* Deal with the case when match.pd has rewritten the (res & ~1) == 0
2312 into res <= 1 and has left a type-cast for signed types. */
2313 if (gimple_assign_cast_p (use_stmt
))
2315 orig_use_lhs
= gimple_assign_lhs (use_stmt
);
2316 /* match.pd would have only done this for a signed type,
2317 so the conversion must be to an unsigned one. */
2318 tree ty1
= TREE_TYPE (gimple_assign_rhs1 (use_stmt
));
2319 tree ty2
= TREE_TYPE (orig_use_lhs
);
2321 if (!TYPE_UNSIGNED (ty2
) || !INTEGRAL_TYPE_P (ty2
))
2323 if (TYPE_PRECISION (ty1
) > TYPE_PRECISION (ty2
))
2325 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs
))
2327 if (!single_imm_use (orig_use_lhs
, &use_p
, &use_stmt
))
2332 else if (is_gimple_assign (use_stmt
)
2333 && gimple_assign_rhs_code (use_stmt
) == BIT_AND_EXPR
2334 && TREE_CODE (gimple_assign_rhs2 (use_stmt
)) == INTEGER_CST
2335 && (wi::to_wide (gimple_assign_rhs2 (use_stmt
))
2336 == wi::shifted_mask (1, prec
- 1, false, prec
)))
2338 /* For partial_ordering result operator>= with unspec as second
2339 argument is (res & 1) == res, folded by match.pd into
2341 orig_use_lhs
= gimple_assign_lhs (use_stmt
);
2342 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs
))
2344 if (!single_imm_use (orig_use_lhs
, &use_p
, &use_stmt
))
2347 if (gimple_code (use_stmt
) == GIMPLE_COND
)
2349 cmp
= gimple_cond_code (use_stmt
);
2350 lhs
= gimple_cond_lhs (use_stmt
);
2351 rhs
= gimple_cond_rhs (use_stmt
);
2353 else if (is_gimple_assign (use_stmt
))
2355 if (gimple_assign_rhs_class (use_stmt
) == GIMPLE_BINARY_RHS
)
2357 cmp
= gimple_assign_rhs_code (use_stmt
);
2358 lhs
= gimple_assign_rhs1 (use_stmt
);
2359 rhs
= gimple_assign_rhs2 (use_stmt
);
2361 else if (gimple_assign_rhs_code (use_stmt
) == COND_EXPR
)
2363 tree cond
= gimple_assign_rhs1 (use_stmt
);
2364 if (!COMPARISON_CLASS_P (cond
))
2366 cmp
= TREE_CODE (cond
);
2367 lhs
= TREE_OPERAND (cond
, 0);
2368 rhs
= TREE_OPERAND (cond
, 1);
2387 if (lhs
!= (orig_use_lhs
? orig_use_lhs
: phires
)
2388 || !tree_fits_shwi_p (rhs
)
2389 || !IN_RANGE (tree_to_shwi (rhs
), -1, 1))
2394 if (TREE_CODE (rhs
) != INTEGER_CST
)
2396 /* As for -ffast-math we assume the 2 return to be
2397 impossible, canonicalize (unsigned) res <= 1U or
2398 (unsigned) res < 2U into res >= 0 and (unsigned) res > 1U
2399 or (unsigned) res >= 2U as res < 0. */
2403 if (!integer_onep (rhs
))
2408 if (wi::ne_p (wi::to_widest (rhs
), 2))
2413 if (!integer_onep (rhs
))
2418 if (wi::ne_p (wi::to_widest (rhs
), 2))
2425 rhs
= build_zero_cst (TREE_TYPE (phires
));
2427 else if (orig_use_lhs
)
2429 if ((cmp
!= EQ_EXPR
&& cmp
!= NE_EXPR
) || !integer_zerop (rhs
))
2431 /* As for -ffast-math we assume the 2 return to be
2432 impossible, canonicalize (res & ~1) == 0 into
2433 res >= 0 and (res & ~1) != 0 as res < 0. */
2434 cmp
= cmp
== EQ_EXPR
? GE_EXPR
: LT_EXPR
;
2437 if (!empty_block_p (middle_bb
))
2440 gcond
*cond1
= as_a
<gcond
*> (*gsi_last_bb (cond_bb
));
2441 enum tree_code cmp1
= gimple_cond_code (cond1
);
2452 tree lhs1
= gimple_cond_lhs (cond1
);
2453 tree rhs1
= gimple_cond_rhs (cond1
);
2454 /* The optimization may be unsafe due to NaNs. */
2455 if (HONOR_NANS (TREE_TYPE (lhs1
)))
2457 if (TREE_CODE (lhs1
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs1
))
2459 if (TREE_CODE (rhs1
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
))
2462 if (!single_pred_p (cond_bb
) || !cond_only_block_p (cond_bb
))
2465 basic_block cond2_bb
= single_pred (cond_bb
);
2466 if (EDGE_COUNT (cond2_bb
->succs
) != 2)
2468 edge cond2_phi_edge
;
2469 if (EDGE_SUCC (cond2_bb
, 0)->dest
== cond_bb
)
2471 if (EDGE_SUCC (cond2_bb
, 1)->dest
!= phi_bb
)
2473 cond2_phi_edge
= EDGE_SUCC (cond2_bb
, 1);
2475 else if (EDGE_SUCC (cond2_bb
, 0)->dest
!= phi_bb
)
2478 cond2_phi_edge
= EDGE_SUCC (cond2_bb
, 0);
2479 tree arg2
= gimple_phi_arg_def (phi
, cond2_phi_edge
->dest_idx
);
2480 if (!tree_fits_shwi_p (arg2
))
2482 gcond
*cond2
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (cond2_bb
));
2485 enum tree_code cmp2
= gimple_cond_code (cond2
);
2486 tree lhs2
= gimple_cond_lhs (cond2
);
2487 tree rhs2
= gimple_cond_rhs (cond2
);
2490 if (!operand_equal_p (rhs2
, rhs1
, 0))
2492 if ((cmp2
== EQ_EXPR
|| cmp2
== NE_EXPR
)
2493 && TREE_CODE (rhs1
) == INTEGER_CST
2494 && TREE_CODE (rhs2
) == INTEGER_CST
)
2496 /* For integers, we can have cond2 x == 5
2497 and cond1 x < 5, x <= 4, x <= 5, x < 6,
2498 x > 5, x >= 6, x >= 5 or x > 4. */
2499 if (tree_int_cst_lt (rhs1
, rhs2
))
2501 if (wi::ne_p (wi::to_wide (rhs1
) + 1, wi::to_wide (rhs2
)))
2503 if (cmp1
== LE_EXPR
)
2505 else if (cmp1
== GT_EXPR
)
2512 gcc_checking_assert (tree_int_cst_lt (rhs2
, rhs1
));
2513 if (wi::ne_p (wi::to_wide (rhs2
) + 1, wi::to_wide (rhs1
)))
2515 if (cmp1
== LT_EXPR
)
2517 else if (cmp1
== GE_EXPR
)
2528 else if (lhs2
== rhs1
)
2537 basic_block cond3_bb
= cond2_bb
;
2538 edge cond3_phi_edge
= cond2_phi_edge
;
2539 gcond
*cond3
= cond2
;
2540 enum tree_code cmp3
= cmp2
;
2543 if (EDGE_COUNT (phi_bb
->preds
) == 4)
2545 if (absu_hwi (tree_to_shwi (arg2
)) != 1)
2547 if (e1
->flags
& EDGE_TRUE_VALUE
)
2549 if (tree_to_shwi (arg0
) != 2
2550 || absu_hwi (tree_to_shwi (arg1
)) != 1
2551 || wi::to_widest (arg1
) == wi::to_widest (arg2
))
2554 else if (tree_to_shwi (arg1
) != 2
2555 || absu_hwi (tree_to_shwi (arg0
)) != 1
2556 || wi::to_widest (arg0
) == wi::to_widest (arg1
))
2568 /* if (x < y) goto phi_bb; else fallthru;
2569 if (x > y) goto phi_bb; else fallthru;
2572 is ok, but if x and y are swapped in one of the comparisons,
2573 or the comparisons are the same and operands not swapped,
2574 or the true and false edges are swapped, it is not. */
2576 ^ (((cond2_phi_edge
->flags
2577 & ((cmp2
== LT_EXPR
|| cmp2
== LE_EXPR
)
2578 ? EDGE_TRUE_VALUE
: EDGE_FALSE_VALUE
)) != 0)
2580 & ((cmp1
== LT_EXPR
|| cmp1
== LE_EXPR
)
2581 ? EDGE_TRUE_VALUE
: EDGE_FALSE_VALUE
)) != 0)))
2583 if (!single_pred_p (cond2_bb
) || !cond_only_block_p (cond2_bb
))
2585 cond3_bb
= single_pred (cond2_bb
);
2586 if (EDGE_COUNT (cond2_bb
->succs
) != 2)
2588 if (EDGE_SUCC (cond3_bb
, 0)->dest
== cond2_bb
)
2590 if (EDGE_SUCC (cond3_bb
, 1)->dest
!= phi_bb
)
2592 cond3_phi_edge
= EDGE_SUCC (cond3_bb
, 1);
2594 else if (EDGE_SUCC (cond3_bb
, 0)->dest
!= phi_bb
)
2597 cond3_phi_edge
= EDGE_SUCC (cond3_bb
, 0);
2598 arg3
= gimple_phi_arg_def (phi
, cond3_phi_edge
->dest_idx
);
2599 cond3
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (cond3_bb
));
2602 cmp3
= gimple_cond_code (cond3
);
2603 lhs3
= gimple_cond_lhs (cond3
);
2604 rhs3
= gimple_cond_rhs (cond3
);
2607 if (!operand_equal_p (rhs3
, rhs1
, 0))
2610 else if (lhs3
== rhs1
)
2618 else if (absu_hwi (tree_to_shwi (arg0
)) != 1
2619 || absu_hwi (tree_to_shwi (arg1
)) != 1
2620 || wi::to_widest (arg0
) == wi::to_widest (arg1
))
2623 if (!integer_zerop (arg3
) || (cmp3
!= EQ_EXPR
&& cmp3
!= NE_EXPR
))
2625 if ((cond3_phi_edge
->flags
& (cmp3
== EQ_EXPR
2626 ? EDGE_TRUE_VALUE
: EDGE_FALSE_VALUE
)) == 0)
2629 /* lhs1 one_cmp rhs1 results in phires of 1. */
2630 enum tree_code one_cmp
;
2631 if ((cmp1
== LT_EXPR
|| cmp1
== LE_EXPR
)
2632 ^ (!integer_onep ((e1
->flags
& EDGE_TRUE_VALUE
) ? arg1
: arg0
)))
2637 enum tree_code res_cmp
;
2641 if (integer_zerop (rhs
))
2643 else if (integer_minus_onep (rhs
))
2644 res_cmp
= one_cmp
== LT_EXPR
? GT_EXPR
: LT_EXPR
;
2645 else if (integer_onep (rhs
))
2651 if (integer_zerop (rhs
))
2653 else if (integer_minus_onep (rhs
))
2654 res_cmp
= one_cmp
== LT_EXPR
? LE_EXPR
: GE_EXPR
;
2655 else if (integer_onep (rhs
))
2656 res_cmp
= one_cmp
== LT_EXPR
? GE_EXPR
: LE_EXPR
;
2661 if (integer_onep (rhs
))
2662 res_cmp
= one_cmp
== LT_EXPR
? GE_EXPR
: LE_EXPR
;
2663 else if (integer_zerop (rhs
))
2664 res_cmp
= one_cmp
== LT_EXPR
? GT_EXPR
: LT_EXPR
;
2669 if (integer_zerop (rhs
))
2670 res_cmp
= one_cmp
== LT_EXPR
? GE_EXPR
: LE_EXPR
;
2671 else if (integer_minus_onep (rhs
))
2672 res_cmp
= one_cmp
== LT_EXPR
? GT_EXPR
: LT_EXPR
;
2677 if (integer_minus_onep (rhs
))
2678 res_cmp
= one_cmp
== LT_EXPR
? LE_EXPR
: GE_EXPR
;
2679 else if (integer_zerop (rhs
))
2685 if (integer_zerop (rhs
))
2686 res_cmp
= one_cmp
== LT_EXPR
? LE_EXPR
: GE_EXPR
;
2687 else if (integer_onep (rhs
))
2696 if (gimple_code (use_stmt
) == GIMPLE_COND
)
2698 gcond
*use_cond
= as_a
<gcond
*> (use_stmt
);
2699 gimple_cond_set_code (use_cond
, res_cmp
);
2700 gimple_cond_set_lhs (use_cond
, lhs1
);
2701 gimple_cond_set_rhs (use_cond
, rhs1
);
2703 else if (gimple_assign_rhs_class (use_stmt
) == GIMPLE_BINARY_RHS
)
2705 gimple_assign_set_rhs_code (use_stmt
, res_cmp
);
2706 gimple_assign_set_rhs1 (use_stmt
, lhs1
);
2707 gimple_assign_set_rhs2 (use_stmt
, rhs1
);
2711 tree cond
= build2 (res_cmp
, TREE_TYPE (gimple_assign_rhs1 (use_stmt
)),
2713 gimple_assign_set_rhs1 (use_stmt
, cond
);
2715 update_stmt (use_stmt
);
2717 if (MAY_HAVE_DEBUG_BIND_STMTS
)
2719 use_operand_p use_p
;
2720 imm_use_iterator iter
;
2721 bool has_debug_uses
= false;
2722 bool has_cast_debug_uses
= false;
2723 FOR_EACH_IMM_USE_FAST (use_p
, iter
, phires
)
2725 gimple
*use_stmt
= USE_STMT (use_p
);
2726 if (orig_use_lhs
&& use_stmt
== orig_use_stmt
)
2728 gcc_assert (is_gimple_debug (use_stmt
));
2729 has_debug_uses
= true;
2734 if (!has_debug_uses
|| is_cast
)
2735 FOR_EACH_IMM_USE_FAST (use_p
, iter
, orig_use_lhs
)
2737 gimple
*use_stmt
= USE_STMT (use_p
);
2738 gcc_assert (is_gimple_debug (use_stmt
));
2739 has_debug_uses
= true;
2741 has_cast_debug_uses
= true;
2743 gimple_stmt_iterator gsi
= gsi_for_stmt (orig_use_stmt
);
2744 tree zero
= build_zero_cst (TREE_TYPE (orig_use_lhs
));
2745 gimple_assign_set_rhs_with_ops (&gsi
, INTEGER_CST
, zero
);
2746 update_stmt (orig_use_stmt
);
2751 /* If there are debug uses, emit something like:
2752 # DEBUG D#1 => i_2(D) > j_3(D) ? 1 : -1
2753 # DEBUG D#2 => i_2(D) == j_3(D) ? 0 : D#1
2754 where > stands for the comparison that yielded 1
2755 and replace debug uses of phi result with that D#2.
2756 Ignore the value of 2, because if NaNs aren't expected,
2757 all floating point numbers should be comparable. */
2758 gimple_stmt_iterator gsi
= gsi_after_labels (gimple_bb (phi
));
2759 tree type
= TREE_TYPE (phires
);
2760 tree temp1
= build_debug_expr_decl (type
);
2761 tree t
= build2 (one_cmp
, boolean_type_node
, lhs1
, rhs2
);
2762 t
= build3 (COND_EXPR
, type
, t
, build_one_cst (type
),
2763 build_int_cst (type
, -1));
2764 gimple
*g
= gimple_build_debug_bind (temp1
, t
, phi
);
2765 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2766 tree temp2
= build_debug_expr_decl (type
);
2767 t
= build2 (EQ_EXPR
, boolean_type_node
, lhs1
, rhs2
);
2768 t
= build3 (COND_EXPR
, type
, t
, build_zero_cst (type
), temp1
);
2769 g
= gimple_build_debug_bind (temp2
, t
, phi
);
2770 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2771 replace_uses_by (phires
, temp2
);
2774 if (has_cast_debug_uses
)
2776 tree temp3
= make_node (DEBUG_EXPR_DECL
);
2777 DECL_ARTIFICIAL (temp3
) = 1;
2778 TREE_TYPE (temp3
) = TREE_TYPE (orig_use_lhs
);
2779 SET_DECL_MODE (temp3
, TYPE_MODE (type
));
2780 t
= fold_convert (TREE_TYPE (temp3
), temp2
);
2781 g
= gimple_build_debug_bind (temp3
, t
, phi
);
2782 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2783 replace_uses_by (orig_use_lhs
, temp3
);
2786 replace_uses_by (orig_use_lhs
, temp2
);
2793 gimple_stmt_iterator gsi
= gsi_for_stmt (orig_use_stmt
);
2794 gsi_remove (&gsi
, true);
2797 gimple_stmt_iterator psi
= gsi_for_stmt (phi
);
2798 remove_phi_node (&psi
, true);
2799 statistics_counter_event (cfun
, "spaceship replacement", 1);
2804 /* Optimize x ? __builtin_fun (x) : C, where C is __builtin_fun (0).
2814 _2 = (unsigned long) b_4(D);
2815 _9 = __builtin_popcountl (_2);
2817 _9 = __builtin_popcountl (b_4(D));
2820 c_12 = PHI <0(2), _9(3)>
2824 _2 = (unsigned long) b_4(D);
2825 _9 = __builtin_popcountl (_2);
2827 _9 = __builtin_popcountl (b_4(D));
2832 Similarly for __builtin_clz or __builtin_ctz if
2833 C?Z_DEFINED_VALUE_AT_ZERO is 2, optab is present and
2834 instead of 0 above it uses the value from that macro. */
2837 cond_removal_in_builtin_zero_pattern (basic_block cond_bb
,
2838 basic_block middle_bb
,
2839 edge e1
, edge e2
, gphi
*phi
,
2840 tree arg0
, tree arg1
)
2842 gimple_stmt_iterator gsi
, gsi_from
;
2844 gimple
*cast
= NULL
;
2848 _2 = (unsigned long) b_4(D);
2849 _9 = __builtin_popcountl (_2);
2851 _9 = __builtin_popcountl (b_4(D));
2852 are the only stmts in the middle_bb. */
2854 gsi
= gsi_start_nondebug_after_labels_bb (middle_bb
);
2855 if (gsi_end_p (gsi
))
2857 cast
= gsi_stmt (gsi
);
2858 gsi_next_nondebug (&gsi
);
2859 if (!gsi_end_p (gsi
))
2861 call
= gsi_stmt (gsi
);
2862 gsi_next_nondebug (&gsi
);
2863 if (!gsi_end_p (gsi
))
2872 /* Check that we have a popcount/clz/ctz builtin. */
2873 if (!is_gimple_call (call
))
2876 lhs
= gimple_get_lhs (call
);
2878 if (lhs
== NULL_TREE
)
2881 combined_fn cfn
= gimple_call_combined_fn (call
);
2882 if (gimple_call_num_args (call
) != 1
2883 && (gimple_call_num_args (call
) != 2
2888 arg
= gimple_call_arg (call
, 0);
2890 internal_fn ifn
= IFN_LAST
;
2892 bool any_val
= false;
2895 case CFN_BUILT_IN_BSWAP16
:
2896 case CFN_BUILT_IN_BSWAP32
:
2897 case CFN_BUILT_IN_BSWAP64
:
2898 case CFN_BUILT_IN_BSWAP128
:
2904 if (INTEGRAL_TYPE_P (TREE_TYPE (arg
)))
2906 tree type
= TREE_TYPE (arg
);
2907 if (TREE_CODE (type
) == BITINT_TYPE
)
2909 if (gimple_call_num_args (call
) == 1)
2915 if (!tree_fits_shwi_p (gimple_call_arg (call
, 1)))
2917 HOST_WIDE_INT at_zero
= tree_to_shwi (gimple_call_arg (call
, 1));
2918 if ((int) at_zero
!= at_zero
)
2924 if (direct_internal_fn_supported_p (IFN_CLZ
, type
, OPTIMIZE_FOR_BOTH
)
2925 && CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type
),
2934 if (INTEGRAL_TYPE_P (TREE_TYPE (arg
)))
2936 tree type
= TREE_TYPE (arg
);
2937 if (TREE_CODE (type
) == BITINT_TYPE
)
2939 if (gimple_call_num_args (call
) == 1)
2945 if (!tree_fits_shwi_p (gimple_call_arg (call
, 1)))
2947 HOST_WIDE_INT at_zero
= tree_to_shwi (gimple_call_arg (call
, 1));
2948 if ((int) at_zero
!= at_zero
)
2954 if (direct_internal_fn_supported_p (IFN_CTZ
, type
, OPTIMIZE_FOR_BOTH
)
2955 && CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type
),
2963 case CFN_BUILT_IN_CLRSB
:
2964 val
= TYPE_PRECISION (integer_type_node
) - 1;
2966 case CFN_BUILT_IN_CLRSBL
:
2967 val
= TYPE_PRECISION (long_integer_type_node
) - 1;
2969 case CFN_BUILT_IN_CLRSBLL
:
2970 val
= TYPE_PRECISION (long_long_integer_type_node
) - 1;
2978 /* We have a cast stmt feeding popcount/clz/ctz builtin. */
2979 /* Check that we have a cast prior to that. */
2980 if (gimple_code (cast
) != GIMPLE_ASSIGN
2981 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (cast
)))
2983 /* Result of the cast stmt is the argument to the builtin. */
2984 if (arg
!= gimple_assign_lhs (cast
))
2986 arg
= gimple_assign_rhs1 (cast
);
2989 gcond
*cond
= dyn_cast
<gcond
*> (*gsi_last_bb (cond_bb
));
2991 /* Cond_bb has a check for b_4 [!=|==] 0 before calling the popcount/clz/ctz
2994 || (gimple_cond_code (cond
) != NE_EXPR
2995 && gimple_cond_code (cond
) != EQ_EXPR
)
2996 || !integer_zerop (gimple_cond_rhs (cond
))
2997 || arg
!= gimple_cond_lhs (cond
))
3001 if ((e2
->flags
& EDGE_TRUE_VALUE
3002 && gimple_cond_code (cond
) == NE_EXPR
)
3003 || (e1
->flags
& EDGE_TRUE_VALUE
3004 && gimple_cond_code (cond
) == EQ_EXPR
))
3006 std::swap (arg0
, arg1
);
3010 /* Check PHI arguments. */
3012 || TREE_CODE (arg1
) != INTEGER_CST
)
3016 if (!tree_fits_shwi_p (arg1
))
3018 HOST_WIDE_INT at_zero
= tree_to_shwi (arg1
);
3019 if ((int) at_zero
!= at_zero
)
3023 else if (wi::to_wide (arg1
) != val
)
3026 /* And insert the popcount/clz/ctz builtin and cast stmt before the
3028 gsi
= gsi_last_bb (cond_bb
);
3031 gsi_from
= gsi_for_stmt (cast
);
3032 gsi_move_before (&gsi_from
, &gsi
);
3033 reset_flow_sensitive_info (gimple_get_lhs (cast
));
3035 gsi_from
= gsi_for_stmt (call
);
3037 || (gimple_call_internal_p (call
) && gimple_call_num_args (call
) == 2))
3038 gsi_move_before (&gsi_from
, &gsi
);
3041 /* For __builtin_c[lt]z* force .C[LT]Z ifn, because only
3042 the latter is well defined at zero. */
3043 call
= gimple_build_call_internal (ifn
, 2, gimple_call_arg (call
, 0),
3044 build_int_cst (integer_type_node
, val
));
3045 gimple_call_set_lhs (call
, lhs
);
3046 gsi_insert_before (&gsi
, call
, GSI_SAME_STMT
);
3047 gsi_remove (&gsi_from
, true);
3049 reset_flow_sensitive_info (lhs
);
3051 /* Now update the PHI and remove unneeded bbs. */
3052 replace_phi_edge_with_variable (cond_bb
, e2
, phi
, lhs
);
3056 /* Auxiliary functions to determine the set of memory accesses which
3057 can't trap because they are preceded by accesses to the same memory
3058 portion. We do that for MEM_REFs, so we only need to track
3059 the SSA_NAME of the pointer indirectly referenced. The algorithm
3060 simply is a walk over all instructions in dominator order. When
3061 we see an MEM_REF we determine if we've already seen a same
3062 ref anywhere up to the root of the dominator tree. If we do the
3063 current access can't trap. If we don't see any dominating access
3064 the current access might trap, but might also make later accesses
3065 non-trapping, so we remember it. We need to be careful with loads
3066 or stores, for instance a load might not trap, while a store would,
3067 so if we see a dominating read access this doesn't mean that a later
3068 write access would not trap. Hence we also need to differentiate the
3069 type of access(es) seen.
3071 ??? We currently are very conservative and assume that a load might
3072 trap even if a store doesn't (write-only memory). This probably is
3073 overly conservative.
3075 We currently support a special case that for !TREE_ADDRESSABLE automatic
3076 variables, it could ignore whether something is a load or store because the
3077 local stack should be always writable. */
3079 /* A hash-table of references (MEM_REF/ARRAY_REF/COMPONENT_REF), and in which
3080 basic block an *_REF through it was seen, which would constitute a
3081 no-trap region for same accesses.
3083 Size is needed to support 2 MEM_REFs of different types, like
3084 MEM<double>(s_1) and MEM<long>(s_1), which would compare equal with
3094 /* Hashtable helpers. */
3096 struct refs_hasher
: free_ptr_hash
<ref_to_bb
>
3098 static inline hashval_t
hash (const ref_to_bb
*);
3099 static inline bool equal (const ref_to_bb
*, const ref_to_bb
*);
3102 /* Used for quick clearing of the hash-table when we see calls.
3103 Hash entries with phase < nt_call_phase are invalid. */
3104 static unsigned int nt_call_phase
;
3106 /* The hash function. */
3109 refs_hasher::hash (const ref_to_bb
*n
)
3111 inchash::hash hstate
;
3112 inchash::add_expr (n
->exp
, hstate
, OEP_ADDRESS_OF
);
3113 hstate
.add_hwi (n
->size
);
3114 return hstate
.end ();
3117 /* The equality function of *P1 and *P2. */
3120 refs_hasher::equal (const ref_to_bb
*n1
, const ref_to_bb
*n2
)
3122 return operand_equal_p (n1
->exp
, n2
->exp
, OEP_ADDRESS_OF
)
3123 && n1
->size
== n2
->size
;
3126 class nontrapping_dom_walker
: public dom_walker
3129 nontrapping_dom_walker (cdi_direction direction
, hash_set
<tree
> *ps
)
3130 : dom_walker (direction
), m_nontrapping (ps
), m_seen_refs (128)
3133 edge
before_dom_children (basic_block
) final override
;
3134 void after_dom_children (basic_block
) final override
;
3138 /* We see the expression EXP in basic block BB. If it's an interesting
3139 expression (an MEM_REF through an SSA_NAME) possibly insert the
3140 expression into the set NONTRAP or the hash table of seen expressions.
3141 STORE is true if this expression is on the LHS, otherwise it's on
3143 void add_or_mark_expr (basic_block
, tree
, bool);
3145 hash_set
<tree
> *m_nontrapping
;
3147 /* The hash table for remembering what we've seen. */
3148 hash_table
<refs_hasher
> m_seen_refs
;
3151 /* Called by walk_dominator_tree, when entering the block BB. */
3153 nontrapping_dom_walker::before_dom_children (basic_block bb
)
3157 gimple_stmt_iterator gsi
;
3159 /* If we haven't seen all our predecessors, clear the hash-table. */
3160 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3161 if ((((size_t)e
->src
->aux
) & 2) == 0)
3167 /* Mark this BB as being on the path to dominator root and as visited. */
3168 bb
->aux
= (void*)(1 | 2);
3170 /* And walk the statements in order. */
3171 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3173 gimple
*stmt
= gsi_stmt (gsi
);
3175 if ((gimple_code (stmt
) == GIMPLE_ASM
&& gimple_vdef (stmt
))
3176 || (is_gimple_call (stmt
)
3177 && (!nonfreeing_call_p (stmt
) || !nonbarrier_call_p (stmt
))))
3179 else if (gimple_assign_single_p (stmt
) && !gimple_has_volatile_ops (stmt
))
3181 add_or_mark_expr (bb
, gimple_assign_lhs (stmt
), true);
3182 add_or_mark_expr (bb
, gimple_assign_rhs1 (stmt
), false);
3188 /* Called by walk_dominator_tree, when basic block BB is exited. */
3190 nontrapping_dom_walker::after_dom_children (basic_block bb
)
3192 /* This BB isn't on the path to dominator root anymore. */
3196 /* We see the expression EXP in basic block BB. If it's an interesting
3201 possibly insert the expression into the set NONTRAP or the hash table
3202 of seen expressions. STORE is true if this expression is on the LHS,
3203 otherwise it's on the RHS. */
3205 nontrapping_dom_walker::add_or_mark_expr (basic_block bb
, tree exp
, bool store
)
3209 if ((TREE_CODE (exp
) == MEM_REF
|| TREE_CODE (exp
) == ARRAY_REF
3210 || TREE_CODE (exp
) == COMPONENT_REF
)
3211 && (size
= int_size_in_bytes (TREE_TYPE (exp
))) > 0)
3213 struct ref_to_bb map
;
3215 struct ref_to_bb
*r2bb
;
3216 basic_block found_bb
= 0;
3220 tree base
= get_base_address (exp
);
3221 /* Only record a LOAD of a local variable without address-taken, as
3222 the local stack is always writable. This allows cselim on a STORE
3223 with a dominating LOAD. */
3224 if (!auto_var_p (base
) || TREE_ADDRESSABLE (base
))
3228 /* Try to find the last seen *_REF, which can trap. */
3231 slot
= m_seen_refs
.find_slot (&map
, INSERT
);
3233 if (r2bb
&& r2bb
->phase
>= nt_call_phase
)
3234 found_bb
= r2bb
->bb
;
3236 /* If we've found a trapping *_REF, _and_ it dominates EXP
3237 (it's in a basic block on the path from us to the dominator root)
3238 then we can't trap. */
3239 if (found_bb
&& (((size_t)found_bb
->aux
) & 1) == 1)
3241 m_nontrapping
->add (exp
);
3245 /* EXP might trap, so insert it into the hash table. */
3248 r2bb
->phase
= nt_call_phase
;
3253 r2bb
= XNEW (struct ref_to_bb
);
3254 r2bb
->phase
= nt_call_phase
;
3264 /* This is the entry point of gathering non trapping memory accesses.
3265 It will do a dominator walk over the whole function, and it will
3266 make use of the bb->aux pointers. It returns a set of trees
3267 (the MEM_REFs itself) which can't trap. */
3268 static hash_set
<tree
> *
3269 get_non_trapping (void)
3272 hash_set
<tree
> *nontrap
= new hash_set
<tree
>;
3274 nontrapping_dom_walker (CDI_DOMINATORS
, nontrap
)
3275 .walk (cfun
->cfg
->x_entry_block_ptr
);
3277 clear_aux_for_blocks ();
3281 /* Do the main work of conditional store replacement. We already know
3282 that the recognized pattern looks like so:
3285 if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
3288 fallthrough (edge E0)
3292 We check that MIDDLE_BB contains only one store, that that store
3293 doesn't trap (not via NOTRAP, but via checking if an access to the same
3294 memory location dominates us, or the store is to a local addressable
3295 object) and that the store has a "simple" RHS. */
3298 cond_store_replacement (basic_block middle_bb
, basic_block join_bb
,
3299 edge e0
, edge e1
, hash_set
<tree
> *nontrap
)
3301 gimple
*assign
= last_and_only_stmt (middle_bb
);
3302 tree lhs
, rhs
, name
, name2
;
3305 gimple_stmt_iterator gsi
;
3308 /* Check if middle_bb contains of only one store. */
3310 || !gimple_assign_single_p (assign
)
3311 || gimple_has_volatile_ops (assign
))
3314 /* And no PHI nodes so all uses in the single stmt are also
3315 available where we insert to. */
3316 if (!gimple_seq_empty_p (phi_nodes (middle_bb
)))
3319 locus
= gimple_location (assign
);
3320 lhs
= gimple_assign_lhs (assign
);
3321 rhs
= gimple_assign_rhs1 (assign
);
3322 if ((!REFERENCE_CLASS_P (lhs
)
3324 || !is_gimple_reg_type (TREE_TYPE (lhs
)))
3327 /* Prove that we can move the store down. We could also check
3328 TREE_THIS_NOTRAP here, but in that case we also could move stores,
3329 whose value is not available readily, which we want to avoid. */
3330 if (!nontrap
->contains (lhs
))
3332 /* If LHS is an access to a local variable without address-taken
3333 (or when we allow data races) and known not to trap, we could
3334 always safely move down the store. */
3335 tree base
= get_base_address (lhs
);
3336 if (!auto_var_p (base
)
3337 || (TREE_ADDRESSABLE (base
) && !flag_store_data_races
)
3338 || tree_could_trap_p (lhs
))
3342 /* Now we've checked the constraints, so do the transformation:
3343 1) Remove the single store. */
3344 gsi
= gsi_for_stmt (assign
);
3345 unlink_stmt_vdef (assign
);
3346 gsi_remove (&gsi
, true);
3347 release_defs (assign
);
3349 /* Make both store and load use alias-set zero as we have to
3350 deal with the case of the store being a conditional change
3351 of the dynamic type. */
3352 lhs
= unshare_expr (lhs
);
3354 while (handled_component_p (*basep
))
3355 basep
= &TREE_OPERAND (*basep
, 0);
3356 if (TREE_CODE (*basep
) == MEM_REF
3357 || TREE_CODE (*basep
) == TARGET_MEM_REF
)
3358 TREE_OPERAND (*basep
, 1)
3359 = fold_convert (ptr_type_node
, TREE_OPERAND (*basep
, 1));
3361 *basep
= build2 (MEM_REF
, TREE_TYPE (*basep
),
3362 build_fold_addr_expr (*basep
),
3363 build_zero_cst (ptr_type_node
));
3365 /* 2) Insert a load from the memory of the store to the temporary
3366 on the edge which did not contain the store. */
3367 name
= make_temp_ssa_name (TREE_TYPE (lhs
), NULL
, "cstore");
3368 new_stmt
= gimple_build_assign (name
, lhs
);
3369 gimple_set_location (new_stmt
, locus
);
3370 lhs
= unshare_expr (lhs
);
3372 /* Set the no-warning bit on the rhs of the load to avoid uninit
3374 tree rhs1
= gimple_assign_rhs1 (new_stmt
);
3375 suppress_warning (rhs1
, OPT_Wuninitialized
);
3377 gsi_insert_on_edge (e1
, new_stmt
);
3379 /* 3) Create a PHI node at the join block, with one argument
3380 holding the old RHS, and the other holding the temporary
3381 where we stored the old memory contents. */
3382 name2
= make_temp_ssa_name (TREE_TYPE (lhs
), NULL
, "cstore");
3383 newphi
= create_phi_node (name2
, join_bb
);
3384 add_phi_arg (newphi
, rhs
, e0
, locus
);
3385 add_phi_arg (newphi
, name
, e1
, locus
);
3387 new_stmt
= gimple_build_assign (lhs
, PHI_RESULT (newphi
));
3389 /* 4) Insert that PHI node. */
3390 gsi
= gsi_after_labels (join_bb
);
3391 if (gsi_end_p (gsi
))
3393 gsi
= gsi_last_bb (join_bb
);
3394 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
3397 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
3399 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3401 fprintf (dump_file
, "\nConditional store replacement happened!");
3402 fprintf (dump_file
, "\nReplaced the store with a load.");
3403 fprintf (dump_file
, "\nInserted a new PHI statement in joint block:\n");
3404 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
);
3406 statistics_counter_event (cfun
, "conditional store replacement", 1);
3411 /* Do the main work of conditional store replacement. */
3414 cond_if_else_store_replacement_1 (basic_block then_bb
, basic_block else_bb
,
3415 basic_block join_bb
, gimple
*then_assign
,
3416 gimple
*else_assign
)
3418 tree lhs_base
, lhs
, then_rhs
, else_rhs
, name
;
3419 location_t then_locus
, else_locus
;
3420 gimple_stmt_iterator gsi
;
3424 if (then_assign
== NULL
3425 || !gimple_assign_single_p (then_assign
)
3426 || gimple_clobber_p (then_assign
)
3427 || gimple_has_volatile_ops (then_assign
)
3428 || else_assign
== NULL
3429 || !gimple_assign_single_p (else_assign
)
3430 || gimple_clobber_p (else_assign
)
3431 || gimple_has_volatile_ops (else_assign
))
3434 lhs
= gimple_assign_lhs (then_assign
);
3435 if (!is_gimple_reg_type (TREE_TYPE (lhs
))
3436 || !operand_equal_p (lhs
, gimple_assign_lhs (else_assign
), 0))
3439 lhs_base
= get_base_address (lhs
);
3440 if (lhs_base
== NULL_TREE
3441 || (!DECL_P (lhs_base
) && TREE_CODE (lhs_base
) != MEM_REF
))
3444 then_rhs
= gimple_assign_rhs1 (then_assign
);
3445 else_rhs
= gimple_assign_rhs1 (else_assign
);
3446 then_locus
= gimple_location (then_assign
);
3447 else_locus
= gimple_location (else_assign
);
3449 /* Now we've checked the constraints, so do the transformation:
3450 1) Remove the stores. */
3451 gsi
= gsi_for_stmt (then_assign
);
3452 unlink_stmt_vdef (then_assign
);
3453 gsi_remove (&gsi
, true);
3454 release_defs (then_assign
);
3456 gsi
= gsi_for_stmt (else_assign
);
3457 unlink_stmt_vdef (else_assign
);
3458 gsi_remove (&gsi
, true);
3459 release_defs (else_assign
);
3461 /* 2) Create a PHI node at the join block, with one argument
3462 holding the old RHS, and the other holding the temporary
3463 where we stored the old memory contents. */
3464 name
= make_temp_ssa_name (TREE_TYPE (lhs
), NULL
, "cstore");
3465 newphi
= create_phi_node (name
, join_bb
);
3466 add_phi_arg (newphi
, then_rhs
, EDGE_SUCC (then_bb
, 0), then_locus
);
3467 add_phi_arg (newphi
, else_rhs
, EDGE_SUCC (else_bb
, 0), else_locus
);
3469 new_stmt
= gimple_build_assign (lhs
, PHI_RESULT (newphi
));
3471 /* 3) Insert that PHI node. */
3472 gsi
= gsi_after_labels (join_bb
);
3473 if (gsi_end_p (gsi
))
3475 gsi
= gsi_last_bb (join_bb
);
3476 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
3479 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
3481 statistics_counter_event (cfun
, "if-then-else store replacement", 1);
3486 /* Return the single store in BB with VDEF or NULL if there are
3487 other stores in the BB or loads following the store. */
3490 single_trailing_store_in_bb (basic_block bb
, tree vdef
)
3492 if (SSA_NAME_IS_DEFAULT_DEF (vdef
))
3494 gimple
*store
= SSA_NAME_DEF_STMT (vdef
);
3495 if (gimple_bb (store
) != bb
3496 || gimple_code (store
) == GIMPLE_PHI
)
3499 /* Verify there is no other store in this BB. */
3500 if (!SSA_NAME_IS_DEFAULT_DEF (gimple_vuse (store
))
3501 && gimple_bb (SSA_NAME_DEF_STMT (gimple_vuse (store
))) == bb
3502 && gimple_code (SSA_NAME_DEF_STMT (gimple_vuse (store
))) != GIMPLE_PHI
)
3505 /* Verify there is no load or store after the store. */
3506 use_operand_p use_p
;
3507 imm_use_iterator imm_iter
;
3508 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_vdef (store
))
3509 if (USE_STMT (use_p
) != store
3510 && gimple_bb (USE_STMT (use_p
)) == bb
)
3516 /* Conditional store replacement. We already know
3517 that the recognized pattern looks like so:
3520 if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
3530 fallthrough (edge E0)
3534 We check that it is safe to sink the store to JOIN_BB by verifying that
3535 there are no read-after-write or write-after-write dependencies in
3536 THEN_BB and ELSE_BB. */
3539 cond_if_else_store_replacement (basic_block then_bb
, basic_block else_bb
,
3540 basic_block join_bb
)
3542 vec
<data_reference_p
> then_datarefs
, else_datarefs
;
3543 vec
<ddr_p
> then_ddrs
, else_ddrs
;
3544 gimple
*then_store
, *else_store
;
3545 bool found
, ok
= false, res
;
3546 struct data_dependence_relation
*ddr
;
3547 data_reference_p then_dr
, else_dr
;
3549 tree then_lhs
, else_lhs
;
3550 basic_block blocks
[3];
3552 /* Handle the case with single store in THEN_BB and ELSE_BB. That is
3553 cheap enough to always handle as it allows us to elide dependence
3556 for (gphi_iterator si
= gsi_start_phis (join_bb
); !gsi_end_p (si
);
3558 if (virtual_operand_p (gimple_phi_result (si
.phi ())))
3565 tree then_vdef
= PHI_ARG_DEF_FROM_EDGE (vphi
, single_succ_edge (then_bb
));
3566 tree else_vdef
= PHI_ARG_DEF_FROM_EDGE (vphi
, single_succ_edge (else_bb
));
3567 gimple
*then_assign
= single_trailing_store_in_bb (then_bb
, then_vdef
);
3570 gimple
*else_assign
= single_trailing_store_in_bb (else_bb
, else_vdef
);
3572 return cond_if_else_store_replacement_1 (then_bb
, else_bb
, join_bb
,
3573 then_assign
, else_assign
);
3576 /* If either vectorization or if-conversion is disabled then do
3577 not sink any stores. */
3578 if (param_max_stores_to_sink
== 0
3579 || (!flag_tree_loop_vectorize
&& !flag_tree_slp_vectorize
)
3580 || !flag_tree_loop_if_convert
)
3583 /* Find data references. */
3584 then_datarefs
.create (1);
3585 else_datarefs
.create (1);
3586 if ((find_data_references_in_bb (NULL
, then_bb
, &then_datarefs
)
3588 || !then_datarefs
.length ()
3589 || (find_data_references_in_bb (NULL
, else_bb
, &else_datarefs
)
3591 || !else_datarefs
.length ())
3593 free_data_refs (then_datarefs
);
3594 free_data_refs (else_datarefs
);
3598 /* Find pairs of stores with equal LHS. */
3599 auto_vec
<gimple
*, 1> then_stores
, else_stores
;
3600 FOR_EACH_VEC_ELT (then_datarefs
, i
, then_dr
)
3602 if (DR_IS_READ (then_dr
))
3605 then_store
= DR_STMT (then_dr
);
3606 then_lhs
= gimple_get_lhs (then_store
);
3607 if (then_lhs
== NULL_TREE
)
3611 FOR_EACH_VEC_ELT (else_datarefs
, j
, else_dr
)
3613 if (DR_IS_READ (else_dr
))
3616 else_store
= DR_STMT (else_dr
);
3617 else_lhs
= gimple_get_lhs (else_store
);
3618 if (else_lhs
== NULL_TREE
)
3621 if (operand_equal_p (then_lhs
, else_lhs
, 0))
3631 then_stores
.safe_push (then_store
);
3632 else_stores
.safe_push (else_store
);
3635 /* No pairs of stores found. */
3636 if (!then_stores
.length ()
3637 || then_stores
.length () > (unsigned) param_max_stores_to_sink
)
3639 free_data_refs (then_datarefs
);
3640 free_data_refs (else_datarefs
);
3644 /* Compute and check data dependencies in both basic blocks. */
3645 then_ddrs
.create (1);
3646 else_ddrs
.create (1);
3647 if (!compute_all_dependences (then_datarefs
, &then_ddrs
,
3649 || !compute_all_dependences (else_datarefs
, &else_ddrs
,
3652 free_dependence_relations (then_ddrs
);
3653 free_dependence_relations (else_ddrs
);
3654 free_data_refs (then_datarefs
);
3655 free_data_refs (else_datarefs
);
3658 blocks
[0] = then_bb
;
3659 blocks
[1] = else_bb
;
3660 blocks
[2] = join_bb
;
3661 renumber_gimple_stmt_uids_in_blocks (blocks
, 3);
3663 /* Check that there are no read-after-write or write-after-write dependencies
3665 FOR_EACH_VEC_ELT (then_ddrs
, i
, ddr
)
3667 struct data_reference
*dra
= DDR_A (ddr
);
3668 struct data_reference
*drb
= DDR_B (ddr
);
3670 if (DDR_ARE_DEPENDENT (ddr
) != chrec_known
3671 && ((DR_IS_READ (dra
) && DR_IS_WRITE (drb
)
3672 && gimple_uid (DR_STMT (dra
)) > gimple_uid (DR_STMT (drb
)))
3673 || (DR_IS_READ (drb
) && DR_IS_WRITE (dra
)
3674 && gimple_uid (DR_STMT (drb
)) > gimple_uid (DR_STMT (dra
)))
3675 || (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))))
3677 free_dependence_relations (then_ddrs
);
3678 free_dependence_relations (else_ddrs
);
3679 free_data_refs (then_datarefs
);
3680 free_data_refs (else_datarefs
);
3685 /* Check that there are no read-after-write or write-after-write dependencies
3687 FOR_EACH_VEC_ELT (else_ddrs
, i
, ddr
)
3689 struct data_reference
*dra
= DDR_A (ddr
);
3690 struct data_reference
*drb
= DDR_B (ddr
);
3692 if (DDR_ARE_DEPENDENT (ddr
) != chrec_known
3693 && ((DR_IS_READ (dra
) && DR_IS_WRITE (drb
)
3694 && gimple_uid (DR_STMT (dra
)) > gimple_uid (DR_STMT (drb
)))
3695 || (DR_IS_READ (drb
) && DR_IS_WRITE (dra
)
3696 && gimple_uid (DR_STMT (drb
)) > gimple_uid (DR_STMT (dra
)))
3697 || (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))))
3699 free_dependence_relations (then_ddrs
);
3700 free_dependence_relations (else_ddrs
);
3701 free_data_refs (then_datarefs
);
3702 free_data_refs (else_datarefs
);
3707 /* Sink stores with same LHS. */
3708 FOR_EACH_VEC_ELT (then_stores
, i
, then_store
)
3710 else_store
= else_stores
[i
];
3711 res
= cond_if_else_store_replacement_1 (then_bb
, else_bb
, join_bb
,
3712 then_store
, else_store
);
3716 free_dependence_relations (then_ddrs
);
3717 free_dependence_relations (else_ddrs
);
3718 free_data_refs (then_datarefs
);
3719 free_data_refs (else_datarefs
);
3724 /* Return TRUE if STMT has a VUSE whose corresponding VDEF is in BB. */
3727 local_mem_dependence (gimple
*stmt
, basic_block bb
)
3729 tree vuse
= gimple_vuse (stmt
);
3735 def
= SSA_NAME_DEF_STMT (vuse
);
3736 return (def
&& gimple_bb (def
) == bb
);
3739 /* Given a "diamond" control-flow pattern where BB0 tests a condition,
3740 BB1 and BB2 are "then" and "else" blocks dependent on this test,
3741 and BB3 rejoins control flow following BB1 and BB2, look for
3742 opportunities to hoist loads as follows. If BB3 contains a PHI of
3743 two loads, one each occurring in BB1 and BB2, and the loads are
3744 provably of adjacent fields in the same structure, then move both
3745 loads into BB0. Of course this can only be done if there are no
3746 dependencies preventing such motion.
3748 One of the hoisted loads will always be speculative, so the
3749 transformation is currently conservative:
3751 - The fields must be strictly adjacent.
3752 - The two fields must occupy a single memory block that is
3753 guaranteed to not cross a page boundary.
3755 The last is difficult to prove, as such memory blocks should be
3756 aligned on the minimum of the stack alignment boundary and the
3757 alignment guaranteed by heap allocation interfaces. Thus we rely
3758 on a parameter for the alignment value.
3760 Provided a good value is used for the last case, the first
3761 restriction could possibly be relaxed. */
3764 hoist_adjacent_loads (basic_block bb0
, basic_block bb1
,
3765 basic_block bb2
, basic_block bb3
)
3767 unsigned HOST_WIDE_INT param_align
= param_l1_cache_line_size
;
3768 unsigned HOST_WIDE_INT param_align_bits
= param_align
* BITS_PER_UNIT
;
3771 /* Walk the phis in bb3 looking for an opportunity. We are looking
3772 for phis of two SSA names, one each of which is defined in bb1 and
3774 for (gsi
= gsi_start_phis (bb3
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3776 gphi
*phi_stmt
= gsi
.phi ();
3777 gimple
*def1
, *def2
;
3778 tree arg1
, arg2
, ref1
, ref2
, field1
, field2
;
3779 tree tree_offset1
, tree_offset2
, tree_size2
, next
;
3780 unsigned HOST_WIDE_INT offset1
, offset2
, size2
, align1
;
3781 gimple_stmt_iterator gsi2
;
3782 basic_block bb_for_def1
, bb_for_def2
;
3784 if (gimple_phi_num_args (phi_stmt
) != 2
3785 || virtual_operand_p (gimple_phi_result (phi_stmt
)))
3788 arg1
= gimple_phi_arg_def (phi_stmt
, 0);
3789 arg2
= gimple_phi_arg_def (phi_stmt
, 1);
3791 if (TREE_CODE (arg1
) != SSA_NAME
3792 || TREE_CODE (arg2
) != SSA_NAME
3793 || SSA_NAME_IS_DEFAULT_DEF (arg1
)
3794 || SSA_NAME_IS_DEFAULT_DEF (arg2
))
3797 def1
= SSA_NAME_DEF_STMT (arg1
);
3798 def2
= SSA_NAME_DEF_STMT (arg2
);
3800 if ((gimple_bb (def1
) != bb1
|| gimple_bb (def2
) != bb2
)
3801 && (gimple_bb (def2
) != bb1
|| gimple_bb (def1
) != bb2
))
3804 /* Check the mode of the arguments to be sure a conditional move
3805 can be generated for it. */
3806 if (optab_handler (movcc_optab
, TYPE_MODE (TREE_TYPE (arg1
)))
3807 == CODE_FOR_nothing
)
3810 /* Both statements must be assignments whose RHS is a COMPONENT_REF. */
3811 if (!gimple_assign_single_p (def1
)
3812 || !gimple_assign_single_p (def2
)
3813 || gimple_has_volatile_ops (def1
)
3814 || gimple_has_volatile_ops (def2
))
3817 ref1
= gimple_assign_rhs1 (def1
);
3818 ref2
= gimple_assign_rhs1 (def2
);
3820 if (TREE_CODE (ref1
) != COMPONENT_REF
3821 || TREE_CODE (ref2
) != COMPONENT_REF
)
3824 /* The zeroth operand of the two component references must be
3825 identical. It is not sufficient to compare get_base_address of
3826 the two references, because this could allow for different
3827 elements of the same array in the two trees. It is not safe to
3828 assume that the existence of one array element implies the
3829 existence of a different one. */
3830 if (!operand_equal_p (TREE_OPERAND (ref1
, 0), TREE_OPERAND (ref2
, 0), 0))
3833 field1
= TREE_OPERAND (ref1
, 1);
3834 field2
= TREE_OPERAND (ref2
, 1);
3836 /* Check for field adjacency, and ensure field1 comes first. */
3837 for (next
= DECL_CHAIN (field1
);
3838 next
&& TREE_CODE (next
) != FIELD_DECL
;
3839 next
= DECL_CHAIN (next
))
3844 for (next
= DECL_CHAIN (field2
);
3845 next
&& TREE_CODE (next
) != FIELD_DECL
;
3846 next
= DECL_CHAIN (next
))
3852 std::swap (field1
, field2
);
3853 std::swap (def1
, def2
);
3856 bb_for_def1
= gimple_bb (def1
);
3857 bb_for_def2
= gimple_bb (def2
);
3859 /* Check for proper alignment of the first field. */
3860 tree_offset1
= bit_position (field1
);
3861 tree_offset2
= bit_position (field2
);
3862 tree_size2
= DECL_SIZE (field2
);
3864 if (!tree_fits_uhwi_p (tree_offset1
)
3865 || !tree_fits_uhwi_p (tree_offset2
)
3866 || !tree_fits_uhwi_p (tree_size2
))
3869 offset1
= tree_to_uhwi (tree_offset1
);
3870 offset2
= tree_to_uhwi (tree_offset2
);
3871 size2
= tree_to_uhwi (tree_size2
);
3872 align1
= DECL_ALIGN (field1
) % param_align_bits
;
3874 if (offset1
% BITS_PER_UNIT
!= 0)
3877 /* For profitability, the two field references should fit within
3878 a single cache line. */
3879 if (align1
+ offset2
- offset1
+ size2
> param_align_bits
)
3882 /* The two expressions cannot be dependent upon vdefs defined
3884 if (local_mem_dependence (def1
, bb_for_def1
)
3885 || local_mem_dependence (def2
, bb_for_def2
))
3888 /* The conditions are satisfied; hoist the loads from bb1 and bb2 into
3889 bb0. We hoist the first one first so that a cache miss is handled
3890 efficiently regardless of hardware cache-fill policy. */
3891 gsi2
= gsi_for_stmt (def1
);
3892 gsi_move_to_bb_end (&gsi2
, bb0
);
3893 gsi2
= gsi_for_stmt (def2
);
3894 gsi_move_to_bb_end (&gsi2
, bb0
);
3895 statistics_counter_event (cfun
, "hoisted loads", 1);
3897 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3900 "\nHoisting adjacent loads from %d and %d into %d: \n",
3901 bb_for_def1
->index
, bb_for_def2
->index
, bb0
->index
);
3902 print_gimple_stmt (dump_file
, def1
, 0, TDF_VOPS
|TDF_MEMSYMS
);
3903 print_gimple_stmt (dump_file
, def2
, 0, TDF_VOPS
|TDF_MEMSYMS
);
3908 /* Determine whether we should attempt to hoist adjacent loads out of
3909 diamond patterns in pass_phiopt. Always hoist loads if
3910 -fhoist-adjacent-loads is specified and the target machine has
3911 both a conditional move instruction and a defined cache line size. */
3914 gate_hoist_loads (void)
3916 return (flag_hoist_adjacent_loads
== 1
3917 && param_l1_cache_line_size
3918 && HAVE_conditional_move
);
3921 /* This pass tries to replaces an if-then-else block with an
3922 assignment. We have different kinds of transformations.
3923 Some of these transformations are also performed by the ifcvt
3926 PHI-OPT using Match-and-simplify infrastructure
3927 -----------------------
3929 The PHI-OPT pass will try to use match-and-simplify infrastructure
3930 (gimple_simplify) to do transformations. This is implemented in
3931 match_simplify_replacement.
3933 The way it works is it replaces:
3935 if (cond) goto bb2; else goto bb1;
3938 x = PHI <a (bb1), b (bb0), ...>;
3940 with a statement if it gets simplified from `cond ? b : a`.
3945 x = PHI <a (bb1), x1 (bb0), ...>;
3946 Bb1 might be removed as it becomes unreachable when doing the replacement.
3947 Though bb1 does not have to be considered a forwarding basic block from bb0.
3949 Will try to see if `(!cond) ? a : b` gets simplified (iff !cond simplifies);
3950 this is done not to have an explosion of patterns in match.pd.
3951 Note bb1 does not need to be completely empty, it can contain
3952 one statement which is known not to trap.
3954 It also can handle the case where we have two forwarding bbs (diamond):
3956 if (cond) goto bb2; else goto bb1;
3960 x = PHI <a (bb1), b (bb2), ...>;
3961 And that is replaced with a statement if it is simplified
3962 from `cond ? b : a`.
3963 Again bb1 and bb2 does not have to be completely empty but
3964 each can contain one statement which is known not to trap.
3965 But in this case bb1/bb2 can only be forwarding basic blocks.
3967 This fully replaces the old "Conditional Replacement",
3968 "ABS Replacement" transformations as they are now
3969 implmeneted in match.pd.
3970 Some parts of the "MIN/MAX Replacement" are re-implemented in match.pd.
3975 This transformation, implemented in value_replacement, replaces
3978 if (a != b) goto bb2; else goto bb1;
3981 x = PHI <a (bb1), b (bb0), ...>;
3987 x = PHI <b (bb0), ...>;
3989 This opportunity can sometimes occur as a result of other
3993 Another case caught by value replacement looks like this:
3999 if (t3 != 0) goto bb1; else goto bb2;
4015 This transformation, minmax_replacement replaces
4018 if (a <= b) goto bb2; else goto bb1;
4021 x = PHI <b (bb1), a (bb0), ...>;
4026 x' = MIN_EXPR (a, b)
4028 x = PHI <x' (bb0), ...>;
4030 A similar transformation is done for MAX_EXPR.
4033 This pass also performs a fifth transformation of a slightly different
4036 Factor operations in COND_EXPR
4037 ------------------------------
4039 This transformation factors the unary operations out of COND_EXPR with
4040 factor_out_conditional_operation.
4043 if (a <= CST) goto <bb 3>; else goto <bb 4>;
4047 tmp = PHI <tmp, CST>
4050 if (a <= CST) goto <bb 3>; else goto <bb 4>;
4056 Adjacent Load Hoisting
4057 ----------------------
4059 This transformation replaces
4062 if (...) goto bb2; else goto bb1;
4064 x1 = (<expr>).field1;
4067 x2 = (<expr>).field2;
4074 x1 = (<expr>).field1;
4075 x2 = (<expr>).field2;
4076 if (...) goto bb2; else goto bb1;
4083 The purpose of this transformation is to enable generation of conditional
4084 move instructions such as Intel CMOVE or PowerPC ISEL. Because one of
4085 the loads is speculative, the transformation is restricted to very
4086 specific cases to avoid introducing a page fault. We are looking for
4094 where left and right are typically adjacent pointers in a tree structure. */
4098 const pass_data pass_data_phiopt
=
4100 GIMPLE_PASS
, /* type */
4101 "phiopt", /* name */
4102 OPTGROUP_NONE
, /* optinfo_flags */
4103 TV_TREE_PHIOPT
, /* tv_id */
4104 ( PROP_cfg
| PROP_ssa
), /* properties_required */
4105 0, /* properties_provided */
4106 0, /* properties_destroyed */
4107 0, /* todo_flags_start */
4108 0, /* todo_flags_finish */
4111 class pass_phiopt
: public gimple_opt_pass
4114 pass_phiopt (gcc::context
*ctxt
)
4115 : gimple_opt_pass (pass_data_phiopt
, ctxt
), early_p (false)
4118 /* opt_pass methods: */
4119 opt_pass
* clone () final override
{ return new pass_phiopt (m_ctxt
); }
4120 void set_pass_param (unsigned n
, bool param
) final override
4122 gcc_assert (n
== 0);
4125 bool gate (function
*) final override
{ return flag_ssa_phiopt
; }
4126 unsigned int execute (function
*) final override
;
4130 }; // class pass_phiopt
4135 make_pass_phiopt (gcc::context
*ctxt
)
4137 return new pass_phiopt (ctxt
);
4141 pass_phiopt::execute (function
*)
4143 bool do_hoist_loads
= !early_p
? gate_hoist_loads () : false;
4145 basic_block
*bb_order
;
4147 bool cfgchanged
= false;
4149 calculate_dominance_info (CDI_DOMINATORS
);
4150 mark_ssa_maybe_undefs ();
4152 /* Search every basic block for COND_EXPR we may be able to optimize.
4154 We walk the blocks in order that guarantees that a block with
4155 a single predecessor is processed before the predecessor.
4156 This ensures that we collapse inner ifs before visiting the
4157 outer ones, and also that we do not try to visit a removed
4159 bb_order
= single_pred_before_succ_order ();
4160 n
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
;
4162 for (i
= 0; i
< n
; i
++)
4165 basic_block bb1
, bb2
;
4168 bool diamond_p
= false;
4172 /* Check to see if the last statement is a GIMPLE_COND. */
4173 gcond
*cond_stmt
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (bb
));
4177 e1
= EDGE_SUCC (bb
, 0);
4179 e2
= EDGE_SUCC (bb
, 1);
4182 /* We cannot do the optimization on abnormal edges. */
4183 if ((e1
->flags
& EDGE_ABNORMAL
) != 0
4184 || (e2
->flags
& EDGE_ABNORMAL
) != 0)
4187 /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
4188 if (EDGE_COUNT (bb1
->succs
) == 0
4189 || EDGE_COUNT (bb2
->succs
) == 0)
4192 /* Find the bb which is the fall through to the other. */
4193 if (EDGE_SUCC (bb1
, 0)->dest
== bb2
)
4195 else if (EDGE_SUCC (bb2
, 0)->dest
== bb1
)
4197 std::swap (bb1
, bb2
);
4200 else if (EDGE_SUCC (bb1
, 0)->dest
== EDGE_SUCC (bb2
, 0)->dest
4201 && single_succ_p (bb2
))
4204 e2
= EDGE_SUCC (bb2
, 0);
4205 /* Make sure bb2 is just a fall through. */
4206 if ((e2
->flags
& EDGE_FALLTHRU
) == 0)
4212 e1
= EDGE_SUCC (bb1
, 0);
4214 /* Make sure that bb1 is just a fall through. */
4215 if (!single_succ_p (bb1
)
4216 || (e1
->flags
& EDGE_FALLTHRU
) == 0)
4221 basic_block bb3
= e1
->dest
;
4223 if (!single_pred_p (bb1
)
4224 || !single_pred_p (bb2
))
4228 && !FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt
)))
4229 && EDGE_COUNT (bb
->succs
) == 2
4230 && EDGE_COUNT (bb3
->preds
) == 2
4231 /* If one edge or the other is dominant, a conditional move
4232 is likely to perform worse than the well-predicted branch. */
4233 && !predictable_edge_p (EDGE_SUCC (bb
, 0))
4234 && !predictable_edge_p (EDGE_SUCC (bb
, 1)))
4235 hoist_adjacent_loads (bb
, bb1
, bb2
, bb3
);
4238 gimple_stmt_iterator gsi
;
4239 bool candorest
= true;
4241 /* Check that we're looking for nested phis. */
4242 basic_block merge
= diamond_p
? EDGE_SUCC (bb2
, 0)->dest
: bb2
;
4243 gimple_seq phis
= phi_nodes (merge
);
4245 /* Value replacement can work with more than one PHI
4246 so try that first. */
4247 if (!early_p
&& !diamond_p
)
4248 for (gsi
= gsi_start (phis
); !gsi_end_p (gsi
); gsi_next (&gsi
))
4250 phi
= as_a
<gphi
*> (gsi_stmt (gsi
));
4251 arg0
= gimple_phi_arg_def (phi
, e1
->dest_idx
);
4252 arg1
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
4253 if (value_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
) == 2)
4264 phi
= single_non_singleton_phi_for_edges (phis
, e1
, e2
);
4268 arg0
= gimple_phi_arg_def (phi
, e1
->dest_idx
);
4269 arg1
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
4271 /* Something is wrong if we cannot find the arguments in the PHI
4273 gcc_assert (arg0
!= NULL_TREE
&& arg1
!= NULL_TREE
);
4275 if (single_pred_p (bb1
)
4276 && EDGE_COUNT (merge
->preds
) == 2)
4282 /* factor_out_conditional_operation may create a new PHI in
4283 BB2 and eliminate an existing PHI in BB2. Recompute values
4284 that may be affected by that change. */
4285 arg0
= gimple_phi_arg_def (phi
, e1
->dest_idx
);
4286 arg1
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
4287 gcc_assert (arg0
!= NULL_TREE
&& arg1
!= NULL_TREE
);
4288 newphi
= factor_out_conditional_operation (e1
, e2
, phi
,
4294 /* Do the replacement of conditional if it can be done. */
4295 if (match_simplify_replacement (bb
, bb1
, bb2
, e1
, e2
, phi
,
4296 arg0
, arg1
, early_p
, diamond_p
))
4300 && single_pred_p (bb1
)
4301 && cond_removal_in_builtin_zero_pattern (bb
, bb1
, e1
, e2
,
4304 else if (minmax_replacement (bb
, bb1
, bb2
, e1
, e2
, phi
, arg0
, arg1
,
4307 else if (single_pred_p (bb1
)
4309 && spaceship_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
))
4316 return TODO_cleanup_cfg
;
4320 /* This pass tries to transform conditional stores into unconditional
4321 ones, enabling further simplifications with the simpler then and else
4322 blocks. In particular it replaces this:
4325 if (cond) goto bb2; else goto bb1;
4333 if (cond) goto bb1; else goto bb2;
4337 condtmp = PHI <RHS, condtmp'>
4340 This transformation can only be done under several constraints,
4341 documented below. It also replaces:
4344 if (cond) goto bb2; else goto bb1;
4355 if (cond) goto bb3; else goto bb1;
4358 condtmp = PHI <RHS1, RHS2>
4363 const pass_data pass_data_cselim
=
4365 GIMPLE_PASS
, /* type */
4366 "cselim", /* name */
4367 OPTGROUP_NONE
, /* optinfo_flags */
4368 TV_TREE_PHIOPT
, /* tv_id */
4369 ( PROP_cfg
| PROP_ssa
), /* properties_required */
4370 0, /* properties_provided */
4371 0, /* properties_destroyed */
4372 0, /* todo_flags_start */
4373 0, /* todo_flags_finish */
4376 class pass_cselim
: public gimple_opt_pass
4379 pass_cselim (gcc::context
*ctxt
)
4380 : gimple_opt_pass (pass_data_cselim
, ctxt
)
4383 /* opt_pass methods: */
4384 bool gate (function
*) final override
{ return flag_tree_cselim
; }
4385 unsigned int execute (function
*) final override
;
4387 }; // class pass_cselim
4392 make_pass_cselim (gcc::context
*ctxt
)
4394 return new pass_cselim (ctxt
);
4398 pass_cselim::execute (function
*)
4401 basic_block
*bb_order
;
4403 bool cfgchanged
= false;
4404 hash_set
<tree
> *nontrap
= 0;
4407 /* ??? We are not interested in loop related info, but the following
4408 will create it, ICEing as we didn't init loops with pre-headers.
4409 An interfacing issue of find_data_references_in_bb. */
4410 loop_optimizer_init (LOOPS_NORMAL
);
4413 calculate_dominance_info (CDI_DOMINATORS
);
4415 /* Calculate the set of non-trapping memory accesses. */
4416 nontrap
= get_non_trapping ();
4418 /* Search every basic block for COND_EXPR we may be able to optimize.
4420 We walk the blocks in order that guarantees that a block with
4421 a single predecessor is processed before the predecessor.
4422 This ensures that we collapse inner ifs before visiting the
4423 outer ones, and also that we do not try to visit a removed
4425 bb_order
= single_pred_before_succ_order ();
4426 n
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
;
4428 for (i
= 0; i
< n
; i
++)
4430 basic_block bb1
, bb2
;
4432 bool diamond_p
= false;
4436 /* Check to see if the last statement is a GIMPLE_COND. */
4437 gcond
*cond_stmt
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (bb
));
4441 e1
= EDGE_SUCC (bb
, 0);
4443 e2
= EDGE_SUCC (bb
, 1);
4446 /* We cannot do the optimization on abnormal edges. */
4447 if ((e1
->flags
& EDGE_ABNORMAL
) != 0
4448 || (e2
->flags
& EDGE_ABNORMAL
) != 0)
4451 /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
4452 if (EDGE_COUNT (bb1
->succs
) == 0
4453 || EDGE_COUNT (bb2
->succs
) == 0)
4456 /* Find the bb which is the fall through to the other. */
4457 if (EDGE_SUCC (bb1
, 0)->dest
== bb2
)
4459 else if (EDGE_SUCC (bb2
, 0)->dest
== bb1
)
4461 std::swap (bb1
, bb2
);
4464 else if (EDGE_SUCC (bb1
, 0)->dest
== EDGE_SUCC (bb2
, 0)->dest
4465 && single_succ_p (bb2
))
4468 e2
= EDGE_SUCC (bb2
, 0);
4469 /* Make sure bb2 is just a fall through. */
4470 if ((e2
->flags
& EDGE_FALLTHRU
) == 0)
4476 e1
= EDGE_SUCC (bb1
, 0);
4478 /* Make sure that bb1 is just a fall through. */
4479 if (!single_succ_p (bb1
)
4480 || (e1
->flags
& EDGE_FALLTHRU
) == 0)
4485 basic_block bb3
= e1
->dest
;
4487 /* Only handle sinking of store from 2 bbs only,
4488 The middle bbs don't need to come from the
4489 if always since we are sinking rather than
4491 if (EDGE_COUNT (bb3
->preds
) != 2)
4493 if (cond_if_else_store_replacement (bb1
, bb2
, bb3
))
4498 /* Also make sure that bb1 only have one predecessor and that it
4500 if (!single_pred_p (bb1
)
4501 || single_pred (bb1
) != bb
)
4504 /* bb1 is the middle block, bb2 the join block, bb the split block,
4505 e1 the fallthrough edge from bb1 to bb2. We can't do the
4506 optimization if the join block has more than two predecessors. */
4507 if (EDGE_COUNT (bb2
->preds
) > 2)
4509 if (cond_store_replacement (bb1
, bb2
, e1
, e2
, nontrap
))
4516 /* If the CFG has changed, we should cleanup the CFG. */
4519 /* In cond-store replacement we have added some loads on edges
4520 and new VOPS (as we moved the store, and created a load). */
4521 gsi_commit_edge_inserts ();
4522 todo
= TODO_cleanup_cfg
| TODO_update_ssa_only_virtuals
;
4525 loop_optimizer_finalize ();