1 /* Rewrite a program in Normal form into SSA.
2 Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
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)
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.
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. */
24 #include "coretypes.h"
30 #include "langhooks.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
37 #include "diagnostic.h"
39 #include "tree-flow.h"
40 #include "tree-simple.h"
41 #include "tree-inline.h"
44 #include "tree-alias-common.h"
46 #include "tree-dump.h"
47 #include "tree-pass.h"
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. */
58 /* Structure to map a variable VAR to the set of blocks that contain
59 definitions for VAR. */
65 /* Blocks that contain definitions of VAR. Bit I will be set if the
66 Ith block contains a definition of VAR. */
69 /* Blocks where VAR is live-on-entry. Similar semantics as
74 /* Each entry in DEF_BLOCKS contains an element of type STRUCT
75 DEF_BLOCKS_D, mapping a variable VAR to a bitmap describing all the
76 basic blocks where VAR is defined (assigned a new value). It also
77 contains a bitmap of all the blocks where VAR is live-on-entry
78 (i.e., there is a use of VAR in block B without a preceding
79 definition in B). The live-on-entry information is used when
80 computing PHI pruning heuristics. */
81 static htab_t def_blocks;
83 /* Global data to attach to the main dominator walk structure. */
84 struct mark_def_sites_global_data
86 /* This sbitmap contains the variables which are set before they
87 are used in a basic block. We keep it as a global variable
88 solely to avoid the overhead of allocating and deallocating
93 struct rewrite_block_data
95 varray_type block_defs;
99 /* Local functions. */
100 static void rewrite_finalize_block (struct dom_walk_data *, basic_block);
101 static void rewrite_initialize_block_local_data (struct dom_walk_data *,
103 static void rewrite_initialize_block (struct dom_walk_data *, basic_block);
104 static void rewrite_add_phi_arguments (struct dom_walk_data *, basic_block);
105 static void mark_def_sites (struct dom_walk_data *walk_data,
106 basic_block bb, block_stmt_iterator);
107 static void mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
109 static void compute_global_livein (bitmap, bitmap);
110 static void set_def_block (tree, basic_block);
111 static void set_livein_block (tree, basic_block);
112 static bool prepare_operand_for_rename (tree *op_p, size_t *uid_p);
113 static void insert_phi_nodes (bitmap *);
114 static void rewrite_stmt (struct dom_walk_data *, basic_block,
115 block_stmt_iterator);
116 static inline void rewrite_operand (tree *);
117 static void insert_phi_nodes_for (tree, bitmap *, varray_type *);
118 static tree get_reaching_def (tree);
119 static hashval_t def_blocks_hash (const void *);
120 static int def_blocks_eq (const void *, const void *);
121 static void def_blocks_free (void *);
122 static int debug_def_blocks_r (void **, void *);
123 static inline struct def_blocks_d *get_def_blocks_for (tree);
124 static inline struct def_blocks_d *find_def_blocks_for (tree);
125 static void htab_statistics (FILE *, htab_t);
127 /* Compute global livein information given the set of blockx where
128 an object is locally live at the start of the block (LIVEIN)
129 and the set of blocks where the object is defined (DEF_BLOCKS).
131 Note: This routine augments the existing local livein information
132 to include global livein (i.e., it modifies the underlying bitmap
136 compute_global_livein (bitmap livein, bitmap def_blocks)
138 basic_block bb, *worklist, *tos;
141 = (basic_block *) xmalloc (sizeof (basic_block) * (last_basic_block + 1));
143 /* Initialize the worklist. */
146 if (bitmap_bit_p (livein, bb->index))
150 /* Iterate until the worklist is empty. */
151 while (tos != worklist)
155 /* Pull a block off the worklist. */
158 /* For each predecessor block. */
159 for (e = bb->pred; e; e = e->pred_next)
161 basic_block pred = e->src;
162 int pred_index = pred->index;
164 /* None of this is necessary for the entry block. */
165 if (pred != ENTRY_BLOCK_PTR
166 && ! bitmap_bit_p (livein, pred_index)
167 && ! bitmap_bit_p (def_blocks, pred_index))
170 bitmap_set_bit (livein, pred_index);
179 /* Block initialization routine for mark_def_sites. Clear the
180 KILLS bitmap at the start of each block. */
183 mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
184 basic_block bb ATTRIBUTE_UNUSED)
186 struct mark_def_sites_global_data *gd = walk_data->global_data;
187 sbitmap kills = gd->kills;
189 sbitmap_zero (kills);
193 /* Call back for walk_dominator_tree used to collect definition sites
194 for every variable in the function. For every statement S in block
197 1- Variables defined by S in DEF_OPS(S) are marked in the bitmap
198 WALK_DATA->GLOBAL_DATA->KILLS.
200 2- If S uses a variable VAR and there is no preceding kill of VAR,
201 then it is marked in marked in the LIVEIN_BLOCKS bitmap
204 This information is used to determine which variables are live
205 across block boundaries to reduce the number of PHI nodes
209 mark_def_sites (struct dom_walk_data *walk_data,
211 block_stmt_iterator bsi)
213 struct mark_def_sites_global_data *gd = walk_data->global_data;
214 sbitmap kills = gd->kills;
223 /* Mark all the blocks that have definitions for each variable in the
224 VARS_TO_RENAME bitmap. */
225 stmt = bsi_stmt (bsi);
226 get_stmt_operands (stmt);
227 ann = stmt_ann (stmt);
229 /* If a variable is used before being set, then the variable is live
230 across a block boundary, so mark it live-on-entry to BB. */
231 uses = USE_OPS (ann);
232 for (i = 0; i < NUM_USES (uses); i++)
234 tree *use_p = USE_OP_PTR (uses, i);
236 if (prepare_operand_for_rename (use_p, &uid)
237 && !TEST_BIT (kills, uid))
238 set_livein_block (*use_p, bb);
241 /* Similarly for virtual uses. */
242 vuses = VUSE_OPS (ann);
243 for (i = 0; i < NUM_VUSES (vuses); i++)
245 tree *use_p = VUSE_OP_PTR (vuses, i);
247 if (prepare_operand_for_rename (use_p, &uid)
248 && !TEST_BIT (kills, uid))
249 set_livein_block (*use_p, bb);
252 /* Note that virtual definitions are irrelevant for computing KILLS
253 because a VDEF does not constitute a killing definition of the
254 variable. However, the operand of a virtual definitions is a use
255 of the variable, so it may cause the variable to be considered
257 vdefs = VDEF_OPS (ann);
258 for (i = 0; i < NUM_VDEFS (vdefs); i++)
262 if (prepare_operand_for_rename (VDEF_OP_PTR (vdefs, i), &uid)
263 && prepare_operand_for_rename (VDEF_RESULT_PTR (vdefs, i), &dummy))
265 VDEF_RESULT (vdefs, i) = VDEF_OP (vdefs, i);
267 if (!TEST_BIT (kills, uid))
268 set_livein_block (VDEF_OP (vdefs, i), bb);
269 set_def_block (VDEF_RESULT (vdefs, i), bb);
273 /* Now process the definition made by this statement. Mark the
274 variables in KILLS. */
275 defs = DEF_OPS (ann);
276 for (i = 0; i < NUM_DEFS (defs); i++)
278 tree *def_p = DEF_OP_PTR (defs, i);
280 if (prepare_operand_for_rename (def_p, &uid))
282 set_def_block (*def_p, bb);
283 SET_BIT (kills, uid);
289 /* Mark block BB as the definition site for variable VAR. */
292 set_def_block (tree var, basic_block bb)
294 struct def_blocks_d *db_p;
295 enum need_phi_state state = var_ann (var)->need_phi_state;
297 db_p = get_def_blocks_for (var);
299 /* Set the bit corresponding to the block where VAR is defined. */
300 bitmap_set_bit (db_p->def_blocks, bb->index);
302 /* Keep track of whether or not we may need to insert phi nodes.
304 If we are in the UNKNOWN state, then this is the first definition
305 of VAR. Additionally, we have not seen any uses of VAR yet, so
306 we do not need a phi node for this variable at this time (i.e.,
307 transition to NEED_PHI_STATE_NO).
309 If we are in any other state, then we either have multiple definitions
310 of this variable occurring in different blocks or we saw a use of the
311 variable which was not dominated by the block containing the
312 definition(s). In this case we may need a PHI node, so enter
313 state NEED_PHI_STATE_MAYBE. */
314 if (state == NEED_PHI_STATE_UNKNOWN)
315 var_ann (var)->need_phi_state = NEED_PHI_STATE_NO;
317 var_ann (var)->need_phi_state = NEED_PHI_STATE_MAYBE;
321 /* Mark block BB as having VAR live at the entry to BB. */
324 set_livein_block (tree var, basic_block bb)
326 struct def_blocks_d *db_p;
327 enum need_phi_state state = var_ann (var)->need_phi_state;
329 db_p = get_def_blocks_for (var);
331 /* Set the bit corresponding to the block where VAR is live in. */
332 bitmap_set_bit (db_p->livein_blocks, bb->index);
334 /* Keep track of whether or not we may need to insert phi nodes.
336 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
337 by the single block containing the definition(s) of this variable. If
338 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
339 NEED_PHI_STATE_MAYBE. */
340 if (state == NEED_PHI_STATE_NO)
342 int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
344 if (def_block_index == -1
345 || ! dominated_by_p (CDI_DOMINATORS, bb,
346 BASIC_BLOCK (def_block_index)))
347 var_ann (var)->need_phi_state = NEED_PHI_STATE_MAYBE;
350 var_ann (var)->need_phi_state = NEED_PHI_STATE_MAYBE;
354 /* If the operand pointed by OP_P needs to be renamed, strip away SSA_NAME
355 wrappers (if needed) and return true. The unique ID for the operand's
356 variable will be stored in *UID_P. */
359 prepare_operand_for_rename (tree *op_p, size_t *uid_p)
361 tree var = (TREE_CODE (*op_p) != SSA_NAME) ? *op_p : SSA_NAME_VAR (*op_p);
362 *uid_p = var_ann (var)->uid;
364 /* Ignore variables that don't need to be renamed. */
365 if (vars_to_rename && !bitmap_bit_p (vars_to_rename, *uid_p))
368 /* The variable needs to be renamed. If it already had an
369 SSA_NAME, strip it off. This way, the SSA rename pass
370 doesn't need to deal with existing SSA names. */
371 if (TREE_CODE (*op_p) == SSA_NAME)
373 if (default_def (SSA_NAME_VAR (*op_p)) != *op_p)
374 release_ssa_name (*op_p);
382 /* Helper for insert_phi_nodes. If VAR needs PHI nodes, insert them
383 at the dominance frontier (DFS) of blocks defining VAR. */
386 void insert_phi_nodes_1 (tree var, bitmap *dfs, varray_type *work_stack)
388 var_ann_t ann = var_ann (var);
389 if (ann->need_phi_state != NEED_PHI_STATE_NO)
390 insert_phi_nodes_for (var, dfs, work_stack);
394 /* Insert PHI nodes at the dominance frontier of blocks with variable
395 definitions. DFS contains the dominance frontier information for
396 the flowgraph. PHI nodes will only be inserted at the dominance
397 frontier of definition blocks for variables whose NEED_PHI_STATE
398 annotation is marked as ``maybe'' or ``unknown'' (computed by
402 insert_phi_nodes (bitmap *dfs)
405 varray_type work_stack;
407 timevar_push (TV_TREE_INSERT_PHI_NODES);
409 /* Array WORK_STACK is a stack of CFG blocks. Each block that contains
410 an assignment or PHI node will be pushed to this stack. */
411 VARRAY_BB_INIT (work_stack, last_basic_block, "work_stack");
413 /* Iterate over all variables in VARS_TO_RENAME. For each variable, add
414 to the work list all the blocks that have a definition for the
415 variable. PHI nodes will be added to the dominance frontier blocks of
416 each definition block. */
418 EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i,
419 insert_phi_nodes_1 (referenced_var (i), dfs, &work_stack));
421 for (i = 0; i < num_referenced_vars; i++)
422 insert_phi_nodes_1 (referenced_var (i), dfs, &work_stack);
424 timevar_pop (TV_TREE_INSERT_PHI_NODES);
428 /* Perform a depth-first traversal of the dominator tree looking for
429 variables to rename. BB is the block where to start searching.
430 Renaming is a five step process:
432 1- Every definition made by PHI nodes at the start of the blocks is
433 registered as the current definition for the corresponding variable.
435 2- Every statement in BB is rewritten. USE and VUSE operands are
436 rewritten with their corresponding reaching definition. DEF and
437 VDEF targets are registered as new definitions.
439 3- All the PHI nodes in successor blocks of BB are visited. The
440 argument corresponding to BB is replaced with its current reaching
443 4- Recursively rewrite every dominator child block of BB.
445 5- Restore (in reverse order) the current reaching definition for every
446 new definition introduced in this block. This is done so that when
447 we return from the recursive call, all the current reaching
448 definitions are restored to the names that were valid in the
449 dominator parent of BB. */
451 /* Initialize the local stacks.
453 BLOCK_DEFS is used to save all the existing reaching definitions for
454 the new SSA names introduced in this block. Before registering a
455 new definition for a variable, the existing reaching definition is
456 pushed into this stack so that we can restore it in Step 5. */
459 rewrite_initialize_block_local_data (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
460 basic_block bb ATTRIBUTE_UNUSED,
461 bool recycled ATTRIBUTE_UNUSED)
463 #ifdef ENABLE_CHECKING
464 struct rewrite_block_data *bd
465 = (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
467 /* We get cleared memory from the allocator, so if the memory is
468 not cleared, then we are re-using a previously allocated entry. In
469 that case, we can also re-use the underlying virtal arrays. Just
470 make sure we clear them before using them! */
471 if (recycled && bd->block_defs && VARRAY_ACTIVE_SIZE (bd->block_defs) > 0)
477 /* SSA Rewriting Step 1. Initialization, create a block local stack
478 of reaching definitions for new SSA names produced in this block
479 (BLOCK_DEFS). Register new definitions for every PHI node in the
483 rewrite_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
486 struct rewrite_block_data *bd
487 = (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
489 if (dump_file && (dump_flags & TDF_DETAILS))
490 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
492 /* Step 1. Register new definitions for every PHI node in the block.
493 Conceptually, all the PHI nodes are executed in parallel and each PHI
494 node introduces a new version for the associated variable. */
495 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
497 tree result = PHI_RESULT (phi);
499 register_new_def (result, &bd->block_defs);
504 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
505 PHI nodes. For every PHI node found, add a new argument containing the
506 current reaching definition for the variable and the edge through which
507 that definition is reaching the PHI node. */
510 rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
515 for (e = bb->succ; e; e = e->succ_next)
519 for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
523 /* If this PHI node has already been rewritten, then there is
524 nothing to do for this PHI or any following PHIs since we
525 always add new PHI nodes at the start of the PHI chain. */
526 if (PHI_REWRITTEN (phi))
529 currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
530 add_phi_arg (&phi, currdef, e);
535 /* SSA Rewriting Step 5. Restore the current reaching definition for each
536 variable referenced in the block (in reverse order). */
539 rewrite_finalize_block (struct dom_walk_data *walk_data,
540 basic_block bb ATTRIBUTE_UNUSED)
542 struct rewrite_block_data *bd
543 = (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
545 /* Step 5. Restore the current reaching definition for each variable
546 referenced in the block (in reverse order). */
547 while (bd->block_defs && VARRAY_ACTIVE_SIZE (bd->block_defs) > 0)
549 tree tmp = VARRAY_TOP_TREE (bd->block_defs);
552 VARRAY_POP (bd->block_defs);
553 if (TREE_CODE (tmp) == SSA_NAME)
556 var = SSA_NAME_VAR (saved_def);
564 var_ann (var)->current_def = saved_def;
569 /* Dump SSA information to FILE. */
572 dump_tree_ssa (FILE *file)
576 = (*lang_hooks.decl_printable_name) (current_function_decl, 2);
578 fprintf (file, "SSA information for %s\n\n", funcname);
582 dump_bb (bb, file, 0);
584 print_generic_stmt (file, phi_nodes (bb), dump_flags);
585 fputs ("\n\n", file);
590 /* Dump SSA information to stderr. */
593 debug_tree_ssa (void)
595 dump_tree_ssa (stderr);
599 /* Dump SSA statistics on FILE. */
602 dump_tree_ssa_stats (FILE *file)
604 fprintf (file, "\nHash table statistics:\n");
606 fprintf (file, " def_blocks: ");
607 htab_statistics (file, def_blocks);
609 fprintf (file, "\n");
613 /* Dump SSA statistics on stderr. */
616 debug_tree_ssa_stats (void)
618 dump_tree_ssa_stats (stderr);
622 /* Dump statistics for the hash table HTAB. */
625 htab_statistics (FILE *file, htab_t htab)
627 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
628 (long) htab_size (htab),
629 (long) htab_elements (htab),
630 htab_collisions (htab));
634 /* Insert PHI nodes for variable VAR using the dominance frontier
635 information given in DFS. */
638 insert_phi_nodes_for (tree var, bitmap *dfs, varray_type *work_stack)
640 struct def_blocks_d *def_map;
641 bitmap phi_insertion_points;
644 def_map = find_def_blocks_for (var);
648 phi_insertion_points = BITMAP_XMALLOC ();
650 EXECUTE_IF_SET_IN_BITMAP (def_map->def_blocks, 0, bb_index,
652 VARRAY_PUSH_BB (*work_stack, BASIC_BLOCK (bb_index));
655 /* Pop a block off the worklist, add every block that appears in
656 the original block's dfs that we have not already processed to
657 the worklist. Iterate until the worklist is empty. Blocks
658 which are added to the worklist are potential sites for
661 The iteration step could be done during PHI insertion just as
662 easily. We do it here for historical reasons -- we used to have
663 a heuristic which used the potential PHI insertion points to
664 determine if fully pruned or semi pruned SSA form was appropriate.
666 We now always use fully pruned SSA form. */
667 while (VARRAY_ACTIVE_SIZE (*work_stack) > 0)
669 basic_block bb = VARRAY_TOP_BB (*work_stack);
670 int bb_index = bb->index;
673 VARRAY_POP (*work_stack);
675 EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index],
676 phi_insertion_points,
679 basic_block bb = BASIC_BLOCK (dfs_index);
681 VARRAY_PUSH_BB (*work_stack, bb);
682 bitmap_set_bit (phi_insertion_points, dfs_index);
686 /* Now compute global livein for this variable. Note this modifies
687 def_map->livein_blocks. */
688 compute_global_livein (def_map->livein_blocks, def_map->def_blocks);
690 /* And insert the PHI nodes. */
691 EXECUTE_IF_AND_IN_BITMAP (phi_insertion_points, def_map->livein_blocks,
694 create_phi_node (var, BASIC_BLOCK (bb_index));
697 BITMAP_FREE (phi_insertion_points);
700 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
701 the block with its immediate reaching definitions. Update the current
702 definition of a variable when a new real or virtual definition is found. */
705 rewrite_stmt (struct dom_walk_data *walk_data,
706 basic_block bb ATTRIBUTE_UNUSED,
707 block_stmt_iterator si)
716 struct rewrite_block_data *bd;
718 bd = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
720 stmt = bsi_stmt (si);
721 ann = stmt_ann (stmt);
723 if (dump_file && (dump_flags & TDF_DETAILS))
725 fprintf (dump_file, "Renaming statement ");
726 print_generic_stmt (dump_file, stmt, TDF_SLIM);
727 fprintf (dump_file, "\n");
730 #if defined ENABLE_CHECKING
731 /* We have just scanned the code for operands. No statement should
737 defs = DEF_OPS (ann);
738 uses = USE_OPS (ann);
739 vuses = VUSE_OPS (ann);
740 vdefs = VDEF_OPS (ann);
742 /* Step 1. Rewrite USES and VUSES in the statement. */
743 for (i = 0; i < NUM_USES (uses); i++)
744 rewrite_operand (USE_OP_PTR (uses, i));
746 /* Rewrite virtual uses in the statement. */
747 for (i = 0; i < NUM_VUSES (vuses); i++)
748 rewrite_operand (VUSE_OP_PTR (vuses, i));
750 /* Step 2. Register the statement's DEF and VDEF operands. */
751 for (i = 0; i < NUM_DEFS (defs); i++)
753 tree *def_p = DEF_OP_PTR (defs, i);
755 if (TREE_CODE (*def_p) != SSA_NAME)
756 *def_p = make_ssa_name (*def_p, stmt);
758 /* FIXME: We shouldn't be registering new defs if the variable
759 doesn't need to be renamed. */
760 register_new_def (*def_p, &bd->block_defs);
763 /* Register new virtual definitions made by the statement. */
764 for (i = 0; i < NUM_VDEFS (vdefs); i++)
766 rewrite_operand (VDEF_OP_PTR (vdefs, i));
768 if (TREE_CODE (VDEF_RESULT (vdefs, i)) != SSA_NAME)
769 *VDEF_RESULT_PTR (vdefs, i)
770 = make_ssa_name (VDEF_RESULT (vdefs, i), stmt);
772 /* FIXME: We shouldn't be registering new defs if the variable
773 doesn't need to be renamed. */
774 register_new_def (VDEF_RESULT (vdefs, i), &bd->block_defs);
779 /* Replace the operand pointed by OP_P with its immediate reaching
783 rewrite_operand (tree *op_p)
785 if (TREE_CODE (*op_p) != SSA_NAME)
786 *op_p = get_reaching_def (*op_p);
790 /* Register DEF (an SSA_NAME) to be a new definition for its underlying
791 variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition
792 into the stack pointed by BLOCK_DEFS_P. */
795 register_new_def (tree def, varray_type *block_defs_p)
797 tree var = SSA_NAME_VAR (def);
800 /* If this variable is set in a single basic block and all uses are
801 dominated by the set(s) in that single basic block, then there is
802 no reason to record anything for this variable in the block local
803 definition stacks. Doing so just wastes time and memory.
805 This is the same test to prune the set of variables which may
806 need PHI nodes. So we just use that information since it's already
807 computed and available for us to use. */
808 if (var_ann (var)->need_phi_state == NEED_PHI_STATE_NO)
810 var_ann (var)->current_def = def;
814 currdef = var_ann (var)->current_def;
816 VARRAY_TREE_INIT (*block_defs_p, 20, "block_defs");
818 /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
819 later used by the dominator tree callbacks to restore the reaching
820 definitions for all the variables defined in the block after a recursive
821 visit to all its immediately dominated blocks. If there is no current
822 reaching definition, then just record the underlying _DECL node. */
823 VARRAY_PUSH_TREE (*block_defs_p, currdef ? currdef : var);
825 /* Set the current reaching definition for VAR to be DEF. */
826 var_ann (var)->current_def = def;
830 /* Return the current definition for variable VAR. If none is found,
831 create a new SSA name to act as the zeroth definition for VAR. If VAR
832 is call clobbered and there exists a more recent definition of
833 GLOBAL_VAR, return the definition for GLOBAL_VAR. This means that VAR
834 has been clobbered by a function call since its last assignment. */
837 get_reaching_def (tree var)
839 tree default_d, currdef_var;
841 /* Lookup the current reaching definition for VAR. */
842 default_d = NULL_TREE;
843 currdef_var = var_ann (var)->current_def;
845 /* If there is no reaching definition for VAR, create and register a
846 default definition for it (if needed). */
847 if (currdef_var == NULL_TREE)
849 default_d = default_def (var);
850 if (default_d == NULL_TREE)
852 default_d = make_ssa_name (var, build_empty_stmt ());
853 set_default_def (var, default_d);
855 var_ann (var)->current_def = default_d;
858 /* Return the current reaching definition for VAR, or the default
859 definition, if we had to create one. */
860 return (currdef_var) ? currdef_var : default_d;
864 /* Hashing and equality functions for DEF_BLOCKS. */
867 def_blocks_hash (const void *p)
869 return htab_hash_pointer
870 ((const void *)((const struct def_blocks_d *)p)->var);
874 def_blocks_eq (const void *p1, const void *p2)
876 return ((const struct def_blocks_d *)p1)->var
877 == ((const struct def_blocks_d *)p2)->var;
880 /* Free memory allocated by one entry in DEF_BLOCKS. */
883 def_blocks_free (void *p)
885 struct def_blocks_d *entry = p;
886 BITMAP_FREE (entry->def_blocks);
887 BITMAP_FREE (entry->livein_blocks);
892 /* Dump the DEF_BLOCKS hash table on stderr. */
895 debug_def_blocks (void)
897 htab_traverse (def_blocks, debug_def_blocks_r, NULL);
900 /* Callback for htab_traverse to dump the DEF_BLOCKS hash table. */
903 debug_def_blocks_r (void **slot, void *data ATTRIBUTE_UNUSED)
906 struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
908 fprintf (stderr, "VAR: ");
909 print_generic_expr (stderr, db_p->var, dump_flags);
910 fprintf (stderr, ", DEF_BLOCKS: { ");
911 EXECUTE_IF_SET_IN_BITMAP (db_p->def_blocks, 0, i,
912 fprintf (stderr, "%ld ", i));
913 fprintf (stderr, "}");
914 fprintf (stderr, ", LIVEIN_BLOCKS: { ");
915 EXECUTE_IF_SET_IN_BITMAP (db_p->livein_blocks, 0, i,
916 fprintf (stderr, "%ld ", i));
917 fprintf (stderr, "}\n");
923 /* Return the set of blocks where variable VAR is defined and the blocks
924 where VAR is live on entry (livein). Return NULL, if no entry is
925 found in DEF_BLOCKS. */
927 static inline struct def_blocks_d *
928 find_def_blocks_for (tree var)
930 struct def_blocks_d dm;
932 return (struct def_blocks_d *) htab_find (def_blocks, &dm);
936 /* Return the set of blocks where variable VAR is defined and the blocks
937 where VAR is live on entry (livein). If no entry is found in
938 DEF_BLOCKS, a new one is created and returned. */
940 static inline struct def_blocks_d *
941 get_def_blocks_for (tree var)
943 struct def_blocks_d db, *db_p;
947 slot = htab_find_slot (def_blocks, (void *) &db, INSERT);
950 db_p = xmalloc (sizeof (*db_p));
952 db_p->def_blocks = BITMAP_XMALLOC ();
953 db_p->livein_blocks = BITMAP_XMALLOC ();
954 *slot = (void *) db_p;
957 db_p = (struct def_blocks_d *) *slot;
962 /* If a variable V in VARS_TO_RENAME is a pointer, the renaming
963 process will cause us to lose the name memory tags that may have
964 been associated with the various SSA_NAMEs of V. This means that
965 the variables aliased to those name tags also need to be renamed
968 FIXME 1- We should either have a better scheme for renaming
969 pointers that doesn't lose name tags or re-run alias
970 analysis to recover points-to information.
972 2- Currently we just invalidate *all* the name tags. This
973 should be more selective. */
976 invalidate_name_tags (bitmap vars_to_rename)
979 bool rename_name_tags_p;
981 rename_name_tags_p = false;
982 EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i,
983 if (POINTER_TYPE_P (TREE_TYPE (referenced_var (i))))
985 rename_name_tags_p = true;
989 if (rename_name_tags_p)
990 for (i = 0; i < num_referenced_vars; i++)
992 var_ann_t ann = var_ann (referenced_var (i));
994 if (ann->mem_tag_kind == NAME_TAG)
997 varray_type may_aliases = ann->may_aliases;
999 bitmap_set_bit (vars_to_rename, ann->uid);
1000 if (ann->may_aliases)
1001 for (j = 0; j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
1003 tree var = VARRAY_TREE (may_aliases, j);
1004 bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1011 /* Main entry point into the SSA builder. The renaming process
1012 proceeds in five main phases:
1014 1- If VARS_TO_RENAME has any entries, any existing PHI nodes for
1015 those variables are removed from the flow graph so that they can
1018 2- Compute dominance frontier and immediate dominators, needed to
1019 insert PHI nodes and rename the function in dominator tree
1022 3- Find and mark all the blocks that define variables
1025 4- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
1027 5- Rename all the blocks (rewrite_initialize_block,
1028 rewrite_add_phi_arguments) and statements in the program
1031 Steps 3 and 5 are done using the dominator tree walker
1032 (walk_dominator_tree). */
1035 rewrite_into_ssa (void)
1039 struct dom_walk_data walk_data;
1040 struct mark_def_sites_global_data mark_def_sites_global_data;
1043 timevar_push (TV_TREE_SSA_OTHER);
1045 /* Initialize the array of variables to rename. */
1046 if (vars_to_rename != NULL)
1048 invalidate_name_tags (vars_to_rename);
1050 /* Now remove all the existing PHI nodes (if any) for the variables
1051 that we are about to rename into SSA. */
1052 remove_all_phi_nodes_for (vars_to_rename);
1055 /* Allocate memory for the DEF_BLOCKS hash table. */
1056 def_blocks = htab_create (VARRAY_ACTIVE_SIZE (referenced_vars),
1057 def_blocks_hash, def_blocks_eq, def_blocks_free);
1059 /* Initialize dominance frontier and immediate dominator bitmaps.
1060 Also count the number of predecessors for each block. Doing so
1061 can save significant time during PHI insertion for large graphs. */
1062 dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
1068 for (e = bb->pred; e; e = e->pred_next)
1071 bb_ann (bb)->num_preds = count;
1072 dfs[bb->index] = BITMAP_XMALLOC ();
1075 for (i = 0; i < num_referenced_vars; i++)
1076 var_ann (referenced_var (i))->current_def = NULL;
1078 /* Ensure that the dominance information is OK. */
1079 calculate_dominance_info (CDI_DOMINATORS);
1081 /* Compute dominance frontiers. */
1082 compute_dominance_frontiers (dfs);
1084 /* Setup callbacks for the generic dominator tree walker to find and
1085 mark definition sites. */
1086 walk_data.walk_stmts_backward = false;
1087 walk_data.dom_direction = CDI_DOMINATORS;
1088 walk_data.initialize_block_local_data = NULL;
1089 walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block;
1090 walk_data.before_dom_children_walk_stmts = mark_def_sites;
1091 walk_data.before_dom_children_after_stmts = NULL;
1092 walk_data.after_dom_children_before_stmts = NULL;
1093 walk_data.after_dom_children_walk_stmts = NULL;
1094 walk_data.after_dom_children_after_stmts = NULL;
1096 /* Notice that this bitmap is indexed using variable UIDs, so it must be
1097 large enough to accommodate all the variables referenced in the
1098 function, not just the ones we are renaming. */
1099 mark_def_sites_global_data.kills = sbitmap_alloc (num_referenced_vars);
1100 walk_data.global_data = &mark_def_sites_global_data;
1102 /* We do not have any local data. */
1103 walk_data.block_local_data_size = 0;
1105 /* Initialize the dominator walker. */
1106 init_walk_dominator_tree (&walk_data);
1108 /* Recursively walk the dominator tree. */
1109 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1111 /* Finalize the dominator walker. */
1112 fini_walk_dominator_tree (&walk_data);
1114 /* We no longer need this bitmap, clear and free it. */
1115 sbitmap_free (mark_def_sites_global_data.kills);
1117 /* Insert PHI nodes at dominance frontiers of definition blocks. */
1118 insert_phi_nodes (dfs);
1120 /* Rewrite all the basic blocks in the program. */
1121 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
1123 /* Setup callbacks for the generic dominator tree walker. */
1124 walk_data.walk_stmts_backward = false;
1125 walk_data.dom_direction = CDI_DOMINATORS;
1126 walk_data.initialize_block_local_data = rewrite_initialize_block_local_data;
1127 walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
1128 walk_data.before_dom_children_walk_stmts = rewrite_stmt;
1129 walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
1130 walk_data.after_dom_children_before_stmts = NULL;
1131 walk_data.after_dom_children_walk_stmts = NULL;
1132 walk_data.after_dom_children_after_stmts = rewrite_finalize_block;
1133 walk_data.global_data = NULL;
1134 walk_data.block_local_data_size = sizeof (struct rewrite_block_data);
1136 /* Initialize the dominator walker. */
1137 init_walk_dominator_tree (&walk_data);
1139 /* Recursively walk the dominator tree rewriting each statement in
1140 each basic block. */
1141 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1143 /* Finalize the dominator walker. */
1144 fini_walk_dominator_tree (&walk_data);
1146 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
1148 /* Debugging dumps. */
1149 if (dump_file && (dump_flags & TDF_STATS))
1151 dump_dfa_stats (dump_file);
1152 dump_tree_ssa_stats (dump_file);
1155 /* Free allocated memory. */
1157 BITMAP_XFREE (dfs[bb->index]);
1160 htab_delete (def_blocks);
1162 timevar_pop (TV_TREE_SSA_OTHER);
1165 struct tree_opt_pass pass_build_ssa =
1169 rewrite_into_ssa, /* execute */
1172 0, /* static_pass_number */
1174 PROP_cfg | PROP_referenced_vars, /* properties_required */
1175 PROP_ssa, /* properties_provided */
1176 0, /* properties_destroyed */
1177 0, /* todo_flags_start */
1178 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */