1 /* Assign reload pseudos.
2 Copyright (C) 2010-2014 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
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
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
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/>. */
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.
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.
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
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.
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.
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
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.
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.
64 Only insns with changed allocation pseudos are processed on the
67 The pseudo live-ranges are used to find conflicting pseudos.
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
79 #include "coretypes.h"
81 #include "hard-reg-set.h"
83 #include "rtl-error.h"
86 #include "insn-config.h"
92 #include "basic-block.h"
96 #include "sparseset.h"
100 /* Current iteration number of the pass and current iteration number
101 of the pass after the latest spill pass when any former reload
102 pseudo was spilled. */
103 int lra_assignment_iter
;
104 int lra_assignment_iter_after_spill
;
106 /* Flag of spilling former reload pseudos on this pass. */
107 static bool former_reload_pseudo_spill_p
;
109 /* Array containing corresponding values of function
110 lra_get_allocno_class. It is used to speed up the code. */
111 static enum reg_class
*regno_allocno_class_array
;
113 /* Information about the thread to which a pseudo belongs. Threads are
114 a set of connected reload and inheritance pseudos with the same set of
115 available hard registers. Lone registers belong to their own threads. */
116 struct regno_assign_info
118 /* First/next pseudo of the same thread. */
120 /* Frequency of the thread (execution frequency of only reload
121 pseudos in the thread when the thread contains a reload pseudo).
122 Defined only for the first thread pseudo. */
126 /* Map regno to the corresponding regno assignment info. */
127 static struct regno_assign_info
*regno_assign_info
;
129 /* All inherited, subreg or optional pseudos created before last spill
130 sub-pass. Such pseudos are permitted to get memory instead of hard
132 static bitmap_head non_reload_pseudos
;
134 /* Process a pseudo copy with execution frequency COPY_FREQ connecting
135 REGNO1 and REGNO2 to form threads. */
137 process_copy_to_form_thread (int regno1
, int regno2
, int copy_freq
)
139 int last
, regno1_first
, regno2_first
;
141 lra_assert (regno1
>= lra_constraint_new_regno_start
142 && regno2
>= lra_constraint_new_regno_start
);
143 regno1_first
= regno_assign_info
[regno1
].first
;
144 regno2_first
= regno_assign_info
[regno2
].first
;
145 if (regno1_first
!= regno2_first
)
147 for (last
= regno2_first
;
148 regno_assign_info
[last
].next
>= 0;
149 last
= regno_assign_info
[last
].next
)
150 regno_assign_info
[last
].first
= regno1_first
;
151 regno_assign_info
[last
].first
= regno1_first
;
152 regno_assign_info
[last
].next
= regno_assign_info
[regno1_first
].next
;
153 regno_assign_info
[regno1_first
].next
= regno2_first
;
154 regno_assign_info
[regno1_first
].freq
155 += regno_assign_info
[regno2_first
].freq
;
157 regno_assign_info
[regno1_first
].freq
-= 2 * copy_freq
;
158 lra_assert (regno_assign_info
[regno1_first
].freq
>= 0);
161 /* Initialize REGNO_ASSIGN_INFO and form threads. */
163 init_regno_assign_info (void)
165 int i
, regno1
, regno2
, max_regno
= max_reg_num ();
168 regno_assign_info
= XNEWVEC (struct regno_assign_info
, max_regno
);
169 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
171 regno_assign_info
[i
].first
= i
;
172 regno_assign_info
[i
].next
= -1;
173 regno_assign_info
[i
].freq
= lra_reg_info
[i
].freq
;
175 /* Form the threads. */
176 for (i
= 0; (cp
= lra_get_copy (i
)) != NULL
; i
++)
177 if ((regno1
= cp
->regno1
) >= lra_constraint_new_regno_start
178 && (regno2
= cp
->regno2
) >= lra_constraint_new_regno_start
179 && reg_renumber
[regno1
] < 0 && lra_reg_info
[regno1
].nrefs
!= 0
180 && reg_renumber
[regno2
] < 0 && lra_reg_info
[regno2
].nrefs
!= 0
181 && (ira_class_hard_regs_num
[regno_allocno_class_array
[regno1
]]
182 == ira_class_hard_regs_num
[regno_allocno_class_array
[regno2
]]))
183 process_copy_to_form_thread (regno1
, regno2
, cp
->freq
);
186 /* Free REGNO_ASSIGN_INFO. */
188 finish_regno_assign_info (void)
190 free (regno_assign_info
);
193 /* The function is used to sort *reload* and *inheritance* pseudos to
194 try to assign them hard registers. We put pseudos from the same
195 thread always nearby. */
197 reload_pseudo_compare_func (const void *v1p
, const void *v2p
)
199 int r1
= *(const int *) v1p
, r2
= *(const int *) v2p
;
200 enum reg_class cl1
= regno_allocno_class_array
[r1
];
201 enum reg_class cl2
= regno_allocno_class_array
[r2
];
204 lra_assert (r1
>= lra_constraint_new_regno_start
205 && r2
>= lra_constraint_new_regno_start
);
207 /* Prefer to assign reload registers with smaller classes first to
208 guarantee assignment to all reload registers. */
209 if ((diff
= (ira_class_hard_regs_num
[cl1
]
210 - ira_class_hard_regs_num
[cl2
])) != 0)
213 = (ira_reg_class_max_nregs
[cl2
][lra_reg_info
[r2
].biggest_mode
]
214 - ira_reg_class_max_nregs
[cl1
][lra_reg_info
[r1
].biggest_mode
])) != 0
215 /* The code below executes rarely as nregs == 1 in most cases.
216 So we should not worry about using faster data structures to
217 check reload pseudos. */
218 && ! bitmap_bit_p (&non_reload_pseudos
, r1
)
219 && ! bitmap_bit_p (&non_reload_pseudos
, r2
))
221 if ((diff
= (regno_assign_info
[regno_assign_info
[r2
].first
].freq
222 - regno_assign_info
[regno_assign_info
[r1
].first
].freq
)) != 0)
224 /* Allocate bigger pseudos first to avoid register file
227 = (ira_reg_class_max_nregs
[cl2
][lra_reg_info
[r2
].biggest_mode
]
228 - ira_reg_class_max_nregs
[cl1
][lra_reg_info
[r1
].biggest_mode
])) != 0)
230 /* Put pseudos from the thread nearby. */
231 if ((diff
= regno_assign_info
[r1
].first
- regno_assign_info
[r2
].first
) != 0)
233 /* If regs are equally good, sort by their numbers, so that the
234 results of qsort leave nothing to chance. */
238 /* The function is used to sort *non-reload* pseudos to try to assign
239 them hard registers. The order calculation is simpler than in the
240 previous function and based on the pseudo frequency usage. */
242 pseudo_compare_func (const void *v1p
, const void *v2p
)
244 int r1
= *(const int *) v1p
, r2
= *(const int *) v2p
;
247 /* Prefer to assign more frequently used registers first. */
248 if ((diff
= lra_reg_info
[r2
].freq
- lra_reg_info
[r1
].freq
) != 0)
251 /* If regs are equally good, sort by their numbers, so that the
252 results of qsort leave nothing to chance. */
256 /* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the
257 pseudo live ranges with given start point. We insert only live
258 ranges of pseudos interesting for assignment purposes. They are
259 reload pseudos and pseudos assigned to hard registers. */
260 static lra_live_range_t
*start_point_ranges
;
262 /* Used as a flag that a live range is not inserted in the start point
264 static struct lra_live_range not_in_chain_mark
;
266 /* Create and set up START_POINT_RANGES. */
268 create_live_range_start_chains (void)
273 start_point_ranges
= XCNEWVEC (lra_live_range_t
, lra_live_max_point
);
274 max_regno
= max_reg_num ();
275 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
276 if (i
>= lra_constraint_new_regno_start
|| reg_renumber
[i
] >= 0)
278 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
280 r
->start_next
= start_point_ranges
[r
->start
];
281 start_point_ranges
[r
->start
] = r
;
286 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
287 r
->start_next
= ¬_in_chain_mark
;
291 /* Insert live ranges of pseudo REGNO into start chains if they are
294 insert_in_live_range_start_chain (int regno
)
296 lra_live_range_t r
= lra_reg_info
[regno
].live_ranges
;
298 if (r
->start_next
!= ¬_in_chain_mark
)
300 for (; r
!= NULL
; r
= r
->next
)
302 r
->start_next
= start_point_ranges
[r
->start
];
303 start_point_ranges
[r
->start
] = r
;
307 /* Free START_POINT_RANGES. */
309 finish_live_range_start_chains (void)
311 gcc_assert (start_point_ranges
!= NULL
);
312 free (start_point_ranges
);
313 start_point_ranges
= NULL
;
316 /* Map: program point -> bitmap of all pseudos living at the point and
317 assigned to hard registers. */
318 static bitmap_head
*live_hard_reg_pseudos
;
319 static bitmap_obstack live_hard_reg_pseudos_bitmap_obstack
;
321 /* reg_renumber corresponding to pseudos marked in
322 live_hard_reg_pseudos. reg_renumber might be not matched to
323 live_hard_reg_pseudos but live_pseudos_reg_renumber always reflects
324 live_hard_reg_pseudos. */
325 static int *live_pseudos_reg_renumber
;
327 /* Sparseset used to calculate living hard reg pseudos for some program
329 static sparseset live_range_hard_reg_pseudos
;
331 /* Sparseset used to calculate living reload/inheritance pseudos for
332 some program point range. */
333 static sparseset live_range_reload_inheritance_pseudos
;
335 /* Allocate and initialize the data about living pseudos at program
340 int i
, max_regno
= max_reg_num ();
342 live_range_hard_reg_pseudos
= sparseset_alloc (max_regno
);
343 live_range_reload_inheritance_pseudos
= sparseset_alloc (max_regno
);
344 live_hard_reg_pseudos
= XNEWVEC (bitmap_head
, lra_live_max_point
);
345 bitmap_obstack_initialize (&live_hard_reg_pseudos_bitmap_obstack
);
346 for (i
= 0; i
< lra_live_max_point
; i
++)
347 bitmap_initialize (&live_hard_reg_pseudos
[i
],
348 &live_hard_reg_pseudos_bitmap_obstack
);
349 live_pseudos_reg_renumber
= XNEWVEC (int, max_regno
);
350 for (i
= 0; i
< max_regno
; i
++)
351 live_pseudos_reg_renumber
[i
] = -1;
354 /* Free the data about living pseudos at program points. */
358 sparseset_free (live_range_hard_reg_pseudos
);
359 sparseset_free (live_range_reload_inheritance_pseudos
);
360 free (live_hard_reg_pseudos
);
361 bitmap_obstack_release (&live_hard_reg_pseudos_bitmap_obstack
);
362 free (live_pseudos_reg_renumber
);
365 /* Update the LIVE_HARD_REG_PSEUDOS and LIVE_PSEUDOS_REG_RENUMBER
366 entries for pseudo REGNO. Assume that the register has been
367 spilled if FREE_P, otherwise assume that it has been assigned
368 reg_renumber[REGNO] (if >= 0). We also insert the pseudo live
369 ranges in the start chains when it is assumed to be assigned to a
370 hard register because we use the chains of pseudos assigned to hard
371 registers during allocation. */
373 update_lives (int regno
, bool free_p
)
378 if (reg_renumber
[regno
] < 0)
380 live_pseudos_reg_renumber
[regno
] = free_p
? -1 : reg_renumber
[regno
];
381 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
383 for (p
= r
->start
; p
<= r
->finish
; p
++)
385 bitmap_clear_bit (&live_hard_reg_pseudos
[p
], regno
);
388 bitmap_set_bit (&live_hard_reg_pseudos
[p
], regno
);
389 insert_in_live_range_start_chain (regno
);
394 /* Sparseset used to calculate reload pseudos conflicting with a given
395 pseudo when we are trying to find a hard register for the given
397 static sparseset conflict_reload_and_inheritance_pseudos
;
399 /* Map: program point -> bitmap of all reload and inheritance pseudos
400 living at the point. */
401 static bitmap_head
*live_reload_and_inheritance_pseudos
;
402 static bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack
;
404 /* Allocate and initialize data about living reload pseudos at any
405 given program point. */
407 init_live_reload_and_inheritance_pseudos (void)
409 int i
, p
, max_regno
= max_reg_num ();
412 conflict_reload_and_inheritance_pseudos
= sparseset_alloc (max_regno
);
413 live_reload_and_inheritance_pseudos
= XNEWVEC (bitmap_head
, lra_live_max_point
);
414 bitmap_obstack_initialize (&live_reload_and_inheritance_pseudos_bitmap_obstack
);
415 for (p
= 0; p
< lra_live_max_point
; p
++)
416 bitmap_initialize (&live_reload_and_inheritance_pseudos
[p
],
417 &live_reload_and_inheritance_pseudos_bitmap_obstack
);
418 for (i
= lra_constraint_new_regno_start
; i
< max_regno
; i
++)
420 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
421 for (p
= r
->start
; p
<= r
->finish
; p
++)
422 bitmap_set_bit (&live_reload_and_inheritance_pseudos
[p
], i
);
426 /* Finalize data about living reload pseudos at any given program
429 finish_live_reload_and_inheritance_pseudos (void)
431 sparseset_free (conflict_reload_and_inheritance_pseudos
);
432 free (live_reload_and_inheritance_pseudos
);
433 bitmap_obstack_release (&live_reload_and_inheritance_pseudos_bitmap_obstack
);
436 /* The value used to check that cost of given hard reg is really
437 defined currently. */
438 static int curr_hard_regno_costs_check
= 0;
439 /* Array used to check that cost of the corresponding hard reg (the
440 array element index) is really defined currently. */
441 static int hard_regno_costs_check
[FIRST_PSEUDO_REGISTER
];
442 /* The current costs of allocation of hard regs. Defined only if the
443 value of the corresponding element of the previous array is equal to
444 CURR_HARD_REGNO_COSTS_CHECK. */
445 static int hard_regno_costs
[FIRST_PSEUDO_REGISTER
];
447 /* Adjust cost of HARD_REGNO by INCR. Reset the cost first if it is
450 adjust_hard_regno_cost (int hard_regno
, int incr
)
452 if (hard_regno_costs_check
[hard_regno
] != curr_hard_regno_costs_check
)
453 hard_regno_costs
[hard_regno
] = 0;
454 hard_regno_costs_check
[hard_regno
] = curr_hard_regno_costs_check
;
455 hard_regno_costs
[hard_regno
] += incr
;
458 /* Try to find a free hard register for pseudo REGNO. Return the
459 hard register on success and set *COST to the cost of using
460 that register. (If several registers have equal cost, the one with
461 the highest priority wins.) Return -1 on failure.
463 If FIRST_P, return the first available hard reg ignoring other
464 criteria, e.g. allocation cost. This approach results in less hard
465 reg pool fragmentation and permit to allocate hard regs to reload
466 pseudos in complicated situations where pseudo sizes are different.
468 If TRY_ONLY_HARD_REGNO >= 0, consider only that hard register,
469 otherwise consider all hard registers in REGNO's class. */
471 find_hard_regno_for (int regno
, int *cost
, int try_only_hard_regno
,
474 HARD_REG_SET conflict_set
;
475 int best_cost
= INT_MAX
, best_priority
= INT_MIN
, best_usage
= INT_MAX
;
477 int p
, i
, j
, rclass_size
, best_hard_regno
, priority
, hard_regno
;
478 int hr
, conflict_hr
, nregs
;
479 enum machine_mode biggest_mode
;
480 unsigned int k
, conflict_regno
;
481 int offset
, val
, biggest_nregs
, nregs_diff
;
482 enum reg_class rclass
;
484 bool *rclass_intersect_p
;
485 HARD_REG_SET impossible_start_hard_regs
, available_regs
;
487 COPY_HARD_REG_SET (conflict_set
, lra_no_alloc_regs
);
488 rclass
= regno_allocno_class_array
[regno
];
489 rclass_intersect_p
= ira_reg_classes_intersect_p
[rclass
];
490 curr_hard_regno_costs_check
++;
491 sparseset_clear (conflict_reload_and_inheritance_pseudos
);
492 sparseset_clear (live_range_hard_reg_pseudos
);
493 IOR_HARD_REG_SET (conflict_set
, lra_reg_info
[regno
].conflict_hard_regs
);
494 biggest_mode
= lra_reg_info
[regno
].biggest_mode
;
495 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
497 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos
[r
->start
], 0, k
, bi
)
498 if (rclass_intersect_p
[regno_allocno_class_array
[k
]])
499 sparseset_set_bit (live_range_hard_reg_pseudos
, k
);
500 EXECUTE_IF_SET_IN_BITMAP (&live_reload_and_inheritance_pseudos
[r
->start
],
502 if (lra_reg_info
[k
].preferred_hard_regno1
>= 0
503 && live_pseudos_reg_renumber
[k
] < 0
504 && rclass_intersect_p
[regno_allocno_class_array
[k
]])
505 sparseset_set_bit (conflict_reload_and_inheritance_pseudos
, k
);
506 for (p
= r
->start
+ 1; p
<= r
->finish
; p
++)
510 for (r2
= start_point_ranges
[p
];
514 if (r2
->regno
>= lra_constraint_new_regno_start
515 && lra_reg_info
[r2
->regno
].preferred_hard_regno1
>= 0
516 && live_pseudos_reg_renumber
[r2
->regno
] < 0
517 && rclass_intersect_p
[regno_allocno_class_array
[r2
->regno
]])
518 sparseset_set_bit (conflict_reload_and_inheritance_pseudos
,
520 if (live_pseudos_reg_renumber
[r2
->regno
] >= 0
521 && rclass_intersect_p
[regno_allocno_class_array
[r2
->regno
]])
522 sparseset_set_bit (live_range_hard_reg_pseudos
, r2
->regno
);
526 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno1
) >= 0)
528 adjust_hard_regno_cost
529 (hard_regno
, -lra_reg_info
[regno
].preferred_hard_regno_profit1
);
530 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno2
) >= 0)
531 adjust_hard_regno_cost
532 (hard_regno
, -lra_reg_info
[regno
].preferred_hard_regno_profit2
);
535 if (lra_reg_info
[regno
].no_stack_p
)
536 for (i
= FIRST_STACK_REG
; i
<= LAST_STACK_REG
; i
++)
537 SET_HARD_REG_BIT (conflict_set
, i
);
539 sparseset_clear_bit (conflict_reload_and_inheritance_pseudos
, regno
);
540 val
= lra_reg_info
[regno
].val
;
541 offset
= lra_reg_info
[regno
].offset
;
542 CLEAR_HARD_REG_SET (impossible_start_hard_regs
);
543 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos
, conflict_regno
)
544 if (lra_reg_val_equal_p (conflict_regno
, val
, offset
))
546 conflict_hr
= live_pseudos_reg_renumber
[conflict_regno
];
547 nregs
= (hard_regno_nregs
[conflict_hr
]
548 [lra_reg_info
[conflict_regno
].biggest_mode
]);
549 /* Remember about multi-register pseudos. For example, 2 hard
550 register pseudos can start on the same hard register but can
551 not start on HR and HR+1/HR-1. */
552 for (hr
= conflict_hr
+ 1;
553 hr
< FIRST_PSEUDO_REGISTER
&& hr
< conflict_hr
+ nregs
;
555 SET_HARD_REG_BIT (impossible_start_hard_regs
, hr
);
556 for (hr
= conflict_hr
- 1;
557 hr
>= 0 && hr
+ hard_regno_nregs
[hr
][biggest_mode
] > conflict_hr
;
559 SET_HARD_REG_BIT (impossible_start_hard_regs
, hr
);
563 add_to_hard_reg_set (&conflict_set
,
564 lra_reg_info
[conflict_regno
].biggest_mode
,
565 live_pseudos_reg_renumber
[conflict_regno
]);
566 if (hard_reg_set_subset_p (reg_class_contents
[rclass
],
570 EXECUTE_IF_SET_IN_SPARSESET (conflict_reload_and_inheritance_pseudos
,
572 if (!lra_reg_val_equal_p (conflict_regno
, val
, offset
))
574 lra_assert (live_pseudos_reg_renumber
[conflict_regno
] < 0);
576 = lra_reg_info
[conflict_regno
].preferred_hard_regno1
) >= 0)
578 adjust_hard_regno_cost
580 lra_reg_info
[conflict_regno
].preferred_hard_regno_profit1
);
582 = lra_reg_info
[conflict_regno
].preferred_hard_regno2
) >= 0)
583 adjust_hard_regno_cost
585 lra_reg_info
[conflict_regno
].preferred_hard_regno_profit2
);
588 /* Make sure that all registers in a multi-word pseudo belong to the
590 IOR_COMPL_HARD_REG_SET (conflict_set
, reg_class_contents
[rclass
]);
591 lra_assert (rclass
!= NO_REGS
);
592 rclass_size
= ira_class_hard_regs_num
[rclass
];
593 best_hard_regno
= -1;
594 hard_regno
= ira_class_hard_regs
[rclass
][0];
595 biggest_nregs
= hard_regno_nregs
[hard_regno
][biggest_mode
];
596 nregs_diff
= (biggest_nregs
597 - hard_regno_nregs
[hard_regno
][PSEUDO_REGNO_MODE (regno
)]);
598 COPY_HARD_REG_SET (available_regs
, reg_class_contents
[rclass
]);
599 AND_COMPL_HARD_REG_SET (available_regs
, lra_no_alloc_regs
);
600 for (i
= 0; i
< rclass_size
; i
++)
602 if (try_only_hard_regno
>= 0)
603 hard_regno
= try_only_hard_regno
;
605 hard_regno
= ira_class_hard_regs
[rclass
][i
];
606 if (! overlaps_hard_reg_set_p (conflict_set
,
607 PSEUDO_REGNO_MODE (regno
), hard_regno
)
608 /* We can not use prohibited_class_mode_regs because it is
609 not defined for all classes. */
610 && HARD_REGNO_MODE_OK (hard_regno
, PSEUDO_REGNO_MODE (regno
))
611 && ! TEST_HARD_REG_BIT (impossible_start_hard_regs
, hard_regno
)
614 ? (hard_regno
- nregs_diff
>= 0
615 && TEST_HARD_REG_BIT (available_regs
,
616 hard_regno
- nregs_diff
))
617 : TEST_HARD_REG_BIT (available_regs
,
618 hard_regno
+ nregs_diff
))))
620 if (hard_regno_costs_check
[hard_regno
]
621 != curr_hard_regno_costs_check
)
623 hard_regno_costs_check
[hard_regno
] = curr_hard_regno_costs_check
;
624 hard_regno_costs
[hard_regno
] = 0;
627 j
< hard_regno_nregs
[hard_regno
][PSEUDO_REGNO_MODE (regno
)];
629 if (! TEST_HARD_REG_BIT (call_used_reg_set
, hard_regno
+ j
)
630 && ! df_regs_ever_live_p (hard_regno
+ j
))
631 /* It needs save restore. */
632 hard_regno_costs
[hard_regno
]
634 * REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
)
636 priority
= targetm
.register_priority (hard_regno
);
637 if (best_hard_regno
< 0 || hard_regno_costs
[hard_regno
] < best_cost
638 || (hard_regno_costs
[hard_regno
] == best_cost
639 && (priority
> best_priority
640 || (targetm
.register_usage_leveling_p ()
641 && priority
== best_priority
642 && best_usage
> lra_hard_reg_usage
[hard_regno
]))))
644 best_hard_regno
= hard_regno
;
645 best_cost
= hard_regno_costs
[hard_regno
];
646 best_priority
= priority
;
647 best_usage
= lra_hard_reg_usage
[hard_regno
];
650 if (try_only_hard_regno
>= 0 || (first_p
&& best_hard_regno
>= 0))
653 if (best_hard_regno
>= 0)
654 *cost
= best_cost
- lra_reg_info
[regno
].freq
;
655 return best_hard_regno
;
658 /* Current value used for checking elements in
659 update_hard_regno_preference_check. */
660 static int curr_update_hard_regno_preference_check
;
661 /* If an element value is equal to the above variable value, then the
662 corresponding regno has been processed for preference
664 static int *update_hard_regno_preference_check
;
666 /* Update the preference for using HARD_REGNO for pseudos that are
667 connected directly or indirectly with REGNO. Apply divisor DIV
668 to any preference adjustments.
670 The more indirectly a pseudo is connected, the smaller its effect
671 should be. We therefore increase DIV on each "hop". */
673 update_hard_regno_preference (int regno
, int hard_regno
, int div
)
675 int another_regno
, cost
;
676 lra_copy_t cp
, next_cp
;
678 /* Search depth 5 seems to be enough. */
681 for (cp
= lra_reg_info
[regno
].copies
; cp
!= NULL
; cp
= next_cp
)
683 if (cp
->regno1
== regno
)
685 next_cp
= cp
->regno1_next
;
686 another_regno
= cp
->regno2
;
688 else if (cp
->regno2
== regno
)
690 next_cp
= cp
->regno2_next
;
691 another_regno
= cp
->regno1
;
695 if (reg_renumber
[another_regno
] < 0
696 && (update_hard_regno_preference_check
[another_regno
]
697 != curr_update_hard_regno_preference_check
))
699 update_hard_regno_preference_check
[another_regno
]
700 = curr_update_hard_regno_preference_check
;
701 cost
= cp
->freq
< div
? 1 : cp
->freq
/ div
;
702 lra_setup_reload_pseudo_preferenced_hard_reg
703 (another_regno
, hard_regno
, cost
);
704 update_hard_regno_preference (another_regno
, hard_regno
, div
* 2);
709 /* Return prefix title for pseudo REGNO. */
711 pseudo_prefix_title (int regno
)
714 (regno
< lra_constraint_new_regno_start
? ""
715 : bitmap_bit_p (&lra_inheritance_pseudos
, regno
) ? "inheritance "
716 : bitmap_bit_p (&lra_split_regs
, regno
) ? "split "
717 : bitmap_bit_p (&lra_optional_reload_pseudos
, regno
) ? "optional reload "
718 : bitmap_bit_p (&lra_subreg_reload_pseudos
, regno
) ? "subreg reload "
722 /* Update REG_RENUMBER and other pseudo preferences by assignment of
723 HARD_REGNO to pseudo REGNO and print about it if PRINT_P. */
725 lra_setup_reg_renumber (int regno
, int hard_regno
, bool print_p
)
729 /* We can not just reassign hard register. */
730 lra_assert (hard_regno
< 0 || reg_renumber
[regno
] < 0);
731 if ((hr
= hard_regno
) < 0)
732 hr
= reg_renumber
[regno
];
733 reg_renumber
[regno
] = hard_regno
;
734 lra_assert (hr
>= 0);
735 for (i
= 0; i
< hard_regno_nregs
[hr
][PSEUDO_REGNO_MODE (regno
)]; i
++)
737 lra_hard_reg_usage
[hr
+ i
] -= lra_reg_info
[regno
].freq
;
739 lra_hard_reg_usage
[hr
+ i
] += lra_reg_info
[regno
].freq
;
740 if (print_p
&& lra_dump_file
!= NULL
)
741 fprintf (lra_dump_file
, " Assign %d to %sr%d (freq=%d)\n",
742 reg_renumber
[regno
], pseudo_prefix_title (regno
),
743 regno
, lra_reg_info
[regno
].freq
);
746 curr_update_hard_regno_preference_check
++;
747 update_hard_regno_preference (regno
, hard_regno
, 1);
751 /* Pseudos which occur in insns containing a particular pseudo. */
752 static bitmap_head insn_conflict_pseudos
;
754 /* Bitmaps used to contain spill pseudos for given pseudo hard regno
755 and best spill pseudos for given pseudo (and best hard regno). */
756 static bitmap_head spill_pseudos_bitmap
, best_spill_pseudos_bitmap
;
758 /* Current pseudo check for validity of elements in
759 TRY_HARD_REG_PSEUDOS. */
760 static int curr_pseudo_check
;
761 /* Array used for validity of elements in TRY_HARD_REG_PSEUDOS. */
762 static int try_hard_reg_pseudos_check
[FIRST_PSEUDO_REGISTER
];
763 /* Pseudos who hold given hard register at the considered points. */
764 static bitmap_head try_hard_reg_pseudos
[FIRST_PSEUDO_REGISTER
];
766 /* Set up try_hard_reg_pseudos for given program point P and class
767 RCLASS. Those are pseudos living at P and assigned to a hard
768 register of RCLASS. In other words, those are pseudos which can be
769 spilled to assign a hard register of RCLASS to a pseudo living at
772 setup_try_hard_regno_pseudos (int p
, enum reg_class rclass
)
775 enum machine_mode mode
;
776 unsigned int spill_regno
;
779 /* Find what pseudos could be spilled. */
780 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos
[p
], 0, spill_regno
, bi
)
782 mode
= PSEUDO_REGNO_MODE (spill_regno
);
783 hard_regno
= live_pseudos_reg_renumber
[spill_regno
];
784 if (overlaps_hard_reg_set_p (reg_class_contents
[rclass
],
787 for (i
= hard_regno_nregs
[hard_regno
][mode
] - 1; i
>= 0; i
--)
789 if (try_hard_reg_pseudos_check
[hard_regno
+ i
]
790 != curr_pseudo_check
)
792 try_hard_reg_pseudos_check
[hard_regno
+ i
]
794 bitmap_clear (&try_hard_reg_pseudos
[hard_regno
+ i
]);
796 bitmap_set_bit (&try_hard_reg_pseudos
[hard_regno
+ i
],
803 /* Assign temporarily HARD_REGNO to pseudo REGNO. Temporary
804 assignment means that we might undo the data change. */
806 assign_temporarily (int regno
, int hard_regno
)
811 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
813 for (p
= r
->start
; p
<= r
->finish
; p
++)
815 bitmap_clear_bit (&live_hard_reg_pseudos
[p
], regno
);
818 bitmap_set_bit (&live_hard_reg_pseudos
[p
], regno
);
819 insert_in_live_range_start_chain (regno
);
822 live_pseudos_reg_renumber
[regno
] = hard_regno
;
825 /* Array used for sorting reload pseudos for subsequent allocation
826 after spilling some pseudo. */
827 static int *sorted_reload_pseudos
;
829 /* Spill some pseudos for a reload pseudo REGNO and return hard
830 register which should be used for pseudo after spilling. The
831 function adds spilled pseudos to SPILLED_PSEUDO_BITMAP. When we
832 choose hard register (and pseudos occupying the hard registers and
833 to be spilled), we take into account not only how REGNO will
834 benefit from the spills but also how other reload pseudos not yet
835 assigned to hard registers benefit from the spills too. In very
836 rare cases, the function can fail and return -1.
838 If FIRST_P, return the first available hard reg ignoring other
839 criteria, e.g. allocation cost and cost of spilling non-reload
840 pseudos. This approach results in less hard reg pool fragmentation
841 and permit to allocate hard regs to reload pseudos in complicated
842 situations where pseudo sizes are different. */
844 spill_for (int regno
, bitmap spilled_pseudo_bitmap
, bool first_p
)
846 int i
, j
, n
, p
, hard_regno
, best_hard_regno
, cost
, best_cost
, rclass_size
;
847 int reload_hard_regno
, reload_cost
;
848 enum machine_mode mode
;
849 enum reg_class rclass
;
850 unsigned int spill_regno
, reload_regno
, uid
;
851 int insn_pseudos_num
, best_insn_pseudos_num
;
852 int bad_spills_num
, smallest_bad_spills_num
;
856 rclass
= regno_allocno_class_array
[regno
];
857 lra_assert (reg_renumber
[regno
] < 0 && rclass
!= NO_REGS
);
858 bitmap_clear (&insn_conflict_pseudos
);
859 bitmap_clear (&best_spill_pseudos_bitmap
);
860 EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info
[regno
].insn_bitmap
, 0, uid
, bi
)
862 struct lra_insn_reg
*ir
;
864 for (ir
= lra_get_insn_regs (uid
); ir
!= NULL
; ir
= ir
->next
)
865 if (ir
->regno
>= FIRST_PSEUDO_REGISTER
)
866 bitmap_set_bit (&insn_conflict_pseudos
, ir
->regno
);
868 best_hard_regno
= -1;
870 best_insn_pseudos_num
= INT_MAX
;
871 smallest_bad_spills_num
= INT_MAX
;
872 rclass_size
= ira_class_hard_regs_num
[rclass
];
873 mode
= PSEUDO_REGNO_MODE (regno
);
874 /* Invalidate try_hard_reg_pseudos elements. */
876 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
877 for (p
= r
->start
; p
<= r
->finish
; p
++)
878 setup_try_hard_regno_pseudos (p
, rclass
);
879 for (i
= 0; i
< rclass_size
; i
++)
881 hard_regno
= ira_class_hard_regs
[rclass
][i
];
882 bitmap_clear (&spill_pseudos_bitmap
);
883 for (j
= hard_regno_nregs
[hard_regno
][mode
] - 1; j
>= 0; j
--)
885 if (try_hard_reg_pseudos_check
[hard_regno
+ j
] != curr_pseudo_check
)
887 lra_assert (!bitmap_empty_p (&try_hard_reg_pseudos
[hard_regno
+ j
]));
888 bitmap_ior_into (&spill_pseudos_bitmap
,
889 &try_hard_reg_pseudos
[hard_regno
+ j
]);
892 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
893 if ((int) spill_regno
>= lra_constraint_new_regno_start
894 && ! bitmap_bit_p (&lra_inheritance_pseudos
, spill_regno
)
895 && ! bitmap_bit_p (&lra_split_regs
, spill_regno
)
896 && ! bitmap_bit_p (&lra_subreg_reload_pseudos
, spill_regno
)
897 && ! bitmap_bit_p (&lra_optional_reload_pseudos
, spill_regno
))
899 insn_pseudos_num
= 0;
901 if (lra_dump_file
!= NULL
)
902 fprintf (lra_dump_file
, " Trying %d:", hard_regno
);
903 sparseset_clear (live_range_reload_inheritance_pseudos
);
904 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
906 if (bitmap_bit_p (&insn_conflict_pseudos
, spill_regno
))
908 if (spill_regno
>= (unsigned int) lra_bad_spill_regno_start
)
910 for (r
= lra_reg_info
[spill_regno
].live_ranges
;
914 for (p
= r
->start
; p
<= r
->finish
; p
++)
918 for (r2
= start_point_ranges
[p
];
921 if (r2
->regno
>= lra_constraint_new_regno_start
)
922 sparseset_set_bit (live_range_reload_inheritance_pseudos
,
928 if (sparseset_cardinality (live_range_reload_inheritance_pseudos
)
929 <= (unsigned)LRA_MAX_CONSIDERED_RELOAD_PSEUDOS
)
930 EXECUTE_IF_SET_IN_SPARSESET (live_range_reload_inheritance_pseudos
,
932 if ((int) reload_regno
!= regno
933 && (ira_reg_classes_intersect_p
934 [rclass
][regno_allocno_class_array
[reload_regno
]])
935 && live_pseudos_reg_renumber
[reload_regno
] < 0
936 && find_hard_regno_for (reload_regno
, &cost
, -1, first_p
) < 0)
937 sorted_reload_pseudos
[n
++] = reload_regno
;
938 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
940 update_lives (spill_regno
, true);
941 if (lra_dump_file
!= NULL
)
942 fprintf (lra_dump_file
, " spill %d(freq=%d)",
943 spill_regno
, lra_reg_info
[spill_regno
].freq
);
945 hard_regno
= find_hard_regno_for (regno
, &cost
, -1, first_p
);
948 assign_temporarily (regno
, hard_regno
);
949 qsort (sorted_reload_pseudos
, n
, sizeof (int),
950 reload_pseudo_compare_func
);
951 for (j
= 0; j
< n
; j
++)
953 reload_regno
= sorted_reload_pseudos
[j
];
954 lra_assert (live_pseudos_reg_renumber
[reload_regno
] < 0);
955 if ((reload_hard_regno
956 = find_hard_regno_for (reload_regno
,
957 &reload_cost
, -1, first_p
)) >= 0)
959 if (lra_dump_file
!= NULL
)
960 fprintf (lra_dump_file
, " assign %d(cost=%d)",
961 reload_regno
, reload_cost
);
962 assign_temporarily (reload_regno
, reload_hard_regno
);
966 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
970 cost
+= lra_reg_info
[spill_regno
].freq
;
971 if (ira_reg_equiv
[spill_regno
].memory
!= NULL
972 || ira_reg_equiv
[spill_regno
].constant
!= NULL
)
973 for (x
= ira_reg_equiv
[spill_regno
].init_insns
;
976 cost
-= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (XEXP (x
, 0)));
978 if (best_insn_pseudos_num
> insn_pseudos_num
979 || (best_insn_pseudos_num
== insn_pseudos_num
980 && (bad_spills_num
< smallest_bad_spills_num
981 || (bad_spills_num
== smallest_bad_spills_num
982 && best_cost
> cost
))))
984 best_insn_pseudos_num
= insn_pseudos_num
;
985 smallest_bad_spills_num
= bad_spills_num
;
987 best_hard_regno
= hard_regno
;
988 bitmap_copy (&best_spill_pseudos_bitmap
, &spill_pseudos_bitmap
);
989 if (lra_dump_file
!= NULL
)
990 fprintf (lra_dump_file
,
991 " Now best %d(cost=%d, bad_spills=%d, insn_pseudos=%d)\n",
992 hard_regno
, cost
, bad_spills_num
, insn_pseudos_num
);
994 assign_temporarily (regno
, -1);
995 for (j
= 0; j
< n
; j
++)
997 reload_regno
= sorted_reload_pseudos
[j
];
998 if (live_pseudos_reg_renumber
[reload_regno
] >= 0)
999 assign_temporarily (reload_regno
, -1);
1002 if (lra_dump_file
!= NULL
)
1003 fprintf (lra_dump_file
, "\n");
1004 /* Restore the live hard reg pseudo info for spilled pseudos. */
1005 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
1006 update_lives (spill_regno
, false);
1011 EXECUTE_IF_SET_IN_BITMAP (&best_spill_pseudos_bitmap
, 0, spill_regno
, bi
)
1013 if ((int) spill_regno
>= lra_constraint_new_regno_start
)
1014 former_reload_pseudo_spill_p
= true;
1015 if (lra_dump_file
!= NULL
)
1016 fprintf (lra_dump_file
, " Spill %sr%d(hr=%d, freq=%d) for r%d\n",
1017 pseudo_prefix_title (spill_regno
),
1018 spill_regno
, reg_renumber
[spill_regno
],
1019 lra_reg_info
[spill_regno
].freq
, regno
);
1020 update_lives (spill_regno
, true);
1021 lra_setup_reg_renumber (spill_regno
, -1, false);
1023 bitmap_ior_into (spilled_pseudo_bitmap
, &best_spill_pseudos_bitmap
);
1024 return best_hard_regno
;
1027 /* Assign HARD_REGNO to REGNO. */
1029 assign_hard_regno (int hard_regno
, int regno
)
1033 lra_assert (hard_regno
>= 0);
1034 lra_setup_reg_renumber (regno
, hard_regno
, true);
1035 update_lives (regno
, false);
1037 i
< hard_regno_nregs
[hard_regno
][lra_reg_info
[regno
].biggest_mode
];
1039 df_set_regs_ever_live (hard_regno
+ i
, true);
1042 /* Array used for sorting different pseudos. */
1043 static int *sorted_pseudos
;
1045 /* The constraints pass is allowed to create equivalences between
1046 pseudos that make the current allocation "incorrect" (in the sense
1047 that pseudos are assigned to hard registers from their own conflict
1048 sets). The global variable lra_risky_transformations_p says
1049 whether this might have happened.
1051 Process pseudos assigned to hard registers (less frequently used
1052 first), spill if a conflict is found, and mark the spilled pseudos
1053 in SPILLED_PSEUDO_BITMAP. Set up LIVE_HARD_REG_PSEUDOS from
1054 pseudos, assigned to hard registers. */
1056 setup_live_pseudos_and_spill_after_risky_transforms (bitmap
1057 spilled_pseudo_bitmap
)
1059 int p
, i
, j
, n
, regno
, hard_regno
;
1060 unsigned int k
, conflict_regno
;
1062 HARD_REG_SET conflict_set
;
1063 enum machine_mode mode
;
1066 int max_regno
= max_reg_num ();
1068 if (! lra_risky_transformations_p
)
1070 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1071 if (reg_renumber
[i
] >= 0 && lra_reg_info
[i
].nrefs
> 0)
1072 update_lives (i
, false);
1075 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1076 if (reg_renumber
[i
] >= 0 && lra_reg_info
[i
].nrefs
> 0)
1077 sorted_pseudos
[n
++] = i
;
1078 qsort (sorted_pseudos
, n
, sizeof (int), pseudo_compare_func
);
1079 for (i
= n
- 1; i
>= 0; i
--)
1081 regno
= sorted_pseudos
[i
];
1082 hard_regno
= reg_renumber
[regno
];
1083 lra_assert (hard_regno
>= 0);
1084 mode
= lra_reg_info
[regno
].biggest_mode
;
1085 sparseset_clear (live_range_hard_reg_pseudos
);
1086 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
1088 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos
[r
->start
], 0, k
, bi
)
1089 sparseset_set_bit (live_range_hard_reg_pseudos
, k
);
1090 for (p
= r
->start
+ 1; p
<= r
->finish
; p
++)
1092 lra_live_range_t r2
;
1094 for (r2
= start_point_ranges
[p
];
1096 r2
= r2
->start_next
)
1097 if (live_pseudos_reg_renumber
[r2
->regno
] >= 0)
1098 sparseset_set_bit (live_range_hard_reg_pseudos
, r2
->regno
);
1101 COPY_HARD_REG_SET (conflict_set
, lra_no_alloc_regs
);
1102 IOR_HARD_REG_SET (conflict_set
, lra_reg_info
[regno
].conflict_hard_regs
);
1103 val
= lra_reg_info
[regno
].val
;
1104 offset
= lra_reg_info
[regno
].offset
;
1105 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos
, conflict_regno
)
1106 if (!lra_reg_val_equal_p (conflict_regno
, val
, offset
)
1107 /* If it is multi-register pseudos they should start on
1108 the same hard register. */
1109 || hard_regno
!= reg_renumber
[conflict_regno
])
1110 add_to_hard_reg_set (&conflict_set
,
1111 lra_reg_info
[conflict_regno
].biggest_mode
,
1112 reg_renumber
[conflict_regno
]);
1113 if (! overlaps_hard_reg_set_p (conflict_set
, mode
, hard_regno
))
1115 update_lives (regno
, false);
1118 bitmap_set_bit (spilled_pseudo_bitmap
, regno
);
1120 j
< hard_regno_nregs
[hard_regno
][PSEUDO_REGNO_MODE (regno
)];
1122 lra_hard_reg_usage
[hard_regno
+ j
] -= lra_reg_info
[regno
].freq
;
1123 reg_renumber
[regno
] = -1;
1124 if (regno
>= lra_constraint_new_regno_start
)
1125 former_reload_pseudo_spill_p
= true;
1126 if (lra_dump_file
!= NULL
)
1127 fprintf (lra_dump_file
, " Spill r%d after risky transformations\n",
1132 /* Improve allocation by assigning the same hard regno of inheritance
1133 pseudos to the connected pseudos. We need this because inheritance
1134 pseudos are allocated after reload pseudos in the thread and when
1135 we assign a hard register to a reload pseudo we don't know yet that
1136 the connected inheritance pseudos can get the same hard register.
1137 Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS. */
1139 improve_inheritance (bitmap changed_pseudos
)
1142 int regno
, another_regno
, hard_regno
, another_hard_regno
, cost
, i
, n
;
1143 lra_copy_t cp
, next_cp
;
1146 if (lra_inheritance_iter
> LRA_MAX_INHERITANCE_PASSES
)
1149 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos
, 0, k
, bi
)
1150 if (reg_renumber
[k
] >= 0 && lra_reg_info
[k
].nrefs
!= 0)
1151 sorted_pseudos
[n
++] = k
;
1152 qsort (sorted_pseudos
, n
, sizeof (int), pseudo_compare_func
);
1153 for (i
= 0; i
< n
; i
++)
1155 regno
= sorted_pseudos
[i
];
1156 hard_regno
= reg_renumber
[regno
];
1157 lra_assert (hard_regno
>= 0);
1158 for (cp
= lra_reg_info
[regno
].copies
; cp
!= NULL
; cp
= next_cp
)
1160 if (cp
->regno1
== regno
)
1162 next_cp
= cp
->regno1_next
;
1163 another_regno
= cp
->regno2
;
1165 else if (cp
->regno2
== regno
)
1167 next_cp
= cp
->regno2_next
;
1168 another_regno
= cp
->regno1
;
1172 /* Don't change reload pseudo allocation. It might have
1173 this allocation for a purpose and changing it can result
1175 if ((another_regno
< lra_constraint_new_regno_start
1176 || bitmap_bit_p (&lra_inheritance_pseudos
, another_regno
))
1177 && (another_hard_regno
= reg_renumber
[another_regno
]) >= 0
1178 && another_hard_regno
!= hard_regno
)
1180 if (lra_dump_file
!= NULL
)
1183 " Improving inheritance for %d(%d) and %d(%d)...\n",
1184 regno
, hard_regno
, another_regno
, another_hard_regno
);
1185 update_lives (another_regno
, true);
1186 lra_setup_reg_renumber (another_regno
, -1, false);
1187 if (hard_regno
== find_hard_regno_for (another_regno
, &cost
,
1189 assign_hard_regno (hard_regno
, another_regno
);
1191 assign_hard_regno (another_hard_regno
, another_regno
);
1192 bitmap_set_bit (changed_pseudos
, another_regno
);
1199 /* Bitmap finally containing all pseudos spilled on this assignment
1201 static bitmap_head all_spilled_pseudos
;
1202 /* All pseudos whose allocation was changed. */
1203 static bitmap_head changed_pseudo_bitmap
;
1206 /* Add to LIVE_RANGE_HARD_REG_PSEUDOS all pseudos conflicting with
1207 REGNO and whose hard regs can be assigned to REGNO. */
1209 find_all_spills_for (int regno
)
1215 enum reg_class rclass
;
1216 bool *rclass_intersect_p
;
1218 rclass
= regno_allocno_class_array
[regno
];
1219 rclass_intersect_p
= ira_reg_classes_intersect_p
[rclass
];
1220 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
1222 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos
[r
->start
], 0, k
, bi
)
1223 if (rclass_intersect_p
[regno_allocno_class_array
[k
]])
1224 sparseset_set_bit (live_range_hard_reg_pseudos
, k
);
1225 for (p
= r
->start
+ 1; p
<= r
->finish
; p
++)
1227 lra_live_range_t r2
;
1229 for (r2
= start_point_ranges
[p
];
1231 r2
= r2
->start_next
)
1233 if (live_pseudos_reg_renumber
[r2
->regno
] >= 0
1234 && rclass_intersect_p
[regno_allocno_class_array
[r2
->regno
]])
1235 sparseset_set_bit (live_range_hard_reg_pseudos
, r2
->regno
);
1241 /* Assign hard registers to reload pseudos and other pseudos. */
1243 assign_by_spills (void)
1245 int i
, n
, nfails
, iter
, regno
, hard_regno
, cost
, restore_regno
;
1247 bitmap_head changed_insns
, do_not_assign_nonreload_pseudos
;
1248 unsigned int u
, conflict_regno
;
1251 int max_regno
= max_reg_num ();
1253 for (n
= 0, i
= lra_constraint_new_regno_start
; i
< max_regno
; i
++)
1254 if (reg_renumber
[i
] < 0 && lra_reg_info
[i
].nrefs
!= 0
1255 && regno_allocno_class_array
[i
] != NO_REGS
)
1256 sorted_pseudos
[n
++] = i
;
1257 bitmap_initialize (&insn_conflict_pseudos
, ®_obstack
);
1258 bitmap_initialize (&spill_pseudos_bitmap
, ®_obstack
);
1259 bitmap_initialize (&best_spill_pseudos_bitmap
, ®_obstack
);
1260 update_hard_regno_preference_check
= XCNEWVEC (int, max_regno
);
1261 curr_update_hard_regno_preference_check
= 0;
1262 memset (try_hard_reg_pseudos_check
, 0, sizeof (try_hard_reg_pseudos_check
));
1263 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1264 bitmap_initialize (&try_hard_reg_pseudos
[i
], ®_obstack
);
1265 curr_pseudo_check
= 0;
1266 bitmap_initialize (&changed_insns
, ®_obstack
);
1267 bitmap_initialize (&non_reload_pseudos
, ®_obstack
);
1268 bitmap_ior (&non_reload_pseudos
, &lra_inheritance_pseudos
, &lra_split_regs
);
1269 bitmap_ior_into (&non_reload_pseudos
, &lra_subreg_reload_pseudos
);
1270 bitmap_ior_into (&non_reload_pseudos
, &lra_optional_reload_pseudos
);
1271 for (iter
= 0; iter
<= 1; iter
++)
1273 qsort (sorted_pseudos
, n
, sizeof (int), reload_pseudo_compare_func
);
1275 for (i
= 0; i
< n
; i
++)
1277 regno
= sorted_pseudos
[i
];
1278 if (lra_dump_file
!= NULL
)
1279 fprintf (lra_dump_file
, " Assigning to %d "
1280 "(cl=%s, orig=%d, freq=%d, tfirst=%d, tfreq=%d)...\n",
1281 regno
, reg_class_names
[regno_allocno_class_array
[regno
]],
1282 ORIGINAL_REGNO (regno_reg_rtx
[regno
]),
1283 lra_reg_info
[regno
].freq
, regno_assign_info
[regno
].first
,
1284 regno_assign_info
[regno_assign_info
[regno
].first
].freq
);
1285 hard_regno
= find_hard_regno_for (regno
, &cost
, -1, iter
== 1);
1286 reload_p
= ! bitmap_bit_p (&non_reload_pseudos
, regno
);
1287 if (hard_regno
< 0 && reload_p
)
1288 hard_regno
= spill_for (regno
, &all_spilled_pseudos
, iter
== 1);
1292 sorted_pseudos
[nfails
++] = regno
;
1296 /* This register might have been spilled by the previous
1297 pass. Indicate that it is no longer spilled. */
1298 bitmap_clear_bit (&all_spilled_pseudos
, regno
);
1299 assign_hard_regno (hard_regno
, regno
);
1301 /* As non-reload pseudo assignment is changed we
1302 should reconsider insns referring for the
1304 bitmap_set_bit (&changed_pseudo_bitmap
, regno
);
1311 /* We did not assign hard regs to reload pseudos after two
1312 iteration. It means something is wrong with asm insn
1313 constraints. Report it. */
1315 bitmap_head failed_reload_insns
;
1317 bitmap_initialize (&failed_reload_insns
, ®_obstack
);
1318 for (i
= 0; i
< nfails
; i
++)
1320 regno
= sorted_pseudos
[i
];
1321 bitmap_ior_into (&failed_reload_insns
,
1322 &lra_reg_info
[regno
].insn_bitmap
);
1323 /* Assign an arbitrary hard register of regno class to
1324 avoid further trouble with the asm insns. */
1325 bitmap_clear_bit (&all_spilled_pseudos
, regno
);
1327 (ira_class_hard_regs
[regno_allocno_class_array
[regno
]][0],
1330 EXECUTE_IF_SET_IN_BITMAP (&failed_reload_insns
, 0, u
, bi
)
1332 insn
= lra_insn_recog_data
[u
]->insn
;
1333 if (asm_noperands (PATTERN (insn
)) >= 0)
1336 error_for_asm (insn
,
1337 "%<asm%> operand has impossible constraints");
1338 /* Avoid further trouble with this insn.
1339 For asm goto, instead of fixing up all the edges
1340 just clear the template and clear input operands
1341 (asm goto doesn't have any output operands). */
1344 rtx asm_op
= extract_asm_operands (PATTERN (insn
));
1345 ASM_OPERANDS_TEMPLATE (asm_op
) = ggc_strdup ("");
1346 ASM_OPERANDS_INPUT_VEC (asm_op
) = rtvec_alloc (0);
1347 ASM_OPERANDS_INPUT_CONSTRAINT_VEC (asm_op
) = rtvec_alloc (0);
1348 lra_update_insn_regno_info (insn
);
1352 PATTERN (insn
) = gen_rtx_USE (VOIDmode
, const0_rtx
);
1353 lra_set_insn_deleted (insn
);
1360 /* This is a very rare event. We can not assign a hard register
1361 to reload pseudo because the hard register was assigned to
1362 another reload pseudo on a previous assignment pass. For x86
1363 example, on the 1st pass we assigned CX (although another
1364 hard register could be used for this) to reload pseudo in an
1365 insn, on the 2nd pass we need CX (and only this) hard
1366 register for a new reload pseudo in the same insn. Another
1367 possible situation may occur in assigning to multi-regs
1368 reload pseudos when hard regs pool is too fragmented even
1369 after spilling non-reload pseudos.
1371 We should do something radical here to succeed. Here we
1372 spill *all* conflicting pseudos and reassign them. */
1373 if (lra_dump_file
!= NULL
)
1374 fprintf (lra_dump_file
, " 2nd iter for reload pseudo assignments:\n");
1375 sparseset_clear (live_range_hard_reg_pseudos
);
1376 for (i
= 0; i
< nfails
; i
++)
1378 if (lra_dump_file
!= NULL
)
1379 fprintf (lra_dump_file
, " Reload r%d assignment failure\n",
1381 find_all_spills_for (sorted_pseudos
[i
]);
1383 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos
, conflict_regno
)
1385 if ((int) conflict_regno
>= lra_constraint_new_regno_start
)
1387 sorted_pseudos
[nfails
++] = conflict_regno
;
1388 former_reload_pseudo_spill_p
= true;
1390 if (lra_dump_file
!= NULL
)
1391 fprintf (lra_dump_file
, " Spill %s r%d(hr=%d, freq=%d)\n",
1392 pseudo_prefix_title (conflict_regno
), conflict_regno
,
1393 reg_renumber
[conflict_regno
],
1394 lra_reg_info
[conflict_regno
].freq
);
1395 update_lives (conflict_regno
, true);
1396 lra_setup_reg_renumber (conflict_regno
, -1, false);
1400 improve_inheritance (&changed_pseudo_bitmap
);
1401 bitmap_clear (&non_reload_pseudos
);
1402 bitmap_clear (&changed_insns
);
1405 /* We should not assign to original pseudos of inheritance
1406 pseudos or split pseudos if any its inheritance pseudo did
1407 not get hard register or any its split pseudo was not split
1408 because undo inheritance/split pass will extend live range of
1409 such inheritance or split pseudos. */
1410 bitmap_initialize (&do_not_assign_nonreload_pseudos
, ®_obstack
);
1411 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos
, 0, u
, bi
)
1412 if ((restore_regno
= lra_reg_info
[u
].restore_regno
) >= 0
1413 && reg_renumber
[u
] < 0
1414 && bitmap_bit_p (&lra_inheritance_pseudos
, u
))
1415 bitmap_set_bit (&do_not_assign_nonreload_pseudos
, restore_regno
);
1416 EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs
, 0, u
, bi
)
1417 if ((restore_regno
= lra_reg_info
[u
].restore_regno
) >= 0
1418 && reg_renumber
[u
] >= 0)
1419 bitmap_set_bit (&do_not_assign_nonreload_pseudos
, restore_regno
);
1420 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1421 if (((i
< lra_constraint_new_regno_start
1422 && ! bitmap_bit_p (&do_not_assign_nonreload_pseudos
, i
))
1423 || (bitmap_bit_p (&lra_inheritance_pseudos
, i
)
1424 && lra_reg_info
[i
].restore_regno
>= 0)
1425 || (bitmap_bit_p (&lra_split_regs
, i
)
1426 && lra_reg_info
[i
].restore_regno
>= 0)
1427 || bitmap_bit_p (&lra_subreg_reload_pseudos
, i
)
1428 || bitmap_bit_p (&lra_optional_reload_pseudos
, i
))
1429 && reg_renumber
[i
] < 0 && lra_reg_info
[i
].nrefs
!= 0
1430 && regno_allocno_class_array
[i
] != NO_REGS
)
1431 sorted_pseudos
[n
++] = i
;
1432 bitmap_clear (&do_not_assign_nonreload_pseudos
);
1433 if (n
!= 0 && lra_dump_file
!= NULL
)
1434 fprintf (lra_dump_file
, " Reassigning non-reload pseudos\n");
1435 qsort (sorted_pseudos
, n
, sizeof (int), pseudo_compare_func
);
1436 for (i
= 0; i
< n
; i
++)
1438 regno
= sorted_pseudos
[i
];
1439 hard_regno
= find_hard_regno_for (regno
, &cost
, -1, false);
1440 if (hard_regno
>= 0)
1442 assign_hard_regno (hard_regno
, regno
);
1443 /* We change allocation for non-reload pseudo on this
1444 iteration -- mark the pseudo for invalidation of used
1445 alternatives of insns containing the pseudo. */
1446 bitmap_set_bit (&changed_pseudo_bitmap
, regno
);
1450 free (update_hard_regno_preference_check
);
1451 bitmap_clear (&best_spill_pseudos_bitmap
);
1452 bitmap_clear (&spill_pseudos_bitmap
);
1453 bitmap_clear (&insn_conflict_pseudos
);
1457 /* Entry function to assign hard registers to new reload pseudos
1458 starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling
1459 of old pseudos) and possibly to the old pseudos. The function adds
1460 what insns to process for the next constraint pass. Those are all
1461 insns who contains non-reload and non-inheritance pseudos with
1464 Return true if we did not spill any non-reload and non-inheritance
1472 bitmap_head insns_to_process
;
1474 int max_regno
= max_reg_num ();
1476 timevar_push (TV_LRA_ASSIGN
);
1477 lra_assignment_iter
++;
1478 if (lra_dump_file
!= NULL
)
1479 fprintf (lra_dump_file
, "\n********** Assignment #%d: **********\n\n",
1480 lra_assignment_iter
);
1482 sorted_pseudos
= XNEWVEC (int, max_regno
);
1483 sorted_reload_pseudos
= XNEWVEC (int, max_regno
);
1484 regno_allocno_class_array
= XNEWVEC (enum reg_class
, max_regno
);
1485 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1486 regno_allocno_class_array
[i
] = lra_get_allocno_class (i
);
1487 former_reload_pseudo_spill_p
= false;
1488 init_regno_assign_info ();
1489 bitmap_initialize (&all_spilled_pseudos
, ®_obstack
);
1490 create_live_range_start_chains ();
1491 setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos
);
1492 #ifdef ENABLE_CHECKING
1493 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1494 if (lra_reg_info
[i
].nrefs
!= 0 && reg_renumber
[i
] >= 0
1495 && lra_reg_info
[i
].call_p
1496 && overlaps_hard_reg_set_p (call_used_reg_set
,
1497 PSEUDO_REGNO_MODE (i
), reg_renumber
[i
]))
1500 /* Setup insns to process on the next constraint pass. */
1501 bitmap_initialize (&changed_pseudo_bitmap
, ®_obstack
);
1502 init_live_reload_and_inheritance_pseudos ();
1503 assign_by_spills ();
1504 finish_live_reload_and_inheritance_pseudos ();
1505 bitmap_ior_into (&changed_pseudo_bitmap
, &all_spilled_pseudos
);
1507 EXECUTE_IF_SET_IN_BITMAP (&all_spilled_pseudos
, 0, u
, bi
)
1508 /* We ignore spilled pseudos created on last inheritance pass
1509 because they will be removed. */
1510 if (lra_reg_info
[u
].restore_regno
< 0)
1512 no_spills_p
= false;
1515 finish_live_range_start_chains ();
1516 bitmap_clear (&all_spilled_pseudos
);
1517 bitmap_initialize (&insns_to_process
, ®_obstack
);
1518 EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap
, 0, u
, bi
)
1519 bitmap_ior_into (&insns_to_process
, &lra_reg_info
[u
].insn_bitmap
);
1520 bitmap_clear (&changed_pseudo_bitmap
);
1521 EXECUTE_IF_SET_IN_BITMAP (&insns_to_process
, 0, u
, bi
)
1523 lra_push_insn_by_uid (u
);
1524 /* Invalidate alternatives for insn should be processed. */
1525 lra_set_used_insn_alternative_by_uid (u
, -1);
1527 bitmap_clear (&insns_to_process
);
1528 finish_regno_assign_info ();
1529 free (regno_allocno_class_array
);
1530 free (sorted_pseudos
);
1531 free (sorted_reload_pseudos
);
1533 timevar_pop (TV_LRA_ASSIGN
);
1534 if (former_reload_pseudo_spill_p
)
1535 lra_assignment_iter_after_spill
++;
1536 if (lra_assignment_iter_after_spill
> LRA_MAX_ASSIGNMENT_ITERATION_NUMBER
)
1538 ("Maximum number of LRA assignment passes is achieved (%d)\n",
1539 LRA_MAX_ASSIGNMENT_ITERATION_NUMBER
);