* tree-cfg.c (tree_find_edge_insert_loc): Handle naked RETURN_EXPR.
[official-gcc.git] / gcc / tree-ssa-live.c
blob132af929852e8ba4b33a55e85279f0f8214adc78
1 /* Liveness for SSA trees.
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to
19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, USA. */
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"
33 #include "tree-gimple.h"
34 #include "tree-inline.h"
35 #include "varray.h"
36 #include "timevar.h"
37 #include "hashtab.h"
38 #include "tree-dump.h"
39 #include "tree-ssa-live.h"
40 #include "toplev.h"
42 static void live_worklist (tree_live_info_p, int *, int);
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);
52 /* This is where the mapping from SSA version number to real storage variable
53 is tracked.
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.
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. */
64 /* Create a variable partition map of SIZE, initialize and return it. */
66 var_map
67 init_var_map (int size)
69 var_map map;
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));
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;
86 /* Free memory associated with MAP. */
88 void
89 delete_var_map (var_map map)
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);
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
105 partitions cannot be combined, NO_PARTITION is returned. */
108 var_union (var_map map, tree var1, tree var2)
110 int p1, p2, p3;
111 tree root_var = NULL_TREE;
112 tree other_var = NULL_TREE;
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. */
118 if (TREE_CODE (var1) == SSA_NAME)
119 p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
120 else
122 p1 = var_to_partition (map, var1);
123 if (map->compact_to_partition)
124 p1 = map->compact_to_partition[p1];
125 root_var = var1;
128 if (TREE_CODE (var2) == SSA_NAME)
129 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
130 else
132 p2 = var_to_partition (map, var2);
133 if (map->compact_to_partition)
134 p2 = map->compact_to_partition[p2];
136 /* If there is no root_var set, or it's not a user variable, set the
137 root_var to this one. */
138 if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var)))
140 other_var = root_var;
141 root_var = var2;
143 else
144 other_var = var2;
147 gcc_assert (p1 != NO_PARTITION);
148 gcc_assert (p2 != NO_PARTITION);
150 if (p1 == p2)
151 p3 = p1;
152 else
153 p3 = partition_union (map->var_partition, p1, p2);
155 if (map->partition_to_compact)
156 p3 = map->partition_to_compact[p3];
158 if (root_var)
159 change_partition_var (map, root_var, p3);
160 if (other_var)
161 change_partition_var (map, other_var, p3);
163 return p3;
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.
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.
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. */
184 void
185 compact_var_map (var_map map, int flags)
187 sbitmap used;
188 int tmp, root, root_i;
189 unsigned int x, limit, count;
190 tree var;
191 root_var_p rv = NULL;
193 limit = map->partition_size;
194 used = sbitmap_alloc (limit);
195 sbitmap_zero (used);
197 /* Already compressed? Abandon the old one. */
198 if (map->partition_to_compact)
200 free (map->partition_to_compact);
201 map->partition_to_compact = NULL;
203 if (map->compact_to_partition)
205 free (map->compact_to_partition);
206 map->compact_to_partition = NULL;
209 map->num_partitions = map->partition_size;
211 if (flags & VARMAP_NO_SINGLE_DEFS)
212 rv = root_var_init (map);
214 map->partition_to_compact = (int *)xmalloc (limit * sizeof (int));
215 memset (map->partition_to_compact, 0xff, (limit * sizeof (int)));
217 /* Find out which partitions are actually referenced. */
218 count = 0;
219 for (x = 0; x < limit; x++)
221 tmp = partition_find (map->var_partition, x);
222 if (!TEST_BIT (used, tmp) && map->partition_to_var[tmp] != NULL_TREE)
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)
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;
234 SET_BIT (used, tmp);
235 count++;
239 /* Build a compacted partitioning. */
240 if (count != limit)
242 sbitmap_iterator sbi;
244 map->compact_to_partition = (int *)xmalloc (count * sizeof (int));
245 count = 0;
246 /* SSA renaming begins at 1, so skip 0 when compacting. */
247 EXECUTE_IF_SET_IN_SBITMAP (used, 1, x, sbi)
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++;
257 else
259 free (map->partition_to_compact);
260 map->partition_to_compact = NULL;
263 map->num_partitions = count;
265 if (rv)
266 root_var_delete (rv);
267 sbitmap_free (used);
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. */
275 void
276 change_partition_var (var_map map, tree var, int part)
278 var_ann_t ann;
280 gcc_assert (TREE_CODE (var) != SSA_NAME);
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;
289 static inline void mark_all_vars_used (tree *);
291 /* Helper function for mark_all_vars_used, called via walk_tree. */
293 static tree
294 mark_all_vars_used_1 (tree *tp, int *walk_subtrees,
295 void *data ATTRIBUTE_UNUSED)
297 tree t = *tp;
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)
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;
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);
315 if (IS_TYPE_OR_DECL_P (t))
316 *walk_subtrees = 0;
318 return NULL;
321 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
322 eliminated during the tree->rtl conversion process. */
324 static inline void
325 mark_all_vars_used (tree *expr_p)
327 walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL);
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. */
334 var_map
335 create_ssa_var_map (int flags)
337 block_stmt_iterator bsi;
338 basic_block bb;
339 tree dest, use;
340 tree stmt;
341 var_map map;
342 ssa_op_iter iter;
343 #ifdef ENABLE_CHECKING
344 bitmap used_in_real_ops;
345 bitmap used_in_virtual_ops;
346 #endif
348 map = init_var_map (num_ssa_names + 1);
350 #ifdef ENABLE_CHECKING
351 used_in_real_ops = BITMAP_ALLOC (NULL);
352 used_in_virtual_ops = BITMAP_ALLOC (NULL);
353 #endif
355 if (flags & SSA_VAR_MAP_REF_COUNT)
357 map->ref_count
358 = (int *)xmalloc (((num_ssa_names + 1) * sizeof (int)));
359 memset (map->ref_count, 0, (num_ssa_names + 1) * sizeof (int));
362 FOR_EACH_BB (bb)
364 tree phi, arg;
365 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
367 int i;
368 register_ssa_partition (map, PHI_RESULT (phi), false);
369 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
371 arg = PHI_ARG_DEF (phi, i);
372 if (TREE_CODE (arg) == SSA_NAME)
373 register_ssa_partition (map, arg, true);
375 mark_all_vars_used (&PHI_ARG_DEF_TREE (phi, i));
379 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
381 stmt = bsi_stmt (bsi);
383 /* Register USE and DEF operands in each statement. */
384 FOR_EACH_SSA_TREE_OPERAND (use , stmt, iter, SSA_OP_USE)
386 register_ssa_partition (map, use, true);
388 #ifdef ENABLE_CHECKING
389 bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (use)));
390 #endif
393 FOR_EACH_SSA_TREE_OPERAND (dest, stmt, iter, SSA_OP_DEF)
395 register_ssa_partition (map, dest, false);
397 #ifdef ENABLE_CHECKING
398 bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (dest)));
399 #endif
402 #ifdef ENABLE_CHECKING
403 /* Validate that virtual ops don't get used in funny ways. */
404 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter,
405 SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF)
407 bitmap_set_bit (used_in_virtual_ops,
408 DECL_UID (SSA_NAME_VAR (use)));
411 #endif /* ENABLE_CHECKING */
413 mark_all_vars_used (bsi_stmt_ptr (bsi));
417 #if defined ENABLE_CHECKING
419 unsigned i;
420 bitmap both = BITMAP_ALLOC (NULL);
421 bitmap_and (both, used_in_real_ops, used_in_virtual_ops);
422 if (!bitmap_empty_p (both))
424 bitmap_iterator bi;
426 EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi)
427 fprintf (stderr, "Variable %s used in real and virtual operands\n",
428 get_name (referenced_var (i)));
429 internal_error ("SSA corruption");
432 BITMAP_FREE (used_in_real_ops);
433 BITMAP_FREE (used_in_virtual_ops);
434 BITMAP_FREE (both);
436 #endif
438 return map;
442 /* Allocate and return a new live range information object base on MAP. */
444 static tree_live_info_p
445 new_tree_live_info (var_map map)
447 tree_live_info_p live;
448 unsigned x;
450 live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
451 live->map = map;
452 live->num_blocks = last_basic_block;
454 live->global = BITMAP_ALLOC (NULL);
456 live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap));
457 for (x = 0; x < num_var_partitions (map); x++)
458 live->livein[x] = BITMAP_ALLOC (NULL);
460 /* liveout is deferred until it is actually requested. */
461 live->liveout = NULL;
462 return live;
466 /* Free storage for live range info object LIVE. */
468 void
469 delete_tree_live_info (tree_live_info_p live)
471 int x;
472 if (live->liveout)
474 for (x = live->num_blocks - 1; x >= 0; x--)
475 BITMAP_FREE (live->liveout[x]);
476 free (live->liveout);
478 if (live->livein)
480 for (x = num_var_partitions (live->map) - 1; x >= 0; x--)
481 BITMAP_FREE (live->livein[x]);
482 free (live->livein);
484 if (live->global)
485 BITMAP_FREE (live->global);
487 free (live);
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. */
495 static void
496 live_worklist (tree_live_info_p live, int *stack, int i)
498 unsigned b;
499 tree var;
500 basic_block def_bb = NULL;
501 edge e;
502 var_map map = live->map;
503 edge_iterator ei;
504 bitmap_iterator bi;
505 int *tos = stack;
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));
511 EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, bi)
513 *tos++ = b;
516 while (tos != stack)
518 b = *--tos;
520 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
521 if (e->src != ENTRY_BLOCK_PTR)
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))
528 bitmap_set_bit (live->livein[i], e->src->index);
529 *tos++ = e->src->index;
536 /* If VAR is in a partition of MAP, set the bit for that partition in VEC. */
538 static inline void
539 set_if_valid (var_map map, bitmap vec, tree var)
541 int p = var_to_partition (map, var);
542 if (p != NO_PARTITION)
543 bitmap_set_bit (vec, p);
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. */
550 static inline void
551 add_livein_if_notdef (tree_live_info_p live, bitmap def_vec,
552 tree var, basic_block bb)
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))
559 bitmap_set_bit (live->livein[p], bb->index);
560 bitmap_set_bit (live->global, p);
565 /* Given partition map MAP, calculate all the live on entry bitmaps for
566 each basic block. Return a live info object. */
568 tree_live_info_p
569 calculate_live_on_entry (var_map map)
571 tree_live_info_p live;
572 unsigned i;
573 basic_block bb;
574 bitmap saw_def;
575 tree phi, var, stmt;
576 tree op;
577 edge e;
578 int *stack;
579 block_stmt_iterator bsi;
580 ssa_op_iter iter;
581 bitmap_iterator bi;
582 #ifdef ENABLE_CHECKING
583 int num;
584 edge_iterator ei;
585 #endif
587 saw_def = BITMAP_ALLOC (NULL);
589 live = new_tree_live_info (map);
591 FOR_EACH_BB (bb)
593 bitmap_clear (saw_def);
595 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
597 for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
599 var = PHI_ARG_DEF (phi, i);
600 if (!phi_ssa_name_p (var))
601 continue;
602 stmt = SSA_NAME_DEF_STMT (var);
603 e = EDGE_PRED (bb, i);
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);
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. */
620 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
622 var = PHI_RESULT (phi);
623 set_if_valid (map, saw_def, var);
626 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
628 stmt = bsi_stmt (bsi);
630 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
632 add_livein_if_notdef (live, saw_def, op, bb);
635 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
637 set_if_valid (map, saw_def, op);
642 stack = xmalloc (sizeof (int) * last_basic_block);
643 EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi)
645 live_worklist (live, stack, i);
647 free (stack);
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. */
654 bb = ENTRY_BLOCK_PTR;
655 num = 0;
656 FOR_EACH_EDGE (e, ei, bb->succs)
658 int entry_block = e->dest->index;
659 if (e->dest == EXIT_BLOCK_PTR)
660 continue;
661 for (i = 0; i < (unsigned)num_var_partitions (map); i++)
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));
670 if (bitmap_bit_p (live_entry_blocks (live, i), entry_block))
672 if (!IS_EMPTY_STMT (stmt))
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");
685 else
687 if (d != var)
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)
694 fprintf (stderr, " but is not the default def of ");
695 print_generic_expr (stderr, d, TDF_SLIM);
696 fprintf (stderr, "\n");
698 else
699 fprintf (stderr, " and there is no default def.\n");
703 else
704 if (d == var)
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;
711 phi = PHI_CHAIN (phi))
713 for (z = 0; z < PHI_NUM_ARGS (phi); z++)
714 if (var == PHI_ARG_DEF (phi, z))
716 ok = 1;
717 break;
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");
730 gcc_assert (num <= 0);
731 #endif
733 BITMAP_FREE (saw_def);
735 return live;
739 /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
741 void
742 calculate_live_on_exit (tree_live_info_p liveinfo)
744 unsigned b;
745 unsigned i, x;
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;
753 on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
754 for (x = 0; x < (unsigned)last_basic_block; x++)
755 on_exit[x] = BITMAP_ALLOC (NULL);
757 /* Set all the live-on-exit bits for uses in PHIs. */
758 FOR_EACH_BB (bb)
760 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
761 for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
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);
771 /* Set live on exit for all predecessors of live on entry's. */
772 for (i = 0; i < num_var_partitions (map); i++)
774 bitmap_iterator bi;
776 on_entry = live_entry_blocks (liveinfo, i);
777 EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi)
779 edge_iterator ei;
780 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
781 if (e->src != ENTRY_BLOCK_PTR)
782 bitmap_set_bit (on_exit[e->src->index], i);
786 liveinfo->liveout = on_exit;
790 /* Initialize a tree_partition_associator object using MAP. */
792 static tpa_p
793 tpa_init (var_map map)
795 tpa_p tpa;
796 int num_partitions = num_var_partitions (map);
797 int x;
799 if (num_partitions == 0)
800 return NULL;
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));
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));
812 x = MAX (40, (num_partitions / 20));
813 tpa->trees = VEC_alloc (tree, heap, x);
814 VARRAY_INT_INIT (tpa->first_partition, x, "first_partition");
816 return tpa;
821 /* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA. */
823 void
824 tpa_remove_partition (tpa_p tpa, int tree_index, int partition_index)
826 int i;
828 i = tpa_first_partition (tpa, tree_index);
829 if (i == partition_index)
831 VARRAY_INT (tpa->first_partition, tree_index) = tpa->next_partition[i];
833 else
835 for ( ; i != TPA_NONE; i = tpa_next_partition (tpa, i))
837 if (tpa->next_partition[i] == partition_index)
839 tpa->next_partition[i] = tpa->next_partition[partition_index];
840 break;
847 /* Free the memory used by tree_partition_associator object TPA. */
849 void
850 tpa_delete (tpa_p tpa)
852 if (!tpa)
853 return;
855 VEC_free (tree, heap, tpa->trees);
856 free (tpa->partition_to_tree_map);
857 free (tpa->next_partition);
858 free (tpa);
862 /* This function will remove any tree entries from TPA which have only a single
863 element. This will help keep the size of the conflict graph down. The
864 function returns the number of remaining tree lists. */
866 int
867 tpa_compact (tpa_p tpa)
869 int last, x, y, first, swap_i;
870 tree swap_t;
872 /* Find the last list which has more than 1 partition. */
873 for (last = tpa->num_trees - 1; last > 0; last--)
875 first = tpa_first_partition (tpa, last);
876 if (tpa_next_partition (tpa, first) != NO_PARTITION)
877 break;
880 x = 0;
881 while (x < last)
883 first = tpa_first_partition (tpa, x);
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)
889 swap_t = VEC_index (tree, tpa->trees, last);
890 swap_i = VARRAY_INT (tpa->first_partition, last);
892 /* Update the last entry. Since it is known to only have one
893 partition, there is nothing else to update. */
894 VEC_replace (tree, tpa->trees, last,
895 VEC_index (tree, tpa->trees, x));
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;
900 /* Since this list is known to have more than one partition, update
901 the list owner entries. */
902 VEC_replace (tree, tpa->trees, x, swap_t);
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;
909 /* Ensure last is a list with more than one partition. */
910 last--;
911 for (; last > x; last--)
913 first = tpa_first_partition (tpa, last);
914 if (tpa_next_partition (tpa, first) != NO_PARTITION)
915 break;
918 x++;
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;
930 /* Initialize a root_var object with SSA partitions from MAP which are based
931 on each root variable. */
933 root_var_p
934 root_var_init (var_map map)
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;
943 rv = tpa_init (map);
944 if (!rv)
945 return NULL;
947 seen = sbitmap_alloc (num_partitions);
948 sbitmap_zero (seen);
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--)
954 t = partition_to_var (map, x);
956 /* The var map may not be compacted yet, so check for NULL. */
957 if (!t)
958 continue;
960 p = var_to_partition (map, t);
962 gcc_assert (p != NO_PARTITION);
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)
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;
977 else
979 ann->root_var_processed = 1;
980 VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++;
981 VEC_safe_push (tree, heap, rv->trees, t);
982 VARRAY_PUSH_INT (rv->first_partition, p);
984 rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann);
987 /* Reset the out_of_ssa_tag flag on each variable for later use. */
988 for (x = 0; x < rv->num_trees; x++)
990 t = VEC_index (tree, rv->trees, x);
991 var_ann (t)->root_var_processed = 0;
994 sbitmap_free (seen);
995 return rv;
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. */
1002 type_var_p
1003 type_var_init (var_map map)
1005 type_var_p tv;
1006 int x, y, p;
1007 int num_partitions = num_var_partitions (map);
1008 tree t;
1009 sbitmap seen;
1011 seen = sbitmap_alloc (num_partitions);
1012 sbitmap_zero (seen);
1014 tv = tpa_init (map);
1015 if (!tv)
1016 return NULL;
1018 for (x = num_partitions - 1; x >= 0; x--)
1020 t = partition_to_var (map, x);
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)
1029 || !DECL_IGNORED_P (t)
1030 || DECL_RTL_SET_P (t))))
1031 continue;
1033 p = var_to_partition (map, t);
1035 gcc_assert (p != NO_PARTITION);
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);
1044 /* Find the list for this type. */
1045 for (y = 0; y < tv->num_trees; y++)
1046 if (t == VEC_index (tree, tv->trees, y))
1047 break;
1048 if (y == tv->num_trees)
1050 tv->num_trees++;
1051 VEC_safe_push (tree, heap, tv->trees, t);
1052 VARRAY_PUSH_INT (tv->first_partition, p);
1054 else
1056 tv->next_partition[p] = VARRAY_INT (tv->first_partition, y);
1057 VARRAY_INT (tv->first_partition, y) = p;
1059 tv->partition_to_tree_map[p] = y;
1061 sbitmap_free (seen);
1062 return tv;
1066 /* Create a new coalesce list object from MAP and return it. */
1068 coalesce_list_p
1069 create_coalesce_list (var_map map)
1071 coalesce_list_p list;
1073 list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
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;
1083 /* Delete coalesce list CL. */
1085 void
1086 delete_coalesce_list (coalesce_list_p cl)
1088 free (cl->list);
1089 free (cl);
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. */
1097 static partition_pair_p
1098 find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create)
1100 partition_pair_p node, tmp;
1101 int s;
1103 /* Normalize so that p1 is the smaller value. */
1104 if (p2 < p1)
1106 s = p1;
1107 p1 = p2;
1108 p2 = s;
1111 tmp = NULL;
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)
1117 if (node->second_partition == p2)
1118 return node;
1119 else
1120 if (node->second_partition > p2)
1121 break;
1122 tmp = node;
1125 if (!create)
1126 return NULL;
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;
1133 if (tmp != NULL)
1135 node->next = tmp->next;
1136 tmp->next = node;
1138 else
1140 /* This is now the first node in the list. */
1141 node->next = cl->list[p1];
1142 cl->list[p1] = node;
1145 return node;
1148 /* Return cost of execution of copy instruction with FREQUENCY
1149 possibly on CRITICAL edge and in HOT basic block. */
1151 coalesce_cost (int frequency, bool hot, bool critical)
1153 /* Base costs on BB frequencies bounded by 1. */
1154 int cost = frequency;
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;
1167 /* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE. */
1169 void
1170 add_coalesce (coalesce_list_p cl, int p1, int p2,
1171 int value)
1173 partition_pair_p node;
1175 gcc_assert (cl->add_mode);
1177 if (p1 == p2)
1178 return;
1180 node = find_partition_pair (cl, p1, p2, true);
1182 node->cost += value;
1186 /* Comparison function to allow qsort to sort P1 and P2 in descending order. */
1188 static
1189 int compare_pairs (const void *p1, const void *p2)
1191 return (*(partition_pair_p *)p2)->cost - (*(partition_pair_p *)p1)->cost;
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. */
1199 void
1200 sort_coalesce_list (coalesce_list_p cl)
1202 unsigned x, num, count;
1203 partition_pair_p chain, p;
1204 partition_pair_p *list;
1206 gcc_assert (cl->add_mode);
1208 cl->add_mode = false;
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)
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;
1224 /* Only call qsort if there are more than 2 items. */
1225 if (num > 2)
1227 list = xmalloc (sizeof (partition_pair_p) * num);
1228 count = 0;
1229 for (p = chain; p != NULL; p = p->next)
1230 list[count++] = p;
1232 gcc_assert (count == num);
1234 qsort (list, count, sizeof (partition_pair_p), compare_pairs);
1236 p = list[0];
1237 for (x = 1; x < num; x++)
1239 p->next = list[x];
1240 p = list[x];
1242 p->next = NULL;
1243 cl->list[0] = list[0];
1244 free (list);
1246 else
1248 cl->list[0] = chain;
1249 if (num == 2)
1251 /* Simply swap the two elements if they are in the wrong order. */
1252 if (chain->cost < chain->next->cost)
1254 cl->list[0] = chain->next;
1255 cl->list[0]->next = chain;
1256 chain->next = NULL;
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. */
1267 static int
1268 pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
1270 partition_pair_p node;
1271 int ret;
1273 gcc_assert (!cl->add_mode);
1275 node = cl->list[0];
1276 if (!node)
1277 return NO_BEST_COALESCE;
1279 cl->list[0] = node->next;
1281 *p1 = node->first_partition;
1282 *p2 = node->second_partition;
1283 ret = node->cost;
1284 free (node);
1286 return ret;
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. */
1294 static inline void
1295 add_conflicts_if_valid (tpa_p tpa, conflict_graph graph,
1296 var_map map, bitmap vec, tree var)
1298 int p, y, first;
1299 p = var_to_partition (map, var);
1300 if (p != NO_PARTITION)
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))
1312 if (bitmap_bit_p (vec, y))
1313 conflict_graph_add (graph, p, y);
1318 DEF_VEC_I(int);
1319 DEF_VEC_ALLOC_I(int,heap);
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. */
1325 conflict_graph
1326 build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa,
1327 coalesce_list_p cl)
1329 conflict_graph graph;
1330 var_map map;
1331 bitmap live;
1332 unsigned x, y, i;
1333 basic_block bb;
1334 int *partition_link, *tpa_nodes;
1335 VEC(int,heap) *tpa_to_clear;
1336 unsigned l;
1337 ssa_op_iter iter;
1338 bitmap_iterator bi;
1340 map = live_var_map (liveinfo);
1341 graph = conflict_graph_new (num_var_partitions (map));
1343 if (tpa_num_trees (tpa) == 0)
1344 return graph;
1346 live = BITMAP_ALLOC (NULL);
1348 partition_link = xcalloc (num_var_partitions (map) + 1, sizeof (int));
1349 tpa_nodes = xcalloc (tpa_num_trees (tpa), sizeof (int));
1350 tpa_to_clear = VEC_alloc (int, heap, 50);
1352 FOR_EACH_BB (bb)
1354 block_stmt_iterator bsi;
1355 tree phi;
1356 int idx;
1358 /* Start with live on exit temporaries. */
1359 bitmap_copy (live, live_on_exit (liveinfo, bb));
1361 for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
1363 bool is_a_copy = false;
1364 tree stmt = bsi_stmt (bsi);
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.
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
1374 root variables in some cases. */
1376 if (TREE_CODE (stmt) == MODIFY_EXPR)
1378 tree lhs = TREE_OPERAND (stmt, 0);
1379 tree rhs = TREE_OPERAND (stmt, 1);
1380 int p1, p2;
1381 int bit;
1383 if (DECL_P (lhs) || TREE_CODE (lhs) == SSA_NAME)
1384 p1 = var_to_partition (map, lhs);
1385 else
1386 p1 = NO_PARTITION;
1388 if (DECL_P (rhs) || TREE_CODE (rhs) == SSA_NAME)
1389 p2 = var_to_partition (map, rhs);
1390 else
1391 p2 = NO_PARTITION;
1393 if (p1 != NO_PARTITION && p2 != NO_PARTITION)
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)
1405 add_coalesce (cl, p1, p2,
1406 coalesce_cost (bb->frequency,
1407 maybe_hot_bb_p (bb), false));
1408 set_if_valid (map, live, rhs);
1412 if (!is_a_copy)
1414 tree var;
1415 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
1417 add_conflicts_if_valid (tpa, graph, map, live, var);
1420 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
1422 set_if_valid (map, live, var);
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. */
1432 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1434 tree result = PHI_RESULT (phi);
1435 int p = var_to_partition (map, result);
1437 if (p != NO_PARTITION && ! bitmap_bit_p (live, p))
1438 add_conflicts_if_valid (tpa, graph, map, live, result);
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.
1444 TPA roots which have been seen are tracked in 'tpa_nodes'. A nonzero
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).
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. */
1454 EXECUTE_IF_SET_IN_BITMAP (live, 0, x, bi)
1456 i = tpa_find_tree (tpa, x);
1457 if (i != (unsigned)TPA_NONE)
1459 int start = tpa_nodes[i];
1460 /* If start is 0, a new root reference list is being started.
1461 Register it to be cleared. */
1462 if (!start)
1463 VEC_safe_push (int, heap, tpa_to_clear, i);
1465 /* Add interferences to other tpa members seen. */
1466 for (y = start; y != 0; y = partition_link[y])
1467 conflict_graph_add (graph, x, y - 1);
1468 tpa_nodes[i] = x + 1;
1469 partition_link[x + 1] = start;
1473 /* Now clear the used tpa root references. */
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);
1479 free (tpa_nodes);
1480 free (partition_link);
1481 VEC_free (int, heap, tpa_to_clear);
1482 BITMAP_FREE (live);
1483 return graph;
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. */
1493 void
1494 coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map,
1495 coalesce_list_p cl, FILE *debug)
1497 int x, y, z, w;
1498 tree var, tmp;
1500 /* Attempt to coalesce any items in a coalesce list. */
1501 if (cl)
1503 while (pop_best_coalesce (cl, &x, &y) != NO_BEST_COALESCE)
1505 if (debug)
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);
1513 w = tpa_find_tree (tpa, x);
1514 z = tpa_find_tree (tpa, y);
1515 if (w != z || w == TPA_NONE || z == TPA_NONE)
1517 if (debug)
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);
1526 continue;
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)
1536 if (debug)
1537 fprintf (debug, ": Already Coalesced.\n");
1538 continue;
1540 if (!conflict_graph_conflict_p (graph, x, y))
1542 z = var_union (map, var, tmp);
1543 if (z == NO_PARTITION)
1545 if (debug)
1546 fprintf (debug, ": Unable to perform partition union.\n");
1547 continue;
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)
1554 conflict_graph_merge_regs (graph, x, y);
1555 w = tpa_find_tree (tpa, y);
1556 tpa_remove_partition (tpa, w, y);
1558 else
1560 conflict_graph_merge_regs (graph, y, x);
1561 w = tpa_find_tree (tpa, x);
1562 tpa_remove_partition (tpa, w, x);
1565 if (debug)
1566 fprintf (debug, ": Success -> %d\n", z);
1568 else
1569 if (debug)
1570 fprintf (debug, ": Fail due to conflict\n");
1572 /* If using a coalesce list, don't try to coalesce anything else. */
1573 return;
1576 for (x = 0; x < tpa_num_trees (tpa); x++)
1578 while (tpa_first_partition (tpa, x) != TPA_NONE)
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);
1585 var = partition_to_var (map, y);
1586 /* p1 is the partition representative to which y belongs. */
1587 p1 = var_to_partition (map, var);
1589 for (z = tpa_next_partition (tpa, y);
1590 z != TPA_NONE;
1591 z = tpa_next_partition (tpa, z))
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)
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);
1605 /* If partitions are already merged, don't check for conflict. */
1606 if (tmp == var)
1608 tpa_remove_partition (tpa, x, z);
1609 if (debug)
1610 fprintf (debug, ": Already coalesced\n");
1612 else
1613 if (!conflict_graph_conflict_p (graph, p1, p2))
1615 int v;
1616 if (tpa_find_tree (tpa, y) == TPA_NONE
1617 || tpa_find_tree (tpa, z) == TPA_NONE)
1619 if (debug)
1620 fprintf (debug, ": Fail non-TPA member\n");
1621 continue;
1623 if ((v = var_union (map, var, tmp)) == NO_PARTITION)
1625 if (debug)
1626 fprintf (debug, ": Fail cannot combine partitions\n");
1627 continue;
1630 tpa_remove_partition (tpa, x, z);
1631 if (v == p1)
1632 conflict_graph_merge_regs (graph, v, z);
1633 else
1635 /* Update the first partition's representative. */
1636 conflict_graph_merge_regs (graph, v, y);
1637 p1 = v;
1640 /* The root variable of the partition may be changed
1641 now. */
1642 var = partition_to_var (map, p1);
1644 if (debug)
1645 fprintf (debug, ": Success -> %d\n", v);
1647 else
1648 if (debug)
1649 fprintf (debug, ": Fail, Conflict\n");
1656 /* Send debug info for coalesce list CL to file F. */
1658 void
1659 dump_coalesce_list (FILE *f, coalesce_list_p cl)
1661 partition_pair_p node;
1662 int x, num;
1663 tree var;
1665 if (cl->add_mode)
1667 fprintf (f, "Coalesce List:\n");
1668 num = num_var_partitions (cl->map);
1669 for (x = 0; x < num; x++)
1671 node = cl->list[x];
1672 if (node)
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)
1679 var = partition_to_var (cl->map, node->second_partition);
1680 print_generic_expr (f, var, TDF_SLIM);
1681 fprintf (f, "(%1d), ", node->cost);
1683 fprintf (f, "\n");
1687 else
1689 fprintf (f, "Sorted Coalesce list:\n");
1690 for (node = cl->list[0]; node; node = node->next)
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");
1704 /* Output tree_partition_associator object TPA to file F.. */
1706 void
1707 tpa_dump (FILE *f, tpa_p tpa)
1709 int x, i;
1711 if (!tpa)
1712 return;
1714 for (x = 0; x < tpa_num_trees (tpa); x++)
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))
1722 fprintf (f, "(%d)",i);
1723 print_generic_expr (f, partition_to_var (tpa->map, i), TDF_SLIM);
1724 fprintf (f, " ");
1726 #ifdef ENABLE_CHECKING
1727 if (tpa_find_tree (tpa, i) != x)
1728 fprintf (f, "**find tree incorrectly set** ");
1729 #endif
1732 fprintf (f, ")\n");
1734 fflush (f);
1738 /* Output partition map MAP to file F. */
1740 void
1741 dump_var_map (FILE *f, var_map map)
1743 int t;
1744 unsigned x, y;
1745 int p;
1747 fprintf (f, "\nPartition map \n\n");
1749 for (x = 0; x < map->num_partitions; x++)
1751 if (map->compact_to_partition != NULL)
1752 p = map->compact_to_partition[x];
1753 else
1754 p = x;
1756 if (map->partition_to_var[p] == NULL_TREE)
1757 continue;
1759 t = 0;
1760 for (y = 1; y < num_ssa_names; y++)
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)
1767 if (t++ == 0)
1769 fprintf(f, "Partition %d (", x);
1770 print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
1771 fprintf (f, " - ");
1773 fprintf (f, "%d ", y);
1776 if (t != 0)
1777 fprintf (f, ")\n");
1779 fprintf (f, "\n");
1783 /* Output live range info LIVE to file F, controlled by FLAG. */
1785 void
1786 dump_live_info (FILE *f, tree_live_info_p live, int flag)
1788 basic_block bb;
1789 unsigned i;
1790 var_map map = live->map;
1791 bitmap_iterator bi;
1793 if ((flag & LIVEDUMP_ENTRY) && live->livein)
1795 FOR_EACH_BB (bb)
1797 fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1798 for (i = 0; i < num_var_partitions (map); i++)
1800 if (bitmap_bit_p (live_entry_blocks (live, i), bb->index))
1802 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1803 fprintf (f, " ");
1806 fprintf (f, "\n");
1810 if ((flag & LIVEDUMP_EXIT) && live->liveout)
1812 FOR_EACH_BB (bb)
1814 fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1815 EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
1817 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1818 fprintf (f, " ");
1820 fprintf (f, "\n");
1825 #ifdef ENABLE_CHECKING
1826 void
1827 register_ssa_partition_check (tree ssa_var)
1829 gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
1830 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
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");
1838 #endif