1 /* Optimization of PHI nodes by converting them into straightline code.
2 Copyright (C) 2004-2018 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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.
10
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.
15
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/>. */
19
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"
48
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);
68
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:
72
73 bb0:
74 if (cond) goto bb2; else goto bb1;
75 bb1:
76 *p = RHS;
77 bb2:
78
79 with
80
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;
88
89 This transformation can only be done under several constraints,
90 documented below. It also replaces:
91
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:
100
101 with
102
103 bb0:
104 if (cond) goto bb3; else goto bb1;
105 bb1:
106 bb3:
107 condtmp = PHI <RHS1, RHS2>
108 *p = condtmp; */
109
110 static unsigned int
tree_ssa_cs_elim(void)111 tree_ssa_cs_elim (void)
112 {
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;
123 }
124
125 /* Return the singleton PHI in the SEQ of PHIs for edges E0 and E1. */
126
127 static gphi *
single_non_singleton_phi_for_edges(gimple_seq seq,edge e0,edge e1)128 single_non_singleton_phi_for_edges (gimple_seq seq, edge e0, edge e1)
129 {
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))
135 {
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;
141
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;
146
147 phi = p;
148 }
149 return phi;
150 }
151
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
tree_ssa_phiopt_worker(bool do_store_elim,bool do_hoist_loads)159 tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads)
160 {
161 basic_block bb;
162 basic_block *bb_order;
163 unsigned n, i;
164 bool cfgchanged = false;
165 hash_set<tree> *nontrap = 0;
166
167 if (do_store_elim)
168 /* Calculate the set of non-trapping memory accesses. */
169 nontrap = get_non_trapping ();
170
171 /* Search every basic block for COND_EXPR we may be able to optimize.
172
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;
180
181 for (i = 0; i < n; i++)
182 {
183 gimple *cond_stmt;
184 gphi *phi;
185 basic_block bb1, bb2;
186 edge e1, e2;
187 tree arg0, arg1;
188
189 bb = bb_order[i];
190
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;
196
197 e1 = EDGE_SUCC (bb, 0);
198 bb1 = e1->dest;
199 e2 = EDGE_SUCC (bb, 1);
200 bb2 = e2->dest;
201
202 /* We cannot do the optimization on abnormal edges. */
203 if ((e1->flags & EDGE_ABNORMAL) != 0
204 || (e2->flags & EDGE_ABNORMAL) != 0)
205 continue;
206
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;
212
213 /* Find the bb which is the fall through to the other. */
214 if (EDGE_SUCC (bb1, 0)->dest == bb2)
215 ;
216 else if (EDGE_SUCC (bb2, 0)->dest == bb1)
217 {
218 std::swap (bb1, bb2);
219 std::swap (e1, e2);
220 }
221 else if (do_store_elim
222 && EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest)
223 {
224 basic_block bb3 = EDGE_SUCC (bb1, 0)->dest;
225
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;
235 }
236 else if (do_hoist_loads
237 && EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest)
238 {
239 basic_block bb3 = EDGE_SUCC (bb1, 0)->dest;
240
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;
254 }
255 else
256 continue;
257
258 e1 = EDGE_SUCC (bb1, 0);
259
260 /* Make sure that bb1 is just a fall through. */
261 if (!single_succ_p (bb1)
262 || (e1->flags & EDGE_FALLTHRU) == 0)
263 continue;
264
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;
270
271 if (do_store_elim)
272 {
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;
280 }
281 else
282 {
283 gimple_seq phis = phi_nodes (bb2);
284 gimple_stmt_iterator gsi;
285 bool candorest = true;
286
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))
290 {
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)
295 {
296 candorest = false;
297 cfgchanged = true;
298 break;
299 }
300 }
301
302 if (!candorest)
303 continue;
304
305 phi = single_non_singleton_phi_for_edges (phis, e1, e2);
306 if (!phi)
307 continue;
308
309 arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
310 arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
311
312 /* Something is wrong if we cannot find the arguments in the PHI
313 node. */
314 gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
315
316 gphi *newphi = factor_out_conditional_conversion (e1, e2, phi,
317 arg0, arg1,
318 cond_stmt);
319 if (newphi != NULL)
320 {
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);
328 }
329
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;
337 }
338 }
339
340 free (bb_order);
341
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)
346 {
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;
351 }
352 else if (cfgchanged)
353 return TODO_cleanup_cfg;
354 return 0;
355 }
356
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). */
360
361 static void
replace_phi_edge_with_variable(basic_block cond_block,edge e,gimple * phi,tree new_tree)362 replace_phi_edge_with_variable (basic_block cond_block,
363 edge e, gimple *phi, tree new_tree)
364 {
365 basic_block bb = gimple_bb (phi);
366 basic_block block_to_remove;
367 gimple_stmt_iterator gsi;
368
369 /* Change the PHI argument to new. */
370 SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);
371
372 /* Remove the empty basic block. */
373 if (EDGE_SUCC (cond_block, 0)->dest == bb)
374 {
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 ();
378
379 block_to_remove = EDGE_SUCC (cond_block, 1)->dest;
380 }
381 else
382 {
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 ();
387
388 block_to_remove = EDGE_SUCC (cond_block, 0)->dest;
389 }
390 delete_basic_block (block_to_remove);
391
392 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
393 gsi = gsi_last_bb (cond_block);
394 gsi_remove (&gsi, true);
395
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);
401 }
402
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. */
407
408 static gphi *
factor_out_conditional_conversion(edge e0,edge e1,gphi * phi,tree arg0,tree arg1,gimple * cond_stmt)409 factor_out_conditional_conversion (edge e0, edge e1, gphi *phi,
410 tree arg0, tree arg1, gimple *cond_stmt)
411 {
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;
419
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;
426
427 /* First canonicalize to simplify tests. */
428 if (TREE_CODE (arg0) != SSA_NAME)
429 {
430 std::swap (arg0, arg1);
431 std::swap (e0, e1);
432 }
433
434 if (TREE_CODE (arg0) != SSA_NAME
435 || (TREE_CODE (arg1) != SSA_NAME
436 && TREE_CODE (arg1) != INTEGER_CST))
437 return NULL;
438
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;
444
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)
449 {
450 new_arg0 = TREE_OPERAND (new_arg0, 0);
451 if (!is_gimple_reg_type (TREE_TYPE (new_arg0)))
452 return NULL;
453 }
454 if (TREE_CODE (new_arg0) == SSA_NAME
455 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_arg0))
456 return NULL;
457
458 if (TREE_CODE (arg1) == SSA_NAME)
459 {
460 /* Check if arg1 is an SSA_NAME and the stmt which defines arg1
461 is a conversion. */
462 arg1_def_stmt = SSA_NAME_DEF_STMT (arg1);
463 if (!is_gimple_assign (arg1_def_stmt)
464 || gimple_assign_rhs_code (arg1_def_stmt) != convert_code)
465 return NULL;
466
467 /* Use the RHS as new_arg1. */
468 new_arg1 = gimple_assign_rhs1 (arg1_def_stmt);
469 if (convert_code == VIEW_CONVERT_EXPR)
470 new_arg1 = TREE_OPERAND (new_arg1, 0);
471 if (TREE_CODE (new_arg1) == SSA_NAME
472 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_arg1))
473 return NULL;
474 }
475 else
476 {
477 /* If arg1 is an INTEGER_CST, fold it to new type. */
478 if (INTEGRAL_TYPE_P (TREE_TYPE (new_arg0))
479 && int_fits_type_p (arg1, TREE_TYPE (new_arg0)))
480 {
481 if (gimple_assign_cast_p (arg0_def_stmt))
482 {
483 /* For the INTEGER_CST case, we are just moving the
484 conversion from one place to another, which can often
485 hurt as the conversion moves further away from the
486 statement that computes the value. So, perform this
487 only if new_arg0 is an operand of COND_STMT, or
488 if arg0_def_stmt is the only non-debug stmt in
489 its basic block, because then it is possible this
490 could enable further optimizations (minmax replacement
491 etc.). See PR71016. */
492 if (new_arg0 != gimple_cond_lhs (cond_stmt)
493 && new_arg0 != gimple_cond_rhs (cond_stmt)
494 && gimple_bb (arg0_def_stmt) == e0->src)
495 {
496 gsi = gsi_for_stmt (arg0_def_stmt);
497 gsi_prev_nondebug (&gsi);
498 if (!gsi_end_p (gsi))
499 return NULL;
500 gsi = gsi_for_stmt (arg0_def_stmt);
501 gsi_next_nondebug (&gsi);
502 if (!gsi_end_p (gsi))
503 return NULL;
504 }
505 new_arg1 = fold_convert (TREE_TYPE (new_arg0), arg1);
506 }
507 else
508 return NULL;
509 }
510 else
511 return NULL;
512 }
513
514 /* If arg0/arg1 have > 1 use, then this transformation actually increases
515 the number of expressions evaluated at runtime. */
516 if (!has_single_use (arg0)
517 || (arg1_def_stmt && !has_single_use (arg1)))
518 return NULL;
519
520 /* If types of new_arg0 and new_arg1 are different bailout. */
521 if (!types_compatible_p (TREE_TYPE (new_arg0), TREE_TYPE (new_arg1)))
522 return NULL;
523
524 /* Create a new PHI stmt. */
525 result = PHI_RESULT (phi);
526 temp = make_ssa_name (TREE_TYPE (new_arg0), NULL);
527 newphi = create_phi_node (temp, gimple_bb (phi));
528
529 if (dump_file && (dump_flags & TDF_DETAILS))
530 {
531 fprintf (dump_file, "PHI ");
532 print_generic_expr (dump_file, gimple_phi_result (phi));
533 fprintf (dump_file,
534 " changed to factor conversion out from COND_EXPR.\n");
535 fprintf (dump_file, "New stmt with CAST that defines ");
536 print_generic_expr (dump_file, result);
537 fprintf (dump_file, ".\n");
538 }
539
540 /* Remove the old cast(s) that has single use. */
541 gsi_for_def = gsi_for_stmt (arg0_def_stmt);
542 gsi_remove (&gsi_for_def, true);
543 release_defs (arg0_def_stmt);
544
545 if (arg1_def_stmt)
546 {
547 gsi_for_def = gsi_for_stmt (arg1_def_stmt);
548 gsi_remove (&gsi_for_def, true);
549 release_defs (arg1_def_stmt);
550 }
551
552 add_phi_arg (newphi, new_arg0, e0, locus);
553 add_phi_arg (newphi, new_arg1, e1, locus);
554
555 /* Create the conversion stmt and insert it. */
556 if (convert_code == VIEW_CONVERT_EXPR)
557 {
558 temp = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (result), temp);
559 new_stmt = gimple_build_assign (result, temp);
560 }
561 else
562 new_stmt = gimple_build_assign (result, convert_code, temp);
563 gsi = gsi_after_labels (gimple_bb (phi));
564 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
565
566 /* Remove the original PHI stmt. */
567 gsi = gsi_for_stmt (phi);
568 gsi_remove (&gsi, true);
569 return newphi;
570 }
571
572 /* The function conditional_replacement does the main work of doing the
573 conditional replacement. Return true if the replacement is done.
574 Otherwise return false.
575 BB is the basic block where the replacement is going to be done on. ARG0
576 is argument 0 from PHI. Likewise for ARG1. */
577
578 static bool
conditional_replacement(basic_block cond_bb,basic_block middle_bb,edge e0,edge e1,gphi * phi,tree arg0,tree arg1)579 conditional_replacement (basic_block cond_bb, basic_block middle_bb,
580 edge e0, edge e1, gphi *phi,
581 tree arg0, tree arg1)
582 {
583 tree result;
584 gimple *stmt;
585 gassign *new_stmt;
586 tree cond;
587 gimple_stmt_iterator gsi;
588 edge true_edge, false_edge;
589 tree new_var, new_var2;
590 bool neg;
591
592 /* FIXME: Gimplification of complex type is too hard for now. */
593 /* We aren't prepared to handle vectors either (and it is a question
594 if it would be worthwhile anyway). */
595 if (!(INTEGRAL_TYPE_P (TREE_TYPE (arg0))
596 || POINTER_TYPE_P (TREE_TYPE (arg0)))
597 || !(INTEGRAL_TYPE_P (TREE_TYPE (arg1))
598 || POINTER_TYPE_P (TREE_TYPE (arg1))))
599 return false;
600
601 /* The PHI arguments have the constants 0 and 1, or 0 and -1, then
602 convert it to the conditional. */
603 if ((integer_zerop (arg0) && integer_onep (arg1))
604 || (integer_zerop (arg1) && integer_onep (arg0)))
605 neg = false;
606 else if ((integer_zerop (arg0) && integer_all_onesp (arg1))
607 || (integer_zerop (arg1) && integer_all_onesp (arg0)))
608 neg = true;
609 else
610 return false;
611
612 if (!empty_block_p (middle_bb))
613 return false;
614
615 /* At this point we know we have a GIMPLE_COND with two successors.
616 One successor is BB, the other successor is an empty block which
617 falls through into BB.
618
619 There is a single PHI node at the join point (BB) and its arguments
620 are constants (0, 1) or (0, -1).
621
622 So, given the condition COND, and the two PHI arguments, we can
623 rewrite this PHI into non-branching code:
624
625 dest = (COND) or dest = COND'
626
627 We use the condition as-is if the argument associated with the
628 true edge has the value one or the argument associated with the
629 false edge as the value zero. Note that those conditions are not
630 the same since only one of the outgoing edges from the GIMPLE_COND
631 will directly reach BB and thus be associated with an argument. */
632
633 stmt = last_stmt (cond_bb);
634 result = PHI_RESULT (phi);
635
636 /* To handle special cases like floating point comparison, it is easier and
637 less error-prone to build a tree and gimplify it on the fly though it is
638 less efficient. */
639 cond = fold_build2_loc (gimple_location (stmt),
640 gimple_cond_code (stmt), boolean_type_node,
641 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
642
643 /* We need to know which is the true edge and which is the false
644 edge so that we know when to invert the condition below. */
645 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
646 if ((e0 == true_edge && integer_zerop (arg0))
647 || (e0 == false_edge && !integer_zerop (arg0))
648 || (e1 == true_edge && integer_zerop (arg1))
649 || (e1 == false_edge && !integer_zerop (arg1)))
650 cond = fold_build1_loc (gimple_location (stmt),
651 TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
652
653 if (neg)
654 {
655 cond = fold_convert_loc (gimple_location (stmt),
656 TREE_TYPE (result), cond);
657 cond = fold_build1_loc (gimple_location (stmt),
658 NEGATE_EXPR, TREE_TYPE (cond), cond);
659 }
660
661 /* Insert our new statements at the end of conditional block before the
662 COND_STMT. */
663 gsi = gsi_for_stmt (stmt);
664 new_var = force_gimple_operand_gsi (&gsi, cond, true, NULL, true,
665 GSI_SAME_STMT);
666
667 if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (new_var)))
668 {
669 source_location locus_0, locus_1;
670
671 new_var2 = make_ssa_name (TREE_TYPE (result));
672 new_stmt = gimple_build_assign (new_var2, CONVERT_EXPR, new_var);
673 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
674 new_var = new_var2;
675
676 /* Set the locus to the first argument, unless is doesn't have one. */
677 locus_0 = gimple_phi_arg_location (phi, 0);
678 locus_1 = gimple_phi_arg_location (phi, 1);
679 if (locus_0 == UNKNOWN_LOCATION)
680 locus_0 = locus_1;
681 gimple_set_location (new_stmt, locus_0);
682 }
683
684 replace_phi_edge_with_variable (cond_bb, e1, phi, new_var);
685
686 /* Note that we optimized this PHI. */
687 return true;
688 }
689
690 /* Update *ARG which is defined in STMT so that it contains the
691 computed value if that seems profitable. Return true if the
692 statement is made dead by that rewriting. */
693
694 static bool
jump_function_from_stmt(tree * arg,gimple * stmt)695 jump_function_from_stmt (tree *arg, gimple *stmt)
696 {
697 enum tree_code code = gimple_assign_rhs_code (stmt);
698 if (code == ADDR_EXPR)
699 {
700 /* For arg = &p->i transform it to p, if possible. */
701 tree rhs1 = gimple_assign_rhs1 (stmt);
702 poly_int64 offset;
703 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs1, 0),
704 &offset);
705 if (tem
706 && TREE_CODE (tem) == MEM_REF
707 && known_eq (mem_ref_offset (tem) + offset, 0))
708 {
709 *arg = TREE_OPERAND (tem, 0);
710 return true;
711 }
712 }
713 /* TODO: Much like IPA-CP jump-functions we want to handle constant
714 additions symbolically here, and we'd need to update the comparison
715 code that compares the arg + cst tuples in our caller. For now the
716 code above exactly handles the VEC_BASE pattern from vec.h. */
717 return false;
718 }
719
720 /* RHS is a source argument in a BIT_AND_EXPR which feeds a conditional
721 of the form SSA_NAME NE 0.
722
723 If RHS is fed by a simple EQ_EXPR comparison of two values, see if
724 the two input values of the EQ_EXPR match arg0 and arg1.
725
726 If so update *code and return TRUE. Otherwise return FALSE. */
727
728 static bool
rhs_is_fed_for_value_replacement(const_tree arg0,const_tree arg1,enum tree_code * code,const_tree rhs)729 rhs_is_fed_for_value_replacement (const_tree arg0, const_tree arg1,
730 enum tree_code *code, const_tree rhs)
731 {
732 /* Obviously if RHS is not an SSA_NAME, we can't look at the defining
733 statement. */
734 if (TREE_CODE (rhs) == SSA_NAME)
735 {
736 gimple *def1 = SSA_NAME_DEF_STMT (rhs);
737
738 /* Verify the defining statement has an EQ_EXPR on the RHS. */
739 if (is_gimple_assign (def1) && gimple_assign_rhs_code (def1) == EQ_EXPR)
740 {
741 /* Finally verify the source operands of the EQ_EXPR are equal
742 to arg0 and arg1. */
743 tree op0 = gimple_assign_rhs1 (def1);
744 tree op1 = gimple_assign_rhs2 (def1);
745 if ((operand_equal_for_phi_arg_p (arg0, op0)
746 && operand_equal_for_phi_arg_p (arg1, op1))
747 || (operand_equal_for_phi_arg_p (arg0, op1)
748 && operand_equal_for_phi_arg_p (arg1, op0)))
749 {
750 /* We will perform the optimization. */
751 *code = gimple_assign_rhs_code (def1);
752 return true;
753 }
754 }
755 }
756 return false;
757 }
758
759 /* Return TRUE if arg0/arg1 are equal to the rhs/lhs or lhs/rhs of COND.
760
761 Also return TRUE if arg0/arg1 are equal to the source arguments of a
762 an EQ comparison feeding a BIT_AND_EXPR which feeds COND.
763
764 Return FALSE otherwise. */
765
766 static bool
operand_equal_for_value_replacement(const_tree arg0,const_tree arg1,enum tree_code * code,gimple * cond)767 operand_equal_for_value_replacement (const_tree arg0, const_tree arg1,
768 enum tree_code *code, gimple *cond)
769 {
770 gimple *def;
771 tree lhs = gimple_cond_lhs (cond);
772 tree rhs = gimple_cond_rhs (cond);
773
774 if ((operand_equal_for_phi_arg_p (arg0, lhs)
775 && operand_equal_for_phi_arg_p (arg1, rhs))
776 || (operand_equal_for_phi_arg_p (arg1, lhs)
777 && operand_equal_for_phi_arg_p (arg0, rhs)))
778 return true;
779
780 /* Now handle more complex case where we have an EQ comparison
781 which feeds a BIT_AND_EXPR which feeds COND.
782
783 First verify that COND is of the form SSA_NAME NE 0. */
784 if (*code != NE_EXPR || !integer_zerop (rhs)
785 || TREE_CODE (lhs) != SSA_NAME)
786 return false;
787
788 /* Now ensure that SSA_NAME is set by a BIT_AND_EXPR. */
789 def = SSA_NAME_DEF_STMT (lhs);
790 if (!is_gimple_assign (def) || gimple_assign_rhs_code (def) != BIT_AND_EXPR)
791 return false;
792
793 /* Now verify arg0/arg1 correspond to the source arguments of an
794 EQ comparison feeding the BIT_AND_EXPR. */
795
796 tree tmp = gimple_assign_rhs1 (def);
797 if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp))
798 return true;
799
800 tmp = gimple_assign_rhs2 (def);
801 if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp))
802 return true;
803
804 return false;
805 }
806
807 /* Returns true if ARG is a neutral element for operation CODE
808 on the RIGHT side. */
809
810 static bool
neutral_element_p(tree_code code,tree arg,bool right)811 neutral_element_p (tree_code code, tree arg, bool right)
812 {
813 switch (code)
814 {
815 case PLUS_EXPR:
816 case BIT_IOR_EXPR:
817 case BIT_XOR_EXPR:
818 return integer_zerop (arg);
819
820 case LROTATE_EXPR:
821 case RROTATE_EXPR:
822 case LSHIFT_EXPR:
823 case RSHIFT_EXPR:
824 case MINUS_EXPR:
825 case POINTER_PLUS_EXPR:
826 return right && integer_zerop (arg);
827
828 case MULT_EXPR:
829 return integer_onep (arg);
830
831 case TRUNC_DIV_EXPR:
832 case CEIL_DIV_EXPR:
833 case FLOOR_DIV_EXPR:
834 case ROUND_DIV_EXPR:
835 case EXACT_DIV_EXPR:
836 return right && integer_onep (arg);
837
838 case BIT_AND_EXPR:
839 return integer_all_onesp (arg);
840
841 default:
842 return false;
843 }
844 }
845
846 /* Returns true if ARG is an absorbing element for operation CODE. */
847
848 static bool
absorbing_element_p(tree_code code,tree arg,bool right,tree rval)849 absorbing_element_p (tree_code code, tree arg, bool right, tree rval)
850 {
851 switch (code)
852 {
853 case BIT_IOR_EXPR:
854 return integer_all_onesp (arg);
855
856 case MULT_EXPR:
857 case BIT_AND_EXPR:
858 return integer_zerop (arg);
859
860 case LSHIFT_EXPR:
861 case RSHIFT_EXPR:
862 case LROTATE_EXPR:
863 case RROTATE_EXPR:
864 return !right && integer_zerop (arg);
865
866 case TRUNC_DIV_EXPR:
867 case CEIL_DIV_EXPR:
868 case FLOOR_DIV_EXPR:
869 case ROUND_DIV_EXPR:
870 case EXACT_DIV_EXPR:
871 case TRUNC_MOD_EXPR:
872 case CEIL_MOD_EXPR:
873 case FLOOR_MOD_EXPR:
874 case ROUND_MOD_EXPR:
875 return (!right
876 && integer_zerop (arg)
877 && tree_single_nonzero_warnv_p (rval, NULL));
878
879 default:
880 return false;
881 }
882 }
883
884 /* The function value_replacement does the main work of doing the value
885 replacement. Return non-zero if the replacement is done. Otherwise return
886 0. If we remove the middle basic block, return 2.
887 BB is the basic block where the replacement is going to be done on. ARG0
888 is argument 0 from the PHI. Likewise for ARG1. */
889
890 static int
value_replacement(basic_block cond_bb,basic_block middle_bb,edge e0,edge e1,gimple * phi,tree arg0,tree arg1)891 value_replacement (basic_block cond_bb, basic_block middle_bb,
892 edge e0, edge e1, gimple *phi,
893 tree arg0, tree arg1)
894 {
895 gimple_stmt_iterator gsi;
896 gimple *cond;
897 edge true_edge, false_edge;
898 enum tree_code code;
899 bool empty_or_with_defined_p = true;
900
901 /* If the type says honor signed zeros we cannot do this
902 optimization. */
903 if (HONOR_SIGNED_ZEROS (arg1))
904 return 0;
905
906 /* If there is a statement in MIDDLE_BB that defines one of the PHI
907 arguments, then adjust arg0 or arg1. */
908 gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
909 while (!gsi_end_p (gsi))
910 {
911 gimple *stmt = gsi_stmt (gsi);
912 tree lhs;
913 gsi_next_nondebug (&gsi);
914 if (!is_gimple_assign (stmt))
915 {
916 empty_or_with_defined_p = false;
917 continue;
918 }
919 /* Now try to adjust arg0 or arg1 according to the computation
920 in the statement. */
921 lhs = gimple_assign_lhs (stmt);
922 if (!(lhs == arg0
923 && jump_function_from_stmt (&arg0, stmt))
924 || (lhs == arg1
925 && jump_function_from_stmt (&arg1, stmt)))
926 empty_or_with_defined_p = false;
927 }
928
929 cond = last_stmt (cond_bb);
930 code = gimple_cond_code (cond);
931
932 /* This transformation is only valid for equality comparisons. */
933 if (code != NE_EXPR && code != EQ_EXPR)
934 return 0;
935
936 /* We need to know which is the true edge and which is the false
937 edge so that we know if have abs or negative abs. */
938 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
939
940 /* At this point we know we have a COND_EXPR with two successors.
941 One successor is BB, the other successor is an empty block which
942 falls through into BB.
943
944 The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
945
946 There is a single PHI node at the join point (BB) with two arguments.
947
948 We now need to verify that the two arguments in the PHI node match
949 the two arguments to the equality comparison. */
950
951 if (operand_equal_for_value_replacement (arg0, arg1, &code, cond))
952 {
953 edge e;
954 tree arg;
955
956 /* For NE_EXPR, we want to build an assignment result = arg where
957 arg is the PHI argument associated with the true edge. For
958 EQ_EXPR we want the PHI argument associated with the false edge. */
959 e = (code == NE_EXPR ? true_edge : false_edge);
960
961 /* Unfortunately, E may not reach BB (it may instead have gone to
962 OTHER_BLOCK). If that is the case, then we want the single outgoing
963 edge from OTHER_BLOCK which reaches BB and represents the desired
964 path from COND_BLOCK. */
965 if (e->dest == middle_bb)
966 e = single_succ_edge (e->dest);
967
968 /* Now we know the incoming edge to BB that has the argument for the
969 RHS of our new assignment statement. */
970 if (e0 == e)
971 arg = arg0;
972 else
973 arg = arg1;
974
975 /* If the middle basic block was empty or is defining the
976 PHI arguments and this is a single phi where the args are different
977 for the edges e0 and e1 then we can remove the middle basic block. */
978 if (empty_or_with_defined_p
979 && single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)),
980 e0, e1) == phi)
981 {
982 replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
983 /* Note that we optimized this PHI. */
984 return 2;
985 }
986 else
987 {
988 /* Replace the PHI arguments with arg. */
989 SET_PHI_ARG_DEF (phi, e0->dest_idx, arg);
990 SET_PHI_ARG_DEF (phi, e1->dest_idx, arg);
991 if (dump_file && (dump_flags & TDF_DETAILS))
992 {
993 fprintf (dump_file, "PHI ");
994 print_generic_expr (dump_file, gimple_phi_result (phi));
995 fprintf (dump_file, " reduced for COND_EXPR in block %d to ",
996 cond_bb->index);
997 print_generic_expr (dump_file, arg);
998 fprintf (dump_file, ".\n");
999 }
1000 return 1;
1001 }
1002
1003 }
1004
1005 /* Now optimize (x != 0) ? x + y : y to just x + y. */
1006 gsi = gsi_last_nondebug_bb (middle_bb);
1007 if (gsi_end_p (gsi))
1008 return 0;
1009
1010 gimple *assign = gsi_stmt (gsi);
1011 if (!is_gimple_assign (assign)
1012 || gimple_assign_rhs_class (assign) != GIMPLE_BINARY_RHS
1013 || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
1014 && !POINTER_TYPE_P (TREE_TYPE (arg0))))
1015 return 0;
1016
1017 /* Punt if there are (degenerate) PHIs in middle_bb, there should not be. */
1018 if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
1019 return 0;
1020
1021 /* Allow up to 2 cheap preparation statements that prepare argument
1022 for assign, e.g.:
1023 if (y_4 != 0)
1024 goto <bb 3>;
1025 else
1026 goto <bb 4>;
1027 <bb 3>:
1028 _1 = (int) y_4;
1029 iftmp.0_6 = x_5(D) r<< _1;
1030 <bb 4>:
1031 # iftmp.0_2 = PHI <iftmp.0_6(3), x_5(D)(2)>
1032 or:
1033 if (y_3(D) == 0)
1034 goto <bb 4>;
1035 else
1036 goto <bb 3>;
1037 <bb 3>:
1038 y_4 = y_3(D) & 31;
1039 _1 = (int) y_4;
1040 _6 = x_5(D) r<< _1;
1041 <bb 4>:
1042 # _2 = PHI <x_5(D)(2), _6(3)> */
1043 gimple *prep_stmt[2] = { NULL, NULL };
1044 int prep_cnt;
1045 for (prep_cnt = 0; ; prep_cnt++)
1046 {
1047 gsi_prev_nondebug (&gsi);
1048 if (gsi_end_p (gsi))
1049 break;
1050
1051 gimple *g = gsi_stmt (gsi);
1052 if (gimple_code (g) == GIMPLE_LABEL)
1053 break;
1054
1055 if (prep_cnt == 2 || !is_gimple_assign (g))
1056 return 0;
1057
1058 tree lhs = gimple_assign_lhs (g);
1059 tree rhs1 = gimple_assign_rhs1 (g);
1060 use_operand_p use_p;
1061 gimple *use_stmt;
1062 if (TREE_CODE (lhs) != SSA_NAME
1063 || TREE_CODE (rhs1) != SSA_NAME
1064 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1065 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1066 || !single_imm_use (lhs, &use_p, &use_stmt)
1067 || use_stmt != (prep_cnt ? prep_stmt[prep_cnt - 1] : assign))
1068 return 0;
1069 switch (gimple_assign_rhs_code (g))
1070 {
1071 CASE_CONVERT:
1072 break;
1073 case PLUS_EXPR:
1074 case BIT_AND_EXPR:
1075 case BIT_IOR_EXPR:
1076 case BIT_XOR_EXPR:
1077 if (TREE_CODE (gimple_assign_rhs2 (g)) != INTEGER_CST)
1078 return 0;
1079 break;
1080 default:
1081 return 0;
1082 }
1083 prep_stmt[prep_cnt] = g;
1084 }
1085
1086 /* Only transform if it removes the condition. */
1087 if (!single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)), e0, e1))
1088 return 0;
1089
1090 /* Size-wise, this is always profitable. */
1091 if (optimize_bb_for_speed_p (cond_bb)
1092 /* The special case is useless if it has a low probability. */
1093 && profile_status_for_fn (cfun) != PROFILE_ABSENT
1094 && EDGE_PRED (middle_bb, 0)->probability < profile_probability::even ()
1095 /* If assign is cheap, there is no point avoiding it. */
1096 && estimate_num_insns_seq (bb_seq (middle_bb), &eni_time_weights)
1097 >= 3 * estimate_num_insns (cond, &eni_time_weights))
1098 return 0;
1099
1100 tree lhs = gimple_assign_lhs (assign);
1101 tree rhs1 = gimple_assign_rhs1 (assign);
1102 tree rhs2 = gimple_assign_rhs2 (assign);
1103 enum tree_code code_def = gimple_assign_rhs_code (assign);
1104 tree cond_lhs = gimple_cond_lhs (cond);
1105 tree cond_rhs = gimple_cond_rhs (cond);
1106
1107 /* Propagate the cond_rhs constant through preparation stmts,
1108 make sure UB isn't invoked while doing that. */
1109 for (int i = prep_cnt - 1; i >= 0; --i)
1110 {
1111 gimple *g = prep_stmt[i];
1112 tree grhs1 = gimple_assign_rhs1 (g);
1113 if (!operand_equal_for_phi_arg_p (cond_lhs, grhs1))
1114 return 0;
1115 cond_lhs = gimple_assign_lhs (g);
1116 cond_rhs = fold_convert (TREE_TYPE (grhs1), cond_rhs);
1117 if (TREE_CODE (cond_rhs) != INTEGER_CST
1118 || TREE_OVERFLOW (cond_rhs))
1119 return 0;
1120 if (gimple_assign_rhs_class (g) == GIMPLE_BINARY_RHS)
1121 {
1122 cond_rhs = int_const_binop (gimple_assign_rhs_code (g), cond_rhs,
1123 gimple_assign_rhs2 (g));
1124 if (TREE_OVERFLOW (cond_rhs))
1125 return 0;
1126 }
1127 cond_rhs = fold_convert (TREE_TYPE (cond_lhs), cond_rhs);
1128 if (TREE_CODE (cond_rhs) != INTEGER_CST
1129 || TREE_OVERFLOW (cond_rhs))
1130 return 0;
1131 }
1132
1133 if (((code == NE_EXPR && e1 == false_edge)
1134 || (code == EQ_EXPR && e1 == true_edge))
1135 && arg0 == lhs
1136 && ((arg1 == rhs1
1137 && operand_equal_for_phi_arg_p (rhs2, cond_lhs)
1138 && neutral_element_p (code_def, cond_rhs, true))
1139 || (arg1 == rhs2
1140 && operand_equal_for_phi_arg_p (rhs1, cond_lhs)
1141 && neutral_element_p (code_def, cond_rhs, false))
1142 || (operand_equal_for_phi_arg_p (arg1, cond_rhs)
1143 && ((operand_equal_for_phi_arg_p (rhs2, cond_lhs)
1144 && absorbing_element_p (code_def, cond_rhs, true, rhs2))
1145 || (operand_equal_for_phi_arg_p (rhs1, cond_lhs)
1146 && absorbing_element_p (code_def,
1147 cond_rhs, false, rhs2))))))
1148 {
1149 gsi = gsi_for_stmt (cond);
1150 /* Moving ASSIGN might change VR of lhs, e.g. when moving u_6
1151 def-stmt in:
1152 if (n_5 != 0)
1153 goto <bb 3>;
1154 else
1155 goto <bb 4>;
1156
1157 <bb 3>:
1158 # RANGE [0, 4294967294]
1159 u_6 = n_5 + 4294967295;
1160
1161 <bb 4>:
1162 # u_3 = PHI <u_6(3), 4294967295(2)> */
1163 reset_flow_sensitive_info (lhs);
1164 if (INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
1165 {
1166 /* If available, we can use VR of phi result at least. */
1167 tree phires = gimple_phi_result (phi);
1168 struct range_info_def *phires_range_info
1169 = SSA_NAME_RANGE_INFO (phires);
1170 if (phires_range_info)
1171 duplicate_ssa_name_range_info (lhs, SSA_NAME_RANGE_TYPE (phires),
1172 phires_range_info);
1173 }
1174 gimple_stmt_iterator gsi_from;
1175 for (int i = prep_cnt - 1; i >= 0; --i)
1176 {
1177 tree plhs = gimple_assign_lhs (prep_stmt[i]);
1178 reset_flow_sensitive_info (plhs);
1179 gsi_from = gsi_for_stmt (prep_stmt[i]);
1180 gsi_move_before (&gsi_from, &gsi);
1181 }
1182 gsi_from = gsi_for_stmt (assign);
1183 gsi_move_before (&gsi_from, &gsi);
1184 replace_phi_edge_with_variable (cond_bb, e1, phi, lhs);
1185 return 2;
1186 }
1187
1188 return 0;
1189 }
1190
1191 /* The function minmax_replacement does the main work of doing the minmax
1192 replacement. Return true if the replacement is done. Otherwise return
1193 false.
1194 BB is the basic block where the replacement is going to be done on. ARG0
1195 is argument 0 from the PHI. Likewise for ARG1. */
1196
1197 static bool
minmax_replacement(basic_block cond_bb,basic_block middle_bb,edge e0,edge e1,gimple * phi,tree arg0,tree arg1)1198 minmax_replacement (basic_block cond_bb, basic_block middle_bb,
1199 edge e0, edge e1, gimple *phi,
1200 tree arg0, tree arg1)
1201 {
1202 tree result, type;
1203 gcond *cond;
1204 gassign *new_stmt;
1205 edge true_edge, false_edge;
1206 enum tree_code cmp, minmax, ass_code;
1207 tree smaller, alt_smaller, larger, alt_larger, arg_true, arg_false;
1208 gimple_stmt_iterator gsi, gsi_from;
1209
1210 type = TREE_TYPE (PHI_RESULT (phi));
1211
1212 /* The optimization may be unsafe due to NaNs. */
1213 if (HONOR_NANS (type) || HONOR_SIGNED_ZEROS (type))
1214 return false;
1215
1216 cond = as_a <gcond *> (last_stmt (cond_bb));
1217 cmp = gimple_cond_code (cond);
1218
1219 /* This transformation is only valid for order comparisons. Record which
1220 operand is smaller/larger if the result of the comparison is true. */
1221 alt_smaller = NULL_TREE;
1222 alt_larger = NULL_TREE;
1223 if (cmp == LT_EXPR || cmp == LE_EXPR)
1224 {
1225 smaller = gimple_cond_lhs (cond);
1226 larger = gimple_cond_rhs (cond);
1227 /* If we have smaller < CST it is equivalent to smaller <= CST-1.
1228 Likewise smaller <= CST is equivalent to smaller < CST+1. */
1229 if (TREE_CODE (larger) == INTEGER_CST)
1230 {
1231 if (cmp == LT_EXPR)
1232 {
1233 bool overflow;
1234 wide_int alt = wi::sub (wi::to_wide (larger), 1,
1235 TYPE_SIGN (TREE_TYPE (larger)),
1236 &overflow);
1237 if (! overflow)
1238 alt_larger = wide_int_to_tree (TREE_TYPE (larger), alt);
1239 }
1240 else
1241 {
1242 bool overflow;
1243 wide_int alt = wi::add (wi::to_wide (larger), 1,
1244 TYPE_SIGN (TREE_TYPE (larger)),
1245 &overflow);
1246 if (! overflow)
1247 alt_larger = wide_int_to_tree (TREE_TYPE (larger), alt);
1248 }
1249 }
1250 }
1251 else if (cmp == GT_EXPR || cmp == GE_EXPR)
1252 {
1253 smaller = gimple_cond_rhs (cond);
1254 larger = gimple_cond_lhs (cond);
1255 /* If we have larger > CST it is equivalent to larger >= CST+1.
1256 Likewise larger >= CST is equivalent to larger > CST-1. */
1257 if (TREE_CODE (smaller) == INTEGER_CST)
1258 {
1259 if (cmp == GT_EXPR)
1260 {
1261 bool overflow;
1262 wide_int alt = wi::add (wi::to_wide (smaller), 1,
1263 TYPE_SIGN (TREE_TYPE (smaller)),
1264 &overflow);
1265 if (! overflow)
1266 alt_smaller = wide_int_to_tree (TREE_TYPE (smaller), alt);
1267 }
1268 else
1269 {
1270 bool overflow;
1271 wide_int alt = wi::sub (wi::to_wide (smaller), 1,
1272 TYPE_SIGN (TREE_TYPE (smaller)),
1273 &overflow);
1274 if (! overflow)
1275 alt_smaller = wide_int_to_tree (TREE_TYPE (smaller), alt);
1276 }
1277 }
1278 }
1279 else
1280 return false;
1281
1282 /* We need to know which is the true edge and which is the false
1283 edge so that we know if have abs or negative abs. */
1284 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1285
1286 /* Forward the edges over the middle basic block. */
1287 if (true_edge->dest == middle_bb)
1288 true_edge = EDGE_SUCC (true_edge->dest, 0);
1289 if (false_edge->dest == middle_bb)
1290 false_edge = EDGE_SUCC (false_edge->dest, 0);
1291
1292 if (true_edge == e0)
1293 {
1294 gcc_assert (false_edge == e1);
1295 arg_true = arg0;
1296 arg_false = arg1;
1297 }
1298 else
1299 {
1300 gcc_assert (false_edge == e0);
1301 gcc_assert (true_edge == e1);
1302 arg_true = arg1;
1303 arg_false = arg0;
1304 }
1305
1306 if (empty_block_p (middle_bb))
1307 {
1308 if ((operand_equal_for_phi_arg_p (arg_true, smaller)
1309 || (alt_smaller
1310 && operand_equal_for_phi_arg_p (arg_true, alt_smaller)))
1311 && (operand_equal_for_phi_arg_p (arg_false, larger)
1312 || (alt_larger
1313 && operand_equal_for_phi_arg_p (arg_true, alt_larger))))
1314 {
1315 /* Case
1316
1317 if (smaller < larger)
1318 rslt = smaller;
1319 else
1320 rslt = larger; */
1321 minmax = MIN_EXPR;
1322 }
1323 else if ((operand_equal_for_phi_arg_p (arg_false, smaller)
1324 || (alt_smaller
1325 && operand_equal_for_phi_arg_p (arg_false, alt_smaller)))
1326 && (operand_equal_for_phi_arg_p (arg_true, larger)
1327 || (alt_larger
1328 && operand_equal_for_phi_arg_p (arg_true, alt_larger))))
1329 minmax = MAX_EXPR;
1330 else
1331 return false;
1332 }
1333 else
1334 {
1335 /* Recognize the following case, assuming d <= u:
1336
1337 if (a <= u)
1338 b = MAX (a, d);
1339 x = PHI <b, u>
1340
1341 This is equivalent to
1342
1343 b = MAX (a, d);
1344 x = MIN (b, u); */
1345
1346 gimple *assign = last_and_only_stmt (middle_bb);
1347 tree lhs, op0, op1, bound;
1348
1349 if (!assign
1350 || gimple_code (assign) != GIMPLE_ASSIGN)
1351 return false;
1352
1353 lhs = gimple_assign_lhs (assign);
1354 ass_code = gimple_assign_rhs_code (assign);
1355 if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
1356 return false;
1357 op0 = gimple_assign_rhs1 (assign);
1358 op1 = gimple_assign_rhs2 (assign);
1359
1360 if (true_edge->src == middle_bb)
1361 {
1362 /* We got here if the condition is true, i.e., SMALLER < LARGER. */
1363 if (!operand_equal_for_phi_arg_p (lhs, arg_true))
1364 return false;
1365
1366 if (operand_equal_for_phi_arg_p (arg_false, larger)
1367 || (alt_larger
1368 && operand_equal_for_phi_arg_p (arg_false, alt_larger)))
1369 {
1370 /* Case
1371
1372 if (smaller < larger)
1373 {
1374 r' = MAX_EXPR (smaller, bound)
1375 }
1376 r = PHI <r', larger> --> to be turned to MIN_EXPR. */
1377 if (ass_code != MAX_EXPR)
1378 return false;
1379
1380 minmax = MIN_EXPR;
1381 if (operand_equal_for_phi_arg_p (op0, smaller)
1382 || (alt_smaller
1383 && operand_equal_for_phi_arg_p (op0, alt_smaller)))
1384 bound = op1;
1385 else if (operand_equal_for_phi_arg_p (op1, smaller)
1386 || (alt_smaller
1387 && operand_equal_for_phi_arg_p (op1, alt_smaller)))
1388 bound = op0;
1389 else
1390 return false;
1391
1392 /* We need BOUND <= LARGER. */
1393 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
1394 bound, larger)))
1395 return false;
1396 }
1397 else if (operand_equal_for_phi_arg_p (arg_false, smaller)
1398 || (alt_smaller
1399 && operand_equal_for_phi_arg_p (arg_false, alt_smaller)))
1400 {
1401 /* Case
1402
1403 if (smaller < larger)
1404 {
1405 r' = MIN_EXPR (larger, bound)
1406 }
1407 r = PHI <r', smaller> --> to be turned to MAX_EXPR. */
1408 if (ass_code != MIN_EXPR)
1409 return false;
1410
1411 minmax = MAX_EXPR;
1412 if (operand_equal_for_phi_arg_p (op0, larger)
1413 || (alt_larger
1414 && operand_equal_for_phi_arg_p (op0, alt_larger)))
1415 bound = op1;
1416 else if (operand_equal_for_phi_arg_p (op1, larger)
1417 || (alt_larger
1418 && operand_equal_for_phi_arg_p (op1, alt_larger)))
1419 bound = op0;
1420 else
1421 return false;
1422
1423 /* We need BOUND >= SMALLER. */
1424 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
1425 bound, smaller)))
1426 return false;
1427 }
1428 else
1429 return false;
1430 }
1431 else
1432 {
1433 /* We got here if the condition is false, i.e., SMALLER > LARGER. */
1434 if (!operand_equal_for_phi_arg_p (lhs, arg_false))
1435 return false;
1436
1437 if (operand_equal_for_phi_arg_p (arg_true, larger)
1438 || (alt_larger
1439 && operand_equal_for_phi_arg_p (arg_true, alt_larger)))
1440 {
1441 /* Case
1442
1443 if (smaller > larger)
1444 {
1445 r' = MIN_EXPR (smaller, bound)
1446 }
1447 r = PHI <r', larger> --> to be turned to MAX_EXPR. */
1448 if (ass_code != MIN_EXPR)
1449 return false;
1450
1451 minmax = MAX_EXPR;
1452 if (operand_equal_for_phi_arg_p (op0, smaller)
1453 || (alt_smaller
1454 && operand_equal_for_phi_arg_p (op0, alt_smaller)))
1455 bound = op1;
1456 else if (operand_equal_for_phi_arg_p (op1, smaller)
1457 || (alt_smaller
1458 && operand_equal_for_phi_arg_p (op1, alt_smaller)))
1459 bound = op0;
1460 else
1461 return false;
1462
1463 /* We need BOUND >= LARGER. */
1464 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
1465 bound, larger)))
1466 return false;
1467 }
1468 else if (operand_equal_for_phi_arg_p (arg_true, smaller)
1469 || (alt_smaller
1470 && operand_equal_for_phi_arg_p (arg_true, alt_smaller)))
1471 {
1472 /* Case
1473
1474 if (smaller > larger)
1475 {
1476 r' = MAX_EXPR (larger, bound)
1477 }
1478 r = PHI <r', smaller> --> to be turned to MIN_EXPR. */
1479 if (ass_code != MAX_EXPR)
1480 return false;
1481
1482 minmax = MIN_EXPR;
1483 if (operand_equal_for_phi_arg_p (op0, larger))
1484 bound = op1;
1485 else if (operand_equal_for_phi_arg_p (op1, larger))
1486 bound = op0;
1487 else
1488 return false;
1489
1490 /* We need BOUND <= SMALLER. */
1491 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
1492 bound, smaller)))
1493 return false;
1494 }
1495 else
1496 return false;
1497 }
1498
1499 /* Move the statement from the middle block. */
1500 gsi = gsi_last_bb (cond_bb);
1501 gsi_from = gsi_last_nondebug_bb (middle_bb);
1502 reset_flow_sensitive_info (SINGLE_SSA_TREE_OPERAND (gsi_stmt (gsi_from),
1503 SSA_OP_DEF));
1504 gsi_move_before (&gsi_from, &gsi);
1505 }
1506
1507 /* Create an SSA var to hold the min/max result. If we're the only
1508 things setting the target PHI, then we can clone the PHI
1509 variable. Otherwise we must create a new one. */
1510 result = PHI_RESULT (phi);
1511 if (EDGE_COUNT (gimple_bb (phi)->preds) == 2)
1512 result = duplicate_ssa_name (result, NULL);
1513 else
1514 result = make_ssa_name (TREE_TYPE (result));
1515
1516 /* Emit the statement to compute min/max. */
1517 new_stmt = gimple_build_assign (result, minmax, arg0, arg1);
1518 gsi = gsi_last_bb (cond_bb);
1519 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
1520
1521 replace_phi_edge_with_variable (cond_bb, e1, phi, result);
1522
1523 return true;
1524 }
1525
1526 /* The function absolute_replacement does the main work of doing the absolute
1527 replacement. Return true if the replacement is done. Otherwise return
1528 false.
1529 bb is the basic block where the replacement is going to be done on. arg0
1530 is argument 0 from the phi. Likewise for arg1. */
1531
1532 static bool
abs_replacement(basic_block cond_bb,basic_block middle_bb,edge e0 ATTRIBUTE_UNUSED,edge e1,gimple * phi,tree arg0,tree arg1)1533 abs_replacement (basic_block cond_bb, basic_block middle_bb,
1534 edge e0 ATTRIBUTE_UNUSED, edge e1,
1535 gimple *phi, tree arg0, tree arg1)
1536 {
1537 tree result;
1538 gassign *new_stmt;
1539 gimple *cond;
1540 gimple_stmt_iterator gsi;
1541 edge true_edge, false_edge;
1542 gimple *assign;
1543 edge e;
1544 tree rhs, lhs;
1545 bool negate;
1546 enum tree_code cond_code;
1547
1548 /* If the type says honor signed zeros we cannot do this
1549 optimization. */
1550 if (HONOR_SIGNED_ZEROS (arg1))
1551 return false;
1552
1553 /* OTHER_BLOCK must have only one executable statement which must have the
1554 form arg0 = -arg1 or arg1 = -arg0. */
1555
1556 assign = last_and_only_stmt (middle_bb);
1557 /* If we did not find the proper negation assignment, then we can not
1558 optimize. */
1559 if (assign == NULL)
1560 return false;
1561
1562 /* If we got here, then we have found the only executable statement
1563 in OTHER_BLOCK. If it is anything other than arg = -arg1 or
1564 arg1 = -arg0, then we can not optimize. */
1565 if (gimple_code (assign) != GIMPLE_ASSIGN)
1566 return false;
1567
1568 lhs = gimple_assign_lhs (assign);
1569
1570 if (gimple_assign_rhs_code (assign) != NEGATE_EXPR)
1571 return false;
1572
1573 rhs = gimple_assign_rhs1 (assign);
1574
1575 /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */
1576 if (!(lhs == arg0 && rhs == arg1)
1577 && !(lhs == arg1 && rhs == arg0))
1578 return false;
1579
1580 cond = last_stmt (cond_bb);
1581 result = PHI_RESULT (phi);
1582
1583 /* Only relationals comparing arg[01] against zero are interesting. */
1584 cond_code = gimple_cond_code (cond);
1585 if (cond_code != GT_EXPR && cond_code != GE_EXPR
1586 && cond_code != LT_EXPR && cond_code != LE_EXPR)
1587 return false;
1588
1589 /* Make sure the conditional is arg[01] OP y. */
1590 if (gimple_cond_lhs (cond) != rhs)
1591 return false;
1592
1593 if (FLOAT_TYPE_P (TREE_TYPE (gimple_cond_rhs (cond)))
1594 ? real_zerop (gimple_cond_rhs (cond))
1595 : integer_zerop (gimple_cond_rhs (cond)))
1596 ;
1597 else
1598 return false;
1599
1600 /* We need to know which is the true edge and which is the false
1601 edge so that we know if have abs or negative abs. */
1602 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1603
1604 /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
1605 will need to negate the result. Similarly for LT_EXPR/LE_EXPR if
1606 the false edge goes to OTHER_BLOCK. */
1607 if (cond_code == GT_EXPR || cond_code == GE_EXPR)
1608 e = true_edge;
1609 else
1610 e = false_edge;
1611
1612 if (e->dest == middle_bb)
1613 negate = true;
1614 else
1615 negate = false;
1616
1617 /* If the code negates only iff positive then make sure to not
1618 introduce undefined behavior when negating or computing the absolute.
1619 ??? We could use range info if present to check for arg1 == INT_MIN. */
1620 if (negate
1621 && (ANY_INTEGRAL_TYPE_P (TREE_TYPE (arg1))
1622 && ! TYPE_OVERFLOW_WRAPS (TREE_TYPE (arg1))))
1623 return false;
1624
1625 result = duplicate_ssa_name (result, NULL);
1626
1627 if (negate)
1628 lhs = make_ssa_name (TREE_TYPE (result));
1629 else
1630 lhs = result;
1631
1632 /* Build the modify expression with abs expression. */
1633 new_stmt = gimple_build_assign (lhs, ABS_EXPR, rhs);
1634
1635 gsi = gsi_last_bb (cond_bb);
1636 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
1637
1638 if (negate)
1639 {
1640 /* Get the right GSI. We want to insert after the recently
1641 added ABS_EXPR statement (which we know is the first statement
1642 in the block. */
1643 new_stmt = gimple_build_assign (result, NEGATE_EXPR, lhs);
1644
1645 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
1646 }
1647
1648 replace_phi_edge_with_variable (cond_bb, e1, phi, result);
1649
1650 /* Note that we optimized this PHI. */
1651 return true;
1652 }
1653
1654 /* Auxiliary functions to determine the set of memory accesses which
1655 can't trap because they are preceded by accesses to the same memory
1656 portion. We do that for MEM_REFs, so we only need to track
1657 the SSA_NAME of the pointer indirectly referenced. The algorithm
1658 simply is a walk over all instructions in dominator order. When
1659 we see an MEM_REF we determine if we've already seen a same
1660 ref anywhere up to the root of the dominator tree. If we do the
1661 current access can't trap. If we don't see any dominating access
1662 the current access might trap, but might also make later accesses
1663 non-trapping, so we remember it. We need to be careful with loads
1664 or stores, for instance a load might not trap, while a store would,
1665 so if we see a dominating read access this doesn't mean that a later
1666 write access would not trap. Hence we also need to differentiate the
1667 type of access(es) seen.
1668
1669 ??? We currently are very conservative and assume that a load might
1670 trap even if a store doesn't (write-only memory). This probably is
1671 overly conservative. */
1672
1673 /* A hash-table of SSA_NAMEs, and in which basic block an MEM_REF
1674 through it was seen, which would constitute a no-trap region for
1675 same accesses. */
1676 struct name_to_bb
1677 {
1678 unsigned int ssa_name_ver;
1679 unsigned int phase;
1680 bool store;
1681 HOST_WIDE_INT offset, size;
1682 basic_block bb;
1683 };
1684
1685 /* Hashtable helpers. */
1686
1687 struct ssa_names_hasher : free_ptr_hash <name_to_bb>
1688 {
1689 static inline hashval_t hash (const name_to_bb *);
1690 static inline bool equal (const name_to_bb *, const name_to_bb *);
1691 };
1692
1693 /* Used for quick clearing of the hash-table when we see calls.
1694 Hash entries with phase < nt_call_phase are invalid. */
1695 static unsigned int nt_call_phase;
1696
1697 /* The hash function. */
1698
1699 inline hashval_t
hash(const name_to_bb * n)1700 ssa_names_hasher::hash (const name_to_bb *n)
1701 {
1702 return n->ssa_name_ver ^ (((hashval_t) n->store) << 31)
1703 ^ (n->offset << 6) ^ (n->size << 3);
1704 }
1705
1706 /* The equality function of *P1 and *P2. */
1707
1708 inline bool
equal(const name_to_bb * n1,const name_to_bb * n2)1709 ssa_names_hasher::equal (const name_to_bb *n1, const name_to_bb *n2)
1710 {
1711 return n1->ssa_name_ver == n2->ssa_name_ver
1712 && n1->store == n2->store
1713 && n1->offset == n2->offset
1714 && n1->size == n2->size;
1715 }
1716
1717 class nontrapping_dom_walker : public dom_walker
1718 {
1719 public:
nontrapping_dom_walker(cdi_direction direction,hash_set<tree> * ps)1720 nontrapping_dom_walker (cdi_direction direction, hash_set<tree> *ps)
1721 : dom_walker (direction), m_nontrapping (ps), m_seen_ssa_names (128) {}
1722
1723 virtual edge before_dom_children (basic_block);
1724 virtual void after_dom_children (basic_block);
1725
1726 private:
1727
1728 /* We see the expression EXP in basic block BB. If it's an interesting
1729 expression (an MEM_REF through an SSA_NAME) possibly insert the
1730 expression into the set NONTRAP or the hash table of seen expressions.
1731 STORE is true if this expression is on the LHS, otherwise it's on
1732 the RHS. */
1733 void add_or_mark_expr (basic_block, tree, bool);
1734
1735 hash_set<tree> *m_nontrapping;
1736
1737 /* The hash table for remembering what we've seen. */
1738 hash_table<ssa_names_hasher> m_seen_ssa_names;
1739 };
1740
1741 /* Called by walk_dominator_tree, when entering the block BB. */
1742 edge
before_dom_children(basic_block bb)1743 nontrapping_dom_walker::before_dom_children (basic_block bb)
1744 {
1745 edge e;
1746 edge_iterator ei;
1747 gimple_stmt_iterator gsi;
1748
1749 /* If we haven't seen all our predecessors, clear the hash-table. */
1750 FOR_EACH_EDGE (e, ei, bb->preds)
1751 if ((((size_t)e->src->aux) & 2) == 0)
1752 {
1753 nt_call_phase++;
1754 break;
1755 }
1756
1757 /* Mark this BB as being on the path to dominator root and as visited. */
1758 bb->aux = (void*)(1 | 2);
1759
1760 /* And walk the statements in order. */
1761 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1762 {
1763 gimple *stmt = gsi_stmt (gsi);
1764
1765 if ((gimple_code (stmt) == GIMPLE_ASM && gimple_vdef (stmt))
1766 || (is_gimple_call (stmt)
1767 && (!nonfreeing_call_p (stmt) || !nonbarrier_call_p (stmt))))
1768 nt_call_phase++;
1769 else if (gimple_assign_single_p (stmt) && !gimple_has_volatile_ops (stmt))
1770 {
1771 add_or_mark_expr (bb, gimple_assign_lhs (stmt), true);
1772 add_or_mark_expr (bb, gimple_assign_rhs1 (stmt), false);
1773 }
1774 }
1775 return NULL;
1776 }
1777
1778 /* Called by walk_dominator_tree, when basic block BB is exited. */
1779 void
after_dom_children(basic_block bb)1780 nontrapping_dom_walker::after_dom_children (basic_block bb)
1781 {
1782 /* This BB isn't on the path to dominator root anymore. */
1783 bb->aux = (void*)2;
1784 }
1785
1786 /* We see the expression EXP in basic block BB. If it's an interesting
1787 expression (an MEM_REF through an SSA_NAME) possibly insert the
1788 expression into the set NONTRAP or the hash table of seen expressions.
1789 STORE is true if this expression is on the LHS, otherwise it's on
1790 the RHS. */
1791 void
add_or_mark_expr(basic_block bb,tree exp,bool store)1792 nontrapping_dom_walker::add_or_mark_expr (basic_block bb, tree exp, bool store)
1793 {
1794 HOST_WIDE_INT size;
1795
1796 if (TREE_CODE (exp) == MEM_REF
1797 && TREE_CODE (TREE_OPERAND (exp, 0)) == SSA_NAME
1798 && tree_fits_shwi_p (TREE_OPERAND (exp, 1))
1799 && (size = int_size_in_bytes (TREE_TYPE (exp))) > 0)
1800 {
1801 tree name = TREE_OPERAND (exp, 0);
1802 struct name_to_bb map;
1803 name_to_bb **slot;
1804 struct name_to_bb *n2bb;
1805 basic_block found_bb = 0;
1806
1807 /* Try to find the last seen MEM_REF through the same
1808 SSA_NAME, which can trap. */
1809 map.ssa_name_ver = SSA_NAME_VERSION (name);
1810 map.phase = 0;
1811 map.bb = 0;
1812 map.store = store;
1813 map.offset = tree_to_shwi (TREE_OPERAND (exp, 1));
1814 map.size = size;
1815
1816 slot = m_seen_ssa_names.find_slot (&map, INSERT);
1817 n2bb = *slot;
1818 if (n2bb && n2bb->phase >= nt_call_phase)
1819 found_bb = n2bb->bb;
1820
1821 /* If we've found a trapping MEM_REF, _and_ it dominates EXP
1822 (it's in a basic block on the path from us to the dominator root)
1823 then we can't trap. */
1824 if (found_bb && (((size_t)found_bb->aux) & 1) == 1)
1825 {
1826 m_nontrapping->add (exp);
1827 }
1828 else
1829 {
1830 /* EXP might trap, so insert it into the hash table. */
1831 if (n2bb)
1832 {
1833 n2bb->phase = nt_call_phase;
1834 n2bb->bb = bb;
1835 }
1836 else
1837 {
1838 n2bb = XNEW (struct name_to_bb);
1839 n2bb->ssa_name_ver = SSA_NAME_VERSION (name);
1840 n2bb->phase = nt_call_phase;
1841 n2bb->bb = bb;
1842 n2bb->store = store;
1843 n2bb->offset = map.offset;
1844 n2bb->size = size;
1845 *slot = n2bb;
1846 }
1847 }
1848 }
1849 }
1850
1851 /* This is the entry point of gathering non trapping memory accesses.
1852 It will do a dominator walk over the whole function, and it will
1853 make use of the bb->aux pointers. It returns a set of trees
1854 (the MEM_REFs itself) which can't trap. */
1855 static hash_set<tree> *
get_non_trapping(void)1856 get_non_trapping (void)
1857 {
1858 nt_call_phase = 0;
1859 hash_set<tree> *nontrap = new hash_set<tree>;
1860 /* We're going to do a dominator walk, so ensure that we have
1861 dominance information. */
1862 calculate_dominance_info (CDI_DOMINATORS);
1863
1864 nontrapping_dom_walker (CDI_DOMINATORS, nontrap)
1865 .walk (cfun->cfg->x_entry_block_ptr);
1866
1867 clear_aux_for_blocks ();
1868 return nontrap;
1869 }
1870
1871 /* Do the main work of conditional store replacement. We already know
1872 that the recognized pattern looks like so:
1873
1874 split:
1875 if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
1876 MIDDLE_BB:
1877 something
1878 fallthrough (edge E0)
1879 JOIN_BB:
1880 some more
1881
1882 We check that MIDDLE_BB contains only one store, that that store
1883 doesn't trap (not via NOTRAP, but via checking if an access to the same
1884 memory location dominates us) and that the store has a "simple" RHS. */
1885
1886 static bool
cond_store_replacement(basic_block middle_bb,basic_block join_bb,edge e0,edge e1,hash_set<tree> * nontrap)1887 cond_store_replacement (basic_block middle_bb, basic_block join_bb,
1888 edge e0, edge e1, hash_set<tree> *nontrap)
1889 {
1890 gimple *assign = last_and_only_stmt (middle_bb);
1891 tree lhs, rhs, name, name2;
1892 gphi *newphi;
1893 gassign *new_stmt;
1894 gimple_stmt_iterator gsi;
1895 source_location locus;
1896
1897 /* Check if middle_bb contains of only one store. */
1898 if (!assign
1899 || !gimple_assign_single_p (assign)
1900 || gimple_has_volatile_ops (assign))
1901 return false;
1902
1903 /* And no PHI nodes so all uses in the single stmt are also
1904 available where we insert to. */
1905 if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
1906 return false;
1907
1908 locus = gimple_location (assign);
1909 lhs = gimple_assign_lhs (assign);
1910 rhs = gimple_assign_rhs1 (assign);
1911 if (TREE_CODE (lhs) != MEM_REF
1912 || TREE_CODE (TREE_OPERAND (lhs, 0)) != SSA_NAME
1913 || !is_gimple_reg_type (TREE_TYPE (lhs)))
1914 return false;
1915
1916 /* Prove that we can move the store down. We could also check
1917 TREE_THIS_NOTRAP here, but in that case we also could move stores,
1918 whose value is not available readily, which we want to avoid. */
1919 if (!nontrap->contains (lhs))
1920 return false;
1921
1922 /* Now we've checked the constraints, so do the transformation:
1923 1) Remove the single store. */
1924 gsi = gsi_for_stmt (assign);
1925 unlink_stmt_vdef (assign);
1926 gsi_remove (&gsi, true);
1927 release_defs (assign);
1928
1929 /* Make both store and load use alias-set zero as we have to
1930 deal with the case of the store being a conditional change
1931 of the dynamic type. */
1932 lhs = unshare_expr (lhs);
1933 tree *basep = &lhs;
1934 while (handled_component_p (*basep))
1935 basep = &TREE_OPERAND (*basep, 0);
1936 if (TREE_CODE (*basep) == MEM_REF
1937 || TREE_CODE (*basep) == TARGET_MEM_REF)
1938 TREE_OPERAND (*basep, 1)
1939 = fold_convert (ptr_type_node, TREE_OPERAND (*basep, 1));
1940 else
1941 *basep = build2 (MEM_REF, TREE_TYPE (*basep),
1942 build_fold_addr_expr (*basep),
1943 build_zero_cst (ptr_type_node));
1944
1945 /* 2) Insert a load from the memory of the store to the temporary
1946 on the edge which did not contain the store. */
1947 name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
1948 new_stmt = gimple_build_assign (name, lhs);
1949 gimple_set_location (new_stmt, locus);
1950 gsi_insert_on_edge (e1, new_stmt);
1951
1952 /* 3) Create a PHI node at the join block, with one argument
1953 holding the old RHS, and the other holding the temporary
1954 where we stored the old memory contents. */
1955 name2 = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
1956 newphi = create_phi_node (name2, join_bb);
1957 add_phi_arg (newphi, rhs, e0, locus);
1958 add_phi_arg (newphi, name, e1, locus);
1959
1960 lhs = unshare_expr (lhs);
1961 new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
1962
1963 /* 4) Insert that PHI node. */
1964 gsi = gsi_after_labels (join_bb);
1965 if (gsi_end_p (gsi))
1966 {
1967 gsi = gsi_last_bb (join_bb);
1968 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
1969 }
1970 else
1971 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
1972
1973 return true;
1974 }
1975
1976 /* Do the main work of conditional store replacement. */
1977
1978 static bool
cond_if_else_store_replacement_1(basic_block then_bb,basic_block else_bb,basic_block join_bb,gimple * then_assign,gimple * else_assign)1979 cond_if_else_store_replacement_1 (basic_block then_bb, basic_block else_bb,
1980 basic_block join_bb, gimple *then_assign,
1981 gimple *else_assign)
1982 {
1983 tree lhs_base, lhs, then_rhs, else_rhs, name;
1984 source_location then_locus, else_locus;
1985 gimple_stmt_iterator gsi;
1986 gphi *newphi;
1987 gassign *new_stmt;
1988
1989 if (then_assign == NULL
1990 || !gimple_assign_single_p (then_assign)
1991 || gimple_clobber_p (then_assign)
1992 || gimple_has_volatile_ops (then_assign)
1993 || else_assign == NULL
1994 || !gimple_assign_single_p (else_assign)
1995 || gimple_clobber_p (else_assign)
1996 || gimple_has_volatile_ops (else_assign))
1997 return false;
1998
1999 lhs = gimple_assign_lhs (then_assign);
2000 if (!is_gimple_reg_type (TREE_TYPE (lhs))
2001 || !operand_equal_p (lhs, gimple_assign_lhs (else_assign), 0))
2002 return false;
2003
2004 lhs_base = get_base_address (lhs);
2005 if (lhs_base == NULL_TREE
2006 || (!DECL_P (lhs_base) && TREE_CODE (lhs_base) != MEM_REF))
2007 return false;
2008
2009 then_rhs = gimple_assign_rhs1 (then_assign);
2010 else_rhs = gimple_assign_rhs1 (else_assign);
2011 then_locus = gimple_location (then_assign);
2012 else_locus = gimple_location (else_assign);
2013
2014 /* Now we've checked the constraints, so do the transformation:
2015 1) Remove the stores. */
2016 gsi = gsi_for_stmt (then_assign);
2017 unlink_stmt_vdef (then_assign);
2018 gsi_remove (&gsi, true);
2019 release_defs (then_assign);
2020
2021 gsi = gsi_for_stmt (else_assign);
2022 unlink_stmt_vdef (else_assign);
2023 gsi_remove (&gsi, true);
2024 release_defs (else_assign);
2025
2026 /* 2) Create a PHI node at the join block, with one argument
2027 holding the old RHS, and the other holding the temporary
2028 where we stored the old memory contents. */
2029 name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
2030 newphi = create_phi_node (name, join_bb);
2031 add_phi_arg (newphi, then_rhs, EDGE_SUCC (then_bb, 0), then_locus);
2032 add_phi_arg (newphi, else_rhs, EDGE_SUCC (else_bb, 0), else_locus);
2033
2034 new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
2035
2036 /* 3) Insert that PHI node. */
2037 gsi = gsi_after_labels (join_bb);
2038 if (gsi_end_p (gsi))
2039 {
2040 gsi = gsi_last_bb (join_bb);
2041 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
2042 }
2043 else
2044 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
2045
2046 return true;
2047 }
2048
2049 /* Return the single store in BB with VDEF or NULL if there are
2050 other stores in the BB or loads following the store. */
2051
2052 static gimple *
single_trailing_store_in_bb(basic_block bb,tree vdef)2053 single_trailing_store_in_bb (basic_block bb, tree vdef)
2054 {
2055 if (SSA_NAME_IS_DEFAULT_DEF (vdef))
2056 return NULL;
2057 gimple *store = SSA_NAME_DEF_STMT (vdef);
2058 if (gimple_bb (store) != bb
2059 || gimple_code (store) == GIMPLE_PHI)
2060 return NULL;
2061
2062 /* Verify there is no other store in this BB. */
2063 if (!SSA_NAME_IS_DEFAULT_DEF (gimple_vuse (store))
2064 && gimple_bb (SSA_NAME_DEF_STMT (gimple_vuse (store))) == bb
2065 && gimple_code (SSA_NAME_DEF_STMT (gimple_vuse (store))) != GIMPLE_PHI)
2066 return NULL;
2067
2068 /* Verify there is no load or store after the store. */
2069 use_operand_p use_p;
2070 imm_use_iterator imm_iter;
2071 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_vdef (store))
2072 if (USE_STMT (use_p) != store
2073 && gimple_bb (USE_STMT (use_p)) == bb)
2074 return NULL;
2075
2076 return store;
2077 }
2078
2079 /* Conditional store replacement. We already know
2080 that the recognized pattern looks like so:
2081
2082 split:
2083 if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
2084 THEN_BB:
2085 ...
2086 X = Y;
2087 ...
2088 goto JOIN_BB;
2089 ELSE_BB:
2090 ...
2091 X = Z;
2092 ...
2093 fallthrough (edge E0)
2094 JOIN_BB:
2095 some more
2096
2097 We check that it is safe to sink the store to JOIN_BB by verifying that
2098 there are no read-after-write or write-after-write dependencies in
2099 THEN_BB and ELSE_BB. */
2100
2101 static bool
cond_if_else_store_replacement(basic_block then_bb,basic_block else_bb,basic_block join_bb)2102 cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb,
2103 basic_block join_bb)
2104 {
2105 vec<data_reference_p> then_datarefs, else_datarefs;
2106 vec<ddr_p> then_ddrs, else_ddrs;
2107 gimple *then_store, *else_store;
2108 bool found, ok = false, res;
2109 struct data_dependence_relation *ddr;
2110 data_reference_p then_dr, else_dr;
2111 int i, j;
2112 tree then_lhs, else_lhs;
2113 basic_block blocks[3];
2114
2115 /* Handle the case with single store in THEN_BB and ELSE_BB. That is
2116 cheap enough to always handle as it allows us to elide dependence
2117 checking. */
2118 gphi *vphi = NULL;
2119 for (gphi_iterator si = gsi_start_phis (join_bb); !gsi_end_p (si);
2120 gsi_next (&si))
2121 if (virtual_operand_p (gimple_phi_result (si.phi ())))
2122 {
2123 vphi = si.phi ();
2124 break;
2125 }
2126 if (!vphi)
2127 return false;
2128 tree then_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (then_bb));
2129 tree else_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (else_bb));
2130 gimple *then_assign = single_trailing_store_in_bb (then_bb, then_vdef);
2131 if (then_assign)
2132 {
2133 gimple *else_assign = single_trailing_store_in_bb (else_bb, else_vdef);
2134 if (else_assign)
2135 return cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
2136 then_assign, else_assign);
2137 }
2138
2139 if (MAX_STORES_TO_SINK == 0)
2140 return false;
2141
2142 /* Find data references. */
2143 then_datarefs.create (1);
2144 else_datarefs.create (1);
2145 if ((find_data_references_in_bb (NULL, then_bb, &then_datarefs)
2146 == chrec_dont_know)
2147 || !then_datarefs.length ()
2148 || (find_data_references_in_bb (NULL, else_bb, &else_datarefs)
2149 == chrec_dont_know)
2150 || !else_datarefs.length ())
2151 {
2152 free_data_refs (then_datarefs);
2153 free_data_refs (else_datarefs);
2154 return false;
2155 }
2156
2157 /* Find pairs of stores with equal LHS. */
2158 auto_vec<gimple *, 1> then_stores, else_stores;
2159 FOR_EACH_VEC_ELT (then_datarefs, i, then_dr)
2160 {
2161 if (DR_IS_READ (then_dr))
2162 continue;
2163
2164 then_store = DR_STMT (then_dr);
2165 then_lhs = gimple_get_lhs (then_store);
2166 if (then_lhs == NULL_TREE)
2167 continue;
2168 found = false;
2169
2170 FOR_EACH_VEC_ELT (else_datarefs, j, else_dr)
2171 {
2172 if (DR_IS_READ (else_dr))
2173 continue;
2174
2175 else_store = DR_STMT (else_dr);
2176 else_lhs = gimple_get_lhs (else_store);
2177 if (else_lhs == NULL_TREE)
2178 continue;
2179
2180 if (operand_equal_p (then_lhs, else_lhs, 0))
2181 {
2182 found = true;
2183 break;
2184 }
2185 }
2186
2187 if (!found)
2188 continue;
2189
2190 then_stores.safe_push (then_store);
2191 else_stores.safe_push (else_store);
2192 }
2193
2194 /* No pairs of stores found. */
2195 if (!then_stores.length ()
2196 || then_stores.length () > (unsigned) MAX_STORES_TO_SINK)
2197 {
2198 free_data_refs (then_datarefs);
2199 free_data_refs (else_datarefs);
2200 return false;
2201 }
2202
2203 /* Compute and check data dependencies in both basic blocks. */
2204 then_ddrs.create (1);
2205 else_ddrs.create (1);
2206 if (!compute_all_dependences (then_datarefs, &then_ddrs,
2207 vNULL, false)
2208 || !compute_all_dependences (else_datarefs, &else_ddrs,
2209 vNULL, false))
2210 {
2211 free_dependence_relations (then_ddrs);
2212 free_dependence_relations (else_ddrs);
2213 free_data_refs (then_datarefs);
2214 free_data_refs (else_datarefs);
2215 return false;
2216 }
2217 blocks[0] = then_bb;
2218 blocks[1] = else_bb;
2219 blocks[2] = join_bb;
2220 renumber_gimple_stmt_uids_in_blocks (blocks, 3);
2221
2222 /* Check that there are no read-after-write or write-after-write dependencies
2223 in THEN_BB. */
2224 FOR_EACH_VEC_ELT (then_ddrs, i, ddr)
2225 {
2226 struct data_reference *dra = DDR_A (ddr);
2227 struct data_reference *drb = DDR_B (ddr);
2228
2229 if (DDR_ARE_DEPENDENT (ddr) != chrec_known
2230 && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
2231 && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
2232 || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
2233 && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
2234 || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
2235 {
2236 free_dependence_relations (then_ddrs);
2237 free_dependence_relations (else_ddrs);
2238 free_data_refs (then_datarefs);
2239 free_data_refs (else_datarefs);
2240 return false;
2241 }
2242 }
2243
2244 /* Check that there are no read-after-write or write-after-write dependencies
2245 in ELSE_BB. */
2246 FOR_EACH_VEC_ELT (else_ddrs, i, ddr)
2247 {
2248 struct data_reference *dra = DDR_A (ddr);
2249 struct data_reference *drb = DDR_B (ddr);
2250
2251 if (DDR_ARE_DEPENDENT (ddr) != chrec_known
2252 && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
2253 && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
2254 || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
2255 && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
2256 || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
2257 {
2258 free_dependence_relations (then_ddrs);
2259 free_dependence_relations (else_ddrs);
2260 free_data_refs (then_datarefs);
2261 free_data_refs (else_datarefs);
2262 return false;
2263 }
2264 }
2265
2266 /* Sink stores with same LHS. */
2267 FOR_EACH_VEC_ELT (then_stores, i, then_store)
2268 {
2269 else_store = else_stores[i];
2270 res = cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
2271 then_store, else_store);
2272 ok = ok || res;
2273 }
2274
2275 free_dependence_relations (then_ddrs);
2276 free_dependence_relations (else_ddrs);
2277 free_data_refs (then_datarefs);
2278 free_data_refs (else_datarefs);
2279
2280 return ok;
2281 }
2282
2283 /* Return TRUE if STMT has a VUSE whose corresponding VDEF is in BB. */
2284
2285 static bool
local_mem_dependence(gimple * stmt,basic_block bb)2286 local_mem_dependence (gimple *stmt, basic_block bb)
2287 {
2288 tree vuse = gimple_vuse (stmt);
2289 gimple *def;
2290
2291 if (!vuse)
2292 return false;
2293
2294 def = SSA_NAME_DEF_STMT (vuse);
2295 return (def && gimple_bb (def) == bb);
2296 }
2297
2298 /* Given a "diamond" control-flow pattern where BB0 tests a condition,
2299 BB1 and BB2 are "then" and "else" blocks dependent on this test,
2300 and BB3 rejoins control flow following BB1 and BB2, look for
2301 opportunities to hoist loads as follows. If BB3 contains a PHI of
2302 two loads, one each occurring in BB1 and BB2, and the loads are
2303 provably of adjacent fields in the same structure, then move both
2304 loads into BB0. Of course this can only be done if there are no
2305 dependencies preventing such motion.
2306
2307 One of the hoisted loads will always be speculative, so the
2308 transformation is currently conservative:
2309
2310 - The fields must be strictly adjacent.
2311 - The two fields must occupy a single memory block that is
2312 guaranteed to not cross a page boundary.
2313
2314 The last is difficult to prove, as such memory blocks should be
2315 aligned on the minimum of the stack alignment boundary and the
2316 alignment guaranteed by heap allocation interfaces. Thus we rely
2317 on a parameter for the alignment value.
2318
2319 Provided a good value is used for the last case, the first
2320 restriction could possibly be relaxed. */
2321
2322 static void
hoist_adjacent_loads(basic_block bb0,basic_block bb1,basic_block bb2,basic_block bb3)2323 hoist_adjacent_loads (basic_block bb0, basic_block bb1,
2324 basic_block bb2, basic_block bb3)
2325 {
2326 int param_align = PARAM_VALUE (PARAM_L1_CACHE_LINE_SIZE);
2327 unsigned param_align_bits = (unsigned) (param_align * BITS_PER_UNIT);
2328 gphi_iterator gsi;
2329
2330 /* Walk the phis in bb3 looking for an opportunity. We are looking
2331 for phis of two SSA names, one each of which is defined in bb1 and
2332 bb2. */
2333 for (gsi = gsi_start_phis (bb3); !gsi_end_p (gsi); gsi_next (&gsi))
2334 {
2335 gphi *phi_stmt = gsi.phi ();
2336 gimple *def1, *def2;
2337 tree arg1, arg2, ref1, ref2, field1, field2;
2338 tree tree_offset1, tree_offset2, tree_size2, next;
2339 int offset1, offset2, size2;
2340 unsigned align1;
2341 gimple_stmt_iterator gsi2;
2342 basic_block bb_for_def1, bb_for_def2;
2343
2344 if (gimple_phi_num_args (phi_stmt) != 2
2345 || virtual_operand_p (gimple_phi_result (phi_stmt)))
2346 continue;
2347
2348 arg1 = gimple_phi_arg_def (phi_stmt, 0);
2349 arg2 = gimple_phi_arg_def (phi_stmt, 1);
2350
2351 if (TREE_CODE (arg1) != SSA_NAME
2352 || TREE_CODE (arg2) != SSA_NAME
2353 || SSA_NAME_IS_DEFAULT_DEF (arg1)
2354 || SSA_NAME_IS_DEFAULT_DEF (arg2))
2355 continue;
2356
2357 def1 = SSA_NAME_DEF_STMT (arg1);
2358 def2 = SSA_NAME_DEF_STMT (arg2);
2359
2360 if ((gimple_bb (def1) != bb1 || gimple_bb (def2) != bb2)
2361 && (gimple_bb (def2) != bb1 || gimple_bb (def1) != bb2))
2362 continue;
2363
2364 /* Check the mode of the arguments to be sure a conditional move
2365 can be generated for it. */
2366 if (optab_handler (movcc_optab, TYPE_MODE (TREE_TYPE (arg1)))
2367 == CODE_FOR_nothing)
2368 continue;
2369
2370 /* Both statements must be assignments whose RHS is a COMPONENT_REF. */
2371 if (!gimple_assign_single_p (def1)
2372 || !gimple_assign_single_p (def2)
2373 || gimple_has_volatile_ops (def1)
2374 || gimple_has_volatile_ops (def2))
2375 continue;
2376
2377 ref1 = gimple_assign_rhs1 (def1);
2378 ref2 = gimple_assign_rhs1 (def2);
2379
2380 if (TREE_CODE (ref1) != COMPONENT_REF
2381 || TREE_CODE (ref2) != COMPONENT_REF)
2382 continue;
2383
2384 /* The zeroth operand of the two component references must be
2385 identical. It is not sufficient to compare get_base_address of
2386 the two references, because this could allow for different
2387 elements of the same array in the two trees. It is not safe to
2388 assume that the existence of one array element implies the
2389 existence of a different one. */
2390 if (!operand_equal_p (TREE_OPERAND (ref1, 0), TREE_OPERAND (ref2, 0), 0))
2391 continue;
2392
2393 field1 = TREE_OPERAND (ref1, 1);
2394 field2 = TREE_OPERAND (ref2, 1);
2395
2396 /* Check for field adjacency, and ensure field1 comes first. */
2397 for (next = DECL_CHAIN (field1);
2398 next && TREE_CODE (next) != FIELD_DECL;
2399 next = DECL_CHAIN (next))
2400 ;
2401
2402 if (next != field2)
2403 {
2404 for (next = DECL_CHAIN (field2);
2405 next && TREE_CODE (next) != FIELD_DECL;
2406 next = DECL_CHAIN (next))
2407 ;
2408
2409 if (next != field1)
2410 continue;
2411
2412 std::swap (field1, field2);
2413 std::swap (def1, def2);
2414 }
2415
2416 bb_for_def1 = gimple_bb (def1);
2417 bb_for_def2 = gimple_bb (def2);
2418
2419 /* Check for proper alignment of the first field. */
2420 tree_offset1 = bit_position (field1);
2421 tree_offset2 = bit_position (field2);
2422 tree_size2 = DECL_SIZE (field2);
2423
2424 if (!tree_fits_uhwi_p (tree_offset1)
2425 || !tree_fits_uhwi_p (tree_offset2)
2426 || !tree_fits_uhwi_p (tree_size2))
2427 continue;
2428
2429 offset1 = tree_to_uhwi (tree_offset1);
2430 offset2 = tree_to_uhwi (tree_offset2);
2431 size2 = tree_to_uhwi (tree_size2);
2432 align1 = DECL_ALIGN (field1) % param_align_bits;
2433
2434 if (offset1 % BITS_PER_UNIT != 0)
2435 continue;
2436
2437 /* For profitability, the two field references should fit within
2438 a single cache line. */
2439 if (align1 + offset2 - offset1 + size2 > param_align_bits)
2440 continue;
2441
2442 /* The two expressions cannot be dependent upon vdefs defined
2443 in bb1/bb2. */
2444 if (local_mem_dependence (def1, bb_for_def1)
2445 || local_mem_dependence (def2, bb_for_def2))
2446 continue;
2447
2448 /* The conditions are satisfied; hoist the loads from bb1 and bb2 into
2449 bb0. We hoist the first one first so that a cache miss is handled
2450 efficiently regardless of hardware cache-fill policy. */
2451 gsi2 = gsi_for_stmt (def1);
2452 gsi_move_to_bb_end (&gsi2, bb0);
2453 gsi2 = gsi_for_stmt (def2);
2454 gsi_move_to_bb_end (&gsi2, bb0);
2455
2456 if (dump_file && (dump_flags & TDF_DETAILS))
2457 {
2458 fprintf (dump_file,
2459 "\nHoisting adjacent loads from %d and %d into %d: \n",
2460 bb_for_def1->index, bb_for_def2->index, bb0->index);
2461 print_gimple_stmt (dump_file, def1, 0, TDF_VOPS|TDF_MEMSYMS);
2462 print_gimple_stmt (dump_file, def2, 0, TDF_VOPS|TDF_MEMSYMS);
2463 }
2464 }
2465 }
2466
2467 /* Determine whether we should attempt to hoist adjacent loads out of
2468 diamond patterns in pass_phiopt. Always hoist loads if
2469 -fhoist-adjacent-loads is specified and the target machine has
2470 both a conditional move instruction and a defined cache line size. */
2471
2472 static bool
gate_hoist_loads(void)2473 gate_hoist_loads (void)
2474 {
2475 return (flag_hoist_adjacent_loads == 1
2476 && PARAM_VALUE (PARAM_L1_CACHE_LINE_SIZE)
2477 && HAVE_conditional_move);
2478 }
2479
2480 /* This pass tries to replaces an if-then-else block with an
2481 assignment. We have four kinds of transformations. Some of these
2482 transformations are also performed by the ifcvt RTL optimizer.
2483
2484 Conditional Replacement
2485 -----------------------
2486
2487 This transformation, implemented in conditional_replacement,
2488 replaces
2489
2490 bb0:
2491 if (cond) goto bb2; else goto bb1;
2492 bb1:
2493 bb2:
2494 x = PHI <0 (bb1), 1 (bb0), ...>;
2495
2496 with
2497
2498 bb0:
2499 x' = cond;
2500 goto bb2;
2501 bb2:
2502 x = PHI <x' (bb0), ...>;
2503
2504 We remove bb1 as it becomes unreachable. This occurs often due to
2505 gimplification of conditionals.
2506
2507 Value Replacement
2508 -----------------
2509
2510 This transformation, implemented in value_replacement, replaces
2511
2512 bb0:
2513 if (a != b) goto bb2; else goto bb1;
2514 bb1:
2515 bb2:
2516 x = PHI <a (bb1), b (bb0), ...>;
2517
2518 with
2519
2520 bb0:
2521 bb2:
2522 x = PHI <b (bb0), ...>;
2523
2524 This opportunity can sometimes occur as a result of other
2525 optimizations.
2526
2527
2528 Another case caught by value replacement looks like this:
2529
2530 bb0:
2531 t1 = a == CONST;
2532 t2 = b > c;
2533 t3 = t1 & t2;
2534 if (t3 != 0) goto bb1; else goto bb2;
2535 bb1:
2536 bb2:
2537 x = PHI (CONST, a)
2538
2539 Gets replaced with:
2540 bb0:
2541 bb2:
2542 t1 = a == CONST;
2543 t2 = b > c;
2544 t3 = t1 & t2;
2545 x = a;
2546
2547 ABS Replacement
2548 ---------------
2549
2550 This transformation, implemented in abs_replacement, replaces
2551
2552 bb0:
2553 if (a >= 0) goto bb2; else goto bb1;
2554 bb1:
2555 x = -a;
2556 bb2:
2557 x = PHI <x (bb1), a (bb0), ...>;
2558
2559 with
2560
2561 bb0:
2562 x' = ABS_EXPR< a >;
2563 bb2:
2564 x = PHI <x' (bb0), ...>;
2565
2566 MIN/MAX Replacement
2567 -------------------
2568
2569 This transformation, minmax_replacement replaces
2570
2571 bb0:
2572 if (a <= b) goto bb2; else goto bb1;
2573 bb1:
2574 bb2:
2575 x = PHI <b (bb1), a (bb0), ...>;
2576
2577 with
2578
2579 bb0:
2580 x' = MIN_EXPR (a, b)
2581 bb2:
2582 x = PHI <x' (bb0), ...>;
2583
2584 A similar transformation is done for MAX_EXPR.
2585
2586
2587 This pass also performs a fifth transformation of a slightly different
2588 flavor.
2589
2590 Factor conversion in COND_EXPR
2591 ------------------------------
2592
2593 This transformation factors the conversion out of COND_EXPR with
2594 factor_out_conditional_conversion.
2595
2596 For example:
2597 if (a <= CST) goto <bb 3>; else goto <bb 4>;
2598 <bb 3>:
2599 tmp = (int) a;
2600 <bb 4>:
2601 tmp = PHI <tmp, CST>
2602
2603 Into:
2604 if (a <= CST) goto <bb 3>; else goto <bb 4>;
2605 <bb 3>:
2606 <bb 4>:
2607 a = PHI <a, CST>
2608 tmp = (int) a;
2609
2610 Adjacent Load Hoisting
2611 ----------------------
2612
2613 This transformation replaces
2614
2615 bb0:
2616 if (...) goto bb2; else goto bb1;
2617 bb1:
2618 x1 = (<expr>).field1;
2619 goto bb3;
2620 bb2:
2621 x2 = (<expr>).field2;
2622 bb3:
2623 # x = PHI <x1, x2>;
2624
2625 with
2626
2627 bb0:
2628 x1 = (<expr>).field1;
2629 x2 = (<expr>).field2;
2630 if (...) goto bb2; else goto bb1;
2631 bb1:
2632 goto bb3;
2633 bb2:
2634 bb3:
2635 # x = PHI <x1, x2>;
2636
2637 The purpose of this transformation is to enable generation of conditional
2638 move instructions such as Intel CMOVE or PowerPC ISEL. Because one of
2639 the loads is speculative, the transformation is restricted to very
2640 specific cases to avoid introducing a page fault. We are looking for
2641 the common idiom:
2642
2643 if (...)
2644 x = y->left;
2645 else
2646 x = y->right;
2647
2648 where left and right are typically adjacent pointers in a tree structure. */
2649
2650 namespace {
2651
2652 const pass_data pass_data_phiopt =
2653 {
2654 GIMPLE_PASS, /* type */
2655 "phiopt", /* name */
2656 OPTGROUP_NONE, /* optinfo_flags */
2657 TV_TREE_PHIOPT, /* tv_id */
2658 ( PROP_cfg | PROP_ssa ), /* properties_required */
2659 0, /* properties_provided */
2660 0, /* properties_destroyed */
2661 0, /* todo_flags_start */
2662 0, /* todo_flags_finish */
2663 };
2664
2665 class pass_phiopt : public gimple_opt_pass
2666 {
2667 public:
pass_phiopt(gcc::context * ctxt)2668 pass_phiopt (gcc::context *ctxt)
2669 : gimple_opt_pass (pass_data_phiopt, ctxt)
2670 {}
2671
2672 /* opt_pass methods: */
clone()2673 opt_pass * clone () { return new pass_phiopt (m_ctxt); }
gate(function *)2674 virtual bool gate (function *) { return flag_ssa_phiopt; }
execute(function *)2675 virtual unsigned int execute (function *)
2676 {
2677 return tree_ssa_phiopt_worker (false, gate_hoist_loads ());
2678 }
2679
2680 }; // class pass_phiopt
2681
2682 } // anon namespace
2683
2684 gimple_opt_pass *
make_pass_phiopt(gcc::context * ctxt)2685 make_pass_phiopt (gcc::context *ctxt)
2686 {
2687 return new pass_phiopt (ctxt);
2688 }
2689
2690 namespace {
2691
2692 const pass_data pass_data_cselim =
2693 {
2694 GIMPLE_PASS, /* type */
2695 "cselim", /* name */
2696 OPTGROUP_NONE, /* optinfo_flags */
2697 TV_TREE_PHIOPT, /* tv_id */
2698 ( PROP_cfg | PROP_ssa ), /* properties_required */
2699 0, /* properties_provided */
2700 0, /* properties_destroyed */
2701 0, /* todo_flags_start */
2702 0, /* todo_flags_finish */
2703 };
2704
2705 class pass_cselim : public gimple_opt_pass
2706 {
2707 public:
pass_cselim(gcc::context * ctxt)2708 pass_cselim (gcc::context *ctxt)
2709 : gimple_opt_pass (pass_data_cselim, ctxt)
2710 {}
2711
2712 /* opt_pass methods: */
gate(function *)2713 virtual bool gate (function *) { return flag_tree_cselim; }
execute(function *)2714 virtual unsigned int execute (function *) { return tree_ssa_cs_elim (); }
2715
2716 }; // class pass_cselim
2717
2718 } // anon namespace
2719
2720 gimple_opt_pass *
make_pass_cselim(gcc::context * ctxt)2721 make_pass_cselim (gcc::context *ctxt)
2722 {
2723 return new pass_cselim (ctxt);
2724 }
2725