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