1 /* Rewrite a program in Normal form into SSA.
2 Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
30 #include "langhooks.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
37 #include "diagnostic.h"
39 #include "tree-flow.h"
40 #include "tree-gimple.h"
41 #include "tree-inline.h"
45 #include "tree-dump.h"
46 #include "tree-pass.h"
51 /* This file builds the SSA form for a function as described in:
52 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
53 Computing Static Single Assignment Form and the Control Dependence
54 Graph. ACM Transactions on Programming Languages and Systems,
55 13(4):451-490, October 1991. */
58 /* Structure to map a variable VAR to the set of blocks that contain
59 definitions for VAR. */
65 /* Blocks that contain definitions of VAR. Bit I will be set if the
66 Ith block contains a definition of VAR. */
69 /* Blocks that contain a phi node for VAR. */
72 /* Blocks where VAR is live-on-entry. Similar semantics as
77 /* Each entry in DEF_BLOCKS contains an element of type STRUCT
78 DEF_BLOCKS_D, mapping a variable VAR to a bitmap describing all the
79 basic blocks where VAR is defined (assigned a new value). It also
80 contains a bitmap of all the blocks where VAR is live-on-entry
81 (i.e., there is a use of VAR in block B without a preceding
82 definition in B). The live-on-entry information is used when
83 computing PHI pruning heuristics. */
84 static htab_t def_blocks;
86 /* Stack of trees used to restore the global currdefs to its original
87 state after completing rewriting of a block and its dominator children.
89 This varray is used in two contexts. The first is rewriting of _DECL
90 nodes into SSA_NAMEs. In that context it's elements have the
93 An SSA_NAME indicates that the current definition of the underlying
94 variable should be set to the given SSA_NAME.
96 A _DECL node indicates that the underlying variable has no current
99 A NULL node is used to mark the last node associated with the
103 This varray is also used when rewriting an SSA_NAME which has multiple
104 definition sites into multiple SSA_NAMEs. In that context entries come
107 The top entry is an SSA_NAME and the top-1 entry is the
108 current value for that SSA_NAME.
110 A NULL node at the top entry is used to mark the last node associated
111 with the current block. */
112 static VEC(tree_on_heap) *block_defs_stack;
114 /* FIXME: The other stacks should also be VEC(tree_on_heap). */
116 /* Global data to attach to the main dominator walk structure. */
117 struct mark_def_sites_global_data
119 /* This sbitmap contains the variables which are set before they
120 are used in a basic block. We keep it as a global variable
121 solely to avoid the overhead of allocating and deallocating
125 /* Bitmap of names to rename. */
126 sbitmap names_to_rename;
129 /* Information stored for ssa names. */
133 /* This field indicates whether or not the variable may need PHI nodes.
134 See the enum's definition for more detailed information about the
136 ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
138 /* The actual definition of the ssa name. */
142 /* Local functions. */
143 static void rewrite_finalize_block (struct dom_walk_data *, basic_block);
144 static void rewrite_initialize_block (struct dom_walk_data *, basic_block);
145 static void rewrite_add_phi_arguments (struct dom_walk_data *, basic_block);
146 static void mark_def_sites (struct dom_walk_data *walk_data,
147 basic_block bb, block_stmt_iterator);
148 static void mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
150 static void set_def_block (tree, basic_block, bool, bool);
151 static void set_livein_block (tree, basic_block);
152 static bool prepare_use_operand_for_rename (use_operand_p, size_t *uid_p);
153 static bool prepare_def_operand_for_rename (tree def, size_t *uid_p);
154 static void insert_phi_nodes (bitmap *, bitmap);
155 static void rewrite_stmt (struct dom_walk_data *, basic_block,
156 block_stmt_iterator);
157 static inline void rewrite_operand (use_operand_p);
158 static void insert_phi_nodes_for (tree, bitmap *, varray_type *);
159 static tree get_reaching_def (tree);
160 static hashval_t def_blocks_hash (const void *);
161 static int def_blocks_eq (const void *, const void *);
162 static void def_blocks_free (void *);
163 static int debug_def_blocks_r (void **, void *);
164 static inline struct def_blocks_d *get_def_blocks_for (tree);
165 static inline struct def_blocks_d *find_def_blocks_for (tree);
166 static void htab_statistics (FILE *, htab_t);
168 /* Get the information associated with NAME. */
170 static inline struct ssa_name_info *
171 get_ssa_name_ann (tree name)
173 if (!SSA_NAME_AUX (name))
174 SSA_NAME_AUX (name) = xcalloc (1, sizeof (struct ssa_name_info));
176 return SSA_NAME_AUX (name);
179 /* Gets phi_state field for VAR. */
181 static inline enum need_phi_state
182 get_phi_state (tree var)
184 if (TREE_CODE (var) == SSA_NAME)
185 return get_ssa_name_ann (var)->need_phi_state;
187 return var_ann (var)->need_phi_state;
190 /* Sets phi_state field for VAR to STATE. */
193 set_phi_state (tree var, enum need_phi_state state)
195 if (TREE_CODE (var) == SSA_NAME)
196 get_ssa_name_ann (var)->need_phi_state = state;
198 var_ann (var)->need_phi_state = state;
201 /* Return the current definition for VAR. */
204 get_current_def (tree var)
206 if (TREE_CODE (var) == SSA_NAME)
207 return get_ssa_name_ann (var)->current_def;
209 return var_ann (var)->current_def;
212 /* Sets current definition of VAR to DEF. */
215 set_current_def (tree var, tree def)
217 if (TREE_CODE (var) == SSA_NAME)
218 get_ssa_name_ann (var)->current_def = def;
220 var_ann (var)->current_def = def;
223 /* Compute global livein information given the set of blockx where
224 an object is locally live at the start of the block (LIVEIN)
225 and the set of blocks where the object is defined (DEF_BLOCKS).
227 Note: This routine augments the existing local livein information
228 to include global livein (i.e., it modifies the underlying bitmap
232 compute_global_livein (bitmap livein, bitmap def_blocks)
234 basic_block bb, *worklist, *tos;
239 = (basic_block *) xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
241 EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
243 *tos++ = BASIC_BLOCK (i);
246 /* Iterate until the worklist is empty. */
247 while (tos != worklist)
252 /* Pull a block off the worklist. */
255 /* For each predecessor block. */
256 FOR_EACH_EDGE (e, ei, bb->preds)
258 basic_block pred = e->src;
259 int pred_index = pred->index;
261 /* None of this is necessary for the entry block. */
262 if (pred != ENTRY_BLOCK_PTR
263 && ! bitmap_bit_p (livein, pred_index)
264 && ! bitmap_bit_p (def_blocks, pred_index))
267 bitmap_set_bit (livein, pred_index);
276 /* Block initialization routine for mark_def_sites. Clear the
277 KILLS bitmap at the start of each block. */
280 mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
281 basic_block bb ATTRIBUTE_UNUSED)
283 struct mark_def_sites_global_data *gd = walk_data->global_data;
284 sbitmap kills = gd->kills;
286 sbitmap_zero (kills);
289 /* Block initialization routine for mark_def_sites. Clear the
290 KILLS bitmap at the start of each block. */
293 ssa_mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
296 struct mark_def_sites_global_data *gd = walk_data->global_data;
297 sbitmap kills = gd->kills;
301 sbitmap_zero (kills);
303 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
305 def = PHI_RESULT (phi);
306 def_uid = SSA_NAME_VERSION (def);
308 if (!TEST_BIT (gd->names_to_rename, def_uid))
311 set_def_block (def, bb, true, true);
312 SET_BIT (kills, def_uid);
316 /* Marks ssa names used as arguments of phis at the end of BB. */
319 ssa_mark_phi_uses (struct dom_walk_data *walk_data, basic_block bb)
321 struct mark_def_sites_global_data *gd = walk_data->global_data;
322 sbitmap kills = gd->kills;
328 FOR_EACH_EDGE (e, ei, bb->succs)
330 if (e->dest == EXIT_BLOCK_PTR)
333 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
335 use = PHI_ARG_DEF_FROM_EDGE (phi, e);
336 if (TREE_CODE (use) != SSA_NAME)
339 uid = SSA_NAME_VERSION (use);
341 if (TEST_BIT (gd->names_to_rename, uid)
342 && !TEST_BIT (kills, uid))
343 set_livein_block (use, bb);
348 /* Call back for walk_dominator_tree used to collect definition sites
349 for every variable in the function. For every statement S in block
352 1- Variables defined by S in DEF_OPS(S) are marked in the bitmap
353 WALK_DATA->GLOBAL_DATA->KILLS.
355 2- If S uses a variable VAR and there is no preceding kill of VAR,
356 then it is marked in marked in the LIVEIN_BLOCKS bitmap
359 This information is used to determine which variables are live
360 across block boundaries to reduce the number of PHI nodes
364 mark_def_sites (struct dom_walk_data *walk_data,
366 block_stmt_iterator bsi)
368 struct mark_def_sites_global_data *gd = walk_data->global_data;
369 sbitmap kills = gd->kills;
376 /* Mark all the blocks that have definitions for each variable in the
377 VARS_TO_RENAME bitmap. */
378 stmt = bsi_stmt (bsi);
379 get_stmt_operands (stmt);
381 /* If a variable is used before being set, then the variable is live
382 across a block boundary, so mark it live-on-entry to BB. */
384 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE | SSA_OP_VMUSTDEFKILL)
386 if (prepare_use_operand_for_rename (use_p, &uid)
387 && !TEST_BIT (kills, uid))
388 set_livein_block (USE_FROM_PTR (use_p), bb);
391 /* Note that virtual definitions are irrelevant for computing KILLS
392 because a V_MAY_DEF does not constitute a killing definition of the
393 variable. However, the operand of a virtual definitions is a use
394 of the variable, so it may cause the variable to be considered
397 FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
399 if (prepare_use_operand_for_rename (use_p, &uid))
401 /* If we do not already have an SSA_NAME for our destination,
402 then set the destination to the source. */
403 if (TREE_CODE (DEF_FROM_PTR (def_p)) != SSA_NAME)
404 SET_DEF (def_p, USE_FROM_PTR (use_p));
406 set_livein_block (USE_FROM_PTR (use_p), bb);
407 set_def_block (DEF_FROM_PTR (def_p), bb, false, false);
411 /* Now process the virtual must-defs made by this statement. */
412 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF | SSA_OP_VMUSTDEF)
414 if (prepare_def_operand_for_rename (def, &uid))
416 set_def_block (def, bb, false, false);
417 SET_BIT (kills, uid);
423 /* Ditto, but works over ssa names. */
426 ssa_mark_def_sites (struct dom_walk_data *walk_data,
428 block_stmt_iterator bsi)
430 struct mark_def_sites_global_data *gd = walk_data->global_data;
431 sbitmap kills = gd->kills;
436 /* Mark all the blocks that have definitions for each variable in the
437 names_to_rename bitmap. */
438 stmt = bsi_stmt (bsi);
439 get_stmt_operands (stmt);
441 /* If a variable is used before being set, then the variable is live
442 across a block boundary, so mark it live-on-entry to BB. */
443 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
445 uid = SSA_NAME_VERSION (use);
447 if (TEST_BIT (gd->names_to_rename, uid)
448 && !TEST_BIT (kills, uid))
449 set_livein_block (use, bb);
452 /* Now process the definition made by this statement. Mark the
453 variables in KILLS. */
454 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
456 def_uid = SSA_NAME_VERSION (def);
458 if (TEST_BIT (gd->names_to_rename, def_uid))
460 set_def_block (def, bb, false, true);
461 SET_BIT (kills, def_uid);
466 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
467 VAR is defined by a phi node. SSA_P is true if we are called from
468 rewrite_ssa_into_ssa. */
471 set_def_block (tree var, basic_block bb, bool phi_p, bool ssa_p)
473 struct def_blocks_d *db_p;
474 enum need_phi_state state;
477 && TREE_CODE (var) == SSA_NAME)
478 var = SSA_NAME_VAR (var);
480 state = get_phi_state (var);
481 db_p = get_def_blocks_for (var);
483 /* Set the bit corresponding to the block where VAR is defined. */
484 bitmap_set_bit (db_p->def_blocks, bb->index);
486 bitmap_set_bit (db_p->phi_blocks, bb->index);
488 /* Keep track of whether or not we may need to insert phi nodes.
490 If we are in the UNKNOWN state, then this is the first definition
491 of VAR. Additionally, we have not seen any uses of VAR yet, so
492 we do not need a phi node for this variable at this time (i.e.,
493 transition to NEED_PHI_STATE_NO).
495 If we are in any other state, then we either have multiple definitions
496 of this variable occurring in different blocks or we saw a use of the
497 variable which was not dominated by the block containing the
498 definition(s). In this case we may need a PHI node, so enter
499 state NEED_PHI_STATE_MAYBE. */
500 if (state == NEED_PHI_STATE_UNKNOWN)
501 set_phi_state (var, NEED_PHI_STATE_NO);
503 set_phi_state (var, NEED_PHI_STATE_MAYBE);
507 /* Mark block BB as having VAR live at the entry to BB. */
510 set_livein_block (tree var, basic_block bb)
512 struct def_blocks_d *db_p;
513 enum need_phi_state state = get_phi_state (var);
515 db_p = get_def_blocks_for (var);
517 /* Set the bit corresponding to the block where VAR is live in. */
518 bitmap_set_bit (db_p->livein_blocks, bb->index);
520 /* Keep track of whether or not we may need to insert phi nodes.
522 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
523 by the single block containing the definition(s) of this variable. If
524 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
525 NEED_PHI_STATE_MAYBE. */
526 if (state == NEED_PHI_STATE_NO)
528 int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
530 if (def_block_index == -1
531 || ! dominated_by_p (CDI_DOMINATORS, bb,
532 BASIC_BLOCK (def_block_index)))
533 set_phi_state (var, NEED_PHI_STATE_MAYBE);
536 set_phi_state (var, NEED_PHI_STATE_MAYBE);
540 /* If the use operand pointed to by OP_P needs to be renamed, then strip away
541 any SSA_NAME wrapping the operand, set *UID_P to the underlying variable's
542 uid, and return true. Otherwise return false. If the operand was an
543 SSA_NAME, change it to the stripped name. */
546 prepare_use_operand_for_rename (use_operand_p op_p, size_t *uid_p)
548 tree use = USE_FROM_PTR (op_p);
549 tree var = (TREE_CODE (use) != SSA_NAME) ? use : SSA_NAME_VAR (use);
550 *uid_p = var_ann (var)->uid;
552 /* Ignore variables that don't need to be renamed. */
553 if (vars_to_rename && !bitmap_bit_p (vars_to_rename, *uid_p))
556 /* The variable needs to be renamed. If this is a use which already
557 has an SSA_NAME, then strip it off.
559 By not throwing away SSA_NAMEs on assignments, we avoid a lot of
560 useless churn of SSA_NAMEs without having to overly complicate the
562 if (TREE_CODE (use) == SSA_NAME)
568 /* If the def variable DEF needs to be renamed, then strip away any SSA_NAME
569 wrapping the operand, set *UID_P to the underlying variable's uid and return
570 true. Otherwise return false. */
573 prepare_def_operand_for_rename (tree def, size_t *uid_p)
575 tree var = (TREE_CODE (def) != SSA_NAME) ? def : SSA_NAME_VAR (def);
576 *uid_p = var_ann (var)->uid;
578 /* Ignore variables that don't need to be renamed. */
579 if (vars_to_rename && !bitmap_bit_p (vars_to_rename, *uid_p))
585 /* Helper for insert_phi_nodes. If VAR needs PHI nodes, insert them
586 at the dominance frontier (DFS) of blocks defining VAR.
587 WORK_STACK is the varray used to implement the worklist of basic
591 void insert_phi_nodes_1 (tree var, bitmap *dfs, varray_type *work_stack)
593 if (get_phi_state (var) != NEED_PHI_STATE_NO)
594 insert_phi_nodes_for (var, dfs, work_stack);
597 /* Insert PHI nodes at the dominance frontier of blocks with variable
598 definitions. DFS contains the dominance frontier information for
599 the flowgraph. PHI nodes will only be inserted at the dominance
600 frontier of definition blocks for variables whose NEED_PHI_STATE
601 annotation is marked as ``maybe'' or ``unknown'' (computed by
602 mark_def_sites). If NAMES_TO_RENAME is not NULL, do the same but
603 for ssa name rewriting. */
606 insert_phi_nodes (bitmap *dfs, bitmap names_to_rename)
609 varray_type work_stack;
612 timevar_push (TV_TREE_INSERT_PHI_NODES);
614 /* Array WORK_STACK is a stack of CFG blocks. Each block that contains
615 an assignment or PHI node will be pushed to this stack. */
616 VARRAY_GENERIC_PTR_NOGC_INIT (work_stack, last_basic_block, "work_stack");
618 /* Iterate over all variables in VARS_TO_RENAME. For each variable, add
619 to the work list all the blocks that have a definition for the
620 variable. PHI nodes will be added to the dominance frontier blocks of
621 each definition block. */
624 EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
627 insert_phi_nodes_1 (ssa_name (i), dfs, &work_stack);
630 else if (vars_to_rename)
631 EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i, bi)
633 insert_phi_nodes_1 (referenced_var (i), dfs, &work_stack);
636 for (i = 0; i < num_referenced_vars; i++)
637 insert_phi_nodes_1 (referenced_var (i), dfs, &work_stack);
639 VARRAY_FREE (work_stack);
641 timevar_pop (TV_TREE_INSERT_PHI_NODES);
645 /* Perform a depth-first traversal of the dominator tree looking for
646 variables to rename. BB is the block where to start searching.
647 Renaming is a five step process:
649 1- Every definition made by PHI nodes at the start of the blocks is
650 registered as the current definition for the corresponding variable.
652 2- Every statement in BB is rewritten. USE and VUSE operands are
653 rewritten with their corresponding reaching definition. DEF and
654 VDEF targets are registered as new definitions.
656 3- All the PHI nodes in successor blocks of BB are visited. The
657 argument corresponding to BB is replaced with its current reaching
660 4- Recursively rewrite every dominator child block of BB.
662 5- Restore (in reverse order) the current reaching definition for every
663 new definition introduced in this block. This is done so that when
664 we return from the recursive call, all the current reaching
665 definitions are restored to the names that were valid in the
666 dominator parent of BB. */
668 /* SSA Rewriting Step 1. Initialization, create a block local stack
669 of reaching definitions for new SSA names produced in this block
670 (BLOCK_DEFS). Register new definitions for every PHI node in the
674 rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
679 if (dump_file && (dump_flags & TDF_DETAILS))
680 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
682 /* Mark the unwind point for this block. */
683 VEC_safe_push (tree_on_heap, block_defs_stack, NULL_TREE);
685 /* Step 1. Register new definitions for every PHI node in the block.
686 Conceptually, all the PHI nodes are executed in parallel and each PHI
687 node introduces a new version for the associated variable. */
688 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
690 tree result = PHI_RESULT (phi);
692 register_new_def (result, &block_defs_stack);
696 /* Register DEF (an SSA_NAME) to be a new definition for the original
697 ssa name VAR and push VAR's current reaching definition
698 into the stack pointed by BLOCK_DEFS_P. */
701 ssa_register_new_def (tree var, tree def)
705 /* If this variable is set in a single basic block and all uses are
706 dominated by the set(s) in that single basic block, then there is
707 nothing to do. TODO we should not be called at all, and just
708 keep the original name. */
709 if (get_phi_state (var) == NEED_PHI_STATE_NO)
711 set_current_def (var, def);
715 currdef = get_current_def (var);
717 /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
718 later used by the dominator tree callbacks to restore the reaching
719 definitions for all the variables defined in the block after a recursive
720 visit to all its immediately dominated blocks. */
721 VEC_safe_push (tree_on_heap, block_defs_stack, currdef);
722 VEC_safe_push (tree_on_heap, block_defs_stack, var);
724 /* Set the current reaching definition for VAR to be DEF. */
725 set_current_def (var, def);
728 /* Ditto, for rewriting ssa names. */
731 ssa_rewrite_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
734 sbitmap names_to_rename = walk_data->global_data;
739 if (dump_file && (dump_flags & TDF_DETAILS))
740 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
742 /* Mark the unwind point for this block. */
743 VEC_safe_push (tree_on_heap, block_defs_stack, NULL_TREE);
745 FOR_EACH_EDGE (e, ei, bb->preds)
746 if (e->flags & EDGE_ABNORMAL)
748 abnormal_phi = (e != NULL);
750 /* Step 1. Register new definitions for every PHI node in the block.
751 Conceptually, all the PHI nodes are executed in parallel and each PHI
752 node introduces a new version for the associated variable. */
753 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
755 tree result = PHI_RESULT (phi);
757 if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (result)))
759 new_name = duplicate_ssa_name (result, phi);
760 SET_PHI_RESULT (phi, new_name);
763 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
768 ssa_register_new_def (result, new_name);
772 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
773 PHI nodes. For every PHI node found, add a new argument containing the
774 current reaching definition for the variable and the edge through which
775 that definition is reaching the PHI node. */
778 rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
784 FOR_EACH_EDGE (e, ei, bb->succs)
788 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
792 /* If this PHI node has already been rewritten, then there is
793 nothing to do for this PHI or any following PHIs since we
794 always add new PHI nodes at the start of the PHI chain. */
795 if (PHI_REWRITTEN (phi))
798 currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
799 add_phi_arg (&phi, currdef, e);
804 /* Rewrite existing virtual PHI arguments so that they have the correct
805 reaching definitions. BB is the basic block whose successors contain the
806 phi nodes we want to add arguments for. */
809 rewrite_virtual_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
816 FOR_EACH_EDGE (e, ei, bb->succs)
820 if (e->dest == EXIT_BLOCK_PTR)
823 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
825 tree result = PHI_RESULT (phi);
826 op = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
828 if (is_gimple_reg (result)
829 || !bitmap_bit_p (vars_to_rename,
830 var_ann (SSA_NAME_VAR (result))->uid))
833 SET_USE (op, get_reaching_def (SSA_NAME_VAR (result)));
834 if (e->flags & EDGE_ABNORMAL)
835 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (op)) = 1;
840 /* Ditto, for ssa name rewriting. */
843 ssa_rewrite_phi_arguments (struct dom_walk_data *walk_data, basic_block bb)
846 sbitmap names_to_rename = walk_data->global_data;
850 FOR_EACH_EDGE (e, ei, bb->succs)
854 if (e->dest == EXIT_BLOCK_PTR)
857 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
859 op = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
860 if (TREE_CODE (USE_FROM_PTR (op)) != SSA_NAME)
863 if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (op))))
866 SET_USE (op, get_reaching_def (USE_FROM_PTR (op)));
867 if (e->flags & EDGE_ABNORMAL)
868 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (op)) = 1;
874 /* Similar to restore_vars_to_original_value, except that it restores
875 CURRDEFS to its original value. */
877 rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
878 basic_block bb ATTRIBUTE_UNUSED)
880 /* Restore CURRDEFS to its original state. */
881 while (VEC_length (tree_on_heap, block_defs_stack) > 0)
883 tree tmp = VEC_pop (tree_on_heap, block_defs_stack);
886 if (tmp == NULL_TREE)
889 /* If we recorded an SSA_NAME, then make the SSA_NAME the current
890 definition of its underlying variable. If we recorded anything
891 else, it must have been an _DECL node and its current reaching
892 definition must have been NULL. */
893 if (TREE_CODE (tmp) == SSA_NAME)
896 var = SSA_NAME_VAR (saved_def);
904 set_current_def (var, saved_def);
908 /* Ditto, for rewriting ssa names. */
911 ssa_rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
912 basic_block bb ATTRIBUTE_UNUSED)
915 /* Step 5. Restore the current reaching definition for each variable
916 referenced in the block (in reverse order). */
917 while (VEC_length (tree_on_heap, block_defs_stack) > 0)
919 tree var = VEC_pop (tree_on_heap, block_defs_stack);
925 saved_def = VEC_pop (tree_on_heap, block_defs_stack);
927 set_current_def (var, saved_def);
931 /* Dump SSA information to FILE. */
934 dump_tree_ssa (FILE *file)
938 = lang_hooks.decl_printable_name (current_function_decl, 2);
940 fprintf (file, "SSA information for %s\n\n", funcname);
944 dump_bb (bb, file, 0);
946 print_generic_stmt (file, phi_nodes (bb), dump_flags);
947 fputs ("\n\n", file);
952 /* Dump SSA information to stderr. */
955 debug_tree_ssa (void)
957 dump_tree_ssa (stderr);
961 /* Dump SSA statistics on FILE. */
964 dump_tree_ssa_stats (FILE *file)
966 fprintf (file, "\nHash table statistics:\n");
968 fprintf (file, " def_blocks: ");
969 htab_statistics (file, def_blocks);
971 fprintf (file, "\n");
975 /* Dump SSA statistics on stderr. */
978 debug_tree_ssa_stats (void)
980 dump_tree_ssa_stats (stderr);
984 /* Dump statistics for the hash table HTAB. */
987 htab_statistics (FILE *file, htab_t htab)
989 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
990 (long) htab_size (htab),
991 (long) htab_elements (htab),
992 htab_collisions (htab));
996 /* Insert PHI nodes for variable VAR using the dominance frontier
997 information given in DFS. WORK_STACK is the varray used to
998 implement the worklist of basic blocks. */
1001 insert_phi_nodes_for (tree var, bitmap *dfs, varray_type *work_stack)
1003 struct def_blocks_d *def_map;
1004 bitmap phi_insertion_points;
1011 def_map = find_def_blocks_for (var);
1012 if (def_map == NULL)
1015 phi_insertion_points = BITMAP_XMALLOC ();
1017 EXECUTE_IF_SET_IN_BITMAP (def_map->def_blocks, 0, bb_index, bi)
1019 VARRAY_PUSH_GENERIC_PTR_NOGC (*work_stack, BASIC_BLOCK (bb_index));
1022 /* Pop a block off the worklist, add every block that appears in
1023 the original block's dfs that we have not already processed to
1024 the worklist. Iterate until the worklist is empty. Blocks
1025 which are added to the worklist are potential sites for
1028 The iteration step could be done during PHI insertion just as
1029 easily. We do it here for historical reasons -- we used to have
1030 a heuristic which used the potential PHI insertion points to
1031 determine if fully pruned or semi pruned SSA form was appropriate.
1033 We now always use fully pruned SSA form. */
1034 while (VARRAY_ACTIVE_SIZE (*work_stack) > 0)
1039 bb = VARRAY_TOP_GENERIC_PTR_NOGC (*work_stack);
1040 bb_index = bb->index;
1042 VARRAY_POP (*work_stack);
1044 EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index],
1045 phi_insertion_points,
1048 basic_block bb = BASIC_BLOCK (dfs_index);
1050 VARRAY_PUSH_GENERIC_PTR_NOGC (*work_stack, bb);
1051 bitmap_set_bit (phi_insertion_points, dfs_index);
1055 /* Remove the blocks where we already have the phis. */
1056 bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
1058 /* Now compute global livein for this variable. Note this modifies
1059 def_map->livein_blocks. */
1060 compute_global_livein (def_map->livein_blocks, def_map->def_blocks);
1062 /* And insert the PHI nodes. */
1063 EXECUTE_IF_AND_IN_BITMAP (phi_insertion_points, def_map->livein_blocks,
1066 bb = BASIC_BLOCK (bb_index);
1068 phi = create_phi_node (var, bb);
1070 /* If we are rewriting ssa names, add also the phi arguments. */
1071 if (TREE_CODE (var) == SSA_NAME)
1074 FOR_EACH_EDGE (e, ei, bb->preds)
1075 add_phi_arg (&phi, var, e);
1079 BITMAP_XFREE (phi_insertion_points);
1082 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1083 the block with its immediate reaching definitions. Update the current
1084 definition of a variable when a new real or virtual definition is found. */
1087 rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1088 basic_block bb ATTRIBUTE_UNUSED,
1089 block_stmt_iterator si)
1093 use_operand_p use_p;
1094 def_operand_p def_p;
1097 stmt = bsi_stmt (si);
1098 ann = stmt_ann (stmt);
1100 if (dump_file && (dump_flags & TDF_DETAILS))
1102 fprintf (dump_file, "Renaming statement ");
1103 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1104 fprintf (dump_file, "\n");
1107 /* We have just scanned the code for operands. No statement should
1109 gcc_assert (!ann->modified);
1111 /* Step 1. Rewrite USES and VUSES in the statement. */
1112 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
1113 rewrite_operand (use_p);
1115 /* Step 2. Register the statement's DEF and VDEF operands. */
1116 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1118 if (TREE_CODE (DEF_FROM_PTR (def_p)) != SSA_NAME)
1119 SET_DEF (def_p, make_ssa_name (DEF_FROM_PTR (def_p), stmt));
1121 /* FIXME: We shouldn't be registering new defs if the variable
1122 doesn't need to be renamed. */
1123 register_new_def (DEF_FROM_PTR (def_p), &block_defs_stack);
1127 /* Ditto, for rewriting ssa names. */
1130 ssa_rewrite_stmt (struct dom_walk_data *walk_data,
1131 basic_block bb ATTRIBUTE_UNUSED,
1132 block_stmt_iterator si)
1137 use_operand_p use_p;
1138 def_operand_p def_p;
1139 sbitmap names_to_rename = walk_data->global_data;
1141 stmt = bsi_stmt (si);
1142 ann = stmt_ann (stmt);
1144 if (dump_file && (dump_flags & TDF_DETAILS))
1146 fprintf (dump_file, "Renaming statement ");
1147 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1148 fprintf (dump_file, "\n");
1151 /* We have just scanned the code for operands. No statement should
1153 gcc_assert (!ann->modified);
1155 /* Step 1. Rewrite USES and VUSES in the statement. */
1156 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
1158 if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (use_p))))
1159 SET_USE (use_p, get_reaching_def (USE_FROM_PTR (use_p)));
1162 /* Step 2. Register the statement's DEF and VDEF operands. */
1163 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1165 var = DEF_FROM_PTR (def_p);
1167 if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (var)))
1170 SET_DEF (def_p, duplicate_ssa_name (var, stmt));
1171 ssa_register_new_def (var, DEF_FROM_PTR (def_p));
1175 /* Replace the operand pointed by OP_P with its immediate reaching
1179 rewrite_operand (use_operand_p op_p)
1181 if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
1182 SET_USE (op_p, get_reaching_def (USE_FROM_PTR (op_p)));
1185 /* Register DEF (an SSA_NAME) to be a new definition for its underlying
1186 variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition
1187 into the stack pointed by BLOCK_DEFS_P. */
1190 register_new_def (tree def, VEC (tree_on_heap) **block_defs_p)
1192 tree var = SSA_NAME_VAR (def);
1195 /* If this variable is set in a single basic block and all uses are
1196 dominated by the set(s) in that single basic block, then there is
1197 no reason to record anything for this variable in the block local
1198 definition stacks. Doing so just wastes time and memory.
1200 This is the same test to prune the set of variables which may
1201 need PHI nodes. So we just use that information since it's already
1202 computed and available for us to use. */
1203 if (get_phi_state (var) == NEED_PHI_STATE_NO)
1205 set_current_def (var, def);
1209 currdef = get_current_def (var);
1211 /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
1212 later used by the dominator tree callbacks to restore the reaching
1213 definitions for all the variables defined in the block after a recursive
1214 visit to all its immediately dominated blocks. If there is no current
1215 reaching definition, then just record the underlying _DECL node. */
1216 VEC_safe_push (tree_on_heap, *block_defs_p, currdef ? currdef : var);
1218 /* Set the current reaching definition for VAR to be DEF. */
1219 set_current_def (var, def);
1222 /* Return the current definition for variable VAR. If none is found,
1223 create a new SSA name to act as the zeroth definition for VAR. If VAR
1224 is call clobbered and there exists a more recent definition of
1225 GLOBAL_VAR, return the definition for GLOBAL_VAR. This means that VAR
1226 has been clobbered by a function call since its last assignment. */
1229 get_reaching_def (tree var)
1231 tree default_d, currdef_var, avar;
1233 /* Lookup the current reaching definition for VAR. */
1234 default_d = NULL_TREE;
1235 currdef_var = get_current_def (var);
1237 /* If there is no reaching definition for VAR, create and register a
1238 default definition for it (if needed). */
1239 if (currdef_var == NULL_TREE)
1241 if (TREE_CODE (var) == SSA_NAME)
1242 avar = SSA_NAME_VAR (var);
1246 default_d = default_def (avar);
1247 if (default_d == NULL_TREE)
1249 default_d = make_ssa_name (avar, build_empty_stmt ());
1250 set_default_def (avar, default_d);
1252 set_current_def (var, default_d);
1255 /* Return the current reaching definition for VAR, or the default
1256 definition, if we had to create one. */
1257 return (currdef_var) ? currdef_var : default_d;
1261 /* Hashing and equality functions for DEF_BLOCKS. */
1264 def_blocks_hash (const void *p)
1266 return htab_hash_pointer
1267 ((const void *)((const struct def_blocks_d *)p)->var);
1271 def_blocks_eq (const void *p1, const void *p2)
1273 return ((const struct def_blocks_d *)p1)->var
1274 == ((const struct def_blocks_d *)p2)->var;
1277 /* Free memory allocated by one entry in DEF_BLOCKS. */
1280 def_blocks_free (void *p)
1282 struct def_blocks_d *entry = p;
1283 BITMAP_XFREE (entry->def_blocks);
1284 BITMAP_XFREE (entry->phi_blocks);
1285 BITMAP_XFREE (entry->livein_blocks);
1290 /* Dump the DEF_BLOCKS hash table on stderr. */
1293 debug_def_blocks (void)
1295 htab_traverse (def_blocks, debug_def_blocks_r, NULL);
1298 /* Callback for htab_traverse to dump the DEF_BLOCKS hash table. */
1301 debug_def_blocks_r (void **slot, void *data ATTRIBUTE_UNUSED)
1303 struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
1305 fprintf (stderr, "VAR: ");
1306 print_generic_expr (stderr, db_p->var, dump_flags);
1307 bitmap_print (stderr, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
1308 bitmap_print (stderr, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}\n");
1314 /* Return the set of blocks where variable VAR is defined and the blocks
1315 where VAR is live on entry (livein). Return NULL, if no entry is
1316 found in DEF_BLOCKS. */
1318 static inline struct def_blocks_d *
1319 find_def_blocks_for (tree var)
1321 struct def_blocks_d dm;
1323 return (struct def_blocks_d *) htab_find (def_blocks, &dm);
1327 /* Return the set of blocks where variable VAR is defined and the blocks
1328 where VAR is live on entry (livein). If no entry is found in
1329 DEF_BLOCKS, a new one is created and returned. */
1331 static inline struct def_blocks_d *
1332 get_def_blocks_for (tree var)
1334 struct def_blocks_d db, *db_p;
1338 slot = htab_find_slot (def_blocks, (void *) &db, INSERT);
1341 db_p = xmalloc (sizeof (*db_p));
1343 db_p->def_blocks = BITMAP_XMALLOC ();
1344 db_p->phi_blocks = BITMAP_XMALLOC ();
1345 db_p->livein_blocks = BITMAP_XMALLOC ();
1346 *slot = (void *) db_p;
1349 db_p = (struct def_blocks_d *) *slot;
1354 /* If a variable V in VARS_TO_RENAME is a pointer, the renaming
1355 process will cause us to lose the name memory tags that may have
1356 been associated with the various SSA_NAMEs of V. This means that
1357 the variables aliased to those name tags also need to be renamed
1360 FIXME 1- We should either have a better scheme for renaming
1361 pointers that doesn't lose name tags or re-run alias
1362 analysis to recover points-to information.
1364 2- Currently we just invalidate *all* the name tags. This
1365 should be more selective. */
1368 invalidate_name_tags (bitmap vars_to_rename)
1371 bool rename_name_tags_p;
1374 rename_name_tags_p = false;
1375 EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i, bi)
1377 if (POINTER_TYPE_P (TREE_TYPE (referenced_var (i))))
1379 rename_name_tags_p = true;
1384 if (rename_name_tags_p)
1385 for (i = 0; i < num_referenced_vars; i++)
1387 var_ann_t ann = var_ann (referenced_var (i));
1389 if (ann->mem_tag_kind == NAME_TAG)
1392 varray_type may_aliases = ann->may_aliases;
1394 bitmap_set_bit (vars_to_rename, ann->uid);
1395 if (ann->may_aliases)
1396 for (j = 0; j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
1398 tree var = VARRAY_TREE (may_aliases, j);
1399 bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1405 /* Rewrite the actual blocks, statements, and phi arguments, to be in SSA
1406 form. FIX_VIRTUAL_PHIS is true if we should only be fixing up virtual
1407 phi arguments, instead of adding new phi arguments for just added phi
1412 rewrite_blocks (bool fix_virtual_phis)
1414 struct dom_walk_data walk_data;
1416 /* Rewrite all the basic blocks in the program. */
1417 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
1419 /* Setup callbacks for the generic dominator tree walker. */
1420 walk_data.walk_stmts_backward = false;
1421 walk_data.dom_direction = CDI_DOMINATORS;
1422 walk_data.initialize_block_local_data = NULL;
1423 walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
1424 walk_data.before_dom_children_walk_stmts = rewrite_stmt;
1425 walk_data.before_dom_children_after_stmts = NULL;
1426 if (!fix_virtual_phis)
1427 walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
1429 walk_data.before_dom_children_after_stmts = rewrite_virtual_phi_arguments;
1431 walk_data.after_dom_children_before_stmts = NULL;
1432 walk_data.after_dom_children_walk_stmts = NULL;
1433 walk_data.after_dom_children_after_stmts = rewrite_finalize_block;
1434 walk_data.global_data = NULL;
1435 walk_data.block_local_data_size = 0;
1437 block_defs_stack = VEC_alloc (tree_on_heap, 10);
1439 /* Initialize the dominator walker. */
1440 init_walk_dominator_tree (&walk_data);
1442 /* Recursively walk the dominator tree rewriting each statement in
1443 each basic block. */
1444 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1446 /* Finalize the dominator walker. */
1447 fini_walk_dominator_tree (&walk_data);
1449 htab_delete (def_blocks);
1451 VEC_free (tree_on_heap, block_defs_stack);
1452 block_defs_stack = NULL;
1454 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
1457 /* Mark the definition site blocks for each variable, so that we know where
1458 the variable is actually live. */
1461 mark_def_site_blocks (void)
1464 struct dom_walk_data walk_data;
1465 struct mark_def_sites_global_data mark_def_sites_global_data;
1467 /* Allocate memory for the DEF_BLOCKS hash table. */
1468 def_blocks = htab_create (VARRAY_ACTIVE_SIZE (referenced_vars),
1469 def_blocks_hash, def_blocks_eq, def_blocks_free);
1471 for (i = 0; i < num_referenced_vars; i++)
1472 set_current_def (referenced_var (i), NULL_TREE);
1474 /* Ensure that the dominance information is OK. */
1475 calculate_dominance_info (CDI_DOMINATORS);
1478 /* Setup callbacks for the generic dominator tree walker to find and
1479 mark definition sites. */
1480 walk_data.walk_stmts_backward = false;
1481 walk_data.dom_direction = CDI_DOMINATORS;
1482 walk_data.initialize_block_local_data = NULL;
1483 walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block;
1484 walk_data.before_dom_children_walk_stmts = mark_def_sites;
1485 walk_data.before_dom_children_after_stmts = NULL;
1486 walk_data.after_dom_children_before_stmts = NULL;
1487 walk_data.after_dom_children_walk_stmts = NULL;
1488 walk_data.after_dom_children_after_stmts = NULL;
1490 /* Notice that this bitmap is indexed using variable UIDs, so it must be
1491 large enough to accommodate all the variables referenced in the
1492 function, not just the ones we are renaming. */
1493 mark_def_sites_global_data.kills = sbitmap_alloc (num_referenced_vars);
1494 walk_data.global_data = &mark_def_sites_global_data;
1496 /* We do not have any local data. */
1497 walk_data.block_local_data_size = 0;
1499 /* Initialize the dominator walker. */
1500 init_walk_dominator_tree (&walk_data);
1502 /* Recursively walk the dominator tree. */
1503 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1505 /* Finalize the dominator walker. */
1506 fini_walk_dominator_tree (&walk_data);
1508 /* We no longer need this bitmap, clear and free it. */
1509 sbitmap_free (mark_def_sites_global_data.kills);
1512 /* Main entry point into the SSA builder. The renaming process
1513 proceeds in five main phases:
1515 1- If VARS_TO_RENAME has any entries, any existing PHI nodes for
1516 those variables are removed from the flow graph so that they can
1519 2- Compute dominance frontier and immediate dominators, needed to
1520 insert PHI nodes and rename the function in dominator tree
1523 3- Find and mark all the blocks that define variables
1524 (mark_def_site_blocks).
1526 4- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
1528 5- Rename all the blocks (rewrite_blocks) and statements in the program.
1530 Steps 3 and 5 are done using the dominator tree walker
1531 (walk_dominator_tree).
1533 ALL is true if all variables should be renamed (otherwise just those
1534 mentioned in vars_to_rename are taken into account). */
1537 rewrite_into_ssa (bool all)
1541 bitmap old_vars_to_rename = vars_to_rename;
1543 timevar_push (TV_TREE_SSA_OTHER);
1546 vars_to_rename = NULL;
1549 /* Initialize the array of variables to rename. */
1550 gcc_assert (vars_to_rename);
1552 if (bitmap_empty_p (vars_to_rename))
1554 timevar_pop (TV_TREE_SSA_OTHER);
1558 invalidate_name_tags (vars_to_rename);
1560 /* Now remove all the existing PHI nodes (if any) for the variables
1561 that we are about to rename into SSA. */
1562 remove_all_phi_nodes_for (vars_to_rename);
1565 mark_def_site_blocks ();
1567 /* Initialize dominance frontier and immediate dominator bitmaps.
1568 Also count the number of predecessors for each block. Doing so
1569 can save significant time during PHI insertion for large graphs. */
1570 dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
1572 dfs[bb->index] = BITMAP_XMALLOC ();
1574 /* Compute dominance frontiers. */
1575 compute_dominance_frontiers (dfs);
1577 /* Insert PHI nodes at dominance frontiers of definition blocks. */
1578 insert_phi_nodes (dfs, NULL);
1580 rewrite_blocks (false);
1582 /* Debugging dumps. */
1583 if (dump_file && (dump_flags & TDF_STATS))
1585 dump_dfa_stats (dump_file);
1586 dump_tree_ssa_stats (dump_file);
1589 /* Free allocated memory. */
1591 BITMAP_XFREE (dfs[bb->index]);
1594 vars_to_rename = old_vars_to_rename;
1595 timevar_pop (TV_TREE_SSA_OTHER);
1598 /* Rewrite the def-def chains so that they have the correct reaching
1602 rewrite_def_def_chains (void)
1604 /* Ensure that the dominance information is OK. */
1605 calculate_dominance_info (CDI_DOMINATORS);
1606 mark_def_site_blocks ();
1607 rewrite_blocks (true);
1610 /* The marked ssa names may have more than one definition;
1611 add phi nodes and rewrite them to fix this. */
1614 rewrite_ssa_into_ssa (void)
1618 struct dom_walk_data walk_data;
1619 struct mark_def_sites_global_data mark_def_sites_global_data;
1621 sbitmap snames_to_rename;
1626 if (!any_marked_for_rewrite_p ())
1628 to_rename = marked_ssa_names ();
1630 timevar_push (TV_TREE_SSA_OTHER);
1632 /* Allocate memory for the DEF_BLOCKS hash table. */
1633 def_blocks = htab_create (num_ssa_names,
1634 def_blocks_hash, def_blocks_eq, def_blocks_free);
1636 /* Initialize dominance frontier and immediate dominator bitmaps.
1637 Also count the number of predecessors for each block. Doing so
1638 can save significant time during PHI insertion for large graphs. */
1639 dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
1641 dfs[bb->index] = BITMAP_XMALLOC ();
1643 /* Ensure that the dominance information is OK. */
1644 calculate_dominance_info (CDI_DOMINATORS);
1646 /* Compute dominance frontiers. */
1647 compute_dominance_frontiers (dfs);
1649 /* Setup callbacks for the generic dominator tree walker to find and
1650 mark definition sites. */
1651 walk_data.walk_stmts_backward = false;
1652 walk_data.dom_direction = CDI_DOMINATORS;
1653 walk_data.initialize_block_local_data = NULL;
1654 walk_data.before_dom_children_before_stmts
1655 = ssa_mark_def_sites_initialize_block;
1656 walk_data.before_dom_children_walk_stmts = ssa_mark_def_sites;
1657 walk_data.before_dom_children_after_stmts = ssa_mark_phi_uses;
1658 walk_data.after_dom_children_before_stmts = NULL;
1659 walk_data.after_dom_children_walk_stmts = NULL;
1660 walk_data.after_dom_children_after_stmts = NULL;
1662 snames_to_rename = sbitmap_alloc (num_ssa_names);
1663 sbitmap_zero (snames_to_rename);
1664 EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, bi)
1666 SET_BIT (snames_to_rename, i);
1669 mark_def_sites_global_data.kills = sbitmap_alloc (num_ssa_names);
1670 mark_def_sites_global_data.names_to_rename = snames_to_rename;
1671 walk_data.global_data = &mark_def_sites_global_data;
1673 block_defs_stack = VEC_alloc (tree_on_heap, 10);
1675 /* We do not have any local data. */
1676 walk_data.block_local_data_size = 0;
1678 /* Initialize the dominator walker. */
1679 init_walk_dominator_tree (&walk_data);
1681 /* Recursively walk the dominator tree. */
1682 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1684 /* Finalize the dominator walker. */
1685 fini_walk_dominator_tree (&walk_data);
1687 /* We no longer need this bitmap, clear and free it. */
1688 sbitmap_free (mark_def_sites_global_data.kills);
1690 for (i = 1; i < num_ssa_names; i++)
1692 set_current_def (ssa_name (i), NULL_TREE);
1694 /* Insert PHI nodes at dominance frontiers of definition blocks. */
1695 insert_phi_nodes (dfs, to_rename);
1697 /* Rewrite all the basic blocks in the program. */
1698 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
1700 /* Setup callbacks for the generic dominator tree walker. */
1701 walk_data.walk_stmts_backward = false;
1702 walk_data.dom_direction = CDI_DOMINATORS;
1703 walk_data.initialize_block_local_data = NULL;
1704 walk_data.before_dom_children_before_stmts = ssa_rewrite_initialize_block;
1705 walk_data.before_dom_children_walk_stmts = ssa_rewrite_stmt;
1706 walk_data.before_dom_children_after_stmts = ssa_rewrite_phi_arguments;
1707 walk_data.after_dom_children_before_stmts = NULL;
1708 walk_data.after_dom_children_walk_stmts = NULL;
1709 walk_data.after_dom_children_after_stmts = ssa_rewrite_finalize_block;
1710 walk_data.global_data = snames_to_rename;
1711 walk_data.block_local_data_size = 0;
1713 /* Initialize the dominator walker. */
1714 init_walk_dominator_tree (&walk_data);
1716 /* Recursively walk the dominator tree rewriting each statement in
1717 each basic block. */
1718 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1720 /* Finalize the dominator walker. */
1721 fini_walk_dominator_tree (&walk_data);
1723 unmark_all_for_rewrite ();
1725 EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, bi)
1727 release_ssa_name (ssa_name (i));
1730 sbitmap_free (snames_to_rename);
1732 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
1734 /* Debugging dumps. */
1735 if (dump_file && (dump_flags & TDF_STATS))
1737 dump_dfa_stats (dump_file);
1738 dump_tree_ssa_stats (dump_file);
1741 /* Free allocated memory. */
1743 BITMAP_XFREE (dfs[bb->index]);
1746 htab_delete (def_blocks);
1748 for (i = 1; i < num_ssa_names; i++)
1750 name = ssa_name (i);
1751 if (!name || !SSA_NAME_AUX (name))
1754 free (SSA_NAME_AUX (name));
1755 SSA_NAME_AUX (name) = NULL;
1758 BITMAP_XFREE (to_rename);
1760 VEC_free (tree_on_heap, block_defs_stack);
1761 block_defs_stack = NULL;
1762 timevar_pop (TV_TREE_SSA_OTHER);
1765 /* Rewrites all variables into ssa. */
1768 rewrite_all_into_ssa (void)
1770 rewrite_into_ssa (true);
1773 struct tree_opt_pass pass_build_ssa =
1777 rewrite_all_into_ssa, /* execute */
1780 0, /* static_pass_number */
1782 PROP_cfg | PROP_referenced_vars, /* properties_required */
1783 PROP_ssa, /* properties_provided */
1784 0, /* properties_destroyed */
1785 0, /* todo_flags_start */
1786 TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */