xref: /dragonfly/contrib/gcc-8.0/gcc/ira-color.c (revision 38fd1498)
1 /* IRA allocation based on graph coloring.
2    Copyright (C) 2006-2018 Free Software Foundation, Inc.
3    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4 
5 This file is part of GCC.
6 
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11 
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16 
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/>.  */
20 
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "backend.h"
25 #include "target.h"
26 #include "rtl.h"
27 #include "tree.h"
28 #include "predict.h"
29 #include "df.h"
30 #include "memmodel.h"
31 #include "tm_p.h"
32 #include "insn-config.h"
33 #include "regs.h"
34 #include "ira.h"
35 #include "ira-int.h"
36 #include "reload.h"
37 #include "cfgloop.h"
38 
39 typedef struct allocno_hard_regs *allocno_hard_regs_t;
40 
41 /* The structure contains information about hard registers can be
42    assigned to allocnos.  Usually it is allocno profitable hard
43    registers but in some cases this set can be a bit different.  Major
44    reason of the difference is a requirement to use hard register sets
45    that form a tree or a forest (set of trees), i.e. hard register set
46    of a node should contain hard register sets of its subnodes.  */
47 struct allocno_hard_regs
48 {
49   /* Hard registers can be assigned to an allocno.  */
50   HARD_REG_SET set;
51   /* Overall (spilling) cost of all allocnos with given register
52      set.  */
53   int64_t cost;
54 };
55 
56 typedef struct allocno_hard_regs_node *allocno_hard_regs_node_t;
57 
58 /* A node representing allocno hard registers.  Such nodes form a
59    forest (set of trees).  Each subnode of given node in the forest
60    refers for hard register set (usually allocno profitable hard
61    register set) which is a subset of one referred from given
62    node.  */
63 struct allocno_hard_regs_node
64 {
65   /* Set up number of the node in preorder traversing of the forest.  */
66   int preorder_num;
67   /* Used for different calculation like finding conflict size of an
68      allocno.  */
69   int check;
70   /* Used for calculation of conflict size of an allocno.  The
71      conflict size of the allocno is maximal number of given allocno
72      hard registers needed for allocation of the conflicting allocnos.
73      Given allocno is trivially colored if this number plus the number
74      of hard registers needed for given allocno is not greater than
75      the number of given allocno hard register set.  */
76   int conflict_size;
77   /* The number of hard registers given by member hard_regs.  */
78   int hard_regs_num;
79   /* The following member is used to form the final forest.  */
80   bool used_p;
81   /* Pointer to the corresponding profitable hard registers.  */
82   allocno_hard_regs_t hard_regs;
83   /* Parent, first subnode, previous and next node with the same
84      parent in the forest.  */
85   allocno_hard_regs_node_t parent, first, prev, next;
86 };
87 
88 /* Info about changing hard reg costs of an allocno.  */
89 struct update_cost_record
90 {
91   /* Hard regno for which we changed the cost.  */
92   int hard_regno;
93   /* Divisor used when we changed the cost of HARD_REGNO.  */
94   int divisor;
95   /* Next record for given allocno.  */
96   struct update_cost_record *next;
97 };
98 
99 /* To decrease footprint of ira_allocno structure we store all data
100    needed only for coloring in the following structure.  */
101 struct allocno_color_data
102 {
103   /* TRUE value means that the allocno was not removed yet from the
104      conflicting graph during coloring.  */
105   unsigned int in_graph_p : 1;
106   /* TRUE if it is put on the stack to make other allocnos
107      colorable.  */
108   unsigned int may_be_spilled_p : 1;
109   /* TRUE if the allocno is trivially colorable.  */
110   unsigned int colorable_p : 1;
111   /* Number of hard registers of the allocno class really
112      available for the allocno allocation.  It is number of the
113      profitable hard regs.  */
114   int available_regs_num;
115   /* Sum of frequencies of hard register preferences of all
116      conflicting allocnos which are not the coloring stack yet.  */
117   int conflict_allocno_hard_prefs;
118   /* Allocnos in a bucket (used in coloring) chained by the following
119      two members.  */
120   ira_allocno_t next_bucket_allocno;
121   ira_allocno_t prev_bucket_allocno;
122   /* Used for temporary purposes.  */
123   int temp;
124   /* Used to exclude repeated processing.  */
125   int last_process;
126   /* Profitable hard regs available for this pseudo allocation.  It
127      means that the set excludes unavailable hard regs and hard regs
128      conflicting with given pseudo.  They should be of the allocno
129      class.  */
130   HARD_REG_SET profitable_hard_regs;
131   /* The allocno hard registers node.  */
132   allocno_hard_regs_node_t hard_regs_node;
133   /* Array of structures allocno_hard_regs_subnode representing
134      given allocno hard registers node (the 1st element in the array)
135      and all its subnodes in the tree (forest) of allocno hard
136      register nodes (see comments above).  */
137   int hard_regs_subnodes_start;
138   /* The length of the previous array.  */
139   int hard_regs_subnodes_num;
140   /* Records about updating allocno hard reg costs from copies.  If
141      the allocno did not get expected hard register, these records are
142      used to restore original hard reg costs of allocnos connected to
143      this allocno by copies.  */
144   struct update_cost_record *update_cost_records;
145   /* Threads.  We collect allocnos connected by copies into threads
146      and try to assign hard regs to allocnos by threads.  */
147   /* Allocno representing all thread.  */
148   ira_allocno_t first_thread_allocno;
149   /* Allocnos in thread forms a cycle list through the following
150      member.  */
151   ira_allocno_t next_thread_allocno;
152   /* All thread frequency.  Defined only for first thread allocno.  */
153   int thread_freq;
154 };
155 
156 /* See above.  */
157 typedef struct allocno_color_data *allocno_color_data_t;
158 
159 /* Container for storing allocno data concerning coloring.  */
160 static allocno_color_data_t allocno_color_data;
161 
162 /* Macro to access the data concerning coloring.  */
163 #define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a))
164 
165 /* Used for finding allocno colorability to exclude repeated allocno
166    processing and for updating preferencing to exclude repeated
167    allocno processing during assignment.  */
168 static int curr_allocno_process;
169 
170 /* This file contains code for regional graph coloring, spill/restore
171    code placement optimization, and code helping the reload pass to do
172    a better job.  */
173 
174 /* Bitmap of allocnos which should be colored.  */
175 static bitmap coloring_allocno_bitmap;
176 
177 /* Bitmap of allocnos which should be taken into account during
178    coloring.  In general case it contains allocnos from
179    coloring_allocno_bitmap plus other already colored conflicting
180    allocnos.  */
181 static bitmap consideration_allocno_bitmap;
182 
183 /* All allocnos sorted according their priorities.  */
184 static ira_allocno_t *sorted_allocnos;
185 
186 /* Vec representing the stack of allocnos used during coloring.  */
187 static vec<ira_allocno_t> allocno_stack_vec;
188 
189 /* Helper for qsort comparison callbacks - return a positive integer if
190    X > Y, or a negative value otherwise.  Use a conditional expression
191    instead of a difference computation to insulate from possible overflow
192    issues, e.g. X - Y < 0 for some X > 0 and Y < 0.  */
193 #define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
194 
195 
196 
197 /* Definition of vector of allocno hard registers.  */
198 
199 /* Vector of unique allocno hard registers.  */
200 static vec<allocno_hard_regs_t> allocno_hard_regs_vec;
201 
202 struct allocno_hard_regs_hasher : nofree_ptr_hash <allocno_hard_regs>
203 {
204   static inline hashval_t hash (const allocno_hard_regs *);
205   static inline bool equal (const allocno_hard_regs *,
206 			    const allocno_hard_regs *);
207 };
208 
209 /* Returns hash value for allocno hard registers V.  */
210 inline hashval_t
hash(const allocno_hard_regs * hv)211 allocno_hard_regs_hasher::hash (const allocno_hard_regs *hv)
212 {
213   return iterative_hash (&hv->set, sizeof (HARD_REG_SET), 0);
214 }
215 
216 /* Compares allocno hard registers V1 and V2.  */
217 inline bool
equal(const allocno_hard_regs * hv1,const allocno_hard_regs * hv2)218 allocno_hard_regs_hasher::equal (const allocno_hard_regs *hv1,
219 				 const allocno_hard_regs *hv2)
220 {
221   return hard_reg_set_equal_p (hv1->set, hv2->set);
222 }
223 
224 /* Hash table of unique allocno hard registers.  */
225 static hash_table<allocno_hard_regs_hasher> *allocno_hard_regs_htab;
226 
227 /* Return allocno hard registers in the hash table equal to HV.  */
228 static allocno_hard_regs_t
find_hard_regs(allocno_hard_regs_t hv)229 find_hard_regs (allocno_hard_regs_t hv)
230 {
231   return allocno_hard_regs_htab->find (hv);
232 }
233 
234 /* Insert allocno hard registers HV in the hash table (if it is not
235    there yet) and return the value which in the table.  */
236 static allocno_hard_regs_t
insert_hard_regs(allocno_hard_regs_t hv)237 insert_hard_regs (allocno_hard_regs_t hv)
238 {
239   allocno_hard_regs **slot = allocno_hard_regs_htab->find_slot (hv, INSERT);
240 
241   if (*slot == NULL)
242     *slot = hv;
243   return *slot;
244 }
245 
246 /* Initialize data concerning allocno hard registers.  */
247 static void
init_allocno_hard_regs(void)248 init_allocno_hard_regs (void)
249 {
250   allocno_hard_regs_vec.create (200);
251   allocno_hard_regs_htab
252     = new hash_table<allocno_hard_regs_hasher> (200);
253 }
254 
255 /* Add (or update info about) allocno hard registers with SET and
256    COST.  */
257 static allocno_hard_regs_t
add_allocno_hard_regs(HARD_REG_SET set,int64_t cost)258 add_allocno_hard_regs (HARD_REG_SET set, int64_t cost)
259 {
260   struct allocno_hard_regs temp;
261   allocno_hard_regs_t hv;
262 
263   gcc_assert (! hard_reg_set_empty_p (set));
264   COPY_HARD_REG_SET (temp.set, set);
265   if ((hv = find_hard_regs (&temp)) != NULL)
266     hv->cost += cost;
267   else
268     {
269       hv = ((struct allocno_hard_regs *)
270 	    ira_allocate (sizeof (struct allocno_hard_regs)));
271       COPY_HARD_REG_SET (hv->set, set);
272       hv->cost = cost;
273       allocno_hard_regs_vec.safe_push (hv);
274       insert_hard_regs (hv);
275     }
276   return hv;
277 }
278 
279 /* Finalize data concerning allocno hard registers.  */
280 static void
finish_allocno_hard_regs(void)281 finish_allocno_hard_regs (void)
282 {
283   int i;
284   allocno_hard_regs_t hv;
285 
286   for (i = 0;
287        allocno_hard_regs_vec.iterate (i, &hv);
288        i++)
289     ira_free (hv);
290   delete allocno_hard_regs_htab;
291   allocno_hard_regs_htab = NULL;
292   allocno_hard_regs_vec.release ();
293 }
294 
295 /* Sort hard regs according to their frequency of usage. */
296 static int
allocno_hard_regs_compare(const void * v1p,const void * v2p)297 allocno_hard_regs_compare (const void *v1p, const void *v2p)
298 {
299   allocno_hard_regs_t hv1 = *(const allocno_hard_regs_t *) v1p;
300   allocno_hard_regs_t hv2 = *(const allocno_hard_regs_t *) v2p;
301 
302   if (hv2->cost > hv1->cost)
303     return 1;
304   else if (hv2->cost < hv1->cost)
305     return -1;
306   return SORTGT (allocno_hard_regs_hasher::hash(hv2), allocno_hard_regs_hasher::hash(hv1));
307 }
308 
309 
310 
311 /* Used for finding a common ancestor of two allocno hard registers
312    nodes in the forest.  We use the current value of
313    'node_check_tick' to mark all nodes from one node to the top and
314    then walking up from another node until we find a marked node.
315 
316    It is also used to figure out allocno colorability as a mark that
317    we already reset value of member 'conflict_size' for the forest
318    node corresponding to the processed allocno.  */
319 static int node_check_tick;
320 
321 /* Roots of the forest containing hard register sets can be assigned
322    to allocnos.  */
323 static allocno_hard_regs_node_t hard_regs_roots;
324 
325 /* Definition of vector of allocno hard register nodes.  */
326 
327 /* Vector used to create the forest.  */
328 static vec<allocno_hard_regs_node_t> hard_regs_node_vec;
329 
330 /* Create and return allocno hard registers node containing allocno
331    hard registers HV.  */
332 static allocno_hard_regs_node_t
create_new_allocno_hard_regs_node(allocno_hard_regs_t hv)333 create_new_allocno_hard_regs_node (allocno_hard_regs_t hv)
334 {
335   allocno_hard_regs_node_t new_node;
336 
337   new_node = ((struct allocno_hard_regs_node *)
338 	      ira_allocate (sizeof (struct allocno_hard_regs_node)));
339   new_node->check = 0;
340   new_node->hard_regs = hv;
341   new_node->hard_regs_num = hard_reg_set_size (hv->set);
342   new_node->first = NULL;
343   new_node->used_p = false;
344   return new_node;
345 }
346 
347 /* Add allocno hard registers node NEW_NODE to the forest on its level
348    given by ROOTS.  */
349 static void
add_new_allocno_hard_regs_node_to_forest(allocno_hard_regs_node_t * roots,allocno_hard_regs_node_t new_node)350 add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t *roots,
351 					  allocno_hard_regs_node_t new_node)
352 {
353   new_node->next = *roots;
354   if (new_node->next != NULL)
355     new_node->next->prev = new_node;
356   new_node->prev = NULL;
357   *roots = new_node;
358 }
359 
360 /* Add allocno hard registers HV (or its best approximation if it is
361    not possible) to the forest on its level given by ROOTS.  */
362 static void
add_allocno_hard_regs_to_forest(allocno_hard_regs_node_t * roots,allocno_hard_regs_t hv)363 add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t *roots,
364 				 allocno_hard_regs_t hv)
365 {
366   unsigned int i, start;
367   allocno_hard_regs_node_t node, prev, new_node;
368   HARD_REG_SET temp_set;
369   allocno_hard_regs_t hv2;
370 
371   start = hard_regs_node_vec.length ();
372   for (node = *roots; node != NULL; node = node->next)
373     {
374       if (hard_reg_set_equal_p (hv->set, node->hard_regs->set))
375 	return;
376       if (hard_reg_set_subset_p (hv->set, node->hard_regs->set))
377 	{
378 	  add_allocno_hard_regs_to_forest (&node->first, hv);
379 	  return;
380 	}
381       if (hard_reg_set_subset_p (node->hard_regs->set, hv->set))
382 	hard_regs_node_vec.safe_push (node);
383       else if (hard_reg_set_intersect_p (hv->set, node->hard_regs->set))
384 	{
385 	  COPY_HARD_REG_SET (temp_set, hv->set);
386 	  AND_HARD_REG_SET (temp_set, node->hard_regs->set);
387 	  hv2 = add_allocno_hard_regs (temp_set, hv->cost);
388 	  add_allocno_hard_regs_to_forest (&node->first, hv2);
389 	}
390     }
391   if (hard_regs_node_vec.length ()
392       > start + 1)
393     {
394       /* Create a new node which contains nodes in hard_regs_node_vec.  */
395       CLEAR_HARD_REG_SET (temp_set);
396       for (i = start;
397 	   i < hard_regs_node_vec.length ();
398 	   i++)
399 	{
400 	  node = hard_regs_node_vec[i];
401 	  IOR_HARD_REG_SET (temp_set, node->hard_regs->set);
402 	}
403       hv = add_allocno_hard_regs (temp_set, hv->cost);
404       new_node = create_new_allocno_hard_regs_node (hv);
405       prev = NULL;
406       for (i = start;
407 	   i < hard_regs_node_vec.length ();
408 	   i++)
409 	{
410 	  node = hard_regs_node_vec[i];
411 	  if (node->prev == NULL)
412 	    *roots = node->next;
413 	  else
414 	    node->prev->next = node->next;
415 	  if (node->next != NULL)
416 	    node->next->prev = node->prev;
417 	  if (prev == NULL)
418 	    new_node->first = node;
419 	  else
420 	    prev->next = node;
421 	  node->prev = prev;
422 	  node->next = NULL;
423 	  prev = node;
424 	}
425       add_new_allocno_hard_regs_node_to_forest (roots, new_node);
426     }
427   hard_regs_node_vec.truncate (start);
428 }
429 
430 /* Add allocno hard registers nodes starting with the forest level
431    given by FIRST which contains biggest set inside SET.  */
432 static void
collect_allocno_hard_regs_cover(allocno_hard_regs_node_t first,HARD_REG_SET set)433 collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first,
434 				 HARD_REG_SET set)
435 {
436   allocno_hard_regs_node_t node;
437 
438   ira_assert (first != NULL);
439   for (node = first; node != NULL; node = node->next)
440     if (hard_reg_set_subset_p (node->hard_regs->set, set))
441       hard_regs_node_vec.safe_push (node);
442     else if (hard_reg_set_intersect_p (set, node->hard_regs->set))
443       collect_allocno_hard_regs_cover (node->first, set);
444 }
445 
446 /* Set up field parent as PARENT in all allocno hard registers nodes
447    in forest given by FIRST.  */
448 static void
setup_allocno_hard_regs_nodes_parent(allocno_hard_regs_node_t first,allocno_hard_regs_node_t parent)449 setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first,
450 				      allocno_hard_regs_node_t parent)
451 {
452   allocno_hard_regs_node_t node;
453 
454   for (node = first; node != NULL; node = node->next)
455     {
456       node->parent = parent;
457       setup_allocno_hard_regs_nodes_parent (node->first, node);
458     }
459 }
460 
461 /* Return allocno hard registers node which is a first common ancestor
462    node of FIRST and SECOND in the forest.  */
463 static allocno_hard_regs_node_t
first_common_ancestor_node(allocno_hard_regs_node_t first,allocno_hard_regs_node_t second)464 first_common_ancestor_node (allocno_hard_regs_node_t first,
465 			    allocno_hard_regs_node_t second)
466 {
467   allocno_hard_regs_node_t node;
468 
469   node_check_tick++;
470   for (node = first; node != NULL; node = node->parent)
471     node->check = node_check_tick;
472   for (node = second; node != NULL; node = node->parent)
473     if (node->check == node_check_tick)
474       return node;
475   return first_common_ancestor_node (second, first);
476 }
477 
478 /* Print hard reg set SET to F.  */
479 static void
print_hard_reg_set(FILE * f,HARD_REG_SET set,bool new_line_p)480 print_hard_reg_set (FILE *f, HARD_REG_SET set, bool new_line_p)
481 {
482   int i, start;
483 
484   for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
485     {
486       if (TEST_HARD_REG_BIT (set, i))
487 	{
488 	  if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
489 	    start = i;
490 	}
491       if (start >= 0
492 	  && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
493 	{
494 	  if (start == i - 1)
495 	    fprintf (f, " %d", start);
496 	  else if (start == i - 2)
497 	    fprintf (f, " %d %d", start, start + 1);
498 	  else
499 	    fprintf (f, " %d-%d", start, i - 1);
500 	  start = -1;
501 	}
502     }
503   if (new_line_p)
504     fprintf (f, "\n");
505 }
506 
507 /* Print allocno hard register subforest given by ROOTS and its LEVEL
508    to F.  */
509 static void
print_hard_regs_subforest(FILE * f,allocno_hard_regs_node_t roots,int level)510 print_hard_regs_subforest (FILE *f, allocno_hard_regs_node_t roots,
511 			   int level)
512 {
513   int i;
514   allocno_hard_regs_node_t node;
515 
516   for (node = roots; node != NULL; node = node->next)
517     {
518       fprintf (f, "    ");
519       for (i = 0; i < level * 2; i++)
520 	fprintf (f, " ");
521       fprintf (f, "%d:(", node->preorder_num);
522       print_hard_reg_set (f, node->hard_regs->set, false);
523       fprintf (f, ")@%" PRId64"\n", node->hard_regs->cost);
524       print_hard_regs_subforest (f, node->first, level + 1);
525     }
526 }
527 
528 /* Print the allocno hard register forest to F.  */
529 static void
print_hard_regs_forest(FILE * f)530 print_hard_regs_forest (FILE *f)
531 {
532   fprintf (f, "    Hard reg set forest:\n");
533   print_hard_regs_subforest (f, hard_regs_roots, 1);
534 }
535 
536 /* Print the allocno hard register forest to stderr.  */
537 void
ira_debug_hard_regs_forest(void)538 ira_debug_hard_regs_forest (void)
539 {
540   print_hard_regs_forest (stderr);
541 }
542 
543 /* Remove unused allocno hard registers nodes from forest given by its
544    *ROOTS.  */
545 static void
remove_unused_allocno_hard_regs_nodes(allocno_hard_regs_node_t * roots)546 remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t *roots)
547 {
548   allocno_hard_regs_node_t node, prev, next, last;
549 
550   for (prev = NULL, node = *roots; node != NULL; node = next)
551     {
552       next = node->next;
553       if (node->used_p)
554 	{
555 	  remove_unused_allocno_hard_regs_nodes (&node->first);
556 	  prev = node;
557 	}
558       else
559 	{
560 	  for (last = node->first;
561 	       last != NULL && last->next != NULL;
562 	       last = last->next)
563 	    ;
564 	  if (last != NULL)
565 	    {
566 	      if (prev == NULL)
567 		*roots = node->first;
568 	      else
569 		prev->next = node->first;
570 	      if (next != NULL)
571 		next->prev = last;
572 	      last->next = next;
573 	      next = node->first;
574 	    }
575 	  else
576 	    {
577 	      if (prev == NULL)
578 		*roots = next;
579 	      else
580 		prev->next = next;
581 	      if (next != NULL)
582 		next->prev = prev;
583 	    }
584 	  ira_free (node);
585 	}
586     }
587 }
588 
589 /* Set up fields preorder_num starting with START_NUM in all allocno
590    hard registers nodes in forest given by FIRST.  Return biggest set
591    PREORDER_NUM increased by 1.  */
592 static int
enumerate_allocno_hard_regs_nodes(allocno_hard_regs_node_t first,allocno_hard_regs_node_t parent,int start_num)593 enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first,
594 				   allocno_hard_regs_node_t parent,
595 				   int start_num)
596 {
597   allocno_hard_regs_node_t node;
598 
599   for (node = first; node != NULL; node = node->next)
600     {
601       node->preorder_num = start_num++;
602       node->parent = parent;
603       start_num = enumerate_allocno_hard_regs_nodes (node->first, node,
604 						     start_num);
605     }
606   return start_num;
607 }
608 
609 /* Number of allocno hard registers nodes in the forest.  */
610 static int allocno_hard_regs_nodes_num;
611 
612 /* Table preorder number of allocno hard registers node in the forest
613    -> the allocno hard registers node.  */
614 static allocno_hard_regs_node_t *allocno_hard_regs_nodes;
615 
616 /* See below.  */
617 typedef struct allocno_hard_regs_subnode *allocno_hard_regs_subnode_t;
618 
619 /* The structure is used to describes all subnodes (not only immediate
620    ones) in the mentioned above tree for given allocno hard register
621    node.  The usage of such data accelerates calculation of
622    colorability of given allocno.  */
623 struct allocno_hard_regs_subnode
624 {
625   /* The conflict size of conflicting allocnos whose hard register
626      sets are equal sets (plus supersets if given node is given
627      allocno hard registers node) of one in the given node.  */
628   int left_conflict_size;
629   /* The summary conflict size of conflicting allocnos whose hard
630      register sets are strict subsets of one in the given node.
631      Overall conflict size is
632      left_conflict_subnodes_size
633        + MIN (max_node_impact - left_conflict_subnodes_size,
634               left_conflict_size)
635   */
636   short left_conflict_subnodes_size;
637   short max_node_impact;
638 };
639 
640 /* Container for hard regs subnodes of all allocnos.  */
641 static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes;
642 
643 /* Table (preorder number of allocno hard registers node in the
644    forest, preorder number of allocno hard registers subnode) -> index
645    of the subnode relative to the node.  -1 if it is not a
646    subnode.  */
647 static int *allocno_hard_regs_subnode_index;
648 
649 /* Setup arrays ALLOCNO_HARD_REGS_NODES and
650    ALLOCNO_HARD_REGS_SUBNODE_INDEX.  */
651 static void
setup_allocno_hard_regs_subnode_index(allocno_hard_regs_node_t first)652 setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first)
653 {
654   allocno_hard_regs_node_t node, parent;
655   int index;
656 
657   for (node = first; node != NULL; node = node->next)
658     {
659       allocno_hard_regs_nodes[node->preorder_num] = node;
660       for (parent = node; parent != NULL; parent = parent->parent)
661 	{
662 	  index = parent->preorder_num * allocno_hard_regs_nodes_num;
663 	  allocno_hard_regs_subnode_index[index + node->preorder_num]
664 	    = node->preorder_num - parent->preorder_num;
665 	}
666       setup_allocno_hard_regs_subnode_index (node->first);
667     }
668 }
669 
670 /* Count all allocno hard registers nodes in tree ROOT.  */
671 static int
get_allocno_hard_regs_subnodes_num(allocno_hard_regs_node_t root)672 get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root)
673 {
674   int len = 1;
675 
676   for (root = root->first; root != NULL; root = root->next)
677     len += get_allocno_hard_regs_subnodes_num (root);
678   return len;
679 }
680 
681 /* Build the forest of allocno hard registers nodes and assign each
682    allocno a node from the forest.  */
683 static void
form_allocno_hard_regs_nodes_forest(void)684 form_allocno_hard_regs_nodes_forest (void)
685 {
686   unsigned int i, j, size, len;
687   int start;
688   ira_allocno_t a;
689   allocno_hard_regs_t hv;
690   bitmap_iterator bi;
691   HARD_REG_SET temp;
692   allocno_hard_regs_node_t node, allocno_hard_regs_node;
693   allocno_color_data_t allocno_data;
694 
695   node_check_tick = 0;
696   init_allocno_hard_regs ();
697   hard_regs_roots = NULL;
698   hard_regs_node_vec.create (100);
699   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
700     if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
701       {
702 	CLEAR_HARD_REG_SET (temp);
703 	SET_HARD_REG_BIT (temp, i);
704 	hv = add_allocno_hard_regs (temp, 0);
705 	node = create_new_allocno_hard_regs_node (hv);
706 	add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots, node);
707       }
708   start = allocno_hard_regs_vec.length ();
709   EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
710     {
711       a = ira_allocnos[i];
712       allocno_data = ALLOCNO_COLOR_DATA (a);
713 
714       if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
715 	continue;
716       hv = (add_allocno_hard_regs
717 	    (allocno_data->profitable_hard_regs,
718 	     ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a)));
719     }
720   SET_HARD_REG_SET (temp);
721   AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
722   add_allocno_hard_regs (temp, 0);
723   qsort (allocno_hard_regs_vec.address () + start,
724 	 allocno_hard_regs_vec.length () - start,
725 	 sizeof (allocno_hard_regs_t), allocno_hard_regs_compare);
726   for (i = start;
727        allocno_hard_regs_vec.iterate (i, &hv);
728        i++)
729     {
730       add_allocno_hard_regs_to_forest (&hard_regs_roots, hv);
731       ira_assert (hard_regs_node_vec.length () == 0);
732     }
733   /* We need to set up parent fields for right work of
734      first_common_ancestor_node. */
735   setup_allocno_hard_regs_nodes_parent (hard_regs_roots, NULL);
736   EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
737     {
738       a = ira_allocnos[i];
739       allocno_data = ALLOCNO_COLOR_DATA (a);
740       if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
741 	continue;
742       hard_regs_node_vec.truncate (0);
743       collect_allocno_hard_regs_cover (hard_regs_roots,
744 				       allocno_data->profitable_hard_regs);
745       allocno_hard_regs_node = NULL;
746       for (j = 0; hard_regs_node_vec.iterate (j, &node); j++)
747 	allocno_hard_regs_node
748 	  = (j == 0
749 	     ? node
750 	     : first_common_ancestor_node (node, allocno_hard_regs_node));
751       /* That is a temporary storage.  */
752       allocno_hard_regs_node->used_p = true;
753       allocno_data->hard_regs_node = allocno_hard_regs_node;
754     }
755   ira_assert (hard_regs_roots->next == NULL);
756   hard_regs_roots->used_p = true;
757   remove_unused_allocno_hard_regs_nodes (&hard_regs_roots);
758   allocno_hard_regs_nodes_num
759     = enumerate_allocno_hard_regs_nodes (hard_regs_roots, NULL, 0);
760   allocno_hard_regs_nodes
761     = ((allocno_hard_regs_node_t *)
762        ira_allocate (allocno_hard_regs_nodes_num
763 		     * sizeof (allocno_hard_regs_node_t)));
764   size = allocno_hard_regs_nodes_num * allocno_hard_regs_nodes_num;
765   allocno_hard_regs_subnode_index
766     = (int *) ira_allocate (size * sizeof (int));
767   for (i = 0; i < size; i++)
768     allocno_hard_regs_subnode_index[i] = -1;
769   setup_allocno_hard_regs_subnode_index (hard_regs_roots);
770   start = 0;
771   EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
772     {
773       a = ira_allocnos[i];
774       allocno_data = ALLOCNO_COLOR_DATA (a);
775       if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
776 	continue;
777       len = get_allocno_hard_regs_subnodes_num (allocno_data->hard_regs_node);
778       allocno_data->hard_regs_subnodes_start = start;
779       allocno_data->hard_regs_subnodes_num = len;
780       start += len;
781     }
782   allocno_hard_regs_subnodes
783     = ((allocno_hard_regs_subnode_t)
784        ira_allocate (sizeof (struct allocno_hard_regs_subnode) * start));
785   hard_regs_node_vec.release ();
786 }
787 
788 /* Free tree of allocno hard registers nodes given by its ROOT.  */
789 static void
finish_allocno_hard_regs_nodes_tree(allocno_hard_regs_node_t root)790 finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root)
791 {
792   allocno_hard_regs_node_t child, next;
793 
794   for (child = root->first; child != NULL; child = next)
795     {
796       next = child->next;
797       finish_allocno_hard_regs_nodes_tree (child);
798     }
799   ira_free (root);
800 }
801 
802 /* Finish work with the forest of allocno hard registers nodes.  */
803 static void
finish_allocno_hard_regs_nodes_forest(void)804 finish_allocno_hard_regs_nodes_forest (void)
805 {
806   allocno_hard_regs_node_t node, next;
807 
808   ira_free (allocno_hard_regs_subnodes);
809   for (node = hard_regs_roots; node != NULL; node = next)
810     {
811       next = node->next;
812       finish_allocno_hard_regs_nodes_tree (node);
813     }
814   ira_free (allocno_hard_regs_nodes);
815   ira_free (allocno_hard_regs_subnode_index);
816   finish_allocno_hard_regs ();
817 }
818 
819 /* Set up left conflict sizes and left conflict subnodes sizes of hard
820    registers subnodes of allocno A.  Return TRUE if allocno A is
821    trivially colorable.  */
822 static bool
setup_left_conflict_sizes_p(ira_allocno_t a)823 setup_left_conflict_sizes_p (ira_allocno_t a)
824 {
825   int i, k, nobj, start;
826   int conflict_size, left_conflict_subnodes_size, node_preorder_num;
827   allocno_color_data_t data;
828   HARD_REG_SET profitable_hard_regs;
829   allocno_hard_regs_subnode_t subnodes;
830   allocno_hard_regs_node_t node;
831   HARD_REG_SET node_set;
832 
833   nobj = ALLOCNO_NUM_OBJECTS (a);
834   data = ALLOCNO_COLOR_DATA (a);
835   subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
836   COPY_HARD_REG_SET (profitable_hard_regs, data->profitable_hard_regs);
837   node = data->hard_regs_node;
838   node_preorder_num = node->preorder_num;
839   COPY_HARD_REG_SET (node_set, node->hard_regs->set);
840   node_check_tick++;
841   for (k = 0; k < nobj; k++)
842     {
843       ira_object_t obj = ALLOCNO_OBJECT (a, k);
844       ira_object_t conflict_obj;
845       ira_object_conflict_iterator oci;
846 
847       FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
848 	{
849 	  int size;
850  	  ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
851 	  allocno_hard_regs_node_t conflict_node, temp_node;
852 	  HARD_REG_SET conflict_node_set;
853 	  allocno_color_data_t conflict_data;
854 
855 	  conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
856 	  if (! ALLOCNO_COLOR_DATA (conflict_a)->in_graph_p
857 	      || ! hard_reg_set_intersect_p (profitable_hard_regs,
858 					     conflict_data
859 					     ->profitable_hard_regs))
860 	    continue;
861 	  conflict_node = conflict_data->hard_regs_node;
862 	  COPY_HARD_REG_SET (conflict_node_set, conflict_node->hard_regs->set);
863 	  if (hard_reg_set_subset_p (node_set, conflict_node_set))
864 	    temp_node = node;
865 	  else
866 	    {
867 	      ira_assert (hard_reg_set_subset_p (conflict_node_set, node_set));
868 	      temp_node = conflict_node;
869 	    }
870 	  if (temp_node->check != node_check_tick)
871 	    {
872 	      temp_node->check = node_check_tick;
873 	      temp_node->conflict_size = 0;
874 	    }
875 	  size = (ira_reg_class_max_nregs
876 		  [ALLOCNO_CLASS (conflict_a)][ALLOCNO_MODE (conflict_a)]);
877 	  if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
878 	    /* We will deal with the subwords individually.  */
879 	    size = 1;
880 	  temp_node->conflict_size += size;
881 	}
882     }
883   for (i = 0; i < data->hard_regs_subnodes_num; i++)
884     {
885       allocno_hard_regs_node_t temp_node;
886 
887       temp_node = allocno_hard_regs_nodes[i + node_preorder_num];
888       ira_assert (temp_node->preorder_num == i + node_preorder_num);
889       subnodes[i].left_conflict_size = (temp_node->check != node_check_tick
890 					? 0 : temp_node->conflict_size);
891       if (hard_reg_set_subset_p (temp_node->hard_regs->set,
892 				 profitable_hard_regs))
893 	subnodes[i].max_node_impact = temp_node->hard_regs_num;
894       else
895 	{
896 	  HARD_REG_SET temp_set;
897 	  int j, n, hard_regno;
898 	  enum reg_class aclass;
899 
900 	  COPY_HARD_REG_SET (temp_set, temp_node->hard_regs->set);
901 	  AND_HARD_REG_SET (temp_set, profitable_hard_regs);
902 	  aclass = ALLOCNO_CLASS (a);
903 	  for (n = 0, j = ira_class_hard_regs_num[aclass] - 1; j >= 0; j--)
904 	    {
905 	      hard_regno = ira_class_hard_regs[aclass][j];
906 	      if (TEST_HARD_REG_BIT (temp_set, hard_regno))
907 		n++;
908 	    }
909 	  subnodes[i].max_node_impact = n;
910 	}
911       subnodes[i].left_conflict_subnodes_size = 0;
912     }
913   start = node_preorder_num * allocno_hard_regs_nodes_num;
914   for (i = data->hard_regs_subnodes_num - 1; i > 0; i--)
915     {
916       int size, parent_i;
917       allocno_hard_regs_node_t parent;
918 
919       size = (subnodes[i].left_conflict_subnodes_size
920 	      + MIN (subnodes[i].max_node_impact
921 		     - subnodes[i].left_conflict_subnodes_size,
922 		     subnodes[i].left_conflict_size));
923       parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
924       gcc_checking_assert(parent);
925       parent_i
926 	= allocno_hard_regs_subnode_index[start + parent->preorder_num];
927       gcc_checking_assert(parent_i >= 0);
928       subnodes[parent_i].left_conflict_subnodes_size += size;
929     }
930   left_conflict_subnodes_size = subnodes[0].left_conflict_subnodes_size;
931   conflict_size
932     = (left_conflict_subnodes_size
933        + MIN (subnodes[0].max_node_impact - left_conflict_subnodes_size,
934 	      subnodes[0].left_conflict_size));
935   conflict_size += ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
936   data->colorable_p = conflict_size <= data->available_regs_num;
937   return data->colorable_p;
938 }
939 
940 /* Update left conflict sizes of hard registers subnodes of allocno A
941    after removing allocno REMOVED_A with SIZE from the conflict graph.
942    Return TRUE if A is trivially colorable.  */
943 static bool
update_left_conflict_sizes_p(ira_allocno_t a,ira_allocno_t removed_a,int size)944 update_left_conflict_sizes_p (ira_allocno_t a,
945 			      ira_allocno_t removed_a, int size)
946 {
947   int i, conflict_size, before_conflict_size, diff, start;
948   int node_preorder_num, parent_i;
949   allocno_hard_regs_node_t node, removed_node, parent;
950   allocno_hard_regs_subnode_t subnodes;
951   allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
952 
953   ira_assert (! data->colorable_p);
954   node = data->hard_regs_node;
955   node_preorder_num = node->preorder_num;
956   removed_node = ALLOCNO_COLOR_DATA (removed_a)->hard_regs_node;
957   ira_assert (hard_reg_set_subset_p (removed_node->hard_regs->set,
958 			       node->hard_regs->set)
959 	      || hard_reg_set_subset_p (node->hard_regs->set,
960 					removed_node->hard_regs->set));
961   start = node_preorder_num * allocno_hard_regs_nodes_num;
962   i = allocno_hard_regs_subnode_index[start + removed_node->preorder_num];
963   if (i < 0)
964     i = 0;
965   subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
966   before_conflict_size
967     = (subnodes[i].left_conflict_subnodes_size
968        + MIN (subnodes[i].max_node_impact
969 	      - subnodes[i].left_conflict_subnodes_size,
970 	      subnodes[i].left_conflict_size));
971   subnodes[i].left_conflict_size -= size;
972   for (;;)
973     {
974       conflict_size
975 	= (subnodes[i].left_conflict_subnodes_size
976 	   + MIN (subnodes[i].max_node_impact
977 		  - subnodes[i].left_conflict_subnodes_size,
978 		  subnodes[i].left_conflict_size));
979       if ((diff = before_conflict_size - conflict_size) == 0)
980 	break;
981       ira_assert (conflict_size < before_conflict_size);
982       parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
983       if (parent == NULL)
984 	break;
985       parent_i
986 	= allocno_hard_regs_subnode_index[start + parent->preorder_num];
987       if (parent_i < 0)
988 	break;
989       i = parent_i;
990       before_conflict_size
991 	= (subnodes[i].left_conflict_subnodes_size
992 	   + MIN (subnodes[i].max_node_impact
993 		  - subnodes[i].left_conflict_subnodes_size,
994 		  subnodes[i].left_conflict_size));
995       subnodes[i].left_conflict_subnodes_size -= diff;
996     }
997   if (i != 0
998       || (conflict_size
999 	  + ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
1000 	  > data->available_regs_num))
1001     return false;
1002   data->colorable_p = true;
1003   return true;
1004 }
1005 
1006 /* Return true if allocno A has empty profitable hard regs.  */
1007 static bool
empty_profitable_hard_regs(ira_allocno_t a)1008 empty_profitable_hard_regs (ira_allocno_t a)
1009 {
1010   allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
1011 
1012   return hard_reg_set_empty_p (data->profitable_hard_regs);
1013 }
1014 
1015 /* Set up profitable hard registers for each allocno being
1016    colored.  */
1017 static void
setup_profitable_hard_regs(void)1018 setup_profitable_hard_regs (void)
1019 {
1020   unsigned int i;
1021   int j, k, nobj, hard_regno, nregs, class_size;
1022   ira_allocno_t a;
1023   bitmap_iterator bi;
1024   enum reg_class aclass;
1025   machine_mode mode;
1026   allocno_color_data_t data;
1027 
1028   /* Initial set up from allocno classes and explicitly conflicting
1029      hard regs.  */
1030   EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1031     {
1032       a = ira_allocnos[i];
1033       if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS)
1034 	continue;
1035       data = ALLOCNO_COLOR_DATA (a);
1036       if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL
1037 	  && ALLOCNO_CLASS_COST (a) > ALLOCNO_MEMORY_COST (a)
1038 	  /* Do not empty profitable regs for static chain pointer
1039 	     pseudo when non-local goto is used.  */
1040 	  && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1041 	CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1042       else
1043 	{
1044 	  mode = ALLOCNO_MODE (a);
1045 	  COPY_HARD_REG_SET (data->profitable_hard_regs,
1046 			     ira_useful_class_mode_regs[aclass][mode]);
1047 	  nobj = ALLOCNO_NUM_OBJECTS (a);
1048 	  for (k = 0; k < nobj; k++)
1049 	    {
1050 	      ira_object_t obj = ALLOCNO_OBJECT (a, k);
1051 
1052 	      AND_COMPL_HARD_REG_SET (data->profitable_hard_regs,
1053 				      OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1054 	    }
1055 	}
1056     }
1057   /* Exclude hard regs already assigned for conflicting objects.  */
1058   EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, i, bi)
1059     {
1060       a = ira_allocnos[i];
1061       if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1062 	  || ! ALLOCNO_ASSIGNED_P (a)
1063 	  || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
1064 	continue;
1065       mode = ALLOCNO_MODE (a);
1066       nregs = hard_regno_nregs (hard_regno, mode);
1067       nobj = ALLOCNO_NUM_OBJECTS (a);
1068       for (k = 0; k < nobj; k++)
1069 	{
1070 	  ira_object_t obj = ALLOCNO_OBJECT (a, k);
1071 	  ira_object_t conflict_obj;
1072 	  ira_object_conflict_iterator oci;
1073 
1074 	  FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1075 	    {
1076 	      ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1077 
1078 	      /* We can process the conflict allocno repeatedly with
1079 		 the same result.  */
1080 	      if (nregs == nobj && nregs > 1)
1081 		{
1082 		  int num = OBJECT_SUBWORD (conflict_obj);
1083 
1084 		  if (REG_WORDS_BIG_ENDIAN)
1085 		    CLEAR_HARD_REG_BIT
1086 		      (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1087 		       hard_regno + nobj - num - 1);
1088 		  else
1089 		    CLEAR_HARD_REG_BIT
1090 		      (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1091 		       hard_regno + num);
1092 		}
1093 	      else
1094 		AND_COMPL_HARD_REG_SET
1095 		  (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1096 		   ira_reg_mode_hard_regset[hard_regno][mode]);
1097 	    }
1098 	}
1099     }
1100   /* Exclude too costly hard regs.  */
1101   EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1102     {
1103       int min_cost = INT_MAX;
1104       int *costs;
1105 
1106       a = ira_allocnos[i];
1107       if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1108 	  || empty_profitable_hard_regs (a))
1109 	continue;
1110       data = ALLOCNO_COLOR_DATA (a);
1111       mode = ALLOCNO_MODE (a);
1112       if ((costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a)) != NULL
1113 	  || (costs = ALLOCNO_HARD_REG_COSTS (a)) != NULL)
1114 	{
1115 	  class_size = ira_class_hard_regs_num[aclass];
1116 	  for (j = 0; j < class_size; j++)
1117 	    {
1118 	      hard_regno = ira_class_hard_regs[aclass][j];
1119 	      if (! TEST_HARD_REG_BIT (data->profitable_hard_regs,
1120 				       hard_regno))
1121 		continue;
1122 	      if (ALLOCNO_UPDATED_MEMORY_COST (a) < costs[j]
1123 		  /* Do not remove HARD_REGNO for static chain pointer
1124 		     pseudo when non-local goto is used.  */
1125 		  && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1126 		CLEAR_HARD_REG_BIT (data->profitable_hard_regs,
1127 				    hard_regno);
1128 	      else if (min_cost > costs[j])
1129 		min_cost = costs[j];
1130 	    }
1131 	}
1132       else if (ALLOCNO_UPDATED_MEMORY_COST (a)
1133 	       < ALLOCNO_UPDATED_CLASS_COST (a)
1134 	       /* Do not empty profitable regs for static chain
1135 		  pointer pseudo when non-local goto is used.  */
1136 	       && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1137 	CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1138       if (ALLOCNO_UPDATED_CLASS_COST (a) > min_cost)
1139 	ALLOCNO_UPDATED_CLASS_COST (a) = min_cost;
1140     }
1141 }
1142 
1143 
1144 
1145 /* This page contains functions used to choose hard registers for
1146    allocnos.  */
1147 
1148 /* Pool for update cost records.  */
1149 static object_allocator<update_cost_record> update_cost_record_pool
1150   ("update cost records");
1151 
1152 /* Return new update cost record with given params.  */
1153 static struct update_cost_record *
get_update_cost_record(int hard_regno,int divisor,struct update_cost_record * next)1154 get_update_cost_record (int hard_regno, int divisor,
1155 			struct update_cost_record *next)
1156 {
1157   struct update_cost_record *record;
1158 
1159   record = update_cost_record_pool.allocate ();
1160   record->hard_regno = hard_regno;
1161   record->divisor = divisor;
1162   record->next = next;
1163   return record;
1164 }
1165 
1166 /* Free memory for all records in LIST.  */
1167 static void
free_update_cost_record_list(struct update_cost_record * list)1168 free_update_cost_record_list (struct update_cost_record *list)
1169 {
1170   struct update_cost_record *next;
1171 
1172   while (list != NULL)
1173     {
1174       next = list->next;
1175       update_cost_record_pool.remove (list);
1176       list = next;
1177     }
1178 }
1179 
1180 /* Free memory allocated for all update cost records.  */
1181 static void
finish_update_cost_records(void)1182 finish_update_cost_records (void)
1183 {
1184   update_cost_record_pool.release ();
1185 }
1186 
1187 /* Array whose element value is TRUE if the corresponding hard
1188    register was already allocated for an allocno.  */
1189 static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
1190 
1191 /* Describes one element in a queue of allocnos whose costs need to be
1192    updated.  Each allocno in the queue is known to have an allocno
1193    class.  */
1194 struct update_cost_queue_elem
1195 {
1196   /* This element is in the queue iff CHECK == update_cost_check.  */
1197   int check;
1198 
1199   /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
1200      connecting this allocno to the one being allocated.  */
1201   int divisor;
1202 
1203   /* Allocno from which we are chaining costs of connected allocnos.
1204      It is used not go back in graph of allocnos connected by
1205      copies.  */
1206   ira_allocno_t from;
1207 
1208   /* The next allocno in the queue, or null if this is the last element.  */
1209   ira_allocno_t next;
1210 };
1211 
1212 /* The first element in a queue of allocnos whose copy costs need to be
1213    updated.  Null if the queue is empty.  */
1214 static ira_allocno_t update_cost_queue;
1215 
1216 /* The last element in the queue described by update_cost_queue.
1217    Not valid if update_cost_queue is null.  */
1218 static struct update_cost_queue_elem *update_cost_queue_tail;
1219 
1220 /* A pool of elements in the queue described by update_cost_queue.
1221    Elements are indexed by ALLOCNO_NUM.  */
1222 static struct update_cost_queue_elem *update_cost_queue_elems;
1223 
1224 /* The current value of update_costs_from_copies call count.  */
1225 static int update_cost_check;
1226 
1227 /* Allocate and initialize data necessary for function
1228    update_costs_from_copies.  */
1229 static void
initiate_cost_update(void)1230 initiate_cost_update (void)
1231 {
1232   size_t size;
1233 
1234   size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
1235   update_cost_queue_elems
1236     = (struct update_cost_queue_elem *) ira_allocate (size);
1237   memset (update_cost_queue_elems, 0, size);
1238   update_cost_check = 0;
1239 }
1240 
1241 /* Deallocate data used by function update_costs_from_copies.  */
1242 static void
finish_cost_update(void)1243 finish_cost_update (void)
1244 {
1245   ira_free (update_cost_queue_elems);
1246   finish_update_cost_records ();
1247 }
1248 
1249 /* When we traverse allocnos to update hard register costs, the cost
1250    divisor will be multiplied by the following macro value for each
1251    hop from given allocno to directly connected allocnos.  */
1252 #define COST_HOP_DIVISOR 4
1253 
1254 /* Start a new cost-updating pass.  */
1255 static void
start_update_cost(void)1256 start_update_cost (void)
1257 {
1258   update_cost_check++;
1259   update_cost_queue = NULL;
1260 }
1261 
1262 /* Add (ALLOCNO, FROM, DIVISOR) to the end of update_cost_queue, unless
1263    ALLOCNO is already in the queue, or has NO_REGS class.  */
1264 static inline void
queue_update_cost(ira_allocno_t allocno,ira_allocno_t from,int divisor)1265 queue_update_cost (ira_allocno_t allocno, ira_allocno_t from, int divisor)
1266 {
1267   struct update_cost_queue_elem *elem;
1268 
1269   elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
1270   if (elem->check != update_cost_check
1271       && ALLOCNO_CLASS (allocno) != NO_REGS)
1272     {
1273       elem->check = update_cost_check;
1274       elem->from = from;
1275       elem->divisor = divisor;
1276       elem->next = NULL;
1277       if (update_cost_queue == NULL)
1278 	update_cost_queue = allocno;
1279       else
1280 	update_cost_queue_tail->next = allocno;
1281       update_cost_queue_tail = elem;
1282     }
1283 }
1284 
1285 /* Try to remove the first element from update_cost_queue.  Return
1286    false if the queue was empty, otherwise make (*ALLOCNO, *FROM,
1287    *DIVISOR) describe the removed element.  */
1288 static inline bool
get_next_update_cost(ira_allocno_t * allocno,ira_allocno_t * from,int * divisor)1289 get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *from, int *divisor)
1290 {
1291   struct update_cost_queue_elem *elem;
1292 
1293   if (update_cost_queue == NULL)
1294     return false;
1295 
1296   *allocno = update_cost_queue;
1297   elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
1298   *from = elem->from;
1299   *divisor = elem->divisor;
1300   update_cost_queue = elem->next;
1301   return true;
1302 }
1303 
1304 /* Increase costs of HARD_REGNO by UPDATE_COST and conflict cost by
1305    UPDATE_CONFLICT_COST for ALLOCNO.  Return true if we really
1306    modified the cost.  */
1307 static bool
update_allocno_cost(ira_allocno_t allocno,int hard_regno,int update_cost,int update_conflict_cost)1308 update_allocno_cost (ira_allocno_t allocno, int hard_regno,
1309 		     int update_cost, int update_conflict_cost)
1310 {
1311   int i;
1312   enum reg_class aclass = ALLOCNO_CLASS (allocno);
1313 
1314   i = ira_class_hard_reg_index[aclass][hard_regno];
1315   if (i < 0)
1316     return false;
1317   ira_allocate_and_set_or_copy_costs
1318     (&ALLOCNO_UPDATED_HARD_REG_COSTS (allocno), aclass,
1319      ALLOCNO_UPDATED_CLASS_COST (allocno),
1320      ALLOCNO_HARD_REG_COSTS (allocno));
1321   ira_allocate_and_set_or_copy_costs
1322     (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno),
1323      aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno));
1324   ALLOCNO_UPDATED_HARD_REG_COSTS (allocno)[i] += update_cost;
1325   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno)[i] += update_conflict_cost;
1326   return true;
1327 }
1328 
1329 /* Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected
1330    by copies to ALLOCNO to increase chances to remove some copies as
1331    the result of subsequent assignment.  Record cost updates if
1332    RECORD_P is true.  */
1333 static void
update_costs_from_allocno(ira_allocno_t allocno,int hard_regno,int divisor,bool decr_p,bool record_p)1334 update_costs_from_allocno (ira_allocno_t allocno, int hard_regno,
1335 			   int divisor, bool decr_p, bool record_p)
1336 {
1337   int cost, update_cost, update_conflict_cost;
1338   machine_mode mode;
1339   enum reg_class rclass, aclass;
1340   ira_allocno_t another_allocno, from = NULL;
1341   ira_copy_t cp, next_cp;
1342 
1343   rclass = REGNO_REG_CLASS (hard_regno);
1344   do
1345     {
1346       mode = ALLOCNO_MODE (allocno);
1347       ira_init_register_move_cost_if_necessary (mode);
1348       for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1349 	{
1350 	  if (cp->first == allocno)
1351 	    {
1352 	      next_cp = cp->next_first_allocno_copy;
1353 	      another_allocno = cp->second;
1354 	    }
1355 	  else if (cp->second == allocno)
1356 	    {
1357 	      next_cp = cp->next_second_allocno_copy;
1358 	      another_allocno = cp->first;
1359 	    }
1360 	  else
1361 	    gcc_unreachable ();
1362 
1363 	  if (another_allocno == from)
1364 	    continue;
1365 
1366 	  aclass = ALLOCNO_CLASS (another_allocno);
1367 	  if (! TEST_HARD_REG_BIT (reg_class_contents[aclass],
1368 				   hard_regno)
1369 	      || ALLOCNO_ASSIGNED_P (another_allocno))
1370 	    continue;
1371 
1372 	  /* If we have different modes use the smallest one.  It is
1373 	     a sub-register move.  It is hard to predict what LRA
1374 	     will reload (the pseudo or its sub-register) but LRA
1375 	     will try to minimize the data movement.  Also for some
1376 	     register classes bigger modes might be invalid,
1377 	     e.g. DImode for AREG on x86.  For such cases the
1378 	     register move cost will be maximal.  */
1379 	  mode = narrower_subreg_mode (mode, ALLOCNO_MODE (cp->second));
1380 
1381 	  cost = (cp->second == allocno
1382 		  ? ira_register_move_cost[mode][rclass][aclass]
1383 		  : ira_register_move_cost[mode][aclass][rclass]);
1384 	  if (decr_p)
1385 	    cost = -cost;
1386 
1387 	  update_conflict_cost = update_cost = cp->freq * cost / divisor;
1388 
1389 	  if (ALLOCNO_COLOR_DATA (another_allocno) != NULL
1390 	      && (ALLOCNO_COLOR_DATA (allocno)->first_thread_allocno
1391 		  != ALLOCNO_COLOR_DATA (another_allocno)->first_thread_allocno))
1392 	    /* Decrease conflict cost of ANOTHER_ALLOCNO if it is not
1393 	       in the same allocation thread.  */
1394 	    update_conflict_cost /= COST_HOP_DIVISOR;
1395 
1396 	  if (update_cost == 0)
1397 	    continue;
1398 
1399 	  if (! update_allocno_cost (another_allocno, hard_regno,
1400 				     update_cost, update_conflict_cost))
1401 	    continue;
1402 	  queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR);
1403 	  if (record_p && ALLOCNO_COLOR_DATA (another_allocno) != NULL)
1404 	    ALLOCNO_COLOR_DATA (another_allocno)->update_cost_records
1405 	      = get_update_cost_record (hard_regno, divisor,
1406 					ALLOCNO_COLOR_DATA (another_allocno)
1407 					->update_cost_records);
1408 	}
1409     }
1410   while (get_next_update_cost (&allocno, &from, &divisor));
1411 }
1412 
1413 /* Decrease preferred ALLOCNO hard register costs and costs of
1414    allocnos connected to ALLOCNO through copy.  */
1415 static void
update_costs_from_prefs(ira_allocno_t allocno)1416 update_costs_from_prefs (ira_allocno_t allocno)
1417 {
1418   ira_pref_t pref;
1419 
1420   start_update_cost ();
1421   for (pref = ALLOCNO_PREFS (allocno); pref != NULL; pref = pref->next_pref)
1422     update_costs_from_allocno (allocno, pref->hard_regno,
1423 			       COST_HOP_DIVISOR, true, true);
1424 }
1425 
1426 /* Update (decrease if DECR_P) the cost of allocnos connected to
1427    ALLOCNO through copies to increase chances to remove some copies as
1428    the result of subsequent assignment.  ALLOCNO was just assigned to
1429    a hard register.  Record cost updates if RECORD_P is true.  */
1430 static void
update_costs_from_copies(ira_allocno_t allocno,bool decr_p,bool record_p)1431 update_costs_from_copies (ira_allocno_t allocno, bool decr_p, bool record_p)
1432 {
1433   int hard_regno;
1434 
1435   hard_regno = ALLOCNO_HARD_REGNO (allocno);
1436   ira_assert (hard_regno >= 0 && ALLOCNO_CLASS (allocno) != NO_REGS);
1437   start_update_cost ();
1438   update_costs_from_allocno (allocno, hard_regno, 1, decr_p, record_p);
1439 }
1440 
1441 /* Update conflict_allocno_hard_prefs of allocnos conflicting with
1442    ALLOCNO.  */
1443 static void
update_conflict_allocno_hard_prefs(ira_allocno_t allocno)1444 update_conflict_allocno_hard_prefs (ira_allocno_t allocno)
1445 {
1446   int l, nr = ALLOCNO_NUM_OBJECTS (allocno);
1447 
1448   for (l = 0; l < nr; l++)
1449     {
1450       ira_object_t conflict_obj, obj = ALLOCNO_OBJECT (allocno, l);
1451       ira_object_conflict_iterator oci;
1452 
1453       FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1454 	{
1455 	  ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1456 	  allocno_color_data_t conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
1457 	  ira_pref_t pref;
1458 
1459 	  if (!(hard_reg_set_intersect_p
1460 		(ALLOCNO_COLOR_DATA (allocno)->profitable_hard_regs,
1461 		 conflict_data->profitable_hard_regs)))
1462 	    continue;
1463 	  for (pref = ALLOCNO_PREFS (allocno);
1464 	       pref != NULL;
1465 	       pref = pref->next_pref)
1466 	    conflict_data->conflict_allocno_hard_prefs += pref->freq;
1467 	}
1468     }
1469 }
1470 
1471 /* Restore costs of allocnos connected to ALLOCNO by copies as it was
1472    before updating costs of these allocnos from given allocno.  This
1473    is a wise thing to do as if given allocno did not get an expected
1474    hard reg, using smaller cost of the hard reg for allocnos connected
1475    by copies to given allocno becomes actually misleading.  Free all
1476    update cost records for ALLOCNO as we don't need them anymore.  */
1477 static void
restore_costs_from_copies(ira_allocno_t allocno)1478 restore_costs_from_copies (ira_allocno_t allocno)
1479 {
1480   struct update_cost_record *records, *curr;
1481 
1482   if (ALLOCNO_COLOR_DATA (allocno) == NULL)
1483     return;
1484   records = ALLOCNO_COLOR_DATA (allocno)->update_cost_records;
1485   start_update_cost ();
1486   for (curr = records; curr != NULL; curr = curr->next)
1487     update_costs_from_allocno (allocno, curr->hard_regno,
1488 			       curr->divisor, true, false);
1489   free_update_cost_record_list (records);
1490   ALLOCNO_COLOR_DATA (allocno)->update_cost_records = NULL;
1491 }
1492 
1493 /* This function updates COSTS (decrease if DECR_P) for hard_registers
1494    of ACLASS by conflict costs of the unassigned allocnos
1495    connected by copies with allocnos in update_cost_queue.  This
1496    update increases chances to remove some copies.  */
1497 static void
update_conflict_hard_regno_costs(int * costs,enum reg_class aclass,bool decr_p)1498 update_conflict_hard_regno_costs (int *costs, enum reg_class aclass,
1499 				  bool decr_p)
1500 {
1501   int i, cost, class_size, freq, mult, div, divisor;
1502   int index, hard_regno;
1503   int *conflict_costs;
1504   bool cont_p;
1505   enum reg_class another_aclass;
1506   ira_allocno_t allocno, another_allocno, from;
1507   ira_copy_t cp, next_cp;
1508 
1509   while (get_next_update_cost (&allocno, &from, &divisor))
1510     for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1511       {
1512 	if (cp->first == allocno)
1513 	  {
1514 	    next_cp = cp->next_first_allocno_copy;
1515 	    another_allocno = cp->second;
1516 	  }
1517 	else if (cp->second == allocno)
1518 	  {
1519 	    next_cp = cp->next_second_allocno_copy;
1520 	    another_allocno = cp->first;
1521 	  }
1522 	else
1523 	  gcc_unreachable ();
1524 
1525 	if (another_allocno == from)
1526 	  continue;
1527 
1528  	another_aclass = ALLOCNO_CLASS (another_allocno);
1529  	if (! ira_reg_classes_intersect_p[aclass][another_aclass]
1530 	    || ALLOCNO_ASSIGNED_P (another_allocno)
1531 	    || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p)
1532 	  continue;
1533 	class_size = ira_class_hard_regs_num[another_aclass];
1534 	ira_allocate_and_copy_costs
1535 	  (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
1536 	   another_aclass, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
1537 	conflict_costs
1538 	  = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
1539 	if (conflict_costs == NULL)
1540 	  cont_p = true;
1541 	else
1542 	  {
1543 	    mult = cp->freq;
1544 	    freq = ALLOCNO_FREQ (another_allocno);
1545 	    if (freq == 0)
1546 	      freq = 1;
1547 	    div = freq * divisor;
1548 	    cont_p = false;
1549 	    for (i = class_size - 1; i >= 0; i--)
1550 	      {
1551 		hard_regno = ira_class_hard_regs[another_aclass][i];
1552 		ira_assert (hard_regno >= 0);
1553 		index = ira_class_hard_reg_index[aclass][hard_regno];
1554 		if (index < 0)
1555 		  continue;
1556 		cost = (int) (((int64_t) conflict_costs [i] * mult) / div);
1557 		if (cost == 0)
1558 		  continue;
1559 		cont_p = true;
1560 		if (decr_p)
1561 		  cost = -cost;
1562 		costs[index] += cost;
1563 	      }
1564 	  }
1565 	/* Probably 5 hops will be enough.  */
1566 	if (cont_p
1567 	    && divisor <= (COST_HOP_DIVISOR
1568 			   * COST_HOP_DIVISOR
1569 			   * COST_HOP_DIVISOR
1570 			   * COST_HOP_DIVISOR))
1571 	  queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR);
1572       }
1573 }
1574 
1575 /* Set up conflicting (through CONFLICT_REGS) for each object of
1576    allocno A and the start allocno profitable regs (through
1577    START_PROFITABLE_REGS).  Remember that the start profitable regs
1578    exclude hard regs which can not hold value of mode of allocno A.
1579    This covers mostly cases when multi-register value should be
1580    aligned.  */
1581 static inline void
get_conflict_and_start_profitable_regs(ira_allocno_t a,bool retry_p,HARD_REG_SET * conflict_regs,HARD_REG_SET * start_profitable_regs)1582 get_conflict_and_start_profitable_regs (ira_allocno_t a, bool retry_p,
1583 					HARD_REG_SET *conflict_regs,
1584 					HARD_REG_SET *start_profitable_regs)
1585 {
1586   int i, nwords;
1587   ira_object_t obj;
1588 
1589   nwords = ALLOCNO_NUM_OBJECTS (a);
1590   for (i = 0; i < nwords; i++)
1591     {
1592       obj = ALLOCNO_OBJECT (a, i);
1593       COPY_HARD_REG_SET (conflict_regs[i],
1594 			 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1595     }
1596   if (retry_p)
1597     {
1598       COPY_HARD_REG_SET (*start_profitable_regs,
1599 			 reg_class_contents[ALLOCNO_CLASS (a)]);
1600       AND_COMPL_HARD_REG_SET (*start_profitable_regs,
1601 			      ira_prohibited_class_mode_regs
1602 			      [ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
1603     }
1604   else
1605     COPY_HARD_REG_SET (*start_profitable_regs,
1606 		       ALLOCNO_COLOR_DATA (a)->profitable_hard_regs);
1607 }
1608 
1609 /* Return true if HARD_REGNO is ok for assigning to allocno A with
1610    PROFITABLE_REGS and whose objects have CONFLICT_REGS.  */
1611 static inline bool
check_hard_reg_p(ira_allocno_t a,int hard_regno,HARD_REG_SET * conflict_regs,HARD_REG_SET profitable_regs)1612 check_hard_reg_p (ira_allocno_t a, int hard_regno,
1613 		  HARD_REG_SET *conflict_regs, HARD_REG_SET profitable_regs)
1614 {
1615   int j, nwords, nregs;
1616   enum reg_class aclass;
1617   machine_mode mode;
1618 
1619   aclass = ALLOCNO_CLASS (a);
1620   mode = ALLOCNO_MODE (a);
1621   if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[aclass][mode],
1622 			 hard_regno))
1623     return false;
1624   /* Checking only profitable hard regs.  */
1625   if (! TEST_HARD_REG_BIT (profitable_regs, hard_regno))
1626     return false;
1627   nregs = hard_regno_nregs (hard_regno, mode);
1628   nwords = ALLOCNO_NUM_OBJECTS (a);
1629   for (j = 0; j < nregs; j++)
1630     {
1631       int k;
1632       int set_to_test_start = 0, set_to_test_end = nwords;
1633 
1634       if (nregs == nwords)
1635 	{
1636 	  if (REG_WORDS_BIG_ENDIAN)
1637 	    set_to_test_start = nwords - j - 1;
1638 	  else
1639 	    set_to_test_start = j;
1640 	  set_to_test_end = set_to_test_start + 1;
1641 	}
1642       for (k = set_to_test_start; k < set_to_test_end; k++)
1643 	if (TEST_HARD_REG_BIT (conflict_regs[k], hard_regno + j))
1644 	  break;
1645       if (k != set_to_test_end)
1646 	break;
1647     }
1648   return j == nregs;
1649 }
1650 
1651 /* Return number of registers needed to be saved and restored at
1652    function prologue/epilogue if we allocate HARD_REGNO to hold value
1653    of MODE.  */
1654 static int
calculate_saved_nregs(int hard_regno,machine_mode mode)1655 calculate_saved_nregs (int hard_regno, machine_mode mode)
1656 {
1657   int i;
1658   int nregs = 0;
1659 
1660   ira_assert (hard_regno >= 0);
1661   for (i = hard_regno_nregs (hard_regno, mode) - 1; i >= 0; i--)
1662     if (!allocated_hardreg_p[hard_regno + i]
1663 	&& !TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + i)
1664 	&& !LOCAL_REGNO (hard_regno + i))
1665       nregs++;
1666   return nregs;
1667 }
1668 
1669 /* Choose a hard register for allocno A.  If RETRY_P is TRUE, it means
1670    that the function called from function
1671    `ira_reassign_conflict_allocnos' and `allocno_reload_assign'.  In
1672    this case some allocno data are not defined or updated and we
1673    should not touch these data.  The function returns true if we
1674    managed to assign a hard register to the allocno.
1675 
1676    To assign a hard register, first of all we calculate all conflict
1677    hard registers which can come from conflicting allocnos with
1678    already assigned hard registers.  After that we find first free
1679    hard register with the minimal cost.  During hard register cost
1680    calculation we take conflict hard register costs into account to
1681    give a chance for conflicting allocnos to get a better hard
1682    register in the future.
1683 
1684    If the best hard register cost is bigger than cost of memory usage
1685    for the allocno, we don't assign a hard register to given allocno
1686    at all.
1687 
1688    If we assign a hard register to the allocno, we update costs of the
1689    hard register for allocnos connected by copies to improve a chance
1690    to coalesce insns represented by the copies when we assign hard
1691    registers to the allocnos connected by the copies.  */
1692 static bool
assign_hard_reg(ira_allocno_t a,bool retry_p)1693 assign_hard_reg (ira_allocno_t a, bool retry_p)
1694 {
1695   HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
1696   int i, j, hard_regno, best_hard_regno, class_size;
1697   int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords, word;
1698   int *a_costs;
1699   enum reg_class aclass;
1700   machine_mode mode;
1701   static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
1702   int saved_nregs;
1703   enum reg_class rclass;
1704   int add_cost;
1705 #ifdef STACK_REGS
1706   bool no_stack_reg_p;
1707 #endif
1708 
1709   ira_assert (! ALLOCNO_ASSIGNED_P (a));
1710   get_conflict_and_start_profitable_regs (a, retry_p,
1711 					  conflicting_regs,
1712 					  &profitable_hard_regs);
1713   aclass = ALLOCNO_CLASS (a);
1714   class_size = ira_class_hard_regs_num[aclass];
1715   best_hard_regno = -1;
1716   memset (full_costs, 0, sizeof (int) * class_size);
1717   mem_cost = 0;
1718   memset (costs, 0, sizeof (int) * class_size);
1719   memset (full_costs, 0, sizeof (int) * class_size);
1720 #ifdef STACK_REGS
1721   no_stack_reg_p = false;
1722 #endif
1723   if (! retry_p)
1724     start_update_cost ();
1725   mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
1726 
1727   ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
1728 			       aclass, ALLOCNO_HARD_REG_COSTS (a));
1729   a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
1730 #ifdef STACK_REGS
1731   no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
1732 #endif
1733   cost = ALLOCNO_UPDATED_CLASS_COST (a);
1734   for (i = 0; i < class_size; i++)
1735     if (a_costs != NULL)
1736       {
1737 	costs[i] += a_costs[i];
1738 	full_costs[i] += a_costs[i];
1739       }
1740     else
1741       {
1742 	costs[i] += cost;
1743 	full_costs[i] += cost;
1744       }
1745   nwords = ALLOCNO_NUM_OBJECTS (a);
1746   curr_allocno_process++;
1747   for (word = 0; word < nwords; word++)
1748     {
1749       ira_object_t conflict_obj;
1750       ira_object_t obj = ALLOCNO_OBJECT (a, word);
1751       ira_object_conflict_iterator oci;
1752 
1753       /* Take preferences of conflicting allocnos into account.  */
1754       FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1755         {
1756 	  ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1757 	  enum reg_class conflict_aclass;
1758 	  allocno_color_data_t data = ALLOCNO_COLOR_DATA (conflict_a);
1759 
1760 	  /* Reload can give another class so we need to check all
1761 	     allocnos.  */
1762 	  if (!retry_p
1763 	      && ((!ALLOCNO_ASSIGNED_P (conflict_a)
1764 		   || ALLOCNO_HARD_REGNO (conflict_a) < 0)
1765 		  && !(hard_reg_set_intersect_p
1766 		       (profitable_hard_regs,
1767 			ALLOCNO_COLOR_DATA
1768 			(conflict_a)->profitable_hard_regs))))
1769 	    {
1770 	      /* All conflict allocnos are in consideration bitmap
1771 		 when retry_p is false.  It might change in future and
1772 		 if it happens the assert will be broken.  It means
1773 		 the code should be modified for the new
1774 		 assumptions.  */
1775 	      ira_assert (bitmap_bit_p (consideration_allocno_bitmap,
1776 					ALLOCNO_NUM (conflict_a)));
1777 	      continue;
1778 	    }
1779 	  conflict_aclass = ALLOCNO_CLASS (conflict_a);
1780 	  ira_assert (ira_reg_classes_intersect_p
1781 		      [aclass][conflict_aclass]);
1782 	  if (ALLOCNO_ASSIGNED_P (conflict_a))
1783 	    {
1784 	      hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
1785 	      if (hard_regno >= 0
1786 		  && (ira_hard_reg_set_intersection_p
1787 		      (hard_regno, ALLOCNO_MODE (conflict_a),
1788 		       reg_class_contents[aclass])))
1789 		{
1790 		  int n_objects = ALLOCNO_NUM_OBJECTS (conflict_a);
1791 		  int conflict_nregs;
1792 
1793 		  mode = ALLOCNO_MODE (conflict_a);
1794 		  conflict_nregs = hard_regno_nregs (hard_regno, mode);
1795 		  if (conflict_nregs == n_objects && conflict_nregs > 1)
1796 		    {
1797 		      int num = OBJECT_SUBWORD (conflict_obj);
1798 
1799 		      if (REG_WORDS_BIG_ENDIAN)
1800 			SET_HARD_REG_BIT (conflicting_regs[word],
1801 					  hard_regno + n_objects - num - 1);
1802 		      else
1803 			SET_HARD_REG_BIT (conflicting_regs[word],
1804 					  hard_regno + num);
1805 		    }
1806 		  else
1807 		    IOR_HARD_REG_SET
1808 		      (conflicting_regs[word],
1809 		       ira_reg_mode_hard_regset[hard_regno][mode]);
1810 		  if (hard_reg_set_subset_p (profitable_hard_regs,
1811 					     conflicting_regs[word]))
1812 		    goto fail;
1813 		}
1814 	    }
1815 	  else if (! retry_p
1816 		   && ! ALLOCNO_COLOR_DATA (conflict_a)->may_be_spilled_p
1817 		   /* Don't process the conflict allocno twice.  */
1818 		   && (ALLOCNO_COLOR_DATA (conflict_a)->last_process
1819 		       != curr_allocno_process))
1820 	    {
1821 	      int k, *conflict_costs;
1822 
1823 	      ALLOCNO_COLOR_DATA (conflict_a)->last_process
1824 		= curr_allocno_process;
1825 	      ira_allocate_and_copy_costs
1826 		(&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a),
1827 		 conflict_aclass,
1828 		 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a));
1829 	      conflict_costs
1830 		= ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a);
1831 	      if (conflict_costs != NULL)
1832 		for (j = class_size - 1; j >= 0; j--)
1833 		  {
1834 		    hard_regno = ira_class_hard_regs[aclass][j];
1835 		    ira_assert (hard_regno >= 0);
1836 		    k = ira_class_hard_reg_index[conflict_aclass][hard_regno];
1837 		    if (k < 0
1838 			   /* If HARD_REGNO is not available for CONFLICT_A,
1839 			      the conflict would be ignored, since HARD_REGNO
1840 			      will never be assigned to CONFLICT_A.  */
1841 			|| !TEST_HARD_REG_BIT (data->profitable_hard_regs,
1842 					       hard_regno))
1843 		      continue;
1844 		    full_costs[j] -= conflict_costs[k];
1845 		  }
1846 	      queue_update_cost (conflict_a, NULL, COST_HOP_DIVISOR);
1847 
1848 	    }
1849 	}
1850     }
1851   if (! retry_p)
1852     /* Take into account preferences of allocnos connected by copies to
1853        the conflict allocnos.  */
1854     update_conflict_hard_regno_costs (full_costs, aclass, true);
1855 
1856   /* Take preferences of allocnos connected by copies into
1857      account.  */
1858   if (! retry_p)
1859     {
1860       start_update_cost ();
1861       queue_update_cost (a, NULL,  COST_HOP_DIVISOR);
1862       update_conflict_hard_regno_costs (full_costs, aclass, false);
1863     }
1864   min_cost = min_full_cost = INT_MAX;
1865   /* We don't care about giving callee saved registers to allocnos no
1866      living through calls because call clobbered registers are
1867      allocated first (it is usual practice to put them first in
1868      REG_ALLOC_ORDER).  */
1869   mode = ALLOCNO_MODE (a);
1870   for (i = 0; i < class_size; i++)
1871     {
1872       hard_regno = ira_class_hard_regs[aclass][i];
1873 #ifdef STACK_REGS
1874       if (no_stack_reg_p
1875 	  && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
1876 	continue;
1877 #endif
1878       if (! check_hard_reg_p (a, hard_regno,
1879 			      conflicting_regs, profitable_hard_regs))
1880 	continue;
1881       cost = costs[i];
1882       full_cost = full_costs[i];
1883       if (!HONOR_REG_ALLOC_ORDER)
1884 	{
1885 	  if ((saved_nregs = calculate_saved_nregs (hard_regno, mode)) != 0)
1886 	  /* We need to save/restore the hard register in
1887 	     epilogue/prologue.  Therefore we increase the cost.  */
1888 	  {
1889 	    rclass = REGNO_REG_CLASS (hard_regno);
1890 	    add_cost = ((ira_memory_move_cost[mode][rclass][0]
1891 		         + ira_memory_move_cost[mode][rclass][1])
1892 		        * saved_nregs / hard_regno_nregs (hard_regno,
1893 							  mode) - 1);
1894 	    cost += add_cost;
1895 	    full_cost += add_cost;
1896 	  }
1897 	}
1898       if (min_cost > cost)
1899 	min_cost = cost;
1900       if (min_full_cost > full_cost)
1901 	{
1902 	  min_full_cost = full_cost;
1903 	  best_hard_regno = hard_regno;
1904 	  ira_assert (hard_regno >= 0);
1905 	}
1906     }
1907   if (min_full_cost > mem_cost
1908       /* Do not spill static chain pointer pseudo when non-local goto
1909 	 is used.  */
1910       && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1911     {
1912       if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1913 	fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
1914 		 mem_cost, min_full_cost);
1915       best_hard_regno = -1;
1916     }
1917  fail:
1918   if (best_hard_regno >= 0)
1919     {
1920       for (i = hard_regno_nregs (best_hard_regno, mode) - 1; i >= 0; i--)
1921 	allocated_hardreg_p[best_hard_regno + i] = true;
1922     }
1923   if (! retry_p)
1924     restore_costs_from_copies (a);
1925   ALLOCNO_HARD_REGNO (a) = best_hard_regno;
1926   ALLOCNO_ASSIGNED_P (a) = true;
1927   if (best_hard_regno >= 0)
1928     update_costs_from_copies (a, true, ! retry_p);
1929   ira_assert (ALLOCNO_CLASS (a) == aclass);
1930   /* We don't need updated costs anymore.  */
1931   ira_free_allocno_updated_costs (a);
1932   return best_hard_regno >= 0;
1933 }
1934 
1935 
1936 
1937 /* An array used to sort copies.  */
1938 static ira_copy_t *sorted_copies;
1939 
1940 /* If allocno A is a cap, return non-cap allocno from which A is
1941    created.  Otherwise, return A.  */
1942 static ira_allocno_t
get_cap_member(ira_allocno_t a)1943 get_cap_member (ira_allocno_t a)
1944 {
1945   ira_allocno_t member;
1946 
1947   while ((member = ALLOCNO_CAP_MEMBER (a)) != NULL)
1948     a = member;
1949   return a;
1950 }
1951 
1952 /* Return TRUE if live ranges of allocnos A1 and A2 intersect.  It is
1953    used to find a conflict for new allocnos or allocnos with the
1954    different allocno classes.  */
1955 static bool
allocnos_conflict_by_live_ranges_p(ira_allocno_t a1,ira_allocno_t a2)1956 allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
1957 {
1958   rtx reg1, reg2;
1959   int i, j;
1960   int n1 = ALLOCNO_NUM_OBJECTS (a1);
1961   int n2 = ALLOCNO_NUM_OBJECTS (a2);
1962 
1963   if (a1 == a2)
1964     return false;
1965   reg1 = regno_reg_rtx[ALLOCNO_REGNO (a1)];
1966   reg2 = regno_reg_rtx[ALLOCNO_REGNO (a2)];
1967   if (reg1 != NULL && reg2 != NULL
1968       && ORIGINAL_REGNO (reg1) == ORIGINAL_REGNO (reg2))
1969     return false;
1970 
1971   /* We don't keep live ranges for caps because they can be quite big.
1972      Use ranges of non-cap allocno from which caps are created.  */
1973   a1 = get_cap_member (a1);
1974   a2 = get_cap_member (a2);
1975   for (i = 0; i < n1; i++)
1976     {
1977       ira_object_t c1 = ALLOCNO_OBJECT (a1, i);
1978 
1979       for (j = 0; j < n2; j++)
1980 	{
1981 	  ira_object_t c2 = ALLOCNO_OBJECT (a2, j);
1982 
1983 	  if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1),
1984 					   OBJECT_LIVE_RANGES (c2)))
1985 	    return true;
1986 	}
1987     }
1988   return false;
1989 }
1990 
1991 /* The function is used to sort copies according to their execution
1992    frequencies.  */
1993 static int
copy_freq_compare_func(const void * v1p,const void * v2p)1994 copy_freq_compare_func (const void *v1p, const void *v2p)
1995 {
1996   ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
1997   int pri1, pri2;
1998 
1999   pri1 = cp1->freq;
2000   pri2 = cp2->freq;
2001   if (pri2 - pri1)
2002     return pri2 - pri1;
2003 
2004   /* If frequencies are equal, sort by copies, so that the results of
2005      qsort leave nothing to chance.  */
2006   return cp1->num - cp2->num;
2007 }
2008 
2009 
2010 
2011 /* Return true if any allocno from thread of A1 conflicts with any
2012    allocno from thread A2.  */
2013 static bool
allocno_thread_conflict_p(ira_allocno_t a1,ira_allocno_t a2)2014 allocno_thread_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
2015 {
2016   ira_allocno_t a, conflict_a;
2017 
2018   for (a = ALLOCNO_COLOR_DATA (a2)->next_thread_allocno;;
2019        a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2020     {
2021       for (conflict_a = ALLOCNO_COLOR_DATA (a1)->next_thread_allocno;;
2022 	   conflict_a = ALLOCNO_COLOR_DATA (conflict_a)->next_thread_allocno)
2023 	{
2024 	  if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
2025 	    return true;
2026 	  if (conflict_a == a1)
2027 	    break;
2028 	}
2029       if (a == a2)
2030 	break;
2031     }
2032   return false;
2033 }
2034 
2035 /* Merge two threads given correspondingly by their first allocnos T1
2036    and T2 (more accurately merging T2 into T1).  */
2037 static void
merge_threads(ira_allocno_t t1,ira_allocno_t t2)2038 merge_threads (ira_allocno_t t1, ira_allocno_t t2)
2039 {
2040   ira_allocno_t a, next, last;
2041 
2042   gcc_assert (t1 != t2
2043 	      && ALLOCNO_COLOR_DATA (t1)->first_thread_allocno == t1
2044 	      && ALLOCNO_COLOR_DATA (t2)->first_thread_allocno == t2);
2045   for (last = t2, a = ALLOCNO_COLOR_DATA (t2)->next_thread_allocno;;
2046        a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2047     {
2048       ALLOCNO_COLOR_DATA (a)->first_thread_allocno = t1;
2049       if (a == t2)
2050 	break;
2051       last = a;
2052     }
2053   next = ALLOCNO_COLOR_DATA (t1)->next_thread_allocno;
2054   ALLOCNO_COLOR_DATA (t1)->next_thread_allocno = t2;
2055   ALLOCNO_COLOR_DATA (last)->next_thread_allocno = next;
2056   ALLOCNO_COLOR_DATA (t1)->thread_freq += ALLOCNO_COLOR_DATA (t2)->thread_freq;
2057 }
2058 
2059 /* Create threads by processing CP_NUM copies from sorted copies.  We
2060    process the most expensive copies first.  */
2061 static void
form_threads_from_copies(int cp_num)2062 form_threads_from_copies (int cp_num)
2063 {
2064   ira_allocno_t a, thread1, thread2;
2065   ira_copy_t cp;
2066   int i, n;
2067 
2068   qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
2069   /* Form threads processing copies, most frequently executed
2070      first.  */
2071   for (; cp_num != 0;)
2072     {
2073       for (i = 0; i < cp_num; i++)
2074 	{
2075 	  cp = sorted_copies[i];
2076 	  thread1 = ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno;
2077 	  thread2 = ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno;
2078 	  if (thread1 == thread2)
2079 	    continue;
2080 	  if (! allocno_thread_conflict_p (thread1, thread2))
2081 	    {
2082 	      if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2083 		fprintf
2084 		  (ira_dump_file,
2085 		   "      Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n",
2086 		   cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
2087 		   ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
2088 		   cp->freq);
2089 	      merge_threads (thread1, thread2);
2090 	      if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2091 		{
2092 		  thread1 = ALLOCNO_COLOR_DATA (thread1)->first_thread_allocno;
2093 		  fprintf (ira_dump_file, "        Result (freq=%d): a%dr%d(%d)",
2094 			   ALLOCNO_COLOR_DATA (thread1)->thread_freq,
2095 			   ALLOCNO_NUM (thread1), ALLOCNO_REGNO (thread1),
2096 			   ALLOCNO_FREQ (thread1));
2097 		  for (a = ALLOCNO_COLOR_DATA (thread1)->next_thread_allocno;
2098 		       a != thread1;
2099 		       a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2100 		    fprintf (ira_dump_file, " a%dr%d(%d)",
2101 			     ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2102 			     ALLOCNO_FREQ (a));
2103 		  fprintf (ira_dump_file, "\n");
2104 		}
2105 	      i++;
2106 	      break;
2107 	    }
2108 	}
2109       /* Collect the rest of copies.  */
2110       for (n = 0; i < cp_num; i++)
2111 	{
2112 	  cp = sorted_copies[i];
2113 	  if (ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno
2114 	      != ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno)
2115 	    sorted_copies[n++] = cp;
2116 	}
2117       cp_num = n;
2118     }
2119 }
2120 
2121 /* Create threads by processing copies of all alocnos from BUCKET.  We
2122    process the most expensive copies first.  */
2123 static void
form_threads_from_bucket(ira_allocno_t bucket)2124 form_threads_from_bucket (ira_allocno_t bucket)
2125 {
2126   ira_allocno_t a;
2127   ira_copy_t cp, next_cp;
2128   int cp_num = 0;
2129 
2130   for (a = bucket; a != NULL; a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2131     {
2132       for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2133 	{
2134 	  if (cp->first == a)
2135 	    {
2136 	      next_cp = cp->next_first_allocno_copy;
2137 	      sorted_copies[cp_num++] = cp;
2138 	    }
2139 	  else if (cp->second == a)
2140 	    next_cp = cp->next_second_allocno_copy;
2141 	  else
2142 	    gcc_unreachable ();
2143 	}
2144     }
2145   form_threads_from_copies (cp_num);
2146 }
2147 
2148 /* Create threads by processing copies of colorable allocno A.  We
2149    process most expensive copies first.  */
2150 static void
form_threads_from_colorable_allocno(ira_allocno_t a)2151 form_threads_from_colorable_allocno (ira_allocno_t a)
2152 {
2153   ira_allocno_t another_a;
2154   ira_copy_t cp, next_cp;
2155   int cp_num = 0;
2156 
2157   for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2158     {
2159       if (cp->first == a)
2160 	{
2161 	  next_cp = cp->next_first_allocno_copy;
2162 	  another_a = cp->second;
2163 	}
2164       else if (cp->second == a)
2165 	{
2166 	  next_cp = cp->next_second_allocno_copy;
2167 	  another_a = cp->first;
2168 	}
2169       else
2170 	gcc_unreachable ();
2171       if ((! ALLOCNO_COLOR_DATA (another_a)->in_graph_p
2172 	   && !ALLOCNO_COLOR_DATA (another_a)->may_be_spilled_p)
2173 	   || ALLOCNO_COLOR_DATA (another_a)->colorable_p)
2174 	sorted_copies[cp_num++] = cp;
2175     }
2176   form_threads_from_copies (cp_num);
2177 }
2178 
2179 /* Form initial threads which contain only one allocno.  */
2180 static void
init_allocno_threads(void)2181 init_allocno_threads (void)
2182 {
2183   ira_allocno_t a;
2184   unsigned int j;
2185   bitmap_iterator bi;
2186 
2187   EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2188     {
2189       a = ira_allocnos[j];
2190       /* Set up initial thread data: */
2191       ALLOCNO_COLOR_DATA (a)->first_thread_allocno
2192 	= ALLOCNO_COLOR_DATA (a)->next_thread_allocno = a;
2193       ALLOCNO_COLOR_DATA (a)->thread_freq = ALLOCNO_FREQ (a);
2194     }
2195 }
2196 
2197 
2198 
2199 /* This page contains the allocator based on the Chaitin-Briggs algorithm.  */
2200 
2201 /* Bucket of allocnos that can colored currently without spilling.  */
2202 static ira_allocno_t colorable_allocno_bucket;
2203 
2204 /* Bucket of allocnos that might be not colored currently without
2205    spilling.  */
2206 static ira_allocno_t uncolorable_allocno_bucket;
2207 
2208 /* The current number of allocnos in the uncolorable_bucket.  */
2209 static int uncolorable_allocnos_num;
2210 
2211 /* Return the current spill priority of allocno A.  The less the
2212    number, the more preferable the allocno for spilling.  */
2213 static inline int
allocno_spill_priority(ira_allocno_t a)2214 allocno_spill_priority (ira_allocno_t a)
2215 {
2216   allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
2217 
2218   return (data->temp
2219 	  / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2220 	     * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
2221 	     + 1));
2222 }
2223 
2224 /* Add allocno A to bucket *BUCKET_PTR.  A should be not in a bucket
2225    before the call.  */
2226 static void
add_allocno_to_bucket(ira_allocno_t a,ira_allocno_t * bucket_ptr)2227 add_allocno_to_bucket (ira_allocno_t a, ira_allocno_t *bucket_ptr)
2228 {
2229   ira_allocno_t first_a;
2230   allocno_color_data_t data;
2231 
2232   if (bucket_ptr == &uncolorable_allocno_bucket
2233       && ALLOCNO_CLASS (a) != NO_REGS)
2234     {
2235       uncolorable_allocnos_num++;
2236       ira_assert (uncolorable_allocnos_num > 0);
2237     }
2238   first_a = *bucket_ptr;
2239   data = ALLOCNO_COLOR_DATA (a);
2240   data->next_bucket_allocno = first_a;
2241   data->prev_bucket_allocno = NULL;
2242   if (first_a != NULL)
2243     ALLOCNO_COLOR_DATA (first_a)->prev_bucket_allocno = a;
2244   *bucket_ptr = a;
2245 }
2246 
2247 /* Compare two allocnos to define which allocno should be pushed first
2248    into the coloring stack.  If the return is a negative number, the
2249    allocno given by the first parameter will be pushed first.  In this
2250    case such allocno has less priority than the second one and the
2251    hard register will be assigned to it after assignment to the second
2252    one.  As the result of such assignment order, the second allocno
2253    has a better chance to get the best hard register.  */
2254 static int
bucket_allocno_compare_func(const void * v1p,const void * v2p)2255 bucket_allocno_compare_func (const void *v1p, const void *v2p)
2256 {
2257   ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2258   ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2259   int diff, freq1, freq2, a1_num, a2_num, pref1, pref2;
2260   ira_allocno_t t1 = ALLOCNO_COLOR_DATA (a1)->first_thread_allocno;
2261   ira_allocno_t t2 = ALLOCNO_COLOR_DATA (a2)->first_thread_allocno;
2262   int cl1 = ALLOCNO_CLASS (a1), cl2 = ALLOCNO_CLASS (a2);
2263 
2264   freq1 = ALLOCNO_COLOR_DATA (t1)->thread_freq;
2265   freq2 = ALLOCNO_COLOR_DATA (t2)->thread_freq;
2266   if ((diff = freq1 - freq2) != 0)
2267     return diff;
2268 
2269   if ((diff = ALLOCNO_NUM (t2) - ALLOCNO_NUM (t1)) != 0)
2270     return diff;
2271 
2272   /* Push pseudos requiring less hard registers first.  It means that
2273      we will assign pseudos requiring more hard registers first
2274      avoiding creation small holes in free hard register file into
2275      which the pseudos requiring more hard registers can not fit.  */
2276   if ((diff = (ira_reg_class_max_nregs[cl1][ALLOCNO_MODE (a1)]
2277 	       - ira_reg_class_max_nregs[cl2][ALLOCNO_MODE (a2)])) != 0)
2278     return diff;
2279 
2280   freq1 = ALLOCNO_FREQ (a1);
2281   freq2 = ALLOCNO_FREQ (a2);
2282   if ((diff = freq1 - freq2) != 0)
2283     return diff;
2284 
2285   a1_num = ALLOCNO_COLOR_DATA (a1)->available_regs_num;
2286   a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num;
2287   if ((diff = a2_num - a1_num) != 0)
2288     return diff;
2289   /* Push allocnos with minimal conflict_allocno_hard_prefs first.  */
2290   pref1 = ALLOCNO_COLOR_DATA (a1)->conflict_allocno_hard_prefs;
2291   pref2 = ALLOCNO_COLOR_DATA (a2)->conflict_allocno_hard_prefs;
2292   if ((diff = pref1 - pref2) != 0)
2293     return diff;
2294   return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2295 }
2296 
2297 /* Sort bucket *BUCKET_PTR and return the result through
2298    BUCKET_PTR.  */
2299 static void
sort_bucket(ira_allocno_t * bucket_ptr,int (* compare_func)(const void *,const void *))2300 sort_bucket (ira_allocno_t *bucket_ptr,
2301 	     int (*compare_func) (const void *, const void *))
2302 {
2303   ira_allocno_t a, head;
2304   int n;
2305 
2306   for (n = 0, a = *bucket_ptr;
2307        a != NULL;
2308        a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2309     sorted_allocnos[n++] = a;
2310   if (n <= 1)
2311     return;
2312   qsort (sorted_allocnos, n, sizeof (ira_allocno_t), compare_func);
2313   head = NULL;
2314   for (n--; n >= 0; n--)
2315     {
2316       a = sorted_allocnos[n];
2317       ALLOCNO_COLOR_DATA (a)->next_bucket_allocno = head;
2318       ALLOCNO_COLOR_DATA (a)->prev_bucket_allocno = NULL;
2319       if (head != NULL)
2320 	ALLOCNO_COLOR_DATA (head)->prev_bucket_allocno = a;
2321       head = a;
2322     }
2323   *bucket_ptr = head;
2324 }
2325 
2326 /* Add ALLOCNO to colorable bucket maintaining the order according
2327    their priority.  ALLOCNO should be not in a bucket before the
2328    call.  */
2329 static void
add_allocno_to_ordered_colorable_bucket(ira_allocno_t allocno)2330 add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno)
2331 {
2332   ira_allocno_t before, after;
2333 
2334   form_threads_from_colorable_allocno (allocno);
2335   for (before = colorable_allocno_bucket, after = NULL;
2336        before != NULL;
2337        after = before,
2338 	 before = ALLOCNO_COLOR_DATA (before)->next_bucket_allocno)
2339     if (bucket_allocno_compare_func (&allocno, &before) < 0)
2340       break;
2341   ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno = before;
2342   ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno = after;
2343   if (after == NULL)
2344     colorable_allocno_bucket = allocno;
2345   else
2346     ALLOCNO_COLOR_DATA (after)->next_bucket_allocno = allocno;
2347   if (before != NULL)
2348     ALLOCNO_COLOR_DATA (before)->prev_bucket_allocno = allocno;
2349 }
2350 
2351 /* Delete ALLOCNO from bucket *BUCKET_PTR.  It should be there before
2352    the call.  */
2353 static void
delete_allocno_from_bucket(ira_allocno_t allocno,ira_allocno_t * bucket_ptr)2354 delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
2355 {
2356   ira_allocno_t prev_allocno, next_allocno;
2357 
2358   if (bucket_ptr == &uncolorable_allocno_bucket
2359       && ALLOCNO_CLASS (allocno) != NO_REGS)
2360     {
2361       uncolorable_allocnos_num--;
2362       ira_assert (uncolorable_allocnos_num >= 0);
2363     }
2364   prev_allocno = ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno;
2365   next_allocno = ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno;
2366   if (prev_allocno != NULL)
2367     ALLOCNO_COLOR_DATA (prev_allocno)->next_bucket_allocno = next_allocno;
2368   else
2369     {
2370       ira_assert (*bucket_ptr == allocno);
2371       *bucket_ptr = next_allocno;
2372     }
2373   if (next_allocno != NULL)
2374     ALLOCNO_COLOR_DATA (next_allocno)->prev_bucket_allocno = prev_allocno;
2375 }
2376 
2377 /* Put allocno A onto the coloring stack without removing it from its
2378    bucket.  Pushing allocno to the coloring stack can result in moving
2379    conflicting allocnos from the uncolorable bucket to the colorable
2380    one.  Update conflict_allocno_hard_prefs of the conflicting
2381    allocnos which are not on stack yet.  */
2382 static void
push_allocno_to_stack(ira_allocno_t a)2383 push_allocno_to_stack (ira_allocno_t a)
2384 {
2385   enum reg_class aclass;
2386   allocno_color_data_t data, conflict_data;
2387   int size, i, n = ALLOCNO_NUM_OBJECTS (a);
2388 
2389   data = ALLOCNO_COLOR_DATA (a);
2390   data->in_graph_p = false;
2391   allocno_stack_vec.safe_push (a);
2392   aclass = ALLOCNO_CLASS (a);
2393   if (aclass == NO_REGS)
2394     return;
2395   size = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
2396   if (n > 1)
2397     {
2398       /* We will deal with the subwords individually.  */
2399       gcc_assert (size == ALLOCNO_NUM_OBJECTS (a));
2400       size = 1;
2401     }
2402   for (i = 0; i < n; i++)
2403     {
2404       ira_object_t obj = ALLOCNO_OBJECT (a, i);
2405       ira_object_t conflict_obj;
2406       ira_object_conflict_iterator oci;
2407 
2408       FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2409 	{
2410 	  ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2411 	  ira_pref_t pref;
2412 
2413 	  conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
2414 	  if (! conflict_data->in_graph_p
2415 	      || ALLOCNO_ASSIGNED_P (conflict_a)
2416 	      || !(hard_reg_set_intersect_p
2417 		   (ALLOCNO_COLOR_DATA (a)->profitable_hard_regs,
2418 		    conflict_data->profitable_hard_regs)))
2419 	    continue;
2420 	  for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
2421 	    conflict_data->conflict_allocno_hard_prefs -= pref->freq;
2422 	  if (conflict_data->colorable_p)
2423 	    continue;
2424 	  ira_assert (bitmap_bit_p (coloring_allocno_bitmap,
2425 				    ALLOCNO_NUM (conflict_a)));
2426 	  if (update_left_conflict_sizes_p (conflict_a, a, size))
2427 	    {
2428 	      delete_allocno_from_bucket
2429 		(conflict_a, &uncolorable_allocno_bucket);
2430 	      add_allocno_to_ordered_colorable_bucket (conflict_a);
2431 	      if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2432 		{
2433 		  fprintf (ira_dump_file, "        Making");
2434 		  ira_print_expanded_allocno (conflict_a);
2435 		  fprintf (ira_dump_file, " colorable\n");
2436 		}
2437 	    }
2438 
2439 	}
2440     }
2441 }
2442 
2443 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
2444    The allocno is in the colorable bucket if COLORABLE_P is TRUE.  */
2445 static void
remove_allocno_from_bucket_and_push(ira_allocno_t allocno,bool colorable_p)2446 remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
2447 {
2448   if (colorable_p)
2449     delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
2450   else
2451     delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
2452   if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2453     {
2454       fprintf (ira_dump_file, "      Pushing");
2455       ira_print_expanded_allocno (allocno);
2456       if (colorable_p)
2457 	fprintf (ira_dump_file, "(cost %d)\n",
2458 		 ALLOCNO_COLOR_DATA (allocno)->temp);
2459       else
2460 	fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n",
2461 		 ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
2462 		 allocno_spill_priority (allocno),
2463 		 ALLOCNO_COLOR_DATA (allocno)->temp);
2464     }
2465   if (! colorable_p)
2466     ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p = true;
2467   push_allocno_to_stack (allocno);
2468 }
2469 
2470 /* Put all allocnos from colorable bucket onto the coloring stack.  */
2471 static void
push_only_colorable(void)2472 push_only_colorable (void)
2473 {
2474   form_threads_from_bucket (colorable_allocno_bucket);
2475   sort_bucket (&colorable_allocno_bucket, bucket_allocno_compare_func);
2476   for (;colorable_allocno_bucket != NULL;)
2477     remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
2478 }
2479 
2480 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2481    loop given by its LOOP_NODE.  */
2482 int
ira_loop_edge_freq(ira_loop_tree_node_t loop_node,int regno,bool exit_p)2483 ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
2484 {
2485   int freq, i;
2486   edge_iterator ei;
2487   edge e;
2488   vec<edge> edges;
2489 
2490   ira_assert (current_loops != NULL && loop_node->loop != NULL
2491 	      && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
2492   freq = 0;
2493   if (! exit_p)
2494     {
2495       FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
2496 	if (e->src != loop_node->loop->latch
2497 	    && (regno < 0
2498 		|| (bitmap_bit_p (df_get_live_out (e->src), regno)
2499 		    && bitmap_bit_p (df_get_live_in (e->dest), regno))))
2500 	  freq += EDGE_FREQUENCY (e);
2501     }
2502   else
2503     {
2504       edges = get_loop_exit_edges (loop_node->loop);
2505       FOR_EACH_VEC_ELT (edges, i, e)
2506 	if (regno < 0
2507 	    || (bitmap_bit_p (df_get_live_out (e->src), regno)
2508 		&& bitmap_bit_p (df_get_live_in (e->dest), regno)))
2509 	  freq += EDGE_FREQUENCY (e);
2510       edges.release ();
2511     }
2512 
2513   return REG_FREQ_FROM_EDGE_FREQ (freq);
2514 }
2515 
2516 /* Calculate and return the cost of putting allocno A into memory.  */
2517 static int
calculate_allocno_spill_cost(ira_allocno_t a)2518 calculate_allocno_spill_cost (ira_allocno_t a)
2519 {
2520   int regno, cost;
2521   machine_mode mode;
2522   enum reg_class rclass;
2523   ira_allocno_t parent_allocno;
2524   ira_loop_tree_node_t parent_node, loop_node;
2525 
2526   regno = ALLOCNO_REGNO (a);
2527   cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_CLASS_COST (a);
2528   if (ALLOCNO_CAP (a) != NULL)
2529     return cost;
2530   loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2531   if ((parent_node = loop_node->parent) == NULL)
2532     return cost;
2533   if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
2534     return cost;
2535   mode = ALLOCNO_MODE (a);
2536   rclass = ALLOCNO_CLASS (a);
2537   if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
2538     cost -= (ira_memory_move_cost[mode][rclass][0]
2539 	     * ira_loop_edge_freq (loop_node, regno, true)
2540 	     + ira_memory_move_cost[mode][rclass][1]
2541 	     * ira_loop_edge_freq (loop_node, regno, false));
2542   else
2543     {
2544       ira_init_register_move_cost_if_necessary (mode);
2545       cost += ((ira_memory_move_cost[mode][rclass][1]
2546 		* ira_loop_edge_freq (loop_node, regno, true)
2547 		+ ira_memory_move_cost[mode][rclass][0]
2548 		* ira_loop_edge_freq (loop_node, regno, false))
2549 	       - (ira_register_move_cost[mode][rclass][rclass]
2550 		  * (ira_loop_edge_freq (loop_node, regno, false)
2551 		     + ira_loop_edge_freq (loop_node, regno, true))));
2552     }
2553   return cost;
2554 }
2555 
2556 /* Used for sorting allocnos for spilling.  */
2557 static inline int
allocno_spill_priority_compare(ira_allocno_t a1,ira_allocno_t a2)2558 allocno_spill_priority_compare (ira_allocno_t a1, ira_allocno_t a2)
2559 {
2560   int pri1, pri2, diff;
2561 
2562   /* Avoid spilling static chain pointer pseudo when non-local goto is
2563      used.  */
2564   if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))
2565     return 1;
2566   else if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2)))
2567     return -1;
2568   if (ALLOCNO_BAD_SPILL_P (a1) && ! ALLOCNO_BAD_SPILL_P (a2))
2569     return 1;
2570   if (ALLOCNO_BAD_SPILL_P (a2) && ! ALLOCNO_BAD_SPILL_P (a1))
2571     return -1;
2572   pri1 = allocno_spill_priority (a1);
2573   pri2 = allocno_spill_priority (a2);
2574   if ((diff = pri1 - pri2) != 0)
2575     return diff;
2576   if ((diff
2577        = ALLOCNO_COLOR_DATA (a1)->temp - ALLOCNO_COLOR_DATA (a2)->temp) != 0)
2578     return diff;
2579   return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2580 }
2581 
2582 /* Used for sorting allocnos for spilling.  */
2583 static int
allocno_spill_sort_compare(const void * v1p,const void * v2p)2584 allocno_spill_sort_compare (const void *v1p, const void *v2p)
2585 {
2586   ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2587   ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2588 
2589   return allocno_spill_priority_compare (p1, p2);
2590 }
2591 
2592 /* Push allocnos to the coloring stack.  The order of allocnos in the
2593    stack defines the order for the subsequent coloring.  */
2594 static void
push_allocnos_to_stack(void)2595 push_allocnos_to_stack (void)
2596 {
2597   ira_allocno_t a;
2598   int cost;
2599 
2600   /* Calculate uncolorable allocno spill costs.  */
2601   for (a = uncolorable_allocno_bucket;
2602        a != NULL;
2603        a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2604     if (ALLOCNO_CLASS (a) != NO_REGS)
2605       {
2606 	cost = calculate_allocno_spill_cost (a);
2607 	/* ??? Remove cost of copies between the coalesced
2608 	   allocnos.  */
2609 	ALLOCNO_COLOR_DATA (a)->temp = cost;
2610       }
2611   sort_bucket (&uncolorable_allocno_bucket, allocno_spill_sort_compare);
2612   for (;;)
2613     {
2614       push_only_colorable ();
2615       a = uncolorable_allocno_bucket;
2616       if (a == NULL)
2617 	break;
2618       remove_allocno_from_bucket_and_push (a, false);
2619     }
2620   ira_assert (colorable_allocno_bucket == NULL
2621 	      && uncolorable_allocno_bucket == NULL);
2622   ira_assert (uncolorable_allocnos_num == 0);
2623 }
2624 
2625 /* Pop the coloring stack and assign hard registers to the popped
2626    allocnos.  */
2627 static void
pop_allocnos_from_stack(void)2628 pop_allocnos_from_stack (void)
2629 {
2630   ira_allocno_t allocno;
2631   enum reg_class aclass;
2632 
2633   for (;allocno_stack_vec.length () != 0;)
2634     {
2635       allocno = allocno_stack_vec.pop ();
2636       aclass = ALLOCNO_CLASS (allocno);
2637       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2638 	{
2639 	  fprintf (ira_dump_file, "      Popping");
2640 	  ira_print_expanded_allocno (allocno);
2641 	  fprintf (ira_dump_file, "  -- ");
2642 	}
2643       if (aclass == NO_REGS)
2644 	{
2645 	  ALLOCNO_HARD_REGNO (allocno) = -1;
2646 	  ALLOCNO_ASSIGNED_P (allocno) = true;
2647 	  ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
2648 	  ira_assert
2649 	    (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
2650 	  if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2651 	    fprintf (ira_dump_file, "assign memory\n");
2652 	}
2653       else if (assign_hard_reg (allocno, false))
2654 	{
2655 	  if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2656 	    fprintf (ira_dump_file, "assign reg %d\n",
2657 		     ALLOCNO_HARD_REGNO (allocno));
2658 	}
2659       else if (ALLOCNO_ASSIGNED_P (allocno))
2660 	{
2661 	  if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2662 	    fprintf (ira_dump_file, "spill%s\n",
2663 		     ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p
2664 		     ? "" : "!");
2665 	}
2666       ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2667     }
2668 }
2669 
2670 /* Set up number of available hard registers for allocno A.  */
2671 static void
setup_allocno_available_regs_num(ira_allocno_t a)2672 setup_allocno_available_regs_num (ira_allocno_t a)
2673 {
2674   int i, n, hard_regno, hard_regs_num, nwords;
2675   enum reg_class aclass;
2676   allocno_color_data_t data;
2677 
2678   aclass = ALLOCNO_CLASS (a);
2679   data = ALLOCNO_COLOR_DATA (a);
2680   data->available_regs_num = 0;
2681   if (aclass == NO_REGS)
2682     return;
2683   hard_regs_num = ira_class_hard_regs_num[aclass];
2684   nwords = ALLOCNO_NUM_OBJECTS (a);
2685   for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
2686     {
2687       hard_regno = ira_class_hard_regs[aclass][i];
2688       /* Checking only profitable hard regs.  */
2689       if (TEST_HARD_REG_BIT (data->profitable_hard_regs, hard_regno))
2690 	n++;
2691     }
2692   data->available_regs_num = n;
2693   if (internal_flag_ira_verbose <= 2 || ira_dump_file == NULL)
2694     return;
2695   fprintf
2696     (ira_dump_file,
2697      "      Allocno a%dr%d of %s(%d) has %d avail. regs ",
2698      ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2699      reg_class_names[aclass], ira_class_hard_regs_num[aclass], n);
2700   print_hard_reg_set (ira_dump_file, data->profitable_hard_regs, false);
2701   fprintf (ira_dump_file, ", %snode: ",
2702 	   hard_reg_set_equal_p (data->profitable_hard_regs,
2703 				 data->hard_regs_node->hard_regs->set)
2704 	   ? "" : "^");
2705   print_hard_reg_set (ira_dump_file,
2706 		      data->hard_regs_node->hard_regs->set, false);
2707   for (i = 0; i < nwords; i++)
2708     {
2709       ira_object_t obj = ALLOCNO_OBJECT (a, i);
2710 
2711       if (nwords != 1)
2712 	{
2713 	  if (i != 0)
2714 	    fprintf (ira_dump_file, ", ");
2715 	  fprintf (ira_dump_file, " obj %d", i);
2716 	}
2717       fprintf (ira_dump_file, " (confl regs = ");
2718       print_hard_reg_set (ira_dump_file, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2719 			  false);
2720       fprintf (ira_dump_file, ")");
2721     }
2722   fprintf (ira_dump_file, "\n");
2723 }
2724 
2725 /* Put ALLOCNO in a bucket corresponding to its number and size of its
2726    conflicting allocnos and hard registers.  */
2727 static void
put_allocno_into_bucket(ira_allocno_t allocno)2728 put_allocno_into_bucket (ira_allocno_t allocno)
2729 {
2730   ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2731   setup_allocno_available_regs_num (allocno);
2732   if (setup_left_conflict_sizes_p (allocno))
2733     add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
2734   else
2735     add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
2736 }
2737 
2738 /* Map: allocno number -> allocno priority.  */
2739 static int *allocno_priorities;
2740 
2741 /* Set up priorities for N allocnos in array
2742    CONSIDERATION_ALLOCNOS.  */
2743 static void
setup_allocno_priorities(ira_allocno_t * consideration_allocnos,int n)2744 setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
2745 {
2746   int i, length, nrefs, priority, max_priority, mult;
2747   ira_allocno_t a;
2748 
2749   max_priority = 0;
2750   for (i = 0; i < n; i++)
2751     {
2752       a = consideration_allocnos[i];
2753       nrefs = ALLOCNO_NREFS (a);
2754       ira_assert (nrefs >= 0);
2755       mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
2756       ira_assert (mult >= 0);
2757       allocno_priorities[ALLOCNO_NUM (a)]
2758 	= priority
2759 	= (mult
2760 	   * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a))
2761 	   * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
2762       if (priority < 0)
2763 	priority = -priority;
2764       if (max_priority < priority)
2765 	max_priority = priority;
2766     }
2767   mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
2768   for (i = 0; i < n; i++)
2769     {
2770       a = consideration_allocnos[i];
2771       length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2772       if (ALLOCNO_NUM_OBJECTS (a) > 1)
2773 	length /= ALLOCNO_NUM_OBJECTS (a);
2774       if (length <= 0)
2775 	length = 1;
2776       allocno_priorities[ALLOCNO_NUM (a)]
2777 	= allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
2778     }
2779 }
2780 
2781 /* Sort allocnos according to the profit of usage of a hard register
2782    instead of memory for them. */
2783 static int
allocno_cost_compare_func(const void * v1p,const void * v2p)2784 allocno_cost_compare_func (const void *v1p, const void *v2p)
2785 {
2786   ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2787   ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2788   int c1, c2;
2789 
2790   c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_CLASS_COST (p1);
2791   c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_CLASS_COST (p2);
2792   if (c1 - c2)
2793     return c1 - c2;
2794 
2795   /* If regs are equally good, sort by allocno numbers, so that the
2796      results of qsort leave nothing to chance.  */
2797   return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
2798 }
2799 
2800 /* Return savings on removed copies when ALLOCNO is assigned to
2801    HARD_REGNO.  */
2802 static int
allocno_copy_cost_saving(ira_allocno_t allocno,int hard_regno)2803 allocno_copy_cost_saving (ira_allocno_t allocno, int hard_regno)
2804 {
2805   int cost = 0;
2806   machine_mode allocno_mode = ALLOCNO_MODE (allocno);
2807   enum reg_class rclass;
2808   ira_copy_t cp, next_cp;
2809 
2810   rclass = REGNO_REG_CLASS (hard_regno);
2811   if (ira_reg_class_max_nregs[rclass][allocno_mode]
2812       > ira_class_hard_regs_num[rclass])
2813     /* For the above condition the cost can be wrong.  Use the allocno
2814        class in this case.  */
2815     rclass = ALLOCNO_CLASS (allocno);
2816   for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
2817     {
2818       if (cp->first == allocno)
2819 	{
2820 	  next_cp = cp->next_first_allocno_copy;
2821 	  if (ALLOCNO_HARD_REGNO (cp->second) != hard_regno)
2822 	    continue;
2823 	}
2824       else if (cp->second == allocno)
2825 	{
2826 	  next_cp = cp->next_second_allocno_copy;
2827 	  if (ALLOCNO_HARD_REGNO (cp->first) != hard_regno)
2828 	    continue;
2829 	}
2830       else
2831 	gcc_unreachable ();
2832       cost += cp->freq * ira_register_move_cost[allocno_mode][rclass][rclass];
2833     }
2834   return cost;
2835 }
2836 
2837 /* We used Chaitin-Briggs coloring to assign as many pseudos as
2838    possible to hard registers.  Let us try to improve allocation with
2839    cost point of view.  This function improves the allocation by
2840    spilling some allocnos and assigning the freed hard registers to
2841    other allocnos if it decreases the overall allocation cost.  */
2842 static void
improve_allocation(void)2843 improve_allocation (void)
2844 {
2845   unsigned int i;
2846   int j, k, n, hregno, conflict_hregno, base_cost, class_size, word, nwords;
2847   int check, spill_cost, min_cost, nregs, conflict_nregs, r, best;
2848   bool try_p;
2849   enum reg_class aclass;
2850   machine_mode mode;
2851   int *allocno_costs;
2852   int costs[FIRST_PSEUDO_REGISTER];
2853   HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
2854   ira_allocno_t a;
2855   bitmap_iterator bi;
2856 
2857   /* Don't bother to optimize the code with static chain pointer and
2858      non-local goto in order not to spill the chain pointer
2859      pseudo.  */
2860   if (cfun->static_chain_decl && crtl->has_nonlocal_goto)
2861     return;
2862   /* Clear counts used to process conflicting allocnos only once for
2863      each allocno.  */
2864   EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2865     ALLOCNO_COLOR_DATA (ira_allocnos[i])->temp = 0;
2866   check = n = 0;
2867   /* Process each allocno and try to assign a hard register to it by
2868      spilling some its conflicting allocnos.  */
2869   EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2870     {
2871       a = ira_allocnos[i];
2872       ALLOCNO_COLOR_DATA (a)->temp = 0;
2873       if (empty_profitable_hard_regs (a))
2874 	continue;
2875       check++;
2876       aclass = ALLOCNO_CLASS (a);
2877       allocno_costs = ALLOCNO_HARD_REG_COSTS (a);
2878       if ((hregno = ALLOCNO_HARD_REGNO (a)) < 0)
2879 	base_cost = ALLOCNO_UPDATED_MEMORY_COST (a);
2880       else if (allocno_costs == NULL)
2881 	/* It means that assigning a hard register is not profitable
2882 	   (we don't waste memory for hard register costs in this
2883 	   case).  */
2884 	continue;
2885       else
2886 	base_cost = (allocno_costs[ira_class_hard_reg_index[aclass][hregno]]
2887 		     - allocno_copy_cost_saving (a, hregno));
2888       try_p = false;
2889       get_conflict_and_start_profitable_regs (a, false,
2890 					      conflicting_regs,
2891 					      &profitable_hard_regs);
2892       class_size = ira_class_hard_regs_num[aclass];
2893       /* Set up cost improvement for usage of each profitable hard
2894 	 register for allocno A.  */
2895       for (j = 0; j < class_size; j++)
2896 	{
2897 	  hregno = ira_class_hard_regs[aclass][j];
2898 	  if (! check_hard_reg_p (a, hregno,
2899 				  conflicting_regs, profitable_hard_regs))
2900 	    continue;
2901 	  ira_assert (ira_class_hard_reg_index[aclass][hregno] == j);
2902 	  k = allocno_costs == NULL ? 0 : j;
2903 	  costs[hregno] = (allocno_costs == NULL
2904 			   ? ALLOCNO_UPDATED_CLASS_COST (a) : allocno_costs[k]);
2905 	  costs[hregno] -= allocno_copy_cost_saving (a, hregno);
2906 	  costs[hregno] -= base_cost;
2907 	  if (costs[hregno] < 0)
2908 	    try_p = true;
2909 	}
2910       if (! try_p)
2911 	/* There is no chance to improve the allocation cost by
2912 	   assigning hard register to allocno A even without spilling
2913 	   conflicting allocnos.  */
2914 	continue;
2915       mode = ALLOCNO_MODE (a);
2916       nwords = ALLOCNO_NUM_OBJECTS (a);
2917       /* Process each allocno conflicting with A and update the cost
2918 	 improvement for profitable hard registers of A.  To use a
2919 	 hard register for A we need to spill some conflicting
2920 	 allocnos and that creates penalty for the cost
2921 	 improvement.  */
2922       for (word = 0; word < nwords; word++)
2923 	{
2924 	  ira_object_t conflict_obj;
2925 	  ira_object_t obj = ALLOCNO_OBJECT (a, word);
2926 	  ira_object_conflict_iterator oci;
2927 
2928 	  FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2929 	    {
2930 	      ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2931 
2932 	      if (ALLOCNO_COLOR_DATA (conflict_a)->temp == check)
2933 		/* We already processed this conflicting allocno
2934 		   because we processed earlier another object of the
2935 		   conflicting allocno.  */
2936 		continue;
2937 	      ALLOCNO_COLOR_DATA (conflict_a)->temp = check;
2938 	      if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2939 		continue;
2940 	      spill_cost = ALLOCNO_UPDATED_MEMORY_COST (conflict_a);
2941 	      k = (ira_class_hard_reg_index
2942 		   [ALLOCNO_CLASS (conflict_a)][conflict_hregno]);
2943 	      ira_assert (k >= 0);
2944 	      if ((allocno_costs = ALLOCNO_HARD_REG_COSTS (conflict_a))
2945 		  != NULL)
2946 		spill_cost -= allocno_costs[k];
2947 	      else
2948 		spill_cost -= ALLOCNO_UPDATED_CLASS_COST (conflict_a);
2949 	      spill_cost
2950 		+= allocno_copy_cost_saving (conflict_a, conflict_hregno);
2951 	      conflict_nregs = hard_regno_nregs (conflict_hregno,
2952 						 ALLOCNO_MODE (conflict_a));
2953 	      for (r = conflict_hregno;
2954 		   r >= 0 && (int) end_hard_regno (mode, r) > conflict_hregno;
2955 		   r--)
2956 		if (check_hard_reg_p (a, r,
2957 				      conflicting_regs, profitable_hard_regs))
2958 		  costs[r] += spill_cost;
2959 	      for (r = conflict_hregno + 1;
2960 		   r < conflict_hregno + conflict_nregs;
2961 		   r++)
2962 		if (check_hard_reg_p (a, r,
2963 				      conflicting_regs, profitable_hard_regs))
2964 		  costs[r] += spill_cost;
2965 	    }
2966 	}
2967       min_cost = INT_MAX;
2968       best = -1;
2969       /* Now we choose hard register for A which results in highest
2970 	 allocation cost improvement.  */
2971       for (j = 0; j < class_size; j++)
2972 	{
2973 	  hregno = ira_class_hard_regs[aclass][j];
2974 	  if (check_hard_reg_p (a, hregno,
2975 				conflicting_regs, profitable_hard_regs)
2976 	      && min_cost > costs[hregno])
2977 	    {
2978 	      best = hregno;
2979 	      min_cost = costs[hregno];
2980 	    }
2981 	}
2982       if (min_cost >= 0)
2983 	/* We are in a situation when assigning any hard register to A
2984 	   by spilling some conflicting allocnos does not improve the
2985 	   allocation cost.  */
2986 	continue;
2987       nregs = hard_regno_nregs (best, mode);
2988       /* Now spill conflicting allocnos which contain a hard register
2989 	 of A when we assign the best chosen hard register to it.  */
2990       for (word = 0; word < nwords; word++)
2991 	{
2992 	  ira_object_t conflict_obj;
2993 	  ira_object_t obj = ALLOCNO_OBJECT (a, word);
2994 	  ira_object_conflict_iterator oci;
2995 
2996 	  FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2997 	    {
2998 	      ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2999 
3000 	      if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
3001 		continue;
3002 	      conflict_nregs = hard_regno_nregs (conflict_hregno,
3003 						 ALLOCNO_MODE (conflict_a));
3004 	      if (best + nregs <= conflict_hregno
3005 		  || conflict_hregno + conflict_nregs <= best)
3006 		/* No intersection.  */
3007 		continue;
3008 	      ALLOCNO_HARD_REGNO (conflict_a) = -1;
3009 	      sorted_allocnos[n++] = conflict_a;
3010 	      if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3011 		fprintf (ira_dump_file, "Spilling a%dr%d for a%dr%d\n",
3012 			 ALLOCNO_NUM (conflict_a), ALLOCNO_REGNO (conflict_a),
3013 			 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
3014 	    }
3015 	}
3016       /* Assign the best chosen hard register to A.  */
3017       ALLOCNO_HARD_REGNO (a) = best;
3018       if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3019 	fprintf (ira_dump_file, "Assigning %d to a%dr%d\n",
3020 		 best, ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
3021     }
3022   if (n == 0)
3023     return;
3024   /* We spilled some allocnos to assign their hard registers to other
3025      allocnos.  The spilled allocnos are now in array
3026      'sorted_allocnos'.  There is still a possibility that some of the
3027      spilled allocnos can get hard registers.  So let us try assign
3028      them hard registers again (just a reminder -- function
3029      'assign_hard_reg' assigns hard registers only if it is possible
3030      and profitable).  We process the spilled allocnos with biggest
3031      benefit to get hard register first -- see function
3032      'allocno_cost_compare_func'.  */
3033   qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
3034 	 allocno_cost_compare_func);
3035   for (j = 0; j < n; j++)
3036     {
3037       a = sorted_allocnos[j];
3038       ALLOCNO_ASSIGNED_P (a) = false;
3039       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3040 	{
3041 	  fprintf (ira_dump_file, "      ");
3042 	  ira_print_expanded_allocno (a);
3043 	  fprintf (ira_dump_file, "  -- ");
3044 	}
3045       if (assign_hard_reg (a, false))
3046 	{
3047 	  if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3048 	    fprintf (ira_dump_file, "assign hard reg %d\n",
3049 		     ALLOCNO_HARD_REGNO (a));
3050 	}
3051       else
3052 	{
3053 	  if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3054 	    fprintf (ira_dump_file, "assign memory\n");
3055 	}
3056     }
3057 }
3058 
3059 /* Sort allocnos according to their priorities.  */
3060 static int
allocno_priority_compare_func(const void * v1p,const void * v2p)3061 allocno_priority_compare_func (const void *v1p, const void *v2p)
3062 {
3063   ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
3064   ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
3065   int pri1, pri2, diff;
3066 
3067   /* Assign hard reg to static chain pointer pseudo first when
3068      non-local goto is used.  */
3069   if ((diff = (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2))
3070 	       - non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))) != 0)
3071     return diff;
3072   pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
3073   pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
3074   if (pri2 != pri1)
3075     return SORTGT (pri2, pri1);
3076 
3077   /* If regs are equally good, sort by allocnos, so that the results of
3078      qsort leave nothing to chance.  */
3079   return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
3080 }
3081 
3082 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
3083    taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP.  */
3084 static void
color_allocnos(void)3085 color_allocnos (void)
3086 {
3087   unsigned int i, n;
3088   bitmap_iterator bi;
3089   ira_allocno_t a;
3090 
3091   setup_profitable_hard_regs ();
3092   EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3093     {
3094       allocno_color_data_t data;
3095       ira_pref_t pref, next_pref;
3096 
3097       a = ira_allocnos[i];
3098       data = ALLOCNO_COLOR_DATA (a);
3099       data->conflict_allocno_hard_prefs = 0;
3100       for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
3101 	{
3102 	  next_pref = pref->next_pref;
3103 	  if (! ira_hard_reg_in_set_p (pref->hard_regno,
3104 				       ALLOCNO_MODE (a),
3105 				       data->profitable_hard_regs))
3106 	    ira_remove_pref (pref);
3107 	}
3108     }
3109 
3110   if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
3111     {
3112       n = 0;
3113       EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3114 	{
3115 	  a = ira_allocnos[i];
3116 	  if (ALLOCNO_CLASS (a) == NO_REGS)
3117 	    {
3118 	      ALLOCNO_HARD_REGNO (a) = -1;
3119 	      ALLOCNO_ASSIGNED_P (a) = true;
3120 	      ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3121 	      ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3122 	      if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3123 		{
3124 		  fprintf (ira_dump_file, "      Spill");
3125 		  ira_print_expanded_allocno (a);
3126 		  fprintf (ira_dump_file, "\n");
3127 		}
3128 	      continue;
3129 	    }
3130 	  sorted_allocnos[n++] = a;
3131 	}
3132       if (n != 0)
3133 	{
3134 	  setup_allocno_priorities (sorted_allocnos, n);
3135 	  qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
3136 		 allocno_priority_compare_func);
3137 	  for (i = 0; i < n; i++)
3138 	    {
3139 	      a = sorted_allocnos[i];
3140 	      if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3141 		{
3142 		  fprintf (ira_dump_file, "      ");
3143 		  ira_print_expanded_allocno (a);
3144 		  fprintf (ira_dump_file, "  -- ");
3145 		}
3146 	      if (assign_hard_reg (a, false))
3147 		{
3148 		  if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3149 		    fprintf (ira_dump_file, "assign hard reg %d\n",
3150 			     ALLOCNO_HARD_REGNO (a));
3151 		}
3152 	      else
3153 		{
3154 		  if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3155 		    fprintf (ira_dump_file, "assign memory\n");
3156 		}
3157 	    }
3158 	}
3159     }
3160   else
3161     {
3162       form_allocno_hard_regs_nodes_forest ();
3163       if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3164 	print_hard_regs_forest (ira_dump_file);
3165       EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3166 	{
3167 	  a = ira_allocnos[i];
3168 	  if (ALLOCNO_CLASS (a) != NO_REGS && ! empty_profitable_hard_regs (a))
3169 	    {
3170 	      ALLOCNO_COLOR_DATA (a)->in_graph_p = true;
3171 	      update_costs_from_prefs (a);
3172 	      update_conflict_allocno_hard_prefs (a);
3173 	    }
3174 	  else
3175 	    {
3176 	      ALLOCNO_HARD_REGNO (a) = -1;
3177 	      ALLOCNO_ASSIGNED_P (a) = true;
3178 	      /* We don't need updated costs anymore.  */
3179 	      ira_free_allocno_updated_costs (a);
3180 	      if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3181 		{
3182 		  fprintf (ira_dump_file, "      Spill");
3183 		  ira_print_expanded_allocno (a);
3184 		  fprintf (ira_dump_file, "\n");
3185 		}
3186 	    }
3187 	}
3188       /* Put the allocnos into the corresponding buckets.  */
3189       colorable_allocno_bucket = NULL;
3190       uncolorable_allocno_bucket = NULL;
3191       EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3192 	{
3193 	  a = ira_allocnos[i];
3194 	  if (ALLOCNO_COLOR_DATA (a)->in_graph_p)
3195 	    put_allocno_into_bucket (a);
3196 	}
3197       push_allocnos_to_stack ();
3198       pop_allocnos_from_stack ();
3199       finish_allocno_hard_regs_nodes_forest ();
3200     }
3201   improve_allocation ();
3202 }
3203 
3204 
3205 
3206 /* Output information about the loop given by its LOOP_TREE_NODE.  */
3207 static void
print_loop_title(ira_loop_tree_node_t loop_tree_node)3208 print_loop_title (ira_loop_tree_node_t loop_tree_node)
3209 {
3210   unsigned int j;
3211   bitmap_iterator bi;
3212   ira_loop_tree_node_t subloop_node, dest_loop_node;
3213   edge e;
3214   edge_iterator ei;
3215 
3216   if (loop_tree_node->parent == NULL)
3217     fprintf (ira_dump_file,
3218 	     "\n  Loop 0 (parent -1, header bb%d, depth 0)\n    bbs:",
3219 	     NUM_FIXED_BLOCKS);
3220   else
3221     {
3222       ira_assert (current_loops != NULL && loop_tree_node->loop != NULL);
3223       fprintf (ira_dump_file,
3224 	       "\n  Loop %d (parent %d, header bb%d, depth %d)\n    bbs:",
3225 	       loop_tree_node->loop_num, loop_tree_node->parent->loop_num,
3226 	       loop_tree_node->loop->header->index,
3227 	       loop_depth (loop_tree_node->loop));
3228     }
3229   for (subloop_node = loop_tree_node->children;
3230        subloop_node != NULL;
3231        subloop_node = subloop_node->next)
3232     if (subloop_node->bb != NULL)
3233       {
3234 	fprintf (ira_dump_file, " %d", subloop_node->bb->index);
3235 	FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
3236 	  if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3237 	      && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
3238 		  != loop_tree_node))
3239 	    fprintf (ira_dump_file, "(->%d:l%d)",
3240 		     e->dest->index, dest_loop_node->loop_num);
3241       }
3242   fprintf (ira_dump_file, "\n    all:");
3243   EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3244     fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
3245   fprintf (ira_dump_file, "\n    modified regnos:");
3246   EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
3247     fprintf (ira_dump_file, " %d", j);
3248   fprintf (ira_dump_file, "\n    border:");
3249   EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
3250     fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
3251   fprintf (ira_dump_file, "\n    Pressure:");
3252   for (j = 0; (int) j < ira_pressure_classes_num; j++)
3253     {
3254       enum reg_class pclass;
3255 
3256       pclass = ira_pressure_classes[j];
3257       if (loop_tree_node->reg_pressure[pclass] == 0)
3258 	continue;
3259       fprintf (ira_dump_file, " %s=%d", reg_class_names[pclass],
3260 	       loop_tree_node->reg_pressure[pclass]);
3261     }
3262   fprintf (ira_dump_file, "\n");
3263 }
3264 
3265 /* Color the allocnos inside loop (in the extreme case it can be all
3266    of the function) given the corresponding LOOP_TREE_NODE.  The
3267    function is called for each loop during top-down traverse of the
3268    loop tree.  */
3269 static void
color_pass(ira_loop_tree_node_t loop_tree_node)3270 color_pass (ira_loop_tree_node_t loop_tree_node)
3271 {
3272   int regno, hard_regno, index = -1, n;
3273   int cost, exit_freq, enter_freq;
3274   unsigned int j;
3275   bitmap_iterator bi;
3276   machine_mode mode;
3277   enum reg_class rclass, aclass, pclass;
3278   ira_allocno_t a, subloop_allocno;
3279   ira_loop_tree_node_t subloop_node;
3280 
3281   ira_assert (loop_tree_node->bb == NULL);
3282   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3283     print_loop_title (loop_tree_node);
3284 
3285   bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
3286   bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
3287   n = 0;
3288   EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3289     {
3290       a = ira_allocnos[j];
3291       n++;
3292       if (! ALLOCNO_ASSIGNED_P (a))
3293 	continue;
3294       bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
3295     }
3296   allocno_color_data
3297     = (allocno_color_data_t) ira_allocate (sizeof (struct allocno_color_data)
3298 					   * n);
3299   memset (allocno_color_data, 0, sizeof (struct allocno_color_data) * n);
3300   curr_allocno_process = 0;
3301   n = 0;
3302   EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3303     {
3304       a = ira_allocnos[j];
3305       ALLOCNO_ADD_DATA (a) = allocno_color_data + n;
3306       n++;
3307     }
3308   init_allocno_threads ();
3309   /* Color all mentioned allocnos including transparent ones.  */
3310   color_allocnos ();
3311   /* Process caps.  They are processed just once.  */
3312   if (flag_ira_region == IRA_REGION_MIXED
3313       || flag_ira_region == IRA_REGION_ALL)
3314     EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3315       {
3316 	a = ira_allocnos[j];
3317 	if (ALLOCNO_CAP_MEMBER (a) == NULL)
3318 	  continue;
3319 	/* Remove from processing in the next loop.  */
3320 	bitmap_clear_bit (consideration_allocno_bitmap, j);
3321 	rclass = ALLOCNO_CLASS (a);
3322 	pclass = ira_pressure_class_translate[rclass];
3323 	if (flag_ira_region == IRA_REGION_MIXED
3324 	    && (loop_tree_node->reg_pressure[pclass]
3325 		<= ira_class_hard_regs_num[pclass]))
3326 	  {
3327 	    mode = ALLOCNO_MODE (a);
3328 	    hard_regno = ALLOCNO_HARD_REGNO (a);
3329 	    if (hard_regno >= 0)
3330 	      {
3331 		index = ira_class_hard_reg_index[rclass][hard_regno];
3332 		ira_assert (index >= 0);
3333 	      }
3334 	    regno = ALLOCNO_REGNO (a);
3335 	    subloop_allocno = ALLOCNO_CAP_MEMBER (a);
3336 	    subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
3337 	    ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
3338 	    ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3339 	    ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3340 	    if (hard_regno >= 0)
3341 	      update_costs_from_copies (subloop_allocno, true, true);
3342 	    /* We don't need updated costs anymore.  */
3343 	    ira_free_allocno_updated_costs (subloop_allocno);
3344 	  }
3345       }
3346   /* Update costs of the corresponding allocnos (not caps) in the
3347      subloops.  */
3348   for (subloop_node = loop_tree_node->subloops;
3349        subloop_node != NULL;
3350        subloop_node = subloop_node->subloop_next)
3351     {
3352       ira_assert (subloop_node->bb == NULL);
3353       EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3354         {
3355 	  a = ira_allocnos[j];
3356 	  ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3357 	  mode = ALLOCNO_MODE (a);
3358 	  rclass = ALLOCNO_CLASS (a);
3359 	  pclass = ira_pressure_class_translate[rclass];
3360 	  hard_regno = ALLOCNO_HARD_REGNO (a);
3361 	  /* Use hard register class here.  ??? */
3362 	  if (hard_regno >= 0)
3363 	    {
3364 	      index = ira_class_hard_reg_index[rclass][hard_regno];
3365 	      ira_assert (index >= 0);
3366 	    }
3367 	  regno = ALLOCNO_REGNO (a);
3368 	  /* ??? conflict costs */
3369 	  subloop_allocno = subloop_node->regno_allocno_map[regno];
3370 	  if (subloop_allocno == NULL
3371 	      || ALLOCNO_CAP (subloop_allocno) != NULL)
3372 	    continue;
3373 	  ira_assert (ALLOCNO_CLASS (subloop_allocno) == rclass);
3374 	  ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
3375 				    ALLOCNO_NUM (subloop_allocno)));
3376 	  if ((flag_ira_region == IRA_REGION_MIXED
3377 	       && (loop_tree_node->reg_pressure[pclass]
3378 		   <= ira_class_hard_regs_num[pclass]))
3379 	      || (pic_offset_table_rtx != NULL
3380 		  && regno == (int) REGNO (pic_offset_table_rtx))
3381 	      /* Avoid overlapped multi-registers. Moves between them
3382 		 might result in wrong code generation.  */
3383 	      || (hard_regno >= 0
3384 		  && ira_reg_class_max_nregs[pclass][mode] > 1))
3385 	    {
3386 	      if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
3387 		{
3388 		  ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3389 		  ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3390 		  if (hard_regno >= 0)
3391 		    update_costs_from_copies (subloop_allocno, true, true);
3392 		  /* We don't need updated costs anymore.  */
3393 		  ira_free_allocno_updated_costs (subloop_allocno);
3394 		}
3395 	      continue;
3396 	    }
3397 	  exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
3398 	  enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
3399 	  ira_assert (regno < ira_reg_equiv_len);
3400 	  if (ira_equiv_no_lvalue_p (regno))
3401 	    {
3402 	      if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
3403 		{
3404 		  ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3405 		  ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3406 		  if (hard_regno >= 0)
3407 		    update_costs_from_copies (subloop_allocno, true, true);
3408 		  /* We don't need updated costs anymore.  */
3409 		  ira_free_allocno_updated_costs (subloop_allocno);
3410 		}
3411 	    }
3412 	  else if (hard_regno < 0)
3413 	    {
3414 	      ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3415 		-= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
3416 		    + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
3417 	    }
3418 	  else
3419 	    {
3420 	      aclass = ALLOCNO_CLASS (subloop_allocno);
3421 	      ira_init_register_move_cost_if_necessary (mode);
3422 	      cost = (ira_register_move_cost[mode][rclass][rclass]
3423 		      * (exit_freq + enter_freq));
3424 	      ira_allocate_and_set_or_copy_costs
3425 		(&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), aclass,
3426 		 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno),
3427 		 ALLOCNO_HARD_REG_COSTS (subloop_allocno));
3428 	      ira_allocate_and_set_or_copy_costs
3429 		(&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
3430 		 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
3431 	      ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
3432 	      ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
3433 		-= cost;
3434 	      if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3435 		  > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
3436 		ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3437 		  = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
3438 	      ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3439 		+= (ira_memory_move_cost[mode][rclass][0] * enter_freq
3440 		    + ira_memory_move_cost[mode][rclass][1] * exit_freq);
3441 	    }
3442 	}
3443     }
3444   ira_free (allocno_color_data);
3445   EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3446     {
3447       a = ira_allocnos[j];
3448       ALLOCNO_ADD_DATA (a) = NULL;
3449     }
3450 }
3451 
3452 /* Initialize the common data for coloring and calls functions to do
3453    Chaitin-Briggs and regional coloring.  */
3454 static void
do_coloring(void)3455 do_coloring (void)
3456 {
3457   coloring_allocno_bitmap = ira_allocate_bitmap ();
3458   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3459     fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
3460 
3461   ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
3462 
3463   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3464     ira_print_disposition (ira_dump_file);
3465 
3466   ira_free_bitmap (coloring_allocno_bitmap);
3467 }
3468 
3469 
3470 
3471 /* Move spill/restore code, which are to be generated in ira-emit.c,
3472    to less frequent points (if it is profitable) by reassigning some
3473    allocnos (in loop with subloops containing in another loop) to
3474    memory which results in longer live-range where the corresponding
3475    pseudo-registers will be in memory.  */
3476 static void
move_spill_restore(void)3477 move_spill_restore (void)
3478 {
3479   int cost, regno, hard_regno, hard_regno2, index;
3480   bool changed_p;
3481   int enter_freq, exit_freq;
3482   machine_mode mode;
3483   enum reg_class rclass;
3484   ira_allocno_t a, parent_allocno, subloop_allocno;
3485   ira_loop_tree_node_t parent, loop_node, subloop_node;
3486   ira_allocno_iterator ai;
3487 
3488   for (;;)
3489     {
3490       changed_p = false;
3491       if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3492 	fprintf (ira_dump_file, "New iteration of spill/restore move\n");
3493       FOR_EACH_ALLOCNO (a, ai)
3494 	{
3495 	  regno = ALLOCNO_REGNO (a);
3496 	  loop_node = ALLOCNO_LOOP_TREE_NODE (a);
3497 	  if (ALLOCNO_CAP_MEMBER (a) != NULL
3498 	      || ALLOCNO_CAP (a) != NULL
3499 	      || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
3500 	      || loop_node->children == NULL
3501 	      /* don't do the optimization because it can create
3502 		 copies and the reload pass can spill the allocno set
3503 		 by copy although the allocno will not get memory
3504 		 slot.  */
3505 	      || ira_equiv_no_lvalue_p (regno)
3506 	      || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a))
3507 	      /* Do not spill static chain pointer pseudo when
3508 		 non-local goto is used.  */
3509 	      || non_spilled_static_chain_regno_p (regno))
3510 	    continue;
3511 	  mode = ALLOCNO_MODE (a);
3512 	  rclass = ALLOCNO_CLASS (a);
3513 	  index = ira_class_hard_reg_index[rclass][hard_regno];
3514 	  ira_assert (index >= 0);
3515 	  cost = (ALLOCNO_MEMORY_COST (a)
3516 		  - (ALLOCNO_HARD_REG_COSTS (a) == NULL
3517 		     ? ALLOCNO_CLASS_COST (a)
3518 		     : ALLOCNO_HARD_REG_COSTS (a)[index]));
3519 	  ira_init_register_move_cost_if_necessary (mode);
3520 	  for (subloop_node = loop_node->subloops;
3521 	       subloop_node != NULL;
3522 	       subloop_node = subloop_node->subloop_next)
3523 	    {
3524 	      ira_assert (subloop_node->bb == NULL);
3525 	      subloop_allocno = subloop_node->regno_allocno_map[regno];
3526 	      if (subloop_allocno == NULL)
3527 		continue;
3528 	      ira_assert (rclass == ALLOCNO_CLASS (subloop_allocno));
3529 	      /* We have accumulated cost.  To get the real cost of
3530 		 allocno usage in the loop we should subtract costs of
3531 		 the subloop allocnos.  */
3532 	      cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
3533 		       - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
3534 			  ? ALLOCNO_CLASS_COST (subloop_allocno)
3535 			  : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
3536 	      exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
3537 	      enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
3538 	      if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
3539 		cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
3540 			 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3541 	      else
3542 		{
3543 		  cost
3544 		    += (ira_memory_move_cost[mode][rclass][0] * exit_freq
3545 			+ ira_memory_move_cost[mode][rclass][1] * enter_freq);
3546 		  if (hard_regno2 != hard_regno)
3547 		    cost -= (ira_register_move_cost[mode][rclass][rclass]
3548 			     * (exit_freq + enter_freq));
3549 		}
3550 	    }
3551 	  if ((parent = loop_node->parent) != NULL
3552 	      && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
3553 	    {
3554 	      ira_assert (rclass == ALLOCNO_CLASS (parent_allocno));
3555 	      exit_freq	= ira_loop_edge_freq (loop_node, regno, true);
3556 	      enter_freq = ira_loop_edge_freq (loop_node, regno, false);
3557 	      if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
3558 		cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
3559 			 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3560 	      else
3561 		{
3562 		  cost
3563 		    += (ira_memory_move_cost[mode][rclass][1] * exit_freq
3564 			+ ira_memory_move_cost[mode][rclass][0] * enter_freq);
3565 		  if (hard_regno2 != hard_regno)
3566 		    cost -= (ira_register_move_cost[mode][rclass][rclass]
3567 			     * (exit_freq + enter_freq));
3568 		}
3569 	    }
3570 	  if (cost < 0)
3571 	    {
3572 	      ALLOCNO_HARD_REGNO (a) = -1;
3573 	      if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3574 		{
3575 		  fprintf
3576 		    (ira_dump_file,
3577 		     "      Moving spill/restore for a%dr%d up from loop %d",
3578 		     ALLOCNO_NUM (a), regno, loop_node->loop_num);
3579 		  fprintf (ira_dump_file, " - profit %d\n", -cost);
3580 		}
3581 	      changed_p = true;
3582 	    }
3583 	}
3584       if (! changed_p)
3585 	break;
3586     }
3587 }
3588 
3589 
3590 
3591 /* Update current hard reg costs and current conflict hard reg costs
3592    for allocno A.  It is done by processing its copies containing
3593    other allocnos already assigned.  */
3594 static void
update_curr_costs(ira_allocno_t a)3595 update_curr_costs (ira_allocno_t a)
3596 {
3597   int i, hard_regno, cost;
3598   machine_mode mode;
3599   enum reg_class aclass, rclass;
3600   ira_allocno_t another_a;
3601   ira_copy_t cp, next_cp;
3602 
3603   ira_free_allocno_updated_costs (a);
3604   ira_assert (! ALLOCNO_ASSIGNED_P (a));
3605   aclass = ALLOCNO_CLASS (a);
3606   if (aclass == NO_REGS)
3607     return;
3608   mode = ALLOCNO_MODE (a);
3609   ira_init_register_move_cost_if_necessary (mode);
3610   for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3611     {
3612       if (cp->first == a)
3613 	{
3614 	  next_cp = cp->next_first_allocno_copy;
3615 	  another_a = cp->second;
3616 	}
3617       else if (cp->second == a)
3618 	{
3619 	  next_cp = cp->next_second_allocno_copy;
3620 	  another_a = cp->first;
3621 	}
3622       else
3623 	gcc_unreachable ();
3624       if (! ira_reg_classes_intersect_p[aclass][ALLOCNO_CLASS (another_a)]
3625 	  || ! ALLOCNO_ASSIGNED_P (another_a)
3626 	  || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
3627 	continue;
3628       rclass = REGNO_REG_CLASS (hard_regno);
3629       i = ira_class_hard_reg_index[aclass][hard_regno];
3630       if (i < 0)
3631 	continue;
3632       cost = (cp->first == a
3633 	      ? ira_register_move_cost[mode][rclass][aclass]
3634 	      : ira_register_move_cost[mode][aclass][rclass]);
3635       ira_allocate_and_set_or_copy_costs
3636 	(&ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a),
3637 	 ALLOCNO_HARD_REG_COSTS (a));
3638       ira_allocate_and_set_or_copy_costs
3639 	(&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
3640 	 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
3641       ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3642       ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3643     }
3644 }
3645 
3646 /* Try to assign hard registers to the unassigned allocnos and
3647    allocnos conflicting with them or conflicting with allocnos whose
3648    regno >= START_REGNO.  The function is called after ira_flattening,
3649    so more allocnos (including ones created in ira-emit.c) will have a
3650    chance to get a hard register.  We use simple assignment algorithm
3651    based on priorities.  */
3652 void
ira_reassign_conflict_allocnos(int start_regno)3653 ira_reassign_conflict_allocnos (int start_regno)
3654 {
3655   int i, allocnos_to_color_num;
3656   ira_allocno_t a;
3657   enum reg_class aclass;
3658   bitmap allocnos_to_color;
3659   ira_allocno_iterator ai;
3660 
3661   allocnos_to_color = ira_allocate_bitmap ();
3662   allocnos_to_color_num = 0;
3663   FOR_EACH_ALLOCNO (a, ai)
3664     {
3665       int n = ALLOCNO_NUM_OBJECTS (a);
3666 
3667       if (! ALLOCNO_ASSIGNED_P (a)
3668 	  && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
3669 	{
3670 	  if (ALLOCNO_CLASS (a) != NO_REGS)
3671 	    sorted_allocnos[allocnos_to_color_num++] = a;
3672 	  else
3673 	    {
3674 	      ALLOCNO_ASSIGNED_P (a) = true;
3675 	      ALLOCNO_HARD_REGNO (a) = -1;
3676 	      ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3677 	      ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3678 	    }
3679 	  bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
3680 	}
3681       if (ALLOCNO_REGNO (a) < start_regno
3682 	  || (aclass = ALLOCNO_CLASS (a)) == NO_REGS)
3683 	continue;
3684       for (i = 0; i < n; i++)
3685 	{
3686 	  ira_object_t obj = ALLOCNO_OBJECT (a, i);
3687 	  ira_object_t conflict_obj;
3688 	  ira_object_conflict_iterator oci;
3689 
3690 	  FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3691 	    {
3692 	      ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3693 
3694 	      ira_assert (ira_reg_classes_intersect_p
3695 			  [aclass][ALLOCNO_CLASS (conflict_a)]);
3696 	      if (!bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
3697 		continue;
3698 	      sorted_allocnos[allocnos_to_color_num++] = conflict_a;
3699 	    }
3700 	}
3701     }
3702   ira_free_bitmap (allocnos_to_color);
3703   if (allocnos_to_color_num > 1)
3704     {
3705       setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
3706       qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
3707 	     allocno_priority_compare_func);
3708     }
3709   for (i = 0; i < allocnos_to_color_num; i++)
3710     {
3711       a = sorted_allocnos[i];
3712       ALLOCNO_ASSIGNED_P (a) = false;
3713       update_curr_costs (a);
3714     }
3715   for (i = 0; i < allocnos_to_color_num; i++)
3716     {
3717       a = sorted_allocnos[i];
3718       if (assign_hard_reg (a, true))
3719 	{
3720 	  if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3721 	    fprintf
3722 	      (ira_dump_file,
3723 	       "      Secondary allocation: assign hard reg %d to reg %d\n",
3724 	       ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
3725 	}
3726     }
3727 }
3728 
3729 
3730 
3731 /* This page contains functions used to find conflicts using allocno
3732    live ranges.  */
3733 
3734 #ifdef ENABLE_IRA_CHECKING
3735 
3736 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
3737    intersect.  This should be used when there is only one region.
3738    Currently this is used during reload.  */
3739 static bool
conflict_by_live_ranges_p(int regno1,int regno2)3740 conflict_by_live_ranges_p (int regno1, int regno2)
3741 {
3742   ira_allocno_t a1, a2;
3743 
3744   ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
3745 	      && regno2 >= FIRST_PSEUDO_REGISTER);
3746   /* Reg info calculated by dataflow infrastructure can be different
3747      from one calculated by regclass.  */
3748   if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
3749       || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
3750     return false;
3751   return allocnos_conflict_by_live_ranges_p (a1, a2);
3752 }
3753 
3754 #endif
3755 
3756 
3757 
3758 /* This page contains code to coalesce memory stack slots used by
3759    spilled allocnos.  This results in smaller stack frame, better data
3760    locality, and in smaller code for some architectures like
3761    x86/x86_64 where insn size depends on address displacement value.
3762    On the other hand, it can worsen insn scheduling after the RA but
3763    in practice it is less important than smaller stack frames.  */
3764 
3765 /* TRUE if we coalesced some allocnos.  In other words, if we got
3766    loops formed by members first_coalesced_allocno and
3767    next_coalesced_allocno containing more one allocno.  */
3768 static bool allocno_coalesced_p;
3769 
3770 /* Bitmap used to prevent a repeated allocno processing because of
3771    coalescing.  */
3772 static bitmap processed_coalesced_allocno_bitmap;
3773 
3774 /* See below.  */
3775 typedef struct coalesce_data *coalesce_data_t;
3776 
3777 /* To decrease footprint of ira_allocno structure we store all data
3778    needed only for coalescing in the following structure.  */
3779 struct coalesce_data
3780 {
3781   /* Coalesced allocnos form a cyclic list.  One allocno given by
3782      FIRST represents all coalesced allocnos.  The
3783      list is chained by NEXT.  */
3784   ira_allocno_t first;
3785   ira_allocno_t next;
3786   int temp;
3787 };
3788 
3789 /* Container for storing allocno data concerning coalescing.  */
3790 static coalesce_data_t allocno_coalesce_data;
3791 
3792 /* Macro to access the data concerning coalescing.  */
3793 #define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
3794 
3795 /* Merge two sets of coalesced allocnos given correspondingly by
3796    allocnos A1 and A2 (more accurately merging A2 set into A1
3797    set).  */
3798 static void
merge_allocnos(ira_allocno_t a1,ira_allocno_t a2)3799 merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
3800 {
3801   ira_allocno_t a, first, last, next;
3802 
3803   first = ALLOCNO_COALESCE_DATA (a1)->first;
3804   a = ALLOCNO_COALESCE_DATA (a2)->first;
3805   if (first == a)
3806     return;
3807   for (last = a2, a = ALLOCNO_COALESCE_DATA (a2)->next;;
3808        a = ALLOCNO_COALESCE_DATA (a)->next)
3809     {
3810       ALLOCNO_COALESCE_DATA (a)->first = first;
3811       if (a == a2)
3812 	break;
3813       last = a;
3814     }
3815   next = allocno_coalesce_data[ALLOCNO_NUM (first)].next;
3816   allocno_coalesce_data[ALLOCNO_NUM (first)].next = a2;
3817   allocno_coalesce_data[ALLOCNO_NUM (last)].next = next;
3818 }
3819 
3820 /* Return TRUE if there are conflicting allocnos from two sets of
3821    coalesced allocnos given correspondingly by allocnos A1 and A2.  We
3822    use live ranges to find conflicts because conflicts are represented
3823    only for allocnos of the same allocno class and during the reload
3824    pass we coalesce allocnos for sharing stack memory slots.  */
3825 static bool
coalesced_allocno_conflict_p(ira_allocno_t a1,ira_allocno_t a2)3826 coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
3827 {
3828   ira_allocno_t a, conflict_a;
3829 
3830   if (allocno_coalesced_p)
3831     {
3832       bitmap_clear (processed_coalesced_allocno_bitmap);
3833       for (a = ALLOCNO_COALESCE_DATA (a1)->next;;
3834 	   a = ALLOCNO_COALESCE_DATA (a)->next)
3835 	{
3836 	  bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
3837 	  if (a == a1)
3838 	    break;
3839 	}
3840     }
3841   for (a = ALLOCNO_COALESCE_DATA (a2)->next;;
3842        a = ALLOCNO_COALESCE_DATA (a)->next)
3843     {
3844       for (conflict_a = ALLOCNO_COALESCE_DATA (a1)->next;;
3845 	   conflict_a = ALLOCNO_COALESCE_DATA (conflict_a)->next)
3846 	{
3847 	  if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
3848 	    return true;
3849 	  if (conflict_a == a1)
3850 	    break;
3851 	}
3852       if (a == a2)
3853 	break;
3854     }
3855   return false;
3856 }
3857 
3858 /* The major function for aggressive allocno coalescing.  We coalesce
3859    only spilled allocnos.  If some allocnos have been coalesced, we
3860    set up flag allocno_coalesced_p.  */
3861 static void
coalesce_allocnos(void)3862 coalesce_allocnos (void)
3863 {
3864   ira_allocno_t a;
3865   ira_copy_t cp, next_cp;
3866   unsigned int j;
3867   int i, n, cp_num, regno;
3868   bitmap_iterator bi;
3869 
3870   cp_num = 0;
3871   /* Collect copies.  */
3872   EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
3873     {
3874       a = ira_allocnos[j];
3875       regno = ALLOCNO_REGNO (a);
3876       if (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
3877 	  || ira_equiv_no_lvalue_p (regno))
3878 	continue;
3879       for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3880 	{
3881 	  if (cp->first == a)
3882 	    {
3883 	      next_cp = cp->next_first_allocno_copy;
3884 	      regno = ALLOCNO_REGNO (cp->second);
3885 	      /* For priority coloring we coalesce allocnos only with
3886 		 the same allocno class not with intersected allocno
3887 		 classes as it were possible.  It is done for
3888 		 simplicity.  */
3889 	      if ((cp->insn != NULL || cp->constraint_p)
3890 		  && ALLOCNO_ASSIGNED_P (cp->second)
3891 		  && ALLOCNO_HARD_REGNO (cp->second) < 0
3892 		  && ! ira_equiv_no_lvalue_p (regno))
3893 		sorted_copies[cp_num++] = cp;
3894 	    }
3895 	  else if (cp->second == a)
3896 	    next_cp = cp->next_second_allocno_copy;
3897 	  else
3898 	    gcc_unreachable ();
3899 	}
3900     }
3901   qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
3902   /* Coalesced copies, most frequently executed first.  */
3903   for (; cp_num != 0;)
3904     {
3905       for (i = 0; i < cp_num; i++)
3906 	{
3907 	  cp = sorted_copies[i];
3908 	  if (! coalesced_allocno_conflict_p (cp->first, cp->second))
3909 	    {
3910 	      allocno_coalesced_p = true;
3911 	      if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3912 		fprintf
3913 		  (ira_dump_file,
3914 		   "      Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
3915 		   cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
3916 		   ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
3917 		   cp->freq);
3918 	      merge_allocnos (cp->first, cp->second);
3919 	      i++;
3920 	      break;
3921 	    }
3922 	}
3923       /* Collect the rest of copies.  */
3924       for (n = 0; i < cp_num; i++)
3925 	{
3926 	  cp = sorted_copies[i];
3927 	  if (allocno_coalesce_data[ALLOCNO_NUM (cp->first)].first
3928 	      != allocno_coalesce_data[ALLOCNO_NUM (cp->second)].first)
3929 	    sorted_copies[n++] = cp;
3930 	}
3931       cp_num = n;
3932     }
3933 }
3934 
3935 /* Usage cost and order number of coalesced allocno set to which
3936    given pseudo register belongs to.  */
3937 static int *regno_coalesced_allocno_cost;
3938 static int *regno_coalesced_allocno_num;
3939 
3940 /* Sort pseudos according frequencies of coalesced allocno sets they
3941    belong to (putting most frequently ones first), and according to
3942    coalesced allocno set order numbers.  */
3943 static int
coalesced_pseudo_reg_freq_compare(const void * v1p,const void * v2p)3944 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
3945 {
3946   const int regno1 = *(const int *) v1p;
3947   const int regno2 = *(const int *) v2p;
3948   int diff;
3949 
3950   if ((diff = (regno_coalesced_allocno_cost[regno2]
3951 	       - regno_coalesced_allocno_cost[regno1])) != 0)
3952     return diff;
3953   if ((diff = (regno_coalesced_allocno_num[regno1]
3954 	       - regno_coalesced_allocno_num[regno2])) != 0)
3955     return diff;
3956   return regno1 - regno2;
3957 }
3958 
3959 /* Widest width in which each pseudo reg is referred to (via subreg).
3960    It is used for sorting pseudo registers.  */
3961 static machine_mode *regno_max_ref_mode;
3962 
3963 /* Sort pseudos according their slot numbers (putting ones with
3964   smaller numbers first, or last when the frame pointer is not
3965   needed).  */
3966 static int
coalesced_pseudo_reg_slot_compare(const void * v1p,const void * v2p)3967 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
3968 {
3969   const int regno1 = *(const int *) v1p;
3970   const int regno2 = *(const int *) v2p;
3971   ira_allocno_t a1 = ira_regno_allocno_map[regno1];
3972   ira_allocno_t a2 = ira_regno_allocno_map[regno2];
3973   int diff, slot_num1, slot_num2;
3974   machine_mode mode1, mode2;
3975 
3976   if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
3977     {
3978       if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3979 	return regno1 - regno2;
3980       return 1;
3981     }
3982   else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3983     return -1;
3984   slot_num1 = -ALLOCNO_HARD_REGNO (a1);
3985   slot_num2 = -ALLOCNO_HARD_REGNO (a2);
3986   if ((diff = slot_num1 - slot_num2) != 0)
3987     return (frame_pointer_needed
3988 	    || (!FRAME_GROWS_DOWNWARD) == STACK_GROWS_DOWNWARD ? diff : -diff);
3989   mode1 = wider_subreg_mode (PSEUDO_REGNO_MODE (regno1),
3990 			     regno_max_ref_mode[regno1]);
3991   mode2 = wider_subreg_mode (PSEUDO_REGNO_MODE (regno2),
3992 			     regno_max_ref_mode[regno2]);
3993   if ((diff = compare_sizes_for_sort (GET_MODE_SIZE (mode2),
3994 				      GET_MODE_SIZE (mode1))) != 0)
3995     return diff;
3996   return regno1 - regno2;
3997 }
3998 
3999 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
4000    for coalesced allocno sets containing allocnos with their regnos
4001    given in array PSEUDO_REGNOS of length N.  */
4002 static void
setup_coalesced_allocno_costs_and_nums(int * pseudo_regnos,int n)4003 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
4004 {
4005   int i, num, regno, cost;
4006   ira_allocno_t allocno, a;
4007 
4008   for (num = i = 0; i < n; i++)
4009     {
4010       regno = pseudo_regnos[i];
4011       allocno = ira_regno_allocno_map[regno];
4012       if (allocno == NULL)
4013 	{
4014 	  regno_coalesced_allocno_cost[regno] = 0;
4015 	  regno_coalesced_allocno_num[regno] = ++num;
4016 	  continue;
4017 	}
4018       if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
4019 	continue;
4020       num++;
4021       for (cost = 0, a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4022 	   a = ALLOCNO_COALESCE_DATA (a)->next)
4023 	{
4024 	  cost += ALLOCNO_FREQ (a);
4025 	  if (a == allocno)
4026 	    break;
4027 	}
4028       for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4029 	   a = ALLOCNO_COALESCE_DATA (a)->next)
4030 	{
4031 	  regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
4032 	  regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
4033 	  if (a == allocno)
4034 	    break;
4035 	}
4036     }
4037 }
4038 
4039 /* Collect spilled allocnos representing coalesced allocno sets (the
4040    first coalesced allocno).  The collected allocnos are returned
4041    through array SPILLED_COALESCED_ALLOCNOS.  The function returns the
4042    number of the collected allocnos.  The allocnos are given by their
4043    regnos in array PSEUDO_REGNOS of length N.  */
4044 static int
collect_spilled_coalesced_allocnos(int * pseudo_regnos,int n,ira_allocno_t * spilled_coalesced_allocnos)4045 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
4046 				    ira_allocno_t *spilled_coalesced_allocnos)
4047 {
4048   int i, num, regno;
4049   ira_allocno_t allocno;
4050 
4051   for (num = i = 0; i < n; i++)
4052     {
4053       regno = pseudo_regnos[i];
4054       allocno = ira_regno_allocno_map[regno];
4055       if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
4056 	  || ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
4057 	continue;
4058       spilled_coalesced_allocnos[num++] = allocno;
4059     }
4060   return num;
4061 }
4062 
4063 /* Array of live ranges of size IRA_ALLOCNOS_NUM.  Live range for
4064    given slot contains live ranges of coalesced allocnos assigned to
4065    given slot.  */
4066 static live_range_t *slot_coalesced_allocnos_live_ranges;
4067 
4068 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
4069    ranges intersected with live ranges of coalesced allocnos assigned
4070    to slot with number N.  */
4071 static bool
slot_coalesced_allocno_live_ranges_intersect_p(ira_allocno_t allocno,int n)4072 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
4073 {
4074   ira_allocno_t a;
4075 
4076   for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4077        a = ALLOCNO_COALESCE_DATA (a)->next)
4078     {
4079       int i;
4080       int nr = ALLOCNO_NUM_OBJECTS (a);
4081       gcc_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
4082       for (i = 0; i < nr; i++)
4083 	{
4084 	  ira_object_t obj = ALLOCNO_OBJECT (a, i);
4085 
4086 	  if (ira_live_ranges_intersect_p
4087 	      (slot_coalesced_allocnos_live_ranges[n],
4088 	       OBJECT_LIVE_RANGES (obj)))
4089 	    return true;
4090 	}
4091       if (a == allocno)
4092 	break;
4093     }
4094   return false;
4095 }
4096 
4097 /* Update live ranges of slot to which coalesced allocnos represented
4098    by ALLOCNO were assigned.  */
4099 static void
setup_slot_coalesced_allocno_live_ranges(ira_allocno_t allocno)4100 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
4101 {
4102   int i, n;
4103   ira_allocno_t a;
4104   live_range_t r;
4105 
4106   n = ALLOCNO_COALESCE_DATA (allocno)->temp;
4107   for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4108        a = ALLOCNO_COALESCE_DATA (a)->next)
4109     {
4110       int nr = ALLOCNO_NUM_OBJECTS (a);
4111       gcc_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
4112       for (i = 0; i < nr; i++)
4113 	{
4114 	  ira_object_t obj = ALLOCNO_OBJECT (a, i);
4115 
4116 	  r = ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj));
4117 	  slot_coalesced_allocnos_live_ranges[n]
4118 	    = ira_merge_live_ranges
4119 	      (slot_coalesced_allocnos_live_ranges[n], r);
4120 	}
4121       if (a == allocno)
4122 	break;
4123     }
4124 }
4125 
4126 /* We have coalesced allocnos involving in copies.  Coalesce allocnos
4127    further in order to share the same memory stack slot.  Allocnos
4128    representing sets of allocnos coalesced before the call are given
4129    in array SPILLED_COALESCED_ALLOCNOS of length NUM.  Return TRUE if
4130    some allocnos were coalesced in the function.  */
4131 static bool
coalesce_spill_slots(ira_allocno_t * spilled_coalesced_allocnos,int num)4132 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
4133 {
4134   int i, j, n, last_coalesced_allocno_num;
4135   ira_allocno_t allocno, a;
4136   bool merged_p = false;
4137   bitmap set_jump_crosses = regstat_get_setjmp_crosses ();
4138 
4139   slot_coalesced_allocnos_live_ranges
4140     = (live_range_t *) ira_allocate (sizeof (live_range_t) * ira_allocnos_num);
4141   memset (slot_coalesced_allocnos_live_ranges, 0,
4142 	  sizeof (live_range_t) * ira_allocnos_num);
4143   last_coalesced_allocno_num = 0;
4144   /* Coalesce non-conflicting spilled allocnos preferring most
4145      frequently used.  */
4146   for (i = 0; i < num; i++)
4147     {
4148       allocno = spilled_coalesced_allocnos[i];
4149       if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
4150 	  || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
4151 	  || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno)))
4152 	continue;
4153       for (j = 0; j < i; j++)
4154 	{
4155 	  a = spilled_coalesced_allocnos[j];
4156 	  n = ALLOCNO_COALESCE_DATA (a)->temp;
4157 	  if (ALLOCNO_COALESCE_DATA (a)->first == a
4158 	      && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
4159 	      && ! ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a))
4160 	      && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
4161 	    break;
4162 	}
4163       if (j >= i)
4164 	{
4165 	  /* No coalescing: set up number for coalesced allocnos
4166 	     represented by ALLOCNO.  */
4167 	  ALLOCNO_COALESCE_DATA (allocno)->temp = last_coalesced_allocno_num++;
4168 	  setup_slot_coalesced_allocno_live_ranges (allocno);
4169 	}
4170       else
4171 	{
4172 	  allocno_coalesced_p = true;
4173 	  merged_p = true;
4174 	  if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4175 	    fprintf (ira_dump_file,
4176 		     "      Coalescing spilled allocnos a%dr%d->a%dr%d\n",
4177 		     ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
4178 		     ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
4179 	  ALLOCNO_COALESCE_DATA (allocno)->temp
4180 	    = ALLOCNO_COALESCE_DATA (a)->temp;
4181 	  setup_slot_coalesced_allocno_live_ranges (allocno);
4182 	  merge_allocnos (a, allocno);
4183 	  ira_assert (ALLOCNO_COALESCE_DATA (a)->first == a);
4184 	}
4185     }
4186   for (i = 0; i < ira_allocnos_num; i++)
4187     ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges[i]);
4188   ira_free (slot_coalesced_allocnos_live_ranges);
4189   return merged_p;
4190 }
4191 
4192 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
4193    subsequent assigning stack slots to them in the reload pass.  To do
4194    this we coalesce spilled allocnos first to decrease the number of
4195    memory-memory move insns.  This function is called by the
4196    reload.  */
4197 void
ira_sort_regnos_for_alter_reg(int * pseudo_regnos,int n,machine_mode * reg_max_ref_mode)4198 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
4199 			       machine_mode *reg_max_ref_mode)
4200 {
4201   int max_regno = max_reg_num ();
4202   int i, regno, num, slot_num;
4203   ira_allocno_t allocno, a;
4204   ira_allocno_iterator ai;
4205   ira_allocno_t *spilled_coalesced_allocnos;
4206 
4207   ira_assert (! ira_use_lra_p);
4208 
4209   /* Set up allocnos can be coalesced.  */
4210   coloring_allocno_bitmap = ira_allocate_bitmap ();
4211   for (i = 0; i < n; i++)
4212     {
4213       regno = pseudo_regnos[i];
4214       allocno = ira_regno_allocno_map[regno];
4215       if (allocno != NULL)
4216 	bitmap_set_bit (coloring_allocno_bitmap, ALLOCNO_NUM (allocno));
4217     }
4218   allocno_coalesced_p = false;
4219   processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
4220   allocno_coalesce_data
4221     = (coalesce_data_t) ira_allocate (sizeof (struct coalesce_data)
4222 				      * ira_allocnos_num);
4223   /* Initialize coalesce data for allocnos.  */
4224   FOR_EACH_ALLOCNO (a, ai)
4225     {
4226       ALLOCNO_ADD_DATA (a) = allocno_coalesce_data + ALLOCNO_NUM (a);
4227       ALLOCNO_COALESCE_DATA (a)->first = a;
4228       ALLOCNO_COALESCE_DATA (a)->next = a;
4229     }
4230   coalesce_allocnos ();
4231   ira_free_bitmap (coloring_allocno_bitmap);
4232   regno_coalesced_allocno_cost
4233     = (int *) ira_allocate (max_regno * sizeof (int));
4234   regno_coalesced_allocno_num
4235     = (int *) ira_allocate (max_regno * sizeof (int));
4236   memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
4237   setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
4238   /* Sort regnos according frequencies of the corresponding coalesced
4239      allocno sets.  */
4240   qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
4241   spilled_coalesced_allocnos
4242     = (ira_allocno_t *) ira_allocate (ira_allocnos_num
4243 				      * sizeof (ira_allocno_t));
4244   /* Collect allocnos representing the spilled coalesced allocno
4245      sets.  */
4246   num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
4247 					    spilled_coalesced_allocnos);
4248   if (flag_ira_share_spill_slots
4249       && coalesce_spill_slots (spilled_coalesced_allocnos, num))
4250     {
4251       setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
4252       qsort (pseudo_regnos, n, sizeof (int),
4253 	     coalesced_pseudo_reg_freq_compare);
4254       num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
4255 						spilled_coalesced_allocnos);
4256     }
4257   ira_free_bitmap (processed_coalesced_allocno_bitmap);
4258   allocno_coalesced_p = false;
4259   /* Assign stack slot numbers to spilled allocno sets, use smaller
4260      numbers for most frequently used coalesced allocnos.  -1 is
4261      reserved for dynamic search of stack slots for pseudos spilled by
4262      the reload.  */
4263   slot_num = 1;
4264   for (i = 0; i < num; i++)
4265     {
4266       allocno = spilled_coalesced_allocnos[i];
4267       if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
4268 	  || ALLOCNO_HARD_REGNO (allocno) >= 0
4269 	  || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno)))
4270 	continue;
4271       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4272 	fprintf (ira_dump_file, "      Slot %d (freq,size):", slot_num);
4273       slot_num++;
4274       for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4275 	   a = ALLOCNO_COALESCE_DATA (a)->next)
4276 	{
4277 	  ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
4278 	  ALLOCNO_HARD_REGNO (a) = -slot_num;
4279 	  if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4280 	    {
4281 	      machine_mode mode = wider_subreg_mode
4282 		(PSEUDO_REGNO_MODE (ALLOCNO_REGNO (a)),
4283 		 reg_max_ref_mode[ALLOCNO_REGNO (a)]);
4284 	      fprintf (ira_dump_file, " a%dr%d(%d,",
4285 		       ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a));
4286 	      print_dec (GET_MODE_SIZE (mode), ira_dump_file, SIGNED);
4287 	      fprintf (ira_dump_file, ")\n");
4288 	    }
4289 
4290 	  if (a == allocno)
4291 	    break;
4292 	}
4293       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4294 	fprintf (ira_dump_file, "\n");
4295     }
4296   ira_spilled_reg_stack_slots_num = slot_num - 1;
4297   ira_free (spilled_coalesced_allocnos);
4298   /* Sort regnos according the slot numbers.  */
4299   regno_max_ref_mode = reg_max_ref_mode;
4300   qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
4301   FOR_EACH_ALLOCNO (a, ai)
4302     ALLOCNO_ADD_DATA (a) = NULL;
4303   ira_free (allocno_coalesce_data);
4304   ira_free (regno_coalesced_allocno_num);
4305   ira_free (regno_coalesced_allocno_cost);
4306 }
4307 
4308 
4309 
4310 /* This page contains code used by the reload pass to improve the
4311    final code.  */
4312 
4313 /* The function is called from reload to mark changes in the
4314    allocation of REGNO made by the reload.  Remember that reg_renumber
4315    reflects the change result.  */
4316 void
ira_mark_allocation_change(int regno)4317 ira_mark_allocation_change (int regno)
4318 {
4319   ira_allocno_t a = ira_regno_allocno_map[regno];
4320   int old_hard_regno, hard_regno, cost;
4321   enum reg_class aclass = ALLOCNO_CLASS (a);
4322 
4323   ira_assert (a != NULL);
4324   hard_regno = reg_renumber[regno];
4325   if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
4326     return;
4327   if (old_hard_regno < 0)
4328     cost = -ALLOCNO_MEMORY_COST (a);
4329   else
4330     {
4331       ira_assert (ira_class_hard_reg_index[aclass][old_hard_regno] >= 0);
4332       cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
4333 	       ? ALLOCNO_CLASS_COST (a)
4334 	       : ALLOCNO_HARD_REG_COSTS (a)
4335 	         [ira_class_hard_reg_index[aclass][old_hard_regno]]);
4336       update_costs_from_copies (a, false, false);
4337     }
4338   ira_overall_cost -= cost;
4339   ALLOCNO_HARD_REGNO (a) = hard_regno;
4340   if (hard_regno < 0)
4341     {
4342       ALLOCNO_HARD_REGNO (a) = -1;
4343       cost += ALLOCNO_MEMORY_COST (a);
4344     }
4345   else if (ira_class_hard_reg_index[aclass][hard_regno] >= 0)
4346     {
4347       cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
4348 	       ? ALLOCNO_CLASS_COST (a)
4349 	       : ALLOCNO_HARD_REG_COSTS (a)
4350 	         [ira_class_hard_reg_index[aclass][hard_regno]]);
4351       update_costs_from_copies (a, true, false);
4352     }
4353   else
4354     /* Reload changed class of the allocno.  */
4355     cost = 0;
4356   ira_overall_cost += cost;
4357 }
4358 
4359 /* This function is called when reload deletes memory-memory move.  In
4360    this case we marks that the allocation of the corresponding
4361    allocnos should be not changed in future.  Otherwise we risk to get
4362    a wrong code.  */
4363 void
ira_mark_memory_move_deletion(int dst_regno,int src_regno)4364 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
4365 {
4366   ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
4367   ira_allocno_t src = ira_regno_allocno_map[src_regno];
4368 
4369   ira_assert (dst != NULL && src != NULL
4370 	      && ALLOCNO_HARD_REGNO (dst) < 0
4371 	      && ALLOCNO_HARD_REGNO (src) < 0);
4372   ALLOCNO_DONT_REASSIGN_P (dst) = true;
4373   ALLOCNO_DONT_REASSIGN_P (src) = true;
4374 }
4375 
4376 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
4377    allocno A and return TRUE in the case of success.  */
4378 static bool
allocno_reload_assign(ira_allocno_t a,HARD_REG_SET forbidden_regs)4379 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
4380 {
4381   int hard_regno;
4382   enum reg_class aclass;
4383   int regno = ALLOCNO_REGNO (a);
4384   HARD_REG_SET saved[2];
4385   int i, n;
4386 
4387   n = ALLOCNO_NUM_OBJECTS (a);
4388   for (i = 0; i < n; i++)
4389     {
4390       ira_object_t obj = ALLOCNO_OBJECT (a, i);
4391       COPY_HARD_REG_SET (saved[i], OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
4392       IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), forbidden_regs);
4393       if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
4394 	IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
4395 			  call_used_reg_set);
4396     }
4397   ALLOCNO_ASSIGNED_P (a) = false;
4398   aclass = ALLOCNO_CLASS (a);
4399   update_curr_costs (a);
4400   assign_hard_reg (a, true);
4401   hard_regno = ALLOCNO_HARD_REGNO (a);
4402   reg_renumber[regno] = hard_regno;
4403   if (hard_regno < 0)
4404     ALLOCNO_HARD_REGNO (a) = -1;
4405   else
4406     {
4407       ira_assert (ira_class_hard_reg_index[aclass][hard_regno] >= 0);
4408       ira_overall_cost
4409 	-= (ALLOCNO_MEMORY_COST (a)
4410 	    - (ALLOCNO_HARD_REG_COSTS (a) == NULL
4411 	       ? ALLOCNO_CLASS_COST (a)
4412 	       : ALLOCNO_HARD_REG_COSTS (a)[ira_class_hard_reg_index
4413 					    [aclass][hard_regno]]));
4414       if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
4415 	  && ira_hard_reg_set_intersection_p (hard_regno, ALLOCNO_MODE (a),
4416 					      call_used_reg_set))
4417 	{
4418 	  ira_assert (flag_caller_saves);
4419 	  caller_save_needed = 1;
4420 	}
4421     }
4422 
4423   /* If we found a hard register, modify the RTL for the pseudo
4424      register to show the hard register, and mark the pseudo register
4425      live.  */
4426   if (reg_renumber[regno] >= 0)
4427     {
4428       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4429 	fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
4430       SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
4431       mark_home_live (regno);
4432     }
4433   else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4434     fprintf (ira_dump_file, "\n");
4435   for (i = 0; i < n; i++)
4436     {
4437       ira_object_t obj = ALLOCNO_OBJECT (a, i);
4438       COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), saved[i]);
4439     }
4440   return reg_renumber[regno] >= 0;
4441 }
4442 
4443 /* Sort pseudos according their usage frequencies (putting most
4444    frequently ones first).  */
4445 static int
pseudo_reg_compare(const void * v1p,const void * v2p)4446 pseudo_reg_compare (const void *v1p, const void *v2p)
4447 {
4448   int regno1 = *(const int *) v1p;
4449   int regno2 = *(const int *) v2p;
4450   int diff;
4451 
4452   if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
4453     return diff;
4454   return regno1 - regno2;
4455 }
4456 
4457 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
4458    NUM of them) or spilled pseudos conflicting with pseudos in
4459    SPILLED_PSEUDO_REGS.  Return TRUE and update SPILLED, if the
4460    allocation has been changed.  The function doesn't use
4461    BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
4462    PSEUDO_PREVIOUS_REGS for the corresponding pseudos.  The function
4463    is called by the reload pass at the end of each reload
4464    iteration.  */
4465 bool
ira_reassign_pseudos(int * spilled_pseudo_regs,int num,HARD_REG_SET bad_spill_regs,HARD_REG_SET * pseudo_forbidden_regs,HARD_REG_SET * pseudo_previous_regs,bitmap spilled)4466 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
4467 		      HARD_REG_SET bad_spill_regs,
4468 		      HARD_REG_SET *pseudo_forbidden_regs,
4469 		      HARD_REG_SET *pseudo_previous_regs,
4470 		      bitmap spilled)
4471 {
4472   int i, n, regno;
4473   bool changed_p;
4474   ira_allocno_t a;
4475   HARD_REG_SET forbidden_regs;
4476   bitmap temp = BITMAP_ALLOC (NULL);
4477 
4478   /* Add pseudos which conflict with pseudos already in
4479      SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS.  This is preferable
4480      to allocating in two steps as some of the conflicts might have
4481      a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS.  */
4482   for (i = 0; i < num; i++)
4483     bitmap_set_bit (temp, spilled_pseudo_regs[i]);
4484 
4485   for (i = 0, n = num; i < n; i++)
4486     {
4487       int nr, j;
4488       int regno = spilled_pseudo_regs[i];
4489       bitmap_set_bit (temp, regno);
4490 
4491       a = ira_regno_allocno_map[regno];
4492       nr = ALLOCNO_NUM_OBJECTS (a);
4493       for (j = 0; j < nr; j++)
4494 	{
4495 	  ira_object_t conflict_obj;
4496 	  ira_object_t obj = ALLOCNO_OBJECT (a, j);
4497 	  ira_object_conflict_iterator oci;
4498 
4499 	  FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
4500 	    {
4501 	      ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
4502 	      if (ALLOCNO_HARD_REGNO (conflict_a) < 0
4503 		  && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
4504 		  && bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a)))
4505 		{
4506 		  spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a);
4507 		  /* ?!? This seems wrong.  */
4508 		  bitmap_set_bit (consideration_allocno_bitmap,
4509 				  ALLOCNO_NUM (conflict_a));
4510 		}
4511 	    }
4512 	}
4513     }
4514 
4515   if (num > 1)
4516     qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
4517   changed_p = false;
4518   /* Try to assign hard registers to pseudos from
4519      SPILLED_PSEUDO_REGS.  */
4520   for (i = 0; i < num; i++)
4521     {
4522       regno = spilled_pseudo_regs[i];
4523       COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
4524       IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
4525       IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
4526       gcc_assert (reg_renumber[regno] < 0);
4527       a = ira_regno_allocno_map[regno];
4528       ira_mark_allocation_change (regno);
4529       ira_assert (reg_renumber[regno] < 0);
4530       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4531 	fprintf (ira_dump_file,
4532 		 "      Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
4533 		 ALLOCNO_MEMORY_COST (a)
4534 		 - ALLOCNO_CLASS_COST (a));
4535       allocno_reload_assign (a, forbidden_regs);
4536       if (reg_renumber[regno] >= 0)
4537 	{
4538 	  CLEAR_REGNO_REG_SET (spilled, regno);
4539 	  changed_p = true;
4540 	}
4541     }
4542   BITMAP_FREE (temp);
4543   return changed_p;
4544 }
4545 
4546 /* The function is called by reload and returns already allocated
4547    stack slot (if any) for REGNO with given INHERENT_SIZE and
4548    TOTAL_SIZE.  In the case of failure to find a slot which can be
4549    used for REGNO, the function returns NULL.  */
4550 rtx
ira_reuse_stack_slot(int regno,poly_uint64 inherent_size,poly_uint64 total_size)4551 ira_reuse_stack_slot (int regno, poly_uint64 inherent_size,
4552 		      poly_uint64 total_size)
4553 {
4554   unsigned int i;
4555   int slot_num, best_slot_num;
4556   int cost, best_cost;
4557   ira_copy_t cp, next_cp;
4558   ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
4559   rtx x;
4560   bitmap_iterator bi;
4561   struct ira_spilled_reg_stack_slot *slot = NULL;
4562 
4563   ira_assert (! ira_use_lra_p);
4564 
4565   ira_assert (known_eq (inherent_size, PSEUDO_REGNO_BYTES (regno))
4566 	      && known_le (inherent_size, total_size)
4567 	      && ALLOCNO_HARD_REGNO (allocno) < 0);
4568   if (! flag_ira_share_spill_slots)
4569     return NULL_RTX;
4570   slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4571   if (slot_num != -1)
4572     {
4573       slot = &ira_spilled_reg_stack_slots[slot_num];
4574       x = slot->mem;
4575     }
4576   else
4577     {
4578       best_cost = best_slot_num = -1;
4579       x = NULL_RTX;
4580       /* It means that the pseudo was spilled in the reload pass, try
4581 	 to reuse a slot.  */
4582       for (slot_num = 0;
4583 	   slot_num < ira_spilled_reg_stack_slots_num;
4584 	   slot_num++)
4585 	{
4586 	  slot = &ira_spilled_reg_stack_slots[slot_num];
4587 	  if (slot->mem == NULL_RTX)
4588 	    continue;
4589 	  if (maybe_lt (slot->width, total_size)
4590 	      || maybe_lt (GET_MODE_SIZE (GET_MODE (slot->mem)), inherent_size))
4591 	    continue;
4592 
4593 	  EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4594 				    FIRST_PSEUDO_REGISTER, i, bi)
4595 	    {
4596 	      another_allocno = ira_regno_allocno_map[i];
4597 	      if (allocnos_conflict_by_live_ranges_p (allocno,
4598 						      another_allocno))
4599 		goto cont;
4600 	    }
4601 	  for (cost = 0, cp = ALLOCNO_COPIES (allocno);
4602 	       cp != NULL;
4603 	       cp = next_cp)
4604 	    {
4605 	      if (cp->first == allocno)
4606 		{
4607 		  next_cp = cp->next_first_allocno_copy;
4608 		  another_allocno = cp->second;
4609 		}
4610 	      else if (cp->second == allocno)
4611 		{
4612 		  next_cp = cp->next_second_allocno_copy;
4613 		  another_allocno = cp->first;
4614 		}
4615 	      else
4616 		gcc_unreachable ();
4617 	      if (cp->insn == NULL_RTX)
4618 		continue;
4619 	      if (bitmap_bit_p (&slot->spilled_regs,
4620 				ALLOCNO_REGNO (another_allocno)))
4621 		cost += cp->freq;
4622 	    }
4623 	  if (cost > best_cost)
4624 	    {
4625 	      best_cost = cost;
4626 	      best_slot_num = slot_num;
4627 	    }
4628 	cont:
4629 	  ;
4630 	}
4631       if (best_cost >= 0)
4632 	{
4633 	  slot_num = best_slot_num;
4634 	  slot = &ira_spilled_reg_stack_slots[slot_num];
4635 	  SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4636 	  x = slot->mem;
4637 	  ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4638 	}
4639     }
4640   if (x != NULL_RTX)
4641     {
4642       ira_assert (known_ge (slot->width, total_size));
4643 #ifdef ENABLE_IRA_CHECKING
4644       EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4645 				FIRST_PSEUDO_REGISTER, i, bi)
4646 	{
4647 	  ira_assert (! conflict_by_live_ranges_p (regno, i));
4648 	}
4649 #endif
4650       SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4651       if (internal_flag_ira_verbose > 3 && ira_dump_file)
4652 	{
4653 	  fprintf (ira_dump_file, "      Assigning %d(freq=%d) slot %d of",
4654 		   regno, REG_FREQ (regno), slot_num);
4655 	  EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4656 				    FIRST_PSEUDO_REGISTER, i, bi)
4657 	    {
4658 	      if ((unsigned) regno != i)
4659 		fprintf (ira_dump_file, " %d", i);
4660 	    }
4661 	  fprintf (ira_dump_file, "\n");
4662 	}
4663     }
4664   return x;
4665 }
4666 
4667 /* This is called by reload every time a new stack slot X with
4668    TOTAL_SIZE was allocated for REGNO.  We store this info for
4669    subsequent ira_reuse_stack_slot calls.  */
4670 void
ira_mark_new_stack_slot(rtx x,int regno,poly_uint64 total_size)4671 ira_mark_new_stack_slot (rtx x, int regno, poly_uint64 total_size)
4672 {
4673   struct ira_spilled_reg_stack_slot *slot;
4674   int slot_num;
4675   ira_allocno_t allocno;
4676 
4677   ira_assert (! ira_use_lra_p);
4678 
4679   ira_assert (known_le (PSEUDO_REGNO_BYTES (regno), total_size));
4680   allocno = ira_regno_allocno_map[regno];
4681   slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4682   if (slot_num == -1)
4683     {
4684       slot_num = ira_spilled_reg_stack_slots_num++;
4685       ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4686     }
4687   slot = &ira_spilled_reg_stack_slots[slot_num];
4688   INIT_REG_SET (&slot->spilled_regs);
4689   SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4690   slot->mem = x;
4691   slot->width = total_size;
4692   if (internal_flag_ira_verbose > 3 && ira_dump_file)
4693     fprintf (ira_dump_file, "      Assigning %d(freq=%d) a new slot %d\n",
4694 	     regno, REG_FREQ (regno), slot_num);
4695 }
4696 
4697 
4698 /* Return spill cost for pseudo-registers whose numbers are in array
4699    REGNOS (with a negative number as an end marker) for reload with
4700    given IN and OUT for INSN.  Return also number points (through
4701    EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
4702    the register pressure is high, number of references of the
4703    pseudo-registers (through NREFS), number of callee-clobbered
4704    hard-registers occupied by the pseudo-registers (through
4705    CALL_USED_COUNT), and the first hard regno occupied by the
4706    pseudo-registers (through FIRST_HARD_REGNO).  */
4707 static int
calculate_spill_cost(int * regnos,rtx in,rtx out,rtx_insn * insn,int * excess_pressure_live_length,int * nrefs,int * call_used_count,int * first_hard_regno)4708 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx_insn *insn,
4709 		      int *excess_pressure_live_length,
4710 		      int *nrefs, int *call_used_count, int *first_hard_regno)
4711 {
4712   int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
4713   bool in_p, out_p;
4714   int length;
4715   ira_allocno_t a;
4716 
4717   *nrefs = 0;
4718   for (length = count = cost = i = 0;; i++)
4719     {
4720       regno = regnos[i];
4721       if (regno < 0)
4722 	break;
4723       *nrefs += REG_N_REFS (regno);
4724       hard_regno = reg_renumber[regno];
4725       ira_assert (hard_regno >= 0);
4726       a = ira_regno_allocno_map[regno];
4727       length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) / ALLOCNO_NUM_OBJECTS (a);
4728       cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
4729       nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (a));
4730       for (j = 0; j < nregs; j++)
4731 	if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
4732 	  break;
4733       if (j == nregs)
4734 	count++;
4735       in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
4736       out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
4737       if ((in_p || out_p)
4738 	  && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
4739 	{
4740 	  saved_cost = 0;
4741 	  if (in_p)
4742 	    saved_cost += ira_memory_move_cost
4743 	                  [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][1];
4744 	  if (out_p)
4745 	    saved_cost
4746 	      += ira_memory_move_cost
4747 	         [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][0];
4748 	  cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
4749 	}
4750     }
4751   *excess_pressure_live_length = length;
4752   *call_used_count = count;
4753   hard_regno = -1;
4754   if (regnos[0] >= 0)
4755     {
4756       hard_regno = reg_renumber[regnos[0]];
4757     }
4758   *first_hard_regno = hard_regno;
4759   return cost;
4760 }
4761 
4762 /* Return TRUE if spilling pseudo-registers whose numbers are in array
4763    REGNOS is better than spilling pseudo-registers with numbers in
4764    OTHER_REGNOS for reload with given IN and OUT for INSN.  The
4765    function used by the reload pass to make better register spilling
4766    decisions.  */
4767 bool
ira_better_spill_reload_regno_p(int * regnos,int * other_regnos,rtx in,rtx out,rtx_insn * insn)4768 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
4769 				 rtx in, rtx out, rtx_insn *insn)
4770 {
4771   int cost, other_cost;
4772   int length, other_length;
4773   int nrefs, other_nrefs;
4774   int call_used_count, other_call_used_count;
4775   int hard_regno, other_hard_regno;
4776 
4777   cost = calculate_spill_cost (regnos, in, out, insn,
4778 			       &length, &nrefs, &call_used_count, &hard_regno);
4779   other_cost = calculate_spill_cost (other_regnos, in, out, insn,
4780 				     &other_length, &other_nrefs,
4781 				     &other_call_used_count,
4782 				     &other_hard_regno);
4783   if (nrefs == 0 && other_nrefs != 0)
4784     return true;
4785   if (nrefs != 0 && other_nrefs == 0)
4786     return false;
4787   if (cost != other_cost)
4788     return cost < other_cost;
4789   if (length != other_length)
4790     return length > other_length;
4791 #ifdef REG_ALLOC_ORDER
4792   if (hard_regno >= 0 && other_hard_regno >= 0)
4793     return (inv_reg_alloc_order[hard_regno]
4794 	    < inv_reg_alloc_order[other_hard_regno]);
4795 #else
4796   if (call_used_count != other_call_used_count)
4797     return call_used_count > other_call_used_count;
4798 #endif
4799   return false;
4800 }
4801 
4802 
4803 
4804 /* Allocate and initialize data necessary for assign_hard_reg.  */
4805 void
ira_initiate_assign(void)4806 ira_initiate_assign (void)
4807 {
4808   sorted_allocnos
4809     = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4810 				      * ira_allocnos_num);
4811   consideration_allocno_bitmap = ira_allocate_bitmap ();
4812   initiate_cost_update ();
4813   allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4814   sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
4815 					       * sizeof (ira_copy_t));
4816 }
4817 
4818 /* Deallocate data used by assign_hard_reg.  */
4819 void
ira_finish_assign(void)4820 ira_finish_assign (void)
4821 {
4822   ira_free (sorted_allocnos);
4823   ira_free_bitmap (consideration_allocno_bitmap);
4824   finish_cost_update ();
4825   ira_free (allocno_priorities);
4826   ira_free (sorted_copies);
4827 }
4828 
4829 
4830 
4831 /* Entry function doing color-based register allocation.  */
4832 static void
color(void)4833 color (void)
4834 {
4835   allocno_stack_vec.create (ira_allocnos_num);
4836   memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
4837   ira_initiate_assign ();
4838   do_coloring ();
4839   ira_finish_assign ();
4840   allocno_stack_vec.release ();
4841   move_spill_restore ();
4842 }
4843 
4844 
4845 
4846 /* This page contains a simple register allocator without usage of
4847    allocno conflicts.  This is used for fast allocation for -O0.  */
4848 
4849 /* Do register allocation by not using allocno conflicts.  It uses
4850    only allocno live ranges.  The algorithm is close to Chow's
4851    priority coloring.  */
4852 static void
fast_allocation(void)4853 fast_allocation (void)
4854 {
4855   int i, j, k, num, class_size, hard_regno;
4856 #ifdef STACK_REGS
4857   bool no_stack_reg_p;
4858 #endif
4859   enum reg_class aclass;
4860   machine_mode mode;
4861   ira_allocno_t a;
4862   ira_allocno_iterator ai;
4863   live_range_t r;
4864   HARD_REG_SET conflict_hard_regs, *used_hard_regs;
4865 
4866   sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4867 						    * ira_allocnos_num);
4868   num = 0;
4869   FOR_EACH_ALLOCNO (a, ai)
4870     sorted_allocnos[num++] = a;
4871   allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4872   setup_allocno_priorities (sorted_allocnos, num);
4873   used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
4874 						  * ira_max_point);
4875   for (i = 0; i < ira_max_point; i++)
4876     CLEAR_HARD_REG_SET (used_hard_regs[i]);
4877   qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
4878 	 allocno_priority_compare_func);
4879   for (i = 0; i < num; i++)
4880     {
4881       int nr, l;
4882 
4883       a = sorted_allocnos[i];
4884       nr = ALLOCNO_NUM_OBJECTS (a);
4885       CLEAR_HARD_REG_SET (conflict_hard_regs);
4886       for (l = 0; l < nr; l++)
4887 	{
4888 	  ira_object_t obj = ALLOCNO_OBJECT (a, l);
4889 	  IOR_HARD_REG_SET (conflict_hard_regs,
4890 			    OBJECT_CONFLICT_HARD_REGS (obj));
4891 	  for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4892 	    for (j = r->start; j <= r->finish; j++)
4893 	      IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
4894 	}
4895       aclass = ALLOCNO_CLASS (a);
4896       ALLOCNO_ASSIGNED_P (a) = true;
4897       ALLOCNO_HARD_REGNO (a) = -1;
4898       if (hard_reg_set_subset_p (reg_class_contents[aclass],
4899 				 conflict_hard_regs))
4900 	continue;
4901       mode = ALLOCNO_MODE (a);
4902 #ifdef STACK_REGS
4903       no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
4904 #endif
4905       class_size = ira_class_hard_regs_num[aclass];
4906       for (j = 0; j < class_size; j++)
4907 	{
4908 	  hard_regno = ira_class_hard_regs[aclass][j];
4909 #ifdef STACK_REGS
4910 	  if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
4911 	      && hard_regno <= LAST_STACK_REG)
4912 	    continue;
4913 #endif
4914 	  if (ira_hard_reg_set_intersection_p (hard_regno, mode, conflict_hard_regs)
4915 	      || (TEST_HARD_REG_BIT
4916 		  (ira_prohibited_class_mode_regs[aclass][mode], hard_regno)))
4917 	    continue;
4918 	  ALLOCNO_HARD_REGNO (a) = hard_regno;
4919 	  for (l = 0; l < nr; l++)
4920 	    {
4921 	      ira_object_t obj = ALLOCNO_OBJECT (a, l);
4922 	      for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4923 		for (k = r->start; k <= r->finish; k++)
4924 		  IOR_HARD_REG_SET (used_hard_regs[k],
4925 				    ira_reg_mode_hard_regset[hard_regno][mode]);
4926 	    }
4927 	  break;
4928 	}
4929     }
4930   ira_free (sorted_allocnos);
4931   ira_free (used_hard_regs);
4932   ira_free (allocno_priorities);
4933   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
4934     ira_print_disposition (ira_dump_file);
4935 }
4936 
4937 
4938 
4939 /* Entry function doing coloring.  */
4940 void
ira_color(void)4941 ira_color (void)
4942 {
4943   ira_allocno_t a;
4944   ira_allocno_iterator ai;
4945 
4946   /* Setup updated costs.  */
4947   FOR_EACH_ALLOCNO (a, ai)
4948     {
4949       ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
4950       ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
4951     }
4952   if (ira_conflicts_p)
4953     color ();
4954   else
4955     fast_allocation ();
4956 }
4957