c, c++: attribute format on a ctor with a vbase [PR101833, PR47634]
[official-gcc.git] / gcc / tree-ssa-phiopt.cc
blob8c9c46d41f1957ea2c0727bd7eba28cee5ce1218
1 /* Optimization of PHI nodes by converting them into straightline code.
2 Copyright (C) 2004-2022 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
9 later version.
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
14 for more details.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "insn-codes.h"
25 #include "rtl.h"
26 #include "tree.h"
27 #include "gimple.h"
28 #include "cfghooks.h"
29 #include "tree-pass.h"
30 #include "ssa.h"
31 #include "tree-ssa.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"
37 #include "cfganal.h"
38 #include "gimplify.h"
39 #include "gimple-iterator.h"
40 #include "gimplify-me.h"
41 #include "tree-cfg.h"
42 #include "tree-dfa.h"
43 #include "domwalk.h"
44 #include "cfgloop.h"
45 #include "tree-data-ref.h"
46 #include "tree-scalar-evolution.h"
47 #include "tree-inline.h"
48 #include "case-cfn-macros.h"
49 #include "tree-eh.h"
50 #include "gimple-fold.h"
51 #include "internal-fn.h"
52 #include "gimple-range.h"
53 #include "gimple-match.h"
54 #include "dbgcnt.h"
55 #include "tree-ssa-propagate.h"
57 static unsigned int tree_ssa_phiopt_worker (bool, bool, bool);
58 static bool two_value_replacement (basic_block, basic_block, edge, gphi *,
59 tree, tree);
60 static bool match_simplify_replacement (basic_block, basic_block,
61 edge, edge, gphi *, tree, tree, bool);
62 static gphi *factor_out_conditional_conversion (edge, edge, gphi *, tree, tree,
63 gimple *);
64 static int value_replacement (basic_block, basic_block,
65 edge, edge, gphi *, tree, tree);
66 static bool minmax_replacement (basic_block, basic_block,
67 edge, edge, gphi *, tree, tree);
68 static bool spaceship_replacement (basic_block, basic_block,
69 edge, edge, gphi *, tree, tree);
70 static bool cond_removal_in_builtin_zero_pattern (basic_block, basic_block,
71 edge, edge, gphi *,
72 tree, tree);
73 static bool cond_store_replacement (basic_block, basic_block, edge, edge,
74 hash_set<tree> *);
75 static bool cond_if_else_store_replacement (basic_block, basic_block, basic_block);
76 static hash_set<tree> * get_non_trapping ();
77 static void replace_phi_edge_with_variable (basic_block, edge, gphi *, tree);
78 static void hoist_adjacent_loads (basic_block, basic_block,
79 basic_block, basic_block);
80 static bool gate_hoist_loads (void);
82 /* This pass tries to transform conditional stores into unconditional
83 ones, enabling further simplifications with the simpler then and else
84 blocks. In particular it replaces this:
86 bb0:
87 if (cond) goto bb2; else goto bb1;
88 bb1:
89 *p = RHS;
90 bb2:
92 with
94 bb0:
95 if (cond) goto bb1; else goto bb2;
96 bb1:
97 condtmp' = *p;
98 bb2:
99 condtmp = PHI <RHS, condtmp'>
100 *p = condtmp;
102 This transformation can only be done under several constraints,
103 documented below. It also replaces:
105 bb0:
106 if (cond) goto bb2; else goto bb1;
107 bb1:
108 *p = RHS1;
109 goto bb3;
110 bb2:
111 *p = RHS2;
112 bb3:
114 with
116 bb0:
117 if (cond) goto bb3; else goto bb1;
118 bb1:
119 bb3:
120 condtmp = PHI <RHS1, RHS2>
121 *p = condtmp; */
123 static unsigned int
124 tree_ssa_cs_elim (void)
126 unsigned todo;
127 /* ??? We are not interested in loop related info, but the following
128 will create it, ICEing as we didn't init loops with pre-headers.
129 An interfacing issue of find_data_references_in_bb. */
130 loop_optimizer_init (LOOPS_NORMAL);
131 scev_initialize ();
132 todo = tree_ssa_phiopt_worker (true, false, false);
133 scev_finalize ();
134 loop_optimizer_finalize ();
135 return todo;
138 /* Return the singleton PHI in the SEQ of PHIs for edges E0 and E1. */
140 static gphi *
141 single_non_singleton_phi_for_edges (gimple_seq seq, edge e0, edge e1)
143 gimple_stmt_iterator i;
144 gphi *phi = NULL;
145 if (gimple_seq_singleton_p (seq))
146 return as_a <gphi *> (gsi_stmt (gsi_start (seq)));
147 for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
149 gphi *p = as_a <gphi *> (gsi_stmt (i));
150 /* If the PHI arguments are equal then we can skip this PHI. */
151 if (operand_equal_for_phi_arg_p (gimple_phi_arg_def (p, e0->dest_idx),
152 gimple_phi_arg_def (p, e1->dest_idx)))
153 continue;
155 /* If we already have a PHI that has the two edge arguments are
156 different, then return it is not a singleton for these PHIs. */
157 if (phi)
158 return NULL;
160 phi = p;
162 return phi;
165 /* The core routine of conditional store replacement and normal
166 phi optimizations. Both share much of the infrastructure in how
167 to match applicable basic block patterns. DO_STORE_ELIM is true
168 when we want to do conditional store replacement, false otherwise.
169 DO_HOIST_LOADS is true when we want to hoist adjacent loads out
170 of diamond control flow patterns, false otherwise. */
171 static unsigned int
172 tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p)
174 basic_block bb;
175 basic_block *bb_order;
176 unsigned n, i;
177 bool cfgchanged = false;
178 hash_set<tree> *nontrap = 0;
180 calculate_dominance_info (CDI_DOMINATORS);
182 if (do_store_elim)
183 /* Calculate the set of non-trapping memory accesses. */
184 nontrap = get_non_trapping ();
186 /* Search every basic block for COND_EXPR we may be able to optimize.
188 We walk the blocks in order that guarantees that a block with
189 a single predecessor is processed before the predecessor.
190 This ensures that we collapse inner ifs before visiting the
191 outer ones, and also that we do not try to visit a removed
192 block. */
193 bb_order = single_pred_before_succ_order ();
194 n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
196 for (i = 0; i < n; i++)
198 gimple *cond_stmt;
199 gphi *phi;
200 basic_block bb1, bb2;
201 edge e1, e2;
202 tree arg0, arg1;
204 bb = bb_order[i];
206 cond_stmt = last_stmt (bb);
207 /* Check to see if the last statement is a GIMPLE_COND. */
208 if (!cond_stmt
209 || gimple_code (cond_stmt) != GIMPLE_COND)
210 continue;
212 e1 = EDGE_SUCC (bb, 0);
213 bb1 = e1->dest;
214 e2 = EDGE_SUCC (bb, 1);
215 bb2 = e2->dest;
217 /* We cannot do the optimization on abnormal edges. */
218 if ((e1->flags & EDGE_ABNORMAL) != 0
219 || (e2->flags & EDGE_ABNORMAL) != 0)
220 continue;
222 /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
223 if (EDGE_COUNT (bb1->succs) == 0
224 || EDGE_COUNT (bb2->succs) == 0)
225 continue;
227 /* Find the bb which is the fall through to the other. */
228 if (EDGE_SUCC (bb1, 0)->dest == bb2)
230 else if (EDGE_SUCC (bb2, 0)->dest == bb1)
232 std::swap (bb1, bb2);
233 std::swap (e1, e2);
235 else if (do_store_elim
236 && EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest)
238 basic_block bb3 = EDGE_SUCC (bb1, 0)->dest;
240 if (!single_succ_p (bb1)
241 || (EDGE_SUCC (bb1, 0)->flags & EDGE_FALLTHRU) == 0
242 || !single_succ_p (bb2)
243 || (EDGE_SUCC (bb2, 0)->flags & EDGE_FALLTHRU) == 0
244 || EDGE_COUNT (bb3->preds) != 2)
245 continue;
246 if (cond_if_else_store_replacement (bb1, bb2, bb3))
247 cfgchanged = true;
248 continue;
250 else if (do_hoist_loads
251 && EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest)
253 basic_block bb3 = EDGE_SUCC (bb1, 0)->dest;
255 if (!FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt)))
256 && single_succ_p (bb1)
257 && single_succ_p (bb2)
258 && single_pred_p (bb1)
259 && single_pred_p (bb2)
260 && EDGE_COUNT (bb->succs) == 2
261 && EDGE_COUNT (bb3->preds) == 2
262 /* If one edge or the other is dominant, a conditional move
263 is likely to perform worse than the well-predicted branch. */
264 && !predictable_edge_p (EDGE_SUCC (bb, 0))
265 && !predictable_edge_p (EDGE_SUCC (bb, 1)))
266 hoist_adjacent_loads (bb, bb1, bb2, bb3);
267 continue;
269 else
270 continue;
272 e1 = EDGE_SUCC (bb1, 0);
274 /* Make sure that bb1 is just a fall through. */
275 if (!single_succ_p (bb1)
276 || (e1->flags & EDGE_FALLTHRU) == 0)
277 continue;
279 if (do_store_elim)
281 /* Also make sure that bb1 only have one predecessor and that it
282 is bb. */
283 if (!single_pred_p (bb1)
284 || single_pred (bb1) != bb)
285 continue;
287 /* bb1 is the middle block, bb2 the join block, bb the split block,
288 e1 the fallthrough edge from bb1 to bb2. We can't do the
289 optimization if the join block has more than two predecessors. */
290 if (EDGE_COUNT (bb2->preds) > 2)
291 continue;
292 if (cond_store_replacement (bb1, bb2, e1, e2, nontrap))
293 cfgchanged = true;
295 else
297 gimple_seq phis = phi_nodes (bb2);
298 gimple_stmt_iterator gsi;
299 bool candorest = true;
301 /* Value replacement can work with more than one PHI
302 so try that first. */
303 if (!early_p)
304 for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
306 phi = as_a <gphi *> (gsi_stmt (gsi));
307 arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
308 arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
309 if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1) == 2)
311 candorest = false;
312 cfgchanged = true;
313 break;
317 if (!candorest)
318 continue;
320 phi = single_non_singleton_phi_for_edges (phis, e1, e2);
321 if (!phi)
322 continue;
324 arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
325 arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
327 /* Something is wrong if we cannot find the arguments in the PHI
328 node. */
329 gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
331 gphi *newphi;
332 if (single_pred_p (bb1)
333 && (newphi = factor_out_conditional_conversion (e1, e2, phi,
334 arg0, arg1,
335 cond_stmt)))
337 phi = newphi;
338 /* factor_out_conditional_conversion may create a new PHI in
339 BB2 and eliminate an existing PHI in BB2. Recompute values
340 that may be affected by that change. */
341 arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
342 arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
343 gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
346 /* Do the replacement of conditional if it can be done. */
347 if (!early_p && two_value_replacement (bb, bb1, e2, phi, arg0, arg1))
348 cfgchanged = true;
349 else if (match_simplify_replacement (bb, bb1, e1, e2, phi,
350 arg0, arg1,
351 early_p))
352 cfgchanged = true;
353 else if (!early_p
354 && single_pred_p (bb1)
355 && cond_removal_in_builtin_zero_pattern (bb, bb1, e1, e2,
356 phi, arg0, arg1))
357 cfgchanged = true;
358 else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
359 cfgchanged = true;
360 else if (single_pred_p (bb1)
361 && spaceship_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
362 cfgchanged = true;
366 free (bb_order);
368 if (do_store_elim)
369 delete nontrap;
370 /* If the CFG has changed, we should cleanup the CFG. */
371 if (cfgchanged && do_store_elim)
373 /* In cond-store replacement we have added some loads on edges
374 and new VOPS (as we moved the store, and created a load). */
375 gsi_commit_edge_inserts ();
376 return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
378 else if (cfgchanged)
379 return TODO_cleanup_cfg;
380 return 0;
383 /* Replace PHI node element whose edge is E in block BB with variable NEW.
384 Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
385 is known to have two edges, one of which must reach BB). */
387 static void
388 replace_phi_edge_with_variable (basic_block cond_block,
389 edge e, gphi *phi, tree new_tree)
391 basic_block bb = gimple_bb (phi);
392 gimple_stmt_iterator gsi;
393 tree phi_result = PHI_RESULT (phi);
395 /* Duplicate range info if they are the only things setting the target PHI.
396 This is needed as later on, the new_tree will be replacing
397 The assignement of the PHI.
398 For an example:
399 bb1:
400 _4 = min<a_1, 255>
401 goto bb2
403 # RANGE [-INF, 255]
404 a_3 = PHI<_4(1)>
405 bb3:
407 use(a_3)
408 And _4 gets propagated into the use of a_3 and losing the range info.
409 This can't be done for more than 2 incoming edges as the propagation
410 won't happen.
411 The new_tree needs to be defined in the same basic block as the conditional. */
412 if (TREE_CODE (new_tree) == SSA_NAME
413 && EDGE_COUNT (gimple_bb (phi)->preds) == 2
414 && INTEGRAL_TYPE_P (TREE_TYPE (phi_result))
415 && !SSA_NAME_RANGE_INFO (new_tree)
416 && SSA_NAME_RANGE_INFO (phi_result)
417 && gimple_bb (SSA_NAME_DEF_STMT (new_tree)) == cond_block
418 && dbg_cnt (phiopt_edge_range))
419 duplicate_ssa_name_range_info (new_tree, phi_result);
421 /* Change the PHI argument to new. */
422 SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);
424 /* Remove the empty basic block. */
425 edge edge_to_remove;
426 if (EDGE_SUCC (cond_block, 0)->dest == bb)
427 edge_to_remove = EDGE_SUCC (cond_block, 1);
428 else
429 edge_to_remove = EDGE_SUCC (cond_block, 0);
430 if (EDGE_COUNT (edge_to_remove->dest->preds) == 1)
432 e->flags |= EDGE_FALLTHRU;
433 e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
434 e->probability = profile_probability::always ();
435 delete_basic_block (edge_to_remove->dest);
437 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
438 gsi = gsi_last_bb (cond_block);
439 gsi_remove (&gsi, true);
441 else
443 /* If there are other edges into the middle block make
444 CFG cleanup deal with the edge removal to avoid
445 updating dominators here in a non-trivial way. */
446 gcond *cond = as_a <gcond *> (last_stmt (cond_block));
447 if (edge_to_remove->flags & EDGE_TRUE_VALUE)
448 gimple_cond_make_false (cond);
449 else
450 gimple_cond_make_true (cond);
453 statistics_counter_event (cfun, "Replace PHI with variable", 1);
455 if (dump_file && (dump_flags & TDF_DETAILS))
456 fprintf (dump_file,
457 "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
458 cond_block->index,
459 bb->index);
462 /* PR66726: Factor conversion out of COND_EXPR. If the arguments of the PHI
463 stmt are CONVERT_STMT, factor out the conversion and perform the conversion
464 to the result of PHI stmt. COND_STMT is the controlling predicate.
465 Return the newly-created PHI, if any. */
467 static gphi *
468 factor_out_conditional_conversion (edge e0, edge e1, gphi *phi,
469 tree arg0, tree arg1, gimple *cond_stmt)
471 gimple *arg0_def_stmt = NULL, *arg1_def_stmt = NULL, *new_stmt;
472 tree new_arg0 = NULL_TREE, new_arg1 = NULL_TREE;
473 tree temp, result;
474 gphi *newphi;
475 gimple_stmt_iterator gsi, gsi_for_def;
476 location_t locus = gimple_location (phi);
477 enum tree_code convert_code;
479 /* Handle only PHI statements with two arguments. TODO: If all
480 other arguments to PHI are INTEGER_CST or if their defining
481 statement have the same unary operation, we can handle more
482 than two arguments too. */
483 if (gimple_phi_num_args (phi) != 2)
484 return NULL;
486 /* First canonicalize to simplify tests. */
487 if (TREE_CODE (arg0) != SSA_NAME)
489 std::swap (arg0, arg1);
490 std::swap (e0, e1);
493 if (TREE_CODE (arg0) != SSA_NAME
494 || (TREE_CODE (arg1) != SSA_NAME
495 && TREE_CODE (arg1) != INTEGER_CST))
496 return NULL;
498 /* Check if arg0 is an SSA_NAME and the stmt which defines arg0 is
499 a conversion. */
500 arg0_def_stmt = SSA_NAME_DEF_STMT (arg0);
501 if (!gimple_assign_cast_p (arg0_def_stmt))
502 return NULL;
504 /* Use the RHS as new_arg0. */
505 convert_code = gimple_assign_rhs_code (arg0_def_stmt);
506 new_arg0 = gimple_assign_rhs1 (arg0_def_stmt);
507 if (convert_code == VIEW_CONVERT_EXPR)
509 new_arg0 = TREE_OPERAND (new_arg0, 0);
510 if (!is_gimple_reg_type (TREE_TYPE (new_arg0)))
511 return NULL;
513 if (TREE_CODE (new_arg0) == SSA_NAME
514 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_arg0))
515 return NULL;
517 if (TREE_CODE (arg1) == SSA_NAME)
519 /* Check if arg1 is an SSA_NAME and the stmt which defines arg1
520 is a conversion. */
521 arg1_def_stmt = SSA_NAME_DEF_STMT (arg1);
522 if (!is_gimple_assign (arg1_def_stmt)
523 || gimple_assign_rhs_code (arg1_def_stmt) != convert_code)
524 return NULL;
526 /* Either arg1_def_stmt or arg0_def_stmt should be conditional. */
527 if (dominated_by_p (CDI_DOMINATORS, gimple_bb (phi), gimple_bb (arg0_def_stmt))
528 && dominated_by_p (CDI_DOMINATORS,
529 gimple_bb (phi), gimple_bb (arg1_def_stmt)))
530 return NULL;
532 /* Use the RHS as new_arg1. */
533 new_arg1 = gimple_assign_rhs1 (arg1_def_stmt);
534 if (convert_code == VIEW_CONVERT_EXPR)
535 new_arg1 = TREE_OPERAND (new_arg1, 0);
536 if (TREE_CODE (new_arg1) == SSA_NAME
537 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_arg1))
538 return NULL;
540 else
542 /* arg0_def_stmt should be conditional. */
543 if (dominated_by_p (CDI_DOMINATORS, gimple_bb (phi), gimple_bb (arg0_def_stmt)))
544 return NULL;
545 /* If arg1 is an INTEGER_CST, fold it to new type. */
546 if (INTEGRAL_TYPE_P (TREE_TYPE (new_arg0))
547 && int_fits_type_p (arg1, TREE_TYPE (new_arg0)))
549 if (gimple_assign_cast_p (arg0_def_stmt))
551 /* For the INTEGER_CST case, we are just moving the
552 conversion from one place to another, which can often
553 hurt as the conversion moves further away from the
554 statement that computes the value. So, perform this
555 only if new_arg0 is an operand of COND_STMT, or
556 if arg0_def_stmt is the only non-debug stmt in
557 its basic block, because then it is possible this
558 could enable further optimizations (minmax replacement
559 etc.). See PR71016. */
560 if (new_arg0 != gimple_cond_lhs (cond_stmt)
561 && new_arg0 != gimple_cond_rhs (cond_stmt)
562 && gimple_bb (arg0_def_stmt) == e0->src)
564 gsi = gsi_for_stmt (arg0_def_stmt);
565 gsi_prev_nondebug (&gsi);
566 if (!gsi_end_p (gsi))
568 if (gassign *assign
569 = dyn_cast <gassign *> (gsi_stmt (gsi)))
571 tree lhs = gimple_assign_lhs (assign);
572 enum tree_code ass_code
573 = gimple_assign_rhs_code (assign);
574 if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
575 return NULL;
576 if (lhs != gimple_assign_rhs1 (arg0_def_stmt))
577 return NULL;
578 gsi_prev_nondebug (&gsi);
579 if (!gsi_end_p (gsi))
580 return NULL;
582 else
583 return NULL;
585 gsi = gsi_for_stmt (arg0_def_stmt);
586 gsi_next_nondebug (&gsi);
587 if (!gsi_end_p (gsi))
588 return NULL;
590 new_arg1 = fold_convert (TREE_TYPE (new_arg0), arg1);
592 else
593 return NULL;
595 else
596 return NULL;
599 /* If arg0/arg1 have > 1 use, then this transformation actually increases
600 the number of expressions evaluated at runtime. */
601 if (!has_single_use (arg0)
602 || (arg1_def_stmt && !has_single_use (arg1)))
603 return NULL;
605 /* If types of new_arg0 and new_arg1 are different bailout. */
606 if (!types_compatible_p (TREE_TYPE (new_arg0), TREE_TYPE (new_arg1)))
607 return NULL;
609 /* Create a new PHI stmt. */
610 result = PHI_RESULT (phi);
611 temp = make_ssa_name (TREE_TYPE (new_arg0), NULL);
612 newphi = create_phi_node (temp, gimple_bb (phi));
614 if (dump_file && (dump_flags & TDF_DETAILS))
616 fprintf (dump_file, "PHI ");
617 print_generic_expr (dump_file, gimple_phi_result (phi));
618 fprintf (dump_file,
619 " changed to factor conversion out from COND_EXPR.\n");
620 fprintf (dump_file, "New stmt with CAST that defines ");
621 print_generic_expr (dump_file, result);
622 fprintf (dump_file, ".\n");
625 /* Remove the old cast(s) that has single use. */
626 gsi_for_def = gsi_for_stmt (arg0_def_stmt);
627 gsi_remove (&gsi_for_def, true);
628 release_defs (arg0_def_stmt);
630 if (arg1_def_stmt)
632 gsi_for_def = gsi_for_stmt (arg1_def_stmt);
633 gsi_remove (&gsi_for_def, true);
634 release_defs (arg1_def_stmt);
637 add_phi_arg (newphi, new_arg0, e0, locus);
638 add_phi_arg (newphi, new_arg1, e1, locus);
640 /* Create the conversion stmt and insert it. */
641 if (convert_code == VIEW_CONVERT_EXPR)
643 temp = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (result), temp);
644 new_stmt = gimple_build_assign (result, temp);
646 else
647 new_stmt = gimple_build_assign (result, convert_code, temp);
648 gsi = gsi_after_labels (gimple_bb (phi));
649 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
651 /* Remove the original PHI stmt. */
652 gsi = gsi_for_stmt (phi);
653 gsi_remove (&gsi, true);
655 statistics_counter_event (cfun, "factored out cast", 1);
657 return newphi;
660 /* Optimize
661 # x_5 in range [cst1, cst2] where cst2 = cst1 + 1
662 if (x_5 op cstN) # where op is == or != and N is 1 or 2
663 goto bb3;
664 else
665 goto bb4;
666 bb3:
667 bb4:
668 # r_6 = PHI<cst3(2), cst4(3)> # where cst3 == cst4 + 1 or cst4 == cst3 + 1
670 to r_6 = x_5 + (min (cst3, cst4) - cst1) or
671 r_6 = (min (cst3, cst4) + cst1) - x_5 depending on op, N and which
672 of cst3 and cst4 is smaller. */
674 static bool
675 two_value_replacement (basic_block cond_bb, basic_block middle_bb,
676 edge e1, gphi *phi, tree arg0, tree arg1)
678 /* Only look for adjacent integer constants. */
679 if (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
680 || !INTEGRAL_TYPE_P (TREE_TYPE (arg1))
681 || TREE_CODE (arg0) != INTEGER_CST
682 || TREE_CODE (arg1) != INTEGER_CST
683 || (tree_int_cst_lt (arg0, arg1)
684 ? wi::to_widest (arg0) + 1 != wi::to_widest (arg1)
685 : wi::to_widest (arg1) + 1 != wi::to_widest (arg0)))
686 return false;
688 if (!empty_block_p (middle_bb))
689 return false;
691 gimple *stmt = last_stmt (cond_bb);
692 tree lhs = gimple_cond_lhs (stmt);
693 tree rhs = gimple_cond_rhs (stmt);
695 if (TREE_CODE (lhs) != SSA_NAME
696 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
697 || TREE_CODE (rhs) != INTEGER_CST)
698 return false;
700 switch (gimple_cond_code (stmt))
702 case EQ_EXPR:
703 case NE_EXPR:
704 break;
705 default:
706 return false;
709 /* Defer boolean x ? 0 : {1,-1} or x ? {1,-1} : 0 to
710 match_simplify_replacement. */
711 if (TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE
712 && (integer_zerop (arg0)
713 || integer_zerop (arg1)
714 || TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE
715 || (TYPE_PRECISION (TREE_TYPE (arg0))
716 <= TYPE_PRECISION (TREE_TYPE (lhs)))))
717 return false;
719 wide_int min, max;
720 value_range r;
721 get_range_query (cfun)->range_of_expr (r, lhs);
723 if (r.kind () == VR_RANGE)
725 min = r.lower_bound ();
726 max = r.upper_bound ();
728 else
730 int prec = TYPE_PRECISION (TREE_TYPE (lhs));
731 signop sgn = TYPE_SIGN (TREE_TYPE (lhs));
732 min = wi::min_value (prec, sgn);
733 max = wi::max_value (prec, sgn);
735 if (min + 1 != max
736 || (wi::to_wide (rhs) != min
737 && wi::to_wide (rhs) != max))
738 return false;
740 /* We need to know which is the true edge and which is the false
741 edge so that we know when to invert the condition below. */
742 edge true_edge, false_edge;
743 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
744 if ((gimple_cond_code (stmt) == EQ_EXPR)
745 ^ (wi::to_wide (rhs) == max)
746 ^ (e1 == false_edge))
747 std::swap (arg0, arg1);
749 tree type;
750 if (TYPE_PRECISION (TREE_TYPE (lhs)) == TYPE_PRECISION (TREE_TYPE (arg0)))
752 /* Avoid performing the arithmetics in bool type which has different
753 semantics, otherwise prefer unsigned types from the two with
754 the same precision. */
755 if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE
756 || !TYPE_UNSIGNED (TREE_TYPE (arg0)))
757 type = TREE_TYPE (lhs);
758 else
759 type = TREE_TYPE (arg0);
761 else if (TYPE_PRECISION (TREE_TYPE (lhs)) > TYPE_PRECISION (TREE_TYPE (arg0)))
762 type = TREE_TYPE (lhs);
763 else
764 type = TREE_TYPE (arg0);
766 min = wide_int::from (min, TYPE_PRECISION (type),
767 TYPE_SIGN (TREE_TYPE (lhs)));
768 wide_int a = wide_int::from (wi::to_wide (arg0), TYPE_PRECISION (type),
769 TYPE_SIGN (TREE_TYPE (arg0)));
770 enum tree_code code;
771 wi::overflow_type ovf;
772 if (tree_int_cst_lt (arg0, arg1))
774 code = PLUS_EXPR;
775 a -= min;
776 if (!TYPE_UNSIGNED (type))
778 /* lhs is known to be in range [min, min+1] and we want to add a
779 to it. Check if that operation can overflow for those 2 values
780 and if yes, force unsigned type. */
781 wi::add (min + (wi::neg_p (a) ? 0 : 1), a, SIGNED, &ovf);
782 if (ovf)
783 type = unsigned_type_for (type);
786 else
788 code = MINUS_EXPR;
789 a += min;
790 if (!TYPE_UNSIGNED (type))
792 /* lhs is known to be in range [min, min+1] and we want to subtract
793 it from a. Check if that operation can overflow for those 2
794 values and if yes, force unsigned type. */
795 wi::sub (a, min + (wi::neg_p (min) ? 0 : 1), SIGNED, &ovf);
796 if (ovf)
797 type = unsigned_type_for (type);
801 tree arg = wide_int_to_tree (type, a);
802 gimple_seq stmts = NULL;
803 lhs = gimple_convert (&stmts, type, lhs);
804 tree new_rhs;
805 if (code == PLUS_EXPR)
806 new_rhs = gimple_build (&stmts, PLUS_EXPR, type, lhs, arg);
807 else
808 new_rhs = gimple_build (&stmts, MINUS_EXPR, type, arg, lhs);
809 new_rhs = gimple_convert (&stmts, TREE_TYPE (arg0), new_rhs);
810 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
811 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
813 replace_phi_edge_with_variable (cond_bb, e1, phi, new_rhs);
815 /* Note that we optimized this PHI. */
816 return true;
819 /* Return TRUE if SEQ/OP pair should be allowed during early phiopt.
820 Currently this is to allow MIN/MAX and ABS/NEGATE and constants. */
821 static bool
822 phiopt_early_allow (gimple_seq &seq, gimple_match_op &op)
824 /* Don't allow functions. */
825 if (!op.code.is_tree_code ())
826 return false;
827 tree_code code = (tree_code)op.code;
829 /* For non-empty sequence, only allow one statement. */
830 if (!gimple_seq_empty_p (seq))
832 /* Check to make sure op was already a SSA_NAME. */
833 if (code != SSA_NAME)
834 return false;
835 if (!gimple_seq_singleton_p (seq))
836 return false;
837 gimple *stmt = gimple_seq_first_stmt (seq);
838 /* Only allow assignments. */
839 if (!is_gimple_assign (stmt))
840 return false;
841 if (gimple_assign_lhs (stmt) != op.ops[0])
842 return false;
843 code = gimple_assign_rhs_code (stmt);
846 switch (code)
848 case MIN_EXPR:
849 case MAX_EXPR:
850 case ABS_EXPR:
851 case ABSU_EXPR:
852 case NEGATE_EXPR:
853 case SSA_NAME:
854 return true;
855 case INTEGER_CST:
856 case REAL_CST:
857 case VECTOR_CST:
858 case FIXED_CST:
859 return true;
860 default:
861 return false;
865 /* gimple_simplify_phiopt is like gimple_simplify but designed for PHIOPT.
866 Return NULL if nothing can be simplified or the resulting simplified value
867 with parts pushed if EARLY_P was true. Also rejects non allowed tree code
868 if EARLY_P is set.
869 Takes the comparison from COMP_STMT and two args, ARG0 and ARG1 and tries
870 to simplify CMP ? ARG0 : ARG1.
871 Also try to simplify (!CMP) ? ARG1 : ARG0 if the non-inverse failed. */
872 static tree
873 gimple_simplify_phiopt (bool early_p, tree type, gimple *comp_stmt,
874 tree arg0, tree arg1,
875 gimple_seq *seq)
877 tree result;
878 gimple_seq seq1 = NULL;
879 enum tree_code comp_code = gimple_cond_code (comp_stmt);
880 location_t loc = gimple_location (comp_stmt);
881 tree cmp0 = gimple_cond_lhs (comp_stmt);
882 tree cmp1 = gimple_cond_rhs (comp_stmt);
883 /* To handle special cases like floating point comparison, it is easier and
884 less error-prone to build a tree and gimplify it on the fly though it is
885 less efficient.
886 Don't use fold_build2 here as that might create (bool)a instead of just
887 "a != 0". */
888 tree cond = build2_loc (loc, comp_code, boolean_type_node,
889 cmp0, cmp1);
890 gimple_match_op op (gimple_match_cond::UNCOND,
891 COND_EXPR, type, cond, arg0, arg1);
893 if (op.resimplify (&seq1, follow_all_ssa_edges))
895 /* Early we want only to allow some generated tree codes. */
896 if (!early_p
897 || phiopt_early_allow (seq1, op))
899 result = maybe_push_res_to_seq (&op, &seq1);
900 if (result)
902 if (loc != UNKNOWN_LOCATION)
903 annotate_all_with_location (seq1, loc);
904 gimple_seq_add_seq_without_update (seq, seq1);
905 return result;
909 gimple_seq_discard (seq1);
910 seq1 = NULL;
912 /* Try the inverted comparison, that is !COMP ? ARG1 : ARG0. */
913 comp_code = invert_tree_comparison (comp_code, HONOR_NANS (cmp0));
915 if (comp_code == ERROR_MARK)
916 return NULL;
918 cond = build2_loc (loc,
919 comp_code, boolean_type_node,
920 cmp0, cmp1);
921 gimple_match_op op1 (gimple_match_cond::UNCOND,
922 COND_EXPR, type, cond, arg1, arg0);
924 if (op1.resimplify (&seq1, follow_all_ssa_edges))
926 /* Early we want only to allow some generated tree codes. */
927 if (!early_p
928 || phiopt_early_allow (seq1, op1))
930 result = maybe_push_res_to_seq (&op1, &seq1);
931 if (result)
933 if (loc != UNKNOWN_LOCATION)
934 annotate_all_with_location (seq1, loc);
935 gimple_seq_add_seq_without_update (seq, seq1);
936 return result;
940 gimple_seq_discard (seq1);
942 return NULL;
945 /* The function match_simplify_replacement does the main work of doing the
946 replacement using match and simplify. Return true if the replacement is done.
947 Otherwise return false.
948 BB is the basic block where the replacement is going to be done on. ARG0
949 is argument 0 from PHI. Likewise for ARG1. */
951 static bool
952 match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
953 edge e0, edge e1, gphi *phi,
954 tree arg0, tree arg1, bool early_p)
956 gimple *stmt;
957 gimple_stmt_iterator gsi;
958 edge true_edge, false_edge;
959 gimple_seq seq = NULL;
960 tree result;
961 gimple *stmt_to_move = NULL;
963 /* Special case A ? B : B as this will always simplify to B. */
964 if (operand_equal_for_phi_arg_p (arg0, arg1))
965 return false;
967 /* If the basic block only has a cheap preparation statement,
968 allow it and move it once the transformation is done. */
969 if (!empty_block_p (middle_bb))
971 if (!single_pred_p (middle_bb))
972 return false;
974 stmt_to_move = last_and_only_stmt (middle_bb);
975 if (!stmt_to_move)
976 return false;
978 if (gimple_vuse (stmt_to_move))
979 return false;
981 if (gimple_could_trap_p (stmt_to_move)
982 || gimple_has_side_effects (stmt_to_move))
983 return false;
985 if (gimple_uses_undefined_value_p (stmt_to_move))
986 return false;
988 /* Allow assignments and not no calls.
989 As const calls don't match any of the above, yet they could
990 still have some side-effects - they could contain
991 gimple_could_trap_p statements, like floating point
992 exceptions or integer division by zero. See PR70586.
993 FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
994 should handle this. */
995 if (!is_gimple_assign (stmt_to_move))
996 return false;
998 tree lhs = gimple_assign_lhs (stmt_to_move);
999 gimple *use_stmt;
1000 use_operand_p use_p;
1002 /* Allow only a statement which feeds into the phi. */
1003 if (!lhs || TREE_CODE (lhs) != SSA_NAME
1004 || !single_imm_use (lhs, &use_p, &use_stmt)
1005 || use_stmt != phi)
1006 return false;
1009 /* At this point we know we have a GIMPLE_COND with two successors.
1010 One successor is BB, the other successor is an empty block which
1011 falls through into BB.
1013 There is a single PHI node at the join point (BB).
1015 So, given the condition COND, and the two PHI arguments, match and simplify
1016 can happen on (COND) ? arg0 : arg1. */
1018 stmt = last_stmt (cond_bb);
1020 /* We need to know which is the true edge and which is the false
1021 edge so that we know when to invert the condition below. */
1022 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1023 if (e1 == true_edge || e0 == false_edge)
1024 std::swap (arg0, arg1);
1026 tree type = TREE_TYPE (gimple_phi_result (phi));
1027 result = gimple_simplify_phiopt (early_p, type, stmt,
1028 arg0, arg1,
1029 &seq);
1030 if (!result)
1031 return false;
1033 gsi = gsi_last_bb (cond_bb);
1034 /* Insert the sequence generated from gimple_simplify_phiopt. */
1035 if (seq)
1036 gsi_insert_seq_before (&gsi, seq, GSI_CONTINUE_LINKING);
1038 /* If there was a statement to move and the result of the statement
1039 is going to be used, move it to right before the original
1040 conditional. */
1041 if (stmt_to_move
1042 && (gimple_assign_lhs (stmt_to_move) == result
1043 || !has_single_use (gimple_assign_lhs (stmt_to_move))))
1045 if (dump_file && (dump_flags & TDF_DETAILS))
1047 fprintf (dump_file, "statement un-sinked:\n");
1048 print_gimple_stmt (dump_file, stmt_to_move, 0,
1049 TDF_VOPS|TDF_MEMSYMS);
1051 gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt_to_move);
1052 gsi_move_before (&gsi1, &gsi);
1053 reset_flow_sensitive_info (gimple_assign_lhs (stmt_to_move));
1056 replace_phi_edge_with_variable (cond_bb, e1, phi, result);
1058 /* Add Statistic here even though replace_phi_edge_with_variable already
1059 does it as we want to be able to count when match-simplify happens vs
1060 the others. */
1061 statistics_counter_event (cfun, "match-simplify PHI replacement", 1);
1063 /* Note that we optimized this PHI. */
1064 return true;
1067 /* Update *ARG which is defined in STMT so that it contains the
1068 computed value if that seems profitable. Return true if the
1069 statement is made dead by that rewriting. */
1071 static bool
1072 jump_function_from_stmt (tree *arg, gimple *stmt)
1074 enum tree_code code = gimple_assign_rhs_code (stmt);
1075 if (code == ADDR_EXPR)
1077 /* For arg = &p->i transform it to p, if possible. */
1078 tree rhs1 = gimple_assign_rhs1 (stmt);
1079 poly_int64 offset;
1080 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs1, 0),
1081 &offset);
1082 if (tem
1083 && TREE_CODE (tem) == MEM_REF
1084 && known_eq (mem_ref_offset (tem) + offset, 0))
1086 *arg = TREE_OPERAND (tem, 0);
1087 return true;
1090 /* TODO: Much like IPA-CP jump-functions we want to handle constant
1091 additions symbolically here, and we'd need to update the comparison
1092 code that compares the arg + cst tuples in our caller. For now the
1093 code above exactly handles the VEC_BASE pattern from vec.h. */
1094 return false;
1097 /* RHS is a source argument in a BIT_AND_EXPR which feeds a conditional
1098 of the form SSA_NAME NE 0.
1100 If RHS is fed by a simple EQ_EXPR comparison of two values, see if
1101 the two input values of the EQ_EXPR match arg0 and arg1.
1103 If so update *code and return TRUE. Otherwise return FALSE. */
1105 static bool
1106 rhs_is_fed_for_value_replacement (const_tree arg0, const_tree arg1,
1107 enum tree_code *code, const_tree rhs)
1109 /* Obviously if RHS is not an SSA_NAME, we can't look at the defining
1110 statement. */
1111 if (TREE_CODE (rhs) == SSA_NAME)
1113 gimple *def1 = SSA_NAME_DEF_STMT (rhs);
1115 /* Verify the defining statement has an EQ_EXPR on the RHS. */
1116 if (is_gimple_assign (def1) && gimple_assign_rhs_code (def1) == EQ_EXPR)
1118 /* Finally verify the source operands of the EQ_EXPR are equal
1119 to arg0 and arg1. */
1120 tree op0 = gimple_assign_rhs1 (def1);
1121 tree op1 = gimple_assign_rhs2 (def1);
1122 if ((operand_equal_for_phi_arg_p (arg0, op0)
1123 && operand_equal_for_phi_arg_p (arg1, op1))
1124 || (operand_equal_for_phi_arg_p (arg0, op1)
1125 && operand_equal_for_phi_arg_p (arg1, op0)))
1127 /* We will perform the optimization. */
1128 *code = gimple_assign_rhs_code (def1);
1129 return true;
1133 return false;
1136 /* Return TRUE if arg0/arg1 are equal to the rhs/lhs or lhs/rhs of COND.
1138 Also return TRUE if arg0/arg1 are equal to the source arguments of a
1139 an EQ comparison feeding a BIT_AND_EXPR which feeds COND.
1141 Return FALSE otherwise. */
1143 static bool
1144 operand_equal_for_value_replacement (const_tree arg0, const_tree arg1,
1145 enum tree_code *code, gimple *cond)
1147 gimple *def;
1148 tree lhs = gimple_cond_lhs (cond);
1149 tree rhs = gimple_cond_rhs (cond);
1151 if ((operand_equal_for_phi_arg_p (arg0, lhs)
1152 && operand_equal_for_phi_arg_p (arg1, rhs))
1153 || (operand_equal_for_phi_arg_p (arg1, lhs)
1154 && operand_equal_for_phi_arg_p (arg0, rhs)))
1155 return true;
1157 /* Now handle more complex case where we have an EQ comparison
1158 which feeds a BIT_AND_EXPR which feeds COND.
1160 First verify that COND is of the form SSA_NAME NE 0. */
1161 if (*code != NE_EXPR || !integer_zerop (rhs)
1162 || TREE_CODE (lhs) != SSA_NAME)
1163 return false;
1165 /* Now ensure that SSA_NAME is set by a BIT_AND_EXPR. */
1166 def = SSA_NAME_DEF_STMT (lhs);
1167 if (!is_gimple_assign (def) || gimple_assign_rhs_code (def) != BIT_AND_EXPR)
1168 return false;
1170 /* Now verify arg0/arg1 correspond to the source arguments of an
1171 EQ comparison feeding the BIT_AND_EXPR. */
1173 tree tmp = gimple_assign_rhs1 (def);
1174 if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp))
1175 return true;
1177 tmp = gimple_assign_rhs2 (def);
1178 if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp))
1179 return true;
1181 return false;
1184 /* Returns true if ARG is a neutral element for operation CODE
1185 on the RIGHT side. */
1187 static bool
1188 neutral_element_p (tree_code code, tree arg, bool right)
1190 switch (code)
1192 case PLUS_EXPR:
1193 case BIT_IOR_EXPR:
1194 case BIT_XOR_EXPR:
1195 return integer_zerop (arg);
1197 case LROTATE_EXPR:
1198 case RROTATE_EXPR:
1199 case LSHIFT_EXPR:
1200 case RSHIFT_EXPR:
1201 case MINUS_EXPR:
1202 case POINTER_PLUS_EXPR:
1203 return right && integer_zerop (arg);
1205 case MULT_EXPR:
1206 return integer_onep (arg);
1208 case TRUNC_DIV_EXPR:
1209 case CEIL_DIV_EXPR:
1210 case FLOOR_DIV_EXPR:
1211 case ROUND_DIV_EXPR:
1212 case EXACT_DIV_EXPR:
1213 return right && integer_onep (arg);
1215 case BIT_AND_EXPR:
1216 return integer_all_onesp (arg);
1218 default:
1219 return false;
1223 /* Returns true if ARG is an absorbing element for operation CODE. */
1225 static bool
1226 absorbing_element_p (tree_code code, tree arg, bool right, tree rval)
1228 switch (code)
1230 case BIT_IOR_EXPR:
1231 return integer_all_onesp (arg);
1233 case MULT_EXPR:
1234 case BIT_AND_EXPR:
1235 return integer_zerop (arg);
1237 case LSHIFT_EXPR:
1238 case RSHIFT_EXPR:
1239 case LROTATE_EXPR:
1240 case RROTATE_EXPR:
1241 return !right && integer_zerop (arg);
1243 case TRUNC_DIV_EXPR:
1244 case CEIL_DIV_EXPR:
1245 case FLOOR_DIV_EXPR:
1246 case ROUND_DIV_EXPR:
1247 case EXACT_DIV_EXPR:
1248 case TRUNC_MOD_EXPR:
1249 case CEIL_MOD_EXPR:
1250 case FLOOR_MOD_EXPR:
1251 case ROUND_MOD_EXPR:
1252 return (!right
1253 && integer_zerop (arg)
1254 && tree_single_nonzero_warnv_p (rval, NULL));
1256 default:
1257 return false;
1261 /* The function value_replacement does the main work of doing the value
1262 replacement. Return non-zero if the replacement is done. Otherwise return
1263 0. If we remove the middle basic block, return 2.
1264 BB is the basic block where the replacement is going to be done on. ARG0
1265 is argument 0 from the PHI. Likewise for ARG1. */
1267 static int
1268 value_replacement (basic_block cond_bb, basic_block middle_bb,
1269 edge e0, edge e1, gphi *phi, tree arg0, tree arg1)
1271 gimple_stmt_iterator gsi;
1272 gimple *cond;
1273 edge true_edge, false_edge;
1274 enum tree_code code;
1275 bool empty_or_with_defined_p = true;
1277 /* If the type says honor signed zeros we cannot do this
1278 optimization. */
1279 if (HONOR_SIGNED_ZEROS (arg1))
1280 return 0;
1282 /* If there is a statement in MIDDLE_BB that defines one of the PHI
1283 arguments, then adjust arg0 or arg1. */
1284 gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
1285 while (!gsi_end_p (gsi))
1287 gimple *stmt = gsi_stmt (gsi);
1288 tree lhs;
1289 gsi_next_nondebug (&gsi);
1290 if (!is_gimple_assign (stmt))
1292 if (gimple_code (stmt) != GIMPLE_PREDICT
1293 && gimple_code (stmt) != GIMPLE_NOP)
1294 empty_or_with_defined_p = false;
1295 continue;
1297 /* Now try to adjust arg0 or arg1 according to the computation
1298 in the statement. */
1299 lhs = gimple_assign_lhs (stmt);
1300 if (!(lhs == arg0
1301 && jump_function_from_stmt (&arg0, stmt))
1302 || (lhs == arg1
1303 && jump_function_from_stmt (&arg1, stmt)))
1304 empty_or_with_defined_p = false;
1307 cond = last_stmt (cond_bb);
1308 code = gimple_cond_code (cond);
1310 /* This transformation is only valid for equality comparisons. */
1311 if (code != NE_EXPR && code != EQ_EXPR)
1312 return 0;
1314 /* We need to know which is the true edge and which is the false
1315 edge so that we know if have abs or negative abs. */
1316 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1318 /* At this point we know we have a COND_EXPR with two successors.
1319 One successor is BB, the other successor is an empty block which
1320 falls through into BB.
1322 The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
1324 There is a single PHI node at the join point (BB) with two arguments.
1326 We now need to verify that the two arguments in the PHI node match
1327 the two arguments to the equality comparison. */
1329 bool equal_p = operand_equal_for_value_replacement (arg0, arg1, &code, cond);
1330 bool maybe_equal_p = false;
1331 if (!equal_p
1332 && empty_or_with_defined_p
1333 && TREE_CODE (gimple_cond_rhs (cond)) == INTEGER_CST
1334 && (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond), arg0)
1335 ? TREE_CODE (arg1) == INTEGER_CST
1336 : (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond), arg1)
1337 && TREE_CODE (arg0) == INTEGER_CST)))
1338 maybe_equal_p = true;
1339 if (equal_p || maybe_equal_p)
1341 edge e;
1342 tree arg;
1344 /* For NE_EXPR, we want to build an assignment result = arg where
1345 arg is the PHI argument associated with the true edge. For
1346 EQ_EXPR we want the PHI argument associated with the false edge. */
1347 e = (code == NE_EXPR ? true_edge : false_edge);
1349 /* Unfortunately, E may not reach BB (it may instead have gone to
1350 OTHER_BLOCK). If that is the case, then we want the single outgoing
1351 edge from OTHER_BLOCK which reaches BB and represents the desired
1352 path from COND_BLOCK. */
1353 if (e->dest == middle_bb)
1354 e = single_succ_edge (e->dest);
1356 /* Now we know the incoming edge to BB that has the argument for the
1357 RHS of our new assignment statement. */
1358 if (e0 == e)
1359 arg = arg0;
1360 else
1361 arg = arg1;
1363 /* If the middle basic block was empty or is defining the
1364 PHI arguments and this is a single phi where the args are different
1365 for the edges e0 and e1 then we can remove the middle basic block. */
1366 if (empty_or_with_defined_p
1367 && single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)),
1368 e0, e1) == phi)
1370 use_operand_p use_p;
1371 gimple *use_stmt;
1373 /* Even if arg0/arg1 isn't equal to second operand of cond, we
1374 can optimize away the bb if we can prove it doesn't care whether
1375 phi result is arg0/arg1 or second operand of cond. Consider:
1376 <bb 2> [local count: 118111600]:
1377 if (i_2(D) == 4)
1378 goto <bb 4>; [97.00%]
1379 else
1380 goto <bb 3>; [3.00%]
1382 <bb 3> [local count: 3540129]:
1384 <bb 4> [local count: 118111600]:
1385 # i_6 = PHI <i_2(D)(3), 6(2)>
1386 _3 = i_6 != 0;
1387 Here, carg is 4, oarg is 6, crhs is 0, and because
1388 (4 != 0) == (6 != 0), we don't care if i_6 is 4 or 6, both
1389 have the same outcome. So, can can optimize this to:
1390 _3 = i_2(D) != 0;
1391 If the single imm use of phi result >, >=, < or <=, similarly
1392 we can check if both carg and oarg compare the same against
1393 crhs using ccode. */
1394 if (maybe_equal_p
1395 && TREE_CODE (arg) != INTEGER_CST
1396 && single_imm_use (gimple_phi_result (phi), &use_p, &use_stmt))
1398 enum tree_code ccode = ERROR_MARK;
1399 tree clhs = NULL_TREE, crhs = NULL_TREE;
1400 tree carg = gimple_cond_rhs (cond);
1401 tree oarg = e0 == e ? arg1 : arg0;
1402 if (is_gimple_assign (use_stmt)
1403 && (TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
1404 == tcc_comparison))
1406 ccode = gimple_assign_rhs_code (use_stmt);
1407 clhs = gimple_assign_rhs1 (use_stmt);
1408 crhs = gimple_assign_rhs2 (use_stmt);
1410 else if (gimple_code (use_stmt) == GIMPLE_COND)
1412 ccode = gimple_cond_code (use_stmt);
1413 clhs = gimple_cond_lhs (use_stmt);
1414 crhs = gimple_cond_rhs (use_stmt);
1416 if (ccode != ERROR_MARK
1417 && clhs == gimple_phi_result (phi)
1418 && TREE_CODE (crhs) == INTEGER_CST)
1419 switch (ccode)
1421 case EQ_EXPR:
1422 case NE_EXPR:
1423 if (!tree_int_cst_equal (crhs, carg)
1424 && !tree_int_cst_equal (crhs, oarg))
1425 equal_p = true;
1426 break;
1427 case GT_EXPR:
1428 if (tree_int_cst_lt (crhs, carg)
1429 == tree_int_cst_lt (crhs, oarg))
1430 equal_p = true;
1431 break;
1432 case GE_EXPR:
1433 if (tree_int_cst_le (crhs, carg)
1434 == tree_int_cst_le (crhs, oarg))
1435 equal_p = true;
1436 break;
1437 case LT_EXPR:
1438 if (tree_int_cst_lt (carg, crhs)
1439 == tree_int_cst_lt (oarg, crhs))
1440 equal_p = true;
1441 break;
1442 case LE_EXPR:
1443 if (tree_int_cst_le (carg, crhs)
1444 == tree_int_cst_le (oarg, crhs))
1445 equal_p = true;
1446 break;
1447 default:
1448 break;
1450 if (equal_p && MAY_HAVE_DEBUG_BIND_STMTS)
1452 imm_use_iterator imm_iter;
1453 tree phires = gimple_phi_result (phi);
1454 tree temp = NULL_TREE;
1455 bool reset_p = false;
1457 /* Add # DEBUG D#1 => arg != carg ? arg : oarg. */
1458 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, phires)
1460 if (!is_gimple_debug (use_stmt))
1461 continue;
1462 if (temp == NULL_TREE)
1464 if (!single_pred_p (middle_bb)
1465 || EDGE_COUNT (gimple_bb (phi)->preds) != 2)
1467 /* But only if middle_bb has a single
1468 predecessor and phi bb has two, otherwise
1469 we could use a SSA_NAME not usable in that
1470 place or wrong-debug. */
1471 reset_p = true;
1472 break;
1474 gimple_stmt_iterator gsi
1475 = gsi_after_labels (gimple_bb (phi));
1476 tree type = TREE_TYPE (phires);
1477 temp = build_debug_expr_decl (type);
1478 tree t = build2 (NE_EXPR, boolean_type_node,
1479 arg, carg);
1480 t = build3 (COND_EXPR, type, t, arg, oarg);
1481 gimple *g = gimple_build_debug_bind (temp, t, phi);
1482 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
1484 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
1485 replace_exp (use_p, temp);
1486 update_stmt (use_stmt);
1488 if (reset_p)
1489 reset_debug_uses (phi);
1492 if (equal_p)
1494 replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
1495 /* Note that we optimized this PHI. */
1496 return 2;
1499 else if (equal_p)
1501 if (!single_pred_p (middle_bb))
1502 return 0;
1503 statistics_counter_event (cfun, "Replace PHI with "
1504 "variable/value_replacement", 1);
1506 /* Replace the PHI arguments with arg. */
1507 SET_PHI_ARG_DEF (phi, e0->dest_idx, arg);
1508 SET_PHI_ARG_DEF (phi, e1->dest_idx, arg);
1509 if (dump_file && (dump_flags & TDF_DETAILS))
1511 fprintf (dump_file, "PHI ");
1512 print_generic_expr (dump_file, gimple_phi_result (phi));
1513 fprintf (dump_file, " reduced for COND_EXPR in block %d to ",
1514 cond_bb->index);
1515 print_generic_expr (dump_file, arg);
1516 fprintf (dump_file, ".\n");
1518 return 1;
1522 if (!single_pred_p (middle_bb))
1523 return 0;
1525 /* Now optimize (x != 0) ? x + y : y to just x + y. */
1526 gsi = gsi_last_nondebug_bb (middle_bb);
1527 if (gsi_end_p (gsi))
1528 return 0;
1530 gimple *assign = gsi_stmt (gsi);
1531 if (!is_gimple_assign (assign)
1532 || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
1533 && !POINTER_TYPE_P (TREE_TYPE (arg0))))
1534 return 0;
1536 if (gimple_assign_rhs_class (assign) != GIMPLE_BINARY_RHS)
1538 /* If last stmt of the middle_bb is a conversion, handle it like
1539 a preparation statement through constant evaluation with
1540 checking for UB. */
1541 enum tree_code sc = gimple_assign_rhs_code (assign);
1542 if (CONVERT_EXPR_CODE_P (sc))
1543 assign = NULL;
1544 else
1545 return 0;
1548 /* Punt if there are (degenerate) PHIs in middle_bb, there should not be. */
1549 if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
1550 return 0;
1552 /* Allow up to 2 cheap preparation statements that prepare argument
1553 for assign, e.g.:
1554 if (y_4 != 0)
1555 goto <bb 3>;
1556 else
1557 goto <bb 4>;
1558 <bb 3>:
1559 _1 = (int) y_4;
1560 iftmp.0_6 = x_5(D) r<< _1;
1561 <bb 4>:
1562 # iftmp.0_2 = PHI <iftmp.0_6(3), x_5(D)(2)>
1564 if (y_3(D) == 0)
1565 goto <bb 4>;
1566 else
1567 goto <bb 3>;
1568 <bb 3>:
1569 y_4 = y_3(D) & 31;
1570 _1 = (int) y_4;
1571 _6 = x_5(D) r<< _1;
1572 <bb 4>:
1573 # _2 = PHI <x_5(D)(2), _6(3)> */
1574 gimple *prep_stmt[2] = { NULL, NULL };
1575 int prep_cnt;
1576 for (prep_cnt = 0; ; prep_cnt++)
1578 if (prep_cnt || assign)
1579 gsi_prev_nondebug (&gsi);
1580 if (gsi_end_p (gsi))
1581 break;
1583 gimple *g = gsi_stmt (gsi);
1584 if (gimple_code (g) == GIMPLE_LABEL)
1585 break;
1587 if (prep_cnt == 2 || !is_gimple_assign (g))
1588 return 0;
1590 tree lhs = gimple_assign_lhs (g);
1591 tree rhs1 = gimple_assign_rhs1 (g);
1592 use_operand_p use_p;
1593 gimple *use_stmt;
1594 if (TREE_CODE (lhs) != SSA_NAME
1595 || TREE_CODE (rhs1) != SSA_NAME
1596 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1597 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1598 || !single_imm_use (lhs, &use_p, &use_stmt)
1599 || ((prep_cnt || assign)
1600 && use_stmt != (prep_cnt ? prep_stmt[prep_cnt - 1] : assign)))
1601 return 0;
1602 switch (gimple_assign_rhs_code (g))
1604 CASE_CONVERT:
1605 break;
1606 case PLUS_EXPR:
1607 case BIT_AND_EXPR:
1608 case BIT_IOR_EXPR:
1609 case BIT_XOR_EXPR:
1610 if (TREE_CODE (gimple_assign_rhs2 (g)) != INTEGER_CST)
1611 return 0;
1612 break;
1613 default:
1614 return 0;
1616 prep_stmt[prep_cnt] = g;
1619 /* Only transform if it removes the condition. */
1620 if (!single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)), e0, e1))
1621 return 0;
1623 /* Size-wise, this is always profitable. */
1624 if (optimize_bb_for_speed_p (cond_bb)
1625 /* The special case is useless if it has a low probability. */
1626 && profile_status_for_fn (cfun) != PROFILE_ABSENT
1627 && EDGE_PRED (middle_bb, 0)->probability < profile_probability::even ()
1628 /* If assign is cheap, there is no point avoiding it. */
1629 && estimate_num_insns_seq (bb_seq (middle_bb), &eni_time_weights)
1630 >= 3 * estimate_num_insns (cond, &eni_time_weights))
1631 return 0;
1633 tree cond_lhs = gimple_cond_lhs (cond);
1634 tree cond_rhs = gimple_cond_rhs (cond);
1636 /* Propagate the cond_rhs constant through preparation stmts,
1637 make sure UB isn't invoked while doing that. */
1638 for (int i = prep_cnt - 1; i >= 0; --i)
1640 gimple *g = prep_stmt[i];
1641 tree grhs1 = gimple_assign_rhs1 (g);
1642 if (!operand_equal_for_phi_arg_p (cond_lhs, grhs1))
1643 return 0;
1644 cond_lhs = gimple_assign_lhs (g);
1645 cond_rhs = fold_convert (TREE_TYPE (grhs1), cond_rhs);
1646 if (TREE_CODE (cond_rhs) != INTEGER_CST
1647 || TREE_OVERFLOW (cond_rhs))
1648 return 0;
1649 if (gimple_assign_rhs_class (g) == GIMPLE_BINARY_RHS)
1651 cond_rhs = int_const_binop (gimple_assign_rhs_code (g), cond_rhs,
1652 gimple_assign_rhs2 (g));
1653 if (TREE_OVERFLOW (cond_rhs))
1654 return 0;
1656 cond_rhs = fold_convert (TREE_TYPE (cond_lhs), cond_rhs);
1657 if (TREE_CODE (cond_rhs) != INTEGER_CST
1658 || TREE_OVERFLOW (cond_rhs))
1659 return 0;
1662 tree lhs, rhs1, rhs2;
1663 enum tree_code code_def;
1664 if (assign)
1666 lhs = gimple_assign_lhs (assign);
1667 rhs1 = gimple_assign_rhs1 (assign);
1668 rhs2 = gimple_assign_rhs2 (assign);
1669 code_def = gimple_assign_rhs_code (assign);
1671 else
1673 gcc_assert (prep_cnt > 0);
1674 lhs = cond_lhs;
1675 rhs1 = NULL_TREE;
1676 rhs2 = NULL_TREE;
1677 code_def = ERROR_MARK;
1680 if (((code == NE_EXPR && e1 == false_edge)
1681 || (code == EQ_EXPR && e1 == true_edge))
1682 && arg0 == lhs
1683 && ((assign == NULL
1684 && operand_equal_for_phi_arg_p (arg1, cond_rhs))
1685 || (assign
1686 && arg1 == rhs1
1687 && operand_equal_for_phi_arg_p (rhs2, cond_lhs)
1688 && neutral_element_p (code_def, cond_rhs, true))
1689 || (assign
1690 && arg1 == rhs2
1691 && operand_equal_for_phi_arg_p (rhs1, cond_lhs)
1692 && neutral_element_p (code_def, cond_rhs, false))
1693 || (assign
1694 && operand_equal_for_phi_arg_p (arg1, cond_rhs)
1695 && ((operand_equal_for_phi_arg_p (rhs2, cond_lhs)
1696 && absorbing_element_p (code_def, cond_rhs, true, rhs2))
1697 || (operand_equal_for_phi_arg_p (rhs1, cond_lhs)
1698 && absorbing_element_p (code_def,
1699 cond_rhs, false, rhs2))))))
1701 gsi = gsi_for_stmt (cond);
1702 /* Moving ASSIGN might change VR of lhs, e.g. when moving u_6
1703 def-stmt in:
1704 if (n_5 != 0)
1705 goto <bb 3>;
1706 else
1707 goto <bb 4>;
1709 <bb 3>:
1710 # RANGE [0, 4294967294]
1711 u_6 = n_5 + 4294967295;
1713 <bb 4>:
1714 # u_3 = PHI <u_6(3), 4294967295(2)> */
1715 reset_flow_sensitive_info (lhs);
1716 gimple_stmt_iterator gsi_from;
1717 for (int i = prep_cnt - 1; i >= 0; --i)
1719 tree plhs = gimple_assign_lhs (prep_stmt[i]);
1720 reset_flow_sensitive_info (plhs);
1721 gsi_from = gsi_for_stmt (prep_stmt[i]);
1722 gsi_move_before (&gsi_from, &gsi);
1724 if (assign)
1726 gsi_from = gsi_for_stmt (assign);
1727 gsi_move_before (&gsi_from, &gsi);
1729 replace_phi_edge_with_variable (cond_bb, e1, phi, lhs);
1730 return 2;
1733 return 0;
1736 /* The function minmax_replacement does the main work of doing the minmax
1737 replacement. Return true if the replacement is done. Otherwise return
1738 false.
1739 BB is the basic block where the replacement is going to be done on. ARG0
1740 is argument 0 from the PHI. Likewise for ARG1. */
1742 static bool
1743 minmax_replacement (basic_block cond_bb, basic_block middle_bb,
1744 edge e0, edge e1, gphi *phi, tree arg0, tree arg1)
1746 tree result;
1747 edge true_edge, false_edge;
1748 enum tree_code minmax, ass_code;
1749 tree smaller, larger, arg_true, arg_false;
1750 gimple_stmt_iterator gsi, gsi_from;
1752 tree type = TREE_TYPE (PHI_RESULT (phi));
1754 /* The optimization may be unsafe due to NaNs. */
1755 if (HONOR_NANS (type) || HONOR_SIGNED_ZEROS (type))
1756 return false;
1758 gcond *cond = as_a <gcond *> (last_stmt (cond_bb));
1759 enum tree_code cmp = gimple_cond_code (cond);
1760 tree rhs = gimple_cond_rhs (cond);
1762 /* Turn EQ/NE of extreme values to order comparisons. */
1763 if ((cmp == NE_EXPR || cmp == EQ_EXPR)
1764 && TREE_CODE (rhs) == INTEGER_CST
1765 && INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
1767 if (wi::eq_p (wi::to_wide (rhs), wi::min_value (TREE_TYPE (rhs))))
1769 cmp = (cmp == EQ_EXPR) ? LT_EXPR : GE_EXPR;
1770 rhs = wide_int_to_tree (TREE_TYPE (rhs),
1771 wi::min_value (TREE_TYPE (rhs)) + 1);
1773 else if (wi::eq_p (wi::to_wide (rhs), wi::max_value (TREE_TYPE (rhs))))
1775 cmp = (cmp == EQ_EXPR) ? GT_EXPR : LE_EXPR;
1776 rhs = wide_int_to_tree (TREE_TYPE (rhs),
1777 wi::max_value (TREE_TYPE (rhs)) - 1);
1781 /* This transformation is only valid for order comparisons. Record which
1782 operand is smaller/larger if the result of the comparison is true. */
1783 tree alt_smaller = NULL_TREE;
1784 tree alt_larger = NULL_TREE;
1785 if (cmp == LT_EXPR || cmp == LE_EXPR)
1787 smaller = gimple_cond_lhs (cond);
1788 larger = rhs;
1789 /* If we have smaller < CST it is equivalent to smaller <= CST-1.
1790 Likewise smaller <= CST is equivalent to smaller < CST+1. */
1791 if (TREE_CODE (larger) == INTEGER_CST
1792 && INTEGRAL_TYPE_P (TREE_TYPE (larger)))
1794 if (cmp == LT_EXPR)
1796 wi::overflow_type overflow;
1797 wide_int alt = wi::sub (wi::to_wide (larger), 1,
1798 TYPE_SIGN (TREE_TYPE (larger)),
1799 &overflow);
1800 if (! overflow)
1801 alt_larger = wide_int_to_tree (TREE_TYPE (larger), alt);
1803 else
1805 wi::overflow_type overflow;
1806 wide_int alt = wi::add (wi::to_wide (larger), 1,
1807 TYPE_SIGN (TREE_TYPE (larger)),
1808 &overflow);
1809 if (! overflow)
1810 alt_larger = wide_int_to_tree (TREE_TYPE (larger), alt);
1814 else if (cmp == GT_EXPR || cmp == GE_EXPR)
1816 smaller = rhs;
1817 larger = gimple_cond_lhs (cond);
1818 /* If we have larger > CST it is equivalent to larger >= CST+1.
1819 Likewise larger >= CST is equivalent to larger > CST-1. */
1820 if (TREE_CODE (smaller) == INTEGER_CST
1821 && INTEGRAL_TYPE_P (TREE_TYPE (smaller)))
1823 wi::overflow_type overflow;
1824 if (cmp == GT_EXPR)
1826 wide_int alt = wi::add (wi::to_wide (smaller), 1,
1827 TYPE_SIGN (TREE_TYPE (smaller)),
1828 &overflow);
1829 if (! overflow)
1830 alt_smaller = wide_int_to_tree (TREE_TYPE (smaller), alt);
1832 else
1834 wide_int alt = wi::sub (wi::to_wide (smaller), 1,
1835 TYPE_SIGN (TREE_TYPE (smaller)),
1836 &overflow);
1837 if (! overflow)
1838 alt_smaller = wide_int_to_tree (TREE_TYPE (smaller), alt);
1842 else
1843 return false;
1845 /* Handle the special case of (signed_type)x < 0 being equivalent
1846 to x > MAX_VAL(signed_type) and (signed_type)x >= 0 equivalent
1847 to x <= MAX_VAL(signed_type). */
1848 if ((cmp == GE_EXPR || cmp == LT_EXPR)
1849 && INTEGRAL_TYPE_P (type)
1850 && TYPE_UNSIGNED (type)
1851 && integer_zerop (rhs))
1853 tree op = gimple_cond_lhs (cond);
1854 if (TREE_CODE (op) == SSA_NAME
1855 && INTEGRAL_TYPE_P (TREE_TYPE (op))
1856 && !TYPE_UNSIGNED (TREE_TYPE (op)))
1858 gimple *def_stmt = SSA_NAME_DEF_STMT (op);
1859 if (gimple_assign_cast_p (def_stmt))
1861 tree op1 = gimple_assign_rhs1 (def_stmt);
1862 if (INTEGRAL_TYPE_P (TREE_TYPE (op1))
1863 && TYPE_UNSIGNED (TREE_TYPE (op1))
1864 && (TYPE_PRECISION (TREE_TYPE (op))
1865 == TYPE_PRECISION (TREE_TYPE (op1)))
1866 && useless_type_conversion_p (type, TREE_TYPE (op1)))
1868 wide_int w1 = wi::max_value (TREE_TYPE (op));
1869 wide_int w2 = wi::add (w1, 1);
1870 if (cmp == LT_EXPR)
1872 larger = op1;
1873 smaller = wide_int_to_tree (TREE_TYPE (op1), w1);
1874 alt_smaller = wide_int_to_tree (TREE_TYPE (op1), w2);
1875 alt_larger = NULL_TREE;
1877 else
1879 smaller = op1;
1880 larger = wide_int_to_tree (TREE_TYPE (op1), w1);
1881 alt_larger = wide_int_to_tree (TREE_TYPE (op1), w2);
1882 alt_smaller = NULL_TREE;
1889 /* We need to know which is the true edge and which is the false
1890 edge so that we know if have abs or negative abs. */
1891 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1893 /* Forward the edges over the middle basic block. */
1894 if (true_edge->dest == middle_bb)
1895 true_edge = EDGE_SUCC (true_edge->dest, 0);
1896 if (false_edge->dest == middle_bb)
1897 false_edge = EDGE_SUCC (false_edge->dest, 0);
1899 if (true_edge == e0)
1901 gcc_assert (false_edge == e1);
1902 arg_true = arg0;
1903 arg_false = arg1;
1905 else
1907 gcc_assert (false_edge == e0);
1908 gcc_assert (true_edge == e1);
1909 arg_true = arg1;
1910 arg_false = arg0;
1913 if (empty_block_p (middle_bb))
1915 if ((operand_equal_for_phi_arg_p (arg_true, smaller)
1916 || (alt_smaller
1917 && operand_equal_for_phi_arg_p (arg_true, alt_smaller)))
1918 && (operand_equal_for_phi_arg_p (arg_false, larger)
1919 || (alt_larger
1920 && operand_equal_for_phi_arg_p (arg_true, alt_larger))))
1922 /* Case
1924 if (smaller < larger)
1925 rslt = smaller;
1926 else
1927 rslt = larger; */
1928 minmax = MIN_EXPR;
1930 else if ((operand_equal_for_phi_arg_p (arg_false, smaller)
1931 || (alt_smaller
1932 && operand_equal_for_phi_arg_p (arg_false, alt_smaller)))
1933 && (operand_equal_for_phi_arg_p (arg_true, larger)
1934 || (alt_larger
1935 && operand_equal_for_phi_arg_p (arg_true, alt_larger))))
1936 minmax = MAX_EXPR;
1937 else
1938 return false;
1940 else
1942 /* Recognize the following case, assuming d <= u:
1944 if (a <= u)
1945 b = MAX (a, d);
1946 x = PHI <b, u>
1948 This is equivalent to
1950 b = MAX (a, d);
1951 x = MIN (b, u); */
1953 gimple *assign = last_and_only_stmt (middle_bb);
1954 tree lhs, op0, op1, bound;
1956 if (!single_pred_p (middle_bb))
1957 return false;
1959 if (!assign
1960 || gimple_code (assign) != GIMPLE_ASSIGN)
1961 return false;
1963 lhs = gimple_assign_lhs (assign);
1964 ass_code = gimple_assign_rhs_code (assign);
1965 if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
1966 return false;
1967 op0 = gimple_assign_rhs1 (assign);
1968 op1 = gimple_assign_rhs2 (assign);
1970 if (true_edge->src == middle_bb)
1972 /* We got here if the condition is true, i.e., SMALLER < LARGER. */
1973 if (!operand_equal_for_phi_arg_p (lhs, arg_true))
1974 return false;
1976 if (operand_equal_for_phi_arg_p (arg_false, larger)
1977 || (alt_larger
1978 && operand_equal_for_phi_arg_p (arg_false, alt_larger)))
1980 /* Case
1982 if (smaller < larger)
1984 r' = MAX_EXPR (smaller, bound)
1986 r = PHI <r', larger> --> to be turned to MIN_EXPR. */
1987 if (ass_code != MAX_EXPR)
1988 return false;
1990 minmax = MIN_EXPR;
1991 if (operand_equal_for_phi_arg_p (op0, smaller)
1992 || (alt_smaller
1993 && operand_equal_for_phi_arg_p (op0, alt_smaller)))
1994 bound = op1;
1995 else if (operand_equal_for_phi_arg_p (op1, smaller)
1996 || (alt_smaller
1997 && operand_equal_for_phi_arg_p (op1, alt_smaller)))
1998 bound = op0;
1999 else
2000 return false;
2002 /* We need BOUND <= LARGER. */
2003 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
2004 bound, larger)))
2005 return false;
2007 else if (operand_equal_for_phi_arg_p (arg_false, smaller)
2008 || (alt_smaller
2009 && operand_equal_for_phi_arg_p (arg_false, alt_smaller)))
2011 /* Case
2013 if (smaller < larger)
2015 r' = MIN_EXPR (larger, bound)
2017 r = PHI <r', smaller> --> to be turned to MAX_EXPR. */
2018 if (ass_code != MIN_EXPR)
2019 return false;
2021 minmax = MAX_EXPR;
2022 if (operand_equal_for_phi_arg_p (op0, larger)
2023 || (alt_larger
2024 && operand_equal_for_phi_arg_p (op0, alt_larger)))
2025 bound = op1;
2026 else if (operand_equal_for_phi_arg_p (op1, larger)
2027 || (alt_larger
2028 && operand_equal_for_phi_arg_p (op1, alt_larger)))
2029 bound = op0;
2030 else
2031 return false;
2033 /* We need BOUND >= SMALLER. */
2034 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
2035 bound, smaller)))
2036 return false;
2038 else
2039 return false;
2041 else
2043 /* We got here if the condition is false, i.e., SMALLER > LARGER. */
2044 if (!operand_equal_for_phi_arg_p (lhs, arg_false))
2045 return false;
2047 if (operand_equal_for_phi_arg_p (arg_true, larger)
2048 || (alt_larger
2049 && operand_equal_for_phi_arg_p (arg_true, alt_larger)))
2051 /* Case
2053 if (smaller > larger)
2055 r' = MIN_EXPR (smaller, bound)
2057 r = PHI <r', larger> --> to be turned to MAX_EXPR. */
2058 if (ass_code != MIN_EXPR)
2059 return false;
2061 minmax = MAX_EXPR;
2062 if (operand_equal_for_phi_arg_p (op0, smaller)
2063 || (alt_smaller
2064 && operand_equal_for_phi_arg_p (op0, alt_smaller)))
2065 bound = op1;
2066 else if (operand_equal_for_phi_arg_p (op1, smaller)
2067 || (alt_smaller
2068 && operand_equal_for_phi_arg_p (op1, alt_smaller)))
2069 bound = op0;
2070 else
2071 return false;
2073 /* We need BOUND >= LARGER. */
2074 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
2075 bound, larger)))
2076 return false;
2078 else if (operand_equal_for_phi_arg_p (arg_true, smaller)
2079 || (alt_smaller
2080 && operand_equal_for_phi_arg_p (arg_true, alt_smaller)))
2082 /* Case
2084 if (smaller > larger)
2086 r' = MAX_EXPR (larger, bound)
2088 r = PHI <r', smaller> --> to be turned to MIN_EXPR. */
2089 if (ass_code != MAX_EXPR)
2090 return false;
2092 minmax = MIN_EXPR;
2093 if (operand_equal_for_phi_arg_p (op0, larger))
2094 bound = op1;
2095 else if (operand_equal_for_phi_arg_p (op1, larger))
2096 bound = op0;
2097 else
2098 return false;
2100 /* We need BOUND <= SMALLER. */
2101 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
2102 bound, smaller)))
2103 return false;
2105 else
2106 return false;
2109 /* Move the statement from the middle block. */
2110 gsi = gsi_last_bb (cond_bb);
2111 gsi_from = gsi_last_nondebug_bb (middle_bb);
2112 reset_flow_sensitive_info (SINGLE_SSA_TREE_OPERAND (gsi_stmt (gsi_from),
2113 SSA_OP_DEF));
2114 gsi_move_before (&gsi_from, &gsi);
2117 /* Emit the statement to compute min/max. */
2118 gimple_seq stmts = NULL;
2119 tree phi_result = PHI_RESULT (phi);
2120 result = gimple_build (&stmts, minmax, TREE_TYPE (phi_result), arg0, arg1);
2122 gsi = gsi_last_bb (cond_bb);
2123 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2125 replace_phi_edge_with_variable (cond_bb, e1, phi, result);
2127 return true;
2130 /* Attempt to optimize (x <=> y) cmp 0 and similar comparisons.
2131 For strong ordering <=> try to match something like:
2132 <bb 2> : // cond3_bb (== cond2_bb)
2133 if (x_4(D) != y_5(D))
2134 goto <bb 3>; [INV]
2135 else
2136 goto <bb 6>; [INV]
2138 <bb 3> : // cond_bb
2139 if (x_4(D) < y_5(D))
2140 goto <bb 6>; [INV]
2141 else
2142 goto <bb 4>; [INV]
2144 <bb 4> : // middle_bb
2146 <bb 6> : // phi_bb
2147 # iftmp.0_2 = PHI <1(4), 0(2), -1(3)>
2148 _1 = iftmp.0_2 == 0;
2150 and for partial ordering <=> something like:
2152 <bb 2> : // cond3_bb
2153 if (a_3(D) == b_5(D))
2154 goto <bb 6>; [50.00%]
2155 else
2156 goto <bb 3>; [50.00%]
2158 <bb 3> [local count: 536870913]: // cond2_bb
2159 if (a_3(D) < b_5(D))
2160 goto <bb 6>; [50.00%]
2161 else
2162 goto <bb 4>; [50.00%]
2164 <bb 4> [local count: 268435456]: // cond_bb
2165 if (a_3(D) > b_5(D))
2166 goto <bb 6>; [50.00%]
2167 else
2168 goto <bb 5>; [50.00%]
2170 <bb 5> [local count: 134217728]: // middle_bb
2172 <bb 6> [local count: 1073741824]: // phi_bb
2173 # SR.27_4 = PHI <0(2), -1(3), 1(4), 2(5)>
2174 _2 = SR.27_4 > 0; */
2176 static bool
2177 spaceship_replacement (basic_block cond_bb, basic_block middle_bb,
2178 edge e0, edge e1, gphi *phi,
2179 tree arg0, tree arg1)
2181 tree phires = PHI_RESULT (phi);
2182 if (!INTEGRAL_TYPE_P (TREE_TYPE (phires))
2183 || TYPE_UNSIGNED (TREE_TYPE (phires))
2184 || !tree_fits_shwi_p (arg0)
2185 || !tree_fits_shwi_p (arg1)
2186 || !IN_RANGE (tree_to_shwi (arg0), -1, 2)
2187 || !IN_RANGE (tree_to_shwi (arg1), -1, 2))
2188 return false;
2190 basic_block phi_bb = gimple_bb (phi);
2191 gcc_assert (phi_bb == e0->dest && phi_bb == e1->dest);
2192 if (!IN_RANGE (EDGE_COUNT (phi_bb->preds), 3, 4))
2193 return false;
2195 use_operand_p use_p;
2196 gimple *use_stmt;
2197 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (phires))
2198 return false;
2199 if (!single_imm_use (phires, &use_p, &use_stmt))
2200 return false;
2201 enum tree_code cmp;
2202 tree lhs, rhs;
2203 gimple *orig_use_stmt = use_stmt;
2204 tree orig_use_lhs = NULL_TREE;
2205 int prec = TYPE_PRECISION (TREE_TYPE (phires));
2206 bool is_cast = false;
2208 /* Deal with the case when match.pd has rewritten the (res & ~1) == 0
2209 into res <= 1 and has left a type-cast for signed types. */
2210 if (gimple_assign_cast_p (use_stmt))
2212 orig_use_lhs = gimple_assign_lhs (use_stmt);
2213 /* match.pd would have only done this for a signed type,
2214 so the conversion must be to an unsigned one. */
2215 tree ty1 = TREE_TYPE (gimple_assign_rhs1 (use_stmt));
2216 tree ty2 = TREE_TYPE (orig_use_lhs);
2218 if (!TYPE_UNSIGNED (ty2) || !INTEGRAL_TYPE_P (ty2))
2219 return false;
2220 if (TYPE_PRECISION (ty1) != TYPE_PRECISION (ty2))
2221 return false;
2222 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
2223 return false;
2224 if (EDGE_COUNT (phi_bb->preds) != 4)
2225 return false;
2226 if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
2227 return false;
2229 is_cast = true;
2231 else if (is_gimple_assign (use_stmt)
2232 && gimple_assign_rhs_code (use_stmt) == BIT_AND_EXPR
2233 && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST
2234 && (wi::to_wide (gimple_assign_rhs2 (use_stmt))
2235 == wi::shifted_mask (1, prec - 1, false, prec)))
2237 /* For partial_ordering result operator>= with unspec as second
2238 argument is (res & 1) == res, folded by match.pd into
2239 (res & ~1) == 0. */
2240 orig_use_lhs = gimple_assign_lhs (use_stmt);
2241 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
2242 return false;
2243 if (EDGE_COUNT (phi_bb->preds) != 4)
2244 return false;
2245 if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
2246 return false;
2248 if (gimple_code (use_stmt) == GIMPLE_COND)
2250 cmp = gimple_cond_code (use_stmt);
2251 lhs = gimple_cond_lhs (use_stmt);
2252 rhs = gimple_cond_rhs (use_stmt);
2254 else if (is_gimple_assign (use_stmt))
2256 if (gimple_assign_rhs_class (use_stmt) == GIMPLE_BINARY_RHS)
2258 cmp = gimple_assign_rhs_code (use_stmt);
2259 lhs = gimple_assign_rhs1 (use_stmt);
2260 rhs = gimple_assign_rhs2 (use_stmt);
2262 else if (gimple_assign_rhs_code (use_stmt) == COND_EXPR)
2264 tree cond = gimple_assign_rhs1 (use_stmt);
2265 if (!COMPARISON_CLASS_P (cond))
2266 return false;
2267 cmp = TREE_CODE (cond);
2268 lhs = TREE_OPERAND (cond, 0);
2269 rhs = TREE_OPERAND (cond, 1);
2271 else
2272 return false;
2274 else
2275 return false;
2276 switch (cmp)
2278 case EQ_EXPR:
2279 case NE_EXPR:
2280 case LT_EXPR:
2281 case GT_EXPR:
2282 case LE_EXPR:
2283 case GE_EXPR:
2284 break;
2285 default:
2286 return false;
2288 if (lhs != (orig_use_lhs ? orig_use_lhs : phires)
2289 || !tree_fits_shwi_p (rhs)
2290 || !IN_RANGE (tree_to_shwi (rhs), -1, 1))
2291 return false;
2293 if (is_cast)
2295 if (TREE_CODE (rhs) != INTEGER_CST)
2296 return false;
2297 /* As for -ffast-math we assume the 2 return to be
2298 impossible, canonicalize (unsigned) res <= 1U or
2299 (unsigned) res < 2U into res >= 0 and (unsigned) res > 1U
2300 or (unsigned) res >= 2U as res < 0. */
2301 switch (cmp)
2303 case LE_EXPR:
2304 if (!integer_onep (rhs))
2305 return false;
2306 cmp = GE_EXPR;
2307 break;
2308 case LT_EXPR:
2309 if (wi::ne_p (wi::to_widest (rhs), 2))
2310 return false;
2311 cmp = GE_EXPR;
2312 break;
2313 case GT_EXPR:
2314 if (!integer_onep (rhs))
2315 return false;
2316 cmp = LT_EXPR;
2317 break;
2318 case GE_EXPR:
2319 if (wi::ne_p (wi::to_widest (rhs), 2))
2320 return false;
2321 cmp = LT_EXPR;
2322 break;
2323 default:
2324 return false;
2326 rhs = build_zero_cst (TREE_TYPE (phires));
2328 else if (orig_use_lhs)
2330 if ((cmp != EQ_EXPR && cmp != NE_EXPR) || !integer_zerop (rhs))
2331 return false;
2332 /* As for -ffast-math we assume the 2 return to be
2333 impossible, canonicalize (res & ~1) == 0 into
2334 res >= 0 and (res & ~1) != 0 as res < 0. */
2335 cmp = cmp == EQ_EXPR ? GE_EXPR : LT_EXPR;
2338 if (!empty_block_p (middle_bb))
2339 return false;
2341 gcond *cond1 = as_a <gcond *> (last_stmt (cond_bb));
2342 enum tree_code cmp1 = gimple_cond_code (cond1);
2343 switch (cmp1)
2345 case LT_EXPR:
2346 case LE_EXPR:
2347 case GT_EXPR:
2348 case GE_EXPR:
2349 break;
2350 default:
2351 return false;
2353 tree lhs1 = gimple_cond_lhs (cond1);
2354 tree rhs1 = gimple_cond_rhs (cond1);
2355 /* The optimization may be unsafe due to NaNs. */
2356 if (HONOR_NANS (TREE_TYPE (lhs1)))
2357 return false;
2358 if (TREE_CODE (lhs1) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs1))
2359 return false;
2360 if (TREE_CODE (rhs1) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1))
2361 return false;
2363 if (!single_pred_p (cond_bb) || !cond_only_block_p (cond_bb))
2364 return false;
2366 basic_block cond2_bb = single_pred (cond_bb);
2367 if (EDGE_COUNT (cond2_bb->succs) != 2)
2368 return false;
2369 edge cond2_phi_edge;
2370 if (EDGE_SUCC (cond2_bb, 0)->dest == cond_bb)
2372 if (EDGE_SUCC (cond2_bb, 1)->dest != phi_bb)
2373 return false;
2374 cond2_phi_edge = EDGE_SUCC (cond2_bb, 1);
2376 else if (EDGE_SUCC (cond2_bb, 0)->dest != phi_bb)
2377 return false;
2378 else
2379 cond2_phi_edge = EDGE_SUCC (cond2_bb, 0);
2380 tree arg2 = gimple_phi_arg_def (phi, cond2_phi_edge->dest_idx);
2381 if (!tree_fits_shwi_p (arg2))
2382 return false;
2383 gimple *cond2 = last_stmt (cond2_bb);
2384 if (cond2 == NULL || gimple_code (cond2) != GIMPLE_COND)
2385 return false;
2386 enum tree_code cmp2 = gimple_cond_code (cond2);
2387 tree lhs2 = gimple_cond_lhs (cond2);
2388 tree rhs2 = gimple_cond_rhs (cond2);
2389 if (lhs2 == lhs1)
2391 if (!operand_equal_p (rhs2, rhs1, 0))
2393 if ((cmp2 == EQ_EXPR || cmp2 == NE_EXPR)
2394 && TREE_CODE (rhs1) == INTEGER_CST
2395 && TREE_CODE (rhs2) == INTEGER_CST)
2397 /* For integers, we can have cond2 x == 5
2398 and cond1 x < 5, x <= 4, x <= 5, x < 6,
2399 x > 5, x >= 6, x >= 5 or x > 4. */
2400 if (tree_int_cst_lt (rhs1, rhs2))
2402 if (wi::ne_p (wi::to_wide (rhs1) + 1, wi::to_wide (rhs2)))
2403 return false;
2404 if (cmp1 == LE_EXPR)
2405 cmp1 = LT_EXPR;
2406 else if (cmp1 == GT_EXPR)
2407 cmp1 = GE_EXPR;
2408 else
2409 return false;
2411 else
2413 gcc_checking_assert (tree_int_cst_lt (rhs2, rhs1));
2414 if (wi::ne_p (wi::to_wide (rhs2) + 1, wi::to_wide (rhs1)))
2415 return false;
2416 if (cmp1 == LT_EXPR)
2417 cmp1 = LE_EXPR;
2418 else if (cmp1 == GE_EXPR)
2419 cmp1 = GT_EXPR;
2420 else
2421 return false;
2423 rhs1 = rhs2;
2425 else
2426 return false;
2429 else if (lhs2 == rhs1)
2431 if (rhs2 != lhs1)
2432 return false;
2434 else
2435 return false;
2437 tree arg3 = arg2;
2438 basic_block cond3_bb = cond2_bb;
2439 edge cond3_phi_edge = cond2_phi_edge;
2440 gimple *cond3 = cond2;
2441 enum tree_code cmp3 = cmp2;
2442 tree lhs3 = lhs2;
2443 tree rhs3 = rhs2;
2444 if (EDGE_COUNT (phi_bb->preds) == 4)
2446 if (absu_hwi (tree_to_shwi (arg2)) != 1)
2447 return false;
2448 if (e1->flags & EDGE_TRUE_VALUE)
2450 if (tree_to_shwi (arg0) != 2
2451 || absu_hwi (tree_to_shwi (arg1)) != 1
2452 || wi::to_widest (arg1) == wi::to_widest (arg2))
2453 return false;
2455 else if (tree_to_shwi (arg1) != 2
2456 || absu_hwi (tree_to_shwi (arg0)) != 1
2457 || wi::to_widest (arg0) == wi::to_widest (arg1))
2458 return false;
2459 switch (cmp2)
2461 case LT_EXPR:
2462 case LE_EXPR:
2463 case GT_EXPR:
2464 case GE_EXPR:
2465 break;
2466 default:
2467 return false;
2469 /* if (x < y) goto phi_bb; else fallthru;
2470 if (x > y) goto phi_bb; else fallthru;
2471 bbx:;
2472 phi_bb:;
2473 is ok, but if x and y are swapped in one of the comparisons,
2474 or the comparisons are the same and operands not swapped,
2475 or the true and false edges are swapped, it is not. */
2476 if ((lhs2 == lhs1)
2477 ^ (((cond2_phi_edge->flags
2478 & ((cmp2 == LT_EXPR || cmp2 == LE_EXPR)
2479 ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE)) != 0)
2480 != ((e1->flags
2481 & ((cmp1 == LT_EXPR || cmp1 == LE_EXPR)
2482 ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE)) != 0)))
2483 return false;
2484 if (!single_pred_p (cond2_bb) || !cond_only_block_p (cond2_bb))
2485 return false;
2486 cond3_bb = single_pred (cond2_bb);
2487 if (EDGE_COUNT (cond2_bb->succs) != 2)
2488 return false;
2489 if (EDGE_SUCC (cond3_bb, 0)->dest == cond2_bb)
2491 if (EDGE_SUCC (cond3_bb, 1)->dest != phi_bb)
2492 return false;
2493 cond3_phi_edge = EDGE_SUCC (cond3_bb, 1);
2495 else if (EDGE_SUCC (cond3_bb, 0)->dest != phi_bb)
2496 return false;
2497 else
2498 cond3_phi_edge = EDGE_SUCC (cond3_bb, 0);
2499 arg3 = gimple_phi_arg_def (phi, cond3_phi_edge->dest_idx);
2500 cond3 = last_stmt (cond3_bb);
2501 if (cond3 == NULL || gimple_code (cond3) != GIMPLE_COND)
2502 return false;
2503 cmp3 = gimple_cond_code (cond3);
2504 lhs3 = gimple_cond_lhs (cond3);
2505 rhs3 = gimple_cond_rhs (cond3);
2506 if (lhs3 == lhs1)
2508 if (!operand_equal_p (rhs3, rhs1, 0))
2509 return false;
2511 else if (lhs3 == rhs1)
2513 if (rhs3 != lhs1)
2514 return false;
2516 else
2517 return false;
2519 else if (absu_hwi (tree_to_shwi (arg0)) != 1
2520 || absu_hwi (tree_to_shwi (arg1)) != 1
2521 || wi::to_widest (arg0) == wi::to_widest (arg1))
2522 return false;
2524 if (!integer_zerop (arg3) || (cmp3 != EQ_EXPR && cmp3 != NE_EXPR))
2525 return false;
2526 if ((cond3_phi_edge->flags & (cmp3 == EQ_EXPR
2527 ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE)) == 0)
2528 return false;
2530 /* lhs1 one_cmp rhs1 results in phires of 1. */
2531 enum tree_code one_cmp;
2532 if ((cmp1 == LT_EXPR || cmp1 == LE_EXPR)
2533 ^ (!integer_onep ((e1->flags & EDGE_TRUE_VALUE) ? arg1 : arg0)))
2534 one_cmp = LT_EXPR;
2535 else
2536 one_cmp = GT_EXPR;
2538 enum tree_code res_cmp;
2539 switch (cmp)
2541 case EQ_EXPR:
2542 if (integer_zerop (rhs))
2543 res_cmp = EQ_EXPR;
2544 else if (integer_minus_onep (rhs))
2545 res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
2546 else if (integer_onep (rhs))
2547 res_cmp = one_cmp;
2548 else
2549 return false;
2550 break;
2551 case NE_EXPR:
2552 if (integer_zerop (rhs))
2553 res_cmp = NE_EXPR;
2554 else if (integer_minus_onep (rhs))
2555 res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
2556 else if (integer_onep (rhs))
2557 res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
2558 else
2559 return false;
2560 break;
2561 case LT_EXPR:
2562 if (integer_onep (rhs))
2563 res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
2564 else if (integer_zerop (rhs))
2565 res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
2566 else
2567 return false;
2568 break;
2569 case LE_EXPR:
2570 if (integer_zerop (rhs))
2571 res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
2572 else if (integer_minus_onep (rhs))
2573 res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
2574 else
2575 return false;
2576 break;
2577 case GT_EXPR:
2578 if (integer_minus_onep (rhs))
2579 res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
2580 else if (integer_zerop (rhs))
2581 res_cmp = one_cmp;
2582 else
2583 return false;
2584 break;
2585 case GE_EXPR:
2586 if (integer_zerop (rhs))
2587 res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
2588 else if (integer_onep (rhs))
2589 res_cmp = one_cmp;
2590 else
2591 return false;
2592 break;
2593 default:
2594 gcc_unreachable ();
2597 if (gimple_code (use_stmt) == GIMPLE_COND)
2599 gcond *use_cond = as_a <gcond *> (use_stmt);
2600 gimple_cond_set_code (use_cond, res_cmp);
2601 gimple_cond_set_lhs (use_cond, lhs1);
2602 gimple_cond_set_rhs (use_cond, rhs1);
2604 else if (gimple_assign_rhs_class (use_stmt) == GIMPLE_BINARY_RHS)
2606 gimple_assign_set_rhs_code (use_stmt, res_cmp);
2607 gimple_assign_set_rhs1 (use_stmt, lhs1);
2608 gimple_assign_set_rhs2 (use_stmt, rhs1);
2610 else
2612 tree cond = build2 (res_cmp, TREE_TYPE (gimple_assign_rhs1 (use_stmt)),
2613 lhs1, rhs1);
2614 gimple_assign_set_rhs1 (use_stmt, cond);
2616 update_stmt (use_stmt);
2618 if (MAY_HAVE_DEBUG_BIND_STMTS)
2620 use_operand_p use_p;
2621 imm_use_iterator iter;
2622 bool has_debug_uses = false;
2623 bool has_cast_debug_uses = false;
2624 FOR_EACH_IMM_USE_FAST (use_p, iter, phires)
2626 gimple *use_stmt = USE_STMT (use_p);
2627 if (orig_use_lhs && use_stmt == orig_use_stmt)
2628 continue;
2629 gcc_assert (is_gimple_debug (use_stmt));
2630 has_debug_uses = true;
2631 break;
2633 if (orig_use_lhs)
2635 if (!has_debug_uses || is_cast)
2636 FOR_EACH_IMM_USE_FAST (use_p, iter, orig_use_lhs)
2638 gimple *use_stmt = USE_STMT (use_p);
2639 gcc_assert (is_gimple_debug (use_stmt));
2640 has_debug_uses = true;
2641 if (is_cast)
2642 has_cast_debug_uses = true;
2644 gimple_stmt_iterator gsi = gsi_for_stmt (orig_use_stmt);
2645 tree zero = build_zero_cst (TREE_TYPE (orig_use_lhs));
2646 gimple_assign_set_rhs_with_ops (&gsi, INTEGER_CST, zero);
2647 update_stmt (orig_use_stmt);
2650 if (has_debug_uses)
2652 /* If there are debug uses, emit something like:
2653 # DEBUG D#1 => i_2(D) > j_3(D) ? 1 : -1
2654 # DEBUG D#2 => i_2(D) == j_3(D) ? 0 : D#1
2655 where > stands for the comparison that yielded 1
2656 and replace debug uses of phi result with that D#2.
2657 Ignore the value of 2, because if NaNs aren't expected,
2658 all floating point numbers should be comparable. */
2659 gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi));
2660 tree type = TREE_TYPE (phires);
2661 tree temp1 = build_debug_expr_decl (type);
2662 tree t = build2 (one_cmp, boolean_type_node, lhs1, rhs2);
2663 t = build3 (COND_EXPR, type, t, build_one_cst (type),
2664 build_int_cst (type, -1));
2665 gimple *g = gimple_build_debug_bind (temp1, t, phi);
2666 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2667 tree temp2 = build_debug_expr_decl (type);
2668 t = build2 (EQ_EXPR, boolean_type_node, lhs1, rhs2);
2669 t = build3 (COND_EXPR, type, t, build_zero_cst (type), temp1);
2670 g = gimple_build_debug_bind (temp2, t, phi);
2671 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2672 replace_uses_by (phires, temp2);
2673 if (orig_use_lhs)
2675 if (has_cast_debug_uses)
2677 tree temp3 = make_node (DEBUG_EXPR_DECL);
2678 DECL_ARTIFICIAL (temp3) = 1;
2679 TREE_TYPE (temp3) = TREE_TYPE (orig_use_lhs);
2680 SET_DECL_MODE (temp3, TYPE_MODE (type));
2681 t = fold_convert (TREE_TYPE (temp3), temp2);
2682 g = gimple_build_debug_bind (temp3, t, phi);
2683 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2684 replace_uses_by (orig_use_lhs, temp3);
2686 else
2687 replace_uses_by (orig_use_lhs, temp2);
2692 if (orig_use_lhs)
2694 gimple_stmt_iterator gsi = gsi_for_stmt (orig_use_stmt);
2695 gsi_remove (&gsi, true);
2698 gimple_stmt_iterator psi = gsi_for_stmt (phi);
2699 remove_phi_node (&psi, true);
2700 statistics_counter_event (cfun, "spaceship replacement", 1);
2702 return true;
2705 /* Optimize x ? __builtin_fun (x) : C, where C is __builtin_fun (0).
2706 Convert
2708 <bb 2>
2709 if (b_4(D) != 0)
2710 goto <bb 3>
2711 else
2712 goto <bb 4>
2714 <bb 3>
2715 _2 = (unsigned long) b_4(D);
2716 _9 = __builtin_popcountl (_2);
2718 _9 = __builtin_popcountl (b_4(D));
2720 <bb 4>
2721 c_12 = PHI <0(2), _9(3)>
2723 Into
2724 <bb 2>
2725 _2 = (unsigned long) b_4(D);
2726 _9 = __builtin_popcountl (_2);
2728 _9 = __builtin_popcountl (b_4(D));
2730 <bb 4>
2731 c_12 = PHI <_9(2)>
2733 Similarly for __builtin_clz or __builtin_ctz if
2734 C?Z_DEFINED_VALUE_AT_ZERO is 2, optab is present and
2735 instead of 0 above it uses the value from that macro. */
2737 static bool
2738 cond_removal_in_builtin_zero_pattern (basic_block cond_bb,
2739 basic_block middle_bb,
2740 edge e1, edge e2, gphi *phi,
2741 tree arg0, tree arg1)
2743 gimple *cond;
2744 gimple_stmt_iterator gsi, gsi_from;
2745 gimple *call;
2746 gimple *cast = NULL;
2747 tree lhs, arg;
2749 /* Check that
2750 _2 = (unsigned long) b_4(D);
2751 _9 = __builtin_popcountl (_2);
2753 _9 = __builtin_popcountl (b_4(D));
2754 are the only stmts in the middle_bb. */
2756 gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
2757 if (gsi_end_p (gsi))
2758 return false;
2759 cast = gsi_stmt (gsi);
2760 gsi_next_nondebug (&gsi);
2761 if (!gsi_end_p (gsi))
2763 call = gsi_stmt (gsi);
2764 gsi_next_nondebug (&gsi);
2765 if (!gsi_end_p (gsi))
2766 return false;
2768 else
2770 call = cast;
2771 cast = NULL;
2774 /* Check that we have a popcount/clz/ctz builtin. */
2775 if (!is_gimple_call (call) || gimple_call_num_args (call) != 1)
2776 return false;
2778 arg = gimple_call_arg (call, 0);
2779 lhs = gimple_get_lhs (call);
2781 if (lhs == NULL_TREE)
2782 return false;
2784 combined_fn cfn = gimple_call_combined_fn (call);
2785 internal_fn ifn = IFN_LAST;
2786 int val = 0;
2787 switch (cfn)
2789 case CFN_BUILT_IN_BSWAP16:
2790 case CFN_BUILT_IN_BSWAP32:
2791 case CFN_BUILT_IN_BSWAP64:
2792 case CFN_BUILT_IN_BSWAP128:
2793 CASE_CFN_FFS:
2794 CASE_CFN_PARITY:
2795 CASE_CFN_POPCOUNT:
2796 break;
2797 CASE_CFN_CLZ:
2798 if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
2800 tree type = TREE_TYPE (arg);
2801 if (direct_internal_fn_supported_p (IFN_CLZ, type, OPTIMIZE_FOR_BOTH)
2802 && CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type),
2803 val) == 2)
2805 ifn = IFN_CLZ;
2806 break;
2809 return false;
2810 CASE_CFN_CTZ:
2811 if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
2813 tree type = TREE_TYPE (arg);
2814 if (direct_internal_fn_supported_p (IFN_CTZ, type, OPTIMIZE_FOR_BOTH)
2815 && CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type),
2816 val) == 2)
2818 ifn = IFN_CTZ;
2819 break;
2822 return false;
2823 case CFN_BUILT_IN_CLRSB:
2824 val = TYPE_PRECISION (integer_type_node) - 1;
2825 break;
2826 case CFN_BUILT_IN_CLRSBL:
2827 val = TYPE_PRECISION (long_integer_type_node) - 1;
2828 break;
2829 case CFN_BUILT_IN_CLRSBLL:
2830 val = TYPE_PRECISION (long_long_integer_type_node) - 1;
2831 break;
2832 default:
2833 return false;
2836 if (cast)
2838 /* We have a cast stmt feeding popcount/clz/ctz builtin. */
2839 /* Check that we have a cast prior to that. */
2840 if (gimple_code (cast) != GIMPLE_ASSIGN
2841 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (cast)))
2842 return false;
2843 /* Result of the cast stmt is the argument to the builtin. */
2844 if (arg != gimple_assign_lhs (cast))
2845 return false;
2846 arg = gimple_assign_rhs1 (cast);
2849 cond = last_stmt (cond_bb);
2851 /* Cond_bb has a check for b_4 [!=|==] 0 before calling the popcount/clz/ctz
2852 builtin. */
2853 if (gimple_code (cond) != GIMPLE_COND
2854 || (gimple_cond_code (cond) != NE_EXPR
2855 && gimple_cond_code (cond) != EQ_EXPR)
2856 || !integer_zerop (gimple_cond_rhs (cond))
2857 || arg != gimple_cond_lhs (cond))
2858 return false;
2860 /* Canonicalize. */
2861 if ((e2->flags & EDGE_TRUE_VALUE
2862 && gimple_cond_code (cond) == NE_EXPR)
2863 || (e1->flags & EDGE_TRUE_VALUE
2864 && gimple_cond_code (cond) == EQ_EXPR))
2866 std::swap (arg0, arg1);
2867 std::swap (e1, e2);
2870 /* Check PHI arguments. */
2871 if (lhs != arg0
2872 || TREE_CODE (arg1) != INTEGER_CST
2873 || wi::to_wide (arg1) != val)
2874 return false;
2876 /* And insert the popcount/clz/ctz builtin and cast stmt before the
2877 cond_bb. */
2878 gsi = gsi_last_bb (cond_bb);
2879 if (cast)
2881 gsi_from = gsi_for_stmt (cast);
2882 gsi_move_before (&gsi_from, &gsi);
2883 reset_flow_sensitive_info (gimple_get_lhs (cast));
2885 gsi_from = gsi_for_stmt (call);
2886 if (ifn == IFN_LAST || gimple_call_internal_p (call))
2887 gsi_move_before (&gsi_from, &gsi);
2888 else
2890 /* For __builtin_c[lt]z* force .C[LT]Z ifn, because only
2891 the latter is well defined at zero. */
2892 call = gimple_build_call_internal (ifn, 1, gimple_call_arg (call, 0));
2893 gimple_call_set_lhs (call, lhs);
2894 gsi_insert_before (&gsi, call, GSI_SAME_STMT);
2895 gsi_remove (&gsi_from, true);
2897 reset_flow_sensitive_info (lhs);
2899 /* Now update the PHI and remove unneeded bbs. */
2900 replace_phi_edge_with_variable (cond_bb, e2, phi, lhs);
2901 return true;
2904 /* Auxiliary functions to determine the set of memory accesses which
2905 can't trap because they are preceded by accesses to the same memory
2906 portion. We do that for MEM_REFs, so we only need to track
2907 the SSA_NAME of the pointer indirectly referenced. The algorithm
2908 simply is a walk over all instructions in dominator order. When
2909 we see an MEM_REF we determine if we've already seen a same
2910 ref anywhere up to the root of the dominator tree. If we do the
2911 current access can't trap. If we don't see any dominating access
2912 the current access might trap, but might also make later accesses
2913 non-trapping, so we remember it. We need to be careful with loads
2914 or stores, for instance a load might not trap, while a store would,
2915 so if we see a dominating read access this doesn't mean that a later
2916 write access would not trap. Hence we also need to differentiate the
2917 type of access(es) seen.
2919 ??? We currently are very conservative and assume that a load might
2920 trap even if a store doesn't (write-only memory). This probably is
2921 overly conservative.
2923 We currently support a special case that for !TREE_ADDRESSABLE automatic
2924 variables, it could ignore whether something is a load or store because the
2925 local stack should be always writable. */
2927 /* A hash-table of references (MEM_REF/ARRAY_REF/COMPONENT_REF), and in which
2928 basic block an *_REF through it was seen, which would constitute a
2929 no-trap region for same accesses.
2931 Size is needed to support 2 MEM_REFs of different types, like
2932 MEM<double>(s_1) and MEM<long>(s_1), which would compare equal with
2933 OEP_ADDRESS_OF. */
2934 struct ref_to_bb
2936 tree exp;
2937 HOST_WIDE_INT size;
2938 unsigned int phase;
2939 basic_block bb;
2942 /* Hashtable helpers. */
2944 struct refs_hasher : free_ptr_hash<ref_to_bb>
2946 static inline hashval_t hash (const ref_to_bb *);
2947 static inline bool equal (const ref_to_bb *, const ref_to_bb *);
2950 /* Used for quick clearing of the hash-table when we see calls.
2951 Hash entries with phase < nt_call_phase are invalid. */
2952 static unsigned int nt_call_phase;
2954 /* The hash function. */
2956 inline hashval_t
2957 refs_hasher::hash (const ref_to_bb *n)
2959 inchash::hash hstate;
2960 inchash::add_expr (n->exp, hstate, OEP_ADDRESS_OF);
2961 hstate.add_hwi (n->size);
2962 return hstate.end ();
2965 /* The equality function of *P1 and *P2. */
2967 inline bool
2968 refs_hasher::equal (const ref_to_bb *n1, const ref_to_bb *n2)
2970 return operand_equal_p (n1->exp, n2->exp, OEP_ADDRESS_OF)
2971 && n1->size == n2->size;
2974 class nontrapping_dom_walker : public dom_walker
2976 public:
2977 nontrapping_dom_walker (cdi_direction direction, hash_set<tree> *ps)
2978 : dom_walker (direction), m_nontrapping (ps), m_seen_refs (128)
2981 virtual edge before_dom_children (basic_block);
2982 virtual void after_dom_children (basic_block);
2984 private:
2986 /* We see the expression EXP in basic block BB. If it's an interesting
2987 expression (an MEM_REF through an SSA_NAME) possibly insert the
2988 expression into the set NONTRAP or the hash table of seen expressions.
2989 STORE is true if this expression is on the LHS, otherwise it's on
2990 the RHS. */
2991 void add_or_mark_expr (basic_block, tree, bool);
2993 hash_set<tree> *m_nontrapping;
2995 /* The hash table for remembering what we've seen. */
2996 hash_table<refs_hasher> m_seen_refs;
2999 /* Called by walk_dominator_tree, when entering the block BB. */
3000 edge
3001 nontrapping_dom_walker::before_dom_children (basic_block bb)
3003 edge e;
3004 edge_iterator ei;
3005 gimple_stmt_iterator gsi;
3007 /* If we haven't seen all our predecessors, clear the hash-table. */
3008 FOR_EACH_EDGE (e, ei, bb->preds)
3009 if ((((size_t)e->src->aux) & 2) == 0)
3011 nt_call_phase++;
3012 break;
3015 /* Mark this BB as being on the path to dominator root and as visited. */
3016 bb->aux = (void*)(1 | 2);
3018 /* And walk the statements in order. */
3019 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3021 gimple *stmt = gsi_stmt (gsi);
3023 if ((gimple_code (stmt) == GIMPLE_ASM && gimple_vdef (stmt))
3024 || (is_gimple_call (stmt)
3025 && (!nonfreeing_call_p (stmt) || !nonbarrier_call_p (stmt))))
3026 nt_call_phase++;
3027 else if (gimple_assign_single_p (stmt) && !gimple_has_volatile_ops (stmt))
3029 add_or_mark_expr (bb, gimple_assign_lhs (stmt), true);
3030 add_or_mark_expr (bb, gimple_assign_rhs1 (stmt), false);
3033 return NULL;
3036 /* Called by walk_dominator_tree, when basic block BB is exited. */
3037 void
3038 nontrapping_dom_walker::after_dom_children (basic_block bb)
3040 /* This BB isn't on the path to dominator root anymore. */
3041 bb->aux = (void*)2;
3044 /* We see the expression EXP in basic block BB. If it's an interesting
3045 expression of:
3046 1) MEM_REF
3047 2) ARRAY_REF
3048 3) COMPONENT_REF
3049 possibly insert the expression into the set NONTRAP or the hash table
3050 of seen expressions. STORE is true if this expression is on the LHS,
3051 otherwise it's on the RHS. */
3052 void
3053 nontrapping_dom_walker::add_or_mark_expr (basic_block bb, tree exp, bool store)
3055 HOST_WIDE_INT size;
3057 if ((TREE_CODE (exp) == MEM_REF || TREE_CODE (exp) == ARRAY_REF
3058 || TREE_CODE (exp) == COMPONENT_REF)
3059 && (size = int_size_in_bytes (TREE_TYPE (exp))) > 0)
3061 struct ref_to_bb map;
3062 ref_to_bb **slot;
3063 struct ref_to_bb *r2bb;
3064 basic_block found_bb = 0;
3066 if (!store)
3068 tree base = get_base_address (exp);
3069 /* Only record a LOAD of a local variable without address-taken, as
3070 the local stack is always writable. This allows cselim on a STORE
3071 with a dominating LOAD. */
3072 if (!auto_var_p (base) || TREE_ADDRESSABLE (base))
3073 return;
3076 /* Try to find the last seen *_REF, which can trap. */
3077 map.exp = exp;
3078 map.size = size;
3079 slot = m_seen_refs.find_slot (&map, INSERT);
3080 r2bb = *slot;
3081 if (r2bb && r2bb->phase >= nt_call_phase)
3082 found_bb = r2bb->bb;
3084 /* If we've found a trapping *_REF, _and_ it dominates EXP
3085 (it's in a basic block on the path from us to the dominator root)
3086 then we can't trap. */
3087 if (found_bb && (((size_t)found_bb->aux) & 1) == 1)
3089 m_nontrapping->add (exp);
3091 else
3093 /* EXP might trap, so insert it into the hash table. */
3094 if (r2bb)
3096 r2bb->phase = nt_call_phase;
3097 r2bb->bb = bb;
3099 else
3101 r2bb = XNEW (struct ref_to_bb);
3102 r2bb->phase = nt_call_phase;
3103 r2bb->bb = bb;
3104 r2bb->exp = exp;
3105 r2bb->size = size;
3106 *slot = r2bb;
3112 /* This is the entry point of gathering non trapping memory accesses.
3113 It will do a dominator walk over the whole function, and it will
3114 make use of the bb->aux pointers. It returns a set of trees
3115 (the MEM_REFs itself) which can't trap. */
3116 static hash_set<tree> *
3117 get_non_trapping (void)
3119 nt_call_phase = 0;
3120 hash_set<tree> *nontrap = new hash_set<tree>;
3122 nontrapping_dom_walker (CDI_DOMINATORS, nontrap)
3123 .walk (cfun->cfg->x_entry_block_ptr);
3125 clear_aux_for_blocks ();
3126 return nontrap;
3129 /* Do the main work of conditional store replacement. We already know
3130 that the recognized pattern looks like so:
3132 split:
3133 if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
3134 MIDDLE_BB:
3135 something
3136 fallthrough (edge E0)
3137 JOIN_BB:
3138 some more
3140 We check that MIDDLE_BB contains only one store, that that store
3141 doesn't trap (not via NOTRAP, but via checking if an access to the same
3142 memory location dominates us, or the store is to a local addressable
3143 object) and that the store has a "simple" RHS. */
3145 static bool
3146 cond_store_replacement (basic_block middle_bb, basic_block join_bb,
3147 edge e0, edge e1, hash_set<tree> *nontrap)
3149 gimple *assign = last_and_only_stmt (middle_bb);
3150 tree lhs, rhs, name, name2;
3151 gphi *newphi;
3152 gassign *new_stmt;
3153 gimple_stmt_iterator gsi;
3154 location_t locus;
3156 /* Check if middle_bb contains of only one store. */
3157 if (!assign
3158 || !gimple_assign_single_p (assign)
3159 || gimple_has_volatile_ops (assign))
3160 return false;
3162 /* And no PHI nodes so all uses in the single stmt are also
3163 available where we insert to. */
3164 if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
3165 return false;
3167 locus = gimple_location (assign);
3168 lhs = gimple_assign_lhs (assign);
3169 rhs = gimple_assign_rhs1 (assign);
3170 if ((!REFERENCE_CLASS_P (lhs)
3171 && !DECL_P (lhs))
3172 || !is_gimple_reg_type (TREE_TYPE (lhs)))
3173 return false;
3175 /* Prove that we can move the store down. We could also check
3176 TREE_THIS_NOTRAP here, but in that case we also could move stores,
3177 whose value is not available readily, which we want to avoid. */
3178 if (!nontrap->contains (lhs))
3180 /* If LHS is an access to a local variable without address-taken
3181 (or when we allow data races) and known not to trap, we could
3182 always safely move down the store. */
3183 tree base = get_base_address (lhs);
3184 if (!auto_var_p (base)
3185 || (TREE_ADDRESSABLE (base) && !flag_store_data_races)
3186 || tree_could_trap_p (lhs))
3187 return false;
3190 /* Now we've checked the constraints, so do the transformation:
3191 1) Remove the single store. */
3192 gsi = gsi_for_stmt (assign);
3193 unlink_stmt_vdef (assign);
3194 gsi_remove (&gsi, true);
3195 release_defs (assign);
3197 /* Make both store and load use alias-set zero as we have to
3198 deal with the case of the store being a conditional change
3199 of the dynamic type. */
3200 lhs = unshare_expr (lhs);
3201 tree *basep = &lhs;
3202 while (handled_component_p (*basep))
3203 basep = &TREE_OPERAND (*basep, 0);
3204 if (TREE_CODE (*basep) == MEM_REF
3205 || TREE_CODE (*basep) == TARGET_MEM_REF)
3206 TREE_OPERAND (*basep, 1)
3207 = fold_convert (ptr_type_node, TREE_OPERAND (*basep, 1));
3208 else
3209 *basep = build2 (MEM_REF, TREE_TYPE (*basep),
3210 build_fold_addr_expr (*basep),
3211 build_zero_cst (ptr_type_node));
3213 /* 2) Insert a load from the memory of the store to the temporary
3214 on the edge which did not contain the store. */
3215 name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3216 new_stmt = gimple_build_assign (name, lhs);
3217 gimple_set_location (new_stmt, locus);
3218 lhs = unshare_expr (lhs);
3220 /* Set the no-warning bit on the rhs of the load to avoid uninit
3221 warnings. */
3222 tree rhs1 = gimple_assign_rhs1 (new_stmt);
3223 suppress_warning (rhs1, OPT_Wuninitialized);
3225 gsi_insert_on_edge (e1, new_stmt);
3227 /* 3) Create a PHI node at the join block, with one argument
3228 holding the old RHS, and the other holding the temporary
3229 where we stored the old memory contents. */
3230 name2 = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3231 newphi = create_phi_node (name2, join_bb);
3232 add_phi_arg (newphi, rhs, e0, locus);
3233 add_phi_arg (newphi, name, e1, locus);
3235 new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
3237 /* 4) Insert that PHI node. */
3238 gsi = gsi_after_labels (join_bb);
3239 if (gsi_end_p (gsi))
3241 gsi = gsi_last_bb (join_bb);
3242 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
3244 else
3245 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
3247 if (dump_file && (dump_flags & TDF_DETAILS))
3249 fprintf (dump_file, "\nConditional store replacement happened!");
3250 fprintf (dump_file, "\nReplaced the store with a load.");
3251 fprintf (dump_file, "\nInserted a new PHI statement in joint block:\n");
3252 print_gimple_stmt (dump_file, new_stmt, 0, TDF_VOPS|TDF_MEMSYMS);
3254 statistics_counter_event (cfun, "conditional store replacement", 1);
3256 return true;
3259 /* Do the main work of conditional store replacement. */
3261 static bool
3262 cond_if_else_store_replacement_1 (basic_block then_bb, basic_block else_bb,
3263 basic_block join_bb, gimple *then_assign,
3264 gimple *else_assign)
3266 tree lhs_base, lhs, then_rhs, else_rhs, name;
3267 location_t then_locus, else_locus;
3268 gimple_stmt_iterator gsi;
3269 gphi *newphi;
3270 gassign *new_stmt;
3272 if (then_assign == NULL
3273 || !gimple_assign_single_p (then_assign)
3274 || gimple_clobber_p (then_assign)
3275 || gimple_has_volatile_ops (then_assign)
3276 || else_assign == NULL
3277 || !gimple_assign_single_p (else_assign)
3278 || gimple_clobber_p (else_assign)
3279 || gimple_has_volatile_ops (else_assign))
3280 return false;
3282 lhs = gimple_assign_lhs (then_assign);
3283 if (!is_gimple_reg_type (TREE_TYPE (lhs))
3284 || !operand_equal_p (lhs, gimple_assign_lhs (else_assign), 0))
3285 return false;
3287 lhs_base = get_base_address (lhs);
3288 if (lhs_base == NULL_TREE
3289 || (!DECL_P (lhs_base) && TREE_CODE (lhs_base) != MEM_REF))
3290 return false;
3292 then_rhs = gimple_assign_rhs1 (then_assign);
3293 else_rhs = gimple_assign_rhs1 (else_assign);
3294 then_locus = gimple_location (then_assign);
3295 else_locus = gimple_location (else_assign);
3297 /* Now we've checked the constraints, so do the transformation:
3298 1) Remove the stores. */
3299 gsi = gsi_for_stmt (then_assign);
3300 unlink_stmt_vdef (then_assign);
3301 gsi_remove (&gsi, true);
3302 release_defs (then_assign);
3304 gsi = gsi_for_stmt (else_assign);
3305 unlink_stmt_vdef (else_assign);
3306 gsi_remove (&gsi, true);
3307 release_defs (else_assign);
3309 /* 2) Create a PHI node at the join block, with one argument
3310 holding the old RHS, and the other holding the temporary
3311 where we stored the old memory contents. */
3312 name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3313 newphi = create_phi_node (name, join_bb);
3314 add_phi_arg (newphi, then_rhs, EDGE_SUCC (then_bb, 0), then_locus);
3315 add_phi_arg (newphi, else_rhs, EDGE_SUCC (else_bb, 0), else_locus);
3317 new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
3319 /* 3) Insert that PHI node. */
3320 gsi = gsi_after_labels (join_bb);
3321 if (gsi_end_p (gsi))
3323 gsi = gsi_last_bb (join_bb);
3324 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
3326 else
3327 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
3329 statistics_counter_event (cfun, "if-then-else store replacement", 1);
3331 return true;
3334 /* Return the single store in BB with VDEF or NULL if there are
3335 other stores in the BB or loads following the store. */
3337 static gimple *
3338 single_trailing_store_in_bb (basic_block bb, tree vdef)
3340 if (SSA_NAME_IS_DEFAULT_DEF (vdef))
3341 return NULL;
3342 gimple *store = SSA_NAME_DEF_STMT (vdef);
3343 if (gimple_bb (store) != bb
3344 || gimple_code (store) == GIMPLE_PHI)
3345 return NULL;
3347 /* Verify there is no other store in this BB. */
3348 if (!SSA_NAME_IS_DEFAULT_DEF (gimple_vuse (store))
3349 && gimple_bb (SSA_NAME_DEF_STMT (gimple_vuse (store))) == bb
3350 && gimple_code (SSA_NAME_DEF_STMT (gimple_vuse (store))) != GIMPLE_PHI)
3351 return NULL;
3353 /* Verify there is no load or store after the store. */
3354 use_operand_p use_p;
3355 imm_use_iterator imm_iter;
3356 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_vdef (store))
3357 if (USE_STMT (use_p) != store
3358 && gimple_bb (USE_STMT (use_p)) == bb)
3359 return NULL;
3361 return store;
3364 /* Conditional store replacement. We already know
3365 that the recognized pattern looks like so:
3367 split:
3368 if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
3369 THEN_BB:
3371 X = Y;
3373 goto JOIN_BB;
3374 ELSE_BB:
3376 X = Z;
3378 fallthrough (edge E0)
3379 JOIN_BB:
3380 some more
3382 We check that it is safe to sink the store to JOIN_BB by verifying that
3383 there are no read-after-write or write-after-write dependencies in
3384 THEN_BB and ELSE_BB. */
3386 static bool
3387 cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb,
3388 basic_block join_bb)
3390 vec<data_reference_p> then_datarefs, else_datarefs;
3391 vec<ddr_p> then_ddrs, else_ddrs;
3392 gimple *then_store, *else_store;
3393 bool found, ok = false, res;
3394 struct data_dependence_relation *ddr;
3395 data_reference_p then_dr, else_dr;
3396 int i, j;
3397 tree then_lhs, else_lhs;
3398 basic_block blocks[3];
3400 /* Handle the case with single store in THEN_BB and ELSE_BB. That is
3401 cheap enough to always handle as it allows us to elide dependence
3402 checking. */
3403 gphi *vphi = NULL;
3404 for (gphi_iterator si = gsi_start_phis (join_bb); !gsi_end_p (si);
3405 gsi_next (&si))
3406 if (virtual_operand_p (gimple_phi_result (si.phi ())))
3408 vphi = si.phi ();
3409 break;
3411 if (!vphi)
3412 return false;
3413 tree then_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (then_bb));
3414 tree else_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (else_bb));
3415 gimple *then_assign = single_trailing_store_in_bb (then_bb, then_vdef);
3416 if (then_assign)
3418 gimple *else_assign = single_trailing_store_in_bb (else_bb, else_vdef);
3419 if (else_assign)
3420 return cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
3421 then_assign, else_assign);
3424 /* If either vectorization or if-conversion is disabled then do
3425 not sink any stores. */
3426 if (param_max_stores_to_sink == 0
3427 || (!flag_tree_loop_vectorize && !flag_tree_slp_vectorize)
3428 || !flag_tree_loop_if_convert)
3429 return false;
3431 /* Find data references. */
3432 then_datarefs.create (1);
3433 else_datarefs.create (1);
3434 if ((find_data_references_in_bb (NULL, then_bb, &then_datarefs)
3435 == chrec_dont_know)
3436 || !then_datarefs.length ()
3437 || (find_data_references_in_bb (NULL, else_bb, &else_datarefs)
3438 == chrec_dont_know)
3439 || !else_datarefs.length ())
3441 free_data_refs (then_datarefs);
3442 free_data_refs (else_datarefs);
3443 return false;
3446 /* Find pairs of stores with equal LHS. */
3447 auto_vec<gimple *, 1> then_stores, else_stores;
3448 FOR_EACH_VEC_ELT (then_datarefs, i, then_dr)
3450 if (DR_IS_READ (then_dr))
3451 continue;
3453 then_store = DR_STMT (then_dr);
3454 then_lhs = gimple_get_lhs (then_store);
3455 if (then_lhs == NULL_TREE)
3456 continue;
3457 found = false;
3459 FOR_EACH_VEC_ELT (else_datarefs, j, else_dr)
3461 if (DR_IS_READ (else_dr))
3462 continue;
3464 else_store = DR_STMT (else_dr);
3465 else_lhs = gimple_get_lhs (else_store);
3466 if (else_lhs == NULL_TREE)
3467 continue;
3469 if (operand_equal_p (then_lhs, else_lhs, 0))
3471 found = true;
3472 break;
3476 if (!found)
3477 continue;
3479 then_stores.safe_push (then_store);
3480 else_stores.safe_push (else_store);
3483 /* No pairs of stores found. */
3484 if (!then_stores.length ()
3485 || then_stores.length () > (unsigned) param_max_stores_to_sink)
3487 free_data_refs (then_datarefs);
3488 free_data_refs (else_datarefs);
3489 return false;
3492 /* Compute and check data dependencies in both basic blocks. */
3493 then_ddrs.create (1);
3494 else_ddrs.create (1);
3495 if (!compute_all_dependences (then_datarefs, &then_ddrs,
3496 vNULL, false)
3497 || !compute_all_dependences (else_datarefs, &else_ddrs,
3498 vNULL, false))
3500 free_dependence_relations (then_ddrs);
3501 free_dependence_relations (else_ddrs);
3502 free_data_refs (then_datarefs);
3503 free_data_refs (else_datarefs);
3504 return false;
3506 blocks[0] = then_bb;
3507 blocks[1] = else_bb;
3508 blocks[2] = join_bb;
3509 renumber_gimple_stmt_uids_in_blocks (blocks, 3);
3511 /* Check that there are no read-after-write or write-after-write dependencies
3512 in THEN_BB. */
3513 FOR_EACH_VEC_ELT (then_ddrs, i, ddr)
3515 struct data_reference *dra = DDR_A (ddr);
3516 struct data_reference *drb = DDR_B (ddr);
3518 if (DDR_ARE_DEPENDENT (ddr) != chrec_known
3519 && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
3520 && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
3521 || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
3522 && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
3523 || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
3525 free_dependence_relations (then_ddrs);
3526 free_dependence_relations (else_ddrs);
3527 free_data_refs (then_datarefs);
3528 free_data_refs (else_datarefs);
3529 return false;
3533 /* Check that there are no read-after-write or write-after-write dependencies
3534 in ELSE_BB. */
3535 FOR_EACH_VEC_ELT (else_ddrs, i, ddr)
3537 struct data_reference *dra = DDR_A (ddr);
3538 struct data_reference *drb = DDR_B (ddr);
3540 if (DDR_ARE_DEPENDENT (ddr) != chrec_known
3541 && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
3542 && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
3543 || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
3544 && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
3545 || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
3547 free_dependence_relations (then_ddrs);
3548 free_dependence_relations (else_ddrs);
3549 free_data_refs (then_datarefs);
3550 free_data_refs (else_datarefs);
3551 return false;
3555 /* Sink stores with same LHS. */
3556 FOR_EACH_VEC_ELT (then_stores, i, then_store)
3558 else_store = else_stores[i];
3559 res = cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
3560 then_store, else_store);
3561 ok = ok || res;
3564 free_dependence_relations (then_ddrs);
3565 free_dependence_relations (else_ddrs);
3566 free_data_refs (then_datarefs);
3567 free_data_refs (else_datarefs);
3569 return ok;
3572 /* Return TRUE if STMT has a VUSE whose corresponding VDEF is in BB. */
3574 static bool
3575 local_mem_dependence (gimple *stmt, basic_block bb)
3577 tree vuse = gimple_vuse (stmt);
3578 gimple *def;
3580 if (!vuse)
3581 return false;
3583 def = SSA_NAME_DEF_STMT (vuse);
3584 return (def && gimple_bb (def) == bb);
3587 /* Given a "diamond" control-flow pattern where BB0 tests a condition,
3588 BB1 and BB2 are "then" and "else" blocks dependent on this test,
3589 and BB3 rejoins control flow following BB1 and BB2, look for
3590 opportunities to hoist loads as follows. If BB3 contains a PHI of
3591 two loads, one each occurring in BB1 and BB2, and the loads are
3592 provably of adjacent fields in the same structure, then move both
3593 loads into BB0. Of course this can only be done if there are no
3594 dependencies preventing such motion.
3596 One of the hoisted loads will always be speculative, so the
3597 transformation is currently conservative:
3599 - The fields must be strictly adjacent.
3600 - The two fields must occupy a single memory block that is
3601 guaranteed to not cross a page boundary.
3603 The last is difficult to prove, as such memory blocks should be
3604 aligned on the minimum of the stack alignment boundary and the
3605 alignment guaranteed by heap allocation interfaces. Thus we rely
3606 on a parameter for the alignment value.
3608 Provided a good value is used for the last case, the first
3609 restriction could possibly be relaxed. */
3611 static void
3612 hoist_adjacent_loads (basic_block bb0, basic_block bb1,
3613 basic_block bb2, basic_block bb3)
3615 int param_align = param_l1_cache_line_size;
3616 unsigned param_align_bits = (unsigned) (param_align * BITS_PER_UNIT);
3617 gphi_iterator gsi;
3619 /* Walk the phis in bb3 looking for an opportunity. We are looking
3620 for phis of two SSA names, one each of which is defined in bb1 and
3621 bb2. */
3622 for (gsi = gsi_start_phis (bb3); !gsi_end_p (gsi); gsi_next (&gsi))
3624 gphi *phi_stmt = gsi.phi ();
3625 gimple *def1, *def2;
3626 tree arg1, arg2, ref1, ref2, field1, field2;
3627 tree tree_offset1, tree_offset2, tree_size2, next;
3628 int offset1, offset2, size2;
3629 unsigned align1;
3630 gimple_stmt_iterator gsi2;
3631 basic_block bb_for_def1, bb_for_def2;
3633 if (gimple_phi_num_args (phi_stmt) != 2
3634 || virtual_operand_p (gimple_phi_result (phi_stmt)))
3635 continue;
3637 arg1 = gimple_phi_arg_def (phi_stmt, 0);
3638 arg2 = gimple_phi_arg_def (phi_stmt, 1);
3640 if (TREE_CODE (arg1) != SSA_NAME
3641 || TREE_CODE (arg2) != SSA_NAME
3642 || SSA_NAME_IS_DEFAULT_DEF (arg1)
3643 || SSA_NAME_IS_DEFAULT_DEF (arg2))
3644 continue;
3646 def1 = SSA_NAME_DEF_STMT (arg1);
3647 def2 = SSA_NAME_DEF_STMT (arg2);
3649 if ((gimple_bb (def1) != bb1 || gimple_bb (def2) != bb2)
3650 && (gimple_bb (def2) != bb1 || gimple_bb (def1) != bb2))
3651 continue;
3653 /* Check the mode of the arguments to be sure a conditional move
3654 can be generated for it. */
3655 if (optab_handler (movcc_optab, TYPE_MODE (TREE_TYPE (arg1)))
3656 == CODE_FOR_nothing)
3657 continue;
3659 /* Both statements must be assignments whose RHS is a COMPONENT_REF. */
3660 if (!gimple_assign_single_p (def1)
3661 || !gimple_assign_single_p (def2)
3662 || gimple_has_volatile_ops (def1)
3663 || gimple_has_volatile_ops (def2))
3664 continue;
3666 ref1 = gimple_assign_rhs1 (def1);
3667 ref2 = gimple_assign_rhs1 (def2);
3669 if (TREE_CODE (ref1) != COMPONENT_REF
3670 || TREE_CODE (ref2) != COMPONENT_REF)
3671 continue;
3673 /* The zeroth operand of the two component references must be
3674 identical. It is not sufficient to compare get_base_address of
3675 the two references, because this could allow for different
3676 elements of the same array in the two trees. It is not safe to
3677 assume that the existence of one array element implies the
3678 existence of a different one. */
3679 if (!operand_equal_p (TREE_OPERAND (ref1, 0), TREE_OPERAND (ref2, 0), 0))
3680 continue;
3682 field1 = TREE_OPERAND (ref1, 1);
3683 field2 = TREE_OPERAND (ref2, 1);
3685 /* Check for field adjacency, and ensure field1 comes first. */
3686 for (next = DECL_CHAIN (field1);
3687 next && TREE_CODE (next) != FIELD_DECL;
3688 next = DECL_CHAIN (next))
3691 if (next != field2)
3693 for (next = DECL_CHAIN (field2);
3694 next && TREE_CODE (next) != FIELD_DECL;
3695 next = DECL_CHAIN (next))
3698 if (next != field1)
3699 continue;
3701 std::swap (field1, field2);
3702 std::swap (def1, def2);
3705 bb_for_def1 = gimple_bb (def1);
3706 bb_for_def2 = gimple_bb (def2);
3708 /* Check for proper alignment of the first field. */
3709 tree_offset1 = bit_position (field1);
3710 tree_offset2 = bit_position (field2);
3711 tree_size2 = DECL_SIZE (field2);
3713 if (!tree_fits_uhwi_p (tree_offset1)
3714 || !tree_fits_uhwi_p (tree_offset2)
3715 || !tree_fits_uhwi_p (tree_size2))
3716 continue;
3718 offset1 = tree_to_uhwi (tree_offset1);
3719 offset2 = tree_to_uhwi (tree_offset2);
3720 size2 = tree_to_uhwi (tree_size2);
3721 align1 = DECL_ALIGN (field1) % param_align_bits;
3723 if (offset1 % BITS_PER_UNIT != 0)
3724 continue;
3726 /* For profitability, the two field references should fit within
3727 a single cache line. */
3728 if (align1 + offset2 - offset1 + size2 > param_align_bits)
3729 continue;
3731 /* The two expressions cannot be dependent upon vdefs defined
3732 in bb1/bb2. */
3733 if (local_mem_dependence (def1, bb_for_def1)
3734 || local_mem_dependence (def2, bb_for_def2))
3735 continue;
3737 /* The conditions are satisfied; hoist the loads from bb1 and bb2 into
3738 bb0. We hoist the first one first so that a cache miss is handled
3739 efficiently regardless of hardware cache-fill policy. */
3740 gsi2 = gsi_for_stmt (def1);
3741 gsi_move_to_bb_end (&gsi2, bb0);
3742 gsi2 = gsi_for_stmt (def2);
3743 gsi_move_to_bb_end (&gsi2, bb0);
3744 statistics_counter_event (cfun, "hoisted loads", 1);
3746 if (dump_file && (dump_flags & TDF_DETAILS))
3748 fprintf (dump_file,
3749 "\nHoisting adjacent loads from %d and %d into %d: \n",
3750 bb_for_def1->index, bb_for_def2->index, bb0->index);
3751 print_gimple_stmt (dump_file, def1, 0, TDF_VOPS|TDF_MEMSYMS);
3752 print_gimple_stmt (dump_file, def2, 0, TDF_VOPS|TDF_MEMSYMS);
3757 /* Determine whether we should attempt to hoist adjacent loads out of
3758 diamond patterns in pass_phiopt. Always hoist loads if
3759 -fhoist-adjacent-loads is specified and the target machine has
3760 both a conditional move instruction and a defined cache line size. */
3762 static bool
3763 gate_hoist_loads (void)
3765 return (flag_hoist_adjacent_loads == 1
3766 && param_l1_cache_line_size
3767 && HAVE_conditional_move);
3770 /* This pass tries to replaces an if-then-else block with an
3771 assignment. We have four kinds of transformations. Some of these
3772 transformations are also performed by the ifcvt RTL optimizer.
3774 Conditional Replacement
3775 -----------------------
3777 This transformation, implemented in match_simplify_replacement,
3778 replaces
3780 bb0:
3781 if (cond) goto bb2; else goto bb1;
3782 bb1:
3783 bb2:
3784 x = PHI <0 (bb1), 1 (bb0), ...>;
3786 with
3788 bb0:
3789 x' = cond;
3790 goto bb2;
3791 bb2:
3792 x = PHI <x' (bb0), ...>;
3794 We remove bb1 as it becomes unreachable. This occurs often due to
3795 gimplification of conditionals.
3797 Value Replacement
3798 -----------------
3800 This transformation, implemented in value_replacement, replaces
3802 bb0:
3803 if (a != b) goto bb2; else goto bb1;
3804 bb1:
3805 bb2:
3806 x = PHI <a (bb1), b (bb0), ...>;
3808 with
3810 bb0:
3811 bb2:
3812 x = PHI <b (bb0), ...>;
3814 This opportunity can sometimes occur as a result of other
3815 optimizations.
3818 Another case caught by value replacement looks like this:
3820 bb0:
3821 t1 = a == CONST;
3822 t2 = b > c;
3823 t3 = t1 & t2;
3824 if (t3 != 0) goto bb1; else goto bb2;
3825 bb1:
3826 bb2:
3827 x = PHI (CONST, a)
3829 Gets replaced with:
3830 bb0:
3831 bb2:
3832 t1 = a == CONST;
3833 t2 = b > c;
3834 t3 = t1 & t2;
3835 x = a;
3837 ABS Replacement
3838 ---------------
3840 This transformation, implemented in match_simplify_replacement, replaces
3842 bb0:
3843 if (a >= 0) goto bb2; else goto bb1;
3844 bb1:
3845 x = -a;
3846 bb2:
3847 x = PHI <x (bb1), a (bb0), ...>;
3849 with
3851 bb0:
3852 x' = ABS_EXPR< a >;
3853 bb2:
3854 x = PHI <x' (bb0), ...>;
3856 MIN/MAX Replacement
3857 -------------------
3859 This transformation, minmax_replacement replaces
3861 bb0:
3862 if (a <= b) goto bb2; else goto bb1;
3863 bb1:
3864 bb2:
3865 x = PHI <b (bb1), a (bb0), ...>;
3867 with
3869 bb0:
3870 x' = MIN_EXPR (a, b)
3871 bb2:
3872 x = PHI <x' (bb0), ...>;
3874 A similar transformation is done for MAX_EXPR.
3877 This pass also performs a fifth transformation of a slightly different
3878 flavor.
3880 Factor conversion in COND_EXPR
3881 ------------------------------
3883 This transformation factors the conversion out of COND_EXPR with
3884 factor_out_conditional_conversion.
3886 For example:
3887 if (a <= CST) goto <bb 3>; else goto <bb 4>;
3888 <bb 3>:
3889 tmp = (int) a;
3890 <bb 4>:
3891 tmp = PHI <tmp, CST>
3893 Into:
3894 if (a <= CST) goto <bb 3>; else goto <bb 4>;
3895 <bb 3>:
3896 <bb 4>:
3897 a = PHI <a, CST>
3898 tmp = (int) a;
3900 Adjacent Load Hoisting
3901 ----------------------
3903 This transformation replaces
3905 bb0:
3906 if (...) goto bb2; else goto bb1;
3907 bb1:
3908 x1 = (<expr>).field1;
3909 goto bb3;
3910 bb2:
3911 x2 = (<expr>).field2;
3912 bb3:
3913 # x = PHI <x1, x2>;
3915 with
3917 bb0:
3918 x1 = (<expr>).field1;
3919 x2 = (<expr>).field2;
3920 if (...) goto bb2; else goto bb1;
3921 bb1:
3922 goto bb3;
3923 bb2:
3924 bb3:
3925 # x = PHI <x1, x2>;
3927 The purpose of this transformation is to enable generation of conditional
3928 move instructions such as Intel CMOVE or PowerPC ISEL. Because one of
3929 the loads is speculative, the transformation is restricted to very
3930 specific cases to avoid introducing a page fault. We are looking for
3931 the common idiom:
3933 if (...)
3934 x = y->left;
3935 else
3936 x = y->right;
3938 where left and right are typically adjacent pointers in a tree structure. */
3940 namespace {
3942 const pass_data pass_data_phiopt =
3944 GIMPLE_PASS, /* type */
3945 "phiopt", /* name */
3946 OPTGROUP_NONE, /* optinfo_flags */
3947 TV_TREE_PHIOPT, /* tv_id */
3948 ( PROP_cfg | PROP_ssa ), /* properties_required */
3949 0, /* properties_provided */
3950 0, /* properties_destroyed */
3951 0, /* todo_flags_start */
3952 0, /* todo_flags_finish */
3955 class pass_phiopt : public gimple_opt_pass
3957 public:
3958 pass_phiopt (gcc::context *ctxt)
3959 : gimple_opt_pass (pass_data_phiopt, ctxt), early_p (false)
3962 /* opt_pass methods: */
3963 opt_pass * clone () { return new pass_phiopt (m_ctxt); }
3964 void set_pass_param (unsigned n, bool param)
3966 gcc_assert (n == 0);
3967 early_p = param;
3969 virtual bool gate (function *) { return flag_ssa_phiopt; }
3970 virtual unsigned int execute (function *)
3972 return tree_ssa_phiopt_worker (false,
3973 !early_p ? gate_hoist_loads () : false,
3974 early_p);
3977 private:
3978 bool early_p;
3979 }; // class pass_phiopt
3981 } // anon namespace
3983 gimple_opt_pass *
3984 make_pass_phiopt (gcc::context *ctxt)
3986 return new pass_phiopt (ctxt);
3989 namespace {
3991 const pass_data pass_data_cselim =
3993 GIMPLE_PASS, /* type */
3994 "cselim", /* name */
3995 OPTGROUP_NONE, /* optinfo_flags */
3996 TV_TREE_PHIOPT, /* tv_id */
3997 ( PROP_cfg | PROP_ssa ), /* properties_required */
3998 0, /* properties_provided */
3999 0, /* properties_destroyed */
4000 0, /* todo_flags_start */
4001 0, /* todo_flags_finish */
4004 class pass_cselim : public gimple_opt_pass
4006 public:
4007 pass_cselim (gcc::context *ctxt)
4008 : gimple_opt_pass (pass_data_cselim, ctxt)
4011 /* opt_pass methods: */
4012 virtual bool gate (function *) { return flag_tree_cselim; }
4013 virtual unsigned int execute (function *) { return tree_ssa_cs_elim (); }
4015 }; // class pass_cselim
4017 } // anon namespace
4019 gimple_opt_pass *
4020 make_pass_cselim (gcc::context *ctxt)
4022 return new pass_cselim (ctxt);