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