OSDN Git Service

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