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