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