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 : 8843871 : known_succ_p (basic_block cond_bb)
58 : : {
59 : 17687742 : gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (cond_bb));
60 : :
61 : 8843871 : if (!cond)
62 : 118927 : return true;
63 : :
64 : 8724944 : return (CONSTANT_CLASS_P (gimple_cond_lhs (cond))
65 : 8724944 : && 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 : 8764540 : recognize_if_then_else (basic_block cond_bb,
99 : : basic_block *then_bb, basic_block *else_bb,
100 : : bool succs_any = false)
101 : : {
102 : 8764540 : edge t, e;
103 : :
104 : 8764540 : if (EDGE_COUNT (cond_bb->succs) != 2
105 : 8764540 : || (!succs_any && known_succ_p (cond_bb)))
106 : : return false;
107 : :
108 : : /* Find the then/else edges. */
109 : 8742918 : t = EDGE_SUCC (cond_bb, 0);
110 : 8742918 : e = EDGE_SUCC (cond_bb, 1);
111 : :
112 : 8742918 : if (succs_any)
113 : 318542 : return ((t->dest == *then_bb && e->dest == *else_bb)
114 : 2041353 : || (t->dest == *else_bb && e->dest == *then_bb));
115 : :
116 : 7340739 : if (!(t->flags & EDGE_TRUE_VALUE))
117 : 247265 : std::swap (t, e);
118 : 7340739 : if (!(t->flags & EDGE_TRUE_VALUE)
119 : 7340739 : || !(e->flags & EDGE_FALSE_VALUE))
120 : : return false;
121 : :
122 : : /* Check if the edge destinations point to the required block. */
123 : 7340739 : if (*then_bb
124 : 3359954 : && t->dest != *then_bb)
125 : : return false;
126 : 4901882 : if (*else_bb
127 : 921097 : && e->dest != *else_bb)
128 : : return false;
129 : :
130 : 4311155 : if (!*then_bb)
131 : 3980785 : *then_bb = t->dest;
132 : 4311155 : if (!*else_bb)
133 : 3980785 : *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 : 3186963 : bb_no_side_effects_p (basic_block bb)
143 : : {
144 : 3186963 : gimple_stmt_iterator gsi;
145 : :
146 : 15986179 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
147 : : {
148 : 11400425 : gimple *stmt = gsi_stmt (gsi);
149 : :
150 : 11400425 : if (is_gimple_debug (stmt))
151 : 5957574 : continue;
152 : :
153 : 5442851 : gassign *ass;
154 : 5442851 : enum tree_code rhs_code;
155 : 5442851 : if (gimple_has_side_effects (stmt)
156 : 4886027 : || gimple_could_trap_p (stmt)
157 : 4152249 : || 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 : 6137350 : || ((ass = dyn_cast <gassign *> (stmt))
161 : 2204423 : && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (ass)))
162 : 3428696 : && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (ass)))
163 : 417106 : && ((rhs_code = gimple_assign_rhs_code (ass)), true)
164 : 417106 : && (rhs_code == TRUNC_DIV_EXPR
165 : : || rhs_code == CEIL_DIV_EXPR
166 : : || rhs_code == FLOOR_DIV_EXPR
167 : 417106 : || 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 : 1153 : && (TREE_CODE (gimple_assign_rhs2 (ass)) != INTEGER_CST
171 : 1153 : || !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 : 11090126 : || is_gimple_call (stmt))
179 : 1788172 : return false;
180 : :
181 : 3658055 : ssa_op_iter it;
182 : 3658055 : tree use;
183 : 7279833 : FOR_EACH_SSA_TREE_OPERAND (use, stmt, it, SSA_OP_USE)
184 : 3625154 : 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 : 1443872 : forwarder_block_to (basic_block bb, basic_block to_bb)
195 : : {
196 : 1443872 : return empty_block_p (bb)
197 : 50126 : && single_succ_p (bb)
198 : 1493998 : && 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 : 766057 : same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
207 : : {
208 : 766057 : edge e1 = find_edge (bb1, dest);
209 : 766057 : edge e2 = find_edge (bb2, dest);
210 : 766057 : gphi_iterator gsi;
211 : 766057 : gphi *phi;
212 : :
213 : 1118206 : for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
214 : : {
215 : 454863 : phi = gsi.phi ();
216 : 454863 : if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
217 : 454863 : 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 : 8621 : 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 : 8621 : if (TREE_CODE (candidate) == SSA_NAME
233 : 8621 : && has_single_use (candidate))
234 : : {
235 : 4019 : gimple *def_stmt = SSA_NAME_DEF_STMT (candidate);
236 : 4019 : if (is_gimple_assign (def_stmt)
237 : 4019 : && 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 : 277157 : recognize_single_bit_test (gcond *cond, tree *name, tree *bit, bool inv)
255 : : {
256 : 277157 : gimple *stmt;
257 : :
258 : : /* Get at the definition of the result of the bit test. */
259 : 277157 : if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
260 : 42360 : || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
261 : 318683 : || !integer_zerop (gimple_cond_rhs (cond)))
262 : 252980 : return false;
263 : 24177 : stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
264 : 24177 : 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 : 20266 : if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
273 : 6293 : && integer_onep (gimple_assign_rhs2 (stmt))
274 : 20854 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
275 : : {
276 : 588 : 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 : 588 : stmt = SSA_NAME_DEF_STMT (orig_name);
281 : :
282 : 589 : while (is_gimple_assign (stmt)
283 : 589 : && ((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 : 507 : || 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 : 588 : if (is_gimple_assign (stmt)
292 : 588 : && gimple_assign_rhs_code (stmt) == RSHIFT_EXPR)
293 : : {
294 : : /* op0 & (1 << op1) */
295 : 77 : *bit = gimple_assign_rhs2 (stmt);
296 : 77 : *name = gimple_assign_rhs1 (stmt);
297 : : }
298 : : else
299 : : {
300 : : /* t & 1 */
301 : 511 : *bit = integer_zero_node;
302 : 511 : *name = get_name_for_bit_test (orig_name);
303 : : }
304 : :
305 : 588 : return true;
306 : : }
307 : :
308 : : /* Another form is
309 : : D.1987_7 = op0 & (1 << CST)
310 : : if (D.1987_7 != 0) */
311 : 19678 : if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
312 : 5705 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
313 : 25383 : && integer_pow2p (gimple_assign_rhs2 (stmt)))
314 : : {
315 : 3288 : *name = gimple_assign_rhs1 (stmt);
316 : 3288 : *bit = build_int_cst (integer_type_node,
317 : 3288 : tree_log2 (gimple_assign_rhs2 (stmt)));
318 : 3288 : 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 : 16390 : if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
326 : 2417 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
327 : 18807 : && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
328 : : {
329 : 2061 : gimple *tmp;
330 : :
331 : : /* Both arguments of the BIT_AND_EXPR can be the single-bit
332 : : specifying expression. */
333 : 2061 : tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
334 : 2061 : if (is_gimple_assign (tmp)
335 : 2025 : && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
336 : 2071 : && 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 : 2051 : tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
344 : 2051 : if (is_gimple_assign (tmp)
345 : 1922 : && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
346 : 2081 : && 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 : 279268 : recognize_bits_test (gcond *cond, tree *name, tree *bits, bool inv)
364 : : {
365 : 279268 : gimple *stmt;
366 : :
367 : : /* Get at the definition of the result of the bit test. */
368 : 279268 : if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
369 : 186093 : || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
370 : 464674 : || !integer_zerop (gimple_cond_rhs (cond)))
371 : 216138 : return false;
372 : 63130 : stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
373 : 63130 : if (!is_gimple_assign (stmt)
374 : 63130 : || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
375 : : return false;
376 : :
377 : 8110 : *name = get_name_for_bit_test (gimple_assign_rhs1 (stmt));
378 : 8110 : *bits = gimple_assign_rhs2 (stmt);
379 : :
380 : 8110 : 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 : 85284 : 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 : 85284 : gcc_assert (single_pred_p (inner_cond_bb));
393 : :
394 : 85284 : basic_block outer_to_inner_bb = inner_cond_bb;
395 : 85284 : profile_probability prob = profile_probability::always ();
396 : 85444 : for (;;)
397 : : {
398 : 85444 : basic_block parent = single_pred (outer_to_inner_bb);
399 : 85444 : prob *= find_edge (parent, outer_to_inner_bb)->probability;
400 : 85444 : if (parent == outer_cond_bb)
401 : : break;
402 : : outer_to_inner_bb = parent;
403 : : }
404 : :
405 : 85284 : edge outer_to_inner = find_edge (outer_cond_bb, outer_to_inner_bb);
406 : 85284 : edge outer2 = (EDGE_SUCC (outer_cond_bb, 0) == outer_to_inner
407 : 85284 : ? EDGE_SUCC (outer_cond_bb, 1)
408 : 85284 : : EDGE_SUCC (outer_cond_bb, 0));
409 : 85284 : edge inner_taken = EDGE_SUCC (inner_cond_bb, 0);
410 : 85284 : edge inner_not_taken = EDGE_SUCC (inner_cond_bb, 1);
411 : :
412 : 85284 : if (inner_taken->dest != outer2->dest)
413 : 30611 : std::swap (inner_taken, inner_not_taken);
414 : 85284 : gcc_assert (inner_taken->dest == outer2->dest);
415 : :
416 : 85284 : if (outer_to_inner_bb == inner_cond_bb
417 : 85284 : && 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 : 85060 : 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 : 85060 : if (inner_taken->probability == profile_probability::always ())
431 : : ;
432 : : else
433 : 83529 : inner_taken->probability = outer2->probability
434 : 83529 : + outer_to_inner->probability * inner_taken->probability;
435 : 85060 : inner_not_taken->probability = profile_probability::always ()
436 : 85060 : - inner_taken->probability;
437 : :
438 : 85060 : outer_to_inner->probability = profile_probability::always ();
439 : 85060 : 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 : 85284 : }
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 : 337594 : ifcombine_rewrite_to_defined_overflow (gimple_stmt_iterator gsi)
516 : : {
517 : 337594 : gassign *ass = dyn_cast <gassign *> (gsi_stmt (gsi));
518 : 214952 : if (!ass)
519 : : return;
520 : 214952 : tree lhs = gimple_assign_lhs (ass);
521 : 429351 : if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
522 : 8 : || POINTER_TYPE_P (TREE_TYPE (lhs)))
523 : 429904 : && arith_code_with_undefined_signed_overflow
524 : 214952 : (gimple_assign_rhs_code (ass)))
525 : 6982 : rewrite_to_defined_overflow (&gsi);
526 : : }
527 : :
528 : :
529 : : /* Replace the conditions in INNER_COND and OUTER_COND with COND and COND2.
530 : : COND and COND2 are computed for insertion at INNER_COND, with OUTER_COND
531 : : replaced with a constant, but if there are intervening blocks, it's best to
532 : : adjust COND for insertion at OUTER_COND, placing COND2 at INNER_COND. */
533 : :
534 : : static bool
535 : 85285 : ifcombine_replace_cond (gcond *inner_cond, bool inner_inv,
536 : : gcond *outer_cond, bool outer_inv,
537 : : tree cond, bool must_canon, tree cond2)
538 : : {
539 : 85285 : bool split_single_cond = false;
540 : : /* Split cond into cond2 if they're contiguous. ??? We might be able to
541 : : handle ORIF as well, inverting both conditions, but it's not clear that
542 : : this would be enough, and it never comes up. */
543 : 85285 : if (!cond2
544 : 85279 : && TREE_CODE (cond) == TRUTH_ANDIF_EXPR
545 : 85415 : && single_pred (gimple_bb (inner_cond)) == gimple_bb (outer_cond))
546 : : {
547 : 109 : cond2 = TREE_OPERAND (cond, 1);
548 : 109 : cond = TREE_OPERAND (cond, 0);
549 : 109 : split_single_cond = true;
550 : : }
551 : :
552 : 85285 : bool outer_p = cond2 || (single_pred (gimple_bb (inner_cond))
553 : 85170 : != gimple_bb (outer_cond));
554 : 85285 : bool result_inv = outer_p ? outer_inv : inner_inv;
555 : 85285 : bool strictening_outer_cond = !split_single_cond && outer_p;
556 : :
557 : 85285 : if (result_inv)
558 : 53627 : cond = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
559 : :
560 : 85285 : if (tree tcanon = canonicalize_cond_expr_cond (cond))
561 : 4424 : cond = tcanon;
562 : 80861 : else if (must_canon)
563 : : return false;
564 : :
565 : 85285 : if (outer_p)
566 : : {
567 : 225 : {
568 : 225 : auto_bitmap used;
569 : 225 : basic_block outer_bb = gimple_bb (outer_cond);
570 : :
571 : 225 : bitmap_tree_view (used);
572 : :
573 : : /* Mark SSA DEFs that are referenced by cond and may thus need to be
574 : : moved to outer. */
575 : 225 : {
576 : 225 : ifcombine_mark_ssa_name_t data = { used, outer_bb };
577 : 225 : walk_tree (&cond, ifcombine_mark_ssa_name_walk, &data, NULL);
578 : : }
579 : :
580 : 225 : if (!bitmap_empty_p (used))
581 : : {
582 : 208 : const int max_stmts = 6;
583 : 208 : auto_vec<gimple *, max_stmts> stmts;
584 : :
585 : : /* Iterate up from inner_cond, moving DEFs identified as used by
586 : : cond, and marking USEs in the DEFs for moving as well. */
587 : 555 : for (basic_block bb = gimple_bb (inner_cond);
588 : 555 : bb != outer_bb; bb = single_pred (bb))
589 : : {
590 : 348 : for (gimple_stmt_iterator gsitr = gsi_last_bb (bb);
591 : 4110 : !gsi_end_p (gsitr); gsi_prev (&gsitr))
592 : : {
593 : 1881 : gimple *stmt = gsi_stmt (gsitr);
594 : 1881 : bool move = false;
595 : 1881 : tree t;
596 : 1881 : ssa_op_iter it;
597 : :
598 : 2864 : FOR_EACH_SSA_TREE_OPERAND (t, stmt, it, SSA_OP_DEF)
599 : 1125 : if (bitmap_bit_p (used, SSA_NAME_VERSION (t)))
600 : : {
601 : : move = true;
602 : : break;
603 : : }
604 : :
605 : 1881 : if (!move)
606 : 1739 : continue;
607 : :
608 : 142 : if (stmts.length () < max_stmts)
609 : 142 : stmts.quick_push (stmt);
610 : : else
611 : 0 : return false;
612 : :
613 : : /* Mark uses in STMT before moving it. */
614 : 162 : FOR_EACH_SSA_TREE_OPERAND (t, stmt, it, SSA_OP_USE)
615 : 20 : ifcombine_mark_ssa_name (used, t, outer_bb);
616 : : }
617 : :
618 : : /* Surprisingly, there may be PHI nodes in single-predecessor
619 : : bocks, as in pr50682.C. Fortunately, since they can't
620 : : involve back edges, there won't be references to parallel
621 : : nodes that we'd have to pay special attention to to keep
622 : : them parallel. We can't move the PHI nodes, but we can turn
623 : : them into assignments. */
624 : 348 : for (gphi_iterator gsi = gsi_start_phis (bb);
625 : 352 : !gsi_end_p (gsi);)
626 : : {
627 : 5 : gphi *phi = gsi.phi ();
628 : :
629 : 5 : gcc_assert (gimple_phi_num_args (phi) == 1);
630 : 5 : tree def = gimple_phi_result (phi);
631 : :
632 : 5 : if (!bitmap_bit_p (used, SSA_NAME_VERSION (def)))
633 : : {
634 : 0 : gsi_next (&gsi);
635 : 0 : continue;
636 : : }
637 : :
638 : 5 : if (stmts.length () < max_stmts)
639 : 4 : stmts.quick_push (phi);
640 : : else
641 : 1 : return false;
642 : :
643 : : /* Mark uses in STMT before moving it. */
644 : 4 : use_operand_p use_p;
645 : 4 : ssa_op_iter it;
646 : 8 : FOR_EACH_PHI_ARG (use_p, phi, it, SSA_OP_USE)
647 : 4 : ifcombine_mark_ssa_name (used, USE_FROM_PTR (use_p),
648 : : outer_bb);
649 : : }
650 : : }
651 : :
652 : : /* ??? Test whether it makes sense to move STMTS. */
653 : :
654 : : /* Move the STMTS that need moving. From this point on, we're
655 : : committing to the attempted ifcombine. */
656 : 207 : gimple_stmt_iterator gsins = gsi_for_stmt (outer_cond);
657 : 207 : unsigned i;
658 : 207 : gimple *stmt;
659 : 347 : FOR_EACH_VEC_ELT (stmts, i, stmt)
660 : : {
661 : 140 : if (gphi *phi = dyn_cast <gphi *> (stmt))
662 : : {
663 : 0 : tree def = gimple_phi_result (phi);
664 : 0 : tree use = gimple_phi_arg_def (phi, 0);
665 : 0 : location_t loc = gimple_phi_arg_location (phi, 0);
666 : :
667 : 0 : gphi_iterator gsi = gsi_for_phi (phi);
668 : 0 : remove_phi_node (&gsi, false);
669 : :
670 : 0 : gassign *a = gimple_build_assign (def, use);
671 : 0 : gimple_set_location (a, loc);
672 : 0 : gsi_insert_before (&gsins, a, GSI_NEW_STMT);
673 : : }
674 : : else
675 : : {
676 : 140 : gimple_stmt_iterator gsitr = gsi_for_stmt (stmt);
677 : 140 : gsi_move_before (&gsitr, &gsins, GSI_NEW_STMT);
678 : : }
679 : : }
680 : :
681 : 347 : for (; gsi_stmt (gsins) != outer_cond; gsi_next (&gsins))
682 : : {
683 : : /* Clear range info from all defs we've moved from under
684 : : conditions. */
685 : 140 : tree t;
686 : 140 : ssa_op_iter it;
687 : 280 : FOR_EACH_SSA_TREE_OPERAND (t, gsi_stmt (gsins), it, SSA_OP_DEF)
688 : 140 : reset_flow_sensitive_info (t);
689 : : /* Avoid introducing undefined overflows while at that. */
690 : 140 : ifcombine_rewrite_to_defined_overflow (gsins);
691 : : }
692 : 208 : }
693 : 1 : }
694 : :
695 : 224 : if (!is_gimple_condexpr_for_cond (cond))
696 : : {
697 : 101 : gimple_stmt_iterator gsi = gsi_for_stmt (outer_cond);
698 : 101 : cond = force_gimple_operand_gsi_1 (&gsi, cond,
699 : : is_gimple_condexpr_for_cond,
700 : : NULL, true, GSI_SAME_STMT);
701 : : }
702 : :
703 : : /* Leave CFG optimization to cfg_cleanup. */
704 : 224 : gimple_cond_set_condition_from_tree (outer_cond, cond);
705 : 224 : update_stmt (outer_cond);
706 : :
707 : 224 : if (cond2)
708 : : {
709 : 115 : if (inner_inv)
710 : 115 : cond2 = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond2), cond2);
711 : :
712 : 115 : if (tree tcanon = canonicalize_cond_expr_cond (cond2))
713 : 43 : cond2 = tcanon;
714 : 115 : if (!is_gimple_condexpr_for_cond (cond2))
715 : : {
716 : 72 : gimple_stmt_iterator gsi = gsi_for_stmt (inner_cond);
717 : 72 : cond2 = force_gimple_operand_gsi_1 (&gsi, cond2,
718 : : is_gimple_condexpr_for_cond,
719 : : NULL, true, GSI_SAME_STMT);
720 : : }
721 : 115 : gimple_cond_set_condition_from_tree (inner_cond, cond2);
722 : : }
723 : : else
724 : 109 : gimple_cond_set_condition_from_tree (inner_cond,
725 : : inner_inv
726 : : ? boolean_false_node
727 : : : boolean_true_node);
728 : 224 : update_stmt (inner_cond);
729 : : }
730 : : else
731 : : {
732 : 85060 : if (!is_gimple_condexpr_for_cond (cond))
733 : : {
734 : 80760 : gimple_stmt_iterator gsi = gsi_for_stmt (inner_cond);
735 : 80760 : cond = force_gimple_operand_gsi_1 (&gsi, cond,
736 : : is_gimple_condexpr_for_cond,
737 : : NULL, true, GSI_SAME_STMT);
738 : : }
739 : 85060 : gimple_cond_set_condition_from_tree (inner_cond, cond);
740 : 85060 : update_stmt (inner_cond);
741 : :
742 : : /* Leave CFG optimization to cfg_cleanup. */
743 : 85060 : gimple_cond_set_condition_from_tree (outer_cond,
744 : : outer_inv
745 : : ? boolean_false_node
746 : : : boolean_true_node);
747 : 85060 : update_stmt (outer_cond);
748 : : }
749 : :
750 : : /* We're changing conditions that guard inner blocks, so reset flow sensitive
751 : : info and avoid introducing undefined behavior. */
752 : 170728 : for (basic_block bb = gimple_bb (inner_cond), end = gimple_bb (outer_cond);
753 : 170728 : bb != end; bb = single_pred (bb))
754 : : {
755 : : /* Clear range info from all stmts in BB which is now guarded by
756 : : different conditionals. */
757 : 85444 : reset_flow_sensitive_info_in_bb (gimple_bb (inner_cond));
758 : :
759 : : /* We only need to worry about introducing undefined behavior if we've
760 : : relaxed the outer condition. */
761 : 85444 : if (strictening_outer_cond)
762 : 275 : continue;
763 : :
764 : : /* Avoid introducing undefined behavior as we move stmts that used to be
765 : : guarded by OUTER_COND. */
766 : 170338 : for (gimple_stmt_iterator gsi = gsi_start_bb (gimple_bb (inner_cond));
767 : 422623 : !gsi_end_p (gsi); gsi_next (&gsi))
768 : 337454 : ifcombine_rewrite_to_defined_overflow (gsi);
769 : : }
770 : :
771 : 85284 : update_profile_after_ifcombine (gimple_bb (inner_cond),
772 : : gimple_bb (outer_cond));
773 : :
774 : 85284 : return true;
775 : : }
776 : :
777 : : /* Returns true if inner_cond_bb contains just the condition or 1/2 statements
778 : : that define lhs or rhs with an integer conversion. */
779 : :
780 : : static bool
781 : 145310 : can_combine_bbs_with_short_circuit (basic_block inner_cond_bb, tree lhs, tree rhs)
782 : : {
783 : 145310 : gimple_stmt_iterator gsi;
784 : 145310 : gsi = gsi_start_nondebug_after_labels_bb (inner_cond_bb);
785 : : /* If only the condition, this should be allowed. */
786 : 145310 : if (gsi_one_before_end_p (gsi))
787 : : return true;
788 : : /* Can have up to 2 statements defining each of lhs/rhs. */
789 : 72541 : for (int i = 0; i < 2; i++)
790 : : {
791 : 72541 : gimple *stmt = gsi_stmt (gsi);
792 : 72541 : if (!is_gimple_assign (stmt)
793 : 72541 : || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt)))
794 : : return false;
795 : : /* The defining statement needs to match either the lhs or rhs of
796 : : the condition. */
797 : 9985 : if (lhs != gimple_assign_lhs (stmt)
798 : 9985 : && rhs != gimple_assign_lhs (stmt))
799 : : return false;
800 : 4980 : gsi_next_nondebug (&gsi);
801 : 83130 : if (gsi_one_before_end_p (gsi))
802 : : return true;
803 : : }
804 : : return false;
805 : : }
806 : :
807 : : /* If-convert on a and pattern with a common else block. The inner
808 : : if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
809 : : inner_inv, outer_inv indicate whether the conditions are inverted.
810 : : Returns true if the edges to the common else basic-block were merged. */
811 : :
812 : : static bool
813 : 274498 : ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv,
814 : : basic_block outer_cond_bb, bool outer_inv)
815 : : {
816 : 274498 : gimple_stmt_iterator gsi;
817 : 274498 : tree name1, name2, bit1, bit2, bits1, bits2;
818 : :
819 : 548996 : gcond *inner_cond = safe_dyn_cast <gcond *> (*gsi_last_bb (inner_cond_bb));
820 : 274498 : if (!inner_cond)
821 : : return false;
822 : :
823 : 548996 : gcond *outer_cond = safe_dyn_cast <gcond *> (*gsi_last_bb (outer_cond_bb));
824 : 274498 : if (!outer_cond)
825 : : return false;
826 : :
827 : : /* See if we test a single bit of the same name in both tests. In
828 : : that case remove the outer test, merging both else edges,
829 : : and change the inner one to test for
830 : : name & (bit1 | bit2) == (bit1 | bit2). */
831 : 274498 : if (recognize_single_bit_test (inner_cond, &name1, &bit1, inner_inv)
832 : 2659 : && recognize_single_bit_test (outer_cond, &name2, &bit2, outer_inv)
833 : 275755 : && name1 == name2)
834 : : {
835 : 952 : tree t, t2;
836 : :
837 : 952 : if (TREE_CODE (name1) == SSA_NAME
838 : 952 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name1))
839 : : return false;
840 : :
841 : : /* Do it. */
842 : 952 : gsi = gsi_for_stmt (inner_cond);
843 : 952 : t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
844 : : build_int_cst (TREE_TYPE (name1), 1), bit1);
845 : 952 : t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
846 : : build_int_cst (TREE_TYPE (name1), 1), bit2);
847 : 952 : t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
848 : 952 : t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
849 : : true, GSI_SAME_STMT);
850 : 952 : t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
851 : 952 : t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE,
852 : : true, GSI_SAME_STMT);
853 : :
854 : 952 : t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t);
855 : :
856 : 952 : if (!ifcombine_replace_cond (inner_cond, inner_inv,
857 : : outer_cond, outer_inv,
858 : : t, true, NULL_TREE))
859 : : return false;
860 : :
861 : 952 : if (dump_file)
862 : : {
863 : 1 : fprintf (dump_file, "optimizing double bit test to ");
864 : 1 : print_generic_expr (dump_file, name1);
865 : 1 : fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
866 : 1 : print_generic_expr (dump_file, bit1);
867 : 1 : fprintf (dump_file, ") | (1 << ");
868 : 1 : print_generic_expr (dump_file, bit2);
869 : 1 : fprintf (dump_file, ")\n");
870 : : }
871 : :
872 : 952 : return true;
873 : : }
874 : :
875 : : /* See if we have two bit tests of the same name in both tests.
876 : : In that case remove the outer test and change the inner one to
877 : : test for name & (bits1 | bits2) != 0. */
878 : 273546 : else if (recognize_bits_test (inner_cond, &name1, &bits1, !inner_inv)
879 : 273546 : && recognize_bits_test (outer_cond, &name2, &bits2, !outer_inv))
880 : : {
881 : 2388 : tree t;
882 : :
883 : 2388 : if ((TREE_CODE (name1) == SSA_NAME
884 : 2387 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name1))
885 : 4775 : || (TREE_CODE (name2) == SSA_NAME
886 : 2387 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name2)))
887 : : return false;
888 : :
889 : : /* Find the common name which is bit-tested. */
890 : 2388 : if (name1 == name2)
891 : : ;
892 : 1048 : else if (bits1 == bits2)
893 : : {
894 : 88 : std::swap (name2, bits2);
895 : 88 : std::swap (name1, bits1);
896 : : }
897 : 960 : else if (name1 == bits2)
898 : 5 : std::swap (name2, bits2);
899 : 955 : else if (bits1 == name2)
900 : 0 : std::swap (name1, bits1);
901 : : else
902 : 955 : goto bits_test_failed;
903 : :
904 : : /* As we strip non-widening conversions in finding a common
905 : : name that is tested make sure to end up with an integral
906 : : type for building the bit operations. */
907 : 1433 : if (TYPE_PRECISION (TREE_TYPE (bits1))
908 : 1433 : >= TYPE_PRECISION (TREE_TYPE (bits2)))
909 : : {
910 : 1433 : bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
911 : 1433 : name1 = fold_convert (TREE_TYPE (bits1), name1);
912 : 1433 : bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
913 : 1433 : bits2 = fold_convert (TREE_TYPE (bits1), bits2);
914 : : }
915 : : else
916 : : {
917 : 0 : bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
918 : 0 : name1 = fold_convert (TREE_TYPE (bits2), name1);
919 : 0 : bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
920 : 0 : bits1 = fold_convert (TREE_TYPE (bits2), bits1);
921 : : }
922 : :
923 : 1433 : t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
924 : 1433 : t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
925 : 1433 : t = fold_build2 (EQ_EXPR, boolean_type_node, t,
926 : : build_int_cst (TREE_TYPE (t), 0));
927 : 1433 : if (!ifcombine_replace_cond (inner_cond, inner_inv,
928 : : outer_cond, outer_inv,
929 : : t, false, NULL_TREE))
930 : : return false;
931 : :
932 : 1433 : if (dump_file)
933 : : {
934 : 1 : fprintf (dump_file, "optimizing bits or bits test to ");
935 : 1 : print_generic_expr (dump_file, name1);
936 : 1 : fprintf (dump_file, " & T != 0\nwith temporary T = ");
937 : 1 : print_generic_expr (dump_file, bits1);
938 : 1 : fprintf (dump_file, " | ");
939 : 1 : print_generic_expr (dump_file, bits2);
940 : 1 : fprintf (dump_file, "\n");
941 : : }
942 : :
943 : 1433 : return true;
944 : : }
945 : :
946 : : /* See if we have two comparisons that we can merge into one. */
947 : 272113 : else bits_test_failed:
948 : 272113 : if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
949 : 272113 : && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
950 : : {
951 : 272113 : tree t, ts = NULL_TREE;
952 : 272113 : enum tree_code inner_cond_code = gimple_cond_code (inner_cond);
953 : 272113 : enum tree_code outer_cond_code = gimple_cond_code (outer_cond);
954 : :
955 : : /* Invert comparisons if necessary (and possible). */
956 : 272113 : if (inner_inv)
957 : 199309 : inner_cond_code = invert_tree_comparison (inner_cond_code,
958 : 199309 : HONOR_NANS (gimple_cond_lhs (inner_cond)));
959 : 272113 : if (inner_cond_code == ERROR_MARK)
960 : : return false;
961 : 270375 : if (outer_inv)
962 : 191421 : outer_cond_code = invert_tree_comparison (outer_cond_code,
963 : 191421 : HONOR_NANS (gimple_cond_lhs (outer_cond)));
964 : 270375 : if (outer_cond_code == ERROR_MARK)
965 : : return false;
966 : : /* Don't return false so fast, try maybe_fold_or_comparisons? */
967 : :
968 : 270097 : if (!(t = maybe_fold_and_comparisons (boolean_type_node, inner_cond_code,
969 : : gimple_cond_lhs (inner_cond),
970 : : gimple_cond_rhs (inner_cond),
971 : : outer_cond_code,
972 : : gimple_cond_lhs (outer_cond),
973 : : gimple_cond_rhs (outer_cond),
974 : : gimple_bb (outer_cond)))
975 : 270097 : && !(t = (fold_truth_andor_for_ifcombine
976 : 268061 : (TRUTH_ANDIF_EXPR, boolean_type_node,
977 : : gimple_location (outer_cond),
978 : : outer_cond_code,
979 : : gimple_cond_lhs (outer_cond),
980 : : gimple_cond_rhs (outer_cond),
981 : : gimple_location (inner_cond),
982 : : inner_cond_code,
983 : : gimple_cond_lhs (inner_cond),
984 : : gimple_cond_rhs (inner_cond),
985 : 268061 : single_pred (inner_cond_bb) != outer_cond_bb
986 : : ? &ts : 0))))
987 : : {
988 : : /* Only combine conditions in this fallback case if the blocks are
989 : : neighbors. */
990 : 264946 : if (single_pred (inner_cond_bb) != outer_cond_bb)
991 : : return false;
992 : 145440 : tree t1, t2;
993 : 145440 : bool logical_op_non_short_circuit = LOGICAL_OP_NON_SHORT_CIRCUIT;
994 : 145440 : if (param_logical_op_non_short_circuit != -1)
995 : 167 : logical_op_non_short_circuit
996 : 167 : = param_logical_op_non_short_circuit;
997 : 145440 : if (!logical_op_non_short_circuit || sanitize_coverage_p ())
998 : 130 : return false;
999 : : /* Only do this optimization if the inner bb contains only the conditional
1000 : : or there is one or 2 statements which are nop conversion for the comparison. */
1001 : 145310 : if (!can_combine_bbs_with_short_circuit (inner_cond_bb,
1002 : : gimple_cond_lhs (inner_cond),
1003 : : gimple_cond_rhs (inner_cond)))
1004 : : return false;
1005 : 77749 : t1 = fold_build2_loc (gimple_location (inner_cond),
1006 : : inner_cond_code,
1007 : : boolean_type_node,
1008 : : gimple_cond_lhs (inner_cond),
1009 : : gimple_cond_rhs (inner_cond));
1010 : 77749 : t2 = fold_build2_loc (gimple_location (outer_cond),
1011 : : outer_cond_code,
1012 : : boolean_type_node,
1013 : : gimple_cond_lhs (outer_cond),
1014 : : gimple_cond_rhs (outer_cond));
1015 : 77749 : t = fold_build2_loc (gimple_location (inner_cond),
1016 : : TRUTH_AND_EXPR, boolean_type_node, t1, t2);
1017 : : }
1018 : :
1019 : 82900 : if (!ifcombine_replace_cond (inner_cond, inner_inv,
1020 : : outer_cond, outer_inv,
1021 : : t, false, ts))
1022 : : return false;
1023 : :
1024 : 82899 : if (dump_file)
1025 : : {
1026 : 30 : fprintf (dump_file, "optimizing two comparisons to ");
1027 : 30 : print_generic_expr (dump_file, t);
1028 : 30 : if (ts)
1029 : : {
1030 : 0 : fprintf (dump_file, " and ");
1031 : 0 : print_generic_expr (dump_file, ts);
1032 : : }
1033 : 30 : fprintf (dump_file, "\n");
1034 : : }
1035 : :
1036 : 82899 : return true;
1037 : : }
1038 : :
1039 : : return false;
1040 : : }
1041 : :
1042 : : /* Helper function for tree_ssa_ifcombine_bb. Recognize a CFG pattern and
1043 : : dispatch to the appropriate if-conversion helper for a particular
1044 : : set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB.
1045 : : PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB.
1046 : : OUTER_SUCC_BB is the successor of OUTER_COND_BB on the path towards
1047 : : INNER_COND_BB. */
1048 : :
1049 : : static bool
1050 : 956742 : tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb,
1051 : : basic_block then_bb, basic_block else_bb,
1052 : : basic_block phi_pred_bb, basic_block outer_succ_bb)
1053 : : {
1054 : : /* The && form is characterized by a common else_bb with
1055 : : the two edges leading to it mergable. The latter is
1056 : : guaranteed by matching PHI arguments in the else_bb and
1057 : : the inner cond_bb having no side-effects. */
1058 : 956742 : if (phi_pred_bb != else_bb
1059 : 937751 : && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &else_bb)
1060 : 1034793 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
1061 : : {
1062 : : /* We have
1063 : : <outer_cond_bb>
1064 : : if (q) goto inner_cond_bb; else goto else_bb;
1065 : : <inner_cond_bb>
1066 : : if (p) goto ...; else goto else_bb;
1067 : : ...
1068 : : <else_bb>
1069 : : ...
1070 : : */
1071 : 69504 : return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, false);
1072 : : }
1073 : :
1074 : : /* And a version where the outer condition is negated. */
1075 : 887238 : if (phi_pred_bb != else_bb
1076 : 868247 : && recognize_if_then_else (outer_cond_bb, &else_bb, &outer_succ_bb)
1077 : 897823 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
1078 : : {
1079 : : /* We have
1080 : : <outer_cond_bb>
1081 : : if (q) goto else_bb; else goto inner_cond_bb;
1082 : : <inner_cond_bb>
1083 : : if (p) goto ...; else goto else_bb;
1084 : : ...
1085 : : <else_bb>
1086 : : ...
1087 : : */
1088 : 4285 : return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, true);
1089 : : }
1090 : :
1091 : : /* The || form is characterized by a common then_bb with the
1092 : : two edges leading to it mergeable. The latter is guaranteed
1093 : : by matching PHI arguments in the then_bb and the inner cond_bb
1094 : : having no side-effects. */
1095 : 882953 : if (phi_pred_bb != then_bb
1096 : 871258 : && recognize_if_then_else (outer_cond_bb, &then_bb, &outer_succ_bb)
1097 : 1107063 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
1098 : : {
1099 : : /* We have
1100 : : <outer_cond_bb>
1101 : : if (q) goto then_bb; else goto inner_cond_bb;
1102 : : <inner_cond_bb>
1103 : : if (p) goto then_bb; else goto ...;
1104 : : <then_bb>
1105 : : ...
1106 : : */
1107 : 188560 : return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, true);
1108 : : }
1109 : :
1110 : : /* And a version where the outer condition is negated. */
1111 : 694393 : if (phi_pred_bb != then_bb
1112 : 682698 : && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &then_bb)
1113 : 712017 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
1114 : : {
1115 : : /* We have
1116 : : <outer_cond_bb>
1117 : : if (q) goto inner_cond_bb; else goto then_bb;
1118 : : <inner_cond_bb>
1119 : : if (p) goto then_bb; else goto ...;
1120 : : <then_bb>
1121 : : ...
1122 : : */
1123 : 12149 : return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false);
1124 : : }
1125 : :
1126 : : return false;
1127 : : }
1128 : :
1129 : : /* Recognize a CFG pattern and dispatch to the appropriate
1130 : : if-conversion helper. We start with BB as the innermost
1131 : : worker basic-block. Returns true if a transformation was done. */
1132 : :
1133 : : static bool
1134 : 3980845 : tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
1135 : : {
1136 : 3980845 : bool ret = false;
1137 : 3980845 : basic_block then_bb = NULL, else_bb = NULL;
1138 : :
1139 : 3980845 : if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
1140 : : return ret;
1141 : :
1142 : : /* Recognize && and || of two conditions with a common
1143 : : then/else block which entry edges we can merge. That is:
1144 : : if (a || b)
1145 : : ;
1146 : : and
1147 : : if (a && b)
1148 : : ;
1149 : : This requires a single predecessor of the inner cond_bb.
1150 : :
1151 : : Look for an OUTER_COND_BBs to combine with INNER_COND_BB. They need not
1152 : : be contiguous, as long as inner and intervening blocks have no side
1153 : : effects, and are either single-entry-single-exit or conditionals choosing
1154 : : between the same EXIT_BB with the same PHI args, possibly through an
1155 : : EXIT_PRED, and the path leading to INNER_COND_BB. EXIT_PRED will be set
1156 : : just before (along with a successful combination) or just after setting
1157 : : EXIT_BB, to either THEN_BB, ELSE_BB, or INNER_COND_BB. ??? We could
1158 : : potentially handle multi-block single-entry-single-exit regions, but the
1159 : : loop below only deals with single-entry-single-exit individual intervening
1160 : : blocks. Larger regions without side effects are presumably rare, so it's
1161 : : probably not worth the effort. */
1162 : 4548366 : for (basic_block bb = inner_cond_bb, outer_cond_bb, exit_bb = NULL,
1163 : : /* This initialization shouldn't be needed, but in case the compiler
1164 : : is not smart enough to tell, make it harmless. */
1165 : 3980785 : exit_pred = NULL;
1166 : 4548366 : single_pred_p (bb) && bb_no_side_effects_p (bb);
1167 : 567581 : bb = outer_cond_bb)
1168 : : {
1169 : 1398791 : bool changed = false;
1170 : :
1171 : 1398791 : outer_cond_bb = single_pred (bb);
1172 : :
1173 : : /* Skip blocks without conditions. */
1174 : 1398791 : if (single_succ_p (outer_cond_bb))
1175 : 112687 : continue;
1176 : :
1177 : : /* When considering noncontiguous conditions, make sure that all
1178 : : non-final conditions lead to the same successor of the final
1179 : : condition, when not taking the path to inner_bb, so that we can
1180 : : combine C into A, both in A && (B && C), and in A || (B || C), but
1181 : : neither in A && (B || C), nor A || (B && C). Say, if C goes to
1182 : : THEN_BB or ELSE_BB, then B must go to either of these, say X, besides
1183 : : C (whether C is then or else), and A must go to X and B (whether then
1184 : : or else).
1185 : :
1186 : : We test for this, while allowing intervening nonconditional blocks, by
1187 : : first taking note of which of the successors of the inner conditional
1188 : : block is the exit path taken by the first considered outer conditional
1189 : : block.
1190 : :
1191 : : Having identified and saved the exit block in EXIT_BB at the end of
1192 : : the loop, here we test that subsequent conditional blocks under
1193 : : consideration also use the exit block as a successor, besides the
1194 : : block that leads to inner_cond_bb, and that the edges to exit share
1195 : : the same phi values. */
1196 : 1286104 : if (exit_bb
1197 : 1286104 : && !recognize_if_then_else (outer_cond_bb, &bb, &exit_bb, true))
1198 : : break;
1199 : :
1200 : : /* After checking dests and phi args, we can also skip blocks whose
1201 : : conditions have been optimized down to a constant, without trying to
1202 : : combine them, but we must not skip the computation of EXIT_BB and the
1203 : : checking of same phi args. */
1204 : 1266352 : if (known_succ_p (outer_cond_bb))
1205 : : changed = false;
1206 : 128481 : else if ((!exit_bb || exit_pred == inner_cond_bb)
1207 : 1054377 : && tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb,
1208 : : then_bb, else_bb, inner_cond_bb, bb))
1209 : : changed = true, exit_pred = inner_cond_bb;
1210 : 840826 : else if (exit_bb
1211 : 840826 : ? exit_pred == else_bb
1212 : 712460 : : forwarder_block_to (else_bb, then_bb))
1213 : : {
1214 : : /* Other possibilities for the && form, if else_bb is
1215 : : empty forwarder block to then_bb. Compared to the above simpler
1216 : : forms this can be treated as if then_bb and else_bb were swapped,
1217 : : and the corresponding inner_cond_bb not inverted because of that.
1218 : : For same_phi_args_p we look at equality of arguments between
1219 : : edge from outer_cond_bb and the forwarder block. */
1220 : 11855 : if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
1221 : : then_bb, else_bb, bb))
1222 : : changed = true, exit_pred = else_bb;
1223 : : }
1224 : 828971 : else if (exit_bb
1225 : 828971 : ? exit_pred == then_bb
1226 : 700632 : : forwarder_block_to (then_bb, else_bb))
1227 : : {
1228 : : /* Other possibilities for the || form, if then_bb is
1229 : : empty forwarder block to else_bb. Compared to the above simpler
1230 : : forms this can be treated as if then_bb and else_bb were swapped,
1231 : : and the corresponding inner_cond_bb not inverted because of that.
1232 : : For same_phi_args_p we look at equality of arguments between
1233 : : edge from outer_cond_bb and the forwarder block. */
1234 : 18991 : if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
1235 : : then_bb, then_bb, bb))
1236 : : changed = true, exit_pred = then_bb;
1237 : : }
1238 : :
1239 : : if (changed)
1240 : 85284 : ret = changed;
1241 : :
1242 : : /* If the inner condition is gone, there's no point in attempting to
1243 : : combine it any further. */
1244 : 85284 : if (changed && known_succ_p (inner_cond_bb))
1245 : : break;
1246 : :
1247 : : /* Starting at this point in the loop, we start preparing to attempt
1248 : : combinations in which OUTER_COND_BB will be an intervening block.
1249 : : Checking that it has a single predecessor is a very cheap test, unlike
1250 : : the PHI args tests below, so test it early and hopefully save the more
1251 : : expensive tests in case we won't be able to try other blocks. */
1252 : 1266241 : if (!single_pred_p (outer_cond_bb))
1253 : : break;
1254 : :
1255 : : /* Record the exit path taken by the outer condition. */
1256 : 966520 : if (!exit_bb)
1257 : : {
1258 : : /* If we have removed the outer condition entirely, we need not
1259 : : commit to an exit block yet, it's as if we'd merged the blocks and
1260 : : were starting afresh. This is sound as long as we never replace
1261 : : the outer condition with a constant that leads away from the inner
1262 : : block. Here's why we never do: when combining contiguous
1263 : : conditions, we replace the inner cond, and replace the outer cond
1264 : : with a constant that leads to inner, so this case is good. When
1265 : : combining noncontiguous blocks, we normally modify outer, and
1266 : : replace inner with a constant or remainders of the original
1267 : : condition that couldn't be combined. This test would normally not
1268 : : hit with noncontiguous blocks, because we'd have computed EXIT_BB
1269 : : before reaching the noncontiguous outer block. However, if all
1270 : : intervening blocks are unconditional, including those just made
1271 : : unconditional, we may replace outer instead of inner with the
1272 : : combined condition. If the combined noncontiguous conditions are
1273 : : mutually exclusive, we could end up with a constant outer
1274 : : condition, but then, the inner condition would also be a constant,
1275 : : and then we'd stop iterating because of the known_succ_p
1276 : : (inner_cond_bb) test above. */
1277 : 642517 : if (changed && known_succ_p (outer_cond_bb))
1278 : 65937 : continue;
1279 : :
1280 : 576580 : if (recognize_if_then_else (outer_cond_bb, &then_bb, &bb, true))
1281 : 78196 : exit_bb = then_bb;
1282 : 498384 : else if (recognize_if_then_else (outer_cond_bb, &bb, &else_bb, true))
1283 : 30275 : exit_bb = else_bb;
1284 : : else
1285 : : break;
1286 : :
1287 : : /* Find out which path from INNER_COND_BB shares PHI args with the
1288 : : edge (OUTER_COND_BB->EXIT_BB). That path may involve a forwarder
1289 : : block, whether THEN_BB or ELSE_BB, and we need to know which one
1290 : : satisfies the condition to avoid combinations that could use
1291 : : different forwarding arrangements, because they would be unsound.
1292 : : E.g., given (a ? 0 : b ? 1 : c ? 1 : 0), after trying to merge b
1293 : : and c, we test that both share the same exit block, with the same
1294 : : value 1. Whether or not that involves a forwarder block, if we
1295 : : don't go through the same (possibly absent) forwarder block in
1296 : : subsequent attempted combinations, e.g. a with c, we could find
1297 : : that a and inverted c share the same exit block with a different
1298 : : value, namely 0, which would enable an unsound merge. We need all
1299 : : of inner, intervening and outer blocks to reach the same exit with
1300 : : the same value for the transformation to be sound. So here we
1301 : : determine how to get to EXIT_BB from outer and inner with the same
1302 : : PHI values, record that in EXIT_PRED, and then subsequent
1303 : : combination attempts that have OUTER_COND_BB as an intervening
1304 : : block will ensure the same path to exit is taken, skipping unsound
1305 : : transformations. */
1306 : 108471 : if (changed)
1307 : : /* EXIT_PRED was set along with CHANGED, and the successful
1308 : : combination already checked for the same PHI args. */;
1309 : 108365 : else if (same_phi_args_p (outer_cond_bb, inner_cond_bb, exit_bb))
1310 : : exit_pred = inner_cond_bb;
1311 : 30780 : else if (then_bb == exit_bb
1312 : 22936 : && forwarder_block_to (else_bb, then_bb)
1313 : 33068 : && same_phi_args_p (outer_cond_bb, else_bb, exit_bb))
1314 : : exit_pred = else_bb;
1315 : 30722 : else if (else_bb == exit_bb
1316 : 7844 : && forwarder_block_to (then_bb, else_bb)
1317 : 31759 : && same_phi_args_p (outer_cond_bb, then_bb, exit_bb))
1318 : : exit_pred = then_bb;
1319 : : else
1320 : : /* If none of the paths share the same PHI args, no combination is
1321 : : viable. */
1322 : : break;
1323 : : /* Skip the PHI args test below, it's redundant with the tests we've
1324 : : just performed. */
1325 : 77870 : continue;
1326 : : }
1327 : :
1328 : : /* Before trying an earlier block, make sure INNER_COND_BB and the
1329 : : current OUTER_COND_BB share the same PHI args at EXIT_BB. We don't
1330 : : need to check if the latest attempt at combining succeeded, because
1331 : : that means we'll have already checked. But we can't only check outer
1332 : : and inner, we have to check that all intervening blocks also get to
1333 : : exit with the same result, otherwise the transformation may change the
1334 : : final result. Consider (a ? 0 : b ? 1 : c ? 0 : -1). If we combine
1335 : : (a | c), yielding ((a | c) ? 0 : b ? 1 : [0 ? 0 :] -1), we'd get 0
1336 : : rather than 1 when (!a&&b). And if we were to replace inner instead
1337 : : of outer, we'd get ([1 ? 0 :] b ? 1 : (a | c) ? 0 : -1), which would
1338 : : yield 1 rather than 0 when (a). */
1339 : 324003 : if (!changed
1340 : 324003 : && !same_phi_args_p (outer_cond_bb, exit_pred, exit_bb))
1341 : : break;
1342 : : }
1343 : :
1344 : 3980785 : return ret;
1345 : : }
1346 : :
1347 : : /* Main entry for the tree if-conversion pass. */
1348 : :
1349 : : namespace {
1350 : :
1351 : : const pass_data pass_data_tree_ifcombine =
1352 : : {
1353 : : GIMPLE_PASS, /* type */
1354 : : "ifcombine", /* name */
1355 : : OPTGROUP_NONE, /* optinfo_flags */
1356 : : TV_TREE_IFCOMBINE, /* tv_id */
1357 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
1358 : : 0, /* properties_provided */
1359 : : 0, /* properties_destroyed */
1360 : : 0, /* todo_flags_start */
1361 : : TODO_update_ssa, /* todo_flags_finish */
1362 : : };
1363 : :
1364 : : class pass_tree_ifcombine : public gimple_opt_pass
1365 : : {
1366 : : public:
1367 : 280831 : pass_tree_ifcombine (gcc::context *ctxt)
1368 : 561662 : : gimple_opt_pass (pass_data_tree_ifcombine, ctxt)
1369 : : {}
1370 : :
1371 : : /* opt_pass methods: */
1372 : : unsigned int execute (function *) final override;
1373 : :
1374 : : }; // class pass_tree_ifcombine
1375 : :
1376 : : unsigned int
1377 : 1000722 : pass_tree_ifcombine::execute (function *fun)
1378 : : {
1379 : 1000722 : basic_block *bbs;
1380 : 1000722 : bool cfg_changed = false;
1381 : 1000722 : int i;
1382 : :
1383 : 1000722 : bbs = single_pred_before_succ_order ();
1384 : 1000722 : calculate_dominance_info (CDI_DOMINATORS);
1385 : 1000722 : mark_ssa_maybe_undefs ();
1386 : :
1387 : : /* Search every basic block for COND_EXPR we may be able to optimize.
1388 : :
1389 : : We walk the blocks in order that guarantees that a block with
1390 : : a single predecessor is processed after the predecessor.
1391 : : This ensures that we collapse outter ifs before visiting the
1392 : : inner ones, and also that we do not try to visit a removed
1393 : : block. This is opposite of PHI-OPT, because we cascade the
1394 : : combining rather than cascading PHIs. */
1395 : 10637074 : for (i = n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS - 1; i >= 0; i--)
1396 : : {
1397 : 9636352 : basic_block bb = bbs[i];
1398 : :
1399 : 19272704 : if (safe_is_a <gcond *> (*gsi_last_bb (bb)))
1400 : 3980845 : if (tree_ssa_ifcombine_bb (bb))
1401 : 9636352 : cfg_changed |= true;
1402 : : }
1403 : :
1404 : 1000722 : free (bbs);
1405 : :
1406 : 1000722 : return cfg_changed ? TODO_cleanup_cfg : 0;
1407 : : }
1408 : :
1409 : : } // anon namespace
1410 : :
1411 : : gimple_opt_pass *
1412 : 280831 : make_pass_tree_ifcombine (gcc::context *ctxt)
1413 : : {
1414 : 280831 : return new pass_tree_ifcombine (ctxt);
1415 : : }
|