Branch data Line data Source code
1 : : /* Optimization of PHI nodes by converting them into straightline code.
2 : : Copyright (C) 2004-2025 Free Software Foundation, Inc.
3 : :
4 : : This file is part of GCC.
5 : :
6 : : GCC is free software; you can redistribute it and/or modify it
7 : : under the terms of the GNU General Public License as published by the
8 : : Free Software Foundation; either version 3, or (at your option) any
9 : : later version.
10 : :
11 : : GCC is distributed in the hope that it will be useful, but WITHOUT
12 : : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : : for more details.
15 : :
16 : : You should have received a copy of the GNU General Public License
17 : : along with GCC; see the file COPYING3. If not see
18 : : <http://www.gnu.org/licenses/>. */
19 : :
20 : : #include "config.h"
21 : : #include "system.h"
22 : : #include "coretypes.h"
23 : : #include "backend.h"
24 : : #include "insn-codes.h"
25 : : #include "rtl.h"
26 : : #include "tree.h"
27 : : #include "gimple.h"
28 : : #include "cfghooks.h"
29 : : #include "tree-pass.h"
30 : : #include "ssa.h"
31 : : #include "tree-ssa.h"
32 : : #include "optabs-tree.h"
33 : : #include "insn-config.h"
34 : : #include "gimple-pretty-print.h"
35 : : #include "fold-const.h"
36 : : #include "stor-layout.h"
37 : : #include "cfganal.h"
38 : : #include "gimplify.h"
39 : : #include "gimple-iterator.h"
40 : : #include "gimplify-me.h"
41 : : #include "tree-cfg.h"
42 : : #include "tree-dfa.h"
43 : : #include "domwalk.h"
44 : : #include "cfgloop.h"
45 : : #include "tree-data-ref.h"
46 : : #include "tree-scalar-evolution.h"
47 : : #include "tree-inline.h"
48 : : #include "case-cfn-macros.h"
49 : : #include "tree-eh.h"
50 : : #include "gimple-fold.h"
51 : : #include "internal-fn.h"
52 : : #include "gimple-range.h"
53 : : #include "gimple-match.h"
54 : : #include "dbgcnt.h"
55 : : #include "tree-ssa-propagate.h"
56 : : #include "tree-ssa-dce.h"
57 : : #include "calls.h"
58 : : #include "tree-ssa-loop-niter.h"
59 : :
60 : : /* Return the singleton PHI in the SEQ of PHIs for edges E0 and E1. */
61 : :
62 : : static gphi *
63 : 3179827 : single_non_singleton_phi_for_edges (gimple_seq seq, edge e0, edge e1)
64 : : {
65 : 3179827 : gimple_stmt_iterator i;
66 : 3179827 : gphi *phi = NULL;
67 : 4773536 : for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
68 : : {
69 : 3872844 : gphi *p = as_a <gphi *> (gsi_stmt (i));
70 : : /* If the PHI arguments are equal then we can skip this PHI. */
71 : 3872844 : if (operand_equal_for_phi_arg_p (gimple_phi_arg_def (p, e0->dest_idx),
72 : 3872844 : gimple_phi_arg_def (p, e1->dest_idx)))
73 : 264797 : continue;
74 : :
75 : : /* Punt on virtual phis with different arguments from the edges. */
76 : 7216094 : 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 : 1557296 : 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 : 84415 : 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 : 84415 : basic_block bb = gimple_bb (phi);
99 : 84415 : gimple_stmt_iterator gsi;
100 : 84415 : tree phi_result = gimple_phi_result (phi);
101 : 84415 : bool deleteboth = false;
102 : :
103 : : /* Duplicate range info if they are the only things setting the target PHI.
104 : : This is needed as later on, the new_tree will be replacing
105 : : The assignement of the PHI.
106 : : For an example:
107 : : bb1:
108 : : _4 = min<a_1, 255>
109 : : goto bb2
110 : :
111 : : # RANGE [-INF, 255]
112 : : a_3 = PHI<_4(1)>
113 : : bb3:
114 : :
115 : : use(a_3)
116 : : And _4 gets propagated into the use of a_3 and losing the range info.
117 : : This can't be done for more than 2 incoming edges as the propagation
118 : : won't happen.
119 : : The new_tree needs to be defined in the same basic block as the conditional. */
120 : 84415 : if (TREE_CODE (new_tree) == SSA_NAME
121 : 84377 : && EDGE_COUNT (gimple_bb (phi)->preds) == 2
122 : 55785 : && INTEGRAL_TYPE_P (TREE_TYPE (phi_result))
123 : 51125 : && !SSA_NAME_RANGE_INFO (new_tree)
124 : 50995 : && SSA_NAME_RANGE_INFO (phi_result)
125 : 30484 : && gimple_bb (SSA_NAME_DEF_STMT (new_tree)) == cond_block
126 : 114897 : && dbg_cnt (phiopt_edge_range))
127 : 30482 : duplicate_ssa_name_range_info (new_tree, phi_result);
128 : :
129 : : /* Change the PHI argument to new. */
130 : 84415 : SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);
131 : :
132 : : /* Remove the empty basic block. */
133 : 84415 : edge edge_to_remove = NULL, keep_edge = NULL;
134 : 84415 : if (EDGE_SUCC (cond_block, 0)->dest == bb)
135 : : {
136 : 32777 : edge_to_remove = EDGE_SUCC (cond_block, 1);
137 : 32777 : keep_edge = EDGE_SUCC (cond_block, 0);
138 : : }
139 : 51638 : 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 : 282 : else if ((keep_edge = find_edge (cond_block, e->src)))
145 : : {
146 : 282 : basic_block bb1 = EDGE_SUCC (cond_block, 0)->dest;
147 : 282 : basic_block bb2 = EDGE_SUCC (cond_block, 1)->dest;
148 : 564 : if (single_pred_p (bb1) && single_pred_p (bb2)
149 : 84979 : && single_succ_p (bb1) && single_succ_p (bb2)
150 : 564 : && empty_block_p (bb1) && empty_block_p (bb2))
151 : : deleteboth = true;
152 : : }
153 : : else
154 : 0 : gcc_unreachable ();
155 : :
156 : : /* If we are removing the cond on a loop exit,
157 : : reset number of iteration information of the loop. */
158 : 84415 : if (loop_exits_from_bb_p (cond_block->loop_father, cond_block))
159 : : {
160 : 10 : auto loop = cond_block->loop_father;
161 : 10 : free_numbers_of_iterations_estimates (loop);
162 : 10 : loop->any_upper_bound = false;
163 : 10 : loop->any_likely_upper_bound = false;
164 : : }
165 : :
166 : 84415 : if (edge_to_remove && EDGE_COUNT (edge_to_remove->dest->preds) == 1)
167 : : {
168 : 73554 : e->flags |= EDGE_FALLTHRU;
169 : 73554 : e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
170 : 73554 : e->probability = profile_probability::always ();
171 : 73554 : delete_basic_block (edge_to_remove->dest);
172 : :
173 : : /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
174 : 73554 : gsi = gsi_last_bb (cond_block);
175 : 73554 : gsi_remove (&gsi, true);
176 : : }
177 : 10861 : else if (deleteboth)
178 : : {
179 : 282 : basic_block bb1 = EDGE_SUCC (cond_block, 0)->dest;
180 : 282 : basic_block bb2 = EDGE_SUCC (cond_block, 1)->dest;
181 : :
182 : 282 : edge newedge = redirect_edge_and_branch (keep_edge, bb);
183 : :
184 : : /* The new edge should be the same. */
185 : 282 : gcc_assert (newedge == keep_edge);
186 : :
187 : 282 : keep_edge->flags |= EDGE_FALLTHRU;
188 : 282 : keep_edge->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
189 : 282 : keep_edge->probability = profile_probability::always ();
190 : :
191 : : /* Copy the edge's phi entry from the old one. */
192 : 282 : copy_phi_arg_into_existing_phi (e, keep_edge);
193 : :
194 : : /* Delete the old 2 empty basic blocks */
195 : 282 : delete_basic_block (bb1);
196 : 282 : delete_basic_block (bb2);
197 : :
198 : : /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
199 : 282 : gsi = gsi_last_bb (cond_block);
200 : 282 : gsi_remove (&gsi, true);
201 : : }
202 : : else
203 : : {
204 : : /* If there are other edges into the middle block make
205 : : CFG cleanup deal with the edge removal to avoid
206 : : updating dominators here in a non-trivial way. */
207 : 21158 : gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_block));
208 : 10579 : if (keep_edge->flags & EDGE_FALSE_VALUE)
209 : 7136 : gimple_cond_make_false (cond);
210 : 3443 : else if (keep_edge->flags & EDGE_TRUE_VALUE)
211 : 3443 : gimple_cond_make_true (cond);
212 : : }
213 : :
214 : 84415 : if (dce_ssa_names)
215 : 78882 : simple_dce_from_worklist (dce_ssa_names);
216 : :
217 : 84415 : statistics_counter_event (cfun, "Replace PHI with variable", 1);
218 : :
219 : 84415 : if (dump_file && (dump_flags & TDF_DETAILS))
220 : 13 : fprintf (dump_file,
221 : : "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
222 : : cond_block->index,
223 : : bb->index);
224 : 84415 : }
225 : :
226 : : /* Returns true if the ARG used from DEF_STMT is profitable to move
227 : : to a PHI node of the basic block MERGE where the new statement
228 : : will be located. */
229 : : static bool
230 : 103851 : is_factor_profitable (gimple *def_stmt, basic_block merge, tree arg)
231 : : {
232 : : /* The defining statement should be conditional. */
233 : 103851 : if (dominated_by_p (CDI_DOMINATORS, merge,
234 : 103851 : gimple_bb (def_stmt)))
235 : : return false;
236 : :
237 : : /* If the arg is invariant, then there is
238 : : no extending of the live range. */
239 : 101988 : if (is_gimple_min_invariant (arg))
240 : : return true;
241 : :
242 : : /* Otherwise, the arg needs to be a ssa name. */
243 : 98215 : if (TREE_CODE (arg) != SSA_NAME)
244 : : return false;
245 : :
246 : : /* We should not increase the live range of arg
247 : : across too many statements or calls. */
248 : 98215 : gimple_stmt_iterator gsi = gsi_for_stmt (def_stmt);
249 : 98215 : gsi_next_nondebug (&gsi);
250 : :
251 : : /* Skip past nops and predicates. */
252 : 196973 : while (!gsi_end_p (gsi)
253 : 98758 : && (gimple_code (gsi_stmt (gsi)) == GIMPLE_NOP
254 : 12390 : || gimple_code (gsi_stmt (gsi)) == GIMPLE_PREDICT))
255 : 543 : gsi_next_nondebug (&gsi);
256 : :
257 : : /* If the defining statement is at the end of the bb, then it is
258 : : always profitable to be to move. */
259 : 98215 : if (gsi_end_p (gsi))
260 : : return true;
261 : :
262 : : /* Check if the uses of arg is dominated by merge block, this is a quick and
263 : : rough estimate if arg is still alive at the merge bb. */
264 : : /* FIXME: extend to a more complete live range detection. */
265 : 11847 : use_operand_p use_p;
266 : 11847 : imm_use_iterator iter;
267 : 28056 : FOR_EACH_IMM_USE_FAST (use_p, iter, arg)
268 : : {
269 : 18254 : gimple *use_stmt = USE_STMT (use_p);
270 : 18254 : basic_block use_bb = gimple_bb (use_stmt);
271 : 18254 : if (dominated_by_p (CDI_DOMINATORS, merge, use_bb))
272 : : return true;
273 : : }
274 : :
275 : : /* If there are a few (non-call/asm) statements between
276 : : the old defining statement and end of the bb, then
277 : : the live range of new arg does not increase enough. */
278 : 9802 : int max_statements = param_phiopt_factor_max_stmts_live;
279 : :
280 : 28645 : while (!gsi_end_p (gsi))
281 : : {
282 : 20530 : gimple *stmt = gsi_stmt (gsi);
283 : 20530 : auto gcode = gimple_code (stmt);
284 : : /* Skip over NOPs and predicts. */
285 : 20530 : if (gcode == GIMPLE_NOP
286 : 20530 : || gcode == GIMPLE_PREDICT)
287 : : {
288 : 0 : gsi_next_nondebug (&gsi);
289 : 0 : continue;
290 : : }
291 : : /* Non-assigns will extend the live range too much. */
292 : 20530 : if (gcode != GIMPLE_ASSIGN)
293 : : return false;
294 : 20324 : max_statements --;
295 : 20324 : if (max_statements == 0)
296 : : return false;
297 : 18843 : gsi_next_nondebug (&gsi);
298 : : }
299 : : return true;
300 : : }
301 : :
302 : : /* PR66726: Factor operations out of COND_EXPR. If the arguments of the PHI
303 : : stmt are Unary operator, factor out the operation and perform the operation
304 : : to the result of PHI stmt. COND_STMT is the controlling predicate.
305 : : Return true if the operation was factored out; false otherwise. */
306 : :
307 : : static bool
308 : 2805095 : factor_out_conditional_operation (edge e0, edge e1, basic_block merge,
309 : : gphi *phi, gimple *cond_stmt)
310 : : {
311 : 2805095 : gimple *arg0_def_stmt = NULL, *arg1_def_stmt = NULL;
312 : 2805095 : tree temp, result;
313 : 2805095 : gphi *newphi;
314 : 2805095 : gimple_stmt_iterator gsi, gsi_for_def;
315 : 2805095 : location_t locus = gimple_location (phi);
316 : 2805095 : gimple_match_op arg0_op, arg1_op;
317 : :
318 : : /* We should only get here if the phi had two arguments. */
319 : 2805095 : gcc_assert (gimple_phi_num_args (phi) == 2);
320 : :
321 : : /* Virtual operands are never handled. */
322 : 5610190 : if (virtual_operand_p (gimple_phi_result (phi)))
323 : : return false;
324 : :
325 : 1206854 : tree arg0 = gimple_phi_arg_def (phi, e0->dest_idx);
326 : 1206854 : tree arg1 = gimple_phi_arg_def (phi, e1->dest_idx);
327 : 1206854 : gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
328 : :
329 : : /* Arugments that are the same don't have anything to be
330 : : done to them. */
331 : 1206854 : if (operand_equal_for_phi_arg_p (arg0, arg1))
332 : : return false;
333 : :
334 : : /* First canonicalize to simplify tests. */
335 : 1193566 : if (TREE_CODE (arg0) != SSA_NAME)
336 : : {
337 : 236156 : std::swap (arg0, arg1);
338 : 236156 : std::swap (e0, e1);
339 : : }
340 : :
341 : 1193566 : if (TREE_CODE (arg0) != SSA_NAME
342 : 1079521 : || (TREE_CODE (arg1) != SSA_NAME
343 : 472324 : && TREE_CODE (arg1) != INTEGER_CST))
344 : : return false;
345 : :
346 : : /* Check if arg0 is an SSA_NAME and the stmt which defines arg0 is
347 : : an unary operation. */
348 : 1047206 : arg0_def_stmt = SSA_NAME_DEF_STMT (arg0);
349 : 1047206 : if (!gimple_extract_op (arg0_def_stmt, &arg0_op))
350 : : return false;
351 : :
352 : : /* Check to make sure none of the operands are in abnormal phis. */
353 : 533400 : if (arg0_op.operands_occurs_in_abnormal_phi ())
354 : : return false;
355 : :
356 : : /* Currently just support one operand expressions. */
357 : 533400 : if (arg0_op.num_ops != 1)
358 : : return false;
359 : :
360 : 119626 : tree new_arg0 = arg0_op.ops[0];
361 : 119626 : tree new_arg1;
362 : :
363 : : /* If arg0 have > 1 use, then this transformation actually increases
364 : : the number of expressions evaluated at runtime. */
365 : 119626 : if (!has_single_use (arg0))
366 : : return false;
367 : 99127 : if (!is_factor_profitable (arg0_def_stmt, merge, new_arg0))
368 : : return false;
369 : :
370 : 96081 : if (TREE_CODE (arg1) == SSA_NAME)
371 : : {
372 : : /* Check if arg1 is an SSA_NAME. */
373 : 48209 : arg1_def_stmt = SSA_NAME_DEF_STMT (arg1);
374 : 48209 : if (!gimple_extract_op (arg1_def_stmt, &arg1_op))
375 : : return false;
376 : 32169 : if (arg1_op.code != arg0_op.code)
377 : : return false;
378 : 7715 : if (arg1_op.num_ops != arg0_op.num_ops)
379 : : return false;
380 : 7715 : if (arg1_op.operands_occurs_in_abnormal_phi ())
381 : : return false;
382 : :
383 : : /* If arg1 have > 1 use, then this transformation actually increases
384 : : the number of expressions evaluated at runtime. */
385 : 7715 : if (!has_single_use (arg1))
386 : : return false;
387 : :
388 : 4724 : new_arg1 = arg1_op.ops[0];
389 : :
390 : 4724 : if (!is_factor_profitable (arg1_def_stmt, merge, new_arg1))
391 : : return false;
392 : : }
393 : : else
394 : : {
395 : : /* For constants only handle if the phi was the only one. */
396 : 47872 : if (single_non_singleton_phi_for_edges (phi_nodes (merge), e0, e1) == NULL)
397 : : return false;
398 : : /* TODO: handle more than just casts here. */
399 : 37666 : if (!gimple_assign_cast_p (arg0_def_stmt))
400 : : return false;
401 : :
402 : : /* arg0_def_stmt should be conditional. */
403 : 30543 : if (dominated_by_p (CDI_DOMINATORS, gimple_bb (phi), gimple_bb (arg0_def_stmt)))
404 : : return false;
405 : :
406 : : /* Only handle if arg1 is a INTEGER_CST and one that fits
407 : : into the new type or if it is the same precision. */
408 : 61076 : if (!INTEGRAL_TYPE_P (TREE_TYPE (new_arg0))
409 : 60812 : || !(int_fits_type_p (arg1, TREE_TYPE (new_arg0))
410 : 1613 : || (TYPE_PRECISION (TREE_TYPE (new_arg0))
411 : 1613 : == TYPE_PRECISION (TREE_TYPE (arg1)))))
412 : : return false;
413 : :
414 : : /* For the INTEGER_CST case, we are just moving the
415 : : conversion from one place to another, which can often
416 : : hurt as the conversion moves further away from the
417 : : statement that computes the value. So, perform this
418 : : only if new_arg0 is an operand of COND_STMT, or
419 : : if arg0_def_stmt is the only non-debug stmt in
420 : : its basic block, because then it is possible this
421 : : could enable further optimizations (minmax replacement
422 : : etc.). See PR71016.
423 : : Note no-op conversions don't have this issue as
424 : : it will not generate any zero/sign extend in that case. */
425 : 29774 : if ((TYPE_PRECISION (TREE_TYPE (new_arg0))
426 : 29774 : != TYPE_PRECISION (TREE_TYPE (arg1)))
427 : 13888 : && new_arg0 != gimple_cond_lhs (cond_stmt)
428 : 12989 : && new_arg0 != gimple_cond_rhs (cond_stmt)
429 : 42757 : && gimple_bb (arg0_def_stmt) == e0->src)
430 : : {
431 : 12983 : gsi = gsi_for_stmt (arg0_def_stmt);
432 : 12983 : gsi_prev_nondebug (&gsi);
433 : : /* Ignore nops, predicates and labels. */
434 : 25978 : while (!gsi_end_p (gsi)
435 : 12995 : && (gimple_code (gsi_stmt (gsi)) == GIMPLE_NOP
436 : 8760 : || gimple_code (gsi_stmt (gsi)) == GIMPLE_PREDICT
437 : 8760 : || gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL))
438 : 12 : gsi_prev_nondebug (&gsi);
439 : :
440 : 12983 : if (!gsi_end_p (gsi))
441 : : {
442 : 8748 : gimple *stmt = gsi_stmt (gsi);
443 : 2788593 : if (gassign *assign = dyn_cast <gassign *> (stmt))
444 : : {
445 : 8365 : tree lhs = gimple_assign_lhs (assign);
446 : 8365 : tree lhst = TREE_TYPE (lhs);
447 : 8365 : enum tree_code ass_code
448 : 8365 : = gimple_assign_rhs_code (assign);
449 : 8365 : if (ass_code != MAX_EXPR && ass_code != MIN_EXPR
450 : : /* Conversions from boolean like types is ok
451 : : as `a?1:b` and `a?0:b` will always simplify
452 : : to `a & b` or `a | b`.
453 : : See PR 116890. */
454 : 8365 : && !(INTEGRAL_TYPE_P (lhst)
455 : 7942 : && TYPE_UNSIGNED (lhst)
456 : 5348 : && TYPE_PRECISION (lhst) == 1))
457 : : return false;
458 : 4640 : if (lhs != gimple_assign_rhs1 (arg0_def_stmt))
459 : : return false;
460 : 4581 : gsi_prev_nondebug (&gsi);
461 : 4581 : if (!gsi_end_p (gsi))
462 : : return false;
463 : : }
464 : : else
465 : : return false;
466 : : }
467 : : }
468 : 21316 : new_arg1 = fold_convert (TREE_TYPE (new_arg0), arg1);
469 : :
470 : : /* Drop the overlow that fold_convert might add. */
471 : 21316 : if (TREE_OVERFLOW (new_arg1))
472 : 0 : new_arg1 = drop_tree_overflow (new_arg1);
473 : : }
474 : :
475 : : /* If types of new_arg0 and new_arg1 are different bailout. */
476 : 25536 : if (!types_compatible_p (TREE_TYPE (new_arg0), TREE_TYPE (new_arg1)))
477 : : return false;
478 : :
479 : : /* Create a new PHI stmt. */
480 : 24997 : result = gimple_phi_result (phi);
481 : 24997 : temp = make_ssa_name (TREE_TYPE (new_arg0), NULL);
482 : :
483 : 24997 : gimple_match_op new_op = arg0_op;
484 : :
485 : : /* Create the operation stmt if possible and insert it. */
486 : 24997 : new_op.ops[0] = temp;
487 : 24997 : gimple_seq seq = NULL;
488 : 24997 : result = maybe_push_res_to_seq (&new_op, &seq, result);
489 : :
490 : : /* If we can't create the new statement, release the temp name
491 : : and return back. */
492 : 24997 : if (!result)
493 : : {
494 : 130 : release_ssa_name (temp);
495 : 130 : return false;
496 : : }
497 : :
498 : 24867 : gsi = gsi_after_labels (gimple_bb (phi));
499 : 24867 : gsi_insert_seq_before (&gsi, seq, GSI_CONTINUE_LINKING);
500 : :
501 : 24867 : newphi = create_phi_node (temp, gimple_bb (phi));
502 : :
503 : 24867 : if (dump_file && (dump_flags & TDF_DETAILS))
504 : : {
505 : 14 : fprintf (dump_file, "PHI ");
506 : 14 : print_generic_expr (dump_file, gimple_phi_result (phi));
507 : 14 : fprintf (dump_file,
508 : : " changed to factor operation out from COND_EXPR.\n");
509 : 14 : fprintf (dump_file, "New stmt with OPERATION that defines ");
510 : 14 : print_generic_expr (dump_file, result);
511 : 14 : fprintf (dump_file, ".\n");
512 : : }
513 : :
514 : : /* Remove the old operation(s) that has single use. */
515 : 24867 : gsi_for_def = gsi_for_stmt (arg0_def_stmt);
516 : 24867 : gsi_remove (&gsi_for_def, true);
517 : 24867 : release_defs (arg0_def_stmt);
518 : :
519 : 24867 : if (arg1_def_stmt)
520 : : {
521 : 3551 : gsi_for_def = gsi_for_stmt (arg1_def_stmt);
522 : 3551 : gsi_remove (&gsi_for_def, true);
523 : 3551 : release_defs (arg1_def_stmt);
524 : : }
525 : :
526 : 24867 : add_phi_arg (newphi, new_arg0, e0, locus);
527 : 24867 : add_phi_arg (newphi, new_arg1, e1, locus);
528 : :
529 : : /* Remove the original PHI stmt. */
530 : 24867 : gsi = gsi_for_stmt (phi);
531 : 24867 : gsi_remove (&gsi, true);
532 : :
533 : 24867 : statistics_counter_event (cfun, "factored out operation", 1);
534 : :
535 : 24867 : return true;
536 : : }
537 : :
538 : :
539 : : /* Return TRUE if SEQ/OP pair should be allowed during early phiopt.
540 : : Currently this is to allow MIN/MAX and ABS/NEGATE and constants. */
541 : : static bool
542 : 149301 : phiopt_early_allow (gimple_seq &seq, gimple_match_op &op)
543 : : {
544 : : /* Don't allow functions. */
545 : 149301 : if (!op.code.is_tree_code ())
546 : : return false;
547 : 149278 : tree_code code = (tree_code)op.code;
548 : :
549 : : /* For non-empty sequence, only allow one statement
550 : : except for MIN/MAX, allow max 2 statements,
551 : : each with MIN/MAX. */
552 : 149278 : if (!gimple_seq_empty_p (seq))
553 : : {
554 : 141046 : if (code == MIN_EXPR || code == MAX_EXPR)
555 : : {
556 : 11 : if (!gimple_seq_singleton_p (seq))
557 : : return false;
558 : :
559 : 11 : gimple *stmt = gimple_seq_first_stmt (seq);
560 : : /* Only allow assignments. */
561 : 11 : if (!is_gimple_assign (stmt))
562 : : return false;
563 : 11 : code = gimple_assign_rhs_code (stmt);
564 : 11 : return code == MIN_EXPR || code == MAX_EXPR;
565 : : }
566 : : /* Check to make sure op was already a SSA_NAME. */
567 : 141035 : if (code != SSA_NAME)
568 : : return false;
569 : 168412 : if (!gimple_seq_singleton_p (seq))
570 : : return false;
571 : 39258 : gimple *stmt = gimple_seq_first_stmt (seq);
572 : : /* Only allow assignments. */
573 : 39258 : if (!is_gimple_assign (stmt))
574 : : return false;
575 : 39258 : if (gimple_assign_lhs (stmt) != op.ops[0])
576 : : return false;
577 : 38403 : code = gimple_assign_rhs_code (stmt);
578 : : }
579 : :
580 : 46635 : switch (code)
581 : : {
582 : : case MIN_EXPR:
583 : : case MAX_EXPR:
584 : : case ABS_EXPR:
585 : : case ABSU_EXPR:
586 : : case NEGATE_EXPR:
587 : : case SSA_NAME:
588 : : return true;
589 : : case INTEGER_CST:
590 : : case REAL_CST:
591 : : case VECTOR_CST:
592 : : case FIXED_CST:
593 : : return true;
594 : : default:
595 : : return false;
596 : : }
597 : : }
598 : :
599 : : /* gimple_simplify_phiopt is like gimple_simplify but designed for PHIOPT.
600 : : Return NULL if nothing can be simplified or the resulting simplified value
601 : : with parts pushed if EARLY_P was true. Also rejects non allowed tree code
602 : : if EARLY_P is set.
603 : : Takes the comparison from COMP_STMT and two args, ARG0 and ARG1 and tries
604 : : to simplify CMP ? ARG0 : ARG1.
605 : : Also try to simplify (!CMP) ? ARG1 : ARG0 if the non-inverse failed. */
606 : : static tree
607 : 495850 : gimple_simplify_phiopt (bool early_p, tree type, gimple *comp_stmt,
608 : : tree arg0, tree arg1,
609 : : gimple_seq *seq)
610 : : {
611 : 495850 : gimple_seq seq1 = NULL;
612 : 495850 : enum tree_code comp_code = gimple_cond_code (comp_stmt);
613 : 495850 : location_t loc = gimple_location (comp_stmt);
614 : 495850 : tree cmp0 = gimple_cond_lhs (comp_stmt);
615 : 495850 : tree cmp1 = gimple_cond_rhs (comp_stmt);
616 : : /* To handle special cases like floating point comparison, it is easier and
617 : : less error-prone to build a tree and gimplify it on the fly though it is
618 : : less efficient.
619 : : Don't use fold_build2 here as that might create (bool)a instead of just
620 : : "a != 0". */
621 : 495850 : tree cond = build2_loc (loc, comp_code, boolean_type_node,
622 : : cmp0, cmp1);
623 : :
624 : 495850 : if (dump_file && (dump_flags & TDF_FOLDING))
625 : : {
626 : 1 : fprintf (dump_file, "\nphiopt match-simplify trying:\n\t");
627 : 1 : print_generic_expr (dump_file, cond);
628 : 1 : fprintf (dump_file, " ? ");
629 : 1 : print_generic_expr (dump_file, arg0);
630 : 1 : fprintf (dump_file, " : ");
631 : 1 : print_generic_expr (dump_file, arg1);
632 : 1 : fprintf (dump_file, "\n");
633 : : }
634 : :
635 : 495850 : gimple_match_op op (gimple_match_cond::UNCOND,
636 : 495850 : COND_EXPR, type, cond, arg0, arg1);
637 : :
638 : 495850 : if (op.resimplify (&seq1, follow_all_ssa_edges))
639 : : {
640 : 141978 : bool allowed = !early_p || phiopt_early_allow (seq1, op);
641 : 141978 : tree result = maybe_push_res_to_seq (&op, &seq1);
642 : 141978 : if (dump_file && (dump_flags & TDF_FOLDING))
643 : : {
644 : 1 : fprintf (dump_file, "\nphiopt match-simplify back:\n");
645 : 1 : if (seq1)
646 : 0 : print_gimple_seq (dump_file, seq1, 0, TDF_VOPS|TDF_MEMSYMS);
647 : 1 : fprintf (dump_file, "result: ");
648 : 1 : if (result)
649 : 1 : print_generic_expr (dump_file, result);
650 : : else
651 : 0 : fprintf (dump_file, " (none)");
652 : 1 : fprintf (dump_file, "\n");
653 : 1 : if (!allowed)
654 : 0 : fprintf (dump_file, "rejected because early\n");
655 : : }
656 : : /* Early we want only to allow some generated tree codes. */
657 : 141978 : if (allowed && result)
658 : : {
659 : 76421 : if (loc != UNKNOWN_LOCATION)
660 : 76252 : annotate_all_with_location (seq1, loc);
661 : 76421 : gimple_seq_add_seq_without_update (seq, seq1);
662 : 76421 : return result;
663 : : }
664 : : }
665 : 419429 : gimple_seq_discard (seq1);
666 : 419429 : seq1 = NULL;
667 : :
668 : : /* Try the inverted comparison, that is !COMP ? ARG1 : ARG0. */
669 : 419429 : comp_code = invert_tree_comparison (comp_code, HONOR_NANS (cmp0));
670 : :
671 : 419429 : if (comp_code == ERROR_MARK)
672 : : return NULL;
673 : :
674 : 405699 : cond = build2_loc (loc,
675 : : comp_code, boolean_type_node,
676 : : cmp0, cmp1);
677 : :
678 : 405699 : if (dump_file && (dump_flags & TDF_FOLDING))
679 : : {
680 : 0 : fprintf (dump_file, "\nphiopt match-simplify trying:\n\t");
681 : 0 : print_generic_expr (dump_file, cond);
682 : 0 : fprintf (dump_file, " ? ");
683 : 0 : print_generic_expr (dump_file, arg1);
684 : 0 : fprintf (dump_file, " : ");
685 : 0 : print_generic_expr (dump_file, arg0);
686 : 0 : fprintf (dump_file, "\n");
687 : : }
688 : :
689 : 405699 : gimple_match_op op1 (gimple_match_cond::UNCOND,
690 : 405699 : COND_EXPR, type, cond, arg1, arg0);
691 : :
692 : 405699 : if (op1.resimplify (&seq1, follow_all_ssa_edges))
693 : : {
694 : 66100 : bool allowed = !early_p || phiopt_early_allow (seq1, op1);
695 : 66100 : tree result = maybe_push_res_to_seq (&op1, &seq1);
696 : 66100 : if (dump_file && (dump_flags & TDF_FOLDING))
697 : : {
698 : 0 : fprintf (dump_file, "\nphiopt match-simplify back:\n");
699 : 0 : if (seq1)
700 : 0 : print_gimple_seq (dump_file, seq1, 0, TDF_VOPS|TDF_MEMSYMS);
701 : 0 : fprintf (dump_file, "result: ");
702 : 0 : if (result)
703 : 0 : print_generic_expr (dump_file, result);
704 : : else
705 : 0 : fprintf (dump_file, " (none)");
706 : 0 : fprintf (dump_file, "\n");
707 : 0 : if (!allowed)
708 : 0 : fprintf (dump_file, "rejected because early\n");
709 : : }
710 : : /* Early we want only to allow some generated tree codes. */
711 : 66100 : if (allowed && result)
712 : : {
713 : 2461 : if (loc != UNKNOWN_LOCATION)
714 : 2461 : annotate_all_with_location (seq1, loc);
715 : 2461 : gimple_seq_add_seq_without_update (seq, seq1);
716 : 2461 : return result;
717 : : }
718 : : }
719 : 403238 : gimple_seq_discard (seq1);
720 : :
721 : 403238 : return NULL;
722 : : }
723 : :
724 : : /* empty_bb_or_one_feeding_into_p returns true if bb was empty basic block
725 : : or it has one cheap preparation statement that feeds into the PHI
726 : : statement and it sets STMT to that statement. */
727 : : static bool
728 : 811071 : empty_bb_or_one_feeding_into_p (basic_block bb,
729 : : gimple *phi,
730 : : gimple *&stmt)
731 : : {
732 : 811071 : stmt = nullptr;
733 : 811071 : gimple *stmt_to_move = nullptr;
734 : 811071 : tree lhs;
735 : :
736 : 811071 : if (empty_block_p (bb))
737 : : return true;
738 : :
739 : 708379 : if (!single_pred_p (bb))
740 : : return false;
741 : :
742 : : /* The middle bb cannot have phi nodes as we don't
743 : : move those assignments yet. */
744 : 418764 : if (!gimple_seq_empty_p (phi_nodes (bb)))
745 : : return false;
746 : :
747 : 418738 : gimple_stmt_iterator gsi;
748 : :
749 : 418738 : gsi = gsi_start_nondebug_after_labels_bb (bb);
750 : 839877 : while (!gsi_end_p (gsi))
751 : : {
752 : 621454 : gimple *s = gsi_stmt (gsi);
753 : 621454 : gsi_next_nondebug (&gsi);
754 : : /* Skip over Predict and nop statements. */
755 : 621454 : if (gimple_code (s) == GIMPLE_PREDICT
756 : 621454 : || gimple_code (s) == GIMPLE_NOP)
757 : 2401 : continue;
758 : : /* If there is more one statement return false. */
759 : 619053 : if (stmt_to_move)
760 : : return false;
761 : : stmt_to_move = s;
762 : : }
763 : :
764 : : /* The only statement here was a Predict or a nop statement
765 : : so return true. */
766 : 218423 : if (!stmt_to_move)
767 : : return true;
768 : :
769 : 436846 : if (gimple_vuse (stmt_to_move))
770 : : return false;
771 : :
772 : 146627 : if (gimple_could_trap_p (stmt_to_move)
773 : 146627 : || gimple_has_side_effects (stmt_to_move))
774 : 4276 : return false;
775 : :
776 : 142351 : ssa_op_iter it;
777 : 142351 : tree use;
778 : 316112 : FOR_EACH_SSA_TREE_OPERAND (use, stmt_to_move, it, SSA_OP_USE)
779 : 174414 : if (ssa_name_maybe_undef_p (use))
780 : : return false;
781 : :
782 : : /* Allow assignments but allow some builtin/internal calls.
783 : : As const calls don't match any of the above, yet they could
784 : : still have some side-effects - they could contain
785 : : gimple_could_trap_p statements, like floating point
786 : : exceptions or integer division by zero. See PR70586.
787 : : FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
788 : : should handle this.
789 : : Allow some known builtin/internal calls that are known not to
790 : : trap: logical functions (e.g. bswap and bit counting). */
791 : 141698 : if (!is_gimple_assign (stmt_to_move))
792 : : {
793 : 5703 : if (!is_gimple_call (stmt_to_move))
794 : : return false;
795 : 5452 : combined_fn cfn = gimple_call_combined_fn (stmt_to_move);
796 : 5452 : switch (cfn)
797 : : {
798 : : default:
799 : : return false;
800 : 4495 : case CFN_BUILT_IN_BSWAP16:
801 : 4495 : case CFN_BUILT_IN_BSWAP32:
802 : 4495 : case CFN_BUILT_IN_BSWAP64:
803 : 4495 : case CFN_BUILT_IN_BSWAP128:
804 : 4495 : CASE_CFN_FFS:
805 : 4495 : CASE_CFN_PARITY:
806 : 4495 : CASE_CFN_POPCOUNT:
807 : 4495 : CASE_CFN_CLZ:
808 : 4495 : CASE_CFN_CTZ:
809 : 4495 : case CFN_BUILT_IN_CLRSB:
810 : 4495 : case CFN_BUILT_IN_CLRSBL:
811 : 4495 : case CFN_BUILT_IN_CLRSBLL:
812 : 4495 : lhs = gimple_call_lhs (stmt_to_move);
813 : 4495 : break;
814 : : }
815 : : }
816 : : else
817 : 135995 : lhs = gimple_assign_lhs (stmt_to_move);
818 : :
819 : 140490 : gimple *use_stmt;
820 : 140490 : use_operand_p use_p;
821 : :
822 : : /* Allow only a statement which feeds into the other stmt. */
823 : 140490 : if (!lhs || TREE_CODE (lhs) != SSA_NAME
824 : 140490 : || !single_imm_use (lhs, &use_p, &use_stmt)
825 : 280975 : || use_stmt != phi)
826 : 5 : return false;
827 : :
828 : 140485 : stmt = stmt_to_move;
829 : 140485 : return true;
830 : : }
831 : :
832 : : /* Move STMT to before GSI and insert its defining
833 : : name into INSERTED_EXPRS bitmap.
834 : : Also rewrite its if it might be undefined when unconditionalized. */
835 : : static void
836 : 157764 : move_stmt (gimple *stmt, gimple_stmt_iterator *gsi, auto_bitmap &inserted_exprs)
837 : : {
838 : 157764 : if (!stmt)
839 : 152847 : return;
840 : 4917 : if (dump_file && (dump_flags & TDF_DETAILS))
841 : : {
842 : 7 : fprintf (dump_file, "statement un-sinked:\n");
843 : 7 : print_gimple_stmt (dump_file, stmt, 0,
844 : : TDF_VOPS|TDF_MEMSYMS);
845 : : }
846 : :
847 : 4917 : tree name = gimple_get_lhs (stmt);
848 : : // Mark the name to be renamed if there is one.
849 : 4917 : bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (name));
850 : 4917 : gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt);
851 : 4917 : gsi_move_before (&gsi1, gsi);
852 : 4917 : reset_flow_sensitive_info (name);
853 : :
854 : : /* Rewrite some code which might be undefined when
855 : : unconditionalized. */
856 : 4917 : if (gimple_assign_single_p (stmt))
857 : : {
858 : 21 : tree rhs = gimple_assign_rhs1 (stmt);
859 : : /* VCE from integral types to another integral types but with
860 : : different precisions need to be changed into casts
861 : : to be well defined when unconditional. */
862 : 21 : if (gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
863 : 21 : && INTEGRAL_TYPE_P (TREE_TYPE (name))
864 : 42 : && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
865 : : {
866 : 21 : if (dump_file && (dump_flags & TDF_DETAILS))
867 : : {
868 : 0 : fprintf (dump_file, "rewriting stmt with maybe undefined VCE ");
869 : 0 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
870 : : }
871 : 21 : tree new_rhs = TREE_OPERAND (rhs, 0);
872 : 21 : gcc_assert (is_gimple_val (new_rhs));
873 : 21 : gimple_assign_set_rhs_code (stmt, NOP_EXPR);
874 : 21 : gimple_assign_set_rhs1 (stmt, new_rhs);
875 : 21 : update_stmt (stmt);
876 : : }
877 : : }
878 : : }
879 : :
880 : : /* RAII style class to temporarily remove flow sensitive
881 : : from ssa names defined by a gimple statement. */
882 : : class auto_flow_sensitive
883 : : {
884 : : public:
885 : : auto_flow_sensitive (gimple *s);
886 : : ~auto_flow_sensitive ();
887 : : private:
888 : : auto_vec<std::pair<tree, flow_sensitive_info_storage>, 2> stack;
889 : : };
890 : :
891 : : /* Constructor for auto_flow_sensitive. Saves
892 : : off the ssa names' flow sensitive information
893 : : that was defined by gimple statement S and
894 : : resets it to be non-flow based ones. */
895 : :
896 : 991700 : auto_flow_sensitive::auto_flow_sensitive (gimple *s)
897 : : {
898 : 991700 : if (!s)
899 : 857573 : return;
900 : 134127 : ssa_op_iter it;
901 : 134127 : tree def;
902 : 268254 : FOR_EACH_SSA_TREE_OPERAND (def, s, it, SSA_OP_DEF)
903 : : {
904 : 134127 : flow_sensitive_info_storage storage;
905 : 134127 : storage.save_and_clear (def);
906 : 134127 : stack.safe_push (std::make_pair (def, storage));
907 : : }
908 : : }
909 : :
910 : : /* Deconstructor, restores the flow sensitive information
911 : : for the SSA names that had been saved off. */
912 : :
913 : 991700 : auto_flow_sensitive::~auto_flow_sensitive ()
914 : : {
915 : 3109227 : for (auto p : stack)
916 : 134127 : p.second.restore (p.first);
917 : 991700 : }
918 : :
919 : : /* The function match_simplify_replacement does the main work of doing the
920 : : replacement using match and simplify. Return true if the replacement is done.
921 : : Otherwise return false.
922 : : BB is the basic block where the replacement is going to be done on. ARG0
923 : : is argument 0 from PHI. Likewise for ARG1. */
924 : :
925 : : static bool
926 : 789883 : match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
927 : : basic_block middle_bb_alt,
928 : : edge e0, edge e1, gphi *phi,
929 : : tree arg0, tree arg1, bool early_p,
930 : : bool threeway_p)
931 : : {
932 : 789883 : gimple *stmt;
933 : 789883 : gimple_stmt_iterator gsi;
934 : 789883 : edge true_edge, false_edge;
935 : 789883 : gimple_seq seq = NULL;
936 : 789883 : tree result;
937 : 789883 : gimple *stmt_to_move = NULL;
938 : 789883 : gimple *stmt_to_move_alt = NULL;
939 : 789883 : tree arg_true, arg_false;
940 : :
941 : : /* Special case A ? B : B as this will always simplify to B. */
942 : 789883 : if (operand_equal_for_phi_arg_p (arg0, arg1))
943 : : return false;
944 : :
945 : : /* If the basic block only has a cheap preparation statement,
946 : : allow it and move it once the transformation is done. */
947 : 789883 : if (!empty_bb_or_one_feeding_into_p (middle_bb, phi, stmt_to_move))
948 : : return false;
949 : :
950 : 510319 : if (threeway_p
951 : 510319 : && middle_bb != middle_bb_alt
952 : 510319 : && !empty_bb_or_one_feeding_into_p (middle_bb_alt, phi,
953 : : stmt_to_move_alt))
954 : : return false;
955 : :
956 : : /* Do not make conditional undefs unconditional. */
957 : 500268 : if ((TREE_CODE (arg0) == SSA_NAME
958 : 261828 : && ssa_name_maybe_undef_p (arg0))
959 : 761779 : || (TREE_CODE (arg1) == SSA_NAME
960 : 211518 : && ssa_name_maybe_undef_p (arg1)))
961 : : return false;
962 : :
963 : : /* At this point we know we have a GIMPLE_COND with two successors.
964 : : One successor is BB, the other successor is an empty block which
965 : : falls through into BB.
966 : :
967 : : There is a single PHI node at the join point (BB).
968 : :
969 : : So, given the condition COND, and the two PHI arguments, match and simplify
970 : : can happen on (COND) ? arg0 : arg1. */
971 : :
972 : 495850 : stmt = last_nondebug_stmt (cond_bb);
973 : :
974 : : /* We need to know which is the true edge and which is the false
975 : : edge so that we know when to invert the condition below. */
976 : 495850 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
977 : :
978 : : /* Forward the edges over the middle basic block. */
979 : 495850 : if (true_edge->dest == middle_bb)
980 : 311406 : true_edge = EDGE_SUCC (true_edge->dest, 0);
981 : 495850 : if (false_edge->dest == middle_bb)
982 : 184444 : false_edge = EDGE_SUCC (false_edge->dest, 0);
983 : :
984 : : /* When THREEWAY_P then e1 will point to the edge of the final transition
985 : : from middle-bb to end. */
986 : 495850 : if (true_edge == e0)
987 : : {
988 : 311406 : if (!threeway_p)
989 : 300344 : gcc_assert (false_edge == e1);
990 : : arg_true = arg0;
991 : : arg_false = arg1;
992 : : }
993 : : else
994 : : {
995 : 184444 : gcc_assert (false_edge == e0);
996 : 184444 : if (!threeway_p)
997 : 184371 : gcc_assert (true_edge == e1);
998 : : arg_true = arg1;
999 : : arg_false = arg0;
1000 : : }
1001 : :
1002 : 495850 : tree type = TREE_TYPE (gimple_phi_result (phi));
1003 : 495850 : {
1004 : 495850 : auto_flow_sensitive s1(stmt_to_move);
1005 : 495850 : auto_flow_sensitive s_alt(stmt_to_move_alt);
1006 : :
1007 : 495850 : result = gimple_simplify_phiopt (early_p, type, stmt,
1008 : : arg_true, arg_false,
1009 : : &seq);
1010 : 495850 : }
1011 : :
1012 : 495850 : if (!result)
1013 : : return false;
1014 : 78882 : if (dump_file && (dump_flags & TDF_FOLDING))
1015 : 1 : fprintf (dump_file, "accepted the phiopt match-simplify.\n");
1016 : :
1017 : 78882 : auto_bitmap exprs_maybe_dce;
1018 : :
1019 : : /* Mark the cond statements' lhs/rhs as maybe dce. */
1020 : 78882 : if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
1021 : 78882 : && !SSA_NAME_IS_DEFAULT_DEF (gimple_cond_lhs (stmt)))
1022 : 74394 : bitmap_set_bit (exprs_maybe_dce,
1023 : 74394 : SSA_NAME_VERSION (gimple_cond_lhs (stmt)));
1024 : 78882 : if (TREE_CODE (gimple_cond_rhs (stmt)) == SSA_NAME
1025 : 78882 : && !SSA_NAME_IS_DEFAULT_DEF (gimple_cond_rhs (stmt)))
1026 : 23197 : bitmap_set_bit (exprs_maybe_dce,
1027 : 23197 : SSA_NAME_VERSION (gimple_cond_rhs (stmt)));
1028 : :
1029 : 78882 : gsi = gsi_last_bb (cond_bb);
1030 : : /* Insert the sequence generated from gimple_simplify_phiopt. */
1031 : 78882 : if (seq)
1032 : : {
1033 : : // Mark the lhs of the new statements maybe for dce
1034 : : gimple_stmt_iterator gsi1 = gsi_start (seq);
1035 : 195838 : for (; !gsi_end_p (gsi1); gsi_next (&gsi1))
1036 : : {
1037 : 124220 : gimple *stmt = gsi_stmt (gsi1);
1038 : 124220 : tree name = gimple_get_lhs (stmt);
1039 : 124220 : if (name && TREE_CODE (name) == SSA_NAME)
1040 : 124220 : bitmap_set_bit (exprs_maybe_dce, SSA_NAME_VERSION (name));
1041 : : }
1042 : 71618 : gsi_insert_seq_before (&gsi, seq, GSI_CONTINUE_LINKING);
1043 : : }
1044 : :
1045 : : /* If there was a statement to move, move it to right before
1046 : : the original conditional. */
1047 : 78882 : move_stmt (stmt_to_move, &gsi, exprs_maybe_dce);
1048 : 78882 : move_stmt (stmt_to_move_alt, &gsi, exprs_maybe_dce);
1049 : :
1050 : 78882 : replace_phi_edge_with_variable (cond_bb, e1, phi, result, exprs_maybe_dce);
1051 : :
1052 : : /* Add Statistic here even though replace_phi_edge_with_variable already
1053 : : does it as we want to be able to count when match-simplify happens vs
1054 : : the others. */
1055 : 78882 : statistics_counter_event (cfun, "match-simplify PHI replacement", 1);
1056 : :
1057 : : /* Note that we optimized this PHI. */
1058 : 78882 : return true;
1059 : 78882 : }
1060 : :
1061 : : /* Update *ARG which is defined in STMT so that it contains the
1062 : : computed value if that seems profitable. Return true if the
1063 : : statement is made dead by that rewriting. */
1064 : :
1065 : : static bool
1066 : 325523 : jump_function_from_stmt (tree *arg, gimple *stmt)
1067 : : {
1068 : 325523 : enum tree_code code = gimple_assign_rhs_code (stmt);
1069 : 325523 : if (code == ADDR_EXPR)
1070 : : {
1071 : : /* For arg = &p->i transform it to p, if possible. */
1072 : 4426 : tree rhs1 = gimple_assign_rhs1 (stmt);
1073 : 4426 : poly_int64 offset;
1074 : 4426 : tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs1, 0),
1075 : : &offset);
1076 : 4426 : if (tem
1077 : 4337 : && TREE_CODE (tem) == MEM_REF
1078 : 8763 : && known_eq (mem_ref_offset (tem) + offset, 0))
1079 : : {
1080 : 1682 : *arg = TREE_OPERAND (tem, 0);
1081 : 1682 : return true;
1082 : : }
1083 : : }
1084 : : /* TODO: Much like IPA-CP jump-functions we want to handle constant
1085 : : additions symbolically here, and we'd need to update the comparison
1086 : : code that compares the arg + cst tuples in our caller. For now the
1087 : : code above exactly handles the VEC_BASE pattern from vec.h. */
1088 : : return false;
1089 : : }
1090 : :
1091 : : /* RHS is a source argument in a BIT_AND_EXPR or BIT_IOR_EXPR which feeds
1092 : : a conditional of the form SSA_NAME NE 0.
1093 : :
1094 : : If RHS is fed by a simple EQ_EXPR or NE_EXPR comparison of two values,
1095 : : see if the two input values of the comparison match arg0 and arg1.
1096 : :
1097 : : If so update *code and return TRUE. Otherwise return FALSE. */
1098 : :
1099 : : static bool
1100 : 164116 : rhs_is_fed_for_value_replacement (const_tree arg0, const_tree arg1,
1101 : : enum tree_code *code, const_tree rhs,
1102 : : enum tree_code bit_expression_code)
1103 : : {
1104 : : /* Obviously if RHS is not an SSA_NAME, we can't look at the defining
1105 : : statement. */
1106 : 164116 : if (TREE_CODE (rhs) == SSA_NAME)
1107 : : {
1108 : 126763 : gimple *def1 = SSA_NAME_DEF_STMT (rhs);
1109 : :
1110 : : /* Verify the defining statement has an EQ_EXPR or NE_EXPR on the RHS. */
1111 : 126763 : if (is_gimple_assign (def1)
1112 : 126763 : && ((bit_expression_code == BIT_AND_EXPR
1113 : 79390 : && gimple_assign_rhs_code (def1) == EQ_EXPR)
1114 : 99786 : || (bit_expression_code == BIT_IOR_EXPR
1115 : 38354 : && gimple_assign_rhs_code (def1) == NE_EXPR)))
1116 : : {
1117 : : /* Finally verify the source operands of the EQ_EXPR or NE_EXPR
1118 : : are equal to arg0 and arg1. */
1119 : 23993 : tree op0 = gimple_assign_rhs1 (def1);
1120 : 23993 : tree op1 = gimple_assign_rhs2 (def1);
1121 : 23993 : if ((operand_equal_for_phi_arg_p (arg0, op0)
1122 : 576 : && operand_equal_for_phi_arg_p (arg1, op1))
1123 : 24517 : || (operand_equal_for_phi_arg_p (arg0, op1)
1124 : 640 : && operand_equal_for_phi_arg_p (arg1, op0)))
1125 : : {
1126 : : /* We will perform the optimization. */
1127 : 450 : *code = gimple_assign_rhs_code (def1);
1128 : 450 : return true;
1129 : : }
1130 : : }
1131 : : }
1132 : : return false;
1133 : : }
1134 : :
1135 : : /* Return TRUE if arg0/arg1 are equal to the rhs/lhs or lhs/rhs of COND.
1136 : :
1137 : : Also return TRUE if arg0/arg1 are equal to the source arguments of an
1138 : : EQ comparison feeding a BIT_AND_EXPR, or NE comparison feeding a
1139 : : BIT_IOR_EXPR which feeds COND.
1140 : :
1141 : : Return FALSE otherwise. */
1142 : :
1143 : : static bool
1144 : 653666 : operand_equal_for_value_replacement (const_tree arg0, const_tree arg1,
1145 : : enum tree_code *code, gimple *cond)
1146 : : {
1147 : 653666 : gimple *def;
1148 : 653666 : tree lhs = gimple_cond_lhs (cond);
1149 : 653666 : tree rhs = gimple_cond_rhs (cond);
1150 : :
1151 : 653666 : if ((operand_equal_for_phi_arg_p (arg0, lhs)
1152 : 28580 : && operand_equal_for_phi_arg_p (arg1, rhs))
1153 : 674604 : || (operand_equal_for_phi_arg_p (arg1, lhs)
1154 : 43828 : && operand_equal_for_phi_arg_p (arg0, rhs)))
1155 : 14647 : return true;
1156 : :
1157 : : /* Now handle more complex case where we have an EQ comparison
1158 : : feeding a BIT_AND_EXPR, or a NE comparison feeding a BIT_IOR_EXPR,
1159 : : which then feeds into COND.
1160 : :
1161 : : First verify that COND is of the form SSA_NAME NE 0. */
1162 : 365788 : if (*code != NE_EXPR || !integer_zerop (rhs)
1163 : 893352 : || TREE_CODE (lhs) != SSA_NAME)
1164 : 384769 : return false;
1165 : :
1166 : : /* Now ensure that SSA_NAME is set by a BIT_AND_EXPR or BIT_OR_EXPR. */
1167 : 254250 : def = SSA_NAME_DEF_STMT (lhs);
1168 : 254250 : if (!is_gimple_assign (def)
1169 : 254250 : || (gimple_assign_rhs_code (def) != BIT_AND_EXPR
1170 : 111972 : && gimple_assign_rhs_code (def) != BIT_IOR_EXPR))
1171 : : return false;
1172 : :
1173 : : /* Now verify arg0/arg1 correspond to the source arguments of an EQ
1174 : : comparison feeding the BIT_AND_EXPR or a NE comparison feeding the
1175 : : BIT_IOR_EXPR. */
1176 : :
1177 : 82221 : tree tmp = gimple_assign_rhs1 (def);
1178 : 82221 : if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp,
1179 : : gimple_assign_rhs_code (def)))
1180 : : return true;
1181 : :
1182 : 81895 : tmp = gimple_assign_rhs2 (def);
1183 : 81895 : if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp,
1184 : : gimple_assign_rhs_code (def)))
1185 : : return true;
1186 : :
1187 : : return false;
1188 : : }
1189 : :
1190 : : /* Returns true if ARG is a neutral element for operation CODE
1191 : : on the RIGHT side. */
1192 : :
1193 : : static bool
1194 : 861 : neutral_element_p (tree_code code, tree arg, bool right)
1195 : : {
1196 : 861 : switch (code)
1197 : : {
1198 : 43 : case PLUS_EXPR:
1199 : 43 : case BIT_IOR_EXPR:
1200 : 43 : case BIT_XOR_EXPR:
1201 : 43 : return integer_zerop (arg);
1202 : :
1203 : 190 : case LROTATE_EXPR:
1204 : 190 : case RROTATE_EXPR:
1205 : 190 : case LSHIFT_EXPR:
1206 : 190 : case RSHIFT_EXPR:
1207 : 190 : case MINUS_EXPR:
1208 : 190 : case POINTER_PLUS_EXPR:
1209 : 190 : return right && integer_zerop (arg);
1210 : :
1211 : 482 : case MULT_EXPR:
1212 : 482 : return integer_onep (arg);
1213 : :
1214 : 31 : case TRUNC_DIV_EXPR:
1215 : 31 : case CEIL_DIV_EXPR:
1216 : 31 : case FLOOR_DIV_EXPR:
1217 : 31 : case ROUND_DIV_EXPR:
1218 : 31 : case EXACT_DIV_EXPR:
1219 : 31 : return right && integer_onep (arg);
1220 : :
1221 : 0 : case BIT_AND_EXPR:
1222 : 0 : return integer_all_onesp (arg);
1223 : :
1224 : : default:
1225 : : return false;
1226 : : }
1227 : : }
1228 : :
1229 : : /* Returns true if ARG is an absorbing element for operation CODE. */
1230 : :
1231 : : static bool
1232 : 591 : absorbing_element_p (tree_code code, tree arg, bool right, tree rval)
1233 : : {
1234 : 591 : switch (code)
1235 : : {
1236 : 18 : case BIT_IOR_EXPR:
1237 : 18 : return integer_all_onesp (arg);
1238 : :
1239 : 42 : case MULT_EXPR:
1240 : 42 : case BIT_AND_EXPR:
1241 : 42 : return integer_zerop (arg);
1242 : :
1243 : 2 : case LSHIFT_EXPR:
1244 : 2 : case RSHIFT_EXPR:
1245 : 2 : case LROTATE_EXPR:
1246 : 2 : case RROTATE_EXPR:
1247 : 2 : return !right && integer_zerop (arg);
1248 : :
1249 : 73 : case TRUNC_DIV_EXPR:
1250 : 73 : case CEIL_DIV_EXPR:
1251 : 73 : case FLOOR_DIV_EXPR:
1252 : 73 : case ROUND_DIV_EXPR:
1253 : 73 : case EXACT_DIV_EXPR:
1254 : 73 : case TRUNC_MOD_EXPR:
1255 : 73 : case CEIL_MOD_EXPR:
1256 : 73 : case FLOOR_MOD_EXPR:
1257 : 73 : case ROUND_MOD_EXPR:
1258 : 73 : return (!right
1259 : 11 : && integer_zerop (arg)
1260 : 83 : && tree_single_nonzero_warnv_p (rval, NULL));
1261 : :
1262 : : default:
1263 : : return false;
1264 : : }
1265 : : }
1266 : :
1267 : : /* The function value_replacement does the main work of doing the value
1268 : : replacement. Return non-zero if the replacement is done. Otherwise return
1269 : : 0. If we remove the middle basic block, return 2.
1270 : : BB is the basic block where the replacement is going to be done on. ARG0
1271 : : is argument 0 from the PHI. Likewise for ARG1. */
1272 : :
1273 : : static int
1274 : 2273875 : value_replacement (basic_block cond_bb, basic_block middle_bb,
1275 : : edge e0, edge e1, gphi *phi, tree arg0, tree arg1)
1276 : : {
1277 : 2273875 : gimple_stmt_iterator gsi;
1278 : 2273875 : edge true_edge, false_edge;
1279 : 2273875 : enum tree_code code;
1280 : 2273875 : bool empty_or_with_defined_p = true;
1281 : :
1282 : : /* Virtual operands don't need to be handled. */
1283 : 4014228 : if (virtual_operand_p (arg1))
1284 : : return 0;
1285 : :
1286 : : /* Special case A ? B : B as this will always simplify to B. */
1287 : 1233399 : if (operand_equal_for_phi_arg_p (arg0, arg1))
1288 : : return 0;
1289 : :
1290 : 2169836 : gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_bb));
1291 : 1084918 : code = gimple_cond_code (cond);
1292 : :
1293 : : /* This transformation is only valid for equality comparisons. */
1294 : 1084918 : if (code != NE_EXPR && code != EQ_EXPR)
1295 : : return 0;
1296 : :
1297 : : /* Do not make conditional undefs unconditional. */
1298 : 680310 : if ((TREE_CODE (arg0) == SSA_NAME
1299 : 514595 : && ssa_name_maybe_undef_p (arg0))
1300 : 1194234 : || (TREE_CODE (arg1) == SSA_NAME
1301 : 287587 : && ssa_name_maybe_undef_p (arg1)))
1302 : : return false;
1303 : :
1304 : : /* If the type says honor signed zeros we cannot do this
1305 : : optimization. */
1306 : 665672 : if (HONOR_SIGNED_ZEROS (arg1))
1307 : : return 0;
1308 : :
1309 : : /* If there is a statement in MIDDLE_BB that defines one of the PHI
1310 : : arguments, then adjust arg0 or arg1. */
1311 : 653666 : gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
1312 : 1984425 : while (!gsi_end_p (gsi))
1313 : : {
1314 : 1330759 : gimple *stmt = gsi_stmt (gsi);
1315 : 1330759 : tree lhs;
1316 : 1330759 : gsi_next_nondebug (&gsi);
1317 : 1330759 : if (!is_gimple_assign (stmt))
1318 : : {
1319 : 195345 : if (gimple_code (stmt) != GIMPLE_PREDICT
1320 : 195345 : && gimple_code (stmt) != GIMPLE_NOP)
1321 : : empty_or_with_defined_p = false;
1322 : 195345 : continue;
1323 : : }
1324 : : /* Now try to adjust arg0 or arg1 according to the computation
1325 : : in the statement. */
1326 : 1135414 : lhs = gimple_assign_lhs (stmt);
1327 : 325523 : if (!(lhs == arg0
1328 : 325523 : && jump_function_from_stmt (&arg0, stmt))
1329 : 1137096 : || (lhs == arg1
1330 : 0 : && jump_function_from_stmt (&arg1, stmt)))
1331 : : empty_or_with_defined_p = false;
1332 : : }
1333 : :
1334 : : /* The middle bb is not empty if there are any phi nodes. */
1335 : 653666 : if (phi_nodes (middle_bb))
1336 : 81200 : empty_or_with_defined_p = false;
1337 : :
1338 : : /* We need to know which is the true edge and which is the false
1339 : : edge so that we know if have abs or negative abs. */
1340 : 653666 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1341 : :
1342 : : /* At this point we know we have a COND_EXPR with two successors.
1343 : : One successor is BB, the other successor is an empty block which
1344 : : falls through into BB.
1345 : :
1346 : : The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
1347 : :
1348 : : There is a single PHI node at the join point (BB) with two arguments.
1349 : :
1350 : : We now need to verify that the two arguments in the PHI node match
1351 : : the two arguments to the equality comparison. */
1352 : :
1353 : 653666 : bool equal_p = operand_equal_for_value_replacement (arg0, arg1, &code, cond);
1354 : 653666 : bool maybe_equal_p = false;
1355 : 653666 : if (!equal_p
1356 : 653666 : && empty_or_with_defined_p
1357 : 189852 : && TREE_CODE (gimple_cond_rhs (cond)) == INTEGER_CST
1358 : 804837 : && (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond), arg0)
1359 : 151171 : ? TREE_CODE (arg1) == INTEGER_CST
1360 : 140660 : : (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond), arg1)
1361 : 20474 : && TREE_CODE (arg0) == INTEGER_CST)))
1362 : : maybe_equal_p = true;
1363 : 633963 : if (equal_p || maybe_equal_p)
1364 : : {
1365 : 34800 : edge e;
1366 : 34800 : tree arg;
1367 : :
1368 : : /* For NE_EXPR, we want to build an assignment result = arg where
1369 : : arg is the PHI argument associated with the true edge. For
1370 : : EQ_EXPR we want the PHI argument associated with the false edge. */
1371 : 34800 : e = (code == NE_EXPR ? true_edge : false_edge);
1372 : :
1373 : : /* Unfortunately, E may not reach BB (it may instead have gone to
1374 : : OTHER_BLOCK). If that is the case, then we want the single outgoing
1375 : : edge from OTHER_BLOCK which reaches BB and represents the desired
1376 : : path from COND_BLOCK. */
1377 : 34800 : if (e->dest == middle_bb)
1378 : 14601 : e = single_succ_edge (e->dest);
1379 : :
1380 : : /* Now we know the incoming edge to BB that has the argument for the
1381 : : RHS of our new assignment statement. */
1382 : 34800 : if (e0 == e)
1383 : : arg = arg0;
1384 : : else
1385 : 20199 : arg = arg1;
1386 : :
1387 : : /* If the middle basic block was empty or is defining the
1388 : : PHI arguments and this is a single phi where the args are different
1389 : : for the edges e0 and e1 then we can remove the middle basic block. */
1390 : 34800 : if (empty_or_with_defined_p
1391 : 34800 : && single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)),
1392 : : e0, e1) == phi)
1393 : : {
1394 : 19564 : use_operand_p use_p;
1395 : 19564 : gimple *use_stmt;
1396 : :
1397 : : /* Even if arg0/arg1 isn't equal to second operand of cond, we
1398 : : can optimize away the bb if we can prove it doesn't care whether
1399 : : phi result is arg0/arg1 or second operand of cond. Consider:
1400 : : <bb 2> [local count: 118111600]:
1401 : : if (i_2(D) == 4)
1402 : : goto <bb 4>; [97.00%]
1403 : : else
1404 : : goto <bb 3>; [3.00%]
1405 : :
1406 : : <bb 3> [local count: 3540129]:
1407 : :
1408 : : <bb 4> [local count: 118111600]:
1409 : : # i_6 = PHI <i_2(D)(3), 6(2)>
1410 : : _3 = i_6 != 0;
1411 : : Here, carg is 4, oarg is 6, crhs is 0, and because
1412 : : (4 != 0) == (6 != 0), we don't care if i_6 is 4 or 6, both
1413 : : have the same outcome. So, we can optimize this to:
1414 : : _3 = i_2(D) != 0;
1415 : : If the single imm use of phi result >, >=, < or <=, similarly
1416 : : we can check if both carg and oarg compare the same against
1417 : : crhs using ccode. */
1418 : 19564 : if (maybe_equal_p
1419 : 18025 : && TREE_CODE (arg) != INTEGER_CST
1420 : 37574 : && single_imm_use (gimple_phi_result (phi), &use_p, &use_stmt))
1421 : : {
1422 : 11404 : enum tree_code ccode = ERROR_MARK;
1423 : 11404 : tree clhs = NULL_TREE, crhs = NULL_TREE;
1424 : 11404 : tree carg = gimple_cond_rhs (cond);
1425 : 11404 : tree oarg = e0 == e ? arg1 : arg0;
1426 : 11404 : if (is_gimple_assign (use_stmt)
1427 : 11404 : && (TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
1428 : : == tcc_comparison))
1429 : : {
1430 : 53 : ccode = gimple_assign_rhs_code (use_stmt);
1431 : 53 : clhs = gimple_assign_rhs1 (use_stmt);
1432 : 53 : crhs = gimple_assign_rhs2 (use_stmt);
1433 : : }
1434 : 11351 : else if (gimple_code (use_stmt) == GIMPLE_COND)
1435 : : {
1436 : 54 : ccode = gimple_cond_code (use_stmt);
1437 : 54 : clhs = gimple_cond_lhs (use_stmt);
1438 : 54 : crhs = gimple_cond_rhs (use_stmt);
1439 : : }
1440 : 107 : if (ccode != ERROR_MARK
1441 : 107 : && clhs == gimple_phi_result (phi)
1442 : 177 : && TREE_CODE (crhs) == INTEGER_CST)
1443 : 46 : switch (ccode)
1444 : : {
1445 : 41 : case EQ_EXPR:
1446 : 41 : case NE_EXPR:
1447 : 41 : if (!tree_int_cst_equal (crhs, carg)
1448 : 41 : && !tree_int_cst_equal (crhs, oarg))
1449 : : equal_p = true;
1450 : : break;
1451 : 2 : case GT_EXPR:
1452 : 4 : if (tree_int_cst_lt (crhs, carg)
1453 : 2 : == tree_int_cst_lt (crhs, oarg))
1454 : : equal_p = true;
1455 : : break;
1456 : 0 : case GE_EXPR:
1457 : 0 : if (tree_int_cst_le (crhs, carg)
1458 : 0 : == tree_int_cst_le (crhs, oarg))
1459 : : equal_p = true;
1460 : : break;
1461 : 1 : case LT_EXPR:
1462 : 2 : if (tree_int_cst_lt (carg, crhs)
1463 : 1 : == tree_int_cst_lt (oarg, crhs))
1464 : : equal_p = true;
1465 : : break;
1466 : 2 : case LE_EXPR:
1467 : 4 : if (tree_int_cst_le (carg, crhs)
1468 : 2 : == tree_int_cst_le (oarg, crhs))
1469 : : equal_p = true;
1470 : : break;
1471 : : default:
1472 : : break;
1473 : : }
1474 : 11394 : if (equal_p)
1475 : : {
1476 : 10 : tree phires = gimple_phi_result (phi);
1477 : 10 : if (SSA_NAME_RANGE_INFO (phires))
1478 : : {
1479 : : /* After the optimization PHI result can have value
1480 : : which it couldn't have previously. */
1481 : 9 : value_range r (TREE_TYPE (phires));
1482 : 9 : if (get_global_range_query ()->range_of_expr (r, phires,
1483 : : phi))
1484 : : {
1485 : 9 : value_range tmp (carg, carg);
1486 : 9 : r.union_ (tmp);
1487 : 9 : reset_flow_sensitive_info (phires);
1488 : 9 : set_range_info (phires, r);
1489 : 9 : }
1490 : : else
1491 : 0 : reset_flow_sensitive_info (phires);
1492 : 9 : }
1493 : : }
1494 : 10 : if (equal_p && MAY_HAVE_DEBUG_BIND_STMTS)
1495 : : {
1496 : 7 : imm_use_iterator imm_iter;
1497 : 7 : tree phires = gimple_phi_result (phi);
1498 : 7 : tree temp = NULL_TREE;
1499 : 7 : bool reset_p = false;
1500 : :
1501 : : /* Add # DEBUG D#1 => arg != carg ? arg : oarg. */
1502 : 24 : FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, phires)
1503 : : {
1504 : 18 : if (!is_gimple_debug (use_stmt))
1505 : 7 : continue;
1506 : 11 : if (temp == NULL_TREE)
1507 : : {
1508 : 6 : if (!single_pred_p (middle_bb)
1509 : 6 : || EDGE_COUNT (gimple_bb (phi)->preds) != 2)
1510 : : {
1511 : : /* But only if middle_bb has a single
1512 : : predecessor and phi bb has two, otherwise
1513 : : we could use a SSA_NAME not usable in that
1514 : : place or wrong-debug. */
1515 : 1 : reset_p = true;
1516 : 1 : break;
1517 : : }
1518 : 5 : gimple_stmt_iterator gsi
1519 : 5 : = gsi_after_labels (gimple_bb (phi));
1520 : 5 : tree type = TREE_TYPE (phires);
1521 : 5 : temp = build_debug_expr_decl (type);
1522 : 5 : tree t = build2 (NE_EXPR, boolean_type_node,
1523 : : arg, carg);
1524 : 5 : t = build3 (COND_EXPR, type, t, arg, oarg);
1525 : 5 : gimple *g = gimple_build_debug_bind (temp, t, phi);
1526 : 5 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
1527 : : }
1528 : 20 : FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
1529 : 10 : replace_exp (use_p, temp);
1530 : 10 : update_stmt (use_stmt);
1531 : 7 : }
1532 : 7 : if (reset_p)
1533 : 1 : reset_debug_uses (phi);
1534 : : }
1535 : : }
1536 : 8170 : if (equal_p)
1537 : : {
1538 : 1549 : replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
1539 : : /* Note that we optimized this PHI. */
1540 : 1549 : return 2;
1541 : : }
1542 : : }
1543 : 15236 : else if (equal_p)
1544 : : {
1545 : 13558 : if (!single_pred_p (middle_bb))
1546 : : return 0;
1547 : 12022 : statistics_counter_event (cfun, "Replace PHI with "
1548 : : "variable/value_replacement", 1);
1549 : :
1550 : : /* Replace the PHI arguments with arg. */
1551 : 12022 : SET_PHI_ARG_DEF (phi, e0->dest_idx, arg);
1552 : 12022 : SET_PHI_ARG_DEF (phi, e1->dest_idx, arg);
1553 : 12022 : if (dump_file && (dump_flags & TDF_DETAILS))
1554 : : {
1555 : 0 : fprintf (dump_file, "PHI ");
1556 : 0 : print_generic_expr (dump_file, gimple_phi_result (phi));
1557 : 0 : fprintf (dump_file, " reduced for COND_EXPR in block %d to ",
1558 : : cond_bb->index);
1559 : 0 : print_generic_expr (dump_file, arg);
1560 : 0 : fprintf (dump_file, ".\n");
1561 : : }
1562 : 12022 : return 1;
1563 : : }
1564 : : }
1565 : :
1566 : 2795056 : if (!single_pred_p (middle_bb))
1567 : : return 0;
1568 : :
1569 : : /* Now optimize (x != 0) ? x + y : y to just x + y. */
1570 : 534856 : gsi = gsi_last_nondebug_bb (middle_bb);
1571 : 534856 : if (gsi_end_p (gsi))
1572 : : return 0;
1573 : :
1574 : 360799 : gimple *assign = gsi_stmt (gsi);
1575 : 360799 : if (!is_gimple_assign (assign)
1576 : 360799 : || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
1577 : 95529 : && !POINTER_TYPE_P (TREE_TYPE (arg0))))
1578 : : return 0;
1579 : :
1580 : 312239 : if (gimple_assign_rhs_class (assign) != GIMPLE_BINARY_RHS)
1581 : : {
1582 : : /* If last stmt of the middle_bb is a conversion, handle it like
1583 : : a preparation statement through constant evaluation with
1584 : : checking for UB. */
1585 : 138966 : enum tree_code sc = gimple_assign_rhs_code (assign);
1586 : 138966 : if (CONVERT_EXPR_CODE_P (sc))
1587 : : assign = NULL;
1588 : : else
1589 : : return 0;
1590 : : }
1591 : :
1592 : : /* Punt if there are (degenerate) PHIs in middle_bb, there should not be. */
1593 : 198769 : if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
1594 : : return 0;
1595 : :
1596 : : /* Allow up to 2 cheap preparation statements that prepare argument
1597 : : for assign, e.g.:
1598 : : if (y_4 != 0)
1599 : : goto <bb 3>;
1600 : : else
1601 : : goto <bb 4>;
1602 : : <bb 3>:
1603 : : _1 = (int) y_4;
1604 : : iftmp.0_6 = x_5(D) r<< _1;
1605 : : <bb 4>:
1606 : : # iftmp.0_2 = PHI <iftmp.0_6(3), x_5(D)(2)>
1607 : : or:
1608 : : if (y_3(D) == 0)
1609 : : goto <bb 4>;
1610 : : else
1611 : : goto <bb 3>;
1612 : : <bb 3>:
1613 : : y_4 = y_3(D) & 31;
1614 : : _1 = (int) y_4;
1615 : : _6 = x_5(D) r<< _1;
1616 : : <bb 4>:
1617 : : # _2 = PHI <x_5(D)(2), _6(3)> */
1618 : 198769 : gimple *prep_stmt[2] = { NULL, NULL };
1619 : 198769 : int prep_cnt;
1620 : 198769 : for (prep_cnt = 0; ; prep_cnt++)
1621 : : {
1622 : 261999 : if (prep_cnt || assign)
1623 : 236503 : gsi_prev_nondebug (&gsi);
1624 : 261999 : if (gsi_end_p (gsi))
1625 : : break;
1626 : :
1627 : 198314 : gimple *g = gsi_stmt (gsi);
1628 : 198314 : if (gimple_code (g) == GIMPLE_LABEL)
1629 : : break;
1630 : :
1631 : 198038 : if (prep_cnt == 2 || !is_gimple_assign (g))
1632 : 134808 : return 0;
1633 : :
1634 : 173222 : tree lhs = gimple_assign_lhs (g);
1635 : 173222 : tree rhs1 = gimple_assign_rhs1 (g);
1636 : 173222 : use_operand_p use_p;
1637 : 173222 : gimple *use_stmt;
1638 : 173222 : if (TREE_CODE (lhs) != SSA_NAME
1639 : 168138 : || TREE_CODE (rhs1) != SSA_NAME
1640 : 111140 : || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1641 : 107151 : || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1642 : 102604 : || !single_imm_use (lhs, &use_p, &use_stmt)
1643 : 275006 : || ((prep_cnt || assign)
1644 : 77978 : && use_stmt != (prep_cnt ? prep_stmt[prep_cnt - 1] : assign)))
1645 : 78698 : return 0;
1646 : 94524 : switch (gimple_assign_rhs_code (g))
1647 : : {
1648 : : CASE_CONVERT:
1649 : : break;
1650 : 19361 : case PLUS_EXPR:
1651 : 19361 : case BIT_AND_EXPR:
1652 : 19361 : case BIT_IOR_EXPR:
1653 : 19361 : case BIT_XOR_EXPR:
1654 : 19361 : if (TREE_CODE (gimple_assign_rhs2 (g)) != INTEGER_CST)
1655 : : return 0;
1656 : : break;
1657 : : default:
1658 : : return 0;
1659 : : }
1660 : 63230 : prep_stmt[prep_cnt] = g;
1661 : 63230 : }
1662 : :
1663 : : /* Only transform if it removes the condition. */
1664 : 63961 : if (!single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)), e0, e1))
1665 : : return 0;
1666 : :
1667 : : /* Size-wise, this is always profitable. */
1668 : 51841 : if (optimize_bb_for_speed_p (cond_bb)
1669 : : /* The special case is useless if it has a low probability. */
1670 : 49375 : && profile_status_for_fn (cfun) != PROFILE_ABSENT
1671 : 61364 : && EDGE_PRED (middle_bb, 0)->probability < profile_probability::even ()
1672 : : /* If assign is cheap, there is no point avoiding it. */
1673 : 63850 : && estimate_num_insns_seq (bb_seq (middle_bb), &eni_time_weights)
1674 : 12009 : >= 3 * estimate_num_insns (cond, &eni_time_weights))
1675 : 78 : return 0;
1676 : :
1677 : 51763 : tree cond_lhs = gimple_cond_lhs (cond);
1678 : 51763 : tree cond_rhs = gimple_cond_rhs (cond);
1679 : :
1680 : : /* Propagate the cond_rhs constant through preparation stmts,
1681 : : make sure UB isn't invoked while doing that. */
1682 : 53685 : for (int i = prep_cnt - 1; i >= 0; --i)
1683 : : {
1684 : 13766 : gimple *g = prep_stmt[i];
1685 : 13766 : tree grhs1 = gimple_assign_rhs1 (g);
1686 : 13766 : if (!operand_equal_for_phi_arg_p (cond_lhs, grhs1))
1687 : : return 0;
1688 : 7518 : cond_lhs = gimple_assign_lhs (g);
1689 : 7518 : cond_rhs = fold_convert (TREE_TYPE (grhs1), cond_rhs);
1690 : 7518 : if (TREE_CODE (cond_rhs) != INTEGER_CST
1691 : 7518 : || TREE_OVERFLOW (cond_rhs))
1692 : : return 0;
1693 : 1922 : if (gimple_assign_rhs_class (g) == GIMPLE_BINARY_RHS)
1694 : : {
1695 : 670 : cond_rhs = int_const_binop (gimple_assign_rhs_code (g), cond_rhs,
1696 : 670 : gimple_assign_rhs2 (g));
1697 : 670 : if (TREE_OVERFLOW (cond_rhs))
1698 : : return 0;
1699 : : }
1700 : 1922 : cond_rhs = fold_convert (TREE_TYPE (cond_lhs), cond_rhs);
1701 : 1922 : if (TREE_CODE (cond_rhs) != INTEGER_CST
1702 : 1922 : || TREE_OVERFLOW (cond_rhs))
1703 : : return 0;
1704 : : }
1705 : :
1706 : 39919 : tree lhs, rhs1, rhs2;
1707 : 39919 : enum tree_code code_def;
1708 : 39919 : if (assign)
1709 : : {
1710 : 39680 : lhs = gimple_assign_lhs (assign);
1711 : 39680 : rhs1 = gimple_assign_rhs1 (assign);
1712 : 39680 : rhs2 = gimple_assign_rhs2 (assign);
1713 : 39680 : code_def = gimple_assign_rhs_code (assign);
1714 : : }
1715 : : else
1716 : : {
1717 : 239 : gcc_assert (prep_cnt > 0);
1718 : : lhs = cond_lhs;
1719 : : rhs1 = NULL_TREE;
1720 : : rhs2 = NULL_TREE;
1721 : : code_def = ERROR_MARK;
1722 : : }
1723 : :
1724 : 22351 : if (((code == NE_EXPR && e1 == false_edge)
1725 : 20296 : || (code == EQ_EXPR && e1 == true_edge))
1726 : 22014 : && arg0 == lhs
1727 : 61933 : && ((assign == NULL
1728 : 238 : && operand_equal_for_phi_arg_p (arg1, cond_rhs))
1729 : : || (assign
1730 : 21776 : && arg1 == rhs1
1731 : 13783 : && operand_equal_for_phi_arg_p (rhs2, cond_lhs)
1732 : 400 : && neutral_element_p (code_def, cond_rhs, true))
1733 : 21719 : || (assign
1734 : 21719 : && arg1 == rhs2
1735 : 1130 : && operand_equal_for_phi_arg_p (rhs1, cond_lhs)
1736 : 461 : && neutral_element_p (code_def, cond_rhs, false))
1737 : : || (assign
1738 : 21707 : && operand_equal_for_phi_arg_p (arg1, cond_rhs)
1739 : 2534 : && ((operand_equal_for_phi_arg_p (rhs2, cond_lhs)
1740 : 138 : && absorbing_element_p (code_def, cond_rhs, true, rhs2))
1741 : 2533 : || (operand_equal_for_phi_arg_p (rhs1, cond_lhs)
1742 : 453 : && absorbing_element_p (code_def,
1743 : : cond_rhs, false, rhs2))))))
1744 : : {
1745 : 104 : gsi = gsi_for_stmt (cond);
1746 : : /* Moving ASSIGN might change VR of lhs, e.g. when moving u_6
1747 : : def-stmt in:
1748 : : if (n_5 != 0)
1749 : : goto <bb 3>;
1750 : : else
1751 : : goto <bb 4>;
1752 : :
1753 : : <bb 3>:
1754 : : # RANGE [0, 4294967294]
1755 : : u_6 = n_5 + 4294967295;
1756 : :
1757 : : <bb 4>:
1758 : : # u_3 = PHI <u_6(3), 4294967295(2)> */
1759 : 104 : reset_flow_sensitive_info (lhs);
1760 : 104 : gimple_stmt_iterator gsi_from;
1761 : 173 : for (int i = prep_cnt - 1; i >= 0; --i)
1762 : : {
1763 : 69 : tree plhs = gimple_assign_lhs (prep_stmt[i]);
1764 : 69 : reset_flow_sensitive_info (plhs);
1765 : 69 : gsi_from = gsi_for_stmt (prep_stmt[i]);
1766 : 69 : gsi_move_before (&gsi_from, &gsi);
1767 : : }
1768 : 104 : if (assign)
1769 : : {
1770 : 104 : gsi_from = gsi_for_stmt (assign);
1771 : 104 : gsi_move_before (&gsi_from, &gsi);
1772 : : }
1773 : 104 : replace_phi_edge_with_variable (cond_bb, e1, phi, lhs);
1774 : 104 : return 2;
1775 : : }
1776 : :
1777 : : return 0;
1778 : : }
1779 : :
1780 : : /* If VAR is an SSA_NAME that points to a BIT_NOT_EXPR then return the TREE for
1781 : : the value being inverted. */
1782 : :
1783 : : static tree
1784 : 0 : strip_bit_not (tree var)
1785 : : {
1786 : 0 : if (TREE_CODE (var) != SSA_NAME)
1787 : : return NULL_TREE;
1788 : :
1789 : 0 : gimple *assign = SSA_NAME_DEF_STMT (var);
1790 : 0 : if (gimple_code (assign) != GIMPLE_ASSIGN)
1791 : : return NULL_TREE;
1792 : :
1793 : 0 : if (gimple_assign_rhs_code (assign) != BIT_NOT_EXPR)
1794 : : return NULL_TREE;
1795 : :
1796 : 0 : return gimple_assign_rhs1 (assign);
1797 : : }
1798 : :
1799 : : /* Invert a MIN to a MAX or a MAX to a MIN expression CODE. */
1800 : :
1801 : : enum tree_code
1802 : 0 : invert_minmax_code (enum tree_code code)
1803 : : {
1804 : 0 : switch (code) {
1805 : : case MIN_EXPR:
1806 : : return MAX_EXPR;
1807 : 0 : case MAX_EXPR:
1808 : 0 : return MIN_EXPR;
1809 : 0 : default:
1810 : 0 : gcc_unreachable ();
1811 : : }
1812 : : }
1813 : :
1814 : : /* The function minmax_replacement does the main work of doing the minmax
1815 : : replacement. Return true if the replacement is done. Otherwise return
1816 : : false.
1817 : : BB is the basic block where the replacement is going to be done on. ARG0
1818 : : is argument 0 from the PHI. Likewise for ARG1.
1819 : :
1820 : : If THREEWAY_P then expect the BB to be laid out in diamond shape with each
1821 : : BB containing only a MIN or MAX expression. */
1822 : :
1823 : : static bool
1824 : 710987 : minmax_replacement (basic_block cond_bb, basic_block middle_bb, basic_block alt_middle_bb,
1825 : : edge e0, edge e1, gphi *phi, tree arg0, tree arg1, bool threeway_p)
1826 : : {
1827 : 710987 : tree result;
1828 : 710987 : edge true_edge, false_edge;
1829 : 710987 : enum tree_code minmax, ass_code;
1830 : 710987 : tree smaller, larger, arg_true, arg_false;
1831 : 710987 : gimple_stmt_iterator gsi, gsi_from;
1832 : :
1833 : 710987 : tree type = TREE_TYPE (gimple_phi_result (phi));
1834 : :
1835 : 1421974 : gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_bb));
1836 : 710987 : enum tree_code cmp = gimple_cond_code (cond);
1837 : 710987 : tree rhs = gimple_cond_rhs (cond);
1838 : :
1839 : : /* Turn EQ/NE of extreme values to order comparisons. */
1840 : 710987 : if ((cmp == NE_EXPR || cmp == EQ_EXPR)
1841 : 522381 : && TREE_CODE (rhs) == INTEGER_CST
1842 : 1095246 : && INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
1843 : : {
1844 : 317743 : if (wi::eq_p (wi::to_wide (rhs), wi::min_value (TREE_TYPE (rhs))))
1845 : : {
1846 : 134078 : cmp = (cmp == EQ_EXPR) ? LT_EXPR : GE_EXPR;
1847 : 134078 : rhs = wide_int_to_tree (TREE_TYPE (rhs),
1848 : 268156 : wi::min_value (TREE_TYPE (rhs)) + 1);
1849 : : }
1850 : 183665 : else if (wi::eq_p (wi::to_wide (rhs), wi::max_value (TREE_TYPE (rhs))))
1851 : : {
1852 : 10251 : cmp = (cmp == EQ_EXPR) ? GT_EXPR : LE_EXPR;
1853 : 10251 : rhs = wide_int_to_tree (TREE_TYPE (rhs),
1854 : 20502 : wi::max_value (TREE_TYPE (rhs)) - 1);
1855 : : }
1856 : : }
1857 : :
1858 : : /* This transformation is only valid for order comparisons. Record which
1859 : : operand is smaller/larger if the result of the comparison is true. */
1860 : 710987 : tree alt_smaller = NULL_TREE;
1861 : 710987 : tree alt_larger = NULL_TREE;
1862 : 710987 : if (cmp == LT_EXPR || cmp == LE_EXPR)
1863 : : {
1864 : 128742 : smaller = gimple_cond_lhs (cond);
1865 : 128742 : larger = rhs;
1866 : : /* If we have smaller < CST it is equivalent to smaller <= CST-1.
1867 : : Likewise smaller <= CST is equivalent to smaller < CST+1. */
1868 : 128742 : if (TREE_CODE (larger) == INTEGER_CST
1869 : 128742 : && INTEGRAL_TYPE_P (TREE_TYPE (larger)))
1870 : : {
1871 : 79418 : if (cmp == LT_EXPR)
1872 : : {
1873 : 44752 : wi::overflow_type overflow;
1874 : 134256 : wide_int alt = wi::sub (wi::to_wide (larger), 1,
1875 : 44752 : TYPE_SIGN (TREE_TYPE (larger)),
1876 : 44752 : &overflow);
1877 : 44752 : if (! overflow)
1878 : 44752 : alt_larger = wide_int_to_tree (TREE_TYPE (larger), alt);
1879 : 44752 : }
1880 : : else
1881 : : {
1882 : 34666 : wi::overflow_type overflow;
1883 : 103998 : wide_int alt = wi::add (wi::to_wide (larger), 1,
1884 : 34666 : TYPE_SIGN (TREE_TYPE (larger)),
1885 : 34666 : &overflow);
1886 : 34666 : if (! overflow)
1887 : 34628 : alt_larger = wide_int_to_tree (TREE_TYPE (larger), alt);
1888 : 34666 : }
1889 : : }
1890 : : }
1891 : 582245 : else if (cmp == GT_EXPR || cmp == GE_EXPR)
1892 : : {
1893 : 201004 : smaller = rhs;
1894 : 201004 : larger = gimple_cond_lhs (cond);
1895 : : /* If we have larger > CST it is equivalent to larger >= CST+1.
1896 : : Likewise larger >= CST is equivalent to larger > CST-1. */
1897 : 201004 : if (TREE_CODE (smaller) == INTEGER_CST
1898 : 201004 : && INTEGRAL_TYPE_P (TREE_TYPE (smaller)))
1899 : : {
1900 : 168991 : wi::overflow_type overflow;
1901 : 168991 : if (cmp == GT_EXPR)
1902 : : {
1903 : 115854 : wide_int alt = wi::add (wi::to_wide (smaller), 1,
1904 : 38618 : TYPE_SIGN (TREE_TYPE (smaller)),
1905 : 38618 : &overflow);
1906 : 38618 : if (! overflow)
1907 : 38618 : alt_smaller = wide_int_to_tree (TREE_TYPE (smaller), alt);
1908 : 38618 : }
1909 : : else
1910 : : {
1911 : 391119 : wide_int alt = wi::sub (wi::to_wide (smaller), 1,
1912 : 130373 : TYPE_SIGN (TREE_TYPE (smaller)),
1913 : 130373 : &overflow);
1914 : 130373 : if (! overflow)
1915 : 130373 : alt_smaller = wide_int_to_tree (TREE_TYPE (smaller), alt);
1916 : 130373 : }
1917 : : }
1918 : : }
1919 : : else
1920 : : return false;
1921 : :
1922 : : /* Handle the special case of (signed_type)x < 0 being equivalent
1923 : : to x > MAX_VAL(signed_type) and (signed_type)x >= 0 equivalent
1924 : : to x <= MAX_VAL(signed_type). */
1925 : 329746 : if ((cmp == GE_EXPR || cmp == LT_EXPR)
1926 : 221734 : && INTEGRAL_TYPE_P (type)
1927 : 171659 : && TYPE_UNSIGNED (type)
1928 : 406227 : && integer_zerop (rhs))
1929 : : {
1930 : 11930 : tree op = gimple_cond_lhs (cond);
1931 : 11930 : if (TREE_CODE (op) == SSA_NAME
1932 : 11930 : && INTEGRAL_TYPE_P (TREE_TYPE (op))
1933 : 23860 : && !TYPE_UNSIGNED (TREE_TYPE (op)))
1934 : : {
1935 : 11930 : gimple *def_stmt = SSA_NAME_DEF_STMT (op);
1936 : 11930 : if (gimple_assign_cast_p (def_stmt))
1937 : : {
1938 : 4001 : tree op1 = gimple_assign_rhs1 (def_stmt);
1939 : 8002 : if (INTEGRAL_TYPE_P (TREE_TYPE (op1))
1940 : 3985 : && TYPE_UNSIGNED (TREE_TYPE (op1))
1941 : 3923 : && (TYPE_PRECISION (TREE_TYPE (op))
1942 : 3923 : == TYPE_PRECISION (TREE_TYPE (op1)))
1943 : 7909 : && useless_type_conversion_p (type, TREE_TYPE (op1)))
1944 : : {
1945 : 2344 : wide_int w1 = wi::max_value (TREE_TYPE (op));
1946 : 2344 : wide_int w2 = wi::add (w1, 1);
1947 : 2344 : if (cmp == LT_EXPR)
1948 : : {
1949 : 1562 : larger = op1;
1950 : 1562 : smaller = wide_int_to_tree (TREE_TYPE (op1), w1);
1951 : 1562 : alt_smaller = wide_int_to_tree (TREE_TYPE (op1), w2);
1952 : 1562 : alt_larger = NULL_TREE;
1953 : : }
1954 : : else
1955 : : {
1956 : 782 : smaller = op1;
1957 : 782 : larger = wide_int_to_tree (TREE_TYPE (op1), w1);
1958 : 782 : alt_larger = wide_int_to_tree (TREE_TYPE (op1), w2);
1959 : 782 : alt_smaller = NULL_TREE;
1960 : : }
1961 : 2344 : }
1962 : : }
1963 : : }
1964 : : }
1965 : :
1966 : : /* We need to know which is the true edge and which is the false
1967 : : edge so that we know if have abs or negative abs. */
1968 : 329746 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1969 : :
1970 : : /* Forward the edges over the middle basic block. */
1971 : 329746 : if (true_edge->dest == middle_bb)
1972 : 220026 : true_edge = EDGE_SUCC (true_edge->dest, 0);
1973 : 329746 : if (false_edge->dest == middle_bb)
1974 : 109720 : false_edge = EDGE_SUCC (false_edge->dest, 0);
1975 : :
1976 : : /* When THREEWAY_P then e1 will point to the edge of the final transition
1977 : : from middle-bb to end. */
1978 : 329746 : if (true_edge == e0)
1979 : : {
1980 : 220026 : if (!threeway_p)
1981 : 184156 : gcc_assert (false_edge == e1);
1982 : : arg_true = arg0;
1983 : : arg_false = arg1;
1984 : : }
1985 : : else
1986 : : {
1987 : 109720 : gcc_assert (false_edge == e0);
1988 : 109720 : if (!threeway_p)
1989 : 109378 : gcc_assert (true_edge == e1);
1990 : : arg_true = arg1;
1991 : : arg_false = arg0;
1992 : : }
1993 : :
1994 : 329746 : if (empty_block_p (middle_bb)
1995 : 329746 : && (!threeway_p
1996 : 8801 : || empty_block_p (alt_middle_bb)))
1997 : : {
1998 : 138026 : if ((operand_equal_for_phi_arg_p (arg_true, smaller)
1999 : 117018 : || (alt_smaller
2000 : 65094 : && operand_equal_for_phi_arg_p (arg_true, alt_smaller)))
2001 : 141610 : && (operand_equal_for_phi_arg_p (arg_false, larger)
2002 : 23014 : || (alt_larger
2003 : 2477 : && operand_equal_for_phi_arg_p (arg_true, alt_larger))))
2004 : : {
2005 : : /* Case
2006 : :
2007 : : if (smaller < larger)
2008 : : rslt = smaller;
2009 : : else
2010 : : rslt = larger; */
2011 : : minmax = MIN_EXPR;
2012 : : }
2013 : 136448 : else if ((operand_equal_for_phi_arg_p (arg_false, smaller)
2014 : 120709 : || (alt_smaller
2015 : 70786 : && operand_equal_for_phi_arg_p (arg_false, alt_smaller)))
2016 : 148430 : && (operand_equal_for_phi_arg_p (arg_true, larger)
2017 : 25472 : || (alt_larger
2018 : 3712 : && operand_equal_for_phi_arg_p (arg_true, alt_larger))))
2019 : : minmax = MAX_EXPR;
2020 : : else
2021 : 134178 : return false;
2022 : : }
2023 : 191720 : else if (HONOR_NANS (type) || HONOR_SIGNED_ZEROS (type))
2024 : : /* The optimization may be unsafe due to NaNs. */
2025 : 9310 : return false;
2026 : 182410 : else if (middle_bb != alt_middle_bb && threeway_p)
2027 : : {
2028 : : /* Recognize the following case:
2029 : :
2030 : : if (smaller < larger)
2031 : : a = MIN (smaller, c);
2032 : : else
2033 : : b = MIN (larger, c);
2034 : : x = PHI <a, b>
2035 : :
2036 : : This is equivalent to
2037 : :
2038 : : a = MIN (smaller, c);
2039 : : x = MIN (larger, a); */
2040 : :
2041 : 29723 : gimple *assign = last_and_only_stmt (middle_bb);
2042 : 29723 : tree lhs, op0, op1, bound;
2043 : 29723 : tree alt_lhs, alt_op0, alt_op1;
2044 : 29723 : bool invert = false;
2045 : :
2046 : : /* When THREEWAY_P then e1 will point to the edge of the final transition
2047 : : from middle-bb to end. */
2048 : 29723 : if (true_edge == e0)
2049 : 29434 : gcc_assert (false_edge == EDGE_PRED (e1->src, 0));
2050 : : else
2051 : 289 : gcc_assert (true_edge == EDGE_PRED (e1->src, 0));
2052 : :
2053 : 29723 : bool valid_minmax_p = false;
2054 : 29723 : gimple_stmt_iterator it1
2055 : 29723 : = gsi_start_nondebug_after_labels_bb (middle_bb);
2056 : 29723 : gimple_stmt_iterator it2
2057 : 29723 : = gsi_start_nondebug_after_labels_bb (alt_middle_bb);
2058 : 29723 : if (gsi_one_nondebug_before_end_p (it1)
2059 : 29723 : && gsi_one_nondebug_before_end_p (it2))
2060 : : {
2061 : 8129 : gimple *stmt1 = gsi_stmt (it1);
2062 : 8129 : gimple *stmt2 = gsi_stmt (it2);
2063 : 8129 : if (is_gimple_assign (stmt1) && is_gimple_assign (stmt2))
2064 : : {
2065 : 6092 : enum tree_code code1 = gimple_assign_rhs_code (stmt1);
2066 : 6092 : enum tree_code code2 = gimple_assign_rhs_code (stmt2);
2067 : 6092 : valid_minmax_p = (code1 == MIN_EXPR || code1 == MAX_EXPR)
2068 : 6092 : && (code2 == MIN_EXPR || code2 == MAX_EXPR);
2069 : : }
2070 : : }
2071 : :
2072 : 40 : if (!valid_minmax_p)
2073 : 29683 : return false;
2074 : :
2075 : 40 : if (!assign
2076 : 40 : || gimple_code (assign) != GIMPLE_ASSIGN)
2077 : : return false;
2078 : :
2079 : : /* There cannot be any phi nodes in the middle bb. */
2080 : 40 : if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
2081 : : return false;
2082 : :
2083 : 40 : lhs = gimple_assign_lhs (assign);
2084 : 40 : ass_code = gimple_assign_rhs_code (assign);
2085 : 40 : if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
2086 : : return false;
2087 : :
2088 : 40 : op0 = gimple_assign_rhs1 (assign);
2089 : 40 : op1 = gimple_assign_rhs2 (assign);
2090 : :
2091 : 40 : assign = last_and_only_stmt (alt_middle_bb);
2092 : 40 : if (!assign
2093 : 40 : || gimple_code (assign) != GIMPLE_ASSIGN)
2094 : : return false;
2095 : :
2096 : : /* There cannot be any phi nodes in the alt middle bb. */
2097 : 40 : if (!gimple_seq_empty_p (phi_nodes (alt_middle_bb)))
2098 : : return false;
2099 : :
2100 : 40 : alt_lhs = gimple_assign_lhs (assign);
2101 : 40 : if (ass_code != gimple_assign_rhs_code (assign))
2102 : : return false;
2103 : :
2104 : 0 : if (!operand_equal_for_phi_arg_p (lhs, arg_true)
2105 : 0 : || !operand_equal_for_phi_arg_p (alt_lhs, arg_false))
2106 : 0 : return false;
2107 : :
2108 : 0 : alt_op0 = gimple_assign_rhs1 (assign);
2109 : 0 : alt_op1 = gimple_assign_rhs2 (assign);
2110 : :
2111 : 0 : if ((operand_equal_for_phi_arg_p (op0, smaller)
2112 : 0 : || (alt_smaller
2113 : 0 : && operand_equal_for_phi_arg_p (op0, alt_smaller)))
2114 : 0 : && (operand_equal_for_phi_arg_p (alt_op0, larger)
2115 : 0 : || (alt_larger
2116 : 0 : && operand_equal_for_phi_arg_p (alt_op0, alt_larger))))
2117 : : {
2118 : : /* We got here if the condition is true, i.e., SMALLER < LARGER. */
2119 : 0 : if (!operand_equal_for_phi_arg_p (op1, alt_op1))
2120 : : return false;
2121 : :
2122 : 0 : if ((arg0 = strip_bit_not (op0)) != NULL
2123 : 0 : && (arg1 = strip_bit_not (alt_op0)) != NULL
2124 : 0 : && (bound = strip_bit_not (op1)) != NULL)
2125 : : {
2126 : 0 : minmax = MAX_EXPR;
2127 : 0 : ass_code = invert_minmax_code (ass_code);
2128 : 0 : invert = true;
2129 : : }
2130 : : else
2131 : : {
2132 : : bound = op1;
2133 : : minmax = MIN_EXPR;
2134 : : arg0 = op0;
2135 : : arg1 = alt_op0;
2136 : : }
2137 : : }
2138 : 0 : else if ((operand_equal_for_phi_arg_p (op0, larger)
2139 : 0 : || (alt_larger
2140 : 0 : && operand_equal_for_phi_arg_p (op0, alt_larger)))
2141 : 0 : && (operand_equal_for_phi_arg_p (alt_op0, smaller)
2142 : 0 : || (alt_smaller
2143 : 0 : && operand_equal_for_phi_arg_p (alt_op0, alt_smaller))))
2144 : : {
2145 : : /* We got here if the condition is true, i.e., SMALLER > LARGER. */
2146 : 0 : if (!operand_equal_for_phi_arg_p (op1, alt_op1))
2147 : : return false;
2148 : :
2149 : 0 : if ((arg0 = strip_bit_not (op0)) != NULL
2150 : 0 : && (arg1 = strip_bit_not (alt_op0)) != NULL
2151 : 0 : && (bound = strip_bit_not (op1)) != NULL)
2152 : : {
2153 : 0 : minmax = MIN_EXPR;
2154 : 0 : ass_code = invert_minmax_code (ass_code);
2155 : 0 : invert = true;
2156 : : }
2157 : : else
2158 : : {
2159 : : bound = op1;
2160 : : minmax = MAX_EXPR;
2161 : : arg0 = op0;
2162 : : arg1 = alt_op0;
2163 : : }
2164 : : }
2165 : : else
2166 : 0 : return false;
2167 : :
2168 : : /* Emit the statement to compute min/max. */
2169 : 0 : location_t locus = gimple_location (last_nondebug_stmt (cond_bb));
2170 : 0 : gimple_seq stmts = NULL;
2171 : 0 : tree phi_result = gimple_phi_result (phi);
2172 : 0 : result = gimple_build (&stmts, locus, minmax, TREE_TYPE (phi_result),
2173 : : arg0, arg1);
2174 : 0 : result = gimple_build (&stmts, locus, ass_code, TREE_TYPE (phi_result),
2175 : : result, bound);
2176 : 0 : if (invert)
2177 : 0 : result = gimple_build (&stmts, locus, BIT_NOT_EXPR, TREE_TYPE (phi_result),
2178 : : result);
2179 : :
2180 : 0 : gsi = gsi_last_bb (cond_bb);
2181 : 0 : gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2182 : :
2183 : 0 : replace_phi_edge_with_variable (cond_bb, e1, phi, result);
2184 : :
2185 : 0 : return true;
2186 : : }
2187 : 152687 : else if (!threeway_p
2188 : 152687 : || empty_block_p (alt_middle_bb))
2189 : : {
2190 : : /* Recognize the following case, assuming d <= u:
2191 : :
2192 : : if (a <= u)
2193 : : b = MAX (a, d);
2194 : : x = PHI <b, u>
2195 : :
2196 : : This is equivalent to
2197 : :
2198 : : b = MAX (a, d);
2199 : : x = MIN (b, u); */
2200 : :
2201 : 152687 : gimple *assign = last_and_only_stmt (middle_bb);
2202 : 152687 : tree lhs, op0, op1, bound;
2203 : :
2204 : 825160 : if (!single_pred_p (middle_bb))
2205 : : return false;
2206 : :
2207 : 147762 : if (!assign
2208 : 147762 : || gimple_code (assign) != GIMPLE_ASSIGN)
2209 : : return false;
2210 : :
2211 : : /* There cannot be any phi nodes in the middle bb. */
2212 : 82717 : if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
2213 : : return false;
2214 : :
2215 : 82697 : lhs = gimple_assign_lhs (assign);
2216 : 82697 : ass_code = gimple_assign_rhs_code (assign);
2217 : 82697 : if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
2218 : : return false;
2219 : 2875 : op0 = gimple_assign_rhs1 (assign);
2220 : 2875 : op1 = gimple_assign_rhs2 (assign);
2221 : :
2222 : 2875 : if (true_edge->src == middle_bb)
2223 : : {
2224 : : /* We got here if the condition is true, i.e., SMALLER < LARGER. */
2225 : 2589 : if (!operand_equal_for_phi_arg_p (lhs, arg_true))
2226 : : return false;
2227 : :
2228 : 2589 : if (operand_equal_for_phi_arg_p (arg_false, larger)
2229 : 2589 : || (alt_larger
2230 : 32 : && operand_equal_for_phi_arg_p (arg_false, alt_larger)))
2231 : : {
2232 : : /* Case
2233 : :
2234 : : if (smaller < larger)
2235 : : {
2236 : : r' = MAX_EXPR (smaller, bound)
2237 : : }
2238 : : r = PHI <r', larger> --> to be turned to MIN_EXPR. */
2239 : 1833 : if (ass_code != MAX_EXPR)
2240 : : return false;
2241 : :
2242 : 1816 : minmax = MIN_EXPR;
2243 : 1816 : if (operand_equal_for_phi_arg_p (op0, smaller)
2244 : 1816 : || (alt_smaller
2245 : 0 : && operand_equal_for_phi_arg_p (op0, alt_smaller)))
2246 : : bound = op1;
2247 : 908 : else if (operand_equal_for_phi_arg_p (op1, smaller)
2248 : 908 : || (alt_smaller
2249 : 0 : && operand_equal_for_phi_arg_p (op1, alt_smaller)))
2250 : : bound = op0;
2251 : : else
2252 : 0 : return false;
2253 : :
2254 : : /* We need BOUND <= LARGER. */
2255 : 1816 : if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
2256 : : bound, arg_false)))
2257 : : return false;
2258 : : }
2259 : 756 : else if (operand_equal_for_phi_arg_p (arg_false, smaller)
2260 : 756 : || (alt_smaller
2261 : 178 : && operand_equal_for_phi_arg_p (arg_false, alt_smaller)))
2262 : : {
2263 : : /* Case
2264 : :
2265 : : if (smaller < larger)
2266 : : {
2267 : : r' = MIN_EXPR (larger, bound)
2268 : : }
2269 : : r = PHI <r', smaller> --> to be turned to MAX_EXPR. */
2270 : 184 : if (ass_code != MIN_EXPR)
2271 : : return false;
2272 : :
2273 : 166 : minmax = MAX_EXPR;
2274 : 166 : if (operand_equal_for_phi_arg_p (op0, larger)
2275 : 166 : || (alt_larger
2276 : 10 : && operand_equal_for_phi_arg_p (op0, alt_larger)))
2277 : : bound = op1;
2278 : 11 : else if (operand_equal_for_phi_arg_p (op1, larger)
2279 : 11 : || (alt_larger
2280 : 10 : && operand_equal_for_phi_arg_p (op1, alt_larger)))
2281 : : bound = op0;
2282 : : else
2283 : 0 : return false;
2284 : :
2285 : : /* We need BOUND >= SMALLER. */
2286 : 166 : if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
2287 : : bound, arg_false)))
2288 : : return false;
2289 : : }
2290 : : else
2291 : 572 : return false;
2292 : : }
2293 : : else
2294 : : {
2295 : : /* We got here if the condition is false, i.e., SMALLER > LARGER. */
2296 : 286 : if (!operand_equal_for_phi_arg_p (lhs, arg_false))
2297 : : return false;
2298 : :
2299 : 286 : if (operand_equal_for_phi_arg_p (arg_true, larger)
2300 : 286 : || (alt_larger
2301 : 59 : && operand_equal_for_phi_arg_p (arg_true, alt_larger)))
2302 : : {
2303 : : /* Case
2304 : :
2305 : : if (smaller > larger)
2306 : : {
2307 : : r' = MIN_EXPR (smaller, bound)
2308 : : }
2309 : : r = PHI <r', larger> --> to be turned to MAX_EXPR. */
2310 : 21 : if (ass_code != MIN_EXPR)
2311 : : return false;
2312 : :
2313 : 21 : minmax = MAX_EXPR;
2314 : 21 : if (operand_equal_for_phi_arg_p (op0, smaller)
2315 : 21 : || (alt_smaller
2316 : 0 : && operand_equal_for_phi_arg_p (op0, alt_smaller)))
2317 : : bound = op1;
2318 : 0 : else if (operand_equal_for_phi_arg_p (op1, smaller)
2319 : 0 : || (alt_smaller
2320 : 0 : && operand_equal_for_phi_arg_p (op1, alt_smaller)))
2321 : : bound = op0;
2322 : : else
2323 : 0 : return false;
2324 : :
2325 : : /* We need BOUND >= LARGER. */
2326 : 21 : if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
2327 : : bound, arg_true)))
2328 : : return false;
2329 : : }
2330 : 265 : else if (operand_equal_for_phi_arg_p (arg_true, smaller)
2331 : 265 : || (alt_smaller
2332 : 24 : && operand_equal_for_phi_arg_p (arg_true, alt_smaller)))
2333 : : {
2334 : : /* Case
2335 : :
2336 : : if (smaller > larger)
2337 : : {
2338 : : r' = MAX_EXPR (larger, bound)
2339 : : }
2340 : : r = PHI <r', smaller> --> to be turned to MIN_EXPR. */
2341 : 7 : if (ass_code != MAX_EXPR)
2342 : : return false;
2343 : :
2344 : 7 : minmax = MIN_EXPR;
2345 : 7 : if (operand_equal_for_phi_arg_p (op0, larger))
2346 : : bound = op1;
2347 : 4 : else if (operand_equal_for_phi_arg_p (op1, larger))
2348 : : bound = op0;
2349 : : else
2350 : : return false;
2351 : :
2352 : : /* We need BOUND <= SMALLER. */
2353 : 3 : if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
2354 : : bound, arg_true)))
2355 : : return false;
2356 : : }
2357 : : else
2358 : 258 : return false;
2359 : : }
2360 : :
2361 : : /* Move the statement from the middle block. */
2362 : 18 : gsi = gsi_last_bb (cond_bb);
2363 : 18 : gsi_from = gsi_last_nondebug_bb (middle_bb);
2364 : 18 : reset_flow_sensitive_info (SINGLE_SSA_TREE_OPERAND (gsi_stmt (gsi_from),
2365 : : SSA_OP_DEF));
2366 : 18 : gsi_move_before (&gsi_from, &gsi);
2367 : : }
2368 : : else
2369 : : return false;
2370 : :
2371 : : /* Emit the statement to compute min/max. */
2372 : 3866 : gimple_seq stmts = NULL;
2373 : 3866 : tree phi_result = gimple_phi_result (phi);
2374 : :
2375 : : /* When we can't use a MIN/MAX_EXPR still make sure the expression
2376 : : stays in a form to be recognized by ISA that map to IEEE x > y ? x : y
2377 : : semantics (that's not IEEE max semantics). */
2378 : 3866 : if (HONOR_NANS (type) || HONOR_SIGNED_ZEROS (type))
2379 : : {
2380 : 3666 : result = gimple_build (&stmts, cmp, boolean_type_node,
2381 : : gimple_cond_lhs (cond), rhs);
2382 : 3666 : result = gimple_build (&stmts, COND_EXPR, TREE_TYPE (phi_result),
2383 : : result, arg_true, arg_false);
2384 : : }
2385 : : else
2386 : 200 : result = gimple_build (&stmts, minmax, TREE_TYPE (phi_result), arg0, arg1);
2387 : :
2388 : 3866 : gsi = gsi_last_bb (cond_bb);
2389 : 3866 : gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2390 : :
2391 : 3866 : replace_phi_edge_with_variable (cond_bb, e1, phi, result);
2392 : :
2393 : 3866 : return true;
2394 : : }
2395 : :
2396 : : /* Attempt to optimize (x <=> y) cmp 0 and similar comparisons.
2397 : : For strong ordering <=> try to match something like:
2398 : : <bb 2> : // cond3_bb (== cond2_bb)
2399 : : if (x_4(D) != y_5(D))
2400 : : goto <bb 3>; [INV]
2401 : : else
2402 : : goto <bb 6>; [INV]
2403 : :
2404 : : <bb 3> : // cond_bb
2405 : : if (x_4(D) < y_5(D))
2406 : : goto <bb 6>; [INV]
2407 : : else
2408 : : goto <bb 4>; [INV]
2409 : :
2410 : : <bb 4> : // middle_bb
2411 : :
2412 : : <bb 6> : // phi_bb
2413 : : # iftmp.0_2 = PHI <1(4), 0(2), -1(3)>
2414 : : _1 = iftmp.0_2 == 0;
2415 : :
2416 : : and for partial ordering <=> something like:
2417 : :
2418 : : <bb 2> : // cond3_bb
2419 : : if (a_3(D) == b_5(D))
2420 : : goto <bb 6>; [50.00%]
2421 : : else
2422 : : goto <bb 3>; [50.00%]
2423 : :
2424 : : <bb 3> [local count: 536870913]: // cond2_bb
2425 : : if (a_3(D) < b_5(D))
2426 : : goto <bb 6>; [50.00%]
2427 : : else
2428 : : goto <bb 4>; [50.00%]
2429 : :
2430 : : <bb 4> [local count: 268435456]: // cond_bb
2431 : : if (a_3(D) > b_5(D))
2432 : : goto <bb 6>; [50.00%]
2433 : : else
2434 : : goto <bb 5>; [50.00%]
2435 : :
2436 : : <bb 5> [local count: 134217728]: // middle_bb
2437 : :
2438 : : <bb 6> [local count: 1073741824]: // phi_bb
2439 : : # SR.27_4 = PHI <0(2), -1(3), 1(4), 2(5)>
2440 : : _2 = SR.27_4 > 0; */
2441 : :
2442 : : static bool
2443 : 615627 : spaceship_replacement (basic_block cond_bb, basic_block middle_bb,
2444 : : edge e0, edge e1, gphi *phi,
2445 : : tree arg0, tree arg1)
2446 : : {
2447 : 615627 : tree phires = gimple_phi_result (phi);
2448 : 1226666 : if (!INTEGRAL_TYPE_P (TREE_TYPE (phires))
2449 : 481099 : || TYPE_UNSIGNED (TREE_TYPE (phires))
2450 : 255094 : || !tree_fits_shwi_p (arg0)
2451 : 68385 : || !tree_fits_shwi_p (arg1)
2452 : 38562 : || !IN_RANGE (tree_to_shwi (arg0), -1, 2)
2453 : 635523 : || !IN_RANGE (tree_to_shwi (arg1), -1, 2))
2454 : : return false;
2455 : :
2456 : 16965 : basic_block phi_bb = gimple_bb (phi);
2457 : 16965 : gcc_assert (phi_bb == e0->dest && phi_bb == e1->dest);
2458 : 16965 : if (!IN_RANGE (EDGE_COUNT (phi_bb->preds), 3, 4))
2459 : : return false;
2460 : :
2461 : 6564 : use_operand_p use_p;
2462 : 6564 : gimple *use_stmt;
2463 : 6564 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (phires))
2464 : : return false;
2465 : 6564 : if (!single_imm_use (phires, &use_p, &use_stmt))
2466 : : return false;
2467 : 5822 : enum tree_code cmp;
2468 : 5822 : tree lhs, rhs;
2469 : 5822 : gimple *orig_use_stmt = use_stmt;
2470 : 5822 : tree orig_use_lhs = NULL_TREE;
2471 : 5822 : int prec = TYPE_PRECISION (TREE_TYPE (phires));
2472 : 5822 : bool is_cast = false;
2473 : :
2474 : : /* Deal with the case when match.pd has rewritten the (res & ~1) == 0
2475 : : into res <= 1 and has left a type-cast for signed types. */
2476 : 5822 : if (gimple_assign_cast_p (use_stmt))
2477 : : {
2478 : 190 : orig_use_lhs = gimple_assign_lhs (use_stmt);
2479 : : /* match.pd would have only done this for a signed type,
2480 : : so the conversion must be to an unsigned one. */
2481 : 190 : tree ty1 = TREE_TYPE (gimple_assign_rhs1 (use_stmt));
2482 : 190 : tree ty2 = TREE_TYPE (orig_use_lhs);
2483 : :
2484 : 190 : if (!TYPE_UNSIGNED (ty2) || !INTEGRAL_TYPE_P (ty2))
2485 : : return false;
2486 : 142 : if (TYPE_PRECISION (ty1) > TYPE_PRECISION (ty2))
2487 : : return false;
2488 : 58 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
2489 : : return false;
2490 : 58 : if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
2491 : : return false;
2492 : :
2493 : : is_cast = true;
2494 : : }
2495 : 5632 : else if (is_gimple_assign (use_stmt)
2496 : 1949 : && gimple_assign_rhs_code (use_stmt) == BIT_AND_EXPR
2497 : 1 : && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST
2498 : 7582 : && (wi::to_wide (gimple_assign_rhs2 (use_stmt))
2499 : 5634 : == wi::shifted_mask (1, prec - 1, false, prec)))
2500 : : {
2501 : : /* For partial_ordering result operator>= with unspec as second
2502 : : argument is (res & 1) == res, folded by match.pd into
2503 : : (res & ~1) == 0. */
2504 : 0 : orig_use_lhs = gimple_assign_lhs (use_stmt);
2505 : 0 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
2506 : : return false;
2507 : 0 : if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
2508 : : return false;
2509 : : }
2510 : 5689 : if (gimple_code (use_stmt) == GIMPLE_COND)
2511 : : {
2512 : 1787 : cmp = gimple_cond_code (use_stmt);
2513 : 1787 : lhs = gimple_cond_lhs (use_stmt);
2514 : 1787 : rhs = gimple_cond_rhs (use_stmt);
2515 : : }
2516 : 3902 : else if (is_gimple_assign (use_stmt))
2517 : : {
2518 : 2004 : if (gimple_assign_rhs_class (use_stmt) == GIMPLE_BINARY_RHS)
2519 : : {
2520 : 1158 : cmp = gimple_assign_rhs_code (use_stmt);
2521 : 1158 : lhs = gimple_assign_rhs1 (use_stmt);
2522 : 1158 : rhs = gimple_assign_rhs2 (use_stmt);
2523 : : }
2524 : 846 : else if (gimple_assign_rhs_code (use_stmt) == COND_EXPR)
2525 : : {
2526 : 0 : tree cond = gimple_assign_rhs1 (use_stmt);
2527 : 0 : if (!COMPARISON_CLASS_P (cond))
2528 : : return false;
2529 : 0 : cmp = TREE_CODE (cond);
2530 : 0 : lhs = TREE_OPERAND (cond, 0);
2531 : 0 : rhs = TREE_OPERAND (cond, 1);
2532 : : }
2533 : : else
2534 : : return false;
2535 : : }
2536 : : else
2537 : : return false;
2538 : 2945 : switch (cmp)
2539 : : {
2540 : 2438 : case EQ_EXPR:
2541 : 2438 : case NE_EXPR:
2542 : 2438 : case LT_EXPR:
2543 : 2438 : case GT_EXPR:
2544 : 2438 : case LE_EXPR:
2545 : 2438 : case GE_EXPR:
2546 : 2438 : break;
2547 : : default:
2548 : : return false;
2549 : : }
2550 : 4840 : if (lhs != (orig_use_lhs ? orig_use_lhs : phires)
2551 : 2271 : || !tree_fits_shwi_p (rhs)
2552 : 1920 : || !IN_RANGE (tree_to_shwi (rhs), -1, 1))
2553 : : return false;
2554 : :
2555 : 1894 : if (is_cast)
2556 : : {
2557 : 36 : if (TREE_CODE (rhs) != INTEGER_CST)
2558 : : return false;
2559 : : /* As for -ffast-math we assume the 2 return to be
2560 : : impossible, canonicalize (unsigned) res <= 1U or
2561 : : (unsigned) res < 2U into res >= 0 and (unsigned) res > 1U
2562 : : or (unsigned) res >= 2U as res < 0. */
2563 : 36 : switch (cmp)
2564 : : {
2565 : 32 : case LE_EXPR:
2566 : 32 : if (!integer_onep (rhs))
2567 : : return false;
2568 : : cmp = GE_EXPR;
2569 : : break;
2570 : 0 : case LT_EXPR:
2571 : 0 : if (wi::ne_p (wi::to_widest (rhs), 2))
2572 : : return false;
2573 : : cmp = GE_EXPR;
2574 : : break;
2575 : 4 : case GT_EXPR:
2576 : 4 : if (!integer_onep (rhs))
2577 : : return false;
2578 : : cmp = LT_EXPR;
2579 : : break;
2580 : 0 : case GE_EXPR:
2581 : 0 : if (wi::ne_p (wi::to_widest (rhs), 2))
2582 : : return false;
2583 : : cmp = LT_EXPR;
2584 : : break;
2585 : : default:
2586 : : return false;
2587 : : }
2588 : 36 : rhs = build_zero_cst (TREE_TYPE (phires));
2589 : : }
2590 : 1858 : else if (orig_use_lhs)
2591 : : {
2592 : 0 : if ((cmp != EQ_EXPR && cmp != NE_EXPR) || !integer_zerop (rhs))
2593 : 0 : return false;
2594 : : /* As for -ffast-math we assume the 2 return to be
2595 : : impossible, canonicalize (res & ~1) == 0 into
2596 : : res >= 0 and (res & ~1) != 0 as res < 0. */
2597 : 0 : cmp = cmp == EQ_EXPR ? GE_EXPR : LT_EXPR;
2598 : : }
2599 : :
2600 : 1894 : if (!empty_block_p (middle_bb))
2601 : : return false;
2602 : :
2603 : 3788 : gcond *cond1 = as_a <gcond *> (*gsi_last_bb (cond_bb));
2604 : 1894 : enum tree_code cmp1 = gimple_cond_code (cond1);
2605 : 1894 : switch (cmp1)
2606 : : {
2607 : 1724 : case LT_EXPR:
2608 : 1724 : case LE_EXPR:
2609 : 1724 : case GT_EXPR:
2610 : 1724 : case GE_EXPR:
2611 : 1724 : break;
2612 : : default:
2613 : : return false;
2614 : : }
2615 : 1724 : tree lhs1 = gimple_cond_lhs (cond1);
2616 : 1724 : tree rhs1 = gimple_cond_rhs (cond1);
2617 : 1724 : if (TREE_CODE (lhs1) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs1))
2618 : : return false;
2619 : 1724 : if (TREE_CODE (rhs1) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1))
2620 : : return false;
2621 : :
2622 : 1724 : if (!single_pred_p (cond_bb) || !cond_only_block_p (cond_bb))
2623 : 16 : return false;
2624 : :
2625 : 1708 : basic_block cond2_bb = single_pred (cond_bb);
2626 : 1708 : if (EDGE_COUNT (cond2_bb->succs) != 2)
2627 : : return false;
2628 : 1708 : edge cond2_phi_edge;
2629 : 1708 : if (EDGE_SUCC (cond2_bb, 0)->dest == cond_bb)
2630 : : {
2631 : 1436 : if (EDGE_SUCC (cond2_bb, 1)->dest != phi_bb)
2632 : : return false;
2633 : : cond2_phi_edge = EDGE_SUCC (cond2_bb, 1);
2634 : : }
2635 : 272 : else if (EDGE_SUCC (cond2_bb, 0)->dest != phi_bb)
2636 : : return false;
2637 : : else
2638 : : cond2_phi_edge = EDGE_SUCC (cond2_bb, 0);
2639 : 1708 : tree arg2 = gimple_phi_arg_def (phi, cond2_phi_edge->dest_idx);
2640 : 1708 : if (!tree_fits_shwi_p (arg2))
2641 : : return false;
2642 : 3416 : gcond *cond2 = safe_dyn_cast <gcond *> (*gsi_last_bb (cond2_bb));
2643 : 1708 : if (!cond2)
2644 : : return false;
2645 : 1708 : enum tree_code cmp2 = gimple_cond_code (cond2);
2646 : 1708 : tree lhs2 = gimple_cond_lhs (cond2);
2647 : 1708 : tree rhs2 = gimple_cond_rhs (cond2);
2648 : 1708 : if (lhs2 == lhs1)
2649 : : {
2650 : 1708 : if (!operand_equal_p (rhs2, rhs1, 0))
2651 : : {
2652 : 212 : if ((cmp2 == EQ_EXPR || cmp2 == NE_EXPR)
2653 : 212 : && TREE_CODE (rhs1) == INTEGER_CST
2654 : 212 : && TREE_CODE (rhs2) == INTEGER_CST)
2655 : : {
2656 : : /* For integers, we can have cond2 x == 5
2657 : : and cond1 x < 5, x <= 4, x <= 5, x < 6,
2658 : : x > 5, x >= 6, x >= 5 or x > 4. */
2659 : 212 : if (tree_int_cst_lt (rhs1, rhs2))
2660 : : {
2661 : 212 : if (wi::ne_p (wi::to_wide (rhs1) + 1, wi::to_wide (rhs2)))
2662 : : return false;
2663 : 212 : if (cmp1 == LE_EXPR)
2664 : : cmp1 = LT_EXPR;
2665 : 0 : else if (cmp1 == GT_EXPR)
2666 : : cmp1 = GE_EXPR;
2667 : : else
2668 : : return false;
2669 : : }
2670 : : else
2671 : : {
2672 : 0 : gcc_checking_assert (tree_int_cst_lt (rhs2, rhs1));
2673 : 0 : if (wi::ne_p (wi::to_wide (rhs2) + 1, wi::to_wide (rhs1)))
2674 : : return false;
2675 : 0 : if (cmp1 == LT_EXPR)
2676 : : cmp1 = LE_EXPR;
2677 : 0 : else if (cmp1 == GE_EXPR)
2678 : : cmp1 = GT_EXPR;
2679 : : else
2680 : : return false;
2681 : : }
2682 : : rhs1 = rhs2;
2683 : : }
2684 : : else
2685 : : return false;
2686 : : }
2687 : : }
2688 : 0 : else if (lhs2 == rhs1)
2689 : : {
2690 : 0 : if (rhs2 != lhs1)
2691 : : return false;
2692 : : }
2693 : : else
2694 : : return false;
2695 : :
2696 : 1708 : tree arg3 = arg2;
2697 : 1708 : basic_block cond3_bb = cond2_bb;
2698 : 1708 : edge cond3_phi_edge = cond2_phi_edge;
2699 : 1708 : gcond *cond3 = cond2;
2700 : 1708 : enum tree_code cmp3 = cmp2;
2701 : 1708 : tree lhs3 = lhs2;
2702 : 1708 : tree rhs3 = rhs2;
2703 : 1708 : if (EDGE_COUNT (phi_bb->preds) == 4)
2704 : : {
2705 : 316 : if (absu_hwi (tree_to_shwi (arg2)) != 1)
2706 : : return false;
2707 : 316 : if ((cond2_phi_edge->flags & EDGE_FALSE_VALUE)
2708 : 316 : && HONOR_NANS (TREE_TYPE (lhs1)))
2709 : : return false;
2710 : 316 : if (e1->flags & EDGE_TRUE_VALUE)
2711 : : {
2712 : 316 : if (tree_to_shwi (arg0) != 2
2713 : 316 : || absu_hwi (tree_to_shwi (arg1)) != 1
2714 : 632 : || wi::to_widest (arg1) == wi::to_widest (arg2))
2715 : 0 : return false;
2716 : : }
2717 : 0 : else if (tree_to_shwi (arg1) != 2
2718 : 0 : || absu_hwi (tree_to_shwi (arg0)) != 1
2719 : 0 : || wi::to_widest (arg0) == wi::to_widest (arg2))
2720 : 0 : return false;
2721 : 316 : switch (cmp2)
2722 : : {
2723 : 316 : case LT_EXPR:
2724 : 316 : case LE_EXPR:
2725 : 316 : case GT_EXPR:
2726 : 316 : case GE_EXPR:
2727 : 316 : break;
2728 : : default:
2729 : : return false;
2730 : : }
2731 : : /* if (x < y) goto phi_bb; else fallthru;
2732 : : if (x > y) goto phi_bb; else fallthru;
2733 : : bbx:;
2734 : : phi_bb:;
2735 : : is ok, but if x and y are swapped in one of the comparisons,
2736 : : or the comparisons are the same and operands not swapped,
2737 : : or the true and false edges are swapped, it is not.
2738 : : For HONOR_NANS, the edge flags are irrelevant and the comparisons
2739 : : must be different for non-swapped operands and same for swapped
2740 : : operands. */
2741 : 316 : if ((lhs2 == lhs1)
2742 : 316 : ^ (HONOR_NANS (TREE_TYPE (lhs1))
2743 : 316 : ? ((cmp2 == LT_EXPR || cmp2 == LE_EXPR)
2744 : 216 : != (cmp1 == LT_EXPR || cmp1 == LE_EXPR))
2745 : 100 : : (((cond2_phi_edge->flags
2746 : 100 : & ((cmp2 == LT_EXPR || cmp2 == LE_EXPR)
2747 : 100 : ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE)) != 0)
2748 : 200 : != ((e1->flags
2749 : 100 : & ((cmp1 == LT_EXPR || cmp1 == LE_EXPR)
2750 : 100 : ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE)) != 0))))
2751 : : return false;
2752 : 316 : if (!single_pred_p (cond2_bb) || !cond_only_block_p (cond2_bb))
2753 : 0 : return false;
2754 : 316 : cond3_bb = single_pred (cond2_bb);
2755 : 316 : if (EDGE_COUNT (cond2_bb->succs) != 2)
2756 : : return false;
2757 : 316 : if (EDGE_SUCC (cond3_bb, 0)->dest == cond2_bb)
2758 : : {
2759 : 220 : if (EDGE_SUCC (cond3_bb, 1)->dest != phi_bb)
2760 : : return false;
2761 : : cond3_phi_edge = EDGE_SUCC (cond3_bb, 1);
2762 : : }
2763 : 96 : else if (EDGE_SUCC (cond3_bb, 0)->dest != phi_bb)
2764 : : return false;
2765 : : else
2766 : : cond3_phi_edge = EDGE_SUCC (cond3_bb, 0);
2767 : 316 : arg3 = gimple_phi_arg_def (phi, cond3_phi_edge->dest_idx);
2768 : 614611 : cond3 = safe_dyn_cast <gcond *> (*gsi_last_bb (cond3_bb));
2769 : 316 : if (!cond3)
2770 : : return false;
2771 : 316 : cmp3 = gimple_cond_code (cond3);
2772 : 316 : lhs3 = gimple_cond_lhs (cond3);
2773 : 316 : rhs3 = gimple_cond_rhs (cond3);
2774 : 316 : if (lhs3 == lhs1)
2775 : : {
2776 : 316 : if (!operand_equal_p (rhs3, rhs1, 0))
2777 : : return false;
2778 : : }
2779 : 0 : else if (lhs3 == rhs1)
2780 : : {
2781 : 0 : if (rhs3 != lhs1)
2782 : : return false;
2783 : : }
2784 : : else
2785 : : return false;
2786 : : }
2787 : 1392 : else if (absu_hwi (tree_to_shwi (arg0)) != 1
2788 : 1392 : || absu_hwi (tree_to_shwi (arg1)) != 1
2789 : 2784 : || wi::to_widest (arg0) == wi::to_widest (arg1)
2790 : 2784 : || HONOR_NANS (TREE_TYPE (lhs1)))
2791 : 0 : return false;
2792 : :
2793 : 1708 : if (!integer_zerop (arg3) || (cmp3 != EQ_EXPR && cmp3 != NE_EXPR))
2794 : : return false;
2795 : 1708 : if ((cond3_phi_edge->flags & (cmp3 == EQ_EXPR
2796 : 1708 : ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE)) == 0)
2797 : : return false;
2798 : :
2799 : : /* lhs1 one_cmp rhs1 results in phires of 1. */
2800 : 1708 : enum tree_code one_cmp;
2801 : 3416 : if ((cmp1 == LT_EXPR || cmp1 == LE_EXPR)
2802 : 1794 : ^ (!integer_onep ((e1->flags & EDGE_TRUE_VALUE) ? arg1 : arg0)))
2803 : : one_cmp = LT_EXPR;
2804 : : else
2805 : 1472 : one_cmp = GT_EXPR;
2806 : :
2807 : 1708 : enum tree_code res_cmp;
2808 : 1708 : bool negate_p = false;
2809 : 1708 : switch (cmp)
2810 : : {
2811 : 996 : case EQ_EXPR:
2812 : 996 : if (integer_zerop (rhs) && !HONOR_NANS (TREE_TYPE (lhs1)))
2813 : : res_cmp = EQ_EXPR;
2814 : 912 : else if (integer_minus_onep (rhs))
2815 : 490 : res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
2816 : 422 : else if (integer_onep (rhs))
2817 : : res_cmp = one_cmp;
2818 : : else
2819 : : return false;
2820 : : break;
2821 : 630 : case NE_EXPR:
2822 : 630 : if (integer_zerop (rhs) && !HONOR_NANS (TREE_TYPE (lhs1)))
2823 : : res_cmp = NE_EXPR;
2824 : 594 : else if (integer_minus_onep (rhs))
2825 : 372 : res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
2826 : 222 : else if (integer_onep (rhs))
2827 : 198 : res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
2828 : : else
2829 : : return false;
2830 : 606 : if (HONOR_NANS (TREE_TYPE (lhs1)))
2831 : : negate_p = true;
2832 : : break;
2833 : 5 : case LT_EXPR:
2834 : 5 : if (integer_onep (rhs))
2835 : 0 : res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
2836 : 5 : else if (integer_zerop (rhs))
2837 : : {
2838 : 5 : if (HONOR_NANS (TREE_TYPE (lhs1)) && orig_use_lhs)
2839 : 5 : negate_p = true;
2840 : 5 : res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
2841 : : }
2842 : : else
2843 : : return false;
2844 : : break;
2845 : 32 : case LE_EXPR:
2846 : 32 : if (integer_zerop (rhs))
2847 : 32 : res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
2848 : 0 : else if (integer_minus_onep (rhs))
2849 : 0 : res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
2850 : : else
2851 : : return false;
2852 : : break;
2853 : 12 : case GT_EXPR:
2854 : 12 : if (integer_minus_onep (rhs))
2855 : 0 : res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
2856 : 12 : else if (integer_zerop (rhs))
2857 : : res_cmp = one_cmp;
2858 : : else
2859 : : return false;
2860 : 12 : if (HONOR_NANS (TREE_TYPE (lhs1)))
2861 : : negate_p = true;
2862 : : break;
2863 : 33 : case GE_EXPR:
2864 : 33 : if (integer_zerop (rhs))
2865 : : {
2866 : 33 : if (HONOR_NANS (TREE_TYPE (lhs1)) && !orig_use_lhs)
2867 : 33 : negate_p = true;
2868 : 33 : res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
2869 : : }
2870 : 0 : else if (integer_onep (rhs))
2871 : : {
2872 : 0 : if (HONOR_NANS (TREE_TYPE (lhs1)))
2873 : : negate_p = true;
2874 : : res_cmp = one_cmp;
2875 : : }
2876 : : else
2877 : : return false;
2878 : : break;
2879 : 0 : default:
2880 : 0 : gcc_unreachable ();
2881 : : }
2882 : :
2883 : 66 : tree clhs1 = lhs1, crhs1 = rhs1;
2884 : 38 : if (negate_p)
2885 : : {
2886 : 28 : if (cfun->can_throw_non_call_exceptions)
2887 : 0 : return false;
2888 : 28 : res_cmp = invert_tree_comparison (res_cmp, false);
2889 : 28 : clhs1 = make_ssa_name (boolean_type_node);
2890 : 28 : gimple *g = gimple_build_assign (clhs1, res_cmp, lhs1, rhs1);
2891 : 28 : gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
2892 : 28 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2893 : 28 : crhs1 = boolean_false_node;
2894 : 28 : res_cmp = EQ_EXPR;
2895 : : }
2896 : :
2897 : 1648 : if (gimple_code (use_stmt) == GIMPLE_COND)
2898 : : {
2899 : 1117 : gcond *use_cond = as_a <gcond *> (use_stmt);
2900 : 1117 : gimple_cond_set_code (use_cond, res_cmp);
2901 : 1117 : gimple_cond_set_lhs (use_cond, clhs1);
2902 : 1117 : gimple_cond_set_rhs (use_cond, crhs1);
2903 : : }
2904 : 531 : else if (gimple_assign_rhs_class (use_stmt) == GIMPLE_BINARY_RHS)
2905 : : {
2906 : 531 : gimple_assign_set_rhs_code (use_stmt, res_cmp);
2907 : 531 : gimple_assign_set_rhs1 (use_stmt, clhs1);
2908 : 531 : gimple_assign_set_rhs2 (use_stmt, crhs1);
2909 : : }
2910 : : else
2911 : : {
2912 : 0 : tree cond = build2 (res_cmp, TREE_TYPE (gimple_assign_rhs1 (use_stmt)),
2913 : : clhs1, crhs1);
2914 : 0 : gimple_assign_set_rhs1 (use_stmt, cond);
2915 : : }
2916 : 1648 : update_stmt (use_stmt);
2917 : :
2918 : 1648 : if (MAY_HAVE_DEBUG_BIND_STMTS)
2919 : : {
2920 : 1368 : use_operand_p use_p;
2921 : 1368 : imm_use_iterator iter;
2922 : 1368 : bool has_debug_uses = false;
2923 : 1368 : bool has_cast_debug_uses = false;
2924 : 1388 : FOR_EACH_IMM_USE_FAST (use_p, iter, phires)
2925 : : {
2926 : 1388 : gimple *use_stmt = USE_STMT (use_p);
2927 : 1388 : if (orig_use_lhs && use_stmt == orig_use_stmt)
2928 : 20 : continue;
2929 : 1368 : gcc_assert (is_gimple_debug (use_stmt));
2930 : : has_debug_uses = true;
2931 : : break;
2932 : : }
2933 : 1368 : if (orig_use_lhs)
2934 : : {
2935 : 20 : if (!has_debug_uses || is_cast)
2936 : 20 : FOR_EACH_IMM_USE_FAST (use_p, iter, orig_use_lhs)
2937 : : {
2938 : 0 : gimple *use_stmt = USE_STMT (use_p);
2939 : 0 : gcc_assert (is_gimple_debug (use_stmt));
2940 : 0 : has_debug_uses = true;
2941 : 0 : if (is_cast)
2942 : 0 : has_cast_debug_uses = true;
2943 : : }
2944 : 20 : gimple_stmt_iterator gsi = gsi_for_stmt (orig_use_stmt);
2945 : 20 : tree zero = build_zero_cst (TREE_TYPE (orig_use_lhs));
2946 : 20 : gimple_assign_set_rhs_with_ops (&gsi, INTEGER_CST, zero);
2947 : 20 : update_stmt (orig_use_stmt);
2948 : : }
2949 : :
2950 : 1368 : if (has_debug_uses)
2951 : : {
2952 : : /* If there are debug uses, emit something like:
2953 : : # DEBUG D#1 => i_2(D) > j_3(D) ? 1 : -1
2954 : : # DEBUG D#2 => i_2(D) == j_3(D) ? 0 : D#1
2955 : : where > stands for the comparison that yielded 1
2956 : : and replace debug uses of phi result with that D#2.
2957 : : Ignore the value of 2 if !HONOR_NANS, because if NaNs
2958 : : aren't expected, all floating point numbers should be
2959 : : comparable. If HONOR_NANS, emit something like:
2960 : : # DEBUG D#1 => i_2(D) < j_3(D) ? -1 : 2
2961 : : # DEBUG D#2 => i_2(D) > j_3(D) ? 1 : D#1
2962 : : # DEBUG D#3 => i_2(D) == j_3(D) ? 0 : D#2
2963 : : instead. */
2964 : 1368 : gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi));
2965 : 1368 : tree type = TREE_TYPE (phires);
2966 : 1368 : tree minus_one = build_int_cst (type, -1);
2967 : 1368 : if (HONOR_NANS (TREE_TYPE (lhs1)))
2968 : : {
2969 : 80 : tree temp3 = build_debug_expr_decl (type);
2970 : 160 : tree t = build2 (one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR,
2971 : : boolean_type_node, lhs1, rhs2);
2972 : 80 : t = build3 (COND_EXPR, type, t, minus_one,
2973 : 80 : build_int_cst (type, 2));
2974 : 80 : gimple *g = gimple_build_debug_bind (temp3, t, phi);
2975 : 80 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2976 : 80 : minus_one = temp3;
2977 : : }
2978 : 1368 : tree temp1 = build_debug_expr_decl (type);
2979 : 1368 : tree t = build2 (one_cmp, boolean_type_node, lhs1, rhs2);
2980 : 1368 : t = build3 (COND_EXPR, type, t, build_one_cst (type),
2981 : : minus_one);
2982 : 1368 : gimple *g = gimple_build_debug_bind (temp1, t, phi);
2983 : 1368 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2984 : 1368 : tree temp2 = build_debug_expr_decl (type);
2985 : 1368 : t = build2 (EQ_EXPR, boolean_type_node, lhs1, rhs2);
2986 : 1368 : t = build3 (COND_EXPR, type, t, build_zero_cst (type), temp1);
2987 : 1368 : g = gimple_build_debug_bind (temp2, t, phi);
2988 : 1368 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2989 : 1368 : replace_uses_by (phires, temp2);
2990 : 1368 : if (orig_use_lhs)
2991 : : {
2992 : 20 : if (has_cast_debug_uses
2993 : 20 : || (HONOR_NANS (TREE_TYPE (lhs1)) && !is_cast))
2994 : : {
2995 : 0 : tree temp3 = make_node (DEBUG_EXPR_DECL);
2996 : 0 : DECL_ARTIFICIAL (temp3) = 1;
2997 : 0 : TREE_TYPE (temp3) = TREE_TYPE (orig_use_lhs);
2998 : 0 : SET_DECL_MODE (temp3, TYPE_MODE (type));
2999 : 0 : if (has_cast_debug_uses)
3000 : 0 : t = fold_convert (TREE_TYPE (temp3), temp2);
3001 : : else
3002 : 0 : t = build2 (BIT_AND_EXPR, TREE_TYPE (temp3),
3003 : 0 : temp2, build_int_cst (TREE_TYPE (temp3),
3004 : 0 : ~1));
3005 : 0 : g = gimple_build_debug_bind (temp3, t, phi);
3006 : 0 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
3007 : 0 : replace_uses_by (orig_use_lhs, temp3);
3008 : : }
3009 : : else
3010 : 20 : replace_uses_by (orig_use_lhs, temp2);
3011 : : }
3012 : : }
3013 : : }
3014 : :
3015 : 1648 : if (orig_use_lhs)
3016 : : {
3017 : 36 : gimple_stmt_iterator gsi = gsi_for_stmt (orig_use_stmt);
3018 : 36 : gsi_remove (&gsi, true);
3019 : : }
3020 : :
3021 : 1648 : gimple_stmt_iterator psi = gsi_for_stmt (phi);
3022 : 1648 : remove_phi_node (&psi, true);
3023 : 1648 : statistics_counter_event (cfun, "spaceship replacement", 1);
3024 : :
3025 : 1648 : return true;
3026 : : }
3027 : :
3028 : : /* Optimize x ? __builtin_fun (x) : C, where C is __builtin_fun (0).
3029 : : Convert
3030 : :
3031 : : <bb 2>
3032 : : if (b_4(D) != 0)
3033 : : goto <bb 3>
3034 : : else
3035 : : goto <bb 4>
3036 : :
3037 : : <bb 3>
3038 : : _2 = (unsigned long) b_4(D);
3039 : : _9 = __builtin_popcountl (_2);
3040 : : OR
3041 : : _9 = __builtin_popcountl (b_4(D));
3042 : :
3043 : : <bb 4>
3044 : : c_12 = PHI <0(2), _9(3)>
3045 : :
3046 : : Into
3047 : : <bb 2>
3048 : : _2 = (unsigned long) b_4(D);
3049 : : _9 = __builtin_popcountl (_2);
3050 : : OR
3051 : : _9 = __builtin_popcountl (b_4(D));
3052 : :
3053 : : <bb 4>
3054 : : c_12 = PHI <_9(2)>
3055 : :
3056 : : Similarly for __builtin_clz or __builtin_ctz if
3057 : : C?Z_DEFINED_VALUE_AT_ZERO is 2, optab is present and
3058 : : instead of 0 above it uses the value from that macro. */
3059 : :
3060 : : static bool
3061 : 434396 : cond_removal_in_builtin_zero_pattern (basic_block cond_bb,
3062 : : basic_block middle_bb,
3063 : : edge e1, edge e2, gphi *phi,
3064 : : tree arg0, tree arg1)
3065 : : {
3066 : 434396 : gimple_stmt_iterator gsi, gsi_from;
3067 : 434396 : gimple *call;
3068 : 434396 : gimple *cast = NULL;
3069 : 434396 : tree lhs, arg;
3070 : :
3071 : : /* Check that
3072 : : _2 = (unsigned long) b_4(D);
3073 : : _9 = __builtin_popcountl (_2);
3074 : : OR
3075 : : _9 = __builtin_popcountl (b_4(D));
3076 : : are the only stmts in the middle_bb. */
3077 : :
3078 : 434396 : gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
3079 : 434396 : if (gsi_end_p (gsi))
3080 : : return false;
3081 : 269789 : cast = gsi_stmt (gsi);
3082 : 269789 : gsi_next_nondebug (&gsi);
3083 : 269789 : if (!gsi_end_p (gsi))
3084 : : {
3085 : 135597 : call = gsi_stmt (gsi);
3086 : 135597 : gsi_next_nondebug (&gsi);
3087 : 135597 : if (!gsi_end_p (gsi))
3088 : : return false;
3089 : : }
3090 : : else
3091 : : {
3092 : : call = cast;
3093 : : cast = NULL;
3094 : : }
3095 : :
3096 : : /* Check that we have a popcount/clz/ctz builtin. */
3097 : 183464 : if (!is_gimple_call (call))
3098 : : return false;
3099 : :
3100 : 6733 : lhs = gimple_get_lhs (call);
3101 : :
3102 : 6733 : if (lhs == NULL_TREE)
3103 : : return false;
3104 : :
3105 : 6707 : combined_fn cfn = gimple_call_combined_fn (call);
3106 : 6707 : if (gimple_call_num_args (call) != 1
3107 : 6707 : && (gimple_call_num_args (call) != 2
3108 : : || cfn == CFN_CLZ
3109 : 612 : || cfn == CFN_CTZ))
3110 : : return false;
3111 : :
3112 : 3689 : arg = gimple_call_arg (call, 0);
3113 : :
3114 : 3689 : internal_fn ifn = IFN_LAST;
3115 : 3689 : int val = 0;
3116 : 3689 : bool any_val = false;
3117 : 3689 : switch (cfn)
3118 : : {
3119 : : case CFN_BUILT_IN_BSWAP16:
3120 : : case CFN_BUILT_IN_BSWAP32:
3121 : : case CFN_BUILT_IN_BSWAP64:
3122 : : case CFN_BUILT_IN_BSWAP128:
3123 : : CASE_CFN_FFS:
3124 : : CASE_CFN_PARITY:
3125 : : CASE_CFN_POPCOUNT:
3126 : : break;
3127 : 1005 : CASE_CFN_CLZ:
3128 : 1005 : if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
3129 : : {
3130 : 1005 : tree type = TREE_TYPE (arg);
3131 : 1005 : if (TREE_CODE (type) == BITINT_TYPE)
3132 : : {
3133 : 4 : if (gimple_call_num_args (call) == 1)
3134 : : {
3135 : : any_val = true;
3136 : : ifn = IFN_CLZ;
3137 : : break;
3138 : : }
3139 : 0 : if (!tree_fits_shwi_p (gimple_call_arg (call, 1)))
3140 : : return false;
3141 : 0 : HOST_WIDE_INT at_zero = tree_to_shwi (gimple_call_arg (call, 1));
3142 : 0 : if ((int) at_zero != at_zero)
3143 : : return false;
3144 : 0 : ifn = IFN_CLZ;
3145 : 0 : val = at_zero;
3146 : 0 : break;
3147 : : }
3148 : 1001 : if (direct_internal_fn_supported_p (IFN_CLZ, type, OPTIMIZE_FOR_BOTH)
3149 : 1977 : && CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type),
3150 : : val) == 2)
3151 : : {
3152 : : ifn = IFN_CLZ;
3153 : : break;
3154 : : }
3155 : : }
3156 : : return false;
3157 : 245 : CASE_CFN_CTZ:
3158 : 245 : if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
3159 : : {
3160 : 245 : tree type = TREE_TYPE (arg);
3161 : 245 : if (TREE_CODE (type) == BITINT_TYPE)
3162 : : {
3163 : 4 : if (gimple_call_num_args (call) == 1)
3164 : : {
3165 : : any_val = true;
3166 : : ifn = IFN_CTZ;
3167 : : break;
3168 : : }
3169 : 0 : if (!tree_fits_shwi_p (gimple_call_arg (call, 1)))
3170 : : return false;
3171 : 0 : HOST_WIDE_INT at_zero = tree_to_shwi (gimple_call_arg (call, 1));
3172 : 0 : if ((int) at_zero != at_zero)
3173 : : return false;
3174 : 0 : ifn = IFN_CTZ;
3175 : 0 : val = at_zero;
3176 : 0 : break;
3177 : : }
3178 : 241 : if (direct_internal_fn_supported_p (IFN_CTZ, type, OPTIMIZE_FOR_BOTH)
3179 : 461 : && CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type),
3180 : : val) == 2)
3181 : : {
3182 : : ifn = IFN_CTZ;
3183 : : break;
3184 : : }
3185 : : }
3186 : : return false;
3187 : 3 : case CFN_BUILT_IN_CLRSB:
3188 : 3 : val = TYPE_PRECISION (integer_type_node) - 1;
3189 : 3 : break;
3190 : 3 : case CFN_BUILT_IN_CLRSBL:
3191 : 3 : val = TYPE_PRECISION (long_integer_type_node) - 1;
3192 : 3 : break;
3193 : 3 : case CFN_BUILT_IN_CLRSBLL:
3194 : 3 : val = TYPE_PRECISION (long_long_integer_type_node) - 1;
3195 : 3 : break;
3196 : : default:
3197 : : return false;
3198 : : }
3199 : :
3200 : 133 : if (cast)
3201 : : {
3202 : : /* We have a cast stmt feeding popcount/clz/ctz builtin. */
3203 : : /* Check that we have a cast prior to that. */
3204 : 68 : if (gimple_code (cast) != GIMPLE_ASSIGN
3205 : 68 : || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (cast)))
3206 : : return false;
3207 : : /* Result of the cast stmt is the argument to the builtin. */
3208 : 38 : if (arg != gimple_assign_lhs (cast))
3209 : : return false;
3210 : 38 : arg = gimple_assign_rhs1 (cast);
3211 : : }
3212 : :
3213 : 206 : gcond *cond = dyn_cast <gcond *> (*gsi_last_bb (cond_bb));
3214 : :
3215 : : /* Cond_bb has a check for b_4 [!=|==] 0 before calling the popcount/clz/ctz
3216 : : builtin. */
3217 : 103 : if (!cond
3218 : 103 : || (gimple_cond_code (cond) != NE_EXPR
3219 : 10 : && gimple_cond_code (cond) != EQ_EXPR)
3220 : 103 : || !integer_zerop (gimple_cond_rhs (cond))
3221 : 103 : || arg != gimple_cond_lhs (cond))
3222 : 70 : return false;
3223 : :
3224 : : /* Canonicalize. */
3225 : 33 : if ((e2->flags & EDGE_TRUE_VALUE
3226 : 0 : && gimple_cond_code (cond) == NE_EXPR)
3227 : 33 : || (e1->flags & EDGE_TRUE_VALUE
3228 : 0 : && gimple_cond_code (cond) == EQ_EXPR))
3229 : : {
3230 : : std::swap (arg0, arg1);
3231 : : std::swap (e1, e2);
3232 : : }
3233 : :
3234 : : /* Check PHI arguments. */
3235 : 33 : if (lhs != arg0
3236 : 33 : || TREE_CODE (arg1) != INTEGER_CST)
3237 : : return false;
3238 : 25 : if (any_val)
3239 : : {
3240 : 0 : if (!tree_fits_shwi_p (arg1))
3241 : : return false;
3242 : 0 : HOST_WIDE_INT at_zero = tree_to_shwi (arg1);
3243 : 0 : if ((int) at_zero != at_zero)
3244 : : return false;
3245 : 0 : val = at_zero;
3246 : : }
3247 : 25 : else if (wi::to_wide (arg1) != val)
3248 : : return false;
3249 : :
3250 : : /* And insert the popcount/clz/ctz builtin and cast stmt before the
3251 : : cond_bb. */
3252 : 14 : gsi = gsi_last_bb (cond_bb);
3253 : 14 : if (cast)
3254 : : {
3255 : 14 : gsi_from = gsi_for_stmt (cast);
3256 : 14 : gsi_move_before (&gsi_from, &gsi);
3257 : 14 : reset_flow_sensitive_info (gimple_get_lhs (cast));
3258 : : }
3259 : 14 : gsi_from = gsi_for_stmt (call);
3260 : 14 : if (ifn == IFN_LAST
3261 : 14 : || (gimple_call_internal_p (call) && gimple_call_num_args (call) == 2))
3262 : 9 : gsi_move_before (&gsi_from, &gsi);
3263 : : else
3264 : : {
3265 : : /* For __builtin_c[lt]z* force .C[LT]Z ifn, because only
3266 : : the latter is well defined at zero. */
3267 : 5 : call = gimple_build_call_internal (ifn, 2, gimple_call_arg (call, 0),
3268 : 5 : build_int_cst (integer_type_node, val));
3269 : 5 : gimple_call_set_lhs (call, lhs);
3270 : 5 : gsi_insert_before (&gsi, call, GSI_SAME_STMT);
3271 : 5 : gsi_remove (&gsi_from, true);
3272 : : }
3273 : 14 : reset_flow_sensitive_info (lhs);
3274 : :
3275 : : /* Now update the PHI and remove unneeded bbs. */
3276 : 14 : replace_phi_edge_with_variable (cond_bb, e2, phi, lhs);
3277 : 14 : return true;
3278 : : }
3279 : :
3280 : : /* Auxiliary functions to determine the set of memory accesses which
3281 : : can't trap because they are preceded by accesses to the same memory
3282 : : portion. We do that for MEM_REFs, so we only need to track
3283 : : the SSA_NAME of the pointer indirectly referenced. The algorithm
3284 : : simply is a walk over all instructions in dominator order. When
3285 : : we see an MEM_REF we determine if we've already seen a same
3286 : : ref anywhere up to the root of the dominator tree. If we do the
3287 : : current access can't trap. If we don't see any dominating access
3288 : : the current access might trap, but might also make later accesses
3289 : : non-trapping, so we remember it. We need to be careful with loads
3290 : : or stores, for instance a load might not trap, while a store would,
3291 : : so if we see a dominating read access this doesn't mean that a later
3292 : : write access would not trap. Hence we also need to differentiate the
3293 : : type of access(es) seen.
3294 : :
3295 : : ??? We currently are very conservative and assume that a load might
3296 : : trap even if a store doesn't (write-only memory). This probably is
3297 : : overly conservative.
3298 : :
3299 : : We currently support a special case that for !TREE_ADDRESSABLE automatic
3300 : : variables, it could ignore whether something is a load or store because the
3301 : : local stack should be always writable. */
3302 : :
3303 : : /* A hash-table of references (MEM_REF/ARRAY_REF/COMPONENT_REF), and in which
3304 : : basic block an *_REF through it was seen, which would constitute a
3305 : : no-trap region for same accesses.
3306 : :
3307 : : Size is needed to support 2 MEM_REFs of different types, like
3308 : : MEM<double>(s_1) and MEM<long>(s_1), which would compare equal with
3309 : : OEP_ADDRESS_OF. */
3310 : : struct ref_to_bb
3311 : : {
3312 : : tree exp;
3313 : : HOST_WIDE_INT size;
3314 : : unsigned int phase;
3315 : : basic_block bb;
3316 : : };
3317 : :
3318 : : /* Hashtable helpers. */
3319 : :
3320 : : struct refs_hasher : free_ptr_hash<ref_to_bb>
3321 : : {
3322 : : static inline hashval_t hash (const ref_to_bb *);
3323 : : static inline bool equal (const ref_to_bb *, const ref_to_bb *);
3324 : : };
3325 : :
3326 : : /* Used for quick clearing of the hash-table when we see calls.
3327 : : Hash entries with phase < nt_call_phase are invalid. */
3328 : : static unsigned int nt_call_phase;
3329 : :
3330 : : /* The hash function. */
3331 : :
3332 : : inline hashval_t
3333 : 18589632 : refs_hasher::hash (const ref_to_bb *n)
3334 : : {
3335 : 18589632 : inchash::hash hstate;
3336 : 18589632 : inchash::add_expr (n->exp, hstate, OEP_ADDRESS_OF);
3337 : 18589632 : hstate.add_hwi (n->size);
3338 : 18589632 : return hstate.end ();
3339 : : }
3340 : :
3341 : : /* The equality function of *P1 and *P2. */
3342 : :
3343 : : inline bool
3344 : 13510655 : refs_hasher::equal (const ref_to_bb *n1, const ref_to_bb *n2)
3345 : : {
3346 : 13510655 : return operand_equal_p (n1->exp, n2->exp, OEP_ADDRESS_OF)
3347 : 13510655 : && n1->size == n2->size;
3348 : : }
3349 : :
3350 : : class nontrapping_dom_walker : public dom_walker
3351 : : {
3352 : : public:
3353 : 1006279 : nontrapping_dom_walker (cdi_direction direction, hash_set<tree> *ps)
3354 : 1006279 : : dom_walker (direction), m_nontrapping (ps), m_seen_refs (128)
3355 : 1006279 : {}
3356 : :
3357 : : edge before_dom_children (basic_block) final override;
3358 : : void after_dom_children (basic_block) final override;
3359 : :
3360 : : private:
3361 : :
3362 : : /* We see the expression EXP in basic block BB. If it's an interesting
3363 : : expression (an MEM_REF through an SSA_NAME) possibly insert the
3364 : : expression into the set NONTRAP or the hash table of seen expressions.
3365 : : STORE is true if this expression is on the LHS, otherwise it's on
3366 : : the RHS. */
3367 : : void add_or_mark_expr (basic_block, tree, bool);
3368 : :
3369 : : hash_set<tree> *m_nontrapping;
3370 : :
3371 : : /* The hash table for remembering what we've seen. */
3372 : : hash_table<refs_hasher> m_seen_refs;
3373 : : };
3374 : :
3375 : : /* Called by walk_dominator_tree, when entering the block BB. */
3376 : : edge
3377 : 10987976 : nontrapping_dom_walker::before_dom_children (basic_block bb)
3378 : : {
3379 : 10987976 : edge e;
3380 : 10987976 : edge_iterator ei;
3381 : 10987976 : gimple_stmt_iterator gsi;
3382 : :
3383 : : /* If we haven't seen all our predecessors, clear the hash-table. */
3384 : 24166342 : FOR_EACH_EDGE (e, ei, bb->preds)
3385 : 13819407 : if ((((size_t)e->src->aux) & 2) == 0)
3386 : : {
3387 : 641041 : nt_call_phase++;
3388 : 641041 : break;
3389 : : }
3390 : :
3391 : : /* Mark this BB as being on the path to dominator root and as visited. */
3392 : 10987976 : bb->aux = (void*)(1 | 2);
3393 : :
3394 : : /* And walk the statements in order. */
3395 : 93220990 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3396 : : {
3397 : 71245038 : gimple *stmt = gsi_stmt (gsi);
3398 : :
3399 : 71245038 : if ((gimple_code (stmt) == GIMPLE_ASM && gimple_vdef (stmt))
3400 : 71286720 : || (is_gimple_call (stmt)
3401 : 5299455 : && (!nonfreeing_call_p (stmt) || !nonbarrier_call_p (stmt))))
3402 : 4764549 : nt_call_phase++;
3403 : 80964431 : else if (gimple_assign_single_p (stmt) && !gimple_has_volatile_ops (stmt))
3404 : : {
3405 : 12508972 : add_or_mark_expr (bb, gimple_assign_lhs (stmt), true);
3406 : 12508972 : add_or_mark_expr (bb, gimple_assign_rhs1 (stmt), false);
3407 : : }
3408 : : }
3409 : 10987976 : return NULL;
3410 : : }
3411 : :
3412 : : /* Called by walk_dominator_tree, when basic block BB is exited. */
3413 : : void
3414 : 10987976 : nontrapping_dom_walker::after_dom_children (basic_block bb)
3415 : : {
3416 : : /* This BB isn't on the path to dominator root anymore. */
3417 : 10987976 : bb->aux = (void*)2;
3418 : 10987976 : }
3419 : :
3420 : : /* We see the expression EXP in basic block BB. If it's an interesting
3421 : : expression of:
3422 : : 1) MEM_REF
3423 : : 2) ARRAY_REF
3424 : : 3) COMPONENT_REF
3425 : : possibly insert the expression into the set NONTRAP or the hash table
3426 : : of seen expressions. STORE is true if this expression is on the LHS,
3427 : : otherwise it's on the RHS. */
3428 : : void
3429 : 25017944 : nontrapping_dom_walker::add_or_mark_expr (basic_block bb, tree exp, bool store)
3430 : : {
3431 : 25017944 : HOST_WIDE_INT size;
3432 : :
3433 : 25017944 : if ((TREE_CODE (exp) == MEM_REF || TREE_CODE (exp) == ARRAY_REF
3434 : 21417359 : || TREE_CODE (exp) == COMPONENT_REF)
3435 : 32253134 : && (size = int_size_in_bytes (TREE_TYPE (exp))) > 0)
3436 : : {
3437 : 10835770 : struct ref_to_bb map;
3438 : 10835770 : ref_to_bb **slot;
3439 : 10835770 : struct ref_to_bb *r2bb;
3440 : 10835770 : basic_block found_bb = 0;
3441 : :
3442 : 10835770 : if (!store)
3443 : : {
3444 : 5027608 : tree base = get_base_address (exp);
3445 : : /* Only record a LOAD of a local variable without address-taken, as
3446 : : the local stack is always writable. This allows cselim on a STORE
3447 : : with a dominating LOAD. */
3448 : 5027608 : if (!auto_var_p (base) || TREE_ADDRESSABLE (base))
3449 : 4023769 : return;
3450 : : }
3451 : :
3452 : : /* Try to find the last seen *_REF, which can trap. */
3453 : 6812001 : map.exp = exp;
3454 : 6812001 : map.size = size;
3455 : 6812001 : slot = m_seen_refs.find_slot (&map, INSERT);
3456 : 6812001 : r2bb = *slot;
3457 : 6812001 : if (r2bb && r2bb->phase >= nt_call_phase)
3458 : 309233 : found_bb = r2bb->bb;
3459 : :
3460 : : /* If we've found a trapping *_REF, _and_ it dominates EXP
3461 : : (it's in a basic block on the path from us to the dominator root)
3462 : : then we can't trap. */
3463 : 309233 : if (found_bb && (((size_t)found_bb->aux) & 1) == 1)
3464 : : {
3465 : 76396 : m_nontrapping->add (exp);
3466 : : }
3467 : : else
3468 : : {
3469 : : /* EXP might trap, so insert it into the hash table. */
3470 : 6735605 : if (r2bb)
3471 : : {
3472 : 965538 : r2bb->phase = nt_call_phase;
3473 : 965538 : r2bb->bb = bb;
3474 : : }
3475 : : else
3476 : : {
3477 : 5770067 : r2bb = XNEW (struct ref_to_bb);
3478 : 5770067 : r2bb->phase = nt_call_phase;
3479 : 5770067 : r2bb->bb = bb;
3480 : 5770067 : r2bb->exp = exp;
3481 : 5770067 : r2bb->size = size;
3482 : 5770067 : *slot = r2bb;
3483 : : }
3484 : : }
3485 : : }
3486 : : }
3487 : :
3488 : : /* This is the entry point of gathering non trapping memory accesses.
3489 : : It will do a dominator walk over the whole function, and it will
3490 : : make use of the bb->aux pointers. It returns a set of trees
3491 : : (the MEM_REFs itself) which can't trap. */
3492 : : static hash_set<tree> *
3493 : 1006279 : get_non_trapping (void)
3494 : : {
3495 : 1006279 : nt_call_phase = 0;
3496 : 1006279 : hash_set<tree> *nontrap = new hash_set<tree>;
3497 : :
3498 : 2012558 : nontrapping_dom_walker (CDI_DOMINATORS, nontrap)
3499 : 1006279 : .walk (cfun->cfg->x_entry_block_ptr);
3500 : :
3501 : 1006279 : clear_aux_for_blocks ();
3502 : 1006279 : return nontrap;
3503 : : }
3504 : :
3505 : : /* Do the main work of conditional store replacement. We already know
3506 : : that the recognized pattern looks like so:
3507 : :
3508 : : split:
3509 : : if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
3510 : : MIDDLE_BB:
3511 : : something
3512 : : fallthrough (edge E0)
3513 : : JOIN_BB:
3514 : : some more
3515 : :
3516 : : We check that MIDDLE_BB contains only one store, that that store
3517 : : doesn't trap (not via NOTRAP, but via checking if an access to the same
3518 : : memory location dominates us, or the store is to a local addressable
3519 : : object) and that the store has a "simple" RHS. */
3520 : :
3521 : : static bool
3522 : 390401 : cond_store_replacement (basic_block middle_bb, basic_block join_bb,
3523 : : edge e0, edge e1, hash_set<tree> *nontrap)
3524 : : {
3525 : 390401 : gimple *assign = last_and_only_stmt (middle_bb);
3526 : 390401 : tree lhs, rhs, name, name2;
3527 : 390401 : gphi *newphi;
3528 : 390401 : gassign *new_stmt;
3529 : 390401 : gimple_stmt_iterator gsi;
3530 : 390401 : location_t locus;
3531 : :
3532 : : /* Check if middle_bb contains of only one store. */
3533 : 390401 : if (!assign
3534 : 159385 : || !gimple_assign_single_p (assign)
3535 : 418448 : || gimple_has_volatile_ops (assign))
3536 : : return false;
3537 : :
3538 : : /* And no PHI nodes so all uses in the single stmt are also
3539 : : available where we insert to. */
3540 : 27890 : if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
3541 : : return false;
3542 : :
3543 : 27765 : locus = gimple_location (assign);
3544 : 27765 : lhs = gimple_assign_lhs (assign);
3545 : 27765 : rhs = gimple_assign_rhs1 (assign);
3546 : 27765 : if ((!REFERENCE_CLASS_P (lhs)
3547 : 27765 : && !DECL_P (lhs))
3548 : 27765 : || !is_gimple_reg_type (TREE_TYPE (lhs)))
3549 : : return false;
3550 : :
3551 : : /* Prove that we can move the store down. We could also check
3552 : : TREE_THIS_NOTRAP here, but in that case we also could move stores,
3553 : : whose value is not available readily, which we want to avoid. */
3554 : 15749 : if (!nontrap->contains (lhs))
3555 : : {
3556 : : /* If LHS is an access to a local variable without address-taken
3557 : : (or when we allow data races) and known not to trap, we could
3558 : : always safely move down the store. */
3559 : 10133 : if (ref_can_have_store_data_races (lhs)
3560 : 10133 : || tree_could_trap_p (lhs))
3561 : 9932 : return false;
3562 : : }
3563 : :
3564 : : /* Now we've checked the constraints, so do the transformation:
3565 : : 1) Remove the single store. */
3566 : 5817 : gsi = gsi_for_stmt (assign);
3567 : 5817 : unlink_stmt_vdef (assign);
3568 : 5817 : gsi_remove (&gsi, true);
3569 : 5817 : release_defs (assign);
3570 : :
3571 : : /* Make both store and load use alias-set zero as we have to
3572 : : deal with the case of the store being a conditional change
3573 : : of the dynamic type. */
3574 : 5817 : lhs = unshare_expr (lhs);
3575 : 5817 : tree *basep = &lhs;
3576 : 11706 : while (handled_component_p (*basep))
3577 : 5889 : basep = &TREE_OPERAND (*basep, 0);
3578 : 5817 : if (TREE_CODE (*basep) == MEM_REF
3579 : 5817 : || TREE_CODE (*basep) == TARGET_MEM_REF)
3580 : 617 : TREE_OPERAND (*basep, 1)
3581 : 1234 : = fold_convert (ptr_type_node, TREE_OPERAND (*basep, 1));
3582 : : else
3583 : 5200 : *basep = build2 (MEM_REF, TREE_TYPE (*basep),
3584 : : build_fold_addr_expr (*basep),
3585 : : build_zero_cst (ptr_type_node));
3586 : :
3587 : : /* 2) Insert a load from the memory of the store to the temporary
3588 : : on the edge which did not contain the store. */
3589 : 5817 : name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3590 : 5817 : new_stmt = gimple_build_assign (name, lhs);
3591 : 5817 : gimple_set_location (new_stmt, locus);
3592 : 5817 : lhs = unshare_expr (lhs);
3593 : 5817 : {
3594 : : /* Set the no-warning bit on the rhs of the load to avoid uninit
3595 : : warnings. */
3596 : 5817 : tree rhs1 = gimple_assign_rhs1 (new_stmt);
3597 : 5817 : suppress_warning (rhs1, OPT_Wuninitialized);
3598 : : }
3599 : 5817 : gsi_insert_on_edge (e1, new_stmt);
3600 : :
3601 : : /* 3) Create a PHI node at the join block, with one argument
3602 : : holding the old RHS, and the other holding the temporary
3603 : : where we stored the old memory contents. */
3604 : 5817 : name2 = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3605 : 5817 : newphi = create_phi_node (name2, join_bb);
3606 : 5817 : add_phi_arg (newphi, rhs, e0, locus);
3607 : 5817 : add_phi_arg (newphi, name, e1, locus);
3608 : :
3609 : 5817 : new_stmt = gimple_build_assign (lhs, gimple_phi_result (newphi));
3610 : :
3611 : : /* 4) Insert that PHI node. */
3612 : 5817 : gsi = gsi_after_labels (join_bb);
3613 : 5817 : if (gsi_end_p (gsi))
3614 : : {
3615 : 1972 : gsi = gsi_last_bb (join_bb);
3616 : 1972 : gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
3617 : : }
3618 : : else
3619 : 3845 : gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
3620 : :
3621 : 5817 : if (dump_file && (dump_flags & TDF_DETAILS))
3622 : : {
3623 : 7 : fprintf (dump_file, "\nConditional store replacement happened!");
3624 : 7 : fprintf (dump_file, "\nReplaced the store with a load.");
3625 : 7 : fprintf (dump_file, "\nInserted a new PHI statement in joint block:\n");
3626 : 7 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_VOPS|TDF_MEMSYMS);
3627 : : }
3628 : 5817 : statistics_counter_event (cfun, "conditional store replacement", 1);
3629 : :
3630 : 5817 : return true;
3631 : : }
3632 : :
3633 : : /* Do the main work of conditional store replacement. */
3634 : :
3635 : : static bool
3636 : 177891 : cond_if_else_store_replacement_1 (basic_block then_bb, basic_block else_bb,
3637 : : basic_block join_bb, gimple *then_assign,
3638 : : gimple *else_assign)
3639 : : {
3640 : 177891 : tree lhs_base, lhs, then_rhs, else_rhs, name;
3641 : 177891 : location_t then_locus, else_locus;
3642 : 177891 : gimple_stmt_iterator gsi;
3643 : 177891 : gphi *newphi;
3644 : 177891 : gassign *new_stmt;
3645 : :
3646 : 177891 : if (then_assign == NULL
3647 : 177891 : || !gimple_assign_single_p (then_assign)
3648 : 170160 : || gimple_clobber_p (then_assign)
3649 : 169633 : || gimple_has_volatile_ops (then_assign)
3650 : 169616 : || else_assign == NULL
3651 : 169616 : || !gimple_assign_single_p (else_assign)
3652 : 23306 : || gimple_clobber_p (else_assign)
3653 : 23306 : || gimple_has_volatile_ops (else_assign)
3654 : 23306 : || stmt_references_abnormal_ssa_name (then_assign)
3655 : 201194 : || stmt_references_abnormal_ssa_name (else_assign))
3656 : 154588 : return false;
3657 : :
3658 : 23303 : lhs = gimple_assign_lhs (then_assign);
3659 : 23303 : if (!is_gimple_reg_type (TREE_TYPE (lhs))
3660 : 23303 : || !operand_equal_p (lhs, gimple_assign_lhs (else_assign), 0))
3661 : 6219 : return false;
3662 : :
3663 : 17084 : lhs_base = get_base_address (lhs);
3664 : 17084 : if (lhs_base == NULL_TREE
3665 : 17084 : || (!DECL_P (lhs_base) && TREE_CODE (lhs_base) != MEM_REF))
3666 : : return false;
3667 : :
3668 : 17084 : then_rhs = gimple_assign_rhs1 (then_assign);
3669 : 17084 : else_rhs = gimple_assign_rhs1 (else_assign);
3670 : 17084 : then_locus = gimple_location (then_assign);
3671 : 17084 : else_locus = gimple_location (else_assign);
3672 : :
3673 : 17084 : if (dump_file && (dump_flags & TDF_DETAILS))
3674 : : {
3675 : 0 : fprintf(dump_file, "factoring out stores:\n\tthen:\n");
3676 : 0 : print_gimple_stmt (dump_file, then_assign, 0,
3677 : : TDF_VOPS|TDF_MEMSYMS);
3678 : 0 : fprintf(dump_file, "\telse:\n");
3679 : 0 : print_gimple_stmt (dump_file, else_assign, 0,
3680 : : TDF_VOPS|TDF_MEMSYMS);
3681 : 0 : fprintf (dump_file, "\n");
3682 : : }
3683 : :
3684 : : /* Now we've checked the constraints, so do the transformation:
3685 : : 1) Remove the stores. */
3686 : 17084 : gsi = gsi_for_stmt (then_assign);
3687 : 17084 : unlink_stmt_vdef (then_assign);
3688 : 17084 : gsi_remove (&gsi, true);
3689 : 17084 : release_defs (then_assign);
3690 : :
3691 : 17084 : gsi = gsi_for_stmt (else_assign);
3692 : 17084 : unlink_stmt_vdef (else_assign);
3693 : 17084 : gsi_remove (&gsi, true);
3694 : 17084 : release_defs (else_assign);
3695 : :
3696 : : /* 2) Create a PHI node at the join block, with one argument
3697 : : holding the old RHS, and the other holding the temporary
3698 : : where we stored the old memory contents. */
3699 : 17084 : name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
3700 : 17084 : newphi = create_phi_node (name, join_bb);
3701 : 17084 : add_phi_arg (newphi, then_rhs, EDGE_SUCC (then_bb, 0), then_locus);
3702 : 17084 : add_phi_arg (newphi, else_rhs, EDGE_SUCC (else_bb, 0), else_locus);
3703 : :
3704 : 17084 : new_stmt = gimple_build_assign (lhs, gimple_phi_result (newphi));
3705 : 17084 : if (dump_file && (dump_flags & TDF_DETAILS))
3706 : : {
3707 : 0 : fprintf(dump_file, "to use phi:\n");
3708 : 0 : print_gimple_stmt (dump_file, newphi, 0,
3709 : : TDF_VOPS|TDF_MEMSYMS);
3710 : 0 : fprintf(dump_file, "\n");
3711 : 0 : print_gimple_stmt (dump_file, new_stmt, 0,
3712 : : TDF_VOPS|TDF_MEMSYMS);
3713 : 0 : fprintf(dump_file, "\n\n");
3714 : : }
3715 : :
3716 : : /* 3) Insert that PHI node. */
3717 : 17084 : gsi = gsi_after_labels (join_bb);
3718 : 17084 : if (gsi_end_p (gsi))
3719 : : {
3720 : 140 : gsi = gsi_last_bb (join_bb);
3721 : 140 : gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
3722 : : }
3723 : : else
3724 : 16944 : gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
3725 : :
3726 : 17084 : statistics_counter_event (cfun, "if-then-else store replacement", 1);
3727 : :
3728 : 17084 : return true;
3729 : : }
3730 : :
3731 : : /* Return the single store in BB with VDEF or NULL if there are
3732 : : other stores in the BB or loads following the store. */
3733 : :
3734 : : static gimple *
3735 : 383018 : single_trailing_store_in_bb (basic_block bb, tree vdef)
3736 : : {
3737 : 383018 : if (SSA_NAME_IS_DEFAULT_DEF (vdef))
3738 : : return NULL;
3739 : 382069 : gimple *store = SSA_NAME_DEF_STMT (vdef);
3740 : 382069 : if (gimple_bb (store) != bb
3741 : 382069 : || gimple_code (store) == GIMPLE_PHI)
3742 : : return NULL;
3743 : :
3744 : : /* Verify there is no other store in this BB. */
3745 : 755092 : if (!SSA_NAME_IS_DEFAULT_DEF (gimple_vuse (store))
3746 : 370454 : && gimple_bb (SSA_NAME_DEF_STMT (gimple_vuse (store))) == bb
3747 : 409157 : && gimple_code (SSA_NAME_DEF_STMT (gimple_vuse (store))) != GIMPLE_PHI)
3748 : : return NULL;
3749 : :
3750 : : /* Verify there is no load or store after the store. */
3751 : 347240 : use_operand_p use_p;
3752 : 347240 : imm_use_iterator imm_iter;
3753 : 1041592 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_vdef (store))
3754 : 347365 : if (USE_STMT (use_p) != store
3755 : 347365 : && gimple_bb (USE_STMT (use_p)) == bb)
3756 : : return NULL;
3757 : :
3758 : : return store;
3759 : : }
3760 : :
3761 : : /* Conditional store replacement. We already know
3762 : : that the recognized pattern looks like so:
3763 : :
3764 : : split:
3765 : : if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
3766 : : THEN_BB:
3767 : : ...
3768 : : X = Y;
3769 : : ...
3770 : : goto JOIN_BB;
3771 : : ELSE_BB:
3772 : : ...
3773 : : X = Z;
3774 : : ...
3775 : : fallthrough (edge E0)
3776 : : JOIN_BB:
3777 : : some more
3778 : :
3779 : : We check that it is safe to sink the store to JOIN_BB by verifying that
3780 : : there are no read-after-write or write-after-write dependencies in
3781 : : THEN_BB and ELSE_BB. */
3782 : :
3783 : : static bool
3784 : 221052 : cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb,
3785 : : basic_block join_bb)
3786 : : {
3787 : 221052 : vec<data_reference_p> then_datarefs, else_datarefs;
3788 : 221052 : vec<ddr_p> then_ddrs, else_ddrs;
3789 : 221052 : gimple *then_store, *else_store;
3790 : 221052 : bool found, ok = false, res;
3791 : 221052 : tree then_lhs, else_lhs;
3792 : 221052 : basic_block blocks[3];
3793 : :
3794 : : /* Handle the case with single store in THEN_BB and ELSE_BB. That is
3795 : : cheap enough to always handle as it allows us to elide dependence
3796 : : checking. */
3797 : 221052 : gphi *vphi = NULL;
3798 : 264120 : for (gphi_iterator si = gsi_start_phis (join_bb); !gsi_end_p (si);
3799 : 43068 : gsi_next (&si))
3800 : 500272 : if (virtual_operand_p (gimple_phi_result (si.phi ())))
3801 : : {
3802 : 207068 : vphi = si.phi ();
3803 : 207068 : break;
3804 : : }
3805 : 221052 : if (!vphi)
3806 : 13984 : return false;
3807 : 207068 : tree then_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (then_bb));
3808 : 207068 : tree else_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (else_bb));
3809 : 207068 : gimple *then_assign = single_trailing_store_in_bb (then_bb, then_vdef);
3810 : 207068 : if (then_assign)
3811 : : {
3812 : 175950 : gimple *else_assign = single_trailing_store_in_bb (else_bb, else_vdef);
3813 : 175950 : if (else_assign)
3814 : 171037 : return cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
3815 : 171037 : then_assign, else_assign);
3816 : : }
3817 : :
3818 : : /* If either vectorization or if-conversion is disabled then do
3819 : : not sink any stores. */
3820 : 36031 : if (param_max_stores_to_sink == 0
3821 : 36030 : || (!flag_tree_loop_vectorize && !flag_tree_slp_vectorize)
3822 : 34113 : || !flag_tree_loop_if_convert)
3823 : : return false;
3824 : :
3825 : : /* Find data references. */
3826 : 34110 : then_datarefs.create (1);
3827 : 34110 : else_datarefs.create (1);
3828 : 34110 : if ((find_data_references_in_bb (NULL, then_bb, &then_datarefs)
3829 : 34110 : == chrec_dont_know)
3830 : 20241 : || !then_datarefs.length ()
3831 : 18142 : || (find_data_references_in_bb (NULL, else_bb, &else_datarefs)
3832 : 18142 : == chrec_dont_know)
3833 : 43929 : || !else_datarefs.length ())
3834 : : {
3835 : 24503 : free_data_refs (then_datarefs);
3836 : 24503 : free_data_refs (else_datarefs);
3837 : 24503 : return false;
3838 : : }
3839 : :
3840 : : /* Find pairs of stores with equal LHS. */
3841 : 9607 : auto_vec<std::pair<gimple *, gimple *>, 1> stores_pairs;
3842 : 67460 : for (auto then_dr : then_datarefs)
3843 : : {
3844 : 38639 : if (DR_IS_READ (then_dr))
3845 : 12328 : continue;
3846 : :
3847 : 26311 : then_store = DR_STMT (then_dr);
3848 : 26311 : then_lhs = gimple_get_lhs (then_store);
3849 : 26311 : if (then_lhs == NULL_TREE)
3850 : 0 : continue;
3851 : 26311 : found = false;
3852 : :
3853 : 169914 : for (auto else_dr : else_datarefs)
3854 : : {
3855 : 109311 : if (DR_IS_READ (else_dr))
3856 : 39054 : continue;
3857 : :
3858 : 70257 : else_store = DR_STMT (else_dr);
3859 : 70257 : else_lhs = gimple_get_lhs (else_store);
3860 : 70257 : if (else_lhs == NULL_TREE)
3861 : 0 : continue;
3862 : :
3863 : 70257 : if (operand_equal_p (then_lhs, else_lhs, 0))
3864 : : {
3865 : : found = true;
3866 : : break;
3867 : : }
3868 : : }
3869 : :
3870 : 26311 : if (!found)
3871 : 7981 : continue;
3872 : :
3873 : 18330 : stores_pairs.safe_push (std::make_pair (then_store, else_store));
3874 : : }
3875 : :
3876 : : /* No pairs of stores found. */
3877 : 9607 : if (!stores_pairs.length ()
3878 : 9607 : || stores_pairs.length () > (unsigned) param_max_stores_to_sink)
3879 : : {
3880 : 3224 : free_data_refs (then_datarefs);
3881 : 3224 : free_data_refs (else_datarefs);
3882 : 3224 : return false;
3883 : : }
3884 : :
3885 : : /* Compute and check data dependencies in both basic blocks. */
3886 : 6383 : then_ddrs.create (1);
3887 : 6383 : else_ddrs.create (1);
3888 : 6383 : if (!compute_all_dependences (then_datarefs, &then_ddrs,
3889 : : vNULL, false)
3890 : 6383 : || !compute_all_dependences (else_datarefs, &else_ddrs,
3891 : : vNULL, false))
3892 : : {
3893 : 0 : free_dependence_relations (then_ddrs);
3894 : 0 : free_dependence_relations (else_ddrs);
3895 : 0 : free_data_refs (then_datarefs);
3896 : 0 : free_data_refs (else_datarefs);
3897 : 0 : return false;
3898 : : }
3899 : 6383 : blocks[0] = then_bb;
3900 : 6383 : blocks[1] = else_bb;
3901 : 6383 : blocks[2] = join_bb;
3902 : 6383 : renumber_gimple_stmt_uids_in_blocks (blocks, 3);
3903 : :
3904 : : /* Check that there are no read-after-write or write-after-write dependencies
3905 : : in THEN_BB. */
3906 : 36484 : for (auto ddr : then_ddrs)
3907 : : {
3908 : 18283 : struct data_reference *dra = DDR_A (ddr);
3909 : 18283 : struct data_reference *drb = DDR_B (ddr);
3910 : :
3911 : 18283 : if (DDR_ARE_DEPENDENT (ddr) != chrec_known
3912 : 18283 : && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
3913 : 744 : && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
3914 : 1692 : || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
3915 : 652 : && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
3916 : 1040 : || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
3917 : : {
3918 : 948 : free_dependence_relations (then_ddrs);
3919 : 948 : free_dependence_relations (else_ddrs);
3920 : 948 : free_data_refs (then_datarefs);
3921 : 948 : free_data_refs (else_datarefs);
3922 : 948 : return false;
3923 : : }
3924 : : }
3925 : :
3926 : : /* Check that there are no read-after-write or write-after-write dependencies
3927 : : in ELSE_BB. */
3928 : 24464 : for (auto ddr : else_ddrs)
3929 : : {
3930 : 8803 : struct data_reference *dra = DDR_A (ddr);
3931 : 8803 : struct data_reference *drb = DDR_B (ddr);
3932 : :
3933 : 8803 : if (DDR_ARE_DEPENDENT (ddr) != chrec_known
3934 : 8803 : && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
3935 : 340 : && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
3936 : 984 : || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
3937 : 620 : && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
3938 : 364 : || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
3939 : : {
3940 : 644 : free_dependence_relations (then_ddrs);
3941 : 644 : free_dependence_relations (else_ddrs);
3942 : 644 : free_data_refs (then_datarefs);
3943 : 644 : free_data_refs (else_datarefs);
3944 : 644 : return false;
3945 : : }
3946 : : }
3947 : :
3948 : : /* Sink stores with same LHS. */
3949 : 21227 : for (auto &store_pair : stores_pairs)
3950 : : {
3951 : 6854 : then_store = store_pair.first;
3952 : 6854 : else_store = store_pair.second;
3953 : 6854 : res = cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
3954 : : then_store, else_store);
3955 : 6854 : ok = ok || res;
3956 : : }
3957 : :
3958 : 4791 : free_dependence_relations (then_ddrs);
3959 : 4791 : free_dependence_relations (else_ddrs);
3960 : 4791 : free_data_refs (then_datarefs);
3961 : 4791 : free_data_refs (else_datarefs);
3962 : :
3963 : 4791 : return ok;
3964 : 9607 : }
3965 : :
3966 : : /* Return TRUE if STMT has a VUSE whose corresponding VDEF is in BB. */
3967 : :
3968 : : static bool
3969 : 11726 : local_mem_dependence (gimple *stmt, basic_block bb)
3970 : : {
3971 : 23452 : tree vuse = gimple_vuse (stmt);
3972 : 11726 : gimple *def;
3973 : :
3974 : 11726 : if (!vuse)
3975 : : return false;
3976 : :
3977 : 11726 : def = SSA_NAME_DEF_STMT (vuse);
3978 : 11726 : return (def && gimple_bb (def) == bb);
3979 : : }
3980 : :
3981 : : /* Given a "diamond" control-flow pattern where BB0 tests a condition,
3982 : : BB1 and BB2 are "then" and "else" blocks dependent on this test,
3983 : : and BB3 rejoins control flow following BB1 and BB2, look for
3984 : : opportunities to hoist loads as follows. If BB3 contains a PHI of
3985 : : two loads, one each occurring in BB1 and BB2, and the loads are
3986 : : provably of adjacent fields in the same structure, then move both
3987 : : loads into BB0. Of course this can only be done if there are no
3988 : : dependencies preventing such motion.
3989 : :
3990 : : One of the hoisted loads will always be speculative, so the
3991 : : transformation is currently conservative:
3992 : :
3993 : : - The fields must be strictly adjacent.
3994 : : - The two fields must occupy a single memory block that is
3995 : : guaranteed to not cross a page boundary.
3996 : :
3997 : : The last is difficult to prove, as such memory blocks should be
3998 : : aligned on the minimum of the stack alignment boundary and the
3999 : : alignment guaranteed by heap allocation interfaces. Thus we rely
4000 : : on a parameter for the alignment value.
4001 : :
4002 : : Provided a good value is used for the last case, the first
4003 : : restriction could possibly be relaxed. */
4004 : :
4005 : : static void
4006 : 548742 : hoist_adjacent_loads (basic_block bb0, basic_block bb1,
4007 : : basic_block bb2, basic_block bb3)
4008 : : {
4009 : 548742 : unsigned HOST_WIDE_INT param_align = param_l1_cache_line_size;
4010 : 548742 : unsigned HOST_WIDE_INT param_align_bits = param_align * BITS_PER_UNIT;
4011 : 548742 : gphi_iterator gsi;
4012 : :
4013 : : /* Walk the phis in bb3 looking for an opportunity. We are looking
4014 : : for phis of two SSA names, one each of which is defined in bb1 and
4015 : : bb2. */
4016 : 1217198 : for (gsi = gsi_start_phis (bb3); !gsi_end_p (gsi); gsi_next (&gsi))
4017 : : {
4018 : 668456 : gphi *phi_stmt = gsi.phi ();
4019 : 668456 : gimple *def1, *def2;
4020 : 668456 : tree arg1, arg2, ref1, ref2, field1, field2;
4021 : 668456 : tree tree_offset1, tree_offset2, tree_size2, next;
4022 : 668456 : unsigned HOST_WIDE_INT offset1, offset2, size2, align1;
4023 : 668456 : gimple_stmt_iterator gsi2;
4024 : 668456 : basic_block bb_for_def1, bb_for_def2;
4025 : :
4026 : 668456 : if (gimple_phi_num_args (phi_stmt) != 2
4027 : 1336912 : || virtual_operand_p (gimple_phi_result (phi_stmt)))
4028 : 662593 : continue;
4029 : :
4030 : 155987 : arg1 = gimple_phi_arg_def (phi_stmt, 0);
4031 : 155987 : arg2 = gimple_phi_arg_def (phi_stmt, 1);
4032 : :
4033 : 184026 : if (TREE_CODE (arg1) != SSA_NAME
4034 : 140177 : || TREE_CODE (arg2) != SSA_NAME
4035 : 128409 : || SSA_NAME_IS_DEFAULT_DEF (arg1)
4036 : 284077 : || SSA_NAME_IS_DEFAULT_DEF (arg2))
4037 : 28039 : continue;
4038 : :
4039 : 127948 : def1 = SSA_NAME_DEF_STMT (arg1);
4040 : 127948 : def2 = SSA_NAME_DEF_STMT (arg2);
4041 : :
4042 : 127948 : if ((gimple_bb (def1) != bb1 || gimple_bb (def2) != bb2)
4043 : 136941 : && (gimple_bb (def2) != bb1 || gimple_bb (def1) != bb2))
4044 : 30072 : continue;
4045 : :
4046 : : /* Check the mode of the arguments to be sure a conditional move
4047 : : can be generated for it. */
4048 : 195752 : if (optab_handler (movcc_optab, TYPE_MODE (TREE_TYPE (arg1)))
4049 : : == CODE_FOR_nothing)
4050 : 4412 : continue;
4051 : :
4052 : : /* Both statements must be assignments whose RHS is a COMPONENT_REF. */
4053 : 93464 : if (!gimple_assign_single_p (def1)
4054 : 44640 : || !gimple_assign_single_p (def2)
4055 : 53526 : || gimple_has_volatile_ops (def1)
4056 : 146984 : || gimple_has_volatile_ops (def2))
4057 : 66704 : continue;
4058 : :
4059 : 26760 : ref1 = gimple_assign_rhs1 (def1);
4060 : 26760 : ref2 = gimple_assign_rhs1 (def2);
4061 : :
4062 : 26760 : if (TREE_CODE (ref1) != COMPONENT_REF
4063 : 19412 : || TREE_CODE (ref2) != COMPONENT_REF)
4064 : 7581 : continue;
4065 : :
4066 : : /* The zeroth operand of the two component references must be
4067 : : identical. It is not sufficient to compare get_base_address of
4068 : : the two references, because this could allow for different
4069 : : elements of the same array in the two trees. It is not safe to
4070 : : assume that the existence of one array element implies the
4071 : : existence of a different one. */
4072 : 19179 : if (!operand_equal_p (TREE_OPERAND (ref1, 0), TREE_OPERAND (ref2, 0), 0))
4073 : 8042 : continue;
4074 : :
4075 : 11137 : field1 = TREE_OPERAND (ref1, 1);
4076 : 11137 : field2 = TREE_OPERAND (ref2, 1);
4077 : :
4078 : : /* Check for field adjacency, and ensure field1 comes first. */
4079 : 11137 : for (next = DECL_CHAIN (field1);
4080 : 33929 : next && TREE_CODE (next) != FIELD_DECL;
4081 : 22792 : next = DECL_CHAIN (next))
4082 : : ;
4083 : :
4084 : 11137 : if (next != field2)
4085 : : {
4086 : 9487 : for (next = DECL_CHAIN (field2);
4087 : 11339 : next && TREE_CODE (next) != FIELD_DECL;
4088 : 1852 : next = DECL_CHAIN (next))
4089 : : ;
4090 : :
4091 : 9487 : if (next != field1)
4092 : 5274 : continue;
4093 : :
4094 : : std::swap (field1, field2);
4095 : : std::swap (def1, def2);
4096 : : }
4097 : :
4098 : 5863 : bb_for_def1 = gimple_bb (def1);
4099 : 5863 : bb_for_def2 = gimple_bb (def2);
4100 : :
4101 : : /* Check for proper alignment of the first field. */
4102 : 5863 : tree_offset1 = bit_position (field1);
4103 : 5863 : tree_offset2 = bit_position (field2);
4104 : 5863 : tree_size2 = DECL_SIZE (field2);
4105 : :
4106 : 5863 : if (!tree_fits_uhwi_p (tree_offset1)
4107 : 5863 : || !tree_fits_uhwi_p (tree_offset2)
4108 : 5863 : || !tree_fits_uhwi_p (tree_size2))
4109 : 0 : continue;
4110 : :
4111 : 5863 : offset1 = tree_to_uhwi (tree_offset1);
4112 : 5863 : offset2 = tree_to_uhwi (tree_offset2);
4113 : 5863 : size2 = tree_to_uhwi (tree_size2);
4114 : 5863 : align1 = DECL_ALIGN (field1) % param_align_bits;
4115 : :
4116 : 5863 : if (offset1 % BITS_PER_UNIT != 0)
4117 : 0 : continue;
4118 : :
4119 : : /* For profitability, the two field references should fit within
4120 : : a single cache line. */
4121 : 5863 : if (align1 + offset2 - offset1 + size2 > param_align_bits)
4122 : 0 : continue;
4123 : :
4124 : : /* The two expressions cannot be dependent upon vdefs defined
4125 : : in bb1/bb2. */
4126 : 5863 : if (local_mem_dependence (def1, bb_for_def1)
4127 : 5863 : || local_mem_dependence (def2, bb_for_def2))
4128 : 0 : continue;
4129 : :
4130 : : /* The conditions are satisfied; hoist the loads from bb1 and bb2 into
4131 : : bb0. We hoist the first one first so that a cache miss is handled
4132 : : efficiently regardless of hardware cache-fill policy. */
4133 : 5863 : gsi2 = gsi_for_stmt (def1);
4134 : 5863 : gsi_move_to_bb_end (&gsi2, bb0);
4135 : 5863 : gsi2 = gsi_for_stmt (def2);
4136 : 5863 : gsi_move_to_bb_end (&gsi2, bb0);
4137 : 5863 : statistics_counter_event (cfun, "hoisted loads", 1);
4138 : :
4139 : 5863 : if (dump_file && (dump_flags & TDF_DETAILS))
4140 : : {
4141 : 0 : fprintf (dump_file,
4142 : : "\nHoisting adjacent loads from %d and %d into %d: \n",
4143 : : bb_for_def1->index, bb_for_def2->index, bb0->index);
4144 : 0 : print_gimple_stmt (dump_file, def1, 0, TDF_VOPS|TDF_MEMSYMS);
4145 : 0 : print_gimple_stmt (dump_file, def2, 0, TDF_VOPS|TDF_MEMSYMS);
4146 : : }
4147 : : }
4148 : 548742 : }
4149 : :
4150 : : /* Determine whether we should attempt to hoist adjacent loads out of
4151 : : diamond patterns in pass_phiopt. Always hoist loads if
4152 : : -fhoist-adjacent-loads is specified and the target machine has
4153 : : both a conditional move instruction and a defined cache line size. */
4154 : :
4155 : : static bool
4156 : 3018743 : gate_hoist_loads (void)
4157 : : {
4158 : 3018743 : return (flag_hoist_adjacent_loads == 1
4159 : 3018743 : && param_l1_cache_line_size
4160 : 0 : && HAVE_conditional_move);
4161 : : }
4162 : :
4163 : : template <class func_type>
4164 : : static void
4165 : 6331681 : execute_over_cond_phis (func_type func)
4166 : : {
4167 : : unsigned n, i;
4168 : : basic_block *bb_order;
4169 : : basic_block bb;
4170 : : /* Search every basic block for COND_EXPR we may be able to optimize.
4171 : :
4172 : : We walk the blocks in order that guarantees that a block with
4173 : : a single predecessor is processed before the predecessor.
4174 : : This ensures that we collapse inner ifs before visiting the
4175 : : outer ones, and also that we do not try to visit a removed
4176 : : block. */
4177 : 6331681 : bb_order = single_pred_before_succ_order ();
4178 : 6331681 : n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
4179 : :
4180 : 56391723 : for (i = 0; i < n; i++)
4181 : : {
4182 : : basic_block bb1, bb2;
4183 : : edge e1, e2;
4184 : 50060042 : bool diamond_p = false;
4185 : :
4186 : 50060042 : bb = bb_order[i];
4187 : :
4188 : : /* Check to see if the last statement is a GIMPLE_COND. */
4189 : 50060042 : gcond *cond_stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
4190 : 30250500 : if (!cond_stmt)
4191 : 50060042 : continue;
4192 : :
4193 : 19809542 : e1 = EDGE_SUCC (bb, 0);
4194 : 19809542 : bb1 = e1->dest;
4195 : 19809542 : e2 = EDGE_SUCC (bb, 1);
4196 : 19809542 : bb2 = e2->dest;
4197 : :
4198 : : /* We cannot do the optimization on abnormal edges. */
4199 : 19809542 : if ((e1->flags & EDGE_ABNORMAL) != 0
4200 : 19809542 : || (e2->flags & EDGE_ABNORMAL) != 0)
4201 : 0 : continue;
4202 : :
4203 : : /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
4204 : 19809542 : if (EDGE_COUNT (bb1->succs) == 0
4205 : 18370349 : || EDGE_COUNT (bb2->succs) == 0)
4206 : 4519804 : continue;
4207 : :
4208 : : /* Find the bb which is the fall through to the other. */
4209 : 15289738 : if (EDGE_SUCC (bb1, 0)->dest == bb2)
4210 : : ;
4211 : 13008650 : else if (EDGE_SUCC (bb2, 0)->dest == bb1)
4212 : : {
4213 : : std::swap (bb1, bb2);
4214 : : std::swap (e1, e2);
4215 : : }
4216 : 9895016 : else if (EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest
4217 : 11306263 : && single_succ_p (bb2))
4218 : : {
4219 : 1411247 : diamond_p = true;
4220 : 1411247 : e2 = EDGE_SUCC (bb2, 0);
4221 : : /* Make sure bb2 is just a fall through. */
4222 : 1411247 : if ((e2->flags & EDGE_FALLTHRU) == 0)
4223 : 56577 : continue;
4224 : : }
4225 : : else
4226 : 9895016 : continue;
4227 : :
4228 : 5338145 : e1 = EDGE_SUCC (bb1, 0);
4229 : :
4230 : : /* Make sure that bb1 is just a fall through. */
4231 : 5338145 : if (!single_succ_p (bb1)
4232 : 5338145 : || (e1->flags & EDGE_FALLTHRU) == 0)
4233 : 1319311 : continue;
4234 : :
4235 : 4018834 : func (bb, bb1, bb2, e1, e2, diamond_p, cond_stmt);
4236 : : }
4237 : 6331681 : free (bb_order);
4238 : 6331681 : }
4239 : :
4240 : : /* This pass tries to replaces an if-then-else block with an
4241 : : assignment. We have different kinds of transformations.
4242 : : Some of these transformations are also performed by the ifcvt
4243 : : RTL optimizer.
4244 : :
4245 : : PHI-OPT using Match-and-simplify infrastructure
4246 : : -----------------------
4247 : :
4248 : : The PHI-OPT pass will try to use match-and-simplify infrastructure
4249 : : (gimple_simplify) to do transformations. This is implemented in
4250 : : match_simplify_replacement.
4251 : :
4252 : : The way it works is it replaces:
4253 : : bb0:
4254 : : if (cond) goto bb2; else goto bb1;
4255 : : bb1:
4256 : : bb2:
4257 : : x = PHI <a (bb1), b (bb0), ...>;
4258 : :
4259 : : with a statement if it gets simplified from `cond ? b : a`.
4260 : :
4261 : : bb0:
4262 : : x1 = cond ? b : a;
4263 : : bb2:
4264 : : x = PHI <a (bb1), x1 (bb0), ...>;
4265 : : Bb1 might be removed as it becomes unreachable when doing the replacement.
4266 : : Though bb1 does not have to be considered a forwarding basic block from bb0.
4267 : :
4268 : : Will try to see if `(!cond) ? a : b` gets simplified (iff !cond simplifies);
4269 : : this is done not to have an explosion of patterns in match.pd.
4270 : : Note bb1 does not need to be completely empty, it can contain
4271 : : one statement which is known not to trap.
4272 : :
4273 : : It also can handle the case where we have two forwarding bbs (diamond):
4274 : : bb0:
4275 : : if (cond) goto bb2; else goto bb1;
4276 : : bb1: goto bb3;
4277 : : bb2: goto bb3;
4278 : : bb3:
4279 : : x = PHI <a (bb1), b (bb2), ...>;
4280 : : And that is replaced with a statement if it is simplified
4281 : : from `cond ? b : a`.
4282 : : Again bb1 and bb2 does not have to be completely empty but
4283 : : each can contain one statement which is known not to trap.
4284 : : But in this case bb1/bb2 can only be forwarding basic blocks.
4285 : :
4286 : : This fully replaces the old "Conditional Replacement",
4287 : : "ABS Replacement" transformations as they are now
4288 : : implmeneted in match.pd.
4289 : : Some parts of the "MIN/MAX Replacement" are re-implemented in match.pd.
4290 : :
4291 : : Value Replacement
4292 : : -----------------
4293 : :
4294 : : This transformation, implemented in value_replacement, replaces
4295 : :
4296 : : bb0:
4297 : : if (a != b) goto bb2; else goto bb1;
4298 : : bb1:
4299 : : bb2:
4300 : : x = PHI <a (bb1), b (bb0), ...>;
4301 : :
4302 : : with
4303 : :
4304 : : bb0:
4305 : : bb2:
4306 : : x = PHI <b (bb0), ...>;
4307 : :
4308 : : This opportunity can sometimes occur as a result of other
4309 : : optimizations.
4310 : :
4311 : :
4312 : : Another case caught by value replacement looks like this:
4313 : :
4314 : : bb0:
4315 : : t1 = a == CONST;
4316 : : t2 = b > c;
4317 : : t3 = t1 & t2;
4318 : : if (t3 != 0) goto bb1; else goto bb2;
4319 : : bb1:
4320 : : bb2:
4321 : : x = PHI (CONST, a)
4322 : :
4323 : : Gets replaced with:
4324 : : bb0:
4325 : : bb2:
4326 : : t1 = a == CONST;
4327 : : t2 = b > c;
4328 : : t3 = t1 & t2;
4329 : : x = a;
4330 : :
4331 : : MIN/MAX Replacement
4332 : : -------------------
4333 : :
4334 : : This transformation, minmax_replacement replaces
4335 : :
4336 : : bb0:
4337 : : if (a <= b) goto bb2; else goto bb1;
4338 : : bb1:
4339 : : bb2:
4340 : : x = PHI <b (bb1), a (bb0), ...>;
4341 : :
4342 : : with
4343 : :
4344 : : bb0:
4345 : : x' = MIN_EXPR (a, b)
4346 : : bb2:
4347 : : x = PHI <x' (bb0), ...>;
4348 : :
4349 : : A similar transformation is done for MAX_EXPR.
4350 : :
4351 : :
4352 : : This pass also performs a fifth transformation of a slightly different
4353 : : flavor.
4354 : :
4355 : : Factor operations in COND_EXPR
4356 : : ------------------------------
4357 : :
4358 : : This transformation factors the unary operations out of COND_EXPR with
4359 : : factor_out_conditional_operation.
4360 : :
4361 : : For example:
4362 : : if (a <= CST) goto <bb 3>; else goto <bb 4>;
4363 : : <bb 3>:
4364 : : tmp = (int) a;
4365 : : <bb 4>:
4366 : : tmp = PHI <tmp, CST>
4367 : :
4368 : : Into:
4369 : : if (a <= CST) goto <bb 3>; else goto <bb 4>;
4370 : : <bb 3>:
4371 : : <bb 4>:
4372 : : a = PHI <a, CST>
4373 : : tmp = (int) a;
4374 : :
4375 : : Adjacent Load Hoisting
4376 : : ----------------------
4377 : :
4378 : : This transformation replaces
4379 : :
4380 : : bb0:
4381 : : if (...) goto bb2; else goto bb1;
4382 : : bb1:
4383 : : x1 = (<expr>).field1;
4384 : : goto bb3;
4385 : : bb2:
4386 : : x2 = (<expr>).field2;
4387 : : bb3:
4388 : : # x = PHI <x1, x2>;
4389 : :
4390 : : with
4391 : :
4392 : : bb0:
4393 : : x1 = (<expr>).field1;
4394 : : x2 = (<expr>).field2;
4395 : : if (...) goto bb2; else goto bb1;
4396 : : bb1:
4397 : : goto bb3;
4398 : : bb2:
4399 : : bb3:
4400 : : # x = PHI <x1, x2>;
4401 : :
4402 : : The purpose of this transformation is to enable generation of conditional
4403 : : move instructions such as Intel CMOVE or PowerPC ISEL. Because one of
4404 : : the loads is speculative, the transformation is restricted to very
4405 : : specific cases to avoid introducing a page fault. We are looking for
4406 : : the common idiom:
4407 : :
4408 : : if (...)
4409 : : x = y->left;
4410 : : else
4411 : : x = y->right;
4412 : :
4413 : : where left and right are typically adjacent pointers in a tree structure. */
4414 : :
4415 : : namespace {
4416 : :
4417 : : const pass_data pass_data_phiopt =
4418 : : {
4419 : : GIMPLE_PASS, /* type */
4420 : : "phiopt", /* name */
4421 : : OPTGROUP_NONE, /* optinfo_flags */
4422 : : TV_TREE_PHIOPT, /* tv_id */
4423 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
4424 : : 0, /* properties_provided */
4425 : : 0, /* properties_destroyed */
4426 : : 0, /* todo_flags_start */
4427 : : 0, /* todo_flags_finish */
4428 : : };
4429 : :
4430 : : class pass_phiopt : public gimple_opt_pass
4431 : : {
4432 : : public:
4433 : 1132628 : pass_phiopt (gcc::context *ctxt)
4434 : 2265256 : : gimple_opt_pass (pass_data_phiopt, ctxt), early_p (false)
4435 : : {}
4436 : :
4437 : : /* opt_pass methods: */
4438 : 849471 : opt_pass * clone () final override { return new pass_phiopt (m_ctxt); }
4439 : 1132628 : void set_pass_param (unsigned n, bool param) final override
4440 : : {
4441 : 1132628 : gcc_assert (n == 0);
4442 : 1132628 : early_p = param;
4443 : 1132628 : }
4444 : 5328748 : bool gate (function *) final override { return flag_ssa_phiopt; }
4445 : : unsigned int execute (function *) final override;
4446 : :
4447 : : private:
4448 : : bool early_p;
4449 : : }; // class pass_phiopt
4450 : :
4451 : : } // anon namespace
4452 : :
4453 : : gimple_opt_pass *
4454 : 283157 : make_pass_phiopt (gcc::context *ctxt)
4455 : : {
4456 : 283157 : return new pass_phiopt (ctxt);
4457 : : }
4458 : :
4459 : : unsigned int
4460 : 5325402 : pass_phiopt::execute (function *)
4461 : : {
4462 : 5325402 : bool do_hoist_loads = !early_p ? gate_hoist_loads () : false;
4463 : 5325402 : bool cfgchanged = false;
4464 : :
4465 : 5325402 : calculate_dominance_info (CDI_DOMINATORS);
4466 : 5325402 : mark_ssa_maybe_undefs ();
4467 : :
4468 : 8504775 : auto phiopt_exec = [&] (basic_block bb, basic_block bb1,
4469 : : basic_block bb2, edge e1, edge e2,
4470 : : bool diamond_p, gcond *cond_stmt)
4471 : : {
4472 : 3179373 : if (diamond_p)
4473 : : {
4474 : 1003204 : basic_block bb3 = e1->dest;
4475 : :
4476 : 1003204 : if (!single_pred_p (bb1)
4477 : 1942940 : || !single_pred_p (bb2))
4478 : 2389490 : return;
4479 : :
4480 : 882369 : if (do_hoist_loads
4481 : 698250 : && !FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt)))
4482 : 691058 : && EDGE_COUNT (bb->succs) == 2
4483 : 691058 : && EDGE_COUNT (bb3->preds) == 2
4484 : : /* If one edge or the other is dominant, a conditional move
4485 : : is likely to perform worse than the well-predicted branch. */
4486 : 552940 : && !predictable_edge_p (EDGE_SUCC (bb, 0))
4487 : 1431111 : && !predictable_edge_p (EDGE_SUCC (bb, 1)))
4488 : 548742 : hoist_adjacent_loads (bb, bb1, bb2, bb3);
4489 : : }
4490 : :
4491 : 882369 : gimple_stmt_iterator gsi;
4492 : :
4493 : : /* Check that we're looking for nested phis. */
4494 : 882369 : basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest : bb2;
4495 : 3058538 : gimple_seq phis = phi_nodes (merge);
4496 : :
4497 : 3058538 : if (gimple_seq_empty_p (phis))
4498 : : return;
4499 : :
4500 : : /* Factor out operations from the phi if possible. */
4501 : 3045033 : if (single_pred_p (bb1)
4502 : 5318587 : && EDGE_COUNT (merge->preds) == 2)
4503 : : {
4504 : 5078649 : for (gsi = gsi_start (phis); !gsi_end_p (gsi); )
4505 : : {
4506 : 2805095 : gphi *phi = as_a <gphi *> (gsi_stmt (gsi));
4507 : :
4508 : 2805095 : if (factor_out_conditional_operation (e1, e2, merge, phi,
4509 : : cond_stmt))
4510 : : {
4511 : : /* Start over if there was an operation that was factored out because the new phi might have another opportunity. */
4512 : 24867 : phis = phi_nodes (merge);
4513 : 5103516 : gsi = gsi_start (phis);
4514 : : }
4515 : : else
4516 : 2780228 : gsi_next (&gsi);
4517 : : }
4518 : : }
4519 : :
4520 : : /* Value replacement can work with more than one PHI
4521 : : so try that first. */
4522 : 3045033 : if (!early_p && !diamond_p)
4523 : 3877083 : for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
4524 : : {
4525 : 2273875 : gphi *phi = as_a <gphi *> (gsi_stmt (gsi));
4526 : 2273875 : tree arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
4527 : 2273875 : tree arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
4528 : 2273875 : if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1) == 2)
4529 : : {
4530 : 1653 : cfgchanged = true;
4531 : 1653 : return;
4532 : : }
4533 : : }
4534 : :
4535 : 3043380 : gphi *phi = single_non_singleton_phi_for_edges (phis, e1, e2);
4536 : 3043380 : if (!phi)
4537 : : return;
4538 : :
4539 : 789883 : tree arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
4540 : 789883 : tree arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
4541 : :
4542 : : /* Something is wrong if we cannot find the arguments in the PHI
4543 : : node. */
4544 : 789883 : gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
4545 : :
4546 : :
4547 : : /* Do the replacement of conditional if it can be done. */
4548 : 789883 : if (match_simplify_replacement (bb, bb1, bb2, e1, e2, phi,
4549 : 789883 : arg0, arg1, early_p, diamond_p))
4550 : 78882 : cfgchanged = true;
4551 : 711001 : else if (!early_p
4552 : 479054 : && !diamond_p
4553 : 449782 : && single_pred_p (bb1)
4554 : 1145397 : && cond_removal_in_builtin_zero_pattern (bb, bb1, e1, e2,
4555 : : phi, arg0, arg1))
4556 : 14 : cfgchanged = true;
4557 : 710987 : else if (minmax_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1,
4558 : : diamond_p))
4559 : 3866 : cfgchanged = true;
4560 : 1497004 : else if (single_pred_p (bb1)
4561 : 664767 : && !diamond_p
4562 : 1322748 : && spaceship_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
4563 : 1648 : cfgchanged = true;
4564 : 5325402 : };
4565 : :
4566 : 5325402 : execute_over_cond_phis (phiopt_exec);
4567 : :
4568 : 5325402 : if (cfgchanged)
4569 : 59268 : return TODO_cleanup_cfg;
4570 : : return 0;
4571 : : }
4572 : :
4573 : : /* This pass tries to transform conditional stores into unconditional
4574 : : ones, enabling further simplifications with the simpler then and else
4575 : : blocks. In particular it replaces this:
4576 : :
4577 : : bb0:
4578 : : if (cond) goto bb2; else goto bb1;
4579 : : bb1:
4580 : : *p = RHS;
4581 : : bb2:
4582 : :
4583 : : with
4584 : :
4585 : : bb0:
4586 : : if (cond) goto bb1; else goto bb2;
4587 : : bb1:
4588 : : condtmp' = *p;
4589 : : bb2:
4590 : : condtmp = PHI <RHS, condtmp'>
4591 : : *p = condtmp;
4592 : :
4593 : : This transformation can only be done under several constraints,
4594 : : documented below. It also replaces:
4595 : :
4596 : : bb0:
4597 : : if (cond) goto bb2; else goto bb1;
4598 : : bb1:
4599 : : *p = RHS1;
4600 : : goto bb3;
4601 : : bb2:
4602 : : *p = RHS2;
4603 : : bb3:
4604 : :
4605 : : with
4606 : :
4607 : : bb0:
4608 : : if (cond) goto bb3; else goto bb1;
4609 : : bb1:
4610 : : bb3:
4611 : : condtmp = PHI <RHS1, RHS2>
4612 : : *p = condtmp; */
4613 : :
4614 : : namespace {
4615 : :
4616 : : const pass_data pass_data_cselim =
4617 : : {
4618 : : GIMPLE_PASS, /* type */
4619 : : "cselim", /* name */
4620 : : OPTGROUP_NONE, /* optinfo_flags */
4621 : : TV_TREE_PHIOPT, /* tv_id */
4622 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
4623 : : 0, /* properties_provided */
4624 : : 0, /* properties_destroyed */
4625 : : 0, /* todo_flags_start */
4626 : : 0, /* todo_flags_finish */
4627 : : };
4628 : :
4629 : : class pass_cselim : public gimple_opt_pass
4630 : : {
4631 : : public:
4632 : 283157 : pass_cselim (gcc::context *ctxt)
4633 : 566314 : : gimple_opt_pass (pass_data_cselim, ctxt)
4634 : : {}
4635 : :
4636 : : /* opt_pass methods: */
4637 : 1006350 : bool gate (function *) final override { return flag_tree_cselim; }
4638 : : unsigned int execute (function *) final override;
4639 : :
4640 : : }; // class pass_cselim
4641 : :
4642 : : } // anon namespace
4643 : :
4644 : : gimple_opt_pass *
4645 : 283157 : make_pass_cselim (gcc::context *ctxt)
4646 : : {
4647 : 283157 : return new pass_cselim (ctxt);
4648 : : }
4649 : :
4650 : : unsigned int
4651 : 1006279 : pass_cselim::execute (function *)
4652 : : {
4653 : 1006279 : bool cfgchanged = false;
4654 : 1006279 : hash_set<tree> *nontrap = 0;
4655 : 1006279 : unsigned todo = 0;
4656 : :
4657 : : /* ??? We are not interested in loop related info, but the following
4658 : : will create it, ICEing as we didn't init loops with pre-headers.
4659 : : An interfacing issue of find_data_references_in_bb. */
4660 : 1006279 : loop_optimizer_init (LOOPS_NORMAL);
4661 : 1006279 : scev_initialize ();
4662 : :
4663 : 1006279 : calculate_dominance_info (CDI_DOMINATORS);
4664 : :
4665 : : /* Calculate the set of non-trapping memory accesses. */
4666 : 1006279 : nontrap = get_non_trapping ();
4667 : :
4668 : 1845740 : auto cselim_exec = [&] (basic_block bb, basic_block bb1,
4669 : : basic_block bb2, edge e1, edge e2,
4670 : : bool diamond_p, gcond *)
4671 : : {
4672 : 839461 : if (diamond_p)
4673 : : {
4674 : 285830 : basic_block bb3 = e1->dest;
4675 : :
4676 : : /* Only handle sinking of store from 2 bbs only,
4677 : : The middle bbs don't need to come from the
4678 : : if always since we are sinking rather than
4679 : : hoisting. */
4680 : 285830 : if (EDGE_COUNT (bb3->preds) != 2)
4681 : : return;
4682 : 221052 : if (cond_if_else_store_replacement (bb1, bb2, bb3))
4683 : 15176 : cfgchanged = true;
4684 : 221052 : return;
4685 : : }
4686 : :
4687 : : /* Also make sure that bb1 only have one predecessor and that it
4688 : : is bb. */
4689 : 553631 : if (!single_pred_p (bb1)
4690 : 1067608 : || single_pred (bb1) != bb)
4691 : : return;
4692 : :
4693 : : /* bb1 is the middle block, bb2 the join block, bb the split block,
4694 : : e1 the fallthrough edge from bb1 to bb2. We can't do the
4695 : : optimization if the join block has more than two predecessors. */
4696 : 513977 : if (EDGE_COUNT (bb2->preds) > 2)
4697 : : return;
4698 : 390401 : if (cond_store_replacement (bb1, bb2, e1, e2, nontrap))
4699 : 5817 : cfgchanged = true;
4700 : 1006279 : };
4701 : :
4702 : 1006279 : execute_over_cond_phis (cselim_exec);
4703 : :
4704 : 2012558 : delete nontrap;
4705 : : /* If the CFG has changed, we should cleanup the CFG. */
4706 : 1006279 : if (cfgchanged)
4707 : : {
4708 : : /* In cond-store replacement we have added some loads on edges
4709 : : and new VOPS (as we moved the store, and created a load). */
4710 : 11175 : gsi_commit_edge_inserts ();
4711 : 11175 : todo = TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
4712 : : }
4713 : 1006279 : scev_finalize ();
4714 : 1006279 : loop_optimizer_finalize ();
4715 : 1006279 : return todo;
4716 : : }
|
