]>
Commit | Line | Data |
---|---|---|
4ee9c684 | 1 | /* Optimization of PHI nodes by converting them into straightline code. |
2 | Copyright (C) 2004 Free Software Foundation, Inc. | |
3 | ||
4 | This file is part of GCC. | |
5 | ||
6 | GCC is free software; you can redistribute it and/or modify it | |
7 | under the terms of the GNU General Public License as published by the | |
8 | Free Software Foundation; either version 2, or (at your option) any | |
9 | later version. | |
10 | ||
11 | GCC is distributed in the hope that it will be useful, but WITHOUT | |
12 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 | for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
17 | along with GCC; see the file COPYING. If not, write to the Free | |
18 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
19 | 02111-1307, USA. */ | |
20 | ||
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "errors.h" | |
26 | #include "ggc.h" | |
27 | #include "tree.h" | |
28 | #include "rtl.h" | |
0beac6fc | 29 | #include "flags.h" |
4ee9c684 | 30 | #include "tm_p.h" |
31 | #include "basic-block.h" | |
32 | #include "timevar.h" | |
33 | #include "diagnostic.h" | |
34 | #include "tree-flow.h" | |
35 | #include "tree-pass.h" | |
36 | #include "tree-dump.h" | |
37 | #include "langhooks.h" | |
38 | ||
39 | static void tree_ssa_phiopt (void); | |
0beac6fc | 40 | static bool conditional_replacement (basic_block, tree, tree, tree); |
41 | static bool value_replacement (basic_block, tree, tree, tree); | |
70512b93 | 42 | static bool abs_replacement (basic_block, tree, tree, tree); |
902929aa | 43 | static void replace_phi_with_stmt (block_stmt_iterator, basic_block, |
44 | basic_block, tree, tree); | |
45 | static bool candidate_bb_for_phi_optimization (basic_block, | |
46 | basic_block *, | |
47 | basic_block *); | |
48 | ||
4ee9c684 | 49 | /* This pass eliminates PHI nodes which can be trivially implemented as |
50 | an assignment from a conditional expression. ie if we have something | |
51 | like: | |
52 | ||
53 | bb0: | |
54 | if (cond) goto bb2; else goto bb1; | |
55 | bb1: | |
56 | bb2: | |
57 | x = PHI (0 (bb1), 1 (bb0) | |
58 | ||
2ab0a163 | 59 | We can rewrite that as: |
4ee9c684 | 60 | |
2ab0a163 | 61 | bb0: |
62 | bb1: | |
63 | bb2: | |
4ee9c684 | 64 | x = cond; |
65 | ||
2ab0a163 | 66 | bb1 will become unreachable and bb0 and bb2 will almost always |
67 | be merged into a single block. This occurs often due to gimplification | |
0beac6fc | 68 | of conditionals. |
69 | ||
70 | Also done is the following optimization: | |
71 | ||
72 | bb0: | |
73 | if (a != b) goto bb2; else goto bb1; | |
74 | bb1: | |
75 | bb2: | |
76 | x = PHI (a (bb1), b (bb0)) | |
77 | ||
78 | We can rewrite that as: | |
79 | ||
80 | bb0: | |
81 | bb1: | |
82 | bb2: | |
83 | x = b; | |
84 | ||
85 | This can sometimes occur as a result of other optimizations. A | |
70512b93 | 86 | similar transformation is done by the ifcvt RTL optimizer. |
87 | ||
88 | This pass also eliminates PHI nodes which are really absolute | |
89 | values. i.e. if we have something like: | |
90 | ||
91 | bb0: | |
92 | if (a >= 0) goto bb2; else goto bb1; | |
93 | bb1: | |
94 | x = -a; | |
95 | bb2: | |
96 | x = PHI (x (bb1), a (bb0)); | |
97 | ||
98 | We can rewrite that as: | |
99 | ||
100 | bb0: | |
101 | bb1: | |
102 | bb2: | |
103 | x = ABS_EXPR< a >; | |
104 | ||
105 | bb1 will become unreachable and bb0 and bb2 will almost always be merged | |
106 | into a single block. Similar transformations are done by the ifcvt | |
107 | RTL optimizer. */ | |
108 | ||
4ee9c684 | 109 | static void |
110 | tree_ssa_phiopt (void) | |
111 | { | |
112 | basic_block bb; | |
113 | bool removed_phis = false; | |
114 | ||
115 | /* Search every basic block for PHI nodes we may be able to optimize. */ | |
116 | FOR_EACH_BB (bb) | |
117 | { | |
118 | tree arg0, arg1, phi; | |
119 | ||
4ee9c684 | 120 | /* We're searching for blocks with one PHI node which has two |
121 | arguments. */ | |
122 | phi = phi_nodes (bb); | |
04f8eea3 | 123 | if (phi && PHI_CHAIN (phi) == NULL |
4ee9c684 | 124 | && PHI_NUM_ARGS (phi) == 2) |
2ab0a163 | 125 | { |
126 | arg0 = PHI_ARG_DEF (phi, 0); | |
127 | arg1 = PHI_ARG_DEF (phi, 1); | |
128 | ||
129 | /* Do the replacement of conditional if it can be done. */ | |
0beac6fc | 130 | if (conditional_replacement (bb, phi, arg0, arg1) |
70512b93 | 131 | || value_replacement (bb, phi, arg0, arg1) |
132 | || abs_replacement (bb, phi, arg0, arg1)) | |
0beac6fc | 133 | { |
134 | /* We have done the replacement so we need to rebuild the | |
135 | cfg when this pass is complete. */ | |
136 | removed_phis = true; | |
137 | } | |
2ab0a163 | 138 | } |
4ee9c684 | 139 | } |
140 | ||
141 | /* If we removed any PHIs, then we have unreachable blocks and blocks | |
142 | which need to be merged in the CFG. */ | |
143 | if (removed_phis) | |
144 | cleanup_tree_cfg (); | |
145 | } | |
146 | ||
70512b93 | 147 | /* Return TRUE if block BB has no executable statements, otherwise return |
148 | FALSE. */ | |
c91e8223 | 149 | bool |
70512b93 | 150 | empty_block_p (basic_block bb) |
151 | { | |
152 | block_stmt_iterator bsi; | |
153 | ||
154 | /* BB must have no executable statements. */ | |
155 | bsi = bsi_start (bb); | |
156 | while (!bsi_end_p (bsi) | |
157 | && (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR | |
158 | || IS_EMPTY_STMT (bsi_stmt (bsi)))) | |
159 | bsi_next (&bsi); | |
160 | ||
161 | if (!bsi_end_p (bsi)) | |
162 | return false; | |
163 | ||
164 | return true; | |
165 | } | |
166 | ||
902929aa | 167 | /* BB is a basic block which has only one PHI node with precisely two |
168 | arguments. | |
169 | ||
170 | Examine both of BB's predecessors to see if one ends with a | |
70512b93 | 171 | COND_EXPR and the other is a successor of the COND_EXPR. If so, then |
172 | we may be able to optimize PHI nodes at the start of BB. | |
902929aa | 173 | |
174 | If so, mark store the block with the COND_EXPR into COND_BLOCK_P | |
175 | and the other block into OTHER_BLOCK_P and return true, otherwise | |
176 | return false. */ | |
4ee9c684 | 177 | |
178 | static bool | |
902929aa | 179 | candidate_bb_for_phi_optimization (basic_block bb, |
180 | basic_block *cond_block_p, | |
181 | basic_block *other_block_p) | |
4ee9c684 | 182 | { |
902929aa | 183 | tree last0, last1; |
902929aa | 184 | basic_block cond_block, other_block; |
4ee9c684 | 185 | |
4ee9c684 | 186 | /* One of the alternatives must come from a block ending with |
70512b93 | 187 | a COND_EXPR. */ |
4ee9c684 | 188 | last0 = last_stmt (bb->pred->src); |
189 | last1 = last_stmt (bb->pred->pred_next->src); | |
190 | if (last0 && TREE_CODE (last0) == COND_EXPR) | |
191 | { | |
192 | cond_block = bb->pred->src; | |
193 | other_block = bb->pred->pred_next->src; | |
194 | } | |
195 | else if (last1 && TREE_CODE (last1) == COND_EXPR) | |
196 | { | |
197 | other_block = bb->pred->src; | |
198 | cond_block = bb->pred->pred_next->src; | |
199 | } | |
200 | else | |
201 | return false; | |
202 | ||
203 | /* COND_BLOCK must have precisely two successors. We indirectly | |
2ab0a163 | 204 | verify that those successors are BB and OTHER_BLOCK. */ |
4ee9c684 | 205 | if (!cond_block->succ |
206 | || !cond_block->succ->succ_next | |
207 | || cond_block->succ->succ_next->succ_next | |
208 | || (cond_block->succ->flags & EDGE_ABNORMAL) != 0 | |
209 | || (cond_block->succ->succ_next->flags & EDGE_ABNORMAL) != 0) | |
210 | return false; | |
211 | ||
212 | /* OTHER_BLOCK must have a single predecessor which is COND_BLOCK, | |
2ab0a163 | 213 | OTHER_BLOCK must have a single successor which is BB and |
214 | OTHER_BLOCK must have no PHI nodes. */ | |
4ee9c684 | 215 | if (!other_block->pred |
216 | || other_block->pred->src != cond_block | |
217 | || other_block->pred->pred_next | |
218 | || !other_block->succ | |
219 | || other_block->succ->dest != bb | |
220 | || other_block->succ->succ_next | |
221 | || phi_nodes (other_block)) | |
222 | return false; | |
223 | ||
902929aa | 224 | *cond_block_p = cond_block; |
225 | *other_block_p = other_block; | |
226 | /* Everything looks OK. */ | |
227 | return true; | |
228 | } | |
229 | ||
230 | /* Replace PHI in block BB with statement NEW. NEW is inserted after | |
231 | BSI. Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK | |
232 | is known to have two edges, one of which must reach BB). */ | |
233 | ||
234 | static void | |
235 | replace_phi_with_stmt (block_stmt_iterator bsi, basic_block bb, | |
236 | basic_block cond_block, tree phi, tree new) | |
237 | { | |
0e1a77e1 | 238 | basic_block block_to_remove; |
239 | ||
902929aa | 240 | /* Insert our new statement at the head of our block. */ |
241 | bsi_insert_after (&bsi, new, BSI_NEW_STMT); | |
242 | ||
243 | /* Register our new statement as the defining statement for | |
244 | the result. */ | |
245 | SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new; | |
246 | ||
247 | /* Remove the now useless PHI node. | |
248 | ||
249 | We do not want to use remove_phi_node since that releases the | |
250 | SSA_NAME as well and the SSA_NAME is still being used. */ | |
251 | release_phi_node (phi); | |
252 | bb_ann (bb)->phi_nodes = NULL; | |
253 | ||
0e1a77e1 | 254 | /* Remove the empty basic block. */ |
902929aa | 255 | if (cond_block->succ->dest == bb) |
256 | { | |
257 | cond_block->succ->flags |= EDGE_FALLTHRU; | |
258 | cond_block->succ->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); | |
0e1a77e1 | 259 | |
260 | block_to_remove = cond_block->succ->succ_next->dest; | |
902929aa | 261 | } |
262 | else | |
263 | { | |
264 | cond_block->succ->succ_next->flags |= EDGE_FALLTHRU; | |
265 | cond_block->succ->succ_next->flags | |
266 | &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); | |
0e1a77e1 | 267 | |
268 | block_to_remove = cond_block->succ->dest; | |
902929aa | 269 | } |
0e1a77e1 | 270 | delete_basic_block (block_to_remove); |
902929aa | 271 | |
272 | /* Eliminate the COND_EXPR at the end of COND_BLOCK. */ | |
273 | bsi = bsi_last (cond_block); | |
274 | bsi_remove (&bsi); | |
275 | ||
276 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
277 | fprintf (dump_file, | |
278 | "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n", | |
279 | cond_block->index, | |
280 | bb->index); | |
281 | } | |
282 | ||
283 | /* The function conditional_replacement does the main work of doing the | |
284 | conditional replacement. Return true if the replacement is done. | |
285 | Otherwise return false. | |
286 | BB is the basic block where the replacement is going to be done on. ARG0 | |
287 | is argument 0 from PHI. Likewise for ARG1. */ | |
288 | ||
289 | static bool | |
290 | conditional_replacement (basic_block bb, tree phi, tree arg0, tree arg1) | |
291 | { | |
292 | tree result; | |
293 | tree old_result = NULL; | |
294 | basic_block other_block = NULL; | |
295 | basic_block cond_block = NULL; | |
296 | tree new, cond; | |
297 | block_stmt_iterator bsi; | |
298 | edge true_edge, false_edge; | |
299 | tree new_var = NULL; | |
300 | ||
301 | /* The PHI arguments have the constants 0 and 1, then convert | |
302 | it to the conditional. */ | |
303 | if ((integer_zerop (arg0) && integer_onep (arg1)) | |
304 | || (integer_zerop (arg1) && integer_onep (arg0))) | |
305 | ; | |
306 | else | |
307 | return false; | |
4ee9c684 | 308 | |
70512b93 | 309 | if (!candidate_bb_for_phi_optimization (bb, &cond_block, &other_block) |
310 | || !empty_block_p (other_block)) | |
902929aa | 311 | return false; |
312 | ||
4ee9c684 | 313 | /* If the condition is not a naked SSA_NAME and its type does not |
2ab0a163 | 314 | match the type of the result, then we have to create a new |
315 | variable to optimize this case as it would likely create | |
316 | non-gimple code when the condition was converted to the | |
317 | result's type. */ | |
4ee9c684 | 318 | cond = COND_EXPR_COND (last_stmt (cond_block)); |
319 | result = PHI_RESULT (phi); | |
320 | if (TREE_CODE (cond) != SSA_NAME | |
321 | && !lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result))) | |
ae5a4794 | 322 | { |
323 | new_var = make_rename_temp (TREE_TYPE (cond), NULL); | |
324 | old_result = cond; | |
325 | cond = new_var; | |
326 | } | |
4ee9c684 | 327 | |
328 | /* If the condition was a naked SSA_NAME and the type is not the | |
2ab0a163 | 329 | same as the type of the result, then convert the type of the |
330 | condition. */ | |
4ee9c684 | 331 | if (!lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result))) |
332 | cond = fold_convert (TREE_TYPE (result), cond); | |
333 | ||
334 | /* We need to know which is the true edge and which is the false | |
2ab0a163 | 335 | edge so that we know when to invert the condition below. */ |
4ee9c684 | 336 | extract_true_false_edges_from_block (cond_block, &true_edge, &false_edge); |
ae5a4794 | 337 | |
338 | /* Insert our new statement at the head of our block. */ | |
339 | bsi = bsi_start (bb); | |
340 | ||
341 | if (old_result) | |
342 | { | |
343 | tree new1; | |
344 | if (TREE_CODE_CLASS (TREE_CODE (old_result)) != '<') | |
2ab0a163 | 345 | return false; |
ae5a4794 | 346 | |
347 | new1 = build (TREE_CODE (old_result), TREE_TYPE (result), | |
2ab0a163 | 348 | TREE_OPERAND (old_result, 0), |
349 | TREE_OPERAND (old_result, 1)); | |
ae5a4794 | 350 | |
0beac6fc | 351 | new1 = build (MODIFY_EXPR, TREE_TYPE (result), new_var, new1); |
ae5a4794 | 352 | bsi_insert_after (&bsi, new1, BSI_NEW_STMT); |
353 | } | |
354 | ||
4ee9c684 | 355 | /* At this point we know we have a COND_EXPR with two successors. |
2ab0a163 | 356 | One successor is BB, the other successor is an empty block which |
357 | falls through into BB. | |
4ee9c684 | 358 | |
2ab0a163 | 359 | There is a single PHI node at the join point (BB) and its arguments |
360 | are constants (0, 1). | |
4ee9c684 | 361 | |
2ab0a163 | 362 | So, given the condition COND, and the two PHI arguments, we can |
363 | rewrite this PHI into non-branching code: | |
4ee9c684 | 364 | |
2ab0a163 | 365 | dest = (COND) or dest = COND' |
ae5a4794 | 366 | |
2ab0a163 | 367 | We use the condition as-is if the argument associated with the |
368 | true edge has the value one or the argument associated with the | |
369 | false edge as the value zero. Note that those conditions are not | |
370 | the same since only one of the outgoing edges from the COND_EXPR | |
371 | will directly reach BB and thus be associated with an argument. */ | |
4ee9c684 | 372 | if ((PHI_ARG_EDGE (phi, 0) == true_edge && integer_onep (arg0)) |
373 | || (PHI_ARG_EDGE (phi, 0) == false_edge && integer_zerop (arg0)) | |
374 | || (PHI_ARG_EDGE (phi, 1) == true_edge && integer_onep (arg1)) | |
375 | || (PHI_ARG_EDGE (phi, 1) == false_edge && integer_zerop (arg1))) | |
376 | { | |
377 | new = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)), | |
2ab0a163 | 378 | PHI_RESULT (phi), cond); |
4ee9c684 | 379 | } |
380 | else | |
381 | { | |
ae5a4794 | 382 | tree cond1 = invert_truthvalue (cond); |
383 | ||
384 | cond = cond1; | |
385 | /* If what we get back is a conditional expression, there is no | |
0beac6fc | 386 | way that it can be gimple. */ |
ae5a4794 | 387 | if (TREE_CODE (cond) == COND_EXPR) |
388 | return false; | |
389 | ||
390 | /* If what we get back is not gimple try to create it as gimple by | |
2ab0a163 | 391 | using a temporary variable. */ |
4ee9c684 | 392 | if (is_gimple_cast (cond) |
393 | && !is_gimple_val (TREE_OPERAND (cond, 0))) | |
2ab0a163 | 394 | { |
395 | tree temp = TREE_OPERAND (cond, 0); | |
396 | tree new_var_1 = make_rename_temp (TREE_TYPE (temp), NULL); | |
397 | new = build (MODIFY_EXPR, TREE_TYPE (new_var_1), new_var_1, temp); | |
398 | bsi_insert_after (&bsi, new, BSI_NEW_STMT); | |
399 | cond = fold_convert (TREE_TYPE (result), new_var_1); | |
400 | } | |
4ee9c684 | 401 | |
402 | if (TREE_CODE (cond) == TRUTH_NOT_EXPR | |
2ab0a163 | 403 | && !is_gimple_val (TREE_OPERAND (cond, 0))) |
404 | return false; | |
4ee9c684 | 405 | |
406 | new = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)), | |
2ab0a163 | 407 | PHI_RESULT (phi), cond); |
4ee9c684 | 408 | } |
409 | ||
902929aa | 410 | replace_phi_with_stmt (bsi, bb, cond_block, phi, new); |
411 | ||
4ee9c684 | 412 | /* Note that we optimized this PHI. */ |
413 | return true; | |
414 | } | |
415 | ||
0beac6fc | 416 | /* The function value_replacement does the main work of doing the value |
417 | replacement. Return true if the replacement is done. Otherwise return | |
418 | false. | |
419 | BB is the basic block where the replacement is going to be done on. ARG0 | |
420 | is argument 0 from the PHI. Likewise for ARG1. */ | |
421 | ||
422 | static bool | |
423 | value_replacement (basic_block bb, tree phi, tree arg0, tree arg1) | |
424 | { | |
425 | tree result; | |
426 | basic_block other_block = NULL; | |
427 | basic_block cond_block = NULL; | |
428 | tree new, cond; | |
429 | edge true_edge, false_edge; | |
430 | ||
431 | /* If the type says honor signed zeros we cannot do this | |
432 | optimization. */ | |
433 | if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1)))) | |
434 | return false; | |
435 | ||
70512b93 | 436 | if (!candidate_bb_for_phi_optimization (bb, &cond_block, &other_block) |
437 | || !empty_block_p (other_block)) | |
0beac6fc | 438 | return false; |
439 | ||
440 | cond = COND_EXPR_COND (last_stmt (cond_block)); | |
441 | result = PHI_RESULT (phi); | |
442 | ||
443 | /* This transformation is only valid for equality comparisons. */ | |
444 | if (TREE_CODE (cond) != NE_EXPR && TREE_CODE (cond) != EQ_EXPR) | |
445 | return false; | |
446 | ||
447 | /* We need to know which is the true edge and which is the false | |
448 | edge so that we know if have abs or negative abs. */ | |
449 | extract_true_false_edges_from_block (cond_block, &true_edge, &false_edge); | |
450 | ||
451 | /* At this point we know we have a COND_EXPR with two successors. | |
452 | One successor is BB, the other successor is an empty block which | |
453 | falls through into BB. | |
454 | ||
455 | The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR. | |
456 | ||
457 | There is a single PHI node at the join point (BB) with two arguments. | |
458 | ||
459 | We now need to verify that the two arguments in the PHI node match | |
460 | the two arguments to the equality comparison. */ | |
461 | ||
462 | if ((operand_equal_p (arg0, TREE_OPERAND (cond, 0), 0) | |
463 | && operand_equal_p (arg1, TREE_OPERAND (cond, 1), 0)) | |
464 | || (operand_equal_p (arg1, TREE_OPERAND (cond, 0), 0) | |
465 | && operand_equal_p (arg0, TREE_OPERAND (cond, 1), 0))) | |
466 | { | |
467 | edge e; | |
468 | tree arg; | |
469 | ||
50737d20 | 470 | /* For NE_EXPR, we want to build an assignment result = arg where |
471 | arg is the PHI argument associated with the true edge. For | |
472 | EQ_EXPR we want the PHI argument associated with the false edge. */ | |
0beac6fc | 473 | e = (TREE_CODE (cond) == NE_EXPR ? true_edge : false_edge); |
50737d20 | 474 | |
475 | /* Unfortunately, E may not reach BB (it may instead have gone to | |
476 | OTHER_BLOCK). If that is the case, then we want the single outgoing | |
477 | edge from OTHER_BLOCK which reaches BB and represents the desired | |
478 | path from COND_BLOCK. */ | |
479 | if (e->dest == other_block) | |
480 | e = e->dest->succ; | |
481 | ||
482 | /* Now we know the incoming edge to BB that has the argument for the | |
483 | RHS of our new assignment statement. */ | |
0beac6fc | 484 | if (PHI_ARG_EDGE (phi, 0) == e) |
485 | arg = arg0; | |
486 | else | |
487 | arg = arg1; | |
488 | ||
489 | /* Build the new assignment. */ | |
490 | new = build (MODIFY_EXPR, TREE_TYPE (result), result, arg); | |
491 | ||
492 | replace_phi_with_stmt (bsi_start (bb), bb, cond_block, phi, new); | |
493 | ||
494 | /* Note that we optimized this PHI. */ | |
495 | return true; | |
496 | } | |
497 | return false; | |
498 | } | |
499 | ||
70512b93 | 500 | /* The function absolute_replacement does the main work of doing the absolute |
501 | replacement. Return true if the replacement is done. Otherwise return | |
502 | false. | |
503 | bb is the basic block where the replacement is going to be done on. arg0 | |
504 | is argument 0 from the phi. Likewise for arg1. */ | |
505 | static bool | |
506 | abs_replacement (basic_block bb, tree phi, tree arg0, tree arg1) | |
507 | { | |
508 | tree result; | |
509 | basic_block other_block = NULL; | |
510 | basic_block cond_block = NULL; | |
511 | tree new, cond; | |
512 | block_stmt_iterator bsi; | |
513 | edge true_edge, false_edge; | |
514 | tree assign = NULL; | |
515 | edge e; | |
516 | tree rhs = NULL, lhs = NULL; | |
517 | bool negate; | |
518 | enum tree_code cond_code; | |
519 | ||
520 | /* If the type says honor signed zeros we cannot do this | |
521 | optimization. */ | |
522 | if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1)))) | |
523 | return false; | |
524 | ||
525 | if (!candidate_bb_for_phi_optimization (bb, &cond_block, &other_block)) | |
526 | return false; | |
527 | ||
528 | /* OTHER_BLOCK must have only one executable statement which must have the | |
529 | form arg0 = -arg1 or arg1 = -arg0. */ | |
530 | bsi = bsi_start (other_block); | |
531 | while (!bsi_end_p (bsi)) | |
532 | { | |
533 | tree stmt = bsi_stmt (bsi); | |
534 | ||
535 | /* Empty statements and labels are uninteresting. */ | |
536 | if (TREE_CODE (stmt) == LABEL_EXPR | |
537 | || IS_EMPTY_STMT (stmt)) | |
538 | { | |
539 | bsi_next (&bsi); | |
540 | continue; | |
541 | } | |
542 | ||
543 | /* If we found the assignment, but it was not the only executable | |
544 | statement in OTHER_BLOCK, then we can not optimize. */ | |
545 | if (assign) | |
546 | return false; | |
547 | ||
548 | /* If we got here, then we have found the first executable statement | |
549 | in OTHER_BLOCK. If it is anything other than arg = -arg1 or | |
550 | arg1 = -arg0, then we can not optimize. */ | |
551 | if (TREE_CODE (stmt) == MODIFY_EXPR) | |
552 | { | |
553 | lhs = TREE_OPERAND (stmt, 0); | |
554 | rhs = TREE_OPERAND (stmt, 1); | |
555 | ||
556 | if (TREE_CODE (rhs) == NEGATE_EXPR) | |
557 | { | |
558 | rhs = TREE_OPERAND (rhs, 0); | |
559 | ||
560 | /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */ | |
561 | if ((lhs == arg0 && rhs == arg1) | |
562 | || (lhs == arg1 && rhs == arg0)) | |
563 | { | |
564 | assign = stmt; | |
565 | bsi_next (&bsi); | |
566 | } | |
567 | else | |
568 | return false; | |
569 | } | |
570 | else | |
571 | return false; | |
572 | } | |
573 | else | |
574 | return false; | |
575 | } | |
576 | ||
577 | /* If we did not find the proper negation assignment, then we can not | |
578 | optimize. */ | |
579 | if (assign == NULL) | |
580 | return false; | |
581 | ||
582 | cond = COND_EXPR_COND (last_stmt (cond_block)); | |
583 | result = PHI_RESULT (phi); | |
584 | ||
585 | /* Only relationals comparing arg[01] against zero are interesting. */ | |
586 | cond_code = TREE_CODE (cond); | |
587 | if (cond_code != GT_EXPR && cond_code != GE_EXPR | |
588 | && cond_code != LT_EXPR && cond_code != LE_EXPR) | |
589 | return false; | |
590 | ||
591 | /* Make sure the conditional is arg[01] OP y. */ | |
592 | if (TREE_OPERAND (cond, 0) != rhs) | |
593 | return false; | |
594 | ||
595 | if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1))) | |
596 | ? real_zerop (TREE_OPERAND (cond, 1)) | |
597 | : integer_zerop (TREE_OPERAND (cond, 1))) | |
598 | ; | |
599 | else | |
600 | return false; | |
601 | ||
602 | /* We need to know which is the true edge and which is the false | |
603 | edge so that we know if have abs or negative abs. */ | |
604 | extract_true_false_edges_from_block (cond_block, &true_edge, &false_edge); | |
605 | ||
606 | /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we | |
607 | will need to negate the result. Similarly for LT_EXPR/LE_EXPR if | |
608 | the false edge goes to OTHER_BLOCK. */ | |
609 | if (cond_code == GT_EXPR || cond_code == GE_EXPR) | |
610 | e = true_edge; | |
611 | else | |
612 | e = false_edge; | |
613 | ||
614 | if (e->dest == other_block) | |
615 | negate = true; | |
616 | else | |
617 | negate = false; | |
618 | ||
619 | if (negate) | |
620 | lhs = make_rename_temp (TREE_TYPE (result), NULL); | |
621 | else | |
622 | lhs = result; | |
623 | ||
624 | /* Build the modify expression with abs expression. */ | |
625 | new = build (MODIFY_EXPR, TREE_TYPE (lhs), | |
626 | lhs, build1 (ABS_EXPR, TREE_TYPE (lhs), rhs)); | |
627 | ||
628 | replace_phi_with_stmt (bsi_start (bb), bb, cond_block, phi, new); | |
629 | ||
630 | if (negate) | |
631 | { | |
632 | ||
633 | /* Get the right BSI. We want to insert after the recently | |
634 | added ABS_EXPR statement (which we know is the first statement | |
635 | in the block. */ | |
636 | bsi = bsi_start (bb); | |
637 | bsi_next (&bsi); | |
638 | new = build (MODIFY_EXPR, TREE_TYPE (result), | |
639 | result, build1 (NEGATE_EXPR, TREE_TYPE (lhs), lhs)); | |
640 | ||
641 | bsi_insert_after (&bsi, new, BSI_NEW_STMT); | |
642 | ||
643 | /* Register the new statement as defining the temporary -- this is | |
644 | normally done by replace_phi_with_stmt, but the link will be wrong | |
645 | if we had to negate the resulting value. */ | |
646 | SSA_NAME_DEF_STMT (result) = new; | |
647 | } | |
648 | ||
649 | /* Note that we optimized this PHI. */ | |
650 | return true; | |
651 | } | |
652 | ||
4ee9c684 | 653 | |
654 | /* Always do these optimizations if we have SSA | |
655 | trees to work on. */ | |
656 | static bool | |
657 | gate_phiopt (void) | |
658 | { | |
659 | return 1; | |
660 | } | |
661 | ||
662 | struct tree_opt_pass pass_phiopt = | |
663 | { | |
664 | "phiopt", /* name */ | |
665 | gate_phiopt, /* gate */ | |
666 | tree_ssa_phiopt, /* execute */ | |
667 | NULL, /* sub */ | |
668 | NULL, /* next */ | |
669 | 0, /* static_pass_number */ | |
670 | TV_TREE_PHIOPT, /* tv_id */ | |
f45a1ca1 | 671 | PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ |
4ee9c684 | 672 | 0, /* properties_provided */ |
673 | 0, /* properties_destroyed */ | |
674 | 0, /* todo_flags_start */ | |
675 | TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */ | |
ae5a4794 | 676 | | TODO_verify_ssa | TODO_rename_vars |
0f9005dd | 677 | | TODO_verify_flow, |
678 | 0 /* letter */ | |
4ee9c684 | 679 | }; |
680 | ||
681 |