|
0
|
1 /* Combining of if-expressions on trees.
|
|
|
2 Copyright (C) 2007, 2008 Free Software Foundation, Inc.
|
|
|
3 Contributed by Richard Guenther <rguenther@suse.de>
|
|
|
4
|
|
|
5 This file is part of GCC.
|
|
|
6
|
|
|
7 GCC is free software; you can redistribute it and/or modify
|
|
|
8 it under the terms of the GNU General Public License as published by
|
|
|
9 the Free Software Foundation; either version 3, or (at your option)
|
|
|
10 any later version.
|
|
|
11
|
|
|
12 GCC is distributed in the hope that it will be useful,
|
|
|
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
15 GNU General Public License for more details.
|
|
|
16
|
|
|
17 You should have received a copy of the GNU General Public License
|
|
|
18 along with GCC; see the file COPYING3. If not see
|
|
|
19 <http://www.gnu.org/licenses/>. */
|
|
|
20
|
|
|
21 #include "config.h"
|
|
|
22 #include "system.h"
|
|
|
23 #include "coretypes.h"
|
|
|
24 #include "tm.h"
|
|
|
25 #include "tree.h"
|
|
|
26 #include "basic-block.h"
|
|
|
27 #include "timevar.h"
|
|
|
28 #include "diagnostic.h"
|
|
|
29 #include "tree-flow.h"
|
|
|
30 #include "tree-pass.h"
|
|
|
31 #include "tree-dump.h"
|
|
|
32
|
|
|
33 /* This pass combines COND_EXPRs to simplify control flow. It
|
|
|
34 currently recognizes bit tests and comparisons in chains that
|
|
|
35 represent logical and or logical or of two COND_EXPRs.
|
|
|
36
|
|
|
37 It does so by walking basic blocks in a approximate reverse
|
|
|
38 post-dominator order and trying to match CFG patterns that
|
|
|
39 represent logical and or logical or of two COND_EXPRs.
|
|
|
40 Transformations are done if the COND_EXPR conditions match
|
|
|
41 either
|
|
|
42
|
|
|
43 1. two single bit tests X & (1 << Yn) (for logical and)
|
|
|
44
|
|
|
45 2. two bit tests X & Yn (for logical or)
|
|
|
46
|
|
|
47 3. two comparisons X OPn Y (for logical or)
|
|
|
48
|
|
|
49 To simplify this pass, removing basic blocks and dead code
|
|
|
50 is left to CFG cleanup and DCE. */
|
|
|
51
|
|
|
52
|
|
|
53 /* Recognize a if-then-else CFG pattern starting to match with the
|
|
|
54 COND_BB basic-block containing the COND_EXPR. The recognized
|
|
|
55 then end else blocks are stored to *THEN_BB and *ELSE_BB. If
|
|
|
56 *THEN_BB and/or *ELSE_BB are already set, they are required to
|
|
|
57 match the then and else basic-blocks to make the pattern match.
|
|
|
58 Returns true if the pattern matched, false otherwise. */
|
|
|
59
|
|
|
60 static bool
|
|
|
61 recognize_if_then_else (basic_block cond_bb,
|
|
|
62 basic_block *then_bb, basic_block *else_bb)
|
|
|
63 {
|
|
|
64 edge t, e;
|
|
|
65
|
|
|
66 if (EDGE_COUNT (cond_bb->succs) != 2)
|
|
|
67 return false;
|
|
|
68
|
|
|
69 /* Find the then/else edges. */
|
|
|
70 t = EDGE_SUCC (cond_bb, 0);
|
|
|
71 e = EDGE_SUCC (cond_bb, 1);
|
|
|
72 if (!(t->flags & EDGE_TRUE_VALUE))
|
|
|
73 {
|
|
|
74 edge tmp = t;
|
|
|
75 t = e;
|
|
|
76 e = tmp;
|
|
|
77 }
|
|
|
78 if (!(t->flags & EDGE_TRUE_VALUE)
|
|
|
79 || !(e->flags & EDGE_FALSE_VALUE))
|
|
|
80 return false;
|
|
|
81
|
|
|
82 /* Check if the edge destinations point to the required block. */
|
|
|
83 if (*then_bb
|
|
|
84 && t->dest != *then_bb)
|
|
|
85 return false;
|
|
|
86 if (*else_bb
|
|
|
87 && e->dest != *else_bb)
|
|
|
88 return false;
|
|
|
89
|
|
|
90 if (!*then_bb)
|
|
|
91 *then_bb = t->dest;
|
|
|
92 if (!*else_bb)
|
|
|
93 *else_bb = e->dest;
|
|
|
94
|
|
|
95 return true;
|
|
|
96 }
|
|
|
97
|
|
|
98 /* Verify if the basic block BB does not have side-effects. Return
|
|
|
99 true in this case, else false. */
|
|
|
100
|
|
|
101 static bool
|
|
|
102 bb_no_side_effects_p (basic_block bb)
|
|
|
103 {
|
|
|
104 gimple_stmt_iterator gsi;
|
|
|
105
|
|
|
106 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
107 {
|
|
|
108 gimple stmt = gsi_stmt (gsi);
|
|
|
109
|
|
|
110 if (gimple_has_volatile_ops (stmt)
|
|
|
111 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
|
|
|
112 return false;
|
|
|
113 }
|
|
|
114
|
|
|
115 return true;
|
|
|
116 }
|
|
|
117
|
|
|
118 /* Verify if all PHI node arguments in DEST for edges from BB1 or
|
|
|
119 BB2 to DEST are the same. This makes the CFG merge point
|
|
|
120 free from side-effects. Return true in this case, else false. */
|
|
|
121
|
|
|
122 static bool
|
|
|
123 same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
|
|
|
124 {
|
|
|
125 edge e1 = find_edge (bb1, dest);
|
|
|
126 edge e2 = find_edge (bb2, dest);
|
|
|
127 gimple_stmt_iterator gsi;
|
|
|
128 gimple phi;
|
|
|
129
|
|
|
130 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
131 {
|
|
|
132 phi = gsi_stmt (gsi);
|
|
|
133 if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
|
|
|
134 PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
|
|
|
135 return false;
|
|
|
136 }
|
|
|
137
|
|
|
138 return true;
|
|
|
139 }
|
|
|
140
|
|
|
141 /* Return the best representative SSA name for CANDIDATE which is used
|
|
|
142 in a bit test. */
|
|
|
143
|
|
|
144 static tree
|
|
|
145 get_name_for_bit_test (tree candidate)
|
|
|
146 {
|
|
|
147 /* Skip single-use names in favor of using the name from a
|
|
|
148 non-widening conversion definition. */
|
|
|
149 if (TREE_CODE (candidate) == SSA_NAME
|
|
|
150 && has_single_use (candidate))
|
|
|
151 {
|
|
|
152 gimple def_stmt = SSA_NAME_DEF_STMT (candidate);
|
|
|
153 if (is_gimple_assign (def_stmt)
|
|
36
|
154 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
|
|
0
|
155 {
|
|
|
156 if (TYPE_PRECISION (TREE_TYPE (candidate))
|
|
|
157 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
|
|
|
158 return gimple_assign_rhs1 (def_stmt);
|
|
|
159 }
|
|
|
160 }
|
|
|
161
|
|
|
162 return candidate;
|
|
|
163 }
|
|
|
164
|
|
|
165 /* Recognize a single bit test pattern in GIMPLE_COND and its defining
|
|
|
166 statements. Store the name being tested in *NAME and the bit
|
|
|
167 in *BIT. The GIMPLE_COND computes *NAME & (1 << *BIT).
|
|
|
168 Returns true if the pattern matched, false otherwise. */
|
|
|
169
|
|
|
170 static bool
|
|
|
171 recognize_single_bit_test (gimple cond, tree *name, tree *bit)
|
|
|
172 {
|
|
|
173 gimple stmt;
|
|
|
174
|
|
|
175 /* Get at the definition of the result of the bit test. */
|
|
|
176 if (gimple_cond_code (cond) != NE_EXPR
|
|
|
177 || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
|
|
|
178 || !integer_zerop (gimple_cond_rhs (cond)))
|
|
|
179 return false;
|
|
|
180 stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
|
|
|
181 if (!is_gimple_assign (stmt))
|
|
|
182 return false;
|
|
|
183
|
|
|
184 /* Look at which bit is tested. One form to recognize is
|
|
|
185 D.1985_5 = state_3(D) >> control1_4(D);
|
|
|
186 D.1986_6 = (int) D.1985_5;
|
|
|
187 D.1987_7 = op0 & 1;
|
|
|
188 if (D.1987_7 != 0) */
|
|
|
189 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
|
|
|
190 && integer_onep (gimple_assign_rhs2 (stmt))
|
|
|
191 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
|
|
|
192 {
|
|
|
193 tree orig_name = gimple_assign_rhs1 (stmt);
|
|
|
194
|
|
|
195 /* Look through copies and conversions to eventually
|
|
|
196 find the stmt that computes the shift. */
|
|
|
197 stmt = SSA_NAME_DEF_STMT (orig_name);
|
|
|
198
|
|
|
199 while (is_gimple_assign (stmt)
|
|
36
|
200 && ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
|
|
|
201 && (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt)))
|
|
|
202 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt)))))
|
|
|
203 || gimple_assign_ssa_name_copy_p (stmt)))
|
|
|
204 stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
|
|
0
|
205
|
|
|
206 /* If we found such, decompose it. */
|
|
|
207 if (is_gimple_assign (stmt)
|
|
|
208 && gimple_assign_rhs_code (stmt) == RSHIFT_EXPR)
|
|
|
209 {
|
|
|
210 /* op0 & (1 << op1) */
|
|
|
211 *bit = gimple_assign_rhs2 (stmt);
|
|
|
212 *name = gimple_assign_rhs1 (stmt);
|
|
|
213 }
|
|
|
214 else
|
|
|
215 {
|
|
|
216 /* t & 1 */
|
|
|
217 *bit = integer_zero_node;
|
|
|
218 *name = get_name_for_bit_test (orig_name);
|
|
|
219 }
|
|
|
220
|
|
|
221 return true;
|
|
|
222 }
|
|
|
223
|
|
|
224 /* Another form is
|
|
|
225 D.1987_7 = op0 & (1 << CST)
|
|
|
226 if (D.1987_7 != 0) */
|
|
|
227 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
|
|
|
228 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
|
|
|
229 && integer_pow2p (gimple_assign_rhs2 (stmt)))
|
|
|
230 {
|
|
|
231 *name = gimple_assign_rhs1 (stmt);
|
|
|
232 *bit = build_int_cst (integer_type_node,
|
|
|
233 tree_log2 (gimple_assign_rhs2 (stmt)));
|
|
|
234 return true;
|
|
|
235 }
|
|
|
236
|
|
|
237 /* Another form is
|
|
|
238 D.1986_6 = 1 << control1_4(D)
|
|
|
239 D.1987_7 = op0 & D.1986_6
|
|
|
240 if (D.1987_7 != 0) */
|
|
|
241 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
|
|
|
242 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
|
|
|
243 && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
|
|
|
244 {
|
|
|
245 gimple tmp;
|
|
|
246
|
|
|
247 /* Both arguments of the BIT_AND_EXPR can be the single-bit
|
|
|
248 specifying expression. */
|
|
|
249 tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
|
|
|
250 if (is_gimple_assign (tmp)
|
|
|
251 && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
|
|
|
252 && integer_onep (gimple_assign_rhs1 (tmp)))
|
|
|
253 {
|
|
|
254 *name = gimple_assign_rhs2 (stmt);
|
|
|
255 *bit = gimple_assign_rhs2 (tmp);
|
|
|
256 return true;
|
|
|
257 }
|
|
|
258
|
|
|
259 tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
|
|
|
260 if (is_gimple_assign (tmp)
|
|
|
261 && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
|
|
|
262 && integer_onep (gimple_assign_rhs1 (tmp)))
|
|
|
263 {
|
|
|
264 *name = gimple_assign_rhs1 (stmt);
|
|
|
265 *bit = gimple_assign_rhs2 (tmp);
|
|
|
266 return true;
|
|
|
267 }
|
|
|
268 }
|
|
|
269
|
|
|
270 return false;
|
|
|
271 }
|
|
|
272
|
|
|
273 /* Recognize a bit test pattern in a GIMPLE_COND and its defining
|
|
|
274 statements. Store the name being tested in *NAME and the bits
|
|
|
275 in *BITS. The COND_EXPR computes *NAME & *BITS.
|
|
|
276 Returns true if the pattern matched, false otherwise. */
|
|
|
277
|
|
|
278 static bool
|
|
|
279 recognize_bits_test (gimple cond, tree *name, tree *bits)
|
|
|
280 {
|
|
|
281 gimple stmt;
|
|
|
282
|
|
|
283 /* Get at the definition of the result of the bit test. */
|
|
|
284 if (gimple_cond_code (cond) != NE_EXPR
|
|
|
285 || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
|
|
|
286 || !integer_zerop (gimple_cond_rhs (cond)))
|
|
|
287 return false;
|
|
|
288 stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
|
|
|
289 if (!is_gimple_assign (stmt)
|
|
|
290 || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
|
|
|
291 return false;
|
|
|
292
|
|
|
293 *name = get_name_for_bit_test (gimple_assign_rhs1 (stmt));
|
|
|
294 *bits = gimple_assign_rhs2 (stmt);
|
|
|
295
|
|
|
296 return true;
|
|
|
297 }
|
|
|
298
|
|
|
299 /* If-convert on a and pattern with a common else block. The inner
|
|
|
300 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
|
|
|
301 Returns true if the edges to the common else basic-block were merged. */
|
|
|
302
|
|
|
303 static bool
|
|
|
304 ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb)
|
|
|
305 {
|
|
|
306 gimple_stmt_iterator gsi;
|
|
|
307 gimple inner_cond, outer_cond;
|
|
|
308 tree name1, name2, bit1, bit2;
|
|
|
309
|
|
|
310 inner_cond = last_stmt (inner_cond_bb);
|
|
|
311 if (!inner_cond
|
|
|
312 || gimple_code (inner_cond) != GIMPLE_COND)
|
|
|
313 return false;
|
|
|
314
|
|
|
315 outer_cond = last_stmt (outer_cond_bb);
|
|
|
316 if (!outer_cond
|
|
|
317 || gimple_code (outer_cond) != GIMPLE_COND)
|
|
|
318 return false;
|
|
|
319
|
|
|
320 /* See if we test a single bit of the same name in both tests. In
|
|
|
321 that case remove the outer test, merging both else edges,
|
|
|
322 and change the inner one to test for
|
|
|
323 name & (bit1 | bit2) == (bit1 | bit2). */
|
|
|
324 if (recognize_single_bit_test (inner_cond, &name1, &bit1)
|
|
|
325 && recognize_single_bit_test (outer_cond, &name2, &bit2)
|
|
|
326 && name1 == name2)
|
|
|
327 {
|
|
|
328 tree t, t2;
|
|
|
329
|
|
|
330 /* Do it. */
|
|
|
331 gsi = gsi_for_stmt (inner_cond);
|
|
|
332 t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
|
|
|
333 build_int_cst (TREE_TYPE (name1), 1), bit1);
|
|
|
334 t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
|
|
|
335 build_int_cst (TREE_TYPE (name1), 1), bit2);
|
|
|
336 t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
|
|
|
337 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
|
|
|
338 true, GSI_SAME_STMT);
|
|
|
339 t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
|
|
|
340 t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE,
|
|
|
341 true, GSI_SAME_STMT);
|
|
|
342 t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t);
|
|
|
343 gimple_cond_set_condition_from_tree (inner_cond, t);
|
|
|
344 update_stmt (inner_cond);
|
|
|
345
|
|
|
346 /* Leave CFG optimization to cfg_cleanup. */
|
|
|
347 gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node);
|
|
|
348 update_stmt (outer_cond);
|
|
|
349
|
|
|
350 if (dump_file)
|
|
|
351 {
|
|
|
352 fprintf (dump_file, "optimizing double bit test to ");
|
|
|
353 print_generic_expr (dump_file, name1, 0);
|
|
|
354 fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
|
|
|
355 print_generic_expr (dump_file, bit1, 0);
|
|
|
356 fprintf (dump_file, ") | (1 << ");
|
|
|
357 print_generic_expr (dump_file, bit2, 0);
|
|
|
358 fprintf (dump_file, ")\n");
|
|
|
359 }
|
|
|
360
|
|
|
361 return true;
|
|
|
362 }
|
|
|
363
|
|
|
364 return false;
|
|
|
365 }
|
|
|
366
|
|
|
367 /* If-convert on a or pattern with a common then block. The inner
|
|
|
368 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
|
|
|
369 Returns true, if the edges leading to the common then basic-block
|
|
|
370 were merged. */
|
|
|
371
|
|
|
372 static bool
|
|
|
373 ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)
|
|
|
374 {
|
|
|
375 gimple inner_cond, outer_cond;
|
|
|
376 tree name1, name2, bits1, bits2;
|
|
|
377
|
|
|
378 inner_cond = last_stmt (inner_cond_bb);
|
|
|
379 if (!inner_cond
|
|
|
380 || gimple_code (inner_cond) != GIMPLE_COND)
|
|
|
381 return false;
|
|
|
382
|
|
|
383 outer_cond = last_stmt (outer_cond_bb);
|
|
|
384 if (!outer_cond
|
|
|
385 || gimple_code (outer_cond) != GIMPLE_COND)
|
|
|
386 return false;
|
|
|
387
|
|
|
388 /* See if we have two bit tests of the same name in both tests.
|
|
|
389 In that case remove the outer test and change the inner one to
|
|
|
390 test for name & (bits1 | bits2) != 0. */
|
|
|
391 if (recognize_bits_test (inner_cond, &name1, &bits1)
|
|
|
392 && recognize_bits_test (outer_cond, &name2, &bits2))
|
|
|
393 {
|
|
|
394 gimple_stmt_iterator gsi;
|
|
|
395 tree t;
|
|
|
396
|
|
|
397 /* Find the common name which is bit-tested. */
|
|
|
398 if (name1 == name2)
|
|
|
399 ;
|
|
|
400 else if (bits1 == bits2)
|
|
|
401 {
|
|
|
402 t = name2;
|
|
|
403 name2 = bits2;
|
|
|
404 bits2 = t;
|
|
|
405 t = name1;
|
|
|
406 name1 = bits1;
|
|
|
407 bits1 = t;
|
|
|
408 }
|
|
|
409 else if (name1 == bits2)
|
|
|
410 {
|
|
|
411 t = name2;
|
|
|
412 name2 = bits2;
|
|
|
413 bits2 = t;
|
|
|
414 }
|
|
|
415 else if (bits1 == name2)
|
|
|
416 {
|
|
|
417 t = name1;
|
|
|
418 name1 = bits1;
|
|
|
419 bits1 = t;
|
|
|
420 }
|
|
|
421 else
|
|
|
422 return false;
|
|
|
423
|
|
|
424 /* As we strip non-widening conversions in finding a common
|
|
|
425 name that is tested make sure to end up with an integral
|
|
|
426 type for building the bit operations. */
|
|
|
427 if (TYPE_PRECISION (TREE_TYPE (bits1))
|
|
|
428 >= TYPE_PRECISION (TREE_TYPE (bits2)))
|
|
|
429 {
|
|
|
430 bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
|
|
|
431 name1 = fold_convert (TREE_TYPE (bits1), name1);
|
|
|
432 bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
|
|
|
433 bits2 = fold_convert (TREE_TYPE (bits1), bits2);
|
|
|
434 }
|
|
|
435 else
|
|
|
436 {
|
|
|
437 bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
|
|
|
438 name1 = fold_convert (TREE_TYPE (bits2), name1);
|
|
|
439 bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
|
|
|
440 bits1 = fold_convert (TREE_TYPE (bits2), bits1);
|
|
|
441 }
|
|
|
442
|
|
|
443 /* Do it. */
|
|
|
444 gsi = gsi_for_stmt (inner_cond);
|
|
|
445 t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
|
|
|
446 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
|
|
|
447 true, GSI_SAME_STMT);
|
|
|
448 t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
|
|
|
449 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
|
|
|
450 true, GSI_SAME_STMT);
|
|
|
451 t = fold_build2 (NE_EXPR, boolean_type_node, t,
|
|
|
452 build_int_cst (TREE_TYPE (t), 0));
|
|
|
453 gimple_cond_set_condition_from_tree (inner_cond, t);
|
|
|
454 update_stmt (inner_cond);
|
|
|
455
|
|
|
456 /* Leave CFG optimization to cfg_cleanup. */
|
|
|
457 gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node);
|
|
|
458 update_stmt (outer_cond);
|
|
|
459
|
|
|
460 if (dump_file)
|
|
|
461 {
|
|
|
462 fprintf (dump_file, "optimizing bits or bits test to ");
|
|
|
463 print_generic_expr (dump_file, name1, 0);
|
|
|
464 fprintf (dump_file, " & T != 0\nwith temporary T = ");
|
|
|
465 print_generic_expr (dump_file, bits1, 0);
|
|
|
466 fprintf (dump_file, " | ");
|
|
|
467 print_generic_expr (dump_file, bits2, 0);
|
|
|
468 fprintf (dump_file, "\n");
|
|
|
469 }
|
|
|
470
|
|
|
471 return true;
|
|
|
472 }
|
|
|
473
|
|
|
474 /* See if we have two comparisons that we can merge into one.
|
|
|
475 This happens for C++ operator overloading where for example
|
|
|
476 GE_EXPR is implemented as GT_EXPR || EQ_EXPR. */
|
|
|
477 else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
|
|
|
478 && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison
|
|
|
479 && operand_equal_p (gimple_cond_lhs (inner_cond),
|
|
|
480 gimple_cond_lhs (outer_cond), 0)
|
|
|
481 && operand_equal_p (gimple_cond_rhs (inner_cond),
|
|
|
482 gimple_cond_rhs (outer_cond), 0))
|
|
|
483 {
|
|
|
484 enum tree_code code1 = gimple_cond_code (inner_cond);
|
|
|
485 enum tree_code code2 = gimple_cond_code (outer_cond);
|
|
|
486 enum tree_code code;
|
|
|
487 tree t;
|
|
|
488
|
|
|
489 #define CHK(a,b) ((code1 == a ## _EXPR && code2 == b ## _EXPR) \
|
|
|
490 || (code2 == a ## _EXPR && code1 == b ## _EXPR))
|
|
|
491 /* Merge the two condition codes if possible. */
|
|
|
492 if (code1 == code2)
|
|
|
493 code = code1;
|
|
|
494 else if (CHK (EQ, LT))
|
|
|
495 code = LE_EXPR;
|
|
|
496 else if (CHK (EQ, GT))
|
|
|
497 code = GE_EXPR;
|
|
|
498 else if (CHK (LT, LE))
|
|
|
499 code = LE_EXPR;
|
|
|
500 else if (CHK (GT, GE))
|
|
|
501 code = GE_EXPR;
|
|
|
502 else if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (inner_cond)))
|
|
|
503 || flag_unsafe_math_optimizations)
|
|
|
504 {
|
|
|
505 if (CHK (LT, GT))
|
|
|
506 code = NE_EXPR;
|
|
|
507 else if (CHK (LT, NE))
|
|
|
508 code = NE_EXPR;
|
|
|
509 else if (CHK (GT, NE))
|
|
|
510 code = NE_EXPR;
|
|
|
511 else
|
|
|
512 return false;
|
|
|
513 }
|
|
|
514 /* We could check for combinations leading to trivial true/false. */
|
|
|
515 else
|
|
|
516 return false;
|
|
|
517 #undef CHK
|
|
|
518
|
|
|
519 /* Do it. */
|
|
|
520 t = fold_build2 (code, boolean_type_node, gimple_cond_lhs (outer_cond),
|
|
|
521 gimple_cond_rhs (outer_cond));
|
|
|
522 t = canonicalize_cond_expr_cond (t);
|
|
|
523 if (!t)
|
|
|
524 return false;
|
|
|
525 gimple_cond_set_condition_from_tree (inner_cond, t);
|
|
|
526 update_stmt (inner_cond);
|
|
|
527
|
|
|
528 /* Leave CFG optimization to cfg_cleanup. */
|
|
|
529 gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node);
|
|
|
530 update_stmt (outer_cond);
|
|
|
531
|
|
|
532 if (dump_file)
|
|
|
533 {
|
|
|
534 fprintf (dump_file, "optimizing two comparisons to ");
|
|
|
535 print_generic_expr (dump_file, t, 0);
|
|
|
536 fprintf (dump_file, "\n");
|
|
|
537 }
|
|
|
538
|
|
|
539 return true;
|
|
|
540 }
|
|
|
541
|
|
|
542 return false;
|
|
|
543 }
|
|
|
544
|
|
|
545 /* Recognize a CFG pattern and dispatch to the appropriate
|
|
|
546 if-conversion helper. We start with BB as the innermost
|
|
|
547 worker basic-block. Returns true if a transformation was done. */
|
|
|
548
|
|
|
549 static bool
|
|
|
550 tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
|
|
|
551 {
|
|
|
552 basic_block then_bb = NULL, else_bb = NULL;
|
|
|
553
|
|
|
554 if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
|
|
|
555 return false;
|
|
|
556
|
|
|
557 /* Recognize && and || of two conditions with a common
|
|
|
558 then/else block which entry edges we can merge. That is:
|
|
|
559 if (a || b)
|
|
|
560 ;
|
|
|
561 and
|
|
|
562 if (a && b)
|
|
|
563 ;
|
|
|
564 This requires a single predecessor of the inner cond_bb. */
|
|
|
565 if (single_pred_p (inner_cond_bb))
|
|
|
566 {
|
|
|
567 basic_block outer_cond_bb = single_pred (inner_cond_bb);
|
|
|
568
|
|
|
569 /* The && form is characterized by a common else_bb with
|
|
|
570 the two edges leading to it mergable. The latter is
|
|
|
571 guaranteed by matching PHI arguments in the else_bb and
|
|
|
572 the inner cond_bb having no side-effects. */
|
|
|
573 if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
|
|
|
574 && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb)
|
|
|
575 && bb_no_side_effects_p (inner_cond_bb))
|
|
|
576 {
|
|
|
577 /* We have
|
|
|
578 <outer_cond_bb>
|
|
|
579 if (q) goto inner_cond_bb; else goto else_bb;
|
|
|
580 <inner_cond_bb>
|
|
|
581 if (p) goto ...; else goto else_bb;
|
|
|
582 ...
|
|
|
583 <else_bb>
|
|
|
584 ...
|
|
|
585 */
|
|
|
586 return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);
|
|
|
587 }
|
|
|
588
|
|
|
589 /* The || form is characterized by a common then_bb with the
|
|
|
590 two edges leading to it mergable. The latter is guaranteed
|
|
|
591 by matching PHI arguments in the then_bb and the inner cond_bb
|
|
|
592 having no side-effects. */
|
|
|
593 if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
|
|
|
594 && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)
|
|
|
595 && bb_no_side_effects_p (inner_cond_bb))
|
|
|
596 {
|
|
|
597 /* We have
|
|
|
598 <outer_cond_bb>
|
|
|
599 if (q) goto then_bb; else goto inner_cond_bb;
|
|
|
600 <inner_cond_bb>
|
|
|
601 if (q) goto then_bb; else goto ...;
|
|
|
602 <then_bb>
|
|
|
603 ...
|
|
|
604 */
|
|
|
605 return ifcombine_iforif (inner_cond_bb, outer_cond_bb);
|
|
|
606 }
|
|
|
607 }
|
|
|
608
|
|
|
609 return false;
|
|
|
610 }
|
|
|
611
|
|
|
612 /* Main entry for the tree if-conversion pass. */
|
|
|
613
|
|
|
614 static unsigned int
|
|
|
615 tree_ssa_ifcombine (void)
|
|
|
616 {
|
|
|
617 basic_block *bbs;
|
|
|
618 bool cfg_changed = false;
|
|
|
619 int i;
|
|
|
620
|
|
|
621 bbs = blocks_in_phiopt_order ();
|
|
|
622
|
|
|
623 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; ++i)
|
|
|
624 {
|
|
|
625 basic_block bb = bbs[i];
|
|
|
626 gimple stmt = last_stmt (bb);
|
|
|
627
|
|
|
628 if (stmt
|
|
|
629 && gimple_code (stmt) == GIMPLE_COND)
|
|
|
630 cfg_changed |= tree_ssa_ifcombine_bb (bb);
|
|
|
631 }
|
|
|
632
|
|
|
633 free (bbs);
|
|
|
634
|
|
|
635 return cfg_changed ? TODO_cleanup_cfg : 0;
|
|
|
636 }
|
|
|
637
|
|
|
638 static bool
|
|
|
639 gate_ifcombine (void)
|
|
|
640 {
|
|
|
641 return 1;
|
|
|
642 }
|
|
|
643
|
|
|
644 struct gimple_opt_pass pass_tree_ifcombine =
|
|
|
645 {
|
|
|
646 {
|
|
|
647 GIMPLE_PASS,
|
|
|
648 "ifcombine", /* name */
|
|
|
649 gate_ifcombine, /* gate */
|
|
|
650 tree_ssa_ifcombine, /* execute */
|
|
|
651 NULL, /* sub */
|
|
|
652 NULL, /* next */
|
|
|
653 0, /* static_pass_number */
|
|
|
654 TV_TREE_IFCOMBINE, /* tv_id */
|
|
|
655 PROP_cfg | PROP_ssa, /* properties_required */
|
|
|
656 0, /* properties_provided */
|
|
|
657 0, /* properties_destroyed */
|
|
|
658 0, /* todo_flags_start */
|
|
|
659 TODO_dump_func
|
|
|
660 | TODO_ggc_collect
|
|
|
661 | TODO_update_ssa
|
|
|
662 | TODO_verify_ssa /* todo_flags_finish */
|
|
|
663 }
|
|
|
664 };
|
