Branch data Line data Source code
1 : : /* Combining of if-expressions on trees.
2 : : Copyright (C) 2007-2024 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 : :
46 : : #ifndef LOGICAL_OP_NON_SHORT_CIRCUIT
47 : : #define LOGICAL_OP_NON_SHORT_CIRCUIT \
48 : : (BRANCH_COST (optimize_function_for_speed_p (cfun), \
49 : : false) >= 2)
50 : : #endif
51 : :
52 : : /* This pass combines COND_EXPRs to simplify control flow. It
53 : : currently recognizes bit tests and comparisons in chains that
54 : : represent logical and or logical or of two COND_EXPRs.
55 : :
56 : : It does so by walking basic blocks in a approximate reverse
57 : : post-dominator order and trying to match CFG patterns that
58 : : represent logical and or logical or of two COND_EXPRs.
59 : : Transformations are done if the COND_EXPR conditions match
60 : : either
61 : :
62 : : 1. two single bit tests X & (1 << Yn) (for logical and)
63 : :
64 : : 2. two bit tests X & Yn (for logical or)
65 : :
66 : : 3. two comparisons X OPn Y (for logical or)
67 : :
68 : : To simplify this pass, removing basic blocks and dead code
69 : : is left to CFG cleanup and DCE. */
70 : :
71 : :
72 : : /* Recognize a if-then-else CFG pattern starting to match with the
73 : : COND_BB basic-block containing the COND_EXPR. The recognized
74 : : then end else blocks are stored to *THEN_BB and *ELSE_BB. If
75 : : *THEN_BB and/or *ELSE_BB are already set, they are required to
76 : : match the then and else basic-blocks to make the pattern match.
77 : : Returns true if the pattern matched, false otherwise. */
78 : :
79 : : static bool
80 : 6200640 : recognize_if_then_else (basic_block cond_bb,
81 : : basic_block *then_bb, basic_block *else_bb)
82 : : {
83 : 6200640 : edge t, e;
84 : :
85 : 6200640 : if (EDGE_COUNT (cond_bb->succs) != 2)
86 : : return false;
87 : :
88 : : /* Find the then/else edges. */
89 : 5834708 : t = EDGE_SUCC (cond_bb, 0);
90 : 5834708 : e = EDGE_SUCC (cond_bb, 1);
91 : 5834708 : if (!(t->flags & EDGE_TRUE_VALUE))
92 : 370429 : std::swap (t, e);
93 : 5834708 : if (!(t->flags & EDGE_TRUE_VALUE)
94 : 5673122 : || !(e->flags & EDGE_FALSE_VALUE))
95 : : return false;
96 : :
97 : : /* Check if the edge destinations point to the required block. */
98 : 5673122 : if (*then_bb
99 : 1944498 : && t->dest != *then_bb)
100 : : return false;
101 : 4244650 : if (*else_bb
102 : 516026 : && e->dest != *else_bb)
103 : : return false;
104 : :
105 : 3871307 : if (!*then_bb)
106 : 3728624 : *then_bb = t->dest;
107 : 3871307 : if (!*else_bb)
108 : 3728624 : *else_bb = e->dest;
109 : :
110 : : return true;
111 : : }
112 : :
113 : : /* Verify if the basic block BB does not have side-effects. Return
114 : : true in this case, else false. */
115 : :
116 : : static bool
117 : 2560724 : bb_no_side_effects_p (basic_block bb)
118 : : {
119 : 2560724 : gimple_stmt_iterator gsi;
120 : :
121 : 10644226 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
122 : : {
123 : 7436403 : gimple *stmt = gsi_stmt (gsi);
124 : :
125 : 7436403 : if (is_gimple_debug (stmt))
126 : 4062454 : continue;
127 : :
128 : 3373949 : gassign *ass;
129 : 3373949 : enum tree_code rhs_code;
130 : 3373949 : if (gimple_has_side_effects (stmt)
131 : 2874580 : || gimple_could_trap_p (stmt)
132 : 2260476 : || gimple_vuse (stmt)
133 : : /* We need to rewrite stmts with undefined overflow to use
134 : : unsigned arithmetic but cannot do so for signed division. */
135 : 2296768 : || ((ass = dyn_cast <gassign *> (stmt))
136 : 766168 : && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (ass)))
137 : 1244320 : && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (ass)))
138 : 179712 : && ((rhs_code = gimple_assign_rhs_code (ass)), true)
139 : 179712 : && (rhs_code == TRUNC_DIV_EXPR
140 : : || rhs_code == CEIL_DIV_EXPR
141 : : || rhs_code == FLOOR_DIV_EXPR
142 : 179712 : || rhs_code == ROUND_DIV_EXPR)
143 : : /* We cannot use expr_not_equal_to since we'd have to restrict
144 : : flow-sensitive info to whats known at the outer if. */
145 : 1046 : && (TREE_CODE (gimple_assign_rhs2 (ass)) != INTEGER_CST
146 : 1046 : || !integer_minus_onep (gimple_assign_rhs2 (ass))))
147 : : /* const calls don't match any of the above, yet they could
148 : : still have some side-effects - they could contain
149 : : gimple_could_trap_p statements, like floating point
150 : : exceptions or integer division by zero. See PR70586.
151 : : FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
152 : : should handle this. */
153 : 5526709 : || is_gimple_call (stmt))
154 : 1913625 : return false;
155 : :
156 : 1463166 : ssa_op_iter it;
157 : 1463166 : tree use;
158 : 3207150 : FOR_EACH_SSA_TREE_OPERAND (use, stmt, it, SSA_OP_USE)
159 : 1746826 : if (ssa_name_maybe_undef_p (use))
160 : : return false;
161 : : }
162 : :
163 : : return true;
164 : : }
165 : :
166 : : /* Return true if BB is an empty forwarder block to TO_BB. */
167 : :
168 : : static bool
169 : 1139652 : forwarder_block_to (basic_block bb, basic_block to_bb)
170 : : {
171 : 1139652 : return empty_block_p (bb)
172 : 44610 : && single_succ_p (bb)
173 : 1184262 : && single_succ (bb) == to_bb;
174 : : }
175 : :
176 : : /* Verify if all PHI node arguments in DEST for edges from BB1 or
177 : : BB2 to DEST are the same. This makes the CFG merge point
178 : : free from side-effects. Return true in this case, else false. */
179 : :
180 : : static bool
181 : 142683 : same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
182 : : {
183 : 142683 : edge e1 = find_edge (bb1, dest);
184 : 142683 : edge e2 = find_edge (bb2, dest);
185 : 142683 : gphi_iterator gsi;
186 : 142683 : gphi *phi;
187 : :
188 : 216249 : for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
189 : : {
190 : 113655 : phi = gsi.phi ();
191 : 113655 : if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
192 : 113655 : PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
193 : : return false;
194 : : }
195 : :
196 : : return true;
197 : : }
198 : :
199 : : /* Return the best representative SSA name for CANDIDATE which is used
200 : : in a bit test. */
201 : :
202 : : static tree
203 : 3091 : get_name_for_bit_test (tree candidate)
204 : : {
205 : : /* Skip single-use names in favor of using the name from a
206 : : non-widening conversion definition. */
207 : 3091 : if (TREE_CODE (candidate) == SSA_NAME
208 : 3091 : && has_single_use (candidate))
209 : : {
210 : 1177 : gimple *def_stmt = SSA_NAME_DEF_STMT (candidate);
211 : 1177 : if (is_gimple_assign (def_stmt)
212 : 1177 : && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
213 : : {
214 : 113 : if (TYPE_PRECISION (TREE_TYPE (candidate))
215 : 113 : <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
216 : : return gimple_assign_rhs1 (def_stmt);
217 : : }
218 : : }
219 : :
220 : : return candidate;
221 : : }
222 : :
223 : : /* Recognize a single bit test pattern in GIMPLE_COND and its defining
224 : : statements. Store the name being tested in *NAME and the bit
225 : : in *BIT. The GIMPLE_COND computes *NAME & (1 << *BIT).
226 : : Returns true if the pattern matched, false otherwise. */
227 : :
228 : : static bool
229 : 105632 : recognize_single_bit_test (gcond *cond, tree *name, tree *bit, bool inv)
230 : : {
231 : 105632 : gimple *stmt;
232 : :
233 : : /* Get at the definition of the result of the bit test. */
234 : 105632 : if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
235 : 31507 : || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
236 : 136368 : || !integer_zerop (gimple_cond_rhs (cond)))
237 : 89920 : return false;
238 : 15712 : stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
239 : 15712 : if (!is_gimple_assign (stmt))
240 : : return false;
241 : :
242 : : /* Look at which bit is tested. One form to recognize is
243 : : D.1985_5 = state_3(D) >> control1_4(D);
244 : : D.1986_6 = (int) D.1985_5;
245 : : D.1987_7 = op0 & 1;
246 : : if (D.1987_7 != 0) */
247 : 11981 : if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
248 : 6094 : && integer_onep (gimple_assign_rhs2 (stmt))
249 : 12474 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
250 : : {
251 : 493 : tree orig_name = gimple_assign_rhs1 (stmt);
252 : :
253 : : /* Look through copies and conversions to eventually
254 : : find the stmt that computes the shift. */
255 : 493 : stmt = SSA_NAME_DEF_STMT (orig_name);
256 : :
257 : 493 : while (is_gimple_assign (stmt)
258 : 493 : && ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
259 : 0 : && (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt)))
260 : 0 : <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt))))
261 : 0 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
262 : 420 : || gimple_assign_ssa_name_copy_p (stmt)))
263 : 0 : stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
264 : :
265 : : /* If we found such, decompose it. */
266 : 493 : if (is_gimple_assign (stmt)
267 : 493 : && gimple_assign_rhs_code (stmt) == RSHIFT_EXPR)
268 : : {
269 : : /* op0 & (1 << op1) */
270 : 77 : *bit = gimple_assign_rhs2 (stmt);
271 : 77 : *name = gimple_assign_rhs1 (stmt);
272 : : }
273 : : else
274 : : {
275 : : /* t & 1 */
276 : 416 : *bit = integer_zero_node;
277 : 416 : *name = get_name_for_bit_test (orig_name);
278 : : }
279 : :
280 : 493 : return true;
281 : : }
282 : :
283 : : /* Another form is
284 : : D.1987_7 = op0 & (1 << CST)
285 : : if (D.1987_7 != 0) */
286 : 11488 : if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
287 : 5601 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
288 : 17089 : && integer_pow2p (gimple_assign_rhs2 (stmt)))
289 : : {
290 : 4246 : *name = gimple_assign_rhs1 (stmt);
291 : 4246 : *bit = build_int_cst (integer_type_node,
292 : 4246 : tree_log2 (gimple_assign_rhs2 (stmt)));
293 : 4246 : return true;
294 : : }
295 : :
296 : : /* Another form is
297 : : D.1986_6 = 1 << control1_4(D)
298 : : D.1987_7 = op0 & D.1986_6
299 : : if (D.1987_7 != 0) */
300 : 7242 : if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
301 : 1355 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
302 : 8597 : && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
303 : : {
304 : 1056 : gimple *tmp;
305 : :
306 : : /* Both arguments of the BIT_AND_EXPR can be the single-bit
307 : : specifying expression. */
308 : 1056 : tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
309 : 1056 : if (is_gimple_assign (tmp)
310 : 1028 : && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
311 : 1066 : && integer_onep (gimple_assign_rhs1 (tmp)))
312 : : {
313 : 10 : *name = gimple_assign_rhs2 (stmt);
314 : 10 : *bit = gimple_assign_rhs2 (tmp);
315 : 10 : return true;
316 : : }
317 : :
318 : 1046 : tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
319 : 1046 : if (is_gimple_assign (tmp)
320 : 934 : && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
321 : 1076 : && integer_onep (gimple_assign_rhs1 (tmp)))
322 : : {
323 : 30 : *name = gimple_assign_rhs1 (stmt);
324 : 30 : *bit = gimple_assign_rhs2 (tmp);
325 : 30 : return true;
326 : : }
327 : : }
328 : :
329 : : return false;
330 : : }
331 : :
332 : : /* Recognize a bit test pattern in a GIMPLE_COND and its defining
333 : : statements. Store the name being tested in *NAME and the bits
334 : : in *BITS. The COND_EXPR computes *NAME & *BITS.
335 : : Returns true if the pattern matched, false otherwise. */
336 : :
337 : : static bool
338 : 104311 : recognize_bits_test (gcond *cond, tree *name, tree *bits, bool inv)
339 : : {
340 : 104311 : gimple *stmt;
341 : :
342 : : /* Get at the definition of the result of the bit test. */
343 : 104311 : if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
344 : 31416 : || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
345 : 135434 : || !integer_zerop (gimple_cond_rhs (cond)))
346 : 94223 : return false;
347 : 10088 : stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
348 : 10088 : if (!is_gimple_assign (stmt)
349 : 10088 : || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
350 : : return false;
351 : :
352 : 2675 : *name = get_name_for_bit_test (gimple_assign_rhs1 (stmt));
353 : 2675 : *bits = gimple_assign_rhs2 (stmt);
354 : :
355 : 2675 : return true;
356 : : }
357 : :
358 : :
359 : : /* Update profile after code in outer_cond_bb was adjusted so
360 : : outer_cond_bb has no condition. */
361 : :
362 : : static void
363 : 70908 : update_profile_after_ifcombine (basic_block inner_cond_bb,
364 : : basic_block outer_cond_bb)
365 : : {
366 : 70908 : edge outer_to_inner = find_edge (outer_cond_bb, inner_cond_bb);
367 : 70908 : edge outer2 = (EDGE_SUCC (outer_cond_bb, 0) == outer_to_inner
368 : 70908 : ? EDGE_SUCC (outer_cond_bb, 1)
369 : 70908 : : EDGE_SUCC (outer_cond_bb, 0));
370 : 70908 : edge inner_taken = EDGE_SUCC (inner_cond_bb, 0);
371 : 70908 : edge inner_not_taken = EDGE_SUCC (inner_cond_bb, 1);
372 : :
373 : 70908 : if (inner_taken->dest != outer2->dest)
374 : 25861 : std::swap (inner_taken, inner_not_taken);
375 : 70908 : gcc_assert (inner_taken->dest == outer2->dest);
376 : :
377 : : /* In the following we assume that inner_cond_bb has single predecessor. */
378 : 141816 : gcc_assert (single_pred_p (inner_cond_bb));
379 : :
380 : : /* Path outer_cond_bb->(outer2) needs to be merged into path
381 : : outer_cond_bb->(outer_to_inner)->inner_cond_bb->(inner_taken)
382 : : and probability of inner_not_taken updated. */
383 : :
384 : 70908 : inner_cond_bb->count = outer_cond_bb->count;
385 : :
386 : : /* Handle special case where inner_taken probability is always. In this case
387 : : we know that the overall outcome will be always as well, but combining
388 : : probabilities will be conservative because it does not know that
389 : : outer2->probability is inverse of outer_to_inner->probability. */
390 : 70908 : if (inner_taken->probability == profile_probability::always ())
391 : : ;
392 : : else
393 : 69716 : inner_taken->probability = outer2->probability + outer_to_inner->probability
394 : 69716 : * inner_taken->probability;
395 : 70908 : inner_not_taken->probability = profile_probability::always ()
396 : 70908 : - inner_taken->probability;
397 : :
398 : 70908 : outer_to_inner->probability = profile_probability::always ();
399 : 70908 : outer2->probability = profile_probability::never ();
400 : 70908 : }
401 : :
402 : : /* If-convert on a and pattern with a common else block. The inner
403 : : if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
404 : : inner_inv, outer_inv and result_inv indicate whether the conditions
405 : : are inverted.
406 : : Returns true if the edges to the common else basic-block were merged. */
407 : :
408 : : static bool
409 : 102594 : ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv,
410 : : basic_block outer_cond_bb, bool outer_inv, bool result_inv)
411 : : {
412 : 102594 : gimple_stmt_iterator gsi;
413 : 102594 : tree name1, name2, bit1, bit2, bits1, bits2;
414 : :
415 : 205188 : gcond *inner_cond = safe_dyn_cast <gcond *> (*gsi_last_bb (inner_cond_bb));
416 : 102594 : if (!inner_cond)
417 : : return false;
418 : :
419 : 236467 : gcond *outer_cond = safe_dyn_cast <gcond *> (*gsi_last_bb (outer_cond_bb));
420 : 102594 : if (!outer_cond)
421 : : return false;
422 : :
423 : : /* See if we test a single bit of the same name in both tests. In
424 : : that case remove the outer test, merging both else edges,
425 : : and change the inner one to test for
426 : : name & (bit1 | bit2) == (bit1 | bit2). */
427 : 102594 : if (recognize_single_bit_test (inner_cond, &name1, &bit1, inner_inv)
428 : 3038 : && recognize_single_bit_test (outer_cond, &name2, &bit2, outer_inv)
429 : 104335 : && name1 == name2)
430 : : {
431 : 63 : tree t, t2;
432 : :
433 : 63 : if (TREE_CODE (name1) == SSA_NAME
434 : 63 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name1))
435 : : return false;
436 : :
437 : : /* Do it. */
438 : 63 : gsi = gsi_for_stmt (inner_cond);
439 : 63 : t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
440 : : build_int_cst (TREE_TYPE (name1), 1), bit1);
441 : 63 : t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
442 : : build_int_cst (TREE_TYPE (name1), 1), bit2);
443 : 63 : t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
444 : 63 : t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
445 : : true, GSI_SAME_STMT);
446 : 63 : t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
447 : 63 : t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE,
448 : : true, GSI_SAME_STMT);
449 : 92 : t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR,
450 : : boolean_type_node, t2, t);
451 : 63 : t = canonicalize_cond_expr_cond (t);
452 : 63 : if (!t)
453 : : return false;
454 : 63 : if (!is_gimple_condexpr_for_cond (t))
455 : : {
456 : 0 : gsi = gsi_for_stmt (inner_cond);
457 : 0 : t = force_gimple_operand_gsi_1 (&gsi, t, is_gimple_condexpr_for_cond,
458 : : NULL, true, GSI_SAME_STMT);
459 : : }
460 : 63 : gimple_cond_set_condition_from_tree (inner_cond, t);
461 : 63 : update_stmt (inner_cond);
462 : :
463 : : /* Leave CFG optimization to cfg_cleanup. */
464 : 63 : gimple_cond_set_condition_from_tree (outer_cond,
465 : : outer_inv ? boolean_false_node : boolean_true_node);
466 : 63 : update_stmt (outer_cond);
467 : :
468 : 63 : update_profile_after_ifcombine (inner_cond_bb, outer_cond_bb);
469 : :
470 : 63 : if (dump_file)
471 : : {
472 : 1 : fprintf (dump_file, "optimizing double bit test to ");
473 : 1 : print_generic_expr (dump_file, name1);
474 : 1 : fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
475 : 1 : print_generic_expr (dump_file, bit1);
476 : 1 : fprintf (dump_file, ") | (1 << ");
477 : 1 : print_generic_expr (dump_file, bit2);
478 : 1 : fprintf (dump_file, ")\n");
479 : : }
480 : :
481 : 63 : return true;
482 : : }
483 : :
484 : : /* See if we have two bit tests of the same name in both tests.
485 : : In that case remove the outer test and change the inner one to
486 : : test for name & (bits1 | bits2) != 0. */
487 : 102531 : else if (recognize_bits_test (inner_cond, &name1, &bits1, !inner_inv)
488 : 102531 : && recognize_bits_test (outer_cond, &name2, &bits2, !outer_inv))
489 : : {
490 : 895 : gimple_stmt_iterator gsi;
491 : 895 : tree t;
492 : :
493 : 895 : if ((TREE_CODE (name1) == SSA_NAME
494 : 894 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name1))
495 : 1789 : || (TREE_CODE (name2) == SSA_NAME
496 : 894 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name2)))
497 : : return false;
498 : :
499 : : /* Find the common name which is bit-tested. */
500 : 895 : if (name1 == name2)
501 : : ;
502 : 484 : else if (bits1 == bits2)
503 : : {
504 : 77 : std::swap (name2, bits2);
505 : 77 : std::swap (name1, bits1);
506 : : }
507 : 407 : else if (name1 == bits2)
508 : 0 : std::swap (name2, bits2);
509 : 407 : else if (bits1 == name2)
510 : 0 : std::swap (name1, bits1);
511 : : else
512 : : return false;
513 : :
514 : : /* As we strip non-widening conversions in finding a common
515 : : name that is tested make sure to end up with an integral
516 : : type for building the bit operations. */
517 : 488 : if (TYPE_PRECISION (TREE_TYPE (bits1))
518 : 488 : >= TYPE_PRECISION (TREE_TYPE (bits2)))
519 : : {
520 : 488 : bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
521 : 488 : name1 = fold_convert (TREE_TYPE (bits1), name1);
522 : 488 : bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
523 : 488 : bits2 = fold_convert (TREE_TYPE (bits1), bits2);
524 : : }
525 : : else
526 : : {
527 : 0 : bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
528 : 0 : name1 = fold_convert (TREE_TYPE (bits2), name1);
529 : 0 : bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
530 : 0 : bits1 = fold_convert (TREE_TYPE (bits2), bits1);
531 : : }
532 : :
533 : : /* Do it. */
534 : 488 : gsi = gsi_for_stmt (inner_cond);
535 : 488 : t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
536 : 488 : t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
537 : : true, GSI_SAME_STMT);
538 : 488 : t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
539 : 488 : t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
540 : : true, GSI_SAME_STMT);
541 : 514 : t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR, boolean_type_node, t,
542 : : build_int_cst (TREE_TYPE (t), 0));
543 : 488 : t = canonicalize_cond_expr_cond (t);
544 : 488 : if (!t)
545 : : return false;
546 : 488 : if (!is_gimple_condexpr_for_cond (t))
547 : : {
548 : 0 : gsi = gsi_for_stmt (inner_cond);
549 : 0 : t = force_gimple_operand_gsi_1 (&gsi, t, is_gimple_condexpr_for_cond,
550 : : NULL, true, GSI_SAME_STMT);
551 : : }
552 : 488 : gimple_cond_set_condition_from_tree (inner_cond, t);
553 : 488 : update_stmt (inner_cond);
554 : :
555 : : /* Leave CFG optimization to cfg_cleanup. */
556 : 488 : gimple_cond_set_condition_from_tree (outer_cond,
557 : : outer_inv ? boolean_false_node : boolean_true_node);
558 : 488 : update_stmt (outer_cond);
559 : 488 : update_profile_after_ifcombine (inner_cond_bb, outer_cond_bb);
560 : :
561 : 488 : if (dump_file)
562 : : {
563 : 1 : fprintf (dump_file, "optimizing bits or bits test to ");
564 : 1 : print_generic_expr (dump_file, name1);
565 : 1 : fprintf (dump_file, " & T != 0\nwith temporary T = ");
566 : 1 : print_generic_expr (dump_file, bits1);
567 : 1 : fprintf (dump_file, " | ");
568 : 1 : print_generic_expr (dump_file, bits2);
569 : 1 : fprintf (dump_file, "\n");
570 : : }
571 : :
572 : 488 : return true;
573 : : }
574 : :
575 : : /* See if we have two comparisons that we can merge into one. */
576 : 101636 : else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
577 : 101636 : && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
578 : : {
579 : 101636 : tree t;
580 : 101636 : enum tree_code inner_cond_code = gimple_cond_code (inner_cond);
581 : 101636 : enum tree_code outer_cond_code = gimple_cond_code (outer_cond);
582 : :
583 : : /* Invert comparisons if necessary (and possible). */
584 : 101636 : if (inner_inv)
585 : 58707 : inner_cond_code = invert_tree_comparison (inner_cond_code,
586 : 58707 : HONOR_NANS (gimple_cond_lhs (inner_cond)));
587 : 101636 : if (inner_cond_code == ERROR_MARK)
588 : : return false;
589 : 101494 : if (outer_inv)
590 : 53588 : outer_cond_code = invert_tree_comparison (outer_cond_code,
591 : 53588 : HONOR_NANS (gimple_cond_lhs (outer_cond)));
592 : 101494 : if (outer_cond_code == ERROR_MARK)
593 : : return false;
594 : : /* Don't return false so fast, try maybe_fold_or_comparisons? */
595 : :
596 : 101234 : if (!(t = maybe_fold_and_comparisons (boolean_type_node, inner_cond_code,
597 : : gimple_cond_lhs (inner_cond),
598 : : gimple_cond_rhs (inner_cond),
599 : : outer_cond_code,
600 : : gimple_cond_lhs (outer_cond),
601 : : gimple_cond_rhs (outer_cond),
602 : : gimple_bb (outer_cond))))
603 : : {
604 : 97962 : tree t1, t2;
605 : 97962 : gimple_stmt_iterator gsi;
606 : 97962 : bool logical_op_non_short_circuit = LOGICAL_OP_NON_SHORT_CIRCUIT;
607 : 97962 : if (param_logical_op_non_short_circuit != -1)
608 : 139 : logical_op_non_short_circuit
609 : 139 : = param_logical_op_non_short_circuit;
610 : 97962 : if (!logical_op_non_short_circuit || sanitize_coverage_p ())
611 : 119 : return false;
612 : : /* Only do this optimization if the inner bb contains only the conditional. */
613 : 128720 : if (!gsi_one_before_end_p (gsi_start_nondebug_after_labels_bb (inner_cond_bb)))
614 : : return false;
615 : 67085 : t1 = fold_build2_loc (gimple_location (inner_cond),
616 : : inner_cond_code,
617 : : boolean_type_node,
618 : : gimple_cond_lhs (inner_cond),
619 : : gimple_cond_rhs (inner_cond));
620 : 67085 : t2 = fold_build2_loc (gimple_location (outer_cond),
621 : : outer_cond_code,
622 : : boolean_type_node,
623 : : gimple_cond_lhs (outer_cond),
624 : : gimple_cond_rhs (outer_cond));
625 : 67085 : t = fold_build2_loc (gimple_location (inner_cond),
626 : : TRUTH_AND_EXPR, boolean_type_node, t1, t2);
627 : 67085 : if (result_inv)
628 : : {
629 : 40690 : t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t);
630 : 40690 : result_inv = false;
631 : : }
632 : 67085 : gsi = gsi_for_stmt (inner_cond);
633 : 67085 : t = force_gimple_operand_gsi_1 (&gsi, t, is_gimple_condexpr_for_cond,
634 : : NULL, true, GSI_SAME_STMT);
635 : : }
636 : 70357 : if (result_inv)
637 : 2864 : t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t);
638 : 70357 : t = canonicalize_cond_expr_cond (t);
639 : 70357 : if (!t)
640 : : return false;
641 : 70357 : if (!is_gimple_condexpr_for_cond (t))
642 : : {
643 : 0 : gsi = gsi_for_stmt (inner_cond);
644 : 0 : t = force_gimple_operand_gsi_1 (&gsi, t, is_gimple_condexpr_for_cond,
645 : : NULL, true, GSI_SAME_STMT);
646 : : }
647 : 70357 : gimple_cond_set_condition_from_tree (inner_cond, t);
648 : 70357 : update_stmt (inner_cond);
649 : :
650 : : /* Leave CFG optimization to cfg_cleanup. */
651 : 70357 : gimple_cond_set_condition_from_tree (outer_cond,
652 : : outer_inv ? boolean_false_node : boolean_true_node);
653 : 70357 : update_stmt (outer_cond);
654 : 70357 : update_profile_after_ifcombine (inner_cond_bb, outer_cond_bb);
655 : :
656 : 70357 : if (dump_file)
657 : : {
658 : 3 : fprintf (dump_file, "optimizing two comparisons to ");
659 : 3 : print_generic_expr (dump_file, t);
660 : 3 : fprintf (dump_file, "\n");
661 : : }
662 : :
663 : 70357 : return true;
664 : : }
665 : :
666 : : return false;
667 : : }
668 : :
669 : : /* Helper function for tree_ssa_ifcombine_bb. Recognize a CFG pattern and
670 : : dispatch to the appropriate if-conversion helper for a particular
671 : : set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB.
672 : : PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB. */
673 : :
674 : : static bool
675 : 677150 : tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb,
676 : : basic_block then_bb, basic_block else_bb,
677 : : basic_block phi_pred_bb)
678 : : {
679 : : /* The && form is characterized by a common else_bb with
680 : : the two edges leading to it mergable. The latter is
681 : : guaranteed by matching PHI arguments in the else_bb and
682 : : the inner cond_bb having no side-effects. */
683 : 677150 : if (phi_pred_bb != else_bb
684 : 660217 : && recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
685 : 723219 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
686 : : {
687 : : /* We have
688 : : <outer_cond_bb>
689 : : if (q) goto inner_cond_bb; else goto else_bb;
690 : : <inner_cond_bb>
691 : : if (p) goto ...; else goto else_bb;
692 : : ...
693 : : <else_bb>
694 : : ...
695 : : */
696 : 39648 : return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, false,
697 : 39648 : false);
698 : : }
699 : :
700 : : /* And a version where the outer condition is negated. */
701 : 637502 : if (phi_pred_bb != else_bb
702 : 620569 : && recognize_if_then_else (outer_cond_bb, &else_bb, &inner_cond_bb)
703 : 649731 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
704 : : {
705 : : /* We have
706 : : <outer_cond_bb>
707 : : if (q) goto else_bb; else goto inner_cond_bb;
708 : : <inner_cond_bb>
709 : : if (p) goto ...; else goto else_bb;
710 : : ...
711 : : <else_bb>
712 : : ...
713 : : */
714 : 3341 : return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, true,
715 : 3341 : false);
716 : : }
717 : :
718 : : /* The || form is characterized by a common then_bb with the
719 : : two edges leading to it mergable. The latter is guaranteed
720 : : by matching PHI arguments in the then_bb and the inner cond_bb
721 : : having no side-effects. */
722 : 634161 : if (phi_pred_bb != then_bb
723 : 621203 : && recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
724 : 705361 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
725 : : {
726 : : /* We have
727 : : <outer_cond_bb>
728 : : if (q) goto then_bb; else goto inner_cond_bb;
729 : : <inner_cond_bb>
730 : : if (q) goto then_bb; else goto ...;
731 : : <then_bb>
732 : : ...
733 : : */
734 : 51176 : return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, true,
735 : 51176 : true);
736 : : }
737 : :
738 : : /* And a version where the outer condition is negated. */
739 : 582985 : if (phi_pred_bb != then_bb
740 : 570027 : && recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &then_bb)
741 : 596170 : && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
742 : : {
743 : : /* We have
744 : : <outer_cond_bb>
745 : : if (q) goto inner_cond_bb; else goto then_bb;
746 : : <inner_cond_bb>
747 : : if (q) goto then_bb; else goto ...;
748 : : <then_bb>
749 : : ...
750 : : */
751 : 8429 : return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false,
752 : 8429 : true);
753 : : }
754 : :
755 : : return false;
756 : : }
757 : :
758 : : /* Recognize a CFG pattern and dispatch to the appropriate
759 : : if-conversion helper. We start with BB as the innermost
760 : : worker basic-block. Returns true if a transformation was done. */
761 : :
762 : : static bool
763 : 3728624 : tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
764 : : {
765 : 3728624 : basic_block then_bb = NULL, else_bb = NULL;
766 : :
767 : 3728624 : if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
768 : : return false;
769 : :
770 : : /* Recognize && and || of two conditions with a common
771 : : then/else block which entry edges we can merge. That is:
772 : : if (a || b)
773 : : ;
774 : : and
775 : : if (a && b)
776 : : ;
777 : : This requires a single predecessor of the inner cond_bb. */
778 : 3728624 : if (single_pred_p (inner_cond_bb)
779 : 3728624 : && bb_no_side_effects_p (inner_cond_bb))
780 : : {
781 : 647099 : basic_block outer_cond_bb = single_pred (inner_cond_bb);
782 : :
783 : 647099 : if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb,
784 : : then_bb, else_bb, inner_cond_bb))
785 : : return true;
786 : :
787 : 576385 : if (forwarder_block_to (else_bb, then_bb))
788 : : {
789 : : /* Other possibilities for the && form, if else_bb is
790 : : empty forwarder block to then_bb. Compared to the above simpler
791 : : forms this can be treated as if then_bb and else_bb were swapped,
792 : : and the corresponding inner_cond_bb not inverted because of that.
793 : : For same_phi_args_p we look at equality of arguments between
794 : : edge from outer_cond_bb and the forwarder block. */
795 : 13118 : if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
796 : : then_bb, else_bb))
797 : : return true;
798 : : }
799 : 563267 : else if (forwarder_block_to (then_bb, else_bb))
800 : : {
801 : : /* Other possibilities for the || form, if then_bb is
802 : : empty forwarder block to else_bb. Compared to the above simpler
803 : : forms this can be treated as if then_bb and else_bb were swapped,
804 : : and the corresponding inner_cond_bb not inverted because of that.
805 : : For same_phi_args_p we look at equality of arguments between
806 : : edge from outer_cond_bb and the forwarder block. */
807 : 16933 : if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
808 : : then_bb, then_bb))
809 : : return true;
810 : : }
811 : : }
812 : :
813 : : return false;
814 : : }
815 : :
816 : : /* Main entry for the tree if-conversion pass. */
817 : :
818 : : namespace {
819 : :
820 : : const pass_data pass_data_tree_ifcombine =
821 : : {
822 : : GIMPLE_PASS, /* type */
823 : : "ifcombine", /* name */
824 : : OPTGROUP_NONE, /* optinfo_flags */
825 : : TV_TREE_IFCOMBINE, /* tv_id */
826 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
827 : : 0, /* properties_provided */
828 : : 0, /* properties_destroyed */
829 : : 0, /* todo_flags_start */
830 : : TODO_update_ssa, /* todo_flags_finish */
831 : : };
832 : :
833 : : class pass_tree_ifcombine : public gimple_opt_pass
834 : : {
835 : : public:
836 : 285617 : pass_tree_ifcombine (gcc::context *ctxt)
837 : 571234 : : gimple_opt_pass (pass_data_tree_ifcombine, ctxt)
838 : : {}
839 : :
840 : : /* opt_pass methods: */
841 : : unsigned int execute (function *) final override;
842 : :
843 : : }; // class pass_tree_ifcombine
844 : :
845 : : unsigned int
846 : 975510 : pass_tree_ifcombine::execute (function *fun)
847 : : {
848 : 975510 : basic_block *bbs;
849 : 975510 : bool cfg_changed = false;
850 : 975510 : int i;
851 : :
852 : 975510 : bbs = single_pred_before_succ_order ();
853 : 975510 : calculate_dominance_info (CDI_DOMINATORS);
854 : 975510 : mark_ssa_maybe_undefs ();
855 : :
856 : : /* Search every basic block for COND_EXPR we may be able to optimize.
857 : :
858 : : We walk the blocks in order that guarantees that a block with
859 : : a single predecessor is processed after the predecessor.
860 : : This ensures that we collapse outter ifs before visiting the
861 : : inner ones, and also that we do not try to visit a removed
862 : : block. This is opposite of PHI-OPT, because we cascade the
863 : : combining rather than cascading PHIs. */
864 : 10036605 : for (i = n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS - 1; i >= 0; i--)
865 : : {
866 : 9061095 : basic_block bb = bbs[i];
867 : :
868 : 21779906 : if (safe_is_a <gcond *> (*gsi_last_bb (bb)))
869 : 3728624 : if (tree_ssa_ifcombine_bb (bb))
870 : : {
871 : : /* Clear range info from all stmts in BB which is now executed
872 : : conditional on a always true/false condition. */
873 : 70908 : reset_flow_sensitive_info_in_bb (bb);
874 : 408002 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
875 : 266186 : gsi_next (&gsi))
876 : : {
877 : 266186 : gassign *ass = dyn_cast <gassign *> (gsi_stmt (gsi));
878 : 266186 : if (!ass)
879 : 95573 : continue;
880 : 170613 : tree lhs = gimple_assign_lhs (ass);
881 : 340789 : if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
882 : 0 : || POINTER_TYPE_P (TREE_TYPE (lhs)))
883 : 341226 : && arith_code_with_undefined_signed_overflow
884 : 170613 : (gimple_assign_rhs_code (ass)))
885 : 3736 : rewrite_to_defined_overflow (&gsi);
886 : : }
887 : 70908 : cfg_changed |= true;
888 : : }
889 : : }
890 : :
891 : 975510 : free (bbs);
892 : :
893 : 975510 : return cfg_changed ? TODO_cleanup_cfg : 0;
894 : : }
895 : :
896 : : } // anon namespace
897 : :
898 : : gimple_opt_pass *
899 : 285617 : make_pass_tree_ifcombine (gcc::context *ctxt)
900 : : {
901 : 285617 : return new pass_tree_ifcombine (ctxt);
902 : : }
|