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