OSDN Git Service

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