OSDN Git Service

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