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"
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. */
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 that contain a phi node for VAR. */
72 /* 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 varray is used in two contexts. The first is rewriting of _DECL
90 nodes into SSA_NAMEs. In that context it's 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
103 This varray is also used when rewriting an SSA_NAME which has multiple
104 definition sites into multiple SSA_NAMEs. In that context entries come
107 The top entry is an SSA_NAME and the top-1 entry is the
108 current value for that SSA_NAME.
110 A NULL node at the top entry is used to mark the last node associated
111 with the current block. */
112 static varray_type block_defs_stack;
114 /* Global data to attach to the main dominator walk structure. */
115 struct mark_def_sites_global_data
117 /* This sbitmap contains the variables which are set before they
118 are used in a basic block. We keep it as a global variable
119 solely to avoid the overhead of allocating and deallocating
123 /* Bitmap of names to rename. */
124 sbitmap names_to_rename;
127 /* Information stored for ssa names. */
131 /* This field indicates whether or not the variable may need PHI nodes.
132 See the enum's definition for more detailed information about the
134 ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
136 /* The actual definition of the ssa name. */
140 /* Local functions. */
141 static void rewrite_finalize_block (struct dom_walk_data *, basic_block);
142 static void rewrite_initialize_block (struct dom_walk_data *, basic_block);
143 static void rewrite_add_phi_arguments (struct dom_walk_data *, basic_block);
144 static void mark_def_sites (struct dom_walk_data *walk_data,
145 basic_block bb, block_stmt_iterator);
146 static void mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
148 static void set_def_block (tree, basic_block, bool, bool);
149 static void set_livein_block (tree, basic_block);
150 static bool prepare_use_operand_for_rename (use_operand_p, size_t *uid_p);
151 static bool prepare_def_operand_for_rename (tree def, size_t *uid_p);
152 static void insert_phi_nodes (bitmap *, bitmap);
153 static void rewrite_stmt (struct dom_walk_data *, basic_block,
154 block_stmt_iterator);
155 static inline void rewrite_operand (use_operand_p);
156 static void insert_phi_nodes_for (tree, bitmap *, varray_type *);
157 static tree get_reaching_def (tree);
158 static hashval_t def_blocks_hash (const void *);
159 static int def_blocks_eq (const void *, const void *);
160 static void def_blocks_free (void *);
161 static int debug_def_blocks_r (void **, void *);
162 static inline struct def_blocks_d *get_def_blocks_for (tree);
163 static inline struct def_blocks_d *find_def_blocks_for (tree);
164 static void htab_statistics (FILE *, htab_t);
166 /* Get the information associated with NAME. */
168 static inline struct ssa_name_info *
169 get_ssa_name_ann (tree name)
171 if (!SSA_NAME_AUX (name))
172 SSA_NAME_AUX (name) = xcalloc (1, sizeof (struct ssa_name_info));
174 return SSA_NAME_AUX (name);
177 /* Gets phi_state field for VAR. */
179 static inline enum need_phi_state
180 get_phi_state (tree var)
182 if (TREE_CODE (var) == SSA_NAME)
183 return get_ssa_name_ann (var)->need_phi_state;
185 return var_ann (var)->need_phi_state;
188 /* Sets phi_state field for VAR to STATE. */
191 set_phi_state (tree var, enum need_phi_state state)
193 if (TREE_CODE (var) == SSA_NAME)
194 get_ssa_name_ann (var)->need_phi_state = state;
196 var_ann (var)->need_phi_state = state;
199 /* Return the current definition for VAR. */
202 get_current_def (tree var)
204 if (TREE_CODE (var) == SSA_NAME)
205 return get_ssa_name_ann (var)->current_def;
207 return var_ann (var)->current_def;
210 /* Sets current definition of VAR to DEF. */
213 set_current_def (tree var, tree def)
215 if (TREE_CODE (var) == SSA_NAME)
216 get_ssa_name_ann (var)->current_def = def;
218 var_ann (var)->current_def = def;
221 /* Compute global livein information given the set of blockx where
222 an object is locally live at the start of the block (LIVEIN)
223 and the set of blocks where the object is defined (DEF_BLOCKS).
225 Note: This routine augments the existing local livein information
226 to include global livein (i.e., it modifies the underlying bitmap
230 compute_global_livein (bitmap livein, bitmap def_blocks)
232 basic_block bb, *worklist, *tos;
237 = (basic_block *) xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
239 EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
241 *tos++ = BASIC_BLOCK (i);
244 /* Iterate until the worklist is empty. */
245 while (tos != worklist)
249 /* Pull a block off the worklist. */
252 /* For each predecessor block. */
253 for (e = bb->pred; e; e = e->pred_next)
255 basic_block pred = e->src;
256 int pred_index = pred->index;
258 /* None of this is necessary for the entry block. */
259 if (pred != ENTRY_BLOCK_PTR
260 && ! bitmap_bit_p (livein, pred_index)
261 && ! bitmap_bit_p (def_blocks, pred_index))
264 bitmap_set_bit (livein, pred_index);
273 /* Block initialization routine for mark_def_sites. Clear the
274 KILLS bitmap at the start of each block. */
277 mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
278 basic_block bb ATTRIBUTE_UNUSED)
280 struct mark_def_sites_global_data *gd = walk_data->global_data;
281 sbitmap kills = gd->kills;
283 sbitmap_zero (kills);
286 /* Block initialization routine for mark_def_sites. Clear the
287 KILLS bitmap at the start of each block. */
290 ssa_mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
293 struct mark_def_sites_global_data *gd = walk_data->global_data;
294 sbitmap kills = gd->kills;
298 sbitmap_zero (kills);
300 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
302 def = PHI_RESULT (phi);
303 def_uid = SSA_NAME_VERSION (def);
305 if (!TEST_BIT (gd->names_to_rename, def_uid))
308 set_def_block (def, bb, true, true);
309 SET_BIT (kills, def_uid);
313 /* Marks ssa names used as arguments of phis at the end of BB. */
316 ssa_mark_phi_uses (struct dom_walk_data *walk_data, basic_block bb)
318 struct mark_def_sites_global_data *gd = walk_data->global_data;
319 sbitmap kills = gd->kills;
324 for (e = bb->succ; e; e = e->succ_next)
326 if (e->dest == EXIT_BLOCK_PTR)
329 for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
331 use = PHI_ARG_DEF_FROM_EDGE (phi, e);
332 if (TREE_CODE (use) != SSA_NAME)
335 uid = SSA_NAME_VERSION (use);
337 if (TEST_BIT (gd->names_to_rename, uid)
338 && !TEST_BIT (kills, uid))
339 set_livein_block (use, bb);
344 /* Call back for walk_dominator_tree used to collect definition sites
345 for every variable in the function. For every statement S in block
348 1- Variables defined by S in DEF_OPS(S) are marked in the bitmap
349 WALK_DATA->GLOBAL_DATA->KILLS.
351 2- If S uses a variable VAR and there is no preceding kill of VAR,
352 then it is marked in marked in the LIVEIN_BLOCKS bitmap
355 This information is used to determine which variables are live
356 across block boundaries to reduce the number of PHI nodes
360 mark_def_sites (struct dom_walk_data *walk_data,
362 block_stmt_iterator bsi)
364 struct mark_def_sites_global_data *gd = walk_data->global_data;
365 sbitmap kills = gd->kills;
372 /* Mark all the blocks that have definitions for each variable in the
373 VARS_TO_RENAME bitmap. */
374 stmt = bsi_stmt (bsi);
375 get_stmt_operands (stmt);
377 /* If a variable is used before being set, then the variable is live
378 across a block boundary, so mark it live-on-entry to BB. */
380 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
382 if (prepare_use_operand_for_rename (use_p, &uid)
383 && !TEST_BIT (kills, uid))
384 set_livein_block (USE_FROM_PTR (use_p), bb);
387 /* Note that virtual definitions are irrelevant for computing KILLS
388 because a V_MAY_DEF does not constitute a killing definition of the
389 variable. However, the operand of a virtual definitions is a use
390 of the variable, so it may cause the variable to be considered
393 FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
395 if (prepare_use_operand_for_rename (use_p, &uid))
397 /* If we do not already have an SSA_NAME for our destination,
398 then set the destination to the source. */
399 if (TREE_CODE (DEF_FROM_PTR (def_p)) != SSA_NAME)
400 SET_DEF (def_p, USE_FROM_PTR (use_p));
402 set_livein_block (USE_FROM_PTR (use_p), bb);
403 set_def_block (DEF_FROM_PTR (def_p), bb, false, false);
407 /* Now process the virtual must-defs made by this statement. */
408 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF | SSA_OP_VMUSTDEF)
410 if (prepare_def_operand_for_rename (def, &uid))
412 set_def_block (def, bb, false, false);
413 SET_BIT (kills, uid);
419 /* Ditto, but works over ssa names. */
422 ssa_mark_def_sites (struct dom_walk_data *walk_data,
424 block_stmt_iterator bsi)
426 struct mark_def_sites_global_data *gd = walk_data->global_data;
427 sbitmap kills = gd->kills;
432 /* Mark all the blocks that have definitions for each variable in the
433 names_to_rename bitmap. */
434 stmt = bsi_stmt (bsi);
435 get_stmt_operands (stmt);
437 /* If a variable is used before being set, then the variable is live
438 across a block boundary, so mark it live-on-entry to BB. */
439 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES)
441 uid = SSA_NAME_VERSION (use);
443 if (TEST_BIT (gd->names_to_rename, uid)
444 && !TEST_BIT (kills, uid))
445 set_livein_block (use, bb);
448 /* Now process the definition made by this statement. Mark the
449 variables in KILLS. */
450 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
452 def_uid = SSA_NAME_VERSION (def);
454 if (TEST_BIT (gd->names_to_rename, def_uid))
456 set_def_block (def, bb, false, true);
457 SET_BIT (kills, def_uid);
462 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
463 VAR is defined by a phi node. SSA_P is true if we are called from
464 rewrite_ssa_into_ssa. */
467 set_def_block (tree var, basic_block bb, bool phi_p, bool ssa_p)
469 struct def_blocks_d *db_p;
470 enum need_phi_state state;
473 && TREE_CODE (var) == SSA_NAME)
474 var = SSA_NAME_VAR (var);
476 state = get_phi_state (var);
477 db_p = get_def_blocks_for (var);
479 /* Set the bit corresponding to the block where VAR is defined. */
480 bitmap_set_bit (db_p->def_blocks, bb->index);
482 bitmap_set_bit (db_p->phi_blocks, bb->index);
484 /* Keep track of whether or not we may need to insert phi nodes.
486 If we are in the UNKNOWN state, then this is the first definition
487 of VAR. Additionally, we have not seen any uses of VAR yet, so
488 we do not need a phi node for this variable at this time (i.e.,
489 transition to NEED_PHI_STATE_NO).
491 If we are in any other state, then we either have multiple definitions
492 of this variable occurring in different blocks or we saw a use of the
493 variable which was not dominated by the block containing the
494 definition(s). In this case we may need a PHI node, so enter
495 state NEED_PHI_STATE_MAYBE. */
496 if (state == NEED_PHI_STATE_UNKNOWN)
497 set_phi_state (var, NEED_PHI_STATE_NO);
499 set_phi_state (var, NEED_PHI_STATE_MAYBE);
503 /* Mark block BB as having VAR live at the entry to BB. */
506 set_livein_block (tree var, basic_block bb)
508 struct def_blocks_d *db_p;
509 enum need_phi_state state = get_phi_state (var);
511 db_p = get_def_blocks_for (var);
513 /* Set the bit corresponding to the block where VAR is live in. */
514 bitmap_set_bit (db_p->livein_blocks, bb->index);
516 /* Keep track of whether or not we may need to insert phi nodes.
518 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
519 by the single block containing the definition(s) of this variable. If
520 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
521 NEED_PHI_STATE_MAYBE. */
522 if (state == NEED_PHI_STATE_NO)
524 int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
526 if (def_block_index == -1
527 || ! dominated_by_p (CDI_DOMINATORS, bb,
528 BASIC_BLOCK (def_block_index)))
529 set_phi_state (var, NEED_PHI_STATE_MAYBE);
532 set_phi_state (var, NEED_PHI_STATE_MAYBE);
536 /* If the use operand pointed to by OP_P needs to be renamed, then strip away
537 any SSA_NAME wrapping the operand, set *UID_P to the underlying variable's
538 uid, and return true. Otherwise return false. If the operand was an
539 SSA_NAME, change it to the stripped name. */
542 prepare_use_operand_for_rename (use_operand_p op_p, size_t *uid_p)
544 tree use = USE_FROM_PTR (op_p);
545 tree var = (TREE_CODE (use) != SSA_NAME) ? use : SSA_NAME_VAR (use);
546 *uid_p = var_ann (var)->uid;
548 /* Ignore variables that don't need to be renamed. */
549 if (vars_to_rename && !bitmap_bit_p (vars_to_rename, *uid_p))
552 /* The variable needs to be renamed. If this is a use which already
553 has an SSA_NAME, then strip it off.
555 By not throwing away SSA_NAMEs on assignments, we avoid a lot of
556 useless churn of SSA_NAMEs without having to overly complicate the
558 if (TREE_CODE (use) == SSA_NAME)
564 /* If the def variable DEF needs to be renamed, then strip away any SSA_NAME
565 wrapping the operand, set *UID_P to the underlying variable's uid and return
566 true. Otherwise return false. */
569 prepare_def_operand_for_rename (tree def, size_t *uid_p)
571 tree var = (TREE_CODE (def) != SSA_NAME) ? def : SSA_NAME_VAR (def);
572 *uid_p = var_ann (var)->uid;
574 /* Ignore variables that don't need to be renamed. */
575 if (vars_to_rename && !bitmap_bit_p (vars_to_rename, *uid_p))
581 /* Helper for insert_phi_nodes. If VAR needs PHI nodes, insert them
582 at the dominance frontier (DFS) of blocks defining VAR.
583 WORK_STACK is the varray used to implement the worklist of basic
587 void insert_phi_nodes_1 (tree var, bitmap *dfs, varray_type *work_stack)
589 if (get_phi_state (var) != NEED_PHI_STATE_NO)
590 insert_phi_nodes_for (var, dfs, work_stack);
593 /* Insert PHI nodes at the dominance frontier of blocks with variable
594 definitions. DFS contains the dominance frontier information for
595 the flowgraph. PHI nodes will only be inserted at the dominance
596 frontier of definition blocks for variables whose NEED_PHI_STATE
597 annotation is marked as ``maybe'' or ``unknown'' (computed by
598 mark_def_sites). If NAMES_TO_RENAME is not NULL, do the same but
599 for ssa name rewriting. */
602 insert_phi_nodes (bitmap *dfs, bitmap names_to_rename)
605 varray_type work_stack;
608 timevar_push (TV_TREE_INSERT_PHI_NODES);
610 /* Array WORK_STACK is a stack of CFG blocks. Each block that contains
611 an assignment or PHI node will be pushed to this stack. */
612 VARRAY_GENERIC_PTR_NOGC_INIT (work_stack, last_basic_block, "work_stack");
614 /* Iterate over all variables in VARS_TO_RENAME. For each variable, add
615 to the work list all the blocks that have a definition for the
616 variable. PHI nodes will be added to the dominance frontier blocks of
617 each definition block. */
620 EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
623 insert_phi_nodes_1 (ssa_name (i), dfs, &work_stack);
626 else if (vars_to_rename)
627 EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i, bi)
629 insert_phi_nodes_1 (referenced_var (i), dfs, &work_stack);
632 for (i = 0; i < num_referenced_vars; i++)
633 insert_phi_nodes_1 (referenced_var (i), dfs, &work_stack);
635 VARRAY_FREE (work_stack);
637 timevar_pop (TV_TREE_INSERT_PHI_NODES);
641 /* Perform a depth-first traversal of the dominator tree looking for
642 variables to rename. BB is the block where to start searching.
643 Renaming is a five step process:
645 1- Every definition made by PHI nodes at the start of the blocks is
646 registered as the current definition for the corresponding variable.
648 2- Every statement in BB is rewritten. USE and VUSE operands are
649 rewritten with their corresponding reaching definition. DEF and
650 VDEF targets are registered as new definitions.
652 3- All the PHI nodes in successor blocks of BB are visited. The
653 argument corresponding to BB is replaced with its current reaching
656 4- Recursively rewrite every dominator child block of BB.
658 5- Restore (in reverse order) the current reaching definition for every
659 new definition introduced in this block. This is done so that when
660 we return from the recursive call, all the current reaching
661 definitions are restored to the names that were valid in the
662 dominator parent of BB. */
664 /* SSA Rewriting Step 1. Initialization, create a block local stack
665 of reaching definitions for new SSA names produced in this block
666 (BLOCK_DEFS). Register new definitions for every PHI node in the
670 rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
675 if (dump_file && (dump_flags & TDF_DETAILS))
676 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
678 /* Mark the unwind point for this block. */
679 VARRAY_PUSH_TREE (block_defs_stack, NULL_TREE);
681 /* Step 1. Register new definitions for every PHI node in the block.
682 Conceptually, all the PHI nodes are executed in parallel and each PHI
683 node introduces a new version for the associated variable. */
684 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
686 tree result = PHI_RESULT (phi);
688 register_new_def (result, &block_defs_stack);
692 /* Register DEF (an SSA_NAME) to be a new definition for the original
693 ssa name VAR and push VAR's current reaching definition
694 into the stack pointed by BLOCK_DEFS_P. */
697 ssa_register_new_def (tree var, tree def)
701 /* If this variable is set in a single basic block and all uses are
702 dominated by the set(s) in that single basic block, then there is
703 nothing to do. TODO we should not be called at all, and just
704 keep the original name. */
705 if (get_phi_state (var) == NEED_PHI_STATE_NO)
707 set_current_def (var, def);
711 currdef = get_current_def (var);
713 /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
714 later used by the dominator tree callbacks to restore the reaching
715 definitions for all the variables defined in the block after a recursive
716 visit to all its immediately dominated blocks. */
717 VARRAY_PUSH_TREE (block_defs_stack, currdef);
718 VARRAY_PUSH_TREE (block_defs_stack, var);
720 /* Set the current reaching definition for VAR to be DEF. */
721 set_current_def (var, def);
724 /* Ditto, for rewriting ssa names. */
727 ssa_rewrite_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
730 sbitmap names_to_rename = walk_data->global_data;
734 if (dump_file && (dump_flags & TDF_DETAILS))
735 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
737 /* Mark the unwind point for this block. */
738 VARRAY_PUSH_TREE (block_defs_stack, NULL_TREE);
740 for (e = bb->pred; e; e = e->pred_next)
741 if (e->flags & EDGE_ABNORMAL)
743 abnormal_phi = (e != NULL);
745 /* Step 1. Register new definitions for every PHI node in the block.
746 Conceptually, all the PHI nodes are executed in parallel and each PHI
747 node introduces a new version for the associated variable. */
748 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
750 tree result = PHI_RESULT (phi);
752 if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (result)))
754 new_name = duplicate_ssa_name (result, phi);
755 SET_PHI_RESULT (phi, new_name);
758 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
763 ssa_register_new_def (result, new_name);
767 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
768 PHI nodes. For every PHI node found, add a new argument containing the
769 current reaching definition for the variable and the edge through which
770 that definition is reaching the PHI node. */
773 rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
778 for (e = bb->succ; e; e = e->succ_next)
782 for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
786 /* If this PHI node has already been rewritten, then there is
787 nothing to do for this PHI or any following PHIs since we
788 always add new PHI nodes at the start of the PHI chain. */
789 if (PHI_REWRITTEN (phi))
792 currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
793 add_phi_arg (&phi, currdef, e);
798 /* Ditto, for ssa name rewriting. */
801 ssa_rewrite_phi_arguments (struct dom_walk_data *walk_data, basic_block bb)
804 sbitmap names_to_rename = walk_data->global_data;
807 for (e = bb->succ; e; e = e->succ_next)
811 if (e->dest == EXIT_BLOCK_PTR)
814 for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
816 op = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
817 if (TREE_CODE (USE_FROM_PTR (op)) != SSA_NAME)
820 if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (op))))
823 SET_USE (op, get_reaching_def (USE_FROM_PTR (op)));
824 if (e->flags & EDGE_ABNORMAL)
825 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (op)) = 1;
831 /* Similar to restore_vars_to_original_value, except that it restores
832 CURRDEFS to its original value. */
834 rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
835 basic_block bb ATTRIBUTE_UNUSED)
837 /* Restore CURRDEFS to its original state. */
838 while (VARRAY_ACTIVE_SIZE (block_defs_stack) > 0)
840 tree tmp = VARRAY_TOP_TREE (block_defs_stack);
843 VARRAY_POP (block_defs_stack);
845 if (tmp == NULL_TREE)
848 /* If we recorded an SSA_NAME, then make the SSA_NAME the current
849 definition of its underlying variable. If we recorded anything
850 else, it must have been an _DECL node and its current reaching
851 definition must have been NULL. */
852 if (TREE_CODE (tmp) == SSA_NAME)
855 var = SSA_NAME_VAR (saved_def);
863 set_current_def (var, saved_def);
867 /* Ditto, for rewriting ssa names. */
870 ssa_rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
871 basic_block bb ATTRIBUTE_UNUSED)
874 /* Step 5. Restore the current reaching definition for each variable
875 referenced in the block (in reverse order). */
876 while (VARRAY_ACTIVE_SIZE (block_defs_stack) > 0)
878 tree var = VARRAY_TOP_TREE (block_defs_stack);
881 VARRAY_POP (block_defs_stack);
886 saved_def = VARRAY_TOP_TREE (block_defs_stack);
887 VARRAY_POP (block_defs_stack);
889 set_current_def (var, saved_def);
893 /* Dump SSA information to FILE. */
896 dump_tree_ssa (FILE *file)
900 = lang_hooks.decl_printable_name (current_function_decl, 2);
902 fprintf (file, "SSA information for %s\n\n", funcname);
906 dump_bb (bb, file, 0);
908 print_generic_stmt (file, phi_nodes (bb), dump_flags);
909 fputs ("\n\n", file);
914 /* Dump SSA information to stderr. */
917 debug_tree_ssa (void)
919 dump_tree_ssa (stderr);
923 /* Dump SSA statistics on FILE. */
926 dump_tree_ssa_stats (FILE *file)
928 fprintf (file, "\nHash table statistics:\n");
930 fprintf (file, " def_blocks: ");
931 htab_statistics (file, def_blocks);
933 fprintf (file, "\n");
937 /* Dump SSA statistics on stderr. */
940 debug_tree_ssa_stats (void)
942 dump_tree_ssa_stats (stderr);
946 /* Dump statistics for the hash table HTAB. */
949 htab_statistics (FILE *file, htab_t htab)
951 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
952 (long) htab_size (htab),
953 (long) htab_elements (htab),
954 htab_collisions (htab));
958 /* Insert PHI nodes for variable VAR using the dominance frontier
959 information given in DFS. WORK_STACK is the varray used to
960 implement the worklist of basic blocks. */
963 insert_phi_nodes_for (tree var, bitmap *dfs, varray_type *work_stack)
965 struct def_blocks_d *def_map;
966 bitmap phi_insertion_points;
973 def_map = find_def_blocks_for (var);
977 phi_insertion_points = BITMAP_XMALLOC ();
979 EXECUTE_IF_SET_IN_BITMAP (def_map->def_blocks, 0, bb_index, bi)
981 VARRAY_PUSH_GENERIC_PTR_NOGC (*work_stack, BASIC_BLOCK (bb_index));
984 /* Pop a block off the worklist, add every block that appears in
985 the original block's dfs that we have not already processed to
986 the worklist. Iterate until the worklist is empty. Blocks
987 which are added to the worklist are potential sites for
990 The iteration step could be done during PHI insertion just as
991 easily. We do it here for historical reasons -- we used to have
992 a heuristic which used the potential PHI insertion points to
993 determine if fully pruned or semi pruned SSA form was appropriate.
995 We now always use fully pruned SSA form. */
996 while (VARRAY_ACTIVE_SIZE (*work_stack) > 0)
1001 bb = VARRAY_TOP_GENERIC_PTR_NOGC (*work_stack);
1002 bb_index = bb->index;
1004 VARRAY_POP (*work_stack);
1006 EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index],
1007 phi_insertion_points,
1010 basic_block bb = BASIC_BLOCK (dfs_index);
1012 VARRAY_PUSH_GENERIC_PTR_NOGC (*work_stack, bb);
1013 bitmap_set_bit (phi_insertion_points, dfs_index);
1017 /* Remove the blocks where we already have the phis. */
1018 bitmap_operation (phi_insertion_points, phi_insertion_points,
1019 def_map->phi_blocks, BITMAP_AND_COMPL);
1021 /* Now compute global livein for this variable. Note this modifies
1022 def_map->livein_blocks. */
1023 compute_global_livein (def_map->livein_blocks, def_map->def_blocks);
1025 /* And insert the PHI nodes. */
1026 EXECUTE_IF_AND_IN_BITMAP (phi_insertion_points, def_map->livein_blocks,
1029 bb = BASIC_BLOCK (bb_index);
1031 phi = create_phi_node (var, bb);
1033 /* If we are rewriting ssa names, add also the phi arguments. */
1034 if (TREE_CODE (var) == SSA_NAME)
1036 for (e = bb->pred; e; e = e->pred_next)
1037 add_phi_arg (&phi, var, e);
1041 BITMAP_XFREE (phi_insertion_points);
1044 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1045 the block with its immediate reaching definitions. Update the current
1046 definition of a variable when a new real or virtual definition is found. */
1049 rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1050 basic_block bb ATTRIBUTE_UNUSED,
1051 block_stmt_iterator si)
1055 use_operand_p use_p;
1056 def_operand_p def_p;
1059 stmt = bsi_stmt (si);
1060 ann = stmt_ann (stmt);
1062 if (dump_file && (dump_flags & TDF_DETAILS))
1064 fprintf (dump_file, "Renaming statement ");
1065 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1066 fprintf (dump_file, "\n");
1069 /* We have just scanned the code for operands. No statement should
1071 gcc_assert (!ann->modified);
1073 /* Step 1. Rewrite USES and VUSES in the statement. */
1074 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1075 rewrite_operand (use_p);
1077 /* Step 2. Register the statement's DEF and VDEF operands. */
1078 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1080 if (TREE_CODE (DEF_FROM_PTR (def_p)) != SSA_NAME)
1081 SET_DEF (def_p, make_ssa_name (DEF_FROM_PTR (def_p), stmt));
1083 /* FIXME: We shouldn't be registering new defs if the variable
1084 doesn't need to be renamed. */
1085 register_new_def (DEF_FROM_PTR (def_p), &block_defs_stack);
1089 /* Ditto, for rewriting ssa names. */
1092 ssa_rewrite_stmt (struct dom_walk_data *walk_data,
1093 basic_block bb ATTRIBUTE_UNUSED,
1094 block_stmt_iterator si)
1099 use_operand_p use_p;
1100 def_operand_p def_p;
1101 sbitmap names_to_rename = walk_data->global_data;
1103 stmt = bsi_stmt (si);
1104 ann = stmt_ann (stmt);
1106 if (dump_file && (dump_flags & TDF_DETAILS))
1108 fprintf (dump_file, "Renaming statement ");
1109 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1110 fprintf (dump_file, "\n");
1113 /* We have just scanned the code for operands. No statement should
1115 gcc_assert (!ann->modified);
1117 /* Step 1. Rewrite USES and VUSES in the statement. */
1118 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1120 if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (use_p))))
1121 SET_USE (use_p, get_reaching_def (USE_FROM_PTR (use_p)));
1124 /* Step 2. Register the statement's DEF and VDEF operands. */
1125 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1127 var = DEF_FROM_PTR (def_p);
1129 if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (var)))
1132 SET_DEF (def_p, duplicate_ssa_name (var, stmt));
1133 ssa_register_new_def (var, DEF_FROM_PTR (def_p));
1137 /* Replace the operand pointed by OP_P with its immediate reaching
1141 rewrite_operand (use_operand_p op_p)
1143 if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
1144 SET_USE (op_p, get_reaching_def (USE_FROM_PTR (op_p)));
1147 /* Register DEF (an SSA_NAME) to be a new definition for its underlying
1148 variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition
1149 into the stack pointed by BLOCK_DEFS_P. */
1152 register_new_def (tree def, varray_type *block_defs_p)
1154 tree var = SSA_NAME_VAR (def);
1157 /* If this variable is set in a single basic block and all uses are
1158 dominated by the set(s) in that single basic block, then there is
1159 no reason to record anything for this variable in the block local
1160 definition stacks. Doing so just wastes time and memory.
1162 This is the same test to prune the set of variables which may
1163 need PHI nodes. So we just use that information since it's already
1164 computed and available for us to use. */
1165 if (get_phi_state (var) == NEED_PHI_STATE_NO)
1167 set_current_def (var, def);
1171 currdef = get_current_def (var);
1173 /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
1174 later used by the dominator tree callbacks to restore the reaching
1175 definitions for all the variables defined in the block after a recursive
1176 visit to all its immediately dominated blocks. If there is no current
1177 reaching definition, then just record the underlying _DECL node. */
1178 VARRAY_PUSH_TREE (*block_defs_p, currdef ? currdef : var);
1180 /* Set the current reaching definition for VAR to be DEF. */
1181 set_current_def (var, def);
1184 /* Return the current definition for variable VAR. If none is found,
1185 create a new SSA name to act as the zeroth definition for VAR. If VAR
1186 is call clobbered and there exists a more recent definition of
1187 GLOBAL_VAR, return the definition for GLOBAL_VAR. This means that VAR
1188 has been clobbered by a function call since its last assignment. */
1191 get_reaching_def (tree var)
1193 tree default_d, currdef_var, avar;
1195 /* Lookup the current reaching definition for VAR. */
1196 default_d = NULL_TREE;
1197 currdef_var = get_current_def (var);
1199 /* If there is no reaching definition for VAR, create and register a
1200 default definition for it (if needed). */
1201 if (currdef_var == NULL_TREE)
1203 if (TREE_CODE (var) == SSA_NAME)
1204 avar = SSA_NAME_VAR (var);
1208 default_d = default_def (avar);
1209 if (default_d == NULL_TREE)
1211 default_d = make_ssa_name (avar, build_empty_stmt ());
1212 set_default_def (avar, default_d);
1214 set_current_def (var, default_d);
1217 /* Return the current reaching definition for VAR, or the default
1218 definition, if we had to create one. */
1219 return (currdef_var) ? currdef_var : default_d;
1223 /* Hashing and equality functions for DEF_BLOCKS. */
1226 def_blocks_hash (const void *p)
1228 return htab_hash_pointer
1229 ((const void *)((const struct def_blocks_d *)p)->var);
1233 def_blocks_eq (const void *p1, const void *p2)
1235 return ((const struct def_blocks_d *)p1)->var
1236 == ((const struct def_blocks_d *)p2)->var;
1239 /* Free memory allocated by one entry in DEF_BLOCKS. */
1242 def_blocks_free (void *p)
1244 struct def_blocks_d *entry = p;
1245 BITMAP_XFREE (entry->def_blocks);
1246 BITMAP_XFREE (entry->phi_blocks);
1247 BITMAP_XFREE (entry->livein_blocks);
1252 /* Dump the DEF_BLOCKS hash table on stderr. */
1255 debug_def_blocks (void)
1257 htab_traverse (def_blocks, debug_def_blocks_r, NULL);
1260 /* Callback for htab_traverse to dump the DEF_BLOCKS hash table. */
1263 debug_def_blocks_r (void **slot, void *data ATTRIBUTE_UNUSED)
1266 struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
1269 fprintf (stderr, "VAR: ");
1270 print_generic_expr (stderr, db_p->var, dump_flags);
1271 fprintf (stderr, ", DEF_BLOCKS: { ");
1272 EXECUTE_IF_SET_IN_BITMAP (db_p->def_blocks, 0, i, bi)
1274 fprintf (stderr, "%ld ", i);
1276 fprintf (stderr, "}");
1277 fprintf (stderr, ", LIVEIN_BLOCKS: { ");
1278 EXECUTE_IF_SET_IN_BITMAP (db_p->livein_blocks, 0, i, bi)
1280 fprintf (stderr, "%ld ", i);
1282 fprintf (stderr, "}\n");
1288 /* Return the set of blocks where variable VAR is defined and the blocks
1289 where VAR is live on entry (livein). Return NULL, if no entry is
1290 found in DEF_BLOCKS. */
1292 static inline struct def_blocks_d *
1293 find_def_blocks_for (tree var)
1295 struct def_blocks_d dm;
1297 return (struct def_blocks_d *) htab_find (def_blocks, &dm);
1301 /* Return the set of blocks where variable VAR is defined and the blocks
1302 where VAR is live on entry (livein). If no entry is found in
1303 DEF_BLOCKS, a new one is created and returned. */
1305 static inline struct def_blocks_d *
1306 get_def_blocks_for (tree var)
1308 struct def_blocks_d db, *db_p;
1312 slot = htab_find_slot (def_blocks, (void *) &db, INSERT);
1315 db_p = xmalloc (sizeof (*db_p));
1317 db_p->def_blocks = BITMAP_XMALLOC ();
1318 db_p->phi_blocks = BITMAP_XMALLOC ();
1319 db_p->livein_blocks = BITMAP_XMALLOC ();
1320 *slot = (void *) db_p;
1323 db_p = (struct def_blocks_d *) *slot;
1328 /* If a variable V in VARS_TO_RENAME is a pointer, the renaming
1329 process will cause us to lose the name memory tags that may have
1330 been associated with the various SSA_NAMEs of V. This means that
1331 the variables aliased to those name tags also need to be renamed
1334 FIXME 1- We should either have a better scheme for renaming
1335 pointers that doesn't lose name tags or re-run alias
1336 analysis to recover points-to information.
1338 2- Currently we just invalidate *all* the name tags. This
1339 should be more selective. */
1342 invalidate_name_tags (bitmap vars_to_rename)
1345 bool rename_name_tags_p;
1348 rename_name_tags_p = false;
1349 EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i, bi)
1351 if (POINTER_TYPE_P (TREE_TYPE (referenced_var (i))))
1353 rename_name_tags_p = true;
1358 if (rename_name_tags_p)
1359 for (i = 0; i < num_referenced_vars; i++)
1361 var_ann_t ann = var_ann (referenced_var (i));
1363 if (ann->mem_tag_kind == NAME_TAG)
1366 varray_type may_aliases = ann->may_aliases;
1368 bitmap_set_bit (vars_to_rename, ann->uid);
1369 if (ann->may_aliases)
1370 for (j = 0; j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
1372 tree var = VARRAY_TREE (may_aliases, j);
1373 bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1380 /* Main entry point into the SSA builder. The renaming process
1381 proceeds in five main phases:
1383 1- If VARS_TO_RENAME has any entries, any existing PHI nodes for
1384 those variables are removed from the flow graph so that they can
1387 2- Compute dominance frontier and immediate dominators, needed to
1388 insert PHI nodes and rename the function in dominator tree
1391 3- Find and mark all the blocks that define variables
1394 4- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
1396 5- Rename all the blocks (rewrite_initialize_block,
1397 rewrite_add_phi_arguments) and statements in the program
1400 Steps 3 and 5 are done using the dominator tree walker
1401 (walk_dominator_tree).
1403 ALL is true if all variables should be renamed (otherwise just those
1404 mentioned in vars_to_rename are taken into account). */
1407 rewrite_into_ssa (bool all)
1411 struct dom_walk_data walk_data;
1412 struct mark_def_sites_global_data mark_def_sites_global_data;
1413 bitmap old_vars_to_rename = vars_to_rename;
1416 timevar_push (TV_TREE_SSA_OTHER);
1419 vars_to_rename = NULL;
1422 /* Initialize the array of variables to rename. */
1423 gcc_assert (vars_to_rename);
1425 if (bitmap_first_set_bit (vars_to_rename) < 0)
1427 timevar_pop (TV_TREE_SSA_OTHER);
1431 invalidate_name_tags (vars_to_rename);
1433 /* Now remove all the existing PHI nodes (if any) for the variables
1434 that we are about to rename into SSA. */
1435 remove_all_phi_nodes_for (vars_to_rename);
1438 /* Allocate memory for the DEF_BLOCKS hash table. */
1439 def_blocks = htab_create (VARRAY_ACTIVE_SIZE (referenced_vars),
1440 def_blocks_hash, def_blocks_eq, def_blocks_free);
1442 /* Initialize dominance frontier and immediate dominator bitmaps.
1443 Also count the number of predecessors for each block. Doing so
1444 can save significant time during PHI insertion for large graphs. */
1445 dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
1451 for (e = bb->pred; e; e = e->pred_next)
1454 bb_ann (bb)->num_preds = count;
1455 dfs[bb->index] = BITMAP_XMALLOC ();
1458 for (i = 0; i < num_referenced_vars; i++)
1459 set_current_def (referenced_var (i), NULL_TREE);
1461 /* Ensure that the dominance information is OK. */
1462 calculate_dominance_info (CDI_DOMINATORS);
1464 /* Compute dominance frontiers. */
1465 compute_dominance_frontiers (dfs);
1467 /* Setup callbacks for the generic dominator tree walker to find and
1468 mark definition sites. */
1469 walk_data.walk_stmts_backward = false;
1470 walk_data.dom_direction = CDI_DOMINATORS;
1471 walk_data.initialize_block_local_data = NULL;
1472 walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block;
1473 walk_data.before_dom_children_walk_stmts = mark_def_sites;
1474 walk_data.before_dom_children_after_stmts = NULL;
1475 walk_data.after_dom_children_before_stmts = NULL;
1476 walk_data.after_dom_children_walk_stmts = NULL;
1477 walk_data.after_dom_children_after_stmts = NULL;
1479 /* Notice that this bitmap is indexed using variable UIDs, so it must be
1480 large enough to accommodate all the variables referenced in the
1481 function, not just the ones we are renaming. */
1482 mark_def_sites_global_data.kills = sbitmap_alloc (num_referenced_vars);
1483 walk_data.global_data = &mark_def_sites_global_data;
1485 /* We do not have any local data. */
1486 walk_data.block_local_data_size = 0;
1488 /* Initialize the dominator walker. */
1489 init_walk_dominator_tree (&walk_data);
1491 /* Recursively walk the dominator tree. */
1492 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1494 /* Finalize the dominator walker. */
1495 fini_walk_dominator_tree (&walk_data);
1497 /* We no longer need this bitmap, clear and free it. */
1498 sbitmap_free (mark_def_sites_global_data.kills);
1500 /* Insert PHI nodes at dominance frontiers of definition blocks. */
1501 insert_phi_nodes (dfs, NULL);
1503 /* Rewrite all the basic blocks in the program. */
1504 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
1506 /* Setup callbacks for the generic dominator tree walker. */
1507 walk_data.walk_stmts_backward = false;
1508 walk_data.dom_direction = CDI_DOMINATORS;
1509 walk_data.initialize_block_local_data = NULL;
1510 walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
1511 walk_data.before_dom_children_walk_stmts = rewrite_stmt;
1512 walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
1513 walk_data.after_dom_children_before_stmts = NULL;
1514 walk_data.after_dom_children_walk_stmts = NULL;
1515 walk_data.after_dom_children_after_stmts = rewrite_finalize_block;
1516 walk_data.global_data = NULL;
1517 walk_data.block_local_data_size = 0;
1519 VARRAY_TREE_INIT (block_defs_stack, 10, "Block DEFS Stack");
1521 /* Initialize the dominator walker. */
1522 init_walk_dominator_tree (&walk_data);
1524 /* Recursively walk the dominator tree rewriting each statement in
1525 each basic block. */
1526 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1528 /* Finalize the dominator walker. */
1529 fini_walk_dominator_tree (&walk_data);
1531 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
1533 /* Debugging dumps. */
1534 if (dump_file && (dump_flags & TDF_STATS))
1536 dump_dfa_stats (dump_file);
1537 dump_tree_ssa_stats (dump_file);
1540 /* Free allocated memory. */
1542 BITMAP_XFREE (dfs[bb->index]);
1545 htab_delete (def_blocks);
1547 vars_to_rename = old_vars_to_rename;
1548 timevar_pop (TV_TREE_SSA_OTHER);
1551 /* The marked ssa names may have more than one definition;
1552 add phi nodes and rewrite them to fix this. */
1555 rewrite_ssa_into_ssa (void)
1559 struct dom_walk_data walk_data;
1560 struct mark_def_sites_global_data mark_def_sites_global_data;
1562 sbitmap snames_to_rename;
1567 if (!any_marked_for_rewrite_p ())
1569 to_rename = marked_ssa_names ();
1571 timevar_push (TV_TREE_SSA_OTHER);
1573 /* Allocate memory for the DEF_BLOCKS hash table. */
1574 def_blocks = htab_create (num_ssa_names,
1575 def_blocks_hash, def_blocks_eq, def_blocks_free);
1577 /* Initialize dominance frontier and immediate dominator bitmaps.
1578 Also count the number of predecessors for each block. Doing so
1579 can save significant time during PHI insertion for large graphs. */
1580 dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
1586 for (e = bb->pred; e; e = e->pred_next)
1589 bb_ann (bb)->num_preds = count;
1590 dfs[bb->index] = BITMAP_XMALLOC ();
1593 /* Ensure that the dominance information is OK. */
1594 calculate_dominance_info (CDI_DOMINATORS);
1596 /* Compute dominance frontiers. */
1597 compute_dominance_frontiers (dfs);
1599 /* Setup callbacks for the generic dominator tree walker to find and
1600 mark definition sites. */
1601 walk_data.walk_stmts_backward = false;
1602 walk_data.dom_direction = CDI_DOMINATORS;
1603 walk_data.initialize_block_local_data = NULL;
1604 walk_data.before_dom_children_before_stmts
1605 = ssa_mark_def_sites_initialize_block;
1606 walk_data.before_dom_children_walk_stmts = ssa_mark_def_sites;
1607 walk_data.before_dom_children_after_stmts = ssa_mark_phi_uses;
1608 walk_data.after_dom_children_before_stmts = NULL;
1609 walk_data.after_dom_children_walk_stmts = NULL;
1610 walk_data.after_dom_children_after_stmts = NULL;
1612 snames_to_rename = sbitmap_alloc (num_ssa_names);
1613 sbitmap_zero (snames_to_rename);
1614 EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, bi)
1616 SET_BIT (snames_to_rename, i);
1619 mark_def_sites_global_data.kills = sbitmap_alloc (num_ssa_names);
1620 mark_def_sites_global_data.names_to_rename = snames_to_rename;
1621 walk_data.global_data = &mark_def_sites_global_data;
1623 VARRAY_TREE_INIT (block_defs_stack, 10, "Block DEFS Stack");
1625 /* We do not have any local data. */
1626 walk_data.block_local_data_size = 0;
1628 /* Initialize the dominator walker. */
1629 init_walk_dominator_tree (&walk_data);
1631 /* Recursively walk the dominator tree. */
1632 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1634 /* Finalize the dominator walker. */
1635 fini_walk_dominator_tree (&walk_data);
1637 /* We no longer need this bitmap, clear and free it. */
1638 sbitmap_free (mark_def_sites_global_data.kills);
1640 for (i = 1; i < num_ssa_names; i++)
1642 set_current_def (ssa_name (i), NULL_TREE);
1644 /* Insert PHI nodes at dominance frontiers of definition blocks. */
1645 insert_phi_nodes (dfs, to_rename);
1647 /* Rewrite all the basic blocks in the program. */
1648 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
1650 /* Setup callbacks for the generic dominator tree walker. */
1651 walk_data.walk_stmts_backward = false;
1652 walk_data.dom_direction = CDI_DOMINATORS;
1653 walk_data.initialize_block_local_data = NULL;
1654 walk_data.before_dom_children_before_stmts = ssa_rewrite_initialize_block;
1655 walk_data.before_dom_children_walk_stmts = ssa_rewrite_stmt;
1656 walk_data.before_dom_children_after_stmts = ssa_rewrite_phi_arguments;
1657 walk_data.after_dom_children_before_stmts = NULL;
1658 walk_data.after_dom_children_walk_stmts = NULL;
1659 walk_data.after_dom_children_after_stmts = ssa_rewrite_finalize_block;
1660 walk_data.global_data = snames_to_rename;
1661 walk_data.block_local_data_size = 0;
1663 /* Initialize the dominator walker. */
1664 init_walk_dominator_tree (&walk_data);
1666 /* Recursively walk the dominator tree rewriting each statement in
1667 each basic block. */
1668 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1670 /* Finalize the dominator walker. */
1671 fini_walk_dominator_tree (&walk_data);
1673 unmark_all_for_rewrite ();
1675 EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, bi)
1677 release_ssa_name (ssa_name (i));
1680 sbitmap_free (snames_to_rename);
1682 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
1684 /* Debugging dumps. */
1685 if (dump_file && (dump_flags & TDF_STATS))
1687 dump_dfa_stats (dump_file);
1688 dump_tree_ssa_stats (dump_file);
1691 /* Free allocated memory. */
1693 BITMAP_XFREE (dfs[bb->index]);
1696 htab_delete (def_blocks);
1698 for (i = 1; i < num_ssa_names; i++)
1700 name = ssa_name (i);
1701 if (!name || !SSA_NAME_AUX (name))
1704 free (SSA_NAME_AUX (name));
1705 SSA_NAME_AUX (name) = NULL;
1708 BITMAP_XFREE (to_rename);
1709 timevar_pop (TV_TREE_SSA_OTHER);
1712 /* Rewrites all variables into ssa. */
1715 rewrite_all_into_ssa (void)
1717 rewrite_into_ssa (true);
1720 struct tree_opt_pass pass_build_ssa =
1724 rewrite_all_into_ssa, /* execute */
1727 0, /* static_pass_number */
1729 PROP_cfg | PROP_referenced_vars, /* properties_required */
1730 PROP_ssa, /* properties_provided */
1731 0, /* properties_destroyed */
1732 0, /* todo_flags_start */
1733 TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */