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