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