1*38fd1498Szrj /* Rewrite a program in Normal form into SSA.
2*38fd1498Szrj Copyright (C) 2001-2018 Free Software Foundation, Inc.
3*38fd1498Szrj Contributed by Diego Novillo <dnovillo@redhat.com>
4*38fd1498Szrj
5*38fd1498Szrj This file is part of GCC.
6*38fd1498Szrj
7*38fd1498Szrj GCC is free software; you can redistribute it and/or modify
8*38fd1498Szrj it under the terms of the GNU General Public License as published by
9*38fd1498Szrj the Free Software Foundation; either version 3, or (at your option)
10*38fd1498Szrj any later version.
11*38fd1498Szrj
12*38fd1498Szrj GCC is distributed in the hope that it will be useful,
13*38fd1498Szrj but WITHOUT ANY WARRANTY; without even the implied warranty of
14*38fd1498Szrj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15*38fd1498Szrj GNU General Public License for more details.
16*38fd1498Szrj
17*38fd1498Szrj You should have received a copy of the GNU General Public License
18*38fd1498Szrj along with GCC; see the file COPYING3. If not see
19*38fd1498Szrj <http://www.gnu.org/licenses/>. */
20*38fd1498Szrj
21*38fd1498Szrj #include "config.h"
22*38fd1498Szrj #include "system.h"
23*38fd1498Szrj #include "coretypes.h"
24*38fd1498Szrj #include "backend.h"
25*38fd1498Szrj #include "rtl.h"
26*38fd1498Szrj #include "tree.h"
27*38fd1498Szrj #include "gimple.h"
28*38fd1498Szrj #include "tree-pass.h"
29*38fd1498Szrj #include "ssa.h"
30*38fd1498Szrj #include "gimple-pretty-print.h"
31*38fd1498Szrj #include "diagnostic-core.h"
32*38fd1498Szrj #include "langhooks.h"
33*38fd1498Szrj #include "cfganal.h"
34*38fd1498Szrj #include "gimple-iterator.h"
35*38fd1498Szrj #include "tree-cfg.h"
36*38fd1498Szrj #include "tree-into-ssa.h"
37*38fd1498Szrj #include "tree-dfa.h"
38*38fd1498Szrj #include "tree-ssa.h"
39*38fd1498Szrj #include "domwalk.h"
40*38fd1498Szrj #include "statistics.h"
41*38fd1498Szrj #include "stringpool.h"
42*38fd1498Szrj #include "attribs.h"
43*38fd1498Szrj #include "asan.h"
44*38fd1498Szrj
45*38fd1498Szrj #define PERCENT(x,y) ((float)(x) * 100.0 / (float)(y))
46*38fd1498Szrj
47*38fd1498Szrj /* This file builds the SSA form for a function as described in:
48*38fd1498Szrj R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
49*38fd1498Szrj Computing Static Single Assignment Form and the Control Dependence
50*38fd1498Szrj Graph. ACM Transactions on Programming Languages and Systems,
51*38fd1498Szrj 13(4):451-490, October 1991. */
52*38fd1498Szrj
53*38fd1498Szrj /* Structure to map a variable VAR to the set of blocks that contain
54*38fd1498Szrj definitions for VAR. */
55*38fd1498Szrj struct def_blocks
56*38fd1498Szrj {
57*38fd1498Szrj /* Blocks that contain definitions of VAR. Bit I will be set if the
58*38fd1498Szrj Ith block contains a definition of VAR. */
59*38fd1498Szrj bitmap def_blocks;
60*38fd1498Szrj
61*38fd1498Szrj /* Blocks that contain a PHI node for VAR. */
62*38fd1498Szrj bitmap phi_blocks;
63*38fd1498Szrj
64*38fd1498Szrj /* Blocks where VAR is live-on-entry. Similar semantics as
65*38fd1498Szrj DEF_BLOCKS. */
66*38fd1498Szrj bitmap livein_blocks;
67*38fd1498Szrj };
68*38fd1498Szrj
69*38fd1498Szrj /* Stack of trees used to restore the global currdefs to its original
70*38fd1498Szrj state after completing rewriting of a block and its dominator
71*38fd1498Szrj children. Its elements have the following properties:
72*38fd1498Szrj
73*38fd1498Szrj - An SSA_NAME (N) indicates that the current definition of the
74*38fd1498Szrj underlying variable should be set to the given SSA_NAME. If the
75*38fd1498Szrj symbol associated with the SSA_NAME is not a GIMPLE register, the
76*38fd1498Szrj next slot in the stack must be a _DECL node (SYM). In this case,
77*38fd1498Szrj the name N in the previous slot is the current reaching
78*38fd1498Szrj definition for SYM.
79*38fd1498Szrj
80*38fd1498Szrj - A _DECL node indicates that the underlying variable has no
81*38fd1498Szrj current definition.
82*38fd1498Szrj
83*38fd1498Szrj - A NULL node at the top entry is used to mark the last slot
84*38fd1498Szrj associated with the current block. */
85*38fd1498Szrj static vec<tree> block_defs_stack;
86*38fd1498Szrj
87*38fd1498Szrj
88*38fd1498Szrj /* Set of existing SSA names being replaced by update_ssa. */
89*38fd1498Szrj static sbitmap old_ssa_names;
90*38fd1498Szrj
91*38fd1498Szrj /* Set of new SSA names being added by update_ssa. Note that both
92*38fd1498Szrj NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
93*38fd1498Szrj the operations done on them are presence tests. */
94*38fd1498Szrj static sbitmap new_ssa_names;
95*38fd1498Szrj
96*38fd1498Szrj static sbitmap interesting_blocks;
97*38fd1498Szrj
98*38fd1498Szrj /* Set of SSA names that have been marked to be released after they
99*38fd1498Szrj were registered in the replacement table. They will be finally
100*38fd1498Szrj released after we finish updating the SSA web. */
101*38fd1498Szrj bitmap names_to_release;
102*38fd1498Szrj
103*38fd1498Szrj /* vec of vec of PHIs to rewrite in a basic block. Element I corresponds
104*38fd1498Szrj the to basic block with index I. Allocated once per compilation, *not*
105*38fd1498Szrj released between different functions. */
106*38fd1498Szrj static vec< vec<gphi *> > phis_to_rewrite;
107*38fd1498Szrj
108*38fd1498Szrj /* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
109*38fd1498Szrj static bitmap blocks_with_phis_to_rewrite;
110*38fd1498Szrj
111*38fd1498Szrj /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
112*38fd1498Szrj to grow as the callers to create_new_def_for will create new names on
113*38fd1498Szrj the fly.
114*38fd1498Szrj FIXME. Currently set to 1/3 to avoid frequent reallocations but still
115*38fd1498Szrj need to find a reasonable growth strategy. */
116*38fd1498Szrj #define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
117*38fd1498Szrj
118*38fd1498Szrj
119*38fd1498Szrj /* The function the SSA updating data structures have been initialized for.
120*38fd1498Szrj NULL if they need to be initialized by create_new_def_for. */
121*38fd1498Szrj static struct function *update_ssa_initialized_fn = NULL;
122*38fd1498Szrj
123*38fd1498Szrj /* Global data to attach to the main dominator walk structure. */
124*38fd1498Szrj struct mark_def_sites_global_data
125*38fd1498Szrj {
126*38fd1498Szrj /* This bitmap contains the variables which are set before they
127*38fd1498Szrj are used in a basic block. */
128*38fd1498Szrj bitmap kills;
129*38fd1498Szrj };
130*38fd1498Szrj
131*38fd1498Szrj /* It is advantageous to avoid things like life analysis for variables which
132*38fd1498Szrj do not need PHI nodes. This enum describes whether or not a particular
133*38fd1498Szrj variable may need a PHI node. */
134*38fd1498Szrj
135*38fd1498Szrj enum need_phi_state {
136*38fd1498Szrj /* This is the default. If we are still in this state after finding
137*38fd1498Szrj all the definition and use sites, then we will assume the variable
138*38fd1498Szrj needs PHI nodes. This is probably an overly conservative assumption. */
139*38fd1498Szrj NEED_PHI_STATE_UNKNOWN,
140*38fd1498Szrj
141*38fd1498Szrj /* This state indicates that we have seen one or more sets of the
142*38fd1498Szrj variable in a single basic block and that the sets dominate all
143*38fd1498Szrj uses seen so far. If after finding all definition and use sites
144*38fd1498Szrj we are still in this state, then the variable does not need any
145*38fd1498Szrj PHI nodes. */
146*38fd1498Szrj NEED_PHI_STATE_NO,
147*38fd1498Szrj
148*38fd1498Szrj /* This state indicates that we have either seen multiple definitions of
149*38fd1498Szrj the variable in multiple blocks, or that we encountered a use in a
150*38fd1498Szrj block that was not dominated by the block containing the set(s) of
151*38fd1498Szrj this variable. This variable is assumed to need PHI nodes. */
152*38fd1498Szrj NEED_PHI_STATE_MAYBE
153*38fd1498Szrj };
154*38fd1498Szrj
155*38fd1498Szrj /* Information stored for both SSA names and decls. */
156*38fd1498Szrj struct common_info
157*38fd1498Szrj {
158*38fd1498Szrj /* This field indicates whether or not the variable may need PHI nodes.
159*38fd1498Szrj See the enum's definition for more detailed information about the
160*38fd1498Szrj states. */
161*38fd1498Szrj ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
162*38fd1498Szrj
163*38fd1498Szrj /* The current reaching definition replacing this var. */
164*38fd1498Szrj tree current_def;
165*38fd1498Szrj
166*38fd1498Szrj /* Definitions for this var. */
167*38fd1498Szrj struct def_blocks def_blocks;
168*38fd1498Szrj };
169*38fd1498Szrj
170*38fd1498Szrj /* Information stored for decls. */
171*38fd1498Szrj struct var_info
172*38fd1498Szrj {
173*38fd1498Szrj /* The variable. */
174*38fd1498Szrj tree var;
175*38fd1498Szrj
176*38fd1498Szrj /* Information stored for both SSA names and decls. */
177*38fd1498Szrj common_info info;
178*38fd1498Szrj };
179*38fd1498Szrj
180*38fd1498Szrj
181*38fd1498Szrj /* VAR_INFOS hashtable helpers. */
182*38fd1498Szrj
183*38fd1498Szrj struct var_info_hasher : free_ptr_hash <var_info>
184*38fd1498Szrj {
185*38fd1498Szrj static inline hashval_t hash (const value_type &);
186*38fd1498Szrj static inline bool equal (const value_type &, const compare_type &);
187*38fd1498Szrj };
188*38fd1498Szrj
189*38fd1498Szrj inline hashval_t
hash(const value_type & p)190*38fd1498Szrj var_info_hasher::hash (const value_type &p)
191*38fd1498Szrj {
192*38fd1498Szrj return DECL_UID (p->var);
193*38fd1498Szrj }
194*38fd1498Szrj
195*38fd1498Szrj inline bool
equal(const value_type & p1,const compare_type & p2)196*38fd1498Szrj var_info_hasher::equal (const value_type &p1, const compare_type &p2)
197*38fd1498Szrj {
198*38fd1498Szrj return p1->var == p2->var;
199*38fd1498Szrj }
200*38fd1498Szrj
201*38fd1498Szrj
202*38fd1498Szrj /* Each entry in VAR_INFOS contains an element of type STRUCT
203*38fd1498Szrj VAR_INFO_D. */
204*38fd1498Szrj static hash_table<var_info_hasher> *var_infos;
205*38fd1498Szrj
206*38fd1498Szrj
207*38fd1498Szrj /* Information stored for SSA names. */
208*38fd1498Szrj struct ssa_name_info
209*38fd1498Szrj {
210*38fd1498Szrj /* Age of this record (so that info_for_ssa_name table can be cleared
211*38fd1498Szrj quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
212*38fd1498Szrj are assumed to be null. */
213*38fd1498Szrj unsigned age;
214*38fd1498Szrj
215*38fd1498Szrj /* Replacement mappings, allocated from update_ssa_obstack. */
216*38fd1498Szrj bitmap repl_set;
217*38fd1498Szrj
218*38fd1498Szrj /* Information stored for both SSA names and decls. */
219*38fd1498Szrj common_info info;
220*38fd1498Szrj };
221*38fd1498Szrj
222*38fd1498Szrj static vec<ssa_name_info *> info_for_ssa_name;
223*38fd1498Szrj static unsigned current_info_for_ssa_name_age;
224*38fd1498Szrj
225*38fd1498Szrj static bitmap_obstack update_ssa_obstack;
226*38fd1498Szrj
227*38fd1498Szrj /* The set of blocks affected by update_ssa. */
228*38fd1498Szrj static bitmap blocks_to_update;
229*38fd1498Szrj
230*38fd1498Szrj /* The main entry point to the SSA renamer (rewrite_blocks) may be
231*38fd1498Szrj called several times to do different, but related, tasks.
232*38fd1498Szrj Initially, we need it to rename the whole program into SSA form.
233*38fd1498Szrj At other times, we may need it to only rename into SSA newly
234*38fd1498Szrj exposed symbols. Finally, we can also call it to incrementally fix
235*38fd1498Szrj an already built SSA web. */
236*38fd1498Szrj enum rewrite_mode {
237*38fd1498Szrj /* Convert the whole function into SSA form. */
238*38fd1498Szrj REWRITE_ALL,
239*38fd1498Szrj
240*38fd1498Szrj /* Incrementally update the SSA web by replacing existing SSA
241*38fd1498Szrj names with new ones. See update_ssa for details. */
242*38fd1498Szrj REWRITE_UPDATE
243*38fd1498Szrj };
244*38fd1498Szrj
245*38fd1498Szrj /* The set of symbols we ought to re-write into SSA form in update_ssa. */
246*38fd1498Szrj static bitmap symbols_to_rename_set;
247*38fd1498Szrj static vec<tree> symbols_to_rename;
248*38fd1498Szrj
249*38fd1498Szrj /* Mark SYM for renaming. */
250*38fd1498Szrj
251*38fd1498Szrj static void
mark_for_renaming(tree sym)252*38fd1498Szrj mark_for_renaming (tree sym)
253*38fd1498Szrj {
254*38fd1498Szrj if (!symbols_to_rename_set)
255*38fd1498Szrj symbols_to_rename_set = BITMAP_ALLOC (NULL);
256*38fd1498Szrj if (bitmap_set_bit (symbols_to_rename_set, DECL_UID (sym)))
257*38fd1498Szrj symbols_to_rename.safe_push (sym);
258*38fd1498Szrj }
259*38fd1498Szrj
260*38fd1498Szrj /* Return true if SYM is marked for renaming. */
261*38fd1498Szrj
262*38fd1498Szrj static bool
marked_for_renaming(tree sym)263*38fd1498Szrj marked_for_renaming (tree sym)
264*38fd1498Szrj {
265*38fd1498Szrj if (!symbols_to_rename_set || sym == NULL_TREE)
266*38fd1498Szrj return false;
267*38fd1498Szrj return bitmap_bit_p (symbols_to_rename_set, DECL_UID (sym));
268*38fd1498Szrj }
269*38fd1498Szrj
270*38fd1498Szrj
271*38fd1498Szrj /* Return true if STMT needs to be rewritten. When renaming a subset
272*38fd1498Szrj of the variables, not all statements will be processed. This is
273*38fd1498Szrj decided in mark_def_sites. */
274*38fd1498Szrj
275*38fd1498Szrj static inline bool
rewrite_uses_p(gimple * stmt)276*38fd1498Szrj rewrite_uses_p (gimple *stmt)
277*38fd1498Szrj {
278*38fd1498Szrj return gimple_visited_p (stmt);
279*38fd1498Szrj }
280*38fd1498Szrj
281*38fd1498Szrj
282*38fd1498Szrj /* Set the rewrite marker on STMT to the value given by REWRITE_P. */
283*38fd1498Szrj
284*38fd1498Szrj static inline void
set_rewrite_uses(gimple * stmt,bool rewrite_p)285*38fd1498Szrj set_rewrite_uses (gimple *stmt, bool rewrite_p)
286*38fd1498Szrj {
287*38fd1498Szrj gimple_set_visited (stmt, rewrite_p);
288*38fd1498Szrj }
289*38fd1498Szrj
290*38fd1498Szrj
291*38fd1498Szrj /* Return true if the DEFs created by statement STMT should be
292*38fd1498Szrj registered when marking new definition sites. This is slightly
293*38fd1498Szrj different than rewrite_uses_p: it's used by update_ssa to
294*38fd1498Szrj distinguish statements that need to have both uses and defs
295*38fd1498Szrj processed from those that only need to have their defs processed.
296*38fd1498Szrj Statements that define new SSA names only need to have their defs
297*38fd1498Szrj registered, but they don't need to have their uses renamed. */
298*38fd1498Szrj
299*38fd1498Szrj static inline bool
register_defs_p(gimple * stmt)300*38fd1498Szrj register_defs_p (gimple *stmt)
301*38fd1498Szrj {
302*38fd1498Szrj return gimple_plf (stmt, GF_PLF_1) != 0;
303*38fd1498Szrj }
304*38fd1498Szrj
305*38fd1498Szrj
306*38fd1498Szrj /* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered. */
307*38fd1498Szrj
308*38fd1498Szrj static inline void
set_register_defs(gimple * stmt,bool register_defs_p)309*38fd1498Szrj set_register_defs (gimple *stmt, bool register_defs_p)
310*38fd1498Szrj {
311*38fd1498Szrj gimple_set_plf (stmt, GF_PLF_1, register_defs_p);
312*38fd1498Szrj }
313*38fd1498Szrj
314*38fd1498Szrj
315*38fd1498Szrj /* Get the information associated with NAME. */
316*38fd1498Szrj
317*38fd1498Szrj static inline ssa_name_info *
get_ssa_name_ann(tree name)318*38fd1498Szrj get_ssa_name_ann (tree name)
319*38fd1498Szrj {
320*38fd1498Szrj unsigned ver = SSA_NAME_VERSION (name);
321*38fd1498Szrj unsigned len = info_for_ssa_name.length ();
322*38fd1498Szrj struct ssa_name_info *info;
323*38fd1498Szrj
324*38fd1498Szrj /* Re-allocate the vector at most once per update/into-SSA. */
325*38fd1498Szrj if (ver >= len)
326*38fd1498Szrj info_for_ssa_name.safe_grow_cleared (num_ssa_names);
327*38fd1498Szrj
328*38fd1498Szrj /* But allocate infos lazily. */
329*38fd1498Szrj info = info_for_ssa_name[ver];
330*38fd1498Szrj if (!info)
331*38fd1498Szrj {
332*38fd1498Szrj info = XCNEW (struct ssa_name_info);
333*38fd1498Szrj info->age = current_info_for_ssa_name_age;
334*38fd1498Szrj info->info.need_phi_state = NEED_PHI_STATE_UNKNOWN;
335*38fd1498Szrj info_for_ssa_name[ver] = info;
336*38fd1498Szrj }
337*38fd1498Szrj
338*38fd1498Szrj if (info->age < current_info_for_ssa_name_age)
339*38fd1498Szrj {
340*38fd1498Szrj info->age = current_info_for_ssa_name_age;
341*38fd1498Szrj info->repl_set = NULL;
342*38fd1498Szrj info->info.need_phi_state = NEED_PHI_STATE_UNKNOWN;
343*38fd1498Szrj info->info.current_def = NULL_TREE;
344*38fd1498Szrj info->info.def_blocks.def_blocks = NULL;
345*38fd1498Szrj info->info.def_blocks.phi_blocks = NULL;
346*38fd1498Szrj info->info.def_blocks.livein_blocks = NULL;
347*38fd1498Szrj }
348*38fd1498Szrj
349*38fd1498Szrj return info;
350*38fd1498Szrj }
351*38fd1498Szrj
352*38fd1498Szrj /* Return and allocate the auxiliar information for DECL. */
353*38fd1498Szrj
354*38fd1498Szrj static inline var_info *
get_var_info(tree decl)355*38fd1498Szrj get_var_info (tree decl)
356*38fd1498Szrj {
357*38fd1498Szrj var_info vi;
358*38fd1498Szrj var_info **slot;
359*38fd1498Szrj vi.var = decl;
360*38fd1498Szrj slot = var_infos->find_slot_with_hash (&vi, DECL_UID (decl), INSERT);
361*38fd1498Szrj if (*slot == NULL)
362*38fd1498Szrj {
363*38fd1498Szrj var_info *v = XCNEW (var_info);
364*38fd1498Szrj v->var = decl;
365*38fd1498Szrj *slot = v;
366*38fd1498Szrj return v;
367*38fd1498Szrj }
368*38fd1498Szrj return *slot;
369*38fd1498Szrj }
370*38fd1498Szrj
371*38fd1498Szrj
372*38fd1498Szrj /* Clears info for SSA names. */
373*38fd1498Szrj
374*38fd1498Szrj static void
clear_ssa_name_info(void)375*38fd1498Szrj clear_ssa_name_info (void)
376*38fd1498Szrj {
377*38fd1498Szrj current_info_for_ssa_name_age++;
378*38fd1498Szrj
379*38fd1498Szrj /* If current_info_for_ssa_name_age wraps we use stale information.
380*38fd1498Szrj Asser that this does not happen. */
381*38fd1498Szrj gcc_assert (current_info_for_ssa_name_age != 0);
382*38fd1498Szrj }
383*38fd1498Szrj
384*38fd1498Szrj
385*38fd1498Szrj /* Get access to the auxiliar information stored per SSA name or decl. */
386*38fd1498Szrj
387*38fd1498Szrj static inline common_info *
get_common_info(tree var)388*38fd1498Szrj get_common_info (tree var)
389*38fd1498Szrj {
390*38fd1498Szrj if (TREE_CODE (var) == SSA_NAME)
391*38fd1498Szrj return &get_ssa_name_ann (var)->info;
392*38fd1498Szrj else
393*38fd1498Szrj return &get_var_info (var)->info;
394*38fd1498Szrj }
395*38fd1498Szrj
396*38fd1498Szrj
397*38fd1498Szrj /* Return the current definition for VAR. */
398*38fd1498Szrj
399*38fd1498Szrj tree
get_current_def(tree var)400*38fd1498Szrj get_current_def (tree var)
401*38fd1498Szrj {
402*38fd1498Szrj return get_common_info (var)->current_def;
403*38fd1498Szrj }
404*38fd1498Szrj
405*38fd1498Szrj
406*38fd1498Szrj /* Sets current definition of VAR to DEF. */
407*38fd1498Szrj
408*38fd1498Szrj void
set_current_def(tree var,tree def)409*38fd1498Szrj set_current_def (tree var, tree def)
410*38fd1498Szrj {
411*38fd1498Szrj get_common_info (var)->current_def = def;
412*38fd1498Szrj }
413*38fd1498Szrj
414*38fd1498Szrj /* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
415*38fd1498Szrj all statements in basic block BB. */
416*38fd1498Szrj
417*38fd1498Szrj static void
initialize_flags_in_bb(basic_block bb)418*38fd1498Szrj initialize_flags_in_bb (basic_block bb)
419*38fd1498Szrj {
420*38fd1498Szrj gimple *stmt;
421*38fd1498Szrj gimple_stmt_iterator gsi;
422*38fd1498Szrj
423*38fd1498Szrj for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
424*38fd1498Szrj {
425*38fd1498Szrj gimple *phi = gsi_stmt (gsi);
426*38fd1498Szrj set_rewrite_uses (phi, false);
427*38fd1498Szrj set_register_defs (phi, false);
428*38fd1498Szrj }
429*38fd1498Szrj
430*38fd1498Szrj for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
431*38fd1498Szrj {
432*38fd1498Szrj stmt = gsi_stmt (gsi);
433*38fd1498Szrj
434*38fd1498Szrj /* We are going to use the operand cache API, such as
435*38fd1498Szrj SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
436*38fd1498Szrj cache for each statement should be up-to-date. */
437*38fd1498Szrj gcc_checking_assert (!gimple_modified_p (stmt));
438*38fd1498Szrj set_rewrite_uses (stmt, false);
439*38fd1498Szrj set_register_defs (stmt, false);
440*38fd1498Szrj }
441*38fd1498Szrj }
442*38fd1498Szrj
443*38fd1498Szrj /* Mark block BB as interesting for update_ssa. */
444*38fd1498Szrj
445*38fd1498Szrj static void
mark_block_for_update(basic_block bb)446*38fd1498Szrj mark_block_for_update (basic_block bb)
447*38fd1498Szrj {
448*38fd1498Szrj gcc_checking_assert (blocks_to_update != NULL);
449*38fd1498Szrj if (!bitmap_set_bit (blocks_to_update, bb->index))
450*38fd1498Szrj return;
451*38fd1498Szrj initialize_flags_in_bb (bb);
452*38fd1498Szrj }
453*38fd1498Szrj
454*38fd1498Szrj /* Return the set of blocks where variable VAR is defined and the blocks
455*38fd1498Szrj where VAR is live on entry (livein). If no entry is found in
456*38fd1498Szrj DEF_BLOCKS, a new one is created and returned. */
457*38fd1498Szrj
458*38fd1498Szrj static inline def_blocks *
get_def_blocks_for(common_info * info)459*38fd1498Szrj get_def_blocks_for (common_info *info)
460*38fd1498Szrj {
461*38fd1498Szrj def_blocks *db_p = &info->def_blocks;
462*38fd1498Szrj if (!db_p->def_blocks)
463*38fd1498Szrj {
464*38fd1498Szrj db_p->def_blocks = BITMAP_ALLOC (&update_ssa_obstack);
465*38fd1498Szrj db_p->phi_blocks = BITMAP_ALLOC (&update_ssa_obstack);
466*38fd1498Szrj db_p->livein_blocks = BITMAP_ALLOC (&update_ssa_obstack);
467*38fd1498Szrj }
468*38fd1498Szrj
469*38fd1498Szrj return db_p;
470*38fd1498Szrj }
471*38fd1498Szrj
472*38fd1498Szrj
473*38fd1498Szrj /* Mark block BB as the definition site for variable VAR. PHI_P is true if
474*38fd1498Szrj VAR is defined by a PHI node. */
475*38fd1498Szrj
476*38fd1498Szrj static void
set_def_block(tree var,basic_block bb,bool phi_p)477*38fd1498Szrj set_def_block (tree var, basic_block bb, bool phi_p)
478*38fd1498Szrj {
479*38fd1498Szrj def_blocks *db_p;
480*38fd1498Szrj common_info *info;
481*38fd1498Szrj
482*38fd1498Szrj info = get_common_info (var);
483*38fd1498Szrj db_p = get_def_blocks_for (info);
484*38fd1498Szrj
485*38fd1498Szrj /* Set the bit corresponding to the block where VAR is defined. */
486*38fd1498Szrj bitmap_set_bit (db_p->def_blocks, bb->index);
487*38fd1498Szrj if (phi_p)
488*38fd1498Szrj bitmap_set_bit (db_p->phi_blocks, bb->index);
489*38fd1498Szrj
490*38fd1498Szrj /* Keep track of whether or not we may need to insert PHI nodes.
491*38fd1498Szrj
492*38fd1498Szrj If we are in the UNKNOWN state, then this is the first definition
493*38fd1498Szrj of VAR. Additionally, we have not seen any uses of VAR yet, so
494*38fd1498Szrj we do not need a PHI node for this variable at this time (i.e.,
495*38fd1498Szrj transition to NEED_PHI_STATE_NO).
496*38fd1498Szrj
497*38fd1498Szrj If we are in any other state, then we either have multiple definitions
498*38fd1498Szrj of this variable occurring in different blocks or we saw a use of the
499*38fd1498Szrj variable which was not dominated by the block containing the
500*38fd1498Szrj definition(s). In this case we may need a PHI node, so enter
501*38fd1498Szrj state NEED_PHI_STATE_MAYBE. */
502*38fd1498Szrj if (info->need_phi_state == NEED_PHI_STATE_UNKNOWN)
503*38fd1498Szrj info->need_phi_state = NEED_PHI_STATE_NO;
504*38fd1498Szrj else
505*38fd1498Szrj info->need_phi_state = NEED_PHI_STATE_MAYBE;
506*38fd1498Szrj }
507*38fd1498Szrj
508*38fd1498Szrj
509*38fd1498Szrj /* Mark block BB as having VAR live at the entry to BB. */
510*38fd1498Szrj
511*38fd1498Szrj static void
set_livein_block(tree var,basic_block bb)512*38fd1498Szrj set_livein_block (tree var, basic_block bb)
513*38fd1498Szrj {
514*38fd1498Szrj common_info *info;
515*38fd1498Szrj def_blocks *db_p;
516*38fd1498Szrj
517*38fd1498Szrj info = get_common_info (var);
518*38fd1498Szrj db_p = get_def_blocks_for (info);
519*38fd1498Szrj
520*38fd1498Szrj /* Set the bit corresponding to the block where VAR is live in. */
521*38fd1498Szrj bitmap_set_bit (db_p->livein_blocks, bb->index);
522*38fd1498Szrj
523*38fd1498Szrj /* Keep track of whether or not we may need to insert PHI nodes.
524*38fd1498Szrj
525*38fd1498Szrj If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
526*38fd1498Szrj by the single block containing the definition(s) of this variable. If
527*38fd1498Szrj it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
528*38fd1498Szrj NEED_PHI_STATE_MAYBE. */
529*38fd1498Szrj if (info->need_phi_state == NEED_PHI_STATE_NO)
530*38fd1498Szrj {
531*38fd1498Szrj int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
532*38fd1498Szrj
533*38fd1498Szrj if (def_block_index == -1
534*38fd1498Szrj || ! dominated_by_p (CDI_DOMINATORS, bb,
535*38fd1498Szrj BASIC_BLOCK_FOR_FN (cfun, def_block_index)))
536*38fd1498Szrj info->need_phi_state = NEED_PHI_STATE_MAYBE;
537*38fd1498Szrj }
538*38fd1498Szrj else
539*38fd1498Szrj info->need_phi_state = NEED_PHI_STATE_MAYBE;
540*38fd1498Szrj }
541*38fd1498Szrj
542*38fd1498Szrj
543*38fd1498Szrj /* Return true if NAME is in OLD_SSA_NAMES. */
544*38fd1498Szrj
545*38fd1498Szrj static inline bool
is_old_name(tree name)546*38fd1498Szrj is_old_name (tree name)
547*38fd1498Szrj {
548*38fd1498Szrj unsigned ver = SSA_NAME_VERSION (name);
549*38fd1498Szrj if (!old_ssa_names)
550*38fd1498Szrj return false;
551*38fd1498Szrj return (ver < SBITMAP_SIZE (old_ssa_names)
552*38fd1498Szrj && bitmap_bit_p (old_ssa_names, ver));
553*38fd1498Szrj }
554*38fd1498Szrj
555*38fd1498Szrj
556*38fd1498Szrj /* Return true if NAME is in NEW_SSA_NAMES. */
557*38fd1498Szrj
558*38fd1498Szrj static inline bool
is_new_name(tree name)559*38fd1498Szrj is_new_name (tree name)
560*38fd1498Szrj {
561*38fd1498Szrj unsigned ver = SSA_NAME_VERSION (name);
562*38fd1498Szrj if (!new_ssa_names)
563*38fd1498Szrj return false;
564*38fd1498Szrj return (ver < SBITMAP_SIZE (new_ssa_names)
565*38fd1498Szrj && bitmap_bit_p (new_ssa_names, ver));
566*38fd1498Szrj }
567*38fd1498Szrj
568*38fd1498Szrj
569*38fd1498Szrj /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET). */
570*38fd1498Szrj
571*38fd1498Szrj static inline bitmap
names_replaced_by(tree new_tree)572*38fd1498Szrj names_replaced_by (tree new_tree)
573*38fd1498Szrj {
574*38fd1498Szrj return get_ssa_name_ann (new_tree)->repl_set;
575*38fd1498Szrj }
576*38fd1498Szrj
577*38fd1498Szrj
578*38fd1498Szrj /* Add OLD to REPL_TBL[NEW_TREE].SET. */
579*38fd1498Szrj
580*38fd1498Szrj static inline void
add_to_repl_tbl(tree new_tree,tree old)581*38fd1498Szrj add_to_repl_tbl (tree new_tree, tree old)
582*38fd1498Szrj {
583*38fd1498Szrj bitmap *set = &get_ssa_name_ann (new_tree)->repl_set;
584*38fd1498Szrj if (!*set)
585*38fd1498Szrj *set = BITMAP_ALLOC (&update_ssa_obstack);
586*38fd1498Szrj bitmap_set_bit (*set, SSA_NAME_VERSION (old));
587*38fd1498Szrj }
588*38fd1498Szrj
589*38fd1498Szrj
590*38fd1498Szrj /* Add a new mapping NEW_TREE -> OLD REPL_TBL. Every entry N_i in REPL_TBL
591*38fd1498Szrj represents the set of names O_1 ... O_j replaced by N_i. This is
592*38fd1498Szrj used by update_ssa and its helpers to introduce new SSA names in an
593*38fd1498Szrj already formed SSA web. */
594*38fd1498Szrj
595*38fd1498Szrj static void
add_new_name_mapping(tree new_tree,tree old)596*38fd1498Szrj add_new_name_mapping (tree new_tree, tree old)
597*38fd1498Szrj {
598*38fd1498Szrj /* OLD and NEW_TREE must be different SSA names for the same symbol. */
599*38fd1498Szrj gcc_checking_assert (new_tree != old
600*38fd1498Szrj && SSA_NAME_VAR (new_tree) == SSA_NAME_VAR (old));
601*38fd1498Szrj
602*38fd1498Szrj /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
603*38fd1498Szrj caller may have created new names since the set was created. */
604*38fd1498Szrj if (SBITMAP_SIZE (new_ssa_names) <= num_ssa_names - 1)
605*38fd1498Szrj {
606*38fd1498Szrj unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
607*38fd1498Szrj new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
608*38fd1498Szrj old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
609*38fd1498Szrj }
610*38fd1498Szrj
611*38fd1498Szrj /* Update the REPL_TBL table. */
612*38fd1498Szrj add_to_repl_tbl (new_tree, old);
613*38fd1498Szrj
614*38fd1498Szrj /* If OLD had already been registered as a new name, then all the
615*38fd1498Szrj names that OLD replaces should also be replaced by NEW_TREE. */
616*38fd1498Szrj if (is_new_name (old))
617*38fd1498Szrj bitmap_ior_into (names_replaced_by (new_tree), names_replaced_by (old));
618*38fd1498Szrj
619*38fd1498Szrj /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
620*38fd1498Szrj respectively. */
621*38fd1498Szrj bitmap_set_bit (new_ssa_names, SSA_NAME_VERSION (new_tree));
622*38fd1498Szrj bitmap_set_bit (old_ssa_names, SSA_NAME_VERSION (old));
623*38fd1498Szrj }
624*38fd1498Szrj
625*38fd1498Szrj
626*38fd1498Szrj /* Call back for walk_dominator_tree used to collect definition sites
627*38fd1498Szrj for every variable in the function. For every statement S in block
628*38fd1498Szrj BB:
629*38fd1498Szrj
630*38fd1498Szrj 1- Variables defined by S in the DEFS of S are marked in the bitmap
631*38fd1498Szrj KILLS.
632*38fd1498Szrj
633*38fd1498Szrj 2- If S uses a variable VAR and there is no preceding kill of VAR,
634*38fd1498Szrj then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
635*38fd1498Szrj
636*38fd1498Szrj This information is used to determine which variables are live
637*38fd1498Szrj across block boundaries to reduce the number of PHI nodes
638*38fd1498Szrj we create. */
639*38fd1498Szrj
640*38fd1498Szrj static void
mark_def_sites(basic_block bb,gimple * stmt,bitmap kills)641*38fd1498Szrj mark_def_sites (basic_block bb, gimple *stmt, bitmap kills)
642*38fd1498Szrj {
643*38fd1498Szrj tree def;
644*38fd1498Szrj use_operand_p use_p;
645*38fd1498Szrj ssa_op_iter iter;
646*38fd1498Szrj
647*38fd1498Szrj /* Since this is the first time that we rewrite the program into SSA
648*38fd1498Szrj form, force an operand scan on every statement. */
649*38fd1498Szrj update_stmt (stmt);
650*38fd1498Szrj
651*38fd1498Szrj gcc_checking_assert (blocks_to_update == NULL);
652*38fd1498Szrj set_register_defs (stmt, false);
653*38fd1498Szrj set_rewrite_uses (stmt, false);
654*38fd1498Szrj
655*38fd1498Szrj if (is_gimple_debug (stmt))
656*38fd1498Szrj {
657*38fd1498Szrj FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
658*38fd1498Szrj {
659*38fd1498Szrj tree sym = USE_FROM_PTR (use_p);
660*38fd1498Szrj gcc_checking_assert (DECL_P (sym));
661*38fd1498Szrj set_rewrite_uses (stmt, true);
662*38fd1498Szrj }
663*38fd1498Szrj if (rewrite_uses_p (stmt))
664*38fd1498Szrj bitmap_set_bit (interesting_blocks, bb->index);
665*38fd1498Szrj return;
666*38fd1498Szrj }
667*38fd1498Szrj
668*38fd1498Szrj /* If a variable is used before being set, then the variable is live
669*38fd1498Szrj across a block boundary, so mark it live-on-entry to BB. */
670*38fd1498Szrj FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
671*38fd1498Szrj {
672*38fd1498Szrj tree sym = USE_FROM_PTR (use_p);
673*38fd1498Szrj if (TREE_CODE (sym) == SSA_NAME)
674*38fd1498Szrj continue;
675*38fd1498Szrj gcc_checking_assert (DECL_P (sym));
676*38fd1498Szrj if (!bitmap_bit_p (kills, DECL_UID (sym)))
677*38fd1498Szrj set_livein_block (sym, bb);
678*38fd1498Szrj set_rewrite_uses (stmt, true);
679*38fd1498Szrj }
680*38fd1498Szrj
681*38fd1498Szrj /* Now process the defs. Mark BB as the definition block and add
682*38fd1498Szrj each def to the set of killed symbols. */
683*38fd1498Szrj FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
684*38fd1498Szrj {
685*38fd1498Szrj if (TREE_CODE (def) == SSA_NAME)
686*38fd1498Szrj continue;
687*38fd1498Szrj gcc_checking_assert (DECL_P (def));
688*38fd1498Szrj set_def_block (def, bb, false);
689*38fd1498Szrj bitmap_set_bit (kills, DECL_UID (def));
690*38fd1498Szrj set_register_defs (stmt, true);
691*38fd1498Szrj }
692*38fd1498Szrj
693*38fd1498Szrj /* If we found the statement interesting then also mark the block BB
694*38fd1498Szrj as interesting. */
695*38fd1498Szrj if (rewrite_uses_p (stmt) || register_defs_p (stmt))
696*38fd1498Szrj bitmap_set_bit (interesting_blocks, bb->index);
697*38fd1498Szrj }
698*38fd1498Szrj
699*38fd1498Szrj /* Structure used by prune_unused_phi_nodes to record bounds of the intervals
700*38fd1498Szrj in the dfs numbering of the dominance tree. */
701*38fd1498Szrj
702*38fd1498Szrj struct dom_dfsnum
703*38fd1498Szrj {
704*38fd1498Szrj /* Basic block whose index this entry corresponds to. */
705*38fd1498Szrj unsigned bb_index;
706*38fd1498Szrj
707*38fd1498Szrj /* The dfs number of this node. */
708*38fd1498Szrj unsigned dfs_num;
709*38fd1498Szrj };
710*38fd1498Szrj
711*38fd1498Szrj /* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
712*38fd1498Szrj for qsort. */
713*38fd1498Szrj
714*38fd1498Szrj static int
cmp_dfsnum(const void * a,const void * b)715*38fd1498Szrj cmp_dfsnum (const void *a, const void *b)
716*38fd1498Szrj {
717*38fd1498Szrj const struct dom_dfsnum *const da = (const struct dom_dfsnum *) a;
718*38fd1498Szrj const struct dom_dfsnum *const db = (const struct dom_dfsnum *) b;
719*38fd1498Szrj
720*38fd1498Szrj return (int) da->dfs_num - (int) db->dfs_num;
721*38fd1498Szrj }
722*38fd1498Szrj
723*38fd1498Szrj /* Among the intervals starting at the N points specified in DEFS, find
724*38fd1498Szrj the one that contains S, and return its bb_index. */
725*38fd1498Szrj
726*38fd1498Szrj static unsigned
find_dfsnum_interval(struct dom_dfsnum * defs,unsigned n,unsigned s)727*38fd1498Szrj find_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s)
728*38fd1498Szrj {
729*38fd1498Szrj unsigned f = 0, t = n, m;
730*38fd1498Szrj
731*38fd1498Szrj while (t > f + 1)
732*38fd1498Szrj {
733*38fd1498Szrj m = (f + t) / 2;
734*38fd1498Szrj if (defs[m].dfs_num <= s)
735*38fd1498Szrj f = m;
736*38fd1498Szrj else
737*38fd1498Szrj t = m;
738*38fd1498Szrj }
739*38fd1498Szrj
740*38fd1498Szrj return defs[f].bb_index;
741*38fd1498Szrj }
742*38fd1498Szrj
743*38fd1498Szrj /* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
744*38fd1498Szrj KILLS is a bitmap of blocks where the value is defined before any use. */
745*38fd1498Szrj
746*38fd1498Szrj static void
prune_unused_phi_nodes(bitmap phis,bitmap kills,bitmap uses)747*38fd1498Szrj prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses)
748*38fd1498Szrj {
749*38fd1498Szrj bitmap_iterator bi;
750*38fd1498Szrj unsigned i, b, p, u, top;
751*38fd1498Szrj bitmap live_phis;
752*38fd1498Szrj basic_block def_bb, use_bb;
753*38fd1498Szrj edge e;
754*38fd1498Szrj edge_iterator ei;
755*38fd1498Szrj bitmap to_remove;
756*38fd1498Szrj struct dom_dfsnum *defs;
757*38fd1498Szrj unsigned n_defs, adef;
758*38fd1498Szrj
759*38fd1498Szrj if (bitmap_empty_p (uses))
760*38fd1498Szrj {
761*38fd1498Szrj bitmap_clear (phis);
762*38fd1498Szrj return;
763*38fd1498Szrj }
764*38fd1498Szrj
765*38fd1498Szrj /* The phi must dominate a use, or an argument of a live phi. Also, we
766*38fd1498Szrj do not create any phi nodes in def blocks, unless they are also livein. */
767*38fd1498Szrj to_remove = BITMAP_ALLOC (NULL);
768*38fd1498Szrj bitmap_and_compl (to_remove, kills, uses);
769*38fd1498Szrj bitmap_and_compl_into (phis, to_remove);
770*38fd1498Szrj if (bitmap_empty_p (phis))
771*38fd1498Szrj {
772*38fd1498Szrj BITMAP_FREE (to_remove);
773*38fd1498Szrj return;
774*38fd1498Szrj }
775*38fd1498Szrj
776*38fd1498Szrj /* We want to remove the unnecessary phi nodes, but we do not want to compute
777*38fd1498Szrj liveness information, as that may be linear in the size of CFG, and if
778*38fd1498Szrj there are lot of different variables to rewrite, this may lead to quadratic
779*38fd1498Szrj behavior.
780*38fd1498Szrj
781*38fd1498Szrj Instead, we basically emulate standard dce. We put all uses to worklist,
782*38fd1498Szrj then for each of them find the nearest def that dominates them. If this
783*38fd1498Szrj def is a phi node, we mark it live, and if it was not live before, we
784*38fd1498Szrj add the predecessors of its basic block to the worklist.
785*38fd1498Szrj
786*38fd1498Szrj To quickly locate the nearest def that dominates use, we use dfs numbering
787*38fd1498Szrj of the dominance tree (that is already available in order to speed up
788*38fd1498Szrj queries). For each def, we have the interval given by the dfs number on
789*38fd1498Szrj entry to and on exit from the corresponding subtree in the dominance tree.
790*38fd1498Szrj The nearest dominator for a given use is the smallest of these intervals
791*38fd1498Szrj that contains entry and exit dfs numbers for the basic block with the use.
792*38fd1498Szrj If we store the bounds for all the uses to an array and sort it, we can
793*38fd1498Szrj locate the nearest dominating def in logarithmic time by binary search.*/
794*38fd1498Szrj bitmap_ior (to_remove, kills, phis);
795*38fd1498Szrj n_defs = bitmap_count_bits (to_remove);
796*38fd1498Szrj defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1);
797*38fd1498Szrj defs[0].bb_index = 1;
798*38fd1498Szrj defs[0].dfs_num = 0;
799*38fd1498Szrj adef = 1;
800*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi)
801*38fd1498Szrj {
802*38fd1498Szrj def_bb = BASIC_BLOCK_FOR_FN (cfun, i);
803*38fd1498Szrj defs[adef].bb_index = i;
804*38fd1498Szrj defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb);
805*38fd1498Szrj defs[adef + 1].bb_index = i;
806*38fd1498Szrj defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb);
807*38fd1498Szrj adef += 2;
808*38fd1498Szrj }
809*38fd1498Szrj BITMAP_FREE (to_remove);
810*38fd1498Szrj gcc_assert (adef == 2 * n_defs + 1);
811*38fd1498Szrj qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum);
812*38fd1498Szrj gcc_assert (defs[0].bb_index == 1);
813*38fd1498Szrj
814*38fd1498Szrj /* Now each DEFS entry contains the number of the basic block to that the
815*38fd1498Szrj dfs number corresponds. Change them to the number of basic block that
816*38fd1498Szrj corresponds to the interval following the dfs number. Also, for the
817*38fd1498Szrj dfs_out numbers, increase the dfs number by one (so that it corresponds
818*38fd1498Szrj to the start of the following interval, not to the end of the current
819*38fd1498Szrj one). We use WORKLIST as a stack. */
820*38fd1498Szrj auto_vec<int> worklist (n_defs + 1);
821*38fd1498Szrj worklist.quick_push (1);
822*38fd1498Szrj top = 1;
823*38fd1498Szrj n_defs = 1;
824*38fd1498Szrj for (i = 1; i < adef; i++)
825*38fd1498Szrj {
826*38fd1498Szrj b = defs[i].bb_index;
827*38fd1498Szrj if (b == top)
828*38fd1498Szrj {
829*38fd1498Szrj /* This is a closing element. Interval corresponding to the top
830*38fd1498Szrj of the stack after removing it follows. */
831*38fd1498Szrj worklist.pop ();
832*38fd1498Szrj top = worklist[worklist.length () - 1];
833*38fd1498Szrj defs[n_defs].bb_index = top;
834*38fd1498Szrj defs[n_defs].dfs_num = defs[i].dfs_num + 1;
835*38fd1498Szrj }
836*38fd1498Szrj else
837*38fd1498Szrj {
838*38fd1498Szrj /* Opening element. Nothing to do, just push it to the stack and move
839*38fd1498Szrj it to the correct position. */
840*38fd1498Szrj defs[n_defs].bb_index = defs[i].bb_index;
841*38fd1498Szrj defs[n_defs].dfs_num = defs[i].dfs_num;
842*38fd1498Szrj worklist.quick_push (b);
843*38fd1498Szrj top = b;
844*38fd1498Szrj }
845*38fd1498Szrj
846*38fd1498Szrj /* If this interval starts at the same point as the previous one, cancel
847*38fd1498Szrj the previous one. */
848*38fd1498Szrj if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num)
849*38fd1498Szrj defs[n_defs - 1].bb_index = defs[n_defs].bb_index;
850*38fd1498Szrj else
851*38fd1498Szrj n_defs++;
852*38fd1498Szrj }
853*38fd1498Szrj worklist.pop ();
854*38fd1498Szrj gcc_assert (worklist.is_empty ());
855*38fd1498Szrj
856*38fd1498Szrj /* Now process the uses. */
857*38fd1498Szrj live_phis = BITMAP_ALLOC (NULL);
858*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi)
859*38fd1498Szrj {
860*38fd1498Szrj worklist.safe_push (i);
861*38fd1498Szrj }
862*38fd1498Szrj
863*38fd1498Szrj while (!worklist.is_empty ())
864*38fd1498Szrj {
865*38fd1498Szrj b = worklist.pop ();
866*38fd1498Szrj if (b == ENTRY_BLOCK)
867*38fd1498Szrj continue;
868*38fd1498Szrj
869*38fd1498Szrj /* If there is a phi node in USE_BB, it is made live. Otherwise,
870*38fd1498Szrj find the def that dominates the immediate dominator of USE_BB
871*38fd1498Szrj (the kill in USE_BB does not dominate the use). */
872*38fd1498Szrj if (bitmap_bit_p (phis, b))
873*38fd1498Szrj p = b;
874*38fd1498Szrj else
875*38fd1498Szrj {
876*38fd1498Szrj use_bb = get_immediate_dominator (CDI_DOMINATORS,
877*38fd1498Szrj BASIC_BLOCK_FOR_FN (cfun, b));
878*38fd1498Szrj p = find_dfsnum_interval (defs, n_defs,
879*38fd1498Szrj bb_dom_dfs_in (CDI_DOMINATORS, use_bb));
880*38fd1498Szrj if (!bitmap_bit_p (phis, p))
881*38fd1498Szrj continue;
882*38fd1498Szrj }
883*38fd1498Szrj
884*38fd1498Szrj /* If the phi node is already live, there is nothing to do. */
885*38fd1498Szrj if (!bitmap_set_bit (live_phis, p))
886*38fd1498Szrj continue;
887*38fd1498Szrj
888*38fd1498Szrj /* Add the new uses to the worklist. */
889*38fd1498Szrj def_bb = BASIC_BLOCK_FOR_FN (cfun, p);
890*38fd1498Szrj FOR_EACH_EDGE (e, ei, def_bb->preds)
891*38fd1498Szrj {
892*38fd1498Szrj u = e->src->index;
893*38fd1498Szrj if (bitmap_bit_p (uses, u))
894*38fd1498Szrj continue;
895*38fd1498Szrj
896*38fd1498Szrj /* In case there is a kill directly in the use block, do not record
897*38fd1498Szrj the use (this is also necessary for correctness, as we assume that
898*38fd1498Szrj uses dominated by a def directly in their block have been filtered
899*38fd1498Szrj out before). */
900*38fd1498Szrj if (bitmap_bit_p (kills, u))
901*38fd1498Szrj continue;
902*38fd1498Szrj
903*38fd1498Szrj bitmap_set_bit (uses, u);
904*38fd1498Szrj worklist.safe_push (u);
905*38fd1498Szrj }
906*38fd1498Szrj }
907*38fd1498Szrj
908*38fd1498Szrj bitmap_copy (phis, live_phis);
909*38fd1498Szrj BITMAP_FREE (live_phis);
910*38fd1498Szrj free (defs);
911*38fd1498Szrj }
912*38fd1498Szrj
913*38fd1498Szrj /* Return the set of blocks where variable VAR is defined and the blocks
914*38fd1498Szrj where VAR is live on entry (livein). Return NULL, if no entry is
915*38fd1498Szrj found in DEF_BLOCKS. */
916*38fd1498Szrj
917*38fd1498Szrj static inline def_blocks *
find_def_blocks_for(tree var)918*38fd1498Szrj find_def_blocks_for (tree var)
919*38fd1498Szrj {
920*38fd1498Szrj def_blocks *p = &get_common_info (var)->def_blocks;
921*38fd1498Szrj if (!p->def_blocks)
922*38fd1498Szrj return NULL;
923*38fd1498Szrj return p;
924*38fd1498Szrj }
925*38fd1498Szrj
926*38fd1498Szrj
927*38fd1498Szrj /* Marks phi node PHI in basic block BB for rewrite. */
928*38fd1498Szrj
929*38fd1498Szrj static void
mark_phi_for_rewrite(basic_block bb,gphi * phi)930*38fd1498Szrj mark_phi_for_rewrite (basic_block bb, gphi *phi)
931*38fd1498Szrj {
932*38fd1498Szrj vec<gphi *> phis;
933*38fd1498Szrj unsigned n, idx = bb->index;
934*38fd1498Szrj
935*38fd1498Szrj if (rewrite_uses_p (phi))
936*38fd1498Szrj return;
937*38fd1498Szrj
938*38fd1498Szrj set_rewrite_uses (phi, true);
939*38fd1498Szrj
940*38fd1498Szrj if (!blocks_with_phis_to_rewrite)
941*38fd1498Szrj return;
942*38fd1498Szrj
943*38fd1498Szrj bitmap_set_bit (blocks_with_phis_to_rewrite, idx);
944*38fd1498Szrj
945*38fd1498Szrj n = (unsigned) last_basic_block_for_fn (cfun) + 1;
946*38fd1498Szrj if (phis_to_rewrite.length () < n)
947*38fd1498Szrj phis_to_rewrite.safe_grow_cleared (n);
948*38fd1498Szrj
949*38fd1498Szrj phis = phis_to_rewrite[idx];
950*38fd1498Szrj phis.reserve (10);
951*38fd1498Szrj
952*38fd1498Szrj phis.safe_push (phi);
953*38fd1498Szrj phis_to_rewrite[idx] = phis;
954*38fd1498Szrj }
955*38fd1498Szrj
956*38fd1498Szrj /* Insert PHI nodes for variable VAR using the iterated dominance
957*38fd1498Szrj frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
958*38fd1498Szrj function assumes that the caller is incrementally updating the
959*38fd1498Szrj existing SSA form, in which case VAR may be an SSA name instead of
960*38fd1498Szrj a symbol.
961*38fd1498Szrj
962*38fd1498Szrj PHI_INSERTION_POINTS is updated to reflect nodes that already had a
963*38fd1498Szrj PHI node for VAR. On exit, only the nodes that received a PHI node
964*38fd1498Szrj for VAR will be present in PHI_INSERTION_POINTS. */
965*38fd1498Szrj
966*38fd1498Szrj static void
insert_phi_nodes_for(tree var,bitmap phi_insertion_points,bool update_p)967*38fd1498Szrj insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
968*38fd1498Szrj {
969*38fd1498Szrj unsigned bb_index;
970*38fd1498Szrj edge e;
971*38fd1498Szrj gphi *phi;
972*38fd1498Szrj basic_block bb;
973*38fd1498Szrj bitmap_iterator bi;
974*38fd1498Szrj def_blocks *def_map = find_def_blocks_for (var);
975*38fd1498Szrj
976*38fd1498Szrj /* Remove the blocks where we already have PHI nodes for VAR. */
977*38fd1498Szrj bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
978*38fd1498Szrj
979*38fd1498Szrj /* Remove obviously useless phi nodes. */
980*38fd1498Szrj prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks,
981*38fd1498Szrj def_map->livein_blocks);
982*38fd1498Szrj
983*38fd1498Szrj /* And insert the PHI nodes. */
984*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
985*38fd1498Szrj {
986*38fd1498Szrj bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
987*38fd1498Szrj if (update_p)
988*38fd1498Szrj mark_block_for_update (bb);
989*38fd1498Szrj
990*38fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
991*38fd1498Szrj {
992*38fd1498Szrj fprintf (dump_file, "creating PHI node in block #%d for ", bb_index);
993*38fd1498Szrj print_generic_expr (dump_file, var, TDF_SLIM);
994*38fd1498Szrj fprintf (dump_file, "\n");
995*38fd1498Szrj }
996*38fd1498Szrj phi = NULL;
997*38fd1498Szrj
998*38fd1498Szrj if (TREE_CODE (var) == SSA_NAME)
999*38fd1498Szrj {
1000*38fd1498Szrj /* If we are rewriting SSA names, create the LHS of the PHI
1001*38fd1498Szrj node by duplicating VAR. This is useful in the case of
1002*38fd1498Szrj pointers, to also duplicate pointer attributes (alias
1003*38fd1498Szrj information, in particular). */
1004*38fd1498Szrj edge_iterator ei;
1005*38fd1498Szrj tree new_lhs;
1006*38fd1498Szrj
1007*38fd1498Szrj gcc_checking_assert (update_p);
1008*38fd1498Szrj new_lhs = duplicate_ssa_name (var, NULL);
1009*38fd1498Szrj phi = create_phi_node (new_lhs, bb);
1010*38fd1498Szrj add_new_name_mapping (new_lhs, var);
1011*38fd1498Szrj
1012*38fd1498Szrj /* Add VAR to every argument slot of PHI. We need VAR in
1013*38fd1498Szrj every argument so that rewrite_update_phi_arguments knows
1014*38fd1498Szrj which name is this PHI node replacing. If VAR is a
1015*38fd1498Szrj symbol marked for renaming, this is not necessary, the
1016*38fd1498Szrj renamer will use the symbol on the LHS to get its
1017*38fd1498Szrj reaching definition. */
1018*38fd1498Szrj FOR_EACH_EDGE (e, ei, bb->preds)
1019*38fd1498Szrj add_phi_arg (phi, var, e, UNKNOWN_LOCATION);
1020*38fd1498Szrj }
1021*38fd1498Szrj else
1022*38fd1498Szrj {
1023*38fd1498Szrj tree tracked_var;
1024*38fd1498Szrj
1025*38fd1498Szrj gcc_checking_assert (DECL_P (var));
1026*38fd1498Szrj phi = create_phi_node (var, bb);
1027*38fd1498Szrj
1028*38fd1498Szrj tracked_var = target_for_debug_bind (var);
1029*38fd1498Szrj if (tracked_var)
1030*38fd1498Szrj {
1031*38fd1498Szrj gimple *note = gimple_build_debug_bind (tracked_var,
1032*38fd1498Szrj PHI_RESULT (phi),
1033*38fd1498Szrj phi);
1034*38fd1498Szrj gimple_stmt_iterator si = gsi_after_labels (bb);
1035*38fd1498Szrj gsi_insert_before (&si, note, GSI_SAME_STMT);
1036*38fd1498Szrj }
1037*38fd1498Szrj }
1038*38fd1498Szrj
1039*38fd1498Szrj /* Mark this PHI node as interesting for update_ssa. */
1040*38fd1498Szrj set_register_defs (phi, true);
1041*38fd1498Szrj mark_phi_for_rewrite (bb, phi);
1042*38fd1498Szrj }
1043*38fd1498Szrj }
1044*38fd1498Szrj
1045*38fd1498Szrj /* Sort var_infos after DECL_UID of their var. */
1046*38fd1498Szrj
1047*38fd1498Szrj static int
insert_phi_nodes_compare_var_infos(const void * a,const void * b)1048*38fd1498Szrj insert_phi_nodes_compare_var_infos (const void *a, const void *b)
1049*38fd1498Szrj {
1050*38fd1498Szrj const var_info *defa = *(var_info * const *)a;
1051*38fd1498Szrj const var_info *defb = *(var_info * const *)b;
1052*38fd1498Szrj if (DECL_UID (defa->var) < DECL_UID (defb->var))
1053*38fd1498Szrj return -1;
1054*38fd1498Szrj else
1055*38fd1498Szrj return 1;
1056*38fd1498Szrj }
1057*38fd1498Szrj
1058*38fd1498Szrj /* Insert PHI nodes at the dominance frontier of blocks with variable
1059*38fd1498Szrj definitions. DFS contains the dominance frontier information for
1060*38fd1498Szrj the flowgraph. */
1061*38fd1498Szrj
1062*38fd1498Szrj static void
insert_phi_nodes(bitmap_head * dfs)1063*38fd1498Szrj insert_phi_nodes (bitmap_head *dfs)
1064*38fd1498Szrj {
1065*38fd1498Szrj hash_table<var_info_hasher>::iterator hi;
1066*38fd1498Szrj unsigned i;
1067*38fd1498Szrj var_info *info;
1068*38fd1498Szrj
1069*38fd1498Szrj timevar_push (TV_TREE_INSERT_PHI_NODES);
1070*38fd1498Szrj
1071*38fd1498Szrj /* When the gimplifier introduces SSA names it cannot easily avoid
1072*38fd1498Szrj situations where abnormal edges added by CFG construction break
1073*38fd1498Szrj the use-def dominance requirement. For this case rewrite SSA
1074*38fd1498Szrj names with broken use-def dominance out-of-SSA and register them
1075*38fd1498Szrj for PHI insertion. We only need to do this if abnormal edges
1076*38fd1498Szrj can appear in the function. */
1077*38fd1498Szrj tree name;
1078*38fd1498Szrj if (cfun->calls_setjmp
1079*38fd1498Szrj || cfun->has_nonlocal_label)
1080*38fd1498Szrj FOR_EACH_SSA_NAME (i, name, cfun)
1081*38fd1498Szrj {
1082*38fd1498Szrj gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1083*38fd1498Szrj if (SSA_NAME_IS_DEFAULT_DEF (name))
1084*38fd1498Szrj continue;
1085*38fd1498Szrj
1086*38fd1498Szrj basic_block def_bb = gimple_bb (def_stmt);
1087*38fd1498Szrj imm_use_iterator it;
1088*38fd1498Szrj gimple *use_stmt;
1089*38fd1498Szrj bool need_phis = false;
1090*38fd1498Szrj FOR_EACH_IMM_USE_STMT (use_stmt, it, name)
1091*38fd1498Szrj {
1092*38fd1498Szrj basic_block use_bb = gimple_bb (use_stmt);
1093*38fd1498Szrj if (use_bb != def_bb
1094*38fd1498Szrj && ! dominated_by_p (CDI_DOMINATORS, use_bb, def_bb))
1095*38fd1498Szrj need_phis = true;
1096*38fd1498Szrj }
1097*38fd1498Szrj if (need_phis)
1098*38fd1498Szrj {
1099*38fd1498Szrj tree var = create_tmp_reg (TREE_TYPE (name));
1100*38fd1498Szrj use_operand_p use_p;
1101*38fd1498Szrj FOR_EACH_IMM_USE_STMT (use_stmt, it, name)
1102*38fd1498Szrj {
1103*38fd1498Szrj basic_block use_bb = gimple_bb (use_stmt);
1104*38fd1498Szrj FOR_EACH_IMM_USE_ON_STMT (use_p, it)
1105*38fd1498Szrj SET_USE (use_p, var);
1106*38fd1498Szrj update_stmt (use_stmt);
1107*38fd1498Szrj set_livein_block (var, use_bb);
1108*38fd1498Szrj set_rewrite_uses (use_stmt, true);
1109*38fd1498Szrj bitmap_set_bit (interesting_blocks, use_bb->index);
1110*38fd1498Szrj }
1111*38fd1498Szrj def_operand_p def_p;
1112*38fd1498Szrj ssa_op_iter dit;
1113*38fd1498Szrj FOR_EACH_SSA_DEF_OPERAND (def_p, def_stmt, dit, SSA_OP_DEF)
1114*38fd1498Szrj if (DEF_FROM_PTR (def_p) == name)
1115*38fd1498Szrj SET_DEF (def_p, var);
1116*38fd1498Szrj update_stmt (def_stmt);
1117*38fd1498Szrj set_def_block (var, def_bb, false);
1118*38fd1498Szrj set_register_defs (def_stmt, true);
1119*38fd1498Szrj bitmap_set_bit (interesting_blocks, def_bb->index);
1120*38fd1498Szrj release_ssa_name (name);
1121*38fd1498Szrj }
1122*38fd1498Szrj }
1123*38fd1498Szrj
1124*38fd1498Szrj auto_vec<var_info *> vars (var_infos->elements ());
1125*38fd1498Szrj FOR_EACH_HASH_TABLE_ELEMENT (*var_infos, info, var_info_p, hi)
1126*38fd1498Szrj if (info->info.need_phi_state != NEED_PHI_STATE_NO)
1127*38fd1498Szrj vars.quick_push (info);
1128*38fd1498Szrj
1129*38fd1498Szrj /* Do two stages to avoid code generation differences for UID
1130*38fd1498Szrj differences but no UID ordering differences. */
1131*38fd1498Szrj vars.qsort (insert_phi_nodes_compare_var_infos);
1132*38fd1498Szrj
1133*38fd1498Szrj FOR_EACH_VEC_ELT (vars, i, info)
1134*38fd1498Szrj {
1135*38fd1498Szrj bitmap idf = compute_idf (info->info.def_blocks.def_blocks, dfs);
1136*38fd1498Szrj insert_phi_nodes_for (info->var, idf, false);
1137*38fd1498Szrj BITMAP_FREE (idf);
1138*38fd1498Szrj }
1139*38fd1498Szrj
1140*38fd1498Szrj timevar_pop (TV_TREE_INSERT_PHI_NODES);
1141*38fd1498Szrj }
1142*38fd1498Szrj
1143*38fd1498Szrj
1144*38fd1498Szrj /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1145*38fd1498Szrj register DEF (an SSA_NAME) to be a new definition for SYM. */
1146*38fd1498Szrj
1147*38fd1498Szrj static void
register_new_def(tree def,tree sym)1148*38fd1498Szrj register_new_def (tree def, tree sym)
1149*38fd1498Szrj {
1150*38fd1498Szrj common_info *info = get_common_info (sym);
1151*38fd1498Szrj tree currdef;
1152*38fd1498Szrj
1153*38fd1498Szrj /* If this variable is set in a single basic block and all uses are
1154*38fd1498Szrj dominated by the set(s) in that single basic block, then there is
1155*38fd1498Szrj no reason to record anything for this variable in the block local
1156*38fd1498Szrj definition stacks. Doing so just wastes time and memory.
1157*38fd1498Szrj
1158*38fd1498Szrj This is the same test to prune the set of variables which may
1159*38fd1498Szrj need PHI nodes. So we just use that information since it's already
1160*38fd1498Szrj computed and available for us to use. */
1161*38fd1498Szrj if (info->need_phi_state == NEED_PHI_STATE_NO)
1162*38fd1498Szrj {
1163*38fd1498Szrj info->current_def = def;
1164*38fd1498Szrj return;
1165*38fd1498Szrj }
1166*38fd1498Szrj
1167*38fd1498Szrj currdef = info->current_def;
1168*38fd1498Szrj
1169*38fd1498Szrj /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1170*38fd1498Szrj SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM
1171*38fd1498Szrj in the stack so that we know which symbol is being defined by
1172*38fd1498Szrj this SSA name when we unwind the stack. */
1173*38fd1498Szrj if (currdef && !is_gimple_reg (sym))
1174*38fd1498Szrj block_defs_stack.safe_push (sym);
1175*38fd1498Szrj
1176*38fd1498Szrj /* Push the current reaching definition into BLOCK_DEFS_STACK. This
1177*38fd1498Szrj stack is later used by the dominator tree callbacks to restore
1178*38fd1498Szrj the reaching definitions for all the variables defined in the
1179*38fd1498Szrj block after a recursive visit to all its immediately dominated
1180*38fd1498Szrj blocks. If there is no current reaching definition, then just
1181*38fd1498Szrj record the underlying _DECL node. */
1182*38fd1498Szrj block_defs_stack.safe_push (currdef ? currdef : sym);
1183*38fd1498Szrj
1184*38fd1498Szrj /* Set the current reaching definition for SYM to be DEF. */
1185*38fd1498Szrj info->current_def = def;
1186*38fd1498Szrj }
1187*38fd1498Szrj
1188*38fd1498Szrj
1189*38fd1498Szrj /* Perform a depth-first traversal of the dominator tree looking for
1190*38fd1498Szrj variables to rename. BB is the block where to start searching.
1191*38fd1498Szrj Renaming is a five step process:
1192*38fd1498Szrj
1193*38fd1498Szrj 1- Every definition made by PHI nodes at the start of the blocks is
1194*38fd1498Szrj registered as the current definition for the corresponding variable.
1195*38fd1498Szrj
1196*38fd1498Szrj 2- Every statement in BB is rewritten. USE and VUSE operands are
1197*38fd1498Szrj rewritten with their corresponding reaching definition. DEF and
1198*38fd1498Szrj VDEF targets are registered as new definitions.
1199*38fd1498Szrj
1200*38fd1498Szrj 3- All the PHI nodes in successor blocks of BB are visited. The
1201*38fd1498Szrj argument corresponding to BB is replaced with its current reaching
1202*38fd1498Szrj definition.
1203*38fd1498Szrj
1204*38fd1498Szrj 4- Recursively rewrite every dominator child block of BB.
1205*38fd1498Szrj
1206*38fd1498Szrj 5- Restore (in reverse order) the current reaching definition for every
1207*38fd1498Szrj new definition introduced in this block. This is done so that when
1208*38fd1498Szrj we return from the recursive call, all the current reaching
1209*38fd1498Szrj definitions are restored to the names that were valid in the
1210*38fd1498Szrj dominator parent of BB. */
1211*38fd1498Szrj
1212*38fd1498Szrj /* Return the current definition for variable VAR. If none is found,
1213*38fd1498Szrj create a new SSA name to act as the zeroth definition for VAR. */
1214*38fd1498Szrj
1215*38fd1498Szrj static tree
get_reaching_def(tree var)1216*38fd1498Szrj get_reaching_def (tree var)
1217*38fd1498Szrj {
1218*38fd1498Szrj common_info *info = get_common_info (var);
1219*38fd1498Szrj tree currdef;
1220*38fd1498Szrj
1221*38fd1498Szrj /* Lookup the current reaching definition for VAR. */
1222*38fd1498Szrj currdef = info->current_def;
1223*38fd1498Szrj
1224*38fd1498Szrj /* If there is no reaching definition for VAR, create and register a
1225*38fd1498Szrj default definition for it (if needed). */
1226*38fd1498Szrj if (currdef == NULL_TREE)
1227*38fd1498Szrj {
1228*38fd1498Szrj tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
1229*38fd1498Szrj if (! sym)
1230*38fd1498Szrj sym = create_tmp_reg (TREE_TYPE (var));
1231*38fd1498Szrj currdef = get_or_create_ssa_default_def (cfun, sym);
1232*38fd1498Szrj }
1233*38fd1498Szrj
1234*38fd1498Szrj /* Return the current reaching definition for VAR, or the default
1235*38fd1498Szrj definition, if we had to create one. */
1236*38fd1498Szrj return currdef;
1237*38fd1498Szrj }
1238*38fd1498Szrj
1239*38fd1498Szrj
1240*38fd1498Szrj /* Helper function for rewrite_stmt. Rewrite uses in a debug stmt. */
1241*38fd1498Szrj
1242*38fd1498Szrj static void
rewrite_debug_stmt_uses(gimple * stmt)1243*38fd1498Szrj rewrite_debug_stmt_uses (gimple *stmt)
1244*38fd1498Szrj {
1245*38fd1498Szrj use_operand_p use_p;
1246*38fd1498Szrj ssa_op_iter iter;
1247*38fd1498Szrj bool update = false;
1248*38fd1498Szrj
1249*38fd1498Szrj FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1250*38fd1498Szrj {
1251*38fd1498Szrj tree var = USE_FROM_PTR (use_p), def;
1252*38fd1498Szrj common_info *info = get_common_info (var);
1253*38fd1498Szrj gcc_checking_assert (DECL_P (var));
1254*38fd1498Szrj def = info->current_def;
1255*38fd1498Szrj if (!def)
1256*38fd1498Szrj {
1257*38fd1498Szrj if (TREE_CODE (var) == PARM_DECL
1258*38fd1498Szrj && single_succ_p (ENTRY_BLOCK_PTR_FOR_FN (cfun)))
1259*38fd1498Szrj {
1260*38fd1498Szrj gimple_stmt_iterator gsi
1261*38fd1498Szrj =
1262*38fd1498Szrj gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1263*38fd1498Szrj int lim;
1264*38fd1498Szrj /* Search a few source bind stmts at the start of first bb to
1265*38fd1498Szrj see if a DEBUG_EXPR_DECL can't be reused. */
1266*38fd1498Szrj for (lim = 32;
1267*38fd1498Szrj !gsi_end_p (gsi) && lim > 0;
1268*38fd1498Szrj gsi_next (&gsi), lim--)
1269*38fd1498Szrj {
1270*38fd1498Szrj gimple *gstmt = gsi_stmt (gsi);
1271*38fd1498Szrj if (!gimple_debug_source_bind_p (gstmt))
1272*38fd1498Szrj break;
1273*38fd1498Szrj if (gimple_debug_source_bind_get_value (gstmt) == var)
1274*38fd1498Szrj {
1275*38fd1498Szrj def = gimple_debug_source_bind_get_var (gstmt);
1276*38fd1498Szrj if (TREE_CODE (def) == DEBUG_EXPR_DECL)
1277*38fd1498Szrj break;
1278*38fd1498Szrj else
1279*38fd1498Szrj def = NULL_TREE;
1280*38fd1498Szrj }
1281*38fd1498Szrj }
1282*38fd1498Szrj /* If not, add a new source bind stmt. */
1283*38fd1498Szrj if (def == NULL_TREE)
1284*38fd1498Szrj {
1285*38fd1498Szrj gimple *def_temp;
1286*38fd1498Szrj def = make_node (DEBUG_EXPR_DECL);
1287*38fd1498Szrj def_temp = gimple_build_debug_source_bind (def, var, NULL);
1288*38fd1498Szrj DECL_ARTIFICIAL (def) = 1;
1289*38fd1498Szrj TREE_TYPE (def) = TREE_TYPE (var);
1290*38fd1498Szrj SET_DECL_MODE (def, DECL_MODE (var));
1291*38fd1498Szrj gsi =
1292*38fd1498Szrj gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1293*38fd1498Szrj gsi_insert_before (&gsi, def_temp, GSI_SAME_STMT);
1294*38fd1498Szrj }
1295*38fd1498Szrj update = true;
1296*38fd1498Szrj }
1297*38fd1498Szrj }
1298*38fd1498Szrj else
1299*38fd1498Szrj {
1300*38fd1498Szrj /* Check if info->current_def can be trusted. */
1301*38fd1498Szrj basic_block bb = gimple_bb (stmt);
1302*38fd1498Szrj basic_block def_bb
1303*38fd1498Szrj = SSA_NAME_IS_DEFAULT_DEF (def)
1304*38fd1498Szrj ? NULL : gimple_bb (SSA_NAME_DEF_STMT (def));
1305*38fd1498Szrj
1306*38fd1498Szrj /* If definition is in current bb, it is fine. */
1307*38fd1498Szrj if (bb == def_bb)
1308*38fd1498Szrj ;
1309*38fd1498Szrj /* If definition bb doesn't dominate the current bb,
1310*38fd1498Szrj it can't be used. */
1311*38fd1498Szrj else if (def_bb && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
1312*38fd1498Szrj def = NULL;
1313*38fd1498Szrj /* If there is just one definition and dominates the current
1314*38fd1498Szrj bb, it is fine. */
1315*38fd1498Szrj else if (info->need_phi_state == NEED_PHI_STATE_NO)
1316*38fd1498Szrj ;
1317*38fd1498Szrj else
1318*38fd1498Szrj {
1319*38fd1498Szrj def_blocks *db_p = get_def_blocks_for (info);
1320*38fd1498Szrj
1321*38fd1498Szrj /* If there are some non-debug uses in the current bb,
1322*38fd1498Szrj it is fine. */
1323*38fd1498Szrj if (bitmap_bit_p (db_p->livein_blocks, bb->index))
1324*38fd1498Szrj ;
1325*38fd1498Szrj /* Otherwise give up for now. */
1326*38fd1498Szrj else
1327*38fd1498Szrj def = NULL;
1328*38fd1498Szrj }
1329*38fd1498Szrj }
1330*38fd1498Szrj if (def == NULL)
1331*38fd1498Szrj {
1332*38fd1498Szrj gimple_debug_bind_reset_value (stmt);
1333*38fd1498Szrj update_stmt (stmt);
1334*38fd1498Szrj return;
1335*38fd1498Szrj }
1336*38fd1498Szrj SET_USE (use_p, def);
1337*38fd1498Szrj }
1338*38fd1498Szrj if (update)
1339*38fd1498Szrj update_stmt (stmt);
1340*38fd1498Szrj }
1341*38fd1498Szrj
1342*38fd1498Szrj /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1343*38fd1498Szrj the block with its immediate reaching definitions. Update the current
1344*38fd1498Szrj definition of a variable when a new real or virtual definition is found. */
1345*38fd1498Szrj
1346*38fd1498Szrj static void
rewrite_stmt(gimple_stmt_iterator * si)1347*38fd1498Szrj rewrite_stmt (gimple_stmt_iterator *si)
1348*38fd1498Szrj {
1349*38fd1498Szrj use_operand_p use_p;
1350*38fd1498Szrj def_operand_p def_p;
1351*38fd1498Szrj ssa_op_iter iter;
1352*38fd1498Szrj gimple *stmt = gsi_stmt (*si);
1353*38fd1498Szrj
1354*38fd1498Szrj /* If mark_def_sites decided that we don't need to rewrite this
1355*38fd1498Szrj statement, ignore it. */
1356*38fd1498Szrj gcc_assert (blocks_to_update == NULL);
1357*38fd1498Szrj if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
1358*38fd1498Szrj return;
1359*38fd1498Szrj
1360*38fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
1361*38fd1498Szrj {
1362*38fd1498Szrj fprintf (dump_file, "Renaming statement ");
1363*38fd1498Szrj print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1364*38fd1498Szrj fprintf (dump_file, "\n");
1365*38fd1498Szrj }
1366*38fd1498Szrj
1367*38fd1498Szrj /* Step 1. Rewrite USES in the statement. */
1368*38fd1498Szrj if (rewrite_uses_p (stmt))
1369*38fd1498Szrj {
1370*38fd1498Szrj if (is_gimple_debug (stmt))
1371*38fd1498Szrj rewrite_debug_stmt_uses (stmt);
1372*38fd1498Szrj else
1373*38fd1498Szrj FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1374*38fd1498Szrj {
1375*38fd1498Szrj tree var = USE_FROM_PTR (use_p);
1376*38fd1498Szrj if (TREE_CODE (var) == SSA_NAME)
1377*38fd1498Szrj continue;
1378*38fd1498Szrj gcc_checking_assert (DECL_P (var));
1379*38fd1498Szrj SET_USE (use_p, get_reaching_def (var));
1380*38fd1498Szrj }
1381*38fd1498Szrj }
1382*38fd1498Szrj
1383*38fd1498Szrj /* Step 2. Register the statement's DEF operands. */
1384*38fd1498Szrj if (register_defs_p (stmt))
1385*38fd1498Szrj FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1386*38fd1498Szrj {
1387*38fd1498Szrj tree var = DEF_FROM_PTR (def_p);
1388*38fd1498Szrj tree name;
1389*38fd1498Szrj tree tracked_var;
1390*38fd1498Szrj
1391*38fd1498Szrj if (TREE_CODE (var) == SSA_NAME)
1392*38fd1498Szrj continue;
1393*38fd1498Szrj gcc_checking_assert (DECL_P (var));
1394*38fd1498Szrj
1395*38fd1498Szrj if (gimple_clobber_p (stmt)
1396*38fd1498Szrj && is_gimple_reg (var))
1397*38fd1498Szrj {
1398*38fd1498Szrj /* If we rewrite a DECL into SSA form then drop its
1399*38fd1498Szrj clobber stmts and replace uses with a new default def. */
1400*38fd1498Szrj gcc_checking_assert (VAR_P (var) && !gimple_vdef (stmt));
1401*38fd1498Szrj gsi_replace (si, gimple_build_nop (), true);
1402*38fd1498Szrj register_new_def (get_or_create_ssa_default_def (cfun, var), var);
1403*38fd1498Szrj break;
1404*38fd1498Szrj }
1405*38fd1498Szrj
1406*38fd1498Szrj name = make_ssa_name (var, stmt);
1407*38fd1498Szrj SET_DEF (def_p, name);
1408*38fd1498Szrj register_new_def (DEF_FROM_PTR (def_p), var);
1409*38fd1498Szrj
1410*38fd1498Szrj tracked_var = target_for_debug_bind (var);
1411*38fd1498Szrj if (tracked_var)
1412*38fd1498Szrj {
1413*38fd1498Szrj gimple *note = gimple_build_debug_bind (tracked_var, name, stmt);
1414*38fd1498Szrj gsi_insert_after (si, note, GSI_SAME_STMT);
1415*38fd1498Szrj }
1416*38fd1498Szrj }
1417*38fd1498Szrj }
1418*38fd1498Szrj
1419*38fd1498Szrj
1420*38fd1498Szrj /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1421*38fd1498Szrj PHI nodes. For every PHI node found, add a new argument containing the
1422*38fd1498Szrj current reaching definition for the variable and the edge through which
1423*38fd1498Szrj that definition is reaching the PHI node. */
1424*38fd1498Szrj
1425*38fd1498Szrj static void
rewrite_add_phi_arguments(basic_block bb)1426*38fd1498Szrj rewrite_add_phi_arguments (basic_block bb)
1427*38fd1498Szrj {
1428*38fd1498Szrj edge e;
1429*38fd1498Szrj edge_iterator ei;
1430*38fd1498Szrj
1431*38fd1498Szrj FOR_EACH_EDGE (e, ei, bb->succs)
1432*38fd1498Szrj {
1433*38fd1498Szrj gphi *phi;
1434*38fd1498Szrj gphi_iterator gsi;
1435*38fd1498Szrj
1436*38fd1498Szrj for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
1437*38fd1498Szrj gsi_next (&gsi))
1438*38fd1498Szrj {
1439*38fd1498Szrj tree currdef, res, argvar;
1440*38fd1498Szrj location_t loc;
1441*38fd1498Szrj
1442*38fd1498Szrj phi = gsi.phi ();
1443*38fd1498Szrj res = gimple_phi_result (phi);
1444*38fd1498Szrj /* If we have pre-existing PHI (via the GIMPLE FE) its args may
1445*38fd1498Szrj be different vars than existing vars and they may be constants
1446*38fd1498Szrj as well. Note the following supports partial SSA for PHI args. */
1447*38fd1498Szrj argvar = gimple_phi_arg_def (phi, e->dest_idx);
1448*38fd1498Szrj if (argvar && ! DECL_P (argvar))
1449*38fd1498Szrj continue;
1450*38fd1498Szrj if (!argvar)
1451*38fd1498Szrj argvar = SSA_NAME_VAR (res);
1452*38fd1498Szrj currdef = get_reaching_def (argvar);
1453*38fd1498Szrj /* Virtual operand PHI args do not need a location. */
1454*38fd1498Szrj if (virtual_operand_p (res))
1455*38fd1498Szrj loc = UNKNOWN_LOCATION;
1456*38fd1498Szrj else
1457*38fd1498Szrj loc = gimple_location (SSA_NAME_DEF_STMT (currdef));
1458*38fd1498Szrj add_phi_arg (phi, currdef, e, loc);
1459*38fd1498Szrj }
1460*38fd1498Szrj }
1461*38fd1498Szrj }
1462*38fd1498Szrj
1463*38fd1498Szrj class rewrite_dom_walker : public dom_walker
1464*38fd1498Szrj {
1465*38fd1498Szrj public:
rewrite_dom_walker(cdi_direction direction)1466*38fd1498Szrj rewrite_dom_walker (cdi_direction direction)
1467*38fd1498Szrj : dom_walker (direction, ALL_BLOCKS, NULL) {}
1468*38fd1498Szrj
1469*38fd1498Szrj virtual edge before_dom_children (basic_block);
1470*38fd1498Szrj virtual void after_dom_children (basic_block);
1471*38fd1498Szrj };
1472*38fd1498Szrj
1473*38fd1498Szrj /* SSA Rewriting Step 1. Initialization, create a block local stack
1474*38fd1498Szrj of reaching definitions for new SSA names produced in this block
1475*38fd1498Szrj (BLOCK_DEFS). Register new definitions for every PHI node in the
1476*38fd1498Szrj block. */
1477*38fd1498Szrj
1478*38fd1498Szrj edge
before_dom_children(basic_block bb)1479*38fd1498Szrj rewrite_dom_walker::before_dom_children (basic_block bb)
1480*38fd1498Szrj {
1481*38fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
1482*38fd1498Szrj fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
1483*38fd1498Szrj
1484*38fd1498Szrj /* Mark the unwind point for this block. */
1485*38fd1498Szrj block_defs_stack.safe_push (NULL_TREE);
1486*38fd1498Szrj
1487*38fd1498Szrj /* Step 1. Register new definitions for every PHI node in the block.
1488*38fd1498Szrj Conceptually, all the PHI nodes are executed in parallel and each PHI
1489*38fd1498Szrj node introduces a new version for the associated variable. */
1490*38fd1498Szrj for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1491*38fd1498Szrj gsi_next (&gsi))
1492*38fd1498Szrj {
1493*38fd1498Szrj tree result = gimple_phi_result (gsi_stmt (gsi));
1494*38fd1498Szrj register_new_def (result, SSA_NAME_VAR (result));
1495*38fd1498Szrj }
1496*38fd1498Szrj
1497*38fd1498Szrj /* Step 2. Rewrite every variable used in each statement in the block
1498*38fd1498Szrj with its immediate reaching definitions. Update the current definition
1499*38fd1498Szrj of a variable when a new real or virtual definition is found. */
1500*38fd1498Szrj if (bitmap_bit_p (interesting_blocks, bb->index))
1501*38fd1498Szrj for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1502*38fd1498Szrj gsi_next (&gsi))
1503*38fd1498Szrj rewrite_stmt (&gsi);
1504*38fd1498Szrj
1505*38fd1498Szrj /* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
1506*38fd1498Szrj For every PHI node found, add a new argument containing the current
1507*38fd1498Szrj reaching definition for the variable and the edge through which that
1508*38fd1498Szrj definition is reaching the PHI node. */
1509*38fd1498Szrj rewrite_add_phi_arguments (bb);
1510*38fd1498Szrj
1511*38fd1498Szrj return NULL;
1512*38fd1498Szrj }
1513*38fd1498Szrj
1514*38fd1498Szrj
1515*38fd1498Szrj
1516*38fd1498Szrj /* Called after visiting all the statements in basic block BB and all
1517*38fd1498Szrj of its dominator children. Restore CURRDEFS to its original value. */
1518*38fd1498Szrj
1519*38fd1498Szrj void
after_dom_children(basic_block bb ATTRIBUTE_UNUSED)1520*38fd1498Szrj rewrite_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
1521*38fd1498Szrj {
1522*38fd1498Szrj /* Restore CURRDEFS to its original state. */
1523*38fd1498Szrj while (block_defs_stack.length () > 0)
1524*38fd1498Szrj {
1525*38fd1498Szrj tree tmp = block_defs_stack.pop ();
1526*38fd1498Szrj tree saved_def, var;
1527*38fd1498Szrj
1528*38fd1498Szrj if (tmp == NULL_TREE)
1529*38fd1498Szrj break;
1530*38fd1498Szrj
1531*38fd1498Szrj if (TREE_CODE (tmp) == SSA_NAME)
1532*38fd1498Szrj {
1533*38fd1498Szrj /* If we recorded an SSA_NAME, then make the SSA_NAME the
1534*38fd1498Szrj current definition of its underlying variable. Note that
1535*38fd1498Szrj if the SSA_NAME is not for a GIMPLE register, the symbol
1536*38fd1498Szrj being defined is stored in the next slot in the stack.
1537*38fd1498Szrj This mechanism is needed because an SSA name for a
1538*38fd1498Szrj non-register symbol may be the definition for more than
1539*38fd1498Szrj one symbol (e.g., SFTs, aliased variables, etc). */
1540*38fd1498Szrj saved_def = tmp;
1541*38fd1498Szrj var = SSA_NAME_VAR (saved_def);
1542*38fd1498Szrj if (!is_gimple_reg (var))
1543*38fd1498Szrj var = block_defs_stack.pop ();
1544*38fd1498Szrj }
1545*38fd1498Szrj else
1546*38fd1498Szrj {
1547*38fd1498Szrj /* If we recorded anything else, it must have been a _DECL
1548*38fd1498Szrj node and its current reaching definition must have been
1549*38fd1498Szrj NULL. */
1550*38fd1498Szrj saved_def = NULL;
1551*38fd1498Szrj var = tmp;
1552*38fd1498Szrj }
1553*38fd1498Szrj
1554*38fd1498Szrj get_common_info (var)->current_def = saved_def;
1555*38fd1498Szrj }
1556*38fd1498Szrj }
1557*38fd1498Szrj
1558*38fd1498Szrj
1559*38fd1498Szrj /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1560*38fd1498Szrj
1561*38fd1498Szrj DEBUG_FUNCTION void
debug_decl_set(bitmap set)1562*38fd1498Szrj debug_decl_set (bitmap set)
1563*38fd1498Szrj {
1564*38fd1498Szrj dump_decl_set (stderr, set);
1565*38fd1498Szrj fprintf (stderr, "\n");
1566*38fd1498Szrj }
1567*38fd1498Szrj
1568*38fd1498Szrj
1569*38fd1498Szrj /* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
1570*38fd1498Szrj stack up to a maximum of N levels. If N is -1, the whole stack is
1571*38fd1498Szrj dumped. New levels are created when the dominator tree traversal
1572*38fd1498Szrj used for renaming enters a new sub-tree. */
1573*38fd1498Szrj
1574*38fd1498Szrj void
dump_defs_stack(FILE * file,int n)1575*38fd1498Szrj dump_defs_stack (FILE *file, int n)
1576*38fd1498Szrj {
1577*38fd1498Szrj int i, j;
1578*38fd1498Szrj
1579*38fd1498Szrj fprintf (file, "\n\nRenaming stack");
1580*38fd1498Szrj if (n > 0)
1581*38fd1498Szrj fprintf (file, " (up to %d levels)", n);
1582*38fd1498Szrj fprintf (file, "\n\n");
1583*38fd1498Szrj
1584*38fd1498Szrj i = 1;
1585*38fd1498Szrj fprintf (file, "Level %d (current level)\n", i);
1586*38fd1498Szrj for (j = (int) block_defs_stack.length () - 1; j >= 0; j--)
1587*38fd1498Szrj {
1588*38fd1498Szrj tree name, var;
1589*38fd1498Szrj
1590*38fd1498Szrj name = block_defs_stack[j];
1591*38fd1498Szrj if (name == NULL_TREE)
1592*38fd1498Szrj {
1593*38fd1498Szrj i++;
1594*38fd1498Szrj if (n > 0 && i > n)
1595*38fd1498Szrj break;
1596*38fd1498Szrj fprintf (file, "\nLevel %d\n", i);
1597*38fd1498Szrj continue;
1598*38fd1498Szrj }
1599*38fd1498Szrj
1600*38fd1498Szrj if (DECL_P (name))
1601*38fd1498Szrj {
1602*38fd1498Szrj var = name;
1603*38fd1498Szrj name = NULL_TREE;
1604*38fd1498Szrj }
1605*38fd1498Szrj else
1606*38fd1498Szrj {
1607*38fd1498Szrj var = SSA_NAME_VAR (name);
1608*38fd1498Szrj if (!is_gimple_reg (var))
1609*38fd1498Szrj {
1610*38fd1498Szrj j--;
1611*38fd1498Szrj var = block_defs_stack[j];
1612*38fd1498Szrj }
1613*38fd1498Szrj }
1614*38fd1498Szrj
1615*38fd1498Szrj fprintf (file, " Previous CURRDEF (");
1616*38fd1498Szrj print_generic_expr (file, var);
1617*38fd1498Szrj fprintf (file, ") = ");
1618*38fd1498Szrj if (name)
1619*38fd1498Szrj print_generic_expr (file, name);
1620*38fd1498Szrj else
1621*38fd1498Szrj fprintf (file, "<NIL>");
1622*38fd1498Szrj fprintf (file, "\n");
1623*38fd1498Szrj }
1624*38fd1498Szrj }
1625*38fd1498Szrj
1626*38fd1498Szrj
1627*38fd1498Szrj /* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
1628*38fd1498Szrj stack up to a maximum of N levels. If N is -1, the whole stack is
1629*38fd1498Szrj dumped. New levels are created when the dominator tree traversal
1630*38fd1498Szrj used for renaming enters a new sub-tree. */
1631*38fd1498Szrj
1632*38fd1498Szrj DEBUG_FUNCTION void
debug_defs_stack(int n)1633*38fd1498Szrj debug_defs_stack (int n)
1634*38fd1498Szrj {
1635*38fd1498Szrj dump_defs_stack (stderr, n);
1636*38fd1498Szrj }
1637*38fd1498Szrj
1638*38fd1498Szrj
1639*38fd1498Szrj /* Dump the current reaching definition of every symbol to FILE. */
1640*38fd1498Szrj
1641*38fd1498Szrj void
dump_currdefs(FILE * file)1642*38fd1498Szrj dump_currdefs (FILE *file)
1643*38fd1498Szrj {
1644*38fd1498Szrj unsigned i;
1645*38fd1498Szrj tree var;
1646*38fd1498Szrj
1647*38fd1498Szrj if (symbols_to_rename.is_empty ())
1648*38fd1498Szrj return;
1649*38fd1498Szrj
1650*38fd1498Szrj fprintf (file, "\n\nCurrent reaching definitions\n\n");
1651*38fd1498Szrj FOR_EACH_VEC_ELT (symbols_to_rename, i, var)
1652*38fd1498Szrj {
1653*38fd1498Szrj common_info *info = get_common_info (var);
1654*38fd1498Szrj fprintf (file, "CURRDEF (");
1655*38fd1498Szrj print_generic_expr (file, var);
1656*38fd1498Szrj fprintf (file, ") = ");
1657*38fd1498Szrj if (info->current_def)
1658*38fd1498Szrj print_generic_expr (file, info->current_def);
1659*38fd1498Szrj else
1660*38fd1498Szrj fprintf (file, "<NIL>");
1661*38fd1498Szrj fprintf (file, "\n");
1662*38fd1498Szrj }
1663*38fd1498Szrj }
1664*38fd1498Szrj
1665*38fd1498Szrj
1666*38fd1498Szrj /* Dump the current reaching definition of every symbol to stderr. */
1667*38fd1498Szrj
1668*38fd1498Szrj DEBUG_FUNCTION void
debug_currdefs(void)1669*38fd1498Szrj debug_currdefs (void)
1670*38fd1498Szrj {
1671*38fd1498Szrj dump_currdefs (stderr);
1672*38fd1498Szrj }
1673*38fd1498Szrj
1674*38fd1498Szrj
1675*38fd1498Szrj /* Dump SSA information to FILE. */
1676*38fd1498Szrj
1677*38fd1498Szrj void
dump_tree_ssa(FILE * file)1678*38fd1498Szrj dump_tree_ssa (FILE *file)
1679*38fd1498Szrj {
1680*38fd1498Szrj const char *funcname
1681*38fd1498Szrj = lang_hooks.decl_printable_name (current_function_decl, 2);
1682*38fd1498Szrj
1683*38fd1498Szrj fprintf (file, "SSA renaming information for %s\n\n", funcname);
1684*38fd1498Szrj
1685*38fd1498Szrj dump_var_infos (file);
1686*38fd1498Szrj dump_defs_stack (file, -1);
1687*38fd1498Szrj dump_currdefs (file);
1688*38fd1498Szrj dump_tree_ssa_stats (file);
1689*38fd1498Szrj }
1690*38fd1498Szrj
1691*38fd1498Szrj
1692*38fd1498Szrj /* Dump SSA information to stderr. */
1693*38fd1498Szrj
1694*38fd1498Szrj DEBUG_FUNCTION void
debug_tree_ssa(void)1695*38fd1498Szrj debug_tree_ssa (void)
1696*38fd1498Szrj {
1697*38fd1498Szrj dump_tree_ssa (stderr);
1698*38fd1498Szrj }
1699*38fd1498Szrj
1700*38fd1498Szrj
1701*38fd1498Szrj /* Dump statistics for the hash table HTAB. */
1702*38fd1498Szrj
1703*38fd1498Szrj static void
htab_statistics(FILE * file,const hash_table<var_info_hasher> & htab)1704*38fd1498Szrj htab_statistics (FILE *file, const hash_table<var_info_hasher> &htab)
1705*38fd1498Szrj {
1706*38fd1498Szrj fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1707*38fd1498Szrj (long) htab.size (),
1708*38fd1498Szrj (long) htab.elements (),
1709*38fd1498Szrj htab.collisions ());
1710*38fd1498Szrj }
1711*38fd1498Szrj
1712*38fd1498Szrj
1713*38fd1498Szrj /* Dump SSA statistics on FILE. */
1714*38fd1498Szrj
1715*38fd1498Szrj void
dump_tree_ssa_stats(FILE * file)1716*38fd1498Szrj dump_tree_ssa_stats (FILE *file)
1717*38fd1498Szrj {
1718*38fd1498Szrj if (var_infos)
1719*38fd1498Szrj {
1720*38fd1498Szrj fprintf (file, "\nHash table statistics:\n");
1721*38fd1498Szrj fprintf (file, " var_infos: ");
1722*38fd1498Szrj htab_statistics (file, *var_infos);
1723*38fd1498Szrj fprintf (file, "\n");
1724*38fd1498Szrj }
1725*38fd1498Szrj }
1726*38fd1498Szrj
1727*38fd1498Szrj
1728*38fd1498Szrj /* Dump SSA statistics on stderr. */
1729*38fd1498Szrj
1730*38fd1498Szrj DEBUG_FUNCTION void
debug_tree_ssa_stats(void)1731*38fd1498Szrj debug_tree_ssa_stats (void)
1732*38fd1498Szrj {
1733*38fd1498Szrj dump_tree_ssa_stats (stderr);
1734*38fd1498Szrj }
1735*38fd1498Szrj
1736*38fd1498Szrj
1737*38fd1498Szrj /* Callback for htab_traverse to dump the VAR_INFOS hash table. */
1738*38fd1498Szrj
1739*38fd1498Szrj int
debug_var_infos_r(var_info ** slot,FILE * file)1740*38fd1498Szrj debug_var_infos_r (var_info **slot, FILE *file)
1741*38fd1498Szrj {
1742*38fd1498Szrj var_info *info = *slot;
1743*38fd1498Szrj
1744*38fd1498Szrj fprintf (file, "VAR: ");
1745*38fd1498Szrj print_generic_expr (file, info->var, dump_flags);
1746*38fd1498Szrj bitmap_print (file, info->info.def_blocks.def_blocks,
1747*38fd1498Szrj ", DEF_BLOCKS: { ", "}");
1748*38fd1498Szrj bitmap_print (file, info->info.def_blocks.livein_blocks,
1749*38fd1498Szrj ", LIVEIN_BLOCKS: { ", "}");
1750*38fd1498Szrj bitmap_print (file, info->info.def_blocks.phi_blocks,
1751*38fd1498Szrj ", PHI_BLOCKS: { ", "}\n");
1752*38fd1498Szrj
1753*38fd1498Szrj return 1;
1754*38fd1498Szrj }
1755*38fd1498Szrj
1756*38fd1498Szrj
1757*38fd1498Szrj /* Dump the VAR_INFOS hash table on FILE. */
1758*38fd1498Szrj
1759*38fd1498Szrj void
dump_var_infos(FILE * file)1760*38fd1498Szrj dump_var_infos (FILE *file)
1761*38fd1498Szrj {
1762*38fd1498Szrj fprintf (file, "\n\nDefinition and live-in blocks:\n\n");
1763*38fd1498Szrj if (var_infos)
1764*38fd1498Szrj var_infos->traverse <FILE *, debug_var_infos_r> (file);
1765*38fd1498Szrj }
1766*38fd1498Szrj
1767*38fd1498Szrj
1768*38fd1498Szrj /* Dump the VAR_INFOS hash table on stderr. */
1769*38fd1498Szrj
1770*38fd1498Szrj DEBUG_FUNCTION void
debug_var_infos(void)1771*38fd1498Szrj debug_var_infos (void)
1772*38fd1498Szrj {
1773*38fd1498Szrj dump_var_infos (stderr);
1774*38fd1498Szrj }
1775*38fd1498Szrj
1776*38fd1498Szrj
1777*38fd1498Szrj /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1778*38fd1498Szrj
1779*38fd1498Szrj static inline void
register_new_update_single(tree new_name,tree old_name)1780*38fd1498Szrj register_new_update_single (tree new_name, tree old_name)
1781*38fd1498Szrj {
1782*38fd1498Szrj common_info *info = get_common_info (old_name);
1783*38fd1498Szrj tree currdef = info->current_def;
1784*38fd1498Szrj
1785*38fd1498Szrj /* Push the current reaching definition into BLOCK_DEFS_STACK.
1786*38fd1498Szrj This stack is later used by the dominator tree callbacks to
1787*38fd1498Szrj restore the reaching definitions for all the variables
1788*38fd1498Szrj defined in the block after a recursive visit to all its
1789*38fd1498Szrj immediately dominated blocks. */
1790*38fd1498Szrj block_defs_stack.reserve (2);
1791*38fd1498Szrj block_defs_stack.quick_push (currdef);
1792*38fd1498Szrj block_defs_stack.quick_push (old_name);
1793*38fd1498Szrj
1794*38fd1498Szrj /* Set the current reaching definition for OLD_NAME to be
1795*38fd1498Szrj NEW_NAME. */
1796*38fd1498Szrj info->current_def = new_name;
1797*38fd1498Szrj }
1798*38fd1498Szrj
1799*38fd1498Szrj
1800*38fd1498Szrj /* Register NEW_NAME to be the new reaching definition for all the
1801*38fd1498Szrj names in OLD_NAMES. Used by the incremental SSA update routines to
1802*38fd1498Szrj replace old SSA names with new ones. */
1803*38fd1498Szrj
1804*38fd1498Szrj static inline void
register_new_update_set(tree new_name,bitmap old_names)1805*38fd1498Szrj register_new_update_set (tree new_name, bitmap old_names)
1806*38fd1498Szrj {
1807*38fd1498Szrj bitmap_iterator bi;
1808*38fd1498Szrj unsigned i;
1809*38fd1498Szrj
1810*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
1811*38fd1498Szrj register_new_update_single (new_name, ssa_name (i));
1812*38fd1498Szrj }
1813*38fd1498Szrj
1814*38fd1498Szrj
1815*38fd1498Szrj
1816*38fd1498Szrj /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1817*38fd1498Szrj it is a symbol marked for renaming, replace it with USE_P's current
1818*38fd1498Szrj reaching definition. */
1819*38fd1498Szrj
1820*38fd1498Szrj static inline void
maybe_replace_use(use_operand_p use_p)1821*38fd1498Szrj maybe_replace_use (use_operand_p use_p)
1822*38fd1498Szrj {
1823*38fd1498Szrj tree rdef = NULL_TREE;
1824*38fd1498Szrj tree use = USE_FROM_PTR (use_p);
1825*38fd1498Szrj tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1826*38fd1498Szrj
1827*38fd1498Szrj if (marked_for_renaming (sym))
1828*38fd1498Szrj rdef = get_reaching_def (sym);
1829*38fd1498Szrj else if (is_old_name (use))
1830*38fd1498Szrj rdef = get_reaching_def (use);
1831*38fd1498Szrj
1832*38fd1498Szrj if (rdef && rdef != use)
1833*38fd1498Szrj SET_USE (use_p, rdef);
1834*38fd1498Szrj }
1835*38fd1498Szrj
1836*38fd1498Szrj
1837*38fd1498Szrj /* Same as maybe_replace_use, but without introducing default stmts,
1838*38fd1498Szrj returning false to indicate a need to do so. */
1839*38fd1498Szrj
1840*38fd1498Szrj static inline bool
maybe_replace_use_in_debug_stmt(use_operand_p use_p)1841*38fd1498Szrj maybe_replace_use_in_debug_stmt (use_operand_p use_p)
1842*38fd1498Szrj {
1843*38fd1498Szrj tree rdef = NULL_TREE;
1844*38fd1498Szrj tree use = USE_FROM_PTR (use_p);
1845*38fd1498Szrj tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1846*38fd1498Szrj
1847*38fd1498Szrj if (marked_for_renaming (sym))
1848*38fd1498Szrj rdef = get_var_info (sym)->info.current_def;
1849*38fd1498Szrj else if (is_old_name (use))
1850*38fd1498Szrj {
1851*38fd1498Szrj rdef = get_ssa_name_ann (use)->info.current_def;
1852*38fd1498Szrj /* We can't assume that, if there's no current definition, the
1853*38fd1498Szrj default one should be used. It could be the case that we've
1854*38fd1498Szrj rearranged blocks so that the earlier definition no longer
1855*38fd1498Szrj dominates the use. */
1856*38fd1498Szrj if (!rdef && SSA_NAME_IS_DEFAULT_DEF (use))
1857*38fd1498Szrj rdef = use;
1858*38fd1498Szrj }
1859*38fd1498Szrj else
1860*38fd1498Szrj rdef = use;
1861*38fd1498Szrj
1862*38fd1498Szrj if (rdef && rdef != use)
1863*38fd1498Szrj SET_USE (use_p, rdef);
1864*38fd1498Szrj
1865*38fd1498Szrj return rdef != NULL_TREE;
1866*38fd1498Szrj }
1867*38fd1498Szrj
1868*38fd1498Szrj
1869*38fd1498Szrj /* If DEF has x_5 = ASAN_POISON () as its current def, add
1870*38fd1498Szrj ASAN_POISON_USE (x_5) stmt before GSI to denote the stmt writes into
1871*38fd1498Szrj a poisoned (out of scope) variable. */
1872*38fd1498Szrj
1873*38fd1498Szrj static void
maybe_add_asan_poison_write(tree def,gimple_stmt_iterator * gsi)1874*38fd1498Szrj maybe_add_asan_poison_write (tree def, gimple_stmt_iterator *gsi)
1875*38fd1498Szrj {
1876*38fd1498Szrj tree cdef = get_current_def (def);
1877*38fd1498Szrj if (cdef != NULL
1878*38fd1498Szrj && TREE_CODE (cdef) == SSA_NAME
1879*38fd1498Szrj && gimple_call_internal_p (SSA_NAME_DEF_STMT (cdef), IFN_ASAN_POISON))
1880*38fd1498Szrj {
1881*38fd1498Szrj gcall *call
1882*38fd1498Szrj = gimple_build_call_internal (IFN_ASAN_POISON_USE, 1, cdef);
1883*38fd1498Szrj gimple_set_location (call, gimple_location (gsi_stmt (*gsi)));
1884*38fd1498Szrj gsi_insert_before (gsi, call, GSI_SAME_STMT);
1885*38fd1498Szrj }
1886*38fd1498Szrj }
1887*38fd1498Szrj
1888*38fd1498Szrj
1889*38fd1498Szrj /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1890*38fd1498Szrj or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1891*38fd1498Szrj register it as the current definition for the names replaced by
1892*38fd1498Szrj DEF_P. Returns whether the statement should be removed. */
1893*38fd1498Szrj
1894*38fd1498Szrj static inline bool
maybe_register_def(def_operand_p def_p,gimple * stmt,gimple_stmt_iterator gsi)1895*38fd1498Szrj maybe_register_def (def_operand_p def_p, gimple *stmt,
1896*38fd1498Szrj gimple_stmt_iterator gsi)
1897*38fd1498Szrj {
1898*38fd1498Szrj tree def = DEF_FROM_PTR (def_p);
1899*38fd1498Szrj tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1900*38fd1498Szrj bool to_delete = false;
1901*38fd1498Szrj
1902*38fd1498Szrj /* If DEF is a naked symbol that needs renaming, create a new
1903*38fd1498Szrj name for it. */
1904*38fd1498Szrj if (marked_for_renaming (sym))
1905*38fd1498Szrj {
1906*38fd1498Szrj if (DECL_P (def))
1907*38fd1498Szrj {
1908*38fd1498Szrj if (gimple_clobber_p (stmt) && is_gimple_reg (sym))
1909*38fd1498Szrj {
1910*38fd1498Szrj gcc_checking_assert (VAR_P (sym));
1911*38fd1498Szrj /* Replace clobber stmts with a default def. This new use of a
1912*38fd1498Szrj default definition may make it look like SSA_NAMEs have
1913*38fd1498Szrj conflicting lifetimes, so we need special code to let them
1914*38fd1498Szrj coalesce properly. */
1915*38fd1498Szrj to_delete = true;
1916*38fd1498Szrj def = get_or_create_ssa_default_def (cfun, sym);
1917*38fd1498Szrj }
1918*38fd1498Szrj else
1919*38fd1498Szrj {
1920*38fd1498Szrj if (asan_sanitize_use_after_scope ())
1921*38fd1498Szrj maybe_add_asan_poison_write (def, &gsi);
1922*38fd1498Szrj def = make_ssa_name (def, stmt);
1923*38fd1498Szrj }
1924*38fd1498Szrj SET_DEF (def_p, def);
1925*38fd1498Szrj
1926*38fd1498Szrj tree tracked_var = target_for_debug_bind (sym);
1927*38fd1498Szrj if (tracked_var)
1928*38fd1498Szrj {
1929*38fd1498Szrj gimple *note = gimple_build_debug_bind (tracked_var, def, stmt);
1930*38fd1498Szrj /* If stmt ends the bb, insert the debug stmt on the single
1931*38fd1498Szrj non-EH edge from the stmt. */
1932*38fd1498Szrj if (gsi_one_before_end_p (gsi) && stmt_ends_bb_p (stmt))
1933*38fd1498Szrj {
1934*38fd1498Szrj basic_block bb = gsi_bb (gsi);
1935*38fd1498Szrj edge_iterator ei;
1936*38fd1498Szrj edge e, ef = NULL;
1937*38fd1498Szrj FOR_EACH_EDGE (e, ei, bb->succs)
1938*38fd1498Szrj if (!(e->flags & EDGE_EH))
1939*38fd1498Szrj {
1940*38fd1498Szrj gcc_checking_assert (!ef);
1941*38fd1498Szrj ef = e;
1942*38fd1498Szrj }
1943*38fd1498Szrj /* If there are other predecessors to ef->dest, then
1944*38fd1498Szrj there must be PHI nodes for the modified
1945*38fd1498Szrj variable, and therefore there will be debug bind
1946*38fd1498Szrj stmts after the PHI nodes. The debug bind notes
1947*38fd1498Szrj we'd insert would force the creation of a new
1948*38fd1498Szrj block (diverging codegen) and be redundant with
1949*38fd1498Szrj the post-PHI bind stmts, so don't add them.
1950*38fd1498Szrj
1951*38fd1498Szrj As for the exit edge, there wouldn't be redundant
1952*38fd1498Szrj bind stmts, but there wouldn't be a PC to bind
1953*38fd1498Szrj them to either, so avoid diverging the CFG. */
1954*38fd1498Szrj if (ef && single_pred_p (ef->dest)
1955*38fd1498Szrj && ef->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1956*38fd1498Szrj {
1957*38fd1498Szrj /* If there were PHI nodes in the node, we'd
1958*38fd1498Szrj have to make sure the value we're binding
1959*38fd1498Szrj doesn't need rewriting. But there shouldn't
1960*38fd1498Szrj be PHI nodes in a single-predecessor block,
1961*38fd1498Szrj so we just add the note. */
1962*38fd1498Szrj gsi_insert_on_edge_immediate (ef, note);
1963*38fd1498Szrj }
1964*38fd1498Szrj }
1965*38fd1498Szrj else
1966*38fd1498Szrj gsi_insert_after (&gsi, note, GSI_SAME_STMT);
1967*38fd1498Szrj }
1968*38fd1498Szrj }
1969*38fd1498Szrj
1970*38fd1498Szrj register_new_update_single (def, sym);
1971*38fd1498Szrj }
1972*38fd1498Szrj else
1973*38fd1498Szrj {
1974*38fd1498Szrj /* If DEF is a new name, register it as a new definition
1975*38fd1498Szrj for all the names replaced by DEF. */
1976*38fd1498Szrj if (is_new_name (def))
1977*38fd1498Szrj register_new_update_set (def, names_replaced_by (def));
1978*38fd1498Szrj
1979*38fd1498Szrj /* If DEF is an old name, register DEF as a new
1980*38fd1498Szrj definition for itself. */
1981*38fd1498Szrj if (is_old_name (def))
1982*38fd1498Szrj register_new_update_single (def, def);
1983*38fd1498Szrj }
1984*38fd1498Szrj
1985*38fd1498Szrj return to_delete;
1986*38fd1498Szrj }
1987*38fd1498Szrj
1988*38fd1498Szrj
1989*38fd1498Szrj /* Update every variable used in the statement pointed-to by SI. The
1990*38fd1498Szrj statement is assumed to be in SSA form already. Names in
1991*38fd1498Szrj OLD_SSA_NAMES used by SI will be updated to their current reaching
1992*38fd1498Szrj definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1993*38fd1498Szrj will be registered as a new definition for their corresponding name
1994*38fd1498Szrj in OLD_SSA_NAMES. Returns whether STMT should be removed. */
1995*38fd1498Szrj
1996*38fd1498Szrj static bool
rewrite_update_stmt(gimple * stmt,gimple_stmt_iterator gsi)1997*38fd1498Szrj rewrite_update_stmt (gimple *stmt, gimple_stmt_iterator gsi)
1998*38fd1498Szrj {
1999*38fd1498Szrj use_operand_p use_p;
2000*38fd1498Szrj def_operand_p def_p;
2001*38fd1498Szrj ssa_op_iter iter;
2002*38fd1498Szrj
2003*38fd1498Szrj /* Only update marked statements. */
2004*38fd1498Szrj if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
2005*38fd1498Szrj return false;
2006*38fd1498Szrj
2007*38fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
2008*38fd1498Szrj {
2009*38fd1498Szrj fprintf (dump_file, "Updating SSA information for statement ");
2010*38fd1498Szrj print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2011*38fd1498Szrj }
2012*38fd1498Szrj
2013*38fd1498Szrj /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
2014*38fd1498Szrj symbol is marked for renaming. */
2015*38fd1498Szrj if (rewrite_uses_p (stmt))
2016*38fd1498Szrj {
2017*38fd1498Szrj if (is_gimple_debug (stmt))
2018*38fd1498Szrj {
2019*38fd1498Szrj bool failed = false;
2020*38fd1498Szrj
2021*38fd1498Szrj FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
2022*38fd1498Szrj if (!maybe_replace_use_in_debug_stmt (use_p))
2023*38fd1498Szrj {
2024*38fd1498Szrj failed = true;
2025*38fd1498Szrj break;
2026*38fd1498Szrj }
2027*38fd1498Szrj
2028*38fd1498Szrj if (failed)
2029*38fd1498Szrj {
2030*38fd1498Szrj /* DOM sometimes threads jumps in such a way that a
2031*38fd1498Szrj debug stmt ends up referencing a SSA variable that no
2032*38fd1498Szrj longer dominates the debug stmt, but such that all
2033*38fd1498Szrj incoming definitions refer to the same definition in
2034*38fd1498Szrj an earlier dominator. We could try to recover that
2035*38fd1498Szrj definition somehow, but this will have to do for now.
2036*38fd1498Szrj
2037*38fd1498Szrj Introducing a default definition, which is what
2038*38fd1498Szrj maybe_replace_use() would do in such cases, may
2039*38fd1498Szrj modify code generation, for the otherwise-unused
2040*38fd1498Szrj default definition would never go away, modifying SSA
2041*38fd1498Szrj version numbers all over. */
2042*38fd1498Szrj gimple_debug_bind_reset_value (stmt);
2043*38fd1498Szrj update_stmt (stmt);
2044*38fd1498Szrj }
2045*38fd1498Szrj }
2046*38fd1498Szrj else
2047*38fd1498Szrj {
2048*38fd1498Szrj FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
2049*38fd1498Szrj maybe_replace_use (use_p);
2050*38fd1498Szrj }
2051*38fd1498Szrj }
2052*38fd1498Szrj
2053*38fd1498Szrj /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
2054*38fd1498Szrj Also register definitions for names whose underlying symbol is
2055*38fd1498Szrj marked for renaming. */
2056*38fd1498Szrj bool to_delete = false;
2057*38fd1498Szrj if (register_defs_p (stmt))
2058*38fd1498Szrj FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
2059*38fd1498Szrj to_delete |= maybe_register_def (def_p, stmt, gsi);
2060*38fd1498Szrj
2061*38fd1498Szrj return to_delete;
2062*38fd1498Szrj }
2063*38fd1498Szrj
2064*38fd1498Szrj
2065*38fd1498Szrj /* Visit all the successor blocks of BB looking for PHI nodes. For
2066*38fd1498Szrj every PHI node found, check if any of its arguments is in
2067*38fd1498Szrj OLD_SSA_NAMES. If so, and if the argument has a current reaching
2068*38fd1498Szrj definition, replace it. */
2069*38fd1498Szrj
2070*38fd1498Szrj static void
rewrite_update_phi_arguments(basic_block bb)2071*38fd1498Szrj rewrite_update_phi_arguments (basic_block bb)
2072*38fd1498Szrj {
2073*38fd1498Szrj edge e;
2074*38fd1498Szrj edge_iterator ei;
2075*38fd1498Szrj unsigned i;
2076*38fd1498Szrj
2077*38fd1498Szrj FOR_EACH_EDGE (e, ei, bb->succs)
2078*38fd1498Szrj {
2079*38fd1498Szrj gphi *phi;
2080*38fd1498Szrj vec<gphi *> phis;
2081*38fd1498Szrj
2082*38fd1498Szrj if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
2083*38fd1498Szrj continue;
2084*38fd1498Szrj
2085*38fd1498Szrj phis = phis_to_rewrite[e->dest->index];
2086*38fd1498Szrj FOR_EACH_VEC_ELT (phis, i, phi)
2087*38fd1498Szrj {
2088*38fd1498Szrj tree arg, lhs_sym, reaching_def = NULL;
2089*38fd1498Szrj use_operand_p arg_p;
2090*38fd1498Szrj
2091*38fd1498Szrj gcc_checking_assert (rewrite_uses_p (phi));
2092*38fd1498Szrj
2093*38fd1498Szrj arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
2094*38fd1498Szrj arg = USE_FROM_PTR (arg_p);
2095*38fd1498Szrj
2096*38fd1498Szrj if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
2097*38fd1498Szrj continue;
2098*38fd1498Szrj
2099*38fd1498Szrj lhs_sym = SSA_NAME_VAR (gimple_phi_result (phi));
2100*38fd1498Szrj
2101*38fd1498Szrj if (arg == NULL_TREE)
2102*38fd1498Szrj {
2103*38fd1498Szrj /* When updating a PHI node for a recently introduced
2104*38fd1498Szrj symbol we may find NULL arguments. That's why we
2105*38fd1498Szrj take the symbol from the LHS of the PHI node. */
2106*38fd1498Szrj reaching_def = get_reaching_def (lhs_sym);
2107*38fd1498Szrj
2108*38fd1498Szrj }
2109*38fd1498Szrj else
2110*38fd1498Szrj {
2111*38fd1498Szrj tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
2112*38fd1498Szrj
2113*38fd1498Szrj if (marked_for_renaming (sym))
2114*38fd1498Szrj reaching_def = get_reaching_def (sym);
2115*38fd1498Szrj else if (is_old_name (arg))
2116*38fd1498Szrj reaching_def = get_reaching_def (arg);
2117*38fd1498Szrj }
2118*38fd1498Szrj
2119*38fd1498Szrj /* Update the argument if there is a reaching def. */
2120*38fd1498Szrj if (reaching_def)
2121*38fd1498Szrj {
2122*38fd1498Szrj source_location locus;
2123*38fd1498Szrj int arg_i = PHI_ARG_INDEX_FROM_USE (arg_p);
2124*38fd1498Szrj
2125*38fd1498Szrj SET_USE (arg_p, reaching_def);
2126*38fd1498Szrj
2127*38fd1498Szrj /* Virtual operands do not need a location. */
2128*38fd1498Szrj if (virtual_operand_p (reaching_def))
2129*38fd1498Szrj locus = UNKNOWN_LOCATION;
2130*38fd1498Szrj else
2131*38fd1498Szrj {
2132*38fd1498Szrj gimple *stmt = SSA_NAME_DEF_STMT (reaching_def);
2133*38fd1498Szrj gphi *other_phi = dyn_cast <gphi *> (stmt);
2134*38fd1498Szrj
2135*38fd1498Szrj /* Single element PHI nodes behave like copies, so get the
2136*38fd1498Szrj location from the phi argument. */
2137*38fd1498Szrj if (other_phi
2138*38fd1498Szrj && gimple_phi_num_args (other_phi) == 1)
2139*38fd1498Szrj locus = gimple_phi_arg_location (other_phi, 0);
2140*38fd1498Szrj else
2141*38fd1498Szrj locus = gimple_location (stmt);
2142*38fd1498Szrj }
2143*38fd1498Szrj
2144*38fd1498Szrj gimple_phi_arg_set_location (phi, arg_i, locus);
2145*38fd1498Szrj }
2146*38fd1498Szrj
2147*38fd1498Szrj
2148*38fd1498Szrj if (e->flags & EDGE_ABNORMAL)
2149*38fd1498Szrj SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
2150*38fd1498Szrj }
2151*38fd1498Szrj }
2152*38fd1498Szrj }
2153*38fd1498Szrj
2154*38fd1498Szrj class rewrite_update_dom_walker : public dom_walker
2155*38fd1498Szrj {
2156*38fd1498Szrj public:
rewrite_update_dom_walker(cdi_direction direction)2157*38fd1498Szrj rewrite_update_dom_walker (cdi_direction direction)
2158*38fd1498Szrj : dom_walker (direction, ALL_BLOCKS, NULL) {}
2159*38fd1498Szrj
2160*38fd1498Szrj virtual edge before_dom_children (basic_block);
2161*38fd1498Szrj virtual void after_dom_children (basic_block);
2162*38fd1498Szrj };
2163*38fd1498Szrj
2164*38fd1498Szrj /* Initialization of block data structures for the incremental SSA
2165*38fd1498Szrj update pass. Create a block local stack of reaching definitions
2166*38fd1498Szrj for new SSA names produced in this block (BLOCK_DEFS). Register
2167*38fd1498Szrj new definitions for every PHI node in the block. */
2168*38fd1498Szrj
2169*38fd1498Szrj edge
before_dom_children(basic_block bb)2170*38fd1498Szrj rewrite_update_dom_walker::before_dom_children (basic_block bb)
2171*38fd1498Szrj {
2172*38fd1498Szrj bool is_abnormal_phi;
2173*38fd1498Szrj
2174*38fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
2175*38fd1498Szrj fprintf (dump_file, "Registering new PHI nodes in block #%d\n",
2176*38fd1498Szrj bb->index);
2177*38fd1498Szrj
2178*38fd1498Szrj /* Mark the unwind point for this block. */
2179*38fd1498Szrj block_defs_stack.safe_push (NULL_TREE);
2180*38fd1498Szrj
2181*38fd1498Szrj if (!bitmap_bit_p (blocks_to_update, bb->index))
2182*38fd1498Szrj return NULL;
2183*38fd1498Szrj
2184*38fd1498Szrj /* Mark the LHS if any of the arguments flows through an abnormal
2185*38fd1498Szrj edge. */
2186*38fd1498Szrj is_abnormal_phi = bb_has_abnormal_pred (bb);
2187*38fd1498Szrj
2188*38fd1498Szrj /* If any of the PHI nodes is a replacement for a name in
2189*38fd1498Szrj OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
2190*38fd1498Szrj register it as a new definition for its corresponding name. Also
2191*38fd1498Szrj register definitions for names whose underlying symbols are
2192*38fd1498Szrj marked for renaming. */
2193*38fd1498Szrj for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
2194*38fd1498Szrj gsi_next (&gsi))
2195*38fd1498Szrj {
2196*38fd1498Szrj tree lhs, lhs_sym;
2197*38fd1498Szrj gphi *phi = gsi.phi ();
2198*38fd1498Szrj
2199*38fd1498Szrj if (!register_defs_p (phi))
2200*38fd1498Szrj continue;
2201*38fd1498Szrj
2202*38fd1498Szrj lhs = gimple_phi_result (phi);
2203*38fd1498Szrj lhs_sym = SSA_NAME_VAR (lhs);
2204*38fd1498Szrj
2205*38fd1498Szrj if (marked_for_renaming (lhs_sym))
2206*38fd1498Szrj register_new_update_single (lhs, lhs_sym);
2207*38fd1498Szrj else
2208*38fd1498Szrj {
2209*38fd1498Szrj
2210*38fd1498Szrj /* If LHS is a new name, register a new definition for all
2211*38fd1498Szrj the names replaced by LHS. */
2212*38fd1498Szrj if (is_new_name (lhs))
2213*38fd1498Szrj register_new_update_set (lhs, names_replaced_by (lhs));
2214*38fd1498Szrj
2215*38fd1498Szrj /* If LHS is an OLD name, register it as a new definition
2216*38fd1498Szrj for itself. */
2217*38fd1498Szrj if (is_old_name (lhs))
2218*38fd1498Szrj register_new_update_single (lhs, lhs);
2219*38fd1498Szrj }
2220*38fd1498Szrj
2221*38fd1498Szrj if (is_abnormal_phi)
2222*38fd1498Szrj SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
2223*38fd1498Szrj }
2224*38fd1498Szrj
2225*38fd1498Szrj /* Step 2. Rewrite every variable used in each statement in the block. */
2226*38fd1498Szrj if (bitmap_bit_p (interesting_blocks, bb->index))
2227*38fd1498Szrj {
2228*38fd1498Szrj gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
2229*38fd1498Szrj for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2230*38fd1498Szrj if (rewrite_update_stmt (gsi_stmt (gsi), gsi))
2231*38fd1498Szrj gsi_remove (&gsi, true);
2232*38fd1498Szrj else
2233*38fd1498Szrj gsi_next (&gsi);
2234*38fd1498Szrj }
2235*38fd1498Szrj
2236*38fd1498Szrj /* Step 3. Update PHI nodes. */
2237*38fd1498Szrj rewrite_update_phi_arguments (bb);
2238*38fd1498Szrj
2239*38fd1498Szrj return NULL;
2240*38fd1498Szrj }
2241*38fd1498Szrj
2242*38fd1498Szrj /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
2243*38fd1498Szrj the current reaching definition of every name re-written in BB to
2244*38fd1498Szrj the original reaching definition before visiting BB. This
2245*38fd1498Szrj unwinding must be done in the opposite order to what is done in
2246*38fd1498Szrj register_new_update_set. */
2247*38fd1498Szrj
2248*38fd1498Szrj void
after_dom_children(basic_block bb ATTRIBUTE_UNUSED)2249*38fd1498Szrj rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
2250*38fd1498Szrj {
2251*38fd1498Szrj while (block_defs_stack.length () > 0)
2252*38fd1498Szrj {
2253*38fd1498Szrj tree var = block_defs_stack.pop ();
2254*38fd1498Szrj tree saved_def;
2255*38fd1498Szrj
2256*38fd1498Szrj /* NULL indicates the unwind stop point for this block (see
2257*38fd1498Szrj rewrite_update_enter_block). */
2258*38fd1498Szrj if (var == NULL)
2259*38fd1498Szrj return;
2260*38fd1498Szrj
2261*38fd1498Szrj saved_def = block_defs_stack.pop ();
2262*38fd1498Szrj get_common_info (var)->current_def = saved_def;
2263*38fd1498Szrj }
2264*38fd1498Szrj }
2265*38fd1498Szrj
2266*38fd1498Szrj
2267*38fd1498Szrj /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2268*38fd1498Szrj form.
2269*38fd1498Szrj
2270*38fd1498Szrj ENTRY indicates the block where to start. Every block dominated by
2271*38fd1498Szrj ENTRY will be rewritten.
2272*38fd1498Szrj
2273*38fd1498Szrj WHAT indicates what actions will be taken by the renamer (see enum
2274*38fd1498Szrj rewrite_mode).
2275*38fd1498Szrj
2276*38fd1498Szrj BLOCKS are the set of interesting blocks for the dominator walker
2277*38fd1498Szrj to process. If this set is NULL, then all the nodes dominated
2278*38fd1498Szrj by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2279*38fd1498Szrj are not present in BLOCKS are ignored. */
2280*38fd1498Szrj
2281*38fd1498Szrj static void
rewrite_blocks(basic_block entry,enum rewrite_mode what)2282*38fd1498Szrj rewrite_blocks (basic_block entry, enum rewrite_mode what)
2283*38fd1498Szrj {
2284*38fd1498Szrj /* Rewrite all the basic blocks in the program. */
2285*38fd1498Szrj timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
2286*38fd1498Szrj
2287*38fd1498Szrj block_defs_stack.create (10);
2288*38fd1498Szrj
2289*38fd1498Szrj /* Recursively walk the dominator tree rewriting each statement in
2290*38fd1498Szrj each basic block. */
2291*38fd1498Szrj if (what == REWRITE_ALL)
2292*38fd1498Szrj rewrite_dom_walker (CDI_DOMINATORS).walk (entry);
2293*38fd1498Szrj else if (what == REWRITE_UPDATE)
2294*38fd1498Szrj rewrite_update_dom_walker (CDI_DOMINATORS).walk (entry);
2295*38fd1498Szrj else
2296*38fd1498Szrj gcc_unreachable ();
2297*38fd1498Szrj
2298*38fd1498Szrj /* Debugging dumps. */
2299*38fd1498Szrj if (dump_file && (dump_flags & TDF_STATS))
2300*38fd1498Szrj {
2301*38fd1498Szrj dump_dfa_stats (dump_file);
2302*38fd1498Szrj if (var_infos)
2303*38fd1498Szrj dump_tree_ssa_stats (dump_file);
2304*38fd1498Szrj }
2305*38fd1498Szrj
2306*38fd1498Szrj block_defs_stack.release ();
2307*38fd1498Szrj
2308*38fd1498Szrj timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
2309*38fd1498Szrj }
2310*38fd1498Szrj
2311*38fd1498Szrj class mark_def_dom_walker : public dom_walker
2312*38fd1498Szrj {
2313*38fd1498Szrj public:
2314*38fd1498Szrj mark_def_dom_walker (cdi_direction direction);
2315*38fd1498Szrj ~mark_def_dom_walker ();
2316*38fd1498Szrj
2317*38fd1498Szrj virtual edge before_dom_children (basic_block);
2318*38fd1498Szrj
2319*38fd1498Szrj private:
2320*38fd1498Szrj /* Notice that this bitmap is indexed using variable UIDs, so it must be
2321*38fd1498Szrj large enough to accommodate all the variables referenced in the
2322*38fd1498Szrj function, not just the ones we are renaming. */
2323*38fd1498Szrj bitmap m_kills;
2324*38fd1498Szrj };
2325*38fd1498Szrj
mark_def_dom_walker(cdi_direction direction)2326*38fd1498Szrj mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction)
2327*38fd1498Szrj : dom_walker (direction, ALL_BLOCKS, NULL), m_kills (BITMAP_ALLOC (NULL))
2328*38fd1498Szrj {
2329*38fd1498Szrj }
2330*38fd1498Szrj
~mark_def_dom_walker()2331*38fd1498Szrj mark_def_dom_walker::~mark_def_dom_walker ()
2332*38fd1498Szrj {
2333*38fd1498Szrj BITMAP_FREE (m_kills);
2334*38fd1498Szrj }
2335*38fd1498Szrj
2336*38fd1498Szrj /* Block processing routine for mark_def_sites. Clear the KILLS bitmap
2337*38fd1498Szrj at the start of each block, and call mark_def_sites for each statement. */
2338*38fd1498Szrj
2339*38fd1498Szrj edge
before_dom_children(basic_block bb)2340*38fd1498Szrj mark_def_dom_walker::before_dom_children (basic_block bb)
2341*38fd1498Szrj {
2342*38fd1498Szrj gimple_stmt_iterator gsi;
2343*38fd1498Szrj
2344*38fd1498Szrj bitmap_clear (m_kills);
2345*38fd1498Szrj for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2346*38fd1498Szrj mark_def_sites (bb, gsi_stmt (gsi), m_kills);
2347*38fd1498Szrj return NULL;
2348*38fd1498Szrj }
2349*38fd1498Szrj
2350*38fd1498Szrj /* Initialize internal data needed during renaming. */
2351*38fd1498Szrj
2352*38fd1498Szrj static void
init_ssa_renamer(void)2353*38fd1498Szrj init_ssa_renamer (void)
2354*38fd1498Szrj {
2355*38fd1498Szrj cfun->gimple_df->in_ssa_p = false;
2356*38fd1498Szrj
2357*38fd1498Szrj /* Allocate memory for the DEF_BLOCKS hash table. */
2358*38fd1498Szrj gcc_assert (!var_infos);
2359*38fd1498Szrj var_infos = new hash_table<var_info_hasher>
2360*38fd1498Szrj (vec_safe_length (cfun->local_decls));
2361*38fd1498Szrj
2362*38fd1498Szrj bitmap_obstack_initialize (&update_ssa_obstack);
2363*38fd1498Szrj }
2364*38fd1498Szrj
2365*38fd1498Szrj
2366*38fd1498Szrj /* Deallocate internal data structures used by the renamer. */
2367*38fd1498Szrj
2368*38fd1498Szrj static void
fini_ssa_renamer(void)2369*38fd1498Szrj fini_ssa_renamer (void)
2370*38fd1498Szrj {
2371*38fd1498Szrj delete var_infos;
2372*38fd1498Szrj var_infos = NULL;
2373*38fd1498Szrj
2374*38fd1498Szrj bitmap_obstack_release (&update_ssa_obstack);
2375*38fd1498Szrj
2376*38fd1498Szrj cfun->gimple_df->ssa_renaming_needed = 0;
2377*38fd1498Szrj cfun->gimple_df->rename_vops = 0;
2378*38fd1498Szrj cfun->gimple_df->in_ssa_p = true;
2379*38fd1498Szrj }
2380*38fd1498Szrj
2381*38fd1498Szrj /* Main entry point into the SSA builder. The renaming process
2382*38fd1498Szrj proceeds in four main phases:
2383*38fd1498Szrj
2384*38fd1498Szrj 1- Compute dominance frontier and immediate dominators, needed to
2385*38fd1498Szrj insert PHI nodes and rename the function in dominator tree
2386*38fd1498Szrj order.
2387*38fd1498Szrj
2388*38fd1498Szrj 2- Find and mark all the blocks that define variables.
2389*38fd1498Szrj
2390*38fd1498Szrj 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2391*38fd1498Szrj
2392*38fd1498Szrj 4- Rename all the blocks (rewrite_blocks) and statements in the program.
2393*38fd1498Szrj
2394*38fd1498Szrj Steps 3 and 4 are done using the dominator tree walker
2395*38fd1498Szrj (walk_dominator_tree). */
2396*38fd1498Szrj
2397*38fd1498Szrj namespace {
2398*38fd1498Szrj
2399*38fd1498Szrj const pass_data pass_data_build_ssa =
2400*38fd1498Szrj {
2401*38fd1498Szrj GIMPLE_PASS, /* type */
2402*38fd1498Szrj "ssa", /* name */
2403*38fd1498Szrj OPTGROUP_NONE, /* optinfo_flags */
2404*38fd1498Szrj TV_TREE_SSA_OTHER, /* tv_id */
2405*38fd1498Szrj PROP_cfg, /* properties_required */
2406*38fd1498Szrj PROP_ssa, /* properties_provided */
2407*38fd1498Szrj 0, /* properties_destroyed */
2408*38fd1498Szrj 0, /* todo_flags_start */
2409*38fd1498Szrj TODO_remove_unused_locals, /* todo_flags_finish */
2410*38fd1498Szrj };
2411*38fd1498Szrj
2412*38fd1498Szrj class pass_build_ssa : public gimple_opt_pass
2413*38fd1498Szrj {
2414*38fd1498Szrj public:
pass_build_ssa(gcc::context * ctxt)2415*38fd1498Szrj pass_build_ssa (gcc::context *ctxt)
2416*38fd1498Szrj : gimple_opt_pass (pass_data_build_ssa, ctxt)
2417*38fd1498Szrj {}
2418*38fd1498Szrj
2419*38fd1498Szrj /* opt_pass methods: */
gate(function * fun)2420*38fd1498Szrj virtual bool gate (function *fun)
2421*38fd1498Szrj {
2422*38fd1498Szrj /* Do nothing for funcions that was produced already in SSA form. */
2423*38fd1498Szrj return !(fun->curr_properties & PROP_ssa);
2424*38fd1498Szrj }
2425*38fd1498Szrj
2426*38fd1498Szrj virtual unsigned int execute (function *);
2427*38fd1498Szrj
2428*38fd1498Szrj }; // class pass_build_ssa
2429*38fd1498Szrj
2430*38fd1498Szrj unsigned int
execute(function * fun)2431*38fd1498Szrj pass_build_ssa::execute (function *fun)
2432*38fd1498Szrj {
2433*38fd1498Szrj bitmap_head *dfs;
2434*38fd1498Szrj basic_block bb;
2435*38fd1498Szrj
2436*38fd1498Szrj /* Initialize operand data structures. */
2437*38fd1498Szrj init_ssa_operands (fun);
2438*38fd1498Szrj
2439*38fd1498Szrj /* Initialize internal data needed by the renamer. */
2440*38fd1498Szrj init_ssa_renamer ();
2441*38fd1498Szrj
2442*38fd1498Szrj /* Initialize the set of interesting blocks. The callback
2443*38fd1498Szrj mark_def_sites will add to this set those blocks that the renamer
2444*38fd1498Szrj should process. */
2445*38fd1498Szrj interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (fun));
2446*38fd1498Szrj bitmap_clear (interesting_blocks);
2447*38fd1498Szrj
2448*38fd1498Szrj /* Initialize dominance frontier. */
2449*38fd1498Szrj dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (fun));
2450*38fd1498Szrj FOR_EACH_BB_FN (bb, fun)
2451*38fd1498Szrj bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
2452*38fd1498Szrj
2453*38fd1498Szrj /* 1- Compute dominance frontiers. */
2454*38fd1498Szrj calculate_dominance_info (CDI_DOMINATORS);
2455*38fd1498Szrj compute_dominance_frontiers (dfs);
2456*38fd1498Szrj
2457*38fd1498Szrj /* 2- Find and mark definition sites. */
2458*38fd1498Szrj mark_def_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
2459*38fd1498Szrj
2460*38fd1498Szrj /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2461*38fd1498Szrj insert_phi_nodes (dfs);
2462*38fd1498Szrj
2463*38fd1498Szrj /* 4- Rename all the blocks. */
2464*38fd1498Szrj rewrite_blocks (ENTRY_BLOCK_PTR_FOR_FN (fun), REWRITE_ALL);
2465*38fd1498Szrj
2466*38fd1498Szrj /* Free allocated memory. */
2467*38fd1498Szrj FOR_EACH_BB_FN (bb, fun)
2468*38fd1498Szrj bitmap_clear (&dfs[bb->index]);
2469*38fd1498Szrj free (dfs);
2470*38fd1498Szrj
2471*38fd1498Szrj sbitmap_free (interesting_blocks);
2472*38fd1498Szrj
2473*38fd1498Szrj fini_ssa_renamer ();
2474*38fd1498Szrj
2475*38fd1498Szrj /* Try to get rid of all gimplifier generated temporaries by making
2476*38fd1498Szrj its SSA names anonymous. This way we can garbage collect them
2477*38fd1498Szrj all after removing unused locals which we do in our TODO. */
2478*38fd1498Szrj unsigned i;
2479*38fd1498Szrj tree name;
2480*38fd1498Szrj
2481*38fd1498Szrj FOR_EACH_SSA_NAME (i, name, cfun)
2482*38fd1498Szrj {
2483*38fd1498Szrj if (SSA_NAME_IS_DEFAULT_DEF (name))
2484*38fd1498Szrj continue;
2485*38fd1498Szrj tree decl = SSA_NAME_VAR (name);
2486*38fd1498Szrj if (decl
2487*38fd1498Szrj && VAR_P (decl)
2488*38fd1498Szrj && !VAR_DECL_IS_VIRTUAL_OPERAND (decl)
2489*38fd1498Szrj && DECL_IGNORED_P (decl))
2490*38fd1498Szrj SET_SSA_NAME_VAR_OR_IDENTIFIER (name, DECL_NAME (decl));
2491*38fd1498Szrj }
2492*38fd1498Szrj
2493*38fd1498Szrj return 0;
2494*38fd1498Szrj }
2495*38fd1498Szrj
2496*38fd1498Szrj } // anon namespace
2497*38fd1498Szrj
2498*38fd1498Szrj gimple_opt_pass *
make_pass_build_ssa(gcc::context * ctxt)2499*38fd1498Szrj make_pass_build_ssa (gcc::context *ctxt)
2500*38fd1498Szrj {
2501*38fd1498Szrj return new pass_build_ssa (ctxt);
2502*38fd1498Szrj }
2503*38fd1498Szrj
2504*38fd1498Szrj
2505*38fd1498Szrj /* Mark the definition of VAR at STMT and BB as interesting for the
2506*38fd1498Szrj renamer. BLOCKS is the set of blocks that need updating. */
2507*38fd1498Szrj
2508*38fd1498Szrj static void
mark_def_interesting(tree var,gimple * stmt,basic_block bb,bool insert_phi_p)2509*38fd1498Szrj mark_def_interesting (tree var, gimple *stmt, basic_block bb,
2510*38fd1498Szrj bool insert_phi_p)
2511*38fd1498Szrj {
2512*38fd1498Szrj gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
2513*38fd1498Szrj set_register_defs (stmt, true);
2514*38fd1498Szrj
2515*38fd1498Szrj if (insert_phi_p)
2516*38fd1498Szrj {
2517*38fd1498Szrj bool is_phi_p = gimple_code (stmt) == GIMPLE_PHI;
2518*38fd1498Szrj
2519*38fd1498Szrj set_def_block (var, bb, is_phi_p);
2520*38fd1498Szrj
2521*38fd1498Szrj /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2522*38fd1498Szrj site for both itself and all the old names replaced by it. */
2523*38fd1498Szrj if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
2524*38fd1498Szrj {
2525*38fd1498Szrj bitmap_iterator bi;
2526*38fd1498Szrj unsigned i;
2527*38fd1498Szrj bitmap set = names_replaced_by (var);
2528*38fd1498Szrj if (set)
2529*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2530*38fd1498Szrj set_def_block (ssa_name (i), bb, is_phi_p);
2531*38fd1498Szrj }
2532*38fd1498Szrj }
2533*38fd1498Szrj }
2534*38fd1498Szrj
2535*38fd1498Szrj
2536*38fd1498Szrj /* Mark the use of VAR at STMT and BB as interesting for the
2537*38fd1498Szrj renamer. INSERT_PHI_P is true if we are going to insert new PHI
2538*38fd1498Szrj nodes. */
2539*38fd1498Szrj
2540*38fd1498Szrj static inline void
mark_use_interesting(tree var,gimple * stmt,basic_block bb,bool insert_phi_p)2541*38fd1498Szrj mark_use_interesting (tree var, gimple *stmt, basic_block bb,
2542*38fd1498Szrj bool insert_phi_p)
2543*38fd1498Szrj {
2544*38fd1498Szrj basic_block def_bb = gimple_bb (stmt);
2545*38fd1498Szrj
2546*38fd1498Szrj mark_block_for_update (def_bb);
2547*38fd1498Szrj mark_block_for_update (bb);
2548*38fd1498Szrj
2549*38fd1498Szrj if (gimple_code (stmt) == GIMPLE_PHI)
2550*38fd1498Szrj mark_phi_for_rewrite (def_bb, as_a <gphi *> (stmt));
2551*38fd1498Szrj else
2552*38fd1498Szrj {
2553*38fd1498Szrj set_rewrite_uses (stmt, true);
2554*38fd1498Szrj
2555*38fd1498Szrj if (is_gimple_debug (stmt))
2556*38fd1498Szrj return;
2557*38fd1498Szrj }
2558*38fd1498Szrj
2559*38fd1498Szrj /* If VAR has not been defined in BB, then it is live-on-entry
2560*38fd1498Szrj to BB. Note that we cannot just use the block holding VAR's
2561*38fd1498Szrj definition because if VAR is one of the names in OLD_SSA_NAMES,
2562*38fd1498Szrj it will have several definitions (itself and all the names that
2563*38fd1498Szrj replace it). */
2564*38fd1498Szrj if (insert_phi_p)
2565*38fd1498Szrj {
2566*38fd1498Szrj def_blocks *db_p = get_def_blocks_for (get_common_info (var));
2567*38fd1498Szrj if (!bitmap_bit_p (db_p->def_blocks, bb->index))
2568*38fd1498Szrj set_livein_block (var, bb);
2569*38fd1498Szrj }
2570*38fd1498Szrj }
2571*38fd1498Szrj
2572*38fd1498Szrj
2573*38fd1498Szrj /* Do a dominator walk starting at BB processing statements that
2574*38fd1498Szrj reference symbols in SSA operands. This is very similar to
2575*38fd1498Szrj mark_def_sites, but the scan handles statements whose operands may
2576*38fd1498Szrj already be SSA names.
2577*38fd1498Szrj
2578*38fd1498Szrj If INSERT_PHI_P is true, mark those uses as live in the
2579*38fd1498Szrj corresponding block. This is later used by the PHI placement
2580*38fd1498Szrj algorithm to make PHI pruning decisions.
2581*38fd1498Szrj
2582*38fd1498Szrj FIXME. Most of this would be unnecessary if we could associate a
2583*38fd1498Szrj symbol to all the SSA names that reference it. But that
2584*38fd1498Szrj sounds like it would be expensive to maintain. Still, it
2585*38fd1498Szrj would be interesting to see if it makes better sense to do
2586*38fd1498Szrj that. */
2587*38fd1498Szrj
2588*38fd1498Szrj static void
prepare_block_for_update(basic_block bb,bool insert_phi_p)2589*38fd1498Szrj prepare_block_for_update (basic_block bb, bool insert_phi_p)
2590*38fd1498Szrj {
2591*38fd1498Szrj basic_block son;
2592*38fd1498Szrj edge e;
2593*38fd1498Szrj edge_iterator ei;
2594*38fd1498Szrj
2595*38fd1498Szrj mark_block_for_update (bb);
2596*38fd1498Szrj
2597*38fd1498Szrj /* Process PHI nodes marking interesting those that define or use
2598*38fd1498Szrj the symbols that we are interested in. */
2599*38fd1498Szrj for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
2600*38fd1498Szrj gsi_next (&si))
2601*38fd1498Szrj {
2602*38fd1498Szrj gphi *phi = si.phi ();
2603*38fd1498Szrj tree lhs_sym, lhs = gimple_phi_result (phi);
2604*38fd1498Szrj
2605*38fd1498Szrj if (TREE_CODE (lhs) == SSA_NAME
2606*38fd1498Szrj && (! virtual_operand_p (lhs)
2607*38fd1498Szrj || ! cfun->gimple_df->rename_vops))
2608*38fd1498Szrj continue;
2609*38fd1498Szrj
2610*38fd1498Szrj lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
2611*38fd1498Szrj mark_for_renaming (lhs_sym);
2612*38fd1498Szrj mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
2613*38fd1498Szrj
2614*38fd1498Szrj /* Mark the uses in phi nodes as interesting. It would be more correct
2615*38fd1498Szrj to process the arguments of the phi nodes of the successor edges of
2616*38fd1498Szrj BB at the end of prepare_block_for_update, however, that turns out
2617*38fd1498Szrj to be significantly more expensive. Doing it here is conservatively
2618*38fd1498Szrj correct -- it may only cause us to believe a value to be live in a
2619*38fd1498Szrj block that also contains its definition, and thus insert a few more
2620*38fd1498Szrj phi nodes for it. */
2621*38fd1498Szrj FOR_EACH_EDGE (e, ei, bb->preds)
2622*38fd1498Szrj mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
2623*38fd1498Szrj }
2624*38fd1498Szrj
2625*38fd1498Szrj /* Process the statements. */
2626*38fd1498Szrj for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
2627*38fd1498Szrj gsi_next (&si))
2628*38fd1498Szrj {
2629*38fd1498Szrj gimple *stmt;
2630*38fd1498Szrj ssa_op_iter i;
2631*38fd1498Szrj use_operand_p use_p;
2632*38fd1498Szrj def_operand_p def_p;
2633*38fd1498Szrj
2634*38fd1498Szrj stmt = gsi_stmt (si);
2635*38fd1498Szrj
2636*38fd1498Szrj if (cfun->gimple_df->rename_vops
2637*38fd1498Szrj && gimple_vuse (stmt))
2638*38fd1498Szrj {
2639*38fd1498Szrj tree use = gimple_vuse (stmt);
2640*38fd1498Szrj tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
2641*38fd1498Szrj mark_for_renaming (sym);
2642*38fd1498Szrj mark_use_interesting (sym, stmt, bb, insert_phi_p);
2643*38fd1498Szrj }
2644*38fd1498Szrj
2645*38fd1498Szrj FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE)
2646*38fd1498Szrj {
2647*38fd1498Szrj tree use = USE_FROM_PTR (use_p);
2648*38fd1498Szrj if (!DECL_P (use))
2649*38fd1498Szrj continue;
2650*38fd1498Szrj mark_for_renaming (use);
2651*38fd1498Szrj mark_use_interesting (use, stmt, bb, insert_phi_p);
2652*38fd1498Szrj }
2653*38fd1498Szrj
2654*38fd1498Szrj if (cfun->gimple_df->rename_vops
2655*38fd1498Szrj && gimple_vdef (stmt))
2656*38fd1498Szrj {
2657*38fd1498Szrj tree def = gimple_vdef (stmt);
2658*38fd1498Szrj tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
2659*38fd1498Szrj mark_for_renaming (sym);
2660*38fd1498Szrj mark_def_interesting (sym, stmt, bb, insert_phi_p);
2661*38fd1498Szrj }
2662*38fd1498Szrj
2663*38fd1498Szrj FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF)
2664*38fd1498Szrj {
2665*38fd1498Szrj tree def = DEF_FROM_PTR (def_p);
2666*38fd1498Szrj if (!DECL_P (def))
2667*38fd1498Szrj continue;
2668*38fd1498Szrj mark_for_renaming (def);
2669*38fd1498Szrj mark_def_interesting (def, stmt, bb, insert_phi_p);
2670*38fd1498Szrj }
2671*38fd1498Szrj }
2672*38fd1498Szrj
2673*38fd1498Szrj /* Now visit all the blocks dominated by BB. */
2674*38fd1498Szrj for (son = first_dom_son (CDI_DOMINATORS, bb);
2675*38fd1498Szrj son;
2676*38fd1498Szrj son = next_dom_son (CDI_DOMINATORS, son))
2677*38fd1498Szrj prepare_block_for_update (son, insert_phi_p);
2678*38fd1498Szrj }
2679*38fd1498Szrj
2680*38fd1498Szrj
2681*38fd1498Szrj /* Helper for prepare_names_to_update. Mark all the use sites for
2682*38fd1498Szrj NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2683*38fd1498Szrj prepare_names_to_update. */
2684*38fd1498Szrj
2685*38fd1498Szrj static void
prepare_use_sites_for(tree name,bool insert_phi_p)2686*38fd1498Szrj prepare_use_sites_for (tree name, bool insert_phi_p)
2687*38fd1498Szrj {
2688*38fd1498Szrj use_operand_p use_p;
2689*38fd1498Szrj imm_use_iterator iter;
2690*38fd1498Szrj
2691*38fd1498Szrj /* If we rename virtual operands do not update them. */
2692*38fd1498Szrj if (virtual_operand_p (name)
2693*38fd1498Szrj && cfun->gimple_df->rename_vops)
2694*38fd1498Szrj return;
2695*38fd1498Szrj
2696*38fd1498Szrj FOR_EACH_IMM_USE_FAST (use_p, iter, name)
2697*38fd1498Szrj {
2698*38fd1498Szrj gimple *stmt = USE_STMT (use_p);
2699*38fd1498Szrj basic_block bb = gimple_bb (stmt);
2700*38fd1498Szrj
2701*38fd1498Szrj if (gimple_code (stmt) == GIMPLE_PHI)
2702*38fd1498Szrj {
2703*38fd1498Szrj int ix = PHI_ARG_INDEX_FROM_USE (use_p);
2704*38fd1498Szrj edge e = gimple_phi_arg_edge (as_a <gphi *> (stmt), ix);
2705*38fd1498Szrj mark_use_interesting (name, stmt, e->src, insert_phi_p);
2706*38fd1498Szrj }
2707*38fd1498Szrj else
2708*38fd1498Szrj {
2709*38fd1498Szrj /* For regular statements, mark this as an interesting use
2710*38fd1498Szrj for NAME. */
2711*38fd1498Szrj mark_use_interesting (name, stmt, bb, insert_phi_p);
2712*38fd1498Szrj }
2713*38fd1498Szrj }
2714*38fd1498Szrj }
2715*38fd1498Szrj
2716*38fd1498Szrj
2717*38fd1498Szrj /* Helper for prepare_names_to_update. Mark the definition site for
2718*38fd1498Szrj NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2719*38fd1498Szrj prepare_names_to_update. */
2720*38fd1498Szrj
2721*38fd1498Szrj static void
prepare_def_site_for(tree name,bool insert_phi_p)2722*38fd1498Szrj prepare_def_site_for (tree name, bool insert_phi_p)
2723*38fd1498Szrj {
2724*38fd1498Szrj gimple *stmt;
2725*38fd1498Szrj basic_block bb;
2726*38fd1498Szrj
2727*38fd1498Szrj gcc_checking_assert (names_to_release == NULL
2728*38fd1498Szrj || !bitmap_bit_p (names_to_release,
2729*38fd1498Szrj SSA_NAME_VERSION (name)));
2730*38fd1498Szrj
2731*38fd1498Szrj /* If we rename virtual operands do not update them. */
2732*38fd1498Szrj if (virtual_operand_p (name)
2733*38fd1498Szrj && cfun->gimple_df->rename_vops)
2734*38fd1498Szrj return;
2735*38fd1498Szrj
2736*38fd1498Szrj stmt = SSA_NAME_DEF_STMT (name);
2737*38fd1498Szrj bb = gimple_bb (stmt);
2738*38fd1498Szrj if (bb)
2739*38fd1498Szrj {
2740*38fd1498Szrj gcc_checking_assert (bb->index < last_basic_block_for_fn (cfun));
2741*38fd1498Szrj mark_block_for_update (bb);
2742*38fd1498Szrj mark_def_interesting (name, stmt, bb, insert_phi_p);
2743*38fd1498Szrj }
2744*38fd1498Szrj }
2745*38fd1498Szrj
2746*38fd1498Szrj
2747*38fd1498Szrj /* Mark definition and use sites of names in NEW_SSA_NAMES and
2748*38fd1498Szrj OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2749*38fd1498Szrj PHI nodes for newly created names. */
2750*38fd1498Szrj
2751*38fd1498Szrj static void
prepare_names_to_update(bool insert_phi_p)2752*38fd1498Szrj prepare_names_to_update (bool insert_phi_p)
2753*38fd1498Szrj {
2754*38fd1498Szrj unsigned i = 0;
2755*38fd1498Szrj bitmap_iterator bi;
2756*38fd1498Szrj sbitmap_iterator sbi;
2757*38fd1498Szrj
2758*38fd1498Szrj /* If a name N from NEW_SSA_NAMES is also marked to be released,
2759*38fd1498Szrj remove it from NEW_SSA_NAMES so that we don't try to visit its
2760*38fd1498Szrj defining basic block (which most likely doesn't exist). Notice
2761*38fd1498Szrj that we cannot do the same with names in OLD_SSA_NAMES because we
2762*38fd1498Szrj want to replace existing instances. */
2763*38fd1498Szrj if (names_to_release)
2764*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2765*38fd1498Szrj bitmap_clear_bit (new_ssa_names, i);
2766*38fd1498Szrj
2767*38fd1498Szrj /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2768*38fd1498Szrj names may be considered to be live-in on blocks that contain
2769*38fd1498Szrj definitions for their replacements. */
2770*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2771*38fd1498Szrj prepare_def_site_for (ssa_name (i), insert_phi_p);
2772*38fd1498Szrj
2773*38fd1498Szrj /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2774*38fd1498Szrj OLD_SSA_NAMES, but we have to ignore its definition site. */
2775*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
2776*38fd1498Szrj {
2777*38fd1498Szrj if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
2778*38fd1498Szrj prepare_def_site_for (ssa_name (i), insert_phi_p);
2779*38fd1498Szrj prepare_use_sites_for (ssa_name (i), insert_phi_p);
2780*38fd1498Szrj }
2781*38fd1498Szrj }
2782*38fd1498Szrj
2783*38fd1498Szrj
2784*38fd1498Szrj /* Dump all the names replaced by NAME to FILE. */
2785*38fd1498Szrj
2786*38fd1498Szrj void
dump_names_replaced_by(FILE * file,tree name)2787*38fd1498Szrj dump_names_replaced_by (FILE *file, tree name)
2788*38fd1498Szrj {
2789*38fd1498Szrj unsigned i;
2790*38fd1498Szrj bitmap old_set;
2791*38fd1498Szrj bitmap_iterator bi;
2792*38fd1498Szrj
2793*38fd1498Szrj print_generic_expr (file, name);
2794*38fd1498Szrj fprintf (file, " -> { ");
2795*38fd1498Szrj
2796*38fd1498Szrj old_set = names_replaced_by (name);
2797*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
2798*38fd1498Szrj {
2799*38fd1498Szrj print_generic_expr (file, ssa_name (i));
2800*38fd1498Szrj fprintf (file, " ");
2801*38fd1498Szrj }
2802*38fd1498Szrj
2803*38fd1498Szrj fprintf (file, "}\n");
2804*38fd1498Szrj }
2805*38fd1498Szrj
2806*38fd1498Szrj
2807*38fd1498Szrj /* Dump all the names replaced by NAME to stderr. */
2808*38fd1498Szrj
2809*38fd1498Szrj DEBUG_FUNCTION void
debug_names_replaced_by(tree name)2810*38fd1498Szrj debug_names_replaced_by (tree name)
2811*38fd1498Szrj {
2812*38fd1498Szrj dump_names_replaced_by (stderr, name);
2813*38fd1498Szrj }
2814*38fd1498Szrj
2815*38fd1498Szrj
2816*38fd1498Szrj /* Dump SSA update information to FILE. */
2817*38fd1498Szrj
2818*38fd1498Szrj void
dump_update_ssa(FILE * file)2819*38fd1498Szrj dump_update_ssa (FILE *file)
2820*38fd1498Szrj {
2821*38fd1498Szrj unsigned i = 0;
2822*38fd1498Szrj bitmap_iterator bi;
2823*38fd1498Szrj
2824*38fd1498Szrj if (!need_ssa_update_p (cfun))
2825*38fd1498Szrj return;
2826*38fd1498Szrj
2827*38fd1498Szrj if (new_ssa_names && bitmap_first_set_bit (new_ssa_names) >= 0)
2828*38fd1498Szrj {
2829*38fd1498Szrj sbitmap_iterator sbi;
2830*38fd1498Szrj
2831*38fd1498Szrj fprintf (file, "\nSSA replacement table\n");
2832*38fd1498Szrj fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
2833*38fd1498Szrj "O_1, ..., O_j\n\n");
2834*38fd1498Szrj
2835*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2836*38fd1498Szrj dump_names_replaced_by (file, ssa_name (i));
2837*38fd1498Szrj }
2838*38fd1498Szrj
2839*38fd1498Szrj if (symbols_to_rename_set && !bitmap_empty_p (symbols_to_rename_set))
2840*38fd1498Szrj {
2841*38fd1498Szrj fprintf (file, "\nSymbols to be put in SSA form\n");
2842*38fd1498Szrj dump_decl_set (file, symbols_to_rename_set);
2843*38fd1498Szrj fprintf (file, "\n");
2844*38fd1498Szrj }
2845*38fd1498Szrj
2846*38fd1498Szrj if (names_to_release && !bitmap_empty_p (names_to_release))
2847*38fd1498Szrj {
2848*38fd1498Szrj fprintf (file, "\nSSA names to release after updating the SSA web\n\n");
2849*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2850*38fd1498Szrj {
2851*38fd1498Szrj print_generic_expr (file, ssa_name (i));
2852*38fd1498Szrj fprintf (file, " ");
2853*38fd1498Szrj }
2854*38fd1498Szrj fprintf (file, "\n");
2855*38fd1498Szrj }
2856*38fd1498Szrj }
2857*38fd1498Szrj
2858*38fd1498Szrj
2859*38fd1498Szrj /* Dump SSA update information to stderr. */
2860*38fd1498Szrj
2861*38fd1498Szrj DEBUG_FUNCTION void
debug_update_ssa(void)2862*38fd1498Szrj debug_update_ssa (void)
2863*38fd1498Szrj {
2864*38fd1498Szrj dump_update_ssa (stderr);
2865*38fd1498Szrj }
2866*38fd1498Szrj
2867*38fd1498Szrj
2868*38fd1498Szrj /* Initialize data structures used for incremental SSA updates. */
2869*38fd1498Szrj
2870*38fd1498Szrj static void
init_update_ssa(struct function * fn)2871*38fd1498Szrj init_update_ssa (struct function *fn)
2872*38fd1498Szrj {
2873*38fd1498Szrj /* Reserve more space than the current number of names. The calls to
2874*38fd1498Szrj add_new_name_mapping are typically done after creating new SSA
2875*38fd1498Szrj names, so we'll need to reallocate these arrays. */
2876*38fd1498Szrj old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2877*38fd1498Szrj bitmap_clear (old_ssa_names);
2878*38fd1498Szrj
2879*38fd1498Szrj new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2880*38fd1498Szrj bitmap_clear (new_ssa_names);
2881*38fd1498Szrj
2882*38fd1498Szrj bitmap_obstack_initialize (&update_ssa_obstack);
2883*38fd1498Szrj
2884*38fd1498Szrj names_to_release = NULL;
2885*38fd1498Szrj update_ssa_initialized_fn = fn;
2886*38fd1498Szrj }
2887*38fd1498Szrj
2888*38fd1498Szrj
2889*38fd1498Szrj /* Deallocate data structures used for incremental SSA updates. */
2890*38fd1498Szrj
2891*38fd1498Szrj void
delete_update_ssa(void)2892*38fd1498Szrj delete_update_ssa (void)
2893*38fd1498Szrj {
2894*38fd1498Szrj unsigned i;
2895*38fd1498Szrj bitmap_iterator bi;
2896*38fd1498Szrj
2897*38fd1498Szrj sbitmap_free (old_ssa_names);
2898*38fd1498Szrj old_ssa_names = NULL;
2899*38fd1498Szrj
2900*38fd1498Szrj sbitmap_free (new_ssa_names);
2901*38fd1498Szrj new_ssa_names = NULL;
2902*38fd1498Szrj
2903*38fd1498Szrj BITMAP_FREE (symbols_to_rename_set);
2904*38fd1498Szrj symbols_to_rename_set = NULL;
2905*38fd1498Szrj symbols_to_rename.release ();
2906*38fd1498Szrj
2907*38fd1498Szrj if (names_to_release)
2908*38fd1498Szrj {
2909*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2910*38fd1498Szrj release_ssa_name (ssa_name (i));
2911*38fd1498Szrj BITMAP_FREE (names_to_release);
2912*38fd1498Szrj }
2913*38fd1498Szrj
2914*38fd1498Szrj clear_ssa_name_info ();
2915*38fd1498Szrj
2916*38fd1498Szrj fini_ssa_renamer ();
2917*38fd1498Szrj
2918*38fd1498Szrj if (blocks_with_phis_to_rewrite)
2919*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
2920*38fd1498Szrj {
2921*38fd1498Szrj vec<gphi *> phis = phis_to_rewrite[i];
2922*38fd1498Szrj phis.release ();
2923*38fd1498Szrj phis_to_rewrite[i].create (0);
2924*38fd1498Szrj }
2925*38fd1498Szrj
2926*38fd1498Szrj BITMAP_FREE (blocks_with_phis_to_rewrite);
2927*38fd1498Szrj BITMAP_FREE (blocks_to_update);
2928*38fd1498Szrj
2929*38fd1498Szrj update_ssa_initialized_fn = NULL;
2930*38fd1498Szrj }
2931*38fd1498Szrj
2932*38fd1498Szrj
2933*38fd1498Szrj /* Create a new name for OLD_NAME in statement STMT and replace the
2934*38fd1498Szrj operand pointed to by DEF_P with the newly created name. If DEF_P
2935*38fd1498Szrj is NULL then STMT should be a GIMPLE assignment.
2936*38fd1498Szrj Return the new name and register the replacement mapping <NEW, OLD> in
2937*38fd1498Szrj update_ssa's tables. */
2938*38fd1498Szrj
2939*38fd1498Szrj tree
create_new_def_for(tree old_name,gimple * stmt,def_operand_p def)2940*38fd1498Szrj create_new_def_for (tree old_name, gimple *stmt, def_operand_p def)
2941*38fd1498Szrj {
2942*38fd1498Szrj tree new_name;
2943*38fd1498Szrj
2944*38fd1498Szrj timevar_push (TV_TREE_SSA_INCREMENTAL);
2945*38fd1498Szrj
2946*38fd1498Szrj if (!update_ssa_initialized_fn)
2947*38fd1498Szrj init_update_ssa (cfun);
2948*38fd1498Szrj
2949*38fd1498Szrj gcc_assert (update_ssa_initialized_fn == cfun);
2950*38fd1498Szrj
2951*38fd1498Szrj new_name = duplicate_ssa_name (old_name, stmt);
2952*38fd1498Szrj if (def)
2953*38fd1498Szrj SET_DEF (def, new_name);
2954*38fd1498Szrj else
2955*38fd1498Szrj gimple_assign_set_lhs (stmt, new_name);
2956*38fd1498Szrj
2957*38fd1498Szrj if (gimple_code (stmt) == GIMPLE_PHI)
2958*38fd1498Szrj {
2959*38fd1498Szrj basic_block bb = gimple_bb (stmt);
2960*38fd1498Szrj
2961*38fd1498Szrj /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2962*38fd1498Szrj SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = bb_has_abnormal_pred (bb);
2963*38fd1498Szrj }
2964*38fd1498Szrj
2965*38fd1498Szrj add_new_name_mapping (new_name, old_name);
2966*38fd1498Szrj
2967*38fd1498Szrj /* For the benefit of passes that will be updating the SSA form on
2968*38fd1498Szrj their own, set the current reaching definition of OLD_NAME to be
2969*38fd1498Szrj NEW_NAME. */
2970*38fd1498Szrj get_ssa_name_ann (old_name)->info.current_def = new_name;
2971*38fd1498Szrj
2972*38fd1498Szrj timevar_pop (TV_TREE_SSA_INCREMENTAL);
2973*38fd1498Szrj
2974*38fd1498Szrj return new_name;
2975*38fd1498Szrj }
2976*38fd1498Szrj
2977*38fd1498Szrj
2978*38fd1498Szrj /* Mark virtual operands of FN for renaming by update_ssa. */
2979*38fd1498Szrj
2980*38fd1498Szrj void
mark_virtual_operands_for_renaming(struct function * fn)2981*38fd1498Szrj mark_virtual_operands_for_renaming (struct function *fn)
2982*38fd1498Szrj {
2983*38fd1498Szrj fn->gimple_df->ssa_renaming_needed = 1;
2984*38fd1498Szrj fn->gimple_df->rename_vops = 1;
2985*38fd1498Szrj }
2986*38fd1498Szrj
2987*38fd1498Szrj /* Replace all uses of NAME by underlying variable and mark it
2988*38fd1498Szrj for renaming. This assumes the defining statement of NAME is
2989*38fd1498Szrj going to be removed. */
2990*38fd1498Szrj
2991*38fd1498Szrj void
mark_virtual_operand_for_renaming(tree name)2992*38fd1498Szrj mark_virtual_operand_for_renaming (tree name)
2993*38fd1498Szrj {
2994*38fd1498Szrj tree name_var = SSA_NAME_VAR (name);
2995*38fd1498Szrj bool used = false;
2996*38fd1498Szrj imm_use_iterator iter;
2997*38fd1498Szrj use_operand_p use_p;
2998*38fd1498Szrj gimple *stmt;
2999*38fd1498Szrj
3000*38fd1498Szrj gcc_assert (VAR_DECL_IS_VIRTUAL_OPERAND (name_var));
3001*38fd1498Szrj FOR_EACH_IMM_USE_STMT (stmt, iter, name)
3002*38fd1498Szrj {
3003*38fd1498Szrj FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3004*38fd1498Szrj SET_USE (use_p, name_var);
3005*38fd1498Szrj used = true;
3006*38fd1498Szrj }
3007*38fd1498Szrj if (used)
3008*38fd1498Szrj mark_virtual_operands_for_renaming (cfun);
3009*38fd1498Szrj }
3010*38fd1498Szrj
3011*38fd1498Szrj /* Replace all uses of the virtual PHI result by its underlying variable
3012*38fd1498Szrj and mark it for renaming. This assumes the PHI node is going to be
3013*38fd1498Szrj removed. */
3014*38fd1498Szrj
3015*38fd1498Szrj void
mark_virtual_phi_result_for_renaming(gphi * phi)3016*38fd1498Szrj mark_virtual_phi_result_for_renaming (gphi *phi)
3017*38fd1498Szrj {
3018*38fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
3019*38fd1498Szrj {
3020*38fd1498Szrj fprintf (dump_file, "Marking result for renaming : ");
3021*38fd1498Szrj print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
3022*38fd1498Szrj fprintf (dump_file, "\n");
3023*38fd1498Szrj }
3024*38fd1498Szrj
3025*38fd1498Szrj mark_virtual_operand_for_renaming (gimple_phi_result (phi));
3026*38fd1498Szrj }
3027*38fd1498Szrj
3028*38fd1498Szrj /* Return true if there is any work to be done by update_ssa
3029*38fd1498Szrj for function FN. */
3030*38fd1498Szrj
3031*38fd1498Szrj bool
need_ssa_update_p(struct function * fn)3032*38fd1498Szrj need_ssa_update_p (struct function *fn)
3033*38fd1498Szrj {
3034*38fd1498Szrj gcc_assert (fn != NULL);
3035*38fd1498Szrj return (update_ssa_initialized_fn == fn
3036*38fd1498Szrj || (fn->gimple_df && fn->gimple_df->ssa_renaming_needed));
3037*38fd1498Szrj }
3038*38fd1498Szrj
3039*38fd1498Szrj /* Return true if name N has been registered in the replacement table. */
3040*38fd1498Szrj
3041*38fd1498Szrj bool
name_registered_for_update_p(tree n ATTRIBUTE_UNUSED)3042*38fd1498Szrj name_registered_for_update_p (tree n ATTRIBUTE_UNUSED)
3043*38fd1498Szrj {
3044*38fd1498Szrj if (!update_ssa_initialized_fn)
3045*38fd1498Szrj return false;
3046*38fd1498Szrj
3047*38fd1498Szrj gcc_assert (update_ssa_initialized_fn == cfun);
3048*38fd1498Szrj
3049*38fd1498Szrj return is_new_name (n) || is_old_name (n);
3050*38fd1498Szrj }
3051*38fd1498Szrj
3052*38fd1498Szrj
3053*38fd1498Szrj /* Mark NAME to be released after update_ssa has finished. */
3054*38fd1498Szrj
3055*38fd1498Szrj void
release_ssa_name_after_update_ssa(tree name)3056*38fd1498Szrj release_ssa_name_after_update_ssa (tree name)
3057*38fd1498Szrj {
3058*38fd1498Szrj gcc_assert (cfun && update_ssa_initialized_fn == cfun);
3059*38fd1498Szrj
3060*38fd1498Szrj if (names_to_release == NULL)
3061*38fd1498Szrj names_to_release = BITMAP_ALLOC (NULL);
3062*38fd1498Szrj
3063*38fd1498Szrj bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
3064*38fd1498Szrj }
3065*38fd1498Szrj
3066*38fd1498Szrj
3067*38fd1498Szrj /* Insert new PHI nodes to replace VAR. DFS contains dominance
3068*38fd1498Szrj frontier information. BLOCKS is the set of blocks to be updated.
3069*38fd1498Szrj
3070*38fd1498Szrj This is slightly different than the regular PHI insertion
3071*38fd1498Szrj algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
3072*38fd1498Szrj real names (i.e., GIMPLE registers) are inserted:
3073*38fd1498Szrj
3074*38fd1498Szrj - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
3075*38fd1498Szrj nodes inside the region affected by the block that defines VAR
3076*38fd1498Szrj and the blocks that define all its replacements. All these
3077*38fd1498Szrj definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
3078*38fd1498Szrj
3079*38fd1498Szrj First, we compute the entry point to the region (ENTRY). This is
3080*38fd1498Szrj given by the nearest common dominator to all the definition
3081*38fd1498Szrj blocks. When computing the iterated dominance frontier (IDF), any
3082*38fd1498Szrj block not strictly dominated by ENTRY is ignored.
3083*38fd1498Szrj
3084*38fd1498Szrj We then call the standard PHI insertion algorithm with the pruned
3085*38fd1498Szrj IDF.
3086*38fd1498Szrj
3087*38fd1498Szrj - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
3088*38fd1498Szrj names is not pruned. PHI nodes are inserted at every IDF block. */
3089*38fd1498Szrj
3090*38fd1498Szrj static void
insert_updated_phi_nodes_for(tree var,bitmap_head * dfs,bitmap blocks,unsigned update_flags)3091*38fd1498Szrj insert_updated_phi_nodes_for (tree var, bitmap_head *dfs, bitmap blocks,
3092*38fd1498Szrj unsigned update_flags)
3093*38fd1498Szrj {
3094*38fd1498Szrj basic_block entry;
3095*38fd1498Szrj def_blocks *db;
3096*38fd1498Szrj bitmap idf, pruned_idf;
3097*38fd1498Szrj bitmap_iterator bi;
3098*38fd1498Szrj unsigned i;
3099*38fd1498Szrj
3100*38fd1498Szrj if (TREE_CODE (var) == SSA_NAME)
3101*38fd1498Szrj gcc_checking_assert (is_old_name (var));
3102*38fd1498Szrj else
3103*38fd1498Szrj gcc_checking_assert (marked_for_renaming (var));
3104*38fd1498Szrj
3105*38fd1498Szrj /* Get all the definition sites for VAR. */
3106*38fd1498Szrj db = find_def_blocks_for (var);
3107*38fd1498Szrj
3108*38fd1498Szrj /* No need to do anything if there were no definitions to VAR. */
3109*38fd1498Szrj if (db == NULL || bitmap_empty_p (db->def_blocks))
3110*38fd1498Szrj return;
3111*38fd1498Szrj
3112*38fd1498Szrj /* Compute the initial iterated dominance frontier. */
3113*38fd1498Szrj idf = compute_idf (db->def_blocks, dfs);
3114*38fd1498Szrj pruned_idf = BITMAP_ALLOC (NULL);
3115*38fd1498Szrj
3116*38fd1498Szrj if (TREE_CODE (var) == SSA_NAME)
3117*38fd1498Szrj {
3118*38fd1498Szrj if (update_flags == TODO_update_ssa)
3119*38fd1498Szrj {
3120*38fd1498Szrj /* If doing regular SSA updates for GIMPLE registers, we are
3121*38fd1498Szrj only interested in IDF blocks dominated by the nearest
3122*38fd1498Szrj common dominator of all the definition blocks. */
3123*38fd1498Szrj entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
3124*38fd1498Szrj db->def_blocks);
3125*38fd1498Szrj if (entry != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3126*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
3127*38fd1498Szrj if (BASIC_BLOCK_FOR_FN (cfun, i) != entry
3128*38fd1498Szrj && dominated_by_p (CDI_DOMINATORS,
3129*38fd1498Szrj BASIC_BLOCK_FOR_FN (cfun, i), entry))
3130*38fd1498Szrj bitmap_set_bit (pruned_idf, i);
3131*38fd1498Szrj }
3132*38fd1498Szrj else
3133*38fd1498Szrj {
3134*38fd1498Szrj /* Otherwise, do not prune the IDF for VAR. */
3135*38fd1498Szrj gcc_checking_assert (update_flags == TODO_update_ssa_full_phi);
3136*38fd1498Szrj bitmap_copy (pruned_idf, idf);
3137*38fd1498Szrj }
3138*38fd1498Szrj }
3139*38fd1498Szrj else
3140*38fd1498Szrj {
3141*38fd1498Szrj /* Otherwise, VAR is a symbol that needs to be put into SSA form
3142*38fd1498Szrj for the first time, so we need to compute the full IDF for
3143*38fd1498Szrj it. */
3144*38fd1498Szrj bitmap_copy (pruned_idf, idf);
3145*38fd1498Szrj }
3146*38fd1498Szrj
3147*38fd1498Szrj if (!bitmap_empty_p (pruned_idf))
3148*38fd1498Szrj {
3149*38fd1498Szrj /* Make sure that PRUNED_IDF blocks and all their feeding blocks
3150*38fd1498Szrj are included in the region to be updated. The feeding blocks
3151*38fd1498Szrj are important to guarantee that the PHI arguments are renamed
3152*38fd1498Szrj properly. */
3153*38fd1498Szrj
3154*38fd1498Szrj /* FIXME, this is not needed if we are updating symbols. We are
3155*38fd1498Szrj already starting at the ENTRY block anyway. */
3156*38fd1498Szrj bitmap_ior_into (blocks, pruned_idf);
3157*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
3158*38fd1498Szrj {
3159*38fd1498Szrj edge e;
3160*38fd1498Szrj edge_iterator ei;
3161*38fd1498Szrj basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
3162*38fd1498Szrj
3163*38fd1498Szrj FOR_EACH_EDGE (e, ei, bb->preds)
3164*38fd1498Szrj if (e->src->index >= 0)
3165*38fd1498Szrj bitmap_set_bit (blocks, e->src->index);
3166*38fd1498Szrj }
3167*38fd1498Szrj
3168*38fd1498Szrj insert_phi_nodes_for (var, pruned_idf, true);
3169*38fd1498Szrj }
3170*38fd1498Szrj
3171*38fd1498Szrj BITMAP_FREE (pruned_idf);
3172*38fd1498Szrj BITMAP_FREE (idf);
3173*38fd1498Szrj }
3174*38fd1498Szrj
3175*38fd1498Szrj /* Sort symbols_to_rename after their DECL_UID. */
3176*38fd1498Szrj
3177*38fd1498Szrj static int
insert_updated_phi_nodes_compare_uids(const void * a,const void * b)3178*38fd1498Szrj insert_updated_phi_nodes_compare_uids (const void *a, const void *b)
3179*38fd1498Szrj {
3180*38fd1498Szrj const_tree syma = *(const const_tree *)a;
3181*38fd1498Szrj const_tree symb = *(const const_tree *)b;
3182*38fd1498Szrj if (DECL_UID (syma) == DECL_UID (symb))
3183*38fd1498Szrj return 0;
3184*38fd1498Szrj return DECL_UID (syma) < DECL_UID (symb) ? -1 : 1;
3185*38fd1498Szrj }
3186*38fd1498Szrj
3187*38fd1498Szrj /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3188*38fd1498Szrj existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3189*38fd1498Szrj
3190*38fd1498Szrj 1- The names in OLD_SSA_NAMES dominated by the definitions of
3191*38fd1498Szrj NEW_SSA_NAMES are all re-written to be reached by the
3192*38fd1498Szrj appropriate definition from NEW_SSA_NAMES.
3193*38fd1498Szrj
3194*38fd1498Szrj 2- If needed, new PHI nodes are added to the iterated dominance
3195*38fd1498Szrj frontier of the blocks where each of NEW_SSA_NAMES are defined.
3196*38fd1498Szrj
3197*38fd1498Szrj The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3198*38fd1498Szrj calling create_new_def_for to create new defs for names that the
3199*38fd1498Szrj caller wants to replace.
3200*38fd1498Szrj
3201*38fd1498Szrj The caller cretaes the new names to be inserted and the names that need
3202*38fd1498Szrj to be replaced by calling create_new_def_for for each old definition
3203*38fd1498Szrj to be replaced. Note that the function assumes that the
3204*38fd1498Szrj new defining statement has already been inserted in the IL.
3205*38fd1498Szrj
3206*38fd1498Szrj For instance, given the following code:
3207*38fd1498Szrj
3208*38fd1498Szrj 1 L0:
3209*38fd1498Szrj 2 x_1 = PHI (0, x_5)
3210*38fd1498Szrj 3 if (x_1 < 10)
3211*38fd1498Szrj 4 if (x_1 > 7)
3212*38fd1498Szrj 5 y_2 = 0
3213*38fd1498Szrj 6 else
3214*38fd1498Szrj 7 y_3 = x_1 + x_7
3215*38fd1498Szrj 8 endif
3216*38fd1498Szrj 9 x_5 = x_1 + 1
3217*38fd1498Szrj 10 goto L0;
3218*38fd1498Szrj 11 endif
3219*38fd1498Szrj
3220*38fd1498Szrj Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3221*38fd1498Szrj
3222*38fd1498Szrj 1 L0:
3223*38fd1498Szrj 2 x_1 = PHI (0, x_5)
3224*38fd1498Szrj 3 if (x_1 < 10)
3225*38fd1498Szrj 4 x_10 = ...
3226*38fd1498Szrj 5 if (x_1 > 7)
3227*38fd1498Szrj 6 y_2 = 0
3228*38fd1498Szrj 7 else
3229*38fd1498Szrj 8 x_11 = ...
3230*38fd1498Szrj 9 y_3 = x_1 + x_7
3231*38fd1498Szrj 10 endif
3232*38fd1498Szrj 11 x_5 = x_1 + 1
3233*38fd1498Szrj 12 goto L0;
3234*38fd1498Szrj 13 endif
3235*38fd1498Szrj
3236*38fd1498Szrj We want to replace all the uses of x_1 with the new definitions of
3237*38fd1498Szrj x_10 and x_11. Note that the only uses that should be replaced are
3238*38fd1498Szrj those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3239*38fd1498Szrj *not* be replaced (this is why we cannot just mark symbol 'x' for
3240*38fd1498Szrj renaming).
3241*38fd1498Szrj
3242*38fd1498Szrj Additionally, we may need to insert a PHI node at line 11 because
3243*38fd1498Szrj that is a merge point for x_10 and x_11. So the use of x_1 at line
3244*38fd1498Szrj 11 will be replaced with the new PHI node. The insertion of PHI
3245*38fd1498Szrj nodes is optional. They are not strictly necessary to preserve the
3246*38fd1498Szrj SSA form, and depending on what the caller inserted, they may not
3247*38fd1498Szrj even be useful for the optimizers. UPDATE_FLAGS controls various
3248*38fd1498Szrj aspects of how update_ssa operates, see the documentation for
3249*38fd1498Szrj TODO_update_ssa*. */
3250*38fd1498Szrj
3251*38fd1498Szrj void
update_ssa(unsigned update_flags)3252*38fd1498Szrj update_ssa (unsigned update_flags)
3253*38fd1498Szrj {
3254*38fd1498Szrj basic_block bb, start_bb;
3255*38fd1498Szrj bitmap_iterator bi;
3256*38fd1498Szrj unsigned i = 0;
3257*38fd1498Szrj bool insert_phi_p;
3258*38fd1498Szrj sbitmap_iterator sbi;
3259*38fd1498Szrj tree sym;
3260*38fd1498Szrj
3261*38fd1498Szrj /* Only one update flag should be set. */
3262*38fd1498Szrj gcc_assert (update_flags == TODO_update_ssa
3263*38fd1498Szrj || update_flags == TODO_update_ssa_no_phi
3264*38fd1498Szrj || update_flags == TODO_update_ssa_full_phi
3265*38fd1498Szrj || update_flags == TODO_update_ssa_only_virtuals);
3266*38fd1498Szrj
3267*38fd1498Szrj if (!need_ssa_update_p (cfun))
3268*38fd1498Szrj return;
3269*38fd1498Szrj
3270*38fd1498Szrj if (flag_checking)
3271*38fd1498Szrj {
3272*38fd1498Szrj timevar_push (TV_TREE_STMT_VERIFY);
3273*38fd1498Szrj
3274*38fd1498Szrj bool err = false;
3275*38fd1498Szrj
3276*38fd1498Szrj FOR_EACH_BB_FN (bb, cfun)
3277*38fd1498Szrj {
3278*38fd1498Szrj gimple_stmt_iterator gsi;
3279*38fd1498Szrj for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3280*38fd1498Szrj {
3281*38fd1498Szrj gimple *stmt = gsi_stmt (gsi);
3282*38fd1498Szrj
3283*38fd1498Szrj ssa_op_iter i;
3284*38fd1498Szrj use_operand_p use_p;
3285*38fd1498Szrj FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_ALL_USES)
3286*38fd1498Szrj {
3287*38fd1498Szrj tree use = USE_FROM_PTR (use_p);
3288*38fd1498Szrj if (TREE_CODE (use) != SSA_NAME)
3289*38fd1498Szrj continue;
3290*38fd1498Szrj
3291*38fd1498Szrj if (SSA_NAME_IN_FREE_LIST (use))
3292*38fd1498Szrj {
3293*38fd1498Szrj error ("statement uses released SSA name:");
3294*38fd1498Szrj debug_gimple_stmt (stmt);
3295*38fd1498Szrj fprintf (stderr, "The use of ");
3296*38fd1498Szrj print_generic_expr (stderr, use);
3297*38fd1498Szrj fprintf (stderr," should have been replaced\n");
3298*38fd1498Szrj err = true;
3299*38fd1498Szrj }
3300*38fd1498Szrj }
3301*38fd1498Szrj }
3302*38fd1498Szrj }
3303*38fd1498Szrj
3304*38fd1498Szrj if (err)
3305*38fd1498Szrj internal_error ("cannot update SSA form");
3306*38fd1498Szrj
3307*38fd1498Szrj timevar_pop (TV_TREE_STMT_VERIFY);
3308*38fd1498Szrj }
3309*38fd1498Szrj
3310*38fd1498Szrj timevar_push (TV_TREE_SSA_INCREMENTAL);
3311*38fd1498Szrj
3312*38fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
3313*38fd1498Szrj fprintf (dump_file, "\nUpdating SSA:\n");
3314*38fd1498Szrj
3315*38fd1498Szrj if (!update_ssa_initialized_fn)
3316*38fd1498Szrj init_update_ssa (cfun);
3317*38fd1498Szrj else if (update_flags == TODO_update_ssa_only_virtuals)
3318*38fd1498Szrj {
3319*38fd1498Szrj /* If we only need to update virtuals, remove all the mappings for
3320*38fd1498Szrj real names before proceeding. The caller is responsible for
3321*38fd1498Szrj having dealt with the name mappings before calling update_ssa. */
3322*38fd1498Szrj bitmap_clear (old_ssa_names);
3323*38fd1498Szrj bitmap_clear (new_ssa_names);
3324*38fd1498Szrj }
3325*38fd1498Szrj
3326*38fd1498Szrj gcc_assert (update_ssa_initialized_fn == cfun);
3327*38fd1498Szrj
3328*38fd1498Szrj blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
3329*38fd1498Szrj if (!phis_to_rewrite.exists ())
3330*38fd1498Szrj phis_to_rewrite.create (last_basic_block_for_fn (cfun) + 1);
3331*38fd1498Szrj blocks_to_update = BITMAP_ALLOC (NULL);
3332*38fd1498Szrj
3333*38fd1498Szrj /* Ensure that the dominance information is up-to-date. */
3334*38fd1498Szrj calculate_dominance_info (CDI_DOMINATORS);
3335*38fd1498Szrj
3336*38fd1498Szrj insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
3337*38fd1498Szrj
3338*38fd1498Szrj /* If there are names defined in the replacement table, prepare
3339*38fd1498Szrj definition and use sites for all the names in NEW_SSA_NAMES and
3340*38fd1498Szrj OLD_SSA_NAMES. */
3341*38fd1498Szrj if (bitmap_first_set_bit (new_ssa_names) >= 0)
3342*38fd1498Szrj {
3343*38fd1498Szrj statistics_counter_event (cfun, "Incremental SSA update", 1);
3344*38fd1498Szrj
3345*38fd1498Szrj prepare_names_to_update (insert_phi_p);
3346*38fd1498Szrj
3347*38fd1498Szrj /* If all the names in NEW_SSA_NAMES had been marked for
3348*38fd1498Szrj removal, and there are no symbols to rename, then there's
3349*38fd1498Szrj nothing else to do. */
3350*38fd1498Szrj if (bitmap_first_set_bit (new_ssa_names) < 0
3351*38fd1498Szrj && !cfun->gimple_df->ssa_renaming_needed)
3352*38fd1498Szrj goto done;
3353*38fd1498Szrj }
3354*38fd1498Szrj
3355*38fd1498Szrj /* Next, determine the block at which to start the renaming process. */
3356*38fd1498Szrj if (cfun->gimple_df->ssa_renaming_needed)
3357*38fd1498Szrj {
3358*38fd1498Szrj statistics_counter_event (cfun, "Symbol to SSA rewrite", 1);
3359*38fd1498Szrj
3360*38fd1498Szrj /* If we rename bare symbols initialize the mapping to
3361*38fd1498Szrj auxiliar info we need to keep track of. */
3362*38fd1498Szrj var_infos = new hash_table<var_info_hasher> (47);
3363*38fd1498Szrj
3364*38fd1498Szrj /* If we have to rename some symbols from scratch, we need to
3365*38fd1498Szrj start the process at the root of the CFG. FIXME, it should
3366*38fd1498Szrj be possible to determine the nearest block that had a
3367*38fd1498Szrj definition for each of the symbols that are marked for
3368*38fd1498Szrj updating. For now this seems more work than it's worth. */
3369*38fd1498Szrj start_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3370*38fd1498Szrj
3371*38fd1498Szrj /* Traverse the CFG looking for existing definitions and uses of
3372*38fd1498Szrj symbols in SSA operands. Mark interesting blocks and
3373*38fd1498Szrj statements and set local live-in information for the PHI
3374*38fd1498Szrj placement heuristics. */
3375*38fd1498Szrj prepare_block_for_update (start_bb, insert_phi_p);
3376*38fd1498Szrj
3377*38fd1498Szrj tree name;
3378*38fd1498Szrj
3379*38fd1498Szrj if (flag_checking)
3380*38fd1498Szrj FOR_EACH_SSA_NAME (i, name, cfun)
3381*38fd1498Szrj {
3382*38fd1498Szrj if (virtual_operand_p (name))
3383*38fd1498Szrj continue;
3384*38fd1498Szrj
3385*38fd1498Szrj /* For all but virtual operands, which do not have SSA names
3386*38fd1498Szrj with overlapping life ranges, ensure that symbols marked
3387*38fd1498Szrj for renaming do not have existing SSA names associated with
3388*38fd1498Szrj them as we do not re-write them out-of-SSA before going
3389*38fd1498Szrj into SSA for the remaining symbol uses. */
3390*38fd1498Szrj if (marked_for_renaming (SSA_NAME_VAR (name)))
3391*38fd1498Szrj {
3392*38fd1498Szrj fprintf (stderr, "Existing SSA name for symbol marked for "
3393*38fd1498Szrj "renaming: ");
3394*38fd1498Szrj print_generic_expr (stderr, name, TDF_SLIM);
3395*38fd1498Szrj fprintf (stderr, "\n");
3396*38fd1498Szrj internal_error ("SSA corruption");
3397*38fd1498Szrj }
3398*38fd1498Szrj }
3399*38fd1498Szrj }
3400*38fd1498Szrj else
3401*38fd1498Szrj {
3402*38fd1498Szrj /* Otherwise, the entry block to the region is the nearest
3403*38fd1498Szrj common dominator for the blocks in BLOCKS. */
3404*38fd1498Szrj start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3405*38fd1498Szrj blocks_to_update);
3406*38fd1498Szrj }
3407*38fd1498Szrj
3408*38fd1498Szrj /* If requested, insert PHI nodes at the iterated dominance frontier
3409*38fd1498Szrj of every block, creating new definitions for names in OLD_SSA_NAMES
3410*38fd1498Szrj and for symbols found. */
3411*38fd1498Szrj if (insert_phi_p)
3412*38fd1498Szrj {
3413*38fd1498Szrj bitmap_head *dfs;
3414*38fd1498Szrj
3415*38fd1498Szrj /* If the caller requested PHI nodes to be added, compute
3416*38fd1498Szrj dominance frontiers. */
3417*38fd1498Szrj dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
3418*38fd1498Szrj FOR_EACH_BB_FN (bb, cfun)
3419*38fd1498Szrj bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
3420*38fd1498Szrj compute_dominance_frontiers (dfs);
3421*38fd1498Szrj
3422*38fd1498Szrj if (bitmap_first_set_bit (old_ssa_names) >= 0)
3423*38fd1498Szrj {
3424*38fd1498Szrj sbitmap_iterator sbi;
3425*38fd1498Szrj
3426*38fd1498Szrj /* insert_update_phi_nodes_for will call add_new_name_mapping
3427*38fd1498Szrj when inserting new PHI nodes, so the set OLD_SSA_NAMES
3428*38fd1498Szrj will grow while we are traversing it (but it will not
3429*38fd1498Szrj gain any new members). Copy OLD_SSA_NAMES to a temporary
3430*38fd1498Szrj for traversal. */
3431*38fd1498Szrj auto_sbitmap tmp (SBITMAP_SIZE (old_ssa_names));
3432*38fd1498Szrj bitmap_copy (tmp, old_ssa_names);
3433*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, sbi)
3434*38fd1498Szrj insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
3435*38fd1498Szrj update_flags);
3436*38fd1498Szrj }
3437*38fd1498Szrj
3438*38fd1498Szrj symbols_to_rename.qsort (insert_updated_phi_nodes_compare_uids);
3439*38fd1498Szrj FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3440*38fd1498Szrj insert_updated_phi_nodes_for (sym, dfs, blocks_to_update,
3441*38fd1498Szrj update_flags);
3442*38fd1498Szrj
3443*38fd1498Szrj FOR_EACH_BB_FN (bb, cfun)
3444*38fd1498Szrj bitmap_clear (&dfs[bb->index]);
3445*38fd1498Szrj free (dfs);
3446*38fd1498Szrj
3447*38fd1498Szrj /* Insertion of PHI nodes may have added blocks to the region.
3448*38fd1498Szrj We need to re-compute START_BB to include the newly added
3449*38fd1498Szrj blocks. */
3450*38fd1498Szrj if (start_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3451*38fd1498Szrj start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3452*38fd1498Szrj blocks_to_update);
3453*38fd1498Szrj }
3454*38fd1498Szrj
3455*38fd1498Szrj /* Reset the current definition for name and symbol before renaming
3456*38fd1498Szrj the sub-graph. */
3457*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
3458*38fd1498Szrj get_ssa_name_ann (ssa_name (i))->info.current_def = NULL_TREE;
3459*38fd1498Szrj
3460*38fd1498Szrj FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3461*38fd1498Szrj get_var_info (sym)->info.current_def = NULL_TREE;
3462*38fd1498Szrj
3463*38fd1498Szrj /* Now start the renaming process at START_BB. */
3464*38fd1498Szrj interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
3465*38fd1498Szrj bitmap_clear (interesting_blocks);
3466*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3467*38fd1498Szrj bitmap_set_bit (interesting_blocks, i);
3468*38fd1498Szrj
3469*38fd1498Szrj rewrite_blocks (start_bb, REWRITE_UPDATE);
3470*38fd1498Szrj
3471*38fd1498Szrj sbitmap_free (interesting_blocks);
3472*38fd1498Szrj
3473*38fd1498Szrj /* Debugging dumps. */
3474*38fd1498Szrj if (dump_file)
3475*38fd1498Szrj {
3476*38fd1498Szrj int c;
3477*38fd1498Szrj unsigned i;
3478*38fd1498Szrj
3479*38fd1498Szrj dump_update_ssa (dump_file);
3480*38fd1498Szrj
3481*38fd1498Szrj fprintf (dump_file, "Incremental SSA update started at block: %d\n",
3482*38fd1498Szrj start_bb->index);
3483*38fd1498Szrj
3484*38fd1498Szrj c = 0;
3485*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3486*38fd1498Szrj c++;
3487*38fd1498Szrj fprintf (dump_file, "Number of blocks in CFG: %d\n",
3488*38fd1498Szrj last_basic_block_for_fn (cfun));
3489*38fd1498Szrj fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n",
3490*38fd1498Szrj c, PERCENT (c, last_basic_block_for_fn (cfun)));
3491*38fd1498Szrj
3492*38fd1498Szrj if (dump_flags & TDF_DETAILS)
3493*38fd1498Szrj {
3494*38fd1498Szrj fprintf (dump_file, "Affected blocks:");
3495*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3496*38fd1498Szrj fprintf (dump_file, " %u", i);
3497*38fd1498Szrj fprintf (dump_file, "\n");
3498*38fd1498Szrj }
3499*38fd1498Szrj
3500*38fd1498Szrj fprintf (dump_file, "\n\n");
3501*38fd1498Szrj }
3502*38fd1498Szrj
3503*38fd1498Szrj /* Free allocated memory. */
3504*38fd1498Szrj done:
3505*38fd1498Szrj delete_update_ssa ();
3506*38fd1498Szrj
3507*38fd1498Szrj timevar_pop (TV_TREE_SSA_INCREMENTAL);
3508*38fd1498Szrj }
3509