1 /* Optimization of PHI nodes by converting them into straightline code.
2 Copyright (C) 2004-2023 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 if (gimple_seq_singleton_p (seq
))
66 return as_a
<gphi
*> (gsi_stmt (gsi_start (seq
)));
67 for (i
= gsi_start (seq
); !gsi_end_p (i
); gsi_next (&i
))
69 gphi
*p
= as_a
<gphi
*> (gsi_stmt (i
));
70 /* If the PHI arguments are equal then we can skip this PHI. */
71 if (operand_equal_for_phi_arg_p (gimple_phi_arg_def (p
, e0
->dest_idx
),
72 gimple_phi_arg_def (p
, e1
->dest_idx
)))
75 /* If we already have a PHI that has the two edge arguments are
76 different, then return it is not a singleton for these PHIs. */
85 /* Replace PHI node element whose edge is E in block BB with variable NEW.
86 Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
87 is known to have two edges, one of which must reach BB). */
90 replace_phi_edge_with_variable (basic_block cond_block
,
91 edge e
, gphi
*phi
, tree new_tree
,
92 bitmap dce_ssa_names
= nullptr)
94 basic_block bb
= gimple_bb (phi
);
95 gimple_stmt_iterator gsi
;
96 tree phi_result
= PHI_RESULT (phi
);
97 bool deleteboth
= false;
99 /* Duplicate range info if they are the only things setting the target PHI.
100 This is needed as later on, the new_tree will be replacing
101 The assignement of the PHI.
112 And _4 gets propagated into the use of a_3 and losing the range info.
113 This can't be done for more than 2 incoming edges as the propagation
115 The new_tree needs to be defined in the same basic block as the conditional. */
116 if (TREE_CODE (new_tree
) == SSA_NAME
117 && EDGE_COUNT (gimple_bb (phi
)->preds
) == 2
118 && INTEGRAL_TYPE_P (TREE_TYPE (phi_result
))
119 && !SSA_NAME_RANGE_INFO (new_tree
)
120 && SSA_NAME_RANGE_INFO (phi_result
)
121 && gimple_bb (SSA_NAME_DEF_STMT (new_tree
)) == cond_block
122 && dbg_cnt (phiopt_edge_range
))
123 duplicate_ssa_name_range_info (new_tree
, phi_result
);
125 /* Change the PHI argument to new. */
126 SET_USE (PHI_ARG_DEF_PTR (phi
, e
->dest_idx
), new_tree
);
128 /* Remove the empty basic block. */
129 edge edge_to_remove
= NULL
, keep_edge
= NULL
;
130 if (EDGE_SUCC (cond_block
, 0)->dest
== bb
)
132 edge_to_remove
= EDGE_SUCC (cond_block
, 1);
133 keep_edge
= EDGE_SUCC (cond_block
, 0);
135 else if (EDGE_SUCC (cond_block
, 1)->dest
== bb
)
137 edge_to_remove
= EDGE_SUCC (cond_block
, 0);
138 keep_edge
= EDGE_SUCC (cond_block
, 1);
140 else if ((keep_edge
= find_edge (cond_block
, e
->src
)))
142 basic_block bb1
= EDGE_SUCC (cond_block
, 0)->dest
;
143 basic_block bb2
= EDGE_SUCC (cond_block
, 1)->dest
;
144 if (single_pred_p (bb1
) && single_pred_p (bb2
)
145 && single_succ_p (bb1
) && single_succ_p (bb2
)
146 && empty_block_p (bb1
) && empty_block_p (bb2
))
152 if (edge_to_remove
&& EDGE_COUNT (edge_to_remove
->dest
->preds
) == 1)
154 e
->flags
|= EDGE_FALLTHRU
;
155 e
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
156 e
->probability
= profile_probability::always ();
157 delete_basic_block (edge_to_remove
->dest
);
159 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
160 gsi
= gsi_last_bb (cond_block
);
161 gsi_remove (&gsi
, true);
165 basic_block bb1
= EDGE_SUCC (cond_block
, 0)->dest
;
166 basic_block bb2
= EDGE_SUCC (cond_block
, 1)->dest
;
168 edge newedge
= redirect_edge_and_branch (keep_edge
, bb
);
170 /* The new edge should be the same. */
171 gcc_assert (newedge
== keep_edge
);
173 keep_edge
->flags
|= EDGE_FALLTHRU
;
174 keep_edge
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
175 keep_edge
->probability
= profile_probability::always ();
177 /* Copy the edge's phi entry from the old one. */
178 copy_phi_arg_into_existing_phi (e
, keep_edge
);
180 /* Delete the old 2 empty basic blocks */
181 delete_basic_block (bb1
);
182 delete_basic_block (bb2
);
184 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
185 gsi
= gsi_last_bb (cond_block
);
186 gsi_remove (&gsi
, true);
190 /* If there are other edges into the middle block make
191 CFG cleanup deal with the edge removal to avoid
192 updating dominators here in a non-trivial way. */
193 gcond
*cond
= as_a
<gcond
*> (*gsi_last_bb (cond_block
));
194 if (keep_edge
->flags
& EDGE_FALSE_VALUE
)
195 gimple_cond_make_false (cond
);
196 else if (keep_edge
->flags
& EDGE_TRUE_VALUE
)
197 gimple_cond_make_true (cond
);
201 simple_dce_from_worklist (dce_ssa_names
);
203 statistics_counter_event (cfun
, "Replace PHI with variable", 1);
205 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
207 "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
212 /* PR66726: Factor operations out of COND_EXPR. If the arguments of the PHI
213 stmt are CONVERT_STMT, factor out the conversion and perform the conversion
214 to the result of PHI stmt. COND_STMT is the controlling predicate.
215 Return the newly-created PHI, if any. */
218 factor_out_conditional_operation (edge e0
, edge e1
, gphi
*phi
,
219 tree arg0
, tree arg1
, gimple
*cond_stmt
)
221 gimple
*arg0_def_stmt
= NULL
, *arg1_def_stmt
= NULL
, *new_stmt
;
222 tree new_arg0
= NULL_TREE
, new_arg1
= NULL_TREE
;
225 gimple_stmt_iterator gsi
, gsi_for_def
;
226 location_t locus
= gimple_location (phi
);
227 enum tree_code op_code
;
229 /* Handle only PHI statements with two arguments. TODO: If all
230 other arguments to PHI are INTEGER_CST or if their defining
231 statement have the same unary operation, we can handle more
232 than two arguments too. */
233 if (gimple_phi_num_args (phi
) != 2)
236 /* First canonicalize to simplify tests. */
237 if (TREE_CODE (arg0
) != SSA_NAME
)
239 std::swap (arg0
, arg1
);
243 if (TREE_CODE (arg0
) != SSA_NAME
244 || (TREE_CODE (arg1
) != SSA_NAME
245 && TREE_CODE (arg1
) != INTEGER_CST
))
248 /* Check if arg0 is an SSA_NAME and the stmt which defines arg0 is
249 an unary operation. */
250 arg0_def_stmt
= SSA_NAME_DEF_STMT (arg0
);
251 if (!is_gimple_assign (arg0_def_stmt
)
252 || (gimple_assign_rhs_class (arg0_def_stmt
) != GIMPLE_UNARY_RHS
253 && gimple_assign_rhs_code (arg0_def_stmt
) != VIEW_CONVERT_EXPR
))
256 /* Use the RHS as new_arg0. */
257 op_code
= gimple_assign_rhs_code (arg0_def_stmt
);
258 new_arg0
= gimple_assign_rhs1 (arg0_def_stmt
);
259 if (op_code
== VIEW_CONVERT_EXPR
)
261 new_arg0
= TREE_OPERAND (new_arg0
, 0);
262 if (!is_gimple_reg_type (TREE_TYPE (new_arg0
)))
265 if (TREE_CODE (new_arg0
) == SSA_NAME
266 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_arg0
))
269 if (TREE_CODE (arg1
) == SSA_NAME
)
271 /* Check if arg1 is an SSA_NAME and the stmt which defines arg1
272 is an unary operation. */
273 arg1_def_stmt
= SSA_NAME_DEF_STMT (arg1
);
274 if (!is_gimple_assign (arg1_def_stmt
)
275 || gimple_assign_rhs_code (arg1_def_stmt
) != op_code
)
278 /* Either arg1_def_stmt or arg0_def_stmt should be conditional. */
279 if (dominated_by_p (CDI_DOMINATORS
, gimple_bb (phi
), gimple_bb (arg0_def_stmt
))
280 && dominated_by_p (CDI_DOMINATORS
,
281 gimple_bb (phi
), gimple_bb (arg1_def_stmt
)))
284 /* Use the RHS as new_arg1. */
285 new_arg1
= gimple_assign_rhs1 (arg1_def_stmt
);
286 if (op_code
== VIEW_CONVERT_EXPR
)
287 new_arg1
= TREE_OPERAND (new_arg1
, 0);
288 if (TREE_CODE (new_arg1
) == SSA_NAME
289 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_arg1
))
294 /* TODO: handle more than just casts here. */
295 if (!gimple_assign_cast_p (arg0_def_stmt
))
298 /* arg0_def_stmt should be conditional. */
299 if (dominated_by_p (CDI_DOMINATORS
, gimple_bb (phi
), gimple_bb (arg0_def_stmt
)))
301 /* If arg1 is an INTEGER_CST, fold it to new type. */
302 if (INTEGRAL_TYPE_P (TREE_TYPE (new_arg0
))
303 && int_fits_type_p (arg1
, TREE_TYPE (new_arg0
)))
305 if (gimple_assign_cast_p (arg0_def_stmt
))
307 /* For the INTEGER_CST case, we are just moving the
308 conversion from one place to another, which can often
309 hurt as the conversion moves further away from the
310 statement that computes the value. So, perform this
311 only if new_arg0 is an operand of COND_STMT, or
312 if arg0_def_stmt is the only non-debug stmt in
313 its basic block, because then it is possible this
314 could enable further optimizations (minmax replacement
315 etc.). See PR71016. */
316 if (new_arg0
!= gimple_cond_lhs (cond_stmt
)
317 && new_arg0
!= gimple_cond_rhs (cond_stmt
)
318 && gimple_bb (arg0_def_stmt
) == e0
->src
)
320 gsi
= gsi_for_stmt (arg0_def_stmt
);
321 gsi_prev_nondebug (&gsi
);
322 if (!gsi_end_p (gsi
))
325 = dyn_cast
<gassign
*> (gsi_stmt (gsi
)))
327 tree lhs
= gimple_assign_lhs (assign
);
328 enum tree_code ass_code
329 = gimple_assign_rhs_code (assign
);
330 if (ass_code
!= MAX_EXPR
&& ass_code
!= MIN_EXPR
)
332 if (lhs
!= gimple_assign_rhs1 (arg0_def_stmt
))
334 gsi_prev_nondebug (&gsi
);
335 if (!gsi_end_p (gsi
))
341 gsi
= gsi_for_stmt (arg0_def_stmt
);
342 gsi_next_nondebug (&gsi
);
343 if (!gsi_end_p (gsi
))
346 new_arg1
= fold_convert (TREE_TYPE (new_arg0
), arg1
);
355 /* If arg0/arg1 have > 1 use, then this transformation actually increases
356 the number of expressions evaluated at runtime. */
357 if (!has_single_use (arg0
)
358 || (arg1_def_stmt
&& !has_single_use (arg1
)))
361 /* If types of new_arg0 and new_arg1 are different bailout. */
362 if (!types_compatible_p (TREE_TYPE (new_arg0
), TREE_TYPE (new_arg1
)))
365 /* Create a new PHI stmt. */
366 result
= PHI_RESULT (phi
);
367 temp
= make_ssa_name (TREE_TYPE (new_arg0
), NULL
);
368 newphi
= create_phi_node (temp
, gimple_bb (phi
));
370 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
372 fprintf (dump_file
, "PHI ");
373 print_generic_expr (dump_file
, gimple_phi_result (phi
));
375 " changed to factor operation out from COND_EXPR.\n");
376 fprintf (dump_file
, "New stmt with OPERATION that defines ");
377 print_generic_expr (dump_file
, result
);
378 fprintf (dump_file
, ".\n");
381 /* Remove the old operation(s) that has single use. */
382 gsi_for_def
= gsi_for_stmt (arg0_def_stmt
);
383 gsi_remove (&gsi_for_def
, true);
384 release_defs (arg0_def_stmt
);
388 gsi_for_def
= gsi_for_stmt (arg1_def_stmt
);
389 gsi_remove (&gsi_for_def
, true);
390 release_defs (arg1_def_stmt
);
393 add_phi_arg (newphi
, new_arg0
, e0
, locus
);
394 add_phi_arg (newphi
, new_arg1
, e1
, locus
);
396 /* Create the operation stmt and insert it. */
397 if (op_code
== VIEW_CONVERT_EXPR
)
399 temp
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (result
), temp
);
400 new_stmt
= gimple_build_assign (result
, temp
);
403 new_stmt
= gimple_build_assign (result
, op_code
, temp
);
404 gsi
= gsi_after_labels (gimple_bb (phi
));
405 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
407 /* Remove the original PHI stmt. */
408 gsi
= gsi_for_stmt (phi
);
409 gsi_remove (&gsi
, true);
411 statistics_counter_event (cfun
, "factored out operation", 1);
417 /* Return TRUE if SEQ/OP pair should be allowed during early phiopt.
418 Currently this is to allow MIN/MAX and ABS/NEGATE and constants. */
420 phiopt_early_allow (gimple_seq
&seq
, gimple_match_op
&op
)
422 /* Don't allow functions. */
423 if (!op
.code
.is_tree_code ())
425 tree_code code
= (tree_code
)op
.code
;
427 /* For non-empty sequence, only allow one statement
428 except for MIN/MAX, allow max 2 statements,
429 each with MIN/MAX. */
430 if (!gimple_seq_empty_p (seq
))
432 if (code
== MIN_EXPR
|| code
== MAX_EXPR
)
434 if (!gimple_seq_singleton_p (seq
))
437 gimple
*stmt
= gimple_seq_first_stmt (seq
);
438 /* Only allow assignments. */
439 if (!is_gimple_assign (stmt
))
441 code
= gimple_assign_rhs_code (stmt
);
442 return code
== MIN_EXPR
|| code
== MAX_EXPR
;
444 /* Check to make sure op was already a SSA_NAME. */
445 if (code
!= SSA_NAME
)
447 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 if (gimple_assign_lhs (stmt
) != op
.ops
[0])
455 code
= gimple_assign_rhs_code (stmt
);
477 /* gimple_simplify_phiopt is like gimple_simplify but designed for PHIOPT.
478 Return NULL if nothing can be simplified or the resulting simplified value
479 with parts pushed if EARLY_P was true. Also rejects non allowed tree code
481 Takes the comparison from COMP_STMT and two args, ARG0 and ARG1 and tries
482 to simplify CMP ? ARG0 : ARG1.
483 Also try to simplify (!CMP) ? ARG1 : ARG0 if the non-inverse failed. */
485 gimple_simplify_phiopt (bool early_p
, tree type
, gimple
*comp_stmt
,
486 tree arg0
, tree arg1
,
490 gimple_seq seq1
= NULL
;
491 enum tree_code comp_code
= gimple_cond_code (comp_stmt
);
492 location_t loc
= gimple_location (comp_stmt
);
493 tree cmp0
= gimple_cond_lhs (comp_stmt
);
494 tree cmp1
= gimple_cond_rhs (comp_stmt
);
495 /* To handle special cases like floating point comparison, it is easier and
496 less error-prone to build a tree and gimplify it on the fly though it is
498 Don't use fold_build2 here as that might create (bool)a instead of just
500 tree cond
= build2_loc (loc
, comp_code
, boolean_type_node
,
503 if (dump_file
&& (dump_flags
& TDF_FOLDING
))
505 fprintf (dump_file
, "\nphiopt match-simplify trying:\n\t");
506 print_generic_expr (dump_file
, cond
);
507 fprintf (dump_file
, " ? ");
508 print_generic_expr (dump_file
, arg0
);
509 fprintf (dump_file
, " : ");
510 print_generic_expr (dump_file
, arg1
);
511 fprintf (dump_file
, "\n");
514 gimple_match_op
op (gimple_match_cond::UNCOND
,
515 COND_EXPR
, type
, cond
, arg0
, arg1
);
517 if (op
.resimplify (&seq1
, follow_all_ssa_edges
))
519 /* Early we want only to allow some generated tree codes. */
521 || phiopt_early_allow (seq1
, op
))
523 result
= maybe_push_res_to_seq (&op
, &seq1
);
526 if (loc
!= UNKNOWN_LOCATION
)
527 annotate_all_with_location (seq1
, loc
);
528 gimple_seq_add_seq_without_update (seq
, seq1
);
533 gimple_seq_discard (seq1
);
536 /* Try the inverted comparison, that is !COMP ? ARG1 : ARG0. */
537 comp_code
= invert_tree_comparison (comp_code
, HONOR_NANS (cmp0
));
539 if (comp_code
== ERROR_MARK
)
542 cond
= build2_loc (loc
,
543 comp_code
, boolean_type_node
,
546 if (dump_file
&& (dump_flags
& TDF_FOLDING
))
548 fprintf (dump_file
, "\nphiopt match-simplify trying:\n\t");
549 print_generic_expr (dump_file
, cond
);
550 fprintf (dump_file
, " ? ");
551 print_generic_expr (dump_file
, arg1
);
552 fprintf (dump_file
, " : ");
553 print_generic_expr (dump_file
, arg0
);
554 fprintf (dump_file
, "\n");
557 gimple_match_op
op1 (gimple_match_cond::UNCOND
,
558 COND_EXPR
, type
, cond
, arg1
, arg0
);
560 if (op1
.resimplify (&seq1
, follow_all_ssa_edges
))
562 /* Early we want only to allow some generated tree codes. */
564 || phiopt_early_allow (seq1
, op1
))
566 result
= maybe_push_res_to_seq (&op1
, &seq1
);
569 if (loc
!= UNKNOWN_LOCATION
)
570 annotate_all_with_location (seq1
, loc
);
571 gimple_seq_add_seq_without_update (seq
, seq1
);
576 gimple_seq_discard (seq1
);
581 /* empty_bb_or_one_feeding_into_p returns true if bb was empty basic block
582 or it has one cheap preparation statement that feeds into the PHI
583 statement and it sets STMT to that statement. */
585 empty_bb_or_one_feeding_into_p (basic_block bb
,
590 gimple
*stmt_to_move
= nullptr;
593 if (empty_block_p (bb
))
596 if (!single_pred_p (bb
))
599 /* The middle bb cannot have phi nodes as we don't
600 move those assignments yet. */
601 if (!gimple_seq_empty_p (phi_nodes (bb
)))
604 gimple_stmt_iterator gsi
;
606 gsi
= gsi_start_nondebug_after_labels_bb (bb
);
607 while (!gsi_end_p (gsi
))
609 gimple
*s
= gsi_stmt (gsi
);
610 gsi_next_nondebug (&gsi
);
611 /* Skip over Predict and nop statements. */
612 if (gimple_code (s
) == GIMPLE_PREDICT
613 || gimple_code (s
) == GIMPLE_NOP
)
615 /* If there is more one statement return false. */
621 /* The only statement here was a Predict or a nop statement
626 if (gimple_vuse (stmt_to_move
))
629 if (gimple_could_trap_p (stmt_to_move
)
630 || gimple_has_side_effects (stmt_to_move
))
633 if (gimple_uses_undefined_value_p (stmt_to_move
))
636 /* Allow assignments but allow some builtin/internal calls.
637 As const calls don't match any of the above, yet they could
638 still have some side-effects - they could contain
639 gimple_could_trap_p statements, like floating point
640 exceptions or integer division by zero. See PR70586.
641 FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
643 Allow some known builtin/internal calls that are known not to
644 trap: logical functions (e.g. bswap and bit counting). */
645 if (!is_gimple_assign (stmt_to_move
))
647 if (!is_gimple_call (stmt_to_move
))
649 combined_fn cfn
= gimple_call_combined_fn (stmt_to_move
);
654 case CFN_BUILT_IN_BSWAP16
:
655 case CFN_BUILT_IN_BSWAP32
:
656 case CFN_BUILT_IN_BSWAP64
:
657 case CFN_BUILT_IN_BSWAP128
:
663 case CFN_BUILT_IN_CLRSB
:
664 case CFN_BUILT_IN_CLRSBL
:
665 case CFN_BUILT_IN_CLRSBLL
:
666 lhs
= gimple_call_lhs (stmt_to_move
);
671 lhs
= gimple_assign_lhs (stmt_to_move
);
676 /* Allow only a statement which feeds into the other stmt. */
677 if (!lhs
|| TREE_CODE (lhs
) != SSA_NAME
678 || !single_imm_use (lhs
, &use_p
, &use_stmt
)
686 /* Move STMT to before GSI and insert its defining
687 name into INSERTED_EXPRS bitmap. */
689 move_stmt (gimple
*stmt
, gimple_stmt_iterator
*gsi
, auto_bitmap
&inserted_exprs
)
693 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
695 fprintf (dump_file
, "statement un-sinked:\n");
696 print_gimple_stmt (dump_file
, stmt
, 0,
697 TDF_VOPS
|TDF_MEMSYMS
);
700 tree name
= gimple_get_lhs (stmt
);
701 // Mark the name to be renamed if there is one.
702 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (name
));
703 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt
);
704 gsi_move_before (&gsi1
, gsi
);
705 reset_flow_sensitive_info (name
);
708 /* The function match_simplify_replacement does the main work of doing the
709 replacement using match and simplify. Return true if the replacement is done.
710 Otherwise return false.
711 BB is the basic block where the replacement is going to be done on. ARG0
712 is argument 0 from PHI. Likewise for ARG1. */
715 match_simplify_replacement (basic_block cond_bb
, basic_block middle_bb
,
716 basic_block middle_bb_alt
,
717 edge e0
, edge e1
, gphi
*phi
,
718 tree arg0
, tree arg1
, bool early_p
,
722 gimple_stmt_iterator gsi
;
723 edge true_edge
, false_edge
;
724 gimple_seq seq
= NULL
;
726 gimple
*stmt_to_move
= NULL
;
727 gimple
*stmt_to_move_alt
= NULL
;
728 auto_bitmap inserted_exprs
;
729 tree arg_true
, arg_false
;
731 /* Special case A ? B : B as this will always simplify to B. */
732 if (operand_equal_for_phi_arg_p (arg0
, arg1
))
735 /* If the basic block only has a cheap preparation statement,
736 allow it and move it once the transformation is done. */
737 if (!empty_bb_or_one_feeding_into_p (middle_bb
, phi
, stmt_to_move
))
741 && middle_bb
!= middle_bb_alt
742 && !empty_bb_or_one_feeding_into_p (middle_bb_alt
, phi
,
746 /* At this point we know we have a GIMPLE_COND with two successors.
747 One successor is BB, the other successor is an empty block which
748 falls through into BB.
750 There is a single PHI node at the join point (BB).
752 So, given the condition COND, and the two PHI arguments, match and simplify
753 can happen on (COND) ? arg0 : arg1. */
755 stmt
= last_nondebug_stmt (cond_bb
);
757 /* We need to know which is the true edge and which is the false
758 edge so that we know when to invert the condition below. */
759 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
761 /* Forward the edges over the middle basic block. */
762 if (true_edge
->dest
== middle_bb
)
763 true_edge
= EDGE_SUCC (true_edge
->dest
, 0);
764 if (false_edge
->dest
== middle_bb
)
765 false_edge
= EDGE_SUCC (false_edge
->dest
, 0);
767 /* When THREEWAY_P then e1 will point to the edge of the final transition
768 from middle-bb to end. */
772 gcc_assert (false_edge
== e1
);
778 gcc_assert (false_edge
== e0
);
780 gcc_assert (true_edge
== e1
);
785 tree type
= TREE_TYPE (gimple_phi_result (phi
));
786 result
= gimple_simplify_phiopt (early_p
, type
, stmt
,
792 gsi
= gsi_last_bb (cond_bb
);
793 /* Insert the sequence generated from gimple_simplify_phiopt. */
796 // Mark the lhs of the new statements maybe for dce
797 gimple_stmt_iterator gsi1
= gsi_start (seq
);
798 for (; !gsi_end_p (gsi1
); gsi_next (&gsi1
))
800 gimple
*stmt
= gsi_stmt (gsi1
);
801 tree name
= gimple_get_lhs (stmt
);
802 if (name
&& TREE_CODE (name
) == SSA_NAME
)
803 bitmap_set_bit (inserted_exprs
, SSA_NAME_VERSION (name
));
805 if (dump_file
&& (dump_flags
& TDF_FOLDING
))
807 fprintf (dump_file
, "Folded into the sequence:\n");
808 print_gimple_seq (dump_file
, seq
, 0, TDF_VOPS
|TDF_MEMSYMS
);
810 gsi_insert_seq_before (&gsi
, seq
, GSI_CONTINUE_LINKING
);
813 /* If there was a statement to move, move it to right before
814 the original conditional. */
815 move_stmt (stmt_to_move
, &gsi
, inserted_exprs
);
816 move_stmt (stmt_to_move_alt
, &gsi
, inserted_exprs
);
818 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, result
, inserted_exprs
);
820 /* Add Statistic here even though replace_phi_edge_with_variable already
821 does it as we want to be able to count when match-simplify happens vs
823 statistics_counter_event (cfun
, "match-simplify PHI replacement", 1);
825 /* Note that we optimized this PHI. */
829 /* Update *ARG which is defined in STMT so that it contains the
830 computed value if that seems profitable. Return true if the
831 statement is made dead by that rewriting. */
834 jump_function_from_stmt (tree
*arg
, gimple
*stmt
)
836 enum tree_code code
= gimple_assign_rhs_code (stmt
);
837 if (code
== ADDR_EXPR
)
839 /* For arg = &p->i transform it to p, if possible. */
840 tree rhs1
= gimple_assign_rhs1 (stmt
);
842 tree tem
= get_addr_base_and_unit_offset (TREE_OPERAND (rhs1
, 0),
845 && TREE_CODE (tem
) == MEM_REF
846 && known_eq (mem_ref_offset (tem
) + offset
, 0))
848 *arg
= TREE_OPERAND (tem
, 0);
852 /* TODO: Much like IPA-CP jump-functions we want to handle constant
853 additions symbolically here, and we'd need to update the comparison
854 code that compares the arg + cst tuples in our caller. For now the
855 code above exactly handles the VEC_BASE pattern from vec.h. */
859 /* RHS is a source argument in a BIT_AND_EXPR which feeds a conditional
860 of the form SSA_NAME NE 0.
862 If RHS is fed by a simple EQ_EXPR comparison of two values, see if
863 the two input values of the EQ_EXPR match arg0 and arg1.
865 If so update *code and return TRUE. Otherwise return FALSE. */
868 rhs_is_fed_for_value_replacement (const_tree arg0
, const_tree arg1
,
869 enum tree_code
*code
, const_tree rhs
)
871 /* Obviously if RHS is not an SSA_NAME, we can't look at the defining
873 if (TREE_CODE (rhs
) == SSA_NAME
)
875 gimple
*def1
= SSA_NAME_DEF_STMT (rhs
);
877 /* Verify the defining statement has an EQ_EXPR on the RHS. */
878 if (is_gimple_assign (def1
) && gimple_assign_rhs_code (def1
) == EQ_EXPR
)
880 /* Finally verify the source operands of the EQ_EXPR are equal
882 tree op0
= gimple_assign_rhs1 (def1
);
883 tree op1
= gimple_assign_rhs2 (def1
);
884 if ((operand_equal_for_phi_arg_p (arg0
, op0
)
885 && operand_equal_for_phi_arg_p (arg1
, op1
))
886 || (operand_equal_for_phi_arg_p (arg0
, op1
)
887 && operand_equal_for_phi_arg_p (arg1
, op0
)))
889 /* We will perform the optimization. */
890 *code
= gimple_assign_rhs_code (def1
);
898 /* Return TRUE if arg0/arg1 are equal to the rhs/lhs or lhs/rhs of COND.
900 Also return TRUE if arg0/arg1 are equal to the source arguments of a
901 an EQ comparison feeding a BIT_AND_EXPR which feeds COND.
903 Return FALSE otherwise. */
906 operand_equal_for_value_replacement (const_tree arg0
, const_tree arg1
,
907 enum tree_code
*code
, gimple
*cond
)
910 tree lhs
= gimple_cond_lhs (cond
);
911 tree rhs
= gimple_cond_rhs (cond
);
913 if ((operand_equal_for_phi_arg_p (arg0
, lhs
)
914 && operand_equal_for_phi_arg_p (arg1
, rhs
))
915 || (operand_equal_for_phi_arg_p (arg1
, lhs
)
916 && operand_equal_for_phi_arg_p (arg0
, rhs
)))
919 /* Now handle more complex case where we have an EQ comparison
920 which feeds a BIT_AND_EXPR which feeds COND.
922 First verify that COND is of the form SSA_NAME NE 0. */
923 if (*code
!= NE_EXPR
|| !integer_zerop (rhs
)
924 || TREE_CODE (lhs
) != SSA_NAME
)
927 /* Now ensure that SSA_NAME is set by a BIT_AND_EXPR. */
928 def
= SSA_NAME_DEF_STMT (lhs
);
929 if (!is_gimple_assign (def
) || gimple_assign_rhs_code (def
) != BIT_AND_EXPR
)
932 /* Now verify arg0/arg1 correspond to the source arguments of an
933 EQ comparison feeding the BIT_AND_EXPR. */
935 tree tmp
= gimple_assign_rhs1 (def
);
936 if (rhs_is_fed_for_value_replacement (arg0
, arg1
, code
, tmp
))
939 tmp
= gimple_assign_rhs2 (def
);
940 if (rhs_is_fed_for_value_replacement (arg0
, arg1
, code
, tmp
))
946 /* Returns true if ARG is a neutral element for operation CODE
947 on the RIGHT side. */
950 neutral_element_p (tree_code code
, tree arg
, bool right
)
957 return integer_zerop (arg
);
964 case POINTER_PLUS_EXPR
:
965 return right
&& integer_zerop (arg
);
968 return integer_onep (arg
);
975 return right
&& integer_onep (arg
);
978 return integer_all_onesp (arg
);
985 /* Returns true if ARG is an absorbing element for operation CODE. */
988 absorbing_element_p (tree_code code
, tree arg
, bool right
, tree rval
)
993 return integer_all_onesp (arg
);
997 return integer_zerop (arg
);
1003 return !right
&& integer_zerop (arg
);
1005 case TRUNC_DIV_EXPR
:
1007 case FLOOR_DIV_EXPR
:
1008 case ROUND_DIV_EXPR
:
1009 case EXACT_DIV_EXPR
:
1010 case TRUNC_MOD_EXPR
:
1012 case FLOOR_MOD_EXPR
:
1013 case ROUND_MOD_EXPR
:
1015 && integer_zerop (arg
)
1016 && tree_single_nonzero_warnv_p (rval
, NULL
));
1023 /* The function value_replacement does the main work of doing the value
1024 replacement. Return non-zero if the replacement is done. Otherwise return
1025 0. If we remove the middle basic block, return 2.
1026 BB is the basic block where the replacement is going to be done on. ARG0
1027 is argument 0 from the PHI. Likewise for ARG1. */
1030 value_replacement (basic_block cond_bb
, basic_block middle_bb
,
1031 edge e0
, edge e1
, gphi
*phi
, tree arg0
, tree arg1
)
1033 gimple_stmt_iterator gsi
;
1034 edge true_edge
, false_edge
;
1035 enum tree_code code
;
1036 bool empty_or_with_defined_p
= true;
1038 /* If the type says honor signed zeros we cannot do this
1040 if (HONOR_SIGNED_ZEROS (arg1
))
1043 /* If there is a statement in MIDDLE_BB that defines one of the PHI
1044 arguments, then adjust arg0 or arg1. */
1045 gsi
= gsi_start_nondebug_after_labels_bb (middle_bb
);
1046 while (!gsi_end_p (gsi
))
1048 gimple
*stmt
= gsi_stmt (gsi
);
1050 gsi_next_nondebug (&gsi
);
1051 if (!is_gimple_assign (stmt
))
1053 if (gimple_code (stmt
) != GIMPLE_PREDICT
1054 && gimple_code (stmt
) != GIMPLE_NOP
)
1055 empty_or_with_defined_p
= false;
1058 /* Now try to adjust arg0 or arg1 according to the computation
1059 in the statement. */
1060 lhs
= gimple_assign_lhs (stmt
);
1062 && jump_function_from_stmt (&arg0
, stmt
))
1064 && jump_function_from_stmt (&arg1
, stmt
)))
1065 empty_or_with_defined_p
= false;
1068 gcond
*cond
= as_a
<gcond
*> (*gsi_last_bb (cond_bb
));
1069 code
= gimple_cond_code (cond
);
1071 /* This transformation is only valid for equality comparisons. */
1072 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1075 /* We need to know which is the true edge and which is the false
1076 edge so that we know if have abs or negative abs. */
1077 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
1079 /* At this point we know we have a COND_EXPR with two successors.
1080 One successor is BB, the other successor is an empty block which
1081 falls through into BB.
1083 The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
1085 There is a single PHI node at the join point (BB) with two arguments.
1087 We now need to verify that the two arguments in the PHI node match
1088 the two arguments to the equality comparison. */
1090 bool equal_p
= operand_equal_for_value_replacement (arg0
, arg1
, &code
, cond
);
1091 bool maybe_equal_p
= false;
1093 && empty_or_with_defined_p
1094 && TREE_CODE (gimple_cond_rhs (cond
)) == INTEGER_CST
1095 && (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond
), arg0
)
1096 ? TREE_CODE (arg1
) == INTEGER_CST
1097 : (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond
), arg1
)
1098 && TREE_CODE (arg0
) == INTEGER_CST
)))
1099 maybe_equal_p
= true;
1100 if (equal_p
|| maybe_equal_p
)
1105 /* For NE_EXPR, we want to build an assignment result = arg where
1106 arg is the PHI argument associated with the true edge. For
1107 EQ_EXPR we want the PHI argument associated with the false edge. */
1108 e
= (code
== NE_EXPR
? true_edge
: false_edge
);
1110 /* Unfortunately, E may not reach BB (it may instead have gone to
1111 OTHER_BLOCK). If that is the case, then we want the single outgoing
1112 edge from OTHER_BLOCK which reaches BB and represents the desired
1113 path from COND_BLOCK. */
1114 if (e
->dest
== middle_bb
)
1115 e
= single_succ_edge (e
->dest
);
1117 /* Now we know the incoming edge to BB that has the argument for the
1118 RHS of our new assignment statement. */
1124 /* If the middle basic block was empty or is defining the
1125 PHI arguments and this is a single phi where the args are different
1126 for the edges e0 and e1 then we can remove the middle basic block. */
1127 if (empty_or_with_defined_p
1128 && single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi
)),
1131 use_operand_p use_p
;
1134 /* Even if arg0/arg1 isn't equal to second operand of cond, we
1135 can optimize away the bb if we can prove it doesn't care whether
1136 phi result is arg0/arg1 or second operand of cond. Consider:
1137 <bb 2> [local count: 118111600]:
1139 goto <bb 4>; [97.00%]
1141 goto <bb 3>; [3.00%]
1143 <bb 3> [local count: 3540129]:
1145 <bb 4> [local count: 118111600]:
1146 # i_6 = PHI <i_2(D)(3), 6(2)>
1148 Here, carg is 4, oarg is 6, crhs is 0, and because
1149 (4 != 0) == (6 != 0), we don't care if i_6 is 4 or 6, both
1150 have the same outcome. So, can can optimize this to:
1152 If the single imm use of phi result >, >=, < or <=, similarly
1153 we can check if both carg and oarg compare the same against
1154 crhs using ccode. */
1156 && TREE_CODE (arg
) != INTEGER_CST
1157 && single_imm_use (gimple_phi_result (phi
), &use_p
, &use_stmt
))
1159 enum tree_code ccode
= ERROR_MARK
;
1160 tree clhs
= NULL_TREE
, crhs
= NULL_TREE
;
1161 tree carg
= gimple_cond_rhs (cond
);
1162 tree oarg
= e0
== e
? arg1
: arg0
;
1163 if (is_gimple_assign (use_stmt
)
1164 && (TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt
))
1167 ccode
= gimple_assign_rhs_code (use_stmt
);
1168 clhs
= gimple_assign_rhs1 (use_stmt
);
1169 crhs
= gimple_assign_rhs2 (use_stmt
);
1171 else if (gimple_code (use_stmt
) == GIMPLE_COND
)
1173 ccode
= gimple_cond_code (use_stmt
);
1174 clhs
= gimple_cond_lhs (use_stmt
);
1175 crhs
= gimple_cond_rhs (use_stmt
);
1177 if (ccode
!= ERROR_MARK
1178 && clhs
== gimple_phi_result (phi
)
1179 && TREE_CODE (crhs
) == INTEGER_CST
)
1184 if (!tree_int_cst_equal (crhs
, carg
)
1185 && !tree_int_cst_equal (crhs
, oarg
))
1189 if (tree_int_cst_lt (crhs
, carg
)
1190 == tree_int_cst_lt (crhs
, oarg
))
1194 if (tree_int_cst_le (crhs
, carg
)
1195 == tree_int_cst_le (crhs
, oarg
))
1199 if (tree_int_cst_lt (carg
, crhs
)
1200 == tree_int_cst_lt (oarg
, crhs
))
1204 if (tree_int_cst_le (carg
, crhs
)
1205 == tree_int_cst_le (oarg
, crhs
))
1213 tree phires
= gimple_phi_result (phi
);
1214 if (SSA_NAME_RANGE_INFO (phires
))
1216 /* After the optimization PHI result can have value
1217 which it couldn't have previously. */
1219 if (get_global_range_query ()->range_of_expr (r
, phires
,
1222 wide_int warg
= wi::to_wide (carg
);
1223 int_range
<2> tmp (TREE_TYPE (carg
), warg
, warg
);
1225 reset_flow_sensitive_info (phires
);
1226 set_range_info (phires
, r
);
1229 reset_flow_sensitive_info (phires
);
1232 if (equal_p
&& MAY_HAVE_DEBUG_BIND_STMTS
)
1234 imm_use_iterator imm_iter
;
1235 tree phires
= gimple_phi_result (phi
);
1236 tree temp
= NULL_TREE
;
1237 bool reset_p
= false;
1239 /* Add # DEBUG D#1 => arg != carg ? arg : oarg. */
1240 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, phires
)
1242 if (!is_gimple_debug (use_stmt
))
1244 if (temp
== NULL_TREE
)
1246 if (!single_pred_p (middle_bb
)
1247 || EDGE_COUNT (gimple_bb (phi
)->preds
) != 2)
1249 /* But only if middle_bb has a single
1250 predecessor and phi bb has two, otherwise
1251 we could use a SSA_NAME not usable in that
1252 place or wrong-debug. */
1256 gimple_stmt_iterator gsi
1257 = gsi_after_labels (gimple_bb (phi
));
1258 tree type
= TREE_TYPE (phires
);
1259 temp
= build_debug_expr_decl (type
);
1260 tree t
= build2 (NE_EXPR
, boolean_type_node
,
1262 t
= build3 (COND_EXPR
, type
, t
, arg
, oarg
);
1263 gimple
*g
= gimple_build_debug_bind (temp
, t
, phi
);
1264 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
1266 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1267 replace_exp (use_p
, temp
);
1268 update_stmt (use_stmt
);
1271 reset_debug_uses (phi
);
1276 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, arg
);
1277 /* Note that we optimized this PHI. */
1283 if (!single_pred_p (middle_bb
))
1285 statistics_counter_event (cfun
, "Replace PHI with "
1286 "variable/value_replacement", 1);
1288 /* Replace the PHI arguments with arg. */
1289 SET_PHI_ARG_DEF (phi
, e0
->dest_idx
, arg
);
1290 SET_PHI_ARG_DEF (phi
, e1
->dest_idx
, arg
);
1291 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1293 fprintf (dump_file
, "PHI ");
1294 print_generic_expr (dump_file
, gimple_phi_result (phi
));
1295 fprintf (dump_file
, " reduced for COND_EXPR in block %d to ",
1297 print_generic_expr (dump_file
, arg
);
1298 fprintf (dump_file
, ".\n");
1304 if (!single_pred_p (middle_bb
))
1307 /* Now optimize (x != 0) ? x + y : y to just x + y. */
1308 gsi
= gsi_last_nondebug_bb (middle_bb
);
1309 if (gsi_end_p (gsi
))
1312 gimple
*assign
= gsi_stmt (gsi
);
1313 if (!is_gimple_assign (assign
)
1314 || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0
))
1315 && !POINTER_TYPE_P (TREE_TYPE (arg0
))))
1318 if (gimple_assign_rhs_class (assign
) != GIMPLE_BINARY_RHS
)
1320 /* If last stmt of the middle_bb is a conversion, handle it like
1321 a preparation statement through constant evaluation with
1323 enum tree_code sc
= gimple_assign_rhs_code (assign
);
1324 if (CONVERT_EXPR_CODE_P (sc
))
1330 /* Punt if there are (degenerate) PHIs in middle_bb, there should not be. */
1331 if (!gimple_seq_empty_p (phi_nodes (middle_bb
)))
1334 /* Allow up to 2 cheap preparation statements that prepare argument
1342 iftmp.0_6 = x_5(D) r<< _1;
1344 # iftmp.0_2 = PHI <iftmp.0_6(3), x_5(D)(2)>
1355 # _2 = PHI <x_5(D)(2), _6(3)> */
1356 gimple
*prep_stmt
[2] = { NULL
, NULL
};
1358 for (prep_cnt
= 0; ; prep_cnt
++)
1360 if (prep_cnt
|| assign
)
1361 gsi_prev_nondebug (&gsi
);
1362 if (gsi_end_p (gsi
))
1365 gimple
*g
= gsi_stmt (gsi
);
1366 if (gimple_code (g
) == GIMPLE_LABEL
)
1369 if (prep_cnt
== 2 || !is_gimple_assign (g
))
1372 tree lhs
= gimple_assign_lhs (g
);
1373 tree rhs1
= gimple_assign_rhs1 (g
);
1374 use_operand_p use_p
;
1376 if (TREE_CODE (lhs
) != SSA_NAME
1377 || TREE_CODE (rhs1
) != SSA_NAME
1378 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
1379 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
1380 || !single_imm_use (lhs
, &use_p
, &use_stmt
)
1381 || ((prep_cnt
|| assign
)
1382 && use_stmt
!= (prep_cnt
? prep_stmt
[prep_cnt
- 1] : assign
)))
1384 switch (gimple_assign_rhs_code (g
))
1392 if (TREE_CODE (gimple_assign_rhs2 (g
)) != INTEGER_CST
)
1398 prep_stmt
[prep_cnt
] = g
;
1401 /* Only transform if it removes the condition. */
1402 if (!single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi
)), e0
, e1
))
1405 /* Size-wise, this is always profitable. */
1406 if (optimize_bb_for_speed_p (cond_bb
)
1407 /* The special case is useless if it has a low probability. */
1408 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
1409 && EDGE_PRED (middle_bb
, 0)->probability
< profile_probability::even ()
1410 /* If assign is cheap, there is no point avoiding it. */
1411 && estimate_num_insns_seq (bb_seq (middle_bb
), &eni_time_weights
)
1412 >= 3 * estimate_num_insns (cond
, &eni_time_weights
))
1415 tree cond_lhs
= gimple_cond_lhs (cond
);
1416 tree cond_rhs
= gimple_cond_rhs (cond
);
1418 /* Propagate the cond_rhs constant through preparation stmts,
1419 make sure UB isn't invoked while doing that. */
1420 for (int i
= prep_cnt
- 1; i
>= 0; --i
)
1422 gimple
*g
= prep_stmt
[i
];
1423 tree grhs1
= gimple_assign_rhs1 (g
);
1424 if (!operand_equal_for_phi_arg_p (cond_lhs
, grhs1
))
1426 cond_lhs
= gimple_assign_lhs (g
);
1427 cond_rhs
= fold_convert (TREE_TYPE (grhs1
), cond_rhs
);
1428 if (TREE_CODE (cond_rhs
) != INTEGER_CST
1429 || TREE_OVERFLOW (cond_rhs
))
1431 if (gimple_assign_rhs_class (g
) == GIMPLE_BINARY_RHS
)
1433 cond_rhs
= int_const_binop (gimple_assign_rhs_code (g
), cond_rhs
,
1434 gimple_assign_rhs2 (g
));
1435 if (TREE_OVERFLOW (cond_rhs
))
1438 cond_rhs
= fold_convert (TREE_TYPE (cond_lhs
), cond_rhs
);
1439 if (TREE_CODE (cond_rhs
) != INTEGER_CST
1440 || TREE_OVERFLOW (cond_rhs
))
1444 tree lhs
, rhs1
, rhs2
;
1445 enum tree_code code_def
;
1448 lhs
= gimple_assign_lhs (assign
);
1449 rhs1
= gimple_assign_rhs1 (assign
);
1450 rhs2
= gimple_assign_rhs2 (assign
);
1451 code_def
= gimple_assign_rhs_code (assign
);
1455 gcc_assert (prep_cnt
> 0);
1459 code_def
= ERROR_MARK
;
1462 if (((code
== NE_EXPR
&& e1
== false_edge
)
1463 || (code
== EQ_EXPR
&& e1
== true_edge
))
1466 && operand_equal_for_phi_arg_p (arg1
, cond_rhs
))
1469 && operand_equal_for_phi_arg_p (rhs2
, cond_lhs
)
1470 && neutral_element_p (code_def
, cond_rhs
, true))
1473 && operand_equal_for_phi_arg_p (rhs1
, cond_lhs
)
1474 && neutral_element_p (code_def
, cond_rhs
, false))
1476 && operand_equal_for_phi_arg_p (arg1
, cond_rhs
)
1477 && ((operand_equal_for_phi_arg_p (rhs2
, cond_lhs
)
1478 && absorbing_element_p (code_def
, cond_rhs
, true, rhs2
))
1479 || (operand_equal_for_phi_arg_p (rhs1
, cond_lhs
)
1480 && absorbing_element_p (code_def
,
1481 cond_rhs
, false, rhs2
))))))
1483 gsi
= gsi_for_stmt (cond
);
1484 /* Moving ASSIGN might change VR of lhs, e.g. when moving u_6
1492 # RANGE [0, 4294967294]
1493 u_6 = n_5 + 4294967295;
1496 # u_3 = PHI <u_6(3), 4294967295(2)> */
1497 reset_flow_sensitive_info (lhs
);
1498 gimple_stmt_iterator gsi_from
;
1499 for (int i
= prep_cnt
- 1; i
>= 0; --i
)
1501 tree plhs
= gimple_assign_lhs (prep_stmt
[i
]);
1502 reset_flow_sensitive_info (plhs
);
1503 gsi_from
= gsi_for_stmt (prep_stmt
[i
]);
1504 gsi_move_before (&gsi_from
, &gsi
);
1508 gsi_from
= gsi_for_stmt (assign
);
1509 gsi_move_before (&gsi_from
, &gsi
);
1511 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, lhs
);
1518 /* If VAR is an SSA_NAME that points to a BIT_NOT_EXPR then return the TREE for
1519 the value being inverted. */
1522 strip_bit_not (tree var
)
1524 if (TREE_CODE (var
) != SSA_NAME
)
1527 gimple
*assign
= SSA_NAME_DEF_STMT (var
);
1528 if (gimple_code (assign
) != GIMPLE_ASSIGN
)
1531 if (gimple_assign_rhs_code (assign
) != BIT_NOT_EXPR
)
1534 return gimple_assign_rhs1 (assign
);
1537 /* Invert a MIN to a MAX or a MAX to a MIN expression CODE. */
1540 invert_minmax_code (enum tree_code code
)
1552 /* The function minmax_replacement does the main work of doing the minmax
1553 replacement. Return true if the replacement is done. Otherwise return
1555 BB is the basic block where the replacement is going to be done on. ARG0
1556 is argument 0 from the PHI. Likewise for ARG1.
1558 If THREEWAY_P then expect the BB to be laid out in diamond shape with each
1559 BB containing only a MIN or MAX expression. */
1562 minmax_replacement (basic_block cond_bb
, basic_block middle_bb
, basic_block alt_middle_bb
,
1563 edge e0
, edge e1
, gphi
*phi
, tree arg0
, tree arg1
, bool threeway_p
)
1566 edge true_edge
, false_edge
;
1567 enum tree_code minmax
, ass_code
;
1568 tree smaller
, larger
, arg_true
, arg_false
;
1569 gimple_stmt_iterator gsi
, gsi_from
;
1571 tree type
= TREE_TYPE (PHI_RESULT (phi
));
1573 /* The optimization may be unsafe due to NaNs. */
1574 if (HONOR_NANS (type
) || HONOR_SIGNED_ZEROS (type
))
1577 gcond
*cond
= as_a
<gcond
*> (*gsi_last_bb (cond_bb
));
1578 enum tree_code cmp
= gimple_cond_code (cond
);
1579 tree rhs
= gimple_cond_rhs (cond
);
1581 /* Turn EQ/NE of extreme values to order comparisons. */
1582 if ((cmp
== NE_EXPR
|| cmp
== EQ_EXPR
)
1583 && TREE_CODE (rhs
) == INTEGER_CST
1584 && INTEGRAL_TYPE_P (TREE_TYPE (rhs
)))
1586 if (wi::eq_p (wi::to_wide (rhs
), wi::min_value (TREE_TYPE (rhs
))))
1588 cmp
= (cmp
== EQ_EXPR
) ? LT_EXPR
: GE_EXPR
;
1589 rhs
= wide_int_to_tree (TREE_TYPE (rhs
),
1590 wi::min_value (TREE_TYPE (rhs
)) + 1);
1592 else if (wi::eq_p (wi::to_wide (rhs
), wi::max_value (TREE_TYPE (rhs
))))
1594 cmp
= (cmp
== EQ_EXPR
) ? GT_EXPR
: LE_EXPR
;
1595 rhs
= wide_int_to_tree (TREE_TYPE (rhs
),
1596 wi::max_value (TREE_TYPE (rhs
)) - 1);
1600 /* This transformation is only valid for order comparisons. Record which
1601 operand is smaller/larger if the result of the comparison is true. */
1602 tree alt_smaller
= NULL_TREE
;
1603 tree alt_larger
= NULL_TREE
;
1604 if (cmp
== LT_EXPR
|| cmp
== LE_EXPR
)
1606 smaller
= gimple_cond_lhs (cond
);
1608 /* If we have smaller < CST it is equivalent to smaller <= CST-1.
1609 Likewise smaller <= CST is equivalent to smaller < CST+1. */
1610 if (TREE_CODE (larger
) == INTEGER_CST
1611 && INTEGRAL_TYPE_P (TREE_TYPE (larger
)))
1615 wi::overflow_type overflow
;
1616 wide_int alt
= wi::sub (wi::to_wide (larger
), 1,
1617 TYPE_SIGN (TREE_TYPE (larger
)),
1620 alt_larger
= wide_int_to_tree (TREE_TYPE (larger
), alt
);
1624 wi::overflow_type overflow
;
1625 wide_int alt
= wi::add (wi::to_wide (larger
), 1,
1626 TYPE_SIGN (TREE_TYPE (larger
)),
1629 alt_larger
= wide_int_to_tree (TREE_TYPE (larger
), alt
);
1633 else if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
1636 larger
= gimple_cond_lhs (cond
);
1637 /* If we have larger > CST it is equivalent to larger >= CST+1.
1638 Likewise larger >= CST is equivalent to larger > CST-1. */
1639 if (TREE_CODE (smaller
) == INTEGER_CST
1640 && INTEGRAL_TYPE_P (TREE_TYPE (smaller
)))
1642 wi::overflow_type overflow
;
1645 wide_int alt
= wi::add (wi::to_wide (smaller
), 1,
1646 TYPE_SIGN (TREE_TYPE (smaller
)),
1649 alt_smaller
= wide_int_to_tree (TREE_TYPE (smaller
), alt
);
1653 wide_int alt
= wi::sub (wi::to_wide (smaller
), 1,
1654 TYPE_SIGN (TREE_TYPE (smaller
)),
1657 alt_smaller
= wide_int_to_tree (TREE_TYPE (smaller
), alt
);
1664 /* Handle the special case of (signed_type)x < 0 being equivalent
1665 to x > MAX_VAL(signed_type) and (signed_type)x >= 0 equivalent
1666 to x <= MAX_VAL(signed_type). */
1667 if ((cmp
== GE_EXPR
|| cmp
== LT_EXPR
)
1668 && INTEGRAL_TYPE_P (type
)
1669 && TYPE_UNSIGNED (type
)
1670 && integer_zerop (rhs
))
1672 tree op
= gimple_cond_lhs (cond
);
1673 if (TREE_CODE (op
) == SSA_NAME
1674 && INTEGRAL_TYPE_P (TREE_TYPE (op
))
1675 && !TYPE_UNSIGNED (TREE_TYPE (op
)))
1677 gimple
*def_stmt
= SSA_NAME_DEF_STMT (op
);
1678 if (gimple_assign_cast_p (def_stmt
))
1680 tree op1
= gimple_assign_rhs1 (def_stmt
);
1681 if (INTEGRAL_TYPE_P (TREE_TYPE (op1
))
1682 && TYPE_UNSIGNED (TREE_TYPE (op1
))
1683 && (TYPE_PRECISION (TREE_TYPE (op
))
1684 == TYPE_PRECISION (TREE_TYPE (op1
)))
1685 && useless_type_conversion_p (type
, TREE_TYPE (op1
)))
1687 wide_int w1
= wi::max_value (TREE_TYPE (op
));
1688 wide_int w2
= wi::add (w1
, 1);
1692 smaller
= wide_int_to_tree (TREE_TYPE (op1
), w1
);
1693 alt_smaller
= wide_int_to_tree (TREE_TYPE (op1
), w2
);
1694 alt_larger
= NULL_TREE
;
1699 larger
= wide_int_to_tree (TREE_TYPE (op1
), w1
);
1700 alt_larger
= wide_int_to_tree (TREE_TYPE (op1
), w2
);
1701 alt_smaller
= NULL_TREE
;
1708 /* We need to know which is the true edge and which is the false
1709 edge so that we know if have abs or negative abs. */
1710 extract_true_false_edges_from_block (cond_bb
, &true_edge
, &false_edge
);
1712 /* Forward the edges over the middle basic block. */
1713 if (true_edge
->dest
== middle_bb
)
1714 true_edge
= EDGE_SUCC (true_edge
->dest
, 0);
1715 if (false_edge
->dest
== middle_bb
)
1716 false_edge
= EDGE_SUCC (false_edge
->dest
, 0);
1718 /* When THREEWAY_P then e1 will point to the edge of the final transition
1719 from middle-bb to end. */
1720 if (true_edge
== e0
)
1723 gcc_assert (false_edge
== e1
);
1729 gcc_assert (false_edge
== e0
);
1731 gcc_assert (true_edge
== e1
);
1736 if (empty_block_p (middle_bb
))
1738 if ((operand_equal_for_phi_arg_p (arg_true
, smaller
)
1740 && operand_equal_for_phi_arg_p (arg_true
, alt_smaller
)))
1741 && (operand_equal_for_phi_arg_p (arg_false
, larger
)
1743 && operand_equal_for_phi_arg_p (arg_true
, alt_larger
))))
1747 if (smaller < larger)
1753 else if ((operand_equal_for_phi_arg_p (arg_false
, smaller
)
1755 && operand_equal_for_phi_arg_p (arg_false
, alt_smaller
)))
1756 && (operand_equal_for_phi_arg_p (arg_true
, larger
)
1758 && operand_equal_for_phi_arg_p (arg_true
, alt_larger
))))
1763 else if (middle_bb
!= alt_middle_bb
&& threeway_p
)
1765 /* Recognize the following case:
1767 if (smaller < larger)
1768 a = MIN (smaller, c);
1770 b = MIN (larger, c);
1773 This is equivalent to
1775 a = MIN (smaller, c);
1776 x = MIN (larger, a); */
1778 gimple
*assign
= last_and_only_stmt (middle_bb
);
1779 tree lhs
, op0
, op1
, bound
;
1780 tree alt_lhs
, alt_op0
, alt_op1
;
1781 bool invert
= false;
1783 /* When THREEWAY_P then e1 will point to the edge of the final transition
1784 from middle-bb to end. */
1785 if (true_edge
== e0
)
1786 gcc_assert (false_edge
== EDGE_PRED (e1
->src
, 0));
1788 gcc_assert (true_edge
== EDGE_PRED (e1
->src
, 0));
1790 bool valid_minmax_p
= false;
1791 gimple_stmt_iterator it1
1792 = gsi_start_nondebug_after_labels_bb (middle_bb
);
1793 gimple_stmt_iterator it2
1794 = gsi_start_nondebug_after_labels_bb (alt_middle_bb
);
1795 if (gsi_one_nondebug_before_end_p (it1
)
1796 && gsi_one_nondebug_before_end_p (it2
))
1798 gimple
*stmt1
= gsi_stmt (it1
);
1799 gimple
*stmt2
= gsi_stmt (it2
);
1800 if (is_gimple_assign (stmt1
) && is_gimple_assign (stmt2
))
1802 enum tree_code code1
= gimple_assign_rhs_code (stmt1
);
1803 enum tree_code code2
= gimple_assign_rhs_code (stmt2
);
1804 valid_minmax_p
= (code1
== MIN_EXPR
|| code1
== MAX_EXPR
)
1805 && (code2
== MIN_EXPR
|| code2
== MAX_EXPR
);
1809 if (!valid_minmax_p
)
1813 || gimple_code (assign
) != GIMPLE_ASSIGN
)
1816 lhs
= gimple_assign_lhs (assign
);
1817 ass_code
= gimple_assign_rhs_code (assign
);
1818 if (ass_code
!= MAX_EXPR
&& ass_code
!= MIN_EXPR
)
1821 op0
= gimple_assign_rhs1 (assign
);
1822 op1
= gimple_assign_rhs2 (assign
);
1824 assign
= last_and_only_stmt (alt_middle_bb
);
1826 || gimple_code (assign
) != GIMPLE_ASSIGN
)
1829 alt_lhs
= gimple_assign_lhs (assign
);
1830 if (ass_code
!= gimple_assign_rhs_code (assign
))
1833 if (!operand_equal_for_phi_arg_p (lhs
, arg_true
)
1834 || !operand_equal_for_phi_arg_p (alt_lhs
, arg_false
))
1837 alt_op0
= gimple_assign_rhs1 (assign
);
1838 alt_op1
= gimple_assign_rhs2 (assign
);
1840 if ((operand_equal_for_phi_arg_p (op0
, smaller
)
1842 && operand_equal_for_phi_arg_p (op0
, alt_smaller
)))
1843 && (operand_equal_for_phi_arg_p (alt_op0
, larger
)
1845 && operand_equal_for_phi_arg_p (alt_op0
, alt_larger
))))
1847 /* We got here if the condition is true, i.e., SMALLER < LARGER. */
1848 if (!operand_equal_for_phi_arg_p (op1
, alt_op1
))
1851 if ((arg0
= strip_bit_not (op0
)) != NULL
1852 && (arg1
= strip_bit_not (alt_op0
)) != NULL
1853 && (bound
= strip_bit_not (op1
)) != NULL
)
1856 ass_code
= invert_minmax_code (ass_code
);
1867 else if ((operand_equal_for_phi_arg_p (op0
, larger
)
1869 && operand_equal_for_phi_arg_p (op0
, alt_larger
)))
1870 && (operand_equal_for_phi_arg_p (alt_op0
, smaller
)
1872 && operand_equal_for_phi_arg_p (alt_op0
, alt_smaller
))))
1874 /* We got here if the condition is true, i.e., SMALLER > LARGER. */
1875 if (!operand_equal_for_phi_arg_p (op1
, alt_op1
))
1878 if ((arg0
= strip_bit_not (op0
)) != NULL
1879 && (arg1
= strip_bit_not (alt_op0
)) != NULL
1880 && (bound
= strip_bit_not (op1
)) != NULL
)
1883 ass_code
= invert_minmax_code (ass_code
);
1897 /* Emit the statement to compute min/max. */
1898 location_t locus
= gimple_location (last_nondebug_stmt (cond_bb
));
1899 gimple_seq stmts
= NULL
;
1900 tree phi_result
= PHI_RESULT (phi
);
1901 result
= gimple_build (&stmts
, locus
, minmax
, TREE_TYPE (phi_result
),
1903 result
= gimple_build (&stmts
, locus
, ass_code
, TREE_TYPE (phi_result
),
1906 result
= gimple_build (&stmts
, locus
, BIT_NOT_EXPR
, TREE_TYPE (phi_result
),
1909 gsi
= gsi_last_bb (cond_bb
);
1910 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
1912 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, result
);
1918 /* Recognize the following case, assuming d <= u:
1924 This is equivalent to
1929 gimple
*assign
= last_and_only_stmt (middle_bb
);
1930 tree lhs
, op0
, op1
, bound
;
1932 if (!single_pred_p (middle_bb
))
1936 || gimple_code (assign
) != GIMPLE_ASSIGN
)
1939 lhs
= gimple_assign_lhs (assign
);
1940 ass_code
= gimple_assign_rhs_code (assign
);
1941 if (ass_code
!= MAX_EXPR
&& ass_code
!= MIN_EXPR
)
1943 op0
= gimple_assign_rhs1 (assign
);
1944 op1
= gimple_assign_rhs2 (assign
);
1946 if (true_edge
->src
== middle_bb
)
1948 /* We got here if the condition is true, i.e., SMALLER < LARGER. */
1949 if (!operand_equal_for_phi_arg_p (lhs
, arg_true
))
1952 if (operand_equal_for_phi_arg_p (arg_false
, larger
)
1954 && operand_equal_for_phi_arg_p (arg_false
, alt_larger
)))
1958 if (smaller < larger)
1960 r' = MAX_EXPR (smaller, bound)
1962 r = PHI <r', larger> --> to be turned to MIN_EXPR. */
1963 if (ass_code
!= MAX_EXPR
)
1967 if (operand_equal_for_phi_arg_p (op0
, smaller
)
1969 && operand_equal_for_phi_arg_p (op0
, alt_smaller
)))
1971 else if (operand_equal_for_phi_arg_p (op1
, smaller
)
1973 && operand_equal_for_phi_arg_p (op1
, alt_smaller
)))
1978 /* We need BOUND <= LARGER. */
1979 if (!integer_nonzerop (fold_build2 (LE_EXPR
, boolean_type_node
,
1983 else if (operand_equal_for_phi_arg_p (arg_false
, smaller
)
1985 && operand_equal_for_phi_arg_p (arg_false
, alt_smaller
)))
1989 if (smaller < larger)
1991 r' = MIN_EXPR (larger, bound)
1993 r = PHI <r', smaller> --> to be turned to MAX_EXPR. */
1994 if (ass_code
!= MIN_EXPR
)
1998 if (operand_equal_for_phi_arg_p (op0
, larger
)
2000 && operand_equal_for_phi_arg_p (op0
, alt_larger
)))
2002 else if (operand_equal_for_phi_arg_p (op1
, larger
)
2004 && operand_equal_for_phi_arg_p (op1
, alt_larger
)))
2009 /* We need BOUND >= SMALLER. */
2010 if (!integer_nonzerop (fold_build2 (GE_EXPR
, boolean_type_node
,
2019 /* We got here if the condition is false, i.e., SMALLER > LARGER. */
2020 if (!operand_equal_for_phi_arg_p (lhs
, arg_false
))
2023 if (operand_equal_for_phi_arg_p (arg_true
, larger
)
2025 && operand_equal_for_phi_arg_p (arg_true
, alt_larger
)))
2029 if (smaller > larger)
2031 r' = MIN_EXPR (smaller, bound)
2033 r = PHI <r', larger> --> to be turned to MAX_EXPR. */
2034 if (ass_code
!= MIN_EXPR
)
2038 if (operand_equal_for_phi_arg_p (op0
, smaller
)
2040 && operand_equal_for_phi_arg_p (op0
, alt_smaller
)))
2042 else if (operand_equal_for_phi_arg_p (op1
, smaller
)
2044 && operand_equal_for_phi_arg_p (op1
, alt_smaller
)))
2049 /* We need BOUND >= LARGER. */
2050 if (!integer_nonzerop (fold_build2 (GE_EXPR
, boolean_type_node
,
2054 else if (operand_equal_for_phi_arg_p (arg_true
, smaller
)
2056 && operand_equal_for_phi_arg_p (arg_true
, alt_smaller
)))
2060 if (smaller > larger)
2062 r' = MAX_EXPR (larger, bound)
2064 r = PHI <r', smaller> --> to be turned to MIN_EXPR. */
2065 if (ass_code
!= MAX_EXPR
)
2069 if (operand_equal_for_phi_arg_p (op0
, larger
))
2071 else if (operand_equal_for_phi_arg_p (op1
, larger
))
2076 /* We need BOUND <= SMALLER. */
2077 if (!integer_nonzerop (fold_build2 (LE_EXPR
, boolean_type_node
,
2085 /* Move the statement from the middle block. */
2086 gsi
= gsi_last_bb (cond_bb
);
2087 gsi_from
= gsi_last_nondebug_bb (middle_bb
);
2088 reset_flow_sensitive_info (SINGLE_SSA_TREE_OPERAND (gsi_stmt (gsi_from
),
2090 gsi_move_before (&gsi_from
, &gsi
);
2093 /* Emit the statement to compute min/max. */
2094 gimple_seq stmts
= NULL
;
2095 tree phi_result
= PHI_RESULT (phi
);
2096 result
= gimple_build (&stmts
, minmax
, TREE_TYPE (phi_result
), arg0
, arg1
);
2098 gsi
= gsi_last_bb (cond_bb
);
2099 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2101 replace_phi_edge_with_variable (cond_bb
, e1
, phi
, result
);
2106 /* Attempt to optimize (x <=> y) cmp 0 and similar comparisons.
2107 For strong ordering <=> try to match something like:
2108 <bb 2> : // cond3_bb (== cond2_bb)
2109 if (x_4(D) != y_5(D))
2115 if (x_4(D) < y_5(D))
2120 <bb 4> : // middle_bb
2123 # iftmp.0_2 = PHI <1(4), 0(2), -1(3)>
2124 _1 = iftmp.0_2 == 0;
2126 and for partial ordering <=> something like:
2128 <bb 2> : // cond3_bb
2129 if (a_3(D) == b_5(D))
2130 goto <bb 6>; [50.00%]
2132 goto <bb 3>; [50.00%]
2134 <bb 3> [local count: 536870913]: // cond2_bb
2135 if (a_3(D) < b_5(D))
2136 goto <bb 6>; [50.00%]
2138 goto <bb 4>; [50.00%]
2140 <bb 4> [local count: 268435456]: // cond_bb
2141 if (a_3(D) > b_5(D))
2142 goto <bb 6>; [50.00%]
2144 goto <bb 5>; [50.00%]
2146 <bb 5> [local count: 134217728]: // middle_bb
2148 <bb 6> [local count: 1073741824]: // phi_bb
2149 # SR.27_4 = PHI <0(2), -1(3), 1(4), 2(5)>
2150 _2 = SR.27_4 > 0; */
2153 spaceship_replacement (basic_block cond_bb
, basic_block middle_bb
,
2154 edge e0
, edge e1
, gphi
*phi
,
2155 tree arg0
, tree arg1
)
2157 tree phires
= PHI_RESULT (phi
);
2158 if (!INTEGRAL_TYPE_P (TREE_TYPE (phires
))
2159 || TYPE_UNSIGNED (TREE_TYPE (phires
))
2160 || !tree_fits_shwi_p (arg0
)
2161 || !tree_fits_shwi_p (arg1
)
2162 || !IN_RANGE (tree_to_shwi (arg0
), -1, 2)
2163 || !IN_RANGE (tree_to_shwi (arg1
), -1, 2))
2166 basic_block phi_bb
= gimple_bb (phi
);
2167 gcc_assert (phi_bb
== e0
->dest
&& phi_bb
== e1
->dest
);
2168 if (!IN_RANGE (EDGE_COUNT (phi_bb
->preds
), 3, 4))
2171 use_operand_p use_p
;
2173 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (phires
))
2175 if (!single_imm_use (phires
, &use_p
, &use_stmt
))
2179 gimple
*orig_use_stmt
= use_stmt
;
2180 tree orig_use_lhs
= NULL_TREE
;
2181 int prec
= TYPE_PRECISION (TREE_TYPE (phires
));
2182 bool is_cast
= false;
2184 /* Deal with the case when match.pd has rewritten the (res & ~1) == 0
2185 into res <= 1 and has left a type-cast for signed types. */
2186 if (gimple_assign_cast_p (use_stmt
))
2188 orig_use_lhs
= gimple_assign_lhs (use_stmt
);
2189 /* match.pd would have only done this for a signed type,
2190 so the conversion must be to an unsigned one. */
2191 tree ty1
= TREE_TYPE (gimple_assign_rhs1 (use_stmt
));
2192 tree ty2
= TREE_TYPE (orig_use_lhs
);
2194 if (!TYPE_UNSIGNED (ty2
) || !INTEGRAL_TYPE_P (ty2
))
2196 if (TYPE_PRECISION (ty1
) > TYPE_PRECISION (ty2
))
2198 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs
))
2200 if (!single_imm_use (orig_use_lhs
, &use_p
, &use_stmt
))
2205 else if (is_gimple_assign (use_stmt
)
2206 && gimple_assign_rhs_code (use_stmt
) == BIT_AND_EXPR
2207 && TREE_CODE (gimple_assign_rhs2 (use_stmt
)) == INTEGER_CST
2208 && (wi::to_wide (gimple_assign_rhs2 (use_stmt
))
2209 == wi::shifted_mask (1, prec
- 1, false, prec
)))
2211 /* For partial_ordering result operator>= with unspec as second
2212 argument is (res & 1) == res, folded by match.pd into
2214 orig_use_lhs
= gimple_assign_lhs (use_stmt
);
2215 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs
))
2217 if (!single_imm_use (orig_use_lhs
, &use_p
, &use_stmt
))
2220 if (gimple_code (use_stmt
) == GIMPLE_COND
)
2222 cmp
= gimple_cond_code (use_stmt
);
2223 lhs
= gimple_cond_lhs (use_stmt
);
2224 rhs
= gimple_cond_rhs (use_stmt
);
2226 else if (is_gimple_assign (use_stmt
))
2228 if (gimple_assign_rhs_class (use_stmt
) == GIMPLE_BINARY_RHS
)
2230 cmp
= gimple_assign_rhs_code (use_stmt
);
2231 lhs
= gimple_assign_rhs1 (use_stmt
);
2232 rhs
= gimple_assign_rhs2 (use_stmt
);
2234 else if (gimple_assign_rhs_code (use_stmt
) == COND_EXPR
)
2236 tree cond
= gimple_assign_rhs1 (use_stmt
);
2237 if (!COMPARISON_CLASS_P (cond
))
2239 cmp
= TREE_CODE (cond
);
2240 lhs
= TREE_OPERAND (cond
, 0);
2241 rhs
= TREE_OPERAND (cond
, 1);
2260 if (lhs
!= (orig_use_lhs
? orig_use_lhs
: phires
)
2261 || !tree_fits_shwi_p (rhs
)
2262 || !IN_RANGE (tree_to_shwi (rhs
), -1, 1))
2267 if (TREE_CODE (rhs
) != INTEGER_CST
)
2269 /* As for -ffast-math we assume the 2 return to be
2270 impossible, canonicalize (unsigned) res <= 1U or
2271 (unsigned) res < 2U into res >= 0 and (unsigned) res > 1U
2272 or (unsigned) res >= 2U as res < 0. */
2276 if (!integer_onep (rhs
))
2281 if (wi::ne_p (wi::to_widest (rhs
), 2))
2286 if (!integer_onep (rhs
))
2291 if (wi::ne_p (wi::to_widest (rhs
), 2))
2298 rhs
= build_zero_cst (TREE_TYPE (phires
));
2300 else if (orig_use_lhs
)
2302 if ((cmp
!= EQ_EXPR
&& cmp
!= NE_EXPR
) || !integer_zerop (rhs
))
2304 /* As for -ffast-math we assume the 2 return to be
2305 impossible, canonicalize (res & ~1) == 0 into
2306 res >= 0 and (res & ~1) != 0 as res < 0. */
2307 cmp
= cmp
== EQ_EXPR
? GE_EXPR
: LT_EXPR
;
2310 if (!empty_block_p (middle_bb
))
2313 gcond
*cond1
= as_a
<gcond
*> (*gsi_last_bb (cond_bb
));
2314 enum tree_code cmp1
= gimple_cond_code (cond1
);
2325 tree lhs1
= gimple_cond_lhs (cond1
);
2326 tree rhs1
= gimple_cond_rhs (cond1
);
2327 /* The optimization may be unsafe due to NaNs. */
2328 if (HONOR_NANS (TREE_TYPE (lhs1
)))
2330 if (TREE_CODE (lhs1
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs1
))
2332 if (TREE_CODE (rhs1
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1
))
2335 if (!single_pred_p (cond_bb
) || !cond_only_block_p (cond_bb
))
2338 basic_block cond2_bb
= single_pred (cond_bb
);
2339 if (EDGE_COUNT (cond2_bb
->succs
) != 2)
2341 edge cond2_phi_edge
;
2342 if (EDGE_SUCC (cond2_bb
, 0)->dest
== cond_bb
)
2344 if (EDGE_SUCC (cond2_bb
, 1)->dest
!= phi_bb
)
2346 cond2_phi_edge
= EDGE_SUCC (cond2_bb
, 1);
2348 else if (EDGE_SUCC (cond2_bb
, 0)->dest
!= phi_bb
)
2351 cond2_phi_edge
= EDGE_SUCC (cond2_bb
, 0);
2352 tree arg2
= gimple_phi_arg_def (phi
, cond2_phi_edge
->dest_idx
);
2353 if (!tree_fits_shwi_p (arg2
))
2355 gcond
*cond2
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (cond2_bb
));
2358 enum tree_code cmp2
= gimple_cond_code (cond2
);
2359 tree lhs2
= gimple_cond_lhs (cond2
);
2360 tree rhs2
= gimple_cond_rhs (cond2
);
2363 if (!operand_equal_p (rhs2
, rhs1
, 0))
2365 if ((cmp2
== EQ_EXPR
|| cmp2
== NE_EXPR
)
2366 && TREE_CODE (rhs1
) == INTEGER_CST
2367 && TREE_CODE (rhs2
) == INTEGER_CST
)
2369 /* For integers, we can have cond2 x == 5
2370 and cond1 x < 5, x <= 4, x <= 5, x < 6,
2371 x > 5, x >= 6, x >= 5 or x > 4. */
2372 if (tree_int_cst_lt (rhs1
, rhs2
))
2374 if (wi::ne_p (wi::to_wide (rhs1
) + 1, wi::to_wide (rhs2
)))
2376 if (cmp1
== LE_EXPR
)
2378 else if (cmp1
== GT_EXPR
)
2385 gcc_checking_assert (tree_int_cst_lt (rhs2
, rhs1
));
2386 if (wi::ne_p (wi::to_wide (rhs2
) + 1, wi::to_wide (rhs1
)))
2388 if (cmp1
== LT_EXPR
)
2390 else if (cmp1
== GE_EXPR
)
2401 else if (lhs2
== rhs1
)
2410 basic_block cond3_bb
= cond2_bb
;
2411 edge cond3_phi_edge
= cond2_phi_edge
;
2412 gcond
*cond3
= cond2
;
2413 enum tree_code cmp3
= cmp2
;
2416 if (EDGE_COUNT (phi_bb
->preds
) == 4)
2418 if (absu_hwi (tree_to_shwi (arg2
)) != 1)
2420 if (e1
->flags
& EDGE_TRUE_VALUE
)
2422 if (tree_to_shwi (arg0
) != 2
2423 || absu_hwi (tree_to_shwi (arg1
)) != 1
2424 || wi::to_widest (arg1
) == wi::to_widest (arg2
))
2427 else if (tree_to_shwi (arg1
) != 2
2428 || absu_hwi (tree_to_shwi (arg0
)) != 1
2429 || wi::to_widest (arg0
) == wi::to_widest (arg1
))
2441 /* if (x < y) goto phi_bb; else fallthru;
2442 if (x > y) goto phi_bb; else fallthru;
2445 is ok, but if x and y are swapped in one of the comparisons,
2446 or the comparisons are the same and operands not swapped,
2447 or the true and false edges are swapped, it is not. */
2449 ^ (((cond2_phi_edge
->flags
2450 & ((cmp2
== LT_EXPR
|| cmp2
== LE_EXPR
)
2451 ? EDGE_TRUE_VALUE
: EDGE_FALSE_VALUE
)) != 0)
2453 & ((cmp1
== LT_EXPR
|| cmp1
== LE_EXPR
)
2454 ? EDGE_TRUE_VALUE
: EDGE_FALSE_VALUE
)) != 0)))
2456 if (!single_pred_p (cond2_bb
) || !cond_only_block_p (cond2_bb
))
2458 cond3_bb
= single_pred (cond2_bb
);
2459 if (EDGE_COUNT (cond2_bb
->succs
) != 2)
2461 if (EDGE_SUCC (cond3_bb
, 0)->dest
== cond2_bb
)
2463 if (EDGE_SUCC (cond3_bb
, 1)->dest
!= phi_bb
)
2465 cond3_phi_edge
= EDGE_SUCC (cond3_bb
, 1);
2467 else if (EDGE_SUCC (cond3_bb
, 0)->dest
!= phi_bb
)
2470 cond3_phi_edge
= EDGE_SUCC (cond3_bb
, 0);
2471 arg3
= gimple_phi_arg_def (phi
, cond3_phi_edge
->dest_idx
);
2472 cond3
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (cond3_bb
));
2475 cmp3
= gimple_cond_code (cond3
);
2476 lhs3
= gimple_cond_lhs (cond3
);
2477 rhs3
= gimple_cond_rhs (cond3
);
2480 if (!operand_equal_p (rhs3
, rhs1
, 0))
2483 else if (lhs3
== rhs1
)
2491 else if (absu_hwi (tree_to_shwi (arg0
)) != 1
2492 || absu_hwi (tree_to_shwi (arg1
)) != 1
2493 || wi::to_widest (arg0
) == wi::to_widest (arg1
))
2496 if (!integer_zerop (arg3
) || (cmp3
!= EQ_EXPR
&& cmp3
!= NE_EXPR
))
2498 if ((cond3_phi_edge
->flags
& (cmp3
== EQ_EXPR
2499 ? EDGE_TRUE_VALUE
: EDGE_FALSE_VALUE
)) == 0)
2502 /* lhs1 one_cmp rhs1 results in phires of 1. */
2503 enum tree_code one_cmp
;
2504 if ((cmp1
== LT_EXPR
|| cmp1
== LE_EXPR
)
2505 ^ (!integer_onep ((e1
->flags
& EDGE_TRUE_VALUE
) ? arg1
: arg0
)))
2510 enum tree_code res_cmp
;
2514 if (integer_zerop (rhs
))
2516 else if (integer_minus_onep (rhs
))
2517 res_cmp
= one_cmp
== LT_EXPR
? GT_EXPR
: LT_EXPR
;
2518 else if (integer_onep (rhs
))
2524 if (integer_zerop (rhs
))
2526 else if (integer_minus_onep (rhs
))
2527 res_cmp
= one_cmp
== LT_EXPR
? LE_EXPR
: GE_EXPR
;
2528 else if (integer_onep (rhs
))
2529 res_cmp
= one_cmp
== LT_EXPR
? GE_EXPR
: LE_EXPR
;
2534 if (integer_onep (rhs
))
2535 res_cmp
= one_cmp
== LT_EXPR
? GE_EXPR
: LE_EXPR
;
2536 else if (integer_zerop (rhs
))
2537 res_cmp
= one_cmp
== LT_EXPR
? GT_EXPR
: LT_EXPR
;
2542 if (integer_zerop (rhs
))
2543 res_cmp
= one_cmp
== LT_EXPR
? GE_EXPR
: LE_EXPR
;
2544 else if (integer_minus_onep (rhs
))
2545 res_cmp
= one_cmp
== LT_EXPR
? GT_EXPR
: LT_EXPR
;
2550 if (integer_minus_onep (rhs
))
2551 res_cmp
= one_cmp
== LT_EXPR
? LE_EXPR
: GE_EXPR
;
2552 else if (integer_zerop (rhs
))
2558 if (integer_zerop (rhs
))
2559 res_cmp
= one_cmp
== LT_EXPR
? LE_EXPR
: GE_EXPR
;
2560 else if (integer_onep (rhs
))
2569 if (gimple_code (use_stmt
) == GIMPLE_COND
)
2571 gcond
*use_cond
= as_a
<gcond
*> (use_stmt
);
2572 gimple_cond_set_code (use_cond
, res_cmp
);
2573 gimple_cond_set_lhs (use_cond
, lhs1
);
2574 gimple_cond_set_rhs (use_cond
, rhs1
);
2576 else if (gimple_assign_rhs_class (use_stmt
) == GIMPLE_BINARY_RHS
)
2578 gimple_assign_set_rhs_code (use_stmt
, res_cmp
);
2579 gimple_assign_set_rhs1 (use_stmt
, lhs1
);
2580 gimple_assign_set_rhs2 (use_stmt
, rhs1
);
2584 tree cond
= build2 (res_cmp
, TREE_TYPE (gimple_assign_rhs1 (use_stmt
)),
2586 gimple_assign_set_rhs1 (use_stmt
, cond
);
2588 update_stmt (use_stmt
);
2590 if (MAY_HAVE_DEBUG_BIND_STMTS
)
2592 use_operand_p use_p
;
2593 imm_use_iterator iter
;
2594 bool has_debug_uses
= false;
2595 bool has_cast_debug_uses
= false;
2596 FOR_EACH_IMM_USE_FAST (use_p
, iter
, phires
)
2598 gimple
*use_stmt
= USE_STMT (use_p
);
2599 if (orig_use_lhs
&& use_stmt
== orig_use_stmt
)
2601 gcc_assert (is_gimple_debug (use_stmt
));
2602 has_debug_uses
= true;
2607 if (!has_debug_uses
|| is_cast
)
2608 FOR_EACH_IMM_USE_FAST (use_p
, iter
, orig_use_lhs
)
2610 gimple
*use_stmt
= USE_STMT (use_p
);
2611 gcc_assert (is_gimple_debug (use_stmt
));
2612 has_debug_uses
= true;
2614 has_cast_debug_uses
= true;
2616 gimple_stmt_iterator gsi
= gsi_for_stmt (orig_use_stmt
);
2617 tree zero
= build_zero_cst (TREE_TYPE (orig_use_lhs
));
2618 gimple_assign_set_rhs_with_ops (&gsi
, INTEGER_CST
, zero
);
2619 update_stmt (orig_use_stmt
);
2624 /* If there are debug uses, emit something like:
2625 # DEBUG D#1 => i_2(D) > j_3(D) ? 1 : -1
2626 # DEBUG D#2 => i_2(D) == j_3(D) ? 0 : D#1
2627 where > stands for the comparison that yielded 1
2628 and replace debug uses of phi result with that D#2.
2629 Ignore the value of 2, because if NaNs aren't expected,
2630 all floating point numbers should be comparable. */
2631 gimple_stmt_iterator gsi
= gsi_after_labels (gimple_bb (phi
));
2632 tree type
= TREE_TYPE (phires
);
2633 tree temp1
= build_debug_expr_decl (type
);
2634 tree t
= build2 (one_cmp
, boolean_type_node
, lhs1
, rhs2
);
2635 t
= build3 (COND_EXPR
, type
, t
, build_one_cst (type
),
2636 build_int_cst (type
, -1));
2637 gimple
*g
= gimple_build_debug_bind (temp1
, t
, phi
);
2638 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2639 tree temp2
= build_debug_expr_decl (type
);
2640 t
= build2 (EQ_EXPR
, boolean_type_node
, lhs1
, rhs2
);
2641 t
= build3 (COND_EXPR
, type
, t
, build_zero_cst (type
), temp1
);
2642 g
= gimple_build_debug_bind (temp2
, t
, phi
);
2643 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2644 replace_uses_by (phires
, temp2
);
2647 if (has_cast_debug_uses
)
2649 tree temp3
= make_node (DEBUG_EXPR_DECL
);
2650 DECL_ARTIFICIAL (temp3
) = 1;
2651 TREE_TYPE (temp3
) = TREE_TYPE (orig_use_lhs
);
2652 SET_DECL_MODE (temp3
, TYPE_MODE (type
));
2653 t
= fold_convert (TREE_TYPE (temp3
), temp2
);
2654 g
= gimple_build_debug_bind (temp3
, t
, phi
);
2655 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2656 replace_uses_by (orig_use_lhs
, temp3
);
2659 replace_uses_by (orig_use_lhs
, temp2
);
2666 gimple_stmt_iterator gsi
= gsi_for_stmt (orig_use_stmt
);
2667 gsi_remove (&gsi
, true);
2670 gimple_stmt_iterator psi
= gsi_for_stmt (phi
);
2671 remove_phi_node (&psi
, true);
2672 statistics_counter_event (cfun
, "spaceship replacement", 1);
2677 /* Optimize x ? __builtin_fun (x) : C, where C is __builtin_fun (0).
2687 _2 = (unsigned long) b_4(D);
2688 _9 = __builtin_popcountl (_2);
2690 _9 = __builtin_popcountl (b_4(D));
2693 c_12 = PHI <0(2), _9(3)>
2697 _2 = (unsigned long) b_4(D);
2698 _9 = __builtin_popcountl (_2);
2700 _9 = __builtin_popcountl (b_4(D));
2705 Similarly for __builtin_clz or __builtin_ctz if
2706 C?Z_DEFINED_VALUE_AT_ZERO is 2, optab is present and
2707 instead of 0 above it uses the value from that macro. */
2710 cond_removal_in_builtin_zero_pattern (basic_block cond_bb
,
2711 basic_block middle_bb
,
2712 edge e1
, edge e2
, gphi
*phi
,
2713 tree arg0
, tree arg1
)
2715 gimple_stmt_iterator gsi
, gsi_from
;
2717 gimple
*cast
= NULL
;
2721 _2 = (unsigned long) b_4(D);
2722 _9 = __builtin_popcountl (_2);
2724 _9 = __builtin_popcountl (b_4(D));
2725 are the only stmts in the middle_bb. */
2727 gsi
= gsi_start_nondebug_after_labels_bb (middle_bb
);
2728 if (gsi_end_p (gsi
))
2730 cast
= gsi_stmt (gsi
);
2731 gsi_next_nondebug (&gsi
);
2732 if (!gsi_end_p (gsi
))
2734 call
= gsi_stmt (gsi
);
2735 gsi_next_nondebug (&gsi
);
2736 if (!gsi_end_p (gsi
))
2745 /* Check that we have a popcount/clz/ctz builtin. */
2746 if (!is_gimple_call (call
) || gimple_call_num_args (call
) != 1)
2749 arg
= gimple_call_arg (call
, 0);
2750 lhs
= gimple_get_lhs (call
);
2752 if (lhs
== NULL_TREE
)
2755 combined_fn cfn
= gimple_call_combined_fn (call
);
2756 internal_fn ifn
= IFN_LAST
;
2760 case CFN_BUILT_IN_BSWAP16
:
2761 case CFN_BUILT_IN_BSWAP32
:
2762 case CFN_BUILT_IN_BSWAP64
:
2763 case CFN_BUILT_IN_BSWAP128
:
2769 if (INTEGRAL_TYPE_P (TREE_TYPE (arg
)))
2771 tree type
= TREE_TYPE (arg
);
2772 if (direct_internal_fn_supported_p (IFN_CLZ
, type
, OPTIMIZE_FOR_BOTH
)
2773 && CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type
),
2782 if (INTEGRAL_TYPE_P (TREE_TYPE (arg
)))
2784 tree type
= TREE_TYPE (arg
);
2785 if (direct_internal_fn_supported_p (IFN_CTZ
, type
, OPTIMIZE_FOR_BOTH
)
2786 && CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type
),
2794 case CFN_BUILT_IN_CLRSB
:
2795 val
= TYPE_PRECISION (integer_type_node
) - 1;
2797 case CFN_BUILT_IN_CLRSBL
:
2798 val
= TYPE_PRECISION (long_integer_type_node
) - 1;
2800 case CFN_BUILT_IN_CLRSBLL
:
2801 val
= TYPE_PRECISION (long_long_integer_type_node
) - 1;
2809 /* We have a cast stmt feeding popcount/clz/ctz builtin. */
2810 /* Check that we have a cast prior to that. */
2811 if (gimple_code (cast
) != GIMPLE_ASSIGN
2812 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (cast
)))
2814 /* Result of the cast stmt is the argument to the builtin. */
2815 if (arg
!= gimple_assign_lhs (cast
))
2817 arg
= gimple_assign_rhs1 (cast
);
2820 gcond
*cond
= dyn_cast
<gcond
*> (*gsi_last_bb (cond_bb
));
2822 /* Cond_bb has a check for b_4 [!=|==] 0 before calling the popcount/clz/ctz
2825 || (gimple_cond_code (cond
) != NE_EXPR
2826 && gimple_cond_code (cond
) != EQ_EXPR
)
2827 || !integer_zerop (gimple_cond_rhs (cond
))
2828 || arg
!= gimple_cond_lhs (cond
))
2832 if ((e2
->flags
& EDGE_TRUE_VALUE
2833 && gimple_cond_code (cond
) == NE_EXPR
)
2834 || (e1
->flags
& EDGE_TRUE_VALUE
2835 && gimple_cond_code (cond
) == EQ_EXPR
))
2837 std::swap (arg0
, arg1
);
2841 /* Check PHI arguments. */
2843 || TREE_CODE (arg1
) != INTEGER_CST
2844 || wi::to_wide (arg1
) != val
)
2847 /* And insert the popcount/clz/ctz builtin and cast stmt before the
2849 gsi
= gsi_last_bb (cond_bb
);
2852 gsi_from
= gsi_for_stmt (cast
);
2853 gsi_move_before (&gsi_from
, &gsi
);
2854 reset_flow_sensitive_info (gimple_get_lhs (cast
));
2856 gsi_from
= gsi_for_stmt (call
);
2857 if (ifn
== IFN_LAST
|| gimple_call_internal_p (call
))
2858 gsi_move_before (&gsi_from
, &gsi
);
2861 /* For __builtin_c[lt]z* force .C[LT]Z ifn, because only
2862 the latter is well defined at zero. */
2863 call
= gimple_build_call_internal (ifn
, 1, gimple_call_arg (call
, 0));
2864 gimple_call_set_lhs (call
, lhs
);
2865 gsi_insert_before (&gsi
, call
, GSI_SAME_STMT
);
2866 gsi_remove (&gsi_from
, true);
2868 reset_flow_sensitive_info (lhs
);
2870 /* Now update the PHI and remove unneeded bbs. */
2871 replace_phi_edge_with_variable (cond_bb
, e2
, phi
, lhs
);
2875 /* Auxiliary functions to determine the set of memory accesses which
2876 can't trap because they are preceded by accesses to the same memory
2877 portion. We do that for MEM_REFs, so we only need to track
2878 the SSA_NAME of the pointer indirectly referenced. The algorithm
2879 simply is a walk over all instructions in dominator order. When
2880 we see an MEM_REF we determine if we've already seen a same
2881 ref anywhere up to the root of the dominator tree. If we do the
2882 current access can't trap. If we don't see any dominating access
2883 the current access might trap, but might also make later accesses
2884 non-trapping, so we remember it. We need to be careful with loads
2885 or stores, for instance a load might not trap, while a store would,
2886 so if we see a dominating read access this doesn't mean that a later
2887 write access would not trap. Hence we also need to differentiate the
2888 type of access(es) seen.
2890 ??? We currently are very conservative and assume that a load might
2891 trap even if a store doesn't (write-only memory). This probably is
2892 overly conservative.
2894 We currently support a special case that for !TREE_ADDRESSABLE automatic
2895 variables, it could ignore whether something is a load or store because the
2896 local stack should be always writable. */
2898 /* A hash-table of references (MEM_REF/ARRAY_REF/COMPONENT_REF), and in which
2899 basic block an *_REF through it was seen, which would constitute a
2900 no-trap region for same accesses.
2902 Size is needed to support 2 MEM_REFs of different types, like
2903 MEM<double>(s_1) and MEM<long>(s_1), which would compare equal with
2913 /* Hashtable helpers. */
2915 struct refs_hasher
: free_ptr_hash
<ref_to_bb
>
2917 static inline hashval_t
hash (const ref_to_bb
*);
2918 static inline bool equal (const ref_to_bb
*, const ref_to_bb
*);
2921 /* Used for quick clearing of the hash-table when we see calls.
2922 Hash entries with phase < nt_call_phase are invalid. */
2923 static unsigned int nt_call_phase
;
2925 /* The hash function. */
2928 refs_hasher::hash (const ref_to_bb
*n
)
2930 inchash::hash hstate
;
2931 inchash::add_expr (n
->exp
, hstate
, OEP_ADDRESS_OF
);
2932 hstate
.add_hwi (n
->size
);
2933 return hstate
.end ();
2936 /* The equality function of *P1 and *P2. */
2939 refs_hasher::equal (const ref_to_bb
*n1
, const ref_to_bb
*n2
)
2941 return operand_equal_p (n1
->exp
, n2
->exp
, OEP_ADDRESS_OF
)
2942 && n1
->size
== n2
->size
;
2945 class nontrapping_dom_walker
: public dom_walker
2948 nontrapping_dom_walker (cdi_direction direction
, hash_set
<tree
> *ps
)
2949 : dom_walker (direction
), m_nontrapping (ps
), m_seen_refs (128)
2952 edge
before_dom_children (basic_block
) final override
;
2953 void after_dom_children (basic_block
) final override
;
2957 /* We see the expression EXP in basic block BB. If it's an interesting
2958 expression (an MEM_REF through an SSA_NAME) possibly insert the
2959 expression into the set NONTRAP or the hash table of seen expressions.
2960 STORE is true if this expression is on the LHS, otherwise it's on
2962 void add_or_mark_expr (basic_block
, tree
, bool);
2964 hash_set
<tree
> *m_nontrapping
;
2966 /* The hash table for remembering what we've seen. */
2967 hash_table
<refs_hasher
> m_seen_refs
;
2970 /* Called by walk_dominator_tree, when entering the block BB. */
2972 nontrapping_dom_walker::before_dom_children (basic_block bb
)
2976 gimple_stmt_iterator gsi
;
2978 /* If we haven't seen all our predecessors, clear the hash-table. */
2979 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2980 if ((((size_t)e
->src
->aux
) & 2) == 0)
2986 /* Mark this BB as being on the path to dominator root and as visited. */
2987 bb
->aux
= (void*)(1 | 2);
2989 /* And walk the statements in order. */
2990 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2992 gimple
*stmt
= gsi_stmt (gsi
);
2994 if ((gimple_code (stmt
) == GIMPLE_ASM
&& gimple_vdef (stmt
))
2995 || (is_gimple_call (stmt
)
2996 && (!nonfreeing_call_p (stmt
) || !nonbarrier_call_p (stmt
))))
2998 else if (gimple_assign_single_p (stmt
) && !gimple_has_volatile_ops (stmt
))
3000 add_or_mark_expr (bb
, gimple_assign_lhs (stmt
), true);
3001 add_or_mark_expr (bb
, gimple_assign_rhs1 (stmt
), false);
3007 /* Called by walk_dominator_tree, when basic block BB is exited. */
3009 nontrapping_dom_walker::after_dom_children (basic_block bb
)
3011 /* This BB isn't on the path to dominator root anymore. */
3015 /* We see the expression EXP in basic block BB. If it's an interesting
3020 possibly insert the expression into the set NONTRAP or the hash table
3021 of seen expressions. STORE is true if this expression is on the LHS,
3022 otherwise it's on the RHS. */
3024 nontrapping_dom_walker::add_or_mark_expr (basic_block bb
, tree exp
, bool store
)
3028 if ((TREE_CODE (exp
) == MEM_REF
|| TREE_CODE (exp
) == ARRAY_REF
3029 || TREE_CODE (exp
) == COMPONENT_REF
)
3030 && (size
= int_size_in_bytes (TREE_TYPE (exp
))) > 0)
3032 struct ref_to_bb map
;
3034 struct ref_to_bb
*r2bb
;
3035 basic_block found_bb
= 0;
3039 tree base
= get_base_address (exp
);
3040 /* Only record a LOAD of a local variable without address-taken, as
3041 the local stack is always writable. This allows cselim on a STORE
3042 with a dominating LOAD. */
3043 if (!auto_var_p (base
) || TREE_ADDRESSABLE (base
))
3047 /* Try to find the last seen *_REF, which can trap. */
3050 slot
= m_seen_refs
.find_slot (&map
, INSERT
);
3052 if (r2bb
&& r2bb
->phase
>= nt_call_phase
)
3053 found_bb
= r2bb
->bb
;
3055 /* If we've found a trapping *_REF, _and_ it dominates EXP
3056 (it's in a basic block on the path from us to the dominator root)
3057 then we can't trap. */
3058 if (found_bb
&& (((size_t)found_bb
->aux
) & 1) == 1)
3060 m_nontrapping
->add (exp
);
3064 /* EXP might trap, so insert it into the hash table. */
3067 r2bb
->phase
= nt_call_phase
;
3072 r2bb
= XNEW (struct ref_to_bb
);
3073 r2bb
->phase
= nt_call_phase
;
3083 /* This is the entry point of gathering non trapping memory accesses.
3084 It will do a dominator walk over the whole function, and it will
3085 make use of the bb->aux pointers. It returns a set of trees
3086 (the MEM_REFs itself) which can't trap. */
3087 static hash_set
<tree
> *
3088 get_non_trapping (void)
3091 hash_set
<tree
> *nontrap
= new hash_set
<tree
>;
3093 nontrapping_dom_walker (CDI_DOMINATORS
, nontrap
)
3094 .walk (cfun
->cfg
->x_entry_block_ptr
);
3096 clear_aux_for_blocks ();
3100 /* Do the main work of conditional store replacement. We already know
3101 that the recognized pattern looks like so:
3104 if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
3107 fallthrough (edge E0)
3111 We check that MIDDLE_BB contains only one store, that that store
3112 doesn't trap (not via NOTRAP, but via checking if an access to the same
3113 memory location dominates us, or the store is to a local addressable
3114 object) and that the store has a "simple" RHS. */
3117 cond_store_replacement (basic_block middle_bb
, basic_block join_bb
,
3118 edge e0
, edge e1
, hash_set
<tree
> *nontrap
)
3120 gimple
*assign
= last_and_only_stmt (middle_bb
);
3121 tree lhs
, rhs
, name
, name2
;
3124 gimple_stmt_iterator gsi
;
3127 /* Check if middle_bb contains of only one store. */
3129 || !gimple_assign_single_p (assign
)
3130 || gimple_has_volatile_ops (assign
))
3133 /* And no PHI nodes so all uses in the single stmt are also
3134 available where we insert to. */
3135 if (!gimple_seq_empty_p (phi_nodes (middle_bb
)))
3138 locus
= gimple_location (assign
);
3139 lhs
= gimple_assign_lhs (assign
);
3140 rhs
= gimple_assign_rhs1 (assign
);
3141 if ((!REFERENCE_CLASS_P (lhs
)
3143 || !is_gimple_reg_type (TREE_TYPE (lhs
)))
3146 /* Prove that we can move the store down. We could also check
3147 TREE_THIS_NOTRAP here, but in that case we also could move stores,
3148 whose value is not available readily, which we want to avoid. */
3149 if (!nontrap
->contains (lhs
))
3151 /* If LHS is an access to a local variable without address-taken
3152 (or when we allow data races) and known not to trap, we could
3153 always safely move down the store. */
3154 tree base
= get_base_address (lhs
);
3155 if (!auto_var_p (base
)
3156 || (TREE_ADDRESSABLE (base
) && !flag_store_data_races
)
3157 || tree_could_trap_p (lhs
))
3161 /* Now we've checked the constraints, so do the transformation:
3162 1) Remove the single store. */
3163 gsi
= gsi_for_stmt (assign
);
3164 unlink_stmt_vdef (assign
);
3165 gsi_remove (&gsi
, true);
3166 release_defs (assign
);
3168 /* Make both store and load use alias-set zero as we have to
3169 deal with the case of the store being a conditional change
3170 of the dynamic type. */
3171 lhs
= unshare_expr (lhs
);
3173 while (handled_component_p (*basep
))
3174 basep
= &TREE_OPERAND (*basep
, 0);
3175 if (TREE_CODE (*basep
) == MEM_REF
3176 || TREE_CODE (*basep
) == TARGET_MEM_REF
)
3177 TREE_OPERAND (*basep
, 1)
3178 = fold_convert (ptr_type_node
, TREE_OPERAND (*basep
, 1));
3180 *basep
= build2 (MEM_REF
, TREE_TYPE (*basep
),
3181 build_fold_addr_expr (*basep
),
3182 build_zero_cst (ptr_type_node
));
3184 /* 2) Insert a load from the memory of the store to the temporary
3185 on the edge which did not contain the store. */
3186 name
= make_temp_ssa_name (TREE_TYPE (lhs
), NULL
, "cstore");
3187 new_stmt
= gimple_build_assign (name
, lhs
);
3188 gimple_set_location (new_stmt
, locus
);
3189 lhs
= unshare_expr (lhs
);
3191 /* Set the no-warning bit on the rhs of the load to avoid uninit
3193 tree rhs1
= gimple_assign_rhs1 (new_stmt
);
3194 suppress_warning (rhs1
, OPT_Wuninitialized
);
3196 gsi_insert_on_edge (e1
, new_stmt
);
3198 /* 3) Create a PHI node at the join block, with one argument
3199 holding the old RHS, and the other holding the temporary
3200 where we stored the old memory contents. */
3201 name2
= make_temp_ssa_name (TREE_TYPE (lhs
), NULL
, "cstore");
3202 newphi
= create_phi_node (name2
, join_bb
);
3203 add_phi_arg (newphi
, rhs
, e0
, locus
);
3204 add_phi_arg (newphi
, name
, e1
, locus
);
3206 new_stmt
= gimple_build_assign (lhs
, PHI_RESULT (newphi
));
3208 /* 4) Insert that PHI node. */
3209 gsi
= gsi_after_labels (join_bb
);
3210 if (gsi_end_p (gsi
))
3212 gsi
= gsi_last_bb (join_bb
);
3213 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
3216 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
3218 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3220 fprintf (dump_file
, "\nConditional store replacement happened!");
3221 fprintf (dump_file
, "\nReplaced the store with a load.");
3222 fprintf (dump_file
, "\nInserted a new PHI statement in joint block:\n");
3223 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
);
3225 statistics_counter_event (cfun
, "conditional store replacement", 1);
3230 /* Do the main work of conditional store replacement. */
3233 cond_if_else_store_replacement_1 (basic_block then_bb
, basic_block else_bb
,
3234 basic_block join_bb
, gimple
*then_assign
,
3235 gimple
*else_assign
)
3237 tree lhs_base
, lhs
, then_rhs
, else_rhs
, name
;
3238 location_t then_locus
, else_locus
;
3239 gimple_stmt_iterator gsi
;
3243 if (then_assign
== NULL
3244 || !gimple_assign_single_p (then_assign
)
3245 || gimple_clobber_p (then_assign
)
3246 || gimple_has_volatile_ops (then_assign
)
3247 || else_assign
== NULL
3248 || !gimple_assign_single_p (else_assign
)
3249 || gimple_clobber_p (else_assign
)
3250 || gimple_has_volatile_ops (else_assign
))
3253 lhs
= gimple_assign_lhs (then_assign
);
3254 if (!is_gimple_reg_type (TREE_TYPE (lhs
))
3255 || !operand_equal_p (lhs
, gimple_assign_lhs (else_assign
), 0))
3258 lhs_base
= get_base_address (lhs
);
3259 if (lhs_base
== NULL_TREE
3260 || (!DECL_P (lhs_base
) && TREE_CODE (lhs_base
) != MEM_REF
))
3263 then_rhs
= gimple_assign_rhs1 (then_assign
);
3264 else_rhs
= gimple_assign_rhs1 (else_assign
);
3265 then_locus
= gimple_location (then_assign
);
3266 else_locus
= gimple_location (else_assign
);
3268 /* Now we've checked the constraints, so do the transformation:
3269 1) Remove the stores. */
3270 gsi
= gsi_for_stmt (then_assign
);
3271 unlink_stmt_vdef (then_assign
);
3272 gsi_remove (&gsi
, true);
3273 release_defs (then_assign
);
3275 gsi
= gsi_for_stmt (else_assign
);
3276 unlink_stmt_vdef (else_assign
);
3277 gsi_remove (&gsi
, true);
3278 release_defs (else_assign
);
3280 /* 2) Create a PHI node at the join block, with one argument
3281 holding the old RHS, and the other holding the temporary
3282 where we stored the old memory contents. */
3283 name
= make_temp_ssa_name (TREE_TYPE (lhs
), NULL
, "cstore");
3284 newphi
= create_phi_node (name
, join_bb
);
3285 add_phi_arg (newphi
, then_rhs
, EDGE_SUCC (then_bb
, 0), then_locus
);
3286 add_phi_arg (newphi
, else_rhs
, EDGE_SUCC (else_bb
, 0), else_locus
);
3288 new_stmt
= gimple_build_assign (lhs
, PHI_RESULT (newphi
));
3290 /* 3) Insert that PHI node. */
3291 gsi
= gsi_after_labels (join_bb
);
3292 if (gsi_end_p (gsi
))
3294 gsi
= gsi_last_bb (join_bb
);
3295 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
3298 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
3300 statistics_counter_event (cfun
, "if-then-else store replacement", 1);
3305 /* Return the single store in BB with VDEF or NULL if there are
3306 other stores in the BB or loads following the store. */
3309 single_trailing_store_in_bb (basic_block bb
, tree vdef
)
3311 if (SSA_NAME_IS_DEFAULT_DEF (vdef
))
3313 gimple
*store
= SSA_NAME_DEF_STMT (vdef
);
3314 if (gimple_bb (store
) != bb
3315 || gimple_code (store
) == GIMPLE_PHI
)
3318 /* Verify there is no other store in this BB. */
3319 if (!SSA_NAME_IS_DEFAULT_DEF (gimple_vuse (store
))
3320 && gimple_bb (SSA_NAME_DEF_STMT (gimple_vuse (store
))) == bb
3321 && gimple_code (SSA_NAME_DEF_STMT (gimple_vuse (store
))) != GIMPLE_PHI
)
3324 /* Verify there is no load or store after the store. */
3325 use_operand_p use_p
;
3326 imm_use_iterator imm_iter
;
3327 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_vdef (store
))
3328 if (USE_STMT (use_p
) != store
3329 && gimple_bb (USE_STMT (use_p
)) == bb
)
3335 /* Conditional store replacement. We already know
3336 that the recognized pattern looks like so:
3339 if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
3349 fallthrough (edge E0)
3353 We check that it is safe to sink the store to JOIN_BB by verifying that
3354 there are no read-after-write or write-after-write dependencies in
3355 THEN_BB and ELSE_BB. */
3358 cond_if_else_store_replacement (basic_block then_bb
, basic_block else_bb
,
3359 basic_block join_bb
)
3361 vec
<data_reference_p
> then_datarefs
, else_datarefs
;
3362 vec
<ddr_p
> then_ddrs
, else_ddrs
;
3363 gimple
*then_store
, *else_store
;
3364 bool found
, ok
= false, res
;
3365 struct data_dependence_relation
*ddr
;
3366 data_reference_p then_dr
, else_dr
;
3368 tree then_lhs
, else_lhs
;
3369 basic_block blocks
[3];
3371 /* Handle the case with single store in THEN_BB and ELSE_BB. That is
3372 cheap enough to always handle as it allows us to elide dependence
3375 for (gphi_iterator si
= gsi_start_phis (join_bb
); !gsi_end_p (si
);
3377 if (virtual_operand_p (gimple_phi_result (si
.phi ())))
3384 tree then_vdef
= PHI_ARG_DEF_FROM_EDGE (vphi
, single_succ_edge (then_bb
));
3385 tree else_vdef
= PHI_ARG_DEF_FROM_EDGE (vphi
, single_succ_edge (else_bb
));
3386 gimple
*then_assign
= single_trailing_store_in_bb (then_bb
, then_vdef
);
3389 gimple
*else_assign
= single_trailing_store_in_bb (else_bb
, else_vdef
);
3391 return cond_if_else_store_replacement_1 (then_bb
, else_bb
, join_bb
,
3392 then_assign
, else_assign
);
3395 /* If either vectorization or if-conversion is disabled then do
3396 not sink any stores. */
3397 if (param_max_stores_to_sink
== 0
3398 || (!flag_tree_loop_vectorize
&& !flag_tree_slp_vectorize
)
3399 || !flag_tree_loop_if_convert
)
3402 /* Find data references. */
3403 then_datarefs
.create (1);
3404 else_datarefs
.create (1);
3405 if ((find_data_references_in_bb (NULL
, then_bb
, &then_datarefs
)
3407 || !then_datarefs
.length ()
3408 || (find_data_references_in_bb (NULL
, else_bb
, &else_datarefs
)
3410 || !else_datarefs
.length ())
3412 free_data_refs (then_datarefs
);
3413 free_data_refs (else_datarefs
);
3417 /* Find pairs of stores with equal LHS. */
3418 auto_vec
<gimple
*, 1> then_stores
, else_stores
;
3419 FOR_EACH_VEC_ELT (then_datarefs
, i
, then_dr
)
3421 if (DR_IS_READ (then_dr
))
3424 then_store
= DR_STMT (then_dr
);
3425 then_lhs
= gimple_get_lhs (then_store
);
3426 if (then_lhs
== NULL_TREE
)
3430 FOR_EACH_VEC_ELT (else_datarefs
, j
, else_dr
)
3432 if (DR_IS_READ (else_dr
))
3435 else_store
= DR_STMT (else_dr
);
3436 else_lhs
= gimple_get_lhs (else_store
);
3437 if (else_lhs
== NULL_TREE
)
3440 if (operand_equal_p (then_lhs
, else_lhs
, 0))
3450 then_stores
.safe_push (then_store
);
3451 else_stores
.safe_push (else_store
);
3454 /* No pairs of stores found. */
3455 if (!then_stores
.length ()
3456 || then_stores
.length () > (unsigned) param_max_stores_to_sink
)
3458 free_data_refs (then_datarefs
);
3459 free_data_refs (else_datarefs
);
3463 /* Compute and check data dependencies in both basic blocks. */
3464 then_ddrs
.create (1);
3465 else_ddrs
.create (1);
3466 if (!compute_all_dependences (then_datarefs
, &then_ddrs
,
3468 || !compute_all_dependences (else_datarefs
, &else_ddrs
,
3471 free_dependence_relations (then_ddrs
);
3472 free_dependence_relations (else_ddrs
);
3473 free_data_refs (then_datarefs
);
3474 free_data_refs (else_datarefs
);
3477 blocks
[0] = then_bb
;
3478 blocks
[1] = else_bb
;
3479 blocks
[2] = join_bb
;
3480 renumber_gimple_stmt_uids_in_blocks (blocks
, 3);
3482 /* Check that there are no read-after-write or write-after-write dependencies
3484 FOR_EACH_VEC_ELT (then_ddrs
, i
, ddr
)
3486 struct data_reference
*dra
= DDR_A (ddr
);
3487 struct data_reference
*drb
= DDR_B (ddr
);
3489 if (DDR_ARE_DEPENDENT (ddr
) != chrec_known
3490 && ((DR_IS_READ (dra
) && DR_IS_WRITE (drb
)
3491 && gimple_uid (DR_STMT (dra
)) > gimple_uid (DR_STMT (drb
)))
3492 || (DR_IS_READ (drb
) && DR_IS_WRITE (dra
)
3493 && gimple_uid (DR_STMT (drb
)) > gimple_uid (DR_STMT (dra
)))
3494 || (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))))
3496 free_dependence_relations (then_ddrs
);
3497 free_dependence_relations (else_ddrs
);
3498 free_data_refs (then_datarefs
);
3499 free_data_refs (else_datarefs
);
3504 /* Check that there are no read-after-write or write-after-write dependencies
3506 FOR_EACH_VEC_ELT (else_ddrs
, i
, ddr
)
3508 struct data_reference
*dra
= DDR_A (ddr
);
3509 struct data_reference
*drb
= DDR_B (ddr
);
3511 if (DDR_ARE_DEPENDENT (ddr
) != chrec_known
3512 && ((DR_IS_READ (dra
) && DR_IS_WRITE (drb
)
3513 && gimple_uid (DR_STMT (dra
)) > gimple_uid (DR_STMT (drb
)))
3514 || (DR_IS_READ (drb
) && DR_IS_WRITE (dra
)
3515 && gimple_uid (DR_STMT (drb
)) > gimple_uid (DR_STMT (dra
)))
3516 || (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))))
3518 free_dependence_relations (then_ddrs
);
3519 free_dependence_relations (else_ddrs
);
3520 free_data_refs (then_datarefs
);
3521 free_data_refs (else_datarefs
);
3526 /* Sink stores with same LHS. */
3527 FOR_EACH_VEC_ELT (then_stores
, i
, then_store
)
3529 else_store
= else_stores
[i
];
3530 res
= cond_if_else_store_replacement_1 (then_bb
, else_bb
, join_bb
,
3531 then_store
, else_store
);
3535 free_dependence_relations (then_ddrs
);
3536 free_dependence_relations (else_ddrs
);
3537 free_data_refs (then_datarefs
);
3538 free_data_refs (else_datarefs
);
3543 /* Return TRUE if STMT has a VUSE whose corresponding VDEF is in BB. */
3546 local_mem_dependence (gimple
*stmt
, basic_block bb
)
3548 tree vuse
= gimple_vuse (stmt
);
3554 def
= SSA_NAME_DEF_STMT (vuse
);
3555 return (def
&& gimple_bb (def
) == bb
);
3558 /* Given a "diamond" control-flow pattern where BB0 tests a condition,
3559 BB1 and BB2 are "then" and "else" blocks dependent on this test,
3560 and BB3 rejoins control flow following BB1 and BB2, look for
3561 opportunities to hoist loads as follows. If BB3 contains a PHI of
3562 two loads, one each occurring in BB1 and BB2, and the loads are
3563 provably of adjacent fields in the same structure, then move both
3564 loads into BB0. Of course this can only be done if there are no
3565 dependencies preventing such motion.
3567 One of the hoisted loads will always be speculative, so the
3568 transformation is currently conservative:
3570 - The fields must be strictly adjacent.
3571 - The two fields must occupy a single memory block that is
3572 guaranteed to not cross a page boundary.
3574 The last is difficult to prove, as such memory blocks should be
3575 aligned on the minimum of the stack alignment boundary and the
3576 alignment guaranteed by heap allocation interfaces. Thus we rely
3577 on a parameter for the alignment value.
3579 Provided a good value is used for the last case, the first
3580 restriction could possibly be relaxed. */
3583 hoist_adjacent_loads (basic_block bb0
, basic_block bb1
,
3584 basic_block bb2
, basic_block bb3
)
3586 int param_align
= param_l1_cache_line_size
;
3587 unsigned param_align_bits
= (unsigned) (param_align
* BITS_PER_UNIT
);
3590 /* Walk the phis in bb3 looking for an opportunity. We are looking
3591 for phis of two SSA names, one each of which is defined in bb1 and
3593 for (gsi
= gsi_start_phis (bb3
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3595 gphi
*phi_stmt
= gsi
.phi ();
3596 gimple
*def1
, *def2
;
3597 tree arg1
, arg2
, ref1
, ref2
, field1
, field2
;
3598 tree tree_offset1
, tree_offset2
, tree_size2
, next
;
3599 int offset1
, offset2
, size2
;
3601 gimple_stmt_iterator gsi2
;
3602 basic_block bb_for_def1
, bb_for_def2
;
3604 if (gimple_phi_num_args (phi_stmt
) != 2
3605 || virtual_operand_p (gimple_phi_result (phi_stmt
)))
3608 arg1
= gimple_phi_arg_def (phi_stmt
, 0);
3609 arg2
= gimple_phi_arg_def (phi_stmt
, 1);
3611 if (TREE_CODE (arg1
) != SSA_NAME
3612 || TREE_CODE (arg2
) != SSA_NAME
3613 || SSA_NAME_IS_DEFAULT_DEF (arg1
)
3614 || SSA_NAME_IS_DEFAULT_DEF (arg2
))
3617 def1
= SSA_NAME_DEF_STMT (arg1
);
3618 def2
= SSA_NAME_DEF_STMT (arg2
);
3620 if ((gimple_bb (def1
) != bb1
|| gimple_bb (def2
) != bb2
)
3621 && (gimple_bb (def2
) != bb1
|| gimple_bb (def1
) != bb2
))
3624 /* Check the mode of the arguments to be sure a conditional move
3625 can be generated for it. */
3626 if (optab_handler (movcc_optab
, TYPE_MODE (TREE_TYPE (arg1
)))
3627 == CODE_FOR_nothing
)
3630 /* Both statements must be assignments whose RHS is a COMPONENT_REF. */
3631 if (!gimple_assign_single_p (def1
)
3632 || !gimple_assign_single_p (def2
)
3633 || gimple_has_volatile_ops (def1
)
3634 || gimple_has_volatile_ops (def2
))
3637 ref1
= gimple_assign_rhs1 (def1
);
3638 ref2
= gimple_assign_rhs1 (def2
);
3640 if (TREE_CODE (ref1
) != COMPONENT_REF
3641 || TREE_CODE (ref2
) != COMPONENT_REF
)
3644 /* The zeroth operand of the two component references must be
3645 identical. It is not sufficient to compare get_base_address of
3646 the two references, because this could allow for different
3647 elements of the same array in the two trees. It is not safe to
3648 assume that the existence of one array element implies the
3649 existence of a different one. */
3650 if (!operand_equal_p (TREE_OPERAND (ref1
, 0), TREE_OPERAND (ref2
, 0), 0))
3653 field1
= TREE_OPERAND (ref1
, 1);
3654 field2
= TREE_OPERAND (ref2
, 1);
3656 /* Check for field adjacency, and ensure field1 comes first. */
3657 for (next
= DECL_CHAIN (field1
);
3658 next
&& TREE_CODE (next
) != FIELD_DECL
;
3659 next
= DECL_CHAIN (next
))
3664 for (next
= DECL_CHAIN (field2
);
3665 next
&& TREE_CODE (next
) != FIELD_DECL
;
3666 next
= DECL_CHAIN (next
))
3672 std::swap (field1
, field2
);
3673 std::swap (def1
, def2
);
3676 bb_for_def1
= gimple_bb (def1
);
3677 bb_for_def2
= gimple_bb (def2
);
3679 /* Check for proper alignment of the first field. */
3680 tree_offset1
= bit_position (field1
);
3681 tree_offset2
= bit_position (field2
);
3682 tree_size2
= DECL_SIZE (field2
);
3684 if (!tree_fits_uhwi_p (tree_offset1
)
3685 || !tree_fits_uhwi_p (tree_offset2
)
3686 || !tree_fits_uhwi_p (tree_size2
))
3689 offset1
= tree_to_uhwi (tree_offset1
);
3690 offset2
= tree_to_uhwi (tree_offset2
);
3691 size2
= tree_to_uhwi (tree_size2
);
3692 align1
= DECL_ALIGN (field1
) % param_align_bits
;
3694 if (offset1
% BITS_PER_UNIT
!= 0)
3697 /* For profitability, the two field references should fit within
3698 a single cache line. */
3699 if (align1
+ offset2
- offset1
+ size2
> param_align_bits
)
3702 /* The two expressions cannot be dependent upon vdefs defined
3704 if (local_mem_dependence (def1
, bb_for_def1
)
3705 || local_mem_dependence (def2
, bb_for_def2
))
3708 /* The conditions are satisfied; hoist the loads from bb1 and bb2 into
3709 bb0. We hoist the first one first so that a cache miss is handled
3710 efficiently regardless of hardware cache-fill policy. */
3711 gsi2
= gsi_for_stmt (def1
);
3712 gsi_move_to_bb_end (&gsi2
, bb0
);
3713 gsi2
= gsi_for_stmt (def2
);
3714 gsi_move_to_bb_end (&gsi2
, bb0
);
3715 statistics_counter_event (cfun
, "hoisted loads", 1);
3717 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3720 "\nHoisting adjacent loads from %d and %d into %d: \n",
3721 bb_for_def1
->index
, bb_for_def2
->index
, bb0
->index
);
3722 print_gimple_stmt (dump_file
, def1
, 0, TDF_VOPS
|TDF_MEMSYMS
);
3723 print_gimple_stmt (dump_file
, def2
, 0, TDF_VOPS
|TDF_MEMSYMS
);
3728 /* Determine whether we should attempt to hoist adjacent loads out of
3729 diamond patterns in pass_phiopt. Always hoist loads if
3730 -fhoist-adjacent-loads is specified and the target machine has
3731 both a conditional move instruction and a defined cache line size. */
3734 gate_hoist_loads (void)
3736 return (flag_hoist_adjacent_loads
== 1
3737 && param_l1_cache_line_size
3738 && HAVE_conditional_move
);
3741 /* This pass tries to replaces an if-then-else block with an
3742 assignment. We have different kinds of transformations.
3743 Some of these transformations are also performed by the ifcvt
3746 PHI-OPT using Match-and-simplify infrastructure
3747 -----------------------
3749 The PHI-OPT pass will try to use match-and-simplify infrastructure
3750 (gimple_simplify) to do transformations. This is implemented in
3751 match_simplify_replacement.
3753 The way it works is it replaces:
3755 if (cond) goto bb2; else goto bb1;
3758 x = PHI <a (bb1), b (bb0), ...>;
3760 with a statement if it gets simplified from `cond ? b : a`.
3765 x = PHI <a (bb1), x1 (bb0), ...>;
3766 Bb1 might be removed as it becomes unreachable when doing the replacement.
3767 Though bb1 does not have to be considered a forwarding basic block from bb0.
3769 Will try to see if `(!cond) ? a : b` gets simplified (iff !cond simplifies);
3770 this is done not to have an explosion of patterns in match.pd.
3771 Note bb1 does not need to be completely empty, it can contain
3772 one statement which is known not to trap.
3774 It also can handle the case where we have two forwarding bbs (diamond):
3776 if (cond) goto bb2; else goto bb1;
3780 x = PHI <a (bb1), b (bb2), ...>;
3781 And that is replaced with a statement if it is simplified
3782 from `cond ? b : a`.
3783 Again bb1 and bb2 does not have to be completely empty but
3784 each can contain one statement which is known not to trap.
3785 But in this case bb1/bb2 can only be forwarding basic blocks.
3787 This fully replaces the old "Conditional Replacement",
3788 "ABS Replacement" transformations as they are now
3789 implmeneted in match.pd.
3790 Some parts of the "MIN/MAX Replacement" are re-implemented in match.pd.
3795 This transformation, implemented in value_replacement, replaces
3798 if (a != b) goto bb2; else goto bb1;
3801 x = PHI <a (bb1), b (bb0), ...>;
3807 x = PHI <b (bb0), ...>;
3809 This opportunity can sometimes occur as a result of other
3813 Another case caught by value replacement looks like this:
3819 if (t3 != 0) goto bb1; else goto bb2;
3835 This transformation, minmax_replacement replaces
3838 if (a <= b) goto bb2; else goto bb1;
3841 x = PHI <b (bb1), a (bb0), ...>;
3846 x' = MIN_EXPR (a, b)
3848 x = PHI <x' (bb0), ...>;
3850 A similar transformation is done for MAX_EXPR.
3853 This pass also performs a fifth transformation of a slightly different
3856 Factor operations in COND_EXPR
3857 ------------------------------
3859 This transformation factors the unary operations out of COND_EXPR with
3860 factor_out_conditional_operation.
3863 if (a <= CST) goto <bb 3>; else goto <bb 4>;
3867 tmp = PHI <tmp, CST>
3870 if (a <= CST) goto <bb 3>; else goto <bb 4>;
3876 Adjacent Load Hoisting
3877 ----------------------
3879 This transformation replaces
3882 if (...) goto bb2; else goto bb1;
3884 x1 = (<expr>).field1;
3887 x2 = (<expr>).field2;
3894 x1 = (<expr>).field1;
3895 x2 = (<expr>).field2;
3896 if (...) goto bb2; else goto bb1;
3903 The purpose of this transformation is to enable generation of conditional
3904 move instructions such as Intel CMOVE or PowerPC ISEL. Because one of
3905 the loads is speculative, the transformation is restricted to very
3906 specific cases to avoid introducing a page fault. We are looking for
3914 where left and right are typically adjacent pointers in a tree structure. */
3918 const pass_data pass_data_phiopt
=
3920 GIMPLE_PASS
, /* type */
3921 "phiopt", /* name */
3922 OPTGROUP_NONE
, /* optinfo_flags */
3923 TV_TREE_PHIOPT
, /* tv_id */
3924 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3925 0, /* properties_provided */
3926 0, /* properties_destroyed */
3927 0, /* todo_flags_start */
3928 0, /* todo_flags_finish */
3931 class pass_phiopt
: public gimple_opt_pass
3934 pass_phiopt (gcc::context
*ctxt
)
3935 : gimple_opt_pass (pass_data_phiopt
, ctxt
), early_p (false)
3938 /* opt_pass methods: */
3939 opt_pass
* clone () final override
{ return new pass_phiopt (m_ctxt
); }
3940 void set_pass_param (unsigned n
, bool param
) final override
3942 gcc_assert (n
== 0);
3945 bool gate (function
*) final override
{ return flag_ssa_phiopt
; }
3946 unsigned int execute (function
*) final override
;
3950 }; // class pass_phiopt
3955 make_pass_phiopt (gcc::context
*ctxt
)
3957 return new pass_phiopt (ctxt
);
3961 pass_phiopt::execute (function
*)
3963 bool do_hoist_loads
= !early_p
? gate_hoist_loads () : false;
3965 basic_block
*bb_order
;
3967 bool cfgchanged
= false;
3969 calculate_dominance_info (CDI_DOMINATORS
);
3971 /* Search every basic block for COND_EXPR we may be able to optimize.
3973 We walk the blocks in order that guarantees that a block with
3974 a single predecessor is processed before the predecessor.
3975 This ensures that we collapse inner ifs before visiting the
3976 outer ones, and also that we do not try to visit a removed
3978 bb_order
= single_pred_before_succ_order ();
3979 n
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
;
3981 for (i
= 0; i
< n
; i
++)
3984 basic_block bb1
, bb2
;
3987 bool diamond_p
= false;
3991 /* Check to see if the last statement is a GIMPLE_COND. */
3992 gcond
*cond_stmt
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (bb
));
3996 e1
= EDGE_SUCC (bb
, 0);
3998 e2
= EDGE_SUCC (bb
, 1);
4001 /* We cannot do the optimization on abnormal edges. */
4002 if ((e1
->flags
& EDGE_ABNORMAL
) != 0
4003 || (e2
->flags
& EDGE_ABNORMAL
) != 0)
4006 /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
4007 if (EDGE_COUNT (bb1
->succs
) == 0
4008 || EDGE_COUNT (bb2
->succs
) == 0)
4011 /* Find the bb which is the fall through to the other. */
4012 if (EDGE_SUCC (bb1
, 0)->dest
== bb2
)
4014 else if (EDGE_SUCC (bb2
, 0)->dest
== bb1
)
4016 std::swap (bb1
, bb2
);
4019 else if (EDGE_SUCC (bb1
, 0)->dest
== EDGE_SUCC (bb2
, 0)->dest
4020 && single_succ_p (bb2
))
4023 e2
= EDGE_SUCC (bb2
, 0);
4024 /* Make sure bb2 is just a fall through. */
4025 if ((e2
->flags
& EDGE_FALLTHRU
) == 0)
4031 e1
= EDGE_SUCC (bb1
, 0);
4033 /* Make sure that bb1 is just a fall through. */
4034 if (!single_succ_p (bb1
)
4035 || (e1
->flags
& EDGE_FALLTHRU
) == 0)
4040 basic_block bb3
= e1
->dest
;
4042 if (!single_pred_p (bb1
)
4043 || !single_pred_p (bb2
))
4047 && !FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt
)))
4048 && EDGE_COUNT (bb
->succs
) == 2
4049 && EDGE_COUNT (bb3
->preds
) == 2
4050 /* If one edge or the other is dominant, a conditional move
4051 is likely to perform worse than the well-predicted branch. */
4052 && !predictable_edge_p (EDGE_SUCC (bb
, 0))
4053 && !predictable_edge_p (EDGE_SUCC (bb
, 1)))
4054 hoist_adjacent_loads (bb
, bb1
, bb2
, bb3
);
4057 gimple_stmt_iterator gsi
;
4058 bool candorest
= true;
4060 /* Check that we're looking for nested phis. */
4061 basic_block merge
= diamond_p
? EDGE_SUCC (bb2
, 0)->dest
: bb2
;
4062 gimple_seq phis
= phi_nodes (merge
);
4064 /* Value replacement can work with more than one PHI
4065 so try that first. */
4066 if (!early_p
&& !diamond_p
)
4067 for (gsi
= gsi_start (phis
); !gsi_end_p (gsi
); gsi_next (&gsi
))
4069 phi
= as_a
<gphi
*> (gsi_stmt (gsi
));
4070 arg0
= gimple_phi_arg_def (phi
, e1
->dest_idx
);
4071 arg1
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
4072 if (value_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
) == 2)
4083 phi
= single_non_singleton_phi_for_edges (phis
, e1
, e2
);
4087 arg0
= gimple_phi_arg_def (phi
, e1
->dest_idx
);
4088 arg1
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
4090 /* Something is wrong if we cannot find the arguments in the PHI
4092 gcc_assert (arg0
!= NULL_TREE
&& arg1
!= NULL_TREE
);
4094 if (single_pred_p (bb1
)
4095 && EDGE_COUNT (merge
->preds
) == 2)
4101 /* factor_out_conditional_operation may create a new PHI in
4102 BB2 and eliminate an existing PHI in BB2. Recompute values
4103 that may be affected by that change. */
4104 arg0
= gimple_phi_arg_def (phi
, e1
->dest_idx
);
4105 arg1
= gimple_phi_arg_def (phi
, e2
->dest_idx
);
4106 gcc_assert (arg0
!= NULL_TREE
&& arg1
!= NULL_TREE
);
4107 newphi
= factor_out_conditional_operation (e1
, e2
, phi
,
4113 /* Do the replacement of conditional if it can be done. */
4114 if (match_simplify_replacement (bb
, bb1
, bb2
, e1
, e2
, phi
,
4115 arg0
, arg1
, early_p
, diamond_p
))
4119 && single_pred_p (bb1
)
4120 && cond_removal_in_builtin_zero_pattern (bb
, bb1
, e1
, e2
,
4123 else if (minmax_replacement (bb
, bb1
, bb2
, e1
, e2
, phi
, arg0
, arg1
,
4126 else if (single_pred_p (bb1
)
4128 && spaceship_replacement (bb
, bb1
, e1
, e2
, phi
, arg0
, arg1
))
4135 return TODO_cleanup_cfg
;
4139 /* This pass tries to transform conditional stores into unconditional
4140 ones, enabling further simplifications with the simpler then and else
4141 blocks. In particular it replaces this:
4144 if (cond) goto bb2; else goto bb1;
4152 if (cond) goto bb1; else goto bb2;
4156 condtmp = PHI <RHS, condtmp'>
4159 This transformation can only be done under several constraints,
4160 documented below. It also replaces:
4163 if (cond) goto bb2; else goto bb1;
4174 if (cond) goto bb3; else goto bb1;
4177 condtmp = PHI <RHS1, RHS2>
4182 const pass_data pass_data_cselim
=
4184 GIMPLE_PASS
, /* type */
4185 "cselim", /* name */
4186 OPTGROUP_NONE
, /* optinfo_flags */
4187 TV_TREE_PHIOPT
, /* tv_id */
4188 ( PROP_cfg
| PROP_ssa
), /* properties_required */
4189 0, /* properties_provided */
4190 0, /* properties_destroyed */
4191 0, /* todo_flags_start */
4192 0, /* todo_flags_finish */
4195 class pass_cselim
: public gimple_opt_pass
4198 pass_cselim (gcc::context
*ctxt
)
4199 : gimple_opt_pass (pass_data_cselim
, ctxt
)
4202 /* opt_pass methods: */
4203 bool gate (function
*) final override
{ return flag_tree_cselim
; }
4204 unsigned int execute (function
*) final override
;
4206 }; // class pass_cselim
4211 make_pass_cselim (gcc::context
*ctxt
)
4213 return new pass_cselim (ctxt
);
4217 pass_cselim::execute (function
*)
4220 basic_block
*bb_order
;
4222 bool cfgchanged
= false;
4223 hash_set
<tree
> *nontrap
= 0;
4226 /* ??? We are not interested in loop related info, but the following
4227 will create it, ICEing as we didn't init loops with pre-headers.
4228 An interfacing issue of find_data_references_in_bb. */
4229 loop_optimizer_init (LOOPS_NORMAL
);
4232 calculate_dominance_info (CDI_DOMINATORS
);
4234 /* Calculate the set of non-trapping memory accesses. */
4235 nontrap
= get_non_trapping ();
4237 /* Search every basic block for COND_EXPR we may be able to optimize.
4239 We walk the blocks in order that guarantees that a block with
4240 a single predecessor is processed before the predecessor.
4241 This ensures that we collapse inner ifs before visiting the
4242 outer ones, and also that we do not try to visit a removed
4244 bb_order
= single_pred_before_succ_order ();
4245 n
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
;
4247 for (i
= 0; i
< n
; i
++)
4249 basic_block bb1
, bb2
;
4251 bool diamond_p
= false;
4255 /* Check to see if the last statement is a GIMPLE_COND. */
4256 gcond
*cond_stmt
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (bb
));
4260 e1
= EDGE_SUCC (bb
, 0);
4262 e2
= EDGE_SUCC (bb
, 1);
4265 /* We cannot do the optimization on abnormal edges. */
4266 if ((e1
->flags
& EDGE_ABNORMAL
) != 0
4267 || (e2
->flags
& EDGE_ABNORMAL
) != 0)
4270 /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
4271 if (EDGE_COUNT (bb1
->succs
) == 0
4272 || EDGE_COUNT (bb2
->succs
) == 0)
4275 /* Find the bb which is the fall through to the other. */
4276 if (EDGE_SUCC (bb1
, 0)->dest
== bb2
)
4278 else if (EDGE_SUCC (bb2
, 0)->dest
== bb1
)
4280 std::swap (bb1
, bb2
);
4283 else if (EDGE_SUCC (bb1
, 0)->dest
== EDGE_SUCC (bb2
, 0)->dest
4284 && single_succ_p (bb2
))
4287 e2
= EDGE_SUCC (bb2
, 0);
4288 /* Make sure bb2 is just a fall through. */
4289 if ((e2
->flags
& EDGE_FALLTHRU
) == 0)
4295 e1
= EDGE_SUCC (bb1
, 0);
4297 /* Make sure that bb1 is just a fall through. */
4298 if (!single_succ_p (bb1
)
4299 || (e1
->flags
& EDGE_FALLTHRU
) == 0)
4304 basic_block bb3
= e1
->dest
;
4306 /* Only handle sinking of store from 2 bbs only,
4307 The middle bbs don't need to come from the
4308 if always since we are sinking rather than
4310 if (EDGE_COUNT (bb3
->preds
) != 2)
4312 if (cond_if_else_store_replacement (bb1
, bb2
, bb3
))
4317 /* Also make sure that bb1 only have one predecessor and that it
4319 if (!single_pred_p (bb1
)
4320 || single_pred (bb1
) != bb
)
4323 /* bb1 is the middle block, bb2 the join block, bb the split block,
4324 e1 the fallthrough edge from bb1 to bb2. We can't do the
4325 optimization if the join block has more than two predecessors. */
4326 if (EDGE_COUNT (bb2
->preds
) > 2)
4328 if (cond_store_replacement (bb1
, bb2
, e1
, e2
, nontrap
))
4335 /* If the CFG has changed, we should cleanup the CFG. */
4338 /* In cond-store replacement we have added some loads on edges
4339 and new VOPS (as we moved the store, and created a load). */
4340 gsi_commit_edge_inserts ();
4341 todo
= TODO_cleanup_cfg
| TODO_update_ssa_only_virtuals
;
4344 loop_optimizer_finalize ();