1 /* Optimization of PHI nodes by converting them into straightline code.
2 Copyright (C) 2004-2021 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 "case-cfn-macros.h"
48 #include "tree-eh.h"
49 #include "gimple-fold.h"
50 #include "internal-fn.h"
51
52 static unsigned int tree_ssa_phiopt_worker (bool, bool, bool);
53 static bool two_value_replacement (basic_block, basic_block, edge, gphi *,
54 tree, tree);
55 static bool conditional_replacement (basic_block, basic_block,
56 edge, edge, gphi *, tree, tree);
57 static gphi *factor_out_conditional_conversion (edge, edge, gphi *, tree, tree,
58 gimple *);
59 static int value_replacement (basic_block, basic_block,
60 edge, edge, gimple *, tree, tree);
61 static bool minmax_replacement (basic_block, basic_block,
62 edge, edge, gimple *, tree, tree);
63 static bool abs_replacement (basic_block, basic_block,
64 edge, edge, gimple *, tree, tree);
65 static bool xor_replacement (basic_block, basic_block,
66 edge, edge, gimple *, tree, tree);
67 static bool cond_removal_in_popcount_clz_ctz_pattern (basic_block, basic_block,
68 edge, edge, gimple *,
69 tree, tree);
70 static bool cond_store_replacement (basic_block, basic_block, edge, edge,
71 hash_set<tree> *);
72 static bool cond_if_else_store_replacement (basic_block, basic_block, basic_block);
73 static hash_set<tree> * get_non_trapping ();
74 static void replace_phi_edge_with_variable (basic_block, edge, gimple *, tree);
75 static void hoist_adjacent_loads (basic_block, basic_block,
76 basic_block, basic_block);
77 static bool gate_hoist_loads (void);
78
79 /* This pass tries to transform conditional stores into unconditional
80 ones, enabling further simplifications with the simpler then and else
81 blocks. In particular it replaces this:
82
83 bb0:
84 if (cond) goto bb2; else goto bb1;
85 bb1:
86 *p = RHS;
87 bb2:
88
89 with
90
91 bb0:
92 if (cond) goto bb1; else goto bb2;
93 bb1:
94 condtmp' = *p;
95 bb2:
96 condtmp = PHI <RHS, condtmp'>
97 *p = condtmp;
98
99 This transformation can only be done under several constraints,
100 documented below. It also replaces:
101
102 bb0:
103 if (cond) goto bb2; else goto bb1;
104 bb1:
105 *p = RHS1;
106 goto bb3;
107 bb2:
108 *p = RHS2;
109 bb3:
110
111 with
112
113 bb0:
114 if (cond) goto bb3; else goto bb1;
115 bb1:
116 bb3:
117 condtmp = PHI <RHS1, RHS2>
118 *p = condtmp; */
119
120 static unsigned int
tree_ssa_cs_elim(void)121 tree_ssa_cs_elim (void)
122 {
123 unsigned todo;
124 /* ??? We are not interested in loop related info, but the following
125 will create it, ICEing as we didn't init loops with pre-headers.
126 An interfacing issue of find_data_references_in_bb. */
127 loop_optimizer_init (LOOPS_NORMAL);
128 scev_initialize ();
129 todo = tree_ssa_phiopt_worker (true, false, false);
130 scev_finalize ();
131 loop_optimizer_finalize ();
132 return todo;
133 }
134
135 /* Return the singleton PHI in the SEQ of PHIs for edges E0 and E1. */
136
137 static gphi *
single_non_singleton_phi_for_edges(gimple_seq seq,edge e0,edge e1)138 single_non_singleton_phi_for_edges (gimple_seq seq, edge e0, edge e1)
139 {
140 gimple_stmt_iterator i;
141 gphi *phi = NULL;
142 if (gimple_seq_singleton_p (seq))
143 return as_a <gphi *> (gsi_stmt (gsi_start (seq)));
144 for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
145 {
146 gphi *p = as_a <gphi *> (gsi_stmt (i));
147 /* If the PHI arguments are equal then we can skip this PHI. */
148 if (operand_equal_for_phi_arg_p (gimple_phi_arg_def (p, e0->dest_idx),
149 gimple_phi_arg_def (p, e1->dest_idx)))
150 continue;
151
152 /* If we already have a PHI that has the two edge arguments are
153 different, then return it is not a singleton for these PHIs. */
154 if (phi)
155 return NULL;
156
157 phi = p;
158 }
159 return phi;
160 }
161
162 /* The core routine of conditional store replacement and normal
163 phi optimizations. Both share much of the infrastructure in how
164 to match applicable basic block patterns. DO_STORE_ELIM is true
165 when we want to do conditional store replacement, false otherwise.
166 DO_HOIST_LOADS is true when we want to hoist adjacent loads out
167 of diamond control flow patterns, false otherwise. */
168 static unsigned int
tree_ssa_phiopt_worker(bool do_store_elim,bool do_hoist_loads,bool early_p)169 tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p)
170 {
171 basic_block bb;
172 basic_block *bb_order;
173 unsigned n, i;
174 bool cfgchanged = false;
175 hash_set<tree> *nontrap = 0;
176
177 calculate_dominance_info (CDI_DOMINATORS);
178
179 if (do_store_elim)
180 /* Calculate the set of non-trapping memory accesses. */
181 nontrap = get_non_trapping ();
182
183 /* Search every basic block for COND_EXPR we may be able to optimize.
184
185 We walk the blocks in order that guarantees that a block with
186 a single predecessor is processed before the predecessor.
187 This ensures that we collapse inner ifs before visiting the
188 outer ones, and also that we do not try to visit a removed
189 block. */
190 bb_order = single_pred_before_succ_order ();
191 n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
192
193 for (i = 0; i < n; i++)
194 {
195 gimple *cond_stmt;
196 gphi *phi;
197 basic_block bb1, bb2;
198 edge e1, e2;
199 tree arg0, arg1;
200
201 bb = bb_order[i];
202
203 cond_stmt = last_stmt (bb);
204 /* Check to see if the last statement is a GIMPLE_COND. */
205 if (!cond_stmt
206 || gimple_code (cond_stmt) != GIMPLE_COND)
207 continue;
208
209 e1 = EDGE_SUCC (bb, 0);
210 bb1 = e1->dest;
211 e2 = EDGE_SUCC (bb, 1);
212 bb2 = e2->dest;
213
214 /* We cannot do the optimization on abnormal edges. */
215 if ((e1->flags & EDGE_ABNORMAL) != 0
216 || (e2->flags & EDGE_ABNORMAL) != 0)
217 continue;
218
219 /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
220 if (EDGE_COUNT (bb1->succs) == 0
221 || bb2 == NULL
222 || EDGE_COUNT (bb2->succs) == 0)
223 continue;
224
225 /* Find the bb which is the fall through to the other. */
226 if (EDGE_SUCC (bb1, 0)->dest == bb2)
227 ;
228 else if (EDGE_SUCC (bb2, 0)->dest == bb1)
229 {
230 std::swap (bb1, bb2);
231 std::swap (e1, e2);
232 }
233 else if (do_store_elim
234 && EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest)
235 {
236 basic_block bb3 = EDGE_SUCC (bb1, 0)->dest;
237
238 if (!single_succ_p (bb1)
239 || (EDGE_SUCC (bb1, 0)->flags & EDGE_FALLTHRU) == 0
240 || !single_succ_p (bb2)
241 || (EDGE_SUCC (bb2, 0)->flags & EDGE_FALLTHRU) == 0
242 || EDGE_COUNT (bb3->preds) != 2)
243 continue;
244 if (cond_if_else_store_replacement (bb1, bb2, bb3))
245 cfgchanged = true;
246 continue;
247 }
248 else if (do_hoist_loads
249 && EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest)
250 {
251 basic_block bb3 = EDGE_SUCC (bb1, 0)->dest;
252
253 if (!FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt)))
254 && single_succ_p (bb1)
255 && single_succ_p (bb2)
256 && single_pred_p (bb1)
257 && single_pred_p (bb2)
258 && EDGE_COUNT (bb->succs) == 2
259 && EDGE_COUNT (bb3->preds) == 2
260 /* If one edge or the other is dominant, a conditional move
261 is likely to perform worse than the well-predicted branch. */
262 && !predictable_edge_p (EDGE_SUCC (bb, 0))
263 && !predictable_edge_p (EDGE_SUCC (bb, 1)))
264 hoist_adjacent_loads (bb, bb1, bb2, bb3);
265 continue;
266 }
267 else
268 continue;
269
270 e1 = EDGE_SUCC (bb1, 0);
271
272 /* Make sure that bb1 is just a fall through. */
273 if (!single_succ_p (bb1)
274 || (e1->flags & EDGE_FALLTHRU) == 0)
275 continue;
276
277 /* Also make sure that bb1 only have one predecessor and that it
278 is bb. */
279 if (!single_pred_p (bb1)
280 || single_pred (bb1) != bb)
281 continue;
282
283 if (do_store_elim)
284 {
285 /* bb1 is the middle block, bb2 the join block, bb the split block,
286 e1 the fallthrough edge from bb1 to bb2. We can't do the
287 optimization if the join block has more than two predecessors. */
288 if (EDGE_COUNT (bb2->preds) > 2)
289 continue;
290 if (cond_store_replacement (bb1, bb2, e1, e2, nontrap))
291 cfgchanged = true;
292 }
293 else
294 {
295 gimple_seq phis = phi_nodes (bb2);
296 gimple_stmt_iterator gsi;
297 bool candorest = true;
298
299 /* Value replacement can work with more than one PHI
300 so try that first. */
301 if (!early_p)
302 for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
303 {
304 phi = as_a <gphi *> (gsi_stmt (gsi));
305 arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
306 arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
307 if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1) == 2)
308 {
309 candorest = false;
310 cfgchanged = true;
311 break;
312 }
313 }
314
315 if (!candorest)
316 continue;
317
318 phi = single_non_singleton_phi_for_edges (phis, e1, e2);
319 if (!phi)
320 continue;
321
322 arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
323 arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
324
325 /* Something is wrong if we cannot find the arguments in the PHI
326 node. */
327 gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
328
329 gphi *newphi = factor_out_conditional_conversion (e1, e2, phi,
330 arg0, arg1,
331 cond_stmt);
332 if (newphi != NULL)
333 {
334 phi = newphi;
335 /* factor_out_conditional_conversion may create a new PHI in
336 BB2 and eliminate an existing PHI in BB2. Recompute values
337 that may be affected by that change. */
338 arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
339 arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
340 gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
341 }
342
343 /* Do the replacement of conditional if it can be done. */
344 if (!early_p && two_value_replacement (bb, bb1, e2, phi, arg0, arg1))
345 cfgchanged = true;
346 else if (!early_p
347 && conditional_replacement (bb, bb1, e1, e2, phi,
348 arg0, arg1))
349 cfgchanged = true;
350 else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
351 cfgchanged = true;
352 else if (!early_p
353 && xor_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
354 cfgchanged = true;
355 else if (!early_p
356 && cond_removal_in_popcount_clz_ctz_pattern (bb, bb1, e1,
357 e2, phi, arg0,
358 arg1))
359 cfgchanged = true;
360 else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
361 cfgchanged = true;
362 }
363 }
364
365 free (bb_order);
366
367 if (do_store_elim)
368 delete nontrap;
369 /* If the CFG has changed, we should cleanup the CFG. */
370 if (cfgchanged && do_store_elim)
371 {
372 /* In cond-store replacement we have added some loads on edges
373 and new VOPS (as we moved the store, and created a load). */
374 gsi_commit_edge_inserts ();
375 return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
376 }
377 else if (cfgchanged)
378 return TODO_cleanup_cfg;
379 return 0;
380 }
381
382 /* Replace PHI node element whose edge is E in block BB with variable NEW.
383 Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
384 is known to have two edges, one of which must reach BB). */
385
386 static void
replace_phi_edge_with_variable(basic_block cond_block,edge e,gimple * phi,tree new_tree)387 replace_phi_edge_with_variable (basic_block cond_block,
388 edge e, gimple *phi, tree new_tree)
389 {
390 basic_block bb = gimple_bb (phi);
391 basic_block block_to_remove;
392 gimple_stmt_iterator gsi;
393
394 /* Change the PHI argument to new. */
395 SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);
396
397 /* Remove the empty basic block. */
398 if (EDGE_SUCC (cond_block, 0)->dest == bb)
399 {
400 EDGE_SUCC (cond_block, 0)->flags |= EDGE_FALLTHRU;
401 EDGE_SUCC (cond_block, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
402 EDGE_SUCC (cond_block, 0)->probability = profile_probability::always ();
403
404 block_to_remove = EDGE_SUCC (cond_block, 1)->dest;
405 }
406 else
407 {
408 EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU;
409 EDGE_SUCC (cond_block, 1)->flags
410 &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
411 EDGE_SUCC (cond_block, 1)->probability = profile_probability::always ();
412
413 block_to_remove = EDGE_SUCC (cond_block, 0)->dest;
414 }
415 delete_basic_block (block_to_remove);
416
417 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
418 gsi = gsi_last_bb (cond_block);
419 gsi_remove (&gsi, true);
420
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);
426 }
427
428 /* PR66726: Factor conversion out of COND_EXPR. If the arguments of the PHI
429 stmt are CONVERT_STMT, factor out the conversion and perform the conversion
430 to the result of PHI stmt. COND_STMT is the controlling predicate.
431 Return the newly-created PHI, if any. */
432
433 static gphi *
factor_out_conditional_conversion(edge e0,edge e1,gphi * phi,tree arg0,tree arg1,gimple * cond_stmt)434 factor_out_conditional_conversion (edge e0, edge e1, gphi *phi,
435 tree arg0, tree arg1, gimple *cond_stmt)
436 {
437 gimple *arg0_def_stmt = NULL, *arg1_def_stmt = NULL, *new_stmt;
438 tree new_arg0 = NULL_TREE, new_arg1 = NULL_TREE;
439 tree temp, result;
440 gphi *newphi;
441 gimple_stmt_iterator gsi, gsi_for_def;
442 location_t locus = gimple_location (phi);
443 enum tree_code convert_code;
444
445 /* Handle only PHI statements with two arguments. TODO: If all
446 other arguments to PHI are INTEGER_CST or if their defining
447 statement have the same unary operation, we can handle more
448 than two arguments too. */
449 if (gimple_phi_num_args (phi) != 2)
450 return NULL;
451
452 /* First canonicalize to simplify tests. */
453 if (TREE_CODE (arg0) != SSA_NAME)
454 {
455 std::swap (arg0, arg1);
456 std::swap (e0, e1);
457 }
458
459 if (TREE_CODE (arg0) != SSA_NAME
460 || (TREE_CODE (arg1) != SSA_NAME
461 && TREE_CODE (arg1) != INTEGER_CST))
462 return NULL;
463
464 /* Check if arg0 is an SSA_NAME and the stmt which defines arg0 is
465 a conversion. */
466 arg0_def_stmt = SSA_NAME_DEF_STMT (arg0);
467 if (!gimple_assign_cast_p (arg0_def_stmt))
468 return NULL;
469
470 /* Use the RHS as new_arg0. */
471 convert_code = gimple_assign_rhs_code (arg0_def_stmt);
472 new_arg0 = gimple_assign_rhs1 (arg0_def_stmt);
473 if (convert_code == VIEW_CONVERT_EXPR)
474 {
475 new_arg0 = TREE_OPERAND (new_arg0, 0);
476 if (!is_gimple_reg_type (TREE_TYPE (new_arg0)))
477 return NULL;
478 }
479 if (TREE_CODE (new_arg0) == SSA_NAME
480 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_arg0))
481 return NULL;
482
483 if (TREE_CODE (arg1) == SSA_NAME)
484 {
485 /* Check if arg1 is an SSA_NAME and the stmt which defines arg1
486 is a conversion. */
487 arg1_def_stmt = SSA_NAME_DEF_STMT (arg1);
488 if (!is_gimple_assign (arg1_def_stmt)
489 || gimple_assign_rhs_code (arg1_def_stmt) != convert_code)
490 return NULL;
491
492 /* Either arg1_def_stmt or arg0_def_stmt should be conditional. */
493 if (dominated_by_p (CDI_DOMINATORS, gimple_bb (phi), gimple_bb (arg0_def_stmt))
494 && dominated_by_p (CDI_DOMINATORS,
495 gimple_bb (phi), gimple_bb (arg1_def_stmt)))
496 return NULL;
497
498 /* Use the RHS as new_arg1. */
499 new_arg1 = gimple_assign_rhs1 (arg1_def_stmt);
500 if (convert_code == VIEW_CONVERT_EXPR)
501 new_arg1 = TREE_OPERAND (new_arg1, 0);
502 if (TREE_CODE (new_arg1) == SSA_NAME
503 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_arg1))
504 return NULL;
505 }
506 else
507 {
508 /* arg0_def_stmt should be conditional. */
509 if (dominated_by_p (CDI_DOMINATORS, gimple_bb (phi), gimple_bb (arg0_def_stmt)))
510 return NULL;
511 /* If arg1 is an INTEGER_CST, fold it to new type. */
512 if (INTEGRAL_TYPE_P (TREE_TYPE (new_arg0))
513 && int_fits_type_p (arg1, TREE_TYPE (new_arg0)))
514 {
515 if (gimple_assign_cast_p (arg0_def_stmt))
516 {
517 /* For the INTEGER_CST case, we are just moving the
518 conversion from one place to another, which can often
519 hurt as the conversion moves further away from the
520 statement that computes the value. So, perform this
521 only if new_arg0 is an operand of COND_STMT, or
522 if arg0_def_stmt is the only non-debug stmt in
523 its basic block, because then it is possible this
524 could enable further optimizations (minmax replacement
525 etc.). See PR71016. */
526 if (new_arg0 != gimple_cond_lhs (cond_stmt)
527 && new_arg0 != gimple_cond_rhs (cond_stmt)
528 && gimple_bb (arg0_def_stmt) == e0->src)
529 {
530 gsi = gsi_for_stmt (arg0_def_stmt);
531 gsi_prev_nondebug (&gsi);
532 if (!gsi_end_p (gsi))
533 {
534 if (gassign *assign
535 = dyn_cast <gassign *> (gsi_stmt (gsi)))
536 {
537 tree lhs = gimple_assign_lhs (assign);
538 enum tree_code ass_code
539 = gimple_assign_rhs_code (assign);
540 if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
541 return NULL;
542 if (lhs != gimple_assign_rhs1 (arg0_def_stmt))
543 return NULL;
544 gsi_prev_nondebug (&gsi);
545 if (!gsi_end_p (gsi))
546 return NULL;
547 }
548 else
549 return NULL;
550 }
551 gsi = gsi_for_stmt (arg0_def_stmt);
552 gsi_next_nondebug (&gsi);
553 if (!gsi_end_p (gsi))
554 return NULL;
555 }
556 new_arg1 = fold_convert (TREE_TYPE (new_arg0), arg1);
557 }
558 else
559 return NULL;
560 }
561 else
562 return NULL;
563 }
564
565 /* If arg0/arg1 have > 1 use, then this transformation actually increases
566 the number of expressions evaluated at runtime. */
567 if (!has_single_use (arg0)
568 || (arg1_def_stmt && !has_single_use (arg1)))
569 return NULL;
570
571 /* If types of new_arg0 and new_arg1 are different bailout. */
572 if (!types_compatible_p (TREE_TYPE (new_arg0), TREE_TYPE (new_arg1)))
573 return NULL;
574
575 /* Create a new PHI stmt. */
576 result = PHI_RESULT (phi);
577 temp = make_ssa_name (TREE_TYPE (new_arg0), NULL);
578 newphi = create_phi_node (temp, gimple_bb (phi));
579
580 if (dump_file && (dump_flags & TDF_DETAILS))
581 {
582 fprintf (dump_file, "PHI ");
583 print_generic_expr (dump_file, gimple_phi_result (phi));
584 fprintf (dump_file,
585 " changed to factor conversion out from COND_EXPR.\n");
586 fprintf (dump_file, "New stmt with CAST that defines ");
587 print_generic_expr (dump_file, result);
588 fprintf (dump_file, ".\n");
589 }
590
591 /* Remove the old cast(s) that has single use. */
592 gsi_for_def = gsi_for_stmt (arg0_def_stmt);
593 gsi_remove (&gsi_for_def, true);
594 release_defs (arg0_def_stmt);
595
596 if (arg1_def_stmt)
597 {
598 gsi_for_def = gsi_for_stmt (arg1_def_stmt);
599 gsi_remove (&gsi_for_def, true);
600 release_defs (arg1_def_stmt);
601 }
602
603 add_phi_arg (newphi, new_arg0, e0, locus);
604 add_phi_arg (newphi, new_arg1, e1, locus);
605
606 /* Create the conversion stmt and insert it. */
607 if (convert_code == VIEW_CONVERT_EXPR)
608 {
609 temp = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (result), temp);
610 new_stmt = gimple_build_assign (result, temp);
611 }
612 else
613 new_stmt = gimple_build_assign (result, convert_code, temp);
614 gsi = gsi_after_labels (gimple_bb (phi));
615 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
616
617 /* Remove the original PHI stmt. */
618 gsi = gsi_for_stmt (phi);
619 gsi_remove (&gsi, true);
620 return newphi;
621 }
622
623 /* Optimize
624 # x_5 in range [cst1, cst2] where cst2 = cst1 + 1
625 if (x_5 op cstN) # where op is == or != and N is 1 or 2
626 goto bb3;
627 else
628 goto bb4;
629 bb3:
630 bb4:
631 # r_6 = PHI<cst3(2), cst4(3)> # where cst3 == cst4 + 1 or cst4 == cst3 + 1
632
633 to r_6 = x_5 + (min (cst3, cst4) - cst1) or
634 r_6 = (min (cst3, cst4) + cst1) - x_5 depending on op, N and which
635 of cst3 and cst4 is smaller. */
636
637 static bool
two_value_replacement(basic_block cond_bb,basic_block middle_bb,edge e1,gphi * phi,tree arg0,tree arg1)638 two_value_replacement (basic_block cond_bb, basic_block middle_bb,
639 edge e1, gphi *phi, tree arg0, tree arg1)
640 {
641 /* Only look for adjacent integer constants. */
642 if (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
643 || !INTEGRAL_TYPE_P (TREE_TYPE (arg1))
644 || TREE_CODE (arg0) != INTEGER_CST
645 || TREE_CODE (arg1) != INTEGER_CST
646 || (tree_int_cst_lt (arg0, arg1)
647 ? wi::to_widest (arg0) + 1 != wi::to_widest (arg1)
648 : wi::to_widest (arg1) + 1 != wi::to_widest (arg0)))
649 return false;
650
651 if (!empty_block_p (middle_bb))
652 return false;
653
654 gimple *stmt = last_stmt (cond_bb);
655 tree lhs = gimple_cond_lhs (stmt);
656 tree rhs = gimple_cond_rhs (stmt);
657
658 if (TREE_CODE (lhs) != SSA_NAME
659 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
660 || TREE_CODE (rhs) != INTEGER_CST)
661 return false;
662
663 switch (gimple_cond_code (stmt))
664 {
665 case EQ_EXPR:
666 case NE_EXPR:
667 break;
668 default:
669 return false;
670 }
671
672 /* Defer boolean x ? 0 : {1,-1} or x ? {1,-1} : 0 to
673 conditional_replacement. */
674 if (TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE
675 && (integer_zerop (arg0)
676 || integer_zerop (arg1)
677 || TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE
678 || (TYPE_PRECISION (TREE_TYPE (arg0))
679 <= TYPE_PRECISION (TREE_TYPE (lhs)))))
680 return false;
681
682 wide_int min, max;
683 if (get_range_info (lhs, &min, &max) != VR_RANGE)
684 {
685 int prec = TYPE_PRECISION (TREE_TYPE (lhs));
686 signop sgn = TYPE_SIGN (TREE_TYPE (lhs));
687 min = wi::min_value (prec, sgn);
688 max = wi::max_value (prec, sgn);
689 }
690 if (min + 1 != max
691 || (wi::to_wide (rhs) != min
692 && wi::to_wide (rhs) != max))
693 return false;
694
695 /* We need to know which is the true edge and which is the false
696 edge so that we know when to invert the condition below. */
697 edge true_edge, false_edge;
698 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
699 if ((gimple_cond_code (stmt) == EQ_EXPR)
700 ^ (wi::to_wide (rhs) == max)
701 ^ (e1 == false_edge))
702 std::swap (arg0, arg1);
703
704 tree type;
705 if (TYPE_PRECISION (TREE_TYPE (lhs)) == TYPE_PRECISION (TREE_TYPE (arg0)))
706 {
707 /* Avoid performing the arithmetics in bool type which has different
708 semantics, otherwise prefer unsigned types from the two with
709 the same precision. */
710 if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE
711 || !TYPE_UNSIGNED (TREE_TYPE (arg0)))
712 type = TREE_TYPE (lhs);
713 else
714 type = TREE_TYPE (arg0);
715 }
716 else if (TYPE_PRECISION (TREE_TYPE (lhs)) > TYPE_PRECISION (TREE_TYPE (arg0)))
717 type = TREE_TYPE (lhs);
718 else
719 type = TREE_TYPE (arg0);
720
721 min = wide_int::from (min, TYPE_PRECISION (type),
722 TYPE_SIGN (TREE_TYPE (lhs)));
723 wide_int a = wide_int::from (wi::to_wide (arg0), TYPE_PRECISION (type),
724 TYPE_SIGN (TREE_TYPE (arg0)));
725 enum tree_code code;
726 wi::overflow_type ovf;
727 if (tree_int_cst_lt (arg0, arg1))
728 {
729 code = PLUS_EXPR;
730 a -= min;
731 if (!TYPE_UNSIGNED (type))
732 {
733 /* lhs is known to be in range [min, min+1] and we want to add a
734 to it. Check if that operation can overflow for those 2 values
735 and if yes, force unsigned type. */
736 wi::add (min + (wi::neg_p (a) ? 0 : 1), a, SIGNED, &ovf);
737 if (ovf)
738 type = unsigned_type_for (type);
739 }
740 }
741 else
742 {
743 code = MINUS_EXPR;
744 a += min;
745 if (!TYPE_UNSIGNED (type))
746 {
747 /* lhs is known to be in range [min, min+1] and we want to subtract
748 it from a. Check if that operation can overflow for those 2
749 values and if yes, force unsigned type. */
750 wi::sub (a, min + (wi::neg_p (min) ? 0 : 1), SIGNED, &ovf);
751 if (ovf)
752 type = unsigned_type_for (type);
753 }
754 }
755
756 tree arg = wide_int_to_tree (type, a);
757 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
758 if (!useless_type_conversion_p (type, TREE_TYPE (lhs)))
759 lhs = gimplify_build1 (&gsi, NOP_EXPR, type, lhs);
760 tree new_rhs;
761 if (code == PLUS_EXPR)
762 new_rhs = gimplify_build2 (&gsi, PLUS_EXPR, type, lhs, arg);
763 else
764 new_rhs = gimplify_build2 (&gsi, MINUS_EXPR, type, arg, lhs);
765 if (!useless_type_conversion_p (TREE_TYPE (arg0), type))
766 new_rhs = gimplify_build1 (&gsi, NOP_EXPR, TREE_TYPE (arg0), new_rhs);
767
768 replace_phi_edge_with_variable (cond_bb, e1, phi, new_rhs);
769
770 /* Note that we optimized this PHI. */
771 return true;
772 }
773
774 /* The function conditional_replacement does the main work of doing the
775 conditional replacement. Return true if the replacement is done.
776 Otherwise return false.
777 BB is the basic block where the replacement is going to be done on. ARG0
778 is argument 0 from PHI. Likewise for ARG1. */
779
780 static bool
conditional_replacement(basic_block cond_bb,basic_block middle_bb,edge e0,edge e1,gphi * phi,tree arg0,tree arg1)781 conditional_replacement (basic_block cond_bb, basic_block middle_bb,
782 edge e0, edge e1, gphi *phi,
783 tree arg0, tree arg1)
784 {
785 tree result;
786 gimple *stmt;
787 gassign *new_stmt;
788 tree cond;
789 gimple_stmt_iterator gsi;
790 edge true_edge, false_edge;
791 tree new_var, new_var2;
792 bool neg = false;
793 int shift = 0;
794 tree nonzero_arg;
795
796 /* FIXME: Gimplification of complex type is too hard for now. */
797 /* We aren't prepared to handle vectors either (and it is a question
798 if it would be worthwhile anyway). */
799 if (!(INTEGRAL_TYPE_P (TREE_TYPE (arg0))
800 || POINTER_TYPE_P (TREE_TYPE (arg0)))
801 || !(INTEGRAL_TYPE_P (TREE_TYPE (arg1))
802 || POINTER_TYPE_P (TREE_TYPE (arg1))))
803 return false;
804
805 /* The PHI arguments have the constants 0 and 1, or 0 and -1 or
806 0 and (1 << cst), then convert it to the conditional. */
807 if (integer_zerop (arg0))
808 nonzero_arg = arg1;
809 else if (integer_zerop (arg1))
810 nonzero_arg = arg0;
811 else
812 return false;
813 if (integer_pow2p (nonzero_arg))
814 {
815 shift = tree_log2 (nonzero_arg);
816 if (shift && POINTER_TYPE_P (TREE_TYPE (nonzero_arg)))
817 return false;
818 }
819 else if (integer_all_onesp (nonzero_arg))
820 neg = true;
821 else
822 return false;
823
824 if (!empty_block_p (middle_bb))
825 return false;
826
827 /* At this point we know we have a GIMPLE_COND with two successors.
828 One successor is BB, the other successor is an empty block which
829 falls through into BB.
830
831 There is a single PHI node at the join point (BB) and its arguments
832 are constants (0, 1) or (0, -1) or (0, (1 << shift)).
833
834 So, given the condition COND, and the two PHI arguments, we can
835 rewrite this PHI into non-branching code:
836
837 dest = (COND) or dest = COND' or dest = (COND) << shift
838
839 We use the condition as-is if the argument associated with the
840 true edge has the value one or the argument associated with the
841 false edge as the value zero. Note that those conditions are not
842 the same since only one of the outgoing edges from the GIMPLE_COND
843 will directly reach BB and thus be associated with an argument. */
844
845 stmt = last_stmt (cond_bb);
846 result = PHI_RESULT (phi);
847
848 /* To handle special cases like floating point comparison, it is easier and
849 less error-prone to build a tree and gimplify it on the fly though it is
850 less efficient. */
851 cond = fold_build2_loc (gimple_location (stmt),
852 gimple_cond_code (stmt), boolean_type_node,
853 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
854
855 /* We need to know which is the true edge and which is the false
856 edge so that we know when to invert the condition below. */
857 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
858 if ((e0 == true_edge && integer_zerop (arg0))
859 || (e0 == false_edge && !integer_zerop (arg0))
860 || (e1 == true_edge && integer_zerop (arg1))
861 || (e1 == false_edge && !integer_zerop (arg1)))
862 cond = fold_build1_loc (gimple_location (stmt),
863 TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
864
865 if (neg)
866 {
867 cond = fold_convert_loc (gimple_location (stmt),
868 TREE_TYPE (result), cond);
869 cond = fold_build1_loc (gimple_location (stmt),
870 NEGATE_EXPR, TREE_TYPE (cond), cond);
871 }
872 else if (shift)
873 {
874 cond = fold_convert_loc (gimple_location (stmt),
875 TREE_TYPE (result), cond);
876 cond = fold_build2_loc (gimple_location (stmt),
877 LSHIFT_EXPR, TREE_TYPE (cond), cond,
878 build_int_cst (integer_type_node, shift));
879 }
880
881 /* Insert our new statements at the end of conditional block before the
882 COND_STMT. */
883 gsi = gsi_for_stmt (stmt);
884 new_var = force_gimple_operand_gsi (&gsi, cond, true, NULL, true,
885 GSI_SAME_STMT);
886
887 if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (new_var)))
888 {
889 location_t locus_0, locus_1;
890
891 new_var2 = make_ssa_name (TREE_TYPE (result));
892 new_stmt = gimple_build_assign (new_var2, CONVERT_EXPR, new_var);
893 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
894 new_var = new_var2;
895
896 /* Set the locus to the first argument, unless is doesn't have one. */
897 locus_0 = gimple_phi_arg_location (phi, 0);
898 locus_1 = gimple_phi_arg_location (phi, 1);
899 if (locus_0 == UNKNOWN_LOCATION)
900 locus_0 = locus_1;
901 gimple_set_location (new_stmt, locus_0);
902 }
903
904 replace_phi_edge_with_variable (cond_bb, e1, phi, new_var);
905
906 /* Note that we optimized this PHI. */
907 return true;
908 }
909
910 /* Update *ARG which is defined in STMT so that it contains the
911 computed value if that seems profitable. Return true if the
912 statement is made dead by that rewriting. */
913
914 static bool
jump_function_from_stmt(tree * arg,gimple * stmt)915 jump_function_from_stmt (tree *arg, gimple *stmt)
916 {
917 enum tree_code code = gimple_assign_rhs_code (stmt);
918 if (code == ADDR_EXPR)
919 {
920 /* For arg = &p->i transform it to p, if possible. */
921 tree rhs1 = gimple_assign_rhs1 (stmt);
922 poly_int64 offset;
923 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs1, 0),
924 &offset);
925 if (tem
926 && TREE_CODE (tem) == MEM_REF
927 && known_eq (mem_ref_offset (tem) + offset, 0))
928 {
929 *arg = TREE_OPERAND (tem, 0);
930 return true;
931 }
932 }
933 /* TODO: Much like IPA-CP jump-functions we want to handle constant
934 additions symbolically here, and we'd need to update the comparison
935 code that compares the arg + cst tuples in our caller. For now the
936 code above exactly handles the VEC_BASE pattern from vec.h. */
937 return false;
938 }
939
940 /* RHS is a source argument in a BIT_AND_EXPR which feeds a conditional
941 of the form SSA_NAME NE 0.
942
943 If RHS is fed by a simple EQ_EXPR comparison of two values, see if
944 the two input values of the EQ_EXPR match arg0 and arg1.
945
946 If so update *code and return TRUE. Otherwise return FALSE. */
947
948 static bool
rhs_is_fed_for_value_replacement(const_tree arg0,const_tree arg1,enum tree_code * code,const_tree rhs)949 rhs_is_fed_for_value_replacement (const_tree arg0, const_tree arg1,
950 enum tree_code *code, const_tree rhs)
951 {
952 /* Obviously if RHS is not an SSA_NAME, we can't look at the defining
953 statement. */
954 if (TREE_CODE (rhs) == SSA_NAME)
955 {
956 gimple *def1 = SSA_NAME_DEF_STMT (rhs);
957
958 /* Verify the defining statement has an EQ_EXPR on the RHS. */
959 if (is_gimple_assign (def1) && gimple_assign_rhs_code (def1) == EQ_EXPR)
960 {
961 /* Finally verify the source operands of the EQ_EXPR are equal
962 to arg0 and arg1. */
963 tree op0 = gimple_assign_rhs1 (def1);
964 tree op1 = gimple_assign_rhs2 (def1);
965 if ((operand_equal_for_phi_arg_p (arg0, op0)
966 && operand_equal_for_phi_arg_p (arg1, op1))
967 || (operand_equal_for_phi_arg_p (arg0, op1)
968 && operand_equal_for_phi_arg_p (arg1, op0)))
969 {
970 /* We will perform the optimization. */
971 *code = gimple_assign_rhs_code (def1);
972 return true;
973 }
974 }
975 }
976 return false;
977 }
978
979 /* Return TRUE if arg0/arg1 are equal to the rhs/lhs or lhs/rhs of COND.
980
981 Also return TRUE if arg0/arg1 are equal to the source arguments of a
982 an EQ comparison feeding a BIT_AND_EXPR which feeds COND.
983
984 Return FALSE otherwise. */
985
986 static bool
operand_equal_for_value_replacement(const_tree arg0,const_tree arg1,enum tree_code * code,gimple * cond)987 operand_equal_for_value_replacement (const_tree arg0, const_tree arg1,
988 enum tree_code *code, gimple *cond)
989 {
990 gimple *def;
991 tree lhs = gimple_cond_lhs (cond);
992 tree rhs = gimple_cond_rhs (cond);
993
994 if ((operand_equal_for_phi_arg_p (arg0, lhs)
995 && operand_equal_for_phi_arg_p (arg1, rhs))
996 || (operand_equal_for_phi_arg_p (arg1, lhs)
997 && operand_equal_for_phi_arg_p (arg0, rhs)))
998 return true;
999
1000 /* Now handle more complex case where we have an EQ comparison
1001 which feeds a BIT_AND_EXPR which feeds COND.
1002
1003 First verify that COND is of the form SSA_NAME NE 0. */
1004 if (*code != NE_EXPR || !integer_zerop (rhs)
1005 || TREE_CODE (lhs) != SSA_NAME)
1006 return false;
1007
1008 /* Now ensure that SSA_NAME is set by a BIT_AND_EXPR. */
1009 def = SSA_NAME_DEF_STMT (lhs);
1010 if (!is_gimple_assign (def) || gimple_assign_rhs_code (def) != BIT_AND_EXPR)
1011 return false;
1012
1013 /* Now verify arg0/arg1 correspond to the source arguments of an
1014 EQ comparison feeding the BIT_AND_EXPR. */
1015
1016 tree tmp = gimple_assign_rhs1 (def);
1017 if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp))
1018 return true;
1019
1020 tmp = gimple_assign_rhs2 (def);
1021 if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp))
1022 return true;
1023
1024 return false;
1025 }
1026
1027 /* Returns true if ARG is a neutral element for operation CODE
1028 on the RIGHT side. */
1029
1030 static bool
neutral_element_p(tree_code code,tree arg,bool right)1031 neutral_element_p (tree_code code, tree arg, bool right)
1032 {
1033 switch (code)
1034 {
1035 case PLUS_EXPR:
1036 case BIT_IOR_EXPR:
1037 case BIT_XOR_EXPR:
1038 return integer_zerop (arg);
1039
1040 case LROTATE_EXPR:
1041 case RROTATE_EXPR:
1042 case LSHIFT_EXPR:
1043 case RSHIFT_EXPR:
1044 case MINUS_EXPR:
1045 case POINTER_PLUS_EXPR:
1046 return right && integer_zerop (arg);
1047
1048 case MULT_EXPR:
1049 return integer_onep (arg);
1050
1051 case TRUNC_DIV_EXPR:
1052 case CEIL_DIV_EXPR:
1053 case FLOOR_DIV_EXPR:
1054 case ROUND_DIV_EXPR:
1055 case EXACT_DIV_EXPR:
1056 return right && integer_onep (arg);
1057
1058 case BIT_AND_EXPR:
1059 return integer_all_onesp (arg);
1060
1061 default:
1062 return false;
1063 }
1064 }
1065
1066 /* Returns true if ARG is an absorbing element for operation CODE. */
1067
1068 static bool
absorbing_element_p(tree_code code,tree arg,bool right,tree rval)1069 absorbing_element_p (tree_code code, tree arg, bool right, tree rval)
1070 {
1071 switch (code)
1072 {
1073 case BIT_IOR_EXPR:
1074 return integer_all_onesp (arg);
1075
1076 case MULT_EXPR:
1077 case BIT_AND_EXPR:
1078 return integer_zerop (arg);
1079
1080 case LSHIFT_EXPR:
1081 case RSHIFT_EXPR:
1082 case LROTATE_EXPR:
1083 case RROTATE_EXPR:
1084 return !right && integer_zerop (arg);
1085
1086 case TRUNC_DIV_EXPR:
1087 case CEIL_DIV_EXPR:
1088 case FLOOR_DIV_EXPR:
1089 case ROUND_DIV_EXPR:
1090 case EXACT_DIV_EXPR:
1091 case TRUNC_MOD_EXPR:
1092 case CEIL_MOD_EXPR:
1093 case FLOOR_MOD_EXPR:
1094 case ROUND_MOD_EXPR:
1095 return (!right
1096 && integer_zerop (arg)
1097 && tree_single_nonzero_warnv_p (rval, NULL));
1098
1099 default:
1100 return false;
1101 }
1102 }
1103
1104 /* The function value_replacement does the main work of doing the value
1105 replacement. Return non-zero if the replacement is done. Otherwise return
1106 0. If we remove the middle basic block, return 2.
1107 BB is the basic block where the replacement is going to be done on. ARG0
1108 is argument 0 from the PHI. Likewise for ARG1. */
1109
1110 static int
value_replacement(basic_block cond_bb,basic_block middle_bb,edge e0,edge e1,gimple * phi,tree arg0,tree arg1)1111 value_replacement (basic_block cond_bb, basic_block middle_bb,
1112 edge e0, edge e1, gimple *phi,
1113 tree arg0, tree arg1)
1114 {
1115 gimple_stmt_iterator gsi;
1116 gimple *cond;
1117 edge true_edge, false_edge;
1118 enum tree_code code;
1119 bool empty_or_with_defined_p = true;
1120
1121 /* If the type says honor signed zeros we cannot do this
1122 optimization. */
1123 if (HONOR_SIGNED_ZEROS (arg1))
1124 return 0;
1125
1126 /* If there is a statement in MIDDLE_BB that defines one of the PHI
1127 arguments, then adjust arg0 or arg1. */
1128 gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
1129 while (!gsi_end_p (gsi))
1130 {
1131 gimple *stmt = gsi_stmt (gsi);
1132 tree lhs;
1133 gsi_next_nondebug (&gsi);
1134 if (!is_gimple_assign (stmt))
1135 {
1136 if (gimple_code (stmt) != GIMPLE_PREDICT
1137 && gimple_code (stmt) != GIMPLE_NOP)
1138 empty_or_with_defined_p = false;
1139 continue;
1140 }
1141 /* Now try to adjust arg0 or arg1 according to the computation
1142 in the statement. */
1143 lhs = gimple_assign_lhs (stmt);
1144 if (!(lhs == arg0
1145 && jump_function_from_stmt (&arg0, stmt))
1146 || (lhs == arg1
1147 && jump_function_from_stmt (&arg1, stmt)))
1148 empty_or_with_defined_p = false;
1149 }
1150
1151 cond = last_stmt (cond_bb);
1152 code = gimple_cond_code (cond);
1153
1154 /* This transformation is only valid for equality comparisons. */
1155 if (code != NE_EXPR && code != EQ_EXPR)
1156 return 0;
1157
1158 /* We need to know which is the true edge and which is the false
1159 edge so that we know if have abs or negative abs. */
1160 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1161
1162 /* At this point we know we have a COND_EXPR with two successors.
1163 One successor is BB, the other successor is an empty block which
1164 falls through into BB.
1165
1166 The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
1167
1168 There is a single PHI node at the join point (BB) with two arguments.
1169
1170 We now need to verify that the two arguments in the PHI node match
1171 the two arguments to the equality comparison. */
1172
1173 if (operand_equal_for_value_replacement (arg0, arg1, &code, cond))
1174 {
1175 edge e;
1176 tree arg;
1177
1178 /* For NE_EXPR, we want to build an assignment result = arg where
1179 arg is the PHI argument associated with the true edge. For
1180 EQ_EXPR we want the PHI argument associated with the false edge. */
1181 e = (code == NE_EXPR ? true_edge : false_edge);
1182
1183 /* Unfortunately, E may not reach BB (it may instead have gone to
1184 OTHER_BLOCK). If that is the case, then we want the single outgoing
1185 edge from OTHER_BLOCK which reaches BB and represents the desired
1186 path from COND_BLOCK. */
1187 if (e->dest == middle_bb)
1188 e = single_succ_edge (e->dest);
1189
1190 /* Now we know the incoming edge to BB that has the argument for the
1191 RHS of our new assignment statement. */
1192 if (e0 == e)
1193 arg = arg0;
1194 else
1195 arg = arg1;
1196
1197 /* If the middle basic block was empty or is defining the
1198 PHI arguments and this is a single phi where the args are different
1199 for the edges e0 and e1 then we can remove the middle basic block. */
1200 if (empty_or_with_defined_p
1201 && single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)),
1202 e0, e1) == phi)
1203 {
1204 replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
1205 /* Note that we optimized this PHI. */
1206 return 2;
1207 }
1208 else
1209 {
1210 /* Replace the PHI arguments with arg. */
1211 SET_PHI_ARG_DEF (phi, e0->dest_idx, arg);
1212 SET_PHI_ARG_DEF (phi, e1->dest_idx, arg);
1213 if (dump_file && (dump_flags & TDF_DETAILS))
1214 {
1215 fprintf (dump_file, "PHI ");
1216 print_generic_expr (dump_file, gimple_phi_result (phi));
1217 fprintf (dump_file, " reduced for COND_EXPR in block %d to ",
1218 cond_bb->index);
1219 print_generic_expr (dump_file, arg);
1220 fprintf (dump_file, ".\n");
1221 }
1222 return 1;
1223 }
1224
1225 }
1226
1227 /* Now optimize (x != 0) ? x + y : y to just x + y. */
1228 gsi = gsi_last_nondebug_bb (middle_bb);
1229 if (gsi_end_p (gsi))
1230 return 0;
1231
1232 gimple *assign = gsi_stmt (gsi);
1233 if (!is_gimple_assign (assign)
1234 || gimple_assign_rhs_class (assign) != GIMPLE_BINARY_RHS
1235 || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
1236 && !POINTER_TYPE_P (TREE_TYPE (arg0))))
1237 return 0;
1238
1239 /* Punt if there are (degenerate) PHIs in middle_bb, there should not be. */
1240 if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
1241 return 0;
1242
1243 /* Allow up to 2 cheap preparation statements that prepare argument
1244 for assign, e.g.:
1245 if (y_4 != 0)
1246 goto <bb 3>;
1247 else
1248 goto <bb 4>;
1249 <bb 3>:
1250 _1 = (int) y_4;
1251 iftmp.0_6 = x_5(D) r<< _1;
1252 <bb 4>:
1253 # iftmp.0_2 = PHI <iftmp.0_6(3), x_5(D)(2)>
1254 or:
1255 if (y_3(D) == 0)
1256 goto <bb 4>;
1257 else
1258 goto <bb 3>;
1259 <bb 3>:
1260 y_4 = y_3(D) & 31;
1261 _1 = (int) y_4;
1262 _6 = x_5(D) r<< _1;
1263 <bb 4>:
1264 # _2 = PHI <x_5(D)(2), _6(3)> */
1265 gimple *prep_stmt[2] = { NULL, NULL };
1266 int prep_cnt;
1267 for (prep_cnt = 0; ; prep_cnt++)
1268 {
1269 gsi_prev_nondebug (&gsi);
1270 if (gsi_end_p (gsi))
1271 break;
1272
1273 gimple *g = gsi_stmt (gsi);
1274 if (gimple_code (g) == GIMPLE_LABEL)
1275 break;
1276
1277 if (prep_cnt == 2 || !is_gimple_assign (g))
1278 return 0;
1279
1280 tree lhs = gimple_assign_lhs (g);
1281 tree rhs1 = gimple_assign_rhs1 (g);
1282 use_operand_p use_p;
1283 gimple *use_stmt;
1284 if (TREE_CODE (lhs) != SSA_NAME
1285 || TREE_CODE (rhs1) != SSA_NAME
1286 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1287 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1288 || !single_imm_use (lhs, &use_p, &use_stmt)
1289 || use_stmt != (prep_cnt ? prep_stmt[prep_cnt - 1] : assign))
1290 return 0;
1291 switch (gimple_assign_rhs_code (g))
1292 {
1293 CASE_CONVERT:
1294 break;
1295 case PLUS_EXPR:
1296 case BIT_AND_EXPR:
1297 case BIT_IOR_EXPR:
1298 case BIT_XOR_EXPR:
1299 if (TREE_CODE (gimple_assign_rhs2 (g)) != INTEGER_CST)
1300 return 0;
1301 break;
1302 default:
1303 return 0;
1304 }
1305 prep_stmt[prep_cnt] = g;
1306 }
1307
1308 /* Only transform if it removes the condition. */
1309 if (!single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)), e0, e1))
1310 return 0;
1311
1312 /* Size-wise, this is always profitable. */
1313 if (optimize_bb_for_speed_p (cond_bb)
1314 /* The special case is useless if it has a low probability. */
1315 && profile_status_for_fn (cfun) != PROFILE_ABSENT
1316 && EDGE_PRED (middle_bb, 0)->probability < profile_probability::even ()
1317 /* If assign is cheap, there is no point avoiding it. */
1318 && estimate_num_insns_seq (bb_seq (middle_bb), &eni_time_weights)
1319 >= 3 * estimate_num_insns (cond, &eni_time_weights))
1320 return 0;
1321
1322 tree lhs = gimple_assign_lhs (assign);
1323 tree rhs1 = gimple_assign_rhs1 (assign);
1324 tree rhs2 = gimple_assign_rhs2 (assign);
1325 enum tree_code code_def = gimple_assign_rhs_code (assign);
1326 tree cond_lhs = gimple_cond_lhs (cond);
1327 tree cond_rhs = gimple_cond_rhs (cond);
1328
1329 /* Propagate the cond_rhs constant through preparation stmts,
1330 make sure UB isn't invoked while doing that. */
1331 for (int i = prep_cnt - 1; i >= 0; --i)
1332 {
1333 gimple *g = prep_stmt[i];
1334 tree grhs1 = gimple_assign_rhs1 (g);
1335 if (!operand_equal_for_phi_arg_p (cond_lhs, grhs1))
1336 return 0;
1337 cond_lhs = gimple_assign_lhs (g);
1338 cond_rhs = fold_convert (TREE_TYPE (grhs1), cond_rhs);
1339 if (TREE_CODE (cond_rhs) != INTEGER_CST
1340 || TREE_OVERFLOW (cond_rhs))
1341 return 0;
1342 if (gimple_assign_rhs_class (g) == GIMPLE_BINARY_RHS)
1343 {
1344 cond_rhs = int_const_binop (gimple_assign_rhs_code (g), cond_rhs,
1345 gimple_assign_rhs2 (g));
1346 if (TREE_OVERFLOW (cond_rhs))
1347 return 0;
1348 }
1349 cond_rhs = fold_convert (TREE_TYPE (cond_lhs), cond_rhs);
1350 if (TREE_CODE (cond_rhs) != INTEGER_CST
1351 || TREE_OVERFLOW (cond_rhs))
1352 return 0;
1353 }
1354
1355 if (((code == NE_EXPR && e1 == false_edge)
1356 || (code == EQ_EXPR && e1 == true_edge))
1357 && arg0 == lhs
1358 && ((arg1 == rhs1
1359 && operand_equal_for_phi_arg_p (rhs2, cond_lhs)
1360 && neutral_element_p (code_def, cond_rhs, true))
1361 || (arg1 == rhs2
1362 && operand_equal_for_phi_arg_p (rhs1, cond_lhs)
1363 && neutral_element_p (code_def, cond_rhs, false))
1364 || (operand_equal_for_phi_arg_p (arg1, cond_rhs)
1365 && ((operand_equal_for_phi_arg_p (rhs2, cond_lhs)
1366 && absorbing_element_p (code_def, cond_rhs, true, rhs2))
1367 || (operand_equal_for_phi_arg_p (rhs1, cond_lhs)
1368 && absorbing_element_p (code_def,
1369 cond_rhs, false, rhs2))))))
1370 {
1371 gsi = gsi_for_stmt (cond);
1372 /* Moving ASSIGN might change VR of lhs, e.g. when moving u_6
1373 def-stmt in:
1374 if (n_5 != 0)
1375 goto <bb 3>;
1376 else
1377 goto <bb 4>;
1378
1379 <bb 3>:
1380 # RANGE [0, 4294967294]
1381 u_6 = n_5 + 4294967295;
1382
1383 <bb 4>:
1384 # u_3 = PHI <u_6(3), 4294967295(2)> */
1385 reset_flow_sensitive_info (lhs);
1386 if (INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
1387 {
1388 /* If available, we can use VR of phi result at least. */
1389 tree phires = gimple_phi_result (phi);
1390 struct range_info_def *phires_range_info
1391 = SSA_NAME_RANGE_INFO (phires);
1392 if (phires_range_info)
1393 duplicate_ssa_name_range_info (lhs, SSA_NAME_RANGE_TYPE (phires),
1394 phires_range_info);
1395 }
1396 gimple_stmt_iterator gsi_from;
1397 for (int i = prep_cnt - 1; i >= 0; --i)
1398 {
1399 tree plhs = gimple_assign_lhs (prep_stmt[i]);
1400 reset_flow_sensitive_info (plhs);
1401 gsi_from = gsi_for_stmt (prep_stmt[i]);
1402 gsi_move_before (&gsi_from, &gsi);
1403 }
1404 gsi_from = gsi_for_stmt (assign);
1405 gsi_move_before (&gsi_from, &gsi);
1406 replace_phi_edge_with_variable (cond_bb, e1, phi, lhs);
1407 return 2;
1408 }
1409
1410 return 0;
1411 }
1412
1413 /* The function minmax_replacement does the main work of doing the minmax
1414 replacement. Return true if the replacement is done. Otherwise return
1415 false.
1416 BB is the basic block where the replacement is going to be done on. ARG0
1417 is argument 0 from the PHI. Likewise for ARG1. */
1418
1419 static bool
minmax_replacement(basic_block cond_bb,basic_block middle_bb,edge e0,edge e1,gimple * phi,tree arg0,tree arg1)1420 minmax_replacement (basic_block cond_bb, basic_block middle_bb,
1421 edge e0, edge e1, gimple *phi,
1422 tree arg0, tree arg1)
1423 {
1424 tree result;
1425 edge true_edge, false_edge;
1426 enum tree_code minmax, ass_code;
1427 tree smaller, larger, arg_true, arg_false;
1428 gimple_stmt_iterator gsi, gsi_from;
1429
1430 tree type = TREE_TYPE (PHI_RESULT (phi));
1431
1432 /* The optimization may be unsafe due to NaNs. */
1433 if (HONOR_NANS (type) || HONOR_SIGNED_ZEROS (type))
1434 return false;
1435
1436 gcond *cond = as_a <gcond *> (last_stmt (cond_bb));
1437 enum tree_code cmp = gimple_cond_code (cond);
1438 tree rhs = gimple_cond_rhs (cond);
1439
1440 /* Turn EQ/NE of extreme values to order comparisons. */
1441 if ((cmp == NE_EXPR || cmp == EQ_EXPR)
1442 && TREE_CODE (rhs) == INTEGER_CST
1443 && INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
1444 {
1445 if (wi::eq_p (wi::to_wide (rhs), wi::min_value (TREE_TYPE (rhs))))
1446 {
1447 cmp = (cmp == EQ_EXPR) ? LT_EXPR : GE_EXPR;
1448 rhs = wide_int_to_tree (TREE_TYPE (rhs),
1449 wi::min_value (TREE_TYPE (rhs)) + 1);
1450 }
1451 else if (wi::eq_p (wi::to_wide (rhs), wi::max_value (TREE_TYPE (rhs))))
1452 {
1453 cmp = (cmp == EQ_EXPR) ? GT_EXPR : LE_EXPR;
1454 rhs = wide_int_to_tree (TREE_TYPE (rhs),
1455 wi::max_value (TREE_TYPE (rhs)) - 1);
1456 }
1457 }
1458
1459 /* This transformation is only valid for order comparisons. Record which
1460 operand is smaller/larger if the result of the comparison is true. */
1461 tree alt_smaller = NULL_TREE;
1462 tree alt_larger = NULL_TREE;
1463 if (cmp == LT_EXPR || cmp == LE_EXPR)
1464 {
1465 smaller = gimple_cond_lhs (cond);
1466 larger = rhs;
1467 /* If we have smaller < CST it is equivalent to smaller <= CST-1.
1468 Likewise smaller <= CST is equivalent to smaller < CST+1. */
1469 if (TREE_CODE (larger) == INTEGER_CST
1470 && INTEGRAL_TYPE_P (TREE_TYPE (larger)))
1471 {
1472 if (cmp == LT_EXPR)
1473 {
1474 wi::overflow_type overflow;
1475 wide_int alt = wi::sub (wi::to_wide (larger), 1,
1476 TYPE_SIGN (TREE_TYPE (larger)),
1477 &overflow);
1478 if (! overflow)
1479 alt_larger = wide_int_to_tree (TREE_TYPE (larger), alt);
1480 }
1481 else
1482 {
1483 wi::overflow_type overflow;
1484 wide_int alt = wi::add (wi::to_wide (larger), 1,
1485 TYPE_SIGN (TREE_TYPE (larger)),
1486 &overflow);
1487 if (! overflow)
1488 alt_larger = wide_int_to_tree (TREE_TYPE (larger), alt);
1489 }
1490 }
1491 }
1492 else if (cmp == GT_EXPR || cmp == GE_EXPR)
1493 {
1494 smaller = rhs;
1495 larger = gimple_cond_lhs (cond);
1496 /* If we have larger > CST it is equivalent to larger >= CST+1.
1497 Likewise larger >= CST is equivalent to larger > CST-1. */
1498 if (TREE_CODE (smaller) == INTEGER_CST
1499 && INTEGRAL_TYPE_P (TREE_TYPE (smaller)))
1500 {
1501 wi::overflow_type overflow;
1502 if (cmp == GT_EXPR)
1503 {
1504 wide_int alt = wi::add (wi::to_wide (smaller), 1,
1505 TYPE_SIGN (TREE_TYPE (smaller)),
1506 &overflow);
1507 if (! overflow)
1508 alt_smaller = wide_int_to_tree (TREE_TYPE (smaller), alt);
1509 }
1510 else
1511 {
1512 wide_int alt = wi::sub (wi::to_wide (smaller), 1,
1513 TYPE_SIGN (TREE_TYPE (smaller)),
1514 &overflow);
1515 if (! overflow)
1516 alt_smaller = wide_int_to_tree (TREE_TYPE (smaller), alt);
1517 }
1518 }
1519 }
1520 else
1521 return false;
1522
1523 /* Handle the special case of (signed_type)x < 0 being equivalent
1524 to x > MAX_VAL(signed_type) and (signed_type)x >= 0 equivalent
1525 to x <= MAX_VAL(signed_type). */
1526 if ((cmp == GE_EXPR || cmp == LT_EXPR)
1527 && INTEGRAL_TYPE_P (type)
1528 && TYPE_UNSIGNED (type)
1529 && integer_zerop (rhs))
1530 {
1531 tree op = gimple_cond_lhs (cond);
1532 if (TREE_CODE (op) == SSA_NAME
1533 && INTEGRAL_TYPE_P (TREE_TYPE (op))
1534 && !TYPE_UNSIGNED (TREE_TYPE (op)))
1535 {
1536 gimple *def_stmt = SSA_NAME_DEF_STMT (op);
1537 if (gimple_assign_cast_p (def_stmt))
1538 {
1539 tree op1 = gimple_assign_rhs1 (def_stmt);
1540 if (INTEGRAL_TYPE_P (TREE_TYPE (op1))
1541 && TYPE_UNSIGNED (TREE_TYPE (op1))
1542 && (TYPE_PRECISION (TREE_TYPE (op))
1543 == TYPE_PRECISION (TREE_TYPE (op1)))
1544 && useless_type_conversion_p (type, TREE_TYPE (op1)))
1545 {
1546 wide_int w1 = wi::max_value (TREE_TYPE (op));
1547 wide_int w2 = wi::add (w1, 1);
1548 if (cmp == LT_EXPR)
1549 {
1550 larger = op1;
1551 smaller = wide_int_to_tree (TREE_TYPE (op1), w1);
1552 alt_smaller = wide_int_to_tree (TREE_TYPE (op1), w2);
1553 alt_larger = NULL_TREE;
1554 }
1555 else
1556 {
1557 smaller = op1;
1558 larger = wide_int_to_tree (TREE_TYPE (op1), w1);
1559 alt_larger = wide_int_to_tree (TREE_TYPE (op1), w2);
1560 alt_smaller = NULL_TREE;
1561 }
1562 }
1563 }
1564 }
1565 }
1566
1567 /* We need to know which is the true edge and which is the false
1568 edge so that we know if have abs or negative abs. */
1569 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1570
1571 /* Forward the edges over the middle basic block. */
1572 if (true_edge->dest == middle_bb)
1573 true_edge = EDGE_SUCC (true_edge->dest, 0);
1574 if (false_edge->dest == middle_bb)
1575 false_edge = EDGE_SUCC (false_edge->dest, 0);
1576
1577 if (true_edge == e0)
1578 {
1579 gcc_assert (false_edge == e1);
1580 arg_true = arg0;
1581 arg_false = arg1;
1582 }
1583 else
1584 {
1585 gcc_assert (false_edge == e0);
1586 gcc_assert (true_edge == e1);
1587 arg_true = arg1;
1588 arg_false = arg0;
1589 }
1590
1591 if (empty_block_p (middle_bb))
1592 {
1593 if ((operand_equal_for_phi_arg_p (arg_true, smaller)
1594 || (alt_smaller
1595 && operand_equal_for_phi_arg_p (arg_true, alt_smaller)))
1596 && (operand_equal_for_phi_arg_p (arg_false, larger)
1597 || (alt_larger
1598 && operand_equal_for_phi_arg_p (arg_true, alt_larger))))
1599 {
1600 /* Case
1601
1602 if (smaller < larger)
1603 rslt = smaller;
1604 else
1605 rslt = larger; */
1606 minmax = MIN_EXPR;
1607 }
1608 else if ((operand_equal_for_phi_arg_p (arg_false, smaller)
1609 || (alt_smaller
1610 && operand_equal_for_phi_arg_p (arg_false, alt_smaller)))
1611 && (operand_equal_for_phi_arg_p (arg_true, larger)
1612 || (alt_larger
1613 && operand_equal_for_phi_arg_p (arg_true, alt_larger))))
1614 minmax = MAX_EXPR;
1615 else
1616 return false;
1617 }
1618 else
1619 {
1620 /* Recognize the following case, assuming d <= u:
1621
1622 if (a <= u)
1623 b = MAX (a, d);
1624 x = PHI <b, u>
1625
1626 This is equivalent to
1627
1628 b = MAX (a, d);
1629 x = MIN (b, u); */
1630
1631 gimple *assign = last_and_only_stmt (middle_bb);
1632 tree lhs, op0, op1, bound;
1633
1634 if (!assign
1635 || gimple_code (assign) != GIMPLE_ASSIGN)
1636 return false;
1637
1638 lhs = gimple_assign_lhs (assign);
1639 ass_code = gimple_assign_rhs_code (assign);
1640 if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
1641 return false;
1642 op0 = gimple_assign_rhs1 (assign);
1643 op1 = gimple_assign_rhs2 (assign);
1644
1645 if (true_edge->src == middle_bb)
1646 {
1647 /* We got here if the condition is true, i.e., SMALLER < LARGER. */
1648 if (!operand_equal_for_phi_arg_p (lhs, arg_true))
1649 return false;
1650
1651 if (operand_equal_for_phi_arg_p (arg_false, larger)
1652 || (alt_larger
1653 && operand_equal_for_phi_arg_p (arg_false, alt_larger)))
1654 {
1655 /* Case
1656
1657 if (smaller < larger)
1658 {
1659 r' = MAX_EXPR (smaller, bound)
1660 }
1661 r = PHI <r', larger> --> to be turned to MIN_EXPR. */
1662 if (ass_code != MAX_EXPR)
1663 return false;
1664
1665 minmax = MIN_EXPR;
1666 if (operand_equal_for_phi_arg_p (op0, smaller)
1667 || (alt_smaller
1668 && operand_equal_for_phi_arg_p (op0, alt_smaller)))
1669 bound = op1;
1670 else if (operand_equal_for_phi_arg_p (op1, smaller)
1671 || (alt_smaller
1672 && operand_equal_for_phi_arg_p (op1, alt_smaller)))
1673 bound = op0;
1674 else
1675 return false;
1676
1677 /* We need BOUND <= LARGER. */
1678 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
1679 bound, larger)))
1680 return false;
1681 }
1682 else if (operand_equal_for_phi_arg_p (arg_false, smaller)
1683 || (alt_smaller
1684 && operand_equal_for_phi_arg_p (arg_false, alt_smaller)))
1685 {
1686 /* Case
1687
1688 if (smaller < larger)
1689 {
1690 r' = MIN_EXPR (larger, bound)
1691 }
1692 r = PHI <r', smaller> --> to be turned to MAX_EXPR. */
1693 if (ass_code != MIN_EXPR)
1694 return false;
1695
1696 minmax = MAX_EXPR;
1697 if (operand_equal_for_phi_arg_p (op0, larger)
1698 || (alt_larger
1699 && operand_equal_for_phi_arg_p (op0, alt_larger)))
1700 bound = op1;
1701 else if (operand_equal_for_phi_arg_p (op1, larger)
1702 || (alt_larger
1703 && operand_equal_for_phi_arg_p (op1, alt_larger)))
1704 bound = op0;
1705 else
1706 return false;
1707
1708 /* We need BOUND >= SMALLER. */
1709 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
1710 bound, smaller)))
1711 return false;
1712 }
1713 else
1714 return false;
1715 }
1716 else
1717 {
1718 /* We got here if the condition is false, i.e., SMALLER > LARGER. */
1719 if (!operand_equal_for_phi_arg_p (lhs, arg_false))
1720 return false;
1721
1722 if (operand_equal_for_phi_arg_p (arg_true, larger)
1723 || (alt_larger
1724 && operand_equal_for_phi_arg_p (arg_true, alt_larger)))
1725 {
1726 /* Case
1727
1728 if (smaller > larger)
1729 {
1730 r' = MIN_EXPR (smaller, bound)
1731 }
1732 r = PHI <r', larger> --> to be turned to MAX_EXPR. */
1733 if (ass_code != MIN_EXPR)
1734 return false;
1735
1736 minmax = MAX_EXPR;
1737 if (operand_equal_for_phi_arg_p (op0, smaller)
1738 || (alt_smaller
1739 && operand_equal_for_phi_arg_p (op0, alt_smaller)))
1740 bound = op1;
1741 else if (operand_equal_for_phi_arg_p (op1, smaller)
1742 || (alt_smaller
1743 && operand_equal_for_phi_arg_p (op1, alt_smaller)))
1744 bound = op0;
1745 else
1746 return false;
1747
1748 /* We need BOUND >= LARGER. */
1749 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
1750 bound, larger)))
1751 return false;
1752 }
1753 else if (operand_equal_for_phi_arg_p (arg_true, smaller)
1754 || (alt_smaller
1755 && operand_equal_for_phi_arg_p (arg_true, alt_smaller)))
1756 {
1757 /* Case
1758
1759 if (smaller > larger)
1760 {
1761 r' = MAX_EXPR (larger, bound)
1762 }
1763 r = PHI <r', smaller> --> to be turned to MIN_EXPR. */
1764 if (ass_code != MAX_EXPR)
1765 return false;
1766
1767 minmax = MIN_EXPR;
1768 if (operand_equal_for_phi_arg_p (op0, larger))
1769 bound = op1;
1770 else if (operand_equal_for_phi_arg_p (op1, larger))
1771 bound = op0;
1772 else
1773 return false;
1774
1775 /* We need BOUND <= SMALLER. */
1776 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
1777 bound, smaller)))
1778 return false;
1779 }
1780 else
1781 return false;
1782 }
1783
1784 /* Move the statement from the middle block. */
1785 gsi = gsi_last_bb (cond_bb);
1786 gsi_from = gsi_last_nondebug_bb (middle_bb);
1787 reset_flow_sensitive_info (SINGLE_SSA_TREE_OPERAND (gsi_stmt (gsi_from),
1788 SSA_OP_DEF));
1789 gsi_move_before (&gsi_from, &gsi);
1790 }
1791
1792 /* Emit the statement to compute min/max. */
1793 gimple_seq stmts = NULL;
1794 tree phi_result = PHI_RESULT (phi);
1795 result = gimple_build (&stmts, minmax, TREE_TYPE (phi_result), arg0, arg1);
1796 /* Duplicate range info if we're the only things setting the target PHI. */
1797 if (!gimple_seq_empty_p (stmts)
1798 && EDGE_COUNT (gimple_bb (phi)->preds) == 2
1799 && !POINTER_TYPE_P (TREE_TYPE (phi_result))
1800 && SSA_NAME_RANGE_INFO (phi_result))
1801 duplicate_ssa_name_range_info (result, SSA_NAME_RANGE_TYPE (phi_result),
1802 SSA_NAME_RANGE_INFO (phi_result));
1803
1804 gsi = gsi_last_bb (cond_bb);
1805 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
1806
1807 replace_phi_edge_with_variable (cond_bb, e1, phi, result);
1808
1809 return true;
1810 }
1811
1812 /* Convert
1813
1814 <bb 2>
1815 if (b_4(D) != 0)
1816 goto <bb 3>
1817 else
1818 goto <bb 4>
1819
1820 <bb 3>
1821 _2 = (unsigned long) b_4(D);
1822 _9 = __builtin_popcountl (_2);
1823 OR
1824 _9 = __builtin_popcountl (b_4(D));
1825
1826 <bb 4>
1827 c_12 = PHI <0(2), _9(3)>
1828
1829 Into
1830 <bb 2>
1831 _2 = (unsigned long) b_4(D);
1832 _9 = __builtin_popcountl (_2);
1833 OR
1834 _9 = __builtin_popcountl (b_4(D));
1835
1836 <bb 4>
1837 c_12 = PHI <_9(2)>
1838
1839 Similarly for __builtin_clz or __builtin_ctz if
1840 C?Z_DEFINED_VALUE_AT_ZERO is 2, optab is present and
1841 instead of 0 above it uses the value from that macro. */
1842
1843 static bool
cond_removal_in_popcount_clz_ctz_pattern(basic_block cond_bb,basic_block middle_bb,edge e1,edge e2,gimple * phi,tree arg0,tree arg1)1844 cond_removal_in_popcount_clz_ctz_pattern (basic_block cond_bb,
1845 basic_block middle_bb,
1846 edge e1, edge e2, gimple *phi,
1847 tree arg0, tree arg1)
1848 {
1849 gimple *cond;
1850 gimple_stmt_iterator gsi, gsi_from;
1851 gimple *call;
1852 gimple *cast = NULL;
1853 tree lhs, arg;
1854
1855 /* Check that
1856 _2 = (unsigned long) b_4(D);
1857 _9 = __builtin_popcountl (_2);
1858 OR
1859 _9 = __builtin_popcountl (b_4(D));
1860 are the only stmts in the middle_bb. */
1861
1862 gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
1863 if (gsi_end_p (gsi))
1864 return false;
1865 cast = gsi_stmt (gsi);
1866 gsi_next_nondebug (&gsi);
1867 if (!gsi_end_p (gsi))
1868 {
1869 call = gsi_stmt (gsi);
1870 gsi_next_nondebug (&gsi);
1871 if (!gsi_end_p (gsi))
1872 return false;
1873 }
1874 else
1875 {
1876 call = cast;
1877 cast = NULL;
1878 }
1879
1880 /* Check that we have a popcount/clz/ctz builtin. */
1881 if (!is_gimple_call (call) || gimple_call_num_args (call) != 1)
1882 return false;
1883
1884 arg = gimple_call_arg (call, 0);
1885 lhs = gimple_get_lhs (call);
1886
1887 if (lhs == NULL_TREE)
1888 return false;
1889
1890 combined_fn cfn = gimple_call_combined_fn (call);
1891 internal_fn ifn = IFN_LAST;
1892 int val = 0;
1893 switch (cfn)
1894 {
1895 CASE_CFN_POPCOUNT:
1896 break;
1897 CASE_CFN_CLZ:
1898 if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
1899 {
1900 tree type = TREE_TYPE (arg);
1901 if (direct_internal_fn_supported_p (IFN_CLZ, type, OPTIMIZE_FOR_BOTH)
1902 && CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type),
1903 val) == 2)
1904 {
1905 ifn = IFN_CLZ;
1906 break;
1907 }
1908 }
1909 return false;
1910 CASE_CFN_CTZ:
1911 if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
1912 {
1913 tree type = TREE_TYPE (arg);
1914 if (direct_internal_fn_supported_p (IFN_CTZ, type, OPTIMIZE_FOR_BOTH)
1915 && CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type),
1916 val) == 2)
1917 {
1918 ifn = IFN_CTZ;
1919 break;
1920 }
1921 }
1922 return false;
1923 default:
1924 return false;
1925 }
1926
1927 if (cast)
1928 {
1929 /* We have a cast stmt feeding popcount/clz/ctz builtin. */
1930 /* Check that we have a cast prior to that. */
1931 if (gimple_code (cast) != GIMPLE_ASSIGN
1932 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (cast)))
1933 return false;
1934 /* Result of the cast stmt is the argument to the builtin. */
1935 if (arg != gimple_assign_lhs (cast))
1936 return false;
1937 arg = gimple_assign_rhs1 (cast);
1938 }
1939
1940 cond = last_stmt (cond_bb);
1941
1942 /* Cond_bb has a check for b_4 [!=|==] 0 before calling the popcount/clz/ctz
1943 builtin. */
1944 if (gimple_code (cond) != GIMPLE_COND
1945 || (gimple_cond_code (cond) != NE_EXPR
1946 && gimple_cond_code (cond) != EQ_EXPR)
1947 || !integer_zerop (gimple_cond_rhs (cond))
1948 || arg != gimple_cond_lhs (cond))
1949 return false;
1950
1951 /* Canonicalize. */
1952 if ((e2->flags & EDGE_TRUE_VALUE
1953 && gimple_cond_code (cond) == NE_EXPR)
1954 || (e1->flags & EDGE_TRUE_VALUE
1955 && gimple_cond_code (cond) == EQ_EXPR))
1956 {
1957 std::swap (arg0, arg1);
1958 std::swap (e1, e2);
1959 }
1960
1961 /* Check PHI arguments. */
1962 if (lhs != arg0
1963 || TREE_CODE (arg1) != INTEGER_CST
1964 || wi::to_wide (arg1) != val)
1965 return false;
1966
1967 /* And insert the popcount/clz/ctz builtin and cast stmt before the
1968 cond_bb. */
1969 gsi = gsi_last_bb (cond_bb);
1970 if (cast)
1971 {
1972 gsi_from = gsi_for_stmt (cast);
1973 gsi_move_before (&gsi_from, &gsi);
1974 reset_flow_sensitive_info (gimple_get_lhs (cast));
1975 }
1976 gsi_from = gsi_for_stmt (call);
1977 if (ifn == IFN_LAST || gimple_call_internal_p (call))
1978 gsi_move_before (&gsi_from, &gsi);
1979 else
1980 {
1981 /* For __builtin_c[lt]z* force .C[LT]Z ifn, because only
1982 the latter is well defined at zero. */
1983 call = gimple_build_call_internal (ifn, 1, gimple_call_arg (call, 0));
1984 gimple_call_set_lhs (call, lhs);
1985 gsi_insert_before (&gsi, call, GSI_SAME_STMT);
1986 gsi_remove (&gsi_from, true);
1987 }
1988 reset_flow_sensitive_info (lhs);
1989
1990 /* Now update the PHI and remove unneeded bbs. */
1991 replace_phi_edge_with_variable (cond_bb, e2, phi, lhs);
1992 return true;
1993 }
1994
1995 /* The function absolute_replacement does the main work of doing the absolute
1996 replacement. Return true if the replacement is done. Otherwise return
1997 false.
1998 bb is the basic block where the replacement is going to be done on. arg0
1999 is argument 0 from the phi. Likewise for arg1. */
2000
2001 static bool
abs_replacement(basic_block cond_bb,basic_block middle_bb,edge e0 ATTRIBUTE_UNUSED,edge e1,gimple * phi,tree arg0,tree arg1)2002 abs_replacement (basic_block cond_bb, basic_block middle_bb,
2003 edge e0 ATTRIBUTE_UNUSED, edge e1,
2004 gimple *phi, tree arg0, tree arg1)
2005 {
2006 tree result;
2007 gassign *new_stmt;
2008 gimple *cond;
2009 gimple_stmt_iterator gsi;
2010 edge true_edge, false_edge;
2011 gimple *assign;
2012 edge e;
2013 tree rhs, lhs;
2014 bool negate;
2015 enum tree_code cond_code;
2016
2017 /* If the type says honor signed zeros we cannot do this
2018 optimization. */
2019 if (HONOR_SIGNED_ZEROS (arg1))
2020 return false;
2021
2022 /* OTHER_BLOCK must have only one executable statement which must have the
2023 form arg0 = -arg1 or arg1 = -arg0. */
2024
2025 assign = last_and_only_stmt (middle_bb);
2026 /* If we did not find the proper negation assignment, then we cannot
2027 optimize. */
2028 if (assign == NULL)
2029 return false;
2030
2031 /* If we got here, then we have found the only executable statement
2032 in OTHER_BLOCK. If it is anything other than arg = -arg1 or
2033 arg1 = -arg0, then we cannot optimize. */
2034 if (gimple_code (assign) != GIMPLE_ASSIGN)
2035 return false;
2036
2037 lhs = gimple_assign_lhs (assign);
2038
2039 if (gimple_assign_rhs_code (assign) != NEGATE_EXPR)
2040 return false;
2041
2042 rhs = gimple_assign_rhs1 (assign);
2043
2044 /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */
2045 if (!(lhs == arg0 && rhs == arg1)
2046 && !(lhs == arg1 && rhs == arg0))
2047 return false;
2048
2049 cond = last_stmt (cond_bb);
2050 result = PHI_RESULT (phi);
2051
2052 /* Only relationals comparing arg[01] against zero are interesting. */
2053 cond_code = gimple_cond_code (cond);
2054 if (cond_code != GT_EXPR && cond_code != GE_EXPR
2055 && cond_code != LT_EXPR && cond_code != LE_EXPR)
2056 return false;
2057
2058 /* Make sure the conditional is arg[01] OP y. */
2059 if (gimple_cond_lhs (cond) != rhs)
2060 return false;
2061
2062 if (FLOAT_TYPE_P (TREE_TYPE (gimple_cond_rhs (cond)))
2063 ? real_zerop (gimple_cond_rhs (cond))
2064 : integer_zerop (gimple_cond_rhs (cond)))
2065 ;
2066 else
2067 return false;
2068
2069 /* We need to know which is the true edge and which is the false
2070 edge so that we know if have abs or negative abs. */
2071 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
2072
2073 /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
2074 will need to negate the result. Similarly for LT_EXPR/LE_EXPR if
2075 the false edge goes to OTHER_BLOCK. */
2076 if (cond_code == GT_EXPR || cond_code == GE_EXPR)
2077 e = true_edge;
2078 else
2079 e = false_edge;
2080
2081 if (e->dest == middle_bb)
2082 negate = true;
2083 else
2084 negate = false;
2085
2086 /* If the code negates only iff positive then make sure to not
2087 introduce undefined behavior when negating or computing the absolute.
2088 ??? We could use range info if present to check for arg1 == INT_MIN. */
2089 if (negate
2090 && (ANY_INTEGRAL_TYPE_P (TREE_TYPE (arg1))
2091 && ! TYPE_OVERFLOW_WRAPS (TREE_TYPE (arg1))))
2092 return false;
2093
2094 result = duplicate_ssa_name (result, NULL);
2095
2096 if (negate)
2097 lhs = make_ssa_name (TREE_TYPE (result));
2098 else
2099 lhs = result;
2100
2101 /* Build the modify expression with abs expression. */
2102 new_stmt = gimple_build_assign (lhs, ABS_EXPR, rhs);
2103
2104 gsi = gsi_last_bb (cond_bb);
2105 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
2106
2107 if (negate)
2108 {
2109 /* Get the right GSI. We want to insert after the recently
2110 added ABS_EXPR statement (which we know is the first statement
2111 in the block. */
2112 new_stmt = gimple_build_assign (result, NEGATE_EXPR, lhs);
2113
2114 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
2115 }
2116
2117 replace_phi_edge_with_variable (cond_bb, e1, phi, result);
2118
2119 /* Note that we optimized this PHI. */
2120 return true;
2121 }
2122
2123 /* Optimize x < 0 ? ~y : y into (x >> (prec-1)) ^ y. */
2124
2125 static bool
xor_replacement(basic_block cond_bb,basic_block middle_bb,edge e0 ATTRIBUTE_UNUSED,edge e1,gimple * phi,tree arg0,tree arg1)2126 xor_replacement (basic_block cond_bb, basic_block middle_bb,
2127 edge e0 ATTRIBUTE_UNUSED, edge e1,
2128 gimple *phi, tree arg0, tree arg1)
2129 {
2130 if (!INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
2131 return false;
2132
2133 /* OTHER_BLOCK must have only one executable statement which must have the
2134 form arg0 = ~arg1 or arg1 = ~arg0. */
2135
2136 gimple *assign = last_and_only_stmt (middle_bb);
2137 /* If we did not find the proper one's complement assignment, then we cannot
2138 optimize. */
2139 if (assign == NULL)
2140 return false;
2141
2142 /* If we got here, then we have found the only executable statement
2143 in OTHER_BLOCK. If it is anything other than arg = ~arg1 or
2144 arg1 = ~arg0, then we cannot optimize. */
2145 if (!is_gimple_assign (assign))
2146 return false;
2147
2148 if (gimple_assign_rhs_code (assign) != BIT_NOT_EXPR)
2149 return false;
2150
2151 tree lhs = gimple_assign_lhs (assign);
2152 tree rhs = gimple_assign_rhs1 (assign);
2153
2154 /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */
2155 if (!(lhs == arg0 && rhs == arg1) && !(lhs == arg1 && rhs == arg0))
2156 return false;
2157
2158 gimple *cond = last_stmt (cond_bb);
2159 tree result = PHI_RESULT (phi);
2160
2161 /* Only relationals comparing arg[01] against zero are interesting. */
2162 enum tree_code cond_code = gimple_cond_code (cond);
2163 if (cond_code != LT_EXPR && cond_code != GE_EXPR)
2164 return false;
2165
2166 /* Make sure the conditional is x OP 0. */
2167 tree clhs = gimple_cond_lhs (cond);
2168 if (TREE_CODE (clhs) != SSA_NAME
2169 || !INTEGRAL_TYPE_P (TREE_TYPE (clhs))
2170 || TYPE_UNSIGNED (TREE_TYPE (clhs))
2171 || TYPE_PRECISION (TREE_TYPE (clhs)) != TYPE_PRECISION (TREE_TYPE (arg1))
2172 || !integer_zerop (gimple_cond_rhs (cond)))
2173 return false;
2174
2175 /* We need to know which is the true edge and which is the false
2176 edge so that we know if have xor or inverted xor. */
2177 edge true_edge, false_edge;
2178 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
2179
2180 /* For GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
2181 will need to invert the result. Similarly for LT_EXPR if
2182 the false edge goes to OTHER_BLOCK. */
2183 edge e;
2184 if (cond_code == GE_EXPR)
2185 e = true_edge;
2186 else
2187 e = false_edge;
2188
2189 bool invert = e->dest == middle_bb;
2190
2191 result = duplicate_ssa_name (result, NULL);
2192
2193 gimple_stmt_iterator gsi = gsi_last_bb (cond_bb);
2194
2195 int prec = TYPE_PRECISION (TREE_TYPE (clhs));
2196 gimple *new_stmt
2197 = gimple_build_assign (make_ssa_name (TREE_TYPE (clhs)), RSHIFT_EXPR, clhs,
2198 build_int_cst (integer_type_node, prec - 1));
2199 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
2200
2201 if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (clhs)))
2202 {
2203 new_stmt = gimple_build_assign (make_ssa_name (TREE_TYPE (result)),
2204 NOP_EXPR, gimple_assign_lhs (new_stmt));
2205 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
2206 }
2207 lhs = gimple_assign_lhs (new_stmt);
2208
2209 if (invert)
2210 {
2211 new_stmt = gimple_build_assign (make_ssa_name (TREE_TYPE (result)),
2212 BIT_NOT_EXPR, rhs);
2213 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
2214 rhs = gimple_assign_lhs (new_stmt);
2215 }
2216
2217 new_stmt = gimple_build_assign (result, BIT_XOR_EXPR, lhs, rhs);
2218 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
2219
2220 replace_phi_edge_with_variable (cond_bb, e1, phi, result);
2221
2222 /* Note that we optimized this PHI. */
2223 return true;
2224 }
2225
2226 /* Auxiliary functions to determine the set of memory accesses which
2227 can't trap because they are preceded by accesses to the same memory
2228 portion. We do that for MEM_REFs, so we only need to track
2229 the SSA_NAME of the pointer indirectly referenced. The algorithm
2230 simply is a walk over all instructions in dominator order. When
2231 we see an MEM_REF we determine if we've already seen a same
2232 ref anywhere up to the root of the dominator tree. If we do the
2233 current access can't trap. If we don't see any dominating access
2234 the current access might trap, but might also make later accesses
2235 non-trapping, so we remember it. We need to be careful with loads
2236 or stores, for instance a load might not trap, while a store would,
2237 so if we see a dominating read access this doesn't mean that a later
2238 write access would not trap. Hence we also need to differentiate the
2239 type of access(es) seen.
2240
2241 ??? We currently are very conservative and assume that a load might
2242 trap even if a store doesn't (write-only memory). This probably is
2243 overly conservative.
2244
2245 We currently support a special case that for !TREE_ADDRESSABLE automatic
2246 variables, it could ignore whether something is a load or store because the
2247 local stack should be always writable. */
2248
2249 /* A hash-table of references (MEM_REF/ARRAY_REF/COMPONENT_REF), and in which
2250 basic block an *_REF through it was seen, which would constitute a
2251 no-trap region for same accesses.
2252
2253 Size is needed to support 2 MEM_REFs of different types, like
2254 MEM<double>(s_1) and MEM<long>(s_1), which would compare equal with
2255 OEP_ADDRESS_OF. */
2256 struct ref_to_bb
2257 {
2258 tree exp;
2259 HOST_WIDE_INT size;
2260 unsigned int phase;
2261 basic_block bb;
2262 };
2263
2264 /* Hashtable helpers. */
2265
2266 struct refs_hasher : free_ptr_hash<ref_to_bb>
2267 {
2268 static inline hashval_t hash (const ref_to_bb *);
2269 static inline bool equal (const ref_to_bb *, const ref_to_bb *);
2270 };
2271
2272 /* Used for quick clearing of the hash-table when we see calls.
2273 Hash entries with phase < nt_call_phase are invalid. */
2274 static unsigned int nt_call_phase;
2275
2276 /* The hash function. */
2277
2278 inline hashval_t
hash(const ref_to_bb * n)2279 refs_hasher::hash (const ref_to_bb *n)
2280 {
2281 inchash::hash hstate;
2282 inchash::add_expr (n->exp, hstate, OEP_ADDRESS_OF);
2283 hstate.add_hwi (n->size);
2284 return hstate.end ();
2285 }
2286
2287 /* The equality function of *P1 and *P2. */
2288
2289 inline bool
equal(const ref_to_bb * n1,const ref_to_bb * n2)2290 refs_hasher::equal (const ref_to_bb *n1, const ref_to_bb *n2)
2291 {
2292 return operand_equal_p (n1->exp, n2->exp, OEP_ADDRESS_OF)
2293 && n1->size == n2->size;
2294 }
2295
2296 class nontrapping_dom_walker : public dom_walker
2297 {
2298 public:
nontrapping_dom_walker(cdi_direction direction,hash_set<tree> * ps)2299 nontrapping_dom_walker (cdi_direction direction, hash_set<tree> *ps)
2300 : dom_walker (direction), m_nontrapping (ps), m_seen_refs (128)
2301 {}
2302
2303 virtual edge before_dom_children (basic_block);
2304 virtual void after_dom_children (basic_block);
2305
2306 private:
2307
2308 /* We see the expression EXP in basic block BB. If it's an interesting
2309 expression (an MEM_REF through an SSA_NAME) possibly insert the
2310 expression into the set NONTRAP or the hash table of seen expressions.
2311 STORE is true if this expression is on the LHS, otherwise it's on
2312 the RHS. */
2313 void add_or_mark_expr (basic_block, tree, bool);
2314
2315 hash_set<tree> *m_nontrapping;
2316
2317 /* The hash table for remembering what we've seen. */
2318 hash_table<refs_hasher> m_seen_refs;
2319 };
2320
2321 /* Called by walk_dominator_tree, when entering the block BB. */
2322 edge
before_dom_children(basic_block bb)2323 nontrapping_dom_walker::before_dom_children (basic_block bb)
2324 {
2325 edge e;
2326 edge_iterator ei;
2327 gimple_stmt_iterator gsi;
2328
2329 /* If we haven't seen all our predecessors, clear the hash-table. */
2330 FOR_EACH_EDGE (e, ei, bb->preds)
2331 if ((((size_t)e->src->aux) & 2) == 0)
2332 {
2333 nt_call_phase++;
2334 break;
2335 }
2336
2337 /* Mark this BB as being on the path to dominator root and as visited. */
2338 bb->aux = (void*)(1 | 2);
2339
2340 /* And walk the statements in order. */
2341 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2342 {
2343 gimple *stmt = gsi_stmt (gsi);
2344
2345 if ((gimple_code (stmt) == GIMPLE_ASM && gimple_vdef (stmt))
2346 || (is_gimple_call (stmt)
2347 && (!nonfreeing_call_p (stmt) || !nonbarrier_call_p (stmt))))
2348 nt_call_phase++;
2349 else if (gimple_assign_single_p (stmt) && !gimple_has_volatile_ops (stmt))
2350 {
2351 add_or_mark_expr (bb, gimple_assign_lhs (stmt), true);
2352 add_or_mark_expr (bb, gimple_assign_rhs1 (stmt), false);
2353 }
2354 }
2355 return NULL;
2356 }
2357
2358 /* Called by walk_dominator_tree, when basic block BB is exited. */
2359 void
after_dom_children(basic_block bb)2360 nontrapping_dom_walker::after_dom_children (basic_block bb)
2361 {
2362 /* This BB isn't on the path to dominator root anymore. */
2363 bb->aux = (void*)2;
2364 }
2365
2366 /* We see the expression EXP in basic block BB. If it's an interesting
2367 expression of:
2368 1) MEM_REF
2369 2) ARRAY_REF
2370 3) COMPONENT_REF
2371 possibly insert the expression into the set NONTRAP or the hash table
2372 of seen expressions. STORE is true if this expression is on the LHS,
2373 otherwise it's on the RHS. */
2374 void
add_or_mark_expr(basic_block bb,tree exp,bool store)2375 nontrapping_dom_walker::add_or_mark_expr (basic_block bb, tree exp, bool store)
2376 {
2377 HOST_WIDE_INT size;
2378
2379 if ((TREE_CODE (exp) == MEM_REF || TREE_CODE (exp) == ARRAY_REF
2380 || TREE_CODE (exp) == COMPONENT_REF)
2381 && (size = int_size_in_bytes (TREE_TYPE (exp))) > 0)
2382 {
2383 struct ref_to_bb map;
2384 ref_to_bb **slot;
2385 struct ref_to_bb *r2bb;
2386 basic_block found_bb = 0;
2387
2388 if (!store)
2389 {
2390 tree base = get_base_address (exp);
2391 /* Only record a LOAD of a local variable without address-taken, as
2392 the local stack is always writable. This allows cselim on a STORE
2393 with a dominating LOAD. */
2394 if (!auto_var_p (base) || TREE_ADDRESSABLE (base))
2395 return;
2396 }
2397
2398 /* Try to find the last seen *_REF, which can trap. */
2399 map.exp = exp;
2400 map.size = size;
2401 slot = m_seen_refs.find_slot (&map, INSERT);
2402 r2bb = *slot;
2403 if (r2bb && r2bb->phase >= nt_call_phase)
2404 found_bb = r2bb->bb;
2405
2406 /* If we've found a trapping *_REF, _and_ it dominates EXP
2407 (it's in a basic block on the path from us to the dominator root)
2408 then we can't trap. */
2409 if (found_bb && (((size_t)found_bb->aux) & 1) == 1)
2410 {
2411 m_nontrapping->add (exp);
2412 }
2413 else
2414 {
2415 /* EXP might trap, so insert it into the hash table. */
2416 if (r2bb)
2417 {
2418 r2bb->phase = nt_call_phase;
2419 r2bb->bb = bb;
2420 }
2421 else
2422 {
2423 r2bb = XNEW (struct ref_to_bb);
2424 r2bb->phase = nt_call_phase;
2425 r2bb->bb = bb;
2426 r2bb->exp = exp;
2427 r2bb->size = size;
2428 *slot = r2bb;
2429 }
2430 }
2431 }
2432 }
2433
2434 /* This is the entry point of gathering non trapping memory accesses.
2435 It will do a dominator walk over the whole function, and it will
2436 make use of the bb->aux pointers. It returns a set of trees
2437 (the MEM_REFs itself) which can't trap. */
2438 static hash_set<tree> *
get_non_trapping(void)2439 get_non_trapping (void)
2440 {
2441 nt_call_phase = 0;
2442 hash_set<tree> *nontrap = new hash_set<tree>;
2443
2444 nontrapping_dom_walker (CDI_DOMINATORS, nontrap)
2445 .walk (cfun->cfg->x_entry_block_ptr);
2446
2447 clear_aux_for_blocks ();
2448 return nontrap;
2449 }
2450
2451 /* Do the main work of conditional store replacement. We already know
2452 that the recognized pattern looks like so:
2453
2454 split:
2455 if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
2456 MIDDLE_BB:
2457 something
2458 fallthrough (edge E0)
2459 JOIN_BB:
2460 some more
2461
2462 We check that MIDDLE_BB contains only one store, that that store
2463 doesn't trap (not via NOTRAP, but via checking if an access to the same
2464 memory location dominates us, or the store is to a local addressable
2465 object) and that the store has a "simple" RHS. */
2466
2467 static bool
cond_store_replacement(basic_block middle_bb,basic_block join_bb,edge e0,edge e1,hash_set<tree> * nontrap)2468 cond_store_replacement (basic_block middle_bb, basic_block join_bb,
2469 edge e0, edge e1, hash_set<tree> *nontrap)
2470 {
2471 gimple *assign = last_and_only_stmt (middle_bb);
2472 tree lhs, rhs, name, name2;
2473 gphi *newphi;
2474 gassign *new_stmt;
2475 gimple_stmt_iterator gsi;
2476 location_t locus;
2477
2478 /* Check if middle_bb contains of only one store. */
2479 if (!assign
2480 || !gimple_assign_single_p (assign)
2481 || gimple_has_volatile_ops (assign))
2482 return false;
2483
2484 /* And no PHI nodes so all uses in the single stmt are also
2485 available where we insert to. */
2486 if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
2487 return false;
2488
2489 locus = gimple_location (assign);
2490 lhs = gimple_assign_lhs (assign);
2491 rhs = gimple_assign_rhs1 (assign);
2492 if ((TREE_CODE (lhs) != MEM_REF
2493 && TREE_CODE (lhs) != ARRAY_REF
2494 && TREE_CODE (lhs) != COMPONENT_REF)
2495 || !is_gimple_reg_type (TREE_TYPE (lhs)))
2496 return false;
2497
2498 /* Prove that we can move the store down. We could also check
2499 TREE_THIS_NOTRAP here, but in that case we also could move stores,
2500 whose value is not available readily, which we want to avoid. */
2501 if (!nontrap->contains (lhs))
2502 {
2503 /* If LHS is an access to a local variable without address-taken
2504 (or when we allow data races) and known not to trap, we could
2505 always safely move down the store. */
2506 tree base = get_base_address (lhs);
2507 if (!auto_var_p (base)
2508 || (TREE_ADDRESSABLE (base) && !flag_store_data_races)
2509 || tree_could_trap_p (lhs))
2510 return false;
2511 }
2512
2513 /* Now we've checked the constraints, so do the transformation:
2514 1) Remove the single store. */
2515 gsi = gsi_for_stmt (assign);
2516 unlink_stmt_vdef (assign);
2517 gsi_remove (&gsi, true);
2518 release_defs (assign);
2519
2520 /* Make both store and load use alias-set zero as we have to
2521 deal with the case of the store being a conditional change
2522 of the dynamic type. */
2523 lhs = unshare_expr (lhs);
2524 tree *basep = &lhs;
2525 while (handled_component_p (*basep))
2526 basep = &TREE_OPERAND (*basep, 0);
2527 if (TREE_CODE (*basep) == MEM_REF
2528 || TREE_CODE (*basep) == TARGET_MEM_REF)
2529 TREE_OPERAND (*basep, 1)
2530 = fold_convert (ptr_type_node, TREE_OPERAND (*basep, 1));
2531 else
2532 *basep = build2 (MEM_REF, TREE_TYPE (*basep),
2533 build_fold_addr_expr (*basep),
2534 build_zero_cst (ptr_type_node));
2535
2536 /* 2) Insert a load from the memory of the store to the temporary
2537 on the edge which did not contain the store. */
2538 name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
2539 new_stmt = gimple_build_assign (name, lhs);
2540 gimple_set_location (new_stmt, locus);
2541 lhs = unshare_expr (lhs);
2542 /* Set TREE_NO_WARNING on the rhs of the load to avoid uninit
2543 warnings. */
2544 TREE_NO_WARNING (gimple_assign_rhs1 (new_stmt)) = 1;
2545 gsi_insert_on_edge (e1, new_stmt);
2546
2547 /* 3) Create a PHI node at the join block, with one argument
2548 holding the old RHS, and the other holding the temporary
2549 where we stored the old memory contents. */
2550 name2 = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
2551 newphi = create_phi_node (name2, join_bb);
2552 add_phi_arg (newphi, rhs, e0, locus);
2553 add_phi_arg (newphi, name, e1, locus);
2554
2555 new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
2556
2557 /* 4) Insert that PHI node. */
2558 gsi = gsi_after_labels (join_bb);
2559 if (gsi_end_p (gsi))
2560 {
2561 gsi = gsi_last_bb (join_bb);
2562 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
2563 }
2564 else
2565 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
2566
2567 if (dump_file && (dump_flags & TDF_DETAILS))
2568 {
2569 fprintf (dump_file, "\nConditional store replacement happened!");
2570 fprintf (dump_file, "\nReplaced the store with a load.");
2571 fprintf (dump_file, "\nInserted a new PHI statement in joint block:\n");
2572 print_gimple_stmt (dump_file, new_stmt, 0, TDF_VOPS|TDF_MEMSYMS);
2573 }
2574
2575 return true;
2576 }
2577
2578 /* Do the main work of conditional store replacement. */
2579
2580 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)2581 cond_if_else_store_replacement_1 (basic_block then_bb, basic_block else_bb,
2582 basic_block join_bb, gimple *then_assign,
2583 gimple *else_assign)
2584 {
2585 tree lhs_base, lhs, then_rhs, else_rhs, name;
2586 location_t then_locus, else_locus;
2587 gimple_stmt_iterator gsi;
2588 gphi *newphi;
2589 gassign *new_stmt;
2590
2591 if (then_assign == NULL
2592 || !gimple_assign_single_p (then_assign)
2593 || gimple_clobber_p (then_assign)
2594 || gimple_has_volatile_ops (then_assign)
2595 || else_assign == NULL
2596 || !gimple_assign_single_p (else_assign)
2597 || gimple_clobber_p (else_assign)
2598 || gimple_has_volatile_ops (else_assign))
2599 return false;
2600
2601 lhs = gimple_assign_lhs (then_assign);
2602 if (!is_gimple_reg_type (TREE_TYPE (lhs))
2603 || !operand_equal_p (lhs, gimple_assign_lhs (else_assign), 0))
2604 return false;
2605
2606 lhs_base = get_base_address (lhs);
2607 if (lhs_base == NULL_TREE
2608 || (!DECL_P (lhs_base) && TREE_CODE (lhs_base) != MEM_REF))
2609 return false;
2610
2611 then_rhs = gimple_assign_rhs1 (then_assign);
2612 else_rhs = gimple_assign_rhs1 (else_assign);
2613 then_locus = gimple_location (then_assign);
2614 else_locus = gimple_location (else_assign);
2615
2616 /* Now we've checked the constraints, so do the transformation:
2617 1) Remove the stores. */
2618 gsi = gsi_for_stmt (then_assign);
2619 unlink_stmt_vdef (then_assign);
2620 gsi_remove (&gsi, true);
2621 release_defs (then_assign);
2622
2623 gsi = gsi_for_stmt (else_assign);
2624 unlink_stmt_vdef (else_assign);
2625 gsi_remove (&gsi, true);
2626 release_defs (else_assign);
2627
2628 /* 2) Create a PHI node at the join block, with one argument
2629 holding the old RHS, and the other holding the temporary
2630 where we stored the old memory contents. */
2631 name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
2632 newphi = create_phi_node (name, join_bb);
2633 add_phi_arg (newphi, then_rhs, EDGE_SUCC (then_bb, 0), then_locus);
2634 add_phi_arg (newphi, else_rhs, EDGE_SUCC (else_bb, 0), else_locus);
2635
2636 new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
2637
2638 /* 3) Insert that PHI node. */
2639 gsi = gsi_after_labels (join_bb);
2640 if (gsi_end_p (gsi))
2641 {
2642 gsi = gsi_last_bb (join_bb);
2643 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
2644 }
2645 else
2646 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
2647
2648 return true;
2649 }
2650
2651 /* Return the single store in BB with VDEF or NULL if there are
2652 other stores in the BB or loads following the store. */
2653
2654 static gimple *
single_trailing_store_in_bb(basic_block bb,tree vdef)2655 single_trailing_store_in_bb (basic_block bb, tree vdef)
2656 {
2657 if (SSA_NAME_IS_DEFAULT_DEF (vdef))
2658 return NULL;
2659 gimple *store = SSA_NAME_DEF_STMT (vdef);
2660 if (gimple_bb (store) != bb
2661 || gimple_code (store) == GIMPLE_PHI)
2662 return NULL;
2663
2664 /* Verify there is no other store in this BB. */
2665 if (!SSA_NAME_IS_DEFAULT_DEF (gimple_vuse (store))
2666 && gimple_bb (SSA_NAME_DEF_STMT (gimple_vuse (store))) == bb
2667 && gimple_code (SSA_NAME_DEF_STMT (gimple_vuse (store))) != GIMPLE_PHI)
2668 return NULL;
2669
2670 /* Verify there is no load or store after the store. */
2671 use_operand_p use_p;
2672 imm_use_iterator imm_iter;
2673 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_vdef (store))
2674 if (USE_STMT (use_p) != store
2675 && gimple_bb (USE_STMT (use_p)) == bb)
2676 return NULL;
2677
2678 return store;
2679 }
2680
2681 /* Conditional store replacement. We already know
2682 that the recognized pattern looks like so:
2683
2684 split:
2685 if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
2686 THEN_BB:
2687 ...
2688 X = Y;
2689 ...
2690 goto JOIN_BB;
2691 ELSE_BB:
2692 ...
2693 X = Z;
2694 ...
2695 fallthrough (edge E0)
2696 JOIN_BB:
2697 some more
2698
2699 We check that it is safe to sink the store to JOIN_BB by verifying that
2700 there are no read-after-write or write-after-write dependencies in
2701 THEN_BB and ELSE_BB. */
2702
2703 static bool
cond_if_else_store_replacement(basic_block then_bb,basic_block else_bb,basic_block join_bb)2704 cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb,
2705 basic_block join_bb)
2706 {
2707 vec<data_reference_p> then_datarefs, else_datarefs;
2708 vec<ddr_p> then_ddrs, else_ddrs;
2709 gimple *then_store, *else_store;
2710 bool found, ok = false, res;
2711 struct data_dependence_relation *ddr;
2712 data_reference_p then_dr, else_dr;
2713 int i, j;
2714 tree then_lhs, else_lhs;
2715 basic_block blocks[3];
2716
2717 /* Handle the case with single store in THEN_BB and ELSE_BB. That is
2718 cheap enough to always handle as it allows us to elide dependence
2719 checking. */
2720 gphi *vphi = NULL;
2721 for (gphi_iterator si = gsi_start_phis (join_bb); !gsi_end_p (si);
2722 gsi_next (&si))
2723 if (virtual_operand_p (gimple_phi_result (si.phi ())))
2724 {
2725 vphi = si.phi ();
2726 break;
2727 }
2728 if (!vphi)
2729 return false;
2730 tree then_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (then_bb));
2731 tree else_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (else_bb));
2732 gimple *then_assign = single_trailing_store_in_bb (then_bb, then_vdef);
2733 if (then_assign)
2734 {
2735 gimple *else_assign = single_trailing_store_in_bb (else_bb, else_vdef);
2736 if (else_assign)
2737 return cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
2738 then_assign, else_assign);
2739 }
2740
2741 /* If either vectorization or if-conversion is disabled then do
2742 not sink any stores. */
2743 if (param_max_stores_to_sink == 0
2744 || (!flag_tree_loop_vectorize && !flag_tree_slp_vectorize)
2745 || !flag_tree_loop_if_convert)
2746 return false;
2747
2748 /* Find data references. */
2749 then_datarefs.create (1);
2750 else_datarefs.create (1);
2751 if ((find_data_references_in_bb (NULL, then_bb, &then_datarefs)
2752 == chrec_dont_know)
2753 || !then_datarefs.length ()
2754 || (find_data_references_in_bb (NULL, else_bb, &else_datarefs)
2755 == chrec_dont_know)
2756 || !else_datarefs.length ())
2757 {
2758 free_data_refs (then_datarefs);
2759 free_data_refs (else_datarefs);
2760 return false;
2761 }
2762
2763 /* Find pairs of stores with equal LHS. */
2764 auto_vec<gimple *, 1> then_stores, else_stores;
2765 FOR_EACH_VEC_ELT (then_datarefs, i, then_dr)
2766 {
2767 if (DR_IS_READ (then_dr))
2768 continue;
2769
2770 then_store = DR_STMT (then_dr);
2771 then_lhs = gimple_get_lhs (then_store);
2772 if (then_lhs == NULL_TREE)
2773 continue;
2774 found = false;
2775
2776 FOR_EACH_VEC_ELT (else_datarefs, j, else_dr)
2777 {
2778 if (DR_IS_READ (else_dr))
2779 continue;
2780
2781 else_store = DR_STMT (else_dr);
2782 else_lhs = gimple_get_lhs (else_store);
2783 if (else_lhs == NULL_TREE)
2784 continue;
2785
2786 if (operand_equal_p (then_lhs, else_lhs, 0))
2787 {
2788 found = true;
2789 break;
2790 }
2791 }
2792
2793 if (!found)
2794 continue;
2795
2796 then_stores.safe_push (then_store);
2797 else_stores.safe_push (else_store);
2798 }
2799
2800 /* No pairs of stores found. */
2801 if (!then_stores.length ()
2802 || then_stores.length () > (unsigned) param_max_stores_to_sink)
2803 {
2804 free_data_refs (then_datarefs);
2805 free_data_refs (else_datarefs);
2806 return false;
2807 }
2808
2809 /* Compute and check data dependencies in both basic blocks. */
2810 then_ddrs.create (1);
2811 else_ddrs.create (1);
2812 if (!compute_all_dependences (then_datarefs, &then_ddrs,
2813 vNULL, false)
2814 || !compute_all_dependences (else_datarefs, &else_ddrs,
2815 vNULL, false))
2816 {
2817 free_dependence_relations (then_ddrs);
2818 free_dependence_relations (else_ddrs);
2819 free_data_refs (then_datarefs);
2820 free_data_refs (else_datarefs);
2821 return false;
2822 }
2823 blocks[0] = then_bb;
2824 blocks[1] = else_bb;
2825 blocks[2] = join_bb;
2826 renumber_gimple_stmt_uids_in_blocks (blocks, 3);
2827
2828 /* Check that there are no read-after-write or write-after-write dependencies
2829 in THEN_BB. */
2830 FOR_EACH_VEC_ELT (then_ddrs, i, ddr)
2831 {
2832 struct data_reference *dra = DDR_A (ddr);
2833 struct data_reference *drb = DDR_B (ddr);
2834
2835 if (DDR_ARE_DEPENDENT (ddr) != chrec_known
2836 && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
2837 && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
2838 || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
2839 && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
2840 || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
2841 {
2842 free_dependence_relations (then_ddrs);
2843 free_dependence_relations (else_ddrs);
2844 free_data_refs (then_datarefs);
2845 free_data_refs (else_datarefs);
2846 return false;
2847 }
2848 }
2849
2850 /* Check that there are no read-after-write or write-after-write dependencies
2851 in ELSE_BB. */
2852 FOR_EACH_VEC_ELT (else_ddrs, i, ddr)
2853 {
2854 struct data_reference *dra = DDR_A (ddr);
2855 struct data_reference *drb = DDR_B (ddr);
2856
2857 if (DDR_ARE_DEPENDENT (ddr) != chrec_known
2858 && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
2859 && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
2860 || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
2861 && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
2862 || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
2863 {
2864 free_dependence_relations (then_ddrs);
2865 free_dependence_relations (else_ddrs);
2866 free_data_refs (then_datarefs);
2867 free_data_refs (else_datarefs);
2868 return false;
2869 }
2870 }
2871
2872 /* Sink stores with same LHS. */
2873 FOR_EACH_VEC_ELT (then_stores, i, then_store)
2874 {
2875 else_store = else_stores[i];
2876 res = cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
2877 then_store, else_store);
2878 ok = ok || res;
2879 }
2880
2881 free_dependence_relations (then_ddrs);
2882 free_dependence_relations (else_ddrs);
2883 free_data_refs (then_datarefs);
2884 free_data_refs (else_datarefs);
2885
2886 return ok;
2887 }
2888
2889 /* Return TRUE if STMT has a VUSE whose corresponding VDEF is in BB. */
2890
2891 static bool
local_mem_dependence(gimple * stmt,basic_block bb)2892 local_mem_dependence (gimple *stmt, basic_block bb)
2893 {
2894 tree vuse = gimple_vuse (stmt);
2895 gimple *def;
2896
2897 if (!vuse)
2898 return false;
2899
2900 def = SSA_NAME_DEF_STMT (vuse);
2901 return (def && gimple_bb (def) == bb);
2902 }
2903
2904 /* Given a "diamond" control-flow pattern where BB0 tests a condition,
2905 BB1 and BB2 are "then" and "else" blocks dependent on this test,
2906 and BB3 rejoins control flow following BB1 and BB2, look for
2907 opportunities to hoist loads as follows. If BB3 contains a PHI of
2908 two loads, one each occurring in BB1 and BB2, and the loads are
2909 provably of adjacent fields in the same structure, then move both
2910 loads into BB0. Of course this can only be done if there are no
2911 dependencies preventing such motion.
2912
2913 One of the hoisted loads will always be speculative, so the
2914 transformation is currently conservative:
2915
2916 - The fields must be strictly adjacent.
2917 - The two fields must occupy a single memory block that is
2918 guaranteed to not cross a page boundary.
2919
2920 The last is difficult to prove, as such memory blocks should be
2921 aligned on the minimum of the stack alignment boundary and the
2922 alignment guaranteed by heap allocation interfaces. Thus we rely
2923 on a parameter for the alignment value.
2924
2925 Provided a good value is used for the last case, the first
2926 restriction could possibly be relaxed. */
2927
2928 static void
hoist_adjacent_loads(basic_block bb0,basic_block bb1,basic_block bb2,basic_block bb3)2929 hoist_adjacent_loads (basic_block bb0, basic_block bb1,
2930 basic_block bb2, basic_block bb3)
2931 {
2932 int param_align = param_l1_cache_line_size;
2933 unsigned param_align_bits = (unsigned) (param_align * BITS_PER_UNIT);
2934 gphi_iterator gsi;
2935
2936 /* Walk the phis in bb3 looking for an opportunity. We are looking
2937 for phis of two SSA names, one each of which is defined in bb1 and
2938 bb2. */
2939 for (gsi = gsi_start_phis (bb3); !gsi_end_p (gsi); gsi_next (&gsi))
2940 {
2941 gphi *phi_stmt = gsi.phi ();
2942 gimple *def1, *def2;
2943 tree arg1, arg2, ref1, ref2, field1, field2;
2944 tree tree_offset1, tree_offset2, tree_size2, next;
2945 int offset1, offset2, size2;
2946 unsigned align1;
2947 gimple_stmt_iterator gsi2;
2948 basic_block bb_for_def1, bb_for_def2;
2949
2950 if (gimple_phi_num_args (phi_stmt) != 2
2951 || virtual_operand_p (gimple_phi_result (phi_stmt)))
2952 continue;
2953
2954 arg1 = gimple_phi_arg_def (phi_stmt, 0);
2955 arg2 = gimple_phi_arg_def (phi_stmt, 1);
2956
2957 if (TREE_CODE (arg1) != SSA_NAME
2958 || TREE_CODE (arg2) != SSA_NAME
2959 || SSA_NAME_IS_DEFAULT_DEF (arg1)
2960 || SSA_NAME_IS_DEFAULT_DEF (arg2))
2961 continue;
2962
2963 def1 = SSA_NAME_DEF_STMT (arg1);
2964 def2 = SSA_NAME_DEF_STMT (arg2);
2965
2966 if ((gimple_bb (def1) != bb1 || gimple_bb (def2) != bb2)
2967 && (gimple_bb (def2) != bb1 || gimple_bb (def1) != bb2))
2968 continue;
2969
2970 /* Check the mode of the arguments to be sure a conditional move
2971 can be generated for it. */
2972 if (optab_handler (movcc_optab, TYPE_MODE (TREE_TYPE (arg1)))
2973 == CODE_FOR_nothing)
2974 continue;
2975
2976 /* Both statements must be assignments whose RHS is a COMPONENT_REF. */
2977 if (!gimple_assign_single_p (def1)
2978 || !gimple_assign_single_p (def2)
2979 || gimple_has_volatile_ops (def1)
2980 || gimple_has_volatile_ops (def2))
2981 continue;
2982
2983 ref1 = gimple_assign_rhs1 (def1);
2984 ref2 = gimple_assign_rhs1 (def2);
2985
2986 if (TREE_CODE (ref1) != COMPONENT_REF
2987 || TREE_CODE (ref2) != COMPONENT_REF)
2988 continue;
2989
2990 /* The zeroth operand of the two component references must be
2991 identical. It is not sufficient to compare get_base_address of
2992 the two references, because this could allow for different
2993 elements of the same array in the two trees. It is not safe to
2994 assume that the existence of one array element implies the
2995 existence of a different one. */
2996 if (!operand_equal_p (TREE_OPERAND (ref1, 0), TREE_OPERAND (ref2, 0), 0))
2997 continue;
2998
2999 field1 = TREE_OPERAND (ref1, 1);
3000 field2 = TREE_OPERAND (ref2, 1);
3001
3002 /* Check for field adjacency, and ensure field1 comes first. */
3003 for (next = DECL_CHAIN (field1);
3004 next && TREE_CODE (next) != FIELD_DECL;
3005 next = DECL_CHAIN (next))
3006 ;
3007
3008 if (next != field2)
3009 {
3010 for (next = DECL_CHAIN (field2);
3011 next && TREE_CODE (next) != FIELD_DECL;
3012 next = DECL_CHAIN (next))
3013 ;
3014
3015 if (next != field1)
3016 continue;
3017
3018 std::swap (field1, field2);
3019 std::swap (def1, def2);
3020 }
3021
3022 bb_for_def1 = gimple_bb (def1);
3023 bb_for_def2 = gimple_bb (def2);
3024
3025 /* Check for proper alignment of the first field. */
3026 tree_offset1 = bit_position (field1);
3027 tree_offset2 = bit_position (field2);
3028 tree_size2 = DECL_SIZE (field2);
3029
3030 if (!tree_fits_uhwi_p (tree_offset1)
3031 || !tree_fits_uhwi_p (tree_offset2)
3032 || !tree_fits_uhwi_p (tree_size2))
3033 continue;
3034
3035 offset1 = tree_to_uhwi (tree_offset1);
3036 offset2 = tree_to_uhwi (tree_offset2);
3037 size2 = tree_to_uhwi (tree_size2);
3038 align1 = DECL_ALIGN (field1) % param_align_bits;
3039
3040 if (offset1 % BITS_PER_UNIT != 0)
3041 continue;
3042
3043 /* For profitability, the two field references should fit within
3044 a single cache line. */
3045 if (align1 + offset2 - offset1 + size2 > param_align_bits)
3046 continue;
3047
3048 /* The two expressions cannot be dependent upon vdefs defined
3049 in bb1/bb2. */
3050 if (local_mem_dependence (def1, bb_for_def1)
3051 || local_mem_dependence (def2, bb_for_def2))
3052 continue;
3053
3054 /* The conditions are satisfied; hoist the loads from bb1 and bb2 into
3055 bb0. We hoist the first one first so that a cache miss is handled
3056 efficiently regardless of hardware cache-fill policy. */
3057 gsi2 = gsi_for_stmt (def1);
3058 gsi_move_to_bb_end (&gsi2, bb0);
3059 gsi2 = gsi_for_stmt (def2);
3060 gsi_move_to_bb_end (&gsi2, bb0);
3061
3062 if (dump_file && (dump_flags & TDF_DETAILS))
3063 {
3064 fprintf (dump_file,
3065 "\nHoisting adjacent loads from %d and %d into %d: \n",
3066 bb_for_def1->index, bb_for_def2->index, bb0->index);
3067 print_gimple_stmt (dump_file, def1, 0, TDF_VOPS|TDF_MEMSYMS);
3068 print_gimple_stmt (dump_file, def2, 0, TDF_VOPS|TDF_MEMSYMS);
3069 }
3070 }
3071 }
3072
3073 /* Determine whether we should attempt to hoist adjacent loads out of
3074 diamond patterns in pass_phiopt. Always hoist loads if
3075 -fhoist-adjacent-loads is specified and the target machine has
3076 both a conditional move instruction and a defined cache line size. */
3077
3078 static bool
gate_hoist_loads(void)3079 gate_hoist_loads (void)
3080 {
3081 return (flag_hoist_adjacent_loads == 1
3082 && param_l1_cache_line_size
3083 && HAVE_conditional_move);
3084 }
3085
3086 /* This pass tries to replaces an if-then-else block with an
3087 assignment. We have four kinds of transformations. Some of these
3088 transformations are also performed by the ifcvt RTL optimizer.
3089
3090 Conditional Replacement
3091 -----------------------
3092
3093 This transformation, implemented in conditional_replacement,
3094 replaces
3095
3096 bb0:
3097 if (cond) goto bb2; else goto bb1;
3098 bb1:
3099 bb2:
3100 x = PHI <0 (bb1), 1 (bb0), ...>;
3101
3102 with
3103
3104 bb0:
3105 x' = cond;
3106 goto bb2;
3107 bb2:
3108 x = PHI <x' (bb0), ...>;
3109
3110 We remove bb1 as it becomes unreachable. This occurs often due to
3111 gimplification of conditionals.
3112
3113 Value Replacement
3114 -----------------
3115
3116 This transformation, implemented in value_replacement, replaces
3117
3118 bb0:
3119 if (a != b) goto bb2; else goto bb1;
3120 bb1:
3121 bb2:
3122 x = PHI <a (bb1), b (bb0), ...>;
3123
3124 with
3125
3126 bb0:
3127 bb2:
3128 x = PHI <b (bb0), ...>;
3129
3130 This opportunity can sometimes occur as a result of other
3131 optimizations.
3132
3133
3134 Another case caught by value replacement looks like this:
3135
3136 bb0:
3137 t1 = a == CONST;
3138 t2 = b > c;
3139 t3 = t1 & t2;
3140 if (t3 != 0) goto bb1; else goto bb2;
3141 bb1:
3142 bb2:
3143 x = PHI (CONST, a)
3144
3145 Gets replaced with:
3146 bb0:
3147 bb2:
3148 t1 = a == CONST;
3149 t2 = b > c;
3150 t3 = t1 & t2;
3151 x = a;
3152
3153 ABS Replacement
3154 ---------------
3155
3156 This transformation, implemented in abs_replacement, replaces
3157
3158 bb0:
3159 if (a >= 0) goto bb2; else goto bb1;
3160 bb1:
3161 x = -a;
3162 bb2:
3163 x = PHI <x (bb1), a (bb0), ...>;
3164
3165 with
3166
3167 bb0:
3168 x' = ABS_EXPR< a >;
3169 bb2:
3170 x = PHI <x' (bb0), ...>;
3171
3172 MIN/MAX Replacement
3173 -------------------
3174
3175 This transformation, minmax_replacement replaces
3176
3177 bb0:
3178 if (a <= b) goto bb2; else goto bb1;
3179 bb1:
3180 bb2:
3181 x = PHI <b (bb1), a (bb0), ...>;
3182
3183 with
3184
3185 bb0:
3186 x' = MIN_EXPR (a, b)
3187 bb2:
3188 x = PHI <x' (bb0), ...>;
3189
3190 A similar transformation is done for MAX_EXPR.
3191
3192
3193 This pass also performs a fifth transformation of a slightly different
3194 flavor.
3195
3196 Factor conversion in COND_EXPR
3197 ------------------------------
3198
3199 This transformation factors the conversion out of COND_EXPR with
3200 factor_out_conditional_conversion.
3201
3202 For example:
3203 if (a <= CST) goto <bb 3>; else goto <bb 4>;
3204 <bb 3>:
3205 tmp = (int) a;
3206 <bb 4>:
3207 tmp = PHI <tmp, CST>
3208
3209 Into:
3210 if (a <= CST) goto <bb 3>; else goto <bb 4>;
3211 <bb 3>:
3212 <bb 4>:
3213 a = PHI <a, CST>
3214 tmp = (int) a;
3215
3216 Adjacent Load Hoisting
3217 ----------------------
3218
3219 This transformation replaces
3220
3221 bb0:
3222 if (...) goto bb2; else goto bb1;
3223 bb1:
3224 x1 = (<expr>).field1;
3225 goto bb3;
3226 bb2:
3227 x2 = (<expr>).field2;
3228 bb3:
3229 # x = PHI <x1, x2>;
3230
3231 with
3232
3233 bb0:
3234 x1 = (<expr>).field1;
3235 x2 = (<expr>).field2;
3236 if (...) goto bb2; else goto bb1;
3237 bb1:
3238 goto bb3;
3239 bb2:
3240 bb3:
3241 # x = PHI <x1, x2>;
3242
3243 The purpose of this transformation is to enable generation of conditional
3244 move instructions such as Intel CMOVE or PowerPC ISEL. Because one of
3245 the loads is speculative, the transformation is restricted to very
3246 specific cases to avoid introducing a page fault. We are looking for
3247 the common idiom:
3248
3249 if (...)
3250 x = y->left;
3251 else
3252 x = y->right;
3253
3254 where left and right are typically adjacent pointers in a tree structure. */
3255
3256 namespace {
3257
3258 const pass_data pass_data_phiopt =
3259 {
3260 GIMPLE_PASS, /* type */
3261 "phiopt", /* name */
3262 OPTGROUP_NONE, /* optinfo_flags */
3263 TV_TREE_PHIOPT, /* tv_id */
3264 ( PROP_cfg | PROP_ssa ), /* properties_required */
3265 0, /* properties_provided */
3266 0, /* properties_destroyed */
3267 0, /* todo_flags_start */
3268 0, /* todo_flags_finish */
3269 };
3270
3271 class pass_phiopt : public gimple_opt_pass
3272 {
3273 public:
pass_phiopt(gcc::context * ctxt)3274 pass_phiopt (gcc::context *ctxt)
3275 : gimple_opt_pass (pass_data_phiopt, ctxt), early_p (false)
3276 {}
3277
3278 /* opt_pass methods: */
clone()3279 opt_pass * clone () { return new pass_phiopt (m_ctxt); }
set_pass_param(unsigned n,bool param)3280 void set_pass_param (unsigned n, bool param)
3281 {
3282 gcc_assert (n == 0);
3283 early_p = param;
3284 }
gate(function *)3285 virtual bool gate (function *) { return flag_ssa_phiopt; }
execute(function *)3286 virtual unsigned int execute (function *)
3287 {
3288 return tree_ssa_phiopt_worker (false,
3289 !early_p ? gate_hoist_loads () : false,
3290 early_p);
3291 }
3292
3293 private:
3294 bool early_p;
3295 }; // class pass_phiopt
3296
3297 } // anon namespace
3298
3299 gimple_opt_pass *
make_pass_phiopt(gcc::context * ctxt)3300 make_pass_phiopt (gcc::context *ctxt)
3301 {
3302 return new pass_phiopt (ctxt);
3303 }
3304
3305 namespace {
3306
3307 const pass_data pass_data_cselim =
3308 {
3309 GIMPLE_PASS, /* type */
3310 "cselim", /* name */
3311 OPTGROUP_NONE, /* optinfo_flags */
3312 TV_TREE_PHIOPT, /* tv_id */
3313 ( PROP_cfg | PROP_ssa ), /* properties_required */
3314 0, /* properties_provided */
3315 0, /* properties_destroyed */
3316 0, /* todo_flags_start */
3317 0, /* todo_flags_finish */
3318 };
3319
3320 class pass_cselim : public gimple_opt_pass
3321 {
3322 public:
pass_cselim(gcc::context * ctxt)3323 pass_cselim (gcc::context *ctxt)
3324 : gimple_opt_pass (pass_data_cselim, ctxt)
3325 {}
3326
3327 /* opt_pass methods: */
gate(function *)3328 virtual bool gate (function *) { return flag_tree_cselim; }
execute(function *)3329 virtual unsigned int execute (function *) { return tree_ssa_cs_elim (); }
3330
3331 }; // class pass_cselim
3332
3333 } // anon namespace
3334
3335 gimple_opt_pass *
make_pass_cselim(gcc::context * ctxt)3336 make_pass_cselim (gcc::context *ctxt)
3337 {
3338 return new pass_cselim (ctxt);
3339 }
3340