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