OSDN Git Service

Add source_location support to PHI arguments.
[pf3gnuchains/gcc-fork.git] / gcc / tree-into-ssa.c
1 /* Rewrite a program in Normal form into SSA.
2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009
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 "langhooks.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
33 #include "output.h"
34 #include "expr.h"
35 #include "function.h"
36 #include "diagnostic.h"
37 #include "bitmap.h"
38 #include "tree-flow.h"
39 #include "gimple.h"
40 #include "tree-inline.h"
41 #include "varray.h"
42 #include "timevar.h"
43 #include "hashtab.h"
44 #include "tree-dump.h"
45 #include "tree-pass.h"
46 #include "cfgloop.h"
47 #include "domwalk.h"
48 #include "ggc.h"
49 #include "params.h"
50 #include "vecprim.h"
51
52
53 /* This file builds the SSA form for a function as described in:
54    R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
55    Computing Static Single Assignment Form and the Control Dependence
56    Graph. ACM Transactions on Programming Languages and Systems,
57    13(4):451-490, October 1991.  */
58
59 /* Structure to map a variable VAR to the set of blocks that contain
60    definitions for VAR.  */
61 struct def_blocks_d
62 {
63   /* The variable.  */
64   tree var;
65
66   /* Blocks that contain definitions of VAR.  Bit I will be set if the
67      Ith block contains a definition of VAR.  */
68   bitmap def_blocks;
69
70   /* Blocks that contain a PHI node for VAR.  */
71   bitmap phi_blocks;
72
73   /* Blocks where VAR is live-on-entry.  Similar semantics as
74      DEF_BLOCKS.  */
75   bitmap livein_blocks;
76 };
77
78
79 /* Each entry in DEF_BLOCKS contains an element of type STRUCT
80    DEF_BLOCKS_D, mapping a variable VAR to a bitmap describing all the
81    basic blocks where VAR is defined (assigned a new value).  It also
82    contains a bitmap of all the blocks where VAR is live-on-entry
83    (i.e., there is a use of VAR in block B without a preceding
84    definition in B).  The live-on-entry information is used when
85    computing PHI pruning heuristics.  */
86 static htab_t def_blocks;
87
88 /* Stack of trees used to restore the global currdefs to its original
89    state after completing rewriting of a block and its dominator
90    children.  Its elements have the following properties:
91
92    - An SSA_NAME (N) indicates that the current definition of the
93      underlying variable should be set to the given SSA_NAME.  If the
94      symbol associated with the SSA_NAME is not a GIMPLE register, the
95      next slot in the stack must be a _DECL node (SYM).  In this case,
96      the name N in the previous slot is the current reaching
97      definition for SYM.
98
99    - A _DECL node indicates that the underlying variable has no
100      current definition.
101
102    - A NULL node at the top entry is used to mark the last slot
103      associated with the current block.  */
104 static VEC(tree,heap) *block_defs_stack;
105
106
107 /* Set of existing SSA names being replaced by update_ssa.  */
108 static sbitmap old_ssa_names;
109
110 /* Set of new SSA names being added by update_ssa.  Note that both
111    NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
112    the operations done on them are presence tests.  */
113 static sbitmap new_ssa_names;
114
115 sbitmap interesting_blocks;
116
117 /* Set of SSA names that have been marked to be released after they
118    were registered in the replacement table.  They will be finally
119    released after we finish updating the SSA web.  */
120 static bitmap names_to_release;
121
122 static VEC(gimple_vec, heap) *phis_to_rewrite;
123
124 /* The bitmap of non-NULL elements of PHIS_TO_REWRITE.  */
125 static bitmap blocks_with_phis_to_rewrite;
126
127 /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES.  These sets need
128    to grow as the callers to register_new_name_mapping will typically
129    create new names on the fly.  FIXME.  Currently set to 1/3 to avoid
130    frequent reallocations but still need to find a reasonable growth
131    strategy.  */
132 #define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
133
134 /* Tuple used to represent replacement mappings.  */
135 struct repl_map_d
136 {
137   tree name;
138   bitmap set;
139 };
140
141
142 /* NEW -> OLD_SET replacement table.  If we are replacing several
143    existing SSA names O_1, O_2, ..., O_j with a new name N_i,
144    then REPL_TBL[N_i] = { O_1, O_2, ..., O_j }.  */
145 static htab_t repl_tbl;
146
147 /* The function the SSA updating data structures have been initialized for.
148    NULL if they need to be initialized by register_new_name_mapping.  */
149 static struct function *update_ssa_initialized_fn = NULL;
150
151 /* Statistics kept by update_ssa to use in the virtual mapping
152    heuristic.  If the number of virtual mappings is beyond certain
153    threshold, the updater will switch from using the mappings into
154    renaming the virtual symbols from scratch.  In some cases, the
155    large number of name mappings for virtual names causes significant
156    slowdowns in the PHI insertion code.  */
157 struct update_ssa_stats_d
158 {
159   unsigned num_virtual_mappings;
160   unsigned num_total_mappings;
161   bitmap virtual_symbols;
162   unsigned num_virtual_symbols;
163 };
164 static struct update_ssa_stats_d update_ssa_stats;
165
166 /* Global data to attach to the main dominator walk structure.  */
167 struct mark_def_sites_global_data
168 {
169   /* This bitmap contains the variables which are set before they
170      are used in a basic block.  */
171   bitmap kills;
172 };
173
174
175 /* Information stored for SSA names.  */
176 struct ssa_name_info
177 {
178   /* The current reaching definition replacing this SSA name.  */
179   tree current_def;
180
181   /* This field indicates whether or not the variable may need PHI nodes.
182      See the enum's definition for more detailed information about the
183      states.  */
184   ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
185
186   /* Age of this record (so that info_for_ssa_name table can be cleared
187      quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
188      are assumed to be null.  */
189   unsigned age;
190 };
191
192 /* The information associated with names.  */
193 typedef struct ssa_name_info *ssa_name_info_p;
194 DEF_VEC_P (ssa_name_info_p);
195 DEF_VEC_ALLOC_P (ssa_name_info_p, heap);
196
197 static VEC(ssa_name_info_p, heap) *info_for_ssa_name;
198 static unsigned current_info_for_ssa_name_age;
199
200 /* The set of blocks affected by update_ssa.  */
201 static bitmap blocks_to_update;
202
203 /* The main entry point to the SSA renamer (rewrite_blocks) may be
204    called several times to do different, but related, tasks.
205    Initially, we need it to rename the whole program into SSA form.
206    At other times, we may need it to only rename into SSA newly
207    exposed symbols.  Finally, we can also call it to incrementally fix
208    an already built SSA web.  */
209 enum rewrite_mode {
210     /* Convert the whole function into SSA form.  */
211     REWRITE_ALL,
212
213     /* Incrementally update the SSA web by replacing existing SSA
214        names with new ones.  See update_ssa for details.  */
215     REWRITE_UPDATE
216 };
217
218
219
220
221 /* Prototypes for debugging functions.  */
222 extern void dump_tree_ssa (FILE *);
223 extern void debug_tree_ssa (void);
224 extern void debug_def_blocks (void);
225 extern void dump_tree_ssa_stats (FILE *);
226 extern void debug_tree_ssa_stats (void);
227 extern void dump_update_ssa (FILE *);
228 extern void debug_update_ssa (void);
229 extern void dump_names_replaced_by (FILE *, tree);
230 extern void debug_names_replaced_by (tree);
231 extern void dump_def_blocks (FILE *);
232 extern void debug_def_blocks (void);
233 extern void dump_defs_stack (FILE *, int);
234 extern void debug_defs_stack (int);
235 extern void dump_currdefs (FILE *);
236 extern void debug_currdefs (void);
237
238 /* Return true if STMT needs to be rewritten.  When renaming a subset
239    of the variables, not all statements will be processed.  This is
240    decided in mark_def_sites.  */
241
242 static inline bool
243 rewrite_uses_p (gimple stmt)
244 {
245   return gimple_visited_p (stmt);
246 }
247
248
249 /* Set the rewrite marker on STMT to the value given by REWRITE_P.  */
250
251 static inline void
252 set_rewrite_uses (gimple stmt, bool rewrite_p)
253 {
254   gimple_set_visited (stmt, rewrite_p);
255 }
256
257
258 /* Return true if the DEFs created by statement STMT should be
259    registered when marking new definition sites.  This is slightly
260    different than rewrite_uses_p: it's used by update_ssa to
261    distinguish statements that need to have both uses and defs
262    processed from those that only need to have their defs processed.
263    Statements that define new SSA names only need to have their defs
264    registered, but they don't need to have their uses renamed.  */
265
266 static inline bool
267 register_defs_p (gimple stmt)
268 {
269   return gimple_plf (stmt, GF_PLF_1) != 0;
270 }
271
272
273 /* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered.  */
274
275 static inline void
276 set_register_defs (gimple stmt, bool register_defs_p)
277 {
278   gimple_set_plf (stmt, GF_PLF_1, register_defs_p);
279 }
280
281
282 /* Get the information associated with NAME.  */
283
284 static inline ssa_name_info_p
285 get_ssa_name_ann (tree name)
286 {
287   unsigned ver = SSA_NAME_VERSION (name);
288   unsigned len = VEC_length (ssa_name_info_p, info_for_ssa_name);
289   struct ssa_name_info *info;
290
291   if (ver >= len)
292     {
293       unsigned new_len = num_ssa_names;
294
295       VEC_reserve (ssa_name_info_p, heap, info_for_ssa_name, new_len);
296       while (len++ < new_len)
297         {
298           struct ssa_name_info *info = XCNEW (struct ssa_name_info);
299           info->age = current_info_for_ssa_name_age;
300           VEC_quick_push (ssa_name_info_p, info_for_ssa_name, info);
301         }
302     }
303
304   info = VEC_index (ssa_name_info_p, info_for_ssa_name, ver);
305   if (info->age < current_info_for_ssa_name_age)
306     {
307       info->need_phi_state = NEED_PHI_STATE_UNKNOWN;
308       info->current_def = NULL_TREE;
309       info->age = current_info_for_ssa_name_age;
310     }
311
312   return info;
313 }
314
315
316 /* Clears info for SSA names.  */
317
318 static void
319 clear_ssa_name_info (void)
320 {
321   current_info_for_ssa_name_age++;
322 }
323
324
325 /* Get phi_state field for VAR.  */
326
327 static inline enum need_phi_state
328 get_phi_state (tree var)
329 {
330   if (TREE_CODE (var) == SSA_NAME)
331     return get_ssa_name_ann (var)->need_phi_state;
332   else
333     return var_ann (var)->need_phi_state;
334 }
335
336
337 /* Sets phi_state field for VAR to STATE.  */
338
339 static inline void
340 set_phi_state (tree var, enum need_phi_state state)
341 {
342   if (TREE_CODE (var) == SSA_NAME)
343     get_ssa_name_ann (var)->need_phi_state = state;
344   else
345     var_ann (var)->need_phi_state = state;
346 }
347
348
349 /* Return the current definition for VAR.  */
350
351 tree
352 get_current_def (tree var)
353 {
354   if (TREE_CODE (var) == SSA_NAME)
355     return get_ssa_name_ann (var)->current_def;
356   else
357     return var_ann (var)->current_def;
358 }
359
360
361 /* Sets current definition of VAR to DEF.  */
362
363 void
364 set_current_def (tree var, tree def)
365 {
366   if (TREE_CODE (var) == SSA_NAME)
367     get_ssa_name_ann (var)->current_def = def;
368   else
369     var_ann (var)->current_def = def;
370 }
371
372
373 /* Compute global livein information given the set of blocks where
374    an object is locally live at the start of the block (LIVEIN)
375    and the set of blocks where the object is defined (DEF_BLOCKS).
376
377    Note: This routine augments the existing local livein information
378    to include global livein (i.e., it modifies the underlying bitmap
379    for LIVEIN).  */
380
381 void
382 compute_global_livein (bitmap livein ATTRIBUTE_UNUSED, bitmap def_blocks ATTRIBUTE_UNUSED)
383 {
384   basic_block bb, *worklist, *tos;
385   unsigned i;
386   bitmap_iterator bi;
387
388   tos = worklist
389     = (basic_block *) xmalloc (sizeof (basic_block) * (last_basic_block + 1));
390
391   EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
392     *tos++ = BASIC_BLOCK (i);
393
394   /* Iterate until the worklist is empty.  */
395   while (tos != worklist)
396     {
397       edge e;
398       edge_iterator ei;
399
400       /* Pull a block off the worklist.  */
401       bb = *--tos;
402
403       /* For each predecessor block.  */
404       FOR_EACH_EDGE (e, ei, bb->preds)
405         {
406           basic_block pred = e->src;
407           int pred_index = pred->index;
408
409           /* None of this is necessary for the entry block.  */
410           if (pred != ENTRY_BLOCK_PTR
411               && ! bitmap_bit_p (livein, pred_index)
412               && ! bitmap_bit_p (def_blocks, pred_index))
413             {
414               *tos++ = pred;
415               bitmap_set_bit (livein, pred_index);
416             }
417         }
418     }
419
420   free (worklist);
421 }
422
423
424 /* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
425    all statements in basic block BB.  */
426
427 static void
428 initialize_flags_in_bb (basic_block bb)
429 {
430   gimple stmt;
431   gimple_stmt_iterator gsi;
432
433   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
434     {
435       gimple phi = gsi_stmt (gsi);
436       set_rewrite_uses (phi, false);
437       set_register_defs (phi, false);
438     }
439
440   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
441     {
442       stmt = gsi_stmt (gsi);
443
444       /* We are going to use the operand cache API, such as
445          SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST.  The operand
446          cache for each statement should be up-to-date.  */
447       gcc_assert (!gimple_modified_p (stmt));
448       set_rewrite_uses (stmt, false);
449       set_register_defs (stmt, false);
450     }
451 }
452
453 /* Mark block BB as interesting for update_ssa.  */
454
455 static void
456 mark_block_for_update (basic_block bb)
457 {
458   gcc_assert (blocks_to_update != NULL);
459   if (bitmap_bit_p (blocks_to_update, bb->index))
460     return;
461   bitmap_set_bit (blocks_to_update, bb->index);
462   initialize_flags_in_bb (bb);
463 }
464
465 /* Return the set of blocks where variable VAR is defined and the blocks
466    where VAR is live on entry (livein).  If no entry is found in
467    DEF_BLOCKS, a new one is created and returned.  */
468
469 static inline struct def_blocks_d *
470 get_def_blocks_for (tree var)
471 {
472   struct def_blocks_d db, *db_p;
473   void **slot;
474
475   db.var = var;
476   slot = htab_find_slot (def_blocks, (void *) &db, INSERT);
477   if (*slot == NULL)
478     {
479       db_p = XNEW (struct def_blocks_d);
480       db_p->var = var;
481       db_p->def_blocks = BITMAP_ALLOC (NULL);
482       db_p->phi_blocks = BITMAP_ALLOC (NULL);
483       db_p->livein_blocks = BITMAP_ALLOC (NULL);
484       *slot = (void *) db_p;
485     }
486   else
487     db_p = (struct def_blocks_d *) *slot;
488
489   return db_p;
490 }
491
492
493 /* Mark block BB as the definition site for variable VAR.  PHI_P is true if
494    VAR is defined by a PHI node.  */
495
496 static void
497 set_def_block (tree var, basic_block bb, bool phi_p)
498 {
499   struct def_blocks_d *db_p;
500   enum need_phi_state state;
501
502   state = get_phi_state (var);
503   db_p = get_def_blocks_for (var);
504
505   /* Set the bit corresponding to the block where VAR is defined.  */
506   bitmap_set_bit (db_p->def_blocks, bb->index);
507   if (phi_p)
508     bitmap_set_bit (db_p->phi_blocks, bb->index);
509
510   /* Keep track of whether or not we may need to insert PHI nodes.
511
512      If we are in the UNKNOWN state, then this is the first definition
513      of VAR.  Additionally, we have not seen any uses of VAR yet, so
514      we do not need a PHI node for this variable at this time (i.e.,
515      transition to NEED_PHI_STATE_NO).
516
517      If we are in any other state, then we either have multiple definitions
518      of this variable occurring in different blocks or we saw a use of the
519      variable which was not dominated by the block containing the
520      definition(s).  In this case we may need a PHI node, so enter
521      state NEED_PHI_STATE_MAYBE.  */
522   if (state == NEED_PHI_STATE_UNKNOWN)
523     set_phi_state (var, NEED_PHI_STATE_NO);
524   else
525     set_phi_state (var, NEED_PHI_STATE_MAYBE);
526 }
527
528
529 /* Mark block BB as having VAR live at the entry to BB.  */
530
531 static void
532 set_livein_block (tree var, basic_block bb)
533 {
534   struct def_blocks_d *db_p;
535   enum need_phi_state state = get_phi_state (var);
536
537   db_p = get_def_blocks_for (var);
538
539   /* Set the bit corresponding to the block where VAR is live in.  */
540   bitmap_set_bit (db_p->livein_blocks, bb->index);
541
542   /* Keep track of whether or not we may need to insert PHI nodes.
543
544      If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
545      by the single block containing the definition(s) of this variable.  If
546      it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
547      NEED_PHI_STATE_MAYBE.  */
548   if (state == NEED_PHI_STATE_NO)
549     {
550       int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
551
552       if (def_block_index == -1
553           || ! dominated_by_p (CDI_DOMINATORS, bb,
554                                BASIC_BLOCK (def_block_index)))
555         set_phi_state (var, NEED_PHI_STATE_MAYBE);
556     }
557   else
558     set_phi_state (var, NEED_PHI_STATE_MAYBE);
559 }
560
561
562 /* Return true if symbol SYM is marked for renaming.  */
563
564 static inline bool
565 symbol_marked_for_renaming (tree sym)
566 {
567   return bitmap_bit_p (SYMS_TO_RENAME (cfun), DECL_UID (sym));
568 }
569
570
571 /* Return true if NAME is in OLD_SSA_NAMES.  */
572
573 static inline bool
574 is_old_name (tree name)
575 {
576   unsigned ver = SSA_NAME_VERSION (name);
577   if (!new_ssa_names)
578     return false;
579   return ver < new_ssa_names->n_bits && TEST_BIT (old_ssa_names, ver);
580 }
581
582
583 /* Return true if NAME is in NEW_SSA_NAMES.  */
584
585 static inline bool
586 is_new_name (tree name)
587 {
588   unsigned ver = SSA_NAME_VERSION (name);
589   if (!new_ssa_names)
590     return false;
591   return ver < new_ssa_names->n_bits && TEST_BIT (new_ssa_names, ver);
592 }
593
594
595 /* Hashing and equality functions for REPL_TBL.  */
596
597 static hashval_t
598 repl_map_hash (const void *p)
599 {
600   return htab_hash_pointer ((const void *)((const struct repl_map_d *)p)->name);
601 }
602
603 static int
604 repl_map_eq (const void *p1, const void *p2)
605 {
606   return ((const struct repl_map_d *)p1)->name
607          == ((const struct repl_map_d *)p2)->name;
608 }
609
610 static void
611 repl_map_free (void *p)
612 {
613   BITMAP_FREE (((struct repl_map_d *)p)->set);
614   free (p);
615 }
616
617
618 /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET).  */
619
620 static inline bitmap
621 names_replaced_by (tree new_tree)
622 {
623   struct repl_map_d m;
624   void **slot;
625
626   m.name = new_tree;
627   slot = htab_find_slot (repl_tbl, (void *) &m, NO_INSERT);
628
629   /* If N was not registered in the replacement table, return NULL.  */
630   if (slot == NULL || *slot == NULL)
631     return NULL;
632
633   return ((struct repl_map_d *) *slot)->set;
634 }
635
636
637 /* Add OLD to REPL_TBL[NEW_TREE].SET.  */
638
639 static inline void
640 add_to_repl_tbl (tree new_tree, tree old)
641 {
642   struct repl_map_d m, *mp;
643   void **slot;
644
645   m.name = new_tree;
646   slot = htab_find_slot (repl_tbl, (void *) &m, INSERT);
647   if (*slot == NULL)
648     {
649       mp = XNEW (struct repl_map_d);
650       mp->name = new_tree;
651       mp->set = BITMAP_ALLOC (NULL);
652       *slot = (void *) mp;
653     }
654   else
655     mp = (struct repl_map_d *) *slot;
656
657   bitmap_set_bit (mp->set, SSA_NAME_VERSION (old));
658 }
659
660
661 /* Add a new mapping NEW_TREE -> OLD REPL_TBL.  Every entry N_i in REPL_TBL
662    represents the set of names O_1 ... O_j replaced by N_i.  This is
663    used by update_ssa and its helpers to introduce new SSA names in an
664    already formed SSA web.  */
665
666 static void
667 add_new_name_mapping (tree new_tree, tree old)
668 {
669   timevar_push (TV_TREE_SSA_INCREMENTAL);
670
671   /* OLD and NEW_TREE must be different SSA names for the same symbol.  */
672   gcc_assert (new_tree != old && SSA_NAME_VAR (new_tree) == SSA_NAME_VAR (old));
673
674   /* If this mapping is for virtual names, we will need to update
675      virtual operands.  If this is a mapping for .MEM, then we gather
676      the symbols associated with each name.  */
677   if (!is_gimple_reg (new_tree))
678     {
679       tree sym;
680
681       update_ssa_stats.num_virtual_mappings++;
682       update_ssa_stats.num_virtual_symbols++;
683
684       /* Keep counts of virtual mappings and symbols to use in the
685          virtual mapping heuristic.  If we have large numbers of
686          virtual mappings for a relatively low number of symbols, it
687          will make more sense to rename the symbols from scratch.
688          Otherwise, the insertion of PHI nodes for each of the old
689          names in these mappings will be very slow.  */
690       sym = SSA_NAME_VAR (new_tree);
691       bitmap_set_bit (update_ssa_stats.virtual_symbols, DECL_UID (sym));
692     }
693
694   /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
695      caller may have created new names since the set was created.  */
696   if (new_ssa_names->n_bits <= num_ssa_names - 1)
697     {
698       unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
699       new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
700       old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
701     }
702
703   /* Update the REPL_TBL table.  */
704   add_to_repl_tbl (new_tree, old);
705
706   /* If OLD had already been registered as a new name, then all the
707      names that OLD replaces should also be replaced by NEW_TREE.  */
708   if (is_new_name (old))
709     bitmap_ior_into (names_replaced_by (new_tree), names_replaced_by (old));
710
711   /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
712      respectively.  */
713   SET_BIT (new_ssa_names, SSA_NAME_VERSION (new_tree));
714   SET_BIT (old_ssa_names, SSA_NAME_VERSION (old));
715
716   /* Update mapping counter to use in the virtual mapping heuristic.  */
717   update_ssa_stats.num_total_mappings++;
718
719   timevar_pop (TV_TREE_SSA_INCREMENTAL);
720 }
721
722
723 /* Call back for walk_dominator_tree used to collect definition sites
724    for every variable in the function.  For every statement S in block
725    BB:
726
727    1- Variables defined by S in the DEFS of S are marked in the bitmap
728       KILLS.
729
730    2- If S uses a variable VAR and there is no preceding kill of VAR,
731       then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
732
733    This information is used to determine which variables are live
734    across block boundaries to reduce the number of PHI nodes
735    we create.  */
736
737 static void
738 mark_def_sites (basic_block bb, gimple stmt, bitmap kills)
739 {
740   tree def;
741   use_operand_p use_p;
742   ssa_op_iter iter;
743
744   /* Since this is the first time that we rewrite the program into SSA
745      form, force an operand scan on every statement.  */
746   update_stmt (stmt);
747
748   gcc_assert (blocks_to_update == NULL);
749   set_register_defs (stmt, false);
750   set_rewrite_uses (stmt, false);
751
752   /* If a variable is used before being set, then the variable is live
753      across a block boundary, so mark it live-on-entry to BB.  */
754   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
755     {
756       tree sym = USE_FROM_PTR (use_p);
757       gcc_assert (DECL_P (sym));
758       if (!bitmap_bit_p (kills, DECL_UID (sym)))
759         set_livein_block (sym, bb);
760       set_rewrite_uses (stmt, true);
761     }
762   
763   /* Now process the defs.  Mark BB as the definition block and add
764      each def to the set of killed symbols.  */
765   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
766     {
767       gcc_assert (DECL_P (def));
768       set_def_block (def, bb, false);
769       bitmap_set_bit (kills, DECL_UID (def));
770       set_register_defs (stmt, true);
771     }
772
773   /* If we found the statement interesting then also mark the block BB
774      as interesting.  */
775   if (rewrite_uses_p (stmt) || register_defs_p (stmt))
776     SET_BIT (interesting_blocks, bb->index);
777 }
778
779 /* Structure used by prune_unused_phi_nodes to record bounds of the intervals
780    in the dfs numbering of the dominance tree.  */
781
782 struct dom_dfsnum
783 {
784   /* Basic block whose index this entry corresponds to.  */
785   unsigned bb_index;
786
787   /* The dfs number of this node.  */
788   unsigned dfs_num;
789 };
790
791 /* Compares two entries of type struct dom_dfsnum by dfs_num field.  Callback
792    for qsort.  */
793
794 static int
795 cmp_dfsnum (const void *a, const void *b)
796 {
797   const struct dom_dfsnum *const da = (const struct dom_dfsnum *) a;
798   const struct dom_dfsnum *const db = (const struct dom_dfsnum *) b;
799
800   return (int) da->dfs_num - (int) db->dfs_num;
801 }
802
803 /* Among the intervals starting at the N points specified in DEFS, find
804    the one that contains S, and return its bb_index.  */
805
806 static unsigned
807 find_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s)
808 {
809   unsigned f = 0, t = n, m;
810
811   while (t > f + 1)
812     {
813       m = (f + t) / 2;
814       if (defs[m].dfs_num <= s)
815         f = m;
816       else
817         t = m;
818     }
819
820   return defs[f].bb_index;
821 }
822
823 /* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
824    KILLS is a bitmap of blocks where the value is defined before any use.  */
825
826 static void
827 prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses)
828 {
829   VEC(int, heap) *worklist;
830   bitmap_iterator bi;
831   unsigned i, b, p, u, top;
832   bitmap live_phis;
833   basic_block def_bb, use_bb;
834   edge e;
835   edge_iterator ei;
836   bitmap to_remove;
837   struct dom_dfsnum *defs;
838   unsigned n_defs, adef;
839
840   if (bitmap_empty_p (uses))
841     {
842       bitmap_clear (phis);
843       return;
844     }
845
846   /* The phi must dominate a use, or an argument of a live phi.  Also, we
847      do not create any phi nodes in def blocks, unless they are also livein.  */
848   to_remove = BITMAP_ALLOC (NULL);
849   bitmap_and_compl (to_remove, kills, uses);
850   bitmap_and_compl_into (phis, to_remove);
851   if (bitmap_empty_p (phis))
852     {
853       BITMAP_FREE (to_remove);
854       return;
855     }
856
857   /* We want to remove the unnecessary phi nodes, but we do not want to compute
858      liveness information, as that may be linear in the size of CFG, and if
859      there are lot of different variables to rewrite, this may lead to quadratic
860      behavior.
861
862      Instead, we basically emulate standard dce.  We put all uses to worklist,
863      then for each of them find the nearest def that dominates them.  If this
864      def is a phi node, we mark it live, and if it was not live before, we
865      add the predecessors of its basic block to the worklist.
866    
867      To quickly locate the nearest def that dominates use, we use dfs numbering
868      of the dominance tree (that is already available in order to speed up
869      queries).  For each def, we have the interval given by the dfs number on
870      entry to and on exit from the corresponding subtree in the dominance tree.
871      The nearest dominator for a given use is the smallest of these intervals
872      that contains entry and exit dfs numbers for the basic block with the use.
873      If we store the bounds for all the uses to an array and sort it, we can
874      locate the nearest dominating def in logarithmic time by binary search.*/
875   bitmap_ior (to_remove, kills, phis);
876   n_defs = bitmap_count_bits (to_remove);
877   defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1);
878   defs[0].bb_index = 1;
879   defs[0].dfs_num = 0;
880   adef = 1;
881   EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi)
882     {
883       def_bb = BASIC_BLOCK (i);
884       defs[adef].bb_index = i;
885       defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb);
886       defs[adef + 1].bb_index = i;
887       defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb);
888       adef += 2;
889     }
890   BITMAP_FREE (to_remove);
891   gcc_assert (adef == 2 * n_defs + 1);
892   qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum);
893   gcc_assert (defs[0].bb_index == 1);
894
895   /* Now each DEFS entry contains the number of the basic block to that the
896      dfs number corresponds.  Change them to the number of basic block that
897      corresponds to the interval following the dfs number.  Also, for the
898      dfs_out numbers, increase the dfs number by one (so that it corresponds
899      to the start of the following interval, not to the end of the current
900      one).  We use WORKLIST as a stack.  */
901   worklist = VEC_alloc (int, heap, n_defs + 1);
902   VEC_quick_push (int, worklist, 1);
903   top = 1;
904   n_defs = 1;
905   for (i = 1; i < adef; i++)
906     {
907       b = defs[i].bb_index;
908       if (b == top)
909         {
910           /* This is a closing element.  Interval corresponding to the top
911              of the stack after removing it follows.  */
912           VEC_pop (int, worklist);
913           top = VEC_index (int, worklist, VEC_length (int, worklist) - 1);
914           defs[n_defs].bb_index = top;
915           defs[n_defs].dfs_num = defs[i].dfs_num + 1;
916         }
917       else
918         {
919           /* Opening element.  Nothing to do, just push it to the stack and move
920              it to the correct position.  */
921           defs[n_defs].bb_index = defs[i].bb_index;
922           defs[n_defs].dfs_num = defs[i].dfs_num;
923           VEC_quick_push (int, worklist, b);
924           top = b;
925         }
926
927       /* If this interval starts at the same point as the previous one, cancel
928          the previous one.  */
929       if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num)
930         defs[n_defs - 1].bb_index = defs[n_defs].bb_index;
931       else
932         n_defs++;
933     }
934   VEC_pop (int, worklist);
935   gcc_assert (VEC_empty (int, worklist));
936
937   /* Now process the uses.  */
938   live_phis = BITMAP_ALLOC (NULL);
939   EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi)
940     {
941       VEC_safe_push (int, heap, worklist, i);
942     }
943
944   while (!VEC_empty (int, worklist))
945     {
946       b = VEC_pop (int, worklist);
947       if (b == ENTRY_BLOCK)
948         continue;
949
950       /* If there is a phi node in USE_BB, it is made live.  Otherwise,
951          find the def that dominates the immediate dominator of USE_BB
952          (the kill in USE_BB does not dominate the use).  */
953       if (bitmap_bit_p (phis, b))
954         p = b;
955       else
956         {
957           use_bb = get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (b));
958           p = find_dfsnum_interval (defs, n_defs,
959                                     bb_dom_dfs_in (CDI_DOMINATORS, use_bb));
960           if (!bitmap_bit_p (phis, p))
961             continue;
962         }
963
964       /* If the phi node is already live, there is nothing to do.  */
965       if (bitmap_bit_p (live_phis, p))
966         continue;
967
968       /* Mark the phi as live, and add the new uses to the worklist.  */
969       bitmap_set_bit (live_phis, p);
970       def_bb = BASIC_BLOCK (p);
971       FOR_EACH_EDGE (e, ei, def_bb->preds)
972         {
973           u = e->src->index;
974           if (bitmap_bit_p (uses, u))
975             continue;
976
977           /* In case there is a kill directly in the use block, do not record
978              the use (this is also necessary for correctness, as we assume that
979              uses dominated by a def directly in their block have been filtered
980              out before).  */
981           if (bitmap_bit_p (kills, u))
982             continue;
983
984           bitmap_set_bit (uses, u);
985           VEC_safe_push (int, heap, worklist, u);
986         }
987     }
988
989   VEC_free (int, heap, worklist);
990   bitmap_copy (phis, live_phis);
991   BITMAP_FREE (live_phis);
992   free (defs);
993 }
994
995 /* Return the set of blocks where variable VAR is defined and the blocks
996    where VAR is live on entry (livein).  Return NULL, if no entry is
997    found in DEF_BLOCKS.  */
998
999 static inline struct def_blocks_d *
1000 find_def_blocks_for (tree var)
1001 {
1002   struct def_blocks_d dm;
1003   dm.var = var;
1004   return (struct def_blocks_d *) htab_find (def_blocks, &dm);
1005 }
1006
1007
1008 /* Retrieve or create a default definition for symbol SYM.  */
1009
1010 static inline tree
1011 get_default_def_for (tree sym)
1012 {
1013   tree ddef = gimple_default_def (cfun, sym);
1014
1015   if (ddef == NULL_TREE)
1016     {
1017       ddef = make_ssa_name (sym, gimple_build_nop ());
1018       set_default_def (sym, ddef);
1019     }
1020
1021   return ddef;
1022 }
1023
1024
1025 /* Marks phi node PHI in basic block BB for rewrite.  */
1026
1027 static void
1028 mark_phi_for_rewrite (basic_block bb, gimple phi)
1029 {
1030   gimple_vec phis;
1031   unsigned i, idx = bb->index;
1032
1033   if (rewrite_uses_p (phi))
1034     return;
1035
1036   set_rewrite_uses (phi, true);
1037
1038   if (!blocks_with_phis_to_rewrite)
1039     return;
1040
1041   bitmap_set_bit (blocks_with_phis_to_rewrite, idx);
1042   VEC_reserve (gimple_vec, heap, phis_to_rewrite, last_basic_block + 1);
1043   for (i = VEC_length (gimple_vec, phis_to_rewrite); i <= idx; i++)
1044     VEC_quick_push (gimple_vec, phis_to_rewrite, NULL);
1045
1046   phis = VEC_index (gimple_vec, phis_to_rewrite, idx);
1047   if (!phis)
1048     phis = VEC_alloc (gimple, heap, 10);
1049
1050   VEC_safe_push (gimple, heap, phis, phi);
1051   VEC_replace (gimple_vec, phis_to_rewrite, idx, phis);
1052 }
1053
1054
1055 /* Insert PHI nodes for variable VAR using the iterated dominance
1056    frontier given in PHI_INSERTION_POINTS.  If UPDATE_P is true, this
1057    function assumes that the caller is incrementally updating the
1058    existing SSA form, in which case VAR may be an SSA name instead of
1059    a symbol.
1060
1061    PHI_INSERTION_POINTS is updated to reflect nodes that already had a
1062    PHI node for VAR.  On exit, only the nodes that received a PHI node
1063    for VAR will be present in PHI_INSERTION_POINTS.  */
1064
1065 static void
1066 insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
1067 {
1068   unsigned bb_index;
1069   edge e;
1070   gimple phi;
1071   basic_block bb;
1072   bitmap_iterator bi;
1073   struct def_blocks_d *def_map;
1074
1075   def_map = find_def_blocks_for (var);
1076   gcc_assert (def_map);
1077
1078   /* Remove the blocks where we already have PHI nodes for VAR.  */
1079   bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
1080
1081   /* Remove obviously useless phi nodes.  */
1082   prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks,
1083                           def_map->livein_blocks);
1084
1085   /* And insert the PHI nodes.  */
1086   EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
1087     {
1088       bb = BASIC_BLOCK (bb_index);
1089       if (update_p)
1090         mark_block_for_update (bb);
1091
1092       phi = NULL;
1093
1094       if (TREE_CODE (var) == SSA_NAME)
1095         {
1096           /* If we are rewriting SSA names, create the LHS of the PHI
1097              node by duplicating VAR.  This is useful in the case of
1098              pointers, to also duplicate pointer attributes (alias
1099              information, in particular).  */
1100           edge_iterator ei;
1101           tree new_lhs;
1102
1103           gcc_assert (update_p);
1104           phi = create_phi_node (var, bb);
1105
1106           new_lhs = duplicate_ssa_name (var, phi);
1107           gimple_phi_set_result (phi, new_lhs);
1108           add_new_name_mapping (new_lhs, var);
1109
1110           /* Add VAR to every argument slot of PHI.  We need VAR in
1111              every argument so that rewrite_update_phi_arguments knows
1112              which name is this PHI node replacing.  If VAR is a
1113              symbol marked for renaming, this is not necessary, the
1114              renamer will use the symbol on the LHS to get its
1115              reaching definition.  */
1116           FOR_EACH_EDGE (e, ei, bb->preds)
1117             add_phi_arg (phi, var, e, UNKNOWN_LOCATION);
1118         }
1119       else
1120         {
1121           gcc_assert (DECL_P (var));
1122           phi = create_phi_node (var, bb);
1123         }
1124
1125       /* Mark this PHI node as interesting for update_ssa.  */
1126       set_register_defs (phi, true);
1127       mark_phi_for_rewrite (bb, phi);
1128     }
1129 }
1130
1131
1132 /* Insert PHI nodes at the dominance frontier of blocks with variable
1133    definitions.  DFS contains the dominance frontier information for
1134    the flowgraph.  */
1135
1136 static void
1137 insert_phi_nodes (bitmap *dfs)
1138 {
1139   referenced_var_iterator rvi;
1140   tree var;
1141
1142   timevar_push (TV_TREE_INSERT_PHI_NODES);
1143   
1144   FOR_EACH_REFERENCED_VAR (var, rvi)
1145     {
1146       struct def_blocks_d *def_map;
1147       bitmap idf;
1148
1149       def_map = find_def_blocks_for (var);
1150       if (def_map == NULL)
1151         continue;
1152
1153       if (get_phi_state (var) != NEED_PHI_STATE_NO)
1154         {
1155           idf = compute_idf (def_map->def_blocks, dfs);
1156           insert_phi_nodes_for (var, idf, false);
1157           BITMAP_FREE (idf);
1158         }
1159     }
1160
1161   timevar_pop (TV_TREE_INSERT_PHI_NODES);
1162 }
1163
1164
1165 /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1166    register DEF (an SSA_NAME) to be a new definition for SYM.  */
1167
1168 static void
1169 register_new_def (tree def, tree sym)
1170 {
1171   tree currdef;
1172    
1173   /* If this variable is set in a single basic block and all uses are
1174      dominated by the set(s) in that single basic block, then there is
1175      no reason to record anything for this variable in the block local
1176      definition stacks.  Doing so just wastes time and memory.
1177
1178      This is the same test to prune the set of variables which may
1179      need PHI nodes.  So we just use that information since it's already
1180      computed and available for us to use.  */
1181   if (get_phi_state (sym) == NEED_PHI_STATE_NO)
1182     {
1183       set_current_def (sym, def);
1184       return;
1185     }
1186
1187   currdef = get_current_def (sym);
1188
1189   /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1190      SSA_NAME_VAR is not necessarily SYM.  In this case, also push SYM
1191      in the stack so that we know which symbol is being defined by
1192      this SSA name when we unwind the stack.  */
1193   if (currdef && !is_gimple_reg (sym))
1194     VEC_safe_push (tree, heap, block_defs_stack, sym);
1195
1196   /* Push the current reaching definition into BLOCK_DEFS_STACK.  This
1197      stack is later used by the dominator tree callbacks to restore
1198      the reaching definitions for all the variables defined in the
1199      block after a recursive visit to all its immediately dominated
1200      blocks.  If there is no current reaching definition, then just
1201      record the underlying _DECL node.  */
1202   VEC_safe_push (tree, heap, block_defs_stack, currdef ? currdef : sym);
1203
1204   /* Set the current reaching definition for SYM to be DEF.  */
1205   set_current_def (sym, def);
1206 }
1207
1208
1209 /* Perform a depth-first traversal of the dominator tree looking for
1210    variables to rename.  BB is the block where to start searching.
1211    Renaming is a five step process:
1212
1213    1- Every definition made by PHI nodes at the start of the blocks is
1214       registered as the current definition for the corresponding variable.
1215
1216    2- Every statement in BB is rewritten.  USE and VUSE operands are
1217       rewritten with their corresponding reaching definition.  DEF and
1218       VDEF targets are registered as new definitions.
1219       
1220    3- All the PHI nodes in successor blocks of BB are visited.  The
1221       argument corresponding to BB is replaced with its current reaching
1222       definition.
1223
1224    4- Recursively rewrite every dominator child block of BB.
1225
1226    5- Restore (in reverse order) the current reaching definition for every
1227       new definition introduced in this block.  This is done so that when
1228       we return from the recursive call, all the current reaching
1229       definitions are restored to the names that were valid in the
1230       dominator parent of BB.  */
1231
1232 /* Return the current definition for variable VAR.  If none is found,
1233    create a new SSA name to act as the zeroth definition for VAR.  */
1234
1235 static tree
1236 get_reaching_def (tree var)
1237 {
1238   tree currdef;
1239   
1240   /* Lookup the current reaching definition for VAR.  */
1241   currdef = get_current_def (var);
1242
1243   /* If there is no reaching definition for VAR, create and register a
1244      default definition for it (if needed).  */
1245   if (currdef == NULL_TREE)
1246     {
1247       tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
1248       currdef = get_default_def_for (sym);
1249       set_current_def (var, currdef);
1250     }
1251
1252   /* Return the current reaching definition for VAR, or the default
1253      definition, if we had to create one.  */
1254   return currdef;
1255 }
1256
1257
1258 /* SSA Rewriting Step 2.  Rewrite every variable used in each statement in
1259    the block with its immediate reaching definitions.  Update the current
1260    definition of a variable when a new real or virtual definition is found.  */
1261
1262 static void
1263 rewrite_stmt (gimple stmt)
1264 {
1265   use_operand_p use_p;
1266   def_operand_p def_p;
1267   ssa_op_iter iter;
1268
1269   /* If mark_def_sites decided that we don't need to rewrite this
1270      statement, ignore it.  */
1271   gcc_assert (blocks_to_update == NULL);
1272   if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
1273     return;
1274
1275   if (dump_file && (dump_flags & TDF_DETAILS))
1276     {
1277       fprintf (dump_file, "Renaming statement ");
1278       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1279       fprintf (dump_file, "\n");
1280     }
1281
1282   /* Step 1.  Rewrite USES in the statement.  */
1283   if (rewrite_uses_p (stmt))
1284     FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1285       {
1286         tree var = USE_FROM_PTR (use_p);
1287         gcc_assert (DECL_P (var));
1288         SET_USE (use_p, get_reaching_def (var));
1289       }
1290
1291   /* Step 2.  Register the statement's DEF operands.  */
1292   if (register_defs_p (stmt))
1293     FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1294       {
1295         tree var = DEF_FROM_PTR (def_p);
1296         gcc_assert (DECL_P (var));
1297         SET_DEF (def_p, make_ssa_name (var, stmt));
1298         register_new_def (DEF_FROM_PTR (def_p), var);
1299       }
1300 }
1301
1302
1303 /* SSA Rewriting Step 3.  Visit all the successor blocks of BB looking for
1304    PHI nodes.  For every PHI node found, add a new argument containing the
1305    current reaching definition for the variable and the edge through which
1306    that definition is reaching the PHI node.  */
1307
1308 static void
1309 rewrite_add_phi_arguments (basic_block bb)
1310 {
1311   edge e;
1312   edge_iterator ei;
1313
1314   FOR_EACH_EDGE (e, ei, bb->succs)
1315     {
1316       gimple phi;
1317       gimple_stmt_iterator gsi;
1318
1319       for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
1320            gsi_next (&gsi))
1321         {
1322           tree currdef;
1323           gimple stmt;
1324
1325           phi = gsi_stmt (gsi);
1326           currdef = get_reaching_def (SSA_NAME_VAR (gimple_phi_result (phi)));
1327           stmt = SSA_NAME_DEF_STMT (currdef);
1328           add_phi_arg (phi, currdef, e, gimple_location (stmt));
1329         }
1330     }
1331 }
1332
1333 /* SSA Rewriting Step 1.  Initialization, create a block local stack
1334    of reaching definitions for new SSA names produced in this block
1335    (BLOCK_DEFS).  Register new definitions for every PHI node in the
1336    block.  */
1337
1338 static void
1339 rewrite_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1340                      basic_block bb)
1341 {
1342   gimple phi;
1343   gimple_stmt_iterator gsi;
1344
1345   if (dump_file && (dump_flags & TDF_DETAILS))
1346     fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
1347
1348   /* Mark the unwind point for this block.  */
1349   VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
1350
1351   /* Step 1.  Register new definitions for every PHI node in the block.
1352      Conceptually, all the PHI nodes are executed in parallel and each PHI
1353      node introduces a new version for the associated variable.  */
1354   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1355     {
1356       tree result;
1357
1358       phi = gsi_stmt (gsi);
1359       result = gimple_phi_result (phi);
1360       gcc_assert (is_gimple_reg (result));
1361       register_new_def (result, SSA_NAME_VAR (result));
1362     }
1363
1364   /* Step 2.  Rewrite every variable used in each statement in the block
1365      with its immediate reaching definitions.  Update the current definition
1366      of a variable when a new real or virtual definition is found.  */
1367   if (TEST_BIT (interesting_blocks, bb->index))
1368     for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1369       rewrite_stmt (gsi_stmt (gsi));
1370
1371   /* Step 3.  Visit all the successor blocks of BB looking for PHI nodes.
1372      For every PHI node found, add a new argument containing the current
1373      reaching definition for the variable and the edge through which that
1374      definition is reaching the PHI node.  */
1375   rewrite_add_phi_arguments (bb);
1376 }
1377
1378
1379
1380 /* Called after visiting all the statements in basic block BB and all
1381    of its dominator children.  Restore CURRDEFS to its original value.  */
1382
1383 static void
1384 rewrite_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1385                      basic_block bb ATTRIBUTE_UNUSED)
1386 {
1387   /* Restore CURRDEFS to its original state.  */
1388   while (VEC_length (tree, block_defs_stack) > 0)
1389     {
1390       tree tmp = VEC_pop (tree, block_defs_stack);
1391       tree saved_def, var;
1392
1393       if (tmp == NULL_TREE)
1394         break;
1395
1396       if (TREE_CODE (tmp) == SSA_NAME)
1397         {
1398           /* If we recorded an SSA_NAME, then make the SSA_NAME the
1399              current definition of its underlying variable.  Note that
1400              if the SSA_NAME is not for a GIMPLE register, the symbol
1401              being defined is stored in the next slot in the stack.
1402              This mechanism is needed because an SSA name for a
1403              non-register symbol may be the definition for more than
1404              one symbol (e.g., SFTs, aliased variables, etc).  */
1405           saved_def = tmp;
1406           var = SSA_NAME_VAR (saved_def);
1407           if (!is_gimple_reg (var))
1408             var = VEC_pop (tree, block_defs_stack);
1409         }
1410       else
1411         {
1412           /* If we recorded anything else, it must have been a _DECL
1413              node and its current reaching definition must have been
1414              NULL.  */
1415           saved_def = NULL;
1416           var = tmp;
1417         }
1418                                                                                 
1419       set_current_def (var, saved_def);
1420     }
1421 }
1422
1423
1424 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE.  */
1425
1426 void
1427 dump_decl_set (FILE *file, bitmap set)
1428 {
1429   if (set)
1430     {
1431       bitmap_iterator bi;
1432       unsigned i;
1433
1434       fprintf (file, "{ ");
1435
1436       EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
1437         {
1438           print_generic_expr (file, referenced_var (i), 0);
1439           fprintf (file, " ");
1440         }
1441
1442       fprintf (file, "}");
1443     }
1444   else
1445     fprintf (file, "NIL");
1446 }
1447
1448
1449 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE.  */
1450
1451 void
1452 debug_decl_set (bitmap set)
1453 {
1454   dump_decl_set (stderr, set);
1455   fprintf (stderr, "\n");
1456 }
1457
1458
1459 /* Dump the renaming stack (block_defs_stack) to FILE.  Traverse the
1460    stack up to a maximum of N levels.  If N is -1, the whole stack is
1461    dumped.  New levels are created when the dominator tree traversal
1462    used for renaming enters a new sub-tree.  */
1463
1464 void
1465 dump_defs_stack (FILE *file, int n)
1466 {
1467   int i, j;
1468
1469   fprintf (file, "\n\nRenaming stack");
1470   if (n > 0)
1471     fprintf (file, " (up to %d levels)", n);
1472   fprintf (file, "\n\n");
1473
1474   i = 1;
1475   fprintf (file, "Level %d (current level)\n", i);
1476   for (j = (int) VEC_length (tree, block_defs_stack) - 1; j >= 0; j--)
1477     {
1478       tree name, var;
1479       
1480       name = VEC_index (tree, block_defs_stack, j);
1481       if (name == NULL_TREE)
1482         {
1483           i++;
1484           if (n > 0 && i > n)
1485             break;
1486           fprintf (file, "\nLevel %d\n", i);
1487           continue;
1488         }
1489
1490       if (DECL_P (name))
1491         {
1492           var = name;
1493           name = NULL_TREE;
1494         }
1495       else
1496         {
1497           var = SSA_NAME_VAR (name);
1498           if (!is_gimple_reg (var))
1499             {
1500               j--;
1501               var = VEC_index (tree, block_defs_stack, j);
1502             }
1503         }
1504
1505       fprintf (file, "    Previous CURRDEF (");
1506       print_generic_expr (file, var, 0);
1507       fprintf (file, ") = ");
1508       if (name)
1509         print_generic_expr (file, name, 0);
1510       else
1511         fprintf (file, "<NIL>");
1512       fprintf (file, "\n");
1513     }
1514 }
1515
1516
1517 /* Dump the renaming stack (block_defs_stack) to stderr.  Traverse the
1518    stack up to a maximum of N levels.  If N is -1, the whole stack is
1519    dumped.  New levels are created when the dominator tree traversal
1520    used for renaming enters a new sub-tree.  */
1521
1522 void
1523 debug_defs_stack (int n)
1524 {
1525   dump_defs_stack (stderr, n);
1526 }
1527
1528
1529 /* Dump the current reaching definition of every symbol to FILE.  */
1530
1531 void
1532 dump_currdefs (FILE *file)
1533 {
1534   referenced_var_iterator i;
1535   tree var;
1536
1537   fprintf (file, "\n\nCurrent reaching definitions\n\n");
1538   FOR_EACH_REFERENCED_VAR (var, i)
1539     if (SYMS_TO_RENAME (cfun) == NULL
1540         || bitmap_bit_p (SYMS_TO_RENAME (cfun), DECL_UID (var)))
1541       {
1542         fprintf (file, "CURRDEF (");
1543         print_generic_expr (file, var, 0);
1544         fprintf (file, ") = ");
1545         if (get_current_def (var))
1546           print_generic_expr (file, get_current_def (var), 0);
1547         else
1548           fprintf (file, "<NIL>");
1549         fprintf (file, "\n");
1550       }
1551 }
1552
1553
1554 /* Dump the current reaching definition of every symbol to stderr.  */
1555
1556 void
1557 debug_currdefs (void)
1558 {
1559   dump_currdefs (stderr);
1560 }
1561
1562
1563 /* Dump SSA information to FILE.  */
1564
1565 void
1566 dump_tree_ssa (FILE *file)
1567 {
1568   const char *funcname
1569     = lang_hooks.decl_printable_name (current_function_decl, 2);
1570
1571   fprintf (file, "SSA renaming information for %s\n\n", funcname);
1572
1573   dump_def_blocks (file);
1574   dump_defs_stack (file, -1);
1575   dump_currdefs (file);
1576   dump_tree_ssa_stats (file);
1577 }
1578
1579
1580 /* Dump SSA information to stderr.  */
1581
1582 void
1583 debug_tree_ssa (void)
1584 {
1585   dump_tree_ssa (stderr);
1586 }
1587
1588
1589 /* Dump statistics for the hash table HTAB.  */
1590
1591 static void
1592 htab_statistics (FILE *file, htab_t htab)
1593 {
1594   fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1595            (long) htab_size (htab),
1596            (long) htab_elements (htab),
1597            htab_collisions (htab));
1598 }
1599
1600
1601 /* Dump SSA statistics on FILE.  */
1602
1603 void
1604 dump_tree_ssa_stats (FILE *file)
1605 {
1606   if (def_blocks || repl_tbl)
1607     fprintf (file, "\nHash table statistics:\n");
1608
1609   if (def_blocks)
1610     {
1611       fprintf (file, "    def_blocks:   ");
1612       htab_statistics (file, def_blocks);
1613     }
1614
1615   if (repl_tbl)
1616     {
1617       fprintf (file, "    repl_tbl:     ");
1618       htab_statistics (file, repl_tbl);
1619     }
1620
1621   if (def_blocks || repl_tbl)
1622     fprintf (file, "\n");
1623 }
1624
1625
1626 /* Dump SSA statistics on stderr.  */
1627
1628 void
1629 debug_tree_ssa_stats (void)
1630 {
1631   dump_tree_ssa_stats (stderr);
1632 }
1633
1634
1635 /* Hashing and equality functions for DEF_BLOCKS.  */
1636
1637 static hashval_t
1638 def_blocks_hash (const void *p)
1639 {
1640   return htab_hash_pointer
1641         ((const void *)((const struct def_blocks_d *)p)->var);
1642 }
1643
1644 static int
1645 def_blocks_eq (const void *p1, const void *p2)
1646 {
1647   return ((const struct def_blocks_d *)p1)->var
1648          == ((const struct def_blocks_d *)p2)->var;
1649 }
1650
1651
1652 /* Free memory allocated by one entry in DEF_BLOCKS.  */
1653
1654 static void
1655 def_blocks_free (void *p)
1656 {
1657   struct def_blocks_d *entry = (struct def_blocks_d *) p;
1658   BITMAP_FREE (entry->def_blocks);
1659   BITMAP_FREE (entry->phi_blocks);
1660   BITMAP_FREE (entry->livein_blocks);
1661   free (entry);
1662 }
1663
1664
1665 /* Callback for htab_traverse to dump the DEF_BLOCKS hash table.  */
1666
1667 static int
1668 debug_def_blocks_r (void **slot, void *data)
1669 {
1670   FILE *file = (FILE *) data;
1671   struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
1672   
1673   fprintf (file, "VAR: ");
1674   print_generic_expr (file, db_p->var, dump_flags);
1675   bitmap_print (file, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
1676   bitmap_print (file, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}");
1677   bitmap_print (file, db_p->phi_blocks, ", PHI_BLOCKS: { ", "}\n");
1678
1679   return 1;
1680 }
1681
1682
1683 /* Dump the DEF_BLOCKS hash table on FILE.  */
1684
1685 void
1686 dump_def_blocks (FILE *file)
1687 {
1688   fprintf (file, "\n\nDefinition and live-in blocks:\n\n");
1689   if (def_blocks)
1690     htab_traverse (def_blocks, debug_def_blocks_r, file);
1691 }
1692
1693
1694 /* Dump the DEF_BLOCKS hash table on stderr.  */
1695
1696 void
1697 debug_def_blocks (void)
1698 {
1699   dump_def_blocks (stderr);
1700 }
1701
1702
1703 /* Register NEW_NAME to be the new reaching definition for OLD_NAME.  */
1704
1705 static inline void
1706 register_new_update_single (tree new_name, tree old_name)
1707 {
1708   tree currdef = get_current_def (old_name);
1709
1710   /* Push the current reaching definition into BLOCK_DEFS_STACK.
1711      This stack is later used by the dominator tree callbacks to
1712      restore the reaching definitions for all the variables
1713      defined in the block after a recursive visit to all its
1714      immediately dominated blocks.  */
1715   VEC_reserve (tree, heap, block_defs_stack, 2);
1716   VEC_quick_push (tree, block_defs_stack, currdef);
1717   VEC_quick_push (tree, block_defs_stack, old_name);
1718
1719   /* Set the current reaching definition for OLD_NAME to be
1720      NEW_NAME.  */
1721   set_current_def (old_name, new_name);
1722 }
1723
1724
1725 /* Register NEW_NAME to be the new reaching definition for all the
1726    names in OLD_NAMES.  Used by the incremental SSA update routines to
1727    replace old SSA names with new ones.  */
1728
1729 static inline void
1730 register_new_update_set (tree new_name, bitmap old_names)
1731 {
1732   bitmap_iterator bi;
1733   unsigned i;
1734
1735   EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
1736     register_new_update_single (new_name, ssa_name (i));
1737 }
1738
1739
1740
1741 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1742    it is a symbol marked for renaming, replace it with USE_P's current
1743    reaching definition.  */
1744
1745 static inline void
1746 maybe_replace_use (use_operand_p use_p)
1747 {
1748   tree rdef = NULL_TREE;
1749   tree use = USE_FROM_PTR (use_p);
1750   tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1751
1752   if (symbol_marked_for_renaming (sym))
1753     rdef = get_reaching_def (sym);
1754   else if (is_old_name (use))
1755     rdef = get_reaching_def (use);
1756
1757   if (rdef && rdef != use)
1758     SET_USE (use_p, rdef);
1759 }
1760
1761
1762 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1763    or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1764    register it as the current definition for the names replaced by
1765    DEF_P.  */
1766
1767 static inline void
1768 maybe_register_def (def_operand_p def_p, gimple stmt)
1769 {
1770   tree def = DEF_FROM_PTR (def_p);
1771   tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1772
1773   /* If DEF is a naked symbol that needs renaming, create a new
1774      name for it.  */
1775   if (symbol_marked_for_renaming (sym))
1776     {
1777       if (DECL_P (def))
1778         {
1779           def = make_ssa_name (def, stmt);
1780           SET_DEF (def_p, def);
1781         }
1782
1783       register_new_update_single (def, sym);
1784     }
1785   else
1786     {
1787       /* If DEF is a new name, register it as a new definition
1788          for all the names replaced by DEF.  */
1789       if (is_new_name (def))
1790         register_new_update_set (def, names_replaced_by (def));
1791
1792       /* If DEF is an old name, register DEF as a new
1793          definition for itself.  */
1794       if (is_old_name (def))
1795         register_new_update_single (def, def);
1796     }
1797 }
1798
1799
1800 /* Update every variable used in the statement pointed-to by SI.  The
1801    statement is assumed to be in SSA form already.  Names in
1802    OLD_SSA_NAMES used by SI will be updated to their current reaching
1803    definition.  Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1804    will be registered as a new definition for their corresponding name
1805    in OLD_SSA_NAMES.  */
1806
1807 static void
1808 rewrite_update_stmt (gimple stmt)
1809 {
1810   use_operand_p use_p;
1811   def_operand_p def_p;
1812   ssa_op_iter iter;
1813
1814   /* Only update marked statements.  */
1815   if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
1816     return;
1817
1818   if (dump_file && (dump_flags & TDF_DETAILS))
1819     {
1820       fprintf (dump_file, "Updating SSA information for statement ");
1821       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1822       fprintf (dump_file, "\n");
1823     }
1824
1825   /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
1826      symbol is marked for renaming.  */
1827   if (rewrite_uses_p (stmt))
1828     FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1829       maybe_replace_use (use_p);
1830
1831   /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
1832      Also register definitions for names whose underlying symbol is
1833      marked for renaming.  */
1834   if (register_defs_p (stmt))
1835     FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1836       maybe_register_def (def_p, stmt);
1837 }
1838
1839
1840 /* Visit all the successor blocks of BB looking for PHI nodes.  For
1841    every PHI node found, check if any of its arguments is in
1842    OLD_SSA_NAMES.  If so, and if the argument has a current reaching
1843    definition, replace it.  */
1844
1845 static void
1846 rewrite_update_phi_arguments (basic_block bb)
1847 {
1848   edge e;
1849   edge_iterator ei;
1850   unsigned i;
1851
1852   FOR_EACH_EDGE (e, ei, bb->succs)
1853     {
1854       gimple phi;
1855       gimple_vec phis;
1856
1857       if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
1858         continue;
1859      
1860       phis = VEC_index (gimple_vec, phis_to_rewrite, e->dest->index);
1861       for (i = 0; VEC_iterate (gimple, phis, i, phi); i++)
1862         {
1863           tree arg, lhs_sym, reaching_def = NULL;
1864           use_operand_p arg_p;
1865
1866           gcc_assert (rewrite_uses_p (phi));
1867
1868           arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
1869           arg = USE_FROM_PTR (arg_p);
1870
1871           if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
1872             continue;
1873
1874           lhs_sym = SSA_NAME_VAR (gimple_phi_result (phi));
1875
1876           if (arg == NULL_TREE)
1877             {
1878               /* When updating a PHI node for a recently introduced
1879                  symbol we may find NULL arguments.  That's why we
1880                  take the symbol from the LHS of the PHI node.  */
1881               reaching_def = get_reaching_def (lhs_sym);
1882
1883             }
1884           else
1885             {
1886               tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
1887
1888               if (symbol_marked_for_renaming (sym))
1889                 reaching_def = get_reaching_def (sym);
1890               else if (is_old_name (arg))
1891                 reaching_def = get_reaching_def (arg);
1892             }
1893
1894           /* Update the argument if there is a reaching def.  */
1895           if (reaching_def)
1896             {
1897               gimple stmt;
1898               source_location locus;
1899               int arg_i = PHI_ARG_INDEX_FROM_USE (arg_p);
1900
1901               SET_USE (arg_p, reaching_def);
1902               stmt = SSA_NAME_DEF_STMT (reaching_def);
1903
1904               /* Single element PHI nodes  behave like copies, so get the 
1905                  location from the phi argument.  */
1906               if (gimple_code (stmt) == GIMPLE_PHI && 
1907                   gimple_phi_num_args (stmt) == 1)
1908                 locus = gimple_phi_arg_location (stmt, 0);
1909               else
1910                 locus = gimple_location (stmt);
1911
1912               gimple_phi_arg_set_location (phi, arg_i, locus);
1913             }
1914
1915
1916           if (e->flags & EDGE_ABNORMAL)
1917             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
1918         }
1919     }
1920 }
1921
1922
1923 /* Initialization of block data structures for the incremental SSA
1924    update pass.  Create a block local stack of reaching definitions
1925    for new SSA names produced in this block (BLOCK_DEFS).  Register
1926    new definitions for every PHI node in the block.  */
1927
1928 static void
1929 rewrite_update_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1930                             basic_block bb)
1931 {
1932   edge e;
1933   edge_iterator ei;
1934   bool is_abnormal_phi;
1935   gimple_stmt_iterator gsi;
1936
1937   if (dump_file && (dump_flags & TDF_DETAILS))
1938     fprintf (dump_file, "\n\nRegistering new PHI nodes in block #%d\n\n",
1939              bb->index);
1940
1941   /* Mark the unwind point for this block.  */
1942   VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
1943
1944   if (!bitmap_bit_p (blocks_to_update, bb->index))
1945     return;
1946
1947   /* Mark the LHS if any of the arguments flows through an abnormal
1948      edge.  */
1949   is_abnormal_phi = false;
1950   FOR_EACH_EDGE (e, ei, bb->preds)
1951     if (e->flags & EDGE_ABNORMAL)
1952       {
1953         is_abnormal_phi = true;
1954         break;
1955       }
1956
1957   /* If any of the PHI nodes is a replacement for a name in
1958      OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
1959      register it as a new definition for its corresponding name.  Also
1960      register definitions for names whose underlying symbols are
1961      marked for renaming.  */
1962   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1963     {
1964       tree lhs, lhs_sym;
1965       gimple phi = gsi_stmt (gsi);
1966
1967       if (!register_defs_p (phi))
1968         continue;
1969       
1970       lhs = gimple_phi_result (phi);
1971       lhs_sym = SSA_NAME_VAR (lhs);
1972
1973       if (symbol_marked_for_renaming (lhs_sym))
1974         register_new_update_single (lhs, lhs_sym);
1975       else
1976         {
1977
1978           /* If LHS is a new name, register a new definition for all
1979              the names replaced by LHS.  */
1980           if (is_new_name (lhs))
1981             register_new_update_set (lhs, names_replaced_by (lhs));
1982           
1983           /* If LHS is an OLD name, register it as a new definition
1984              for itself.  */
1985           if (is_old_name (lhs))
1986             register_new_update_single (lhs, lhs);
1987         }
1988
1989       if (is_abnormal_phi)
1990         SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
1991     }
1992
1993   /* Step 2.  Rewrite every variable used in each statement in the block.  */
1994   if (TEST_BIT (interesting_blocks, bb->index))
1995    {
1996      gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
1997       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1998         rewrite_update_stmt (gsi_stmt (gsi));
1999    }
2000
2001   /* Step 3.  Update PHI nodes.  */
2002   rewrite_update_phi_arguments (bb);
2003 }
2004
2005 /* Called after visiting block BB.  Unwind BLOCK_DEFS_STACK to restore
2006    the current reaching definition of every name re-written in BB to
2007    the original reaching definition before visiting BB.  This
2008    unwinding must be done in the opposite order to what is done in
2009    register_new_update_set.  */
2010
2011 static void
2012 rewrite_update_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
2013                             basic_block bb ATTRIBUTE_UNUSED)
2014 {
2015   while (VEC_length (tree, block_defs_stack) > 0)
2016     {
2017       tree var = VEC_pop (tree, block_defs_stack);
2018       tree saved_def;
2019       
2020       /* NULL indicates the unwind stop point for this block (see
2021          rewrite_update_enter_block).  */
2022       if (var == NULL)
2023         return;
2024
2025       saved_def = VEC_pop (tree, block_defs_stack);
2026       set_current_def (var, saved_def);
2027     }
2028 }
2029
2030
2031 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2032    form.  
2033
2034    ENTRY indicates the block where to start.  Every block dominated by
2035       ENTRY will be rewritten.
2036
2037    WHAT indicates what actions will be taken by the renamer (see enum
2038       rewrite_mode).
2039
2040    BLOCKS are the set of interesting blocks for the dominator walker
2041       to process.  If this set is NULL, then all the nodes dominated
2042       by ENTRY are walked.  Otherwise, blocks dominated by ENTRY that
2043       are not present in BLOCKS are ignored.  */
2044
2045 static void
2046 rewrite_blocks (basic_block entry, enum rewrite_mode what)
2047 {
2048   struct dom_walk_data walk_data;
2049   
2050   /* Rewrite all the basic blocks in the program.  */
2051   timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
2052
2053   /* Setup callbacks for the generic dominator tree walker.  */
2054   memset (&walk_data, 0, sizeof (walk_data));
2055
2056   walk_data.dom_direction = CDI_DOMINATORS;
2057
2058   if (what == REWRITE_ALL)
2059     {
2060       walk_data.before_dom_children = rewrite_enter_block;
2061       walk_data.after_dom_children = rewrite_leave_block;
2062     }
2063   else if (what == REWRITE_UPDATE)
2064     {
2065       walk_data.before_dom_children = rewrite_update_enter_block;
2066       walk_data.after_dom_children = rewrite_update_leave_block;
2067     }
2068   else
2069     gcc_unreachable ();
2070
2071   block_defs_stack = VEC_alloc (tree, heap, 10);
2072
2073   /* Initialize the dominator walker.  */
2074   init_walk_dominator_tree (&walk_data);
2075
2076   /* Recursively walk the dominator tree rewriting each statement in
2077      each basic block.  */
2078   walk_dominator_tree (&walk_data, entry);
2079
2080   /* Finalize the dominator walker.  */
2081   fini_walk_dominator_tree (&walk_data);
2082
2083   /* Debugging dumps.  */
2084   if (dump_file && (dump_flags & TDF_STATS))
2085     {
2086       dump_dfa_stats (dump_file);
2087       if (def_blocks)
2088         dump_tree_ssa_stats (dump_file);
2089     }
2090   
2091   VEC_free (tree, heap, block_defs_stack);
2092
2093   timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
2094 }
2095
2096
2097 /* Block processing routine for mark_def_sites.  Clear the KILLS bitmap
2098    at the start of each block, and call mark_def_sites for each statement.  */
2099
2100 static void
2101 mark_def_sites_block (struct dom_walk_data *walk_data, basic_block bb)
2102 {
2103   struct mark_def_sites_global_data *gd;
2104   bitmap kills;
2105   gimple_stmt_iterator gsi;
2106
2107   gd = (struct mark_def_sites_global_data *) walk_data->global_data;
2108   kills = gd->kills;
2109
2110   bitmap_clear (kills);
2111   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2112     mark_def_sites (bb, gsi_stmt (gsi), kills);
2113 }
2114
2115
2116 /* Mark the definition site blocks for each variable, so that we know
2117    where the variable is actually live.
2118
2119    The INTERESTING_BLOCKS global will be filled in with all the blocks
2120    that should be processed by the renamer.  It is assumed that the
2121    caller has already initialized and zeroed it.  */
2122
2123 static void
2124 mark_def_site_blocks (void)
2125 {
2126   struct dom_walk_data walk_data;
2127   struct mark_def_sites_global_data mark_def_sites_global_data;
2128
2129   /* Setup callbacks for the generic dominator tree walker to find and
2130      mark definition sites.  */
2131   walk_data.dom_direction = CDI_DOMINATORS;
2132   walk_data.initialize_block_local_data = NULL;
2133   walk_data.before_dom_children = mark_def_sites_block;
2134   walk_data.after_dom_children = NULL;
2135
2136   /* Notice that this bitmap is indexed using variable UIDs, so it must be
2137      large enough to accommodate all the variables referenced in the
2138      function, not just the ones we are renaming.  */
2139   mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
2140   walk_data.global_data = &mark_def_sites_global_data;
2141
2142   /* We do not have any local data.  */
2143   walk_data.block_local_data_size = 0;
2144
2145   /* Initialize the dominator walker.  */
2146   init_walk_dominator_tree (&walk_data);
2147
2148   /* Recursively walk the dominator tree.  */
2149   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
2150
2151   /* Finalize the dominator walker.  */
2152   fini_walk_dominator_tree (&walk_data);
2153
2154   /* We no longer need this bitmap, clear and free it.  */
2155   BITMAP_FREE (mark_def_sites_global_data.kills);
2156 }
2157
2158
2159 /* Initialize internal data needed during renaming.  */
2160
2161 static void
2162 init_ssa_renamer (void)
2163 {
2164   tree var;
2165   referenced_var_iterator rvi;
2166
2167   cfun->gimple_df->in_ssa_p = false;
2168
2169   /* Allocate memory for the DEF_BLOCKS hash table.  */
2170   gcc_assert (def_blocks == NULL);
2171   def_blocks = htab_create (num_referenced_vars, def_blocks_hash,
2172                             def_blocks_eq, def_blocks_free);
2173
2174   FOR_EACH_REFERENCED_VAR(var, rvi)
2175     set_current_def (var, NULL_TREE);
2176 }
2177
2178
2179 /* Deallocate internal data structures used by the renamer.  */
2180
2181 static void
2182 fini_ssa_renamer (void)
2183 {
2184   if (def_blocks)
2185     {
2186       htab_delete (def_blocks);
2187       def_blocks = NULL;
2188     }
2189
2190   cfun->gimple_df->in_ssa_p = true;
2191 }
2192
2193 /* Main entry point into the SSA builder.  The renaming process
2194    proceeds in four main phases:
2195
2196    1- Compute dominance frontier and immediate dominators, needed to
2197       insert PHI nodes and rename the function in dominator tree
2198       order.
2199
2200    2- Find and mark all the blocks that define variables
2201       (mark_def_site_blocks).
2202
2203    3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2204
2205    4- Rename all the blocks (rewrite_blocks) and statements in the program.
2206
2207    Steps 3 and 4 are done using the dominator tree walker
2208    (walk_dominator_tree).  */
2209
2210 static unsigned int
2211 rewrite_into_ssa (void)
2212 {
2213   bitmap *dfs;
2214   basic_block bb;
2215   
2216   timevar_push (TV_TREE_SSA_OTHER);
2217
2218   /* Initialize operand data structures.  */
2219   init_ssa_operands ();
2220
2221   /* Initialize internal data needed by the renamer.  */
2222   init_ssa_renamer ();
2223
2224   /* Initialize the set of interesting blocks.  The callback
2225      mark_def_sites will add to this set those blocks that the renamer
2226      should process.  */
2227   interesting_blocks = sbitmap_alloc (last_basic_block);
2228   sbitmap_zero (interesting_blocks);
2229
2230   /* Initialize dominance frontier.  */
2231   dfs = XNEWVEC (bitmap, last_basic_block);
2232   FOR_EACH_BB (bb)
2233     dfs[bb->index] = BITMAP_ALLOC (NULL);
2234
2235   /* 1- Compute dominance frontiers.  */
2236   calculate_dominance_info (CDI_DOMINATORS);
2237   compute_dominance_frontiers (dfs);
2238
2239   /* 2- Find and mark definition sites.  */
2240   mark_def_site_blocks ();
2241
2242   /* 3- Insert PHI nodes at dominance frontiers of definition blocks.  */
2243   insert_phi_nodes (dfs);
2244
2245   /* 4- Rename all the blocks.  */
2246   rewrite_blocks (ENTRY_BLOCK_PTR, REWRITE_ALL);
2247
2248   /* Free allocated memory.  */
2249   FOR_EACH_BB (bb)
2250     BITMAP_FREE (dfs[bb->index]);
2251   free (dfs);
2252
2253   fini_ssa_renamer ();
2254
2255   timevar_pop (TV_TREE_SSA_OTHER);
2256   return 0;
2257 }
2258
2259
2260 struct gimple_opt_pass pass_build_ssa = 
2261 {
2262  {
2263   GIMPLE_PASS,
2264   "ssa",                                /* name */
2265   NULL,                                 /* gate */
2266   rewrite_into_ssa,                     /* execute */
2267   NULL,                                 /* sub */
2268   NULL,                                 /* next */
2269   0,                                    /* static_pass_number */
2270   TV_NONE,                              /* tv_id */
2271   PROP_cfg | PROP_referenced_vars,      /* properties_required */
2272   PROP_ssa,                             /* properties_provided */
2273   0,                                    /* properties_destroyed */
2274   0,                                    /* todo_flags_start */
2275   TODO_dump_func
2276     | TODO_update_ssa_only_virtuals
2277     | TODO_verify_ssa
2278     | TODO_remove_unused_locals         /* todo_flags_finish */
2279  }
2280 };
2281
2282
2283 /* Mark the definition of VAR at STMT and BB as interesting for the
2284    renamer.  BLOCKS is the set of blocks that need updating.  */
2285
2286 static void
2287 mark_def_interesting (tree var, gimple stmt, basic_block bb, bool insert_phi_p)
2288 {
2289   gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
2290   set_register_defs (stmt, true);
2291
2292   if (insert_phi_p)
2293     {
2294       bool is_phi_p = gimple_code (stmt) == GIMPLE_PHI;
2295
2296       set_def_block (var, bb, is_phi_p);
2297
2298       /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2299          site for both itself and all the old names replaced by it.  */
2300       if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
2301         {
2302           bitmap_iterator bi;
2303           unsigned i;
2304           bitmap set = names_replaced_by (var);
2305           if (set)
2306             EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2307               set_def_block (ssa_name (i), bb, is_phi_p);
2308         }
2309     }
2310 }
2311
2312
2313 /* Mark the use of VAR at STMT and BB as interesting for the
2314    renamer.  INSERT_PHI_P is true if we are going to insert new PHI
2315    nodes.  */
2316
2317 static inline void
2318 mark_use_interesting (tree var, gimple stmt, basic_block bb, bool insert_phi_p)
2319 {
2320   basic_block def_bb = gimple_bb (stmt);
2321
2322   mark_block_for_update (def_bb);
2323   mark_block_for_update (bb);
2324
2325   if (gimple_code (stmt) == GIMPLE_PHI)
2326     mark_phi_for_rewrite (def_bb, stmt);
2327   else
2328     set_rewrite_uses (stmt, true);
2329
2330   /* If VAR has not been defined in BB, then it is live-on-entry
2331      to BB.  Note that we cannot just use the block holding VAR's
2332      definition because if VAR is one of the names in OLD_SSA_NAMES,
2333      it will have several definitions (itself and all the names that
2334      replace it).  */
2335   if (insert_phi_p)
2336     {
2337       struct def_blocks_d *db_p = get_def_blocks_for (var);
2338       if (!bitmap_bit_p (db_p->def_blocks, bb->index))
2339         set_livein_block (var, bb);
2340     }
2341 }
2342
2343
2344 /* Do a dominator walk starting at BB processing statements that
2345    reference symbols in SYMS_TO_RENAME.  This is very similar to
2346    mark_def_sites, but the scan handles statements whose operands may
2347    already be SSA names.
2348
2349    If INSERT_PHI_P is true, mark those uses as live in the
2350    corresponding block.  This is later used by the PHI placement
2351    algorithm to make PHI pruning decisions.
2352
2353    FIXME.  Most of this would be unnecessary if we could associate a
2354            symbol to all the SSA names that reference it.  But that
2355            sounds like it would be expensive to maintain.  Still, it
2356            would be interesting to see if it makes better sense to do
2357            that.  */
2358
2359 static void
2360 prepare_block_for_update (basic_block bb, bool insert_phi_p)
2361 {
2362   basic_block son;
2363   gimple_stmt_iterator si;
2364   edge e;
2365   edge_iterator ei;
2366
2367   mark_block_for_update (bb);
2368
2369   /* Process PHI nodes marking interesting those that define or use
2370      the symbols that we are interested in.  */
2371   for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
2372     {
2373       gimple phi = gsi_stmt (si);
2374       tree lhs_sym, lhs = gimple_phi_result (phi);
2375
2376       lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
2377
2378       if (!symbol_marked_for_renaming (lhs_sym))
2379         continue;
2380
2381       mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
2382
2383       /* Mark the uses in phi nodes as interesting.  It would be more correct
2384          to process the arguments of the phi nodes of the successor edges of
2385          BB at the end of prepare_block_for_update, however, that turns out
2386          to be significantly more expensive.  Doing it here is conservatively
2387          correct -- it may only cause us to believe a value to be live in a
2388          block that also contains its definition, and thus insert a few more
2389          phi nodes for it.  */
2390       FOR_EACH_EDGE (e, ei, bb->preds)
2391         mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
2392     }
2393
2394   /* Process the statements.  */
2395   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
2396     {
2397       gimple stmt;
2398       ssa_op_iter i;
2399       use_operand_p use_p;
2400       def_operand_p def_p;
2401       
2402       stmt = gsi_stmt (si);
2403
2404       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_ALL_USES)
2405         {
2406           tree use = USE_FROM_PTR (use_p);
2407           tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
2408           if (symbol_marked_for_renaming (sym))
2409             mark_use_interesting (sym, stmt, bb, insert_phi_p);
2410         }
2411
2412       FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_ALL_DEFS)
2413         {
2414           tree def = DEF_FROM_PTR (def_p);
2415           tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
2416           if (symbol_marked_for_renaming (sym))
2417             mark_def_interesting (sym, stmt, bb, insert_phi_p);
2418         }
2419     }
2420
2421   /* Now visit all the blocks dominated by BB.  */
2422   for (son = first_dom_son (CDI_DOMINATORS, bb);
2423        son;
2424        son = next_dom_son (CDI_DOMINATORS, son))
2425     prepare_block_for_update (son, insert_phi_p);
2426 }
2427
2428
2429 /* Helper for prepare_names_to_update.  Mark all the use sites for
2430    NAME as interesting.  BLOCKS and INSERT_PHI_P are as in
2431    prepare_names_to_update.  */
2432
2433 static void
2434 prepare_use_sites_for (tree name, bool insert_phi_p)
2435 {
2436   use_operand_p use_p;
2437   imm_use_iterator iter;
2438
2439   FOR_EACH_IMM_USE_FAST (use_p, iter, name)
2440     {
2441       gimple stmt = USE_STMT (use_p);
2442       basic_block bb = gimple_bb (stmt);
2443
2444       if (gimple_code (stmt) == GIMPLE_PHI)
2445         {
2446           int ix = PHI_ARG_INDEX_FROM_USE (use_p);
2447           edge e = gimple_phi_arg_edge (stmt, ix);
2448           mark_use_interesting (name, stmt, e->src, insert_phi_p);
2449         }
2450       else
2451         {
2452           /* For regular statements, mark this as an interesting use
2453              for NAME.  */
2454           mark_use_interesting (name, stmt, bb, insert_phi_p);
2455         }
2456     }
2457 }
2458
2459
2460 /* Helper for prepare_names_to_update.  Mark the definition site for
2461    NAME as interesting.  BLOCKS and INSERT_PHI_P are as in
2462    prepare_names_to_update.  */
2463
2464 static void
2465 prepare_def_site_for (tree name, bool insert_phi_p)
2466 {
2467   gimple stmt;
2468   basic_block bb;
2469
2470   gcc_assert (names_to_release == NULL
2471               || !bitmap_bit_p (names_to_release, SSA_NAME_VERSION (name)));
2472
2473   stmt = SSA_NAME_DEF_STMT (name);
2474   bb = gimple_bb (stmt);
2475   if (bb)
2476     {
2477       gcc_assert (bb->index < last_basic_block);
2478       mark_block_for_update (bb);
2479       mark_def_interesting (name, stmt, bb, insert_phi_p);
2480     }
2481 }
2482
2483
2484 /* Mark definition and use sites of names in NEW_SSA_NAMES and
2485    OLD_SSA_NAMES.  INSERT_PHI_P is true if the caller wants to insert
2486    PHI nodes for newly created names.  */
2487
2488 static void
2489 prepare_names_to_update (bool insert_phi_p)
2490 {
2491   unsigned i = 0;
2492   bitmap_iterator bi;
2493   sbitmap_iterator sbi;
2494
2495   /* If a name N from NEW_SSA_NAMES is also marked to be released,
2496      remove it from NEW_SSA_NAMES so that we don't try to visit its
2497      defining basic block (which most likely doesn't exist).  Notice
2498      that we cannot do the same with names in OLD_SSA_NAMES because we
2499      want to replace existing instances.  */
2500   if (names_to_release)
2501     EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2502       RESET_BIT (new_ssa_names, i);
2503
2504   /* First process names in NEW_SSA_NAMES.  Otherwise, uses of old
2505      names may be considered to be live-in on blocks that contain
2506      definitions for their replacements.  */
2507   EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
2508     prepare_def_site_for (ssa_name (i), insert_phi_p);
2509
2510   /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2511      OLD_SSA_NAMES, but we have to ignore its definition site.  */
2512   EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
2513     {
2514       if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
2515         prepare_def_site_for (ssa_name (i), insert_phi_p);
2516       prepare_use_sites_for (ssa_name (i), insert_phi_p);
2517     }
2518 }
2519
2520
2521 /* Dump all the names replaced by NAME to FILE.  */
2522
2523 void
2524 dump_names_replaced_by (FILE *file, tree name)
2525 {
2526   unsigned i;
2527   bitmap old_set;
2528   bitmap_iterator bi;
2529
2530   print_generic_expr (file, name, 0);
2531   fprintf (file, " -> { ");
2532
2533   old_set = names_replaced_by (name);
2534   EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
2535     {
2536       print_generic_expr (file, ssa_name (i), 0);
2537       fprintf (file, " ");
2538     }
2539
2540   fprintf (file, "}\n");
2541 }
2542
2543
2544 /* Dump all the names replaced by NAME to stderr.  */
2545
2546 void
2547 debug_names_replaced_by (tree name)
2548 {
2549   dump_names_replaced_by (stderr, name);
2550 }
2551
2552
2553 /* Dump SSA update information to FILE.  */
2554
2555 void
2556 dump_update_ssa (FILE *file)
2557 {
2558   unsigned i = 0;
2559   bitmap_iterator bi;
2560
2561   if (!need_ssa_update_p (cfun))
2562     return;
2563
2564   if (new_ssa_names && sbitmap_first_set_bit (new_ssa_names) >= 0)
2565     {
2566       sbitmap_iterator sbi;
2567
2568       fprintf (file, "\nSSA replacement table\n");
2569       fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
2570                      "O_1, ..., O_j\n\n");
2571
2572       EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
2573         dump_names_replaced_by (file, ssa_name (i));
2574
2575       fprintf (file, "\n");
2576       fprintf (file, "Number of virtual NEW -> OLD mappings: %7u\n",
2577                update_ssa_stats.num_virtual_mappings);
2578       fprintf (file, "Number of real NEW -> OLD mappings:    %7u\n",
2579                update_ssa_stats.num_total_mappings
2580                - update_ssa_stats.num_virtual_mappings);
2581       fprintf (file, "Number of total NEW -> OLD mappings:   %7u\n",
2582                update_ssa_stats.num_total_mappings);
2583
2584       fprintf (file, "\nNumber of virtual symbols: %u\n",
2585                update_ssa_stats.num_virtual_symbols);
2586     }
2587
2588   if (!bitmap_empty_p (SYMS_TO_RENAME (cfun)))
2589     {
2590       fprintf (file, "\n\nSymbols to be put in SSA form\n\n");
2591       dump_decl_set (file, SYMS_TO_RENAME (cfun));
2592       fprintf (file, "\n");
2593     }
2594
2595   if (names_to_release && !bitmap_empty_p (names_to_release))
2596     {
2597       fprintf (file, "\n\nSSA names to release after updating the SSA web\n\n");
2598       EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2599         {
2600           print_generic_expr (file, ssa_name (i), 0);
2601           fprintf (file, " ");
2602         }
2603     }
2604
2605   fprintf (file, "\n\n");
2606 }
2607
2608
2609 /* Dump SSA update information to stderr.  */
2610
2611 void
2612 debug_update_ssa (void)
2613 {
2614   dump_update_ssa (stderr);
2615 }
2616
2617
2618 /* Initialize data structures used for incremental SSA updates.  */
2619
2620 static void
2621 init_update_ssa (struct function *fn)
2622 {
2623   /* Reserve more space than the current number of names.  The calls to
2624      add_new_name_mapping are typically done after creating new SSA
2625      names, so we'll need to reallocate these arrays.  */
2626   old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2627   sbitmap_zero (old_ssa_names);
2628
2629   new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2630   sbitmap_zero (new_ssa_names);
2631
2632   repl_tbl = htab_create (20, repl_map_hash, repl_map_eq, repl_map_free);
2633   names_to_release = NULL;
2634   memset (&update_ssa_stats, 0, sizeof (update_ssa_stats));
2635   update_ssa_stats.virtual_symbols = BITMAP_ALLOC (NULL);
2636   update_ssa_initialized_fn = fn;
2637 }
2638
2639
2640 /* Deallocate data structures used for incremental SSA updates.  */
2641
2642 void
2643 delete_update_ssa (void)
2644 {
2645   unsigned i;
2646   bitmap_iterator bi;
2647
2648   sbitmap_free (old_ssa_names);
2649   old_ssa_names = NULL;
2650
2651   sbitmap_free (new_ssa_names);
2652   new_ssa_names = NULL;
2653
2654   htab_delete (repl_tbl);
2655   repl_tbl = NULL;
2656
2657   bitmap_clear (SYMS_TO_RENAME (update_ssa_initialized_fn));
2658   BITMAP_FREE (update_ssa_stats.virtual_symbols);
2659
2660   if (names_to_release)
2661     {
2662       EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2663         release_ssa_name (ssa_name (i));
2664       BITMAP_FREE (names_to_release);
2665     }
2666
2667   clear_ssa_name_info ();
2668
2669   fini_ssa_renamer ();
2670
2671   if (blocks_with_phis_to_rewrite)
2672     EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
2673       {
2674         gimple_vec phis = VEC_index (gimple_vec, phis_to_rewrite, i);
2675
2676         VEC_free (gimple, heap, phis);
2677         VEC_replace (gimple_vec, phis_to_rewrite, i, NULL);
2678       }
2679
2680   BITMAP_FREE (blocks_with_phis_to_rewrite);
2681   BITMAP_FREE (blocks_to_update);
2682   update_ssa_initialized_fn = NULL;
2683 }
2684
2685
2686 /* Create a new name for OLD_NAME in statement STMT and replace the
2687    operand pointed to by DEF_P with the newly created name.  Return
2688    the new name and register the replacement mapping <NEW, OLD> in
2689    update_ssa's tables.  */
2690
2691 tree
2692 create_new_def_for (tree old_name, gimple stmt, def_operand_p def)
2693 {
2694   tree new_name = duplicate_ssa_name (old_name, stmt);
2695
2696   SET_DEF (def, new_name);
2697
2698   if (gimple_code (stmt) == GIMPLE_PHI)
2699     {
2700       edge e;
2701       edge_iterator ei;
2702       basic_block bb = gimple_bb (stmt);
2703
2704       /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2705       FOR_EACH_EDGE (e, ei, bb->preds)
2706         if (e->flags & EDGE_ABNORMAL)
2707           {
2708             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
2709             break;
2710           }
2711     }
2712
2713   register_new_name_mapping (new_name, old_name);
2714
2715   /* For the benefit of passes that will be updating the SSA form on
2716      their own, set the current reaching definition of OLD_NAME to be
2717      NEW_NAME.  */
2718   set_current_def (old_name, new_name);
2719
2720   return new_name;
2721 }
2722
2723
2724 /* Register name NEW to be a replacement for name OLD.  This function
2725    must be called for every replacement that should be performed by
2726    update_ssa.  */
2727
2728 void
2729 register_new_name_mapping (tree new_tree, tree old)
2730 {
2731   if (!update_ssa_initialized_fn)
2732     init_update_ssa (cfun);
2733
2734   gcc_assert (update_ssa_initialized_fn == cfun);
2735
2736   add_new_name_mapping (new_tree, old);
2737 }
2738
2739
2740 /* Register symbol SYM to be renamed by update_ssa.  */
2741
2742 void
2743 mark_sym_for_renaming (tree sym)
2744 {
2745   bitmap_set_bit (SYMS_TO_RENAME (cfun), DECL_UID (sym));
2746 }
2747
2748
2749 /* Register all the symbols in SET to be renamed by update_ssa.  */
2750
2751 void
2752 mark_set_for_renaming (bitmap set)
2753 {
2754   bitmap_iterator bi;
2755   unsigned i;
2756
2757   if (set == NULL || bitmap_empty_p (set))
2758     return;
2759
2760   EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2761     mark_sym_for_renaming (referenced_var (i));
2762 }
2763
2764
2765 /* Return true if there is any work to be done by update_ssa
2766    for function FN.  */
2767
2768 bool
2769 need_ssa_update_p (struct function *fn)
2770 {
2771   gcc_assert (fn != NULL);
2772   return (update_ssa_initialized_fn == fn
2773           || (fn->gimple_df
2774               && !bitmap_empty_p (SYMS_TO_RENAME (fn))));
2775 }
2776
2777 /* Return true if SSA name mappings have been registered for SSA updating.  */
2778
2779 bool
2780 name_mappings_registered_p (void)
2781 {
2782   if (!update_ssa_initialized_fn)
2783     return false;
2784
2785   gcc_assert (update_ssa_initialized_fn == cfun);
2786
2787   return repl_tbl && htab_elements (repl_tbl) > 0;
2788 }
2789
2790 /* Return true if name N has been registered in the replacement table.  */
2791
2792 bool
2793 name_registered_for_update_p (tree n ATTRIBUTE_UNUSED)
2794 {
2795   if (!update_ssa_initialized_fn)
2796     return false;
2797
2798   gcc_assert (update_ssa_initialized_fn == cfun);
2799
2800   return is_new_name (n) || is_old_name (n);
2801 }
2802
2803
2804 /* Return the set of all the SSA names marked to be replaced.  */
2805
2806 bitmap
2807 ssa_names_to_replace (void)
2808 {
2809   unsigned i = 0;
2810   bitmap ret;
2811   sbitmap_iterator sbi;
2812   
2813   gcc_assert (update_ssa_initialized_fn == NULL
2814               || update_ssa_initialized_fn == cfun);
2815
2816   ret = BITMAP_ALLOC (NULL);
2817   EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
2818     bitmap_set_bit (ret, i);
2819
2820   return ret;
2821 }
2822
2823
2824 /* Mark NAME to be released after update_ssa has finished.  */
2825
2826 void
2827 release_ssa_name_after_update_ssa (tree name)
2828 {
2829   gcc_assert (cfun && update_ssa_initialized_fn == cfun);
2830
2831   if (names_to_release == NULL)
2832     names_to_release = BITMAP_ALLOC (NULL);
2833
2834   bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
2835 }
2836
2837
2838 /* Insert new PHI nodes to replace VAR.  DFS contains dominance
2839    frontier information.  BLOCKS is the set of blocks to be updated.
2840
2841    This is slightly different than the regular PHI insertion
2842    algorithm.  The value of UPDATE_FLAGS controls how PHI nodes for
2843    real names (i.e., GIMPLE registers) are inserted:
2844  
2845    - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
2846      nodes inside the region affected by the block that defines VAR
2847      and the blocks that define all its replacements.  All these
2848      definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
2849
2850      First, we compute the entry point to the region (ENTRY).  This is
2851      given by the nearest common dominator to all the definition
2852      blocks. When computing the iterated dominance frontier (IDF), any
2853      block not strictly dominated by ENTRY is ignored.
2854
2855      We then call the standard PHI insertion algorithm with the pruned
2856      IDF.
2857
2858    - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
2859      names is not pruned.  PHI nodes are inserted at every IDF block.  */
2860
2861 static void
2862 insert_updated_phi_nodes_for (tree var, bitmap *dfs, bitmap blocks,
2863                               unsigned update_flags)
2864 {
2865   basic_block entry;
2866   struct def_blocks_d *db;
2867   bitmap idf, pruned_idf;
2868   bitmap_iterator bi;
2869   unsigned i;
2870
2871 #if defined ENABLE_CHECKING
2872   if (TREE_CODE (var) == SSA_NAME)
2873     gcc_assert (is_old_name (var));
2874   else
2875     gcc_assert (symbol_marked_for_renaming (var));
2876 #endif
2877
2878   /* Get all the definition sites for VAR.  */
2879   db = find_def_blocks_for (var);
2880
2881   /* No need to do anything if there were no definitions to VAR.  */
2882   if (db == NULL || bitmap_empty_p (db->def_blocks))
2883     return;
2884
2885   /* Compute the initial iterated dominance frontier.  */
2886   idf = compute_idf (db->def_blocks, dfs);
2887   pruned_idf = BITMAP_ALLOC (NULL);
2888
2889   if (TREE_CODE (var) == SSA_NAME)
2890     {
2891       if (update_flags == TODO_update_ssa)
2892         {
2893           /* If doing regular SSA updates for GIMPLE registers, we are
2894              only interested in IDF blocks dominated by the nearest
2895              common dominator of all the definition blocks.  */
2896           entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
2897                                                     db->def_blocks);
2898           if (entry != ENTRY_BLOCK_PTR)
2899             EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
2900               if (BASIC_BLOCK (i) != entry
2901                   && dominated_by_p (CDI_DOMINATORS, BASIC_BLOCK (i), entry))
2902                 bitmap_set_bit (pruned_idf, i);
2903         }
2904       else
2905         {
2906           /* Otherwise, do not prune the IDF for VAR.  */
2907           gcc_assert (update_flags == TODO_update_ssa_full_phi);
2908           bitmap_copy (pruned_idf, idf);
2909         }
2910     }
2911   else
2912     {
2913       /* Otherwise, VAR is a symbol that needs to be put into SSA form
2914          for the first time, so we need to compute the full IDF for
2915          it.  */
2916       bitmap_copy (pruned_idf, idf);
2917     }
2918
2919   if (!bitmap_empty_p (pruned_idf))
2920     {
2921       /* Make sure that PRUNED_IDF blocks and all their feeding blocks
2922          are included in the region to be updated.  The feeding blocks
2923          are important to guarantee that the PHI arguments are renamed
2924          properly.  */
2925
2926       /* FIXME, this is not needed if we are updating symbols.  We are
2927          already starting at the ENTRY block anyway.  */
2928       bitmap_ior_into (blocks, pruned_idf);
2929       EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
2930         {
2931           edge e;
2932           edge_iterator ei;
2933           basic_block bb = BASIC_BLOCK (i);
2934
2935           FOR_EACH_EDGE (e, ei, bb->preds)
2936             if (e->src->index >= 0)
2937               bitmap_set_bit (blocks, e->src->index);
2938         }
2939
2940       insert_phi_nodes_for (var, pruned_idf, true);
2941     }
2942
2943   BITMAP_FREE (pruned_idf);
2944   BITMAP_FREE (idf);
2945 }
2946
2947
2948 /* Heuristic to determine whether SSA name mappings for virtual names
2949    should be discarded and their symbols rewritten from scratch.  When
2950    there is a large number of mappings for virtual names, the
2951    insertion of PHI nodes for the old names in the mappings takes
2952    considerable more time than if we inserted PHI nodes for the
2953    symbols instead.
2954
2955    Currently the heuristic takes these stats into account:
2956
2957         - Number of mappings for virtual SSA names.
2958         - Number of distinct virtual symbols involved in those mappings.
2959
2960    If the number of virtual mappings is much larger than the number of
2961    virtual symbols, then it will be faster to compute PHI insertion
2962    spots for the symbols.  Even if this involves traversing the whole
2963    CFG, which is what happens when symbols are renamed from scratch.  */
2964
2965 static bool
2966 switch_virtuals_to_full_rewrite_p (void)
2967 {
2968   if (update_ssa_stats.num_virtual_mappings < (unsigned) MIN_VIRTUAL_MAPPINGS)
2969     return false;
2970
2971   if (update_ssa_stats.num_virtual_mappings
2972       > (unsigned) VIRTUAL_MAPPINGS_TO_SYMS_RATIO
2973         * update_ssa_stats.num_virtual_symbols)
2974     return true;
2975
2976   return false;
2977 }
2978
2979
2980 /* Remove every virtual mapping and mark all the affected virtual
2981    symbols for renaming.  */
2982
2983 static void
2984 switch_virtuals_to_full_rewrite (void)
2985 {
2986   unsigned i = 0;
2987   sbitmap_iterator sbi;
2988
2989   if (dump_file)
2990     {
2991       fprintf (dump_file, "\nEnabled virtual name mapping heuristic.\n");
2992       fprintf (dump_file, "\tNumber of virtual mappings:       %7u\n",
2993                update_ssa_stats.num_virtual_mappings);
2994       fprintf (dump_file, "\tNumber of unique virtual symbols: %7u\n",
2995                update_ssa_stats.num_virtual_symbols);
2996       fprintf (dump_file, "Updating FUD-chains from top of CFG will be "
2997                           "faster than processing\nthe name mappings.\n\n");
2998     }
2999
3000   /* Remove all virtual names from NEW_SSA_NAMES and OLD_SSA_NAMES.
3001      Note that it is not really necessary to remove the mappings from
3002      REPL_TBL, that would only waste time.  */
3003   EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
3004     if (!is_gimple_reg (ssa_name (i)))
3005       RESET_BIT (new_ssa_names, i);
3006
3007   EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
3008     if (!is_gimple_reg (ssa_name (i)))
3009       RESET_BIT (old_ssa_names, i);
3010
3011   mark_set_for_renaming (update_ssa_stats.virtual_symbols);
3012 }
3013
3014
3015 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3016    existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3017
3018    1- The names in OLD_SSA_NAMES dominated by the definitions of
3019       NEW_SSA_NAMES are all re-written to be reached by the
3020       appropriate definition from NEW_SSA_NAMES.
3021
3022    2- If needed, new PHI nodes are added to the iterated dominance
3023       frontier of the blocks where each of NEW_SSA_NAMES are defined.
3024
3025    The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3026    calling register_new_name_mapping for every pair of names that the
3027    caller wants to replace.
3028
3029    The caller identifies the new names that have been inserted and the
3030    names that need to be replaced by calling register_new_name_mapping
3031    for every pair <NEW, OLD>.  Note that the function assumes that the
3032    new names have already been inserted in the IL.
3033
3034    For instance, given the following code:
3035
3036      1  L0:
3037      2  x_1 = PHI (0, x_5)
3038      3  if (x_1 < 10)
3039      4    if (x_1 > 7)
3040      5      y_2 = 0
3041      6    else
3042      7      y_3 = x_1 + x_7
3043      8    endif
3044      9    x_5 = x_1 + 1
3045      10   goto L0;
3046      11 endif
3047
3048    Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3049
3050      1  L0:
3051      2  x_1 = PHI (0, x_5)
3052      3  if (x_1 < 10)
3053      4    x_10 = ...
3054      5    if (x_1 > 7)
3055      6      y_2 = 0
3056      7    else
3057      8      x_11 = ...
3058      9      y_3 = x_1 + x_7
3059      10   endif
3060      11   x_5 = x_1 + 1
3061      12   goto L0;
3062      13 endif
3063
3064    We want to replace all the uses of x_1 with the new definitions of
3065    x_10 and x_11.  Note that the only uses that should be replaced are
3066    those at lines 5, 9 and 11.  Also, the use of x_7 at line 9 should
3067    *not* be replaced (this is why we cannot just mark symbol 'x' for
3068    renaming).
3069
3070    Additionally, we may need to insert a PHI node at line 11 because
3071    that is a merge point for x_10 and x_11.  So the use of x_1 at line
3072    11 will be replaced with the new PHI node.  The insertion of PHI
3073    nodes is optional.  They are not strictly necessary to preserve the
3074    SSA form, and depending on what the caller inserted, they may not
3075    even be useful for the optimizers.  UPDATE_FLAGS controls various
3076    aspects of how update_ssa operates, see the documentation for
3077    TODO_update_ssa*.  */
3078
3079 void
3080 update_ssa (unsigned update_flags)
3081 {
3082   basic_block bb, start_bb;
3083   bitmap_iterator bi;
3084   unsigned i = 0;
3085   bool insert_phi_p;
3086   sbitmap_iterator sbi;
3087
3088   if (!need_ssa_update_p (cfun))
3089     return;
3090
3091   timevar_push (TV_TREE_SSA_INCREMENTAL);
3092
3093   if (!update_ssa_initialized_fn)
3094     init_update_ssa (cfun);
3095   gcc_assert (update_ssa_initialized_fn == cfun);
3096
3097   blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
3098   if (!phis_to_rewrite)
3099     phis_to_rewrite = VEC_alloc (gimple_vec, heap, last_basic_block);
3100   blocks_to_update = BITMAP_ALLOC (NULL);
3101
3102   /* Ensure that the dominance information is up-to-date.  */
3103   calculate_dominance_info (CDI_DOMINATORS);
3104
3105   /* Only one update flag should be set.  */
3106   gcc_assert (update_flags == TODO_update_ssa
3107               || update_flags == TODO_update_ssa_no_phi
3108               || update_flags == TODO_update_ssa_full_phi
3109               || update_flags == TODO_update_ssa_only_virtuals);
3110
3111   /* If we only need to update virtuals, remove all the mappings for
3112      real names before proceeding.  The caller is responsible for
3113      having dealt with the name mappings before calling update_ssa.  */
3114   if (update_flags == TODO_update_ssa_only_virtuals)
3115     {
3116       sbitmap_zero (old_ssa_names);
3117       sbitmap_zero (new_ssa_names);
3118       htab_empty (repl_tbl);
3119     }
3120
3121   insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
3122
3123   if (insert_phi_p)
3124     {
3125       /* If the caller requested PHI nodes to be added, initialize
3126          live-in information data structures (DEF_BLOCKS).  */
3127
3128       /* For each SSA name N, the DEF_BLOCKS table describes where the
3129          name is defined, which blocks have PHI nodes for N, and which
3130          blocks have uses of N (i.e., N is live-on-entry in those
3131          blocks).  */
3132       def_blocks = htab_create (num_ssa_names, def_blocks_hash,
3133                                 def_blocks_eq, def_blocks_free);
3134     }
3135   else
3136     {
3137       def_blocks = NULL;
3138     }
3139
3140   /* Heuristic to avoid massive slow downs when the replacement
3141      mappings include lots of virtual names.  */
3142   if (insert_phi_p && switch_virtuals_to_full_rewrite_p ())
3143     switch_virtuals_to_full_rewrite ();
3144
3145   /* If there are names defined in the replacement table, prepare
3146      definition and use sites for all the names in NEW_SSA_NAMES and
3147      OLD_SSA_NAMES.  */
3148   if (sbitmap_first_set_bit (new_ssa_names) >= 0)
3149     {
3150       prepare_names_to_update (insert_phi_p);
3151
3152       /* If all the names in NEW_SSA_NAMES had been marked for
3153          removal, and there are no symbols to rename, then there's
3154          nothing else to do.  */
3155       if (sbitmap_first_set_bit (new_ssa_names) < 0
3156           && bitmap_empty_p (SYMS_TO_RENAME (cfun)))
3157         goto done;
3158     }
3159
3160   /* Next, determine the block at which to start the renaming process.  */
3161   if (!bitmap_empty_p (SYMS_TO_RENAME (cfun)))
3162     {
3163       /* If we have to rename some symbols from scratch, we need to
3164          start the process at the root of the CFG.  FIXME, it should
3165          be possible to determine the nearest block that had a
3166          definition for each of the symbols that are marked for
3167          updating.  For now this seems more work than it's worth.  */
3168       start_bb = ENTRY_BLOCK_PTR;
3169
3170       /* Traverse the CFG looking for existing definitions and uses of
3171          symbols in SYMS_TO_RENAME.  Mark interesting blocks and
3172          statements and set local live-in information for the PHI
3173          placement heuristics.  */
3174       prepare_block_for_update (start_bb, insert_phi_p);
3175     }
3176   else
3177     {
3178       /* Otherwise, the entry block to the region is the nearest
3179          common dominator for the blocks in BLOCKS.  */
3180       start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3181                                                    blocks_to_update);
3182     }
3183
3184   /* If requested, insert PHI nodes at the iterated dominance frontier
3185      of every block, creating new definitions for names in OLD_SSA_NAMES
3186      and for symbols in SYMS_TO_RENAME.  */
3187   if (insert_phi_p)
3188     {
3189       bitmap *dfs;
3190
3191       /* If the caller requested PHI nodes to be added, compute
3192          dominance frontiers.  */
3193       dfs = XNEWVEC (bitmap, last_basic_block);
3194       FOR_EACH_BB (bb)
3195         dfs[bb->index] = BITMAP_ALLOC (NULL);
3196       compute_dominance_frontiers (dfs);
3197
3198       if (sbitmap_first_set_bit (old_ssa_names) >= 0)
3199         {
3200           sbitmap_iterator sbi;
3201
3202           /* insert_update_phi_nodes_for will call add_new_name_mapping
3203              when inserting new PHI nodes, so the set OLD_SSA_NAMES
3204              will grow while we are traversing it (but it will not
3205              gain any new members).  Copy OLD_SSA_NAMES to a temporary
3206              for traversal.  */
3207           sbitmap tmp = sbitmap_alloc (old_ssa_names->n_bits);
3208           sbitmap_copy (tmp, old_ssa_names);
3209           EXECUTE_IF_SET_IN_SBITMAP (tmp, 0, i, sbi)
3210             insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
3211                                           update_flags);
3212           sbitmap_free (tmp);
3213         }
3214
3215       EXECUTE_IF_SET_IN_BITMAP (SYMS_TO_RENAME (cfun), 0, i, bi)
3216         insert_updated_phi_nodes_for (referenced_var (i), dfs, blocks_to_update,
3217                                       update_flags);
3218
3219       FOR_EACH_BB (bb)
3220         BITMAP_FREE (dfs[bb->index]);
3221       free (dfs);
3222
3223       /* Insertion of PHI nodes may have added blocks to the region.
3224          We need to re-compute START_BB to include the newly added
3225          blocks.  */
3226       if (start_bb != ENTRY_BLOCK_PTR)
3227         start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3228                                                      blocks_to_update);
3229     }
3230
3231   /* Reset the current definition for name and symbol before renaming
3232      the sub-graph.  */
3233   EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
3234     set_current_def (ssa_name (i), NULL_TREE);
3235
3236   EXECUTE_IF_SET_IN_BITMAP (SYMS_TO_RENAME (cfun), 0, i, bi)
3237     set_current_def (referenced_var (i), NULL_TREE);
3238
3239   /* Now start the renaming process at START_BB.  */
3240   interesting_blocks = sbitmap_alloc (last_basic_block);
3241   sbitmap_zero (interesting_blocks);
3242   EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3243     SET_BIT (interesting_blocks, i);
3244
3245   rewrite_blocks (start_bb, REWRITE_UPDATE);
3246
3247   sbitmap_free (interesting_blocks);
3248
3249   /* Debugging dumps.  */
3250   if (dump_file)
3251     {
3252       int c;
3253       unsigned i;
3254
3255       dump_update_ssa (dump_file);
3256
3257       fprintf (dump_file, "Incremental SSA update started at block: %d\n\n",
3258                start_bb->index);
3259
3260       c = 0;
3261       EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3262         c++;
3263       fprintf (dump_file, "Number of blocks in CFG: %d\n", last_basic_block);
3264       fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n\n",
3265                c, PERCENT (c, last_basic_block));
3266
3267       if (dump_flags & TDF_DETAILS)
3268         {
3269           fprintf (dump_file, "Affected blocks: ");
3270           EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3271             fprintf (dump_file, "%u ", i);
3272           fprintf (dump_file, "\n");
3273         }
3274
3275       fprintf (dump_file, "\n\n");
3276     }
3277
3278   /* Free allocated memory.  */
3279 done:
3280   delete_update_ssa ();
3281
3282   timevar_pop (TV_TREE_SSA_INCREMENTAL);
3283 }