OSDN Git Service

a134244bd9fa70efce5de144ecc9df5f6d1ee9a7
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-dom.c
1 /* SSA Dominator optimizations for trees
2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
3    Free Software Foundation, Inc.
4    Contributed by Diego Novillo <dnovillo@redhat.com>
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
12
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "flags.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "ggc.h"
31 #include "basic-block.h"
32 #include "cfgloop.h"
33 #include "output.h"
34 #include "expr.h"
35 #include "function.h"
36 #include "diagnostic.h"
37 #include "timevar.h"
38 #include "tree-dump.h"
39 #include "tree-flow.h"
40 #include "domwalk.h"
41 #include "real.h"
42 #include "tree-pass.h"
43 #include "tree-ssa-propagate.h"
44 #include "langhooks.h"
45 #include "params.h"
46
47 /* This file implements optimizations on the dominator tree.  */
48
49 /* Representation of a "naked" right-hand-side expression, to be used
50    in recording available expressions in the expression hash table.  */
51
52 enum expr_kind
53 {
54   EXPR_SINGLE,
55   EXPR_UNARY,
56   EXPR_BINARY,
57   EXPR_CALL
58 };
59
60 struct hashable_expr
61 {
62   tree type;
63   enum expr_kind kind;
64   union {
65     struct { tree rhs; } single;
66     struct { enum tree_code op;  tree opnd; } unary;
67     struct { enum tree_code op;  tree opnd0; tree opnd1; } binary;
68     struct { tree fn; bool pure; size_t nargs; tree *args; } call;
69   } ops;
70 };
71
72 /* Structure for recording known values of a conditional expression
73    at the exits from its block.  */
74
75 struct cond_equivalence
76 {
77   struct hashable_expr cond;
78   tree value;
79 };
80
81 /* Structure for recording edge equivalences as well as any pending
82    edge redirections during the dominator optimizer.
83
84    Computing and storing the edge equivalences instead of creating
85    them on-demand can save significant amounts of time, particularly
86    for pathological cases involving switch statements.  
87
88    These structures live for a single iteration of the dominator
89    optimizer in the edge's AUX field.  At the end of an iteration we
90    free each of these structures and update the AUX field to point
91    to any requested redirection target (the code for updating the
92    CFG and SSA graph for edge redirection expects redirection edge
93    targets to be in the AUX field for each edge.  */
94
95 struct edge_info
96 {
97   /* If this edge creates a simple equivalence, the LHS and RHS of
98      the equivalence will be stored here.  */
99   tree lhs;
100   tree rhs;
101
102   /* Traversing an edge may also indicate one or more particular conditions
103      are true or false.  The number of recorded conditions can vary, but
104      can be determined by the condition's code.  So we have an array
105      and its maximum index rather than use a varray.  */
106   struct cond_equivalence *cond_equivalences;
107   unsigned int max_cond_equivalences;
108 };
109
110 /* Hash table with expressions made available during the renaming process.
111    When an assignment of the form X_i = EXPR is found, the statement is
112    stored in this table.  If the same expression EXPR is later found on the
113    RHS of another statement, it is replaced with X_i (thus performing
114    global redundancy elimination).  Similarly as we pass through conditionals
115    we record the conditional itself as having either a true or false value
116    in this table.  */
117 static htab_t avail_exprs;
118
119 /* Stack of available expressions in AVAIL_EXPRs.  Each block pushes any
120    expressions it enters into the hash table along with a marker entry
121    (null).  When we finish processing the block, we pop off entries and
122    remove the expressions from the global hash table until we hit the
123    marker.  */
124 typedef struct expr_hash_elt * expr_hash_elt_t;
125 DEF_VEC_P(expr_hash_elt_t);
126 DEF_VEC_ALLOC_P(expr_hash_elt_t,heap);
127
128 static VEC(expr_hash_elt_t,heap) *avail_exprs_stack;
129
130 /* Stack of statements we need to rescan during finalization for newly
131    exposed variables.
132
133    Statement rescanning must occur after the current block's available
134    expressions are removed from AVAIL_EXPRS.  Else we may change the
135    hash code for an expression and be unable to find/remove it from
136    AVAIL_EXPRS.  */
137 static VEC(gimple_p,heap) *stmts_to_rescan;
138
139 /* Structure for entries in the expression hash table.  */
140
141 struct expr_hash_elt
142 {
143   /* The value (lhs) of this expression.  */
144   tree lhs;
145
146   /* The expression (rhs) we want to record.  */
147   struct hashable_expr expr;
148
149   /* The stmt pointer if this element corresponds to a statement.  */
150   gimple stmt;
151
152   /* The hash value for RHS.  */
153   hashval_t hash;
154
155   /* A unique stamp, typically the address of the hash
156      element itself, used in removing entries from the table.  */
157   struct expr_hash_elt *stamp;
158 };
159
160 /* Stack of dest,src pairs that need to be restored during finalization.
161
162    A NULL entry is used to mark the end of pairs which need to be
163    restored during finalization of this block.  */
164 static VEC(tree,heap) *const_and_copies_stack;
165
166 /* Track whether or not we have changed the control flow graph.  */
167 static bool cfg_altered;
168
169 /* Bitmap of blocks that have had EH statements cleaned.  We should
170    remove their dead edges eventually.  */
171 static bitmap need_eh_cleanup;
172
173 /* Statistics for dominator optimizations.  */
174 struct opt_stats_d
175 {
176   long num_stmts;
177   long num_exprs_considered;
178   long num_re;
179   long num_const_prop;
180   long num_copy_prop;
181 };
182
183 static struct opt_stats_d opt_stats;
184
185 /* Local functions.  */
186 static void optimize_stmt (struct dom_walk_data *, 
187                            basic_block,
188                            gimple_stmt_iterator);
189 static tree lookup_avail_expr (gimple, bool);
190 static hashval_t avail_expr_hash (const void *);
191 static hashval_t real_avail_expr_hash (const void *);
192 static int avail_expr_eq (const void *, const void *);
193 static void htab_statistics (FILE *, htab_t);
194 static void record_cond (struct cond_equivalence *);
195 static void record_const_or_copy (tree, tree);
196 static void record_equality (tree, tree);
197 static void record_equivalences_from_phis (basic_block);
198 static void record_equivalences_from_incoming_edge (basic_block);
199 static bool eliminate_redundant_computations (gimple_stmt_iterator *);
200 static void record_equivalences_from_stmt (gimple, int);
201 static void dom_thread_across_edge (struct dom_walk_data *, edge);
202 static void dom_opt_finalize_block (struct dom_walk_data *, basic_block);
203 static void dom_opt_initialize_block (struct dom_walk_data *, basic_block);
204 static void propagate_to_outgoing_edges (struct dom_walk_data *, basic_block);
205 static void remove_local_expressions_from_table (void);
206 static void restore_vars_to_original_value (void);
207 static edge single_incoming_edge_ignoring_loop_edges (basic_block);
208
209
210 /* Given a statement STMT, initialize the hash table element pointed to
211    by ELEMENT.  */
212
213 static void
214 initialize_hash_element (gimple stmt, tree lhs,
215                          struct expr_hash_elt *element)
216 {
217   enum gimple_code code = gimple_code (stmt);
218   struct hashable_expr *expr = &element->expr;
219
220   if (code == GIMPLE_ASSIGN)
221     {
222       enum tree_code subcode = gimple_assign_rhs_code (stmt);
223
224       expr->type = NULL_TREE;
225       
226       switch (get_gimple_rhs_class (subcode))
227         {
228         case GIMPLE_SINGLE_RHS:
229           expr->kind = EXPR_SINGLE;
230           expr->ops.single.rhs = gimple_assign_rhs1 (stmt);
231           break;
232         case GIMPLE_UNARY_RHS:
233           expr->kind = EXPR_UNARY;
234           expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
235           expr->ops.unary.op = subcode;
236           expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
237           break;
238         case GIMPLE_BINARY_RHS:
239           expr->kind = EXPR_BINARY;
240           expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
241           expr->ops.binary.op = subcode;
242           expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt);
243           expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt);
244           break;
245         default:
246           gcc_unreachable ();
247         }
248     }
249   else if (code == GIMPLE_COND)
250     {
251       expr->type = boolean_type_node;
252       expr->kind = EXPR_BINARY;
253       expr->ops.binary.op = gimple_cond_code (stmt);
254       expr->ops.binary.opnd0 = gimple_cond_lhs (stmt);
255       expr->ops.binary.opnd1 = gimple_cond_rhs (stmt);
256     }
257   else if (code == GIMPLE_CALL)
258     {
259       size_t nargs = gimple_call_num_args (stmt);
260       size_t i;
261
262       gcc_assert (gimple_call_lhs (stmt));
263
264       expr->type = TREE_TYPE (gimple_call_lhs (stmt));
265       expr->kind = EXPR_CALL;
266       expr->ops.call.fn = gimple_call_fn (stmt);
267
268       if (gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))
269         expr->ops.call.pure = true;
270       else 
271         expr->ops.call.pure = false;
272
273       expr->ops.call.nargs = nargs;
274       expr->ops.call.args = (tree *) xcalloc (nargs, sizeof (tree));
275       for (i = 0; i < nargs; i++)
276         expr->ops.call.args[i] = gimple_call_arg (stmt, i);
277     }
278   else if (code == GIMPLE_SWITCH)
279     {
280       expr->type = TREE_TYPE (gimple_switch_index (stmt));
281       expr->kind = EXPR_SINGLE;
282       expr->ops.single.rhs = gimple_switch_index (stmt);
283     }
284   else if (code == GIMPLE_GOTO)
285     {
286       expr->type = TREE_TYPE (gimple_goto_dest (stmt));
287       expr->kind = EXPR_SINGLE;
288       expr->ops.single.rhs = gimple_goto_dest (stmt);
289     }
290   else
291     gcc_unreachable ();
292
293   element->lhs = lhs;
294   element->stmt = stmt;
295   element->hash = avail_expr_hash (element);
296   element->stamp = element;
297 }
298
299 /* Given a conditional expression COND as a tree, initialize
300    a hashable_expr expression EXPR.  The conditional must be a
301    comparison or logical negation.  A constant or a variable is
302    not permitted.  */
303
304 static void
305 initialize_expr_from_cond (tree cond, struct hashable_expr *expr)
306 {
307   expr->type = boolean_type_node;
308   
309   if (COMPARISON_CLASS_P (cond))
310     {
311       expr->kind = EXPR_BINARY;
312       expr->ops.binary.op = TREE_CODE (cond);
313       expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0);
314       expr->ops.binary.opnd1 = TREE_OPERAND (cond, 1);
315     }
316   else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
317     {
318       expr->kind = EXPR_UNARY;
319       expr->ops.unary.op = TRUTH_NOT_EXPR;
320       expr->ops.unary.opnd = TREE_OPERAND (cond, 0);
321     }
322   else
323     gcc_unreachable ();
324 }
325
326 /* Given a hashable_expr expression EXPR and an LHS,
327    initialize the hash table element pointed to by ELEMENT.  */
328
329 static void
330 initialize_hash_element_from_expr (struct hashable_expr *expr,
331                                    tree lhs,
332                                    struct expr_hash_elt *element)
333 {
334   element->expr = *expr;
335   element->lhs = lhs;
336   element->stmt = NULL;
337   element->hash = avail_expr_hash (element);
338   element->stamp = element;
339 }
340
341 /* Compare two hashable_expr structures for equivalence.
342    They are considered equivalent when the the expressions
343    they denote must necessarily be equal.  The logic is intended
344    to follow that of operand_equal_p in fold-const.c  */
345
346 static bool
347 hashable_expr_equal_p (const struct hashable_expr *expr0,
348                         const struct hashable_expr *expr1)
349 {
350   tree type0 = expr0->type;
351   tree type1 = expr1->type;
352
353   /* If either type is NULL, there is nothing to check.  */
354   if ((type0 == NULL_TREE) ^ (type1 == NULL_TREE))
355     return false;
356
357   /* If both types don't have the same signedness, precision, and mode,
358      then we can't consider  them equal.  */
359   if (type0 != type1
360       && (TREE_CODE (type0) == ERROR_MARK
361           || TREE_CODE (type1) == ERROR_MARK
362           || TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1)
363           || TYPE_PRECISION (type0) != TYPE_PRECISION (type1)
364           || TYPE_MODE (type0) != TYPE_MODE (type1)))
365     return false;
366
367   if (expr0->kind != expr1->kind)
368     return false;
369
370   switch (expr0->kind)
371     {
372     case EXPR_SINGLE:
373       return operand_equal_p (expr0->ops.single.rhs,
374                               expr1->ops.single.rhs, 0);
375
376     case EXPR_UNARY:
377       if (expr0->ops.unary.op != expr1->ops.unary.op)
378         return false;
379
380       if ((CONVERT_EXPR_CODE_P (expr0->ops.unary.op)
381            || expr0->ops.unary.op == NON_LVALUE_EXPR)
382           && TYPE_UNSIGNED (expr0->type) != TYPE_UNSIGNED (expr1->type))
383         return false;
384
385       return operand_equal_p (expr0->ops.unary.opnd,
386                               expr1->ops.unary.opnd, 0);
387
388     case EXPR_BINARY:
389       {
390         if (expr0->ops.binary.op != expr1->ops.binary.op)
391           return false;
392
393         if (operand_equal_p (expr0->ops.binary.opnd0,
394                              expr1->ops.binary.opnd0, 0)
395             && operand_equal_p (expr0->ops.binary.opnd1,
396                                 expr1->ops.binary.opnd1, 0))
397           return true;
398
399         /* For commutative ops, allow the other order.  */
400         return (commutative_tree_code (expr0->ops.binary.op)
401                 && operand_equal_p (expr0->ops.binary.opnd0,
402                                     expr1->ops.binary.opnd1, 0)
403                 && operand_equal_p (expr0->ops.binary.opnd1,
404                                     expr1->ops.binary.opnd0, 0));
405       }
406
407     case EXPR_CALL:
408       {
409         size_t i;
410
411         /* If the calls are to different functions, then they
412            clearly cannot be equal.  */
413         if (! operand_equal_p (expr0->ops.call.fn,
414                                expr1->ops.call.fn, 0))
415           return false;
416
417         if (! expr0->ops.call.pure)
418           return false;
419
420         if (expr0->ops.call.nargs !=  expr1->ops.call.nargs)
421           return false;
422
423         for (i = 0; i < expr0->ops.call.nargs; i++)
424           if (! operand_equal_p (expr0->ops.call.args[i],
425                                  expr1->ops.call.args[i], 0))
426             return false;
427
428         return true;
429       }
430      
431     default:
432       gcc_unreachable ();
433     }
434 }
435
436 /* Compute a hash value for a hashable_expr value EXPR and a
437    previously accumulated hash value VAL.  If two hashable_expr
438    values compare equal with hashable_expr_equal_p, they must
439    hash to the same value, given an identical value of VAL.
440    The logic is intended to follow iterative_hash_expr in tree.c.  */
441
442 static hashval_t
443 iterative_hash_hashable_expr (const struct hashable_expr *expr, hashval_t val)
444 {
445   switch (expr->kind)
446     {
447     case EXPR_SINGLE:
448       val = iterative_hash_expr (expr->ops.single.rhs, val);
449       break;
450
451     case EXPR_UNARY:
452       val = iterative_hash_object (expr->ops.unary.op, val);
453
454       /* Make sure to include signedness in the hash computation.
455          Don't hash the type, that can lead to having nodes which
456          compare equal according to operand_equal_p, but which
457          have different hash codes.  */
458       if (CONVERT_EXPR_CODE_P (expr->ops.unary.op)
459           || expr->ops.unary.op == NON_LVALUE_EXPR)
460         val += TYPE_UNSIGNED (expr->type);
461
462       val = iterative_hash_expr (expr->ops.unary.opnd, val);
463       break;
464
465     case EXPR_BINARY:
466       val = iterative_hash_object (expr->ops.binary.op, val);
467       if (commutative_tree_code (expr->ops.binary.op))
468           val = iterative_hash_exprs_commutative (expr->ops.binary.opnd0,
469                                                   expr->ops.binary.opnd1, val);
470       else
471         {
472           val = iterative_hash_expr (expr->ops.binary.opnd0, val);
473           val = iterative_hash_expr (expr->ops.binary.opnd1, val);
474         }
475       break;
476
477     case EXPR_CALL:
478       {
479         size_t i;
480         enum tree_code code = CALL_EXPR;
481
482         val = iterative_hash_object (code, val);
483         val = iterative_hash_expr (expr->ops.call.fn, val);
484         for (i = 0; i < expr->ops.call.nargs; i++)
485           val = iterative_hash_expr (expr->ops.call.args[i], val);
486       }
487       break;
488      
489     default:
490       gcc_unreachable ();
491     }
492
493   return val;
494 }
495
496 /* Print a diagnostic dump of an expression hash table entry.  */
497
498 static void
499 print_expr_hash_elt (FILE * stream, const struct expr_hash_elt *element)
500 {
501   if (element->stmt)
502     fprintf (stream, "STMT ");
503   else
504     fprintf (stream, "COND ");
505
506   if (element->lhs)
507     {
508       print_generic_expr (stream, element->lhs, 0);
509       fprintf (stream, " = ");
510     }
511   
512   switch (element->expr.kind)
513     {
514       case EXPR_SINGLE:
515         print_generic_expr (stream, element->expr.ops.single.rhs, 0);
516         break;
517
518       case EXPR_UNARY:
519         fprintf (stream, "%s ", tree_code_name[element->expr.ops.unary.op]);
520         print_generic_expr (stream, element->expr.ops.unary.opnd, 0);
521         break;
522
523       case EXPR_BINARY:
524         print_generic_expr (stream, element->expr.ops.binary.opnd0, 0);
525         fprintf (stream, " %s ", tree_code_name[element->expr.ops.binary.op]);
526         print_generic_expr (stream, element->expr.ops.binary.opnd1, 0);
527         break;
528
529       case EXPR_CALL:
530         {
531           size_t i;
532           size_t nargs = element->expr.ops.call.nargs;
533
534           print_generic_expr (stream, element->expr.ops.call.fn, 0);
535           fprintf (stream, " (");
536           for (i = 0; i < nargs; i++)
537             {
538               print_generic_expr (stream, element->expr.ops.call.args[i], 0);
539               if (i + 1 < nargs)
540                 fprintf (stream, ", ");
541             }
542           fprintf (stream, ")");
543         }
544         break;
545     }
546   fprintf (stream, "\n");
547
548   if (element->stmt)
549     {
550       fprintf (stream, "          ");
551       print_gimple_stmt (stream, element->stmt, 0, 0);
552     }
553 }
554
555 /* Delete an expr_hash_elt and reclaim its storage.  */
556
557 static void
558 free_expr_hash_elt (void *elt)
559 {
560   struct expr_hash_elt *element = ((struct expr_hash_elt *)elt);
561
562   if (element->expr.kind == EXPR_CALL)
563     free (element->expr.ops.call.args);
564
565   free (element);
566 }
567
568 /* Allocate an EDGE_INFO for edge E and attach it to E.
569    Return the new EDGE_INFO structure.  */
570
571 static struct edge_info *
572 allocate_edge_info (edge e)
573 {
574   struct edge_info *edge_info;
575
576   edge_info = XCNEW (struct edge_info);
577
578   e->aux = edge_info;
579   return edge_info;
580 }
581
582 /* Free all EDGE_INFO structures associated with edges in the CFG.
583    If a particular edge can be threaded, copy the redirection
584    target from the EDGE_INFO structure into the edge's AUX field
585    as required by code to update the CFG and SSA graph for
586    jump threading.  */
587
588 static void
589 free_all_edge_infos (void)
590 {
591   basic_block bb;
592   edge_iterator ei;
593   edge e;
594
595   FOR_EACH_BB (bb)
596     {
597       FOR_EACH_EDGE (e, ei, bb->preds)
598         {
599          struct edge_info *edge_info = (struct edge_info *) e->aux;
600
601           if (edge_info)
602             {
603               if (edge_info->cond_equivalences)
604                 free (edge_info->cond_equivalences);
605               free (edge_info);
606               e->aux = NULL;
607             }
608         }
609     }
610 }
611
612 /* Jump threading, redundancy elimination and const/copy propagation. 
613
614    This pass may expose new symbols that need to be renamed into SSA.  For
615    every new symbol exposed, its corresponding bit will be set in
616    VARS_TO_RENAME.  */
617
618 static unsigned int
619 tree_ssa_dominator_optimize (void)
620 {
621   struct dom_walk_data walk_data;
622
623   memset (&opt_stats, 0, sizeof (opt_stats));
624
625   /* Create our hash tables.  */
626   avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free_expr_hash_elt);
627   avail_exprs_stack = VEC_alloc (expr_hash_elt_t, heap, 20);
628   const_and_copies_stack = VEC_alloc (tree, heap, 20);
629   stmts_to_rescan = VEC_alloc (gimple_p, heap, 20);
630   need_eh_cleanup = BITMAP_ALLOC (NULL);
631
632   /* Setup callbacks for the generic dominator tree walker.  */
633   walk_data.walk_stmts_backward = false;
634   walk_data.dom_direction = CDI_DOMINATORS;
635   walk_data.initialize_block_local_data = NULL;
636   walk_data.before_dom_children_before_stmts = dom_opt_initialize_block;
637   walk_data.before_dom_children_walk_stmts = optimize_stmt;
638   walk_data.before_dom_children_after_stmts = propagate_to_outgoing_edges;
639   walk_data.after_dom_children_before_stmts = NULL;
640   walk_data.after_dom_children_walk_stmts = NULL;
641   walk_data.after_dom_children_after_stmts = dom_opt_finalize_block;
642   /* Right now we only attach a dummy COND_EXPR to the global data pointer.
643      When we attach more stuff we'll need to fill this out with a real
644      structure.  */
645   walk_data.global_data = NULL;
646   walk_data.block_local_data_size = 0;
647   walk_data.interesting_blocks = NULL;
648
649   /* Now initialize the dominator walker.  */
650   init_walk_dominator_tree (&walk_data);
651
652   calculate_dominance_info (CDI_DOMINATORS);
653   cfg_altered = false;
654
655   /* We need to know loop structures in order to avoid destroying them
656      in jump threading.  Note that we still can e.g. thread through loop
657      headers to an exit edge, or through loop header to the loop body, assuming
658      that we update the loop info.  */
659   loop_optimizer_init (LOOPS_HAVE_SIMPLE_LATCHES);
660
661   /* Initialize the value-handle array.  */
662   threadedge_initialize_values ();
663
664   /* We need accurate information regarding back edges in the CFG
665      for jump threading; this may include back edges that are not part of
666      a single loop.  */
667   mark_dfs_back_edges ();
668       
669   /* Recursively walk the dominator tree optimizing statements.  */
670   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
671
672   {
673     gimple_stmt_iterator gsi;
674     basic_block bb;
675     FOR_EACH_BB (bb)
676       {for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
677           update_stmt_if_modified (gsi_stmt (gsi));
678       }
679   }
680
681   /* If we exposed any new variables, go ahead and put them into
682      SSA form now, before we handle jump threading.  This simplifies
683      interactions between rewriting of _DECL nodes into SSA form
684      and rewriting SSA_NAME nodes into SSA form after block
685      duplication and CFG manipulation.  */
686   update_ssa (TODO_update_ssa);
687
688   free_all_edge_infos ();
689
690   /* Thread jumps, creating duplicate blocks as needed.  */
691   cfg_altered |= thread_through_all_blocks (first_pass_instance);
692
693   if (cfg_altered)
694     free_dominance_info (CDI_DOMINATORS);
695
696   /* Removal of statements may make some EH edges dead.  Purge
697      such edges from the CFG as needed.  */
698   if (!bitmap_empty_p (need_eh_cleanup))
699     {
700       unsigned i;
701       bitmap_iterator bi;
702
703       /* Jump threading may have created forwarder blocks from blocks
704          needing EH cleanup; the new successor of these blocks, which
705          has inherited from the original block, needs the cleanup.  */
706       EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi)
707         {
708           basic_block bb = BASIC_BLOCK (i);
709           if (single_succ_p (bb) == 1
710               && (single_succ_edge (bb)->flags & EDGE_EH) == 0)
711             {
712               bitmap_clear_bit (need_eh_cleanup, i);
713               bitmap_set_bit (need_eh_cleanup, single_succ (bb)->index);
714             }
715         }
716
717       gimple_purge_all_dead_eh_edges (need_eh_cleanup);
718       bitmap_zero (need_eh_cleanup);
719     }
720
721   statistics_counter_event (cfun, "Redundant expressions eliminated",
722                             opt_stats.num_re);
723   statistics_counter_event (cfun, "Constants propagated",
724                             opt_stats.num_const_prop);
725   statistics_counter_event (cfun, "Copies propagated",
726                             opt_stats.num_copy_prop);
727
728   /* Debugging dumps.  */
729   if (dump_file && (dump_flags & TDF_STATS))
730     dump_dominator_optimization_stats (dump_file);
731
732   loop_optimizer_finalize ();
733
734   /* Delete our main hashtable.  */
735   htab_delete (avail_exprs);
736
737   /* And finalize the dominator walker.  */
738   fini_walk_dominator_tree (&walk_data);
739
740   /* Free asserted bitmaps and stacks.  */
741   BITMAP_FREE (need_eh_cleanup);
742   
743   VEC_free (expr_hash_elt_t, heap, avail_exprs_stack);
744   VEC_free (tree, heap, const_and_copies_stack);
745   VEC_free (gimple_p, heap, stmts_to_rescan);
746   
747   /* Free the value-handle array.  */
748   threadedge_finalize_values ();
749   ssa_name_values = NULL;
750
751   return 0;
752 }
753
754 static bool
755 gate_dominator (void)
756 {
757   return flag_tree_dom != 0;
758 }
759
760 struct gimple_opt_pass pass_dominator = 
761 {
762  {
763   GIMPLE_PASS,
764   "dom",                                /* name */
765   gate_dominator,                       /* gate */
766   tree_ssa_dominator_optimize,          /* execute */
767   NULL,                                 /* sub */
768   NULL,                                 /* next */
769   0,                                    /* static_pass_number */
770   TV_TREE_SSA_DOMINATOR_OPTS,           /* tv_id */
771   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
772   0,                                    /* properties_provided */
773   0,                                    /* properties_destroyed */
774   0,                                    /* todo_flags_start */
775   TODO_dump_func
776     | TODO_update_ssa
777     | TODO_cleanup_cfg
778     | TODO_verify_ssa                   /* todo_flags_finish */
779  }
780 };
781
782
783 /* Given a conditional statement CONDSTMT, convert the
784    condition to a canonical form.  */
785
786 static void
787 canonicalize_comparison (gimple condstmt)
788 {
789   tree op0;
790   tree op1;
791   enum tree_code code;
792
793   gcc_assert (gimple_code (condstmt) == GIMPLE_COND);
794
795   op0 = gimple_cond_lhs (condstmt);
796   op1 = gimple_cond_rhs (condstmt);
797
798   code = gimple_cond_code (condstmt);
799
800   /* If it would be profitable to swap the operands, then do so to
801      canonicalize the statement, enabling better optimization.
802
803      By placing canonicalization of such expressions here we
804      transparently keep statements in canonical form, even
805      when the statement is modified.  */
806   if (tree_swap_operands_p (op0, op1, false))
807     {
808       /* For relationals we need to swap the operands
809          and change the code.  */
810       if (code == LT_EXPR
811           || code == GT_EXPR
812           || code == LE_EXPR
813           || code == GE_EXPR)
814         {
815           code = swap_tree_comparison (code);
816
817           gimple_cond_set_code (condstmt, code);
818           gimple_cond_set_lhs (condstmt, op1);
819           gimple_cond_set_rhs (condstmt, op0);
820
821           update_stmt (condstmt);
822         }
823     }
824 }
825
826 /* Initialize local stacks for this optimizer and record equivalences
827    upon entry to BB.  Equivalences can come from the edge traversed to
828    reach BB or they may come from PHI nodes at the start of BB.  */
829
830 static void
831 dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
832                           basic_block bb)
833 {
834   if (dump_file && (dump_flags & TDF_DETAILS))
835     fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
836
837   /* Push a marker on the stacks of local information so that we know how
838      far to unwind when we finalize this block.  */
839   VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
840   VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
841
842   record_equivalences_from_incoming_edge (bb);
843
844   /* PHI nodes can create equivalences too.  */
845   record_equivalences_from_phis (bb);
846 }
847
848 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
849    LIMIT entries left in LOCALs.  */
850
851 static void
852 remove_local_expressions_from_table (void)
853 {
854   /* Remove all the expressions made available in this block.  */
855   while (VEC_length (expr_hash_elt_t, avail_exprs_stack) > 0)
856     {
857       struct expr_hash_elt element;
858       expr_hash_elt_t victim = VEC_pop (expr_hash_elt_t, avail_exprs_stack);
859
860       if (victim == NULL)
861         break;
862
863       element = *victim;
864
865       /* This must precede the actual removal from the hash table,
866          as ELEMENT and the table entry may share a call argument
867          vector which will be freed during removal.  */
868       if (dump_file && (dump_flags & TDF_DETAILS))
869         {
870           fprintf (dump_file, "<<<< ");
871           print_expr_hash_elt (dump_file, &element);
872         }
873
874       htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
875     }
876 }
877
878 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
879    CONST_AND_COPIES to its original state, stopping when we hit a
880    NULL marker.  */
881
882 static void
883 restore_vars_to_original_value (void)
884 {
885   while (VEC_length (tree, const_and_copies_stack) > 0)
886     {
887       tree prev_value, dest;
888
889       dest = VEC_pop (tree, const_and_copies_stack);
890
891       if (dest == NULL)
892         break;
893
894       if (dump_file && (dump_flags & TDF_DETAILS))
895         {
896           fprintf (dump_file, "<<<< COPY ");
897           print_generic_expr (dump_file, dest, 0);
898           fprintf (dump_file, " = ");
899           print_generic_expr (dump_file, SSA_NAME_VALUE (dest), 0);
900           fprintf (dump_file, "\n");
901         }
902
903       prev_value = VEC_pop (tree, const_and_copies_stack);
904       set_ssa_name_value (dest, prev_value);
905     }
906 }
907
908 /* A trivial wrapper so that we can present the generic jump
909    threading code with a simple API for simplifying statements.  */
910 static tree
911 simplify_stmt_for_jump_threading (gimple stmt,
912                                   gimple within_stmt ATTRIBUTE_UNUSED)
913 {
914   return lookup_avail_expr (stmt, false);
915 }
916
917 /* Wrapper for common code to attempt to thread an edge.  For example,
918    it handles lazily building the dummy condition and the bookkeeping
919    when jump threading is successful.  */
920
921 static void
922 dom_thread_across_edge (struct dom_walk_data *walk_data, edge e)
923 {
924   if (! walk_data->global_data)
925   {
926     gimple dummy_cond =
927         gimple_build_cond (NE_EXPR,
928                            integer_zero_node, integer_zero_node,
929                            NULL, NULL);
930     walk_data->global_data = dummy_cond;
931   }
932
933   thread_across_edge ((gimple) walk_data->global_data, e, false,
934                       &const_and_copies_stack,
935                       simplify_stmt_for_jump_threading);
936 }
937
938 /* We have finished processing the dominator children of BB, perform
939    any finalization actions in preparation for leaving this node in
940    the dominator tree.  */
941
942 static void
943 dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
944 {
945   gimple last;
946
947   /* If we have an outgoing edge to a block with multiple incoming and
948      outgoing edges, then we may be able to thread the edge, i.e., we
949      may be able to statically determine which of the outgoing edges
950      will be traversed when the incoming edge from BB is traversed.  */
951   if (single_succ_p (bb)
952       && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0
953       && potentially_threadable_block (single_succ (bb)))
954     {
955       dom_thread_across_edge (walk_data, single_succ_edge (bb));
956     }
957   else if ((last = last_stmt (bb))
958            && gimple_code (last) == GIMPLE_COND
959            && EDGE_COUNT (bb->succs) == 2
960            && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0
961            && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0)
962     {
963       edge true_edge, false_edge;
964
965       extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
966
967       /* Only try to thread the edge if it reaches a target block with
968          more than one predecessor and more than one successor.  */
969       if (potentially_threadable_block (true_edge->dest))
970         {
971           struct edge_info *edge_info;
972           unsigned int i;
973
974           /* Push a marker onto the available expression stack so that we
975              unwind any expressions related to the TRUE arm before processing
976              the false arm below.  */
977           VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
978           VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
979
980           edge_info = (struct edge_info *) true_edge->aux;
981
982           /* If we have info associated with this edge, record it into
983              our equivalence tables.  */
984           if (edge_info)
985             {
986               struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
987               tree lhs = edge_info->lhs;
988               tree rhs = edge_info->rhs;
989
990               /* If we have a simple NAME = VALUE equivalence, record it.  */
991               if (lhs && TREE_CODE (lhs) == SSA_NAME)
992                 record_const_or_copy (lhs, rhs);
993
994               /* If we have 0 = COND or 1 = COND equivalences, record them
995                  into our expression hash tables.  */
996               if (cond_equivalences)
997                 for (i = 0; i < edge_info->max_cond_equivalences; i++)
998                   record_cond (&cond_equivalences[i]);
999             }
1000
1001           dom_thread_across_edge (walk_data, true_edge);
1002
1003           /* And restore the various tables to their state before
1004              we threaded this edge.  */
1005           remove_local_expressions_from_table ();
1006         }
1007
1008       /* Similarly for the ELSE arm.  */
1009       if (potentially_threadable_block (false_edge->dest))
1010         {
1011           struct edge_info *edge_info;
1012           unsigned int i;
1013
1014           VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
1015           edge_info = (struct edge_info *) false_edge->aux;
1016
1017           /* If we have info associated with this edge, record it into
1018              our equivalence tables.  */
1019           if (edge_info)
1020             {
1021               struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
1022               tree lhs = edge_info->lhs;
1023               tree rhs = edge_info->rhs;
1024
1025               /* If we have a simple NAME = VALUE equivalence, record it.  */
1026               if (lhs && TREE_CODE (lhs) == SSA_NAME)
1027                 record_const_or_copy (lhs, rhs);
1028
1029               /* If we have 0 = COND or 1 = COND equivalences, record them
1030                  into our expression hash tables.  */
1031               if (cond_equivalences)
1032                 for (i = 0; i < edge_info->max_cond_equivalences; i++)
1033                   record_cond (&cond_equivalences[i]);
1034             }
1035
1036           /* Now thread the edge.  */
1037           dom_thread_across_edge (walk_data, false_edge);
1038
1039           /* No need to remove local expressions from our tables
1040              or restore vars to their original value as that will
1041              be done immediately below.  */
1042         }
1043     }
1044
1045   remove_local_expressions_from_table ();
1046   restore_vars_to_original_value ();
1047
1048   /* If we queued any statements to rescan in this block, then
1049      go ahead and rescan them now.  */
1050   while (VEC_length (gimple_p, stmts_to_rescan) > 0)
1051     {
1052       gimple *stmt_p = VEC_last (gimple_p, stmts_to_rescan);
1053       gimple stmt = *stmt_p;
1054       basic_block stmt_bb = gimple_bb (stmt);
1055
1056       if (stmt_bb != bb)
1057         break;
1058
1059       VEC_pop (gimple_p, stmts_to_rescan);
1060       pop_stmt_changes (stmt_p);
1061     }
1062 }
1063
1064 /* PHI nodes can create equivalences too.
1065
1066    Ignoring any alternatives which are the same as the result, if
1067    all the alternatives are equal, then the PHI node creates an
1068    equivalence.  */
1069
1070 static void
1071 record_equivalences_from_phis (basic_block bb)
1072 {
1073   gimple_stmt_iterator gsi;
1074   
1075   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1076     {
1077       gimple phi = gsi_stmt (gsi);
1078
1079       tree lhs = gimple_phi_result (phi);
1080       tree rhs = NULL;
1081       size_t i;
1082
1083       for (i = 0; i < gimple_phi_num_args (phi); i++)
1084         {
1085           tree t = gimple_phi_arg_def (phi, i);
1086
1087           /* Ignore alternatives which are the same as our LHS.  Since
1088              LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
1089              can simply compare pointers.  */
1090           if (lhs == t)
1091             continue;
1092
1093           /* If we have not processed an alternative yet, then set
1094              RHS to this alternative.  */
1095           if (rhs == NULL)
1096             rhs = t;
1097           /* If we have processed an alternative (stored in RHS), then
1098              see if it is equal to this one.  If it isn't, then stop
1099              the search.  */
1100           else if (! operand_equal_for_phi_arg_p (rhs, t))
1101             break;
1102         }
1103
1104       /* If we had no interesting alternatives, then all the RHS alternatives
1105          must have been the same as LHS.  */
1106       if (!rhs)
1107         rhs = lhs;
1108
1109       /* If we managed to iterate through each PHI alternative without
1110          breaking out of the loop, then we have a PHI which may create
1111          a useful equivalence.  We do not need to record unwind data for
1112          this, since this is a true assignment and not an equivalence
1113          inferred from a comparison.  All uses of this ssa name are dominated
1114          by this assignment, so unwinding just costs time and space.  */
1115       if (i == gimple_phi_num_args (phi) && may_propagate_copy (lhs, rhs))
1116         set_ssa_name_value (lhs, rhs);
1117     }
1118 }
1119
1120 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1121    return that edge.  Otherwise return NULL.  */
1122 static edge
1123 single_incoming_edge_ignoring_loop_edges (basic_block bb)
1124 {
1125   edge retval = NULL;
1126   edge e;
1127   edge_iterator ei;
1128
1129   FOR_EACH_EDGE (e, ei, bb->preds)
1130     {
1131       /* A loop back edge can be identified by the destination of
1132          the edge dominating the source of the edge.  */
1133       if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
1134         continue;
1135
1136       /* If we have already seen a non-loop edge, then we must have
1137          multiple incoming non-loop edges and thus we return NULL.  */
1138       if (retval)
1139         return NULL;
1140
1141       /* This is the first non-loop incoming edge we have found.  Record
1142          it.  */
1143       retval = e;
1144     }
1145
1146   return retval;
1147 }
1148
1149 /* Record any equivalences created by the incoming edge to BB.  If BB
1150    has more than one incoming edge, then no equivalence is created.  */
1151
1152 static void
1153 record_equivalences_from_incoming_edge (basic_block bb)
1154 {
1155   edge e;
1156   basic_block parent;
1157   struct edge_info *edge_info;
1158
1159   /* If our parent block ended with a control statement, then we may be
1160      able to record some equivalences based on which outgoing edge from
1161      the parent was followed.  */
1162   parent = get_immediate_dominator (CDI_DOMINATORS, bb);
1163
1164   e = single_incoming_edge_ignoring_loop_edges (bb);
1165
1166   /* If we had a single incoming edge from our parent block, then enter
1167      any data associated with the edge into our tables.  */
1168   if (e && e->src == parent)
1169     {
1170       unsigned int i;
1171
1172       edge_info = (struct edge_info *) e->aux;
1173
1174       if (edge_info)
1175         {
1176           tree lhs = edge_info->lhs;
1177           tree rhs = edge_info->rhs;
1178           struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
1179
1180           if (lhs)
1181             record_equality (lhs, rhs);
1182
1183           if (cond_equivalences)
1184             for (i = 0; i < edge_info->max_cond_equivalences; i++)
1185               record_cond (&cond_equivalences[i]);
1186         }
1187     }
1188 }
1189
1190 /* Dump SSA statistics on FILE.  */
1191
1192 void
1193 dump_dominator_optimization_stats (FILE *file)
1194 {
1195   fprintf (file, "Total number of statements:                   %6ld\n\n",
1196            opt_stats.num_stmts);
1197   fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
1198            opt_stats.num_exprs_considered);
1199
1200   fprintf (file, "\nHash table statistics:\n");
1201
1202   fprintf (file, "    avail_exprs: ");
1203   htab_statistics (file, avail_exprs);
1204 }
1205
1206
1207 /* Dump SSA statistics on stderr.  */
1208
1209 void
1210 debug_dominator_optimization_stats (void)
1211 {
1212   dump_dominator_optimization_stats (stderr);
1213 }
1214
1215
1216 /* Dump statistics for the hash table HTAB.  */
1217
1218 static void
1219 htab_statistics (FILE *file, htab_t htab)
1220 {
1221   fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1222            (long) htab_size (htab),
1223            (long) htab_elements (htab),
1224            htab_collisions (htab));
1225 }
1226
1227
1228 /* Enter condition equivalence into the expression hash table.
1229    This indicates that a conditional expression has a known
1230    boolean value.  */
1231
1232 static void
1233 record_cond (struct cond_equivalence *p)
1234 {
1235   struct expr_hash_elt *element = XCNEW (struct expr_hash_elt);
1236   void **slot;
1237
1238   initialize_hash_element_from_expr (&p->cond, p->value, element);
1239
1240   slot = htab_find_slot_with_hash (avail_exprs, (void *)element,
1241                                    element->hash, INSERT);
1242   if (*slot == NULL)
1243     {
1244       *slot = (void *) element;
1245
1246       if (dump_file && (dump_flags & TDF_DETAILS))
1247         {
1248           fprintf (dump_file, "1>>> ");
1249           print_expr_hash_elt (dump_file, element);
1250         }
1251
1252       VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element);
1253     }
1254   else
1255     free (element);
1256 }
1257
1258 /* Build a cond_equivalence record indicating that the comparison
1259    CODE holds between operands OP0 and OP1.  */
1260    
1261 static void
1262 build_and_record_new_cond (enum tree_code code,
1263                            tree op0, tree op1,
1264                            struct cond_equivalence *p)
1265 {
1266   struct hashable_expr *cond = &p->cond;
1267
1268   gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
1269
1270   cond->type = boolean_type_node;
1271   cond->kind = EXPR_BINARY;
1272   cond->ops.binary.op = code;
1273   cond->ops.binary.opnd0 = op0;
1274   cond->ops.binary.opnd1 = op1;
1275
1276   p->value = boolean_true_node;
1277 }
1278
1279 /* Record that COND is true and INVERTED is false into the edge information
1280    structure.  Also record that any conditions dominated by COND are true
1281    as well.
1282
1283    For example, if a < b is true, then a <= b must also be true.  */
1284
1285 static void
1286 record_conditions (struct edge_info *edge_info, tree cond, tree inverted)
1287 {
1288   tree op0, op1;
1289
1290   if (!COMPARISON_CLASS_P (cond))
1291     return;
1292
1293   op0 = TREE_OPERAND (cond, 0);
1294   op1 = TREE_OPERAND (cond, 1);
1295
1296   switch (TREE_CODE (cond))
1297     {
1298     case LT_EXPR:
1299     case GT_EXPR:
1300       if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1301         {
1302           edge_info->max_cond_equivalences = 6;
1303           edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 6);
1304           build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1305                                      &edge_info->cond_equivalences[4]);
1306           build_and_record_new_cond (LTGT_EXPR, op0, op1,
1307                                      &edge_info->cond_equivalences[5]);
1308         }
1309       else
1310         {
1311           edge_info->max_cond_equivalences = 4;
1312           edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1313         }
1314
1315       build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
1316                                   ? LE_EXPR : GE_EXPR),
1317                                  op0, op1, &edge_info->cond_equivalences[2]);
1318       build_and_record_new_cond (NE_EXPR, op0, op1,
1319                                  &edge_info->cond_equivalences[3]);
1320       break;
1321
1322     case GE_EXPR:
1323     case LE_EXPR:
1324       if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1325         {
1326           edge_info->max_cond_equivalences = 3;
1327           edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 3);
1328           build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1329                                      &edge_info->cond_equivalences[2]);
1330         }
1331       else
1332         {
1333           edge_info->max_cond_equivalences = 2;
1334           edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 2);
1335         }
1336       break;
1337
1338     case EQ_EXPR:
1339       if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1340         {
1341           edge_info->max_cond_equivalences = 5;
1342           edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 5);
1343           build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1344                                      &edge_info->cond_equivalences[4]);
1345         }
1346       else
1347         {
1348           edge_info->max_cond_equivalences = 4;
1349           edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1350         }
1351       build_and_record_new_cond (LE_EXPR, op0, op1,
1352                                  &edge_info->cond_equivalences[2]);
1353       build_and_record_new_cond (GE_EXPR, op0, op1,
1354                                  &edge_info->cond_equivalences[3]);
1355       break;
1356
1357     case UNORDERED_EXPR:
1358       edge_info->max_cond_equivalences = 8;
1359       edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 8);
1360       build_and_record_new_cond (NE_EXPR, op0, op1,
1361                                  &edge_info->cond_equivalences[2]);
1362       build_and_record_new_cond (UNLE_EXPR, op0, op1,
1363                                  &edge_info->cond_equivalences[3]);
1364       build_and_record_new_cond (UNGE_EXPR, op0, op1,
1365                                  &edge_info->cond_equivalences[4]);
1366       build_and_record_new_cond (UNEQ_EXPR, op0, op1,
1367                                  &edge_info->cond_equivalences[5]);
1368       build_and_record_new_cond (UNLT_EXPR, op0, op1,
1369                                  &edge_info->cond_equivalences[6]);
1370       build_and_record_new_cond (UNGT_EXPR, op0, op1,
1371                                  &edge_info->cond_equivalences[7]);
1372       break;
1373
1374     case UNLT_EXPR:
1375     case UNGT_EXPR:
1376       edge_info->max_cond_equivalences = 4;
1377       edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1378       build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
1379                                   ? UNLE_EXPR : UNGE_EXPR),
1380                                  op0, op1, &edge_info->cond_equivalences[2]);
1381       build_and_record_new_cond (NE_EXPR, op0, op1,
1382                                  &edge_info->cond_equivalences[3]);
1383       break;
1384
1385     case UNEQ_EXPR:
1386       edge_info->max_cond_equivalences = 4;
1387       edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1388       build_and_record_new_cond (UNLE_EXPR, op0, op1,
1389                                  &edge_info->cond_equivalences[2]);
1390       build_and_record_new_cond (UNGE_EXPR, op0, op1,
1391                                  &edge_info->cond_equivalences[3]);
1392       break;
1393
1394     case LTGT_EXPR:
1395       edge_info->max_cond_equivalences = 4;
1396       edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1397       build_and_record_new_cond (NE_EXPR, op0, op1,
1398                                  &edge_info->cond_equivalences[2]);
1399       build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1400                                  &edge_info->cond_equivalences[3]);
1401       break;
1402
1403     default:
1404       edge_info->max_cond_equivalences = 2;
1405       edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 2);
1406       break;
1407     }
1408
1409   /* Now store the original true and false conditions into the first
1410      two slots.  */
1411   initialize_expr_from_cond (cond, &edge_info->cond_equivalences[0].cond);
1412   edge_info->cond_equivalences[0].value = boolean_true_node;
1413
1414   /* It is possible for INVERTED to be the negation of a comparison,
1415      and not a valid RHS or GIMPLE_COND condition.  This happens because
1416      invert_truthvalue may return such an expression when asked to invert
1417      a floating-point comparison.  These comparisons are not assumed to
1418      obey the trichotomy law.  */
1419   initialize_expr_from_cond (inverted, &edge_info->cond_equivalences[1].cond);
1420   edge_info->cond_equivalences[1].value = boolean_false_node;
1421 }
1422
1423 /* A helper function for record_const_or_copy and record_equality.
1424    Do the work of recording the value and undo info.  */
1425
1426 static void
1427 record_const_or_copy_1 (tree x, tree y, tree prev_x)
1428 {
1429   set_ssa_name_value (x, y);
1430
1431   if (dump_file && (dump_flags & TDF_DETAILS))
1432     {
1433       fprintf (dump_file, "0>>> COPY ");
1434       print_generic_expr (dump_file, x, 0);
1435       fprintf (dump_file, " = ");
1436       print_generic_expr (dump_file, y, 0);
1437       fprintf (dump_file, "\n");
1438     }
1439
1440   VEC_reserve (tree, heap, const_and_copies_stack, 2);
1441   VEC_quick_push (tree, const_and_copies_stack, prev_x);
1442   VEC_quick_push (tree, const_and_copies_stack, x);
1443 }
1444
1445 /* Return the loop depth of the basic block of the defining statement of X.
1446    This number should not be treated as absolutely correct because the loop
1447    information may not be completely up-to-date when dom runs.  However, it
1448    will be relatively correct, and as more passes are taught to keep loop info
1449    up to date, the result will become more and more accurate.  */
1450
1451 int
1452 loop_depth_of_name (tree x)
1453 {
1454   gimple defstmt;
1455   basic_block defbb;
1456
1457   /* If it's not an SSA_NAME, we have no clue where the definition is.  */
1458   if (TREE_CODE (x) != SSA_NAME)
1459     return 0;
1460
1461   /* Otherwise return the loop depth of the defining statement's bb.
1462      Note that there may not actually be a bb for this statement, if the
1463      ssa_name is live on entry.  */
1464   defstmt = SSA_NAME_DEF_STMT (x);
1465   defbb = gimple_bb (defstmt);
1466   if (!defbb)
1467     return 0;
1468
1469   return defbb->loop_depth;
1470 }
1471
1472 /* Record that X is equal to Y in const_and_copies.  Record undo
1473    information in the block-local vector.  */
1474
1475 static void
1476 record_const_or_copy (tree x, tree y)
1477 {
1478   tree prev_x = SSA_NAME_VALUE (x);
1479
1480   gcc_assert (TREE_CODE (x) == SSA_NAME);
1481
1482   if (TREE_CODE (y) == SSA_NAME)
1483     {
1484       tree tmp = SSA_NAME_VALUE (y);
1485       if (tmp)
1486         y = tmp;
1487     }
1488
1489   record_const_or_copy_1 (x, y, prev_x);
1490 }
1491
1492 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1493    This constrains the cases in which we may treat this as assignment.  */
1494
1495 static void
1496 record_equality (tree x, tree y)
1497 {
1498   tree prev_x = NULL, prev_y = NULL;
1499
1500   if (TREE_CODE (x) == SSA_NAME)
1501     prev_x = SSA_NAME_VALUE (x);
1502   if (TREE_CODE (y) == SSA_NAME)
1503     prev_y = SSA_NAME_VALUE (y);
1504
1505   /* If one of the previous values is invariant, or invariant in more loops
1506      (by depth), then use that.
1507      Otherwise it doesn't matter which value we choose, just so
1508      long as we canonicalize on one value.  */
1509   if (is_gimple_min_invariant (y))
1510     ;
1511   else if (is_gimple_min_invariant (x)
1512            || (loop_depth_of_name (x) <= loop_depth_of_name (y)))
1513     prev_x = x, x = y, y = prev_x, prev_x = prev_y;
1514   else if (prev_x && is_gimple_min_invariant (prev_x))
1515     x = y, y = prev_x, prev_x = prev_y;
1516   else if (prev_y)
1517     y = prev_y;
1518
1519   /* After the swapping, we must have one SSA_NAME.  */
1520   if (TREE_CODE (x) != SSA_NAME)
1521     return;
1522
1523   /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1524      variable compared against zero.  If we're honoring signed zeros,
1525      then we cannot record this value unless we know that the value is
1526      nonzero.  */
1527   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x)))
1528       && (TREE_CODE (y) != REAL_CST
1529           || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y))))
1530     return;
1531
1532   record_const_or_copy_1 (x, y, prev_x);
1533 }
1534
1535 /* Returns true when STMT is a simple iv increment.  It detects the
1536    following situation:
1537    
1538    i_1 = phi (..., i_2)
1539    i_2 = i_1 +/- ...  */
1540
1541 static bool
1542 simple_iv_increment_p (gimple stmt)
1543 {
1544   tree lhs, preinc;
1545   gimple phi;
1546   size_t i;
1547
1548   if (gimple_code (stmt) != GIMPLE_ASSIGN)
1549     return false;
1550
1551   lhs = gimple_assign_lhs (stmt);
1552   if (TREE_CODE (lhs) != SSA_NAME)
1553     return false;
1554
1555   if (gimple_assign_rhs_code (stmt) != PLUS_EXPR
1556       && gimple_assign_rhs_code (stmt) != MINUS_EXPR)
1557     return false;
1558
1559   preinc = gimple_assign_rhs1 (stmt);
1560
1561   if (TREE_CODE (preinc) != SSA_NAME)
1562     return false;
1563
1564   phi = SSA_NAME_DEF_STMT (preinc);
1565   if (gimple_code (phi) != GIMPLE_PHI)
1566     return false;
1567
1568   for (i = 0; i < gimple_phi_num_args (phi); i++)
1569     if (gimple_phi_arg_def (phi, i) == lhs)
1570       return true;
1571
1572   return false;
1573 }
1574
1575 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1576    known value for that SSA_NAME (or NULL if no value is known).  
1577
1578    Propagate values from CONST_AND_COPIES into the PHI nodes of the
1579    successors of BB.  */
1580
1581 static void
1582 cprop_into_successor_phis (basic_block bb)
1583 {
1584   edge e;
1585   edge_iterator ei;
1586
1587   FOR_EACH_EDGE (e, ei, bb->succs)
1588     {
1589       int indx;
1590       gimple_stmt_iterator gsi;
1591
1592       /* If this is an abnormal edge, then we do not want to copy propagate
1593          into the PHI alternative associated with this edge.  */
1594       if (e->flags & EDGE_ABNORMAL)
1595         continue;
1596
1597       gsi = gsi_start_phis (e->dest);
1598       if (gsi_end_p (gsi))
1599         continue;
1600
1601       indx = e->dest_idx;
1602       for ( ; !gsi_end_p (gsi); gsi_next (&gsi))
1603         {
1604           tree new_val;
1605           use_operand_p orig_p;
1606           tree orig_val;
1607           gimple phi = gsi_stmt (gsi);
1608
1609           /* The alternative may be associated with a constant, so verify
1610              it is an SSA_NAME before doing anything with it.  */
1611           orig_p = gimple_phi_arg_imm_use_ptr (phi, indx);
1612           orig_val = get_use_from_ptr (orig_p);
1613           if (TREE_CODE (orig_val) != SSA_NAME)
1614             continue;
1615
1616           /* If we have *ORIG_P in our constant/copy table, then replace
1617              ORIG_P with its value in our constant/copy table.  */
1618           new_val = SSA_NAME_VALUE (orig_val);
1619           if (new_val
1620               && new_val != orig_val
1621               && (TREE_CODE (new_val) == SSA_NAME
1622                   || is_gimple_min_invariant (new_val))
1623               && may_propagate_copy (orig_val, new_val))
1624             propagate_value (orig_p, new_val);
1625         }
1626     }
1627 }
1628
1629 /* We have finished optimizing BB, record any information implied by
1630    taking a specific outgoing edge from BB.  */
1631
1632 static void
1633 record_edge_info (basic_block bb)
1634 {
1635   gimple_stmt_iterator gsi = gsi_last_bb (bb);
1636   struct edge_info *edge_info;
1637
1638   if (! gsi_end_p (gsi))
1639     {
1640       gimple stmt = gsi_stmt (gsi);
1641
1642       if (gimple_code (stmt) == GIMPLE_SWITCH)
1643         {
1644           tree index = gimple_switch_index (stmt);
1645
1646           if (TREE_CODE (index) == SSA_NAME)
1647             {
1648               int i;
1649               int n_labels = gimple_switch_num_labels (stmt);
1650               tree *info = XCNEWVEC (tree, last_basic_block);
1651               edge e;
1652               edge_iterator ei;
1653
1654               for (i = 0; i < n_labels; i++)
1655                 {
1656                   tree label = gimple_switch_label (stmt, i);
1657                   basic_block target_bb = label_to_block (CASE_LABEL (label));
1658                   if (CASE_HIGH (label)
1659                       || !CASE_LOW (label)
1660                       || info[target_bb->index])
1661                     info[target_bb->index] = error_mark_node;
1662                   else
1663                     info[target_bb->index] = label;
1664                 }
1665
1666               FOR_EACH_EDGE (e, ei, bb->succs)
1667                 {
1668                   basic_block target_bb = e->dest;
1669                   tree label = info[target_bb->index];
1670
1671                   if (label != NULL && label != error_mark_node)
1672                     {
1673                       tree x = fold_convert (TREE_TYPE (index), CASE_LOW (label));
1674                       edge_info = allocate_edge_info (e);
1675                       edge_info->lhs = index;
1676                       edge_info->rhs = x;
1677                     }
1678                 }
1679               free (info);
1680             }
1681         }
1682
1683       /* A COND_EXPR may create equivalences too.  */
1684       if (gimple_code (stmt) == GIMPLE_COND)
1685         {
1686           edge true_edge;
1687           edge false_edge;
1688
1689           tree op0 = gimple_cond_lhs (stmt);
1690           tree op1 = gimple_cond_rhs (stmt);
1691           enum tree_code code = gimple_cond_code (stmt);
1692
1693           extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1694
1695           /* Special case comparing booleans against a constant as we
1696              know the value of OP0 on both arms of the branch.  i.e., we
1697              can record an equivalence for OP0 rather than COND.  */
1698           if ((code == EQ_EXPR || code == NE_EXPR)
1699               && TREE_CODE (op0) == SSA_NAME
1700               && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
1701               && is_gimple_min_invariant (op1))
1702             {
1703               if (code == EQ_EXPR)
1704                 {
1705                   edge_info = allocate_edge_info (true_edge);
1706                   edge_info->lhs = op0;
1707                   edge_info->rhs = (integer_zerop (op1)
1708                                     ? boolean_false_node
1709                                     : boolean_true_node);
1710
1711                   edge_info = allocate_edge_info (false_edge);
1712                   edge_info->lhs = op0;
1713                   edge_info->rhs = (integer_zerop (op1)
1714                                     ? boolean_true_node
1715                                     : boolean_false_node);
1716                 }
1717               else
1718                 {
1719                   edge_info = allocate_edge_info (true_edge);
1720                   edge_info->lhs = op0;
1721                   edge_info->rhs = (integer_zerop (op1)
1722                                     ? boolean_true_node
1723                                     : boolean_false_node);
1724
1725                   edge_info = allocate_edge_info (false_edge);
1726                   edge_info->lhs = op0;
1727                   edge_info->rhs = (integer_zerop (op1)
1728                                     ? boolean_false_node
1729                                     : boolean_true_node);
1730                 }
1731             }
1732           else if (is_gimple_min_invariant (op0)
1733                    && (TREE_CODE (op1) == SSA_NAME
1734                        || is_gimple_min_invariant (op1)))
1735             {
1736               tree cond = build2 (code, boolean_type_node, op0, op1);
1737               tree inverted = invert_truthvalue (cond);
1738               struct edge_info *edge_info;
1739
1740               edge_info = allocate_edge_info (true_edge);
1741               record_conditions (edge_info, cond, inverted);
1742
1743               if (code == EQ_EXPR)
1744                 {
1745                   edge_info->lhs = op1;
1746                   edge_info->rhs = op0;
1747                 }
1748
1749               edge_info = allocate_edge_info (false_edge);
1750               record_conditions (edge_info, inverted, cond);
1751
1752               if (code == NE_EXPR)
1753                 {
1754                   edge_info->lhs = op1;
1755                   edge_info->rhs = op0;
1756                 }
1757             }
1758
1759           else if (TREE_CODE (op0) == SSA_NAME
1760                    && (is_gimple_min_invariant (op1)
1761                        || TREE_CODE (op1) == SSA_NAME))
1762             {
1763               tree cond = build2 (code, boolean_type_node, op0, op1);
1764               tree inverted = invert_truthvalue (cond);
1765               struct edge_info *edge_info;
1766
1767               edge_info = allocate_edge_info (true_edge);
1768               record_conditions (edge_info, cond, inverted);
1769
1770               if (code == EQ_EXPR)
1771                 {
1772                   edge_info->lhs = op0;
1773                   edge_info->rhs = op1;
1774                 }
1775
1776               edge_info = allocate_edge_info (false_edge);
1777               record_conditions (edge_info, inverted, cond);
1778
1779               if (TREE_CODE (cond) == NE_EXPR)
1780                 {
1781                   edge_info->lhs = op0;
1782                   edge_info->rhs = op1;
1783                 }
1784             }
1785         }
1786
1787       /* ??? TRUTH_NOT_EXPR can create an equivalence too.  */
1788     }
1789 }
1790
1791 /* Propagate information from BB to its outgoing edges.
1792
1793    This can include equivalence information implied by control statements
1794    at the end of BB and const/copy propagation into PHIs in BB's
1795    successor blocks.  */
1796
1797 static void
1798 propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1799                              basic_block bb)
1800 {
1801   record_edge_info (bb);
1802   cprop_into_successor_phis (bb);
1803 }
1804
1805 /* Search for redundant computations in STMT.  If any are found, then
1806    replace them with the variable holding the result of the computation.
1807
1808    If safe, record this expression into the available expression hash
1809    table.  */
1810
1811 static bool
1812 eliminate_redundant_computations (gimple_stmt_iterator* gsi)
1813 {
1814   tree expr_type;
1815   tree cached_lhs;
1816   bool insert = true;
1817   bool retval = false;
1818   bool assigns_var_p = false;
1819
1820   gimple stmt = gsi_stmt (*gsi);
1821
1822   tree def = gimple_get_lhs (stmt);
1823
1824   /* Certain expressions on the RHS can be optimized away, but can not
1825      themselves be entered into the hash tables.  */
1826   if (! def
1827       || TREE_CODE (def) != SSA_NAME
1828       || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
1829       || gimple_vdef (stmt)
1830       /* Do not record equivalences for increments of ivs.  This would create
1831          overlapping live ranges for a very questionable gain.  */
1832       || simple_iv_increment_p (stmt))
1833     insert = false;
1834
1835   /* Check if the expression has been computed before.  */
1836   cached_lhs = lookup_avail_expr (stmt, insert);
1837
1838   opt_stats.num_exprs_considered++;
1839
1840   /* Get the type of the expression we are trying to optimize.  */
1841   if (is_gimple_assign (stmt))
1842     {
1843       expr_type = TREE_TYPE (gimple_assign_lhs (stmt));
1844       assigns_var_p = true;
1845     }
1846   else if (gimple_code (stmt) == GIMPLE_COND)
1847     expr_type = boolean_type_node;
1848   else if (is_gimple_call (stmt))
1849     {
1850       gcc_assert (gimple_call_lhs (stmt));
1851       expr_type = TREE_TYPE (gimple_call_lhs (stmt));
1852       assigns_var_p = true;
1853     }
1854   else if (gimple_code (stmt) == GIMPLE_SWITCH)
1855     expr_type = TREE_TYPE (gimple_switch_index (stmt));
1856   else
1857     gcc_unreachable ();
1858
1859   if (!cached_lhs)
1860     return false;
1861
1862   /* It is safe to ignore types here since we have already done
1863      type checking in the hashing and equality routines.  In fact
1864      type checking here merely gets in the way of constant
1865      propagation.  Also, make sure that it is safe to propagate
1866      CACHED_LHS into the expression in STMT.  */
1867   if ((TREE_CODE (cached_lhs) != SSA_NAME
1868        && (assigns_var_p
1869            || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))))
1870       || may_propagate_copy_into_stmt (stmt, cached_lhs))
1871   {
1872 #if defined ENABLE_CHECKING
1873       gcc_assert (TREE_CODE (cached_lhs) == SSA_NAME
1874                   || is_gimple_min_invariant (cached_lhs));
1875 #endif
1876
1877       if (dump_file && (dump_flags & TDF_DETAILS))
1878         {
1879           fprintf (dump_file, "  Replaced redundant expr '");
1880           print_gimple_expr (dump_file, stmt, 0, dump_flags);
1881           fprintf (dump_file, "' with '");
1882           print_generic_expr (dump_file, cached_lhs, dump_flags);
1883           fprintf (dump_file, "'\n");
1884         }
1885
1886       opt_stats.num_re++;
1887
1888       if (TREE_CODE (cached_lhs) == ADDR_EXPR
1889           || (POINTER_TYPE_P (expr_type)
1890               && is_gimple_min_invariant (cached_lhs)))
1891         retval = true;
1892       
1893       if (assigns_var_p
1894           && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))
1895         cached_lhs = fold_convert (expr_type, cached_lhs);
1896
1897       propagate_tree_value_into_stmt (gsi, cached_lhs);
1898
1899       /* Since it is always necessary to mark the result as modified,
1900          perhaps we should move this into propagate_tree_value_into_stmt
1901          itself.  */
1902       gimple_set_modified (gsi_stmt (*gsi), true);
1903   }
1904   return retval;
1905 }
1906
1907 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
1908    the available expressions table or the const_and_copies table.
1909    Detect and record those equivalences.  */
1910 /* We handle only very simple copy equivalences here.  The heavy
1911    lifing is done by eliminate_redundant_computations.  */
1912
1913 static void
1914 record_equivalences_from_stmt (gimple stmt, int may_optimize_p)
1915 {
1916   tree lhs;
1917   enum tree_code lhs_code;
1918
1919   gcc_assert (is_gimple_assign (stmt));
1920
1921   lhs = gimple_assign_lhs (stmt);
1922   lhs_code = TREE_CODE (lhs);
1923
1924   if (lhs_code == SSA_NAME
1925       && gimple_assign_single_p (stmt))
1926     {
1927       tree rhs = gimple_assign_rhs1 (stmt);
1928                
1929       /* If the RHS of the assignment is a constant or another variable that
1930          may be propagated, register it in the CONST_AND_COPIES table.  We
1931          do not need to record unwind data for this, since this is a true
1932          assignment and not an equivalence inferred from a comparison.  All
1933          uses of this ssa name are dominated by this assignment, so unwinding
1934          just costs time and space.  */
1935       if (may_optimize_p
1936           && (TREE_CODE (rhs) == SSA_NAME
1937               || is_gimple_min_invariant (rhs)))
1938       {
1939         if (dump_file && (dump_flags & TDF_DETAILS))
1940           {
1941             fprintf (dump_file, "==== ASGN ");
1942             print_generic_expr (dump_file, lhs, 0);
1943             fprintf (dump_file, " = ");
1944             print_generic_expr (dump_file, rhs, 0);
1945             fprintf (dump_file, "\n");
1946           }
1947
1948         set_ssa_name_value (lhs, rhs);
1949       }
1950     }
1951
1952   /* A memory store, even an aliased store, creates a useful
1953      equivalence.  By exchanging the LHS and RHS, creating suitable
1954      vops and recording the result in the available expression table,
1955      we may be able to expose more redundant loads.  */
1956   if (!gimple_has_volatile_ops (stmt)
1957       && gimple_references_memory_p (stmt)
1958       && gimple_assign_single_p (stmt)
1959       && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1960           || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
1961       && !is_gimple_reg (lhs))
1962     {
1963       tree rhs = gimple_assign_rhs1 (stmt);
1964       gimple new_stmt;
1965
1966       /* Build a new statement with the RHS and LHS exchanged.  */
1967       if (TREE_CODE (rhs) == SSA_NAME)
1968         {
1969           /* NOTE tuples.  The call to gimple_build_assign below replaced
1970              a call to build_gimple_modify_stmt, which did not set the
1971              SSA_NAME_DEF_STMT on the LHS of the assignment.  Doing so
1972              may cause an SSA validation failure, as the LHS may be a
1973              default-initialized name and should have no definition.  I'm
1974              a bit dubious of this, as the artificial statement that we
1975              generate here may in fact be ill-formed, but it is simply
1976              used as an internal device in this pass, and never becomes
1977              part of the CFG.  */
1978           gimple defstmt = SSA_NAME_DEF_STMT (rhs);
1979           new_stmt = gimple_build_assign (rhs, lhs);
1980           SSA_NAME_DEF_STMT (rhs) = defstmt;
1981         }
1982       else
1983         new_stmt = gimple_build_assign (rhs, lhs);
1984
1985       gimple_set_vuse (new_stmt, gimple_vdef (stmt));
1986
1987       /* Finally enter the statement into the available expression
1988          table.  */
1989       lookup_avail_expr (new_stmt, true);
1990     }
1991 }
1992
1993 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
1994    CONST_AND_COPIES.  */
1995
1996 static bool
1997 cprop_operand (gimple stmt, use_operand_p op_p)
1998 {
1999   bool may_have_exposed_new_symbols = false;
2000   tree val;
2001   tree op = USE_FROM_PTR (op_p);
2002
2003   /* If the operand has a known constant value or it is known to be a
2004      copy of some other variable, use the value or copy stored in
2005      CONST_AND_COPIES.  */
2006   val = SSA_NAME_VALUE (op);
2007   if (val && val != op)
2008     {
2009       /* Do not change the base variable in the virtual operand
2010          tables.  That would make it impossible to reconstruct
2011          the renamed virtual operand if we later modify this
2012          statement.  Also only allow the new value to be an SSA_NAME
2013          for propagation into virtual operands.  */
2014       if (!is_gimple_reg (op)
2015           && (TREE_CODE (val) != SSA_NAME
2016               || is_gimple_reg (val)
2017               || get_virtual_var (val) != get_virtual_var (op)))
2018         return false;
2019
2020       /* Do not replace hard register operands in asm statements.  */
2021       if (gimple_code (stmt) == GIMPLE_ASM
2022           && !may_propagate_copy_into_asm (op))
2023         return false;
2024
2025       /* Certain operands are not allowed to be copy propagated due
2026          to their interaction with exception handling and some GCC
2027          extensions.  */
2028       if (!may_propagate_copy (op, val))
2029         return false;
2030
2031       /* Do not propagate addresses that point to volatiles into memory
2032          stmts without volatile operands.  */
2033       if (POINTER_TYPE_P (TREE_TYPE (val))
2034           && TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (val)))
2035           && gimple_has_mem_ops (stmt)
2036           && !gimple_has_volatile_ops (stmt))
2037         return false;
2038
2039       /* Do not propagate copies if the propagated value is at a deeper loop
2040          depth than the propagatee.  Otherwise, this may move loop variant
2041          variables outside of their loops and prevent coalescing
2042          opportunities.  If the value was loop invariant, it will be hoisted
2043          by LICM and exposed for copy propagation.  */
2044       if (loop_depth_of_name (val) > loop_depth_of_name (op))
2045         return false;
2046
2047       /* Dump details.  */
2048       if (dump_file && (dump_flags & TDF_DETAILS))
2049         {
2050           fprintf (dump_file, "  Replaced '");
2051           print_generic_expr (dump_file, op, dump_flags);
2052           fprintf (dump_file, "' with %s '",
2053                    (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
2054           print_generic_expr (dump_file, val, dump_flags);
2055           fprintf (dump_file, "'\n");
2056         }
2057
2058       /* If VAL is an ADDR_EXPR or a constant of pointer type, note
2059          that we may have exposed a new symbol for SSA renaming.  */
2060       if (TREE_CODE (val) == ADDR_EXPR
2061           || (POINTER_TYPE_P (TREE_TYPE (op))
2062               && is_gimple_min_invariant (val)))
2063         may_have_exposed_new_symbols = true;
2064
2065       if (TREE_CODE (val) != SSA_NAME)
2066         opt_stats.num_const_prop++;
2067       else
2068         opt_stats.num_copy_prop++;
2069
2070       propagate_value (op_p, val);
2071
2072       /* And note that we modified this statement.  This is now
2073          safe, even if we changed virtual operands since we will
2074          rescan the statement and rewrite its operands again.  */
2075       gimple_set_modified (stmt, true);
2076     }
2077   return may_have_exposed_new_symbols;
2078 }
2079
2080 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2081    known value for that SSA_NAME (or NULL if no value is known).  
2082
2083    Propagate values from CONST_AND_COPIES into the uses, vuses and
2084    vdef_ops of STMT.  */
2085
2086 static bool
2087 cprop_into_stmt (gimple stmt)
2088 {
2089   bool may_have_exposed_new_symbols = false;
2090   use_operand_p op_p;
2091   ssa_op_iter iter;
2092
2093   FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES)
2094     {
2095       if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
2096         may_have_exposed_new_symbols |= cprop_operand (stmt, op_p);
2097     }
2098
2099   return may_have_exposed_new_symbols;
2100 }
2101
2102 /* Optimize the statement pointed to by iterator SI.
2103    
2104    We try to perform some simplistic global redundancy elimination and
2105    constant propagation:
2106
2107    1- To detect global redundancy, we keep track of expressions that have
2108       been computed in this block and its dominators.  If we find that the
2109       same expression is computed more than once, we eliminate repeated
2110       computations by using the target of the first one.
2111
2112    2- Constant values and copy assignments.  This is used to do very
2113       simplistic constant and copy propagation.  When a constant or copy
2114       assignment is found, we map the value on the RHS of the assignment to
2115       the variable in the LHS in the CONST_AND_COPIES table.  */
2116
2117 static void
2118 optimize_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
2119                basic_block bb, gimple_stmt_iterator si)
2120 {
2121   gimple stmt, old_stmt;
2122   bool may_optimize_p;
2123   bool may_have_exposed_new_symbols;
2124   bool modified_p = false;
2125
2126   old_stmt = stmt = gsi_stmt (si);
2127   
2128   if (gimple_code (stmt) == GIMPLE_COND)
2129     canonicalize_comparison (stmt);
2130   
2131   update_stmt_if_modified (stmt);
2132   opt_stats.num_stmts++;
2133   push_stmt_changes (gsi_stmt_ptr (&si));
2134
2135   if (dump_file && (dump_flags & TDF_DETAILS))
2136     {
2137       fprintf (dump_file, "Optimizing statement ");
2138       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2139     }
2140
2141   /* Const/copy propagate into USES, VUSES and the RHS of VDEFs.  */
2142   may_have_exposed_new_symbols = cprop_into_stmt (stmt);
2143
2144   /* If the statement has been modified with constant replacements,
2145      fold its RHS before checking for redundant computations.  */
2146   if (gimple_modified_p (stmt))
2147     {
2148       tree rhs = NULL;
2149
2150       /* Try to fold the statement making sure that STMT is kept
2151          up to date.  */
2152       if (fold_stmt (&si))
2153         {
2154           stmt = gsi_stmt (si);
2155
2156           if (dump_file && (dump_flags & TDF_DETAILS))
2157             {
2158               fprintf (dump_file, "  Folded to: ");
2159               print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2160             }
2161         }
2162
2163       /* We only need to consider cases that can yield a gimple operand.  */
2164       if (gimple_assign_single_p (stmt))
2165         rhs = gimple_assign_rhs1 (stmt);
2166       else if (gimple_code (stmt) == GIMPLE_GOTO)
2167         rhs = gimple_goto_dest (stmt);
2168       else if (gimple_code (stmt) == GIMPLE_SWITCH)
2169         /* This should never be an ADDR_EXPR.  */
2170         rhs = gimple_switch_index (stmt);
2171
2172       if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
2173         recompute_tree_invariant_for_addr_expr (rhs);
2174
2175       /* Constant/copy propagation above may change the set of 
2176          virtual operands associated with this statement.  Folding
2177          may remove the need for some virtual operands.
2178
2179          Indicate we will need to rescan and rewrite the statement.  */
2180       may_have_exposed_new_symbols = true;
2181       /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
2182          even if fold_stmt updated the stmt already and thus cleared
2183          gimple_modified_p flag on it.  */
2184       modified_p = true;
2185     }
2186
2187   /* Check for redundant computations.  Do this optimization only
2188      for assignments that have no volatile ops and conditionals.  */
2189   may_optimize_p = (!gimple_has_volatile_ops (stmt)
2190                     && ((is_gimple_assign (stmt)
2191                          && !gimple_rhs_has_side_effects (stmt))
2192                         || (is_gimple_call (stmt)
2193                             && gimple_call_lhs (stmt) != NULL_TREE
2194                             && !gimple_rhs_has_side_effects (stmt))
2195                         || gimple_code (stmt) == GIMPLE_COND
2196                         || gimple_code (stmt) == GIMPLE_SWITCH));
2197
2198   if (may_optimize_p)
2199     {
2200       may_have_exposed_new_symbols |= eliminate_redundant_computations (&si);
2201       stmt = gsi_stmt (si);
2202     }
2203
2204   /* Record any additional equivalences created by this statement.  */
2205   if (is_gimple_assign (stmt))
2206     record_equivalences_from_stmt (stmt, may_optimize_p);
2207
2208   /* If STMT is a COND_EXPR and it was modified, then we may know
2209      where it goes.  If that is the case, then mark the CFG as altered.
2210
2211      This will cause us to later call remove_unreachable_blocks and
2212      cleanup_tree_cfg when it is safe to do so.  It is not safe to 
2213      clean things up here since removal of edges and such can trigger
2214      the removal of PHI nodes, which in turn can release SSA_NAMEs to
2215      the manager.
2216
2217      That's all fine and good, except that once SSA_NAMEs are released
2218      to the manager, we must not call create_ssa_name until all references
2219      to released SSA_NAMEs have been eliminated.
2220
2221      All references to the deleted SSA_NAMEs can not be eliminated until
2222      we remove unreachable blocks.
2223
2224      We can not remove unreachable blocks until after we have completed
2225      any queued jump threading.
2226
2227      We can not complete any queued jump threads until we have taken
2228      appropriate variables out of SSA form.  Taking variables out of
2229      SSA form can call create_ssa_name and thus we lose.
2230
2231      Ultimately I suspect we're going to need to change the interface
2232      into the SSA_NAME manager.  */
2233   if (gimple_modified_p (stmt) || modified_p)
2234     {
2235       tree val = NULL;
2236
2237       if (gimple_code (stmt) == GIMPLE_COND)
2238         val = fold_binary (gimple_cond_code (stmt), boolean_type_node,
2239                            gimple_cond_lhs (stmt),  gimple_cond_rhs (stmt));
2240       else if (gimple_code (stmt) == GIMPLE_SWITCH)
2241         val = gimple_switch_index (stmt);
2242
2243       if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val))
2244         cfg_altered = true;
2245
2246       /* If we simplified a statement in such a way as to be shown that it
2247          cannot trap, update the eh information and the cfg to match.  */
2248       if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
2249         {
2250           bitmap_set_bit (need_eh_cleanup, bb->index);
2251           if (dump_file && (dump_flags & TDF_DETAILS))
2252             fprintf (dump_file, "  Flagged to clear EH edges.\n");
2253         }
2254     }
2255
2256   if (may_have_exposed_new_symbols)
2257     {
2258       /* Queue the statement to be re-scanned after all the
2259          AVAIL_EXPRS have been processed.  The change buffer stack for
2260          all the pushed statements will be processed when this queue
2261          is emptied.  */
2262       VEC_safe_push (gimple_p, heap, stmts_to_rescan, gsi_stmt_ptr (&si));
2263     }
2264   else
2265     {
2266       /* Otherwise, just discard the recently pushed change buffer.  If
2267          not, the STMTS_TO_RESCAN queue will get out of synch with the
2268          change buffer stack.  */
2269       discard_stmt_changes (gsi_stmt_ptr (&si));
2270     }
2271 }
2272
2273 /* Search for an existing instance of STMT in the AVAIL_EXPRS table.
2274    If found, return its LHS. Otherwise insert STMT in the table and
2275    return NULL_TREE.
2276
2277    Also, when an expression is first inserted in the  table, it is also
2278    is also added to AVAIL_EXPRS_STACK, so that it can be removed when
2279    we finish processing this block and its children.  */
2280
2281 static tree
2282 lookup_avail_expr (gimple stmt, bool insert)
2283 {
2284   void **slot;
2285   tree lhs;
2286   tree temp;
2287   struct expr_hash_elt *element = XNEW (struct expr_hash_elt);
2288
2289   /* Get LHS of assignment or call, else NULL_TREE.  */
2290   lhs = gimple_get_lhs (stmt);
2291
2292   initialize_hash_element (stmt, lhs, element);
2293
2294   if (dump_file && (dump_flags & TDF_DETAILS))
2295     {
2296       fprintf (dump_file, "LKUP ");
2297       print_expr_hash_elt (dump_file, element);
2298     }
2299
2300   /* Don't bother remembering constant assignments and copy operations.
2301      Constants and copy operations are handled by the constant/copy propagator
2302      in optimize_stmt.  */
2303   if (element->expr.kind == EXPR_SINGLE
2304       && (TREE_CODE (element->expr.ops.single.rhs) == SSA_NAME
2305           || is_gimple_min_invariant (element->expr.ops.single.rhs)))
2306     {
2307       free (element);
2308       return NULL_TREE;
2309     }
2310
2311   /* Finally try to find the expression in the main expression hash table.  */
2312   slot = htab_find_slot_with_hash (avail_exprs, element, element->hash,
2313                                    (insert ? INSERT : NO_INSERT));
2314   if (slot == NULL)
2315     {
2316       free (element);
2317       return NULL_TREE;  
2318     }
2319
2320   if (*slot == NULL)
2321     {
2322       *slot = (void *) element;
2323
2324       if (dump_file && (dump_flags & TDF_DETAILS))
2325         {
2326           fprintf (dump_file, "2>>> ");
2327           print_expr_hash_elt (dump_file, element);
2328         }
2329
2330       VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element);
2331       return NULL_TREE;
2332     }
2333
2334   /* Extract the LHS of the assignment so that it can be used as the current
2335      definition of another variable.  */
2336   lhs = ((struct expr_hash_elt *)*slot)->lhs;
2337
2338   /* See if the LHS appears in the CONST_AND_COPIES table.  If it does, then
2339      use the value from the const_and_copies table.  */
2340   if (TREE_CODE (lhs) == SSA_NAME)
2341     {
2342       temp = SSA_NAME_VALUE (lhs);
2343       if (temp)
2344         lhs = temp;
2345     }
2346
2347   free (element);
2348
2349   if (dump_file && (dump_flags & TDF_DETAILS))
2350     {
2351       fprintf (dump_file, "FIND: ");
2352       print_generic_expr (dump_file, lhs, 0);
2353       fprintf (dump_file, "\n");
2354     }
2355
2356   return lhs;
2357 }
2358
2359 /* Hashing and equality functions for AVAIL_EXPRS.  We compute a value number
2360    for expressions using the code of the expression and the SSA numbers of
2361    its operands.  */
2362
2363 static hashval_t
2364 avail_expr_hash (const void *p)
2365 {
2366   gimple stmt = ((const struct expr_hash_elt *)p)->stmt;
2367   const struct hashable_expr *expr = &((const struct expr_hash_elt *)p)->expr;
2368   tree vuse;
2369   hashval_t val = 0;
2370
2371   val = iterative_hash_hashable_expr (expr, val);
2372
2373   /* If the hash table entry is not associated with a statement, then we
2374      can just hash the expression and not worry about virtual operands
2375      and such.  */
2376   if (!stmt)
2377     return val;
2378
2379   /* Add the SSA version numbers of the vuse operand.  This is important
2380      because compound variables like arrays are not renamed in the
2381      operands.  Rather, the rename is done on the virtual variable
2382      representing all the elements of the array.  */
2383   if ((vuse = gimple_vuse (stmt)))
2384     val = iterative_hash_expr (vuse, val);
2385
2386   return val;
2387 }
2388
2389 static hashval_t
2390 real_avail_expr_hash (const void *p)
2391 {
2392   return ((const struct expr_hash_elt *)p)->hash;
2393 }
2394
2395 static int
2396 avail_expr_eq (const void *p1, const void *p2)
2397 {
2398   gimple stmt1 = ((const struct expr_hash_elt *)p1)->stmt;
2399   const struct hashable_expr *expr1 = &((const struct expr_hash_elt *)p1)->expr;
2400   const struct expr_hash_elt *stamp1 = ((const struct expr_hash_elt *)p1)->stamp;
2401   gimple stmt2 = ((const struct expr_hash_elt *)p2)->stmt;
2402   const struct hashable_expr *expr2 = &((const struct expr_hash_elt *)p2)->expr;
2403   const struct expr_hash_elt *stamp2 = ((const struct expr_hash_elt *)p2)->stamp;
2404
2405   /* This case should apply only when removing entries from the table.  */
2406   if (stamp1 == stamp2)
2407     return true;
2408
2409   /* FIXME tuples:
2410      We add stmts to a hash table and them modify them. To detect the case
2411      that we modify a stmt and then search for it, we assume that the hash
2412      is always modified by that change.
2413      We have to fully check why this doesn't happen on trunk or rewrite
2414      this in a more  reliable (and easier to understand) way. */
2415   if (((const struct expr_hash_elt *)p1)->hash
2416       != ((const struct expr_hash_elt *)p2)->hash)
2417     return false;
2418
2419   /* In case of a collision, both RHS have to be identical and have the
2420      same VUSE operands.  */
2421   if (hashable_expr_equal_p (expr1, expr2)
2422       && types_compatible_p (expr1->type, expr2->type))
2423     {
2424       /* Note that STMT1 and/or STMT2 may be NULL.  */
2425       return ((stmt1 ? gimple_vuse (stmt1) : NULL_TREE)
2426               == (stmt2 ? gimple_vuse (stmt2) : NULL_TREE));
2427     }
2428
2429   return false;
2430 }
2431
2432 /* PHI-ONLY copy and constant propagation.  This pass is meant to clean
2433    up degenerate PHIs created by or exposed by jump threading.  */
2434
2435 /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
2436    NULL.  */
2437
2438 tree
2439 degenerate_phi_result (gimple phi)
2440 {
2441   tree lhs = gimple_phi_result (phi);
2442   tree val = NULL;
2443   size_t i;
2444
2445   /* Ignoring arguments which are the same as LHS, if all the remaining
2446      arguments are the same, then the PHI is a degenerate and has the
2447      value of that common argument.  */
2448   for (i = 0; i < gimple_phi_num_args (phi); i++)
2449     {
2450       tree arg = gimple_phi_arg_def (phi, i);
2451
2452       if (arg == lhs)
2453         continue;
2454       else if (!val)
2455         val = arg;
2456       else if (!operand_equal_p (arg, val, 0))
2457         break;
2458     }
2459   return (i == gimple_phi_num_args (phi) ? val : NULL);
2460 }
2461
2462 /* Given a statement STMT, which is either a PHI node or an assignment,
2463    remove it from the IL.  */
2464
2465 static void
2466 remove_stmt_or_phi (gimple stmt)
2467 {
2468   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
2469
2470   if (gimple_code (stmt) == GIMPLE_PHI)
2471     remove_phi_node (&gsi, true);
2472   else
2473     {
2474       gsi_remove (&gsi, true);
2475       release_defs (stmt);
2476     }
2477 }
2478
2479 /* Given a statement STMT, which is either a PHI node or an assignment,
2480    return the "rhs" of the node, in the case of a non-degenerate
2481    phi, NULL is returned.  */
2482
2483 static tree
2484 get_rhs_or_phi_arg (gimple stmt)
2485 {
2486   if (gimple_code (stmt) == GIMPLE_PHI)
2487     return degenerate_phi_result (stmt);
2488   else if (gimple_assign_single_p (stmt))
2489     return gimple_assign_rhs1 (stmt);
2490   else
2491     gcc_unreachable ();
2492 }
2493
2494
2495 /* Given a statement STMT, which is either a PHI node or an assignment,
2496    return the "lhs" of the node.  */
2497
2498 static tree
2499 get_lhs_or_phi_result (gimple stmt)
2500 {
2501   if (gimple_code (stmt) == GIMPLE_PHI)
2502     return gimple_phi_result (stmt);
2503   else if (is_gimple_assign (stmt))
2504     return gimple_assign_lhs (stmt);
2505   else
2506     gcc_unreachable ();
2507 }
2508
2509 /* Propagate RHS into all uses of LHS (when possible).
2510
2511    RHS and LHS are derived from STMT, which is passed in solely so
2512    that we can remove it if propagation is successful.
2513
2514    When propagating into a PHI node or into a statement which turns
2515    into a trivial copy or constant initialization, set the
2516    appropriate bit in INTERESTING_NAMEs so that we will visit those
2517    nodes as well in an effort to pick up secondary optimization
2518    opportunities.  */
2519
2520 static void 
2521 propagate_rhs_into_lhs (gimple stmt, tree lhs, tree rhs, bitmap interesting_names)
2522 {
2523   /* First verify that propagation is valid and isn't going to move a
2524      loop variant variable outside its loop.  */
2525   if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)
2526       && (TREE_CODE (rhs) != SSA_NAME
2527           || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
2528       && may_propagate_copy (lhs, rhs)
2529       && loop_depth_of_name (lhs) >= loop_depth_of_name (rhs))
2530     {
2531       use_operand_p use_p;
2532       imm_use_iterator iter;
2533       gimple use_stmt;
2534       bool all = true;
2535
2536       /* Dump details.  */
2537       if (dump_file && (dump_flags & TDF_DETAILS))
2538         {
2539           fprintf (dump_file, "  Replacing '");
2540           print_generic_expr (dump_file, lhs, dump_flags);
2541           fprintf (dump_file, "' with %s '",
2542                    (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable"));
2543                    print_generic_expr (dump_file, rhs, dump_flags);
2544           fprintf (dump_file, "'\n");
2545         }
2546
2547       /* Walk over every use of LHS and try to replace the use with RHS. 
2548          At this point the only reason why such a propagation would not
2549          be successful would be if the use occurs in an ASM_EXPR.  */
2550       FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
2551         {
2552         
2553           /* It's not always safe to propagate into an ASM_EXPR.  */
2554           if (gimple_code (use_stmt) == GIMPLE_ASM
2555               && ! may_propagate_copy_into_asm (lhs))
2556             {
2557               all = false;
2558               continue;
2559             }
2560
2561           /* Dump details.  */
2562           if (dump_file && (dump_flags & TDF_DETAILS))
2563             {
2564               fprintf (dump_file, "    Original statement:");
2565               print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2566             }
2567
2568           push_stmt_changes (&use_stmt);
2569
2570           /* Propagate the RHS into this use of the LHS.  */
2571           FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
2572             propagate_value (use_p, rhs);
2573
2574           /* Special cases to avoid useless calls into the folding
2575              routines, operand scanning, etc.
2576
2577              First, propagation into a PHI may cause the PHI to become
2578              a degenerate, so mark the PHI as interesting.  No other
2579              actions are necessary.
2580
2581              Second, if we're propagating a virtual operand and the
2582              propagation does not change the underlying _DECL node for
2583              the virtual operand, then no further actions are necessary.  */
2584           if (gimple_code (use_stmt) == GIMPLE_PHI
2585               || (! is_gimple_reg (lhs)
2586                   && TREE_CODE (rhs) == SSA_NAME
2587                   && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs)))
2588             {
2589               /* Dump details.  */
2590               if (dump_file && (dump_flags & TDF_DETAILS))
2591                 {
2592                   fprintf (dump_file, "    Updated statement:");
2593                   print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2594                 }
2595
2596               /* Propagation into a PHI may expose new degenerate PHIs,
2597                  so mark the result of the PHI as interesting.  */
2598               if (gimple_code (use_stmt) == GIMPLE_PHI)
2599                 {
2600                   tree result = get_lhs_or_phi_result (use_stmt);
2601                   bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
2602                 }
2603
2604               discard_stmt_changes (&use_stmt);
2605               continue;
2606             }
2607
2608           /* From this point onward we are propagating into a 
2609              real statement.  Folding may (or may not) be possible,
2610              we may expose new operands, expose dead EH edges,
2611              etc.  */
2612           /* NOTE tuples. In the tuples world, fold_stmt_inplace
2613              cannot fold a call that simplifies to a constant,
2614              because the GIMPLE_CALL must be replaced by a
2615              GIMPLE_ASSIGN, and there is no way to effect such a
2616              transformation in-place.  We might want to consider
2617              using the more general fold_stmt here.  */
2618           fold_stmt_inplace (use_stmt);
2619
2620           /* Sometimes propagation can expose new operands to the
2621              renamer.  Note this will call update_stmt at the 
2622              appropriate time.  */
2623           pop_stmt_changes (&use_stmt);
2624
2625           /* Dump details.  */
2626           if (dump_file && (dump_flags & TDF_DETAILS))
2627             {
2628               fprintf (dump_file, "    Updated statement:");
2629               print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2630             }
2631
2632           /* If we replaced a variable index with a constant, then
2633              we would need to update the invariant flag for ADDR_EXPRs.  */
2634           if (gimple_assign_single_p (use_stmt)
2635               && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR)
2636             recompute_tree_invariant_for_addr_expr
2637                 (gimple_assign_rhs1 (use_stmt));
2638
2639           /* If we cleaned up EH information from the statement,
2640              mark its containing block as needing EH cleanups.  */
2641           if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt))
2642             {
2643               bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index);
2644               if (dump_file && (dump_flags & TDF_DETAILS))
2645                 fprintf (dump_file, "  Flagged to clear EH edges.\n");
2646             }
2647
2648           /* Propagation may expose new trivial copy/constant propagation
2649              opportunities.  */
2650           if (gimple_assign_single_p (use_stmt)
2651               && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
2652               && (TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
2653                   || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt))))
2654             {
2655               tree result = get_lhs_or_phi_result (use_stmt);
2656               bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
2657             }
2658
2659           /* Propagation into these nodes may make certain edges in
2660              the CFG unexecutable.  We want to identify them as PHI nodes
2661              at the destination of those unexecutable edges may become
2662              degenerates.  */
2663           else if (gimple_code (use_stmt) == GIMPLE_COND
2664                    || gimple_code (use_stmt) == GIMPLE_SWITCH
2665                    || gimple_code (use_stmt) == GIMPLE_GOTO)
2666             {
2667               tree val;
2668
2669               if (gimple_code (use_stmt) == GIMPLE_COND)
2670                 val = fold_binary (gimple_cond_code (use_stmt),
2671                                    boolean_type_node,
2672                                    gimple_cond_lhs (use_stmt),
2673                                    gimple_cond_rhs (use_stmt));
2674               else if (gimple_code (use_stmt) == GIMPLE_SWITCH)
2675                 val = gimple_switch_index (use_stmt);
2676               else
2677                 val = gimple_goto_dest  (use_stmt);
2678
2679               if (val && is_gimple_min_invariant (val))
2680                 {
2681                   basic_block bb = gimple_bb (use_stmt);
2682                   edge te = find_taken_edge (bb, val);
2683                   edge_iterator ei;
2684                   edge e;
2685                   gimple_stmt_iterator gsi, psi;
2686
2687                   /* Remove all outgoing edges except TE.  */
2688                   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));)
2689                     {
2690                       if (e != te)
2691                         {
2692                           /* Mark all the PHI nodes at the destination of
2693                              the unexecutable edge as interesting.  */
2694                           for (psi = gsi_start_phis (e->dest);
2695                                !gsi_end_p (psi);
2696                                gsi_next (&psi))
2697                             {
2698                               gimple phi = gsi_stmt (psi);
2699
2700                               tree result = gimple_phi_result (phi);
2701                               int version = SSA_NAME_VERSION (result);
2702
2703                               bitmap_set_bit (interesting_names, version);
2704                             }
2705
2706                           te->probability += e->probability;
2707
2708                           te->count += e->count;
2709                           remove_edge (e);
2710                           cfg_altered = true;
2711                         }
2712                       else
2713                         ei_next (&ei);
2714                     }
2715
2716                   gsi = gsi_last_bb (gimple_bb (use_stmt));
2717                   gsi_remove (&gsi, true);
2718
2719                   /* And fixup the flags on the single remaining edge.  */
2720                   te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
2721                   te->flags &= ~EDGE_ABNORMAL;
2722                   te->flags |= EDGE_FALLTHRU;
2723                   if (te->probability > REG_BR_PROB_BASE)
2724                     te->probability = REG_BR_PROB_BASE;
2725                 }
2726             }
2727         }
2728
2729       /* Ensure there is nothing else to do. */ 
2730       gcc_assert (!all || has_zero_uses (lhs));
2731
2732       /* If we were able to propagate away all uses of LHS, then
2733          we can remove STMT.  */
2734       if (all)
2735         remove_stmt_or_phi (stmt);
2736     }
2737 }
2738
2739 /* STMT is either a PHI node (potentially a degenerate PHI node) or
2740    a statement that is a trivial copy or constant initialization.
2741
2742    Attempt to eliminate T by propagating its RHS into all uses of
2743    its LHS.  This may in turn set new bits in INTERESTING_NAMES
2744    for nodes we want to revisit later.
2745
2746    All exit paths should clear INTERESTING_NAMES for the result
2747    of STMT.  */
2748
2749 static void
2750 eliminate_const_or_copy (gimple stmt, bitmap interesting_names)
2751 {
2752   tree lhs = get_lhs_or_phi_result (stmt);
2753   tree rhs;
2754   int version = SSA_NAME_VERSION (lhs);
2755
2756   /* If the LHS of this statement or PHI has no uses, then we can
2757      just eliminate it.  This can occur if, for example, the PHI
2758      was created by block duplication due to threading and its only
2759      use was in the conditional at the end of the block which was
2760      deleted.  */
2761   if (has_zero_uses (lhs))
2762     {
2763       bitmap_clear_bit (interesting_names, version);
2764       remove_stmt_or_phi (stmt);
2765       return;
2766     }
2767
2768   /* Get the RHS of the assignment or PHI node if the PHI is a
2769      degenerate.  */
2770   rhs = get_rhs_or_phi_arg (stmt);
2771   if (!rhs)
2772     {
2773       bitmap_clear_bit (interesting_names, version);
2774       return;
2775     }
2776
2777   propagate_rhs_into_lhs (stmt, lhs, rhs, interesting_names);
2778
2779   /* Note that STMT may well have been deleted by now, so do
2780      not access it, instead use the saved version # to clear
2781      T's entry in the worklist.  */
2782   bitmap_clear_bit (interesting_names, version);
2783 }
2784
2785 /* The first phase in degenerate PHI elimination.
2786
2787    Eliminate the degenerate PHIs in BB, then recurse on the
2788    dominator children of BB.  */
2789
2790 static void
2791 eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names)
2792 {
2793   gimple_stmt_iterator gsi;
2794   basic_block son;
2795
2796   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2797     {
2798       gimple phi = gsi_stmt (gsi);
2799
2800       eliminate_const_or_copy (phi, interesting_names);
2801     }
2802
2803   /* Recurse into the dominator children of BB.  */
2804   for (son = first_dom_son (CDI_DOMINATORS, bb);
2805        son;
2806        son = next_dom_son (CDI_DOMINATORS, son))
2807     eliminate_degenerate_phis_1 (son, interesting_names);
2808 }
2809
2810
2811 /* A very simple pass to eliminate degenerate PHI nodes from the
2812    IL.  This is meant to be fast enough to be able to be run several
2813    times in the optimization pipeline.
2814
2815    Certain optimizations, particularly those which duplicate blocks
2816    or remove edges from the CFG can create or expose PHIs which are
2817    trivial copies or constant initializations.
2818
2819    While we could pick up these optimizations in DOM or with the
2820    combination of copy-prop and CCP, those solutions are far too
2821    heavy-weight for our needs.
2822
2823    This implementation has two phases so that we can efficiently
2824    eliminate the first order degenerate PHIs and second order
2825    degenerate PHIs.
2826
2827    The first phase performs a dominator walk to identify and eliminate
2828    the vast majority of the degenerate PHIs.  When a degenerate PHI
2829    is identified and eliminated any affected statements or PHIs
2830    are put on a worklist.
2831
2832    The second phase eliminates degenerate PHIs and trivial copies
2833    or constant initializations using the worklist.  This is how we
2834    pick up the secondary optimization opportunities with minimal
2835    cost.  */
2836
2837 static unsigned int
2838 eliminate_degenerate_phis (void)
2839 {
2840   bitmap interesting_names;
2841   bitmap interesting_names1;
2842
2843   /* Bitmap of blocks which need EH information updated.  We can not
2844      update it on-the-fly as doing so invalidates the dominator tree.  */
2845   need_eh_cleanup = BITMAP_ALLOC (NULL);
2846
2847   /* INTERESTING_NAMES is effectively our worklist, indexed by
2848      SSA_NAME_VERSION.
2849
2850      A set bit indicates that the statement or PHI node which
2851      defines the SSA_NAME should be (re)examined to determine if
2852      it has become a degenerate PHI or trivial const/copy propagation
2853      opportunity. 
2854
2855      Experiments have show we generally get better compilation
2856      time behavior with bitmaps rather than sbitmaps.  */
2857   interesting_names = BITMAP_ALLOC (NULL);
2858   interesting_names1 = BITMAP_ALLOC (NULL);
2859
2860   calculate_dominance_info (CDI_DOMINATORS);
2861   cfg_altered = false;
2862
2863   /* First phase.  Eliminate degenerate PHIs via a dominator
2864      walk of the CFG.
2865
2866      Experiments have indicated that we generally get better
2867      compile-time behavior by visiting blocks in the first
2868      phase in dominator order.  Presumably this is because walking
2869      in dominator order leaves fewer PHIs for later examination
2870      by the worklist phase.  */
2871   eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR, interesting_names);
2872
2873   /* Second phase.  Eliminate second order degenerate PHIs as well
2874      as trivial copies or constant initializations identified by
2875      the first phase or this phase.  Basically we keep iterating
2876      until our set of INTERESTING_NAMEs is empty.   */
2877   while (!bitmap_empty_p (interesting_names))
2878     {
2879       unsigned int i;
2880       bitmap_iterator bi;
2881
2882       /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap
2883          changed during the loop.  Copy it to another bitmap and
2884          use that.  */
2885       bitmap_copy (interesting_names1, interesting_names);
2886
2887       EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi)
2888         {
2889           tree name = ssa_name (i);
2890
2891           /* Ignore SSA_NAMEs that have been released because
2892              their defining statement was deleted (unreachable).  */
2893           if (name)
2894             eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)),
2895                                      interesting_names);
2896         }
2897     }
2898
2899   if (cfg_altered)
2900     free_dominance_info (CDI_DOMINATORS);
2901
2902   /* Propagation of const and copies may make some EH edges dead.  Purge
2903      such edges from the CFG as needed.  */
2904   if (!bitmap_empty_p (need_eh_cleanup))
2905     {
2906       gimple_purge_all_dead_eh_edges (need_eh_cleanup);
2907       BITMAP_FREE (need_eh_cleanup);
2908     }
2909
2910   BITMAP_FREE (interesting_names);
2911   BITMAP_FREE (interesting_names1);
2912   return 0;
2913 }
2914
2915 struct gimple_opt_pass pass_phi_only_cprop =
2916 {
2917  {
2918   GIMPLE_PASS,
2919   "phicprop",                           /* name */
2920   gate_dominator,                       /* gate */
2921   eliminate_degenerate_phis,            /* execute */
2922   NULL,                                 /* sub */
2923   NULL,                                 /* next */
2924   0,                                    /* static_pass_number */
2925   TV_TREE_PHI_CPROP,                    /* tv_id */
2926   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
2927   0,                                    /* properties_provided */
2928   0,                                    /* properties_destroyed */
2929   0,                                    /* todo_flags_start */
2930   TODO_cleanup_cfg
2931     | TODO_dump_func 
2932     | TODO_ggc_collect
2933     | TODO_verify_ssa
2934     | TODO_verify_stmts
2935     | TODO_update_ssa                   /* todo_flags_finish */
2936  }
2937 };