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