Line data Source code
1 : /* Combining of if-expressions on trees.
2 : Copyright (C) 2007-2026 Free Software Foundation, Inc.
3 : Contributed by Richard Guenther <rguenther@suse.de>
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify
8 : it under the terms of the GNU General Public License as published by
9 : the Free Software Foundation; either version 3, or (at your option)
10 : any later version.
11 :
12 : GCC is distributed in the hope that it will be useful,
13 : but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : GNU General Public License for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #include "config.h"
22 : #include "system.h"
23 : #include "coretypes.h"
24 : #include "backend.h"
25 : #include "rtl.h"
26 : #include "tree.h"
27 : #include "gimple.h"
28 : #include "cfghooks.h"
29 : #include "tree-pass.h"
30 : #include "memmodel.h"
31 : #include "tm_p.h"
32 : #include "ssa.h"
33 : #include "tree-pretty-print.h"
34 : /* rtl is needed only because arm back-end requires it for
35 : BRANCH_COST. */
36 : #include "fold-const.h"
37 : #include "cfganal.h"
38 : #include "gimple-iterator.h"
39 : #include "gimple-fold.h"
40 : #include "gimplify-me.h"
41 : #include "tree-cfg.h"
42 : #include "tree-ssa.h"
43 : #include "attribs.h"
44 : #include "asan.h"
45 : #include "bitmap.h"
46 : #include "cfgloop.h"
47 :
48 : #ifndef LOGICAL_OP_NON_SHORT_CIRCUIT
49 : #define LOGICAL_OP_NON_SHORT_CIRCUIT \
50 : (BRANCH_COST (optimize_function_for_speed_p (cfun), \
51 : false) >= 2)
52 : #endif
53 :
54 : /* Return FALSE iff the COND_BB ends with a conditional whose result is not a
55 : known constant. */
56 :
57 : static bool
58 10058424 : known_succ_p (basic_block cond_bb)
59 : {
60 20611061 : gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (cond_bb));
61 :
62 9947900 : if (!cond)
63 : return true;
64 :
65 9947900 : return (CONSTANT_CLASS_P (gimple_cond_lhs (cond))
66 9947900 : && CONSTANT_CLASS_P (gimple_cond_rhs (cond)));
67 : }
68 :
69 : /* This pass combines COND_EXPRs to simplify control flow. It
70 : currently recognizes bit tests and comparisons in chains that
71 : represent logical and or logical or of two COND_EXPRs.
72 :
73 : It does so by walking basic blocks in a approximate reverse
74 : post-dominator order and trying to match CFG patterns that
75 : represent logical and or logical or of two COND_EXPRs.
76 : Transformations are done if the COND_EXPR conditions match
77 : either
78 :
79 : 1. two single bit tests X & (1 << Yn) (for logical and)
80 :
81 : 2. two bit tests X & Yn (for logical or)
82 :
83 : 3. two comparisons X OPn Y (for logical or)
84 :
85 : To simplify this pass, removing basic blocks and dead code
86 : is left to CFG cleanup and DCE. */
87 :
88 :
89 : /* Recognize a if-then-else CFG pattern starting to match with the COND_BB
90 : basic-block containing the COND_EXPR. If !SUCCS_ANY, the condition must not
91 : resolve to a constant for a match. Returns true if the pattern matched,
92 : false otherwise. In case of a !SUCCS_ANY match, the recognized then end
93 : else blocks are stored to *THEN_BB and *ELSE_BB. If *THEN_BB and/or
94 : *ELSE_BB are already set, they are required to match the then and else
95 : basic-blocks to make the pattern match. If SUCCS_ANY, *THEN_BB and *ELSE_BB
96 : will not be filled in, and they will be found to match even if reversed. */
97 :
98 : static bool
99 10018402 : recognize_if_then_else (basic_block cond_bb,
100 : basic_block *then_bb, basic_block *else_bb,
101 : bool succs_any = false)
102 : {
103 10018402 : edge t, e;
104 :
105 10018402 : if (EDGE_COUNT (cond_bb->succs) != 2
106 10018402 : || (!succs_any && known_succ_p (cond_bb)))
107 : return false;
108 :
109 : /* Find the then/else edges. */
110 9996660 : t = EDGE_SUCC (cond_bb, 0);
111 9996660 : e = EDGE_SUCC (cond_bb, 1);
112 :
113 9996660 : if (succs_any)
114 378256 : return ((t->dest == *then_bb && e->dest == *else_bb)
115 2280494 : || (t->dest == *else_bb && e->dest == *then_bb));
116 :
117 8381049 : if (!(t->flags & EDGE_TRUE_VALUE))
118 248056 : std::swap (t, e);
119 8381049 : if (!(t->flags & EDGE_TRUE_VALUE)
120 8381049 : || !(e->flags & EDGE_FALSE_VALUE))
121 : return false;
122 :
123 : /* Check if the edge destinations point to the required block. */
124 8381049 : if (*then_bb
125 4027874 : && t->dest != *then_bb)
126 : return false;
127 5423232 : if (*else_bb
128 1070057 : && e->dest != *else_bb)
129 : return false;
130 :
131 4676168 : if (!*then_bb)
132 4353175 : *then_bb = t->dest;
133 4676168 : if (!*else_bb)
134 4353175 : *else_bb = e->dest;
135 :
136 : return true;
137 : }
138 :
139 : /* Verify if the basic block BB does not have side-effects. Return
140 : true in this case, else false. */
141 :
142 : static bool
143 3424792 : bb_no_side_effects_p (basic_block bb)
144 : {
145 3424792 : gimple_stmt_iterator gsi;
146 :
147 18484424 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
148 : {
149 13467484 : gimple *stmt = gsi_stmt (gsi);
150 :
151 13467484 : if (is_gimple_debug (stmt))
152 7511119 : continue;
153 :
154 5956365 : gassign *ass;
155 5956365 : enum tree_code rhs_code;
156 5956365 : if (gimple_has_side_effects (stmt)
157 5383784 : || gimple_could_trap_p (stmt)
158 4647784 : || gimple_vdef (stmt)
159 : /* We need to rewrite stmts with undefined overflow to use
160 : unsigned arithmetic but cannot do so for signed division. */
161 6888613 : || ((ass = dyn_cast <gassign *> (stmt))
162 2473870 : && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (ass)))
163 3731264 : && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (ass)))
164 477146 : && ((rhs_code = gimple_assign_rhs_code (ass)), true)
165 477146 : && (rhs_code == TRUNC_DIV_EXPR
166 : || rhs_code == CEIL_DIV_EXPR
167 : || rhs_code == FLOOR_DIV_EXPR
168 477146 : || rhs_code == ROUND_DIV_EXPR)
169 : /* We cannot use expr_not_equal_to since we'd have to restrict
170 : flow-sensitive info to whats known at the outer if. */
171 908 : && (TREE_CODE (gimple_assign_rhs2 (ass)) != INTEGER_CST
172 908 : || !integer_minus_onep (gimple_assign_rhs2 (ass))))
173 : /* const calls don't match any of the above, yet they could
174 : still have some side-effects - they could contain
175 : gimple_could_trap_p statements, like floating point
176 : exceptions or integer division by zero. See PR70586.
177 : FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
178 : should handle this. */
179 12236740 : || is_gimple_call (stmt))
180 1832644 : return false;
181 :
182 4127009 : ssa_op_iter it;
183 4127009 : tree use;
184 8332049 : FOR_EACH_SSA_TREE_OPERAND (use, stmt, it, SSA_OP_USE)
185 4208328 : if (ssa_name_maybe_undef_p (use))
186 : return false;
187 : }
188 :
189 : return true;
190 : }
191 :
192 : /* Return true if BB is an empty forwarder block to TO_BB. */
193 :
194 : static bool
195 1844691 : forwarder_block_to (basic_block bb, basic_block to_bb)
196 : {
197 1844691 : return empty_block_p (bb)
198 59038 : && single_succ_p (bb)
199 1903729 : && single_succ (bb) == to_bb;
200 : }
201 :
202 : /* Verify if all PHI node arguments in DEST for edges from BB1 or
203 : BB2 to DEST are the same. This makes the CFG merge point
204 : free from side-effects. Return true in this case, else false. */
205 :
206 : static bool
207 735058 : same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
208 : {
209 735058 : edge e1 = find_edge (bb1, dest);
210 735058 : edge e2 = find_edge (bb2, dest);
211 735058 : gphi_iterator gsi;
212 735058 : gphi *phi;
213 :
214 1094315 : for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
215 : {
216 467696 : phi = gsi.phi ();
217 467696 : if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
218 467696 : PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
219 : return false;
220 : }
221 :
222 : return true;
223 : }
224 :
225 : /* Return the best representative SSA name for CANDIDATE which is used
226 : in a bit test. */
227 :
228 : static tree
229 9176 : get_name_for_bit_test (tree candidate)
230 : {
231 : /* Skip single-use names in favor of using the name from a
232 : non-widening conversion definition. */
233 9176 : if (TREE_CODE (candidate) == SSA_NAME
234 9176 : && has_single_use (candidate))
235 : {
236 4163 : gimple *def_stmt = SSA_NAME_DEF_STMT (candidate);
237 4163 : if (is_gimple_assign (def_stmt)
238 4163 : && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
239 : {
240 179 : if (TYPE_PRECISION (TREE_TYPE (candidate))
241 179 : <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
242 : return gimple_assign_rhs1 (def_stmt);
243 : }
244 : }
245 :
246 : return candidate;
247 : }
248 :
249 : /* Recognize a single bit test pattern in GIMPLE_COND and its defining
250 : statements. Store the name being tested in *NAME and the bit
251 : in *BIT. The GIMPLE_COND computes *NAME & (1 << *BIT).
252 : Returns true if the pattern matched, false otherwise. */
253 :
254 : static bool
255 244815 : recognize_single_bit_test (gcond *cond, tree *name, tree *bit, bool inv)
256 : {
257 244815 : gimple *stmt;
258 :
259 : /* Get at the definition of the result of the bit test. */
260 244815 : if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
261 45299 : || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
262 290109 : || !integer_zerop (gimple_cond_rhs (cond)))
263 218556 : return false;
264 26259 : stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
265 26259 : if (!is_gimple_assign (stmt))
266 : return false;
267 :
268 : /* Look at which bit is tested. One form to recognize is
269 : D.1985_5 = state_3(D) >> control1_4(D);
270 : D.1986_6 = (int) D.1985_5;
271 : D.1987_7 = op0 & 1;
272 : if (D.1987_7 != 0) */
273 21766 : if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
274 7106 : && integer_onep (gimple_assign_rhs2 (stmt))
275 22166 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
276 : {
277 400 : tree orig_name = gimple_assign_rhs1 (stmt);
278 :
279 : /* Look through copies and conversions to eventually
280 : find the stmt that computes the shift. */
281 400 : stmt = SSA_NAME_DEF_STMT (orig_name);
282 :
283 401 : while (is_gimple_assign (stmt)
284 401 : && ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
285 1 : && (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt)))
286 1 : <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt))))
287 1 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
288 324 : || gimple_assign_ssa_name_copy_p (stmt)))
289 1 : stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
290 :
291 : /* If we found such, decompose it. */
292 400 : if (is_gimple_assign (stmt)
293 400 : && gimple_assign_rhs_code (stmt) == RSHIFT_EXPR)
294 : {
295 : /* op0 & (1 << op1) */
296 79 : *bit = gimple_assign_rhs2 (stmt);
297 79 : *name = gimple_assign_rhs1 (stmt);
298 : }
299 : else
300 : {
301 : /* t & 1 */
302 321 : *bit = integer_zero_node;
303 321 : *name = get_name_for_bit_test (orig_name);
304 : }
305 :
306 400 : return true;
307 : }
308 :
309 : /* Another form is
310 : D.1987_7 = op0 & (1 << CST)
311 : if (D.1987_7 != 0) */
312 21366 : if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
313 6706 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
314 28072 : && integer_pow2p (gimple_assign_rhs2 (stmt)))
315 : {
316 4141 : *name = gimple_assign_rhs1 (stmt);
317 4141 : *bit = build_int_cst (integer_type_node,
318 4141 : tree_log2 (gimple_assign_rhs2 (stmt)));
319 4141 : return true;
320 : }
321 :
322 : /* Another form is
323 : D.1986_6 = 1 << control1_4(D)
324 : D.1987_7 = op0 & D.1986_6
325 : if (D.1987_7 != 0) */
326 17225 : if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
327 2565 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
328 19790 : && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
329 : {
330 2088 : gimple *tmp;
331 :
332 : /* Both arguments of the BIT_AND_EXPR can be the single-bit
333 : specifying expression. */
334 2088 : tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
335 2088 : if (is_gimple_assign (tmp)
336 1967 : && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
337 2098 : && integer_onep (gimple_assign_rhs1 (tmp)))
338 : {
339 10 : *name = gimple_assign_rhs2 (stmt);
340 10 : *bit = gimple_assign_rhs2 (tmp);
341 10 : return true;
342 : }
343 :
344 2078 : tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
345 2078 : if (is_gimple_assign (tmp)
346 2009 : && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
347 2108 : && integer_onep (gimple_assign_rhs1 (tmp)))
348 : {
349 30 : *name = gimple_assign_rhs1 (stmt);
350 30 : *bit = gimple_assign_rhs2 (tmp);
351 30 : return true;
352 : }
353 : }
354 :
355 : return false;
356 : }
357 :
358 : /* Recognize a bit test pattern in a GIMPLE_COND and its defining
359 : statements. Store the name being tested in *NAME and the bits
360 : in *BITS. The COND_EXPR computes *NAME & *BITS.
361 : Returns true if the pattern matched, false otherwise. */
362 :
363 : static bool
364 246912 : recognize_bits_test (gcond *cond, tree *name, tree *bits, bool inv)
365 : {
366 246912 : gimple *stmt;
367 :
368 : /* Get at the definition of the result of the bit test. */
369 246912 : if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
370 142329 : || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
371 389241 : || !integer_zerop (gimple_cond_rhs (cond)))
372 217147 : return false;
373 29765 : stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
374 29765 : if (!is_gimple_assign (stmt)
375 29765 : || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
376 : return false;
377 :
378 8855 : *name = get_name_for_bit_test (gimple_assign_rhs1 (stmt));
379 8855 : *bits = gimple_assign_rhs2 (stmt);
380 :
381 8855 : return true;
382 : }
383 :
384 :
385 : /* Update profile after code in either outer_cond_bb or inner_cond_bb was
386 : adjusted so that it has no condition. */
387 :
388 : static void
389 89763 : update_profile_after_ifcombine (basic_block inner_cond_bb,
390 : basic_block outer_cond_bb)
391 : {
392 : /* In the following we assume that inner_cond_bb has single predecessor. */
393 89763 : gcc_assert (single_pred_p (inner_cond_bb));
394 :
395 89763 : basic_block outer_to_inner_bb = inner_cond_bb;
396 89763 : profile_probability prob = profile_probability::always ();
397 89925 : for (;;)
398 : {
399 89925 : basic_block parent = single_pred (outer_to_inner_bb);
400 89925 : prob *= find_edge (parent, outer_to_inner_bb)->probability;
401 89925 : if (parent == outer_cond_bb)
402 : break;
403 : outer_to_inner_bb = parent;
404 : }
405 :
406 89763 : edge outer_to_inner = find_edge (outer_cond_bb, outer_to_inner_bb);
407 89763 : edge outer2 = (EDGE_SUCC (outer_cond_bb, 0) == outer_to_inner
408 35761 : ? EDGE_SUCC (outer_cond_bb, 1)
409 125524 : : EDGE_SUCC (outer_cond_bb, 0));
410 89763 : edge inner_taken = EDGE_SUCC (inner_cond_bb, 0);
411 89763 : edge inner_not_taken = EDGE_SUCC (inner_cond_bb, 1);
412 :
413 89763 : if (inner_taken->dest != outer2->dest)
414 30130 : std::swap (inner_taken, inner_not_taken);
415 89763 : gcc_assert (inner_taken->dest == outer2->dest);
416 :
417 89763 : if (outer_to_inner_bb == inner_cond_bb
418 89763 : && known_succ_p (outer_cond_bb))
419 : {
420 : /* Path outer_cond_bb->(outer2) needs to be merged into path
421 : outer_cond_bb->(outer_to_inner)->inner_cond_bb->(inner_taken)
422 : and probability of inner_not_taken updated. */
423 :
424 89531 : inner_cond_bb->count = outer_cond_bb->count;
425 :
426 : /* Handle special case where inner_taken probability is always. In this
427 : case we know that the overall outcome will be always as well, but
428 : combining probabilities will be conservative because it does not know
429 : that outer2->probability is inverse of
430 : outer_to_inner->probability. */
431 89531 : if (inner_taken->probability == profile_probability::always ())
432 : ;
433 : else
434 87912 : inner_taken->probability = outer2->probability
435 87912 : + outer_to_inner->probability * inner_taken->probability;
436 89531 : inner_not_taken->probability = profile_probability::always ()
437 89531 : - inner_taken->probability;
438 :
439 89531 : outer_to_inner->probability = profile_probability::always ();
440 89531 : outer2->probability = profile_probability::never ();
441 : }
442 232 : else if (known_succ_p (inner_cond_bb))
443 : {
444 : /* Path inner_cond_bb->(inner_taken) needs to be merged into path
445 : outer_cond_bb->(outer2). We've accumulated the probabilities from
446 : outer_cond_bb->(outer)->...->inner_cond_bb in prob, so we have to
447 : adjust that by inner_taken, and make inner unconditional. */
448 :
449 111 : prob *= inner_taken->probability;
450 111 : outer2->probability += prob;
451 111 : outer_to_inner->probability = profile_probability::always ()
452 111 : - outer2->probability;
453 :
454 111 : inner_taken->probability = profile_probability::never ();
455 111 : inner_not_taken->probability = profile_probability::always ();
456 : }
457 : else
458 : {
459 : /* We've moved part of the inner cond to outer, but we don't know the
460 : probabilities for each part, so estimate the effects by moving half of
461 : the odds of inner_taken to outer. */
462 :
463 121 : inner_taken->probability *= profile_probability::even ();
464 121 : inner_not_taken->probability = profile_probability::always ()
465 121 : - inner_taken->probability;
466 :
467 121 : prob *= inner_taken->probability;
468 121 : outer2->probability += prob;
469 121 : outer_to_inner->probability = profile_probability::always ()
470 121 : - outer2->probability;
471 : }
472 89763 : }
473 :
474 : /* Set NAME's bit in USED if OUTER dominates it. */
475 :
476 : static void
477 1121 : ifcombine_mark_ssa_name (bitmap used, tree name, basic_block outer)
478 : {
479 1121 : if (!name || TREE_CODE (name) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (name))
480 : return;
481 :
482 471 : gimple *def = SSA_NAME_DEF_STMT (name);
483 471 : basic_block bb = gimple_bb (def);
484 471 : if (!dominated_by_p (CDI_DOMINATORS, bb, outer))
485 : return;
486 :
487 421 : bitmap_set_bit (used, SSA_NAME_VERSION (name));
488 : }
489 :
490 : /* Data structure passed to ifcombine_mark_ssa_name. */
491 : struct ifcombine_mark_ssa_name_t
492 : {
493 : /* SSA_NAMEs that have been referenced. */
494 : bitmap used;
495 : /* Dominating block of DEFs that might need moving. */
496 : basic_block outer;
497 : };
498 :
499 : /* Mark in DATA->used any SSA_NAMEs used in *t. */
500 :
501 : static tree
502 1097 : ifcombine_mark_ssa_name_walk (tree *t, int *, void *data_)
503 : {
504 1097 : ifcombine_mark_ssa_name_t *data = (ifcombine_mark_ssa_name_t *)data_;
505 :
506 1097 : ifcombine_mark_ssa_name (data->used, *t, data->outer);
507 :
508 1097 : return NULL;
509 : }
510 :
511 : /* Rewrite a stmt, that presumably used to be guarded by conditions that could
512 : avoid undefined overflow, into one that has well-defined overflow, so that
513 : it won't invoke undefined behavior once the guarding conditions change. */
514 :
515 : static inline void
516 347502 : ifcombine_rewrite_to_defined_overflow (gimple_stmt_iterator gsi)
517 : {
518 347502 : if (!gimple_needing_rewrite_undefined (gsi_stmt (gsi)))
519 : return;
520 34 : rewrite_to_defined_unconditional (&gsi);
521 : }
522 :
523 :
524 : /* Replace the conditions in INNER_COND and OUTER_COND with COND and COND2.
525 : COND and COND2 are computed for insertion at INNER_COND, with OUTER_COND
526 : replaced with a constant, but if there are intervening blocks, it's best to
527 : adjust COND for insertion at OUTER_COND, placing COND2 at INNER_COND. */
528 :
529 : static bool
530 89764 : ifcombine_replace_cond (gcond *inner_cond, bool inner_inv,
531 : gcond *outer_cond, bool outer_inv,
532 : tree cond, bool must_canon, tree cond2)
533 : {
534 89764 : bool split_single_cond = false;
535 : /* Split cond into cond2 if they're contiguous. ??? We might be able to
536 : handle ORIF as well, inverting both conditions, but it's not clear that
537 : this would be enough, and it never comes up. */
538 89764 : if (!cond2
539 89758 : && TREE_CODE (cond) == TRUTH_ANDIF_EXPR
540 89900 : && single_pred (gimple_bb (inner_cond)) == gimple_bb (outer_cond))
541 : {
542 115 : cond2 = TREE_OPERAND (cond, 1);
543 115 : cond = TREE_OPERAND (cond, 0);
544 115 : split_single_cond = true;
545 : }
546 :
547 89764 : bool outer_p = cond2 || (single_pred (gimple_bb (inner_cond))
548 89643 : != gimple_bb (outer_cond));
549 : bool result_inv = outer_p ? outer_inv : inner_inv;
550 89764 : bool strictening_outer_cond = !split_single_cond && outer_p;
551 :
552 89764 : if (result_inv)
553 60156 : cond = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
554 :
555 89764 : if (tree tcanon = canonicalize_cond_expr_cond (cond))
556 4598 : cond = tcanon;
557 85166 : else if (must_canon)
558 : return false;
559 :
560 89764 : if (outer_p)
561 : {
562 233 : {
563 233 : auto_bitmap used;
564 233 : basic_block outer_bb = gimple_bb (outer_cond);
565 :
566 233 : bitmap_tree_view (used);
567 :
568 : /* Mark SSA DEFs that are referenced by cond and may thus need to be
569 : moved to outer. */
570 233 : {
571 233 : ifcombine_mark_ssa_name_t data = { used, outer_bb };
572 233 : walk_tree (&cond, ifcombine_mark_ssa_name_walk, &data, NULL);
573 : }
574 :
575 233 : if (!bitmap_empty_p (used))
576 : {
577 213 : const int max_stmts = 6;
578 213 : auto_vec<gimple *, max_stmts> stmts;
579 :
580 : /* Iterate up from inner_cond, moving DEFs identified as used by
581 : cond, and marking USEs in the DEFs for moving as well. */
582 567 : for (basic_block bb = gimple_bb (inner_cond);
583 567 : bb != outer_bb; bb = single_pred (bb))
584 : {
585 355 : for (gimple_stmt_iterator gsitr = gsi_last_bb (bb);
586 4091 : !gsi_end_p (gsitr); gsi_prev (&gsitr))
587 : {
588 1868 : gimple *stmt = gsi_stmt (gsitr);
589 1868 : bool move = false;
590 1868 : tree t;
591 1868 : ssa_op_iter it;
592 :
593 2867 : FOR_EACH_SSA_TREE_OPERAND (t, stmt, it, SSA_OP_DEF)
594 1141 : if (bitmap_bit_p (used, SSA_NAME_VERSION (t)))
595 : {
596 : move = true;
597 : break;
598 : }
599 :
600 1868 : if (!move)
601 1726 : continue;
602 :
603 142 : if (stmts.length () < max_stmts)
604 142 : stmts.quick_push (stmt);
605 : else
606 0 : return false;
607 :
608 : /* Mark uses in STMT before moving it. */
609 162 : FOR_EACH_SSA_TREE_OPERAND (t, stmt, it, SSA_OP_USE)
610 20 : ifcombine_mark_ssa_name (used, t, outer_bb);
611 : }
612 :
613 : /* Surprisingly, there may be PHI nodes in single-predecessor
614 : bocks, as in pr50682.C. Fortunately, since they can't
615 : involve back edges, there won't be references to parallel
616 : nodes that we'd have to pay special attention to to keep
617 : them parallel. We can't move the PHI nodes, but we can turn
618 : them into assignments. */
619 355 : for (gphi_iterator gsi = gsi_start_phis (bb);
620 359 : !gsi_end_p (gsi);)
621 : {
622 5 : gphi *phi = gsi.phi ();
623 :
624 5 : gcc_assert (gimple_phi_num_args (phi) == 1);
625 5 : tree def = gimple_phi_result (phi);
626 :
627 5 : if (!bitmap_bit_p (used, SSA_NAME_VERSION (def)))
628 : {
629 0 : gsi_next (&gsi);
630 0 : continue;
631 : }
632 :
633 5 : if (stmts.length () < max_stmts)
634 4 : stmts.quick_push (phi);
635 : else
636 1 : return false;
637 :
638 : /* Mark uses in STMT before moving it. */
639 4 : use_operand_p use_p;
640 4 : ssa_op_iter it;
641 8 : FOR_EACH_PHI_ARG (use_p, phi, it, SSA_OP_USE)
642 4 : ifcombine_mark_ssa_name (used, USE_FROM_PTR (use_p),
643 : outer_bb);
644 : }
645 : }
646 :
647 : /* ??? Test whether it makes sense to move STMTS. */
648 :
649 : /* Move the STMTS that need moving. From this point on, we're
650 : committing to the attempted ifcombine. */
651 212 : gimple_stmt_iterator gsins = gsi_for_stmt (outer_cond);
652 212 : unsigned i;
653 212 : gimple *stmt;
654 352 : FOR_EACH_VEC_ELT (stmts, i, stmt)
655 : {
656 140 : if (gphi *phi = dyn_cast <gphi *> (stmt))
657 : {
658 0 : tree def = gimple_phi_result (phi);
659 0 : tree use = gimple_phi_arg_def (phi, 0);
660 0 : location_t loc = gimple_phi_arg_location (phi, 0);
661 :
662 0 : gphi_iterator gsi = gsi_for_phi (phi);
663 0 : remove_phi_node (&gsi, false);
664 :
665 0 : gassign *a = gimple_build_assign (def, use);
666 0 : gimple_set_location (a, loc);
667 0 : gsi_insert_before (&gsins, a, GSI_NEW_STMT);
668 : }
669 : else
670 : {
671 140 : gimple_stmt_iterator gsitr = gsi_for_stmt (stmt);
672 140 : gsi_move_before (&gsitr, &gsins, GSI_NEW_STMT);
673 : }
674 : }
675 :
676 352 : for (; gsi_stmt (gsins) != outer_cond; gsi_next (&gsins))
677 : {
678 : /* Clear range info from all defs we've moved from under
679 : conditions. */
680 140 : tree t;
681 140 : ssa_op_iter it;
682 280 : FOR_EACH_SSA_TREE_OPERAND (t, gsi_stmt (gsins), it, SSA_OP_DEF)
683 140 : reset_flow_sensitive_info (t);
684 : /* Avoid introducing undefined overflows while at that. */
685 140 : ifcombine_rewrite_to_defined_overflow (gsins);
686 : }
687 213 : }
688 1 : }
689 :
690 232 : if (!is_gimple_condexpr_for_cond (cond))
691 : {
692 103 : gimple_stmt_iterator gsi = gsi_for_stmt (outer_cond);
693 103 : cond = force_gimple_operand_gsi_1 (&gsi, cond,
694 : is_gimple_condexpr_for_cond,
695 : NULL, true, GSI_SAME_STMT);
696 : }
697 :
698 : /* Leave CFG optimization to cfg_cleanup. */
699 232 : gimple_cond_set_condition_from_tree (outer_cond, cond);
700 232 : update_stmt (outer_cond);
701 :
702 232 : if (cond2)
703 : {
704 121 : if (inner_inv)
705 115 : cond2 = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond2), cond2);
706 :
707 121 : if (tree tcanon = canonicalize_cond_expr_cond (cond2))
708 49 : cond2 = tcanon;
709 121 : if (!is_gimple_condexpr_for_cond (cond2))
710 : {
711 72 : gimple_stmt_iterator gsi = gsi_for_stmt (inner_cond);
712 72 : cond2 = force_gimple_operand_gsi_1 (&gsi, cond2,
713 : is_gimple_condexpr_for_cond,
714 : NULL, true, GSI_SAME_STMT);
715 : }
716 121 : gimple_cond_set_condition_from_tree (inner_cond, cond2);
717 : }
718 : else
719 111 : gimple_cond_set_condition_from_tree (inner_cond,
720 : inner_inv
721 : ? boolean_false_node
722 : : boolean_true_node);
723 232 : update_stmt (inner_cond);
724 : }
725 : else
726 : {
727 89531 : if (!is_gimple_condexpr_for_cond (cond))
728 : {
729 85063 : gimple_stmt_iterator gsi = gsi_for_stmt (inner_cond);
730 85063 : cond = force_gimple_operand_gsi_1 (&gsi, cond,
731 : is_gimple_condexpr_for_cond,
732 : NULL, true, GSI_SAME_STMT);
733 : }
734 89531 : gimple_cond_set_condition_from_tree (inner_cond, cond);
735 89531 : update_stmt (inner_cond);
736 :
737 : /* Leave CFG optimization to cfg_cleanup. */
738 89531 : gimple_cond_set_condition_from_tree (outer_cond,
739 : outer_inv
740 : ? boolean_false_node
741 : : boolean_true_node);
742 89531 : update_stmt (outer_cond);
743 : }
744 :
745 : /* We're changing conditions that guard inner blocks, so reset flow sensitive
746 : info and avoid introducing undefined behavior. */
747 179688 : for (basic_block bb = gimple_bb (inner_cond), end = gimple_bb (outer_cond);
748 179688 : bb != end; bb = single_pred (bb))
749 : {
750 : /* Clear range info from all stmts in BB which is now guarded by
751 : different conditionals. */
752 89925 : reset_flow_sensitive_info_in_bb (gimple_bb (inner_cond));
753 :
754 : /* We only need to worry about introducing undefined behavior if we've
755 : relaxed the outer condition. */
756 89925 : if (strictening_outer_cond)
757 279 : continue;
758 :
759 : /* Avoid introducing undefined behavior as we move stmts that used to be
760 : guarded by OUTER_COND. */
761 179292 : for (gimple_stmt_iterator gsi = gsi_start_bb (gimple_bb (inner_cond));
762 437008 : !gsi_end_p (gsi); gsi_next (&gsi))
763 347362 : ifcombine_rewrite_to_defined_overflow (gsi);
764 : }
765 :
766 89763 : update_profile_after_ifcombine (gimple_bb (inner_cond),
767 : gimple_bb (outer_cond));
768 :
769 89763 : return true;
770 : }
771 :
772 : /* Returns true if inner_cond_bb contains just the condition or 1/2 statements
773 : that define lhs or rhs with an integer conversion. */
774 :
775 : static bool
776 152596 : can_combine_bbs_with_short_circuit (basic_block inner_cond_bb, tree lhs, tree rhs)
777 : {
778 152596 : gimple_stmt_iterator gsi;
779 152596 : gsi = gsi_start_nondebug_after_labels_bb (inner_cond_bb);
780 : /* If only the condition, this should be allowed. */
781 152596 : if (gsi_one_before_end_p (gsi))
782 : return true;
783 : /* Can have up to 2 statements defining each of lhs/rhs. */
784 75058 : for (int i = 0; i < 2; i++)
785 : {
786 75058 : gimple *stmt = gsi_stmt (gsi);
787 75058 : if (!is_gimple_assign (stmt)
788 75058 : || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt)))
789 : return false;
790 : /* The defining statement needs to match either the lhs or rhs of
791 : the condition. */
792 7668 : if (lhs != gimple_assign_lhs (stmt)
793 7668 : && rhs != gimple_assign_lhs (stmt))
794 : return false;
795 4012 : gsi_next_nondebug (&gsi);
796 85933 : if (gsi_one_before_end_p (gsi))
797 : return true;
798 : }
799 : return false;
800 : }
801 :
802 : /* If-convert on a and pattern with a common else block. The inner
803 : if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
804 : inner_inv, outer_inv indicate whether the conditions are inverted.
805 : Returns true if the edges to the common else basic-block were merged. */
806 :
807 : static bool
808 263102 : ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv,
809 : basic_block outer_cond_bb, bool outer_inv)
810 : {
811 263102 : gimple_stmt_iterator gsi;
812 263102 : tree name1, name2, bit1, bit2, bits1, bits2;
813 :
814 526204 : gcond *inner_cond = safe_dyn_cast <gcond *> (*gsi_last_bb (inner_cond_bb));
815 263102 : if (!inner_cond)
816 : return false;
817 :
818 547496 : gcond *outer_cond = safe_dyn_cast <gcond *> (*gsi_last_bb (outer_cond_bb));
819 263102 : if (!outer_cond)
820 : return false;
821 :
822 : /* niter analysis does not cope with boolean typed loop exit conditions.
823 : Avoid turning an analyzable exit into an unanalyzable one. */
824 263102 : if (inner_cond_bb->loop_father == outer_cond_bb->loop_father
825 263102 : && loop_exits_from_bb_p (inner_cond_bb->loop_father, inner_cond_bb)
826 289660 : && loop_exits_from_bb_p (outer_cond_bb->loop_father, outer_cond_bb))
827 : {
828 21912 : tree outer_type = TREE_TYPE (gimple_cond_lhs (outer_cond));
829 21912 : tree inner_type = TREE_TYPE (gimple_cond_lhs (inner_cond));
830 21912 : if (TREE_CODE (outer_type) == INTEGER_TYPE
831 7488 : || POINTER_TYPE_P (outer_type)
832 3732 : || TREE_CODE (inner_type) == INTEGER_TYPE
833 670 : || POINTER_TYPE_P (inner_type))
834 : return false;
835 : }
836 :
837 : /* See if we test a single bit of the same name in both tests. In
838 : that case remove the outer test, merging both else edges,
839 : and change the inner one to test for
840 : name & (bit1 | bit2) == (bit1 | bit2). */
841 241810 : if (recognize_single_bit_test (inner_cond, &name1, &bit1, inner_inv)
842 3005 : && recognize_single_bit_test (outer_cond, &name2, &bit2, outer_inv)
843 243386 : && name1 == name2)
844 : {
845 1001 : tree t, t2;
846 :
847 1001 : if (TREE_CODE (name1) == SSA_NAME
848 1001 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name1))
849 : return false;
850 :
851 : /* Do it. */
852 1001 : gsi = gsi_for_stmt (inner_cond);
853 1001 : location_t loc1 = gimple_location (inner_cond);
854 1001 : location_t loc2 = gimple_location (outer_cond);
855 2002 : t = gimple_build (&gsi, true, GSI_SAME_STMT, loc1, LSHIFT_EXPR,
856 1001 : TREE_TYPE (name1),
857 1001 : build_int_cst (TREE_TYPE (name1), 1), bit1);
858 2002 : t2 = gimple_build (&gsi, true, GSI_SAME_STMT, loc2, LSHIFT_EXPR,
859 1001 : TREE_TYPE (name1),
860 1001 : build_int_cst (TREE_TYPE (name1), 1), bit2);
861 1001 : t = gimple_build (&gsi, true, GSI_SAME_STMT, loc1, BIT_IOR_EXPR,
862 1001 : TREE_TYPE (name1), t, t2);
863 1001 : t2 = gimple_build (&gsi, true, GSI_SAME_STMT, loc1, BIT_AND_EXPR,
864 1001 : TREE_TYPE (name1), name1, t);
865 :
866 1001 : t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t);
867 :
868 1001 : if (!ifcombine_replace_cond (inner_cond, inner_inv,
869 : outer_cond, outer_inv,
870 : t, true, NULL_TREE))
871 : return false;
872 :
873 1001 : if (dump_file)
874 : {
875 1 : fprintf (dump_file, "optimizing double bit test to ");
876 1 : print_generic_expr (dump_file, name1);
877 1 : fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
878 1 : print_generic_expr (dump_file, bit1);
879 1 : fprintf (dump_file, ") | (1 << ");
880 1 : print_generic_expr (dump_file, bit2);
881 1 : fprintf (dump_file, ")\n");
882 : }
883 :
884 1001 : return true;
885 : }
886 :
887 : /* See if we have two bit tests of the same name in both tests.
888 : In that case remove the outer test and change the inner one to
889 : test for name & (bits1 | bits2) != 0. */
890 240809 : else if (recognize_bits_test (inner_cond, &name1, &bits1, !inner_inv)
891 240809 : && recognize_bits_test (outer_cond, &name2, &bits2, !outer_inv))
892 : {
893 2752 : tree t;
894 :
895 2752 : if ((TREE_CODE (name1) == SSA_NAME
896 2751 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name1))
897 5503 : || (TREE_CODE (name2) == SSA_NAME
898 2751 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name2)))
899 : return false;
900 :
901 : /* Find the common name which is bit-tested. */
902 2752 : if (name1 == name2)
903 : ;
904 905 : else if (bits1 == bits2)
905 : {
906 86 : std::swap (name2, bits2);
907 86 : std::swap (name1, bits1);
908 : }
909 819 : else if (name1 == bits2)
910 5 : std::swap (name2, bits2);
911 814 : else if (bits1 == name2)
912 0 : std::swap (name1, bits1);
913 : else
914 814 : goto bits_test_failed;
915 :
916 : /* As we strip non-widening conversions in finding a common
917 : name that is tested make sure to end up with an integral
918 : type for building the bit operations. */
919 1938 : if (TYPE_PRECISION (TREE_TYPE (bits1))
920 1938 : >= TYPE_PRECISION (TREE_TYPE (bits2)))
921 : {
922 1938 : bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
923 1938 : name1 = fold_convert (TREE_TYPE (bits1), name1);
924 1938 : bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
925 1938 : bits2 = fold_convert (TREE_TYPE (bits1), bits2);
926 : }
927 : else
928 : {
929 0 : bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
930 0 : name1 = fold_convert (TREE_TYPE (bits2), name1);
931 0 : bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
932 0 : bits1 = fold_convert (TREE_TYPE (bits2), bits1);
933 : }
934 :
935 1938 : t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
936 1938 : t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
937 1938 : t = fold_build2 (EQ_EXPR, boolean_type_node, t,
938 : build_int_cst (TREE_TYPE (t), 0));
939 1938 : if (!ifcombine_replace_cond (inner_cond, inner_inv,
940 : outer_cond, outer_inv,
941 : t, false, NULL_TREE))
942 : return false;
943 :
944 1938 : if (dump_file)
945 : {
946 1 : fprintf (dump_file, "optimizing bits or bits test to ");
947 1 : print_generic_expr (dump_file, name1);
948 1 : fprintf (dump_file, " & T != 0\nwith temporary T = ");
949 1 : print_generic_expr (dump_file, bits1);
950 1 : fprintf (dump_file, " | ");
951 1 : print_generic_expr (dump_file, bits2);
952 1 : fprintf (dump_file, "\n");
953 : }
954 :
955 1938 : return true;
956 : }
957 :
958 : /* See if we have two comparisons that we can merge into one. */
959 238871 : else bits_test_failed:
960 238871 : if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
961 238871 : && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
962 : {
963 238871 : tree t, ts = NULL_TREE;
964 238871 : enum tree_code inner_cond_code = gimple_cond_code (inner_cond);
965 238871 : enum tree_code outer_cond_code = gimple_cond_code (outer_cond);
966 :
967 : /* Invert comparisons if necessary (and possible). */
968 238871 : if (inner_inv)
969 165961 : inner_cond_code = invert_tree_comparison (inner_cond_code,
970 165961 : HONOR_NANS (gimple_cond_lhs (inner_cond)));
971 238871 : if (inner_cond_code == ERROR_MARK)
972 : return false;
973 237144 : if (outer_inv)
974 159669 : outer_cond_code = invert_tree_comparison (outer_cond_code,
975 159669 : HONOR_NANS (gimple_cond_lhs (outer_cond)));
976 237144 : if (outer_cond_code == ERROR_MARK)
977 : return false;
978 : /* Don't return false so fast, try maybe_fold_or_comparisons? */
979 :
980 236860 : if (!(t = maybe_fold_and_comparisons (boolean_type_node, inner_cond_code,
981 : gimple_cond_lhs (inner_cond),
982 : gimple_cond_rhs (inner_cond),
983 : outer_cond_code,
984 : gimple_cond_lhs (outer_cond),
985 : gimple_cond_rhs (outer_cond),
986 : gimple_bb (outer_cond)))
987 236860 : && !(t = (fold_truth_andor_for_ifcombine
988 234670 : (TRUTH_ANDIF_EXPR, boolean_type_node,
989 : gimple_location (outer_cond),
990 : outer_cond_code,
991 : gimple_cond_lhs (outer_cond),
992 : gimple_cond_rhs (outer_cond),
993 : gimple_location (inner_cond),
994 : inner_cond_code,
995 : gimple_cond_lhs (inner_cond),
996 : gimple_cond_rhs (inner_cond),
997 234670 : single_pred (inner_cond_bb) != outer_cond_bb
998 : ? &ts : 0))))
999 : {
1000 : /* Only combine conditions in this fallback case if the blocks are
1001 : neighbors. */
1002 231585 : if (single_pred (inner_cond_bb) != outer_cond_bb)
1003 : return false;
1004 152718 : tree t1, t2;
1005 152718 : bool logical_op_non_short_circuit = LOGICAL_OP_NON_SHORT_CIRCUIT;
1006 152718 : if (param_logical_op_non_short_circuit != -1)
1007 157 : logical_op_non_short_circuit
1008 157 : = param_logical_op_non_short_circuit;
1009 152718 : if (!logical_op_non_short_circuit || sanitize_coverage_p ())
1010 122 : return false;
1011 : /* Only do this optimization if the inner bb contains only the conditional
1012 : or there is one or 2 statements which are nop conversion for the comparison. */
1013 152596 : if (!can_combine_bbs_with_short_circuit (inner_cond_bb,
1014 : gimple_cond_lhs (inner_cond),
1015 : gimple_cond_rhs (inner_cond)))
1016 : return false;
1017 81550 : t1 = fold_build2_loc (gimple_location (inner_cond),
1018 : inner_cond_code,
1019 : boolean_type_node,
1020 : gimple_cond_lhs (inner_cond),
1021 : gimple_cond_rhs (inner_cond));
1022 81550 : t2 = fold_build2_loc (gimple_location (outer_cond),
1023 : outer_cond_code,
1024 : boolean_type_node,
1025 : gimple_cond_lhs (outer_cond),
1026 : gimple_cond_rhs (outer_cond));
1027 81550 : t = fold_build2_loc (gimple_location (inner_cond),
1028 : TRUTH_AND_EXPR, boolean_type_node, t1, t2);
1029 : }
1030 :
1031 86825 : if (!ifcombine_replace_cond (inner_cond, inner_inv,
1032 : outer_cond, outer_inv,
1033 : t, false, ts))
1034 : return false;
1035 :
1036 86824 : if (dump_file)
1037 : {
1038 30 : fprintf (dump_file, "optimizing two comparisons to ");
1039 30 : print_generic_expr (dump_file, t);
1040 30 : if (ts)
1041 : {
1042 0 : fprintf (dump_file, " and ");
1043 0 : print_generic_expr (dump_file, ts);
1044 : }
1045 30 : fprintf (dump_file, "\n");
1046 : }
1047 :
1048 86824 : return true;
1049 : }
1050 :
1051 : return false;
1052 : }
1053 :
1054 : /* Helper function for tree_ssa_ifcombine_bb. Recognize a CFG pattern and
1055 : dispatch to the appropriate if-conversion helper for a particular
1056 : set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB.
1057 : PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB.
1058 : OUTER_SUCC_BB is the successor of OUTER_COND_BB on the path towards
1059 : INNER_COND_BB. */
1060 :
1061 : static bool
1062 1126707 : tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb,
1063 : basic_block then_bb, basic_block else_bb,
1064 : basic_block phi_pred_bb, basic_block outer_succ_bb)
1065 : {
1066 : /* The && form is characterized by a common else_bb with
1067 : the two edges leading to it mergable. The latter is
1068 : guaranteed by matching PHI arguments in the else_bb and
1069 : the inner cond_bb having no side-effects. */
1070 1126707 : if (phi_pred_bb != else_bb
1071 1105958 : && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &else_bb)
1072 1214987 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
1073 : {
1074 : /* We have
1075 : <outer_cond_bb>
1076 : if (q) goto inner_cond_bb; else goto else_bb;
1077 : <inner_cond_bb>
1078 : if (p) goto ...; else goto else_bb;
1079 : ...
1080 : <else_bb>
1081 : ...
1082 : */
1083 78302 : return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, false);
1084 : }
1085 :
1086 : /* And a version where the outer condition is negated. */
1087 1048405 : if (phi_pred_bb != else_bb
1088 1027656 : && recognize_if_then_else (outer_cond_bb, &else_bb, &outer_succ_bb)
1089 1061220 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
1090 : {
1091 : /* We have
1092 : <outer_cond_bb>
1093 : if (q) goto else_bb; else goto inner_cond_bb;
1094 : <inner_cond_bb>
1095 : if (p) goto ...; else goto else_bb;
1096 : ...
1097 : <else_bb>
1098 : ...
1099 : */
1100 5220 : return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, true);
1101 : }
1102 :
1103 : /* The || form is characterized by a common then_bb with the
1104 : two edges leading to it mergeable. The latter is guaranteed
1105 : by matching PHI arguments in the then_bb and the inner cond_bb
1106 : having no side-effects. */
1107 1043185 : if (phi_pred_bb != then_bb
1108 1030611 : && recognize_if_then_else (outer_cond_bb, &then_bb, &outer_succ_bb)
1109 1246188 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
1110 : {
1111 : /* We have
1112 : <outer_cond_bb>
1113 : if (q) goto then_bb; else goto inner_cond_bb;
1114 : <inner_cond_bb>
1115 : if (p) goto then_bb; else goto ...;
1116 : <then_bb>
1117 : ...
1118 : */
1119 166962 : return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, true);
1120 : }
1121 :
1122 : /* And a version where the outer condition is negated. */
1123 876223 : if (phi_pred_bb != then_bb
1124 863649 : && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &then_bb)
1125 895118 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
1126 : {
1127 : /* We have
1128 : <outer_cond_bb>
1129 : if (q) goto inner_cond_bb; else goto then_bb;
1130 : <inner_cond_bb>
1131 : if (p) goto then_bb; else goto ...;
1132 : <then_bb>
1133 : ...
1134 : */
1135 12618 : return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false);
1136 : }
1137 :
1138 : return false;
1139 : }
1140 :
1141 : /* Recognize a CFG pattern and dispatch to the appropriate
1142 : if-conversion helper. We start with BB as the innermost
1143 : worker basic-block. Returns true if a transformation was done. */
1144 :
1145 : static bool
1146 4353212 : tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
1147 : {
1148 4353212 : bool ret = false;
1149 4353212 : basic_block then_bb = NULL, else_bb = NULL;
1150 :
1151 4353212 : if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
1152 : return ret;
1153 :
1154 : /* Recognize && and || of two conditions with a common
1155 : then/else block which entry edges we can merge. That is:
1156 : if (a || b)
1157 : ;
1158 : and
1159 : if (a && b)
1160 : ;
1161 : This requires a single predecessor of the inner cond_bb.
1162 :
1163 : Look for an OUTER_COND_BBs to combine with INNER_COND_BB. They need not
1164 : be contiguous, as long as inner and intervening blocks have no side
1165 : effects, and are either single-entry-single-exit or conditionals choosing
1166 : between the same EXIT_BB with the same PHI args, possibly through an
1167 : EXIT_PRED, and the path leading to INNER_COND_BB. EXIT_PRED will be set
1168 : just before (along with a successful combination) or just after setting
1169 : EXIT_BB, to either THEN_BB, ELSE_BB, or INNER_COND_BB. ??? We could
1170 : potentially handle multi-block single-entry-single-exit regions, but the
1171 : loop below only deals with single-entry-single-exit individual intervening
1172 : blocks. Larger regions without side effects are presumably rare, so it's
1173 : probably not worth the effort. */
1174 4930584 : for (basic_block bb = inner_cond_bb, outer_cond_bb, exit_bb = NULL,
1175 : /* This initialization shouldn't be needed, but in case the compiler
1176 : is not smart enough to tell, make it harmless. */
1177 4353175 : exit_pred = NULL;
1178 4930584 : single_pred_p (bb) && bb_no_side_effects_p (bb);
1179 577409 : bb = outer_cond_bb)
1180 : {
1181 1592148 : bool changed = false;
1182 :
1183 1592148 : outer_cond_bb = single_pred (bb);
1184 :
1185 : /* Skip blocks without conditions. */
1186 1592148 : if (single_succ_p (outer_cond_bb))
1187 140215 : continue;
1188 :
1189 : /* When considering noncontiguous conditions, make sure that all
1190 : non-final conditions lead to the same successor of the final
1191 : condition, when not taking the path to inner_bb, so that we can
1192 : combine C into A, both in A && (B && C), and in A || (B || C), but
1193 : neither in A && (B || C), nor A || (B && C). Say, if C goes to
1194 : THEN_BB or ELSE_BB, then B must go to either of these, say X, besides
1195 : C (whether C is then or else), and A must go to X and B (whether then
1196 : or else).
1197 :
1198 : We test for this, while allowing intervening nonconditional blocks, by
1199 : first taking note of which of the successors of the inner conditional
1200 : block is the exit path taken by the first considered outer conditional
1201 : block.
1202 :
1203 : Having identified and saved the exit block in EXIT_BB at the end of
1204 : the loop, here we test that subsequent conditional blocks under
1205 : consideration also use the exit block as a successor, besides the
1206 : block that leads to inner_cond_bb, and that the edges to exit share
1207 : the same phi values. */
1208 1451933 : if (exit_bb
1209 1451933 : && !recognize_if_then_else (outer_cond_bb, &bb, &exit_bb, true))
1210 : break;
1211 :
1212 : /* After checking dests and phi args, we can also skip blocks whose
1213 : conditions have been optimized down to a constant, without trying to
1214 : combine them, but we must not skip the computation of EXIT_BB and the
1215 : checking of same phi args. */
1216 1424026 : if (known_succ_p (outer_cond_bb))
1217 : changed = false;
1218 90967 : else if ((!exit_bb || exit_pred == inner_cond_bb)
1219 1184083 : && tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb,
1220 : then_bb, else_bb, inner_cond_bb, bb))
1221 : changed = true, exit_pred = inner_cond_bb;
1222 1003692 : else if (exit_bb
1223 1003692 : ? exit_pred == else_bb
1224 912842 : : forwarder_block_to (else_bb, then_bb))
1225 : {
1226 : /* Other possibilities for the && form, if else_bb is
1227 : empty forwarder block to then_bb. Compared to the above simpler
1228 : forms this can be treated as if then_bb and else_bb were swapped,
1229 : and the corresponding inner_cond_bb not inverted because of that.
1230 : For same_phi_args_p we look at equality of arguments between
1231 : edge from outer_cond_bb and the forwarder block. */
1232 12842 : if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
1233 : then_bb, else_bb, bb))
1234 : changed = true, exit_pred = else_bb;
1235 : }
1236 990850 : else if (exit_bb
1237 990850 : ? exit_pred == then_bb
1238 900020 : : forwarder_block_to (then_bb, else_bb))
1239 : {
1240 : /* Other possibilities for the || form, if then_bb is
1241 : empty forwarder block to else_bb. Compared to the above simpler
1242 : forms this can be treated as if then_bb and else_bb were swapped,
1243 : and the corresponding inner_cond_bb not inverted because of that.
1244 : For same_phi_args_p we look at equality of arguments between
1245 : edge from outer_cond_bb and the forwarder block. */
1246 20749 : if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
1247 : then_bb, then_bb, bb))
1248 : changed = true, exit_pred = then_bb;
1249 : }
1250 :
1251 : if (changed)
1252 89763 : ret = changed;
1253 :
1254 : /* If the inner condition is gone, there's no point in attempting to
1255 : combine it any further. */
1256 89763 : if (changed && known_succ_p (inner_cond_bb))
1257 : break;
1258 :
1259 : /* Starting at this point in the loop, we start preparing to attempt
1260 : combinations in which OUTER_COND_BB will be an intervening block.
1261 : Checking that it has a single predecessor is a very cheap test, unlike
1262 : the PHI args tests below, so test it early and hopefully save the more
1263 : expensive tests in case we won't be able to try other blocks. */
1264 1423913 : if (!single_pred_p (outer_cond_bb))
1265 : break;
1266 :
1267 : /* Record the exit path taken by the outer condition. */
1268 1060127 : if (!exit_bb)
1269 : {
1270 : /* If we have removed the outer condition entirely, we need not
1271 : commit to an exit block yet, it's as if we'd merged the blocks and
1272 : were starting afresh. This is sound as long as we never replace
1273 : the outer condition with a constant that leads away from the inner
1274 : block. Here's why we never do: when combining contiguous
1275 : conditions, we replace the inner cond, and replace the outer cond
1276 : with a constant that leads to inner, so this case is good. When
1277 : combining noncontiguous blocks, we normally modify outer, and
1278 : replace inner with a constant or remainders of the original
1279 : condition that couldn't be combined. This test would normally not
1280 : hit with noncontiguous blocks, because we'd have computed EXIT_BB
1281 : before reaching the noncontiguous outer block. However, if all
1282 : intervening blocks are unconditional, including those just made
1283 : unconditional, we may replace outer instead of inner with the
1284 : combined condition. If the combined noncontiguous conditions are
1285 : mutually exclusive, we could end up with a constant outer
1286 : condition, but then, the inner condition would also be a constant,
1287 : and then we'd stop iterating because of the known_succ_p
1288 : (inner_cond_bb) test above. */
1289 775003 : if (changed && known_succ_p (outer_cond_bb))
1290 73559 : continue;
1291 :
1292 701444 : if (recognize_if_then_else (outer_cond_bb, &then_bb, &bb, true))
1293 84052 : exit_bb = then_bb;
1294 617392 : else if (recognize_if_then_else (outer_cond_bb, &bb, &else_bb, true))
1295 39543 : exit_bb = else_bb;
1296 : else
1297 : break;
1298 :
1299 : /* Find out which path from INNER_COND_BB shares PHI args with the
1300 : edge (OUTER_COND_BB->EXIT_BB). That path may involve a forwarder
1301 : block, whether THEN_BB or ELSE_BB, and we need to know which one
1302 : satisfies the condition to avoid combinations that could use
1303 : different forwarding arrangements, because they would be unsound.
1304 : E.g., given (a ? 0 : b ? 1 : c ? 1 : 0), after trying to merge b
1305 : and c, we test that both share the same exit block, with the same
1306 : value 1. Whether or not that involves a forwarder block, if we
1307 : don't go through the same (possibly absent) forwarder block in
1308 : subsequent attempted combinations, e.g. a with c, we could find
1309 : that a and inverted c share the same exit block with a different
1310 : value, namely 0, which would enable an unsound merge. We need all
1311 : of inner, intervening and outer blocks to reach the same exit with
1312 : the same value for the transformation to be sound. So here we
1313 : determine how to get to EXIT_BB from outer and inner with the same
1314 : PHI values, record that in EXIT_PRED, and then subsequent
1315 : combination attempts that have OUTER_COND_BB as an intervening
1316 : block will ensure the same path to exit is taken, skipping unsound
1317 : transformations. */
1318 123595 : if (changed)
1319 : /* EXIT_PRED was set along with CHANGED, and the successful
1320 : combination already checked for the same PHI args. */;
1321 123483 : else if (same_phi_args_p (outer_cond_bb, inner_cond_bb, exit_bb))
1322 : exit_pred = inner_cond_bb;
1323 31829 : else if (then_bb == exit_bb
1324 23318 : && forwarder_block_to (else_bb, then_bb)
1325 34149 : && same_phi_args_p (outer_cond_bb, else_bb, exit_bb))
1326 : exit_pred = else_bb;
1327 31785 : else if (else_bb == exit_bb
1328 8511 : && forwarder_block_to (then_bb, else_bb)
1329 32929 : && same_phi_args_p (outer_cond_bb, then_bb, exit_bb))
1330 : exit_pred = then_bb;
1331 : else
1332 : /* If none of the paths share the same PHI args, no combination is
1333 : viable. */
1334 : break;
1335 : /* Skip the PHI args test below, it's redundant with the tests we've
1336 : just performed. */
1337 91979 : continue;
1338 : }
1339 :
1340 : /* Before trying an earlier block, make sure INNER_COND_BB and the
1341 : current OUTER_COND_BB share the same PHI args at EXIT_BB. We don't
1342 : need to check if the latest attempt at combining succeeded, because
1343 : that means we'll have already checked. But we can't only check outer
1344 : and inner, we have to check that all intervening blocks also get to
1345 : exit with the same result, otherwise the transformation may change the
1346 : final result. Consider (a ? 0 : b ? 1 : c ? 0 : -1). If we combine
1347 : (a | c), yielding ((a | c) ? 0 : b ? 1 : [0 ? 0 :] -1), we'd get 0
1348 : rather than 1 when (!a&&b). And if we were to replace inner instead
1349 : of outer, we'd get ([1 ? 0 :] b ? 1 : (a | c) ? 0 : -1), which would
1350 : yield 1 rather than 0 when (a). */
1351 285124 : if (!changed
1352 285124 : && !same_phi_args_p (outer_cond_bb, exit_pred, exit_bb))
1353 : break;
1354 : }
1355 :
1356 4353175 : return ret;
1357 : }
1358 :
1359 : /* Main entry for the tree if-conversion pass. */
1360 :
1361 : namespace {
1362 :
1363 : const pass_data pass_data_tree_ifcombine =
1364 : {
1365 : GIMPLE_PASS, /* type */
1366 : "ifcombine", /* name */
1367 : OPTGROUP_NONE, /* optinfo_flags */
1368 : TV_TREE_IFCOMBINE, /* tv_id */
1369 : ( PROP_cfg | PROP_ssa ), /* properties_required */
1370 : 0, /* properties_provided */
1371 : 0, /* properties_destroyed */
1372 : 0, /* todo_flags_start */
1373 : TODO_update_ssa, /* todo_flags_finish */
1374 : };
1375 :
1376 : class pass_tree_ifcombine : public gimple_opt_pass
1377 : {
1378 : public:
1379 285722 : pass_tree_ifcombine (gcc::context *ctxt)
1380 571444 : : gimple_opt_pass (pass_data_tree_ifcombine, ctxt)
1381 : {}
1382 :
1383 : /* opt_pass methods: */
1384 : unsigned int execute (function *) final override;
1385 :
1386 : }; // class pass_tree_ifcombine
1387 :
1388 : unsigned int
1389 1041410 : pass_tree_ifcombine::execute (function *fun)
1390 : {
1391 1041410 : basic_block *bbs;
1392 1041410 : bool cfg_changed = false;
1393 1041410 : int i;
1394 :
1395 1041410 : bbs = single_pred_before_succ_order ();
1396 1041410 : calculate_dominance_info (CDI_DOMINATORS);
1397 1041410 : mark_ssa_maybe_undefs ();
1398 :
1399 : /* Search every basic block for COND_EXPR we may be able to optimize.
1400 :
1401 : We walk the blocks in order that guarantees that a block with
1402 : a single predecessor is processed after the predecessor.
1403 : This ensures that we collapse outter ifs before visiting the
1404 : inner ones, and also that we do not try to visit a removed
1405 : block. This is opposite of PHI-OPT, because we cascade the
1406 : combining rather than cascading PHIs. */
1407 11418496 : for (i = n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS - 1; i >= 0; i--)
1408 : {
1409 10377086 : basic_block bb = bbs[i];
1410 :
1411 25017623 : if (safe_is_a <gcond *> (*gsi_last_bb (bb)))
1412 4353212 : if (tree_ssa_ifcombine_bb (bb))
1413 10377086 : cfg_changed |= true;
1414 : }
1415 :
1416 1041410 : free (bbs);
1417 :
1418 1041410 : return cfg_changed ? TODO_cleanup_cfg : 0;
1419 : }
1420 :
1421 : } // anon namespace
1422 :
1423 : gimple_opt_pass *
1424 285722 : make_pass_tree_ifcombine (gcc::context *ctxt)
1425 : {
1426 285722 : return new pass_tree_ifcombine (ctxt);
1427 : }
|
