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