* gcc.dg/atomic/c11-atomic-exec-5.c (dg-additional-options): Use
[official-gcc.git] / gcc / tree-ssa-phiopt.c
blob052d76014a63c052c238fb4b65a2eee831f1eeb5
1 /* Optimization of PHI nodes by converting them into straightline code.
2 Copyright (C) 2004-2014 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 "hash-table.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "stor-layout.h"
27 #include "flags.h"
28 #include "tm_p.h"
29 #include "basic-block.h"
30 #include "pointer-set.h"
31 #include "tree-ssa-alias.h"
32 #include "internal-fn.h"
33 #include "gimple-expr.h"
34 #include "is-a.h"
35 #include "gimple.h"
36 #include "gimplify.h"
37 #include "gimple-iterator.h"
38 #include "gimplify-me.h"
39 #include "gimple-ssa.h"
40 #include "tree-cfg.h"
41 #include "tree-phinodes.h"
42 #include "ssa-iterators.h"
43 #include "stringpool.h"
44 #include "tree-ssanames.h"
45 #include "expr.h"
46 #include "tree-dfa.h"
47 #include "tree-pass.h"
48 #include "langhooks.h"
49 #include "domwalk.h"
50 #include "cfgloop.h"
51 #include "tree-data-ref.h"
52 #include "gimple-pretty-print.h"
53 #include "insn-config.h"
54 #include "expr.h"
55 #include "optabs.h"
56 #include "tree-scalar-evolution.h"
57 #include "tree-inline.h"
59 #ifndef HAVE_conditional_move
60 #define HAVE_conditional_move (0)
61 #endif
63 static unsigned int tree_ssa_phiopt_worker (bool, bool);
64 static bool conditional_replacement (basic_block, basic_block,
65 edge, edge, gimple, tree, tree);
66 static int value_replacement (basic_block, basic_block,
67 edge, edge, gimple, tree, tree);
68 static bool minmax_replacement (basic_block, basic_block,
69 edge, edge, gimple, tree, tree);
70 static bool abs_replacement (basic_block, basic_block,
71 edge, edge, gimple, tree, tree);
72 static bool neg_replacement (basic_block, basic_block,
73 edge, edge, gimple, tree, tree);
74 static bool cond_store_replacement (basic_block, basic_block, edge, edge,
75 struct pointer_set_t *);
76 static bool cond_if_else_store_replacement (basic_block, basic_block, basic_block);
77 static struct pointer_set_t * get_non_trapping (void);
78 static void replace_phi_edge_with_variable (basic_block, edge, gimple, tree);
79 static void hoist_adjacent_loads (basic_block, basic_block,
80 basic_block, basic_block);
81 static bool gate_hoist_loads (void);
83 /* This pass tries to transform conditional stores into unconditional
84 ones, enabling further simplifications with the simpler then and else
85 blocks. In particular it replaces this:
87 bb0:
88 if (cond) goto bb2; else goto bb1;
89 bb1:
90 *p = RHS;
91 bb2:
93 with
95 bb0:
96 if (cond) goto bb1; else goto bb2;
97 bb1:
98 condtmp' = *p;
99 bb2:
100 condtmp = PHI <RHS, condtmp'>
101 *p = condtmp;
103 This transformation can only be done under several constraints,
104 documented below. It also replaces:
106 bb0:
107 if (cond) goto bb2; else goto bb1;
108 bb1:
109 *p = RHS1;
110 goto bb3;
111 bb2:
112 *p = RHS2;
113 bb3:
115 with
117 bb0:
118 if (cond) goto bb3; else goto bb1;
119 bb1:
120 bb3:
121 condtmp = PHI <RHS1, RHS2>
122 *p = condtmp; */
124 static unsigned int
125 tree_ssa_cs_elim (void)
127 unsigned todo;
128 /* ??? We are not interested in loop related info, but the following
129 will create it, ICEing as we didn't init loops with pre-headers.
130 An interfacing issue of find_data_references_in_bb. */
131 loop_optimizer_init (LOOPS_NORMAL);
132 scev_initialize ();
133 todo = tree_ssa_phiopt_worker (true, false);
134 scev_finalize ();
135 loop_optimizer_finalize ();
136 return todo;
139 /* Return the singleton PHI in the SEQ of PHIs for edges E0 and E1. */
141 static gimple
142 single_non_singleton_phi_for_edges (gimple_seq seq, edge e0, edge e1)
144 gimple_stmt_iterator i;
145 gimple phi = NULL;
146 if (gimple_seq_singleton_p (seq))
147 return gsi_stmt (gsi_start (seq));
148 for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
150 gimple p = gsi_stmt (i);
151 /* If the PHI arguments are equal then we can skip this PHI. */
152 if (operand_equal_for_phi_arg_p (gimple_phi_arg_def (p, e0->dest_idx),
153 gimple_phi_arg_def (p, e1->dest_idx)))
154 continue;
156 /* If we already have a PHI that has the two edge arguments are
157 different, then return it is not a singleton for these PHIs. */
158 if (phi)
159 return NULL;
161 phi = p;
163 return phi;
166 /* The core routine of conditional store replacement and normal
167 phi optimizations. Both share much of the infrastructure in how
168 to match applicable basic block patterns. DO_STORE_ELIM is true
169 when we want to do conditional store replacement, false otherwise.
170 DO_HOIST_LOADS is true when we want to hoist adjacent loads out
171 of diamond control flow patterns, false otherwise. */
172 static unsigned int
173 tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads)
175 basic_block bb;
176 basic_block *bb_order;
177 unsigned n, i;
178 bool cfgchanged = false;
179 struct pointer_set_t *nontrap = 0;
181 if (do_store_elim)
182 /* Calculate the set of non-trapping memory accesses. */
183 nontrap = get_non_trapping ();
185 /* The replacement of conditional negation with a non-branching
186 sequence is really only a win when optimizing for speed and we
187 can avoid transformations by gimple if-conversion that result
188 in poor RTL generation.
190 Ideally either gimple if-conversion or the RTL expanders will
191 be improved and the code to emit branchless conditional negation
192 can be removed. */
193 bool replace_conditional_negation = false;
194 if (!do_store_elim)
195 replace_conditional_negation
196 = ((!optimize_size && optimize >= 2)
197 || (((flag_tree_loop_vectorize || cfun->has_force_vectorize_loops)
198 && flag_tree_loop_if_convert != 0)
199 || flag_tree_loop_if_convert == 1
200 || flag_tree_loop_if_convert_stores == 1));
202 /* Search every basic block for COND_EXPR we may be able to optimize.
204 We walk the blocks in order that guarantees that a block with
205 a single predecessor is processed before the predecessor.
206 This ensures that we collapse inner ifs before visiting the
207 outer ones, and also that we do not try to visit a removed
208 block. */
209 bb_order = single_pred_before_succ_order ();
210 n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
212 for (i = 0; i < n; i++)
214 gimple cond_stmt, phi;
215 basic_block bb1, bb2;
216 edge e1, e2;
217 tree arg0, arg1;
219 bb = bb_order[i];
221 cond_stmt = last_stmt (bb);
222 /* Check to see if the last statement is a GIMPLE_COND. */
223 if (!cond_stmt
224 || gimple_code (cond_stmt) != GIMPLE_COND)
225 continue;
227 e1 = EDGE_SUCC (bb, 0);
228 bb1 = e1->dest;
229 e2 = EDGE_SUCC (bb, 1);
230 bb2 = e2->dest;
232 /* We cannot do the optimization on abnormal edges. */
233 if ((e1->flags & EDGE_ABNORMAL) != 0
234 || (e2->flags & EDGE_ABNORMAL) != 0)
235 continue;
237 /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
238 if (EDGE_COUNT (bb1->succs) == 0
239 || bb2 == NULL
240 || EDGE_COUNT (bb2->succs) == 0)
241 continue;
243 /* Find the bb which is the fall through to the other. */
244 if (EDGE_SUCC (bb1, 0)->dest == bb2)
246 else if (EDGE_SUCC (bb2, 0)->dest == bb1)
248 basic_block bb_tmp = bb1;
249 edge e_tmp = e1;
250 bb1 = bb2;
251 bb2 = bb_tmp;
252 e1 = e2;
253 e2 = e_tmp;
255 else if (do_store_elim
256 && EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest)
258 basic_block bb3 = EDGE_SUCC (bb1, 0)->dest;
260 if (!single_succ_p (bb1)
261 || (EDGE_SUCC (bb1, 0)->flags & EDGE_FALLTHRU) == 0
262 || !single_succ_p (bb2)
263 || (EDGE_SUCC (bb2, 0)->flags & EDGE_FALLTHRU) == 0
264 || EDGE_COUNT (bb3->preds) != 2)
265 continue;
266 if (cond_if_else_store_replacement (bb1, bb2, bb3))
267 cfgchanged = true;
268 continue;
270 else if (do_hoist_loads
271 && EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest)
273 basic_block bb3 = EDGE_SUCC (bb1, 0)->dest;
275 if (!FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt)))
276 && single_succ_p (bb1)
277 && single_succ_p (bb2)
278 && single_pred_p (bb1)
279 && single_pred_p (bb2)
280 && EDGE_COUNT (bb->succs) == 2
281 && EDGE_COUNT (bb3->preds) == 2
282 /* If one edge or the other is dominant, a conditional move
283 is likely to perform worse than the well-predicted branch. */
284 && !predictable_edge_p (EDGE_SUCC (bb, 0))
285 && !predictable_edge_p (EDGE_SUCC (bb, 1)))
286 hoist_adjacent_loads (bb, bb1, bb2, bb3);
287 continue;
289 else
290 continue;
292 e1 = EDGE_SUCC (bb1, 0);
294 /* Make sure that bb1 is just a fall through. */
295 if (!single_succ_p (bb1)
296 || (e1->flags & EDGE_FALLTHRU) == 0)
297 continue;
299 /* Also make sure that bb1 only have one predecessor and that it
300 is bb. */
301 if (!single_pred_p (bb1)
302 || single_pred (bb1) != bb)
303 continue;
305 if (do_store_elim)
307 /* bb1 is the middle block, bb2 the join block, bb the split block,
308 e1 the fallthrough edge from bb1 to bb2. We can't do the
309 optimization if the join block has more than two predecessors. */
310 if (EDGE_COUNT (bb2->preds) > 2)
311 continue;
312 if (cond_store_replacement (bb1, bb2, e1, e2, nontrap))
313 cfgchanged = true;
315 else
317 gimple_seq phis = phi_nodes (bb2);
318 gimple_stmt_iterator gsi;
319 bool candorest = true;
321 /* Value replacement can work with more than one PHI
322 so try that first. */
323 for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
325 phi = gsi_stmt (gsi);
326 arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
327 arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
328 if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1) == 2)
330 candorest = false;
331 cfgchanged = true;
332 break;
336 if (!candorest)
337 continue;
339 phi = single_non_singleton_phi_for_edges (phis, e1, e2);
340 if (!phi)
341 continue;
343 arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
344 arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
346 /* Something is wrong if we cannot find the arguments in the PHI
347 node. */
348 gcc_assert (arg0 != NULL && arg1 != NULL);
350 /* Do the replacement of conditional if it can be done. */
351 if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
352 cfgchanged = true;
353 else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
354 cfgchanged = true;
355 else if (replace_conditional_negation
356 && neg_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
357 cfgchanged = true;
358 else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
359 cfgchanged = true;
363 free (bb_order);
365 if (do_store_elim)
366 pointer_set_destroy (nontrap);
367 /* If the CFG has changed, we should cleanup the CFG. */
368 if (cfgchanged && do_store_elim)
370 /* In cond-store replacement we have added some loads on edges
371 and new VOPS (as we moved the store, and created a load). */
372 gsi_commit_edge_inserts ();
373 return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
375 else if (cfgchanged)
376 return TODO_cleanup_cfg;
377 return 0;
380 /* Replace PHI node element whose edge is E in block BB with variable NEW.
381 Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
382 is known to have two edges, one of which must reach BB). */
384 static void
385 replace_phi_edge_with_variable (basic_block cond_block,
386 edge e, gimple phi, tree new_tree)
388 basic_block bb = gimple_bb (phi);
389 basic_block block_to_remove;
390 gimple_stmt_iterator gsi;
392 /* Change the PHI argument to new. */
393 SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);
395 /* Remove the empty basic block. */
396 if (EDGE_SUCC (cond_block, 0)->dest == bb)
398 EDGE_SUCC (cond_block, 0)->flags |= EDGE_FALLTHRU;
399 EDGE_SUCC (cond_block, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
400 EDGE_SUCC (cond_block, 0)->probability = REG_BR_PROB_BASE;
401 EDGE_SUCC (cond_block, 0)->count += EDGE_SUCC (cond_block, 1)->count;
403 block_to_remove = EDGE_SUCC (cond_block, 1)->dest;
405 else
407 EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU;
408 EDGE_SUCC (cond_block, 1)->flags
409 &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
410 EDGE_SUCC (cond_block, 1)->probability = REG_BR_PROB_BASE;
411 EDGE_SUCC (cond_block, 1)->count += EDGE_SUCC (cond_block, 0)->count;
413 block_to_remove = EDGE_SUCC (cond_block, 0)->dest;
415 delete_basic_block (block_to_remove);
417 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
418 gsi = gsi_last_bb (cond_block);
419 gsi_remove (&gsi, true);
421 if (dump_file && (dump_flags & TDF_DETAILS))
422 fprintf (dump_file,
423 "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
424 cond_block->index,
425 bb->index);
428 /* The function conditional_replacement does the main work of doing the
429 conditional replacement. Return true if the replacement is done.
430 Otherwise return false.
431 BB is the basic block where the replacement is going to be done on. ARG0
432 is argument 0 from PHI. Likewise for ARG1. */
434 static bool
435 conditional_replacement (basic_block cond_bb, basic_block middle_bb,
436 edge e0, edge e1, gimple phi,
437 tree arg0, tree arg1)
439 tree result;
440 gimple stmt, new_stmt;
441 tree cond;
442 gimple_stmt_iterator gsi;
443 edge true_edge, false_edge;
444 tree new_var, new_var2;
445 bool neg;
447 /* FIXME: Gimplification of complex type is too hard for now. */
448 /* We aren't prepared to handle vectors either (and it is a question
449 if it would be worthwhile anyway). */
450 if (!(INTEGRAL_TYPE_P (TREE_TYPE (arg0))
451 || POINTER_TYPE_P (TREE_TYPE (arg0)))
452 || !(INTEGRAL_TYPE_P (TREE_TYPE (arg1))
453 || POINTER_TYPE_P (TREE_TYPE (arg1))))
454 return false;
456 /* The PHI arguments have the constants 0 and 1, or 0 and -1, then
457 convert it to the conditional. */
458 if ((integer_zerop (arg0) && integer_onep (arg1))
459 || (integer_zerop (arg1) && integer_onep (arg0)))
460 neg = false;
461 else if ((integer_zerop (arg0) && integer_all_onesp (arg1))
462 || (integer_zerop (arg1) && integer_all_onesp (arg0)))
463 neg = true;
464 else
465 return false;
467 if (!empty_block_p (middle_bb))
468 return false;
470 /* At this point we know we have a GIMPLE_COND with two successors.
471 One successor is BB, the other successor is an empty block which
472 falls through into BB.
474 There is a single PHI node at the join point (BB) and its arguments
475 are constants (0, 1) or (0, -1).
477 So, given the condition COND, and the two PHI arguments, we can
478 rewrite this PHI into non-branching code:
480 dest = (COND) or dest = COND'
482 We use the condition as-is if the argument associated with the
483 true edge has the value one or the argument associated with the
484 false edge as the value zero. Note that those conditions are not
485 the same since only one of the outgoing edges from the GIMPLE_COND
486 will directly reach BB and thus be associated with an argument. */
488 stmt = last_stmt (cond_bb);
489 result = PHI_RESULT (phi);
491 /* To handle special cases like floating point comparison, it is easier and
492 less error-prone to build a tree and gimplify it on the fly though it is
493 less efficient. */
494 cond = fold_build2_loc (gimple_location (stmt),
495 gimple_cond_code (stmt), boolean_type_node,
496 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
498 /* We need to know which is the true edge and which is the false
499 edge so that we know when to invert the condition below. */
500 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
501 if ((e0 == true_edge && integer_zerop (arg0))
502 || (e0 == false_edge && !integer_zerop (arg0))
503 || (e1 == true_edge && integer_zerop (arg1))
504 || (e1 == false_edge && !integer_zerop (arg1)))
505 cond = fold_build1_loc (gimple_location (stmt),
506 TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
508 if (neg)
510 cond = fold_convert_loc (gimple_location (stmt),
511 TREE_TYPE (result), cond);
512 cond = fold_build1_loc (gimple_location (stmt),
513 NEGATE_EXPR, TREE_TYPE (cond), cond);
516 /* Insert our new statements at the end of conditional block before the
517 COND_STMT. */
518 gsi = gsi_for_stmt (stmt);
519 new_var = force_gimple_operand_gsi (&gsi, cond, true, NULL, true,
520 GSI_SAME_STMT);
522 if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (new_var)))
524 source_location locus_0, locus_1;
526 new_var2 = make_ssa_name (TREE_TYPE (result), NULL);
527 new_stmt = gimple_build_assign_with_ops (CONVERT_EXPR, new_var2,
528 new_var, NULL);
529 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
530 new_var = new_var2;
532 /* Set the locus to the first argument, unless is doesn't have one. */
533 locus_0 = gimple_phi_arg_location (phi, 0);
534 locus_1 = gimple_phi_arg_location (phi, 1);
535 if (locus_0 == UNKNOWN_LOCATION)
536 locus_0 = locus_1;
537 gimple_set_location (new_stmt, locus_0);
540 replace_phi_edge_with_variable (cond_bb, e1, phi, new_var);
542 /* Note that we optimized this PHI. */
543 return true;
546 /* Update *ARG which is defined in STMT so that it contains the
547 computed value if that seems profitable. Return true if the
548 statement is made dead by that rewriting. */
550 static bool
551 jump_function_from_stmt (tree *arg, gimple stmt)
553 enum tree_code code = gimple_assign_rhs_code (stmt);
554 if (code == ADDR_EXPR)
556 /* For arg = &p->i transform it to p, if possible. */
557 tree rhs1 = gimple_assign_rhs1 (stmt);
558 HOST_WIDE_INT offset;
559 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs1, 0),
560 &offset);
561 if (tem
562 && TREE_CODE (tem) == MEM_REF
563 && (mem_ref_offset (tem) + offset) == 0)
565 *arg = TREE_OPERAND (tem, 0);
566 return true;
569 /* TODO: Much like IPA-CP jump-functions we want to handle constant
570 additions symbolically here, and we'd need to update the comparison
571 code that compares the arg + cst tuples in our caller. For now the
572 code above exactly handles the VEC_BASE pattern from vec.h. */
573 return false;
576 /* RHS is a source argument in a BIT_AND_EXPR which feeds a conditional
577 of the form SSA_NAME NE 0.
579 If RHS is fed by a simple EQ_EXPR comparison of two values, see if
580 the two input values of the EQ_EXPR match arg0 and arg1.
582 If so update *code and return TRUE. Otherwise return FALSE. */
584 static bool
585 rhs_is_fed_for_value_replacement (const_tree arg0, const_tree arg1,
586 enum tree_code *code, const_tree rhs)
588 /* Obviously if RHS is not an SSA_NAME, we can't look at the defining
589 statement. */
590 if (TREE_CODE (rhs) == SSA_NAME)
592 gimple def1 = SSA_NAME_DEF_STMT (rhs);
594 /* Verify the defining statement has an EQ_EXPR on the RHS. */
595 if (is_gimple_assign (def1) && gimple_assign_rhs_code (def1) == EQ_EXPR)
597 /* Finally verify the source operands of the EQ_EXPR are equal
598 to arg0 and arg1. */
599 tree op0 = gimple_assign_rhs1 (def1);
600 tree op1 = gimple_assign_rhs2 (def1);
601 if ((operand_equal_for_phi_arg_p (arg0, op0)
602 && operand_equal_for_phi_arg_p (arg1, op1))
603 || (operand_equal_for_phi_arg_p (arg0, op1)
604 && operand_equal_for_phi_arg_p (arg1, op0)))
606 /* We will perform the optimization. */
607 *code = gimple_assign_rhs_code (def1);
608 return true;
612 return false;
615 /* Return TRUE if arg0/arg1 are equal to the rhs/lhs or lhs/rhs of COND.
617 Also return TRUE if arg0/arg1 are equal to the source arguments of a
618 an EQ comparison feeding a BIT_AND_EXPR which feeds COND.
620 Return FALSE otherwise. */
622 static bool
623 operand_equal_for_value_replacement (const_tree arg0, const_tree arg1,
624 enum tree_code *code, gimple cond)
626 gimple def;
627 tree lhs = gimple_cond_lhs (cond);
628 tree rhs = gimple_cond_rhs (cond);
630 if ((operand_equal_for_phi_arg_p (arg0, lhs)
631 && operand_equal_for_phi_arg_p (arg1, rhs))
632 || (operand_equal_for_phi_arg_p (arg1, lhs)
633 && operand_equal_for_phi_arg_p (arg0, rhs)))
634 return true;
636 /* Now handle more complex case where we have an EQ comparison
637 which feeds a BIT_AND_EXPR which feeds COND.
639 First verify that COND is of the form SSA_NAME NE 0. */
640 if (*code != NE_EXPR || !integer_zerop (rhs)
641 || TREE_CODE (lhs) != SSA_NAME)
642 return false;
644 /* Now ensure that SSA_NAME is set by a BIT_AND_EXPR. */
645 def = SSA_NAME_DEF_STMT (lhs);
646 if (!is_gimple_assign (def) || gimple_assign_rhs_code (def) != BIT_AND_EXPR)
647 return false;
649 /* Now verify arg0/arg1 correspond to the source arguments of an
650 EQ comparison feeding the BIT_AND_EXPR. */
652 tree tmp = gimple_assign_rhs1 (def);
653 if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp))
654 return true;
656 tmp = gimple_assign_rhs2 (def);
657 if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp))
658 return true;
660 return false;
663 /* Returns true if ARG is a neutral element for operation CODE
664 on the RIGHT side. */
666 static bool
667 neutral_element_p (tree_code code, tree arg, bool right)
669 switch (code)
671 case PLUS_EXPR:
672 case BIT_IOR_EXPR:
673 case BIT_XOR_EXPR:
674 return integer_zerop (arg);
676 case LROTATE_EXPR:
677 case RROTATE_EXPR:
678 case LSHIFT_EXPR:
679 case RSHIFT_EXPR:
680 case MINUS_EXPR:
681 case POINTER_PLUS_EXPR:
682 return right && integer_zerop (arg);
684 case MULT_EXPR:
685 return integer_onep (arg);
687 case TRUNC_DIV_EXPR:
688 case CEIL_DIV_EXPR:
689 case FLOOR_DIV_EXPR:
690 case ROUND_DIV_EXPR:
691 case EXACT_DIV_EXPR:
692 return right && integer_onep (arg);
694 case BIT_AND_EXPR:
695 return integer_all_onesp (arg);
697 default:
698 return false;
702 /* Returns true if ARG is an absorbing element for operation CODE. */
704 static bool
705 absorbing_element_p (tree_code code, tree arg)
707 switch (code)
709 case BIT_IOR_EXPR:
710 return integer_all_onesp (arg);
712 case MULT_EXPR:
713 case BIT_AND_EXPR:
714 return integer_zerop (arg);
716 default:
717 return false;
721 /* The function value_replacement does the main work of doing the value
722 replacement. Return non-zero if the replacement is done. Otherwise return
723 0. If we remove the middle basic block, return 2.
724 BB is the basic block where the replacement is going to be done on. ARG0
725 is argument 0 from the PHI. Likewise for ARG1. */
727 static int
728 value_replacement (basic_block cond_bb, basic_block middle_bb,
729 edge e0, edge e1, gimple phi,
730 tree arg0, tree arg1)
732 gimple_stmt_iterator gsi;
733 gimple cond;
734 edge true_edge, false_edge;
735 enum tree_code code;
736 bool emtpy_or_with_defined_p = true;
738 /* If the type says honor signed zeros we cannot do this
739 optimization. */
740 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
741 return 0;
743 /* If there is a statement in MIDDLE_BB that defines one of the PHI
744 arguments, then adjust arg0 or arg1. */
745 gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
746 while (!gsi_end_p (gsi))
748 gimple stmt = gsi_stmt (gsi);
749 tree lhs;
750 gsi_next_nondebug (&gsi);
751 if (!is_gimple_assign (stmt))
753 emtpy_or_with_defined_p = false;
754 continue;
756 /* Now try to adjust arg0 or arg1 according to the computation
757 in the statement. */
758 lhs = gimple_assign_lhs (stmt);
759 if (!(lhs == arg0
760 && jump_function_from_stmt (&arg0, stmt))
761 || (lhs == arg1
762 && jump_function_from_stmt (&arg1, stmt)))
763 emtpy_or_with_defined_p = false;
766 cond = last_stmt (cond_bb);
767 code = gimple_cond_code (cond);
769 /* This transformation is only valid for equality comparisons. */
770 if (code != NE_EXPR && code != EQ_EXPR)
771 return 0;
773 /* We need to know which is the true edge and which is the false
774 edge so that we know if have abs or negative abs. */
775 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
777 /* At this point we know we have a COND_EXPR with two successors.
778 One successor is BB, the other successor is an empty block which
779 falls through into BB.
781 The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
783 There is a single PHI node at the join point (BB) with two arguments.
785 We now need to verify that the two arguments in the PHI node match
786 the two arguments to the equality comparison. */
788 if (operand_equal_for_value_replacement (arg0, arg1, &code, cond))
790 edge e;
791 tree arg;
793 /* For NE_EXPR, we want to build an assignment result = arg where
794 arg is the PHI argument associated with the true edge. For
795 EQ_EXPR we want the PHI argument associated with the false edge. */
796 e = (code == NE_EXPR ? true_edge : false_edge);
798 /* Unfortunately, E may not reach BB (it may instead have gone to
799 OTHER_BLOCK). If that is the case, then we want the single outgoing
800 edge from OTHER_BLOCK which reaches BB and represents the desired
801 path from COND_BLOCK. */
802 if (e->dest == middle_bb)
803 e = single_succ_edge (e->dest);
805 /* Now we know the incoming edge to BB that has the argument for the
806 RHS of our new assignment statement. */
807 if (e0 == e)
808 arg = arg0;
809 else
810 arg = arg1;
812 /* If the middle basic block was empty or is defining the
813 PHI arguments and this is a single phi where the args are different
814 for the edges e0 and e1 then we can remove the middle basic block. */
815 if (emtpy_or_with_defined_p
816 && single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)),
817 e0, e1))
819 replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
820 /* Note that we optimized this PHI. */
821 return 2;
823 else
825 /* Replace the PHI arguments with arg. */
826 SET_PHI_ARG_DEF (phi, e0->dest_idx, arg);
827 SET_PHI_ARG_DEF (phi, e1->dest_idx, arg);
828 if (dump_file && (dump_flags & TDF_DETAILS))
830 fprintf (dump_file, "PHI ");
831 print_generic_expr (dump_file, gimple_phi_result (phi), 0);
832 fprintf (dump_file, " reduced for COND_EXPR in block %d to ",
833 cond_bb->index);
834 print_generic_expr (dump_file, arg, 0);
835 fprintf (dump_file, ".\n");
837 return 1;
842 /* Now optimize (x != 0) ? x + y : y to just y.
843 The following condition is too restrictive, there can easily be another
844 stmt in middle_bb, for instance a CONVERT_EXPR for the second argument. */
845 gimple assign = last_and_only_stmt (middle_bb);
846 if (!assign || gimple_code (assign) != GIMPLE_ASSIGN
847 || gimple_assign_rhs_class (assign) != GIMPLE_BINARY_RHS
848 || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
849 && !POINTER_TYPE_P (TREE_TYPE (arg0))))
850 return 0;
852 /* Punt if there are (degenerate) PHIs in middle_bb, there should not be. */
853 if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
854 return 0;
856 /* Only transform if it removes the condition. */
857 if (!single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)), e0, e1))
858 return 0;
860 /* Size-wise, this is always profitable. */
861 if (optimize_bb_for_speed_p (cond_bb)
862 /* The special case is useless if it has a low probability. */
863 && profile_status_for_fn (cfun) != PROFILE_ABSENT
864 && EDGE_PRED (middle_bb, 0)->probability < PROB_EVEN
865 /* If assign is cheap, there is no point avoiding it. */
866 && estimate_num_insns (assign, &eni_time_weights)
867 >= 3 * estimate_num_insns (cond, &eni_time_weights))
868 return 0;
870 tree lhs = gimple_assign_lhs (assign);
871 tree rhs1 = gimple_assign_rhs1 (assign);
872 tree rhs2 = gimple_assign_rhs2 (assign);
873 enum tree_code code_def = gimple_assign_rhs_code (assign);
874 tree cond_lhs = gimple_cond_lhs (cond);
875 tree cond_rhs = gimple_cond_rhs (cond);
877 if (((code == NE_EXPR && e1 == false_edge)
878 || (code == EQ_EXPR && e1 == true_edge))
879 && arg0 == lhs
880 && ((arg1 == rhs1
881 && operand_equal_for_phi_arg_p (rhs2, cond_lhs)
882 && neutral_element_p (code_def, cond_rhs, true))
883 || (arg1 == rhs2
884 && operand_equal_for_phi_arg_p (rhs1, cond_lhs)
885 && neutral_element_p (code_def, cond_rhs, false))
886 || (operand_equal_for_phi_arg_p (arg1, cond_rhs)
887 && (operand_equal_for_phi_arg_p (rhs2, cond_lhs)
888 || operand_equal_for_phi_arg_p (rhs1, cond_lhs))
889 && absorbing_element_p (code_def, cond_rhs))))
891 gsi = gsi_for_stmt (cond);
892 gimple_stmt_iterator gsi_from = gsi_for_stmt (assign);
893 gsi_move_before (&gsi_from, &gsi);
894 replace_phi_edge_with_variable (cond_bb, e1, phi, lhs);
895 return 2;
898 return 0;
901 /* The function minmax_replacement does the main work of doing the minmax
902 replacement. Return true if the replacement is done. Otherwise return
903 false.
904 BB is the basic block where the replacement is going to be done on. ARG0
905 is argument 0 from the PHI. Likewise for ARG1. */
907 static bool
908 minmax_replacement (basic_block cond_bb, basic_block middle_bb,
909 edge e0, edge e1, gimple phi,
910 tree arg0, tree arg1)
912 tree result, type;
913 gimple cond, new_stmt;
914 edge true_edge, false_edge;
915 enum tree_code cmp, minmax, ass_code;
916 tree smaller, larger, arg_true, arg_false;
917 gimple_stmt_iterator gsi, gsi_from;
919 type = TREE_TYPE (PHI_RESULT (phi));
921 /* The optimization may be unsafe due to NaNs. */
922 if (HONOR_NANS (TYPE_MODE (type)))
923 return false;
925 cond = last_stmt (cond_bb);
926 cmp = gimple_cond_code (cond);
928 /* This transformation is only valid for order comparisons. Record which
929 operand is smaller/larger if the result of the comparison is true. */
930 if (cmp == LT_EXPR || cmp == LE_EXPR)
932 smaller = gimple_cond_lhs (cond);
933 larger = gimple_cond_rhs (cond);
935 else if (cmp == GT_EXPR || cmp == GE_EXPR)
937 smaller = gimple_cond_rhs (cond);
938 larger = gimple_cond_lhs (cond);
940 else
941 return false;
943 /* We need to know which is the true edge and which is the false
944 edge so that we know if have abs or negative abs. */
945 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
947 /* Forward the edges over the middle basic block. */
948 if (true_edge->dest == middle_bb)
949 true_edge = EDGE_SUCC (true_edge->dest, 0);
950 if (false_edge->dest == middle_bb)
951 false_edge = EDGE_SUCC (false_edge->dest, 0);
953 if (true_edge == e0)
955 gcc_assert (false_edge == e1);
956 arg_true = arg0;
957 arg_false = arg1;
959 else
961 gcc_assert (false_edge == e0);
962 gcc_assert (true_edge == e1);
963 arg_true = arg1;
964 arg_false = arg0;
967 if (empty_block_p (middle_bb))
969 if (operand_equal_for_phi_arg_p (arg_true, smaller)
970 && operand_equal_for_phi_arg_p (arg_false, larger))
972 /* Case
974 if (smaller < larger)
975 rslt = smaller;
976 else
977 rslt = larger; */
978 minmax = MIN_EXPR;
980 else if (operand_equal_for_phi_arg_p (arg_false, smaller)
981 && operand_equal_for_phi_arg_p (arg_true, larger))
982 minmax = MAX_EXPR;
983 else
984 return false;
986 else
988 /* Recognize the following case, assuming d <= u:
990 if (a <= u)
991 b = MAX (a, d);
992 x = PHI <b, u>
994 This is equivalent to
996 b = MAX (a, d);
997 x = MIN (b, u); */
999 gimple assign = last_and_only_stmt (middle_bb);
1000 tree lhs, op0, op1, bound;
1002 if (!assign
1003 || gimple_code (assign) != GIMPLE_ASSIGN)
1004 return false;
1006 lhs = gimple_assign_lhs (assign);
1007 ass_code = gimple_assign_rhs_code (assign);
1008 if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
1009 return false;
1010 op0 = gimple_assign_rhs1 (assign);
1011 op1 = gimple_assign_rhs2 (assign);
1013 if (true_edge->src == middle_bb)
1015 /* We got here if the condition is true, i.e., SMALLER < LARGER. */
1016 if (!operand_equal_for_phi_arg_p (lhs, arg_true))
1017 return false;
1019 if (operand_equal_for_phi_arg_p (arg_false, larger))
1021 /* Case
1023 if (smaller < larger)
1025 r' = MAX_EXPR (smaller, bound)
1027 r = PHI <r', larger> --> to be turned to MIN_EXPR. */
1028 if (ass_code != MAX_EXPR)
1029 return false;
1031 minmax = MIN_EXPR;
1032 if (operand_equal_for_phi_arg_p (op0, smaller))
1033 bound = op1;
1034 else if (operand_equal_for_phi_arg_p (op1, smaller))
1035 bound = op0;
1036 else
1037 return false;
1039 /* We need BOUND <= LARGER. */
1040 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
1041 bound, larger)))
1042 return false;
1044 else if (operand_equal_for_phi_arg_p (arg_false, smaller))
1046 /* Case
1048 if (smaller < larger)
1050 r' = MIN_EXPR (larger, bound)
1052 r = PHI <r', smaller> --> to be turned to MAX_EXPR. */
1053 if (ass_code != MIN_EXPR)
1054 return false;
1056 minmax = MAX_EXPR;
1057 if (operand_equal_for_phi_arg_p (op0, larger))
1058 bound = op1;
1059 else if (operand_equal_for_phi_arg_p (op1, larger))
1060 bound = op0;
1061 else
1062 return false;
1064 /* We need BOUND >= SMALLER. */
1065 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
1066 bound, smaller)))
1067 return false;
1069 else
1070 return false;
1072 else
1074 /* We got here if the condition is false, i.e., SMALLER > LARGER. */
1075 if (!operand_equal_for_phi_arg_p (lhs, arg_false))
1076 return false;
1078 if (operand_equal_for_phi_arg_p (arg_true, larger))
1080 /* Case
1082 if (smaller > larger)
1084 r' = MIN_EXPR (smaller, bound)
1086 r = PHI <r', larger> --> to be turned to MAX_EXPR. */
1087 if (ass_code != MIN_EXPR)
1088 return false;
1090 minmax = MAX_EXPR;
1091 if (operand_equal_for_phi_arg_p (op0, smaller))
1092 bound = op1;
1093 else if (operand_equal_for_phi_arg_p (op1, smaller))
1094 bound = op0;
1095 else
1096 return false;
1098 /* We need BOUND >= LARGER. */
1099 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
1100 bound, larger)))
1101 return false;
1103 else if (operand_equal_for_phi_arg_p (arg_true, smaller))
1105 /* Case
1107 if (smaller > larger)
1109 r' = MAX_EXPR (larger, bound)
1111 r = PHI <r', smaller> --> to be turned to MIN_EXPR. */
1112 if (ass_code != MAX_EXPR)
1113 return false;
1115 minmax = MIN_EXPR;
1116 if (operand_equal_for_phi_arg_p (op0, larger))
1117 bound = op1;
1118 else if (operand_equal_for_phi_arg_p (op1, larger))
1119 bound = op0;
1120 else
1121 return false;
1123 /* We need BOUND <= SMALLER. */
1124 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
1125 bound, smaller)))
1126 return false;
1128 else
1129 return false;
1132 /* Move the statement from the middle block. */
1133 gsi = gsi_last_bb (cond_bb);
1134 gsi_from = gsi_last_nondebug_bb (middle_bb);
1135 gsi_move_before (&gsi_from, &gsi);
1138 /* Emit the statement to compute min/max. */
1139 result = duplicate_ssa_name (PHI_RESULT (phi), NULL);
1140 new_stmt = gimple_build_assign_with_ops (minmax, result, arg0, arg1);
1141 gsi = gsi_last_bb (cond_bb);
1142 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
1144 replace_phi_edge_with_variable (cond_bb, e1, phi, result);
1145 return true;
1148 /* The function absolute_replacement does the main work of doing the absolute
1149 replacement. Return true if the replacement is done. Otherwise return
1150 false.
1151 bb is the basic block where the replacement is going to be done on. arg0
1152 is argument 0 from the phi. Likewise for arg1. */
1154 static bool
1155 abs_replacement (basic_block cond_bb, basic_block middle_bb,
1156 edge e0 ATTRIBUTE_UNUSED, edge e1,
1157 gimple phi, tree arg0, tree arg1)
1159 tree result;
1160 gimple new_stmt, cond;
1161 gimple_stmt_iterator gsi;
1162 edge true_edge, false_edge;
1163 gimple assign;
1164 edge e;
1165 tree rhs, lhs;
1166 bool negate;
1167 enum tree_code cond_code;
1169 /* If the type says honor signed zeros we cannot do this
1170 optimization. */
1171 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
1172 return false;
1174 /* OTHER_BLOCK must have only one executable statement which must have the
1175 form arg0 = -arg1 or arg1 = -arg0. */
1177 assign = last_and_only_stmt (middle_bb);
1178 /* If we did not find the proper negation assignment, then we can not
1179 optimize. */
1180 if (assign == NULL)
1181 return false;
1183 /* If we got here, then we have found the only executable statement
1184 in OTHER_BLOCK. If it is anything other than arg = -arg1 or
1185 arg1 = -arg0, then we can not optimize. */
1186 if (gimple_code (assign) != GIMPLE_ASSIGN)
1187 return false;
1189 lhs = gimple_assign_lhs (assign);
1191 if (gimple_assign_rhs_code (assign) != NEGATE_EXPR)
1192 return false;
1194 rhs = gimple_assign_rhs1 (assign);
1196 /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */
1197 if (!(lhs == arg0 && rhs == arg1)
1198 && !(lhs == arg1 && rhs == arg0))
1199 return false;
1201 cond = last_stmt (cond_bb);
1202 result = PHI_RESULT (phi);
1204 /* Only relationals comparing arg[01] against zero are interesting. */
1205 cond_code = gimple_cond_code (cond);
1206 if (cond_code != GT_EXPR && cond_code != GE_EXPR
1207 && cond_code != LT_EXPR && cond_code != LE_EXPR)
1208 return false;
1210 /* Make sure the conditional is arg[01] OP y. */
1211 if (gimple_cond_lhs (cond) != rhs)
1212 return false;
1214 if (FLOAT_TYPE_P (TREE_TYPE (gimple_cond_rhs (cond)))
1215 ? real_zerop (gimple_cond_rhs (cond))
1216 : integer_zerop (gimple_cond_rhs (cond)))
1218 else
1219 return false;
1221 /* We need to know which is the true edge and which is the false
1222 edge so that we know if have abs or negative abs. */
1223 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1225 /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
1226 will need to negate the result. Similarly for LT_EXPR/LE_EXPR if
1227 the false edge goes to OTHER_BLOCK. */
1228 if (cond_code == GT_EXPR || cond_code == GE_EXPR)
1229 e = true_edge;
1230 else
1231 e = false_edge;
1233 if (e->dest == middle_bb)
1234 negate = true;
1235 else
1236 negate = false;
1238 result = duplicate_ssa_name (result, NULL);
1240 if (negate)
1241 lhs = make_ssa_name (TREE_TYPE (result), NULL);
1242 else
1243 lhs = result;
1245 /* Build the modify expression with abs expression. */
1246 new_stmt = gimple_build_assign_with_ops (ABS_EXPR, lhs, rhs, NULL);
1248 gsi = gsi_last_bb (cond_bb);
1249 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
1251 if (negate)
1253 /* Get the right GSI. We want to insert after the recently
1254 added ABS_EXPR statement (which we know is the first statement
1255 in the block. */
1256 new_stmt = gimple_build_assign_with_ops (NEGATE_EXPR, result, lhs, NULL);
1258 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
1261 replace_phi_edge_with_variable (cond_bb, e1, phi, result);
1263 /* Note that we optimized this PHI. */
1264 return true;
1267 /* The function neg_replacement replaces conditional negation with
1268 equivalent straight line code. Returns TRUE if replacement is done,
1269 otherwise returns FALSE.
1271 COND_BB branches around negation occuring in MIDDLE_BB.
1273 E0 and E1 are edges out of COND_BB. E0 reaches MIDDLE_BB and
1274 E1 reaches the other successor which should contain PHI with
1275 arguments ARG0 and ARG1.
1277 Assuming negation is to occur when the condition is true,
1278 then the non-branching sequence is:
1280 result = (rhs ^ -cond) + cond
1282 Inverting the condition or its result gives us negation
1283 when the original condition is false. */
1285 static bool
1286 neg_replacement (basic_block cond_bb, basic_block middle_bb,
1287 edge e0 ATTRIBUTE_UNUSED, edge e1,
1288 gimple phi, tree arg0, tree arg1)
1290 gimple new_stmt, cond;
1291 gimple_stmt_iterator gsi;
1292 gimple assign;
1293 edge true_edge, false_edge;
1294 tree rhs, lhs;
1295 enum tree_code cond_code;
1296 bool invert = false;
1298 /* This transformation performs logical operations on the
1299 incoming arguments. So force them to be integral types. */
1300 if (!INTEGRAL_TYPE_P (TREE_TYPE (arg0)))
1301 return false;
1303 /* OTHER_BLOCK must have only one executable statement which must have the
1304 form arg0 = -arg1 or arg1 = -arg0. */
1306 assign = last_and_only_stmt (middle_bb);
1307 /* If we did not find the proper negation assignment, then we can not
1308 optimize. */
1309 if (assign == NULL)
1310 return false;
1312 /* If we got here, then we have found the only executable statement
1313 in OTHER_BLOCK. If it is anything other than arg0 = -arg1 or
1314 arg1 = -arg0, then we can not optimize. */
1315 if (gimple_code (assign) != GIMPLE_ASSIGN)
1316 return false;
1318 lhs = gimple_assign_lhs (assign);
1320 if (gimple_assign_rhs_code (assign) != NEGATE_EXPR)
1321 return false;
1323 rhs = gimple_assign_rhs1 (assign);
1325 /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */
1326 if (!(lhs == arg0 && rhs == arg1)
1327 && !(lhs == arg1 && rhs == arg0))
1328 return false;
1330 /* The basic sequence assumes we negate when the condition is true.
1331 If we need the opposite, then we will either need to invert the
1332 condition or its result. */
1333 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1334 invert = false_edge->dest == middle_bb;
1336 /* Unlike abs_replacement, we can handle arbitrary conditionals here. */
1337 cond = last_stmt (cond_bb);
1338 cond_code = gimple_cond_code (cond);
1340 /* If inversion is needed, first try to invert the test since
1341 that's cheapest. */
1342 if (invert)
1344 bool honor_nans
1345 = HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (cond))));
1346 enum tree_code new_code = invert_tree_comparison (cond_code, honor_nans);
1348 /* If invert_tree_comparison was successful, then use its return
1349 value as the new code and note that inversion is no longer
1350 needed. */
1351 if (new_code != ERROR_MARK)
1353 cond_code = new_code;
1354 invert = false;
1358 tree cond_val = make_ssa_name (boolean_type_node, NULL);
1359 new_stmt = gimple_build_assign_with_ops (cond_code, cond_val,
1360 gimple_cond_lhs (cond),
1361 gimple_cond_rhs (cond));
1362 gsi = gsi_last_bb (cond_bb);
1363 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
1365 /* If we still need inversion, then invert the result of the
1366 condition. */
1367 if (invert)
1369 tree tmp = make_ssa_name (boolean_type_node, NULL);
1370 new_stmt = gimple_build_assign_with_ops (BIT_XOR_EXPR, tmp,
1371 cond_val, boolean_true_node);
1372 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
1373 cond_val = tmp;
1376 /* Get the condition in the right type so that we can perform
1377 logical and arithmetic operations on it. */
1378 tree cond_val_converted = make_ssa_name (TREE_TYPE (rhs), NULL);
1379 new_stmt = gimple_build_assign_with_ops (NOP_EXPR, cond_val_converted,
1380 cond_val, NULL_TREE);
1381 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
1383 tree neg_cond_val_converted = make_ssa_name (TREE_TYPE (rhs), NULL);
1384 new_stmt = gimple_build_assign_with_ops (NEGATE_EXPR, neg_cond_val_converted,
1385 cond_val_converted, NULL_TREE);
1386 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
1388 tree tmp = make_ssa_name (TREE_TYPE (rhs), NULL);
1389 new_stmt = gimple_build_assign_with_ops (BIT_XOR_EXPR, tmp,
1390 rhs, neg_cond_val_converted);
1391 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
1393 tree new_lhs = make_ssa_name (TREE_TYPE (rhs), NULL);
1394 new_stmt = gimple_build_assign_with_ops (PLUS_EXPR, new_lhs,
1395 tmp, cond_val_converted);
1396 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
1398 replace_phi_edge_with_variable (cond_bb, e1, phi, new_lhs);
1400 /* Note that we optimized this PHI. */
1401 return true;
1404 /* Auxiliary functions to determine the set of memory accesses which
1405 can't trap because they are preceded by accesses to the same memory
1406 portion. We do that for MEM_REFs, so we only need to track
1407 the SSA_NAME of the pointer indirectly referenced. The algorithm
1408 simply is a walk over all instructions in dominator order. When
1409 we see an MEM_REF we determine if we've already seen a same
1410 ref anywhere up to the root of the dominator tree. If we do the
1411 current access can't trap. If we don't see any dominating access
1412 the current access might trap, but might also make later accesses
1413 non-trapping, so we remember it. We need to be careful with loads
1414 or stores, for instance a load might not trap, while a store would,
1415 so if we see a dominating read access this doesn't mean that a later
1416 write access would not trap. Hence we also need to differentiate the
1417 type of access(es) seen.
1419 ??? We currently are very conservative and assume that a load might
1420 trap even if a store doesn't (write-only memory). This probably is
1421 overly conservative. */
1423 /* A hash-table of SSA_NAMEs, and in which basic block an MEM_REF
1424 through it was seen, which would constitute a no-trap region for
1425 same accesses. */
1426 struct name_to_bb
1428 unsigned int ssa_name_ver;
1429 unsigned int phase;
1430 bool store;
1431 HOST_WIDE_INT offset, size;
1432 basic_block bb;
1435 /* Hashtable helpers. */
1437 struct ssa_names_hasher : typed_free_remove <name_to_bb>
1439 typedef name_to_bb value_type;
1440 typedef name_to_bb compare_type;
1441 static inline hashval_t hash (const value_type *);
1442 static inline bool equal (const value_type *, const compare_type *);
1445 /* Used for quick clearing of the hash-table when we see calls.
1446 Hash entries with phase < nt_call_phase are invalid. */
1447 static unsigned int nt_call_phase;
1449 /* The hash function. */
1451 inline hashval_t
1452 ssa_names_hasher::hash (const value_type *n)
1454 return n->ssa_name_ver ^ (((hashval_t) n->store) << 31)
1455 ^ (n->offset << 6) ^ (n->size << 3);
1458 /* The equality function of *P1 and *P2. */
1460 inline bool
1461 ssa_names_hasher::equal (const value_type *n1, const compare_type *n2)
1463 return n1->ssa_name_ver == n2->ssa_name_ver
1464 && n1->store == n2->store
1465 && n1->offset == n2->offset
1466 && n1->size == n2->size;
1469 class nontrapping_dom_walker : public dom_walker
1471 public:
1472 nontrapping_dom_walker (cdi_direction direction, pointer_set_t *ps)
1473 : dom_walker (direction), m_nontrapping (ps), m_seen_ssa_names (128) {}
1475 virtual void before_dom_children (basic_block);
1476 virtual void after_dom_children (basic_block);
1478 private:
1480 /* We see the expression EXP in basic block BB. If it's an interesting
1481 expression (an MEM_REF through an SSA_NAME) possibly insert the
1482 expression into the set NONTRAP or the hash table of seen expressions.
1483 STORE is true if this expression is on the LHS, otherwise it's on
1484 the RHS. */
1485 void add_or_mark_expr (basic_block, tree, bool);
1487 pointer_set_t *m_nontrapping;
1489 /* The hash table for remembering what we've seen. */
1490 hash_table<ssa_names_hasher> m_seen_ssa_names;
1493 /* Called by walk_dominator_tree, when entering the block BB. */
1494 void
1495 nontrapping_dom_walker::before_dom_children (basic_block bb)
1497 edge e;
1498 edge_iterator ei;
1499 gimple_stmt_iterator gsi;
1501 /* If we haven't seen all our predecessors, clear the hash-table. */
1502 FOR_EACH_EDGE (e, ei, bb->preds)
1503 if ((((size_t)e->src->aux) & 2) == 0)
1505 nt_call_phase++;
1506 break;
1509 /* Mark this BB as being on the path to dominator root and as visited. */
1510 bb->aux = (void*)(1 | 2);
1512 /* And walk the statements in order. */
1513 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1515 gimple stmt = gsi_stmt (gsi);
1517 if (is_gimple_call (stmt) && !nonfreeing_call_p (stmt))
1518 nt_call_phase++;
1519 else if (gimple_assign_single_p (stmt) && !gimple_has_volatile_ops (stmt))
1521 add_or_mark_expr (bb, gimple_assign_lhs (stmt), true);
1522 add_or_mark_expr (bb, gimple_assign_rhs1 (stmt), false);
1527 /* Called by walk_dominator_tree, when basic block BB is exited. */
1528 void
1529 nontrapping_dom_walker::after_dom_children (basic_block bb)
1531 /* This BB isn't on the path to dominator root anymore. */
1532 bb->aux = (void*)2;
1535 /* We see the expression EXP in basic block BB. If it's an interesting
1536 expression (an MEM_REF through an SSA_NAME) possibly insert the
1537 expression into the set NONTRAP or the hash table of seen expressions.
1538 STORE is true if this expression is on the LHS, otherwise it's on
1539 the RHS. */
1540 void
1541 nontrapping_dom_walker::add_or_mark_expr (basic_block bb, tree exp, bool store)
1543 HOST_WIDE_INT size;
1545 if (TREE_CODE (exp) == MEM_REF
1546 && TREE_CODE (TREE_OPERAND (exp, 0)) == SSA_NAME
1547 && tree_fits_shwi_p (TREE_OPERAND (exp, 1))
1548 && (size = int_size_in_bytes (TREE_TYPE (exp))) > 0)
1550 tree name = TREE_OPERAND (exp, 0);
1551 struct name_to_bb map;
1552 name_to_bb **slot;
1553 struct name_to_bb *n2bb;
1554 basic_block found_bb = 0;
1556 /* Try to find the last seen MEM_REF through the same
1557 SSA_NAME, which can trap. */
1558 map.ssa_name_ver = SSA_NAME_VERSION (name);
1559 map.phase = 0;
1560 map.bb = 0;
1561 map.store = store;
1562 map.offset = tree_to_shwi (TREE_OPERAND (exp, 1));
1563 map.size = size;
1565 slot = m_seen_ssa_names.find_slot (&map, INSERT);
1566 n2bb = *slot;
1567 if (n2bb && n2bb->phase >= nt_call_phase)
1568 found_bb = n2bb->bb;
1570 /* If we've found a trapping MEM_REF, _and_ it dominates EXP
1571 (it's in a basic block on the path from us to the dominator root)
1572 then we can't trap. */
1573 if (found_bb && (((size_t)found_bb->aux) & 1) == 1)
1575 pointer_set_insert (m_nontrapping, exp);
1577 else
1579 /* EXP might trap, so insert it into the hash table. */
1580 if (n2bb)
1582 n2bb->phase = nt_call_phase;
1583 n2bb->bb = bb;
1585 else
1587 n2bb = XNEW (struct name_to_bb);
1588 n2bb->ssa_name_ver = SSA_NAME_VERSION (name);
1589 n2bb->phase = nt_call_phase;
1590 n2bb->bb = bb;
1591 n2bb->store = store;
1592 n2bb->offset = map.offset;
1593 n2bb->size = size;
1594 *slot = n2bb;
1600 /* This is the entry point of gathering non trapping memory accesses.
1601 It will do a dominator walk over the whole function, and it will
1602 make use of the bb->aux pointers. It returns a set of trees
1603 (the MEM_REFs itself) which can't trap. */
1604 static struct pointer_set_t *
1605 get_non_trapping (void)
1607 nt_call_phase = 0;
1608 pointer_set_t *nontrap = pointer_set_create ();
1609 /* We're going to do a dominator walk, so ensure that we have
1610 dominance information. */
1611 calculate_dominance_info (CDI_DOMINATORS);
1613 nontrapping_dom_walker (CDI_DOMINATORS, nontrap)
1614 .walk (cfun->cfg->x_entry_block_ptr);
1616 clear_aux_for_blocks ();
1617 return nontrap;
1620 /* Do the main work of conditional store replacement. We already know
1621 that the recognized pattern looks like so:
1623 split:
1624 if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
1625 MIDDLE_BB:
1626 something
1627 fallthrough (edge E0)
1628 JOIN_BB:
1629 some more
1631 We check that MIDDLE_BB contains only one store, that that store
1632 doesn't trap (not via NOTRAP, but via checking if an access to the same
1633 memory location dominates us) and that the store has a "simple" RHS. */
1635 static bool
1636 cond_store_replacement (basic_block middle_bb, basic_block join_bb,
1637 edge e0, edge e1, struct pointer_set_t *nontrap)
1639 gimple assign = last_and_only_stmt (middle_bb);
1640 tree lhs, rhs, name, name2;
1641 gimple newphi, new_stmt;
1642 gimple_stmt_iterator gsi;
1643 source_location locus;
1645 /* Check if middle_bb contains of only one store. */
1646 if (!assign
1647 || !gimple_assign_single_p (assign)
1648 || gimple_has_volatile_ops (assign))
1649 return false;
1651 locus = gimple_location (assign);
1652 lhs = gimple_assign_lhs (assign);
1653 rhs = gimple_assign_rhs1 (assign);
1654 if (TREE_CODE (lhs) != MEM_REF
1655 || TREE_CODE (TREE_OPERAND (lhs, 0)) != SSA_NAME
1656 || !is_gimple_reg_type (TREE_TYPE (lhs)))
1657 return false;
1659 /* Prove that we can move the store down. We could also check
1660 TREE_THIS_NOTRAP here, but in that case we also could move stores,
1661 whose value is not available readily, which we want to avoid. */
1662 if (!pointer_set_contains (nontrap, lhs))
1663 return false;
1665 /* Now we've checked the constraints, so do the transformation:
1666 1) Remove the single store. */
1667 gsi = gsi_for_stmt (assign);
1668 unlink_stmt_vdef (assign);
1669 gsi_remove (&gsi, true);
1670 release_defs (assign);
1672 /* 2) Insert a load from the memory of the store to the temporary
1673 on the edge which did not contain the store. */
1674 lhs = unshare_expr (lhs);
1675 name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
1676 new_stmt = gimple_build_assign (name, lhs);
1677 gimple_set_location (new_stmt, locus);
1678 gsi_insert_on_edge (e1, new_stmt);
1680 /* 3) Create a PHI node at the join block, with one argument
1681 holding the old RHS, and the other holding the temporary
1682 where we stored the old memory contents. */
1683 name2 = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
1684 newphi = create_phi_node (name2, join_bb);
1685 add_phi_arg (newphi, rhs, e0, locus);
1686 add_phi_arg (newphi, name, e1, locus);
1688 lhs = unshare_expr (lhs);
1689 new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
1691 /* 4) Insert that PHI node. */
1692 gsi = gsi_after_labels (join_bb);
1693 if (gsi_end_p (gsi))
1695 gsi = gsi_last_bb (join_bb);
1696 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
1698 else
1699 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
1701 return true;
1704 /* Do the main work of conditional store replacement. */
1706 static bool
1707 cond_if_else_store_replacement_1 (basic_block then_bb, basic_block else_bb,
1708 basic_block join_bb, gimple then_assign,
1709 gimple else_assign)
1711 tree lhs_base, lhs, then_rhs, else_rhs, name;
1712 source_location then_locus, else_locus;
1713 gimple_stmt_iterator gsi;
1714 gimple newphi, new_stmt;
1716 if (then_assign == NULL
1717 || !gimple_assign_single_p (then_assign)
1718 || gimple_clobber_p (then_assign)
1719 || gimple_has_volatile_ops (then_assign)
1720 || else_assign == NULL
1721 || !gimple_assign_single_p (else_assign)
1722 || gimple_clobber_p (else_assign)
1723 || gimple_has_volatile_ops (else_assign))
1724 return false;
1726 lhs = gimple_assign_lhs (then_assign);
1727 if (!is_gimple_reg_type (TREE_TYPE (lhs))
1728 || !operand_equal_p (lhs, gimple_assign_lhs (else_assign), 0))
1729 return false;
1731 lhs_base = get_base_address (lhs);
1732 if (lhs_base == NULL_TREE
1733 || (!DECL_P (lhs_base) && TREE_CODE (lhs_base) != MEM_REF))
1734 return false;
1736 then_rhs = gimple_assign_rhs1 (then_assign);
1737 else_rhs = gimple_assign_rhs1 (else_assign);
1738 then_locus = gimple_location (then_assign);
1739 else_locus = gimple_location (else_assign);
1741 /* Now we've checked the constraints, so do the transformation:
1742 1) Remove the stores. */
1743 gsi = gsi_for_stmt (then_assign);
1744 unlink_stmt_vdef (then_assign);
1745 gsi_remove (&gsi, true);
1746 release_defs (then_assign);
1748 gsi = gsi_for_stmt (else_assign);
1749 unlink_stmt_vdef (else_assign);
1750 gsi_remove (&gsi, true);
1751 release_defs (else_assign);
1753 /* 2) Create a PHI node at the join block, with one argument
1754 holding the old RHS, and the other holding the temporary
1755 where we stored the old memory contents. */
1756 name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
1757 newphi = create_phi_node (name, join_bb);
1758 add_phi_arg (newphi, then_rhs, EDGE_SUCC (then_bb, 0), then_locus);
1759 add_phi_arg (newphi, else_rhs, EDGE_SUCC (else_bb, 0), else_locus);
1761 new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
1763 /* 3) Insert that PHI node. */
1764 gsi = gsi_after_labels (join_bb);
1765 if (gsi_end_p (gsi))
1767 gsi = gsi_last_bb (join_bb);
1768 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
1770 else
1771 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
1773 return true;
1776 /* Conditional store replacement. We already know
1777 that the recognized pattern looks like so:
1779 split:
1780 if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
1781 THEN_BB:
1783 X = Y;
1785 goto JOIN_BB;
1786 ELSE_BB:
1788 X = Z;
1790 fallthrough (edge E0)
1791 JOIN_BB:
1792 some more
1794 We check that it is safe to sink the store to JOIN_BB by verifying that
1795 there are no read-after-write or write-after-write dependencies in
1796 THEN_BB and ELSE_BB. */
1798 static bool
1799 cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb,
1800 basic_block join_bb)
1802 gimple then_assign = last_and_only_stmt (then_bb);
1803 gimple else_assign = last_and_only_stmt (else_bb);
1804 vec<data_reference_p> then_datarefs, else_datarefs;
1805 vec<ddr_p> then_ddrs, else_ddrs;
1806 gimple then_store, else_store;
1807 bool found, ok = false, res;
1808 struct data_dependence_relation *ddr;
1809 data_reference_p then_dr, else_dr;
1810 int i, j;
1811 tree then_lhs, else_lhs;
1812 basic_block blocks[3];
1814 if (MAX_STORES_TO_SINK == 0)
1815 return false;
1817 /* Handle the case with single statement in THEN_BB and ELSE_BB. */
1818 if (then_assign && else_assign)
1819 return cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
1820 then_assign, else_assign);
1822 /* Find data references. */
1823 then_datarefs.create (1);
1824 else_datarefs.create (1);
1825 if ((find_data_references_in_bb (NULL, then_bb, &then_datarefs)
1826 == chrec_dont_know)
1827 || !then_datarefs.length ()
1828 || (find_data_references_in_bb (NULL, else_bb, &else_datarefs)
1829 == chrec_dont_know)
1830 || !else_datarefs.length ())
1832 free_data_refs (then_datarefs);
1833 free_data_refs (else_datarefs);
1834 return false;
1837 /* Find pairs of stores with equal LHS. */
1838 auto_vec<gimple, 1> then_stores, else_stores;
1839 FOR_EACH_VEC_ELT (then_datarefs, i, then_dr)
1841 if (DR_IS_READ (then_dr))
1842 continue;
1844 then_store = DR_STMT (then_dr);
1845 then_lhs = gimple_get_lhs (then_store);
1846 if (then_lhs == NULL_TREE)
1847 continue;
1848 found = false;
1850 FOR_EACH_VEC_ELT (else_datarefs, j, else_dr)
1852 if (DR_IS_READ (else_dr))
1853 continue;
1855 else_store = DR_STMT (else_dr);
1856 else_lhs = gimple_get_lhs (else_store);
1857 if (else_lhs == NULL_TREE)
1858 continue;
1860 if (operand_equal_p (then_lhs, else_lhs, 0))
1862 found = true;
1863 break;
1867 if (!found)
1868 continue;
1870 then_stores.safe_push (then_store);
1871 else_stores.safe_push (else_store);
1874 /* No pairs of stores found. */
1875 if (!then_stores.length ()
1876 || then_stores.length () > (unsigned) MAX_STORES_TO_SINK)
1878 free_data_refs (then_datarefs);
1879 free_data_refs (else_datarefs);
1880 return false;
1883 /* Compute and check data dependencies in both basic blocks. */
1884 then_ddrs.create (1);
1885 else_ddrs.create (1);
1886 if (!compute_all_dependences (then_datarefs, &then_ddrs,
1887 vNULL, false)
1888 || !compute_all_dependences (else_datarefs, &else_ddrs,
1889 vNULL, false))
1891 free_dependence_relations (then_ddrs);
1892 free_dependence_relations (else_ddrs);
1893 free_data_refs (then_datarefs);
1894 free_data_refs (else_datarefs);
1895 return false;
1897 blocks[0] = then_bb;
1898 blocks[1] = else_bb;
1899 blocks[2] = join_bb;
1900 renumber_gimple_stmt_uids_in_blocks (blocks, 3);
1902 /* Check that there are no read-after-write or write-after-write dependencies
1903 in THEN_BB. */
1904 FOR_EACH_VEC_ELT (then_ddrs, i, ddr)
1906 struct data_reference *dra = DDR_A (ddr);
1907 struct data_reference *drb = DDR_B (ddr);
1909 if (DDR_ARE_DEPENDENT (ddr) != chrec_known
1910 && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
1911 && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
1912 || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
1913 && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
1914 || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
1916 free_dependence_relations (then_ddrs);
1917 free_dependence_relations (else_ddrs);
1918 free_data_refs (then_datarefs);
1919 free_data_refs (else_datarefs);
1920 return false;
1924 /* Check that there are no read-after-write or write-after-write dependencies
1925 in ELSE_BB. */
1926 FOR_EACH_VEC_ELT (else_ddrs, i, ddr)
1928 struct data_reference *dra = DDR_A (ddr);
1929 struct data_reference *drb = DDR_B (ddr);
1931 if (DDR_ARE_DEPENDENT (ddr) != chrec_known
1932 && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
1933 && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
1934 || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
1935 && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
1936 || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
1938 free_dependence_relations (then_ddrs);
1939 free_dependence_relations (else_ddrs);
1940 free_data_refs (then_datarefs);
1941 free_data_refs (else_datarefs);
1942 return false;
1946 /* Sink stores with same LHS. */
1947 FOR_EACH_VEC_ELT (then_stores, i, then_store)
1949 else_store = else_stores[i];
1950 res = cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
1951 then_store, else_store);
1952 ok = ok || res;
1955 free_dependence_relations (then_ddrs);
1956 free_dependence_relations (else_ddrs);
1957 free_data_refs (then_datarefs);
1958 free_data_refs (else_datarefs);
1960 return ok;
1963 /* Return TRUE if STMT has a VUSE whose corresponding VDEF is in BB. */
1965 static bool
1966 local_mem_dependence (gimple stmt, basic_block bb)
1968 tree vuse = gimple_vuse (stmt);
1969 gimple def;
1971 if (!vuse)
1972 return false;
1974 def = SSA_NAME_DEF_STMT (vuse);
1975 return (def && gimple_bb (def) == bb);
1978 /* Given a "diamond" control-flow pattern where BB0 tests a condition,
1979 BB1 and BB2 are "then" and "else" blocks dependent on this test,
1980 and BB3 rejoins control flow following BB1 and BB2, look for
1981 opportunities to hoist loads as follows. If BB3 contains a PHI of
1982 two loads, one each occurring in BB1 and BB2, and the loads are
1983 provably of adjacent fields in the same structure, then move both
1984 loads into BB0. Of course this can only be done if there are no
1985 dependencies preventing such motion.
1987 One of the hoisted loads will always be speculative, so the
1988 transformation is currently conservative:
1990 - The fields must be strictly adjacent.
1991 - The two fields must occupy a single memory block that is
1992 guaranteed to not cross a page boundary.
1994 The last is difficult to prove, as such memory blocks should be
1995 aligned on the minimum of the stack alignment boundary and the
1996 alignment guaranteed by heap allocation interfaces. Thus we rely
1997 on a parameter for the alignment value.
1999 Provided a good value is used for the last case, the first
2000 restriction could possibly be relaxed. */
2002 static void
2003 hoist_adjacent_loads (basic_block bb0, basic_block bb1,
2004 basic_block bb2, basic_block bb3)
2006 int param_align = PARAM_VALUE (PARAM_L1_CACHE_LINE_SIZE);
2007 unsigned param_align_bits = (unsigned) (param_align * BITS_PER_UNIT);
2008 gimple_stmt_iterator gsi;
2010 /* Walk the phis in bb3 looking for an opportunity. We are looking
2011 for phis of two SSA names, one each of which is defined in bb1 and
2012 bb2. */
2013 for (gsi = gsi_start_phis (bb3); !gsi_end_p (gsi); gsi_next (&gsi))
2015 gimple phi_stmt = gsi_stmt (gsi);
2016 gimple def1, def2, defswap;
2017 tree arg1, arg2, ref1, ref2, field1, field2, fieldswap;
2018 tree tree_offset1, tree_offset2, tree_size2, next;
2019 int offset1, offset2, size2;
2020 unsigned align1;
2021 gimple_stmt_iterator gsi2;
2022 basic_block bb_for_def1, bb_for_def2;
2024 if (gimple_phi_num_args (phi_stmt) != 2
2025 || virtual_operand_p (gimple_phi_result (phi_stmt)))
2026 continue;
2028 arg1 = gimple_phi_arg_def (phi_stmt, 0);
2029 arg2 = gimple_phi_arg_def (phi_stmt, 1);
2031 if (TREE_CODE (arg1) != SSA_NAME
2032 || TREE_CODE (arg2) != SSA_NAME
2033 || SSA_NAME_IS_DEFAULT_DEF (arg1)
2034 || SSA_NAME_IS_DEFAULT_DEF (arg2))
2035 continue;
2037 def1 = SSA_NAME_DEF_STMT (arg1);
2038 def2 = SSA_NAME_DEF_STMT (arg2);
2040 if ((gimple_bb (def1) != bb1 || gimple_bb (def2) != bb2)
2041 && (gimple_bb (def2) != bb1 || gimple_bb (def1) != bb2))
2042 continue;
2044 /* Check the mode of the arguments to be sure a conditional move
2045 can be generated for it. */
2046 if (optab_handler (movcc_optab, TYPE_MODE (TREE_TYPE (arg1)))
2047 == CODE_FOR_nothing)
2048 continue;
2050 /* Both statements must be assignments whose RHS is a COMPONENT_REF. */
2051 if (!gimple_assign_single_p (def1)
2052 || !gimple_assign_single_p (def2)
2053 || gimple_has_volatile_ops (def1)
2054 || gimple_has_volatile_ops (def2))
2055 continue;
2057 ref1 = gimple_assign_rhs1 (def1);
2058 ref2 = gimple_assign_rhs1 (def2);
2060 if (TREE_CODE (ref1) != COMPONENT_REF
2061 || TREE_CODE (ref2) != COMPONENT_REF)
2062 continue;
2064 /* The zeroth operand of the two component references must be
2065 identical. It is not sufficient to compare get_base_address of
2066 the two references, because this could allow for different
2067 elements of the same array in the two trees. It is not safe to
2068 assume that the existence of one array element implies the
2069 existence of a different one. */
2070 if (!operand_equal_p (TREE_OPERAND (ref1, 0), TREE_OPERAND (ref2, 0), 0))
2071 continue;
2073 field1 = TREE_OPERAND (ref1, 1);
2074 field2 = TREE_OPERAND (ref2, 1);
2076 /* Check for field adjacency, and ensure field1 comes first. */
2077 for (next = DECL_CHAIN (field1);
2078 next && TREE_CODE (next) != FIELD_DECL;
2079 next = DECL_CHAIN (next))
2082 if (next != field2)
2084 for (next = DECL_CHAIN (field2);
2085 next && TREE_CODE (next) != FIELD_DECL;
2086 next = DECL_CHAIN (next))
2089 if (next != field1)
2090 continue;
2092 fieldswap = field1;
2093 field1 = field2;
2094 field2 = fieldswap;
2095 defswap = def1;
2096 def1 = def2;
2097 def2 = defswap;
2100 bb_for_def1 = gimple_bb (def1);
2101 bb_for_def2 = gimple_bb (def2);
2103 /* Check for proper alignment of the first field. */
2104 tree_offset1 = bit_position (field1);
2105 tree_offset2 = bit_position (field2);
2106 tree_size2 = DECL_SIZE (field2);
2108 if (!tree_fits_uhwi_p (tree_offset1)
2109 || !tree_fits_uhwi_p (tree_offset2)
2110 || !tree_fits_uhwi_p (tree_size2))
2111 continue;
2113 offset1 = tree_to_uhwi (tree_offset1);
2114 offset2 = tree_to_uhwi (tree_offset2);
2115 size2 = tree_to_uhwi (tree_size2);
2116 align1 = DECL_ALIGN (field1) % param_align_bits;
2118 if (offset1 % BITS_PER_UNIT != 0)
2119 continue;
2121 /* For profitability, the two field references should fit within
2122 a single cache line. */
2123 if (align1 + offset2 - offset1 + size2 > param_align_bits)
2124 continue;
2126 /* The two expressions cannot be dependent upon vdefs defined
2127 in bb1/bb2. */
2128 if (local_mem_dependence (def1, bb_for_def1)
2129 || local_mem_dependence (def2, bb_for_def2))
2130 continue;
2132 /* The conditions are satisfied; hoist the loads from bb1 and bb2 into
2133 bb0. We hoist the first one first so that a cache miss is handled
2134 efficiently regardless of hardware cache-fill policy. */
2135 gsi2 = gsi_for_stmt (def1);
2136 gsi_move_to_bb_end (&gsi2, bb0);
2137 gsi2 = gsi_for_stmt (def2);
2138 gsi_move_to_bb_end (&gsi2, bb0);
2140 if (dump_file && (dump_flags & TDF_DETAILS))
2142 fprintf (dump_file,
2143 "\nHoisting adjacent loads from %d and %d into %d: \n",
2144 bb_for_def1->index, bb_for_def2->index, bb0->index);
2145 print_gimple_stmt (dump_file, def1, 0, TDF_VOPS|TDF_MEMSYMS);
2146 print_gimple_stmt (dump_file, def2, 0, TDF_VOPS|TDF_MEMSYMS);
2151 /* Determine whether we should attempt to hoist adjacent loads out of
2152 diamond patterns in pass_phiopt. Always hoist loads if
2153 -fhoist-adjacent-loads is specified and the target machine has
2154 both a conditional move instruction and a defined cache line size. */
2156 static bool
2157 gate_hoist_loads (void)
2159 return (flag_hoist_adjacent_loads == 1
2160 && PARAM_VALUE (PARAM_L1_CACHE_LINE_SIZE)
2161 && HAVE_conditional_move);
2164 /* This pass tries to replaces an if-then-else block with an
2165 assignment. We have four kinds of transformations. Some of these
2166 transformations are also performed by the ifcvt RTL optimizer.
2168 Conditional Replacement
2169 -----------------------
2171 This transformation, implemented in conditional_replacement,
2172 replaces
2174 bb0:
2175 if (cond) goto bb2; else goto bb1;
2176 bb1:
2177 bb2:
2178 x = PHI <0 (bb1), 1 (bb0), ...>;
2180 with
2182 bb0:
2183 x' = cond;
2184 goto bb2;
2185 bb2:
2186 x = PHI <x' (bb0), ...>;
2188 We remove bb1 as it becomes unreachable. This occurs often due to
2189 gimplification of conditionals.
2191 Value Replacement
2192 -----------------
2194 This transformation, implemented in value_replacement, replaces
2196 bb0:
2197 if (a != b) goto bb2; else goto bb1;
2198 bb1:
2199 bb2:
2200 x = PHI <a (bb1), b (bb0), ...>;
2202 with
2204 bb0:
2205 bb2:
2206 x = PHI <b (bb0), ...>;
2208 This opportunity can sometimes occur as a result of other
2209 optimizations.
2212 Another case caught by value replacement looks like this:
2214 bb0:
2215 t1 = a == CONST;
2216 t2 = b > c;
2217 t3 = t1 & t2;
2218 if (t3 != 0) goto bb1; else goto bb2;
2219 bb1:
2220 bb2:
2221 x = PHI (CONST, a)
2223 Gets replaced with:
2224 bb0:
2225 bb2:
2226 t1 = a == CONST;
2227 t2 = b > c;
2228 t3 = t1 & t2;
2229 x = a;
2231 ABS Replacement
2232 ---------------
2234 This transformation, implemented in abs_replacement, replaces
2236 bb0:
2237 if (a >= 0) goto bb2; else goto bb1;
2238 bb1:
2239 x = -a;
2240 bb2:
2241 x = PHI <x (bb1), a (bb0), ...>;
2243 with
2245 bb0:
2246 x' = ABS_EXPR< a >;
2247 bb2:
2248 x = PHI <x' (bb0), ...>;
2250 MIN/MAX Replacement
2251 -------------------
2253 This transformation, minmax_replacement replaces
2255 bb0:
2256 if (a <= b) goto bb2; else goto bb1;
2257 bb1:
2258 bb2:
2259 x = PHI <b (bb1), a (bb0), ...>;
2261 with
2263 bb0:
2264 x' = MIN_EXPR (a, b)
2265 bb2:
2266 x = PHI <x' (bb0), ...>;
2268 A similar transformation is done for MAX_EXPR.
2271 This pass also performs a fifth transformation of a slightly different
2272 flavor.
2274 Adjacent Load Hoisting
2275 ----------------------
2277 This transformation replaces
2279 bb0:
2280 if (...) goto bb2; else goto bb1;
2281 bb1:
2282 x1 = (<expr>).field1;
2283 goto bb3;
2284 bb2:
2285 x2 = (<expr>).field2;
2286 bb3:
2287 # x = PHI <x1, x2>;
2289 with
2291 bb0:
2292 x1 = (<expr>).field1;
2293 x2 = (<expr>).field2;
2294 if (...) goto bb2; else goto bb1;
2295 bb1:
2296 goto bb3;
2297 bb2:
2298 bb3:
2299 # x = PHI <x1, x2>;
2301 The purpose of this transformation is to enable generation of conditional
2302 move instructions such as Intel CMOVE or PowerPC ISEL. Because one of
2303 the loads is speculative, the transformation is restricted to very
2304 specific cases to avoid introducing a page fault. We are looking for
2305 the common idiom:
2307 if (...)
2308 x = y->left;
2309 else
2310 x = y->right;
2312 where left and right are typically adjacent pointers in a tree structure. */
2314 namespace {
2316 const pass_data pass_data_phiopt =
2318 GIMPLE_PASS, /* type */
2319 "phiopt", /* name */
2320 OPTGROUP_NONE, /* optinfo_flags */
2321 TV_TREE_PHIOPT, /* tv_id */
2322 ( PROP_cfg | PROP_ssa ), /* properties_required */
2323 0, /* properties_provided */
2324 0, /* properties_destroyed */
2325 0, /* todo_flags_start */
2326 0, /* todo_flags_finish */
2329 class pass_phiopt : public gimple_opt_pass
2331 public:
2332 pass_phiopt (gcc::context *ctxt)
2333 : gimple_opt_pass (pass_data_phiopt, ctxt)
2336 /* opt_pass methods: */
2337 opt_pass * clone () { return new pass_phiopt (m_ctxt); }
2338 virtual bool gate (function *) { return flag_ssa_phiopt; }
2339 virtual unsigned int execute (function *)
2341 return tree_ssa_phiopt_worker (false, gate_hoist_loads ());
2344 }; // class pass_phiopt
2346 } // anon namespace
2348 gimple_opt_pass *
2349 make_pass_phiopt (gcc::context *ctxt)
2351 return new pass_phiopt (ctxt);
2354 namespace {
2356 const pass_data pass_data_cselim =
2358 GIMPLE_PASS, /* type */
2359 "cselim", /* name */
2360 OPTGROUP_NONE, /* optinfo_flags */
2361 TV_TREE_PHIOPT, /* tv_id */
2362 ( PROP_cfg | PROP_ssa ), /* properties_required */
2363 0, /* properties_provided */
2364 0, /* properties_destroyed */
2365 0, /* todo_flags_start */
2366 0, /* todo_flags_finish */
2369 class pass_cselim : public gimple_opt_pass
2371 public:
2372 pass_cselim (gcc::context *ctxt)
2373 : gimple_opt_pass (pass_data_cselim, ctxt)
2376 /* opt_pass methods: */
2377 virtual bool gate (function *) { return flag_tree_cselim; }
2378 virtual unsigned int execute (function *) { return tree_ssa_cs_elim (); }
2380 }; // class pass_cselim
2382 } // anon namespace
2384 gimple_opt_pass *
2385 make_pass_cselim (gcc::context *ctxt)
2387 return new pass_cselim (ctxt);