1*e4b17023SJohn Marino /* Coalesce SSA_NAMES together for the out-of-ssa pass.
2*e4b17023SJohn Marino Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
3*e4b17023SJohn Marino Free Software Foundation, Inc.
4*e4b17023SJohn Marino Contributed by Andrew MacLeod <amacleod@redhat.com>
5*e4b17023SJohn Marino
6*e4b17023SJohn Marino This file is part of GCC.
7*e4b17023SJohn Marino
8*e4b17023SJohn Marino GCC is free software; you can redistribute it and/or modify
9*e4b17023SJohn Marino it under the terms of the GNU General Public License as published by
10*e4b17023SJohn Marino the Free Software Foundation; either version 3, or (at your option)
11*e4b17023SJohn Marino any later version.
12*e4b17023SJohn Marino
13*e4b17023SJohn Marino GCC is distributed in the hope that it will be useful,
14*e4b17023SJohn Marino but WITHOUT ANY WARRANTY; without even the implied warranty of
15*e4b17023SJohn Marino MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16*e4b17023SJohn Marino GNU General Public License for more details.
17*e4b17023SJohn Marino
18*e4b17023SJohn Marino You should have received a copy of the GNU General Public License
19*e4b17023SJohn Marino along with GCC; see the file COPYING3. If not see
20*e4b17023SJohn Marino <http://www.gnu.org/licenses/>. */
21*e4b17023SJohn Marino
22*e4b17023SJohn Marino #include "config.h"
23*e4b17023SJohn Marino #include "system.h"
24*e4b17023SJohn Marino #include "coretypes.h"
25*e4b17023SJohn Marino #include "tm.h"
26*e4b17023SJohn Marino #include "tree.h"
27*e4b17023SJohn Marino #include "flags.h"
28*e4b17023SJohn Marino #include "tree-pretty-print.h"
29*e4b17023SJohn Marino #include "bitmap.h"
30*e4b17023SJohn Marino #include "tree-flow.h"
31*e4b17023SJohn Marino #include "hashtab.h"
32*e4b17023SJohn Marino #include "tree-dump.h"
33*e4b17023SJohn Marino #include "tree-ssa-live.h"
34*e4b17023SJohn Marino #include "diagnostic-core.h"
35*e4b17023SJohn Marino
36*e4b17023SJohn Marino
37*e4b17023SJohn Marino /* This set of routines implements a coalesce_list. This is an object which
38*e4b17023SJohn Marino is used to track pairs of ssa_names which are desirable to coalesce
39*e4b17023SJohn Marino together to avoid copies. Costs are associated with each pair, and when
40*e4b17023SJohn Marino all desired information has been collected, the object can be used to
41*e4b17023SJohn Marino order the pairs for processing. */
42*e4b17023SJohn Marino
43*e4b17023SJohn Marino /* This structure defines a pair entry. */
44*e4b17023SJohn Marino
45*e4b17023SJohn Marino typedef struct coalesce_pair
46*e4b17023SJohn Marino {
47*e4b17023SJohn Marino int first_element;
48*e4b17023SJohn Marino int second_element;
49*e4b17023SJohn Marino int cost;
50*e4b17023SJohn Marino } * coalesce_pair_p;
51*e4b17023SJohn Marino typedef const struct coalesce_pair *const_coalesce_pair_p;
52*e4b17023SJohn Marino
53*e4b17023SJohn Marino typedef struct cost_one_pair_d
54*e4b17023SJohn Marino {
55*e4b17023SJohn Marino int first_element;
56*e4b17023SJohn Marino int second_element;
57*e4b17023SJohn Marino struct cost_one_pair_d *next;
58*e4b17023SJohn Marino } * cost_one_pair_p;
59*e4b17023SJohn Marino
60*e4b17023SJohn Marino /* This structure maintains the list of coalesce pairs. */
61*e4b17023SJohn Marino
62*e4b17023SJohn Marino typedef struct coalesce_list_d
63*e4b17023SJohn Marino {
64*e4b17023SJohn Marino htab_t list; /* Hash table. */
65*e4b17023SJohn Marino coalesce_pair_p *sorted; /* List when sorted. */
66*e4b17023SJohn Marino int num_sorted; /* Number in the sorted list. */
67*e4b17023SJohn Marino cost_one_pair_p cost_one_list;/* Single use coalesces with cost 1. */
68*e4b17023SJohn Marino } *coalesce_list_p;
69*e4b17023SJohn Marino
70*e4b17023SJohn Marino #define NO_BEST_COALESCE -1
71*e4b17023SJohn Marino #define MUST_COALESCE_COST INT_MAX
72*e4b17023SJohn Marino
73*e4b17023SJohn Marino
74*e4b17023SJohn Marino /* Return cost of execution of copy instruction with FREQUENCY. */
75*e4b17023SJohn Marino
76*e4b17023SJohn Marino static inline int
coalesce_cost(int frequency,bool optimize_for_size)77*e4b17023SJohn Marino coalesce_cost (int frequency, bool optimize_for_size)
78*e4b17023SJohn Marino {
79*e4b17023SJohn Marino /* Base costs on BB frequencies bounded by 1. */
80*e4b17023SJohn Marino int cost = frequency;
81*e4b17023SJohn Marino
82*e4b17023SJohn Marino if (!cost)
83*e4b17023SJohn Marino cost = 1;
84*e4b17023SJohn Marino
85*e4b17023SJohn Marino if (optimize_for_size)
86*e4b17023SJohn Marino cost = 1;
87*e4b17023SJohn Marino
88*e4b17023SJohn Marino return cost;
89*e4b17023SJohn Marino }
90*e4b17023SJohn Marino
91*e4b17023SJohn Marino
92*e4b17023SJohn Marino /* Return the cost of executing a copy instruction in basic block BB. */
93*e4b17023SJohn Marino
94*e4b17023SJohn Marino static inline int
coalesce_cost_bb(basic_block bb)95*e4b17023SJohn Marino coalesce_cost_bb (basic_block bb)
96*e4b17023SJohn Marino {
97*e4b17023SJohn Marino return coalesce_cost (bb->frequency, optimize_bb_for_size_p (bb));
98*e4b17023SJohn Marino }
99*e4b17023SJohn Marino
100*e4b17023SJohn Marino
101*e4b17023SJohn Marino /* Return the cost of executing a copy instruction on edge E. */
102*e4b17023SJohn Marino
103*e4b17023SJohn Marino static inline int
coalesce_cost_edge(edge e)104*e4b17023SJohn Marino coalesce_cost_edge (edge e)
105*e4b17023SJohn Marino {
106*e4b17023SJohn Marino int mult = 1;
107*e4b17023SJohn Marino
108*e4b17023SJohn Marino /* Inserting copy on critical edge costs more than inserting it elsewhere. */
109*e4b17023SJohn Marino if (EDGE_CRITICAL_P (e))
110*e4b17023SJohn Marino mult = 2;
111*e4b17023SJohn Marino if (e->flags & EDGE_ABNORMAL)
112*e4b17023SJohn Marino return MUST_COALESCE_COST;
113*e4b17023SJohn Marino if (e->flags & EDGE_EH)
114*e4b17023SJohn Marino {
115*e4b17023SJohn Marino edge e2;
116*e4b17023SJohn Marino edge_iterator ei;
117*e4b17023SJohn Marino FOR_EACH_EDGE (e2, ei, e->dest->preds)
118*e4b17023SJohn Marino if (e2 != e)
119*e4b17023SJohn Marino {
120*e4b17023SJohn Marino /* Putting code on EH edge that leads to BB
121*e4b17023SJohn Marino with multiple predecestors imply splitting of
122*e4b17023SJohn Marino edge too. */
123*e4b17023SJohn Marino if (mult < 2)
124*e4b17023SJohn Marino mult = 2;
125*e4b17023SJohn Marino /* If there are multiple EH predecestors, we
126*e4b17023SJohn Marino also copy EH regions and produce separate
127*e4b17023SJohn Marino landing pad. This is expensive. */
128*e4b17023SJohn Marino if (e2->flags & EDGE_EH)
129*e4b17023SJohn Marino {
130*e4b17023SJohn Marino mult = 5;
131*e4b17023SJohn Marino break;
132*e4b17023SJohn Marino }
133*e4b17023SJohn Marino }
134*e4b17023SJohn Marino }
135*e4b17023SJohn Marino
136*e4b17023SJohn Marino return coalesce_cost (EDGE_FREQUENCY (e),
137*e4b17023SJohn Marino optimize_edge_for_size_p (e)) * mult;
138*e4b17023SJohn Marino }
139*e4b17023SJohn Marino
140*e4b17023SJohn Marino
141*e4b17023SJohn Marino /* Retrieve a pair to coalesce from the cost_one_list in CL. Returns the
142*e4b17023SJohn Marino 2 elements via P1 and P2. 1 is returned by the function if there is a pair,
143*e4b17023SJohn Marino NO_BEST_COALESCE is returned if there aren't any. */
144*e4b17023SJohn Marino
145*e4b17023SJohn Marino static inline int
pop_cost_one_pair(coalesce_list_p cl,int * p1,int * p2)146*e4b17023SJohn Marino pop_cost_one_pair (coalesce_list_p cl, int *p1, int *p2)
147*e4b17023SJohn Marino {
148*e4b17023SJohn Marino cost_one_pair_p ptr;
149*e4b17023SJohn Marino
150*e4b17023SJohn Marino ptr = cl->cost_one_list;
151*e4b17023SJohn Marino if (!ptr)
152*e4b17023SJohn Marino return NO_BEST_COALESCE;
153*e4b17023SJohn Marino
154*e4b17023SJohn Marino *p1 = ptr->first_element;
155*e4b17023SJohn Marino *p2 = ptr->second_element;
156*e4b17023SJohn Marino cl->cost_one_list = ptr->next;
157*e4b17023SJohn Marino
158*e4b17023SJohn Marino free (ptr);
159*e4b17023SJohn Marino
160*e4b17023SJohn Marino return 1;
161*e4b17023SJohn Marino }
162*e4b17023SJohn Marino
163*e4b17023SJohn Marino /* Retrieve the most expensive remaining pair to coalesce from CL. Returns the
164*e4b17023SJohn Marino 2 elements via P1 and P2. Their calculated cost is returned by the function.
165*e4b17023SJohn Marino NO_BEST_COALESCE is returned if the coalesce list is empty. */
166*e4b17023SJohn Marino
167*e4b17023SJohn Marino static inline int
pop_best_coalesce(coalesce_list_p cl,int * p1,int * p2)168*e4b17023SJohn Marino pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
169*e4b17023SJohn Marino {
170*e4b17023SJohn Marino coalesce_pair_p node;
171*e4b17023SJohn Marino int ret;
172*e4b17023SJohn Marino
173*e4b17023SJohn Marino if (cl->sorted == NULL)
174*e4b17023SJohn Marino return pop_cost_one_pair (cl, p1, p2);
175*e4b17023SJohn Marino
176*e4b17023SJohn Marino if (cl->num_sorted == 0)
177*e4b17023SJohn Marino return pop_cost_one_pair (cl, p1, p2);
178*e4b17023SJohn Marino
179*e4b17023SJohn Marino node = cl->sorted[--(cl->num_sorted)];
180*e4b17023SJohn Marino *p1 = node->first_element;
181*e4b17023SJohn Marino *p2 = node->second_element;
182*e4b17023SJohn Marino ret = node->cost;
183*e4b17023SJohn Marino free (node);
184*e4b17023SJohn Marino
185*e4b17023SJohn Marino return ret;
186*e4b17023SJohn Marino }
187*e4b17023SJohn Marino
188*e4b17023SJohn Marino
189*e4b17023SJohn Marino #define COALESCE_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1))
190*e4b17023SJohn Marino
191*e4b17023SJohn Marino /* Hash function for coalesce list. Calculate hash for PAIR. */
192*e4b17023SJohn Marino
193*e4b17023SJohn Marino static unsigned int
coalesce_pair_map_hash(const void * pair)194*e4b17023SJohn Marino coalesce_pair_map_hash (const void *pair)
195*e4b17023SJohn Marino {
196*e4b17023SJohn Marino hashval_t a = (hashval_t)(((const_coalesce_pair_p)pair)->first_element);
197*e4b17023SJohn Marino hashval_t b = (hashval_t)(((const_coalesce_pair_p)pair)->second_element);
198*e4b17023SJohn Marino
199*e4b17023SJohn Marino return COALESCE_HASH_FN (a,b);
200*e4b17023SJohn Marino }
201*e4b17023SJohn Marino
202*e4b17023SJohn Marino
203*e4b17023SJohn Marino /* Equality function for coalesce list hash table. Compare PAIR1 and PAIR2,
204*e4b17023SJohn Marino returning TRUE if the two pairs are equivalent. */
205*e4b17023SJohn Marino
206*e4b17023SJohn Marino static int
coalesce_pair_map_eq(const void * pair1,const void * pair2)207*e4b17023SJohn Marino coalesce_pair_map_eq (const void *pair1, const void *pair2)
208*e4b17023SJohn Marino {
209*e4b17023SJohn Marino const_coalesce_pair_p const p1 = (const_coalesce_pair_p) pair1;
210*e4b17023SJohn Marino const_coalesce_pair_p const p2 = (const_coalesce_pair_p) pair2;
211*e4b17023SJohn Marino
212*e4b17023SJohn Marino return (p1->first_element == p2->first_element
213*e4b17023SJohn Marino && p1->second_element == p2->second_element);
214*e4b17023SJohn Marino }
215*e4b17023SJohn Marino
216*e4b17023SJohn Marino
217*e4b17023SJohn Marino /* Create a new empty coalesce list object and return it. */
218*e4b17023SJohn Marino
219*e4b17023SJohn Marino static inline coalesce_list_p
create_coalesce_list(void)220*e4b17023SJohn Marino create_coalesce_list (void)
221*e4b17023SJohn Marino {
222*e4b17023SJohn Marino coalesce_list_p list;
223*e4b17023SJohn Marino unsigned size = num_ssa_names * 3;
224*e4b17023SJohn Marino
225*e4b17023SJohn Marino if (size < 40)
226*e4b17023SJohn Marino size = 40;
227*e4b17023SJohn Marino
228*e4b17023SJohn Marino list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
229*e4b17023SJohn Marino list->list = htab_create (size, coalesce_pair_map_hash,
230*e4b17023SJohn Marino coalesce_pair_map_eq, NULL);
231*e4b17023SJohn Marino list->sorted = NULL;
232*e4b17023SJohn Marino list->num_sorted = 0;
233*e4b17023SJohn Marino list->cost_one_list = NULL;
234*e4b17023SJohn Marino return list;
235*e4b17023SJohn Marino }
236*e4b17023SJohn Marino
237*e4b17023SJohn Marino
238*e4b17023SJohn Marino /* Delete coalesce list CL. */
239*e4b17023SJohn Marino
240*e4b17023SJohn Marino static inline void
delete_coalesce_list(coalesce_list_p cl)241*e4b17023SJohn Marino delete_coalesce_list (coalesce_list_p cl)
242*e4b17023SJohn Marino {
243*e4b17023SJohn Marino gcc_assert (cl->cost_one_list == NULL);
244*e4b17023SJohn Marino htab_delete (cl->list);
245*e4b17023SJohn Marino free (cl->sorted);
246*e4b17023SJohn Marino gcc_assert (cl->num_sorted == 0);
247*e4b17023SJohn Marino free (cl);
248*e4b17023SJohn Marino }
249*e4b17023SJohn Marino
250*e4b17023SJohn Marino
251*e4b17023SJohn Marino /* Find a matching coalesce pair object in CL for the pair P1 and P2. If
252*e4b17023SJohn Marino one isn't found, return NULL if CREATE is false, otherwise create a new
253*e4b17023SJohn Marino coalesce pair object and return it. */
254*e4b17023SJohn Marino
255*e4b17023SJohn Marino static coalesce_pair_p
find_coalesce_pair(coalesce_list_p cl,int p1,int p2,bool create)256*e4b17023SJohn Marino find_coalesce_pair (coalesce_list_p cl, int p1, int p2, bool create)
257*e4b17023SJohn Marino {
258*e4b17023SJohn Marino struct coalesce_pair p;
259*e4b17023SJohn Marino void **slot;
260*e4b17023SJohn Marino unsigned int hash;
261*e4b17023SJohn Marino
262*e4b17023SJohn Marino /* Normalize so that p1 is the smaller value. */
263*e4b17023SJohn Marino if (p2 < p1)
264*e4b17023SJohn Marino {
265*e4b17023SJohn Marino p.first_element = p2;
266*e4b17023SJohn Marino p.second_element = p1;
267*e4b17023SJohn Marino }
268*e4b17023SJohn Marino else
269*e4b17023SJohn Marino {
270*e4b17023SJohn Marino p.first_element = p1;
271*e4b17023SJohn Marino p.second_element = p2;
272*e4b17023SJohn Marino }
273*e4b17023SJohn Marino
274*e4b17023SJohn Marino hash = coalesce_pair_map_hash (&p);
275*e4b17023SJohn Marino slot = htab_find_slot_with_hash (cl->list, &p, hash,
276*e4b17023SJohn Marino create ? INSERT : NO_INSERT);
277*e4b17023SJohn Marino if (!slot)
278*e4b17023SJohn Marino return NULL;
279*e4b17023SJohn Marino
280*e4b17023SJohn Marino if (!*slot)
281*e4b17023SJohn Marino {
282*e4b17023SJohn Marino struct coalesce_pair * pair = XNEW (struct coalesce_pair);
283*e4b17023SJohn Marino gcc_assert (cl->sorted == NULL);
284*e4b17023SJohn Marino pair->first_element = p.first_element;
285*e4b17023SJohn Marino pair->second_element = p.second_element;
286*e4b17023SJohn Marino pair->cost = 0;
287*e4b17023SJohn Marino *slot = (void *)pair;
288*e4b17023SJohn Marino }
289*e4b17023SJohn Marino
290*e4b17023SJohn Marino return (struct coalesce_pair *) *slot;
291*e4b17023SJohn Marino }
292*e4b17023SJohn Marino
293*e4b17023SJohn Marino static inline void
add_cost_one_coalesce(coalesce_list_p cl,int p1,int p2)294*e4b17023SJohn Marino add_cost_one_coalesce (coalesce_list_p cl, int p1, int p2)
295*e4b17023SJohn Marino {
296*e4b17023SJohn Marino cost_one_pair_p pair;
297*e4b17023SJohn Marino
298*e4b17023SJohn Marino pair = XNEW (struct cost_one_pair_d);
299*e4b17023SJohn Marino pair->first_element = p1;
300*e4b17023SJohn Marino pair->second_element = p2;
301*e4b17023SJohn Marino pair->next = cl->cost_one_list;
302*e4b17023SJohn Marino cl->cost_one_list = pair;
303*e4b17023SJohn Marino }
304*e4b17023SJohn Marino
305*e4b17023SJohn Marino
306*e4b17023SJohn Marino /* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */
307*e4b17023SJohn Marino
308*e4b17023SJohn Marino static inline void
add_coalesce(coalesce_list_p cl,int p1,int p2,int value)309*e4b17023SJohn Marino add_coalesce (coalesce_list_p cl, int p1, int p2, int value)
310*e4b17023SJohn Marino {
311*e4b17023SJohn Marino coalesce_pair_p node;
312*e4b17023SJohn Marino
313*e4b17023SJohn Marino gcc_assert (cl->sorted == NULL);
314*e4b17023SJohn Marino if (p1 == p2)
315*e4b17023SJohn Marino return;
316*e4b17023SJohn Marino
317*e4b17023SJohn Marino node = find_coalesce_pair (cl, p1, p2, true);
318*e4b17023SJohn Marino
319*e4b17023SJohn Marino /* Once the value is at least MUST_COALESCE_COST - 1, leave it that way. */
320*e4b17023SJohn Marino if (node->cost < MUST_COALESCE_COST - 1)
321*e4b17023SJohn Marino {
322*e4b17023SJohn Marino if (value < MUST_COALESCE_COST - 1)
323*e4b17023SJohn Marino node->cost += value;
324*e4b17023SJohn Marino else
325*e4b17023SJohn Marino node->cost = value;
326*e4b17023SJohn Marino }
327*e4b17023SJohn Marino }
328*e4b17023SJohn Marino
329*e4b17023SJohn Marino
330*e4b17023SJohn Marino /* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */
331*e4b17023SJohn Marino
332*e4b17023SJohn Marino static int
compare_pairs(const void * p1,const void * p2)333*e4b17023SJohn Marino compare_pairs (const void *p1, const void *p2)
334*e4b17023SJohn Marino {
335*e4b17023SJohn Marino const_coalesce_pair_p const *const pp1 = (const_coalesce_pair_p const *) p1;
336*e4b17023SJohn Marino const_coalesce_pair_p const *const pp2 = (const_coalesce_pair_p const *) p2;
337*e4b17023SJohn Marino int result;
338*e4b17023SJohn Marino
339*e4b17023SJohn Marino result = (* pp1)->cost - (* pp2)->cost;
340*e4b17023SJohn Marino /* Since qsort does not guarantee stability we use the elements
341*e4b17023SJohn Marino as a secondary key. This provides us with independence from
342*e4b17023SJohn Marino the host's implementation of the sorting algorithm. */
343*e4b17023SJohn Marino if (result == 0)
344*e4b17023SJohn Marino {
345*e4b17023SJohn Marino result = (* pp2)->first_element - (* pp1)->first_element;
346*e4b17023SJohn Marino if (result == 0)
347*e4b17023SJohn Marino result = (* pp2)->second_element - (* pp1)->second_element;
348*e4b17023SJohn Marino }
349*e4b17023SJohn Marino
350*e4b17023SJohn Marino return result;
351*e4b17023SJohn Marino }
352*e4b17023SJohn Marino
353*e4b17023SJohn Marino
354*e4b17023SJohn Marino /* Return the number of unique coalesce pairs in CL. */
355*e4b17023SJohn Marino
356*e4b17023SJohn Marino static inline int
num_coalesce_pairs(coalesce_list_p cl)357*e4b17023SJohn Marino num_coalesce_pairs (coalesce_list_p cl)
358*e4b17023SJohn Marino {
359*e4b17023SJohn Marino return htab_elements (cl->list);
360*e4b17023SJohn Marino }
361*e4b17023SJohn Marino
362*e4b17023SJohn Marino
363*e4b17023SJohn Marino /* Iterator over hash table pairs. */
364*e4b17023SJohn Marino typedef struct
365*e4b17023SJohn Marino {
366*e4b17023SJohn Marino htab_iterator hti;
367*e4b17023SJohn Marino } coalesce_pair_iterator;
368*e4b17023SJohn Marino
369*e4b17023SJohn Marino
370*e4b17023SJohn Marino /* Return first partition pair from list CL, initializing iterator ITER. */
371*e4b17023SJohn Marino
372*e4b17023SJohn Marino static inline coalesce_pair_p
first_coalesce_pair(coalesce_list_p cl,coalesce_pair_iterator * iter)373*e4b17023SJohn Marino first_coalesce_pair (coalesce_list_p cl, coalesce_pair_iterator *iter)
374*e4b17023SJohn Marino {
375*e4b17023SJohn Marino coalesce_pair_p pair;
376*e4b17023SJohn Marino
377*e4b17023SJohn Marino pair = (coalesce_pair_p) first_htab_element (&(iter->hti), cl->list);
378*e4b17023SJohn Marino return pair;
379*e4b17023SJohn Marino }
380*e4b17023SJohn Marino
381*e4b17023SJohn Marino
382*e4b17023SJohn Marino /* Return TRUE if there are no more partitions in for ITER to process. */
383*e4b17023SJohn Marino
384*e4b17023SJohn Marino static inline bool
end_coalesce_pair_p(coalesce_pair_iterator * iter)385*e4b17023SJohn Marino end_coalesce_pair_p (coalesce_pair_iterator *iter)
386*e4b17023SJohn Marino {
387*e4b17023SJohn Marino return end_htab_p (&(iter->hti));
388*e4b17023SJohn Marino }
389*e4b17023SJohn Marino
390*e4b17023SJohn Marino
391*e4b17023SJohn Marino /* Return the next partition pair to be visited by ITER. */
392*e4b17023SJohn Marino
393*e4b17023SJohn Marino static inline coalesce_pair_p
next_coalesce_pair(coalesce_pair_iterator * iter)394*e4b17023SJohn Marino next_coalesce_pair (coalesce_pair_iterator *iter)
395*e4b17023SJohn Marino {
396*e4b17023SJohn Marino coalesce_pair_p pair;
397*e4b17023SJohn Marino
398*e4b17023SJohn Marino pair = (coalesce_pair_p) next_htab_element (&(iter->hti));
399*e4b17023SJohn Marino return pair;
400*e4b17023SJohn Marino }
401*e4b17023SJohn Marino
402*e4b17023SJohn Marino
403*e4b17023SJohn Marino /* Iterate over CL using ITER, returning values in PAIR. */
404*e4b17023SJohn Marino
405*e4b17023SJohn Marino #define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL) \
406*e4b17023SJohn Marino for ((PAIR) = first_coalesce_pair ((CL), &(ITER)); \
407*e4b17023SJohn Marino !end_coalesce_pair_p (&(ITER)); \
408*e4b17023SJohn Marino (PAIR) = next_coalesce_pair (&(ITER)))
409*e4b17023SJohn Marino
410*e4b17023SJohn Marino
411*e4b17023SJohn Marino /* Prepare CL for removal of preferred pairs. When finished they are sorted
412*e4b17023SJohn Marino in order from most important coalesce to least important. */
413*e4b17023SJohn Marino
414*e4b17023SJohn Marino static void
sort_coalesce_list(coalesce_list_p cl)415*e4b17023SJohn Marino sort_coalesce_list (coalesce_list_p cl)
416*e4b17023SJohn Marino {
417*e4b17023SJohn Marino unsigned x, num;
418*e4b17023SJohn Marino coalesce_pair_p p;
419*e4b17023SJohn Marino coalesce_pair_iterator ppi;
420*e4b17023SJohn Marino
421*e4b17023SJohn Marino gcc_assert (cl->sorted == NULL);
422*e4b17023SJohn Marino
423*e4b17023SJohn Marino num = num_coalesce_pairs (cl);
424*e4b17023SJohn Marino cl->num_sorted = num;
425*e4b17023SJohn Marino if (num == 0)
426*e4b17023SJohn Marino return;
427*e4b17023SJohn Marino
428*e4b17023SJohn Marino /* Allocate a vector for the pair pointers. */
429*e4b17023SJohn Marino cl->sorted = XNEWVEC (coalesce_pair_p, num);
430*e4b17023SJohn Marino
431*e4b17023SJohn Marino /* Populate the vector with pointers to the pairs. */
432*e4b17023SJohn Marino x = 0;
433*e4b17023SJohn Marino FOR_EACH_PARTITION_PAIR (p, ppi, cl)
434*e4b17023SJohn Marino cl->sorted[x++] = p;
435*e4b17023SJohn Marino gcc_assert (x == num);
436*e4b17023SJohn Marino
437*e4b17023SJohn Marino /* Already sorted. */
438*e4b17023SJohn Marino if (num == 1)
439*e4b17023SJohn Marino return;
440*e4b17023SJohn Marino
441*e4b17023SJohn Marino /* If there are only 2, just pick swap them if the order isn't correct. */
442*e4b17023SJohn Marino if (num == 2)
443*e4b17023SJohn Marino {
444*e4b17023SJohn Marino if (cl->sorted[0]->cost > cl->sorted[1]->cost)
445*e4b17023SJohn Marino {
446*e4b17023SJohn Marino p = cl->sorted[0];
447*e4b17023SJohn Marino cl->sorted[0] = cl->sorted[1];
448*e4b17023SJohn Marino cl->sorted[1] = p;
449*e4b17023SJohn Marino }
450*e4b17023SJohn Marino return;
451*e4b17023SJohn Marino }
452*e4b17023SJohn Marino
453*e4b17023SJohn Marino /* Only call qsort if there are more than 2 items. */
454*e4b17023SJohn Marino if (num > 2)
455*e4b17023SJohn Marino qsort (cl->sorted, num, sizeof (coalesce_pair_p), compare_pairs);
456*e4b17023SJohn Marino }
457*e4b17023SJohn Marino
458*e4b17023SJohn Marino
459*e4b17023SJohn Marino /* Send debug info for coalesce list CL to file F. */
460*e4b17023SJohn Marino
461*e4b17023SJohn Marino static void
dump_coalesce_list(FILE * f,coalesce_list_p cl)462*e4b17023SJohn Marino dump_coalesce_list (FILE *f, coalesce_list_p cl)
463*e4b17023SJohn Marino {
464*e4b17023SJohn Marino coalesce_pair_p node;
465*e4b17023SJohn Marino coalesce_pair_iterator ppi;
466*e4b17023SJohn Marino int x;
467*e4b17023SJohn Marino tree var;
468*e4b17023SJohn Marino
469*e4b17023SJohn Marino if (cl->sorted == NULL)
470*e4b17023SJohn Marino {
471*e4b17023SJohn Marino fprintf (f, "Coalesce List:\n");
472*e4b17023SJohn Marino FOR_EACH_PARTITION_PAIR (node, ppi, cl)
473*e4b17023SJohn Marino {
474*e4b17023SJohn Marino tree var1 = ssa_name (node->first_element);
475*e4b17023SJohn Marino tree var2 = ssa_name (node->second_element);
476*e4b17023SJohn Marino print_generic_expr (f, var1, TDF_SLIM);
477*e4b17023SJohn Marino fprintf (f, " <-> ");
478*e4b17023SJohn Marino print_generic_expr (f, var2, TDF_SLIM);
479*e4b17023SJohn Marino fprintf (f, " (%1d), ", node->cost);
480*e4b17023SJohn Marino fprintf (f, "\n");
481*e4b17023SJohn Marino }
482*e4b17023SJohn Marino }
483*e4b17023SJohn Marino else
484*e4b17023SJohn Marino {
485*e4b17023SJohn Marino fprintf (f, "Sorted Coalesce list:\n");
486*e4b17023SJohn Marino for (x = cl->num_sorted - 1 ; x >=0; x--)
487*e4b17023SJohn Marino {
488*e4b17023SJohn Marino node = cl->sorted[x];
489*e4b17023SJohn Marino fprintf (f, "(%d) ", node->cost);
490*e4b17023SJohn Marino var = ssa_name (node->first_element);
491*e4b17023SJohn Marino print_generic_expr (f, var, TDF_SLIM);
492*e4b17023SJohn Marino fprintf (f, " <-> ");
493*e4b17023SJohn Marino var = ssa_name (node->second_element);
494*e4b17023SJohn Marino print_generic_expr (f, var, TDF_SLIM);
495*e4b17023SJohn Marino fprintf (f, "\n");
496*e4b17023SJohn Marino }
497*e4b17023SJohn Marino }
498*e4b17023SJohn Marino }
499*e4b17023SJohn Marino
500*e4b17023SJohn Marino
501*e4b17023SJohn Marino /* This represents a conflict graph. Implemented as an array of bitmaps.
502*e4b17023SJohn Marino A full matrix is used for conflicts rather than just upper triangular form.
503*e4b17023SJohn Marino this make sit much simpler and faster to perform conflict merges. */
504*e4b17023SJohn Marino
505*e4b17023SJohn Marino typedef struct ssa_conflicts_d
506*e4b17023SJohn Marino {
507*e4b17023SJohn Marino unsigned size;
508*e4b17023SJohn Marino bitmap *conflicts;
509*e4b17023SJohn Marino } * ssa_conflicts_p;
510*e4b17023SJohn Marino
511*e4b17023SJohn Marino
512*e4b17023SJohn Marino /* Return an empty new conflict graph for SIZE elements. */
513*e4b17023SJohn Marino
514*e4b17023SJohn Marino static inline ssa_conflicts_p
ssa_conflicts_new(unsigned size)515*e4b17023SJohn Marino ssa_conflicts_new (unsigned size)
516*e4b17023SJohn Marino {
517*e4b17023SJohn Marino ssa_conflicts_p ptr;
518*e4b17023SJohn Marino
519*e4b17023SJohn Marino ptr = XNEW (struct ssa_conflicts_d);
520*e4b17023SJohn Marino ptr->conflicts = XCNEWVEC (bitmap, size);
521*e4b17023SJohn Marino ptr->size = size;
522*e4b17023SJohn Marino return ptr;
523*e4b17023SJohn Marino }
524*e4b17023SJohn Marino
525*e4b17023SJohn Marino
526*e4b17023SJohn Marino /* Free storage for conflict graph PTR. */
527*e4b17023SJohn Marino
528*e4b17023SJohn Marino static inline void
ssa_conflicts_delete(ssa_conflicts_p ptr)529*e4b17023SJohn Marino ssa_conflicts_delete (ssa_conflicts_p ptr)
530*e4b17023SJohn Marino {
531*e4b17023SJohn Marino unsigned x;
532*e4b17023SJohn Marino for (x = 0; x < ptr->size; x++)
533*e4b17023SJohn Marino if (ptr->conflicts[x])
534*e4b17023SJohn Marino BITMAP_FREE (ptr->conflicts[x]);
535*e4b17023SJohn Marino
536*e4b17023SJohn Marino free (ptr->conflicts);
537*e4b17023SJohn Marino free (ptr);
538*e4b17023SJohn Marino }
539*e4b17023SJohn Marino
540*e4b17023SJohn Marino
541*e4b17023SJohn Marino /* Test if elements X and Y conflict in graph PTR. */
542*e4b17023SJohn Marino
543*e4b17023SJohn Marino static inline bool
ssa_conflicts_test_p(ssa_conflicts_p ptr,unsigned x,unsigned y)544*e4b17023SJohn Marino ssa_conflicts_test_p (ssa_conflicts_p ptr, unsigned x, unsigned y)
545*e4b17023SJohn Marino {
546*e4b17023SJohn Marino bitmap b;
547*e4b17023SJohn Marino
548*e4b17023SJohn Marino gcc_checking_assert (x < ptr->size);
549*e4b17023SJohn Marino gcc_checking_assert (y < ptr->size);
550*e4b17023SJohn Marino gcc_checking_assert (x != y);
551*e4b17023SJohn Marino
552*e4b17023SJohn Marino b = ptr->conflicts[x];
553*e4b17023SJohn Marino if (b)
554*e4b17023SJohn Marino /* Avoid the lookup if Y has no conflicts. */
555*e4b17023SJohn Marino return ptr->conflicts[y] ? bitmap_bit_p (b, y) : false;
556*e4b17023SJohn Marino else
557*e4b17023SJohn Marino return false;
558*e4b17023SJohn Marino }
559*e4b17023SJohn Marino
560*e4b17023SJohn Marino
561*e4b17023SJohn Marino /* Add a conflict with Y to the bitmap for X in graph PTR. */
562*e4b17023SJohn Marino
563*e4b17023SJohn Marino static inline void
ssa_conflicts_add_one(ssa_conflicts_p ptr,unsigned x,unsigned y)564*e4b17023SJohn Marino ssa_conflicts_add_one (ssa_conflicts_p ptr, unsigned x, unsigned y)
565*e4b17023SJohn Marino {
566*e4b17023SJohn Marino /* If there are no conflicts yet, allocate the bitmap and set bit. */
567*e4b17023SJohn Marino if (!ptr->conflicts[x])
568*e4b17023SJohn Marino ptr->conflicts[x] = BITMAP_ALLOC (NULL);
569*e4b17023SJohn Marino bitmap_set_bit (ptr->conflicts[x], y);
570*e4b17023SJohn Marino }
571*e4b17023SJohn Marino
572*e4b17023SJohn Marino
573*e4b17023SJohn Marino /* Add conflicts between X and Y in graph PTR. */
574*e4b17023SJohn Marino
575*e4b17023SJohn Marino static inline void
ssa_conflicts_add(ssa_conflicts_p ptr,unsigned x,unsigned y)576*e4b17023SJohn Marino ssa_conflicts_add (ssa_conflicts_p ptr, unsigned x, unsigned y)
577*e4b17023SJohn Marino {
578*e4b17023SJohn Marino gcc_checking_assert (x < ptr->size);
579*e4b17023SJohn Marino gcc_checking_assert (y < ptr->size);
580*e4b17023SJohn Marino gcc_checking_assert (x != y);
581*e4b17023SJohn Marino ssa_conflicts_add_one (ptr, x, y);
582*e4b17023SJohn Marino ssa_conflicts_add_one (ptr, y, x);
583*e4b17023SJohn Marino }
584*e4b17023SJohn Marino
585*e4b17023SJohn Marino
586*e4b17023SJohn Marino /* Merge all Y's conflict into X in graph PTR. */
587*e4b17023SJohn Marino
588*e4b17023SJohn Marino static inline void
ssa_conflicts_merge(ssa_conflicts_p ptr,unsigned x,unsigned y)589*e4b17023SJohn Marino ssa_conflicts_merge (ssa_conflicts_p ptr, unsigned x, unsigned y)
590*e4b17023SJohn Marino {
591*e4b17023SJohn Marino unsigned z;
592*e4b17023SJohn Marino bitmap_iterator bi;
593*e4b17023SJohn Marino
594*e4b17023SJohn Marino gcc_assert (x != y);
595*e4b17023SJohn Marino if (!(ptr->conflicts[y]))
596*e4b17023SJohn Marino return;
597*e4b17023SJohn Marino
598*e4b17023SJohn Marino /* Add a conflict between X and every one Y has. If the bitmap doesn't
599*e4b17023SJohn Marino exist, then it has already been coalesced, and we don't need to add a
600*e4b17023SJohn Marino conflict. */
601*e4b17023SJohn Marino EXECUTE_IF_SET_IN_BITMAP (ptr->conflicts[y], 0, z, bi)
602*e4b17023SJohn Marino if (ptr->conflicts[z])
603*e4b17023SJohn Marino bitmap_set_bit (ptr->conflicts[z], x);
604*e4b17023SJohn Marino
605*e4b17023SJohn Marino if (ptr->conflicts[x])
606*e4b17023SJohn Marino {
607*e4b17023SJohn Marino /* If X has conflicts, add Y's to X. */
608*e4b17023SJohn Marino bitmap_ior_into (ptr->conflicts[x], ptr->conflicts[y]);
609*e4b17023SJohn Marino BITMAP_FREE (ptr->conflicts[y]);
610*e4b17023SJohn Marino }
611*e4b17023SJohn Marino else
612*e4b17023SJohn Marino {
613*e4b17023SJohn Marino /* If X has no conflicts, simply use Y's. */
614*e4b17023SJohn Marino ptr->conflicts[x] = ptr->conflicts[y];
615*e4b17023SJohn Marino ptr->conflicts[y] = NULL;
616*e4b17023SJohn Marino }
617*e4b17023SJohn Marino }
618*e4b17023SJohn Marino
619*e4b17023SJohn Marino
620*e4b17023SJohn Marino /* Dump a conflicts graph. */
621*e4b17023SJohn Marino
622*e4b17023SJohn Marino static void
ssa_conflicts_dump(FILE * file,ssa_conflicts_p ptr)623*e4b17023SJohn Marino ssa_conflicts_dump (FILE *file, ssa_conflicts_p ptr)
624*e4b17023SJohn Marino {
625*e4b17023SJohn Marino unsigned x;
626*e4b17023SJohn Marino
627*e4b17023SJohn Marino fprintf (file, "\nConflict graph:\n");
628*e4b17023SJohn Marino
629*e4b17023SJohn Marino for (x = 0; x < ptr->size; x++)
630*e4b17023SJohn Marino if (ptr->conflicts[x])
631*e4b17023SJohn Marino {
632*e4b17023SJohn Marino fprintf (dump_file, "%d: ", x);
633*e4b17023SJohn Marino dump_bitmap (file, ptr->conflicts[x]);
634*e4b17023SJohn Marino }
635*e4b17023SJohn Marino }
636*e4b17023SJohn Marino
637*e4b17023SJohn Marino
638*e4b17023SJohn Marino /* This structure is used to efficiently record the current status of live
639*e4b17023SJohn Marino SSA_NAMES when building a conflict graph.
640*e4b17023SJohn Marino LIVE_BASE_VAR has a bit set for each base variable which has at least one
641*e4b17023SJohn Marino ssa version live.
642*e4b17023SJohn Marino LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an
643*e4b17023SJohn Marino index, and is used to track what partitions of each base variable are
644*e4b17023SJohn Marino live. This makes it easy to add conflicts between just live partitions
645*e4b17023SJohn Marino with the same base variable.
646*e4b17023SJohn Marino The values in LIVE_BASE_PARTITIONS are only valid if the base variable is
647*e4b17023SJohn Marino marked as being live. This delays clearing of these bitmaps until
648*e4b17023SJohn Marino they are actually needed again. */
649*e4b17023SJohn Marino
650*e4b17023SJohn Marino typedef struct live_track_d
651*e4b17023SJohn Marino {
652*e4b17023SJohn Marino bitmap live_base_var; /* Indicates if a basevar is live. */
653*e4b17023SJohn Marino bitmap *live_base_partitions; /* Live partitions for each basevar. */
654*e4b17023SJohn Marino var_map map; /* Var_map being used for partition mapping. */
655*e4b17023SJohn Marino } * live_track_p;
656*e4b17023SJohn Marino
657*e4b17023SJohn Marino
658*e4b17023SJohn Marino /* This routine will create a new live track structure based on the partitions
659*e4b17023SJohn Marino in MAP. */
660*e4b17023SJohn Marino
661*e4b17023SJohn Marino static live_track_p
new_live_track(var_map map)662*e4b17023SJohn Marino new_live_track (var_map map)
663*e4b17023SJohn Marino {
664*e4b17023SJohn Marino live_track_p ptr;
665*e4b17023SJohn Marino int lim, x;
666*e4b17023SJohn Marino
667*e4b17023SJohn Marino /* Make sure there is a partition view in place. */
668*e4b17023SJohn Marino gcc_assert (map->partition_to_base_index != NULL);
669*e4b17023SJohn Marino
670*e4b17023SJohn Marino ptr = (live_track_p) xmalloc (sizeof (struct live_track_d));
671*e4b17023SJohn Marino ptr->map = map;
672*e4b17023SJohn Marino lim = num_basevars (map);
673*e4b17023SJohn Marino ptr->live_base_partitions = (bitmap *) xmalloc(sizeof (bitmap *) * lim);
674*e4b17023SJohn Marino ptr->live_base_var = BITMAP_ALLOC (NULL);
675*e4b17023SJohn Marino for (x = 0; x < lim; x++)
676*e4b17023SJohn Marino ptr->live_base_partitions[x] = BITMAP_ALLOC (NULL);
677*e4b17023SJohn Marino return ptr;
678*e4b17023SJohn Marino }
679*e4b17023SJohn Marino
680*e4b17023SJohn Marino
681*e4b17023SJohn Marino /* This routine will free the memory associated with PTR. */
682*e4b17023SJohn Marino
683*e4b17023SJohn Marino static void
delete_live_track(live_track_p ptr)684*e4b17023SJohn Marino delete_live_track (live_track_p ptr)
685*e4b17023SJohn Marino {
686*e4b17023SJohn Marino int x, lim;
687*e4b17023SJohn Marino
688*e4b17023SJohn Marino lim = num_basevars (ptr->map);
689*e4b17023SJohn Marino for (x = 0; x < lim; x++)
690*e4b17023SJohn Marino BITMAP_FREE (ptr->live_base_partitions[x]);
691*e4b17023SJohn Marino BITMAP_FREE (ptr->live_base_var);
692*e4b17023SJohn Marino free (ptr->live_base_partitions);
693*e4b17023SJohn Marino free (ptr);
694*e4b17023SJohn Marino }
695*e4b17023SJohn Marino
696*e4b17023SJohn Marino
697*e4b17023SJohn Marino /* This function will remove PARTITION from the live list in PTR. */
698*e4b17023SJohn Marino
699*e4b17023SJohn Marino static inline void
live_track_remove_partition(live_track_p ptr,int partition)700*e4b17023SJohn Marino live_track_remove_partition (live_track_p ptr, int partition)
701*e4b17023SJohn Marino {
702*e4b17023SJohn Marino int root;
703*e4b17023SJohn Marino
704*e4b17023SJohn Marino root = basevar_index (ptr->map, partition);
705*e4b17023SJohn Marino bitmap_clear_bit (ptr->live_base_partitions[root], partition);
706*e4b17023SJohn Marino /* If the element list is empty, make the base variable not live either. */
707*e4b17023SJohn Marino if (bitmap_empty_p (ptr->live_base_partitions[root]))
708*e4b17023SJohn Marino bitmap_clear_bit (ptr->live_base_var, root);
709*e4b17023SJohn Marino }
710*e4b17023SJohn Marino
711*e4b17023SJohn Marino
712*e4b17023SJohn Marino /* This function will adds PARTITION to the live list in PTR. */
713*e4b17023SJohn Marino
714*e4b17023SJohn Marino static inline void
live_track_add_partition(live_track_p ptr,int partition)715*e4b17023SJohn Marino live_track_add_partition (live_track_p ptr, int partition)
716*e4b17023SJohn Marino {
717*e4b17023SJohn Marino int root;
718*e4b17023SJohn Marino
719*e4b17023SJohn Marino root = basevar_index (ptr->map, partition);
720*e4b17023SJohn Marino /* If this base var wasn't live before, it is now. Clear the element list
721*e4b17023SJohn Marino since it was delayed until needed. */
722*e4b17023SJohn Marino if (bitmap_set_bit (ptr->live_base_var, root))
723*e4b17023SJohn Marino bitmap_clear (ptr->live_base_partitions[root]);
724*e4b17023SJohn Marino bitmap_set_bit (ptr->live_base_partitions[root], partition);
725*e4b17023SJohn Marino
726*e4b17023SJohn Marino }
727*e4b17023SJohn Marino
728*e4b17023SJohn Marino
729*e4b17023SJohn Marino /* Clear the live bit for VAR in PTR. */
730*e4b17023SJohn Marino
731*e4b17023SJohn Marino static inline void
live_track_clear_var(live_track_p ptr,tree var)732*e4b17023SJohn Marino live_track_clear_var (live_track_p ptr, tree var)
733*e4b17023SJohn Marino {
734*e4b17023SJohn Marino int p;
735*e4b17023SJohn Marino
736*e4b17023SJohn Marino p = var_to_partition (ptr->map, var);
737*e4b17023SJohn Marino if (p != NO_PARTITION)
738*e4b17023SJohn Marino live_track_remove_partition (ptr, p);
739*e4b17023SJohn Marino }
740*e4b17023SJohn Marino
741*e4b17023SJohn Marino
742*e4b17023SJohn Marino /* Return TRUE if VAR is live in PTR. */
743*e4b17023SJohn Marino
744*e4b17023SJohn Marino static inline bool
live_track_live_p(live_track_p ptr,tree var)745*e4b17023SJohn Marino live_track_live_p (live_track_p ptr, tree var)
746*e4b17023SJohn Marino {
747*e4b17023SJohn Marino int p, root;
748*e4b17023SJohn Marino
749*e4b17023SJohn Marino p = var_to_partition (ptr->map, var);
750*e4b17023SJohn Marino if (p != NO_PARTITION)
751*e4b17023SJohn Marino {
752*e4b17023SJohn Marino root = basevar_index (ptr->map, p);
753*e4b17023SJohn Marino if (bitmap_bit_p (ptr->live_base_var, root))
754*e4b17023SJohn Marino return bitmap_bit_p (ptr->live_base_partitions[root], p);
755*e4b17023SJohn Marino }
756*e4b17023SJohn Marino return false;
757*e4b17023SJohn Marino }
758*e4b17023SJohn Marino
759*e4b17023SJohn Marino
760*e4b17023SJohn Marino /* This routine will add USE to PTR. USE will be marked as live in both the
761*e4b17023SJohn Marino ssa live map and the live bitmap for the root of USE. */
762*e4b17023SJohn Marino
763*e4b17023SJohn Marino static inline void
live_track_process_use(live_track_p ptr,tree use)764*e4b17023SJohn Marino live_track_process_use (live_track_p ptr, tree use)
765*e4b17023SJohn Marino {
766*e4b17023SJohn Marino int p;
767*e4b17023SJohn Marino
768*e4b17023SJohn Marino p = var_to_partition (ptr->map, use);
769*e4b17023SJohn Marino if (p == NO_PARTITION)
770*e4b17023SJohn Marino return;
771*e4b17023SJohn Marino
772*e4b17023SJohn Marino /* Mark as live in the appropriate live list. */
773*e4b17023SJohn Marino live_track_add_partition (ptr, p);
774*e4b17023SJohn Marino }
775*e4b17023SJohn Marino
776*e4b17023SJohn Marino
777*e4b17023SJohn Marino /* This routine will process a DEF in PTR. DEF will be removed from the live
778*e4b17023SJohn Marino lists, and if there are any other live partitions with the same base
779*e4b17023SJohn Marino variable, conflicts will be added to GRAPH. */
780*e4b17023SJohn Marino
781*e4b17023SJohn Marino static inline void
live_track_process_def(live_track_p ptr,tree def,ssa_conflicts_p graph)782*e4b17023SJohn Marino live_track_process_def (live_track_p ptr, tree def, ssa_conflicts_p graph)
783*e4b17023SJohn Marino {
784*e4b17023SJohn Marino int p, root;
785*e4b17023SJohn Marino bitmap b;
786*e4b17023SJohn Marino unsigned x;
787*e4b17023SJohn Marino bitmap_iterator bi;
788*e4b17023SJohn Marino
789*e4b17023SJohn Marino p = var_to_partition (ptr->map, def);
790*e4b17023SJohn Marino if (p == NO_PARTITION)
791*e4b17023SJohn Marino return;
792*e4b17023SJohn Marino
793*e4b17023SJohn Marino /* Clear the liveness bit. */
794*e4b17023SJohn Marino live_track_remove_partition (ptr, p);
795*e4b17023SJohn Marino
796*e4b17023SJohn Marino /* If the bitmap isn't empty now, conflicts need to be added. */
797*e4b17023SJohn Marino root = basevar_index (ptr->map, p);
798*e4b17023SJohn Marino if (bitmap_bit_p (ptr->live_base_var, root))
799*e4b17023SJohn Marino {
800*e4b17023SJohn Marino b = ptr->live_base_partitions[root];
801*e4b17023SJohn Marino EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi)
802*e4b17023SJohn Marino ssa_conflicts_add (graph, p, x);
803*e4b17023SJohn Marino }
804*e4b17023SJohn Marino }
805*e4b17023SJohn Marino
806*e4b17023SJohn Marino
807*e4b17023SJohn Marino /* Initialize PTR with the partitions set in INIT. */
808*e4b17023SJohn Marino
809*e4b17023SJohn Marino static inline void
live_track_init(live_track_p ptr,bitmap init)810*e4b17023SJohn Marino live_track_init (live_track_p ptr, bitmap init)
811*e4b17023SJohn Marino {
812*e4b17023SJohn Marino unsigned p;
813*e4b17023SJohn Marino bitmap_iterator bi;
814*e4b17023SJohn Marino
815*e4b17023SJohn Marino /* Mark all live on exit partitions. */
816*e4b17023SJohn Marino EXECUTE_IF_SET_IN_BITMAP (init, 0, p, bi)
817*e4b17023SJohn Marino live_track_add_partition (ptr, p);
818*e4b17023SJohn Marino }
819*e4b17023SJohn Marino
820*e4b17023SJohn Marino
821*e4b17023SJohn Marino /* This routine will clear all live partitions in PTR. */
822*e4b17023SJohn Marino
823*e4b17023SJohn Marino static inline void
live_track_clear_base_vars(live_track_p ptr)824*e4b17023SJohn Marino live_track_clear_base_vars (live_track_p ptr)
825*e4b17023SJohn Marino {
826*e4b17023SJohn Marino /* Simply clear the live base list. Anything marked as live in the element
827*e4b17023SJohn Marino lists will be cleared later if/when the base variable ever comes alive
828*e4b17023SJohn Marino again. */
829*e4b17023SJohn Marino bitmap_clear (ptr->live_base_var);
830*e4b17023SJohn Marino }
831*e4b17023SJohn Marino
832*e4b17023SJohn Marino
833*e4b17023SJohn Marino /* Build a conflict graph based on LIVEINFO. Any partitions which are in the
834*e4b17023SJohn Marino partition view of the var_map liveinfo is based on get entries in the
835*e4b17023SJohn Marino conflict graph. Only conflicts between ssa_name partitions with the same
836*e4b17023SJohn Marino base variable are added. */
837*e4b17023SJohn Marino
838*e4b17023SJohn Marino static ssa_conflicts_p
build_ssa_conflict_graph(tree_live_info_p liveinfo)839*e4b17023SJohn Marino build_ssa_conflict_graph (tree_live_info_p liveinfo)
840*e4b17023SJohn Marino {
841*e4b17023SJohn Marino ssa_conflicts_p graph;
842*e4b17023SJohn Marino var_map map;
843*e4b17023SJohn Marino basic_block bb;
844*e4b17023SJohn Marino ssa_op_iter iter;
845*e4b17023SJohn Marino live_track_p live;
846*e4b17023SJohn Marino
847*e4b17023SJohn Marino map = live_var_map (liveinfo);
848*e4b17023SJohn Marino graph = ssa_conflicts_new (num_var_partitions (map));
849*e4b17023SJohn Marino
850*e4b17023SJohn Marino live = new_live_track (map);
851*e4b17023SJohn Marino
852*e4b17023SJohn Marino FOR_EACH_BB (bb)
853*e4b17023SJohn Marino {
854*e4b17023SJohn Marino gimple_stmt_iterator gsi;
855*e4b17023SJohn Marino
856*e4b17023SJohn Marino /* Start with live on exit temporaries. */
857*e4b17023SJohn Marino live_track_init (live, live_on_exit (liveinfo, bb));
858*e4b17023SJohn Marino
859*e4b17023SJohn Marino for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
860*e4b17023SJohn Marino {
861*e4b17023SJohn Marino tree var;
862*e4b17023SJohn Marino gimple stmt = gsi_stmt (gsi);
863*e4b17023SJohn Marino
864*e4b17023SJohn Marino /* A copy between 2 partitions does not introduce an interference
865*e4b17023SJohn Marino by itself. If they did, you would never be able to coalesce
866*e4b17023SJohn Marino two things which are copied. If the two variables really do
867*e4b17023SJohn Marino conflict, they will conflict elsewhere in the program.
868*e4b17023SJohn Marino
869*e4b17023SJohn Marino This is handled by simply removing the SRC of the copy from the
870*e4b17023SJohn Marino live list, and processing the stmt normally. */
871*e4b17023SJohn Marino if (is_gimple_assign (stmt))
872*e4b17023SJohn Marino {
873*e4b17023SJohn Marino tree lhs = gimple_assign_lhs (stmt);
874*e4b17023SJohn Marino tree rhs1 = gimple_assign_rhs1 (stmt);
875*e4b17023SJohn Marino if (gimple_assign_copy_p (stmt)
876*e4b17023SJohn Marino && TREE_CODE (lhs) == SSA_NAME
877*e4b17023SJohn Marino && TREE_CODE (rhs1) == SSA_NAME)
878*e4b17023SJohn Marino live_track_clear_var (live, rhs1);
879*e4b17023SJohn Marino }
880*e4b17023SJohn Marino else if (is_gimple_debug (stmt))
881*e4b17023SJohn Marino continue;
882*e4b17023SJohn Marino
883*e4b17023SJohn Marino FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
884*e4b17023SJohn Marino live_track_process_def (live, var, graph);
885*e4b17023SJohn Marino
886*e4b17023SJohn Marino FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
887*e4b17023SJohn Marino live_track_process_use (live, var);
888*e4b17023SJohn Marino }
889*e4b17023SJohn Marino
890*e4b17023SJohn Marino /* If result of a PHI is unused, looping over the statements will not
891*e4b17023SJohn Marino record any conflicts since the def was never live. Since the PHI node
892*e4b17023SJohn Marino is going to be translated out of SSA form, it will insert a copy.
893*e4b17023SJohn Marino There must be a conflict recorded between the result of the PHI and
894*e4b17023SJohn Marino any variables that are live. Otherwise the out-of-ssa translation
895*e4b17023SJohn Marino may create incorrect code. */
896*e4b17023SJohn Marino for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
897*e4b17023SJohn Marino {
898*e4b17023SJohn Marino gimple phi = gsi_stmt (gsi);
899*e4b17023SJohn Marino tree result = PHI_RESULT (phi);
900*e4b17023SJohn Marino if (live_track_live_p (live, result))
901*e4b17023SJohn Marino live_track_process_def (live, result, graph);
902*e4b17023SJohn Marino }
903*e4b17023SJohn Marino
904*e4b17023SJohn Marino live_track_clear_base_vars (live);
905*e4b17023SJohn Marino }
906*e4b17023SJohn Marino
907*e4b17023SJohn Marino delete_live_track (live);
908*e4b17023SJohn Marino return graph;
909*e4b17023SJohn Marino }
910*e4b17023SJohn Marino
911*e4b17023SJohn Marino
912*e4b17023SJohn Marino /* Shortcut routine to print messages to file F of the form:
913*e4b17023SJohn Marino "STR1 EXPR1 STR2 EXPR2 STR3." */
914*e4b17023SJohn Marino
915*e4b17023SJohn Marino static inline void
print_exprs(FILE * f,const char * str1,tree expr1,const char * str2,tree expr2,const char * str3)916*e4b17023SJohn Marino print_exprs (FILE *f, const char *str1, tree expr1, const char *str2,
917*e4b17023SJohn Marino tree expr2, const char *str3)
918*e4b17023SJohn Marino {
919*e4b17023SJohn Marino fprintf (f, "%s", str1);
920*e4b17023SJohn Marino print_generic_expr (f, expr1, TDF_SLIM);
921*e4b17023SJohn Marino fprintf (f, "%s", str2);
922*e4b17023SJohn Marino print_generic_expr (f, expr2, TDF_SLIM);
923*e4b17023SJohn Marino fprintf (f, "%s", str3);
924*e4b17023SJohn Marino }
925*e4b17023SJohn Marino
926*e4b17023SJohn Marino
927*e4b17023SJohn Marino /* Called if a coalesce across and abnormal edge cannot be performed. PHI is
928*e4b17023SJohn Marino the phi node at fault, I is the argument index at fault. A message is
929*e4b17023SJohn Marino printed and compilation is then terminated. */
930*e4b17023SJohn Marino
931*e4b17023SJohn Marino static inline void
abnormal_corrupt(gimple phi,int i)932*e4b17023SJohn Marino abnormal_corrupt (gimple phi, int i)
933*e4b17023SJohn Marino {
934*e4b17023SJohn Marino edge e = gimple_phi_arg_edge (phi, i);
935*e4b17023SJohn Marino tree res = gimple_phi_result (phi);
936*e4b17023SJohn Marino tree arg = gimple_phi_arg_def (phi, i);
937*e4b17023SJohn Marino
938*e4b17023SJohn Marino fprintf (stderr, " Corrupt SSA across abnormal edge BB%d->BB%d\n",
939*e4b17023SJohn Marino e->src->index, e->dest->index);
940*e4b17023SJohn Marino fprintf (stderr, "Argument %d (", i);
941*e4b17023SJohn Marino print_generic_expr (stderr, arg, TDF_SLIM);
942*e4b17023SJohn Marino if (TREE_CODE (arg) != SSA_NAME)
943*e4b17023SJohn Marino fprintf (stderr, ") is not an SSA_NAME.\n");
944*e4b17023SJohn Marino else
945*e4b17023SJohn Marino {
946*e4b17023SJohn Marino gcc_assert (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg));
947*e4b17023SJohn Marino fprintf (stderr, ") does not have the same base variable as the result ");
948*e4b17023SJohn Marino print_generic_stmt (stderr, res, TDF_SLIM);
949*e4b17023SJohn Marino }
950*e4b17023SJohn Marino
951*e4b17023SJohn Marino internal_error ("SSA corruption");
952*e4b17023SJohn Marino }
953*e4b17023SJohn Marino
954*e4b17023SJohn Marino
955*e4b17023SJohn Marino /* Print a failure to coalesce a MUST_COALESCE pair X and Y. */
956*e4b17023SJohn Marino
957*e4b17023SJohn Marino static inline void
fail_abnormal_edge_coalesce(int x,int y)958*e4b17023SJohn Marino fail_abnormal_edge_coalesce (int x, int y)
959*e4b17023SJohn Marino {
960*e4b17023SJohn Marino fprintf (stderr, "\nUnable to coalesce ssa_names %d and %d",x, y);
961*e4b17023SJohn Marino fprintf (stderr, " which are marked as MUST COALESCE.\n");
962*e4b17023SJohn Marino print_generic_expr (stderr, ssa_name (x), TDF_SLIM);
963*e4b17023SJohn Marino fprintf (stderr, " and ");
964*e4b17023SJohn Marino print_generic_stmt (stderr, ssa_name (y), TDF_SLIM);
965*e4b17023SJohn Marino
966*e4b17023SJohn Marino internal_error ("SSA corruption");
967*e4b17023SJohn Marino }
968*e4b17023SJohn Marino
969*e4b17023SJohn Marino
970*e4b17023SJohn Marino /* This function creates a var_map for the current function as well as creating
971*e4b17023SJohn Marino a coalesce list for use later in the out of ssa process. */
972*e4b17023SJohn Marino
973*e4b17023SJohn Marino static var_map
create_outofssa_var_map(coalesce_list_p cl,bitmap used_in_copy)974*e4b17023SJohn Marino create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy)
975*e4b17023SJohn Marino {
976*e4b17023SJohn Marino gimple_stmt_iterator gsi;
977*e4b17023SJohn Marino basic_block bb;
978*e4b17023SJohn Marino tree var;
979*e4b17023SJohn Marino gimple stmt;
980*e4b17023SJohn Marino tree first;
981*e4b17023SJohn Marino var_map map;
982*e4b17023SJohn Marino ssa_op_iter iter;
983*e4b17023SJohn Marino int v1, v2, cost;
984*e4b17023SJohn Marino unsigned i;
985*e4b17023SJohn Marino
986*e4b17023SJohn Marino #ifdef ENABLE_CHECKING
987*e4b17023SJohn Marino bitmap used_in_real_ops;
988*e4b17023SJohn Marino bitmap used_in_virtual_ops;
989*e4b17023SJohn Marino
990*e4b17023SJohn Marino used_in_real_ops = BITMAP_ALLOC (NULL);
991*e4b17023SJohn Marino used_in_virtual_ops = BITMAP_ALLOC (NULL);
992*e4b17023SJohn Marino #endif
993*e4b17023SJohn Marino
994*e4b17023SJohn Marino map = init_var_map (num_ssa_names);
995*e4b17023SJohn Marino
996*e4b17023SJohn Marino FOR_EACH_BB (bb)
997*e4b17023SJohn Marino {
998*e4b17023SJohn Marino tree arg;
999*e4b17023SJohn Marino
1000*e4b17023SJohn Marino for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1001*e4b17023SJohn Marino {
1002*e4b17023SJohn Marino gimple phi = gsi_stmt (gsi);
1003*e4b17023SJohn Marino size_t i;
1004*e4b17023SJohn Marino int ver;
1005*e4b17023SJohn Marino tree res;
1006*e4b17023SJohn Marino bool saw_copy = false;
1007*e4b17023SJohn Marino
1008*e4b17023SJohn Marino res = gimple_phi_result (phi);
1009*e4b17023SJohn Marino ver = SSA_NAME_VERSION (res);
1010*e4b17023SJohn Marino register_ssa_partition (map, res);
1011*e4b17023SJohn Marino
1012*e4b17023SJohn Marino /* Register ssa_names and coalesces between the args and the result
1013*e4b17023SJohn Marino of all PHI. */
1014*e4b17023SJohn Marino for (i = 0; i < gimple_phi_num_args (phi); i++)
1015*e4b17023SJohn Marino {
1016*e4b17023SJohn Marino edge e = gimple_phi_arg_edge (phi, i);
1017*e4b17023SJohn Marino arg = PHI_ARG_DEF (phi, i);
1018*e4b17023SJohn Marino if (TREE_CODE (arg) == SSA_NAME)
1019*e4b17023SJohn Marino register_ssa_partition (map, arg);
1020*e4b17023SJohn Marino if (TREE_CODE (arg) == SSA_NAME
1021*e4b17023SJohn Marino && SSA_NAME_VAR (arg) == SSA_NAME_VAR (res))
1022*e4b17023SJohn Marino {
1023*e4b17023SJohn Marino saw_copy = true;
1024*e4b17023SJohn Marino bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg));
1025*e4b17023SJohn Marino if ((e->flags & EDGE_ABNORMAL) == 0)
1026*e4b17023SJohn Marino {
1027*e4b17023SJohn Marino int cost = coalesce_cost_edge (e);
1028*e4b17023SJohn Marino if (cost == 1 && has_single_use (arg))
1029*e4b17023SJohn Marino add_cost_one_coalesce (cl, ver, SSA_NAME_VERSION (arg));
1030*e4b17023SJohn Marino else
1031*e4b17023SJohn Marino add_coalesce (cl, ver, SSA_NAME_VERSION (arg), cost);
1032*e4b17023SJohn Marino }
1033*e4b17023SJohn Marino }
1034*e4b17023SJohn Marino else
1035*e4b17023SJohn Marino if (e->flags & EDGE_ABNORMAL)
1036*e4b17023SJohn Marino abnormal_corrupt (phi, i);
1037*e4b17023SJohn Marino }
1038*e4b17023SJohn Marino if (saw_copy)
1039*e4b17023SJohn Marino bitmap_set_bit (used_in_copy, ver);
1040*e4b17023SJohn Marino }
1041*e4b17023SJohn Marino
1042*e4b17023SJohn Marino for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1043*e4b17023SJohn Marino {
1044*e4b17023SJohn Marino stmt = gsi_stmt (gsi);
1045*e4b17023SJohn Marino
1046*e4b17023SJohn Marino if (is_gimple_debug (stmt))
1047*e4b17023SJohn Marino continue;
1048*e4b17023SJohn Marino
1049*e4b17023SJohn Marino /* Register USE and DEF operands in each statement. */
1050*e4b17023SJohn Marino FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
1051*e4b17023SJohn Marino register_ssa_partition (map, var);
1052*e4b17023SJohn Marino
1053*e4b17023SJohn Marino /* Check for copy coalesces. */
1054*e4b17023SJohn Marino switch (gimple_code (stmt))
1055*e4b17023SJohn Marino {
1056*e4b17023SJohn Marino case GIMPLE_ASSIGN:
1057*e4b17023SJohn Marino {
1058*e4b17023SJohn Marino tree lhs = gimple_assign_lhs (stmt);
1059*e4b17023SJohn Marino tree rhs1 = gimple_assign_rhs1 (stmt);
1060*e4b17023SJohn Marino
1061*e4b17023SJohn Marino if (gimple_assign_copy_p (stmt)
1062*e4b17023SJohn Marino && TREE_CODE (lhs) == SSA_NAME
1063*e4b17023SJohn Marino && TREE_CODE (rhs1) == SSA_NAME
1064*e4b17023SJohn Marino && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs1))
1065*e4b17023SJohn Marino {
1066*e4b17023SJohn Marino v1 = SSA_NAME_VERSION (lhs);
1067*e4b17023SJohn Marino v2 = SSA_NAME_VERSION (rhs1);
1068*e4b17023SJohn Marino cost = coalesce_cost_bb (bb);
1069*e4b17023SJohn Marino add_coalesce (cl, v1, v2, cost);
1070*e4b17023SJohn Marino bitmap_set_bit (used_in_copy, v1);
1071*e4b17023SJohn Marino bitmap_set_bit (used_in_copy, v2);
1072*e4b17023SJohn Marino }
1073*e4b17023SJohn Marino }
1074*e4b17023SJohn Marino break;
1075*e4b17023SJohn Marino
1076*e4b17023SJohn Marino case GIMPLE_ASM:
1077*e4b17023SJohn Marino {
1078*e4b17023SJohn Marino unsigned long noutputs, i;
1079*e4b17023SJohn Marino unsigned long ninputs;
1080*e4b17023SJohn Marino tree *outputs, link;
1081*e4b17023SJohn Marino noutputs = gimple_asm_noutputs (stmt);
1082*e4b17023SJohn Marino ninputs = gimple_asm_ninputs (stmt);
1083*e4b17023SJohn Marino outputs = (tree *) alloca (noutputs * sizeof (tree));
1084*e4b17023SJohn Marino for (i = 0; i < noutputs; ++i) {
1085*e4b17023SJohn Marino link = gimple_asm_output_op (stmt, i);
1086*e4b17023SJohn Marino outputs[i] = TREE_VALUE (link);
1087*e4b17023SJohn Marino }
1088*e4b17023SJohn Marino
1089*e4b17023SJohn Marino for (i = 0; i < ninputs; ++i)
1090*e4b17023SJohn Marino {
1091*e4b17023SJohn Marino const char *constraint;
1092*e4b17023SJohn Marino tree input;
1093*e4b17023SJohn Marino char *end;
1094*e4b17023SJohn Marino unsigned long match;
1095*e4b17023SJohn Marino
1096*e4b17023SJohn Marino link = gimple_asm_input_op (stmt, i);
1097*e4b17023SJohn Marino constraint
1098*e4b17023SJohn Marino = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1099*e4b17023SJohn Marino input = TREE_VALUE (link);
1100*e4b17023SJohn Marino
1101*e4b17023SJohn Marino if (TREE_CODE (input) != SSA_NAME)
1102*e4b17023SJohn Marino continue;
1103*e4b17023SJohn Marino
1104*e4b17023SJohn Marino match = strtoul (constraint, &end, 10);
1105*e4b17023SJohn Marino if (match >= noutputs || end == constraint)
1106*e4b17023SJohn Marino continue;
1107*e4b17023SJohn Marino
1108*e4b17023SJohn Marino if (TREE_CODE (outputs[match]) != SSA_NAME)
1109*e4b17023SJohn Marino continue;
1110*e4b17023SJohn Marino
1111*e4b17023SJohn Marino v1 = SSA_NAME_VERSION (outputs[match]);
1112*e4b17023SJohn Marino v2 = SSA_NAME_VERSION (input);
1113*e4b17023SJohn Marino
1114*e4b17023SJohn Marino if (SSA_NAME_VAR (outputs[match]) == SSA_NAME_VAR (input))
1115*e4b17023SJohn Marino {
1116*e4b17023SJohn Marino cost = coalesce_cost (REG_BR_PROB_BASE,
1117*e4b17023SJohn Marino optimize_bb_for_size_p (bb));
1118*e4b17023SJohn Marino add_coalesce (cl, v1, v2, cost);
1119*e4b17023SJohn Marino bitmap_set_bit (used_in_copy, v1);
1120*e4b17023SJohn Marino bitmap_set_bit (used_in_copy, v2);
1121*e4b17023SJohn Marino }
1122*e4b17023SJohn Marino }
1123*e4b17023SJohn Marino break;
1124*e4b17023SJohn Marino }
1125*e4b17023SJohn Marino
1126*e4b17023SJohn Marino default:
1127*e4b17023SJohn Marino break;
1128*e4b17023SJohn Marino }
1129*e4b17023SJohn Marino
1130*e4b17023SJohn Marino #ifdef ENABLE_CHECKING
1131*e4b17023SJohn Marino /* Mark real uses and defs. */
1132*e4b17023SJohn Marino FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
1133*e4b17023SJohn Marino bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (var)));
1134*e4b17023SJohn Marino
1135*e4b17023SJohn Marino /* Validate that virtual ops don't get used in funny ways. */
1136*e4b17023SJohn Marino if (gimple_vuse (stmt))
1137*e4b17023SJohn Marino bitmap_set_bit (used_in_virtual_ops,
1138*e4b17023SJohn Marino DECL_UID (SSA_NAME_VAR (gimple_vuse (stmt))));
1139*e4b17023SJohn Marino #endif /* ENABLE_CHECKING */
1140*e4b17023SJohn Marino }
1141*e4b17023SJohn Marino }
1142*e4b17023SJohn Marino
1143*e4b17023SJohn Marino /* Now process result decls and live on entry variables for entry into
1144*e4b17023SJohn Marino the coalesce list. */
1145*e4b17023SJohn Marino first = NULL_TREE;
1146*e4b17023SJohn Marino for (i = 1; i < num_ssa_names; i++)
1147*e4b17023SJohn Marino {
1148*e4b17023SJohn Marino var = ssa_name (i);
1149*e4b17023SJohn Marino if (var != NULL_TREE && is_gimple_reg (var))
1150*e4b17023SJohn Marino {
1151*e4b17023SJohn Marino /* Add coalesces between all the result decls. */
1152*e4b17023SJohn Marino if (TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
1153*e4b17023SJohn Marino {
1154*e4b17023SJohn Marino if (first == NULL_TREE)
1155*e4b17023SJohn Marino first = var;
1156*e4b17023SJohn Marino else
1157*e4b17023SJohn Marino {
1158*e4b17023SJohn Marino gcc_assert (SSA_NAME_VAR (var) == SSA_NAME_VAR (first));
1159*e4b17023SJohn Marino v1 = SSA_NAME_VERSION (first);
1160*e4b17023SJohn Marino v2 = SSA_NAME_VERSION (var);
1161*e4b17023SJohn Marino bitmap_set_bit (used_in_copy, v1);
1162*e4b17023SJohn Marino bitmap_set_bit (used_in_copy, v2);
1163*e4b17023SJohn Marino cost = coalesce_cost_bb (EXIT_BLOCK_PTR);
1164*e4b17023SJohn Marino add_coalesce (cl, v1, v2, cost);
1165*e4b17023SJohn Marino }
1166*e4b17023SJohn Marino }
1167*e4b17023SJohn Marino /* Mark any default_def variables as being in the coalesce list
1168*e4b17023SJohn Marino since they will have to be coalesced with the base variable. If
1169*e4b17023SJohn Marino not marked as present, they won't be in the coalesce view. */
1170*e4b17023SJohn Marino if (gimple_default_def (cfun, SSA_NAME_VAR (var)) == var
1171*e4b17023SJohn Marino && !has_zero_uses (var))
1172*e4b17023SJohn Marino bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1173*e4b17023SJohn Marino }
1174*e4b17023SJohn Marino }
1175*e4b17023SJohn Marino
1176*e4b17023SJohn Marino #if defined ENABLE_CHECKING
1177*e4b17023SJohn Marino {
1178*e4b17023SJohn Marino unsigned i;
1179*e4b17023SJohn Marino bitmap both = BITMAP_ALLOC (NULL);
1180*e4b17023SJohn Marino bitmap_and (both, used_in_real_ops, used_in_virtual_ops);
1181*e4b17023SJohn Marino if (!bitmap_empty_p (both))
1182*e4b17023SJohn Marino {
1183*e4b17023SJohn Marino bitmap_iterator bi;
1184*e4b17023SJohn Marino
1185*e4b17023SJohn Marino EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi)
1186*e4b17023SJohn Marino fprintf (stderr, "Variable %s used in real and virtual operands\n",
1187*e4b17023SJohn Marino get_name (referenced_var (i)));
1188*e4b17023SJohn Marino internal_error ("SSA corruption");
1189*e4b17023SJohn Marino }
1190*e4b17023SJohn Marino
1191*e4b17023SJohn Marino BITMAP_FREE (used_in_real_ops);
1192*e4b17023SJohn Marino BITMAP_FREE (used_in_virtual_ops);
1193*e4b17023SJohn Marino BITMAP_FREE (both);
1194*e4b17023SJohn Marino }
1195*e4b17023SJohn Marino #endif
1196*e4b17023SJohn Marino
1197*e4b17023SJohn Marino return map;
1198*e4b17023SJohn Marino }
1199*e4b17023SJohn Marino
1200*e4b17023SJohn Marino
1201*e4b17023SJohn Marino /* Attempt to coalesce ssa versions X and Y together using the partition
1202*e4b17023SJohn Marino mapping in MAP and checking conflicts in GRAPH. Output any debug info to
1203*e4b17023SJohn Marino DEBUG, if it is nun-NULL. */
1204*e4b17023SJohn Marino
1205*e4b17023SJohn Marino static inline bool
attempt_coalesce(var_map map,ssa_conflicts_p graph,int x,int y,FILE * debug)1206*e4b17023SJohn Marino attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y,
1207*e4b17023SJohn Marino FILE *debug)
1208*e4b17023SJohn Marino {
1209*e4b17023SJohn Marino int z;
1210*e4b17023SJohn Marino tree var1, var2;
1211*e4b17023SJohn Marino int p1, p2;
1212*e4b17023SJohn Marino
1213*e4b17023SJohn Marino p1 = var_to_partition (map, ssa_name (x));
1214*e4b17023SJohn Marino p2 = var_to_partition (map, ssa_name (y));
1215*e4b17023SJohn Marino
1216*e4b17023SJohn Marino if (debug)
1217*e4b17023SJohn Marino {
1218*e4b17023SJohn Marino fprintf (debug, "(%d)", x);
1219*e4b17023SJohn Marino print_generic_expr (debug, partition_to_var (map, p1), TDF_SLIM);
1220*e4b17023SJohn Marino fprintf (debug, " & (%d)", y);
1221*e4b17023SJohn Marino print_generic_expr (debug, partition_to_var (map, p2), TDF_SLIM);
1222*e4b17023SJohn Marino }
1223*e4b17023SJohn Marino
1224*e4b17023SJohn Marino if (p1 == p2)
1225*e4b17023SJohn Marino {
1226*e4b17023SJohn Marino if (debug)
1227*e4b17023SJohn Marino fprintf (debug, ": Already Coalesced.\n");
1228*e4b17023SJohn Marino return true;
1229*e4b17023SJohn Marino }
1230*e4b17023SJohn Marino
1231*e4b17023SJohn Marino if (debug)
1232*e4b17023SJohn Marino fprintf (debug, " [map: %d, %d] ", p1, p2);
1233*e4b17023SJohn Marino
1234*e4b17023SJohn Marino
1235*e4b17023SJohn Marino if (!ssa_conflicts_test_p (graph, p1, p2))
1236*e4b17023SJohn Marino {
1237*e4b17023SJohn Marino var1 = partition_to_var (map, p1);
1238*e4b17023SJohn Marino var2 = partition_to_var (map, p2);
1239*e4b17023SJohn Marino z = var_union (map, var1, var2);
1240*e4b17023SJohn Marino if (z == NO_PARTITION)
1241*e4b17023SJohn Marino {
1242*e4b17023SJohn Marino if (debug)
1243*e4b17023SJohn Marino fprintf (debug, ": Unable to perform partition union.\n");
1244*e4b17023SJohn Marino return false;
1245*e4b17023SJohn Marino }
1246*e4b17023SJohn Marino
1247*e4b17023SJohn Marino /* z is the new combined partition. Remove the other partition from
1248*e4b17023SJohn Marino the list, and merge the conflicts. */
1249*e4b17023SJohn Marino if (z == p1)
1250*e4b17023SJohn Marino ssa_conflicts_merge (graph, p1, p2);
1251*e4b17023SJohn Marino else
1252*e4b17023SJohn Marino ssa_conflicts_merge (graph, p2, p1);
1253*e4b17023SJohn Marino
1254*e4b17023SJohn Marino if (debug)
1255*e4b17023SJohn Marino fprintf (debug, ": Success -> %d\n", z);
1256*e4b17023SJohn Marino return true;
1257*e4b17023SJohn Marino }
1258*e4b17023SJohn Marino
1259*e4b17023SJohn Marino if (debug)
1260*e4b17023SJohn Marino fprintf (debug, ": Fail due to conflict\n");
1261*e4b17023SJohn Marino
1262*e4b17023SJohn Marino return false;
1263*e4b17023SJohn Marino }
1264*e4b17023SJohn Marino
1265*e4b17023SJohn Marino
1266*e4b17023SJohn Marino /* Attempt to Coalesce partitions in MAP which occur in the list CL using
1267*e4b17023SJohn Marino GRAPH. Debug output is sent to DEBUG if it is non-NULL. */
1268*e4b17023SJohn Marino
1269*e4b17023SJohn Marino static void
coalesce_partitions(var_map map,ssa_conflicts_p graph,coalesce_list_p cl,FILE * debug)1270*e4b17023SJohn Marino coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl,
1271*e4b17023SJohn Marino FILE *debug)
1272*e4b17023SJohn Marino {
1273*e4b17023SJohn Marino int x = 0, y = 0;
1274*e4b17023SJohn Marino tree var1, var2;
1275*e4b17023SJohn Marino int cost;
1276*e4b17023SJohn Marino basic_block bb;
1277*e4b17023SJohn Marino edge e;
1278*e4b17023SJohn Marino edge_iterator ei;
1279*e4b17023SJohn Marino
1280*e4b17023SJohn Marino /* First, coalesce all the copies across abnormal edges. These are not placed
1281*e4b17023SJohn Marino in the coalesce list because they do not need to be sorted, and simply
1282*e4b17023SJohn Marino consume extra memory/compilation time in large programs. */
1283*e4b17023SJohn Marino
1284*e4b17023SJohn Marino FOR_EACH_BB (bb)
1285*e4b17023SJohn Marino {
1286*e4b17023SJohn Marino FOR_EACH_EDGE (e, ei, bb->preds)
1287*e4b17023SJohn Marino if (e->flags & EDGE_ABNORMAL)
1288*e4b17023SJohn Marino {
1289*e4b17023SJohn Marino gimple_stmt_iterator gsi;
1290*e4b17023SJohn Marino for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1291*e4b17023SJohn Marino gsi_next (&gsi))
1292*e4b17023SJohn Marino {
1293*e4b17023SJohn Marino gimple phi = gsi_stmt (gsi);
1294*e4b17023SJohn Marino tree res = PHI_RESULT (phi);
1295*e4b17023SJohn Marino tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1296*e4b17023SJohn Marino int v1 = SSA_NAME_VERSION (res);
1297*e4b17023SJohn Marino int v2 = SSA_NAME_VERSION (arg);
1298*e4b17023SJohn Marino
1299*e4b17023SJohn Marino if (SSA_NAME_VAR (arg) != SSA_NAME_VAR (res))
1300*e4b17023SJohn Marino abnormal_corrupt (phi, e->dest_idx);
1301*e4b17023SJohn Marino
1302*e4b17023SJohn Marino if (debug)
1303*e4b17023SJohn Marino fprintf (debug, "Abnormal coalesce: ");
1304*e4b17023SJohn Marino
1305*e4b17023SJohn Marino if (!attempt_coalesce (map, graph, v1, v2, debug))
1306*e4b17023SJohn Marino fail_abnormal_edge_coalesce (v1, v2);
1307*e4b17023SJohn Marino }
1308*e4b17023SJohn Marino }
1309*e4b17023SJohn Marino }
1310*e4b17023SJohn Marino
1311*e4b17023SJohn Marino /* Now process the items in the coalesce list. */
1312*e4b17023SJohn Marino
1313*e4b17023SJohn Marino while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE)
1314*e4b17023SJohn Marino {
1315*e4b17023SJohn Marino var1 = ssa_name (x);
1316*e4b17023SJohn Marino var2 = ssa_name (y);
1317*e4b17023SJohn Marino
1318*e4b17023SJohn Marino /* Assert the coalesces have the same base variable. */
1319*e4b17023SJohn Marino gcc_assert (SSA_NAME_VAR (var1) == SSA_NAME_VAR (var2));
1320*e4b17023SJohn Marino
1321*e4b17023SJohn Marino if (debug)
1322*e4b17023SJohn Marino fprintf (debug, "Coalesce list: ");
1323*e4b17023SJohn Marino attempt_coalesce (map, graph, x, y, debug);
1324*e4b17023SJohn Marino }
1325*e4b17023SJohn Marino }
1326*e4b17023SJohn Marino
1327*e4b17023SJohn Marino /* Returns a hash code for P. */
1328*e4b17023SJohn Marino
1329*e4b17023SJohn Marino static hashval_t
hash_ssa_name_by_var(const void * p)1330*e4b17023SJohn Marino hash_ssa_name_by_var (const void *p)
1331*e4b17023SJohn Marino {
1332*e4b17023SJohn Marino const_tree n = (const_tree) p;
1333*e4b17023SJohn Marino return (hashval_t) htab_hash_pointer (SSA_NAME_VAR (n));
1334*e4b17023SJohn Marino }
1335*e4b17023SJohn Marino
1336*e4b17023SJohn Marino /* Returns nonzero if P1 and P2 are equal. */
1337*e4b17023SJohn Marino
1338*e4b17023SJohn Marino static int
eq_ssa_name_by_var(const void * p1,const void * p2)1339*e4b17023SJohn Marino eq_ssa_name_by_var (const void *p1, const void *p2)
1340*e4b17023SJohn Marino {
1341*e4b17023SJohn Marino const_tree n1 = (const_tree) p1;
1342*e4b17023SJohn Marino const_tree n2 = (const_tree) p2;
1343*e4b17023SJohn Marino return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
1344*e4b17023SJohn Marino }
1345*e4b17023SJohn Marino
1346*e4b17023SJohn Marino /* Reduce the number of copies by coalescing variables in the function. Return
1347*e4b17023SJohn Marino a partition map with the resulting coalesces. */
1348*e4b17023SJohn Marino
1349*e4b17023SJohn Marino extern var_map
coalesce_ssa_name(void)1350*e4b17023SJohn Marino coalesce_ssa_name (void)
1351*e4b17023SJohn Marino {
1352*e4b17023SJohn Marino tree_live_info_p liveinfo;
1353*e4b17023SJohn Marino ssa_conflicts_p graph;
1354*e4b17023SJohn Marino coalesce_list_p cl;
1355*e4b17023SJohn Marino bitmap used_in_copies = BITMAP_ALLOC (NULL);
1356*e4b17023SJohn Marino var_map map;
1357*e4b17023SJohn Marino unsigned int i;
1358*e4b17023SJohn Marino static htab_t ssa_name_hash;
1359*e4b17023SJohn Marino
1360*e4b17023SJohn Marino cl = create_coalesce_list ();
1361*e4b17023SJohn Marino map = create_outofssa_var_map (cl, used_in_copies);
1362*e4b17023SJohn Marino
1363*e4b17023SJohn Marino /* We need to coalesce all names originating same SSA_NAME_VAR
1364*e4b17023SJohn Marino so debug info remains undisturbed. */
1365*e4b17023SJohn Marino if (!optimize)
1366*e4b17023SJohn Marino {
1367*e4b17023SJohn Marino ssa_name_hash = htab_create (10, hash_ssa_name_by_var,
1368*e4b17023SJohn Marino eq_ssa_name_by_var, NULL);
1369*e4b17023SJohn Marino for (i = 1; i < num_ssa_names; i++)
1370*e4b17023SJohn Marino {
1371*e4b17023SJohn Marino tree a = ssa_name (i);
1372*e4b17023SJohn Marino
1373*e4b17023SJohn Marino if (a
1374*e4b17023SJohn Marino && SSA_NAME_VAR (a)
1375*e4b17023SJohn Marino && !DECL_IGNORED_P (SSA_NAME_VAR (a))
1376*e4b17023SJohn Marino && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)))
1377*e4b17023SJohn Marino {
1378*e4b17023SJohn Marino tree *slot = (tree *) htab_find_slot (ssa_name_hash, a, INSERT);
1379*e4b17023SJohn Marino
1380*e4b17023SJohn Marino if (!*slot)
1381*e4b17023SJohn Marino *slot = a;
1382*e4b17023SJohn Marino else
1383*e4b17023SJohn Marino {
1384*e4b17023SJohn Marino add_coalesce (cl, SSA_NAME_VERSION (a), SSA_NAME_VERSION (*slot),
1385*e4b17023SJohn Marino MUST_COALESCE_COST - 1);
1386*e4b17023SJohn Marino bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (a));
1387*e4b17023SJohn Marino bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (*slot));
1388*e4b17023SJohn Marino }
1389*e4b17023SJohn Marino }
1390*e4b17023SJohn Marino }
1391*e4b17023SJohn Marino htab_delete (ssa_name_hash);
1392*e4b17023SJohn Marino }
1393*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_DETAILS))
1394*e4b17023SJohn Marino dump_var_map (dump_file, map);
1395*e4b17023SJohn Marino
1396*e4b17023SJohn Marino /* Don't calculate live ranges for variables not in the coalesce list. */
1397*e4b17023SJohn Marino partition_view_bitmap (map, used_in_copies, true);
1398*e4b17023SJohn Marino BITMAP_FREE (used_in_copies);
1399*e4b17023SJohn Marino
1400*e4b17023SJohn Marino if (num_var_partitions (map) < 1)
1401*e4b17023SJohn Marino {
1402*e4b17023SJohn Marino delete_coalesce_list (cl);
1403*e4b17023SJohn Marino return map;
1404*e4b17023SJohn Marino }
1405*e4b17023SJohn Marino
1406*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_DETAILS))
1407*e4b17023SJohn Marino dump_var_map (dump_file, map);
1408*e4b17023SJohn Marino
1409*e4b17023SJohn Marino liveinfo = calculate_live_ranges (map);
1410*e4b17023SJohn Marino
1411*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_DETAILS))
1412*e4b17023SJohn Marino dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY);
1413*e4b17023SJohn Marino
1414*e4b17023SJohn Marino /* Build a conflict graph. */
1415*e4b17023SJohn Marino graph = build_ssa_conflict_graph (liveinfo);
1416*e4b17023SJohn Marino delete_tree_live_info (liveinfo);
1417*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_DETAILS))
1418*e4b17023SJohn Marino ssa_conflicts_dump (dump_file, graph);
1419*e4b17023SJohn Marino
1420*e4b17023SJohn Marino sort_coalesce_list (cl);
1421*e4b17023SJohn Marino
1422*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_DETAILS))
1423*e4b17023SJohn Marino {
1424*e4b17023SJohn Marino fprintf (dump_file, "\nAfter sorting:\n");
1425*e4b17023SJohn Marino dump_coalesce_list (dump_file, cl);
1426*e4b17023SJohn Marino }
1427*e4b17023SJohn Marino
1428*e4b17023SJohn Marino /* First, coalesce all live on entry variables to their base variable.
1429*e4b17023SJohn Marino This will ensure the first use is coming from the correct location. */
1430*e4b17023SJohn Marino
1431*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_DETAILS))
1432*e4b17023SJohn Marino dump_var_map (dump_file, map);
1433*e4b17023SJohn Marino
1434*e4b17023SJohn Marino /* Now coalesce everything in the list. */
1435*e4b17023SJohn Marino coalesce_partitions (map, graph, cl,
1436*e4b17023SJohn Marino ((dump_flags & TDF_DETAILS) ? dump_file
1437*e4b17023SJohn Marino : NULL));
1438*e4b17023SJohn Marino
1439*e4b17023SJohn Marino delete_coalesce_list (cl);
1440*e4b17023SJohn Marino ssa_conflicts_delete (graph);
1441*e4b17023SJohn Marino
1442*e4b17023SJohn Marino return map;
1443*e4b17023SJohn Marino }
1444