OSDN Git Service

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