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 vector 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 vector 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 VEC(tree_on_heap) *block_defs_stack;
114 /* Basic block vectors used in this file ought to be allocated in the heap. */
115 DEF_VEC_MALLOC_P(basic_block);
117 /* Global data to attach to the main dominator walk structure. */
118 struct mark_def_sites_global_data
120 /* This sbitmap contains the variables which are set before they
121 are used in a basic block. We keep it as a global variable
122 solely to avoid the overhead of allocating and deallocating
126 /* Bitmap of names to rename. */
127 sbitmap names_to_rename;
130 /* Information stored for ssa names. */
134 /* This field indicates whether or not the variable may need PHI nodes.
135 See the enum's definition for more detailed information about the
137 ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
139 /* The actual definition of the ssa name. */
143 /* Local functions. */
144 static void rewrite_finalize_block (struct dom_walk_data *, basic_block);
145 static void rewrite_initialize_block (struct dom_walk_data *, basic_block);
146 static void rewrite_add_phi_arguments (struct dom_walk_data *, basic_block);
147 static void mark_def_sites (struct dom_walk_data *walk_data,
148 basic_block bb, block_stmt_iterator);
149 static void mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
151 static void set_def_block (tree, basic_block, bool, bool);
152 static void set_livein_block (tree, basic_block);
153 static bool prepare_use_operand_for_rename (use_operand_p, size_t *uid_p);
154 static bool prepare_def_operand_for_rename (tree def, size_t *uid_p);
155 static void insert_phi_nodes (bitmap *, bitmap);
156 static void rewrite_stmt (struct dom_walk_data *, basic_block,
157 block_stmt_iterator);
158 static inline void rewrite_operand (use_operand_p);
159 static void insert_phi_nodes_for (tree, bitmap *, VEC(basic_block) **);
160 static tree get_reaching_def (tree);
161 static hashval_t def_blocks_hash (const void *);
162 static int def_blocks_eq (const void *, const void *);
163 static void def_blocks_free (void *);
164 static int debug_def_blocks_r (void **, void *);
165 static inline struct def_blocks_d *get_def_blocks_for (tree);
166 static inline struct def_blocks_d *find_def_blocks_for (tree);
167 static void htab_statistics (FILE *, htab_t);
169 /* Get the information associated with NAME. */
171 static inline struct ssa_name_info *
172 get_ssa_name_ann (tree name)
174 if (!SSA_NAME_AUX (name))
175 SSA_NAME_AUX (name) = xcalloc (1, sizeof (struct ssa_name_info));
177 return SSA_NAME_AUX (name);
180 /* Gets phi_state field for VAR. */
182 static inline enum need_phi_state
183 get_phi_state (tree var)
185 if (TREE_CODE (var) == SSA_NAME)
186 return get_ssa_name_ann (var)->need_phi_state;
188 return var_ann (var)->need_phi_state;
191 /* Sets phi_state field for VAR to STATE. */
194 set_phi_state (tree var, enum need_phi_state state)
196 if (TREE_CODE (var) == SSA_NAME)
197 get_ssa_name_ann (var)->need_phi_state = state;
199 var_ann (var)->need_phi_state = state;
202 /* Return the current definition for VAR. */
205 get_current_def (tree var)
207 if (TREE_CODE (var) == SSA_NAME)
208 return get_ssa_name_ann (var)->current_def;
210 return var_ann (var)->current_def;
213 /* Sets current definition of VAR to DEF. */
216 set_current_def (tree var, tree def)
218 if (TREE_CODE (var) == SSA_NAME)
219 get_ssa_name_ann (var)->current_def = def;
221 var_ann (var)->current_def = def;
224 /* Compute global livein information given the set of blockx where
225 an object is locally live at the start of the block (LIVEIN)
226 and the set of blocks where the object is defined (DEF_BLOCKS).
228 Note: This routine augments the existing local livein information
229 to include global livein (i.e., it modifies the underlying bitmap
233 compute_global_livein (bitmap livein, bitmap def_blocks)
235 basic_block bb, *worklist, *tos;
240 = (basic_block *) xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
242 EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
244 *tos++ = BASIC_BLOCK (i);
247 /* Iterate until the worklist is empty. */
248 while (tos != worklist)
253 /* Pull a block off the worklist. */
256 /* For each predecessor block. */
257 FOR_EACH_EDGE (e, ei, bb->preds)
259 basic_block pred = e->src;
260 int pred_index = pred->index;
262 /* None of this is necessary for the entry block. */
263 if (pred != ENTRY_BLOCK_PTR
264 && ! bitmap_bit_p (livein, pred_index)
265 && ! bitmap_bit_p (def_blocks, pred_index))
268 bitmap_set_bit (livein, pred_index);
277 /* Block initialization routine for mark_def_sites. Clear the
278 KILLS bitmap at the start of each block. */
281 mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
282 basic_block bb ATTRIBUTE_UNUSED)
284 struct mark_def_sites_global_data *gd = walk_data->global_data;
285 sbitmap kills = gd->kills;
287 sbitmap_zero (kills);
290 /* Block initialization routine for mark_def_sites. Clear the
291 KILLS bitmap at the start of each block. */
294 ssa_mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
297 struct mark_def_sites_global_data *gd = walk_data->global_data;
298 sbitmap kills = gd->kills;
302 sbitmap_zero (kills);
304 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
306 def = PHI_RESULT (phi);
307 def_uid = SSA_NAME_VERSION (def);
309 if (!TEST_BIT (gd->names_to_rename, def_uid))
312 set_def_block (def, bb, true, true);
313 SET_BIT (kills, def_uid);
317 /* Marks ssa names used as arguments of phis at the end of BB. */
320 ssa_mark_phi_uses (struct dom_walk_data *walk_data, basic_block bb)
322 struct mark_def_sites_global_data *gd = walk_data->global_data;
323 sbitmap kills = gd->kills;
329 FOR_EACH_EDGE (e, ei, bb->succs)
331 if (e->dest == EXIT_BLOCK_PTR)
334 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
336 use = PHI_ARG_DEF_FROM_EDGE (phi, e);
337 if (TREE_CODE (use) != SSA_NAME)
340 uid = SSA_NAME_VERSION (use);
342 if (TEST_BIT (gd->names_to_rename, uid)
343 && !TEST_BIT (kills, uid))
344 set_livein_block (use, bb);
349 /* Call back for walk_dominator_tree used to collect definition sites
350 for every variable in the function. For every statement S in block
353 1- Variables defined by S in DEF_OPS(S) are marked in the bitmap
354 WALK_DATA->GLOBAL_DATA->KILLS.
356 2- If S uses a variable VAR and there is no preceding kill of VAR,
357 then it is marked in marked in the LIVEIN_BLOCKS bitmap
360 This information is used to determine which variables are live
361 across block boundaries to reduce the number of PHI nodes
365 mark_def_sites (struct dom_walk_data *walk_data,
367 block_stmt_iterator bsi)
369 struct mark_def_sites_global_data *gd = walk_data->global_data;
370 sbitmap kills = gd->kills;
377 /* Mark all the blocks that have definitions for each variable in the
378 VARS_TO_RENAME bitmap. */
379 stmt = bsi_stmt (bsi);
380 get_stmt_operands (stmt);
382 /* If a variable is used before being set, then the variable is live
383 across a block boundary, so mark it live-on-entry to BB. */
385 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE | SSA_OP_VMUSTDEFKILL)
387 if (prepare_use_operand_for_rename (use_p, &uid)
388 && !TEST_BIT (kills, uid))
389 set_livein_block (USE_FROM_PTR (use_p), bb);
392 /* Note that virtual definitions are irrelevant for computing KILLS
393 because a V_MAY_DEF does not constitute a killing definition of the
394 variable. However, the operand of a virtual definitions is a use
395 of the variable, so it may cause the variable to be considered
398 FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
400 if (prepare_use_operand_for_rename (use_p, &uid))
402 /* If we do not already have an SSA_NAME for our destination,
403 then set the destination to the source. */
404 if (TREE_CODE (DEF_FROM_PTR (def_p)) != SSA_NAME)
405 SET_DEF (def_p, USE_FROM_PTR (use_p));
407 set_livein_block (USE_FROM_PTR (use_p), bb);
408 set_def_block (DEF_FROM_PTR (def_p), bb, false, false);
412 /* Now process the virtual must-defs made by this statement. */
413 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF | SSA_OP_VMUSTDEF)
415 if (prepare_def_operand_for_rename (def, &uid))
417 set_def_block (def, bb, false, false);
418 SET_BIT (kills, uid);
424 /* Ditto, but works over ssa names. */
427 ssa_mark_def_sites (struct dom_walk_data *walk_data,
429 block_stmt_iterator bsi)
431 struct mark_def_sites_global_data *gd = walk_data->global_data;
432 sbitmap kills = gd->kills;
437 /* Mark all the blocks that have definitions for each variable in the
438 names_to_rename bitmap. */
439 stmt = bsi_stmt (bsi);
440 get_stmt_operands (stmt);
442 /* If a variable is used before being set, then the variable is live
443 across a block boundary, so mark it live-on-entry to BB. */
444 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
446 uid = SSA_NAME_VERSION (use);
448 if (TEST_BIT (gd->names_to_rename, uid)
449 && !TEST_BIT (kills, uid))
450 set_livein_block (use, bb);
453 /* Now process the definition made by this statement. Mark the
454 variables in KILLS. */
455 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
457 def_uid = SSA_NAME_VERSION (def);
459 if (TEST_BIT (gd->names_to_rename, def_uid))
461 set_def_block (def, bb, false, true);
462 SET_BIT (kills, def_uid);
467 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
468 VAR is defined by a phi node. SSA_P is true if we are called from
469 rewrite_ssa_into_ssa. */
472 set_def_block (tree var, basic_block bb, bool phi_p, bool ssa_p)
474 struct def_blocks_d *db_p;
475 enum need_phi_state state;
478 && TREE_CODE (var) == SSA_NAME)
479 var = SSA_NAME_VAR (var);
481 state = get_phi_state (var);
482 db_p = get_def_blocks_for (var);
484 /* Set the bit corresponding to the block where VAR is defined. */
485 bitmap_set_bit (db_p->def_blocks, bb->index);
487 bitmap_set_bit (db_p->phi_blocks, bb->index);
489 /* Keep track of whether or not we may need to insert phi nodes.
491 If we are in the UNKNOWN state, then this is the first definition
492 of VAR. Additionally, we have not seen any uses of VAR yet, so
493 we do not need a phi node for this variable at this time (i.e.,
494 transition to NEED_PHI_STATE_NO).
496 If we are in any other state, then we either have multiple definitions
497 of this variable occurring in different blocks or we saw a use of the
498 variable which was not dominated by the block containing the
499 definition(s). In this case we may need a PHI node, so enter
500 state NEED_PHI_STATE_MAYBE. */
501 if (state == NEED_PHI_STATE_UNKNOWN)
502 set_phi_state (var, NEED_PHI_STATE_NO);
504 set_phi_state (var, NEED_PHI_STATE_MAYBE);
508 /* Mark block BB as having VAR live at the entry to BB. */
511 set_livein_block (tree var, basic_block bb)
513 struct def_blocks_d *db_p;
514 enum need_phi_state state = get_phi_state (var);
516 db_p = get_def_blocks_for (var);
518 /* Set the bit corresponding to the block where VAR is live in. */
519 bitmap_set_bit (db_p->livein_blocks, bb->index);
521 /* Keep track of whether or not we may need to insert phi nodes.
523 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
524 by the single block containing the definition(s) of this variable. If
525 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
526 NEED_PHI_STATE_MAYBE. */
527 if (state == NEED_PHI_STATE_NO)
529 int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
531 if (def_block_index == -1
532 || ! dominated_by_p (CDI_DOMINATORS, bb,
533 BASIC_BLOCK (def_block_index)))
534 set_phi_state (var, NEED_PHI_STATE_MAYBE);
537 set_phi_state (var, NEED_PHI_STATE_MAYBE);
541 /* If the use operand pointed to by OP_P needs to be renamed, then strip away
542 any SSA_NAME wrapping the operand, set *UID_P to the underlying variable's
543 uid, and return true. Otherwise return false. If the operand was an
544 SSA_NAME, change it to the stripped name. */
547 prepare_use_operand_for_rename (use_operand_p op_p, size_t *uid_p)
549 tree use = USE_FROM_PTR (op_p);
550 tree var = (TREE_CODE (use) != SSA_NAME) ? use : SSA_NAME_VAR (use);
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))
557 /* The variable needs to be renamed. If this is a use which already
558 has an SSA_NAME, then strip it off.
560 By not throwing away SSA_NAMEs on assignments, we avoid a lot of
561 useless churn of SSA_NAMEs without having to overly complicate the
563 if (TREE_CODE (use) == SSA_NAME)
569 /* If the def variable DEF needs to be renamed, then strip away any SSA_NAME
570 wrapping the operand, set *UID_P to the underlying variable's uid and return
571 true. Otherwise return false. */
574 prepare_def_operand_for_rename (tree def, size_t *uid_p)
576 tree var = (TREE_CODE (def) != SSA_NAME) ? def : SSA_NAME_VAR (def);
577 *uid_p = var_ann (var)->uid;
579 /* Ignore variables that don't need to be renamed. */
580 if (vars_to_rename && !bitmap_bit_p (vars_to_rename, *uid_p))
586 /* Helper for insert_phi_nodes. If VAR needs PHI nodes, insert them
587 at the dominance frontier (DFS) of blocks defining VAR.
588 WORK_STACK is the vector used to implement the worklist of basic
592 insert_phi_nodes_1 (tree var, bitmap *dfs, VEC(basic_block) **work_stack)
594 if (get_phi_state (var) != NEED_PHI_STATE_NO)
595 insert_phi_nodes_for (var, dfs, work_stack);
598 /* Insert PHI nodes at the dominance frontier of blocks with variable
599 definitions. DFS contains the dominance frontier information for
600 the flowgraph. PHI nodes will only be inserted at the dominance
601 frontier of definition blocks for variables whose NEED_PHI_STATE
602 annotation is marked as ``maybe'' or ``unknown'' (computed by
603 mark_def_sites). If NAMES_TO_RENAME is not NULL, do the same but
604 for ssa name rewriting. */
607 insert_phi_nodes (bitmap *dfs, bitmap names_to_rename)
610 VEC(basic_block) *work_stack;
613 timevar_push (TV_TREE_INSERT_PHI_NODES);
615 /* Vector WORK_STACK is a stack of CFG blocks. Each block that contains
616 an assignment or PHI node will be pushed to this stack. */
617 work_stack = VEC_alloc (basic_block, n_basic_blocks);
619 /* Iterate over all variables in VARS_TO_RENAME. For each variable, add
620 to the work list all the blocks that have a definition for the
621 variable. PHI nodes will be added to the dominance frontier blocks of
622 each definition block. */
625 EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
628 insert_phi_nodes_1 (ssa_name (i), dfs, &work_stack);
631 else if (vars_to_rename)
632 EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i, bi)
634 insert_phi_nodes_1 (referenced_var (i), dfs, &work_stack);
637 for (i = 0; i < num_referenced_vars; i++)
638 insert_phi_nodes_1 (referenced_var (i), dfs, &work_stack);
640 VEC_free (basic_block, work_stack);
642 timevar_pop (TV_TREE_INSERT_PHI_NODES);
646 /* Perform a depth-first traversal of the dominator tree looking for
647 variables to rename. BB is the block where to start searching.
648 Renaming is a five step process:
650 1- Every definition made by PHI nodes at the start of the blocks is
651 registered as the current definition for the corresponding variable.
653 2- Every statement in BB is rewritten. USE and VUSE operands are
654 rewritten with their corresponding reaching definition. DEF and
655 VDEF targets are registered as new definitions.
657 3- All the PHI nodes in successor blocks of BB are visited. The
658 argument corresponding to BB is replaced with its current reaching
661 4- Recursively rewrite every dominator child block of BB.
663 5- Restore (in reverse order) the current reaching definition for every
664 new definition introduced in this block. This is done so that when
665 we return from the recursive call, all the current reaching
666 definitions are restored to the names that were valid in the
667 dominator parent of BB. */
669 /* SSA Rewriting Step 1. Initialization, create a block local stack
670 of reaching definitions for new SSA names produced in this block
671 (BLOCK_DEFS). Register new definitions for every PHI node in the
675 rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
680 if (dump_file && (dump_flags & TDF_DETAILS))
681 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
683 /* Mark the unwind point for this block. */
684 VEC_safe_push (tree_on_heap, block_defs_stack, NULL_TREE);
686 /* Step 1. Register new definitions for every PHI node in the block.
687 Conceptually, all the PHI nodes are executed in parallel and each PHI
688 node introduces a new version for the associated variable. */
689 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
691 tree result = PHI_RESULT (phi);
693 register_new_def (result, &block_defs_stack);
697 /* Register DEF (an SSA_NAME) to be a new definition for the original
698 ssa name VAR and push VAR's current reaching definition
699 into the stack pointed by BLOCK_DEFS_P. */
702 ssa_register_new_def (tree var, tree def)
706 /* If this variable is set in a single basic block and all uses are
707 dominated by the set(s) in that single basic block, then there is
708 nothing to do. TODO we should not be called at all, and just
709 keep the original name. */
710 if (get_phi_state (var) == NEED_PHI_STATE_NO)
712 set_current_def (var, def);
716 currdef = get_current_def (var);
718 /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
719 later used by the dominator tree callbacks to restore the reaching
720 definitions for all the variables defined in the block after a recursive
721 visit to all its immediately dominated blocks. */
722 VEC_safe_push (tree_on_heap, block_defs_stack, currdef);
723 VEC_safe_push (tree_on_heap, block_defs_stack, var);
725 /* Set the current reaching definition for VAR to be DEF. */
726 set_current_def (var, def);
729 /* Ditto, for rewriting ssa names. */
732 ssa_rewrite_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
735 sbitmap names_to_rename = walk_data->global_data;
740 if (dump_file && (dump_flags & TDF_DETAILS))
741 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
743 /* Mark the unwind point for this block. */
744 VEC_safe_push (tree_on_heap, block_defs_stack, NULL_TREE);
746 FOR_EACH_EDGE (e, ei, bb->preds)
747 if (e->flags & EDGE_ABNORMAL)
749 abnormal_phi = (e != NULL);
751 /* Step 1. Register new definitions for every PHI node in the block.
752 Conceptually, all the PHI nodes are executed in parallel and each PHI
753 node introduces a new version for the associated variable. */
754 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
756 tree result = PHI_RESULT (phi);
758 if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (result)))
760 new_name = duplicate_ssa_name (result, phi);
761 SET_PHI_RESULT (phi, new_name);
764 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
769 ssa_register_new_def (result, new_name);
773 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
774 PHI nodes. For every PHI node found, add a new argument containing the
775 current reaching definition for the variable and the edge through which
776 that definition is reaching the PHI node. */
779 rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
785 FOR_EACH_EDGE (e, ei, bb->succs)
789 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
793 /* If this PHI node has already been rewritten, then there is
794 nothing to do for this PHI or any following PHIs since we
795 always add new PHI nodes at the start of the PHI chain. */
796 if (PHI_REWRITTEN (phi))
799 currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
800 add_phi_arg (phi, currdef, e);
805 /* Rewrite existing virtual PHI arguments so that they have the correct
806 reaching definitions. BB is the basic block whose successors contain the
807 phi nodes we want to add arguments for. */
810 rewrite_virtual_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
817 FOR_EACH_EDGE (e, ei, bb->succs)
821 if (e->dest == EXIT_BLOCK_PTR)
824 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
826 tree result = PHI_RESULT (phi);
827 op = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
829 if (is_gimple_reg (result)
830 || !bitmap_bit_p (vars_to_rename,
831 var_ann (SSA_NAME_VAR (result))->uid))
834 SET_USE (op, get_reaching_def (SSA_NAME_VAR (result)));
835 if (e->flags & EDGE_ABNORMAL)
836 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (op)) = 1;
841 /* Ditto, for ssa name rewriting. */
844 ssa_rewrite_phi_arguments (struct dom_walk_data *walk_data, basic_block bb)
847 sbitmap names_to_rename = walk_data->global_data;
851 FOR_EACH_EDGE (e, ei, bb->succs)
855 if (e->dest == EXIT_BLOCK_PTR)
858 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
860 op = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
861 if (TREE_CODE (USE_FROM_PTR (op)) != SSA_NAME)
864 if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (op))))
867 SET_USE (op, get_reaching_def (USE_FROM_PTR (op)));
868 if (e->flags & EDGE_ABNORMAL)
869 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (op)) = 1;
875 /* Similar to restore_vars_to_original_value, except that it restores
876 CURRDEFS to its original value. */
878 rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
879 basic_block bb ATTRIBUTE_UNUSED)
881 /* Restore CURRDEFS to its original state. */
882 while (VEC_length (tree_on_heap, block_defs_stack) > 0)
884 tree tmp = VEC_pop (tree_on_heap, block_defs_stack);
887 if (tmp == NULL_TREE)
890 /* If we recorded an SSA_NAME, then make the SSA_NAME the current
891 definition of its underlying variable. If we recorded anything
892 else, it must have been an _DECL node and its current reaching
893 definition must have been NULL. */
894 if (TREE_CODE (tmp) == SSA_NAME)
897 var = SSA_NAME_VAR (saved_def);
905 set_current_def (var, saved_def);
909 /* Ditto, for rewriting ssa names. */
912 ssa_rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
913 basic_block bb ATTRIBUTE_UNUSED)
916 /* Step 5. Restore the current reaching definition for each variable
917 referenced in the block (in reverse order). */
918 while (VEC_length (tree_on_heap, block_defs_stack) > 0)
920 tree var = VEC_pop (tree_on_heap, block_defs_stack);
926 saved_def = VEC_pop (tree_on_heap, block_defs_stack);
928 set_current_def (var, saved_def);
932 /* Dump SSA information to FILE. */
935 dump_tree_ssa (FILE *file)
939 = lang_hooks.decl_printable_name (current_function_decl, 2);
941 fprintf (file, "SSA information for %s\n\n", funcname);
945 dump_bb (bb, file, 0);
947 print_generic_stmt (file, phi_nodes (bb), dump_flags);
948 fputs ("\n\n", file);
953 /* Dump SSA information to stderr. */
956 debug_tree_ssa (void)
958 dump_tree_ssa (stderr);
962 /* Dump SSA statistics on FILE. */
965 dump_tree_ssa_stats (FILE *file)
967 fprintf (file, "\nHash table statistics:\n");
969 fprintf (file, " def_blocks: ");
970 htab_statistics (file, def_blocks);
972 fprintf (file, "\n");
976 /* Dump SSA statistics on stderr. */
979 debug_tree_ssa_stats (void)
981 dump_tree_ssa_stats (stderr);
985 /* Dump statistics for the hash table HTAB. */
988 htab_statistics (FILE *file, htab_t htab)
990 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
991 (long) htab_size (htab),
992 (long) htab_elements (htab),
993 htab_collisions (htab));
997 /* Insert PHI nodes for variable VAR using the dominance frontier
998 information given in DFS. WORK_STACK is the vector used to
999 implement the worklist of basic blocks. */
1002 insert_phi_nodes_for (tree var, bitmap *dfs, VEC(basic_block) **work_stack)
1004 struct def_blocks_d *def_map;
1005 bitmap phi_insertion_points;
1012 def_map = find_def_blocks_for (var);
1013 if (def_map == NULL)
1016 phi_insertion_points = BITMAP_XMALLOC ();
1018 EXECUTE_IF_SET_IN_BITMAP (def_map->def_blocks, 0, bb_index, bi)
1020 VEC_safe_push (basic_block, *work_stack, BASIC_BLOCK (bb_index));
1023 /* Pop a block off the worklist, add every block that appears in
1024 the original block's dfs that we have not already processed to
1025 the worklist. Iterate until the worklist is empty. Blocks
1026 which are added to the worklist are potential sites for
1029 The iteration step could be done during PHI insertion just as
1030 easily. We do it here for historical reasons -- we used to have
1031 a heuristic which used the potential PHI insertion points to
1032 determine if fully pruned or semi pruned SSA form was appropriate.
1034 We now always use fully pruned SSA form. */
1035 while (VEC_length (basic_block, *work_stack) > 0)
1040 bb = VEC_pop (basic_block, *work_stack);
1041 bb_index = bb->index;
1043 EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index],
1044 phi_insertion_points,
1047 basic_block bb = BASIC_BLOCK (dfs_index);
1049 /* Use a safe push because if there is a definition of VAR
1050 in every basic block, then WORK_STACK may eventually have
1051 more than N_BASIC_BLOCK entries. */
1052 VEC_safe_push (basic_block, *work_stack, bb);
1053 bitmap_set_bit (phi_insertion_points, dfs_index);
1057 /* Remove the blocks where we already have the phis. */
1058 bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
1060 /* Now compute global livein for this variable. Note this modifies
1061 def_map->livein_blocks. */
1062 compute_global_livein (def_map->livein_blocks, def_map->def_blocks);
1064 /* And insert the PHI nodes. */
1065 EXECUTE_IF_AND_IN_BITMAP (phi_insertion_points, def_map->livein_blocks,
1068 bb = BASIC_BLOCK (bb_index);
1070 phi = create_phi_node (var, bb);
1072 /* If we are rewriting ssa names, add also the phi arguments. */
1073 if (TREE_CODE (var) == SSA_NAME)
1076 FOR_EACH_EDGE (e, ei, bb->preds)
1077 add_phi_arg (phi, var, e);
1081 BITMAP_XFREE (phi_insertion_points);
1084 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1085 the block with its immediate reaching definitions. Update the current
1086 definition of a variable when a new real or virtual definition is found. */
1089 rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1090 basic_block bb ATTRIBUTE_UNUSED,
1091 block_stmt_iterator si)
1095 use_operand_p use_p;
1096 def_operand_p def_p;
1099 stmt = bsi_stmt (si);
1100 ann = stmt_ann (stmt);
1102 if (dump_file && (dump_flags & TDF_DETAILS))
1104 fprintf (dump_file, "Renaming statement ");
1105 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1106 fprintf (dump_file, "\n");
1109 /* We have just scanned the code for operands. No statement should
1111 gcc_assert (!ann->modified);
1113 /* Step 1. Rewrite USES and VUSES in the statement. */
1114 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
1115 rewrite_operand (use_p);
1117 /* Step 2. Register the statement's DEF and VDEF operands. */
1118 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1120 if (TREE_CODE (DEF_FROM_PTR (def_p)) != SSA_NAME)
1121 SET_DEF (def_p, make_ssa_name (DEF_FROM_PTR (def_p), stmt));
1123 /* FIXME: We shouldn't be registering new defs if the variable
1124 doesn't need to be renamed. */
1125 register_new_def (DEF_FROM_PTR (def_p), &block_defs_stack);
1129 /* Ditto, for rewriting ssa names. */
1132 ssa_rewrite_stmt (struct dom_walk_data *walk_data,
1133 basic_block bb ATTRIBUTE_UNUSED,
1134 block_stmt_iterator si)
1139 use_operand_p use_p;
1140 def_operand_p def_p;
1141 sbitmap names_to_rename = walk_data->global_data;
1143 stmt = bsi_stmt (si);
1144 ann = stmt_ann (stmt);
1146 if (dump_file && (dump_flags & TDF_DETAILS))
1148 fprintf (dump_file, "Renaming statement ");
1149 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1150 fprintf (dump_file, "\n");
1153 /* We have just scanned the code for operands. No statement should
1155 gcc_assert (!ann->modified);
1157 /* Step 1. Rewrite USES and VUSES in the statement. */
1158 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
1160 if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (use_p))))
1161 SET_USE (use_p, get_reaching_def (USE_FROM_PTR (use_p)));
1164 /* Step 2. Register the statement's DEF and VDEF operands. */
1165 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1167 var = DEF_FROM_PTR (def_p);
1169 if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (var)))
1172 SET_DEF (def_p, duplicate_ssa_name (var, stmt));
1173 ssa_register_new_def (var, DEF_FROM_PTR (def_p));
1177 /* Replace the operand pointed by OP_P with its immediate reaching
1181 rewrite_operand (use_operand_p op_p)
1183 if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
1184 SET_USE (op_p, get_reaching_def (USE_FROM_PTR (op_p)));
1187 /* Register DEF (an SSA_NAME) to be a new definition for its underlying
1188 variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition
1189 into the stack pointed by BLOCK_DEFS_P. */
1192 register_new_def (tree def, VEC (tree_on_heap) **block_defs_p)
1194 tree var = SSA_NAME_VAR (def);
1197 /* If this variable is set in a single basic block and all uses are
1198 dominated by the set(s) in that single basic block, then there is
1199 no reason to record anything for this variable in the block local
1200 definition stacks. Doing so just wastes time and memory.
1202 This is the same test to prune the set of variables which may
1203 need PHI nodes. So we just use that information since it's already
1204 computed and available for us to use. */
1205 if (get_phi_state (var) == NEED_PHI_STATE_NO)
1207 set_current_def (var, def);
1211 currdef = get_current_def (var);
1213 /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
1214 later used by the dominator tree callbacks to restore the reaching
1215 definitions for all the variables defined in the block after a recursive
1216 visit to all its immediately dominated blocks. If there is no current
1217 reaching definition, then just record the underlying _DECL node. */
1218 VEC_safe_push (tree_on_heap, *block_defs_p, currdef ? currdef : var);
1220 /* Set the current reaching definition for VAR to be DEF. */
1221 set_current_def (var, def);
1224 /* Return the current definition for variable VAR. If none is found,
1225 create a new SSA name to act as the zeroth definition for VAR. If VAR
1226 is call clobbered and there exists a more recent definition of
1227 GLOBAL_VAR, return the definition for GLOBAL_VAR. This means that VAR
1228 has been clobbered by a function call since its last assignment. */
1231 get_reaching_def (tree var)
1233 tree default_d, currdef_var, avar;
1235 /* Lookup the current reaching definition for VAR. */
1236 default_d = NULL_TREE;
1237 currdef_var = get_current_def (var);
1239 /* If there is no reaching definition for VAR, create and register a
1240 default definition for it (if needed). */
1241 if (currdef_var == NULL_TREE)
1243 if (TREE_CODE (var) == SSA_NAME)
1244 avar = SSA_NAME_VAR (var);
1248 default_d = default_def (avar);
1249 if (default_d == NULL_TREE)
1251 default_d = make_ssa_name (avar, build_empty_stmt ());
1252 set_default_def (avar, default_d);
1254 set_current_def (var, default_d);
1257 /* Return the current reaching definition for VAR, or the default
1258 definition, if we had to create one. */
1259 return (currdef_var) ? currdef_var : default_d;
1263 /* Hashing and equality functions for DEF_BLOCKS. */
1266 def_blocks_hash (const void *p)
1268 return htab_hash_pointer
1269 ((const void *)((const struct def_blocks_d *)p)->var);
1273 def_blocks_eq (const void *p1, const void *p2)
1275 return ((const struct def_blocks_d *)p1)->var
1276 == ((const struct def_blocks_d *)p2)->var;
1279 /* Free memory allocated by one entry in DEF_BLOCKS. */
1282 def_blocks_free (void *p)
1284 struct def_blocks_d *entry = p;
1285 BITMAP_XFREE (entry->def_blocks);
1286 BITMAP_XFREE (entry->phi_blocks);
1287 BITMAP_XFREE (entry->livein_blocks);
1292 /* Dump the DEF_BLOCKS hash table on stderr. */
1295 debug_def_blocks (void)
1297 htab_traverse (def_blocks, debug_def_blocks_r, NULL);
1300 /* Callback for htab_traverse to dump the DEF_BLOCKS hash table. */
1303 debug_def_blocks_r (void **slot, void *data ATTRIBUTE_UNUSED)
1305 struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
1307 fprintf (stderr, "VAR: ");
1308 print_generic_expr (stderr, db_p->var, dump_flags);
1309 bitmap_print (stderr, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
1310 bitmap_print (stderr, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}\n");
1316 /* Return the set of blocks where variable VAR is defined and the blocks
1317 where VAR is live on entry (livein). Return NULL, if no entry is
1318 found in DEF_BLOCKS. */
1320 static inline struct def_blocks_d *
1321 find_def_blocks_for (tree var)
1323 struct def_blocks_d dm;
1325 return (struct def_blocks_d *) htab_find (def_blocks, &dm);
1329 /* Return the set of blocks where variable VAR is defined and the blocks
1330 where VAR is live on entry (livein). If no entry is found in
1331 DEF_BLOCKS, a new one is created and returned. */
1333 static inline struct def_blocks_d *
1334 get_def_blocks_for (tree var)
1336 struct def_blocks_d db, *db_p;
1340 slot = htab_find_slot (def_blocks, (void *) &db, INSERT);
1343 db_p = xmalloc (sizeof (*db_p));
1345 db_p->def_blocks = BITMAP_XMALLOC ();
1346 db_p->phi_blocks = BITMAP_XMALLOC ();
1347 db_p->livein_blocks = BITMAP_XMALLOC ();
1348 *slot = (void *) db_p;
1351 db_p = (struct def_blocks_d *) *slot;
1356 /* If a variable V in VARS_TO_RENAME is a pointer, the renaming
1357 process will cause us to lose the name memory tags that may have
1358 been associated with the various SSA_NAMEs of V. This means that
1359 the variables aliased to those name tags also need to be renamed
1362 FIXME 1- We should either have a better scheme for renaming
1363 pointers that doesn't lose name tags or re-run alias
1364 analysis to recover points-to information.
1366 2- Currently we just invalidate *all* the name tags. This
1367 should be more selective. */
1370 invalidate_name_tags (bitmap vars_to_rename)
1373 bool rename_name_tags_p;
1376 rename_name_tags_p = false;
1377 EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i, bi)
1379 if (POINTER_TYPE_P (TREE_TYPE (referenced_var (i))))
1381 rename_name_tags_p = true;
1386 if (rename_name_tags_p)
1387 for (i = 0; i < num_referenced_vars; i++)
1389 var_ann_t ann = var_ann (referenced_var (i));
1391 if (ann->mem_tag_kind == NAME_TAG)
1394 varray_type may_aliases = ann->may_aliases;
1396 bitmap_set_bit (vars_to_rename, ann->uid);
1397 if (ann->may_aliases)
1398 for (j = 0; j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
1400 tree var = VARRAY_TREE (may_aliases, j);
1401 bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1407 /* Rewrite the actual blocks, statements, and phi arguments, to be in SSA
1408 form. FIX_VIRTUAL_PHIS is true if we should only be fixing up virtual
1409 phi arguments, instead of adding new phi arguments for just added phi
1414 rewrite_blocks (bool fix_virtual_phis)
1416 struct dom_walk_data walk_data;
1418 /* Rewrite all the basic blocks in the program. */
1419 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
1421 /* Setup callbacks for the generic dominator tree walker. */
1422 walk_data.walk_stmts_backward = false;
1423 walk_data.dom_direction = CDI_DOMINATORS;
1424 walk_data.initialize_block_local_data = NULL;
1425 walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
1426 walk_data.before_dom_children_walk_stmts = rewrite_stmt;
1427 walk_data.before_dom_children_after_stmts = NULL;
1428 if (!fix_virtual_phis)
1429 walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
1431 walk_data.before_dom_children_after_stmts = rewrite_virtual_phi_arguments;
1433 walk_data.after_dom_children_before_stmts = NULL;
1434 walk_data.after_dom_children_walk_stmts = NULL;
1435 walk_data.after_dom_children_after_stmts = rewrite_finalize_block;
1436 walk_data.global_data = NULL;
1437 walk_data.block_local_data_size = 0;
1439 block_defs_stack = VEC_alloc (tree_on_heap, 10);
1441 /* Initialize the dominator walker. */
1442 init_walk_dominator_tree (&walk_data);
1444 /* Recursively walk the dominator tree rewriting each statement in
1445 each basic block. */
1446 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1448 /* Finalize the dominator walker. */
1449 fini_walk_dominator_tree (&walk_data);
1451 htab_delete (def_blocks);
1453 VEC_free (tree_on_heap, block_defs_stack);
1454 block_defs_stack = NULL;
1456 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
1459 /* Mark the definition site blocks for each variable, so that we know where
1460 the variable is actually live. */
1463 mark_def_site_blocks (void)
1466 struct dom_walk_data walk_data;
1467 struct mark_def_sites_global_data mark_def_sites_global_data;
1469 /* Allocate memory for the DEF_BLOCKS hash table. */
1470 def_blocks = htab_create (VARRAY_ACTIVE_SIZE (referenced_vars),
1471 def_blocks_hash, def_blocks_eq, def_blocks_free);
1473 for (i = 0; i < num_referenced_vars; i++)
1474 set_current_def (referenced_var (i), NULL_TREE);
1476 /* Ensure that the dominance information is OK. */
1477 calculate_dominance_info (CDI_DOMINATORS);
1480 /* Setup callbacks for the generic dominator tree walker to find and
1481 mark definition sites. */
1482 walk_data.walk_stmts_backward = false;
1483 walk_data.dom_direction = CDI_DOMINATORS;
1484 walk_data.initialize_block_local_data = NULL;
1485 walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block;
1486 walk_data.before_dom_children_walk_stmts = mark_def_sites;
1487 walk_data.before_dom_children_after_stmts = NULL;
1488 walk_data.after_dom_children_before_stmts = NULL;
1489 walk_data.after_dom_children_walk_stmts = NULL;
1490 walk_data.after_dom_children_after_stmts = NULL;
1492 /* Notice that this bitmap is indexed using variable UIDs, so it must be
1493 large enough to accommodate all the variables referenced in the
1494 function, not just the ones we are renaming. */
1495 mark_def_sites_global_data.kills = sbitmap_alloc (num_referenced_vars);
1496 walk_data.global_data = &mark_def_sites_global_data;
1498 /* We do not have any local data. */
1499 walk_data.block_local_data_size = 0;
1501 /* Initialize the dominator walker. */
1502 init_walk_dominator_tree (&walk_data);
1504 /* Recursively walk the dominator tree. */
1505 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1507 /* Finalize the dominator walker. */
1508 fini_walk_dominator_tree (&walk_data);
1510 /* We no longer need this bitmap, clear and free it. */
1511 sbitmap_free (mark_def_sites_global_data.kills);
1514 /* Main entry point into the SSA builder. The renaming process
1515 proceeds in five main phases:
1517 1- If VARS_TO_RENAME has any entries, any existing PHI nodes for
1518 those variables are removed from the flow graph so that they can
1521 2- Compute dominance frontier and immediate dominators, needed to
1522 insert PHI nodes and rename the function in dominator tree
1525 3- Find and mark all the blocks that define variables
1526 (mark_def_site_blocks).
1528 4- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
1530 5- Rename all the blocks (rewrite_blocks) and statements in the program.
1532 Steps 3 and 5 are done using the dominator tree walker
1533 (walk_dominator_tree).
1535 ALL is true if all variables should be renamed (otherwise just those
1536 mentioned in vars_to_rename are taken into account). */
1539 rewrite_into_ssa (bool all)
1543 bitmap old_vars_to_rename = vars_to_rename;
1545 timevar_push (TV_TREE_SSA_OTHER);
1548 vars_to_rename = NULL;
1551 /* Initialize the array of variables to rename. */
1552 gcc_assert (vars_to_rename);
1554 if (bitmap_empty_p (vars_to_rename))
1556 timevar_pop (TV_TREE_SSA_OTHER);
1560 invalidate_name_tags (vars_to_rename);
1562 /* Now remove all the existing PHI nodes (if any) for the variables
1563 that we are about to rename into SSA. */
1564 remove_all_phi_nodes_for (vars_to_rename);
1567 mark_def_site_blocks ();
1569 /* Initialize dominance frontier and immediate dominator bitmaps.
1570 Also count the number of predecessors for each block. Doing so
1571 can save significant time during PHI insertion for large graphs. */
1572 dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
1574 dfs[bb->index] = BITMAP_XMALLOC ();
1576 /* Compute dominance frontiers. */
1577 compute_dominance_frontiers (dfs);
1579 /* Insert PHI nodes at dominance frontiers of definition blocks. */
1580 insert_phi_nodes (dfs, NULL);
1582 rewrite_blocks (false);
1584 /* Debugging dumps. */
1585 if (dump_file && (dump_flags & TDF_STATS))
1587 dump_dfa_stats (dump_file);
1588 dump_tree_ssa_stats (dump_file);
1591 /* Free allocated memory. */
1593 BITMAP_XFREE (dfs[bb->index]);
1596 vars_to_rename = old_vars_to_rename;
1597 timevar_pop (TV_TREE_SSA_OTHER);
1600 /* Rewrite the def-def chains so that they have the correct reaching
1604 rewrite_def_def_chains (void)
1606 /* Ensure that the dominance information is OK. */
1607 calculate_dominance_info (CDI_DOMINATORS);
1608 mark_def_site_blocks ();
1609 rewrite_blocks (true);
1612 /* The marked ssa names may have more than one definition;
1613 add phi nodes and rewrite them to fix this. */
1616 rewrite_ssa_into_ssa (void)
1620 struct dom_walk_data walk_data;
1621 struct mark_def_sites_global_data mark_def_sites_global_data;
1623 sbitmap snames_to_rename;
1628 if (!any_marked_for_rewrite_p ())
1630 to_rename = marked_ssa_names ();
1632 timevar_push (TV_TREE_SSA_OTHER);
1634 /* Allocate memory for the DEF_BLOCKS hash table. */
1635 def_blocks = htab_create (num_ssa_names,
1636 def_blocks_hash, def_blocks_eq, def_blocks_free);
1638 /* Initialize dominance frontier and immediate dominator bitmaps.
1639 Also count the number of predecessors for each block. Doing so
1640 can save significant time during PHI insertion for large graphs. */
1641 dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
1643 dfs[bb->index] = BITMAP_XMALLOC ();
1645 /* Ensure that the dominance information is OK. */
1646 calculate_dominance_info (CDI_DOMINATORS);
1648 /* Compute dominance frontiers. */
1649 compute_dominance_frontiers (dfs);
1651 /* Setup callbacks for the generic dominator tree walker to find and
1652 mark definition sites. */
1653 walk_data.walk_stmts_backward = false;
1654 walk_data.dom_direction = CDI_DOMINATORS;
1655 walk_data.initialize_block_local_data = NULL;
1656 walk_data.before_dom_children_before_stmts
1657 = ssa_mark_def_sites_initialize_block;
1658 walk_data.before_dom_children_walk_stmts = ssa_mark_def_sites;
1659 walk_data.before_dom_children_after_stmts = ssa_mark_phi_uses;
1660 walk_data.after_dom_children_before_stmts = NULL;
1661 walk_data.after_dom_children_walk_stmts = NULL;
1662 walk_data.after_dom_children_after_stmts = NULL;
1664 snames_to_rename = sbitmap_alloc (num_ssa_names);
1665 sbitmap_zero (snames_to_rename);
1666 EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, bi)
1668 SET_BIT (snames_to_rename, i);
1671 mark_def_sites_global_data.kills = sbitmap_alloc (num_ssa_names);
1672 mark_def_sites_global_data.names_to_rename = snames_to_rename;
1673 walk_data.global_data = &mark_def_sites_global_data;
1675 block_defs_stack = VEC_alloc (tree_on_heap, 10);
1677 /* We do not have any local data. */
1678 walk_data.block_local_data_size = 0;
1680 /* Initialize the dominator walker. */
1681 init_walk_dominator_tree (&walk_data);
1683 /* Recursively walk the dominator tree. */
1684 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1686 /* Finalize the dominator walker. */
1687 fini_walk_dominator_tree (&walk_data);
1689 /* We no longer need this bitmap, clear and free it. */
1690 sbitmap_free (mark_def_sites_global_data.kills);
1692 for (i = 1; i < num_ssa_names; i++)
1694 set_current_def (ssa_name (i), NULL_TREE);
1696 /* Insert PHI nodes at dominance frontiers of definition blocks. */
1697 insert_phi_nodes (dfs, to_rename);
1699 /* Rewrite all the basic blocks in the program. */
1700 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
1702 /* Setup callbacks for the generic dominator tree walker. */
1703 walk_data.walk_stmts_backward = false;
1704 walk_data.dom_direction = CDI_DOMINATORS;
1705 walk_data.initialize_block_local_data = NULL;
1706 walk_data.before_dom_children_before_stmts = ssa_rewrite_initialize_block;
1707 walk_data.before_dom_children_walk_stmts = ssa_rewrite_stmt;
1708 walk_data.before_dom_children_after_stmts = ssa_rewrite_phi_arguments;
1709 walk_data.after_dom_children_before_stmts = NULL;
1710 walk_data.after_dom_children_walk_stmts = NULL;
1711 walk_data.after_dom_children_after_stmts = ssa_rewrite_finalize_block;
1712 walk_data.global_data = snames_to_rename;
1713 walk_data.block_local_data_size = 0;
1715 /* Initialize the dominator walker. */
1716 init_walk_dominator_tree (&walk_data);
1718 /* Recursively walk the dominator tree rewriting each statement in
1719 each basic block. */
1720 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1722 /* Finalize the dominator walker. */
1723 fini_walk_dominator_tree (&walk_data);
1725 unmark_all_for_rewrite ();
1727 EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, bi)
1729 release_ssa_name (ssa_name (i));
1732 sbitmap_free (snames_to_rename);
1734 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
1736 /* Debugging dumps. */
1737 if (dump_file && (dump_flags & TDF_STATS))
1739 dump_dfa_stats (dump_file);
1740 dump_tree_ssa_stats (dump_file);
1743 /* Free allocated memory. */
1745 BITMAP_XFREE (dfs[bb->index]);
1748 htab_delete (def_blocks);
1750 for (i = 1; i < num_ssa_names; i++)
1752 name = ssa_name (i);
1753 if (!name || !SSA_NAME_AUX (name))
1756 free (SSA_NAME_AUX (name));
1757 SSA_NAME_AUX (name) = NULL;
1760 BITMAP_XFREE (to_rename);
1762 VEC_free (tree_on_heap, block_defs_stack);
1763 block_defs_stack = NULL;
1764 timevar_pop (TV_TREE_SSA_OTHER);
1767 /* Rewrites all variables into ssa. */
1770 rewrite_all_into_ssa (void)
1772 rewrite_into_ssa (true);
1775 struct tree_opt_pass pass_build_ssa =
1779 rewrite_all_into_ssa, /* execute */
1782 0, /* static_pass_number */
1784 PROP_cfg | PROP_referenced_vars, /* properties_required */
1785 PROP_ssa, /* properties_provided */
1786 0, /* properties_destroyed */
1787 0, /* todo_flags_start */
1788 TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */