OSDN Git Service

* cfganal.c: Include vec.h and vecprim.h.
[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 /* Return the set of blocks where variable VAR is defined and the blocks
989    where VAR is live on entry (livein).  Return NULL, if no entry is
990    found in DEF_BLOCKS.  */
991
992 static inline struct def_blocks_d *
993 find_def_blocks_for (tree var)
994 {
995   struct def_blocks_d dm;
996   dm.var = var;
997   return (struct def_blocks_d *) htab_find (def_blocks, &dm);
998 }
999
1000
1001 /* Retrieve or create a default definition for symbol SYM.  */
1002
1003 static inline tree
1004 get_default_def_for (tree sym)
1005 {
1006   tree ddef = gimple_default_def (cfun, sym);
1007
1008   if (ddef == NULL_TREE)
1009     {
1010       ddef = make_ssa_name (sym, build_empty_stmt ());
1011       set_default_def (sym, ddef);
1012     }
1013
1014   return ddef;
1015 }
1016
1017
1018 /* Marks phi node PHI in basic block BB for rewrite.  */
1019
1020 static void
1021 mark_phi_for_rewrite (basic_block bb, tree phi)
1022 {
1023   tree_vec phis;
1024   unsigned i, idx = bb->index;
1025
1026   if (REWRITE_THIS_STMT (phi))
1027     return;
1028
1029   REWRITE_THIS_STMT (phi) = 1;
1030
1031   if (!blocks_with_phis_to_rewrite)
1032     return;
1033
1034   bitmap_set_bit (blocks_with_phis_to_rewrite, idx);
1035   VEC_reserve (tree_vec, heap, phis_to_rewrite, last_basic_block + 1);
1036   for (i = VEC_length (tree_vec, phis_to_rewrite); i <= idx; i++)
1037     VEC_quick_push (tree_vec, phis_to_rewrite, NULL);
1038
1039   phis = VEC_index (tree_vec, phis_to_rewrite, idx);
1040   if (!phis)
1041     phis = VEC_alloc (tree, heap, 10);
1042
1043   VEC_safe_push (tree, heap, phis, phi);
1044   VEC_replace (tree_vec, phis_to_rewrite, idx, phis);
1045 }
1046
1047
1048 /* Insert PHI nodes for variable VAR using the iterated dominance
1049    frontier given in PHI_INSERTION_POINTS.  If UPDATE_P is true, this
1050    function assumes that the caller is incrementally updating the
1051    existing SSA form, in which case VAR may be an SSA name instead of
1052    a symbol.
1053
1054    PHI_INSERTION_POINTS is updated to reflect nodes that already had a
1055    PHI node for VAR.  On exit, only the nodes that received a PHI node
1056    for VAR will be present in PHI_INSERTION_POINTS.  */
1057
1058 static void
1059 insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
1060 {
1061   unsigned bb_index;
1062   edge e;
1063   tree phi;
1064   basic_block bb;
1065   bitmap_iterator bi;
1066   struct def_blocks_d *def_map;
1067
1068   def_map = find_def_blocks_for (var);
1069   gcc_assert (def_map);
1070
1071   /* Remove the blocks where we already have PHI nodes for VAR.  */
1072   bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
1073
1074   /* Remove obviously useless phi nodes.  */
1075   prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks,
1076                           def_map->livein_blocks);
1077
1078   /* And insert the PHI nodes.  */
1079   EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
1080     {
1081       bb = BASIC_BLOCK (bb_index);
1082       if (update_p)
1083         mark_block_for_update (bb);
1084
1085       phi = NULL_TREE;
1086
1087       if (TREE_CODE (var) == SSA_NAME)
1088         {
1089           /* If we are rewriting SSA names, create the LHS of the PHI
1090              node by duplicating VAR.  This is useful in the case of
1091              pointers, to also duplicate pointer attributes (alias
1092              information, in particular).  */
1093           edge_iterator ei;
1094           tree new_lhs;
1095
1096           gcc_assert (update_p);
1097           phi = create_phi_node (var, bb);
1098
1099           new_lhs = duplicate_ssa_name (var, phi);
1100           SET_PHI_RESULT (phi, new_lhs);
1101           add_new_name_mapping (new_lhs, var);
1102
1103           /* Add VAR to every argument slot of PHI.  We need VAR in
1104              every argument so that rewrite_update_phi_arguments knows
1105              which name is this PHI node replacing.  If VAR is a
1106              symbol marked for renaming, this is not necessary, the
1107              renamer will use the symbol on the LHS to get its
1108              reaching definition.  */
1109           FOR_EACH_EDGE (e, ei, bb->preds)
1110             add_phi_arg (phi, var, e);
1111         }
1112       else
1113         {
1114           tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
1115           phi = create_phi_node (sym, bb);
1116         }
1117
1118       /* Mark this PHI node as interesting for update_ssa.  */
1119       REGISTER_DEFS_IN_THIS_STMT (phi) = 1;
1120       mark_phi_for_rewrite (bb, phi);
1121     }
1122 }
1123
1124
1125 /* Insert PHI nodes at the dominance frontier of blocks with variable
1126    definitions.  DFS contains the dominance frontier information for
1127    the flowgraph.  */
1128
1129 static void
1130 insert_phi_nodes (bitmap *dfs)
1131 {
1132   referenced_var_iterator rvi;
1133   tree var;
1134
1135   timevar_push (TV_TREE_INSERT_PHI_NODES);
1136   
1137   FOR_EACH_REFERENCED_VAR (var, rvi)
1138     {
1139       struct def_blocks_d *def_map;
1140       bitmap idf;
1141
1142       def_map = find_def_blocks_for (var);
1143       if (def_map == NULL)
1144         continue;
1145
1146       if (get_phi_state (var) != NEED_PHI_STATE_NO)
1147         {
1148           idf = compute_idf (def_map->def_blocks, dfs);
1149           insert_phi_nodes_for (var, idf, false);
1150           BITMAP_FREE (idf);
1151         }
1152     }
1153
1154   timevar_pop (TV_TREE_INSERT_PHI_NODES);
1155 }
1156
1157
1158 /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1159    register DEF (an SSA_NAME) to be a new definition for SYM.  */
1160
1161 static void
1162 register_new_def (tree def, tree sym)
1163 {
1164   tree currdef;
1165    
1166   /* If this variable is set in a single basic block and all uses are
1167      dominated by the set(s) in that single basic block, then there is
1168      no reason to record anything for this variable in the block local
1169      definition stacks.  Doing so just wastes time and memory.
1170
1171      This is the same test to prune the set of variables which may
1172      need PHI nodes.  So we just use that information since it's already
1173      computed and available for us to use.  */
1174   if (get_phi_state (sym) == NEED_PHI_STATE_NO)
1175     {
1176       set_current_def (sym, def);
1177       return;
1178     }
1179
1180   currdef = get_current_def (sym);
1181
1182   /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1183      SSA_NAME_VAR is not necessarily SYM.  In this case, also push SYM
1184      in the stack so that we know which symbol is being defined by
1185      this SSA name when we unwind the stack.  */
1186   if (currdef && !is_gimple_reg (sym))
1187     VEC_safe_push (tree, heap, block_defs_stack, sym);
1188
1189   /* Push the current reaching definition into BLOCK_DEFS_STACK.  This
1190      stack is later used by the dominator tree callbacks to restore
1191      the reaching definitions for all the variables defined in the
1192      block after a recursive visit to all its immediately dominated
1193      blocks.  If there is no current reaching definition, then just
1194      record the underlying _DECL node.  */
1195   VEC_safe_push (tree, heap, block_defs_stack, currdef ? currdef : sym);
1196
1197   /* Set the current reaching definition for SYM to be DEF.  */
1198   set_current_def (sym, def);
1199 }
1200
1201
1202 /* Perform a depth-first traversal of the dominator tree looking for
1203    variables to rename.  BB is the block where to start searching.
1204    Renaming is a five step process:
1205
1206    1- Every definition made by PHI nodes at the start of the blocks is
1207       registered as the current definition for the corresponding variable.
1208
1209    2- Every statement in BB is rewritten.  USE and VUSE operands are
1210       rewritten with their corresponding reaching definition.  DEF and
1211       VDEF targets are registered as new definitions.
1212       
1213    3- All the PHI nodes in successor blocks of BB are visited.  The
1214       argument corresponding to BB is replaced with its current reaching
1215       definition.
1216
1217    4- Recursively rewrite every dominator child block of BB.
1218
1219    5- Restore (in reverse order) the current reaching definition for every
1220       new definition introduced in this block.  This is done so that when
1221       we return from the recursive call, all the current reaching
1222       definitions are restored to the names that were valid in the
1223       dominator parent of BB.  */
1224
1225 /* SSA Rewriting Step 1.  Initialization, create a block local stack
1226    of reaching definitions for new SSA names produced in this block
1227    (BLOCK_DEFS).  Register new definitions for every PHI node in the
1228    block.  */
1229
1230 static void
1231 rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1232                           basic_block bb)
1233 {
1234   tree phi;
1235
1236   if (dump_file && (dump_flags & TDF_DETAILS))
1237     fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
1238
1239   /* Mark the unwind point for this block.  */
1240   VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
1241
1242   /* Step 1.  Register new definitions for every PHI node in the block.
1243      Conceptually, all the PHI nodes are executed in parallel and each PHI
1244      node introduces a new version for the associated variable.  */
1245   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1246     {
1247       tree result = PHI_RESULT (phi);
1248       gcc_assert (is_gimple_reg (result));
1249       register_new_def (result, SSA_NAME_VAR (result));
1250     }
1251 }
1252
1253
1254 /* Return the current definition for variable VAR.  If none is found,
1255    create a new SSA name to act as the zeroth definition for VAR.  */
1256
1257 static tree
1258 get_reaching_def (tree var)
1259 {
1260   tree currdef;
1261   
1262   /* Lookup the current reaching definition for VAR.  */
1263   currdef = get_current_def (var);
1264
1265   /* If there is no reaching definition for VAR, create and register a
1266      default definition for it (if needed).  */
1267   if (currdef == NULL_TREE)
1268     {
1269       tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
1270       currdef = get_default_def_for (sym);
1271       set_current_def (var, currdef);
1272     }
1273
1274   /* Return the current reaching definition for VAR, or the default
1275      definition, if we had to create one.  */
1276   return currdef;
1277 }
1278
1279
1280 /* SSA Rewriting Step 2.  Rewrite every variable used in each statement in
1281    the block with its immediate reaching definitions.  Update the current
1282    definition of a variable when a new real or virtual definition is found.  */
1283
1284 static void
1285 rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1286               basic_block bb ATTRIBUTE_UNUSED, block_stmt_iterator si)
1287 {
1288   tree stmt;
1289   use_operand_p use_p;
1290   def_operand_p def_p;
1291   ssa_op_iter iter;
1292
1293   stmt = bsi_stmt (si);
1294
1295   /* If mark_def_sites decided that we don't need to rewrite this
1296      statement, ignore it.  */
1297   gcc_assert (blocks_to_update == NULL);
1298   if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
1299     return;
1300
1301   if (dump_file && (dump_flags & TDF_DETAILS))
1302     {
1303       fprintf (dump_file, "Renaming statement ");
1304       print_generic_stmt (dump_file, stmt, TDF_SLIM);
1305       fprintf (dump_file, "\n");
1306     }
1307
1308   /* Step 1.  Rewrite USES in the statement.  */
1309   if (REWRITE_THIS_STMT (stmt))
1310     FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1311       {
1312         tree var = USE_FROM_PTR (use_p);
1313         gcc_assert (DECL_P (var));
1314         SET_USE (use_p, get_reaching_def (var));
1315       }
1316
1317   /* Step 2.  Register the statement's DEF operands.  */
1318   if (REGISTER_DEFS_IN_THIS_STMT (stmt))
1319     FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1320       {
1321         tree var = DEF_FROM_PTR (def_p);
1322         gcc_assert (DECL_P (var));
1323         SET_DEF (def_p, make_ssa_name (var, stmt));
1324         register_new_def (DEF_FROM_PTR (def_p), var);
1325       }
1326 }
1327
1328
1329 /* SSA Rewriting Step 3.  Visit all the successor blocks of BB looking for
1330    PHI nodes.  For every PHI node found, add a new argument containing the
1331    current reaching definition for the variable and the edge through which
1332    that definition is reaching the PHI node.  */
1333
1334 static void
1335 rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1336                            basic_block bb)
1337 {
1338   edge e;
1339   edge_iterator ei;
1340
1341   FOR_EACH_EDGE (e, ei, bb->succs)
1342     {
1343       tree phi;
1344
1345       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
1346         {
1347           tree currdef;
1348           currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
1349           add_phi_arg (phi, currdef, e);
1350         }
1351     }
1352 }
1353
1354
1355 /* Called after visiting all the statements in basic block BB and all
1356    of its dominator children.  Restore CURRDEFS to its original value.  */
1357
1358 static void
1359 rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1360                         basic_block bb ATTRIBUTE_UNUSED)
1361 {
1362   /* Restore CURRDEFS to its original state.  */
1363   while (VEC_length (tree, block_defs_stack) > 0)
1364     {
1365       tree tmp = VEC_pop (tree, block_defs_stack);
1366       tree saved_def, var;
1367
1368       if (tmp == NULL_TREE)
1369         break;
1370
1371       if (TREE_CODE (tmp) == SSA_NAME)
1372         {
1373           /* If we recorded an SSA_NAME, then make the SSA_NAME the
1374              current definition of its underlying variable.  Note that
1375              if the SSA_NAME is not for a GIMPLE register, the symbol
1376              being defined is stored in the next slot in the stack.
1377              This mechanism is needed because an SSA name for a
1378              non-register symbol may be the definition for more than
1379              one symbol (e.g., SFTs, aliased variables, etc).  */
1380           saved_def = tmp;
1381           var = SSA_NAME_VAR (saved_def);
1382           if (!is_gimple_reg (var))
1383             var = VEC_pop (tree, block_defs_stack);
1384         }
1385       else
1386         {
1387           /* If we recorded anything else, it must have been a _DECL
1388              node and its current reaching definition must have been
1389              NULL.  */
1390           saved_def = NULL;
1391           var = tmp;
1392         }
1393                                                                                 
1394       set_current_def (var, saved_def);
1395     }
1396 }
1397
1398
1399 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE.  */
1400
1401 void
1402 dump_decl_set (FILE *file, bitmap set)
1403 {
1404   if (set)
1405     {
1406       bitmap_iterator bi;
1407       unsigned i;
1408
1409       fprintf (file, "{ ");
1410
1411       EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
1412         {
1413           print_generic_expr (file, referenced_var (i), 0);
1414           fprintf (file, " ");
1415         }
1416
1417       fprintf (file, "}\n");
1418     }
1419   else
1420     fprintf (file, "NIL\n");
1421 }
1422
1423
1424 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE.  */
1425
1426 void
1427 debug_decl_set (bitmap set)
1428 {
1429   dump_decl_set (stderr, set);
1430 }
1431
1432
1433 /* Dump the renaming stack (block_defs_stack) to FILE.  Traverse the
1434    stack up to a maximum of N levels.  If N is -1, the whole stack is
1435    dumped.  New levels are created when the dominator tree traversal
1436    used for renaming enters a new sub-tree.  */
1437
1438 void
1439 dump_defs_stack (FILE *file, int n)
1440 {
1441   int i, j;
1442
1443   fprintf (file, "\n\nRenaming stack");
1444   if (n > 0)
1445     fprintf (file, " (up to %d levels)", n);
1446   fprintf (file, "\n\n");
1447
1448   i = 1;
1449   fprintf (file, "Level %d (current level)\n", i);
1450   for (j = (int) VEC_length (tree, block_defs_stack) - 1; j >= 0; j--)
1451     {
1452       tree name, var;
1453       
1454       name = VEC_index (tree, block_defs_stack, j);
1455       if (name == NULL_TREE)
1456         {
1457           i++;
1458           if (n > 0 && i > n)
1459             break;
1460           fprintf (file, "\nLevel %d\n", i);
1461           continue;
1462         }
1463
1464       if (DECL_P (name))
1465         {
1466           var = name;
1467           name = NULL_TREE;
1468         }
1469       else
1470         {
1471           var = SSA_NAME_VAR (name);
1472           if (!is_gimple_reg (var))
1473             {
1474               j--;
1475               var = VEC_index (tree, block_defs_stack, j);
1476             }
1477         }
1478
1479       fprintf (file, "    Previous CURRDEF (");
1480       print_generic_expr (file, var, 0);
1481       fprintf (file, ") = ");
1482       if (name)
1483         print_generic_expr (file, name, 0);
1484       else
1485         fprintf (file, "<NIL>");
1486       fprintf (file, "\n");
1487     }
1488 }
1489
1490
1491 /* Dump the renaming stack (block_defs_stack) to stderr.  Traverse the
1492    stack up to a maximum of N levels.  If N is -1, the whole stack is
1493    dumped.  New levels are created when the dominator tree traversal
1494    used for renaming enters a new sub-tree.  */
1495
1496 void
1497 debug_defs_stack (int n)
1498 {
1499   dump_defs_stack (stderr, n);
1500 }
1501
1502
1503 /* Dump the current reaching definition of every symbol to FILE.  */
1504
1505 void
1506 dump_currdefs (FILE *file)
1507 {
1508   referenced_var_iterator i;
1509   tree var;
1510
1511   fprintf (file, "\n\nCurrent reaching definitions\n\n");
1512   FOR_EACH_REFERENCED_VAR (var, i)
1513     if (syms_to_rename == NULL || bitmap_bit_p (syms_to_rename, DECL_UID (var)))
1514       {
1515         fprintf (file, "CURRDEF (");
1516         print_generic_expr (file, var, 0);
1517         fprintf (file, ") = ");
1518         if (get_current_def (var))
1519           print_generic_expr (file, get_current_def (var), 0);
1520         else
1521           fprintf (file, "<NIL>");
1522         fprintf (file, "\n");
1523       }
1524 }
1525
1526
1527 /* Dump the current reaching definition of every symbol to stderr.  */
1528
1529 void
1530 debug_currdefs (void)
1531 {
1532   dump_currdefs (stderr);
1533 }
1534
1535
1536 /* Dump SSA information to FILE.  */
1537
1538 void
1539 dump_tree_ssa (FILE *file)
1540 {
1541   const char *funcname
1542     = lang_hooks.decl_printable_name (current_function_decl, 2);
1543
1544   fprintf (file, "SSA renaming information for %s\n\n", funcname);
1545
1546   dump_def_blocks (file);
1547   dump_defs_stack (file, -1);
1548   dump_currdefs (file);
1549   dump_tree_ssa_stats (file);
1550 }
1551
1552
1553 /* Dump SSA information to stderr.  */
1554
1555 void
1556 debug_tree_ssa (void)
1557 {
1558   dump_tree_ssa (stderr);
1559 }
1560
1561
1562 /* Dump statistics for the hash table HTAB.  */
1563
1564 static void
1565 htab_statistics (FILE *file, htab_t htab)
1566 {
1567   fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1568            (long) htab_size (htab),
1569            (long) htab_elements (htab),
1570            htab_collisions (htab));
1571 }
1572
1573
1574 /* Dump SSA statistics on FILE.  */
1575
1576 void
1577 dump_tree_ssa_stats (FILE *file)
1578 {
1579   if (def_blocks || repl_tbl)
1580     fprintf (file, "\nHash table statistics:\n");
1581
1582   if (def_blocks)
1583     {
1584       fprintf (file, "    def_blocks:   ");
1585       htab_statistics (file, def_blocks);
1586     }
1587
1588   if (repl_tbl)
1589     {
1590       fprintf (file, "    repl_tbl:     ");
1591       htab_statistics (file, repl_tbl);
1592     }
1593
1594   if (def_blocks || repl_tbl)
1595     fprintf (file, "\n");
1596 }
1597
1598
1599 /* Dump SSA statistics on stderr.  */
1600
1601 void
1602 debug_tree_ssa_stats (void)
1603 {
1604   dump_tree_ssa_stats (stderr);
1605 }
1606
1607
1608 /* Hashing and equality functions for DEF_BLOCKS.  */
1609
1610 static hashval_t
1611 def_blocks_hash (const void *p)
1612 {
1613   return htab_hash_pointer
1614         ((const void *)((const struct def_blocks_d *)p)->var);
1615 }
1616
1617 static int
1618 def_blocks_eq (const void *p1, const void *p2)
1619 {
1620   return ((const struct def_blocks_d *)p1)->var
1621          == ((const struct def_blocks_d *)p2)->var;
1622 }
1623
1624
1625 /* Free memory allocated by one entry in DEF_BLOCKS.  */
1626
1627 static void
1628 def_blocks_free (void *p)
1629 {
1630   struct def_blocks_d *entry = (struct def_blocks_d *) p;
1631   BITMAP_FREE (entry->def_blocks);
1632   BITMAP_FREE (entry->phi_blocks);
1633   BITMAP_FREE (entry->livein_blocks);
1634   free (entry);
1635 }
1636
1637
1638 /* Callback for htab_traverse to dump the DEF_BLOCKS hash table.  */
1639
1640 static int
1641 debug_def_blocks_r (void **slot, void *data)
1642 {
1643   FILE *file = (FILE *) data;
1644   struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
1645   
1646   fprintf (file, "VAR: ");
1647   print_generic_expr (file, db_p->var, dump_flags);
1648   bitmap_print (file, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
1649   bitmap_print (file, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}");
1650   bitmap_print (file, db_p->phi_blocks, ", PHI_BLOCKS: { ", "}\n");
1651
1652   return 1;
1653 }
1654
1655
1656 /* Dump the DEF_BLOCKS hash table on FILE.  */
1657
1658 void
1659 dump_def_blocks (FILE *file)
1660 {
1661   fprintf (file, "\n\nDefinition and live-in blocks:\n\n");
1662   if (def_blocks)
1663     htab_traverse (def_blocks, debug_def_blocks_r, file);
1664 }
1665
1666
1667 /* Dump the DEF_BLOCKS hash table on stderr.  */
1668
1669 void
1670 debug_def_blocks (void)
1671 {
1672   dump_def_blocks (stderr);
1673 }
1674
1675
1676 /* Register NEW_NAME to be the new reaching definition for OLD_NAME.  */
1677
1678 static inline void
1679 register_new_update_single (tree new_name, tree old_name)
1680 {
1681   tree currdef = get_current_def (old_name);
1682
1683   /* Push the current reaching definition into BLOCK_DEFS_STACK.
1684      This stack is later used by the dominator tree callbacks to
1685      restore the reaching definitions for all the variables
1686      defined in the block after a recursive visit to all its
1687      immediately dominated blocks.  */
1688   VEC_reserve (tree, heap, block_defs_stack, 2);
1689   VEC_quick_push (tree, block_defs_stack, currdef);
1690   VEC_quick_push (tree, block_defs_stack, old_name);
1691
1692   /* Set the current reaching definition for OLD_NAME to be
1693      NEW_NAME.  */
1694   set_current_def (old_name, new_name);
1695 }
1696
1697
1698 /* Register NEW_NAME to be the new reaching definition for all the
1699    names in OLD_NAMES.  Used by the incremental SSA update routines to
1700    replace old SSA names with new ones.  */
1701
1702 static inline void
1703 register_new_update_set (tree new_name, bitmap old_names)
1704 {
1705   bitmap_iterator bi;
1706   unsigned i;
1707
1708   EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
1709     register_new_update_single (new_name, ssa_name (i));
1710 }
1711
1712
1713 /* Initialization of block data structures for the incremental SSA
1714    update pass.  Create a block local stack of reaching definitions
1715    for new SSA names produced in this block (BLOCK_DEFS).  Register
1716    new definitions for every PHI node in the block.  */
1717
1718 static void
1719 rewrite_update_init_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1720                            basic_block bb)
1721 {
1722   edge e;
1723   edge_iterator ei;
1724   tree phi;
1725   bool is_abnormal_phi;
1726
1727   if (dump_file && (dump_flags & TDF_DETAILS))
1728     fprintf (dump_file, "\n\nRegistering new PHI nodes in block #%d\n\n",
1729              bb->index);
1730
1731   /* Mark the unwind point for this block.  */
1732   VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
1733
1734   if (!bitmap_bit_p (blocks_to_update, bb->index))
1735     return;
1736
1737   /* Mark the LHS if any of the arguments flows through an abnormal
1738      edge.  */
1739   is_abnormal_phi = false;
1740   FOR_EACH_EDGE (e, ei, bb->preds)
1741     if (e->flags & EDGE_ABNORMAL)
1742       {
1743         is_abnormal_phi = true;
1744         break;
1745       }
1746
1747   /* If any of the PHI nodes is a replacement for a name in
1748      OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
1749      register it as a new definition for its corresponding name.  Also
1750      register definitions for names whose underlying symbols are
1751      marked for renaming.  */
1752   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1753     {
1754       tree lhs, lhs_sym;
1755
1756       if (!REGISTER_DEFS_IN_THIS_STMT (phi))
1757         continue;
1758       
1759       lhs = PHI_RESULT (phi);
1760       lhs_sym = SSA_NAME_VAR (lhs);
1761
1762       if (symbol_marked_for_renaming (lhs_sym))
1763         register_new_update_single (lhs, lhs_sym);
1764       else
1765         {
1766
1767           /* If LHS is a new name, register a new definition for all
1768              the names replaced by LHS.  */
1769           if (is_new_name (lhs))
1770             register_new_update_set (lhs, names_replaced_by (lhs));
1771           
1772           /* If LHS is an OLD name, register it as a new definition
1773              for itself.  */
1774           if (is_old_name (lhs))
1775             register_new_update_single (lhs, lhs);
1776         }
1777
1778       if (is_abnormal_phi)
1779         SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
1780     }
1781 }
1782
1783
1784 /* Called after visiting block BB.  Unwind BLOCK_DEFS_STACK to restore
1785    the current reaching definition of every name re-written in BB to
1786    the original reaching definition before visiting BB.  This
1787    unwinding must be done in the opposite order to what is done in
1788    register_new_update_set.  */
1789
1790 static void
1791 rewrite_update_fini_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1792                            basic_block bb ATTRIBUTE_UNUSED)
1793 {
1794   while (VEC_length (tree, block_defs_stack) > 0)
1795     {
1796       tree var = VEC_pop (tree, block_defs_stack);
1797       tree saved_def;
1798       
1799       /* NULL indicates the unwind stop point for this block (see
1800          rewrite_update_init_block).  */
1801       if (var == NULL)
1802         return;
1803
1804       saved_def = VEC_pop (tree, block_defs_stack);
1805       set_current_def (var, saved_def);
1806     }
1807 }
1808
1809
1810 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1811    it is a symbol marked for renaming, replace it with USE_P's current
1812    reaching definition.  */
1813
1814 static inline void
1815 maybe_replace_use (use_operand_p use_p)
1816 {
1817   tree rdef = NULL_TREE;
1818   tree use = USE_FROM_PTR (use_p);
1819   tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1820
1821   if (symbol_marked_for_renaming (sym))
1822     rdef = get_reaching_def (sym);
1823   else if (is_old_name (use))
1824     rdef = get_reaching_def (use);
1825
1826   if (rdef && rdef != use)
1827     SET_USE (use_p, rdef);
1828 }
1829
1830
1831 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1832    or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1833    register it as the current definition for the names replaced by
1834    DEF_P.  */
1835
1836 static inline void
1837 maybe_register_def (def_operand_p def_p, tree stmt)
1838 {
1839   tree def = DEF_FROM_PTR (def_p);
1840   tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1841
1842   /* If DEF is a naked symbol that needs renaming, create a new
1843      name for it.  */
1844   if (symbol_marked_for_renaming (sym))
1845     {
1846       if (DECL_P (def))
1847         {
1848           def = make_ssa_name (def, stmt);
1849           SET_DEF (def_p, def);
1850         }
1851
1852       register_new_update_single (def, sym);
1853     }
1854   else
1855     {
1856       /* If DEF is a new name, register it as a new definition
1857          for all the names replaced by DEF.  */
1858       if (is_new_name (def))
1859         register_new_update_set (def, names_replaced_by (def));
1860
1861       /* If DEF is an old name, register DEF as a new
1862          definition for itself.  */
1863       if (is_old_name (def))
1864         register_new_update_single (def, def);
1865     }
1866 }
1867
1868
1869 /* Update every variable used in the statement pointed-to by SI.  The
1870    statement is assumed to be in SSA form already.  Names in
1871    OLD_SSA_NAMES used by SI will be updated to their current reaching
1872    definition.  Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1873    will be registered as a new definition for their corresponding name
1874    in OLD_SSA_NAMES.  */
1875
1876 static void
1877 rewrite_update_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1878                      basic_block bb ATTRIBUTE_UNUSED,
1879                      block_stmt_iterator si)
1880 {
1881   stmt_ann_t ann;
1882   tree stmt;
1883   use_operand_p use_p;
1884   def_operand_p def_p;
1885   ssa_op_iter iter;
1886
1887   stmt = bsi_stmt (si);
1888   ann = stmt_ann (stmt);
1889
1890   gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
1891
1892   /* Only update marked statements.  */
1893   if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
1894     return;
1895
1896   if (dump_file && (dump_flags & TDF_DETAILS))
1897     {
1898       fprintf (dump_file, "Updating SSA information for statement ");
1899       print_generic_stmt (dump_file, stmt, TDF_SLIM);
1900       fprintf (dump_file, "\n");
1901     }
1902
1903   /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
1904      symbol is marked for renaming.  */
1905   if (REWRITE_THIS_STMT (stmt))
1906     {
1907       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1908         maybe_replace_use (use_p);
1909
1910       if (need_to_update_vops_p)
1911         FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_VIRTUAL_USES)
1912           maybe_replace_use (use_p);
1913     }
1914
1915   /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
1916      Also register definitions for names whose underlying symbol is
1917      marked for renaming.  */
1918   if (REGISTER_DEFS_IN_THIS_STMT (stmt))
1919     {
1920       FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1921         maybe_register_def (def_p, stmt);
1922
1923       if (need_to_update_vops_p)
1924         FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_VIRTUAL_DEFS)
1925           maybe_register_def (def_p, stmt);
1926     }
1927 }
1928
1929
1930 /* Visit all the successor blocks of BB looking for PHI nodes.  For
1931    every PHI node found, check if any of its arguments is in
1932    OLD_SSA_NAMES.  If so, and if the argument has a current reaching
1933    definition, replace it.  */
1934
1935 static void
1936 rewrite_update_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1937                               basic_block bb)
1938 {
1939   edge e;
1940   edge_iterator ei;
1941   unsigned i;
1942
1943   FOR_EACH_EDGE (e, ei, bb->succs)
1944     {
1945       tree phi;
1946       tree_vec phis;
1947
1948       if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
1949         continue;
1950      
1951       phis = VEC_index (tree_vec, phis_to_rewrite, e->dest->index);
1952       for (i = 0; VEC_iterate (tree, phis, i, phi); i++)
1953         {
1954           tree arg, lhs_sym;
1955           use_operand_p arg_p;
1956
1957           gcc_assert (REWRITE_THIS_STMT (phi));
1958
1959           arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
1960           arg = USE_FROM_PTR (arg_p);
1961
1962           if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
1963             continue;
1964
1965           lhs_sym = SSA_NAME_VAR (PHI_RESULT (phi));
1966
1967           if (arg == NULL_TREE)
1968             {
1969               /* When updating a PHI node for a recently introduced
1970                  symbol we may find NULL arguments.  That's why we
1971                  take the symbol from the LHS of the PHI node.  */
1972               SET_USE (arg_p, get_reaching_def (lhs_sym));
1973             }
1974           else
1975             {
1976               tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
1977
1978               if (symbol_marked_for_renaming (sym))
1979                 SET_USE (arg_p, get_reaching_def (sym));
1980               else if (is_old_name (arg))
1981                 SET_USE (arg_p, get_reaching_def (arg));
1982             }
1983
1984           if (e->flags & EDGE_ABNORMAL)
1985             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
1986         }
1987     }
1988 }
1989
1990
1991 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
1992    form.  
1993
1994    ENTRY indicates the block where to start.  Every block dominated by
1995       ENTRY will be rewritten.
1996
1997    WHAT indicates what actions will be taken by the renamer (see enum
1998       rewrite_mode).
1999
2000    BLOCKS are the set of interesting blocks for the dominator walker
2001       to process.  If this set is NULL, then all the nodes dominated
2002       by ENTRY are walked.  Otherwise, blocks dominated by ENTRY that
2003       are not present in BLOCKS are ignored.  */
2004
2005 static void
2006 rewrite_blocks (basic_block entry, enum rewrite_mode what, sbitmap blocks)
2007 {
2008   struct dom_walk_data walk_data;
2009   
2010   /* Rewrite all the basic blocks in the program.  */
2011   timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
2012
2013   /* Setup callbacks for the generic dominator tree walker.  */
2014   memset (&walk_data, 0, sizeof (walk_data));
2015
2016   walk_data.dom_direction = CDI_DOMINATORS;
2017   walk_data.interesting_blocks = blocks;
2018
2019   if (what == REWRITE_ALL)
2020     walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
2021   else
2022     walk_data.before_dom_children_before_stmts = rewrite_update_init_block;
2023
2024   if (what == REWRITE_ALL)
2025     walk_data.before_dom_children_walk_stmts = rewrite_stmt;
2026   else if (what == REWRITE_UPDATE)
2027     walk_data.before_dom_children_walk_stmts = rewrite_update_stmt;
2028   else
2029     gcc_unreachable ();
2030
2031   if (what == REWRITE_ALL)
2032     walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
2033   else if (what == REWRITE_UPDATE)
2034     walk_data.before_dom_children_after_stmts = rewrite_update_phi_arguments;
2035   else
2036     gcc_unreachable ();
2037   
2038   if (what == REWRITE_ALL)
2039     walk_data.after_dom_children_after_stmts =  rewrite_finalize_block;
2040   else if (what == REWRITE_UPDATE)
2041     walk_data.after_dom_children_after_stmts = rewrite_update_fini_block;
2042   else
2043     gcc_unreachable ();
2044
2045   block_defs_stack = VEC_alloc (tree, heap, 10);
2046
2047   /* Initialize the dominator walker.  */
2048   init_walk_dominator_tree (&walk_data);
2049
2050   /* Recursively walk the dominator tree rewriting each statement in
2051      each basic block.  */
2052   walk_dominator_tree (&walk_data, entry);
2053
2054   /* Finalize the dominator walker.  */
2055   fini_walk_dominator_tree (&walk_data);
2056
2057   /* Debugging dumps.  */
2058   if (dump_file && (dump_flags & TDF_STATS))
2059     {
2060       dump_dfa_stats (dump_file);
2061       if (def_blocks)
2062         dump_tree_ssa_stats (dump_file);
2063     }
2064   
2065   VEC_free (tree, heap, block_defs_stack);
2066
2067   timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
2068 }
2069
2070
2071 /* Block initialization routine for mark_def_sites.  Clear the 
2072    KILLS bitmap at the start of each block.  */
2073
2074 static void
2075 mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
2076                                  basic_block bb ATTRIBUTE_UNUSED)
2077 {
2078   struct mark_def_sites_global_data *gd;
2079   gd = (struct mark_def_sites_global_data *) walk_data->global_data;
2080   bitmap_clear (gd->kills);
2081 }
2082
2083
2084 /* Mark the definition site blocks for each variable, so that we know
2085    where the variable is actually live.
2086
2087    INTERESTING_BLOCKS will be filled in with all the blocks that
2088       should be processed by the renamer.  It is assumed to be
2089       initialized and zeroed by the caller.  */
2090
2091 static void
2092 mark_def_site_blocks (sbitmap interesting_blocks)
2093 {
2094   struct dom_walk_data walk_data;
2095   struct mark_def_sites_global_data mark_def_sites_global_data;
2096
2097   /* Setup callbacks for the generic dominator tree walker to find and
2098      mark definition sites.  */
2099   walk_data.walk_stmts_backward = false;
2100   walk_data.dom_direction = CDI_DOMINATORS;
2101   walk_data.initialize_block_local_data = NULL;
2102   walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block;
2103   walk_data.before_dom_children_walk_stmts = mark_def_sites;
2104   walk_data.before_dom_children_after_stmts = NULL; 
2105   walk_data.after_dom_children_before_stmts =  NULL;
2106   walk_data.after_dom_children_walk_stmts =  NULL;
2107   walk_data.after_dom_children_after_stmts =  NULL;
2108   walk_data.interesting_blocks = NULL;
2109
2110   /* Notice that this bitmap is indexed using variable UIDs, so it must be
2111      large enough to accommodate all the variables referenced in the
2112      function, not just the ones we are renaming.  */
2113   mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
2114
2115   /* Create the set of interesting blocks that will be filled by
2116      mark_def_sites.  */
2117   mark_def_sites_global_data.interesting_blocks = interesting_blocks;
2118   walk_data.global_data = &mark_def_sites_global_data;
2119
2120   /* We do not have any local data.  */
2121   walk_data.block_local_data_size = 0;
2122
2123   /* Initialize the dominator walker.  */
2124   init_walk_dominator_tree (&walk_data);
2125
2126   /* Recursively walk the dominator tree.  */
2127   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
2128
2129   /* Finalize the dominator walker.  */
2130   fini_walk_dominator_tree (&walk_data);
2131
2132   /* We no longer need this bitmap, clear and free it.  */
2133   BITMAP_FREE (mark_def_sites_global_data.kills);
2134 }
2135
2136
2137 /* Initialize internal data needed during renaming.  */
2138
2139 static void
2140 init_ssa_renamer (void)
2141 {
2142   tree var;
2143   referenced_var_iterator rvi;
2144
2145   cfun->gimple_df->in_ssa_p = false;
2146
2147   /* Allocate memory for the DEF_BLOCKS hash table.  */
2148   gcc_assert (def_blocks == NULL);
2149   def_blocks = htab_create (num_referenced_vars, def_blocks_hash,
2150                             def_blocks_eq, def_blocks_free);
2151
2152   FOR_EACH_REFERENCED_VAR(var, rvi)
2153     set_current_def (var, NULL_TREE);
2154 }
2155
2156
2157 /* Deallocate internal data structures used by the renamer.  */
2158
2159 static void
2160 fini_ssa_renamer (void)
2161 {
2162   if (def_blocks)
2163     {
2164       htab_delete (def_blocks);
2165       def_blocks = NULL;
2166     }
2167
2168   cfun->gimple_df->in_ssa_p = true;
2169 }
2170
2171
2172 /* Main entry point into the SSA builder.  The renaming process
2173    proceeds in four main phases:
2174
2175    1- Compute dominance frontier and immediate dominators, needed to
2176       insert PHI nodes and rename the function in dominator tree
2177       order.
2178
2179    2- Find and mark all the blocks that define variables
2180       (mark_def_site_blocks).
2181
2182    3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2183
2184    4- Rename all the blocks (rewrite_blocks) and statements in the program.
2185
2186    Steps 3 and 4 are done using the dominator tree walker
2187    (walk_dominator_tree).  */
2188
2189 static unsigned int
2190 rewrite_into_ssa (void)
2191 {
2192   bitmap *dfs;
2193   basic_block bb;
2194   sbitmap interesting_blocks;
2195   
2196   timevar_push (TV_TREE_SSA_OTHER);
2197
2198   /* Initialize operand data structures.  */
2199   init_ssa_operands ();
2200
2201   /* Initialize internal data needed by the renamer.  */
2202   init_ssa_renamer ();
2203
2204   /* Initialize the set of interesting blocks.  The callback
2205      mark_def_sites will add to this set those blocks that the renamer
2206      should process.  */
2207   interesting_blocks = sbitmap_alloc (last_basic_block);
2208   sbitmap_zero (interesting_blocks);
2209
2210   /* Initialize dominance frontier.  */
2211   dfs = XNEWVEC (bitmap, last_basic_block);
2212   FOR_EACH_BB (bb)
2213     dfs[bb->index] = BITMAP_ALLOC (NULL);
2214
2215   /* 1- Compute dominance frontiers.  */
2216   calculate_dominance_info (CDI_DOMINATORS);
2217   compute_dominance_frontiers (dfs);
2218
2219   /* 2- Find and mark definition sites.  */
2220   mark_def_site_blocks (interesting_blocks);
2221
2222   /* 3- Insert PHI nodes at dominance frontiers of definition blocks.  */
2223   insert_phi_nodes (dfs);
2224
2225   /* 4- Rename all the blocks.  */
2226   rewrite_blocks (ENTRY_BLOCK_PTR, REWRITE_ALL, interesting_blocks);
2227
2228   /* Free allocated memory.  */
2229   FOR_EACH_BB (bb)
2230     BITMAP_FREE (dfs[bb->index]);
2231   free (dfs);
2232   sbitmap_free (interesting_blocks);
2233
2234   fini_ssa_renamer ();
2235
2236   timevar_pop (TV_TREE_SSA_OTHER);
2237   return 0;
2238 }
2239
2240
2241 struct gimple_opt_pass pass_build_ssa = 
2242 {
2243  {
2244   GIMPLE_PASS,
2245   "ssa",                                /* name */
2246   NULL,                                 /* gate */
2247   rewrite_into_ssa,                     /* execute */
2248   NULL,                                 /* sub */
2249   NULL,                                 /* next */
2250   0,                                    /* static_pass_number */
2251   0,                                    /* tv_id */
2252   PROP_cfg | PROP_referenced_vars,      /* properties_required */
2253   PROP_ssa,                             /* properties_provided */
2254   0,                                    /* properties_destroyed */
2255   0,                                    /* todo_flags_start */
2256   TODO_dump_func
2257     | TODO_verify_ssa
2258     | TODO_remove_unused_locals         /* todo_flags_finish */
2259  }
2260 };
2261
2262
2263 /* Mark the definition of VAR at STMT and BB as interesting for the
2264    renamer.  BLOCKS is the set of blocks that need updating.  */
2265
2266 static void
2267 mark_def_interesting (tree var, tree stmt, basic_block bb, bool insert_phi_p)
2268 {
2269   gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
2270   REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
2271
2272   if (insert_phi_p)
2273     {
2274       bool is_phi_p = TREE_CODE (stmt) == PHI_NODE;
2275
2276       set_def_block (var, bb, is_phi_p);
2277
2278       /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2279          site for both itself and all the old names replaced by it.  */
2280       if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
2281         {
2282           bitmap_iterator bi;
2283           unsigned i;
2284           bitmap set = names_replaced_by (var);
2285           if (set)
2286             EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2287               set_def_block (ssa_name (i), bb, is_phi_p);
2288         }
2289     }
2290 }
2291
2292
2293 /* Mark the use of VAR at STMT and BB as interesting for the
2294    renamer.  INSERT_PHI_P is true if we are going to insert new PHI
2295    nodes.  */
2296
2297 static inline void
2298 mark_use_interesting (tree var, tree stmt, basic_block bb, bool insert_phi_p)
2299 {
2300   basic_block def_bb = bb_for_stmt (stmt);
2301
2302   mark_block_for_update (def_bb);
2303   mark_block_for_update (bb);
2304
2305   if (TREE_CODE (stmt) == PHI_NODE)
2306     mark_phi_for_rewrite (def_bb, stmt);
2307   else
2308     REWRITE_THIS_STMT (stmt) = 1;
2309
2310   /* If VAR has not been defined in BB, then it is live-on-entry
2311      to BB.  Note that we cannot just use the block holding VAR's
2312      definition because if VAR is one of the names in OLD_SSA_NAMES,
2313      it will have several definitions (itself and all the names that
2314      replace it).  */
2315   if (insert_phi_p)
2316     {
2317       struct def_blocks_d *db_p = get_def_blocks_for (var);
2318       if (!bitmap_bit_p (db_p->def_blocks, bb->index))
2319         set_livein_block (var, bb);
2320     }
2321 }
2322
2323
2324 /* Do a dominator walk starting at BB processing statements that
2325    reference symbols in SYMS_TO_RENAME.  This is very similar to
2326    mark_def_sites, but the scan handles statements whose operands may
2327    already be SSA names.
2328
2329    If INSERT_PHI_P is true, mark those uses as live in the
2330    corresponding block.  This is later used by the PHI placement
2331    algorithm to make PHI pruning decisions.
2332
2333    FIXME.  Most of this would be unnecessary if we could associate a
2334            symbol to all the SSA names that reference it.  But that
2335            sounds like it would be expensive to maintain.  Still, it
2336            would be interesting to see if it makes better sense to do
2337            that.  */
2338
2339 static void
2340 prepare_block_for_update (basic_block bb, bool insert_phi_p)
2341 {
2342   basic_block son;
2343   block_stmt_iterator si;
2344   tree phi;
2345   edge e;
2346   edge_iterator ei;
2347
2348   mark_block_for_update (bb);
2349
2350   /* Process PHI nodes marking interesting those that define or use
2351      the symbols that we are interested in.  */
2352   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2353     {
2354       tree lhs_sym, lhs = PHI_RESULT (phi);
2355
2356       lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
2357
2358       if (!symbol_marked_for_renaming (lhs_sym))
2359         continue;
2360       mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
2361
2362       /* Mark the uses in phi nodes as interesting.  It would be more correct
2363          to process the arguments of the phi nodes of the successor edges of
2364          BB at the end of prepare_block_for_update, however, that turns out
2365          to be significantly more expensive.  Doing it here is conservatively
2366          correct -- it may only cause us to believe a value to be live in a
2367          block that also contains its definition, and thus insert a few more
2368          phi nodes for it.  */
2369       FOR_EACH_EDGE (e, ei, bb->preds)
2370         {
2371           mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
2372         }
2373     }
2374
2375   /* Process the statements.  */
2376   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2377     {
2378       tree stmt;
2379       ssa_op_iter i;
2380       use_operand_p use_p;
2381       def_operand_p def_p;
2382       
2383       stmt = bsi_stmt (si);
2384
2385       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_ALL_USES)
2386         {
2387           tree use = USE_FROM_PTR (use_p);
2388           tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
2389           if (symbol_marked_for_renaming (sym))
2390             mark_use_interesting (sym, stmt, bb, insert_phi_p);
2391         }
2392
2393       FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_ALL_DEFS)
2394         {
2395           tree def = DEF_FROM_PTR (def_p);
2396           tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
2397           if (symbol_marked_for_renaming (sym))
2398             mark_def_interesting (sym, stmt, bb, insert_phi_p);
2399         }
2400     }
2401
2402   /* Now visit all the blocks dominated by BB.  */
2403   for (son = first_dom_son (CDI_DOMINATORS, bb);
2404        son;
2405        son = next_dom_son (CDI_DOMINATORS, son))
2406     prepare_block_for_update (son, insert_phi_p);
2407 }
2408
2409
2410 /* Helper for prepare_names_to_update.  Mark all the use sites for
2411    NAME as interesting.  BLOCKS and INSERT_PHI_P are as in
2412    prepare_names_to_update.  */
2413
2414 static void
2415 prepare_use_sites_for (tree name, bool insert_phi_p)
2416 {
2417   use_operand_p use_p;
2418   imm_use_iterator iter;
2419
2420   FOR_EACH_IMM_USE_FAST (use_p, iter, name)
2421     {
2422       tree stmt = USE_STMT (use_p);
2423       basic_block bb = bb_for_stmt (stmt);
2424
2425       if (TREE_CODE (stmt) == PHI_NODE)
2426         {
2427           int ix = PHI_ARG_INDEX_FROM_USE (use_p);
2428           edge e = PHI_ARG_EDGE (stmt, ix);
2429           mark_use_interesting (name, stmt, e->src, insert_phi_p);
2430         }
2431       else
2432         {
2433           /* For regular statements, mark this as an interesting use
2434              for NAME.  */
2435           mark_use_interesting (name, stmt, bb, insert_phi_p);
2436         }
2437     }
2438 }
2439
2440
2441 /* Helper for prepare_names_to_update.  Mark the definition site for
2442    NAME as interesting.  BLOCKS and INSERT_PHI_P are as in
2443    prepare_names_to_update.  */
2444
2445 static void
2446 prepare_def_site_for (tree name, bool insert_phi_p)
2447 {
2448   tree stmt;
2449   basic_block bb;
2450
2451   gcc_assert (names_to_release == NULL
2452               || !bitmap_bit_p (names_to_release, SSA_NAME_VERSION (name)));
2453
2454   stmt = SSA_NAME_DEF_STMT (name);
2455   bb = bb_for_stmt (stmt);
2456   if (bb)
2457     {
2458       gcc_assert (bb->index < last_basic_block);
2459       mark_block_for_update (bb);
2460       mark_def_interesting (name, stmt, bb, insert_phi_p);
2461     }
2462 }
2463
2464
2465 /* Mark definition and use sites of names in NEW_SSA_NAMES and
2466    OLD_SSA_NAMES.  INSERT_PHI_P is true if the caller wants to insert
2467    PHI nodes for newly created names.  */
2468
2469 static void
2470 prepare_names_to_update (bool insert_phi_p)
2471 {
2472   unsigned i = 0;
2473   bitmap_iterator bi;
2474   sbitmap_iterator sbi;
2475
2476   /* If a name N from NEW_SSA_NAMES is also marked to be released,
2477      remove it from NEW_SSA_NAMES so that we don't try to visit its
2478      defining basic block (which most likely doesn't exist).  Notice
2479      that we cannot do the same with names in OLD_SSA_NAMES because we
2480      want to replace existing instances.  */
2481   if (names_to_release)
2482     EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2483       RESET_BIT (new_ssa_names, i);
2484
2485   /* First process names in NEW_SSA_NAMES.  Otherwise, uses of old
2486      names may be considered to be live-in on blocks that contain
2487      definitions for their replacements.  */
2488   EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
2489     prepare_def_site_for (ssa_name (i), insert_phi_p);
2490
2491   /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2492      OLD_SSA_NAMES, but we have to ignore its definition site.  */
2493   EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
2494     {
2495       if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
2496         prepare_def_site_for (ssa_name (i), insert_phi_p);
2497       prepare_use_sites_for (ssa_name (i), insert_phi_p);
2498     }
2499 }
2500
2501
2502 /* Dump all the names replaced by NAME to FILE.  */
2503
2504 void
2505 dump_names_replaced_by (FILE *file, tree name)
2506 {
2507   unsigned i;
2508   bitmap old_set;
2509   bitmap_iterator bi;
2510
2511   print_generic_expr (file, name, 0);
2512   fprintf (file, " -> { ");
2513
2514   old_set = names_replaced_by (name);
2515   EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
2516     {
2517       print_generic_expr (file, ssa_name (i), 0);
2518       fprintf (file, " ");
2519     }
2520
2521   fprintf (file, "}\n");
2522 }
2523
2524
2525 /* Dump all the names replaced by NAME to stderr.  */
2526
2527 void
2528 debug_names_replaced_by (tree name)
2529 {
2530   dump_names_replaced_by (stderr, name);
2531 }
2532
2533
2534 /* Dump SSA update information to FILE.  */
2535
2536 void
2537 dump_update_ssa (FILE *file)
2538 {
2539   unsigned i = 0;
2540   bitmap_iterator bi;
2541
2542   if (!need_ssa_update_p ())
2543     return;
2544
2545   if (new_ssa_names && sbitmap_first_set_bit (new_ssa_names) >= 0)
2546     {
2547       sbitmap_iterator sbi;
2548
2549       fprintf (file, "\nSSA replacement table\n");
2550       fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
2551                      "O_1, ..., O_j\n\n");
2552
2553       EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
2554         dump_names_replaced_by (file, ssa_name (i));
2555
2556       fprintf (file, "\n");
2557       fprintf (file, "Number of virtual NEW -> OLD mappings: %7u\n",
2558                update_ssa_stats.num_virtual_mappings);
2559       fprintf (file, "Number of real NEW -> OLD mappings:    %7u\n",
2560                update_ssa_stats.num_total_mappings
2561                - update_ssa_stats.num_virtual_mappings);
2562       fprintf (file, "Number of total NEW -> OLD mappings:   %7u\n",
2563                update_ssa_stats.num_total_mappings);
2564
2565       fprintf (file, "\nNumber of virtual symbols: %u\n",
2566                update_ssa_stats.num_virtual_symbols);
2567     }
2568
2569   if (syms_to_rename && !bitmap_empty_p (syms_to_rename))
2570     {
2571       fprintf (file, "\n\nSymbols to be put in SSA form\n\n");
2572       dump_decl_set (file, syms_to_rename);
2573     }
2574
2575   if (names_to_release && !bitmap_empty_p (names_to_release))
2576     {
2577       fprintf (file, "\n\nSSA names to release after updating the SSA web\n\n");
2578       EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2579         {
2580           print_generic_expr (file, ssa_name (i), 0);
2581           fprintf (file, " ");
2582         }
2583     }
2584
2585   fprintf (file, "\n\n");
2586 }
2587
2588
2589 /* Dump SSA update information to stderr.  */
2590
2591 void
2592 debug_update_ssa (void)
2593 {
2594   dump_update_ssa (stderr);
2595 }
2596
2597
2598 /* Initialize data structures used for incremental SSA updates.  */
2599
2600 static void
2601 init_update_ssa (void)
2602 {
2603   /* Reserve more space than the current number of names.  The calls to
2604      add_new_name_mapping are typically done after creating new SSA
2605      names, so we'll need to reallocate these arrays.  */
2606   old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2607   sbitmap_zero (old_ssa_names);
2608
2609   new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2610   sbitmap_zero (new_ssa_names);
2611
2612   repl_tbl = htab_create (20, repl_map_hash, repl_map_eq, repl_map_free);
2613   need_to_initialize_update_ssa_p = false;
2614   need_to_update_vops_p = false;
2615   syms_to_rename = BITMAP_ALLOC (NULL);
2616   regs_to_rename = BITMAP_ALLOC (NULL);
2617   mem_syms_to_rename = BITMAP_ALLOC (NULL);
2618   names_to_release = NULL;
2619   memset (&update_ssa_stats, 0, sizeof (update_ssa_stats));
2620   update_ssa_stats.virtual_symbols = BITMAP_ALLOC (NULL);
2621 }
2622
2623
2624 /* Deallocate data structures used for incremental SSA updates.  */
2625
2626 void
2627 delete_update_ssa (void)
2628 {
2629   unsigned i;
2630   bitmap_iterator bi;
2631
2632   sbitmap_free (old_ssa_names);
2633   old_ssa_names = NULL;
2634
2635   sbitmap_free (new_ssa_names);
2636   new_ssa_names = NULL;
2637
2638   htab_delete (repl_tbl);
2639   repl_tbl = NULL;
2640
2641   need_to_initialize_update_ssa_p = true;
2642   need_to_update_vops_p = false;
2643   BITMAP_FREE (syms_to_rename);
2644   BITMAP_FREE (regs_to_rename);
2645   BITMAP_FREE (mem_syms_to_rename);
2646   BITMAP_FREE (update_ssa_stats.virtual_symbols);
2647
2648   if (names_to_release)
2649     {
2650       EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2651         release_ssa_name (ssa_name (i));
2652       BITMAP_FREE (names_to_release);
2653     }
2654
2655   clear_ssa_name_info ();
2656
2657   fini_ssa_renamer ();
2658
2659   if (blocks_with_phis_to_rewrite)
2660     EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
2661       {
2662         tree_vec phis = VEC_index (tree_vec, phis_to_rewrite, i);
2663
2664         VEC_free (tree, heap, phis);
2665         VEC_replace (tree_vec, phis_to_rewrite, i, NULL);
2666       }
2667
2668   BITMAP_FREE (blocks_with_phis_to_rewrite);
2669   BITMAP_FREE (blocks_to_update);
2670 }
2671
2672
2673 /* Create a new name for OLD_NAME in statement STMT and replace the
2674    operand pointed to by DEF_P with the newly created name.  Return
2675    the new name and register the replacement mapping <NEW, OLD> in
2676    update_ssa's tables.  */
2677
2678 tree
2679 create_new_def_for (tree old_name, tree stmt, def_operand_p def)
2680 {
2681   tree new_name = duplicate_ssa_name (old_name, stmt);
2682
2683   SET_DEF (def, new_name);
2684
2685   if (TREE_CODE (stmt) == PHI_NODE)
2686     {
2687       edge e;
2688       edge_iterator ei;
2689       basic_block bb = bb_for_stmt (stmt);
2690
2691       /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2692       FOR_EACH_EDGE (e, ei, bb->preds)
2693         if (e->flags & EDGE_ABNORMAL)
2694           {
2695             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
2696             break;
2697           }
2698     }
2699
2700   register_new_name_mapping (new_name, old_name);
2701
2702   /* For the benefit of passes that will be updating the SSA form on
2703      their own, set the current reaching definition of OLD_NAME to be
2704      NEW_NAME.  */
2705   set_current_def (old_name, new_name);
2706
2707   return new_name;
2708 }
2709
2710
2711 /* Register name NEW to be a replacement for name OLD.  This function
2712    must be called for every replacement that should be performed by
2713    update_ssa.  */
2714
2715 void
2716 register_new_name_mapping (tree new, tree old)
2717 {
2718   if (need_to_initialize_update_ssa_p)
2719     init_update_ssa ();
2720
2721   add_new_name_mapping (new, old);
2722 }
2723
2724
2725 /* Register symbol SYM to be renamed by update_ssa.  */
2726
2727 void
2728 mark_sym_for_renaming (tree sym)
2729 {
2730   if (need_to_initialize_update_ssa_p)
2731     init_update_ssa ();
2732
2733   bitmap_set_bit (syms_to_rename, DECL_UID (sym));
2734
2735   if (!is_gimple_reg (sym))
2736     {
2737       need_to_update_vops_p = true;
2738       if (memory_partition (sym))
2739         bitmap_set_bit (syms_to_rename, DECL_UID (memory_partition (sym)));
2740     }
2741 }
2742
2743
2744 /* Register all the symbols in SET to be renamed by update_ssa.  */
2745
2746 void
2747 mark_set_for_renaming (bitmap set)
2748 {
2749   bitmap_iterator bi;
2750   unsigned i;
2751
2752   if (set == NULL || bitmap_empty_p (set))
2753     return;
2754
2755   if (need_to_initialize_update_ssa_p)
2756     init_update_ssa ();
2757
2758   EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2759     mark_sym_for_renaming (referenced_var (i));
2760 }
2761
2762
2763 /* Return true if there is any work to be done by update_ssa.  */
2764
2765 bool
2766 need_ssa_update_p (void)
2767 {
2768   return syms_to_rename || old_ssa_names || new_ssa_names;
2769 }
2770
2771 /* Return true if SSA name mappings have been registered for SSA updating.  */
2772
2773 bool
2774 name_mappings_registered_p (void)
2775 {
2776   return repl_tbl && htab_elements (repl_tbl) > 0;
2777 }
2778
2779 /* Return true if name N has been registered in the replacement table.  */
2780
2781 bool
2782 name_registered_for_update_p (tree n)
2783 {
2784   if (!need_ssa_update_p ())
2785     return false;
2786
2787   return is_new_name (n)
2788          || is_old_name (n)
2789          || symbol_marked_for_renaming (SSA_NAME_VAR (n));
2790 }
2791
2792
2793 /* Return the set of all the SSA names marked to be replaced.  */
2794
2795 bitmap
2796 ssa_names_to_replace (void)
2797 {
2798   unsigned i = 0;
2799   bitmap ret;
2800   sbitmap_iterator sbi;
2801   
2802   ret = BITMAP_ALLOC (NULL);
2803   EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
2804     bitmap_set_bit (ret, i);
2805
2806   return ret;
2807 }
2808
2809
2810 /* Mark NAME to be released after update_ssa has finished.  */
2811
2812 void
2813 release_ssa_name_after_update_ssa (tree name)
2814 {
2815   gcc_assert (!need_to_initialize_update_ssa_p);
2816
2817   if (names_to_release == NULL)
2818     names_to_release = BITMAP_ALLOC (NULL);
2819
2820   bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
2821 }
2822
2823
2824 /* Insert new PHI nodes to replace VAR.  DFS contains dominance
2825    frontier information.  BLOCKS is the set of blocks to be updated.
2826
2827    This is slightly different than the regular PHI insertion
2828    algorithm.  The value of UPDATE_FLAGS controls how PHI nodes for
2829    real names (i.e., GIMPLE registers) are inserted:
2830  
2831    - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
2832      nodes inside the region affected by the block that defines VAR
2833      and the blocks that define all its replacements.  All these
2834      definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
2835
2836      First, we compute the entry point to the region (ENTRY).  This is
2837      given by the nearest common dominator to all the definition
2838      blocks. When computing the iterated dominance frontier (IDF), any
2839      block not strictly dominated by ENTRY is ignored.
2840
2841      We then call the standard PHI insertion algorithm with the pruned
2842      IDF.
2843
2844    - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
2845      names is not pruned.  PHI nodes are inserted at every IDF block.  */
2846
2847 static void
2848 insert_updated_phi_nodes_for (tree var, bitmap *dfs, bitmap blocks,
2849                               unsigned update_flags)
2850 {
2851   basic_block entry;
2852   struct def_blocks_d *db;
2853   bitmap idf, pruned_idf;
2854   bitmap_iterator bi;
2855   unsigned i;
2856
2857 #if defined ENABLE_CHECKING
2858   if (TREE_CODE (var) == SSA_NAME)
2859     gcc_assert (is_old_name (var));
2860   else
2861     gcc_assert (symbol_marked_for_renaming (var));
2862 #endif
2863
2864   /* Get all the definition sites for VAR.  */
2865   db = find_def_blocks_for (var);
2866
2867   /* No need to do anything if there were no definitions to VAR.  */
2868   if (db == NULL || bitmap_empty_p (db->def_blocks))
2869     return;
2870
2871   /* Compute the initial iterated dominance frontier.  */
2872   idf = compute_idf (db->def_blocks, dfs);
2873   pruned_idf = BITMAP_ALLOC (NULL);
2874
2875   if (TREE_CODE (var) == SSA_NAME)
2876     {
2877       if (update_flags == TODO_update_ssa)
2878         {
2879           /* If doing regular SSA updates for GIMPLE registers, we are
2880              only interested in IDF blocks dominated by the nearest
2881              common dominator of all the definition blocks.  */
2882           entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
2883                                                     db->def_blocks);
2884           if (entry != ENTRY_BLOCK_PTR)
2885             EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
2886               if (BASIC_BLOCK (i) != entry
2887                   && dominated_by_p (CDI_DOMINATORS, BASIC_BLOCK (i), entry))
2888                 bitmap_set_bit (pruned_idf, i);
2889         }
2890       else
2891         {
2892           /* Otherwise, do not prune the IDF for VAR.  */
2893           gcc_assert (update_flags == TODO_update_ssa_full_phi);
2894           bitmap_copy (pruned_idf, idf);
2895         }
2896     }
2897   else
2898     {
2899       /* Otherwise, VAR is a symbol that needs to be put into SSA form
2900          for the first time, so we need to compute the full IDF for
2901          it.  */
2902       bitmap_copy (pruned_idf, idf);
2903     }
2904
2905   if (!bitmap_empty_p (pruned_idf))
2906     {
2907       /* Make sure that PRUNED_IDF blocks and all their feeding blocks
2908          are included in the region to be updated.  The feeding blocks
2909          are important to guarantee that the PHI arguments are renamed
2910          properly.  */
2911
2912       /* FIXME, this is not needed if we are updating symbols.  We are
2913          already starting at the ENTRY block anyway.  */
2914       bitmap_ior_into (blocks, pruned_idf);
2915       EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
2916         {
2917           edge e;
2918           edge_iterator ei;
2919           basic_block bb = BASIC_BLOCK (i);
2920
2921           FOR_EACH_EDGE (e, ei, bb->preds)
2922             if (e->src->index >= 0)
2923               bitmap_set_bit (blocks, e->src->index);
2924         }
2925
2926       insert_phi_nodes_for (var, pruned_idf, true);
2927     }
2928
2929   BITMAP_FREE (pruned_idf);
2930   BITMAP_FREE (idf);
2931 }
2932
2933
2934 /* Heuristic to determine whether SSA name mappings for virtual names
2935    should be discarded and their symbols rewritten from scratch.  When
2936    there is a large number of mappings for virtual names, the
2937    insertion of PHI nodes for the old names in the mappings takes
2938    considerable more time than if we inserted PHI nodes for the
2939    symbols instead.
2940
2941    Currently the heuristic takes these stats into account:
2942
2943         - Number of mappings for virtual SSA names.
2944         - Number of distinct virtual symbols involved in those mappings.
2945
2946    If the number of virtual mappings is much larger than the number of
2947    virtual symbols, then it will be faster to compute PHI insertion
2948    spots for the symbols.  Even if this involves traversing the whole
2949    CFG, which is what happens when symbols are renamed from scratch.  */
2950
2951 static bool
2952 switch_virtuals_to_full_rewrite_p (void)
2953 {
2954   if (update_ssa_stats.num_virtual_mappings < (unsigned) MIN_VIRTUAL_MAPPINGS)
2955     return false;
2956
2957   if (update_ssa_stats.num_virtual_mappings
2958       > (unsigned) VIRTUAL_MAPPINGS_TO_SYMS_RATIO
2959         * update_ssa_stats.num_virtual_symbols)
2960     return true;
2961
2962   return false;
2963 }
2964
2965
2966 /* Remove every virtual mapping and mark all the affected virtual
2967    symbols for renaming.  */
2968
2969 static void
2970 switch_virtuals_to_full_rewrite (void)
2971 {
2972   unsigned i = 0;
2973   sbitmap_iterator sbi;
2974
2975   if (dump_file)
2976     {
2977       fprintf (dump_file, "\nEnabled virtual name mapping heuristic.\n");
2978       fprintf (dump_file, "\tNumber of virtual mappings:       %7u\n",
2979                update_ssa_stats.num_virtual_mappings);
2980       fprintf (dump_file, "\tNumber of unique virtual symbols: %7u\n",
2981                update_ssa_stats.num_virtual_symbols);
2982       fprintf (dump_file, "Updating FUD-chains from top of CFG will be "
2983                           "faster than processing\nthe name mappings.\n\n");
2984     }
2985
2986   /* Remove all virtual names from NEW_SSA_NAMES and OLD_SSA_NAMES.
2987      Note that it is not really necessary to remove the mappings from
2988      REPL_TBL, that would only waste time.  */
2989   EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
2990     if (!is_gimple_reg (ssa_name (i)))
2991       RESET_BIT (new_ssa_names, i);
2992
2993   EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
2994     if (!is_gimple_reg (ssa_name (i)))
2995       RESET_BIT (old_ssa_names, i);
2996
2997   mark_set_for_renaming (update_ssa_stats.virtual_symbols);
2998 }
2999
3000
3001 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3002    existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3003
3004    1- The names in OLD_SSA_NAMES dominated by the definitions of
3005       NEW_SSA_NAMES are all re-written to be reached by the
3006       appropriate definition from NEW_SSA_NAMES.
3007
3008    2- If needed, new PHI nodes are added to the iterated dominance
3009       frontier of the blocks where each of NEW_SSA_NAMES are defined.
3010
3011    The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3012    calling register_new_name_mapping for every pair of names that the
3013    caller wants to replace.
3014
3015    The caller identifies the new names that have been inserted and the
3016    names that need to be replaced by calling register_new_name_mapping
3017    for every pair <NEW, OLD>.  Note that the function assumes that the
3018    new names have already been inserted in the IL.
3019
3020    For instance, given the following code:
3021
3022      1  L0:
3023      2  x_1 = PHI (0, x_5)
3024      3  if (x_1 < 10)
3025      4    if (x_1 > 7)
3026      5      y_2 = 0
3027      6    else
3028      7      y_3 = x_1 + x_7
3029      8    endif
3030      9    x_5 = x_1 + 1
3031      10   goto L0;
3032      11 endif
3033
3034    Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3035
3036      1  L0:
3037      2  x_1 = PHI (0, x_5)
3038      3  if (x_1 < 10)
3039      4    x_10 = ...
3040      5    if (x_1 > 7)
3041      6      y_2 = 0
3042      7    else
3043      8      x_11 = ...
3044      9      y_3 = x_1 + x_7
3045      10   endif
3046      11   x_5 = x_1 + 1
3047      12   goto L0;
3048      13 endif
3049
3050    We want to replace all the uses of x_1 with the new definitions of
3051    x_10 and x_11.  Note that the only uses that should be replaced are
3052    those at lines 5, 9 and 11.  Also, the use of x_7 at line 9 should
3053    *not* be replaced (this is why we cannot just mark symbol 'x' for
3054    renaming).
3055
3056    Additionally, we may need to insert a PHI node at line 11 because
3057    that is a merge point for x_10 and x_11.  So the use of x_1 at line
3058    11 will be replaced with the new PHI node.  The insertion of PHI
3059    nodes is optional.  They are not strictly necessary to preserve the
3060    SSA form, and depending on what the caller inserted, they may not
3061    even be useful for the optimizers.  UPDATE_FLAGS controls various
3062    aspects of how update_ssa operates, see the documentation for
3063    TODO_update_ssa*.  */
3064
3065 void
3066 update_ssa (unsigned update_flags)
3067 {
3068   basic_block bb, start_bb;
3069   bitmap_iterator bi;
3070   unsigned i = 0;
3071   sbitmap tmp;
3072   bool insert_phi_p;
3073   sbitmap_iterator sbi;
3074
3075   if (!need_ssa_update_p ())
3076     return;
3077
3078   timevar_push (TV_TREE_SSA_INCREMENTAL);
3079
3080   blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
3081   if (!phis_to_rewrite)
3082     phis_to_rewrite = VEC_alloc (tree_vec, heap, last_basic_block);
3083   blocks_to_update = BITMAP_ALLOC (NULL);
3084
3085   /* Ensure that the dominance information is up-to-date.  */
3086   calculate_dominance_info (CDI_DOMINATORS);
3087
3088   /* Only one update flag should be set.  */
3089   gcc_assert (update_flags == TODO_update_ssa
3090               || update_flags == TODO_update_ssa_no_phi
3091               || update_flags == TODO_update_ssa_full_phi
3092               || update_flags == TODO_update_ssa_only_virtuals);
3093
3094   /* If we only need to update virtuals, remove all the mappings for
3095      real names before proceeding.  The caller is responsible for
3096      having dealt with the name mappings before calling update_ssa.  */
3097   if (update_flags == TODO_update_ssa_only_virtuals)
3098     {
3099       sbitmap_zero (old_ssa_names);
3100       sbitmap_zero (new_ssa_names);
3101       htab_empty (repl_tbl);
3102     }
3103
3104   insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
3105
3106   if (insert_phi_p)
3107     {
3108       /* If the caller requested PHI nodes to be added, initialize
3109          live-in information data structures (DEF_BLOCKS).  */
3110
3111       /* For each SSA name N, the DEF_BLOCKS table describes where the
3112          name is defined, which blocks have PHI nodes for N, and which
3113          blocks have uses of N (i.e., N is live-on-entry in those
3114          blocks).  */
3115       def_blocks = htab_create (num_ssa_names, def_blocks_hash,
3116                                 def_blocks_eq, def_blocks_free);
3117     }
3118   else
3119     {
3120       def_blocks = NULL;
3121     }
3122
3123   /* Heuristic to avoid massive slow downs when the replacement
3124      mappings include lots of virtual names.  */
3125   if (insert_phi_p && switch_virtuals_to_full_rewrite_p ())
3126     switch_virtuals_to_full_rewrite ();
3127
3128   /* If there are symbols to rename, identify those symbols that are
3129      GIMPLE registers into the set REGS_TO_RENAME and those that are
3130      memory symbols into the set MEM_SYMS_TO_RENAME.  */
3131   if (!bitmap_empty_p (syms_to_rename))
3132     {
3133       unsigned i;
3134       bitmap_iterator bi;
3135
3136       EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
3137         {
3138           tree sym = referenced_var (i);
3139           if (is_gimple_reg (sym))
3140             bitmap_set_bit (regs_to_rename, i);
3141           else
3142             {
3143               /* Memory partitioning information may have been
3144                  computed after the symbol was marked for renaming,
3145                  if SYM is inside a partition also mark the partition
3146                  for renaming.  */
3147               tree mpt = memory_partition (sym);
3148               if (mpt)
3149                 bitmap_set_bit (syms_to_rename, DECL_UID (mpt));
3150             }
3151         }
3152
3153       /* Memory symbols are those not in REGS_TO_RENAME.  */
3154       bitmap_and_compl (mem_syms_to_rename, syms_to_rename, regs_to_rename);
3155     }
3156
3157   /* If there are names defined in the replacement table, prepare
3158      definition and use sites for all the names in NEW_SSA_NAMES and
3159      OLD_SSA_NAMES.  */
3160   if (sbitmap_first_set_bit (new_ssa_names) >= 0)
3161     {
3162       prepare_names_to_update (insert_phi_p);
3163
3164       /* If all the names in NEW_SSA_NAMES had been marked for
3165          removal, and there are no symbols to rename, then there's
3166          nothing else to do.  */
3167       if (sbitmap_first_set_bit (new_ssa_names) < 0
3168           && bitmap_empty_p (syms_to_rename))
3169         goto done;
3170     }
3171
3172   /* Next, determine the block at which to start the renaming process.  */
3173   if (!bitmap_empty_p (syms_to_rename))
3174     {
3175       /* If we have to rename some symbols from scratch, we need to
3176          start the process at the root of the CFG.  FIXME, it should
3177          be possible to determine the nearest block that had a
3178          definition for each of the symbols that are marked for
3179          updating.  For now this seems more work than it's worth.  */
3180       start_bb = ENTRY_BLOCK_PTR;
3181
3182       /* Traverse the CFG looking for existing definitions and uses of
3183          symbols in SYMS_TO_RENAME.  Mark interesting blocks and
3184          statements and set local live-in information for the PHI
3185          placement heuristics.  */
3186       prepare_block_for_update (start_bb, insert_phi_p);
3187     }
3188   else
3189     {
3190       /* Otherwise, the entry block to the region is the nearest
3191          common dominator for the blocks in BLOCKS.  */
3192       start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3193                                                    blocks_to_update);
3194     }
3195
3196   /* If requested, insert PHI nodes at the iterated dominance frontier
3197      of every block, creating new definitions for names in OLD_SSA_NAMES
3198      and for symbols in SYMS_TO_RENAME.  */
3199   if (insert_phi_p)
3200     {
3201       bitmap *dfs;
3202
3203       /* If the caller requested PHI nodes to be added, compute
3204          dominance frontiers.  */
3205       dfs = XNEWVEC (bitmap, last_basic_block);
3206       FOR_EACH_BB (bb)
3207         dfs[bb->index] = BITMAP_ALLOC (NULL);
3208       compute_dominance_frontiers (dfs);
3209
3210       if (sbitmap_first_set_bit (old_ssa_names) >= 0)
3211         {
3212           sbitmap_iterator sbi;
3213
3214           /* insert_update_phi_nodes_for will call add_new_name_mapping
3215              when inserting new PHI nodes, so the set OLD_SSA_NAMES
3216              will grow while we are traversing it (but it will not
3217              gain any new members).  Copy OLD_SSA_NAMES to a temporary
3218              for traversal.  */
3219           sbitmap tmp = sbitmap_alloc (old_ssa_names->n_bits);
3220           sbitmap_copy (tmp, old_ssa_names);
3221           EXECUTE_IF_SET_IN_SBITMAP (tmp, 0, i, sbi)
3222             insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
3223                                           update_flags);
3224           sbitmap_free (tmp);
3225         }
3226
3227       EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
3228         insert_updated_phi_nodes_for (referenced_var (i), dfs, blocks_to_update,
3229                                       update_flags);
3230
3231       FOR_EACH_BB (bb)
3232         BITMAP_FREE (dfs[bb->index]);
3233       free (dfs);
3234
3235       /* Insertion of PHI nodes may have added blocks to the region.
3236          We need to re-compute START_BB to include the newly added
3237          blocks.  */
3238       if (start_bb != ENTRY_BLOCK_PTR)
3239         start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3240                                                      blocks_to_update);
3241     }
3242
3243   /* Reset the current definition for name and symbol before renaming
3244      the sub-graph.  */
3245   EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
3246     set_current_def (ssa_name (i), NULL_TREE);
3247
3248   EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
3249     set_current_def (referenced_var (i), NULL_TREE);
3250
3251   /* Now start the renaming process at START_BB.  */
3252   tmp = sbitmap_alloc (last_basic_block);
3253   sbitmap_zero (tmp);
3254   EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3255     SET_BIT (tmp, i);
3256
3257   rewrite_blocks (start_bb, REWRITE_UPDATE, tmp);
3258
3259   sbitmap_free (tmp);
3260
3261   /* Debugging dumps.  */
3262   if (dump_file)
3263     {
3264       int c;
3265       unsigned i;
3266
3267       dump_update_ssa (dump_file);
3268
3269       fprintf (dump_file, "Incremental SSA update started at block: %d\n\n",
3270                start_bb->index);
3271
3272       c = 0;
3273       EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3274         c++;
3275       fprintf (dump_file, "Number of blocks in CFG: %d\n", last_basic_block);
3276       fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n\n",
3277                c, PERCENT (c, last_basic_block));
3278
3279       if (dump_flags & TDF_DETAILS)
3280         {
3281           fprintf (dump_file, "Affected blocks: ");
3282           EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3283             fprintf (dump_file, "%u ", i);
3284           fprintf (dump_file, "\n");
3285         }
3286
3287       fprintf (dump_file, "\n\n");
3288     }
3289
3290   /* Free allocated memory.  */
3291 done:
3292   delete_update_ssa ();
3293
3294   timevar_pop (TV_TREE_SSA_INCREMENTAL);
3295 }