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-gimple.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
, bool);
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
;
142 = (basic_block
*) xmalloc (sizeof (basic_block
) * (last_basic_block
+ 1));
144 EXECUTE_IF_SET_IN_BITMAP (livein
, 0, i
,
146 *tos
++ = BASIC_BLOCK (i
);
149 /* Iterate until the worklist is empty. */
150 while (tos
!= worklist
)
154 /* Pull a block off the worklist. */
157 /* For each predecessor block. */
158 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
160 basic_block pred
= e
->src
;
161 int pred_index
= pred
->index
;
163 /* None of this is necessary for the entry block. */
164 if (pred
!= ENTRY_BLOCK_PTR
165 && ! bitmap_bit_p (livein
, pred_index
)
166 && ! bitmap_bit_p (def_blocks
, pred_index
))
169 bitmap_set_bit (livein
, pred_index
);
178 /* Block initialization routine for mark_def_sites. Clear the
179 KILLS bitmap at the start of each block. */
182 mark_def_sites_initialize_block (struct dom_walk_data
*walk_data
,
183 basic_block bb ATTRIBUTE_UNUSED
)
185 struct mark_def_sites_global_data
*gd
= walk_data
->global_data
;
186 sbitmap kills
= gd
->kills
;
188 sbitmap_zero (kills
);
192 /* Call back for walk_dominator_tree used to collect definition sites
193 for every variable in the function. For every statement S in block
196 1- Variables defined by S in DEF_OPS(S) are marked in the bitmap
197 WALK_DATA->GLOBAL_DATA->KILLS.
199 2- If S uses a variable VAR and there is no preceding kill of VAR,
200 then it is marked in marked in the LIVEIN_BLOCKS bitmap
203 This information is used to determine which variables are live
204 across block boundaries to reduce the number of PHI nodes
208 mark_def_sites (struct dom_walk_data
*walk_data
,
210 block_stmt_iterator bsi
)
212 struct mark_def_sites_global_data
*gd
= walk_data
->global_data
;
213 sbitmap kills
= gd
->kills
;
214 v_may_def_optype v_may_defs
;
215 v_must_def_optype v_must_defs
;
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
, true)
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
, true))
248 set_livein_block (*use_p
, bb
);
251 /* Note that virtual definitions are irrelevant for computing KILLS
252 because a V_MAY_DEF does not constitute a killing definition of the
253 variable. However, the operand of a virtual definitions is a use
254 of the variable, so it may cause the variable to be considered
256 v_may_defs
= V_MAY_DEF_OPS (ann
);
257 for (i
= 0; i
< NUM_V_MAY_DEFS (v_may_defs
); i
++)
259 if (prepare_operand_for_rename (V_MAY_DEF_OP_PTR (v_may_defs
, i
),
262 /* If we do not already have an SSA_NAME for our destination,
263 then set the destination to the source. */
264 if (TREE_CODE (V_MAY_DEF_RESULT (v_may_defs
, i
)) != SSA_NAME
)
265 V_MAY_DEF_RESULT (v_may_defs
, i
) = V_MAY_DEF_OP (v_may_defs
, i
);
267 set_livein_block (V_MAY_DEF_OP (v_may_defs
, i
), bb
);
268 set_def_block (V_MAY_DEF_RESULT (v_may_defs
, i
), bb
);
272 /* Now process the virtual must-defs made by this statement. */
273 v_must_defs
= V_MUST_DEF_OPS (ann
);
274 for (i
= 0; i
< NUM_V_MUST_DEFS (v_must_defs
); i
++)
276 tree
*def_p
= V_MUST_DEF_OP_PTR (v_must_defs
, i
);
278 if (prepare_operand_for_rename (def_p
, &uid
, false))
280 set_def_block (*def_p
, bb
);
281 SET_BIT (kills
, uid
);
285 /* Now process the definition made by this statement. Mark the
286 variables in KILLS. */
287 defs
= DEF_OPS (ann
);
288 for (i
= 0; i
< NUM_DEFS (defs
); i
++)
290 tree
*def_p
= DEF_OP_PTR (defs
, i
);
292 if (prepare_operand_for_rename (def_p
, &uid
, false))
294 set_def_block (*def_p
, bb
);
295 SET_BIT (kills
, uid
);
301 /* Mark block BB as the definition site for variable VAR. */
304 set_def_block (tree var
, basic_block bb
)
306 struct def_blocks_d
*db_p
;
307 enum need_phi_state state
;
309 if (TREE_CODE (var
) == SSA_NAME
)
310 var
= SSA_NAME_VAR (var
);
312 state
= var_ann (var
)->need_phi_state
;
313 db_p
= get_def_blocks_for (var
);
315 /* Set the bit corresponding to the block where VAR is defined. */
316 bitmap_set_bit (db_p
->def_blocks
, bb
->index
);
318 /* Keep track of whether or not we may need to insert phi nodes.
320 If we are in the UNKNOWN state, then this is the first definition
321 of VAR. Additionally, we have not seen any uses of VAR yet, so
322 we do not need a phi node for this variable at this time (i.e.,
323 transition to NEED_PHI_STATE_NO).
325 If we are in any other state, then we either have multiple definitions
326 of this variable occurring in different blocks or we saw a use of the
327 variable which was not dominated by the block containing the
328 definition(s). In this case we may need a PHI node, so enter
329 state NEED_PHI_STATE_MAYBE. */
330 if (state
== NEED_PHI_STATE_UNKNOWN
)
331 var_ann (var
)->need_phi_state
= NEED_PHI_STATE_NO
;
333 var_ann (var
)->need_phi_state
= NEED_PHI_STATE_MAYBE
;
337 /* Mark block BB as having VAR live at the entry to BB. */
340 set_livein_block (tree var
, basic_block bb
)
342 struct def_blocks_d
*db_p
;
343 enum need_phi_state state
= var_ann (var
)->need_phi_state
;
345 db_p
= get_def_blocks_for (var
);
347 /* Set the bit corresponding to the block where VAR is live in. */
348 bitmap_set_bit (db_p
->livein_blocks
, bb
->index
);
350 /* Keep track of whether or not we may need to insert phi nodes.
352 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
353 by the single block containing the definition(s) of this variable. If
354 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
355 NEED_PHI_STATE_MAYBE. */
356 if (state
== NEED_PHI_STATE_NO
)
358 int def_block_index
= bitmap_first_set_bit (db_p
->def_blocks
);
360 if (def_block_index
== -1
361 || ! dominated_by_p (CDI_DOMINATORS
, bb
,
362 BASIC_BLOCK (def_block_index
)))
363 var_ann (var
)->need_phi_state
= NEED_PHI_STATE_MAYBE
;
366 var_ann (var
)->need_phi_state
= NEED_PHI_STATE_MAYBE
;
370 /* If the operand pointed to by OP_P needs to be renamed, then
372 1. If OP_P is used (rather than set), then strip away any SSA_NAME
373 wrapping the operand.
375 2. Set *UID_P to the underlying variable's uid.
379 Otherwise return false. */
382 prepare_operand_for_rename (tree
*op_p
, size_t *uid_p
, bool is_use
)
384 tree var
= (TREE_CODE (*op_p
) != SSA_NAME
) ? *op_p
: SSA_NAME_VAR (*op_p
);
385 *uid_p
= var_ann (var
)->uid
;
387 /* Ignore variables that don't need to be renamed. */
388 if (vars_to_rename
&& !bitmap_bit_p (vars_to_rename
, *uid_p
))
391 /* The variable needs to be renamed. If this is a use which already
392 has an SSA_NAME, then strip it off.
394 By not throwing away SSA_NAMEs on assignments, we avoid a lot of
395 useless churn of SSA_NAMEs without having to overly complicate the
397 if (TREE_CODE (*op_p
) == SSA_NAME
&& is_use
)
404 /* Helper for insert_phi_nodes. If VAR needs PHI nodes, insert them
405 at the dominance frontier (DFS) of blocks defining VAR. */
408 void insert_phi_nodes_1 (tree var
, bitmap
*dfs
, varray_type
*work_stack
)
410 var_ann_t ann
= var_ann (var
);
411 if (ann
->need_phi_state
!= NEED_PHI_STATE_NO
)
412 insert_phi_nodes_for (var
, dfs
, work_stack
);
416 /* Insert PHI nodes at the dominance frontier of blocks with variable
417 definitions. DFS contains the dominance frontier information for
418 the flowgraph. PHI nodes will only be inserted at the dominance
419 frontier of definition blocks for variables whose NEED_PHI_STATE
420 annotation is marked as ``maybe'' or ``unknown'' (computed by
424 insert_phi_nodes (bitmap
*dfs
)
427 varray_type work_stack
;
429 timevar_push (TV_TREE_INSERT_PHI_NODES
);
431 /* Array WORK_STACK is a stack of CFG blocks. Each block that contains
432 an assignment or PHI node will be pushed to this stack. */
433 VARRAY_BB_INIT (work_stack
, last_basic_block
, "work_stack");
435 /* Iterate over all variables in VARS_TO_RENAME. For each variable, add
436 to the work list all the blocks that have a definition for the
437 variable. PHI nodes will be added to the dominance frontier blocks of
438 each definition block. */
440 EXECUTE_IF_SET_IN_BITMAP (vars_to_rename
, 0, i
,
441 insert_phi_nodes_1 (referenced_var (i
), dfs
, &work_stack
));
443 for (i
= 0; i
< num_referenced_vars
; i
++)
444 insert_phi_nodes_1 (referenced_var (i
), dfs
, &work_stack
);
446 timevar_pop (TV_TREE_INSERT_PHI_NODES
);
450 /* Perform a depth-first traversal of the dominator tree looking for
451 variables to rename. BB is the block where to start searching.
452 Renaming is a five step process:
454 1- Every definition made by PHI nodes at the start of the blocks is
455 registered as the current definition for the corresponding variable.
457 2- Every statement in BB is rewritten. USE and VUSE operands are
458 rewritten with their corresponding reaching definition. DEF and
459 VDEF targets are registered as new definitions.
461 3- All the PHI nodes in successor blocks of BB are visited. The
462 argument corresponding to BB is replaced with its current reaching
465 4- Recursively rewrite every dominator child block of BB.
467 5- Restore (in reverse order) the current reaching definition for every
468 new definition introduced in this block. This is done so that when
469 we return from the recursive call, all the current reaching
470 definitions are restored to the names that were valid in the
471 dominator parent of BB. */
473 /* Initialize the local stacks.
475 BLOCK_DEFS is used to save all the existing reaching definitions for
476 the new SSA names introduced in this block. Before registering a
477 new definition for a variable, the existing reaching definition is
478 pushed into this stack so that we can restore it in Step 5. */
481 rewrite_initialize_block_local_data (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
482 basic_block bb ATTRIBUTE_UNUSED
,
483 bool recycled ATTRIBUTE_UNUSED
)
485 #ifdef ENABLE_CHECKING
486 struct rewrite_block_data
*bd
487 = (struct rewrite_block_data
*)VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
489 /* We get cleared memory from the allocator, so if the memory is
490 not cleared, then we are re-using a previously allocated entry. In
491 that case, we can also re-use the underlying virtual arrays. Just
492 make sure we clear them before using them! */
493 if (recycled
&& bd
->block_defs
&& VARRAY_ACTIVE_SIZE (bd
->block_defs
) > 0)
499 /* SSA Rewriting Step 1. Initialization, create a block local stack
500 of reaching definitions for new SSA names produced in this block
501 (BLOCK_DEFS). Register new definitions for every PHI node in the
505 rewrite_initialize_block (struct dom_walk_data
*walk_data
, basic_block bb
)
508 struct rewrite_block_data
*bd
509 = (struct rewrite_block_data
*)VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
511 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
512 fprintf (dump_file
, "\n\nRenaming block #%d\n\n", bb
->index
);
514 /* Step 1. Register new definitions for every PHI node in the block.
515 Conceptually, all the PHI nodes are executed in parallel and each PHI
516 node introduces a new version for the associated variable. */
517 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
519 tree result
= PHI_RESULT (phi
);
521 register_new_def (result
, &bd
->block_defs
);
526 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
527 PHI nodes. For every PHI node found, add a new argument containing the
528 current reaching definition for the variable and the edge through which
529 that definition is reaching the PHI node. */
532 rewrite_add_phi_arguments (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
537 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
541 for (phi
= phi_nodes (e
->dest
); phi
; phi
= TREE_CHAIN (phi
))
545 /* If this PHI node has already been rewritten, then there is
546 nothing to do for this PHI or any following PHIs since we
547 always add new PHI nodes at the start of the PHI chain. */
548 if (PHI_REWRITTEN (phi
))
551 currdef
= get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi
)));
552 add_phi_arg (&phi
, currdef
, e
);
557 /* SSA Rewriting Step 5. Restore the current reaching definition for each
558 variable referenced in the block (in reverse order). */
561 rewrite_finalize_block (struct dom_walk_data
*walk_data
,
562 basic_block bb ATTRIBUTE_UNUSED
)
564 struct rewrite_block_data
*bd
565 = (struct rewrite_block_data
*)VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
567 /* Step 5. Restore the current reaching definition for each variable
568 referenced in the block (in reverse order). */
569 while (bd
->block_defs
&& VARRAY_ACTIVE_SIZE (bd
->block_defs
) > 0)
571 tree tmp
= VARRAY_TOP_TREE (bd
->block_defs
);
574 VARRAY_POP (bd
->block_defs
);
575 if (TREE_CODE (tmp
) == SSA_NAME
)
578 var
= SSA_NAME_VAR (saved_def
);
586 var_ann (var
)->current_def
= saved_def
;
591 /* Dump SSA information to FILE. */
594 dump_tree_ssa (FILE *file
)
598 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
600 fprintf (file
, "SSA information for %s\n\n", funcname
);
604 dump_bb (bb
, file
, 0);
606 print_generic_stmt (file
, phi_nodes (bb
), dump_flags
);
607 fputs ("\n\n", file
);
612 /* Dump SSA information to stderr. */
615 debug_tree_ssa (void)
617 dump_tree_ssa (stderr
);
621 /* Dump SSA statistics on FILE. */
624 dump_tree_ssa_stats (FILE *file
)
626 fprintf (file
, "\nHash table statistics:\n");
628 fprintf (file
, " def_blocks: ");
629 htab_statistics (file
, def_blocks
);
631 fprintf (file
, "\n");
635 /* Dump SSA statistics on stderr. */
638 debug_tree_ssa_stats (void)
640 dump_tree_ssa_stats (stderr
);
644 /* Dump statistics for the hash table HTAB. */
647 htab_statistics (FILE *file
, htab_t htab
)
649 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
650 (long) htab_size (htab
),
651 (long) htab_elements (htab
),
652 htab_collisions (htab
));
656 /* Insert PHI nodes for variable VAR using the dominance frontier
657 information given in DFS. */
660 insert_phi_nodes_for (tree var
, bitmap
*dfs
, varray_type
*work_stack
)
662 struct def_blocks_d
*def_map
;
663 bitmap phi_insertion_points
;
666 def_map
= find_def_blocks_for (var
);
670 phi_insertion_points
= BITMAP_XMALLOC ();
672 EXECUTE_IF_SET_IN_BITMAP (def_map
->def_blocks
, 0, bb_index
,
674 VARRAY_PUSH_BB (*work_stack
, BASIC_BLOCK (bb_index
));
677 /* Pop a block off the worklist, add every block that appears in
678 the original block's dfs that we have not already processed to
679 the worklist. Iterate until the worklist is empty. Blocks
680 which are added to the worklist are potential sites for
683 The iteration step could be done during PHI insertion just as
684 easily. We do it here for historical reasons -- we used to have
685 a heuristic which used the potential PHI insertion points to
686 determine if fully pruned or semi pruned SSA form was appropriate.
688 We now always use fully pruned SSA form. */
689 while (VARRAY_ACTIVE_SIZE (*work_stack
) > 0)
691 basic_block bb
= VARRAY_TOP_BB (*work_stack
);
692 int bb_index
= bb
->index
;
695 VARRAY_POP (*work_stack
);
697 EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs
[bb_index
],
698 phi_insertion_points
,
701 basic_block bb
= BASIC_BLOCK (dfs_index
);
703 VARRAY_PUSH_BB (*work_stack
, bb
);
704 bitmap_set_bit (phi_insertion_points
, dfs_index
);
708 /* Now compute global livein for this variable. Note this modifies
709 def_map->livein_blocks. */
710 compute_global_livein (def_map
->livein_blocks
, def_map
->def_blocks
);
712 /* And insert the PHI nodes. */
713 EXECUTE_IF_AND_IN_BITMAP (phi_insertion_points
, def_map
->livein_blocks
,
716 create_phi_node (var
, BASIC_BLOCK (bb_index
));
719 BITMAP_XFREE (phi_insertion_points
);
722 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
723 the block with its immediate reaching definitions. Update the current
724 definition of a variable when a new real or virtual definition is found. */
727 rewrite_stmt (struct dom_walk_data
*walk_data
,
728 basic_block bb ATTRIBUTE_UNUSED
,
729 block_stmt_iterator si
)
735 v_may_def_optype v_may_defs
;
736 v_must_def_optype v_must_defs
;
739 struct rewrite_block_data
*bd
;
741 bd
= VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
743 stmt
= bsi_stmt (si
);
744 ann
= stmt_ann (stmt
);
746 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
748 fprintf (dump_file
, "Renaming statement ");
749 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
750 fprintf (dump_file
, "\n");
753 #if defined ENABLE_CHECKING
754 /* We have just scanned the code for operands. No statement should
760 defs
= DEF_OPS (ann
);
761 uses
= USE_OPS (ann
);
762 vuses
= VUSE_OPS (ann
);
763 v_may_defs
= V_MAY_DEF_OPS (ann
);
764 v_must_defs
= V_MUST_DEF_OPS (ann
);
766 /* Step 1. Rewrite USES and VUSES in the statement. */
767 for (i
= 0; i
< NUM_USES (uses
); i
++)
768 rewrite_operand (USE_OP_PTR (uses
, i
));
770 /* Rewrite virtual uses in the statement. */
771 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
772 rewrite_operand (VUSE_OP_PTR (vuses
, i
));
774 /* Step 2. Register the statement's DEF and VDEF operands. */
775 for (i
= 0; i
< NUM_DEFS (defs
); i
++)
777 tree
*def_p
= DEF_OP_PTR (defs
, i
);
779 if (TREE_CODE (*def_p
) != SSA_NAME
)
780 *def_p
= make_ssa_name (*def_p
, stmt
);
782 /* FIXME: We shouldn't be registering new defs if the variable
783 doesn't need to be renamed. */
784 register_new_def (*def_p
, &bd
->block_defs
);
787 /* Register new virtual definitions made by the statement. */
788 for (i
= 0; i
< NUM_V_MAY_DEFS (v_may_defs
); i
++)
790 rewrite_operand (V_MAY_DEF_OP_PTR (v_may_defs
, i
));
792 if (TREE_CODE (V_MAY_DEF_RESULT (v_may_defs
, i
)) != SSA_NAME
)
793 *V_MAY_DEF_RESULT_PTR (v_may_defs
, i
)
794 = make_ssa_name (V_MAY_DEF_RESULT (v_may_defs
, i
), stmt
);
796 /* FIXME: We shouldn't be registering new defs if the variable
797 doesn't need to be renamed. */
798 register_new_def (V_MAY_DEF_RESULT (v_may_defs
, i
), &bd
->block_defs
);
801 /* Register new virtual mustdefs made by the statement. */
802 for (i
= 0; i
< NUM_V_MUST_DEFS (v_must_defs
); i
++)
804 tree
*v_must_def_p
= V_MUST_DEF_OP_PTR (v_must_defs
, i
);
806 if (TREE_CODE (*v_must_def_p
) != SSA_NAME
)
807 *v_must_def_p
= make_ssa_name (*v_must_def_p
, stmt
);
809 /* FIXME: We shouldn't be registering new mustdefs if the variable
810 doesn't need to be renamed. */
811 register_new_def (*v_must_def_p
, &bd
->block_defs
);
817 /* Replace the operand pointed by OP_P with its immediate reaching
821 rewrite_operand (tree
*op_p
)
823 if (TREE_CODE (*op_p
) != SSA_NAME
)
824 *op_p
= get_reaching_def (*op_p
);
828 /* Register DEF (an SSA_NAME) to be a new definition for its underlying
829 variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition
830 into the stack pointed by BLOCK_DEFS_P. */
833 register_new_def (tree def
, varray_type
*block_defs_p
)
835 tree var
= SSA_NAME_VAR (def
);
838 /* If this variable is set in a single basic block and all uses are
839 dominated by the set(s) in that single basic block, then there is
840 no reason to record anything for this variable in the block local
841 definition stacks. Doing so just wastes time and memory.
843 This is the same test to prune the set of variables which may
844 need PHI nodes. So we just use that information since it's already
845 computed and available for us to use. */
846 if (var_ann (var
)->need_phi_state
== NEED_PHI_STATE_NO
)
848 var_ann (var
)->current_def
= def
;
852 currdef
= var_ann (var
)->current_def
;
854 VARRAY_TREE_INIT (*block_defs_p
, 20, "block_defs");
856 /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
857 later used by the dominator tree callbacks to restore the reaching
858 definitions for all the variables defined in the block after a recursive
859 visit to all its immediately dominated blocks. If there is no current
860 reaching definition, then just record the underlying _DECL node. */
861 VARRAY_PUSH_TREE (*block_defs_p
, currdef
? currdef
: var
);
863 /* Set the current reaching definition for VAR to be DEF. */
864 var_ann (var
)->current_def
= def
;
868 /* Return the current definition for variable VAR. If none is found,
869 create a new SSA name to act as the zeroth definition for VAR. If VAR
870 is call clobbered and there exists a more recent definition of
871 GLOBAL_VAR, return the definition for GLOBAL_VAR. This means that VAR
872 has been clobbered by a function call since its last assignment. */
875 get_reaching_def (tree var
)
877 tree default_d
, currdef_var
;
879 /* Lookup the current reaching definition for VAR. */
880 default_d
= NULL_TREE
;
881 currdef_var
= var_ann (var
)->current_def
;
883 /* If there is no reaching definition for VAR, create and register a
884 default definition for it (if needed). */
885 if (currdef_var
== NULL_TREE
)
887 default_d
= default_def (var
);
888 if (default_d
== NULL_TREE
)
890 default_d
= make_ssa_name (var
, build_empty_stmt ());
891 set_default_def (var
, default_d
);
893 var_ann (var
)->current_def
= default_d
;
896 /* Return the current reaching definition for VAR, or the default
897 definition, if we had to create one. */
898 return (currdef_var
) ? currdef_var
: default_d
;
902 /* Hashing and equality functions for DEF_BLOCKS. */
905 def_blocks_hash (const void *p
)
907 return htab_hash_pointer
908 ((const void *)((const struct def_blocks_d
*)p
)->var
);
912 def_blocks_eq (const void *p1
, const void *p2
)
914 return ((const struct def_blocks_d
*)p1
)->var
915 == ((const struct def_blocks_d
*)p2
)->var
;
918 /* Free memory allocated by one entry in DEF_BLOCKS. */
921 def_blocks_free (void *p
)
923 struct def_blocks_d
*entry
= p
;
924 BITMAP_XFREE (entry
->def_blocks
);
925 BITMAP_XFREE (entry
->livein_blocks
);
930 /* Dump the DEF_BLOCKS hash table on stderr. */
933 debug_def_blocks (void)
935 htab_traverse (def_blocks
, debug_def_blocks_r
, NULL
);
938 /* Callback for htab_traverse to dump the DEF_BLOCKS hash table. */
941 debug_def_blocks_r (void **slot
, void *data ATTRIBUTE_UNUSED
)
944 struct def_blocks_d
*db_p
= (struct def_blocks_d
*) *slot
;
946 fprintf (stderr
, "VAR: ");
947 print_generic_expr (stderr
, db_p
->var
, dump_flags
);
948 fprintf (stderr
, ", DEF_BLOCKS: { ");
949 EXECUTE_IF_SET_IN_BITMAP (db_p
->def_blocks
, 0, i
,
950 fprintf (stderr
, "%ld ", i
));
951 fprintf (stderr
, "}");
952 fprintf (stderr
, ", LIVEIN_BLOCKS: { ");
953 EXECUTE_IF_SET_IN_BITMAP (db_p
->livein_blocks
, 0, i
,
954 fprintf (stderr
, "%ld ", i
));
955 fprintf (stderr
, "}\n");
961 /* Return the set of blocks where variable VAR is defined and the blocks
962 where VAR is live on entry (livein). Return NULL, if no entry is
963 found in DEF_BLOCKS. */
965 static inline struct def_blocks_d
*
966 find_def_blocks_for (tree var
)
968 struct def_blocks_d dm
;
970 return (struct def_blocks_d
*) htab_find (def_blocks
, &dm
);
974 /* Return the set of blocks where variable VAR is defined and the blocks
975 where VAR is live on entry (livein). If no entry is found in
976 DEF_BLOCKS, a new one is created and returned. */
978 static inline struct def_blocks_d
*
979 get_def_blocks_for (tree var
)
981 struct def_blocks_d db
, *db_p
;
985 slot
= htab_find_slot (def_blocks
, (void *) &db
, INSERT
);
988 db_p
= xmalloc (sizeof (*db_p
));
990 db_p
->def_blocks
= BITMAP_XMALLOC ();
991 db_p
->livein_blocks
= BITMAP_XMALLOC ();
992 *slot
= (void *) db_p
;
995 db_p
= (struct def_blocks_d
*) *slot
;
1000 /* If a variable V in VARS_TO_RENAME is a pointer, the renaming
1001 process will cause us to lose the name memory tags that may have
1002 been associated with the various SSA_NAMEs of V. This means that
1003 the variables aliased to those name tags also need to be renamed
1006 FIXME 1- We should either have a better scheme for renaming
1007 pointers that doesn't lose name tags or re-run alias
1008 analysis to recover points-to information.
1010 2- Currently we just invalidate *all* the name tags. This
1011 should be more selective. */
1014 invalidate_name_tags (bitmap vars_to_rename
)
1017 bool rename_name_tags_p
;
1019 rename_name_tags_p
= false;
1020 EXECUTE_IF_SET_IN_BITMAP (vars_to_rename
, 0, i
,
1021 if (POINTER_TYPE_P (TREE_TYPE (referenced_var (i
))))
1023 rename_name_tags_p
= true;
1027 if (rename_name_tags_p
)
1028 for (i
= 0; i
< num_referenced_vars
; i
++)
1030 var_ann_t ann
= var_ann (referenced_var (i
));
1032 if (ann
->mem_tag_kind
== NAME_TAG
)
1035 varray_type may_aliases
= ann
->may_aliases
;
1037 bitmap_set_bit (vars_to_rename
, ann
->uid
);
1038 if (ann
->may_aliases
)
1039 for (j
= 0; j
< VARRAY_ACTIVE_SIZE (may_aliases
); j
++)
1041 tree var
= VARRAY_TREE (may_aliases
, j
);
1042 bitmap_set_bit (vars_to_rename
, var_ann (var
)->uid
);
1049 /* Main entry point into the SSA builder. The renaming process
1050 proceeds in five main phases:
1052 1- If VARS_TO_RENAME has any entries, any existing PHI nodes for
1053 those variables are removed from the flow graph so that they can
1056 2- Compute dominance frontier and immediate dominators, needed to
1057 insert PHI nodes and rename the function in dominator tree
1060 3- Find and mark all the blocks that define variables
1063 4- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
1065 5- Rename all the blocks (rewrite_initialize_block,
1066 rewrite_add_phi_arguments) and statements in the program
1069 Steps 3 and 5 are done using the dominator tree walker
1070 (walk_dominator_tree). */
1073 rewrite_into_ssa (void)
1077 struct dom_walk_data walk_data
;
1078 struct mark_def_sites_global_data mark_def_sites_global_data
;
1081 timevar_push (TV_TREE_SSA_OTHER
);
1083 /* Initialize the array of variables to rename. */
1084 if (vars_to_rename
!= NULL
)
1086 invalidate_name_tags (vars_to_rename
);
1088 /* Now remove all the existing PHI nodes (if any) for the variables
1089 that we are about to rename into SSA. */
1090 remove_all_phi_nodes_for (vars_to_rename
);
1093 /* Allocate memory for the DEF_BLOCKS hash table. */
1094 def_blocks
= htab_create (VARRAY_ACTIVE_SIZE (referenced_vars
),
1095 def_blocks_hash
, def_blocks_eq
, def_blocks_free
);
1097 /* Initialize dominance frontier and immediate dominator bitmaps.
1098 Also count the number of predecessors for each block. Doing so
1099 can save significant time during PHI insertion for large graphs. */
1100 dfs
= (bitmap
*) xmalloc (last_basic_block
* sizeof (bitmap
*));
1106 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1109 bb_ann (bb
)->num_preds
= count
;
1110 dfs
[bb
->index
] = BITMAP_XMALLOC ();
1113 for (i
= 0; i
< num_referenced_vars
; i
++)
1114 var_ann (referenced_var (i
))->current_def
= NULL
;
1116 /* Ensure that the dominance information is OK. */
1117 calculate_dominance_info (CDI_DOMINATORS
);
1119 /* Compute dominance frontiers. */
1120 compute_dominance_frontiers (dfs
);
1122 /* Setup callbacks for the generic dominator tree walker to find and
1123 mark definition sites. */
1124 walk_data
.walk_stmts_backward
= false;
1125 walk_data
.dom_direction
= CDI_DOMINATORS
;
1126 walk_data
.initialize_block_local_data
= NULL
;
1127 walk_data
.before_dom_children_before_stmts
= mark_def_sites_initialize_block
;
1128 walk_data
.before_dom_children_walk_stmts
= mark_def_sites
;
1129 walk_data
.before_dom_children_after_stmts
= NULL
;
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
= NULL
;
1134 /* Notice that this bitmap is indexed using variable UIDs, so it must be
1135 large enough to accommodate all the variables referenced in the
1136 function, not just the ones we are renaming. */
1137 mark_def_sites_global_data
.kills
= sbitmap_alloc (num_referenced_vars
);
1138 walk_data
.global_data
= &mark_def_sites_global_data
;
1140 /* We do not have any local data. */
1141 walk_data
.block_local_data_size
= 0;
1143 /* Initialize the dominator walker. */
1144 init_walk_dominator_tree (&walk_data
);
1146 /* Recursively walk the dominator tree. */
1147 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1149 /* Finalize the dominator walker. */
1150 fini_walk_dominator_tree (&walk_data
);
1152 /* We no longer need this bitmap, clear and free it. */
1153 sbitmap_free (mark_def_sites_global_data
.kills
);
1155 /* Insert PHI nodes at dominance frontiers of definition blocks. */
1156 insert_phi_nodes (dfs
);
1158 /* Rewrite all the basic blocks in the program. */
1159 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS
);
1161 /* Setup callbacks for the generic dominator tree walker. */
1162 walk_data
.walk_stmts_backward
= false;
1163 walk_data
.dom_direction
= CDI_DOMINATORS
;
1164 walk_data
.initialize_block_local_data
= rewrite_initialize_block_local_data
;
1165 walk_data
.before_dom_children_before_stmts
= rewrite_initialize_block
;
1166 walk_data
.before_dom_children_walk_stmts
= rewrite_stmt
;
1167 walk_data
.before_dom_children_after_stmts
= rewrite_add_phi_arguments
;
1168 walk_data
.after_dom_children_before_stmts
= NULL
;
1169 walk_data
.after_dom_children_walk_stmts
= NULL
;
1170 walk_data
.after_dom_children_after_stmts
= rewrite_finalize_block
;
1171 walk_data
.global_data
= NULL
;
1172 walk_data
.block_local_data_size
= sizeof (struct rewrite_block_data
);
1174 /* Initialize the dominator walker. */
1175 init_walk_dominator_tree (&walk_data
);
1177 /* Recursively walk the dominator tree rewriting each statement in
1178 each basic block. */
1179 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1181 /* Finalize the dominator walker. */
1182 fini_walk_dominator_tree (&walk_data
);
1184 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS
);
1186 /* Debugging dumps. */
1187 if (dump_file
&& (dump_flags
& TDF_STATS
))
1189 dump_dfa_stats (dump_file
);
1190 dump_tree_ssa_stats (dump_file
);
1193 /* Free allocated memory. */
1195 BITMAP_XFREE (dfs
[bb
->index
]);
1198 htab_delete (def_blocks
);
1200 timevar_pop (TV_TREE_SSA_OTHER
);
1203 struct tree_opt_pass pass_build_ssa
=
1207 rewrite_into_ssa
, /* execute */
1210 0, /* static_pass_number */
1212 PROP_cfg
| PROP_referenced_vars
, /* properties_required */
1213 PROP_ssa
, /* properties_provided */
1214 0, /* properties_destroyed */
1215 0, /* todo_flags_start */
1216 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */