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