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