Branch data Line data Source code
1 : : /* Combining of if-expressions on trees.
2 : : Copyright (C) 2007-2025 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 : 9748888 : known_succ_p (basic_block cond_bb)
58 : : {
59 : 20021117 : gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (cond_bb));
60 : :
61 : 9625251 : if (!cond)
62 : : return true;
63 : :
64 : 9625251 : return (CONSTANT_CLASS_P (gimple_cond_lhs (cond))
65 : 9625251 : && 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 : 9627611 : recognize_if_then_else (basic_block cond_bb,
99 : : basic_block *then_bb, basic_block *else_bb,
100 : : bool succs_any = false)
101 : : {
102 : 9627611 : edge t, e;
103 : :
104 : 9627611 : if (EDGE_COUNT (cond_bb->succs) != 2
105 : 9627611 : || (!succs_any && known_succ_p (cond_bb)))
106 : : return false;
107 : :
108 : : /* Find the then/else edges. */
109 : 9602552 : t = EDGE_SUCC (cond_bb, 0);
110 : 9602552 : e = EDGE_SUCC (cond_bb, 1);
111 : :
112 : 9602552 : if (succs_any)
113 : 336528 : return ((t->dest == *then_bb && e->dest == *else_bb)
114 : 2170080 : || (t->dest == *else_bb && e->dest == *then_bb));
115 : :
116 : 8091237 : if (!(t->flags & EDGE_TRUE_VALUE))
117 : 286522 : std::swap (t, e);
118 : 8091237 : if (!(t->flags & EDGE_TRUE_VALUE)
119 : 8091237 : || !(e->flags & EDGE_FALSE_VALUE))
120 : : return false;
121 : :
122 : : /* Check if the edge destinations point to the required block. */
123 : 8091237 : if (*then_bb
124 : 3776088 : && t->dest != *then_bb)
125 : : return false;
126 : 5322757 : if (*else_bb
127 : 1007608 : && e->dest != *else_bb)
128 : : return false;
129 : :
130 : 4665850 : if (!*then_bb)
131 : 4315149 : *then_bb = t->dest;
132 : 4665850 : if (!*else_bb)
133 : 4315149 : *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 : 3428383 : bb_no_side_effects_p (basic_block bb)
143 : : {
144 : 3428383 : gimple_stmt_iterator gsi;
145 : :
146 : 17875612 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
147 : : {
148 : 12931004 : gimple *stmt = gsi_stmt (gsi);
149 : :
150 : 12931004 : if (is_gimple_debug (stmt))
151 : 7129324 : continue;
152 : :
153 : 5801680 : gassign *ass;
154 : 5801680 : enum tree_code rhs_code;
155 : 5801680 : if (gimple_has_side_effects (stmt)
156 : 5222843 : || gimple_could_trap_p (stmt)
157 : 4420484 : || 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 : 6497060 : || ((ass = dyn_cast <gassign *> (stmt))
161 : 2311153 : && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (ass)))
162 : 3594250 : && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (ass)))
163 : 439626 : && ((rhs_code = gimple_assign_rhs_code (ass)), true)
164 : 439626 : && (rhs_code == TRUNC_DIV_EXPR
165 : : || rhs_code == CEIL_DIV_EXPR
166 : : || rhs_code == FLOOR_DIV_EXPR
167 : 439626 : || 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 : 986 : && (TREE_CODE (gimple_assign_rhs2 (ass)) != INTEGER_CST
171 : 986 : || !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 : 11784712 : || is_gimple_call (stmt))
179 : 1912158 : return false;
180 : :
181 : 3892720 : ssa_op_iter it;
182 : 3892720 : tree use;
183 : 7733295 : FOR_EACH_SSA_TREE_OPERAND (use, stmt, it, SSA_OP_USE)
184 : 3843773 : 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 : 1634668 : forwarder_block_to (basic_block bb, basic_block to_bb)
195 : : {
196 : 1634668 : return empty_block_p (bb)
197 : 59163 : && single_succ_p (bb)
198 : 1693831 : && 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 : 788723 : same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
207 : : {
208 : 788723 : edge e1 = find_edge (bb1, dest);
209 : 788723 : edge e2 = find_edge (bb2, dest);
210 : 788723 : gphi_iterator gsi;
211 : 788723 : gphi *phi;
212 : :
213 : 1152967 : for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
214 : : {
215 : 469660 : phi = gsi.phi ();
216 : 469660 : if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
217 : 469660 : 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 : 9809 : 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 : 9809 : if (TREE_CODE (candidate) == SSA_NAME
233 : 9809 : && has_single_use (candidate))
234 : : {
235 : 3695 : gimple *def_stmt = SSA_NAME_DEF_STMT (candidate);
236 : 3695 : if (is_gimple_assign (def_stmt)
237 : 3695 : && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
238 : : {
239 : 169 : if (TYPE_PRECISION (TREE_TYPE (candidate))
240 : 169 : <= 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 : 295419 : recognize_single_bit_test (gcond *cond, tree *name, tree *bit, bool inv)
255 : : {
256 : 295419 : gimple *stmt;
257 : :
258 : : /* Get at the definition of the result of the bit test. */
259 : 295419 : if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
260 : 47655 : || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
261 : 343069 : || !integer_zerop (gimple_cond_rhs (cond)))
262 : 269227 : return false;
263 : 26192 : stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
264 : 26192 : 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 : 20737 : if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
273 : 6397 : && integer_onep (gimple_assign_rhs2 (stmt))
274 : 21329 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
275 : : {
276 : 592 : 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 : 592 : stmt = SSA_NAME_DEF_STMT (orig_name);
281 : :
282 : 593 : while (is_gimple_assign (stmt)
283 : 593 : && ((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 : 504 : || 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 : 592 : if (is_gimple_assign (stmt)
292 : 592 : && 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 : 513 : *bit = integer_zero_node;
302 : 513 : *name = get_name_for_bit_test (orig_name);
303 : : }
304 : :
305 : 592 : return true;
306 : : }
307 : :
308 : : /* Another form is
309 : : D.1987_7 = op0 & (1 << CST)
310 : : if (D.1987_7 != 0) */
311 : 20145 : if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
312 : 5805 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
313 : 25950 : && integer_pow2p (gimple_assign_rhs2 (stmt)))
314 : : {
315 : 3294 : *name = gimple_assign_rhs1 (stmt);
316 : 3294 : *bit = build_int_cst (integer_type_node,
317 : 3294 : tree_log2 (gimple_assign_rhs2 (stmt)));
318 : 3294 : 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 : 16851 : if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
326 : 2511 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
327 : 19362 : && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
328 : : {
329 : 2163 : gimple *tmp;
330 : :
331 : : /* Both arguments of the BIT_AND_EXPR can be the single-bit
332 : : specifying expression. */
333 : 2163 : tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
334 : 2163 : if (is_gimple_assign (tmp)
335 : 2112 : && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
336 : 2173 : && 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 : 2153 : tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
344 : 2153 : if (is_gimple_assign (tmp)
345 : 1996 : && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
346 : 2183 : && 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 : 298023 : recognize_bits_test (gcond *cond, tree *name, tree *bits, bool inv)
364 : : {
365 : 298023 : gimple *stmt;
366 : :
367 : : /* Get at the definition of the result of the bit test. */
368 : 298023 : if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
369 : 186621 : || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
370 : 484644 : || !integer_zerop (gimple_cond_rhs (cond)))
371 : 232634 : return false;
372 : 65389 : stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
373 : 65389 : if (!is_gimple_assign (stmt)
374 : 65389 : || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
375 : : return false;
376 : :
377 : 9296 : *name = get_name_for_bit_test (gimple_assign_rhs1 (stmt));
378 : 9296 : *bits = gimple_assign_rhs2 (stmt);
379 : :
380 : 9296 : 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 : 100227 : 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 : 100227 : gcc_assert (single_pred_p (inner_cond_bb));
393 : :
394 : 100227 : basic_block outer_to_inner_bb = inner_cond_bb;
395 : 100227 : profile_probability prob = profile_probability::always ();
396 : 100387 : for (;;)
397 : : {
398 : 100387 : basic_block parent = single_pred (outer_to_inner_bb);
399 : 100387 : prob *= find_edge (parent, outer_to_inner_bb)->probability;
400 : 100387 : if (parent == outer_cond_bb)
401 : : break;
402 : : outer_to_inner_bb = parent;
403 : : }
404 : :
405 : 100227 : edge outer_to_inner = find_edge (outer_cond_bb, outer_to_inner_bb);
406 : 100227 : edge outer2 = (EDGE_SUCC (outer_cond_bb, 0) == outer_to_inner
407 : 43031 : ? EDGE_SUCC (outer_cond_bb, 1)
408 : 143258 : : EDGE_SUCC (outer_cond_bb, 0));
409 : 100227 : edge inner_taken = EDGE_SUCC (inner_cond_bb, 0);
410 : 100227 : edge inner_not_taken = EDGE_SUCC (inner_cond_bb, 1);
411 : :
412 : 100227 : if (inner_taken->dest != outer2->dest)
413 : 34513 : std::swap (inner_taken, inner_not_taken);
414 : 100227 : gcc_assert (inner_taken->dest == outer2->dest);
415 : :
416 : 100227 : if (outer_to_inner_bb == inner_cond_bb
417 : 100227 : && 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 : 100003 : 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 : 100003 : if (inner_taken->probability == profile_probability::always ())
431 : : ;
432 : : else
433 : 98658 : inner_taken->probability = outer2->probability
434 : 98658 : + outer_to_inner->probability * inner_taken->probability;
435 : 100003 : inner_not_taken->probability = profile_probability::always ()
436 : 100003 : - inner_taken->probability;
437 : :
438 : 100003 : outer_to_inner->probability = profile_probability::always ();
439 : 100003 : outer2->probability = profile_probability::never ();
440 : : }
441 : 224 : 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 : 109 : prob *= inner_taken->probability;
449 : 109 : outer2->probability += prob;
450 : 109 : outer_to_inner->probability = profile_probability::always ()
451 : 109 : - outer2->probability;
452 : :
453 : 109 : inner_taken->probability = profile_probability::never ();
454 : 109 : 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 : 115 : inner_taken->probability *= profile_probability::even ();
463 : 115 : inner_not_taken->probability = profile_probability::always ()
464 : 115 : - inner_taken->probability;
465 : :
466 : 115 : prob *= inner_taken->probability;
467 : 115 : outer2->probability += prob;
468 : 115 : outer_to_inner->probability = profile_probability::always ()
469 : 115 : - outer2->probability;
470 : : }
471 : 100227 : }
472 : :
473 : : /* Set NAME's bit in USED if OUTER dominates it. */
474 : :
475 : : static void
476 : 1093 : ifcombine_mark_ssa_name (bitmap used, tree name, basic_block outer)
477 : : {
478 : 1093 : if (!name || TREE_CODE (name) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (name))
479 : : return;
480 : :
481 : 457 : gimple *def = SSA_NAME_DEF_STMT (name);
482 : 457 : basic_block bb = gimple_bb (def);
483 : 457 : if (!dominated_by_p (CDI_DOMINATORS, bb, outer))
484 : : return;
485 : :
486 : 413 : 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 : 1069 : ifcombine_mark_ssa_name_walk (tree *t, int *, void *data_)
502 : : {
503 : 1069 : ifcombine_mark_ssa_name_t *data = (ifcombine_mark_ssa_name_t *)data_;
504 : :
505 : 1069 : ifcombine_mark_ssa_name (data->used, *t, data->outer);
506 : :
507 : 1069 : 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 : 389256 : ifcombine_rewrite_to_defined_overflow (gimple_stmt_iterator gsi)
516 : : {
517 : 389256 : if (!gimple_needing_rewrite_undefined (gsi_stmt (gsi)))
518 : : return;
519 : 24 : 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 : 100228 : 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 : 100228 : 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 : 100228 : if (!cond2
538 : 100222 : && TREE_CODE (cond) == TRUTH_ANDIF_EXPR
539 : 100358 : && single_pred (gimple_bb (inner_cond)) == gimple_bb (outer_cond))
540 : : {
541 : 109 : cond2 = TREE_OPERAND (cond, 1);
542 : 109 : cond = TREE_OPERAND (cond, 0);
543 : 109 : split_single_cond = true;
544 : : }
545 : :
546 : 100228 : bool outer_p = cond2 || (single_pred (gimple_bb (inner_cond))
547 : 100113 : != gimple_bb (outer_cond));
548 : : bool result_inv = outer_p ? outer_inv : inner_inv;
549 : 100228 : bool strictening_outer_cond = !split_single_cond && outer_p;
550 : :
551 : 100228 : if (result_inv)
552 : 64533 : cond = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
553 : :
554 : 100228 : if (tree tcanon = canonicalize_cond_expr_cond (cond))
555 : 4536 : cond = tcanon;
556 : 95692 : else if (must_canon)
557 : : return false;
558 : :
559 : 100228 : if (outer_p)
560 : : {
561 : 225 : {
562 : 225 : auto_bitmap used;
563 : 225 : basic_block outer_bb = gimple_bb (outer_cond);
564 : :
565 : 225 : 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 : 225 : {
570 : 225 : ifcombine_mark_ssa_name_t data = { used, outer_bb };
571 : 225 : walk_tree (&cond, ifcombine_mark_ssa_name_walk, &data, NULL);
572 : : }
573 : :
574 : 225 : if (!bitmap_empty_p (used))
575 : : {
576 : 208 : const int max_stmts = 6;
577 : 208 : 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 : 555 : for (basic_block bb = gimple_bb (inner_cond);
582 : 555 : bb != outer_bb; bb = single_pred (bb))
583 : : {
584 : 348 : for (gimple_stmt_iterator gsitr = gsi_last_bb (bb);
585 : 4038 : !gsi_end_p (gsitr); gsi_prev (&gsitr))
586 : : {
587 : 1845 : gimple *stmt = gsi_stmt (gsitr);
588 : 1845 : bool move = false;
589 : 1845 : tree t;
590 : 1845 : ssa_op_iter it;
591 : :
592 : 2828 : FOR_EACH_SSA_TREE_OPERAND (t, stmt, it, SSA_OP_DEF)
593 : 1125 : if (bitmap_bit_p (used, SSA_NAME_VERSION (t)))
594 : : {
595 : : move = true;
596 : : break;
597 : : }
598 : :
599 : 1845 : if (!move)
600 : 1703 : 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 : 348 : for (gphi_iterator gsi = gsi_start_phis (bb);
619 : 352 : !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 : 207 : gimple_stmt_iterator gsins = gsi_for_stmt (outer_cond);
651 : 207 : unsigned i;
652 : 207 : gimple *stmt;
653 : 347 : 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 : 347 : 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 : 208 : }
687 : 1 : }
688 : :
689 : 224 : if (!is_gimple_condexpr_for_cond (cond))
690 : : {
691 : 101 : gimple_stmt_iterator gsi = gsi_for_stmt (outer_cond);
692 : 101 : 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 : 224 : gimple_cond_set_condition_from_tree (outer_cond, cond);
699 : 224 : update_stmt (outer_cond);
700 : :
701 : 224 : if (cond2)
702 : : {
703 : 115 : if (inner_inv)
704 : 115 : cond2 = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond2), cond2);
705 : :
706 : 115 : if (tree tcanon = canonicalize_cond_expr_cond (cond2))
707 : 43 : cond2 = tcanon;
708 : 115 : 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 : 115 : gimple_cond_set_condition_from_tree (inner_cond, cond2);
716 : : }
717 : : else
718 : 109 : gimple_cond_set_condition_from_tree (inner_cond,
719 : : inner_inv
720 : : ? boolean_false_node
721 : : : boolean_true_node);
722 : 224 : update_stmt (inner_cond);
723 : : }
724 : : else
725 : : {
726 : 100003 : if (!is_gimple_condexpr_for_cond (cond))
727 : : {
728 : 95591 : gimple_stmt_iterator gsi = gsi_for_stmt (inner_cond);
729 : 95591 : cond = force_gimple_operand_gsi_1 (&gsi, cond,
730 : : is_gimple_condexpr_for_cond,
731 : : NULL, true, GSI_SAME_STMT);
732 : : }
733 : 100003 : gimple_cond_set_condition_from_tree (inner_cond, cond);
734 : 100003 : update_stmt (inner_cond);
735 : :
736 : : /* Leave CFG optimization to cfg_cleanup. */
737 : 100003 : gimple_cond_set_condition_from_tree (outer_cond,
738 : : outer_inv
739 : : ? boolean_false_node
740 : : : boolean_true_node);
741 : 100003 : 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 : 200614 : for (basic_block bb = gimple_bb (inner_cond), end = gimple_bb (outer_cond);
747 : 200614 : 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 : 100387 : 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 : 100387 : if (strictening_outer_cond)
756 : 275 : continue;
757 : :
758 : : /* Avoid introducing undefined behavior as we move stmts that used to be
759 : : guarded by OUTER_COND. */
760 : 200224 : for (gimple_stmt_iterator gsi = gsi_start_bb (gimple_bb (inner_cond));
761 : 489228 : !gsi_end_p (gsi); gsi_next (&gsi))
762 : 389116 : ifcombine_rewrite_to_defined_overflow (gsi);
763 : : }
764 : :
765 : 100227 : update_profile_after_ifcombine (gimple_bb (inner_cond),
766 : : gimple_bb (outer_cond));
767 : :
768 : 100227 : 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 : 165130 : can_combine_bbs_with_short_circuit (basic_block inner_cond_bb, tree lhs, tree rhs)
776 : : {
777 : 165130 : gimple_stmt_iterator gsi;
778 : 165130 : gsi = gsi_start_nondebug_after_labels_bb (inner_cond_bb);
779 : : /* If only the condition, this should be allowed. */
780 : 165130 : if (gsi_one_before_end_p (gsi))
781 : : return true;
782 : : /* Can have up to 2 statements defining each of lhs/rhs. */
783 : 78184 : for (int i = 0; i < 2; i++)
784 : : {
785 : 78184 : gimple *stmt = gsi_stmt (gsi);
786 : 78184 : if (!is_gimple_assign (stmt)
787 : 78184 : || !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 : 10051 : if (lhs != gimple_assign_lhs (stmt)
792 : 10051 : && rhs != gimple_assign_lhs (stmt))
793 : : return false;
794 : 4943 : gsi_next_nondebug (&gsi);
795 : 97231 : 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 : 292756 : ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv,
808 : : basic_block outer_cond_bb, bool outer_inv)
809 : : {
810 : 292756 : gimple_stmt_iterator gsi;
811 : 292756 : tree name1, name2, bit1, bit2, bits1, bits2;
812 : :
813 : 585512 : gcond *inner_cond = safe_dyn_cast <gcond *> (*gsi_last_bb (inner_cond_bb));
814 : 292756 : if (!inner_cond)
815 : : return false;
816 : :
817 : 585512 : gcond *outer_cond = safe_dyn_cast <gcond *> (*gsi_last_bb (outer_cond_bb));
818 : 292756 : 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 : 292756 : if (recognize_single_bit_test (inner_cond, &name1, &bit1, inner_inv)
826 : 2663 : && recognize_single_bit_test (outer_cond, &name2, &bit2, outer_inv)
827 : 294019 : && name1 == name2)
828 : : {
829 : 958 : tree t, t2;
830 : :
831 : 958 : if (TREE_CODE (name1) == SSA_NAME
832 : 958 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name1))
833 : : return false;
834 : :
835 : : /* Do it. */
836 : 958 : gsi = gsi_for_stmt (inner_cond);
837 : 958 : t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
838 : : build_int_cst (TREE_TYPE (name1), 1), bit1);
839 : 958 : t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
840 : : build_int_cst (TREE_TYPE (name1), 1), bit2);
841 : 958 : t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
842 : 958 : t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
843 : : true, GSI_SAME_STMT);
844 : 958 : t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
845 : 958 : t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE,
846 : : true, GSI_SAME_STMT);
847 : :
848 : 958 : t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t);
849 : :
850 : 958 : if (!ifcombine_replace_cond (inner_cond, inner_inv,
851 : : outer_cond, outer_inv,
852 : : t, true, NULL_TREE))
853 : : return false;
854 : :
855 : 958 : if (dump_file)
856 : : {
857 : 1 : fprintf (dump_file, "optimizing double bit test to ");
858 : 1 : print_generic_expr (dump_file, name1);
859 : 1 : fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
860 : 1 : print_generic_expr (dump_file, bit1);
861 : 1 : fprintf (dump_file, ") | (1 << ");
862 : 1 : print_generic_expr (dump_file, bit2);
863 : 1 : fprintf (dump_file, ")\n");
864 : : }
865 : :
866 : 958 : return true;
867 : : }
868 : :
869 : : /* See if we have two bit tests of the same name in both tests.
870 : : In that case remove the outer test and change the inner one to
871 : : test for name & (bits1 | bits2) != 0. */
872 : 291798 : else if (recognize_bits_test (inner_cond, &name1, &bits1, !inner_inv)
873 : 291798 : && recognize_bits_test (outer_cond, &name2, &bits2, !outer_inv))
874 : : {
875 : 3071 : tree t;
876 : :
877 : 3071 : if ((TREE_CODE (name1) == SSA_NAME
878 : 3070 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name1))
879 : 6141 : || (TREE_CODE (name2) == SSA_NAME
880 : 3070 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name2)))
881 : : return false;
882 : :
883 : : /* Find the common name which is bit-tested. */
884 : 3071 : if (name1 == name2)
885 : : ;
886 : 880 : else if (bits1 == bits2)
887 : : {
888 : 87 : std::swap (name2, bits2);
889 : 87 : std::swap (name1, bits1);
890 : : }
891 : 793 : else if (name1 == bits2)
892 : 5 : std::swap (name2, bits2);
893 : 788 : else if (bits1 == name2)
894 : 0 : std::swap (name1, bits1);
895 : : else
896 : 788 : goto bits_test_failed;
897 : :
898 : : /* As we strip non-widening conversions in finding a common
899 : : name that is tested make sure to end up with an integral
900 : : type for building the bit operations. */
901 : 2283 : if (TYPE_PRECISION (TREE_TYPE (bits1))
902 : 2283 : >= TYPE_PRECISION (TREE_TYPE (bits2)))
903 : : {
904 : 2283 : bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
905 : 2283 : name1 = fold_convert (TREE_TYPE (bits1), name1);
906 : 2283 : bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
907 : 2283 : bits2 = fold_convert (TREE_TYPE (bits1), bits2);
908 : : }
909 : : else
910 : : {
911 : 0 : bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
912 : 0 : name1 = fold_convert (TREE_TYPE (bits2), name1);
913 : 0 : bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
914 : 0 : bits1 = fold_convert (TREE_TYPE (bits2), bits1);
915 : : }
916 : :
917 : 2283 : t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
918 : 2283 : t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
919 : 2283 : t = fold_build2 (EQ_EXPR, boolean_type_node, t,
920 : : build_int_cst (TREE_TYPE (t), 0));
921 : 2283 : if (!ifcombine_replace_cond (inner_cond, inner_inv,
922 : : outer_cond, outer_inv,
923 : : t, false, NULL_TREE))
924 : : return false;
925 : :
926 : 2283 : if (dump_file)
927 : : {
928 : 1 : fprintf (dump_file, "optimizing bits or bits test to ");
929 : 1 : print_generic_expr (dump_file, name1);
930 : 1 : fprintf (dump_file, " & T != 0\nwith temporary T = ");
931 : 1 : print_generic_expr (dump_file, bits1);
932 : 1 : fprintf (dump_file, " | ");
933 : 1 : print_generic_expr (dump_file, bits2);
934 : 1 : fprintf (dump_file, "\n");
935 : : }
936 : :
937 : 2283 : return true;
938 : : }
939 : :
940 : : /* See if we have two comparisons that we can merge into one. */
941 : 289515 : else bits_test_failed:
942 : 289515 : if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
943 : 289515 : && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
944 : : {
945 : 289515 : tree t, ts = NULL_TREE;
946 : 289515 : enum tree_code inner_cond_code = gimple_cond_code (inner_cond);
947 : 289515 : enum tree_code outer_cond_code = gimple_cond_code (outer_cond);
948 : :
949 : : /* Invert comparisons if necessary (and possible). */
950 : 289515 : if (inner_inv)
951 : 213533 : inner_cond_code = invert_tree_comparison (inner_cond_code,
952 : 213533 : HONOR_NANS (gimple_cond_lhs (inner_cond)));
953 : 289515 : if (inner_cond_code == ERROR_MARK)
954 : : return false;
955 : 287057 : if (outer_inv)
956 : 204427 : outer_cond_code = invert_tree_comparison (outer_cond_code,
957 : 204427 : HONOR_NANS (gimple_cond_lhs (outer_cond)));
958 : 287057 : if (outer_cond_code == ERROR_MARK)
959 : : return false;
960 : : /* Don't return false so fast, try maybe_fold_or_comparisons? */
961 : :
962 : 286778 : if (!(t = maybe_fold_and_comparisons (boolean_type_node, inner_cond_code,
963 : : gimple_cond_lhs (inner_cond),
964 : : gimple_cond_rhs (inner_cond),
965 : : outer_cond_code,
966 : : gimple_cond_lhs (outer_cond),
967 : : gimple_cond_rhs (outer_cond),
968 : : gimple_bb (outer_cond)))
969 : 286778 : && !(t = (fold_truth_andor_for_ifcombine
970 : 284603 : (TRUTH_ANDIF_EXPR, boolean_type_node,
971 : : gimple_location (outer_cond),
972 : : outer_cond_code,
973 : : gimple_cond_lhs (outer_cond),
974 : : gimple_cond_rhs (outer_cond),
975 : : gimple_location (inner_cond),
976 : : inner_cond_code,
977 : : gimple_cond_lhs (inner_cond),
978 : : gimple_cond_rhs (inner_cond),
979 : 284603 : single_pred (inner_cond_bb) != outer_cond_bb
980 : : ? &ts : 0))))
981 : : {
982 : : /* Only combine conditions in this fallback case if the blocks are
983 : : neighbors. */
984 : 281680 : if (single_pred (inner_cond_bb) != outer_cond_bb)
985 : : return false;
986 : 165261 : tree t1, t2;
987 : 165261 : bool logical_op_non_short_circuit = LOGICAL_OP_NON_SHORT_CIRCUIT;
988 : 165261 : if (param_logical_op_non_short_circuit != -1)
989 : 167 : logical_op_non_short_circuit
990 : 167 : = param_logical_op_non_short_circuit;
991 : 165261 : if (!logical_op_non_short_circuit || sanitize_coverage_p ())
992 : 131 : return false;
993 : : /* Only do this optimization if the inner bb contains only the conditional
994 : : or there is one or 2 statements which are nop conversion for the comparison. */
995 : 165130 : if (!can_combine_bbs_with_short_circuit (inner_cond_bb,
996 : : gimple_cond_lhs (inner_cond),
997 : : gimple_cond_rhs (inner_cond)))
998 : : return false;
999 : 91889 : t1 = fold_build2_loc (gimple_location (inner_cond),
1000 : : inner_cond_code,
1001 : : boolean_type_node,
1002 : : gimple_cond_lhs (inner_cond),
1003 : : gimple_cond_rhs (inner_cond));
1004 : 91889 : t2 = fold_build2_loc (gimple_location (outer_cond),
1005 : : outer_cond_code,
1006 : : boolean_type_node,
1007 : : gimple_cond_lhs (outer_cond),
1008 : : gimple_cond_rhs (outer_cond));
1009 : 91889 : t = fold_build2_loc (gimple_location (inner_cond),
1010 : : TRUTH_AND_EXPR, boolean_type_node, t1, t2);
1011 : : }
1012 : :
1013 : 96987 : if (!ifcombine_replace_cond (inner_cond, inner_inv,
1014 : : outer_cond, outer_inv,
1015 : : t, false, ts))
1016 : : return false;
1017 : :
1018 : 96986 : if (dump_file)
1019 : : {
1020 : 30 : fprintf (dump_file, "optimizing two comparisons to ");
1021 : 30 : print_generic_expr (dump_file, t);
1022 : 30 : if (ts)
1023 : : {
1024 : 0 : fprintf (dump_file, " and ");
1025 : 0 : print_generic_expr (dump_file, ts);
1026 : : }
1027 : 30 : fprintf (dump_file, "\n");
1028 : : }
1029 : :
1030 : 96986 : return true;
1031 : : }
1032 : :
1033 : : return false;
1034 : : }
1035 : :
1036 : : /* Helper function for tree_ssa_ifcombine_bb. Recognize a CFG pattern and
1037 : : dispatch to the appropriate if-conversion helper for a particular
1038 : : set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB.
1039 : : PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB.
1040 : : OUTER_SUCC_BB is the successor of OUTER_COND_BB on the path towards
1041 : : INNER_COND_BB. */
1042 : :
1043 : : static bool
1044 : 1068959 : tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb,
1045 : : basic_block then_bb, basic_block else_bb,
1046 : : basic_block phi_pred_bb, basic_block outer_succ_bb)
1047 : : {
1048 : : /* The && form is characterized by a common else_bb with
1049 : : the two edges leading to it mergable. The latter is
1050 : : guaranteed by matching PHI arguments in the else_bb and
1051 : : the inner cond_bb having no side-effects. */
1052 : 1068959 : if (phi_pred_bb != else_bb
1053 : 1047908 : && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &else_bb)
1054 : 1150967 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
1055 : : {
1056 : : /* We have
1057 : : <outer_cond_bb>
1058 : : if (q) goto inner_cond_bb; else goto else_bb;
1059 : : <inner_cond_bb>
1060 : : if (p) goto ...; else goto else_bb;
1061 : : ...
1062 : : <else_bb>
1063 : : ...
1064 : : */
1065 : 73089 : return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, false);
1066 : : }
1067 : :
1068 : : /* And a version where the outer condition is negated. */
1069 : 995870 : if (phi_pred_bb != else_bb
1070 : 974819 : && recognize_if_then_else (outer_cond_bb, &else_bb, &outer_succ_bb)
1071 : 1007825 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
1072 : : {
1073 : : /* We have
1074 : : <outer_cond_bb>
1075 : : if (q) goto else_bb; else goto inner_cond_bb;
1076 : : <inner_cond_bb>
1077 : : if (p) goto ...; else goto else_bb;
1078 : : ...
1079 : : <else_bb>
1080 : : ...
1081 : : */
1082 : 4278 : return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, true);
1083 : : }
1084 : :
1085 : : /* The || form is characterized by a common then_bb with the
1086 : : two edges leading to it mergeable. The latter is guaranteed
1087 : : by matching PHI arguments in the then_bb and the inner cond_bb
1088 : : having no side-effects. */
1089 : 991592 : if (phi_pred_bb != then_bb
1090 : 977695 : && recognize_if_then_else (outer_cond_bb, &then_bb, &outer_succ_bb)
1091 : 1229707 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
1092 : : {
1093 : : /* We have
1094 : : <outer_cond_bb>
1095 : : if (q) goto then_bb; else goto inner_cond_bb;
1096 : : <inner_cond_bb>
1097 : : if (p) goto then_bb; else goto ...;
1098 : : <then_bb>
1099 : : ...
1100 : : */
1101 : 202029 : return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, true);
1102 : : }
1103 : :
1104 : : /* And a version where the outer condition is negated. */
1105 : 789563 : if (phi_pred_bb != then_bb
1106 : 775666 : && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &then_bb)
1107 : 808186 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
1108 : : {
1109 : : /* We have
1110 : : <outer_cond_bb>
1111 : : if (q) goto inner_cond_bb; else goto then_bb;
1112 : : <inner_cond_bb>
1113 : : if (p) goto then_bb; else goto ...;
1114 : : <then_bb>
1115 : : ...
1116 : : */
1117 : 13360 : return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false);
1118 : : }
1119 : :
1120 : : return false;
1121 : : }
1122 : :
1123 : : /* Recognize a CFG pattern and dispatch to the appropriate
1124 : : if-conversion helper. We start with BB as the innermost
1125 : : worker basic-block. Returns true if a transformation was done. */
1126 : :
1127 : : static bool
1128 : 4315209 : tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
1129 : : {
1130 : 4315209 : bool ret = false;
1131 : 4315209 : basic_block then_bb = NULL, else_bb = NULL;
1132 : :
1133 : 4315209 : if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
1134 : : return ret;
1135 : :
1136 : : /* Recognize && and || of two conditions with a common
1137 : : then/else block which entry edges we can merge. That is:
1138 : : if (a || b)
1139 : : ;
1140 : : and
1141 : : if (a && b)
1142 : : ;
1143 : : This requires a single predecessor of the inner cond_bb.
1144 : :
1145 : : Look for an OUTER_COND_BBs to combine with INNER_COND_BB. They need not
1146 : : be contiguous, as long as inner and intervening blocks have no side
1147 : : effects, and are either single-entry-single-exit or conditionals choosing
1148 : : between the same EXIT_BB with the same PHI args, possibly through an
1149 : : EXIT_PRED, and the path leading to INNER_COND_BB. EXIT_PRED will be set
1150 : : just before (along with a successful combination) or just after setting
1151 : : EXIT_BB, to either THEN_BB, ELSE_BB, or INNER_COND_BB. ??? We could
1152 : : potentially handle multi-block single-entry-single-exit regions, but the
1153 : : loop below only deals with single-entry-single-exit individual intervening
1154 : : blocks. Larger regions without side effects are presumably rare, so it's
1155 : : probably not worth the effort. */
1156 : 4897833 : for (basic_block bb = inner_cond_bb, outer_cond_bb, exit_bb = NULL,
1157 : : /* This initialization shouldn't be needed, but in case the compiler
1158 : : is not smart enough to tell, make it harmless. */
1159 : 4315149 : exit_pred = NULL;
1160 : 4897833 : single_pred_p (bb) && bb_no_side_effects_p (bb);
1161 : 582684 : bb = outer_cond_bb)
1162 : : {
1163 : 1516225 : bool changed = false;
1164 : :
1165 : 1516225 : outer_cond_bb = single_pred (bb);
1166 : :
1167 : : /* Skip blocks without conditions. */
1168 : 1516225 : if (single_succ_p (outer_cond_bb))
1169 : 114978 : continue;
1170 : :
1171 : : /* When considering noncontiguous conditions, make sure that all
1172 : : non-final conditions lead to the same successor of the final
1173 : : condition, when not taking the path to inner_bb, so that we can
1174 : : combine C into A, both in A && (B && C), and in A || (B || C), but
1175 : : neither in A && (B || C), nor A || (B && C). Say, if C goes to
1176 : : THEN_BB or ELSE_BB, then B must go to either of these, say X, besides
1177 : : C (whether C is then or else), and A must go to X and B (whether then
1178 : : or else).
1179 : :
1180 : : We test for this, while allowing intervening nonconditional blocks, by
1181 : : first taking note of which of the successors of the inner conditional
1182 : : block is the exit path taken by the first considered outer conditional
1183 : : block.
1184 : :
1185 : : Having identified and saved the exit block in EXIT_BB at the end of
1186 : : the loop, here we test that subsequent conditional blocks under
1187 : : consideration also use the exit block as a successor, besides the
1188 : : block that leads to inner_cond_bb, and that the edges to exit share
1189 : : the same phi values. */
1190 : 1401247 : if (exit_bb
1191 : 1401247 : && !recognize_if_then_else (outer_cond_bb, &bb, &exit_bb, true))
1192 : : break;
1193 : :
1194 : : /* After checking dests and phi args, we can also skip blocks whose
1195 : : conditions have been optimized down to a constant, without trying to
1196 : : combine them, but we must not skip the computation of EXIT_BB and the
1197 : : checking of same phi args. */
1198 : 1379879 : if (known_succ_p (outer_cond_bb))
1199 : : changed = false;
1200 : 125283 : else if ((!exit_bb || exit_pred == inner_cond_bb)
1201 : 1159087 : && tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb,
1202 : : then_bb, else_bb, inner_cond_bb, bb))
1203 : : changed = true, exit_pred = inner_cond_bb;
1204 : 933897 : else if (exit_bb
1205 : 933897 : ? exit_pred == else_bb
1206 : 808729 : : forwarder_block_to (else_bb, then_bb))
1207 : : {
1208 : : /* Other possibilities for the && form, if else_bb is
1209 : : empty forwarder block to then_bb. Compared to the above simpler
1210 : : forms this can be treated as if then_bb and else_bb were swapped,
1211 : : and the corresponding inner_cond_bb not inverted because of that.
1212 : : For same_phi_args_p we look at equality of arguments between
1213 : : edge from outer_cond_bb and the forwarder block. */
1214 : 14104 : if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
1215 : : then_bb, else_bb, bb))
1216 : : changed = true, exit_pred = else_bb;
1217 : : }
1218 : 919793 : else if (exit_bb
1219 : 919793 : ? exit_pred == then_bb
1220 : 794661 : : forwarder_block_to (then_bb, else_bb))
1221 : : {
1222 : : /* Other possibilities for the || form, if then_bb is
1223 : : empty forwarder block to else_bb. Compared to the above simpler
1224 : : forms this can be treated as if then_bb and else_bb were swapped,
1225 : : and the corresponding inner_cond_bb not inverted because of that.
1226 : : For same_phi_args_p we look at equality of arguments between
1227 : : edge from outer_cond_bb and the forwarder block. */
1228 : 21051 : if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
1229 : : then_bb, then_bb, bb))
1230 : : changed = true, exit_pred = then_bb;
1231 : : }
1232 : :
1233 : : if (changed)
1234 : 100227 : ret = changed;
1235 : :
1236 : : /* If the inner condition is gone, there's no point in attempting to
1237 : : combine it any further. */
1238 : 100227 : if (changed && known_succ_p (inner_cond_bb))
1239 : : break;
1240 : :
1241 : : /* Starting at this point in the loop, we start preparing to attempt
1242 : : combinations in which OUTER_COND_BB will be an intervening block.
1243 : : Checking that it has a single predecessor is a very cheap test, unlike
1244 : : the PHI args tests below, so test it early and hopefully save the more
1245 : : expensive tests in case we won't be able to try other blocks. */
1246 : 1379768 : if (!single_pred_p (outer_cond_bb))
1247 : : break;
1248 : :
1249 : : /* Record the exit path taken by the outer condition. */
1250 : 1032826 : if (!exit_bb)
1251 : : {
1252 : : /* If we have removed the outer condition entirely, we need not
1253 : : commit to an exit block yet, it's as if we'd merged the blocks and
1254 : : were starting afresh. This is sound as long as we never replace
1255 : : the outer condition with a constant that leads away from the inner
1256 : : block. Here's why we never do: when combining contiguous
1257 : : conditions, we replace the inner cond, and replace the outer cond
1258 : : with a constant that leads to inner, so this case is good. When
1259 : : combining noncontiguous blocks, we normally modify outer, and
1260 : : replace inner with a constant or remainders of the original
1261 : : condition that couldn't be combined. This test would normally not
1262 : : hit with noncontiguous blocks, because we'd have computed EXIT_BB
1263 : : before reaching the noncontiguous outer block. However, if all
1264 : : intervening blocks are unconditional, including those just made
1265 : : unconditional, we may replace outer instead of inner with the
1266 : : combined condition. If the combined noncontiguous conditions are
1267 : : mutually exclusive, we could end up with a constant outer
1268 : : condition, but then, the inner condition would also be a constant,
1269 : : and then we'd stop iterating because of the known_succ_p
1270 : : (inner_cond_bb) test above. */
1271 : 712298 : if (changed && known_succ_p (outer_cond_bb))
1272 : 77043 : continue;
1273 : :
1274 : 635255 : if (recognize_if_then_else (outer_cond_bb, &then_bb, &bb, true))
1275 : 81251 : exit_bb = then_bb;
1276 : 554004 : else if (recognize_if_then_else (outer_cond_bb, &bb, &else_bb, true))
1277 : 32846 : exit_bb = else_bb;
1278 : : else
1279 : : break;
1280 : :
1281 : : /* Find out which path from INNER_COND_BB shares PHI args with the
1282 : : edge (OUTER_COND_BB->EXIT_BB). That path may involve a forwarder
1283 : : block, whether THEN_BB or ELSE_BB, and we need to know which one
1284 : : satisfies the condition to avoid combinations that could use
1285 : : different forwarding arrangements, because they would be unsound.
1286 : : E.g., given (a ? 0 : b ? 1 : c ? 1 : 0), after trying to merge b
1287 : : and c, we test that both share the same exit block, with the same
1288 : : value 1. Whether or not that involves a forwarder block, if we
1289 : : don't go through the same (possibly absent) forwarder block in
1290 : : subsequent attempted combinations, e.g. a with c, we could find
1291 : : that a and inverted c share the same exit block with a different
1292 : : value, namely 0, which would enable an unsound merge. We need all
1293 : : of inner, intervening and outer blocks to reach the same exit with
1294 : : the same value for the transformation to be sound. So here we
1295 : : determine how to get to EXIT_BB from outer and inner with the same
1296 : : PHI values, record that in EXIT_PRED, and then subsequent
1297 : : combination attempts that have OUTER_COND_BB as an intervening
1298 : : block will ensure the same path to exit is taken, skipping unsound
1299 : : transformations. */
1300 : 114097 : if (changed)
1301 : : /* EXIT_PRED was set along with CHANGED, and the successful
1302 : : combination already checked for the same PHI args. */;
1303 : 113991 : else if (same_phi_args_p (outer_cond_bb, inner_cond_bb, exit_bb))
1304 : : exit_pred = inner_cond_bb;
1305 : 31278 : else if (then_bb == exit_bb
1306 : 23337 : && forwarder_block_to (else_bb, then_bb)
1307 : 33695 : && same_phi_args_p (outer_cond_bb, else_bb, exit_bb))
1308 : : exit_pred = else_bb;
1309 : 31215 : else if (else_bb == exit_bb
1310 : 7941 : && forwarder_block_to (then_bb, else_bb)
1311 : 32307 : && same_phi_args_p (outer_cond_bb, then_bb, exit_bb))
1312 : : exit_pred = then_bb;
1313 : : else
1314 : : /* If none of the paths share the same PHI args, no combination is
1315 : : viable. */
1316 : : break;
1317 : : /* Skip the PHI args test below, it's redundant with the tests we've
1318 : : just performed. */
1319 : 83056 : continue;
1320 : : }
1321 : :
1322 : : /* Before trying an earlier block, make sure INNER_COND_BB and the
1323 : : current OUTER_COND_BB share the same PHI args at EXIT_BB. We don't
1324 : : need to check if the latest attempt at combining succeeded, because
1325 : : that means we'll have already checked. But we can't only check outer
1326 : : and inner, we have to check that all intervening blocks also get to
1327 : : exit with the same result, otherwise the transformation may change the
1328 : : final result. Consider (a ? 0 : b ? 1 : c ? 0 : -1). If we combine
1329 : : (a | c), yielding ((a | c) ? 0 : b ? 1 : [0 ? 0 :] -1), we'd get 0
1330 : : rather than 1 when (!a&&b). And if we were to replace inner instead
1331 : : of outer, we'd get ([1 ? 0 :] b ? 1 : (a | c) ? 0 : -1), which would
1332 : : yield 1 rather than 0 when (a). */
1333 : 320528 : if (!changed
1334 : 320528 : && !same_phi_args_p (outer_cond_bb, exit_pred, exit_bb))
1335 : : break;
1336 : : }
1337 : :
1338 : 4315149 : return ret;
1339 : : }
1340 : :
1341 : : /* Main entry for the tree if-conversion pass. */
1342 : :
1343 : : namespace {
1344 : :
1345 : : const pass_data pass_data_tree_ifcombine =
1346 : : {
1347 : : GIMPLE_PASS, /* type */
1348 : : "ifcombine", /* name */
1349 : : OPTGROUP_NONE, /* optinfo_flags */
1350 : : TV_TREE_IFCOMBINE, /* tv_id */
1351 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
1352 : : 0, /* properties_provided */
1353 : : 0, /* properties_destroyed */
1354 : : 0, /* todo_flags_start */
1355 : : TODO_update_ssa, /* todo_flags_finish */
1356 : : };
1357 : :
1358 : : class pass_tree_ifcombine : public gimple_opt_pass
1359 : : {
1360 : : public:
1361 : 285081 : pass_tree_ifcombine (gcc::context *ctxt)
1362 : 570162 : : gimple_opt_pass (pass_data_tree_ifcombine, ctxt)
1363 : : {}
1364 : :
1365 : : /* opt_pass methods: */
1366 : : unsigned int execute (function *) final override;
1367 : :
1368 : : }; // class pass_tree_ifcombine
1369 : :
1370 : : unsigned int
1371 : 1021523 : pass_tree_ifcombine::execute (function *fun)
1372 : : {
1373 : 1021523 : basic_block *bbs;
1374 : 1021523 : bool cfg_changed = false;
1375 : 1021523 : int i;
1376 : :
1377 : 1021523 : bbs = single_pred_before_succ_order ();
1378 : 1021523 : calculate_dominance_info (CDI_DOMINATORS);
1379 : 1021523 : mark_ssa_maybe_undefs ();
1380 : :
1381 : : /* Search every basic block for COND_EXPR we may be able to optimize.
1382 : :
1383 : : We walk the blocks in order that guarantees that a block with
1384 : : a single predecessor is processed after the predecessor.
1385 : : This ensures that we collapse outter ifs before visiting the
1386 : : inner ones, and also that we do not try to visit a removed
1387 : : block. This is opposite of PHI-OPT, because we cascade the
1388 : : combining rather than cascading PHIs. */
1389 : 11413996 : for (i = n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS - 1; i >= 0; i--)
1390 : : {
1391 : 10392473 : basic_block bb = bbs[i];
1392 : :
1393 : 24999930 : if (safe_is_a <gcond *> (*gsi_last_bb (bb)))
1394 : 4315209 : if (tree_ssa_ifcombine_bb (bb))
1395 : 10392473 : cfg_changed |= true;
1396 : : }
1397 : :
1398 : 1021523 : free (bbs);
1399 : :
1400 : 1021523 : return cfg_changed ? TODO_cleanup_cfg : 0;
1401 : : }
1402 : :
1403 : : } // anon namespace
1404 : :
1405 : : gimple_opt_pass *
1406 : 285081 : make_pass_tree_ifcombine (gcc::context *ctxt)
1407 : : {
1408 : 285081 : return new pass_tree_ifcombine (ctxt);
1409 : : }
|
