Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / lra-assigns.c
1 /* Assign reload pseudos.
2    Copyright (C) 2010-2015 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
22 /* This file's main objective is to assign hard registers to reload
23    pseudos.  It also tries to allocate hard registers to other
24    pseudos, but at a lower priority than the reload pseudos.  The pass
25    does not transform the RTL.
26
27    We must allocate a hard register to every reload pseudo.  We try to
28    increase the chances of finding a viable allocation by assigning
29    the pseudos in order of fewest available hard registers first.  If
30    we still fail to find a hard register, we spill other (non-reload)
31    pseudos in order to make room.
32
33    find_hard_regno_for finds hard registers for allocation without
34    spilling.  spill_for does the same with spilling.  Both functions
35    use a cost model to determine the most profitable choice of hard
36    and spill registers.
37
38    Once we have finished allocating reload pseudos, we also try to
39    assign registers to other (non-reload) pseudos.  This is useful if
40    hard registers were freed up by the spilling just described.
41
42    We try to assign hard registers by collecting pseudos into threads.
43    These threads contain reload and inheritance pseudos that are
44    connected by copies (move insns).  Doing this improves the chances
45    of pseudos in the thread getting the same hard register and, as a
46    result, of allowing some move insns to be deleted.
47
48    When we assign a hard register to a pseudo, we decrease the cost of
49    using the same hard register for pseudos that are connected by
50    copies.
51
52    If two hard registers have the same frequency-derived cost, we
53    prefer hard registers with higher priorities.  The mapping of
54    registers to priorities is controlled by the register_priority
55    target hook.  For example, x86-64 has a few register priorities:
56    hard registers with and without REX prefixes have different
57    priorities.  This permits us to generate smaller code as insns
58    without REX prefixes are shorter.
59
60    If a few hard registers are still equally good for the assignment,
61    we choose the least used hard register.  It is called leveling and
62    may be profitable for some targets.
63
64    Only insns with changed allocation pseudos are processed on the
65    next constraint pass.
66
67    The pseudo live-ranges are used to find conflicting pseudos.
68
69    For understanding the code, it is important to keep in mind that
70    inheritance, split, and reload pseudos created since last
71    constraint pass have regno >= lra_constraint_new_regno_start.
72    Inheritance and split pseudos created on any pass are in the
73    corresponding bitmaps.  Inheritance and split pseudos since the
74    last constraint pass have also the corresponding non-negative
75    restore_regno.  */
76
77 #include "config.h"
78 #include "system.h"
79 #include "coretypes.h"
80 #include "tm.h"
81 #include "hard-reg-set.h"
82 #include "rtl.h"
83 #include "rtl-error.h"
84 #include "tm_p.h"
85 #include "target.h"
86 #include "insn-config.h"
87 #include "recog.h"
88 #include "output.h"
89 #include "regs.h"
90 #include "hashtab.h"
91 #include "hash-set.h"
92 #include "vec.h"
93 #include "machmode.h"
94 #include "input.h"
95 #include "function.h"
96 #include "symtab.h"
97 #include "flags.h"
98 #include "statistics.h"
99 #include "double-int.h"
100 #include "real.h"
101 #include "fixed-value.h"
102 #include "alias.h"
103 #include "wide-int.h"
104 #include "inchash.h"
105 #include "tree.h"
106 #include "expmed.h"
107 #include "dojump.h"
108 #include "explow.h"
109 #include "calls.h"
110 #include "emit-rtl.h"
111 #include "varasm.h"
112 #include "stmt.h"
113 #include "expr.h"
114 #include "predict.h"
115 #include "dominance.h"
116 #include "cfg.h"
117 #include "basic-block.h"
118 #include "except.h"
119 #include "df.h"
120 #include "ira.h"
121 #include "sparseset.h"
122 #include "params.h"
123 #include "lra-int.h"
124
125 /* Current iteration number of the pass and current iteration number
126    of the pass after the latest spill pass when any former reload
127    pseudo was spilled.  */
128 int lra_assignment_iter;
129 int lra_assignment_iter_after_spill;
130
131 /* Flag of spilling former reload pseudos on this pass.  */
132 static bool former_reload_pseudo_spill_p;
133
134 /* Array containing corresponding values of function
135    lra_get_allocno_class.  It is used to speed up the code.  */
136 static enum reg_class *regno_allocno_class_array;
137
138 /* Information about the thread to which a pseudo belongs.  Threads are
139    a set of connected reload and inheritance pseudos with the same set of
140    available hard registers.  Lone registers belong to their own threads.  */
141 struct regno_assign_info
142 {
143   /* First/next pseudo of the same thread.  */
144   int first, next;
145   /* Frequency of the thread (execution frequency of only reload
146      pseudos in the thread when the thread contains a reload pseudo).
147      Defined only for the first thread pseudo.  */
148   int freq;
149 };
150
151 /* Map regno to the corresponding regno assignment info.  */
152 static struct regno_assign_info *regno_assign_info;
153
154 /* All inherited, subreg or optional pseudos created before last spill
155    sub-pass.  Such pseudos are permitted to get memory instead of hard
156    regs.  */
157 static bitmap_head non_reload_pseudos;
158
159 /* Process a pseudo copy with execution frequency COPY_FREQ connecting
160    REGNO1 and REGNO2 to form threads.  */
161 static void
162 process_copy_to_form_thread (int regno1, int regno2, int copy_freq)
163 {
164   int last, regno1_first, regno2_first;
165
166   lra_assert (regno1 >= lra_constraint_new_regno_start
167               && regno2 >= lra_constraint_new_regno_start);
168   regno1_first = regno_assign_info[regno1].first;
169   regno2_first = regno_assign_info[regno2].first;
170   if (regno1_first != regno2_first)
171     {
172       for (last = regno2_first;
173            regno_assign_info[last].next >= 0;
174            last = regno_assign_info[last].next)
175         regno_assign_info[last].first = regno1_first;
176       regno_assign_info[last].first = regno1_first;
177       regno_assign_info[last].next = regno_assign_info[regno1_first].next;
178       regno_assign_info[regno1_first].next = regno2_first;
179       regno_assign_info[regno1_first].freq
180         += regno_assign_info[regno2_first].freq;
181     }
182   regno_assign_info[regno1_first].freq -= 2 * copy_freq;
183   lra_assert (regno_assign_info[regno1_first].freq >= 0);
184 }
185
186 /* Initialize REGNO_ASSIGN_INFO and form threads.  */
187 static void
188 init_regno_assign_info (void)
189 {
190   int i, regno1, regno2, max_regno = max_reg_num ();
191   lra_copy_t cp;
192
193   regno_assign_info = XNEWVEC (struct regno_assign_info, max_regno);
194   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
195     {
196       regno_assign_info[i].first = i;
197       regno_assign_info[i].next = -1;
198       regno_assign_info[i].freq = lra_reg_info[i].freq;
199     }
200   /* Form the threads.  */
201   for (i = 0; (cp = lra_get_copy (i)) != NULL; i++)
202     if ((regno1 = cp->regno1) >= lra_constraint_new_regno_start
203         && (regno2 = cp->regno2) >= lra_constraint_new_regno_start
204         && reg_renumber[regno1] < 0 && lra_reg_info[regno1].nrefs != 0
205         && reg_renumber[regno2] < 0 && lra_reg_info[regno2].nrefs != 0
206         && (ira_class_hard_regs_num[regno_allocno_class_array[regno1]]
207             == ira_class_hard_regs_num[regno_allocno_class_array[regno2]]))
208       process_copy_to_form_thread (regno1, regno2, cp->freq);
209 }
210
211 /* Free REGNO_ASSIGN_INFO.  */
212 static void
213 finish_regno_assign_info (void)
214 {
215   free (regno_assign_info);
216 }
217
218 /* The function is used to sort *reload* and *inheritance* pseudos to
219    try to assign them hard registers.  We put pseudos from the same
220    thread always nearby.  */
221 static int
222 reload_pseudo_compare_func (const void *v1p, const void *v2p)
223 {
224   int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
225   enum reg_class cl1 = regno_allocno_class_array[r1];
226   enum reg_class cl2 = regno_allocno_class_array[r2];
227   int diff;
228
229   lra_assert (r1 >= lra_constraint_new_regno_start
230               && r2 >= lra_constraint_new_regno_start);
231
232   /* Prefer to assign reload registers with smaller classes first to
233      guarantee assignment to all reload registers.  */
234   if ((diff = (ira_class_hard_regs_num[cl1]
235                - ira_class_hard_regs_num[cl2])) != 0)
236     return diff;
237   if ((diff
238        = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
239           - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0
240       /* The code below executes rarely as nregs == 1 in most cases.
241          So we should not worry about using faster data structures to
242          check reload pseudos.  */
243       && ! bitmap_bit_p (&non_reload_pseudos, r1)
244       && ! bitmap_bit_p (&non_reload_pseudos, r2))
245     return diff;
246   if ((diff = (regno_assign_info[regno_assign_info[r2].first].freq
247                - regno_assign_info[regno_assign_info[r1].first].freq)) != 0)
248     return diff;
249   /* Allocate bigger pseudos first to avoid register file
250      fragmentation.  */
251   if ((diff
252        = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
253           - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0)
254     return diff;
255   /* Put pseudos from the thread nearby.  */
256   if ((diff = regno_assign_info[r1].first - regno_assign_info[r2].first) != 0)
257     return diff;
258   /* If regs are equally good, sort by their numbers, so that the
259      results of qsort leave nothing to chance.  */
260   return r1 - r2;
261 }
262
263 /* The function is used to sort *non-reload* pseudos to try to assign
264    them hard registers.  The order calculation is simpler than in the
265    previous function and based on the pseudo frequency usage.  */
266 static int
267 pseudo_compare_func (const void *v1p, const void *v2p)
268 {
269   int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
270   int diff;
271
272   /* Prefer to assign more frequently used registers first.  */
273   if ((diff = lra_reg_info[r2].freq - lra_reg_info[r1].freq) != 0)
274     return diff;
275
276   /* If regs are equally good, sort by their numbers, so that the
277      results of qsort leave nothing to chance.  */
278   return r1 - r2;
279 }
280
281 /* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the
282    pseudo live ranges with given start point.  We insert only live
283    ranges of pseudos interesting for assignment purposes.  They are
284    reload pseudos and pseudos assigned to hard registers.  */
285 static lra_live_range_t *start_point_ranges;
286
287 /* Used as a flag that a live range is not inserted in the start point
288    chain.  */
289 static struct lra_live_range not_in_chain_mark;
290
291 /* Create and set up START_POINT_RANGES.  */
292 static void
293 create_live_range_start_chains (void)
294 {
295   int i, max_regno;
296   lra_live_range_t r;
297
298   start_point_ranges = XCNEWVEC (lra_live_range_t, lra_live_max_point);
299   max_regno = max_reg_num ();
300   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
301     if (i >= lra_constraint_new_regno_start || reg_renumber[i] >= 0)
302       {
303         for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
304           {
305             r->start_next = start_point_ranges[r->start];
306             start_point_ranges[r->start] = r;
307           }
308       }
309     else
310       {
311         for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
312           r->start_next = &not_in_chain_mark;
313       }
314 }
315
316 /* Insert live ranges of pseudo REGNO into start chains if they are
317    not there yet.  */
318 static void
319 insert_in_live_range_start_chain (int regno)
320 {
321   lra_live_range_t r = lra_reg_info[regno].live_ranges;
322
323   if (r->start_next != &not_in_chain_mark)
324     return;
325   for (; r != NULL; r = r->next)
326     {
327       r->start_next = start_point_ranges[r->start];
328       start_point_ranges[r->start] = r;
329     }
330 }
331
332 /* Free START_POINT_RANGES.  */
333 static void
334 finish_live_range_start_chains (void)
335 {
336   gcc_assert (start_point_ranges != NULL);
337   free (start_point_ranges);
338   start_point_ranges = NULL;
339 }
340
341 /* Map: program point -> bitmap of all pseudos living at the point and
342    assigned to hard registers.  */
343 static bitmap_head *live_hard_reg_pseudos;
344 static bitmap_obstack live_hard_reg_pseudos_bitmap_obstack;
345
346 /* reg_renumber corresponding to pseudos marked in
347    live_hard_reg_pseudos.  reg_renumber might be not matched to
348    live_hard_reg_pseudos but live_pseudos_reg_renumber always reflects
349    live_hard_reg_pseudos.  */
350 static int *live_pseudos_reg_renumber;
351
352 /* Sparseset used to calculate living hard reg pseudos for some program
353    point range.  */
354 static sparseset live_range_hard_reg_pseudos;
355
356 /* Sparseset used to calculate living reload/inheritance pseudos for
357    some program point range.  */
358 static sparseset live_range_reload_inheritance_pseudos;
359
360 /* Allocate and initialize the data about living pseudos at program
361    points.  */
362 static void
363 init_lives (void)
364 {
365   int i, max_regno = max_reg_num ();
366
367   live_range_hard_reg_pseudos = sparseset_alloc (max_regno);
368   live_range_reload_inheritance_pseudos = sparseset_alloc (max_regno);
369   live_hard_reg_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
370   bitmap_obstack_initialize (&live_hard_reg_pseudos_bitmap_obstack);
371   for (i = 0; i < lra_live_max_point; i++)
372     bitmap_initialize (&live_hard_reg_pseudos[i],
373                        &live_hard_reg_pseudos_bitmap_obstack);
374   live_pseudos_reg_renumber = XNEWVEC (int, max_regno);
375   for (i = 0; i < max_regno; i++)
376     live_pseudos_reg_renumber[i] = -1;
377 }
378
379 /* Free the data about living pseudos at program points.  */
380 static void
381 finish_lives (void)
382 {
383   sparseset_free (live_range_hard_reg_pseudos);
384   sparseset_free (live_range_reload_inheritance_pseudos);
385   free (live_hard_reg_pseudos);
386   bitmap_obstack_release (&live_hard_reg_pseudos_bitmap_obstack);
387   free (live_pseudos_reg_renumber);
388 }
389
390 /* Update the LIVE_HARD_REG_PSEUDOS and LIVE_PSEUDOS_REG_RENUMBER
391    entries for pseudo REGNO.  Assume that the register has been
392    spilled if FREE_P, otherwise assume that it has been assigned
393    reg_renumber[REGNO] (if >= 0).  We also insert the pseudo live
394    ranges in the start chains when it is assumed to be assigned to a
395    hard register because we use the chains of pseudos assigned to hard
396    registers during allocation.  */
397 static void
398 update_lives (int regno, bool free_p)
399 {
400   int p;
401   lra_live_range_t r;
402
403   if (reg_renumber[regno] < 0)
404     return;
405   live_pseudos_reg_renumber[regno] = free_p ? -1 : reg_renumber[regno];
406   for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
407     {
408       for (p = r->start; p <= r->finish; p++)
409         if (free_p)
410           bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
411         else
412           {
413             bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
414             insert_in_live_range_start_chain (regno);
415           }
416     }
417 }
418
419 /* Sparseset used to calculate reload pseudos conflicting with a given
420    pseudo when we are trying to find a hard register for the given
421    pseudo.  */
422 static sparseset conflict_reload_and_inheritance_pseudos;
423
424 /* Map: program point -> bitmap of all reload and inheritance pseudos
425    living at the point.  */
426 static bitmap_head *live_reload_and_inheritance_pseudos;
427 static bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack;
428
429 /* Allocate and initialize data about living reload pseudos at any
430    given program point.  */
431 static void
432 init_live_reload_and_inheritance_pseudos (void)
433 {
434   int i, p, max_regno = max_reg_num ();
435   lra_live_range_t r;
436
437   conflict_reload_and_inheritance_pseudos = sparseset_alloc (max_regno);
438   live_reload_and_inheritance_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
439   bitmap_obstack_initialize (&live_reload_and_inheritance_pseudos_bitmap_obstack);
440   for (p = 0; p < lra_live_max_point; p++)
441     bitmap_initialize (&live_reload_and_inheritance_pseudos[p],
442                        &live_reload_and_inheritance_pseudos_bitmap_obstack);
443   for (i = lra_constraint_new_regno_start; i < max_regno; i++)
444     {
445       for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
446         for (p = r->start; p <= r->finish; p++)
447           bitmap_set_bit (&live_reload_and_inheritance_pseudos[p], i);
448     }
449 }
450
451 /* Finalize data about living reload pseudos at any given program
452    point.  */
453 static void
454 finish_live_reload_and_inheritance_pseudos (void)
455 {
456   sparseset_free (conflict_reload_and_inheritance_pseudos);
457   free (live_reload_and_inheritance_pseudos);
458   bitmap_obstack_release (&live_reload_and_inheritance_pseudos_bitmap_obstack);
459 }
460
461 /* The value used to check that cost of given hard reg is really
462    defined currently.  */
463 static int curr_hard_regno_costs_check = 0;
464 /* Array used to check that cost of the corresponding hard reg (the
465    array element index) is really defined currently.  */
466 static int hard_regno_costs_check[FIRST_PSEUDO_REGISTER];
467 /* The current costs of allocation of hard regs.  Defined only if the
468    value of the corresponding element of the previous array is equal to
469    CURR_HARD_REGNO_COSTS_CHECK.  */
470 static int hard_regno_costs[FIRST_PSEUDO_REGISTER];
471
472 /* Adjust cost of HARD_REGNO by INCR.  Reset the cost first if it is
473    not defined yet.  */
474 static inline void
475 adjust_hard_regno_cost (int hard_regno, int incr)
476 {
477   if (hard_regno_costs_check[hard_regno] != curr_hard_regno_costs_check)
478     hard_regno_costs[hard_regno] = 0;
479   hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
480   hard_regno_costs[hard_regno] += incr;
481 }
482
483 /* Try to find a free hard register for pseudo REGNO.  Return the
484    hard register on success and set *COST to the cost of using
485    that register.  (If several registers have equal cost, the one with
486    the highest priority wins.)  Return -1 on failure.
487
488    If FIRST_P, return the first available hard reg ignoring other
489    criteria, e.g. allocation cost.  This approach results in less hard
490    reg pool fragmentation and permit to allocate hard regs to reload
491    pseudos in complicated situations where pseudo sizes are different.
492
493    If TRY_ONLY_HARD_REGNO >= 0, consider only that hard register,
494    otherwise consider all hard registers in REGNO's class.  */
495 static int
496 find_hard_regno_for (int regno, int *cost, int try_only_hard_regno,
497                      bool first_p)
498 {
499   HARD_REG_SET conflict_set;
500   int best_cost = INT_MAX, best_priority = INT_MIN, best_usage = INT_MAX;
501   lra_live_range_t r;
502   int p, i, j, rclass_size, best_hard_regno, priority, hard_regno;
503   int hr, conflict_hr, nregs;
504   machine_mode biggest_mode;
505   unsigned int k, conflict_regno;
506   int offset, val, biggest_nregs, nregs_diff;
507   enum reg_class rclass;
508   bitmap_iterator bi;
509   bool *rclass_intersect_p;
510   HARD_REG_SET impossible_start_hard_regs, available_regs;
511
512   COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
513   rclass = regno_allocno_class_array[regno];
514   rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
515   curr_hard_regno_costs_check++;
516   sparseset_clear (conflict_reload_and_inheritance_pseudos);
517   sparseset_clear (live_range_hard_reg_pseudos);
518   IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs);
519   biggest_mode = lra_reg_info[regno].biggest_mode;
520   for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
521     {
522       EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
523         if (rclass_intersect_p[regno_allocno_class_array[k]])
524           sparseset_set_bit (live_range_hard_reg_pseudos, k);
525       EXECUTE_IF_SET_IN_BITMAP (&live_reload_and_inheritance_pseudos[r->start],
526                                 0, k, bi)
527         if (lra_reg_info[k].preferred_hard_regno1 >= 0
528             && live_pseudos_reg_renumber[k] < 0
529             && rclass_intersect_p[regno_allocno_class_array[k]])
530           sparseset_set_bit (conflict_reload_and_inheritance_pseudos, k);
531       for (p = r->start + 1; p <= r->finish; p++)
532         {
533           lra_live_range_t r2;
534
535           for (r2 = start_point_ranges[p];
536                r2 != NULL;
537                r2 = r2->start_next)
538             {
539               if (r2->regno >= lra_constraint_new_regno_start
540                   && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
541                   && live_pseudos_reg_renumber[r2->regno] < 0
542                   && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
543                 sparseset_set_bit (conflict_reload_and_inheritance_pseudos,
544                                    r2->regno);
545               if (live_pseudos_reg_renumber[r2->regno] >= 0
546                   && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
547                 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
548             }
549         }
550     }
551   if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
552     {
553       adjust_hard_regno_cost
554         (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit1);
555       if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
556         adjust_hard_regno_cost
557           (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit2);
558     }
559 #ifdef STACK_REGS
560   if (lra_reg_info[regno].no_stack_p)
561     for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
562       SET_HARD_REG_BIT (conflict_set, i);
563 #endif
564   sparseset_clear_bit (conflict_reload_and_inheritance_pseudos, regno);
565   val = lra_reg_info[regno].val;
566   offset = lra_reg_info[regno].offset;
567   CLEAR_HARD_REG_SET (impossible_start_hard_regs);
568   EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
569     if (lra_reg_val_equal_p (conflict_regno, val, offset))
570       {
571         conflict_hr = live_pseudos_reg_renumber[conflict_regno];
572         nregs = (hard_regno_nregs[conflict_hr]
573                  [lra_reg_info[conflict_regno].biggest_mode]);
574         /* Remember about multi-register pseudos.  For example, 2 hard
575            register pseudos can start on the same hard register but can
576            not start on HR and HR+1/HR-1.  */
577         for (hr = conflict_hr + 1;
578              hr < FIRST_PSEUDO_REGISTER && hr < conflict_hr + nregs;
579              hr++)
580           SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
581         for (hr = conflict_hr - 1;
582              hr >= 0 && hr + hard_regno_nregs[hr][biggest_mode] > conflict_hr;
583              hr--)
584           SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
585       }
586     else
587       {
588         add_to_hard_reg_set (&conflict_set,
589                              lra_reg_info[conflict_regno].biggest_mode,
590                              live_pseudos_reg_renumber[conflict_regno]);
591         if (hard_reg_set_subset_p (reg_class_contents[rclass],
592                                    conflict_set))
593           return -1;
594       }
595   EXECUTE_IF_SET_IN_SPARSESET (conflict_reload_and_inheritance_pseudos,
596                                conflict_regno)
597     if (!lra_reg_val_equal_p (conflict_regno, val, offset))
598       {
599         lra_assert (live_pseudos_reg_renumber[conflict_regno] < 0);
600         if ((hard_regno
601              = lra_reg_info[conflict_regno].preferred_hard_regno1) >= 0)
602           {
603             adjust_hard_regno_cost
604               (hard_regno,
605                lra_reg_info[conflict_regno].preferred_hard_regno_profit1);
606             if ((hard_regno
607                  = lra_reg_info[conflict_regno].preferred_hard_regno2) >= 0)
608               adjust_hard_regno_cost
609                 (hard_regno,
610                  lra_reg_info[conflict_regno].preferred_hard_regno_profit2);
611           }
612       }
613   /* Make sure that all registers in a multi-word pseudo belong to the
614      required class.  */
615   IOR_COMPL_HARD_REG_SET (conflict_set, reg_class_contents[rclass]);
616   lra_assert (rclass != NO_REGS);
617   rclass_size = ira_class_hard_regs_num[rclass];
618   best_hard_regno = -1;
619   hard_regno = ira_class_hard_regs[rclass][0];
620   biggest_nregs = hard_regno_nregs[hard_regno][biggest_mode];
621   nregs_diff = (biggest_nregs
622                 - hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)]);
623   COPY_HARD_REG_SET (available_regs, reg_class_contents[rclass]);
624   AND_COMPL_HARD_REG_SET (available_regs, lra_no_alloc_regs);
625   for (i = 0; i < rclass_size; i++)
626     {
627       if (try_only_hard_regno >= 0)
628         hard_regno = try_only_hard_regno;
629       else
630         hard_regno = ira_class_hard_regs[rclass][i];
631       if (! overlaps_hard_reg_set_p (conflict_set,
632                                      PSEUDO_REGNO_MODE (regno), hard_regno)
633           /* We can not use prohibited_class_mode_regs because it is
634              not defined for all classes.  */
635           && HARD_REGNO_MODE_OK (hard_regno, PSEUDO_REGNO_MODE (regno))
636           && ! TEST_HARD_REG_BIT (impossible_start_hard_regs, hard_regno)
637           && (nregs_diff == 0
638               || (WORDS_BIG_ENDIAN
639                   ? (hard_regno - nregs_diff >= 0
640                      && TEST_HARD_REG_BIT (available_regs,
641                                            hard_regno - nregs_diff))
642                   : TEST_HARD_REG_BIT (available_regs,
643                                        hard_regno + nregs_diff))))
644         {
645           if (hard_regno_costs_check[hard_regno]
646               != curr_hard_regno_costs_check)
647             {
648               hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
649               hard_regno_costs[hard_regno] = 0;
650             }
651           for (j = 0;
652                j < hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)];
653                j++)
654             if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j)
655                 && ! df_regs_ever_live_p (hard_regno + j))
656               /* It needs save restore.  */
657               hard_regno_costs[hard_regno]
658                 += (2
659                     * REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
660                     + 1);
661           priority = targetm.register_priority (hard_regno);
662           if (best_hard_regno < 0 || hard_regno_costs[hard_regno] < best_cost
663               || (hard_regno_costs[hard_regno] == best_cost
664                   && (priority > best_priority
665                       || (targetm.register_usage_leveling_p ()
666                           && priority == best_priority
667                           && best_usage > lra_hard_reg_usage[hard_regno]))))
668             {
669               best_hard_regno = hard_regno;
670               best_cost = hard_regno_costs[hard_regno];
671               best_priority = priority;
672               best_usage = lra_hard_reg_usage[hard_regno];
673             }
674         }
675       if (try_only_hard_regno >= 0 || (first_p && best_hard_regno >= 0))
676         break;
677     }
678   if (best_hard_regno >= 0)
679     *cost = best_cost - lra_reg_info[regno].freq;
680   return best_hard_regno;
681 }
682
683 /* Current value used for checking elements in
684    update_hard_regno_preference_check.  */
685 static int curr_update_hard_regno_preference_check;
686 /* If an element value is equal to the above variable value, then the
687    corresponding regno has been processed for preference
688    propagation.  */
689 static int *update_hard_regno_preference_check;
690
691 /* Update the preference for using HARD_REGNO for pseudos that are
692    connected directly or indirectly with REGNO.  Apply divisor DIV
693    to any preference adjustments.
694
695    The more indirectly a pseudo is connected, the smaller its effect
696    should be.  We therefore increase DIV on each "hop".  */
697 static void
698 update_hard_regno_preference (int regno, int hard_regno, int div)
699 {
700   int another_regno, cost;
701   lra_copy_t cp, next_cp;
702
703   /* Search depth 5 seems to be enough.  */
704   if (div > (1 << 5))
705     return;
706   for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
707     {
708       if (cp->regno1 == regno)
709         {
710           next_cp = cp->regno1_next;
711           another_regno = cp->regno2;
712         }
713       else if (cp->regno2 == regno)
714         {
715           next_cp = cp->regno2_next;
716           another_regno = cp->regno1;
717         }
718       else
719         gcc_unreachable ();
720       if (reg_renumber[another_regno] < 0
721           && (update_hard_regno_preference_check[another_regno]
722               != curr_update_hard_regno_preference_check))
723         {
724           update_hard_regno_preference_check[another_regno]
725             = curr_update_hard_regno_preference_check;
726           cost = cp->freq < div ? 1 : cp->freq / div;
727           lra_setup_reload_pseudo_preferenced_hard_reg
728             (another_regno, hard_regno, cost);
729           update_hard_regno_preference (another_regno, hard_regno, div * 2);
730         }
731     }
732 }
733
734 /* Return prefix title for pseudo REGNO.  */
735 static const char *
736 pseudo_prefix_title (int regno)
737 {
738   return
739     (regno < lra_constraint_new_regno_start ? ""
740      : bitmap_bit_p (&lra_inheritance_pseudos, regno) ? "inheritance "
741      : bitmap_bit_p (&lra_split_regs, regno) ? "split "
742      : bitmap_bit_p (&lra_optional_reload_pseudos, regno) ? "optional reload "
743      : bitmap_bit_p (&lra_subreg_reload_pseudos, regno) ? "subreg reload "
744      : "reload ");
745 }
746
747 /* Update REG_RENUMBER and other pseudo preferences by assignment of
748    HARD_REGNO to pseudo REGNO and print about it if PRINT_P.  */
749 void
750 lra_setup_reg_renumber (int regno, int hard_regno, bool print_p)
751 {
752   int i, hr;
753
754   /* We can not just reassign hard register.  */
755   lra_assert (hard_regno < 0 || reg_renumber[regno] < 0);
756   if ((hr = hard_regno) < 0)
757     hr = reg_renumber[regno];
758   reg_renumber[regno] = hard_regno;
759   lra_assert (hr >= 0);
760   for (i = 0; i < hard_regno_nregs[hr][PSEUDO_REGNO_MODE (regno)]; i++)
761     if (hard_regno < 0)
762       lra_hard_reg_usage[hr + i] -= lra_reg_info[regno].freq;
763     else
764       lra_hard_reg_usage[hr + i] += lra_reg_info[regno].freq;
765   if (print_p && lra_dump_file != NULL)
766     fprintf (lra_dump_file, "      Assign %d to %sr%d (freq=%d)\n",
767              reg_renumber[regno], pseudo_prefix_title (regno),
768              regno, lra_reg_info[regno].freq);
769   if (hard_regno >= 0)
770     {
771       curr_update_hard_regno_preference_check++;
772       update_hard_regno_preference (regno, hard_regno, 1);
773     }
774 }
775
776 /* Pseudos which occur in insns containing a particular pseudo.  */
777 static bitmap_head insn_conflict_pseudos;
778
779 /* Bitmaps used to contain spill pseudos for given pseudo hard regno
780    and best spill pseudos for given pseudo (and best hard regno).  */
781 static bitmap_head spill_pseudos_bitmap, best_spill_pseudos_bitmap;
782
783 /* Current pseudo check for validity of elements in
784    TRY_HARD_REG_PSEUDOS.  */
785 static int curr_pseudo_check;
786 /* Array used for validity of elements in TRY_HARD_REG_PSEUDOS.  */
787 static int try_hard_reg_pseudos_check[FIRST_PSEUDO_REGISTER];
788 /* Pseudos who hold given hard register at the considered points.  */
789 static bitmap_head try_hard_reg_pseudos[FIRST_PSEUDO_REGISTER];
790
791 /* Set up try_hard_reg_pseudos for given program point P and class
792    RCLASS.  Those are pseudos living at P and assigned to a hard
793    register of RCLASS.  In other words, those are pseudos which can be
794    spilled to assign a hard register of RCLASS to a pseudo living at
795    P.  */
796 static void
797 setup_try_hard_regno_pseudos (int p, enum reg_class rclass)
798 {
799   int i, hard_regno;
800   machine_mode mode;
801   unsigned int spill_regno;
802   bitmap_iterator bi;
803
804   /* Find what pseudos could be spilled.  */
805   EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[p], 0, spill_regno, bi)
806     {
807       mode = PSEUDO_REGNO_MODE (spill_regno);
808       hard_regno = live_pseudos_reg_renumber[spill_regno];
809       if (overlaps_hard_reg_set_p (reg_class_contents[rclass],
810                                    mode, hard_regno))
811         {
812           for (i = hard_regno_nregs[hard_regno][mode] - 1; i >= 0; i--)
813             {
814               if (try_hard_reg_pseudos_check[hard_regno + i]
815                   != curr_pseudo_check)
816                 {
817                   try_hard_reg_pseudos_check[hard_regno + i]
818                     = curr_pseudo_check;
819                   bitmap_clear (&try_hard_reg_pseudos[hard_regno + i]);
820                 }
821               bitmap_set_bit (&try_hard_reg_pseudos[hard_regno + i],
822                               spill_regno);
823             }
824         }
825     }
826 }
827
828 /* Assign temporarily HARD_REGNO to pseudo REGNO.  Temporary
829    assignment means that we might undo the data change.  */
830 static void
831 assign_temporarily (int regno, int hard_regno)
832 {
833   int p;
834   lra_live_range_t r;
835
836   for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
837     {
838       for (p = r->start; p <= r->finish; p++)
839         if (hard_regno < 0)
840           bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
841         else
842           {
843             bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
844             insert_in_live_range_start_chain (regno);
845           }
846     }
847   live_pseudos_reg_renumber[regno] = hard_regno;
848 }
849
850 /* Array used for sorting reload pseudos for subsequent allocation
851    after spilling some pseudo.  */
852 static int *sorted_reload_pseudos;
853
854 /* Spill some pseudos for a reload pseudo REGNO and return hard
855    register which should be used for pseudo after spilling.  The
856    function adds spilled pseudos to SPILLED_PSEUDO_BITMAP.  When we
857    choose hard register (and pseudos occupying the hard registers and
858    to be spilled), we take into account not only how REGNO will
859    benefit from the spills but also how other reload pseudos not yet
860    assigned to hard registers benefit from the spills too.  In very
861    rare cases, the function can fail and return -1.
862
863    If FIRST_P, return the first available hard reg ignoring other
864    criteria, e.g. allocation cost and cost of spilling non-reload
865    pseudos.  This approach results in less hard reg pool fragmentation
866    and permit to allocate hard regs to reload pseudos in complicated
867    situations where pseudo sizes are different.  */
868 static int
869 spill_for (int regno, bitmap spilled_pseudo_bitmap, bool first_p)
870 {
871   int i, j, n, p, hard_regno, best_hard_regno, cost, best_cost, rclass_size;
872   int reload_hard_regno, reload_cost;
873   machine_mode mode;
874   enum reg_class rclass;
875   unsigned int spill_regno, reload_regno, uid;
876   int insn_pseudos_num, best_insn_pseudos_num;
877   lra_live_range_t r;
878   bitmap_iterator bi;
879
880   rclass = regno_allocno_class_array[regno];
881   lra_assert (reg_renumber[regno] < 0 && rclass != NO_REGS);
882   bitmap_clear (&insn_conflict_pseudos);
883   bitmap_clear (&best_spill_pseudos_bitmap);
884   EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi)
885     {
886       struct lra_insn_reg *ir;
887
888       for (ir = lra_get_insn_regs (uid); ir != NULL; ir = ir->next)
889         if (ir->regno >= FIRST_PSEUDO_REGISTER)
890           bitmap_set_bit (&insn_conflict_pseudos, ir->regno);
891     }
892   best_hard_regno = -1;
893   best_cost = INT_MAX;
894   best_insn_pseudos_num = INT_MAX;
895   rclass_size = ira_class_hard_regs_num[rclass];
896   mode = PSEUDO_REGNO_MODE (regno);
897   /* Invalidate try_hard_reg_pseudos elements.  */
898   curr_pseudo_check++;
899   for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
900     for (p = r->start; p <= r->finish; p++)
901       setup_try_hard_regno_pseudos (p, rclass);
902   for (i = 0; i < rclass_size; i++)
903     {
904       hard_regno = ira_class_hard_regs[rclass][i];
905       bitmap_clear (&spill_pseudos_bitmap);
906       for (j = hard_regno_nregs[hard_regno][mode] - 1; j >= 0; j--)
907         {
908           if (try_hard_reg_pseudos_check[hard_regno + j] != curr_pseudo_check)
909             continue;
910           lra_assert (!bitmap_empty_p (&try_hard_reg_pseudos[hard_regno + j]));
911           bitmap_ior_into (&spill_pseudos_bitmap,
912                            &try_hard_reg_pseudos[hard_regno + j]);
913         }
914       /* Spill pseudos.  */
915       EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
916         if ((pic_offset_table_rtx != NULL
917              && spill_regno == REGNO (pic_offset_table_rtx))
918             || ((int) spill_regno >= lra_constraint_new_regno_start
919                 && ! bitmap_bit_p (&lra_inheritance_pseudos, spill_regno)
920                 && ! bitmap_bit_p (&lra_split_regs, spill_regno)
921                 && ! bitmap_bit_p (&lra_subreg_reload_pseudos, spill_regno)
922                 && ! bitmap_bit_p (&lra_optional_reload_pseudos, spill_regno)))
923           goto fail;
924       insn_pseudos_num = 0;
925       if (lra_dump_file != NULL)
926         fprintf (lra_dump_file, "        Trying %d:", hard_regno);
927       sparseset_clear (live_range_reload_inheritance_pseudos);
928       EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
929         {
930           if (bitmap_bit_p (&insn_conflict_pseudos, spill_regno))
931             insn_pseudos_num++;
932           for (r = lra_reg_info[spill_regno].live_ranges;
933                r != NULL;
934                r = r->next)
935             {
936               for (p = r->start; p <= r->finish; p++)
937                 {
938                   lra_live_range_t r2;
939
940                   for (r2 = start_point_ranges[p];
941                        r2 != NULL;
942                        r2 = r2->start_next)
943                     if (r2->regno >= lra_constraint_new_regno_start)
944                       sparseset_set_bit (live_range_reload_inheritance_pseudos,
945                                          r2->regno);
946                 }
947             }
948         }
949       n = 0;
950       if (sparseset_cardinality (live_range_reload_inheritance_pseudos)
951           <= (unsigned)LRA_MAX_CONSIDERED_RELOAD_PSEUDOS)
952         EXECUTE_IF_SET_IN_SPARSESET (live_range_reload_inheritance_pseudos,
953                                      reload_regno)
954           if ((int) reload_regno != regno
955               && (ira_reg_classes_intersect_p
956                   [rclass][regno_allocno_class_array[reload_regno]])
957               && live_pseudos_reg_renumber[reload_regno] < 0
958               && find_hard_regno_for (reload_regno, &cost, -1, first_p) < 0)
959             sorted_reload_pseudos[n++] = reload_regno;
960       EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
961         {
962           update_lives (spill_regno, true);
963           if (lra_dump_file != NULL)
964             fprintf (lra_dump_file, " spill %d(freq=%d)",
965                      spill_regno, lra_reg_info[spill_regno].freq);
966         }
967       hard_regno = find_hard_regno_for (regno, &cost, -1, first_p);
968       if (hard_regno >= 0)
969         {
970           assign_temporarily (regno, hard_regno);
971           qsort (sorted_reload_pseudos, n, sizeof (int),
972                  reload_pseudo_compare_func);
973           for (j = 0; j < n; j++)
974             {
975               reload_regno = sorted_reload_pseudos[j];
976               lra_assert (live_pseudos_reg_renumber[reload_regno] < 0);
977               if ((reload_hard_regno
978                    = find_hard_regno_for (reload_regno,
979                                           &reload_cost, -1, first_p)) >= 0)
980                 {
981                   if (lra_dump_file != NULL)
982                     fprintf (lra_dump_file, " assign %d(cost=%d)",
983                              reload_regno, reload_cost);
984                   assign_temporarily (reload_regno, reload_hard_regno);
985                   cost += reload_cost;
986                 }
987             }
988           EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
989             {
990               rtx_insn_list *x;
991
992               cost += lra_reg_info[spill_regno].freq;
993               if (ira_reg_equiv[spill_regno].memory != NULL
994                   || ira_reg_equiv[spill_regno].constant != NULL)
995                 for (x = ira_reg_equiv[spill_regno].init_insns;
996                      x != NULL;
997                      x = x->next ())
998                   cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (x->insn ()));
999             }
1000           if (best_insn_pseudos_num > insn_pseudos_num
1001               || (best_insn_pseudos_num == insn_pseudos_num
1002                   && best_cost > cost))
1003             {
1004               best_insn_pseudos_num = insn_pseudos_num;
1005               best_cost = cost;
1006               best_hard_regno = hard_regno;
1007               bitmap_copy (&best_spill_pseudos_bitmap, &spill_pseudos_bitmap);
1008               if (lra_dump_file != NULL)
1009                 fprintf (lra_dump_file, "        Now best %d(cost=%d)\n",
1010                          hard_regno, cost);
1011             }
1012           assign_temporarily (regno, -1);
1013           for (j = 0; j < n; j++)
1014             {
1015               reload_regno = sorted_reload_pseudos[j];
1016               if (live_pseudos_reg_renumber[reload_regno] >= 0)
1017                 assign_temporarily (reload_regno, -1);
1018             }
1019         }
1020       if (lra_dump_file != NULL)
1021         fprintf (lra_dump_file, "\n");
1022       /* Restore the live hard reg pseudo info for spilled pseudos.  */
1023       EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1024         update_lives (spill_regno, false);
1025     fail:
1026       ;
1027     }
1028   /* Spill: */
1029   EXECUTE_IF_SET_IN_BITMAP (&best_spill_pseudos_bitmap, 0, spill_regno, bi)
1030     {
1031       if ((int) spill_regno >= lra_constraint_new_regno_start)
1032         former_reload_pseudo_spill_p = true;
1033       if (lra_dump_file != NULL)
1034         fprintf (lra_dump_file, "      Spill %sr%d(hr=%d, freq=%d) for r%d\n",
1035                  pseudo_prefix_title (spill_regno),
1036                  spill_regno, reg_renumber[spill_regno],
1037                  lra_reg_info[spill_regno].freq, regno);
1038       update_lives (spill_regno, true);
1039       lra_setup_reg_renumber (spill_regno, -1, false);
1040     }
1041   bitmap_ior_into (spilled_pseudo_bitmap, &best_spill_pseudos_bitmap);
1042   return best_hard_regno;
1043 }
1044
1045 /* Assign HARD_REGNO to REGNO.  */
1046 static void
1047 assign_hard_regno (int hard_regno, int regno)
1048 {
1049   int i;
1050
1051   lra_assert (hard_regno >= 0);
1052   lra_setup_reg_renumber (regno, hard_regno, true);
1053   update_lives (regno, false);
1054   for (i = 0;
1055        i < hard_regno_nregs[hard_regno][lra_reg_info[regno].biggest_mode];
1056        i++)
1057     df_set_regs_ever_live (hard_regno + i, true);
1058 }
1059
1060 /* Array used for sorting different pseudos.  */
1061 static int *sorted_pseudos;
1062
1063 /* The constraints pass is allowed to create equivalences between
1064    pseudos that make the current allocation "incorrect" (in the sense
1065    that pseudos are assigned to hard registers from their own conflict
1066    sets).  The global variable lra_risky_transformations_p says
1067    whether this might have happened.
1068
1069    Process pseudos assigned to hard registers (less frequently used
1070    first), spill if a conflict is found, and mark the spilled pseudos
1071    in SPILLED_PSEUDO_BITMAP.  Set up LIVE_HARD_REG_PSEUDOS from
1072    pseudos, assigned to hard registers.  */
1073 static void
1074 setup_live_pseudos_and_spill_after_risky_transforms (bitmap
1075                                                      spilled_pseudo_bitmap)
1076 {
1077   int p, i, j, n, regno, hard_regno;
1078   unsigned int k, conflict_regno;
1079   int val, offset;
1080   HARD_REG_SET conflict_set;
1081   machine_mode mode;
1082   lra_live_range_t r;
1083   bitmap_iterator bi;
1084   int max_regno = max_reg_num ();
1085
1086   if (! lra_risky_transformations_p)
1087     {
1088       for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1089         if (reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0)
1090           update_lives (i, false);
1091       return;
1092     }
1093   for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1094     if ((pic_offset_table_rtx == NULL_RTX
1095          || i != (int) REGNO (pic_offset_table_rtx))
1096         && reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0)
1097       sorted_pseudos[n++] = i;
1098   qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1099   if (pic_offset_table_rtx != NULL_RTX
1100       && (regno = REGNO (pic_offset_table_rtx)) >= FIRST_PSEUDO_REGISTER
1101       && reg_renumber[regno] >= 0 && lra_reg_info[regno].nrefs > 0)
1102     sorted_pseudos[n++] = regno;
1103   for (i = n - 1; i >= 0; i--)
1104     {
1105       regno = sorted_pseudos[i];
1106       hard_regno = reg_renumber[regno];
1107       lra_assert (hard_regno >= 0);
1108       mode = lra_reg_info[regno].biggest_mode;
1109       sparseset_clear (live_range_hard_reg_pseudos);
1110       for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1111         {
1112           EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1113             sparseset_set_bit (live_range_hard_reg_pseudos, k);
1114           for (p = r->start + 1; p <= r->finish; p++)
1115             {
1116               lra_live_range_t r2;
1117
1118               for (r2 = start_point_ranges[p];
1119                    r2 != NULL;
1120                    r2 = r2->start_next)
1121                 if (live_pseudos_reg_renumber[r2->regno] >= 0)
1122                   sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
1123             }
1124         }
1125       COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
1126       IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs);
1127       val = lra_reg_info[regno].val;
1128       offset = lra_reg_info[regno].offset;
1129       EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1130         if (!lra_reg_val_equal_p (conflict_regno, val, offset)
1131             /* If it is multi-register pseudos they should start on
1132                the same hard register.  */
1133             || hard_regno != reg_renumber[conflict_regno])
1134           add_to_hard_reg_set (&conflict_set,
1135                                lra_reg_info[conflict_regno].biggest_mode,
1136                                reg_renumber[conflict_regno]);
1137       if (! overlaps_hard_reg_set_p (conflict_set, mode, hard_regno))
1138         {
1139           update_lives (regno, false);
1140           continue;
1141         }
1142       bitmap_set_bit (spilled_pseudo_bitmap, regno);
1143       for (j = 0;
1144            j < hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)];
1145            j++)
1146         lra_hard_reg_usage[hard_regno + j] -= lra_reg_info[regno].freq;
1147       reg_renumber[regno] = -1;
1148       if (regno >= lra_constraint_new_regno_start)
1149         former_reload_pseudo_spill_p = true;
1150       if (lra_dump_file != NULL)
1151         fprintf (lra_dump_file, "    Spill r%d after risky transformations\n",
1152                  regno);
1153     }
1154 }
1155
1156 /* Improve allocation by assigning the same hard regno of inheritance
1157    pseudos to the connected pseudos.  We need this because inheritance
1158    pseudos are allocated after reload pseudos in the thread and when
1159    we assign a hard register to a reload pseudo we don't know yet that
1160    the connected inheritance pseudos can get the same hard register.
1161    Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS.  */
1162 static void
1163 improve_inheritance (bitmap changed_pseudos)
1164 {
1165   unsigned int k;
1166   int regno, another_regno, hard_regno, another_hard_regno, cost, i, n;
1167   lra_copy_t cp, next_cp;
1168   bitmap_iterator bi;
1169
1170   if (lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES)
1171     return;
1172   n = 0;
1173   EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, k, bi)
1174     if (reg_renumber[k] >= 0 && lra_reg_info[k].nrefs != 0)
1175       sorted_pseudos[n++] = k;
1176   qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1177   for (i = 0; i < n; i++)
1178     {
1179       regno = sorted_pseudos[i];
1180       hard_regno = reg_renumber[regno];
1181       lra_assert (hard_regno >= 0);
1182       for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
1183         {
1184           if (cp->regno1 == regno)
1185             {
1186               next_cp = cp->regno1_next;
1187               another_regno = cp->regno2;
1188             }
1189           else if (cp->regno2 == regno)
1190             {
1191               next_cp = cp->regno2_next;
1192               another_regno = cp->regno1;
1193             }
1194           else
1195             gcc_unreachable ();
1196           /* Don't change reload pseudo allocation.  It might have
1197              this allocation for a purpose and changing it can result
1198              in LRA cycling.  */
1199           if ((another_regno < lra_constraint_new_regno_start
1200                || bitmap_bit_p (&lra_inheritance_pseudos, another_regno))
1201               && (another_hard_regno = reg_renumber[another_regno]) >= 0
1202               && another_hard_regno != hard_regno)
1203             {
1204               if (lra_dump_file != NULL)
1205                 fprintf
1206                   (lra_dump_file,
1207                    "    Improving inheritance for %d(%d) and %d(%d)...\n",
1208                    regno, hard_regno, another_regno, another_hard_regno);
1209               update_lives (another_regno, true);
1210               lra_setup_reg_renumber (another_regno, -1, false);
1211               if (hard_regno == find_hard_regno_for (another_regno, &cost,
1212                                                      hard_regno, false))
1213                 assign_hard_regno (hard_regno, another_regno);
1214               else
1215                 assign_hard_regno (another_hard_regno, another_regno);
1216               bitmap_set_bit (changed_pseudos, another_regno);
1217             }
1218         }
1219     }
1220 }
1221
1222
1223 /* Bitmap finally containing all pseudos spilled on this assignment
1224    pass.  */
1225 static bitmap_head all_spilled_pseudos;
1226 /* All pseudos whose allocation was changed.  */
1227 static bitmap_head changed_pseudo_bitmap;
1228
1229
1230 /* Add to LIVE_RANGE_HARD_REG_PSEUDOS all pseudos conflicting with
1231    REGNO and whose hard regs can be assigned to REGNO.  */
1232 static void
1233 find_all_spills_for (int regno)
1234 {
1235   int p;
1236   lra_live_range_t r;
1237   unsigned int k;
1238   bitmap_iterator bi;
1239   enum reg_class rclass;
1240   bool *rclass_intersect_p;
1241
1242   rclass = regno_allocno_class_array[regno];
1243   rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
1244   for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1245     {
1246       EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1247         if (rclass_intersect_p[regno_allocno_class_array[k]])
1248           sparseset_set_bit (live_range_hard_reg_pseudos, k);
1249       for (p = r->start + 1; p <= r->finish; p++)
1250         {
1251           lra_live_range_t r2;
1252
1253           for (r2 = start_point_ranges[p];
1254                r2 != NULL;
1255                r2 = r2->start_next)
1256             {
1257               if (live_pseudos_reg_renumber[r2->regno] >= 0
1258                   && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
1259                 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
1260             }
1261         }
1262     }
1263 }
1264
1265 /* Assign hard registers to reload pseudos and other pseudos.  */
1266 static void
1267 assign_by_spills (void)
1268 {
1269   int i, n, nfails, iter, regno, hard_regno, cost, restore_regno;
1270   rtx_insn *insn;
1271   bitmap_head changed_insns, do_not_assign_nonreload_pseudos;
1272   unsigned int u, conflict_regno;
1273   bitmap_iterator bi;
1274   bool reload_p;
1275   int max_regno = max_reg_num ();
1276
1277   for (n = 0, i = lra_constraint_new_regno_start; i < max_regno; i++)
1278     if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1279         && regno_allocno_class_array[i] != NO_REGS)
1280       sorted_pseudos[n++] = i;
1281   bitmap_initialize (&insn_conflict_pseudos, &reg_obstack);
1282   bitmap_initialize (&spill_pseudos_bitmap, &reg_obstack);
1283   bitmap_initialize (&best_spill_pseudos_bitmap, &reg_obstack);
1284   update_hard_regno_preference_check = XCNEWVEC (int, max_regno);
1285   curr_update_hard_regno_preference_check = 0;
1286   memset (try_hard_reg_pseudos_check, 0, sizeof (try_hard_reg_pseudos_check));
1287   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1288     bitmap_initialize (&try_hard_reg_pseudos[i], &reg_obstack);
1289   curr_pseudo_check = 0;
1290   bitmap_initialize (&changed_insns, &reg_obstack);
1291   bitmap_initialize (&non_reload_pseudos, &reg_obstack);
1292   bitmap_ior (&non_reload_pseudos, &lra_inheritance_pseudos, &lra_split_regs);
1293   bitmap_ior_into (&non_reload_pseudos, &lra_subreg_reload_pseudos);
1294   bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos);
1295   for (iter = 0; iter <= 1; iter++)
1296     {
1297       qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func);
1298       nfails = 0;
1299       for (i = 0; i < n; i++)
1300         {
1301           regno = sorted_pseudos[i];
1302           if (lra_dump_file != NULL)
1303             fprintf (lra_dump_file, "    Assigning to %d "
1304                      "(cl=%s, orig=%d, freq=%d, tfirst=%d, tfreq=%d)...\n",
1305                      regno, reg_class_names[regno_allocno_class_array[regno]],
1306                      ORIGINAL_REGNO (regno_reg_rtx[regno]),
1307                      lra_reg_info[regno].freq, regno_assign_info[regno].first,
1308                      regno_assign_info[regno_assign_info[regno].first].freq);
1309           hard_regno = find_hard_regno_for (regno, &cost, -1, iter == 1);
1310           reload_p = ! bitmap_bit_p (&non_reload_pseudos, regno);
1311           if (hard_regno < 0 && reload_p)
1312             hard_regno = spill_for (regno, &all_spilled_pseudos, iter == 1);
1313           if (hard_regno < 0)
1314             {
1315               if (reload_p)
1316                 sorted_pseudos[nfails++] = regno;
1317             }
1318           else
1319             {
1320               /* This register might have been spilled by the previous
1321                  pass.  Indicate that it is no longer spilled.  */
1322               bitmap_clear_bit (&all_spilled_pseudos, regno);
1323               assign_hard_regno (hard_regno, regno);
1324               if (! reload_p)
1325                 /* As non-reload pseudo assignment is changed we
1326                    should reconsider insns referring for the
1327                    pseudo.  */
1328                 bitmap_set_bit (&changed_pseudo_bitmap, regno);
1329             }
1330         }
1331       if (nfails == 0)
1332         break;
1333       if (iter > 0)
1334         {
1335           /* We did not assign hard regs to reload pseudos after two iterations.
1336              Either it's an asm and something is wrong with the constraints, or
1337              we have run out of spill registers; error out in either case.  */
1338           bool asm_p = false;
1339           bitmap_head failed_reload_insns;
1340
1341           bitmap_initialize (&failed_reload_insns, &reg_obstack);
1342           for (i = 0; i < nfails; i++)
1343             {
1344               regno = sorted_pseudos[i];
1345               bitmap_ior_into (&failed_reload_insns,
1346                                &lra_reg_info[regno].insn_bitmap);
1347               /* Assign an arbitrary hard register of regno class to
1348                  avoid further trouble with this insn.  */
1349               bitmap_clear_bit (&all_spilled_pseudos, regno);
1350               assign_hard_regno
1351                 (ira_class_hard_regs[regno_allocno_class_array[regno]][0],
1352                  regno);
1353             }
1354           EXECUTE_IF_SET_IN_BITMAP (&failed_reload_insns, 0, u, bi)
1355             {
1356               insn = lra_insn_recog_data[u]->insn;
1357               if (asm_noperands (PATTERN (insn)) >= 0)
1358                 {
1359                   asm_p = true;
1360                   error_for_asm (insn,
1361                                  "%<asm%> operand has impossible constraints");
1362                   /* Avoid further trouble with this insn.
1363                      For asm goto, instead of fixing up all the edges
1364                      just clear the template and clear input operands
1365                      (asm goto doesn't have any output operands).  */
1366                   if (JUMP_P (insn))
1367                     {
1368                       rtx asm_op = extract_asm_operands (PATTERN (insn));
1369                       ASM_OPERANDS_TEMPLATE (asm_op) = ggc_strdup ("");
1370                       ASM_OPERANDS_INPUT_VEC (asm_op) = rtvec_alloc (0);
1371                       ASM_OPERANDS_INPUT_CONSTRAINT_VEC (asm_op) = rtvec_alloc (0);
1372                       lra_update_insn_regno_info (insn);
1373                     }
1374                   else
1375                     {
1376                       PATTERN (insn) = gen_rtx_USE (VOIDmode, const0_rtx);
1377                       lra_set_insn_deleted (insn);
1378                     }
1379                 }
1380               else if (!asm_p)
1381                 {
1382                   error ("unable to find a register to spill");
1383                   fatal_insn ("this is the insn:", insn);
1384                 }
1385             }
1386           break;
1387         }
1388       /* This is a very rare event.  We can not assign a hard register
1389          to reload pseudo because the hard register was assigned to
1390          another reload pseudo on a previous assignment pass.  For x86
1391          example, on the 1st pass we assigned CX (although another
1392          hard register could be used for this) to reload pseudo in an
1393          insn, on the 2nd pass we need CX (and only this) hard
1394          register for a new reload pseudo in the same insn.  Another
1395          possible situation may occur in assigning to multi-regs
1396          reload pseudos when hard regs pool is too fragmented even
1397          after spilling non-reload pseudos.
1398
1399          We should do something radical here to succeed.  Here we
1400          spill *all* conflicting pseudos and reassign them.  */
1401       if (lra_dump_file != NULL)
1402         fprintf (lra_dump_file, "  2nd iter for reload pseudo assignments:\n");
1403       sparseset_clear (live_range_hard_reg_pseudos);
1404       for (i = 0; i < nfails; i++)
1405         {
1406           if (lra_dump_file != NULL)
1407             fprintf (lra_dump_file, "    Reload r%d assignment failure\n",
1408                      sorted_pseudos[i]);
1409           find_all_spills_for (sorted_pseudos[i]);
1410         }
1411       EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1412         {
1413           if ((int) conflict_regno >= lra_constraint_new_regno_start)
1414             {
1415               sorted_pseudos[nfails++] = conflict_regno;
1416               former_reload_pseudo_spill_p = true;
1417             }
1418           if (lra_dump_file != NULL)
1419             fprintf (lra_dump_file, "     Spill %s r%d(hr=%d, freq=%d)\n",
1420                      pseudo_prefix_title (conflict_regno), conflict_regno,
1421                      reg_renumber[conflict_regno],
1422                      lra_reg_info[conflict_regno].freq);
1423           update_lives (conflict_regno, true);
1424           lra_setup_reg_renumber (conflict_regno, -1, false);
1425         }
1426       n = nfails;
1427     }
1428   improve_inheritance (&changed_pseudo_bitmap);
1429   bitmap_clear (&non_reload_pseudos);
1430   bitmap_clear (&changed_insns);
1431   if (! lra_simple_p)
1432     {
1433       /* We should not assign to original pseudos of inheritance
1434          pseudos or split pseudos if any its inheritance pseudo did
1435          not get hard register or any its split pseudo was not split
1436          because undo inheritance/split pass will extend live range of
1437          such inheritance or split pseudos.  */
1438       bitmap_initialize (&do_not_assign_nonreload_pseudos, &reg_obstack);
1439       EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, u, bi)
1440         if ((restore_regno = lra_reg_info[u].restore_regno) >= 0
1441             && reg_renumber[u] < 0
1442             && bitmap_bit_p (&lra_inheritance_pseudos, u))
1443           bitmap_set_bit (&do_not_assign_nonreload_pseudos, restore_regno);
1444       EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, u, bi)
1445         if ((restore_regno = lra_reg_info[u].restore_regno) >= 0
1446             && reg_renumber[u] >= 0)
1447           bitmap_set_bit (&do_not_assign_nonreload_pseudos, restore_regno);
1448       for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1449         if (((i < lra_constraint_new_regno_start
1450               && ! bitmap_bit_p (&do_not_assign_nonreload_pseudos, i))
1451              || (bitmap_bit_p (&lra_inheritance_pseudos, i)
1452                  && lra_reg_info[i].restore_regno >= 0)
1453              || (bitmap_bit_p (&lra_split_regs, i)
1454                  && lra_reg_info[i].restore_regno >= 0)
1455              || bitmap_bit_p (&lra_subreg_reload_pseudos, i)
1456              || bitmap_bit_p (&lra_optional_reload_pseudos, i))
1457             && reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1458             && regno_allocno_class_array[i] != NO_REGS)
1459           sorted_pseudos[n++] = i;
1460       bitmap_clear (&do_not_assign_nonreload_pseudos);
1461       if (n != 0 && lra_dump_file != NULL)
1462         fprintf (lra_dump_file, "  Reassigning non-reload pseudos\n");
1463       qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1464       for (i = 0; i < n; i++)
1465         {
1466           regno = sorted_pseudos[i];
1467           hard_regno = find_hard_regno_for (regno, &cost, -1, false);
1468           if (hard_regno >= 0)
1469             {
1470               assign_hard_regno (hard_regno, regno);
1471               /* We change allocation for non-reload pseudo on this
1472                  iteration -- mark the pseudo for invalidation of used
1473                  alternatives of insns containing the pseudo.  */
1474               bitmap_set_bit (&changed_pseudo_bitmap, regno);
1475             }
1476           else
1477             {
1478               enum reg_class rclass = lra_get_allocno_class (regno);
1479               enum reg_class spill_class;
1480               
1481               if (targetm.spill_class == NULL
1482                   || lra_reg_info[regno].restore_regno < 0
1483                   || ! bitmap_bit_p (&lra_inheritance_pseudos, regno)
1484                   || (spill_class
1485                       = ((enum reg_class)
1486                          targetm.spill_class
1487                          ((reg_class_t) rclass,
1488                           PSEUDO_REGNO_MODE (regno)))) == NO_REGS)
1489                 continue;
1490               regno_allocno_class_array[regno] = spill_class;
1491               hard_regno = find_hard_regno_for (regno, &cost, -1, false);
1492               if (hard_regno < 0)
1493                 regno_allocno_class_array[regno] = rclass;
1494               else
1495                 {
1496                   setup_reg_classes
1497                     (regno, spill_class, spill_class, spill_class);
1498                   assign_hard_regno (hard_regno, regno);
1499                   bitmap_set_bit (&changed_pseudo_bitmap, regno);
1500                 }
1501             }
1502         }
1503     }
1504   free (update_hard_regno_preference_check);
1505   bitmap_clear (&best_spill_pseudos_bitmap);
1506   bitmap_clear (&spill_pseudos_bitmap);
1507   bitmap_clear (&insn_conflict_pseudos);
1508 }
1509
1510
1511 /* Entry function to assign hard registers to new reload pseudos
1512    starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling
1513    of old pseudos) and possibly to the old pseudos.  The function adds
1514    what insns to process for the next constraint pass.  Those are all
1515    insns who contains non-reload and non-inheritance pseudos with
1516    changed allocation.
1517
1518    Return true if we did not spill any non-reload and non-inheritance
1519    pseudos.  */
1520 bool
1521 lra_assign (void)
1522 {
1523   int i;
1524   unsigned int u;
1525   bitmap_iterator bi;
1526   bitmap_head insns_to_process;
1527   bool no_spills_p;
1528   int max_regno = max_reg_num ();
1529
1530   timevar_push (TV_LRA_ASSIGN);
1531   lra_assignment_iter++;
1532   if (lra_dump_file != NULL)
1533     fprintf (lra_dump_file, "\n********** Assignment #%d: **********\n\n",
1534              lra_assignment_iter);
1535   init_lives ();
1536   sorted_pseudos = XNEWVEC (int, max_regno);
1537   sorted_reload_pseudos = XNEWVEC (int, max_regno);
1538   regno_allocno_class_array = XNEWVEC (enum reg_class, max_regno);
1539   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1540     regno_allocno_class_array[i] = lra_get_allocno_class (i);
1541   former_reload_pseudo_spill_p = false;
1542   init_regno_assign_info ();
1543   bitmap_initialize (&all_spilled_pseudos, &reg_obstack);
1544   create_live_range_start_chains ();
1545   setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos);
1546 #ifdef ENABLE_CHECKING
1547   if (!flag_ipa_ra)
1548     for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1549       if (lra_reg_info[i].nrefs != 0 && reg_renumber[i] >= 0
1550           && lra_reg_info[i].call_p
1551           && overlaps_hard_reg_set_p (call_used_reg_set,
1552                                       PSEUDO_REGNO_MODE (i), reg_renumber[i]))
1553         gcc_unreachable ();
1554 #endif
1555   /* Setup insns to process on the next constraint pass.  */
1556   bitmap_initialize (&changed_pseudo_bitmap, &reg_obstack);
1557   init_live_reload_and_inheritance_pseudos ();
1558   assign_by_spills ();
1559   finish_live_reload_and_inheritance_pseudos ();
1560   bitmap_ior_into (&changed_pseudo_bitmap, &all_spilled_pseudos);
1561   no_spills_p = true;
1562   EXECUTE_IF_SET_IN_BITMAP (&all_spilled_pseudos, 0, u, bi)
1563     /* We ignore spilled pseudos created on last inheritance pass
1564        because they will be removed.  */
1565     if (lra_reg_info[u].restore_regno < 0)
1566       {
1567         no_spills_p = false;
1568         break;
1569       }
1570   finish_live_range_start_chains ();
1571   bitmap_clear (&all_spilled_pseudos);
1572   bitmap_initialize (&insns_to_process, &reg_obstack);
1573   EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap, 0, u, bi)
1574     bitmap_ior_into (&insns_to_process, &lra_reg_info[u].insn_bitmap);
1575   bitmap_clear (&changed_pseudo_bitmap);
1576   EXECUTE_IF_SET_IN_BITMAP (&insns_to_process, 0, u, bi)
1577     {
1578       lra_push_insn_by_uid (u);
1579       /* Invalidate alternatives for insn should be processed.  */
1580       lra_set_used_insn_alternative_by_uid (u, -1);
1581     }
1582   bitmap_clear (&insns_to_process);
1583   finish_regno_assign_info ();
1584   free (regno_allocno_class_array);
1585   free (sorted_pseudos);
1586   free (sorted_reload_pseudos);
1587   finish_lives ();
1588   timevar_pop (TV_LRA_ASSIGN);
1589   if (former_reload_pseudo_spill_p)
1590     lra_assignment_iter_after_spill++;
1591   if (lra_assignment_iter_after_spill > LRA_MAX_ASSIGNMENT_ITERATION_NUMBER)
1592     internal_error
1593       ("Maximum number of LRA assignment passes is achieved (%d)\n",
1594        LRA_MAX_ASSIGNMENT_ITERATION_NUMBER);
1595   return no_spills_p;
1596 }