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