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 3527979 : single_non_singleton_phi_for_edges (gimple_seq seq, edge e0, edge e1)
63 : {
64 3527979 : gimple_stmt_iterator i;
65 3527979 : gphi *phi = NULL;
66 5228766 : for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
67 : {
68 4252688 : gphi *p = as_a <gphi *> (gsi_stmt (i));
69 : /* If the PHI arguments are equal then we can skip this PHI. */
70 4252688 : if (operand_equal_for_phi_arg_p (gimple_phi_arg_def (p, e0->dest_idx),
71 4252688 : gimple_phi_arg_def (p, e1->dest_idx)))
72 242822 : continue;
73 :
74 : /* Punt on virtual phis with different arguments from the edges. */
75 8019732 : 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 1706113 : 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 97293 : 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 97293 : basic_block bb = gimple_bb (phi);
98 97293 : gimple_stmt_iterator gsi;
99 97293 : tree phi_result = gimple_phi_result (phi);
100 97293 : 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 97293 : if (TREE_CODE (new_tree) == SSA_NAME
120 97270 : && EDGE_COUNT (gimple_bb (phi)->preds) == 2
121 63638 : && INTEGRAL_TYPE_P (TREE_TYPE (phi_result))
122 58515 : && !SSA_NAME_RANGE_INFO (new_tree)
123 58421 : && SSA_NAME_RANGE_INFO (phi_result)
124 36120 : && gimple_bb (SSA_NAME_DEF_STMT (new_tree)) == cond_block
125 133413 : && dbg_cnt (phiopt_edge_range))
126 36120 : duplicate_ssa_name_range_info (new_tree, phi_result);
127 :
128 : /* Change the PHI argument to new. */
129 97293 : SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);
130 :
131 : /* Remove the empty basic block. */
132 97293 : edge edge_to_remove = NULL, keep_edge = NULL;
133 97293 : if (EDGE_SUCC (cond_block, 0)->dest == bb)
134 : {
135 33715 : edge_to_remove = EDGE_SUCC (cond_block, 1);
136 33715 : keep_edge = EDGE_SUCC (cond_block, 0);
137 : }
138 63578 : 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 1227 : else if ((keep_edge = find_edge (cond_block, e->src)))
144 : {
145 1227 : basic_block bb1 = EDGE_SUCC (cond_block, 0)->dest;
146 1227 : basic_block bb2 = EDGE_SUCC (cond_block, 1)->dest;
147 2454 : if (single_pred_p (bb1) && single_pred_p (bb2)
148 99747 : && single_succ_p (bb1) && single_succ_p (bb2)
149 2454 : && 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 97293 : 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 97293 : if (edge_to_remove && EDGE_COUNT (edge_to_remove->dest->preds) == 1)
166 : {
167 84634 : e->flags |= EDGE_FALLTHRU;
168 84634 : e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
169 84634 : e->probability = profile_probability::always ();
170 84634 : delete_basic_block (edge_to_remove->dest);
171 :
172 : /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
173 84634 : gsi = gsi_last_bb (cond_block);
174 84634 : gsi_remove (&gsi, true);
175 : }
176 12659 : else if (deleteboth)
177 : {
178 1227 : basic_block bb1 = EDGE_SUCC (cond_block, 0)->dest;
179 1227 : basic_block bb2 = EDGE_SUCC (cond_block, 1)->dest;
180 :
181 1227 : edge newedge = redirect_edge_and_branch (keep_edge, bb);
182 :
183 : /* The new edge should be the same. */
184 1227 : gcc_assert (newedge == keep_edge);
185 :
186 1227 : keep_edge->flags |= EDGE_FALLTHRU;
187 1227 : keep_edge->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
188 1227 : keep_edge->probability = profile_probability::always ();
189 :
190 : /* Copy the edge's phi entry from the old one. */
191 1227 : copy_phi_arg_into_existing_phi (e, keep_edge);
192 :
193 : /* Delete the old 2 empty basic blocks */
194 1227 : delete_basic_block (bb1);
195 1227 : delete_basic_block (bb2);
196 :
197 : /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
198 1227 : gsi = gsi_last_bb (cond_block);
199 1227 : 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 22864 : gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_block));
207 11432 : if (keep_edge->flags & EDGE_FALSE_VALUE)
208 7584 : gimple_cond_make_false (cond);
209 3848 : else if (keep_edge->flags & EDGE_TRUE_VALUE)
210 3848 : gimple_cond_make_true (cond);
211 : }
212 :
213 97293 : if (dce_ssa_names)
214 95619 : simple_dce_from_worklist (dce_ssa_names);
215 :
216 97293 : statistics_counter_event (cfun, "Replace PHI with variable", 1);
217 :
218 97293 : if (dump_file && (dump_flags & TDF_DETAILS))
219 17 : 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 97293 : }
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 65465 : is_factor_profitable (gimple *def_stmt, basic_block merge, tree *operands, unsigned opcount)
230 : {
231 : /* The defining statement should be conditional. */
232 65465 : if (dominated_by_p (CDI_DOMINATORS, merge,
233 65465 : 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 62017 : gimple_stmt_iterator gsi = gsi_for_stmt (def_stmt);
239 62017 : gsi_next_nondebug (&gsi);
240 :
241 : /* Skip past nops and predicates. */
242 124522 : while (!gsi_end_p (gsi)
243 62505 : && (gimple_code (gsi_stmt (gsi)) == GIMPLE_NOP
244 8879 : || gimple_code (gsi_stmt (gsi)) == GIMPLE_PREDICT))
245 488 : 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 62017 : 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 8391 : int max_statements = param_phiopt_factor_max_stmts_live;
256 8391 : bool stmts_extending_ok = true;
257 :
258 24035 : while (!gsi_end_p (gsi))
259 : {
260 16541 : gimple *stmt = gsi_stmt (gsi);
261 16541 : auto gcode = gimple_code (stmt);
262 : /* Skip over NOPs and predicts. */
263 16555 : if (gcode == GIMPLE_NOP
264 16541 : || 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 16527 : if (gcode != GIMPLE_ASSIGN)
271 : {
272 : stmts_extending_ok = false;
273 : break;
274 : }
275 16246 : max_statements --;
276 16246 : if (max_statements == 0)
277 : {
278 : stmts_extending_ok = false;
279 : break;
280 : }
281 15630 : gsi_next_nondebug (&gsi);
282 : }
283 8391 : 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 3060407 : factor_out_conditional_operation (edge e0, edge e1, basic_block merge,
330 : gphi *phi, gimple *cond_stmt,
331 : bool early_p)
332 : {
333 3060407 : gimple *arg0_def_stmt = NULL, *arg1_def_stmt = NULL;
334 3060407 : tree temp, result;
335 3060407 : gphi *newphi;
336 3060407 : gimple_stmt_iterator gsi, gsi_for_def;
337 3060407 : location_t locus = gimple_location (phi);
338 3060407 : gimple_match_op arg0_op, arg1_op;
339 :
340 : /* We should only get here if the phi had two arguments. */
341 3060407 : gcc_assert (gimple_phi_num_args (phi) == 2);
342 :
343 : /* Virtual operands are never handled. */
344 6120814 : if (virtual_operand_p (gimple_phi_result (phi)))
345 : return false;
346 :
347 1331088 : tree arg0 = gimple_phi_arg_def (phi, e0->dest_idx);
348 1331088 : tree arg1 = gimple_phi_arg_def (phi, e1->dest_idx);
349 1331088 : location_t narg0_loc = gimple_location (phi);
350 1331088 : location_t narg1_loc = gimple_location (phi);
351 1331088 : if (gimple_phi_arg_location (phi, e0->dest_idx) != UNKNOWN_LOCATION)
352 1132267 : narg0_loc = gimple_phi_arg_location (phi, e0->dest_idx);
353 1331088 : if (gimple_phi_arg_location (phi, e1->dest_idx) != UNKNOWN_LOCATION)
354 932719 : narg1_loc = gimple_phi_arg_location (phi, e1->dest_idx);
355 :
356 1331088 : 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 1331088 : if (operand_equal_for_phi_arg_p (arg0, arg1))
361 : return false;
362 :
363 : /* First canonicalize to simplify tests. */
364 1330857 : if (TREE_CODE (arg0) != SSA_NAME)
365 : {
366 251528 : std::swap (arg0, arg1);
367 251528 : std::swap (e0, e1);
368 : }
369 :
370 1330857 : if (TREE_CODE (arg0) != SSA_NAME
371 1210324 : || (TREE_CODE (arg1) != SSA_NAME
372 498870 : && 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 1172779 : arg0_def_stmt = SSA_NAME_DEF_STMT (arg0);
378 1172779 : 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 602481 : if (arg0_op.operands_occurs_in_abnormal_phi ())
383 : return false;
384 :
385 602481 : tree new_arg0;
386 602481 : tree new_arg1;
387 602481 : int opnum = -1;
388 :
389 : /* If arg0 have > 1 use, then this transformation actually increases
390 : the number of expressions evaluated at runtime. */
391 602481 : if (!has_single_use (arg0))
392 : return false;
393 492074 : if (gimple_has_location (arg0_def_stmt))
394 454229 : narg0_loc = gimple_location (arg0_def_stmt);
395 :
396 492074 : if (TREE_CODE (arg1) == SSA_NAME)
397 : {
398 : /* Check if arg1 is an SSA_NAME. */
399 316961 : arg1_def_stmt = SSA_NAME_DEF_STMT (arg1);
400 316961 : if (!gimple_extract_op (arg1_def_stmt, &arg1_op))
401 : return false;
402 159217 : if (arg1_op.code != arg0_op.code)
403 : return false;
404 41911 : if (arg1_op.num_ops != arg0_op.num_ops)
405 : return false;
406 41895 : 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 41895 : 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 41780 : if (!has_single_use (arg1))
418 : return false;
419 :
420 29265 : opnum = find_different_opnum (arg0_op, arg1_op, &new_arg0, &new_arg1);
421 29265 : if (opnum == -1)
422 : return false;
423 :
424 : /* Check to make sure extending the lifetimes of all operands is ok. */
425 12577 : if (!is_factor_profitable (arg0_def_stmt, merge,
426 : arg0_op.ops, arg0_op.num_ops))
427 : return false;
428 11638 : 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 9342 : 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 4384 : if (early_p && arg1_op.code == POINTER_PLUS_EXPR
446 166 : && opnum == 1
447 153 : && TREE_CODE (new_arg0) != SSA_NAME
448 9320 : && 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 9281 : if ((arg1_op.code == BIT_FIELD_REF
454 9251 : || arg1_op.code == BIT_INSERT_EXPR)
455 9348 : && 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 9203 : if (arg1_op.code == VEC_PERM_EXPR && opnum == 2
468 103 : && TREE_CODE (new_arg0) == VECTOR_CST
469 9306 : && TREE_CODE (new_arg1) == VECTOR_CST)
470 : return false;
471 :
472 9119 : if (gimple_has_location (arg1_def_stmt))
473 8893 : narg1_loc = gimple_location (arg1_def_stmt);
474 :
475 : /* Chose the location for the new statement if the phi location is unknown. */
476 9119 : if (locus == UNKNOWN_LOCATION)
477 : {
478 9119 : if (narg0_loc == UNKNOWN_LOCATION
479 9119 : && narg1_loc != UNKNOWN_LOCATION)
480 : locus = narg1_loc;
481 9119 : else if (narg0_loc != UNKNOWN_LOCATION
482 9119 : && narg1_loc == UNKNOWN_LOCATION)
483 51 : locus = narg0_loc;
484 : }
485 : }
486 175113 : else if (arg0_op.num_ops != 1)
487 : return false;
488 : else
489 : {
490 51200 : new_arg0 = arg0_op.ops[0];
491 51200 : opnum = 0;
492 : /* For constants only handle if the phi was the only one. */
493 51200 : 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 38583 : if (!gimple_assign_cast_p (arg0_def_stmt))
497 : return false;
498 31970 : 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 62389 : if (!INTEGRAL_TYPE_P (TREE_TYPE (new_arg0))
505 62122 : || !(int_fits_type_p (arg1, TREE_TYPE (new_arg0))
506 1698 : || (TYPE_PRECISION (TREE_TYPE (new_arg0))
507 1698 : == TYPE_PRECISION (TREE_TYPE (arg1))
508 806 : && (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 30042 : if ((TYPE_PRECISION (TREE_TYPE (new_arg0))
524 30042 : != TYPE_PRECISION (TREE_TYPE (arg1)))
525 14408 : && new_arg0 != gimple_cond_lhs (cond_stmt)
526 13714 : && new_arg0 != gimple_cond_rhs (cond_stmt)
527 43750 : && gimple_bb (arg0_def_stmt) == e0->src)
528 : {
529 13708 : gsi = gsi_for_stmt (arg0_def_stmt);
530 13708 : gsi_prev_nondebug (&gsi);
531 : /* Ignore nops, predicates and labels. */
532 27428 : while (!gsi_end_p (gsi)
533 13720 : && (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 13708 : if (!gsi_end_p (gsi))
539 : {
540 10316 : gimple *stmt = gsi_stmt (gsi);
541 3042183 : if (gassign *assign = dyn_cast <gassign *> (stmt))
542 : {
543 9721 : tree lhs = gimple_assign_lhs (assign);
544 9721 : tree lhst = TREE_TYPE (lhs);
545 9721 : enum tree_code ass_code
546 9721 : = gimple_assign_rhs_code (assign);
547 9721 : 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 9721 : && !(INTEGRAL_TYPE_P (lhst)
553 9265 : && TYPE_UNSIGNED (lhst)
554 6960 : && TYPE_PRECISION (lhst) == 1))
555 : return false;
556 4776 : if (lhs != gimple_assign_rhs1 (arg0_def_stmt))
557 : return false;
558 4734 : gsi_prev_nondebug (&gsi);
559 4734 : if (!gsi_end_p (gsi))
560 : return false;
561 : }
562 : else
563 : return false;
564 : }
565 : }
566 20035 : new_arg1 = fold_convert (TREE_TYPE (new_arg0), arg1);
567 :
568 : /* Drop the overflow that fold_convert might add. */
569 20035 : 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 20035 : if (gimple_has_location (arg0_def_stmt))
574 19584 : locus = gimple_location (arg0_def_stmt);
575 : }
576 :
577 : /* If types of new_arg0 and new_arg1 are different bailout. */
578 29154 : if (!types_compatible_p (TREE_TYPE (new_arg0), TREE_TYPE (new_arg1)))
579 : return false;
580 :
581 : /* Create a new PHI stmt. */
582 28201 : result = gimple_phi_result (phi);
583 28201 : temp = make_ssa_name (TREE_TYPE (new_arg0), NULL);
584 :
585 28201 : gimple_match_op new_op = arg0_op;
586 :
587 : /* Create the operation stmt if possible and insert it. */
588 28201 : new_op.ops[opnum] = temp;
589 28201 : gimple_seq seq = NULL;
590 28201 : 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 28201 : if (!result)
595 : {
596 256 : release_ssa_name (temp);
597 256 : return false;
598 : }
599 :
600 27945 : if (locus != UNKNOWN_LOCATION)
601 19631 : annotate_all_with_location (seq, locus);
602 27945 : gsi = gsi_after_labels (gimple_bb (phi));
603 27945 : gsi_insert_seq_before (&gsi, seq, GSI_CONTINUE_LINKING);
604 :
605 27945 : newphi = create_phi_node (temp, gimple_bb (phi));
606 :
607 27945 : if (dump_file && (dump_flags & TDF_DETAILS))
608 : {
609 31 : fprintf (dump_file, "PHI ");
610 31 : print_generic_expr (dump_file, gimple_phi_result (phi));
611 31 : fprintf (dump_file,
612 : " changed to factor operation out from COND_EXPR.\n");
613 31 : fprintf (dump_file, "New stmt with OPERATION that defines ");
614 31 : print_generic_expr (dump_file, result);
615 31 : fprintf (dump_file, ".\n");
616 : }
617 :
618 : /* Remove the old operation(s) that has single use. */
619 27945 : gsi_for_def = gsi_for_stmt (arg0_def_stmt);
620 27945 : gsi_remove (&gsi_for_def, true);
621 27945 : release_defs (arg0_def_stmt);
622 :
623 27945 : if (arg1_def_stmt)
624 : {
625 7910 : gsi_for_def = gsi_for_stmt (arg1_def_stmt);
626 7910 : gsi_remove (&gsi_for_def, true);
627 7910 : release_defs (arg1_def_stmt);
628 : }
629 :
630 27945 : add_phi_arg (newphi, new_arg0, e0, narg0_loc);
631 27945 : add_phi_arg (newphi, new_arg1, e1, narg1_loc);
632 :
633 : /* Remove the original PHI stmt. */
634 27945 : gsi = gsi_for_stmt (phi);
635 27945 : remove_phi_node (&gsi, false);
636 :
637 27945 : statistics_counter_event (cfun, "factored out operation", 1);
638 :
639 27945 : 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 179571 : phiopt_early_allow (gimple_seq &seq, gimple_match_op &op)
647 : {
648 : /* Don't allow functions. */
649 179571 : if (!op.code.is_tree_code ())
650 : return false;
651 179519 : 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 179519 : if (!gimple_seq_empty_p (seq))
656 : {
657 148093 : if (code == MIN_EXPR || code == MAX_EXPR)
658 : {
659 151091 : if (!gimple_seq_singleton_p (seq))
660 : return false;
661 :
662 1 : gimple *stmt = gimple_seq_first_stmt (seq);
663 : /* Only allow assignments. */
664 1 : if (!is_gimple_assign (stmt))
665 : return false;
666 1 : code = gimple_assign_rhs_code (stmt);
667 1 : return code == MIN_EXPR || code == MAX_EXPR;
668 : }
669 : return false;
670 : }
671 :
672 31426 : 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 545166 : gimple_simplify_phiopt (bool early_p, tree type, gimple *comp_stmt,
700 : tree arg0, tree arg1,
701 : gimple_seq *seq)
702 : {
703 545166 : gimple_seq seq1 = NULL;
704 545166 : enum tree_code comp_code = gimple_cond_code (comp_stmt);
705 545166 : location_t loc = gimple_location (comp_stmt);
706 545166 : tree cmp0 = gimple_cond_lhs (comp_stmt);
707 545166 : 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 545166 : tree cond = build2_loc (loc, comp_code, boolean_type_node,
714 : cmp0, cmp1);
715 :
716 545166 : 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 545166 : gimple_match_op op (gimple_match_cond::UNCOND,
728 545166 : COND_EXPR, type, cond, arg0, arg1);
729 :
730 545166 : if (op.resimplify (&seq1, follow_all_ssa_edges))
731 : {
732 162927 : bool allowed = !early_p || phiopt_early_allow (seq1, op);
733 162927 : tree result = maybe_push_res_to_seq (&op, &seq1);
734 162927 : 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 162927 : if (allowed && result)
750 : {
751 86258 : if (loc != UNKNOWN_LOCATION)
752 85789 : annotate_all_with_location (seq1, loc);
753 86258 : gimple_seq_add_seq_without_update (seq, seq1);
754 86258 : return result;
755 : }
756 : }
757 458908 : gimple_seq_discard (seq1);
758 458908 : seq1 = NULL;
759 :
760 : /* Try the inverted comparison, that is !COMP ? ARG1 : ARG0. */
761 458908 : comp_code = invert_tree_comparison (comp_code, HONOR_NANS (cmp0));
762 :
763 458908 : if (comp_code == ERROR_MARK)
764 : return NULL;
765 :
766 442783 : cond = build2_loc (loc,
767 : comp_code, boolean_type_node,
768 : cmp0, cmp1);
769 :
770 442783 : 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 442783 : gimple_match_op op1 (gimple_match_cond::UNCOND,
782 442783 : COND_EXPR, type, cond, arg1, arg0);
783 :
784 442783 : if (op1.resimplify (&seq1, follow_all_ssa_edges))
785 : {
786 79809 : bool allowed = !early_p || phiopt_early_allow (seq1, op1);
787 79809 : tree result = maybe_push_res_to_seq (&op1, &seq1);
788 79809 : 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 79809 : if (allowed && result)
804 : {
805 5346 : if (loc != UNKNOWN_LOCATION)
806 5346 : annotate_all_with_location (seq1, loc);
807 5346 : gimple_seq_add_seq_without_update (seq, seq1);
808 5346 : return result;
809 : }
810 : }
811 437437 : gimple_seq_discard (seq1);
812 :
813 437437 : return NULL;
814 : }
815 :
816 : /* empty_bb_or_one_feeding_into_p returns true if bb was empty basic block
817 : or it has one cheap preparation statement that feeds into the PHI
818 : statement and it sets STMT to that statement. */
819 : static bool
820 893627 : empty_bb_or_one_feeding_into_p (basic_block bb,
821 : gimple *phi,
822 : gimple *&stmt)
823 : {
824 893627 : stmt = nullptr;
825 893627 : gimple *stmt_to_move = nullptr;
826 893627 : tree lhs;
827 :
828 893627 : if (empty_block_p (bb))
829 : return true;
830 :
831 777948 : if (!single_pred_p (bb))
832 : return false;
833 :
834 : /* The middle bb cannot have phi nodes as we don't
835 : move those assignments yet. */
836 463294 : if (!gimple_seq_empty_p (phi_nodes (bb)))
837 : return false;
838 :
839 463274 : gimple_stmt_iterator gsi;
840 :
841 463274 : gsi = gsi_start_nondebug_after_labels_bb (bb);
842 929600 : while (!gsi_end_p (gsi))
843 : {
844 679845 : gimple *s = gsi_stmt (gsi);
845 679845 : gsi_next_nondebug (&gsi);
846 : /* Skip over Predict and nop statements. */
847 679845 : if (gimple_code (s) == GIMPLE_PREDICT
848 679845 : || gimple_code (s) == GIMPLE_NOP)
849 3052 : continue;
850 : /* If there is more one statement return false. */
851 676793 : if (stmt_to_move)
852 : return false;
853 : stmt_to_move = s;
854 : }
855 :
856 : /* The only statement here was a Predict or a nop statement
857 : so return true. */
858 249755 : if (!stmt_to_move)
859 : return true;
860 :
861 499510 : if (gimple_vuse (stmt_to_move))
862 : return false;
863 :
864 169073 : if (gimple_could_trap_p (stmt_to_move)
865 169073 : || gimple_has_side_effects (stmt_to_move))
866 5403 : return false;
867 :
868 163670 : ssa_op_iter it;
869 163670 : tree use;
870 361513 : FOR_EACH_SSA_TREE_OPERAND (use, stmt_to_move, it, SSA_OP_USE)
871 198503 : if (ssa_name_maybe_undef_p (use))
872 : return false;
873 :
874 : /* Allow assignments but allow some builtin/internal calls.
875 : As const calls don't match any of the above, yet they could
876 : still have some side-effects - they could contain
877 : gimple_could_trap_p statements, like floating point
878 : exceptions or integer division by zero. See PR70586.
879 : FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
880 : should handle this.
881 : Allow some known builtin/internal calls that are known not to
882 : trap: logical functions (e.g. bswap and bit counting). */
883 163010 : if (!is_gimple_assign (stmt_to_move))
884 : {
885 5939 : if (!is_gimple_call (stmt_to_move))
886 : return false;
887 5688 : combined_fn cfn = gimple_call_combined_fn (stmt_to_move);
888 5688 : switch (cfn)
889 : {
890 : default:
891 : return false;
892 4774 : CASE_CFN_BSWAP:
893 4774 : CASE_CFN_BITREVERSE:
894 4774 : CASE_CFN_FFS:
895 4774 : CASE_CFN_PARITY:
896 4774 : CASE_CFN_POPCOUNT:
897 4774 : CASE_CFN_CLZ:
898 4774 : CASE_CFN_CTZ:
899 4774 : case CFN_BUILT_IN_CLRSB:
900 4774 : case CFN_BUILT_IN_CLRSBL:
901 4774 : case CFN_BUILT_IN_CLRSBLL:
902 4774 : lhs = gimple_call_lhs (stmt_to_move);
903 4774 : break;
904 : }
905 : }
906 : else
907 157071 : lhs = gimple_assign_lhs (stmt_to_move);
908 :
909 161845 : gimple *use_stmt;
910 161845 : use_operand_p use_p;
911 :
912 : /* Allow only a statement which feeds into the other stmt. */
913 161845 : if (!lhs || TREE_CODE (lhs) != SSA_NAME
914 161845 : || !single_imm_use (lhs, &use_p, &use_stmt)
915 323685 : || use_stmt != phi)
916 5 : return false;
917 :
918 161840 : stmt = stmt_to_move;
919 161840 : return true;
920 : }
921 :
922 : /* Move STMT to before GSI and insert its defining
923 : name into INSERTED_EXPRS bitmap.
924 : Also rewrite its if it might be undefined when unconditionalized. */
925 : static void
926 191238 : move_stmt (gimple *stmt, gimple_stmt_iterator *gsi, auto_bitmap &inserted_exprs)
927 : {
928 191238 : if (!stmt)
929 185141 : return;
930 6097 : if (dump_file && (dump_flags & TDF_DETAILS))
931 : {
932 7 : fprintf (dump_file, "statement un-sinked:\n");
933 7 : print_gimple_stmt (dump_file, stmt, 0,
934 : TDF_VOPS|TDF_MEMSYMS);
935 : }
936 :
937 6097 : tree name = gimple_get_lhs (stmt);
938 : // Mark the name to be renamed if there is one.
939 6097 : bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (name));
940 6097 : gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt);
941 6097 : gsi_move_before (&gsi1, gsi, GSI_NEW_STMT);
942 6097 : reset_flow_sensitive_info (name);
943 :
944 : /* Rewrite some code which might be undefined when
945 : unconditionalized. */
946 6097 : if (gimple_needing_rewrite_undefined (stmt))
947 1077 : rewrite_to_defined_unconditional (gsi);
948 : }
949 :
950 : /* RAII style class to temporarily remove flow sensitive
951 : from ssa names defined by a gimple statement. */
952 : class auto_flow_sensitive
953 : {
954 : public:
955 : auto_flow_sensitive (gimple *s);
956 : ~auto_flow_sensitive ();
957 : private:
958 : auto_vec<std::pair<tree, flow_sensitive_info_storage>, 2> stack;
959 : };
960 :
961 : /* Constructor for auto_flow_sensitive. Saves
962 : off the ssa names' flow sensitive information
963 : that was defined by gimple statement S and
964 : resets it to be non-flow based ones. */
965 :
966 1090332 : auto_flow_sensitive::auto_flow_sensitive (gimple *s)
967 : {
968 1090332 : if (!s)
969 935172 : return;
970 155160 : ssa_op_iter it;
971 155160 : tree def;
972 310320 : FOR_EACH_SSA_TREE_OPERAND (def, s, it, SSA_OP_DEF)
973 : {
974 155160 : flow_sensitive_info_storage storage;
975 155160 : storage.save_and_clear (def);
976 155160 : stack.safe_push (std::make_pair (def, storage));
977 : }
978 : }
979 :
980 : /* Deconstructor, restores the flow sensitive information
981 : for the SSA names that had been saved off. */
982 :
983 1090332 : auto_flow_sensitive::~auto_flow_sensitive ()
984 : {
985 3426156 : for (auto p : stack)
986 155160 : p.second.restore (p.first);
987 1090332 : }
988 :
989 : /* Returns true if BB contains an user provided predictor
990 : (PRED_HOT_LABEL/PRED_COLD_LABEL). */
991 :
992 : static bool
993 6361 : contains_hot_cold_predict (basic_block bb)
994 : {
995 6361 : gimple_stmt_iterator gsi;
996 6361 : gsi = gsi_start_nondebug_after_labels_bb (bb);
997 8903 : for (; !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
998 : {
999 2543 : gimple *s = gsi_stmt (gsi);
1000 2543 : if (gimple_code (s) != GIMPLE_PREDICT)
1001 2 : continue;
1002 2541 : auto predict = gimple_predict_predictor (s);
1003 2541 : if (predict == PRED_HOT_LABEL
1004 2541 : || predict == PRED_COLD_LABEL)
1005 : return true;
1006 : }
1007 : return false;
1008 : }
1009 :
1010 : /* The function match_simplify_replacement does the main work of doing the
1011 : replacement using match and simplify. Return true if the replacement is done.
1012 : Otherwise return false.
1013 : BB is the basic block where the replacement is going to be done on. ARG0
1014 : is argument 0 from PHI. Likewise for ARG1. */
1015 :
1016 : static bool
1017 864414 : match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
1018 : basic_block middle_bb_alt,
1019 : edge e0, edge e1, gphi *phi,
1020 : tree arg0, tree arg1, bool early_p,
1021 : bool threeway_p)
1022 : {
1023 864414 : gimple *stmt;
1024 864414 : gimple_stmt_iterator gsi;
1025 864414 : edge true_edge, false_edge;
1026 864414 : gimple_seq seq = NULL;
1027 864414 : tree result;
1028 864414 : gimple *stmt_to_move = NULL;
1029 864414 : gimple *stmt_to_move_alt = NULL;
1030 864414 : tree arg_true, arg_false;
1031 :
1032 : /* Special case A ? B : B as this will always simplify to B. */
1033 864414 : if (operand_equal_for_phi_arg_p (arg0, arg1))
1034 : return false;
1035 :
1036 : /* If the basic block only has a cheap preparation statement,
1037 : allow it and move it once the transformation is done. */
1038 864414 : if (!empty_bb_or_one_feeding_into_p (middle_bb, phi, stmt_to_move))
1039 : return false;
1040 :
1041 561492 : if (threeway_p
1042 561492 : && middle_bb != middle_bb_alt
1043 561492 : && !empty_bb_or_one_feeding_into_p (middle_bb_alt, phi,
1044 : stmt_to_move_alt))
1045 : return false;
1046 :
1047 : /* Do not make conditional undefs unconditional. */
1048 549760 : if ((TREE_CODE (arg0) == SSA_NAME
1049 290326 : && ssa_name_maybe_undef_p (arg0))
1050 839736 : || (TREE_CODE (arg1) == SSA_NAME
1051 241256 : && ssa_name_maybe_undef_p (arg1)))
1052 : return false;
1053 :
1054 : /* At this point we know we have a GIMPLE_COND with two successors.
1055 : One successor is BB, the other successor is an empty block which
1056 : falls through into BB.
1057 :
1058 : There is a single PHI node at the join point (BB).
1059 :
1060 : So, given the condition COND, and the two PHI arguments, match and simplify
1061 : can happen on (COND) ? arg0 : arg1. */
1062 :
1063 545166 : stmt = last_nondebug_stmt (cond_bb);
1064 :
1065 : /* We need to know which is the true edge and which is the false
1066 : edge so that we know when to invert the condition below. */
1067 545166 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1068 :
1069 : /* Forward the edges over the middle basic block. */
1070 545166 : if (true_edge->dest == middle_bb)
1071 351324 : true_edge = EDGE_SUCC (true_edge->dest, 0);
1072 545166 : if (false_edge->dest == middle_bb)
1073 193842 : false_edge = EDGE_SUCC (false_edge->dest, 0);
1074 :
1075 : /* When THREEWAY_P then e1 will point to the edge of the final transition
1076 : from middle-bb to end. */
1077 545166 : if (true_edge == e0)
1078 : {
1079 351324 : if (!threeway_p)
1080 334346 : gcc_assert (false_edge == e1);
1081 : arg_true = arg0;
1082 : arg_false = arg1;
1083 : }
1084 : else
1085 : {
1086 193842 : gcc_assert (false_edge == e0);
1087 193842 : if (!threeway_p)
1088 193459 : gcc_assert (true_edge == e1);
1089 : arg_true = arg1;
1090 : arg_false = arg0;
1091 : }
1092 :
1093 545166 : tree type = TREE_TYPE (gimple_phi_result (phi));
1094 545166 : {
1095 545166 : auto_flow_sensitive s1(stmt_to_move);
1096 545166 : auto_flow_sensitive s_alt(stmt_to_move_alt);
1097 :
1098 545166 : result = gimple_simplify_phiopt (early_p, type, stmt,
1099 : arg_true, arg_false,
1100 : &seq);
1101 545166 : }
1102 :
1103 : /* For early phiopt, we don't want to lose user generated predictors
1104 : if the phiopt is converting `if (a)` into `a` as that might
1105 : be jump threaded later on so we want to keep around the
1106 : predictors. */
1107 545166 : if (early_p && result && TREE_CODE (result) == SSA_NAME)
1108 : {
1109 28474 : bool check_it = false;
1110 28474 : tree cmp0 = gimple_cond_lhs (stmt);
1111 28474 : tree cmp1 = gimple_cond_rhs (stmt);
1112 28474 : if (result == cmp0 || result == cmp1)
1113 : check_it = true;
1114 22499 : else if (gimple_seq_singleton_p (seq))
1115 : {
1116 22384 : gimple *stmt = gimple_seq_first_stmt (seq);
1117 22384 : if (is_gimple_assign (stmt)
1118 22384 : && result == gimple_assign_lhs (stmt)
1119 44768 : && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
1120 : == tcc_comparison)
1121 : check_it = true;
1122 : }
1123 : if (!check_it)
1124 : ;
1125 5975 : else if (contains_hot_cold_predict (middle_bb))
1126 : return false;
1127 5974 : else if (threeway_p
1128 : && middle_bb != middle_bb_alt
1129 5974 : && contains_hot_cold_predict (middle_bb_alt))
1130 : return false;
1131 : }
1132 :
1133 545158 : if (!result)
1134 : {
1135 : /* If we don't get back a MIN/MAX_EXPR still make sure the expression
1136 : stays in a form to be recognized by ISA that map to IEEE x > y ? x : y
1137 : semantics (that's not IEEE max semantics). */
1138 453562 : if (!HONOR_NANS (type) && !HONOR_SIGNED_ZEROS (type))
1139 : return false;
1140 17126 : if (stmt_to_move || stmt_to_move_alt)
1141 : return false;
1142 14221 : tree_code cmp = gimple_cond_code (stmt);
1143 14221 : if (cmp != LT_EXPR && cmp != LE_EXPR
1144 14221 : && cmp != GT_EXPR && cmp != GE_EXPR)
1145 : return false;
1146 6858 : tree lhs = gimple_cond_lhs (stmt);
1147 6858 : tree rhs = gimple_cond_rhs (stmt);
1148 : /* `lhs CMP rhs ? lhs : rhs` or `lhs CMP rhs ? rhs : lhs`
1149 : are only acceptable case here. */
1150 6858 : if ((!operand_equal_for_phi_arg_p (lhs, arg_false)
1151 2607 : || !operand_equal_for_phi_arg_p (rhs, arg_true))
1152 6918 : && (!operand_equal_for_phi_arg_p (rhs, arg_false)
1153 1631 : || !operand_equal_for_phi_arg_p (lhs, arg_true)))
1154 2842 : return false;
1155 4016 : seq = nullptr;
1156 4016 : result = gimple_build (&seq, cmp, boolean_type_node, lhs, rhs);
1157 4016 : result = gimple_build (&seq, COND_EXPR, type, result,
1158 : arg_true, arg_false);
1159 4016 : statistics_counter_event (cfun, "Non-IEEE FP MIN/MAX PHI replacement",
1160 : 1);
1161 : }
1162 95619 : if (dump_file && (dump_flags & TDF_FOLDING))
1163 1 : fprintf (dump_file, "accepted the phiopt match-simplify.\n");
1164 :
1165 95619 : auto_bitmap exprs_maybe_dce;
1166 :
1167 : /* Mark the cond statements' lhs/rhs as maybe dce. */
1168 95619 : if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
1169 95619 : && !SSA_NAME_IS_DEFAULT_DEF (gimple_cond_lhs (stmt)))
1170 90218 : bitmap_set_bit (exprs_maybe_dce,
1171 90218 : SSA_NAME_VERSION (gimple_cond_lhs (stmt)));
1172 95619 : if (TREE_CODE (gimple_cond_rhs (stmt)) == SSA_NAME
1173 95619 : && !SSA_NAME_IS_DEFAULT_DEF (gimple_cond_rhs (stmt)))
1174 28413 : bitmap_set_bit (exprs_maybe_dce,
1175 28413 : SSA_NAME_VERSION (gimple_cond_rhs (stmt)));
1176 :
1177 95619 : gsi = gsi_last_bb (cond_bb);
1178 : /* Insert the sequence generated from gimple_simplify_phiopt. */
1179 95619 : if (seq)
1180 : {
1181 : // Mark the lhs of the new statements maybe for dce
1182 87741 : mark_lhs_in_seq_for_dce (exprs_maybe_dce, seq);
1183 87741 : gsi_insert_seq_before (&gsi, seq, GSI_CONTINUE_LINKING);
1184 : }
1185 :
1186 : /* If there was a statement to move, move it to right before
1187 : the original conditional. */
1188 95619 : move_stmt (stmt_to_move, &gsi, exprs_maybe_dce);
1189 95619 : move_stmt (stmt_to_move_alt, &gsi, exprs_maybe_dce);
1190 :
1191 95619 : replace_phi_edge_with_variable (cond_bb, e1, phi, result, exprs_maybe_dce);
1192 :
1193 : /* Add Statistic here even though replace_phi_edge_with_variable already
1194 : does it as we want to be able to count when match-simplify happens vs
1195 : the others. */
1196 95619 : statistics_counter_event (cfun, "match-simplify PHI replacement", 1);
1197 :
1198 : /* Note that we optimized this PHI. */
1199 95619 : return true;
1200 95619 : }
1201 :
1202 : /* Update *ARG which is defined in STMT so that it contains the
1203 : computed value if that seems profitable. Return true if the
1204 : statement is made dead by that rewriting. */
1205 :
1206 : static bool
1207 336907 : jump_function_from_stmt (tree *arg, gimple *stmt)
1208 : {
1209 336907 : enum tree_code code = gimple_assign_rhs_code (stmt);
1210 336907 : if (code == ADDR_EXPR)
1211 : {
1212 : /* For arg = &p->i transform it to p, if possible. */
1213 4887 : tree rhs1 = gimple_assign_rhs1 (stmt);
1214 4887 : poly_int64 offset;
1215 4887 : tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs1, 0),
1216 : &offset);
1217 4887 : if (tem
1218 4806 : && TREE_CODE (tem) == MEM_REF
1219 9693 : && known_eq (mem_ref_offset (tem) + offset, 0))
1220 : {
1221 2140 : *arg = TREE_OPERAND (tem, 0);
1222 2140 : return true;
1223 : }
1224 : }
1225 : /* TODO: Much like IPA-CP jump-functions we want to handle constant
1226 : additions symbolically here, and we'd need to update the comparison
1227 : code that compares the arg + cst tuples in our caller. For now the
1228 : code above exactly handles the VEC_BASE pattern from vec.h. */
1229 : return false;
1230 : }
1231 :
1232 : /* RHS is a source argument in a BIT_AND_EXPR or BIT_IOR_EXPR which feeds
1233 : a conditional of the form SSA_NAME NE 0.
1234 :
1235 : If RHS is fed by a simple EQ_EXPR or NE_EXPR comparison of two values,
1236 : see if the two input values of the comparison match arg0 and arg1.
1237 :
1238 : If so update *code and return TRUE. Otherwise return FALSE. */
1239 :
1240 : static bool
1241 160287 : rhs_is_fed_for_value_replacement (const_tree arg0, const_tree arg1,
1242 : enum tree_code *code, const_tree rhs,
1243 : enum tree_code bit_expression_code)
1244 : {
1245 : /* Obviously if RHS is not an SSA_NAME, we can't look at the defining
1246 : statement. */
1247 160287 : if (TREE_CODE (rhs) == SSA_NAME)
1248 : {
1249 125760 : gimple *def1 = SSA_NAME_DEF_STMT (rhs);
1250 :
1251 : /* Verify the defining statement has an EQ_EXPR or NE_EXPR on the RHS. */
1252 125760 : if (is_gimple_assign (def1)
1253 125760 : && ((bit_expression_code == BIT_AND_EXPR
1254 76796 : && gimple_assign_rhs_code (def1) == EQ_EXPR)
1255 94295 : || (bit_expression_code == BIT_IOR_EXPR
1256 38976 : && gimple_assign_rhs_code (def1) == NE_EXPR)))
1257 : {
1258 : /* Finally verify the source operands of the EQ_EXPR or NE_EXPR
1259 : are equal to arg0 and arg1. */
1260 26589 : tree op0 = gimple_assign_rhs1 (def1);
1261 26589 : tree op1 = gimple_assign_rhs2 (def1);
1262 26589 : if ((operand_equal_for_phi_arg_p (arg0, op0)
1263 650 : && operand_equal_for_phi_arg_p (arg1, op1))
1264 27194 : || (operand_equal_for_phi_arg_p (arg0, op1)
1265 635 : && operand_equal_for_phi_arg_p (arg1, op0)))
1266 : {
1267 : /* We will perform the optimization. */
1268 455 : *code = gimple_assign_rhs_code (def1);
1269 455 : return true;
1270 : }
1271 : }
1272 : }
1273 : return false;
1274 : }
1275 :
1276 : /* Return TRUE if arg0/arg1 are equal to the rhs/lhs or lhs/rhs of COND.
1277 :
1278 : Also return TRUE if arg0/arg1 are equal to the source arguments of an
1279 : EQ comparison feeding a BIT_AND_EXPR, or NE comparison feeding a
1280 : BIT_IOR_EXPR which feeds COND.
1281 :
1282 : Return FALSE otherwise. */
1283 :
1284 : static bool
1285 673710 : operand_equal_for_value_replacement (const_tree arg0, const_tree arg1,
1286 : enum tree_code *code, gimple *cond)
1287 : {
1288 673710 : gimple *def;
1289 673710 : tree lhs = gimple_cond_lhs (cond);
1290 673710 : tree rhs = gimple_cond_rhs (cond);
1291 :
1292 673710 : if ((operand_equal_for_phi_arg_p (arg0, lhs)
1293 28682 : && operand_equal_for_phi_arg_p (arg1, rhs))
1294 693414 : || (operand_equal_for_phi_arg_p (arg1, lhs)
1295 44713 : && operand_equal_for_phi_arg_p (arg0, rhs)))
1296 12866 : return true;
1297 :
1298 : /* Now handle more complex case where we have an EQ comparison
1299 : feeding a BIT_AND_EXPR, or a NE comparison feeding a BIT_IOR_EXPR,
1300 : which then feeds into COND.
1301 :
1302 : First verify that COND is of the form SSA_NAME NE 0. */
1303 382572 : if (*code != NE_EXPR || !integer_zerop (rhs)
1304 936879 : || TREE_CODE (lhs) != SSA_NAME)
1305 385210 : return false;
1306 :
1307 : /* Now ensure that SSA_NAME is set by a BIT_AND_EXPR or BIT_OR_EXPR. */
1308 275634 : def = SSA_NAME_DEF_STMT (lhs);
1309 275634 : if (!is_gimple_assign (def)
1310 275634 : || (gimple_assign_rhs_code (def) != BIT_AND_EXPR
1311 133141 : && gimple_assign_rhs_code (def) != BIT_IOR_EXPR))
1312 : return false;
1313 :
1314 : /* Now verify arg0/arg1 correspond to the source arguments of an EQ
1315 : comparison feeding the BIT_AND_EXPR or a NE comparison feeding the
1316 : BIT_IOR_EXPR. */
1317 :
1318 80301 : tree tmp = gimple_assign_rhs1 (def);
1319 80301 : if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp,
1320 : gimple_assign_rhs_code (def)))
1321 : return true;
1322 :
1323 79986 : tmp = gimple_assign_rhs2 (def);
1324 79986 : if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp,
1325 : gimple_assign_rhs_code (def)))
1326 : return true;
1327 :
1328 : return false;
1329 : }
1330 :
1331 : /* Returns true if ARG is a neutral element for operation CODE
1332 : on the RIGHT side. */
1333 :
1334 : static bool
1335 1043 : neutral_element_p (tree_code code, tree arg, bool right)
1336 : {
1337 1043 : switch (code)
1338 : {
1339 41 : case PLUS_EXPR:
1340 41 : case BIT_IOR_EXPR:
1341 41 : case BIT_XOR_EXPR:
1342 41 : return integer_zerop (arg);
1343 :
1344 193 : case LROTATE_EXPR:
1345 193 : case RROTATE_EXPR:
1346 193 : case LSHIFT_EXPR:
1347 193 : case RSHIFT_EXPR:
1348 193 : case MINUS_EXPR:
1349 193 : case POINTER_PLUS_EXPR:
1350 193 : return right && integer_zerop (arg);
1351 :
1352 679 : case MULT_EXPR:
1353 679 : return integer_onep (arg);
1354 :
1355 31 : case TRUNC_DIV_EXPR:
1356 31 : case CEIL_DIV_EXPR:
1357 31 : case FLOOR_DIV_EXPR:
1358 31 : case ROUND_DIV_EXPR:
1359 31 : case EXACT_DIV_EXPR:
1360 31 : return right && integer_onep (arg);
1361 :
1362 0 : case BIT_AND_EXPR:
1363 0 : return integer_all_onesp (arg);
1364 :
1365 : default:
1366 : return false;
1367 : }
1368 : }
1369 :
1370 : /* Returns true if ARG is an absorbing element for operation CODE. */
1371 :
1372 : static bool
1373 879 : absorbing_element_p (tree_code code, tree arg, bool right, tree rval)
1374 : {
1375 879 : switch (code)
1376 : {
1377 18 : case BIT_IOR_EXPR:
1378 18 : return integer_all_onesp (arg);
1379 :
1380 38 : case MULT_EXPR:
1381 38 : case BIT_AND_EXPR:
1382 38 : return integer_zerop (arg);
1383 :
1384 2 : case LSHIFT_EXPR:
1385 2 : case RSHIFT_EXPR:
1386 2 : case LROTATE_EXPR:
1387 2 : case RROTATE_EXPR:
1388 2 : return !right && integer_zerop (arg);
1389 :
1390 169 : case TRUNC_DIV_EXPR:
1391 169 : case CEIL_DIV_EXPR:
1392 169 : case FLOOR_DIV_EXPR:
1393 169 : case ROUND_DIV_EXPR:
1394 169 : case EXACT_DIV_EXPR:
1395 169 : case TRUNC_MOD_EXPR:
1396 169 : case CEIL_MOD_EXPR:
1397 169 : case FLOOR_MOD_EXPR:
1398 169 : case ROUND_MOD_EXPR:
1399 169 : return (!right
1400 11 : && integer_zerop (arg)
1401 179 : && tree_single_nonzero_p (rval));
1402 :
1403 : default:
1404 : return false;
1405 : }
1406 : }
1407 :
1408 : /* The function value_replacement does the main work of doing the value
1409 : replacement. Return non-zero if the replacement is done. Otherwise return
1410 : 0. If we remove the middle basic block, return 2.
1411 : BB is the basic block where the replacement is going to be done on. ARG0
1412 : is argument 0 from the PHI. Likewise for ARG1. */
1413 :
1414 : static int
1415 2477174 : value_replacement (basic_block cond_bb, basic_block middle_bb,
1416 : edge e0, edge e1, gphi *phi, tree arg0, tree arg1)
1417 : {
1418 2477174 : gimple_stmt_iterator gsi;
1419 2477174 : edge true_edge, false_edge;
1420 2477174 : enum tree_code code;
1421 2477174 : bool empty_or_with_defined_p = true;
1422 :
1423 : /* Virtual operands don't need to be handled. */
1424 4409727 : if (virtual_operand_p (arg1))
1425 : return 0;
1426 :
1427 : /* Special case A ? B : B as this will always simplify to B. */
1428 1307177 : if (operand_equal_for_phi_arg_p (arg0, arg1))
1429 : return 0;
1430 :
1431 2326658 : gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_bb));
1432 1163329 : code = gimple_cond_code (cond);
1433 :
1434 : /* This transformation is only valid for equality comparisons. */
1435 1163329 : if (code != NE_EXPR && code != EQ_EXPR)
1436 : return 0;
1437 :
1438 : /* Do not make conditional undefs unconditional. */
1439 703320 : if ((TREE_CODE (arg0) == SSA_NAME
1440 541213 : && ssa_name_maybe_undef_p (arg0))
1441 1242714 : || (TREE_CODE (arg1) == SSA_NAME
1442 301771 : && ssa_name_maybe_undef_p (arg1)))
1443 : return false;
1444 :
1445 : /* If the type says honor signed zeros we cannot do this
1446 : optimization. */
1447 687127 : if (HONOR_SIGNED_ZEROS (arg1))
1448 : return 0;
1449 :
1450 : /* If there is a statement in MIDDLE_BB that defines one of the PHI
1451 : arguments, then adjust arg0 or arg1. */
1452 673710 : gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
1453 2134140 : while (!gsi_end_p (gsi))
1454 : {
1455 1460430 : gimple *stmt = gsi_stmt (gsi);
1456 1460430 : tree lhs;
1457 1460430 : gsi_next_nondebug (&gsi);
1458 1460430 : if (!is_gimple_assign (stmt))
1459 : {
1460 205425 : if (gimple_code (stmt) != GIMPLE_PREDICT
1461 205425 : && gimple_code (stmt) != GIMPLE_NOP)
1462 : empty_or_with_defined_p = false;
1463 205425 : continue;
1464 : }
1465 : /* Now try to adjust arg0 or arg1 according to the computation
1466 : in the statement. */
1467 1255005 : lhs = gimple_assign_lhs (stmt);
1468 336907 : if (!(lhs == arg0
1469 336907 : && jump_function_from_stmt (&arg0, stmt))
1470 1257145 : || (lhs == arg1
1471 0 : && jump_function_from_stmt (&arg1, stmt)))
1472 : empty_or_with_defined_p = false;
1473 : }
1474 :
1475 : /* The middle bb is not empty if there are any phi nodes. */
1476 673710 : if (phi_nodes (middle_bb))
1477 72392 : empty_or_with_defined_p = false;
1478 :
1479 : /* We need to know which is the true edge and which is the false
1480 : edge so that we know if have abs or negative abs. */
1481 673710 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1482 :
1483 : /* At this point we know we have a COND_EXPR with two successors.
1484 : One successor is BB, the other successor is an empty block which
1485 : falls through into BB.
1486 :
1487 : The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
1488 :
1489 : There is a single PHI node at the join point (BB) with two arguments.
1490 :
1491 : We now need to verify that the two arguments in the PHI node match
1492 : the two arguments to the equality comparison. */
1493 :
1494 673710 : bool equal_p = operand_equal_for_value_replacement (arg0, arg1, &code, cond);
1495 673710 : bool maybe_equal_p = false;
1496 673710 : if (!equal_p
1497 673710 : && empty_or_with_defined_p
1498 188058 : && TREE_CODE (gimple_cond_rhs (cond)) == INTEGER_CST
1499 821308 : && (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond), arg0)
1500 147598 : ? TREE_CODE (arg1) == INTEGER_CST
1501 138549 : : (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond), arg1)
1502 20097 : && TREE_CODE (arg0) == INTEGER_CST)))
1503 : maybe_equal_p = true;
1504 654831 : if (equal_p || maybe_equal_p)
1505 : {
1506 32200 : edge e;
1507 32200 : tree arg;
1508 :
1509 : /* For NE_EXPR, we want to build an assignment result = arg where
1510 : arg is the PHI argument associated with the true edge. For
1511 : EQ_EXPR we want the PHI argument associated with the false edge. */
1512 32200 : e = (code == NE_EXPR ? true_edge : false_edge);
1513 :
1514 : /* Unfortunately, E may not reach BB (it may instead have gone to
1515 : OTHER_BLOCK). If that is the case, then we want the single outgoing
1516 : edge from OTHER_BLOCK which reaches BB and represents the desired
1517 : path from COND_BLOCK. */
1518 32200 : if (e->dest == middle_bb)
1519 14231 : e = single_succ_edge (e->dest);
1520 :
1521 : /* Now we know the incoming edge to BB that has the argument for the
1522 : RHS of our new assignment statement. */
1523 32200 : if (e0 == e)
1524 : arg = arg0;
1525 : else
1526 17969 : arg = arg1;
1527 :
1528 : /* If the middle basic block was empty or is defining the
1529 : PHI arguments and this is a single phi where the args are different
1530 : for the edges e0 and e1 then we can remove the middle basic block. */
1531 32200 : if (empty_or_with_defined_p
1532 32200 : && single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)),
1533 : e0, e1) == phi)
1534 : {
1535 18822 : use_operand_p use_p;
1536 18822 : gimple *use_stmt;
1537 :
1538 : /* Even if arg0/arg1 isn't equal to second operand of cond, we
1539 : can optimize away the bb if we can prove it doesn't care whether
1540 : phi result is arg0/arg1 or second operand of cond. Consider:
1541 : <bb 2> [local count: 118111600]:
1542 : if (i_2(D) == 4)
1543 : goto <bb 4>; [97.00%]
1544 : else
1545 : goto <bb 3>; [3.00%]
1546 :
1547 : <bb 3> [local count: 3540129]:
1548 :
1549 : <bb 4> [local count: 118111600]:
1550 : # i_6 = PHI <i_2(D)(3), 6(2)>
1551 : _3 = i_6 != 0;
1552 : Here, carg is 4, oarg is 6, crhs is 0, and because
1553 : (4 != 0) == (6 != 0), we don't care if i_6 is 4 or 6, both
1554 : have the same outcome. So, we can optimize this to:
1555 : _3 = i_2(D) != 0;
1556 : If the single imm use of phi result >, >=, < or <=, similarly
1557 : we can check if both carg and oarg compare the same against
1558 : crhs using ccode. */
1559 18822 : if (maybe_equal_p
1560 17284 : && TREE_CODE (arg) != INTEGER_CST
1561 36091 : && single_imm_use (gimple_phi_result (phi), &use_p, &use_stmt))
1562 : {
1563 9704 : enum tree_code ccode = ERROR_MARK;
1564 9704 : tree clhs = NULL_TREE, crhs = NULL_TREE;
1565 9704 : tree carg = gimple_cond_rhs (cond);
1566 9704 : tree oarg = e0 == e ? arg1 : arg0;
1567 9704 : if (is_gimple_assign (use_stmt)
1568 9704 : && (TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
1569 : == tcc_comparison))
1570 : {
1571 57 : ccode = gimple_assign_rhs_code (use_stmt);
1572 57 : clhs = gimple_assign_rhs1 (use_stmt);
1573 57 : crhs = gimple_assign_rhs2 (use_stmt);
1574 : }
1575 9647 : else if (gimple_code (use_stmt) == GIMPLE_COND)
1576 : {
1577 79 : ccode = gimple_cond_code (use_stmt);
1578 79 : clhs = gimple_cond_lhs (use_stmt);
1579 79 : crhs = gimple_cond_rhs (use_stmt);
1580 : }
1581 136 : if (ccode != ERROR_MARK
1582 136 : && clhs == gimple_phi_result (phi)
1583 233 : && TREE_CODE (crhs) == INTEGER_CST)
1584 45 : switch (ccode)
1585 : {
1586 26 : case EQ_EXPR:
1587 26 : case NE_EXPR:
1588 26 : if (!tree_int_cst_equal (crhs, carg)
1589 26 : && !tree_int_cst_equal (crhs, oarg))
1590 : equal_p = true;
1591 : break;
1592 2 : case GT_EXPR:
1593 4 : if (tree_int_cst_lt (crhs, carg)
1594 2 : == tree_int_cst_lt (crhs, oarg))
1595 : equal_p = true;
1596 : break;
1597 0 : case GE_EXPR:
1598 0 : if (tree_int_cst_le (crhs, carg)
1599 0 : == tree_int_cst_le (crhs, oarg))
1600 : equal_p = true;
1601 : break;
1602 13 : case LT_EXPR:
1603 26 : if (tree_int_cst_lt (carg, crhs)
1604 13 : == tree_int_cst_lt (oarg, crhs))
1605 : equal_p = true;
1606 : break;
1607 4 : case LE_EXPR:
1608 8 : if (tree_int_cst_le (carg, crhs)
1609 4 : == tree_int_cst_le (oarg, crhs))
1610 : equal_p = true;
1611 : break;
1612 : default:
1613 : break;
1614 : }
1615 9688 : if (equal_p)
1616 : {
1617 16 : tree phires = gimple_phi_result (phi);
1618 16 : if (SSA_NAME_RANGE_INFO (phires))
1619 : {
1620 : /* After the optimization PHI result can have value
1621 : which it couldn't have previously. */
1622 15 : value_range r (TREE_TYPE (phires));
1623 15 : if (get_global_range_query ()->range_of_expr (r, phires,
1624 : phi))
1625 : {
1626 15 : value_range tmp (carg, carg);
1627 15 : r.union_ (tmp);
1628 15 : reset_flow_sensitive_info (phires);
1629 15 : set_range_info (phires, r);
1630 15 : }
1631 : else
1632 0 : reset_flow_sensitive_info (phires);
1633 15 : }
1634 : }
1635 16 : if (equal_p && MAY_HAVE_DEBUG_BIND_STMTS)
1636 : {
1637 13 : imm_use_iterator imm_iter;
1638 13 : tree phires = gimple_phi_result (phi);
1639 13 : tree temp = NULL_TREE;
1640 13 : bool reset_p = false;
1641 :
1642 : /* Add # DEBUG D#1 => arg != carg ? arg : oarg. */
1643 42 : FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, phires)
1644 : {
1645 30 : if (!is_gimple_debug (use_stmt))
1646 13 : continue;
1647 17 : if (temp == NULL_TREE)
1648 : {
1649 12 : if (!single_pred_p (middle_bb)
1650 12 : || EDGE_COUNT (gimple_bb (phi)->preds) != 2)
1651 : {
1652 : /* But only if middle_bb has a single
1653 : predecessor and phi bb has two, otherwise
1654 : we could use a SSA_NAME not usable in that
1655 : place or wrong-debug. */
1656 1 : reset_p = true;
1657 1 : break;
1658 : }
1659 11 : gimple_stmt_iterator gsi
1660 11 : = gsi_after_labels (gimple_bb (phi));
1661 11 : tree type = TREE_TYPE (phires);
1662 11 : temp = build_debug_expr_decl (type);
1663 11 : tree t = build2 (NE_EXPR, boolean_type_node,
1664 : arg, carg);
1665 11 : t = build3 (COND_EXPR, type, t, arg, oarg);
1666 11 : gimple *g = gimple_build_debug_bind (temp, t, phi);
1667 11 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
1668 : }
1669 32 : FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
1670 16 : replace_exp (use_p, temp);
1671 16 : update_stmt (use_stmt);
1672 13 : }
1673 13 : if (reset_p)
1674 1 : reset_debug_uses (phi);
1675 : }
1676 : }
1677 9134 : if (equal_p)
1678 : {
1679 1554 : replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
1680 : /* Note that we optimized this PHI. */
1681 1554 : return 2;
1682 : }
1683 : }
1684 13378 : else if (equal_p)
1685 : {
1686 11783 : if (!single_pred_p (middle_bb))
1687 : return 0;
1688 10957 : statistics_counter_event (cfun, "Replace PHI with "
1689 : "variable/value_replacement", 1);
1690 :
1691 : /* Replace the PHI arguments with arg. */
1692 10957 : SET_PHI_ARG_DEF (phi, e0->dest_idx, arg);
1693 10957 : SET_PHI_ARG_DEF (phi, e1->dest_idx, arg);
1694 10957 : if (dump_file && (dump_flags & TDF_DETAILS))
1695 : {
1696 0 : fprintf (dump_file, "PHI ");
1697 0 : print_generic_expr (dump_file, gimple_phi_result (phi));
1698 0 : fprintf (dump_file, " reduced for COND_EXPR in block %d to ",
1699 : cond_bb->index);
1700 0 : print_generic_expr (dump_file, arg);
1701 0 : fprintf (dump_file, ".\n");
1702 : }
1703 10957 : return 1;
1704 : }
1705 : }
1706 :
1707 3027076 : if (!single_pred_p (middle_bb))
1708 : return 0;
1709 :
1710 : /* Now optimize (x != 0) ? x + y : y to just x + y. */
1711 562520 : gsi = gsi_last_nondebug_bb (middle_bb);
1712 562520 : if (gsi_end_p (gsi))
1713 : return 0;
1714 :
1715 392344 : gimple *assign = gsi_stmt (gsi);
1716 392344 : if (!is_gimple_assign (assign)
1717 392344 : || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
1718 109290 : && !POINTER_TYPE_P (TREE_TYPE (arg0))))
1719 : return 0;
1720 :
1721 333293 : if (gimple_assign_rhs_class (assign) != GIMPLE_BINARY_RHS)
1722 : {
1723 : /* If last stmt of the middle_bb is a conversion, handle it like
1724 : a preparation statement through constant evaluation with
1725 : checking for UB. */
1726 142459 : enum tree_code sc = gimple_assign_rhs_code (assign);
1727 142459 : if (CONVERT_EXPR_CODE_P (sc))
1728 : assign = NULL;
1729 : else
1730 : return 0;
1731 : }
1732 :
1733 : /* Punt if there are (degenerate) PHIs in middle_bb, there should not be. */
1734 213253 : if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
1735 : return 0;
1736 :
1737 : /* Allow up to 2 cheap preparation statements that prepare argument
1738 : for assign, e.g.:
1739 : if (y_4 != 0)
1740 : goto <bb 3>;
1741 : else
1742 : goto <bb 4>;
1743 : <bb 3>:
1744 : _1 = (int) y_4;
1745 : iftmp.0_6 = x_5(D) r<< _1;
1746 : <bb 4>:
1747 : # iftmp.0_2 = PHI <iftmp.0_6(3), x_5(D)(2)>
1748 : or:
1749 : if (y_3(D) == 0)
1750 : goto <bb 4>;
1751 : else
1752 : goto <bb 3>;
1753 : <bb 3>:
1754 : y_4 = y_3(D) & 31;
1755 : _1 = (int) y_4;
1756 : _6 = x_5(D) r<< _1;
1757 : <bb 4>:
1758 : # _2 = PHI <x_5(D)(2), _6(3)> */
1759 213253 : gimple *prep_stmt[2] = { NULL, NULL };
1760 213253 : int prep_cnt;
1761 213253 : for (prep_cnt = 0; ; prep_cnt++)
1762 : {
1763 274367 : if (prep_cnt || assign)
1764 251948 : gsi_prev_nondebug (&gsi);
1765 274367 : if (gsi_end_p (gsi))
1766 : break;
1767 :
1768 206072 : gimple *g = gsi_stmt (gsi);
1769 206072 : if (gimple_code (g) == GIMPLE_LABEL)
1770 : break;
1771 :
1772 205717 : if (prep_cnt == 2 || !is_gimple_assign (g))
1773 144603 : return 0;
1774 :
1775 181118 : tree lhs = gimple_assign_lhs (g);
1776 181118 : tree rhs1 = gimple_assign_rhs1 (g);
1777 181118 : use_operand_p use_p;
1778 181118 : gimple *use_stmt;
1779 181118 : if (TREE_CODE (lhs) != SSA_NAME
1780 174389 : || TREE_CODE (rhs1) != SSA_NAME
1781 110815 : || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1782 107275 : || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1783 103404 : || !single_imm_use (lhs, &use_p, &use_stmt)
1784 283613 : || ((prep_cnt || assign)
1785 81618 : && use_stmt != (prep_cnt ? prep_stmt[prep_cnt - 1] : assign)))
1786 86283 : return 0;
1787 94835 : switch (gimple_assign_rhs_code (g))
1788 : {
1789 : CASE_CONVERT:
1790 : break;
1791 20657 : case PLUS_EXPR:
1792 20657 : case BIT_AND_EXPR:
1793 20657 : case BIT_IOR_EXPR:
1794 20657 : case BIT_XOR_EXPR:
1795 20657 : if (TREE_CODE (gimple_assign_rhs2 (g)) != INTEGER_CST)
1796 : return 0;
1797 : break;
1798 : default:
1799 : return 0;
1800 : }
1801 61114 : prep_stmt[prep_cnt] = g;
1802 61114 : }
1803 :
1804 : /* Only transform if it removes the condition. */
1805 68650 : if (!single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)), e0, e1))
1806 : return 0;
1807 :
1808 : /* Size-wise, this is always profitable. */
1809 52205 : if (optimize_bb_for_speed_p (cond_bb)
1810 : /* The special case is useless if it has a low probability. */
1811 49423 : && profile_status_for_fn (cfun) != PROFILE_ABSENT
1812 60622 : && EDGE_PRED (middle_bb, 0)->probability < profile_probability::even ()
1813 : /* If assign is cheap, there is no point avoiding it. */
1814 63423 : && estimate_num_insns_seq (bb_seq (middle_bb), &eni_time_weights)
1815 11218 : >= 3 * estimate_num_insns (cond, &eni_time_weights))
1816 82 : return 0;
1817 :
1818 52123 : tree cond_lhs = gimple_cond_lhs (cond);
1819 52123 : tree cond_rhs = gimple_cond_rhs (cond);
1820 :
1821 : /* Propagate the cond_rhs constant through preparation stmts,
1822 : make sure UB isn't invoked while doing that. */
1823 53711 : for (int i = prep_cnt - 1; i >= 0; --i)
1824 : {
1825 13542 : gimple *g = prep_stmt[i];
1826 13542 : tree grhs1 = gimple_assign_rhs1 (g);
1827 13542 : if (!operand_equal_for_phi_arg_p (cond_lhs, grhs1))
1828 : return 0;
1829 7190 : cond_lhs = gimple_assign_lhs (g);
1830 7190 : cond_rhs = fold_convert (TREE_TYPE (grhs1), cond_rhs);
1831 7190 : if (TREE_CODE (cond_rhs) != INTEGER_CST
1832 7190 : || TREE_OVERFLOW (cond_rhs))
1833 : return 0;
1834 1588 : if (gimple_assign_rhs_class (g) == GIMPLE_BINARY_RHS)
1835 : {
1836 539 : cond_rhs = int_const_binop (gimple_assign_rhs_code (g), cond_rhs,
1837 539 : gimple_assign_rhs2 (g));
1838 539 : if (TREE_OVERFLOW (cond_rhs))
1839 : return 0;
1840 : }
1841 1588 : cond_rhs = fold_convert (TREE_TYPE (cond_lhs), cond_rhs);
1842 1588 : if (TREE_CODE (cond_rhs) != INTEGER_CST
1843 1588 : || TREE_OVERFLOW (cond_rhs))
1844 : return 0;
1845 : }
1846 :
1847 40169 : tree lhs, rhs1, rhs2;
1848 40169 : enum tree_code code_def;
1849 40169 : if (assign)
1850 : {
1851 39913 : lhs = gimple_assign_lhs (assign);
1852 39913 : rhs1 = gimple_assign_rhs1 (assign);
1853 39913 : rhs2 = gimple_assign_rhs2 (assign);
1854 39913 : code_def = gimple_assign_rhs_code (assign);
1855 : }
1856 : else
1857 : {
1858 256 : gcc_assert (prep_cnt > 0);
1859 : lhs = cond_lhs;
1860 : rhs1 = NULL_TREE;
1861 : rhs2 = NULL_TREE;
1862 : code_def = ERROR_MARK;
1863 : }
1864 :
1865 23292 : if (((code == NE_EXPR && e1 == false_edge)
1866 19668 : || (code == EQ_EXPR && e1 == true_edge))
1867 23211 : && arg0 == lhs
1868 63380 : && ((assign == NULL
1869 255 : && operand_equal_for_phi_arg_p (arg1, cond_rhs))
1870 : || (assign
1871 22956 : && arg1 == rhs1
1872 14899 : && operand_equal_for_phi_arg_p (rhs2, cond_lhs)
1873 388 : && neutral_element_p (code_def, cond_rhs, true))
1874 22890 : || (assign
1875 22890 : && arg1 == rhs2
1876 1314 : && operand_equal_for_phi_arg_p (rhs1, cond_lhs)
1877 655 : && neutral_element_p (code_def, cond_rhs, false))
1878 : || (assign
1879 22884 : && operand_equal_for_phi_arg_p (arg1, cond_rhs)
1880 2886 : && ((operand_equal_for_phi_arg_p (rhs2, cond_lhs)
1881 243 : && absorbing_element_p (code_def, cond_rhs, true, rhs2))
1882 2885 : || (operand_equal_for_phi_arg_p (rhs1, cond_lhs)
1883 636 : && absorbing_element_p (code_def,
1884 : cond_rhs, false, rhs2))))))
1885 : {
1886 107 : gsi = gsi_for_stmt (cond);
1887 : /* Moving ASSIGN might change VR of lhs, e.g. when moving u_6
1888 : def-stmt in:
1889 : if (n_5 != 0)
1890 : goto <bb 3>;
1891 : else
1892 : goto <bb 4>;
1893 :
1894 : <bb 3>:
1895 : # RANGE [0, 4294967294]
1896 : u_6 = n_5 + 4294967295;
1897 :
1898 : <bb 4>:
1899 : # u_3 = PHI <u_6(3), 4294967295(2)> */
1900 107 : reset_flow_sensitive_info (lhs);
1901 107 : gimple_stmt_iterator gsi_from;
1902 182 : for (int i = prep_cnt - 1; i >= 0; --i)
1903 : {
1904 75 : tree plhs = gimple_assign_lhs (prep_stmt[i]);
1905 75 : reset_flow_sensitive_info (plhs);
1906 75 : gsi_from = gsi_for_stmt (prep_stmt[i]);
1907 75 : gsi_move_before (&gsi_from, &gsi);
1908 : }
1909 107 : if (assign)
1910 : {
1911 103 : gsi_from = gsi_for_stmt (assign);
1912 103 : gsi_move_before (&gsi_from, &gsi);
1913 : }
1914 107 : replace_phi_edge_with_variable (cond_bb, e1, phi, lhs);
1915 107 : return 2;
1916 : }
1917 :
1918 : return 0;
1919 : }
1920 :
1921 : /* Attempt to optimize (x <=> y) cmp 0 and similar comparisons.
1922 : For strong ordering <=> try to match something like:
1923 : <bb 2> : // cond3_bb (== cond2_bb)
1924 : if (x_4(D) != y_5(D))
1925 : goto <bb 3>; [INV]
1926 : else
1927 : goto <bb 6>; [INV]
1928 :
1929 : <bb 3> : // cond_bb
1930 : if (x_4(D) < y_5(D))
1931 : goto <bb 6>; [INV]
1932 : else
1933 : goto <bb 4>; [INV]
1934 :
1935 : <bb 4> : // middle_bb
1936 :
1937 : <bb 6> : // phi_bb
1938 : # iftmp.0_2 = PHI <1(4), 0(2), -1(3)>
1939 : _1 = iftmp.0_2 == 0;
1940 :
1941 : and for partial ordering <=> something like:
1942 :
1943 : <bb 2> : // cond3_bb
1944 : if (a_3(D) == b_5(D))
1945 : goto <bb 6>; [50.00%]
1946 : else
1947 : goto <bb 3>; [50.00%]
1948 :
1949 : <bb 3> [local count: 536870913]: // cond2_bb
1950 : if (a_3(D) < b_5(D))
1951 : goto <bb 6>; [50.00%]
1952 : else
1953 : goto <bb 4>; [50.00%]
1954 :
1955 : <bb 4> [local count: 268435456]: // cond_bb
1956 : if (a_3(D) > b_5(D))
1957 : goto <bb 6>; [50.00%]
1958 : else
1959 : goto <bb 5>; [50.00%]
1960 :
1961 : <bb 5> [local count: 134217728]: // middle_bb
1962 :
1963 : <bb 6> [local count: 1073741824]: // phi_bb
1964 : # SR.27_4 = PHI <0(2), -1(3), 1(4), -128(5)>
1965 : _2 = SR.27_4 > 0; */
1966 :
1967 : static bool
1968 656692 : spaceship_replacement (basic_block cond_bb, basic_block middle_bb,
1969 : edge e0, edge e1, gphi *phi,
1970 : tree arg0, tree arg1)
1971 : {
1972 656692 : tree phires = gimple_phi_result (phi);
1973 1306140 : if (!INTEGRAL_TYPE_P (TREE_TYPE (phires))
1974 519060 : || TYPE_UNSIGNED (TREE_TYPE (phires))
1975 261640 : || !tree_fits_shwi_p (arg0)
1976 72022 : || !tree_fits_shwi_p (arg1)
1977 42329 : || (!IN_RANGE (tree_to_shwi (arg0), -1, 1)
1978 19961 : && tree_to_shwi (arg0) != -128)
1979 679622 : || (!IN_RANGE (tree_to_shwi (arg1), -1, 1)
1980 2743 : && tree_to_shwi (arg1) != -128))
1981 : return false;
1982 :
1983 20243 : basic_block phi_bb = gimple_bb (phi);
1984 20243 : gcc_assert (phi_bb == e0->dest && phi_bb == e1->dest);
1985 20243 : if (!IN_RANGE (EDGE_COUNT (phi_bb->preds), 3, 4))
1986 : return false;
1987 :
1988 7572 : use_operand_p use_p;
1989 7572 : gimple *use_stmt;
1990 7572 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (phires))
1991 : return false;
1992 7567 : if (!single_imm_use (phires, &use_p, &use_stmt))
1993 : return false;
1994 6945 : enum tree_code cmp;
1995 6945 : tree lhs, rhs;
1996 6945 : gimple *orig_use_stmt = use_stmt;
1997 6945 : tree orig_use_lhs = NULL_TREE;
1998 6945 : tree temps[2] = { NULL_TREE, NULL_TREE };
1999 :
2000 : /* Handle std::partial_ordering::_M_reverse(), i.e.
2001 : _1 = (unsigned char) phires;
2002 : _2 = -_1;
2003 : _3 = (signed char) _2;
2004 : and uses of _3 in comparison instead of phires. */
2005 6945 : if (gimple_assign_cast_p (use_stmt))
2006 : {
2007 285 : orig_use_lhs = gimple_assign_lhs (use_stmt);
2008 285 : temps[0] = orig_use_lhs;
2009 285 : tree ty1 = TREE_TYPE (gimple_assign_rhs1 (use_stmt));
2010 285 : tree ty2 = TREE_TYPE (orig_use_lhs);
2011 :
2012 285 : if (!TYPE_UNSIGNED (ty2) || !INTEGRAL_TYPE_P (ty2))
2013 : return false;
2014 245 : if (TYPE_PRECISION (ty2) != 8 || TYPE_PRECISION (ty1) < 8)
2015 : return false;
2016 126 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
2017 : return false;
2018 126 : if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
2019 : return false;
2020 :
2021 125 : if (!is_gimple_assign (use_stmt)
2022 125 : || gimple_assign_rhs_code (use_stmt) != NEGATE_EXPR)
2023 : return false;
2024 :
2025 122 : orig_use_lhs = gimple_assign_lhs (use_stmt);
2026 122 : temps[1] = orig_use_lhs;
2027 122 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
2028 : return false;
2029 122 : if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
2030 : return false;
2031 :
2032 122 : if (!gimple_assign_cast_p (use_stmt))
2033 : return false;
2034 :
2035 122 : orig_use_lhs = gimple_assign_lhs (use_stmt);
2036 122 : tree ty3 = TREE_TYPE (orig_use_lhs);
2037 :
2038 122 : if (!useless_type_conversion_p (ty3, ty1))
2039 : return false;
2040 122 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
2041 : return false;
2042 122 : if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
2043 : return false;
2044 : }
2045 6782 : if (gimple_code (use_stmt) == GIMPLE_COND)
2046 : {
2047 2465 : cmp = gimple_cond_code (use_stmt);
2048 2465 : lhs = gimple_cond_lhs (use_stmt);
2049 2465 : rhs = gimple_cond_rhs (use_stmt);
2050 : }
2051 4317 : else if (is_gimple_assign (use_stmt))
2052 : {
2053 2448 : if (gimple_assign_rhs_class (use_stmt) == GIMPLE_BINARY_RHS)
2054 : {
2055 1325 : cmp = gimple_assign_rhs_code (use_stmt);
2056 1325 : lhs = gimple_assign_rhs1 (use_stmt);
2057 1325 : rhs = gimple_assign_rhs2 (use_stmt);
2058 : }
2059 1123 : else if (gimple_assign_rhs_code (use_stmt) == COND_EXPR)
2060 : {
2061 0 : tree cond = gimple_assign_rhs1 (use_stmt);
2062 0 : if (!COMPARISON_CLASS_P (cond))
2063 : return false;
2064 0 : cmp = TREE_CODE (cond);
2065 0 : lhs = TREE_OPERAND (cond, 0);
2066 0 : rhs = TREE_OPERAND (cond, 1);
2067 : }
2068 : else
2069 : return false;
2070 : }
2071 : else
2072 : return false;
2073 3790 : switch (cmp)
2074 : {
2075 3309 : case EQ_EXPR:
2076 3309 : case NE_EXPR:
2077 3309 : case LT_EXPR:
2078 3309 : case GT_EXPR:
2079 3309 : case LE_EXPR:
2080 3309 : case GE_EXPR:
2081 3309 : break;
2082 : default:
2083 : return false;
2084 : }
2085 6496 : if (lhs != (orig_use_lhs ? orig_use_lhs : phires)
2086 2944 : || !tree_fits_shwi_p (rhs)
2087 2678 : || !IN_RANGE (tree_to_shwi (rhs), -1, 1))
2088 : return false;
2089 :
2090 2666 : if (!empty_block_p (middle_bb))
2091 : return false;
2092 :
2093 5332 : gcond *cond1 = as_a <gcond *> (*gsi_last_bb (cond_bb));
2094 2666 : enum tree_code cmp1 = gimple_cond_code (cond1);
2095 2666 : switch (cmp1)
2096 : {
2097 2531 : case LT_EXPR:
2098 2531 : case LE_EXPR:
2099 2531 : case GT_EXPR:
2100 2531 : case GE_EXPR:
2101 2531 : break;
2102 : default:
2103 : return false;
2104 : }
2105 2531 : tree lhs1 = gimple_cond_lhs (cond1);
2106 2531 : tree rhs1 = gimple_cond_rhs (cond1);
2107 2531 : if (TREE_CODE (lhs1) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs1))
2108 : return false;
2109 2531 : if (TREE_CODE (rhs1) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1))
2110 : return false;
2111 :
2112 2531 : if (!single_pred_p (cond_bb) || !cond_only_block_p (cond_bb))
2113 15 : return false;
2114 :
2115 2516 : basic_block cond2_bb = single_pred (cond_bb);
2116 2516 : if (EDGE_COUNT (cond2_bb->succs) != 2)
2117 : return false;
2118 2516 : edge cond2_phi_edge;
2119 2516 : if (EDGE_SUCC (cond2_bb, 0)->dest == cond_bb)
2120 : {
2121 2066 : if (EDGE_SUCC (cond2_bb, 1)->dest != phi_bb)
2122 : return false;
2123 : cond2_phi_edge = EDGE_SUCC (cond2_bb, 1);
2124 : }
2125 450 : else if (EDGE_SUCC (cond2_bb, 0)->dest != phi_bb)
2126 : return false;
2127 : else
2128 : cond2_phi_edge = EDGE_SUCC (cond2_bb, 0);
2129 2516 : tree arg2 = gimple_phi_arg_def (phi, cond2_phi_edge->dest_idx);
2130 2516 : if (!tree_fits_shwi_p (arg2))
2131 : return false;
2132 5032 : gcond *cond2 = safe_dyn_cast <gcond *> (*gsi_last_bb (cond2_bb));
2133 2516 : if (!cond2)
2134 : return false;
2135 2516 : enum tree_code cmp2 = gimple_cond_code (cond2);
2136 2516 : tree lhs2 = gimple_cond_lhs (cond2);
2137 2516 : tree rhs2 = gimple_cond_rhs (cond2);
2138 2516 : if (lhs2 == lhs1)
2139 : {
2140 2514 : if (!operand_equal_p (rhs2, rhs1, 0))
2141 : {
2142 337 : if ((cmp2 == EQ_EXPR || cmp2 == NE_EXPR)
2143 337 : && TREE_CODE (rhs1) == INTEGER_CST
2144 337 : && TREE_CODE (rhs2) == INTEGER_CST)
2145 : {
2146 : /* For integers, we can have cond2 x == 5
2147 : and cond1 x < 5, x <= 4, x <= 5, x < 6,
2148 : x > 5, x >= 6, x >= 5 or x > 4. */
2149 337 : if (tree_int_cst_lt (rhs1, rhs2))
2150 : {
2151 337 : if (wi::ne_p (wi::to_wide (rhs1) + 1, wi::to_wide (rhs2)))
2152 : return false;
2153 337 : if (cmp1 == LE_EXPR)
2154 : cmp1 = LT_EXPR;
2155 0 : else if (cmp1 == GT_EXPR)
2156 : cmp1 = GE_EXPR;
2157 : else
2158 : return false;
2159 : }
2160 : else
2161 : {
2162 0 : gcc_checking_assert (tree_int_cst_lt (rhs2, rhs1));
2163 0 : if (wi::ne_p (wi::to_wide (rhs2) + 1, wi::to_wide (rhs1)))
2164 : return false;
2165 0 : if (cmp1 == LT_EXPR)
2166 : cmp1 = LE_EXPR;
2167 0 : else if (cmp1 == GE_EXPR)
2168 : cmp1 = GT_EXPR;
2169 : else
2170 : return false;
2171 : }
2172 : rhs1 = rhs2;
2173 : }
2174 : else
2175 : return false;
2176 : }
2177 : }
2178 2 : else if (lhs2 == rhs1)
2179 : {
2180 0 : if (rhs2 != lhs1)
2181 : return false;
2182 : }
2183 : else
2184 : return false;
2185 :
2186 2514 : tree arg3 = arg2;
2187 2514 : basic_block cond3_bb = cond2_bb;
2188 2514 : edge cond3_phi_edge = cond2_phi_edge;
2189 2514 : gcond *cond3 = cond2;
2190 2514 : enum tree_code cmp3 = cmp2;
2191 2514 : tree lhs3 = lhs2;
2192 2514 : tree rhs3 = rhs2;
2193 2514 : if (EDGE_COUNT (phi_bb->preds) == 4)
2194 : {
2195 550 : if (absu_hwi (tree_to_shwi (arg2)) != 1)
2196 : return false;
2197 542 : if ((cond2_phi_edge->flags & EDGE_FALSE_VALUE)
2198 542 : && HONOR_NANS (TREE_TYPE (lhs1)))
2199 : return false;
2200 446 : if (e1->flags & EDGE_TRUE_VALUE)
2201 : {
2202 446 : if (tree_to_shwi (arg0) != -128
2203 446 : || absu_hwi (tree_to_shwi (arg1)) != 1
2204 892 : || wi::to_widest (arg1) == wi::to_widest (arg2))
2205 0 : return false;
2206 : }
2207 0 : else if (tree_to_shwi (arg1) != -128
2208 0 : || absu_hwi (tree_to_shwi (arg0)) != 1
2209 0 : || wi::to_widest (arg0) == wi::to_widest (arg2))
2210 0 : return false;
2211 446 : switch (cmp2)
2212 : {
2213 446 : case LT_EXPR:
2214 446 : case LE_EXPR:
2215 446 : case GT_EXPR:
2216 446 : case GE_EXPR:
2217 446 : break;
2218 : default:
2219 : return false;
2220 : }
2221 : /* if (x < y) goto phi_bb; else fallthru;
2222 : if (x > y) goto phi_bb; else fallthru;
2223 : bbx:;
2224 : phi_bb:;
2225 : is ok, but if x and y are swapped in one of the comparisons,
2226 : or the comparisons are the same and operands not swapped,
2227 : or the true and false edges are swapped, it is not.
2228 : For HONOR_NANS, the edge flags are irrelevant and the comparisons
2229 : must be different for non-swapped operands and same for swapped
2230 : operands. */
2231 446 : if ((lhs2 == lhs1)
2232 446 : ^ (HONOR_NANS (TREE_TYPE (lhs1))
2233 446 : ? ((cmp2 == LT_EXPR || cmp2 == LE_EXPR)
2234 318 : != (cmp1 == LT_EXPR || cmp1 == LE_EXPR))
2235 128 : : (((cond2_phi_edge->flags
2236 128 : & ((cmp2 == LT_EXPR || cmp2 == LE_EXPR)
2237 128 : ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE)) != 0)
2238 256 : != ((e1->flags
2239 128 : & ((cmp1 == LT_EXPR || cmp1 == LE_EXPR)
2240 128 : ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE)) != 0))))
2241 : return false;
2242 446 : if (!single_pred_p (cond2_bb) || !cond_only_block_p (cond2_bb))
2243 0 : return false;
2244 446 : cond3_bb = single_pred (cond2_bb);
2245 446 : if (EDGE_COUNT (cond2_bb->succs) != 2)
2246 : return false;
2247 446 : if (EDGE_SUCC (cond3_bb, 0)->dest == cond2_bb)
2248 : {
2249 222 : if (EDGE_SUCC (cond3_bb, 1)->dest != phi_bb)
2250 : return false;
2251 : cond3_phi_edge = EDGE_SUCC (cond3_bb, 1);
2252 : }
2253 224 : else if (EDGE_SUCC (cond3_bb, 0)->dest != phi_bb)
2254 : return false;
2255 : else
2256 : cond3_phi_edge = EDGE_SUCC (cond3_bb, 0);
2257 446 : arg3 = gimple_phi_arg_def (phi, cond3_phi_edge->dest_idx);
2258 655266 : cond3 = safe_dyn_cast <gcond *> (*gsi_last_bb (cond3_bb));
2259 446 : if (!cond3)
2260 : return false;
2261 446 : cmp3 = gimple_cond_code (cond3);
2262 446 : lhs3 = gimple_cond_lhs (cond3);
2263 446 : rhs3 = gimple_cond_rhs (cond3);
2264 446 : if (lhs3 == lhs1)
2265 : {
2266 446 : if (!operand_equal_p (rhs3, rhs1, 0))
2267 : return false;
2268 : }
2269 0 : else if (lhs3 == rhs1)
2270 : {
2271 0 : if (rhs3 != lhs1)
2272 : return false;
2273 : }
2274 : else
2275 : return false;
2276 : }
2277 1964 : else if (absu_hwi (tree_to_shwi (arg0)) != 1
2278 1944 : || absu_hwi (tree_to_shwi (arg1)) != 1
2279 3888 : || wi::to_widest (arg0) == wi::to_widest (arg1)
2280 3908 : || HONOR_NANS (TREE_TYPE (lhs1)))
2281 20 : return false;
2282 :
2283 2390 : if (!integer_zerop (arg3) || (cmp3 != EQ_EXPR && cmp3 != NE_EXPR))
2284 : return false;
2285 2390 : if ((cond3_phi_edge->flags & (cmp3 == EQ_EXPR
2286 2390 : ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE)) == 0)
2287 : return false;
2288 :
2289 : /* lhs1 one_cmp rhs1 results in phires of 1. */
2290 2390 : enum tree_code one_cmp;
2291 4780 : if ((cmp1 == LT_EXPR || cmp1 == LE_EXPR)
2292 2462 : ^ (!integer_onep ((e1->flags & EDGE_TRUE_VALUE) ? arg1 : arg0)))
2293 : one_cmp = LT_EXPR;
2294 : else
2295 1771 : one_cmp = GT_EXPR;
2296 :
2297 2390 : enum tree_code res_cmp;
2298 2390 : bool negate_p = false;
2299 2390 : switch (cmp)
2300 : {
2301 1304 : case EQ_EXPR:
2302 1304 : if (integer_zerop (rhs) && !HONOR_NANS (TREE_TYPE (lhs1)))
2303 : res_cmp = EQ_EXPR;
2304 1220 : else if (integer_minus_onep (rhs))
2305 763 : res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
2306 457 : else if (integer_onep (rhs))
2307 : res_cmp = one_cmp;
2308 : else
2309 : return false;
2310 : break;
2311 971 : case NE_EXPR:
2312 971 : if (integer_zerop (rhs) && !HONOR_NANS (TREE_TYPE (lhs1)))
2313 : res_cmp = NE_EXPR;
2314 933 : else if (integer_minus_onep (rhs))
2315 539 : res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
2316 458 : else if (integer_onep (rhs))
2317 668 : res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
2318 : else
2319 : return false;
2320 941 : if (HONOR_NANS (TREE_TYPE (lhs1)))
2321 : negate_p = true;
2322 : break;
2323 35 : case LT_EXPR:
2324 35 : if (integer_onep (rhs))
2325 0 : res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
2326 35 : else if (integer_zerop (rhs))
2327 35 : res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
2328 : else
2329 : return false;
2330 35 : if (HONOR_NANS (TREE_TYPE (lhs1)))
2331 : negate_p = true;
2332 : break;
2333 4 : case LE_EXPR:
2334 4 : if (integer_zerop (rhs))
2335 4 : res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
2336 0 : else if (integer_minus_onep (rhs))
2337 0 : res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
2338 : else
2339 : return false;
2340 4 : if (HONOR_NANS (TREE_TYPE (lhs1)))
2341 : negate_p = true;
2342 : break;
2343 0 : case GT_EXPR:
2344 0 : if (integer_minus_onep (rhs))
2345 0 : res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
2346 0 : else if (integer_zerop (rhs))
2347 : res_cmp = one_cmp;
2348 : else
2349 : return false;
2350 : break;
2351 76 : case GE_EXPR:
2352 76 : if (integer_zerop (rhs))
2353 76 : res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
2354 0 : else if (integer_onep (rhs))
2355 : res_cmp = one_cmp;
2356 : else
2357 : return false;
2358 : break;
2359 0 : default:
2360 0 : gcc_unreachable ();
2361 : }
2362 2318 : if (orig_use_lhs)
2363 104 : res_cmp = swap_tree_comparison (res_cmp);
2364 :
2365 2318 : tree clhs1 = lhs1, crhs1 = rhs1;
2366 2318 : if (negate_p)
2367 : {
2368 72 : if (cfun->can_throw_non_call_exceptions)
2369 0 : return false;
2370 72 : res_cmp = invert_tree_comparison (res_cmp, false);
2371 72 : clhs1 = make_ssa_name (boolean_type_node);
2372 72 : gimple *g = gimple_build_assign (clhs1, res_cmp, lhs1, rhs1);
2373 72 : gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
2374 72 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2375 72 : crhs1 = boolean_false_node;
2376 72 : res_cmp = EQ_EXPR;
2377 : }
2378 :
2379 2318 : if (gimple_code (use_stmt) == GIMPLE_COND)
2380 : {
2381 1664 : gcond *use_cond = as_a <gcond *> (use_stmt);
2382 1664 : gimple_cond_set_code (use_cond, res_cmp);
2383 1664 : gimple_cond_set_lhs (use_cond, clhs1);
2384 1664 : gimple_cond_set_rhs (use_cond, crhs1);
2385 : }
2386 654 : else if (gimple_assign_rhs_class (use_stmt) == GIMPLE_BINARY_RHS)
2387 : {
2388 654 : gimple_assign_set_rhs_code (use_stmt, res_cmp);
2389 654 : gimple_assign_set_rhs1 (use_stmt, clhs1);
2390 654 : gimple_assign_set_rhs2 (use_stmt, crhs1);
2391 : }
2392 : else
2393 : {
2394 0 : tree cond = build2 (res_cmp, TREE_TYPE (gimple_assign_rhs1 (use_stmt)),
2395 : clhs1, crhs1);
2396 0 : gimple_assign_set_rhs1 (use_stmt, cond);
2397 : }
2398 2318 : update_stmt (use_stmt);
2399 :
2400 2318 : if (MAY_HAVE_DEBUG_BIND_STMTS)
2401 : {
2402 1935 : use_operand_p use_p;
2403 1935 : imm_use_iterator iter;
2404 1935 : bool has_debug_uses = false;
2405 1935 : bool has_cast1_debug_uses = false;
2406 1935 : bool has_neg_debug_uses = false;
2407 1935 : bool has_cast2_debug_uses = false;
2408 3914 : FOR_EACH_IMM_USE_FAST (use_p, iter, phires)
2409 : {
2410 1979 : gimple *use_stmt = USE_STMT (use_p);
2411 1979 : if (is_gimple_debug (use_stmt))
2412 : {
2413 : has_debug_uses = true;
2414 : break;
2415 : }
2416 1935 : }
2417 1935 : if (orig_use_lhs)
2418 : {
2419 132 : FOR_EACH_IMM_USE_FAST (use_p, iter, temps[0])
2420 : {
2421 76 : gimple *use_stmt = USE_STMT (use_p);
2422 76 : if (is_gimple_debug (use_stmt))
2423 : {
2424 : has_debug_uses = true;
2425 : has_cast1_debug_uses = true;
2426 : break;
2427 : }
2428 44 : }
2429 132 : FOR_EACH_IMM_USE_FAST (use_p, iter, temps[1])
2430 : {
2431 76 : gimple *use_stmt = USE_STMT (use_p);
2432 76 : if (is_gimple_debug (use_stmt))
2433 : {
2434 : has_debug_uses = true;
2435 : has_cast1_debug_uses = true;
2436 : has_neg_debug_uses = true;
2437 : break;
2438 : }
2439 44 : }
2440 88 : FOR_EACH_IMM_USE_FAST (use_p, iter, orig_use_lhs)
2441 : {
2442 32 : gimple *use_stmt = USE_STMT (use_p);
2443 32 : if (is_gimple_debug (use_stmt))
2444 : {
2445 : has_debug_uses = true;
2446 : has_cast1_debug_uses = true;
2447 : has_neg_debug_uses = true;
2448 : has_cast2_debug_uses = true;
2449 : break;
2450 : }
2451 44 : }
2452 44 : if (has_debug_uses)
2453 : {
2454 44 : gimple_stmt_iterator gsi = gsi_for_stmt (orig_use_stmt);
2455 44 : tree zero = build_zero_cst (TREE_TYPE (temps[0]));
2456 44 : gimple_assign_set_rhs_with_ops (&gsi, INTEGER_CST, zero);
2457 44 : update_stmt (orig_use_stmt);
2458 44 : gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (temps[1]));
2459 44 : zero = build_zero_cst (TREE_TYPE (temps[1]));
2460 44 : gimple_assign_set_rhs_with_ops (&gsi, INTEGER_CST, zero);
2461 44 : update_stmt (SSA_NAME_DEF_STMT (temps[1]));
2462 44 : gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (orig_use_lhs));
2463 44 : zero = build_zero_cst (TREE_TYPE (orig_use_lhs));
2464 44 : gimple_assign_set_rhs_with_ops (&gsi, INTEGER_CST, zero);
2465 44 : update_stmt (SSA_NAME_DEF_STMT (orig_use_lhs));
2466 : }
2467 : }
2468 :
2469 1935 : if (has_debug_uses)
2470 : {
2471 : /* If there are debug uses, emit something like:
2472 : # DEBUG D#1 => i_2(D) > j_3(D) ? 1 : -1
2473 : # DEBUG D#2 => i_2(D) == j_3(D) ? 0 : D#1
2474 : where > stands for the comparison that yielded 1
2475 : and replace debug uses of phi result with that D#2.
2476 : Ignore the value of -128 if !HONOR_NANS, because if NaNs
2477 : aren't expected, all floating point numbers should be
2478 : comparable. If HONOR_NANS, emit something like:
2479 : # DEBUG D#1 => i_2(D) < j_3(D) ? -1 : -128
2480 : # DEBUG D#2 => i_2(D) > j_3(D) ? 1 : D#1
2481 : # DEBUG D#3 => i_2(D) == j_3(D) ? 0 : D#2
2482 : instead. */
2483 1935 : gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi));
2484 1935 : tree type = TREE_TYPE (phires);
2485 1935 : tree minus_one = build_int_cst (type, -1);
2486 1935 : if (HONOR_NANS (TREE_TYPE (lhs1)))
2487 : {
2488 102 : tree temp3 = build_debug_expr_decl (type);
2489 204 : tree t = build2 (one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR,
2490 : boolean_type_node, lhs1, rhs2);
2491 102 : t = build3 (COND_EXPR, type, t, minus_one,
2492 : build_int_cst (type, -128));
2493 102 : gimple *g = gimple_build_debug_bind (temp3, t, phi);
2494 102 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2495 102 : minus_one = temp3;
2496 : }
2497 1935 : tree temp1 = build_debug_expr_decl (type);
2498 1935 : tree t = build2 (one_cmp, boolean_type_node, lhs1, rhs2);
2499 1935 : t = build3 (COND_EXPR, type, t, build_one_cst (type),
2500 : minus_one);
2501 1935 : gimple *g = gimple_build_debug_bind (temp1, t, phi);
2502 1935 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2503 1935 : tree temp2 = build_debug_expr_decl (type);
2504 1935 : t = build2 (EQ_EXPR, boolean_type_node, lhs1, rhs2);
2505 1935 : t = build3 (COND_EXPR, type, t, build_zero_cst (type), temp1);
2506 1935 : g = gimple_build_debug_bind (temp2, t, phi);
2507 1935 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2508 1935 : replace_uses_by (phires, temp2);
2509 1935 : if (has_cast1_debug_uses)
2510 : {
2511 32 : tree temp3 = build_debug_expr_decl (TREE_TYPE (temps[0]));
2512 32 : t = fold_convert (TREE_TYPE (temps[0]), temp2);
2513 32 : g = gimple_build_debug_bind (temp3, t, phi);
2514 32 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2515 32 : replace_uses_by (temps[0], temp3);
2516 32 : temp2 = temp3;
2517 : }
2518 1935 : if (has_neg_debug_uses)
2519 : {
2520 32 : tree temp3 = build_debug_expr_decl (TREE_TYPE (temps[1]));
2521 32 : t = fold_build1 (NEGATE_EXPR, TREE_TYPE (temps[1]), temp2);
2522 32 : g = gimple_build_debug_bind (temp3, t, phi);
2523 32 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2524 32 : replace_uses_by (temps[1], temp3);
2525 32 : temp2 = temp3;
2526 : }
2527 1935 : if (has_cast2_debug_uses)
2528 : {
2529 32 : tree temp3 = build_debug_expr_decl (TREE_TYPE (orig_use_lhs));
2530 32 : t = fold_convert (TREE_TYPE (orig_use_lhs), temp2);
2531 32 : g = gimple_build_debug_bind (temp3, t, phi);
2532 32 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2533 32 : replace_uses_by (orig_use_lhs, temp3);
2534 : }
2535 : }
2536 : }
2537 :
2538 2318 : if (orig_use_lhs)
2539 : {
2540 104 : gimple_stmt_iterator gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (orig_use_lhs));
2541 104 : gsi_remove (&gsi, true);
2542 104 : gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (temps[1]));
2543 104 : gsi_remove (&gsi, true);
2544 104 : gsi = gsi_for_stmt (orig_use_stmt);
2545 104 : gsi_remove (&gsi, true);
2546 104 : release_ssa_name (orig_use_lhs);
2547 104 : release_ssa_name (temps[1]);
2548 104 : release_ssa_name (temps[0]);
2549 : }
2550 :
2551 2318 : gimple_stmt_iterator psi = gsi_for_stmt (phi);
2552 2318 : remove_phi_node (&psi, true);
2553 2318 : statistics_counter_event (cfun, "spaceship replacement", 1);
2554 :
2555 2318 : return true;
2556 : }
2557 :
2558 : /* Optimize x ? __builtin_fun (x) : C, where C is __builtin_fun (0).
2559 : Convert
2560 :
2561 : <bb 2>
2562 : if (b_4(D) != 0)
2563 : goto <bb 3>
2564 : else
2565 : goto <bb 4>
2566 :
2567 : <bb 3>
2568 : _2 = (unsigned long) b_4(D);
2569 : _9 = __builtin_popcountl (_2);
2570 : OR
2571 : _9 = __builtin_popcountl (b_4(D));
2572 :
2573 : <bb 4>
2574 : c_12 = PHI <0(2), _9(3)>
2575 :
2576 : Into
2577 : <bb 2>
2578 : _2 = (unsigned long) b_4(D);
2579 : _9 = __builtin_popcountl (_2);
2580 : OR
2581 : _9 = __builtin_popcountl (b_4(D));
2582 :
2583 : <bb 4>
2584 : c_12 = PHI <_9(2)>
2585 :
2586 : Similarly for __builtin_clz or __builtin_ctz if
2587 : C?Z_DEFINED_VALUE_AT_ZERO is 2, optab is present and
2588 : instead of 0 above it uses the value from that macro. */
2589 :
2590 : static bool
2591 455645 : cond_removal_in_builtin_zero_pattern (basic_block cond_bb,
2592 : basic_block middle_bb,
2593 : edge e1, edge e2, gphi *phi,
2594 : tree arg0, tree arg1)
2595 : {
2596 455645 : gimple_stmt_iterator gsi, gsi_from;
2597 455645 : gimple *call;
2598 455645 : gimple *cast = NULL;
2599 455645 : tree lhs, arg;
2600 :
2601 : /* Check that
2602 : _2 = (unsigned long) b_4(D);
2603 : _9 = __builtin_popcountl (_2);
2604 : OR
2605 : _9 = __builtin_popcountl (b_4(D));
2606 : are the only stmts in the middle_bb. */
2607 :
2608 455645 : gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
2609 455645 : if (gsi_end_p (gsi))
2610 : return false;
2611 292274 : cast = gsi_stmt (gsi);
2612 292274 : gsi_next_nondebug (&gsi);
2613 292274 : if (!gsi_end_p (gsi))
2614 : {
2615 141253 : call = gsi_stmt (gsi);
2616 141253 : gsi_next_nondebug (&gsi);
2617 141253 : if (!gsi_end_p (gsi))
2618 : return false;
2619 : }
2620 : else
2621 : {
2622 : call = cast;
2623 : cast = NULL;
2624 : }
2625 :
2626 : /* Check that we have a popcount/clz/ctz builtin. */
2627 200260 : if (!is_gimple_call (call))
2628 : return false;
2629 :
2630 6199 : lhs = gimple_get_lhs (call);
2631 :
2632 6199 : if (lhs == NULL_TREE)
2633 : return false;
2634 :
2635 6173 : combined_fn cfn = gimple_call_combined_fn (call);
2636 6173 : if (gimple_call_num_args (call) != 1
2637 6173 : && (gimple_call_num_args (call) != 2
2638 : || cfn == CFN_CLZ
2639 578 : || cfn == CFN_CTZ))
2640 : return false;
2641 :
2642 4660 : arg = gimple_call_arg (call, 0);
2643 :
2644 4660 : internal_fn ifn = IFN_LAST;
2645 4660 : int val = 0;
2646 4660 : bool any_val = false;
2647 4660 : switch (cfn)
2648 : {
2649 : CASE_CFN_BSWAP:
2650 : CASE_CFN_BITREVERSE:
2651 : CASE_CFN_FFS:
2652 : CASE_CFN_PARITY:
2653 : CASE_CFN_POPCOUNT:
2654 : break;
2655 973 : CASE_CFN_CLZ:
2656 973 : if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
2657 : {
2658 973 : tree type = TREE_TYPE (arg);
2659 973 : if (BITINT_TYPE_P (type))
2660 : {
2661 4 : if (gimple_call_num_args (call) == 1)
2662 : {
2663 : any_val = true;
2664 : ifn = IFN_CLZ;
2665 : break;
2666 : }
2667 0 : if (!tree_fits_shwi_p (gimple_call_arg (call, 1)))
2668 : return false;
2669 0 : HOST_WIDE_INT at_zero = tree_to_shwi (gimple_call_arg (call, 1));
2670 0 : if ((int) at_zero != at_zero)
2671 : return false;
2672 0 : ifn = IFN_CLZ;
2673 0 : val = at_zero;
2674 0 : break;
2675 : }
2676 969 : if (direct_internal_fn_supported_p (IFN_CLZ, type, OPTIMIZE_FOR_BOTH)
2677 1913 : && CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type),
2678 : val) == 2)
2679 : {
2680 : ifn = IFN_CLZ;
2681 : break;
2682 : }
2683 : }
2684 : return false;
2685 298 : CASE_CFN_CTZ:
2686 298 : if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
2687 : {
2688 298 : tree type = TREE_TYPE (arg);
2689 298 : if (BITINT_TYPE_P (type))
2690 : {
2691 4 : if (gimple_call_num_args (call) == 1)
2692 : {
2693 : any_val = true;
2694 : ifn = IFN_CTZ;
2695 : break;
2696 : }
2697 0 : if (!tree_fits_shwi_p (gimple_call_arg (call, 1)))
2698 : return false;
2699 0 : HOST_WIDE_INT at_zero = tree_to_shwi (gimple_call_arg (call, 1));
2700 0 : if ((int) at_zero != at_zero)
2701 : return false;
2702 0 : ifn = IFN_CTZ;
2703 0 : val = at_zero;
2704 0 : break;
2705 : }
2706 294 : if (direct_internal_fn_supported_p (IFN_CTZ, type, OPTIMIZE_FOR_BOTH)
2707 567 : && CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type),
2708 : val) == 2)
2709 : {
2710 : ifn = IFN_CTZ;
2711 : break;
2712 : }
2713 : }
2714 : return false;
2715 3 : case CFN_BUILT_IN_CLRSB:
2716 3 : val = TYPE_PRECISION (integer_type_node) - 1;
2717 3 : break;
2718 3 : case CFN_BUILT_IN_CLRSBL:
2719 3 : val = TYPE_PRECISION (long_integer_type_node) - 1;
2720 3 : break;
2721 3 : case CFN_BUILT_IN_CLRSBLL:
2722 3 : val = TYPE_PRECISION (long_long_integer_type_node) - 1;
2723 3 : break;
2724 : default:
2725 : return false;
2726 : }
2727 :
2728 143 : if (cast)
2729 : {
2730 : /* We have a cast stmt feeding popcount/clz/ctz builtin. */
2731 : /* Check that we have a cast prior to that. */
2732 55 : if (gimple_code (cast) != GIMPLE_ASSIGN
2733 55 : || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (cast)))
2734 : return false;
2735 : /* Result of the cast stmt is the argument to the builtin. */
2736 25 : if (arg != gimple_assign_lhs (cast))
2737 : return false;
2738 25 : arg = gimple_assign_rhs1 (cast);
2739 : }
2740 :
2741 226 : gcond *cond = dyn_cast <gcond *> (*gsi_last_bb (cond_bb));
2742 :
2743 : /* Cond_bb has a check for b_4 [!=|==] 0 before calling the popcount/clz/ctz
2744 : builtin. */
2745 113 : if (!cond
2746 113 : || (gimple_cond_code (cond) != NE_EXPR
2747 20 : && gimple_cond_code (cond) != EQ_EXPR)
2748 113 : || !integer_zerop (gimple_cond_rhs (cond))
2749 113 : || arg != gimple_cond_lhs (cond))
2750 78 : return false;
2751 :
2752 35 : edge true_edge, false_edge;
2753 : /* We need to know which is the true edge and which is the false
2754 : edge so that we know when to invert the condition below. */
2755 35 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
2756 :
2757 : /* Forward the edges over the middle basic block. */
2758 35 : if (true_edge->dest == middle_bb)
2759 35 : true_edge = EDGE_SUCC (true_edge->dest, 0);
2760 35 : if (false_edge->dest == middle_bb)
2761 0 : false_edge = EDGE_SUCC (false_edge->dest, 0);
2762 :
2763 : /* Canonicalize the args with respect to the edges,
2764 : arg0 is from the true edge and arg1 is from the
2765 : false edge.
2766 : That is `cond ? arg0 : arg1`.*/
2767 35 : if (true_edge == e1)
2768 35 : gcc_assert (false_edge == e2);
2769 : else
2770 : {
2771 0 : gcc_assert (false_edge == e1);
2772 0 : gcc_assert (true_edge == e2);
2773 : std::swap (arg0, arg1);
2774 : }
2775 :
2776 : /* Canonicalize the args such that we get:
2777 : `arg != 0 ? arg0 : arg1`. So swap arg0/arg1
2778 : around if cond was an equals. */
2779 35 : if (gimple_cond_code (cond) == EQ_EXPR)
2780 2 : std::swap (arg0, arg1);
2781 :
2782 : /* Check PHI arguments. */
2783 35 : if (lhs != arg0
2784 33 : || TREE_CODE (arg1) != INTEGER_CST)
2785 : return false;
2786 25 : if (any_val)
2787 : {
2788 0 : if (!tree_fits_shwi_p (arg1))
2789 : return false;
2790 0 : HOST_WIDE_INT at_zero = tree_to_shwi (arg1);
2791 0 : if ((int) at_zero != at_zero)
2792 : return false;
2793 0 : val = at_zero;
2794 : }
2795 25 : else if (wi::to_wide (arg1) != val)
2796 : return false;
2797 :
2798 : /* And insert the popcount/clz/ctz builtin and cast stmt before the
2799 : cond_bb. */
2800 13 : gsi = gsi_last_bb (cond_bb);
2801 13 : if (cast)
2802 : {
2803 13 : gsi_from = gsi_for_stmt (cast);
2804 13 : gsi_move_before (&gsi_from, &gsi);
2805 13 : reset_flow_sensitive_info (gimple_get_lhs (cast));
2806 : }
2807 13 : gsi_from = gsi_for_stmt (call);
2808 13 : if (ifn == IFN_LAST
2809 13 : || (gimple_call_internal_p (call) && gimple_call_num_args (call) == 2))
2810 8 : gsi_move_before (&gsi_from, &gsi);
2811 : else
2812 : {
2813 : /* For __builtin_c[lt]z* force .C[LT]Z ifn, because only
2814 : the latter is well defined at zero. */
2815 5 : call = gimple_build_call_internal (ifn, 2, gimple_call_arg (call, 0),
2816 5 : build_int_cst (integer_type_node, val));
2817 5 : gimple_call_set_lhs (call, lhs);
2818 5 : gsi_insert_before (&gsi, call, GSI_SAME_STMT);
2819 5 : gsi_remove (&gsi_from, true);
2820 : }
2821 13 : reset_flow_sensitive_info (lhs);
2822 :
2823 : /* Now update the PHI and remove unneeded bbs. */
2824 13 : replace_phi_edge_with_variable (cond_bb, e2, phi, lhs);
2825 13 : return true;
2826 : }
2827 :
2828 : /* Auxiliary functions to determine the set of memory accesses which
2829 : can't trap because they are preceded by accesses to the same memory
2830 : portion. We do that for MEM_REFs, so we only need to track
2831 : the SSA_NAME of the pointer indirectly referenced. The algorithm
2832 : simply is a walk over all instructions in dominator order. When
2833 : we see an MEM_REF we determine if we've already seen a same
2834 : ref anywhere up to the root of the dominator tree. If we do the
2835 : current access can't trap. If we don't see any dominating access
2836 : the current access might trap, but might also make later accesses
2837 : non-trapping, so we remember it. We need to be careful with loads
2838 : or stores, for instance a load might not trap, while a store would,
2839 : so if we see a dominating read access this doesn't mean that a later
2840 : write access would not trap. Hence we also need to differentiate the
2841 : type of access(es) seen.
2842 :
2843 : ??? We currently are very conservative and assume that a load might
2844 : trap even if a store doesn't (write-only memory). This probably is
2845 : overly conservative.
2846 :
2847 : We currently support a special case that for !TREE_ADDRESSABLE automatic
2848 : variables, it could ignore whether something is a load or store because the
2849 : local stack should be always writable. */
2850 :
2851 : /* A hash-table of references (MEM_REF/ARRAY_REF/COMPONENT_REF), and in which
2852 : basic block an *_REF through it was seen, which would constitute a
2853 : no-trap region for same accesses.
2854 :
2855 : Size is needed to support 2 MEM_REFs of different types, like
2856 : MEM<double>(s_1) and MEM<long>(s_1), which would compare equal with
2857 : OEP_ADDRESS_OF. */
2858 : struct ref_to_bb
2859 : {
2860 : tree exp;
2861 : HOST_WIDE_INT size;
2862 : unsigned int phase;
2863 : basic_block bb;
2864 : };
2865 :
2866 : /* Hashtable helpers. */
2867 :
2868 : struct refs_hasher : free_ptr_hash<ref_to_bb>
2869 : {
2870 : static inline hashval_t hash (const ref_to_bb *);
2871 : static inline bool equal (const ref_to_bb *, const ref_to_bb *);
2872 : };
2873 :
2874 : /* Used for quick clearing of the hash-table when we see calls.
2875 : Hash entries with phase < nt_call_phase are invalid. */
2876 : static unsigned int nt_call_phase;
2877 :
2878 : /* The hash function. */
2879 :
2880 : inline hashval_t
2881 19983212 : refs_hasher::hash (const ref_to_bb *n)
2882 : {
2883 19983212 : inchash::hash hstate;
2884 19983212 : inchash::add_expr (n->exp, hstate, OEP_ADDRESS_OF);
2885 19983212 : hstate.add_hwi (n->size);
2886 19983212 : return hstate.end ();
2887 : }
2888 :
2889 : /* The equality function of *P1 and *P2. */
2890 :
2891 : inline bool
2892 14604141 : refs_hasher::equal (const ref_to_bb *n1, const ref_to_bb *n2)
2893 : {
2894 14604141 : return operand_equal_p (n1->exp, n2->exp, OEP_ADDRESS_OF)
2895 14604141 : && n1->size == n2->size;
2896 : }
2897 :
2898 : class nontrapping_dom_walker : public dom_walker
2899 : {
2900 : public:
2901 1055009 : nontrapping_dom_walker (cdi_direction direction, hash_set<tree> *ps)
2902 1055009 : : dom_walker (direction), m_nontrapping (ps), m_seen_refs (128)
2903 1055009 : {}
2904 :
2905 : edge before_dom_children (basic_block) final override;
2906 : void after_dom_children (basic_block) final override;
2907 :
2908 : private:
2909 :
2910 : /* We see the expression EXP in basic block BB. If it's an interesting
2911 : expression (an MEM_REF through an SSA_NAME) possibly insert the
2912 : expression into the set NONTRAP or the hash table of seen expressions.
2913 : STORE is true if this expression is on the LHS, otherwise it's on
2914 : the RHS. */
2915 : void add_or_mark_expr (basic_block, tree, bool);
2916 :
2917 : hash_set<tree> *m_nontrapping;
2918 :
2919 : /* The hash table for remembering what we've seen. */
2920 : hash_table<refs_hasher> m_seen_refs;
2921 : };
2922 :
2923 : /* Called by walk_dominator_tree, when entering the block BB. */
2924 : edge
2925 11834151 : nontrapping_dom_walker::before_dom_children (basic_block bb)
2926 : {
2927 11834151 : edge e;
2928 11834151 : edge_iterator ei;
2929 11834151 : gimple_stmt_iterator gsi;
2930 :
2931 : /* If we haven't seen all our predecessors, clear the hash-table. */
2932 26011434 : FOR_EACH_EDGE (e, ei, bb->preds)
2933 14870838 : if ((((size_t)e->src->aux) & 2) == 0)
2934 : {
2935 693555 : nt_call_phase++;
2936 693555 : break;
2937 : }
2938 :
2939 : /* Mark this BB as being on the path to dominator root and as visited. */
2940 11834151 : bb->aux = (void*)(1 | 2);
2941 :
2942 : /* And walk the statements in order. */
2943 106710266 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2944 : {
2945 83041964 : gimple *stmt = gsi_stmt (gsi);
2946 :
2947 83041964 : if ((gimple_code (stmt) == GIMPLE_ASM && gimple_vdef (stmt))
2948 83085245 : || (is_gimple_call (stmt)
2949 5667822 : && (!nonfreeing_call_p (stmt) || !nonbarrier_call_p (stmt))))
2950 5071403 : nt_call_phase++;
2951 93265180 : else if (gimple_assign_single_p (stmt) && !gimple_has_volatile_ops (stmt))
2952 : {
2953 13358835 : add_or_mark_expr (bb, gimple_assign_lhs (stmt), true);
2954 13358835 : add_or_mark_expr (bb, gimple_assign_rhs1 (stmt), false);
2955 : }
2956 : }
2957 11834151 : return NULL;
2958 : }
2959 :
2960 : /* Called by walk_dominator_tree, when basic block BB is exited. */
2961 : void
2962 11834151 : nontrapping_dom_walker::after_dom_children (basic_block bb)
2963 : {
2964 : /* This BB isn't on the path to dominator root anymore. */
2965 11834151 : bb->aux = (void*)2;
2966 11834151 : }
2967 :
2968 : /* We see the expression EXP in basic block BB. If it's an interesting
2969 : expression of:
2970 : 1) MEM_REF
2971 : 2) ARRAY_REF
2972 : 3) COMPONENT_REF
2973 : possibly insert the expression into the set NONTRAP or the hash table
2974 : of seen expressions. STORE is true if this expression is on the LHS,
2975 : otherwise it's on the RHS. */
2976 : void
2977 26717670 : nontrapping_dom_walker::add_or_mark_expr (basic_block bb, tree exp, bool store)
2978 : {
2979 26717670 : HOST_WIDE_INT size;
2980 :
2981 26717670 : if ((TREE_CODE (exp) == MEM_REF || TREE_CODE (exp) == ARRAY_REF
2982 22371322 : || TREE_CODE (exp) == COMPONENT_REF)
2983 33919134 : && (size = int_size_in_bytes (TREE_TYPE (exp))) > 0)
2984 : {
2985 11547807 : struct ref_to_bb map;
2986 11547807 : ref_to_bb **slot;
2987 11547807 : struct ref_to_bb *r2bb;
2988 11547807 : basic_block found_bb = 0;
2989 :
2990 11547807 : if (!store)
2991 : {
2992 5314866 : tree base = get_base_address (exp);
2993 : /* Only record a LOAD of a local variable without address-taken, as
2994 : the local stack is always writable. This allows cselim on a STORE
2995 : with a dominating LOAD. */
2996 5314866 : if (!auto_var_p (base) || TREE_ADDRESSABLE (base))
2997 4340401 : return;
2998 : }
2999 :
3000 : /* Try to find the last seen *_REF, which can trap. */
3001 7207406 : map.exp = exp;
3002 7207406 : map.size = size;
3003 7207406 : slot = m_seen_refs.find_slot (&map, INSERT);
3004 7207406 : r2bb = *slot;
3005 7207406 : if (r2bb && r2bb->phase >= nt_call_phase)
3006 295812 : found_bb = r2bb->bb;
3007 :
3008 : /* If we've found a trapping *_REF, _and_ it dominates EXP
3009 : (it's in a basic block on the path from us to the dominator root)
3010 : then we can't trap. */
3011 295812 : if (found_bb && (((size_t)found_bb->aux) & 1) == 1)
3012 : {
3013 82667 : m_nontrapping->add (exp);
3014 : }
3015 : else
3016 : {
3017 : /* EXP might trap, so insert it into the hash table. */
3018 7124739 : if (r2bb)
3019 : {
3020 985324 : r2bb->phase = nt_call_phase;
3021 985324 : r2bb->bb = bb;
3022 : }
3023 : else
3024 : {
3025 6139415 : r2bb = XNEW (struct ref_to_bb);
3026 6139415 : r2bb->phase = nt_call_phase;
3027 6139415 : r2bb->bb = bb;
3028 6139415 : r2bb->exp = exp;
3029 6139415 : r2bb->size = size;
3030 6139415 : *slot = r2bb;
3031 : }
3032 : }
3033 : }
3034 : }
3035 :
3036 : /* This is the entry point of gathering non trapping memory accesses.
3037 : It will do a dominator walk over the whole function, and it will
3038 : make use of the bb->aux pointers. It returns a set of trees
3039 : (the MEM_REFs itself) which can't trap. */
3040 : static hash_set<tree> *
3041 1055009 : get_non_trapping (void)
3042 : {
3043 1055009 : nt_call_phase = 0;
3044 1055009 : hash_set<tree> *nontrap = new hash_set<tree>;
3045 :
3046 2110018 : nontrapping_dom_walker (CDI_DOMINATORS, nontrap)
3047 1055009 : .walk (cfun->cfg->x_entry_block_ptr);
3048 :
3049 1055009 : clear_aux_for_blocks ();
3050 1055009 : return nontrap;
3051 : }
3052 :
3053 : /* Do the main work of conditional store replacement. We already know
3054 : that the recognized pattern looks like so:
3055 :
3056 : split:
3057 : if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
3058 : MIDDLE_BB:
3059 : something
3060 : fallthrough (edge E0)
3061 : JOIN_BB:
3062 : some more
3063 :
3064 : ASSIGN is a store in MIDDLE_BB which is the candidate for cselim. We check
3065 : that MIDDLE_BB contains only one store (i.e., ASSIGN), that that store
3066 : doesn't trap (not via NOTRAP, but via checking if an access to the same
3067 : memory location dominates us, or the store is to a local addressable object)
3068 : and that the store has a "simple" RHS. */
3069 :
3070 : static bool
3071 437713 : cond_store_replacement (basic_block middle_bb, basic_block join_bb, edge e0,
3072 : edge e1, gimple *assign, hash_set<tree> *nontrap)
3073 : {
3074 437713 : tree lhs, rhs, name, name2;
3075 437713 : gphi *newphi;
3076 437713 : gassign *new_stmt;
3077 437713 : gimple_stmt_iterator gsi;
3078 437713 : location_t locus;
3079 :
3080 : /* Check if middle_bb contains of only one store. */
3081 437713 : if (!assign
3082 190982 : || !gimple_assign_single_p (assign)
3083 471865 : || gimple_has_volatile_ops (assign))
3084 : return false;
3085 :
3086 33951 : locus = gimple_location (assign);
3087 33951 : lhs = gimple_assign_lhs (assign);
3088 33951 : rhs = gimple_assign_rhs1 (assign);
3089 33951 : if ((!REFERENCE_CLASS_P (lhs)
3090 33951 : && !DECL_P (lhs))
3091 33951 : || !is_gimple_reg_type (TREE_TYPE (lhs)))
3092 : return false;
3093 :
3094 : /* Make sure all uses (except the rhs) in the single stmt are also available
3095 : where we insert to. */
3096 33470 : ssa_op_iter iter;
3097 33470 : tree use;
3098 65151 : FOR_EACH_SSA_TREE_OPERAND (use, assign, iter, SSA_OP_USE)
3099 : {
3100 36091 : if (use == rhs)
3101 14809 : continue;
3102 :
3103 21282 : gimple *stmt = SSA_NAME_DEF_STMT (use);
3104 21282 : if (stmt && gimple_bb (stmt) == middle_bb)
3105 : return false;
3106 : }
3107 :
3108 : /* Prove that we can move the store down. We could also check
3109 : TREE_THIS_NOTRAP here, but in that case we also could move stores,
3110 : whose value is not available readily, which we want to avoid. */
3111 29060 : if (nontrap->contains (lhs))
3112 : {
3113 : /* For local non-addressable variables, a load in the same bb
3114 : (though before) will cause the lhs to be in the nontrap hashset.
3115 : So need to check if there are no other loads in the middle bb.
3116 : FIXME: this is over conserative, this check could be made to
3117 : allow loads unrelated to lhs. */
3118 7126 : tree vuse = gimple_vuse (assign);
3119 7126 : imm_use_iterator iter;
3120 7126 : gimple *use_stmt;
3121 31035 : FOR_EACH_IMM_USE_STMT (use_stmt, iter, vuse)
3122 : {
3123 17559 : if (use_stmt == assign)
3124 7101 : continue;
3125 10458 : if (gimple_bb (use_stmt) == middle_bb)
3126 776 : return false;
3127 7126 : }
3128 : }
3129 : else
3130 : {
3131 : /* If LHS is an access to a local variable without address-taken
3132 : (or when we allow data races) and known not to trap, we could
3133 : always safely move down the store. */
3134 21934 : tree base;
3135 21934 : if (ref_can_have_store_data_races (lhs)
3136 1146 : || tree_could_trap_p (lhs)
3137 : /* tree_could_trap_p is a predicate for rvalues, so check
3138 : for readonly memory explicitly. */
3139 22249 : || ((base = get_base_address (lhs))
3140 315 : && ((DECL_P (base)
3141 308 : && TREE_READONLY (base))
3142 310 : || TREE_CODE (base) == STRING_CST)))
3143 21630 : return false;
3144 : }
3145 :
3146 : /* Now we've checked the constraints, so do the transformation:
3147 : 1) Remove the single store. */
3148 6654 : gsi = gsi_for_stmt (assign);
3149 6654 : unlink_stmt_vdef (assign);
3150 6654 : gsi_remove (&gsi, true);
3151 6654 : release_defs (assign);
3152 :
3153 : /* Make both store and load use alias-set zero as we have to
3154 : deal with the case of the store being a conditional change
3155 : of the dynamic type. */
3156 6654 : lhs = unshare_expr (lhs);
3157 6654 : tree *basep = &lhs;
3158 13399 : while (handled_component_p (*basep))
3159 6745 : basep = &TREE_OPERAND (*basep, 0);
3160 6654 : if (TREE_CODE (*basep) == MEM_REF
3161 6654 : || TREE_CODE (*basep) == TARGET_MEM_REF)
3162 1062 : TREE_OPERAND (*basep, 1)
3163 2124 : = fold_convert (ptr_type_node, TREE_OPERAND (*basep, 1));
3164 : else
3165 5592 : *basep = build2 (MEM_REF, TREE_TYPE (*basep),
3166 : build_fold_addr_expr (*basep),
3167 : build_zero_cst (ptr_type_node));
3168 :
3169 : /* 2) Insert a load from the memory of the store to the temporary
3170 : on the edge which did not contain the store. */
3171 6654 : gphi *vphi = get_virtual_phi (join_bb);
3172 6654 : name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3173 6654 : new_stmt = gimple_build_assign (name, lhs);
3174 6654 : gimple_set_location (new_stmt, locus);
3175 : /* Set the vuse for the new load. */
3176 6654 : gimple_set_vuse (new_stmt, gimple_phi_arg_def (vphi, e1->dest_idx));
3177 6654 : lhs = unshare_expr (lhs);
3178 6654 : {
3179 : /* Set the no-warning bit on the rhs of the load to avoid uninit
3180 : warnings. */
3181 6654 : tree rhs1 = gimple_assign_rhs1 (new_stmt);
3182 6654 : suppress_warning (rhs1, OPT_Wuninitialized);
3183 : }
3184 6654 : gsi_insert_on_edge (e1, new_stmt);
3185 :
3186 : /* 3) Create a PHI node at the join block, with one argument
3187 : holding the old RHS, and the other holding the temporary
3188 : where we stored the old memory contents. */
3189 6654 : name2 = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3190 6654 : newphi = create_phi_node (name2, join_bb);
3191 6654 : add_phi_arg (newphi, rhs, e0, locus);
3192 6654 : add_phi_arg (newphi, name, e1, locus);
3193 :
3194 6654 : new_stmt = gimple_build_assign (lhs, gimple_phi_result (newphi));
3195 :
3196 : /* Update the vdef for the new store statement. */
3197 6654 : tree newvphilhs = make_ssa_name (gimple_vop (cfun));
3198 6654 : tree vdef = gimple_phi_result (vphi);
3199 6654 : gimple_set_vuse (new_stmt, newvphilhs);
3200 6654 : gimple_set_vdef (new_stmt, vdef);
3201 6654 : gimple_phi_set_result (vphi, newvphilhs);
3202 6654 : SSA_NAME_DEF_STMT (vdef) = new_stmt;
3203 6654 : update_stmt (vphi);
3204 :
3205 : /* 4) Insert that PHI node. */
3206 6654 : gsi = gsi_after_labels (join_bb);
3207 6654 : gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
3208 :
3209 6654 : if (dump_file && (dump_flags & TDF_DETAILS))
3210 : {
3211 8 : fprintf (dump_file, "\nConditional store replacement happened!");
3212 8 : fprintf (dump_file, "\nReplaced the store with a load.");
3213 8 : fprintf (dump_file, "\nInserted a new PHI statement in joint block:\n");
3214 8 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_VOPS|TDF_MEMSYMS);
3215 : }
3216 6654 : statistics_counter_event (cfun, "conditional store replacement", 1);
3217 :
3218 6654 : return true;
3219 : }
3220 :
3221 : /* Do the main work of conditional store replacement. */
3222 :
3223 : static bool
3224 853362 : cond_if_else_store_replacement_1 (basic_block then_bb, basic_block else_bb,
3225 : basic_block join_bb, gimple *then_assign,
3226 : gimple *else_assign,
3227 : gphi *vphi)
3228 : {
3229 853362 : tree lhs_base, lhs, then_rhs, else_rhs, name;
3230 853362 : location_t then_locus, else_locus;
3231 853362 : gimple_stmt_iterator gsi;
3232 853362 : gphi *newphi = nullptr;
3233 853362 : gassign *new_stmt;
3234 :
3235 853362 : if (then_assign == NULL
3236 853362 : || !gimple_assign_single_p (then_assign)
3237 770679 : || else_assign == NULL
3238 770679 : || !gimple_assign_single_p (else_assign)
3239 99876 : || stmt_references_abnormal_ssa_name (then_assign)
3240 953224 : || stmt_references_abnormal_ssa_name (else_assign))
3241 753500 : return false;
3242 :
3243 : /* Allow both being clobbers but no other volatile operations. */
3244 99862 : if (gimple_clobber_p (then_assign)
3245 99862 : && gimple_clobber_p (else_assign))
3246 : ;
3247 182130 : else if (gimple_has_volatile_ops (then_assign)
3248 182130 : || gimple_has_volatile_ops (else_assign))
3249 : return false;
3250 :
3251 82252 : lhs = gimple_assign_lhs (then_assign);
3252 82252 : if (!operand_equal_p (lhs, gimple_assign_lhs (else_assign), 0))
3253 : return false;
3254 :
3255 32255 : lhs_base = get_base_address (lhs);
3256 32255 : if (lhs_base == NULL_TREE
3257 32255 : || (!DECL_P (lhs_base) && TREE_CODE (lhs_base) != MEM_REF))
3258 : return false;
3259 :
3260 32175 : then_rhs = gimple_assign_rhs1 (then_assign);
3261 32175 : else_rhs = gimple_assign_rhs1 (else_assign);
3262 32175 : then_locus = gimple_location (then_assign);
3263 32175 : else_locus = gimple_location (else_assign);
3264 :
3265 32175 : if (!is_gimple_reg_type (TREE_TYPE (lhs)))
3266 : {
3267 : /* Handle clobbers separately as operand_equal_p does not check
3268 : the kind of the clobbers being the same. */
3269 6499 : if (TREE_CLOBBER_P (then_rhs) && TREE_CLOBBER_P (else_rhs))
3270 : {
3271 2906 : if (CLOBBER_KIND (then_rhs) != CLOBBER_KIND (else_rhs))
3272 : return false;
3273 : }
3274 3593 : else if (!operand_equal_p (then_rhs, else_rhs))
3275 : return false;
3276 : /* Currently only handle commoning of `= {}`. */
3277 3393 : if (TREE_CODE (then_rhs) != CONSTRUCTOR)
3278 : return false;
3279 : }
3280 :
3281 28685 : if (dump_file && (dump_flags & TDF_DETAILS))
3282 : {
3283 8 : if (TREE_CLOBBER_P (then_rhs))
3284 3 : fprintf(dump_file, "factoring out clobber:\n\tthen:\n");
3285 : else
3286 5 : fprintf(dump_file, "factoring out stores:\n\tthen:\n");
3287 8 : print_gimple_stmt (dump_file, then_assign, 0,
3288 : TDF_VOPS|TDF_MEMSYMS);
3289 8 : fprintf(dump_file, "\telse:\n");
3290 8 : print_gimple_stmt (dump_file, else_assign, 0,
3291 : TDF_VOPS|TDF_MEMSYMS);
3292 8 : fprintf (dump_file, "\n");
3293 : }
3294 :
3295 : /* Now we've checked the constraints, so do the transformation:
3296 : 1) Remove the stores. */
3297 28685 : gsi = gsi_for_stmt (then_assign);
3298 28685 : unlink_stmt_vdef (then_assign);
3299 28685 : gsi_remove (&gsi, true);
3300 28685 : release_defs (then_assign);
3301 :
3302 28685 : gsi = gsi_for_stmt (else_assign);
3303 28685 : unlink_stmt_vdef (else_assign);
3304 28685 : gsi_remove (&gsi, true);
3305 28685 : release_defs (else_assign);
3306 :
3307 : /* 2) Create a PHI node at the join block, with one argument
3308 : holding the old RHS, and the other holding the temporary
3309 : where we stored the old memory contents. */
3310 28685 : if (operand_equal_p (then_rhs, else_rhs))
3311 : name = then_rhs;
3312 : else
3313 : {
3314 23481 : name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3315 23481 : newphi = create_phi_node (name, join_bb);
3316 23481 : add_phi_arg (newphi, then_rhs, EDGE_SUCC (then_bb, 0), then_locus);
3317 23481 : add_phi_arg (newphi, else_rhs, EDGE_SUCC (else_bb, 0), else_locus);
3318 : }
3319 :
3320 28685 : new_stmt = gimple_build_assign (lhs, name);
3321 : /* Update the vdef for the new store statement. */
3322 28685 : tree newvphilhs = make_ssa_name (gimple_vop (cfun));
3323 28685 : tree vdef = gimple_phi_result (vphi);
3324 28685 : gimple_set_vuse (new_stmt, newvphilhs);
3325 28685 : gimple_set_vdef (new_stmt, vdef);
3326 28685 : gimple_phi_set_result (vphi, newvphilhs);
3327 28685 : SSA_NAME_DEF_STMT (vdef) = new_stmt;
3328 28685 : update_stmt (vphi);
3329 28685 : if (dump_file && (dump_flags & TDF_DETAILS))
3330 : {
3331 8 : if (newphi)
3332 : {
3333 4 : fprintf(dump_file, "to use phi:\n");
3334 4 : print_gimple_stmt (dump_file, newphi, 0,
3335 : TDF_VOPS|TDF_MEMSYMS);
3336 4 : fprintf(dump_file, "\n");
3337 : }
3338 : else
3339 4 : fprintf(dump_file, "to:\n");
3340 8 : print_gimple_stmt (dump_file, new_stmt, 0,
3341 : TDF_VOPS|TDF_MEMSYMS);
3342 8 : fprintf(dump_file, "\n\n");
3343 : }
3344 :
3345 : /* 3) Insert that new store. */
3346 28685 : gsi = gsi_after_labels (join_bb);
3347 28685 : gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
3348 :
3349 28685 : statistics_counter_event (cfun, "if-then-else store replacement", 1);
3350 :
3351 28685 : return true;
3352 : }
3353 :
3354 : /* Return the last store in BB with VDEF or NULL if there are
3355 : loads following the store. VPHI is where the only use of the
3356 : vdef should be. If ONLYONESTORE is true, then the store is
3357 : the only store in the BB. */
3358 :
3359 : static gimple *
3360 2087976 : trailing_store_in_bb (basic_block bb, tree vdef, gphi *vphi, bool onlyonestore)
3361 : {
3362 2087976 : if (SSA_NAME_IS_DEFAULT_DEF (vdef))
3363 : return NULL;
3364 2062806 : gimple *store = SSA_NAME_DEF_STMT (vdef);
3365 2062806 : if (gimple_bb (store) != bb
3366 2062806 : || gimple_code (store) == GIMPLE_PHI)
3367 : return NULL;
3368 :
3369 : /* Verify there is no other store in this BB if requested. */
3370 2023293 : if (onlyonestore
3371 295204 : && !SSA_NAME_IS_DEFAULT_DEF (gimple_vuse (store))
3372 234293 : && gimple_bb (SSA_NAME_DEF_STMT (gimple_vuse (store))) == bb
3373 2109592 : && gimple_code (SSA_NAME_DEF_STMT (gimple_vuse (store))) != GIMPLE_PHI)
3374 : return NULL;
3375 :
3376 :
3377 : /* Verify there is no load or store after the store, the vdef of the store
3378 : should only be used by the vphi joining the 2 bbs. */
3379 1937000 : use_operand_p use_p;
3380 1937000 : gimple *use_stmt;
3381 3874000 : if (!single_imm_use (gimple_vdef (store), &use_p, &use_stmt))
3382 : return NULL;
3383 1914179 : if (use_stmt != vphi)
3384 : return NULL;
3385 :
3386 : return store;
3387 : }
3388 :
3389 : /* Return the only store in MIDDLE_BB as the candidate store for cselim. Return
3390 : NULL if no candidate can be found. */
3391 :
3392 : static gimple *
3393 437713 : cselim_candidate (basic_block middle_bb, basic_block join_bb, edge e0)
3394 : {
3395 437713 : gphi *vphi = get_virtual_phi (join_bb);
3396 437713 : if (!vphi)
3397 : return NULL;
3398 :
3399 268802 : tree middle_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, e0);
3400 268802 : return trailing_store_in_bb (middle_bb, middle_vdef, vphi, true);
3401 : }
3402 :
3403 : /* Limited Conditional store replacement. We already know
3404 : that the recognized pattern looks like so:
3405 :
3406 : split:
3407 : if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
3408 : THEN_BB:
3409 : ...
3410 : STORE = Y;
3411 : ...
3412 : goto JOIN_BB;
3413 : ELSE_BB:
3414 : ...
3415 : STORE = Z;
3416 : ...
3417 : fallthrough (edge E0)
3418 : JOIN_BB:
3419 : some more
3420 :
3421 : Handles only the case with store in THEN_BB and ELSE_BB. That is
3422 : cheap enough due to in phiopt and not worry about heurstics. Moving the store
3423 : out might provide an opportunity for a phiopt to happen.
3424 : At -O1 (!flag_expensive_optimizations), this only handles the only store in
3425 : the BBs. */
3426 :
3427 : static bool
3428 947740 : cond_if_else_store_replacement_limited (basic_block then_bb, basic_block else_bb,
3429 : basic_block join_bb)
3430 : {
3431 947740 : gphi *vphi = get_virtual_phi (join_bb);
3432 947740 : if (!vphi)
3433 : return false;
3434 :
3435 947740 : tree then_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (then_bb));
3436 1895480 : gimple *then_assign = trailing_store_in_bb (then_bb, then_vdef, vphi,
3437 947740 : !flag_expensive_optimizations);
3438 947740 : if (!then_assign)
3439 : return false;
3440 :
3441 871434 : tree else_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (else_bb));
3442 1742868 : gimple *else_assign = trailing_store_in_bb (else_bb, else_vdef, vphi,
3443 871434 : !flag_expensive_optimizations);
3444 871434 : if (!else_assign)
3445 : return false;
3446 :
3447 851763 : return cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
3448 851763 : then_assign, else_assign, vphi);
3449 : }
3450 :
3451 : /* Conditional store replacement. We already know
3452 : that the recognized pattern looks like so:
3453 :
3454 : split:
3455 : if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
3456 : THEN_BB:
3457 : ...
3458 : X = Y;
3459 : ...
3460 : goto JOIN_BB;
3461 : ELSE_BB:
3462 : ...
3463 : X = Z;
3464 : ...
3465 : fallthrough (edge E0)
3466 : JOIN_BB:
3467 : some more
3468 :
3469 : We check that it is safe to sink the store to JOIN_BB by verifying that
3470 : there are no read-after-write or write-after-write dependencies in
3471 : THEN_BB and ELSE_BB. */
3472 :
3473 : static bool
3474 240161 : cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb,
3475 : basic_block join_bb)
3476 : {
3477 240161 : vec<data_reference_p> then_datarefs, else_datarefs;
3478 240161 : vec<ddr_p> then_ddrs, else_ddrs;
3479 240161 : gimple *then_store, *else_store;
3480 240161 : bool found, ok = false, res;
3481 240161 : tree then_lhs, else_lhs;
3482 240161 : basic_block blocks[3];
3483 240161 : gphi *vphi = get_virtual_phi (join_bb);
3484 240161 : if (!vphi)
3485 : return false;
3486 :
3487 : /* Handle the case with trailing stores in THEN_BB and ELSE_BB. That is
3488 : cheap enough to always handle as it allows us to elide dependence
3489 : checking. */
3490 238621 : while (cond_if_else_store_replacement_limited (then_bb, else_bb, join_bb))
3491 : ;
3492 :
3493 : /* If either vectorization or if-conversion is disabled then do
3494 : not sink any stores. */
3495 224413 : if (param_max_stores_to_sink == 0
3496 224412 : || (!flag_tree_loop_vectorize && !flag_tree_slp_vectorize)
3497 218857 : || !flag_tree_loop_if_convert)
3498 : return false;
3499 :
3500 : /* Find data references. */
3501 218854 : then_datarefs.create (1);
3502 218854 : else_datarefs.create (1);
3503 218854 : if ((find_data_references_in_bb (NULL, then_bb, &then_datarefs)
3504 218854 : == chrec_dont_know)
3505 193424 : || !then_datarefs.length ()
3506 187571 : || (find_data_references_in_bb (NULL, else_bb, &else_datarefs)
3507 187571 : == chrec_dont_know)
3508 234317 : || !else_datarefs.length ())
3509 : {
3510 204445 : free_data_refs (then_datarefs);
3511 204445 : free_data_refs (else_datarefs);
3512 204445 : return false;
3513 : }
3514 :
3515 : /* Clear visited on else stores, we want to make sure to pick each store
3516 : at most once to avoid quadratic behavior. */
3517 51706 : for (auto else_dr : else_datarefs)
3518 : {
3519 37297 : if (DR_IS_READ (else_dr))
3520 19316 : continue;
3521 17981 : gimple_set_visited (DR_STMT (else_dr), false);
3522 : }
3523 :
3524 : /* Find pairs of stores with equal LHS. Work from the end to avoid
3525 : re-ordering stores unnecessarily. */
3526 14409 : auto_vec<std::pair<gimple *, gimple *>, 1> stores_pairs;
3527 14409 : unsigned i;
3528 14409 : data_reference_p then_dr;
3529 60950 : FOR_EACH_VEC_ELT_REVERSE (then_datarefs, i, then_dr)
3530 : {
3531 32132 : if (DR_IS_READ (then_dr))
3532 44973 : continue;
3533 :
3534 19291 : then_store = DR_STMT (then_dr);
3535 19291 : then_lhs = gimple_get_lhs (then_store);
3536 19291 : if (then_lhs == NULL_TREE)
3537 0 : continue;
3538 19291 : found = false;
3539 :
3540 19291 : unsigned j;
3541 19291 : data_reference_p else_dr;
3542 91118 : FOR_EACH_VEC_ELT_REVERSE (else_datarefs, j, else_dr)
3543 : {
3544 56202 : if (DR_IS_READ (else_dr))
3545 20367 : continue;
3546 :
3547 35835 : else_store = DR_STMT (else_dr);
3548 35835 : if (gimple_visited_p (else_store))
3549 3281 : continue;
3550 32554 : else_lhs = gimple_get_lhs (else_store);
3551 32554 : if (else_lhs == NULL_TREE)
3552 0 : continue;
3553 :
3554 32554 : if (operand_equal_p (then_lhs, else_lhs, 0))
3555 : {
3556 : found = true;
3557 : break;
3558 : }
3559 : }
3560 :
3561 19291 : if (!found)
3562 15625 : continue;
3563 :
3564 3666 : gimple_set_visited (else_store, true);
3565 3666 : stores_pairs.safe_push (std::make_pair (then_store, else_store));
3566 : }
3567 :
3568 : /* No pairs of stores found. */
3569 14409 : if (!stores_pairs.length ()
3570 14409 : || stores_pairs.length () > (unsigned) param_max_stores_to_sink)
3571 : {
3572 12286 : free_data_refs (then_datarefs);
3573 12286 : free_data_refs (else_datarefs);
3574 12286 : return false;
3575 : }
3576 :
3577 : /* Compute and check data dependencies in both basic blocks. */
3578 2123 : then_ddrs.create (1);
3579 2123 : else_ddrs.create (1);
3580 2123 : if (!compute_all_dependences (then_datarefs, &then_ddrs,
3581 2123 : vNULL, false)
3582 4246 : || !compute_all_dependences (else_datarefs, &else_ddrs,
3583 2123 : vNULL, false))
3584 : {
3585 0 : free_dependence_relations (then_ddrs);
3586 0 : free_dependence_relations (else_ddrs);
3587 0 : free_data_refs (then_datarefs);
3588 0 : free_data_refs (else_datarefs);
3589 0 : return false;
3590 : }
3591 2123 : blocks[0] = then_bb;
3592 2123 : blocks[1] = else_bb;
3593 2123 : blocks[2] = join_bb;
3594 2123 : renumber_gimple_stmt_uids_in_blocks (blocks, 3);
3595 :
3596 : /* Check that there are no read-after-write or write-after-write dependencies
3597 : in THEN_BB. */
3598 12917 : for (auto ddr : then_ddrs)
3599 : {
3600 7282 : struct data_reference *dra = DDR_A (ddr);
3601 7282 : struct data_reference *drb = DDR_B (ddr);
3602 :
3603 7282 : if (DDR_ARE_DEPENDENT (ddr) != chrec_known
3604 7282 : && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
3605 823 : && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
3606 1557 : || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
3607 475 : && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
3608 1082 : || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
3609 : {
3610 734 : free_dependence_relations (then_ddrs);
3611 734 : free_dependence_relations (else_ddrs);
3612 734 : free_data_refs (then_datarefs);
3613 734 : free_data_refs (else_datarefs);
3614 734 : return false;
3615 : }
3616 : }
3617 :
3618 : /* Check that there are no read-after-write or write-after-write dependencies
3619 : in ELSE_BB. */
3620 8682 : for (auto ddr : else_ddrs)
3621 : {
3622 4683 : struct data_reference *dra = DDR_A (ddr);
3623 4683 : struct data_reference *drb = DDR_B (ddr);
3624 :
3625 4683 : if (DDR_ARE_DEPENDENT (ddr) != chrec_known
3626 4683 : && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
3627 401 : && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
3628 569 : || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
3629 140 : && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
3630 429 : || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
3631 : {
3632 168 : free_dependence_relations (then_ddrs);
3633 168 : free_dependence_relations (else_ddrs);
3634 168 : free_data_refs (then_datarefs);
3635 168 : free_data_refs (else_datarefs);
3636 168 : return false;
3637 : }
3638 : }
3639 :
3640 : /* Sink stores with same LHS. */
3641 5262 : for (auto &store_pair : stores_pairs)
3642 : {
3643 1599 : then_store = store_pair.first;
3644 1599 : else_store = store_pair.second;
3645 1599 : res = cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
3646 : then_store, else_store, vphi);
3647 1599 : ok = ok || res;
3648 : }
3649 :
3650 1221 : free_dependence_relations (then_ddrs);
3651 1221 : free_dependence_relations (else_ddrs);
3652 1221 : free_data_refs (then_datarefs);
3653 1221 : free_data_refs (else_datarefs);
3654 :
3655 1221 : return ok;
3656 14409 : }
3657 :
3658 : /* If PHI at MERGE is a "load PHI", PHI <*P, *Q> whose two arguments are
3659 : single-use, non-volatile scalar MEM_REF loads reading the same memory state
3660 : (same VUSE), factor the load out: introduce P' = PHI <P, Q> and a single
3661 : load *P' replacing the PHI. No speculative load is introduced (the load uses
3662 : whichever pointer the taken edge selected).
3663 : E0/E1 are the middle bbs to MERGE edges.
3664 : EARLY_P is set when the first phiopt is run.
3665 : BEFORE_VECT is true if this is before vectorization, where some extra checks
3666 : are needed for profitability.
3667 : Returns true if a load was factored out. */
3668 :
3669 : static bool
3670 972206 : factor_out_conditional_load (edge e0, edge e1, basic_block merge, gphi *phi,
3671 : bool early_p, bool before_vect)
3672 : {
3673 : /* Factoring out a load during the first phi means we can't
3674 : trust if this is inside a loop or not; due to before inlining. */
3675 972206 : if (early_p)
3676 : return false;
3677 :
3678 : /* Before vectorization, we don't want to factor out loads unless not inside a loop. */
3679 772155 : if (before_vect && bb_loop_depth (merge) != 0)
3680 : return false;
3681 :
3682 : /* Not a virtual operand. */
3683 787783 : if (virtual_operand_p (gimple_phi_result (phi))
3684 : /* can only handle the merge bb having 2 predecessors. */
3685 787783 : || gimple_phi_num_args (phi) != 2)
3686 : return false;
3687 :
3688 153674 : tree arg0 = gimple_phi_arg_def (phi, e0->dest_idx);
3689 153674 : tree arg1 = gimple_phi_arg_def (phi, e1->dest_idx);
3690 : /* The load needs to be only used in the phi. */
3691 136249 : if (TREE_CODE (arg0) != SSA_NAME || TREE_CODE (arg1) != SSA_NAME
3692 276166 : || !has_single_use (arg0) || !has_single_use (arg1))
3693 : return false;
3694 :
3695 : /* Re-derive the loads and pointers validated by the predicate above. */
3696 63148 : gimple *load0 = SSA_NAME_DEF_STMT (arg0);
3697 63148 : gimple *load1 = SSA_NAME_DEF_STMT (arg1);
3698 :
3699 : /* Load have to need to be in the middle bbs. */
3700 63148 : if (gimple_bb (load0) != e0->src
3701 63148 : || gimple_bb (load1) != e1->src)
3702 : return false;
3703 :
3704 : /* The load needs to be a load with NO volatile ops. */
3705 80132 : if (!gimple_assign_load_p (load0) || !gimple_assign_load_p (load1)
3706 91845 : || gimple_has_volatile_ops (load0) || gimple_has_volatile_ops (load1))
3707 43279 : return false;
3708 :
3709 : /* Allow for stores/calls before the load. */
3710 16187 : if (gphi *vphi = get_virtual_phi (merge))
3711 : {
3712 23654 : if (gimple_vuse (load0) != gimple_phi_arg_def (vphi, e0->dest_idx)
3713 20557 : || gimple_vuse (load1) != gimple_phi_arg_def (vphi, e1->dest_idx))
3714 : return false;
3715 : }
3716 : /* Sometimes due to not removing dead statements,
3717 : a virtual phi does not show up going into an infinite loop
3718 : so just reject that case. */
3719 13080 : else if (gimple_vuse (load0) != gimple_vuse (load1))
3720 : return false;
3721 :
3722 13053 : tree ref0 = gimple_assign_rhs1 (load0);
3723 13053 : tree ref1 = gimple_assign_rhs1 (load1);
3724 :
3725 : /* Both must be *P loads of a compatible value type. The
3726 : TBAA alias-ptr type carried by MEM_REF operand 1 need not match; it is
3727 : merged the way get_alias_type_for_stmts does when the load is built. */
3728 5057 : if (TREE_CODE (ref0) != MEM_REF || TREE_CODE (ref1) != MEM_REF
3729 17945 : || !types_compatible_p (TREE_TYPE (ref0), TREE_TYPE (ref1)))
3730 8161 : return false;
3731 :
3732 : /* The alignment of the two accesses need to be the same. */
3733 4892 : if (TYPE_ALIGN (TREE_TYPE (ref0)) != TYPE_ALIGN (TREE_TYPE (ref1)))
3734 : return false;
3735 :
3736 4649 : tree p0 = TREE_OPERAND (ref0, 0);
3737 4649 : tree p1 = TREE_OPERAND (ref1, 0);
3738 4649 : if (!is_factor_profitable (load0, merge, &p0, 1))
3739 : return false;
3740 4631 : if (!is_factor_profitable (load1, merge, &p1, 1))
3741 : return false;
3742 :
3743 : /* Merge the two arms' TBAA info as get_alias_type_for_stmts does: keep the
3744 : common alias-ptr type and dependence clique/base when the arms agree,
3745 : otherwise fall back to ptr_type_node (alias-everything) and drop the
3746 : clique/base, so the combined load conservatively conflicts with any store
3747 : either original arm could. */
3748 4631 : unsigned short clique = MR_DEPENDENCE_CLIQUE (ref0);
3749 4631 : unsigned short base = MR_DEPENDENCE_BASE (ref0);
3750 4631 : if (clique != MR_DEPENDENCE_CLIQUE (ref1) || base != MR_DEPENDENCE_BASE (ref1))
3751 : clique = base = 0;
3752 4631 : tree atype = TREE_TYPE (TREE_OPERAND (ref0, 1));
3753 4631 : if (!alias_ptr_types_compatible_p (atype, TREE_TYPE (TREE_OPERAND (ref1, 1))))
3754 : {
3755 588 : atype = ptr_type_node;
3756 588 : clique = base = 0;
3757 : }
3758 :
3759 4631 : tree index0 = TREE_OPERAND (ref0, 1);
3760 4631 : tree index1 = TREE_OPERAND (ref1, 1);
3761 4631 : tree newindex;
3762 4631 : gimple_stmt_iterator gsi;
3763 4631 : gsi = gsi_after_labels (merge);
3764 :
3765 : /* Try to handle different indices. */
3766 4631 : if (operand_equal_p (index0, index1))
3767 4098 : newindex = fold_convert (atype, index0);
3768 : /* FIXME: right now non ssa names with different indices are not handled. */
3769 533 : else if (TREE_CODE (p0) != SSA_NAME || TREE_CODE (p1) != SSA_NAME)
3770 : return false;
3771 : /* If we have the same base already, just create a phi for the index
3772 : and the pointer plus will be done in the merge. */
3773 68 : else if (p0 == p1)
3774 : {
3775 52 : index0 = fold_convert (sizetype, index0);
3776 52 : index1 = fold_convert (sizetype, index1);
3777 52 : tree index = make_ssa_name (sizetype);
3778 52 : gphi *pphi = create_phi_node (index, merge);
3779 52 : add_phi_arg (pphi, index0, e0, gimple_phi_arg_location (phi, e0->dest_idx));
3780 52 : add_phi_arg (pphi, index1, e1, gimple_phi_arg_location (phi, e1->dest_idx));
3781 52 : p0 = gimple_build (&gsi, true, GSI_SAME_STMT,
3782 : UNKNOWN_LOCATION,
3783 : POINTER_PLUS_EXPR, atype, p0, index);
3784 : /* Since we already have the same pointer for both, just set that way.
3785 : Also the index offset is already 0 because we just did the add. */
3786 52 : p1 = p0;
3787 52 : newindex = build_zero_cst (atype);
3788 52 : if (dump_file && (dump_flags & TDF_DETAILS))
3789 : {
3790 1 : fprintf (dump_file, "new PHI ");
3791 1 : print_generic_expr (dump_file, index);
3792 1 : fprintf (dump_file,
3793 : " was created for the index.\n");
3794 : }
3795 : }
3796 : else
3797 : {
3798 16 : gimple_stmt_iterator gsi_index;
3799 : /* When the indices are different create 2 new pointers on each
3800 : of the middle bb right after the original load.
3801 : Note in the case of 0 index, gimple_build just returns
3802 : the original pointer. */
3803 16 : gsi_index = gsi_for_stmt (load0);
3804 16 : index0 = fold_convert (sizetype, index0);
3805 16 : p0 = gimple_build (&gsi_index, false, GSI_SAME_STMT,
3806 : gimple_location (load0),
3807 : POINTER_PLUS_EXPR, atype, p0, index0);
3808 :
3809 16 : gsi_index = gsi_for_stmt (load1);
3810 16 : index1 = fold_convert (sizetype, index1);
3811 16 : p1 = gimple_build (&gsi_index, false, GSI_SAME_STMT,
3812 : gimple_location (load1),
3813 : POINTER_PLUS_EXPR, atype, p1, index1);
3814 16 : newindex = build_zero_cst (atype);
3815 16 : if (dump_file && (dump_flags & TDF_DETAILS))
3816 : {
3817 1 : fprintf (dump_file, "new ptrs ");
3818 1 : print_generic_expr (dump_file, p0);
3819 1 : fprintf (dump_file, " and ");
3820 1 : print_generic_expr (dump_file, p1);
3821 1 : fprintf (dump_file,
3822 : " was created due to different offsets.\n");
3823 : }
3824 : }
3825 :
3826 4166 : tree newptr;
3827 4166 : if (p0 != p1)
3828 : {
3829 : /* We can't factor out a non-ssa named based load
3830 : as it might cause a variable not taken an
3831 : address to become needing the address taken.
3832 : An example is in go.
3833 : Were we produce:
3834 : _24 = PHI <&crypto/tls.cipherSuitesPreferenceOrder(36), &crypto/tls.cipherSuitesPreferenceOrderNoAES(37)>
3835 : And &crypto/tls.cipherSuitesPreferenceOrder address bit was not set.
3836 : FIXME: Refine to check ADDRESSABLE bit. */
3837 2777 : if (TREE_CODE (p0) != SSA_NAME || TREE_CODE (p1) != SSA_NAME)
3838 : return false;
3839 : /* Build P' = PHI <P, Q> and the single load result = *P'. */
3840 301 : newptr = make_ssa_name (TREE_TYPE (p0));
3841 301 : gphi *pphi = create_phi_node (newptr, merge);
3842 301 : add_phi_arg (pphi, p0, e0, gimple_phi_arg_location (phi, e0->dest_idx));
3843 301 : add_phi_arg (pphi, p1, e1, gimple_phi_arg_location (phi, e1->dest_idx));
3844 : }
3845 : else
3846 : newptr = p0;
3847 :
3848 : /* Build the combined load RES = *PTR, reusing the PHI result so any range
3849 : info on it is preserved (as factor_out_conditional_operation does). */
3850 1690 : tree nref = build2 (MEM_REF, TREE_TYPE (ref0), newptr, newindex);
3851 1690 : MR_DEPENDENCE_CLIQUE (nref) = clique;
3852 1690 : MR_DEPENDENCE_BASE (nref) = base;
3853 1690 : tree res = gimple_phi_result (phi);
3854 1690 : gassign *load = gimple_build_assign (res, nref);
3855 1690 : if (gphi *vphi = get_virtual_phi (merge))
3856 1381 : gimple_set_vuse (load, gimple_phi_result (vphi));
3857 : else
3858 618 : gimple_set_vuse (load, gimple_vuse (load0));
3859 1690 : gsi_insert_before (&gsi, load, GSI_SAME_STMT);
3860 :
3861 : /* RES is now defined by the load; drop the original PHI. */
3862 1690 : gsi = gsi_for_stmt (phi);
3863 1690 : remove_phi_node (&gsi, false);
3864 :
3865 : /* The two arm loads are now dead. */
3866 1690 : gsi = gsi_for_stmt (load0);
3867 1690 : gsi_remove (&gsi, true);
3868 1690 : release_defs (load0);
3869 1690 : gsi = gsi_for_stmt (load1);
3870 1690 : gsi_remove (&gsi, true);
3871 1690 : release_defs (load1);
3872 :
3873 1690 : if (dump_file && (dump_flags & TDF_DETAILS))
3874 : {
3875 7 : fprintf (dump_file, "PHI ");
3876 7 : print_generic_expr (dump_file, res);
3877 7 : fprintf (dump_file,
3878 : " changed to factor out load from COND_EXPR.\n");
3879 7 : if (p0 != p1)
3880 : {
3881 6 : fprintf (dump_file, "new PHI ");
3882 6 : print_generic_expr (dump_file, newptr);
3883 6 : fprintf (dump_file,
3884 : " was created for the pointers.\n");
3885 : }
3886 : }
3887 :
3888 1690 : statistics_counter_event (cfun, "factored load out of COND_EXPR", 1);
3889 1690 : return true;
3890 : }
3891 :
3892 : /* Factor out operations and stores from the phi of the MERGE block coming
3893 : in from the edges E1 and E2 if possible. COND_STMT is the conditional
3894 : statement of the origin block. DIAMOND_P says that both E1 and E2 src
3895 : are not the origin block but rather 2 middle BBs. EARLY_P is true if
3896 : this was the early phi-opt.
3897 : Returns true if a factoring happened. */
3898 : static bool
3899 2544958 : factor_out_all (edge e1, edge e2, basic_block merge,
3900 : gcond *cond_stmt, bool diamond_p, bool early_p)
3901 : {
3902 2544958 : bool changed = false;
3903 2544958 : bool do_over;
3904 2544958 : basic_block bb1 = e1->src;
3905 2544958 : basic_block bb2 = e2->src;
3906 2518182 : do
3907 : {
3908 2587747 : do_over = false;
3909 2587747 : if (diamond_p && get_virtual_phi (merge))
3910 : {
3911 709119 : if (cond_if_else_store_replacement_limited (bb1, bb2, merge))
3912 : {
3913 13154 : changed = true;
3914 13154 : do_over = true;
3915 13154 : continue;
3916 : }
3917 : }
3918 2574593 : if (!single_pred_p (bb1))
3919 : break;
3920 2505028 : gphi_iterator gsi;
3921 5537490 : for (gsi = gsi_start_phis (merge); !gsi_end_p (gsi); gsi_next (&gsi))
3922 : {
3923 3062097 : gphi *phi = *gsi;
3924 : /* Conditional load elimination can only be on a diamond. */
3925 3062097 : if ((diamond_p
3926 972206 : && factor_out_conditional_load (e1, e2, merge, phi, early_p,
3927 972206 : !fold_before_rtl_expansion_p ()))
3928 4032613 : || factor_out_conditional_operation (e1, e2, merge, phi,
3929 : cond_stmt, early_p))
3930 : {
3931 : changed = true;
3932 : do_over = true;
3933 : break;
3934 : }
3935 : }
3936 : } while (do_over);
3937 2544958 : return changed;
3938 : }
3939 :
3940 : /* Return TRUE if STMT has a VUSE whose corresponding VDEF is in BB. */
3941 :
3942 : static bool
3943 12134 : local_mem_dependence (gimple *stmt, basic_block bb)
3944 : {
3945 24268 : tree vuse = gimple_vuse (stmt);
3946 12134 : gimple *def;
3947 :
3948 12134 : if (!vuse)
3949 : return false;
3950 :
3951 12134 : def = SSA_NAME_DEF_STMT (vuse);
3952 12134 : return (def && gimple_bb (def) == bb);
3953 : }
3954 :
3955 : /* Given a "diamond" control-flow pattern where BB0 tests a condition,
3956 : BB1 and BB2 are "then" and "else" blocks dependent on this test,
3957 : and BB3 rejoins control flow following BB1 and BB2, look for
3958 : opportunities to hoist loads as follows. If BB3 contains a PHI of
3959 : two loads, one each occurring in BB1 and BB2, and the loads are
3960 : provably of adjacent fields in the same structure, then move both
3961 : loads into BB0. Of course this can only be done if there are no
3962 : dependencies preventing such motion.
3963 :
3964 : One of the hoisted loads will always be speculative, so the
3965 : transformation is currently conservative:
3966 :
3967 : - The fields must be strictly adjacent.
3968 : - The two fields must occupy a single memory block that is
3969 : guaranteed to not cross a page boundary.
3970 :
3971 : The last is difficult to prove, as such memory blocks should be
3972 : aligned on the minimum of the stack alignment boundary and the
3973 : alignment guaranteed by heap allocation interfaces. Thus we rely
3974 : on a parameter for the alignment value.
3975 :
3976 : Provided a good value is used for the last case, the first
3977 : restriction could possibly be relaxed. */
3978 :
3979 : static void
3980 592538 : hoist_adjacent_loads (basic_block bb0, basic_block bb1,
3981 : basic_block bb2, basic_block bb3)
3982 : {
3983 592538 : unsigned HOST_WIDE_INT param_align = param_l1_cache_line_size;
3984 592538 : unsigned HOST_WIDE_INT param_align_bits = param_align * BITS_PER_UNIT;
3985 592538 : gphi_iterator gsi;
3986 :
3987 : /* Walk the phis in bb3 looking for an opportunity. We are looking
3988 : for phis of two SSA names, one each of which is defined in bb1 and
3989 : bb2. */
3990 1319241 : for (gsi = gsi_start_phis (bb3); !gsi_end_p (gsi); gsi_next (&gsi))
3991 : {
3992 726703 : gphi *phi_stmt = gsi.phi ();
3993 726703 : gimple *def1, *def2;
3994 726703 : tree arg1, arg2, ref1, ref2, field1, field2;
3995 726703 : tree tree_offset1, tree_offset2, tree_size2, next;
3996 726703 : unsigned HOST_WIDE_INT offset1, offset2, size2, align1;
3997 726703 : gimple_stmt_iterator gsi2;
3998 726703 : basic_block bb_for_def1, bb_for_def2;
3999 :
4000 726703 : if (gimple_phi_num_args (phi_stmt) != 2
4001 1453406 : || virtual_operand_p (gimple_phi_result (phi_stmt)))
4002 720636 : continue;
4003 :
4004 174828 : arg1 = gimple_phi_arg_def (phi_stmt, 0);
4005 174828 : arg2 = gimple_phi_arg_def (phi_stmt, 1);
4006 :
4007 208384 : if (TREE_CODE (arg1) != SSA_NAME
4008 157284 : || TREE_CODE (arg2) != SSA_NAME
4009 142532 : || SSA_NAME_IS_DEFAULT_DEF (arg1)
4010 317036 : || SSA_NAME_IS_DEFAULT_DEF (arg2))
4011 33556 : continue;
4012 :
4013 141272 : def1 = SSA_NAME_DEF_STMT (arg1);
4014 141272 : def2 = SSA_NAME_DEF_STMT (arg2);
4015 :
4016 141272 : if ((gimple_bb (def1) != bb1 || gimple_bb (def2) != bb2)
4017 155817 : && (gimple_bb (def2) != bb1 || gimple_bb (def1) != bb2))
4018 41703 : continue;
4019 :
4020 : /* Check the mode of the arguments to be sure a conditional move
4021 : can be generated for it. */
4022 199138 : if (optab_handler (movcc_optab, TYPE_MODE (TREE_TYPE (arg1)))
4023 : == CODE_FOR_nothing)
4024 6013 : continue;
4025 :
4026 : /* Both statements must be assignments whose RHS is a COMPONENT_REF. */
4027 93556 : if (!gimple_assign_single_p (def1)
4028 44914 : || !gimple_assign_single_p (def2)
4029 53850 : || gimple_has_volatile_ops (def1)
4030 147400 : || gimple_has_volatile_ops (def2))
4031 66634 : continue;
4032 :
4033 26922 : ref1 = gimple_assign_rhs1 (def1);
4034 26922 : ref2 = gimple_assign_rhs1 (def2);
4035 :
4036 26922 : if (TREE_CODE (ref1) != COMPONENT_REF
4037 15635 : || TREE_CODE (ref2) != COMPONENT_REF)
4038 11410 : continue;
4039 :
4040 : /* The zeroth operand of the two component references must be
4041 : identical. It is not sufficient to compare get_base_address of
4042 : the two references, because this could allow for different
4043 : elements of the same array in the two trees. It is not safe to
4044 : assume that the existence of one array element implies the
4045 : existence of a different one. */
4046 15512 : if (!operand_equal_p (TREE_OPERAND (ref1, 0), TREE_OPERAND (ref2, 0), 0))
4047 4593 : continue;
4048 :
4049 10919 : field1 = TREE_OPERAND (ref1, 1);
4050 10919 : field2 = TREE_OPERAND (ref2, 1);
4051 :
4052 : /* Check for field adjacency, and ensure field1 comes first. */
4053 10919 : for (next = DECL_CHAIN (field1);
4054 25019 : next && TREE_CODE (next) != FIELD_DECL;
4055 14100 : next = DECL_CHAIN (next))
4056 : ;
4057 :
4058 10919 : if (next != field2)
4059 : {
4060 7311 : for (next = DECL_CHAIN (field2);
4061 9312 : next && TREE_CODE (next) != FIELD_DECL;
4062 2001 : next = DECL_CHAIN (next))
4063 : ;
4064 :
4065 7311 : if (next != field1)
4066 4852 : continue;
4067 :
4068 : std::swap (field1, field2);
4069 : std::swap (def1, def2);
4070 : }
4071 :
4072 6067 : bb_for_def1 = gimple_bb (def1);
4073 6067 : bb_for_def2 = gimple_bb (def2);
4074 :
4075 : /* Check for proper alignment of the first field. */
4076 6067 : tree_offset1 = bit_position (field1);
4077 6067 : tree_offset2 = bit_position (field2);
4078 6067 : tree_size2 = DECL_SIZE (field2);
4079 :
4080 6067 : if (!tree_fits_uhwi_p (tree_offset1)
4081 6067 : || !tree_fits_uhwi_p (tree_offset2)
4082 6067 : || !tree_fits_uhwi_p (tree_size2))
4083 0 : continue;
4084 :
4085 6067 : offset1 = tree_to_uhwi (tree_offset1);
4086 6067 : offset2 = tree_to_uhwi (tree_offset2);
4087 6067 : size2 = tree_to_uhwi (tree_size2);
4088 6067 : align1 = DECL_ALIGN (field1) % param_align_bits;
4089 :
4090 6067 : if (offset1 % BITS_PER_UNIT != 0)
4091 0 : continue;
4092 :
4093 : /* For profitability, the two field references should fit within
4094 : a single cache line. */
4095 6067 : if (align1 + offset2 - offset1 + size2 > param_align_bits)
4096 0 : continue;
4097 :
4098 : /* The two expressions cannot be dependent upon vdefs defined
4099 : in bb1/bb2. */
4100 6067 : if (local_mem_dependence (def1, bb_for_def1)
4101 6067 : || local_mem_dependence (def2, bb_for_def2))
4102 0 : continue;
4103 :
4104 : /* The conditions are satisfied; hoist the loads from bb1 and bb2 into
4105 : bb0. We hoist the first one first so that a cache miss is handled
4106 : efficiently regardless of hardware cache-fill policy. */
4107 6067 : gsi2 = gsi_for_stmt (def1);
4108 6067 : gsi_move_to_bb_end (&gsi2, bb0);
4109 6067 : gsi2 = gsi_for_stmt (def2);
4110 6067 : gsi_move_to_bb_end (&gsi2, bb0);
4111 6067 : statistics_counter_event (cfun, "hoisted loads", 1);
4112 :
4113 6067 : if (dump_file && (dump_flags & TDF_DETAILS))
4114 : {
4115 0 : fprintf (dump_file,
4116 : "\nHoisting adjacent loads from %d and %d into %d: \n",
4117 : bb_for_def1->index, bb_for_def2->index, bb0->index);
4118 0 : print_gimple_stmt (dump_file, def1, 0, TDF_VOPS|TDF_MEMSYMS);
4119 0 : print_gimple_stmt (dump_file, def2, 0, TDF_VOPS|TDF_MEMSYMS);
4120 : }
4121 : }
4122 592538 : }
4123 :
4124 : /* Determine whether we should attempt to hoist adjacent loads out of
4125 : diamond patterns in pass_phiopt. Always hoist loads if
4126 : -fhoist-adjacent-loads is specified and the target machine has
4127 : both a conditional move instruction and a defined cache line size. */
4128 :
4129 : static bool
4130 3164936 : gate_hoist_loads (void)
4131 : {
4132 3164936 : return (flag_hoist_adjacent_loads == 1
4133 3164936 : && param_l1_cache_line_size
4134 0 : && HAVE_conditional_move);
4135 : }
4136 :
4137 : template <class func_type>
4138 : static void
4139 6745290 : execute_over_cond_phis (func_type func)
4140 : {
4141 : unsigned n, i;
4142 : basic_block *bb_order;
4143 : basic_block bb;
4144 : /* Search every basic block for COND_EXPR we may be able to optimize.
4145 :
4146 : We walk the blocks in order that guarantees that a block with
4147 : a single predecessor is processed before the predecessor.
4148 : This ensures that we collapse inner ifs before visiting the
4149 : outer ones, and also that we do not try to visit a removed
4150 : block. */
4151 6745290 : bb_order = single_pred_before_succ_order ();
4152 6745290 : n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
4153 :
4154 60570844 : for (i = 0; i < n; i++)
4155 : {
4156 : basic_block bb1, bb2;
4157 : edge e1, e2;
4158 53825554 : bool diamond_p = false;
4159 :
4160 53825554 : bb = bb_order[i];
4161 :
4162 : /* Check to see if the last statement is a GIMPLE_COND. */
4163 53825554 : gcond *cond_stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
4164 32151732 : if (!cond_stmt)
4165 53825554 : continue;
4166 :
4167 21673822 : e1 = EDGE_SUCC (bb, 0);
4168 21673822 : bb1 = e1->dest;
4169 21673822 : e2 = EDGE_SUCC (bb, 1);
4170 21673822 : bb2 = e2->dest;
4171 :
4172 : /* We cannot do the optimization on abnormal edges. */
4173 21673822 : if ((e1->flags & EDGE_ABNORMAL) != 0
4174 21673822 : || (e2->flags & EDGE_ABNORMAL) != 0)
4175 0 : continue;
4176 :
4177 : /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
4178 21673822 : if (EDGE_COUNT (bb1->succs) == 0
4179 20189963 : || EDGE_COUNT (bb2->succs) == 0)
4180 4993759 : continue;
4181 :
4182 : /* Find the bb which is the fall through to the other. */
4183 16680063 : if (EDGE_SUCC (bb1, 0)->dest == bb2)
4184 : ;
4185 14161399 : else if (EDGE_SUCC (bb2, 0)->dest == bb1)
4186 : {
4187 : std::swap (bb1, bb2);
4188 : std::swap (e1, e2);
4189 : }
4190 10784016 : else if (EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest
4191 12344936 : && single_succ_p (bb2))
4192 : {
4193 1560920 : diamond_p = true;
4194 1560920 : e2 = EDGE_SUCC (bb2, 0);
4195 : /* Make sure bb2 is just a fall through. */
4196 1560920 : if ((e2->flags & EDGE_FALLTHRU) == 0)
4197 52239 : continue;
4198 : }
4199 : else
4200 10784016 : continue;
4201 :
4202 5843808 : e1 = EDGE_SUCC (bb1, 0);
4203 :
4204 : /* Make sure that bb1 is just a fall through. */
4205 5843808 : if (!single_succ_p (bb1)
4206 5843808 : || (e1->flags & EDGE_FALLTHRU) == 0)
4207 1386156 : continue;
4208 :
4209 4457652 : func (bb, bb1, bb2, e1, e2, diamond_p, cond_stmt);
4210 : }
4211 6745290 : free (bb_order);
4212 6745290 : }
4213 :
4214 : /* This pass tries to replaces an if-then-else block with an
4215 : assignment. We have different kinds of transformations.
4216 : Some of these transformations are also performed by the ifcvt
4217 : RTL optimizer.
4218 :
4219 : PHI-OPT using Match-and-simplify infrastructure
4220 : -----------------------
4221 :
4222 : The PHI-OPT pass will try to use match-and-simplify infrastructure
4223 : (gimple_simplify) to do transformations. This is implemented in
4224 : match_simplify_replacement.
4225 :
4226 : The way it works is it replaces:
4227 : bb0:
4228 : if (cond) goto bb2; else goto bb1;
4229 : bb1:
4230 : bb2:
4231 : x = PHI <a (bb1), b (bb0), ...>;
4232 :
4233 : with a statement if it gets simplified from `cond ? b : a`.
4234 :
4235 : bb0:
4236 : x1 = cond ? b : a;
4237 : bb2:
4238 : x = PHI <a (bb1), x1 (bb0), ...>;
4239 : Bb1 might be removed as it becomes unreachable when doing the replacement.
4240 : Though bb1 does not have to be considered a forwarding basic block from bb0.
4241 :
4242 : Will try to see if `(!cond) ? a : b` gets simplified (iff !cond simplifies);
4243 : this is done not to have an explosion of patterns in match.pd.
4244 : Note bb1 does not need to be completely empty, it can contain
4245 : one statement which is known not to trap.
4246 :
4247 : It also can handle the case where we have two forwarding bbs (diamond):
4248 : bb0:
4249 : if (cond) goto bb2; else goto bb1;
4250 : bb1: goto bb3;
4251 : bb2: goto bb3;
4252 : bb3:
4253 : x = PHI <a (bb1), b (bb2), ...>;
4254 : And that is replaced with a statement if it is simplified
4255 : from `cond ? b : a`.
4256 : Again bb1 and bb2 does not have to be completely empty but
4257 : each can contain one statement which is known not to trap.
4258 : But in this case bb1/bb2 can only be forwarding basic blocks.
4259 :
4260 : This fully replaces the old "Conditional Replacement",
4261 : "ABS Replacement" and "MIN/MAX Replacement" transformations as they are now
4262 : implemented in match.pd.
4263 :
4264 : Value Replacement
4265 : -----------------
4266 :
4267 : This transformation, implemented in value_replacement, replaces
4268 :
4269 : bb0:
4270 : if (a != b) goto bb2; else goto bb1;
4271 : bb1:
4272 : bb2:
4273 : x = PHI <a (bb1), b (bb0), ...>;
4274 :
4275 : with
4276 :
4277 : bb0:
4278 : bb2:
4279 : x = PHI <b (bb0), ...>;
4280 :
4281 : This opportunity can sometimes occur as a result of other
4282 : optimizations.
4283 :
4284 :
4285 : Another case caught by value replacement looks like this:
4286 :
4287 : bb0:
4288 : t1 = a == CONST;
4289 : t2 = b > c;
4290 : t3 = t1 & t2;
4291 : if (t3 != 0) goto bb1; else goto bb2;
4292 : bb1:
4293 : bb2:
4294 : x = PHI (CONST, a)
4295 :
4296 : Gets replaced with:
4297 : bb0:
4298 : bb2:
4299 : t1 = a == CONST;
4300 : t2 = b > c;
4301 : t3 = t1 & t2;
4302 : x = a;
4303 :
4304 :
4305 : This pass also performs a fifth transformation of a slightly different
4306 : flavor.
4307 :
4308 : Factor operations in COND_EXPR
4309 : ------------------------------
4310 :
4311 : This transformation factors the unary operations out of COND_EXPR with
4312 : factor_out_conditional_operation.
4313 :
4314 : For example:
4315 : if (a <= CST) goto <bb 3>; else goto <bb 4>;
4316 : <bb 3>:
4317 : tmp = (int) a;
4318 : <bb 4>:
4319 : tmp = PHI <tmp, CST>
4320 :
4321 : Into:
4322 : if (a <= CST) goto <bb 3>; else goto <bb 4>;
4323 : <bb 3>:
4324 : <bb 4>:
4325 : a = PHI <a, CST>
4326 : tmp = (int) a;
4327 :
4328 : Adjacent Load Hoisting
4329 : ----------------------
4330 :
4331 : This transformation replaces
4332 :
4333 : bb0:
4334 : if (...) goto bb2; else goto bb1;
4335 : bb1:
4336 : x1 = (<expr>).field1;
4337 : goto bb3;
4338 : bb2:
4339 : x2 = (<expr>).field2;
4340 : bb3:
4341 : # x = PHI <x1, x2>;
4342 :
4343 : with
4344 :
4345 : bb0:
4346 : x1 = (<expr>).field1;
4347 : x2 = (<expr>).field2;
4348 : if (...) goto bb2; else goto bb1;
4349 : bb1:
4350 : goto bb3;
4351 : bb2:
4352 : bb3:
4353 : # x = PHI <x1, x2>;
4354 :
4355 : The purpose of this transformation is to enable generation of conditional
4356 : move instructions such as Intel CMOVE or PowerPC ISEL. Because one of
4357 : the loads is speculative, the transformation is restricted to very
4358 : specific cases to avoid introducing a page fault. We are looking for
4359 : the common idiom:
4360 :
4361 : if (...)
4362 : x = y->left;
4363 : else
4364 : x = y->right;
4365 :
4366 : where left and right are typically adjacent pointers in a tree structure. */
4367 :
4368 : namespace {
4369 :
4370 : const pass_data pass_data_phiopt =
4371 : {
4372 : GIMPLE_PASS, /* type */
4373 : "phiopt", /* name */
4374 : OPTGROUP_NONE, /* optinfo_flags */
4375 : TV_TREE_PHIOPT, /* tv_id */
4376 : ( PROP_cfg | PROP_ssa ), /* properties_required */
4377 : 0, /* properties_provided */
4378 : 0, /* properties_destroyed */
4379 : 0, /* todo_flags_start */
4380 : 0, /* todo_flags_finish */
4381 : };
4382 :
4383 : class pass_phiopt : public gimple_opt_pass
4384 : {
4385 : public:
4386 1169484 : pass_phiopt (gcc::context *ctxt)
4387 2338968 : : gimple_opt_pass (pass_data_phiopt, ctxt), early_p (false)
4388 : {}
4389 :
4390 : /* opt_pass methods: */
4391 877113 : opt_pass * clone () final override { return new pass_phiopt (m_ctxt); }
4392 1169484 : void set_pass_param (unsigned n, bool param) final override
4393 : {
4394 1169484 : gcc_assert (n == 0);
4395 1169484 : early_p = param;
4396 1169484 : }
4397 5693500 : bool gate (function *) final override { return flag_ssa_phiopt; }
4398 : unsigned int execute (function *) final override;
4399 :
4400 : private:
4401 : bool early_p;
4402 : }; // class pass_phiopt
4403 :
4404 : } // anon namespace
4405 :
4406 : gimple_opt_pass *
4407 292371 : make_pass_phiopt (gcc::context *ctxt)
4408 : {
4409 292371 : return new pass_phiopt (ctxt);
4410 : }
4411 :
4412 : unsigned int
4413 5690281 : pass_phiopt::execute (function *)
4414 : {
4415 5690281 : bool do_hoist_loads = !early_p ? gate_hoist_loads () : false;
4416 5690281 : bool cfgchanged = false;
4417 :
4418 5690281 : calculate_dominance_info (CDI_DOMINATORS);
4419 5690281 : mark_ssa_maybe_undefs ();
4420 :
4421 9213608 : auto phiopt_exec = [&] (basic_block bb, basic_block bb1,
4422 : basic_block bb2, edge e1, edge e2,
4423 : bool diamond_p, gcond *cond_stmt)
4424 : {
4425 3523327 : if (diamond_p)
4426 : {
4427 1116427 : basic_block bb3 = e1->dest;
4428 :
4429 1116427 : if (!single_pred_p (bb1)
4430 2172818 : || !single_pred_p (bb2))
4431 2658913 : return;
4432 :
4433 995734 : if (do_hoist_loads
4434 780050 : && !FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt)))
4435 772255 : && EDGE_COUNT (bb->succs) == 2
4436 772255 : && EDGE_COUNT (bb3->preds) == 2
4437 : /* If one edge or the other is dominant, a conditional move
4438 : is likely to perform worse than the well-predicted branch. */
4439 596965 : && !predictable_edge_p (EDGE_SUCC (bb, 0))
4440 1588272 : && !predictable_edge_p (EDGE_SUCC (bb, 1)))
4441 592538 : hoist_adjacent_loads (bb, bb1, bb2, bb3);
4442 : }
4443 :
4444 995734 : gimple_stmt_iterator gsi;
4445 :
4446 : /* Check that we're looking for nested phis. */
4447 995734 : basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest : bb2;
4448 :
4449 : /* Factor out operations from the phi if possible. */
4450 3402634 : if (EDGE_COUNT (merge->preds) == 2
4451 3402634 : && !optimize_debug && factor_out_all (e1, e2, merge, cond_stmt, diamond_p, early_p))
4452 35976 : cfgchanged = true;
4453 :
4454 3402634 : gimple_seq phis = phi_nodes (merge);
4455 :
4456 3402634 : if (gimple_seq_empty_p (phis))
4457 : return;
4458 :
4459 : /* Value replacement can work with more than one PHI
4460 : so try that first. */
4461 3388395 : if (!early_p && !diamond_p)
4462 4260366 : for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
4463 : {
4464 2477174 : gphi *phi = as_a <gphi *> (gsi_stmt (gsi));
4465 2477174 : tree arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
4466 2477174 : tree arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
4467 2477174 : if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1) == 2)
4468 : {
4469 1661 : cfgchanged = true;
4470 1661 : return;
4471 : }
4472 : }
4473 :
4474 3386734 : gphi *phi = single_non_singleton_phi_for_edges (phis, e1, e2);
4475 3386734 : if (!phi)
4476 : return;
4477 :
4478 864414 : tree arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
4479 864414 : tree arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
4480 :
4481 : /* Something is wrong if we cannot find the arguments in the PHI
4482 : node. */
4483 864414 : gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
4484 :
4485 :
4486 : /* Do the replacement of conditional if it can be done. */
4487 864414 : if (match_simplify_replacement (bb, bb1, bb2, e1, e2, phi,
4488 864414 : arg0, arg1, early_p, diamond_p))
4489 95619 : cfgchanged = true;
4490 768795 : else if (!early_p
4491 506930 : && !diamond_p
4492 475097 : && single_pred_p (bb1)
4493 1224440 : && cond_removal_in_builtin_zero_pattern (bb, bb1, e1, e2,
4494 : phi, arg0, arg1))
4495 13 : cfgchanged = true;
4496 1633196 : else if (single_pred_p (bb1)
4497 718961 : && !diamond_p
4498 1425474 : && spaceship_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
4499 2318 : cfgchanged = true;
4500 5690281 : };
4501 :
4502 5690281 : execute_over_cond_phis (phiopt_exec);
4503 :
4504 5690281 : if (cfgchanged)
4505 89382 : return TODO_cleanup_cfg;
4506 : return 0;
4507 : }
4508 :
4509 : /* This pass tries to transform conditional stores into unconditional
4510 : ones, enabling further simplifications with the simpler then and else
4511 : blocks. In particular it replaces this:
4512 :
4513 : bb0:
4514 : if (cond) goto bb2; else goto bb1;
4515 : bb1:
4516 : *p = RHS;
4517 : bb2:
4518 :
4519 : with
4520 :
4521 : bb0:
4522 : if (cond) goto bb1; else goto bb2;
4523 : bb1:
4524 : condtmp' = *p;
4525 : bb2:
4526 : condtmp = PHI <RHS, condtmp'>
4527 : *p = condtmp;
4528 :
4529 : This transformation can only be done under several constraints,
4530 : documented below. It also replaces:
4531 :
4532 : bb0:
4533 : if (cond) goto bb2; else goto bb1;
4534 : bb1:
4535 : *p = RHS1;
4536 : goto bb3;
4537 : bb2:
4538 : *p = RHS2;
4539 : bb3:
4540 :
4541 : with
4542 :
4543 : bb0:
4544 : if (cond) goto bb3; else goto bb1;
4545 : bb1:
4546 : bb3:
4547 : condtmp = PHI <RHS1, RHS2>
4548 : *p = condtmp; */
4549 :
4550 : namespace {
4551 :
4552 : const pass_data pass_data_cselim =
4553 : {
4554 : GIMPLE_PASS, /* type */
4555 : "cselim", /* name */
4556 : OPTGROUP_NONE, /* optinfo_flags */
4557 : TV_TREE_PHIOPT, /* tv_id */
4558 : ( PROP_cfg | PROP_ssa ), /* properties_required */
4559 : 0, /* properties_provided */
4560 : 0, /* properties_destroyed */
4561 : 0, /* todo_flags_start */
4562 : 0, /* todo_flags_finish */
4563 : };
4564 :
4565 : class pass_cselim : public gimple_opt_pass
4566 : {
4567 : public:
4568 292371 : pass_cselim (gcc::context *ctxt)
4569 584742 : : gimple_opt_pass (pass_data_cselim, ctxt)
4570 : {}
4571 :
4572 : /* opt_pass methods: */
4573 1055105 : bool gate (function *) final override { return flag_tree_cselim; }
4574 : unsigned int execute (function *) final override;
4575 :
4576 : }; // class pass_cselim
4577 :
4578 : } // anon namespace
4579 :
4580 : gimple_opt_pass *
4581 292371 : make_pass_cselim (gcc::context *ctxt)
4582 : {
4583 292371 : return new pass_cselim (ctxt);
4584 : }
4585 :
4586 : unsigned int
4587 1055009 : pass_cselim::execute (function *)
4588 : {
4589 1055009 : bool cfgchanged = false;
4590 1055009 : hash_set<tree> *nontrap = 0;
4591 1055009 : unsigned todo = 0;
4592 :
4593 : /* ??? We are not interested in loop related info, but the following
4594 : will create it, ICEing as we didn't init loops with pre-headers.
4595 : An interfacing issue of find_data_references_in_bb. */
4596 1055009 : loop_optimizer_init (LOOPS_NORMAL);
4597 1055009 : scev_initialize ();
4598 :
4599 1055009 : calculate_dominance_info (CDI_DOMINATORS);
4600 :
4601 : /* Calculate the set of non-trapping memory accesses. */
4602 1055009 : nontrap = get_non_trapping ();
4603 :
4604 1989334 : auto cselim_exec = [&] (basic_block bb, basic_block bb1,
4605 : basic_block bb2, edge e1, edge e2,
4606 : bool diamond_p, gcond *)
4607 : {
4608 934325 : if (diamond_p)
4609 : {
4610 324920 : basic_block bb3 = e1->dest;
4611 :
4612 : /* Only handle sinking of store from 2 bbs only,
4613 : The middle bbs don't need to come from the
4614 : if always since we are sinking rather than
4615 : hoisting. */
4616 324920 : if (EDGE_COUNT (bb3->preds) != 2)
4617 : return;
4618 240161 : if (cond_if_else_store_replacement (bb1, bb2, bb3))
4619 1003 : cfgchanged = true;
4620 240161 : return;
4621 : }
4622 :
4623 : /* Also make sure that bb1 only have one predecessor and that it
4624 : is bb. */
4625 609405 : if (!single_pred_p (bb1)
4626 1171762 : || single_pred (bb1) != bb)
4627 : return;
4628 :
4629 : /* bb1 is the middle block, bb2 the join block, bb the split block,
4630 : e1 the fallthrough edge from bb1 to bb2. We can't do the
4631 : optimization if the join block has more than two predecessors. */
4632 562357 : if (EDGE_COUNT (bb2->preds) > 2)
4633 : return;
4634 :
4635 437713 : gimple *assign = cselim_candidate (bb1, bb2, e1);
4636 437713 : if (cond_store_replacement (bb1, bb2, e1, e2, assign, nontrap))
4637 6654 : cfgchanged = true;
4638 1055009 : };
4639 :
4640 1055009 : execute_over_cond_phis (cselim_exec);
4641 :
4642 2110018 : delete nontrap;
4643 : /* If the CFG has changed, we should cleanup the CFG. */
4644 1055009 : if (cfgchanged)
4645 : {
4646 4420 : gsi_commit_edge_inserts ();
4647 4420 : todo = TODO_cleanup_cfg;
4648 : }
4649 1055009 : scev_finalize ();
4650 1055009 : loop_optimizer_finalize ();
4651 1055009 : return todo;
4652 : }
|
