OSDN Git Service

05229470901a1a1ffeb52402cf461ca603f2e046
[pf3gnuchains/gcc-fork.git] / gcc / tree-into-ssa.c
1 /* Rewrite a program in Normal form into SSA.
2    Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3    Contributed by Diego Novillo <dnovillo@redhat.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "flags.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "langhooks.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
33 #include "output.h"
34 #include "errors.h"
35 #include "expr.h"
36 #include "function.h"
37 #include "diagnostic.h"
38 #include "bitmap.h"
39 #include "tree-flow.h"
40 #include "tree-gimple.h"
41 #include "tree-inline.h"
42 #include "varray.h"
43 #include "timevar.h"
44 #include "hashtab.h"
45 #include "tree-dump.h"
46 #include "tree-pass.h"
47 #include "cfgloop.h"
48 #include "domwalk.h"
49 #include "ggc.h"
50
51 /* This file builds the SSA form for a function as described in:
52    R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
53    Computing Static Single Assignment Form and the Control Dependence
54    Graph. ACM Transactions on Programming Languages and Systems,
55    13(4):451-490, October 1991.  */
56
57
58 /* Structure to map a variable VAR to the set of blocks that contain
59    definitions for VAR.  */
60 struct def_blocks_d
61 {
62   /* The variable.  */
63   tree var;
64
65   /* Blocks that contain definitions of VAR.  Bit I will be set if the
66      Ith block contains a definition of VAR.  */
67   bitmap def_blocks;
68
69   /* Blocks that contain a phi node for VAR.  */
70   bitmap phi_blocks;
71
72   /* Blocks where VAR is live-on-entry.  Similar semantics as
73      DEF_BLOCKS.  */
74   bitmap livein_blocks;
75 };
76
77 /* Each entry in DEF_BLOCKS contains an element of type STRUCT
78    DEF_BLOCKS_D, mapping a variable VAR to a bitmap describing all the
79    basic blocks where VAR is defined (assigned a new value).  It also
80    contains a bitmap of all the blocks where VAR is live-on-entry
81    (i.e., there is a use of VAR in block B without a preceding
82    definition in B).  The live-on-entry information is used when
83    computing PHI pruning heuristics.  */
84 static htab_t def_blocks;
85
86 /* Stack of trees used to restore the global currdefs to its original
87    state after completing rewriting of a block and its dominator children.
88
89    This vector is used in two contexts.  The first is rewriting of _DECL
90    nodes into SSA_NAMEs.  In that context it's elements have the
91    following properties:
92
93      An SSA_NAME indicates that the current definition of the underlying
94      variable should be set to the given SSA_NAME.
95                                                                                 
96      A _DECL node indicates that the underlying variable has no current
97      definition.
98                                                                                 
99      A NULL node is used to mark the last node associated with the
100      current block. 
101
102
103    This vector is also used when rewriting an SSA_NAME which has multiple
104    definition sites into multiple SSA_NAMEs.  In that context entries come
105    in pairs.
106
107      The top entry is an SSA_NAME and the top-1 entry is the
108      current value for that SSA_NAME. 
109
110      A NULL node at the top entry is used to mark the last node associated
111      with the current block.  */
112 static VEC(tree_on_heap) *block_defs_stack;
113
114 /* Basic block vectors used in this file ought to be allocated in the heap.  */
115 DEF_VEC_MALLOC_P(basic_block);
116
117 /* Global data to attach to the main dominator walk structure.  */
118 struct mark_def_sites_global_data
119 {
120   /* This sbitmap contains the variables which are set before they
121      are used in a basic block.  We keep it as a global variable
122      solely to avoid the overhead of allocating and deallocating
123      the bitmap.  */
124   bitmap kills;
125
126   /* Bitmap of names to rename.  */
127   sbitmap names_to_rename;
128 };
129
130 /* Information stored for ssa names.  */
131
132 struct ssa_name_info
133 {
134   /* This field indicates whether or not the variable may need PHI nodes.
135      See the enum's definition for more detailed information about the
136      states.  */
137   ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
138
139   /* The actual definition of the ssa name.  */
140   tree current_def;
141 };
142
143 /* Local functions.  */
144 static void rewrite_finalize_block (struct dom_walk_data *, basic_block);
145 static void rewrite_initialize_block (struct dom_walk_data *, basic_block);
146 static void rewrite_add_phi_arguments (struct dom_walk_data *, basic_block);
147 static void mark_def_sites (struct dom_walk_data *walk_data,
148                             basic_block bb, block_stmt_iterator);
149 static void mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
150                                              basic_block bb);
151 static void set_def_block (tree, basic_block, bool, bool);
152 static void set_livein_block (tree, basic_block);
153 static bool prepare_use_operand_for_rename (use_operand_p, size_t *uid_p);
154 static bool prepare_def_operand_for_rename (tree def, size_t *uid_p);
155 static void insert_phi_nodes (bitmap *, bitmap);
156 static void rewrite_stmt (struct dom_walk_data *, basic_block,
157                           block_stmt_iterator);
158 static inline void rewrite_operand (use_operand_p);
159 static void insert_phi_nodes_for (tree, bitmap *, VEC(basic_block) **);
160 static tree get_reaching_def (tree);
161 static hashval_t def_blocks_hash (const void *);
162 static int def_blocks_eq (const void *, const void *);
163 static void def_blocks_free (void *);
164 static int debug_def_blocks_r (void **, void *);
165 static inline struct def_blocks_d *get_def_blocks_for (tree);
166 static inline struct def_blocks_d *find_def_blocks_for (tree);
167 static void htab_statistics (FILE *, htab_t);
168
169 /* Use TREE_VISITED to keep track of which statements we want to
170    rename.  When renaming a subset of the variables, not all
171    statements will be processed.  This is decided in mark_def_sites.  */
172 #define REWRITE_THIS_STMT(T)    TREE_VISITED (T)
173
174
175 /* Get the information associated with NAME.  */
176
177 static inline struct ssa_name_info *
178 get_ssa_name_ann (tree name)
179 {
180   if (!SSA_NAME_AUX (name))
181     SSA_NAME_AUX (name) = xcalloc (1, sizeof (struct ssa_name_info));
182
183   return SSA_NAME_AUX (name);
184 }
185
186 /* Gets phi_state field for VAR.  */
187
188 static inline enum need_phi_state
189 get_phi_state (tree var)
190 {
191   if (TREE_CODE (var) == SSA_NAME)
192     return get_ssa_name_ann (var)->need_phi_state;
193   else
194     return var_ann (var)->need_phi_state;
195 }
196
197 /* Sets phi_state field for VAR to STATE.  */
198
199 static inline void
200 set_phi_state (tree var, enum need_phi_state state)
201 {
202   if (TREE_CODE (var) == SSA_NAME)
203     get_ssa_name_ann (var)->need_phi_state = state;
204   else
205     var_ann (var)->need_phi_state = state;
206 }
207
208 /* Return the current definition for VAR.  */
209
210 static inline tree
211 get_current_def (tree var)
212 {
213   if (TREE_CODE (var) == SSA_NAME)
214     return get_ssa_name_ann (var)->current_def;
215   else
216     return var_ann (var)->current_def;
217 }
218
219 /* Sets current definition of VAR to DEF.  */
220
221 static inline void
222 set_current_def (tree var, tree def)
223 {
224   if (TREE_CODE (var) == SSA_NAME)
225     get_ssa_name_ann (var)->current_def = def;
226   else
227     var_ann (var)->current_def = def;
228 }
229
230 /* Compute global livein information given the set of blockx where
231    an object is locally live at the start of the block (LIVEIN)
232    and the set of blocks where the object is defined (DEF_BLOCKS).
233
234    Note: This routine augments the existing local livein information
235    to include global livein (i.e., it modifies the underlying bitmap
236    for LIVEIN).  */
237
238 void
239 compute_global_livein (bitmap livein, bitmap def_blocks)
240 {
241   basic_block bb, *worklist, *tos;
242   unsigned i;
243   bitmap_iterator bi;
244
245   tos = worklist
246     = (basic_block *) xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
247
248   EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
249     {
250       *tos++ = BASIC_BLOCK (i);
251     }
252
253   /* Iterate until the worklist is empty.  */
254   while (tos != worklist)
255     {
256       edge e;
257       edge_iterator ei;
258
259       /* Pull a block off the worklist.  */
260       bb = *--tos;
261
262       /* For each predecessor block.  */
263       FOR_EACH_EDGE (e, ei, bb->preds)
264         {
265           basic_block pred = e->src;
266           int pred_index = pred->index;
267
268           /* None of this is necessary for the entry block.  */
269           if (pred != ENTRY_BLOCK_PTR
270               && ! bitmap_bit_p (livein, pred_index)
271               && ! bitmap_bit_p (def_blocks, pred_index))
272             {
273               *tos++ = pred;
274               bitmap_set_bit (livein, pred_index);
275             }
276         }
277     }
278
279   free (worklist);
280 }
281
282
283 /* Block initialization routine for mark_def_sites.  Clear the 
284    KILLS bitmap at the start of each block.  */
285
286 static void
287 mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
288                                  basic_block bb ATTRIBUTE_UNUSED)
289 {
290   struct mark_def_sites_global_data *gd = walk_data->global_data;
291   bitmap kills = gd->kills;
292
293   bitmap_clear (kills);
294 }
295
296 /* Block initialization routine for mark_def_sites.  Clear the 
297    KILLS bitmap at the start of each block.  */
298
299 static void
300 ssa_mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
301                                      basic_block bb)
302 {
303   struct mark_def_sites_global_data *gd = walk_data->global_data;
304   bitmap kills = gd->kills;
305   tree phi, def;
306   unsigned def_uid;
307
308   bitmap_clear (kills);
309
310   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
311     {
312       def = PHI_RESULT (phi);
313       def_uid = SSA_NAME_VERSION (def);
314
315       if (!TEST_BIT (gd->names_to_rename, def_uid))
316         continue;
317
318       set_def_block (def, bb, true, true);
319       bitmap_set_bit (kills, def_uid);
320     }
321 }
322
323 /* Marks ssa names used as arguments of phis at the end of BB.  */
324
325 static void
326 ssa_mark_phi_uses (struct dom_walk_data *walk_data, basic_block bb)
327 {
328   struct mark_def_sites_global_data *gd = walk_data->global_data;
329   bitmap kills = gd->kills;
330   edge e;
331   tree phi, use;
332   unsigned uid;
333   edge_iterator ei;
334
335   FOR_EACH_EDGE (e, ei, bb->succs)
336     {
337       if (e->dest == EXIT_BLOCK_PTR)
338         continue;
339
340       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
341         {
342           use = PHI_ARG_DEF_FROM_EDGE (phi, e);
343           if (TREE_CODE (use) != SSA_NAME)
344             continue;
345
346           uid = SSA_NAME_VERSION (use);
347
348           if (TEST_BIT (gd->names_to_rename, uid)
349               && !bitmap_bit_p (kills, uid))
350             set_livein_block (use, bb);
351         }
352     }
353 }
354
355 /* Call back for walk_dominator_tree used to collect definition sites
356    for every variable in the function.  For every statement S in block
357    BB:
358
359    1- Variables defined by S in DEF_OPS(S) are marked in the bitmap
360       WALK_DATA->GLOBAL_DATA->KILLS.
361
362    2- If S uses a variable VAR and there is no preceding kill of VAR,
363       then it is marked in marked in the LIVEIN_BLOCKS bitmap
364       associated with VAR.
365
366    This information is used to determine which variables are live
367    across block boundaries to reduce the number of PHI nodes
368    we create.  */
369
370 static void
371 mark_def_sites (struct dom_walk_data *walk_data,
372                 basic_block bb,
373                 block_stmt_iterator bsi)
374 {
375   struct mark_def_sites_global_data *gd = walk_data->global_data;
376   bitmap kills = gd->kills;
377   size_t uid;
378   tree stmt, def;
379   use_operand_p use_p;
380   def_operand_p def_p;
381   ssa_op_iter iter;
382
383   /* Mark all the blocks that have definitions for each variable in the
384      VARS_TO_RENAME bitmap.  */
385   stmt = bsi_stmt (bsi);
386   get_stmt_operands (stmt);
387
388   REWRITE_THIS_STMT (stmt) = 0;
389
390   /* If a variable is used before being set, then the variable is live
391      across a block boundary, so mark it live-on-entry to BB.  */
392
393   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
394                             SSA_OP_USE | SSA_OP_VUSE | SSA_OP_VMUSTDEFKILL)
395     {
396       if (prepare_use_operand_for_rename (use_p, &uid))
397         {
398           REWRITE_THIS_STMT (stmt) = 1;
399           if (!bitmap_bit_p (kills, uid))
400             set_livein_block (USE_FROM_PTR (use_p), bb);
401         }
402     }
403   
404   /* Note that virtual definitions are irrelevant for computing KILLS
405      because a V_MAY_DEF does not constitute a killing definition of the
406      variable.  However, the operand of a virtual definitions is a use
407      of the variable, so it may cause the variable to be considered
408      live-on-entry.  */
409   FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
410     {
411       if (prepare_use_operand_for_rename (use_p, &uid))
412         {
413           /* If we do not already have an SSA_NAME for our destination,
414              then set the destination to the source.  */
415           if (TREE_CODE (DEF_FROM_PTR (def_p)) != SSA_NAME)
416             SET_DEF (def_p, USE_FROM_PTR (use_p));
417             
418           set_livein_block (USE_FROM_PTR (use_p), bb);
419           set_def_block (DEF_FROM_PTR (def_p), bb, false, false);
420           REWRITE_THIS_STMT (stmt) = 1;
421         }
422     }
423
424   /* Now process the defs and must-defs made by this statement.  */
425   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF | SSA_OP_VMUSTDEF)
426     {
427       if (prepare_def_operand_for_rename (def, &uid))
428         {
429           set_def_block (def, bb, false, false);
430           bitmap_set_bit (kills, uid);
431           REWRITE_THIS_STMT (stmt) = 1;
432         }
433     }
434 }
435
436
437 /* Same as mark_def_sites, but works over SSA names.  */
438
439 static void
440 ssa_mark_def_sites (struct dom_walk_data *walk_data,
441                     basic_block bb,
442                     block_stmt_iterator bsi)
443 {
444   struct mark_def_sites_global_data *gd = walk_data->global_data;
445   bitmap kills = gd->kills;
446   size_t uid, def_uid;
447   tree stmt, use, def;
448   ssa_op_iter iter;
449
450   /* Mark all the blocks that have definitions for each variable in the
451      names_to_rename bitmap.  */
452   stmt = bsi_stmt (bsi);
453   get_stmt_operands (stmt);
454
455   /* If a variable is used before being set, then the variable is live
456      across a block boundary, so mark it live-on-entry to BB.  */
457   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
458     {
459       uid = SSA_NAME_VERSION (use);
460
461       if (TEST_BIT (gd->names_to_rename, uid)
462           && !bitmap_bit_p (kills, uid))
463         set_livein_block (use, bb);
464     }
465           
466   /* Now process the definition made by this statement.  Mark the
467      variables in KILLS.  */
468   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
469     {
470       def_uid = SSA_NAME_VERSION (def);
471
472       if (TEST_BIT (gd->names_to_rename, def_uid))
473         {
474           set_def_block (def, bb, false, true);
475           bitmap_set_bit (kills, def_uid);
476         }
477     }
478 }
479
480 /* Mark block BB as the definition site for variable VAR.  PHI_P is true if
481    VAR is defined by a phi node.  SSA_P is true if we are called from
482    rewrite_ssa_into_ssa.  */
483
484 static void
485 set_def_block (tree var, basic_block bb, bool phi_p, bool ssa_p)
486 {
487   struct def_blocks_d *db_p;
488   enum need_phi_state state;
489
490   if (!ssa_p
491       && TREE_CODE (var) == SSA_NAME)
492     var = SSA_NAME_VAR (var);
493
494   state = get_phi_state (var);
495   db_p = get_def_blocks_for (var);
496
497   /* Set the bit corresponding to the block where VAR is defined.  */
498   bitmap_set_bit (db_p->def_blocks, bb->index);
499   if (phi_p)
500     bitmap_set_bit (db_p->phi_blocks, bb->index);
501
502   /* Keep track of whether or not we may need to insert phi nodes.
503
504      If we are in the UNKNOWN state, then this is the first definition
505      of VAR.  Additionally, we have not seen any uses of VAR yet, so
506      we do not need a phi node for this variable at this time (i.e.,
507      transition to NEED_PHI_STATE_NO).
508
509      If we are in any other state, then we either have multiple definitions
510      of this variable occurring in different blocks or we saw a use of the
511      variable which was not dominated by the block containing the
512      definition(s).  In this case we may need a PHI node, so enter
513      state NEED_PHI_STATE_MAYBE.  */
514   if (state == NEED_PHI_STATE_UNKNOWN)
515     set_phi_state (var, NEED_PHI_STATE_NO);
516   else
517     set_phi_state (var, NEED_PHI_STATE_MAYBE);
518 }
519
520
521 /* Mark block BB as having VAR live at the entry to BB.  */
522
523 static void
524 set_livein_block (tree var, basic_block bb)
525 {
526   struct def_blocks_d *db_p;
527   enum need_phi_state state = get_phi_state (var);
528
529   db_p = get_def_blocks_for (var);
530
531   /* Set the bit corresponding to the block where VAR is live in.  */
532   bitmap_set_bit (db_p->livein_blocks, bb->index);
533
534   /* Keep track of whether or not we may need to insert phi nodes.
535
536      If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
537      by the single block containing the definition(s) of this variable.  If
538      it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
539      NEED_PHI_STATE_MAYBE.  */
540   if (state == NEED_PHI_STATE_NO)
541     {
542       int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
543
544       if (def_block_index == -1
545           || ! dominated_by_p (CDI_DOMINATORS, bb,
546                                BASIC_BLOCK (def_block_index)))
547         set_phi_state (var, NEED_PHI_STATE_MAYBE);
548     }
549   else
550     set_phi_state (var, NEED_PHI_STATE_MAYBE);
551 }
552
553
554 /* If the use operand pointed to by OP_P needs to be renamed, then strip away 
555    any SSA_NAME wrapping the operand, set *UID_P to the underlying variable's 
556    uid, and return true.  Otherwise return false.  If the operand was an 
557    SSA_NAME, change it to the stripped name.  */
558
559 static bool
560 prepare_use_operand_for_rename (use_operand_p op_p, size_t *uid_p)
561 {
562   tree use = USE_FROM_PTR (op_p);
563   tree var = (TREE_CODE (use) != SSA_NAME) ? use : SSA_NAME_VAR (use);
564   *uid_p = var_ann (var)->uid;
565
566   /* Ignore variables that don't need to be renamed.  */
567   if (vars_to_rename && !bitmap_bit_p (vars_to_rename, *uid_p))
568     return false;
569
570   /* The variable needs to be renamed.  If this is a use which already
571      has an SSA_NAME, then strip it off.
572
573      By not throwing away SSA_NAMEs on assignments, we avoid a lot of 
574      useless churn of SSA_NAMEs without having to overly complicate the
575      renamer.  */
576   if (TREE_CODE (use) == SSA_NAME)
577     SET_USE (op_p, var);
578
579   return true;
580 }
581
582 /* If the def variable DEF needs to be renamed, then strip away any SSA_NAME 
583    wrapping the operand, set *UID_P to the underlying variable's uid and return
584    true.  Otherwise return false.  */
585
586 static bool
587 prepare_def_operand_for_rename (tree def, size_t *uid_p)
588 {
589   tree var = (TREE_CODE (def) != SSA_NAME) ? def : SSA_NAME_VAR (def);
590   *uid_p = var_ann (var)->uid;
591
592   /* Ignore variables that don't need to be renamed.  */
593   if (vars_to_rename && !bitmap_bit_p (vars_to_rename, *uid_p))
594     return false;
595
596   return true;
597 }
598
599 /* Helper for insert_phi_nodes.  If VAR needs PHI nodes, insert them
600    at the dominance frontier (DFS) of blocks defining VAR.
601    WORK_STACK is the vector used to implement the worklist of basic
602    blocks.  */
603
604 static inline void
605 insert_phi_nodes_1 (tree var, bitmap *dfs, VEC(basic_block) **work_stack)
606 {
607   if (get_phi_state (var) != NEED_PHI_STATE_NO)
608     insert_phi_nodes_for (var, dfs, work_stack);
609 }
610
611 /* Insert PHI nodes at the dominance frontier of blocks with variable
612    definitions.  DFS contains the dominance frontier information for
613    the flowgraph.  PHI nodes will only be inserted at the dominance
614    frontier of definition blocks for variables whose NEED_PHI_STATE
615    annotation is marked as ``maybe'' or ``unknown'' (computed by
616    mark_def_sites).  If NAMES_TO_RENAME is not NULL, do the same but
617    for ssa name rewriting.  */
618
619 static void
620 insert_phi_nodes (bitmap *dfs, bitmap names_to_rename)
621 {
622   unsigned i;
623   VEC(basic_block) *work_stack;
624   bitmap_iterator bi;
625
626   timevar_push (TV_TREE_INSERT_PHI_NODES);
627
628   /* Vector WORK_STACK is a stack of CFG blocks.  Each block that contains
629      an assignment or PHI node will be pushed to this stack.  */
630   work_stack = VEC_alloc (basic_block, n_basic_blocks);
631
632   /* Iterate over all variables in VARS_TO_RENAME.  For each variable, add
633      to the work list all the blocks that have a definition for the
634      variable.  PHI nodes will be added to the dominance frontier blocks of
635      each definition block.  */
636   if (names_to_rename)
637     {
638       EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
639         {
640           if (ssa_name (i))
641             insert_phi_nodes_1 (ssa_name (i), dfs, &work_stack);
642         }
643     }
644   else if (vars_to_rename)
645     EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i, bi)
646       {
647         insert_phi_nodes_1 (referenced_var (i), dfs, &work_stack);
648       }
649   else
650     for (i = 0; i < num_referenced_vars; i++)
651       insert_phi_nodes_1 (referenced_var (i), dfs, &work_stack);
652
653   VEC_free (basic_block, work_stack);
654
655   timevar_pop (TV_TREE_INSERT_PHI_NODES);
656 }
657
658
659 /* Perform a depth-first traversal of the dominator tree looking for
660    variables to rename.  BB is the block where to start searching.
661    Renaming is a five step process:
662
663    1- Every definition made by PHI nodes at the start of the blocks is
664       registered as the current definition for the corresponding variable.
665
666    2- Every statement in BB is rewritten.  USE and VUSE operands are
667       rewritten with their corresponding reaching definition.  DEF and
668       VDEF targets are registered as new definitions.
669       
670    3- All the PHI nodes in successor blocks of BB are visited.  The
671       argument corresponding to BB is replaced with its current reaching
672       definition.
673
674    4- Recursively rewrite every dominator child block of BB.
675
676    5- Restore (in reverse order) the current reaching definition for every
677       new definition introduced in this block.  This is done so that when
678       we return from the recursive call, all the current reaching
679       definitions are restored to the names that were valid in the
680       dominator parent of BB.  */
681
682 /* SSA Rewriting Step 1.  Initialization, create a block local stack
683    of reaching definitions for new SSA names produced in this block
684    (BLOCK_DEFS).  Register new definitions for every PHI node in the
685    block.  */
686
687 static void
688 rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
689                           basic_block bb)
690 {
691   tree phi;
692
693   if (dump_file && (dump_flags & TDF_DETAILS))
694     fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
695
696   /* Mark the unwind point for this block.  */
697   VEC_safe_push (tree_on_heap, block_defs_stack, NULL_TREE);
698
699   /* Step 1.  Register new definitions for every PHI node in the block.
700      Conceptually, all the PHI nodes are executed in parallel and each PHI
701      node introduces a new version for the associated variable.  */
702   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
703     {
704       tree result = PHI_RESULT (phi);
705
706       register_new_def (result, &block_defs_stack);
707     }
708 }
709
710 /* Register DEF (an SSA_NAME) to be a new definition for the original
711    ssa name VAR and push VAR's current reaching definition
712    into the stack pointed by BLOCK_DEFS_P.  */
713
714 static void
715 ssa_register_new_def (tree var, tree def)
716 {
717   tree currdef;
718    
719   /* If this variable is set in a single basic block and all uses are
720      dominated by the set(s) in that single basic block, then there is
721      nothing to do.  TODO we should not be called at all, and just
722      keep the original name.  */
723   if (get_phi_state (var) == NEED_PHI_STATE_NO)
724     {
725       set_current_def (var, def);
726       return;
727     }
728
729   currdef = get_current_def (var);
730
731   /* Push the current reaching definition into *BLOCK_DEFS_P.  This stack is
732      later used by the dominator tree callbacks to restore the reaching
733      definitions for all the variables defined in the block after a recursive
734      visit to all its immediately dominated blocks.  */
735   VEC_safe_push (tree_on_heap, block_defs_stack, currdef);
736   VEC_safe_push (tree_on_heap, block_defs_stack, var);
737
738   /* Set the current reaching definition for VAR to be DEF.  */
739   set_current_def (var, def);
740 }
741
742 /* Ditto, for rewriting ssa names.  */
743
744 static void
745 ssa_rewrite_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
746 {
747   tree phi, new_name;
748   sbitmap names_to_rename = walk_data->global_data;
749   edge e;
750   bool abnormal_phi;
751   edge_iterator ei;
752
753   if (dump_file && (dump_flags & TDF_DETAILS))
754     fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
755
756   /* Mark the unwind point for this block.  */
757   VEC_safe_push (tree_on_heap, block_defs_stack, NULL_TREE);
758
759   FOR_EACH_EDGE (e, ei, bb->preds)
760     if (e->flags & EDGE_ABNORMAL)
761       break;
762   abnormal_phi = (e != NULL);
763
764   /* Step 1.  Register new definitions for every PHI node in the block.
765      Conceptually, all the PHI nodes are executed in parallel and each PHI
766      node introduces a new version for the associated variable.  */
767   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
768     {
769       tree result = PHI_RESULT (phi);
770
771       if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (result)))
772         {
773           new_name = duplicate_ssa_name (result, phi);
774           SET_PHI_RESULT (phi, new_name);
775
776           if (abnormal_phi)
777             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
778           ssa_register_new_def (result, new_name);
779         }
780     }
781 }
782
783 /* SSA Rewriting Step 3.  Visit all the successor blocks of BB looking for
784    PHI nodes.  For every PHI node found, add a new argument containing the
785    current reaching definition for the variable and the edge through which
786    that definition is reaching the PHI node.  */
787
788 static void
789 rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
790                            basic_block bb)
791 {
792   edge e;
793   edge_iterator ei;
794
795   FOR_EACH_EDGE (e, ei, bb->succs)
796     {
797       tree phi;
798
799       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
800         {
801           tree currdef;
802
803           /* If this PHI node has already been rewritten, then there is
804              nothing to do for this PHI or any following PHIs since we
805              always add new PHI nodes at the start of the PHI chain.  */
806           if (PHI_REWRITTEN (phi))
807             break;
808
809           currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
810           add_phi_arg (phi, currdef, e);
811         }
812     }
813 }
814
815 /*  Rewrite existing virtual PHI arguments so that they have the correct
816     reaching definitions.  BB is the basic block whose successors contain the
817     phi nodes we want to add arguments for.  */
818
819 static void
820 rewrite_virtual_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
821                                basic_block bb)
822 {
823   edge e;
824   use_operand_p op;
825   edge_iterator ei;
826
827   FOR_EACH_EDGE (e, ei, bb->succs)
828     {
829       tree phi;
830
831       if (e->dest == EXIT_BLOCK_PTR)
832         continue;
833
834       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
835         {
836           tree result = PHI_RESULT (phi);
837           op = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
838           
839           if (is_gimple_reg (result) 
840               || !bitmap_bit_p (vars_to_rename, 
841                                 var_ann (SSA_NAME_VAR (result))->uid))
842             continue;
843
844           SET_USE (op, get_reaching_def (SSA_NAME_VAR (result)));
845           if (e->flags & EDGE_ABNORMAL)
846             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (op)) = 1;
847         }
848     }
849 }
850
851 /* Ditto, for ssa name rewriting.  */
852
853 static void
854 ssa_rewrite_phi_arguments (struct dom_walk_data *walk_data, basic_block bb)
855 {
856   edge e;
857   sbitmap names_to_rename = walk_data->global_data;
858   use_operand_p op;
859   edge_iterator ei;
860
861   FOR_EACH_EDGE (e, ei, bb->succs)
862     {
863       tree phi;
864
865       if (e->dest == EXIT_BLOCK_PTR)
866         continue;
867
868       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
869         {
870           op = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
871           if (TREE_CODE (USE_FROM_PTR (op)) != SSA_NAME)
872             continue;
873           
874           if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (op))))
875             continue; 
876
877           SET_USE (op, get_reaching_def (USE_FROM_PTR (op)));
878           if (e->flags & EDGE_ABNORMAL)
879             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (op)) = 1;
880         }
881     }
882 }
883
884
885 /* Similar to restore_vars_to_original_value, except that it restores 
886    CURRDEFS to its original value.  */
887 static void
888 rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
889                         basic_block bb ATTRIBUTE_UNUSED)
890 {
891   /* Restore CURRDEFS to its original state.  */
892   while (VEC_length (tree_on_heap, block_defs_stack) > 0)
893     {
894       tree tmp = VEC_pop (tree_on_heap, block_defs_stack);
895       tree saved_def, var;
896
897       if (tmp == NULL_TREE)
898         break;
899
900       /* If we recorded an SSA_NAME, then make the SSA_NAME the current
901          definition of its underlying variable.  If we recorded anything
902          else, it must have been an _DECL node and its current reaching
903          definition must have been NULL.  */
904       if (TREE_CODE (tmp) == SSA_NAME)
905         {
906           saved_def = tmp;
907           var = SSA_NAME_VAR (saved_def);
908         }
909       else
910         {
911           saved_def = NULL;
912           var = tmp;
913         }
914                                                                                 
915       set_current_def (var, saved_def);
916     }
917 }
918
919 /* Ditto, for rewriting ssa names.  */
920
921 static void
922 ssa_rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
923                             basic_block bb ATTRIBUTE_UNUSED)
924 {
925
926   /* Step 5.  Restore the current reaching definition for each variable
927      referenced in the block (in reverse order).  */
928   while (VEC_length (tree_on_heap, block_defs_stack) > 0)
929     {
930       tree var = VEC_pop (tree_on_heap, block_defs_stack);
931       tree saved_def;
932       
933       if (var == NULL)
934         break;
935
936       saved_def = VEC_pop (tree_on_heap, block_defs_stack);
937
938       set_current_def (var, saved_def);
939     }
940 }
941
942 /* Dump SSA information to FILE.  */
943
944 void
945 dump_tree_ssa (FILE *file)
946 {
947   basic_block bb;
948   const char *funcname
949     = lang_hooks.decl_printable_name (current_function_decl, 2);
950
951   fprintf (file, "SSA information for %s\n\n", funcname);
952
953   FOR_EACH_BB (bb)
954     {
955       dump_bb (bb, file, 0);
956       fputs ("    ", file);
957       print_generic_stmt (file, phi_nodes (bb), dump_flags);
958       fputs ("\n\n", file);
959     }
960 }
961
962
963 /* Dump SSA information to stderr.  */
964
965 void
966 debug_tree_ssa (void)
967 {
968   dump_tree_ssa (stderr);
969 }
970
971
972 /* Dump SSA statistics on FILE.  */
973
974 void
975 dump_tree_ssa_stats (FILE *file)
976 {
977   fprintf (file, "\nHash table statistics:\n");
978
979   fprintf (file, "    def_blocks: ");
980   htab_statistics (file, def_blocks);
981
982   fprintf (file, "\n");
983 }
984
985
986 /* Dump SSA statistics on stderr.  */
987
988 void
989 debug_tree_ssa_stats (void)
990 {
991   dump_tree_ssa_stats (stderr);
992 }
993
994
995 /* Dump statistics for the hash table HTAB.  */
996
997 static void
998 htab_statistics (FILE *file, htab_t htab)
999 {
1000   fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1001            (long) htab_size (htab),
1002            (long) htab_elements (htab),
1003            htab_collisions (htab));
1004 }
1005
1006
1007 /* Insert PHI nodes for variable VAR using the dominance frontier
1008    information given in DFS.  WORK_STACK is the vector used to
1009    implement the worklist of basic blocks.  */
1010
1011 static void
1012 insert_phi_nodes_for (tree var, bitmap *dfs, VEC(basic_block) **work_stack)
1013 {
1014   struct def_blocks_d *def_map;
1015   bitmap phi_insertion_points;
1016   unsigned bb_index;
1017   edge e;
1018   tree phi;
1019   basic_block bb;
1020   bitmap_iterator bi;
1021
1022   def_map = find_def_blocks_for (var);
1023   if (def_map == NULL)
1024     return;
1025
1026   phi_insertion_points = BITMAP_ALLOC (NULL);
1027
1028   EXECUTE_IF_SET_IN_BITMAP (def_map->def_blocks, 0, bb_index, bi)
1029     {
1030       VEC_safe_push (basic_block, *work_stack, BASIC_BLOCK (bb_index));
1031     }
1032
1033   /* Pop a block off the worklist, add every block that appears in
1034      the original block's dfs that we have not already processed to
1035      the worklist.  Iterate until the worklist is empty.   Blocks
1036      which are added to the worklist are potential sites for
1037      PHI nodes. 
1038
1039      The iteration step could be done during PHI insertion just as
1040      easily.  We do it here for historical reasons -- we used to have
1041      a heuristic which used the potential PHI insertion points to
1042      determine if fully pruned or semi pruned SSA form was appropriate.
1043
1044      We now always use fully pruned SSA form.  */
1045   while (VEC_length (basic_block, *work_stack) > 0)
1046     {
1047       unsigned dfs_index;
1048       bitmap_iterator bi;
1049
1050       bb = VEC_pop (basic_block, *work_stack);
1051       bb_index = bb->index;
1052       
1053       EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index],
1054                                       phi_insertion_points,
1055                                       0, dfs_index, bi)
1056         {
1057           basic_block bb = BASIC_BLOCK (dfs_index);
1058
1059           /* Use a safe push because if there is a definition of VAR
1060              in every basic block, then WORK_STACK may eventually have
1061              more than N_BASIC_BLOCK entries.  */
1062           VEC_safe_push (basic_block, *work_stack, bb);
1063           bitmap_set_bit (phi_insertion_points, dfs_index);
1064         }
1065     }
1066
1067   /* Remove the blocks where we already have the phis.  */
1068   bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
1069
1070   /* Now compute global livein for this variable.  Note this modifies
1071      def_map->livein_blocks.  */
1072   compute_global_livein (def_map->livein_blocks, def_map->def_blocks);
1073
1074   /* And insert the PHI nodes.  */
1075   EXECUTE_IF_AND_IN_BITMAP (phi_insertion_points, def_map->livein_blocks,
1076                             0, bb_index, bi)
1077     {
1078       bb = BASIC_BLOCK (bb_index);
1079
1080       phi = create_phi_node (var, bb);
1081
1082       /* If we are rewriting ssa names, add also the phi arguments.  */
1083       if (TREE_CODE (var) == SSA_NAME)
1084         {
1085           edge_iterator ei;
1086           FOR_EACH_EDGE (e, ei, bb->preds)
1087             add_phi_arg (phi, var, e);
1088         }
1089     }
1090
1091   BITMAP_FREE (phi_insertion_points);
1092 }
1093
1094 /* SSA Rewriting Step 2.  Rewrite every variable used in each statement in
1095    the block with its immediate reaching definitions.  Update the current
1096    definition of a variable when a new real or virtual definition is found.  */
1097
1098 static void
1099 rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1100               basic_block bb ATTRIBUTE_UNUSED,
1101               block_stmt_iterator si)
1102 {
1103   stmt_ann_t ann;
1104   tree stmt;
1105   use_operand_p use_p;
1106   def_operand_p def_p;
1107   ssa_op_iter iter;
1108
1109   stmt = bsi_stmt (si);
1110   ann = stmt_ann (stmt);
1111
1112   /* If mark_def_sites decided that we don't need to rewrite this
1113      statement, ignore it.  */
1114   if (!REWRITE_THIS_STMT (stmt))
1115     return;
1116
1117   if (dump_file && (dump_flags & TDF_DETAILS))
1118     {
1119       fprintf (dump_file, "Renaming statement ");
1120       print_generic_stmt (dump_file, stmt, TDF_SLIM);
1121       fprintf (dump_file, "\n");
1122     }
1123
1124   /* We have just scanned the code for operands.  No statement should
1125      be modified.  */
1126   gcc_assert (!ann->modified);
1127
1128   /* Step 1.  Rewrite USES and VUSES in the statement.  */
1129   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
1130     rewrite_operand (use_p);
1131
1132   /* Step 2.  Register the statement's DEF and VDEF operands.  */
1133   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1134     {
1135       if (TREE_CODE (DEF_FROM_PTR (def_p)) != SSA_NAME)
1136         SET_DEF (def_p, make_ssa_name (DEF_FROM_PTR (def_p), stmt));
1137
1138       /* FIXME: We shouldn't be registering new defs if the variable
1139          doesn't need to be renamed.  */
1140       register_new_def (DEF_FROM_PTR (def_p), &block_defs_stack);
1141     }
1142 }
1143
1144
1145 /* Same as rewrite_stmt, for rewriting ssa names.  */
1146
1147 static void
1148 ssa_rewrite_stmt (struct dom_walk_data *walk_data,
1149                   basic_block bb ATTRIBUTE_UNUSED,
1150                   block_stmt_iterator si)
1151 {
1152   stmt_ann_t ann;
1153   tree stmt, var;
1154   ssa_op_iter iter;
1155   use_operand_p use_p;
1156   def_operand_p def_p;
1157   sbitmap names_to_rename = walk_data->global_data;
1158
1159   stmt = bsi_stmt (si);
1160   ann = stmt_ann (stmt);
1161
1162   if (dump_file && (dump_flags & TDF_DETAILS))
1163     {
1164       fprintf (dump_file, "Renaming statement ");
1165       print_generic_stmt (dump_file, stmt, TDF_SLIM);
1166       fprintf (dump_file, "\n");
1167     }
1168
1169   /* We have just scanned the code for operands.  No statement should
1170      be modified.  */
1171   gcc_assert (!ann->modified);
1172
1173   /* Step 1.  Rewrite USES and VUSES in the statement.  */
1174   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
1175     {
1176       if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (use_p))))
1177         SET_USE (use_p, get_reaching_def (USE_FROM_PTR (use_p)));
1178     }
1179
1180   /* Step 2.  Register the statement's DEF and VDEF operands.  */
1181   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1182     {
1183       var = DEF_FROM_PTR (def_p);
1184
1185       if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (var)))
1186         continue;
1187
1188       SET_DEF (def_p, duplicate_ssa_name (var, stmt));
1189       ssa_register_new_def (var, DEF_FROM_PTR (def_p));
1190     }
1191 }
1192
1193 /* Replace the operand pointed by OP_P with its immediate reaching
1194    definition.  */
1195
1196 static inline void
1197 rewrite_operand (use_operand_p op_p)
1198 {
1199   tree var = USE_FROM_PTR (op_p);
1200   if (TREE_CODE (var) != SSA_NAME)
1201     SET_USE (op_p, get_reaching_def (var));
1202   else
1203     {
1204 #if defined ENABLE_CHECKING
1205       /* If we get to this point, VAR is an SSA_NAME.  If VAR's symbol
1206          was marked for renaming, make sure that its reaching
1207          definition is VAR itself.  Otherwise, something has gone
1208          wrong.  */
1209       tree sym = SSA_NAME_VAR (var);
1210       if (bitmap_bit_p (vars_to_rename, var_ann (sym)->uid))
1211         gcc_assert (var == get_reaching_def (SSA_NAME_VAR (var)));
1212 #endif
1213     }
1214 }
1215
1216 /* Register DEF (an SSA_NAME) to be a new definition for its underlying
1217    variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition
1218    into the stack pointed by BLOCK_DEFS_P.  */
1219
1220 void
1221 register_new_def (tree def, VEC (tree_on_heap) **block_defs_p)
1222 {
1223   tree var = SSA_NAME_VAR (def);
1224   tree currdef;
1225    
1226   /* If this variable is set in a single basic block and all uses are
1227      dominated by the set(s) in that single basic block, then there is
1228      no reason to record anything for this variable in the block local
1229      definition stacks.  Doing so just wastes time and memory.
1230
1231      This is the same test to prune the set of variables which may
1232      need PHI nodes.  So we just use that information since it's already
1233      computed and available for us to use.  */
1234   if (get_phi_state (var) == NEED_PHI_STATE_NO)
1235     {
1236       set_current_def (var, def);
1237       return;
1238     }
1239
1240   currdef = get_current_def (var);
1241
1242   /* Push the current reaching definition into *BLOCK_DEFS_P.  This stack is
1243      later used by the dominator tree callbacks to restore the reaching
1244      definitions for all the variables defined in the block after a recursive
1245      visit to all its immediately dominated blocks.  If there is no current
1246      reaching definition, then just record the underlying _DECL node.  */
1247   VEC_safe_push (tree_on_heap, *block_defs_p, currdef ? currdef : var);
1248
1249   /* Set the current reaching definition for VAR to be DEF.  */
1250   set_current_def (var, def);
1251 }
1252
1253 /* Return the current definition for variable VAR.  If none is found,
1254    create a new SSA name to act as the zeroth definition for VAR.  If VAR
1255    is call clobbered and there exists a more recent definition of
1256    GLOBAL_VAR, return the definition for GLOBAL_VAR.  This means that VAR
1257    has been clobbered by a function call since its last assignment.  */
1258
1259 static tree
1260 get_reaching_def (tree var)
1261 {
1262   tree default_d, currdef_var, avar;
1263   
1264   /* Lookup the current reaching definition for VAR.  */
1265   default_d = NULL_TREE;
1266   currdef_var = get_current_def (var);
1267
1268   /* If there is no reaching definition for VAR, create and register a
1269      default definition for it (if needed).  */
1270   if (currdef_var == NULL_TREE)
1271     {
1272       if (TREE_CODE (var) == SSA_NAME)
1273         avar = SSA_NAME_VAR (var);
1274       else
1275         avar = var;
1276
1277       default_d = default_def (avar);
1278       if (default_d == NULL_TREE)
1279         {
1280           default_d = make_ssa_name (avar, build_empty_stmt ());
1281           set_default_def (avar, default_d);
1282         }
1283       set_current_def (var, default_d);
1284     }
1285
1286   /* Return the current reaching definition for VAR, or the default
1287      definition, if we had to create one.  */
1288   return (currdef_var) ? currdef_var : default_d;
1289 }
1290
1291
1292 /* Hashing and equality functions for DEF_BLOCKS.  */
1293
1294 static hashval_t
1295 def_blocks_hash (const void *p)
1296 {
1297   return htab_hash_pointer
1298         ((const void *)((const struct def_blocks_d *)p)->var);
1299 }
1300
1301 static int
1302 def_blocks_eq (const void *p1, const void *p2)
1303 {
1304   return ((const struct def_blocks_d *)p1)->var
1305          == ((const struct def_blocks_d *)p2)->var;
1306 }
1307
1308 /* Free memory allocated by one entry in DEF_BLOCKS.  */
1309
1310 static void
1311 def_blocks_free (void *p)
1312 {
1313   struct def_blocks_d *entry = p;
1314   BITMAP_FREE (entry->def_blocks);
1315   BITMAP_FREE (entry->phi_blocks);
1316   BITMAP_FREE (entry->livein_blocks);
1317   free (entry);
1318 }
1319
1320
1321 /* Dump the DEF_BLOCKS hash table on stderr.  */
1322
1323 void
1324 debug_def_blocks (void)
1325 {
1326   htab_traverse (def_blocks, debug_def_blocks_r, NULL);
1327 }
1328
1329 /* Callback for htab_traverse to dump the DEF_BLOCKS hash table.  */
1330
1331 static int
1332 debug_def_blocks_r (void **slot, void *data ATTRIBUTE_UNUSED)
1333 {
1334   struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
1335   
1336   fprintf (stderr, "VAR: ");
1337   print_generic_expr (stderr, db_p->var, dump_flags);
1338   bitmap_print (stderr, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
1339   bitmap_print (stderr, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}\n");
1340
1341   return 1;
1342 }
1343
1344
1345 /* Return the set of blocks where variable VAR is defined and the blocks
1346    where VAR is live on entry (livein).  Return NULL, if no entry is
1347    found in DEF_BLOCKS.  */
1348
1349 static inline struct def_blocks_d *
1350 find_def_blocks_for (tree var)
1351 {
1352   struct def_blocks_d dm;
1353   dm.var = var;
1354   return (struct def_blocks_d *) htab_find (def_blocks, &dm);
1355 }
1356
1357
1358 /* Return the set of blocks where variable VAR is defined and the blocks
1359    where VAR is live on entry (livein).  If no entry is found in
1360    DEF_BLOCKS, a new one is created and returned.  */
1361
1362 static inline struct def_blocks_d *
1363 get_def_blocks_for (tree var)
1364 {
1365   struct def_blocks_d db, *db_p;
1366   void **slot;
1367
1368   db.var = var;
1369   slot = htab_find_slot (def_blocks, (void *) &db, INSERT);
1370   if (*slot == NULL)
1371     {
1372       db_p = xmalloc (sizeof (*db_p));
1373       db_p->var = var;
1374       db_p->def_blocks = BITMAP_ALLOC (NULL);
1375       db_p->phi_blocks = BITMAP_ALLOC (NULL);
1376       db_p->livein_blocks = BITMAP_ALLOC (NULL);
1377       *slot = (void *) db_p;
1378     }
1379   else
1380     db_p = (struct def_blocks_d *) *slot;
1381
1382   return db_p;
1383 }
1384
1385 /* If a variable V in VARS_TO_RENAME is a pointer, the renaming
1386    process will cause us to lose the name memory tags that may have
1387    been associated with the various SSA_NAMEs of V.  This means that
1388    the variables aliased to those name tags also need to be renamed
1389    again.
1390
1391    FIXME 1- We should either have a better scheme for renaming
1392             pointers that doesn't lose name tags or re-run alias
1393             analysis to recover points-to information.
1394
1395          2- Currently we just invalidate *all* the name tags.  This
1396             should be more selective.  */
1397
1398 static void
1399 invalidate_name_tags (bitmap vars_to_rename)
1400 {
1401   unsigned i;
1402   bool rename_name_tags_p;
1403   bitmap_iterator bi;
1404
1405   rename_name_tags_p = false;
1406   EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i, bi)
1407     {
1408       if (POINTER_TYPE_P (TREE_TYPE (referenced_var (i))))
1409         {
1410           rename_name_tags_p = true;
1411           break;
1412         }
1413     }
1414
1415   if (rename_name_tags_p)
1416     for (i = 0; i < num_referenced_vars; i++)
1417       {
1418         var_ann_t ann = var_ann (referenced_var (i));
1419
1420         if (ann->mem_tag_kind == NAME_TAG)
1421           {
1422             size_t j;
1423             varray_type may_aliases = ann->may_aliases;
1424
1425             bitmap_set_bit (vars_to_rename, ann->uid);
1426             if (ann->may_aliases)
1427               for (j = 0; j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
1428                 {
1429                   tree var = VARRAY_TREE (may_aliases, j);
1430                   bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1431                 }
1432           }
1433       }
1434 }
1435
1436 /* Rewrite the actual blocks, statements, and phi arguments, to be in SSA
1437    form.  FIX_VIRTUAL_PHIS is true if we should only be fixing up virtual
1438    phi arguments, instead of adding new phi arguments for just added phi
1439    nodes.  */
1440
1441
1442 static void
1443 rewrite_blocks (bool fix_virtual_phis)
1444 {
1445   struct dom_walk_data walk_data;
1446   
1447   /* Rewrite all the basic blocks in the program.  */
1448   timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
1449
1450   /* Setup callbacks for the generic dominator tree walker.  */
1451   walk_data.walk_stmts_backward = false;
1452   walk_data.dom_direction = CDI_DOMINATORS;
1453   walk_data.initialize_block_local_data = NULL;
1454   walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
1455   walk_data.before_dom_children_walk_stmts = rewrite_stmt;
1456   walk_data.before_dom_children_after_stmts = NULL;
1457   if (!fix_virtual_phis)
1458     walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
1459   else
1460     walk_data.before_dom_children_after_stmts = rewrite_virtual_phi_arguments;
1461   
1462   walk_data.after_dom_children_before_stmts =  NULL;
1463   walk_data.after_dom_children_walk_stmts =  NULL;
1464   walk_data.after_dom_children_after_stmts =  rewrite_finalize_block;
1465   walk_data.global_data = NULL;
1466   walk_data.block_local_data_size = 0;
1467
1468   block_defs_stack = VEC_alloc (tree_on_heap, 10);
1469
1470   /* Initialize the dominator walker.  */
1471   init_walk_dominator_tree (&walk_data);
1472
1473   /* Recursively walk the dominator tree rewriting each statement in
1474      each basic block.  */
1475   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1476
1477   /* Finalize the dominator walker.  */
1478   fini_walk_dominator_tree (&walk_data);
1479
1480   /* Debugging dumps.  */
1481   if (dump_file && (dump_flags & TDF_STATS))
1482     {
1483       dump_dfa_stats (dump_file);
1484       dump_tree_ssa_stats (dump_file);
1485     }
1486
1487   htab_delete (def_blocks);
1488   def_blocks = NULL;
1489   
1490   VEC_free (tree_on_heap, block_defs_stack);
1491   block_defs_stack = NULL;
1492
1493   timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
1494 }
1495
1496 /* Mark the definition site blocks for each variable, so that we know where
1497    the variable is actually live.  */
1498
1499 static void 
1500 mark_def_site_blocks (void)
1501 {
1502   size_t i;
1503   struct dom_walk_data walk_data;
1504   struct mark_def_sites_global_data mark_def_sites_global_data;
1505
1506   /* Allocate memory for the DEF_BLOCKS hash table.  */
1507   def_blocks = htab_create (VARRAY_ACTIVE_SIZE (referenced_vars),
1508                             def_blocks_hash, def_blocks_eq, def_blocks_free);
1509
1510   for (i = 0; i < num_referenced_vars; i++)
1511     set_current_def (referenced_var (i), NULL_TREE);
1512
1513   /* Ensure that the dominance information is OK.  */
1514   calculate_dominance_info (CDI_DOMINATORS);
1515
1516
1517   /* Setup callbacks for the generic dominator tree walker to find and
1518      mark definition sites.  */
1519   walk_data.walk_stmts_backward = false;
1520   walk_data.dom_direction = CDI_DOMINATORS;
1521   walk_data.initialize_block_local_data = NULL;
1522   walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block;
1523   walk_data.before_dom_children_walk_stmts = mark_def_sites;
1524   walk_data.before_dom_children_after_stmts = NULL; 
1525   walk_data.after_dom_children_before_stmts =  NULL;
1526   walk_data.after_dom_children_walk_stmts =  NULL;
1527   walk_data.after_dom_children_after_stmts =  NULL;
1528
1529   /* Notice that this bitmap is indexed using variable UIDs, so it must be
1530      large enough to accommodate all the variables referenced in the
1531      function, not just the ones we are renaming.  */
1532   mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
1533   walk_data.global_data = &mark_def_sites_global_data;
1534
1535   /* We do not have any local data.  */
1536   walk_data.block_local_data_size = 0;
1537
1538   /* Initialize the dominator walker.  */
1539   init_walk_dominator_tree (&walk_data);
1540
1541   /* Recursively walk the dominator tree.  */
1542   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1543
1544   /* Finalize the dominator walker.  */
1545   fini_walk_dominator_tree (&walk_data);
1546
1547   /* We no longer need this bitmap, clear and free it.  */
1548   BITMAP_FREE (mark_def_sites_global_data.kills);
1549 }
1550
1551
1552 /* Main entry point into the SSA builder.  The renaming process
1553    proceeds in five main phases:
1554
1555    1- If VARS_TO_RENAME has any entries, any existing PHI nodes for
1556       those variables are removed from the flow graph so that they can
1557       be computed again.
1558
1559    2- Compute dominance frontier and immediate dominators, needed to
1560       insert PHI nodes and rename the function in dominator tree
1561       order.
1562
1563    3- Find and mark all the blocks that define variables
1564       (mark_def_site_blocks).
1565
1566    4- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
1567
1568    5- Rename all the blocks (rewrite_blocks) and statements in the program.
1569
1570    Steps 3 and 5 are done using the dominator tree walker
1571    (walk_dominator_tree).
1572
1573    ALL is true if all variables should be renamed (otherwise just those
1574    mentioned in vars_to_rename are taken into account).  */
1575
1576 void
1577 rewrite_into_ssa (bool all)
1578 {
1579   bitmap *dfs;
1580   basic_block bb;
1581   bitmap old_vars_to_rename = vars_to_rename;
1582   
1583   timevar_push (TV_TREE_SSA_OTHER);
1584
1585   if (all)
1586     vars_to_rename = NULL;
1587   else
1588     {
1589       /* Initialize the array of variables to rename.  */
1590       gcc_assert (vars_to_rename);
1591
1592       if (bitmap_empty_p (vars_to_rename))
1593         {
1594           timevar_pop (TV_TREE_SSA_OTHER);
1595           return;
1596         }
1597       
1598       invalidate_name_tags (vars_to_rename);
1599
1600       /* Now remove all the existing PHI nodes (if any) for the variables
1601          that we are about to rename into SSA.  */
1602       remove_all_phi_nodes_for (vars_to_rename);
1603     }
1604
1605   mark_def_site_blocks ();
1606
1607   /* Initialize dominance frontier and immediate dominator bitmaps. 
1608      Also count the number of predecessors for each block.  Doing so
1609      can save significant time during PHI insertion for large graphs.  */
1610   dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
1611   FOR_EACH_BB (bb)
1612     dfs[bb->index] = BITMAP_ALLOC (NULL);
1613
1614   /* Compute dominance frontiers.  */
1615   compute_dominance_frontiers (dfs);
1616
1617   /* Insert PHI nodes at dominance frontiers of definition blocks.  */
1618   insert_phi_nodes (dfs, NULL);
1619
1620   rewrite_blocks (false);
1621
1622   /* Free allocated memory.  */
1623   FOR_EACH_BB (bb)
1624     BITMAP_FREE (dfs[bb->index]);
1625   free (dfs);
1626
1627   vars_to_rename = old_vars_to_rename;
1628   timevar_pop (TV_TREE_SSA_OTHER);
1629 }
1630
1631 /* Rewrite the def-def chains so that they have the correct reaching
1632    definitions.  */
1633
1634 void
1635 rewrite_def_def_chains (void)
1636 {
1637   /* Ensure that the dominance information is OK.  */
1638   calculate_dominance_info (CDI_DOMINATORS);
1639   mark_def_site_blocks ();
1640   rewrite_blocks (true);
1641
1642 }
1643 /* The marked ssa names may have more than one definition;
1644    add phi nodes and rewrite them to fix this.  */
1645
1646 void
1647 rewrite_ssa_into_ssa (void)
1648 {
1649   bitmap *dfs;
1650   basic_block bb;
1651   struct dom_walk_data walk_data;
1652   struct mark_def_sites_global_data mark_def_sites_global_data;
1653   unsigned i;
1654   sbitmap snames_to_rename;
1655   bitmap to_rename;
1656   bitmap_iterator bi;
1657   
1658   if (!any_marked_for_rewrite_p ())
1659     return;
1660   to_rename = marked_ssa_names ();
1661
1662   timevar_push (TV_TREE_SSA_OTHER);
1663
1664   /* Allocate memory for the DEF_BLOCKS hash table.  */
1665   def_blocks = htab_create (num_ssa_names,
1666                             def_blocks_hash, def_blocks_eq, def_blocks_free);
1667
1668   /* Initialize dominance frontier and immediate dominator bitmaps. 
1669      Also count the number of predecessors for each block.  Doing so
1670      can save significant time during PHI insertion for large graphs.  */
1671   dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
1672   FOR_EACH_BB (bb)
1673     dfs[bb->index] = BITMAP_ALLOC (NULL);
1674
1675   /* Ensure that the dominance information is OK.  */
1676   calculate_dominance_info (CDI_DOMINATORS);
1677
1678   /* Compute dominance frontiers.  */
1679   compute_dominance_frontiers (dfs);
1680
1681   /* Setup callbacks for the generic dominator tree walker to find and
1682      mark definition sites.  */
1683   walk_data.walk_stmts_backward = false;
1684   walk_data.dom_direction = CDI_DOMINATORS;
1685   walk_data.initialize_block_local_data = NULL;
1686   walk_data.before_dom_children_before_stmts
1687           = ssa_mark_def_sites_initialize_block;
1688   walk_data.before_dom_children_walk_stmts = ssa_mark_def_sites;
1689   walk_data.before_dom_children_after_stmts = ssa_mark_phi_uses; 
1690   walk_data.after_dom_children_before_stmts =  NULL;
1691   walk_data.after_dom_children_walk_stmts =  NULL;
1692   walk_data.after_dom_children_after_stmts =  NULL;
1693
1694   snames_to_rename = sbitmap_alloc (num_ssa_names);
1695   sbitmap_zero (snames_to_rename);
1696   EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, bi)
1697     {
1698       SET_BIT (snames_to_rename, i);
1699       set_current_def (ssa_name (i), NULL_TREE);
1700     }
1701
1702   mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
1703   mark_def_sites_global_data.names_to_rename = snames_to_rename;
1704   walk_data.global_data = &mark_def_sites_global_data;
1705
1706   block_defs_stack = VEC_alloc (tree_on_heap, 10);
1707
1708   /* We do not have any local data.  */
1709   walk_data.block_local_data_size = 0;
1710
1711   /* Initialize the dominator walker.  */
1712   init_walk_dominator_tree (&walk_data);
1713
1714   /* Recursively walk the dominator tree.  */
1715   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1716
1717   /* Finalize the dominator walker.  */
1718   fini_walk_dominator_tree (&walk_data);
1719
1720   /* We no longer need this bitmap, clear and free it.  */
1721   BITMAP_FREE (mark_def_sites_global_data.kills);
1722
1723   /* Insert PHI nodes at dominance frontiers of definition blocks.  */
1724   insert_phi_nodes (dfs, to_rename);
1725
1726   /* Rewrite all the basic blocks in the program.  */
1727   timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
1728
1729   /* Setup callbacks for the generic dominator tree walker.  */
1730   walk_data.walk_stmts_backward = false;
1731   walk_data.dom_direction = CDI_DOMINATORS;
1732   walk_data.initialize_block_local_data = NULL;
1733   walk_data.before_dom_children_before_stmts = ssa_rewrite_initialize_block;
1734   walk_data.before_dom_children_walk_stmts = ssa_rewrite_stmt;
1735   walk_data.before_dom_children_after_stmts = ssa_rewrite_phi_arguments;
1736   walk_data.after_dom_children_before_stmts = NULL;
1737   walk_data.after_dom_children_walk_stmts =  NULL;
1738   walk_data.after_dom_children_after_stmts =  ssa_rewrite_finalize_block;
1739   walk_data.global_data = snames_to_rename;
1740   walk_data.block_local_data_size = 0;
1741
1742   /* Initialize the dominator walker.  */
1743   init_walk_dominator_tree (&walk_data);
1744
1745   /* Recursively walk the dominator tree rewriting each statement in
1746      each basic block.  */
1747   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1748
1749   /* Finalize the dominator walker.  */
1750   fini_walk_dominator_tree (&walk_data);
1751
1752   unmark_all_for_rewrite ();
1753
1754   EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, bi)
1755     {
1756       /* Free SSA_NAME_AUX.  We don't have to zero it because
1757          release_ssa_name will.  */
1758       if (SSA_NAME_AUX (ssa_name (i)))
1759         free (SSA_NAME_AUX (ssa_name (i)));
1760
1761       release_ssa_name (ssa_name (i));
1762     }
1763
1764   sbitmap_free (snames_to_rename);
1765
1766   timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
1767
1768   /* Debugging dumps.  */
1769   if (dump_file && (dump_flags & TDF_STATS))
1770     {
1771       dump_dfa_stats (dump_file);
1772       dump_tree_ssa_stats (dump_file);
1773     }
1774
1775   /* Free allocated memory.  */
1776   FOR_EACH_BB (bb)
1777     BITMAP_FREE (dfs[bb->index]);
1778   free (dfs);
1779
1780   htab_delete (def_blocks);
1781
1782 #ifdef ENABLE_CHECKING
1783   for (i = 1; i < num_ssa_names; i++)
1784     {
1785       tree name = ssa_name (i);
1786       if (!name)
1787         continue;
1788
1789       gcc_assert (SSA_NAME_AUX (name) == NULL);
1790     }
1791 #endif
1792
1793   BITMAP_FREE (to_rename);
1794   
1795   VEC_free (tree_on_heap, block_defs_stack);
1796   block_defs_stack = NULL;
1797   timevar_pop (TV_TREE_SSA_OTHER);
1798 }
1799
1800 /* Rewrites all variables into ssa.  */
1801
1802 static void
1803 rewrite_all_into_ssa (void)
1804 {
1805   rewrite_into_ssa (true);
1806 }
1807
1808 struct tree_opt_pass pass_build_ssa = 
1809 {
1810   "ssa",                                /* name */
1811   NULL,                                 /* gate */
1812   rewrite_all_into_ssa,                 /* execute */
1813   NULL,                                 /* sub */
1814   NULL,                                 /* next */
1815   0,                                    /* static_pass_number */
1816   0,                                    /* tv_id */
1817   PROP_cfg | PROP_referenced_vars,      /* properties_required */
1818   PROP_ssa,                             /* properties_provided */
1819   0,                                    /* properties_destroyed */
1820   0,                                    /* todo_flags_start */
1821   TODO_dump_func | TODO_verify_ssa,                     /* todo_flags_finish */
1822   0                                     /* letter */
1823 };