]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Liveness for SSA trees. |
c8d3e15a | 2 | Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. |
6de9cd9a DN |
3 | Contributed by Andrew MacLeod <amacleod@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 | |
366ccddb KC |
19 | the Free Software Foundation, 51 Franklin Street, Fifth Floor, |
20 | Boston, MA 02110-1301, USA. */ | |
6de9cd9a DN |
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 "basic-block.h" | |
29 | #include "function.h" | |
30 | #include "diagnostic.h" | |
31 | #include "bitmap.h" | |
32 | #include "tree-flow.h" | |
eadf906f | 33 | #include "tree-gimple.h" |
6de9cd9a DN |
34 | #include "tree-inline.h" |
35 | #include "varray.h" | |
36 | #include "timevar.h" | |
6de9cd9a DN |
37 | #include "hashtab.h" |
38 | #include "tree-dump.h" | |
39 | #include "tree-ssa-live.h" | |
4c714dd4 | 40 | #include "toplev.h" |
6de9cd9a | 41 | |
d0b06ef9 | 42 | static void live_worklist (tree_live_info_p, int *, int); |
6de9cd9a DN |
43 | static tree_live_info_p new_tree_live_info (var_map); |
44 | static inline void set_if_valid (var_map, bitmap, tree); | |
45 | static inline void add_livein_if_notdef (tree_live_info_p, bitmap, | |
46 | tree, basic_block); | |
47 | static inline void register_ssa_partition (var_map, tree, bool); | |
48 | static inline void add_conflicts_if_valid (tpa_p, conflict_graph, | |
49 | var_map, bitmap, tree); | |
50 | static partition_pair_p find_partition_pair (coalesce_list_p, int, int, bool); | |
51 | ||
52 | /* This is where the mapping from SSA version number to real storage variable | |
53 | is tracked. | |
54 | ||
55 | All SSA versions of the same variable may not ultimately be mapped back to | |
56 | the same real variable. In that instance, we need to detect the live | |
57 | range overlap, and give one of the variable new storage. The vector | |
58 | 'partition_to_var' tracks which partition maps to which variable. | |
59 | ||
60 | Given a VAR, it is sometimes desirable to know which partition that VAR | |
61 | represents. There is an additional field in the variable annotation to | |
62 | track that information. */ | |
63 | ||
64 | /* Create a variable partition map of SIZE, initialize and return it. */ | |
65 | ||
66 | var_map | |
67 | init_var_map (int size) | |
68 | { | |
69 | var_map map; | |
70 | ||
71 | map = (var_map) xmalloc (sizeof (struct _var_map)); | |
72 | map->var_partition = partition_new (size); | |
73 | map->partition_to_var | |
74 | = (tree *)xmalloc (size * sizeof (tree)); | |
75 | memset (map->partition_to_var, 0, size * sizeof (tree)); | |
76 | ||
77 | map->partition_to_compact = NULL; | |
78 | map->compact_to_partition = NULL; | |
79 | map->num_partitions = size; | |
80 | map->partition_size = size; | |
81 | map->ref_count = NULL; | |
82 | return map; | |
83 | } | |
84 | ||
85 | ||
86 | /* Free memory associated with MAP. */ | |
87 | ||
88 | void | |
89 | delete_var_map (var_map map) | |
90 | { | |
91 | free (map->partition_to_var); | |
92 | partition_delete (map->var_partition); | |
93 | if (map->partition_to_compact) | |
94 | free (map->partition_to_compact); | |
95 | if (map->compact_to_partition) | |
96 | free (map->compact_to_partition); | |
97 | if (map->ref_count) | |
98 | free (map->ref_count); | |
99 | free (map); | |
100 | } | |
101 | ||
102 | ||
103 | /* This function will combine the partitions in MAP for VAR1 and VAR2. It | |
104 | Returns the partition which represents the new partition. If the two | |
9cf737f8 | 105 | partitions cannot be combined, NO_PARTITION is returned. */ |
6de9cd9a DN |
106 | |
107 | int | |
108 | var_union (var_map map, tree var1, tree var2) | |
109 | { | |
110 | int p1, p2, p3; | |
111 | tree root_var = NULL_TREE; | |
112 | tree other_var = NULL_TREE; | |
113 | ||
114 | /* This is independent of partition_to_compact. If partition_to_compact is | |
115 | on, then whichever one of these partitions is absorbed will never have a | |
116 | dereference into the partition_to_compact array any more. */ | |
117 | ||
118 | if (TREE_CODE (var1) == SSA_NAME) | |
119 | p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1)); | |
120 | else | |
121 | { | |
122 | p1 = var_to_partition (map, var1); | |
123 | if (map->compact_to_partition) | |
124 | p1 = map->compact_to_partition[p1]; | |
125 | root_var = var1; | |
126 | } | |
127 | ||
128 | if (TREE_CODE (var2) == SSA_NAME) | |
129 | p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2)); | |
130 | else | |
131 | { | |
132 | p2 = var_to_partition (map, var2); | |
133 | if (map->compact_to_partition) | |
134 | p2 = map->compact_to_partition[p2]; | |
135 | ||
89dbed81 | 136 | /* If there is no root_var set, or it's not a user variable, set the |
6de9cd9a | 137 | root_var to this one. */ |
17ad5b5e | 138 | if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var))) |
6de9cd9a DN |
139 | { |
140 | other_var = root_var; | |
141 | root_var = var2; | |
142 | } | |
143 | else | |
144 | other_var = var2; | |
145 | } | |
146 | ||
1e128c5f GB |
147 | gcc_assert (p1 != NO_PARTITION); |
148 | gcc_assert (p2 != NO_PARTITION); | |
6de9cd9a DN |
149 | |
150 | if (p1 == p2) | |
151 | p3 = p1; | |
152 | else | |
153 | p3 = partition_union (map->var_partition, p1, p2); | |
154 | ||
155 | if (map->partition_to_compact) | |
156 | p3 = map->partition_to_compact[p3]; | |
157 | ||
158 | if (root_var) | |
159 | change_partition_var (map, root_var, p3); | |
160 | if (other_var) | |
161 | change_partition_var (map, other_var, p3); | |
162 | ||
163 | return p3; | |
164 | } | |
165 | ||
166 | ||
167 | /* Compress the partition numbers in MAP such that they fall in the range | |
168 | 0..(num_partitions-1) instead of wherever they turned out during | |
169 | the partitioning exercise. This removes any references to unused | |
170 | partitions, thereby allowing bitmaps and other vectors to be much | |
171 | denser. Compression type is controlled by FLAGS. | |
172 | ||
173 | This is implemented such that compaction doesn't affect partitioning. | |
174 | Ie., once partitions are created and possibly merged, running one | |
175 | or more different kind of compaction will not affect the partitions | |
176 | themselves. Their index might change, but all the same variables will | |
177 | still be members of the same partition group. This allows work on reduced | |
178 | sets, and no loss of information when a larger set is later desired. | |
179 | ||
180 | In particular, coalescing can work on partitions which have 2 or more | |
181 | definitions, and then 'recompact' later to include all the single | |
182 | definitions for assignment to program variables. */ | |
183 | ||
184 | void | |
185 | compact_var_map (var_map map, int flags) | |
186 | { | |
187 | sbitmap used; | |
b6e7e9af KH |
188 | int tmp, root, root_i; |
189 | unsigned int x, limit, count; | |
6de9cd9a DN |
190 | tree var; |
191 | root_var_p rv = NULL; | |
192 | ||
193 | limit = map->partition_size; | |
194 | used = sbitmap_alloc (limit); | |
195 | sbitmap_zero (used); | |
196 | ||
197 | /* Already compressed? Abandon the old one. */ | |
198 | if (map->partition_to_compact) | |
199 | { | |
200 | free (map->partition_to_compact); | |
201 | map->partition_to_compact = NULL; | |
202 | } | |
203 | if (map->compact_to_partition) | |
204 | { | |
205 | free (map->compact_to_partition); | |
206 | map->compact_to_partition = NULL; | |
207 | } | |
208 | ||
209 | map->num_partitions = map->partition_size; | |
210 | ||
211 | if (flags & VARMAP_NO_SINGLE_DEFS) | |
212 | rv = root_var_init (map); | |
213 | ||
214 | map->partition_to_compact = (int *)xmalloc (limit * sizeof (int)); | |
215 | memset (map->partition_to_compact, 0xff, (limit * sizeof (int))); | |
216 | ||
217 | /* Find out which partitions are actually referenced. */ | |
218 | count = 0; | |
219 | for (x = 0; x < limit; x++) | |
220 | { | |
221 | tmp = partition_find (map->var_partition, x); | |
222 | if (!TEST_BIT (used, tmp) && map->partition_to_var[tmp] != NULL_TREE) | |
223 | { | |
224 | /* It is referenced, check to see if there is more than one version | |
225 | in the root_var table, if one is available. */ | |
226 | if (rv) | |
227 | { | |
228 | root = root_var_find (rv, tmp); | |
229 | root_i = root_var_first_partition (rv, root); | |
230 | /* If there is only one, don't include this in the compaction. */ | |
231 | if (root_var_next_partition (rv, root_i) == ROOT_VAR_NONE) | |
232 | continue; | |
233 | } | |
234 | SET_BIT (used, tmp); | |
235 | count++; | |
236 | } | |
237 | } | |
238 | ||
239 | /* Build a compacted partitioning. */ | |
240 | if (count != limit) | |
241 | { | |
b6e7e9af KH |
242 | sbitmap_iterator sbi; |
243 | ||
6de9cd9a DN |
244 | map->compact_to_partition = (int *)xmalloc (count * sizeof (int)); |
245 | count = 0; | |
246 | /* SSA renaming begins at 1, so skip 0 when compacting. */ | |
b6e7e9af | 247 | EXECUTE_IF_SET_IN_SBITMAP (used, 1, x, sbi) |
6de9cd9a DN |
248 | { |
249 | map->partition_to_compact[x] = count; | |
250 | map->compact_to_partition[count] = x; | |
251 | var = map->partition_to_var[x]; | |
252 | if (TREE_CODE (var) != SSA_NAME) | |
253 | change_partition_var (map, var, count); | |
254 | count++; | |
b6e7e9af | 255 | } |
6de9cd9a DN |
256 | } |
257 | else | |
258 | { | |
259 | free (map->partition_to_compact); | |
260 | map->partition_to_compact = NULL; | |
261 | } | |
262 | ||
263 | map->num_partitions = count; | |
264 | ||
265 | if (rv) | |
266 | root_var_delete (rv); | |
267 | sbitmap_free (used); | |
268 | } | |
269 | ||
270 | ||
271 | /* This function is used to change the representative variable in MAP for VAR's | |
272 | partition from an SSA_NAME variable to a regular variable. This allows | |
273 | partitions to be mapped back to real variables. */ | |
274 | ||
275 | void | |
276 | change_partition_var (var_map map, tree var, int part) | |
277 | { | |
278 | var_ann_t ann; | |
279 | ||
1e128c5f | 280 | gcc_assert (TREE_CODE (var) != SSA_NAME); |
6de9cd9a DN |
281 | |
282 | ann = var_ann (var); | |
283 | ann->out_of_ssa_tag = 1; | |
284 | VAR_ANN_PARTITION (ann) = part; | |
285 | if (map->compact_to_partition) | |
286 | map->partition_to_var[map->compact_to_partition[part]] = var; | |
287 | } | |
288 | ||
89632019 | 289 | static inline void mark_all_vars_used (tree *); |
6de9cd9a | 290 | |
727a31fa RH |
291 | /* Helper function for mark_all_vars_used, called via walk_tree. */ |
292 | ||
293 | static tree | |
294 | mark_all_vars_used_1 (tree *tp, int *walk_subtrees, | |
295 | void *data ATTRIBUTE_UNUSED) | |
296 | { | |
297 | tree t = *tp; | |
298 | ||
89632019 ZD |
299 | /* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other |
300 | fields that do not contain vars. */ | |
301 | if (TREE_CODE (t) == TARGET_MEM_REF) | |
302 | { | |
303 | mark_all_vars_used (&TMR_SYMBOL (t)); | |
304 | mark_all_vars_used (&TMR_BASE (t)); | |
305 | mark_all_vars_used (&TMR_INDEX (t)); | |
306 | *walk_subtrees = 0; | |
307 | return NULL; | |
308 | } | |
309 | ||
727a31fa RH |
310 | /* Only need to mark VAR_DECLS; parameters and return results are not |
311 | eliminated as unused. */ | |
312 | if (TREE_CODE (t) == VAR_DECL) | |
313 | set_is_used (t); | |
314 | ||
6615c446 | 315 | if (IS_TYPE_OR_DECL_P (t)) |
727a31fa RH |
316 | *walk_subtrees = 0; |
317 | ||
318 | return NULL; | |
319 | } | |
320 | ||
321 | /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be | |
322 | eliminated during the tree->rtl conversion process. */ | |
323 | ||
324 | static inline void | |
325 | mark_all_vars_used (tree *expr_p) | |
326 | { | |
327 | walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL); | |
328 | } | |
329 | ||
6de9cd9a DN |
330 | /* This function looks through the program and uses FLAGS to determine what |
331 | SSA versioned variables are given entries in a new partition table. This | |
332 | new partition map is returned. */ | |
333 | ||
334 | var_map | |
335 | create_ssa_var_map (int flags) | |
336 | { | |
337 | block_stmt_iterator bsi; | |
338 | basic_block bb; | |
d00ad49b | 339 | tree dest, use; |
6de9cd9a | 340 | tree stmt; |
6de9cd9a | 341 | var_map map; |
4c124b4c | 342 | ssa_op_iter iter; |
312bc278 | 343 | #ifdef ENABLE_CHECKING |
a3648cfc DB |
344 | bitmap used_in_real_ops; |
345 | bitmap used_in_virtual_ops; | |
6de9cd9a DN |
346 | #endif |
347 | ||
95a3742c | 348 | map = init_var_map (num_ssa_names + 1); |
6de9cd9a | 349 | |
312bc278 | 350 | #ifdef ENABLE_CHECKING |
a3648cfc DB |
351 | used_in_real_ops = BITMAP_ALLOC (NULL); |
352 | used_in_virtual_ops = BITMAP_ALLOC (NULL); | |
6de9cd9a DN |
353 | #endif |
354 | ||
355 | if (flags & SSA_VAR_MAP_REF_COUNT) | |
356 | { | |
357 | map->ref_count | |
95a3742c DN |
358 | = (int *)xmalloc (((num_ssa_names + 1) * sizeof (int))); |
359 | memset (map->ref_count, 0, (num_ssa_names + 1) * sizeof (int)); | |
6de9cd9a DN |
360 | } |
361 | ||
362 | FOR_EACH_BB (bb) | |
363 | { | |
364 | tree phi, arg; | |
17192884 | 365 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
6de9cd9a DN |
366 | { |
367 | int i; | |
368 | register_ssa_partition (map, PHI_RESULT (phi), false); | |
369 | for (i = 0; i < PHI_NUM_ARGS (phi); i++) | |
370 | { | |
371 | arg = PHI_ARG_DEF (phi, i); | |
372 | if (TREE_CODE (arg) == SSA_NAME) | |
373 | register_ssa_partition (map, arg, true); | |
727a31fa RH |
374 | |
375 | mark_all_vars_used (&PHI_ARG_DEF_TREE (phi, i)); | |
6de9cd9a DN |
376 | } |
377 | } | |
378 | ||
379 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
380 | { | |
381 | stmt = bsi_stmt (bsi); | |
6de9cd9a DN |
382 | |
383 | /* Register USE and DEF operands in each statement. */ | |
4c124b4c | 384 | FOR_EACH_SSA_TREE_OPERAND (use , stmt, iter, SSA_OP_USE) |
6de9cd9a | 385 | { |
d00ad49b | 386 | register_ssa_partition (map, use, true); |
6de9cd9a | 387 | |
312bc278 | 388 | #ifdef ENABLE_CHECKING |
a3648cfc | 389 | bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (use))); |
6de9cd9a DN |
390 | #endif |
391 | } | |
392 | ||
4c124b4c | 393 | FOR_EACH_SSA_TREE_OPERAND (dest, stmt, iter, SSA_OP_DEF) |
6de9cd9a | 394 | { |
d00ad49b | 395 | register_ssa_partition (map, dest, false); |
6de9cd9a | 396 | |
312bc278 | 397 | #ifdef ENABLE_CHECKING |
a3648cfc | 398 | bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (dest))); |
6de9cd9a DN |
399 | #endif |
400 | } | |
401 | ||
312bc278 RH |
402 | #ifdef ENABLE_CHECKING |
403 | /* Validate that virtual ops don't get used in funny ways. */ | |
4c124b4c AM |
404 | FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, |
405 | SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF) | |
6de9cd9a | 406 | { |
a3648cfc DB |
407 | bitmap_set_bit (used_in_virtual_ops, |
408 | DECL_UID (SSA_NAME_VAR (use))); | |
6de9cd9a DN |
409 | } |
410 | ||
312bc278 | 411 | #endif /* ENABLE_CHECKING */ |
727a31fa RH |
412 | |
413 | mark_all_vars_used (bsi_stmt_ptr (bsi)); | |
6de9cd9a DN |
414 | } |
415 | } | |
416 | ||
417 | #if defined ENABLE_CHECKING | |
418 | { | |
419 | unsigned i; | |
a3648cfc DB |
420 | bitmap both = BITMAP_ALLOC (NULL); |
421 | bitmap_and (both, used_in_real_ops, used_in_virtual_ops); | |
422 | if (!bitmap_empty_p (both)) | |
6de9cd9a | 423 | { |
a3648cfc | 424 | bitmap_iterator bi; |
b6e7e9af | 425 | |
a3648cfc | 426 | EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi) |
6de9cd9a | 427 | fprintf (stderr, "Variable %s used in real and virtual operands\n", |
b6e7e9af | 428 | get_name (referenced_var (i))); |
1e128c5f | 429 | internal_error ("SSA corruption"); |
6de9cd9a DN |
430 | } |
431 | ||
a3648cfc DB |
432 | BITMAP_FREE (used_in_real_ops); |
433 | BITMAP_FREE (used_in_virtual_ops); | |
434 | BITMAP_FREE (both); | |
6de9cd9a DN |
435 | } |
436 | #endif | |
437 | ||
438 | return map; | |
439 | } | |
440 | ||
441 | ||
442 | /* Allocate and return a new live range information object base on MAP. */ | |
443 | ||
444 | static tree_live_info_p | |
445 | new_tree_live_info (var_map map) | |
446 | { | |
447 | tree_live_info_p live; | |
3cd8c58a | 448 | unsigned x; |
6de9cd9a DN |
449 | |
450 | live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d)); | |
451 | live->map = map; | |
452 | live->num_blocks = last_basic_block; | |
453 | ||
8bdbfff5 | 454 | live->global = BITMAP_ALLOC (NULL); |
6de9cd9a DN |
455 | |
456 | live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap)); | |
457 | for (x = 0; x < num_var_partitions (map); x++) | |
8bdbfff5 | 458 | live->livein[x] = BITMAP_ALLOC (NULL); |
6de9cd9a DN |
459 | |
460 | /* liveout is deferred until it is actually requested. */ | |
461 | live->liveout = NULL; | |
462 | return live; | |
463 | } | |
464 | ||
465 | ||
466 | /* Free storage for live range info object LIVE. */ | |
467 | ||
468 | void | |
469 | delete_tree_live_info (tree_live_info_p live) | |
470 | { | |
471 | int x; | |
472 | if (live->liveout) | |
473 | { | |
474 | for (x = live->num_blocks - 1; x >= 0; x--) | |
8bdbfff5 | 475 | BITMAP_FREE (live->liveout[x]); |
6de9cd9a DN |
476 | free (live->liveout); |
477 | } | |
478 | if (live->livein) | |
479 | { | |
480 | for (x = num_var_partitions (live->map) - 1; x >= 0; x--) | |
8bdbfff5 | 481 | BITMAP_FREE (live->livein[x]); |
6de9cd9a DN |
482 | free (live->livein); |
483 | } | |
484 | if (live->global) | |
8bdbfff5 | 485 | BITMAP_FREE (live->global); |
6de9cd9a DN |
486 | |
487 | free (live); | |
488 | } | |
489 | ||
490 | ||
491 | /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses | |
492 | for partition I. STACK is a varray used for temporary memory which is | |
493 | passed in rather than being allocated on every call. */ | |
494 | ||
495 | static void | |
d0b06ef9 | 496 | live_worklist (tree_live_info_p live, int *stack, int i) |
6de9cd9a | 497 | { |
3cd8c58a | 498 | unsigned b; |
6de9cd9a DN |
499 | tree var; |
500 | basic_block def_bb = NULL; | |
501 | edge e; | |
502 | var_map map = live->map; | |
628f6a4e | 503 | edge_iterator ei; |
87c476a2 | 504 | bitmap_iterator bi; |
d0b06ef9 | 505 | int *tos = stack; |
6de9cd9a DN |
506 | |
507 | var = partition_to_var (map, i); | |
508 | if (SSA_NAME_DEF_STMT (var)) | |
509 | def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var)); | |
510 | ||
87c476a2 | 511 | EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, bi) |
6de9cd9a | 512 | { |
d0b06ef9 | 513 | *tos++ = b; |
87c476a2 | 514 | } |
6de9cd9a | 515 | |
d0b06ef9 | 516 | while (tos != stack) |
6de9cd9a | 517 | { |
d0b06ef9 | 518 | b = *--tos; |
6de9cd9a | 519 | |
628f6a4e BE |
520 | FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds) |
521 | if (e->src != ENTRY_BLOCK_PTR) | |
6de9cd9a DN |
522 | { |
523 | /* Its not live on entry to the block its defined in. */ | |
524 | if (e->src == def_bb) | |
525 | continue; | |
526 | if (!bitmap_bit_p (live->livein[i], e->src->index)) | |
527 | { | |
628f6a4e | 528 | bitmap_set_bit (live->livein[i], e->src->index); |
d0b06ef9 | 529 | *tos++ = e->src->index; |
6de9cd9a DN |
530 | } |
531 | } | |
532 | } | |
533 | } | |
534 | ||
535 | ||
536 | /* If VAR is in a partition of MAP, set the bit for that partition in VEC. */ | |
537 | ||
538 | static inline void | |
539 | set_if_valid (var_map map, bitmap vec, tree var) | |
540 | { | |
541 | int p = var_to_partition (map, var); | |
542 | if (p != NO_PARTITION) | |
543 | bitmap_set_bit (vec, p); | |
544 | } | |
545 | ||
546 | ||
547 | /* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and | |
548 | global bit for it in the LIVE object. BB is the block being processed. */ | |
549 | ||
550 | static inline void | |
551 | add_livein_if_notdef (tree_live_info_p live, bitmap def_vec, | |
552 | tree var, basic_block bb) | |
553 | { | |
554 | int p = var_to_partition (live->map, var); | |
555 | if (p == NO_PARTITION || bb == ENTRY_BLOCK_PTR) | |
556 | return; | |
557 | if (!bitmap_bit_p (def_vec, p)) | |
558 | { | |
559 | bitmap_set_bit (live->livein[p], bb->index); | |
560 | bitmap_set_bit (live->global, p); | |
561 | } | |
562 | } | |
563 | ||
564 | ||
565 | /* Given partition map MAP, calculate all the live on entry bitmaps for | |
566 | each basic block. Return a live info object. */ | |
567 | ||
568 | tree_live_info_p | |
569 | calculate_live_on_entry (var_map map) | |
570 | { | |
571 | tree_live_info_p live; | |
3cd8c58a | 572 | unsigned i; |
6de9cd9a DN |
573 | basic_block bb; |
574 | bitmap saw_def; | |
575 | tree phi, var, stmt; | |
02ea8d06 | 576 | tree op; |
6de9cd9a | 577 | edge e; |
d0b06ef9 | 578 | int *stack; |
6de9cd9a | 579 | block_stmt_iterator bsi; |
4c124b4c | 580 | ssa_op_iter iter; |
87c476a2 | 581 | bitmap_iterator bi; |
4c124b4c AM |
582 | #ifdef ENABLE_CHECKING |
583 | int num; | |
628f6a4e | 584 | edge_iterator ei; |
c3b8e9aa | 585 | #endif |
6de9cd9a | 586 | |
8bdbfff5 | 587 | saw_def = BITMAP_ALLOC (NULL); |
6de9cd9a DN |
588 | |
589 | live = new_tree_live_info (map); | |
590 | ||
591 | FOR_EACH_BB (bb) | |
592 | { | |
593 | bitmap_clear (saw_def); | |
594 | ||
17192884 | 595 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
6de9cd9a | 596 | { |
3cd8c58a | 597 | for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++) |
6de9cd9a DN |
598 | { |
599 | var = PHI_ARG_DEF (phi, i); | |
600 | if (!phi_ssa_name_p (var)) | |
601 | continue; | |
602 | stmt = SSA_NAME_DEF_STMT (var); | |
62112e35 | 603 | e = EDGE_PRED (bb, i); |
6de9cd9a DN |
604 | |
605 | /* Any uses in PHIs which either don't have def's or are not | |
606 | defined in the block from which the def comes, will be live | |
607 | on entry to that block. */ | |
608 | if (!stmt || e->src != bb_for_stmt (stmt)) | |
609 | add_livein_if_notdef (live, saw_def, var, e->src); | |
610 | } | |
611 | } | |
612 | ||
613 | /* Don't mark PHI results as defined until all the PHI nodes have | |
614 | been processed. If the PHI sequence is: | |
615 | a_3 = PHI <a_1, a_2> | |
616 | b_3 = PHI <b_1, a_3> | |
617 | The a_3 referred to in b_3's PHI node is the one incoming on the | |
618 | edge, *not* the PHI node just seen. */ | |
619 | ||
17192884 | 620 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
6de9cd9a DN |
621 | { |
622 | var = PHI_RESULT (phi); | |
623 | set_if_valid (map, saw_def, var); | |
624 | } | |
625 | ||
626 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
627 | { | |
628 | stmt = bsi_stmt (bsi); | |
6de9cd9a | 629 | |
4c124b4c | 630 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE) |
6de9cd9a | 631 | { |
02ea8d06 | 632 | add_livein_if_notdef (live, saw_def, op, bb); |
6de9cd9a DN |
633 | } |
634 | ||
4c124b4c | 635 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF) |
6de9cd9a | 636 | { |
02ea8d06 | 637 | set_if_valid (map, saw_def, op); |
6de9cd9a DN |
638 | } |
639 | } | |
640 | } | |
641 | ||
e1111e8e | 642 | stack = XNEWVEC (int, last_basic_block); |
87c476a2 | 643 | EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi) |
6de9cd9a DN |
644 | { |
645 | live_worklist (live, stack, i); | |
87c476a2 | 646 | } |
d0b06ef9 | 647 | free (stack); |
6de9cd9a DN |
648 | |
649 | #ifdef ENABLE_CHECKING | |
650 | /* Check for live on entry partitions and report those with a DEF in | |
651 | the program. This will typically mean an optimization has done | |
652 | something wrong. */ | |
653 | ||
654 | bb = ENTRY_BLOCK_PTR; | |
655 | num = 0; | |
628f6a4e | 656 | FOR_EACH_EDGE (e, ei, bb->succs) |
6de9cd9a DN |
657 | { |
658 | int entry_block = e->dest->index; | |
659 | if (e->dest == EXIT_BLOCK_PTR) | |
660 | continue; | |
3cd8c58a | 661 | for (i = 0; i < (unsigned)num_var_partitions (map); i++) |
6de9cd9a DN |
662 | { |
663 | basic_block tmp; | |
664 | tree d; | |
665 | var = partition_to_var (map, i); | |
666 | stmt = SSA_NAME_DEF_STMT (var); | |
667 | tmp = bb_for_stmt (stmt); | |
668 | d = default_def (SSA_NAME_VAR (var)); | |
669 | ||
670 | if (bitmap_bit_p (live_entry_blocks (live, i), entry_block)) | |
671 | { | |
672 | if (!IS_EMPTY_STMT (stmt)) | |
673 | { | |
674 | num++; | |
675 | print_generic_expr (stderr, var, TDF_SLIM); | |
676 | fprintf (stderr, " is defined "); | |
677 | if (tmp) | |
678 | fprintf (stderr, " in BB%d, ", tmp->index); | |
679 | fprintf (stderr, "by:\n"); | |
680 | print_generic_expr (stderr, stmt, TDF_SLIM); | |
681 | fprintf (stderr, "\nIt is also live-on-entry to entry BB %d", | |
682 | entry_block); | |
683 | fprintf (stderr, " So it appears to have multiple defs.\n"); | |
684 | } | |
685 | else | |
686 | { | |
687 | if (d != var) | |
688 | { | |
689 | num++; | |
690 | print_generic_expr (stderr, var, TDF_SLIM); | |
691 | fprintf (stderr, " is live-on-entry to BB%d ",entry_block); | |
692 | if (d) | |
693 | { | |
694 | fprintf (stderr, " but is not the default def of "); | |
695 | print_generic_expr (stderr, d, TDF_SLIM); | |
696 | fprintf (stderr, "\n"); | |
697 | } | |
698 | else | |
699 | fprintf (stderr, " and there is no default def.\n"); | |
700 | } | |
701 | } | |
702 | } | |
703 | else | |
704 | if (d == var) | |
705 | { | |
706 | /* The only way this var shouldn't be marked live on entry is | |
707 | if it occurs in a PHI argument of the block. */ | |
708 | int z, ok = 0; | |
709 | for (phi = phi_nodes (e->dest); | |
710 | phi && !ok; | |
17192884 | 711 | phi = PHI_CHAIN (phi)) |
6de9cd9a DN |
712 | { |
713 | for (z = 0; z < PHI_NUM_ARGS (phi); z++) | |
714 | if (var == PHI_ARG_DEF (phi, z)) | |
715 | { | |
716 | ok = 1; | |
717 | break; | |
718 | } | |
719 | } | |
720 | if (ok) | |
721 | continue; | |
722 | num++; | |
723 | print_generic_expr (stderr, var, TDF_SLIM); | |
724 | fprintf (stderr, " is not marked live-on-entry to entry BB%d ", | |
725 | entry_block); | |
726 | fprintf (stderr, "but it is a default def so it should be.\n"); | |
727 | } | |
728 | } | |
729 | } | |
1e128c5f | 730 | gcc_assert (num <= 0); |
6de9cd9a DN |
731 | #endif |
732 | ||
8bdbfff5 | 733 | BITMAP_FREE (saw_def); |
623f4556 | 734 | |
6de9cd9a DN |
735 | return live; |
736 | } | |
737 | ||
738 | ||
739 | /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */ | |
740 | ||
741 | void | |
742 | calculate_live_on_exit (tree_live_info_p liveinfo) | |
743 | { | |
744 | unsigned b; | |
3cd8c58a | 745 | unsigned i, x; |
6de9cd9a DN |
746 | bitmap *on_exit; |
747 | basic_block bb; | |
748 | edge e; | |
749 | tree t, phi; | |
750 | bitmap on_entry; | |
751 | var_map map = liveinfo->map; | |
752 | ||
753 | on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap)); | |
3cd8c58a | 754 | for (x = 0; x < (unsigned)last_basic_block; x++) |
8bdbfff5 | 755 | on_exit[x] = BITMAP_ALLOC (NULL); |
6de9cd9a DN |
756 | |
757 | /* Set all the live-on-exit bits for uses in PHIs. */ | |
758 | FOR_EACH_BB (bb) | |
759 | { | |
17192884 | 760 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
3cd8c58a | 761 | for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++) |
6de9cd9a DN |
762 | { |
763 | t = PHI_ARG_DEF (phi, i); | |
764 | e = PHI_ARG_EDGE (phi, i); | |
765 | if (!phi_ssa_name_p (t) || e->src == ENTRY_BLOCK_PTR) | |
766 | continue; | |
767 | set_if_valid (map, on_exit[e->src->index], t); | |
768 | } | |
769 | } | |
770 | ||
771 | /* Set live on exit for all predecessors of live on entry's. */ | |
772 | for (i = 0; i < num_var_partitions (map); i++) | |
773 | { | |
87c476a2 ZD |
774 | bitmap_iterator bi; |
775 | ||
6de9cd9a | 776 | on_entry = live_entry_blocks (liveinfo, i); |
87c476a2 | 777 | EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi) |
6de9cd9a | 778 | { |
628f6a4e BE |
779 | edge_iterator ei; |
780 | FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds) | |
6de9cd9a DN |
781 | if (e->src != ENTRY_BLOCK_PTR) |
782 | bitmap_set_bit (on_exit[e->src->index], i); | |
87c476a2 | 783 | } |
6de9cd9a DN |
784 | } |
785 | ||
786 | liveinfo->liveout = on_exit; | |
787 | } | |
788 | ||
789 | ||
790 | /* Initialize a tree_partition_associator object using MAP. */ | |
791 | ||
1d9d8683 | 792 | static tpa_p |
6de9cd9a DN |
793 | tpa_init (var_map map) |
794 | { | |
795 | tpa_p tpa; | |
796 | int num_partitions = num_var_partitions (map); | |
797 | int x; | |
798 | ||
799 | if (num_partitions == 0) | |
800 | return NULL; | |
801 | ||
802 | tpa = (tpa_p) xmalloc (sizeof (struct tree_partition_associator_d)); | |
803 | tpa->num_trees = 0; | |
804 | tpa->uncompressed_num = -1; | |
805 | tpa->map = map; | |
806 | tpa->next_partition = (int *)xmalloc (num_partitions * sizeof (int)); | |
807 | memset (tpa->next_partition, TPA_NONE, num_partitions * sizeof (int)); | |
808 | ||
809 | tpa->partition_to_tree_map = (int *)xmalloc (num_partitions * sizeof (int)); | |
810 | memset (tpa->partition_to_tree_map, TPA_NONE, num_partitions * sizeof (int)); | |
811 | ||
812 | x = MAX (40, (num_partitions / 20)); | |
7af893cb | 813 | tpa->trees = VEC_alloc (tree, heap, x); |
6de9cd9a DN |
814 | VARRAY_INT_INIT (tpa->first_partition, x, "first_partition"); |
815 | ||
816 | return tpa; | |
817 | ||
818 | } | |
819 | ||
820 | ||
821 | /* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA. */ | |
822 | ||
823 | void | |
824 | tpa_remove_partition (tpa_p tpa, int tree_index, int partition_index) | |
825 | { | |
826 | int i; | |
827 | ||
828 | i = tpa_first_partition (tpa, tree_index); | |
829 | if (i == partition_index) | |
830 | { | |
831 | VARRAY_INT (tpa->first_partition, tree_index) = tpa->next_partition[i]; | |
832 | } | |
833 | else | |
834 | { | |
835 | for ( ; i != TPA_NONE; i = tpa_next_partition (tpa, i)) | |
836 | { | |
837 | if (tpa->next_partition[i] == partition_index) | |
838 | { | |
839 | tpa->next_partition[i] = tpa->next_partition[partition_index]; | |
840 | break; | |
841 | } | |
842 | } | |
843 | } | |
844 | } | |
845 | ||
846 | ||
847 | /* Free the memory used by tree_partition_associator object TPA. */ | |
848 | ||
849 | void | |
850 | tpa_delete (tpa_p tpa) | |
851 | { | |
852 | if (!tpa) | |
853 | return; | |
854 | ||
7af893cb | 855 | VEC_free (tree, heap, tpa->trees); |
6de9cd9a DN |
856 | free (tpa->partition_to_tree_map); |
857 | free (tpa->next_partition); | |
858 | free (tpa); | |
859 | } | |
860 | ||
861 | ||
1ea7e6ad | 862 | /* This function will remove any tree entries from TPA which have only a single |
6de9cd9a DN |
863 | element. This will help keep the size of the conflict graph down. The |
864 | function returns the number of remaining tree lists. */ | |
865 | ||
866 | int | |
867 | tpa_compact (tpa_p tpa) | |
868 | { | |
869 | int last, x, y, first, swap_i; | |
870 | tree swap_t; | |
871 | ||
872 | /* Find the last list which has more than 1 partition. */ | |
873 | for (last = tpa->num_trees - 1; last > 0; last--) | |
874 | { | |
875 | first = tpa_first_partition (tpa, last); | |
876 | if (tpa_next_partition (tpa, first) != NO_PARTITION) | |
877 | break; | |
878 | } | |
879 | ||
880 | x = 0; | |
881 | while (x < last) | |
882 | { | |
883 | first = tpa_first_partition (tpa, x); | |
884 | ||
885 | /* If there is not more than one partition, swap with the current end | |
886 | of the tree list. */ | |
887 | if (tpa_next_partition (tpa, first) == NO_PARTITION) | |
888 | { | |
7af893cb | 889 | swap_t = VEC_index (tree, tpa->trees, last); |
6de9cd9a DN |
890 | swap_i = VARRAY_INT (tpa->first_partition, last); |
891 | ||
892 | /* Update the last entry. Since it is known to only have one | |
893 | partition, there is nothing else to update. */ | |
7af893cb KH |
894 | VEC_replace (tree, tpa->trees, last, |
895 | VEC_index (tree, tpa->trees, x)); | |
6de9cd9a DN |
896 | VARRAY_INT (tpa->first_partition, last) |
897 | = VARRAY_INT (tpa->first_partition, x); | |
898 | tpa->partition_to_tree_map[tpa_first_partition (tpa, last)] = last; | |
899 | ||
900 | /* Since this list is known to have more than one partition, update | |
901 | the list owner entries. */ | |
7af893cb | 902 | VEC_replace (tree, tpa->trees, x, swap_t); |
6de9cd9a DN |
903 | VARRAY_INT (tpa->first_partition, x) = swap_i; |
904 | for (y = tpa_first_partition (tpa, x); | |
905 | y != NO_PARTITION; | |
906 | y = tpa_next_partition (tpa, y)) | |
907 | tpa->partition_to_tree_map[y] = x; | |
908 | ||
909 | /* Ensure last is a list with more than one partition. */ | |
910 | last--; | |
911 | for (; last > x; last--) | |
912 | { | |
913 | first = tpa_first_partition (tpa, last); | |
914 | if (tpa_next_partition (tpa, first) != NO_PARTITION) | |
915 | break; | |
916 | } | |
917 | } | |
918 | x++; | |
919 | } | |
920 | ||
921 | first = tpa_first_partition (tpa, x); | |
922 | if (tpa_next_partition (tpa, first) != NO_PARTITION) | |
923 | x++; | |
924 | tpa->uncompressed_num = tpa->num_trees; | |
925 | tpa->num_trees = x; | |
926 | return last; | |
927 | } | |
928 | ||
929 | ||
930 | /* Initialize a root_var object with SSA partitions from MAP which are based | |
931 | on each root variable. */ | |
932 | ||
933 | root_var_p | |
934 | root_var_init (var_map map) | |
935 | { | |
936 | root_var_p rv; | |
937 | int num_partitions = num_var_partitions (map); | |
938 | int x, p; | |
939 | tree t; | |
940 | var_ann_t ann; | |
941 | sbitmap seen; | |
942 | ||
943 | rv = tpa_init (map); | |
944 | if (!rv) | |
945 | return NULL; | |
946 | ||
947 | seen = sbitmap_alloc (num_partitions); | |
948 | sbitmap_zero (seen); | |
949 | ||
950 | /* Start at the end and work towards the front. This will provide a list | |
951 | that is ordered from smallest to largest. */ | |
952 | for (x = num_partitions - 1; x >= 0; x--) | |
953 | { | |
954 | t = partition_to_var (map, x); | |
955 | ||
956 | /* The var map may not be compacted yet, so check for NULL. */ | |
957 | if (!t) | |
958 | continue; | |
959 | ||
960 | p = var_to_partition (map, t); | |
961 | ||
1e128c5f | 962 | gcc_assert (p != NO_PARTITION); |
6de9cd9a DN |
963 | |
964 | /* Make sure we only put coalesced partitions into the list once. */ | |
965 | if (TEST_BIT (seen, p)) | |
966 | continue; | |
967 | SET_BIT (seen, p); | |
968 | if (TREE_CODE (t) == SSA_NAME) | |
969 | t = SSA_NAME_VAR (t); | |
970 | ann = var_ann (t); | |
971 | if (ann->root_var_processed) | |
972 | { | |
973 | rv->next_partition[p] = VARRAY_INT (rv->first_partition, | |
974 | VAR_ANN_ROOT_INDEX (ann)); | |
975 | VARRAY_INT (rv->first_partition, VAR_ANN_ROOT_INDEX (ann)) = p; | |
976 | } | |
977 | else | |
978 | { | |
979 | ann->root_var_processed = 1; | |
980 | VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++; | |
7af893cb | 981 | VEC_safe_push (tree, heap, rv->trees, t); |
6de9cd9a DN |
982 | VARRAY_PUSH_INT (rv->first_partition, p); |
983 | } | |
984 | rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann); | |
985 | } | |
986 | ||
987 | /* Reset the out_of_ssa_tag flag on each variable for later use. */ | |
988 | for (x = 0; x < rv->num_trees; x++) | |
989 | { | |
7af893cb | 990 | t = VEC_index (tree, rv->trees, x); |
6de9cd9a DN |
991 | var_ann (t)->root_var_processed = 0; |
992 | } | |
993 | ||
994 | sbitmap_free (seen); | |
995 | return rv; | |
996 | } | |
997 | ||
998 | ||
999 | /* Initialize a type_var structure which associates all the partitions in MAP | |
1000 | of the same type to the type node's index. Volatiles are ignored. */ | |
1001 | ||
1002 | type_var_p | |
1003 | type_var_init (var_map map) | |
1004 | { | |
1005 | type_var_p tv; | |
1006 | int x, y, p; | |
1007 | int num_partitions = num_var_partitions (map); | |
1008 | tree t; | |
1009 | sbitmap seen; | |
1010 | ||
1011 | seen = sbitmap_alloc (num_partitions); | |
1012 | sbitmap_zero (seen); | |
1013 | ||
1014 | tv = tpa_init (map); | |
1015 | if (!tv) | |
1016 | return NULL; | |
1017 | ||
1018 | for (x = num_partitions - 1; x >= 0; x--) | |
1019 | { | |
1020 | t = partition_to_var (map, x); | |
1021 | ||
1022 | /* Disallow coalescing of these types of variables. */ | |
1023 | if (!t | |
1024 | || TREE_THIS_VOLATILE (t) | |
1025 | || TREE_CODE (t) == RESULT_DECL | |
1026 | || TREE_CODE (t) == PARM_DECL | |
1027 | || (DECL_P (t) | |
1028 | && (DECL_REGISTER (t) | |
17ad5b5e | 1029 | || !DECL_IGNORED_P (t) |
6de9cd9a DN |
1030 | || DECL_RTL_SET_P (t)))) |
1031 | continue; | |
1032 | ||
1033 | p = var_to_partition (map, t); | |
1034 | ||
1e128c5f | 1035 | gcc_assert (p != NO_PARTITION); |
6de9cd9a DN |
1036 | |
1037 | /* If partitions have been coalesced, only add the representative | |
1038 | for the partition to the list once. */ | |
1039 | if (TEST_BIT (seen, p)) | |
1040 | continue; | |
1041 | SET_BIT (seen, p); | |
1042 | t = TREE_TYPE (t); | |
1043 | ||
1044 | /* Find the list for this type. */ | |
1045 | for (y = 0; y < tv->num_trees; y++) | |
7af893cb | 1046 | if (t == VEC_index (tree, tv->trees, y)) |
6de9cd9a DN |
1047 | break; |
1048 | if (y == tv->num_trees) | |
1049 | { | |
1050 | tv->num_trees++; | |
7af893cb | 1051 | VEC_safe_push (tree, heap, tv->trees, t); |
6de9cd9a DN |
1052 | VARRAY_PUSH_INT (tv->first_partition, p); |
1053 | } | |
1054 | else | |
1055 | { | |
1056 | tv->next_partition[p] = VARRAY_INT (tv->first_partition, y); | |
1057 | VARRAY_INT (tv->first_partition, y) = p; | |
1058 | } | |
1059 | tv->partition_to_tree_map[p] = y; | |
1060 | } | |
1061 | sbitmap_free (seen); | |
1062 | return tv; | |
1063 | } | |
1064 | ||
1065 | ||
1066 | /* Create a new coalesce list object from MAP and return it. */ | |
1067 | ||
1068 | coalesce_list_p | |
1069 | create_coalesce_list (var_map map) | |
1070 | { | |
1071 | coalesce_list_p list; | |
1072 | ||
1073 | list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d)); | |
1074 | ||
1075 | list->map = map; | |
1076 | list->add_mode = true; | |
1077 | list->list = (partition_pair_p *) xcalloc (num_var_partitions (map), | |
1078 | sizeof (struct partition_pair_d)); | |
1079 | return list; | |
1080 | } | |
1081 | ||
1082 | ||
1083 | /* Delete coalesce list CL. */ | |
1084 | ||
1085 | void | |
1086 | delete_coalesce_list (coalesce_list_p cl) | |
1087 | { | |
1088 | free (cl->list); | |
1089 | free (cl); | |
1090 | } | |
1091 | ||
1092 | ||
1093 | /* Find a matching coalesce pair object in CL for partitions P1 and P2. If | |
1094 | one isn't found, return NULL if CREATE is false, otherwise create a new | |
1095 | coalesce pair object and return it. */ | |
1096 | ||
1097 | static partition_pair_p | |
1098 | find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create) | |
1099 | { | |
1100 | partition_pair_p node, tmp; | |
1101 | int s; | |
1102 | ||
1103 | /* Normalize so that p1 is the smaller value. */ | |
1104 | if (p2 < p1) | |
1105 | { | |
1106 | s = p1; | |
1107 | p1 = p2; | |
1108 | p2 = s; | |
1109 | } | |
1110 | ||
1111 | tmp = NULL; | |
1112 | ||
1113 | /* The list is sorted such that if we find a value greater than p2, | |
1114 | p2 is not in the list. */ | |
1115 | for (node = cl->list[p1]; node; node = node->next) | |
1116 | { | |
1117 | if (node->second_partition == p2) | |
1118 | return node; | |
1119 | else | |
1120 | if (node->second_partition > p2) | |
1121 | break; | |
1122 | tmp = node; | |
1123 | } | |
1124 | ||
1125 | if (!create) | |
1126 | return NULL; | |
1127 | ||
1128 | node = (partition_pair_p) xmalloc (sizeof (struct partition_pair_d)); | |
1129 | node->first_partition = p1; | |
1130 | node->second_partition = p2; | |
1131 | node->cost = 0; | |
1132 | ||
1133 | if (tmp != NULL) | |
1134 | { | |
1135 | node->next = tmp->next; | |
1136 | tmp->next = node; | |
1137 | } | |
1138 | else | |
1139 | { | |
1140 | /* This is now the first node in the list. */ | |
1141 | node->next = cl->list[p1]; | |
1142 | cl->list[p1] = node; | |
1143 | } | |
1144 | ||
1145 | return node; | |
1146 | } | |
1147 | ||
0bde02b3 JH |
1148 | /* Return cost of execution of copy instruction with FREQUENCY |
1149 | possibly on CRITICAL edge and in HOT basic block. */ | |
1150 | int | |
1151 | coalesce_cost (int frequency, bool hot, bool critical) | |
1152 | { | |
1153 | /* Base costs on BB frequencies bounded by 1. */ | |
1154 | int cost = frequency; | |
1155 | ||
1156 | if (!cost) | |
1157 | cost = 1; | |
1158 | if (optimize_size || hot) | |
1159 | cost = 1; | |
1160 | /* Inserting copy on critical edge costs more | |
1161 | than inserting it elsewhere. */ | |
1162 | if (critical) | |
1163 | cost *= 2; | |
1164 | return cost; | |
1165 | } | |
6de9cd9a DN |
1166 | |
1167 | /* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE. */ | |
1168 | ||
1169 | void | |
0bde02b3 JH |
1170 | add_coalesce (coalesce_list_p cl, int p1, int p2, |
1171 | int value) | |
6de9cd9a DN |
1172 | { |
1173 | partition_pair_p node; | |
1174 | ||
1e128c5f | 1175 | gcc_assert (cl->add_mode); |
6de9cd9a DN |
1176 | |
1177 | if (p1 == p2) | |
1178 | return; | |
1179 | ||
1180 | node = find_partition_pair (cl, p1, p2, true); | |
1181 | ||
1182 | node->cost += value; | |
1183 | } | |
1184 | ||
1185 | ||
1186 | /* Comparison function to allow qsort to sort P1 and P2 in descending order. */ | |
1187 | ||
1188 | static | |
1189 | int compare_pairs (const void *p1, const void *p2) | |
1190 | { | |
1191 | return (*(partition_pair_p *)p2)->cost - (*(partition_pair_p *)p1)->cost; | |
1192 | } | |
1193 | ||
1194 | ||
1195 | /* Prepare CL for removal of preferred pairs. When finished, list element | |
1196 | 0 has all the coalesce pairs, sorted in order from most important coalesce | |
1197 | to least important. */ | |
1198 | ||
1199 | void | |
1200 | sort_coalesce_list (coalesce_list_p cl) | |
1201 | { | |
3cd8c58a | 1202 | unsigned x, num, count; |
6de9cd9a DN |
1203 | partition_pair_p chain, p; |
1204 | partition_pair_p *list; | |
1205 | ||
1e128c5f | 1206 | gcc_assert (cl->add_mode); |
6de9cd9a DN |
1207 | |
1208 | cl->add_mode = false; | |
1209 | ||
1210 | /* Compact the array of lists to a single list, and count the elements. */ | |
1211 | num = 0; | |
1212 | chain = NULL; | |
1213 | for (x = 0; x < num_var_partitions (cl->map); x++) | |
1214 | if (cl->list[x] != NULL) | |
1215 | { | |
1216 | for (p = cl->list[x]; p->next != NULL; p = p->next) | |
1217 | num++; | |
1218 | num++; | |
1219 | p->next = chain; | |
1220 | chain = cl->list[x]; | |
1221 | cl->list[x] = NULL; | |
1222 | } | |
1223 | ||
1224 | /* Only call qsort if there are more than 2 items. */ | |
1225 | if (num > 2) | |
1226 | { | |
e1111e8e | 1227 | list = XNEWVEC (partition_pair_p, num); |
6de9cd9a DN |
1228 | count = 0; |
1229 | for (p = chain; p != NULL; p = p->next) | |
1230 | list[count++] = p; | |
1231 | ||
1e128c5f | 1232 | gcc_assert (count == num); |
6de9cd9a DN |
1233 | |
1234 | qsort (list, count, sizeof (partition_pair_p), compare_pairs); | |
1235 | ||
1236 | p = list[0]; | |
1237 | for (x = 1; x < num; x++) | |
1238 | { | |
1239 | p->next = list[x]; | |
1240 | p = list[x]; | |
1241 | } | |
1242 | p->next = NULL; | |
1243 | cl->list[0] = list[0]; | |
1244 | free (list); | |
1245 | } | |
1246 | else | |
1247 | { | |
1248 | cl->list[0] = chain; | |
1249 | if (num == 2) | |
1250 | { | |
1251 | /* Simply swap the two elements if they are in the wrong order. */ | |
1252 | if (chain->cost < chain->next->cost) | |
1253 | { | |
1254 | cl->list[0] = chain->next; | |
1255 | cl->list[0]->next = chain; | |
1256 | chain->next = NULL; | |
1257 | } | |
1258 | } | |
1259 | } | |
1260 | } | |
1261 | ||
1262 | ||
1263 | /* Retrieve the best remaining pair to coalesce from CL. Returns the 2 | |
1264 | partitions via P1 and P2. Their calculated cost is returned by the function. | |
1265 | NO_BEST_COALESCE is returned if the coalesce list is empty. */ | |
1266 | ||
1d9d8683 | 1267 | static int |
6de9cd9a DN |
1268 | pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2) |
1269 | { | |
1270 | partition_pair_p node; | |
1271 | int ret; | |
1272 | ||
1e128c5f | 1273 | gcc_assert (!cl->add_mode); |
6de9cd9a DN |
1274 | |
1275 | node = cl->list[0]; | |
1276 | if (!node) | |
1277 | return NO_BEST_COALESCE; | |
1278 | ||
1279 | cl->list[0] = node->next; | |
1280 | ||
1281 | *p1 = node->first_partition; | |
1282 | *p2 = node->second_partition; | |
1283 | ret = node->cost; | |
1284 | free (node); | |
1285 | ||
1286 | return ret; | |
1287 | } | |
1288 | ||
1289 | ||
1290 | /* If variable VAR is in a partition in MAP, add a conflict in GRAPH between | |
1291 | VAR and any other live partitions in VEC which are associated via TPA. | |
1292 | Reset the live bit in VEC. */ | |
1293 | ||
1294 | static inline void | |
1295 | add_conflicts_if_valid (tpa_p tpa, conflict_graph graph, | |
1296 | var_map map, bitmap vec, tree var) | |
1297 | { | |
1298 | int p, y, first; | |
1299 | p = var_to_partition (map, var); | |
1300 | if (p != NO_PARTITION) | |
1301 | { | |
1302 | bitmap_clear_bit (vec, p); | |
1303 | first = tpa_find_tree (tpa, p); | |
1304 | /* If find returns nothing, this object isn't interesting. */ | |
1305 | if (first == TPA_NONE) | |
1306 | return; | |
1307 | /* Only add interferences between objects in the same list. */ | |
1308 | for (y = tpa_first_partition (tpa, first); | |
1309 | y != TPA_NONE; | |
1310 | y = tpa_next_partition (tpa, y)) | |
1311 | { | |
1312 | if (bitmap_bit_p (vec, y)) | |
1313 | conflict_graph_add (graph, p, y); | |
1314 | } | |
1315 | } | |
1316 | } | |
1317 | ||
a0ef884f NS |
1318 | DEF_VEC_I(int); |
1319 | DEF_VEC_ALLOC_I(int,heap); | |
6de9cd9a DN |
1320 | |
1321 | /* Return a conflict graph for the information contained in LIVE_INFO. Only | |
1322 | conflicts between items in the same TPA list are added. If optional | |
1323 | coalesce list CL is passed in, any copies encountered are added. */ | |
1324 | ||
1325 | conflict_graph | |
1326 | build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa, | |
1327 | coalesce_list_p cl) | |
1328 | { | |
1329 | conflict_graph graph; | |
1330 | var_map map; | |
1331 | bitmap live; | |
3cd8c58a | 1332 | unsigned x, y, i; |
6de9cd9a | 1333 | basic_block bb; |
7df5a591 | 1334 | int *partition_link, *tpa_nodes; |
09a3016e | 1335 | VEC(int,heap) *tpa_to_clear; |
6de9cd9a | 1336 | unsigned l; |
4c124b4c | 1337 | ssa_op_iter iter; |
87c476a2 | 1338 | bitmap_iterator bi; |
6de9cd9a DN |
1339 | |
1340 | map = live_var_map (liveinfo); | |
1341 | graph = conflict_graph_new (num_var_partitions (map)); | |
1342 | ||
1343 | if (tpa_num_trees (tpa) == 0) | |
1344 | return graph; | |
1345 | ||
8bdbfff5 | 1346 | live = BITMAP_ALLOC (NULL); |
6de9cd9a | 1347 | |
e1111e8e GDR |
1348 | partition_link = XCNEWVEC (int, num_var_partitions (map) + 1); |
1349 | tpa_nodes = XCNEWVEC (int, tpa_num_trees (tpa)); | |
09a3016e | 1350 | tpa_to_clear = VEC_alloc (int, heap, 50); |
6de9cd9a DN |
1351 | |
1352 | FOR_EACH_BB (bb) | |
1353 | { | |
1354 | block_stmt_iterator bsi; | |
1355 | tree phi; | |
09a3016e | 1356 | int idx; |
6de9cd9a DN |
1357 | |
1358 | /* Start with live on exit temporaries. */ | |
1359 | bitmap_copy (live, live_on_exit (liveinfo, bb)); | |
1360 | ||
1361 | for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) | |
1362 | { | |
1363 | bool is_a_copy = false; | |
1364 | tree stmt = bsi_stmt (bsi); | |
6de9cd9a | 1365 | |
6de9cd9a DN |
1366 | /* A copy between 2 partitions does not introduce an interference |
1367 | by itself. If they did, you would never be able to coalesce | |
1368 | two things which are copied. If the two variables really do | |
1369 | conflict, they will conflict elsewhere in the program. | |
1370 | ||
1371 | This is handled specially here since we may also be interested | |
1372 | in copies between real variables and SSA_NAME variables. We may | |
1373 | be interested in trying to coalesce SSA_NAME variables with | |
9cf737f8 | 1374 | root variables in some cases. */ |
6de9cd9a DN |
1375 | |
1376 | if (TREE_CODE (stmt) == MODIFY_EXPR) | |
1377 | { | |
1378 | tree lhs = TREE_OPERAND (stmt, 0); | |
1379 | tree rhs = TREE_OPERAND (stmt, 1); | |
1380 | int p1, p2; | |
1381 | int bit; | |
1382 | ||
1383 | if (DECL_P (lhs) || TREE_CODE (lhs) == SSA_NAME) | |
1384 | p1 = var_to_partition (map, lhs); | |
1385 | else | |
1386 | p1 = NO_PARTITION; | |
1387 | ||
1388 | if (DECL_P (rhs) || TREE_CODE (rhs) == SSA_NAME) | |
1389 | p2 = var_to_partition (map, rhs); | |
1390 | else | |
1391 | p2 = NO_PARTITION; | |
1392 | ||
1393 | if (p1 != NO_PARTITION && p2 != NO_PARTITION) | |
1394 | { | |
1395 | is_a_copy = true; | |
1396 | bit = bitmap_bit_p (live, p2); | |
1397 | /* If the RHS is live, make it not live while we add | |
1398 | the conflicts, then make it live again. */ | |
1399 | if (bit) | |
1400 | bitmap_clear_bit (live, p2); | |
1401 | add_conflicts_if_valid (tpa, graph, map, live, lhs); | |
1402 | if (bit) | |
1403 | bitmap_set_bit (live, p2); | |
1404 | if (cl) | |
0bde02b3 JH |
1405 | add_coalesce (cl, p1, p2, |
1406 | coalesce_cost (bb->frequency, | |
1407 | maybe_hot_bb_p (bb), false)); | |
6de9cd9a DN |
1408 | set_if_valid (map, live, rhs); |
1409 | } | |
1410 | } | |
1411 | ||
1412 | if (!is_a_copy) | |
1413 | { | |
d00ad49b | 1414 | tree var; |
4c124b4c | 1415 | FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF) |
6de9cd9a | 1416 | { |
d00ad49b | 1417 | add_conflicts_if_valid (tpa, graph, map, live, var); |
6de9cd9a DN |
1418 | } |
1419 | ||
4c124b4c | 1420 | FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) |
6de9cd9a | 1421 | { |
d00ad49b | 1422 | set_if_valid (map, live, var); |
6de9cd9a DN |
1423 | } |
1424 | } | |
1425 | } | |
1426 | ||
1427 | /* If result of a PHI is unused, then the loops over the statements | |
1428 | will not record any conflicts. However, since the PHI node is | |
1429 | going to be translated out of SSA form we must record a conflict | |
1430 | between the result of the PHI and any variables with are live. | |
1431 | Otherwise the out-of-ssa translation may create incorrect code. */ | |
17192884 | 1432 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
6de9cd9a DN |
1433 | { |
1434 | tree result = PHI_RESULT (phi); | |
1435 | int p = var_to_partition (map, result); | |
1436 | ||
1437 | if (p != NO_PARTITION && ! bitmap_bit_p (live, p)) | |
1438 | add_conflicts_if_valid (tpa, graph, map, live, result); | |
1439 | } | |
1440 | ||
1441 | /* Anything which is still live at this point interferes. | |
1442 | In order to implement this efficiently, only conflicts between | |
1443 | partitions which have the same TPA root need be added. | |
1ea7e6ad | 1444 | TPA roots which have been seen are tracked in 'tpa_nodes'. A nonzero |
6de9cd9a DN |
1445 | entry points to an index into 'partition_link', which then indexes |
1446 | into itself forming a linked list of partitions sharing a tpa root | |
1447 | which have been seen as live up to this point. Since partitions start | |
1448 | at index zero, all entries in partition_link are (partition + 1). | |
1449 | ||
1450 | Conflicts are added between the current partition and any already seen. | |
1451 | tpa_clear contains all the tpa_roots processed, and these are the only | |
1452 | entries which need to be zero'd out for a clean restart. */ | |
1453 | ||
87c476a2 | 1454 | EXECUTE_IF_SET_IN_BITMAP (live, 0, x, bi) |
6de9cd9a DN |
1455 | { |
1456 | i = tpa_find_tree (tpa, x); | |
3cd8c58a | 1457 | if (i != (unsigned)TPA_NONE) |
6de9cd9a | 1458 | { |
7df5a591 | 1459 | int start = tpa_nodes[i]; |
6de9cd9a DN |
1460 | /* If start is 0, a new root reference list is being started. |
1461 | Register it to be cleared. */ | |
1462 | if (!start) | |
09a3016e | 1463 | VEC_safe_push (int, heap, tpa_to_clear, i); |
6de9cd9a DN |
1464 | |
1465 | /* Add interferences to other tpa members seen. */ | |
7df5a591 | 1466 | for (y = start; y != 0; y = partition_link[y]) |
6de9cd9a | 1467 | conflict_graph_add (graph, x, y - 1); |
7df5a591 KH |
1468 | tpa_nodes[i] = x + 1; |
1469 | partition_link[x + 1] = start; | |
6de9cd9a | 1470 | } |
87c476a2 | 1471 | } |
6de9cd9a DN |
1472 | |
1473 | /* Now clear the used tpa root references. */ | |
09a3016e KH |
1474 | for (l = 0; VEC_iterate (int, tpa_to_clear, l, idx); l++) |
1475 | tpa_nodes[idx] = 0; | |
1476 | VEC_truncate (int, tpa_to_clear, 0); | |
6de9cd9a DN |
1477 | } |
1478 | ||
7df5a591 KH |
1479 | free (tpa_nodes); |
1480 | free (partition_link); | |
09a3016e | 1481 | VEC_free (int, heap, tpa_to_clear); |
8bdbfff5 | 1482 | BITMAP_FREE (live); |
6de9cd9a DN |
1483 | return graph; |
1484 | } | |
1485 | ||
1486 | ||
1487 | /* This routine will attempt to coalesce the elements in TPA subject to the | |
1488 | conflicts found in GRAPH. If optional coalesce_list CL is provided, | |
1489 | only coalesces specified within the coalesce list are attempted. Otherwise | |
1490 | an attempt is made to coalesce as many partitions within each TPA grouping | |
1491 | as possible. If DEBUG is provided, debug output will be sent there. */ | |
1492 | ||
1493 | void | |
1494 | coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map, | |
1495 | coalesce_list_p cl, FILE *debug) | |
1496 | { | |
1497 | int x, y, z, w; | |
1498 | tree var, tmp; | |
1499 | ||
1500 | /* Attempt to coalesce any items in a coalesce list. */ | |
1501 | if (cl) | |
1502 | { | |
1503 | while (pop_best_coalesce (cl, &x, &y) != NO_BEST_COALESCE) | |
1504 | { | |
1505 | if (debug) | |
1506 | { | |
1507 | fprintf (debug, "Coalesce list: (%d)", x); | |
1508 | print_generic_expr (debug, partition_to_var (map, x), TDF_SLIM); | |
1509 | fprintf (debug, " & (%d)", y); | |
1510 | print_generic_expr (debug, partition_to_var (map, y), TDF_SLIM); | |
1511 | } | |
1512 | ||
1513 | w = tpa_find_tree (tpa, x); | |
1514 | z = tpa_find_tree (tpa, y); | |
1515 | if (w != z || w == TPA_NONE || z == TPA_NONE) | |
1516 | { | |
1517 | if (debug) | |
1518 | { | |
1519 | if (w != z) | |
1520 | fprintf (debug, ": Fail, Non-matching TPA's\n"); | |
1521 | if (w == TPA_NONE) | |
1522 | fprintf (debug, ": Fail %d non TPA.\n", x); | |
1523 | else | |
1524 | fprintf (debug, ": Fail %d non TPA.\n", y); | |
1525 | } | |
1526 | continue; | |
1527 | } | |
1528 | var = partition_to_var (map, x); | |
1529 | tmp = partition_to_var (map, y); | |
1530 | x = var_to_partition (map, var); | |
1531 | y = var_to_partition (map, tmp); | |
1532 | if (debug) | |
1533 | fprintf (debug, " [map: %d, %d] ", x, y); | |
1534 | if (x == y) | |
1535 | { | |
1536 | if (debug) | |
1537 | fprintf (debug, ": Already Coalesced.\n"); | |
1538 | continue; | |
1539 | } | |
1540 | if (!conflict_graph_conflict_p (graph, x, y)) | |
1541 | { | |
1542 | z = var_union (map, var, tmp); | |
1543 | if (z == NO_PARTITION) | |
1544 | { | |
1545 | if (debug) | |
1546 | fprintf (debug, ": Unable to perform partition union.\n"); | |
1547 | continue; | |
1548 | } | |
1549 | ||
1550 | /* z is the new combined partition. We need to remove the other | |
1551 | partition from the list. Set x to be that other partition. */ | |
1552 | if (z == x) | |
1553 | { | |
1554 | conflict_graph_merge_regs (graph, x, y); | |
1555 | w = tpa_find_tree (tpa, y); | |
1556 | tpa_remove_partition (tpa, w, y); | |
1557 | } | |
1558 | else | |
1559 | { | |
1560 | conflict_graph_merge_regs (graph, y, x); | |
1561 | w = tpa_find_tree (tpa, x); | |
1562 | tpa_remove_partition (tpa, w, x); | |
1563 | } | |
1564 | ||
1565 | if (debug) | |
1566 | fprintf (debug, ": Success -> %d\n", z); | |
1567 | } | |
1568 | else | |
1569 | if (debug) | |
1570 | fprintf (debug, ": Fail due to conflict\n"); | |
1571 | } | |
1572 | /* If using a coalesce list, don't try to coalesce anything else. */ | |
1573 | return; | |
1574 | } | |
1575 | ||
1576 | for (x = 0; x < tpa_num_trees (tpa); x++) | |
1577 | { | |
1578 | while (tpa_first_partition (tpa, x) != TPA_NONE) | |
1579 | { | |
1580 | int p1, p2; | |
1581 | /* Coalesce first partition with anything that doesn't conflict. */ | |
1582 | y = tpa_first_partition (tpa, x); | |
1583 | tpa_remove_partition (tpa, x, y); | |
1584 | ||
1585 | var = partition_to_var (map, y); | |
1586 | /* p1 is the partition representative to which y belongs. */ | |
1587 | p1 = var_to_partition (map, var); | |
1588 | ||
1589 | for (z = tpa_next_partition (tpa, y); | |
1590 | z != TPA_NONE; | |
1591 | z = tpa_next_partition (tpa, z)) | |
1592 | { | |
1593 | tmp = partition_to_var (map, z); | |
1594 | /* p2 is the partition representative to which z belongs. */ | |
1595 | p2 = var_to_partition (map, tmp); | |
1596 | if (debug) | |
1597 | { | |
1598 | fprintf (debug, "Coalesce : "); | |
1599 | print_generic_expr (debug, var, TDF_SLIM); | |
1600 | fprintf (debug, " &"); | |
1601 | print_generic_expr (debug, tmp, TDF_SLIM); | |
1602 | fprintf (debug, " (%d ,%d)", p1, p2); | |
1603 | } | |
1604 | ||
1605 | /* If partitions are already merged, don't check for conflict. */ | |
1606 | if (tmp == var) | |
1607 | { | |
1608 | tpa_remove_partition (tpa, x, z); | |
1609 | if (debug) | |
1610 | fprintf (debug, ": Already coalesced\n"); | |
1611 | } | |
1612 | else | |
1613 | if (!conflict_graph_conflict_p (graph, p1, p2)) | |
1614 | { | |
1615 | int v; | |
1616 | if (tpa_find_tree (tpa, y) == TPA_NONE | |
1617 | || tpa_find_tree (tpa, z) == TPA_NONE) | |
1618 | { | |
1619 | if (debug) | |
1620 | fprintf (debug, ": Fail non-TPA member\n"); | |
1621 | continue; | |
1622 | } | |
1623 | if ((v = var_union (map, var, tmp)) == NO_PARTITION) | |
1624 | { | |
1625 | if (debug) | |
1626 | fprintf (debug, ": Fail cannot combine partitions\n"); | |
1627 | continue; | |
1628 | } | |
1629 | ||
1630 | tpa_remove_partition (tpa, x, z); | |
1631 | if (v == p1) | |
1632 | conflict_graph_merge_regs (graph, v, z); | |
1633 | else | |
1634 | { | |
1635 | /* Update the first partition's representative. */ | |
1636 | conflict_graph_merge_regs (graph, v, y); | |
1637 | p1 = v; | |
1638 | } | |
1639 | ||
1640 | /* The root variable of the partition may be changed | |
1641 | now. */ | |
1642 | var = partition_to_var (map, p1); | |
1643 | ||
1644 | if (debug) | |
1645 | fprintf (debug, ": Success -> %d\n", v); | |
1646 | } | |
1647 | else | |
1648 | if (debug) | |
1649 | fprintf (debug, ": Fail, Conflict\n"); | |
1650 | } | |
1651 | } | |
1652 | } | |
1653 | } | |
1654 | ||
1655 | ||
1656 | /* Send debug info for coalesce list CL to file F. */ | |
1657 | ||
1658 | void | |
1659 | dump_coalesce_list (FILE *f, coalesce_list_p cl) | |
1660 | { | |
1661 | partition_pair_p node; | |
1662 | int x, num; | |
1663 | tree var; | |
1664 | ||
1665 | if (cl->add_mode) | |
1666 | { | |
1667 | fprintf (f, "Coalesce List:\n"); | |
1668 | num = num_var_partitions (cl->map); | |
1669 | for (x = 0; x < num; x++) | |
1670 | { | |
1671 | node = cl->list[x]; | |
1672 | if (node) | |
1673 | { | |
1674 | fprintf (f, "["); | |
1675 | print_generic_expr (f, partition_to_var (cl->map, x), TDF_SLIM); | |
1676 | fprintf (f, "] - "); | |
1677 | for ( ; node; node = node->next) | |
1678 | { | |
1679 | var = partition_to_var (cl->map, node->second_partition); | |
1680 | print_generic_expr (f, var, TDF_SLIM); | |
1681 | fprintf (f, "(%1d), ", node->cost); | |
1682 | } | |
1683 | fprintf (f, "\n"); | |
1684 | } | |
1685 | } | |
1686 | } | |
1687 | else | |
1688 | { | |
1689 | fprintf (f, "Sorted Coalesce list:\n"); | |
1690 | for (node = cl->list[0]; node; node = node->next) | |
1691 | { | |
1692 | fprintf (f, "(%d) ", node->cost); | |
1693 | var = partition_to_var (cl->map, node->first_partition); | |
1694 | print_generic_expr (f, var, TDF_SLIM); | |
1695 | fprintf (f, " : "); | |
1696 | var = partition_to_var (cl->map, node->second_partition); | |
1697 | print_generic_expr (f, var, TDF_SLIM); | |
1698 | fprintf (f, "\n"); | |
1699 | } | |
1700 | } | |
1701 | } | |
1702 | ||
1703 | ||
1704 | /* Output tree_partition_associator object TPA to file F.. */ | |
1705 | ||
1706 | void | |
1707 | tpa_dump (FILE *f, tpa_p tpa) | |
1708 | { | |
1709 | int x, i; | |
1710 | ||
1711 | if (!tpa) | |
1712 | return; | |
1713 | ||
1714 | for (x = 0; x < tpa_num_trees (tpa); x++) | |
1715 | { | |
1716 | print_generic_expr (f, tpa_tree (tpa, x), TDF_SLIM); | |
1717 | fprintf (f, " : ("); | |
1718 | for (i = tpa_first_partition (tpa, x); | |
1719 | i != TPA_NONE; | |
1720 | i = tpa_next_partition (tpa, i)) | |
1721 | { | |
1722 | fprintf (f, "(%d)",i); | |
1723 | print_generic_expr (f, partition_to_var (tpa->map, i), TDF_SLIM); | |
1724 | fprintf (f, " "); | |
1725 | ||
1726 | #ifdef ENABLE_CHECKING | |
1727 | if (tpa_find_tree (tpa, i) != x) | |
1728 | fprintf (f, "**find tree incorrectly set** "); | |
1729 | #endif | |
1730 | ||
1731 | } | |
1732 | fprintf (f, ")\n"); | |
1733 | } | |
1734 | fflush (f); | |
1735 | } | |
1736 | ||
1737 | ||
1738 | /* Output partition map MAP to file F. */ | |
1739 | ||
1740 | void | |
1741 | dump_var_map (FILE *f, var_map map) | |
1742 | { | |
1743 | int t; | |
1744 | unsigned x, y; | |
1745 | int p; | |
1746 | ||
1747 | fprintf (f, "\nPartition map \n\n"); | |
1748 | ||
1749 | for (x = 0; x < map->num_partitions; x++) | |
1750 | { | |
1751 | if (map->compact_to_partition != NULL) | |
1752 | p = map->compact_to_partition[x]; | |
1753 | else | |
1754 | p = x; | |
1755 | ||
1756 | if (map->partition_to_var[p] == NULL_TREE) | |
1757 | continue; | |
1758 | ||
1759 | t = 0; | |
95a3742c | 1760 | for (y = 1; y < num_ssa_names; y++) |
6de9cd9a DN |
1761 | { |
1762 | p = partition_find (map->var_partition, y); | |
1763 | if (map->partition_to_compact) | |
1764 | p = map->partition_to_compact[p]; | |
1765 | if (p == (int)x) | |
1766 | { | |
1767 | if (t++ == 0) | |
1768 | { | |
1769 | fprintf(f, "Partition %d (", x); | |
1770 | print_generic_expr (f, partition_to_var (map, p), TDF_SLIM); | |
1771 | fprintf (f, " - "); | |
1772 | } | |
1773 | fprintf (f, "%d ", y); | |
1774 | } | |
1775 | } | |
1776 | if (t != 0) | |
1777 | fprintf (f, ")\n"); | |
1778 | } | |
1779 | fprintf (f, "\n"); | |
1780 | } | |
1781 | ||
1782 | ||
1783 | /* Output live range info LIVE to file F, controlled by FLAG. */ | |
1784 | ||
1785 | void | |
1786 | dump_live_info (FILE *f, tree_live_info_p live, int flag) | |
1787 | { | |
1788 | basic_block bb; | |
3cd8c58a | 1789 | unsigned i; |
6de9cd9a | 1790 | var_map map = live->map; |
87c476a2 | 1791 | bitmap_iterator bi; |
6de9cd9a DN |
1792 | |
1793 | if ((flag & LIVEDUMP_ENTRY) && live->livein) | |
1794 | { | |
1795 | FOR_EACH_BB (bb) | |
1796 | { | |
1797 | fprintf (f, "\nLive on entry to BB%d : ", bb->index); | |
1798 | for (i = 0; i < num_var_partitions (map); i++) | |
1799 | { | |
1800 | if (bitmap_bit_p (live_entry_blocks (live, i), bb->index)) | |
1801 | { | |
1802 | print_generic_expr (f, partition_to_var (map, i), TDF_SLIM); | |
1803 | fprintf (f, " "); | |
1804 | } | |
1805 | } | |
1806 | fprintf (f, "\n"); | |
1807 | } | |
1808 | } | |
1809 | ||
1810 | if ((flag & LIVEDUMP_EXIT) && live->liveout) | |
1811 | { | |
1812 | FOR_EACH_BB (bb) | |
1813 | { | |
1814 | fprintf (f, "\nLive on exit from BB%d : ", bb->index); | |
87c476a2 | 1815 | EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi) |
6de9cd9a DN |
1816 | { |
1817 | print_generic_expr (f, partition_to_var (map, i), TDF_SLIM); | |
1818 | fprintf (f, " "); | |
87c476a2 | 1819 | } |
6de9cd9a DN |
1820 | fprintf (f, "\n"); |
1821 | } | |
1822 | } | |
1823 | } | |
1e128c5f GB |
1824 | |
1825 | #ifdef ENABLE_CHECKING | |
1826 | void | |
1827 | register_ssa_partition_check (tree ssa_var) | |
1828 | { | |
1829 | gcc_assert (TREE_CODE (ssa_var) == SSA_NAME); | |
1830 | if (!is_gimple_reg (SSA_NAME_VAR (ssa_var))) | |
1831 | { | |
1832 | fprintf (stderr, "Illegally registering a virtual SSA name :"); | |
1833 | print_generic_expr (stderr, ssa_var, TDF_SLIM); | |
1834 | fprintf (stderr, " in the SSA->Normal phase.\n"); | |
1835 | internal_error ("SSA corruption"); | |
1836 | } | |
1837 | } | |
1838 | #endif |