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