OSDN Git Service

PR tree-optimization/20204
[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 }
596
597
598 /* Helper for insert_phi_nodes.  If VAR needs PHI nodes, insert them
599    at the dominance frontier (DFS) of blocks defining VAR.  */
600
601 static inline void
602 insert_phi_nodes_1 (tree var, bitmap *dfs)
603 {
604   struct def_blocks_d *def_map;
605   bitmap idf;
606
607   def_map = find_def_blocks_for (var);
608   if (def_map == NULL)
609     return;
610
611   idf = find_idf (def_map->def_blocks, dfs);
612
613   if (get_phi_state (var) != NEED_PHI_STATE_NO)
614     insert_phi_nodes_for (var, idf);
615
616   BITMAP_FREE (idf);
617 }
618
619
620 /* Insert PHI nodes at the dominance frontier of blocks with variable
621    definitions.  DFS contains the dominance frontier information for
622    the flowgraph.  PHI nodes will only be inserted at the dominance
623    frontier of definition blocks for variables whose NEED_PHI_STATE
624    annotation is marked as ``maybe'' or ``unknown'' (computed by
625    mark_def_sites).  If NAMES_TO_RENAME is not NULL, do the same but
626    for ssa name rewriting.  */
627
628 static void
629 insert_phi_nodes (bitmap *dfs, bitmap names_to_rename)
630 {
631   unsigned i;
632   bitmap_iterator bi;
633
634   timevar_push (TV_TREE_INSERT_PHI_NODES);
635
636   /* Iterate over all variables in VARS_TO_RENAME.  For each variable, add
637      to the work list all the blocks that have a definition for the
638      variable.  PHI nodes will be added to the dominance frontier blocks of
639      each definition block.  */
640   if (names_to_rename)
641     {
642       EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
643         if (ssa_name (i))
644           insert_phi_nodes_1 (ssa_name (i), dfs);
645     }
646   else if (vars_to_rename)
647     {
648       EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i, bi)
649         insert_phi_nodes_1 (referenced_var (i), dfs);
650     }
651   else
652     {
653       for (i = 0; i < num_referenced_vars; i++)
654         insert_phi_nodes_1 (referenced_var (i), dfs);
655     }
656
657   timevar_pop (TV_TREE_INSERT_PHI_NODES);
658 }
659
660
661 /* Register DEF (an SSA_NAME) to be a new definition for its underlying
662    variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition
663    into the stack pointed by BLOCK_DEFS_P.  */
664
665 void
666 register_new_def (tree def, VEC (tree_on_heap) **block_defs_p)
667 {
668   tree var = SSA_NAME_VAR (def);
669   tree currdef;
670    
671   /* If this variable is set in a single basic block and all uses are
672      dominated by the set(s) in that single basic block, then there is
673      no reason to record anything for this variable in the block local
674      definition stacks.  Doing so just wastes time and memory.
675
676      This is the same test to prune the set of variables which may
677      need PHI nodes.  So we just use that information since it's already
678      computed and available for us to use.  */
679   if (get_phi_state (var) == NEED_PHI_STATE_NO)
680     {
681       set_current_def (var, def);
682       return;
683     }
684
685   currdef = get_current_def (var);
686
687   /* Push the current reaching definition into *BLOCK_DEFS_P.  This stack is
688      later used by the dominator tree callbacks to restore the reaching
689      definitions for all the variables defined in the block after a recursive
690      visit to all its immediately dominated blocks.  If there is no current
691      reaching definition, then just record the underlying _DECL node.  */
692   VEC_safe_push (tree_on_heap, *block_defs_p, currdef ? currdef : var);
693
694   /* Set the current reaching definition for VAR to be DEF.  */
695   set_current_def (var, def);
696 }
697
698
699 /* Perform a depth-first traversal of the dominator tree looking for
700    variables to rename.  BB is the block where to start searching.
701    Renaming is a five step process:
702
703    1- Every definition made by PHI nodes at the start of the blocks is
704       registered as the current definition for the corresponding variable.
705
706    2- Every statement in BB is rewritten.  USE and VUSE operands are
707       rewritten with their corresponding reaching definition.  DEF and
708       VDEF targets are registered as new definitions.
709       
710    3- All the PHI nodes in successor blocks of BB are visited.  The
711       argument corresponding to BB is replaced with its current reaching
712       definition.
713
714    4- Recursively rewrite every dominator child block of BB.
715
716    5- Restore (in reverse order) the current reaching definition for every
717       new definition introduced in this block.  This is done so that when
718       we return from the recursive call, all the current reaching
719       definitions are restored to the names that were valid in the
720       dominator parent of BB.  */
721
722 /* SSA Rewriting Step 1.  Initialization, create a block local stack
723    of reaching definitions for new SSA names produced in this block
724    (BLOCK_DEFS).  Register new definitions for every PHI node in the
725    block.  */
726
727 static void
728 rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
729                           basic_block bb)
730 {
731   tree phi;
732
733   if (dump_file && (dump_flags & TDF_DETAILS))
734     fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
735
736   /* Mark the unwind point for this block.  */
737   VEC_safe_push (tree_on_heap, block_defs_stack, NULL_TREE);
738
739   /* Step 1.  Register new definitions for every PHI node in the block.
740      Conceptually, all the PHI nodes are executed in parallel and each PHI
741      node introduces a new version for the associated variable.  */
742   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
743     {
744       tree result = PHI_RESULT (phi);
745       register_new_def (result, &block_defs_stack);
746     }
747 }
748
749
750 /* Return the current definition for variable VAR.  If none is found,
751    create a new SSA name to act as the zeroth definition for VAR.  If VAR
752    is call clobbered and there exists a more recent definition of
753    GLOBAL_VAR, return the definition for GLOBAL_VAR.  This means that VAR
754    has been clobbered by a function call since its last assignment.  */
755
756 static tree
757 get_reaching_def (tree var)
758 {
759   tree default_d, currdef_var, avar;
760   
761   /* Lookup the current reaching definition for VAR.  */
762   default_d = NULL_TREE;
763   currdef_var = get_current_def (var);
764
765   /* If there is no reaching definition for VAR, create and register a
766      default definition for it (if needed).  */
767   if (currdef_var == NULL_TREE)
768     {
769       if (TREE_CODE (var) == SSA_NAME)
770         avar = SSA_NAME_VAR (var);
771       else
772         avar = var;
773
774       default_d = default_def (avar);
775       if (default_d == NULL_TREE)
776         {
777           default_d = make_ssa_name (avar, build_empty_stmt ());
778           set_default_def (avar, default_d);
779         }
780       set_current_def (var, default_d);
781     }
782
783   /* Return the current reaching definition for VAR, or the default
784      definition, if we had to create one.  */
785   return (currdef_var) ? currdef_var : default_d;
786 }
787
788
789 /* Replace the operand pointed by OP_P with its immediate reaching
790    definition.  */
791
792 static inline void
793 rewrite_operand (use_operand_p op_p)
794 {
795   tree var = USE_FROM_PTR (op_p);
796   if (TREE_CODE (var) != SSA_NAME)
797     SET_USE (op_p, get_reaching_def (var));
798   else
799     {
800 #if defined ENABLE_CHECKING
801       /* If we get to this point, VAR is an SSA_NAME.  If VAR's symbol
802          was marked for renaming, make sure that its reaching
803          definition is VAR itself.  Otherwise, something has gone
804          wrong.  */
805       tree sym = SSA_NAME_VAR (var);
806       if (bitmap_bit_p (vars_to_rename, var_ann (sym)->uid))
807         gcc_assert (var == get_reaching_def (SSA_NAME_VAR (var)));
808 #endif
809     }
810 }
811
812
813 /* SSA Rewriting Step 2.  Rewrite every variable used in each statement in
814    the block with its immediate reaching definitions.  Update the current
815    definition of a variable when a new real or virtual definition is found.  */
816
817 static void
818 rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
819               basic_block bb ATTRIBUTE_UNUSED,
820               block_stmt_iterator si)
821 {
822   stmt_ann_t ann;
823   tree stmt;
824   use_operand_p use_p;
825   def_operand_p def_p;
826   ssa_op_iter iter;
827
828   stmt = bsi_stmt (si);
829   ann = stmt_ann (stmt);
830
831   /* If mark_def_sites decided that we don't need to rewrite this
832      statement, ignore it.  */
833   if (!REWRITE_THIS_STMT (stmt))
834     return;
835
836   if (dump_file && (dump_flags & TDF_DETAILS))
837     {
838       fprintf (dump_file, "Renaming statement ");
839       print_generic_stmt (dump_file, stmt, TDF_SLIM);
840       fprintf (dump_file, "\n");
841     }
842
843   get_stmt_operands (stmt);
844
845   /* Step 1.  Rewrite USES and VUSES in the statement.  */
846   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
847     rewrite_operand (use_p);
848
849   /* Step 2.  Register the statement's DEF and VDEF operands.  */
850   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
851     {
852       if (TREE_CODE (DEF_FROM_PTR (def_p)) != SSA_NAME)
853         SET_DEF (def_p, make_ssa_name (DEF_FROM_PTR (def_p), stmt));
854
855       /* FIXME: We shouldn't be registering new defs if the variable
856          doesn't need to be renamed.  */
857       register_new_def (DEF_FROM_PTR (def_p), &block_defs_stack);
858     }
859 }
860
861
862 /* SSA Rewriting Step 3.  Visit all the successor blocks of BB looking for
863    PHI nodes.  For every PHI node found, add a new argument containing the
864    current reaching definition for the variable and the edge through which
865    that definition is reaching the PHI node.  */
866
867 static void
868 rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
869                            basic_block bb)
870 {
871   edge e;
872   edge_iterator ei;
873
874   FOR_EACH_EDGE (e, ei, bb->succs)
875     {
876       tree phi;
877
878       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
879         {
880           tree currdef;
881
882           /* If this PHI node has already been rewritten, then there is
883              nothing to do for this PHI or any following PHIs since we
884              always add new PHI nodes at the start of the PHI chain.  */
885           if (PHI_REWRITTEN (phi))
886             break;
887
888           currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
889           add_phi_arg (phi, currdef, e);
890         }
891     }
892 }
893
894
895 /*  Rewrite existing virtual PHI arguments so that they have the correct
896     reaching definitions.  BB is the basic block whose successors contain the
897     PHI nodes we want to add arguments for.  */
898
899 static void
900 rewrite_virtual_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
901                                basic_block bb)
902 {
903   edge e;
904   use_operand_p op;
905   edge_iterator ei;
906
907   FOR_EACH_EDGE (e, ei, bb->succs)
908     {
909       tree phi;
910
911       if (e->dest == EXIT_BLOCK_PTR)
912         continue;
913
914       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
915         {
916           tree result = PHI_RESULT (phi);
917           op = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
918           
919           if (is_gimple_reg (result) 
920               || !bitmap_bit_p (vars_to_rename, 
921                                 var_ann (SSA_NAME_VAR (result))->uid))
922             continue;
923
924           SET_USE (op, get_reaching_def (SSA_NAME_VAR (result)));
925           if (e->flags & EDGE_ABNORMAL)
926             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (op)) = 1;
927         }
928     }
929 }
930
931
932 /* Called after visiting basic block BB.  Restore CURRDEFS to its
933    original value.  */
934
935 static void
936 rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
937                         basic_block bb ATTRIBUTE_UNUSED)
938 {
939   /* Restore CURRDEFS to its original state.  */
940   while (VEC_length (tree_on_heap, block_defs_stack) > 0)
941     {
942       tree tmp = VEC_pop (tree_on_heap, block_defs_stack);
943       tree saved_def, var;
944
945       if (tmp == NULL_TREE)
946         break;
947
948       /* If we recorded an SSA_NAME, then make the SSA_NAME the current
949          definition of its underlying variable.  If we recorded anything
950          else, it must have been an _DECL node and its current reaching
951          definition must have been NULL.  */
952       if (TREE_CODE (tmp) == SSA_NAME)
953         {
954           saved_def = tmp;
955           var = SSA_NAME_VAR (saved_def);
956         }
957       else
958         {
959           saved_def = NULL;
960           var = tmp;
961         }
962                                                                                 
963       set_current_def (var, saved_def);
964     }
965 }
966
967
968 /* Dump SSA information to FILE.  */
969
970 void
971 dump_tree_ssa (FILE *file)
972 {
973   basic_block bb;
974   const char *funcname
975     = lang_hooks.decl_printable_name (current_function_decl, 2);
976
977   fprintf (file, "SSA information for %s\n\n", funcname);
978
979   FOR_EACH_BB (bb)
980     {
981       dump_bb (bb, file, 0);
982       fputs ("    ", file);
983       print_generic_stmt (file, phi_nodes (bb), dump_flags);
984       fputs ("\n\n", file);
985     }
986 }
987
988
989 /* Dump SSA information to stderr.  */
990
991 void
992 debug_tree_ssa (void)
993 {
994   dump_tree_ssa (stderr);
995 }
996
997
998 /* Dump statistics for the hash table HTAB.  */
999
1000 static void
1001 htab_statistics (FILE *file, htab_t htab)
1002 {
1003   fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1004            (long) htab_size (htab),
1005            (long) htab_elements (htab),
1006            htab_collisions (htab));
1007 }
1008
1009
1010 /* Dump SSA statistics on FILE.  */
1011
1012 void
1013 dump_tree_ssa_stats (FILE *file)
1014 {
1015   fprintf (file, "\nHash table statistics:\n");
1016
1017   fprintf (file, "    def_blocks: ");
1018   htab_statistics (file, def_blocks);
1019
1020   fprintf (file, "\n");
1021 }
1022
1023
1024 /* Dump SSA statistics on stderr.  */
1025
1026 void
1027 debug_tree_ssa_stats (void)
1028 {
1029   dump_tree_ssa_stats (stderr);
1030 }
1031
1032
1033 /* Hashing and equality functions for DEF_BLOCKS.  */
1034
1035 static hashval_t
1036 def_blocks_hash (const void *p)
1037 {
1038   return htab_hash_pointer
1039         ((const void *)((const struct def_blocks_d *)p)->var);
1040 }
1041
1042 static int
1043 def_blocks_eq (const void *p1, const void *p2)
1044 {
1045   return ((const struct def_blocks_d *)p1)->var
1046          == ((const struct def_blocks_d *)p2)->var;
1047 }
1048
1049
1050 /* Free memory allocated by one entry in DEF_BLOCKS.  */
1051
1052 static void
1053 def_blocks_free (void *p)
1054 {
1055   struct def_blocks_d *entry = p;
1056   BITMAP_FREE (entry->def_blocks);
1057   BITMAP_FREE (entry->phi_blocks);
1058   BITMAP_FREE (entry->livein_blocks);
1059   free (entry);
1060 }
1061
1062
1063 /* Callback for htab_traverse to dump the DEF_BLOCKS hash table.  */
1064
1065 static int
1066 debug_def_blocks_r (void **slot, void *data ATTRIBUTE_UNUSED)
1067 {
1068   struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
1069   
1070   fprintf (stderr, "VAR: ");
1071   print_generic_expr (stderr, db_p->var, dump_flags);
1072   bitmap_print (stderr, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
1073   bitmap_print (stderr, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}\n");
1074
1075   return 1;
1076 }
1077
1078
1079 /* Dump the DEF_BLOCKS hash table on stderr.  */
1080
1081 void
1082 debug_def_blocks (void)
1083 {
1084   htab_traverse (def_blocks, debug_def_blocks_r, NULL);
1085 }
1086
1087
1088 /* If a variable V in VARS_TO_RENAME is a pointer, the renaming
1089    process will cause us to lose the name memory tags that may have
1090    been associated with the various SSA_NAMEs of V.  This means that
1091    the variables aliased to those name tags also need to be renamed
1092    again.
1093
1094    FIXME 1- We should either have a better scheme for renaming
1095             pointers that doesn't lose name tags or re-run alias
1096             analysis to recover points-to information.
1097
1098          2- Currently we just invalidate *all* the name tags.  This
1099             should be more selective.  */
1100
1101 static void
1102 invalidate_name_tags (bitmap vars_to_rename)
1103 {
1104   unsigned i;
1105   bool rename_name_tags_p;
1106   bitmap_iterator bi;
1107
1108   rename_name_tags_p = false;
1109   EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i, bi)
1110     {
1111       if (POINTER_TYPE_P (TREE_TYPE (referenced_var (i))))
1112         {
1113           rename_name_tags_p = true;
1114           break;
1115         }
1116     }
1117
1118   if (rename_name_tags_p)
1119     for (i = 0; i < num_referenced_vars; i++)
1120       {
1121         var_ann_t ann = var_ann (referenced_var (i));
1122
1123         if (ann->mem_tag_kind == NAME_TAG)
1124           {
1125             size_t j;
1126             varray_type may_aliases = ann->may_aliases;
1127
1128             bitmap_set_bit (vars_to_rename, ann->uid);
1129             if (ann->may_aliases)
1130               for (j = 0; j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
1131                 {
1132                   tree var = VARRAY_TREE (may_aliases, j);
1133                   bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1134                 }
1135           }
1136       }
1137 }
1138
1139
1140 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
1141    form.  FIX_VIRTUAL_PHIS is true if we should only be fixing up virtual
1142    PHI arguments, instead of adding new PHI arguments for just added PHI
1143    nodes.  */
1144
1145 static void
1146 rewrite_blocks (bool fix_virtual_phis)
1147 {
1148   struct dom_walk_data walk_data;
1149   
1150   /* Rewrite all the basic blocks in the program.  */
1151   timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
1152
1153   /* Setup callbacks for the generic dominator tree walker.  */
1154   walk_data.walk_stmts_backward = false;
1155   walk_data.dom_direction = CDI_DOMINATORS;
1156   walk_data.initialize_block_local_data = NULL;
1157   walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
1158   walk_data.before_dom_children_walk_stmts = rewrite_stmt;
1159   walk_data.before_dom_children_after_stmts = NULL;
1160   if (!fix_virtual_phis)
1161     walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
1162   else
1163     walk_data.before_dom_children_after_stmts = rewrite_virtual_phi_arguments;
1164   
1165   walk_data.after_dom_children_before_stmts =  NULL;
1166   walk_data.after_dom_children_walk_stmts =  NULL;
1167   walk_data.after_dom_children_after_stmts =  rewrite_finalize_block;
1168   walk_data.global_data = NULL;
1169   walk_data.block_local_data_size = 0;
1170
1171   block_defs_stack = VEC_alloc (tree_on_heap, 10);
1172
1173   /* Initialize the dominator walker.  */
1174   init_walk_dominator_tree (&walk_data);
1175
1176   /* Recursively walk the dominator tree rewriting each statement in
1177      each basic block.  */
1178   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1179
1180   /* Finalize the dominator walker.  */
1181   fini_walk_dominator_tree (&walk_data);
1182
1183   /* Debugging dumps.  */
1184   if (dump_file && (dump_flags & TDF_STATS))
1185     {
1186       dump_dfa_stats (dump_file);
1187       dump_tree_ssa_stats (dump_file);
1188     }
1189
1190   htab_delete (def_blocks);
1191   def_blocks = NULL;
1192   
1193   VEC_free (tree_on_heap, block_defs_stack);
1194   block_defs_stack = NULL;
1195
1196   timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
1197 }
1198
1199
1200 /* Block initialization routine for mark_def_sites.  Clear the 
1201    KILLS bitmap at the start of each block.  */
1202
1203 static void
1204 mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
1205                                  basic_block bb ATTRIBUTE_UNUSED)
1206 {
1207   struct mark_def_sites_global_data *gd = walk_data->global_data;
1208   bitmap kills = gd->kills;
1209   bitmap_clear (kills);
1210 }
1211
1212
1213 /* Mark the definition site blocks for each variable, so that we know where
1214    the variable is actually live.  */
1215
1216 static void 
1217 mark_def_site_blocks (void)
1218 {
1219   size_t i;
1220   struct dom_walk_data walk_data;
1221   struct mark_def_sites_global_data mark_def_sites_global_data;
1222
1223   /* Allocate memory for the DEF_BLOCKS hash table.  */
1224   def_blocks = htab_create (VARRAY_ACTIVE_SIZE (referenced_vars),
1225                             def_blocks_hash, def_blocks_eq, def_blocks_free);
1226
1227   for (i = 0; i < num_referenced_vars; i++)
1228     set_current_def (referenced_var (i), NULL_TREE);
1229
1230   /* Ensure that the dominance information is OK.  */
1231   calculate_dominance_info (CDI_DOMINATORS);
1232
1233   /* Setup callbacks for the generic dominator tree walker to find and
1234      mark definition sites.  */
1235   walk_data.walk_stmts_backward = false;
1236   walk_data.dom_direction = CDI_DOMINATORS;
1237   walk_data.initialize_block_local_data = NULL;
1238   walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block;
1239   walk_data.before_dom_children_walk_stmts = mark_def_sites;
1240   walk_data.before_dom_children_after_stmts = NULL; 
1241   walk_data.after_dom_children_before_stmts =  NULL;
1242   walk_data.after_dom_children_walk_stmts =  NULL;
1243   walk_data.after_dom_children_after_stmts =  NULL;
1244
1245   /* Notice that this bitmap is indexed using variable UIDs, so it must be
1246      large enough to accommodate all the variables referenced in the
1247      function, not just the ones we are renaming.  */
1248   mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
1249   walk_data.global_data = &mark_def_sites_global_data;
1250
1251   /* We do not have any local data.  */
1252   walk_data.block_local_data_size = 0;
1253
1254   /* Initialize the dominator walker.  */
1255   init_walk_dominator_tree (&walk_data);
1256
1257   /* Recursively walk the dominator tree.  */
1258   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1259
1260   /* Finalize the dominator walker.  */
1261   fini_walk_dominator_tree (&walk_data);
1262
1263   /* We no longer need this bitmap, clear and free it.  */
1264   BITMAP_FREE (mark_def_sites_global_data.kills);
1265 }
1266
1267
1268 /* Main entry point into the SSA builder.  The renaming process
1269    proceeds in five main phases:
1270
1271    1- If VARS_TO_RENAME has any entries, any existing PHI nodes for
1272       those variables are removed from the flow graph so that they can
1273       be computed again.
1274
1275    2- Compute dominance frontier and immediate dominators, needed to
1276       insert PHI nodes and rename the function in dominator tree
1277       order.
1278
1279    3- Find and mark all the blocks that define variables
1280       (mark_def_site_blocks).
1281
1282    4- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
1283
1284    5- Rename all the blocks (rewrite_blocks) and statements in the program.
1285
1286    Steps 3 and 5 are done using the dominator tree walker
1287    (walk_dominator_tree).
1288
1289    ALL is true if all variables should be renamed (otherwise just those
1290    mentioned in vars_to_rename are taken into account).  */
1291
1292 void
1293 rewrite_into_ssa (bool all)
1294 {
1295   bitmap *dfs;
1296   basic_block bb;
1297   bitmap old_vars_to_rename = vars_to_rename;
1298   
1299   timevar_push (TV_TREE_SSA_OTHER);
1300
1301   if (all)
1302     vars_to_rename = NULL;
1303   else
1304     {
1305       /* Initialize the array of variables to rename.  */
1306       gcc_assert (vars_to_rename);
1307
1308       if (bitmap_empty_p (vars_to_rename))
1309         {
1310           timevar_pop (TV_TREE_SSA_OTHER);
1311           return;
1312         }
1313       
1314       invalidate_name_tags (vars_to_rename);
1315
1316       /* Now remove all the existing PHI nodes (if any) for the variables
1317          that we are about to rename into SSA.  */
1318       remove_all_phi_nodes_for (vars_to_rename);
1319     }
1320
1321   mark_def_site_blocks ();
1322
1323   /* Initialize dominance frontier and immediate dominator bitmaps. 
1324      Also count the number of predecessors for each block.  Doing so
1325      can save significant time during PHI insertion for large graphs.  */
1326   dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
1327   FOR_EACH_BB (bb)
1328     dfs[bb->index] = BITMAP_ALLOC (NULL);
1329
1330   /* Compute dominance frontiers.  */
1331   compute_dominance_frontiers (dfs);
1332
1333   /* Insert PHI nodes at dominance frontiers of definition blocks.  */
1334   insert_phi_nodes (dfs, NULL);
1335
1336   rewrite_blocks (false);
1337
1338   /* Free allocated memory.  */
1339   FOR_EACH_BB (bb)
1340     BITMAP_FREE (dfs[bb->index]);
1341   free (dfs);
1342
1343   vars_to_rename = old_vars_to_rename;
1344   timevar_pop (TV_TREE_SSA_OTHER);
1345 }
1346
1347
1348 /* Rewrites all variables into SSA.  */
1349
1350 static void
1351 rewrite_all_into_ssa (void)
1352 {
1353   rewrite_into_ssa (true);
1354 }
1355
1356 struct tree_opt_pass pass_build_ssa = 
1357 {
1358   "ssa",                                /* name */
1359   NULL,                                 /* gate */
1360   rewrite_all_into_ssa,                 /* execute */
1361   NULL,                                 /* sub */
1362   NULL,                                 /* next */
1363   0,                                    /* static_pass_number */
1364   0,                                    /* tv_id */
1365   PROP_cfg | PROP_referenced_vars,      /* properties_required */
1366   PROP_ssa,                             /* properties_provided */
1367   0,                                    /* properties_destroyed */
1368   0,                                    /* todo_flags_start */
1369   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
1370   0                                     /* letter */
1371 };
1372
1373
1374 /* Rewrite the def-def chains of virtual operands so that they have
1375    the correct reaching definitions.  */
1376
1377 void
1378 rewrite_def_def_chains (void)
1379 {
1380   /* Ensure that the dominance information is OK.  */
1381   calculate_dominance_info (CDI_DOMINATORS);
1382   mark_def_site_blocks ();
1383   rewrite_blocks (true);
1384 }
1385
1386
1387
1388 /*---------------------------------------------------------------------------
1389     Functions to fix a program in invalid SSA form into valid SSA
1390     form.  The main entry point here is rewrite_ssa_into_ssa.
1391 ---------------------------------------------------------------------------*/
1392
1393 /* Called after visiting basic block BB.  Restore CURRDEFS to its
1394    original value.  */
1395
1396 static void
1397 ssa_rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1398                             basic_block bb ATTRIBUTE_UNUSED)
1399 {
1400
1401   /* Step 5.  Restore the current reaching definition for each variable
1402      referenced in the block (in reverse order).  */
1403   while (VEC_length (tree_on_heap, block_defs_stack) > 0)
1404     {
1405       tree var = VEC_pop (tree_on_heap, block_defs_stack);
1406       tree saved_def;
1407       
1408       if (var == NULL)
1409         break;
1410
1411       saved_def = VEC_pop (tree_on_heap, block_defs_stack);
1412       set_current_def (var, saved_def);
1413     }
1414 }
1415
1416
1417 /* Register DEF (an SSA_NAME) to be a new definition for the original
1418    ssa name VAR and push VAR's current reaching definition
1419    into the stack pointed by BLOCK_DEFS_P.  */
1420
1421 static void
1422 ssa_register_new_def (tree var, tree def)
1423 {
1424   tree currdef;
1425    
1426   /* If this variable is set in a single basic block and all uses are
1427      dominated by the set(s) in that single basic block, then there is
1428      nothing to do.  TODO we should not be called at all, and just
1429      keep the original name.  */
1430   if (get_phi_state (var) == NEED_PHI_STATE_NO)
1431     {
1432       set_current_def (var, def);
1433       return;
1434     }
1435
1436   currdef = get_current_def (var);
1437
1438   /* Push the current reaching definition into *BLOCK_DEFS_P.  This stack is
1439      later used by the dominator tree callbacks to restore the reaching
1440      definitions for all the variables defined in the block after a recursive
1441      visit to all its immediately dominated blocks.  */
1442   VEC_safe_push (tree_on_heap, block_defs_stack, currdef);
1443   VEC_safe_push (tree_on_heap, block_defs_stack, var);
1444
1445   /* Set the current reaching definition for VAR to be DEF.  */
1446   set_current_def (var, def);
1447 }
1448
1449
1450 /* Same as rewrite_stmt, for rewriting ssa names.  */
1451
1452 static void
1453 ssa_rewrite_stmt (struct dom_walk_data *walk_data,
1454                   basic_block bb ATTRIBUTE_UNUSED,
1455                   block_stmt_iterator si)
1456 {
1457   stmt_ann_t ann;
1458   tree stmt, var;
1459   ssa_op_iter iter;
1460   use_operand_p use_p;
1461   def_operand_p def_p;
1462   sbitmap names_to_rename = walk_data->global_data;
1463
1464   stmt = bsi_stmt (si);
1465   ann = stmt_ann (stmt);
1466
1467   if (dump_file && (dump_flags & TDF_DETAILS))
1468     {
1469       fprintf (dump_file, "Renaming statement ");
1470       print_generic_stmt (dump_file, stmt, TDF_SLIM);
1471       fprintf (dump_file, "\n");
1472     }
1473
1474   /* We have just scanned the code for operands.  No statement should
1475      be modified.  */
1476   gcc_assert (!ann->modified);
1477
1478   /* Step 1.  Rewrite USES and VUSES in the statement.  */
1479   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
1480     {
1481       if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (use_p))))
1482         SET_USE (use_p, get_reaching_def (USE_FROM_PTR (use_p)));
1483     }
1484
1485   /* Step 2.  Register the statement's DEF and VDEF operands.  */
1486   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1487     {
1488       var = DEF_FROM_PTR (def_p);
1489
1490       if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (var)))
1491         continue;
1492
1493       SET_DEF (def_p, duplicate_ssa_name (var, stmt));
1494       ssa_register_new_def (var, DEF_FROM_PTR (def_p));
1495     }
1496 }
1497
1498
1499 /* Ditto, for ssa name rewriting.  */
1500
1501 static void
1502 ssa_rewrite_phi_arguments (struct dom_walk_data *walk_data, basic_block bb)
1503 {
1504   edge e;
1505   sbitmap names_to_rename = walk_data->global_data;
1506   use_operand_p op;
1507   edge_iterator ei;
1508
1509   FOR_EACH_EDGE (e, ei, bb->succs)
1510     {
1511       tree phi;
1512
1513       if (e->dest == EXIT_BLOCK_PTR)
1514         continue;
1515
1516       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
1517         {
1518           op = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
1519           if (TREE_CODE (USE_FROM_PTR (op)) != SSA_NAME)
1520             continue;
1521           
1522           if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (op))))
1523             continue; 
1524
1525           SET_USE (op, get_reaching_def (USE_FROM_PTR (op)));
1526           if (e->flags & EDGE_ABNORMAL)
1527             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (op)) = 1;
1528         }
1529     }
1530 }
1531
1532 /* Ditto, for rewriting ssa names.  */
1533
1534 static void
1535 ssa_rewrite_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
1536 {
1537   tree phi, new_name;
1538   sbitmap names_to_rename = walk_data->global_data;
1539   edge e;
1540   bool abnormal_phi;
1541   edge_iterator ei;
1542
1543   if (dump_file && (dump_flags & TDF_DETAILS))
1544     fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
1545
1546   /* Mark the unwind point for this block.  */
1547   VEC_safe_push (tree_on_heap, block_defs_stack, NULL_TREE);
1548
1549   FOR_EACH_EDGE (e, ei, bb->preds)
1550     if (e->flags & EDGE_ABNORMAL)
1551       break;
1552   abnormal_phi = (e != NULL);
1553
1554   /* Step 1.  Register new definitions for every PHI node in the block.
1555      Conceptually, all the PHI nodes are executed in parallel and each PHI
1556      node introduces a new version for the associated variable.  */
1557   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1558     {
1559       tree result = PHI_RESULT (phi);
1560
1561       if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (result)))
1562         {
1563           new_name = duplicate_ssa_name (result, phi);
1564           SET_PHI_RESULT (phi, new_name);
1565
1566           if (abnormal_phi)
1567             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
1568           ssa_register_new_def (result, new_name);
1569         }
1570     }
1571 }
1572
1573
1574 /* Same as mark_def_sites, but works over SSA names.  */
1575
1576 static void
1577 ssa_mark_def_sites (struct dom_walk_data *walk_data,
1578                     basic_block bb,
1579                     block_stmt_iterator bsi)
1580 {
1581   struct mark_def_sites_global_data *gd = walk_data->global_data;
1582   bitmap kills = gd->kills;
1583   size_t uid, def_uid;
1584   tree stmt, use, def;
1585   ssa_op_iter iter;
1586
1587   /* Mark all the blocks that have definitions for each variable in the
1588      names_to_rename bitmap.  */
1589   stmt = bsi_stmt (bsi);
1590   get_stmt_operands (stmt);
1591
1592   /* If a variable is used before being set, then the variable is live
1593      across a block boundary, so mark it live-on-entry to BB.  */
1594   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
1595     {
1596       uid = SSA_NAME_VERSION (use);
1597
1598       if (TEST_BIT (gd->names_to_rename, uid)
1599           && !bitmap_bit_p (kills, uid))
1600         set_livein_block (use, bb);
1601     }
1602           
1603   /* Now process the definition made by this statement.  Mark the
1604      variables in KILLS.  */
1605   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
1606     {
1607       def_uid = SSA_NAME_VERSION (def);
1608
1609       if (TEST_BIT (gd->names_to_rename, def_uid))
1610         {
1611           set_def_block (def, bb, false, true);
1612           bitmap_set_bit (kills, def_uid);
1613         }
1614     }
1615 }
1616
1617
1618 /* Block initialization routine for mark_def_sites.  Clear the 
1619    KILLS bitmap at the start of each block.  */
1620
1621 static void
1622 ssa_mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
1623                                      basic_block bb)
1624 {
1625   struct mark_def_sites_global_data *gd = walk_data->global_data;
1626   bitmap kills = gd->kills;
1627   tree phi, def;
1628   unsigned def_uid;
1629
1630   bitmap_clear (kills);
1631
1632   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1633     {
1634       def = PHI_RESULT (phi);
1635       def_uid = SSA_NAME_VERSION (def);
1636
1637       if (!TEST_BIT (gd->names_to_rename, def_uid))
1638         continue;
1639
1640       set_def_block (def, bb, true, true);
1641       bitmap_set_bit (kills, def_uid);
1642     }
1643 }
1644
1645 /* Marks ssa names used as arguments of phis at the end of BB.  */
1646
1647 static void
1648 ssa_mark_phi_uses (struct dom_walk_data *walk_data, basic_block bb)
1649 {
1650   struct mark_def_sites_global_data *gd = walk_data->global_data;
1651   bitmap kills = gd->kills;
1652   edge e;
1653   tree phi, use;
1654   unsigned uid;
1655   edge_iterator ei;
1656
1657   FOR_EACH_EDGE (e, ei, bb->succs)
1658     {
1659       if (e->dest == EXIT_BLOCK_PTR)
1660         continue;
1661
1662       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
1663         {
1664           use = PHI_ARG_DEF_FROM_EDGE (phi, e);
1665           if (TREE_CODE (use) != SSA_NAME)
1666             continue;
1667
1668           uid = SSA_NAME_VERSION (use);
1669
1670           if (TEST_BIT (gd->names_to_rename, uid)
1671               && !bitmap_bit_p (kills, uid))
1672             set_livein_block (use, bb);
1673         }
1674     }
1675 }
1676        
1677    
1678 /* The marked ssa names may have more than one definition;
1679    add PHI nodes and rewrite them to fix this.  */
1680
1681 void
1682 rewrite_ssa_into_ssa (void)
1683 {
1684   bitmap *dfs;
1685   basic_block bb;
1686   struct dom_walk_data walk_data;
1687   struct mark_def_sites_global_data mark_def_sites_global_data;
1688   unsigned i;
1689   sbitmap snames_to_rename;
1690   bitmap to_rename;
1691   bitmap_iterator bi;
1692   
1693   if (!any_marked_for_rewrite_p ())
1694     return;
1695   to_rename = marked_ssa_names ();
1696
1697   timevar_push (TV_TREE_SSA_OTHER);
1698
1699   /* Allocate memory for the DEF_BLOCKS hash table.  */
1700   def_blocks = htab_create (num_ssa_names,
1701                             def_blocks_hash, def_blocks_eq, def_blocks_free);
1702
1703   /* Initialize dominance frontier and immediate dominator bitmaps. 
1704      Also count the number of predecessors for each block.  Doing so
1705      can save significant time during PHI insertion for large graphs.  */
1706   dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
1707   FOR_EACH_BB (bb)
1708     dfs[bb->index] = BITMAP_ALLOC (NULL);
1709
1710   /* Ensure that the dominance information is OK.  */
1711   calculate_dominance_info (CDI_DOMINATORS);
1712
1713   /* Compute dominance frontiers.  */
1714   compute_dominance_frontiers (dfs);
1715
1716   /* Setup callbacks for the generic dominator tree walker to find and
1717      mark definition sites.  */
1718   walk_data.walk_stmts_backward = false;
1719   walk_data.dom_direction = CDI_DOMINATORS;
1720   walk_data.initialize_block_local_data = NULL;
1721   walk_data.before_dom_children_before_stmts
1722           = ssa_mark_def_sites_initialize_block;
1723   walk_data.before_dom_children_walk_stmts = ssa_mark_def_sites;
1724   walk_data.before_dom_children_after_stmts = ssa_mark_phi_uses; 
1725   walk_data.after_dom_children_before_stmts =  NULL;
1726   walk_data.after_dom_children_walk_stmts =  NULL;
1727   walk_data.after_dom_children_after_stmts =  NULL;
1728
1729   snames_to_rename = sbitmap_alloc (num_ssa_names);
1730   sbitmap_zero (snames_to_rename);
1731   EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, bi)
1732     {
1733       SET_BIT (snames_to_rename, i);
1734       set_current_def (ssa_name (i), NULL_TREE);
1735     }
1736
1737   mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
1738   mark_def_sites_global_data.names_to_rename = snames_to_rename;
1739   walk_data.global_data = &mark_def_sites_global_data;
1740
1741   block_defs_stack = VEC_alloc (tree_on_heap, 10);
1742
1743   /* We do not have any local data.  */
1744   walk_data.block_local_data_size = 0;
1745
1746   /* Initialize the dominator walker.  */
1747   init_walk_dominator_tree (&walk_data);
1748
1749   /* Recursively walk the dominator tree.  */
1750   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1751
1752   /* Finalize the dominator walker.  */
1753   fini_walk_dominator_tree (&walk_data);
1754
1755   /* We no longer need this bitmap, clear and free it.  */
1756   BITMAP_FREE (mark_def_sites_global_data.kills);
1757
1758   /* Insert PHI nodes at dominance frontiers of definition blocks.  */
1759   insert_phi_nodes (dfs, to_rename);
1760
1761   /* Rewrite all the basic blocks in the program.  */
1762   timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
1763
1764   /* Setup callbacks for the generic dominator tree walker.  */
1765   walk_data.walk_stmts_backward = false;
1766   walk_data.dom_direction = CDI_DOMINATORS;
1767   walk_data.initialize_block_local_data = NULL;
1768   walk_data.before_dom_children_before_stmts = ssa_rewrite_initialize_block;
1769   walk_data.before_dom_children_walk_stmts = ssa_rewrite_stmt;
1770   walk_data.before_dom_children_after_stmts = ssa_rewrite_phi_arguments;
1771   walk_data.after_dom_children_before_stmts = NULL;
1772   walk_data.after_dom_children_walk_stmts =  NULL;
1773   walk_data.after_dom_children_after_stmts =  ssa_rewrite_finalize_block;
1774   walk_data.global_data = snames_to_rename;
1775   walk_data.block_local_data_size = 0;
1776
1777   /* Initialize the dominator walker.  */
1778   init_walk_dominator_tree (&walk_data);
1779
1780   /* Recursively walk the dominator tree rewriting each statement in
1781      each basic block.  */
1782   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1783
1784   /* Finalize the dominator walker.  */
1785   fini_walk_dominator_tree (&walk_data);
1786
1787   unmark_all_for_rewrite ();
1788
1789   EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, bi)
1790     {
1791       /* Free SSA_NAME_AUX.  We don't have to zero it because
1792          release_ssa_name will.  */
1793       if (SSA_NAME_AUX (ssa_name (i)))
1794         free (SSA_NAME_AUX (ssa_name (i)));
1795
1796       release_ssa_name (ssa_name (i));
1797     }
1798
1799   sbitmap_free (snames_to_rename);
1800
1801   timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
1802
1803   /* Debugging dumps.  */
1804   if (dump_file && (dump_flags & TDF_STATS))
1805     {
1806       dump_dfa_stats (dump_file);
1807       dump_tree_ssa_stats (dump_file);
1808     }
1809
1810   /* Free allocated memory.  */
1811   FOR_EACH_BB (bb)
1812     BITMAP_FREE (dfs[bb->index]);
1813   free (dfs);
1814
1815   htab_delete (def_blocks);
1816
1817 #ifdef ENABLE_CHECKING
1818   for (i = 1; i < num_ssa_names; i++)
1819     {
1820       tree name = ssa_name (i);
1821       if (!name)
1822         continue;
1823
1824       gcc_assert (SSA_NAME_AUX (name) == NULL);
1825     }
1826 #endif
1827
1828   BITMAP_FREE (to_rename);
1829   
1830   VEC_free (tree_on_heap, block_defs_stack);
1831   block_defs_stack = NULL;
1832   timevar_pop (TV_TREE_SSA_OTHER);
1833 }