* c-cppbuiltin.c (c_cpp_builtins): Use ggc_strdup for the fp_suffix
[official-gcc.git] / gcc / tree-ssa-phiopt.c
blobe740cf5993079d7b1d88803810ebfcbba1218646
1 /* Optimization of PHI nodes by converting them into straightline code.
2 Copyright (C) 2004-2018 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 "optabs-tree.h"
32 #include "insn-config.h"
33 #include "gimple-pretty-print.h"
34 #include "fold-const.h"
35 #include "stor-layout.h"
36 #include "cfganal.h"
37 #include "gimplify.h"
38 #include "gimple-iterator.h"
39 #include "gimplify-me.h"
40 #include "tree-cfg.h"
41 #include "tree-dfa.h"
42 #include "domwalk.h"
43 #include "cfgloop.h"
44 #include "tree-data-ref.h"
45 #include "tree-scalar-evolution.h"
46 #include "tree-inline.h"
47 #include "params.h"
49 static unsigned int tree_ssa_phiopt_worker (bool, bool);
50 static bool conditional_replacement (basic_block, basic_block,
51 edge, edge, gphi *, tree, tree);
52 static gphi *factor_out_conditional_conversion (edge, edge, gphi *, tree, tree,
53 gimple *);
54 static int value_replacement (basic_block, basic_block,
55 edge, edge, gimple *, tree, tree);
56 static bool minmax_replacement (basic_block, basic_block,
57 edge, edge, gimple *, tree, tree);
58 static bool abs_replacement (basic_block, basic_block,
59 edge, edge, gimple *, tree, tree);
60 static bool cond_store_replacement (basic_block, basic_block, edge, edge,
61 hash_set<tree> *);
62 static bool cond_if_else_store_replacement (basic_block, basic_block, basic_block);
63 static hash_set<tree> * get_non_trapping ();
64 static void replace_phi_edge_with_variable (basic_block, edge, gimple *, tree);
65 static void hoist_adjacent_loads (basic_block, basic_block,
66 basic_block, basic_block);
67 static bool gate_hoist_loads (void);
69 /* This pass tries to transform conditional stores into unconditional
70 ones, enabling further simplifications with the simpler then and else
71 blocks. In particular it replaces this:
73 bb0:
74 if (cond) goto bb2; else goto bb1;
75 bb1:
76 *p = RHS;
77 bb2:
79 with
81 bb0:
82 if (cond) goto bb1; else goto bb2;
83 bb1:
84 condtmp' = *p;
85 bb2:
86 condtmp = PHI <RHS, condtmp'>
87 *p = condtmp;
89 This transformation can only be done under several constraints,
90 documented below. It also replaces:
92 bb0:
93 if (cond) goto bb2; else goto bb1;
94 bb1:
95 *p = RHS1;
96 goto bb3;
97 bb2:
98 *p = RHS2;
99 bb3:
101 with
103 bb0:
104 if (cond) goto bb3; else goto bb1;
105 bb1:
106 bb3:
107 condtmp = PHI <RHS1, RHS2>
108 *p = condtmp; */
110 static unsigned int
111 tree_ssa_cs_elim (void)
113 unsigned todo;
114 /* ??? We are not interested in loop related info, but the following
115 will create it, ICEing as we didn't init loops with pre-headers.
116 An interfacing issue of find_data_references_in_bb. */
117 loop_optimizer_init (LOOPS_NORMAL);
118 scev_initialize ();
119 todo = tree_ssa_phiopt_worker (true, false);
120 scev_finalize ();
121 loop_optimizer_finalize ();
122 return todo;
125 /* Return the singleton PHI in the SEQ of PHIs for edges E0 and E1. */
127 static gphi *
128 single_non_singleton_phi_for_edges (gimple_seq seq, edge e0, edge e1)
130 gimple_stmt_iterator i;
131 gphi *phi = NULL;
132 if (gimple_seq_singleton_p (seq))
133 return as_a <gphi *> (gsi_stmt (gsi_start (seq)));
134 for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
136 gphi *p = as_a <gphi *> (gsi_stmt (i));
137 /* If the PHI arguments are equal then we can skip this PHI. */
138 if (operand_equal_for_phi_arg_p (gimple_phi_arg_def (p, e0->dest_idx),
139 gimple_phi_arg_def (p, e1->dest_idx)))
140 continue;
142 /* If we already have a PHI that has the two edge arguments are
143 different, then return it is not a singleton for these PHIs. */
144 if (phi)
145 return NULL;
147 phi = p;
149 return phi;
152 /* The core routine of conditional store replacement and normal
153 phi optimizations. Both share much of the infrastructure in how
154 to match applicable basic block patterns. DO_STORE_ELIM is true
155 when we want to do conditional store replacement, false otherwise.
156 DO_HOIST_LOADS is true when we want to hoist adjacent loads out
157 of diamond control flow patterns, false otherwise. */
158 static unsigned int
159 tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads)
161 basic_block bb;
162 basic_block *bb_order;
163 unsigned n, i;
164 bool cfgchanged = false;
165 hash_set<tree> *nontrap = 0;
167 if (do_store_elim)
168 /* Calculate the set of non-trapping memory accesses. */
169 nontrap = get_non_trapping ();
171 /* Search every basic block for COND_EXPR we may be able to optimize.
173 We walk the blocks in order that guarantees that a block with
174 a single predecessor is processed before the predecessor.
175 This ensures that we collapse inner ifs before visiting the
176 outer ones, and also that we do not try to visit a removed
177 block. */
178 bb_order = single_pred_before_succ_order ();
179 n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
181 for (i = 0; i < n; i++)
183 gimple *cond_stmt;
184 gphi *phi;
185 basic_block bb1, bb2;
186 edge e1, e2;
187 tree arg0, arg1;
189 bb = bb_order[i];
191 cond_stmt = last_stmt (bb);
192 /* Check to see if the last statement is a GIMPLE_COND. */
193 if (!cond_stmt
194 || gimple_code (cond_stmt) != GIMPLE_COND)
195 continue;
197 e1 = EDGE_SUCC (bb, 0);
198 bb1 = e1->dest;
199 e2 = EDGE_SUCC (bb, 1);
200 bb2 = e2->dest;
202 /* We cannot do the optimization on abnormal edges. */
203 if ((e1->flags & EDGE_ABNORMAL) != 0
204 || (e2->flags & EDGE_ABNORMAL) != 0)
205 continue;
207 /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
208 if (EDGE_COUNT (bb1->succs) == 0
209 || bb2 == NULL
210 || EDGE_COUNT (bb2->succs) == 0)
211 continue;
213 /* Find the bb which is the fall through to the other. */
214 if (EDGE_SUCC (bb1, 0)->dest == bb2)
216 else if (EDGE_SUCC (bb2, 0)->dest == bb1)
218 std::swap (bb1, bb2);
219 std::swap (e1, e2);
221 else if (do_store_elim
222 && EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest)
224 basic_block bb3 = EDGE_SUCC (bb1, 0)->dest;
226 if (!single_succ_p (bb1)
227 || (EDGE_SUCC (bb1, 0)->flags & EDGE_FALLTHRU) == 0
228 || !single_succ_p (bb2)
229 || (EDGE_SUCC (bb2, 0)->flags & EDGE_FALLTHRU) == 0
230 || EDGE_COUNT (bb3->preds) != 2)
231 continue;
232 if (cond_if_else_store_replacement (bb1, bb2, bb3))
233 cfgchanged = true;
234 continue;
236 else if (do_hoist_loads
237 && EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest)
239 basic_block bb3 = EDGE_SUCC (bb1, 0)->dest;
241 if (!FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt)))
242 && single_succ_p (bb1)
243 && single_succ_p (bb2)
244 && single_pred_p (bb1)
245 && single_pred_p (bb2)
246 && EDGE_COUNT (bb->succs) == 2
247 && EDGE_COUNT (bb3->preds) == 2
248 /* If one edge or the other is dominant, a conditional move
249 is likely to perform worse than the well-predicted branch. */
250 && !predictable_edge_p (EDGE_SUCC (bb, 0))
251 && !predictable_edge_p (EDGE_SUCC (bb, 1)))
252 hoist_adjacent_loads (bb, bb1, bb2, bb3);
253 continue;
255 else
256 continue;
258 e1 = EDGE_SUCC (bb1, 0);
260 /* Make sure that bb1 is just a fall through. */
261 if (!single_succ_p (bb1)
262 || (e1->flags & EDGE_FALLTHRU) == 0)
263 continue;
265 /* Also make sure that bb1 only have one predecessor and that it
266 is bb. */
267 if (!single_pred_p (bb1)
268 || single_pred (bb1) != bb)
269 continue;
271 if (do_store_elim)
273 /* bb1 is the middle block, bb2 the join block, bb the split block,
274 e1 the fallthrough edge from bb1 to bb2. We can't do the
275 optimization if the join block has more than two predecessors. */
276 if (EDGE_COUNT (bb2->preds) > 2)
277 continue;
278 if (cond_store_replacement (bb1, bb2, e1, e2, nontrap))
279 cfgchanged = true;
281 else
283 gimple_seq phis = phi_nodes (bb2);
284 gimple_stmt_iterator gsi;
285 bool candorest = true;
287 /* Value replacement can work with more than one PHI
288 so try that first. */
289 for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
291 phi = as_a <gphi *> (gsi_stmt (gsi));
292 arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
293 arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
294 if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1) == 2)
296 candorest = false;
297 cfgchanged = true;
298 break;
302 if (!candorest)
303 continue;
305 phi = single_non_singleton_phi_for_edges (phis, e1, e2);
306 if (!phi)
307 continue;
309 arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
310 arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
312 /* Something is wrong if we cannot find the arguments in the PHI
313 node. */
314 gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
316 gphi *newphi = factor_out_conditional_conversion (e1, e2, phi,
317 arg0, arg1,
318 cond_stmt);
319 if (newphi != NULL)
321 phi = newphi;
322 /* factor_out_conditional_conversion may create a new PHI in
323 BB2 and eliminate an existing PHI in BB2. Recompute values
324 that may be affected by that change. */
325 arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
326 arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
327 gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
330 /* Do the replacement of conditional if it can be done. */
331 if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
332 cfgchanged = true;
333 else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
334 cfgchanged = true;
335 else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
336 cfgchanged = true;
340 free (bb_order);
342 if (do_store_elim)
343 delete nontrap;
344 /* If the CFG has changed, we should cleanup the CFG. */
345 if (cfgchanged && do_store_elim)
347 /* In cond-store replacement we have added some loads on edges
348 and new VOPS (as we moved the store, and created a load). */
349 gsi_commit_edge_inserts ();
350 return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
352 else if (cfgchanged)
353 return TODO_cleanup_cfg;
354 return 0;
357 /* Replace PHI node element whose edge is E in block BB with variable NEW.
358 Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
359 is known to have two edges, one of which must reach BB). */
361 static void
362 replace_phi_edge_with_variable (basic_block cond_block,
363 edge e, gimple *phi, tree new_tree)
365 basic_block bb = gimple_bb (phi);
366 basic_block block_to_remove;
367 gimple_stmt_iterator gsi;
369 /* Change the PHI argument to new. */
370 SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);
372 /* Remove the empty basic block. */
373 if (EDGE_SUCC (cond_block, 0)->dest == bb)
375 EDGE_SUCC (cond_block, 0)->flags |= EDGE_FALLTHRU;
376 EDGE_SUCC (cond_block, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
377 EDGE_SUCC (cond_block, 0)->probability = profile_probability::always ();
379 block_to_remove = EDGE_SUCC (cond_block, 1)->dest;
381 else
383 EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU;
384 EDGE_SUCC (cond_block, 1)->flags
385 &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
386 EDGE_SUCC (cond_block, 1)->probability = profile_probability::always ();
388 block_to_remove = EDGE_SUCC (cond_block, 0)->dest;
390 delete_basic_block (block_to_remove);
392 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
393 gsi = gsi_last_bb (cond_block);
394 gsi_remove (&gsi, true);
396 if (dump_file && (dump_flags & TDF_DETAILS))
397 fprintf (dump_file,
398 "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
399 cond_block->index,
400 bb->index);
403 /* PR66726: Factor conversion out of COND_EXPR. If the arguments of the PHI
404 stmt are CONVERT_STMT, factor out the conversion and perform the conversion
405 to the result of PHI stmt. COND_STMT is the controlling predicate.
406 Return the newly-created PHI, if any. */
408 static gphi *
409 factor_out_conditional_conversion (edge e0, edge e1, gphi *phi,
410 tree arg0, tree arg1, gimple *cond_stmt)
412 gimple *arg0_def_stmt = NULL, *arg1_def_stmt = NULL, *new_stmt;
413 tree new_arg0 = NULL_TREE, new_arg1 = NULL_TREE;
414 tree temp, result;
415 gphi *newphi;
416 gimple_stmt_iterator gsi, gsi_for_def;
417 source_location locus = gimple_location (phi);
418 enum tree_code convert_code;
420 /* Handle only PHI statements with two arguments. TODO: If all
421 other arguments to PHI are INTEGER_CST or if their defining
422 statement have the same unary operation, we can handle more
423 than two arguments too. */
424 if (gimple_phi_num_args (phi) != 2)
425 return NULL;
427 /* First canonicalize to simplify tests. */
428 if (TREE_CODE (arg0) != SSA_NAME)
430 std::swap (arg0, arg1);
431 std::swap (e0, e1);
434 if (TREE_CODE (arg0) != SSA_NAME
435 || (TREE_CODE (arg1) != SSA_NAME
436 && TREE_CODE (arg1) != INTEGER_CST))
437 return NULL;
439 /* Check if arg0 is an SSA_NAME and the stmt which defines arg0 is
440 a conversion. */
441 arg0_def_stmt = SSA_NAME_DEF_STMT (arg0);
442 if (!gimple_assign_cast_p (arg0_def_stmt))
443 return NULL;
445 /* Use the RHS as new_arg0. */
446 convert_code = gimple_assign_rhs_code (arg0_def_stmt);
447 new_arg0 = gimple_assign_rhs1 (arg0_def_stmt);
448 if (convert_code == VIEW_CONVERT_EXPR)
450 new_arg0 = TREE_OPERAND (new_arg0, 0);
451 if (!is_gimple_reg_type (TREE_TYPE (new_arg0)))
452 return NULL;
455 if (TREE_CODE (arg1) == SSA_NAME)
457 /* Check if arg1 is an SSA_NAME and the stmt which defines arg1
458 is a conversion. */
459 arg1_def_stmt = SSA_NAME_DEF_STMT (arg1);
460 if (!is_gimple_assign (arg1_def_stmt)
461 || gimple_assign_rhs_code (arg1_def_stmt) != convert_code)
462 return NULL;
464 /* Use the RHS as new_arg1. */
465 new_arg1 = gimple_assign_rhs1 (arg1_def_stmt);
466 if (convert_code == VIEW_CONVERT_EXPR)
467 new_arg1 = TREE_OPERAND (new_arg1, 0);
469 else
471 /* If arg1 is an INTEGER_CST, fold it to new type. */
472 if (INTEGRAL_TYPE_P (TREE_TYPE (new_arg0))
473 && int_fits_type_p (arg1, TREE_TYPE (new_arg0)))
475 if (gimple_assign_cast_p (arg0_def_stmt))
477 /* For the INTEGER_CST case, we are just moving the
478 conversion from one place to another, which can often
479 hurt as the conversion moves further away from the
480 statement that computes the value. So, perform this
481 only if new_arg0 is an operand of COND_STMT, or
482 if arg0_def_stmt is the only non-debug stmt in
483 its basic block, because then it is possible this
484 could enable further optimizations (minmax replacement
485 etc.). See PR71016. */
486 if (new_arg0 != gimple_cond_lhs (cond_stmt)
487 && new_arg0 != gimple_cond_rhs (cond_stmt)
488 && gimple_bb (arg0_def_stmt) == e0->src)
490 gsi = gsi_for_stmt (arg0_def_stmt);
491 gsi_prev_nondebug (&gsi);
492 if (!gsi_end_p (gsi))
493 return NULL;
494 gsi = gsi_for_stmt (arg0_def_stmt);
495 gsi_next_nondebug (&gsi);
496 if (!gsi_end_p (gsi))
497 return NULL;
499 new_arg1 = fold_convert (TREE_TYPE (new_arg0), arg1);
501 else
502 return NULL;
504 else
505 return NULL;
508 /* If arg0/arg1 have > 1 use, then this transformation actually increases
509 the number of expressions evaluated at runtime. */
510 if (!has_single_use (arg0)
511 || (arg1_def_stmt && !has_single_use (arg1)))
512 return NULL;
514 /* If types of new_arg0 and new_arg1 are different bailout. */
515 if (!types_compatible_p (TREE_TYPE (new_arg0), TREE_TYPE (new_arg1)))
516 return NULL;
518 /* Create a new PHI stmt. */
519 result = PHI_RESULT (phi);
520 temp = make_ssa_name (TREE_TYPE (new_arg0), NULL);
521 newphi = create_phi_node (temp, gimple_bb (phi));
523 if (dump_file && (dump_flags & TDF_DETAILS))
525 fprintf (dump_file, "PHI ");
526 print_generic_expr (dump_file, gimple_phi_result (phi));
527 fprintf (dump_file,
528 " changed to factor conversion out from COND_EXPR.\n");
529 fprintf (dump_file, "New stmt with CAST that defines ");
530 print_generic_expr (dump_file, result);
531 fprintf (dump_file, ".\n");
534 /* Remove the old cast(s) that has single use. */
535 gsi_for_def = gsi_for_stmt (arg0_def_stmt);
536 gsi_remove (&gsi_for_def, true);
537 release_defs (arg0_def_stmt);
539 if (arg1_def_stmt)
541 gsi_for_def = gsi_for_stmt (arg1_def_stmt);
542 gsi_remove (&gsi_for_def, true);
543 release_defs (arg1_def_stmt);
546 add_phi_arg (newphi, new_arg0, e0, locus);
547 add_phi_arg (newphi, new_arg1, e1, locus);
549 /* Create the conversion stmt and insert it. */
550 if (convert_code == VIEW_CONVERT_EXPR)
552 temp = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (result), temp);
553 new_stmt = gimple_build_assign (result, temp);
555 else
556 new_stmt = gimple_build_assign (result, convert_code, temp);
557 gsi = gsi_after_labels (gimple_bb (phi));
558 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
560 /* Remove the original PHI stmt. */
561 gsi = gsi_for_stmt (phi);
562 gsi_remove (&gsi, true);
563 return newphi;
566 /* The function conditional_replacement does the main work of doing the
567 conditional replacement. Return true if the replacement is done.
568 Otherwise return false.
569 BB is the basic block where the replacement is going to be done on. ARG0
570 is argument 0 from PHI. Likewise for ARG1. */
572 static bool
573 conditional_replacement (basic_block cond_bb, basic_block middle_bb,
574 edge e0, edge e1, gphi *phi,
575 tree arg0, tree arg1)
577 tree result;
578 gimple *stmt;
579 gassign *new_stmt;
580 tree cond;
581 gimple_stmt_iterator gsi;
582 edge true_edge, false_edge;
583 tree new_var, new_var2;
584 bool neg;
586 /* FIXME: Gimplification of complex type is too hard for now. */
587 /* We aren't prepared to handle vectors either (and it is a question
588 if it would be worthwhile anyway). */
589 if (!(INTEGRAL_TYPE_P (TREE_TYPE (arg0))
590 || POINTER_TYPE_P (TREE_TYPE (arg0)))
591 || !(INTEGRAL_TYPE_P (TREE_TYPE (arg1))
592 || POINTER_TYPE_P (TREE_TYPE (arg1))))
593 return false;
595 /* The PHI arguments have the constants 0 and 1, or 0 and -1, then
596 convert it to the conditional. */
597 if ((integer_zerop (arg0) && integer_onep (arg1))
598 || (integer_zerop (arg1) && integer_onep (arg0)))
599 neg = false;
600 else if ((integer_zerop (arg0) && integer_all_onesp (arg1))
601 || (integer_zerop (arg1) && integer_all_onesp (arg0)))
602 neg = true;
603 else
604 return false;
606 if (!empty_block_p (middle_bb))
607 return false;
609 /* At this point we know we have a GIMPLE_COND with two successors.
610 One successor is BB, the other successor is an empty block which
611 falls through into BB.
613 There is a single PHI node at the join point (BB) and its arguments
614 are constants (0, 1) or (0, -1).
616 So, given the condition COND, and the two PHI arguments, we can
617 rewrite this PHI into non-branching code:
619 dest = (COND) or dest = COND'
621 We use the condition as-is if the argument associated with the
622 true edge has the value one or the argument associated with the
623 false edge as the value zero. Note that those conditions are not
624 the same since only one of the outgoing edges from the GIMPLE_COND
625 will directly reach BB and thus be associated with an argument. */
627 stmt = last_stmt (cond_bb);
628 result = PHI_RESULT (phi);
630 /* To handle special cases like floating point comparison, it is easier and
631 less error-prone to build a tree and gimplify it on the fly though it is
632 less efficient. */
633 cond = fold_build2_loc (gimple_location (stmt),
634 gimple_cond_code (stmt), boolean_type_node,
635 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
637 /* We need to know which is the true edge and which is the false
638 edge so that we know when to invert the condition below. */
639 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
640 if ((e0 == true_edge && integer_zerop (arg0))
641 || (e0 == false_edge && !integer_zerop (arg0))
642 || (e1 == true_edge && integer_zerop (arg1))
643 || (e1 == false_edge && !integer_zerop (arg1)))
644 cond = fold_build1_loc (gimple_location (stmt),
645 TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
647 if (neg)
649 cond = fold_convert_loc (gimple_location (stmt),
650 TREE_TYPE (result), cond);
651 cond = fold_build1_loc (gimple_location (stmt),
652 NEGATE_EXPR, TREE_TYPE (cond), cond);
655 /* Insert our new statements at the end of conditional block before the
656 COND_STMT. */
657 gsi = gsi_for_stmt (stmt);
658 new_var = force_gimple_operand_gsi (&gsi, cond, true, NULL, true,
659 GSI_SAME_STMT);
661 if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (new_var)))
663 source_location locus_0, locus_1;
665 new_var2 = make_ssa_name (TREE_TYPE (result));
666 new_stmt = gimple_build_assign (new_var2, CONVERT_EXPR, new_var);
667 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
668 new_var = new_var2;
670 /* Set the locus to the first argument, unless is doesn't have one. */
671 locus_0 = gimple_phi_arg_location (phi, 0);
672 locus_1 = gimple_phi_arg_location (phi, 1);
673 if (locus_0 == UNKNOWN_LOCATION)
674 locus_0 = locus_1;
675 gimple_set_location (new_stmt, locus_0);
678 replace_phi_edge_with_variable (cond_bb, e1, phi, new_var);
680 /* Note that we optimized this PHI. */
681 return true;
684 /* Update *ARG which is defined in STMT so that it contains the
685 computed value if that seems profitable. Return true if the
686 statement is made dead by that rewriting. */
688 static bool
689 jump_function_from_stmt (tree *arg, gimple *stmt)
691 enum tree_code code = gimple_assign_rhs_code (stmt);
692 if (code == ADDR_EXPR)
694 /* For arg = &p->i transform it to p, if possible. */
695 tree rhs1 = gimple_assign_rhs1 (stmt);
696 poly_int64 offset;
697 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs1, 0),
698 &offset);
699 if (tem
700 && TREE_CODE (tem) == MEM_REF
701 && known_eq (mem_ref_offset (tem) + offset, 0))
703 *arg = TREE_OPERAND (tem, 0);
704 return true;
707 /* TODO: Much like IPA-CP jump-functions we want to handle constant
708 additions symbolically here, and we'd need to update the comparison
709 code that compares the arg + cst tuples in our caller. For now the
710 code above exactly handles the VEC_BASE pattern from vec.h. */
711 return false;
714 /* RHS is a source argument in a BIT_AND_EXPR which feeds a conditional
715 of the form SSA_NAME NE 0.
717 If RHS is fed by a simple EQ_EXPR comparison of two values, see if
718 the two input values of the EQ_EXPR match arg0 and arg1.
720 If so update *code and return TRUE. Otherwise return FALSE. */
722 static bool
723 rhs_is_fed_for_value_replacement (const_tree arg0, const_tree arg1,
724 enum tree_code *code, const_tree rhs)
726 /* Obviously if RHS is not an SSA_NAME, we can't look at the defining
727 statement. */
728 if (TREE_CODE (rhs) == SSA_NAME)
730 gimple *def1 = SSA_NAME_DEF_STMT (rhs);
732 /* Verify the defining statement has an EQ_EXPR on the RHS. */
733 if (is_gimple_assign (def1) && gimple_assign_rhs_code (def1) == EQ_EXPR)
735 /* Finally verify the source operands of the EQ_EXPR are equal
736 to arg0 and arg1. */
737 tree op0 = gimple_assign_rhs1 (def1);
738 tree op1 = gimple_assign_rhs2 (def1);
739 if ((operand_equal_for_phi_arg_p (arg0, op0)
740 && operand_equal_for_phi_arg_p (arg1, op1))
741 || (operand_equal_for_phi_arg_p (arg0, op1)
742 && operand_equal_for_phi_arg_p (arg1, op0)))
744 /* We will perform the optimization. */
745 *code = gimple_assign_rhs_code (def1);
746 return true;
750 return false;
753 /* Return TRUE if arg0/arg1 are equal to the rhs/lhs or lhs/rhs of COND.
755 Also return TRUE if arg0/arg1 are equal to the source arguments of a
756 an EQ comparison feeding a BIT_AND_EXPR which feeds COND.
758 Return FALSE otherwise. */
760 static bool
761 operand_equal_for_value_replacement (const_tree arg0, const_tree arg1,
762 enum tree_code *code, gimple *cond)
764 gimple *def;
765 tree lhs = gimple_cond_lhs (cond);
766 tree rhs = gimple_cond_rhs (cond);
768 if ((operand_equal_for_phi_arg_p (arg0, lhs)
769 && operand_equal_for_phi_arg_p (arg1, rhs))
770 || (operand_equal_for_phi_arg_p (arg1, lhs)
771 && operand_equal_for_phi_arg_p (arg0, rhs)))
772 return true;
774 /* Now handle more complex case where we have an EQ comparison
775 which feeds a BIT_AND_EXPR which feeds COND.
777 First verify that COND is of the form SSA_NAME NE 0. */
778 if (*code != NE_EXPR || !integer_zerop (rhs)
779 || TREE_CODE (lhs) != SSA_NAME)
780 return false;
782 /* Now ensure that SSA_NAME is set by a BIT_AND_EXPR. */
783 def = SSA_NAME_DEF_STMT (lhs);
784 if (!is_gimple_assign (def) || gimple_assign_rhs_code (def) != BIT_AND_EXPR)
785 return false;
787 /* Now verify arg0/arg1 correspond to the source arguments of an
788 EQ comparison feeding the BIT_AND_EXPR. */
790 tree tmp = gimple_assign_rhs1 (def);
791 if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp))
792 return true;
794 tmp = gimple_assign_rhs2 (def);
795 if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp))
796 return true;
798 return false;
801 /* Returns true if ARG is a neutral element for operation CODE
802 on the RIGHT side. */
804 static bool
805 neutral_element_p (tree_code code, tree arg, bool right)
807 switch (code)
809 case PLUS_EXPR:
810 case BIT_IOR_EXPR:
811 case BIT_XOR_EXPR:
812 return integer_zerop (arg);
814 case LROTATE_EXPR:
815 case RROTATE_EXPR:
816 case LSHIFT_EXPR:
817 case RSHIFT_EXPR:
818 case MINUS_EXPR:
819 case POINTER_PLUS_EXPR:
820 return right && integer_zerop (arg);
822 case MULT_EXPR:
823 return integer_onep (arg);
825 case TRUNC_DIV_EXPR:
826 case CEIL_DIV_EXPR:
827 case FLOOR_DIV_EXPR:
828 case ROUND_DIV_EXPR:
829 case EXACT_DIV_EXPR:
830 return right && integer_onep (arg);
832 case BIT_AND_EXPR:
833 return integer_all_onesp (arg);
835 default:
836 return false;
840 /* Returns true if ARG is an absorbing element for operation CODE. */
842 static bool
843 absorbing_element_p (tree_code code, tree arg, bool right, tree rval)
845 switch (code)
847 case BIT_IOR_EXPR:
848 return integer_all_onesp (arg);
850 case MULT_EXPR:
851 case BIT_AND_EXPR:
852 return integer_zerop (arg);
854 case LSHIFT_EXPR:
855 case RSHIFT_EXPR:
856 case LROTATE_EXPR:
857 case RROTATE_EXPR:
858 return !right && integer_zerop (arg);
860 case TRUNC_DIV_EXPR:
861 case CEIL_DIV_EXPR:
862 case FLOOR_DIV_EXPR:
863 case ROUND_DIV_EXPR:
864 case EXACT_DIV_EXPR:
865 case TRUNC_MOD_EXPR:
866 case CEIL_MOD_EXPR:
867 case FLOOR_MOD_EXPR:
868 case ROUND_MOD_EXPR:
869 return (!right
870 && integer_zerop (arg)
871 && tree_single_nonzero_warnv_p (rval, NULL));
873 default:
874 return false;
878 /* The function value_replacement does the main work of doing the value
879 replacement. Return non-zero if the replacement is done. Otherwise return
880 0. If we remove the middle basic block, return 2.
881 BB is the basic block where the replacement is going to be done on. ARG0
882 is argument 0 from the PHI. Likewise for ARG1. */
884 static int
885 value_replacement (basic_block cond_bb, basic_block middle_bb,
886 edge e0, edge e1, gimple *phi,
887 tree arg0, tree arg1)
889 gimple_stmt_iterator gsi;
890 gimple *cond;
891 edge true_edge, false_edge;
892 enum tree_code code;
893 bool emtpy_or_with_defined_p = true;
895 /* If the type says honor signed zeros we cannot do this
896 optimization. */
897 if (HONOR_SIGNED_ZEROS (arg1))
898 return 0;
900 /* If there is a statement in MIDDLE_BB that defines one of the PHI
901 arguments, then adjust arg0 or arg1. */
902 gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
903 while (!gsi_end_p (gsi))
905 gimple *stmt = gsi_stmt (gsi);
906 tree lhs;
907 gsi_next_nondebug (&gsi);
908 if (!is_gimple_assign (stmt))
910 emtpy_or_with_defined_p = false;
911 continue;
913 /* Now try to adjust arg0 or arg1 according to the computation
914 in the statement. */
915 lhs = gimple_assign_lhs (stmt);
916 if (!(lhs == arg0
917 && jump_function_from_stmt (&arg0, stmt))
918 || (lhs == arg1
919 && jump_function_from_stmt (&arg1, stmt)))
920 emtpy_or_with_defined_p = false;
923 cond = last_stmt (cond_bb);
924 code = gimple_cond_code (cond);
926 /* This transformation is only valid for equality comparisons. */
927 if (code != NE_EXPR && code != EQ_EXPR)
928 return 0;
930 /* We need to know which is the true edge and which is the false
931 edge so that we know if have abs or negative abs. */
932 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
934 /* At this point we know we have a COND_EXPR with two successors.
935 One successor is BB, the other successor is an empty block which
936 falls through into BB.
938 The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
940 There is a single PHI node at the join point (BB) with two arguments.
942 We now need to verify that the two arguments in the PHI node match
943 the two arguments to the equality comparison. */
945 if (operand_equal_for_value_replacement (arg0, arg1, &code, cond))
947 edge e;
948 tree arg;
950 /* For NE_EXPR, we want to build an assignment result = arg where
951 arg is the PHI argument associated with the true edge. For
952 EQ_EXPR we want the PHI argument associated with the false edge. */
953 e = (code == NE_EXPR ? true_edge : false_edge);
955 /* Unfortunately, E may not reach BB (it may instead have gone to
956 OTHER_BLOCK). If that is the case, then we want the single outgoing
957 edge from OTHER_BLOCK which reaches BB and represents the desired
958 path from COND_BLOCK. */
959 if (e->dest == middle_bb)
960 e = single_succ_edge (e->dest);
962 /* Now we know the incoming edge to BB that has the argument for the
963 RHS of our new assignment statement. */
964 if (e0 == e)
965 arg = arg0;
966 else
967 arg = arg1;
969 /* If the middle basic block was empty or is defining the
970 PHI arguments and this is a single phi where the args are different
971 for the edges e0 and e1 then we can remove the middle basic block. */
972 if (emtpy_or_with_defined_p
973 && single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)),
974 e0, e1) == phi)
976 replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
977 /* Note that we optimized this PHI. */
978 return 2;
980 else
982 /* Replace the PHI arguments with arg. */
983 SET_PHI_ARG_DEF (phi, e0->dest_idx, arg);
984 SET_PHI_ARG_DEF (phi, e1->dest_idx, arg);
985 if (dump_file && (dump_flags & TDF_DETAILS))
987 fprintf (dump_file, "PHI ");
988 print_generic_expr (dump_file, gimple_phi_result (phi));
989 fprintf (dump_file, " reduced for COND_EXPR in block %d to ",
990 cond_bb->index);
991 print_generic_expr (dump_file, arg);
992 fprintf (dump_file, ".\n");
994 return 1;
999 /* Now optimize (x != 0) ? x + y : y to just x + y. */
1000 gsi = gsi_last_nondebug_bb (middle_bb);
1001 if (gsi_end_p (gsi))
1002 return 0;
1004 gimple *assign = gsi_stmt (gsi);
1005 if (!is_gimple_assign (assign)
1006 || gimple_assign_rhs_class (assign) != GIMPLE_BINARY_RHS
1007 || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
1008 && !POINTER_TYPE_P (TREE_TYPE (arg0))))
1009 return 0;
1011 /* Punt if there are (degenerate) PHIs in middle_bb, there should not be. */
1012 if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
1013 return 0;
1015 /* Allow up to 2 cheap preparation statements that prepare argument
1016 for assign, e.g.:
1017 if (y_4 != 0)
1018 goto <bb 3>;
1019 else
1020 goto <bb 4>;
1021 <bb 3>:
1022 _1 = (int) y_4;
1023 iftmp.0_6 = x_5(D) r<< _1;
1024 <bb 4>:
1025 # iftmp.0_2 = PHI <iftmp.0_6(3), x_5(D)(2)>
1027 if (y_3(D) == 0)
1028 goto <bb 4>;
1029 else
1030 goto <bb 3>;
1031 <bb 3>:
1032 y_4 = y_3(D) & 31;
1033 _1 = (int) y_4;
1034 _6 = x_5(D) r<< _1;
1035 <bb 4>:
1036 # _2 = PHI <x_5(D)(2), _6(3)> */
1037 gimple *prep_stmt[2] = { NULL, NULL };
1038 int prep_cnt;
1039 for (prep_cnt = 0; ; prep_cnt++)
1041 gsi_prev_nondebug (&gsi);
1042 if (gsi_end_p (gsi))
1043 break;
1045 gimple *g = gsi_stmt (gsi);
1046 if (gimple_code (g) == GIMPLE_LABEL)
1047 break;
1049 if (prep_cnt == 2 || !is_gimple_assign (g))
1050 return 0;
1052 tree lhs = gimple_assign_lhs (g);
1053 tree rhs1 = gimple_assign_rhs1 (g);
1054 use_operand_p use_p;
1055 gimple *use_stmt;
1056 if (TREE_CODE (lhs) != SSA_NAME
1057 || TREE_CODE (rhs1) != SSA_NAME
1058 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1059 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1060 || !single_imm_use (lhs, &use_p, &use_stmt)
1061 || use_stmt != (prep_cnt ? prep_stmt[prep_cnt - 1] : assign))
1062 return 0;
1063 switch (gimple_assign_rhs_code (g))
1065 CASE_CONVERT:
1066 break;
1067 case PLUS_EXPR:
1068 case BIT_AND_EXPR:
1069 case BIT_IOR_EXPR:
1070 case BIT_XOR_EXPR:
1071 if (TREE_CODE (gimple_assign_rhs2 (g)) != INTEGER_CST)
1072 return 0;
1073 break;
1074 default:
1075 return 0;
1077 prep_stmt[prep_cnt] = g;
1080 /* Only transform if it removes the condition. */
1081 if (!single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)), e0, e1))
1082 return 0;
1084 /* Size-wise, this is always profitable. */
1085 if (optimize_bb_for_speed_p (cond_bb)
1086 /* The special case is useless if it has a low probability. */
1087 && profile_status_for_fn (cfun) != PROFILE_ABSENT
1088 && EDGE_PRED (middle_bb, 0)->probability < profile_probability::even ()
1089 /* If assign is cheap, there is no point avoiding it. */
1090 && estimate_num_insns (bb_seq (middle_bb), &eni_time_weights)
1091 >= 3 * estimate_num_insns (cond, &eni_time_weights))
1092 return 0;
1094 tree lhs = gimple_assign_lhs (assign);
1095 tree rhs1 = gimple_assign_rhs1 (assign);
1096 tree rhs2 = gimple_assign_rhs2 (assign);
1097 enum tree_code code_def = gimple_assign_rhs_code (assign);
1098 tree cond_lhs = gimple_cond_lhs (cond);
1099 tree cond_rhs = gimple_cond_rhs (cond);
1101 /* Propagate the cond_rhs constant through preparation stmts,
1102 make sure UB isn't invoked while doing that. */
1103 for (int i = prep_cnt - 1; i >= 0; --i)
1105 gimple *g = prep_stmt[i];
1106 tree grhs1 = gimple_assign_rhs1 (g);
1107 if (!operand_equal_for_phi_arg_p (cond_lhs, grhs1))
1108 return 0;
1109 cond_lhs = gimple_assign_lhs (g);
1110 cond_rhs = fold_convert (TREE_TYPE (grhs1), cond_rhs);
1111 if (TREE_CODE (cond_rhs) != INTEGER_CST
1112 || TREE_OVERFLOW (cond_rhs))
1113 return 0;
1114 if (gimple_assign_rhs_class (g) == GIMPLE_BINARY_RHS)
1116 cond_rhs = int_const_binop (gimple_assign_rhs_code (g), cond_rhs,
1117 gimple_assign_rhs2 (g));
1118 if (TREE_OVERFLOW (cond_rhs))
1119 return 0;
1121 cond_rhs = fold_convert (TREE_TYPE (cond_lhs), cond_rhs);
1122 if (TREE_CODE (cond_rhs) != INTEGER_CST
1123 || TREE_OVERFLOW (cond_rhs))
1124 return 0;
1127 if (((code == NE_EXPR && e1 == false_edge)
1128 || (code == EQ_EXPR && e1 == true_edge))
1129 && arg0 == lhs
1130 && ((arg1 == rhs1
1131 && operand_equal_for_phi_arg_p (rhs2, cond_lhs)
1132 && neutral_element_p (code_def, cond_rhs, true))
1133 || (arg1 == rhs2
1134 && operand_equal_for_phi_arg_p (rhs1, cond_lhs)
1135 && neutral_element_p (code_def, cond_rhs, false))
1136 || (operand_equal_for_phi_arg_p (arg1, cond_rhs)
1137 && ((operand_equal_for_phi_arg_p (rhs2, cond_lhs)
1138 && absorbing_element_p (code_def, cond_rhs, true, rhs2))
1139 || (operand_equal_for_phi_arg_p (rhs1, cond_lhs)
1140 && absorbing_element_p (code_def,
1141 cond_rhs, false, rhs2))))))
1143 gsi = gsi_for_stmt (cond);
1144 /* Moving ASSIGN might change VR of lhs, e.g. when moving u_6
1145 def-stmt in:
1146 if (n_5 != 0)
1147 goto <bb 3>;
1148 else
1149 goto <bb 4>;
1151 <bb 3>:
1152 # RANGE [0, 4294967294]
1153 u_6 = n_5 + 4294967295;
1155 <bb 4>:
1156 # u_3 = PHI <u_6(3), 4294967295(2)> */
1157 reset_flow_sensitive_info (lhs);
1158 if (INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
1160 /* If available, we can use VR of phi result at least. */
1161 tree phires = gimple_phi_result (phi);
1162 struct range_info_def *phires_range_info
1163 = SSA_NAME_RANGE_INFO (phires);
1164 if (phires_range_info)
1165 duplicate_ssa_name_range_info (lhs, SSA_NAME_RANGE_TYPE (phires),
1166 phires_range_info);
1168 gimple_stmt_iterator gsi_from;
1169 for (int i = prep_cnt - 1; i >= 0; --i)
1171 tree plhs = gimple_assign_lhs (prep_stmt[i]);
1172 reset_flow_sensitive_info (plhs);
1173 gsi_from = gsi_for_stmt (prep_stmt[i]);
1174 gsi_move_before (&gsi_from, &gsi);
1176 gsi_from = gsi_for_stmt (assign);
1177 gsi_move_before (&gsi_from, &gsi);
1178 replace_phi_edge_with_variable (cond_bb, e1, phi, lhs);
1179 return 2;
1182 return 0;
1185 /* The function minmax_replacement does the main work of doing the minmax
1186 replacement. Return true if the replacement is done. Otherwise return
1187 false.
1188 BB is the basic block where the replacement is going to be done on. ARG0
1189 is argument 0 from the PHI. Likewise for ARG1. */
1191 static bool
1192 minmax_replacement (basic_block cond_bb, basic_block middle_bb,
1193 edge e0, edge e1, gimple *phi,
1194 tree arg0, tree arg1)
1196 tree result, type;
1197 gcond *cond;
1198 gassign *new_stmt;
1199 edge true_edge, false_edge;
1200 enum tree_code cmp, minmax, ass_code;
1201 tree smaller, alt_smaller, larger, alt_larger, arg_true, arg_false;
1202 gimple_stmt_iterator gsi, gsi_from;
1204 type = TREE_TYPE (PHI_RESULT (phi));
1206 /* The optimization may be unsafe due to NaNs. */
1207 if (HONOR_NANS (type) || HONOR_SIGNED_ZEROS (type))
1208 return false;
1210 cond = as_a <gcond *> (last_stmt (cond_bb));
1211 cmp = gimple_cond_code (cond);
1213 /* This transformation is only valid for order comparisons. Record which
1214 operand is smaller/larger if the result of the comparison is true. */
1215 alt_smaller = NULL_TREE;
1216 alt_larger = NULL_TREE;
1217 if (cmp == LT_EXPR || cmp == LE_EXPR)
1219 smaller = gimple_cond_lhs (cond);
1220 larger = gimple_cond_rhs (cond);
1221 /* If we have smaller < CST it is equivalent to smaller <= CST-1.
1222 Likewise smaller <= CST is equivalent to smaller < CST+1. */
1223 if (TREE_CODE (larger) == INTEGER_CST)
1225 if (cmp == LT_EXPR)
1227 bool overflow;
1228 wide_int alt = wi::sub (wi::to_wide (larger), 1,
1229 TYPE_SIGN (TREE_TYPE (larger)),
1230 &overflow);
1231 if (! overflow)
1232 alt_larger = wide_int_to_tree (TREE_TYPE (larger), alt);
1234 else
1236 bool overflow;
1237 wide_int alt = wi::add (wi::to_wide (larger), 1,
1238 TYPE_SIGN (TREE_TYPE (larger)),
1239 &overflow);
1240 if (! overflow)
1241 alt_larger = wide_int_to_tree (TREE_TYPE (larger), alt);
1245 else if (cmp == GT_EXPR || cmp == GE_EXPR)
1247 smaller = gimple_cond_rhs (cond);
1248 larger = gimple_cond_lhs (cond);
1249 /* If we have larger > CST it is equivalent to larger >= CST+1.
1250 Likewise larger >= CST is equivalent to larger > CST-1. */
1251 if (TREE_CODE (smaller) == INTEGER_CST)
1253 if (cmp == GT_EXPR)
1255 bool overflow;
1256 wide_int alt = wi::add (wi::to_wide (smaller), 1,
1257 TYPE_SIGN (TREE_TYPE (smaller)),
1258 &overflow);
1259 if (! overflow)
1260 alt_smaller = wide_int_to_tree (TREE_TYPE (smaller), alt);
1262 else
1264 bool overflow;
1265 wide_int alt = wi::sub (wi::to_wide (smaller), 1,
1266 TYPE_SIGN (TREE_TYPE (smaller)),
1267 &overflow);
1268 if (! overflow)
1269 alt_smaller = wide_int_to_tree (TREE_TYPE (smaller), alt);
1273 else
1274 return false;
1276 /* We need to know which is the true edge and which is the false
1277 edge so that we know if have abs or negative abs. */
1278 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1280 /* Forward the edges over the middle basic block. */
1281 if (true_edge->dest == middle_bb)
1282 true_edge = EDGE_SUCC (true_edge->dest, 0);
1283 if (false_edge->dest == middle_bb)
1284 false_edge = EDGE_SUCC (false_edge->dest, 0);
1286 if (true_edge == e0)
1288 gcc_assert (false_edge == e1);
1289 arg_true = arg0;
1290 arg_false = arg1;
1292 else
1294 gcc_assert (false_edge == e0);
1295 gcc_assert (true_edge == e1);
1296 arg_true = arg1;
1297 arg_false = arg0;
1300 if (empty_block_p (middle_bb))
1302 if ((operand_equal_for_phi_arg_p (arg_true, smaller)
1303 || (alt_smaller
1304 && operand_equal_for_phi_arg_p (arg_true, alt_smaller)))
1305 && (operand_equal_for_phi_arg_p (arg_false, larger)
1306 || (alt_larger
1307 && operand_equal_for_phi_arg_p (arg_true, alt_larger))))
1309 /* Case
1311 if (smaller < larger)
1312 rslt = smaller;
1313 else
1314 rslt = larger; */
1315 minmax = MIN_EXPR;
1317 else if ((operand_equal_for_phi_arg_p (arg_false, smaller)
1318 || (alt_smaller
1319 && operand_equal_for_phi_arg_p (arg_false, alt_smaller)))
1320 && (operand_equal_for_phi_arg_p (arg_true, larger)
1321 || (alt_larger
1322 && operand_equal_for_phi_arg_p (arg_true, alt_larger))))
1323 minmax = MAX_EXPR;
1324 else
1325 return false;
1327 else
1329 /* Recognize the following case, assuming d <= u:
1331 if (a <= u)
1332 b = MAX (a, d);
1333 x = PHI <b, u>
1335 This is equivalent to
1337 b = MAX (a, d);
1338 x = MIN (b, u); */
1340 gimple *assign = last_and_only_stmt (middle_bb);
1341 tree lhs, op0, op1, bound;
1343 if (!assign
1344 || gimple_code (assign) != GIMPLE_ASSIGN)
1345 return false;
1347 lhs = gimple_assign_lhs (assign);
1348 ass_code = gimple_assign_rhs_code (assign);
1349 if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
1350 return false;
1351 op0 = gimple_assign_rhs1 (assign);
1352 op1 = gimple_assign_rhs2 (assign);
1354 if (true_edge->src == middle_bb)
1356 /* We got here if the condition is true, i.e., SMALLER < LARGER. */
1357 if (!operand_equal_for_phi_arg_p (lhs, arg_true))
1358 return false;
1360 if (operand_equal_for_phi_arg_p (arg_false, larger)
1361 || (alt_larger
1362 && operand_equal_for_phi_arg_p (arg_false, alt_larger)))
1364 /* Case
1366 if (smaller < larger)
1368 r' = MAX_EXPR (smaller, bound)
1370 r = PHI <r', larger> --> to be turned to MIN_EXPR. */
1371 if (ass_code != MAX_EXPR)
1372 return false;
1374 minmax = MIN_EXPR;
1375 if (operand_equal_for_phi_arg_p (op0, smaller)
1376 || (alt_smaller
1377 && operand_equal_for_phi_arg_p (op0, alt_smaller)))
1378 bound = op1;
1379 else if (operand_equal_for_phi_arg_p (op1, smaller)
1380 || (alt_smaller
1381 && operand_equal_for_phi_arg_p (op1, alt_smaller)))
1382 bound = op0;
1383 else
1384 return false;
1386 /* We need BOUND <= LARGER. */
1387 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
1388 bound, larger)))
1389 return false;
1391 else if (operand_equal_for_phi_arg_p (arg_false, smaller)
1392 || (alt_smaller
1393 && operand_equal_for_phi_arg_p (arg_false, alt_smaller)))
1395 /* Case
1397 if (smaller < larger)
1399 r' = MIN_EXPR (larger, bound)
1401 r = PHI <r', smaller> --> to be turned to MAX_EXPR. */
1402 if (ass_code != MIN_EXPR)
1403 return false;
1405 minmax = MAX_EXPR;
1406 if (operand_equal_for_phi_arg_p (op0, larger)
1407 || (alt_larger
1408 && operand_equal_for_phi_arg_p (op0, alt_larger)))
1409 bound = op1;
1410 else if (operand_equal_for_phi_arg_p (op1, larger)
1411 || (alt_larger
1412 && operand_equal_for_phi_arg_p (op1, alt_larger)))
1413 bound = op0;
1414 else
1415 return false;
1417 /* We need BOUND >= SMALLER. */
1418 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
1419 bound, smaller)))
1420 return false;
1422 else
1423 return false;
1425 else
1427 /* We got here if the condition is false, i.e., SMALLER > LARGER. */
1428 if (!operand_equal_for_phi_arg_p (lhs, arg_false))
1429 return false;
1431 if (operand_equal_for_phi_arg_p (arg_true, larger)
1432 || (alt_larger
1433 && operand_equal_for_phi_arg_p (arg_true, alt_larger)))
1435 /* Case
1437 if (smaller > larger)
1439 r' = MIN_EXPR (smaller, bound)
1441 r = PHI <r', larger> --> to be turned to MAX_EXPR. */
1442 if (ass_code != MIN_EXPR)
1443 return false;
1445 minmax = MAX_EXPR;
1446 if (operand_equal_for_phi_arg_p (op0, smaller)
1447 || (alt_smaller
1448 && operand_equal_for_phi_arg_p (op0, alt_smaller)))
1449 bound = op1;
1450 else if (operand_equal_for_phi_arg_p (op1, smaller)
1451 || (alt_smaller
1452 && operand_equal_for_phi_arg_p (op1, alt_smaller)))
1453 bound = op0;
1454 else
1455 return false;
1457 /* We need BOUND >= LARGER. */
1458 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
1459 bound, larger)))
1460 return false;
1462 else if (operand_equal_for_phi_arg_p (arg_true, smaller)
1463 || (alt_smaller
1464 && operand_equal_for_phi_arg_p (arg_true, alt_smaller)))
1466 /* Case
1468 if (smaller > larger)
1470 r' = MAX_EXPR (larger, bound)
1472 r = PHI <r', smaller> --> to be turned to MIN_EXPR. */
1473 if (ass_code != MAX_EXPR)
1474 return false;
1476 minmax = MIN_EXPR;
1477 if (operand_equal_for_phi_arg_p (op0, larger))
1478 bound = op1;
1479 else if (operand_equal_for_phi_arg_p (op1, larger))
1480 bound = op0;
1481 else
1482 return false;
1484 /* We need BOUND <= SMALLER. */
1485 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
1486 bound, smaller)))
1487 return false;
1489 else
1490 return false;
1493 /* Move the statement from the middle block. */
1494 gsi = gsi_last_bb (cond_bb);
1495 gsi_from = gsi_last_nondebug_bb (middle_bb);
1496 reset_flow_sensitive_info (SINGLE_SSA_TREE_OPERAND (gsi_stmt (gsi_from),
1497 SSA_OP_DEF));
1498 gsi_move_before (&gsi_from, &gsi);
1501 /* Create an SSA var to hold the min/max result. If we're the only
1502 things setting the target PHI, then we can clone the PHI
1503 variable. Otherwise we must create a new one. */
1504 result = PHI_RESULT (phi);
1505 if (EDGE_COUNT (gimple_bb (phi)->preds) == 2)
1506 result = duplicate_ssa_name (result, NULL);
1507 else
1508 result = make_ssa_name (TREE_TYPE (result));
1510 /* Emit the statement to compute min/max. */
1511 new_stmt = gimple_build_assign (result, minmax, arg0, arg1);
1512 gsi = gsi_last_bb (cond_bb);
1513 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
1515 replace_phi_edge_with_variable (cond_bb, e1, phi, result);
1517 return true;
1520 /* The function absolute_replacement does the main work of doing the absolute
1521 replacement. Return true if the replacement is done. Otherwise return
1522 false.
1523 bb is the basic block where the replacement is going to be done on. arg0
1524 is argument 0 from the phi. Likewise for arg1. */
1526 static bool
1527 abs_replacement (basic_block cond_bb, basic_block middle_bb,
1528 edge e0 ATTRIBUTE_UNUSED, edge e1,
1529 gimple *phi, tree arg0, tree arg1)
1531 tree result;
1532 gassign *new_stmt;
1533 gimple *cond;
1534 gimple_stmt_iterator gsi;
1535 edge true_edge, false_edge;
1536 gimple *assign;
1537 edge e;
1538 tree rhs, lhs;
1539 bool negate;
1540 enum tree_code cond_code;
1542 /* If the type says honor signed zeros we cannot do this
1543 optimization. */
1544 if (HONOR_SIGNED_ZEROS (arg1))
1545 return false;
1547 /* OTHER_BLOCK must have only one executable statement which must have the
1548 form arg0 = -arg1 or arg1 = -arg0. */
1550 assign = last_and_only_stmt (middle_bb);
1551 /* If we did not find the proper negation assignment, then we can not
1552 optimize. */
1553 if (assign == NULL)
1554 return false;
1556 /* If we got here, then we have found the only executable statement
1557 in OTHER_BLOCK. If it is anything other than arg = -arg1 or
1558 arg1 = -arg0, then we can not optimize. */
1559 if (gimple_code (assign) != GIMPLE_ASSIGN)
1560 return false;
1562 lhs = gimple_assign_lhs (assign);
1564 if (gimple_assign_rhs_code (assign) != NEGATE_EXPR)
1565 return false;
1567 rhs = gimple_assign_rhs1 (assign);
1569 /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */
1570 if (!(lhs == arg0 && rhs == arg1)
1571 && !(lhs == arg1 && rhs == arg0))
1572 return false;
1574 cond = last_stmt (cond_bb);
1575 result = PHI_RESULT (phi);
1577 /* Only relationals comparing arg[01] against zero are interesting. */
1578 cond_code = gimple_cond_code (cond);
1579 if (cond_code != GT_EXPR && cond_code != GE_EXPR
1580 && cond_code != LT_EXPR && cond_code != LE_EXPR)
1581 return false;
1583 /* Make sure the conditional is arg[01] OP y. */
1584 if (gimple_cond_lhs (cond) != rhs)
1585 return false;
1587 if (FLOAT_TYPE_P (TREE_TYPE (gimple_cond_rhs (cond)))
1588 ? real_zerop (gimple_cond_rhs (cond))
1589 : integer_zerop (gimple_cond_rhs (cond)))
1591 else
1592 return false;
1594 /* We need to know which is the true edge and which is the false
1595 edge so that we know if have abs or negative abs. */
1596 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1598 /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
1599 will need to negate the result. Similarly for LT_EXPR/LE_EXPR if
1600 the false edge goes to OTHER_BLOCK. */
1601 if (cond_code == GT_EXPR || cond_code == GE_EXPR)
1602 e = true_edge;
1603 else
1604 e = false_edge;
1606 if (e->dest == middle_bb)
1607 negate = true;
1608 else
1609 negate = false;
1611 /* If the code negates only iff positive then make sure to not
1612 introduce undefined behavior when negating or computing the absolute.
1613 ??? We could use range info if present to check for arg1 == INT_MIN. */
1614 if (negate
1615 && (ANY_INTEGRAL_TYPE_P (TREE_TYPE (arg1))
1616 && ! TYPE_OVERFLOW_WRAPS (TREE_TYPE (arg1))))
1617 return false;
1619 result = duplicate_ssa_name (result, NULL);
1621 if (negate)
1622 lhs = make_ssa_name (TREE_TYPE (result));
1623 else
1624 lhs = result;
1626 /* Build the modify expression with abs expression. */
1627 new_stmt = gimple_build_assign (lhs, ABS_EXPR, rhs);
1629 gsi = gsi_last_bb (cond_bb);
1630 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
1632 if (negate)
1634 /* Get the right GSI. We want to insert after the recently
1635 added ABS_EXPR statement (which we know is the first statement
1636 in the block. */
1637 new_stmt = gimple_build_assign (result, NEGATE_EXPR, lhs);
1639 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
1642 replace_phi_edge_with_variable (cond_bb, e1, phi, result);
1644 /* Note that we optimized this PHI. */
1645 return true;
1648 /* Auxiliary functions to determine the set of memory accesses which
1649 can't trap because they are preceded by accesses to the same memory
1650 portion. We do that for MEM_REFs, so we only need to track
1651 the SSA_NAME of the pointer indirectly referenced. The algorithm
1652 simply is a walk over all instructions in dominator order. When
1653 we see an MEM_REF we determine if we've already seen a same
1654 ref anywhere up to the root of the dominator tree. If we do the
1655 current access can't trap. If we don't see any dominating access
1656 the current access might trap, but might also make later accesses
1657 non-trapping, so we remember it. We need to be careful with loads
1658 or stores, for instance a load might not trap, while a store would,
1659 so if we see a dominating read access this doesn't mean that a later
1660 write access would not trap. Hence we also need to differentiate the
1661 type of access(es) seen.
1663 ??? We currently are very conservative and assume that a load might
1664 trap even if a store doesn't (write-only memory). This probably is
1665 overly conservative. */
1667 /* A hash-table of SSA_NAMEs, and in which basic block an MEM_REF
1668 through it was seen, which would constitute a no-trap region for
1669 same accesses. */
1670 struct name_to_bb
1672 unsigned int ssa_name_ver;
1673 unsigned int phase;
1674 bool store;
1675 HOST_WIDE_INT offset, size;
1676 basic_block bb;
1679 /* Hashtable helpers. */
1681 struct ssa_names_hasher : free_ptr_hash <name_to_bb>
1683 static inline hashval_t hash (const name_to_bb *);
1684 static inline bool equal (const name_to_bb *, const name_to_bb *);
1687 /* Used for quick clearing of the hash-table when we see calls.
1688 Hash entries with phase < nt_call_phase are invalid. */
1689 static unsigned int nt_call_phase;
1691 /* The hash function. */
1693 inline hashval_t
1694 ssa_names_hasher::hash (const name_to_bb *n)
1696 return n->ssa_name_ver ^ (((hashval_t) n->store) << 31)
1697 ^ (n->offset << 6) ^ (n->size << 3);
1700 /* The equality function of *P1 and *P2. */
1702 inline bool
1703 ssa_names_hasher::equal (const name_to_bb *n1, const name_to_bb *n2)
1705 return n1->ssa_name_ver == n2->ssa_name_ver
1706 && n1->store == n2->store
1707 && n1->offset == n2->offset
1708 && n1->size == n2->size;
1711 class nontrapping_dom_walker : public dom_walker
1713 public:
1714 nontrapping_dom_walker (cdi_direction direction, hash_set<tree> *ps)
1715 : dom_walker (direction), m_nontrapping (ps), m_seen_ssa_names (128) {}
1717 virtual edge before_dom_children (basic_block);
1718 virtual void after_dom_children (basic_block);
1720 private:
1722 /* We see the expression EXP in basic block BB. If it's an interesting
1723 expression (an MEM_REF through an SSA_NAME) possibly insert the
1724 expression into the set NONTRAP or the hash table of seen expressions.
1725 STORE is true if this expression is on the LHS, otherwise it's on
1726 the RHS. */
1727 void add_or_mark_expr (basic_block, tree, bool);
1729 hash_set<tree> *m_nontrapping;
1731 /* The hash table for remembering what we've seen. */
1732 hash_table<ssa_names_hasher> m_seen_ssa_names;
1735 /* Called by walk_dominator_tree, when entering the block BB. */
1736 edge
1737 nontrapping_dom_walker::before_dom_children (basic_block bb)
1739 edge e;
1740 edge_iterator ei;
1741 gimple_stmt_iterator gsi;
1743 /* If we haven't seen all our predecessors, clear the hash-table. */
1744 FOR_EACH_EDGE (e, ei, bb->preds)
1745 if ((((size_t)e->src->aux) & 2) == 0)
1747 nt_call_phase++;
1748 break;
1751 /* Mark this BB as being on the path to dominator root and as visited. */
1752 bb->aux = (void*)(1 | 2);
1754 /* And walk the statements in order. */
1755 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1757 gimple *stmt = gsi_stmt (gsi);
1759 if ((gimple_code (stmt) == GIMPLE_ASM && gimple_vdef (stmt))
1760 || (is_gimple_call (stmt)
1761 && (!nonfreeing_call_p (stmt) || !nonbarrier_call_p (stmt))))
1762 nt_call_phase++;
1763 else if (gimple_assign_single_p (stmt) && !gimple_has_volatile_ops (stmt))
1765 add_or_mark_expr (bb, gimple_assign_lhs (stmt), true);
1766 add_or_mark_expr (bb, gimple_assign_rhs1 (stmt), false);
1769 return NULL;
1772 /* Called by walk_dominator_tree, when basic block BB is exited. */
1773 void
1774 nontrapping_dom_walker::after_dom_children (basic_block bb)
1776 /* This BB isn't on the path to dominator root anymore. */
1777 bb->aux = (void*)2;
1780 /* We see the expression EXP in basic block BB. If it's an interesting
1781 expression (an MEM_REF through an SSA_NAME) possibly insert the
1782 expression into the set NONTRAP or the hash table of seen expressions.
1783 STORE is true if this expression is on the LHS, otherwise it's on
1784 the RHS. */
1785 void
1786 nontrapping_dom_walker::add_or_mark_expr (basic_block bb, tree exp, bool store)
1788 HOST_WIDE_INT size;
1790 if (TREE_CODE (exp) == MEM_REF
1791 && TREE_CODE (TREE_OPERAND (exp, 0)) == SSA_NAME
1792 && tree_fits_shwi_p (TREE_OPERAND (exp, 1))
1793 && (size = int_size_in_bytes (TREE_TYPE (exp))) > 0)
1795 tree name = TREE_OPERAND (exp, 0);
1796 struct name_to_bb map;
1797 name_to_bb **slot;
1798 struct name_to_bb *n2bb;
1799 basic_block found_bb = 0;
1801 /* Try to find the last seen MEM_REF through the same
1802 SSA_NAME, which can trap. */
1803 map.ssa_name_ver = SSA_NAME_VERSION (name);
1804 map.phase = 0;
1805 map.bb = 0;
1806 map.store = store;
1807 map.offset = tree_to_shwi (TREE_OPERAND (exp, 1));
1808 map.size = size;
1810 slot = m_seen_ssa_names.find_slot (&map, INSERT);
1811 n2bb = *slot;
1812 if (n2bb && n2bb->phase >= nt_call_phase)
1813 found_bb = n2bb->bb;
1815 /* If we've found a trapping MEM_REF, _and_ it dominates EXP
1816 (it's in a basic block on the path from us to the dominator root)
1817 then we can't trap. */
1818 if (found_bb && (((size_t)found_bb->aux) & 1) == 1)
1820 m_nontrapping->add (exp);
1822 else
1824 /* EXP might trap, so insert it into the hash table. */
1825 if (n2bb)
1827 n2bb->phase = nt_call_phase;
1828 n2bb->bb = bb;
1830 else
1832 n2bb = XNEW (struct name_to_bb);
1833 n2bb->ssa_name_ver = SSA_NAME_VERSION (name);
1834 n2bb->phase = nt_call_phase;
1835 n2bb->bb = bb;
1836 n2bb->store = store;
1837 n2bb->offset = map.offset;
1838 n2bb->size = size;
1839 *slot = n2bb;
1845 /* This is the entry point of gathering non trapping memory accesses.
1846 It will do a dominator walk over the whole function, and it will
1847 make use of the bb->aux pointers. It returns a set of trees
1848 (the MEM_REFs itself) which can't trap. */
1849 static hash_set<tree> *
1850 get_non_trapping (void)
1852 nt_call_phase = 0;
1853 hash_set<tree> *nontrap = new hash_set<tree>;
1854 /* We're going to do a dominator walk, so ensure that we have
1855 dominance information. */
1856 calculate_dominance_info (CDI_DOMINATORS);
1858 nontrapping_dom_walker (CDI_DOMINATORS, nontrap)
1859 .walk (cfun->cfg->x_entry_block_ptr);
1861 clear_aux_for_blocks ();
1862 return nontrap;
1865 /* Do the main work of conditional store replacement. We already know
1866 that the recognized pattern looks like so:
1868 split:
1869 if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
1870 MIDDLE_BB:
1871 something
1872 fallthrough (edge E0)
1873 JOIN_BB:
1874 some more
1876 We check that MIDDLE_BB contains only one store, that that store
1877 doesn't trap (not via NOTRAP, but via checking if an access to the same
1878 memory location dominates us) and that the store has a "simple" RHS. */
1880 static bool
1881 cond_store_replacement (basic_block middle_bb, basic_block join_bb,
1882 edge e0, edge e1, hash_set<tree> *nontrap)
1884 gimple *assign = last_and_only_stmt (middle_bb);
1885 tree lhs, rhs, name, name2;
1886 gphi *newphi;
1887 gassign *new_stmt;
1888 gimple_stmt_iterator gsi;
1889 source_location locus;
1891 /* Check if middle_bb contains of only one store. */
1892 if (!assign
1893 || !gimple_assign_single_p (assign)
1894 || gimple_has_volatile_ops (assign))
1895 return false;
1897 locus = gimple_location (assign);
1898 lhs = gimple_assign_lhs (assign);
1899 rhs = gimple_assign_rhs1 (assign);
1900 if (TREE_CODE (lhs) != MEM_REF
1901 || TREE_CODE (TREE_OPERAND (lhs, 0)) != SSA_NAME
1902 || !is_gimple_reg_type (TREE_TYPE (lhs)))
1903 return false;
1905 /* Prove that we can move the store down. We could also check
1906 TREE_THIS_NOTRAP here, but in that case we also could move stores,
1907 whose value is not available readily, which we want to avoid. */
1908 if (!nontrap->contains (lhs))
1909 return false;
1911 /* Now we've checked the constraints, so do the transformation:
1912 1) Remove the single store. */
1913 gsi = gsi_for_stmt (assign);
1914 unlink_stmt_vdef (assign);
1915 gsi_remove (&gsi, true);
1916 release_defs (assign);
1918 /* Make both store and load use alias-set zero as we have to
1919 deal with the case of the store being a conditional change
1920 of the dynamic type. */
1921 lhs = unshare_expr (lhs);
1922 tree *basep = &lhs;
1923 while (handled_component_p (*basep))
1924 basep = &TREE_OPERAND (*basep, 0);
1925 if (TREE_CODE (*basep) == MEM_REF
1926 || TREE_CODE (*basep) == TARGET_MEM_REF)
1927 TREE_OPERAND (*basep, 1)
1928 = fold_convert (ptr_type_node, TREE_OPERAND (*basep, 1));
1929 else
1930 *basep = build2 (MEM_REF, TREE_TYPE (*basep),
1931 build_fold_addr_expr (*basep),
1932 build_zero_cst (ptr_type_node));
1934 /* 2) Insert a load from the memory of the store to the temporary
1935 on the edge which did not contain the store. */
1936 name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
1937 new_stmt = gimple_build_assign (name, lhs);
1938 gimple_set_location (new_stmt, locus);
1939 gsi_insert_on_edge (e1, new_stmt);
1941 /* 3) Create a PHI node at the join block, with one argument
1942 holding the old RHS, and the other holding the temporary
1943 where we stored the old memory contents. */
1944 name2 = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
1945 newphi = create_phi_node (name2, join_bb);
1946 add_phi_arg (newphi, rhs, e0, locus);
1947 add_phi_arg (newphi, name, e1, locus);
1949 lhs = unshare_expr (lhs);
1950 new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
1952 /* 4) Insert that PHI node. */
1953 gsi = gsi_after_labels (join_bb);
1954 if (gsi_end_p (gsi))
1956 gsi = gsi_last_bb (join_bb);
1957 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
1959 else
1960 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
1962 return true;
1965 /* Do the main work of conditional store replacement. */
1967 static bool
1968 cond_if_else_store_replacement_1 (basic_block then_bb, basic_block else_bb,
1969 basic_block join_bb, gimple *then_assign,
1970 gimple *else_assign)
1972 tree lhs_base, lhs, then_rhs, else_rhs, name;
1973 source_location then_locus, else_locus;
1974 gimple_stmt_iterator gsi;
1975 gphi *newphi;
1976 gassign *new_stmt;
1978 if (then_assign == NULL
1979 || !gimple_assign_single_p (then_assign)
1980 || gimple_clobber_p (then_assign)
1981 || gimple_has_volatile_ops (then_assign)
1982 || else_assign == NULL
1983 || !gimple_assign_single_p (else_assign)
1984 || gimple_clobber_p (else_assign)
1985 || gimple_has_volatile_ops (else_assign))
1986 return false;
1988 lhs = gimple_assign_lhs (then_assign);
1989 if (!is_gimple_reg_type (TREE_TYPE (lhs))
1990 || !operand_equal_p (lhs, gimple_assign_lhs (else_assign), 0))
1991 return false;
1993 lhs_base = get_base_address (lhs);
1994 if (lhs_base == NULL_TREE
1995 || (!DECL_P (lhs_base) && TREE_CODE (lhs_base) != MEM_REF))
1996 return false;
1998 then_rhs = gimple_assign_rhs1 (then_assign);
1999 else_rhs = gimple_assign_rhs1 (else_assign);
2000 then_locus = gimple_location (then_assign);
2001 else_locus = gimple_location (else_assign);
2003 /* Now we've checked the constraints, so do the transformation:
2004 1) Remove the stores. */
2005 gsi = gsi_for_stmt (then_assign);
2006 unlink_stmt_vdef (then_assign);
2007 gsi_remove (&gsi, true);
2008 release_defs (then_assign);
2010 gsi = gsi_for_stmt (else_assign);
2011 unlink_stmt_vdef (else_assign);
2012 gsi_remove (&gsi, true);
2013 release_defs (else_assign);
2015 /* 2) Create a PHI node at the join block, with one argument
2016 holding the old RHS, and the other holding the temporary
2017 where we stored the old memory contents. */
2018 name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
2019 newphi = create_phi_node (name, join_bb);
2020 add_phi_arg (newphi, then_rhs, EDGE_SUCC (then_bb, 0), then_locus);
2021 add_phi_arg (newphi, else_rhs, EDGE_SUCC (else_bb, 0), else_locus);
2023 new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
2025 /* 3) Insert that PHI node. */
2026 gsi = gsi_after_labels (join_bb);
2027 if (gsi_end_p (gsi))
2029 gsi = gsi_last_bb (join_bb);
2030 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
2032 else
2033 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
2035 return true;
2038 /* Conditional store replacement. We already know
2039 that the recognized pattern looks like so:
2041 split:
2042 if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
2043 THEN_BB:
2045 X = Y;
2047 goto JOIN_BB;
2048 ELSE_BB:
2050 X = Z;
2052 fallthrough (edge E0)
2053 JOIN_BB:
2054 some more
2056 We check that it is safe to sink the store to JOIN_BB by verifying that
2057 there are no read-after-write or write-after-write dependencies in
2058 THEN_BB and ELSE_BB. */
2060 static bool
2061 cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb,
2062 basic_block join_bb)
2064 gimple *then_assign = last_and_only_stmt (then_bb);
2065 gimple *else_assign = last_and_only_stmt (else_bb);
2066 vec<data_reference_p> then_datarefs, else_datarefs;
2067 vec<ddr_p> then_ddrs, else_ddrs;
2068 gimple *then_store, *else_store;
2069 bool found, ok = false, res;
2070 struct data_dependence_relation *ddr;
2071 data_reference_p then_dr, else_dr;
2072 int i, j;
2073 tree then_lhs, else_lhs;
2074 basic_block blocks[3];
2076 if (MAX_STORES_TO_SINK == 0)
2077 return false;
2079 /* Handle the case with single statement in THEN_BB and ELSE_BB. */
2080 if (then_assign && else_assign)
2081 return cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
2082 then_assign, else_assign);
2084 /* Find data references. */
2085 then_datarefs.create (1);
2086 else_datarefs.create (1);
2087 if ((find_data_references_in_bb (NULL, then_bb, &then_datarefs)
2088 == chrec_dont_know)
2089 || !then_datarefs.length ()
2090 || (find_data_references_in_bb (NULL, else_bb, &else_datarefs)
2091 == chrec_dont_know)
2092 || !else_datarefs.length ())
2094 free_data_refs (then_datarefs);
2095 free_data_refs (else_datarefs);
2096 return false;
2099 /* Find pairs of stores with equal LHS. */
2100 auto_vec<gimple *, 1> then_stores, else_stores;
2101 FOR_EACH_VEC_ELT (then_datarefs, i, then_dr)
2103 if (DR_IS_READ (then_dr))
2104 continue;
2106 then_store = DR_STMT (then_dr);
2107 then_lhs = gimple_get_lhs (then_store);
2108 if (then_lhs == NULL_TREE)
2109 continue;
2110 found = false;
2112 FOR_EACH_VEC_ELT (else_datarefs, j, else_dr)
2114 if (DR_IS_READ (else_dr))
2115 continue;
2117 else_store = DR_STMT (else_dr);
2118 else_lhs = gimple_get_lhs (else_store);
2119 if (else_lhs == NULL_TREE)
2120 continue;
2122 if (operand_equal_p (then_lhs, else_lhs, 0))
2124 found = true;
2125 break;
2129 if (!found)
2130 continue;
2132 then_stores.safe_push (then_store);
2133 else_stores.safe_push (else_store);
2136 /* No pairs of stores found. */
2137 if (!then_stores.length ()
2138 || then_stores.length () > (unsigned) MAX_STORES_TO_SINK)
2140 free_data_refs (then_datarefs);
2141 free_data_refs (else_datarefs);
2142 return false;
2145 /* Compute and check data dependencies in both basic blocks. */
2146 then_ddrs.create (1);
2147 else_ddrs.create (1);
2148 if (!compute_all_dependences (then_datarefs, &then_ddrs,
2149 vNULL, false)
2150 || !compute_all_dependences (else_datarefs, &else_ddrs,
2151 vNULL, false))
2153 free_dependence_relations (then_ddrs);
2154 free_dependence_relations (else_ddrs);
2155 free_data_refs (then_datarefs);
2156 free_data_refs (else_datarefs);
2157 return false;
2159 blocks[0] = then_bb;
2160 blocks[1] = else_bb;
2161 blocks[2] = join_bb;
2162 renumber_gimple_stmt_uids_in_blocks (blocks, 3);
2164 /* Check that there are no read-after-write or write-after-write dependencies
2165 in THEN_BB. */
2166 FOR_EACH_VEC_ELT (then_ddrs, i, ddr)
2168 struct data_reference *dra = DDR_A (ddr);
2169 struct data_reference *drb = DDR_B (ddr);
2171 if (DDR_ARE_DEPENDENT (ddr) != chrec_known
2172 && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
2173 && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
2174 || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
2175 && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
2176 || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
2178 free_dependence_relations (then_ddrs);
2179 free_dependence_relations (else_ddrs);
2180 free_data_refs (then_datarefs);
2181 free_data_refs (else_datarefs);
2182 return false;
2186 /* Check that there are no read-after-write or write-after-write dependencies
2187 in ELSE_BB. */
2188 FOR_EACH_VEC_ELT (else_ddrs, i, ddr)
2190 struct data_reference *dra = DDR_A (ddr);
2191 struct data_reference *drb = DDR_B (ddr);
2193 if (DDR_ARE_DEPENDENT (ddr) != chrec_known
2194 && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
2195 && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
2196 || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
2197 && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
2198 || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
2200 free_dependence_relations (then_ddrs);
2201 free_dependence_relations (else_ddrs);
2202 free_data_refs (then_datarefs);
2203 free_data_refs (else_datarefs);
2204 return false;
2208 /* Sink stores with same LHS. */
2209 FOR_EACH_VEC_ELT (then_stores, i, then_store)
2211 else_store = else_stores[i];
2212 res = cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
2213 then_store, else_store);
2214 ok = ok || res;
2217 free_dependence_relations (then_ddrs);
2218 free_dependence_relations (else_ddrs);
2219 free_data_refs (then_datarefs);
2220 free_data_refs (else_datarefs);
2222 return ok;
2225 /* Return TRUE if STMT has a VUSE whose corresponding VDEF is in BB. */
2227 static bool
2228 local_mem_dependence (gimple *stmt, basic_block bb)
2230 tree vuse = gimple_vuse (stmt);
2231 gimple *def;
2233 if (!vuse)
2234 return false;
2236 def = SSA_NAME_DEF_STMT (vuse);
2237 return (def && gimple_bb (def) == bb);
2240 /* Given a "diamond" control-flow pattern where BB0 tests a condition,
2241 BB1 and BB2 are "then" and "else" blocks dependent on this test,
2242 and BB3 rejoins control flow following BB1 and BB2, look for
2243 opportunities to hoist loads as follows. If BB3 contains a PHI of
2244 two loads, one each occurring in BB1 and BB2, and the loads are
2245 provably of adjacent fields in the same structure, then move both
2246 loads into BB0. Of course this can only be done if there are no
2247 dependencies preventing such motion.
2249 One of the hoisted loads will always be speculative, so the
2250 transformation is currently conservative:
2252 - The fields must be strictly adjacent.
2253 - The two fields must occupy a single memory block that is
2254 guaranteed to not cross a page boundary.
2256 The last is difficult to prove, as such memory blocks should be
2257 aligned on the minimum of the stack alignment boundary and the
2258 alignment guaranteed by heap allocation interfaces. Thus we rely
2259 on a parameter for the alignment value.
2261 Provided a good value is used for the last case, the first
2262 restriction could possibly be relaxed. */
2264 static void
2265 hoist_adjacent_loads (basic_block bb0, basic_block bb1,
2266 basic_block bb2, basic_block bb3)
2268 int param_align = PARAM_VALUE (PARAM_L1_CACHE_LINE_SIZE);
2269 unsigned param_align_bits = (unsigned) (param_align * BITS_PER_UNIT);
2270 gphi_iterator gsi;
2272 /* Walk the phis in bb3 looking for an opportunity. We are looking
2273 for phis of two SSA names, one each of which is defined in bb1 and
2274 bb2. */
2275 for (gsi = gsi_start_phis (bb3); !gsi_end_p (gsi); gsi_next (&gsi))
2277 gphi *phi_stmt = gsi.phi ();
2278 gimple *def1, *def2;
2279 tree arg1, arg2, ref1, ref2, field1, field2;
2280 tree tree_offset1, tree_offset2, tree_size2, next;
2281 int offset1, offset2, size2;
2282 unsigned align1;
2283 gimple_stmt_iterator gsi2;
2284 basic_block bb_for_def1, bb_for_def2;
2286 if (gimple_phi_num_args (phi_stmt) != 2
2287 || virtual_operand_p (gimple_phi_result (phi_stmt)))
2288 continue;
2290 arg1 = gimple_phi_arg_def (phi_stmt, 0);
2291 arg2 = gimple_phi_arg_def (phi_stmt, 1);
2293 if (TREE_CODE (arg1) != SSA_NAME
2294 || TREE_CODE (arg2) != SSA_NAME
2295 || SSA_NAME_IS_DEFAULT_DEF (arg1)
2296 || SSA_NAME_IS_DEFAULT_DEF (arg2))
2297 continue;
2299 def1 = SSA_NAME_DEF_STMT (arg1);
2300 def2 = SSA_NAME_DEF_STMT (arg2);
2302 if ((gimple_bb (def1) != bb1 || gimple_bb (def2) != bb2)
2303 && (gimple_bb (def2) != bb1 || gimple_bb (def1) != bb2))
2304 continue;
2306 /* Check the mode of the arguments to be sure a conditional move
2307 can be generated for it. */
2308 if (optab_handler (movcc_optab, TYPE_MODE (TREE_TYPE (arg1)))
2309 == CODE_FOR_nothing)
2310 continue;
2312 /* Both statements must be assignments whose RHS is a COMPONENT_REF. */
2313 if (!gimple_assign_single_p (def1)
2314 || !gimple_assign_single_p (def2)
2315 || gimple_has_volatile_ops (def1)
2316 || gimple_has_volatile_ops (def2))
2317 continue;
2319 ref1 = gimple_assign_rhs1 (def1);
2320 ref2 = gimple_assign_rhs1 (def2);
2322 if (TREE_CODE (ref1) != COMPONENT_REF
2323 || TREE_CODE (ref2) != COMPONENT_REF)
2324 continue;
2326 /* The zeroth operand of the two component references must be
2327 identical. It is not sufficient to compare get_base_address of
2328 the two references, because this could allow for different
2329 elements of the same array in the two trees. It is not safe to
2330 assume that the existence of one array element implies the
2331 existence of a different one. */
2332 if (!operand_equal_p (TREE_OPERAND (ref1, 0), TREE_OPERAND (ref2, 0), 0))
2333 continue;
2335 field1 = TREE_OPERAND (ref1, 1);
2336 field2 = TREE_OPERAND (ref2, 1);
2338 /* Check for field adjacency, and ensure field1 comes first. */
2339 for (next = DECL_CHAIN (field1);
2340 next && TREE_CODE (next) != FIELD_DECL;
2341 next = DECL_CHAIN (next))
2344 if (next != field2)
2346 for (next = DECL_CHAIN (field2);
2347 next && TREE_CODE (next) != FIELD_DECL;
2348 next = DECL_CHAIN (next))
2351 if (next != field1)
2352 continue;
2354 std::swap (field1, field2);
2355 std::swap (def1, def2);
2358 bb_for_def1 = gimple_bb (def1);
2359 bb_for_def2 = gimple_bb (def2);
2361 /* Check for proper alignment of the first field. */
2362 tree_offset1 = bit_position (field1);
2363 tree_offset2 = bit_position (field2);
2364 tree_size2 = DECL_SIZE (field2);
2366 if (!tree_fits_uhwi_p (tree_offset1)
2367 || !tree_fits_uhwi_p (tree_offset2)
2368 || !tree_fits_uhwi_p (tree_size2))
2369 continue;
2371 offset1 = tree_to_uhwi (tree_offset1);
2372 offset2 = tree_to_uhwi (tree_offset2);
2373 size2 = tree_to_uhwi (tree_size2);
2374 align1 = DECL_ALIGN (field1) % param_align_bits;
2376 if (offset1 % BITS_PER_UNIT != 0)
2377 continue;
2379 /* For profitability, the two field references should fit within
2380 a single cache line. */
2381 if (align1 + offset2 - offset1 + size2 > param_align_bits)
2382 continue;
2384 /* The two expressions cannot be dependent upon vdefs defined
2385 in bb1/bb2. */
2386 if (local_mem_dependence (def1, bb_for_def1)
2387 || local_mem_dependence (def2, bb_for_def2))
2388 continue;
2390 /* The conditions are satisfied; hoist the loads from bb1 and bb2 into
2391 bb0. We hoist the first one first so that a cache miss is handled
2392 efficiently regardless of hardware cache-fill policy. */
2393 gsi2 = gsi_for_stmt (def1);
2394 gsi_move_to_bb_end (&gsi2, bb0);
2395 gsi2 = gsi_for_stmt (def2);
2396 gsi_move_to_bb_end (&gsi2, bb0);
2398 if (dump_file && (dump_flags & TDF_DETAILS))
2400 fprintf (dump_file,
2401 "\nHoisting adjacent loads from %d and %d into %d: \n",
2402 bb_for_def1->index, bb_for_def2->index, bb0->index);
2403 print_gimple_stmt (dump_file, def1, 0, TDF_VOPS|TDF_MEMSYMS);
2404 print_gimple_stmt (dump_file, def2, 0, TDF_VOPS|TDF_MEMSYMS);
2409 /* Determine whether we should attempt to hoist adjacent loads out of
2410 diamond patterns in pass_phiopt. Always hoist loads if
2411 -fhoist-adjacent-loads is specified and the target machine has
2412 both a conditional move instruction and a defined cache line size. */
2414 static bool
2415 gate_hoist_loads (void)
2417 return (flag_hoist_adjacent_loads == 1
2418 && PARAM_VALUE (PARAM_L1_CACHE_LINE_SIZE)
2419 && HAVE_conditional_move);
2422 /* This pass tries to replaces an if-then-else block with an
2423 assignment. We have four kinds of transformations. Some of these
2424 transformations are also performed by the ifcvt RTL optimizer.
2426 Conditional Replacement
2427 -----------------------
2429 This transformation, implemented in conditional_replacement,
2430 replaces
2432 bb0:
2433 if (cond) goto bb2; else goto bb1;
2434 bb1:
2435 bb2:
2436 x = PHI <0 (bb1), 1 (bb0), ...>;
2438 with
2440 bb0:
2441 x' = cond;
2442 goto bb2;
2443 bb2:
2444 x = PHI <x' (bb0), ...>;
2446 We remove bb1 as it becomes unreachable. This occurs often due to
2447 gimplification of conditionals.
2449 Value Replacement
2450 -----------------
2452 This transformation, implemented in value_replacement, replaces
2454 bb0:
2455 if (a != b) goto bb2; else goto bb1;
2456 bb1:
2457 bb2:
2458 x = PHI <a (bb1), b (bb0), ...>;
2460 with
2462 bb0:
2463 bb2:
2464 x = PHI <b (bb0), ...>;
2466 This opportunity can sometimes occur as a result of other
2467 optimizations.
2470 Another case caught by value replacement looks like this:
2472 bb0:
2473 t1 = a == CONST;
2474 t2 = b > c;
2475 t3 = t1 & t2;
2476 if (t3 != 0) goto bb1; else goto bb2;
2477 bb1:
2478 bb2:
2479 x = PHI (CONST, a)
2481 Gets replaced with:
2482 bb0:
2483 bb2:
2484 t1 = a == CONST;
2485 t2 = b > c;
2486 t3 = t1 & t2;
2487 x = a;
2489 ABS Replacement
2490 ---------------
2492 This transformation, implemented in abs_replacement, replaces
2494 bb0:
2495 if (a >= 0) goto bb2; else goto bb1;
2496 bb1:
2497 x = -a;
2498 bb2:
2499 x = PHI <x (bb1), a (bb0), ...>;
2501 with
2503 bb0:
2504 x' = ABS_EXPR< a >;
2505 bb2:
2506 x = PHI <x' (bb0), ...>;
2508 MIN/MAX Replacement
2509 -------------------
2511 This transformation, minmax_replacement replaces
2513 bb0:
2514 if (a <= b) goto bb2; else goto bb1;
2515 bb1:
2516 bb2:
2517 x = PHI <b (bb1), a (bb0), ...>;
2519 with
2521 bb0:
2522 x' = MIN_EXPR (a, b)
2523 bb2:
2524 x = PHI <x' (bb0), ...>;
2526 A similar transformation is done for MAX_EXPR.
2529 This pass also performs a fifth transformation of a slightly different
2530 flavor.
2532 Factor conversion in COND_EXPR
2533 ------------------------------
2535 This transformation factors the conversion out of COND_EXPR with
2536 factor_out_conditional_conversion.
2538 For example:
2539 if (a <= CST) goto <bb 3>; else goto <bb 4>;
2540 <bb 3>:
2541 tmp = (int) a;
2542 <bb 4>:
2543 tmp = PHI <tmp, CST>
2545 Into:
2546 if (a <= CST) goto <bb 3>; else goto <bb 4>;
2547 <bb 3>:
2548 <bb 4>:
2549 a = PHI <a, CST>
2550 tmp = (int) a;
2552 Adjacent Load Hoisting
2553 ----------------------
2555 This transformation replaces
2557 bb0:
2558 if (...) goto bb2; else goto bb1;
2559 bb1:
2560 x1 = (<expr>).field1;
2561 goto bb3;
2562 bb2:
2563 x2 = (<expr>).field2;
2564 bb3:
2565 # x = PHI <x1, x2>;
2567 with
2569 bb0:
2570 x1 = (<expr>).field1;
2571 x2 = (<expr>).field2;
2572 if (...) goto bb2; else goto bb1;
2573 bb1:
2574 goto bb3;
2575 bb2:
2576 bb3:
2577 # x = PHI <x1, x2>;
2579 The purpose of this transformation is to enable generation of conditional
2580 move instructions such as Intel CMOVE or PowerPC ISEL. Because one of
2581 the loads is speculative, the transformation is restricted to very
2582 specific cases to avoid introducing a page fault. We are looking for
2583 the common idiom:
2585 if (...)
2586 x = y->left;
2587 else
2588 x = y->right;
2590 where left and right are typically adjacent pointers in a tree structure. */
2592 namespace {
2594 const pass_data pass_data_phiopt =
2596 GIMPLE_PASS, /* type */
2597 "phiopt", /* name */
2598 OPTGROUP_NONE, /* optinfo_flags */
2599 TV_TREE_PHIOPT, /* tv_id */
2600 ( PROP_cfg | PROP_ssa ), /* properties_required */
2601 0, /* properties_provided */
2602 0, /* properties_destroyed */
2603 0, /* todo_flags_start */
2604 0, /* todo_flags_finish */
2607 class pass_phiopt : public gimple_opt_pass
2609 public:
2610 pass_phiopt (gcc::context *ctxt)
2611 : gimple_opt_pass (pass_data_phiopt, ctxt)
2614 /* opt_pass methods: */
2615 opt_pass * clone () { return new pass_phiopt (m_ctxt); }
2616 virtual bool gate (function *) { return flag_ssa_phiopt; }
2617 virtual unsigned int execute (function *)
2619 return tree_ssa_phiopt_worker (false, gate_hoist_loads ());
2622 }; // class pass_phiopt
2624 } // anon namespace
2626 gimple_opt_pass *
2627 make_pass_phiopt (gcc::context *ctxt)
2629 return new pass_phiopt (ctxt);
2632 namespace {
2634 const pass_data pass_data_cselim =
2636 GIMPLE_PASS, /* type */
2637 "cselim", /* name */
2638 OPTGROUP_NONE, /* optinfo_flags */
2639 TV_TREE_PHIOPT, /* tv_id */
2640 ( PROP_cfg | PROP_ssa ), /* properties_required */
2641 0, /* properties_provided */
2642 0, /* properties_destroyed */
2643 0, /* todo_flags_start */
2644 0, /* todo_flags_finish */
2647 class pass_cselim : public gimple_opt_pass
2649 public:
2650 pass_cselim (gcc::context *ctxt)
2651 : gimple_opt_pass (pass_data_cselim, ctxt)
2654 /* opt_pass methods: */
2655 virtual bool gate (function *) { return flag_tree_cselim; }
2656 virtual unsigned int execute (function *) { return tree_ssa_cs_elim (); }
2658 }; // class pass_cselim
2660 } // anon namespace
2662 gimple_opt_pass *
2663 make_pass_cselim (gcc::context *ctxt)
2665 return new pass_cselim (ctxt);