OSDN Git Service

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