]>
Commit | Line | Data |
---|---|---|
8530c7be | 1 | /* Combining of if-expressions on trees. |
711789cc | 2 | Copyright (C) 2007-2013 Free Software Foundation, Inc. |
8530c7be | 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 | |
8c4c00c1 | 9 | the Free Software Foundation; either version 3, or (at your option) |
8530c7be | 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 | |
8c4c00c1 | 18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
8530c7be | 20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
b4c65f30 | 25 | /* rtl is needed only because arm back-end requires it for |
26 | BRANCH_COST. */ | |
27 | #include "rtl.h" | |
28 | #include "tm_p.h" | |
8530c7be | 29 | #include "tree.h" |
9ed99284 | 30 | #include "stor-layout.h" |
8530c7be | 31 | #include "basic-block.h" |
ce084dfc | 32 | #include "tree-pretty-print.h" |
e795d6e1 | 33 | #include "gimple.h" |
dcf1a1ec | 34 | #include "gimple-iterator.h" |
e795d6e1 | 35 | #include "gimplify-me.h" |
073c1fd5 | 36 | #include "gimple-ssa.h" |
37 | #include "tree-cfg.h" | |
38 | #include "tree-phinodes.h" | |
39 | #include "ssa-iterators.h" | |
8530c7be | 40 | #include "tree-pass.h" |
8530c7be | 41 | |
b4c65f30 | 42 | #ifndef LOGICAL_OP_NON_SHORT_CIRCUIT |
43 | #define LOGICAL_OP_NON_SHORT_CIRCUIT \ | |
44 | (BRANCH_COST (optimize_function_for_speed_p (cfun), \ | |
45 | false) >= 2) | |
46 | #endif | |
47 | ||
8530c7be | 48 | /* This pass combines COND_EXPRs to simplify control flow. It |
49 | currently recognizes bit tests and comparisons in chains that | |
50 | represent logical and or logical or of two COND_EXPRs. | |
51 | ||
52 | It does so by walking basic blocks in a approximate reverse | |
53 | post-dominator order and trying to match CFG patterns that | |
54 | represent logical and or logical or of two COND_EXPRs. | |
55 | Transformations are done if the COND_EXPR conditions match | |
56 | either | |
57 | ||
58 | 1. two single bit tests X & (1 << Yn) (for logical and) | |
59 | ||
60 | 2. two bit tests X & Yn (for logical or) | |
61 | ||
62 | 3. two comparisons X OPn Y (for logical or) | |
63 | ||
64 | To simplify this pass, removing basic blocks and dead code | |
65 | is left to CFG cleanup and DCE. */ | |
66 | ||
67 | ||
68 | /* Recognize a if-then-else CFG pattern starting to match with the | |
69 | COND_BB basic-block containing the COND_EXPR. The recognized | |
70 | then end else blocks are stored to *THEN_BB and *ELSE_BB. If | |
71 | *THEN_BB and/or *ELSE_BB are already set, they are required to | |
72 | match the then and else basic-blocks to make the pattern match. | |
73 | Returns true if the pattern matched, false otherwise. */ | |
74 | ||
75 | static bool | |
76 | recognize_if_then_else (basic_block cond_bb, | |
77 | basic_block *then_bb, basic_block *else_bb) | |
78 | { | |
79 | edge t, e; | |
80 | ||
81 | if (EDGE_COUNT (cond_bb->succs) != 2) | |
82 | return false; | |
83 | ||
84 | /* Find the then/else edges. */ | |
85 | t = EDGE_SUCC (cond_bb, 0); | |
86 | e = EDGE_SUCC (cond_bb, 1); | |
87 | if (!(t->flags & EDGE_TRUE_VALUE)) | |
88 | { | |
89 | edge tmp = t; | |
90 | t = e; | |
91 | e = tmp; | |
92 | } | |
93 | if (!(t->flags & EDGE_TRUE_VALUE) | |
94 | || !(e->flags & EDGE_FALSE_VALUE)) | |
95 | return false; | |
96 | ||
97 | /* Check if the edge destinations point to the required block. */ | |
98 | if (*then_bb | |
99 | && t->dest != *then_bb) | |
100 | return false; | |
101 | if (*else_bb | |
102 | && e->dest != *else_bb) | |
103 | return false; | |
104 | ||
105 | if (!*then_bb) | |
106 | *then_bb = t->dest; | |
107 | if (!*else_bb) | |
108 | *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 | bb_no_side_effects_p (basic_block bb) | |
118 | { | |
75a70cf9 | 119 | gimple_stmt_iterator gsi; |
8530c7be | 120 | |
75a70cf9 | 121 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
8530c7be | 122 | { |
75a70cf9 | 123 | gimple stmt = gsi_stmt (gsi); |
8530c7be | 124 | |
b523dd6d | 125 | if (gimple_has_side_effects (stmt) |
dd277d48 | 126 | || gimple_vuse (stmt)) |
8530c7be | 127 | return false; |
128 | } | |
129 | ||
130 | return true; | |
131 | } | |
132 | ||
133 | /* Verify if all PHI node arguments in DEST for edges from BB1 or | |
134 | BB2 to DEST are the same. This makes the CFG merge point | |
135 | free from side-effects. Return true in this case, else false. */ | |
136 | ||
137 | static bool | |
138 | same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest) | |
139 | { | |
140 | edge e1 = find_edge (bb1, dest); | |
141 | edge e2 = find_edge (bb2, dest); | |
75a70cf9 | 142 | gimple_stmt_iterator gsi; |
143 | gimple phi; | |
8530c7be | 144 | |
75a70cf9 | 145 | for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi)) |
146 | { | |
147 | phi = gsi_stmt (gsi); | |
148 | if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1), | |
149 | PHI_ARG_DEF_FROM_EDGE (phi, e2), 0)) | |
150 | return false; | |
151 | } | |
8530c7be | 152 | |
153 | return true; | |
154 | } | |
155 | ||
c9686d06 | 156 | /* Return the best representative SSA name for CANDIDATE which is used |
157 | in a bit test. */ | |
158 | ||
159 | static tree | |
160 | get_name_for_bit_test (tree candidate) | |
161 | { | |
162 | /* Skip single-use names in favor of using the name from a | |
163 | non-widening conversion definition. */ | |
164 | if (TREE_CODE (candidate) == SSA_NAME | |
165 | && has_single_use (candidate)) | |
166 | { | |
75a70cf9 | 167 | gimple def_stmt = SSA_NAME_DEF_STMT (candidate); |
168 | if (is_gimple_assign (def_stmt) | |
854e8953 | 169 | && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))) |
c9686d06 | 170 | { |
75a70cf9 | 171 | if (TYPE_PRECISION (TREE_TYPE (candidate)) |
172 | <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt)))) | |
173 | return gimple_assign_rhs1 (def_stmt); | |
c9686d06 | 174 | } |
175 | } | |
176 | ||
177 | return candidate; | |
178 | } | |
179 | ||
75a70cf9 | 180 | /* Recognize a single bit test pattern in GIMPLE_COND and its defining |
8530c7be | 181 | statements. Store the name being tested in *NAME and the bit |
75a70cf9 | 182 | in *BIT. The GIMPLE_COND computes *NAME & (1 << *BIT). |
8530c7be | 183 | Returns true if the pattern matched, false otherwise. */ |
184 | ||
185 | static bool | |
6e6b952b | 186 | recognize_single_bit_test (gimple cond, tree *name, tree *bit, bool inv) |
8530c7be | 187 | { |
75a70cf9 | 188 | gimple stmt; |
8530c7be | 189 | |
190 | /* Get at the definition of the result of the bit test. */ | |
6e6b952b | 191 | if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR) |
75a70cf9 | 192 | || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME |
193 | || !integer_zerop (gimple_cond_rhs (cond))) | |
8530c7be | 194 | return false; |
75a70cf9 | 195 | stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond)); |
196 | if (!is_gimple_assign (stmt)) | |
8530c7be | 197 | return false; |
8530c7be | 198 | |
199 | /* Look at which bit is tested. One form to recognize is | |
200 | D.1985_5 = state_3(D) >> control1_4(D); | |
201 | D.1986_6 = (int) D.1985_5; | |
202 | D.1987_7 = op0 & 1; | |
203 | if (D.1987_7 != 0) */ | |
75a70cf9 | 204 | if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR |
205 | && integer_onep (gimple_assign_rhs2 (stmt)) | |
206 | && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME) | |
8530c7be | 207 | { |
75a70cf9 | 208 | tree orig_name = gimple_assign_rhs1 (stmt); |
d9022390 | 209 | |
210 | /* Look through copies and conversions to eventually | |
211 | find the stmt that computes the shift. */ | |
75a70cf9 | 212 | stmt = SSA_NAME_DEF_STMT (orig_name); |
213 | ||
214 | while (is_gimple_assign (stmt) | |
854e8953 | 215 | && ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt)) |
216 | && (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt))) | |
217 | <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt))))) | |
218 | || gimple_assign_ssa_name_copy_p (stmt))) | |
219 | stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt)); | |
8530c7be | 220 | |
d9022390 | 221 | /* If we found such, decompose it. */ |
75a70cf9 | 222 | if (is_gimple_assign (stmt) |
223 | && gimple_assign_rhs_code (stmt) == RSHIFT_EXPR) | |
8530c7be | 224 | { |
225 | /* op0 & (1 << op1) */ | |
75a70cf9 | 226 | *bit = gimple_assign_rhs2 (stmt); |
227 | *name = gimple_assign_rhs1 (stmt); | |
8530c7be | 228 | } |
229 | else | |
230 | { | |
231 | /* t & 1 */ | |
d9022390 | 232 | *bit = integer_zero_node; |
c9686d06 | 233 | *name = get_name_for_bit_test (orig_name); |
8530c7be | 234 | } |
235 | ||
236 | return true; | |
237 | } | |
238 | ||
239 | /* Another form is | |
240 | D.1987_7 = op0 & (1 << CST) | |
241 | if (D.1987_7 != 0) */ | |
75a70cf9 | 242 | if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR |
243 | && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME | |
244 | && integer_pow2p (gimple_assign_rhs2 (stmt))) | |
8530c7be | 245 | { |
75a70cf9 | 246 | *name = gimple_assign_rhs1 (stmt); |
8530c7be | 247 | *bit = build_int_cst (integer_type_node, |
75a70cf9 | 248 | tree_log2 (gimple_assign_rhs2 (stmt))); |
8530c7be | 249 | return true; |
250 | } | |
251 | ||
252 | /* Another form is | |
253 | D.1986_6 = 1 << control1_4(D) | |
254 | D.1987_7 = op0 & D.1986_6 | |
255 | if (D.1987_7 != 0) */ | |
75a70cf9 | 256 | if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR |
257 | && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME | |
258 | && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME) | |
8530c7be | 259 | { |
75a70cf9 | 260 | gimple tmp; |
8530c7be | 261 | |
262 | /* Both arguments of the BIT_AND_EXPR can be the single-bit | |
263 | specifying expression. */ | |
75a70cf9 | 264 | tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt)); |
265 | if (is_gimple_assign (tmp) | |
266 | && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR | |
267 | && integer_onep (gimple_assign_rhs1 (tmp))) | |
8530c7be | 268 | { |
75a70cf9 | 269 | *name = gimple_assign_rhs2 (stmt); |
270 | *bit = gimple_assign_rhs2 (tmp); | |
8530c7be | 271 | return true; |
272 | } | |
273 | ||
75a70cf9 | 274 | tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt)); |
275 | if (is_gimple_assign (tmp) | |
276 | && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR | |
277 | && integer_onep (gimple_assign_rhs1 (tmp))) | |
8530c7be | 278 | { |
75a70cf9 | 279 | *name = gimple_assign_rhs1 (stmt); |
280 | *bit = gimple_assign_rhs2 (tmp); | |
8530c7be | 281 | return true; |
282 | } | |
283 | } | |
284 | ||
285 | return false; | |
286 | } | |
287 | ||
75a70cf9 | 288 | /* Recognize a bit test pattern in a GIMPLE_COND and its defining |
8530c7be | 289 | statements. Store the name being tested in *NAME and the bits |
290 | in *BITS. The COND_EXPR computes *NAME & *BITS. | |
291 | Returns true if the pattern matched, false otherwise. */ | |
292 | ||
293 | static bool | |
6e6b952b | 294 | recognize_bits_test (gimple cond, tree *name, tree *bits, bool inv) |
8530c7be | 295 | { |
75a70cf9 | 296 | gimple stmt; |
8530c7be | 297 | |
298 | /* Get at the definition of the result of the bit test. */ | |
6e6b952b | 299 | if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR) |
75a70cf9 | 300 | || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME |
301 | || !integer_zerop (gimple_cond_rhs (cond))) | |
8530c7be | 302 | return false; |
75a70cf9 | 303 | stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond)); |
304 | if (!is_gimple_assign (stmt) | |
305 | || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR) | |
8530c7be | 306 | return false; |
307 | ||
75a70cf9 | 308 | *name = get_name_for_bit_test (gimple_assign_rhs1 (stmt)); |
309 | *bits = gimple_assign_rhs2 (stmt); | |
8530c7be | 310 | |
311 | return true; | |
312 | } | |
313 | ||
314 | /* If-convert on a and pattern with a common else block. The inner | |
315 | if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB. | |
6e6b952b | 316 | inner_inv, outer_inv and result_inv indicate whether the conditions |
317 | are inverted. | |
8530c7be | 318 | Returns true if the edges to the common else basic-block were merged. */ |
319 | ||
320 | static bool | |
6e6b952b | 321 | ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv, |
322 | basic_block outer_cond_bb, bool outer_inv, bool result_inv) | |
8530c7be | 323 | { |
75a70cf9 | 324 | gimple_stmt_iterator gsi; |
325 | gimple inner_cond, outer_cond; | |
6e6b952b | 326 | tree name1, name2, bit1, bit2, bits1, bits2; |
8530c7be | 327 | |
328 | inner_cond = last_stmt (inner_cond_bb); | |
329 | if (!inner_cond | |
75a70cf9 | 330 | || gimple_code (inner_cond) != GIMPLE_COND) |
8530c7be | 331 | return false; |
332 | ||
333 | outer_cond = last_stmt (outer_cond_bb); | |
334 | if (!outer_cond | |
75a70cf9 | 335 | || gimple_code (outer_cond) != GIMPLE_COND) |
8530c7be | 336 | return false; |
337 | ||
338 | /* See if we test a single bit of the same name in both tests. In | |
339 | that case remove the outer test, merging both else edges, | |
340 | and change the inner one to test for | |
341 | name & (bit1 | bit2) == (bit1 | bit2). */ | |
6e6b952b | 342 | if (recognize_single_bit_test (inner_cond, &name1, &bit1, inner_inv) |
343 | && recognize_single_bit_test (outer_cond, &name2, &bit2, outer_inv) | |
8530c7be | 344 | && name1 == name2) |
345 | { | |
346 | tree t, t2; | |
347 | ||
348 | /* Do it. */ | |
75a70cf9 | 349 | gsi = gsi_for_stmt (inner_cond); |
8530c7be | 350 | t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1), |
9289fc25 | 351 | build_int_cst (TREE_TYPE (name1), 1), bit1); |
8530c7be | 352 | t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1), |
9289fc25 | 353 | build_int_cst (TREE_TYPE (name1), 1), bit2); |
8530c7be | 354 | t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2); |
75a70cf9 | 355 | t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, |
356 | true, GSI_SAME_STMT); | |
8530c7be | 357 | t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t); |
75a70cf9 | 358 | t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE, |
359 | true, GSI_SAME_STMT); | |
6e6b952b | 360 | t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR, |
361 | boolean_type_node, t2, t); | |
b611dd5f | 362 | t = canonicalize_cond_expr_cond (t); |
363 | if (!t) | |
364 | return false; | |
75a70cf9 | 365 | gimple_cond_set_condition_from_tree (inner_cond, t); |
8530c7be | 366 | update_stmt (inner_cond); |
367 | ||
368 | /* Leave CFG optimization to cfg_cleanup. */ | |
6e6b952b | 369 | gimple_cond_set_condition_from_tree (outer_cond, |
370 | outer_inv ? boolean_false_node : boolean_true_node); | |
8530c7be | 371 | update_stmt (outer_cond); |
372 | ||
373 | if (dump_file) | |
374 | { | |
375 | fprintf (dump_file, "optimizing double bit test to "); | |
376 | print_generic_expr (dump_file, name1, 0); | |
377 | fprintf (dump_file, " & T == T\nwith temporary T = (1 << "); | |
378 | print_generic_expr (dump_file, bit1, 0); | |
379 | fprintf (dump_file, ") | (1 << "); | |
380 | print_generic_expr (dump_file, bit2, 0); | |
381 | fprintf (dump_file, ")\n"); | |
382 | } | |
383 | ||
384 | return true; | |
385 | } | |
386 | ||
8530c7be | 387 | /* See if we have two bit tests of the same name in both tests. |
388 | In that case remove the outer test and change the inner one to | |
389 | test for name & (bits1 | bits2) != 0. */ | |
6e6b952b | 390 | else if (recognize_bits_test (inner_cond, &name1, &bits1, !inner_inv) |
391 | && recognize_bits_test (outer_cond, &name2, &bits2, !outer_inv)) | |
8530c7be | 392 | { |
75a70cf9 | 393 | gimple_stmt_iterator gsi; |
8530c7be | 394 | tree t; |
395 | ||
396 | /* Find the common name which is bit-tested. */ | |
397 | if (name1 == name2) | |
398 | ; | |
399 | else if (bits1 == bits2) | |
400 | { | |
401 | t = name2; | |
402 | name2 = bits2; | |
403 | bits2 = t; | |
404 | t = name1; | |
405 | name1 = bits1; | |
406 | bits1 = t; | |
407 | } | |
408 | else if (name1 == bits2) | |
409 | { | |
410 | t = name2; | |
411 | name2 = bits2; | |
412 | bits2 = t; | |
413 | } | |
414 | else if (bits1 == name2) | |
415 | { | |
416 | t = name1; | |
417 | name1 = bits1; | |
418 | bits1 = t; | |
419 | } | |
420 | else | |
421 | return false; | |
422 | ||
2a8d660d | 423 | /* As we strip non-widening conversions in finding a common |
424 | name that is tested make sure to end up with an integral | |
425 | type for building the bit operations. */ | |
426 | if (TYPE_PRECISION (TREE_TYPE (bits1)) | |
427 | >= TYPE_PRECISION (TREE_TYPE (bits2))) | |
428 | { | |
429 | bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1); | |
430 | name1 = fold_convert (TREE_TYPE (bits1), name1); | |
431 | bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2); | |
432 | bits2 = fold_convert (TREE_TYPE (bits1), bits2); | |
433 | } | |
434 | else | |
435 | { | |
436 | bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2); | |
437 | name1 = fold_convert (TREE_TYPE (bits2), name1); | |
438 | bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1); | |
439 | bits1 = fold_convert (TREE_TYPE (bits2), bits1); | |
440 | } | |
441 | ||
8530c7be | 442 | /* Do it. */ |
75a70cf9 | 443 | gsi = gsi_for_stmt (inner_cond); |
8530c7be | 444 | t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2); |
75a70cf9 | 445 | t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, |
446 | true, GSI_SAME_STMT); | |
8530c7be | 447 | t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t); |
75a70cf9 | 448 | t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, |
449 | true, GSI_SAME_STMT); | |
6e6b952b | 450 | t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR, boolean_type_node, t, |
75a70cf9 | 451 | build_int_cst (TREE_TYPE (t), 0)); |
b611dd5f | 452 | t = canonicalize_cond_expr_cond (t); |
453 | if (!t) | |
454 | return false; | |
75a70cf9 | 455 | gimple_cond_set_condition_from_tree (inner_cond, t); |
8530c7be | 456 | update_stmt (inner_cond); |
457 | ||
458 | /* Leave CFG optimization to cfg_cleanup. */ | |
6e6b952b | 459 | gimple_cond_set_condition_from_tree (outer_cond, |
460 | outer_inv ? boolean_false_node : boolean_true_node); | |
8530c7be | 461 | update_stmt (outer_cond); |
462 | ||
463 | if (dump_file) | |
464 | { | |
465 | fprintf (dump_file, "optimizing bits or bits test to "); | |
466 | print_generic_expr (dump_file, name1, 0); | |
467 | fprintf (dump_file, " & T != 0\nwith temporary T = "); | |
468 | print_generic_expr (dump_file, bits1, 0); | |
469 | fprintf (dump_file, " | "); | |
470 | print_generic_expr (dump_file, bits2, 0); | |
471 | fprintf (dump_file, "\n"); | |
472 | } | |
473 | ||
474 | return true; | |
475 | } | |
476 | ||
6e6b952b | 477 | /* See if we have two comparisons that we can merge into one. */ |
478 | else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison | |
c82d157a | 479 | && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison) |
8530c7be | 480 | { |
8530c7be | 481 | tree t; |
6e6b952b | 482 | enum tree_code inner_cond_code = gimple_cond_code (inner_cond); |
483 | enum tree_code outer_cond_code = gimple_cond_code (outer_cond); | |
484 | ||
485 | /* Invert comparisons if necessary (and possible). */ | |
486 | if (inner_inv) | |
487 | inner_cond_code = invert_tree_comparison (inner_cond_code, | |
488 | HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (inner_cond))))); | |
489 | if (inner_cond_code == ERROR_MARK) | |
490 | return false; | |
491 | if (outer_inv) | |
492 | outer_cond_code = invert_tree_comparison (outer_cond_code, | |
493 | HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (outer_cond))))); | |
494 | if (outer_cond_code == ERROR_MARK) | |
495 | return false; | |
496 | /* Don't return false so fast, try maybe_fold_or_comparisons? */ | |
8530c7be | 497 | |
6e6b952b | 498 | if (!(t = maybe_fold_and_comparisons (inner_cond_code, |
499 | gimple_cond_lhs (inner_cond), | |
500 | gimple_cond_rhs (inner_cond), | |
501 | outer_cond_code, | |
502 | gimple_cond_lhs (outer_cond), | |
503 | gimple_cond_rhs (outer_cond)))) | |
b4c65f30 | 504 | { |
505 | tree t1, t2; | |
506 | gimple_stmt_iterator gsi; | |
507 | if (!LOGICAL_OP_NON_SHORT_CIRCUIT) | |
508 | return false; | |
509 | /* Only do this optimization if the inner bb contains only the conditional. */ | |
510 | if (!gsi_one_before_end_p (gsi_start_nondebug_after_labels_bb (inner_cond_bb))) | |
511 | return false; | |
512 | t1 = fold_build2_loc (gimple_location (inner_cond), | |
513 | inner_cond_code, | |
514 | boolean_type_node, | |
515 | gimple_cond_lhs (inner_cond), | |
516 | gimple_cond_rhs (inner_cond)); | |
517 | t2 = fold_build2_loc (gimple_location (outer_cond), | |
518 | outer_cond_code, | |
519 | boolean_type_node, | |
520 | gimple_cond_lhs (outer_cond), | |
521 | gimple_cond_rhs (outer_cond)); | |
522 | t = fold_build2_loc (gimple_location (inner_cond), | |
523 | TRUTH_AND_EXPR, boolean_type_node, t1, t2); | |
524 | if (result_inv) | |
525 | { | |
526 | t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t); | |
527 | result_inv = false; | |
528 | } | |
529 | gsi = gsi_for_stmt (inner_cond); | |
530 | t = force_gimple_operand_gsi_1 (&gsi, t, is_gimple_condexpr, NULL, true, | |
531 | GSI_SAME_STMT); | |
532 | } | |
6e6b952b | 533 | if (result_inv) |
534 | t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t); | |
a7392604 | 535 | t = canonicalize_cond_expr_cond (t); |
536 | if (!t) | |
537 | return false; | |
75a70cf9 | 538 | gimple_cond_set_condition_from_tree (inner_cond, t); |
8530c7be | 539 | update_stmt (inner_cond); |
540 | ||
541 | /* Leave CFG optimization to cfg_cleanup. */ | |
6e6b952b | 542 | gimple_cond_set_condition_from_tree (outer_cond, |
543 | outer_inv ? boolean_false_node : boolean_true_node); | |
8530c7be | 544 | update_stmt (outer_cond); |
545 | ||
546 | if (dump_file) | |
547 | { | |
548 | fprintf (dump_file, "optimizing two comparisons to "); | |
549 | print_generic_expr (dump_file, t, 0); | |
550 | fprintf (dump_file, "\n"); | |
551 | } | |
552 | ||
553 | return true; | |
554 | } | |
555 | ||
556 | return false; | |
557 | } | |
558 | ||
559 | /* Recognize a CFG pattern and dispatch to the appropriate | |
560 | if-conversion helper. We start with BB as the innermost | |
561 | worker basic-block. Returns true if a transformation was done. */ | |
562 | ||
563 | static bool | |
564 | tree_ssa_ifcombine_bb (basic_block inner_cond_bb) | |
565 | { | |
566 | basic_block then_bb = NULL, else_bb = NULL; | |
567 | ||
568 | if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb)) | |
569 | return false; | |
570 | ||
571 | /* Recognize && and || of two conditions with a common | |
572 | then/else block which entry edges we can merge. That is: | |
573 | if (a || b) | |
574 | ; | |
575 | and | |
576 | if (a && b) | |
577 | ; | |
578 | This requires a single predecessor of the inner cond_bb. */ | |
579 | if (single_pred_p (inner_cond_bb)) | |
580 | { | |
581 | basic_block outer_cond_bb = single_pred (inner_cond_bb); | |
582 | ||
583 | /* The && form is characterized by a common else_bb with | |
584 | the two edges leading to it mergable. The latter is | |
585 | guaranteed by matching PHI arguments in the else_bb and | |
586 | the inner cond_bb having no side-effects. */ | |
587 | if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb) | |
588 | && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb) | |
589 | && bb_no_side_effects_p (inner_cond_bb)) | |
590 | { | |
591 | /* We have | |
592 | <outer_cond_bb> | |
593 | if (q) goto inner_cond_bb; else goto else_bb; | |
594 | <inner_cond_bb> | |
595 | if (p) goto ...; else goto else_bb; | |
596 | ... | |
597 | <else_bb> | |
598 | ... | |
599 | */ | |
6e6b952b | 600 | return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, false, |
601 | false); | |
602 | } | |
603 | ||
604 | /* And a version where the outer condition is negated. */ | |
605 | if (recognize_if_then_else (outer_cond_bb, &else_bb, &inner_cond_bb) | |
606 | && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb) | |
607 | && bb_no_side_effects_p (inner_cond_bb)) | |
608 | { | |
609 | /* We have | |
610 | <outer_cond_bb> | |
611 | if (q) goto else_bb; else goto inner_cond_bb; | |
612 | <inner_cond_bb> | |
613 | if (p) goto ...; else goto else_bb; | |
614 | ... | |
615 | <else_bb> | |
616 | ... | |
617 | */ | |
618 | return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, true, | |
619 | false); | |
8530c7be | 620 | } |
621 | ||
622 | /* The || form is characterized by a common then_bb with the | |
623 | two edges leading to it mergable. The latter is guaranteed | |
624 | by matching PHI arguments in the then_bb and the inner cond_bb | |
625 | having no side-effects. */ | |
626 | if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb) | |
627 | && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb) | |
628 | && bb_no_side_effects_p (inner_cond_bb)) | |
629 | { | |
630 | /* We have | |
631 | <outer_cond_bb> | |
632 | if (q) goto then_bb; else goto inner_cond_bb; | |
633 | <inner_cond_bb> | |
634 | if (q) goto then_bb; else goto ...; | |
635 | <then_bb> | |
636 | ... | |
637 | */ | |
6e6b952b | 638 | return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, true, |
639 | true); | |
640 | } | |
641 | ||
642 | /* And a version where the outer condition is negated. */ | |
643 | if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &then_bb) | |
644 | && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb) | |
645 | && bb_no_side_effects_p (inner_cond_bb)) | |
646 | { | |
647 | /* We have | |
648 | <outer_cond_bb> | |
649 | if (q) goto inner_cond_bb; else goto then_bb; | |
650 | <inner_cond_bb> | |
651 | if (q) goto then_bb; else goto ...; | |
652 | <then_bb> | |
653 | ... | |
654 | */ | |
655 | return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false, | |
656 | true); | |
8530c7be | 657 | } |
658 | } | |
659 | ||
660 | return false; | |
661 | } | |
662 | ||
663 | /* Main entry for the tree if-conversion pass. */ | |
664 | ||
665 | static unsigned int | |
666 | tree_ssa_ifcombine (void) | |
667 | { | |
668 | basic_block *bbs; | |
669 | bool cfg_changed = false; | |
670 | int i; | |
671 | ||
ba4d2b2f | 672 | bbs = single_pred_before_succ_order (); |
8a245b9d | 673 | calculate_dominance_info (CDI_DOMINATORS); |
8530c7be | 674 | |
b4c65f30 | 675 | /* Search every basic block for COND_EXPR we may be able to optimize. |
676 | ||
677 | We walk the blocks in order that guarantees that a block with | |
678 | a single predecessor is processed after the predecessor. | |
679 | This ensures that we collapse outter ifs before visiting the | |
680 | inner ones, and also that we do not try to visit a removed | |
681 | block. This is opposite of PHI-OPT, because we cascade the | |
682 | combining rather than cascading PHIs. */ | |
a28770e1 | 683 | for (i = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS - 1; i >= 0; i--) |
8530c7be | 684 | { |
685 | basic_block bb = bbs[i]; | |
75a70cf9 | 686 | gimple stmt = last_stmt (bb); |
8530c7be | 687 | |
688 | if (stmt | |
75a70cf9 | 689 | && gimple_code (stmt) == GIMPLE_COND) |
8530c7be | 690 | cfg_changed |= tree_ssa_ifcombine_bb (bb); |
691 | } | |
692 | ||
693 | free (bbs); | |
694 | ||
695 | return cfg_changed ? TODO_cleanup_cfg : 0; | |
696 | } | |
697 | ||
698 | static bool | |
699 | gate_ifcombine (void) | |
700 | { | |
701 | return 1; | |
702 | } | |
703 | ||
cbe8bda8 | 704 | namespace { |
705 | ||
706 | const pass_data pass_data_tree_ifcombine = | |
20099e35 | 707 | { |
cbe8bda8 | 708 | GIMPLE_PASS, /* type */ |
709 | "ifcombine", /* name */ | |
710 | OPTGROUP_NONE, /* optinfo_flags */ | |
711 | true, /* has_gate */ | |
712 | true, /* has_execute */ | |
713 | TV_TREE_IFCOMBINE, /* tv_id */ | |
714 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
715 | 0, /* properties_provided */ | |
716 | 0, /* properties_destroyed */ | |
717 | 0, /* todo_flags_start */ | |
718 | ( TODO_update_ssa | TODO_verify_ssa ), /* todo_flags_finish */ | |
8530c7be | 719 | }; |
cbe8bda8 | 720 | |
721 | class pass_tree_ifcombine : public gimple_opt_pass | |
722 | { | |
723 | public: | |
9af5ce0c | 724 | pass_tree_ifcombine (gcc::context *ctxt) |
725 | : gimple_opt_pass (pass_data_tree_ifcombine, ctxt) | |
cbe8bda8 | 726 | {} |
727 | ||
728 | /* opt_pass methods: */ | |
729 | bool gate () { return gate_ifcombine (); } | |
730 | unsigned int execute () { return tree_ssa_ifcombine (); } | |
731 | ||
732 | }; // class pass_tree_ifcombine | |
733 | ||
734 | } // anon namespace | |
735 | ||
736 | gimple_opt_pass * | |
737 | make_pass_tree_ifcombine (gcc::context *ctxt) | |
738 | { | |
739 | return new pass_tree_ifcombine (ctxt); | |
740 | } |