1 /* Rewrite a program in Normal form into SSA.
2 Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
30 #include "langhooks.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
37 #include "diagnostic.h"
39 #include "tree-flow.h"
40 #include "tree-gimple.h"
41 #include "tree-inline.h"
44 #include "tree-alias-common.h"
46 #include "tree-dump.h"
47 #include "tree-pass.h"
52 /* This file builds the SSA form for a function as described in:
53 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
54 Computing Static Single Assignment Form and the Control Dependence
55 Graph. ACM Transactions on Programming Languages and Systems,
56 13(4):451-490, October 1991. */
59 /* Structure to map a variable VAR to the set of blocks that contain
60 definitions for VAR. */
66 /* Blocks that contain definitions of VAR. Bit I will be set if the
67 Ith block contains a definition of VAR. */
70 /* Blocks that contain a phi node for VAR. */
73 /* Blocks where VAR is live-on-entry. Similar semantics as
78 /* Each entry in DEF_BLOCKS contains an element of type STRUCT
79 DEF_BLOCKS_D, mapping a variable VAR to a bitmap describing all the
80 basic blocks where VAR is defined (assigned a new value). It also
81 contains a bitmap of all the blocks where VAR is live-on-entry
82 (i.e., there is a use of VAR in block B without a preceding
83 definition in B). The live-on-entry information is used when
84 computing PHI pruning heuristics. */
85 static htab_t def_blocks;
87 /* Global data to attach to the main dominator walk structure. */
88 struct mark_def_sites_global_data
90 /* This sbitmap contains the variables which are set before they
91 are used in a basic block. We keep it as a global variable
92 solely to avoid the overhead of allocating and deallocating
96 /* Bitmap of names to rename. */
97 sbitmap names_to_rename;
100 struct rewrite_block_data
102 varray_type block_defs;
105 /* Information stored for ssa names. */
109 /* This field indicates whether or not the variable may need PHI nodes.
110 See the enum's definition for more detailed information about the
112 ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
114 /* The actual definition of the ssa name. */
118 /* Local functions. */
119 static void rewrite_finalize_block (struct dom_walk_data *, basic_block);
120 static void rewrite_initialize_block_local_data (struct dom_walk_data *,
122 static void rewrite_initialize_block (struct dom_walk_data *, basic_block);
123 static void rewrite_add_phi_arguments (struct dom_walk_data *, basic_block);
124 static void mark_def_sites (struct dom_walk_data *walk_data,
125 basic_block bb, block_stmt_iterator);
126 static void mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
128 static void set_def_block (tree, basic_block, bool, bool);
129 static void set_livein_block (tree, basic_block);
130 static bool prepare_use_operand_for_rename (use_operand_p, size_t *uid_p);
131 static bool prepare_def_operand_for_rename (tree def, size_t *uid_p);
132 static void insert_phi_nodes (bitmap *, bitmap);
133 static void rewrite_stmt (struct dom_walk_data *, basic_block,
134 block_stmt_iterator);
135 static inline void rewrite_operand (use_operand_p);
136 static void insert_phi_nodes_for (tree, bitmap *, varray_type *);
137 static tree get_reaching_def (tree);
138 static hashval_t def_blocks_hash (const void *);
139 static int def_blocks_eq (const void *, const void *);
140 static void def_blocks_free (void *);
141 static int debug_def_blocks_r (void **, void *);
142 static inline struct def_blocks_d *get_def_blocks_for (tree);
143 static inline struct def_blocks_d *find_def_blocks_for (tree);
144 static void htab_statistics (FILE *, htab_t);
146 /* Get the information associated with NAME. */
148 static inline struct ssa_name_info *
149 get_ssa_name_ann (tree name)
151 if (!SSA_NAME_AUX (name))
152 SSA_NAME_AUX (name) = xcalloc (1, sizeof (struct ssa_name_info));
154 return SSA_NAME_AUX (name);
157 /* Gets phi_state field for VAR. */
159 static inline enum need_phi_state
160 get_phi_state (tree var)
162 if (TREE_CODE (var) == SSA_NAME)
163 return get_ssa_name_ann (var)->need_phi_state;
165 return var_ann (var)->need_phi_state;
168 /* Sets phi_state field for VAR to STATE. */
171 set_phi_state (tree var, enum need_phi_state state)
173 if (TREE_CODE (var) == SSA_NAME)
174 get_ssa_name_ann (var)->need_phi_state = state;
176 var_ann (var)->need_phi_state = state;
179 /* Return the current definition for VAR. */
182 get_current_def (tree var)
184 if (TREE_CODE (var) == SSA_NAME)
185 return get_ssa_name_ann (var)->current_def;
187 return var_ann (var)->current_def;
190 /* Sets current definition of VAR to DEF. */
193 set_current_def (tree var, tree def)
195 if (TREE_CODE (var) == SSA_NAME)
196 get_ssa_name_ann (var)->current_def = def;
198 var_ann (var)->current_def = def;
201 /* Compute global livein information given the set of blockx where
202 an object is locally live at the start of the block (LIVEIN)
203 and the set of blocks where the object is defined (DEF_BLOCKS).
205 Note: This routine augments the existing local livein information
206 to include global livein (i.e., it modifies the underlying bitmap
210 compute_global_livein (bitmap livein, bitmap def_blocks)
212 basic_block bb, *worklist, *tos;
216 = (basic_block *) xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
218 EXECUTE_IF_SET_IN_BITMAP (livein, 0, i,
220 *tos++ = BASIC_BLOCK (i);
223 /* Iterate until the worklist is empty. */
224 while (tos != worklist)
228 /* Pull a block off the worklist. */
231 /* For each predecessor block. */
232 for (e = bb->pred; e; e = e->pred_next)
234 basic_block pred = e->src;
235 int pred_index = pred->index;
237 /* None of this is necessary for the entry block. */
238 if (pred != ENTRY_BLOCK_PTR
239 && ! bitmap_bit_p (livein, pred_index)
240 && ! bitmap_bit_p (def_blocks, pred_index))
243 bitmap_set_bit (livein, pred_index);
252 /* Block initialization routine for mark_def_sites. Clear the
253 KILLS bitmap at the start of each block. */
256 mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
257 basic_block bb ATTRIBUTE_UNUSED)
259 struct mark_def_sites_global_data *gd = walk_data->global_data;
260 sbitmap kills = gd->kills;
262 sbitmap_zero (kills);
265 /* Block initialization routine for mark_def_sites. Clear the
266 KILLS bitmap at the start of each block. */
269 ssa_mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
272 struct mark_def_sites_global_data *gd = walk_data->global_data;
273 sbitmap kills = gd->kills;
277 sbitmap_zero (kills);
279 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
281 def = PHI_RESULT (phi);
282 def_uid = SSA_NAME_VERSION (def);
284 if (!TEST_BIT (gd->names_to_rename, def_uid))
287 set_def_block (def, bb, true, true);
288 SET_BIT (kills, def_uid);
292 /* Marks ssa names used as arguments of phis at the end of BB. */
295 ssa_mark_phi_uses (struct dom_walk_data *walk_data, basic_block bb)
297 struct mark_def_sites_global_data *gd = walk_data->global_data;
298 sbitmap kills = gd->kills;
303 for (e = bb->succ; e; e = e->succ_next)
305 if (e->dest == EXIT_BLOCK_PTR)
308 for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
310 use = PHI_ARG_DEF_FROM_EDGE (phi, e);
311 if (TREE_CODE (use) != SSA_NAME)
314 uid = SSA_NAME_VERSION (use);
316 if (TEST_BIT (gd->names_to_rename, uid)
317 && !TEST_BIT (kills, uid))
318 set_livein_block (use, bb);
323 /* Call back for walk_dominator_tree used to collect definition sites
324 for every variable in the function. For every statement S in block
327 1- Variables defined by S in DEF_OPS(S) are marked in the bitmap
328 WALK_DATA->GLOBAL_DATA->KILLS.
330 2- If S uses a variable VAR and there is no preceding kill of VAR,
331 then it is marked in marked in the LIVEIN_BLOCKS bitmap
334 This information is used to determine which variables are live
335 across block boundaries to reduce the number of PHI nodes
339 mark_def_sites (struct dom_walk_data *walk_data,
341 block_stmt_iterator bsi)
343 struct mark_def_sites_global_data *gd = walk_data->global_data;
344 sbitmap kills = gd->kills;
351 /* Mark all the blocks that have definitions for each variable in the
352 VARS_TO_RENAME bitmap. */
353 stmt = bsi_stmt (bsi);
354 get_stmt_operands (stmt);
356 /* If a variable is used before being set, then the variable is live
357 across a block boundary, so mark it live-on-entry to BB. */
359 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
361 if (prepare_use_operand_for_rename (use_p, &uid)
362 && !TEST_BIT (kills, uid))
363 set_livein_block (USE_FROM_PTR (use_p), bb);
366 /* Note that virtual definitions are irrelevant for computing KILLS
367 because a V_MAY_DEF does not constitute a killing definition of the
368 variable. However, the operand of a virtual definitions is a use
369 of the variable, so it may cause the variable to be considered
372 FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
374 if (prepare_use_operand_for_rename (use_p, &uid))
376 /* If we do not already have an SSA_NAME for our destination,
377 then set the destination to the source. */
378 if (TREE_CODE (DEF_FROM_PTR (def_p)) != SSA_NAME)
379 SET_DEF (def_p, USE_FROM_PTR (use_p));
381 set_livein_block (USE_FROM_PTR (use_p), bb);
382 set_def_block (DEF_FROM_PTR (def_p), bb, false, false);
386 /* Now process the virtual must-defs made by this statement. */
387 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF | SSA_OP_VMUSTDEF)
389 if (prepare_def_operand_for_rename (def, &uid))
391 set_def_block (def, bb, false, false);
392 SET_BIT (kills, uid);
398 /* Ditto, but works over ssa names. */
401 ssa_mark_def_sites (struct dom_walk_data *walk_data,
403 block_stmt_iterator bsi)
405 struct mark_def_sites_global_data *gd = walk_data->global_data;
406 sbitmap kills = gd->kills;
411 /* Mark all the blocks that have definitions for each variable in the
412 names_to_rename bitmap. */
413 stmt = bsi_stmt (bsi);
414 get_stmt_operands (stmt);
416 /* If a variable is used before being set, then the variable is live
417 across a block boundary, so mark it live-on-entry to BB. */
418 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES)
420 uid = SSA_NAME_VERSION (use);
422 if (TEST_BIT (gd->names_to_rename, uid)
423 && !TEST_BIT (kills, uid))
424 set_livein_block (use, bb);
427 /* Now process the definition made by this statement. Mark the
428 variables in KILLS. */
429 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
431 def_uid = SSA_NAME_VERSION (def);
433 if (TEST_BIT (gd->names_to_rename, def_uid))
435 set_def_block (def, bb, false, true);
436 SET_BIT (kills, def_uid);
441 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
442 VAR is defined by a phi node. SSA_P is true if we are called from
443 rewrite_ssa_into_ssa. */
446 set_def_block (tree var, basic_block bb, bool phi_p, bool ssa_p)
448 struct def_blocks_d *db_p;
449 enum need_phi_state state;
452 && TREE_CODE (var) == SSA_NAME)
453 var = SSA_NAME_VAR (var);
455 state = get_phi_state (var);
456 db_p = get_def_blocks_for (var);
458 /* Set the bit corresponding to the block where VAR is defined. */
459 bitmap_set_bit (db_p->def_blocks, bb->index);
461 bitmap_set_bit (db_p->phi_blocks, bb->index);
463 /* Keep track of whether or not we may need to insert phi nodes.
465 If we are in the UNKNOWN state, then this is the first definition
466 of VAR. Additionally, we have not seen any uses of VAR yet, so
467 we do not need a phi node for this variable at this time (i.e.,
468 transition to NEED_PHI_STATE_NO).
470 If we are in any other state, then we either have multiple definitions
471 of this variable occurring in different blocks or we saw a use of the
472 variable which was not dominated by the block containing the
473 definition(s). In this case we may need a PHI node, so enter
474 state NEED_PHI_STATE_MAYBE. */
475 if (state == NEED_PHI_STATE_UNKNOWN)
476 set_phi_state (var, NEED_PHI_STATE_NO);
478 set_phi_state (var, NEED_PHI_STATE_MAYBE);
482 /* Mark block BB as having VAR live at the entry to BB. */
485 set_livein_block (tree var, basic_block bb)
487 struct def_blocks_d *db_p;
488 enum need_phi_state state = get_phi_state (var);
490 db_p = get_def_blocks_for (var);
492 /* Set the bit corresponding to the block where VAR is live in. */
493 bitmap_set_bit (db_p->livein_blocks, bb->index);
495 /* Keep track of whether or not we may need to insert phi nodes.
497 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
498 by the single block containing the definition(s) of this variable. If
499 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
500 NEED_PHI_STATE_MAYBE. */
501 if (state == NEED_PHI_STATE_NO)
503 int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
505 if (def_block_index == -1
506 || ! dominated_by_p (CDI_DOMINATORS, bb,
507 BASIC_BLOCK (def_block_index)))
508 set_phi_state (var, NEED_PHI_STATE_MAYBE);
511 set_phi_state (var, NEED_PHI_STATE_MAYBE);
515 /* If the use operand pointed to by OP_P needs to be renamed, then strip away
516 any SSA_NAME wrapping the operand, set *UID_P to the underlying variable's
517 uid, and return true. Otherwise return false. If the operand was an
518 SSA_NAME, change it to the stripped name. */
521 prepare_use_operand_for_rename (use_operand_p op_p, size_t *uid_p)
523 tree use = USE_FROM_PTR (op_p);
524 tree var = (TREE_CODE (use) != SSA_NAME) ? use : SSA_NAME_VAR (use);
525 *uid_p = var_ann (var)->uid;
527 /* Ignore variables that don't need to be renamed. */
528 if (vars_to_rename && !bitmap_bit_p (vars_to_rename, *uid_p))
531 /* The variable needs to be renamed. If this is a use which already
532 has an SSA_NAME, then strip it off.
534 By not throwing away SSA_NAMEs on assignments, we avoid a lot of
535 useless churn of SSA_NAMEs without having to overly complicate the
537 if (TREE_CODE (use) == SSA_NAME)
543 /* If the def variable DEF needs to be renamed, then strip away any SSA_NAME
544 wrapping the operand, set *UID_P to the underlying variable's uid and return
545 true. Otherwise return false. */
548 prepare_def_operand_for_rename (tree def, size_t *uid_p)
550 tree var = (TREE_CODE (def) != SSA_NAME) ? def : SSA_NAME_VAR (def);
551 *uid_p = var_ann (var)->uid;
553 /* Ignore variables that don't need to be renamed. */
554 if (vars_to_rename && !bitmap_bit_p (vars_to_rename, *uid_p))
560 /* Helper for insert_phi_nodes. If VAR needs PHI nodes, insert them
561 at the dominance frontier (DFS) of blocks defining VAR.
562 WORK_STACK is the varray used to implement the worklist of basic
566 void insert_phi_nodes_1 (tree var, bitmap *dfs, varray_type *work_stack)
568 if (get_phi_state (var) != NEED_PHI_STATE_NO)
569 insert_phi_nodes_for (var, dfs, work_stack);
572 /* Insert PHI nodes at the dominance frontier of blocks with variable
573 definitions. DFS contains the dominance frontier information for
574 the flowgraph. PHI nodes will only be inserted at the dominance
575 frontier of definition blocks for variables whose NEED_PHI_STATE
576 annotation is marked as ``maybe'' or ``unknown'' (computed by
577 mark_def_sites). If NAMES_TO_RENAME is not NULL, do the same but
578 for ssa name rewriting. */
581 insert_phi_nodes (bitmap *dfs, bitmap names_to_rename)
584 varray_type work_stack;
586 timevar_push (TV_TREE_INSERT_PHI_NODES);
588 /* Array WORK_STACK is a stack of CFG blocks. Each block that contains
589 an assignment or PHI node will be pushed to this stack. */
590 VARRAY_GENERIC_PTR_NOGC_INIT (work_stack, last_basic_block, "work_stack");
592 /* Iterate over all variables in VARS_TO_RENAME. For each variable, add
593 to the work list all the blocks that have a definition for the
594 variable. PHI nodes will be added to the dominance frontier blocks of
595 each definition block. */
598 EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i,
601 insert_phi_nodes_1 (ssa_name (i), dfs, &work_stack);
604 else if (vars_to_rename)
605 EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i,
606 insert_phi_nodes_1 (referenced_var (i), dfs, &work_stack));
608 for (i = 0; i < num_referenced_vars; i++)
609 insert_phi_nodes_1 (referenced_var (i), dfs, &work_stack);
611 VARRAY_FREE (work_stack);
613 timevar_pop (TV_TREE_INSERT_PHI_NODES);
617 /* Perform a depth-first traversal of the dominator tree looking for
618 variables to rename. BB is the block where to start searching.
619 Renaming is a five step process:
621 1- Every definition made by PHI nodes at the start of the blocks is
622 registered as the current definition for the corresponding variable.
624 2- Every statement in BB is rewritten. USE and VUSE operands are
625 rewritten with their corresponding reaching definition. DEF and
626 VDEF targets are registered as new definitions.
628 3- All the PHI nodes in successor blocks of BB are visited. The
629 argument corresponding to BB is replaced with its current reaching
632 4- Recursively rewrite every dominator child block of BB.
634 5- Restore (in reverse order) the current reaching definition for every
635 new definition introduced in this block. This is done so that when
636 we return from the recursive call, all the current reaching
637 definitions are restored to the names that were valid in the
638 dominator parent of BB. */
640 /* Initialize the local stacks.
642 BLOCK_DEFS is used to save all the existing reaching definitions for
643 the new SSA names introduced in this block. Before registering a
644 new definition for a variable, the existing reaching definition is
645 pushed into this stack so that we can restore it in Step 5. */
648 rewrite_initialize_block_local_data (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
649 basic_block bb ATTRIBUTE_UNUSED,
650 bool recycled ATTRIBUTE_UNUSED)
652 #ifdef ENABLE_CHECKING
653 struct rewrite_block_data *bd
654 = (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
656 /* We get cleared memory from the allocator, so if the memory is
657 not cleared, then we are re-using a previously allocated entry. In
658 that case, we can also re-use the underlying virtual arrays. Just
659 make sure we clear them before using them! */
660 if (recycled && bd->block_defs && VARRAY_ACTIVE_SIZE (bd->block_defs) > 0)
666 /* SSA Rewriting Step 1. Initialization, create a block local stack
667 of reaching definitions for new SSA names produced in this block
668 (BLOCK_DEFS). Register new definitions for every PHI node in the
672 rewrite_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
675 struct rewrite_block_data *bd
676 = (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
678 if (dump_file && (dump_flags & TDF_DETAILS))
679 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
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, &bd->block_defs);
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, varray_type *block_defs_p)
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 VARRAY_TREE_INIT (*block_defs_p, 20, "block_defs");
715 /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
716 later used by the dominator tree callbacks to restore the reaching
717 definitions for all the variables defined in the block after a recursive
718 visit to all its immediately dominated blocks. */
719 VARRAY_PUSH_TREE (*block_defs_p, var);
720 VARRAY_PUSH_TREE (*block_defs_p, currdef);
722 /* Set the current reaching definition for VAR to be DEF. */
723 set_current_def (var, def);
726 /* Ditto, for rewriting ssa names. */
729 ssa_rewrite_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
732 struct rewrite_block_data *bd
733 = (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
734 sbitmap names_to_rename = walk_data->global_data;
738 if (dump_file && (dump_flags & TDF_DETAILS))
739 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
741 for (e = bb->pred; e; e = e->pred_next)
742 if (e->flags & EDGE_ABNORMAL)
744 abnormal_phi = (e != NULL);
746 /* Step 1. Register new definitions for every PHI node in the block.
747 Conceptually, all the PHI nodes are executed in parallel and each PHI
748 node introduces a new version for the associated variable. */
749 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
751 tree result = PHI_RESULT (phi);
753 if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (result)))
755 new_name = duplicate_ssa_name (result, phi);
756 SET_PHI_RESULT (phi, new_name);
759 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
764 ssa_register_new_def (result, new_name, &bd->block_defs);
768 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
769 PHI nodes. For every PHI node found, add a new argument containing the
770 current reaching definition for the variable and the edge through which
771 that definition is reaching the PHI node. */
774 rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
779 for (e = bb->succ; e; e = e->succ_next)
783 for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
787 /* If this PHI node has already been rewritten, then there is
788 nothing to do for this PHI or any following PHIs since we
789 always add new PHI nodes at the start of the PHI chain. */
790 if (PHI_REWRITTEN (phi))
793 currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
794 add_phi_arg (&phi, currdef, e);
799 /* Ditto, for ssa name rewriting. */
802 ssa_rewrite_phi_arguments (struct dom_walk_data *walk_data, basic_block bb)
805 sbitmap names_to_rename = walk_data->global_data;
808 for (e = bb->succ; e; e = e->succ_next)
812 if (e->dest == EXIT_BLOCK_PTR)
815 for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
817 op = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
818 if (TREE_CODE (USE_FROM_PTR (op)) != SSA_NAME)
821 if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (op))))
824 SET_USE (op, get_reaching_def (USE_FROM_PTR (op)));
825 if (e->flags & EDGE_ABNORMAL)
826 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (op)) = 1;
831 /* SSA Rewriting Step 5. Restore the current reaching definition for each
832 variable referenced in the block (in reverse order). */
835 rewrite_finalize_block (struct dom_walk_data *walk_data,
836 basic_block bb ATTRIBUTE_UNUSED)
838 struct rewrite_block_data *bd
839 = (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
841 /* Step 5. Restore the current reaching definition for each variable
842 referenced in the block (in reverse order). */
843 while (bd->block_defs && VARRAY_ACTIVE_SIZE (bd->block_defs) > 0)
845 tree tmp = VARRAY_TOP_TREE (bd->block_defs);
848 VARRAY_POP (bd->block_defs);
849 if (TREE_CODE (tmp) == SSA_NAME)
852 var = SSA_NAME_VAR (saved_def);
860 set_current_def (var, saved_def);
864 /* Ditto, for rewriting ssa names. */
867 ssa_rewrite_finalize_block (struct dom_walk_data *walk_data,
868 basic_block bb ATTRIBUTE_UNUSED)
870 struct rewrite_block_data *bd
871 = (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
873 /* Step 5. Restore the current reaching definition for each variable
874 referenced in the block (in reverse order). */
875 while (bd->block_defs && VARRAY_ACTIVE_SIZE (bd->block_defs) > 0)
878 tree saved_def = VARRAY_TOP_TREE (bd->block_defs);
879 VARRAY_POP (bd->block_defs);
881 var = VARRAY_TOP_TREE (bd->block_defs);
882 VARRAY_POP (bd->block_defs);
884 set_current_def (var, saved_def);
888 /* Dump SSA information to FILE. */
891 dump_tree_ssa (FILE *file)
895 = lang_hooks.decl_printable_name (current_function_decl, 2);
897 fprintf (file, "SSA information for %s\n\n", funcname);
901 dump_bb (bb, file, 0);
903 print_generic_stmt (file, phi_nodes (bb), dump_flags);
904 fputs ("\n\n", file);
909 /* Dump SSA information to stderr. */
912 debug_tree_ssa (void)
914 dump_tree_ssa (stderr);
918 /* Dump SSA statistics on FILE. */
921 dump_tree_ssa_stats (FILE *file)
923 fprintf (file, "\nHash table statistics:\n");
925 fprintf (file, " def_blocks: ");
926 htab_statistics (file, def_blocks);
928 fprintf (file, "\n");
932 /* Dump SSA statistics on stderr. */
935 debug_tree_ssa_stats (void)
937 dump_tree_ssa_stats (stderr);
941 /* Dump statistics for the hash table HTAB. */
944 htab_statistics (FILE *file, htab_t htab)
946 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
947 (long) htab_size (htab),
948 (long) htab_elements (htab),
949 htab_collisions (htab));
953 /* Insert PHI nodes for variable VAR using the dominance frontier
954 information given in DFS. WORK_STACK is the varray used to
955 implement the worklist of basic blocks. */
958 insert_phi_nodes_for (tree var, bitmap *dfs, varray_type *work_stack)
960 struct def_blocks_d *def_map;
961 bitmap phi_insertion_points;
967 def_map = find_def_blocks_for (var);
971 phi_insertion_points = BITMAP_XMALLOC ();
973 EXECUTE_IF_SET_IN_BITMAP (def_map->def_blocks, 0, bb_index,
975 VARRAY_PUSH_GENERIC_PTR_NOGC (*work_stack, BASIC_BLOCK (bb_index));
978 /* Pop a block off the worklist, add every block that appears in
979 the original block's dfs that we have not already processed to
980 the worklist. Iterate until the worklist is empty. Blocks
981 which are added to the worklist are potential sites for
984 The iteration step could be done during PHI insertion just as
985 easily. We do it here for historical reasons -- we used to have
986 a heuristic which used the potential PHI insertion points to
987 determine if fully pruned or semi pruned SSA form was appropriate.
989 We now always use fully pruned SSA form. */
990 while (VARRAY_ACTIVE_SIZE (*work_stack) > 0)
994 bb = VARRAY_TOP_GENERIC_PTR_NOGC (*work_stack);
995 bb_index = bb->index;
997 VARRAY_POP (*work_stack);
999 EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index],
1000 phi_insertion_points,
1003 basic_block bb = BASIC_BLOCK (dfs_index);
1005 VARRAY_PUSH_GENERIC_PTR_NOGC (*work_stack, bb);
1006 bitmap_set_bit (phi_insertion_points, dfs_index);
1010 /* Remove the blocks where we already have the phis. */
1011 bitmap_operation (phi_insertion_points, phi_insertion_points,
1012 def_map->phi_blocks, BITMAP_AND_COMPL);
1014 /* Now compute global livein for this variable. Note this modifies
1015 def_map->livein_blocks. */
1016 compute_global_livein (def_map->livein_blocks, def_map->def_blocks);
1018 /* And insert the PHI nodes. */
1019 EXECUTE_IF_AND_IN_BITMAP (phi_insertion_points, def_map->livein_blocks,
1023 bb = BASIC_BLOCK (bb_index);
1025 phi = create_phi_node (var, bb);
1027 /* If we are rewriting ssa names, add also the phi arguments. */
1028 if (TREE_CODE (var) == SSA_NAME)
1030 for (e = bb->pred; e; e = e->pred_next)
1031 add_phi_arg (&phi, var, e);
1036 BITMAP_XFREE (phi_insertion_points);
1039 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1040 the block with its immediate reaching definitions. Update the current
1041 definition of a variable when a new real or virtual definition is found. */
1044 rewrite_stmt (struct dom_walk_data *walk_data,
1045 basic_block bb ATTRIBUTE_UNUSED,
1046 block_stmt_iterator si)
1050 use_operand_p use_p;
1051 def_operand_p def_p;
1053 struct rewrite_block_data *bd;
1055 bd = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
1057 stmt = bsi_stmt (si);
1058 ann = stmt_ann (stmt);
1060 if (dump_file && (dump_flags & TDF_DETAILS))
1062 fprintf (dump_file, "Renaming statement ");
1063 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1064 fprintf (dump_file, "\n");
1067 #if defined ENABLE_CHECKING
1068 /* We have just scanned the code for operands. No statement should
1074 /* Step 1. Rewrite USES and VUSES in the statement. */
1075 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1076 rewrite_operand (use_p);
1078 /* Step 2. Register the statement's DEF and VDEF operands. */
1079 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1081 if (TREE_CODE (DEF_FROM_PTR (def_p)) != SSA_NAME)
1082 SET_DEF (def_p, make_ssa_name (DEF_FROM_PTR (def_p), stmt));
1084 /* FIXME: We shouldn't be registering new defs if the variable
1085 doesn't need to be renamed. */
1086 register_new_def (DEF_FROM_PTR (def_p), &bd->block_defs);
1090 /* Ditto, for rewriting ssa names. */
1093 ssa_rewrite_stmt (struct dom_walk_data *walk_data,
1094 basic_block bb ATTRIBUTE_UNUSED,
1095 block_stmt_iterator si)
1100 use_operand_p use_p;
1101 def_operand_p def_p;
1102 struct rewrite_block_data *bd;
1103 sbitmap names_to_rename = walk_data->global_data;
1105 bd = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
1107 stmt = bsi_stmt (si);
1108 ann = stmt_ann (stmt);
1110 if (dump_file && (dump_flags & TDF_DETAILS))
1112 fprintf (dump_file, "Renaming statement ");
1113 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1114 fprintf (dump_file, "\n");
1117 #if defined ENABLE_CHECKING
1118 /* We have just scanned the code for operands. No statement should
1124 /* Step 1. Rewrite USES and VUSES in the statement. */
1125 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1127 if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (use_p))))
1128 SET_USE (use_p, get_reaching_def (USE_FROM_PTR (use_p)));
1131 /* Step 2. Register the statement's DEF and VDEF operands. */
1132 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1134 var = DEF_FROM_PTR (def_p);
1136 if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (var)))
1139 SET_DEF (def_p, duplicate_ssa_name (var, stmt));
1140 ssa_register_new_def (var, DEF_FROM_PTR (def_p), &bd->block_defs);
1144 /* Replace the operand pointed by OP_P with its immediate reaching
1148 rewrite_operand (use_operand_p op_p)
1150 if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
1151 SET_USE (op_p, get_reaching_def (USE_FROM_PTR (op_p)));
1154 /* Register DEF (an SSA_NAME) to be a new definition for its underlying
1155 variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition
1156 into the stack pointed by BLOCK_DEFS_P. */
1159 register_new_def (tree def, varray_type *block_defs_p)
1161 tree var = SSA_NAME_VAR (def);
1164 /* If this variable is set in a single basic block and all uses are
1165 dominated by the set(s) in that single basic block, then there is
1166 no reason to record anything for this variable in the block local
1167 definition stacks. Doing so just wastes time and memory.
1169 This is the same test to prune the set of variables which may
1170 need PHI nodes. So we just use that information since it's already
1171 computed and available for us to use. */
1172 if (get_phi_state (var) == NEED_PHI_STATE_NO)
1174 set_current_def (var, def);
1178 currdef = get_current_def (var);
1179 if (! *block_defs_p)
1180 VARRAY_TREE_INIT (*block_defs_p, 20, "block_defs");
1182 /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
1183 later used by the dominator tree callbacks to restore the reaching
1184 definitions for all the variables defined in the block after a recursive
1185 visit to all its immediately dominated blocks. If there is no current
1186 reaching definition, then just record the underlying _DECL node. */
1187 VARRAY_PUSH_TREE (*block_defs_p, currdef ? currdef : var);
1189 /* Set the current reaching definition for VAR to be DEF. */
1190 set_current_def (var, def);
1193 /* Return the current definition for variable VAR. If none is found,
1194 create a new SSA name to act as the zeroth definition for VAR. If VAR
1195 is call clobbered and there exists a more recent definition of
1196 GLOBAL_VAR, return the definition for GLOBAL_VAR. This means that VAR
1197 has been clobbered by a function call since its last assignment. */
1200 get_reaching_def (tree var)
1202 tree default_d, currdef_var, avar;
1204 /* Lookup the current reaching definition for VAR. */
1205 default_d = NULL_TREE;
1206 currdef_var = get_current_def (var);
1208 /* If there is no reaching definition for VAR, create and register a
1209 default definition for it (if needed). */
1210 if (currdef_var == NULL_TREE)
1212 if (TREE_CODE (var) == SSA_NAME)
1213 avar = SSA_NAME_VAR (var);
1217 default_d = default_def (avar);
1218 if (default_d == NULL_TREE)
1220 default_d = make_ssa_name (avar, build_empty_stmt ());
1221 set_default_def (avar, default_d);
1223 set_current_def (var, default_d);
1226 /* Return the current reaching definition for VAR, or the default
1227 definition, if we had to create one. */
1228 return (currdef_var) ? currdef_var : default_d;
1232 /* Hashing and equality functions for DEF_BLOCKS. */
1235 def_blocks_hash (const void *p)
1237 return htab_hash_pointer
1238 ((const void *)((const struct def_blocks_d *)p)->var);
1242 def_blocks_eq (const void *p1, const void *p2)
1244 return ((const struct def_blocks_d *)p1)->var
1245 == ((const struct def_blocks_d *)p2)->var;
1248 /* Free memory allocated by one entry in DEF_BLOCKS. */
1251 def_blocks_free (void *p)
1253 struct def_blocks_d *entry = p;
1254 BITMAP_XFREE (entry->def_blocks);
1255 BITMAP_XFREE (entry->phi_blocks);
1256 BITMAP_XFREE (entry->livein_blocks);
1261 /* Dump the DEF_BLOCKS hash table on stderr. */
1264 debug_def_blocks (void)
1266 htab_traverse (def_blocks, debug_def_blocks_r, NULL);
1269 /* Callback for htab_traverse to dump the DEF_BLOCKS hash table. */
1272 debug_def_blocks_r (void **slot, void *data ATTRIBUTE_UNUSED)
1275 struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
1277 fprintf (stderr, "VAR: ");
1278 print_generic_expr (stderr, db_p->var, dump_flags);
1279 fprintf (stderr, ", DEF_BLOCKS: { ");
1280 EXECUTE_IF_SET_IN_BITMAP (db_p->def_blocks, 0, i,
1281 fprintf (stderr, "%ld ", i));
1282 fprintf (stderr, "}");
1283 fprintf (stderr, ", LIVEIN_BLOCKS: { ");
1284 EXECUTE_IF_SET_IN_BITMAP (db_p->livein_blocks, 0, i,
1285 fprintf (stderr, "%ld ", i));
1286 fprintf (stderr, "}\n");
1292 /* Return the set of blocks where variable VAR is defined and the blocks
1293 where VAR is live on entry (livein). Return NULL, if no entry is
1294 found in DEF_BLOCKS. */
1296 static inline struct def_blocks_d *
1297 find_def_blocks_for (tree var)
1299 struct def_blocks_d dm;
1301 return (struct def_blocks_d *) htab_find (def_blocks, &dm);
1305 /* Return the set of blocks where variable VAR is defined and the blocks
1306 where VAR is live on entry (livein). If no entry is found in
1307 DEF_BLOCKS, a new one is created and returned. */
1309 static inline struct def_blocks_d *
1310 get_def_blocks_for (tree var)
1312 struct def_blocks_d db, *db_p;
1316 slot = htab_find_slot (def_blocks, (void *) &db, INSERT);
1319 db_p = xmalloc (sizeof (*db_p));
1321 db_p->def_blocks = BITMAP_XMALLOC ();
1322 db_p->phi_blocks = BITMAP_XMALLOC ();
1323 db_p->livein_blocks = BITMAP_XMALLOC ();
1324 *slot = (void *) db_p;
1327 db_p = (struct def_blocks_d *) *slot;
1332 /* If a variable V in VARS_TO_RENAME is a pointer, the renaming
1333 process will cause us to lose the name memory tags that may have
1334 been associated with the various SSA_NAMEs of V. This means that
1335 the variables aliased to those name tags also need to be renamed
1338 FIXME 1- We should either have a better scheme for renaming
1339 pointers that doesn't lose name tags or re-run alias
1340 analysis to recover points-to information.
1342 2- Currently we just invalidate *all* the name tags. This
1343 should be more selective. */
1346 invalidate_name_tags (bitmap vars_to_rename)
1349 bool rename_name_tags_p;
1351 rename_name_tags_p = false;
1352 EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i,
1353 if (POINTER_TYPE_P (TREE_TYPE (referenced_var (i))))
1355 rename_name_tags_p = true;
1359 if (rename_name_tags_p)
1360 for (i = 0; i < num_referenced_vars; i++)
1362 var_ann_t ann = var_ann (referenced_var (i));
1364 if (ann->mem_tag_kind == NAME_TAG)
1367 varray_type may_aliases = ann->may_aliases;
1369 bitmap_set_bit (vars_to_rename, ann->uid);
1370 if (ann->may_aliases)
1371 for (j = 0; j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
1373 tree var = VARRAY_TREE (may_aliases, j);
1374 bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1381 /* Main entry point into the SSA builder. The renaming process
1382 proceeds in five main phases:
1384 1- If VARS_TO_RENAME has any entries, any existing PHI nodes for
1385 those variables are removed from the flow graph so that they can
1388 2- Compute dominance frontier and immediate dominators, needed to
1389 insert PHI nodes and rename the function in dominator tree
1392 3- Find and mark all the blocks that define variables
1395 4- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
1397 5- Rename all the blocks (rewrite_initialize_block,
1398 rewrite_add_phi_arguments) and statements in the program
1401 Steps 3 and 5 are done using the dominator tree walker
1402 (walk_dominator_tree).
1404 ALL is true if all variables should be renamed (otherwise just those
1405 mentioned in vars_to_rename are taken into account). */
1408 rewrite_into_ssa (bool all)
1412 struct dom_walk_data walk_data;
1413 struct mark_def_sites_global_data mark_def_sites_global_data;
1414 bitmap old_vars_to_rename = vars_to_rename;
1417 timevar_push (TV_TREE_SSA_OTHER);
1420 vars_to_rename = NULL;
1423 /* Initialize the array of variables to rename. */
1425 if (vars_to_rename == NULL)
1428 if (bitmap_first_set_bit (vars_to_rename) < 0)
1430 timevar_pop (TV_TREE_SSA_OTHER);
1434 invalidate_name_tags (vars_to_rename);
1436 /* Now remove all the existing PHI nodes (if any) for the variables
1437 that we are about to rename into SSA. */
1438 remove_all_phi_nodes_for (vars_to_rename);
1441 /* Allocate memory for the DEF_BLOCKS hash table. */
1442 def_blocks = htab_create (VARRAY_ACTIVE_SIZE (referenced_vars),
1443 def_blocks_hash, def_blocks_eq, def_blocks_free);
1445 /* Initialize dominance frontier and immediate dominator bitmaps.
1446 Also count the number of predecessors for each block. Doing so
1447 can save significant time during PHI insertion for large graphs. */
1448 dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
1454 for (e = bb->pred; e; e = e->pred_next)
1457 bb_ann (bb)->num_preds = count;
1458 dfs[bb->index] = BITMAP_XMALLOC ();
1461 for (i = 0; i < num_referenced_vars; i++)
1462 set_current_def (referenced_var (i), NULL_TREE);
1464 /* Ensure that the dominance information is OK. */
1465 calculate_dominance_info (CDI_DOMINATORS);
1467 /* Compute dominance frontiers. */
1468 compute_dominance_frontiers (dfs);
1470 /* Setup callbacks for the generic dominator tree walker to find and
1471 mark definition sites. */
1472 walk_data.walk_stmts_backward = false;
1473 walk_data.dom_direction = CDI_DOMINATORS;
1474 walk_data.initialize_block_local_data = NULL;
1475 walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block;
1476 walk_data.before_dom_children_walk_stmts = mark_def_sites;
1477 walk_data.before_dom_children_after_stmts = NULL;
1478 walk_data.after_dom_children_before_stmts = NULL;
1479 walk_data.after_dom_children_walk_stmts = NULL;
1480 walk_data.after_dom_children_after_stmts = NULL;
1482 /* Notice that this bitmap is indexed using variable UIDs, so it must be
1483 large enough to accommodate all the variables referenced in the
1484 function, not just the ones we are renaming. */
1485 mark_def_sites_global_data.kills = sbitmap_alloc (num_referenced_vars);
1486 walk_data.global_data = &mark_def_sites_global_data;
1488 /* We do not have any local data. */
1489 walk_data.block_local_data_size = 0;
1491 /* Initialize the dominator walker. */
1492 init_walk_dominator_tree (&walk_data);
1494 /* Recursively walk the dominator tree. */
1495 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1497 /* Finalize the dominator walker. */
1498 fini_walk_dominator_tree (&walk_data);
1500 /* We no longer need this bitmap, clear and free it. */
1501 sbitmap_free (mark_def_sites_global_data.kills);
1503 /* Insert PHI nodes at dominance frontiers of definition blocks. */
1504 insert_phi_nodes (dfs, NULL);
1506 /* Rewrite all the basic blocks in the program. */
1507 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
1509 /* Setup callbacks for the generic dominator tree walker. */
1510 walk_data.walk_stmts_backward = false;
1511 walk_data.dom_direction = CDI_DOMINATORS;
1512 walk_data.initialize_block_local_data = rewrite_initialize_block_local_data;
1513 walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
1514 walk_data.before_dom_children_walk_stmts = rewrite_stmt;
1515 walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
1516 walk_data.after_dom_children_before_stmts = NULL;
1517 walk_data.after_dom_children_walk_stmts = NULL;
1518 walk_data.after_dom_children_after_stmts = rewrite_finalize_block;
1519 walk_data.global_data = NULL;
1520 walk_data.block_local_data_size = sizeof (struct rewrite_block_data);
1522 /* Initialize the dominator walker. */
1523 init_walk_dominator_tree (&walk_data);
1525 /* Recursively walk the dominator tree rewriting each statement in
1526 each basic block. */
1527 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1529 /* Finalize the dominator walker. */
1530 fini_walk_dominator_tree (&walk_data);
1532 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
1534 /* Debugging dumps. */
1535 if (dump_file && (dump_flags & TDF_STATS))
1537 dump_dfa_stats (dump_file);
1538 dump_tree_ssa_stats (dump_file);
1541 /* Free allocated memory. */
1543 BITMAP_XFREE (dfs[bb->index]);
1546 htab_delete (def_blocks);
1548 vars_to_rename = old_vars_to_rename;
1549 timevar_pop (TV_TREE_SSA_OTHER);
1552 /* The marked ssa names may have more than one definition;
1553 add phi nodes and rewrite them to fix this. */
1556 rewrite_ssa_into_ssa (void)
1560 struct dom_walk_data walk_data;
1561 struct mark_def_sites_global_data mark_def_sites_global_data;
1563 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,
1615 SET_BIT (snames_to_rename, i));
1617 mark_def_sites_global_data.kills = sbitmap_alloc (num_ssa_names);
1618 mark_def_sites_global_data.names_to_rename = snames_to_rename;
1619 walk_data.global_data = &mark_def_sites_global_data;
1621 /* We do not have any local data. */
1622 walk_data.block_local_data_size = 0;
1624 /* Initialize the dominator walker. */
1625 init_walk_dominator_tree (&walk_data);
1627 /* Recursively walk the dominator tree. */
1628 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1630 /* Finalize the dominator walker. */
1631 fini_walk_dominator_tree (&walk_data);
1633 /* We no longer need this bitmap, clear and free it. */
1634 sbitmap_free (mark_def_sites_global_data.kills);
1636 for (i = 1; i < num_ssa_names; i++)
1637 set_current_def (ssa_name (i), NULL_TREE);
1639 /* Insert PHI nodes at dominance frontiers of definition blocks. */
1640 insert_phi_nodes (dfs, to_rename);
1642 /* Rewrite all the basic blocks in the program. */
1643 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
1645 /* Setup callbacks for the generic dominator tree walker. */
1646 walk_data.walk_stmts_backward = false;
1647 walk_data.dom_direction = CDI_DOMINATORS;
1648 walk_data.initialize_block_local_data
1649 = rewrite_initialize_block_local_data;
1650 walk_data.before_dom_children_before_stmts = ssa_rewrite_initialize_block;
1651 walk_data.before_dom_children_walk_stmts = ssa_rewrite_stmt;
1652 walk_data.before_dom_children_after_stmts = ssa_rewrite_phi_arguments;
1653 walk_data.after_dom_children_before_stmts = NULL;
1654 walk_data.after_dom_children_walk_stmts = NULL;
1655 walk_data.after_dom_children_after_stmts = ssa_rewrite_finalize_block;
1656 walk_data.global_data = snames_to_rename;
1657 walk_data.block_local_data_size = sizeof (struct rewrite_block_data);
1659 /* Initialize the dominator walker. */
1660 init_walk_dominator_tree (&walk_data);
1662 /* Recursively walk the dominator tree rewriting each statement in
1663 each basic block. */
1664 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1666 /* Finalize the dominator walker. */
1667 fini_walk_dominator_tree (&walk_data);
1669 unmark_all_for_rewrite ();
1671 EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, release_ssa_name (ssa_name (i)));
1673 sbitmap_free (snames_to_rename);
1675 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
1677 /* Debugging dumps. */
1678 if (dump_file && (dump_flags & TDF_STATS))
1680 dump_dfa_stats (dump_file);
1681 dump_tree_ssa_stats (dump_file);
1684 /* Free allocated memory. */
1686 BITMAP_XFREE (dfs[bb->index]);
1689 htab_delete (def_blocks);
1691 for (i = 1; i < num_ssa_names; i++)
1693 name = ssa_name (i);
1694 if (!SSA_NAME_AUX (name))
1697 free (SSA_NAME_AUX (name));
1698 SSA_NAME_AUX (name) = NULL;
1701 BITMAP_XFREE (to_rename);
1702 timevar_pop (TV_TREE_SSA_OTHER);
1705 /* Rewrites all variables into ssa. */
1708 rewrite_all_into_ssa (void)
1710 rewrite_into_ssa (true);
1713 struct tree_opt_pass pass_build_ssa =
1717 rewrite_all_into_ssa, /* execute */
1720 0, /* static_pass_number */
1722 PROP_cfg | PROP_referenced_vars, /* properties_required */
1723 PROP_ssa, /* properties_provided */
1724 0, /* properties_destroyed */
1725 0, /* todo_flags_start */
1726 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */