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 32626733 : known_succ_p (basic_block cond_bb)
60 : {
61 67240771 : gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (cond_bb));
62 :
63 30933073 : if (!cond)
64 : return true;
65 :
66 30933073 : return (CONSTANT_CLASS_P (gimple_cond_lhs (cond))
67 30933073 : && 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 36002834 : recognize_if_then_else (basic_block cond_bb,
101 : basic_block *then_bb, basic_block *else_bb,
102 : bool succs_any)
103 : {
104 36002834 : edge t, e;
105 :
106 36002834 : if (EDGE_COUNT (cond_bb->succs) != 2
107 36002834 : || (!succs_any && known_succ_p (cond_bb)))
108 : return false;
109 :
110 : /* Find the then/else edges. */
111 31130825 : t = EDGE_SUCC (cond_bb, 0);
112 31130825 : e = EDGE_SUCC (cond_bb, 1);
113 :
114 31130825 : if (succs_any)
115 605046 : return ((t->dest == *then_bb && e->dest == *else_bb)
116 2494623 : || (t->dest == *else_bb && e->dest == *then_bb));
117 :
118 28965708 : if (!(t->flags & EDGE_TRUE_VALUE))
119 2672084 : std::swap (t, e);
120 28965708 : if (!(t->flags & EDGE_TRUE_VALUE)
121 28965708 : || !(e->flags & EDGE_FALSE_VALUE))
122 : return false;
123 :
124 : /* Check if the edge destinations point to the required block. */
125 28965708 : if (*then_bb
126 22473927 : && t->dest != *then_bb)
127 : return false;
128 24043082 : if (*else_bb
129 2511982 : && e->dest != *else_bb)
130 : return false;
131 :
132 23090738 : if (!*then_bb)
133 6491781 : *then_bb = t->dest;
134 23090738 : if (!*else_bb)
135 21531100 : *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 4503634 : bb_no_side_effects_p (basic_block bb)
145 : {
146 4503634 : gimple_stmt_iterator gsi;
147 :
148 25626279 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
149 : {
150 19035746 : gimple *stmt = gsi_stmt (gsi);
151 :
152 19035746 : if (is_gimple_debug (stmt))
153 11238175 : continue;
154 :
155 7797571 : gassign *ass;
156 7797571 : enum tree_code rhs_code;
157 7797571 : if (gimple_has_side_effects (stmt)
158 : /* Ignore GIMPLE_COND for trapping. */
159 6933756 : || (!is_a<gcond*>(stmt)
160 4846710 : && gimple_could_trap_p (stmt))
161 6054838 : || 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 9007376 : || ((ass = dyn_cast <gassign *> (stmt))
165 3223556 : && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (ass)))
166 4857006 : && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (ass)))
167 839822 : && ((rhs_code = gimple_assign_rhs_code (ass)), true)
168 839822 : && (rhs_code == TRUNC_DIV_EXPR
169 : || rhs_code == CEIL_DIV_EXPR
170 : || rhs_code == FLOOR_DIV_EXPR
171 839822 : || 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 1841 : && (TREE_CODE (gimple_assign_rhs2 (ass)) != INTEGER_CST
175 1841 : || !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 16009894 : || is_gimple_call (stmt))
183 2416735 : return false;
184 :
185 5385380 : ssa_op_iter it;
186 5385380 : tree use;
187 10732974 : FOR_EACH_SSA_TREE_OPERAND (use, stmt, it, SSA_OP_USE)
188 5352138 : 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 2522342 : forwarder_block_to (basic_block bb, basic_block to_bb)
199 : {
200 2522342 : return empty_block_p (bb)
201 359131 : && single_succ_p (bb)
202 2881473 : && 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 1131600 : same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
211 : {
212 1131600 : edge e1 = find_edge (bb1, dest);
213 1131600 : edge e2 = find_edge (bb2, dest);
214 1131600 : gphi_iterator gsi;
215 1131600 : gphi *phi;
216 :
217 1392879 : for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
218 : {
219 349282 : phi = gsi.phi ();
220 349282 : if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
221 349282 : 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 7716 : 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 7716 : if (TREE_CODE (candidate) == SSA_NAME
237 7716 : && has_single_use (candidate))
238 : {
239 7061 : gimple *def_stmt = SSA_NAME_DEF_STMT (candidate);
240 7061 : if (is_gimple_assign (def_stmt)
241 7061 : && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
242 : {
243 70 : if (TYPE_PRECISION (TREE_TYPE (candidate))
244 70 : <= 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 453198 : recognize_single_bit_test (gcond *cond, tree *name, tree *bit, bool inv)
259 : {
260 453198 : gimple *stmt;
261 :
262 : /* Get at the definition of the result of the bit test. */
263 453198 : if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
264 114882 : || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
265 568065 : || !integer_zerop (gimple_cond_rhs (cond)))
266 : return false;
267 88605 : stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
268 88605 : 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 84209 : if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
277 11090 : && integer_onep (gimple_assign_rhs2 (stmt))
278 84706 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
279 : {
280 497 : 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 497 : stmt = SSA_NAME_DEF_STMT (orig_name);
285 :
286 498 : while (is_gimple_assign (stmt)
287 498 : && ((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 378 : || 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 497 : if (is_gimple_assign (stmt)
296 497 : && 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 378 : *bit = integer_zero_node;
306 378 : *name = get_name_for_bit_test (orig_name);
307 : }
308 :
309 : return true;
310 : }
311 :
312 : /* Another form is
313 : D.1987_7 = op0 & (1 << CST)
314 : if (D.1987_7 != 0) */
315 83712 : if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
316 10593 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
317 94305 : && integer_pow2p (gimple_assign_rhs2 (stmt)))
318 : {
319 5613 : *name = gimple_assign_rhs1 (stmt);
320 5613 : *bit = build_int_cst (integer_type_node,
321 5613 : tree_log2 (gimple_assign_rhs2 (stmt)));
322 5613 : 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 78099 : if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
330 4980 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
331 83079 : && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
332 : {
333 3863 : gimple *tmp;
334 :
335 : /* Both arguments of the BIT_AND_EXPR can be the single-bit
336 : specifying expression. */
337 3863 : tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
338 3863 : if (is_gimple_assign (tmp)
339 3716 : && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
340 3882 : && 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 3844 : tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
348 3844 : if (is_gimple_assign (tmp)
349 3747 : && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
350 3892 : && integer_onep (gimple_assign_rhs1 (tmp)))
351 : {
352 48 : *name = gimple_assign_rhs1 (stmt);
353 48 : *bit = gimple_assign_rhs2 (tmp);
354 48 : 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 458678 : recognize_bits_test (gcond *cond, tree *name, tree *bits, bool inv)
368 : {
369 458678 : gimple *stmt;
370 :
371 : /* Get at the definition of the result of the bit test. */
372 458678 : if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
373 279411 : || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
374 738076 : || !integer_zerop (gimple_cond_rhs (cond)))
375 : return false;
376 56485 : stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
377 56485 : if (!is_gimple_assign (stmt)
378 56485 : || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
379 : return false;
380 :
381 15907 : *name = gimple_assign_rhs1 (stmt);
382 15907 : *bits = gimple_assign_rhs2 (stmt);
383 :
384 15907 : 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 94088 : 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 94088 : gcc_assert (single_pred_p (inner_cond_bb));
397 :
398 94088 : basic_block outer_to_inner_bb = inner_cond_bb;
399 94088 : profile_probability prob = profile_probability::always ();
400 94351 : for (;;)
401 : {
402 94351 : basic_block parent = single_pred (outer_to_inner_bb);
403 94351 : prob *= find_edge (parent, outer_to_inner_bb)->probability;
404 94351 : if (parent == outer_cond_bb)
405 : break;
406 : outer_to_inner_bb = parent;
407 : }
408 :
409 94088 : edge outer_to_inner = find_edge (outer_cond_bb, outer_to_inner_bb);
410 94088 : edge outer2 = (EDGE_SUCC (outer_cond_bb, 0) == outer_to_inner
411 42431 : ? EDGE_SUCC (outer_cond_bb, 1)
412 136519 : : EDGE_SUCC (outer_cond_bb, 0));
413 94088 : edge inner_taken = EDGE_SUCC (inner_cond_bb, 0);
414 94088 : edge inner_not_taken = EDGE_SUCC (inner_cond_bb, 1);
415 :
416 94088 : if (inner_taken->dest != outer2->dest)
417 35983 : std::swap (inner_taken, inner_not_taken);
418 94088 : gcc_assert (inner_taken->dest == outer2->dest);
419 :
420 94088 : if (outer_to_inner_bb == inner_cond_bb
421 94088 : && 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 93755 : 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 93755 : if (inner_taken->probability == profile_probability::always ())
435 : ;
436 : else
437 90555 : inner_taken->probability = outer2->probability
438 90555 : + outer_to_inner->probability * inner_taken->probability;
439 93755 : inner_not_taken->probability = profile_probability::always ()
440 93755 : - inner_taken->probability;
441 :
442 93755 : outer_to_inner->probability = profile_probability::always ();
443 93755 : outer2->probability = profile_probability::never ();
444 : }
445 333 : 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 212 : prob *= inner_taken->probability;
453 212 : outer2->probability += prob;
454 212 : outer_to_inner->probability = profile_probability::always ()
455 212 : - outer2->probability;
456 :
457 212 : inner_taken->probability = profile_probability::never ();
458 212 : 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 94088 : }
476 :
477 : /* Set NAME's bit in USED if OUTER dominates it. */
478 :
479 : static void
480 1416 : ifcombine_mark_ssa_name (bitmap used, tree name, basic_block outer)
481 : {
482 1416 : if (!name || TREE_CODE (name) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (name))
483 : return;
484 :
485 670 : gimple *def = SSA_NAME_DEF_STMT (name);
486 670 : basic_block bb = gimple_bb (def);
487 670 : if (!dominated_by_p (CDI_DOMINATORS, bb, outer))
488 : return;
489 :
490 463 : 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 1392 : ifcombine_mark_ssa_name_walk (tree *t, int *, void *data_)
506 : {
507 1392 : ifcombine_mark_ssa_name_t *data = (ifcombine_mark_ssa_name_t *)data_;
508 :
509 1392 : ifcombine_mark_ssa_name (data->used, *t, data->outer);
510 :
511 1392 : 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 426333 : ifcombine_rewrite_to_defined_overflow (gimple_stmt_iterator gsi)
520 : {
521 426333 : if (!gimple_needing_rewrite_undefined (gsi_stmt (gsi)))
522 : return;
523 36 : 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 94204 : 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 94204 : 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 94204 : if (!cond2
542 94198 : && TREE_CODE (cond) == TRUTH_ANDIF_EXPR
543 94340 : && 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 94204 : bool outer_p = cond2 || (single_pred (gimple_bb (inner_cond))
551 94083 : != gimple_bb (outer_cond));
552 : bool result_inv = outer_p ? outer_inv : inner_inv;
553 94204 : bool strictening_outer_cond = !split_single_cond && outer_p;
554 :
555 94204 : if (result_inv)
556 59501 : cond = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
557 :
558 94204 : if (tree tcanon = canonicalize_cond_expr_cond (cond))
559 6112 : cond = tcanon;
560 88092 : else if (must_canon)
561 : return false;
562 :
563 94089 : if (outer_p)
564 : {
565 334 : {
566 334 : auto_bitmap used;
567 334 : basic_block outer_bb = gimple_bb (outer_cond);
568 :
569 334 : 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 334 : {
574 334 : ifcombine_mark_ssa_name_t data = { used, outer_bb };
575 334 : walk_tree (&cond, ifcombine_mark_ssa_name_walk, &data, NULL);
576 : }
577 :
578 334 : if (!bitmap_empty_p (used))
579 : {
580 241 : const int max_stmts = 6;
581 241 : 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 651 : for (basic_block bb = gimple_bb (inner_cond);
586 651 : bb != outer_bb; bb = single_pred (bb))
587 : {
588 822 : for (gimple_stmt_iterator gsitr = gsi_last_bb (bb);
589 2748 : !gsi_end_p (gsitr); gsi_prev (&gsitr))
590 : {
591 1926 : gimple *stmt = gsi_stmt (gsitr);
592 1926 : bool move = false;
593 1926 : tree t;
594 1926 : ssa_op_iter it;
595 :
596 2927 : FOR_EACH_SSA_TREE_OPERAND (t, stmt, it, SSA_OP_DEF)
597 1143 : if (bitmap_bit_p (used, SSA_NAME_VERSION (t)))
598 : {
599 : move = true;
600 : break;
601 : }
602 :
603 1926 : if (!move)
604 1784 : 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 411 : for (gphi_iterator gsi = gsi_start_phis (bb);
623 415 : !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 240 : gimple_stmt_iterator gsins = gsi_for_stmt (outer_cond);
655 240 : unsigned i;
656 240 : gimple *stmt;
657 620 : 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 380 : 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 241 : }
691 1 : }
692 :
693 333 : 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 333 : gimple_cond_set_condition_from_tree (outer_cond, cond);
703 333 : update_stmt (outer_cond);
704 :
705 333 : 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 212 : gimple_cond_set_condition_from_tree (inner_cond,
723 : inner_inv
724 : ? boolean_false_node
725 : : boolean_true_node);
726 333 : update_stmt (inner_cond);
727 : }
728 : else
729 : {
730 93755 : if (!is_gimple_condexpr_for_cond (cond))
731 : {
732 87878 : gimple_stmt_iterator gsi = gsi_for_stmt (inner_cond);
733 87878 : cond = force_gimple_operand_gsi_1 (&gsi, cond,
734 : is_gimple_condexpr_for_cond,
735 : NULL, true, GSI_SAME_STMT);
736 : }
737 93755 : gimple_cond_set_condition_from_tree (inner_cond, cond);
738 93755 : update_stmt (inner_cond);
739 :
740 : /* Leave CFG optimization to cfg_cleanup. */
741 93755 : gimple_cond_set_condition_from_tree (outer_cond,
742 : outer_inv
743 : ? boolean_false_node
744 : : boolean_true_node);
745 93755 : 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 188439 : for (basic_block bb = gimple_bb (inner_cond), end = gimple_bb (outer_cond);
751 188439 : 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 94351 : 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 94351 : if (strictening_outer_cond)
760 481 : continue;
761 :
762 : /* Avoid introducing undefined behavior as we move stmts that used to be
763 : guarded by OUTER_COND. */
764 187740 : for (gimple_stmt_iterator gsi = gsi_start_bb (gimple_bb (inner_cond));
765 520063 : !gsi_end_p (gsi); gsi_next (&gsi))
766 426193 : ifcombine_rewrite_to_defined_overflow (gsi);
767 : }
768 :
769 94088 : update_profile_after_ifcombine (gimple_bb (inner_cond),
770 : gimple_bb (outer_cond));
771 :
772 94088 : 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 225706 : can_combine_bbs_with_short_circuit (basic_block inner_cond_bb, tree lhs, tree rhs)
780 : {
781 225706 : gimple_stmt_iterator gsi;
782 225706 : gsi = gsi_start_nondebug_after_labels_bb (inner_cond_bb);
783 : /* If only the condition, this should be allowed. */
784 225706 : if (gsi_one_before_end_p (gsi))
785 : return true;
786 : /* Can have up to 2 statements defining each of lhs/rhs. */
787 145847 : for (int i = 0; i < 2; i++)
788 : {
789 145847 : gimple *stmt = gsi_stmt (gsi);
790 145847 : if (!is_gimple_assign (stmt)
791 145847 : || !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 11644 : if (lhs != gimple_assign_lhs (stmt)
796 11644 : && rhs != gimple_assign_lhs (stmt))
797 : return false;
798 4701 : gsi_next_nondebug (&gsi);
799 5343 : 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 471737 : bb_guards_loop_p (basic_block bb)
813 : {
814 471737 : edge e;
815 471737 : edge_iterator ei;
816 1376302 : FOR_EACH_EDGE (e, ei, bb->succs)
817 : {
818 933063 : basic_block h = e->dest;
819 933063 : if (single_succ_p (h) && !bb_loop_header_p (h))
820 373628 : h = single_succ (h);
821 933063 : 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 532703 : ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv,
834 : basic_block outer_cond_bb, bool outer_inv)
835 : {
836 532703 : gimple_stmt_iterator gsi;
837 532703 : tree name1, name2, bit1, bit2, bits1, bits2;
838 :
839 1065406 : gcond *inner_cond = safe_dyn_cast <gcond *> (*gsi_last_bb (inner_cond_bb));
840 532703 : if (!inner_cond)
841 : return false;
842 :
843 1065406 : gcond *outer_cond = safe_dyn_cast <gcond *> (*gsi_last_bb (outer_cond_bb));
844 532703 : 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 532703 : if (gimple_could_trap_p (inner_cond))
850 : {
851 6398 : if (!operand_equal_p (gimple_cond_lhs (inner_cond),
852 6398 : gimple_cond_lhs (outer_cond))
853 9249 : || !operand_equal_p (gimple_cond_rhs (inner_cond),
854 2851 : gimple_cond_rhs (outer_cond)))
855 : 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 679 : tree res = NULL_TREE;
860 679 : tree_code outer_cond_code = gimple_cond_code (outer_cond);
861 679 : tree_code inner_cond_code = gimple_cond_code (inner_cond);
862 679 : tree larg = gimple_cond_lhs (inner_cond);
863 679 : tree rarg = gimple_cond_rhs (inner_cond);
864 : // Handle `(a && b)`, no inverse
865 679 : if (!inner_inv && !outer_inv)
866 256 : res = combine_comparisons (UNKNOWN_LOCATION, TRUTH_ANDIF_EXPR,
867 : outer_cond_code, inner_cond_code,
868 : boolean_type_node, boolean_type_node,
869 : larg, rarg);
870 : // If both are inverse, `!a && !b`, then handle it as `!(a || b)`
871 : // As that !a or !b are most likely not producing a comparison code.
872 423 : else if (inner_inv && outer_inv)
873 : {
874 132 : res = combine_comparisons (UNKNOWN_LOCATION, TRUTH_ORIF_EXPR,
875 : outer_cond_code, inner_cond_code,
876 : boolean_type_node, boolean_type_node,
877 : larg, rarg);
878 132 : if (res)
879 120 : res = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (res), res);
880 : }
881 : else
882 : {
883 : // Handles the case where one is inverted and the other is not.
884 291 : tree_code inner_cond_code1 = inner_cond_code;
885 291 : tree_code outer_cond_code1 = outer_cond_code;
886 : // Try first `!a && b` and `a && !b`, those might be invertable.
887 291 : if (inner_inv)
888 236 : inner_cond_code1 = invert_tree_comparison (inner_cond_code1,
889 : HONOR_NANS (larg));
890 55 : else if (outer_inv)
891 55 : outer_cond_code1 = invert_tree_comparison (outer_cond_code1,
892 : HONOR_NANS (larg));
893 291 : if (inner_cond_code1 != ERROR_MARK && outer_cond_code1 != ERROR_MARK)
894 224 : res = combine_comparisons (UNKNOWN_LOCATION, TRUTH_ANDIF_EXPR,
895 : outer_cond_code1, inner_cond_code1,
896 : boolean_type_node, boolean_type_node,
897 : larg, rarg);
898 : // Otherwise, we need to try `!(!a || b)
899 67 : else if (inner_cond_code1 == ERROR_MARK)
900 : {
901 : // a && !b -> !(!a || b)
902 32 : outer_cond_code1 = invert_tree_comparison (outer_cond_code,
903 : HONOR_NANS (larg));
904 32 : if (outer_cond_code1 != ERROR_MARK)
905 12 : res = combine_comparisons (UNKNOWN_LOCATION, TRUTH_ORIF_EXPR,
906 : outer_cond_code1, inner_cond_code,
907 : boolean_type_node, boolean_type_node,
908 : larg, rarg);
909 12 : if (res)
910 12 : res = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (res), res);
911 : }
912 : // Or `!(a || !b)`
913 : else
914 : {
915 : // !a && b -> !(a || !b)
916 35 : inner_cond_code1 = invert_tree_comparison (inner_cond_code,
917 : HONOR_NANS (larg));
918 35 : if (inner_cond_code1 != ERROR_MARK)
919 0 : res = combine_comparisons (UNKNOWN_LOCATION, TRUTH_ORIF_EXPR,
920 : outer_cond_code, inner_cond_code1,
921 : boolean_type_node, boolean_type_node,
922 : larg, rarg);
923 0 : if (res)
924 0 : res = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (res), res);
925 : }
926 : }
927 612 : if (res)
928 : {
929 493 : if (!ifcombine_replace_cond (inner_cond, inner_inv,
930 : outer_cond, outer_inv,
931 : res, true, NULL_TREE))
932 : return false;
933 :
934 378 : if (dump_file)
935 : {
936 5 : fprintf (dump_file, "optimizing trapping cond to ");
937 5 : print_generic_expr (dump_file, res);
938 5 : fprintf (dump_file, "\n");
939 : }
940 : return true;
941 : }
942 : return false;
943 : }
944 :
945 : /* niter analysis does not cope with boolean typed loop exit conditions, nor
946 : with boolean loop guards. Avoid turning an analyzable loop exit or guard
947 : into an unanalyzable one. */
948 526305 : if ((inner_cond_bb->loop_father == outer_cond_bb->loop_father
949 526305 : && loop_exits_from_bb_p (inner_cond_bb->loop_father, inner_cond_bb)
950 60957 : && loop_exits_from_bb_p (outer_cond_bb->loop_father, outer_cond_bb))
951 998042 : || bb_guards_loop_p (inner_cond_bb))
952 : {
953 83066 : tree outer_type = TREE_TYPE (gimple_cond_lhs (outer_cond));
954 83066 : tree inner_type = TREE_TYPE (gimple_cond_lhs (inner_cond));
955 83066 : if (TREE_CODE (outer_type) == INTEGER_TYPE
956 20993 : || POINTER_TYPE_P (outer_type)
957 11424 : || TREE_CODE (inner_type) == INTEGER_TYPE
958 6784 : || POINTER_TYPE_P (inner_type))
959 : return false;
960 : }
961 :
962 : /* See if we test a single bit of the same name in both tests. In
963 : that case remove the outer test, merging both else edges,
964 : and change the inner one to test for
965 : name & (bit1 | bit2) == (bit1 | bit2). */
966 449100 : if (recognize_single_bit_test (inner_cond, &name1, &bit1, inner_inv)
967 4098 : && recognize_single_bit_test (outer_cond, &name2, &bit2, outer_inv)
968 451179 : && name1 == name2)
969 : {
970 1018 : tree t, t2;
971 :
972 1018 : if (TREE_CODE (name1) == SSA_NAME
973 1018 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name1))
974 : return false;
975 :
976 : /* Do it. */
977 1018 : gsi = gsi_for_stmt (inner_cond);
978 1018 : location_t loc1 = gimple_location (inner_cond);
979 1018 : location_t loc2 = gimple_location (outer_cond);
980 2036 : t = gimple_build (&gsi, true, GSI_SAME_STMT, loc1, LSHIFT_EXPR,
981 1018 : TREE_TYPE (name1),
982 1018 : build_int_cst (TREE_TYPE (name1), 1), bit1);
983 2036 : t2 = gimple_build (&gsi, true, GSI_SAME_STMT, loc2, LSHIFT_EXPR,
984 1018 : TREE_TYPE (name1),
985 1018 : build_int_cst (TREE_TYPE (name1), 1), bit2);
986 1018 : t = gimple_build (&gsi, true, GSI_SAME_STMT, loc1, BIT_IOR_EXPR,
987 1018 : TREE_TYPE (name1), t, t2);
988 1018 : t2 = gimple_build (&gsi, true, GSI_SAME_STMT, loc1, BIT_AND_EXPR,
989 1018 : TREE_TYPE (name1), name1, t);
990 :
991 1018 : t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t);
992 :
993 1018 : if (!ifcombine_replace_cond (inner_cond, inner_inv,
994 : outer_cond, outer_inv,
995 : t, true, NULL_TREE))
996 : return false;
997 :
998 1018 : if (dump_file)
999 : {
1000 1 : fprintf (dump_file, "optimizing double bit test to ");
1001 1 : print_generic_expr (dump_file, name1);
1002 1 : fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
1003 1 : print_generic_expr (dump_file, bit1);
1004 1 : fprintf (dump_file, ") | (1 << ");
1005 1 : print_generic_expr (dump_file, bit2);
1006 1 : fprintf (dump_file, ")\n");
1007 : }
1008 :
1009 : return true;
1010 : }
1011 :
1012 : /* See if we have two bit tests of the same name in both tests.
1013 : In that case remove the outer test and change the inner one to
1014 : test for name & (bits1 | bits2) != 0. */
1015 448082 : else if (recognize_bits_test (inner_cond, &name1, &bits1, !inner_inv)
1016 448082 : && recognize_bits_test (outer_cond, &name2, &bits2, !outer_inv))
1017 : {
1018 5311 : tree t;
1019 :
1020 5311 : if ((TREE_CODE (name1) == SSA_NAME
1021 5311 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name1))
1022 5311 : || (TREE_CODE (name2) == SSA_NAME
1023 5311 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name2))
1024 5311 : || (TREE_CODE (bits1) == SSA_NAME
1025 3285 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (bits1))
1026 10622 : || (TREE_CODE (bits2) == SSA_NAME
1027 3305 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (bits2)))
1028 : return false;
1029 :
1030 : /* Find the common name which is bit-tested. */
1031 5311 : if (name1 == name2)
1032 : ;
1033 3761 : else if (bits1 == bits2)
1034 : {
1035 86 : std::swap (name2, bits2);
1036 86 : std::swap (name1, bits1);
1037 : }
1038 3675 : else if (name1 == bits2)
1039 6 : std::swap (name2, bits2);
1040 3669 : else if (bits1 == name2)
1041 0 : std::swap (name1, bits1);
1042 : else
1043 : {
1044 : /* Look through non-widening conversions, but only on the names
1045 : so that a stripped operand never becomes part of the mask. */
1046 3669 : tree t1 = get_name_for_bit_test (name1);
1047 3669 : tree t2 = get_name_for_bit_test (name2);
1048 3669 : if (t1 != t2)
1049 3658 : goto bits_test_failed;
1050 11 : name1 = name2 = t1;
1051 : }
1052 :
1053 1653 : if (TREE_CODE (name1) == SSA_NAME
1054 1653 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name1))
1055 : return false;
1056 :
1057 : /* As we strip non-widening conversions in finding a common
1058 : name that is tested make sure to end up with an integral
1059 : type for building the bit operations. */
1060 1653 : if (TYPE_PRECISION (TREE_TYPE (bits1))
1061 1653 : >= TYPE_PRECISION (TREE_TYPE (bits2)))
1062 : {
1063 1653 : bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
1064 1653 : name1 = fold_convert (TREE_TYPE (bits1), name1);
1065 1653 : bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
1066 1653 : bits2 = fold_convert (TREE_TYPE (bits1), bits2);
1067 : }
1068 : else
1069 : {
1070 0 : bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
1071 0 : name1 = fold_convert (TREE_TYPE (bits2), name1);
1072 0 : bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
1073 0 : bits1 = fold_convert (TREE_TYPE (bits2), bits1);
1074 : }
1075 :
1076 1653 : t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
1077 1653 : t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
1078 1653 : t = fold_build2 (EQ_EXPR, boolean_type_node, t,
1079 : build_int_cst (TREE_TYPE (t), 0));
1080 1653 : if (!ifcombine_replace_cond (inner_cond, inner_inv,
1081 : outer_cond, outer_inv,
1082 : t, false, NULL_TREE))
1083 : return false;
1084 :
1085 1653 : if (dump_file)
1086 : {
1087 3 : fprintf (dump_file, "optimizing bits or bits test to ");
1088 3 : print_generic_expr (dump_file, name1);
1089 3 : fprintf (dump_file, " & T != 0\nwith temporary T = ");
1090 3 : print_generic_expr (dump_file, bits1);
1091 3 : fprintf (dump_file, " | ");
1092 3 : print_generic_expr (dump_file, bits2);
1093 3 : fprintf (dump_file, "\n");
1094 : }
1095 :
1096 : return true;
1097 : }
1098 :
1099 : /* See if we have two comparisons that we can merge into one. */
1100 : else
1101 : {
1102 446429 : bits_test_failed:
1103 446429 : tree t, ts = NULL_TREE;
1104 446429 : enum tree_code inner_cond_code = gimple_cond_code (inner_cond);
1105 446429 : enum tree_code outer_cond_code = gimple_cond_code (outer_cond);
1106 :
1107 : /* Invert comparisons if necessary (and possible). */
1108 446429 : if (inner_inv)
1109 284994 : inner_cond_code = invert_tree_comparison (inner_cond_code,
1110 284994 : HONOR_NANS (gimple_cond_lhs (inner_cond)));
1111 446429 : if (inner_cond_code == ERROR_MARK)
1112 : return false;
1113 444749 : if (outer_inv)
1114 277809 : outer_cond_code = invert_tree_comparison (outer_cond_code,
1115 277809 : HONOR_NANS (gimple_cond_lhs (outer_cond)));
1116 444749 : if (outer_cond_code == ERROR_MARK)
1117 : return false;
1118 : /* Don't return false so fast, try maybe_fold_or_comparisons? */
1119 :
1120 444046 : if (!(t = maybe_fold_and_comparisons (boolean_type_node,
1121 : TRUTH_ANDIF_EXPR, outer_cond_code,
1122 : gimple_cond_lhs (outer_cond),
1123 : gimple_cond_rhs (outer_cond),
1124 : inner_cond_code,
1125 : gimple_cond_lhs (inner_cond),
1126 : gimple_cond_rhs (inner_cond),
1127 : gimple_bb (outer_cond)))
1128 444046 : && !(t = (fold_truth_andor_for_ifcombine
1129 440944 : (TRUTH_ANDIF_EXPR, boolean_type_node,
1130 : gimple_location (outer_cond),
1131 : outer_cond_code,
1132 : gimple_cond_lhs (outer_cond),
1133 : gimple_cond_rhs (outer_cond),
1134 : gimple_location (inner_cond),
1135 : inner_cond_code,
1136 : gimple_cond_lhs (inner_cond),
1137 : gimple_cond_rhs (inner_cond),
1138 440944 : single_pred (inner_cond_bb) != outer_cond_bb
1139 : ? &ts : 0))))
1140 : {
1141 : /* Only combine conditions in this fallback case if the blocks are
1142 : neighbors. */
1143 437566 : if (single_pred (inner_cond_bb) != outer_cond_bb)
1144 : return false;
1145 225854 : tree t1, t2;
1146 225854 : bool logical_op_non_short_circuit = LOGICAL_OP_NON_SHORT_CIRCUIT;
1147 225854 : if (param_logical_op_non_short_circuit != -1)
1148 175 : logical_op_non_short_circuit
1149 175 : = param_logical_op_non_short_circuit;
1150 225854 : if (!logical_op_non_short_circuit || sanitize_coverage_p ())
1151 : return false;
1152 : /* Only do this optimization if the inner bb contains only the conditional
1153 : or there is one or 2 statements which are nop conversion for the comparison. */
1154 225706 : if (!can_combine_bbs_with_short_circuit (inner_cond_bb,
1155 : gimple_cond_lhs (inner_cond),
1156 : gimple_cond_rhs (inner_cond)))
1157 : return false;
1158 84560 : t1 = fold_build2_loc (gimple_location (inner_cond),
1159 : inner_cond_code,
1160 : boolean_type_node,
1161 : gimple_cond_lhs (inner_cond),
1162 : gimple_cond_rhs (inner_cond));
1163 84560 : t2 = fold_build2_loc (gimple_location (outer_cond),
1164 : outer_cond_code,
1165 : boolean_type_node,
1166 : gimple_cond_lhs (outer_cond),
1167 : gimple_cond_rhs (outer_cond));
1168 84560 : t = fold_build2_loc (gimple_location (inner_cond),
1169 : TRUTH_AND_EXPR, boolean_type_node, t1, t2);
1170 : }
1171 :
1172 91040 : if (!ifcombine_replace_cond (inner_cond, inner_inv,
1173 : outer_cond, outer_inv,
1174 : t, false, ts))
1175 : return false;
1176 :
1177 91039 : if (dump_file)
1178 : {
1179 49 : fprintf (dump_file, "optimizing two comparisons to ");
1180 49 : print_generic_expr (dump_file, t);
1181 49 : if (ts)
1182 : {
1183 0 : fprintf (dump_file, " and ");
1184 0 : print_generic_expr (dump_file, ts);
1185 : }
1186 49 : fprintf (dump_file, "\n");
1187 : }
1188 :
1189 : return true;
1190 : }
1191 :
1192 : return false;
1193 : }
1194 :
1195 : /* Helper function for tree_ssa_ifcombine_bb. Recognize a CFG pattern and
1196 : dispatch to the appropriate if-conversion helper for a particular
1197 : set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB.
1198 : PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB.
1199 : OUTER_SUCC_BB is the successor of OUTER_COND_BB on the path towards
1200 : INNER_COND_BB. */
1201 :
1202 : static bool
1203 1616965 : tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb,
1204 : basic_block then_bb, basic_block else_bb,
1205 : basic_block phi_pred_bb, basic_block outer_succ_bb)
1206 : {
1207 : /* The && form is characterized by a common else_bb with
1208 : the two edges leading to it mergeable. The latter is
1209 : guaranteed by matching PHI arguments in the else_bb and
1210 : the inner cond_bb having no side-effects. */
1211 1616965 : if (phi_pred_bb != else_bb
1212 1593644 : && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &else_bb)
1213 1821663 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
1214 : {
1215 : /* We have
1216 : <outer_cond_bb>
1217 : if (q) goto inner_cond_bb; else goto else_bb;
1218 : <inner_cond_bb>
1219 : if (p) goto ...; else goto else_bb;
1220 : ...
1221 : <else_bb>
1222 : ...
1223 : */
1224 194786 : return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, false);
1225 : }
1226 :
1227 : /* And a version where the outer condition is negated. */
1228 1422179 : if (phi_pred_bb != else_bb
1229 1398858 : && recognize_if_then_else (outer_cond_bb, &else_bb, &outer_succ_bb)
1230 1441604 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
1231 : {
1232 : /* We have
1233 : <outer_cond_bb>
1234 : if (q) goto else_bb; else goto inner_cond_bb;
1235 : <inner_cond_bb>
1236 : if (p) goto ...; else goto else_bb;
1237 : ...
1238 : <else_bb>
1239 : ...
1240 : */
1241 11028 : return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, true);
1242 : }
1243 :
1244 : /* The || form is characterized by a common then_bb with the
1245 : two edges leading to it mergeable. The latter is guaranteed
1246 : by matching PHI arguments in the then_bb and the inner cond_bb
1247 : having no side-effects. */
1248 1411151 : if (phi_pred_bb != then_bb
1249 1397273 : && recognize_if_then_else (outer_cond_bb, &then_bb, &outer_succ_bb)
1250 1742155 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
1251 : {
1252 : /* We have
1253 : <outer_cond_bb>
1254 : if (q) goto then_bb; else goto inner_cond_bb;
1255 : <inner_cond_bb>
1256 : if (p) goto then_bb; else goto ...;
1257 : <then_bb>
1258 : ...
1259 : */
1260 307110 : return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, true);
1261 : }
1262 :
1263 : /* And a version where the outer condition is negated. */
1264 1104041 : if (phi_pred_bb != then_bb
1265 1090163 : && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &then_bb)
1266 1131217 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
1267 : {
1268 : /* We have
1269 : <outer_cond_bb>
1270 : if (q) goto inner_cond_bb; else goto then_bb;
1271 : <inner_cond_bb>
1272 : if (p) goto then_bb; else goto ...;
1273 : <then_bb>
1274 : ...
1275 : */
1276 19779 : return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false);
1277 : }
1278 :
1279 : return false;
1280 : }
1281 :
1282 : /* Recognize a CFG pattern and dispatch to the appropriate
1283 : if-conversion helper. We start with BB as the innermost
1284 : worker basic-block. Returns true if a transformation was done. */
1285 :
1286 : bool
1287 5514698 : tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
1288 : {
1289 5514698 : bool ret = false;
1290 5514698 : basic_block then_bb = NULL, else_bb = NULL;
1291 :
1292 5514698 : if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
1293 : return ret;
1294 :
1295 : /* Recognize && and || of two conditions with a common
1296 : then/else block which entry edges we can merge. That is:
1297 : if (a || b)
1298 : ;
1299 : and
1300 : if (a && b)
1301 : ;
1302 : This requires a single predecessor of the inner cond_bb.
1303 :
1304 : Look for an OUTER_COND_BBs to combine with INNER_COND_BB. They need not
1305 : be contiguous, as long as inner and intervening blocks have no side
1306 : effects, and are either single-entry-single-exit or conditionals choosing
1307 : between the same EXIT_BB with the same PHI args, possibly through an
1308 : EXIT_PRED, and the path leading to INNER_COND_BB. EXIT_PRED will be set
1309 : just before (along with a successful combination) or just after setting
1310 : EXIT_BB, to either THEN_BB, ELSE_BB, or INNER_COND_BB. ??? We could
1311 : potentially handle multi-block single-entry-single-exit regions, but the
1312 : loop below only deals with single-entry-single-exit individual intervening
1313 : blocks. Larger regions without side effects are presumably rare, so it's
1314 : probably not worth the effort. */
1315 6292989 : for (basic_block bb = inner_cond_bb, outer_cond_bb, exit_bb = NULL,
1316 : /* This initialization shouldn't be needed, but in case the compiler
1317 : is not smart enough to tell, make it harmless. */
1318 5514446 : exit_pred = NULL;
1319 6292989 : single_pred_p (bb) && bb_no_side_effects_p (bb);
1320 778543 : bb = outer_cond_bb)
1321 : {
1322 2086899 : bool changed = false;
1323 :
1324 2086899 : outer_cond_bb = single_pred (bb);
1325 :
1326 : /* Skip blocks without conditions. */
1327 2086899 : if (single_succ_p (outer_cond_bb))
1328 189679 : continue;
1329 :
1330 : /* When considering noncontiguous conditions, make sure that all
1331 : non-final conditions lead to the same successor of the final
1332 : condition, when not taking the path to inner_bb, so that we can
1333 : combine C into A, both in A && (B && C), and in A || (B || C), but
1334 : neither in A && (B || C), nor A || (B && C). Say, if C goes to
1335 : THEN_BB or ELSE_BB, then B must go to either of these, say X, besides
1336 : C (whether C is then or else), and A must go to X and B (whether then
1337 : or else).
1338 :
1339 : We test for this, while allowing intervening nonconditional blocks, by
1340 : first taking note of which of the successors of the inner conditional
1341 : block is the exit path taken by the first considered outer conditional
1342 : block.
1343 :
1344 : Having identified and saved the exit block in EXIT_BB at the end of
1345 : the loop, here we test that subsequent conditional blocks under
1346 : consideration also use the exit block as a successor, besides the
1347 : block that leads to inner_cond_bb, and that the edges to exit share
1348 : the same phi values. */
1349 1897220 : if (exit_bb
1350 1897220 : && !recognize_if_then_else (outer_cond_bb, &bb, &exit_bb, true))
1351 : break;
1352 :
1353 : /* After checking dests and phi args, we can also skip blocks whose
1354 : conditions have been optimized down to a constant, without trying to
1355 : combine them, but we must not skip the computation of EXIT_BB and the
1356 : checking of same phi args. */
1357 1831259 : if (known_succ_p (outer_cond_bb))
1358 : changed = false;
1359 232276 : else if ((!exit_bb || exit_pred == inner_cond_bb)
1360 1811730 : && tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb,
1361 : then_bb, else_bb, inner_cond_bb, bb))
1362 : changed = true, exit_pred = inner_cond_bb;
1363 1485806 : else if (exit_bb
1364 1485806 : ? exit_pred == else_bb
1365 1253664 : : forwarder_block_to (else_bb, then_bb))
1366 : {
1367 : /* Other possibilities for the && form, if else_bb is
1368 : empty forwarder block to then_bb. Compared to the above simpler
1369 : forms this can be treated as if then_bb and else_bb were swapped,
1370 : and the corresponding inner_cond_bb not inverted because of that.
1371 : For same_phi_args_p we look at equality of arguments between
1372 : edge from outer_cond_bb and the forwarder block. */
1373 14190 : if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
1374 : then_bb, else_bb, bb))
1375 192 : changed = true, exit_pred = else_bb;
1376 : }
1377 1471616 : else if (exit_bb
1378 1471616 : ? exit_pred == then_bb
1379 1239494 : : forwarder_block_to (then_bb, else_bb))
1380 : {
1381 : /* Other possibilities for the || form, if then_bb is
1382 : empty forwarder block to else_bb. Compared to the above simpler
1383 : forms this can be treated as if then_bb and else_bb were swapped,
1384 : and the corresponding inner_cond_bb not inverted because of that.
1385 : For same_phi_args_p we look at equality of arguments between
1386 : edge from outer_cond_bb and the forwarder block. */
1387 23321 : if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
1388 : then_bb, then_bb, bb))
1389 188 : changed = true, exit_pred = then_bb;
1390 : }
1391 :
1392 380 : if (changed)
1393 94088 : ret = changed;
1394 :
1395 : /* If the inner condition is gone, there's no point in attempting to
1396 : combine it any further. */
1397 94088 : if (changed && known_succ_p (inner_cond_bb))
1398 : break;
1399 :
1400 : /* Starting at this point in the loop, we start preparing to attempt
1401 : combinations in which OUTER_COND_BB will be an intervening block.
1402 : Checking that it has a single predecessor is a very cheap test, unlike
1403 : the PHI args tests below, so test it early and hopefully save the more
1404 : expensive tests in case we won't be able to try other blocks. */
1405 1831029 : if (!single_pred_p (outer_cond_bb))
1406 : break;
1407 :
1408 : /* Record the exit path taken by the outer condition. */
1409 1365026 : if (!exit_bb)
1410 : {
1411 : /* If we have removed the outer condition entirely, we need not
1412 : commit to an exit block yet, it's as if we'd merged the blocks and
1413 : were starting afresh. This is sound as long as we never replace
1414 : the outer condition with a constant that leads away from the inner
1415 : block. Here's why we never do: when combining contiguous
1416 : conditions, we replace the inner cond, and replace the outer cond
1417 : with a constant that leads to inner, so this case is good. When
1418 : combining noncontiguous blocks, we normally modify outer, and
1419 : replace inner with a constant or remainders of the original
1420 : condition that couldn't be combined. This test would normally not
1421 : hit with noncontiguous blocks, because we'd have computed EXIT_BB
1422 : before reaching the noncontiguous outer block. However, if all
1423 : intervening blocks are unconditional, including those just made
1424 : unconditional, we may replace outer instead of inner with the
1425 : combined condition. If the combined noncontiguous conditions are
1426 : mutually exclusive, we could end up with a constant outer
1427 : condition, but then, the inner condition would also be a constant,
1428 : and then we'd stop iterating because of the known_succ_p
1429 : (inner_cond_bb) test above. */
1430 1036735 : if (changed && known_succ_p (outer_cond_bb))
1431 77852 : continue;
1432 :
1433 958883 : if (recognize_if_then_else (outer_cond_bb, &then_bb, &bb, true))
1434 127258 : exit_bb = then_bb;
1435 831625 : else if (recognize_if_then_else (outer_cond_bb, &bb, &else_bb, true))
1436 89999 : exit_bb = else_bb;
1437 : else
1438 : break;
1439 :
1440 : /* Find out which path from INNER_COND_BB shares PHI args with the
1441 : edge (OUTER_COND_BB->EXIT_BB). That path may involve a forwarder
1442 : block, whether THEN_BB or ELSE_BB, and we need to know which one
1443 : satisfies the condition to avoid combinations that could use
1444 : different forwarding arrangements, because they would be unsound.
1445 : E.g., given (a ? 0 : b ? 1 : c ? 1 : 0), after trying to merge b
1446 : and c, we test that both share the same exit block, with the same
1447 : value 1. Whether or not that involves a forwarder block, if we
1448 : don't go through the same (possibly absent) forwarder block in
1449 : subsequent attempted combinations, e.g. a with c, we could find
1450 : that a and inverted c share the same exit block with a different
1451 : value, namely 0, which would enable an unsound merge. We need all
1452 : of inner, intervening and outer blocks to reach the same exit with
1453 : the same value for the transformation to be sound. So here we
1454 : determine how to get to EXIT_BB from outer and inner with the same
1455 : PHI values, record that in EXIT_PRED, and then subsequent
1456 : combination attempts that have OUTER_COND_BB as an intervening
1457 : block will ensure the same path to exit is taken, skipping unsound
1458 : transformations. */
1459 217257 : if (changed)
1460 : /* EXIT_PRED was set along with CHANGED, and the successful
1461 : combination already checked for the same PHI args. */;
1462 217145 : else if (same_phi_args_p (outer_cond_bb, inner_cond_bb, exit_bb))
1463 : exit_pred = inner_cond_bb;
1464 29184 : else if (then_bb == exit_bb
1465 20205 : && forwarder_block_to (else_bb, then_bb)
1466 31822 : && same_phi_args_p (outer_cond_bb, else_bb, exit_bb))
1467 76 : exit_pred = else_bb;
1468 29108 : else if (else_bb == exit_bb
1469 8979 : && forwarder_block_to (then_bb, else_bb)
1470 30337 : && same_phi_args_p (outer_cond_bb, then_bb, exit_bb))
1471 179 : exit_pred = then_bb;
1472 : else
1473 : /* If none of the paths share the same PHI args, no combination is
1474 : viable. */
1475 : break;
1476 : /* Skip the PHI args test below, it's redundant with the tests we've
1477 : just performed. */
1478 188328 : continue;
1479 : }
1480 :
1481 : /* Before trying an earlier block, make sure INNER_COND_BB and the
1482 : current OUTER_COND_BB share the same PHI args at EXIT_BB. We don't
1483 : need to check if the latest attempt at combining succeeded, because
1484 : that means we'll have already checked. But we can't only check outer
1485 : and inner, we have to check that all intervening blocks also get to
1486 : exit with the same result, otherwise the transformation may change the
1487 : final result. Consider (a ? 0 : b ? 1 : c ? 0 : -1). If we combine
1488 : (a | c), yielding ((a | c) ? 0 : b ? 1 : [0 ? 0 :] -1), we'd get 0
1489 : rather than 1 when (!a&&b). And if we were to replace inner instead
1490 : of outer, we'd get ([1 ? 0 :] b ? 1 : (a | c) ? 0 : -1), which would
1491 : yield 1 rather than 0 when (a). */
1492 328291 : if (!changed
1493 328291 : && !same_phi_args_p (outer_cond_bb, exit_pred, exit_bb))
1494 : break;
1495 : }
1496 :
1497 5514446 : return ret;
1498 : }
1499 :
1500 : /* Main entry for the tree if-conversion pass. */
1501 :
1502 : namespace {
1503 :
1504 : const pass_data pass_data_tree_ifcombine =
1505 : {
1506 : GIMPLE_PASS, /* type */
1507 : "ifcombine", /* name */
1508 : OPTGROUP_NONE, /* optinfo_flags */
1509 : TV_TREE_IFCOMBINE, /* tv_id */
1510 : ( PROP_cfg | PROP_ssa ), /* properties_required */
1511 : 0, /* properties_provided */
1512 : 0, /* properties_destroyed */
1513 : 0, /* todo_flags_start */
1514 : TODO_update_ssa, /* todo_flags_finish */
1515 : };
1516 :
1517 : class pass_tree_ifcombine : public gimple_opt_pass
1518 : {
1519 : public:
1520 297180 : pass_tree_ifcombine (gcc::context *ctxt)
1521 594360 : : gimple_opt_pass (pass_data_tree_ifcombine, ctxt)
1522 : {}
1523 :
1524 : /* opt_pass methods: */
1525 : unsigned int execute (function *) final override;
1526 :
1527 : }; // class pass_tree_ifcombine
1528 :
1529 : unsigned int
1530 1062893 : pass_tree_ifcombine::execute (function *fun)
1531 : {
1532 1062893 : basic_block *bbs;
1533 1062893 : bool cfg_changed = false;
1534 1062893 : int i;
1535 :
1536 1062893 : bbs = single_pred_before_succ_order ();
1537 1062893 : calculate_dominance_info (CDI_DOMINATORS);
1538 1062893 : mark_ssa_maybe_undefs ();
1539 :
1540 : /* Search every basic block for COND_EXPR we may be able to optimize.
1541 :
1542 : We walk the blocks in order that guarantees that a block with
1543 : a single predecessor is processed after the predecessor.
1544 : This ensures that we collapse outer ifs before visiting the
1545 : inner ones, and also that we do not try to visit a removed
1546 : block. This is opposite of PHI-OPT, because we cascade the
1547 : combining rather than cascading PHIs. */
1548 11675220 : for (i = n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS - 1; i >= 0; i--)
1549 : {
1550 10612327 : basic_block bb = bbs[i];
1551 :
1552 25575514 : if (safe_is_a <gcond *> (*gsi_last_bb (bb)))
1553 4430234 : if (tree_ssa_ifcombine_bb (bb))
1554 10612327 : cfg_changed |= true;
1555 : }
1556 :
1557 1062893 : free (bbs);
1558 :
1559 1062893 : return cfg_changed ? TODO_cleanup_cfg : 0;
1560 : }
1561 :
1562 : } // anon namespace
1563 :
1564 : gimple_opt_pass *
1565 297180 : make_pass_tree_ifcombine (gcc::context *ctxt)
1566 : {
1567 297180 : return new pass_tree_ifcombine (ctxt);
1568 : }
|