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>
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"
45 #include "tree-dump.h"
46 #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. */
57 /* Structure to map a variable VAR to the set of blocks that contain
58 definitions for VAR. */
64 /* Blocks that contain definitions of VAR. Bit I will be set if the
65 Ith block contains a definition of VAR. */
68 /* Blocks that contain a PHI node for VAR. */
71 /* Blocks where VAR is live-on-entry. Similar semantics as
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
;
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.
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
93 An SSA_NAME indicates that the current definition of the underlying
94 variable should be set to the given SSA_NAME.
96 A _DECL node indicates that the underlying variable has no current
99 A NULL node is used to mark the last node associated with the
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
106 The top entry is an SSA_NAME and the top-1 entry is the
107 current value for that SSA_NAME.
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
;
113 /* Basic block vectors used in this file ought to be allocated in the heap. */
114 DEF_VEC_MALLOC_P(int);
116 /* Global data to attach to the main dominator walk structure. */
117 struct mark_def_sites_global_data
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
125 /* Bitmap of names to rename. */
126 sbitmap names_to_rename
;
130 /* Information stored for ssa names. */
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
136 ENUM_BITFIELD (need_phi_state
) need_phi_state
: 2;
138 /* The actual definition of the ssa name. */
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)
149 /* Get the information associated with NAME. */
151 static inline struct ssa_name_info
*
152 get_ssa_name_ann (tree name
)
154 if (!SSA_NAME_AUX (name
))
155 SSA_NAME_AUX (name
) = xcalloc (1, sizeof (struct ssa_name_info
));
157 return SSA_NAME_AUX (name
);
161 /* Gets phi_state field for VAR. */
163 static inline enum need_phi_state
164 get_phi_state (tree var
)
166 if (TREE_CODE (var
) == SSA_NAME
)
167 return get_ssa_name_ann (var
)->need_phi_state
;
169 return var_ann (var
)->need_phi_state
;
173 /* Sets phi_state field for VAR to STATE. */
176 set_phi_state (tree var
, enum need_phi_state state
)
178 if (TREE_CODE (var
) == SSA_NAME
)
179 get_ssa_name_ann (var
)->need_phi_state
= state
;
181 var_ann (var
)->need_phi_state
= state
;
185 /* Return the current definition for VAR. */
188 get_current_def (tree var
)
190 if (TREE_CODE (var
) == SSA_NAME
)
191 return get_ssa_name_ann (var
)->current_def
;
193 return var_ann (var
)->current_def
;
197 /* Sets current definition of VAR to DEF. */
200 set_current_def (tree var
, tree def
)
202 if (TREE_CODE (var
) == SSA_NAME
)
203 get_ssa_name_ann (var
)->current_def
= def
;
205 var_ann (var
)->current_def
= def
;
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).
213 Note: This routine augments the existing local livein information
214 to include global livein (i.e., it modifies the underlying bitmap
218 compute_global_livein (bitmap livein
, bitmap def_blocks
)
220 basic_block bb
, *worklist
, *tos
;
225 = (basic_block
*) xmalloc (sizeof (basic_block
) * (n_basic_blocks
+ 1));
227 EXECUTE_IF_SET_IN_BITMAP (livein
, 0, i
, bi
)
229 *tos
++ = BASIC_BLOCK (i
);
232 /* Iterate until the worklist is empty. */
233 while (tos
!= worklist
)
238 /* Pull a block off the worklist. */
241 /* For each predecessor block. */
242 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
244 basic_block pred
= e
->src
;
245 int pred_index
= pred
->index
;
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
))
253 bitmap_set_bit (livein
, pred_index
);
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. */
266 static inline struct def_blocks_d
*
267 get_def_blocks_for (tree var
)
269 struct def_blocks_d db
, *db_p
;
273 slot
= htab_find_slot (def_blocks
, (void *) &db
, INSERT
);
276 db_p
= xmalloc (sizeof (*db_p
));
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
;
284 db_p
= (struct def_blocks_d
*) *slot
;
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. */
295 set_def_block (tree var
, basic_block bb
, bool phi_p
, bool is_update
)
297 struct def_blocks_d
*db_p
;
298 enum need_phi_state state
;
300 if (!is_update
&& TREE_CODE (var
) == SSA_NAME
)
301 var
= SSA_NAME_VAR (var
);
303 state
= get_phi_state (var
);
304 db_p
= get_def_blocks_for (var
);
306 /* Set the bit corresponding to the block where VAR is defined. */
307 bitmap_set_bit (db_p
->def_blocks
, bb
->index
);
309 bitmap_set_bit (db_p
->phi_blocks
, bb
->index
);
311 /* Keep track of whether or not we may need to insert PHI nodes.
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).
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
);
326 set_phi_state (var
, NEED_PHI_STATE_MAYBE
);
330 /* Mark block BB as having VAR live at the entry to BB. */
333 set_livein_block (tree var
, basic_block bb
)
335 struct def_blocks_d
*db_p
;
336 enum need_phi_state state
= get_phi_state (var
);
338 db_p
= get_def_blocks_for (var
);
340 /* Set the bit corresponding to the block where VAR is live in. */
341 bitmap_set_bit (db_p
->livein_blocks
, bb
->index
);
343 /* Keep track of whether or not we may need to insert PHI nodes.
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
)
351 int def_block_index
= bitmap_first_set_bit (db_p
->def_blocks
);
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
);
359 set_phi_state (var
, NEED_PHI_STATE_MAYBE
);
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. */
369 prepare_use_operand_for_rename (use_operand_p op_p
, size_t *uid_p
)
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
;
375 /* Ignore variables that don't need to be renamed. */
376 if (vars_to_rename
&& !bitmap_bit_p (vars_to_rename
, *uid_p
))
379 /* The variable needs to be renamed. If this is a use which already
380 has an SSA_NAME, then strip it off.
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
385 if (TREE_CODE (use
) == SSA_NAME
)
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. */
397 prepare_def_operand_for_rename (tree def
, size_t *uid_p
)
399 tree var
= (TREE_CODE (def
) != SSA_NAME
) ? def
: SSA_NAME_VAR (def
);
400 *uid_p
= var_ann (var
)->uid
;
402 /* Ignore variables that don't need to be renamed. */
403 if (vars_to_rename
&& !bitmap_bit_p (vars_to_rename
, *uid_p
))
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
414 1- Variables defined by S in DEF_OPS(S) are marked in the bitmap
415 WALK_DATA->GLOBAL_DATA->KILLS.
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
421 This information is used to determine which variables are live
422 across block boundaries to reduce the number of PHI nodes
426 mark_def_sites (struct dom_walk_data
*walk_data
,
428 block_stmt_iterator bsi
)
430 struct mark_def_sites_global_data
*gd
= walk_data
->global_data
;
431 bitmap kills
= gd
->kills
;
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
);
443 REWRITE_THIS_STMT (stmt
) = 0;
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. */
448 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
,
449 SSA_OP_USE
| SSA_OP_VUSE
| SSA_OP_VMUSTDEFKILL
)
451 if (prepare_use_operand_for_rename (use_p
, &uid
))
453 REWRITE_THIS_STMT (stmt
) = 1;
454 if (!bitmap_bit_p (kills
, uid
))
455 set_livein_block (USE_FROM_PTR (use_p
), bb
);
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
464 FOR_EACH_SSA_MAYDEF_OPERAND (def_p
, use_p
, stmt
, iter
)
466 if (prepare_use_operand_for_rename (use_p
, &uid
))
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
));
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;
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
)
482 if (prepare_def_operand_for_rename (def
, &uid
))
484 set_def_block (def
, bb
, false, false);
485 bitmap_set_bit (kills
, uid
);
486 REWRITE_THIS_STMT (stmt
) = 1;
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.
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. */
502 find_idf (bitmap def_blocks
, bitmap
*dfs
)
506 VEC(int) *work_stack
;
507 bitmap phi_insertion_points
;
509 work_stack
= VEC_alloc (int, n_basic_blocks
);
510 phi_insertion_points
= BITMAP_ALLOC (NULL
);
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 (int, work_stack
, bb_index
);
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
521 while (VEC_length (int, work_stack
) > 0)
523 bb_index
= VEC_pop (int, work_stack
);
525 EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs
[bb_index
], phi_insertion_points
,
528 /* Use a safe push because if there is a definition of VAR
529 in every basic block, then WORK_STACK may eventually have
530 more than N_BASIC_BLOCK entries. */
531 VEC_safe_push (int, work_stack
, bb_index
);
532 bitmap_set_bit (phi_insertion_points
, bb_index
);
536 VEC_free (int, work_stack
);
538 return phi_insertion_points
;
542 /* Return the set of blocks where variable VAR is defined and the blocks
543 where VAR is live on entry (livein). Return NULL, if no entry is
544 found in DEF_BLOCKS. */
546 static inline struct def_blocks_d
*
547 find_def_blocks_for (tree var
)
549 struct def_blocks_d dm
;
551 return (struct def_blocks_d
*) htab_find (def_blocks
, &dm
);
555 /* Insert PHI nodes for variable VAR using the iterated dominance
556 frontier given in PHI_INSERTION_POINTS. */
559 insert_phi_nodes_for (tree var
, bitmap phi_insertion_points
)
566 struct def_blocks_d
*def_map
;
568 def_map
= find_def_blocks_for (var
);
570 /* Remove the blocks where we already have PHI nodes for VAR. */
571 bitmap_and_compl_into (phi_insertion_points
, def_map
->phi_blocks
);
573 /* Now compute global livein for this variable. Note this modifies
574 def_map->livein_blocks. */
575 compute_global_livein (def_map
->livein_blocks
, def_map
->def_blocks
);
577 /* And insert the PHI nodes. */
578 EXECUTE_IF_AND_IN_BITMAP (phi_insertion_points
, def_map
->livein_blocks
,
581 bb
= BASIC_BLOCK (bb_index
);
582 phi
= create_phi_node (var
, bb
);
584 /* If we are rewriting SSA names, add also the PHI arguments. */
585 if (TREE_CODE (var
) == SSA_NAME
)
588 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
589 add_phi_arg (phi
, var
, e
);
595 /* Helper for insert_phi_nodes. If VAR needs PHI nodes, insert them
596 at the dominance frontier (DFS) of blocks defining VAR. */
599 insert_phi_nodes_1 (tree var
, bitmap
*dfs
)
601 struct def_blocks_d
*def_map
;
604 def_map
= find_def_blocks_for (var
);
608 idf
= find_idf (def_map
->def_blocks
, dfs
);
610 if (get_phi_state (var
) != NEED_PHI_STATE_NO
)
611 insert_phi_nodes_for (var
, idf
);
617 /* Insert PHI nodes at the dominance frontier of blocks with variable
618 definitions. DFS contains the dominance frontier information for
619 the flowgraph. PHI nodes will only be inserted at the dominance
620 frontier of definition blocks for variables whose NEED_PHI_STATE
621 annotation is marked as ``maybe'' or ``unknown'' (computed by
622 mark_def_sites). If NAMES_TO_RENAME is not NULL, do the same but
623 for ssa name rewriting. */
626 insert_phi_nodes (bitmap
*dfs
, bitmap names_to_rename
)
631 timevar_push (TV_TREE_INSERT_PHI_NODES
);
633 /* Iterate over all variables in VARS_TO_RENAME. For each variable, add
634 to the work list all the blocks that have a definition for the
635 variable. PHI nodes will be added to the dominance frontier blocks of
636 each definition block. */
639 EXECUTE_IF_SET_IN_BITMAP (names_to_rename
, 0, i
, bi
)
641 insert_phi_nodes_1 (ssa_name (i
), dfs
);
643 else if (vars_to_rename
)
645 EXECUTE_IF_SET_IN_BITMAP (vars_to_rename
, 0, i
, bi
)
646 insert_phi_nodes_1 (referenced_var (i
), dfs
);
650 for (i
= 0; i
< num_referenced_vars
; i
++)
651 insert_phi_nodes_1 (referenced_var (i
), dfs
);
654 timevar_pop (TV_TREE_INSERT_PHI_NODES
);
658 /* Register DEF (an SSA_NAME) to be a new definition for its underlying
659 variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition
660 into the stack pointed by BLOCK_DEFS_P. */
663 register_new_def (tree def
, VEC (tree_on_heap
) **block_defs_p
)
665 tree var
= SSA_NAME_VAR (def
);
668 /* If this variable is set in a single basic block and all uses are
669 dominated by the set(s) in that single basic block, then there is
670 no reason to record anything for this variable in the block local
671 definition stacks. Doing so just wastes time and memory.
673 This is the same test to prune the set of variables which may
674 need PHI nodes. So we just use that information since it's already
675 computed and available for us to use. */
676 if (get_phi_state (var
) == NEED_PHI_STATE_NO
)
678 set_current_def (var
, def
);
682 currdef
= get_current_def (var
);
684 /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
685 later used by the dominator tree callbacks to restore the reaching
686 definitions for all the variables defined in the block after a recursive
687 visit to all its immediately dominated blocks. If there is no current
688 reaching definition, then just record the underlying _DECL node. */
689 VEC_safe_push (tree_on_heap
, *block_defs_p
, currdef
? currdef
: var
);
691 /* Set the current reaching definition for VAR to be DEF. */
692 set_current_def (var
, def
);
696 /* Perform a depth-first traversal of the dominator tree looking for
697 variables to rename. BB is the block where to start searching.
698 Renaming is a five step process:
700 1- Every definition made by PHI nodes at the start of the blocks is
701 registered as the current definition for the corresponding variable.
703 2- Every statement in BB is rewritten. USE and VUSE operands are
704 rewritten with their corresponding reaching definition. DEF and
705 VDEF targets are registered as new definitions.
707 3- All the PHI nodes in successor blocks of BB are visited. The
708 argument corresponding to BB is replaced with its current reaching
711 4- Recursively rewrite every dominator child block of BB.
713 5- Restore (in reverse order) the current reaching definition for every
714 new definition introduced in this block. This is done so that when
715 we return from the recursive call, all the current reaching
716 definitions are restored to the names that were valid in the
717 dominator parent of BB. */
719 /* SSA Rewriting Step 1. Initialization, create a block local stack
720 of reaching definitions for new SSA names produced in this block
721 (BLOCK_DEFS). Register new definitions for every PHI node in the
725 rewrite_initialize_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
730 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
731 fprintf (dump_file
, "\n\nRenaming block #%d\n\n", bb
->index
);
733 /* Mark the unwind point for this block. */
734 VEC_safe_push (tree_on_heap
, block_defs_stack
, NULL_TREE
);
736 /* Step 1. Register new definitions for every PHI node in the block.
737 Conceptually, all the PHI nodes are executed in parallel and each PHI
738 node introduces a new version for the associated variable. */
739 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
741 tree result
= PHI_RESULT (phi
);
742 register_new_def (result
, &block_defs_stack
);
747 /* Return the current definition for variable VAR. If none is found,
748 create a new SSA name to act as the zeroth definition for VAR. If VAR
749 is call clobbered and there exists a more recent definition of
750 GLOBAL_VAR, return the definition for GLOBAL_VAR. This means that VAR
751 has been clobbered by a function call since its last assignment. */
754 get_reaching_def (tree var
)
756 tree default_d
, currdef_var
, avar
;
758 /* Lookup the current reaching definition for VAR. */
759 default_d
= NULL_TREE
;
760 currdef_var
= get_current_def (var
);
762 /* If there is no reaching definition for VAR, create and register a
763 default definition for it (if needed). */
764 if (currdef_var
== NULL_TREE
)
766 if (TREE_CODE (var
) == SSA_NAME
)
767 avar
= SSA_NAME_VAR (var
);
771 default_d
= default_def (avar
);
772 if (default_d
== NULL_TREE
)
774 default_d
= make_ssa_name (avar
, build_empty_stmt ());
775 set_default_def (avar
, default_d
);
777 set_current_def (var
, default_d
);
780 /* Return the current reaching definition for VAR, or the default
781 definition, if we had to create one. */
782 return (currdef_var
) ? currdef_var
: default_d
;
786 /* Replace the operand pointed by OP_P with its immediate reaching
790 rewrite_operand (use_operand_p op_p
)
792 tree var
= USE_FROM_PTR (op_p
);
793 if (TREE_CODE (var
) != SSA_NAME
)
794 SET_USE (op_p
, get_reaching_def (var
));
797 #if defined ENABLE_CHECKING
798 /* If we get to this point, VAR is an SSA_NAME. If VAR's symbol
799 was marked for renaming, make sure that its reaching
800 definition is VAR itself. Otherwise, something has gone
802 tree sym
= SSA_NAME_VAR (var
);
803 if (bitmap_bit_p (vars_to_rename
, var_ann (sym
)->uid
))
804 gcc_assert (var
== get_reaching_def (SSA_NAME_VAR (var
)));
810 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
811 the block with its immediate reaching definitions. Update the current
812 definition of a variable when a new real or virtual definition is found. */
815 rewrite_stmt (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
816 basic_block bb ATTRIBUTE_UNUSED
,
817 block_stmt_iterator si
)
824 stmt
= bsi_stmt (si
);
826 /* If mark_def_sites decided that we don't need to rewrite this
827 statement, ignore it. */
828 if (!REWRITE_THIS_STMT (stmt
))
831 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
833 fprintf (dump_file
, "Renaming statement ");
834 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
835 fprintf (dump_file
, "\n");
838 get_stmt_operands (stmt
);
840 /* Step 1. Rewrite USES and VUSES in the statement. */
841 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
| SSA_OP_ALL_KILLS
)
842 rewrite_operand (use_p
);
844 /* Step 2. Register the statement's DEF and VDEF operands. */
845 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
847 if (TREE_CODE (DEF_FROM_PTR (def_p
)) != SSA_NAME
)
848 SET_DEF (def_p
, make_ssa_name (DEF_FROM_PTR (def_p
), stmt
));
850 /* FIXME: We shouldn't be registering new defs if the variable
851 doesn't need to be renamed. */
852 register_new_def (DEF_FROM_PTR (def_p
), &block_defs_stack
);
857 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
858 PHI nodes. For every PHI node found, add a new argument containing the
859 current reaching definition for the variable and the edge through which
860 that definition is reaching the PHI node. */
863 rewrite_add_phi_arguments (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
869 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
873 for (phi
= phi_nodes (e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
877 /* If this PHI node has already been rewritten, then there is
878 nothing to do for this PHI or any following PHIs since we
879 always add new PHI nodes at the start of the PHI chain. */
880 if (PHI_REWRITTEN (phi
))
883 currdef
= get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi
)));
884 add_phi_arg (phi
, currdef
, e
);
890 /* Rewrite existing virtual PHI arguments so that they have the correct
891 reaching definitions. BB is the basic block whose successors contain the
892 PHI nodes we want to add arguments for. */
895 rewrite_virtual_phi_arguments (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
902 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
906 if (e
->dest
== EXIT_BLOCK_PTR
)
909 for (phi
= phi_nodes (e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
911 tree result
= PHI_RESULT (phi
);
912 op
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
914 if (is_gimple_reg (result
)
915 || !bitmap_bit_p (vars_to_rename
,
916 var_ann (SSA_NAME_VAR (result
))->uid
))
919 SET_USE (op
, get_reaching_def (SSA_NAME_VAR (result
)));
920 if (e
->flags
& EDGE_ABNORMAL
)
921 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (op
)) = 1;
927 /* Called after visiting basic block BB. Restore CURRDEFS to its
931 rewrite_finalize_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
932 basic_block bb ATTRIBUTE_UNUSED
)
934 /* Restore CURRDEFS to its original state. */
935 while (VEC_length (tree_on_heap
, block_defs_stack
) > 0)
937 tree tmp
= VEC_pop (tree_on_heap
, block_defs_stack
);
940 if (tmp
== NULL_TREE
)
943 /* If we recorded an SSA_NAME, then make the SSA_NAME the current
944 definition of its underlying variable. If we recorded anything
945 else, it must have been an _DECL node and its current reaching
946 definition must have been NULL. */
947 if (TREE_CODE (tmp
) == SSA_NAME
)
950 var
= SSA_NAME_VAR (saved_def
);
958 set_current_def (var
, saved_def
);
963 /* Dump SSA information to FILE. */
966 dump_tree_ssa (FILE *file
)
970 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
972 fprintf (file
, "SSA information for %s\n\n", funcname
);
976 dump_bb (bb
, file
, 0);
978 print_generic_stmt (file
, phi_nodes (bb
), dump_flags
);
979 fputs ("\n\n", file
);
984 /* Dump SSA information to stderr. */
987 debug_tree_ssa (void)
989 dump_tree_ssa (stderr
);
993 /* Dump statistics for the hash table HTAB. */
996 htab_statistics (FILE *file
, htab_t htab
)
998 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
999 (long) htab_size (htab
),
1000 (long) htab_elements (htab
),
1001 htab_collisions (htab
));
1005 /* Dump SSA statistics on FILE. */
1008 dump_tree_ssa_stats (FILE *file
)
1010 fprintf (file
, "\nHash table statistics:\n");
1012 fprintf (file
, " def_blocks: ");
1013 htab_statistics (file
, def_blocks
);
1015 fprintf (file
, "\n");
1019 /* Dump SSA statistics on stderr. */
1022 debug_tree_ssa_stats (void)
1024 dump_tree_ssa_stats (stderr
);
1028 /* Hashing and equality functions for DEF_BLOCKS. */
1031 def_blocks_hash (const void *p
)
1033 return htab_hash_pointer
1034 ((const void *)((const struct def_blocks_d
*)p
)->var
);
1038 def_blocks_eq (const void *p1
, const void *p2
)
1040 return ((const struct def_blocks_d
*)p1
)->var
1041 == ((const struct def_blocks_d
*)p2
)->var
;
1045 /* Free memory allocated by one entry in DEF_BLOCKS. */
1048 def_blocks_free (void *p
)
1050 struct def_blocks_d
*entry
= p
;
1051 BITMAP_FREE (entry
->def_blocks
);
1052 BITMAP_FREE (entry
->phi_blocks
);
1053 BITMAP_FREE (entry
->livein_blocks
);
1058 /* Callback for htab_traverse to dump the DEF_BLOCKS hash table. */
1061 debug_def_blocks_r (void **slot
, void *data ATTRIBUTE_UNUSED
)
1063 struct def_blocks_d
*db_p
= (struct def_blocks_d
*) *slot
;
1065 fprintf (stderr
, "VAR: ");
1066 print_generic_expr (stderr
, db_p
->var
, dump_flags
);
1067 bitmap_print (stderr
, db_p
->def_blocks
, ", DEF_BLOCKS: { ", "}");
1068 bitmap_print (stderr
, db_p
->livein_blocks
, ", LIVEIN_BLOCKS: { ", "}\n");
1074 /* Dump the DEF_BLOCKS hash table on stderr. */
1077 debug_def_blocks (void)
1079 htab_traverse (def_blocks
, debug_def_blocks_r
, NULL
);
1083 /* If a variable V in VARS_TO_RENAME is a pointer, the renaming
1084 process will cause us to lose the name memory tags that may have
1085 been associated with the various SSA_NAMEs of V. This means that
1086 the variables aliased to those name tags also need to be renamed
1089 FIXME 1- We should either have a better scheme for renaming
1090 pointers that doesn't lose name tags or re-run alias
1091 analysis to recover points-to information.
1093 2- Currently we just invalidate *all* the name tags. This
1094 should be more selective. */
1097 invalidate_name_tags (bitmap vars_to_rename
)
1100 bool rename_name_tags_p
;
1103 rename_name_tags_p
= false;
1104 EXECUTE_IF_SET_IN_BITMAP (vars_to_rename
, 0, i
, bi
)
1106 if (POINTER_TYPE_P (TREE_TYPE (referenced_var (i
))))
1108 rename_name_tags_p
= true;
1113 if (rename_name_tags_p
)
1114 for (i
= 0; i
< num_referenced_vars
; i
++)
1116 var_ann_t ann
= var_ann (referenced_var (i
));
1118 if (ann
->mem_tag_kind
== NAME_TAG
)
1121 varray_type may_aliases
= ann
->may_aliases
;
1123 bitmap_set_bit (vars_to_rename
, ann
->uid
);
1124 if (ann
->may_aliases
)
1125 for (j
= 0; j
< VARRAY_ACTIVE_SIZE (may_aliases
); j
++)
1127 tree var
= VARRAY_TREE (may_aliases
, j
);
1128 bitmap_set_bit (vars_to_rename
, var_ann (var
)->uid
);
1135 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
1136 form. FIX_VIRTUAL_PHIS is true if we should only be fixing up virtual
1137 PHI arguments, instead of adding new PHI arguments for just added PHI
1141 rewrite_blocks (bool fix_virtual_phis
)
1143 struct dom_walk_data walk_data
;
1145 /* Rewrite all the basic blocks in the program. */
1146 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS
);
1148 /* Setup callbacks for the generic dominator tree walker. */
1149 walk_data
.walk_stmts_backward
= false;
1150 walk_data
.dom_direction
= CDI_DOMINATORS
;
1151 walk_data
.initialize_block_local_data
= NULL
;
1152 walk_data
.before_dom_children_before_stmts
= rewrite_initialize_block
;
1153 walk_data
.before_dom_children_walk_stmts
= rewrite_stmt
;
1154 walk_data
.before_dom_children_after_stmts
= NULL
;
1155 if (!fix_virtual_phis
)
1156 walk_data
.before_dom_children_after_stmts
= rewrite_add_phi_arguments
;
1158 walk_data
.before_dom_children_after_stmts
= rewrite_virtual_phi_arguments
;
1160 walk_data
.after_dom_children_before_stmts
= NULL
;
1161 walk_data
.after_dom_children_walk_stmts
= NULL
;
1162 walk_data
.after_dom_children_after_stmts
= rewrite_finalize_block
;
1163 walk_data
.global_data
= NULL
;
1164 walk_data
.block_local_data_size
= 0;
1166 block_defs_stack
= VEC_alloc (tree_on_heap
, 10);
1168 /* Initialize the dominator walker. */
1169 init_walk_dominator_tree (&walk_data
);
1171 /* Recursively walk the dominator tree rewriting each statement in
1172 each basic block. */
1173 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1175 /* Finalize the dominator walker. */
1176 fini_walk_dominator_tree (&walk_data
);
1178 /* Debugging dumps. */
1179 if (dump_file
&& (dump_flags
& TDF_STATS
))
1181 dump_dfa_stats (dump_file
);
1182 dump_tree_ssa_stats (dump_file
);
1185 htab_delete (def_blocks
);
1188 VEC_free (tree_on_heap
, block_defs_stack
);
1189 block_defs_stack
= NULL
;
1191 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS
);
1195 /* Block initialization routine for mark_def_sites. Clear the
1196 KILLS bitmap at the start of each block. */
1199 mark_def_sites_initialize_block (struct dom_walk_data
*walk_data
,
1200 basic_block bb ATTRIBUTE_UNUSED
)
1202 struct mark_def_sites_global_data
*gd
= walk_data
->global_data
;
1203 bitmap kills
= gd
->kills
;
1204 bitmap_clear (kills
);
1208 /* Mark the definition site blocks for each variable, so that we know where
1209 the variable is actually live. */
1212 mark_def_site_blocks (void)
1215 struct dom_walk_data walk_data
;
1216 struct mark_def_sites_global_data mark_def_sites_global_data
;
1218 /* Allocate memory for the DEF_BLOCKS hash table. */
1219 def_blocks
= htab_create (VARRAY_ACTIVE_SIZE (referenced_vars
),
1220 def_blocks_hash
, def_blocks_eq
, def_blocks_free
);
1222 for (i
= 0; i
< num_referenced_vars
; i
++)
1223 set_current_def (referenced_var (i
), NULL_TREE
);
1225 /* Ensure that the dominance information is OK. */
1226 calculate_dominance_info (CDI_DOMINATORS
);
1228 /* Setup callbacks for the generic dominator tree walker to find and
1229 mark definition sites. */
1230 walk_data
.walk_stmts_backward
= false;
1231 walk_data
.dom_direction
= CDI_DOMINATORS
;
1232 walk_data
.initialize_block_local_data
= NULL
;
1233 walk_data
.before_dom_children_before_stmts
= mark_def_sites_initialize_block
;
1234 walk_data
.before_dom_children_walk_stmts
= mark_def_sites
;
1235 walk_data
.before_dom_children_after_stmts
= NULL
;
1236 walk_data
.after_dom_children_before_stmts
= NULL
;
1237 walk_data
.after_dom_children_walk_stmts
= NULL
;
1238 walk_data
.after_dom_children_after_stmts
= NULL
;
1240 /* Notice that this bitmap is indexed using variable UIDs, so it must be
1241 large enough to accommodate all the variables referenced in the
1242 function, not just the ones we are renaming. */
1243 mark_def_sites_global_data
.kills
= BITMAP_ALLOC (NULL
);
1244 walk_data
.global_data
= &mark_def_sites_global_data
;
1246 /* We do not have any local data. */
1247 walk_data
.block_local_data_size
= 0;
1249 /* Initialize the dominator walker. */
1250 init_walk_dominator_tree (&walk_data
);
1252 /* Recursively walk the dominator tree. */
1253 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1255 /* Finalize the dominator walker. */
1256 fini_walk_dominator_tree (&walk_data
);
1258 /* We no longer need this bitmap, clear and free it. */
1259 BITMAP_FREE (mark_def_sites_global_data
.kills
);
1263 /* Main entry point into the SSA builder. The renaming process
1264 proceeds in five main phases:
1266 1- If VARS_TO_RENAME has any entries, any existing PHI nodes for
1267 those variables are removed from the flow graph so that they can
1270 2- Compute dominance frontier and immediate dominators, needed to
1271 insert PHI nodes and rename the function in dominator tree
1274 3- Find and mark all the blocks that define variables
1275 (mark_def_site_blocks).
1277 4- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
1279 5- Rename all the blocks (rewrite_blocks) and statements in the program.
1281 Steps 3 and 5 are done using the dominator tree walker
1282 (walk_dominator_tree).
1284 ALL is true if all variables should be renamed (otherwise just those
1285 mentioned in vars_to_rename are taken into account). */
1288 rewrite_into_ssa (bool all
)
1292 bitmap old_vars_to_rename
= vars_to_rename
;
1294 timevar_push (TV_TREE_SSA_OTHER
);
1297 vars_to_rename
= NULL
;
1300 /* Initialize the array of variables to rename. */
1301 gcc_assert (vars_to_rename
);
1303 if (bitmap_empty_p (vars_to_rename
))
1305 timevar_pop (TV_TREE_SSA_OTHER
);
1309 invalidate_name_tags (vars_to_rename
);
1311 /* Now remove all the existing PHI nodes (if any) for the variables
1312 that we are about to rename into SSA. */
1313 remove_all_phi_nodes_for (vars_to_rename
);
1316 mark_def_site_blocks ();
1318 /* Initialize dominance frontier and immediate dominator bitmaps.
1319 Also count the number of predecessors for each block. Doing so
1320 can save significant time during PHI insertion for large graphs. */
1321 dfs
= (bitmap
*) xmalloc (last_basic_block
* sizeof (bitmap
*));
1323 dfs
[bb
->index
] = BITMAP_ALLOC (NULL
);
1325 /* Compute dominance frontiers. */
1326 compute_dominance_frontiers (dfs
);
1328 /* Insert PHI nodes at dominance frontiers of definition blocks. */
1329 insert_phi_nodes (dfs
, NULL
);
1331 rewrite_blocks (false);
1333 /* Free allocated memory. */
1335 BITMAP_FREE (dfs
[bb
->index
]);
1338 vars_to_rename
= old_vars_to_rename
;
1339 timevar_pop (TV_TREE_SSA_OTHER
);
1343 /* Rewrites all variables into SSA. */
1346 rewrite_all_into_ssa (void)
1348 rewrite_into_ssa (true);
1351 struct tree_opt_pass pass_build_ssa
=
1355 rewrite_all_into_ssa
, /* execute */
1358 0, /* static_pass_number */
1360 PROP_cfg
| PROP_referenced_vars
, /* properties_required */
1361 PROP_ssa
, /* properties_provided */
1362 0, /* properties_destroyed */
1363 0, /* todo_flags_start */
1364 TODO_dump_func
| TODO_verify_ssa
, /* todo_flags_finish */
1369 /* Rewrite the def-def chains of virtual operands so that they have
1370 the correct reaching definitions. */
1373 rewrite_def_def_chains (void)
1375 /* Ensure that the dominance information is OK. */
1376 calculate_dominance_info (CDI_DOMINATORS
);
1377 mark_def_site_blocks ();
1378 rewrite_blocks (true);
1383 /*---------------------------------------------------------------------------
1384 Functions to fix a program in invalid SSA form into valid SSA
1385 form. The main entry point here is rewrite_ssa_into_ssa.
1386 ---------------------------------------------------------------------------*/
1388 /* Called after visiting basic block BB. Restore CURRDEFS to its
1392 ssa_rewrite_finalize_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
1393 basic_block bb ATTRIBUTE_UNUSED
)
1396 /* Step 5. Restore the current reaching definition for each variable
1397 referenced in the block (in reverse order). */
1398 while (VEC_length (tree_on_heap
, block_defs_stack
) > 0)
1400 tree var
= VEC_pop (tree_on_heap
, block_defs_stack
);
1406 saved_def
= VEC_pop (tree_on_heap
, block_defs_stack
);
1407 set_current_def (var
, saved_def
);
1412 /* Register DEF (an SSA_NAME) to be a new definition for the original
1413 ssa name VAR and push VAR's current reaching definition
1414 into the stack pointed by BLOCK_DEFS_P. */
1417 ssa_register_new_def (tree var
, tree def
)
1421 /* If this variable is set in a single basic block and all uses are
1422 dominated by the set(s) in that single basic block, then there is
1423 nothing to do. TODO we should not be called at all, and just
1424 keep the original name. */
1425 if (get_phi_state (var
) == NEED_PHI_STATE_NO
)
1427 set_current_def (var
, def
);
1431 currdef
= get_current_def (var
);
1433 /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
1434 later used by the dominator tree callbacks to restore the reaching
1435 definitions for all the variables defined in the block after a recursive
1436 visit to all its immediately dominated blocks. */
1437 VEC_safe_push (tree_on_heap
, block_defs_stack
, currdef
);
1438 VEC_safe_push (tree_on_heap
, block_defs_stack
, var
);
1440 /* Set the current reaching definition for VAR to be DEF. */
1441 set_current_def (var
, def
);
1445 /* Same as rewrite_stmt, for rewriting ssa names. */
1448 ssa_rewrite_stmt (struct dom_walk_data
*walk_data
,
1449 basic_block bb ATTRIBUTE_UNUSED
,
1450 block_stmt_iterator si
)
1455 use_operand_p use_p
;
1456 def_operand_p def_p
;
1457 sbitmap names_to_rename
= walk_data
->global_data
;
1459 stmt
= bsi_stmt (si
);
1460 ann
= stmt_ann (stmt
);
1462 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1464 fprintf (dump_file
, "Renaming statement ");
1465 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1466 fprintf (dump_file
, "\n");
1469 /* We have just scanned the code for operands. No statement should
1471 gcc_assert (!ann
->modified
);
1473 /* Step 1. Rewrite USES and VUSES in the statement. */
1474 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
| SSA_OP_ALL_KILLS
)
1476 if (TEST_BIT (names_to_rename
, SSA_NAME_VERSION (USE_FROM_PTR (use_p
))))
1477 SET_USE (use_p
, get_reaching_def (USE_FROM_PTR (use_p
)));
1480 /* Step 2. Register the statement's DEF and VDEF operands. */
1481 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1483 var
= DEF_FROM_PTR (def_p
);
1485 if (!TEST_BIT (names_to_rename
, SSA_NAME_VERSION (var
)))
1488 SET_DEF (def_p
, duplicate_ssa_name (var
, stmt
));
1489 ssa_register_new_def (var
, DEF_FROM_PTR (def_p
));
1494 /* Ditto, for ssa name rewriting. */
1497 ssa_rewrite_phi_arguments (struct dom_walk_data
*walk_data
, basic_block bb
)
1500 sbitmap names_to_rename
= walk_data
->global_data
;
1504 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1508 if (e
->dest
== EXIT_BLOCK_PTR
)
1511 for (phi
= phi_nodes (e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
1513 op
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
1514 if (TREE_CODE (USE_FROM_PTR (op
)) != SSA_NAME
)
1517 if (!TEST_BIT (names_to_rename
, SSA_NAME_VERSION (USE_FROM_PTR (op
))))
1520 SET_USE (op
, get_reaching_def (USE_FROM_PTR (op
)));
1521 if (e
->flags
& EDGE_ABNORMAL
)
1522 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (op
)) = 1;
1527 /* Ditto, for rewriting ssa names. */
1530 ssa_rewrite_initialize_block (struct dom_walk_data
*walk_data
, basic_block bb
)
1533 sbitmap names_to_rename
= walk_data
->global_data
;
1538 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1539 fprintf (dump_file
, "\n\nRenaming block #%d\n\n", bb
->index
);
1541 /* Mark the unwind point for this block. */
1542 VEC_safe_push (tree_on_heap
, block_defs_stack
, NULL_TREE
);
1544 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1545 if (e
->flags
& EDGE_ABNORMAL
)
1547 abnormal_phi
= (e
!= NULL
);
1549 /* Step 1. Register new definitions for every PHI node in the block.
1550 Conceptually, all the PHI nodes are executed in parallel and each PHI
1551 node introduces a new version for the associated variable. */
1552 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1554 tree result
= PHI_RESULT (phi
);
1556 if (TEST_BIT (names_to_rename
, SSA_NAME_VERSION (result
)))
1558 new_name
= duplicate_ssa_name (result
, phi
);
1559 SET_PHI_RESULT (phi
, new_name
);
1562 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name
) = 1;
1563 ssa_register_new_def (result
, new_name
);
1569 /* Same as mark_def_sites, but works over SSA names. */
1572 ssa_mark_def_sites (struct dom_walk_data
*walk_data
,
1574 block_stmt_iterator bsi
)
1576 struct mark_def_sites_global_data
*gd
= walk_data
->global_data
;
1577 bitmap kills
= gd
->kills
;
1578 size_t uid
, def_uid
;
1579 tree stmt
, use
, def
;
1582 /* Mark all the blocks that have definitions for each variable in the
1583 names_to_rename bitmap. */
1584 stmt
= bsi_stmt (bsi
);
1585 get_stmt_operands (stmt
);
1587 /* If a variable is used before being set, then the variable is live
1588 across a block boundary, so mark it live-on-entry to BB. */
1589 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_ALL_USES
| SSA_OP_ALL_KILLS
)
1591 uid
= SSA_NAME_VERSION (use
);
1593 if (TEST_BIT (gd
->names_to_rename
, uid
)
1594 && !bitmap_bit_p (kills
, uid
))
1595 set_livein_block (use
, bb
);
1598 /* Now process the definition made by this statement. Mark the
1599 variables in KILLS. */
1600 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1602 def_uid
= SSA_NAME_VERSION (def
);
1604 if (TEST_BIT (gd
->names_to_rename
, def_uid
))
1606 set_def_block (def
, bb
, false, true);
1607 bitmap_set_bit (kills
, def_uid
);
1613 /* Block initialization routine for mark_def_sites. Clear the
1614 KILLS bitmap at the start of each block. */
1617 ssa_mark_def_sites_initialize_block (struct dom_walk_data
*walk_data
,
1620 struct mark_def_sites_global_data
*gd
= walk_data
->global_data
;
1621 bitmap kills
= gd
->kills
;
1625 bitmap_clear (kills
);
1627 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1629 def
= PHI_RESULT (phi
);
1630 def_uid
= SSA_NAME_VERSION (def
);
1632 if (!TEST_BIT (gd
->names_to_rename
, def_uid
))
1635 set_def_block (def
, bb
, true, true);
1636 bitmap_set_bit (kills
, def_uid
);
1640 /* Marks ssa names used as arguments of phis at the end of BB. */
1643 ssa_mark_phi_uses (struct dom_walk_data
*walk_data
, basic_block bb
)
1645 struct mark_def_sites_global_data
*gd
= walk_data
->global_data
;
1646 bitmap kills
= gd
->kills
;
1652 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1654 if (e
->dest
== EXIT_BLOCK_PTR
)
1657 for (phi
= phi_nodes (e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
1659 use
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
1660 if (TREE_CODE (use
) != SSA_NAME
)
1663 uid
= SSA_NAME_VERSION (use
);
1665 if (TEST_BIT (gd
->names_to_rename
, uid
)
1666 && !bitmap_bit_p (kills
, uid
))
1667 set_livein_block (use
, bb
);
1673 /* The marked ssa names may have more than one definition;
1674 add PHI nodes and rewrite them to fix this. */
1677 rewrite_ssa_into_ssa (void)
1681 struct dom_walk_data walk_data
;
1682 struct mark_def_sites_global_data mark_def_sites_global_data
;
1684 sbitmap snames_to_rename
;
1688 if (!any_marked_for_rewrite_p ())
1690 to_rename
= marked_ssa_names ();
1692 timevar_push (TV_TREE_SSA_OTHER
);
1694 /* Allocate memory for the DEF_BLOCKS hash table. */
1695 def_blocks
= htab_create (num_ssa_names
,
1696 def_blocks_hash
, def_blocks_eq
, def_blocks_free
);
1698 /* Initialize dominance frontier and immediate dominator bitmaps.
1699 Also count the number of predecessors for each block. Doing so
1700 can save significant time during PHI insertion for large graphs. */
1701 dfs
= (bitmap
*) xmalloc (last_basic_block
* sizeof (bitmap
*));
1703 dfs
[bb
->index
] = BITMAP_ALLOC (NULL
);
1705 /* Ensure that the dominance information is OK. */
1706 calculate_dominance_info (CDI_DOMINATORS
);
1708 /* Compute dominance frontiers. */
1709 compute_dominance_frontiers (dfs
);
1711 /* Setup callbacks for the generic dominator tree walker to find and
1712 mark definition sites. */
1713 walk_data
.walk_stmts_backward
= false;
1714 walk_data
.dom_direction
= CDI_DOMINATORS
;
1715 walk_data
.initialize_block_local_data
= NULL
;
1716 walk_data
.before_dom_children_before_stmts
1717 = ssa_mark_def_sites_initialize_block
;
1718 walk_data
.before_dom_children_walk_stmts
= ssa_mark_def_sites
;
1719 walk_data
.before_dom_children_after_stmts
= ssa_mark_phi_uses
;
1720 walk_data
.after_dom_children_before_stmts
= NULL
;
1721 walk_data
.after_dom_children_walk_stmts
= NULL
;
1722 walk_data
.after_dom_children_after_stmts
= NULL
;
1724 snames_to_rename
= sbitmap_alloc (num_ssa_names
);
1725 sbitmap_zero (snames_to_rename
);
1726 EXECUTE_IF_SET_IN_BITMAP (to_rename
, 0, i
, bi
)
1728 SET_BIT (snames_to_rename
, i
);
1729 set_current_def (ssa_name (i
), NULL_TREE
);
1732 mark_def_sites_global_data
.kills
= BITMAP_ALLOC (NULL
);
1733 mark_def_sites_global_data
.names_to_rename
= snames_to_rename
;
1734 walk_data
.global_data
= &mark_def_sites_global_data
;
1736 block_defs_stack
= VEC_alloc (tree_on_heap
, 10);
1738 /* We do not have any local data. */
1739 walk_data
.block_local_data_size
= 0;
1741 /* Initialize the dominator walker. */
1742 init_walk_dominator_tree (&walk_data
);
1744 /* Recursively walk the dominator tree. */
1745 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1747 /* Finalize the dominator walker. */
1748 fini_walk_dominator_tree (&walk_data
);
1750 /* We no longer need this bitmap, clear and free it. */
1751 BITMAP_FREE (mark_def_sites_global_data
.kills
);
1753 /* Insert PHI nodes at dominance frontiers of definition blocks. */
1754 insert_phi_nodes (dfs
, to_rename
);
1756 /* Rewrite all the basic blocks in the program. */
1757 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS
);
1759 /* Setup callbacks for the generic dominator tree walker. */
1760 walk_data
.walk_stmts_backward
= false;
1761 walk_data
.dom_direction
= CDI_DOMINATORS
;
1762 walk_data
.initialize_block_local_data
= NULL
;
1763 walk_data
.before_dom_children_before_stmts
= ssa_rewrite_initialize_block
;
1764 walk_data
.before_dom_children_walk_stmts
= ssa_rewrite_stmt
;
1765 walk_data
.before_dom_children_after_stmts
= ssa_rewrite_phi_arguments
;
1766 walk_data
.after_dom_children_before_stmts
= NULL
;
1767 walk_data
.after_dom_children_walk_stmts
= NULL
;
1768 walk_data
.after_dom_children_after_stmts
= ssa_rewrite_finalize_block
;
1769 walk_data
.global_data
= snames_to_rename
;
1770 walk_data
.block_local_data_size
= 0;
1772 /* Initialize the dominator walker. */
1773 init_walk_dominator_tree (&walk_data
);
1775 /* Recursively walk the dominator tree rewriting each statement in
1776 each basic block. */
1777 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1779 /* Finalize the dominator walker. */
1780 fini_walk_dominator_tree (&walk_data
);
1782 unmark_all_for_rewrite ();
1784 EXECUTE_IF_SET_IN_BITMAP (to_rename
, 0, i
, bi
)
1786 /* Free SSA_NAME_AUX. We don't have to zero it because
1787 release_ssa_name will. */
1788 if (SSA_NAME_AUX (ssa_name (i
)))
1789 free (SSA_NAME_AUX (ssa_name (i
)));
1791 release_ssa_name (ssa_name (i
));
1794 sbitmap_free (snames_to_rename
);
1796 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS
);
1798 /* Debugging dumps. */
1799 if (dump_file
&& (dump_flags
& TDF_STATS
))
1801 dump_dfa_stats (dump_file
);
1802 dump_tree_ssa_stats (dump_file
);
1805 /* Free allocated memory. */
1807 BITMAP_FREE (dfs
[bb
->index
]);
1810 htab_delete (def_blocks
);
1812 #ifdef ENABLE_CHECKING
1813 for (i
= 1; i
< num_ssa_names
; i
++)
1815 tree name
= ssa_name (i
);
1819 gcc_assert (SSA_NAME_AUX (name
) == NULL
);
1823 BITMAP_FREE (to_rename
);
1825 VEC_free (tree_on_heap
, block_defs_stack
);
1826 block_defs_stack
= NULL
;
1827 timevar_pop (TV_TREE_SSA_OTHER
);