1 /* Coalesce SSA_NAMES together for the out-of-ssa pass.
2 Copyright (C) 2004-2015 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 3, or (at your option)
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 COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "fold-const.h"
30 #include "tree-pretty-print.h"
34 #include "hard-reg-set.h"
36 #include "dominance.h"
38 #include "basic-block.h"
39 #include "tree-ssa-alias.h"
40 #include "internal-fn.h"
41 #include "gimple-expr.h"
43 #include "gimple-iterator.h"
44 #include "gimple-ssa.h"
45 #include "tree-phinodes.h"
46 #include "ssa-iterators.h"
47 #include "stringpool.h"
48 #include "tree-ssanames.h"
49 #include "tree-ssa-live.h"
50 #include "tree-ssa-coalesce.h"
51 #include "diagnostic-core.h"
54 /* This set of routines implements a coalesce_list. This is an object which
55 is used to track pairs of ssa_names which are desirable to coalesce
56 together to avoid copies. Costs are associated with each pair, and when
57 all desired information has been collected, the object can be used to
58 order the pairs for processing. */
60 /* This structure defines a pair entry. */
62 typedef struct coalesce_pair
68 typedef const struct coalesce_pair
*const_coalesce_pair_p
;
70 /* Coalesce pair hashtable helpers. */
72 struct coalesce_pair_hasher
: typed_noop_remove
<coalesce_pair
>
74 typedef coalesce_pair
*value_type
;
75 typedef coalesce_pair
*compare_type
;
76 static inline hashval_t
hash (const coalesce_pair
*);
77 static inline bool equal (const coalesce_pair
*, const coalesce_pair
*);
80 /* Hash function for coalesce list. Calculate hash for PAIR. */
83 coalesce_pair_hasher::hash (const coalesce_pair
*pair
)
85 hashval_t a
= (hashval_t
)(pair
->first_element
);
86 hashval_t b
= (hashval_t
)(pair
->second_element
);
88 return b
* (b
- 1) / 2 + a
;
91 /* Equality function for coalesce list hash table. Compare PAIR1 and PAIR2,
92 returning TRUE if the two pairs are equivalent. */
95 coalesce_pair_hasher::equal (const coalesce_pair
*p1
, const coalesce_pair
*p2
)
97 return (p1
->first_element
== p2
->first_element
98 && p1
->second_element
== p2
->second_element
);
101 typedef hash_table
<coalesce_pair_hasher
> coalesce_table_type
;
102 typedef coalesce_table_type::iterator coalesce_iterator_type
;
105 typedef struct cost_one_pair_d
109 struct cost_one_pair_d
*next
;
112 /* This structure maintains the list of coalesce pairs. */
114 typedef struct coalesce_list_d
116 coalesce_table_type
*list
; /* Hash table. */
117 coalesce_pair_p
*sorted
; /* List when sorted. */
118 int num_sorted
; /* Number in the sorted list. */
119 cost_one_pair_p cost_one_list
;/* Single use coalesces with cost 1. */
122 #define NO_BEST_COALESCE -1
123 #define MUST_COALESCE_COST INT_MAX
126 /* Return cost of execution of copy instruction with FREQUENCY. */
129 coalesce_cost (int frequency
, bool optimize_for_size
)
131 /* Base costs on BB frequencies bounded by 1. */
132 int cost
= frequency
;
137 if (optimize_for_size
)
144 /* Return the cost of executing a copy instruction in basic block BB. */
147 coalesce_cost_bb (basic_block bb
)
149 return coalesce_cost (bb
->frequency
, optimize_bb_for_size_p (bb
));
153 /* Return the cost of executing a copy instruction on edge E. */
156 coalesce_cost_edge (edge e
)
160 /* Inserting copy on critical edge costs more than inserting it elsewhere. */
161 if (EDGE_CRITICAL_P (e
))
163 if (e
->flags
& EDGE_ABNORMAL
)
164 return MUST_COALESCE_COST
;
165 if (e
->flags
& EDGE_EH
)
169 FOR_EACH_EDGE (e2
, ei
, e
->dest
->preds
)
172 /* Putting code on EH edge that leads to BB
173 with multiple predecestors imply splitting of
177 /* If there are multiple EH predecestors, we
178 also copy EH regions and produce separate
179 landing pad. This is expensive. */
180 if (e2
->flags
& EDGE_EH
)
188 return coalesce_cost (EDGE_FREQUENCY (e
),
189 optimize_edge_for_size_p (e
)) * mult
;
193 /* Retrieve a pair to coalesce from the cost_one_list in CL. Returns the
194 2 elements via P1 and P2. 1 is returned by the function if there is a pair,
195 NO_BEST_COALESCE is returned if there aren't any. */
198 pop_cost_one_pair (coalesce_list_p cl
, int *p1
, int *p2
)
202 ptr
= cl
->cost_one_list
;
204 return NO_BEST_COALESCE
;
206 *p1
= ptr
->first_element
;
207 *p2
= ptr
->second_element
;
208 cl
->cost_one_list
= ptr
->next
;
215 /* Retrieve the most expensive remaining pair to coalesce from CL. Returns the
216 2 elements via P1 and P2. Their calculated cost is returned by the function.
217 NO_BEST_COALESCE is returned if the coalesce list is empty. */
220 pop_best_coalesce (coalesce_list_p cl
, int *p1
, int *p2
)
222 coalesce_pair_p node
;
225 if (cl
->sorted
== NULL
)
226 return pop_cost_one_pair (cl
, p1
, p2
);
228 if (cl
->num_sorted
== 0)
229 return pop_cost_one_pair (cl
, p1
, p2
);
231 node
= cl
->sorted
[--(cl
->num_sorted
)];
232 *p1
= node
->first_element
;
233 *p2
= node
->second_element
;
241 /* Create a new empty coalesce list object and return it. */
243 static inline coalesce_list_p
244 create_coalesce_list (void)
246 coalesce_list_p list
;
247 unsigned size
= num_ssa_names
* 3;
252 list
= (coalesce_list_p
) xmalloc (sizeof (struct coalesce_list_d
));
253 list
->list
= new coalesce_table_type (size
);
255 list
->num_sorted
= 0;
256 list
->cost_one_list
= NULL
;
261 /* Delete coalesce list CL. */
264 delete_coalesce_list (coalesce_list_p cl
)
266 gcc_assert (cl
->cost_one_list
== NULL
);
270 gcc_assert (cl
->num_sorted
== 0);
275 /* Find a matching coalesce pair object in CL for the pair P1 and P2. If
276 one isn't found, return NULL if CREATE is false, otherwise create a new
277 coalesce pair object and return it. */
279 static coalesce_pair_p
280 find_coalesce_pair (coalesce_list_p cl
, int p1
, int p2
, bool create
)
282 struct coalesce_pair p
;
283 coalesce_pair
**slot
;
286 /* Normalize so that p1 is the smaller value. */
289 p
.first_element
= p2
;
290 p
.second_element
= p1
;
294 p
.first_element
= p1
;
295 p
.second_element
= p2
;
298 hash
= coalesce_pair_hasher::hash (&p
);
299 slot
= cl
->list
->find_slot_with_hash (&p
, hash
, create
? INSERT
: NO_INSERT
);
305 struct coalesce_pair
* pair
= XNEW (struct coalesce_pair
);
306 gcc_assert (cl
->sorted
== NULL
);
307 pair
->first_element
= p
.first_element
;
308 pair
->second_element
= p
.second_element
;
313 return (struct coalesce_pair
*) *slot
;
317 add_cost_one_coalesce (coalesce_list_p cl
, int p1
, int p2
)
319 cost_one_pair_p pair
;
321 pair
= XNEW (struct cost_one_pair_d
);
322 pair
->first_element
= p1
;
323 pair
->second_element
= p2
;
324 pair
->next
= cl
->cost_one_list
;
325 cl
->cost_one_list
= pair
;
329 /* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */
332 add_coalesce (coalesce_list_p cl
, int p1
, int p2
, int value
)
334 coalesce_pair_p node
;
336 gcc_assert (cl
->sorted
== NULL
);
340 node
= find_coalesce_pair (cl
, p1
, p2
, true);
342 /* Once the value is at least MUST_COALESCE_COST - 1, leave it that way. */
343 if (node
->cost
< MUST_COALESCE_COST
- 1)
345 if (value
< MUST_COALESCE_COST
- 1)
353 /* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */
356 compare_pairs (const void *p1
, const void *p2
)
358 const_coalesce_pair_p
const *const pp1
= (const_coalesce_pair_p
const *) p1
;
359 const_coalesce_pair_p
const *const pp2
= (const_coalesce_pair_p
const *) p2
;
362 result
= (* pp1
)->cost
- (* pp2
)->cost
;
363 /* Since qsort does not guarantee stability we use the elements
364 as a secondary key. This provides us with independence from
365 the host's implementation of the sorting algorithm. */
368 result
= (* pp2
)->first_element
- (* pp1
)->first_element
;
370 result
= (* pp2
)->second_element
- (* pp1
)->second_element
;
377 /* Return the number of unique coalesce pairs in CL. */
380 num_coalesce_pairs (coalesce_list_p cl
)
382 return cl
->list
->elements ();
386 /* Iterate over CL using ITER, returning values in PAIR. */
388 #define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL) \
389 FOR_EACH_HASH_TABLE_ELEMENT (*(CL)->list, (PAIR), coalesce_pair_p, (ITER))
392 /* Prepare CL for removal of preferred pairs. When finished they are sorted
393 in order from most important coalesce to least important. */
396 sort_coalesce_list (coalesce_list_p cl
)
400 coalesce_iterator_type ppi
;
402 gcc_assert (cl
->sorted
== NULL
);
404 num
= num_coalesce_pairs (cl
);
405 cl
->num_sorted
= num
;
409 /* Allocate a vector for the pair pointers. */
410 cl
->sorted
= XNEWVEC (coalesce_pair_p
, num
);
412 /* Populate the vector with pointers to the pairs. */
414 FOR_EACH_PARTITION_PAIR (p
, ppi
, cl
)
416 gcc_assert (x
== num
);
418 /* Already sorted. */
422 /* If there are only 2, just pick swap them if the order isn't correct. */
425 if (cl
->sorted
[0]->cost
> cl
->sorted
[1]->cost
)
426 std::swap (cl
->sorted
[0], cl
->sorted
[1]);
430 /* Only call qsort if there are more than 2 items.
431 ??? Maybe std::sort will do better, provided that compare_pairs
434 qsort (cl
->sorted
, num
, sizeof (coalesce_pair_p
), compare_pairs
);
438 /* Send debug info for coalesce list CL to file F. */
441 dump_coalesce_list (FILE *f
, coalesce_list_p cl
)
443 coalesce_pair_p node
;
444 coalesce_iterator_type ppi
;
449 if (cl
->sorted
== NULL
)
451 fprintf (f
, "Coalesce List:\n");
452 FOR_EACH_PARTITION_PAIR (node
, ppi
, cl
)
454 tree var1
= ssa_name (node
->first_element
);
455 tree var2
= ssa_name (node
->second_element
);
456 print_generic_expr (f
, var1
, TDF_SLIM
);
457 fprintf (f
, " <-> ");
458 print_generic_expr (f
, var2
, TDF_SLIM
);
459 fprintf (f
, " (%1d), ", node
->cost
);
465 fprintf (f
, "Sorted Coalesce list:\n");
466 for (x
= cl
->num_sorted
- 1 ; x
>=0; x
--)
468 node
= cl
->sorted
[x
];
469 fprintf (f
, "(%d) ", node
->cost
);
470 var
= ssa_name (node
->first_element
);
471 print_generic_expr (f
, var
, TDF_SLIM
);
472 fprintf (f
, " <-> ");
473 var
= ssa_name (node
->second_element
);
474 print_generic_expr (f
, var
, TDF_SLIM
);
481 /* This represents a conflict graph. Implemented as an array of bitmaps.
482 A full matrix is used for conflicts rather than just upper triangular form.
483 this make sit much simpler and faster to perform conflict merges. */
485 typedef struct ssa_conflicts_d
487 bitmap_obstack obstack
; /* A place to allocate our bitmaps. */
488 vec
<bitmap
> conflicts
;
491 /* Return an empty new conflict graph for SIZE elements. */
493 static inline ssa_conflicts_p
494 ssa_conflicts_new (unsigned size
)
498 ptr
= XNEW (struct ssa_conflicts_d
);
499 bitmap_obstack_initialize (&ptr
->obstack
);
500 ptr
->conflicts
.create (size
);
501 ptr
->conflicts
.safe_grow_cleared (size
);
506 /* Free storage for conflict graph PTR. */
509 ssa_conflicts_delete (ssa_conflicts_p ptr
)
511 bitmap_obstack_release (&ptr
->obstack
);
512 ptr
->conflicts
.release ();
517 /* Test if elements X and Y conflict in graph PTR. */
520 ssa_conflicts_test_p (ssa_conflicts_p ptr
, unsigned x
, unsigned y
)
522 bitmap bx
= ptr
->conflicts
[x
];
523 bitmap by
= ptr
->conflicts
[y
];
525 gcc_checking_assert (x
!= y
);
528 /* Avoid the lookup if Y has no conflicts. */
529 return by
? bitmap_bit_p (bx
, y
) : false;
535 /* Add a conflict with Y to the bitmap for X in graph PTR. */
538 ssa_conflicts_add_one (ssa_conflicts_p ptr
, unsigned x
, unsigned y
)
540 bitmap bx
= ptr
->conflicts
[x
];
541 /* If there are no conflicts yet, allocate the bitmap and set bit. */
543 bx
= ptr
->conflicts
[x
] = BITMAP_ALLOC (&ptr
->obstack
);
544 bitmap_set_bit (bx
, y
);
548 /* Add conflicts between X and Y in graph PTR. */
551 ssa_conflicts_add (ssa_conflicts_p ptr
, unsigned x
, unsigned y
)
553 gcc_checking_assert (x
!= y
);
554 ssa_conflicts_add_one (ptr
, x
, y
);
555 ssa_conflicts_add_one (ptr
, y
, x
);
559 /* Merge all Y's conflict into X in graph PTR. */
562 ssa_conflicts_merge (ssa_conflicts_p ptr
, unsigned x
, unsigned y
)
566 bitmap bx
= ptr
->conflicts
[x
];
567 bitmap by
= ptr
->conflicts
[y
];
569 gcc_checking_assert (x
!= y
);
573 /* Add a conflict between X and every one Y has. If the bitmap doesn't
574 exist, then it has already been coalesced, and we don't need to add a
576 EXECUTE_IF_SET_IN_BITMAP (by
, 0, z
, bi
)
578 bitmap bz
= ptr
->conflicts
[z
];
580 bitmap_set_bit (bz
, x
);
585 /* If X has conflicts, add Y's to X. */
586 bitmap_ior_into (bx
, by
);
588 ptr
->conflicts
[y
] = NULL
;
592 /* If X has no conflicts, simply use Y's. */
593 ptr
->conflicts
[x
] = by
;
594 ptr
->conflicts
[y
] = NULL
;
599 /* Dump a conflicts graph. */
602 ssa_conflicts_dump (FILE *file
, ssa_conflicts_p ptr
)
607 fprintf (file
, "\nConflict graph:\n");
609 FOR_EACH_VEC_ELT (ptr
->conflicts
, x
, b
)
612 fprintf (file
, "%d: ", x
);
613 dump_bitmap (file
, b
);
618 /* This structure is used to efficiently record the current status of live
619 SSA_NAMES when building a conflict graph.
620 LIVE_BASE_VAR has a bit set for each base variable which has at least one
622 LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an
623 index, and is used to track what partitions of each base variable are
624 live. This makes it easy to add conflicts between just live partitions
625 with the same base variable.
626 The values in LIVE_BASE_PARTITIONS are only valid if the base variable is
627 marked as being live. This delays clearing of these bitmaps until
628 they are actually needed again. */
630 typedef struct live_track_d
632 bitmap_obstack obstack
; /* A place to allocate our bitmaps. */
633 bitmap live_base_var
; /* Indicates if a basevar is live. */
634 bitmap
*live_base_partitions
; /* Live partitions for each basevar. */
635 var_map map
; /* Var_map being used for partition mapping. */
639 /* This routine will create a new live track structure based on the partitions
643 new_live_track (var_map map
)
648 /* Make sure there is a partition view in place. */
649 gcc_assert (map
->partition_to_base_index
!= NULL
);
651 ptr
= (live_track_p
) xmalloc (sizeof (struct live_track_d
));
653 lim
= num_basevars (map
);
654 bitmap_obstack_initialize (&ptr
->obstack
);
655 ptr
->live_base_partitions
= (bitmap
*) xmalloc (sizeof (bitmap
*) * lim
);
656 ptr
->live_base_var
= BITMAP_ALLOC (&ptr
->obstack
);
657 for (x
= 0; x
< lim
; x
++)
658 ptr
->live_base_partitions
[x
] = BITMAP_ALLOC (&ptr
->obstack
);
663 /* This routine will free the memory associated with PTR. */
666 delete_live_track (live_track_p ptr
)
668 bitmap_obstack_release (&ptr
->obstack
);
669 free (ptr
->live_base_partitions
);
674 /* This function will remove PARTITION from the live list in PTR. */
677 live_track_remove_partition (live_track_p ptr
, int partition
)
681 root
= basevar_index (ptr
->map
, partition
);
682 bitmap_clear_bit (ptr
->live_base_partitions
[root
], partition
);
683 /* If the element list is empty, make the base variable not live either. */
684 if (bitmap_empty_p (ptr
->live_base_partitions
[root
]))
685 bitmap_clear_bit (ptr
->live_base_var
, root
);
689 /* This function will adds PARTITION to the live list in PTR. */
692 live_track_add_partition (live_track_p ptr
, int partition
)
696 root
= basevar_index (ptr
->map
, partition
);
697 /* If this base var wasn't live before, it is now. Clear the element list
698 since it was delayed until needed. */
699 if (bitmap_set_bit (ptr
->live_base_var
, root
))
700 bitmap_clear (ptr
->live_base_partitions
[root
]);
701 bitmap_set_bit (ptr
->live_base_partitions
[root
], partition
);
706 /* Clear the live bit for VAR in PTR. */
709 live_track_clear_var (live_track_p ptr
, tree var
)
713 p
= var_to_partition (ptr
->map
, var
);
714 if (p
!= NO_PARTITION
)
715 live_track_remove_partition (ptr
, p
);
719 /* Return TRUE if VAR is live in PTR. */
722 live_track_live_p (live_track_p ptr
, tree var
)
726 p
= var_to_partition (ptr
->map
, var
);
727 if (p
!= NO_PARTITION
)
729 root
= basevar_index (ptr
->map
, p
);
730 if (bitmap_bit_p (ptr
->live_base_var
, root
))
731 return bitmap_bit_p (ptr
->live_base_partitions
[root
], p
);
737 /* This routine will add USE to PTR. USE will be marked as live in both the
738 ssa live map and the live bitmap for the root of USE. */
741 live_track_process_use (live_track_p ptr
, tree use
)
745 p
= var_to_partition (ptr
->map
, use
);
746 if (p
== NO_PARTITION
)
749 /* Mark as live in the appropriate live list. */
750 live_track_add_partition (ptr
, p
);
754 /* This routine will process a DEF in PTR. DEF will be removed from the live
755 lists, and if there are any other live partitions with the same base
756 variable, conflicts will be added to GRAPH. */
759 live_track_process_def (live_track_p ptr
, tree def
, ssa_conflicts_p graph
)
766 p
= var_to_partition (ptr
->map
, def
);
767 if (p
== NO_PARTITION
)
770 /* Clear the liveness bit. */
771 live_track_remove_partition (ptr
, p
);
773 /* If the bitmap isn't empty now, conflicts need to be added. */
774 root
= basevar_index (ptr
->map
, p
);
775 if (bitmap_bit_p (ptr
->live_base_var
, root
))
777 b
= ptr
->live_base_partitions
[root
];
778 EXECUTE_IF_SET_IN_BITMAP (b
, 0, x
, bi
)
779 ssa_conflicts_add (graph
, p
, x
);
784 /* Initialize PTR with the partitions set in INIT. */
787 live_track_init (live_track_p ptr
, bitmap init
)
792 /* Mark all live on exit partitions. */
793 EXECUTE_IF_SET_IN_BITMAP (init
, 0, p
, bi
)
794 live_track_add_partition (ptr
, p
);
798 /* This routine will clear all live partitions in PTR. */
801 live_track_clear_base_vars (live_track_p ptr
)
803 /* Simply clear the live base list. Anything marked as live in the element
804 lists will be cleared later if/when the base variable ever comes alive
806 bitmap_clear (ptr
->live_base_var
);
810 /* Build a conflict graph based on LIVEINFO. Any partitions which are in the
811 partition view of the var_map liveinfo is based on get entries in the
812 conflict graph. Only conflicts between ssa_name partitions with the same
813 base variable are added. */
815 static ssa_conflicts_p
816 build_ssa_conflict_graph (tree_live_info_p liveinfo
)
818 ssa_conflicts_p graph
;
824 map
= live_var_map (liveinfo
);
825 graph
= ssa_conflicts_new (num_var_partitions (map
));
827 live
= new_live_track (map
);
829 FOR_EACH_BB_FN (bb
, cfun
)
831 /* Start with live on exit temporaries. */
832 live_track_init (live
, live_on_exit (liveinfo
, bb
));
834 for (gimple_stmt_iterator gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
);
838 gimple stmt
= gsi_stmt (gsi
);
840 /* A copy between 2 partitions does not introduce an interference
841 by itself. If they did, you would never be able to coalesce
842 two things which are copied. If the two variables really do
843 conflict, they will conflict elsewhere in the program.
845 This is handled by simply removing the SRC of the copy from the
846 live list, and processing the stmt normally. */
847 if (is_gimple_assign (stmt
))
849 tree lhs
= gimple_assign_lhs (stmt
);
850 tree rhs1
= gimple_assign_rhs1 (stmt
);
851 if (gimple_assign_copy_p (stmt
)
852 && TREE_CODE (lhs
) == SSA_NAME
853 && TREE_CODE (rhs1
) == SSA_NAME
)
854 live_track_clear_var (live
, rhs1
);
856 else if (is_gimple_debug (stmt
))
859 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_DEF
)
860 live_track_process_def (live
, var
, graph
);
862 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_USE
)
863 live_track_process_use (live
, var
);
866 /* If result of a PHI is unused, looping over the statements will not
867 record any conflicts since the def was never live. Since the PHI node
868 is going to be translated out of SSA form, it will insert a copy.
869 There must be a conflict recorded between the result of the PHI and
870 any variables that are live. Otherwise the out-of-ssa translation
871 may create incorrect code. */
872 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
875 gphi
*phi
= gsi
.phi ();
876 tree result
= PHI_RESULT (phi
);
877 if (live_track_live_p (live
, result
))
878 live_track_process_def (live
, result
, graph
);
881 live_track_clear_base_vars (live
);
884 delete_live_track (live
);
889 /* Shortcut routine to print messages to file F of the form:
890 "STR1 EXPR1 STR2 EXPR2 STR3." */
893 print_exprs (FILE *f
, const char *str1
, tree expr1
, const char *str2
,
894 tree expr2
, const char *str3
)
896 fprintf (f
, "%s", str1
);
897 print_generic_expr (f
, expr1
, TDF_SLIM
);
898 fprintf (f
, "%s", str2
);
899 print_generic_expr (f
, expr2
, TDF_SLIM
);
900 fprintf (f
, "%s", str3
);
904 /* Print a failure to coalesce a MUST_COALESCE pair X and Y. */
907 fail_abnormal_edge_coalesce (int x
, int y
)
909 fprintf (stderr
, "\nUnable to coalesce ssa_names %d and %d",x
, y
);
910 fprintf (stderr
, " which are marked as MUST COALESCE.\n");
911 print_generic_expr (stderr
, ssa_name (x
), TDF_SLIM
);
912 fprintf (stderr
, " and ");
913 print_generic_stmt (stderr
, ssa_name (y
), TDF_SLIM
);
915 internal_error ("SSA corruption");
919 /* This function creates a var_map for the current function as well as creating
920 a coalesce list for use later in the out of ssa process. */
923 create_outofssa_var_map (coalesce_list_p cl
, bitmap used_in_copy
)
925 gimple_stmt_iterator gsi
;
935 map
= init_var_map (num_ssa_names
);
937 FOR_EACH_BB_FN (bb
, cfun
)
941 for (gphi_iterator gpi
= gsi_start_phis (bb
);
945 gphi
*phi
= gpi
.phi ();
949 bool saw_copy
= false;
951 res
= gimple_phi_result (phi
);
952 ver
= SSA_NAME_VERSION (res
);
953 register_ssa_partition (map
, res
);
955 /* Register ssa_names and coalesces between the args and the result
957 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
959 edge e
= gimple_phi_arg_edge (phi
, i
);
960 arg
= PHI_ARG_DEF (phi
, i
);
961 if (TREE_CODE (arg
) != SSA_NAME
)
964 register_ssa_partition (map
, arg
);
965 if (gimple_can_coalesce_p (arg
, res
)
966 || (e
->flags
& EDGE_ABNORMAL
))
969 bitmap_set_bit (used_in_copy
, SSA_NAME_VERSION (arg
));
970 if ((e
->flags
& EDGE_ABNORMAL
) == 0)
972 int cost
= coalesce_cost_edge (e
);
973 if (cost
== 1 && has_single_use (arg
))
974 add_cost_one_coalesce (cl
, ver
, SSA_NAME_VERSION (arg
));
976 add_coalesce (cl
, ver
, SSA_NAME_VERSION (arg
), cost
);
981 bitmap_set_bit (used_in_copy
, ver
);
984 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
986 stmt
= gsi_stmt (gsi
);
988 if (is_gimple_debug (stmt
))
991 /* Register USE and DEF operands in each statement. */
992 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, (SSA_OP_DEF
|SSA_OP_USE
))
993 register_ssa_partition (map
, var
);
995 /* Check for copy coalesces. */
996 switch (gimple_code (stmt
))
1000 tree lhs
= gimple_assign_lhs (stmt
);
1001 tree rhs1
= gimple_assign_rhs1 (stmt
);
1002 if (gimple_assign_ssa_name_copy_p (stmt
)
1003 && gimple_can_coalesce_p (lhs
, rhs1
))
1005 v1
= SSA_NAME_VERSION (lhs
);
1006 v2
= SSA_NAME_VERSION (rhs1
);
1007 cost
= coalesce_cost_bb (bb
);
1008 add_coalesce (cl
, v1
, v2
, cost
);
1009 bitmap_set_bit (used_in_copy
, v1
);
1010 bitmap_set_bit (used_in_copy
, v2
);
1017 gasm
*asm_stmt
= as_a
<gasm
*> (stmt
);
1018 unsigned long noutputs
, i
;
1019 unsigned long ninputs
;
1020 tree
*outputs
, link
;
1021 noutputs
= gimple_asm_noutputs (asm_stmt
);
1022 ninputs
= gimple_asm_ninputs (asm_stmt
);
1023 outputs
= (tree
*) alloca (noutputs
* sizeof (tree
));
1024 for (i
= 0; i
< noutputs
; ++i
)
1026 link
= gimple_asm_output_op (asm_stmt
, i
);
1027 outputs
[i
] = TREE_VALUE (link
);
1030 for (i
= 0; i
< ninputs
; ++i
)
1032 const char *constraint
;
1035 unsigned long match
;
1037 link
= gimple_asm_input_op (asm_stmt
, i
);
1039 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
1040 input
= TREE_VALUE (link
);
1042 if (TREE_CODE (input
) != SSA_NAME
)
1045 match
= strtoul (constraint
, &end
, 10);
1046 if (match
>= noutputs
|| end
== constraint
)
1049 if (TREE_CODE (outputs
[match
]) != SSA_NAME
)
1052 v1
= SSA_NAME_VERSION (outputs
[match
]);
1053 v2
= SSA_NAME_VERSION (input
);
1055 if (gimple_can_coalesce_p (outputs
[match
], input
))
1057 cost
= coalesce_cost (REG_BR_PROB_BASE
,
1058 optimize_bb_for_size_p (bb
));
1059 add_coalesce (cl
, v1
, v2
, cost
);
1060 bitmap_set_bit (used_in_copy
, v1
);
1061 bitmap_set_bit (used_in_copy
, v2
);
1073 /* Now process result decls and live on entry variables for entry into
1074 the coalesce list. */
1076 for (i
= 1; i
< num_ssa_names
; i
++)
1079 if (var
!= NULL_TREE
&& !virtual_operand_p (var
))
1081 /* Add coalesces between all the result decls. */
1082 if (SSA_NAME_VAR (var
)
1083 && TREE_CODE (SSA_NAME_VAR (var
)) == RESULT_DECL
)
1085 if (first
== NULL_TREE
)
1089 gcc_assert (gimple_can_coalesce_p (var
, first
));
1090 v1
= SSA_NAME_VERSION (first
);
1091 v2
= SSA_NAME_VERSION (var
);
1092 bitmap_set_bit (used_in_copy
, v1
);
1093 bitmap_set_bit (used_in_copy
, v2
);
1094 cost
= coalesce_cost_bb (EXIT_BLOCK_PTR_FOR_FN (cfun
));
1095 add_coalesce (cl
, v1
, v2
, cost
);
1098 /* Mark any default_def variables as being in the coalesce list
1099 since they will have to be coalesced with the base variable. If
1100 not marked as present, they won't be in the coalesce view. */
1101 if (SSA_NAME_IS_DEFAULT_DEF (var
)
1102 && !has_zero_uses (var
))
1103 bitmap_set_bit (used_in_copy
, SSA_NAME_VERSION (var
));
1111 /* Attempt to coalesce ssa versions X and Y together using the partition
1112 mapping in MAP and checking conflicts in GRAPH. Output any debug info to
1113 DEBUG, if it is nun-NULL. */
1116 attempt_coalesce (var_map map
, ssa_conflicts_p graph
, int x
, int y
,
1123 p1
= var_to_partition (map
, ssa_name (x
));
1124 p2
= var_to_partition (map
, ssa_name (y
));
1128 fprintf (debug
, "(%d)", x
);
1129 print_generic_expr (debug
, partition_to_var (map
, p1
), TDF_SLIM
);
1130 fprintf (debug
, " & (%d)", y
);
1131 print_generic_expr (debug
, partition_to_var (map
, p2
), TDF_SLIM
);
1137 fprintf (debug
, ": Already Coalesced.\n");
1142 fprintf (debug
, " [map: %d, %d] ", p1
, p2
);
1145 if (!ssa_conflicts_test_p (graph
, p1
, p2
))
1147 var1
= partition_to_var (map
, p1
);
1148 var2
= partition_to_var (map
, p2
);
1149 z
= var_union (map
, var1
, var2
);
1150 if (z
== NO_PARTITION
)
1153 fprintf (debug
, ": Unable to perform partition union.\n");
1157 /* z is the new combined partition. Remove the other partition from
1158 the list, and merge the conflicts. */
1160 ssa_conflicts_merge (graph
, p1
, p2
);
1162 ssa_conflicts_merge (graph
, p2
, p1
);
1165 fprintf (debug
, ": Success -> %d\n", z
);
1170 fprintf (debug
, ": Fail due to conflict\n");
1176 /* Attempt to Coalesce partitions in MAP which occur in the list CL using
1177 GRAPH. Debug output is sent to DEBUG if it is non-NULL. */
1180 coalesce_partitions (var_map map
, ssa_conflicts_p graph
, coalesce_list_p cl
,
1190 /* First, coalesce all the copies across abnormal edges. These are not placed
1191 in the coalesce list because they do not need to be sorted, and simply
1192 consume extra memory/compilation time in large programs. */
1194 FOR_EACH_BB_FN (bb
, cfun
)
1196 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1197 if (e
->flags
& EDGE_ABNORMAL
)
1200 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1203 gphi
*phi
= gsi
.phi ();
1204 tree arg
= PHI_ARG_DEF (phi
, e
->dest_idx
);
1205 if (SSA_NAME_IS_DEFAULT_DEF (arg
)
1206 && (!SSA_NAME_VAR (arg
)
1207 || TREE_CODE (SSA_NAME_VAR (arg
)) != PARM_DECL
))
1210 tree res
= PHI_RESULT (phi
);
1211 int v1
= SSA_NAME_VERSION (res
);
1212 int v2
= SSA_NAME_VERSION (arg
);
1215 fprintf (debug
, "Abnormal coalesce: ");
1217 if (!attempt_coalesce (map
, graph
, v1
, v2
, debug
))
1218 fail_abnormal_edge_coalesce (v1
, v2
);
1223 /* Now process the items in the coalesce list. */
1225 while ((cost
= pop_best_coalesce (cl
, &x
, &y
)) != NO_BEST_COALESCE
)
1227 var1
= ssa_name (x
);
1228 var2
= ssa_name (y
);
1230 /* Assert the coalesces have the same base variable. */
1231 gcc_assert (gimple_can_coalesce_p (var1
, var2
));
1234 fprintf (debug
, "Coalesce list: ");
1235 attempt_coalesce (map
, graph
, x
, y
, debug
);
1240 /* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */
1242 struct ssa_name_var_hash
: typed_noop_remove
<tree_node
>
1244 typedef union tree_node
*value_type
;
1245 typedef union tree_node
*compare_type
;
1246 static inline hashval_t
hash (const tree_node
*);
1247 static inline int equal (const tree_node
*, const tree_node
*);
1251 ssa_name_var_hash::hash (const_tree n
)
1253 return DECL_UID (SSA_NAME_VAR (n
));
1257 ssa_name_var_hash::equal (const tree_node
*n1
, const tree_node
*n2
)
1259 return SSA_NAME_VAR (n1
) == SSA_NAME_VAR (n2
);
1263 /* Reduce the number of copies by coalescing variables in the function. Return
1264 a partition map with the resulting coalesces. */
1267 coalesce_ssa_name (void)
1269 tree_live_info_p liveinfo
;
1270 ssa_conflicts_p graph
;
1272 bitmap used_in_copies
= BITMAP_ALLOC (NULL
);
1276 cl
= create_coalesce_list ();
1277 map
= create_outofssa_var_map (cl
, used_in_copies
);
1279 /* If optimization is disabled, we need to coalesce all the names originating
1280 from the same SSA_NAME_VAR so debug info remains undisturbed. */
1283 hash_table
<ssa_name_var_hash
> ssa_name_hash (10);
1285 for (i
= 1; i
< num_ssa_names
; i
++)
1287 tree a
= ssa_name (i
);
1291 && !DECL_IGNORED_P (SSA_NAME_VAR (a
))
1292 && (!has_zero_uses (a
) || !SSA_NAME_IS_DEFAULT_DEF (a
)))
1294 tree
*slot
= ssa_name_hash
.find_slot (a
, INSERT
);
1300 /* If the variable is a PARM_DECL or a RESULT_DECL, we
1301 _require_ that all the names originating from it be
1302 coalesced, because there must be a single partition
1303 containing all the names so that it can be assigned
1304 the canonical RTL location of the DECL safely.
1305 If in_lto_p, a function could have been compiled
1306 originally with optimizations and only the link
1307 performed at -O0, so we can't actually require it. */
1309 = (TREE_CODE (SSA_NAME_VAR (a
)) == VAR_DECL
|| in_lto_p
)
1310 ? MUST_COALESCE_COST
- 1 : MUST_COALESCE_COST
;
1311 add_coalesce (cl
, SSA_NAME_VERSION (a
),
1312 SSA_NAME_VERSION (*slot
), cost
);
1313 bitmap_set_bit (used_in_copies
, SSA_NAME_VERSION (a
));
1314 bitmap_set_bit (used_in_copies
, SSA_NAME_VERSION (*slot
));
1319 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1320 dump_var_map (dump_file
, map
);
1322 /* Don't calculate live ranges for variables not in the coalesce list. */
1323 partition_view_bitmap (map
, used_in_copies
, true);
1324 BITMAP_FREE (used_in_copies
);
1326 if (num_var_partitions (map
) < 1)
1328 delete_coalesce_list (cl
);
1332 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1333 dump_var_map (dump_file
, map
);
1335 liveinfo
= calculate_live_ranges (map
, false);
1337 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1338 dump_live_info (dump_file
, liveinfo
, LIVEDUMP_ENTRY
);
1340 /* Build a conflict graph. */
1341 graph
= build_ssa_conflict_graph (liveinfo
);
1342 delete_tree_live_info (liveinfo
);
1343 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1344 ssa_conflicts_dump (dump_file
, graph
);
1346 sort_coalesce_list (cl
);
1348 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1350 fprintf (dump_file
, "\nAfter sorting:\n");
1351 dump_coalesce_list (dump_file
, cl
);
1354 /* First, coalesce all live on entry variables to their base variable.
1355 This will ensure the first use is coming from the correct location. */
1357 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1358 dump_var_map (dump_file
, map
);
1360 /* Now coalesce everything in the list. */
1361 coalesce_partitions (map
, graph
, cl
,
1362 ((dump_flags
& TDF_DETAILS
) ? dump_file
1365 delete_coalesce_list (cl
);
1366 ssa_conflicts_delete (graph
);