1 /* Optimization of PHI nodes by converting them into straightline code.
2 Copyright (C) 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA
19 02110-1301, USA. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "ggc.h"
26 #include "tree.h"
27 #include "rtl.h"
28 #include "flags.h"
29 #include "tm_p.h"
30 #include "basic-block.h"
31 #include "timevar.h"
32 #include "diagnostic.h"
33 #include "tree-flow.h"
34 #include "tree-pass.h"
35 #include "tree-dump.h"
36 #include "langhooks.h"
37
38 static unsigned int tree_ssa_phiopt (void);
39 static bool conditional_replacement (basic_block, basic_block,
40 edge, edge, tree, tree, tree);
41 static bool value_replacement (basic_block, basic_block,
42 edge, edge, tree, tree, tree);
43 static bool minmax_replacement (basic_block, basic_block,
44 edge, edge, tree, tree, tree);
45 static bool abs_replacement (basic_block, basic_block,
46 edge, edge, tree, tree, tree);
47 static void replace_phi_edge_with_variable (basic_block, edge, tree, tree);
48 static basic_block *blocks_in_phiopt_order (void);
49
50 /* This pass tries to replaces an if-then-else block with an
51 assignment. We have four kinds of transformations. Some of these
52 transformations are also performed by the ifcvt RTL optimizer.
53
54 Conditional Replacement
55 -----------------------
56
57 This transformation, implemented in conditional_replacement,
58 replaces
59
60 bb0:
61 if (cond) goto bb2; else goto bb1;
62 bb1:
63 bb2:
64 x = PHI <0 (bb1), 1 (bb0), ...>;
65
66 with
67
68 bb0:
69 x' = cond;
70 goto bb2;
71 bb2:
72 x = PHI <x' (bb0), ...>;
73
74 We remove bb1 as it becomes unreachable. This occurs often due to
75 gimplification of conditionals.
76
77 Value Replacement
78 -----------------
79
80 This transformation, implemented in value_replacement, replaces
81
82 bb0:
83 if (a != b) goto bb2; else goto bb1;
84 bb1:
85 bb2:
86 x = PHI <a (bb1), b (bb0), ...>;
87
88 with
89
90 bb0:
91 bb2:
92 x = PHI <b (bb0), ...>;
93
94 This opportunity can sometimes occur as a result of other
95 optimizations.
96
97 ABS Replacement
98 ---------------
99
100 This transformation, implemented in abs_replacement, replaces
101
102 bb0:
103 if (a >= 0) goto bb2; else goto bb1;
104 bb1:
105 x = -a;
106 bb2:
107 x = PHI <x (bb1), a (bb0), ...>;
108
109 with
110
111 bb0:
112 x' = ABS_EXPR< a >;
113 bb2:
114 x = PHI <x' (bb0), ...>;
115
116 MIN/MAX Replacement
117 -------------------
118
119 This transformation, minmax_replacement replaces
120
121 bb0:
122 if (a <= b) goto bb2; else goto bb1;
123 bb1:
124 bb2:
125 x = PHI <b (bb1), a (bb0), ...>;
126
127 with
128
129 bb0:
130 x' = MIN_EXPR (a, b)
131 bb2:
132 x = PHI <x' (bb0), ...>;
133
134 A similar transformation is done for MAX_EXPR. */
135
136 static unsigned int
tree_ssa_phiopt(void)137 tree_ssa_phiopt (void)
138 {
139 basic_block bb;
140 basic_block *bb_order;
141 unsigned n, i;
142 bool cfgchanged = false;
143
144 /* Search every basic block for COND_EXPR we may be able to optimize.
145
146 We walk the blocks in order that guarantees that a block with
147 a single predecessor is processed before the predecessor.
148 This ensures that we collapse inner ifs before visiting the
149 outer ones, and also that we do not try to visit a removed
150 block. */
151 bb_order = blocks_in_phiopt_order ();
152 n = n_basic_blocks - NUM_FIXED_BLOCKS;
153
154 for (i = 0; i < n; i++)
155 {
156 tree cond_expr;
157 tree phi;
158 basic_block bb1, bb2;
159 edge e1, e2;
160 tree arg0, arg1;
161
162 bb = bb_order[i];
163
164 cond_expr = last_stmt (bb);
165 /* Check to see if the last statement is a COND_EXPR. */
166 if (!cond_expr
167 || TREE_CODE (cond_expr) != COND_EXPR)
168 continue;
169
170 e1 = EDGE_SUCC (bb, 0);
171 bb1 = e1->dest;
172 e2 = EDGE_SUCC (bb, 1);
173 bb2 = e2->dest;
174
175 /* We cannot do the optimization on abnormal edges. */
176 if ((e1->flags & EDGE_ABNORMAL) != 0
177 || (e2->flags & EDGE_ABNORMAL) != 0)
178 continue;
179
180 /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
181 if (EDGE_COUNT (bb1->succs) == 0
182 || bb2 == NULL
183 || EDGE_COUNT (bb2->succs) == 0)
184 continue;
185
186 /* Find the bb which is the fall through to the other. */
187 if (EDGE_SUCC (bb1, 0)->dest == bb2)
188 ;
189 else if (EDGE_SUCC (bb2, 0)->dest == bb1)
190 {
191 basic_block bb_tmp = bb1;
192 edge e_tmp = e1;
193 bb1 = bb2;
194 bb2 = bb_tmp;
195 e1 = e2;
196 e2 = e_tmp;
197 }
198 else
199 continue;
200
201 e1 = EDGE_SUCC (bb1, 0);
202
203 /* Make sure that bb1 is just a fall through. */
204 if (!single_succ_p (bb1)
205 || (e1->flags & EDGE_FALLTHRU) == 0)
206 continue;
207
208 /* Also make sure that bb1 only have one predecessor and that it
209 is bb. */
210 if (!single_pred_p (bb1)
211 || single_pred (bb1) != bb)
212 continue;
213
214 phi = phi_nodes (bb2);
215
216 /* Check to make sure that there is only one PHI node.
217 TODO: we could do it with more than one iff the other PHI nodes
218 have the same elements for these two edges. */
219 if (!phi || PHI_CHAIN (phi) != NULL)
220 continue;
221
222 arg0 = PHI_ARG_DEF_TREE (phi, e1->dest_idx);
223 arg1 = PHI_ARG_DEF_TREE (phi, e2->dest_idx);
224
225 /* Something is wrong if we cannot find the arguments in the PHI
226 node. */
227 gcc_assert (arg0 != NULL && arg1 != NULL);
228
229 /* Do the replacement of conditional if it can be done. */
230 if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
231 cfgchanged = true;
232 else if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
233 cfgchanged = true;
234 else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
235 cfgchanged = true;
236 else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
237 cfgchanged = true;
238 }
239
240 free (bb_order);
241
242 /* If the CFG has changed, we should cleanup the CFG. */
243 return cfgchanged ? TODO_cleanup_cfg : 0;
244 }
245
246 /* Returns the list of basic blocks in the function in an order that guarantees
247 that if a block X has just a single predecessor Y, then Y is after X in the
248 ordering. */
249
250 static basic_block *
blocks_in_phiopt_order(void)251 blocks_in_phiopt_order (void)
252 {
253 basic_block x, y;
254 basic_block *order = XNEWVEC (basic_block, n_basic_blocks);
255 unsigned n = n_basic_blocks - NUM_FIXED_BLOCKS;
256 unsigned np, i;
257 sbitmap visited = sbitmap_alloc (last_basic_block);
258
259 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
260 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
261
262 sbitmap_zero (visited);
263
264 MARK_VISITED (ENTRY_BLOCK_PTR);
265 FOR_EACH_BB (x)
266 {
267 if (VISITED_P (x))
268 continue;
269
270 /* Walk the predecessors of x as long as they have precisely one
271 predecessor and add them to the list, so that they get stored
272 after x. */
273 for (y = x, np = 1;
274 single_pred_p (y) && !VISITED_P (single_pred (y));
275 y = single_pred (y))
276 np++;
277 for (y = x, i = n - np;
278 single_pred_p (y) && !VISITED_P (single_pred (y));
279 y = single_pred (y), i++)
280 {
281 order[i] = y;
282 MARK_VISITED (y);
283 }
284 order[i] = y;
285 MARK_VISITED (y);
286
287 gcc_assert (i == n - 1);
288 n -= np;
289 }
290
291 sbitmap_free (visited);
292 gcc_assert (n == 0);
293 return order;
294
295 #undef MARK_VISITED
296 #undef VISITED_P
297 }
298
299 /* Return TRUE if block BB has no executable statements, otherwise return
300 FALSE. */
301 bool
empty_block_p(basic_block bb)302 empty_block_p (basic_block bb)
303 {
304 block_stmt_iterator bsi;
305
306 /* BB must have no executable statements. */
307 bsi = bsi_start (bb);
308 while (!bsi_end_p (bsi)
309 && (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR
310 || IS_EMPTY_STMT (bsi_stmt (bsi))))
311 bsi_next (&bsi);
312
313 if (!bsi_end_p (bsi))
314 return false;
315
316 return true;
317 }
318
319 /* Replace PHI node element whose edge is E in block BB with variable NEW.
320 Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
321 is known to have two edges, one of which must reach BB). */
322
323 static void
replace_phi_edge_with_variable(basic_block cond_block,edge e,tree phi,tree new)324 replace_phi_edge_with_variable (basic_block cond_block,
325 edge e, tree phi, tree new)
326 {
327 basic_block bb = bb_for_stmt (phi);
328 basic_block block_to_remove;
329 block_stmt_iterator bsi;
330
331 /* Change the PHI argument to new. */
332 SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new);
333
334 /* Remove the empty basic block. */
335 if (EDGE_SUCC (cond_block, 0)->dest == bb)
336 {
337 EDGE_SUCC (cond_block, 0)->flags |= EDGE_FALLTHRU;
338 EDGE_SUCC (cond_block, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
339 EDGE_SUCC (cond_block, 0)->probability = REG_BR_PROB_BASE;
340 EDGE_SUCC (cond_block, 0)->count += EDGE_SUCC (cond_block, 1)->count;
341
342 block_to_remove = EDGE_SUCC (cond_block, 1)->dest;
343 }
344 else
345 {
346 EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU;
347 EDGE_SUCC (cond_block, 1)->flags
348 &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
349 EDGE_SUCC (cond_block, 1)->probability = REG_BR_PROB_BASE;
350 EDGE_SUCC (cond_block, 1)->count += EDGE_SUCC (cond_block, 0)->count;
351
352 block_to_remove = EDGE_SUCC (cond_block, 0)->dest;
353 }
354 delete_basic_block (block_to_remove);
355
356 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
357 bsi = bsi_last (cond_block);
358 bsi_remove (&bsi, true);
359
360 if (dump_file && (dump_flags & TDF_DETAILS))
361 fprintf (dump_file,
362 "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
363 cond_block->index,
364 bb->index);
365 }
366
367 /* The function conditional_replacement does the main work of doing the
368 conditional replacement. Return true if the replacement is done.
369 Otherwise return false.
370 BB is the basic block where the replacement is going to be done on. ARG0
371 is argument 0 from PHI. Likewise for ARG1. */
372
373 static bool
conditional_replacement(basic_block cond_bb,basic_block middle_bb,edge e0,edge e1,tree phi,tree arg0,tree arg1)374 conditional_replacement (basic_block cond_bb, basic_block middle_bb,
375 edge e0, edge e1, tree phi,
376 tree arg0, tree arg1)
377 {
378 tree result;
379 tree old_result = NULL;
380 tree new, cond;
381 block_stmt_iterator bsi;
382 edge true_edge, false_edge;
383 tree new_var = NULL;
384 tree new_var1;
385
386 /* The PHI arguments have the constants 0 and 1, then convert
387 it to the conditional. */
388 if ((integer_zerop (arg0) && integer_onep (arg1))
389 || (integer_zerop (arg1) && integer_onep (arg0)))
390 ;
391 else
392 return false;
393
394 if (!empty_block_p (middle_bb))
395 return false;
396
397 /* If the condition is not a naked SSA_NAME and its type does not
398 match the type of the result, then we have to create a new
399 variable to optimize this case as it would likely create
400 non-gimple code when the condition was converted to the
401 result's type. */
402 cond = COND_EXPR_COND (last_stmt (cond_bb));
403 result = PHI_RESULT (phi);
404 if (TREE_CODE (cond) != SSA_NAME
405 && !lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
406 {
407 tree tmp;
408
409 if (!COMPARISON_CLASS_P (cond))
410 return false;
411
412 tmp = create_tmp_var (TREE_TYPE (cond), NULL);
413 add_referenced_var (tmp);
414 new_var = make_ssa_name (tmp, NULL);
415 old_result = cond;
416 cond = new_var;
417 }
418
419 /* If the condition was a naked SSA_NAME and the type is not the
420 same as the type of the result, then convert the type of the
421 condition. */
422 if (!lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
423 cond = fold_convert (TREE_TYPE (result), cond);
424
425 /* We need to know which is the true edge and which is the false
426 edge so that we know when to invert the condition below. */
427 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
428
429 /* Insert our new statement at the end of conditional block before the
430 COND_EXPR. */
431 bsi = bsi_last (cond_bb);
432 bsi_insert_before (&bsi, build_empty_stmt (), BSI_NEW_STMT);
433
434 if (old_result)
435 {
436 tree new1;
437
438 new1 = build2 (TREE_CODE (old_result), TREE_TYPE (old_result),
439 TREE_OPERAND (old_result, 0),
440 TREE_OPERAND (old_result, 1));
441
442 new1 = build2 (MODIFY_EXPR, TREE_TYPE (old_result), new_var, new1);
443 SSA_NAME_DEF_STMT (new_var) = new1;
444
445 bsi_insert_after (&bsi, new1, BSI_NEW_STMT);
446 }
447
448 new_var1 = duplicate_ssa_name (PHI_RESULT (phi), NULL);
449
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 There is a single PHI node at the join point (BB) and its arguments
456 are constants (0, 1).
457
458 So, given the condition COND, and the two PHI arguments, we can
459 rewrite this PHI into non-branching code:
460
461 dest = (COND) or dest = COND'
462
463 We use the condition as-is if the argument associated with the
464 true edge has the value one or the argument associated with the
465 false edge as the value zero. Note that those conditions are not
466 the same since only one of the outgoing edges from the COND_EXPR
467 will directly reach BB and thus be associated with an argument. */
468 if ((e0 == true_edge && integer_onep (arg0))
469 || (e0 == false_edge && integer_zerop (arg0))
470 || (e1 == true_edge && integer_onep (arg1))
471 || (e1 == false_edge && integer_zerop (arg1)))
472 {
473 new = build2 (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
474 }
475 else
476 {
477 tree cond1 = invert_truthvalue (cond);
478
479 cond = cond1;
480
481 /* If what we get back is a conditional expression, there is no
482 way that it can be gimple. */
483 if (TREE_CODE (cond) == COND_EXPR)
484 {
485 release_ssa_name (new_var1);
486 return false;
487 }
488
489 /* If COND is not something we can expect to be reducible to a GIMPLE
490 condition, return early. */
491 if (is_gimple_cast (cond))
492 cond1 = TREE_OPERAND (cond, 0);
493 if (TREE_CODE (cond1) == TRUTH_NOT_EXPR
494 && !is_gimple_val (TREE_OPERAND (cond1, 0)))
495 {
496 release_ssa_name (new_var1);
497 return false;
498 }
499
500 /* If what we get back is not gimple try to create it as gimple by
501 using a temporary variable. */
502 if (is_gimple_cast (cond)
503 && !is_gimple_val (TREE_OPERAND (cond, 0)))
504 {
505 tree op0, tmp, cond_tmp;
506
507 /* Only "real" casts are OK here, not everything that is
508 acceptable to is_gimple_cast. Make sure we don't do
509 anything stupid here. */
510 gcc_assert (TREE_CODE (cond) == NOP_EXPR
511 || TREE_CODE (cond) == CONVERT_EXPR);
512
513 op0 = TREE_OPERAND (cond, 0);
514 tmp = create_tmp_var (TREE_TYPE (op0), NULL);
515 add_referenced_var (tmp);
516 cond_tmp = make_ssa_name (tmp, NULL);
517 new = build2 (MODIFY_EXPR, TREE_TYPE (cond_tmp), cond_tmp, op0);
518 SSA_NAME_DEF_STMT (cond_tmp) = new;
519
520 bsi_insert_after (&bsi, new, BSI_NEW_STMT);
521 cond = fold_convert (TREE_TYPE (result), cond_tmp);
522 }
523
524 new = build2 (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
525 }
526
527 bsi_insert_after (&bsi, new, BSI_NEW_STMT);
528
529 SSA_NAME_DEF_STMT (new_var1) = new;
530
531 replace_phi_edge_with_variable (cond_bb, e1, phi, new_var1);
532
533 /* Note that we optimized this PHI. */
534 return true;
535 }
536
537 /* The function value_replacement does the main work of doing the value
538 replacement. Return true if the replacement is done. Otherwise return
539 false.
540 BB is the basic block where the replacement is going to be done on. ARG0
541 is argument 0 from the PHI. Likewise for ARG1. */
542
543 static bool
value_replacement(basic_block cond_bb,basic_block middle_bb,edge e0,edge e1,tree phi,tree arg0,tree arg1)544 value_replacement (basic_block cond_bb, basic_block middle_bb,
545 edge e0, edge e1, tree phi,
546 tree arg0, tree arg1)
547 {
548 tree cond;
549 edge true_edge, false_edge;
550
551 /* If the type says honor signed zeros we cannot do this
552 optimization. */
553 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
554 return false;
555
556 if (!empty_block_p (middle_bb))
557 return false;
558
559 cond = COND_EXPR_COND (last_stmt (cond_bb));
560
561 /* This transformation is only valid for equality comparisons. */
562 if (TREE_CODE (cond) != NE_EXPR && TREE_CODE (cond) != EQ_EXPR)
563 return false;
564
565 /* We need to know which is the true edge and which is the false
566 edge so that we know if have abs or negative abs. */
567 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
568
569 /* At this point we know we have a COND_EXPR with two successors.
570 One successor is BB, the other successor is an empty block which
571 falls through into BB.
572
573 The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
574
575 There is a single PHI node at the join point (BB) with two arguments.
576
577 We now need to verify that the two arguments in the PHI node match
578 the two arguments to the equality comparison. */
579
580 if ((operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 0))
581 && operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 1)))
582 || (operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 0))
583 && operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 1))))
584 {
585 edge e;
586 tree arg;
587
588 /* For NE_EXPR, we want to build an assignment result = arg where
589 arg is the PHI argument associated with the true edge. For
590 EQ_EXPR we want the PHI argument associated with the false edge. */
591 e = (TREE_CODE (cond) == NE_EXPR ? true_edge : false_edge);
592
593 /* Unfortunately, E may not reach BB (it may instead have gone to
594 OTHER_BLOCK). If that is the case, then we want the single outgoing
595 edge from OTHER_BLOCK which reaches BB and represents the desired
596 path from COND_BLOCK. */
597 if (e->dest == middle_bb)
598 e = single_succ_edge (e->dest);
599
600 /* Now we know the incoming edge to BB that has the argument for the
601 RHS of our new assignment statement. */
602 if (e0 == e)
603 arg = arg0;
604 else
605 arg = arg1;
606
607 replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
608
609 /* Note that we optimized this PHI. */
610 return true;
611 }
612 return false;
613 }
614
615 /* The function minmax_replacement does the main work of doing the minmax
616 replacement. Return true if the replacement is done. Otherwise return
617 false.
618 BB is the basic block where the replacement is going to be done on. ARG0
619 is argument 0 from the PHI. Likewise for ARG1. */
620
621 static bool
minmax_replacement(basic_block cond_bb,basic_block middle_bb,edge e0,edge e1,tree phi,tree arg0,tree arg1)622 minmax_replacement (basic_block cond_bb, basic_block middle_bb,
623 edge e0, edge e1, tree phi,
624 tree arg0, tree arg1)
625 {
626 tree result, type;
627 tree cond, new;
628 edge true_edge, false_edge;
629 enum tree_code cmp, minmax, ass_code;
630 tree smaller, larger, arg_true, arg_false;
631 block_stmt_iterator bsi, bsi_from;
632
633 type = TREE_TYPE (PHI_RESULT (phi));
634
635 /* The optimization may be unsafe due to NaNs. */
636 if (HONOR_NANS (TYPE_MODE (type)))
637 return false;
638
639 cond = COND_EXPR_COND (last_stmt (cond_bb));
640 cmp = TREE_CODE (cond);
641 result = PHI_RESULT (phi);
642
643 /* This transformation is only valid for order comparisons. Record which
644 operand is smaller/larger if the result of the comparison is true. */
645 if (cmp == LT_EXPR || cmp == LE_EXPR)
646 {
647 smaller = TREE_OPERAND (cond, 0);
648 larger = TREE_OPERAND (cond, 1);
649 }
650 else if (cmp == GT_EXPR || cmp == GE_EXPR)
651 {
652 smaller = TREE_OPERAND (cond, 1);
653 larger = TREE_OPERAND (cond, 0);
654 }
655 else
656 return false;
657
658 /* We need to know which is the true edge and which is the false
659 edge so that we know if have abs or negative abs. */
660 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
661
662 /* Forward the edges over the middle basic block. */
663 if (true_edge->dest == middle_bb)
664 true_edge = EDGE_SUCC (true_edge->dest, 0);
665 if (false_edge->dest == middle_bb)
666 false_edge = EDGE_SUCC (false_edge->dest, 0);
667
668 if (true_edge == e0)
669 {
670 gcc_assert (false_edge == e1);
671 arg_true = arg0;
672 arg_false = arg1;
673 }
674 else
675 {
676 gcc_assert (false_edge == e0);
677 gcc_assert (true_edge == e1);
678 arg_true = arg1;
679 arg_false = arg0;
680 }
681
682 if (empty_block_p (middle_bb))
683 {
684 if (operand_equal_for_phi_arg_p (arg_true, smaller)
685 && operand_equal_for_phi_arg_p (arg_false, larger))
686 {
687 /* Case
688
689 if (smaller < larger)
690 rslt = smaller;
691 else
692 rslt = larger; */
693 minmax = MIN_EXPR;
694 }
695 else if (operand_equal_for_phi_arg_p (arg_false, smaller)
696 && operand_equal_for_phi_arg_p (arg_true, larger))
697 minmax = MAX_EXPR;
698 else
699 return false;
700 }
701 else
702 {
703 /* Recognize the following case, assuming d <= u:
704
705 if (a <= u)
706 b = MAX (a, d);
707 x = PHI <b, u>
708
709 This is equivalent to
710
711 b = MAX (a, d);
712 x = MIN (b, u); */
713
714 tree assign = last_and_only_stmt (middle_bb);
715 tree lhs, rhs, op0, op1, bound;
716
717 if (!assign
718 || TREE_CODE (assign) != MODIFY_EXPR)
719 return false;
720
721 lhs = TREE_OPERAND (assign, 0);
722 rhs = TREE_OPERAND (assign, 1);
723 ass_code = TREE_CODE (rhs);
724 if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
725 return false;
726 op0 = TREE_OPERAND (rhs, 0);
727 op1 = TREE_OPERAND (rhs, 1);
728
729 if (true_edge->src == middle_bb)
730 {
731 /* We got here if the condition is true, i.e., SMALLER < LARGER. */
732 if (!operand_equal_for_phi_arg_p (lhs, arg_true))
733 return false;
734
735 if (operand_equal_for_phi_arg_p (arg_false, larger))
736 {
737 /* Case
738
739 if (smaller < larger)
740 {
741 r' = MAX_EXPR (smaller, bound)
742 }
743 r = PHI <r', larger> --> to be turned to MIN_EXPR. */
744 if (ass_code != MAX_EXPR)
745 return false;
746
747 minmax = MIN_EXPR;
748 if (operand_equal_for_phi_arg_p (op0, smaller))
749 bound = op1;
750 else if (operand_equal_for_phi_arg_p (op1, smaller))
751 bound = op0;
752 else
753 return false;
754
755 /* We need BOUND <= LARGER. */
756 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
757 bound, larger)))
758 return false;
759 }
760 else if (operand_equal_for_phi_arg_p (arg_false, smaller))
761 {
762 /* Case
763
764 if (smaller < larger)
765 {
766 r' = MIN_EXPR (larger, bound)
767 }
768 r = PHI <r', smaller> --> to be turned to MAX_EXPR. */
769 if (ass_code != MIN_EXPR)
770 return false;
771
772 minmax = MAX_EXPR;
773 if (operand_equal_for_phi_arg_p (op0, larger))
774 bound = op1;
775 else if (operand_equal_for_phi_arg_p (op1, larger))
776 bound = op0;
777 else
778 return false;
779
780 /* We need BOUND >= SMALLER. */
781 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
782 bound, smaller)))
783 return false;
784 }
785 else
786 return false;
787 }
788 else
789 {
790 /* We got here if the condition is false, i.e., SMALLER > LARGER. */
791 if (!operand_equal_for_phi_arg_p (lhs, arg_false))
792 return false;
793
794 if (operand_equal_for_phi_arg_p (arg_true, larger))
795 {
796 /* Case
797
798 if (smaller > larger)
799 {
800 r' = MIN_EXPR (smaller, bound)
801 }
802 r = PHI <r', larger> --> to be turned to MAX_EXPR. */
803 if (ass_code != MIN_EXPR)
804 return false;
805
806 minmax = MAX_EXPR;
807 if (operand_equal_for_phi_arg_p (op0, smaller))
808 bound = op1;
809 else if (operand_equal_for_phi_arg_p (op1, smaller))
810 bound = op0;
811 else
812 return false;
813
814 /* We need BOUND >= LARGER. */
815 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
816 bound, larger)))
817 return false;
818 }
819 else if (operand_equal_for_phi_arg_p (arg_true, smaller))
820 {
821 /* Case
822
823 if (smaller > larger)
824 {
825 r' = MAX_EXPR (larger, bound)
826 }
827 r = PHI <r', smaller> --> to be turned to MIN_EXPR. */
828 if (ass_code != MAX_EXPR)
829 return false;
830
831 minmax = MIN_EXPR;
832 if (operand_equal_for_phi_arg_p (op0, larger))
833 bound = op1;
834 else if (operand_equal_for_phi_arg_p (op1, larger))
835 bound = op0;
836 else
837 return false;
838
839 /* We need BOUND <= SMALLER. */
840 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
841 bound, smaller)))
842 return false;
843 }
844 else
845 return false;
846 }
847
848 /* Move the statement from the middle block. */
849 bsi = bsi_last (cond_bb);
850 bsi_from = bsi_last (middle_bb);
851 bsi_move_before (&bsi_from, &bsi);
852 }
853
854 /* Emit the statement to compute min/max. */
855 result = duplicate_ssa_name (PHI_RESULT (phi), NULL);
856 new = build2 (MODIFY_EXPR, type, result,
857 build2 (minmax, type, arg0, arg1));
858 SSA_NAME_DEF_STMT (result) = new;
859 bsi = bsi_last (cond_bb);
860 bsi_insert_before (&bsi, new, BSI_NEW_STMT);
861
862 replace_phi_edge_with_variable (cond_bb, e1, phi, result);
863 return true;
864 }
865
866 /* The function absolute_replacement does the main work of doing the absolute
867 replacement. Return true if the replacement is done. Otherwise return
868 false.
869 bb is the basic block where the replacement is going to be done on. arg0
870 is argument 0 from the phi. Likewise for arg1. */
871
872 static bool
abs_replacement(basic_block cond_bb,basic_block middle_bb,edge e0 ATTRIBUTE_UNUSED,edge e1,tree phi,tree arg0,tree arg1)873 abs_replacement (basic_block cond_bb, basic_block middle_bb,
874 edge e0 ATTRIBUTE_UNUSED, edge e1,
875 tree phi, tree arg0, tree arg1)
876 {
877 tree result;
878 tree new, cond;
879 block_stmt_iterator bsi;
880 edge true_edge, false_edge;
881 tree assign;
882 edge e;
883 tree rhs, lhs;
884 bool negate;
885 enum tree_code cond_code;
886
887 /* If the type says honor signed zeros we cannot do this
888 optimization. */
889 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
890 return false;
891
892 /* OTHER_BLOCK must have only one executable statement which must have the
893 form arg0 = -arg1 or arg1 = -arg0. */
894
895 assign = last_and_only_stmt (middle_bb);
896 /* If we did not find the proper negation assignment, then we can not
897 optimize. */
898 if (assign == NULL)
899 return false;
900
901 /* If we got here, then we have found the only executable statement
902 in OTHER_BLOCK. If it is anything other than arg = -arg1 or
903 arg1 = -arg0, then we can not optimize. */
904 if (TREE_CODE (assign) != MODIFY_EXPR)
905 return false;
906
907 lhs = TREE_OPERAND (assign, 0);
908 rhs = TREE_OPERAND (assign, 1);
909
910 if (TREE_CODE (rhs) != NEGATE_EXPR)
911 return false;
912
913 rhs = TREE_OPERAND (rhs, 0);
914
915 /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */
916 if (!(lhs == arg0 && rhs == arg1)
917 && !(lhs == arg1 && rhs == arg0))
918 return false;
919
920 cond = COND_EXPR_COND (last_stmt (cond_bb));
921 result = PHI_RESULT (phi);
922
923 /* Only relationals comparing arg[01] against zero are interesting. */
924 cond_code = TREE_CODE (cond);
925 if (cond_code != GT_EXPR && cond_code != GE_EXPR
926 && cond_code != LT_EXPR && cond_code != LE_EXPR)
927 return false;
928
929 /* Make sure the conditional is arg[01] OP y. */
930 if (TREE_OPERAND (cond, 0) != rhs)
931 return false;
932
933 if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))
934 ? real_zerop (TREE_OPERAND (cond, 1))
935 : integer_zerop (TREE_OPERAND (cond, 1)))
936 ;
937 else
938 return false;
939
940 /* We need to know which is the true edge and which is the false
941 edge so that we know if have abs or negative abs. */
942 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
943
944 /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
945 will need to negate the result. Similarly for LT_EXPR/LE_EXPR if
946 the false edge goes to OTHER_BLOCK. */
947 if (cond_code == GT_EXPR || cond_code == GE_EXPR)
948 e = true_edge;
949 else
950 e = false_edge;
951
952 if (e->dest == middle_bb)
953 negate = true;
954 else
955 negate = false;
956
957 result = duplicate_ssa_name (result, NULL);
958
959 if (negate)
960 {
961 tree tmp = create_tmp_var (TREE_TYPE (result), NULL);
962 add_referenced_var (tmp);
963 lhs = make_ssa_name (tmp, NULL);
964 }
965 else
966 lhs = result;
967
968 /* Build the modify expression with abs expression. */
969 new = build2 (MODIFY_EXPR, TREE_TYPE (lhs),
970 lhs, build1 (ABS_EXPR, TREE_TYPE (lhs), rhs));
971 SSA_NAME_DEF_STMT (lhs) = new;
972
973 bsi = bsi_last (cond_bb);
974 bsi_insert_before (&bsi, new, BSI_NEW_STMT);
975
976 if (negate)
977 {
978 /* Get the right BSI. We want to insert after the recently
979 added ABS_EXPR statement (which we know is the first statement
980 in the block. */
981 new = build2 (MODIFY_EXPR, TREE_TYPE (result),
982 result, build1 (NEGATE_EXPR, TREE_TYPE (lhs), lhs));
983 SSA_NAME_DEF_STMT (result) = new;
984
985 bsi_insert_after (&bsi, new, BSI_NEW_STMT);
986 }
987
988 replace_phi_edge_with_variable (cond_bb, e1, phi, result);
989
990 /* Note that we optimized this PHI. */
991 return true;
992 }
993
994
995 /* Always do these optimizations if we have SSA
996 trees to work on. */
997 static bool
gate_phiopt(void)998 gate_phiopt (void)
999 {
1000 return 1;
1001 }
1002
1003 struct tree_opt_pass pass_phiopt =
1004 {
1005 "phiopt", /* name */
1006 gate_phiopt, /* gate */
1007 tree_ssa_phiopt, /* execute */
1008 NULL, /* sub */
1009 NULL, /* next */
1010 0, /* static_pass_number */
1011 TV_TREE_PHIOPT, /* tv_id */
1012 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1013 0, /* properties_provided */
1014 0, /* properties_destroyed */
1015 0, /* todo_flags_start */
1016 TODO_dump_func
1017 | TODO_ggc_collect
1018 | TODO_verify_ssa
1019 | TODO_verify_flow
1020 | TODO_verify_stmts, /* todo_flags_finish */
1021 0 /* letter */
1022 };
1023