Line data Source code
1 : /* Optimization of PHI nodes by converting them into straightline code.
2 : Copyright (C) 2004-2026 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 "tree-ssa.h"
32 : #include "optabs-tree.h"
33 : #include "insn-config.h"
34 : #include "gimple-pretty-print.h"
35 : #include "fold-const.h"
36 : #include "stor-layout.h"
37 : #include "cfganal.h"
38 : #include "gimple-iterator.h"
39 : #include "tree-cfg.h"
40 : #include "tree-dfa.h"
41 : #include "domwalk.h"
42 : #include "cfgloop.h"
43 : #include "tree-data-ref.h"
44 : #include "tree-scalar-evolution.h"
45 : #include "tree-inline.h"
46 : #include "case-cfn-macros.h"
47 : #include "tree-eh.h"
48 : #include "gimple-fold.h"
49 : #include "internal-fn.h"
50 : #include "gimple-range.h"
51 : #include "gimple-match.h"
52 : #include "dbgcnt.h"
53 : #include "tree-ssa-propagate.h"
54 : #include "tree-ssa-dce.h"
55 : #include "tree-ssa-loop-niter.h"
56 : #include "gimple-predict.h"
57 : #include "alias.h"
58 :
59 : /* Return the singleton PHI in the SEQ of PHIs for edges E0 and E1. */
60 :
61 : static gphi *
62 3552452 : single_non_singleton_phi_for_edges (gimple_seq seq, edge e0, edge e1)
63 : {
64 3552452 : gimple_stmt_iterator i;
65 3552452 : gphi *phi = NULL;
66 5276881 : for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
67 : {
68 4296432 : gphi *p = as_a <gphi *> (gsi_stmt (i));
69 : /* If the PHI arguments are equal then we can skip this PHI. */
70 4296432 : if (operand_equal_for_phi_arg_p (gimple_phi_arg_def (p, e0->dest_idx),
71 4296432 : gimple_phi_arg_def (p, e1->dest_idx)))
72 249998 : continue;
73 :
74 : /* Punt on virtual phis with different arguments from the edges. */
75 8092868 : if (virtual_operand_p (gimple_phi_result (p)))
76 : return NULL;
77 :
78 : /* If we already have a PHI that has the two edge arguments are
79 : different, then return it is not a singleton for these PHIs. */
80 1732627 : if (phi)
81 : return NULL;
82 :
83 : phi = p;
84 : }
85 : return phi;
86 : }
87 :
88 : /* Replace PHI node element whose edge is E in block BB with variable NEW.
89 : Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
90 : is known to have two edges, one of which must reach BB). */
91 :
92 : static void
93 98098 : replace_phi_edge_with_variable (basic_block cond_block,
94 : edge e, gphi *phi, tree new_tree,
95 : bitmap dce_ssa_names = nullptr)
96 : {
97 98098 : basic_block bb = gimple_bb (phi);
98 98098 : gimple_stmt_iterator gsi;
99 98098 : tree phi_result = gimple_phi_result (phi);
100 98098 : bool deleteboth = false;
101 :
102 : /* Duplicate range info if they are the only things setting the target PHI.
103 : This is needed as later on, the new_tree will be replacing
104 : The assignment of the PHI.
105 : For an example:
106 : bb1:
107 : _4 = min<a_1, 255>
108 : goto bb2
109 :
110 : # RANGE [-INF, 255]
111 : a_3 = PHI<_4(1)>
112 : bb3:
113 :
114 : use(a_3)
115 : And _4 gets propagated into the use of a_3 and losing the range info.
116 : This can't be done for more than 2 incoming edges as the propagation
117 : won't happen.
118 : The new_tree needs to be defined in the same basic block as the conditional. */
119 98098 : if (TREE_CODE (new_tree) == SSA_NAME
120 98079 : && EDGE_COUNT (gimple_bb (phi)->preds) == 2
121 64098 : && INTEGRAL_TYPE_P (TREE_TYPE (phi_result))
122 58915 : && !SSA_NAME_RANGE_INFO (new_tree)
123 58809 : && SSA_NAME_RANGE_INFO (phi_result)
124 36306 : && gimple_bb (SSA_NAME_DEF_STMT (new_tree)) == cond_block
125 134404 : && dbg_cnt (phiopt_edge_range))
126 36306 : duplicate_ssa_name_range_info (new_tree, phi_result);
127 :
128 : /* Change the PHI argument to new. */
129 98098 : SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);
130 :
131 : /* Remove the empty basic block. */
132 98098 : edge edge_to_remove = NULL, keep_edge = NULL;
133 98098 : if (EDGE_SUCC (cond_block, 0)->dest == bb)
134 : {
135 33711 : edge_to_remove = EDGE_SUCC (cond_block, 1);
136 33711 : keep_edge = EDGE_SUCC (cond_block, 0);
137 : }
138 64387 : else if (EDGE_SUCC (cond_block, 1)->dest == bb)
139 : {
140 : edge_to_remove = EDGE_SUCC (cond_block, 0);
141 : keep_edge = EDGE_SUCC (cond_block, 1);
142 : }
143 1359 : else if ((keep_edge = find_edge (cond_block, e->src)))
144 : {
145 1359 : basic_block bb1 = EDGE_SUCC (cond_block, 0)->dest;
146 1359 : basic_block bb2 = EDGE_SUCC (cond_block, 1)->dest;
147 100816 : if (single_pred_p (bb1) && single_pred_p (bb2)
148 2718 : && single_succ_p (bb1) && single_succ_p (bb2)
149 2718 : && empty_block_p (bb1) && empty_block_p (bb2))
150 : deleteboth = true;
151 : }
152 : else
153 0 : gcc_unreachable ();
154 :
155 : /* If we are removing the cond on a loop exit,
156 : reset number of iteration information of the loop. */
157 98098 : if (loop_exits_from_bb_p (cond_block->loop_father, cond_block))
158 : {
159 0 : auto loop = cond_block->loop_father;
160 0 : free_numbers_of_iterations_estimates (loop);
161 0 : loop->any_upper_bound = false;
162 0 : loop->any_likely_upper_bound = false;
163 : }
164 :
165 98098 : if (edge_to_remove && EDGE_COUNT (edge_to_remove->dest->preds) == 1)
166 : {
167 85379 : e->flags |= EDGE_FALLTHRU;
168 85379 : e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
169 85379 : e->probability = profile_probability::always ();
170 85379 : delete_basic_block (edge_to_remove->dest);
171 :
172 : /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
173 85379 : gsi = gsi_last_bb (cond_block);
174 85379 : gsi_remove (&gsi, true);
175 : }
176 12719 : else if (deleteboth)
177 : {
178 1357 : basic_block bb1 = EDGE_SUCC (cond_block, 0)->dest;
179 1357 : basic_block bb2 = EDGE_SUCC (cond_block, 1)->dest;
180 :
181 1357 : edge newedge = redirect_edge_and_branch (keep_edge, bb);
182 :
183 : /* The new edge should be the same. */
184 1357 : gcc_assert (newedge == keep_edge);
185 :
186 1357 : keep_edge->flags |= EDGE_FALLTHRU;
187 1357 : keep_edge->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
188 1357 : keep_edge->probability = profile_probability::always ();
189 :
190 : /* Copy the edge's phi entry from the old one. */
191 1357 : copy_phi_arg_into_existing_phi (e, keep_edge);
192 :
193 : /* Delete the old 2 empty basic blocks */
194 1357 : delete_basic_block (bb1);
195 1357 : delete_basic_block (bb2);
196 :
197 : /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
198 1357 : gsi = gsi_last_bb (cond_block);
199 1357 : gsi_remove (&gsi, true);
200 : }
201 : else
202 : {
203 : /* If there are other edges into the middle block make
204 : CFG cleanup deal with the edge removal to avoid
205 : updating dominators here in a non-trivial way. */
206 22724 : gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_block));
207 11362 : if (keep_edge->flags & EDGE_FALSE_VALUE)
208 7475 : gimple_cond_make_false (cond);
209 3887 : else if (keep_edge->flags & EDGE_TRUE_VALUE)
210 3887 : gimple_cond_make_true (cond);
211 : }
212 :
213 98098 : if (dce_ssa_names)
214 96106 : simple_dce_from_worklist (dce_ssa_names);
215 :
216 98098 : statistics_counter_event (cfun, "Replace PHI with variable", 1);
217 :
218 98098 : if (dump_file && (dump_flags & TDF_DETAILS))
219 29 : fprintf (dump_file,
220 : "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
221 : cond_block->index,
222 : bb->index);
223 98098 : }
224 :
225 : /* Returns true if the OPERANDS (OPCOUNTED) defined from DEF_STMT is profitable to move
226 : to the usage into the basic block MERGE where the new statement
227 : will be located. */
228 : static bool
229 67615 : is_factor_profitable (gimple *def_stmt, basic_block merge, tree *operands, unsigned opcount)
230 : {
231 : /* The defining statement should be conditional. */
232 67615 : if (dominated_by_p (CDI_DOMINATORS, merge,
233 67615 : gimple_bb (def_stmt)))
234 : return false;
235 :
236 : /* We should not increase the live range of arg
237 : across too many statements or calls. */
238 63710 : gimple_stmt_iterator gsi = gsi_for_stmt (def_stmt);
239 63710 : gsi_next_nondebug (&gsi);
240 :
241 : /* Skip past nops and predicates. */
242 127926 : while (!gsi_end_p (gsi)
243 64216 : && (gimple_code (gsi_stmt (gsi)) == GIMPLE_NOP
244 9288 : || gimple_code (gsi_stmt (gsi)) == GIMPLE_PREDICT))
245 506 : gsi_next_nondebug (&gsi);
246 :
247 : /* If the defining statement is at the end of the bb, then it is
248 : always profitable to be to move. */
249 63710 : if (gsi_end_p (gsi))
250 : return true;
251 :
252 : /* If there are a few (non-call/asm) statements between
253 : the old defining statement and end of the bb, then
254 : the live range of operands will increase enough. */
255 8782 : int max_statements = param_phiopt_factor_max_stmts_live;
256 8782 : bool stmts_extending_ok = true;
257 :
258 25230 : while (!gsi_end_p (gsi))
259 : {
260 17338 : gimple *stmt = gsi_stmt (gsi);
261 17338 : auto gcode = gimple_code (stmt);
262 : /* Skip over NOPs and predicts. */
263 17352 : if (gcode == GIMPLE_NOP
264 17338 : || gcode == GIMPLE_PREDICT)
265 : {
266 14 : gsi_next_nondebug (&gsi);
267 14 : continue;
268 : }
269 : /* Non-assigns will extend the live range too much. */
270 17324 : if (gcode != GIMPLE_ASSIGN)
271 : {
272 : stmts_extending_ok = false;
273 : break;
274 : }
275 17044 : max_statements --;
276 17044 : if (max_statements == 0)
277 : {
278 : stmts_extending_ok = false;
279 : break;
280 : }
281 16434 : gsi_next_nondebug (&gsi);
282 : }
283 8782 : if (stmts_extending_ok)
284 : return true;
285 :
286 : /* Loop over all of the operands to see if all are used after anyways. */
287 1237 : for (unsigned i = 0; i < opcount; i++)
288 : {
289 920 : tree arg = operands[i];
290 : /* If the arg is invariant, then there is
291 : no extending of the live range. */
292 920 : if (is_gimple_min_invariant (arg))
293 304 : continue;
294 :
295 : /* Otherwise, the arg needs to be a ssa name. */
296 616 : if (TREE_CODE (arg) != SSA_NAME)
297 573 : return false;
298 :
299 : /* Check if the uses of arg is dominated by merge block, this is a quick and
300 : rough estimate if arg is still alive at the merge bb. */
301 : /* FIXME: extend to a more complete live range detection. */
302 616 : use_operand_p use_p;
303 616 : imm_use_iterator iter;
304 616 : bool usedafter = false;
305 2791 : FOR_EACH_IMM_USE_FAST (use_p, iter, arg)
306 : {
307 2218 : gimple *use_stmt = USE_STMT (use_p);
308 2218 : if (is_gimple_debug (use_stmt))
309 216 : continue;
310 2002 : basic_block use_bb = gimple_bb (use_stmt);
311 2002 : if (dominated_by_p (CDI_DOMINATORS, merge, use_bb))
312 : {
313 : usedafter = true;
314 : break;
315 : }
316 616 : }
317 616 : if (!usedafter)
318 : return false;
319 : }
320 : return true;
321 : }
322 :
323 : /* PR66726: Factor operations out of COND_EXPR. If the arguments of the PHI
324 : stmt are Unary operator, factor out the operation and perform the operation
325 : to the result of PHI stmt. COND_STMT is the controlling predicate.
326 : Return true if the operation was factored out; false otherwise. */
327 :
328 : static bool
329 3094548 : factor_out_conditional_operation (edge e0, edge e1, basic_block merge,
330 : gphi *phi, gimple *cond_stmt,
331 : bool early_p)
332 : {
333 3094548 : gimple *arg0_def_stmt = NULL, *arg1_def_stmt = NULL;
334 3094548 : tree temp, result;
335 3094548 : gphi *newphi;
336 3094548 : gimple_stmt_iterator gsi, gsi_for_def;
337 3094548 : location_t locus = gimple_location (phi);
338 3094548 : gimple_match_op arg0_op, arg1_op;
339 :
340 : /* We should only get here if the phi had two arguments. */
341 3094548 : gcc_assert (gimple_phi_num_args (phi) == 2);
342 :
343 : /* Virtual operands are never handled. */
344 6189096 : if (virtual_operand_p (gimple_phi_result (phi)))
345 : return false;
346 :
347 1354814 : tree arg0 = gimple_phi_arg_def (phi, e0->dest_idx);
348 1354814 : tree arg1 = gimple_phi_arg_def (phi, e1->dest_idx);
349 1354814 : location_t narg0_loc = gimple_location (phi);
350 1354814 : location_t narg1_loc = gimple_location (phi);
351 1354814 : if (gimple_phi_arg_location (phi, e0->dest_idx) != UNKNOWN_LOCATION)
352 1137387 : narg0_loc = gimple_phi_arg_location (phi, e0->dest_idx);
353 1354814 : if (gimple_phi_arg_location (phi, e1->dest_idx) != UNKNOWN_LOCATION)
354 956540 : narg1_loc = gimple_phi_arg_location (phi, e1->dest_idx);
355 :
356 1354814 : gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
357 :
358 : /* Arguments that are the same don't have anything to be
359 : done to them. */
360 1354814 : if (operand_equal_for_phi_arg_p (arg0, arg1))
361 : return false;
362 :
363 : /* First canonicalize to simplify tests. */
364 1354634 : if (TREE_CODE (arg0) != SSA_NAME)
365 : {
366 252661 : std::swap (arg0, arg1);
367 252661 : std::swap (e0, e1);
368 : }
369 :
370 1354634 : if (TREE_CODE (arg0) != SSA_NAME
371 1234893 : || (TREE_CODE (arg1) != SSA_NAME
372 501848 : && TREE_CODE (arg1) != INTEGER_CST))
373 : return false;
374 :
375 : /* Check if arg0 is an SSA_NAME and the stmt which defines arg0 is
376 : an unary operation. */
377 1197797 : arg0_def_stmt = SSA_NAME_DEF_STMT (arg0);
378 1197797 : if (!gimple_extract_op (arg0_def_stmt, &arg0_op))
379 : return false;
380 :
381 : /* Check to make sure none of the operands are in abnormal phis. */
382 619406 : if (arg0_op.operands_occurs_in_abnormal_phi ())
383 : return false;
384 :
385 619406 : tree new_arg0;
386 619406 : tree new_arg1;
387 619406 : int opnum = -1;
388 :
389 : /* If arg0 have > 1 use, then this transformation actually increases
390 : the number of expressions evaluated at runtime. */
391 619406 : if (!has_single_use (arg0))
392 : return false;
393 506438 : if (gimple_has_location (arg0_def_stmt))
394 467640 : narg0_loc = gimple_location (arg0_def_stmt);
395 :
396 506438 : if (TREE_CODE (arg1) == SSA_NAME)
397 : {
398 : /* Check if arg1 is an SSA_NAME. */
399 330602 : arg1_def_stmt = SSA_NAME_DEF_STMT (arg1);
400 330602 : if (!gimple_extract_op (arg1_def_stmt, &arg1_op))
401 : return false;
402 172409 : if (arg1_op.code != arg0_op.code)
403 : return false;
404 51685 : if (arg1_op.num_ops != arg0_op.num_ops)
405 : return false;
406 51669 : if (arg1_op.operands_occurs_in_abnormal_phi ())
407 : return false;
408 :
409 : /* For the complex expression, don't factor
410 : out, that will confuse the uninitializing
411 : warnings. */
412 51669 : if (arg1_op.code == COMPLEX_EXPR)
413 : return false;
414 :
415 : /* If arg1 have > 1 use, then this transformation actually increases
416 : the number of expressions evaluated at runtime. */
417 51554 : if (!has_single_use (arg1))
418 : return false;
419 :
420 39606 : opnum = find_different_opnum (arg0_op, arg1_op, &new_arg0, &new_arg1);
421 39606 : if (opnum == -1)
422 : return false;
423 :
424 : /* Check to make sure extending the lifetimes of all operands is ok. */
425 13411 : if (!is_factor_profitable (arg0_def_stmt, merge,
426 : arg0_op.ops, arg0_op.num_ops))
427 : return false;
428 12446 : if (!is_factor_profitable (arg1_def_stmt, merge,
429 : arg1_op.ops, arg1_op.num_ops))
430 : return false;
431 :
432 : /* If this was a division and the operand is the divisor
433 : and either divisor was a constant, don't factor out
434 : the division; dividing by an explicit constant can be
435 : expanded better than without an constant.
436 : FIXME: maybe isel could undo this case. */
437 9663 : if (int_divide_or_mod_p (arg1_op.code)
438 400 : && opnum == 1
439 42 : && (poly_int_tree_p (new_arg0)
440 0 : || poly_int_tree_p (new_arg1)))
441 : return false;
442 :
443 : /* For early phiopt, don't factor out constants for pointer plus.
444 : BOS pass does not like that factoring. */
445 4495 : if (early_p && arg1_op.code == POINTER_PLUS_EXPR
446 198 : && opnum == 1
447 185 : && TREE_CODE (new_arg0) != SSA_NAME
448 9641 : && TREE_CODE (new_arg1) != SSA_NAME)
449 : return false;
450 :
451 : /* BIT_FIELD_REF and BIT_INSERT_EXPR can't be factored out for non-0 operands
452 : as the other operands require constants. */
453 9602 : if ((arg1_op.code == BIT_FIELD_REF
454 9572 : || arg1_op.code == BIT_INSERT_EXPR)
455 9669 : && opnum != 0)
456 : return false;
457 :
458 : /* It is not profitability to factor out vec_perm with
459 : constant masks (operand 2). The target might not support it
460 : and that might be invalid to do as such. Also with constants
461 : masks, the number of elements of the mask type does not need
462 : to match the number of elements of other operands and can be
463 : arbitrary integral vector type so factoring that out can't work.
464 : Note in the case where one mask is a constant and the other is not,
465 : the check for compatible types will reject the case the
466 : constant mask has the incompatible type. */
467 9524 : if (arg1_op.code == VEC_PERM_EXPR && opnum == 2
468 103 : && TREE_CODE (new_arg0) == VECTOR_CST
469 9627 : && TREE_CODE (new_arg1) == VECTOR_CST)
470 : return false;
471 :
472 9440 : if (gimple_has_location (arg1_def_stmt))
473 9182 : narg1_loc = gimple_location (arg1_def_stmt);
474 :
475 : /* Chose the location for the new statement if the phi location is unknown. */
476 9440 : if (locus == UNKNOWN_LOCATION)
477 : {
478 9440 : if (narg0_loc == UNKNOWN_LOCATION
479 9440 : && narg1_loc != UNKNOWN_LOCATION)
480 : locus = narg1_loc;
481 9440 : else if (narg0_loc != UNKNOWN_LOCATION
482 9440 : && narg1_loc == UNKNOWN_LOCATION)
483 51 : locus = narg0_loc;
484 : }
485 : }
486 175836 : else if (arg0_op.num_ops != 1)
487 : return false;
488 : else
489 : {
490 51434 : new_arg0 = arg0_op.ops[0];
491 51434 : opnum = 0;
492 : /* For constants only handle if the phi was the only one. */
493 51434 : if (single_non_singleton_phi_for_edges (phi_nodes (merge), e0, e1) == NULL)
494 : return false;
495 : /* TODO: handle more than just casts here. */
496 38200 : if (!gimple_assign_cast_p (arg0_def_stmt))
497 : return false;
498 31776 : if (!is_factor_profitable (arg0_def_stmt, merge, arg0_op.ops, arg0_op.num_ops))
499 : return false;
500 :
501 : /* If arg1 is an INTEGER_CST, fold it to new type if it fits, or else
502 : if the bits will not be modified during the conversion, except for
503 : boolean types whose precision is not 1 (see int_fits_type_p). */
504 62115 : if (!INTEGRAL_TYPE_P (TREE_TYPE (new_arg0))
505 61860 : || !(int_fits_type_p (arg1, TREE_TYPE (new_arg0))
506 1587 : || (TYPE_PRECISION (TREE_TYPE (new_arg0))
507 1587 : == TYPE_PRECISION (TREE_TYPE (arg1))
508 687 : && (TREE_CODE (TREE_TYPE (new_arg0)) != BOOLEAN_TYPE
509 0 : || TYPE_PRECISION (TREE_TYPE (new_arg0)) == 1))))
510 : return false;
511 :
512 : /* For the INTEGER_CST case, we are just moving the
513 : conversion from one place to another, which can often
514 : hurt as the conversion moves further away from the
515 : statement that computes the value. So, perform this
516 : only if new_arg0 is an operand of COND_STMT, or
517 : if arg0_def_stmt is the only non-debug stmt in
518 : its basic block, because then it is possible this
519 : could enable further optimizations (minmax replacement
520 : etc.). See PR71016.
521 : Note no-op conversions don't have this issue as
522 : it will not generate any zero/sign extend in that case. */
523 29909 : if ((TYPE_PRECISION (TREE_TYPE (new_arg0))
524 29909 : != TYPE_PRECISION (TREE_TYPE (arg1)))
525 14394 : && new_arg0 != gimple_cond_lhs (cond_stmt)
526 13698 : && new_arg0 != gimple_cond_rhs (cond_stmt)
527 43601 : && gimple_bb (arg0_def_stmt) == e0->src)
528 : {
529 13692 : gsi = gsi_for_stmt (arg0_def_stmt);
530 13692 : gsi_prev_nondebug (&gsi);
531 : /* Ignore nops, predicates and labels. */
532 27396 : while (!gsi_end_p (gsi)
533 13704 : && (gimple_code (gsi_stmt (gsi)) == GIMPLE_NOP
534 : || gimple_code (gsi_stmt (gsi)) == GIMPLE_PREDICT
535 : || gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL))
536 12 : gsi_prev_nondebug (&gsi);
537 :
538 13692 : if (!gsi_end_p (gsi))
539 : {
540 10280 : gimple *stmt = gsi_stmt (gsi);
541 10280 : if (gassign *assign = dyn_cast <gassign *> (stmt))
542 : {
543 9668 : tree lhs = gimple_assign_lhs (assign);
544 9668 : tree lhst = TREE_TYPE (lhs);
545 9668 : enum tree_code ass_code
546 9668 : = gimple_assign_rhs_code (assign);
547 9668 : if (ass_code != MAX_EXPR && ass_code != MIN_EXPR
548 : /* Conversions from boolean like types is ok
549 : as `a?1:b` and `a?0:b` will always simplify
550 : to `a & b` or `a | b`.
551 : See PR 116890. */
552 9668 : && !(INTEGRAL_TYPE_P (lhst)
553 9213 : && TYPE_UNSIGNED (lhst)
554 6904 : && TYPE_PRECISION (lhst) == 1))
555 : return false;
556 4664 : if (lhs != gimple_assign_rhs1 (arg0_def_stmt))
557 : return false;
558 4622 : gsi_prev_nondebug (&gsi);
559 4622 : if (!gsi_end_p (gsi))
560 : return false;
561 : }
562 : else
563 : return false;
564 : }
565 : }
566 19875 : new_arg1 = fold_convert (TREE_TYPE (new_arg0), arg1);
567 :
568 : /* Drop the overflow that fold_convert might add. */
569 19875 : if (TREE_OVERFLOW (new_arg1))
570 0 : new_arg1 = drop_tree_overflow (new_arg1);
571 :
572 : /* The locus of the new statement is arg0 defining statement. */
573 19875 : if (gimple_has_location (arg0_def_stmt))
574 19423 : locus = gimple_location (arg0_def_stmt);
575 : }
576 :
577 : /* If types of new_arg0 and new_arg1 are different bailout. */
578 29315 : if (!types_compatible_p (TREE_TYPE (new_arg0), TREE_TYPE (new_arg1)))
579 : return false;
580 :
581 : /* Create a new PHI stmt. */
582 28302 : result = gimple_phi_result (phi);
583 28302 : temp = make_ssa_name (TREE_TYPE (new_arg0), NULL);
584 :
585 28302 : gimple_match_op new_op = arg0_op;
586 :
587 : /* Create the operation stmt if possible and insert it. */
588 28302 : new_op.ops[opnum] = temp;
589 28302 : gimple_seq seq = NULL;
590 28302 : result = maybe_push_res_to_seq (&new_op, &seq, result);
591 :
592 : /* If we can't create the new statement, release the temp name
593 : and return back. */
594 28302 : if (!result)
595 : {
596 256 : release_ssa_name (temp);
597 256 : return false;
598 : }
599 :
600 28046 : if (locus != UNKNOWN_LOCATION)
601 19470 : annotate_all_with_location (seq, locus);
602 28046 : gsi = gsi_after_labels (gimple_bb (phi));
603 28046 : gsi_insert_seq_before (&gsi, seq, GSI_CONTINUE_LINKING);
604 :
605 28046 : newphi = create_phi_node (temp, gimple_bb (phi));
606 :
607 28046 : if (dump_file && (dump_flags & TDF_DETAILS))
608 : {
609 35 : fprintf (dump_file, "PHI ");
610 35 : print_generic_expr (dump_file, gimple_phi_result (phi));
611 35 : fprintf (dump_file,
612 : " changed to factor operation out from COND_EXPR.\n");
613 35 : fprintf (dump_file, "New stmt with OPERATION that defines ");
614 35 : print_generic_expr (dump_file, result);
615 35 : fprintf (dump_file, ".\n");
616 : }
617 :
618 : /* Remove the old operation(s) that has single use. */
619 28046 : gsi_for_def = gsi_for_stmt (arg0_def_stmt);
620 28046 : gsi_remove (&gsi_for_def, true);
621 28046 : release_defs (arg0_def_stmt);
622 :
623 28046 : if (arg1_def_stmt)
624 : {
625 8171 : gsi_for_def = gsi_for_stmt (arg1_def_stmt);
626 8171 : gsi_remove (&gsi_for_def, true);
627 8171 : release_defs (arg1_def_stmt);
628 : }
629 :
630 28046 : add_phi_arg (newphi, new_arg0, e0, narg0_loc);
631 28046 : add_phi_arg (newphi, new_arg1, e1, narg1_loc);
632 :
633 : /* Remove the original PHI stmt. */
634 28046 : gsi = gsi_for_stmt (phi);
635 28046 : remove_phi_node (&gsi, false);
636 :
637 28046 : statistics_counter_event (cfun, "factored out operation", 1);
638 :
639 28046 : return true;
640 : }
641 :
642 :
643 : /* Return TRUE if SEQ/OP pair should be allowed during early phiopt.
644 : Currently this is to allow MIN/MAX and ABS/NEGATE and constants. */
645 : static bool
646 180337 : phiopt_early_allow (gimple_seq &seq, gimple_match_op &op)
647 : {
648 : /* Don't allow functions. */
649 180337 : if (!op.code.is_tree_code ())
650 : return false;
651 180276 : tree_code code = (tree_code)op.code;
652 :
653 : /* For non-empty sequence, only allow one statement
654 : a MIN/MAX and an original MIN/MAX. */
655 180276 : if (!gimple_seq_empty_p (seq))
656 : {
657 148634 : if (code == MIN_EXPR || code == MAX_EXPR)
658 : {
659 151666 : if (!gimple_seq_singleton_p (seq))
660 : return false;
661 :
662 3 : gimple *stmt = gimple_seq_first_stmt (seq);
663 : /* Only allow assignments. */
664 3 : if (!is_gimple_assign (stmt))
665 : return false;
666 3 : code = gimple_assign_rhs_code (stmt);
667 3 : return code == MIN_EXPR || code == MAX_EXPR;
668 : }
669 : return false;
670 : }
671 :
672 31642 : switch (code)
673 : {
674 : case MIN_EXPR:
675 : case MAX_EXPR:
676 : case ABS_EXPR:
677 : case ABSU_EXPR:
678 : case NEGATE_EXPR:
679 : case SSA_NAME:
680 : return true;
681 : case INTEGER_CST:
682 : case REAL_CST:
683 : case VECTOR_CST:
684 : case FIXED_CST:
685 : return true;
686 : default:
687 : return false;
688 : }
689 : }
690 :
691 : /* gimple_simplify_phiopt is like gimple_simplify but designed for PHIOPT.
692 : Return NULL if nothing can be simplified or the resulting simplified value
693 : with parts pushed if EARLY_P was true. Also rejects non allowed tree code
694 : if EARLY_P is set.
695 : Takes the comparison from COMP_STMT and two args, ARG0 and ARG1 and tries
696 : to simplify CMP ? ARG0 : ARG1.
697 : Also try to simplify (!CMP) ? ARG1 : ARG0 if the non-inverse failed. */
698 : static tree
699 546980 : gimple_simplify_phiopt (bool early_p, tree type, gimple *comp_stmt,
700 : tree arg0, tree arg1,
701 : gimple_seq *seq)
702 : {
703 546980 : gimple_seq seq1 = NULL;
704 546980 : enum tree_code comp_code = gimple_cond_code (comp_stmt);
705 546980 : location_t loc = gimple_location (comp_stmt);
706 546980 : tree cmp0 = gimple_cond_lhs (comp_stmt);
707 546980 : tree cmp1 = gimple_cond_rhs (comp_stmt);
708 : /* To handle special cases like floating point comparison, it is easier and
709 : less error-prone to build a tree and gimplify it on the fly though it is
710 : less efficient.
711 : Don't use fold_build2 here as that might create (bool)a instead of just
712 : "a != 0". */
713 546980 : tree cond = build2_loc (loc, comp_code, boolean_type_node,
714 : cmp0, cmp1);
715 :
716 546980 : if (dump_file && (dump_flags & TDF_FOLDING))
717 : {
718 1 : fprintf (dump_file, "\nphiopt match-simplify trying:\n\t");
719 1 : print_generic_expr (dump_file, cond);
720 1 : fprintf (dump_file, " ? ");
721 1 : print_generic_expr (dump_file, arg0);
722 1 : fprintf (dump_file, " : ");
723 1 : print_generic_expr (dump_file, arg1);
724 1 : fprintf (dump_file, "\n");
725 : }
726 :
727 546980 : gimple_match_op op (gimple_match_cond::UNCOND,
728 546980 : COND_EXPR, type, cond, arg0, arg1);
729 :
730 546980 : if (op.resimplify (&seq1, follow_all_ssa_edges))
731 : {
732 163594 : bool allowed = !early_p || phiopt_early_allow (seq1, op);
733 163594 : tree result = maybe_push_res_to_seq (&op, &seq1);
734 163594 : if (dump_file && (dump_flags & TDF_FOLDING))
735 : {
736 1 : fprintf (dump_file, "\nphiopt match-simplify back:\n");
737 1 : if (seq1)
738 0 : print_gimple_seq (dump_file, seq1, 0, TDF_VOPS|TDF_MEMSYMS);
739 1 : fprintf (dump_file, "result: ");
740 1 : if (result)
741 1 : print_generic_expr (dump_file, result);
742 : else
743 0 : fprintf (dump_file, " (none)");
744 1 : fprintf (dump_file, "\n");
745 1 : if (!allowed)
746 0 : fprintf (dump_file, "rejected because early\n");
747 : }
748 : /* Early we want only to allow some generated tree codes. */
749 163594 : if (allowed && result)
750 : {
751 86661 : if (loc != UNKNOWN_LOCATION)
752 86192 : annotate_all_with_location (seq1, loc);
753 86661 : gimple_seq_add_seq_without_update (seq, seq1);
754 86661 : return result;
755 : }
756 : }
757 460319 : gimple_seq_discard (seq1);
758 460319 : seq1 = NULL;
759 :
760 : /* Try the inverted comparison, that is !COMP ? ARG1 : ARG0. */
761 460319 : comp_code = invert_tree_comparison (comp_code, HONOR_NANS (cmp0));
762 :
763 460319 : if (comp_code == ERROR_MARK)
764 : return NULL;
765 :
766 443278 : cond = build2_loc (loc,
767 : comp_code, boolean_type_node,
768 : cmp0, cmp1);
769 :
770 443278 : if (dump_file && (dump_flags & TDF_FOLDING))
771 : {
772 0 : fprintf (dump_file, "\nphiopt match-simplify trying:\n\t");
773 0 : print_generic_expr (dump_file, cond);
774 0 : fprintf (dump_file, " ? ");
775 0 : print_generic_expr (dump_file, arg1);
776 0 : fprintf (dump_file, " : ");
777 0 : print_generic_expr (dump_file, arg0);
778 0 : fprintf (dump_file, "\n");
779 : }
780 :
781 443278 : gimple_match_op op1 (gimple_match_cond::UNCOND,
782 443278 : COND_EXPR, type, cond, arg1, arg0);
783 :
784 443278 : if (op1.resimplify (&seq1, follow_all_ssa_edges))
785 : {
786 80163 : bool allowed = !early_p || phiopt_early_allow (seq1, op1);
787 80163 : tree result = maybe_push_res_to_seq (&op1, &seq1);
788 80163 : if (dump_file && (dump_flags & TDF_FOLDING))
789 : {
790 0 : fprintf (dump_file, "\nphiopt match-simplify back:\n");
791 0 : if (seq1)
792 0 : print_gimple_seq (dump_file, seq1, 0, TDF_VOPS|TDF_MEMSYMS);
793 0 : fprintf (dump_file, "result: ");
794 0 : if (result)
795 0 : print_generic_expr (dump_file, result);
796 : else
797 0 : fprintf (dump_file, " (none)");
798 0 : fprintf (dump_file, "\n");
799 0 : if (!allowed)
800 0 : fprintf (dump_file, "rejected because early\n");
801 : }
802 : /* Early we want only to allow some generated tree codes. */
803 80163 : if (allowed && result)
804 : {
805 5401 : if (loc != UNKNOWN_LOCATION)
806 5401 : annotate_all_with_location (seq1, loc);
807 5401 : gimple_seq_add_seq_without_update (seq, seq1);
808 5401 : return result;
809 : }
810 : }
811 437877 : gimple_seq_discard (seq1);
812 :
813 437877 : return NULL;
814 : }
815 :
816 : /* one_feeding_comparison_into_p returns true if BB has one comparison
817 : statement and it sets STMT to that statement. Note the comparison can
818 : be trapping too. */
819 : static bool
820 1200 : one_feeding_comparison_into_p (basic_block bb,
821 : gimple *phi,
822 : gassign *&assign)
823 : {
824 1200 : assign = nullptr;
825 1200 : gimple *stmt = nullptr;
826 :
827 1200 : if (empty_block_p (bb))
828 : return false;
829 :
830 1182 : if (!single_pred_p (bb))
831 : return false;
832 :
833 1174 : if (!gimple_seq_empty_p (phi_nodes (bb)))
834 : return false;
835 :
836 1174 : gimple_stmt_iterator gsi;
837 1174 : gsi = gsi_start_nondebug_after_labels_bb (bb);
838 2350 : while (!gsi_end_p (gsi))
839 : {
840 1978 : gimple *s = gsi_stmt (gsi);
841 1978 : gsi_next_nondebug (&gsi);
842 : /* Skip over Predict and nop statements. */
843 1978 : if (gimple_code (s) == GIMPLE_PREDICT
844 1978 : || gimple_code (s) == GIMPLE_NOP)
845 2 : continue;
846 : /* If there is more one statement return false. */
847 1976 : if (stmt)
848 : return false;
849 : stmt = s;
850 : }
851 :
852 372 : if (!stmt)
853 : return false;
854 :
855 744 : if (gimple_vuse (stmt))
856 : return false;
857 :
858 366 : gassign *a = dyn_cast<gassign*>(stmt);
859 366 : if (!a || TREE_CODE_CLASS (gimple_assign_rhs_code (a)) != tcc_comparison)
860 : return false;
861 :
862 366 : tree lhs = gimple_assign_lhs (a);
863 :
864 366 : gimple *use_stmt;
865 366 : use_operand_p use_p;
866 : /* Allow only a statement which feeds into the other stmt. */
867 366 : if (!lhs || TREE_CODE (lhs) != SSA_NAME
868 366 : || !single_imm_use (lhs, &use_p, &use_stmt)
869 732 : || use_stmt != phi)
870 : return false;
871 :
872 : // Don't handle non-call exceptions
873 366 : if (stmt_could_throw_p (cfun, a))
874 : return false;
875 :
876 354 : assign = a;
877 354 : return true;
878 : }
879 :
880 : /* empty_bb_or_one_feeding_into_p returns true if bb was empty basic block
881 : or it has one cheap preparation statement that feeds into the PHI
882 : statement and it sets STMT to that statement. */
883 : static bool
884 899847 : empty_bb_or_one_feeding_into_p (basic_block bb,
885 : gimple *phi,
886 : gimple *&stmt)
887 : {
888 899847 : stmt = nullptr;
889 899847 : gimple *stmt_to_move = nullptr;
890 899847 : tree lhs;
891 :
892 899847 : if (empty_block_p (bb))
893 : return true;
894 :
895 481949 : if (!single_pred_p (bb))
896 : return false;
897 :
898 : /* The middle bb cannot have phi nodes as we don't
899 : move those assignments yet. */
900 468725 : if (!gimple_seq_empty_p (phi_nodes (bb)))
901 : return false;
902 :
903 468705 : gimple_stmt_iterator gsi;
904 :
905 468705 : gsi = gsi_start_nondebug_after_labels_bb (bb);
906 940493 : while (!gsi_end_p (gsi))
907 : {
908 687398 : gimple *s = gsi_stmt (gsi);
909 687398 : gsi_next_nondebug (&gsi);
910 : /* Skip over Predict and nop statements. */
911 687398 : if (gimple_code (s) == GIMPLE_PREDICT
912 687398 : || gimple_code (s) == GIMPLE_NOP)
913 3083 : continue;
914 : /* If there is more one statement return false. */
915 684315 : if (stmt_to_move)
916 : return false;
917 : stmt_to_move = s;
918 : }
919 :
920 : /* The only statement here was a Predict or a nop statement
921 : so return true. */
922 253095 : if (!stmt_to_move)
923 : return true;
924 :
925 506190 : if (gimple_vuse (stmt_to_move))
926 : return false;
927 :
928 172592 : if (gimple_could_trap_p (stmt_to_move)
929 172592 : || gimple_has_side_effects (stmt_to_move))
930 : return false;
931 :
932 167159 : ssa_op_iter it;
933 167159 : tree use;
934 368769 : FOR_EACH_SSA_TREE_OPERAND (use, stmt_to_move, it, SSA_OP_USE)
935 202270 : if (ssa_name_maybe_undef_p (use))
936 : return false;
937 :
938 : /* Allow assignments but allow some builtin/internal calls.
939 : As const calls don't match any of the above, yet they could
940 : still have some side-effects - they could contain
941 : gimple_could_trap_p statements, like floating point
942 : exceptions or integer division by zero. See PR70586.
943 : FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
944 : should handle this.
945 : Allow some known builtin/internal calls that are known not to
946 : trap: logical functions (e.g. bswap and bit counting). */
947 166499 : if (!is_gimple_assign (stmt_to_move))
948 : {
949 5790 : if (!is_gimple_call (stmt_to_move))
950 : return false;
951 5539 : combined_fn cfn = gimple_call_combined_fn (stmt_to_move);
952 5539 : switch (cfn)
953 : {
954 : default:
955 : return false;
956 4620 : CASE_CFN_BSWAP:
957 4620 : CASE_CFN_BITREVERSE:
958 4620 : CASE_CFN_FFS:
959 4620 : CASE_CFN_PARITY:
960 4620 : CASE_CFN_POPCOUNT:
961 4620 : CASE_CFN_CLZ:
962 4620 : CASE_CFN_CTZ:
963 4620 : case CFN_BUILT_IN_CLRSB:
964 4620 : case CFN_BUILT_IN_CLRSBL:
965 4620 : case CFN_BUILT_IN_CLRSBLL:
966 4620 : lhs = gimple_call_lhs (stmt_to_move);
967 4620 : break;
968 : }
969 : }
970 : else
971 160709 : lhs = gimple_assign_lhs (stmt_to_move);
972 :
973 165329 : gimple *use_stmt;
974 165329 : use_operand_p use_p;
975 :
976 : /* Allow only a statement which feeds into the other stmt. */
977 165329 : if (!lhs || TREE_CODE (lhs) != SSA_NAME
978 165329 : || !single_imm_use (lhs, &use_p, &use_stmt)
979 330653 : || use_stmt != phi)
980 : return false;
981 :
982 165324 : stmt = stmt_to_move;
983 165324 : return true;
984 : }
985 :
986 : /* Move STMT to before GSI and insert its defining
987 : name into INSERTED_EXPRS bitmap.
988 : Also rewrite its if it might be undefined when unconditionalized. */
989 : static void
990 192212 : move_stmt (gimple *stmt, gimple_stmt_iterator *gsi, auto_bitmap &inserted_exprs)
991 : {
992 192212 : if (!stmt)
993 185995 : return;
994 6217 : if (dump_file && (dump_flags & TDF_DETAILS))
995 : {
996 9 : fprintf (dump_file, "statement un-sinked:\n");
997 9 : print_gimple_stmt (dump_file, stmt, 0,
998 : TDF_VOPS|TDF_MEMSYMS);
999 : }
1000 :
1001 6217 : tree name = gimple_get_lhs (stmt);
1002 : // Mark the name to be renamed if there is one.
1003 6217 : bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (name));
1004 6217 : gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt);
1005 6217 : gsi_move_before (&gsi1, gsi, GSI_NEW_STMT);
1006 6217 : reset_flow_sensitive_info (name);
1007 :
1008 : /* Rewrite some code which might be undefined when
1009 : unconditionalized. */
1010 6217 : if (gimple_needing_rewrite_undefined (stmt))
1011 1146 : rewrite_to_defined_unconditional (gsi);
1012 : }
1013 :
1014 : /* RAII style class to temporarily remove flow sensitive
1015 : from ssa names defined by a gimple statement. */
1016 : class auto_flow_sensitive
1017 : {
1018 : public:
1019 : auto_flow_sensitive (gimple *s);
1020 : ~auto_flow_sensitive ();
1021 : private:
1022 : auto_vec<std::pair<tree, flow_sensitive_info_storage>, 2> stack;
1023 : };
1024 :
1025 : /* Constructor for auto_flow_sensitive. Saves
1026 : off the ssa names' flow sensitive information
1027 : that was defined by gimple statement S and
1028 : resets it to be non-flow based ones. */
1029 :
1030 1093960 : auto_flow_sensitive::auto_flow_sensitive (gimple *s)
1031 : {
1032 1093960 : if (!s)
1033 937675 : return;
1034 156285 : ssa_op_iter it;
1035 156285 : tree def;
1036 312570 : FOR_EACH_SSA_TREE_OPERAND (def, s, it, SSA_OP_DEF)
1037 : {
1038 156285 : flow_sensitive_info_storage storage;
1039 156285 : storage.save_and_clear (def);
1040 156285 : stack.safe_push (std::make_pair (def, storage));
1041 : }
1042 : }
1043 :
1044 : /* Deconstructor, restores the flow sensitive information
1045 : for the SSA names that had been saved off. */
1046 :
1047 1093960 : auto_flow_sensitive::~auto_flow_sensitive ()
1048 : {
1049 3438165 : for (auto p : stack)
1050 156285 : p.second.restore (p.first);
1051 1093960 : }
1052 :
1053 : /* Returns true if BB contains an user provided predictor
1054 : (PRED_HOT_LABEL/PRED_COLD_LABEL). */
1055 :
1056 : static bool
1057 6382 : contains_hot_cold_predict (basic_block bb)
1058 : {
1059 6382 : gimple_stmt_iterator gsi;
1060 6382 : gsi = gsi_start_nondebug_after_labels_bb (bb);
1061 8924 : for (; !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
1062 : {
1063 2543 : gimple *s = gsi_stmt (gsi);
1064 2543 : if (gimple_code (s) != GIMPLE_PREDICT)
1065 2 : continue;
1066 2541 : auto predict = gimple_predict_predictor (s);
1067 2541 : if (predict == PRED_HOT_LABEL
1068 2541 : || predict == PRED_COLD_LABEL)
1069 : return true;
1070 : }
1071 : return false;
1072 : }
1073 :
1074 : /* The function match_simplify_replacement does the main work of doing the
1075 : replacement using match and simplify. Return true if the replacement is done.
1076 : Otherwise return false.
1077 : BB is the basic block where the replacement is going to be done on. ARG0
1078 : is argument 0 from PHI. Likewise for ARG1. */
1079 :
1080 : static bool
1081 868186 : match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
1082 : basic_block middle_bb_alt,
1083 : edge e0, edge e1, gphi *phi,
1084 : tree arg0, tree arg1, bool early_p,
1085 : bool threeway_p)
1086 : {
1087 868186 : gimple *stmt;
1088 868186 : gimple_stmt_iterator gsi;
1089 868186 : edge true_edge, false_edge;
1090 868186 : gimple_seq seq = NULL;
1091 868186 : tree result;
1092 868186 : gimple *stmt_to_move = NULL;
1093 868186 : gimple *stmt_to_move_alt = NULL;
1094 868186 : tree arg_true, arg_false;
1095 :
1096 : /* Special case A ? B : B as this will always simplify to B. */
1097 868186 : if (operand_equal_for_phi_arg_p (arg0, arg1))
1098 : return false;
1099 :
1100 : /* If the basic block only has a cheap preparation statement,
1101 : allow it and move it once the transformation is done. */
1102 868186 : if (!empty_bb_or_one_feeding_into_p (middle_bb, phi, stmt_to_move))
1103 : return false;
1104 :
1105 565655 : if (threeway_p
1106 565655 : && middle_bb != middle_bb_alt
1107 565655 : && !empty_bb_or_one_feeding_into_p (middle_bb_alt, phi,
1108 : stmt_to_move_alt))
1109 : return false;
1110 :
1111 : /* Do not make conditional undefs unconditional. */
1112 551561 : if ((TREE_CODE (arg0) == SSA_NAME
1113 290787 : && ssa_name_maybe_undef_p (arg0))
1114 842030 : || (TREE_CODE (arg1) == SSA_NAME
1115 242503 : && ssa_name_maybe_undef_p (arg1)))
1116 : return false;
1117 :
1118 : /* At this point we know we have a GIMPLE_COND with two successors.
1119 : One successor is BB, the other successor is an empty block which
1120 : falls through into BB.
1121 :
1122 : There is a single PHI node at the join point (BB).
1123 :
1124 : So, given the condition COND, and the two PHI arguments, match and simplify
1125 : can happen on (COND) ? arg0 : arg1. */
1126 :
1127 546980 : stmt = last_nondebug_stmt (cond_bb);
1128 :
1129 : /* We need to know which is the true edge and which is the false
1130 : edge so that we know when to invert the condition below. */
1131 546980 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1132 :
1133 : /* Forward the edges over the middle basic block. */
1134 546980 : if (true_edge->dest == middle_bb)
1135 353154 : true_edge = EDGE_SUCC (true_edge->dest, 0);
1136 546980 : if (false_edge->dest == middle_bb)
1137 193826 : false_edge = EDGE_SUCC (false_edge->dest, 0);
1138 :
1139 : /* When THREEWAY_P then e1 will point to the edge of the final transition
1140 : from middle-bb to end. */
1141 546980 : if (true_edge == e0)
1142 : {
1143 353154 : if (!threeway_p)
1144 336158 : gcc_assert (false_edge == e1);
1145 : arg_true = arg0;
1146 : arg_false = arg1;
1147 : }
1148 : else
1149 : {
1150 193826 : gcc_assert (false_edge == e0);
1151 193826 : if (!threeway_p)
1152 193375 : gcc_assert (true_edge == e1);
1153 : arg_true = arg1;
1154 : arg_false = arg0;
1155 : }
1156 :
1157 546980 : tree type = TREE_TYPE (gimple_phi_result (phi));
1158 546980 : {
1159 546980 : auto_flow_sensitive s1(stmt_to_move);
1160 546980 : auto_flow_sensitive s_alt(stmt_to_move_alt);
1161 :
1162 546980 : result = gimple_simplify_phiopt (early_p, type, stmt,
1163 : arg_true, arg_false,
1164 : &seq);
1165 546980 : }
1166 :
1167 : /* For early phiopt, we don't want to lose user generated predictors
1168 : if the phiopt is converting `if (a)` into `a` as that might
1169 : be jump threaded later on so we want to keep around the
1170 : predictors. */
1171 546980 : if (early_p && result && TREE_CODE (result) == SSA_NAME)
1172 : {
1173 28667 : bool check_it = false;
1174 28667 : tree cmp0 = gimple_cond_lhs (stmt);
1175 28667 : tree cmp1 = gimple_cond_rhs (stmt);
1176 28667 : if (result == cmp0 || result == cmp1)
1177 : check_it = true;
1178 22673 : else if (gimple_seq_singleton_p (seq))
1179 : {
1180 22538 : gimple *stmt = gimple_seq_first_stmt (seq);
1181 22538 : if (is_gimple_assign (stmt)
1182 22538 : && result == gimple_assign_lhs (stmt)
1183 45076 : && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
1184 : == tcc_comparison)
1185 : check_it = true;
1186 : }
1187 : if (!check_it)
1188 : ;
1189 5994 : else if (contains_hot_cold_predict (middle_bb))
1190 : return false;
1191 5993 : else if (threeway_p
1192 : && middle_bb != middle_bb_alt
1193 5993 : && contains_hot_cold_predict (middle_bb_alt))
1194 : return false;
1195 : }
1196 :
1197 546972 : if (!result)
1198 : {
1199 : /* If we don't get back a MIN/MAX_EXPR still make sure the expression
1200 : stays in a form to be recognized by ISA that map to IEEE x > y ? x : y
1201 : semantics (that's not IEEE max semantics). */
1202 454918 : if (!HONOR_NANS (type) && !HONOR_SIGNED_ZEROS (type))
1203 : return false;
1204 17098 : if (stmt_to_move || stmt_to_move_alt)
1205 : return false;
1206 14159 : tree_code cmp = gimple_cond_code (stmt);
1207 14159 : if (cmp != LT_EXPR && cmp != LE_EXPR
1208 14159 : && cmp != GT_EXPR && cmp != GE_EXPR)
1209 : return false;
1210 6888 : tree lhs = gimple_cond_lhs (stmt);
1211 6888 : tree rhs = gimple_cond_rhs (stmt);
1212 : /* `lhs CMP rhs ? lhs : rhs` or `lhs CMP rhs ? rhs : lhs`
1213 : are only acceptable case here. */
1214 6888 : if ((!operand_equal_for_phi_arg_p (lhs, arg_false)
1215 2676 : || !operand_equal_for_phi_arg_p (rhs, arg_true))
1216 6966 : && (!operand_equal_for_phi_arg_p (rhs, arg_false)
1217 1609 : || !operand_equal_for_phi_arg_p (lhs, arg_true)))
1218 : return false;
1219 4045 : seq = nullptr;
1220 4045 : result = gimple_build (&seq, cmp, boolean_type_node, lhs, rhs);
1221 4045 : result = gimple_build (&seq, COND_EXPR, type, result,
1222 : arg_true, arg_false);
1223 4045 : statistics_counter_event (cfun, "Non-IEEE FP MIN/MAX PHI replacement",
1224 : 1);
1225 : }
1226 96106 : if (dump_file && (dump_flags & TDF_FOLDING))
1227 1 : fprintf (dump_file, "accepted the phiopt match-simplify.\n");
1228 :
1229 96106 : auto_bitmap exprs_maybe_dce;
1230 :
1231 : /* Mark the cond statements' lhs/rhs as maybe dce. */
1232 96106 : if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
1233 96106 : && !SSA_NAME_IS_DEFAULT_DEF (gimple_cond_lhs (stmt)))
1234 90615 : bitmap_set_bit (exprs_maybe_dce,
1235 90615 : SSA_NAME_VERSION (gimple_cond_lhs (stmt)));
1236 96106 : if (TREE_CODE (gimple_cond_rhs (stmt)) == SSA_NAME
1237 96106 : && !SSA_NAME_IS_DEFAULT_DEF (gimple_cond_rhs (stmt)))
1238 28547 : bitmap_set_bit (exprs_maybe_dce,
1239 28547 : SSA_NAME_VERSION (gimple_cond_rhs (stmt)));
1240 :
1241 96106 : gsi = gsi_last_bb (cond_bb);
1242 : /* Insert the sequence generated from gimple_simplify_phiopt. */
1243 96106 : if (seq)
1244 : {
1245 : // Mark the lhs of the new statements maybe for dce
1246 88177 : mark_lhs_in_seq_for_dce (exprs_maybe_dce, seq);
1247 88177 : gsi_insert_seq_before (&gsi, seq, GSI_CONTINUE_LINKING);
1248 : }
1249 :
1250 : /* If there was a statement to move, move it to right before
1251 : the original conditional. */
1252 96106 : move_stmt (stmt_to_move, &gsi, exprs_maybe_dce);
1253 96106 : move_stmt (stmt_to_move_alt, &gsi, exprs_maybe_dce);
1254 :
1255 96106 : replace_phi_edge_with_variable (cond_bb, e1, phi, result, exprs_maybe_dce);
1256 :
1257 : /* Add Statistic here even though replace_phi_edge_with_variable already
1258 : does it as we want to be able to count when match-simplify happens vs
1259 : the others. */
1260 96106 : statistics_counter_event (cfun, "match-simplify PHI replacement", 1);
1261 :
1262 : /* Note that we optimized this PHI. */
1263 96106 : return true;
1264 96106 : }
1265 :
1266 : /* The function comparison_combine tries to handle cases like:
1267 : if (a CMP0 b)
1268 : d = a CMP1 b;
1269 : PHI<d, [0,1]>
1270 : This has to be seperately as `a CMP1 b` might be trapping and
1271 : match_simplify_replacement does not handle trapping statements.
1272 : Returns true if a replacement happens. */
1273 :
1274 : static bool
1275 772080 : comparison_combine (basic_block cond_bb, basic_block middle_bb,
1276 : basic_block middle_bb_alt,
1277 : edge e0, edge e1, gphi *phi,
1278 : tree arg0, tree arg1, bool threeway_p)
1279 : {
1280 772080 : gcond *stmt;
1281 772080 : gimple_stmt_iterator gsi;
1282 772080 : edge true_edge, false_edge;
1283 772080 : tree arg_true, arg_false;
1284 :
1285 772080 : if (!types_compatible_p (boolean_type_node, TREE_TYPE (arg0)))
1286 : return false;
1287 :
1288 : /* Do not make conditional undefs unconditional. */
1289 118738 : if ((TREE_CODE (arg0) == SSA_NAME
1290 86086 : && ssa_name_maybe_undef_p (arg0))
1291 204824 : || (TREE_CODE (arg1) == SSA_NAME
1292 19239 : && ssa_name_maybe_undef_p (arg1)))
1293 : return false;
1294 :
1295 118719 : stmt = as_a<gcond*>(last_nondebug_stmt (cond_bb));
1296 :
1297 : // Handle only floating point types as they only trap.
1298 : // The match and simplify will handle the non-trapping case.
1299 118719 : if (!FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))))
1300 : return false;
1301 :
1302 : /* Needs to be PHI<[1,0],arg1> PHI<arg0,[1,0]>. */
1303 5473 : if (((!integer_onep (arg0) && !integer_zerop (arg0))
1304 1213 : || TREE_CODE (arg1) != SSA_NAME)
1305 5608 : && ((!integer_onep (arg1) && !integer_zerop (arg1))
1306 2365 : || TREE_CODE (arg0) != SSA_NAME))
1307 : return false;
1308 :
1309 1188 : gassign *other_cmp = nullptr;
1310 1188 : if (!one_feeding_comparison_into_p (middle_bb, phi, other_cmp))
1311 : {
1312 836 : if (!threeway_p || middle_bb == middle_bb_alt)
1313 : return false;
1314 12 : if (!empty_block_p (middle_bb))
1315 : return false;
1316 12 : if (!one_feeding_comparison_into_p (middle_bb_alt, phi, other_cmp))
1317 : return false;
1318 : }
1319 352 : else if (threeway_p
1320 352 : && middle_bb != middle_bb_alt
1321 352 : && !empty_block_p (middle_bb_alt))
1322 : return false;
1323 :
1324 : /* We need to know which is the true edge and which is the false
1325 : edge so that we know when to invert the condition below. */
1326 354 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1327 :
1328 : /* Forward the edges over the middle basic block. */
1329 354 : if (true_edge->dest == middle_bb)
1330 247 : true_edge = EDGE_SUCC (true_edge->dest, 0);
1331 354 : if (false_edge->dest == middle_bb)
1332 107 : false_edge = EDGE_SUCC (false_edge->dest, 0);
1333 : /* When THREEWAY_P then e1 will point to the edge of the final transition
1334 : from middle-bb to end. */
1335 354 : if (true_edge == e0)
1336 : {
1337 247 : if (!threeway_p)
1338 245 : gcc_assert (false_edge == e1);
1339 : arg_true = arg0;
1340 : arg_false = arg1;
1341 : }
1342 : else
1343 : {
1344 107 : gcc_assert (false_edge == e0);
1345 107 : if (!threeway_p)
1346 107 : gcc_assert (true_edge == e1);
1347 : arg_true = arg1;
1348 : arg_false = arg0;
1349 : }
1350 354 : if (TREE_CODE (arg_true) == SSA_NAME
1351 354 : && arg_true != gimple_assign_lhs (other_cmp))
1352 : return false;
1353 354 : if (TREE_CODE (arg_false) == SSA_NAME
1354 354 : && arg_false != gimple_assign_lhs (other_cmp))
1355 : return false;
1356 :
1357 354 : tree larg = gimple_cond_lhs (stmt);
1358 354 : tree rarg = gimple_cond_rhs (stmt);
1359 354 : if (!operand_equal_p (larg, gimple_assign_rhs1 (other_cmp))
1360 569 : || !operand_equal_p (rarg, gimple_assign_rhs2 (other_cmp)))
1361 : return false;
1362 :
1363 78 : tree_code logical;
1364 : // a CMP0 b ? 1 : a CMP1 b -> `a CMP0 b || a CMP1 b`
1365 : // a CMP0 b ? a CMP1 b : 1 -> `!(a CMP0 b) || a CMP1 b`
1366 :
1367 : // a CMP0 b ? a CMP1 b : 0 -> `a CMP0 b && a CMP1 b`
1368 : // a CMP0 b ? 0 : a CMP1 b -> `!(a CMP0 b) && a CMP1 b`
1369 78 : if (integer_onep (arg_true) || integer_onep (arg_false))
1370 : logical = TRUTH_ORIF_EXPR;
1371 : else
1372 : logical = TRUTH_ANDIF_EXPR;
1373 78 : tree_code outer_code = gimple_cond_code (stmt);
1374 78 : tree_code inner_code = gimple_assign_rhs_code (other_cmp);
1375 : // Invert the outter if needed.
1376 78 : if (integer_onep (arg_false) || integer_zerop (arg_true))
1377 : {
1378 0 : outer_code = invert_tree_comparison (outer_code,
1379 : HONOR_NANS (larg));
1380 : // In theory could handle it as !((a CMP0 b) LOGICAL' !(a CMP1 b))
1381 : // Most likely the outer comparison will be EQ/NE which is invertable.
1382 0 : if (outer_code == ERROR_MARK)
1383 : return false;
1384 : }
1385 78 : tree result;
1386 78 : tree_code newcmp_code;
1387 78 : newcmp_code = combine_comparisons (logical, outer_code, inner_code,
1388 : boolean_type_node,
1389 : HONOR_NANS (larg), &result);
1390 78 : if (newcmp_code == ERROR_MARK)
1391 : return false;
1392 16 : gimple_seq seq = nullptr;
1393 16 : if (newcmp_code != INTEGER_CST)
1394 16 : result = gimple_build (&seq, newcmp_code, boolean_type_node,
1395 : larg, rarg);
1396 16 : gsi = gsi_last_bb (cond_bb);
1397 16 : gsi_insert_seq_before (&gsi, seq, GSI_CONTINUE_LINKING);
1398 16 : replace_phi_edge_with_variable (cond_bb, e1, phi, result);
1399 16 : return true;
1400 : }
1401 :
1402 : /* Update *ARG which is defined in STMT so that it contains the
1403 : computed value if that seems profitable. Return true if the
1404 : statement is made dead by that rewriting. */
1405 :
1406 : static bool
1407 339770 : jump_function_from_stmt (tree *arg, gimple *stmt)
1408 : {
1409 339770 : enum tree_code code = gimple_assign_rhs_code (stmt);
1410 339770 : if (code == ADDR_EXPR)
1411 : {
1412 : /* For arg = &p->i transform it to p, if possible. */
1413 5110 : tree rhs1 = gimple_assign_rhs1 (stmt);
1414 5110 : poly_int64 offset;
1415 5110 : tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs1, 0),
1416 : &offset);
1417 5110 : if (tem
1418 5029 : && TREE_CODE (tem) == MEM_REF
1419 10139 : && known_eq (mem_ref_offset (tem) + offset, 0))
1420 : {
1421 2358 : *arg = TREE_OPERAND (tem, 0);
1422 2358 : return true;
1423 : }
1424 : }
1425 : /* TODO: Much like IPA-CP jump-functions we want to handle constant
1426 : additions symbolically here, and we'd need to update the comparison
1427 : code that compares the arg + cst tuples in our caller. For now the
1428 : code above exactly handles the VEC_BASE pattern from vec.h. */
1429 : return false;
1430 : }
1431 :
1432 : /* RHS is a source argument in a BIT_AND_EXPR or BIT_IOR_EXPR which feeds
1433 : a conditional of the form SSA_NAME NE 0.
1434 :
1435 : If RHS is fed by a simple EQ_EXPR or NE_EXPR comparison of two values,
1436 : see if the two input values of the comparison match arg0 and arg1.
1437 :
1438 : If so update *code and return TRUE. Otherwise return FALSE. */
1439 :
1440 : static bool
1441 162716 : rhs_is_fed_for_value_replacement (const_tree arg0, const_tree arg1,
1442 : enum tree_code *code, const_tree rhs,
1443 : enum tree_code bit_expression_code)
1444 : {
1445 : /* Obviously if RHS is not an SSA_NAME, we can't look at the defining
1446 : statement. */
1447 162716 : if (TREE_CODE (rhs) == SSA_NAME)
1448 : {
1449 127285 : gimple *def1 = SSA_NAME_DEF_STMT (rhs);
1450 :
1451 : /* Verify the defining statement has an EQ_EXPR or NE_EXPR on the RHS. */
1452 127285 : if (is_gimple_assign (def1)
1453 127285 : && ((bit_expression_code == BIT_AND_EXPR
1454 78394 : && gimple_assign_rhs_code (def1) == EQ_EXPR)
1455 95159 : || (bit_expression_code == BIT_IOR_EXPR
1456 38813 : && gimple_assign_rhs_code (def1) == NE_EXPR)))
1457 : {
1458 : /* Finally verify the source operands of the EQ_EXPR or NE_EXPR
1459 : are equal to arg0 and arg1. */
1460 27180 : tree op0 = gimple_assign_rhs1 (def1);
1461 27180 : tree op1 = gimple_assign_rhs2 (def1);
1462 27180 : if ((operand_equal_for_phi_arg_p (arg0, op0)
1463 662 : && operand_equal_for_phi_arg_p (arg1, op1))
1464 27781 : || (operand_equal_for_phi_arg_p (arg0, op1)
1465 637 : && operand_equal_for_phi_arg_p (arg1, op0)))
1466 : {
1467 : /* We will perform the optimization. */
1468 473 : *code = gimple_assign_rhs_code (def1);
1469 473 : return true;
1470 : }
1471 : }
1472 : }
1473 : return false;
1474 : }
1475 :
1476 : /* Return TRUE if arg0/arg1 are equal to the rhs/lhs or lhs/rhs of COND.
1477 :
1478 : Also return TRUE if arg0/arg1 are equal to the source arguments of an
1479 : EQ comparison feeding a BIT_AND_EXPR, or NE comparison feeding a
1480 : BIT_IOR_EXPR which feeds COND.
1481 :
1482 : Return FALSE otherwise. */
1483 :
1484 : static bool
1485 681456 : operand_equal_for_value_replacement (const_tree arg0, const_tree arg1,
1486 : enum tree_code *code, gimple *cond)
1487 : {
1488 681456 : gimple *def;
1489 681456 : tree lhs = gimple_cond_lhs (cond);
1490 681456 : tree rhs = gimple_cond_rhs (cond);
1491 :
1492 681456 : if ((operand_equal_for_phi_arg_p (arg0, lhs)
1493 29235 : && operand_equal_for_phi_arg_p (arg1, rhs))
1494 701384 : || (operand_equal_for_phi_arg_p (arg1, lhs)
1495 46708 : && operand_equal_for_phi_arg_p (arg0, rhs)))
1496 : return true;
1497 :
1498 : /* Now handle more complex case where we have an EQ comparison
1499 : feeding a BIT_AND_EXPR, or a NE comparison feeding a BIT_IOR_EXPR,
1500 : which then feeds into COND.
1501 :
1502 : First verify that COND is of the form SSA_NAME NE 0. */
1503 387830 : if (*code != NE_EXPR || !integer_zerop (rhs)
1504 949018 : || TREE_CODE (lhs) != SSA_NAME)
1505 : return false;
1506 :
1507 : /* Now ensure that SSA_NAME is set by a BIT_AND_EXPR or BIT_OR_EXPR. */
1508 280412 : def = SSA_NAME_DEF_STMT (lhs);
1509 280412 : if (!is_gimple_assign (def)
1510 280412 : || (gimple_assign_rhs_code (def) != BIT_AND_EXPR
1511 135827 : && gimple_assign_rhs_code (def) != BIT_IOR_EXPR))
1512 : return false;
1513 :
1514 : /* Now verify arg0/arg1 correspond to the source arguments of an EQ
1515 : comparison feeding the BIT_AND_EXPR or a NE comparison feeding the
1516 : BIT_IOR_EXPR. */
1517 :
1518 81524 : tree tmp = gimple_assign_rhs1 (def);
1519 81524 : if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp,
1520 : gimple_assign_rhs_code (def)))
1521 : return true;
1522 :
1523 81192 : tmp = gimple_assign_rhs2 (def);
1524 81192 : if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp,
1525 : gimple_assign_rhs_code (def)))
1526 : return true;
1527 :
1528 : return false;
1529 : }
1530 :
1531 : /* Returns true if ARG is a neutral element for operation CODE
1532 : on the RIGHT side. */
1533 :
1534 : static bool
1535 674 : neutral_element_p (tree_code code, tree arg, bool right)
1536 : {
1537 674 : switch (code)
1538 : {
1539 29 : case PLUS_EXPR:
1540 29 : case BIT_IOR_EXPR:
1541 29 : case BIT_XOR_EXPR:
1542 29 : return integer_zerop (arg);
1543 :
1544 191 : case LROTATE_EXPR:
1545 191 : case RROTATE_EXPR:
1546 191 : case LSHIFT_EXPR:
1547 191 : case RSHIFT_EXPR:
1548 191 : case MINUS_EXPR:
1549 191 : case POINTER_PLUS_EXPR:
1550 191 : return right && integer_zerop (arg);
1551 :
1552 327 : case MULT_EXPR:
1553 327 : return integer_onep (arg);
1554 :
1555 31 : case TRUNC_DIV_EXPR:
1556 31 : case CEIL_DIV_EXPR:
1557 31 : case FLOOR_DIV_EXPR:
1558 31 : case ROUND_DIV_EXPR:
1559 31 : case EXACT_DIV_EXPR:
1560 31 : return right && integer_onep (arg);
1561 :
1562 0 : case BIT_AND_EXPR:
1563 0 : return integer_all_onesp (arg);
1564 :
1565 : default:
1566 : return false;
1567 : }
1568 : }
1569 :
1570 : /* Returns true if ARG is an absorbing element for operation CODE. */
1571 :
1572 : static bool
1573 881 : absorbing_element_p (tree_code code, tree arg, bool right, tree rval)
1574 : {
1575 881 : switch (code)
1576 : {
1577 18 : case BIT_IOR_EXPR:
1578 18 : return integer_all_onesp (arg);
1579 :
1580 38 : case MULT_EXPR:
1581 38 : case BIT_AND_EXPR:
1582 38 : return integer_zerop (arg);
1583 :
1584 3 : case LSHIFT_EXPR:
1585 3 : case RSHIFT_EXPR:
1586 3 : case LROTATE_EXPR:
1587 3 : case RROTATE_EXPR:
1588 3 : return !right && integer_zerop (arg);
1589 :
1590 167 : case TRUNC_DIV_EXPR:
1591 167 : case CEIL_DIV_EXPR:
1592 167 : case FLOOR_DIV_EXPR:
1593 167 : case ROUND_DIV_EXPR:
1594 167 : case EXACT_DIV_EXPR:
1595 167 : case TRUNC_MOD_EXPR:
1596 167 : case CEIL_MOD_EXPR:
1597 167 : case FLOOR_MOD_EXPR:
1598 167 : case ROUND_MOD_EXPR:
1599 167 : return (!right
1600 9 : && integer_zerop (arg)
1601 175 : && tree_single_nonzero_p (rval));
1602 :
1603 : default:
1604 : return false;
1605 : }
1606 : }
1607 :
1608 : /* The function value_replacement does the main work of doing the value
1609 : replacement. Return non-zero if the replacement is done. Otherwise return
1610 : 0. If we remove the middle basic block, return 2.
1611 : BB is the basic block where the replacement is going to be done on. ARG0
1612 : is argument 0 from the PHI. Likewise for ARG1. */
1613 :
1614 : static int
1615 2497235 : value_replacement (basic_block cond_bb, basic_block middle_bb,
1616 : edge e0, edge e1, gphi *phi, tree arg0, tree arg1)
1617 : {
1618 2497235 : gimple_stmt_iterator gsi;
1619 2497235 : edge true_edge, false_edge;
1620 2497235 : enum tree_code code;
1621 2497235 : bool empty_or_with_defined_p = true;
1622 :
1623 : /* Virtual operands don't need to be handled. */
1624 4444626 : if (virtual_operand_p (arg1))
1625 : return 0;
1626 :
1627 : /* Special case A ? B : B as this will always simplify to B. */
1628 1324423 : if (operand_equal_for_phi_arg_p (arg0, arg1))
1629 : return 0;
1630 :
1631 2354914 : gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_bb));
1632 1177457 : code = gimple_cond_code (cond);
1633 :
1634 : /* This transformation is only valid for equality comparisons. */
1635 1177457 : if (code != NE_EXPR && code != EQ_EXPR)
1636 : return 0;
1637 :
1638 : /* Do not make conditional undefs unconditional. */
1639 710912 : if ((TREE_CODE (arg0) == SSA_NAME
1640 549454 : && ssa_name_maybe_undef_p (arg0))
1641 1258592 : || (TREE_CODE (arg1) == SSA_NAME
1642 308254 : && ssa_name_maybe_undef_p (arg1)))
1643 : return false;
1644 :
1645 : /* If the type says honor signed zeros we cannot do this
1646 : optimization. */
1647 694772 : if (HONOR_SIGNED_ZEROS (arg1))
1648 : return 0;
1649 :
1650 : /* If there is a statement in MIDDLE_BB that defines one of the PHI
1651 : arguments, then adjust arg0 or arg1. */
1652 681456 : gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
1653 2158511 : while (!gsi_end_p (gsi))
1654 : {
1655 1477055 : gimple *stmt = gsi_stmt (gsi);
1656 1477055 : tree lhs;
1657 1477055 : gsi_next_nondebug (&gsi);
1658 1477055 : if (!is_gimple_assign (stmt))
1659 : {
1660 208032 : if (gimple_code (stmt) != GIMPLE_PREDICT
1661 208032 : && gimple_code (stmt) != GIMPLE_NOP)
1662 : empty_or_with_defined_p = false;
1663 208032 : continue;
1664 : }
1665 : /* Now try to adjust arg0 or arg1 according to the computation
1666 : in the statement. */
1667 1269023 : lhs = gimple_assign_lhs (stmt);
1668 339770 : if (!(lhs == arg0
1669 339770 : && jump_function_from_stmt (&arg0, stmt))
1670 1271381 : || (lhs == arg1
1671 0 : && jump_function_from_stmt (&arg1, stmt)))
1672 1477055 : empty_or_with_defined_p = false;
1673 : }
1674 :
1675 : /* The middle bb is not empty if there are any phi nodes. */
1676 681456 : if (phi_nodes (middle_bb))
1677 76917 : empty_or_with_defined_p = false;
1678 :
1679 : /* We need to know which is the true edge and which is the false
1680 : edge so that we know if have abs or negative abs. */
1681 681456 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1682 :
1683 : /* At this point we know we have a COND_EXPR with two successors.
1684 : One successor is BB, the other successor is an empty block which
1685 : falls through into BB.
1686 :
1687 : The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
1688 :
1689 : There is a single PHI node at the join point (BB) with two arguments.
1690 :
1691 : We now need to verify that the two arguments in the PHI node match
1692 : the two arguments to the equality comparison. */
1693 :
1694 681456 : bool equal_p = operand_equal_for_value_replacement (arg0, arg1, &code, cond);
1695 681456 : bool maybe_equal_p = false;
1696 681456 : if (!equal_p
1697 681456 : && empty_or_with_defined_p
1698 188610 : && TREE_CODE (gimple_cond_rhs (cond)) == INTEGER_CST
1699 829526 : && (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond), arg0)
1700 148070 : ? TREE_CODE (arg1) == INTEGER_CST
1701 138722 : : (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond), arg1)
1702 21502 : && TREE_CODE (arg0) == INTEGER_CST)))
1703 : maybe_equal_p = true;
1704 661877 : if (equal_p || maybe_equal_p)
1705 : {
1706 33303 : edge e;
1707 33303 : tree arg;
1708 :
1709 : /* For NE_EXPR, we want to build an assignment result = arg where
1710 : arg is the PHI argument associated with the true edge. For
1711 : EQ_EXPR we want the PHI argument associated with the false edge. */
1712 33303 : e = (code == NE_EXPR ? true_edge : false_edge);
1713 :
1714 : /* Unfortunately, E may not reach BB (it may instead have gone to
1715 : OTHER_BLOCK). If that is the case, then we want the single outgoing
1716 : edge from OTHER_BLOCK which reaches BB and represents the desired
1717 : path from COND_BLOCK. */
1718 33303 : if (e->dest == middle_bb)
1719 15055 : e = single_succ_edge (e->dest);
1720 :
1721 : /* Now we know the incoming edge to BB that has the argument for the
1722 : RHS of our new assignment statement. */
1723 33303 : if (e0 == e)
1724 : arg = arg0;
1725 : else
1726 18248 : arg = arg1;
1727 :
1728 : /* If the middle basic block was empty or is defining the
1729 : PHI arguments and this is a single phi where the args are different
1730 : for the edges e0 and e1 then we can remove the middle basic block. */
1731 33303 : if (empty_or_with_defined_p
1732 33303 : && single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)),
1733 : e0, e1) == phi)
1734 : {
1735 19835 : use_operand_p use_p;
1736 19835 : gimple *use_stmt;
1737 :
1738 : /* Even if arg0/arg1 isn't equal to second operand of cond, we
1739 : can optimize away the bb if we can prove it doesn't care whether
1740 : phi result is arg0/arg1 or second operand of cond. Consider:
1741 : <bb 2> [local count: 118111600]:
1742 : if (i_2(D) == 4)
1743 : goto <bb 4>; [97.00%]
1744 : else
1745 : goto <bb 3>; [3.00%]
1746 :
1747 : <bb 3> [local count: 3540129]:
1748 :
1749 : <bb 4> [local count: 118111600]:
1750 : # i_6 = PHI <i_2(D)(3), 6(2)>
1751 : _3 = i_6 != 0;
1752 : Here, carg is 4, oarg is 6, crhs is 0, and because
1753 : (4 != 0) == (6 != 0), we don't care if i_6 is 4 or 6, both
1754 : have the same outcome. So, we can optimize this to:
1755 : _3 = i_2(D) != 0;
1756 : If the single imm use of phi result >, >=, < or <=, similarly
1757 : we can check if both carg and oarg compare the same against
1758 : crhs using ccode. */
1759 19835 : if (maybe_equal_p
1760 17982 : && TREE_CODE (arg) != INTEGER_CST
1761 37802 : && single_imm_use (gimple_phi_result (phi), &use_p, &use_stmt))
1762 : {
1763 10201 : enum tree_code ccode = ERROR_MARK;
1764 10201 : tree clhs = NULL_TREE, crhs = NULL_TREE;
1765 10201 : tree carg = gimple_cond_rhs (cond);
1766 10201 : tree oarg = e0 == e ? arg1 : arg0;
1767 10201 : if (is_gimple_assign (use_stmt)
1768 10201 : && (TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
1769 : == tcc_comparison))
1770 : {
1771 57 : ccode = gimple_assign_rhs_code (use_stmt);
1772 57 : clhs = gimple_assign_rhs1 (use_stmt);
1773 57 : crhs = gimple_assign_rhs2 (use_stmt);
1774 : }
1775 10144 : else if (gimple_code (use_stmt) == GIMPLE_COND)
1776 : {
1777 79 : ccode = gimple_cond_code (use_stmt);
1778 79 : clhs = gimple_cond_lhs (use_stmt);
1779 79 : crhs = gimple_cond_rhs (use_stmt);
1780 : }
1781 136 : if (ccode != ERROR_MARK
1782 136 : && clhs == gimple_phi_result (phi)
1783 233 : && TREE_CODE (crhs) == INTEGER_CST)
1784 45 : switch (ccode)
1785 : {
1786 26 : case EQ_EXPR:
1787 26 : case NE_EXPR:
1788 26 : if (!tree_int_cst_equal (crhs, carg)
1789 26 : && !tree_int_cst_equal (crhs, oarg))
1790 : equal_p = true;
1791 : break;
1792 2 : case GT_EXPR:
1793 4 : if (tree_int_cst_lt (crhs, carg)
1794 2 : == tree_int_cst_lt (crhs, oarg))
1795 : equal_p = true;
1796 : break;
1797 0 : case GE_EXPR:
1798 0 : if (tree_int_cst_le (crhs, carg)
1799 0 : == tree_int_cst_le (crhs, oarg))
1800 : equal_p = true;
1801 : break;
1802 13 : case LT_EXPR:
1803 26 : if (tree_int_cst_lt (carg, crhs)
1804 13 : == tree_int_cst_lt (oarg, crhs))
1805 : equal_p = true;
1806 : break;
1807 4 : case LE_EXPR:
1808 8 : if (tree_int_cst_le (carg, crhs)
1809 4 : == tree_int_cst_le (oarg, crhs))
1810 : equal_p = true;
1811 : break;
1812 : default:
1813 : break;
1814 : }
1815 10185 : if (equal_p)
1816 : {
1817 16 : tree phires = gimple_phi_result (phi);
1818 16 : if (SSA_NAME_RANGE_INFO (phires))
1819 : {
1820 : /* After the optimization PHI result can have value
1821 : which it couldn't have previously. */
1822 15 : value_range r (TREE_TYPE (phires));
1823 15 : if (get_global_range_query ()->range_of_expr (r, phires,
1824 : phi))
1825 : {
1826 15 : value_range tmp (carg, carg);
1827 15 : r.union_ (tmp);
1828 15 : reset_flow_sensitive_info (phires);
1829 15 : set_range_info (phires, r);
1830 15 : }
1831 : else
1832 0 : reset_flow_sensitive_info (phires);
1833 15 : }
1834 : }
1835 16 : if (equal_p && MAY_HAVE_DEBUG_BIND_STMTS)
1836 : {
1837 13 : imm_use_iterator imm_iter;
1838 13 : tree phires = gimple_phi_result (phi);
1839 13 : tree temp = NULL_TREE;
1840 13 : bool reset_p = false;
1841 :
1842 : /* Add # DEBUG D#1 => arg != carg ? arg : oarg. */
1843 42 : FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, phires)
1844 : {
1845 30 : if (!is_gimple_debug (use_stmt))
1846 13 : continue;
1847 17 : if (temp == NULL_TREE)
1848 : {
1849 12 : if (!single_pred_p (middle_bb)
1850 12 : || EDGE_COUNT (gimple_bb (phi)->preds) != 2)
1851 : {
1852 : /* But only if middle_bb has a single
1853 : predecessor and phi bb has two, otherwise
1854 : we could use a SSA_NAME not usable in that
1855 : place or wrong-debug. */
1856 1 : reset_p = true;
1857 1 : break;
1858 : }
1859 11 : gimple_stmt_iterator gsi
1860 11 : = gsi_after_labels (gimple_bb (phi));
1861 11 : tree type = TREE_TYPE (phires);
1862 11 : temp = build_debug_expr_decl (type);
1863 11 : tree t = build2 (NE_EXPR, boolean_type_node,
1864 : arg, carg);
1865 11 : t = build3 (COND_EXPR, type, t, arg, oarg);
1866 11 : gimple *g = gimple_build_debug_bind (temp, t, phi);
1867 11 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
1868 : }
1869 32 : FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
1870 16 : replace_exp (use_p, temp);
1871 16 : update_stmt (use_stmt);
1872 13 : }
1873 13 : if (reset_p)
1874 1 : reset_debug_uses (phi);
1875 : }
1876 : }
1877 9650 : if (equal_p)
1878 : {
1879 1869 : replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
1880 : /* Note that we optimized this PHI. */
1881 1869 : return 2;
1882 : }
1883 : }
1884 13468 : else if (equal_p)
1885 : {
1886 11871 : if (!single_pred_p (middle_bb))
1887 : return 0;
1888 11001 : statistics_counter_event (cfun, "Replace PHI with "
1889 : "variable/value_replacement", 1);
1890 :
1891 : /* Replace the PHI arguments with arg. */
1892 11001 : SET_PHI_ARG_DEF (phi, e0->dest_idx, arg);
1893 11001 : SET_PHI_ARG_DEF (phi, e1->dest_idx, arg);
1894 11001 : if (dump_file && (dump_flags & TDF_DETAILS))
1895 : {
1896 0 : fprintf (dump_file, "PHI ");
1897 0 : print_generic_expr (dump_file, gimple_phi_result (phi));
1898 0 : fprintf (dump_file, " reduced for COND_EXPR in block %d to ",
1899 : cond_bb->index);
1900 0 : print_generic_expr (dump_file, arg);
1901 0 : fprintf (dump_file, ".\n");
1902 : }
1903 : return 1;
1904 : }
1905 : }
1906 :
1907 667716 : if (!single_pred_p (middle_bb))
1908 : return 0;
1909 :
1910 : /* Now optimize (x != 0) ? x + y : y to just x + y. */
1911 565472 : gsi = gsi_last_nondebug_bb (middle_bb);
1912 565472 : if (gsi_end_p (gsi))
1913 : return 0;
1914 :
1915 394937 : gimple *assign = gsi_stmt (gsi);
1916 394937 : if (!is_gimple_assign (assign)
1917 394937 : || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
1918 109288 : && !POINTER_TYPE_P (TREE_TYPE (arg0))))
1919 : return 0;
1920 :
1921 334544 : if (gimple_assign_rhs_class (assign) != GIMPLE_BINARY_RHS)
1922 : {
1923 : /* If last stmt of the middle_bb is a conversion, handle it like
1924 : a preparation statement through constant evaluation with
1925 : checking for UB. */
1926 143178 : enum tree_code sc = gimple_assign_rhs_code (assign);
1927 143178 : if (CONVERT_EXPR_CODE_P (sc))
1928 : assign = NULL;
1929 : else
1930 : return 0;
1931 : }
1932 :
1933 : /* Punt if there are (degenerate) PHIs in middle_bb, there should not be. */
1934 214360 : if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
1935 : return 0;
1936 :
1937 : /* Allow up to 2 cheap preparation statements that prepare argument
1938 : for assign, e.g.:
1939 : if (y_4 != 0)
1940 : goto <bb 3>;
1941 : else
1942 : goto <bb 4>;
1943 : <bb 3>:
1944 : _1 = (int) y_4;
1945 : iftmp.0_6 = x_5(D) r<< _1;
1946 : <bb 4>:
1947 : # iftmp.0_2 = PHI <iftmp.0_6(3), x_5(D)(2)>
1948 : or:
1949 : if (y_3(D) == 0)
1950 : goto <bb 4>;
1951 : else
1952 : goto <bb 3>;
1953 : <bb 3>:
1954 : y_4 = y_3(D) & 31;
1955 : _1 = (int) y_4;
1956 : _6 = x_5(D) r<< _1;
1957 : <bb 4>:
1958 : # _2 = PHI <x_5(D)(2), _6(3)> */
1959 214360 : gimple *prep_stmt[2] = { NULL, NULL };
1960 214360 : int prep_cnt;
1961 214360 : for (prep_cnt = 0; ; prep_cnt++)
1962 : {
1963 275754 : if (prep_cnt || assign)
1964 252760 : gsi_prev_nondebug (&gsi);
1965 275754 : if (gsi_end_p (gsi))
1966 : break;
1967 :
1968 207431 : gimple *g = gsi_stmt (gsi);
1969 207431 : if (gimple_code (g) == GIMPLE_LABEL)
1970 : break;
1971 :
1972 207076 : if (prep_cnt == 2 || !is_gimple_assign (g))
1973 145682 : return 0;
1974 :
1975 182435 : tree lhs = gimple_assign_lhs (g);
1976 182435 : tree rhs1 = gimple_assign_rhs1 (g);
1977 182435 : use_operand_p use_p;
1978 182435 : gimple *use_stmt;
1979 182435 : if (TREE_CODE (lhs) != SSA_NAME
1980 175533 : || TREE_CODE (rhs1) != SSA_NAME
1981 111684 : || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1982 108111 : || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1983 104312 : || !single_imm_use (lhs, &use_p, &use_stmt)
1984 285588 : || ((prep_cnt || assign)
1985 81708 : && use_stmt != (prep_cnt ? prep_stmt[prep_cnt - 1] : assign)))
1986 : return 0;
1987 95660 : switch (gimple_assign_rhs_code (g))
1988 : {
1989 : CASE_CONVERT:
1990 : break;
1991 21030 : case PLUS_EXPR:
1992 21030 : case BIT_AND_EXPR:
1993 21030 : case BIT_IOR_EXPR:
1994 21030 : case BIT_XOR_EXPR:
1995 21030 : if (TREE_CODE (gimple_assign_rhs2 (g)) != INTEGER_CST)
1996 : return 0;
1997 : break;
1998 : default:
1999 : return 0;
2000 : }
2001 61394 : prep_stmt[prep_cnt] = g;
2002 61394 : }
2003 :
2004 : /* Only transform if it removes the condition. */
2005 68678 : if (!single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)), e0, e1))
2006 : return 0;
2007 :
2008 : /* Size-wise, this is always profitable. */
2009 52168 : if (optimize_bb_for_speed_p (cond_bb)
2010 : /* The special case is useless if it has a low probability. */
2011 49318 : && profile_status_for_fn (cfun) != PROFILE_ABSENT
2012 60845 : && EDGE_PRED (middle_bb, 0)->probability < profile_probability::even ()
2013 : /* If assign is cheap, there is no point avoiding it. */
2014 63714 : && estimate_num_insns_seq (bb_seq (middle_bb), &eni_time_weights)
2015 11546 : >= 3 * estimate_num_insns (cond, &eni_time_weights))
2016 92 : return 0;
2017 :
2018 52076 : tree cond_lhs = gimple_cond_lhs (cond);
2019 52076 : tree cond_rhs = gimple_cond_rhs (cond);
2020 :
2021 : /* Propagate the cond_rhs constant through preparation stmts,
2022 : make sure UB isn't invoked while doing that. */
2023 53310 : for (int i = prep_cnt - 1; i >= 0; --i)
2024 : {
2025 13235 : gimple *g = prep_stmt[i];
2026 13235 : tree grhs1 = gimple_assign_rhs1 (g);
2027 13235 : if (!operand_equal_for_phi_arg_p (cond_lhs, grhs1))
2028 : return 0;
2029 6821 : cond_lhs = gimple_assign_lhs (g);
2030 6821 : cond_rhs = fold_convert (TREE_TYPE (grhs1), cond_rhs);
2031 6821 : if (TREE_CODE (cond_rhs) != INTEGER_CST
2032 6821 : || TREE_OVERFLOW (cond_rhs))
2033 : return 0;
2034 1234 : if (gimple_assign_rhs_class (g) == GIMPLE_BINARY_RHS)
2035 : {
2036 544 : cond_rhs = int_const_binop (gimple_assign_rhs_code (g), cond_rhs,
2037 544 : gimple_assign_rhs2 (g));
2038 544 : if (TREE_OVERFLOW (cond_rhs))
2039 : return 0;
2040 : }
2041 1234 : cond_rhs = fold_convert (TREE_TYPE (cond_lhs), cond_rhs);
2042 1234 : if (TREE_CODE (cond_rhs) != INTEGER_CST
2043 1234 : || TREE_OVERFLOW (cond_rhs))
2044 : return 0;
2045 : }
2046 :
2047 40075 : tree lhs, rhs1, rhs2;
2048 40075 : enum tree_code code_def;
2049 40075 : if (assign)
2050 : {
2051 39812 : lhs = gimple_assign_lhs (assign);
2052 39812 : rhs1 = gimple_assign_rhs1 (assign);
2053 39812 : rhs2 = gimple_assign_rhs2 (assign);
2054 39812 : code_def = gimple_assign_rhs_code (assign);
2055 : }
2056 : else
2057 : {
2058 263 : gcc_assert (prep_cnt > 0);
2059 : lhs = cond_lhs;
2060 : rhs1 = NULL_TREE;
2061 : rhs2 = NULL_TREE;
2062 : code_def = ERROR_MARK;
2063 : }
2064 :
2065 23360 : if (((code == NE_EXPR && e1 == false_edge)
2066 19588 : || (code == EQ_EXPR && e1 == true_edge))
2067 22853 : && arg0 == lhs
2068 62928 : && ((assign == NULL
2069 262 : && operand_equal_for_phi_arg_p (arg1, cond_rhs))
2070 : || (assign
2071 22591 : && arg1 == rhs1
2072 14933 : && operand_equal_for_phi_arg_p (rhs2, cond_lhs)
2073 385 : && neutral_element_p (code_def, cond_rhs, true))
2074 22531 : || (assign
2075 22531 : && arg1 == rhs2
2076 1013 : && operand_equal_for_phi_arg_p (rhs1, cond_lhs)
2077 289 : && neutral_element_p (code_def, cond_rhs, false))
2078 : || (assign
2079 22531 : && operand_equal_for_phi_arg_p (arg1, cond_rhs)
2080 2849 : && ((operand_equal_for_phi_arg_p (rhs2, cond_lhs)
2081 247 : && absorbing_element_p (code_def, cond_rhs, true, rhs2))
2082 2848 : || (operand_equal_for_phi_arg_p (rhs1, cond_lhs)
2083 634 : && absorbing_element_p (code_def,
2084 : cond_rhs, false, rhs2))))))
2085 : {
2086 94 : gsi = gsi_for_stmt (cond);
2087 : /* Moving ASSIGN might change VR of lhs, e.g. when moving u_6
2088 : def-stmt in:
2089 : if (n_5 != 0)
2090 : goto <bb 3>;
2091 : else
2092 : goto <bb 4>;
2093 :
2094 : <bb 3>:
2095 : # RANGE [0, 4294967294]
2096 : u_6 = n_5 + 4294967295;
2097 :
2098 : <bb 4>:
2099 : # u_3 = PHI <u_6(3), 4294967295(2)> */
2100 94 : reset_flow_sensitive_info (lhs);
2101 94 : gimple_stmt_iterator gsi_from;
2102 263 : for (int i = prep_cnt - 1; i >= 0; --i)
2103 : {
2104 75 : tree plhs = gimple_assign_lhs (prep_stmt[i]);
2105 75 : reset_flow_sensitive_info (plhs);
2106 75 : gsi_from = gsi_for_stmt (prep_stmt[i]);
2107 75 : gsi_move_before (&gsi_from, &gsi);
2108 : }
2109 94 : if (assign)
2110 : {
2111 90 : gsi_from = gsi_for_stmt (assign);
2112 90 : gsi_move_before (&gsi_from, &gsi);
2113 : }
2114 94 : replace_phi_edge_with_variable (cond_bb, e1, phi, lhs);
2115 94 : return 2;
2116 : }
2117 :
2118 : return 0;
2119 : }
2120 :
2121 : /* Attempt to optimize (x <=> y) cmp 0 and similar comparisons.
2122 : For strong ordering <=> try to match something like:
2123 : <bb 2> : // cond3_bb (== cond2_bb)
2124 : if (x_4(D) != y_5(D))
2125 : goto <bb 3>; [INV]
2126 : else
2127 : goto <bb 6>; [INV]
2128 :
2129 : <bb 3> : // cond_bb
2130 : if (x_4(D) < y_5(D))
2131 : goto <bb 6>; [INV]
2132 : else
2133 : goto <bb 4>; [INV]
2134 :
2135 : <bb 4> : // middle_bb
2136 :
2137 : <bb 6> : // phi_bb
2138 : # iftmp.0_2 = PHI <1(4), 0(2), -1(3)>
2139 : _1 = iftmp.0_2 == 0;
2140 :
2141 : and for partial ordering <=> something like:
2142 :
2143 : <bb 2> : // cond3_bb
2144 : if (a_3(D) == b_5(D))
2145 : goto <bb 6>; [50.00%]
2146 : else
2147 : goto <bb 3>; [50.00%]
2148 :
2149 : <bb 3> [local count: 536870913]: // cond2_bb
2150 : if (a_3(D) < b_5(D))
2151 : goto <bb 6>; [50.00%]
2152 : else
2153 : goto <bb 4>; [50.00%]
2154 :
2155 : <bb 4> [local count: 268435456]: // cond_bb
2156 : if (a_3(D) > b_5(D))
2157 : goto <bb 6>; [50.00%]
2158 : else
2159 : goto <bb 5>; [50.00%]
2160 :
2161 : <bb 5> [local count: 134217728]: // middle_bb
2162 :
2163 : <bb 6> [local count: 1073741824]: // phi_bb
2164 : # SR.27_4 = PHI <0(2), -1(3), 1(4), -128(5)>
2165 : _2 = SR.27_4 > 0; */
2166 :
2167 : static bool
2168 658158 : spaceship_replacement (basic_block cond_bb, basic_block middle_bb,
2169 : edge e0, edge e1, gphi *phi,
2170 : tree arg0, tree arg1)
2171 : {
2172 658158 : tree phires = gimple_phi_result (phi);
2173 1309018 : if (!INTEGRAL_TYPE_P (TREE_TYPE (phires))
2174 523040 : || TYPE_UNSIGNED (TREE_TYPE (phires))
2175 262747 : || !tree_fits_shwi_p (arg0)
2176 71586 : || !tree_fits_shwi_p (arg1)
2177 41453 : || (!IN_RANGE (tree_to_shwi (arg0), -1, 1)
2178 18843 : && tree_to_shwi (arg0) != -128)
2179 681239 : || (!IN_RANGE (tree_to_shwi (arg1), -1, 1)
2180 2750 : && tree_to_shwi (arg1) != -128))
2181 : return false;
2182 :
2183 20389 : basic_block phi_bb = gimple_bb (phi);
2184 20389 : gcc_assert (phi_bb == e0->dest && phi_bb == e1->dest);
2185 20389 : if (!IN_RANGE (EDGE_COUNT (phi_bb->preds), 3, 4))
2186 : return false;
2187 :
2188 7687 : use_operand_p use_p;
2189 7687 : gimple *use_stmt;
2190 7687 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (phires))
2191 : return false;
2192 7682 : if (!single_imm_use (phires, &use_p, &use_stmt))
2193 : return false;
2194 7032 : enum tree_code cmp;
2195 7032 : tree lhs, rhs;
2196 7032 : gimple *orig_use_stmt = use_stmt;
2197 7032 : tree orig_use_lhs = NULL_TREE;
2198 7032 : tree temps[2] = { NULL_TREE, NULL_TREE };
2199 :
2200 : /* Handle std::partial_ordering::_M_reverse(), i.e.
2201 : _1 = (unsigned char) phires;
2202 : _2 = -_1;
2203 : _3 = (signed char) _2;
2204 : and uses of _3 in comparison instead of phires. */
2205 7032 : if (gimple_assign_cast_p (use_stmt))
2206 : {
2207 252 : orig_use_lhs = gimple_assign_lhs (use_stmt);
2208 252 : temps[0] = orig_use_lhs;
2209 252 : tree ty1 = TREE_TYPE (gimple_assign_rhs1 (use_stmt));
2210 252 : tree ty2 = TREE_TYPE (orig_use_lhs);
2211 :
2212 252 : if (!TYPE_UNSIGNED (ty2) || !INTEGRAL_TYPE_P (ty2))
2213 : return false;
2214 213 : if (TYPE_PRECISION (ty2) != 8 || TYPE_PRECISION (ty1) < 8)
2215 : return false;
2216 94 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
2217 : return false;
2218 94 : if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
2219 : return false;
2220 :
2221 93 : if (!is_gimple_assign (use_stmt)
2222 93 : || gimple_assign_rhs_code (use_stmt) != NEGATE_EXPR)
2223 : return false;
2224 :
2225 78 : orig_use_lhs = gimple_assign_lhs (use_stmt);
2226 78 : temps[1] = orig_use_lhs;
2227 78 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
2228 : return false;
2229 78 : if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
2230 : return false;
2231 :
2232 78 : if (!gimple_assign_cast_p (use_stmt))
2233 : return false;
2234 :
2235 78 : orig_use_lhs = gimple_assign_lhs (use_stmt);
2236 78 : tree ty3 = TREE_TYPE (orig_use_lhs);
2237 :
2238 78 : if (!useless_type_conversion_p (ty3, ty1))
2239 : return false;
2240 78 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
2241 : return false;
2242 78 : if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
2243 : return false;
2244 : }
2245 6858 : if (gimple_code (use_stmt) == GIMPLE_COND)
2246 : {
2247 2478 : cmp = gimple_cond_code (use_stmt);
2248 2478 : lhs = gimple_cond_lhs (use_stmt);
2249 2478 : rhs = gimple_cond_rhs (use_stmt);
2250 : }
2251 4380 : else if (is_gimple_assign (use_stmt))
2252 : {
2253 2512 : if (gimple_assign_rhs_class (use_stmt) == GIMPLE_BINARY_RHS)
2254 : {
2255 1338 : cmp = gimple_assign_rhs_code (use_stmt);
2256 1338 : lhs = gimple_assign_rhs1 (use_stmt);
2257 1338 : rhs = gimple_assign_rhs2 (use_stmt);
2258 : }
2259 1174 : else if (gimple_assign_rhs_code (use_stmt) == COND_EXPR)
2260 : {
2261 0 : tree cond = gimple_assign_rhs1 (use_stmt);
2262 0 : if (!COMPARISON_CLASS_P (cond))
2263 : return false;
2264 0 : cmp = TREE_CODE (cond);
2265 0 : lhs = TREE_OPERAND (cond, 0);
2266 0 : rhs = TREE_OPERAND (cond, 1);
2267 : }
2268 : else
2269 : return false;
2270 : }
2271 : else
2272 : return false;
2273 3816 : switch (cmp)
2274 : {
2275 3328 : case EQ_EXPR:
2276 3328 : case NE_EXPR:
2277 3328 : case LT_EXPR:
2278 3328 : case GT_EXPR:
2279 3328 : case LE_EXPR:
2280 3328 : case GE_EXPR:
2281 3328 : break;
2282 : default:
2283 : return false;
2284 : }
2285 6578 : if (lhs != (orig_use_lhs ? orig_use_lhs : phires)
2286 2965 : || !tree_fits_shwi_p (rhs)
2287 2703 : || !IN_RANGE (tree_to_shwi (rhs), -1, 1))
2288 : return false;
2289 :
2290 2691 : if (!empty_block_p (middle_bb))
2291 : return false;
2292 :
2293 5382 : gcond *cond1 = as_a <gcond *> (*gsi_last_bb (cond_bb));
2294 2691 : enum tree_code cmp1 = gimple_cond_code (cond1);
2295 2691 : switch (cmp1)
2296 : {
2297 2555 : case LT_EXPR:
2298 2555 : case LE_EXPR:
2299 2555 : case GT_EXPR:
2300 2555 : case GE_EXPR:
2301 2555 : break;
2302 : default:
2303 : return false;
2304 : }
2305 2555 : tree lhs1 = gimple_cond_lhs (cond1);
2306 2555 : tree rhs1 = gimple_cond_rhs (cond1);
2307 2555 : if (TREE_CODE (lhs1) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs1))
2308 : return false;
2309 2555 : if (TREE_CODE (rhs1) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1))
2310 : return false;
2311 :
2312 2555 : if (!single_pred_p (cond_bb) || !cond_only_block_p (cond_bb))
2313 : return false;
2314 :
2315 2531 : basic_block cond2_bb = single_pred (cond_bb);
2316 2531 : if (EDGE_COUNT (cond2_bb->succs) != 2)
2317 : return false;
2318 2531 : edge cond2_phi_edge;
2319 2531 : if (EDGE_SUCC (cond2_bb, 0)->dest == cond_bb)
2320 : {
2321 2078 : if (EDGE_SUCC (cond2_bb, 1)->dest != phi_bb)
2322 : return false;
2323 : cond2_phi_edge = EDGE_SUCC (cond2_bb, 1);
2324 : }
2325 453 : else if (EDGE_SUCC (cond2_bb, 0)->dest != phi_bb)
2326 : return false;
2327 : else
2328 : cond2_phi_edge = EDGE_SUCC (cond2_bb, 0);
2329 2531 : tree arg2 = gimple_phi_arg_def (phi, cond2_phi_edge->dest_idx);
2330 2531 : if (!tree_fits_shwi_p (arg2))
2331 : return false;
2332 5062 : gcond *cond2 = safe_dyn_cast <gcond *> (*gsi_last_bb (cond2_bb));
2333 2531 : if (!cond2)
2334 : return false;
2335 2531 : enum tree_code cmp2 = gimple_cond_code (cond2);
2336 2531 : tree lhs2 = gimple_cond_lhs (cond2);
2337 2531 : tree rhs2 = gimple_cond_rhs (cond2);
2338 2531 : if (lhs2 == lhs1)
2339 : {
2340 2529 : if (!operand_equal_p (rhs2, rhs1, 0))
2341 : {
2342 336 : if ((cmp2 == EQ_EXPR || cmp2 == NE_EXPR)
2343 336 : && TREE_CODE (rhs1) == INTEGER_CST
2344 336 : && TREE_CODE (rhs2) == INTEGER_CST)
2345 : {
2346 : /* For integers, we can have cond2 x == 5
2347 : and cond1 x < 5, x <= 4, x <= 5, x < 6,
2348 : x > 5, x >= 6, x >= 5 or x > 4. */
2349 336 : if (tree_int_cst_lt (rhs1, rhs2))
2350 : {
2351 336 : if (wi::ne_p (wi::to_wide (rhs1) + 1, wi::to_wide (rhs2)))
2352 : return false;
2353 336 : if (cmp1 == LE_EXPR)
2354 : cmp1 = LT_EXPR;
2355 0 : else if (cmp1 == GT_EXPR)
2356 : cmp1 = GE_EXPR;
2357 : else
2358 : return false;
2359 : }
2360 : else
2361 : {
2362 0 : gcc_checking_assert (tree_int_cst_lt (rhs2, rhs1));
2363 0 : if (wi::ne_p (wi::to_wide (rhs2) + 1, wi::to_wide (rhs1)))
2364 : return false;
2365 0 : if (cmp1 == LT_EXPR)
2366 : cmp1 = LE_EXPR;
2367 0 : else if (cmp1 == GE_EXPR)
2368 : cmp1 = GT_EXPR;
2369 : else
2370 : return false;
2371 : }
2372 : rhs1 = rhs2;
2373 : }
2374 : else
2375 : return false;
2376 : }
2377 : }
2378 2 : else if (lhs2 == rhs1)
2379 : {
2380 0 : if (rhs2 != lhs1)
2381 : return false;
2382 : }
2383 : else
2384 : return false;
2385 :
2386 2529 : tree arg3 = arg2;
2387 2529 : basic_block cond3_bb = cond2_bb;
2388 2529 : edge cond3_phi_edge = cond2_phi_edge;
2389 2529 : gcond *cond3 = cond2;
2390 2529 : enum tree_code cmp3 = cmp2;
2391 2529 : tree lhs3 = lhs2;
2392 2529 : tree rhs3 = rhs2;
2393 2529 : if (EDGE_COUNT (phi_bb->preds) == 4)
2394 : {
2395 424 : if (absu_hwi (tree_to_shwi (arg2)) != 1)
2396 : return false;
2397 416 : if ((cond2_phi_edge->flags & EDGE_FALSE_VALUE)
2398 416 : && HONOR_NANS (TREE_TYPE (lhs1)))
2399 : return false;
2400 320 : if (e1->flags & EDGE_TRUE_VALUE)
2401 : {
2402 318 : if (tree_to_shwi (arg0) != -128
2403 318 : || absu_hwi (tree_to_shwi (arg1)) != 1
2404 636 : || wi::to_widest (arg1) == wi::to_widest (arg2))
2405 : return false;
2406 : }
2407 2 : else if (tree_to_shwi (arg1) != -128
2408 2 : || absu_hwi (tree_to_shwi (arg0)) != 1
2409 4 : || wi::to_widest (arg0) == wi::to_widest (arg2))
2410 : return false;
2411 320 : switch (cmp2)
2412 : {
2413 320 : case LT_EXPR:
2414 320 : case LE_EXPR:
2415 320 : case GT_EXPR:
2416 320 : case GE_EXPR:
2417 320 : break;
2418 : default:
2419 : return false;
2420 : }
2421 : /* if (x < y) goto phi_bb; else fallthru;
2422 : if (x > y) goto phi_bb; else fallthru;
2423 : bbx:;
2424 : phi_bb:;
2425 : is ok, but if x and y are swapped in one of the comparisons,
2426 : or the comparisons are the same and operands not swapped,
2427 : or the true and false edges are swapped, it is not.
2428 : For HONOR_NANS, the edge flags are irrelevant and the comparisons
2429 : must be different for non-swapped operands and same for swapped
2430 : operands. */
2431 320 : if ((lhs2 == lhs1)
2432 320 : ^ ((cmp2 == LT_EXPR || cmp2 == LE_EXPR)
2433 320 : != (cmp1 == LT_EXPR || cmp1 == LE_EXPR))
2434 320 : ^ ((cond2_phi_edge->flags & EDGE_FALSE_VALUE) != 0))
2435 : return false;
2436 318 : if (!single_pred_p (cond2_bb) || !cond_only_block_p (cond2_bb))
2437 : return false;
2438 318 : cond3_bb = single_pred (cond2_bb);
2439 318 : if (EDGE_COUNT (cond2_bb->succs) != 2)
2440 : return false;
2441 318 : if (EDGE_SUCC (cond3_bb, 0)->dest == cond2_bb)
2442 : {
2443 150 : if (EDGE_SUCC (cond3_bb, 1)->dest != phi_bb)
2444 : return false;
2445 : cond3_phi_edge = EDGE_SUCC (cond3_bb, 1);
2446 : }
2447 168 : else if (EDGE_SUCC (cond3_bb, 0)->dest != phi_bb)
2448 : return false;
2449 : else
2450 : cond3_phi_edge = EDGE_SUCC (cond3_bb, 0);
2451 318 : arg3 = gimple_phi_arg_def (phi, cond3_phi_edge->dest_idx);
2452 636 : cond3 = safe_dyn_cast <gcond *> (*gsi_last_bb (cond3_bb));
2453 318 : if (!cond3)
2454 : return false;
2455 318 : cmp3 = gimple_cond_code (cond3);
2456 318 : lhs3 = gimple_cond_lhs (cond3);
2457 318 : rhs3 = gimple_cond_rhs (cond3);
2458 318 : if (lhs3 == lhs1)
2459 : {
2460 318 : if (!operand_equal_p (rhs3, rhs1, 0))
2461 : return false;
2462 : }
2463 0 : else if (lhs3 == rhs1)
2464 : {
2465 0 : if (rhs3 != lhs1)
2466 : return false;
2467 : }
2468 : else
2469 : return false;
2470 : }
2471 2105 : else if (absu_hwi (tree_to_shwi (arg0)) != 1
2472 2084 : || absu_hwi (tree_to_shwi (arg1)) != 1
2473 4189 : || wi::to_widest (arg0) == wi::to_widest (arg1)
2474 4189 : || HONOR_NANS (TREE_TYPE (lhs1)))
2475 : return false;
2476 :
2477 2402 : if (!integer_zerop (arg3) || (cmp3 != EQ_EXPR && cmp3 != NE_EXPR))
2478 : return false;
2479 2402 : if ((cond3_phi_edge->flags & (cmp3 == EQ_EXPR
2480 2402 : ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE)) == 0)
2481 : return false;
2482 :
2483 : /* lhs1 one_cmp rhs1 results in phires of 1. */
2484 2402 : enum tree_code one_cmp;
2485 4804 : if ((cmp1 == LT_EXPR || cmp1 == LE_EXPR)
2486 2546 : ^ (!integer_onep ((e1->flags & EDGE_TRUE_VALUE) ? arg1 : arg0)))
2487 : one_cmp = LT_EXPR;
2488 : else
2489 1778 : one_cmp = GT_EXPR;
2490 :
2491 2402 : enum tree_code res_cmp;
2492 2402 : bool negate_p = false;
2493 2402 : switch (cmp)
2494 : {
2495 1317 : case EQ_EXPR:
2496 1317 : if (integer_zerop (rhs) && !HONOR_NANS (TREE_TYPE (lhs1)))
2497 : res_cmp = EQ_EXPR;
2498 1233 : else if (integer_minus_onep (rhs))
2499 771 : res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
2500 462 : else if (integer_onep (rhs))
2501 : res_cmp = one_cmp;
2502 : else
2503 : return false;
2504 : break;
2505 998 : case NE_EXPR:
2506 998 : if (integer_zerop (rhs) && !HONOR_NANS (TREE_TYPE (lhs1)))
2507 : res_cmp = NE_EXPR;
2508 960 : else if (integer_minus_onep (rhs))
2509 484 : res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
2510 476 : else if (integer_onep (rhs))
2511 686 : res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
2512 : else
2513 : return false;
2514 968 : if (HONOR_NANS (TREE_TYPE (lhs1)))
2515 : negate_p = true;
2516 : break;
2517 27 : case LT_EXPR:
2518 27 : if (integer_onep (rhs))
2519 0 : res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
2520 27 : else if (integer_zerop (rhs))
2521 27 : res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
2522 : else
2523 : return false;
2524 27 : if (HONOR_NANS (TREE_TYPE (lhs1)))
2525 : negate_p = true;
2526 : break;
2527 4 : case LE_EXPR:
2528 4 : if (integer_zerop (rhs))
2529 4 : res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
2530 0 : else if (integer_minus_onep (rhs))
2531 0 : res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
2532 : else
2533 : return false;
2534 4 : if (HONOR_NANS (TREE_TYPE (lhs1)))
2535 : negate_p = true;
2536 : break;
2537 0 : case GT_EXPR:
2538 0 : if (integer_minus_onep (rhs))
2539 0 : res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
2540 0 : else if (integer_zerop (rhs))
2541 : res_cmp = one_cmp;
2542 : else
2543 : return false;
2544 : break;
2545 56 : case GE_EXPR:
2546 56 : if (integer_zerop (rhs))
2547 56 : res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
2548 0 : else if (integer_onep (rhs))
2549 : res_cmp = one_cmp;
2550 : else
2551 : return false;
2552 : break;
2553 : default:
2554 : gcc_unreachable ();
2555 : }
2556 2330 : if (orig_use_lhs)
2557 60 : res_cmp = swap_tree_comparison (res_cmp);
2558 :
2559 2330 : tree clhs1 = lhs1, crhs1 = rhs1;
2560 2330 : if (negate_p)
2561 : {
2562 72 : if (cfun->can_throw_non_call_exceptions)
2563 0 : return false;
2564 72 : res_cmp = invert_tree_comparison (res_cmp, false);
2565 72 : clhs1 = make_ssa_name (boolean_type_node);
2566 72 : gimple *g = gimple_build_assign (clhs1, res_cmp, lhs1, rhs1);
2567 72 : gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
2568 72 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2569 72 : crhs1 = boolean_false_node;
2570 72 : res_cmp = EQ_EXPR;
2571 : }
2572 :
2573 2330 : if (gimple_code (use_stmt) == GIMPLE_COND)
2574 : {
2575 1673 : gcond *use_cond = as_a <gcond *> (use_stmt);
2576 1673 : gimple_cond_set_code (use_cond, res_cmp);
2577 1673 : gimple_cond_set_lhs (use_cond, clhs1);
2578 1673 : gimple_cond_set_rhs (use_cond, crhs1);
2579 : }
2580 657 : else if (gimple_assign_rhs_class (use_stmt) == GIMPLE_BINARY_RHS)
2581 : {
2582 657 : gimple_assign_set_rhs_code (use_stmt, res_cmp);
2583 657 : gimple_assign_set_rhs1 (use_stmt, clhs1);
2584 657 : gimple_assign_set_rhs2 (use_stmt, crhs1);
2585 : }
2586 : else
2587 : {
2588 0 : tree cond = build2 (res_cmp, TREE_TYPE (gimple_assign_rhs1 (use_stmt)),
2589 : clhs1, crhs1);
2590 0 : gimple_assign_set_rhs1 (use_stmt, cond);
2591 : }
2592 2330 : update_stmt (use_stmt);
2593 :
2594 2330 : if (MAY_HAVE_DEBUG_BIND_STMTS)
2595 : {
2596 1947 : use_operand_p use_p;
2597 1947 : imm_use_iterator iter;
2598 1947 : bool has_debug_uses = false;
2599 1947 : bool has_cast1_debug_uses = false;
2600 1947 : bool has_neg_debug_uses = false;
2601 1947 : bool has_cast2_debug_uses = false;
2602 1969 : FOR_EACH_IMM_USE_FAST (use_p, iter, phires)
2603 : {
2604 1969 : gimple *use_stmt = USE_STMT (use_p);
2605 1969 : if (is_gimple_debug (use_stmt))
2606 : {
2607 : has_debug_uses = true;
2608 : break;
2609 : }
2610 1947 : }
2611 1947 : if (orig_use_lhs)
2612 : {
2613 44 : FOR_EACH_IMM_USE_FAST (use_p, iter, temps[0])
2614 : {
2615 38 : gimple *use_stmt = USE_STMT (use_p);
2616 38 : if (is_gimple_debug (use_stmt))
2617 : {
2618 : has_debug_uses = true;
2619 : has_cast1_debug_uses = true;
2620 : break;
2621 : }
2622 22 : }
2623 44 : FOR_EACH_IMM_USE_FAST (use_p, iter, temps[1])
2624 : {
2625 38 : gimple *use_stmt = USE_STMT (use_p);
2626 38 : if (is_gimple_debug (use_stmt))
2627 : {
2628 : has_debug_uses = true;
2629 : has_cast1_debug_uses = true;
2630 : has_neg_debug_uses = true;
2631 : break;
2632 : }
2633 22 : }
2634 22 : FOR_EACH_IMM_USE_FAST (use_p, iter, orig_use_lhs)
2635 : {
2636 16 : gimple *use_stmt = USE_STMT (use_p);
2637 16 : if (is_gimple_debug (use_stmt))
2638 : {
2639 : has_debug_uses = true;
2640 : has_cast1_debug_uses = true;
2641 : has_neg_debug_uses = true;
2642 : has_cast2_debug_uses = true;
2643 : break;
2644 : }
2645 22 : }
2646 22 : if (has_debug_uses)
2647 : {
2648 22 : gimple_stmt_iterator gsi = gsi_for_stmt (orig_use_stmt);
2649 22 : tree zero = build_zero_cst (TREE_TYPE (temps[0]));
2650 22 : gimple_assign_set_rhs_with_ops (&gsi, INTEGER_CST, zero);
2651 22 : update_stmt (orig_use_stmt);
2652 22 : gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (temps[1]));
2653 22 : zero = build_zero_cst (TREE_TYPE (temps[1]));
2654 22 : gimple_assign_set_rhs_with_ops (&gsi, INTEGER_CST, zero);
2655 22 : update_stmt (SSA_NAME_DEF_STMT (temps[1]));
2656 22 : gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (orig_use_lhs));
2657 22 : zero = build_zero_cst (TREE_TYPE (orig_use_lhs));
2658 22 : gimple_assign_set_rhs_with_ops (&gsi, INTEGER_CST, zero);
2659 22 : update_stmt (SSA_NAME_DEF_STMT (orig_use_lhs));
2660 : }
2661 : }
2662 :
2663 1947 : if (has_debug_uses)
2664 : {
2665 : /* If there are debug uses, emit something like:
2666 : # DEBUG D#1 => i_2(D) > j_3(D) ? 1 : -1
2667 : # DEBUG D#2 => i_2(D) == j_3(D) ? 0 : D#1
2668 : where > stands for the comparison that yielded 1
2669 : and replace debug uses of phi result with that D#2.
2670 : Ignore the value of -128 if !HONOR_NANS, because if NaNs
2671 : aren't expected, all floating point numbers should be
2672 : comparable. If HONOR_NANS, emit something like:
2673 : # DEBUG D#1 => i_2(D) < j_3(D) ? -1 : -128
2674 : # DEBUG D#2 => i_2(D) > j_3(D) ? 1 : D#1
2675 : # DEBUG D#3 => i_2(D) == j_3(D) ? 0 : D#2
2676 : instead. */
2677 1947 : gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi));
2678 1947 : tree type = TREE_TYPE (phires);
2679 1947 : tree minus_one = build_int_cst (type, -1);
2680 1947 : if (HONOR_NANS (TREE_TYPE (lhs1)))
2681 : {
2682 102 : tree temp3 = build_debug_expr_decl (type);
2683 204 : tree t = build2 (one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR,
2684 : boolean_type_node, lhs1, rhs2);
2685 102 : t = build3 (COND_EXPR, type, t, minus_one,
2686 : build_int_cst (type, -128));
2687 102 : gimple *g = gimple_build_debug_bind (temp3, t, phi);
2688 102 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2689 102 : minus_one = temp3;
2690 : }
2691 1947 : tree temp1 = build_debug_expr_decl (type);
2692 1947 : tree t = build2 (one_cmp, boolean_type_node, lhs1, rhs2);
2693 1947 : t = build3 (COND_EXPR, type, t, build_one_cst (type),
2694 : minus_one);
2695 1947 : gimple *g = gimple_build_debug_bind (temp1, t, phi);
2696 1947 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2697 1947 : tree temp2 = build_debug_expr_decl (type);
2698 1947 : t = build2 (EQ_EXPR, boolean_type_node, lhs1, rhs2);
2699 1947 : t = build3 (COND_EXPR, type, t, build_zero_cst (type), temp1);
2700 1947 : g = gimple_build_debug_bind (temp2, t, phi);
2701 1947 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2702 1947 : replace_uses_by (phires, temp2);
2703 1947 : if (has_cast1_debug_uses)
2704 : {
2705 16 : tree temp3 = build_debug_expr_decl (TREE_TYPE (temps[0]));
2706 16 : t = fold_convert (TREE_TYPE (temps[0]), temp2);
2707 16 : g = gimple_build_debug_bind (temp3, t, phi);
2708 16 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2709 16 : replace_uses_by (temps[0], temp3);
2710 16 : temp2 = temp3;
2711 : }
2712 1947 : if (has_neg_debug_uses)
2713 : {
2714 16 : tree temp3 = build_debug_expr_decl (TREE_TYPE (temps[1]));
2715 16 : t = fold_build1 (NEGATE_EXPR, TREE_TYPE (temps[1]), temp2);
2716 16 : g = gimple_build_debug_bind (temp3, t, phi);
2717 16 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2718 16 : replace_uses_by (temps[1], temp3);
2719 16 : temp2 = temp3;
2720 : }
2721 1947 : if (has_cast2_debug_uses)
2722 : {
2723 16 : tree temp3 = build_debug_expr_decl (TREE_TYPE (orig_use_lhs));
2724 16 : t = fold_convert (TREE_TYPE (orig_use_lhs), temp2);
2725 16 : g = gimple_build_debug_bind (temp3, t, phi);
2726 16 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2727 16 : replace_uses_by (orig_use_lhs, temp3);
2728 : }
2729 : }
2730 : }
2731 :
2732 2330 : if (orig_use_lhs)
2733 : {
2734 60 : gimple_stmt_iterator gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (orig_use_lhs));
2735 60 : gsi_remove (&gsi, true);
2736 60 : gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (temps[1]));
2737 60 : gsi_remove (&gsi, true);
2738 60 : gsi = gsi_for_stmt (orig_use_stmt);
2739 60 : gsi_remove (&gsi, true);
2740 60 : release_ssa_name (orig_use_lhs);
2741 60 : release_ssa_name (temps[1]);
2742 60 : release_ssa_name (temps[0]);
2743 : }
2744 :
2745 2330 : gimple_stmt_iterator psi = gsi_for_stmt (phi);
2746 2330 : remove_phi_node (&psi, true);
2747 2330 : statistics_counter_event (cfun, "spaceship replacement", 1);
2748 :
2749 2330 : return true;
2750 : }
2751 :
2752 : /* Optimize x ? __builtin_fun (x) : C, where C is __builtin_fun (0).
2753 : Convert
2754 :
2755 : <bb 2>
2756 : if (b_4(D) != 0)
2757 : goto <bb 3>
2758 : else
2759 : goto <bb 4>
2760 :
2761 : <bb 3>
2762 : _2 = (unsigned long) b_4(D);
2763 : _9 = __builtin_popcountl (_2);
2764 : OR
2765 : _9 = __builtin_popcountl (b_4(D));
2766 :
2767 : <bb 4>
2768 : c_12 = PHI <0(2), _9(3)>
2769 :
2770 : Into
2771 : <bb 2>
2772 : _2 = (unsigned long) b_4(D);
2773 : _9 = __builtin_popcountl (_2);
2774 : OR
2775 : _9 = __builtin_popcountl (b_4(D));
2776 :
2777 : <bb 4>
2778 : c_12 = PHI <_9(2)>
2779 :
2780 : Similarly for __builtin_clz or __builtin_ctz if
2781 : C?Z_DEFINED_VALUE_AT_ZERO is 2, optab is present and
2782 : instead of 0 above it uses the value from that macro. */
2783 :
2784 : static bool
2785 457637 : cond_removal_in_builtin_zero_pattern (basic_block cond_bb,
2786 : basic_block middle_bb,
2787 : edge e1, edge e2, gphi *phi,
2788 : tree arg0, tree arg1)
2789 : {
2790 457637 : gimple_stmt_iterator gsi, gsi_from;
2791 457637 : gimple *call;
2792 457637 : gimple *cast = NULL;
2793 457637 : tree lhs, arg;
2794 :
2795 : /* Check that
2796 : _2 = (unsigned long) b_4(D);
2797 : _9 = __builtin_popcountl (_2);
2798 : OR
2799 : _9 = __builtin_popcountl (b_4(D));
2800 : are the only stmts in the middle_bb. */
2801 :
2802 457637 : gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
2803 457637 : if (gsi_end_p (gsi))
2804 : return false;
2805 292961 : cast = gsi_stmt (gsi);
2806 292961 : gsi_next_nondebug (&gsi);
2807 292961 : if (!gsi_end_p (gsi))
2808 : {
2809 141604 : call = gsi_stmt (gsi);
2810 141604 : gsi_next_nondebug (&gsi);
2811 141604 : if (!gsi_end_p (gsi))
2812 : return false;
2813 : }
2814 : else
2815 : {
2816 : call = cast;
2817 : cast = NULL;
2818 : }
2819 :
2820 : /* Check that we have a popcount/clz/ctz builtin. */
2821 200350 : if (!is_gimple_call (call))
2822 : return false;
2823 :
2824 6032 : lhs = gimple_get_lhs (call);
2825 :
2826 6032 : if (lhs == NULL_TREE)
2827 : return false;
2828 :
2829 6006 : combined_fn cfn = gimple_call_combined_fn (call);
2830 6006 : if (gimple_call_num_args (call) != 1
2831 6006 : && (gimple_call_num_args (call) != 2
2832 : || cfn == CFN_CLZ
2833 578 : || cfn == CFN_CTZ))
2834 : return false;
2835 :
2836 4492 : arg = gimple_call_arg (call, 0);
2837 :
2838 4492 : internal_fn ifn = IFN_LAST;
2839 4492 : int val = 0;
2840 4492 : bool any_val = false;
2841 4492 : switch (cfn)
2842 : {
2843 : CASE_CFN_BSWAP:
2844 : CASE_CFN_BITREVERSE:
2845 : CASE_CFN_FFS:
2846 : CASE_CFN_PARITY:
2847 : CASE_CFN_POPCOUNT:
2848 : break;
2849 787 : CASE_CFN_CLZ:
2850 787 : if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
2851 : {
2852 787 : tree type = TREE_TYPE (arg);
2853 787 : if (BITINT_TYPE_P (type))
2854 : {
2855 4 : if (gimple_call_num_args (call) == 1)
2856 : {
2857 : any_val = true;
2858 : ifn = IFN_CLZ;
2859 : break;
2860 : }
2861 0 : if (!tree_fits_shwi_p (gimple_call_arg (call, 1)))
2862 : return false;
2863 0 : HOST_WIDE_INT at_zero = tree_to_shwi (gimple_call_arg (call, 1));
2864 0 : if ((int) at_zero != at_zero)
2865 : return false;
2866 0 : ifn = IFN_CLZ;
2867 0 : val = at_zero;
2868 0 : break;
2869 : }
2870 783 : if (direct_internal_fn_supported_p (IFN_CLZ, type, OPTIMIZE_FOR_BOTH)
2871 1541 : && CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type),
2872 : val) == 2)
2873 : {
2874 : ifn = IFN_CLZ;
2875 : break;
2876 : }
2877 : }
2878 : return false;
2879 298 : CASE_CFN_CTZ:
2880 298 : if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
2881 : {
2882 298 : tree type = TREE_TYPE (arg);
2883 298 : if (BITINT_TYPE_P (type))
2884 : {
2885 4 : if (gimple_call_num_args (call) == 1)
2886 : {
2887 : any_val = true;
2888 : ifn = IFN_CTZ;
2889 : break;
2890 : }
2891 0 : if (!tree_fits_shwi_p (gimple_call_arg (call, 1)))
2892 : return false;
2893 0 : HOST_WIDE_INT at_zero = tree_to_shwi (gimple_call_arg (call, 1));
2894 0 : if ((int) at_zero != at_zero)
2895 : return false;
2896 0 : ifn = IFN_CTZ;
2897 0 : val = at_zero;
2898 0 : break;
2899 : }
2900 294 : if (direct_internal_fn_supported_p (IFN_CTZ, type, OPTIMIZE_FOR_BOTH)
2901 567 : && CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type),
2902 : val) == 2)
2903 : {
2904 : ifn = IFN_CTZ;
2905 : break;
2906 : }
2907 : }
2908 : return false;
2909 3 : case CFN_BUILT_IN_CLRSB:
2910 3 : val = TYPE_PRECISION (integer_type_node) - 1;
2911 3 : break;
2912 3 : case CFN_BUILT_IN_CLRSBL:
2913 3 : val = TYPE_PRECISION (long_integer_type_node) - 1;
2914 3 : break;
2915 3 : case CFN_BUILT_IN_CLRSBLL:
2916 3 : val = TYPE_PRECISION (long_long_integer_type_node) - 1;
2917 3 : break;
2918 : default:
2919 : return false;
2920 : }
2921 :
2922 146 : if (cast)
2923 : {
2924 : /* We have a cast stmt feeding popcount/clz/ctz builtin. */
2925 : /* Check that we have a cast prior to that. */
2926 55 : if (gimple_code (cast) != GIMPLE_ASSIGN
2927 55 : || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (cast)))
2928 : return false;
2929 : /* Result of the cast stmt is the argument to the builtin. */
2930 25 : if (arg != gimple_assign_lhs (cast))
2931 : return false;
2932 25 : arg = gimple_assign_rhs1 (cast);
2933 : }
2934 :
2935 232 : gcond *cond = dyn_cast <gcond *> (*gsi_last_bb (cond_bb));
2936 :
2937 : /* Cond_bb has a check for b_4 [!=|==] 0 before calling the popcount/clz/ctz
2938 : builtin. */
2939 116 : if (!cond
2940 116 : || (gimple_cond_code (cond) != NE_EXPR
2941 23 : && gimple_cond_code (cond) != EQ_EXPR)
2942 116 : || !integer_zerop (gimple_cond_rhs (cond))
2943 113 : || arg != gimple_cond_lhs (cond))
2944 : return false;
2945 :
2946 35 : edge true_edge, false_edge;
2947 : /* We need to know which is the true edge and which is the false
2948 : edge so that we know when to invert the condition below. */
2949 35 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
2950 :
2951 : /* Forward the edges over the middle basic block. */
2952 35 : if (true_edge->dest == middle_bb)
2953 35 : true_edge = EDGE_SUCC (true_edge->dest, 0);
2954 35 : if (false_edge->dest == middle_bb)
2955 0 : false_edge = EDGE_SUCC (false_edge->dest, 0);
2956 :
2957 : /* Canonicalize the args with respect to the edges,
2958 : arg0 is from the true edge and arg1 is from the
2959 : false edge.
2960 : That is `cond ? arg0 : arg1`.*/
2961 35 : if (true_edge == e1)
2962 35 : gcc_assert (false_edge == e2);
2963 : else
2964 : {
2965 0 : gcc_assert (false_edge == e1);
2966 0 : gcc_assert (true_edge == e2);
2967 : std::swap (arg0, arg1);
2968 : }
2969 :
2970 : /* Canonicalize the args such that we get:
2971 : `arg != 0 ? arg0 : arg1`. So swap arg0/arg1
2972 : around if cond was an equals. */
2973 35 : if (gimple_cond_code (cond) == EQ_EXPR)
2974 2 : std::swap (arg0, arg1);
2975 :
2976 : /* Check PHI arguments. */
2977 35 : if (lhs != arg0
2978 33 : || TREE_CODE (arg1) != INTEGER_CST)
2979 : return false;
2980 25 : if (any_val)
2981 : {
2982 0 : if (!tree_fits_shwi_p (arg1))
2983 : return false;
2984 0 : HOST_WIDE_INT at_zero = tree_to_shwi (arg1);
2985 0 : if ((int) at_zero != at_zero)
2986 : return false;
2987 0 : val = at_zero;
2988 : }
2989 25 : else if (wi::to_wide (arg1) != val)
2990 : return false;
2991 :
2992 : /* And insert the popcount/clz/ctz builtin and cast stmt before the
2993 : cond_bb. */
2994 13 : gsi = gsi_last_bb (cond_bb);
2995 13 : if (cast)
2996 : {
2997 13 : gsi_from = gsi_for_stmt (cast);
2998 13 : gsi_move_before (&gsi_from, &gsi);
2999 13 : reset_flow_sensitive_info (gimple_get_lhs (cast));
3000 : }
3001 13 : gsi_from = gsi_for_stmt (call);
3002 13 : if (ifn == IFN_LAST
3003 13 : || (gimple_call_internal_p (call) && gimple_call_num_args (call) == 2))
3004 8 : gsi_move_before (&gsi_from, &gsi);
3005 : else
3006 : {
3007 : /* For __builtin_c[lt]z* force .C[LT]Z ifn, because only
3008 : the latter is well defined at zero. */
3009 5 : call = gimple_build_call_internal (ifn, 2, gimple_call_arg (call, 0),
3010 5 : build_int_cst (integer_type_node, val));
3011 5 : gimple_call_set_lhs (call, lhs);
3012 5 : gsi_insert_before (&gsi, call, GSI_SAME_STMT);
3013 5 : gsi_remove (&gsi_from, true);
3014 : }
3015 13 : reset_flow_sensitive_info (lhs);
3016 :
3017 : /* Now update the PHI and remove unneeded bbs. */
3018 13 : replace_phi_edge_with_variable (cond_bb, e2, phi, lhs);
3019 13 : return true;
3020 : }
3021 :
3022 : /* Auxiliary functions to determine the set of memory accesses which
3023 : can't trap because they are preceded by accesses to the same memory
3024 : portion. We do that for MEM_REFs, so we only need to track
3025 : the SSA_NAME of the pointer indirectly referenced. The algorithm
3026 : simply is a walk over all instructions in dominator order. When
3027 : we see an MEM_REF we determine if we've already seen a same
3028 : ref anywhere up to the root of the dominator tree. If we do the
3029 : current access can't trap. If we don't see any dominating access
3030 : the current access might trap, but might also make later accesses
3031 : non-trapping, so we remember it. We need to be careful with loads
3032 : or stores, for instance a load might not trap, while a store would,
3033 : so if we see a dominating read access this doesn't mean that a later
3034 : write access would not trap. Hence we also need to differentiate the
3035 : type of access(es) seen.
3036 :
3037 : ??? We currently are very conservative and assume that a load might
3038 : trap even if a store doesn't (write-only memory). This probably is
3039 : overly conservative.
3040 :
3041 : We currently support a special case that for !TREE_ADDRESSABLE automatic
3042 : variables, it could ignore whether something is a load or store because the
3043 : local stack should be always writable. */
3044 :
3045 : /* A hash-table of references (MEM_REF/ARRAY_REF/COMPONENT_REF), and in which
3046 : basic block an *_REF through it was seen, which would constitute a
3047 : no-trap region for same accesses.
3048 :
3049 : Size is needed to support 2 MEM_REFs of different types, like
3050 : MEM<double>(s_1) and MEM<long>(s_1), which would compare equal with
3051 : OEP_ADDRESS_OF. */
3052 : struct ref_to_bb
3053 : {
3054 : tree exp;
3055 : HOST_WIDE_INT size;
3056 : unsigned int phase;
3057 : basic_block bb;
3058 : };
3059 :
3060 : /* Hashtable helpers. */
3061 :
3062 : struct refs_hasher : free_ptr_hash<ref_to_bb>
3063 : {
3064 : static inline hashval_t hash (const ref_to_bb *);
3065 : static inline bool equal (const ref_to_bb *, const ref_to_bb *);
3066 : };
3067 :
3068 : /* Used for quick clearing of the hash-table when we see calls.
3069 : Hash entries with phase < nt_call_phase are invalid. */
3070 : static unsigned int nt_call_phase;
3071 :
3072 : /* The hash function. */
3073 :
3074 : inline hashval_t
3075 19965918 : refs_hasher::hash (const ref_to_bb *n)
3076 : {
3077 19965918 : inchash::hash hstate;
3078 19965918 : inchash::add_expr (n->exp, hstate, OEP_ADDRESS_OF);
3079 19965918 : hstate.add_hwi (n->size);
3080 19965918 : return hstate.end ();
3081 : }
3082 :
3083 : /* The equality function of *P1 and *P2. */
3084 :
3085 : inline bool
3086 14557183 : refs_hasher::equal (const ref_to_bb *n1, const ref_to_bb *n2)
3087 : {
3088 14557183 : return operand_equal_p (n1->exp, n2->exp, OEP_ADDRESS_OF)
3089 14557183 : && n1->size == n2->size;
3090 : }
3091 :
3092 : class nontrapping_dom_walker : public dom_walker
3093 : {
3094 : public:
3095 1060283 : nontrapping_dom_walker (cdi_direction direction, hash_set<tree> *ps)
3096 1060283 : : dom_walker (direction), m_nontrapping (ps), m_seen_refs (128)
3097 1060283 : {}
3098 :
3099 : edge before_dom_children (basic_block) final override;
3100 : void after_dom_children (basic_block) final override;
3101 :
3102 : private:
3103 :
3104 : /* We see the expression EXP in basic block BB. If it's an interesting
3105 : expression (an MEM_REF through an SSA_NAME) possibly insert the
3106 : expression into the set NONTRAP or the hash table of seen expressions.
3107 : STORE is true if this expression is on the LHS, otherwise it's on
3108 : the RHS. */
3109 : void add_or_mark_expr (basic_block, tree, bool);
3110 :
3111 : hash_set<tree> *m_nontrapping;
3112 :
3113 : /* The hash table for remembering what we've seen. */
3114 : hash_table<refs_hasher> m_seen_refs;
3115 : };
3116 :
3117 : /* Called by walk_dominator_tree, when entering the block BB. */
3118 : edge
3119 11908514 : nontrapping_dom_walker::before_dom_children (basic_block bb)
3120 : {
3121 11908514 : edge e;
3122 11908514 : edge_iterator ei;
3123 11908514 : gimple_stmt_iterator gsi;
3124 :
3125 : /* If we haven't seen all our predecessors, clear the hash-table. */
3126 26182243 : FOR_EACH_EDGE (e, ei, bb->preds)
3127 14968576 : if ((((size_t)e->src->aux) & 2) == 0)
3128 : {
3129 694847 : nt_call_phase++;
3130 694847 : break;
3131 : }
3132 :
3133 : /* Mark this BB as being on the path to dominator root and as visited. */
3134 11908514 : bb->aux = (void*)(1 | 2);
3135 :
3136 : /* And walk the statements in order. */
3137 108321731 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3138 : {
3139 84504703 : gimple *stmt = gsi_stmt (gsi);
3140 :
3141 84504703 : if ((gimple_code (stmt) == GIMPLE_ASM && gimple_vdef (stmt))
3142 84540401 : || (is_gimple_call (stmt)
3143 5700046 : && (!nonfreeing_call_p (stmt) || !nonbarrier_call_p (stmt))))
3144 5097858 : nt_call_phase++;
3145 94806418 : else if (gimple_assign_single_p (stmt) && !gimple_has_volatile_ops (stmt))
3146 : {
3147 13447030 : add_or_mark_expr (bb, gimple_assign_lhs (stmt), true);
3148 13447030 : add_or_mark_expr (bb, gimple_assign_rhs1 (stmt), false);
3149 : }
3150 : }
3151 11908514 : return NULL;
3152 : }
3153 :
3154 : /* Called by walk_dominator_tree, when basic block BB is exited. */
3155 : void
3156 11908514 : nontrapping_dom_walker::after_dom_children (basic_block bb)
3157 : {
3158 : /* This BB isn't on the path to dominator root anymore. */
3159 11908514 : bb->aux = (void*)2;
3160 11908514 : }
3161 :
3162 : /* We see the expression EXP in basic block BB. If it's an interesting
3163 : expression of:
3164 : 1) MEM_REF
3165 : 2) ARRAY_REF
3166 : 3) COMPONENT_REF
3167 : possibly insert the expression into the set NONTRAP or the hash table
3168 : of seen expressions. STORE is true if this expression is on the LHS,
3169 : otherwise it's on the RHS. */
3170 : void
3171 26894060 : nontrapping_dom_walker::add_or_mark_expr (basic_block bb, tree exp, bool store)
3172 : {
3173 26894060 : HOST_WIDE_INT size;
3174 :
3175 26894060 : if ((TREE_CODE (exp) == MEM_REF || TREE_CODE (exp) == ARRAY_REF
3176 22520153 : || TREE_CODE (exp) == COMPONENT_REF)
3177 34143285 : && (size = int_size_in_bytes (TREE_TYPE (exp))) > 0)
3178 : {
3179 11623127 : struct ref_to_bb map;
3180 11623127 : ref_to_bb **slot;
3181 11623127 : struct ref_to_bb *r2bb;
3182 11623127 : basic_block found_bb = 0;
3183 :
3184 11623127 : if (!store)
3185 : {
3186 5349755 : tree base = get_base_address (exp);
3187 : /* Only record a LOAD of a local variable without address-taken, as
3188 : the local stack is always writable. This allows cselim on a STORE
3189 : with a dominating LOAD. */
3190 5349755 : if (!auto_var_p (base) || TREE_ADDRESSABLE (base))
3191 4373296 : return;
3192 : }
3193 :
3194 : /* Try to find the last seen *_REF, which can trap. */
3195 7249831 : map.exp = exp;
3196 7249831 : map.size = size;
3197 7249831 : slot = m_seen_refs.find_slot (&map, INSERT);
3198 7249831 : r2bb = *slot;
3199 7249831 : if (r2bb && r2bb->phase >= nt_call_phase)
3200 296488 : found_bb = r2bb->bb;
3201 :
3202 : /* If we've found a trapping *_REF, _and_ it dominates EXP
3203 : (it's in a basic block on the path from us to the dominator root)
3204 : then we can't trap. */
3205 296488 : if (found_bb && (((size_t)found_bb->aux) & 1) == 1)
3206 : {
3207 81200 : m_nontrapping->add (exp);
3208 : }
3209 : else
3210 : {
3211 : /* EXP might trap, so insert it into the hash table. */
3212 7168631 : if (r2bb)
3213 : {
3214 994881 : r2bb->phase = nt_call_phase;
3215 994881 : r2bb->bb = bb;
3216 : }
3217 : else
3218 : {
3219 6173750 : r2bb = XNEW (struct ref_to_bb);
3220 6173750 : r2bb->phase = nt_call_phase;
3221 6173750 : r2bb->bb = bb;
3222 6173750 : r2bb->exp = exp;
3223 6173750 : r2bb->size = size;
3224 6173750 : *slot = r2bb;
3225 : }
3226 : }
3227 : }
3228 : }
3229 :
3230 : /* This is the entry point of gathering non trapping memory accesses.
3231 : It will do a dominator walk over the whole function, and it will
3232 : make use of the bb->aux pointers. It returns a set of trees
3233 : (the MEM_REFs itself) which can't trap. */
3234 : static hash_set<tree> *
3235 1060283 : get_non_trapping (void)
3236 : {
3237 1060283 : nt_call_phase = 0;
3238 1060283 : hash_set<tree> *nontrap = new hash_set<tree>;
3239 :
3240 2120566 : nontrapping_dom_walker (CDI_DOMINATORS, nontrap)
3241 1060283 : .walk (cfun->cfg->x_entry_block_ptr);
3242 :
3243 1060283 : clear_aux_for_blocks ();
3244 1060283 : return nontrap;
3245 : }
3246 :
3247 : /* Do the main work of conditional store replacement. We already know
3248 : that the recognized pattern looks like so:
3249 :
3250 : split:
3251 : if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
3252 : MIDDLE_BB:
3253 : something
3254 : fallthrough (edge E0)
3255 : JOIN_BB:
3256 : some more
3257 :
3258 : ASSIGN is a store in MIDDLE_BB which is the candidate for cselim. We check
3259 : that MIDDLE_BB contains only one store (i.e., ASSIGN), that that store
3260 : doesn't trap (not via NOTRAP, but via checking if an access to the same
3261 : memory location dominates us, or the store is to a local addressable object)
3262 : and that the store has a "simple" RHS. */
3263 :
3264 : static bool
3265 441230 : cond_store_replacement (basic_block middle_bb, basic_block join_bb, edge e0,
3266 : edge e1, gimple *assign, hash_set<tree> *nontrap)
3267 : {
3268 441230 : tree lhs, rhs, name, name2;
3269 441230 : gphi *newphi;
3270 441230 : gassign *new_stmt;
3271 441230 : gimple_stmt_iterator gsi;
3272 441230 : location_t locus;
3273 :
3274 : /* Check if middle_bb contains of only one store. */
3275 441230 : if (!assign
3276 192076 : || !gimple_assign_single_p (assign)
3277 474088 : || gimple_has_volatile_ops (assign))
3278 : return false;
3279 :
3280 32657 : locus = gimple_location (assign);
3281 32657 : lhs = gimple_assign_lhs (assign);
3282 32657 : rhs = gimple_assign_rhs1 (assign);
3283 32657 : if ((!REFERENCE_CLASS_P (lhs)
3284 32657 : && !DECL_P (lhs))
3285 32657 : || !is_gimple_reg_type (TREE_TYPE (lhs)))
3286 : return false;
3287 :
3288 : /* Make sure all uses (except the rhs) in the single stmt are also available
3289 : where we insert to. */
3290 32171 : ssa_op_iter iter;
3291 32171 : tree use;
3292 61987 : FOR_EACH_SSA_TREE_OPERAND (use, assign, iter, SSA_OP_USE)
3293 : {
3294 34256 : if (use == rhs)
3295 13333 : continue;
3296 :
3297 20923 : gimple *stmt = SSA_NAME_DEF_STMT (use);
3298 20923 : if (stmt && gimple_bb (stmt) == middle_bb)
3299 : return false;
3300 : }
3301 :
3302 : /* Prove that we can move the store down. We could also check
3303 : TREE_THIS_NOTRAP here, but in that case we also could move stores,
3304 : whose value is not available readily, which we want to avoid. */
3305 27731 : if (nontrap->contains (lhs))
3306 : {
3307 : /* For local non-addressable variables, a load in the same bb
3308 : (though before) will cause the lhs to be in the nontrap hashset.
3309 : So need to check if there are no other loads in the middle bb.
3310 : FIXME: this is over conserative, this check could be made to
3311 : allow loads unrelated to lhs. */
3312 5805 : tree vuse = gimple_vuse (assign);
3313 5805 : imm_use_iterator iter;
3314 5805 : gimple *use_stmt;
3315 19590 : FOR_EACH_IMM_USE_STMT (use_stmt, iter, vuse)
3316 : {
3317 13989 : if (use_stmt == assign)
3318 5804 : continue;
3319 8185 : if (gimple_bb (use_stmt) == middle_bb)
3320 204 : return false;
3321 5805 : }
3322 : }
3323 : else
3324 : {
3325 : /* If LHS is an access to a local variable without address-taken
3326 : (or when we allow data races) and known not to trap, we could
3327 : always safely move down the store. */
3328 21926 : tree base;
3329 21926 : if (ref_can_have_store_data_races (lhs)
3330 1013 : || tree_could_trap_p (lhs)
3331 : /* tree_could_trap_p is a predicate for rvalues, so check
3332 : for readonly memory explicitly. */
3333 22108 : || ((base = get_base_address (lhs))
3334 182 : && ((DECL_P (base)
3335 176 : && TREE_READONLY (base))
3336 177 : || TREE_CODE (base) == STRING_CST)))
3337 : return false;
3338 : }
3339 :
3340 : /* Now we've checked the constraints, so do the transformation:
3341 : 1) Remove the single store. */
3342 5772 : gsi = gsi_for_stmt (assign);
3343 5772 : unlink_stmt_vdef (assign);
3344 5772 : gsi_remove (&gsi, true);
3345 5772 : release_defs (assign);
3346 :
3347 : /* Make both store and load use alias-set zero as we have to
3348 : deal with the case of the store being a conditional change
3349 : of the dynamic type. */
3350 5772 : lhs = unshare_expr (lhs);
3351 5772 : tree *basep = &lhs;
3352 11590 : while (handled_component_p (*basep))
3353 5818 : basep = &TREE_OPERAND (*basep, 0);
3354 5772 : if (TREE_CODE (*basep) == MEM_REF
3355 5772 : || TREE_CODE (*basep) == TARGET_MEM_REF)
3356 619 : TREE_OPERAND (*basep, 1)
3357 1238 : = fold_convert (ptr_type_node, TREE_OPERAND (*basep, 1));
3358 : else
3359 5153 : *basep = build2 (MEM_REF, TREE_TYPE (*basep),
3360 : build_fold_addr_expr (*basep),
3361 : build_zero_cst (ptr_type_node));
3362 :
3363 : /* 2) Insert a load from the memory of the store to the temporary
3364 : on the edge which did not contain the store. */
3365 5772 : gphi *vphi = get_virtual_phi (join_bb);
3366 5772 : name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3367 5772 : new_stmt = gimple_build_assign (name, lhs);
3368 5772 : gimple_set_location (new_stmt, locus);
3369 : /* Set the vuse for the new load. */
3370 5772 : gimple_set_vuse (new_stmt, gimple_phi_arg_def (vphi, e1->dest_idx));
3371 5772 : lhs = unshare_expr (lhs);
3372 5772 : {
3373 : /* Set the no-warning bit on the rhs of the load to avoid uninit
3374 : warnings. */
3375 5772 : tree rhs1 = gimple_assign_rhs1 (new_stmt);
3376 5772 : suppress_warning (rhs1, OPT_Wuninitialized);
3377 : }
3378 5772 : gsi_insert_on_edge (e1, new_stmt);
3379 :
3380 : /* 3) Create a PHI node at the join block, with one argument
3381 : holding the old RHS, and the other holding the temporary
3382 : where we stored the old memory contents. */
3383 5772 : name2 = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3384 5772 : newphi = create_phi_node (name2, join_bb);
3385 5772 : add_phi_arg (newphi, rhs, e0, locus);
3386 5772 : add_phi_arg (newphi, name, e1, locus);
3387 :
3388 5772 : new_stmt = gimple_build_assign (lhs, gimple_phi_result (newphi));
3389 :
3390 : /* Update the vdef for the new store statement. */
3391 5772 : tree newvphilhs = make_ssa_name (gimple_vop (cfun));
3392 5772 : tree vdef = gimple_phi_result (vphi);
3393 5772 : gimple_set_vuse (new_stmt, newvphilhs);
3394 5772 : gimple_set_vdef (new_stmt, vdef);
3395 5772 : gimple_phi_set_result (vphi, newvphilhs);
3396 5772 : SSA_NAME_DEF_STMT (vdef) = new_stmt;
3397 5772 : update_stmt (vphi);
3398 :
3399 : /* 4) Insert that PHI node. */
3400 5772 : gsi = gsi_after_labels (join_bb);
3401 5772 : gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
3402 :
3403 5772 : if (dump_file && (dump_flags & TDF_DETAILS))
3404 : {
3405 1 : fprintf (dump_file, "\nConditional store replacement happened!");
3406 1 : fprintf (dump_file, "\nReplaced the store with a load.");
3407 1 : fprintf (dump_file, "\nInserted a new PHI statement in joint block:\n");
3408 1 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_VOPS|TDF_MEMSYMS);
3409 : }
3410 5772 : statistics_counter_event (cfun, "conditional store replacement", 1);
3411 :
3412 5772 : return true;
3413 : }
3414 :
3415 : /* Do the main work of conditional store replacement. */
3416 :
3417 : static bool
3418 855158 : cond_if_else_store_replacement_1 (basic_block then_bb, basic_block else_bb,
3419 : basic_block join_bb, gimple *then_assign,
3420 : gimple *else_assign,
3421 : gphi *vphi)
3422 : {
3423 855158 : tree lhs_base, lhs, then_rhs, else_rhs, name;
3424 855158 : location_t then_locus, else_locus;
3425 855158 : gimple_stmt_iterator gsi;
3426 855158 : gphi *newphi = nullptr;
3427 855158 : gassign *new_stmt;
3428 :
3429 855158 : if (then_assign == NULL
3430 855158 : || !gimple_assign_single_p (then_assign)
3431 771737 : || else_assign == NULL
3432 771737 : || !gimple_assign_single_p (else_assign)
3433 100450 : || stmt_references_abnormal_ssa_name (then_assign)
3434 955594 : || stmt_references_abnormal_ssa_name (else_assign))
3435 : return false;
3436 :
3437 : /* Allow both being clobbers but no other volatile operations. */
3438 100436 : if (gimple_clobber_p (then_assign)
3439 100436 : && gimple_clobber_p (else_assign))
3440 : ;
3441 182803 : else if (gimple_has_volatile_ops (then_assign)
3442 182803 : || gimple_has_volatile_ops (else_assign))
3443 : return false;
3444 :
3445 82916 : lhs = gimple_assign_lhs (then_assign);
3446 82916 : if (!operand_equal_p (lhs, gimple_assign_lhs (else_assign), 0))
3447 : return false;
3448 :
3449 32609 : lhs_base = get_base_address (lhs);
3450 32609 : if (lhs_base == NULL_TREE
3451 32609 : || (!DECL_P (lhs_base) && TREE_CODE (lhs_base) != MEM_REF))
3452 : return false;
3453 :
3454 32531 : then_rhs = gimple_assign_rhs1 (then_assign);
3455 32531 : else_rhs = gimple_assign_rhs1 (else_assign);
3456 32531 : then_locus = gimple_location (then_assign);
3457 32531 : else_locus = gimple_location (else_assign);
3458 :
3459 32531 : if (!is_gimple_reg_type (TREE_TYPE (lhs)))
3460 : {
3461 : /* Handle clobbers separately as operand_equal_p does not check
3462 : the kind of the clobbers being the same. */
3463 6687 : if (TREE_CLOBBER_P (then_rhs) && TREE_CLOBBER_P (else_rhs))
3464 : {
3465 3083 : if (CLOBBER_KIND (then_rhs) != CLOBBER_KIND (else_rhs))
3466 : return false;
3467 : }
3468 3604 : else if (!operand_equal_p (then_rhs, else_rhs))
3469 : return false;
3470 : /* Currently only handle commoning of `= {}`. */
3471 3585 : if (TREE_CODE (then_rhs) != CONSTRUCTOR)
3472 : return false;
3473 : }
3474 :
3475 29045 : if (dump_file && (dump_flags & TDF_DETAILS))
3476 : {
3477 8 : if (TREE_CLOBBER_P (then_rhs))
3478 3 : fprintf(dump_file, "factoring out clobber:\n\tthen:\n");
3479 : else
3480 5 : fprintf(dump_file, "factoring out stores:\n\tthen:\n");
3481 8 : print_gimple_stmt (dump_file, then_assign, 0,
3482 : TDF_VOPS|TDF_MEMSYMS);
3483 8 : fprintf(dump_file, "\telse:\n");
3484 8 : print_gimple_stmt (dump_file, else_assign, 0,
3485 : TDF_VOPS|TDF_MEMSYMS);
3486 8 : fprintf (dump_file, "\n");
3487 : }
3488 :
3489 : /* Now we've checked the constraints, so do the transformation:
3490 : 1) Remove the stores. */
3491 29045 : gsi = gsi_for_stmt (then_assign);
3492 29045 : unlink_stmt_vdef (then_assign);
3493 29045 : gsi_remove (&gsi, true);
3494 29045 : release_defs (then_assign);
3495 :
3496 29045 : gsi = gsi_for_stmt (else_assign);
3497 29045 : unlink_stmt_vdef (else_assign);
3498 29045 : gsi_remove (&gsi, true);
3499 29045 : release_defs (else_assign);
3500 :
3501 : /* 2) Create a PHI node at the join block, with one argument
3502 : holding the old RHS, and the other holding the temporary
3503 : where we stored the old memory contents. */
3504 29045 : if (operand_equal_p (then_rhs, else_rhs))
3505 : name = then_rhs;
3506 : else
3507 : {
3508 23630 : name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3509 23630 : newphi = create_phi_node (name, join_bb);
3510 23630 : add_phi_arg (newphi, then_rhs, EDGE_SUCC (then_bb, 0), then_locus);
3511 23630 : add_phi_arg (newphi, else_rhs, EDGE_SUCC (else_bb, 0), else_locus);
3512 : }
3513 :
3514 29045 : new_stmt = gimple_build_assign (lhs, name);
3515 : /* Update the vdef for the new store statement. */
3516 29045 : tree newvphilhs = make_ssa_name (gimple_vop (cfun));
3517 29045 : tree vdef = gimple_phi_result (vphi);
3518 29045 : gimple_set_vuse (new_stmt, newvphilhs);
3519 29045 : gimple_set_vdef (new_stmt, vdef);
3520 29045 : gimple_phi_set_result (vphi, newvphilhs);
3521 29045 : SSA_NAME_DEF_STMT (vdef) = new_stmt;
3522 29045 : update_stmt (vphi);
3523 29045 : if (dump_file && (dump_flags & TDF_DETAILS))
3524 : {
3525 8 : if (newphi)
3526 : {
3527 4 : fprintf(dump_file, "to use phi:\n");
3528 4 : print_gimple_stmt (dump_file, newphi, 0,
3529 : TDF_VOPS|TDF_MEMSYMS);
3530 4 : fprintf(dump_file, "\n");
3531 : }
3532 : else
3533 4 : fprintf(dump_file, "to:\n");
3534 8 : print_gimple_stmt (dump_file, new_stmt, 0,
3535 : TDF_VOPS|TDF_MEMSYMS);
3536 8 : fprintf(dump_file, "\n\n");
3537 : }
3538 :
3539 : /* 3) Insert that new store. */
3540 29045 : gsi = gsi_after_labels (join_bb);
3541 29045 : gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
3542 :
3543 29045 : statistics_counter_event (cfun, "if-then-else store replacement", 1);
3544 :
3545 29045 : return true;
3546 : }
3547 :
3548 : /* Return the last store in BB with VDEF or NULL if there are
3549 : loads following the store. VPHI is where the only use of the
3550 : vdef should be. If ONLYONESTORE is true, then the store is
3551 : the only store in the BB. */
3552 :
3553 : static gimple *
3554 3410220 : trailing_store_in_bb (basic_block bb, tree vdef, gphi *vphi, bool onlyonestore)
3555 : {
3556 3410220 : if (SSA_NAME_IS_DEFAULT_DEF (vdef))
3557 : return NULL;
3558 3384757 : gimple *store = SSA_NAME_DEF_STMT (vdef);
3559 3384757 : if (gimple_bb (store) != bb
3560 3384757 : || gimple_code (store) == GIMPLE_PHI)
3561 : return NULL;
3562 :
3563 : /* Verify there is no other store in this BB if requested. */
3564 3336769 : if (onlyonestore
3565 1595800 : && !SSA_NAME_IS_DEFAULT_DEF (gimple_vuse (store))
3566 1200864 : && gimple_bb (SSA_NAME_DEF_STMT (gimple_vuse (store))) == bb
3567 3757962 : && gimple_code (SSA_NAME_DEF_STMT (gimple_vuse (store))) != GIMPLE_PHI)
3568 : return NULL;
3569 :
3570 :
3571 : /* Verify there is no load or store after the store, the vdef of the store
3572 : should only be used by the vphi joining the 2 bbs. */
3573 2915587 : use_operand_p use_p;
3574 2915587 : gimple *use_stmt;
3575 5831174 : if (!single_imm_use (gimple_vdef (store), &use_p, &use_stmt))
3576 : return NULL;
3577 2870263 : if (use_stmt != vphi)
3578 0 : return NULL;
3579 :
3580 : return store;
3581 : }
3582 :
3583 : /* Takes a MEM and changes the aliasing set to be zero on it.
3584 : This handles all variants include decls. */
3585 : static tree
3586 698 : copy_mem_with_alias_set_zero (tree mem)
3587 : {
3588 698 : mem = unshare_expr (mem);
3589 698 : tree *basep = &mem;
3590 1480 : while (handled_component_p (*basep))
3591 782 : basep = &TREE_OPERAND (*basep, 0);
3592 698 : if (TREE_CODE (*basep) == MEM_REF
3593 698 : || TREE_CODE (*basep) == TARGET_MEM_REF)
3594 146 : TREE_OPERAND (*basep, 1)
3595 292 : = fold_convert (ptr_type_node, TREE_OPERAND (*basep, 1));
3596 : else
3597 552 : *basep = build2 (MEM_REF, TREE_TYPE (*basep),
3598 : build_fold_addr_expr (*basep),
3599 : build_zero_cst (ptr_type_node));
3600 698 : return mem;
3601 : }
3602 :
3603 : /* Do the main work of a limited conditional store replacement.
3604 : This recognized pattern like so:
3605 :
3606 : COND_BB:
3607 : store = a_1;
3608 : // no loads
3609 : if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
3610 : MIDDLE_BB:
3611 : something // no loads
3612 : store = a_2;
3613 : something // no loads
3614 : fallthrough (edge E0)
3615 : JOIN_BB:
3616 : some more
3617 :
3618 : This is a limited form of the full cond_store_replacement
3619 : to be allowed from use from phiopt and can be done
3620 : without calculating the non-trapping cases. */
3621 : static bool
3622 1477793 : cond_store_replacement_limited (basic_block middle_bb, basic_block join_bb,
3623 : basic_block cond_bb,
3624 : edge e0, edge e1,
3625 : bool caninsert_edge)
3626 : {
3627 1477793 : tree lhs, rhs;
3628 1477793 : location_t locus;
3629 : /* Currently don't handle more than 2 incoming edges
3630 : into the merge bb. */
3631 1477793 : if (EDGE_COUNT (join_bb->preds) > 2)
3632 : return false;
3633 : /* The middle bb needs to have a single predecessor of the cond_bb. */
3634 1477793 : if (!single_pred_p (middle_bb))
3635 : return false;
3636 1477793 : gphi *vphi = get_virtual_phi (join_bb);
3637 1477793 : if (!vphi)
3638 : return false;
3639 1306921 : tree middle_vdef = gimple_phi_arg_def_from_edge (vphi, e0);
3640 : /* Check if middle_bb contains of only one store. */
3641 1306921 : gimple *store_middle;
3642 1306921 : store_middle = trailing_store_in_bb (middle_bb, middle_vdef,
3643 : vphi, true);
3644 :
3645 1306921 : if (!store_middle
3646 950934 : || !gimple_assign_single_p (store_middle)
3647 1454065 : || gimple_has_volatile_ops (store_middle))
3648 : return false;
3649 :
3650 146342 : locus = gimple_location (store_middle);
3651 146342 : lhs = gimple_assign_lhs (store_middle);
3652 146342 : rhs = gimple_assign_rhs1 (store_middle);
3653 146342 : if ((!REFERENCE_CLASS_P (lhs)
3654 146342 : && !DECL_P (lhs))
3655 146342 : || !is_gimple_reg_type (TREE_TYPE (lhs)))
3656 : return false;
3657 144056 : if (TREE_CODE (rhs) != SSA_NAME)
3658 : return false;
3659 :
3660 : /* Three cases that can be handled:
3661 : 1) the lhs is stored to right before the condition.
3662 : Will remove the store before the condition.
3663 : 2) Or the lhs is loaded from right before the condition.
3664 : 3) Neither of these. (this will insert a load in the other edge)
3665 : For case 2 and 3, check for data races.
3666 : For case 2, the load can either be based on a local variable
3667 : or a known non-trapping decl.
3668 : For case 3, the store needs to known to be non-trapping. */
3669 84421 : tree vuse = gimple_vuse (store_middle);
3670 84421 : gimple *beforestore = nullptr;
3671 84421 : gimple *vdef_before = SSA_NAME_DEF_STMT (vuse);
3672 84421 : tree other_rhs = nullptr;
3673 :
3674 : /* See if there is a store before the condition case. */
3675 84421 : if (gimple_assign_single_p (vdef_before))
3676 : {
3677 20805 : tree beforelhs = gimple_assign_lhs (vdef_before);
3678 : /* Only allow the store to be right before the condition. */
3679 20805 : if (gimple_bb (vdef_before) == cond_bb
3680 : /* This can't be a clobber */
3681 17848 : && !gimple_clobber_p (vdef_before)
3682 : /* An exact match is only supported.
3683 : FIXME: Allow for clique/base mismatch? */
3684 35657 : && operand_equal_p (lhs, beforelhs))
3685 : {
3686 : /* The vuse of the of store in the middle should be also
3687 : the entry in the phi for the other edge. */
3688 808 : gcc_assert (vuse == gimple_phi_arg_def_from_edge (vphi, e1));
3689 808 : tree vuse = gimple_vuse (store_middle);
3690 808 : imm_use_iterator iter;
3691 808 : gimple *use_stmt;
3692 808 : bool has_load = false;
3693 : /* If there is a load, then just reuse the value and not
3694 : remove the old store as that might be used by the load. */
3695 1950 : FOR_EACH_IMM_USE_STMT (use_stmt, iter, vuse)
3696 : {
3697 1609 : if (use_stmt != store_middle
3698 1609 : && use_stmt != vphi)
3699 : {
3700 : has_load = true;
3701 : break;
3702 : }
3703 808 : }
3704 808 : other_rhs = gimple_assign_rhs1 (vdef_before);
3705 : /* If there is no load, then keep the reference to the store stmt. */
3706 808 : if (!has_load)
3707 341 : beforestore = vdef_before;
3708 : }
3709 : }
3710 : /*
3711 : case 2:
3712 : a = local_var[n];
3713 : if (b)
3714 : local_var[n] = c;
3715 :
3716 : case 3:
3717 : if (b)
3718 : nontrapping = c;
3719 :
3720 : For case 3, nontrapping needs to satisfy tree_could_trap_p.
3721 : In both cases ref_can_have_store_data_races needs to be satisfy.
3722 : */
3723 :
3724 : /* Maybe the load/local non-escaped variable case. */
3725 808 : if (!other_rhs)
3726 : {
3727 83613 : tree lhsbase = get_base_address (lhs);
3728 : /* If this store ref can't have data races, a store
3729 : that was conditional can't become unconditional. */
3730 83613 : if (ref_can_have_store_data_races (lhs))
3731 82915 : return false;
3732 5468 : tree vuse = gimple_vuse (store_middle);
3733 5468 : imm_use_iterator iter;
3734 5468 : gimple *use_stmt;
3735 : /* Try to find the load before the store that matches
3736 : if we have a local variable or a non trapping store. */
3737 10403 : if ((auto_var_p (lhsbase) && !TREE_ADDRESSABLE (lhsbase))
3738 5504 : || !lhs_could_trap_p (lhs))
3739 : {
3740 25898 : FOR_EACH_IMM_USE_STMT (use_stmt, iter, vuse)
3741 : {
3742 21146 : if (gimple_bb (use_stmt) != cond_bb)
3743 14964 : continue;
3744 : /* Looking for a load only. */
3745 6182 : if (!gimple_assign_load_p (use_stmt))
3746 0 : continue;
3747 6182 : tree rhs = gimple_assign_rhs1 (use_stmt);
3748 6182 : if (!operand_equal_p (rhs, lhs))
3749 5973 : continue;
3750 209 : other_rhs = gimple_assign_lhs (use_stmt);
3751 209 : lhs = copy_mem_with_alias_set_zero (lhs);
3752 209 : break;
3753 4961 : }
3754 : }
3755 5468 : if (!other_rhs)
3756 : {
3757 5259 : gassign *new_stmt;
3758 : /* If not allowing inserting on the edge, then don't. */
3759 5259 : if (!caninsert_edge)
3760 : return false;
3761 : /* If LHS is an access to a local variable without address-taken
3762 : (or when we allow data races) and known not to trap, we could
3763 : always safely move down the store. */
3764 1587 : if (lhs_could_trap_p (lhs))
3765 : return false;
3766 489 : lhs = copy_mem_with_alias_set_zero (lhs);
3767 : /* Insert a load from the memory of the store to the temporary
3768 : on the edge which did not contain the store. */
3769 489 : other_rhs = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3770 489 : new_stmt = gimple_build_assign (other_rhs, lhs);
3771 489 : gimple_set_location (new_stmt, locus);
3772 : /* Set the vuse for the new load. */
3773 489 : gimple_set_vuse (new_stmt,
3774 489 : gimple_phi_arg_def (vphi, e1->dest_idx));
3775 489 : lhs = unshare_expr (lhs);
3776 489 : {
3777 : /* Set the no-warning bit on the rhs of the load to avoid
3778 : uninit warnings. */
3779 489 : tree rhs1 = gimple_assign_rhs1 (new_stmt);
3780 489 : suppress_warning (rhs1, OPT_Wuninitialized);
3781 : }
3782 489 : gsi_insert_on_edge (e1, new_stmt);
3783 : }
3784 : }
3785 :
3786 1506 : gphi *newphi;
3787 1506 : gassign *new_stmt;
3788 1506 : gimple_stmt_iterator gsi;
3789 : /* Now we've checked the constraints, so do the transformation:
3790 : 1) Remove the store(s). */
3791 1506 : gsi = gsi_for_stmt (store_middle);
3792 1506 : unlink_stmt_vdef (store_middle);
3793 1506 : gsi_remove (&gsi, true);
3794 1506 : release_defs (store_middle);
3795 :
3796 : /* Remove the store before the conditional if possible. */
3797 1506 : if (beforestore)
3798 : {
3799 341 : gsi = gsi_for_stmt (beforestore);
3800 341 : unlink_stmt_vdef (beforestore);
3801 341 : gsi_remove (&gsi, true);
3802 341 : release_defs (beforestore);
3803 : }
3804 :
3805 :
3806 : /* 2) Create a PHI node at the join block, with one argument
3807 : holding the old RHS, and the other holding the temporary
3808 : where we stored the old memory contents. */
3809 1506 : tree phiname = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3810 1506 : newphi = create_phi_node (phiname, join_bb);
3811 1506 : add_phi_arg (newphi, rhs, e0, locus);
3812 1506 : add_phi_arg (newphi, other_rhs, e1, locus);
3813 :
3814 : /* 3. Create the new store. */
3815 1506 : new_stmt = gimple_build_assign (lhs, phiname);
3816 :
3817 : /* Update the vdef for the new store statement. */
3818 1506 : tree newvphilhs = make_ssa_name (gimple_vop (cfun));
3819 1506 : tree vdef = gimple_phi_result (vphi);
3820 1506 : gimple_set_vuse (new_stmt, newvphilhs);
3821 1506 : gimple_set_vdef (new_stmt, vdef);
3822 1506 : gimple_phi_set_result (vphi, newvphilhs);
3823 1506 : SSA_NAME_DEF_STMT (vdef) = new_stmt;
3824 1506 : update_stmt (vphi);
3825 :
3826 1506 : gsi = gsi_after_labels (join_bb);
3827 1506 : gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
3828 :
3829 1506 : if (dump_file && (dump_flags & TDF_DETAILS))
3830 : {
3831 12 : fprintf (dump_file, "\nConditional store replacement happened!");
3832 12 : if (beforestore)
3833 4 : fprintf (dump_file, "\nRemoved the store before the condition.");
3834 12 : fprintf (dump_file, "\nInserted a new PHI statement in joint block:\n");
3835 12 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_VOPS|TDF_MEMSYMS);
3836 : }
3837 1506 : statistics_counter_event (cfun, "conditional store replacement", 1);
3838 1506 : return true;
3839 : }
3840 :
3841 :
3842 : /* Return the only store in MIDDLE_BB as the candidate store for cselim. Return
3843 : NULL if no candidate can be found. */
3844 :
3845 : static gimple *
3846 441230 : cselim_candidate (basic_block middle_bb, basic_block join_bb, edge e0)
3847 : {
3848 441230 : gphi *vphi = get_virtual_phi (join_bb);
3849 441230 : if (!vphi)
3850 : return NULL;
3851 :
3852 270358 : tree middle_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, e0);
3853 270358 : return trailing_store_in_bb (middle_bb, middle_vdef, vphi, true);
3854 : }
3855 :
3856 : /* Limited Conditional store replacement. We already know
3857 : that the recognized pattern looks like so:
3858 :
3859 : split:
3860 : if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
3861 : THEN_BB:
3862 : ...
3863 : STORE = Y;
3864 : ...
3865 : goto JOIN_BB;
3866 : ELSE_BB:
3867 : ...
3868 : STORE = Z;
3869 : ...
3870 : fallthrough (edge E0)
3871 : JOIN_BB:
3872 : some more
3873 :
3874 : Handles only the case with store in THEN_BB and ELSE_BB. That is
3875 : cheap enough due to in phiopt and not worry about heurstics. Moving the store
3876 : out might provide an opportunity for a phiopt to happen.
3877 : At -O1 (!flag_expensive_optimizations), this only handles the only store in
3878 : the BBs. */
3879 :
3880 : static bool
3881 959223 : cond_if_else_store_replacement_limited (basic_block then_bb, basic_block else_bb,
3882 : basic_block join_bb)
3883 : {
3884 959223 : gphi *vphi = get_virtual_phi (join_bb);
3885 959223 : if (!vphi)
3886 : return false;
3887 :
3888 959223 : tree then_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (then_bb));
3889 1918446 : gimple *then_assign = trailing_store_in_bb (then_bb, then_vdef, vphi,
3890 959223 : !flag_expensive_optimizations);
3891 959223 : if (!then_assign)
3892 : return false;
3893 :
3894 873718 : tree else_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (else_bb));
3895 1747436 : gimple *else_assign = trailing_store_in_bb (else_bb, else_vdef, vphi,
3896 873718 : !flag_expensive_optimizations);
3897 873718 : if (!else_assign)
3898 : return false;
3899 :
3900 853535 : return cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
3901 853535 : then_assign, else_assign, vphi);
3902 : }
3903 :
3904 : /* Conditional store replacement. We already know
3905 : that the recognized pattern looks like so:
3906 :
3907 : split:
3908 : if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
3909 : THEN_BB:
3910 : ...
3911 : X = Y;
3912 : ...
3913 : goto JOIN_BB;
3914 : ELSE_BB:
3915 : ...
3916 : X = Z;
3917 : ...
3918 : fallthrough (edge E0)
3919 : JOIN_BB:
3920 : some more
3921 :
3922 : We check that it is safe to sink the store to JOIN_BB by verifying that
3923 : there are no read-after-write or write-after-write dependencies in
3924 : THEN_BB and ELSE_BB. */
3925 :
3926 : static bool
3927 240899 : cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb,
3928 : basic_block join_bb)
3929 : {
3930 240899 : vec<data_reference_p> then_datarefs, else_datarefs;
3931 240899 : vec<ddr_p> then_ddrs, else_ddrs;
3932 240899 : gimple *then_store, *else_store;
3933 240899 : bool found, ok = false, res;
3934 240899 : tree then_lhs, else_lhs;
3935 240899 : basic_block blocks[3];
3936 240899 : gphi *vphi = get_virtual_phi (join_bb);
3937 240899 : if (!vphi)
3938 : return false;
3939 :
3940 : /* Handle the case with trailing stores in THEN_BB and ELSE_BB. That is
3941 : cheap enough to always handle as it allows us to elide dependence
3942 : checking. */
3943 239060 : while (cond_if_else_store_replacement_limited (then_bb, else_bb, join_bb))
3944 : ;
3945 :
3946 : /* If either vectorization or if-conversion is disabled then do
3947 : not sink any stores. */
3948 224859 : if (param_max_stores_to_sink == 0
3949 224858 : || (!flag_tree_loop_vectorize && !flag_tree_slp_vectorize)
3950 219195 : || !flag_tree_loop_if_convert)
3951 : return false;
3952 :
3953 : /* Find data references. */
3954 219192 : then_datarefs.create (1);
3955 219192 : else_datarefs.create (1);
3956 219192 : if ((find_data_references_in_bb (NULL, then_bb, &then_datarefs)
3957 219192 : == chrec_dont_know)
3958 193626 : || !then_datarefs.length ()
3959 187712 : || (find_data_references_in_bb (NULL, else_bb, &else_datarefs)
3960 187712 : == chrec_dont_know)
3961 234756 : || !else_datarefs.length ())
3962 : {
3963 204679 : free_data_refs (then_datarefs);
3964 204679 : free_data_refs (else_datarefs);
3965 204679 : return false;
3966 : }
3967 :
3968 : /* Clear visited on else stores, we want to make sure to pick each store
3969 : at most once to avoid quadratic behavior. */
3970 66639 : for (auto else_dr : else_datarefs)
3971 : {
3972 37613 : if (DR_IS_READ (else_dr))
3973 19471 : continue;
3974 18142 : gimple_set_visited (DR_STMT (else_dr), false);
3975 : }
3976 :
3977 : /* Find pairs of stores with equal LHS. Work from the end to avoid
3978 : re-ordering stores unnecessarily. */
3979 14513 : auto_vec<std::pair<gimple *, gimple *>, 1> stores_pairs;
3980 14513 : unsigned i;
3981 14513 : data_reference_p then_dr;
3982 61493 : FOR_EACH_VEC_ELT_REVERSE (then_datarefs, i, then_dr)
3983 : {
3984 32467 : if (DR_IS_READ (then_dr))
3985 32467 : continue;
3986 :
3987 19481 : then_store = DR_STMT (then_dr);
3988 19481 : then_lhs = gimple_get_lhs (then_store);
3989 19481 : if (then_lhs == NULL_TREE)
3990 0 : continue;
3991 19481 : found = false;
3992 :
3993 19481 : unsigned j;
3994 19481 : data_reference_p else_dr;
3995 92081 : FOR_EACH_VEC_ELT_REVERSE (else_datarefs, j, else_dr)
3996 : {
3997 56813 : if (DR_IS_READ (else_dr))
3998 20530 : continue;
3999 :
4000 36283 : else_store = DR_STMT (else_dr);
4001 36283 : if (gimple_visited_p (else_store))
4002 3316 : continue;
4003 32967 : else_lhs = gimple_get_lhs (else_store);
4004 32967 : if (else_lhs == NULL_TREE)
4005 0 : continue;
4006 :
4007 32967 : if (operand_equal_p (then_lhs, else_lhs, 0))
4008 : {
4009 : found = true;
4010 : break;
4011 : }
4012 : }
4013 :
4014 19481 : if (!found)
4015 15787 : continue;
4016 :
4017 3694 : gimple_set_visited (else_store, true);
4018 3694 : stores_pairs.safe_push (std::make_pair (then_store, else_store));
4019 : }
4020 :
4021 : /* No pairs of stores found. */
4022 14513 : if (!stores_pairs.length ()
4023 14513 : || stores_pairs.length () > (unsigned) param_max_stores_to_sink)
4024 : {
4025 12371 : free_data_refs (then_datarefs);
4026 12371 : free_data_refs (else_datarefs);
4027 12371 : return false;
4028 : }
4029 :
4030 : /* Compute and check data dependencies in both basic blocks. */
4031 2142 : then_ddrs.create (1);
4032 2142 : else_ddrs.create (1);
4033 2142 : if (!compute_all_dependences (then_datarefs, &then_ddrs,
4034 2142 : vNULL, false)
4035 4284 : || !compute_all_dependences (else_datarefs, &else_ddrs,
4036 2142 : vNULL, false))
4037 : {
4038 0 : free_dependence_relations (then_ddrs);
4039 0 : free_dependence_relations (else_ddrs);
4040 0 : free_data_refs (then_datarefs);
4041 0 : free_data_refs (else_datarefs);
4042 0 : return false;
4043 : }
4044 2142 : blocks[0] = then_bb;
4045 2142 : blocks[1] = else_bb;
4046 2142 : blocks[2] = join_bb;
4047 2142 : renumber_gimple_stmt_uids_in_blocks (blocks, 3);
4048 :
4049 : /* Check that there are no read-after-write or write-after-write dependencies
4050 : in THEN_BB. */
4051 13083 : for (auto ddr : then_ddrs)
4052 : {
4053 7396 : struct data_reference *dra = DDR_A (ddr);
4054 7396 : struct data_reference *drb = DDR_B (ddr);
4055 :
4056 7396 : if (DDR_ARE_DEPENDENT (ddr) != chrec_known
4057 7396 : && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
4058 827 : && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
4059 1566 : || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
4060 480 : && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
4061 1086 : || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
4062 : {
4063 739 : free_dependence_relations (then_ddrs);
4064 739 : free_dependence_relations (else_ddrs);
4065 739 : free_data_refs (then_datarefs);
4066 739 : free_data_refs (else_datarefs);
4067 739 : return false;
4068 : }
4069 : }
4070 :
4071 : /* Check that there are no read-after-write or write-after-write dependencies
4072 : in ELSE_BB. */
4073 8760 : for (auto ddr : else_ddrs)
4074 : {
4075 4719 : struct data_reference *dra = DDR_A (ddr);
4076 4719 : struct data_reference *drb = DDR_B (ddr);
4077 :
4078 4719 : if (DDR_ARE_DEPENDENT (ddr) != chrec_known
4079 4719 : && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
4080 401 : && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
4081 569 : || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
4082 140 : && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
4083 429 : || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
4084 : {
4085 168 : free_dependence_relations (then_ddrs);
4086 168 : free_dependence_relations (else_ddrs);
4087 168 : free_data_refs (then_datarefs);
4088 168 : free_data_refs (else_datarefs);
4089 168 : return false;
4090 : }
4091 : }
4092 :
4093 : /* Sink stores with same LHS. */
4094 5328 : for (auto &store_pair : stores_pairs)
4095 : {
4096 1623 : then_store = store_pair.first;
4097 1623 : else_store = store_pair.second;
4098 1623 : res = cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
4099 : then_store, else_store, vphi);
4100 1623 : ok = ok || res;
4101 : }
4102 :
4103 1235 : free_dependence_relations (then_ddrs);
4104 1235 : free_dependence_relations (else_ddrs);
4105 1235 : free_data_refs (then_datarefs);
4106 1235 : free_data_refs (else_datarefs);
4107 :
4108 1235 : return ok;
4109 14513 : }
4110 :
4111 : /* If PHI at MERGE is a "load PHI", PHI <*P, *Q> whose two arguments are
4112 : single-use, non-volatile scalar MEM_REF loads reading the same memory state
4113 : (same VUSE), factor the load out: introduce P' = PHI <P, Q> and a single
4114 : load *P' replacing the PHI. No speculative load is introduced (the load uses
4115 : whichever pointer the taken edge selected).
4116 : E0/E1 are the middle bbs to MERGE edges.
4117 : EARLY_P is set when the first phiopt is run.
4118 : BEFORE_VECT is true if this is before vectorization, where some extra checks
4119 : are needed for profitability.
4120 : Returns true if a load was factored out. */
4121 :
4122 : static bool
4123 1002332 : factor_out_conditional_load (edge e0, edge e1, basic_block merge, gphi *phi,
4124 : bool early_p, bool before_vect)
4125 : {
4126 : /* Factoring out a load during the first phi means we can't
4127 : trust if this is inside a loop or not; due to before inlining. */
4128 1002332 : if (early_p)
4129 : return false;
4130 :
4131 : /* Before vectorization, we don't want to factor out loads unless not inside a loop. */
4132 801939 : if (before_vect && bb_loop_depth (merge) != 0)
4133 : return false;
4134 :
4135 : /* Not a virtual operand. */
4136 834852 : if (virtual_operand_p (gimple_phi_result (phi))
4137 : /* can only handle the merge bb having 2 predecessors. */
4138 834852 : || gimple_phi_num_args (phi) != 2)
4139 : return false;
4140 :
4141 172254 : tree arg0 = gimple_phi_arg_def (phi, e0->dest_idx);
4142 172254 : tree arg1 = gimple_phi_arg_def (phi, e1->dest_idx);
4143 : /* The load needs to be only used in the phi. */
4144 154921 : if (TREE_CODE (arg0) != SSA_NAME || TREE_CODE (arg1) != SSA_NAME
4145 313611 : || !has_single_use (arg0) || !has_single_use (arg1))
4146 : return false;
4147 :
4148 : /* Re-derive the loads and pointers validated by the predicate above. */
4149 73734 : gimple *load0 = SSA_NAME_DEF_STMT (arg0);
4150 73734 : gimple *load1 = SSA_NAME_DEF_STMT (arg1);
4151 :
4152 : /* Load have to need to be in the middle bbs. */
4153 73734 : if (gimple_bb (load0) != e0->src
4154 73734 : || gimple_bb (load1) != e1->src)
4155 : return false;
4156 :
4157 : /* The load needs to be a load with NO volatile ops. */
4158 91270 : if (!gimple_assign_load_p (load0) || !gimple_assign_load_p (load1)
4159 103386 : || gimple_has_volatile_ops (load0) || gimple_has_volatile_ops (load1))
4160 : return false;
4161 :
4162 : /* Allow for stores/calls before the load. */
4163 16654 : if (gphi *vphi = get_virtual_phi (merge))
4164 : {
4165 24468 : if (gimple_vuse (load0) != gimple_phi_arg_def (vphi, e0->dest_idx)
4166 21384 : || gimple_vuse (load1) != gimple_phi_arg_def (vphi, e1->dest_idx))
4167 : return false;
4168 : }
4169 : /* Sometimes due to not removing dead statements,
4170 : a virtual phi does not show up going into an infinite loop
4171 : so just reject that case. */
4172 13260 : else if (gimple_vuse (load0) != gimple_vuse (load1))
4173 : return false;
4174 :
4175 13533 : tree ref0 = gimple_assign_rhs1 (load0);
4176 13533 : tree ref1 = gimple_assign_rhs1 (load1);
4177 13533 : tree index = nullptr;
4178 13533 : tree step = nullptr;
4179 13533 : tree index2 = nullptr;
4180 13533 : bool rev_order = false;
4181 :
4182 : /* Both must be *P loads of a compatible value type. The
4183 : TBAA alias-ptr type carried by MEM_REF operand 1 need not match; it is
4184 : merged the way get_alias_type_for_stmts does when the load is built. */
4185 13533 : if (TREE_CODE (ref0) == MEM_REF)
4186 5100 : rev_order = REF_REVERSE_STORAGE_ORDER (ref0);
4187 : else
4188 : {
4189 8433 : if (TREE_CODE (ref0) != TARGET_MEM_REF)
4190 : return false;
4191 315 : index = TMR_INDEX (ref0);
4192 315 : step = TMR_STEP (ref0);
4193 315 : index2 = TMR_INDEX2 (ref0);
4194 : }
4195 5415 : if (TREE_CODE (ref1) == MEM_REF)
4196 : {
4197 4946 : if (index || step || index2)
4198 : return false;
4199 4946 : if (rev_order != REF_REVERSE_STORAGE_ORDER (ref1))
4200 : return false;
4201 : }
4202 : else
4203 : {
4204 469 : if (TREE_CODE (ref1) != TARGET_MEM_REF)
4205 : return false;
4206 325 : if (rev_order)
4207 : return false;
4208 325 : if (!safe_operand_equal_p (index, TMR_INDEX (ref1)))
4209 : return false;
4210 312 : if (!safe_operand_equal_p (step, TMR_STEP (ref1)))
4211 : return false;
4212 312 : if (!safe_operand_equal_p (index2, TMR_INDEX2 (ref1)))
4213 : return false;
4214 : }
4215 :
4216 5246 : if (!types_compatible_p (TREE_TYPE (ref0), TREE_TYPE (ref1)))
4217 : return false;
4218 :
4219 : /* The alignment of the two accesses need to be the same. */
4220 5246 : if (TYPE_ALIGN (TREE_TYPE (ref0)) != TYPE_ALIGN (TREE_TYPE (ref1)))
4221 : return false;
4222 :
4223 5000 : tree p0 = TREE_OPERAND (ref0, 0);
4224 5000 : tree p1 = TREE_OPERAND (ref1, 0);
4225 5000 : if (!is_factor_profitable (load0, merge, &p0, 1))
4226 : return false;
4227 4982 : if (!is_factor_profitable (load1, merge, &p1, 1))
4228 : return false;
4229 :
4230 : /* Merge the two arms' TBAA info as get_alias_type_for_stmts does: keep the
4231 : common alias-ptr type and dependence clique/base when the arms agree,
4232 : otherwise fall back to ptr_type_node (alias-everything) and drop the
4233 : clique/base, so the combined load conservatively conflicts with any store
4234 : either original arm could. */
4235 4982 : unsigned short clique = MR_DEPENDENCE_CLIQUE (ref0);
4236 4982 : unsigned short base = MR_DEPENDENCE_BASE (ref0);
4237 4982 : if (clique != MR_DEPENDENCE_CLIQUE (ref1) || base != MR_DEPENDENCE_BASE (ref1))
4238 : clique = base = 0;
4239 4982 : tree atype = TREE_TYPE (TREE_OPERAND (ref0, 1));
4240 4982 : if (!alias_ptr_types_compatible_p (atype, TREE_TYPE (TREE_OPERAND (ref1, 1))))
4241 : {
4242 588 : atype = ptr_type_node;
4243 588 : clique = base = 0;
4244 : }
4245 :
4246 4982 : tree index0 = TREE_OPERAND (ref0, 1);
4247 4982 : tree index1 = TREE_OPERAND (ref1, 1);
4248 4982 : tree newindex;
4249 4982 : gimple_stmt_iterator gsi;
4250 4982 : gsi = gsi_after_labels (merge);
4251 :
4252 : /* Try to handle different indices. */
4253 4982 : if (operand_equal_p (index0, index1))
4254 4445 : newindex = fold_convert (atype, index0);
4255 : /* FIXME: right now non ssa names with different indices are not handled. */
4256 537 : else if (TREE_CODE (p0) != SSA_NAME || TREE_CODE (p1) != SSA_NAME)
4257 : return false;
4258 : /* If we have the same base already, just create a phi for the index
4259 : and the pointer plus will be done in the merge. */
4260 72 : else if (p0 == p1)
4261 : {
4262 53 : index0 = fold_convert (sizetype, index0);
4263 53 : index1 = fold_convert (sizetype, index1);
4264 53 : tree index = make_ssa_name (sizetype);
4265 53 : gphi *pphi = create_phi_node (index, merge);
4266 53 : add_phi_arg (pphi, index0, e0, gimple_phi_arg_location (phi, e0->dest_idx));
4267 53 : add_phi_arg (pphi, index1, e1, gimple_phi_arg_location (phi, e1->dest_idx));
4268 53 : p0 = gimple_build (&gsi, true, GSI_SAME_STMT,
4269 : UNKNOWN_LOCATION,
4270 : POINTER_PLUS_EXPR, atype, p0, index);
4271 : /* Since we already have the same pointer for both, just set that way.
4272 : Also the index offset is already 0 because we just did the add. */
4273 53 : p1 = p0;
4274 53 : newindex = build_zero_cst (atype);
4275 53 : if (dump_file && (dump_flags & TDF_DETAILS))
4276 : {
4277 2 : fprintf (dump_file, "new PHI ");
4278 2 : print_generic_expr (dump_file, index);
4279 2 : fprintf (dump_file,
4280 : " was created for the index.\n");
4281 : }
4282 : }
4283 : else
4284 : {
4285 19 : gimple_stmt_iterator gsi_index;
4286 : /* When the indices are different create 2 new pointers on each
4287 : of the middle bb right after the original load.
4288 : Note in the case of 0 index, gimple_build just returns
4289 : the original pointer. */
4290 19 : gsi_index = gsi_for_stmt (load0);
4291 19 : index0 = fold_convert (sizetype, index0);
4292 19 : p0 = gimple_build (&gsi_index, false, GSI_SAME_STMT,
4293 : gimple_location (load0),
4294 : POINTER_PLUS_EXPR, atype, p0, index0);
4295 :
4296 19 : gsi_index = gsi_for_stmt (load1);
4297 19 : index1 = fold_convert (sizetype, index1);
4298 19 : p1 = gimple_build (&gsi_index, false, GSI_SAME_STMT,
4299 : gimple_location (load1),
4300 : POINTER_PLUS_EXPR, atype, p1, index1);
4301 19 : newindex = build_zero_cst (atype);
4302 19 : if (dump_file && (dump_flags & TDF_DETAILS))
4303 : {
4304 1 : fprintf (dump_file, "new ptrs ");
4305 1 : print_generic_expr (dump_file, p0);
4306 1 : fprintf (dump_file, " and ");
4307 1 : print_generic_expr (dump_file, p1);
4308 1 : fprintf (dump_file,
4309 : " was created due to different offsets.\n");
4310 : }
4311 : }
4312 :
4313 4517 : tree newptr;
4314 4517 : if (p0 != p1)
4315 : {
4316 : /* We can't factor out a non-ssa named based load
4317 : as it might cause a variable not taken an
4318 : address to become needing the address taken.
4319 : An example is in go.
4320 : Were we produce:
4321 : _24 = PHI <&crypto/tls.cipherSuitesPreferenceOrder(36), &crypto/tls.cipherSuitesPreferenceOrderNoAES(37)>
4322 : And &crypto/tls.cipherSuitesPreferenceOrder address bit was not set.
4323 : FIXME: Refine to check ADDRESSABLE bit. */
4324 3065 : if (TREE_CODE (p0) != SSA_NAME || TREE_CODE (p1) != SSA_NAME)
4325 : return false;
4326 : // Incompatible address spaces or differnt function pointers could show up here.
4327 343 : if (!types_compatible_p (TREE_TYPE (p0), TREE_TYPE (p1)))
4328 : return false;
4329 : /* Build P' = PHI <P, Q> and the single load result = *P'. */
4330 325 : newptr = make_ssa_name (TREE_TYPE (p0));
4331 325 : gphi *pphi = create_phi_node (newptr, merge);
4332 325 : add_phi_arg (pphi, p0, e0, gimple_phi_arg_location (phi, e0->dest_idx));
4333 325 : add_phi_arg (pphi, p1, e1, gimple_phi_arg_location (phi, e1->dest_idx));
4334 : }
4335 : else
4336 : newptr = p0;
4337 :
4338 : /* Build the combined load RES = *PTR, reusing the PHI result so any range
4339 : info on it is preserved (as factor_out_conditional_operation does). */
4340 1777 : tree nref;
4341 1777 : if (index || step || index2)
4342 24 : nref = build5 (TARGET_MEM_REF, TREE_TYPE (ref0), newptr,
4343 : newindex, index, step, index2);
4344 : else
4345 : {
4346 1753 : nref = build2 (MEM_REF, TREE_TYPE (ref0), newptr, newindex);
4347 1753 : REF_REVERSE_STORAGE_ORDER (nref) = rev_order;
4348 : }
4349 1777 : MR_DEPENDENCE_CLIQUE (nref) = clique;
4350 1777 : MR_DEPENDENCE_BASE (nref) = base;
4351 1777 : tree res = gimple_phi_result (phi);
4352 1777 : gassign *load = gimple_build_assign (res, nref);
4353 1777 : if (gphi *vphi = get_virtual_phi (merge))
4354 1435 : gimple_set_vuse (load, gimple_phi_result (vphi));
4355 : else
4356 684 : gimple_set_vuse (load, gimple_vuse (load0));
4357 1777 : gsi_insert_before (&gsi, load, GSI_SAME_STMT);
4358 :
4359 : /* RES is now defined by the load; drop the original PHI. */
4360 1777 : gsi = gsi_for_stmt (phi);
4361 1777 : remove_phi_node (&gsi, false);
4362 :
4363 : /* The two arm loads are now dead. */
4364 1777 : gsi = gsi_for_stmt (load0);
4365 1777 : gsi_remove (&gsi, true);
4366 1777 : release_defs (load0);
4367 1777 : gsi = gsi_for_stmt (load1);
4368 1777 : gsi_remove (&gsi, true);
4369 1777 : release_defs (load1);
4370 :
4371 1777 : if (dump_file && (dump_flags & TDF_DETAILS))
4372 : {
4373 11 : fprintf (dump_file, "PHI ");
4374 11 : print_generic_expr (dump_file, res);
4375 11 : fprintf (dump_file,
4376 : " changed to factor out load from COND_EXPR.\n");
4377 11 : if (p0 != p1)
4378 : {
4379 9 : fprintf (dump_file, "new PHI ");
4380 9 : print_generic_expr (dump_file, newptr);
4381 9 : fprintf (dump_file,
4382 : " was created for the pointers.\n");
4383 : }
4384 : }
4385 :
4386 1777 : statistics_counter_event (cfun, "factored load out of COND_EXPR", 1);
4387 1777 : return true;
4388 : }
4389 :
4390 : /* Factor out operations and stores from the phi of the MERGE block coming
4391 : in from the edges E1 and E2 if possible. COND_STMT is the conditional
4392 : statement of the origin block. DIAMOND_P says that both E1 and E2 src
4393 : are not the origin block but rather 2 middle BBs. EARLY_P is true if
4394 : this was the early phi-opt.
4395 : Returns true if a factoring happened. */
4396 : static bool
4397 2560789 : factor_out_all (edge e1, edge e2, basic_block merge,
4398 : gcond *cond_stmt, bool diamond_p, bool early_p)
4399 : {
4400 2560789 : bool changed = false;
4401 2560789 : bool do_over;
4402 2560789 : basic_block bb1 = e1->src;
4403 2560789 : basic_block bb2 = e2->src;
4404 2532949 : do
4405 : {
4406 2604899 : do_over = false;
4407 2604899 : if (diamond_p && get_virtual_phi (merge))
4408 : {
4409 720163 : if (cond_if_else_store_replacement_limited (bb1, bb2, merge))
4410 : {
4411 13497 : changed = true;
4412 13497 : do_over = true;
4413 14287 : continue;
4414 : }
4415 : }
4416 2591402 : if (!single_pred_p (bb1))
4417 : break;
4418 1735430 : if (!diamond_p && get_virtual_phi (merge)
4419 3555299 : && cond_store_replacement_limited (bb1, merge, bb2,
4420 : e1, e2, false))
4421 : {
4422 790 : changed = true;
4423 790 : do_over = true;
4424 790 : continue;
4425 : }
4426 2518662 : gphi_iterator gsi;
4427 5585164 : for (gsi = gsi_start_phis (merge); !gsi_end_p (gsi); gsi_next (&gsi))
4428 : {
4429 3096325 : gphi *phi = *gsi;
4430 : /* Conditional load elimination can only be on a diamond. */
4431 3096325 : if ((diamond_p
4432 1002332 : && factor_out_conditional_load (e1, e2, merge, phi, early_p,
4433 : !fold_before_rtl_expansion_p ()))
4434 4096880 : || factor_out_conditional_operation (e1, e2, merge, phi,
4435 : cond_stmt, early_p))
4436 : {
4437 : changed = true;
4438 : do_over = true;
4439 : break;
4440 : }
4441 : }
4442 : } while (do_over);
4443 2560789 : return changed;
4444 : }
4445 :
4446 : /* Return TRUE if STMT has a VUSE whose corresponding VDEF is in BB. */
4447 :
4448 : static bool
4449 12134 : local_mem_dependence (gimple *stmt, basic_block bb)
4450 : {
4451 24268 : tree vuse = gimple_vuse (stmt);
4452 12134 : gimple *def;
4453 :
4454 12134 : if (!vuse)
4455 : return false;
4456 :
4457 12134 : def = SSA_NAME_DEF_STMT (vuse);
4458 12134 : return (def && gimple_bb (def) == bb);
4459 : }
4460 :
4461 : /* Given a "diamond" control-flow pattern where BB0 tests a condition,
4462 : BB1 and BB2 are "then" and "else" blocks dependent on this test,
4463 : and BB3 rejoins control flow following BB1 and BB2, look for
4464 : opportunities to hoist loads as follows. If BB3 contains a PHI of
4465 : two loads, one each occurring in BB1 and BB2, and the loads are
4466 : provably of adjacent fields in the same structure, then move both
4467 : loads into BB0. Of course this can only be done if there are no
4468 : dependencies preventing such motion.
4469 :
4470 : One of the hoisted loads will always be speculative, so the
4471 : transformation is currently conservative:
4472 :
4473 : - The fields must be strictly adjacent.
4474 : - The two fields must occupy a single memory block that is
4475 : guaranteed to not cross a page boundary.
4476 :
4477 : The last is difficult to prove, as such memory blocks should be
4478 : aligned on the minimum of the stack alignment boundary and the
4479 : alignment guaranteed by heap allocation interfaces. Thus we rely
4480 : on a parameter for the alignment value.
4481 :
4482 : Provided a good value is used for the last case, the first
4483 : restriction could possibly be relaxed. */
4484 :
4485 : static void
4486 603958 : hoist_adjacent_loads (basic_block bb0, basic_block bb1,
4487 : basic_block bb2, basic_block bb3)
4488 : {
4489 603958 : unsigned HOST_WIDE_INT param_align = param_l1_cache_line_size;
4490 603958 : unsigned HOST_WIDE_INT param_align_bits = param_align * BITS_PER_UNIT;
4491 603958 : gphi_iterator gsi;
4492 :
4493 : /* Walk the phis in bb3 looking for an opportunity. We are looking
4494 : for phis of two SSA names, one each of which is defined in bb1 and
4495 : bb2. */
4496 1359000 : for (gsi = gsi_start_phis (bb3); !gsi_end_p (gsi); gsi_next (&gsi))
4497 : {
4498 755042 : gphi *phi_stmt = gsi.phi ();
4499 755042 : gimple *def1, *def2;
4500 755042 : tree arg1, arg2, ref1, ref2, field1, field2;
4501 755042 : tree tree_offset1, tree_offset2, tree_size2, next;
4502 755042 : unsigned HOST_WIDE_INT offset1, offset2, size2, align1;
4503 755042 : gimple_stmt_iterator gsi2;
4504 755042 : basic_block bb_for_def1, bb_for_def2;
4505 :
4506 755042 : if (gimple_phi_num_args (phi_stmt) != 2
4507 1510084 : || virtual_operand_p (gimple_phi_result (phi_stmt)))
4508 748975 : continue;
4509 :
4510 193754 : arg1 = gimple_phi_arg_def (phi_stmt, 0);
4511 193754 : arg2 = gimple_phi_arg_def (phi_stmt, 1);
4512 :
4513 227007 : if (TREE_CODE (arg1) != SSA_NAME
4514 176603 : || TREE_CODE (arg2) != SSA_NAME
4515 161770 : || SSA_NAME_IS_DEFAULT_DEF (arg1)
4516 355194 : || SSA_NAME_IS_DEFAULT_DEF (arg2))
4517 33253 : continue;
4518 :
4519 160501 : def1 = SSA_NAME_DEF_STMT (arg1);
4520 160501 : def2 = SSA_NAME_DEF_STMT (arg2);
4521 :
4522 160501 : if ((gimple_bb (def1) != bb1 || gimple_bb (def2) != bb2)
4523 175033 : && (gimple_bb (def2) != bb1 || gimple_bb (def1) != bb2))
4524 41492 : continue;
4525 :
4526 : /* Check the mode of the arguments to be sure a conditional move
4527 : can be generated for it. */
4528 238018 : if (optab_handler (movcc_optab, TYPE_MODE (TREE_TYPE (arg1)))
4529 : == CODE_FOR_nothing)
4530 5260 : continue;
4531 :
4532 : /* Both statements must be assignments whose RHS is a COMPONENT_REF. */
4533 113749 : if (!gimple_assign_single_p (def1)
4534 53315 : || !gimple_assign_single_p (def2)
4535 71260 : || gimple_has_volatile_ops (def1)
4536 185003 : || gimple_has_volatile_ops (def2))
4537 78122 : continue;
4538 :
4539 35627 : ref1 = gimple_assign_rhs1 (def1);
4540 35627 : ref2 = gimple_assign_rhs1 (def2);
4541 :
4542 35627 : if (TREE_CODE (ref1) != COMPONENT_REF
4543 24145 : || TREE_CODE (ref2) != COMPONENT_REF)
4544 11605 : continue;
4545 :
4546 : /* The zeroth operand of the two component references must be
4547 : identical. It is not sufficient to compare get_base_address of
4548 : the two references, because this could allow for different
4549 : elements of the same array in the two trees. It is not safe to
4550 : assume that the existence of one array element implies the
4551 : existence of a different one. */
4552 24022 : if (!operand_equal_p (TREE_OPERAND (ref1, 0), TREE_OPERAND (ref2, 0), 0))
4553 4589 : continue;
4554 :
4555 19433 : field1 = TREE_OPERAND (ref1, 1);
4556 19433 : field2 = TREE_OPERAND (ref2, 1);
4557 :
4558 : /* Check for field adjacency, and ensure field1 comes first. */
4559 19433 : for (next = DECL_CHAIN (field1);
4560 33603 : next && TREE_CODE (next) != FIELD_DECL;
4561 14170 : next = DECL_CHAIN (next))
4562 : ;
4563 :
4564 19433 : if (next != field2)
4565 : {
4566 15825 : for (next = DECL_CHAIN (field2);
4567 17896 : next && TREE_CODE (next) != FIELD_DECL;
4568 2071 : next = DECL_CHAIN (next))
4569 : ;
4570 :
4571 15825 : if (next != field1)
4572 13366 : continue;
4573 :
4574 : std::swap (field1, field2);
4575 : std::swap (def1, def2);
4576 : }
4577 :
4578 6067 : bb_for_def1 = gimple_bb (def1);
4579 6067 : bb_for_def2 = gimple_bb (def2);
4580 :
4581 : /* Check for proper alignment of the first field. */
4582 6067 : tree_offset1 = bit_position (field1);
4583 6067 : tree_offset2 = bit_position (field2);
4584 6067 : tree_size2 = DECL_SIZE (field2);
4585 :
4586 6067 : if (!tree_fits_uhwi_p (tree_offset1)
4587 6067 : || !tree_fits_uhwi_p (tree_offset2)
4588 6067 : || !tree_fits_uhwi_p (tree_size2))
4589 0 : continue;
4590 :
4591 6067 : offset1 = tree_to_uhwi (tree_offset1);
4592 6067 : offset2 = tree_to_uhwi (tree_offset2);
4593 6067 : size2 = tree_to_uhwi (tree_size2);
4594 6067 : align1 = DECL_ALIGN (field1) % param_align_bits;
4595 :
4596 6067 : if (offset1 % BITS_PER_UNIT != 0)
4597 0 : continue;
4598 :
4599 : /* For profitability, the two field references should fit within
4600 : a single cache line. */
4601 6067 : if (align1 + offset2 - offset1 + size2 > param_align_bits)
4602 0 : continue;
4603 :
4604 : /* The two expressions cannot be dependent upon vdefs defined
4605 : in bb1/bb2. */
4606 6067 : if (local_mem_dependence (def1, bb_for_def1)
4607 6067 : || local_mem_dependence (def2, bb_for_def2))
4608 0 : continue;
4609 :
4610 : /* The conditions are satisfied; hoist the loads from bb1 and bb2 into
4611 : bb0. We hoist the first one first so that a cache miss is handled
4612 : efficiently regardless of hardware cache-fill policy. */
4613 6067 : gsi2 = gsi_for_stmt (def1);
4614 6067 : gsi_move_to_bb_end (&gsi2, bb0);
4615 6067 : gsi2 = gsi_for_stmt (def2);
4616 6067 : gsi_move_to_bb_end (&gsi2, bb0);
4617 6067 : statistics_counter_event (cfun, "hoisted loads", 1);
4618 :
4619 6067 : if (dump_file && (dump_flags & TDF_DETAILS))
4620 : {
4621 0 : fprintf (dump_file,
4622 : "\nHoisting adjacent loads from %d and %d into %d: \n",
4623 : bb_for_def1->index, bb_for_def2->index, bb0->index);
4624 0 : print_gimple_stmt (dump_file, def1, 0, TDF_VOPS|TDF_MEMSYMS);
4625 0 : print_gimple_stmt (dump_file, def2, 0, TDF_VOPS|TDF_MEMSYMS);
4626 : }
4627 : }
4628 603958 : }
4629 :
4630 : /* Determine whether we should attempt to hoist adjacent loads out of
4631 : diamond patterns in pass_phiopt. Always hoist loads if
4632 : -fhoist-adjacent-loads is specified and the target machine has
4633 : both a conditional move instruction and a defined cache line size. */
4634 :
4635 : static bool
4636 3180751 : gate_hoist_loads (void)
4637 : {
4638 3180751 : return (flag_hoist_adjacent_loads == 1
4639 3180751 : && param_l1_cache_line_size
4640 0 : && HAVE_conditional_move);
4641 : }
4642 :
4643 : template <class func_type>
4644 : static void
4645 6779922 : execute_over_cond_phis (func_type func)
4646 : {
4647 : unsigned n, i;
4648 : basic_block *bb_order;
4649 : basic_block bb;
4650 : /* Search every basic block for COND_EXPR we may be able to optimize.
4651 :
4652 : We walk the blocks in order that guarantees that a block with
4653 : a single predecessor is processed before the predecessor.
4654 : This ensures that we collapse inner ifs before visiting the
4655 : outer ones, and also that we do not try to visit a removed
4656 : block. */
4657 6779922 : bb_order = single_pred_before_succ_order ();
4658 6779922 : n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
4659 :
4660 60935781 : for (i = 0; i < n; i++)
4661 : {
4662 : basic_block bb1, bb2;
4663 : edge e1, e2;
4664 54155859 : bool diamond_p = false;
4665 :
4666 54155859 : bb = bb_order[i];
4667 :
4668 : /* Check to see if the last statement is a GIMPLE_COND. */
4669 54155859 : gcond *cond_stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
4670 32371755 : if (!cond_stmt)
4671 54155859 : continue;
4672 :
4673 21784104 : e1 = EDGE_SUCC (bb, 0);
4674 21784104 : bb1 = e1->dest;
4675 21784104 : e2 = EDGE_SUCC (bb, 1);
4676 21784104 : bb2 = e2->dest;
4677 :
4678 : /* We cannot do the optimization on abnormal edges. */
4679 21784104 : if ((e1->flags & EDGE_ABNORMAL) != 0
4680 21784104 : || (e2->flags & EDGE_ABNORMAL) != 0)
4681 0 : continue;
4682 :
4683 : /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
4684 21784104 : if (EDGE_COUNT (bb1->succs) == 0
4685 20304820 : || EDGE_COUNT (bb2->succs) == 0)
4686 5001684 : continue;
4687 :
4688 : /* Find the bb which is the fall through to the other. */
4689 16782420 : if (EDGE_SUCC (bb1, 0)->dest == bb2)
4690 : ;
4691 14252024 : else if (EDGE_SUCC (bb2, 0)->dest == bb1)
4692 : {
4693 : std::swap (bb1, bb2);
4694 : std::swap (e1, e2);
4695 : }
4696 10850420 : else if (EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest
4697 12429536 : && single_succ_p (bb2))
4698 : {
4699 1579116 : diamond_p = true;
4700 1579116 : e2 = EDGE_SUCC (bb2, 0);
4701 : /* Make sure bb2 is just a fall through. */
4702 1579116 : if ((e2->flags & EDGE_FALLTHRU) == 0)
4703 52259 : continue;
4704 : }
4705 : else
4706 10850420 : continue;
4707 :
4708 5879741 : e1 = EDGE_SUCC (bb1, 0);
4709 :
4710 : /* Make sure that bb1 is just a fall through. */
4711 5879741 : if (!single_succ_p (bb1)
4712 5879741 : || (e1->flags & EDGE_FALLTHRU) == 0)
4713 1390623 : continue;
4714 :
4715 4489118 : func (bb, bb1, bb2, e1, e2, diamond_p, cond_stmt);
4716 : }
4717 6779922 : free (bb_order);
4718 6779922 : }
4719 :
4720 : /* This pass tries to replaces an if-then-else block with an
4721 : assignment. We have different kinds of transformations.
4722 : Some of these transformations are also performed by the ifcvt
4723 : RTL optimizer.
4724 :
4725 : PHI-OPT using Match-and-simplify infrastructure
4726 : -----------------------
4727 :
4728 : The PHI-OPT pass will try to use match-and-simplify infrastructure
4729 : (gimple_simplify) to do transformations. This is implemented in
4730 : match_simplify_replacement.
4731 :
4732 : The way it works is it replaces:
4733 : bb0:
4734 : if (cond) goto bb2; else goto bb1;
4735 : bb1:
4736 : bb2:
4737 : x = PHI <a (bb1), b (bb0), ...>;
4738 :
4739 : with a statement if it gets simplified from `cond ? b : a`.
4740 :
4741 : bb0:
4742 : x1 = cond ? b : a;
4743 : bb2:
4744 : x = PHI <a (bb1), x1 (bb0), ...>;
4745 : Bb1 might be removed as it becomes unreachable when doing the replacement.
4746 : Though bb1 does not have to be considered a forwarding basic block from bb0.
4747 :
4748 : Will try to see if `(!cond) ? a : b` gets simplified (iff !cond simplifies);
4749 : this is done not to have an explosion of patterns in match.pd.
4750 : Note bb1 does not need to be completely empty, it can contain
4751 : one statement which is known not to trap.
4752 :
4753 : It also can handle the case where we have two forwarding bbs (diamond):
4754 : bb0:
4755 : if (cond) goto bb2; else goto bb1;
4756 : bb1: goto bb3;
4757 : bb2: goto bb3;
4758 : bb3:
4759 : x = PHI <a (bb1), b (bb2), ...>;
4760 : And that is replaced with a statement if it is simplified
4761 : from `cond ? b : a`.
4762 : Again bb1 and bb2 does not have to be completely empty but
4763 : each can contain one statement which is known not to trap.
4764 : But in this case bb1/bb2 can only be forwarding basic blocks.
4765 :
4766 : This fully replaces the old "Conditional Replacement",
4767 : "ABS Replacement" and "MIN/MAX Replacement" transformations as they are now
4768 : implemented in match.pd.
4769 :
4770 : Value Replacement
4771 : -----------------
4772 :
4773 : This transformation, implemented in value_replacement, replaces
4774 :
4775 : bb0:
4776 : if (a != b) goto bb2; else goto bb1;
4777 : bb1:
4778 : bb2:
4779 : x = PHI <a (bb1), b (bb0), ...>;
4780 :
4781 : with
4782 :
4783 : bb0:
4784 : bb2:
4785 : x = PHI <b (bb0), ...>;
4786 :
4787 : This opportunity can sometimes occur as a result of other
4788 : optimizations.
4789 :
4790 :
4791 : Another case caught by value replacement looks like this:
4792 :
4793 : bb0:
4794 : t1 = a == CONST;
4795 : t2 = b > c;
4796 : t3 = t1 & t2;
4797 : if (t3 != 0) goto bb1; else goto bb2;
4798 : bb1:
4799 : bb2:
4800 : x = PHI (CONST, a)
4801 :
4802 : Gets replaced with:
4803 : bb0:
4804 : bb2:
4805 : t1 = a == CONST;
4806 : t2 = b > c;
4807 : t3 = t1 & t2;
4808 : x = a;
4809 :
4810 :
4811 : This pass also performs a fifth transformation of a slightly different
4812 : flavor.
4813 :
4814 : Factor operations in COND_EXPR
4815 : ------------------------------
4816 :
4817 : This transformation factors the unary operations out of COND_EXPR with
4818 : factor_out_conditional_operation.
4819 :
4820 : For example:
4821 : if (a <= CST) goto <bb 3>; else goto <bb 4>;
4822 : <bb 3>:
4823 : tmp = (int) a;
4824 : <bb 4>:
4825 : tmp = PHI <tmp, CST>
4826 :
4827 : Into:
4828 : if (a <= CST) goto <bb 3>; else goto <bb 4>;
4829 : <bb 3>:
4830 : <bb 4>:
4831 : a = PHI <a, CST>
4832 : tmp = (int) a;
4833 :
4834 : Adjacent Load Hoisting
4835 : ----------------------
4836 :
4837 : This transformation replaces
4838 :
4839 : bb0:
4840 : if (...) goto bb2; else goto bb1;
4841 : bb1:
4842 : x1 = (<expr>).field1;
4843 : goto bb3;
4844 : bb2:
4845 : x2 = (<expr>).field2;
4846 : bb3:
4847 : # x = PHI <x1, x2>;
4848 :
4849 : with
4850 :
4851 : bb0:
4852 : x1 = (<expr>).field1;
4853 : x2 = (<expr>).field2;
4854 : if (...) goto bb2; else goto bb1;
4855 : bb1:
4856 : goto bb3;
4857 : bb2:
4858 : bb3:
4859 : # x = PHI <x1, x2>;
4860 :
4861 : The purpose of this transformation is to enable generation of conditional
4862 : move instructions such as Intel CMOVE or PowerPC ISEL. Because one of
4863 : the loads is speculative, the transformation is restricted to very
4864 : specific cases to avoid introducing a page fault. We are looking for
4865 : the common idiom:
4866 :
4867 : if (...)
4868 : x = y->left;
4869 : else
4870 : x = y->right;
4871 :
4872 : where left and right are typically adjacent pointers in a tree structure. */
4873 :
4874 : namespace {
4875 :
4876 : const pass_data pass_data_phiopt =
4877 : {
4878 : GIMPLE_PASS, /* type */
4879 : "phiopt", /* name */
4880 : OPTGROUP_NONE, /* optinfo_flags */
4881 : TV_TREE_PHIOPT, /* tv_id */
4882 : ( PROP_cfg | PROP_ssa ), /* properties_required */
4883 : 0, /* properties_provided */
4884 : 0, /* properties_destroyed */
4885 : 0, /* todo_flags_start */
4886 : 0, /* todo_flags_finish */
4887 : };
4888 :
4889 : class pass_phiopt : public gimple_opt_pass
4890 : {
4891 : public:
4892 1176784 : pass_phiopt (gcc::context *ctxt)
4893 2353568 : : gimple_opt_pass (pass_data_phiopt, ctxt), early_p (false)
4894 : {}
4895 :
4896 : /* opt_pass methods: */
4897 882588 : opt_pass * clone () final override { return new pass_phiopt (m_ctxt); }
4898 1176784 : void set_pass_param (unsigned n, bool param) final override
4899 : {
4900 1176784 : gcc_assert (n == 0);
4901 1176784 : early_p = param;
4902 1176784 : }
4903 5722910 : bool gate (function *) final override { return flag_ssa_phiopt; }
4904 : unsigned int execute (function *) final override;
4905 :
4906 : private:
4907 : bool early_p;
4908 : }; // class pass_phiopt
4909 :
4910 : } // anon namespace
4911 :
4912 : gimple_opt_pass *
4913 294196 : make_pass_phiopt (gcc::context *ctxt)
4914 : {
4915 294196 : return new pass_phiopt (ctxt);
4916 : }
4917 :
4918 : unsigned int
4919 5719639 : pass_phiopt::execute (function *)
4920 : {
4921 5719639 : bool do_hoist_loads = !early_p ? gate_hoist_loads () : false;
4922 5719639 : bool cfgchanged = false;
4923 :
4924 5719639 : calculate_dominance_info (CDI_DOMINATORS);
4925 5719639 : mark_ssa_maybe_undefs ();
4926 :
4927 9267287 : auto phiopt_exec = [&] (basic_block bb, basic_block bb1,
4928 : basic_block bb2, edge e1, edge e2,
4929 : bool diamond_p, gcond *cond_stmt)
4930 : {
4931 3547648 : if (diamond_p)
4932 : {
4933 1132436 : basic_block bb3 = e1->dest;
4934 :
4935 1132436 : if (!single_pred_p (bb1)
4936 2204600 : || !single_pred_p (bb2))
4937 3547648 : return;
4938 :
4939 1011008 : if (do_hoist_loads
4940 794428 : && !FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt)))
4941 786274 : && EDGE_COUNT (bb->succs) == 2
4942 786274 : && EDGE_COUNT (bb3->preds) == 2
4943 : /* If one edge or the other is dominant, a conditional move
4944 : is likely to perform worse than the well-predicted branch. */
4945 608459 : && !predictable_edge_p (EDGE_SUCC (bb, 0))
4946 1614966 : && !predictable_edge_p (EDGE_SUCC (bb, 1)))
4947 603958 : hoist_adjacent_loads (bb, bb1, bb2, bb3);
4948 : }
4949 :
4950 1011008 : gimple_stmt_iterator gsi;
4951 :
4952 : /* Check that we're looking for nested phis. */
4953 1011008 : basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest : bb2;
4954 :
4955 : /* Factor out operations from the phi if possible. */
4956 3426220 : if (EDGE_COUNT (merge->preds) == 2
4957 3426220 : && !optimize_debug && factor_out_all (e1, e2, merge, cond_stmt, diamond_p, early_p))
4958 37077 : cfgchanged = true;
4959 :
4960 3426220 : gimple_seq phis = phi_nodes (merge);
4961 :
4962 3426220 : if (gimple_seq_empty_p (phis))
4963 : return;
4964 :
4965 : /* Value replacement can work with more than one PHI
4966 : so try that first. */
4967 3411912 : if (!early_p && !diamond_p)
4968 4286839 : for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
4969 : {
4970 2497235 : gphi *phi = as_a <gphi *> (gsi_stmt (gsi));
4971 2497235 : tree arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
4972 2497235 : tree arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
4973 2497235 : if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1) == 2)
4974 : {
4975 1963 : cfgchanged = true;
4976 1963 : return;
4977 : }
4978 : }
4979 :
4980 3409949 : gphi *phi = single_non_singleton_phi_for_edges (phis, e1, e2);
4981 3409949 : if (!phi)
4982 : return;
4983 :
4984 868186 : tree arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
4985 868186 : tree arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
4986 :
4987 : /* Something is wrong if we cannot find the arguments in the PHI
4988 : node. */
4989 868186 : gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
4990 :
4991 :
4992 : /* Do the replacement of conditional if it can be done. */
4993 868186 : if (match_simplify_replacement (bb, bb1, bb2, e1, e2, phi,
4994 : arg0, arg1, early_p, diamond_p))
4995 96106 : cfgchanged = true;
4996 772080 : else if (comparison_combine (bb, bb1, bb2, e1, e2, phi,
4997 : arg0, arg1, diamond_p))
4998 16 : cfgchanged = true;
4999 772064 : else if (!early_p
5000 511299 : && !diamond_p
5001 477613 : && single_pred_p (bb1)
5002 1229701 : && cond_removal_in_builtin_zero_pattern (bb, bb1, e1, e2,
5003 : phi, arg0, arg1))
5004 13 : cfgchanged = true;
5005 772051 : else if (single_pred_p (bb1)
5006 721361 : && !diamond_p
5007 1430209 : && spaceship_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
5008 2330 : cfgchanged = true;
5009 5719639 : };
5010 :
5011 5719639 : execute_over_cond_phis (phiopt_exec);
5012 :
5013 5719639 : if (cfgchanged)
5014 90563 : return TODO_cleanup_cfg;
5015 : return 0;
5016 : }
5017 :
5018 : /* This pass tries to transform conditional stores into unconditional
5019 : ones, enabling further simplifications with the simpler then and else
5020 : blocks. In particular it replaces this:
5021 :
5022 : bb0:
5023 : if (cond) goto bb2; else goto bb1;
5024 : bb1:
5025 : *p = RHS;
5026 : bb2:
5027 :
5028 : with
5029 :
5030 : bb0:
5031 : if (cond) goto bb1; else goto bb2;
5032 : bb1:
5033 : condtmp' = *p;
5034 : bb2:
5035 : condtmp = PHI <RHS, condtmp'>
5036 : *p = condtmp;
5037 :
5038 : This transformation can only be done under several constraints,
5039 : documented below. It also replaces:
5040 :
5041 : bb0:
5042 : if (cond) goto bb2; else goto bb1;
5043 : bb1:
5044 : *p = RHS1;
5045 : goto bb3;
5046 : bb2:
5047 : *p = RHS2;
5048 : bb3:
5049 :
5050 : with
5051 :
5052 : bb0:
5053 : if (cond) goto bb3; else goto bb1;
5054 : bb1:
5055 : bb3:
5056 : condtmp = PHI <RHS1, RHS2>
5057 : *p = condtmp; */
5058 :
5059 : namespace {
5060 :
5061 : const pass_data pass_data_cselim =
5062 : {
5063 : GIMPLE_PASS, /* type */
5064 : "cselim", /* name */
5065 : OPTGROUP_NONE, /* optinfo_flags */
5066 : TV_TREE_PHIOPT, /* tv_id */
5067 : ( PROP_cfg | PROP_ssa ), /* properties_required */
5068 : 0, /* properties_provided */
5069 : 0, /* properties_destroyed */
5070 : 0, /* todo_flags_start */
5071 : 0, /* todo_flags_finish */
5072 : };
5073 :
5074 : class pass_cselim : public gimple_opt_pass
5075 : {
5076 : public:
5077 294196 : pass_cselim (gcc::context *ctxt)
5078 588392 : : gimple_opt_pass (pass_data_cselim, ctxt)
5079 : {}
5080 :
5081 : /* opt_pass methods: */
5082 1060389 : bool gate (function *) final override { return flag_tree_cselim; }
5083 : unsigned int execute (function *) final override;
5084 :
5085 : }; // class pass_cselim
5086 :
5087 : } // anon namespace
5088 :
5089 : gimple_opt_pass *
5090 294196 : make_pass_cselim (gcc::context *ctxt)
5091 : {
5092 294196 : return new pass_cselim (ctxt);
5093 : }
5094 :
5095 : unsigned int
5096 1060283 : pass_cselim::execute (function *)
5097 : {
5098 1060283 : bool cfgchanged = false;
5099 1060283 : hash_set<tree> *nontrap = 0;
5100 1060283 : unsigned todo = 0;
5101 :
5102 : /* ??? We are not interested in loop related info, but the following
5103 : will create it, ICEing as we didn't init loops with pre-headers.
5104 : An interfacing issue of find_data_references_in_bb. */
5105 1060283 : loop_optimizer_init (LOOPS_NORMAL);
5106 1060283 : scev_initialize ();
5107 :
5108 1060283 : calculate_dominance_info (CDI_DOMINATORS);
5109 :
5110 : /* Calculate the set of non-trapping memory accesses. */
5111 1060283 : nontrap = get_non_trapping ();
5112 :
5113 2001753 : auto cselim_exec = [&] (basic_block bb, basic_block bb1,
5114 : basic_block bb2, edge e1, edge e2,
5115 : bool diamond_p, gcond *)
5116 : {
5117 941470 : if (diamond_p)
5118 : {
5119 326728 : basic_block bb3 = e1->dest;
5120 :
5121 : /* Only handle sinking of store from 2 bbs only,
5122 : The middle bbs don't need to come from the
5123 : if always since we are sinking rather than
5124 : hoisting. */
5125 326728 : if (EDGE_COUNT (bb3->preds) != 2)
5126 : return;
5127 240899 : if (cond_if_else_store_replacement (bb1, bb2, bb3))
5128 1017 : cfgchanged = true;
5129 : return;
5130 : }
5131 :
5132 : /* Also make sure that bb1 only have one predecessor and that it
5133 : is bb. */
5134 614742 : if (!single_pred_p (bb1)
5135 1182051 : || single_pred (bb1) != bb)
5136 : return;
5137 :
5138 : /* bb1 is the middle block, bb2 the join block, bb the split block,
5139 : e1 the fallthrough edge from bb1 to bb2. We can't do the
5140 : optimization if the join block has more than two predecessors. */
5141 567309 : if (EDGE_COUNT (bb2->preds) > 2)
5142 : return;
5143 :
5144 441946 : if (cond_store_replacement_limited (bb1, bb2, bb, e1, e2, true))
5145 : {
5146 716 : cfgchanged = true;
5147 716 : return;
5148 : }
5149 441230 : gimple *assign = cselim_candidate (bb1, bb2, e1);
5150 441230 : if (cond_store_replacement (bb1, bb2, e1, e2, assign, nontrap))
5151 5772 : cfgchanged = true;
5152 1060283 : };
5153 :
5154 1060283 : execute_over_cond_phis (cselim_exec);
5155 :
5156 2120566 : delete nontrap;
5157 : /* If the CFG has changed, we should cleanup the CFG. */
5158 1060283 : if (cfgchanged)
5159 : {
5160 4403 : gsi_commit_edge_inserts ();
5161 4403 : todo = TODO_cleanup_cfg;
5162 : }
5163 1060283 : scev_finalize ();
5164 1060283 : loop_optimizer_finalize ();
5165 1060283 : return todo;
5166 : }
|
