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 "gimplify.h"
39 : #include "gimple-iterator.h"
40 : #include "gimplify-me.h"
41 : #include "tree-cfg.h"
42 : #include "tree-dfa.h"
43 : #include "domwalk.h"
44 : #include "cfgloop.h"
45 : #include "tree-data-ref.h"
46 : #include "tree-scalar-evolution.h"
47 : #include "tree-inline.h"
48 : #include "case-cfn-macros.h"
49 : #include "tree-eh.h"
50 : #include "gimple-fold.h"
51 : #include "internal-fn.h"
52 : #include "gimple-range.h"
53 : #include "gimple-match.h"
54 : #include "dbgcnt.h"
55 : #include "tree-ssa-propagate.h"
56 : #include "tree-ssa-dce.h"
57 : #include "tree-ssa-loop-niter.h"
58 : #include "gimple-predict.h"
59 :
60 : /* Return the singleton PHI in the SEQ of PHIs for edges E0 and E1. */
61 :
62 : static gphi *
63 3472053 : single_non_singleton_phi_for_edges (gimple_seq seq, edge e0, edge e1)
64 : {
65 3472053 : gimple_stmt_iterator i;
66 3472053 : gphi *phi = NULL;
67 5159673 : for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
68 : {
69 4231377 : gphi *p = as_a <gphi *> (gsi_stmt (i));
70 : /* If the PHI arguments are equal then we can skip this PHI. */
71 4231377 : if (operand_equal_for_phi_arg_p (gimple_phi_arg_def (p, e0->dest_idx),
72 4231377 : gimple_phi_arg_def (p, e1->dest_idx)))
73 257433 : continue;
74 :
75 : /* Punt on virtual phis with different arguments from the edges. */
76 7947888 : if (virtual_operand_p (gimple_phi_result (p)))
77 : return NULL;
78 :
79 : /* If we already have a PHI that has the two edge arguments are
80 : different, then return it is not a singleton for these PHIs. */
81 1696961 : if (phi)
82 : return NULL;
83 :
84 : phi = p;
85 : }
86 : return phi;
87 : }
88 :
89 : /* Replace PHI node element whose edge is E in block BB with variable NEW.
90 : Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
91 : is known to have two edges, one of which must reach BB). */
92 :
93 : static void
94 89333 : replace_phi_edge_with_variable (basic_block cond_block,
95 : edge e, gphi *phi, tree new_tree,
96 : bitmap dce_ssa_names = nullptr)
97 : {
98 89333 : basic_block bb = gimple_bb (phi);
99 89333 : gimple_stmt_iterator gsi;
100 89333 : tree phi_result = gimple_phi_result (phi);
101 89333 : bool deleteboth = false;
102 :
103 : /* Duplicate range info if they are the only things setting the target PHI.
104 : This is needed as later on, the new_tree will be replacing
105 : The assignement of the PHI.
106 : For an example:
107 : bb1:
108 : _4 = min<a_1, 255>
109 : goto bb2
110 :
111 : # RANGE [-INF, 255]
112 : a_3 = PHI<_4(1)>
113 : bb3:
114 :
115 : use(a_3)
116 : And _4 gets propagated into the use of a_3 and losing the range info.
117 : This can't be done for more than 2 incoming edges as the propagation
118 : won't happen.
119 : The new_tree needs to be defined in the same basic block as the conditional. */
120 89333 : if (TREE_CODE (new_tree) == SSA_NAME
121 89309 : && EDGE_COUNT (gimple_bb (phi)->preds) == 2
122 59304 : && INTEGRAL_TYPE_P (TREE_TYPE (phi_result))
123 54443 : && !SSA_NAME_RANGE_INFO (new_tree)
124 54361 : && SSA_NAME_RANGE_INFO (phi_result)
125 32961 : && gimple_bb (SSA_NAME_DEF_STMT (new_tree)) == cond_block
126 122294 : && dbg_cnt (phiopt_edge_range))
127 32961 : duplicate_ssa_name_range_info (new_tree, phi_result);
128 :
129 : /* Change the PHI argument to new. */
130 89333 : SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);
131 :
132 : /* Remove the empty basic block. */
133 89333 : edge edge_to_remove = NULL, keep_edge = NULL;
134 89333 : if (EDGE_SUCC (cond_block, 0)->dest == bb)
135 : {
136 36296 : edge_to_remove = EDGE_SUCC (cond_block, 1);
137 36296 : keep_edge = EDGE_SUCC (cond_block, 0);
138 : }
139 53037 : else if (EDGE_SUCC (cond_block, 1)->dest == bb)
140 : {
141 : edge_to_remove = EDGE_SUCC (cond_block, 0);
142 : keep_edge = EDGE_SUCC (cond_block, 1);
143 : }
144 743 : else if ((keep_edge = find_edge (cond_block, e->src)))
145 : {
146 743 : basic_block bb1 = EDGE_SUCC (cond_block, 0)->dest;
147 743 : basic_block bb2 = EDGE_SUCC (cond_block, 1)->dest;
148 1486 : if (single_pred_p (bb1) && single_pred_p (bb2)
149 90819 : && single_succ_p (bb1) && single_succ_p (bb2)
150 1486 : && empty_block_p (bb1) && empty_block_p (bb2))
151 : deleteboth = true;
152 : }
153 : else
154 0 : gcc_unreachable ();
155 :
156 : /* If we are removing the cond on a loop exit,
157 : reset number of iteration information of the loop. */
158 89333 : if (loop_exits_from_bb_p (cond_block->loop_father, cond_block))
159 : {
160 1 : auto loop = cond_block->loop_father;
161 1 : free_numbers_of_iterations_estimates (loop);
162 1 : loop->any_upper_bound = false;
163 1 : loop->any_likely_upper_bound = false;
164 : }
165 :
166 89333 : if (edge_to_remove && EDGE_COUNT (edge_to_remove->dest->preds) == 1)
167 : {
168 77873 : e->flags |= EDGE_FALLTHRU;
169 77873 : e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
170 77873 : e->probability = profile_probability::always ();
171 77873 : delete_basic_block (edge_to_remove->dest);
172 :
173 : /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
174 77873 : gsi = gsi_last_bb (cond_block);
175 77873 : gsi_remove (&gsi, true);
176 : }
177 11460 : else if (deleteboth)
178 : {
179 743 : basic_block bb1 = EDGE_SUCC (cond_block, 0)->dest;
180 743 : basic_block bb2 = EDGE_SUCC (cond_block, 1)->dest;
181 :
182 743 : edge newedge = redirect_edge_and_branch (keep_edge, bb);
183 :
184 : /* The new edge should be the same. */
185 743 : gcc_assert (newedge == keep_edge);
186 :
187 743 : keep_edge->flags |= EDGE_FALLTHRU;
188 743 : keep_edge->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
189 743 : keep_edge->probability = profile_probability::always ();
190 :
191 : /* Copy the edge's phi entry from the old one. */
192 743 : copy_phi_arg_into_existing_phi (e, keep_edge);
193 :
194 : /* Delete the old 2 empty basic blocks */
195 743 : delete_basic_block (bb1);
196 743 : delete_basic_block (bb2);
197 :
198 : /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
199 743 : gsi = gsi_last_bb (cond_block);
200 743 : gsi_remove (&gsi, true);
201 : }
202 : else
203 : {
204 : /* If there are other edges into the middle block make
205 : CFG cleanup deal with the edge removal to avoid
206 : updating dominators here in a non-trivial way. */
207 21434 : gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_block));
208 10717 : if (keep_edge->flags & EDGE_FALSE_VALUE)
209 7476 : gimple_cond_make_false (cond);
210 3241 : else if (keep_edge->flags & EDGE_TRUE_VALUE)
211 3241 : gimple_cond_make_true (cond);
212 : }
213 :
214 89333 : if (dce_ssa_names)
215 87377 : simple_dce_from_worklist (dce_ssa_names);
216 :
217 89333 : statistics_counter_event (cfun, "Replace PHI with variable", 1);
218 :
219 89333 : if (dump_file && (dump_flags & TDF_DETAILS))
220 16 : fprintf (dump_file,
221 : "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
222 : cond_block->index,
223 : bb->index);
224 89333 : }
225 :
226 : /* Returns true if the ARG used from DEF_STMT is profitable to move
227 : to a PHI node of the basic block MERGE where the new statement
228 : will be located. */
229 : static bool
230 101357 : is_factor_profitable (gimple *def_stmt, basic_block merge, tree arg)
231 : {
232 : /* The defining statement should be conditional. */
233 101357 : if (dominated_by_p (CDI_DOMINATORS, merge,
234 101357 : gimple_bb (def_stmt)))
235 : return false;
236 :
237 : /* If the arg is invariant, then there is
238 : no extending of the live range. */
239 99323 : if (is_gimple_min_invariant (arg))
240 : return true;
241 :
242 : /* Otherwise, the arg needs to be a ssa name. */
243 95132 : if (TREE_CODE (arg) != SSA_NAME)
244 : return false;
245 :
246 : /* We should not increase the live range of arg
247 : across too many statements or calls. */
248 95132 : gimple_stmt_iterator gsi = gsi_for_stmt (def_stmt);
249 95132 : gsi_next_nondebug (&gsi);
250 :
251 : /* Skip past nops and predicates. */
252 190896 : while (!gsi_end_p (gsi)
253 95764 : && (gimple_code (gsi_stmt (gsi)) == GIMPLE_NOP
254 11573 : || gimple_code (gsi_stmt (gsi)) == GIMPLE_PREDICT))
255 632 : gsi_next_nondebug (&gsi);
256 :
257 : /* If the defining statement is at the end of the bb, then it is
258 : always profitable to be to move. */
259 95132 : if (gsi_end_p (gsi))
260 : return true;
261 :
262 : /* Check if the uses of arg is dominated by merge block, this is a quick and
263 : rough estimate if arg is still alive at the merge bb. */
264 : /* FIXME: extend to a more complete live range detection. */
265 10941 : use_operand_p use_p;
266 10941 : imm_use_iterator iter;
267 37026 : FOR_EACH_IMM_USE_FAST (use_p, iter, arg)
268 : {
269 17320 : gimple *use_stmt = USE_STMT (use_p);
270 17320 : basic_block use_bb = gimple_bb (use_stmt);
271 17320 : if (dominated_by_p (CDI_DOMINATORS, merge, use_bb))
272 2176 : return true;
273 2176 : }
274 :
275 : /* If there are a few (non-call/asm) statements between
276 : the old defining statement and end of the bb, then
277 : the live range of new arg does not increase enough. */
278 8765 : int max_statements = param_phiopt_factor_max_stmts_live;
279 :
280 24450 : while (!gsi_end_p (gsi))
281 : {
282 17017 : gimple *stmt = gsi_stmt (gsi);
283 17017 : auto gcode = gimple_code (stmt);
284 : /* Skip over NOPs and predicts. */
285 17017 : if (gcode == GIMPLE_NOP
286 17017 : || gcode == GIMPLE_PREDICT)
287 : {
288 0 : gsi_next_nondebug (&gsi);
289 0 : continue;
290 : }
291 : /* Non-assigns will extend the live range too much. */
292 17017 : if (gcode != GIMPLE_ASSIGN)
293 : return false;
294 16804 : max_statements --;
295 16804 : if (max_statements == 0)
296 : return false;
297 15685 : gsi_next_nondebug (&gsi);
298 : }
299 : return true;
300 : }
301 :
302 : /* PR66726: Factor operations out of COND_EXPR. If the arguments of the PHI
303 : stmt are Unary operator, factor out the operation and perform the operation
304 : to the result of PHI stmt. COND_STMT is the controlling predicate.
305 : Return true if the operation was factored out; false otherwise. */
306 :
307 : static bool
308 2997734 : factor_out_conditional_operation (edge e0, edge e1, basic_block merge,
309 : gphi *phi, gimple *cond_stmt)
310 : {
311 2997734 : gimple *arg0_def_stmt = NULL, *arg1_def_stmt = NULL;
312 2997734 : tree temp, result;
313 2997734 : gphi *newphi;
314 2997734 : gimple_stmt_iterator gsi, gsi_for_def;
315 2997734 : location_t locus = gimple_location (phi);
316 2997734 : gimple_match_op arg0_op, arg1_op;
317 :
318 : /* We should only get here if the phi had two arguments. */
319 2997734 : gcc_assert (gimple_phi_num_args (phi) == 2);
320 :
321 : /* Virtual operands are never handled. */
322 5995468 : if (virtual_operand_p (gimple_phi_result (phi)))
323 : return false;
324 :
325 1299661 : tree arg0 = gimple_phi_arg_def (phi, e0->dest_idx);
326 1299661 : tree arg1 = gimple_phi_arg_def (phi, e1->dest_idx);
327 1299661 : location_t narg0_loc = gimple_location (phi);
328 1299661 : location_t narg1_loc = gimple_location (phi);
329 1299661 : if (gimple_phi_arg_location (phi, e0->dest_idx) != UNKNOWN_LOCATION)
330 1104652 : narg0_loc = gimple_phi_arg_location (phi, e0->dest_idx);
331 1299661 : if (gimple_phi_arg_location (phi, e1->dest_idx) != UNKNOWN_LOCATION)
332 927654 : narg1_loc = gimple_phi_arg_location (phi, e1->dest_idx);
333 :
334 1299661 : gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
335 :
336 : /* Arugments that are the same don't have anything to be
337 : done to them. */
338 1299661 : if (operand_equal_for_phi_arg_p (arg0, arg1))
339 : return false;
340 :
341 : /* First canonicalize to simplify tests. */
342 1297989 : if (TREE_CODE (arg0) != SSA_NAME)
343 : {
344 248078 : std::swap (arg0, arg1);
345 248078 : std::swap (e0, e1);
346 : }
347 :
348 1297989 : if (TREE_CODE (arg0) != SSA_NAME
349 1178730 : || (TREE_CODE (arg1) != SSA_NAME
350 499491 : && TREE_CODE (arg1) != INTEGER_CST))
351 : return false;
352 :
353 : /* Check if arg0 is an SSA_NAME and the stmt which defines arg0 is
354 : an unary operation. */
355 1146475 : arg0_def_stmt = SSA_NAME_DEF_STMT (arg0);
356 1146475 : if (!gimple_extract_op (arg0_def_stmt, &arg0_op))
357 : return false;
358 :
359 : /* Check to make sure none of the operands are in abnormal phis. */
360 578860 : if (arg0_op.operands_occurs_in_abnormal_phi ())
361 : return false;
362 :
363 : /* Currently just support one operand expressions. */
364 578860 : if (arg0_op.num_ops != 1)
365 : return false;
366 :
367 118208 : tree new_arg0 = arg0_op.ops[0];
368 118208 : tree new_arg1;
369 :
370 : /* If arg0 have > 1 use, then this transformation actually increases
371 : the number of expressions evaluated at runtime. */
372 118208 : if (!has_single_use (arg0))
373 : return false;
374 96692 : if (!is_factor_profitable (arg0_def_stmt, merge, new_arg0))
375 : return false;
376 93835 : if (gimple_has_location (arg0_def_stmt))
377 91523 : narg0_loc = gimple_location (arg0_def_stmt);
378 :
379 93835 : if (TREE_CODE (arg1) == SSA_NAME)
380 : {
381 : /* Check if arg1 is an SSA_NAME. */
382 47271 : arg1_def_stmt = SSA_NAME_DEF_STMT (arg1);
383 47271 : if (!gimple_extract_op (arg1_def_stmt, &arg1_op))
384 : return false;
385 31572 : if (arg1_op.code != arg0_op.code)
386 : return false;
387 7502 : if (arg1_op.num_ops != arg0_op.num_ops)
388 : return false;
389 7502 : if (arg1_op.operands_occurs_in_abnormal_phi ())
390 : return false;
391 :
392 : /* If arg1 have > 1 use, then this transformation actually increases
393 : the number of expressions evaluated at runtime. */
394 7502 : if (!has_single_use (arg1))
395 : return false;
396 :
397 4665 : new_arg1 = arg1_op.ops[0];
398 4665 : if (!is_factor_profitable (arg1_def_stmt, merge, new_arg1))
399 : return false;
400 4156 : if (gimple_has_location (arg1_def_stmt))
401 4059 : narg1_loc = gimple_location (arg1_def_stmt);
402 :
403 : /* Chose the location for the new statement if the phi location is unknown. */
404 4156 : if (locus == UNKNOWN_LOCATION)
405 : {
406 4156 : if (narg0_loc == UNKNOWN_LOCATION
407 4156 : && narg1_loc != UNKNOWN_LOCATION)
408 : locus = narg1_loc;
409 4156 : else if (narg0_loc != UNKNOWN_LOCATION
410 4156 : && narg1_loc == UNKNOWN_LOCATION)
411 46 : locus = narg0_loc;
412 : }
413 : }
414 : else
415 : {
416 : /* For constants only handle if the phi was the only one. */
417 46564 : if (single_non_singleton_phi_for_edges (phi_nodes (merge), e0, e1) == NULL)
418 : return false;
419 : /* TODO: handle more than just casts here. */
420 34899 : if (!gimple_assign_cast_p (arg0_def_stmt))
421 : return false;
422 :
423 : /* arg0_def_stmt should be conditional. */
424 28380 : if (dominated_by_p (CDI_DOMINATORS, gimple_bb (phi), gimple_bb (arg0_def_stmt)))
425 : return false;
426 :
427 : /* If arg1 is an INTEGER_CST, fold it to new type if it fits, or else
428 : if the bits will not be modified during the conversion, except for
429 : boolean types whose precision is not 1 (see int_fits_type_p). */
430 56750 : if (!INTEGRAL_TYPE_P (TREE_TYPE (new_arg0))
431 56490 : || !(int_fits_type_p (arg1, TREE_TYPE (new_arg0))
432 1683 : || (TYPE_PRECISION (TREE_TYPE (new_arg0))
433 1683 : == TYPE_PRECISION (TREE_TYPE (arg1))
434 1112 : && (TREE_CODE (TREE_TYPE (new_arg0)) != BOOLEAN_TYPE
435 0 : || TYPE_PRECISION (TREE_TYPE (new_arg0)) == 1))))
436 : return false;
437 :
438 : /* For the INTEGER_CST case, we are just moving the
439 : conversion from one place to another, which can often
440 : hurt as the conversion moves further away from the
441 : statement that computes the value. So, perform this
442 : only if new_arg0 is an operand of COND_STMT, or
443 : if arg0_def_stmt is the only non-debug stmt in
444 : its basic block, because then it is possible this
445 : could enable further optimizations (minmax replacement
446 : etc.). See PR71016.
447 : Note no-op conversions don't have this issue as
448 : it will not generate any zero/sign extend in that case. */
449 27549 : if ((TYPE_PRECISION (TREE_TYPE (new_arg0))
450 27549 : != TYPE_PRECISION (TREE_TYPE (arg1)))
451 12182 : && new_arg0 != gimple_cond_lhs (cond_stmt)
452 11464 : && new_arg0 != gimple_cond_rhs (cond_stmt)
453 39007 : && gimple_bb (arg0_def_stmt) == e0->src)
454 : {
455 11458 : gsi = gsi_for_stmt (arg0_def_stmt);
456 11458 : gsi_prev_nondebug (&gsi);
457 : /* Ignore nops, predicates and labels. */
458 22936 : while (!gsi_end_p (gsi)
459 11478 : && (gimple_code (gsi_stmt (gsi)) == GIMPLE_NOP
460 : || gimple_code (gsi_stmt (gsi)) == GIMPLE_PREDICT
461 : || gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL))
462 20 : gsi_prev_nondebug (&gsi);
463 :
464 11458 : if (!gsi_end_p (gsi))
465 : {
466 8093 : gimple *stmt = gsi_stmt (gsi);
467 2982272 : if (gassign *assign = dyn_cast <gassign *> (stmt))
468 : {
469 7694 : tree lhs = gimple_assign_lhs (assign);
470 7694 : tree lhst = TREE_TYPE (lhs);
471 7694 : enum tree_code ass_code
472 7694 : = gimple_assign_rhs_code (assign);
473 7694 : if (ass_code != MAX_EXPR && ass_code != MIN_EXPR
474 : /* Conversions from boolean like types is ok
475 : as `a?1:b` and `a?0:b` will always simplify
476 : to `a & b` or `a | b`.
477 : See PR 116890. */
478 7694 : && !(INTEGRAL_TYPE_P (lhst)
479 7269 : && TYPE_UNSIGNED (lhst)
480 5131 : && TYPE_PRECISION (lhst) == 1))
481 : return false;
482 4445 : if (lhs != gimple_assign_rhs1 (arg0_def_stmt))
483 : return false;
484 4403 : gsi_prev_nondebug (&gsi);
485 4403 : if (!gsi_end_p (gsi))
486 : return false;
487 : }
488 : else
489 : return false;
490 : }
491 : }
492 19759 : new_arg1 = fold_convert (TREE_TYPE (new_arg0), arg1);
493 :
494 : /* Drop the overlow that fold_convert might add. */
495 19759 : if (TREE_OVERFLOW (new_arg1))
496 0 : new_arg1 = drop_tree_overflow (new_arg1);
497 :
498 : /* The locus of the new statement is arg0 defining statement. */
499 19759 : if (gimple_has_location (arg0_def_stmt))
500 19336 : locus = gimple_location (arg0_def_stmt);
501 : }
502 :
503 : /* If types of new_arg0 and new_arg1 are different bailout. */
504 23915 : if (!types_compatible_p (TREE_TYPE (new_arg0), TREE_TYPE (new_arg1)))
505 : return false;
506 :
507 : /* Create a new PHI stmt. */
508 23289 : result = gimple_phi_result (phi);
509 23289 : temp = make_ssa_name (TREE_TYPE (new_arg0), NULL);
510 :
511 23289 : gimple_match_op new_op = arg0_op;
512 :
513 : /* Create the operation stmt if possible and insert it. */
514 23289 : new_op.ops[0] = temp;
515 23289 : gimple_seq seq = NULL;
516 23289 : result = maybe_push_res_to_seq (&new_op, &seq, result);
517 :
518 : /* If we can't create the new statement, release the temp name
519 : and return back. */
520 23289 : if (!result)
521 : {
522 133 : release_ssa_name (temp);
523 133 : return false;
524 : }
525 :
526 23156 : if (locus != UNKNOWN_LOCATION)
527 19378 : annotate_all_with_location (seq, locus);
528 23156 : gsi = gsi_after_labels (gimple_bb (phi));
529 23156 : gsi_insert_seq_before (&gsi, seq, GSI_CONTINUE_LINKING);
530 :
531 23156 : newphi = create_phi_node (temp, gimple_bb (phi));
532 :
533 23156 : if (dump_file && (dump_flags & TDF_DETAILS))
534 : {
535 14 : fprintf (dump_file, "PHI ");
536 14 : print_generic_expr (dump_file, gimple_phi_result (phi));
537 14 : fprintf (dump_file,
538 : " changed to factor operation out from COND_EXPR.\n");
539 14 : fprintf (dump_file, "New stmt with OPERATION that defines ");
540 14 : print_generic_expr (dump_file, result);
541 14 : fprintf (dump_file, ".\n");
542 : }
543 :
544 : /* Remove the old operation(s) that has single use. */
545 23156 : gsi_for_def = gsi_for_stmt (arg0_def_stmt);
546 23156 : gsi_remove (&gsi_for_def, true);
547 23156 : release_defs (arg0_def_stmt);
548 :
549 23156 : if (arg1_def_stmt)
550 : {
551 3397 : gsi_for_def = gsi_for_stmt (arg1_def_stmt);
552 3397 : gsi_remove (&gsi_for_def, true);
553 3397 : release_defs (arg1_def_stmt);
554 : }
555 :
556 23156 : add_phi_arg (newphi, new_arg0, e0, narg0_loc);
557 23156 : add_phi_arg (newphi, new_arg1, e1, narg1_loc);
558 :
559 : /* Remove the original PHI stmt. */
560 23156 : gsi = gsi_for_stmt (phi);
561 23156 : gsi_remove (&gsi, true);
562 :
563 23156 : statistics_counter_event (cfun, "factored out operation", 1);
564 :
565 23156 : return true;
566 : }
567 :
568 :
569 : /* Return TRUE if SEQ/OP pair should be allowed during early phiopt.
570 : Currently this is to allow MIN/MAX and ABS/NEGATE and constants. */
571 : static bool
572 168030 : phiopt_early_allow (gimple_seq &seq, gimple_match_op &op)
573 : {
574 : /* Don't allow functions. */
575 168030 : if (!op.code.is_tree_code ())
576 : return false;
577 167981 : tree_code code = (tree_code)op.code;
578 :
579 : /* For non-empty sequence, only allow one statement
580 : a MIN/MAX and an original MIN/MAX. */
581 167981 : if (!gimple_seq_empty_p (seq))
582 : {
583 139462 : if (code == MIN_EXPR || code == MAX_EXPR)
584 : {
585 143794 : if (!gimple_seq_singleton_p (seq))
586 : return false;
587 :
588 11 : gimple *stmt = gimple_seq_first_stmt (seq);
589 : /* Only allow assignments. */
590 11 : if (!is_gimple_assign (stmt))
591 : return false;
592 11 : code = gimple_assign_rhs_code (stmt);
593 11 : return code == MIN_EXPR || code == MAX_EXPR;
594 : }
595 : return false;
596 : }
597 :
598 28519 : switch (code)
599 : {
600 : case MIN_EXPR:
601 : case MAX_EXPR:
602 : case ABS_EXPR:
603 : case ABSU_EXPR:
604 : case NEGATE_EXPR:
605 : case SSA_NAME:
606 : return true;
607 : case INTEGER_CST:
608 : case REAL_CST:
609 : case VECTOR_CST:
610 : case FIXED_CST:
611 : return true;
612 : default:
613 : return false;
614 : }
615 : }
616 :
617 : /* gimple_simplify_phiopt is like gimple_simplify but designed for PHIOPT.
618 : Return NULL if nothing can be simplified or the resulting simplified value
619 : with parts pushed if EARLY_P was true. Also rejects non allowed tree code
620 : if EARLY_P is set.
621 : Takes the comparison from COMP_STMT and two args, ARG0 and ARG1 and tries
622 : to simplify CMP ? ARG0 : ARG1.
623 : Also try to simplify (!CMP) ? ARG1 : ARG0 if the non-inverse failed. */
624 : static tree
625 514290 : gimple_simplify_phiopt (bool early_p, tree type, gimple *comp_stmt,
626 : tree arg0, tree arg1,
627 : gimple_seq *seq)
628 : {
629 514290 : gimple_seq seq1 = NULL;
630 514290 : enum tree_code comp_code = gimple_cond_code (comp_stmt);
631 514290 : location_t loc = gimple_location (comp_stmt);
632 514290 : tree cmp0 = gimple_cond_lhs (comp_stmt);
633 514290 : tree cmp1 = gimple_cond_rhs (comp_stmt);
634 : /* To handle special cases like floating point comparison, it is easier and
635 : less error-prone to build a tree and gimplify it on the fly though it is
636 : less efficient.
637 : Don't use fold_build2 here as that might create (bool)a instead of just
638 : "a != 0". */
639 514290 : tree cond = build2_loc (loc, comp_code, boolean_type_node,
640 : cmp0, cmp1);
641 :
642 514290 : if (dump_file && (dump_flags & TDF_FOLDING))
643 : {
644 1 : fprintf (dump_file, "\nphiopt match-simplify trying:\n\t");
645 1 : print_generic_expr (dump_file, cond);
646 1 : fprintf (dump_file, " ? ");
647 1 : print_generic_expr (dump_file, arg0);
648 1 : fprintf (dump_file, " : ");
649 1 : print_generic_expr (dump_file, arg1);
650 1 : fprintf (dump_file, "\n");
651 : }
652 :
653 514290 : gimple_match_op op (gimple_match_cond::UNCOND,
654 514290 : COND_EXPR, type, cond, arg0, arg1);
655 :
656 514290 : if (op.resimplify (&seq1, follow_all_ssa_edges))
657 : {
658 153059 : bool allowed = !early_p || phiopt_early_allow (seq1, op);
659 153059 : tree result = maybe_push_res_to_seq (&op, &seq1);
660 153059 : if (dump_file && (dump_flags & TDF_FOLDING))
661 : {
662 1 : fprintf (dump_file, "\nphiopt match-simplify back:\n");
663 1 : if (seq1)
664 0 : print_gimple_seq (dump_file, seq1, 0, TDF_VOPS|TDF_MEMSYMS);
665 1 : fprintf (dump_file, "result: ");
666 1 : if (result)
667 1 : print_generic_expr (dump_file, result);
668 : else
669 0 : fprintf (dump_file, " (none)");
670 1 : fprintf (dump_file, "\n");
671 1 : if (!allowed)
672 0 : fprintf (dump_file, "rejected because early\n");
673 : }
674 : /* Early we want only to allow some generated tree codes. */
675 153059 : if (allowed && result)
676 : {
677 80208 : if (loc != UNKNOWN_LOCATION)
678 79742 : annotate_all_with_location (seq1, loc);
679 80208 : gimple_seq_add_seq_without_update (seq, seq1);
680 80208 : return result;
681 : }
682 : }
683 434082 : gimple_seq_discard (seq1);
684 434082 : seq1 = NULL;
685 :
686 : /* Try the inverted comparison, that is !COMP ? ARG1 : ARG0. */
687 434082 : comp_code = invert_tree_comparison (comp_code, HONOR_NANS (cmp0));
688 :
689 434082 : if (comp_code == ERROR_MARK)
690 : return NULL;
691 :
692 420345 : cond = build2_loc (loc,
693 : comp_code, boolean_type_node,
694 : cmp0, cmp1);
695 :
696 420345 : if (dump_file && (dump_flags & TDF_FOLDING))
697 : {
698 0 : fprintf (dump_file, "\nphiopt match-simplify trying:\n\t");
699 0 : print_generic_expr (dump_file, cond);
700 0 : fprintf (dump_file, " ? ");
701 0 : print_generic_expr (dump_file, arg1);
702 0 : fprintf (dump_file, " : ");
703 0 : print_generic_expr (dump_file, arg0);
704 0 : fprintf (dump_file, "\n");
705 : }
706 :
707 420345 : gimple_match_op op1 (gimple_match_cond::UNCOND,
708 420345 : COND_EXPR, type, cond, arg1, arg0);
709 :
710 420345 : if (op1.resimplify (&seq1, follow_all_ssa_edges))
711 : {
712 74210 : bool allowed = !early_p || phiopt_early_allow (seq1, op1);
713 74210 : tree result = maybe_push_res_to_seq (&op1, &seq1);
714 74210 : if (dump_file && (dump_flags & TDF_FOLDING))
715 : {
716 0 : fprintf (dump_file, "\nphiopt match-simplify back:\n");
717 0 : if (seq1)
718 0 : print_gimple_seq (dump_file, seq1, 0, TDF_VOPS|TDF_MEMSYMS);
719 0 : fprintf (dump_file, "result: ");
720 0 : if (result)
721 0 : print_generic_expr (dump_file, result);
722 : else
723 0 : fprintf (dump_file, " (none)");
724 0 : fprintf (dump_file, "\n");
725 0 : if (!allowed)
726 0 : fprintf (dump_file, "rejected because early\n");
727 : }
728 : /* Early we want only to allow some generated tree codes. */
729 74210 : if (allowed && result)
730 : {
731 3236 : if (loc != UNKNOWN_LOCATION)
732 3236 : annotate_all_with_location (seq1, loc);
733 3236 : gimple_seq_add_seq_without_update (seq, seq1);
734 3236 : return result;
735 : }
736 : }
737 417109 : gimple_seq_discard (seq1);
738 :
739 417109 : return NULL;
740 : }
741 :
742 : /* empty_bb_or_one_feeding_into_p returns true if bb was empty basic block
743 : or it has one cheap preparation statement that feeds into the PHI
744 : statement and it sets STMT to that statement. */
745 : static bool
746 849075 : empty_bb_or_one_feeding_into_p (basic_block bb,
747 : gimple *phi,
748 : gimple *&stmt)
749 : {
750 849075 : stmt = nullptr;
751 849075 : gimple *stmt_to_move = nullptr;
752 849075 : tree lhs;
753 :
754 849075 : if (empty_block_p (bb))
755 : return true;
756 :
757 733529 : if (!single_pred_p (bb))
758 : return false;
759 :
760 : /* The middle bb cannot have phi nodes as we don't
761 : move those assignments yet. */
762 431604 : if (!gimple_seq_empty_p (phi_nodes (bb)))
763 : return false;
764 :
765 431578 : gimple_stmt_iterator gsi;
766 :
767 431578 : gsi = gsi_start_nondebug_after_labels_bb (bb);
768 866133 : while (!gsi_end_p (gsi))
769 : {
770 644767 : gimple *s = gsi_stmt (gsi);
771 644767 : gsi_next_nondebug (&gsi);
772 : /* Skip over Predict and nop statements. */
773 644767 : if (gimple_code (s) == GIMPLE_PREDICT
774 644767 : || gimple_code (s) == GIMPLE_NOP)
775 2977 : continue;
776 : /* If there is more one statement return false. */
777 641790 : if (stmt_to_move)
778 : return false;
779 : stmt_to_move = s;
780 : }
781 :
782 : /* The only statement here was a Predict or a nop statement
783 : so return true. */
784 221366 : if (!stmt_to_move)
785 : return true;
786 :
787 442732 : if (gimple_vuse (stmt_to_move))
788 : return false;
789 :
790 148503 : if (gimple_could_trap_p (stmt_to_move)
791 148503 : || gimple_has_side_effects (stmt_to_move))
792 5074 : return false;
793 :
794 143429 : ssa_op_iter it;
795 143429 : tree use;
796 321398 : FOR_EACH_SSA_TREE_OPERAND (use, stmt_to_move, it, SSA_OP_USE)
797 178603 : if (ssa_name_maybe_undef_p (use))
798 : return false;
799 :
800 : /* Allow assignments but allow some builtin/internal calls.
801 : As const calls don't match any of the above, yet they could
802 : still have some side-effects - they could contain
803 : gimple_could_trap_p statements, like floating point
804 : exceptions or integer division by zero. See PR70586.
805 : FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
806 : should handle this.
807 : Allow some known builtin/internal calls that are known not to
808 : trap: logical functions (e.g. bswap and bit counting). */
809 142795 : if (!is_gimple_assign (stmt_to_move))
810 : {
811 5123 : if (!is_gimple_call (stmt_to_move))
812 : return false;
813 4872 : combined_fn cfn = gimple_call_combined_fn (stmt_to_move);
814 4872 : switch (cfn)
815 : {
816 : default:
817 : return false;
818 3994 : case CFN_BUILT_IN_BSWAP16:
819 3994 : case CFN_BUILT_IN_BSWAP32:
820 3994 : case CFN_BUILT_IN_BSWAP64:
821 3994 : case CFN_BUILT_IN_BSWAP128:
822 3994 : CASE_CFN_FFS:
823 3994 : CASE_CFN_PARITY:
824 3994 : CASE_CFN_POPCOUNT:
825 3994 : CASE_CFN_CLZ:
826 3994 : CASE_CFN_CTZ:
827 3994 : case CFN_BUILT_IN_CLRSB:
828 3994 : case CFN_BUILT_IN_CLRSBL:
829 3994 : case CFN_BUILT_IN_CLRSBLL:
830 3994 : lhs = gimple_call_lhs (stmt_to_move);
831 3994 : break;
832 : }
833 : }
834 : else
835 137672 : lhs = gimple_assign_lhs (stmt_to_move);
836 :
837 141666 : gimple *use_stmt;
838 141666 : use_operand_p use_p;
839 :
840 : /* Allow only a statement which feeds into the other stmt. */
841 141666 : if (!lhs || TREE_CODE (lhs) != SSA_NAME
842 141666 : || !single_imm_use (lhs, &use_p, &use_stmt)
843 283327 : || use_stmt != phi)
844 5 : return false;
845 :
846 141661 : stmt = stmt_to_move;
847 141661 : return true;
848 : }
849 :
850 : /* Move STMT to before GSI and insert its defining
851 : name into INSERTED_EXPRS bitmap.
852 : Also rewrite its if it might be undefined when unconditionalized. */
853 : static void
854 174754 : move_stmt (gimple *stmt, gimple_stmt_iterator *gsi, auto_bitmap &inserted_exprs)
855 : {
856 174754 : if (!stmt)
857 169365 : return;
858 5389 : if (dump_file && (dump_flags & TDF_DETAILS))
859 : {
860 7 : fprintf (dump_file, "statement un-sinked:\n");
861 7 : print_gimple_stmt (dump_file, stmt, 0,
862 : TDF_VOPS|TDF_MEMSYMS);
863 : }
864 :
865 5389 : tree name = gimple_get_lhs (stmt);
866 : // Mark the name to be renamed if there is one.
867 5389 : bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (name));
868 5389 : gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt);
869 5389 : gsi_move_before (&gsi1, gsi, GSI_NEW_STMT);
870 5389 : reset_flow_sensitive_info (name);
871 :
872 : /* Rewrite some code which might be undefined when
873 : unconditionalized. */
874 5389 : if (gimple_needing_rewrite_undefined (stmt))
875 1065 : rewrite_to_defined_unconditional (gsi);
876 : }
877 :
878 : /* RAII style class to temporarily remove flow sensitive
879 : from ssa names defined by a gimple statement. */
880 : class auto_flow_sensitive
881 : {
882 : public:
883 : auto_flow_sensitive (gimple *s);
884 : ~auto_flow_sensitive ();
885 : private:
886 : auto_vec<std::pair<tree, flow_sensitive_info_storage>, 2> stack;
887 : };
888 :
889 : /* Constructor for auto_flow_sensitive. Saves
890 : off the ssa names' flow sensitive information
891 : that was defined by gimple statement S and
892 : resets it to be non-flow based ones. */
893 :
894 1028580 : auto_flow_sensitive::auto_flow_sensitive (gimple *s)
895 : {
896 1028580 : if (!s)
897 893619 : return;
898 134961 : ssa_op_iter it;
899 134961 : tree def;
900 269922 : FOR_EACH_SSA_TREE_OPERAND (def, s, it, SSA_OP_DEF)
901 : {
902 134961 : flow_sensitive_info_storage storage;
903 134961 : storage.save_and_clear (def);
904 134961 : stack.safe_push (std::make_pair (def, storage));
905 : }
906 : }
907 :
908 : /* Deconstructor, restores the flow sensitive information
909 : for the SSA names that had been saved off. */
910 :
911 1028580 : auto_flow_sensitive::~auto_flow_sensitive ()
912 : {
913 3220701 : for (auto p : stack)
914 134961 : p.second.restore (p.first);
915 1028580 : }
916 :
917 : /* Returns true if BB contains an user provided predictor
918 : (PRED_HOT_LABEL/PRED_COLD_LABEL). */
919 :
920 : static bool
921 6179 : contains_hot_cold_predict (basic_block bb)
922 : {
923 6179 : gimple_stmt_iterator gsi;
924 6179 : gsi = gsi_start_nondebug_after_labels_bb (bb);
925 8648 : for (; !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
926 : {
927 2470 : gimple *s = gsi_stmt (gsi);
928 2470 : if (gimple_code (s) != GIMPLE_PREDICT)
929 2 : continue;
930 2468 : auto predict = gimple_predict_predictor (s);
931 2468 : if (predict == PRED_HOT_LABEL
932 2468 : || predict == PRED_COLD_LABEL)
933 : return true;
934 : }
935 : return false;
936 : }
937 :
938 : /* The function match_simplify_replacement does the main work of doing the
939 : replacement using match and simplify. Return true if the replacement is done.
940 : Otherwise return false.
941 : BB is the basic block where the replacement is going to be done on. ARG0
942 : is argument 0 from PHI. Likewise for ARG1. */
943 :
944 : static bool
945 820766 : match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
946 : basic_block middle_bb_alt,
947 : edge e0, edge e1, gphi *phi,
948 : tree arg0, tree arg1, bool early_p,
949 : bool threeway_p)
950 : {
951 820766 : gimple *stmt;
952 820766 : gimple_stmt_iterator gsi;
953 820766 : edge true_edge, false_edge;
954 820766 : gimple_seq seq = NULL;
955 820766 : tree result;
956 820766 : gimple *stmt_to_move = NULL;
957 820766 : gimple *stmt_to_move_alt = NULL;
958 820766 : tree arg_true, arg_false;
959 :
960 : /* Special case A ? B : B as this will always simplify to B. */
961 820766 : if (operand_equal_for_phi_arg_p (arg0, arg1))
962 : return false;
963 :
964 : /* If the basic block only has a cheap preparation statement,
965 : allow it and move it once the transformation is done. */
966 820766 : if (!empty_bb_or_one_feeding_into_p (middle_bb, phi, stmt_to_move))
967 : return false;
968 :
969 530201 : if (threeway_p
970 530201 : && middle_bb != middle_bb_alt
971 530201 : && !empty_bb_or_one_feeding_into_p (middle_bb_alt, phi,
972 : stmt_to_move_alt))
973 : return false;
974 :
975 : /* Do not make conditional undefs unconditional. */
976 518841 : if ((TREE_CODE (arg0) == SSA_NAME
977 265425 : && ssa_name_maybe_undef_p (arg0))
978 783919 : || (TREE_CODE (arg1) == SSA_NAME
979 216643 : && ssa_name_maybe_undef_p (arg1)))
980 : return false;
981 :
982 : /* At this point we know we have a GIMPLE_COND with two successors.
983 : One successor is BB, the other successor is an empty block which
984 : falls through into BB.
985 :
986 : There is a single PHI node at the join point (BB).
987 :
988 : So, given the condition COND, and the two PHI arguments, match and simplify
989 : can happen on (COND) ? arg0 : arg1. */
990 :
991 514290 : stmt = last_nondebug_stmt (cond_bb);
992 :
993 : /* We need to know which is the true edge and which is the false
994 : edge so that we know when to invert the condition below. */
995 514290 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
996 :
997 : /* Forward the edges over the middle basic block. */
998 514290 : if (true_edge->dest == middle_bb)
999 322405 : true_edge = EDGE_SUCC (true_edge->dest, 0);
1000 514290 : if (false_edge->dest == middle_bb)
1001 191885 : false_edge = EDGE_SUCC (false_edge->dest, 0);
1002 :
1003 : /* When THREEWAY_P then e1 will point to the edge of the final transition
1004 : from middle-bb to end. */
1005 514290 : if (true_edge == e0)
1006 : {
1007 322405 : if (!threeway_p)
1008 305972 : gcc_assert (false_edge == e1);
1009 : arg_true = arg0;
1010 : arg_false = arg1;
1011 : }
1012 : else
1013 : {
1014 191885 : gcc_assert (false_edge == e0);
1015 191885 : if (!threeway_p)
1016 191489 : gcc_assert (true_edge == e1);
1017 : arg_true = arg1;
1018 : arg_false = arg0;
1019 : }
1020 :
1021 514290 : tree type = TREE_TYPE (gimple_phi_result (phi));
1022 514290 : {
1023 514290 : auto_flow_sensitive s1(stmt_to_move);
1024 514290 : auto_flow_sensitive s_alt(stmt_to_move_alt);
1025 :
1026 514290 : result = gimple_simplify_phiopt (early_p, type, stmt,
1027 : arg_true, arg_false,
1028 : &seq);
1029 514290 : }
1030 :
1031 : /* For early phiopt, we don't want to lose user generated predictors
1032 : if the phiopt is converting `if (a)` into `a` as that might
1033 : be jump threaded later on so we want to keep around the
1034 : predictors. */
1035 514290 : if (early_p && result && TREE_CODE (result) == SSA_NAME)
1036 : {
1037 24241 : bool check_it = false;
1038 24241 : tree cmp0 = gimple_cond_lhs (stmt);
1039 24241 : tree cmp1 = gimple_cond_rhs (stmt);
1040 24241 : if (result == cmp0 || result == cmp1)
1041 : check_it = true;
1042 18415 : else if (gimple_seq_singleton_p (seq))
1043 : {
1044 18317 : gimple *stmt = gimple_seq_first_stmt (seq);
1045 18317 : if (is_gimple_assign (stmt)
1046 18317 : && result == gimple_assign_lhs (stmt)
1047 36634 : && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
1048 : == tcc_comparison)
1049 : check_it = true;
1050 : }
1051 : if (!check_it)
1052 : ;
1053 5826 : else if (contains_hot_cold_predict (middle_bb))
1054 : return false;
1055 5825 : else if (threeway_p
1056 : && middle_bb != middle_bb_alt
1057 5825 : && contains_hot_cold_predict (middle_bb_alt))
1058 : return false;
1059 : }
1060 :
1061 514283 : if (!result)
1062 : {
1063 : /* If we don't get back a MIN/MAX_EXPR still make sure the expression
1064 : stays in a form to be recognized by ISA that map to IEEE x > y ? x : y
1065 : semantics (that's not IEEE max semantics). */
1066 430846 : if (!HONOR_NANS (type) && !HONOR_SIGNED_ZEROS (type))
1067 : return false;
1068 16569 : if (stmt_to_move || stmt_to_move_alt)
1069 : return false;
1070 13735 : tree_code cmp = gimple_cond_code (stmt);
1071 13735 : if (cmp != LT_EXPR && cmp != LE_EXPR
1072 13735 : && cmp != GT_EXPR && cmp != GE_EXPR)
1073 : return false;
1074 6574 : tree lhs = gimple_cond_lhs (stmt);
1075 6574 : tree rhs = gimple_cond_rhs (stmt);
1076 : /* `lhs CMP rhs ? lhs : rhs` or `lhs CMP rhs ? rhs : lhs`
1077 : are only acceptable case here. */
1078 6574 : if ((!operand_equal_for_phi_arg_p (lhs, arg_false)
1079 2568 : || !operand_equal_for_phi_arg_p (rhs, arg_true))
1080 6634 : && (!operand_equal_for_phi_arg_p (rhs, arg_false)
1081 1603 : || !operand_equal_for_phi_arg_p (lhs, arg_true)))
1082 2640 : return false;
1083 3934 : seq = nullptr;
1084 3934 : result = gimple_build (&seq, cmp, boolean_type_node, lhs, rhs);
1085 3934 : result = gimple_build (&seq, COND_EXPR, type, result,
1086 : arg_true, arg_false);
1087 3934 : statistics_counter_event (cfun, "Non-IEEE FP MIN/MAX PHI replacement",
1088 : 1);
1089 : }
1090 87377 : if (dump_file && (dump_flags & TDF_FOLDING))
1091 1 : fprintf (dump_file, "accepted the phiopt match-simplify.\n");
1092 :
1093 87377 : auto_bitmap exprs_maybe_dce;
1094 :
1095 : /* Mark the cond statements' lhs/rhs as maybe dce. */
1096 87377 : if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
1097 87377 : && !SSA_NAME_IS_DEFAULT_DEF (gimple_cond_lhs (stmt)))
1098 82384 : bitmap_set_bit (exprs_maybe_dce,
1099 82384 : SSA_NAME_VERSION (gimple_cond_lhs (stmt)));
1100 87377 : if (TREE_CODE (gimple_cond_rhs (stmt)) == SSA_NAME
1101 87377 : && !SSA_NAME_IS_DEFAULT_DEF (gimple_cond_rhs (stmt)))
1102 27681 : bitmap_set_bit (exprs_maybe_dce,
1103 27681 : SSA_NAME_VERSION (gimple_cond_rhs (stmt)));
1104 :
1105 87377 : gsi = gsi_last_bb (cond_bb);
1106 : /* Insert the sequence generated from gimple_simplify_phiopt. */
1107 87377 : if (seq)
1108 : {
1109 : // Mark the lhs of the new statements maybe for dce
1110 79741 : mark_lhs_in_seq_for_dce (exprs_maybe_dce, seq);
1111 79741 : gsi_insert_seq_before (&gsi, seq, GSI_CONTINUE_LINKING);
1112 : }
1113 :
1114 : /* If there was a statement to move, move it to right before
1115 : the original conditional. */
1116 87377 : move_stmt (stmt_to_move, &gsi, exprs_maybe_dce);
1117 87377 : move_stmt (stmt_to_move_alt, &gsi, exprs_maybe_dce);
1118 :
1119 87377 : replace_phi_edge_with_variable (cond_bb, e1, phi, result, exprs_maybe_dce);
1120 :
1121 : /* Add Statistic here even though replace_phi_edge_with_variable already
1122 : does it as we want to be able to count when match-simplify happens vs
1123 : the others. */
1124 87377 : statistics_counter_event (cfun, "match-simplify PHI replacement", 1);
1125 :
1126 : /* Note that we optimized this PHI. */
1127 87377 : return true;
1128 87377 : }
1129 :
1130 : /* Update *ARG which is defined in STMT so that it contains the
1131 : computed value if that seems profitable. Return true if the
1132 : statement is made dead by that rewriting. */
1133 :
1134 : static bool
1135 338306 : jump_function_from_stmt (tree *arg, gimple *stmt)
1136 : {
1137 338306 : enum tree_code code = gimple_assign_rhs_code (stmt);
1138 338306 : if (code == ADDR_EXPR)
1139 : {
1140 : /* For arg = &p->i transform it to p, if possible. */
1141 4733 : tree rhs1 = gimple_assign_rhs1 (stmt);
1142 4733 : poly_int64 offset;
1143 4733 : tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs1, 0),
1144 : &offset);
1145 4733 : if (tem
1146 4652 : && TREE_CODE (tem) == MEM_REF
1147 9385 : && known_eq (mem_ref_offset (tem) + offset, 0))
1148 : {
1149 1873 : *arg = TREE_OPERAND (tem, 0);
1150 1873 : return true;
1151 : }
1152 : }
1153 : /* TODO: Much like IPA-CP jump-functions we want to handle constant
1154 : additions symbolically here, and we'd need to update the comparison
1155 : code that compares the arg + cst tuples in our caller. For now the
1156 : code above exactly handles the VEC_BASE pattern from vec.h. */
1157 : return false;
1158 : }
1159 :
1160 : /* RHS is a source argument in a BIT_AND_EXPR or BIT_IOR_EXPR which feeds
1161 : a conditional of the form SSA_NAME NE 0.
1162 :
1163 : If RHS is fed by a simple EQ_EXPR or NE_EXPR comparison of two values,
1164 : see if the two input values of the comparison match arg0 and arg1.
1165 :
1166 : If so update *code and return TRUE. Otherwise return FALSE. */
1167 :
1168 : static bool
1169 165350 : rhs_is_fed_for_value_replacement (const_tree arg0, const_tree arg1,
1170 : enum tree_code *code, const_tree rhs,
1171 : enum tree_code bit_expression_code)
1172 : {
1173 : /* Obviously if RHS is not an SSA_NAME, we can't look at the defining
1174 : statement. */
1175 165350 : if (TREE_CODE (rhs) == SSA_NAME)
1176 : {
1177 127420 : gimple *def1 = SSA_NAME_DEF_STMT (rhs);
1178 :
1179 : /* Verify the defining statement has an EQ_EXPR or NE_EXPR on the RHS. */
1180 127420 : if (is_gimple_assign (def1)
1181 127420 : && ((bit_expression_code == BIT_AND_EXPR
1182 80939 : && gimple_assign_rhs_code (def1) == EQ_EXPR)
1183 98002 : || (bit_expression_code == BIT_IOR_EXPR
1184 36707 : && gimple_assign_rhs_code (def1) == NE_EXPR)))
1185 : {
1186 : /* Finally verify the source operands of the EQ_EXPR or NE_EXPR
1187 : are equal to arg0 and arg1. */
1188 24376 : tree op0 = gimple_assign_rhs1 (def1);
1189 24376 : tree op1 = gimple_assign_rhs2 (def1);
1190 24376 : if ((operand_equal_for_phi_arg_p (arg0, op0)
1191 576 : && operand_equal_for_phi_arg_p (arg1, op1))
1192 24895 : || (operand_equal_for_phi_arg_p (arg0, op1)
1193 676 : && operand_equal_for_phi_arg_p (arg1, op0)))
1194 : {
1195 : /* We will perform the optimization. */
1196 473 : *code = gimple_assign_rhs_code (def1);
1197 473 : return true;
1198 : }
1199 : }
1200 : }
1201 : return false;
1202 : }
1203 :
1204 : /* Return TRUE if arg0/arg1 are equal to the rhs/lhs or lhs/rhs of COND.
1205 :
1206 : Also return TRUE if arg0/arg1 are equal to the source arguments of an
1207 : EQ comparison feeding a BIT_AND_EXPR, or NE comparison feeding a
1208 : BIT_IOR_EXPR which feeds COND.
1209 :
1210 : Return FALSE otherwise. */
1211 :
1212 : static bool
1213 690398 : operand_equal_for_value_replacement (const_tree arg0, const_tree arg1,
1214 : enum tree_code *code, gimple *cond)
1215 : {
1216 690398 : gimple *def;
1217 690398 : tree lhs = gimple_cond_lhs (cond);
1218 690398 : tree rhs = gimple_cond_rhs (cond);
1219 :
1220 690398 : if ((operand_equal_for_phi_arg_p (arg0, lhs)
1221 27991 : && operand_equal_for_phi_arg_p (arg1, rhs))
1222 710285 : || (operand_equal_for_phi_arg_p (arg1, lhs)
1223 47775 : && operand_equal_for_phi_arg_p (arg0, rhs)))
1224 15727 : return true;
1225 :
1226 : /* Now handle more complex case where we have an EQ comparison
1227 : feeding a BIT_AND_EXPR, or a NE comparison feeding a BIT_IOR_EXPR,
1228 : which then feeds into COND.
1229 :
1230 : First verify that COND is of the form SSA_NAME NE 0. */
1231 387987 : if (*code != NE_EXPR || !integer_zerop (rhs)
1232 951367 : || TREE_CODE (lhs) != SSA_NAME)
1233 398094 : return false;
1234 :
1235 : /* Now ensure that SSA_NAME is set by a BIT_AND_EXPR or BIT_OR_EXPR. */
1236 276577 : def = SSA_NAME_DEF_STMT (lhs);
1237 276577 : if (!is_gimple_assign (def)
1238 276577 : || (gimple_assign_rhs_code (def) != BIT_AND_EXPR
1239 128317 : && gimple_assign_rhs_code (def) != BIT_IOR_EXPR))
1240 : return false;
1241 :
1242 : /* Now verify arg0/arg1 correspond to the source arguments of an EQ
1243 : comparison feeding the BIT_AND_EXPR or a NE comparison feeding the
1244 : BIT_IOR_EXPR. */
1245 :
1246 82844 : tree tmp = gimple_assign_rhs1 (def);
1247 82844 : if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp,
1248 : gimple_assign_rhs_code (def)))
1249 : return true;
1250 :
1251 82506 : tmp = gimple_assign_rhs2 (def);
1252 82506 : if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp,
1253 : gimple_assign_rhs_code (def)))
1254 : return true;
1255 :
1256 : return false;
1257 : }
1258 :
1259 : /* Returns true if ARG is a neutral element for operation CODE
1260 : on the RIGHT side. */
1261 :
1262 : static bool
1263 1130 : neutral_element_p (tree_code code, tree arg, bool right)
1264 : {
1265 1130 : switch (code)
1266 : {
1267 41 : case PLUS_EXPR:
1268 41 : case BIT_IOR_EXPR:
1269 41 : case BIT_XOR_EXPR:
1270 41 : return integer_zerop (arg);
1271 :
1272 193 : case LROTATE_EXPR:
1273 193 : case RROTATE_EXPR:
1274 193 : case LSHIFT_EXPR:
1275 193 : case RSHIFT_EXPR:
1276 193 : case MINUS_EXPR:
1277 193 : case POINTER_PLUS_EXPR:
1278 193 : return right && integer_zerop (arg);
1279 :
1280 608 : case MULT_EXPR:
1281 608 : return integer_onep (arg);
1282 :
1283 31 : case TRUNC_DIV_EXPR:
1284 31 : case CEIL_DIV_EXPR:
1285 31 : case FLOOR_DIV_EXPR:
1286 31 : case ROUND_DIV_EXPR:
1287 31 : case EXACT_DIV_EXPR:
1288 31 : return right && integer_onep (arg);
1289 :
1290 0 : case BIT_AND_EXPR:
1291 0 : return integer_all_onesp (arg);
1292 :
1293 : default:
1294 : return false;
1295 : }
1296 : }
1297 :
1298 : /* Returns true if ARG is an absorbing element for operation CODE. */
1299 :
1300 : static bool
1301 860 : absorbing_element_p (tree_code code, tree arg, bool right, tree rval)
1302 : {
1303 860 : switch (code)
1304 : {
1305 18 : case BIT_IOR_EXPR:
1306 18 : return integer_all_onesp (arg);
1307 :
1308 37 : case MULT_EXPR:
1309 37 : case BIT_AND_EXPR:
1310 37 : return integer_zerop (arg);
1311 :
1312 2 : case LSHIFT_EXPR:
1313 2 : case RSHIFT_EXPR:
1314 2 : case LROTATE_EXPR:
1315 2 : case RROTATE_EXPR:
1316 2 : return !right && integer_zerop (arg);
1317 :
1318 169 : case TRUNC_DIV_EXPR:
1319 169 : case CEIL_DIV_EXPR:
1320 169 : case FLOOR_DIV_EXPR:
1321 169 : case ROUND_DIV_EXPR:
1322 169 : case EXACT_DIV_EXPR:
1323 169 : case TRUNC_MOD_EXPR:
1324 169 : case CEIL_MOD_EXPR:
1325 169 : case FLOOR_MOD_EXPR:
1326 169 : case ROUND_MOD_EXPR:
1327 169 : return (!right
1328 11 : && integer_zerop (arg)
1329 179 : && tree_single_nonzero_warnv_p (rval, NULL));
1330 :
1331 : default:
1332 : return false;
1333 : }
1334 : }
1335 :
1336 : /* The function value_replacement does the main work of doing the value
1337 : replacement. Return non-zero if the replacement is done. Otherwise return
1338 : 0. If we remove the middle basic block, return 2.
1339 : BB is the basic block where the replacement is going to be done on. ARG0
1340 : is argument 0 from the PHI. Likewise for ARG1. */
1341 :
1342 : static int
1343 2506886 : value_replacement (basic_block cond_bb, basic_block middle_bb,
1344 : edge e0, edge e1, gphi *phi, tree arg0, tree arg1)
1345 : {
1346 2506886 : gimple_stmt_iterator gsi;
1347 2506886 : edge true_edge, false_edge;
1348 2506886 : enum tree_code code;
1349 2506886 : bool empty_or_with_defined_p = true;
1350 :
1351 : /* Virtual operands don't need to be handled. */
1352 4426942 : if (virtual_operand_p (arg1))
1353 : return 0;
1354 :
1355 : /* Special case A ? B : B as this will always simplify to B. */
1356 1346540 : if (operand_equal_for_phi_arg_p (arg0, arg1))
1357 : return 0;
1358 :
1359 2383946 : gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_bb));
1360 1191973 : code = gimple_cond_code (cond);
1361 :
1362 : /* This transformation is only valid for equality comparisons. */
1363 1191973 : if (code != NE_EXPR && code != EQ_EXPR)
1364 : return 0;
1365 :
1366 : /* Do not make conditional undefs unconditional. */
1367 718962 : if ((TREE_CODE (arg0) == SSA_NAME
1368 546739 : && ssa_name_maybe_undef_p (arg0))
1369 1263896 : || (TREE_CODE (arg1) == SSA_NAME
1370 316261 : && ssa_name_maybe_undef_p (arg1)))
1371 : return false;
1372 :
1373 : /* If the type says honor signed zeros we cannot do this
1374 : optimization. */
1375 703200 : if (HONOR_SIGNED_ZEROS (arg1))
1376 : return 0;
1377 :
1378 : /* If there is a statement in MIDDLE_BB that defines one of the PHI
1379 : arguments, then adjust arg0 or arg1. */
1380 690398 : gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
1381 2151231 : while (!gsi_end_p (gsi))
1382 : {
1383 1460833 : gimple *stmt = gsi_stmt (gsi);
1384 1460833 : tree lhs;
1385 1460833 : gsi_next_nondebug (&gsi);
1386 1460833 : if (!is_gimple_assign (stmt))
1387 : {
1388 211770 : if (gimple_code (stmt) != GIMPLE_PREDICT
1389 211770 : && gimple_code (stmt) != GIMPLE_NOP)
1390 : empty_or_with_defined_p = false;
1391 211770 : continue;
1392 : }
1393 : /* Now try to adjust arg0 or arg1 according to the computation
1394 : in the statement. */
1395 1249063 : lhs = gimple_assign_lhs (stmt);
1396 338306 : if (!(lhs == arg0
1397 338306 : && jump_function_from_stmt (&arg0, stmt))
1398 1250936 : || (lhs == arg1
1399 0 : && jump_function_from_stmt (&arg1, stmt)))
1400 : empty_or_with_defined_p = false;
1401 : }
1402 :
1403 : /* The middle bb is not empty if there are any phi nodes. */
1404 690398 : if (phi_nodes (middle_bb))
1405 84904 : empty_or_with_defined_p = false;
1406 :
1407 : /* We need to know which is the true edge and which is the false
1408 : edge so that we know if have abs or negative abs. */
1409 690398 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1410 :
1411 : /* At this point we know we have a COND_EXPR with two successors.
1412 : One successor is BB, the other successor is an empty block which
1413 : falls through into BB.
1414 :
1415 : The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
1416 :
1417 : There is a single PHI node at the join point (BB) with two arguments.
1418 :
1419 : We now need to verify that the two arguments in the PHI node match
1420 : the two arguments to the equality comparison. */
1421 :
1422 690398 : bool equal_p = operand_equal_for_value_replacement (arg0, arg1, &code, cond);
1423 690398 : bool maybe_equal_p = false;
1424 690398 : if (!equal_p
1425 690398 : && empty_or_with_defined_p
1426 194706 : && TREE_CODE (gimple_cond_rhs (cond)) == INTEGER_CST
1427 845216 : && (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond), arg0)
1428 154818 : ? TREE_CODE (arg1) == INTEGER_CST
1429 145533 : : (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond), arg1)
1430 20284 : && TREE_CODE (arg0) == INTEGER_CST)))
1431 : maybe_equal_p = true;
1432 672440 : if (equal_p || maybe_equal_p)
1433 : {
1434 34158 : edge e;
1435 34158 : tree arg;
1436 :
1437 : /* For NE_EXPR, we want to build an assignment result = arg where
1438 : arg is the PHI argument associated with the true edge. For
1439 : EQ_EXPR we want the PHI argument associated with the false edge. */
1440 34158 : e = (code == NE_EXPR ? true_edge : false_edge);
1441 :
1442 : /* Unfortunately, E may not reach BB (it may instead have gone to
1443 : OTHER_BLOCK). If that is the case, then we want the single outgoing
1444 : edge from OTHER_BLOCK which reaches BB and represents the desired
1445 : path from COND_BLOCK. */
1446 34158 : if (e->dest == middle_bb)
1447 13300 : e = single_succ_edge (e->dest);
1448 :
1449 : /* Now we know the incoming edge to BB that has the argument for the
1450 : RHS of our new assignment statement. */
1451 34158 : if (e0 == e)
1452 : arg = arg0;
1453 : else
1454 20858 : arg = arg1;
1455 :
1456 : /* If the middle basic block was empty or is defining the
1457 : PHI arguments and this is a single phi where the args are different
1458 : for the edges e0 and e1 then we can remove the middle basic block. */
1459 34158 : if (empty_or_with_defined_p
1460 34158 : && single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)),
1461 : e0, e1) == phi)
1462 : {
1463 18186 : use_operand_p use_p;
1464 18186 : gimple *use_stmt;
1465 :
1466 : /* Even if arg0/arg1 isn't equal to second operand of cond, we
1467 : can optimize away the bb if we can prove it doesn't care whether
1468 : phi result is arg0/arg1 or second operand of cond. Consider:
1469 : <bb 2> [local count: 118111600]:
1470 : if (i_2(D) == 4)
1471 : goto <bb 4>; [97.00%]
1472 : else
1473 : goto <bb 3>; [3.00%]
1474 :
1475 : <bb 3> [local count: 3540129]:
1476 :
1477 : <bb 4> [local count: 118111600]:
1478 : # i_6 = PHI <i_2(D)(3), 6(2)>
1479 : _3 = i_6 != 0;
1480 : Here, carg is 4, oarg is 6, crhs is 0, and because
1481 : (4 != 0) == (6 != 0), we don't care if i_6 is 4 or 6, both
1482 : have the same outcome. So, we can optimize this to:
1483 : _3 = i_2(D) != 0;
1484 : If the single imm use of phi result >, >=, < or <=, similarly
1485 : we can check if both carg and oarg compare the same against
1486 : crhs using ccode. */
1487 18186 : if (maybe_equal_p
1488 16365 : && TREE_CODE (arg) != INTEGER_CST
1489 34536 : && single_imm_use (gimple_phi_result (phi), &use_p, &use_stmt))
1490 : {
1491 9579 : enum tree_code ccode = ERROR_MARK;
1492 9579 : tree clhs = NULL_TREE, crhs = NULL_TREE;
1493 9579 : tree carg = gimple_cond_rhs (cond);
1494 9579 : tree oarg = e0 == e ? arg1 : arg0;
1495 9579 : if (is_gimple_assign (use_stmt)
1496 9579 : && (TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
1497 : == tcc_comparison))
1498 : {
1499 58 : ccode = gimple_assign_rhs_code (use_stmt);
1500 58 : clhs = gimple_assign_rhs1 (use_stmt);
1501 58 : crhs = gimple_assign_rhs2 (use_stmt);
1502 : }
1503 9521 : else if (gimple_code (use_stmt) == GIMPLE_COND)
1504 : {
1505 78 : ccode = gimple_cond_code (use_stmt);
1506 78 : clhs = gimple_cond_lhs (use_stmt);
1507 78 : crhs = gimple_cond_rhs (use_stmt);
1508 : }
1509 136 : if (ccode != ERROR_MARK
1510 136 : && clhs == gimple_phi_result (phi)
1511 233 : && TREE_CODE (crhs) == INTEGER_CST)
1512 45 : switch (ccode)
1513 : {
1514 26 : case EQ_EXPR:
1515 26 : case NE_EXPR:
1516 26 : if (!tree_int_cst_equal (crhs, carg)
1517 26 : && !tree_int_cst_equal (crhs, oarg))
1518 : equal_p = true;
1519 : break;
1520 2 : case GT_EXPR:
1521 4 : if (tree_int_cst_lt (crhs, carg)
1522 2 : == tree_int_cst_lt (crhs, oarg))
1523 : equal_p = true;
1524 : break;
1525 0 : case GE_EXPR:
1526 0 : if (tree_int_cst_le (crhs, carg)
1527 0 : == tree_int_cst_le (crhs, oarg))
1528 : equal_p = true;
1529 : break;
1530 13 : case LT_EXPR:
1531 26 : if (tree_int_cst_lt (carg, crhs)
1532 13 : == tree_int_cst_lt (oarg, crhs))
1533 : equal_p = true;
1534 : break;
1535 4 : case LE_EXPR:
1536 8 : if (tree_int_cst_le (carg, crhs)
1537 4 : == tree_int_cst_le (oarg, crhs))
1538 : equal_p = true;
1539 : break;
1540 : default:
1541 : break;
1542 : }
1543 9563 : if (equal_p)
1544 : {
1545 16 : tree phires = gimple_phi_result (phi);
1546 16 : if (SSA_NAME_RANGE_INFO (phires))
1547 : {
1548 : /* After the optimization PHI result can have value
1549 : which it couldn't have previously. */
1550 15 : value_range r (TREE_TYPE (phires));
1551 15 : if (get_global_range_query ()->range_of_expr (r, phires,
1552 : phi))
1553 : {
1554 15 : value_range tmp (carg, carg);
1555 15 : r.union_ (tmp);
1556 15 : reset_flow_sensitive_info (phires);
1557 15 : set_range_info (phires, r);
1558 15 : }
1559 : else
1560 0 : reset_flow_sensitive_info (phires);
1561 15 : }
1562 : }
1563 16 : if (equal_p && MAY_HAVE_DEBUG_BIND_STMTS)
1564 : {
1565 13 : imm_use_iterator imm_iter;
1566 13 : tree phires = gimple_phi_result (phi);
1567 13 : tree temp = NULL_TREE;
1568 13 : bool reset_p = false;
1569 :
1570 : /* Add # DEBUG D#1 => arg != carg ? arg : oarg. */
1571 42 : FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, phires)
1572 : {
1573 30 : if (!is_gimple_debug (use_stmt))
1574 13 : continue;
1575 17 : if (temp == NULL_TREE)
1576 : {
1577 12 : if (!single_pred_p (middle_bb)
1578 12 : || EDGE_COUNT (gimple_bb (phi)->preds) != 2)
1579 : {
1580 : /* But only if middle_bb has a single
1581 : predecessor and phi bb has two, otherwise
1582 : we could use a SSA_NAME not usable in that
1583 : place or wrong-debug. */
1584 1 : reset_p = true;
1585 1 : break;
1586 : }
1587 11 : gimple_stmt_iterator gsi
1588 11 : = gsi_after_labels (gimple_bb (phi));
1589 11 : tree type = TREE_TYPE (phires);
1590 11 : temp = build_debug_expr_decl (type);
1591 11 : tree t = build2 (NE_EXPR, boolean_type_node,
1592 : arg, carg);
1593 11 : t = build3 (COND_EXPR, type, t, arg, oarg);
1594 11 : gimple *g = gimple_build_debug_bind (temp, t, phi);
1595 11 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
1596 : }
1597 32 : FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
1598 16 : replace_exp (use_p, temp);
1599 16 : update_stmt (use_stmt);
1600 13 : }
1601 13 : if (reset_p)
1602 1 : reset_debug_uses (phi);
1603 : }
1604 : }
1605 8623 : if (equal_p)
1606 : {
1607 1837 : replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
1608 : /* Note that we optimized this PHI. */
1609 1837 : return 2;
1610 : }
1611 : }
1612 15972 : else if (equal_p)
1613 : {
1614 14379 : if (!single_pred_p (middle_bb))
1615 : return 0;
1616 12400 : statistics_counter_event (cfun, "Replace PHI with "
1617 : "variable/value_replacement", 1);
1618 :
1619 : /* Replace the PHI arguments with arg. */
1620 12400 : SET_PHI_ARG_DEF (phi, e0->dest_idx, arg);
1621 12400 : SET_PHI_ARG_DEF (phi, e1->dest_idx, arg);
1622 12400 : if (dump_file && (dump_flags & TDF_DETAILS))
1623 : {
1624 0 : fprintf (dump_file, "PHI ");
1625 0 : print_generic_expr (dump_file, gimple_phi_result (phi));
1626 0 : fprintf (dump_file, " reduced for COND_EXPR in block %d to ",
1627 : cond_bb->index);
1628 0 : print_generic_expr (dump_file, arg);
1629 0 : fprintf (dump_file, ".\n");
1630 : }
1631 12400 : return 1;
1632 : }
1633 : }
1634 :
1635 3057683 : if (!single_pred_p (middle_bb))
1636 : return 0;
1637 :
1638 : /* Now optimize (x != 0) ? x + y : y to just x + y. */
1639 565140 : gsi = gsi_last_nondebug_bb (middle_bb);
1640 565140 : if (gsi_end_p (gsi))
1641 : return 0;
1642 :
1643 387629 : gimple *assign = gsi_stmt (gsi);
1644 387629 : if (!is_gimple_assign (assign)
1645 387629 : || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
1646 110435 : && !POINTER_TYPE_P (TREE_TYPE (arg0))))
1647 : return 0;
1648 :
1649 330341 : if (gimple_assign_rhs_class (assign) != GIMPLE_BINARY_RHS)
1650 : {
1651 : /* If last stmt of the middle_bb is a conversion, handle it like
1652 : a preparation statement through constant evaluation with
1653 : checking for UB. */
1654 142546 : enum tree_code sc = gimple_assign_rhs_code (assign);
1655 142546 : if (CONVERT_EXPR_CODE_P (sc))
1656 : assign = NULL;
1657 : else
1658 : return 0;
1659 : }
1660 :
1661 : /* Punt if there are (degenerate) PHIs in middle_bb, there should not be. */
1662 209430 : if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
1663 : return 0;
1664 :
1665 : /* Allow up to 2 cheap preparation statements that prepare argument
1666 : for assign, e.g.:
1667 : if (y_4 != 0)
1668 : goto <bb 3>;
1669 : else
1670 : goto <bb 4>;
1671 : <bb 3>:
1672 : _1 = (int) y_4;
1673 : iftmp.0_6 = x_5(D) r<< _1;
1674 : <bb 4>:
1675 : # iftmp.0_2 = PHI <iftmp.0_6(3), x_5(D)(2)>
1676 : or:
1677 : if (y_3(D) == 0)
1678 : goto <bb 4>;
1679 : else
1680 : goto <bb 3>;
1681 : <bb 3>:
1682 : y_4 = y_3(D) & 31;
1683 : _1 = (int) y_4;
1684 : _6 = x_5(D) r<< _1;
1685 : <bb 4>:
1686 : # _2 = PHI <x_5(D)(2), _6(3)> */
1687 209430 : gimple *prep_stmt[2] = { NULL, NULL };
1688 209430 : int prep_cnt;
1689 209430 : for (prep_cnt = 0; ; prep_cnt++)
1690 : {
1691 269104 : if (prep_cnt || assign)
1692 247469 : gsi_prev_nondebug (&gsi);
1693 269104 : if (gsi_end_p (gsi))
1694 : break;
1695 :
1696 201525 : gimple *g = gsi_stmt (gsi);
1697 201525 : if (gimple_code (g) == GIMPLE_LABEL)
1698 : break;
1699 :
1700 201170 : if (prep_cnt == 2 || !is_gimple_assign (g))
1701 141496 : return 0;
1702 :
1703 178031 : tree lhs = gimple_assign_lhs (g);
1704 178031 : tree rhs1 = gimple_assign_rhs1 (g);
1705 178031 : use_operand_p use_p;
1706 178031 : gimple *use_stmt;
1707 178031 : if (TREE_CODE (lhs) != SSA_NAME
1708 171123 : || TREE_CODE (rhs1) != SSA_NAME
1709 108529 : || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1710 105014 : || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1711 100742 : || !single_imm_use (lhs, &use_p, &use_stmt)
1712 277972 : || ((prep_cnt || assign)
1713 79848 : && use_stmt != (prep_cnt ? prep_stmt[prep_cnt - 1] : assign)))
1714 85763 : return 0;
1715 92268 : switch (gimple_assign_rhs_code (g))
1716 : {
1717 : CASE_CONVERT:
1718 : break;
1719 19784 : case PLUS_EXPR:
1720 19784 : case BIT_AND_EXPR:
1721 19784 : case BIT_IOR_EXPR:
1722 19784 : case BIT_XOR_EXPR:
1723 19784 : if (TREE_CODE (gimple_assign_rhs2 (g)) != INTEGER_CST)
1724 : return 0;
1725 : break;
1726 : default:
1727 : return 0;
1728 : }
1729 59674 : prep_stmt[prep_cnt] = g;
1730 59674 : }
1731 :
1732 : /* Only transform if it removes the condition. */
1733 67934 : if (!single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)), e0, e1))
1734 : return 0;
1735 :
1736 : /* Size-wise, this is always profitable. */
1737 52486 : if (optimize_bb_for_speed_p (cond_bb)
1738 : /* The special case is useless if it has a low probability. */
1739 49754 : && profile_status_for_fn (cfun) != PROFILE_ABSENT
1740 60993 : && EDGE_PRED (middle_bb, 0)->probability < profile_probability::even ()
1741 : /* If assign is cheap, there is no point avoiding it. */
1742 63745 : && estimate_num_insns_seq (bb_seq (middle_bb), &eni_time_weights)
1743 11259 : >= 3 * estimate_num_insns (cond, &eni_time_weights))
1744 78 : return 0;
1745 :
1746 52408 : tree cond_lhs = gimple_cond_lhs (cond);
1747 52408 : tree cond_rhs = gimple_cond_rhs (cond);
1748 :
1749 : /* Propagate the cond_rhs constant through preparation stmts,
1750 : make sure UB isn't invoked while doing that. */
1751 54192 : for (int i = prep_cnt - 1; i >= 0; --i)
1752 : {
1753 13539 : gimple *g = prep_stmt[i];
1754 13539 : tree grhs1 = gimple_assign_rhs1 (g);
1755 13539 : if (!operand_equal_for_phi_arg_p (cond_lhs, grhs1))
1756 : return 0;
1757 7390 : cond_lhs = gimple_assign_lhs (g);
1758 7390 : cond_rhs = fold_convert (TREE_TYPE (grhs1), cond_rhs);
1759 7390 : if (TREE_CODE (cond_rhs) != INTEGER_CST
1760 7390 : || TREE_OVERFLOW (cond_rhs))
1761 : return 0;
1762 1784 : if (gimple_assign_rhs_class (g) == GIMPLE_BINARY_RHS)
1763 : {
1764 737 : cond_rhs = int_const_binop (gimple_assign_rhs_code (g), cond_rhs,
1765 737 : gimple_assign_rhs2 (g));
1766 737 : if (TREE_OVERFLOW (cond_rhs))
1767 : return 0;
1768 : }
1769 1784 : cond_rhs = fold_convert (TREE_TYPE (cond_lhs), cond_rhs);
1770 1784 : if (TREE_CODE (cond_rhs) != INTEGER_CST
1771 1784 : || TREE_OVERFLOW (cond_rhs))
1772 : return 0;
1773 : }
1774 :
1775 40653 : tree lhs, rhs1, rhs2;
1776 40653 : enum tree_code code_def;
1777 40653 : if (assign)
1778 : {
1779 40395 : lhs = gimple_assign_lhs (assign);
1780 40395 : rhs1 = gimple_assign_rhs1 (assign);
1781 40395 : rhs2 = gimple_assign_rhs2 (assign);
1782 40395 : code_def = gimple_assign_rhs_code (assign);
1783 : }
1784 : else
1785 : {
1786 258 : gcc_assert (prep_cnt > 0);
1787 : lhs = cond_lhs;
1788 : rhs1 = NULL_TREE;
1789 : rhs2 = NULL_TREE;
1790 : code_def = ERROR_MARK;
1791 : }
1792 :
1793 23609 : if (((code == NE_EXPR && e1 == false_edge)
1794 19796 : || (code == EQ_EXPR && e1 == true_edge))
1795 23645 : && arg0 == lhs
1796 64298 : && ((assign == NULL
1797 257 : && operand_equal_for_phi_arg_p (arg1, cond_rhs))
1798 : || (assign
1799 23388 : && arg1 == rhs1
1800 14886 : && operand_equal_for_phi_arg_p (rhs2, cond_lhs)
1801 416 : && neutral_element_p (code_def, cond_rhs, true))
1802 23323 : || (assign
1803 23323 : && arg1 == rhs2
1804 1384 : && operand_equal_for_phi_arg_p (rhs1, cond_lhs)
1805 714 : && neutral_element_p (code_def, cond_rhs, false))
1806 : || (assign
1807 23316 : && operand_equal_for_phi_arg_p (arg1, cond_rhs)
1808 2837 : && ((operand_equal_for_phi_arg_p (rhs2, cond_lhs)
1809 236 : && absorbing_element_p (code_def, cond_rhs, true, rhs2))
1810 2836 : || (operand_equal_for_phi_arg_p (rhs1, cond_lhs)
1811 624 : && absorbing_element_p (code_def,
1812 : cond_rhs, false, rhs2))))))
1813 : {
1814 106 : gsi = gsi_for_stmt (cond);
1815 : /* Moving ASSIGN might change VR of lhs, e.g. when moving u_6
1816 : def-stmt in:
1817 : if (n_5 != 0)
1818 : goto <bb 3>;
1819 : else
1820 : goto <bb 4>;
1821 :
1822 : <bb 3>:
1823 : # RANGE [0, 4294967294]
1824 : u_6 = n_5 + 4294967295;
1825 :
1826 : <bb 4>:
1827 : # u_3 = PHI <u_6(3), 4294967295(2)> */
1828 106 : reset_flow_sensitive_info (lhs);
1829 106 : gimple_stmt_iterator gsi_from;
1830 179 : for (int i = prep_cnt - 1; i >= 0; --i)
1831 : {
1832 73 : tree plhs = gimple_assign_lhs (prep_stmt[i]);
1833 73 : reset_flow_sensitive_info (plhs);
1834 73 : gsi_from = gsi_for_stmt (prep_stmt[i]);
1835 73 : gsi_move_before (&gsi_from, &gsi);
1836 : }
1837 106 : if (assign)
1838 : {
1839 102 : gsi_from = gsi_for_stmt (assign);
1840 102 : gsi_move_before (&gsi_from, &gsi);
1841 : }
1842 106 : replace_phi_edge_with_variable (cond_bb, e1, phi, lhs);
1843 106 : return 2;
1844 : }
1845 :
1846 : return 0;
1847 : }
1848 :
1849 : /* Attempt to optimize (x <=> y) cmp 0 and similar comparisons.
1850 : For strong ordering <=> try to match something like:
1851 : <bb 2> : // cond3_bb (== cond2_bb)
1852 : if (x_4(D) != y_5(D))
1853 : goto <bb 3>; [INV]
1854 : else
1855 : goto <bb 6>; [INV]
1856 :
1857 : <bb 3> : // cond_bb
1858 : if (x_4(D) < y_5(D))
1859 : goto <bb 6>; [INV]
1860 : else
1861 : goto <bb 4>; [INV]
1862 :
1863 : <bb 4> : // middle_bb
1864 :
1865 : <bb 6> : // phi_bb
1866 : # iftmp.0_2 = PHI <1(4), 0(2), -1(3)>
1867 : _1 = iftmp.0_2 == 0;
1868 :
1869 : and for partial ordering <=> something like:
1870 :
1871 : <bb 2> : // cond3_bb
1872 : if (a_3(D) == b_5(D))
1873 : goto <bb 6>; [50.00%]
1874 : else
1875 : goto <bb 3>; [50.00%]
1876 :
1877 : <bb 3> [local count: 536870913]: // cond2_bb
1878 : if (a_3(D) < b_5(D))
1879 : goto <bb 6>; [50.00%]
1880 : else
1881 : goto <bb 4>; [50.00%]
1882 :
1883 : <bb 4> [local count: 268435456]: // cond_bb
1884 : if (a_3(D) > b_5(D))
1885 : goto <bb 6>; [50.00%]
1886 : else
1887 : goto <bb 5>; [50.00%]
1888 :
1889 : <bb 5> [local count: 134217728]: // middle_bb
1890 :
1891 : <bb 6> [local count: 1073741824]: // phi_bb
1892 : # SR.27_4 = PHI <0(2), -1(3), 1(4), -128(5)>
1893 : _2 = SR.27_4 > 0; */
1894 :
1895 : static bool
1896 628518 : spaceship_replacement (basic_block cond_bb, basic_block middle_bb,
1897 : edge e0, edge e1, gphi *phi,
1898 : tree arg0, tree arg1)
1899 : {
1900 628518 : tree phires = gimple_phi_result (phi);
1901 1250117 : if (!INTEGRAL_TYPE_P (TREE_TYPE (phires))
1902 491334 : || TYPE_UNSIGNED (TREE_TYPE (phires))
1903 256021 : || !tree_fits_shwi_p (arg0)
1904 72169 : || !tree_fits_shwi_p (arg1)
1905 41895 : || (!IN_RANGE (tree_to_shwi (arg0), -1, 1)
1906 22334 : && tree_to_shwi (arg0) != -128)
1907 648495 : || (!IN_RANGE (tree_to_shwi (arg1), -1, 1)
1908 2667 : && tree_to_shwi (arg1) != -128))
1909 : return false;
1910 :
1911 17366 : basic_block phi_bb = gimple_bb (phi);
1912 17366 : gcc_assert (phi_bb == e0->dest && phi_bb == e1->dest);
1913 17366 : if (!IN_RANGE (EDGE_COUNT (phi_bb->preds), 3, 4))
1914 : return false;
1915 :
1916 7282 : use_operand_p use_p;
1917 7282 : gimple *use_stmt;
1918 7282 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (phires))
1919 : return false;
1920 7282 : if (!single_imm_use (phires, &use_p, &use_stmt))
1921 : return false;
1922 6612 : enum tree_code cmp;
1923 6612 : tree lhs, rhs;
1924 6612 : gimple *orig_use_stmt = use_stmt;
1925 6612 : tree orig_use_lhs = NULL_TREE;
1926 6612 : tree temps[2] = { NULL_TREE, NULL_TREE };
1927 :
1928 : /* Handle std::partial_ordering::_M_reverse(), i.e.
1929 : _1 = (unsigned char) phires;
1930 : _2 = -_1;
1931 : _3 = (signed char) _2;
1932 : and uses of _3 in comparison instead of phires. */
1933 6612 : if (gimple_assign_cast_p (use_stmt))
1934 : {
1935 251 : orig_use_lhs = gimple_assign_lhs (use_stmt);
1936 251 : temps[0] = orig_use_lhs;
1937 251 : tree ty1 = TREE_TYPE (gimple_assign_rhs1 (use_stmt));
1938 251 : tree ty2 = TREE_TYPE (orig_use_lhs);
1939 :
1940 251 : if (!TYPE_UNSIGNED (ty2) || !INTEGRAL_TYPE_P (ty2))
1941 : return false;
1942 211 : if (TYPE_PRECISION (ty2) != 8 || TYPE_PRECISION (ty1) < 8)
1943 : return false;
1944 92 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
1945 : return false;
1946 92 : if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
1947 : return false;
1948 :
1949 91 : if (!is_gimple_assign (use_stmt)
1950 91 : || gimple_assign_rhs_code (use_stmt) != NEGATE_EXPR)
1951 : return false;
1952 :
1953 88 : orig_use_lhs = gimple_assign_lhs (use_stmt);
1954 88 : temps[1] = orig_use_lhs;
1955 88 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
1956 : return false;
1957 88 : if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
1958 : return false;
1959 :
1960 88 : if (!gimple_assign_cast_p (use_stmt))
1961 : return false;
1962 :
1963 88 : orig_use_lhs = gimple_assign_lhs (use_stmt);
1964 88 : tree ty3 = TREE_TYPE (orig_use_lhs);
1965 :
1966 88 : if (!useless_type_conversion_p (ty3, ty1))
1967 : return false;
1968 88 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
1969 : return false;
1970 88 : if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
1971 : return false;
1972 : }
1973 6449 : if (gimple_code (use_stmt) == GIMPLE_COND)
1974 : {
1975 2381 : cmp = gimple_cond_code (use_stmt);
1976 2381 : lhs = gimple_cond_lhs (use_stmt);
1977 2381 : rhs = gimple_cond_rhs (use_stmt);
1978 : }
1979 4068 : else if (is_gimple_assign (use_stmt))
1980 : {
1981 2308 : if (gimple_assign_rhs_class (use_stmt) == GIMPLE_BINARY_RHS)
1982 : {
1983 1217 : cmp = gimple_assign_rhs_code (use_stmt);
1984 1217 : lhs = gimple_assign_rhs1 (use_stmt);
1985 1217 : rhs = gimple_assign_rhs2 (use_stmt);
1986 : }
1987 1091 : else if (gimple_assign_rhs_code (use_stmt) == COND_EXPR)
1988 : {
1989 0 : tree cond = gimple_assign_rhs1 (use_stmt);
1990 0 : if (!COMPARISON_CLASS_P (cond))
1991 : return false;
1992 0 : cmp = TREE_CODE (cond);
1993 0 : lhs = TREE_OPERAND (cond, 0);
1994 0 : rhs = TREE_OPERAND (cond, 1);
1995 : }
1996 : else
1997 : return false;
1998 : }
1999 : else
2000 : return false;
2001 3598 : switch (cmp)
2002 : {
2003 3127 : case EQ_EXPR:
2004 3127 : case NE_EXPR:
2005 3127 : case LT_EXPR:
2006 3127 : case GT_EXPR:
2007 3127 : case LE_EXPR:
2008 3127 : case GE_EXPR:
2009 3127 : break;
2010 : default:
2011 : return false;
2012 : }
2013 6166 : if (lhs != (orig_use_lhs ? orig_use_lhs : phires)
2014 2786 : || !tree_fits_shwi_p (rhs)
2015 2528 : || !IN_RANGE (tree_to_shwi (rhs), -1, 1))
2016 : return false;
2017 :
2018 2516 : if (!empty_block_p (middle_bb))
2019 : return false;
2020 :
2021 5032 : gcond *cond1 = as_a <gcond *> (*gsi_last_bb (cond_bb));
2022 2516 : enum tree_code cmp1 = gimple_cond_code (cond1);
2023 2516 : switch (cmp1)
2024 : {
2025 2382 : case LT_EXPR:
2026 2382 : case LE_EXPR:
2027 2382 : case GT_EXPR:
2028 2382 : case GE_EXPR:
2029 2382 : break;
2030 : default:
2031 : return false;
2032 : }
2033 2382 : tree lhs1 = gimple_cond_lhs (cond1);
2034 2382 : tree rhs1 = gimple_cond_rhs (cond1);
2035 2382 : if (TREE_CODE (lhs1) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs1))
2036 : return false;
2037 2382 : if (TREE_CODE (rhs1) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1))
2038 : return false;
2039 :
2040 2382 : if (!single_pred_p (cond_bb) || !cond_only_block_p (cond_bb))
2041 11 : return false;
2042 :
2043 2371 : basic_block cond2_bb = single_pred (cond_bb);
2044 2371 : if (EDGE_COUNT (cond2_bb->succs) != 2)
2045 : return false;
2046 2371 : edge cond2_phi_edge;
2047 2371 : if (EDGE_SUCC (cond2_bb, 0)->dest == cond_bb)
2048 : {
2049 1970 : if (EDGE_SUCC (cond2_bb, 1)->dest != phi_bb)
2050 : return false;
2051 : cond2_phi_edge = EDGE_SUCC (cond2_bb, 1);
2052 : }
2053 401 : else if (EDGE_SUCC (cond2_bb, 0)->dest != phi_bb)
2054 : return false;
2055 : else
2056 : cond2_phi_edge = EDGE_SUCC (cond2_bb, 0);
2057 2371 : tree arg2 = gimple_phi_arg_def (phi, cond2_phi_edge->dest_idx);
2058 2371 : if (!tree_fits_shwi_p (arg2))
2059 : return false;
2060 4742 : gcond *cond2 = safe_dyn_cast <gcond *> (*gsi_last_bb (cond2_bb));
2061 2371 : if (!cond2)
2062 : return false;
2063 2371 : enum tree_code cmp2 = gimple_cond_code (cond2);
2064 2371 : tree lhs2 = gimple_cond_lhs (cond2);
2065 2371 : tree rhs2 = gimple_cond_rhs (cond2);
2066 2371 : if (lhs2 == lhs1)
2067 : {
2068 2369 : if (!operand_equal_p (rhs2, rhs1, 0))
2069 : {
2070 327 : if ((cmp2 == EQ_EXPR || cmp2 == NE_EXPR)
2071 327 : && TREE_CODE (rhs1) == INTEGER_CST
2072 327 : && TREE_CODE (rhs2) == INTEGER_CST)
2073 : {
2074 : /* For integers, we can have cond2 x == 5
2075 : and cond1 x < 5, x <= 4, x <= 5, x < 6,
2076 : x > 5, x >= 6, x >= 5 or x > 4. */
2077 327 : if (tree_int_cst_lt (rhs1, rhs2))
2078 : {
2079 327 : if (wi::ne_p (wi::to_wide (rhs1) + 1, wi::to_wide (rhs2)))
2080 : return false;
2081 327 : if (cmp1 == LE_EXPR)
2082 : cmp1 = LT_EXPR;
2083 0 : else if (cmp1 == GT_EXPR)
2084 : cmp1 = GE_EXPR;
2085 : else
2086 : return false;
2087 : }
2088 : else
2089 : {
2090 0 : gcc_checking_assert (tree_int_cst_lt (rhs2, rhs1));
2091 0 : if (wi::ne_p (wi::to_wide (rhs2) + 1, wi::to_wide (rhs1)))
2092 : return false;
2093 0 : if (cmp1 == LT_EXPR)
2094 : cmp1 = LE_EXPR;
2095 0 : else if (cmp1 == GE_EXPR)
2096 : cmp1 = GT_EXPR;
2097 : else
2098 : return false;
2099 : }
2100 : rhs1 = rhs2;
2101 : }
2102 : else
2103 : return false;
2104 : }
2105 : }
2106 2 : else if (lhs2 == rhs1)
2107 : {
2108 0 : if (rhs2 != lhs1)
2109 : return false;
2110 : }
2111 : else
2112 : return false;
2113 :
2114 2369 : tree arg3 = arg2;
2115 2369 : basic_block cond3_bb = cond2_bb;
2116 2369 : edge cond3_phi_edge = cond2_phi_edge;
2117 2369 : gcond *cond3 = cond2;
2118 2369 : enum tree_code cmp3 = cmp2;
2119 2369 : tree lhs3 = lhs2;
2120 2369 : tree rhs3 = rhs2;
2121 2369 : if (EDGE_COUNT (phi_bb->preds) == 4)
2122 : {
2123 405 : if (absu_hwi (tree_to_shwi (arg2)) != 1)
2124 : return false;
2125 397 : if ((cond2_phi_edge->flags & EDGE_FALSE_VALUE)
2126 397 : && HONOR_NANS (TREE_TYPE (lhs1)))
2127 : return false;
2128 397 : if (e1->flags & EDGE_TRUE_VALUE)
2129 : {
2130 397 : if (tree_to_shwi (arg0) != -128
2131 397 : || absu_hwi (tree_to_shwi (arg1)) != 1
2132 794 : || wi::to_widest (arg1) == wi::to_widest (arg2))
2133 0 : return false;
2134 : }
2135 0 : else if (tree_to_shwi (arg1) != -128
2136 0 : || absu_hwi (tree_to_shwi (arg0)) != 1
2137 0 : || wi::to_widest (arg0) == wi::to_widest (arg2))
2138 0 : return false;
2139 397 : switch (cmp2)
2140 : {
2141 397 : case LT_EXPR:
2142 397 : case LE_EXPR:
2143 397 : case GT_EXPR:
2144 397 : case GE_EXPR:
2145 397 : break;
2146 : default:
2147 : return false;
2148 : }
2149 : /* if (x < y) goto phi_bb; else fallthru;
2150 : if (x > y) goto phi_bb; else fallthru;
2151 : bbx:;
2152 : phi_bb:;
2153 : is ok, but if x and y are swapped in one of the comparisons,
2154 : or the comparisons are the same and operands not swapped,
2155 : or the true and false edges are swapped, it is not.
2156 : For HONOR_NANS, the edge flags are irrelevant and the comparisons
2157 : must be different for non-swapped operands and same for swapped
2158 : operands. */
2159 397 : if ((lhs2 == lhs1)
2160 397 : ^ (HONOR_NANS (TREE_TYPE (lhs1))
2161 397 : ? ((cmp2 == LT_EXPR || cmp2 == LE_EXPR)
2162 269 : != (cmp1 == LT_EXPR || cmp1 == LE_EXPR))
2163 128 : : (((cond2_phi_edge->flags
2164 128 : & ((cmp2 == LT_EXPR || cmp2 == LE_EXPR)
2165 128 : ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE)) != 0)
2166 256 : != ((e1->flags
2167 128 : & ((cmp1 == LT_EXPR || cmp1 == LE_EXPR)
2168 128 : ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE)) != 0))))
2169 : return false;
2170 397 : if (!single_pred_p (cond2_bb) || !cond_only_block_p (cond2_bb))
2171 0 : return false;
2172 397 : cond3_bb = single_pred (cond2_bb);
2173 397 : if (EDGE_COUNT (cond2_bb->succs) != 2)
2174 : return false;
2175 397 : if (EDGE_SUCC (cond3_bb, 0)->dest == cond2_bb)
2176 : {
2177 221 : if (EDGE_SUCC (cond3_bb, 1)->dest != phi_bb)
2178 : return false;
2179 : cond3_phi_edge = EDGE_SUCC (cond3_bb, 1);
2180 : }
2181 176 : else if (EDGE_SUCC (cond3_bb, 0)->dest != phi_bb)
2182 : return false;
2183 : else
2184 : cond3_phi_edge = EDGE_SUCC (cond3_bb, 0);
2185 397 : arg3 = gimple_phi_arg_def (phi, cond3_phi_edge->dest_idx);
2186 627043 : cond3 = safe_dyn_cast <gcond *> (*gsi_last_bb (cond3_bb));
2187 397 : if (!cond3)
2188 : return false;
2189 397 : cmp3 = gimple_cond_code (cond3);
2190 397 : lhs3 = gimple_cond_lhs (cond3);
2191 397 : rhs3 = gimple_cond_rhs (cond3);
2192 397 : if (lhs3 == lhs1)
2193 : {
2194 397 : if (!operand_equal_p (rhs3, rhs1, 0))
2195 : return false;
2196 : }
2197 0 : else if (lhs3 == rhs1)
2198 : {
2199 0 : if (rhs3 != lhs1)
2200 : return false;
2201 : }
2202 : else
2203 : return false;
2204 : }
2205 1964 : else if (absu_hwi (tree_to_shwi (arg0)) != 1
2206 1944 : || absu_hwi (tree_to_shwi (arg1)) != 1
2207 3888 : || wi::to_widest (arg0) == wi::to_widest (arg1)
2208 3908 : || HONOR_NANS (TREE_TYPE (lhs1)))
2209 20 : return false;
2210 :
2211 2341 : if (!integer_zerop (arg3) || (cmp3 != EQ_EXPR && cmp3 != NE_EXPR))
2212 : return false;
2213 2341 : if ((cond3_phi_edge->flags & (cmp3 == EQ_EXPR
2214 2341 : ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE)) == 0)
2215 : return false;
2216 :
2217 : /* lhs1 one_cmp rhs1 results in phires of 1. */
2218 2341 : enum tree_code one_cmp;
2219 4682 : if ((cmp1 == LT_EXPR || cmp1 == LE_EXPR)
2220 2413 : ^ (!integer_onep ((e1->flags & EDGE_TRUE_VALUE) ? arg1 : arg0)))
2221 : one_cmp = LT_EXPR;
2222 : else
2223 1736 : one_cmp = GT_EXPR;
2224 :
2225 2341 : enum tree_code res_cmp;
2226 2341 : bool negate_p = false;
2227 2341 : switch (cmp)
2228 : {
2229 1275 : case EQ_EXPR:
2230 1275 : if (integer_zerop (rhs) && !HONOR_NANS (TREE_TYPE (lhs1)))
2231 : res_cmp = EQ_EXPR;
2232 1191 : else if (integer_minus_onep (rhs))
2233 758 : res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
2234 433 : else if (integer_onep (rhs))
2235 : res_cmp = one_cmp;
2236 : else
2237 : return false;
2238 : break;
2239 968 : case NE_EXPR:
2240 968 : if (integer_zerop (rhs) && !HONOR_NANS (TREE_TYPE (lhs1)))
2241 : res_cmp = NE_EXPR;
2242 930 : else if (integer_minus_onep (rhs))
2243 560 : res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
2244 428 : else if (integer_onep (rhs))
2245 639 : res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
2246 : else
2247 : return false;
2248 938 : if (HONOR_NANS (TREE_TYPE (lhs1)))
2249 : negate_p = true;
2250 : break;
2251 27 : case LT_EXPR:
2252 27 : if (integer_onep (rhs))
2253 0 : res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
2254 27 : else if (integer_zerop (rhs))
2255 27 : res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
2256 : else
2257 : return false;
2258 27 : if (HONOR_NANS (TREE_TYPE (lhs1)))
2259 : negate_p = true;
2260 : break;
2261 4 : case LE_EXPR:
2262 4 : if (integer_zerop (rhs))
2263 4 : res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
2264 0 : else if (integer_minus_onep (rhs))
2265 0 : res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
2266 : else
2267 : return false;
2268 4 : if (HONOR_NANS (TREE_TYPE (lhs1)))
2269 : negate_p = true;
2270 : break;
2271 0 : case GT_EXPR:
2272 0 : if (integer_minus_onep (rhs))
2273 0 : res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
2274 0 : else if (integer_zerop (rhs))
2275 : res_cmp = one_cmp;
2276 : else
2277 : return false;
2278 : break;
2279 67 : case GE_EXPR:
2280 67 : if (integer_zerop (rhs))
2281 67 : res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
2282 0 : else if (integer_onep (rhs))
2283 : res_cmp = one_cmp;
2284 : else
2285 : return false;
2286 : break;
2287 0 : default:
2288 0 : gcc_unreachable ();
2289 : }
2290 2269 : if (orig_use_lhs)
2291 88 : res_cmp = swap_tree_comparison (res_cmp);
2292 :
2293 2269 : tree clhs1 = lhs1, crhs1 = rhs1;
2294 2269 : if (negate_p)
2295 : {
2296 48 : if (cfun->can_throw_non_call_exceptions)
2297 0 : return false;
2298 48 : res_cmp = invert_tree_comparison (res_cmp, false);
2299 48 : clhs1 = make_ssa_name (boolean_type_node);
2300 48 : gimple *g = gimple_build_assign (clhs1, res_cmp, lhs1, rhs1);
2301 48 : gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
2302 48 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2303 48 : crhs1 = boolean_false_node;
2304 48 : res_cmp = EQ_EXPR;
2305 : }
2306 :
2307 2269 : if (gimple_code (use_stmt) == GIMPLE_COND)
2308 : {
2309 1641 : gcond *use_cond = as_a <gcond *> (use_stmt);
2310 1641 : gimple_cond_set_code (use_cond, res_cmp);
2311 1641 : gimple_cond_set_lhs (use_cond, clhs1);
2312 1641 : gimple_cond_set_rhs (use_cond, crhs1);
2313 : }
2314 628 : else if (gimple_assign_rhs_class (use_stmt) == GIMPLE_BINARY_RHS)
2315 : {
2316 628 : gimple_assign_set_rhs_code (use_stmt, res_cmp);
2317 628 : gimple_assign_set_rhs1 (use_stmt, clhs1);
2318 628 : gimple_assign_set_rhs2 (use_stmt, crhs1);
2319 : }
2320 : else
2321 : {
2322 0 : tree cond = build2 (res_cmp, TREE_TYPE (gimple_assign_rhs1 (use_stmt)),
2323 : clhs1, crhs1);
2324 0 : gimple_assign_set_rhs1 (use_stmt, cond);
2325 : }
2326 2269 : update_stmt (use_stmt);
2327 :
2328 2269 : if (MAY_HAVE_DEBUG_BIND_STMTS)
2329 : {
2330 1934 : use_operand_p use_p;
2331 1934 : imm_use_iterator iter;
2332 1934 : bool has_debug_uses = false;
2333 1934 : bool has_cast1_debug_uses = false;
2334 1934 : bool has_neg_debug_uses = false;
2335 1934 : bool has_cast2_debug_uses = false;
2336 3912 : FOR_EACH_IMM_USE_FAST (use_p, iter, phires)
2337 : {
2338 1978 : gimple *use_stmt = USE_STMT (use_p);
2339 1978 : if (is_gimple_debug (use_stmt))
2340 : {
2341 : has_debug_uses = true;
2342 : break;
2343 : }
2344 1934 : }
2345 1934 : if (orig_use_lhs)
2346 : {
2347 132 : FOR_EACH_IMM_USE_FAST (use_p, iter, temps[0])
2348 : {
2349 76 : gimple *use_stmt = USE_STMT (use_p);
2350 76 : if (is_gimple_debug (use_stmt))
2351 : {
2352 : has_debug_uses = true;
2353 : has_cast1_debug_uses = true;
2354 : break;
2355 : }
2356 44 : }
2357 132 : FOR_EACH_IMM_USE_FAST (use_p, iter, temps[1])
2358 : {
2359 76 : gimple *use_stmt = USE_STMT (use_p);
2360 76 : if (is_gimple_debug (use_stmt))
2361 : {
2362 : has_debug_uses = true;
2363 : has_cast1_debug_uses = true;
2364 : has_neg_debug_uses = true;
2365 : break;
2366 : }
2367 44 : }
2368 88 : FOR_EACH_IMM_USE_FAST (use_p, iter, orig_use_lhs)
2369 : {
2370 32 : gimple *use_stmt = USE_STMT (use_p);
2371 32 : if (is_gimple_debug (use_stmt))
2372 : {
2373 : has_debug_uses = true;
2374 : has_cast1_debug_uses = true;
2375 : has_neg_debug_uses = true;
2376 : has_cast2_debug_uses = true;
2377 : break;
2378 : }
2379 44 : }
2380 44 : if (has_debug_uses)
2381 : {
2382 44 : gimple_stmt_iterator gsi = gsi_for_stmt (orig_use_stmt);
2383 44 : tree zero = build_zero_cst (TREE_TYPE (temps[0]));
2384 44 : gimple_assign_set_rhs_with_ops (&gsi, INTEGER_CST, zero);
2385 44 : update_stmt (orig_use_stmt);
2386 44 : gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (temps[1]));
2387 44 : zero = build_zero_cst (TREE_TYPE (temps[1]));
2388 44 : gimple_assign_set_rhs_with_ops (&gsi, INTEGER_CST, zero);
2389 44 : update_stmt (SSA_NAME_DEF_STMT (temps[1]));
2390 44 : gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (orig_use_lhs));
2391 44 : zero = build_zero_cst (TREE_TYPE (orig_use_lhs));
2392 44 : gimple_assign_set_rhs_with_ops (&gsi, INTEGER_CST, zero);
2393 44 : update_stmt (SSA_NAME_DEF_STMT (orig_use_lhs));
2394 : }
2395 : }
2396 :
2397 1934 : if (has_debug_uses)
2398 : {
2399 : /* If there are debug uses, emit something like:
2400 : # DEBUG D#1 => i_2(D) > j_3(D) ? 1 : -1
2401 : # DEBUG D#2 => i_2(D) == j_3(D) ? 0 : D#1
2402 : where > stands for the comparison that yielded 1
2403 : and replace debug uses of phi result with that D#2.
2404 : Ignore the value of -128 if !HONOR_NANS, because if NaNs
2405 : aren't expected, all floating point numbers should be
2406 : comparable. If HONOR_NANS, emit something like:
2407 : # DEBUG D#1 => i_2(D) < j_3(D) ? -1 : -128
2408 : # DEBUG D#2 => i_2(D) > j_3(D) ? 1 : D#1
2409 : # DEBUG D#3 => i_2(D) == j_3(D) ? 0 : D#2
2410 : instead. */
2411 1934 : gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi));
2412 1934 : tree type = TREE_TYPE (phires);
2413 1934 : tree minus_one = build_int_cst (type, -1);
2414 1934 : if (HONOR_NANS (TREE_TYPE (lhs1)))
2415 : {
2416 101 : tree temp3 = build_debug_expr_decl (type);
2417 202 : tree t = build2 (one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR,
2418 : boolean_type_node, lhs1, rhs2);
2419 101 : t = build3 (COND_EXPR, type, t, minus_one,
2420 : build_int_cst (type, -128));
2421 101 : gimple *g = gimple_build_debug_bind (temp3, t, phi);
2422 101 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2423 101 : minus_one = temp3;
2424 : }
2425 1934 : tree temp1 = build_debug_expr_decl (type);
2426 1934 : tree t = build2 (one_cmp, boolean_type_node, lhs1, rhs2);
2427 1934 : t = build3 (COND_EXPR, type, t, build_one_cst (type),
2428 : minus_one);
2429 1934 : gimple *g = gimple_build_debug_bind (temp1, t, phi);
2430 1934 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2431 1934 : tree temp2 = build_debug_expr_decl (type);
2432 1934 : t = build2 (EQ_EXPR, boolean_type_node, lhs1, rhs2);
2433 1934 : t = build3 (COND_EXPR, type, t, build_zero_cst (type), temp1);
2434 1934 : g = gimple_build_debug_bind (temp2, t, phi);
2435 1934 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2436 1934 : replace_uses_by (phires, temp2);
2437 1934 : if (has_cast1_debug_uses)
2438 : {
2439 32 : tree temp3 = build_debug_expr_decl (TREE_TYPE (temps[0]));
2440 32 : t = fold_convert (TREE_TYPE (temps[0]), temp2);
2441 32 : g = gimple_build_debug_bind (temp3, t, phi);
2442 32 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2443 32 : replace_uses_by (temps[0], temp3);
2444 32 : temp2 = temp3;
2445 : }
2446 1934 : if (has_neg_debug_uses)
2447 : {
2448 32 : tree temp3 = build_debug_expr_decl (TREE_TYPE (temps[1]));
2449 32 : t = fold_build1 (NEGATE_EXPR, TREE_TYPE (temps[1]), temp2);
2450 32 : g = gimple_build_debug_bind (temp3, t, phi);
2451 32 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2452 32 : replace_uses_by (temps[1], temp3);
2453 32 : temp2 = temp3;
2454 : }
2455 1934 : if (has_cast2_debug_uses)
2456 : {
2457 32 : tree temp3 = build_debug_expr_decl (TREE_TYPE (orig_use_lhs));
2458 32 : t = fold_convert (TREE_TYPE (orig_use_lhs), temp2);
2459 32 : g = gimple_build_debug_bind (temp3, t, phi);
2460 32 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2461 32 : replace_uses_by (orig_use_lhs, temp3);
2462 : }
2463 : }
2464 : }
2465 :
2466 2269 : if (orig_use_lhs)
2467 : {
2468 88 : gimple_stmt_iterator gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (orig_use_lhs));
2469 88 : gsi_remove (&gsi, true);
2470 88 : gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (temps[1]));
2471 88 : gsi_remove (&gsi, true);
2472 88 : gsi = gsi_for_stmt (orig_use_stmt);
2473 88 : gsi_remove (&gsi, true);
2474 88 : release_ssa_name (orig_use_lhs);
2475 88 : release_ssa_name (temps[1]);
2476 88 : release_ssa_name (temps[0]);
2477 : }
2478 :
2479 2269 : gimple_stmt_iterator psi = gsi_for_stmt (phi);
2480 2269 : remove_phi_node (&psi, true);
2481 2269 : statistics_counter_event (cfun, "spaceship replacement", 1);
2482 :
2483 2269 : return true;
2484 : }
2485 :
2486 : /* Optimize x ? __builtin_fun (x) : C, where C is __builtin_fun (0).
2487 : Convert
2488 :
2489 : <bb 2>
2490 : if (b_4(D) != 0)
2491 : goto <bb 3>
2492 : else
2493 : goto <bb 4>
2494 :
2495 : <bb 3>
2496 : _2 = (unsigned long) b_4(D);
2497 : _9 = __builtin_popcountl (_2);
2498 : OR
2499 : _9 = __builtin_popcountl (b_4(D));
2500 :
2501 : <bb 4>
2502 : c_12 = PHI <0(2), _9(3)>
2503 :
2504 : Into
2505 : <bb 2>
2506 : _2 = (unsigned long) b_4(D);
2507 : _9 = __builtin_popcountl (_2);
2508 : OR
2509 : _9 = __builtin_popcountl (b_4(D));
2510 :
2511 : <bb 4>
2512 : c_12 = PHI <_9(2)>
2513 :
2514 : Similarly for __builtin_clz or __builtin_ctz if
2515 : C?Z_DEFINED_VALUE_AT_ZERO is 2, optab is present and
2516 : instead of 0 above it uses the value from that macro. */
2517 :
2518 : static bool
2519 435937 : cond_removal_in_builtin_zero_pattern (basic_block cond_bb,
2520 : basic_block middle_bb,
2521 : edge e1, edge e2, gphi *phi,
2522 : tree arg0, tree arg1)
2523 : {
2524 435937 : gimple_stmt_iterator gsi, gsi_from;
2525 435937 : gimple *call;
2526 435937 : gimple *cast = NULL;
2527 435937 : tree lhs, arg;
2528 :
2529 : /* Check that
2530 : _2 = (unsigned long) b_4(D);
2531 : _9 = __builtin_popcountl (_2);
2532 : OR
2533 : _9 = __builtin_popcountl (b_4(D));
2534 : are the only stmts in the middle_bb. */
2535 :
2536 435937 : gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
2537 435937 : if (gsi_end_p (gsi))
2538 : return false;
2539 268828 : cast = gsi_stmt (gsi);
2540 268828 : gsi_next_nondebug (&gsi);
2541 268828 : if (!gsi_end_p (gsi))
2542 : {
2543 137943 : call = gsi_stmt (gsi);
2544 137943 : gsi_next_nondebug (&gsi);
2545 137943 : if (!gsi_end_p (gsi))
2546 : return false;
2547 : }
2548 : else
2549 : {
2550 : call = cast;
2551 : cast = NULL;
2552 : }
2553 :
2554 : /* Check that we have a popcount/clz/ctz builtin. */
2555 178465 : if (!is_gimple_call (call))
2556 : return false;
2557 :
2558 5521 : lhs = gimple_get_lhs (call);
2559 :
2560 5521 : if (lhs == NULL_TREE)
2561 : return false;
2562 :
2563 5495 : combined_fn cfn = gimple_call_combined_fn (call);
2564 5495 : if (gimple_call_num_args (call) != 1
2565 5495 : && (gimple_call_num_args (call) != 2
2566 : || cfn == CFN_CLZ
2567 585 : || cfn == CFN_CTZ))
2568 : return false;
2569 :
2570 3989 : arg = gimple_call_arg (call, 0);
2571 :
2572 3989 : internal_fn ifn = IFN_LAST;
2573 3989 : int val = 0;
2574 3989 : bool any_val = false;
2575 3989 : switch (cfn)
2576 : {
2577 : case CFN_BUILT_IN_BSWAP16:
2578 : case CFN_BUILT_IN_BSWAP32:
2579 : case CFN_BUILT_IN_BSWAP64:
2580 : case CFN_BUILT_IN_BSWAP128:
2581 : CASE_CFN_FFS:
2582 : CASE_CFN_PARITY:
2583 : CASE_CFN_POPCOUNT:
2584 : break;
2585 694 : CASE_CFN_CLZ:
2586 694 : if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
2587 : {
2588 694 : tree type = TREE_TYPE (arg);
2589 694 : if (TREE_CODE (type) == BITINT_TYPE)
2590 : {
2591 4 : if (gimple_call_num_args (call) == 1)
2592 : {
2593 : any_val = true;
2594 : ifn = IFN_CLZ;
2595 : break;
2596 : }
2597 0 : if (!tree_fits_shwi_p (gimple_call_arg (call, 1)))
2598 : return false;
2599 0 : HOST_WIDE_INT at_zero = tree_to_shwi (gimple_call_arg (call, 1));
2600 0 : if ((int) at_zero != at_zero)
2601 : return false;
2602 0 : ifn = IFN_CLZ;
2603 0 : val = at_zero;
2604 0 : break;
2605 : }
2606 690 : if (direct_internal_fn_supported_p (IFN_CLZ, type, OPTIMIZE_FOR_BOTH)
2607 1355 : && CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type),
2608 : val) == 2)
2609 : {
2610 : ifn = IFN_CLZ;
2611 : break;
2612 : }
2613 : }
2614 : return false;
2615 263 : CASE_CFN_CTZ:
2616 263 : if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
2617 : {
2618 263 : tree type = TREE_TYPE (arg);
2619 263 : if (TREE_CODE (type) == BITINT_TYPE)
2620 : {
2621 4 : if (gimple_call_num_args (call) == 1)
2622 : {
2623 : any_val = true;
2624 : ifn = IFN_CTZ;
2625 : break;
2626 : }
2627 0 : if (!tree_fits_shwi_p (gimple_call_arg (call, 1)))
2628 : return false;
2629 0 : HOST_WIDE_INT at_zero = tree_to_shwi (gimple_call_arg (call, 1));
2630 0 : if ((int) at_zero != at_zero)
2631 : return false;
2632 0 : ifn = IFN_CTZ;
2633 0 : val = at_zero;
2634 0 : break;
2635 : }
2636 259 : if (direct_internal_fn_supported_p (IFN_CTZ, type, OPTIMIZE_FOR_BOTH)
2637 497 : && CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type),
2638 : val) == 2)
2639 : {
2640 : ifn = IFN_CTZ;
2641 : break;
2642 : }
2643 : }
2644 : return false;
2645 3 : case CFN_BUILT_IN_CLRSB:
2646 3 : val = TYPE_PRECISION (integer_type_node) - 1;
2647 3 : break;
2648 3 : case CFN_BUILT_IN_CLRSBL:
2649 3 : val = TYPE_PRECISION (long_integer_type_node) - 1;
2650 3 : break;
2651 3 : case CFN_BUILT_IN_CLRSBLL:
2652 3 : val = TYPE_PRECISION (long_long_integer_type_node) - 1;
2653 3 : break;
2654 : default:
2655 : return false;
2656 : }
2657 :
2658 142 : if (cast)
2659 : {
2660 : /* We have a cast stmt feeding popcount/clz/ctz builtin. */
2661 : /* Check that we have a cast prior to that. */
2662 54 : if (gimple_code (cast) != GIMPLE_ASSIGN
2663 54 : || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (cast)))
2664 : return false;
2665 : /* Result of the cast stmt is the argument to the builtin. */
2666 24 : if (arg != gimple_assign_lhs (cast))
2667 : return false;
2668 24 : arg = gimple_assign_rhs1 (cast);
2669 : }
2670 :
2671 224 : gcond *cond = dyn_cast <gcond *> (*gsi_last_bb (cond_bb));
2672 :
2673 : /* Cond_bb has a check for b_4 [!=|==] 0 before calling the popcount/clz/ctz
2674 : builtin. */
2675 112 : if (!cond
2676 112 : || (gimple_cond_code (cond) != NE_EXPR
2677 20 : && gimple_cond_code (cond) != EQ_EXPR)
2678 112 : || !integer_zerop (gimple_cond_rhs (cond))
2679 112 : || arg != gimple_cond_lhs (cond))
2680 78 : return false;
2681 :
2682 34 : edge true_edge, false_edge;
2683 : /* We need to know which is the true edge and which is the false
2684 : edge so that we know when to invert the condition below. */
2685 34 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
2686 :
2687 : /* Forward the edges over the middle basic block. */
2688 34 : if (true_edge->dest == middle_bb)
2689 34 : true_edge = EDGE_SUCC (true_edge->dest, 0);
2690 34 : if (false_edge->dest == middle_bb)
2691 0 : false_edge = EDGE_SUCC (false_edge->dest, 0);
2692 :
2693 : /* Canonicalize the args with respect to the edges,
2694 : arg0 is from the true edge and arg1 is from the
2695 : false edge.
2696 : That is `cond ? arg0 : arg1`.*/
2697 34 : if (true_edge == e1)
2698 34 : gcc_assert (false_edge == e2);
2699 : else
2700 : {
2701 0 : gcc_assert (false_edge == e1);
2702 0 : gcc_assert (true_edge == e2);
2703 : std::swap (arg0, arg1);
2704 : }
2705 :
2706 : /* Canonicalize the args such that we get:
2707 : `arg != 0 ? arg0 : arg1`. So swap arg0/arg1
2708 : around if cond was an equals. */
2709 34 : if (gimple_cond_code (cond) == EQ_EXPR)
2710 2 : std::swap (arg0, arg1);
2711 :
2712 : /* Check PHI arguments. */
2713 34 : if (lhs != arg0
2714 32 : || TREE_CODE (arg1) != INTEGER_CST)
2715 : return false;
2716 24 : if (any_val)
2717 : {
2718 0 : if (!tree_fits_shwi_p (arg1))
2719 : return false;
2720 0 : HOST_WIDE_INT at_zero = tree_to_shwi (arg1);
2721 0 : if ((int) at_zero != at_zero)
2722 : return false;
2723 0 : val = at_zero;
2724 : }
2725 24 : else if (wi::to_wide (arg1) != val)
2726 : return false;
2727 :
2728 : /* And insert the popcount/clz/ctz builtin and cast stmt before the
2729 : cond_bb. */
2730 13 : gsi = gsi_last_bb (cond_bb);
2731 13 : if (cast)
2732 : {
2733 13 : gsi_from = gsi_for_stmt (cast);
2734 13 : gsi_move_before (&gsi_from, &gsi);
2735 13 : reset_flow_sensitive_info (gimple_get_lhs (cast));
2736 : }
2737 13 : gsi_from = gsi_for_stmt (call);
2738 13 : if (ifn == IFN_LAST
2739 13 : || (gimple_call_internal_p (call) && gimple_call_num_args (call) == 2))
2740 8 : gsi_move_before (&gsi_from, &gsi);
2741 : else
2742 : {
2743 : /* For __builtin_c[lt]z* force .C[LT]Z ifn, because only
2744 : the latter is well defined at zero. */
2745 5 : call = gimple_build_call_internal (ifn, 2, gimple_call_arg (call, 0),
2746 5 : build_int_cst (integer_type_node, val));
2747 5 : gimple_call_set_lhs (call, lhs);
2748 5 : gsi_insert_before (&gsi, call, GSI_SAME_STMT);
2749 5 : gsi_remove (&gsi_from, true);
2750 : }
2751 13 : reset_flow_sensitive_info (lhs);
2752 :
2753 : /* Now update the PHI and remove unneeded bbs. */
2754 13 : replace_phi_edge_with_variable (cond_bb, e2, phi, lhs);
2755 13 : return true;
2756 : }
2757 :
2758 : /* Auxiliary functions to determine the set of memory accesses which
2759 : can't trap because they are preceded by accesses to the same memory
2760 : portion. We do that for MEM_REFs, so we only need to track
2761 : the SSA_NAME of the pointer indirectly referenced. The algorithm
2762 : simply is a walk over all instructions in dominator order. When
2763 : we see an MEM_REF we determine if we've already seen a same
2764 : ref anywhere up to the root of the dominator tree. If we do the
2765 : current access can't trap. If we don't see any dominating access
2766 : the current access might trap, but might also make later accesses
2767 : non-trapping, so we remember it. We need to be careful with loads
2768 : or stores, for instance a load might not trap, while a store would,
2769 : so if we see a dominating read access this doesn't mean that a later
2770 : write access would not trap. Hence we also need to differentiate the
2771 : type of access(es) seen.
2772 :
2773 : ??? We currently are very conservative and assume that a load might
2774 : trap even if a store doesn't (write-only memory). This probably is
2775 : overly conservative.
2776 :
2777 : We currently support a special case that for !TREE_ADDRESSABLE automatic
2778 : variables, it could ignore whether something is a load or store because the
2779 : local stack should be always writable. */
2780 :
2781 : /* A hash-table of references (MEM_REF/ARRAY_REF/COMPONENT_REF), and in which
2782 : basic block an *_REF through it was seen, which would constitute a
2783 : no-trap region for same accesses.
2784 :
2785 : Size is needed to support 2 MEM_REFs of different types, like
2786 : MEM<double>(s_1) and MEM<long>(s_1), which would compare equal with
2787 : OEP_ADDRESS_OF. */
2788 : struct ref_to_bb
2789 : {
2790 : tree exp;
2791 : HOST_WIDE_INT size;
2792 : unsigned int phase;
2793 : basic_block bb;
2794 : };
2795 :
2796 : /* Hashtable helpers. */
2797 :
2798 : struct refs_hasher : free_ptr_hash<ref_to_bb>
2799 : {
2800 : static inline hashval_t hash (const ref_to_bb *);
2801 : static inline bool equal (const ref_to_bb *, const ref_to_bb *);
2802 : };
2803 :
2804 : /* Used for quick clearing of the hash-table when we see calls.
2805 : Hash entries with phase < nt_call_phase are invalid. */
2806 : static unsigned int nt_call_phase;
2807 :
2808 : /* The hash function. */
2809 :
2810 : inline hashval_t
2811 19436820 : refs_hasher::hash (const ref_to_bb *n)
2812 : {
2813 19436820 : inchash::hash hstate;
2814 19436820 : inchash::add_expr (n->exp, hstate, OEP_ADDRESS_OF);
2815 19436820 : hstate.add_hwi (n->size);
2816 19436820 : return hstate.end ();
2817 : }
2818 :
2819 : /* The equality function of *P1 and *P2. */
2820 :
2821 : inline bool
2822 14167839 : refs_hasher::equal (const ref_to_bb *n1, const ref_to_bb *n2)
2823 : {
2824 14167839 : return operand_equal_p (n1->exp, n2->exp, OEP_ADDRESS_OF)
2825 14167839 : && n1->size == n2->size;
2826 : }
2827 :
2828 : class nontrapping_dom_walker : public dom_walker
2829 : {
2830 : public:
2831 1041396 : nontrapping_dom_walker (cdi_direction direction, hash_set<tree> *ps)
2832 1041396 : : dom_walker (direction), m_nontrapping (ps), m_seen_refs (128)
2833 1041396 : {}
2834 :
2835 : edge before_dom_children (basic_block) final override;
2836 : void after_dom_children (basic_block) final override;
2837 :
2838 : private:
2839 :
2840 : /* We see the expression EXP in basic block BB. If it's an interesting
2841 : expression (an MEM_REF through an SSA_NAME) possibly insert the
2842 : expression into the set NONTRAP or the hash table of seen expressions.
2843 : STORE is true if this expression is on the LHS, otherwise it's on
2844 : the RHS. */
2845 : void add_or_mark_expr (basic_block, tree, bool);
2846 :
2847 : hash_set<tree> *m_nontrapping;
2848 :
2849 : /* The hash table for remembering what we've seen. */
2850 : hash_table<refs_hasher> m_seen_refs;
2851 : };
2852 :
2853 : /* Called by walk_dominator_tree, when entering the block BB. */
2854 : edge
2855 11615164 : nontrapping_dom_walker::before_dom_children (basic_block bb)
2856 : {
2857 11615164 : edge e;
2858 11615164 : edge_iterator ei;
2859 11615164 : gimple_stmt_iterator gsi;
2860 :
2861 : /* If we haven't seen all our predecessors, clear the hash-table. */
2862 25516825 : FOR_EACH_EDGE (e, ei, bb->preds)
2863 14588718 : if ((((size_t)e->src->aux) & 2) == 0)
2864 : {
2865 687057 : nt_call_phase++;
2866 687057 : break;
2867 : }
2868 :
2869 : /* Mark this BB as being on the path to dominator root and as visited. */
2870 11615164 : bb->aux = (void*)(1 | 2);
2871 :
2872 : /* And walk the statements in order. */
2873 101813262 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2874 : {
2875 78582934 : gimple *stmt = gsi_stmt (gsi);
2876 :
2877 78582934 : if ((gimple_code (stmt) == GIMPLE_ASM && gimple_vdef (stmt))
2878 78626081 : || (is_gimple_call (stmt)
2879 5520275 : && (!nonfreeing_call_p (stmt) || !nonbarrier_call_p (stmt))))
2880 4936373 : nt_call_phase++;
2881 88510570 : else if (gimple_assign_single_p (stmt) && !gimple_has_volatile_ops (stmt))
2882 : {
2883 13029054 : add_or_mark_expr (bb, gimple_assign_lhs (stmt), true);
2884 13029054 : add_or_mark_expr (bb, gimple_assign_rhs1 (stmt), false);
2885 : }
2886 : }
2887 11615164 : return NULL;
2888 : }
2889 :
2890 : /* Called by walk_dominator_tree, when basic block BB is exited. */
2891 : void
2892 11615164 : nontrapping_dom_walker::after_dom_children (basic_block bb)
2893 : {
2894 : /* This BB isn't on the path to dominator root anymore. */
2895 11615164 : bb->aux = (void*)2;
2896 11615164 : }
2897 :
2898 : /* We see the expression EXP in basic block BB. If it's an interesting
2899 : expression of:
2900 : 1) MEM_REF
2901 : 2) ARRAY_REF
2902 : 3) COMPONENT_REF
2903 : possibly insert the expression into the set NONTRAP or the hash table
2904 : of seen expressions. STORE is true if this expression is on the LHS,
2905 : otherwise it's on the RHS. */
2906 : void
2907 26058108 : nontrapping_dom_walker::add_or_mark_expr (basic_block bb, tree exp, bool store)
2908 : {
2909 26058108 : HOST_WIDE_INT size;
2910 :
2911 26058108 : if ((TREE_CODE (exp) == MEM_REF || TREE_CODE (exp) == ARRAY_REF
2912 21839470 : || TREE_CODE (exp) == COMPONENT_REF)
2913 33149443 : && (size = int_size_in_bytes (TREE_TYPE (exp))) > 0)
2914 : {
2915 11309968 : struct ref_to_bb map;
2916 11309968 : ref_to_bb **slot;
2917 11309968 : struct ref_to_bb *r2bb;
2918 11309968 : basic_block found_bb = 0;
2919 :
2920 11309968 : if (!store)
2921 : {
2922 5218050 : tree base = get_base_address (exp);
2923 : /* Only record a LOAD of a local variable without address-taken, as
2924 : the local stack is always writable. This allows cselim on a STORE
2925 : with a dominating LOAD. */
2926 5218050 : if (!auto_var_p (base) || TREE_ADDRESSABLE (base))
2927 4251973 : return;
2928 : }
2929 :
2930 : /* Try to find the last seen *_REF, which can trap. */
2931 7057995 : map.exp = exp;
2932 7057995 : map.size = size;
2933 7057995 : slot = m_seen_refs.find_slot (&map, INSERT);
2934 7057995 : r2bb = *slot;
2935 7057995 : if (r2bb && r2bb->phase >= nt_call_phase)
2936 293961 : found_bb = r2bb->bb;
2937 :
2938 : /* If we've found a trapping *_REF, _and_ it dominates EXP
2939 : (it's in a basic block on the path from us to the dominator root)
2940 : then we can't trap. */
2941 293961 : if (found_bb && (((size_t)found_bb->aux) & 1) == 1)
2942 : {
2943 79895 : m_nontrapping->add (exp);
2944 : }
2945 : else
2946 : {
2947 : /* EXP might trap, so insert it into the hash table. */
2948 6978100 : if (r2bb)
2949 : {
2950 980989 : r2bb->phase = nt_call_phase;
2951 980989 : r2bb->bb = bb;
2952 : }
2953 : else
2954 : {
2955 5997111 : r2bb = XNEW (struct ref_to_bb);
2956 5997111 : r2bb->phase = nt_call_phase;
2957 5997111 : r2bb->bb = bb;
2958 5997111 : r2bb->exp = exp;
2959 5997111 : r2bb->size = size;
2960 5997111 : *slot = r2bb;
2961 : }
2962 : }
2963 : }
2964 : }
2965 :
2966 : /* This is the entry point of gathering non trapping memory accesses.
2967 : It will do a dominator walk over the whole function, and it will
2968 : make use of the bb->aux pointers. It returns a set of trees
2969 : (the MEM_REFs itself) which can't trap. */
2970 : static hash_set<tree> *
2971 1041396 : get_non_trapping (void)
2972 : {
2973 1041396 : nt_call_phase = 0;
2974 1041396 : hash_set<tree> *nontrap = new hash_set<tree>;
2975 :
2976 2082792 : nontrapping_dom_walker (CDI_DOMINATORS, nontrap)
2977 1041396 : .walk (cfun->cfg->x_entry_block_ptr);
2978 :
2979 1041396 : clear_aux_for_blocks ();
2980 1041396 : return nontrap;
2981 : }
2982 :
2983 : /* Do the main work of conditional store replacement. We already know
2984 : that the recognized pattern looks like so:
2985 :
2986 : split:
2987 : if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
2988 : MIDDLE_BB:
2989 : something
2990 : fallthrough (edge E0)
2991 : JOIN_BB:
2992 : some more
2993 :
2994 : We check that MIDDLE_BB contains only one store, that that store
2995 : doesn't trap (not via NOTRAP, but via checking if an access to the same
2996 : memory location dominates us, or the store is to a local addressable
2997 : object) and that the store has a "simple" RHS. */
2998 :
2999 : static bool
3000 426992 : cond_store_replacement (basic_block middle_bb, basic_block join_bb,
3001 : edge e0, edge e1, hash_set<tree> *nontrap)
3002 : {
3003 426992 : gimple *assign = last_and_only_stmt (middle_bb);
3004 426992 : tree lhs, rhs, name, name2;
3005 426992 : gphi *newphi;
3006 426992 : gassign *new_stmt;
3007 426992 : gimple_stmt_iterator gsi;
3008 426992 : location_t locus;
3009 :
3010 : /* Check if middle_bb contains of only one store. */
3011 426992 : if (!assign
3012 173826 : || !gimple_assign_single_p (assign)
3013 458301 : || gimple_has_volatile_ops (assign))
3014 : return false;
3015 :
3016 : /* And no PHI nodes so all uses in the single stmt are also
3017 : available where we insert to. */
3018 31047 : if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
3019 : return false;
3020 :
3021 30914 : locus = gimple_location (assign);
3022 30914 : lhs = gimple_assign_lhs (assign);
3023 30914 : rhs = gimple_assign_rhs1 (assign);
3024 30914 : if ((!REFERENCE_CLASS_P (lhs)
3025 30914 : && !DECL_P (lhs))
3026 30914 : || !is_gimple_reg_type (TREE_TYPE (lhs)))
3027 : return false;
3028 :
3029 : /* Prove that we can move the store down. We could also check
3030 : TREE_THIS_NOTRAP here, but in that case we also could move stores,
3031 : whose value is not available readily, which we want to avoid. */
3032 17605 : if (!nontrap->contains (lhs))
3033 : {
3034 : /* If LHS is an access to a local variable without address-taken
3035 : (or when we allow data races) and known not to trap, we could
3036 : always safely move down the store. */
3037 11945 : tree base;
3038 11945 : if (ref_can_have_store_data_races (lhs)
3039 333 : || tree_could_trap_p (lhs)
3040 : /* tree_could_trap_p is a predicate for rvalues, so check
3041 : for readonly memory explicitly. */
3042 12159 : || ((base = get_base_address (lhs))
3043 214 : && ((DECL_P (base)
3044 207 : && TREE_READONLY (base))
3045 209 : || TREE_CODE (base) == STRING_CST)))
3046 11742 : return false;
3047 : }
3048 :
3049 : /* Now we've checked the constraints, so do the transformation:
3050 : 1) Remove the single store. */
3051 5863 : gsi = gsi_for_stmt (assign);
3052 5863 : unlink_stmt_vdef (assign);
3053 5863 : gsi_remove (&gsi, true);
3054 5863 : release_defs (assign);
3055 :
3056 : /* Make both store and load use alias-set zero as we have to
3057 : deal with the case of the store being a conditional change
3058 : of the dynamic type. */
3059 5863 : lhs = unshare_expr (lhs);
3060 5863 : tree *basep = &lhs;
3061 11774 : while (handled_component_p (*basep))
3062 5911 : basep = &TREE_OPERAND (*basep, 0);
3063 5863 : if (TREE_CODE (*basep) == MEM_REF
3064 5863 : || TREE_CODE (*basep) == TARGET_MEM_REF)
3065 585 : TREE_OPERAND (*basep, 1)
3066 1170 : = fold_convert (ptr_type_node, TREE_OPERAND (*basep, 1));
3067 : else
3068 5278 : *basep = build2 (MEM_REF, TREE_TYPE (*basep),
3069 : build_fold_addr_expr (*basep),
3070 : build_zero_cst (ptr_type_node));
3071 :
3072 : /* 2) Insert a load from the memory of the store to the temporary
3073 : on the edge which did not contain the store. */
3074 5863 : name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3075 5863 : new_stmt = gimple_build_assign (name, lhs);
3076 5863 : gimple_set_location (new_stmt, locus);
3077 5863 : lhs = unshare_expr (lhs);
3078 5863 : {
3079 : /* Set the no-warning bit on the rhs of the load to avoid uninit
3080 : warnings. */
3081 5863 : tree rhs1 = gimple_assign_rhs1 (new_stmt);
3082 5863 : suppress_warning (rhs1, OPT_Wuninitialized);
3083 : }
3084 5863 : gsi_insert_on_edge (e1, new_stmt);
3085 :
3086 : /* 3) Create a PHI node at the join block, with one argument
3087 : holding the old RHS, and the other holding the temporary
3088 : where we stored the old memory contents. */
3089 5863 : name2 = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3090 5863 : newphi = create_phi_node (name2, join_bb);
3091 5863 : add_phi_arg (newphi, rhs, e0, locus);
3092 5863 : add_phi_arg (newphi, name, e1, locus);
3093 :
3094 5863 : new_stmt = gimple_build_assign (lhs, gimple_phi_result (newphi));
3095 :
3096 : /* 4) Insert that PHI node. */
3097 5863 : gsi = gsi_after_labels (join_bb);
3098 5863 : if (gsi_end_p (gsi))
3099 : {
3100 25 : gsi = gsi_last_bb (join_bb);
3101 25 : gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
3102 : }
3103 : else
3104 5838 : gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
3105 :
3106 5863 : if (dump_file && (dump_flags & TDF_DETAILS))
3107 : {
3108 7 : fprintf (dump_file, "\nConditional store replacement happened!");
3109 7 : fprintf (dump_file, "\nReplaced the store with a load.");
3110 7 : fprintf (dump_file, "\nInserted a new PHI statement in joint block:\n");
3111 7 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_VOPS|TDF_MEMSYMS);
3112 : }
3113 5863 : statistics_counter_event (cfun, "conditional store replacement", 1);
3114 :
3115 5863 : return true;
3116 : }
3117 :
3118 : /* Do the main work of conditional store replacement. */
3119 :
3120 : static bool
3121 824763 : cond_if_else_store_replacement_1 (basic_block then_bb, basic_block else_bb,
3122 : basic_block join_bb, gimple *then_assign,
3123 : gimple *else_assign,
3124 : gphi *vphi)
3125 : {
3126 824763 : tree lhs_base, lhs, then_rhs, else_rhs, name;
3127 824763 : location_t then_locus, else_locus;
3128 824763 : gimple_stmt_iterator gsi;
3129 824763 : gphi *newphi = nullptr;
3130 824763 : gassign *new_stmt;
3131 :
3132 824763 : if (then_assign == NULL
3133 824763 : || !gimple_assign_single_p (then_assign)
3134 756342 : || else_assign == NULL
3135 756342 : || !gimple_assign_single_p (else_assign)
3136 84286 : || stmt_references_abnormal_ssa_name (then_assign)
3137 909035 : || stmt_references_abnormal_ssa_name (else_assign))
3138 740491 : return false;
3139 :
3140 : /* Allow both being clobbers but no other volatile operations. */
3141 84272 : if (gimple_clobber_p (then_assign)
3142 84272 : && gimple_clobber_p (else_assign))
3143 : ;
3144 152144 : else if (gimple_has_volatile_ops (then_assign)
3145 152144 : || gimple_has_volatile_ops (else_assign))
3146 : return false;
3147 :
3148 81311 : lhs = gimple_assign_lhs (then_assign);
3149 81311 : if (!operand_equal_p (lhs, gimple_assign_lhs (else_assign), 0))
3150 : return false;
3151 :
3152 30392 : lhs_base = get_base_address (lhs);
3153 30392 : if (lhs_base == NULL_TREE
3154 30392 : || (!DECL_P (lhs_base) && TREE_CODE (lhs_base) != MEM_REF))
3155 : return false;
3156 :
3157 30345 : then_rhs = gimple_assign_rhs1 (then_assign);
3158 30345 : else_rhs = gimple_assign_rhs1 (else_assign);
3159 30345 : then_locus = gimple_location (then_assign);
3160 30345 : else_locus = gimple_location (else_assign);
3161 :
3162 30345 : if (!is_gimple_reg_type (TREE_TYPE (lhs)))
3163 : {
3164 : /* Handle clobbers seperately as operand_equal_p does not check
3165 : the kind of the clobbers being the same. */
3166 5218 : if (TREE_CLOBBER_P (then_rhs) && TREE_CLOBBER_P (else_rhs))
3167 : {
3168 1774 : if (CLOBBER_KIND (then_rhs) != CLOBBER_KIND (else_rhs))
3169 : return false;
3170 : }
3171 3444 : else if (!operand_equal_p (then_rhs, else_rhs))
3172 : return false;
3173 : /* Currently only handle commoning of `= {}`. */
3174 2229 : if (TREE_CODE (then_rhs) != CONSTRUCTOR)
3175 : return false;
3176 : }
3177 :
3178 26972 : if (dump_file && (dump_flags & TDF_DETAILS))
3179 : {
3180 7 : if (TREE_CLOBBER_P (then_rhs))
3181 3 : fprintf(dump_file, "factoring out clobber:\n\tthen:\n");
3182 : else
3183 4 : fprintf(dump_file, "factoring out stores:\n\tthen:\n");
3184 7 : print_gimple_stmt (dump_file, then_assign, 0,
3185 : TDF_VOPS|TDF_MEMSYMS);
3186 7 : fprintf(dump_file, "\telse:\n");
3187 7 : print_gimple_stmt (dump_file, else_assign, 0,
3188 : TDF_VOPS|TDF_MEMSYMS);
3189 7 : fprintf (dump_file, "\n");
3190 : }
3191 :
3192 : /* Now we've checked the constraints, so do the transformation:
3193 : 1) Remove the stores. */
3194 26972 : gsi = gsi_for_stmt (then_assign);
3195 26972 : unlink_stmt_vdef (then_assign);
3196 26972 : gsi_remove (&gsi, true);
3197 26972 : release_defs (then_assign);
3198 :
3199 26972 : gsi = gsi_for_stmt (else_assign);
3200 26972 : unlink_stmt_vdef (else_assign);
3201 26972 : gsi_remove (&gsi, true);
3202 26972 : release_defs (else_assign);
3203 :
3204 : /* 2) Create a PHI node at the join block, with one argument
3205 : holding the old RHS, and the other holding the temporary
3206 : where we stored the old memory contents. */
3207 26972 : if (operand_equal_p (then_rhs, else_rhs))
3208 : name = then_rhs;
3209 : else
3210 : {
3211 23365 : name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3212 23365 : newphi = create_phi_node (name, join_bb);
3213 23365 : add_phi_arg (newphi, then_rhs, EDGE_SUCC (then_bb, 0), then_locus);
3214 23365 : add_phi_arg (newphi, else_rhs, EDGE_SUCC (else_bb, 0), else_locus);
3215 : }
3216 :
3217 26972 : new_stmt = gimple_build_assign (lhs, name);
3218 : /* Update the vdef for the new store statement. */
3219 26972 : tree newvphilhs = make_ssa_name (gimple_vop (cfun));
3220 26972 : tree vdef = gimple_phi_result (vphi);
3221 26972 : gimple_set_vuse (new_stmt, newvphilhs);
3222 26972 : gimple_set_vdef (new_stmt, vdef);
3223 26972 : gimple_phi_set_result (vphi, newvphilhs);
3224 26972 : SSA_NAME_DEF_STMT (vdef) = new_stmt;
3225 26972 : update_stmt (vphi);
3226 26972 : if (dump_file && (dump_flags & TDF_DETAILS))
3227 : {
3228 7 : if (newphi)
3229 : {
3230 3 : fprintf(dump_file, "to use phi:\n");
3231 3 : print_gimple_stmt (dump_file, newphi, 0,
3232 : TDF_VOPS|TDF_MEMSYMS);
3233 3 : fprintf(dump_file, "\n");
3234 : }
3235 : else
3236 4 : fprintf(dump_file, "to:\n");
3237 7 : print_gimple_stmt (dump_file, new_stmt, 0,
3238 : TDF_VOPS|TDF_MEMSYMS);
3239 7 : fprintf(dump_file, "\n\n");
3240 : }
3241 :
3242 : /* 3) Insert that new store. */
3243 26972 : gsi = gsi_after_labels (join_bb);
3244 26972 : if (gsi_end_p (gsi))
3245 : {
3246 86 : gsi = gsi_last_bb (join_bb);
3247 86 : gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
3248 : }
3249 : else
3250 26886 : gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
3251 :
3252 26972 : statistics_counter_event (cfun, "if-then-else store replacement", 1);
3253 :
3254 26972 : return true;
3255 : }
3256 :
3257 : /* Return the last store in BB with VDEF or NULL if there are
3258 : loads following the store. VPHI is where the only use of the
3259 : vdef should be. If ONLYONESTORE is true, then the store is
3260 : the only store in the BB. */
3261 :
3262 : static gimple *
3263 1759808 : trailing_store_in_bb (basic_block bb, tree vdef, gphi *vphi, bool onlyonestore)
3264 : {
3265 1759808 : if (SSA_NAME_IS_DEFAULT_DEF (vdef))
3266 : return NULL;
3267 1736306 : gimple *store = SSA_NAME_DEF_STMT (vdef);
3268 1736306 : if (gimple_bb (store) != bb
3269 1736306 : || gimple_code (store) == GIMPLE_PHI)
3270 : return NULL;
3271 :
3272 : /* Verify there is no other store in this BB if requested. */
3273 1696601 : if (onlyonestore
3274 24831 : && !SSA_NAME_IS_DEFAULT_DEF (gimple_vuse (store))
3275 23559 : && gimple_bb (SSA_NAME_DEF_STMT (gimple_vuse (store))) == bb
3276 1704419 : && gimple_code (SSA_NAME_DEF_STMT (gimple_vuse (store))) != GIMPLE_PHI)
3277 : return NULL;
3278 :
3279 :
3280 : /* Verify there is no load or store after the store, the vdef of the store
3281 : should only be used by the vphi joining the 2 bbs. */
3282 1688789 : use_operand_p use_p;
3283 1688789 : gimple *use_stmt;
3284 3377578 : if (!single_imm_use (gimple_vdef (store), &use_p, &use_stmt))
3285 : return NULL;
3286 1667330 : if (use_stmt != vphi)
3287 : return NULL;
3288 :
3289 : return store;
3290 : }
3291 :
3292 : /* Limited Conditional store replacement. We already know
3293 : that the recognized pattern looks like so:
3294 :
3295 : split:
3296 : if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
3297 : THEN_BB:
3298 : ...
3299 : STORE = Y;
3300 : ...
3301 : goto JOIN_BB;
3302 : ELSE_BB:
3303 : ...
3304 : STORE = Z;
3305 : ...
3306 : fallthrough (edge E0)
3307 : JOIN_BB:
3308 : some more
3309 :
3310 : Handles only the case with store in THEN_BB and ELSE_BB. That is
3311 : cheap enough due to in phiopt and not worry about heurstics. Moving the store
3312 : out might provide an opportunity for a phiopt to happen.
3313 : At -O1 (!flag_expensive_optimizations), this only handles the only store in
3314 : the BBs. */
3315 :
3316 : static bool
3317 982803 : cond_if_else_store_replacement_limited (basic_block then_bb, basic_block else_bb,
3318 : basic_block join_bb)
3319 : {
3320 982803 : gphi *vphi = get_virtual_phi (join_bb);
3321 982803 : if (!vphi)
3322 : return false;
3323 :
3324 915582 : tree then_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (then_bb));
3325 1831164 : gimple *then_assign = trailing_store_in_bb (then_bb, then_vdef, vphi,
3326 915582 : !flag_expensive_optimizations);
3327 915582 : if (!then_assign)
3328 : return false;
3329 :
3330 844226 : tree else_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (else_bb));
3331 1688452 : gimple *else_assign = trailing_store_in_bb (else_bb, else_vdef, vphi,
3332 844226 : !flag_expensive_optimizations);
3333 844226 : if (!else_assign)
3334 : return false;
3335 :
3336 823104 : return cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
3337 823104 : then_assign, else_assign, vphi);
3338 : }
3339 :
3340 : /* Conditional store replacement. We already know
3341 : that the recognized pattern looks like so:
3342 :
3343 : split:
3344 : if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
3345 : THEN_BB:
3346 : ...
3347 : X = Y;
3348 : ...
3349 : goto JOIN_BB;
3350 : ELSE_BB:
3351 : ...
3352 : X = Z;
3353 : ...
3354 : fallthrough (edge E0)
3355 : JOIN_BB:
3356 : some more
3357 :
3358 : We check that it is safe to sink the store to JOIN_BB by verifying that
3359 : there are no read-after-write or write-after-write dependencies in
3360 : THEN_BB and ELSE_BB. */
3361 :
3362 : static bool
3363 229801 : cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb,
3364 : basic_block join_bb)
3365 : {
3366 229801 : vec<data_reference_p> then_datarefs, else_datarefs;
3367 229801 : vec<ddr_p> then_ddrs, else_ddrs;
3368 229801 : gimple *then_store, *else_store;
3369 229801 : bool found, ok = false, res;
3370 229801 : tree then_lhs, else_lhs;
3371 229801 : basic_block blocks[3];
3372 229801 : gphi *vphi = get_virtual_phi (join_bb);
3373 229801 : if (!vphi)
3374 : return false;
3375 :
3376 : /* Handle the case with trailing stores in THEN_BB and ELSE_BB. That is
3377 : cheap enough to always handle as it allows us to elide dependence
3378 : checking. */
3379 226893 : while (cond_if_else_store_replacement_limited (then_bb, else_bb, join_bb))
3380 : ;
3381 :
3382 : /* If either vectorization or if-conversion is disabled then do
3383 : not sink any stores. */
3384 213918 : if (param_max_stores_to_sink == 0
3385 213917 : || (!flag_tree_loop_vectorize && !flag_tree_slp_vectorize)
3386 209137 : || !flag_tree_loop_if_convert)
3387 : return false;
3388 :
3389 : /* Find data references. */
3390 209134 : then_datarefs.create (1);
3391 209134 : else_datarefs.create (1);
3392 209134 : if ((find_data_references_in_bb (NULL, then_bb, &then_datarefs)
3393 209134 : == chrec_dont_know)
3394 186988 : || !then_datarefs.length ()
3395 181347 : || (find_data_references_in_bb (NULL, else_bb, &else_datarefs)
3396 181347 : == chrec_dont_know)
3397 225680 : || !else_datarefs.length ())
3398 : {
3399 194688 : free_data_refs (then_datarefs);
3400 194688 : free_data_refs (else_datarefs);
3401 194688 : return false;
3402 : }
3403 :
3404 : /* Clear visited on else stores, we want to make sure to pick each store
3405 : at most once to avoid quadratic behavior. */
3406 51192 : for (auto else_dr : else_datarefs)
3407 : {
3408 36746 : if (DR_IS_READ (else_dr))
3409 19027 : continue;
3410 17719 : gimple_set_visited (DR_STMT (else_dr), false);
3411 : }
3412 :
3413 : /* Find pairs of stores with equal LHS. Work from the end to avoid
3414 : re-ordering stores unnecessarily. */
3415 14446 : auto_vec<std::pair<gimple *, gimple *>, 1> stores_pairs;
3416 14446 : unsigned i;
3417 14446 : data_reference_p then_dr;
3418 61631 : FOR_EACH_VEC_ELT_REVERSE (then_datarefs, i, then_dr)
3419 : {
3420 32739 : if (DR_IS_READ (then_dr))
3421 45940 : continue;
3422 :
3423 19538 : then_store = DR_STMT (then_dr);
3424 19538 : then_lhs = gimple_get_lhs (then_store);
3425 19538 : if (then_lhs == NULL_TREE)
3426 0 : continue;
3427 19538 : found = false;
3428 :
3429 19538 : unsigned j;
3430 19538 : data_reference_p else_dr;
3431 90791 : FOR_EACH_VEC_ELT_REVERSE (else_datarefs, j, else_dr)
3432 : {
3433 55438 : if (DR_IS_READ (else_dr))
3434 19955 : continue;
3435 :
3436 35483 : else_store = DR_STMT (else_dr);
3437 35483 : if (gimple_visited_p (else_store))
3438 3535 : continue;
3439 31948 : else_lhs = gimple_get_lhs (else_store);
3440 31948 : if (else_lhs == NULL_TREE)
3441 0 : continue;
3442 :
3443 31948 : if (operand_equal_p (then_lhs, else_lhs, 0))
3444 : {
3445 : found = true;
3446 : break;
3447 : }
3448 : }
3449 :
3450 19538 : if (!found)
3451 15815 : continue;
3452 :
3453 3723 : gimple_set_visited (else_store, true);
3454 3723 : stores_pairs.safe_push (std::make_pair (then_store, else_store));
3455 : }
3456 :
3457 : /* No pairs of stores found. */
3458 14446 : if (!stores_pairs.length ()
3459 14446 : || stores_pairs.length () > (unsigned) param_max_stores_to_sink)
3460 : {
3461 12328 : free_data_refs (then_datarefs);
3462 12328 : free_data_refs (else_datarefs);
3463 12328 : return false;
3464 : }
3465 :
3466 : /* Compute and check data dependencies in both basic blocks. */
3467 2118 : then_ddrs.create (1);
3468 2118 : else_ddrs.create (1);
3469 2118 : if (!compute_all_dependences (then_datarefs, &then_ddrs,
3470 2118 : vNULL, false)
3471 4236 : || !compute_all_dependences (else_datarefs, &else_ddrs,
3472 2118 : vNULL, false))
3473 : {
3474 0 : free_dependence_relations (then_ddrs);
3475 0 : free_dependence_relations (else_ddrs);
3476 0 : free_data_refs (then_datarefs);
3477 0 : free_data_refs (else_datarefs);
3478 0 : return false;
3479 : }
3480 2118 : blocks[0] = then_bb;
3481 2118 : blocks[1] = else_bb;
3482 2118 : blocks[2] = join_bb;
3483 2118 : renumber_gimple_stmt_uids_in_blocks (blocks, 3);
3484 :
3485 : /* Check that there are no read-after-write or write-after-write dependencies
3486 : in THEN_BB. */
3487 13344 : for (auto ddr : then_ddrs)
3488 : {
3489 7715 : struct data_reference *dra = DDR_A (ddr);
3490 7715 : struct data_reference *drb = DDR_B (ddr);
3491 :
3492 7715 : if (DDR_ARE_DEPENDENT (ddr) != chrec_known
3493 7715 : && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
3494 872 : && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
3495 1597 : || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
3496 466 : && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
3497 1131 : || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
3498 : {
3499 725 : free_dependence_relations (then_ddrs);
3500 725 : free_dependence_relations (else_ddrs);
3501 725 : free_data_refs (then_datarefs);
3502 725 : free_data_refs (else_datarefs);
3503 725 : return false;
3504 : }
3505 : }
3506 :
3507 : /* Check that there are no read-after-write or write-after-write dependencies
3508 : in ELSE_BB. */
3509 8815 : for (auto ddr : else_ddrs)
3510 : {
3511 4800 : struct data_reference *dra = DDR_A (ddr);
3512 4800 : struct data_reference *drb = DDR_B (ddr);
3513 :
3514 4800 : if (DDR_ARE_DEPENDENT (ddr) != chrec_known
3515 4800 : && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
3516 401 : && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
3517 565 : || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
3518 136 : && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
3519 429 : || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
3520 : {
3521 164 : free_dependence_relations (then_ddrs);
3522 164 : free_dependence_relations (else_ddrs);
3523 164 : free_data_refs (then_datarefs);
3524 164 : free_data_refs (else_datarefs);
3525 164 : return false;
3526 : }
3527 : }
3528 :
3529 : /* Sink stores with same LHS. */
3530 5346 : for (auto &store_pair : stores_pairs)
3531 : {
3532 1659 : then_store = store_pair.first;
3533 1659 : else_store = store_pair.second;
3534 1659 : res = cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
3535 : then_store, else_store, vphi);
3536 1659 : ok = ok || res;
3537 : }
3538 :
3539 1229 : free_dependence_relations (then_ddrs);
3540 1229 : free_dependence_relations (else_ddrs);
3541 1229 : free_data_refs (then_datarefs);
3542 1229 : free_data_refs (else_datarefs);
3543 :
3544 1229 : return ok;
3545 14446 : }
3546 :
3547 : /* Return TRUE if STMT has a VUSE whose corresponding VDEF is in BB. */
3548 :
3549 : static bool
3550 11886 : local_mem_dependence (gimple *stmt, basic_block bb)
3551 : {
3552 23772 : tree vuse = gimple_vuse (stmt);
3553 11886 : gimple *def;
3554 :
3555 11886 : if (!vuse)
3556 : return false;
3557 :
3558 11886 : def = SSA_NAME_DEF_STMT (vuse);
3559 11886 : return (def && gimple_bb (def) == bb);
3560 : }
3561 :
3562 : /* Given a "diamond" control-flow pattern where BB0 tests a condition,
3563 : BB1 and BB2 are "then" and "else" blocks dependent on this test,
3564 : and BB3 rejoins control flow following BB1 and BB2, look for
3565 : opportunities to hoist loads as follows. If BB3 contains a PHI of
3566 : two loads, one each occurring in BB1 and BB2, and the loads are
3567 : provably of adjacent fields in the same structure, then move both
3568 : loads into BB0. Of course this can only be done if there are no
3569 : dependencies preventing such motion.
3570 :
3571 : One of the hoisted loads will always be speculative, so the
3572 : transformation is currently conservative:
3573 :
3574 : - The fields must be strictly adjacent.
3575 : - The two fields must occupy a single memory block that is
3576 : guaranteed to not cross a page boundary.
3577 :
3578 : The last is difficult to prove, as such memory blocks should be
3579 : aligned on the minimum of the stack alignment boundary and the
3580 : alignment guaranteed by heap allocation interfaces. Thus we rely
3581 : on a parameter for the alignment value.
3582 :
3583 : Provided a good value is used for the last case, the first
3584 : restriction could possibly be relaxed. */
3585 :
3586 : static void
3587 581742 : hoist_adjacent_loads (basic_block bb0, basic_block bb1,
3588 : basic_block bb2, basic_block bb3)
3589 : {
3590 581742 : unsigned HOST_WIDE_INT param_align = param_l1_cache_line_size;
3591 581742 : unsigned HOST_WIDE_INT param_align_bits = param_align * BITS_PER_UNIT;
3592 581742 : gphi_iterator gsi;
3593 :
3594 : /* Walk the phis in bb3 looking for an opportunity. We are looking
3595 : for phis of two SSA names, one each of which is defined in bb1 and
3596 : bb2. */
3597 1292687 : for (gsi = gsi_start_phis (bb3); !gsi_end_p (gsi); gsi_next (&gsi))
3598 : {
3599 710945 : gphi *phi_stmt = gsi.phi ();
3600 710945 : gimple *def1, *def2;
3601 710945 : tree arg1, arg2, ref1, ref2, field1, field2;
3602 710945 : tree tree_offset1, tree_offset2, tree_size2, next;
3603 710945 : unsigned HOST_WIDE_INT offset1, offset2, size2, align1;
3604 710945 : gimple_stmt_iterator gsi2;
3605 710945 : basic_block bb_for_def1, bb_for_def2;
3606 :
3607 710945 : if (gimple_phi_num_args (phi_stmt) != 2
3608 1421890 : || virtual_operand_p (gimple_phi_result (phi_stmt)))
3609 705002 : continue;
3610 :
3611 168839 : arg1 = gimple_phi_arg_def (phi_stmt, 0);
3612 168839 : arg2 = gimple_phi_arg_def (phi_stmt, 1);
3613 :
3614 197630 : if (TREE_CODE (arg1) != SSA_NAME
3615 152177 : || TREE_CODE (arg2) != SSA_NAME
3616 140487 : || SSA_NAME_IS_DEFAULT_DEF (arg1)
3617 309028 : || SSA_NAME_IS_DEFAULT_DEF (arg2))
3618 28791 : continue;
3619 :
3620 140048 : def1 = SSA_NAME_DEF_STMT (arg1);
3621 140048 : def2 = SSA_NAME_DEF_STMT (arg2);
3622 :
3623 140048 : if ((gimple_bb (def1) != bb1 || gimple_bb (def2) != bb2)
3624 150397 : && (gimple_bb (def2) != bb1 || gimple_bb (def1) != bb2))
3625 33172 : continue;
3626 :
3627 : /* Check the mode of the arguments to be sure a conditional move
3628 : can be generated for it. */
3629 213752 : if (optab_handler (movcc_optab, TYPE_MODE (TREE_TYPE (arg1)))
3630 : == CODE_FOR_nothing)
3631 5255 : continue;
3632 :
3633 : /* Both statements must be assignments whose RHS is a COMPONENT_REF. */
3634 101621 : if (!gimple_assign_single_p (def1)
3635 47550 : || !gimple_assign_single_p (def2)
3636 58712 : || gimple_has_volatile_ops (def1)
3637 160327 : || gimple_has_volatile_ops (def2))
3638 72268 : continue;
3639 :
3640 29353 : ref1 = gimple_assign_rhs1 (def1);
3641 29353 : ref2 = gimple_assign_rhs1 (def2);
3642 :
3643 29353 : if (TREE_CODE (ref1) != COMPONENT_REF
3644 16318 : || TREE_CODE (ref2) != COMPONENT_REF)
3645 13144 : continue;
3646 :
3647 : /* The zeroth operand of the two component references must be
3648 : identical. It is not sufficient to compare get_base_address of
3649 : the two references, because this could allow for different
3650 : elements of the same array in the two trees. It is not safe to
3651 : assume that the existence of one array element implies the
3652 : existence of a different one. */
3653 16209 : if (!operand_equal_p (TREE_OPERAND (ref1, 0), TREE_OPERAND (ref2, 0), 0))
3654 4924 : continue;
3655 :
3656 11285 : field1 = TREE_OPERAND (ref1, 1);
3657 11285 : field2 = TREE_OPERAND (ref2, 1);
3658 :
3659 : /* Check for field adjacency, and ensure field1 comes first. */
3660 11285 : for (next = DECL_CHAIN (field1);
3661 25322 : next && TREE_CODE (next) != FIELD_DECL;
3662 14037 : next = DECL_CHAIN (next))
3663 : ;
3664 :
3665 11285 : if (next != field2)
3666 : {
3667 7774 : for (next = DECL_CHAIN (field2);
3668 9847 : next && TREE_CODE (next) != FIELD_DECL;
3669 2073 : next = DECL_CHAIN (next))
3670 : ;
3671 :
3672 7774 : if (next != field1)
3673 5342 : continue;
3674 :
3675 : std::swap (field1, field2);
3676 : std::swap (def1, def2);
3677 : }
3678 :
3679 5943 : bb_for_def1 = gimple_bb (def1);
3680 5943 : bb_for_def2 = gimple_bb (def2);
3681 :
3682 : /* Check for proper alignment of the first field. */
3683 5943 : tree_offset1 = bit_position (field1);
3684 5943 : tree_offset2 = bit_position (field2);
3685 5943 : tree_size2 = DECL_SIZE (field2);
3686 :
3687 5943 : if (!tree_fits_uhwi_p (tree_offset1)
3688 5943 : || !tree_fits_uhwi_p (tree_offset2)
3689 5943 : || !tree_fits_uhwi_p (tree_size2))
3690 0 : continue;
3691 :
3692 5943 : offset1 = tree_to_uhwi (tree_offset1);
3693 5943 : offset2 = tree_to_uhwi (tree_offset2);
3694 5943 : size2 = tree_to_uhwi (tree_size2);
3695 5943 : align1 = DECL_ALIGN (field1) % param_align_bits;
3696 :
3697 5943 : if (offset1 % BITS_PER_UNIT != 0)
3698 0 : continue;
3699 :
3700 : /* For profitability, the two field references should fit within
3701 : a single cache line. */
3702 5943 : if (align1 + offset2 - offset1 + size2 > param_align_bits)
3703 0 : continue;
3704 :
3705 : /* The two expressions cannot be dependent upon vdefs defined
3706 : in bb1/bb2. */
3707 5943 : if (local_mem_dependence (def1, bb_for_def1)
3708 5943 : || local_mem_dependence (def2, bb_for_def2))
3709 0 : continue;
3710 :
3711 : /* The conditions are satisfied; hoist the loads from bb1 and bb2 into
3712 : bb0. We hoist the first one first so that a cache miss is handled
3713 : efficiently regardless of hardware cache-fill policy. */
3714 5943 : gsi2 = gsi_for_stmt (def1);
3715 5943 : gsi_move_to_bb_end (&gsi2, bb0);
3716 5943 : gsi2 = gsi_for_stmt (def2);
3717 5943 : gsi_move_to_bb_end (&gsi2, bb0);
3718 5943 : statistics_counter_event (cfun, "hoisted loads", 1);
3719 :
3720 5943 : if (dump_file && (dump_flags & TDF_DETAILS))
3721 : {
3722 0 : fprintf (dump_file,
3723 : "\nHoisting adjacent loads from %d and %d into %d: \n",
3724 : bb_for_def1->index, bb_for_def2->index, bb0->index);
3725 0 : print_gimple_stmt (dump_file, def1, 0, TDF_VOPS|TDF_MEMSYMS);
3726 0 : print_gimple_stmt (dump_file, def2, 0, TDF_VOPS|TDF_MEMSYMS);
3727 : }
3728 : }
3729 581742 : }
3730 :
3731 : /* Determine whether we should attempt to hoist adjacent loads out of
3732 : diamond patterns in pass_phiopt. Always hoist loads if
3733 : -fhoist-adjacent-loads is specified and the target machine has
3734 : both a conditional move instruction and a defined cache line size. */
3735 :
3736 : static bool
3737 3124091 : gate_hoist_loads (void)
3738 : {
3739 3124091 : return (flag_hoist_adjacent_loads == 1
3740 3124091 : && param_l1_cache_line_size
3741 0 : && HAVE_conditional_move);
3742 : }
3743 :
3744 : template <class func_type>
3745 : static void
3746 6574836 : execute_over_cond_phis (func_type func)
3747 : {
3748 : unsigned n, i;
3749 : basic_block *bb_order;
3750 : basic_block bb;
3751 : /* Search every basic block for COND_EXPR we may be able to optimize.
3752 :
3753 : We walk the blocks in order that guarantees that a block with
3754 : a single predecessor is processed before the predecessor.
3755 : This ensures that we collapse inner ifs before visiting the
3756 : outer ones, and also that we do not try to visit a removed
3757 : block. */
3758 6574836 : bb_order = single_pred_before_succ_order ();
3759 6574836 : n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
3760 :
3761 59096232 : for (i = 0; i < n; i++)
3762 : {
3763 : basic_block bb1, bb2;
3764 : edge e1, e2;
3765 52521396 : bool diamond_p = false;
3766 :
3767 52521396 : bb = bb_order[i];
3768 :
3769 : /* Check to see if the last statement is a GIMPLE_COND. */
3770 52521396 : gcond *cond_stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
3771 31233116 : if (!cond_stmt)
3772 52521396 : continue;
3773 :
3774 21288280 : e1 = EDGE_SUCC (bb, 0);
3775 21288280 : bb1 = e1->dest;
3776 21288280 : e2 = EDGE_SUCC (bb, 1);
3777 21288280 : bb2 = e2->dest;
3778 :
3779 : /* We cannot do the optimization on abnormal edges. */
3780 21288280 : if ((e1->flags & EDGE_ABNORMAL) != 0
3781 21288280 : || (e2->flags & EDGE_ABNORMAL) != 0)
3782 0 : continue;
3783 :
3784 : /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
3785 21288280 : if (EDGE_COUNT (bb1->succs) == 0
3786 19895845 : || EDGE_COUNT (bb2->succs) == 0)
3787 4881119 : continue;
3788 :
3789 : /* Find the bb which is the fall through to the other. */
3790 16407161 : if (EDGE_SUCC (bb1, 0)->dest == bb2)
3791 : ;
3792 13922661 : else if (EDGE_SUCC (bb2, 0)->dest == bb1)
3793 : {
3794 : std::swap (bb1, bb2);
3795 : std::swap (e1, e2);
3796 : }
3797 10576891 : else if (EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest
3798 12103871 : && single_succ_p (bb2))
3799 : {
3800 1526980 : diamond_p = true;
3801 1526980 : e2 = EDGE_SUCC (bb2, 0);
3802 : /* Make sure bb2 is just a fall through. */
3803 1526980 : if ((e2->flags & EDGE_FALLTHRU) == 0)
3804 52063 : continue;
3805 : }
3806 : else
3807 10576891 : continue;
3808 :
3809 5778207 : e1 = EDGE_SUCC (bb1, 0);
3810 :
3811 : /* Make sure that bb1 is just a fall through. */
3812 5778207 : if (!single_succ_p (bb1)
3813 5778207 : || (e1->flags & EDGE_FALLTHRU) == 0)
3814 1399800 : continue;
3815 :
3816 4378407 : func (bb, bb1, bb2, e1, e2, diamond_p, cond_stmt);
3817 : }
3818 6574836 : free (bb_order);
3819 6574836 : }
3820 :
3821 : /* This pass tries to replaces an if-then-else block with an
3822 : assignment. We have different kinds of transformations.
3823 : Some of these transformations are also performed by the ifcvt
3824 : RTL optimizer.
3825 :
3826 : PHI-OPT using Match-and-simplify infrastructure
3827 : -----------------------
3828 :
3829 : The PHI-OPT pass will try to use match-and-simplify infrastructure
3830 : (gimple_simplify) to do transformations. This is implemented in
3831 : match_simplify_replacement.
3832 :
3833 : The way it works is it replaces:
3834 : bb0:
3835 : if (cond) goto bb2; else goto bb1;
3836 : bb1:
3837 : bb2:
3838 : x = PHI <a (bb1), b (bb0), ...>;
3839 :
3840 : with a statement if it gets simplified from `cond ? b : a`.
3841 :
3842 : bb0:
3843 : x1 = cond ? b : a;
3844 : bb2:
3845 : x = PHI <a (bb1), x1 (bb0), ...>;
3846 : Bb1 might be removed as it becomes unreachable when doing the replacement.
3847 : Though bb1 does not have to be considered a forwarding basic block from bb0.
3848 :
3849 : Will try to see if `(!cond) ? a : b` gets simplified (iff !cond simplifies);
3850 : this is done not to have an explosion of patterns in match.pd.
3851 : Note bb1 does not need to be completely empty, it can contain
3852 : one statement which is known not to trap.
3853 :
3854 : It also can handle the case where we have two forwarding bbs (diamond):
3855 : bb0:
3856 : if (cond) goto bb2; else goto bb1;
3857 : bb1: goto bb3;
3858 : bb2: goto bb3;
3859 : bb3:
3860 : x = PHI <a (bb1), b (bb2), ...>;
3861 : And that is replaced with a statement if it is simplified
3862 : from `cond ? b : a`.
3863 : Again bb1 and bb2 does not have to be completely empty but
3864 : each can contain one statement which is known not to trap.
3865 : But in this case bb1/bb2 can only be forwarding basic blocks.
3866 :
3867 : This fully replaces the old "Conditional Replacement",
3868 : "ABS Replacement" and "MIN/MAX Replacement" transformations as they are now
3869 : implmeneted in match.pd.
3870 :
3871 : Value Replacement
3872 : -----------------
3873 :
3874 : This transformation, implemented in value_replacement, replaces
3875 :
3876 : bb0:
3877 : if (a != b) goto bb2; else goto bb1;
3878 : bb1:
3879 : bb2:
3880 : x = PHI <a (bb1), b (bb0), ...>;
3881 :
3882 : with
3883 :
3884 : bb0:
3885 : bb2:
3886 : x = PHI <b (bb0), ...>;
3887 :
3888 : This opportunity can sometimes occur as a result of other
3889 : optimizations.
3890 :
3891 :
3892 : Another case caught by value replacement looks like this:
3893 :
3894 : bb0:
3895 : t1 = a == CONST;
3896 : t2 = b > c;
3897 : t3 = t1 & t2;
3898 : if (t3 != 0) goto bb1; else goto bb2;
3899 : bb1:
3900 : bb2:
3901 : x = PHI (CONST, a)
3902 :
3903 : Gets replaced with:
3904 : bb0:
3905 : bb2:
3906 : t1 = a == CONST;
3907 : t2 = b > c;
3908 : t3 = t1 & t2;
3909 : x = a;
3910 :
3911 :
3912 : This pass also performs a fifth transformation of a slightly different
3913 : flavor.
3914 :
3915 : Factor operations in COND_EXPR
3916 : ------------------------------
3917 :
3918 : This transformation factors the unary operations out of COND_EXPR with
3919 : factor_out_conditional_operation.
3920 :
3921 : For example:
3922 : if (a <= CST) goto <bb 3>; else goto <bb 4>;
3923 : <bb 3>:
3924 : tmp = (int) a;
3925 : <bb 4>:
3926 : tmp = PHI <tmp, CST>
3927 :
3928 : Into:
3929 : if (a <= CST) goto <bb 3>; else goto <bb 4>;
3930 : <bb 3>:
3931 : <bb 4>:
3932 : a = PHI <a, CST>
3933 : tmp = (int) a;
3934 :
3935 : Adjacent Load Hoisting
3936 : ----------------------
3937 :
3938 : This transformation replaces
3939 :
3940 : bb0:
3941 : if (...) goto bb2; else goto bb1;
3942 : bb1:
3943 : x1 = (<expr>).field1;
3944 : goto bb3;
3945 : bb2:
3946 : x2 = (<expr>).field2;
3947 : bb3:
3948 : # x = PHI <x1, x2>;
3949 :
3950 : with
3951 :
3952 : bb0:
3953 : x1 = (<expr>).field1;
3954 : x2 = (<expr>).field2;
3955 : if (...) goto bb2; else goto bb1;
3956 : bb1:
3957 : goto bb3;
3958 : bb2:
3959 : bb3:
3960 : # x = PHI <x1, x2>;
3961 :
3962 : The purpose of this transformation is to enable generation of conditional
3963 : move instructions such as Intel CMOVE or PowerPC ISEL. Because one of
3964 : the loads is speculative, the transformation is restricted to very
3965 : specific cases to avoid introducing a page fault. We are looking for
3966 : the common idiom:
3967 :
3968 : if (...)
3969 : x = y->left;
3970 : else
3971 : x = y->right;
3972 :
3973 : where left and right are typically adjacent pointers in a tree structure. */
3974 :
3975 : namespace {
3976 :
3977 : const pass_data pass_data_phiopt =
3978 : {
3979 : GIMPLE_PASS, /* type */
3980 : "phiopt", /* name */
3981 : OPTGROUP_NONE, /* optinfo_flags */
3982 : TV_TREE_PHIOPT, /* tv_id */
3983 : ( PROP_cfg | PROP_ssa ), /* properties_required */
3984 : 0, /* properties_provided */
3985 : 0, /* properties_destroyed */
3986 : 0, /* todo_flags_start */
3987 : 0, /* todo_flags_finish */
3988 : };
3989 :
3990 : class pass_phiopt : public gimple_opt_pass
3991 : {
3992 : public:
3993 1142888 : pass_phiopt (gcc::context *ctxt)
3994 2285776 : : gimple_opt_pass (pass_data_phiopt, ctxt), early_p (false)
3995 : {}
3996 :
3997 : /* opt_pass methods: */
3998 857166 : opt_pass * clone () final override { return new pass_phiopt (m_ctxt); }
3999 1142888 : void set_pass_param (unsigned n, bool param) final override
4000 : {
4001 1142888 : gcc_assert (n == 0);
4002 1142888 : early_p = param;
4003 1142888 : }
4004 5536880 : bool gate (function *) final override { return flag_ssa_phiopt; }
4005 : unsigned int execute (function *) final override;
4006 :
4007 : private:
4008 : bool early_p;
4009 : }; // class pass_phiopt
4010 :
4011 : } // anon namespace
4012 :
4013 : gimple_opt_pass *
4014 285722 : make_pass_phiopt (gcc::context *ctxt)
4015 : {
4016 285722 : return new pass_phiopt (ctxt);
4017 : }
4018 :
4019 : unsigned int
4020 5533440 : pass_phiopt::execute (function *)
4021 : {
4022 5533440 : bool do_hoist_loads = !early_p ? gate_hoist_loads () : false;
4023 5533440 : bool cfgchanged = false;
4024 :
4025 5533440 : calculate_dominance_info (CDI_DOMINATORS);
4026 5533440 : mark_ssa_maybe_undefs ();
4027 :
4028 8995369 : auto phiopt_exec = [&] (basic_block bb, basic_block bb1,
4029 : basic_block bb2, edge e1, edge e2,
4030 : bool diamond_p, gcond *cond_stmt)
4031 : {
4032 3461929 : if (diamond_p)
4033 : {
4034 1081681 : basic_block bb3 = e1->dest;
4035 :
4036 1081681 : if (!single_pred_p (bb1)
4037 2107961 : || !single_pred_p (bb2))
4038 2641163 : return;
4039 :
4040 971441 : if (do_hoist_loads
4041 763500 : && !FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt)))
4042 756295 : && EDGE_COUNT (bb->succs) == 2
4043 756295 : && EDGE_COUNT (bb3->preds) == 2
4044 : /* If one edge or the other is dominant, a conditional move
4045 : is likely to perform worse than the well-predicted branch. */
4046 586073 : && !predictable_edge_p (EDGE_SUCC (bb, 0))
4047 1553183 : && !predictable_edge_p (EDGE_SUCC (bb, 1)))
4048 581742 : hoist_adjacent_loads (bb, bb1, bb2, bb3);
4049 :
4050 : /* Try to see if there are only store in each side of the if
4051 : and try to remove that; don't do this for -Og. */
4052 971441 : if (EDGE_COUNT (bb3->preds) == 2 && !optimize_debug)
4053 755910 : while (cond_if_else_store_replacement_limited (bb1, bb2, bb3))
4054 : ;
4055 : }
4056 :
4057 971441 : gimple_stmt_iterator gsi;
4058 :
4059 : /* Check that we're looking for nested phis. */
4060 971441 : basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest : bb2;
4061 3351689 : gimple_seq phis = phi_nodes (merge);
4062 :
4063 3351689 : if (gimple_seq_empty_p (phis))
4064 : return;
4065 :
4066 : /* Factor out operations from the phi if possible. */
4067 3337508 : if (single_pred_p (bb1)
4068 5749660 : && EDGE_COUNT (merge->preds) == 2
4069 5749660 : && !optimize_debug)
4070 : {
4071 5409886 : for (gsi = gsi_start (phis); !gsi_end_p (gsi); )
4072 : {
4073 2997734 : gphi *phi = as_a <gphi *> (gsi_stmt (gsi));
4074 :
4075 2997734 : if (factor_out_conditional_operation (e1, e2, merge, phi,
4076 : cond_stmt))
4077 : {
4078 : /* Start over if there was an operation that was factored out because the new phi might have another opportunity. */
4079 23156 : phis = phi_nodes (merge);
4080 5433042 : gsi = gsi_start (phis);
4081 : }
4082 : else
4083 2974578 : gsi_next (&gsi);
4084 : }
4085 : }
4086 :
4087 : /* Value replacement can work with more than one PHI
4088 : so try that first. */
4089 3337508 : if (!early_p && !diamond_p)
4090 4273099 : for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
4091 : {
4092 2506886 : gphi *phi = as_a <gphi *> (gsi_stmt (gsi));
4093 2506886 : tree arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
4094 2506886 : tree arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
4095 2506886 : if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1) == 2)
4096 : {
4097 1943 : cfgchanged = true;
4098 1943 : return;
4099 : }
4100 : }
4101 :
4102 3335565 : gphi *phi = single_non_singleton_phi_for_edges (phis, e1, e2);
4103 3335565 : if (!phi)
4104 : return;
4105 :
4106 820766 : tree arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
4107 820766 : tree arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
4108 :
4109 : /* Something is wrong if we cannot find the arguments in the PHI
4110 : node. */
4111 820766 : gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
4112 :
4113 :
4114 : /* Do the replacement of conditional if it can be done. */
4115 820766 : if (match_simplify_replacement (bb, bb1, bb2, e1, e2, phi,
4116 820766 : arg0, arg1, early_p, diamond_p))
4117 87377 : cfgchanged = true;
4118 733389 : else if (!early_p
4119 485390 : && !diamond_p
4120 452916 : && single_pred_p (bb1)
4121 1169326 : && cond_removal_in_builtin_zero_pattern (bb, bb1, e1, e2,
4122 : phi, arg0, arg1))
4123 13 : cfgchanged = true;
4124 1554142 : else if (single_pred_p (bb1)
4125 687784 : && !diamond_p
4126 1361894 : && spaceship_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
4127 2269 : cfgchanged = true;
4128 5533440 : };
4129 :
4130 5533440 : execute_over_cond_phis (phiopt_exec);
4131 :
4132 5533440 : if (cfgchanged)
4133 63411 : return TODO_cleanup_cfg;
4134 : return 0;
4135 : }
4136 :
4137 : /* This pass tries to transform conditional stores into unconditional
4138 : ones, enabling further simplifications with the simpler then and else
4139 : blocks. In particular it replaces this:
4140 :
4141 : bb0:
4142 : if (cond) goto bb2; else goto bb1;
4143 : bb1:
4144 : *p = RHS;
4145 : bb2:
4146 :
4147 : with
4148 :
4149 : bb0:
4150 : if (cond) goto bb1; else goto bb2;
4151 : bb1:
4152 : condtmp' = *p;
4153 : bb2:
4154 : condtmp = PHI <RHS, condtmp'>
4155 : *p = condtmp;
4156 :
4157 : This transformation can only be done under several constraints,
4158 : documented below. It also replaces:
4159 :
4160 : bb0:
4161 : if (cond) goto bb2; else goto bb1;
4162 : bb1:
4163 : *p = RHS1;
4164 : goto bb3;
4165 : bb2:
4166 : *p = RHS2;
4167 : bb3:
4168 :
4169 : with
4170 :
4171 : bb0:
4172 : if (cond) goto bb3; else goto bb1;
4173 : bb1:
4174 : bb3:
4175 : condtmp = PHI <RHS1, RHS2>
4176 : *p = condtmp; */
4177 :
4178 : namespace {
4179 :
4180 : const pass_data pass_data_cselim =
4181 : {
4182 : GIMPLE_PASS, /* type */
4183 : "cselim", /* name */
4184 : OPTGROUP_NONE, /* optinfo_flags */
4185 : TV_TREE_PHIOPT, /* tv_id */
4186 : ( PROP_cfg | PROP_ssa ), /* properties_required */
4187 : 0, /* properties_provided */
4188 : 0, /* properties_destroyed */
4189 : 0, /* todo_flags_start */
4190 : 0, /* todo_flags_finish */
4191 : };
4192 :
4193 : class pass_cselim : public gimple_opt_pass
4194 : {
4195 : public:
4196 285722 : pass_cselim (gcc::context *ctxt)
4197 571444 : : gimple_opt_pass (pass_data_cselim, ctxt)
4198 : {}
4199 :
4200 : /* opt_pass methods: */
4201 1041484 : bool gate (function *) final override { return flag_tree_cselim; }
4202 : unsigned int execute (function *) final override;
4203 :
4204 : }; // class pass_cselim
4205 :
4206 : } // anon namespace
4207 :
4208 : gimple_opt_pass *
4209 285722 : make_pass_cselim (gcc::context *ctxt)
4210 : {
4211 285722 : return new pass_cselim (ctxt);
4212 : }
4213 :
4214 : unsigned int
4215 1041396 : pass_cselim::execute (function *)
4216 : {
4217 1041396 : bool cfgchanged = false;
4218 1041396 : hash_set<tree> *nontrap = 0;
4219 1041396 : unsigned todo = 0;
4220 :
4221 : /* ??? We are not interested in loop related info, but the following
4222 : will create it, ICEing as we didn't init loops with pre-headers.
4223 : An interfacing issue of find_data_references_in_bb. */
4224 1041396 : loop_optimizer_init (LOOPS_NORMAL);
4225 1041396 : scev_initialize ();
4226 :
4227 1041396 : calculate_dominance_info (CDI_DOMINATORS);
4228 :
4229 : /* Calculate the set of non-trapping memory accesses. */
4230 1041396 : nontrap = get_non_trapping ();
4231 :
4232 1957874 : auto cselim_exec = [&] (basic_block bb, basic_block bb1,
4233 : basic_block bb2, edge e1, edge e2,
4234 : bool diamond_p, gcond *)
4235 : {
4236 916478 : if (diamond_p)
4237 : {
4238 312181 : basic_block bb3 = e1->dest;
4239 :
4240 : /* Only handle sinking of store from 2 bbs only,
4241 : The middle bbs don't need to come from the
4242 : if always since we are sinking rather than
4243 : hoisting. */
4244 312181 : if (EDGE_COUNT (bb3->preds) != 2)
4245 : return;
4246 229801 : if (cond_if_else_store_replacement (bb1, bb2, bb3))
4247 1045 : cfgchanged = true;
4248 229801 : return;
4249 : }
4250 :
4251 : /* Also make sure that bb1 only have one predecessor and that it
4252 : is bb. */
4253 604297 : if (!single_pred_p (bb1)
4254 1162300 : || single_pred (bb1) != bb)
4255 : return;
4256 :
4257 : /* bb1 is the middle block, bb2 the join block, bb the split block,
4258 : e1 the fallthrough edge from bb1 to bb2. We can't do the
4259 : optimization if the join block has more than two predecessors. */
4260 558003 : if (EDGE_COUNT (bb2->preds) > 2)
4261 : return;
4262 426992 : if (cond_store_replacement (bb1, bb2, e1, e2, nontrap))
4263 5863 : cfgchanged = true;
4264 1041396 : };
4265 :
4266 1041396 : execute_over_cond_phis (cselim_exec);
4267 :
4268 2082792 : delete nontrap;
4269 : /* If the CFG has changed, we should cleanup the CFG. */
4270 1041396 : if (cfgchanged)
4271 : {
4272 : /* In cond-store replacement we have added some loads on edges
4273 : and new VOPS (as we moved the store, and created a load). */
4274 3993 : gsi_commit_edge_inserts ();
4275 3993 : todo = TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
4276 : }
4277 1041396 : scev_finalize ();
4278 1041396 : loop_optimizer_finalize ();
4279 1041396 : return todo;
4280 : }
|
