re PR tree-optimization/33961 (gcc 4.3 causes crash valid code to crash)
[gcc.git] / gcc / tree-ssa-phiopt.c
1 /* Optimization of PHI nodes by converting them into straightline code.
2 Copyright (C) 2004, 2005, 2006, 2007 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 3, 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 COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
19
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "ggc.h"
25 #include "tree.h"
26 #include "rtl.h"
27 #include "flags.h"
28 #include "tm_p.h"
29 #include "basic-block.h"
30 #include "timevar.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-pass.h"
34 #include "tree-dump.h"
35 #include "langhooks.h"
36 #include "pointer-set.h"
37 #include "domwalk.h"
38
39 static unsigned int tree_ssa_phiopt_worker (bool);
40 static bool conditional_replacement (basic_block, basic_block,
41 edge, edge, tree, tree, tree);
42 static bool value_replacement (basic_block, basic_block,
43 edge, edge, tree, tree, tree);
44 static bool minmax_replacement (basic_block, basic_block,
45 edge, edge, tree, tree, tree);
46 static bool abs_replacement (basic_block, basic_block,
47 edge, edge, tree, tree, tree);
48 static bool cond_store_replacement (basic_block, basic_block, edge, edge,
49 struct pointer_set_t *);
50 static struct pointer_set_t * get_non_trapping (void);
51 static void replace_phi_edge_with_variable (basic_block, edge, tree, tree);
52
53 /* This pass tries to replaces an if-then-else block with an
54 assignment. We have four kinds of transformations. Some of these
55 transformations are also performed by the ifcvt RTL optimizer.
56
57 Conditional Replacement
58 -----------------------
59
60 This transformation, implemented in conditional_replacement,
61 replaces
62
63 bb0:
64 if (cond) goto bb2; else goto bb1;
65 bb1:
66 bb2:
67 x = PHI <0 (bb1), 1 (bb0), ...>;
68
69 with
70
71 bb0:
72 x' = cond;
73 goto bb2;
74 bb2:
75 x = PHI <x' (bb0), ...>;
76
77 We remove bb1 as it becomes unreachable. This occurs often due to
78 gimplification of conditionals.
79
80 Value Replacement
81 -----------------
82
83 This transformation, implemented in value_replacement, replaces
84
85 bb0:
86 if (a != b) goto bb2; else goto bb1;
87 bb1:
88 bb2:
89 x = PHI <a (bb1), b (bb0), ...>;
90
91 with
92
93 bb0:
94 bb2:
95 x = PHI <b (bb0), ...>;
96
97 This opportunity can sometimes occur as a result of other
98 optimizations.
99
100 ABS Replacement
101 ---------------
102
103 This transformation, implemented in abs_replacement, replaces
104
105 bb0:
106 if (a >= 0) goto bb2; else goto bb1;
107 bb1:
108 x = -a;
109 bb2:
110 x = PHI <x (bb1), a (bb0), ...>;
111
112 with
113
114 bb0:
115 x' = ABS_EXPR< a >;
116 bb2:
117 x = PHI <x' (bb0), ...>;
118
119 MIN/MAX Replacement
120 -------------------
121
122 This transformation, minmax_replacement replaces
123
124 bb0:
125 if (a <= b) goto bb2; else goto bb1;
126 bb1:
127 bb2:
128 x = PHI <b (bb1), a (bb0), ...>;
129
130 with
131
132 bb0:
133 x' = MIN_EXPR (a, b)
134 bb2:
135 x = PHI <x' (bb0), ...>;
136
137 A similar transformation is done for MAX_EXPR. */
138
139 static unsigned int
140 tree_ssa_phiopt (void)
141 {
142 return tree_ssa_phiopt_worker (false);
143 }
144
145 /* This pass tries to transform conditional stores into unconditional
146 ones, enabling further simplifications with the simpler then and else
147 blocks. In particular it replaces this:
148
149 bb0:
150 if (cond) goto bb2; else goto bb1;
151 bb1:
152 *p = RHS
153 bb2:
154
155 with
156
157 bb0:
158 if (cond) goto bb1; else goto bb2;
159 bb1:
160 condtmp' = *p;
161 bb2:
162 condtmp = PHI <RHS, condtmp'>
163 *p = condtmp
164
165 This transformation can only be done under several constraints,
166 documented below. */
167
168 static unsigned int
169 tree_ssa_cs_elim (void)
170 {
171 return tree_ssa_phiopt_worker (true);
172 }
173
174 /* For conditional store replacement we need a temporary to
175 put the old contents of the memory in. */
176 static tree condstoretemp;
177
178 /* The core routine of conditional store replacement and normal
179 phi optimizations. Both share much of the infrastructure in how
180 to match applicable basic block patterns. DO_STORE_ELIM is true
181 when we want to do conditional store replacement, false otherwise. */
182 static unsigned int
183 tree_ssa_phiopt_worker (bool do_store_elim)
184 {
185 basic_block bb;
186 basic_block *bb_order;
187 unsigned n, i;
188 bool cfgchanged = false;
189 struct pointer_set_t *nontrap = 0;
190
191 if (do_store_elim)
192 {
193 condstoretemp = NULL_TREE;
194 /* Calculate the set of non-trapping memory accesses. */
195 nontrap = get_non_trapping ();
196 }
197
198 /* Search every basic block for COND_EXPR we may be able to optimize.
199
200 We walk the blocks in order that guarantees that a block with
201 a single predecessor is processed before the predecessor.
202 This ensures that we collapse inner ifs before visiting the
203 outer ones, and also that we do not try to visit a removed
204 block. */
205 bb_order = blocks_in_phiopt_order ();
206 n = n_basic_blocks - NUM_FIXED_BLOCKS;
207
208 for (i = 0; i < n; i++)
209 {
210 tree cond_expr;
211 tree phi;
212 basic_block bb1, bb2;
213 edge e1, e2;
214 tree arg0, arg1;
215
216 bb = bb_order[i];
217
218 cond_expr = last_stmt (bb);
219 /* Check to see if the last statement is a COND_EXPR. */
220 if (!cond_expr
221 || TREE_CODE (cond_expr) != COND_EXPR)
222 continue;
223
224 e1 = EDGE_SUCC (bb, 0);
225 bb1 = e1->dest;
226 e2 = EDGE_SUCC (bb, 1);
227 bb2 = e2->dest;
228
229 /* We cannot do the optimization on abnormal edges. */
230 if ((e1->flags & EDGE_ABNORMAL) != 0
231 || (e2->flags & EDGE_ABNORMAL) != 0)
232 continue;
233
234 /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
235 if (EDGE_COUNT (bb1->succs) == 0
236 || bb2 == NULL
237 || EDGE_COUNT (bb2->succs) == 0)
238 continue;
239
240 /* Find the bb which is the fall through to the other. */
241 if (EDGE_SUCC (bb1, 0)->dest == bb2)
242 ;
243 else if (EDGE_SUCC (bb2, 0)->dest == bb1)
244 {
245 basic_block bb_tmp = bb1;
246 edge e_tmp = e1;
247 bb1 = bb2;
248 bb2 = bb_tmp;
249 e1 = e2;
250 e2 = e_tmp;
251 }
252 else
253 continue;
254
255 e1 = EDGE_SUCC (bb1, 0);
256
257 /* Make sure that bb1 is just a fall through. */
258 if (!single_succ_p (bb1)
259 || (e1->flags & EDGE_FALLTHRU) == 0)
260 continue;
261
262 /* Also make sure that bb1 only have one predecessor and that it
263 is bb. */
264 if (!single_pred_p (bb1)
265 || single_pred (bb1) != bb)
266 continue;
267
268 if (do_store_elim)
269 {
270 /* bb1 is the middle block, bb2 the join block, bb the split block,
271 e1 the fallthrough edge from bb1 to bb2. We can't do the
272 optimization if the join block has more than two predecessors. */
273 if (EDGE_COUNT (bb2->preds) > 2)
274 continue;
275 if (cond_store_replacement (bb1, bb2, e1, e2, nontrap))
276 cfgchanged = true;
277 }
278 else
279 {
280 phi = phi_nodes (bb2);
281
282 /* Check to make sure that there is only one PHI node.
283 TODO: we could do it with more than one iff the other PHI nodes
284 have the same elements for these two edges. */
285 if (!phi || PHI_CHAIN (phi) != NULL)
286 continue;
287
288 arg0 = PHI_ARG_DEF_TREE (phi, e1->dest_idx);
289 arg1 = PHI_ARG_DEF_TREE (phi, e2->dest_idx);
290
291 /* Something is wrong if we cannot find the arguments in the PHI
292 node. */
293 gcc_assert (arg0 != NULL && arg1 != NULL);
294
295 /* Do the replacement of conditional if it can be done. */
296 if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
297 cfgchanged = true;
298 else if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
299 cfgchanged = true;
300 else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
301 cfgchanged = true;
302 else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
303 cfgchanged = true;
304 }
305 }
306
307 free (bb_order);
308
309 if (do_store_elim)
310 pointer_set_destroy (nontrap);
311 /* If the CFG has changed, we should cleanup the CFG. */
312 if (cfgchanged && do_store_elim)
313 {
314 /* In cond-store replacement we have added some loads on edges
315 and new VOPS (as we moved the store, and created a load). */
316 bsi_commit_edge_inserts ();
317 return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
318 }
319 else if (cfgchanged)
320 return TODO_cleanup_cfg;
321 return 0;
322 }
323
324 /* Returns the list of basic blocks in the function in an order that guarantees
325 that if a block X has just a single predecessor Y, then Y is after X in the
326 ordering. */
327
328 basic_block *
329 blocks_in_phiopt_order (void)
330 {
331 basic_block x, y;
332 basic_block *order = XNEWVEC (basic_block, n_basic_blocks);
333 unsigned n = n_basic_blocks - NUM_FIXED_BLOCKS;
334 unsigned np, i;
335 sbitmap visited = sbitmap_alloc (last_basic_block);
336
337 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
338 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
339
340 sbitmap_zero (visited);
341
342 MARK_VISITED (ENTRY_BLOCK_PTR);
343 FOR_EACH_BB (x)
344 {
345 if (VISITED_P (x))
346 continue;
347
348 /* Walk the predecessors of x as long as they have precisely one
349 predecessor and add them to the list, so that they get stored
350 after x. */
351 for (y = x, np = 1;
352 single_pred_p (y) && !VISITED_P (single_pred (y));
353 y = single_pred (y))
354 np++;
355 for (y = x, i = n - np;
356 single_pred_p (y) && !VISITED_P (single_pred (y));
357 y = single_pred (y), i++)
358 {
359 order[i] = y;
360 MARK_VISITED (y);
361 }
362 order[i] = y;
363 MARK_VISITED (y);
364
365 gcc_assert (i == n - 1);
366 n -= np;
367 }
368
369 sbitmap_free (visited);
370 gcc_assert (n == 0);
371 return order;
372
373 #undef MARK_VISITED
374 #undef VISITED_P
375 }
376
377
378 /* Return TRUE if block BB has no executable statements, otherwise return
379 FALSE. */
380
381 bool
382 empty_block_p (basic_block bb)
383 {
384 block_stmt_iterator bsi;
385
386 /* BB must have no executable statements. */
387 bsi = bsi_start (bb);
388 while (!bsi_end_p (bsi)
389 && (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR
390 || IS_EMPTY_STMT (bsi_stmt (bsi))))
391 bsi_next (&bsi);
392
393 if (!bsi_end_p (bsi))
394 return false;
395
396 return true;
397 }
398
399 /* Replace PHI node element whose edge is E in block BB with variable NEW.
400 Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
401 is known to have two edges, one of which must reach BB). */
402
403 static void
404 replace_phi_edge_with_variable (basic_block cond_block,
405 edge e, tree phi, tree new_tree)
406 {
407 basic_block bb = bb_for_stmt (phi);
408 basic_block block_to_remove;
409 block_stmt_iterator bsi;
410
411 /* Change the PHI argument to new. */
412 SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);
413
414 /* Remove the empty basic block. */
415 if (EDGE_SUCC (cond_block, 0)->dest == bb)
416 {
417 EDGE_SUCC (cond_block, 0)->flags |= EDGE_FALLTHRU;
418 EDGE_SUCC (cond_block, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
419 EDGE_SUCC (cond_block, 0)->probability = REG_BR_PROB_BASE;
420 EDGE_SUCC (cond_block, 0)->count += EDGE_SUCC (cond_block, 1)->count;
421
422 block_to_remove = EDGE_SUCC (cond_block, 1)->dest;
423 }
424 else
425 {
426 EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU;
427 EDGE_SUCC (cond_block, 1)->flags
428 &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
429 EDGE_SUCC (cond_block, 1)->probability = REG_BR_PROB_BASE;
430 EDGE_SUCC (cond_block, 1)->count += EDGE_SUCC (cond_block, 0)->count;
431
432 block_to_remove = EDGE_SUCC (cond_block, 0)->dest;
433 }
434 delete_basic_block (block_to_remove);
435
436 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
437 bsi = bsi_last (cond_block);
438 bsi_remove (&bsi, true);
439
440 if (dump_file && (dump_flags & TDF_DETAILS))
441 fprintf (dump_file,
442 "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
443 cond_block->index,
444 bb->index);
445 }
446
447 /* The function conditional_replacement does the main work of doing the
448 conditional replacement. Return true if the replacement is done.
449 Otherwise return false.
450 BB is the basic block where the replacement is going to be done on. ARG0
451 is argument 0 from PHI. Likewise for ARG1. */
452
453 static bool
454 conditional_replacement (basic_block cond_bb, basic_block middle_bb,
455 edge e0, edge e1, tree phi,
456 tree arg0, tree arg1)
457 {
458 tree result;
459 tree old_result = NULL;
460 tree new_stmt, cond;
461 block_stmt_iterator bsi;
462 edge true_edge, false_edge;
463 tree new_var = NULL;
464 tree new_var1;
465
466 /* The PHI arguments have the constants 0 and 1, then convert
467 it to the conditional. */
468 if ((integer_zerop (arg0) && integer_onep (arg1))
469 || (integer_zerop (arg1) && integer_onep (arg0)))
470 ;
471 else
472 return false;
473
474 if (!empty_block_p (middle_bb))
475 return false;
476
477 /* If the condition is not a naked SSA_NAME and its type does not
478 match the type of the result, then we have to create a new
479 variable to optimize this case as it would likely create
480 non-gimple code when the condition was converted to the
481 result's type. */
482 cond = COND_EXPR_COND (last_stmt (cond_bb));
483 result = PHI_RESULT (phi);
484 if (TREE_CODE (cond) != SSA_NAME
485 && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (cond)))
486 {
487 tree tmp;
488
489 if (!COMPARISON_CLASS_P (cond))
490 return false;
491
492 tmp = create_tmp_var (TREE_TYPE (cond), NULL);
493 add_referenced_var (tmp);
494 new_var = make_ssa_name (tmp, NULL);
495 old_result = cond;
496 cond = new_var;
497 }
498
499 /* If the condition was a naked SSA_NAME and the type is not the
500 same as the type of the result, then convert the type of the
501 condition. */
502 if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (cond)))
503 cond = fold_convert (TREE_TYPE (result), cond);
504
505 /* We need to know which is the true edge and which is the false
506 edge so that we know when to invert the condition below. */
507 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
508
509 /* Insert our new statement at the end of conditional block before the
510 COND_EXPR. */
511 bsi = bsi_last (cond_bb);
512 bsi_insert_before (&bsi, build_empty_stmt (), BSI_NEW_STMT);
513
514 if (old_result)
515 {
516 tree new1;
517
518 new1 = build2 (TREE_CODE (old_result), TREE_TYPE (old_result),
519 TREE_OPERAND (old_result, 0),
520 TREE_OPERAND (old_result, 1));
521
522 new1 = build_gimple_modify_stmt (new_var, new1);
523 SSA_NAME_DEF_STMT (new_var) = new1;
524
525 bsi_insert_after (&bsi, new1, BSI_NEW_STMT);
526 }
527
528 new_var1 = duplicate_ssa_name (PHI_RESULT (phi), NULL);
529
530
531 /* At this point we know we have a COND_EXPR with two successors.
532 One successor is BB, the other successor is an empty block which
533 falls through into BB.
534
535 There is a single PHI node at the join point (BB) and its arguments
536 are constants (0, 1).
537
538 So, given the condition COND, and the two PHI arguments, we can
539 rewrite this PHI into non-branching code:
540
541 dest = (COND) or dest = COND'
542
543 We use the condition as-is if the argument associated with the
544 true edge has the value one or the argument associated with the
545 false edge as the value zero. Note that those conditions are not
546 the same since only one of the outgoing edges from the COND_EXPR
547 will directly reach BB and thus be associated with an argument. */
548 if ((e0 == true_edge && integer_onep (arg0))
549 || (e0 == false_edge && integer_zerop (arg0))
550 || (e1 == true_edge && integer_onep (arg1))
551 || (e1 == false_edge && integer_zerop (arg1)))
552 {
553 new_stmt = build_gimple_modify_stmt (new_var1, cond);
554 }
555 else
556 {
557 tree cond1 = invert_truthvalue (cond);
558
559 cond = cond1;
560
561 /* If what we get back is a conditional expression, there is no
562 way that it can be gimple. */
563 if (TREE_CODE (cond) == COND_EXPR)
564 {
565 release_ssa_name (new_var1);
566 return false;
567 }
568
569 /* If COND is not something we can expect to be reducible to a GIMPLE
570 condition, return early. */
571 if (is_gimple_cast (cond))
572 cond1 = TREE_OPERAND (cond, 0);
573 if (TREE_CODE (cond1) == TRUTH_NOT_EXPR
574 && !is_gimple_val (TREE_OPERAND (cond1, 0)))
575 {
576 release_ssa_name (new_var1);
577 return false;
578 }
579
580 /* If what we get back is not gimple try to create it as gimple by
581 using a temporary variable. */
582 if (is_gimple_cast (cond)
583 && !is_gimple_val (TREE_OPERAND (cond, 0)))
584 {
585 tree op0, tmp, cond_tmp;
586
587 /* Only "real" casts are OK here, not everything that is
588 acceptable to is_gimple_cast. Make sure we don't do
589 anything stupid here. */
590 gcc_assert (TREE_CODE (cond) == NOP_EXPR
591 || TREE_CODE (cond) == CONVERT_EXPR);
592
593 op0 = TREE_OPERAND (cond, 0);
594 tmp = create_tmp_var (TREE_TYPE (op0), NULL);
595 add_referenced_var (tmp);
596 cond_tmp = make_ssa_name (tmp, NULL);
597 new_stmt = build_gimple_modify_stmt (cond_tmp, op0);
598 SSA_NAME_DEF_STMT (cond_tmp) = new_stmt;
599
600 bsi_insert_after (&bsi, new_stmt, BSI_NEW_STMT);
601 cond = fold_convert (TREE_TYPE (result), cond_tmp);
602 }
603
604 new_stmt = build_gimple_modify_stmt (new_var1, cond);
605 }
606
607 bsi_insert_after (&bsi, new_stmt, BSI_NEW_STMT);
608
609 SSA_NAME_DEF_STMT (new_var1) = new_stmt;
610
611 replace_phi_edge_with_variable (cond_bb, e1, phi, new_var1);
612
613 /* Note that we optimized this PHI. */
614 return true;
615 }
616
617 /* The function value_replacement does the main work of doing the value
618 replacement. Return true if the replacement is done. Otherwise return
619 false.
620 BB is the basic block where the replacement is going to be done on. ARG0
621 is argument 0 from the PHI. Likewise for ARG1. */
622
623 static bool
624 value_replacement (basic_block cond_bb, basic_block middle_bb,
625 edge e0, edge e1, tree phi,
626 tree arg0, tree arg1)
627 {
628 tree cond;
629 edge true_edge, false_edge;
630
631 /* If the type says honor signed zeros we cannot do this
632 optimization. */
633 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
634 return false;
635
636 if (!empty_block_p (middle_bb))
637 return false;
638
639 cond = COND_EXPR_COND (last_stmt (cond_bb));
640
641 /* This transformation is only valid for equality comparisons. */
642 if (TREE_CODE (cond) != NE_EXPR && TREE_CODE (cond) != EQ_EXPR)
643 return false;
644
645 /* We need to know which is the true edge and which is the false
646 edge so that we know if have abs or negative abs. */
647 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
648
649 /* At this point we know we have a COND_EXPR with two successors.
650 One successor is BB, the other successor is an empty block which
651 falls through into BB.
652
653 The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
654
655 There is a single PHI node at the join point (BB) with two arguments.
656
657 We now need to verify that the two arguments in the PHI node match
658 the two arguments to the equality comparison. */
659
660 if ((operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 0))
661 && operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 1)))
662 || (operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 0))
663 && operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 1))))
664 {
665 edge e;
666 tree arg;
667
668 /* For NE_EXPR, we want to build an assignment result = arg where
669 arg is the PHI argument associated with the true edge. For
670 EQ_EXPR we want the PHI argument associated with the false edge. */
671 e = (TREE_CODE (cond) == NE_EXPR ? true_edge : false_edge);
672
673 /* Unfortunately, E may not reach BB (it may instead have gone to
674 OTHER_BLOCK). If that is the case, then we want the single outgoing
675 edge from OTHER_BLOCK which reaches BB and represents the desired
676 path from COND_BLOCK. */
677 if (e->dest == middle_bb)
678 e = single_succ_edge (e->dest);
679
680 /* Now we know the incoming edge to BB that has the argument for the
681 RHS of our new assignment statement. */
682 if (e0 == e)
683 arg = arg0;
684 else
685 arg = arg1;
686
687 replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
688
689 /* Note that we optimized this PHI. */
690 return true;
691 }
692 return false;
693 }
694
695 /* The function minmax_replacement does the main work of doing the minmax
696 replacement. Return true if the replacement is done. Otherwise return
697 false.
698 BB is the basic block where the replacement is going to be done on. ARG0
699 is argument 0 from the PHI. Likewise for ARG1. */
700
701 static bool
702 minmax_replacement (basic_block cond_bb, basic_block middle_bb,
703 edge e0, edge e1, tree phi,
704 tree arg0, tree arg1)
705 {
706 tree result, type;
707 tree cond, new_stmt;
708 edge true_edge, false_edge;
709 enum tree_code cmp, minmax, ass_code;
710 tree smaller, larger, arg_true, arg_false;
711 block_stmt_iterator bsi, bsi_from;
712
713 type = TREE_TYPE (PHI_RESULT (phi));
714
715 /* The optimization may be unsafe due to NaNs. */
716 if (HONOR_NANS (TYPE_MODE (type)))
717 return false;
718
719 cond = COND_EXPR_COND (last_stmt (cond_bb));
720 cmp = TREE_CODE (cond);
721 result = PHI_RESULT (phi);
722
723 /* This transformation is only valid for order comparisons. Record which
724 operand is smaller/larger if the result of the comparison is true. */
725 if (cmp == LT_EXPR || cmp == LE_EXPR)
726 {
727 smaller = TREE_OPERAND (cond, 0);
728 larger = TREE_OPERAND (cond, 1);
729 }
730 else if (cmp == GT_EXPR || cmp == GE_EXPR)
731 {
732 smaller = TREE_OPERAND (cond, 1);
733 larger = TREE_OPERAND (cond, 0);
734 }
735 else
736 return false;
737
738 /* We need to know which is the true edge and which is the false
739 edge so that we know if have abs or negative abs. */
740 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
741
742 /* Forward the edges over the middle basic block. */
743 if (true_edge->dest == middle_bb)
744 true_edge = EDGE_SUCC (true_edge->dest, 0);
745 if (false_edge->dest == middle_bb)
746 false_edge = EDGE_SUCC (false_edge->dest, 0);
747
748 if (true_edge == e0)
749 {
750 gcc_assert (false_edge == e1);
751 arg_true = arg0;
752 arg_false = arg1;
753 }
754 else
755 {
756 gcc_assert (false_edge == e0);
757 gcc_assert (true_edge == e1);
758 arg_true = arg1;
759 arg_false = arg0;
760 }
761
762 if (empty_block_p (middle_bb))
763 {
764 if (operand_equal_for_phi_arg_p (arg_true, smaller)
765 && operand_equal_for_phi_arg_p (arg_false, larger))
766 {
767 /* Case
768
769 if (smaller < larger)
770 rslt = smaller;
771 else
772 rslt = larger; */
773 minmax = MIN_EXPR;
774 }
775 else if (operand_equal_for_phi_arg_p (arg_false, smaller)
776 && operand_equal_for_phi_arg_p (arg_true, larger))
777 minmax = MAX_EXPR;
778 else
779 return false;
780 }
781 else
782 {
783 /* Recognize the following case, assuming d <= u:
784
785 if (a <= u)
786 b = MAX (a, d);
787 x = PHI <b, u>
788
789 This is equivalent to
790
791 b = MAX (a, d);
792 x = MIN (b, u); */
793
794 tree assign = last_and_only_stmt (middle_bb);
795 tree lhs, rhs, op0, op1, bound;
796
797 if (!assign
798 || TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
799 return false;
800
801 lhs = GIMPLE_STMT_OPERAND (assign, 0);
802 rhs = GIMPLE_STMT_OPERAND (assign, 1);
803 ass_code = TREE_CODE (rhs);
804 if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
805 return false;
806 op0 = TREE_OPERAND (rhs, 0);
807 op1 = TREE_OPERAND (rhs, 1);
808
809 if (true_edge->src == middle_bb)
810 {
811 /* We got here if the condition is true, i.e., SMALLER < LARGER. */
812 if (!operand_equal_for_phi_arg_p (lhs, arg_true))
813 return false;
814
815 if (operand_equal_for_phi_arg_p (arg_false, larger))
816 {
817 /* Case
818
819 if (smaller < larger)
820 {
821 r' = MAX_EXPR (smaller, bound)
822 }
823 r = PHI <r', larger> --> to be turned to MIN_EXPR. */
824 if (ass_code != MAX_EXPR)
825 return false;
826
827 minmax = MIN_EXPR;
828 if (operand_equal_for_phi_arg_p (op0, smaller))
829 bound = op1;
830 else if (operand_equal_for_phi_arg_p (op1, smaller))
831 bound = op0;
832 else
833 return false;
834
835 /* We need BOUND <= LARGER. */
836 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
837 bound, larger)))
838 return false;
839 }
840 else if (operand_equal_for_phi_arg_p (arg_false, smaller))
841 {
842 /* Case
843
844 if (smaller < larger)
845 {
846 r' = MIN_EXPR (larger, bound)
847 }
848 r = PHI <r', smaller> --> to be turned to MAX_EXPR. */
849 if (ass_code != MIN_EXPR)
850 return false;
851
852 minmax = MAX_EXPR;
853 if (operand_equal_for_phi_arg_p (op0, larger))
854 bound = op1;
855 else if (operand_equal_for_phi_arg_p (op1, larger))
856 bound = op0;
857 else
858 return false;
859
860 /* We need BOUND >= SMALLER. */
861 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
862 bound, smaller)))
863 return false;
864 }
865 else
866 return false;
867 }
868 else
869 {
870 /* We got here if the condition is false, i.e., SMALLER > LARGER. */
871 if (!operand_equal_for_phi_arg_p (lhs, arg_false))
872 return false;
873
874 if (operand_equal_for_phi_arg_p (arg_true, larger))
875 {
876 /* Case
877
878 if (smaller > larger)
879 {
880 r' = MIN_EXPR (smaller, bound)
881 }
882 r = PHI <r', larger> --> to be turned to MAX_EXPR. */
883 if (ass_code != MIN_EXPR)
884 return false;
885
886 minmax = MAX_EXPR;
887 if (operand_equal_for_phi_arg_p (op0, smaller))
888 bound = op1;
889 else if (operand_equal_for_phi_arg_p (op1, smaller))
890 bound = op0;
891 else
892 return false;
893
894 /* We need BOUND >= LARGER. */
895 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
896 bound, larger)))
897 return false;
898 }
899 else if (operand_equal_for_phi_arg_p (arg_true, smaller))
900 {
901 /* Case
902
903 if (smaller > larger)
904 {
905 r' = MAX_EXPR (larger, bound)
906 }
907 r = PHI <r', smaller> --> to be turned to MIN_EXPR. */
908 if (ass_code != MAX_EXPR)
909 return false;
910
911 minmax = MIN_EXPR;
912 if (operand_equal_for_phi_arg_p (op0, larger))
913 bound = op1;
914 else if (operand_equal_for_phi_arg_p (op1, larger))
915 bound = op0;
916 else
917 return false;
918
919 /* We need BOUND <= SMALLER. */
920 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
921 bound, smaller)))
922 return false;
923 }
924 else
925 return false;
926 }
927
928 /* Move the statement from the middle block. */
929 bsi = bsi_last (cond_bb);
930 bsi_from = bsi_last (middle_bb);
931 bsi_move_before (&bsi_from, &bsi);
932 }
933
934 /* Emit the statement to compute min/max. */
935 result = duplicate_ssa_name (PHI_RESULT (phi), NULL);
936 new_stmt = build_gimple_modify_stmt (result, build2 (minmax, type, arg0, arg1));
937 SSA_NAME_DEF_STMT (result) = new_stmt;
938 bsi = bsi_last (cond_bb);
939 bsi_insert_before (&bsi, new_stmt, BSI_NEW_STMT);
940
941 replace_phi_edge_with_variable (cond_bb, e1, phi, result);
942 return true;
943 }
944
945 /* The function absolute_replacement does the main work of doing the absolute
946 replacement. Return true if the replacement is done. Otherwise return
947 false.
948 bb is the basic block where the replacement is going to be done on. arg0
949 is argument 0 from the phi. Likewise for arg1. */
950
951 static bool
952 abs_replacement (basic_block cond_bb, basic_block middle_bb,
953 edge e0 ATTRIBUTE_UNUSED, edge e1,
954 tree phi, tree arg0, tree arg1)
955 {
956 tree result;
957 tree new_stmt, cond;
958 block_stmt_iterator bsi;
959 edge true_edge, false_edge;
960 tree assign;
961 edge e;
962 tree rhs, lhs;
963 bool negate;
964 enum tree_code cond_code;
965
966 /* If the type says honor signed zeros we cannot do this
967 optimization. */
968 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
969 return false;
970
971 /* OTHER_BLOCK must have only one executable statement which must have the
972 form arg0 = -arg1 or arg1 = -arg0. */
973
974 assign = last_and_only_stmt (middle_bb);
975 /* If we did not find the proper negation assignment, then we can not
976 optimize. */
977 if (assign == NULL)
978 return false;
979
980 /* If we got here, then we have found the only executable statement
981 in OTHER_BLOCK. If it is anything other than arg = -arg1 or
982 arg1 = -arg0, then we can not optimize. */
983 if (TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
984 return false;
985
986 lhs = GIMPLE_STMT_OPERAND (assign, 0);
987 rhs = GIMPLE_STMT_OPERAND (assign, 1);
988
989 if (TREE_CODE (rhs) != NEGATE_EXPR)
990 return false;
991
992 rhs = TREE_OPERAND (rhs, 0);
993
994 /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */
995 if (!(lhs == arg0 && rhs == arg1)
996 && !(lhs == arg1 && rhs == arg0))
997 return false;
998
999 cond = COND_EXPR_COND (last_stmt (cond_bb));
1000 result = PHI_RESULT (phi);
1001
1002 /* Only relationals comparing arg[01] against zero are interesting. */
1003 cond_code = TREE_CODE (cond);
1004 if (cond_code != GT_EXPR && cond_code != GE_EXPR
1005 && cond_code != LT_EXPR && cond_code != LE_EXPR)
1006 return false;
1007
1008 /* Make sure the conditional is arg[01] OP y. */
1009 if (TREE_OPERAND (cond, 0) != rhs)
1010 return false;
1011
1012 if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))
1013 ? real_zerop (TREE_OPERAND (cond, 1))
1014 : integer_zerop (TREE_OPERAND (cond, 1)))
1015 ;
1016 else
1017 return false;
1018
1019 /* We need to know which is the true edge and which is the false
1020 edge so that we know if have abs or negative abs. */
1021 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1022
1023 /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
1024 will need to negate the result. Similarly for LT_EXPR/LE_EXPR if
1025 the false edge goes to OTHER_BLOCK. */
1026 if (cond_code == GT_EXPR || cond_code == GE_EXPR)
1027 e = true_edge;
1028 else
1029 e = false_edge;
1030
1031 if (e->dest == middle_bb)
1032 negate = true;
1033 else
1034 negate = false;
1035
1036 result = duplicate_ssa_name (result, NULL);
1037
1038 if (negate)
1039 {
1040 tree tmp = create_tmp_var (TREE_TYPE (result), NULL);
1041 add_referenced_var (tmp);
1042 lhs = make_ssa_name (tmp, NULL);
1043 }
1044 else
1045 lhs = result;
1046
1047 /* Build the modify expression with abs expression. */
1048 new_stmt = build_gimple_modify_stmt (lhs,
1049 build1 (ABS_EXPR, TREE_TYPE (lhs), rhs));
1050 SSA_NAME_DEF_STMT (lhs) = new_stmt;
1051
1052 bsi = bsi_last (cond_bb);
1053 bsi_insert_before (&bsi, new_stmt, BSI_NEW_STMT);
1054
1055 if (negate)
1056 {
1057 /* Get the right BSI. We want to insert after the recently
1058 added ABS_EXPR statement (which we know is the first statement
1059 in the block. */
1060 new_stmt = build_gimple_modify_stmt (result,
1061 build1 (NEGATE_EXPR, TREE_TYPE (lhs),
1062 lhs));
1063 SSA_NAME_DEF_STMT (result) = new_stmt;
1064
1065 bsi_insert_after (&bsi, new_stmt, BSI_NEW_STMT);
1066 }
1067
1068 replace_phi_edge_with_variable (cond_bb, e1, phi, result);
1069
1070 /* Note that we optimized this PHI. */
1071 return true;
1072 }
1073
1074 /* Auxiliary functions to determine the set of memory accesses which
1075 can't trap because they are preceded by accesses to the same memory
1076 portion. We do that for INDIRECT_REFs, so we only need to track
1077 the SSA_NAME of the pointer indirectly referenced. The algorithm
1078 simply is a walk over all instructions in dominator order. When
1079 we see an INDIRECT_REF we determine if we've already seen a same
1080 ref anywhere up to the root of the dominator tree. If we do the
1081 current access can't trap. If we don't see any dominating access
1082 the current access might trap, but might also make later accesses
1083 non-trapping, so we remember it. We need to be careful with loads
1084 or stores, for instance a load might not trap, while a store would,
1085 so if we see a dominating read access this doesn't mean that a later
1086 write access would not trap. Hence we also need to differentiate the
1087 type of access(es) seen.
1088
1089 ??? We currently are very conservative and assume that a load might
1090 trap even if a store doesn't (write-only memory). This probably is
1091 overly conservative. */
1092
1093 /* A hash-table of SSA_NAMEs, and in which basic block an INDIRECT_REF
1094 through it was seen, which would constitute a no-trap region for
1095 same accesses. */
1096 struct name_to_bb
1097 {
1098 tree ssa_name;
1099 basic_block bb;
1100 unsigned store : 1;
1101 };
1102
1103 /* The hash table for remembering what we've seen. */
1104 static htab_t seen_ssa_names;
1105
1106 /* The set of INDIRECT_REFs which can't trap. */
1107 static struct pointer_set_t *nontrap_set;
1108
1109 /* The hash function, based on the pointer to the pointer SSA_NAME. */
1110 static hashval_t
1111 name_to_bb_hash (const void *p)
1112 {
1113 tree n = ((struct name_to_bb *)p)->ssa_name;
1114 return htab_hash_pointer (n) ^ ((struct name_to_bb *)p)->store;
1115 }
1116
1117 /* The equality function of *P1 and *P2. SSA_NAMEs are shared, so
1118 it's enough to simply compare them for equality. */
1119 static int
1120 name_to_bb_eq (const void *p1, const void *p2)
1121 {
1122 const struct name_to_bb *n1 = (const struct name_to_bb *)p1;
1123 const struct name_to_bb *n2 = (const struct name_to_bb *)p2;
1124
1125 return n1->ssa_name == n2->ssa_name && n1->store == n2->store;
1126 }
1127
1128 /* We see a the expression EXP in basic block BB. If it's an interesting
1129 expression (an INDIRECT_REF through an SSA_NAME) possibly insert the
1130 expression into the set NONTRAP or the hash table of seen expressions.
1131 STORE is true if this expression is on the LHS, otherwise it's on
1132 the RHS. */
1133 static void
1134 add_or_mark_expr (basic_block bb, tree exp,
1135 struct pointer_set_t *nontrap, bool store)
1136 {
1137 if (INDIRECT_REF_P (exp)
1138 && TREE_CODE (TREE_OPERAND (exp, 0)) == SSA_NAME)
1139 {
1140 tree name = TREE_OPERAND (exp, 0);
1141 struct name_to_bb map;
1142 void **slot;
1143 struct name_to_bb *n2bb;
1144 basic_block found_bb = 0;
1145
1146 /* Try to find the last seen INDIRECT_REF through the same
1147 SSA_NAME, which can trap. */
1148 map.ssa_name = name;
1149 map.bb = 0;
1150 map.store = store;
1151 slot = htab_find_slot (seen_ssa_names, &map, INSERT);
1152 n2bb = (struct name_to_bb *) *slot;
1153 if (n2bb)
1154 found_bb = n2bb->bb;
1155
1156 /* If we've found a trapping INDIRECT_REF, _and_ it dominates EXP
1157 (it's in a basic block on the path from us to the dominator root)
1158 then we can't trap. */
1159 if (found_bb && found_bb->aux == (void *)1)
1160 {
1161 pointer_set_insert (nontrap, exp);
1162 }
1163 else
1164 {
1165 /* EXP might trap, so insert it into the hash table. */
1166 if (n2bb)
1167 {
1168 n2bb->bb = bb;
1169 }
1170 else
1171 {
1172 n2bb = XNEW (struct name_to_bb);
1173 n2bb->ssa_name = name;
1174 n2bb->bb = bb;
1175 n2bb->store = store;
1176 *slot = n2bb;
1177 }
1178 }
1179 }
1180 }
1181
1182 /* Called by walk_dominator_tree, when entering the block BB. */
1183 static void
1184 nt_init_block (struct dom_walk_data *data ATTRIBUTE_UNUSED, basic_block bb)
1185 {
1186 block_stmt_iterator bsi;
1187 /* Mark this BB as being on the path to dominator root. */
1188 bb->aux = (void*)1;
1189
1190 /* And walk the statements in order. */
1191 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1192 {
1193 tree stmt = bsi_stmt (bsi);
1194
1195 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1196 {
1197 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1198 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1199 add_or_mark_expr (bb, rhs, nontrap_set, false);
1200 add_or_mark_expr (bb, lhs, nontrap_set, true);
1201 }
1202 }
1203 }
1204
1205 /* Called by walk_dominator_tree, when basic block BB is exited. */
1206 static void
1207 nt_fini_block (struct dom_walk_data *data ATTRIBUTE_UNUSED, basic_block bb)
1208 {
1209 /* This BB isn't on the path to dominator root anymore. */
1210 bb->aux = NULL;
1211 }
1212
1213 /* This is the entry point of gathering non trapping memory accesses.
1214 It will do a dominator walk over the whole function, and it will
1215 make use of the bb->aux pointers. It returns a set of trees
1216 (the INDIRECT_REFs itself) which can't trap. */
1217 static struct pointer_set_t *
1218 get_non_trapping (void)
1219 {
1220 struct pointer_set_t *nontrap;
1221 struct dom_walk_data walk_data;
1222
1223 nontrap = pointer_set_create ();
1224 seen_ssa_names = htab_create (128, name_to_bb_hash, name_to_bb_eq,
1225 free);
1226 /* We're going to do a dominator walk, so ensure that we have
1227 dominance information. */
1228 calculate_dominance_info (CDI_DOMINATORS);
1229
1230 /* Setup callbacks for the generic dominator tree walker. */
1231 nontrap_set = nontrap;
1232 walk_data.walk_stmts_backward = false;
1233 walk_data.dom_direction = CDI_DOMINATORS;
1234 walk_data.initialize_block_local_data = NULL;
1235 walk_data.before_dom_children_before_stmts = nt_init_block;
1236 walk_data.before_dom_children_walk_stmts = NULL;
1237 walk_data.before_dom_children_after_stmts = NULL;
1238 walk_data.after_dom_children_before_stmts = NULL;
1239 walk_data.after_dom_children_walk_stmts = NULL;
1240 walk_data.after_dom_children_after_stmts = nt_fini_block;
1241 walk_data.global_data = NULL;
1242 walk_data.block_local_data_size = 0;
1243 walk_data.interesting_blocks = NULL;
1244
1245 init_walk_dominator_tree (&walk_data);
1246 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1247 fini_walk_dominator_tree (&walk_data);
1248 htab_delete (seen_ssa_names);
1249
1250 return nontrap;
1251 }
1252
1253 /* Do the main work of conditional store replacement. We already know
1254 that the recognized pattern looks like so:
1255
1256 split:
1257 if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
1258 MIDDLE_BB:
1259 something
1260 fallthrough (edge E0)
1261 JOIN_BB:
1262 some more
1263
1264 We check that MIDDLE_BB contains only one store, that that store
1265 doesn't trap (not via NOTRAP, but via checking if an access to the same
1266 memory location dominates us) and that the store has a "simple" RHS. */
1267
1268 static bool
1269 cond_store_replacement (basic_block middle_bb, basic_block join_bb,
1270 edge e0, edge e1, struct pointer_set_t *nontrap)
1271 {
1272 tree assign = last_and_only_stmt (middle_bb);
1273 tree lhs, rhs, newexpr, name;
1274 tree newphi;
1275 block_stmt_iterator bsi;
1276
1277 /* Check if middle_bb contains of only one store. */
1278 if (!assign
1279 || TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
1280 return false;
1281
1282 lhs = GIMPLE_STMT_OPERAND (assign, 0);
1283 if (!INDIRECT_REF_P (lhs))
1284 return false;
1285 rhs = GIMPLE_STMT_OPERAND (assign, 1);
1286 if (TREE_CODE (rhs) != SSA_NAME && !is_gimple_min_invariant (rhs))
1287 return false;
1288 /* Prove that we can move the store down. We could also check
1289 TREE_THIS_NOTRAP here, but in that case we also could move stores,
1290 whose value is not available readily, which we want to avoid. */
1291 if (!pointer_set_contains (nontrap, lhs))
1292 return false;
1293
1294 /* Now we've checked the constraints, so do the transformation:
1295 1) Remove the single store. */
1296 mark_symbols_for_renaming (assign);
1297 bsi = bsi_for_stmt (assign);
1298 bsi_remove (&bsi, true);
1299
1300 /* 2) Create a temporary where we can store the old content
1301 of the memory touched by the store, if we need to. */
1302 if (!condstoretemp || TREE_TYPE (lhs) != TREE_TYPE (condstoretemp))
1303 {
1304 condstoretemp = create_tmp_var (TREE_TYPE (lhs), "cstore");
1305 get_var_ann (condstoretemp);
1306 if (TREE_CODE (TREE_TYPE (lhs)) == COMPLEX_TYPE
1307 || TREE_CODE (TREE_TYPE (lhs)) == VECTOR_TYPE)
1308 DECL_GIMPLE_REG_P (condstoretemp) = 1;
1309 }
1310 add_referenced_var (condstoretemp);
1311
1312 /* 3) Insert a load from the memory of the store to the temporary
1313 on the edge which did not contain the store. */
1314 lhs = unshare_expr (lhs);
1315 newexpr = build_gimple_modify_stmt (condstoretemp, lhs);
1316 name = make_ssa_name (condstoretemp, newexpr);
1317 GIMPLE_STMT_OPERAND (newexpr, 0) = name;
1318 mark_symbols_for_renaming (newexpr);
1319 bsi_insert_on_edge (e1, newexpr);
1320
1321 /* 4) Create a PHI node at the join block, with one argument
1322 holding the old RHS, and the other holding the temporary
1323 where we stored the old memory contents. */
1324 newphi = create_phi_node (condstoretemp, join_bb);
1325 add_phi_arg (newphi, rhs, e0);
1326 add_phi_arg (newphi, name, e1);
1327
1328 lhs = unshare_expr (lhs);
1329 newexpr = build_gimple_modify_stmt (lhs, PHI_RESULT (newphi));
1330 mark_symbols_for_renaming (newexpr);
1331
1332 /* 5) Insert that PHI node. */
1333 bsi = bsi_start (join_bb);
1334 while (!bsi_end_p (bsi) && TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
1335 bsi_next (&bsi);
1336 if (bsi_end_p (bsi))
1337 {
1338 bsi = bsi_last (join_bb);
1339 bsi_insert_after (&bsi, newexpr, BSI_NEW_STMT);
1340 }
1341 else
1342 bsi_insert_before (&bsi, newexpr, BSI_NEW_STMT);
1343
1344 return true;
1345 }
1346
1347 /* Always do these optimizations if we have SSA
1348 trees to work on. */
1349 static bool
1350 gate_phiopt (void)
1351 {
1352 return 1;
1353 }
1354
1355 struct tree_opt_pass pass_phiopt =
1356 {
1357 "phiopt", /* name */
1358 gate_phiopt, /* gate */
1359 tree_ssa_phiopt, /* execute */
1360 NULL, /* sub */
1361 NULL, /* next */
1362 0, /* static_pass_number */
1363 TV_TREE_PHIOPT, /* tv_id */
1364 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1365 0, /* properties_provided */
1366 0, /* properties_destroyed */
1367 0, /* todo_flags_start */
1368 TODO_dump_func
1369 | TODO_ggc_collect
1370 | TODO_verify_ssa
1371 | TODO_verify_flow
1372 | TODO_verify_stmts, /* todo_flags_finish */
1373 0 /* letter */
1374 };
1375
1376 static bool
1377 gate_cselim (void)
1378 {
1379 return flag_tree_cselim;
1380 }
1381
1382 struct tree_opt_pass pass_cselim =
1383 {
1384 "cselim", /* name */
1385 gate_cselim, /* gate */
1386 tree_ssa_cs_elim, /* execute */
1387 NULL, /* sub */
1388 NULL, /* next */
1389 0, /* static_pass_number */
1390 TV_TREE_PHIOPT, /* tv_id */
1391 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1392 0, /* properties_provided */
1393 0, /* properties_destroyed */
1394 0, /* todo_flags_start */
1395 TODO_dump_func
1396 | TODO_ggc_collect
1397 | TODO_verify_ssa
1398 | TODO_verify_flow
1399 | TODO_verify_stmts, /* todo_flags_finish */
1400 0 /* letter */
1401 };