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 3424099 : single_non_singleton_phi_for_edges (gimple_seq seq, edge e0, edge e1)
63 : {
64 3424099 : gimple_stmt_iterator i;
65 3424099 : gphi *phi = NULL;
66 5069158 : for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
67 : {
68 4123965 : gphi *p = as_a <gphi *> (gsi_stmt (i));
69 : /* If the PHI arguments are equal then we can skip this PHI. */
70 4123965 : if (operand_equal_for_phi_arg_p (gimple_phi_arg_def (p, e0->dest_idx),
71 4123965 : gimple_phi_arg_def (p, e1->dest_idx)))
72 237874 : continue;
73 :
74 : /* Punt on virtual phis with different arguments from the edges. */
75 7772182 : 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 1647621 : 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 94208 : 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 94208 : basic_block bb = gimple_bb (phi);
98 94208 : gimple_stmt_iterator gsi;
99 94208 : tree phi_result = gimple_phi_result (phi);
100 94208 : 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 94208 : if (TREE_CODE (new_tree) == SSA_NAME
120 94185 : && EDGE_COUNT (gimple_bb (phi)->preds) == 2
121 61340 : && INTEGRAL_TYPE_P (TREE_TYPE (phi_result))
122 56331 : && !SSA_NAME_RANGE_INFO (new_tree)
123 56238 : && SSA_NAME_RANGE_INFO (phi_result)
124 34579 : && gimple_bb (SSA_NAME_DEF_STMT (new_tree)) == cond_block
125 128787 : && dbg_cnt (phiopt_edge_range))
126 34579 : duplicate_ssa_name_range_info (new_tree, phi_result);
127 :
128 : /* Change the PHI argument to new. */
129 94208 : SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);
130 :
131 : /* Remove the empty basic block. */
132 94208 : edge edge_to_remove = NULL, keep_edge = NULL;
133 94208 : if (EDGE_SUCC (cond_block, 0)->dest == bb)
134 : {
135 32493 : edge_to_remove = EDGE_SUCC (cond_block, 1);
136 32493 : keep_edge = EDGE_SUCC (cond_block, 0);
137 : }
138 61715 : 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 1206 : else if ((keep_edge = find_edge (cond_block, e->src)))
144 : {
145 1206 : basic_block bb1 = EDGE_SUCC (cond_block, 0)->dest;
146 1206 : basic_block bb2 = EDGE_SUCC (cond_block, 1)->dest;
147 2412 : if (single_pred_p (bb1) && single_pred_p (bb2)
148 96620 : && single_succ_p (bb1) && single_succ_p (bb2)
149 2412 : && 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 94208 : 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 94208 : if (edge_to_remove && EDGE_COUNT (edge_to_remove->dest->preds) == 1)
166 : {
167 82241 : e->flags |= EDGE_FALLTHRU;
168 82241 : e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
169 82241 : e->probability = profile_probability::always ();
170 82241 : delete_basic_block (edge_to_remove->dest);
171 :
172 : /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
173 82241 : gsi = gsi_last_bb (cond_block);
174 82241 : gsi_remove (&gsi, true);
175 : }
176 11967 : else if (deleteboth)
177 : {
178 1206 : basic_block bb1 = EDGE_SUCC (cond_block, 0)->dest;
179 1206 : basic_block bb2 = EDGE_SUCC (cond_block, 1)->dest;
180 :
181 1206 : edge newedge = redirect_edge_and_branch (keep_edge, bb);
182 :
183 : /* The new edge should be the same. */
184 1206 : gcc_assert (newedge == keep_edge);
185 :
186 1206 : keep_edge->flags |= EDGE_FALLTHRU;
187 1206 : keep_edge->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
188 1206 : keep_edge->probability = profile_probability::always ();
189 :
190 : /* Copy the edge's phi entry from the old one. */
191 1206 : copy_phi_arg_into_existing_phi (e, keep_edge);
192 :
193 : /* Delete the old 2 empty basic blocks */
194 1206 : delete_basic_block (bb1);
195 1206 : delete_basic_block (bb2);
196 :
197 : /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
198 1206 : gsi = gsi_last_bb (cond_block);
199 1206 : 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 21522 : gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_block));
207 10761 : if (keep_edge->flags & EDGE_FALSE_VALUE)
208 7314 : gimple_cond_make_false (cond);
209 3447 : else if (keep_edge->flags & EDGE_TRUE_VALUE)
210 3447 : gimple_cond_make_true (cond);
211 : }
212 :
213 94208 : if (dce_ssa_names)
214 92554 : simple_dce_from_worklist (dce_ssa_names);
215 :
216 94208 : statistics_counter_event (cfun, "Replace PHI with variable", 1);
217 :
218 94208 : 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 94208 : }
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 63169 : is_factor_profitable (gimple *def_stmt, basic_block merge, tree *operands, unsigned opcount)
230 : {
231 : /* The defining statement should be conditional. */
232 63169 : if (dominated_by_p (CDI_DOMINATORS, merge,
233 63169 : 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 59723 : gimple_stmt_iterator gsi = gsi_for_stmt (def_stmt);
239 59723 : gsi_next_nondebug (&gsi);
240 :
241 : /* Skip past nops and predicates. */
242 119921 : while (!gsi_end_p (gsi)
243 60198 : && (gimple_code (gsi_stmt (gsi)) == GIMPLE_NOP
244 8654 : || gimple_code (gsi_stmt (gsi)) == GIMPLE_PREDICT))
245 475 : 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 59723 : 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 8179 : int max_statements = param_phiopt_factor_max_stmts_live;
256 8179 : bool stmts_extending_ok = true;
257 :
258 23591 : while (!gsi_end_p (gsi))
259 : {
260 16307 : gimple *stmt = gsi_stmt (gsi);
261 16307 : auto gcode = gimple_code (stmt);
262 : /* Skip over NOPs and predicts. */
263 16321 : if (gcode == GIMPLE_NOP
264 16307 : || 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 16293 : if (gcode != GIMPLE_ASSIGN)
271 : {
272 : stmts_extending_ok = false;
273 : break;
274 : }
275 16014 : max_statements --;
276 16014 : if (max_statements == 0)
277 : {
278 : stmts_extending_ok = false;
279 : break;
280 : }
281 15398 : gsi_next_nondebug (&gsi);
282 : }
283 8179 : if (stmts_extending_ok)
284 : return true;
285 :
286 : /* Loop over all of the operands to see if all are used after anyways. */
287 1244 : for (unsigned i = 0; i < opcount; i++)
288 : {
289 923 : tree arg = operands[i];
290 : /* If the arg is invariant, then there is
291 : no extending of the live range. */
292 923 : if (is_gimple_min_invariant (arg))
293 308 : continue;
294 :
295 : /* Otherwise, the arg needs to be a ssa name. */
296 615 : 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 615 : use_operand_p use_p;
303 615 : imm_use_iterator iter;
304 615 : bool usedafter = false;
305 3411 : FOR_EACH_IMM_USE_FAST (use_p, iter, arg)
306 : {
307 2222 : gimple *use_stmt = USE_STMT (use_p);
308 2222 : if (is_gimple_debug (use_stmt))
309 222 : continue;
310 2000 : basic_block use_bb = gimple_bb (use_stmt);
311 2000 : if (dominated_by_p (CDI_DOMINATORS, merge, use_bb))
312 : {
313 : usedafter = true;
314 : break;
315 : }
316 615 : }
317 615 : 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 2981331 : factor_out_conditional_operation (edge e0, edge e1, basic_block merge,
330 : gphi *phi, gimple *cond_stmt,
331 : bool early_p)
332 : {
333 2981331 : gimple *arg0_def_stmt = NULL, *arg1_def_stmt = NULL;
334 2981331 : tree temp, result;
335 2981331 : gphi *newphi;
336 2981331 : gimple_stmt_iterator gsi, gsi_for_def;
337 2981331 : location_t locus = gimple_location (phi);
338 2981331 : gimple_match_op arg0_op, arg1_op;
339 :
340 : /* We should only get here if the phi had two arguments. */
341 2981331 : gcc_assert (gimple_phi_num_args (phi) == 2);
342 :
343 : /* Virtual operands are never handled. */
344 5962662 : if (virtual_operand_p (gimple_phi_result (phi)))
345 : return false;
346 :
347 1296237 : tree arg0 = gimple_phi_arg_def (phi, e0->dest_idx);
348 1296237 : tree arg1 = gimple_phi_arg_def (phi, e1->dest_idx);
349 1296237 : location_t narg0_loc = gimple_location (phi);
350 1296237 : location_t narg1_loc = gimple_location (phi);
351 1296237 : if (gimple_phi_arg_location (phi, e0->dest_idx) != UNKNOWN_LOCATION)
352 1101413 : narg0_loc = gimple_phi_arg_location (phi, e0->dest_idx);
353 1296237 : if (gimple_phi_arg_location (phi, e1->dest_idx) != UNKNOWN_LOCATION)
354 904767 : narg1_loc = gimple_phi_arg_location (phi, e1->dest_idx);
355 :
356 1296237 : 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 1296237 : if (operand_equal_for_phi_arg_p (arg0, arg1))
361 : return false;
362 :
363 : /* First canonicalize to simplify tests. */
364 1296030 : if (TREE_CODE (arg0) != SSA_NAME)
365 : {
366 246038 : std::swap (arg0, arg1);
367 246038 : std::swap (e0, e1);
368 : }
369 :
370 1296030 : if (TREE_CODE (arg0) != SSA_NAME
371 1179396 : || (TREE_CODE (arg1) != SSA_NAME
372 485286 : && 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 1146193 : arg0_def_stmt = SSA_NAME_DEF_STMT (arg0);
378 1146193 : 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 587626 : if (arg0_op.operands_occurs_in_abnormal_phi ())
383 : return false;
384 :
385 587626 : tree new_arg0;
386 587626 : tree new_arg1;
387 587626 : int opnum = -1;
388 :
389 : /* If arg0 have > 1 use, then this transformation actually increases
390 : the number of expressions evaluated at runtime. */
391 587626 : if (!has_single_use (arg0))
392 : return false;
393 478819 : if (gimple_has_location (arg0_def_stmt))
394 440940 : narg0_loc = gimple_location (arg0_def_stmt);
395 :
396 478819 : if (TREE_CODE (arg1) == SSA_NAME)
397 : {
398 : /* Check if arg1 is an SSA_NAME. */
399 307745 : arg1_def_stmt = SSA_NAME_DEF_STMT (arg1);
400 307745 : if (!gimple_extract_op (arg1_def_stmt, &arg1_op))
401 : return false;
402 156009 : if (arg1_op.code != arg0_op.code)
403 : return false;
404 41379 : if (arg1_op.num_ops != arg0_op.num_ops)
405 : return false;
406 41379 : 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 41379 : 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 41262 : if (!has_single_use (arg1))
418 : return false;
419 :
420 28714 : opnum = find_different_opnum (arg0_op, arg1_op, &new_arg0, &new_arg1);
421 28714 : if (opnum == -1)
422 : return false;
423 :
424 : /* Check to make sure extending the lifetimes of all operands is ok. */
425 12111 : if (!is_factor_profitable (arg0_def_stmt, merge,
426 : arg0_op.ops, arg0_op.num_ops))
427 : return false;
428 11172 : 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 8878 : 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 4206 : if (early_p && arg1_op.code == POINTER_PLUS_EXPR
446 166 : && opnum == 1
447 153 : && TREE_CODE (new_arg0) != SSA_NAME
448 8856 : && 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 8817 : if ((arg1_op.code == BIT_FIELD_REF
454 8787 : || arg1_op.code == BIT_INSERT_EXPR)
455 8884 : && 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 8739 : if (arg1_op.code == VEC_PERM_EXPR && opnum == 2
468 43 : && TREE_CODE (new_arg0) == VECTOR_CST
469 8782 : && TREE_CODE (new_arg1) == VECTOR_CST)
470 : return false;
471 :
472 8715 : if (gimple_has_location (arg1_def_stmt))
473 8497 : narg1_loc = gimple_location (arg1_def_stmt);
474 :
475 : /* Chose the location for the new statement if the phi location is unknown. */
476 8715 : if (locus == UNKNOWN_LOCATION)
477 : {
478 8715 : if (narg0_loc == UNKNOWN_LOCATION
479 8715 : && narg1_loc != UNKNOWN_LOCATION)
480 : locus = narg1_loc;
481 8715 : else if (narg0_loc != UNKNOWN_LOCATION
482 8715 : && narg1_loc == UNKNOWN_LOCATION)
483 51 : locus = narg0_loc;
484 : }
485 : }
486 171074 : else if (arg0_op.num_ops != 1)
487 : return false;
488 : else
489 : {
490 49017 : new_arg0 = arg0_op.ops[0];
491 49017 : opnum = 0;
492 : /* For constants only handle if the phi was the only one. */
493 49017 : 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 36483 : if (!gimple_assign_cast_p (arg0_def_stmt))
497 : return false;
498 31016 : 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 60481 : if (!INTEGRAL_TYPE_P (TREE_TYPE (new_arg0))
505 60219 : || !(int_fits_type_p (arg1, TREE_TYPE (new_arg0))
506 1675 : || (TYPE_PRECISION (TREE_TYPE (new_arg0))
507 1675 : == TYPE_PRECISION (TREE_TYPE (arg1))
508 783 : && (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 29093 : if ((TYPE_PRECISION (TREE_TYPE (new_arg0))
524 29093 : != TYPE_PRECISION (TREE_TYPE (arg1)))
525 13224 : && new_arg0 != gimple_cond_lhs (cond_stmt)
526 12528 : && new_arg0 != gimple_cond_rhs (cond_stmt)
527 41615 : && gimple_bb (arg0_def_stmt) == e0->src)
528 : {
529 12522 : gsi = gsi_for_stmt (arg0_def_stmt);
530 12522 : gsi_prev_nondebug (&gsi);
531 : /* Ignore nops, predicates and labels. */
532 25056 : while (!gsi_end_p (gsi)
533 12534 : && (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 12522 : if (!gsi_end_p (gsi))
539 : {
540 9130 : gimple *stmt = gsi_stmt (gsi);
541 2962118 : if (gassign *assign = dyn_cast <gassign *> (stmt))
542 : {
543 8716 : tree lhs = gimple_assign_lhs (assign);
544 8716 : tree lhst = TREE_TYPE (lhs);
545 8716 : enum tree_code ass_code
546 8716 : = gimple_assign_rhs_code (assign);
547 8716 : 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 8716 : && !(INTEGRAL_TYPE_P (lhst)
553 8265 : && TYPE_UNSIGNED (lhst)
554 6127 : && TYPE_PRECISION (lhst) == 1))
555 : return false;
556 4607 : if (lhs != gimple_assign_rhs1 (arg0_def_stmt))
557 : return false;
558 4565 : gsi_prev_nondebug (&gsi);
559 4565 : if (!gsi_end_p (gsi))
560 : return false;
561 : }
562 : else
563 : return false;
564 : }
565 : }
566 20268 : new_arg1 = fold_convert (TREE_TYPE (new_arg0), arg1);
567 :
568 : /* Drop the overflow that fold_convert might add. */
569 20268 : 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 20268 : if (gimple_has_location (arg0_def_stmt))
574 19811 : locus = gimple_location (arg0_def_stmt);
575 : }
576 :
577 : /* If types of new_arg0 and new_arg1 are different bailout. */
578 28983 : if (!types_compatible_p (TREE_TYPE (new_arg0), TREE_TYPE (new_arg1)))
579 : return false;
580 :
581 : /* Create a new PHI stmt. */
582 28186 : result = gimple_phi_result (phi);
583 28186 : temp = make_ssa_name (TREE_TYPE (new_arg0), NULL);
584 :
585 28186 : gimple_match_op new_op = arg0_op;
586 :
587 : /* Create the operation stmt if possible and insert it. */
588 28186 : new_op.ops[opnum] = temp;
589 28186 : gimple_seq seq = NULL;
590 28186 : 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 28186 : if (!result)
595 : {
596 257 : release_ssa_name (temp);
597 257 : return false;
598 : }
599 :
600 27929 : if (locus != UNKNOWN_LOCATION)
601 19858 : annotate_all_with_location (seq, locus);
602 27929 : gsi = gsi_after_labels (gimple_bb (phi));
603 27929 : gsi_insert_seq_before (&gsi, seq, GSI_CONTINUE_LINKING);
604 :
605 27929 : newphi = create_phi_node (temp, gimple_bb (phi));
606 :
607 27929 : 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 27929 : gsi_for_def = gsi_for_stmt (arg0_def_stmt);
620 27929 : gsi_remove (&gsi_for_def, true);
621 27929 : release_defs (arg0_def_stmt);
622 :
623 27929 : if (arg1_def_stmt)
624 : {
625 7661 : gsi_for_def = gsi_for_stmt (arg1_def_stmt);
626 7661 : gsi_remove (&gsi_for_def, true);
627 7661 : release_defs (arg1_def_stmt);
628 : }
629 :
630 27929 : add_phi_arg (newphi, new_arg0, e0, narg0_loc);
631 27929 : add_phi_arg (newphi, new_arg1, e1, narg1_loc);
632 :
633 : /* Remove the original PHI stmt. */
634 27929 : gsi = gsi_for_stmt (phi);
635 27929 : gsi_remove (&gsi, true);
636 :
637 27929 : statistics_counter_event (cfun, "factored out operation", 1);
638 :
639 27929 : 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 171045 : phiopt_early_allow (gimple_seq &seq, gimple_match_op &op)
647 : {
648 : /* Don't allow functions. */
649 171045 : if (!op.code.is_tree_code ())
650 : return false;
651 170993 : 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 170993 : if (!gimple_seq_empty_p (seq))
656 : {
657 140933 : if (code == MIN_EXPR || code == MAX_EXPR)
658 : {
659 143929 : 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 30060 : 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 529864 : gimple_simplify_phiopt (bool early_p, tree type, gimple *comp_stmt,
700 : tree arg0, tree arg1,
701 : gimple_seq *seq)
702 : {
703 529864 : gimple_seq seq1 = NULL;
704 529864 : enum tree_code comp_code = gimple_cond_code (comp_stmt);
705 529864 : location_t loc = gimple_location (comp_stmt);
706 529864 : tree cmp0 = gimple_cond_lhs (comp_stmt);
707 529864 : 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 529864 : tree cond = build2_loc (loc, comp_code, boolean_type_node,
714 : cmp0, cmp1);
715 :
716 529864 : 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 529864 : gimple_match_op op (gimple_match_cond::UNCOND,
728 529864 : COND_EXPR, type, cond, arg0, arg1);
729 :
730 529864 : if (op.resimplify (&seq1, follow_all_ssa_edges))
731 : {
732 156818 : bool allowed = !early_p || phiopt_early_allow (seq1, op);
733 156818 : tree result = maybe_push_res_to_seq (&op, &seq1);
734 156818 : 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 156818 : if (allowed && result)
750 : {
751 83859 : if (loc != UNKNOWN_LOCATION)
752 83391 : annotate_all_with_location (seq1, loc);
753 83859 : gimple_seq_add_seq_without_update (seq, seq1);
754 83859 : return result;
755 : }
756 : }
757 446005 : gimple_seq_discard (seq1);
758 446005 : seq1 = NULL;
759 :
760 : /* Try the inverted comparison, that is !COMP ? ARG1 : ARG0. */
761 446005 : comp_code = invert_tree_comparison (comp_code, HONOR_NANS (cmp0));
762 :
763 446005 : if (comp_code == ERROR_MARK)
764 : return NULL;
765 :
766 432250 : cond = build2_loc (loc,
767 : comp_code, boolean_type_node,
768 : cmp0, cmp1);
769 :
770 432250 : 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 432250 : gimple_match_op op1 (gimple_match_cond::UNCOND,
782 432250 : COND_EXPR, type, cond, arg1, arg0);
783 :
784 432250 : if (op1.resimplify (&seq1, follow_all_ssa_edges))
785 : {
786 75761 : bool allowed = !early_p || phiopt_early_allow (seq1, op1);
787 75761 : tree result = maybe_push_res_to_seq (&op1, &seq1);
788 75761 : 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 75761 : if (allowed && result)
804 : {
805 4750 : if (loc != UNKNOWN_LOCATION)
806 4750 : annotate_all_with_location (seq1, loc);
807 4750 : gimple_seq_add_seq_without_update (seq, seq1);
808 4750 : return result;
809 : }
810 : }
811 427500 : gimple_seq_discard (seq1);
812 :
813 427500 : 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 864596 : empty_bb_or_one_feeding_into_p (basic_block bb,
821 : gimple *phi,
822 : gimple *&stmt)
823 : {
824 864596 : stmt = nullptr;
825 864596 : gimple *stmt_to_move = nullptr;
826 864596 : tree lhs;
827 :
828 864596 : if (empty_block_p (bb))
829 : return true;
830 :
831 747859 : 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 446009 : if (!gimple_seq_empty_p (phi_nodes (bb)))
837 : return false;
838 :
839 445992 : gimple_stmt_iterator gsi;
840 :
841 445992 : gsi = gsi_start_nondebug_after_labels_bb (bb);
842 894800 : while (!gsi_end_p (gsi))
843 : {
844 656053 : gimple *s = gsi_stmt (gsi);
845 656053 : gsi_next_nondebug (&gsi);
846 : /* Skip over Predict and nop statements. */
847 656053 : if (gimple_code (s) == GIMPLE_PREDICT
848 656053 : || gimple_code (s) == GIMPLE_NOP)
849 2816 : continue;
850 : /* If there is more one statement return false. */
851 653237 : 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 238747 : if (!stmt_to_move)
859 : return true;
860 :
861 477494 : if (gimple_vuse (stmt_to_move))
862 : return false;
863 :
864 164353 : if (gimple_could_trap_p (stmt_to_move)
865 164353 : || gimple_has_side_effects (stmt_to_move))
866 5238 : return false;
867 :
868 159115 : ssa_op_iter it;
869 159115 : tree use;
870 352228 : FOR_EACH_SSA_TREE_OPERAND (use, stmt_to_move, it, SSA_OP_USE)
871 193766 : 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 158462 : if (!is_gimple_assign (stmt_to_move))
884 : {
885 4662 : if (!is_gimple_call (stmt_to_move))
886 : return false;
887 4411 : combined_fn cfn = gimple_call_combined_fn (stmt_to_move);
888 4411 : switch (cfn)
889 : {
890 : default:
891 : return false;
892 3498 : CASE_CFN_BSWAP:
893 3498 : CASE_CFN_BITREVERSE:
894 3498 : CASE_CFN_FFS:
895 3498 : CASE_CFN_PARITY:
896 3498 : CASE_CFN_POPCOUNT:
897 3498 : CASE_CFN_CLZ:
898 3498 : CASE_CFN_CTZ:
899 3498 : case CFN_BUILT_IN_CLRSB:
900 3498 : case CFN_BUILT_IN_CLRSBL:
901 3498 : case CFN_BUILT_IN_CLRSBLL:
902 3498 : lhs = gimple_call_lhs (stmt_to_move);
903 3498 : break;
904 : }
905 : }
906 : else
907 153800 : lhs = gimple_assign_lhs (stmt_to_move);
908 :
909 157298 : gimple *use_stmt;
910 157298 : use_operand_p use_p;
911 :
912 : /* Allow only a statement which feeds into the other stmt. */
913 157298 : if (!lhs || TREE_CODE (lhs) != SSA_NAME
914 157298 : || !single_imm_use (lhs, &use_p, &use_stmt)
915 314591 : || use_stmt != phi)
916 5 : return false;
917 :
918 157293 : stmt = stmt_to_move;
919 157293 : 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 185108 : move_stmt (gimple *stmt, gimple_stmt_iterator *gsi, auto_bitmap &inserted_exprs)
927 : {
928 185108 : if (!stmt)
929 179059 : return;
930 6049 : 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 6049 : tree name = gimple_get_lhs (stmt);
938 : // Mark the name to be renamed if there is one.
939 6049 : bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (name));
940 6049 : gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt);
941 6049 : gsi_move_before (&gsi1, gsi, GSI_NEW_STMT);
942 6049 : reset_flow_sensitive_info (name);
943 :
944 : /* Rewrite some code which might be undefined when
945 : unconditionalized. */
946 6049 : if (gimple_needing_rewrite_undefined (stmt))
947 1058 : 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 1059728 : auto_flow_sensitive::auto_flow_sensitive (gimple *s)
967 : {
968 1059728 : if (!s)
969 909294 : return;
970 150434 : ssa_op_iter it;
971 150434 : tree def;
972 300868 : FOR_EACH_SSA_TREE_OPERAND (def, s, it, SSA_OP_DEF)
973 : {
974 150434 : flow_sensitive_info_storage storage;
975 150434 : storage.save_and_clear (def);
976 150434 : 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 1059728 : auto_flow_sensitive::~auto_flow_sensitive ()
984 : {
985 3329618 : for (auto p : stack)
986 150434 : p.second.restore (p.first);
987 1059728 : }
988 :
989 : /* Returns true if BB contains an user provided predictor
990 : (PRED_HOT_LABEL/PRED_COLD_LABEL). */
991 :
992 : static bool
993 6169 : contains_hot_cold_predict (basic_block bb)
994 : {
995 6169 : gimple_stmt_iterator gsi;
996 6169 : gsi = gsi_start_nondebug_after_labels_bb (bb);
997 8675 : for (; !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
998 : {
999 2507 : gimple *s = gsi_stmt (gsi);
1000 2507 : if (gimple_code (s) != GIMPLE_PREDICT)
1001 2 : continue;
1002 2505 : auto predict = gimple_predict_predictor (s);
1003 2505 : if (predict == PRED_HOT_LABEL
1004 2505 : || 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 836263 : 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 836263 : gimple *stmt;
1024 836263 : gimple_stmt_iterator gsi;
1025 836263 : edge true_edge, false_edge;
1026 836263 : gimple_seq seq = NULL;
1027 836263 : tree result;
1028 836263 : gimple *stmt_to_move = NULL;
1029 836263 : gimple *stmt_to_move_alt = NULL;
1030 836263 : tree arg_true, arg_false;
1031 :
1032 : /* Special case A ? B : B as this will always simplify to B. */
1033 836263 : 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 836263 : if (!empty_bb_or_one_feeding_into_p (middle_bb, phi, stmt_to_move))
1039 : return false;
1040 :
1041 545930 : if (threeway_p
1042 545930 : && middle_bb != middle_bb_alt
1043 545930 : && !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 534413 : if ((TREE_CODE (arg0) == SSA_NAME
1049 282815 : && ssa_name_maybe_undef_p (arg0))
1050 816886 : || (TREE_CODE (arg1) == SSA_NAME
1051 234950 : && 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 529864 : 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 529864 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1068 :
1069 : /* Forward the edges over the middle basic block. */
1070 529864 : if (true_edge->dest == middle_bb)
1071 341531 : true_edge = EDGE_SUCC (true_edge->dest, 0);
1072 529864 : if (false_edge->dest == middle_bb)
1073 188333 : 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 529864 : if (true_edge == e0)
1078 : {
1079 341531 : if (!threeway_p)
1080 325210 : gcc_assert (false_edge == e1);
1081 : arg_true = arg0;
1082 : arg_false = arg1;
1083 : }
1084 : else
1085 : {
1086 188333 : gcc_assert (false_edge == e0);
1087 188333 : if (!threeway_p)
1088 187958 : gcc_assert (true_edge == e1);
1089 : arg_true = arg1;
1090 : arg_false = arg0;
1091 : }
1092 :
1093 529864 : tree type = TREE_TYPE (gimple_phi_result (phi));
1094 529864 : {
1095 529864 : auto_flow_sensitive s1(stmt_to_move);
1096 529864 : auto_flow_sensitive s_alt(stmt_to_move_alt);
1097 :
1098 529864 : result = gimple_simplify_phiopt (early_p, type, stmt,
1099 : arg_true, arg_false,
1100 : &seq);
1101 529864 : }
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 529864 : if (early_p && result && TREE_CODE (result) == SSA_NAME)
1108 : {
1109 27110 : bool check_it = false;
1110 27110 : tree cmp0 = gimple_cond_lhs (stmt);
1111 27110 : tree cmp1 = gimple_cond_rhs (stmt);
1112 27110 : if (result == cmp0 || result == cmp1)
1113 : check_it = true;
1114 21310 : else if (gimple_seq_singleton_p (seq))
1115 : {
1116 21194 : gimple *stmt = gimple_seq_first_stmt (seq);
1117 21194 : if (is_gimple_assign (stmt)
1118 21194 : && result == gimple_assign_lhs (stmt)
1119 42388 : && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
1120 : == tcc_comparison)
1121 : check_it = true;
1122 : }
1123 : if (!check_it)
1124 : ;
1125 5800 : else if (contains_hot_cold_predict (middle_bb))
1126 : return false;
1127 5799 : else if (threeway_p
1128 : && middle_bb != middle_bb_alt
1129 5799 : && contains_hot_cold_predict (middle_bb_alt))
1130 : return false;
1131 : }
1132 :
1133 529856 : 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 441255 : if (!HONOR_NANS (type) && !HONOR_SIGNED_ZEROS (type))
1139 : return false;
1140 16638 : if (stmt_to_move || stmt_to_move_alt)
1141 : return false;
1142 13795 : tree_code cmp = gimple_cond_code (stmt);
1143 13795 : if (cmp != LT_EXPR && cmp != LE_EXPR
1144 13795 : && cmp != GT_EXPR && cmp != GE_EXPR)
1145 : return false;
1146 6588 : tree lhs = gimple_cond_lhs (stmt);
1147 6588 : 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 6588 : if ((!operand_equal_for_phi_arg_p (lhs, arg_false)
1151 2579 : || !operand_equal_for_phi_arg_p (rhs, arg_true))
1152 6648 : && (!operand_equal_for_phi_arg_p (rhs, arg_false)
1153 1589 : || !operand_equal_for_phi_arg_p (lhs, arg_true)))
1154 2642 : return false;
1155 3946 : seq = nullptr;
1156 3946 : result = gimple_build (&seq, cmp, boolean_type_node, lhs, rhs);
1157 3946 : result = gimple_build (&seq, COND_EXPR, type, result,
1158 : arg_true, arg_false);
1159 3946 : statistics_counter_event (cfun, "Non-IEEE FP MIN/MAX PHI replacement",
1160 : 1);
1161 : }
1162 92554 : if (dump_file && (dump_flags & TDF_FOLDING))
1163 1 : fprintf (dump_file, "accepted the phiopt match-simplify.\n");
1164 :
1165 92554 : auto_bitmap exprs_maybe_dce;
1166 :
1167 : /* Mark the cond statements' lhs/rhs as maybe dce. */
1168 92554 : if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
1169 92554 : && !SSA_NAME_IS_DEFAULT_DEF (gimple_cond_lhs (stmt)))
1170 87390 : bitmap_set_bit (exprs_maybe_dce,
1171 87390 : SSA_NAME_VERSION (gimple_cond_lhs (stmt)));
1172 92554 : if (TREE_CODE (gimple_cond_rhs (stmt)) == SSA_NAME
1173 92554 : && !SSA_NAME_IS_DEFAULT_DEF (gimple_cond_rhs (stmt)))
1174 27858 : bitmap_set_bit (exprs_maybe_dce,
1175 27858 : SSA_NAME_VERSION (gimple_cond_rhs (stmt)));
1176 :
1177 92554 : gsi = gsi_last_bb (cond_bb);
1178 : /* Insert the sequence generated from gimple_simplify_phiopt. */
1179 92554 : if (seq)
1180 : {
1181 : // Mark the lhs of the new statements maybe for dce
1182 84926 : mark_lhs_in_seq_for_dce (exprs_maybe_dce, seq);
1183 84926 : 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 92554 : move_stmt (stmt_to_move, &gsi, exprs_maybe_dce);
1189 92554 : move_stmt (stmt_to_move_alt, &gsi, exprs_maybe_dce);
1190 :
1191 92554 : 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 92554 : statistics_counter_event (cfun, "match-simplify PHI replacement", 1);
1197 :
1198 : /* Note that we optimized this PHI. */
1199 92554 : return true;
1200 92554 : }
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 329855 : jump_function_from_stmt (tree *arg, gimple *stmt)
1208 : {
1209 329855 : enum tree_code code = gimple_assign_rhs_code (stmt);
1210 329855 : if (code == ADDR_EXPR)
1211 : {
1212 : /* For arg = &p->i transform it to p, if possible. */
1213 4829 : tree rhs1 = gimple_assign_rhs1 (stmt);
1214 4829 : poly_int64 offset;
1215 4829 : tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs1, 0),
1216 : &offset);
1217 4829 : if (tem
1218 4748 : && TREE_CODE (tem) == MEM_REF
1219 9577 : && known_eq (mem_ref_offset (tem) + offset, 0))
1220 : {
1221 2106 : *arg = TREE_OPERAND (tem, 0);
1222 2106 : 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 155860 : 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 155860 : if (TREE_CODE (rhs) == SSA_NAME)
1248 : {
1249 121549 : gimple *def1 = SSA_NAME_DEF_STMT (rhs);
1250 :
1251 : /* Verify the defining statement has an EQ_EXPR or NE_EXPR on the RHS. */
1252 121549 : if (is_gimple_assign (def1)
1253 121549 : && ((bit_expression_code == BIT_AND_EXPR
1254 74900 : && gimple_assign_rhs_code (def1) == EQ_EXPR)
1255 91376 : || (bit_expression_code == BIT_IOR_EXPR
1256 36740 : && 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 25020 : tree op0 = gimple_assign_rhs1 (def1);
1261 25020 : tree op1 = gimple_assign_rhs2 (def1);
1262 25020 : if ((operand_equal_for_phi_arg_p (arg0, op0)
1263 595 : && operand_equal_for_phi_arg_p (arg1, op1))
1264 25580 : || (operand_equal_for_phi_arg_p (arg0, op1)
1265 667 : && operand_equal_for_phi_arg_p (arg1, op0)))
1266 : {
1267 : /* We will perform the optimization. */
1268 445 : *code = gimple_assign_rhs_code (def1);
1269 445 : 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 660695 : operand_equal_for_value_replacement (const_tree arg0, const_tree arg1,
1286 : enum tree_code *code, gimple *cond)
1287 : {
1288 660695 : gimple *def;
1289 660695 : tree lhs = gimple_cond_lhs (cond);
1290 660695 : tree rhs = gimple_cond_rhs (cond);
1291 :
1292 660695 : if ((operand_equal_for_phi_arg_p (arg0, lhs)
1293 28432 : && operand_equal_for_phi_arg_p (arg1, rhs))
1294 680312 : || (operand_equal_for_phi_arg_p (arg1, lhs)
1295 43333 : && operand_equal_for_phi_arg_p (arg0, rhs)))
1296 12683 : 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 376737 : if (*code != NE_EXPR || !integer_zerop (rhs)
1304 917081 : || TREE_CODE (lhs) != SSA_NAME)
1305 379344 : return false;
1306 :
1307 : /* Now ensure that SSA_NAME is set by a BIT_AND_EXPR or BIT_OR_EXPR. */
1308 268668 : def = SSA_NAME_DEF_STMT (lhs);
1309 268668 : if (!is_gimple_assign (def)
1310 268668 : || (gimple_assign_rhs_code (def) != BIT_AND_EXPR
1311 128876 : && 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 78085 : tree tmp = gimple_assign_rhs1 (def);
1319 78085 : if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp,
1320 : gimple_assign_rhs_code (def)))
1321 : return true;
1322 :
1323 77775 : tmp = gimple_assign_rhs2 (def);
1324 77775 : 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 997 : neutral_element_p (tree_code code, tree arg, bool right)
1336 : {
1337 997 : 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 611 : case MULT_EXPR:
1353 611 : 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 2410370 : value_replacement (basic_block cond_bb, basic_block middle_bb,
1416 : edge e0, edge e1, gphi *phi, tree arg0, tree arg1)
1417 : {
1418 2410370 : gimple_stmt_iterator gsi;
1419 2410370 : edge true_edge, false_edge;
1420 2410370 : enum tree_code code;
1421 2410370 : bool empty_or_with_defined_p = true;
1422 :
1423 : /* Virtual operands don't need to be handled. */
1424 4293187 : if (virtual_operand_p (arg1))
1425 : return 0;
1426 :
1427 : /* Special case A ? B : B as this will always simplify to B. */
1428 1277569 : if (operand_equal_for_phi_arg_p (arg0, arg1))
1429 : return 0;
1430 :
1431 2276304 : gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_bb));
1432 1138152 : code = gimple_cond_code (cond);
1433 :
1434 : /* This transformation is only valid for equality comparisons. */
1435 1138152 : if (code != NE_EXPR && code != EQ_EXPR)
1436 : return 0;
1437 :
1438 : /* Do not make conditional undefs unconditional. */
1439 689822 : if ((TREE_CODE (arg0) == SSA_NAME
1440 526914 : && ssa_name_maybe_undef_p (arg0))
1441 1214921 : || (TREE_CODE (arg1) == SSA_NAME
1442 297019 : && 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 673694 : 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 660695 : gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
1453 2093790 : while (!gsi_end_p (gsi))
1454 : {
1455 1433095 : gimple *stmt = gsi_stmt (gsi);
1456 1433095 : tree lhs;
1457 1433095 : gsi_next_nondebug (&gsi);
1458 1433095 : if (!is_gimple_assign (stmt))
1459 : {
1460 196227 : if (gimple_code (stmt) != GIMPLE_PREDICT
1461 196227 : && gimple_code (stmt) != GIMPLE_NOP)
1462 : empty_or_with_defined_p = false;
1463 196227 : continue;
1464 : }
1465 : /* Now try to adjust arg0 or arg1 according to the computation
1466 : in the statement. */
1467 1236868 : lhs = gimple_assign_lhs (stmt);
1468 329855 : if (!(lhs == arg0
1469 329855 : && jump_function_from_stmt (&arg0, stmt))
1470 1238974 : || (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 660695 : if (phi_nodes (middle_bb))
1477 69420 : 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 660695 : 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 660695 : bool equal_p = operand_equal_for_value_replacement (arg0, arg1, &code, cond);
1495 660695 : bool maybe_equal_p = false;
1496 660695 : if (!equal_p
1497 660695 : && empty_or_with_defined_p
1498 187097 : && TREE_CODE (gimple_cond_rhs (cond)) == INTEGER_CST
1499 807820 : && (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond), arg0)
1500 147125 : ? TREE_CODE (arg1) == INTEGER_CST
1501 138121 : : (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond), arg1)
1502 19670 : && TREE_CODE (arg0) == INTEGER_CST)))
1503 : maybe_equal_p = true;
1504 642037 : if (equal_p || maybe_equal_p)
1505 : {
1506 31786 : edge e;
1507 31786 : 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 31786 : 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 31786 : if (e->dest == middle_bb)
1519 13990 : 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 31786 : if (e0 == e)
1524 : arg = arg0;
1525 : else
1526 17796 : 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 31786 : if (empty_or_with_defined_p
1532 31786 : && single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)),
1533 : e0, e1) == phi)
1534 : {
1535 18581 : use_operand_p use_p;
1536 18581 : 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 18581 : if (maybe_equal_p
1560 17063 : && TREE_CODE (arg) != INTEGER_CST
1561 35629 : && single_imm_use (gimple_phi_result (phi), &use_p, &use_stmt))
1562 : {
1563 9626 : enum tree_code ccode = ERROR_MARK;
1564 9626 : tree clhs = NULL_TREE, crhs = NULL_TREE;
1565 9626 : tree carg = gimple_cond_rhs (cond);
1566 9626 : tree oarg = e0 == e ? arg1 : arg0;
1567 9626 : if (is_gimple_assign (use_stmt)
1568 9626 : && (TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
1569 : == tcc_comparison))
1570 : {
1571 58 : ccode = gimple_assign_rhs_code (use_stmt);
1572 58 : clhs = gimple_assign_rhs1 (use_stmt);
1573 58 : crhs = gimple_assign_rhs2 (use_stmt);
1574 : }
1575 9568 : else if (gimple_code (use_stmt) == GIMPLE_COND)
1576 : {
1577 78 : ccode = gimple_cond_code (use_stmt);
1578 78 : clhs = gimple_cond_lhs (use_stmt);
1579 78 : 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 9610 : 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 8971 : if (equal_p)
1678 : {
1679 1534 : replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
1680 : /* Note that we optimized this PHI. */
1681 1534 : return 2;
1682 : }
1683 : }
1684 13205 : else if (equal_p)
1685 : {
1686 11610 : if (!single_pred_p (middle_bb))
1687 : return 0;
1688 10893 : statistics_counter_event (cfun, "Replace PHI with "
1689 : "variable/value_replacement", 1);
1690 :
1691 : /* Replace the PHI arguments with arg. */
1692 10893 : SET_PHI_ARG_DEF (phi, e0->dest_idx, arg);
1693 10893 : SET_PHI_ARG_DEF (phi, e1->dest_idx, arg);
1694 10893 : 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 10893 : return 1;
1704 : }
1705 : }
1706 :
1707 2950702 : if (!single_pred_p (middle_bb))
1708 : return 0;
1709 :
1710 : /* Now optimize (x != 0) ? x + y : y to just x + y. */
1711 552866 : gsi = gsi_last_nondebug_bb (middle_bb);
1712 552866 : if (gsi_end_p (gsi))
1713 : return 0;
1714 :
1715 383193 : gimple *assign = gsi_stmt (gsi);
1716 383193 : if (!is_gimple_assign (assign)
1717 383193 : || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
1718 109400 : && !POINTER_TYPE_P (TREE_TYPE (arg0))))
1719 : return 0;
1720 :
1721 328234 : 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 140750 : enum tree_code sc = gimple_assign_rhs_code (assign);
1727 140750 : 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 208914 : 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 208914 : gimple *prep_stmt[2] = { NULL, NULL };
1760 208914 : int prep_cnt;
1761 208914 : for (prep_cnt = 0; ; prep_cnt++)
1762 : {
1763 268140 : if (prep_cnt || assign)
1764 246710 : gsi_prev_nondebug (&gsi);
1765 268140 : if (gsi_end_p (gsi))
1766 : break;
1767 :
1768 201924 : gimple *g = gsi_stmt (gsi);
1769 201924 : if (gimple_code (g) == GIMPLE_LABEL)
1770 : break;
1771 :
1772 201569 : if (prep_cnt == 2 || !is_gimple_assign (g))
1773 142343 : return 0;
1774 :
1775 177207 : tree lhs = gimple_assign_lhs (g);
1776 177207 : tree rhs1 = gimple_assign_rhs1 (g);
1777 177207 : use_operand_p use_p;
1778 177207 : gimple *use_stmt;
1779 177207 : if (TREE_CODE (lhs) != SSA_NAME
1780 170509 : || TREE_CODE (rhs1) != SSA_NAME
1781 107726 : || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1782 104227 : || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1783 100470 : || !single_imm_use (lhs, &use_p, &use_stmt)
1784 276784 : || ((prep_cnt || assign)
1785 79674 : && use_stmt != (prep_cnt ? prep_stmt[prep_cnt - 1] : assign)))
1786 85346 : return 0;
1787 91861 : switch (gimple_assign_rhs_code (g))
1788 : {
1789 : CASE_CONVERT:
1790 : break;
1791 20067 : case PLUS_EXPR:
1792 20067 : case BIT_AND_EXPR:
1793 20067 : case BIT_IOR_EXPR:
1794 20067 : case BIT_XOR_EXPR:
1795 20067 : if (TREE_CODE (gimple_assign_rhs2 (g)) != INTEGER_CST)
1796 : return 0;
1797 : break;
1798 : default:
1799 : return 0;
1800 : }
1801 59226 : prep_stmt[prep_cnt] = g;
1802 59226 : }
1803 :
1804 : /* Only transform if it removes the condition. */
1805 66571 : 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 51894 : if (optimize_bb_for_speed_p (cond_bb)
1810 : /* The special case is useless if it has a low probability. */
1811 49181 : && profile_status_for_fn (cfun) != PROFILE_ABSENT
1812 60258 : && EDGE_PRED (middle_bb, 0)->probability < profile_probability::even ()
1813 : /* If assign is cheap, there is no point avoiding it. */
1814 62991 : && estimate_num_insns_seq (bb_seq (middle_bb), &eni_time_weights)
1815 11097 : >= 3 * estimate_num_insns (cond, &eni_time_weights))
1816 78 : return 0;
1817 :
1818 51816 : tree cond_lhs = gimple_cond_lhs (cond);
1819 51816 : 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 53385 : for (int i = prep_cnt - 1; i >= 0; --i)
1824 : {
1825 13438 : gimple *g = prep_stmt[i];
1826 13438 : tree grhs1 = gimple_assign_rhs1 (g);
1827 13438 : if (!operand_equal_for_phi_arg_p (cond_lhs, grhs1))
1828 : return 0;
1829 7172 : cond_lhs = gimple_assign_lhs (g);
1830 7172 : cond_rhs = fold_convert (TREE_TYPE (grhs1), cond_rhs);
1831 7172 : if (TREE_CODE (cond_rhs) != INTEGER_CST
1832 7172 : || TREE_OVERFLOW (cond_rhs))
1833 : return 0;
1834 1569 : if (gimple_assign_rhs_class (g) == GIMPLE_BINARY_RHS)
1835 : {
1836 522 : cond_rhs = int_const_binop (gimple_assign_rhs_code (g), cond_rhs,
1837 522 : gimple_assign_rhs2 (g));
1838 522 : if (TREE_OVERFLOW (cond_rhs))
1839 : return 0;
1840 : }
1841 1569 : cond_rhs = fold_convert (TREE_TYPE (cond_lhs), cond_rhs);
1842 1569 : if (TREE_CODE (cond_rhs) != INTEGER_CST
1843 1569 : || TREE_OVERFLOW (cond_rhs))
1844 : return 0;
1845 : }
1846 :
1847 39947 : tree lhs, rhs1, rhs2;
1848 39947 : enum tree_code code_def;
1849 39947 : if (assign)
1850 : {
1851 39691 : lhs = gimple_assign_lhs (assign);
1852 39691 : rhs1 = gimple_assign_rhs1 (assign);
1853 39691 : rhs2 = gimple_assign_rhs2 (assign);
1854 39691 : 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 23168 : if (((code == NE_EXPR && e1 == false_edge)
1866 19554 : || (code == EQ_EXPR && e1 == true_edge))
1867 23182 : && arg0 == lhs
1868 63129 : && ((assign == NULL
1869 255 : && operand_equal_for_phi_arg_p (arg1, cond_rhs))
1870 : || (assign
1871 22927 : && arg1 == rhs1
1872 14915 : && operand_equal_for_phi_arg_p (rhs2, cond_lhs)
1873 394 : && neutral_element_p (code_def, cond_rhs, true))
1874 22861 : || (assign
1875 22861 : && arg1 == rhs2
1876 1258 : && operand_equal_for_phi_arg_p (rhs1, cond_lhs)
1877 603 : && neutral_element_p (code_def, cond_rhs, false))
1878 : || (assign
1879 22855 : && operand_equal_for_phi_arg_p (arg1, cond_rhs)
1880 2876 : && ((operand_equal_for_phi_arg_p (rhs2, cond_lhs)
1881 243 : && absorbing_element_p (code_def, cond_rhs, true, rhs2))
1882 2875 : || (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 638754 : spaceship_replacement (basic_block cond_bb, basic_block middle_bb,
1969 : edge e0, edge e1, gphi *phi,
1970 : tree arg0, tree arg1)
1971 : {
1972 638754 : tree phires = gimple_phi_result (phi);
1973 1270504 : if (!INTEGRAL_TYPE_P (TREE_TYPE (phires))
1974 507566 : || TYPE_UNSIGNED (TREE_TYPE (phires))
1975 258416 : || !tree_fits_shwi_p (arg0)
1976 71582 : || !tree_fits_shwi_p (arg1)
1977 41245 : || (!IN_RANGE (tree_to_shwi (arg0), -1, 1)
1978 21141 : && tree_to_shwi (arg0) != -128)
1979 659276 : || (!IN_RANGE (tree_to_shwi (arg1), -1, 1)
1980 2671 : && tree_to_shwi (arg1) != -128))
1981 : return false;
1982 :
1983 17907 : basic_block phi_bb = gimple_bb (phi);
1984 17907 : gcc_assert (phi_bb == e0->dest && phi_bb == e1->dest);
1985 17907 : if (!IN_RANGE (EDGE_COUNT (phi_bb->preds), 3, 4))
1986 : return false;
1987 :
1988 7334 : use_operand_p use_p;
1989 7334 : gimple *use_stmt;
1990 7334 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (phires))
1991 : return false;
1992 7329 : if (!single_imm_use (phires, &use_p, &use_stmt))
1993 : return false;
1994 6717 : enum tree_code cmp;
1995 6717 : tree lhs, rhs;
1996 6717 : gimple *orig_use_stmt = use_stmt;
1997 6717 : tree orig_use_lhs = NULL_TREE;
1998 6717 : 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 6717 : if (gimple_assign_cast_p (use_stmt))
2006 : {
2007 251 : orig_use_lhs = gimple_assign_lhs (use_stmt);
2008 251 : temps[0] = orig_use_lhs;
2009 251 : tree ty1 = TREE_TYPE (gimple_assign_rhs1 (use_stmt));
2010 251 : tree ty2 = TREE_TYPE (orig_use_lhs);
2011 :
2012 251 : if (!TYPE_UNSIGNED (ty2) || !INTEGRAL_TYPE_P (ty2))
2013 : return false;
2014 211 : if (TYPE_PRECISION (ty2) != 8 || TYPE_PRECISION (ty1) < 8)
2015 : return false;
2016 92 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
2017 : return false;
2018 92 : if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
2019 : return false;
2020 :
2021 91 : if (!is_gimple_assign (use_stmt)
2022 91 : || gimple_assign_rhs_code (use_stmt) != NEGATE_EXPR)
2023 : return false;
2024 :
2025 88 : orig_use_lhs = gimple_assign_lhs (use_stmt);
2026 88 : temps[1] = orig_use_lhs;
2027 88 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
2028 : return false;
2029 88 : if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
2030 : return false;
2031 :
2032 88 : if (!gimple_assign_cast_p (use_stmt))
2033 : return false;
2034 :
2035 88 : orig_use_lhs = gimple_assign_lhs (use_stmt);
2036 88 : tree ty3 = TREE_TYPE (orig_use_lhs);
2037 :
2038 88 : if (!useless_type_conversion_p (ty3, ty1))
2039 : return false;
2040 88 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
2041 : return false;
2042 88 : if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
2043 : return false;
2044 : }
2045 6554 : if (gimple_code (use_stmt) == GIMPLE_COND)
2046 : {
2047 2392 : cmp = gimple_cond_code (use_stmt);
2048 2392 : lhs = gimple_cond_lhs (use_stmt);
2049 2392 : rhs = gimple_cond_rhs (use_stmt);
2050 : }
2051 4162 : else if (is_gimple_assign (use_stmt))
2052 : {
2053 2296 : if (gimple_assign_rhs_class (use_stmt) == GIMPLE_BINARY_RHS)
2054 : {
2055 1202 : cmp = gimple_assign_rhs_code (use_stmt);
2056 1202 : lhs = gimple_assign_rhs1 (use_stmt);
2057 1202 : rhs = gimple_assign_rhs2 (use_stmt);
2058 : }
2059 1094 : 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 3594 : switch (cmp)
2074 : {
2075 3113 : case EQ_EXPR:
2076 3113 : case NE_EXPR:
2077 3113 : case LT_EXPR:
2078 3113 : case GT_EXPR:
2079 3113 : case LE_EXPR:
2080 3113 : case GE_EXPR:
2081 3113 : break;
2082 : default:
2083 : return false;
2084 : }
2085 6138 : if (lhs != (orig_use_lhs ? orig_use_lhs : phires)
2086 2754 : || !tree_fits_shwi_p (rhs)
2087 2490 : || !IN_RANGE (tree_to_shwi (rhs), -1, 1))
2088 : return false;
2089 :
2090 2478 : if (!empty_block_p (middle_bb))
2091 : return false;
2092 :
2093 4956 : gcond *cond1 = as_a <gcond *> (*gsi_last_bb (cond_bb));
2094 2478 : enum tree_code cmp1 = gimple_cond_code (cond1);
2095 2478 : switch (cmp1)
2096 : {
2097 2343 : case LT_EXPR:
2098 2343 : case LE_EXPR:
2099 2343 : case GT_EXPR:
2100 2343 : case GE_EXPR:
2101 2343 : break;
2102 : default:
2103 : return false;
2104 : }
2105 2343 : tree lhs1 = gimple_cond_lhs (cond1);
2106 2343 : tree rhs1 = gimple_cond_rhs (cond1);
2107 2343 : if (TREE_CODE (lhs1) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs1))
2108 : return false;
2109 2343 : if (TREE_CODE (rhs1) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1))
2110 : return false;
2111 :
2112 2343 : if (!single_pred_p (cond_bb) || !cond_only_block_p (cond_bb))
2113 13 : return false;
2114 :
2115 2330 : basic_block cond2_bb = single_pred (cond_bb);
2116 2330 : if (EDGE_COUNT (cond2_bb->succs) != 2)
2117 : return false;
2118 2330 : edge cond2_phi_edge;
2119 2330 : if (EDGE_SUCC (cond2_bb, 0)->dest == cond_bb)
2120 : {
2121 1928 : if (EDGE_SUCC (cond2_bb, 1)->dest != phi_bb)
2122 : return false;
2123 : cond2_phi_edge = EDGE_SUCC (cond2_bb, 1);
2124 : }
2125 402 : 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 2330 : tree arg2 = gimple_phi_arg_def (phi, cond2_phi_edge->dest_idx);
2130 2330 : if (!tree_fits_shwi_p (arg2))
2131 : return false;
2132 4660 : gcond *cond2 = safe_dyn_cast <gcond *> (*gsi_last_bb (cond2_bb));
2133 2330 : if (!cond2)
2134 : return false;
2135 2330 : enum tree_code cmp2 = gimple_cond_code (cond2);
2136 2330 : tree lhs2 = gimple_cond_lhs (cond2);
2137 2330 : tree rhs2 = gimple_cond_rhs (cond2);
2138 2330 : if (lhs2 == lhs1)
2139 : {
2140 2328 : if (!operand_equal_p (rhs2, rhs1, 0))
2141 : {
2142 331 : if ((cmp2 == EQ_EXPR || cmp2 == NE_EXPR)
2143 331 : && TREE_CODE (rhs1) == INTEGER_CST
2144 331 : && 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 331 : if (tree_int_cst_lt (rhs1, rhs2))
2150 : {
2151 331 : if (wi::ne_p (wi::to_wide (rhs1) + 1, wi::to_wide (rhs2)))
2152 : return false;
2153 331 : 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 2328 : tree arg3 = arg2;
2187 2328 : basic_block cond3_bb = cond2_bb;
2188 2328 : edge cond3_phi_edge = cond2_phi_edge;
2189 2328 : gcond *cond3 = cond2;
2190 2328 : enum tree_code cmp3 = cmp2;
2191 2328 : tree lhs3 = lhs2;
2192 2328 : tree rhs3 = rhs2;
2193 2328 : if (EDGE_COUNT (phi_bb->preds) == 4)
2194 : {
2195 406 : if (absu_hwi (tree_to_shwi (arg2)) != 1)
2196 : return false;
2197 398 : if ((cond2_phi_edge->flags & EDGE_FALSE_VALUE)
2198 398 : && HONOR_NANS (TREE_TYPE (lhs1)))
2199 : return false;
2200 398 : if (e1->flags & EDGE_TRUE_VALUE)
2201 : {
2202 398 : if (tree_to_shwi (arg0) != -128
2203 398 : || absu_hwi (tree_to_shwi (arg1)) != 1
2204 796 : || 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 398 : switch (cmp2)
2212 : {
2213 398 : case LT_EXPR:
2214 398 : case LE_EXPR:
2215 398 : case GT_EXPR:
2216 398 : case GE_EXPR:
2217 398 : 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 398 : if ((lhs2 == lhs1)
2232 398 : ^ (HONOR_NANS (TREE_TYPE (lhs1))
2233 398 : ? ((cmp2 == LT_EXPR || cmp2 == LE_EXPR)
2234 270 : != (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 398 : if (!single_pred_p (cond2_bb) || !cond_only_block_p (cond2_bb))
2243 0 : return false;
2244 398 : cond3_bb = single_pred (cond2_bb);
2245 398 : if (EDGE_COUNT (cond2_bb->succs) != 2)
2246 : return false;
2247 398 : 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 176 : 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 398 : arg3 = gimple_phi_arg_def (phi, cond3_phi_edge->dest_idx);
2258 637322 : cond3 = safe_dyn_cast <gcond *> (*gsi_last_bb (cond3_bb));
2259 398 : if (!cond3)
2260 : return false;
2261 398 : cmp3 = gimple_cond_code (cond3);
2262 398 : lhs3 = gimple_cond_lhs (cond3);
2263 398 : rhs3 = gimple_cond_rhs (cond3);
2264 398 : if (lhs3 == lhs1)
2265 : {
2266 398 : 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 1922 : else if (absu_hwi (tree_to_shwi (arg0)) != 1
2278 1902 : || absu_hwi (tree_to_shwi (arg1)) != 1
2279 3804 : || wi::to_widest (arg0) == wi::to_widest (arg1)
2280 3824 : || HONOR_NANS (TREE_TYPE (lhs1)))
2281 20 : return false;
2282 :
2283 2300 : if (!integer_zerop (arg3) || (cmp3 != EQ_EXPR && cmp3 != NE_EXPR))
2284 : return false;
2285 2300 : if ((cond3_phi_edge->flags & (cmp3 == EQ_EXPR
2286 2300 : ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE)) == 0)
2287 : return false;
2288 :
2289 : /* lhs1 one_cmp rhs1 results in phires of 1. */
2290 2300 : enum tree_code one_cmp;
2291 4600 : if ((cmp1 == LT_EXPR || cmp1 == LE_EXPR)
2292 2372 : ^ (!integer_onep ((e1->flags & EDGE_TRUE_VALUE) ? arg1 : arg0)))
2293 : one_cmp = LT_EXPR;
2294 : else
2295 1695 : one_cmp = GT_EXPR;
2296 :
2297 2300 : enum tree_code res_cmp;
2298 2300 : bool negate_p = false;
2299 2300 : switch (cmp)
2300 : {
2301 1265 : case EQ_EXPR:
2302 1265 : if (integer_zerop (rhs) && !HONOR_NANS (TREE_TYPE (lhs1)))
2303 : res_cmp = EQ_EXPR;
2304 1181 : else if (integer_minus_onep (rhs))
2305 746 : res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
2306 435 : else if (integer_onep (rhs))
2307 : res_cmp = one_cmp;
2308 : else
2309 : return false;
2310 : break;
2311 936 : case NE_EXPR:
2312 936 : if (integer_zerop (rhs) && !HONOR_NANS (TREE_TYPE (lhs1)))
2313 : res_cmp = NE_EXPR;
2314 898 : else if (integer_minus_onep (rhs))
2315 525 : res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
2316 432 : else if (integer_onep (rhs))
2317 642 : res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
2318 : else
2319 : return false;
2320 906 : if (HONOR_NANS (TREE_TYPE (lhs1)))
2321 : negate_p = true;
2322 : break;
2323 27 : case LT_EXPR:
2324 27 : if (integer_onep (rhs))
2325 0 : res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
2326 27 : else if (integer_zerop (rhs))
2327 27 : res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
2328 : else
2329 : return false;
2330 27 : 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 68 : case GE_EXPR:
2352 68 : if (integer_zerop (rhs))
2353 68 : 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 2228 : if (orig_use_lhs)
2363 88 : res_cmp = swap_tree_comparison (res_cmp);
2364 :
2365 2228 : tree clhs1 = lhs1, crhs1 = rhs1;
2366 2228 : if (negate_p)
2367 : {
2368 48 : if (cfun->can_throw_non_call_exceptions)
2369 0 : return false;
2370 48 : res_cmp = invert_tree_comparison (res_cmp, false);
2371 48 : clhs1 = make_ssa_name (boolean_type_node);
2372 48 : gimple *g = gimple_build_assign (clhs1, res_cmp, lhs1, rhs1);
2373 48 : gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
2374 48 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2375 48 : crhs1 = boolean_false_node;
2376 48 : res_cmp = EQ_EXPR;
2377 : }
2378 :
2379 2228 : if (gimple_code (use_stmt) == GIMPLE_COND)
2380 : {
2381 1625 : gcond *use_cond = as_a <gcond *> (use_stmt);
2382 1625 : gimple_cond_set_code (use_cond, res_cmp);
2383 1625 : gimple_cond_set_lhs (use_cond, clhs1);
2384 1625 : gimple_cond_set_rhs (use_cond, crhs1);
2385 : }
2386 603 : else if (gimple_assign_rhs_class (use_stmt) == GIMPLE_BINARY_RHS)
2387 : {
2388 603 : gimple_assign_set_rhs_code (use_stmt, res_cmp);
2389 603 : gimple_assign_set_rhs1 (use_stmt, clhs1);
2390 603 : 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 2228 : update_stmt (use_stmt);
2399 :
2400 2228 : if (MAY_HAVE_DEBUG_BIND_STMTS)
2401 : {
2402 1893 : use_operand_p use_p;
2403 1893 : imm_use_iterator iter;
2404 1893 : bool has_debug_uses = false;
2405 1893 : bool has_cast1_debug_uses = false;
2406 1893 : bool has_neg_debug_uses = false;
2407 1893 : bool has_cast2_debug_uses = false;
2408 3830 : FOR_EACH_IMM_USE_FAST (use_p, iter, phires)
2409 : {
2410 1937 : gimple *use_stmt = USE_STMT (use_p);
2411 1937 : if (is_gimple_debug (use_stmt))
2412 : {
2413 : has_debug_uses = true;
2414 : break;
2415 : }
2416 1893 : }
2417 1893 : 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 1893 : 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 1893 : gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi));
2484 1893 : tree type = TREE_TYPE (phires);
2485 1893 : tree minus_one = build_int_cst (type, -1);
2486 1893 : 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 1893 : tree temp1 = build_debug_expr_decl (type);
2498 1893 : tree t = build2 (one_cmp, boolean_type_node, lhs1, rhs2);
2499 1893 : t = build3 (COND_EXPR, type, t, build_one_cst (type),
2500 : minus_one);
2501 1893 : gimple *g = gimple_build_debug_bind (temp1, t, phi);
2502 1893 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2503 1893 : tree temp2 = build_debug_expr_decl (type);
2504 1893 : t = build2 (EQ_EXPR, boolean_type_node, lhs1, rhs2);
2505 1893 : t = build3 (COND_EXPR, type, t, build_zero_cst (type), temp1);
2506 1893 : g = gimple_build_debug_bind (temp2, t, phi);
2507 1893 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2508 1893 : replace_uses_by (phires, temp2);
2509 1893 : 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 1893 : 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 1893 : 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 2228 : if (orig_use_lhs)
2539 : {
2540 88 : gimple_stmt_iterator gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (orig_use_lhs));
2541 88 : gsi_remove (&gsi, true);
2542 88 : gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (temps[1]));
2543 88 : gsi_remove (&gsi, true);
2544 88 : gsi = gsi_for_stmt (orig_use_stmt);
2545 88 : gsi_remove (&gsi, true);
2546 88 : release_ssa_name (orig_use_lhs);
2547 88 : release_ssa_name (temps[1]);
2548 88 : release_ssa_name (temps[0]);
2549 : }
2550 :
2551 2228 : gimple_stmt_iterator psi = gsi_for_stmt (phi);
2552 2228 : remove_phi_node (&psi, true);
2553 2228 : statistics_counter_event (cfun, "spaceship replacement", 1);
2554 :
2555 2228 : 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 445398 : 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 445398 : gimple_stmt_iterator gsi, gsi_from;
2597 445398 : gimple *call;
2598 445398 : gimple *cast = NULL;
2599 445398 : 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 445398 : gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
2609 445398 : if (gsi_end_p (gsi))
2610 : return false;
2611 282885 : cast = gsi_stmt (gsi);
2612 282885 : gsi_next_nondebug (&gsi);
2613 282885 : if (!gsi_end_p (gsi))
2614 : {
2615 137484 : call = gsi_stmt (gsi);
2616 137484 : gsi_next_nondebug (&gsi);
2617 137484 : 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 192709 : if (!is_gimple_call (call))
2628 : return false;
2629 :
2630 5056 : lhs = gimple_get_lhs (call);
2631 :
2632 5056 : if (lhs == NULL_TREE)
2633 : return false;
2634 :
2635 5030 : combined_fn cfn = gimple_call_combined_fn (call);
2636 5030 : if (gimple_call_num_args (call) != 1
2637 5030 : && (gimple_call_num_args (call) != 2
2638 : || cfn == CFN_CLZ
2639 578 : || cfn == CFN_CTZ))
2640 : return false;
2641 :
2642 3521 : arg = gimple_call_arg (call, 0);
2643 :
2644 3521 : internal_fn ifn = IFN_LAST;
2645 3521 : int val = 0;
2646 3521 : bool any_val = false;
2647 3521 : 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 730 : CASE_CFN_CLZ:
2656 730 : if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
2657 : {
2658 730 : tree type = TREE_TYPE (arg);
2659 730 : 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 726 : if (direct_internal_fn_supported_p (IFN_CLZ, type, OPTIMIZE_FOR_BOTH)
2677 1427 : && 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 266 : CASE_CFN_CTZ:
2686 266 : if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
2687 : {
2688 266 : tree type = TREE_TYPE (arg);
2689 266 : 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 262 : if (direct_internal_fn_supported_p (IFN_CTZ, type, OPTIMIZE_FOR_BOTH)
2707 503 : && 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 142 : 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 54 : if (gimple_code (cast) != GIMPLE_ASSIGN
2733 54 : || !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 24 : if (arg != gimple_assign_lhs (cast))
2737 : return false;
2738 24 : arg = gimple_assign_rhs1 (cast);
2739 : }
2740 :
2741 224 : 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 112 : if (!cond
2746 112 : || (gimple_cond_code (cond) != NE_EXPR
2747 20 : && gimple_cond_code (cond) != EQ_EXPR)
2748 112 : || !integer_zerop (gimple_cond_rhs (cond))
2749 112 : || arg != gimple_cond_lhs (cond))
2750 78 : return false;
2751 :
2752 34 : 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 34 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
2756 :
2757 : /* Forward the edges over the middle basic block. */
2758 34 : if (true_edge->dest == middle_bb)
2759 34 : true_edge = EDGE_SUCC (true_edge->dest, 0);
2760 34 : 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 34 : if (true_edge == e1)
2768 34 : 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 34 : if (gimple_cond_code (cond) == EQ_EXPR)
2780 2 : std::swap (arg0, arg1);
2781 :
2782 : /* Check PHI arguments. */
2783 34 : if (lhs != arg0
2784 32 : || TREE_CODE (arg1) != INTEGER_CST)
2785 : return false;
2786 24 : 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 24 : 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 19626459 : refs_hasher::hash (const ref_to_bb *n)
2882 : {
2883 19626459 : inchash::hash hstate;
2884 19626459 : inchash::add_expr (n->exp, hstate, OEP_ADDRESS_OF);
2885 19626459 : hstate.add_hwi (n->size);
2886 19626459 : return hstate.end ();
2887 : }
2888 :
2889 : /* The equality function of *P1 and *P2. */
2890 :
2891 : inline bool
2892 14354105 : refs_hasher::equal (const ref_to_bb *n1, const ref_to_bb *n2)
2893 : {
2894 14354105 : return operand_equal_p (n1->exp, n2->exp, OEP_ADDRESS_OF)
2895 14354105 : && n1->size == n2->size;
2896 : }
2897 :
2898 : class nontrapping_dom_walker : public dom_walker
2899 : {
2900 : public:
2901 1039719 : nontrapping_dom_walker (cdi_direction direction, hash_set<tree> *ps)
2902 1039719 : : dom_walker (direction), m_nontrapping (ps), m_seen_refs (128)
2903 1039719 : {}
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 11487898 : nontrapping_dom_walker::before_dom_children (basic_block bb)
2926 : {
2927 11487898 : edge e;
2928 11487898 : edge_iterator ei;
2929 11487898 : gimple_stmt_iterator gsi;
2930 :
2931 : /* If we haven't seen all our predecessors, clear the hash-table. */
2932 25214638 : FOR_EACH_EDGE (e, ei, bb->preds)
2933 14409155 : if ((((size_t)e->src->aux) & 2) == 0)
2934 : {
2935 682415 : nt_call_phase++;
2936 682415 : break;
2937 : }
2938 :
2939 : /* Mark this BB as being on the path to dominator root and as visited. */
2940 11487898 : bb->aux = (void*)(1 | 2);
2941 :
2942 : /* And walk the statements in order. */
2943 100785199 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2944 : {
2945 77809403 : gimple *stmt = gsi_stmt (gsi);
2946 :
2947 77809403 : if ((gimple_code (stmt) == GIMPLE_ASM && gimple_vdef (stmt))
2948 77852549 : || (is_gimple_call (stmt)
2949 5493295 : && (!nonfreeing_call_p (stmt) || !nonbarrier_call_p (stmt))))
2950 4926372 : nt_call_phase++;
2951 87689821 : else if (gimple_assign_single_p (stmt) && !gimple_has_volatile_ops (stmt))
2952 : {
2953 12966980 : add_or_mark_expr (bb, gimple_assign_lhs (stmt), true);
2954 12966980 : add_or_mark_expr (bb, gimple_assign_rhs1 (stmt), false);
2955 : }
2956 : }
2957 11487898 : return NULL;
2958 : }
2959 :
2960 : /* Called by walk_dominator_tree, when basic block BB is exited. */
2961 : void
2962 11487898 : nontrapping_dom_walker::after_dom_children (basic_block bb)
2963 : {
2964 : /* This BB isn't on the path to dominator root anymore. */
2965 11487898 : bb->aux = (void*)2;
2966 11487898 : }
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 25933960 : nontrapping_dom_walker::add_or_mark_expr (basic_block bb, tree exp, bool store)
2978 : {
2979 25933960 : HOST_WIDE_INT size;
2980 :
2981 25933960 : if ((TREE_CODE (exp) == MEM_REF || TREE_CODE (exp) == ARRAY_REF
2982 21672788 : || TREE_CODE (exp) == COMPONENT_REF)
2983 32926659 : && (size = int_size_in_bytes (TREE_TYPE (exp))) > 0)
2984 : {
2985 11253866 : struct ref_to_bb map;
2986 11253866 : ref_to_bb **slot;
2987 11253866 : struct ref_to_bb *r2bb;
2988 11253866 : basic_block found_bb = 0;
2989 :
2990 11253866 : if (!store)
2991 : {
2992 5157422 : 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 5157422 : if (!auto_var_p (base) || TREE_ADDRESSABLE (base))
2997 4195598 : return;
2998 : }
2999 :
3000 : /* Try to find the last seen *_REF, which can trap. */
3001 7058268 : map.exp = exp;
3002 7058268 : map.size = size;
3003 7058268 : slot = m_seen_refs.find_slot (&map, INSERT);
3004 7058268 : r2bb = *slot;
3005 7058268 : if (r2bb && r2bb->phase >= nt_call_phase)
3006 288926 : 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 288926 : if (found_bb && (((size_t)found_bb->aux) & 1) == 1)
3012 : {
3013 80801 : m_nontrapping->add (exp);
3014 : }
3015 : else
3016 : {
3017 : /* EXP might trap, so insert it into the hash table. */
3018 6977467 : if (r2bb)
3019 : {
3020 964523 : r2bb->phase = nt_call_phase;
3021 964523 : r2bb->bb = bb;
3022 : }
3023 : else
3024 : {
3025 6012944 : r2bb = XNEW (struct ref_to_bb);
3026 6012944 : r2bb->phase = nt_call_phase;
3027 6012944 : r2bb->bb = bb;
3028 6012944 : r2bb->exp = exp;
3029 6012944 : r2bb->size = size;
3030 6012944 : *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 1039719 : get_non_trapping (void)
3042 : {
3043 1039719 : nt_call_phase = 0;
3044 1039719 : hash_set<tree> *nontrap = new hash_set<tree>;
3045 :
3046 2079438 : nontrapping_dom_walker (CDI_DOMINATORS, nontrap)
3047 1039719 : .walk (cfun->cfg->x_entry_block_ptr);
3048 :
3049 1039719 : clear_aux_for_blocks ();
3050 1039719 : 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 428588 : cond_store_replacement (basic_block middle_bb, basic_block join_bb, edge e0,
3072 : edge e1, gimple *assign, hash_set<tree> *nontrap)
3073 : {
3074 428588 : tree lhs, rhs, name, name2;
3075 428588 : gphi *newphi;
3076 428588 : gassign *new_stmt;
3077 428588 : gimple_stmt_iterator gsi;
3078 428588 : location_t locus;
3079 :
3080 : /* Check if middle_bb contains of only one store. */
3081 428588 : if (!assign
3082 187700 : || !gimple_assign_single_p (assign)
3083 462466 : || gimple_has_volatile_ops (assign))
3084 : return false;
3085 :
3086 33677 : locus = gimple_location (assign);
3087 33677 : lhs = gimple_assign_lhs (assign);
3088 33677 : rhs = gimple_assign_rhs1 (assign);
3089 33677 : if ((!REFERENCE_CLASS_P (lhs)
3090 33677 : && !DECL_P (lhs))
3091 33677 : || !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 33179 : ssa_op_iter iter;
3097 33179 : tree use;
3098 64639 : FOR_EACH_SSA_TREE_OPERAND (use, assign, iter, SSA_OP_USE)
3099 : {
3100 35793 : if (use == rhs)
3101 14689 : continue;
3102 :
3103 21104 : gimple *stmt = SSA_NAME_DEF_STMT (use);
3104 21104 : 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 28846 : if (nontrap->contains (lhs))
3112 : {
3113 : /* Make sure there is no load in the middle bb,
3114 : this invalidates nontrap.
3115 : FIXME: this is over conserative, this check could be made to
3116 : allow loads unrelated to lhs. */
3117 7114 : tree vuse = gimple_vuse (assign);
3118 7114 : imm_use_iterator iter;
3119 7114 : gimple *use_stmt;
3120 30983 : FOR_EACH_IMM_USE_STMT (use_stmt, iter, vuse)
3121 : {
3122 17531 : if (use_stmt == assign)
3123 7089 : continue;
3124 10442 : if (gimple_bb (use_stmt) == middle_bb)
3125 776 : return false;
3126 7114 : }
3127 : }
3128 : else
3129 : {
3130 : /* If LHS is an access to a local variable without address-taken
3131 : (or when we allow data races) and known not to trap, we could
3132 : always safely move down the store. */
3133 21732 : tree base;
3134 21732 : if (ref_can_have_store_data_races (lhs)
3135 1146 : || tree_could_trap_p (lhs)
3136 : /* tree_could_trap_p is a predicate for rvalues, so check
3137 : for readonly memory explicitly. */
3138 22047 : || ((base = get_base_address (lhs))
3139 315 : && ((DECL_P (base)
3140 308 : && TREE_READONLY (base))
3141 310 : || TREE_CODE (base) == STRING_CST)))
3142 21428 : return false;
3143 : }
3144 :
3145 : /* Now we've checked the constraints, so do the transformation:
3146 : 1) Remove the single store. */
3147 6642 : gsi = gsi_for_stmt (assign);
3148 6642 : unlink_stmt_vdef (assign);
3149 6642 : gsi_remove (&gsi, true);
3150 6642 : release_defs (assign);
3151 :
3152 : /* Make both store and load use alias-set zero as we have to
3153 : deal with the case of the store being a conditional change
3154 : of the dynamic type. */
3155 6642 : lhs = unshare_expr (lhs);
3156 6642 : tree *basep = &lhs;
3157 13375 : while (handled_component_p (*basep))
3158 6733 : basep = &TREE_OPERAND (*basep, 0);
3159 6642 : if (TREE_CODE (*basep) == MEM_REF
3160 6642 : || TREE_CODE (*basep) == TARGET_MEM_REF)
3161 1053 : TREE_OPERAND (*basep, 1)
3162 2106 : = fold_convert (ptr_type_node, TREE_OPERAND (*basep, 1));
3163 : else
3164 5589 : *basep = build2 (MEM_REF, TREE_TYPE (*basep),
3165 : build_fold_addr_expr (*basep),
3166 : build_zero_cst (ptr_type_node));
3167 :
3168 : /* 2) Insert a load from the memory of the store to the temporary
3169 : on the edge which did not contain the store. */
3170 6642 : name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3171 6642 : new_stmt = gimple_build_assign (name, lhs);
3172 6642 : gimple_set_location (new_stmt, locus);
3173 6642 : lhs = unshare_expr (lhs);
3174 6642 : {
3175 : /* Set the no-warning bit on the rhs of the load to avoid uninit
3176 : warnings. */
3177 6642 : tree rhs1 = gimple_assign_rhs1 (new_stmt);
3178 6642 : suppress_warning (rhs1, OPT_Wuninitialized);
3179 : }
3180 6642 : gsi_insert_on_edge (e1, new_stmt);
3181 :
3182 : /* 3) Create a PHI node at the join block, with one argument
3183 : holding the old RHS, and the other holding the temporary
3184 : where we stored the old memory contents. */
3185 6642 : name2 = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3186 6642 : newphi = create_phi_node (name2, join_bb);
3187 6642 : add_phi_arg (newphi, rhs, e0, locus);
3188 6642 : add_phi_arg (newphi, name, e1, locus);
3189 :
3190 6642 : new_stmt = gimple_build_assign (lhs, gimple_phi_result (newphi));
3191 :
3192 : /* 4) Insert that PHI node. */
3193 6642 : gsi = gsi_after_labels (join_bb);
3194 6642 : if (gsi_end_p (gsi))
3195 : {
3196 36 : gsi = gsi_last_bb (join_bb);
3197 36 : gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
3198 : }
3199 : else
3200 6606 : gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
3201 :
3202 6642 : if (dump_file && (dump_flags & TDF_DETAILS))
3203 : {
3204 8 : fprintf (dump_file, "\nConditional store replacement happened!");
3205 8 : fprintf (dump_file, "\nReplaced the store with a load.");
3206 8 : fprintf (dump_file, "\nInserted a new PHI statement in joint block:\n");
3207 8 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_VOPS|TDF_MEMSYMS);
3208 : }
3209 6642 : statistics_counter_event (cfun, "conditional store replacement", 1);
3210 :
3211 6642 : return true;
3212 : }
3213 :
3214 : /* Do the main work of conditional store replacement. */
3215 :
3216 : static bool
3217 830439 : cond_if_else_store_replacement_1 (basic_block then_bb, basic_block else_bb,
3218 : basic_block join_bb, gimple *then_assign,
3219 : gimple *else_assign,
3220 : gphi *vphi)
3221 : {
3222 830439 : tree lhs_base, lhs, then_rhs, else_rhs, name;
3223 830439 : location_t then_locus, else_locus;
3224 830439 : gimple_stmt_iterator gsi;
3225 830439 : gphi *newphi = nullptr;
3226 830439 : gassign *new_stmt;
3227 :
3228 830439 : if (then_assign == NULL
3229 830439 : || !gimple_assign_single_p (then_assign)
3230 758232 : || else_assign == NULL
3231 758232 : || !gimple_assign_single_p (else_assign)
3232 90888 : || stmt_references_abnormal_ssa_name (then_assign)
3233 921313 : || stmt_references_abnormal_ssa_name (else_assign))
3234 739565 : return false;
3235 :
3236 : /* Allow both being clobbers but no other volatile operations. */
3237 90874 : if (gimple_clobber_p (then_assign)
3238 90874 : && gimple_clobber_p (else_assign))
3239 : ;
3240 165480 : else if (gimple_has_volatile_ops (then_assign)
3241 165480 : || gimple_has_volatile_ops (else_assign))
3242 : return false;
3243 :
3244 82728 : lhs = gimple_assign_lhs (then_assign);
3245 82728 : if (!operand_equal_p (lhs, gimple_assign_lhs (else_assign), 0))
3246 : return false;
3247 :
3248 30963 : lhs_base = get_base_address (lhs);
3249 30963 : if (lhs_base == NULL_TREE
3250 30963 : || (!DECL_P (lhs_base) && TREE_CODE (lhs_base) != MEM_REF))
3251 : return false;
3252 :
3253 30883 : then_rhs = gimple_assign_rhs1 (then_assign);
3254 30883 : else_rhs = gimple_assign_rhs1 (else_assign);
3255 30883 : then_locus = gimple_location (then_assign);
3256 30883 : else_locus = gimple_location (else_assign);
3257 :
3258 30883 : if (!is_gimple_reg_type (TREE_TYPE (lhs)))
3259 : {
3260 : /* Handle clobbers separately as operand_equal_p does not check
3261 : the kind of the clobbers being the same. */
3262 5753 : if (TREE_CLOBBER_P (then_rhs) && TREE_CLOBBER_P (else_rhs))
3263 : {
3264 2289 : if (CLOBBER_KIND (then_rhs) != CLOBBER_KIND (else_rhs))
3265 : return false;
3266 : }
3267 3464 : else if (!operand_equal_p (then_rhs, else_rhs))
3268 : return false;
3269 : /* Currently only handle commoning of `= {}`. */
3270 2760 : if (TREE_CODE (then_rhs) != CONSTRUCTOR)
3271 : return false;
3272 : }
3273 :
3274 27506 : if (dump_file && (dump_flags & TDF_DETAILS))
3275 : {
3276 8 : if (TREE_CLOBBER_P (then_rhs))
3277 3 : fprintf(dump_file, "factoring out clobber:\n\tthen:\n");
3278 : else
3279 5 : fprintf(dump_file, "factoring out stores:\n\tthen:\n");
3280 8 : print_gimple_stmt (dump_file, then_assign, 0,
3281 : TDF_VOPS|TDF_MEMSYMS);
3282 8 : fprintf(dump_file, "\telse:\n");
3283 8 : print_gimple_stmt (dump_file, else_assign, 0,
3284 : TDF_VOPS|TDF_MEMSYMS);
3285 8 : fprintf (dump_file, "\n");
3286 : }
3287 :
3288 : /* Now we've checked the constraints, so do the transformation:
3289 : 1) Remove the stores. */
3290 27506 : gsi = gsi_for_stmt (then_assign);
3291 27506 : unlink_stmt_vdef (then_assign);
3292 27506 : gsi_remove (&gsi, true);
3293 27506 : release_defs (then_assign);
3294 :
3295 27506 : gsi = gsi_for_stmt (else_assign);
3296 27506 : unlink_stmt_vdef (else_assign);
3297 27506 : gsi_remove (&gsi, true);
3298 27506 : release_defs (else_assign);
3299 :
3300 : /* 2) Create a PHI node at the join block, with one argument
3301 : holding the old RHS, and the other holding the temporary
3302 : where we stored the old memory contents. */
3303 27506 : if (operand_equal_p (then_rhs, else_rhs))
3304 : name = then_rhs;
3305 : else
3306 : {
3307 22997 : name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3308 22997 : newphi = create_phi_node (name, join_bb);
3309 22997 : add_phi_arg (newphi, then_rhs, EDGE_SUCC (then_bb, 0), then_locus);
3310 22997 : add_phi_arg (newphi, else_rhs, EDGE_SUCC (else_bb, 0), else_locus);
3311 : }
3312 :
3313 27506 : new_stmt = gimple_build_assign (lhs, name);
3314 : /* Update the vdef for the new store statement. */
3315 27506 : tree newvphilhs = make_ssa_name (gimple_vop (cfun));
3316 27506 : tree vdef = gimple_phi_result (vphi);
3317 27506 : gimple_set_vuse (new_stmt, newvphilhs);
3318 27506 : gimple_set_vdef (new_stmt, vdef);
3319 27506 : gimple_phi_set_result (vphi, newvphilhs);
3320 27506 : SSA_NAME_DEF_STMT (vdef) = new_stmt;
3321 27506 : update_stmt (vphi);
3322 27506 : if (dump_file && (dump_flags & TDF_DETAILS))
3323 : {
3324 8 : if (newphi)
3325 : {
3326 4 : fprintf(dump_file, "to use phi:\n");
3327 4 : print_gimple_stmt (dump_file, newphi, 0,
3328 : TDF_VOPS|TDF_MEMSYMS);
3329 4 : fprintf(dump_file, "\n");
3330 : }
3331 : else
3332 4 : fprintf(dump_file, "to:\n");
3333 8 : print_gimple_stmt (dump_file, new_stmt, 0,
3334 : TDF_VOPS|TDF_MEMSYMS);
3335 8 : fprintf(dump_file, "\n\n");
3336 : }
3337 :
3338 : /* 3) Insert that new store. */
3339 27506 : gsi = gsi_after_labels (join_bb);
3340 27506 : if (gsi_end_p (gsi))
3341 : {
3342 86 : gsi = gsi_last_bb (join_bb);
3343 86 : gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
3344 : }
3345 : else
3346 27420 : gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
3347 :
3348 27506 : statistics_counter_event (cfun, "if-then-else store replacement", 1);
3349 :
3350 27506 : return true;
3351 : }
3352 :
3353 : /* Return the last store in BB with VDEF or NULL if there are
3354 : loads following the store. VPHI is where the only use of the
3355 : vdef should be. If ONLYONESTORE is true, then the store is
3356 : the only store in the BB. */
3357 :
3358 : static gimple *
3359 2033142 : trailing_store_in_bb (basic_block bb, tree vdef, gphi *vphi, bool onlyonestore)
3360 : {
3361 2033142 : if (SSA_NAME_IS_DEFAULT_DEF (vdef))
3362 : return NULL;
3363 2009358 : gimple *store = SSA_NAME_DEF_STMT (vdef);
3364 2009358 : if (gimple_bb (store) != bb
3365 2009358 : || gimple_code (store) == GIMPLE_PHI)
3366 : return NULL;
3367 :
3368 : /* Verify there is no other store in this BB if requested. */
3369 1970667 : if (onlyonestore
3370 290256 : && !SSA_NAME_IS_DEFAULT_DEF (gimple_vuse (store))
3371 229723 : && gimple_bb (SSA_NAME_DEF_STMT (gimple_vuse (store))) == bb
3372 2054676 : && gimple_code (SSA_NAME_DEF_STMT (gimple_vuse (store))) != GIMPLE_PHI)
3373 : return NULL;
3374 :
3375 :
3376 : /* Verify there is no load or store after the store, the vdef of the store
3377 : should only be used by the vphi joining the 2 bbs. */
3378 1886664 : use_operand_p use_p;
3379 1886664 : gimple *use_stmt;
3380 3773328 : if (!single_imm_use (gimple_vdef (store), &use_p, &use_stmt))
3381 : return NULL;
3382 1864850 : if (use_stmt != vphi)
3383 : return NULL;
3384 :
3385 : return store;
3386 : }
3387 :
3388 : /* Return the only store in MIDDLE_BB as the candidate store for cselim. Return
3389 : NULL if no candidate can be found. */
3390 :
3391 : static gimple *
3392 428588 : cselim_candidate (basic_block middle_bb, basic_block join_bb, edge e0)
3393 : {
3394 428588 : gphi *vphi = get_virtual_phi (join_bb);
3395 428588 : if (!vphi)
3396 : return NULL;
3397 :
3398 263330 : tree middle_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, e0);
3399 263330 : return trailing_store_in_bb (middle_bb, middle_vdef, vphi, true);
3400 : }
3401 :
3402 : /* Limited Conditional store replacement. We already know
3403 : that the recognized pattern looks like so:
3404 :
3405 : split:
3406 : if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
3407 : THEN_BB:
3408 : ...
3409 : STORE = Y;
3410 : ...
3411 : goto JOIN_BB;
3412 : ELSE_BB:
3413 : ...
3414 : STORE = Z;
3415 : ...
3416 : fallthrough (edge E0)
3417 : JOIN_BB:
3418 : some more
3419 :
3420 : Handles only the case with store in THEN_BB and ELSE_BB. That is
3421 : cheap enough due to in phiopt and not worry about heurstics. Moving the store
3422 : out might provide an opportunity for a phiopt to happen.
3423 : At -O1 (!flag_expensive_optimizations), this only handles the only store in
3424 : the BBs. */
3425 :
3426 : static bool
3427 921557 : cond_if_else_store_replacement_limited (basic_block then_bb, basic_block else_bb,
3428 : basic_block join_bb)
3429 : {
3430 921557 : gphi *vphi = get_virtual_phi (join_bb);
3431 921557 : if (!vphi)
3432 : return false;
3433 :
3434 921557 : tree then_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (then_bb));
3435 1843114 : gimple *then_assign = trailing_store_in_bb (then_bb, then_vdef, vphi,
3436 921557 : !flag_expensive_optimizations);
3437 921557 : if (!then_assign)
3438 : return false;
3439 :
3440 848255 : tree else_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (else_bb));
3441 1696510 : gimple *else_assign = trailing_store_in_bb (else_bb, else_vdef, vphi,
3442 848255 : !flag_expensive_optimizations);
3443 848255 : if (!else_assign)
3444 : return false;
3445 :
3446 828895 : return cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
3447 828895 : then_assign, else_assign, vphi);
3448 : }
3449 :
3450 : /* Conditional store replacement. We already know
3451 : that the recognized pattern looks like so:
3452 :
3453 : split:
3454 : if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
3455 : THEN_BB:
3456 : ...
3457 : X = Y;
3458 : ...
3459 : goto JOIN_BB;
3460 : ELSE_BB:
3461 : ...
3462 : X = Z;
3463 : ...
3464 : fallthrough (edge E0)
3465 : JOIN_BB:
3466 : some more
3467 :
3468 : We check that it is safe to sink the store to JOIN_BB by verifying that
3469 : there are no read-after-write or write-after-write dependencies in
3470 : THEN_BB and ELSE_BB. */
3471 :
3472 : static bool
3473 230601 : cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb,
3474 : basic_block join_bb)
3475 : {
3476 230601 : vec<data_reference_p> then_datarefs, else_datarefs;
3477 230601 : vec<ddr_p> then_ddrs, else_ddrs;
3478 230601 : gimple *then_store, *else_store;
3479 230601 : bool found, ok = false, res;
3480 230601 : tree then_lhs, else_lhs;
3481 230601 : basic_block blocks[3];
3482 230601 : gphi *vphi = get_virtual_phi (join_bb);
3483 230601 : if (!vphi)
3484 : return false;
3485 :
3486 : /* Handle the case with trailing stores in THEN_BB and ELSE_BB. That is
3487 : cheap enough to always handle as it allows us to elide dependence
3488 : checking. */
3489 229033 : while (cond_if_else_store_replacement_limited (then_bb, else_bb, join_bb))
3490 : ;
3491 :
3492 : /* If either vectorization or if-conversion is disabled then do
3493 : not sink any stores. */
3494 215567 : if (param_max_stores_to_sink == 0
3495 215566 : || (!flag_tree_loop_vectorize && !flag_tree_slp_vectorize)
3496 210061 : || !flag_tree_loop_if_convert)
3497 : return false;
3498 :
3499 : /* Find data references. */
3500 210058 : then_datarefs.create (1);
3501 210058 : else_datarefs.create (1);
3502 210058 : if ((find_data_references_in_bb (NULL, then_bb, &then_datarefs)
3503 210058 : == chrec_dont_know)
3504 187249 : || !then_datarefs.length ()
3505 181641 : || (find_data_references_in_bb (NULL, else_bb, &else_datarefs)
3506 181641 : == chrec_dont_know)
3507 225144 : || !else_datarefs.length ())
3508 : {
3509 195970 : free_data_refs (then_datarefs);
3510 195970 : free_data_refs (else_datarefs);
3511 195970 : return false;
3512 : }
3513 :
3514 : /* Clear visited on else stores, we want to make sure to pick each store
3515 : at most once to avoid quadratic behavior. */
3516 50909 : for (auto else_dr : else_datarefs)
3517 : {
3518 36821 : if (DR_IS_READ (else_dr))
3519 19062 : continue;
3520 17759 : gimple_set_visited (DR_STMT (else_dr), false);
3521 : }
3522 :
3523 : /* Find pairs of stores with equal LHS. Work from the end to avoid
3524 : re-ordering stores unnecessarily. */
3525 14088 : auto_vec<std::pair<gimple *, gimple *>, 1> stores_pairs;
3526 14088 : unsigned i;
3527 14088 : data_reference_p then_dr;
3528 59650 : FOR_EACH_VEC_ELT_REVERSE (then_datarefs, i, then_dr)
3529 : {
3530 31474 : if (DR_IS_READ (then_dr))
3531 43983 : continue;
3532 :
3533 18965 : then_store = DR_STMT (then_dr);
3534 18965 : then_lhs = gimple_get_lhs (then_store);
3535 18965 : if (then_lhs == NULL_TREE)
3536 0 : continue;
3537 18965 : found = false;
3538 :
3539 18965 : unsigned j;
3540 18965 : data_reference_p else_dr;
3541 89798 : FOR_EACH_VEC_ELT_REVERSE (else_datarefs, j, else_dr)
3542 : {
3543 55473 : if (DR_IS_READ (else_dr))
3544 20235 : continue;
3545 :
3546 35238 : else_store = DR_STMT (else_dr);
3547 35238 : if (gimple_visited_p (else_store))
3548 3225 : continue;
3549 32013 : else_lhs = gimple_get_lhs (else_store);
3550 32013 : if (else_lhs == NULL_TREE)
3551 0 : continue;
3552 :
3553 32013 : if (operand_equal_p (then_lhs, else_lhs, 0))
3554 : {
3555 : found = true;
3556 : break;
3557 : }
3558 : }
3559 :
3560 18965 : if (!found)
3561 15360 : continue;
3562 :
3563 3605 : gimple_set_visited (else_store, true);
3564 3605 : stores_pairs.safe_push (std::make_pair (then_store, else_store));
3565 : }
3566 :
3567 : /* No pairs of stores found. */
3568 14088 : if (!stores_pairs.length ()
3569 14088 : || stores_pairs.length () > (unsigned) param_max_stores_to_sink)
3570 : {
3571 12014 : free_data_refs (then_datarefs);
3572 12014 : free_data_refs (else_datarefs);
3573 12014 : return false;
3574 : }
3575 :
3576 : /* Compute and check data dependencies in both basic blocks. */
3577 2074 : then_ddrs.create (1);
3578 2074 : else_ddrs.create (1);
3579 2074 : if (!compute_all_dependences (then_datarefs, &then_ddrs,
3580 2074 : vNULL, false)
3581 4148 : || !compute_all_dependences (else_datarefs, &else_ddrs,
3582 2074 : vNULL, false))
3583 : {
3584 0 : free_dependence_relations (then_ddrs);
3585 0 : free_dependence_relations (else_ddrs);
3586 0 : free_data_refs (then_datarefs);
3587 0 : free_data_refs (else_datarefs);
3588 0 : return false;
3589 : }
3590 2074 : blocks[0] = then_bb;
3591 2074 : blocks[1] = else_bb;
3592 2074 : blocks[2] = join_bb;
3593 2074 : renumber_gimple_stmt_uids_in_blocks (blocks, 3);
3594 :
3595 : /* Check that there are no read-after-write or write-after-write dependencies
3596 : in THEN_BB. */
3597 12657 : for (auto ddr : then_ddrs)
3598 : {
3599 7167 : struct data_reference *dra = DDR_A (ddr);
3600 7167 : struct data_reference *drb = DDR_B (ddr);
3601 :
3602 7167 : if (DDR_ARE_DEPENDENT (ddr) != chrec_known
3603 7167 : && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
3604 819 : && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
3605 1551 : || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
3606 473 : && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
3607 1078 : || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
3608 : {
3609 732 : free_dependence_relations (then_ddrs);
3610 732 : free_dependence_relations (else_ddrs);
3611 732 : free_data_refs (then_datarefs);
3612 732 : free_data_refs (else_datarefs);
3613 732 : return false;
3614 : }
3615 : }
3616 :
3617 : /* Check that there are no read-after-write or write-after-write dependencies
3618 : in ELSE_BB. */
3619 8481 : for (auto ddr : else_ddrs)
3620 : {
3621 4621 : struct data_reference *dra = DDR_A (ddr);
3622 4621 : struct data_reference *drb = DDR_B (ddr);
3623 :
3624 4621 : if (DDR_ARE_DEPENDENT (ddr) != chrec_known
3625 4621 : && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
3626 401 : && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
3627 567 : || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
3628 138 : && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
3629 429 : || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
3630 : {
3631 166 : free_dependence_relations (then_ddrs);
3632 166 : free_dependence_relations (else_ddrs);
3633 166 : free_data_refs (then_datarefs);
3634 166 : free_data_refs (else_datarefs);
3635 166 : return false;
3636 : }
3637 : }
3638 :
3639 : /* Sink stores with same LHS. */
3640 5072 : for (auto &store_pair : stores_pairs)
3641 : {
3642 1544 : then_store = store_pair.first;
3643 1544 : else_store = store_pair.second;
3644 1544 : res = cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
3645 : then_store, else_store, vphi);
3646 1544 : ok = ok || res;
3647 : }
3648 :
3649 1176 : free_dependence_relations (then_ddrs);
3650 1176 : free_dependence_relations (else_ddrs);
3651 1176 : free_data_refs (then_datarefs);
3652 1176 : free_data_refs (else_datarefs);
3653 :
3654 1176 : return ok;
3655 14088 : }
3656 :
3657 : /* If PHI at MERGE is a "load PHI", PHI <*P, *Q> whose two arguments are
3658 : single-use, non-volatile scalar MEM_REF loads reading the same memory state
3659 : (same VUSE), factor the load out: introduce P' = PHI <P, Q> and a single
3660 : load *P' replacing the PHI. No speculative load is introduced (the load uses
3661 : whichever pointer the taken edge selected).
3662 : E0/E1 are the middle bbs to MERGE edges.
3663 : EARLY_P is set when the first phiopt is run.
3664 : BEFORE_VECT is true if this is before vectorization, where some extra checks
3665 : are needed for profitability.
3666 : Returns true if a load was factored out. */
3667 :
3668 : static bool
3669 943040 : factor_out_conditional_load (edge e0, edge e1, basic_block merge, gphi *phi,
3670 : bool early_p, bool before_vect)
3671 : {
3672 : /* Factoring out a load during the first phi means we can't
3673 : trust if this is inside a loop or not; due to before inlining. */
3674 943040 : if (early_p)
3675 : return false;
3676 :
3677 : /* Before vectorization, we don't want to factor out loads unless not inside a loop. */
3678 749709 : if (before_vect && bb_loop_depth (merge) != 0)
3679 : return false;
3680 :
3681 : /* Not a virtual operand. */
3682 762208 : if (virtual_operand_p (gimple_phi_result (phi))
3683 : /* can only handle the merge bb having 2 predecessors. */
3684 762208 : || gimple_phi_num_args (phi) != 2)
3685 : return false;
3686 :
3687 146880 : tree arg0 = gimple_phi_arg_def (phi, e0->dest_idx);
3688 146880 : tree arg1 = gimple_phi_arg_def (phi, e1->dest_idx);
3689 : /* The load needs to be only used in the phi. */
3690 129370 : if (TREE_CODE (arg0) != SSA_NAME || TREE_CODE (arg1) != SSA_NAME
3691 264600 : || !has_single_use (arg0) || !has_single_use (arg1))
3692 : return false;
3693 :
3694 : /* Re-derive the loads and pointers validated by the predicate above. */
3695 61223 : gimple *load0 = SSA_NAME_DEF_STMT (arg0);
3696 61223 : gimple *load1 = SSA_NAME_DEF_STMT (arg1);
3697 :
3698 : /* Load have to need to be in the middle bbs. */
3699 61223 : if (gimple_bb (load0) != e0->src
3700 61223 : || gimple_bb (load1) != e1->src)
3701 : return false;
3702 :
3703 : /* The load needs to be a load with NO volatile ops. */
3704 77879 : if (!gimple_assign_load_p (load0) || !gimple_assign_load_p (load1)
3705 88959 : || gimple_has_volatile_ops (load0) || gimple_has_volatile_ops (load1))
3706 41929 : return false;
3707 :
3708 : /* Allow for stores/calls before the load. */
3709 15675 : if (gphi *vphi = get_virtual_phi (merge))
3710 : {
3711 22728 : if (gimple_vuse (load0) != gimple_phi_arg_def (vphi, e0->dest_idx)
3712 19640 : || gimple_vuse (load1) != gimple_phi_arg_def (vphi, e1->dest_idx))
3713 : return false;
3714 : }
3715 : else
3716 12933 : gcc_assert (gimple_vuse (load0) == gimple_vuse (load1));
3717 :
3718 12554 : tree ref0 = gimple_assign_rhs1 (load0);
3719 12554 : tree ref1 = gimple_assign_rhs1 (load1);
3720 :
3721 : /* Both must be *P loads of a compatible value type. The
3722 : TBAA alias-ptr type carried by MEM_REF operand 1 need not match; it is
3723 : merged the way get_alias_type_for_stmts does when the load is built. */
3724 4852 : if (TREE_CODE (ref0) != MEM_REF || TREE_CODE (ref1) != MEM_REF
3725 17241 : || !types_compatible_p (TREE_TYPE (ref0), TREE_TYPE (ref1)))
3726 7867 : return false;
3727 :
3728 : /* The alignment of the two accesses need to be the same. */
3729 4687 : if (TYPE_ALIGN (TREE_TYPE (ref0)) != TYPE_ALIGN (TREE_TYPE (ref1)))
3730 : return false;
3731 :
3732 4444 : tree p0 = TREE_OPERAND (ref0, 0);
3733 4444 : tree p1 = TREE_OPERAND (ref1, 0);
3734 4444 : if (!is_factor_profitable (load0, merge, &p0, 1))
3735 : return false;
3736 4426 : if (!is_factor_profitable (load1, merge, &p1, 1))
3737 : return false;
3738 :
3739 : /* Merge the two arms' TBAA info as get_alias_type_for_stmts does: keep the
3740 : common alias-ptr type and dependence clique/base when the arms agree,
3741 : otherwise fall back to ptr_type_node (alias-everything) and drop the
3742 : clique/base, so the combined load conservatively conflicts with any store
3743 : either original arm could. */
3744 4426 : unsigned short clique = MR_DEPENDENCE_CLIQUE (ref0);
3745 4426 : unsigned short base = MR_DEPENDENCE_BASE (ref0);
3746 4426 : if (clique != MR_DEPENDENCE_CLIQUE (ref1) || base != MR_DEPENDENCE_BASE (ref1))
3747 : clique = base = 0;
3748 4426 : tree atype = TREE_TYPE (TREE_OPERAND (ref0, 1));
3749 4426 : if (!alias_ptr_types_compatible_p (atype, TREE_TYPE (TREE_OPERAND (ref1, 1))))
3750 : {
3751 588 : atype = ptr_type_node;
3752 588 : clique = base = 0;
3753 : }
3754 :
3755 4426 : tree index0 = TREE_OPERAND (ref0, 1);
3756 4426 : tree index1 = TREE_OPERAND (ref1, 1);
3757 4426 : tree newindex;
3758 4426 : gimple_stmt_iterator gsi;
3759 4426 : gsi = gsi_after_labels (merge);
3760 :
3761 : /* Try to handle different indices. */
3762 4426 : if (operand_equal_p (index0, index1))
3763 3893 : newindex = fold_convert (atype, index0);
3764 : /* FIXME: right now non ssa names with different indices are not handled. */
3765 533 : else if (TREE_CODE (p0) != SSA_NAME || TREE_CODE (p1) != SSA_NAME)
3766 : return false;
3767 : /* If we have the same base already, just create a phi for the index
3768 : and the pointer plus will be done in the merge. */
3769 68 : else if (p0 == p1)
3770 : {
3771 52 : index0 = fold_convert (sizetype, index0);
3772 52 : index1 = fold_convert (sizetype, index1);
3773 52 : tree index = make_ssa_name (sizetype);
3774 52 : gphi *pphi = create_phi_node (index, merge);
3775 52 : add_phi_arg (pphi, index0, e0, gimple_phi_arg_location (phi, e0->dest_idx));
3776 52 : add_phi_arg (pphi, index1, e1, gimple_phi_arg_location (phi, e1->dest_idx));
3777 52 : p0 = gimple_build (&gsi, true, GSI_SAME_STMT,
3778 : UNKNOWN_LOCATION,
3779 : POINTER_PLUS_EXPR, atype, p0, index);
3780 : /* Since we already have the same pointer for both, just set that way.
3781 : Also the index offset is already 0 because we just did the add. */
3782 52 : p1 = p0;
3783 52 : newindex = build_zero_cst (atype);
3784 52 : if (dump_file && (dump_flags & TDF_DETAILS))
3785 : {
3786 1 : fprintf (dump_file, "new PHI ");
3787 1 : print_generic_expr (dump_file, index);
3788 1 : fprintf (dump_file,
3789 : " was created for the index.\n");
3790 : }
3791 : }
3792 : else
3793 : {
3794 16 : gimple_stmt_iterator gsi_index;
3795 : /* When the indices are different create 2 new pointers on each
3796 : of the middle bb right after the original load.
3797 : Note in the case of 0 index, gimple_build just returns
3798 : the original pointer. */
3799 16 : gsi_index = gsi_for_stmt (load0);
3800 16 : index0 = fold_convert (sizetype, index0);
3801 16 : p0 = gimple_build (&gsi_index, false, GSI_SAME_STMT,
3802 : gimple_location (load0),
3803 : POINTER_PLUS_EXPR, atype, p0, index0);
3804 :
3805 16 : gsi_index = gsi_for_stmt (load1);
3806 16 : index1 = fold_convert (sizetype, index1);
3807 16 : p1 = gimple_build (&gsi_index, false, GSI_SAME_STMT,
3808 : gimple_location (load1),
3809 : POINTER_PLUS_EXPR, atype, p1, index1);
3810 16 : newindex = build_zero_cst (atype);
3811 16 : if (dump_file && (dump_flags & TDF_DETAILS))
3812 : {
3813 1 : fprintf (dump_file, "new ptrs ");
3814 1 : print_generic_expr (dump_file, p0);
3815 1 : fprintf (dump_file, " and ");
3816 1 : print_generic_expr (dump_file, p1);
3817 1 : fprintf (dump_file,
3818 : " was created due to different offsets.\n");
3819 : }
3820 : }
3821 :
3822 3961 : tree newptr;
3823 3961 : if (p0 != p1)
3824 : {
3825 : /* We can't factor out a non-ssa named based load
3826 : as it might cause a variable not taken an
3827 : address to become needing the address taken.
3828 : An example is in go.
3829 : Were we produce:
3830 : _24 = PHI <&crypto/tls.cipherSuitesPreferenceOrder(36), &crypto/tls.cipherSuitesPreferenceOrderNoAES(37)>
3831 : And &crypto/tls.cipherSuitesPreferenceOrder address bit was not set.
3832 : FIXME: Refine to check ADDRESSABLE bit. */
3833 2762 : if (TREE_CODE (p0) != SSA_NAME || TREE_CODE (p1) != SSA_NAME)
3834 : return false;
3835 : /* Build P' = PHI <P, Q> and the single load result = *P'. */
3836 301 : newptr = make_ssa_name (TREE_TYPE (p0));
3837 301 : gphi *pphi = create_phi_node (newptr, merge);
3838 301 : add_phi_arg (pphi, p0, e0, gimple_phi_arg_location (phi, e0->dest_idx));
3839 301 : add_phi_arg (pphi, p1, e1, gimple_phi_arg_location (phi, e1->dest_idx));
3840 : }
3841 : else
3842 : newptr = p0;
3843 :
3844 : /* Build the combined load RES = *PTR, reusing the PHI result so any range
3845 : info on it is preserved (as factor_out_conditional_operation does). */
3846 1500 : tree nref = build2 (MEM_REF, TREE_TYPE (ref0), newptr, newindex);
3847 1500 : MR_DEPENDENCE_CLIQUE (nref) = clique;
3848 1500 : MR_DEPENDENCE_BASE (nref) = base;
3849 1500 : tree res = gimple_phi_result (phi);
3850 1500 : gassign *load = gimple_build_assign (res, nref);
3851 1500 : if (gphi *vphi = get_virtual_phi (merge))
3852 1189 : gimple_set_vuse (load, gimple_phi_result (vphi));
3853 : else
3854 622 : gimple_set_vuse (load, gimple_vuse (load0));
3855 1500 : gsi_insert_before (&gsi, load, GSI_SAME_STMT);
3856 :
3857 : /* RES is now defined by the load; drop the original PHI. */
3858 1500 : gsi = gsi_for_stmt (phi);
3859 1500 : gsi_remove (&gsi, true);
3860 :
3861 : /* The two arm loads are now dead. */
3862 1500 : gsi = gsi_for_stmt (load0);
3863 1500 : gsi_remove (&gsi, true);
3864 1500 : release_defs (load0);
3865 1500 : gsi = gsi_for_stmt (load1);
3866 1500 : gsi_remove (&gsi, true);
3867 1500 : release_defs (load1);
3868 :
3869 1500 : if (dump_file && (dump_flags & TDF_DETAILS))
3870 : {
3871 7 : fprintf (dump_file, "PHI ");
3872 7 : print_generic_expr (dump_file, res);
3873 7 : fprintf (dump_file,
3874 : " changed to factor out load from COND_EXPR.\n");
3875 7 : if (p0 != p1)
3876 : {
3877 6 : fprintf (dump_file, "new PHI ");
3878 6 : print_generic_expr (dump_file, newptr);
3879 6 : fprintf (dump_file,
3880 : " was created for the pointers.\n");
3881 : }
3882 : }
3883 :
3884 1500 : statistics_counter_event (cfun, "factored load out of COND_EXPR", 1);
3885 1500 : return true;
3886 : }
3887 :
3888 : /* Factor out operations and stores from the phi of the MERGE block coming
3889 : in from the edges E1 and E2 if possible. COND_STMT is the conditional
3890 : statement of the origin block. DIAMOND_P says that both E1 and E2 src
3891 : are not the origin block but rather 2 middle BBs. EARLY_P is true if
3892 : this was the early phi-opt.
3893 : Returns true if a factoring happened. */
3894 : static bool
3895 2474585 : factor_out_all (edge e1, edge e2, basic_block merge,
3896 : gcond *cond_stmt, bool diamond_p, bool early_p)
3897 : {
3898 2474585 : bool changed = false;
3899 2474585 : bool do_over;
3900 2474585 : basic_block bb1 = e1->src;
3901 2474585 : basic_block bb2 = e2->src;
3902 2450252 : do
3903 : {
3904 2516752 : do_over = false;
3905 2516752 : if (diamond_p && get_virtual_phi (merge))
3906 : {
3907 692524 : if (cond_if_else_store_replacement_limited (bb1, bb2, merge))
3908 : {
3909 12738 : changed = true;
3910 12738 : do_over = true;
3911 12738 : continue;
3912 : }
3913 : }
3914 2504014 : if (!single_pred_p (bb1))
3915 : break;
3916 2437514 : gphi_iterator gsi;
3917 5390916 : for (gsi = gsi_start_phis (merge); !gsi_end_p (gsi); gsi_next (&gsi))
3918 : {
3919 2982831 : gphi *phi = *gsi;
3920 : /* Conditional load elimination can only be on a diamond. */
3921 2982831 : if ((diamond_p
3922 943040 : && factor_out_conditional_load (e1, e2, merge, phi, early_p,
3923 943040 : !fold_before_rtl_expansion_p ()))
3924 3924371 : || factor_out_conditional_operation (e1, e2, merge, phi,
3925 : cond_stmt, early_p))
3926 : {
3927 : changed = true;
3928 : do_over = true;
3929 : break;
3930 : }
3931 : }
3932 : } while (do_over);
3933 2474585 : return changed;
3934 : }
3935 :
3936 : /* Return TRUE if STMT has a VUSE whose corresponding VDEF is in BB. */
3937 :
3938 : static bool
3939 11962 : local_mem_dependence (gimple *stmt, basic_block bb)
3940 : {
3941 23924 : tree vuse = gimple_vuse (stmt);
3942 11962 : gimple *def;
3943 :
3944 11962 : if (!vuse)
3945 : return false;
3946 :
3947 11962 : def = SSA_NAME_DEF_STMT (vuse);
3948 11962 : return (def && gimple_bb (def) == bb);
3949 : }
3950 :
3951 : /* Given a "diamond" control-flow pattern where BB0 tests a condition,
3952 : BB1 and BB2 are "then" and "else" blocks dependent on this test,
3953 : and BB3 rejoins control flow following BB1 and BB2, look for
3954 : opportunities to hoist loads as follows. If BB3 contains a PHI of
3955 : two loads, one each occurring in BB1 and BB2, and the loads are
3956 : provably of adjacent fields in the same structure, then move both
3957 : loads into BB0. Of course this can only be done if there are no
3958 : dependencies preventing such motion.
3959 :
3960 : One of the hoisted loads will always be speculative, so the
3961 : transformation is currently conservative:
3962 :
3963 : - The fields must be strictly adjacent.
3964 : - The two fields must occupy a single memory block that is
3965 : guaranteed to not cross a page boundary.
3966 :
3967 : The last is difficult to prove, as such memory blocks should be
3968 : aligned on the minimum of the stack alignment boundary and the
3969 : alignment guaranteed by heap allocation interfaces. Thus we rely
3970 : on a parameter for the alignment value.
3971 :
3972 : Provided a good value is used for the last case, the first
3973 : restriction could possibly be relaxed. */
3974 :
3975 : static void
3976 577977 : hoist_adjacent_loads (basic_block bb0, basic_block bb1,
3977 : basic_block bb2, basic_block bb3)
3978 : {
3979 577977 : unsigned HOST_WIDE_INT param_align = param_l1_cache_line_size;
3980 577977 : unsigned HOST_WIDE_INT param_align_bits = param_align * BITS_PER_UNIT;
3981 577977 : gphi_iterator gsi;
3982 :
3983 : /* Walk the phis in bb3 looking for an opportunity. We are looking
3984 : for phis of two SSA names, one each of which is defined in bb1 and
3985 : bb2. */
3986 1283518 : for (gsi = gsi_start_phis (bb3); !gsi_end_p (gsi); gsi_next (&gsi))
3987 : {
3988 705541 : gphi *phi_stmt = gsi.phi ();
3989 705541 : gimple *def1, *def2;
3990 705541 : tree arg1, arg2, ref1, ref2, field1, field2;
3991 705541 : tree tree_offset1, tree_offset2, tree_size2, next;
3992 705541 : unsigned HOST_WIDE_INT offset1, offset2, size2, align1;
3993 705541 : gimple_stmt_iterator gsi2;
3994 705541 : basic_block bb_for_def1, bb_for_def2;
3995 :
3996 705541 : if (gimple_phi_num_args (phi_stmt) != 2
3997 1411082 : || virtual_operand_p (gimple_phi_result (phi_stmt)))
3998 699560 : continue;
3999 :
4000 165880 : arg1 = gimple_phi_arg_def (phi_stmt, 0);
4001 165880 : arg2 = gimple_phi_arg_def (phi_stmt, 1);
4002 :
4003 196368 : if (TREE_CODE (arg1) != SSA_NAME
4004 148437 : || TREE_CODE (arg2) != SSA_NAME
4005 136252 : || SSA_NAME_IS_DEFAULT_DEF (arg1)
4006 301808 : || SSA_NAME_IS_DEFAULT_DEF (arg2))
4007 30488 : continue;
4008 :
4009 135392 : def1 = SSA_NAME_DEF_STMT (arg1);
4010 135392 : def2 = SSA_NAME_DEF_STMT (arg2);
4011 :
4012 135392 : if ((gimple_bb (def1) != bb1 || gimple_bb (def2) != bb2)
4013 148527 : && (gimple_bb (def2) != bb1 || gimple_bb (def1) != bb2))
4014 35785 : continue;
4015 :
4016 : /* Check the mode of the arguments to be sure a conditional move
4017 : can be generated for it. */
4018 199214 : if (optab_handler (movcc_optab, TYPE_MODE (TREE_TYPE (arg1)))
4019 : == CODE_FOR_nothing)
4020 5608 : continue;
4021 :
4022 : /* Both statements must be assignments whose RHS is a COMPONENT_REF. */
4023 93999 : if (!gimple_assign_single_p (def1)
4024 43987 : || !gimple_assign_single_p (def2)
4025 52384 : || gimple_has_volatile_ops (def1)
4026 146377 : || gimple_has_volatile_ops (def2))
4027 67810 : continue;
4028 :
4029 26189 : ref1 = gimple_assign_rhs1 (def1);
4030 26189 : ref2 = gimple_assign_rhs1 (def2);
4031 :
4032 26189 : if (TREE_CODE (ref1) != COMPONENT_REF
4033 15409 : || TREE_CODE (ref2) != COMPONENT_REF)
4034 10896 : continue;
4035 :
4036 : /* The zeroth operand of the two component references must be
4037 : identical. It is not sufficient to compare get_base_address of
4038 : the two references, because this could allow for different
4039 : elements of the same array in the two trees. It is not safe to
4040 : assume that the existence of one array element implies the
4041 : existence of a different one. */
4042 15293 : if (!operand_equal_p (TREE_OPERAND (ref1, 0), TREE_OPERAND (ref2, 0), 0))
4043 4585 : continue;
4044 :
4045 10708 : field1 = TREE_OPERAND (ref1, 1);
4046 10708 : field2 = TREE_OPERAND (ref2, 1);
4047 :
4048 : /* Check for field adjacency, and ensure field1 comes first. */
4049 10708 : for (next = DECL_CHAIN (field1);
4050 24759 : next && TREE_CODE (next) != FIELD_DECL;
4051 14051 : next = DECL_CHAIN (next))
4052 : ;
4053 :
4054 10708 : if (next != field2)
4055 : {
4056 7202 : for (next = DECL_CHAIN (field2);
4057 9074 : next && TREE_CODE (next) != FIELD_DECL;
4058 1872 : next = DECL_CHAIN (next))
4059 : ;
4060 :
4061 7202 : if (next != field1)
4062 4727 : continue;
4063 :
4064 : std::swap (field1, field2);
4065 : std::swap (def1, def2);
4066 : }
4067 :
4068 5981 : bb_for_def1 = gimple_bb (def1);
4069 5981 : bb_for_def2 = gimple_bb (def2);
4070 :
4071 : /* Check for proper alignment of the first field. */
4072 5981 : tree_offset1 = bit_position (field1);
4073 5981 : tree_offset2 = bit_position (field2);
4074 5981 : tree_size2 = DECL_SIZE (field2);
4075 :
4076 5981 : if (!tree_fits_uhwi_p (tree_offset1)
4077 5981 : || !tree_fits_uhwi_p (tree_offset2)
4078 5981 : || !tree_fits_uhwi_p (tree_size2))
4079 0 : continue;
4080 :
4081 5981 : offset1 = tree_to_uhwi (tree_offset1);
4082 5981 : offset2 = tree_to_uhwi (tree_offset2);
4083 5981 : size2 = tree_to_uhwi (tree_size2);
4084 5981 : align1 = DECL_ALIGN (field1) % param_align_bits;
4085 :
4086 5981 : if (offset1 % BITS_PER_UNIT != 0)
4087 0 : continue;
4088 :
4089 : /* For profitability, the two field references should fit within
4090 : a single cache line. */
4091 5981 : if (align1 + offset2 - offset1 + size2 > param_align_bits)
4092 0 : continue;
4093 :
4094 : /* The two expressions cannot be dependent upon vdefs defined
4095 : in bb1/bb2. */
4096 5981 : if (local_mem_dependence (def1, bb_for_def1)
4097 5981 : || local_mem_dependence (def2, bb_for_def2))
4098 0 : continue;
4099 :
4100 : /* The conditions are satisfied; hoist the loads from bb1 and bb2 into
4101 : bb0. We hoist the first one first so that a cache miss is handled
4102 : efficiently regardless of hardware cache-fill policy. */
4103 5981 : gsi2 = gsi_for_stmt (def1);
4104 5981 : gsi_move_to_bb_end (&gsi2, bb0);
4105 5981 : gsi2 = gsi_for_stmt (def2);
4106 5981 : gsi_move_to_bb_end (&gsi2, bb0);
4107 5981 : statistics_counter_event (cfun, "hoisted loads", 1);
4108 :
4109 5981 : if (dump_file && (dump_flags & TDF_DETAILS))
4110 : {
4111 0 : fprintf (dump_file,
4112 : "\nHoisting adjacent loads from %d and %d into %d: \n",
4113 : bb_for_def1->index, bb_for_def2->index, bb0->index);
4114 0 : print_gimple_stmt (dump_file, def1, 0, TDF_VOPS|TDF_MEMSYMS);
4115 0 : print_gimple_stmt (dump_file, def2, 0, TDF_VOPS|TDF_MEMSYMS);
4116 : }
4117 : }
4118 577977 : }
4119 :
4120 : /* Determine whether we should attempt to hoist adjacent loads out of
4121 : diamond patterns in pass_phiopt. Always hoist loads if
4122 : -fhoist-adjacent-loads is specified and the target machine has
4123 : both a conditional move instruction and a defined cache line size. */
4124 :
4125 : static bool
4126 3119060 : gate_hoist_loads (void)
4127 : {
4128 3119060 : return (flag_hoist_adjacent_loads == 1
4129 3119060 : && param_l1_cache_line_size
4130 0 : && HAVE_conditional_move);
4131 : }
4132 :
4133 : template <class func_type>
4134 : static void
4135 6559113 : execute_over_cond_phis (func_type func)
4136 : {
4137 : unsigned n, i;
4138 : basic_block *bb_order;
4139 : basic_block bb;
4140 : /* Search every basic block for COND_EXPR we may be able to optimize.
4141 :
4142 : We walk the blocks in order that guarantees that a block with
4143 : a single predecessor is processed before the predecessor.
4144 : This ensures that we collapse inner ifs before visiting the
4145 : outer ones, and also that we do not try to visit a removed
4146 : block. */
4147 6559113 : bb_order = single_pred_before_succ_order ();
4148 6559113 : n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
4149 :
4150 58681221 : for (i = 0; i < n; i++)
4151 : {
4152 : basic_block bb1, bb2;
4153 : edge e1, e2;
4154 52122108 : bool diamond_p = false;
4155 :
4156 52122108 : bb = bb_order[i];
4157 :
4158 : /* Check to see if the last statement is a GIMPLE_COND. */
4159 52122108 : gcond *cond_stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
4160 31099625 : if (!cond_stmt)
4161 52122108 : continue;
4162 :
4163 21022483 : e1 = EDGE_SUCC (bb, 0);
4164 21022483 : bb1 = e1->dest;
4165 21022483 : e2 = EDGE_SUCC (bb, 1);
4166 21022483 : bb2 = e2->dest;
4167 :
4168 : /* We cannot do the optimization on abnormal edges. */
4169 21022483 : if ((e1->flags & EDGE_ABNORMAL) != 0
4170 21022483 : || (e2->flags & EDGE_ABNORMAL) != 0)
4171 0 : continue;
4172 :
4173 : /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
4174 21022483 : if (EDGE_COUNT (bb1->succs) == 0
4175 19580687 : || EDGE_COUNT (bb2->succs) == 0)
4176 4859426 : continue;
4177 :
4178 : /* Find the bb which is the fall through to the other. */
4179 16163057 : if (EDGE_SUCC (bb1, 0)->dest == bb2)
4180 : ;
4181 13698549 : else if (EDGE_SUCC (bb2, 0)->dest == bb1)
4182 : {
4183 : std::swap (bb1, bb2);
4184 : std::swap (e1, e2);
4185 : }
4186 10434230 : else if (EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest
4187 11938244 : && single_succ_p (bb2))
4188 : {
4189 1504014 : diamond_p = true;
4190 1504014 : e2 = EDGE_SUCC (bb2, 0);
4191 : /* Make sure bb2 is just a fall through. */
4192 1504014 : if ((e2->flags & EDGE_FALLTHRU) == 0)
4193 51855 : continue;
4194 : }
4195 : else
4196 10434230 : continue;
4197 :
4198 5676972 : e1 = EDGE_SUCC (bb1, 0);
4199 :
4200 : /* Make sure that bb1 is just a fall through. */
4201 5676972 : if (!single_succ_p (bb1)
4202 5676972 : || (e1->flags & EDGE_FALLTHRU) == 0)
4203 1358091 : continue;
4204 :
4205 4318881 : func (bb, bb1, bb2, e1, e2, diamond_p, cond_stmt);
4206 : }
4207 6559113 : free (bb_order);
4208 6559113 : }
4209 :
4210 : /* This pass tries to replaces an if-then-else block with an
4211 : assignment. We have different kinds of transformations.
4212 : Some of these transformations are also performed by the ifcvt
4213 : RTL optimizer.
4214 :
4215 : PHI-OPT using Match-and-simplify infrastructure
4216 : -----------------------
4217 :
4218 : The PHI-OPT pass will try to use match-and-simplify infrastructure
4219 : (gimple_simplify) to do transformations. This is implemented in
4220 : match_simplify_replacement.
4221 :
4222 : The way it works is it replaces:
4223 : bb0:
4224 : if (cond) goto bb2; else goto bb1;
4225 : bb1:
4226 : bb2:
4227 : x = PHI <a (bb1), b (bb0), ...>;
4228 :
4229 : with a statement if it gets simplified from `cond ? b : a`.
4230 :
4231 : bb0:
4232 : x1 = cond ? b : a;
4233 : bb2:
4234 : x = PHI <a (bb1), x1 (bb0), ...>;
4235 : Bb1 might be removed as it becomes unreachable when doing the replacement.
4236 : Though bb1 does not have to be considered a forwarding basic block from bb0.
4237 :
4238 : Will try to see if `(!cond) ? a : b` gets simplified (iff !cond simplifies);
4239 : this is done not to have an explosion of patterns in match.pd.
4240 : Note bb1 does not need to be completely empty, it can contain
4241 : one statement which is known not to trap.
4242 :
4243 : It also can handle the case where we have two forwarding bbs (diamond):
4244 : bb0:
4245 : if (cond) goto bb2; else goto bb1;
4246 : bb1: goto bb3;
4247 : bb2: goto bb3;
4248 : bb3:
4249 : x = PHI <a (bb1), b (bb2), ...>;
4250 : And that is replaced with a statement if it is simplified
4251 : from `cond ? b : a`.
4252 : Again bb1 and bb2 does not have to be completely empty but
4253 : each can contain one statement which is known not to trap.
4254 : But in this case bb1/bb2 can only be forwarding basic blocks.
4255 :
4256 : This fully replaces the old "Conditional Replacement",
4257 : "ABS Replacement" and "MIN/MAX Replacement" transformations as they are now
4258 : implemented in match.pd.
4259 :
4260 : Value Replacement
4261 : -----------------
4262 :
4263 : This transformation, implemented in value_replacement, replaces
4264 :
4265 : bb0:
4266 : if (a != b) goto bb2; else goto bb1;
4267 : bb1:
4268 : bb2:
4269 : x = PHI <a (bb1), b (bb0), ...>;
4270 :
4271 : with
4272 :
4273 : bb0:
4274 : bb2:
4275 : x = PHI <b (bb0), ...>;
4276 :
4277 : This opportunity can sometimes occur as a result of other
4278 : optimizations.
4279 :
4280 :
4281 : Another case caught by value replacement looks like this:
4282 :
4283 : bb0:
4284 : t1 = a == CONST;
4285 : t2 = b > c;
4286 : t3 = t1 & t2;
4287 : if (t3 != 0) goto bb1; else goto bb2;
4288 : bb1:
4289 : bb2:
4290 : x = PHI (CONST, a)
4291 :
4292 : Gets replaced with:
4293 : bb0:
4294 : bb2:
4295 : t1 = a == CONST;
4296 : t2 = b > c;
4297 : t3 = t1 & t2;
4298 : x = a;
4299 :
4300 :
4301 : This pass also performs a fifth transformation of a slightly different
4302 : flavor.
4303 :
4304 : Factor operations in COND_EXPR
4305 : ------------------------------
4306 :
4307 : This transformation factors the unary operations out of COND_EXPR with
4308 : factor_out_conditional_operation.
4309 :
4310 : For example:
4311 : if (a <= CST) goto <bb 3>; else goto <bb 4>;
4312 : <bb 3>:
4313 : tmp = (int) a;
4314 : <bb 4>:
4315 : tmp = PHI <tmp, CST>
4316 :
4317 : Into:
4318 : if (a <= CST) goto <bb 3>; else goto <bb 4>;
4319 : <bb 3>:
4320 : <bb 4>:
4321 : a = PHI <a, CST>
4322 : tmp = (int) a;
4323 :
4324 : Adjacent Load Hoisting
4325 : ----------------------
4326 :
4327 : This transformation replaces
4328 :
4329 : bb0:
4330 : if (...) goto bb2; else goto bb1;
4331 : bb1:
4332 : x1 = (<expr>).field1;
4333 : goto bb3;
4334 : bb2:
4335 : x2 = (<expr>).field2;
4336 : bb3:
4337 : # x = PHI <x1, x2>;
4338 :
4339 : with
4340 :
4341 : bb0:
4342 : x1 = (<expr>).field1;
4343 : x2 = (<expr>).field2;
4344 : if (...) goto bb2; else goto bb1;
4345 : bb1:
4346 : goto bb3;
4347 : bb2:
4348 : bb3:
4349 : # x = PHI <x1, x2>;
4350 :
4351 : The purpose of this transformation is to enable generation of conditional
4352 : move instructions such as Intel CMOVE or PowerPC ISEL. Because one of
4353 : the loads is speculative, the transformation is restricted to very
4354 : specific cases to avoid introducing a page fault. We are looking for
4355 : the common idiom:
4356 :
4357 : if (...)
4358 : x = y->left;
4359 : else
4360 : x = y->right;
4361 :
4362 : where left and right are typically adjacent pointers in a tree structure. */
4363 :
4364 : namespace {
4365 :
4366 : const pass_data pass_data_phiopt =
4367 : {
4368 : GIMPLE_PASS, /* type */
4369 : "phiopt", /* name */
4370 : OPTGROUP_NONE, /* optinfo_flags */
4371 : TV_TREE_PHIOPT, /* tv_id */
4372 : ( PROP_cfg | PROP_ssa ), /* properties_required */
4373 : 0, /* properties_provided */
4374 : 0, /* properties_destroyed */
4375 : 0, /* todo_flags_start */
4376 : 0, /* todo_flags_finish */
4377 : };
4378 :
4379 : class pass_phiopt : public gimple_opt_pass
4380 : {
4381 : public:
4382 1195312 : pass_phiopt (gcc::context *ctxt)
4383 2390624 : : gimple_opt_pass (pass_data_phiopt, ctxt), early_p (false)
4384 : {}
4385 :
4386 : /* opt_pass methods: */
4387 896484 : opt_pass * clone () final override { return new pass_phiopt (m_ctxt); }
4388 1195312 : void set_pass_param (unsigned n, bool param) final override
4389 : {
4390 1195312 : gcc_assert (n == 0);
4391 1195312 : early_p = param;
4392 1195312 : }
4393 5522637 : bool gate (function *) final override { return flag_ssa_phiopt; }
4394 : unsigned int execute (function *) final override;
4395 :
4396 : private:
4397 : bool early_p;
4398 : }; // class pass_phiopt
4399 :
4400 : } // anon namespace
4401 :
4402 : gimple_opt_pass *
4403 298828 : make_pass_phiopt (gcc::context *ctxt)
4404 : {
4405 298828 : return new pass_phiopt (ctxt);
4406 : }
4407 :
4408 : unsigned int
4409 5519394 : pass_phiopt::execute (function *)
4410 : {
4411 5519394 : bool do_hoist_loads = !early_p ? gate_hoist_loads () : false;
4412 5519394 : bool cfgchanged = false;
4413 :
4414 5519394 : calculate_dominance_info (CDI_DOMINATORS);
4415 5519394 : mark_ssa_maybe_undefs ();
4416 :
4417 8931726 : auto phiopt_exec = [&] (basic_block bb, basic_block bb1,
4418 : basic_block bb2, edge e1, edge e2,
4419 : bool diamond_p, gcond *cond_stmt)
4420 : {
4421 3412332 : if (diamond_p)
4422 : {
4423 1075086 : basic_block bb3 = e1->dest;
4424 :
4425 1075086 : if (!single_pred_p (bb1)
4426 2095330 : || !single_pred_p (bb2))
4427 2576069 : return;
4428 :
4429 965929 : if (do_hoist_loads
4430 758945 : && !FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt)))
4431 751640 : && EDGE_COUNT (bb->succs) == 2
4432 751640 : && EDGE_COUNT (bb3->preds) == 2
4433 : /* If one edge or the other is dominant, a conditional move
4434 : is likely to perform worse than the well-predicted branch. */
4435 582313 : && !predictable_edge_p (EDGE_SUCC (bb, 0))
4436 1543906 : && !predictable_edge_p (EDGE_SUCC (bb, 1)))
4437 577977 : hoist_adjacent_loads (bb, bb1, bb2, bb3);
4438 : }
4439 :
4440 965929 : gimple_stmt_iterator gsi;
4441 :
4442 : /* Check that we're looking for nested phis. */
4443 965929 : basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest : bb2;
4444 :
4445 : /* Factor out operations from the phi if possible. */
4446 3303175 : if (EDGE_COUNT (merge->preds) == 2
4447 3303175 : && !optimize_debug && factor_out_all (e1, e2, merge, cond_stmt, diamond_p, early_p))
4448 35773 : cfgchanged = true;
4449 :
4450 3303175 : gimple_seq phis = phi_nodes (merge);
4451 :
4452 3303175 : if (gimple_seq_empty_p (phis))
4453 : return;
4454 :
4455 : /* Value replacement can work with more than one PHI
4456 : so try that first. */
4457 3288998 : if (!early_p && !diamond_p)
4458 4141302 : for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
4459 : {
4460 2410370 : gphi *phi = as_a <gphi *> (gsi_stmt (gsi));
4461 2410370 : tree arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
4462 2410370 : tree arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
4463 2410370 : if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1) == 2)
4464 : {
4465 1641 : cfgchanged = true;
4466 1641 : return;
4467 : }
4468 : }
4469 :
4470 3287357 : gphi *phi = single_non_singleton_phi_for_edges (phis, e1, e2);
4471 3287357 : if (!phi)
4472 : return;
4473 :
4474 836263 : tree arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
4475 836263 : tree arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
4476 :
4477 : /* Something is wrong if we cannot find the arguments in the PHI
4478 : node. */
4479 836263 : gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
4480 :
4481 :
4482 : /* Do the replacement of conditional if it can be done. */
4483 836263 : if (match_simplify_replacement (bb, bb1, bb2, e1, e2, phi,
4484 836263 : arg0, arg1, early_p, diamond_p))
4485 92554 : cfgchanged = true;
4486 743709 : else if (!early_p
4487 494781 : && !diamond_p
4488 463431 : && single_pred_p (bb1)
4489 1189107 : && cond_removal_in_builtin_zero_pattern (bb, bb1, e1, e2,
4490 : phi, arg0, arg1))
4491 13 : cfgchanged = true;
4492 1579959 : else if (single_pred_p (bb1)
4493 697282 : && !diamond_p
4494 1382450 : && spaceship_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
4495 2228 : cfgchanged = true;
4496 5519394 : };
4497 :
4498 5519394 : execute_over_cond_phis (phiopt_exec);
4499 :
4500 5519394 : if (cfgchanged)
4501 87140 : return TODO_cleanup_cfg;
4502 : return 0;
4503 : }
4504 :
4505 : /* This pass tries to transform conditional stores into unconditional
4506 : ones, enabling further simplifications with the simpler then and else
4507 : blocks. In particular it replaces this:
4508 :
4509 : bb0:
4510 : if (cond) goto bb2; else goto bb1;
4511 : bb1:
4512 : *p = RHS;
4513 : bb2:
4514 :
4515 : with
4516 :
4517 : bb0:
4518 : if (cond) goto bb1; else goto bb2;
4519 : bb1:
4520 : condtmp' = *p;
4521 : bb2:
4522 : condtmp = PHI <RHS, condtmp'>
4523 : *p = condtmp;
4524 :
4525 : This transformation can only be done under several constraints,
4526 : documented below. It also replaces:
4527 :
4528 : bb0:
4529 : if (cond) goto bb2; else goto bb1;
4530 : bb1:
4531 : *p = RHS1;
4532 : goto bb3;
4533 : bb2:
4534 : *p = RHS2;
4535 : bb3:
4536 :
4537 : with
4538 :
4539 : bb0:
4540 : if (cond) goto bb3; else goto bb1;
4541 : bb1:
4542 : bb3:
4543 : condtmp = PHI <RHS1, RHS2>
4544 : *p = condtmp; */
4545 :
4546 : namespace {
4547 :
4548 : const pass_data pass_data_cselim =
4549 : {
4550 : GIMPLE_PASS, /* type */
4551 : "cselim", /* name */
4552 : OPTGROUP_NONE, /* optinfo_flags */
4553 : TV_TREE_PHIOPT, /* tv_id */
4554 : ( PROP_cfg | PROP_ssa ), /* properties_required */
4555 : 0, /* properties_provided */
4556 : 0, /* properties_destroyed */
4557 : 0, /* todo_flags_start */
4558 : 0, /* todo_flags_finish */
4559 : };
4560 :
4561 : class pass_cselim : public gimple_opt_pass
4562 : {
4563 : public:
4564 298828 : pass_cselim (gcc::context *ctxt)
4565 597656 : : gimple_opt_pass (pass_data_cselim, ctxt)
4566 : {}
4567 :
4568 : /* opt_pass methods: */
4569 1039819 : bool gate (function *) final override { return flag_tree_cselim; }
4570 : unsigned int execute (function *) final override;
4571 :
4572 : }; // class pass_cselim
4573 :
4574 : } // anon namespace
4575 :
4576 : gimple_opt_pass *
4577 298828 : make_pass_cselim (gcc::context *ctxt)
4578 : {
4579 298828 : return new pass_cselim (ctxt);
4580 : }
4581 :
4582 : unsigned int
4583 1039719 : pass_cselim::execute (function *)
4584 : {
4585 1039719 : bool cfgchanged = false;
4586 1039719 : hash_set<tree> *nontrap = 0;
4587 1039719 : unsigned todo = 0;
4588 :
4589 : /* ??? We are not interested in loop related info, but the following
4590 : will create it, ICEing as we didn't init loops with pre-headers.
4591 : An interfacing issue of find_data_references_in_bb. */
4592 1039719 : loop_optimizer_init (LOOPS_NORMAL);
4593 1039719 : scev_initialize ();
4594 :
4595 1039719 : calculate_dominance_info (CDI_DOMINATORS);
4596 :
4597 : /* Calculate the set of non-trapping memory accesses. */
4598 1039719 : nontrap = get_non_trapping ();
4599 :
4600 1946268 : auto cselim_exec = [&] (basic_block bb, basic_block bb1,
4601 : basic_block bb2, edge e1, edge e2,
4602 : bool diamond_p, gcond *)
4603 : {
4604 906549 : if (diamond_p)
4605 : {
4606 311569 : basic_block bb3 = e1->dest;
4607 :
4608 : /* Only handle sinking of store from 2 bbs only,
4609 : The middle bbs don't need to come from the
4610 : if always since we are sinking rather than
4611 : hoisting. */
4612 311569 : if (EDGE_COUNT (bb3->preds) != 2)
4613 : return;
4614 230601 : if (cond_if_else_store_replacement (bb1, bb2, bb3))
4615 992 : cfgchanged = true;
4616 230601 : return;
4617 : }
4618 :
4619 : /* Also make sure that bb1 only have one predecessor and that it
4620 : is bb. */
4621 594980 : if (!single_pred_p (bb1)
4622 1145257 : || single_pred (bb1) != bb)
4623 : return;
4624 :
4625 : /* bb1 is the middle block, bb2 the join block, bb the split block,
4626 : e1 the fallthrough edge from bb1 to bb2. We can't do the
4627 : optimization if the join block has more than two predecessors. */
4628 550277 : if (EDGE_COUNT (bb2->preds) > 2)
4629 : return;
4630 :
4631 428588 : gimple *assign = cselim_candidate (bb1, bb2, e1);
4632 428588 : if (cond_store_replacement (bb1, bb2, e1, e2, assign, nontrap))
4633 6642 : cfgchanged = true;
4634 1039719 : };
4635 :
4636 1039719 : execute_over_cond_phis (cselim_exec);
4637 :
4638 2079438 : delete nontrap;
4639 : /* If the CFG has changed, we should cleanup the CFG. */
4640 1039719 : if (cfgchanged)
4641 : {
4642 : /* In cond-store replacement we have added some loads on edges
4643 : and new VOPS (as we moved the store, and created a load). */
4644 4403 : gsi_commit_edge_inserts ();
4645 4403 : todo = TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
4646 : }
4647 1039719 : scev_finalize ();
4648 1039719 : loop_optimizer_finalize ();
4649 1039719 : return todo;
4650 : }
|
