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