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