1 /* Assign reload pseudos.
2 Copyright (C) 2010-2015 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"
84 #include "rtl-error.h"
87 #include "insn-config.h"
103 #include "sparseset.h"
106 #include "insn-attr.h"
107 #include "insn-codes.h"
110 /* Current iteration number of the pass and current iteration number
111 of the pass after the latest spill pass when any former reload
112 pseudo was spilled. */
113 int lra_assignment_iter
;
114 int lra_assignment_iter_after_spill
;
116 /* Flag of spilling former reload pseudos on this pass. */
117 static bool former_reload_pseudo_spill_p
;
119 /* Array containing corresponding values of function
120 lra_get_allocno_class. It is used to speed up the code. */
121 static enum reg_class
*regno_allocno_class_array
;
123 /* Information about the thread to which a pseudo belongs. Threads are
124 a set of connected reload and inheritance pseudos with the same set of
125 available hard registers. Lone registers belong to their own threads. */
126 struct regno_assign_info
128 /* First/next pseudo of the same thread. */
130 /* Frequency of the thread (execution frequency of only reload
131 pseudos in the thread when the thread contains a reload pseudo).
132 Defined only for the first thread pseudo. */
136 /* Map regno to the corresponding regno assignment info. */
137 static struct regno_assign_info
*regno_assign_info
;
139 /* All inherited, subreg or optional pseudos created before last spill
140 sub-pass. Such pseudos are permitted to get memory instead of hard
142 static bitmap_head non_reload_pseudos
;
144 /* Process a pseudo copy with execution frequency COPY_FREQ connecting
145 REGNO1 and REGNO2 to form threads. */
147 process_copy_to_form_thread (int regno1
, int regno2
, int copy_freq
)
149 int last
, regno1_first
, regno2_first
;
151 lra_assert (regno1
>= lra_constraint_new_regno_start
152 && regno2
>= lra_constraint_new_regno_start
);
153 regno1_first
= regno_assign_info
[regno1
].first
;
154 regno2_first
= regno_assign_info
[regno2
].first
;
155 if (regno1_first
!= regno2_first
)
157 for (last
= regno2_first
;
158 regno_assign_info
[last
].next
>= 0;
159 last
= regno_assign_info
[last
].next
)
160 regno_assign_info
[last
].first
= regno1_first
;
161 regno_assign_info
[last
].first
= regno1_first
;
162 regno_assign_info
[last
].next
= regno_assign_info
[regno1_first
].next
;
163 regno_assign_info
[regno1_first
].next
= regno2_first
;
164 regno_assign_info
[regno1_first
].freq
165 += regno_assign_info
[regno2_first
].freq
;
167 regno_assign_info
[regno1_first
].freq
-= 2 * copy_freq
;
168 lra_assert (regno_assign_info
[regno1_first
].freq
>= 0);
171 /* Initialize REGNO_ASSIGN_INFO and form threads. */
173 init_regno_assign_info (void)
175 int i
, regno1
, regno2
, max_regno
= max_reg_num ();
178 regno_assign_info
= XNEWVEC (struct regno_assign_info
, max_regno
);
179 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
181 regno_assign_info
[i
].first
= i
;
182 regno_assign_info
[i
].next
= -1;
183 regno_assign_info
[i
].freq
= lra_reg_info
[i
].freq
;
185 /* Form the threads. */
186 for (i
= 0; (cp
= lra_get_copy (i
)) != NULL
; i
++)
187 if ((regno1
= cp
->regno1
) >= lra_constraint_new_regno_start
188 && (regno2
= cp
->regno2
) >= lra_constraint_new_regno_start
189 && reg_renumber
[regno1
] < 0 && lra_reg_info
[regno1
].nrefs
!= 0
190 && reg_renumber
[regno2
] < 0 && lra_reg_info
[regno2
].nrefs
!= 0
191 && (ira_class_hard_regs_num
[regno_allocno_class_array
[regno1
]]
192 == ira_class_hard_regs_num
[regno_allocno_class_array
[regno2
]]))
193 process_copy_to_form_thread (regno1
, regno2
, cp
->freq
);
196 /* Free REGNO_ASSIGN_INFO. */
198 finish_regno_assign_info (void)
200 free (regno_assign_info
);
203 /* The function is used to sort *reload* and *inheritance* pseudos to
204 try to assign them hard registers. We put pseudos from the same
205 thread always nearby. */
207 reload_pseudo_compare_func (const void *v1p
, const void *v2p
)
209 int r1
= *(const int *) v1p
, r2
= *(const int *) v2p
;
210 enum reg_class cl1
= regno_allocno_class_array
[r1
];
211 enum reg_class cl2
= regno_allocno_class_array
[r2
];
214 lra_assert (r1
>= lra_constraint_new_regno_start
215 && r2
>= lra_constraint_new_regno_start
);
217 /* Prefer to assign reload registers with smaller classes first to
218 guarantee assignment to all reload registers. */
219 if ((diff
= (ira_class_hard_regs_num
[cl1
]
220 - ira_class_hard_regs_num
[cl2
])) != 0)
223 = (ira_reg_class_max_nregs
[cl2
][lra_reg_info
[r2
].biggest_mode
]
224 - ira_reg_class_max_nregs
[cl1
][lra_reg_info
[r1
].biggest_mode
])) != 0
225 /* The code below executes rarely as nregs == 1 in most cases.
226 So we should not worry about using faster data structures to
227 check reload pseudos. */
228 && ! bitmap_bit_p (&non_reload_pseudos
, r1
)
229 && ! bitmap_bit_p (&non_reload_pseudos
, r2
))
231 if ((diff
= (regno_assign_info
[regno_assign_info
[r2
].first
].freq
232 - regno_assign_info
[regno_assign_info
[r1
].first
].freq
)) != 0)
234 /* Allocate bigger pseudos first to avoid register file
237 = (ira_reg_class_max_nregs
[cl2
][lra_reg_info
[r2
].biggest_mode
]
238 - ira_reg_class_max_nregs
[cl1
][lra_reg_info
[r1
].biggest_mode
])) != 0)
240 /* Put pseudos from the thread nearby. */
241 if ((diff
= regno_assign_info
[r1
].first
- regno_assign_info
[r2
].first
) != 0)
243 /* If regs are equally good, sort by their numbers, so that the
244 results of qsort leave nothing to chance. */
248 /* The function is used to sort *non-reload* pseudos to try to assign
249 them hard registers. The order calculation is simpler than in the
250 previous function and based on the pseudo frequency usage. */
252 pseudo_compare_func (const void *v1p
, const void *v2p
)
254 int r1
= *(const int *) v1p
, r2
= *(const int *) v2p
;
257 /* Prefer to assign more frequently used registers first. */
258 if ((diff
= lra_reg_info
[r2
].freq
- lra_reg_info
[r1
].freq
) != 0)
261 /* If regs are equally good, sort by their numbers, so that the
262 results of qsort leave nothing to chance. */
266 /* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the
267 pseudo live ranges with given start point. We insert only live
268 ranges of pseudos interesting for assignment purposes. They are
269 reload pseudos and pseudos assigned to hard registers. */
270 static lra_live_range_t
*start_point_ranges
;
272 /* Used as a flag that a live range is not inserted in the start point
274 static struct lra_live_range not_in_chain_mark
;
276 /* Create and set up START_POINT_RANGES. */
278 create_live_range_start_chains (void)
283 start_point_ranges
= XCNEWVEC (lra_live_range_t
, lra_live_max_point
);
284 max_regno
= max_reg_num ();
285 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
286 if (i
>= lra_constraint_new_regno_start
|| reg_renumber
[i
] >= 0)
288 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
290 r
->start_next
= start_point_ranges
[r
->start
];
291 start_point_ranges
[r
->start
] = r
;
296 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
297 r
->start_next
= ¬_in_chain_mark
;
301 /* Insert live ranges of pseudo REGNO into start chains if they are
304 insert_in_live_range_start_chain (int regno
)
306 lra_live_range_t r
= lra_reg_info
[regno
].live_ranges
;
308 if (r
->start_next
!= ¬_in_chain_mark
)
310 for (; r
!= NULL
; r
= r
->next
)
312 r
->start_next
= start_point_ranges
[r
->start
];
313 start_point_ranges
[r
->start
] = r
;
317 /* Free START_POINT_RANGES. */
319 finish_live_range_start_chains (void)
321 gcc_assert (start_point_ranges
!= NULL
);
322 free (start_point_ranges
);
323 start_point_ranges
= NULL
;
326 /* Map: program point -> bitmap of all pseudos living at the point and
327 assigned to hard registers. */
328 static bitmap_head
*live_hard_reg_pseudos
;
329 static bitmap_obstack live_hard_reg_pseudos_bitmap_obstack
;
331 /* reg_renumber corresponding to pseudos marked in
332 live_hard_reg_pseudos. reg_renumber might be not matched to
333 live_hard_reg_pseudos but live_pseudos_reg_renumber always reflects
334 live_hard_reg_pseudos. */
335 static int *live_pseudos_reg_renumber
;
337 /* Sparseset used to calculate living hard reg pseudos for some program
339 static sparseset live_range_hard_reg_pseudos
;
341 /* Sparseset used to calculate living reload/inheritance pseudos for
342 some program point range. */
343 static sparseset live_range_reload_inheritance_pseudos
;
345 /* Allocate and initialize the data about living pseudos at program
350 int i
, max_regno
= max_reg_num ();
352 live_range_hard_reg_pseudos
= sparseset_alloc (max_regno
);
353 live_range_reload_inheritance_pseudos
= sparseset_alloc (max_regno
);
354 live_hard_reg_pseudos
= XNEWVEC (bitmap_head
, lra_live_max_point
);
355 bitmap_obstack_initialize (&live_hard_reg_pseudos_bitmap_obstack
);
356 for (i
= 0; i
< lra_live_max_point
; i
++)
357 bitmap_initialize (&live_hard_reg_pseudos
[i
],
358 &live_hard_reg_pseudos_bitmap_obstack
);
359 live_pseudos_reg_renumber
= XNEWVEC (int, max_regno
);
360 for (i
= 0; i
< max_regno
; i
++)
361 live_pseudos_reg_renumber
[i
] = -1;
364 /* Free the data about living pseudos at program points. */
368 sparseset_free (live_range_hard_reg_pseudos
);
369 sparseset_free (live_range_reload_inheritance_pseudos
);
370 free (live_hard_reg_pseudos
);
371 bitmap_obstack_release (&live_hard_reg_pseudos_bitmap_obstack
);
372 free (live_pseudos_reg_renumber
);
375 /* Update the LIVE_HARD_REG_PSEUDOS and LIVE_PSEUDOS_REG_RENUMBER
376 entries for pseudo REGNO. Assume that the register has been
377 spilled if FREE_P, otherwise assume that it has been assigned
378 reg_renumber[REGNO] (if >= 0). We also insert the pseudo live
379 ranges in the start chains when it is assumed to be assigned to a
380 hard register because we use the chains of pseudos assigned to hard
381 registers during allocation. */
383 update_lives (int regno
, bool free_p
)
388 if (reg_renumber
[regno
] < 0)
390 live_pseudos_reg_renumber
[regno
] = free_p
? -1 : reg_renumber
[regno
];
391 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
393 for (p
= r
->start
; p
<= r
->finish
; p
++)
395 bitmap_clear_bit (&live_hard_reg_pseudos
[p
], regno
);
398 bitmap_set_bit (&live_hard_reg_pseudos
[p
], regno
);
399 insert_in_live_range_start_chain (regno
);
404 /* Sparseset used to calculate reload pseudos conflicting with a given
405 pseudo when we are trying to find a hard register for the given
407 static sparseset conflict_reload_and_inheritance_pseudos
;
409 /* Map: program point -> bitmap of all reload and inheritance pseudos
410 living at the point. */
411 static bitmap_head
*live_reload_and_inheritance_pseudos
;
412 static bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack
;
414 /* Allocate and initialize data about living reload pseudos at any
415 given program point. */
417 init_live_reload_and_inheritance_pseudos (void)
419 int i
, p
, max_regno
= max_reg_num ();
422 conflict_reload_and_inheritance_pseudos
= sparseset_alloc (max_regno
);
423 live_reload_and_inheritance_pseudos
= XNEWVEC (bitmap_head
, lra_live_max_point
);
424 bitmap_obstack_initialize (&live_reload_and_inheritance_pseudos_bitmap_obstack
);
425 for (p
= 0; p
< lra_live_max_point
; p
++)
426 bitmap_initialize (&live_reload_and_inheritance_pseudos
[p
],
427 &live_reload_and_inheritance_pseudos_bitmap_obstack
);
428 for (i
= lra_constraint_new_regno_start
; i
< max_regno
; i
++)
430 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
431 for (p
= r
->start
; p
<= r
->finish
; p
++)
432 bitmap_set_bit (&live_reload_and_inheritance_pseudos
[p
], i
);
436 /* Finalize data about living reload pseudos at any given program
439 finish_live_reload_and_inheritance_pseudos (void)
441 sparseset_free (conflict_reload_and_inheritance_pseudos
);
442 free (live_reload_and_inheritance_pseudos
);
443 bitmap_obstack_release (&live_reload_and_inheritance_pseudos_bitmap_obstack
);
446 /* The value used to check that cost of given hard reg is really
447 defined currently. */
448 static int curr_hard_regno_costs_check
= 0;
449 /* Array used to check that cost of the corresponding hard reg (the
450 array element index) is really defined currently. */
451 static int hard_regno_costs_check
[FIRST_PSEUDO_REGISTER
];
452 /* The current costs of allocation of hard regs. Defined only if the
453 value of the corresponding element of the previous array is equal to
454 CURR_HARD_REGNO_COSTS_CHECK. */
455 static int hard_regno_costs
[FIRST_PSEUDO_REGISTER
];
457 /* Adjust cost of HARD_REGNO by INCR. Reset the cost first if it is
460 adjust_hard_regno_cost (int hard_regno
, int incr
)
462 if (hard_regno_costs_check
[hard_regno
] != curr_hard_regno_costs_check
)
463 hard_regno_costs
[hard_regno
] = 0;
464 hard_regno_costs_check
[hard_regno
] = curr_hard_regno_costs_check
;
465 hard_regno_costs
[hard_regno
] += incr
;
468 /* Try to find a free hard register for pseudo REGNO. Return the
469 hard register on success and set *COST to the cost of using
470 that register. (If several registers have equal cost, the one with
471 the highest priority wins.) Return -1 on failure.
473 If FIRST_P, return the first available hard reg ignoring other
474 criteria, e.g. allocation cost. This approach results in less hard
475 reg pool fragmentation and permit to allocate hard regs to reload
476 pseudos in complicated situations where pseudo sizes are different.
478 If TRY_ONLY_HARD_REGNO >= 0, consider only that hard register,
479 otherwise consider all hard registers in REGNO's class.
481 If REGNO_SET is not empty, only hard registers from the set are
484 find_hard_regno_for_1 (int regno
, int *cost
, int try_only_hard_regno
,
485 bool first_p
, HARD_REG_SET regno_set
)
487 HARD_REG_SET conflict_set
;
488 int best_cost
= INT_MAX
, best_priority
= INT_MIN
, best_usage
= INT_MAX
;
490 int p
, i
, j
, rclass_size
, best_hard_regno
, priority
, hard_regno
;
491 int hr
, conflict_hr
, nregs
;
492 machine_mode biggest_mode
;
493 unsigned int k
, conflict_regno
;
494 int offset
, val
, biggest_nregs
, nregs_diff
;
495 enum reg_class rclass
;
497 bool *rclass_intersect_p
;
498 HARD_REG_SET impossible_start_hard_regs
, available_regs
;
500 if (hard_reg_set_empty_p (regno_set
))
501 COPY_HARD_REG_SET (conflict_set
, lra_no_alloc_regs
);
504 COMPL_HARD_REG_SET (conflict_set
, regno_set
);
505 IOR_HARD_REG_SET (conflict_set
, lra_no_alloc_regs
);
507 rclass
= regno_allocno_class_array
[regno
];
508 rclass_intersect_p
= ira_reg_classes_intersect_p
[rclass
];
509 curr_hard_regno_costs_check
++;
510 sparseset_clear (conflict_reload_and_inheritance_pseudos
);
511 sparseset_clear (live_range_hard_reg_pseudos
);
512 IOR_HARD_REG_SET (conflict_set
, lra_reg_info
[regno
].conflict_hard_regs
);
513 biggest_mode
= lra_reg_info
[regno
].biggest_mode
;
514 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
516 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos
[r
->start
], 0, k
, bi
)
517 if (rclass_intersect_p
[regno_allocno_class_array
[k
]])
518 sparseset_set_bit (live_range_hard_reg_pseudos
, k
);
519 EXECUTE_IF_SET_IN_BITMAP (&live_reload_and_inheritance_pseudos
[r
->start
],
521 if (lra_reg_info
[k
].preferred_hard_regno1
>= 0
522 && live_pseudos_reg_renumber
[k
] < 0
523 && rclass_intersect_p
[regno_allocno_class_array
[k
]])
524 sparseset_set_bit (conflict_reload_and_inheritance_pseudos
, k
);
525 for (p
= r
->start
+ 1; p
<= r
->finish
; p
++)
529 for (r2
= start_point_ranges
[p
];
533 if (r2
->regno
>= lra_constraint_new_regno_start
534 && lra_reg_info
[r2
->regno
].preferred_hard_regno1
>= 0
535 && live_pseudos_reg_renumber
[r2
->regno
] < 0
536 && rclass_intersect_p
[regno_allocno_class_array
[r2
->regno
]])
537 sparseset_set_bit (conflict_reload_and_inheritance_pseudos
,
539 if (live_pseudos_reg_renumber
[r2
->regno
] >= 0
540 && rclass_intersect_p
[regno_allocno_class_array
[r2
->regno
]])
541 sparseset_set_bit (live_range_hard_reg_pseudos
, r2
->regno
);
545 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno1
) >= 0)
547 adjust_hard_regno_cost
548 (hard_regno
, -lra_reg_info
[regno
].preferred_hard_regno_profit1
);
549 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno2
) >= 0)
550 adjust_hard_regno_cost
551 (hard_regno
, -lra_reg_info
[regno
].preferred_hard_regno_profit2
);
554 if (lra_reg_info
[regno
].no_stack_p
)
555 for (i
= FIRST_STACK_REG
; i
<= LAST_STACK_REG
; i
++)
556 SET_HARD_REG_BIT (conflict_set
, i
);
558 sparseset_clear_bit (conflict_reload_and_inheritance_pseudos
, regno
);
559 val
= lra_reg_info
[regno
].val
;
560 offset
= lra_reg_info
[regno
].offset
;
561 CLEAR_HARD_REG_SET (impossible_start_hard_regs
);
562 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos
, conflict_regno
)
563 if (lra_reg_val_equal_p (conflict_regno
, val
, offset
))
565 conflict_hr
= live_pseudos_reg_renumber
[conflict_regno
];
566 nregs
= (hard_regno_nregs
[conflict_hr
]
567 [lra_reg_info
[conflict_regno
].biggest_mode
]);
568 /* Remember about multi-register pseudos. For example, 2 hard
569 register pseudos can start on the same hard register but can
570 not start on HR and HR+1/HR-1. */
571 for (hr
= conflict_hr
+ 1;
572 hr
< FIRST_PSEUDO_REGISTER
&& hr
< conflict_hr
+ nregs
;
574 SET_HARD_REG_BIT (impossible_start_hard_regs
, hr
);
575 for (hr
= conflict_hr
- 1;
576 hr
>= 0 && hr
+ hard_regno_nregs
[hr
][biggest_mode
] > conflict_hr
;
578 SET_HARD_REG_BIT (impossible_start_hard_regs
, hr
);
582 add_to_hard_reg_set (&conflict_set
,
583 lra_reg_info
[conflict_regno
].biggest_mode
,
584 live_pseudos_reg_renumber
[conflict_regno
]);
585 if (hard_reg_set_subset_p (reg_class_contents
[rclass
],
589 EXECUTE_IF_SET_IN_SPARSESET (conflict_reload_and_inheritance_pseudos
,
591 if (!lra_reg_val_equal_p (conflict_regno
, val
, offset
))
593 lra_assert (live_pseudos_reg_renumber
[conflict_regno
] < 0);
595 = lra_reg_info
[conflict_regno
].preferred_hard_regno1
) >= 0)
597 adjust_hard_regno_cost
599 lra_reg_info
[conflict_regno
].preferred_hard_regno_profit1
);
601 = lra_reg_info
[conflict_regno
].preferred_hard_regno2
) >= 0)
602 adjust_hard_regno_cost
604 lra_reg_info
[conflict_regno
].preferred_hard_regno_profit2
);
607 /* Make sure that all registers in a multi-word pseudo belong to the
609 IOR_COMPL_HARD_REG_SET (conflict_set
, reg_class_contents
[rclass
]);
610 lra_assert (rclass
!= NO_REGS
);
611 rclass_size
= ira_class_hard_regs_num
[rclass
];
612 best_hard_regno
= -1;
613 hard_regno
= ira_class_hard_regs
[rclass
][0];
614 biggest_nregs
= hard_regno_nregs
[hard_regno
][biggest_mode
];
615 nregs_diff
= (biggest_nregs
616 - hard_regno_nregs
[hard_regno
][PSEUDO_REGNO_MODE (regno
)]);
617 COPY_HARD_REG_SET (available_regs
, reg_class_contents
[rclass
]);
618 AND_COMPL_HARD_REG_SET (available_regs
, lra_no_alloc_regs
);
619 for (i
= 0; i
< rclass_size
; i
++)
621 if (try_only_hard_regno
>= 0)
622 hard_regno
= try_only_hard_regno
;
624 hard_regno
= ira_class_hard_regs
[rclass
][i
];
625 if (! overlaps_hard_reg_set_p (conflict_set
,
626 PSEUDO_REGNO_MODE (regno
), hard_regno
)
627 /* We can not use prohibited_class_mode_regs because it is
628 not defined for all classes. */
629 && HARD_REGNO_MODE_OK (hard_regno
, PSEUDO_REGNO_MODE (regno
))
630 && ! TEST_HARD_REG_BIT (impossible_start_hard_regs
, hard_regno
)
633 ? (hard_regno
- nregs_diff
>= 0
634 && TEST_HARD_REG_BIT (available_regs
,
635 hard_regno
- nregs_diff
))
636 : TEST_HARD_REG_BIT (available_regs
,
637 hard_regno
+ nregs_diff
))))
639 if (hard_regno_costs_check
[hard_regno
]
640 != curr_hard_regno_costs_check
)
642 hard_regno_costs_check
[hard_regno
] = curr_hard_regno_costs_check
;
643 hard_regno_costs
[hard_regno
] = 0;
646 j
< hard_regno_nregs
[hard_regno
][PSEUDO_REGNO_MODE (regno
)];
648 if (! TEST_HARD_REG_BIT (call_used_reg_set
, hard_regno
+ j
)
649 && ! df_regs_ever_live_p (hard_regno
+ j
))
650 /* It needs save restore. */
651 hard_regno_costs
[hard_regno
]
653 * REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
)
655 priority
= targetm
.register_priority (hard_regno
);
656 if (best_hard_regno
< 0 || hard_regno_costs
[hard_regno
] < best_cost
657 || (hard_regno_costs
[hard_regno
] == best_cost
658 && (priority
> best_priority
659 || (targetm
.register_usage_leveling_p ()
660 && priority
== best_priority
661 && best_usage
> lra_hard_reg_usage
[hard_regno
]))))
663 best_hard_regno
= hard_regno
;
664 best_cost
= hard_regno_costs
[hard_regno
];
665 best_priority
= priority
;
666 best_usage
= lra_hard_reg_usage
[hard_regno
];
669 if (try_only_hard_regno
>= 0 || (first_p
&& best_hard_regno
>= 0))
672 if (best_hard_regno
>= 0)
673 *cost
= best_cost
- lra_reg_info
[regno
].freq
;
674 return best_hard_regno
;
677 /* A wrapper for find_hard_regno_for_1 (see comments for that function
678 description). This function tries to find a hard register for
679 preferred class first if it is worth. */
681 find_hard_regno_for (int regno
, int *cost
, int try_only_hard_regno
, bool first_p
)
684 HARD_REG_SET regno_set
;
686 /* Only original pseudos can have a different preferred class. */
687 if (try_only_hard_regno
< 0 && regno
< lra_new_regno_start
)
689 enum reg_class pref_class
= reg_preferred_class (regno
);
691 if (regno_allocno_class_array
[regno
] != pref_class
)
693 hard_regno
= find_hard_regno_for_1 (regno
, cost
, -1, first_p
,
694 reg_class_contents
[pref_class
]);
699 CLEAR_HARD_REG_SET (regno_set
);
700 return find_hard_regno_for_1 (regno
, cost
, try_only_hard_regno
, first_p
,
704 /* Current value used for checking elements in
705 update_hard_regno_preference_check. */
706 static int curr_update_hard_regno_preference_check
;
707 /* If an element value is equal to the above variable value, then the
708 corresponding regno has been processed for preference
710 static int *update_hard_regno_preference_check
;
712 /* Update the preference for using HARD_REGNO for pseudos that are
713 connected directly or indirectly with REGNO. Apply divisor DIV
714 to any preference adjustments.
716 The more indirectly a pseudo is connected, the smaller its effect
717 should be. We therefore increase DIV on each "hop". */
719 update_hard_regno_preference (int regno
, int hard_regno
, int div
)
721 int another_regno
, cost
;
722 lra_copy_t cp
, next_cp
;
724 /* Search depth 5 seems to be enough. */
727 for (cp
= lra_reg_info
[regno
].copies
; cp
!= NULL
; cp
= next_cp
)
729 if (cp
->regno1
== regno
)
731 next_cp
= cp
->regno1_next
;
732 another_regno
= cp
->regno2
;
734 else if (cp
->regno2
== regno
)
736 next_cp
= cp
->regno2_next
;
737 another_regno
= cp
->regno1
;
741 if (reg_renumber
[another_regno
] < 0
742 && (update_hard_regno_preference_check
[another_regno
]
743 != curr_update_hard_regno_preference_check
))
745 update_hard_regno_preference_check
[another_regno
]
746 = curr_update_hard_regno_preference_check
;
747 cost
= cp
->freq
< div
? 1 : cp
->freq
/ div
;
748 lra_setup_reload_pseudo_preferenced_hard_reg
749 (another_regno
, hard_regno
, cost
);
750 update_hard_regno_preference (another_regno
, hard_regno
, div
* 2);
755 /* Return prefix title for pseudo REGNO. */
757 pseudo_prefix_title (int regno
)
760 (regno
< lra_constraint_new_regno_start
? ""
761 : bitmap_bit_p (&lra_inheritance_pseudos
, regno
) ? "inheritance "
762 : bitmap_bit_p (&lra_split_regs
, regno
) ? "split "
763 : bitmap_bit_p (&lra_optional_reload_pseudos
, regno
) ? "optional reload "
764 : bitmap_bit_p (&lra_subreg_reload_pseudos
, regno
) ? "subreg reload "
768 /* Update REG_RENUMBER and other pseudo preferences by assignment of
769 HARD_REGNO to pseudo REGNO and print about it if PRINT_P. */
771 lra_setup_reg_renumber (int regno
, int hard_regno
, bool print_p
)
775 /* We can not just reassign hard register. */
776 lra_assert (hard_regno
< 0 || reg_renumber
[regno
] < 0);
777 if ((hr
= hard_regno
) < 0)
778 hr
= reg_renumber
[regno
];
779 reg_renumber
[regno
] = hard_regno
;
780 lra_assert (hr
>= 0);
781 for (i
= 0; i
< hard_regno_nregs
[hr
][PSEUDO_REGNO_MODE (regno
)]; i
++)
783 lra_hard_reg_usage
[hr
+ i
] -= lra_reg_info
[regno
].freq
;
785 lra_hard_reg_usage
[hr
+ i
] += lra_reg_info
[regno
].freq
;
786 if (print_p
&& lra_dump_file
!= NULL
)
787 fprintf (lra_dump_file
, " Assign %d to %sr%d (freq=%d)\n",
788 reg_renumber
[regno
], pseudo_prefix_title (regno
),
789 regno
, lra_reg_info
[regno
].freq
);
792 curr_update_hard_regno_preference_check
++;
793 update_hard_regno_preference (regno
, hard_regno
, 1);
797 /* Pseudos which occur in insns containing a particular pseudo. */
798 static bitmap_head insn_conflict_pseudos
;
800 /* Bitmaps used to contain spill pseudos for given pseudo hard regno
801 and best spill pseudos for given pseudo (and best hard regno). */
802 static bitmap_head spill_pseudos_bitmap
, best_spill_pseudos_bitmap
;
804 /* Current pseudo check for validity of elements in
805 TRY_HARD_REG_PSEUDOS. */
806 static int curr_pseudo_check
;
807 /* Array used for validity of elements in TRY_HARD_REG_PSEUDOS. */
808 static int try_hard_reg_pseudos_check
[FIRST_PSEUDO_REGISTER
];
809 /* Pseudos who hold given hard register at the considered points. */
810 static bitmap_head try_hard_reg_pseudos
[FIRST_PSEUDO_REGISTER
];
812 /* Set up try_hard_reg_pseudos for given program point P and class
813 RCLASS. Those are pseudos living at P and assigned to a hard
814 register of RCLASS. In other words, those are pseudos which can be
815 spilled to assign a hard register of RCLASS to a pseudo living at
818 setup_try_hard_regno_pseudos (int p
, enum reg_class rclass
)
822 unsigned int spill_regno
;
825 /* Find what pseudos could be spilled. */
826 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos
[p
], 0, spill_regno
, bi
)
828 mode
= PSEUDO_REGNO_MODE (spill_regno
);
829 hard_regno
= live_pseudos_reg_renumber
[spill_regno
];
830 if (overlaps_hard_reg_set_p (reg_class_contents
[rclass
],
833 for (i
= hard_regno_nregs
[hard_regno
][mode
] - 1; i
>= 0; i
--)
835 if (try_hard_reg_pseudos_check
[hard_regno
+ i
]
836 != curr_pseudo_check
)
838 try_hard_reg_pseudos_check
[hard_regno
+ i
]
840 bitmap_clear (&try_hard_reg_pseudos
[hard_regno
+ i
]);
842 bitmap_set_bit (&try_hard_reg_pseudos
[hard_regno
+ i
],
849 /* Assign temporarily HARD_REGNO to pseudo REGNO. Temporary
850 assignment means that we might undo the data change. */
852 assign_temporarily (int regno
, int hard_regno
)
857 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
859 for (p
= r
->start
; p
<= r
->finish
; p
++)
861 bitmap_clear_bit (&live_hard_reg_pseudos
[p
], regno
);
864 bitmap_set_bit (&live_hard_reg_pseudos
[p
], regno
);
865 insert_in_live_range_start_chain (regno
);
868 live_pseudos_reg_renumber
[regno
] = hard_regno
;
871 /* Array used for sorting reload pseudos for subsequent allocation
872 after spilling some pseudo. */
873 static int *sorted_reload_pseudos
;
875 /* Spill some pseudos for a reload pseudo REGNO and return hard
876 register which should be used for pseudo after spilling. The
877 function adds spilled pseudos to SPILLED_PSEUDO_BITMAP. When we
878 choose hard register (and pseudos occupying the hard registers and
879 to be spilled), we take into account not only how REGNO will
880 benefit from the spills but also how other reload pseudos not yet
881 assigned to hard registers benefit from the spills too. In very
882 rare cases, the function can fail and return -1.
884 If FIRST_P, return the first available hard reg ignoring other
885 criteria, e.g. allocation cost and cost of spilling non-reload
886 pseudos. This approach results in less hard reg pool fragmentation
887 and permit to allocate hard regs to reload pseudos in complicated
888 situations where pseudo sizes are different. */
890 spill_for (int regno
, bitmap spilled_pseudo_bitmap
, bool first_p
)
892 int i
, j
, n
, p
, hard_regno
, best_hard_regno
, cost
, best_cost
, rclass_size
;
893 int reload_hard_regno
, reload_cost
;
895 enum reg_class rclass
;
896 unsigned int spill_regno
, reload_regno
, uid
;
897 int insn_pseudos_num
, best_insn_pseudos_num
;
898 int bad_spills_num
, smallest_bad_spills_num
;
902 rclass
= regno_allocno_class_array
[regno
];
903 lra_assert (reg_renumber
[regno
] < 0 && rclass
!= NO_REGS
);
904 bitmap_clear (&insn_conflict_pseudos
);
905 bitmap_clear (&best_spill_pseudos_bitmap
);
906 EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info
[regno
].insn_bitmap
, 0, uid
, bi
)
908 struct lra_insn_reg
*ir
;
910 for (ir
= lra_get_insn_regs (uid
); ir
!= NULL
; ir
= ir
->next
)
911 if (ir
->regno
>= FIRST_PSEUDO_REGISTER
)
912 bitmap_set_bit (&insn_conflict_pseudos
, ir
->regno
);
914 best_hard_regno
= -1;
916 best_insn_pseudos_num
= INT_MAX
;
917 smallest_bad_spills_num
= INT_MAX
;
918 rclass_size
= ira_class_hard_regs_num
[rclass
];
919 mode
= PSEUDO_REGNO_MODE (regno
);
920 /* Invalidate try_hard_reg_pseudos elements. */
922 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
923 for (p
= r
->start
; p
<= r
->finish
; p
++)
924 setup_try_hard_regno_pseudos (p
, rclass
);
925 for (i
= 0; i
< rclass_size
; i
++)
927 hard_regno
= ira_class_hard_regs
[rclass
][i
];
928 bitmap_clear (&spill_pseudos_bitmap
);
929 for (j
= hard_regno_nregs
[hard_regno
][mode
] - 1; j
>= 0; j
--)
931 if (try_hard_reg_pseudos_check
[hard_regno
+ j
] != curr_pseudo_check
)
933 lra_assert (!bitmap_empty_p (&try_hard_reg_pseudos
[hard_regno
+ j
]));
934 bitmap_ior_into (&spill_pseudos_bitmap
,
935 &try_hard_reg_pseudos
[hard_regno
+ j
]);
938 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
939 if ((pic_offset_table_rtx
!= NULL
940 && spill_regno
== REGNO (pic_offset_table_rtx
))
941 || ((int) spill_regno
>= lra_constraint_new_regno_start
942 && ! bitmap_bit_p (&lra_inheritance_pseudos
, spill_regno
)
943 && ! bitmap_bit_p (&lra_split_regs
, spill_regno
)
944 && ! bitmap_bit_p (&lra_subreg_reload_pseudos
, spill_regno
)
945 && ! bitmap_bit_p (&lra_optional_reload_pseudos
, spill_regno
)))
947 insn_pseudos_num
= 0;
949 if (lra_dump_file
!= NULL
)
950 fprintf (lra_dump_file
, " Trying %d:", hard_regno
);
951 sparseset_clear (live_range_reload_inheritance_pseudos
);
952 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
954 if (bitmap_bit_p (&insn_conflict_pseudos
, spill_regno
))
956 if (spill_regno
>= (unsigned int) lra_bad_spill_regno_start
)
958 for (r
= lra_reg_info
[spill_regno
].live_ranges
;
962 for (p
= r
->start
; p
<= r
->finish
; p
++)
966 for (r2
= start_point_ranges
[p
];
969 if (r2
->regno
>= lra_constraint_new_regno_start
)
970 sparseset_set_bit (live_range_reload_inheritance_pseudos
,
976 if (sparseset_cardinality (live_range_reload_inheritance_pseudos
)
977 <= (unsigned)LRA_MAX_CONSIDERED_RELOAD_PSEUDOS
)
978 EXECUTE_IF_SET_IN_SPARSESET (live_range_reload_inheritance_pseudos
,
980 if ((int) reload_regno
!= regno
981 && (ira_reg_classes_intersect_p
982 [rclass
][regno_allocno_class_array
[reload_regno
]])
983 && live_pseudos_reg_renumber
[reload_regno
] < 0
984 && find_hard_regno_for (reload_regno
, &cost
, -1, first_p
) < 0)
985 sorted_reload_pseudos
[n
++] = reload_regno
;
986 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
988 update_lives (spill_regno
, true);
989 if (lra_dump_file
!= NULL
)
990 fprintf (lra_dump_file
, " spill %d(freq=%d)",
991 spill_regno
, lra_reg_info
[spill_regno
].freq
);
993 hard_regno
= find_hard_regno_for (regno
, &cost
, -1, first_p
);
996 assign_temporarily (regno
, hard_regno
);
997 qsort (sorted_reload_pseudos
, n
, sizeof (int),
998 reload_pseudo_compare_func
);
999 for (j
= 0; j
< n
; j
++)
1001 reload_regno
= sorted_reload_pseudos
[j
];
1002 lra_assert (live_pseudos_reg_renumber
[reload_regno
] < 0);
1003 if ((reload_hard_regno
1004 = find_hard_regno_for (reload_regno
,
1005 &reload_cost
, -1, first_p
)) >= 0)
1007 if (lra_dump_file
!= NULL
)
1008 fprintf (lra_dump_file
, " assign %d(cost=%d)",
1009 reload_regno
, reload_cost
);
1010 assign_temporarily (reload_regno
, reload_hard_regno
);
1011 cost
+= reload_cost
;
1014 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
1018 cost
+= lra_reg_info
[spill_regno
].freq
;
1019 if (ira_reg_equiv
[spill_regno
].memory
!= NULL
1020 || ira_reg_equiv
[spill_regno
].constant
!= NULL
)
1021 for (x
= ira_reg_equiv
[spill_regno
].init_insns
;
1024 cost
-= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (x
->insn ()));
1026 if (best_insn_pseudos_num
> insn_pseudos_num
1027 || (best_insn_pseudos_num
== insn_pseudos_num
1028 && (bad_spills_num
< smallest_bad_spills_num
1029 || (bad_spills_num
== smallest_bad_spills_num
1030 && best_cost
> cost
))))
1032 best_insn_pseudos_num
= insn_pseudos_num
;
1033 smallest_bad_spills_num
= bad_spills_num
;
1035 best_hard_regno
= hard_regno
;
1036 bitmap_copy (&best_spill_pseudos_bitmap
, &spill_pseudos_bitmap
);
1037 if (lra_dump_file
!= NULL
)
1038 fprintf (lra_dump_file
,
1039 " Now best %d(cost=%d, bad_spills=%d, insn_pseudos=%d)\n",
1040 hard_regno
, cost
, bad_spills_num
, insn_pseudos_num
);
1042 assign_temporarily (regno
, -1);
1043 for (j
= 0; j
< n
; j
++)
1045 reload_regno
= sorted_reload_pseudos
[j
];
1046 if (live_pseudos_reg_renumber
[reload_regno
] >= 0)
1047 assign_temporarily (reload_regno
, -1);
1050 if (lra_dump_file
!= NULL
)
1051 fprintf (lra_dump_file
, "\n");
1052 /* Restore the live hard reg pseudo info for spilled pseudos. */
1053 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
1054 update_lives (spill_regno
, false);
1059 EXECUTE_IF_SET_IN_BITMAP (&best_spill_pseudos_bitmap
, 0, spill_regno
, bi
)
1061 if ((int) spill_regno
>= lra_constraint_new_regno_start
)
1062 former_reload_pseudo_spill_p
= true;
1063 if (lra_dump_file
!= NULL
)
1064 fprintf (lra_dump_file
, " Spill %sr%d(hr=%d, freq=%d) for r%d\n",
1065 pseudo_prefix_title (spill_regno
),
1066 spill_regno
, reg_renumber
[spill_regno
],
1067 lra_reg_info
[spill_regno
].freq
, regno
);
1068 update_lives (spill_regno
, true);
1069 lra_setup_reg_renumber (spill_regno
, -1, false);
1071 bitmap_ior_into (spilled_pseudo_bitmap
, &best_spill_pseudos_bitmap
);
1072 return best_hard_regno
;
1075 /* Assign HARD_REGNO to REGNO. */
1077 assign_hard_regno (int hard_regno
, int regno
)
1081 lra_assert (hard_regno
>= 0);
1082 lra_setup_reg_renumber (regno
, hard_regno
, true);
1083 update_lives (regno
, false);
1085 i
< hard_regno_nregs
[hard_regno
][lra_reg_info
[regno
].biggest_mode
];
1087 df_set_regs_ever_live (hard_regno
+ i
, true);
1090 /* Array used for sorting different pseudos. */
1091 static int *sorted_pseudos
;
1093 /* The constraints pass is allowed to create equivalences between
1094 pseudos that make the current allocation "incorrect" (in the sense
1095 that pseudos are assigned to hard registers from their own conflict
1096 sets). The global variable lra_risky_transformations_p says
1097 whether this might have happened.
1099 Process pseudos assigned to hard registers (less frequently used
1100 first), spill if a conflict is found, and mark the spilled pseudos
1101 in SPILLED_PSEUDO_BITMAP. Set up LIVE_HARD_REG_PSEUDOS from
1102 pseudos, assigned to hard registers. */
1104 setup_live_pseudos_and_spill_after_risky_transforms (bitmap
1105 spilled_pseudo_bitmap
)
1107 int p
, i
, j
, n
, regno
, hard_regno
;
1108 unsigned int k
, conflict_regno
;
1110 HARD_REG_SET conflict_set
;
1114 int max_regno
= max_reg_num ();
1116 if (! lra_risky_transformations_p
)
1118 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1119 if (reg_renumber
[i
] >= 0 && lra_reg_info
[i
].nrefs
> 0)
1120 update_lives (i
, false);
1123 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1124 if ((pic_offset_table_rtx
== NULL_RTX
1125 || i
!= (int) REGNO (pic_offset_table_rtx
))
1126 && reg_renumber
[i
] >= 0 && lra_reg_info
[i
].nrefs
> 0)
1127 sorted_pseudos
[n
++] = i
;
1128 qsort (sorted_pseudos
, n
, sizeof (int), pseudo_compare_func
);
1129 if (pic_offset_table_rtx
!= NULL_RTX
1130 && (regno
= REGNO (pic_offset_table_rtx
)) >= FIRST_PSEUDO_REGISTER
1131 && reg_renumber
[regno
] >= 0 && lra_reg_info
[regno
].nrefs
> 0)
1132 sorted_pseudos
[n
++] = regno
;
1133 for (i
= n
- 1; i
>= 0; i
--)
1135 regno
= sorted_pseudos
[i
];
1136 hard_regno
= reg_renumber
[regno
];
1137 lra_assert (hard_regno
>= 0);
1138 mode
= lra_reg_info
[regno
].biggest_mode
;
1139 sparseset_clear (live_range_hard_reg_pseudos
);
1140 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
1142 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos
[r
->start
], 0, k
, bi
)
1143 sparseset_set_bit (live_range_hard_reg_pseudos
, k
);
1144 for (p
= r
->start
+ 1; p
<= r
->finish
; p
++)
1146 lra_live_range_t r2
;
1148 for (r2
= start_point_ranges
[p
];
1150 r2
= r2
->start_next
)
1151 if (live_pseudos_reg_renumber
[r2
->regno
] >= 0)
1152 sparseset_set_bit (live_range_hard_reg_pseudos
, r2
->regno
);
1155 COPY_HARD_REG_SET (conflict_set
, lra_no_alloc_regs
);
1156 IOR_HARD_REG_SET (conflict_set
, lra_reg_info
[regno
].conflict_hard_regs
);
1157 val
= lra_reg_info
[regno
].val
;
1158 offset
= lra_reg_info
[regno
].offset
;
1159 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos
, conflict_regno
)
1160 if (!lra_reg_val_equal_p (conflict_regno
, val
, offset
)
1161 /* If it is multi-register pseudos they should start on
1162 the same hard register. */
1163 || hard_regno
!= reg_renumber
[conflict_regno
])
1164 add_to_hard_reg_set (&conflict_set
,
1165 lra_reg_info
[conflict_regno
].biggest_mode
,
1166 reg_renumber
[conflict_regno
]);
1167 if (! overlaps_hard_reg_set_p (conflict_set
, mode
, hard_regno
))
1169 update_lives (regno
, false);
1172 bitmap_set_bit (spilled_pseudo_bitmap
, regno
);
1174 j
< hard_regno_nregs
[hard_regno
][PSEUDO_REGNO_MODE (regno
)];
1176 lra_hard_reg_usage
[hard_regno
+ j
] -= lra_reg_info
[regno
].freq
;
1177 reg_renumber
[regno
] = -1;
1178 if (regno
>= lra_constraint_new_regno_start
)
1179 former_reload_pseudo_spill_p
= true;
1180 if (lra_dump_file
!= NULL
)
1181 fprintf (lra_dump_file
, " Spill r%d after risky transformations\n",
1186 /* Improve allocation by assigning the same hard regno of inheritance
1187 pseudos to the connected pseudos. We need this because inheritance
1188 pseudos are allocated after reload pseudos in the thread and when
1189 we assign a hard register to a reload pseudo we don't know yet that
1190 the connected inheritance pseudos can get the same hard register.
1191 Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS. */
1193 improve_inheritance (bitmap changed_pseudos
)
1196 int regno
, another_regno
, hard_regno
, another_hard_regno
, cost
, i
, n
;
1197 lra_copy_t cp
, next_cp
;
1200 if (lra_inheritance_iter
> LRA_MAX_INHERITANCE_PASSES
)
1203 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos
, 0, k
, bi
)
1204 if (reg_renumber
[k
] >= 0 && lra_reg_info
[k
].nrefs
!= 0)
1205 sorted_pseudos
[n
++] = k
;
1206 qsort (sorted_pseudos
, n
, sizeof (int), pseudo_compare_func
);
1207 for (i
= 0; i
< n
; i
++)
1209 regno
= sorted_pseudos
[i
];
1210 hard_regno
= reg_renumber
[regno
];
1211 lra_assert (hard_regno
>= 0);
1212 for (cp
= lra_reg_info
[regno
].copies
; cp
!= NULL
; cp
= next_cp
)
1214 if (cp
->regno1
== regno
)
1216 next_cp
= cp
->regno1_next
;
1217 another_regno
= cp
->regno2
;
1219 else if (cp
->regno2
== regno
)
1221 next_cp
= cp
->regno2_next
;
1222 another_regno
= cp
->regno1
;
1226 /* Don't change reload pseudo allocation. It might have
1227 this allocation for a purpose and changing it can result
1229 if ((another_regno
< lra_constraint_new_regno_start
1230 || bitmap_bit_p (&lra_inheritance_pseudos
, another_regno
))
1231 && (another_hard_regno
= reg_renumber
[another_regno
]) >= 0
1232 && another_hard_regno
!= hard_regno
)
1234 if (lra_dump_file
!= NULL
)
1237 " Improving inheritance for %d(%d) and %d(%d)...\n",
1238 regno
, hard_regno
, another_regno
, another_hard_regno
);
1239 update_lives (another_regno
, true);
1240 lra_setup_reg_renumber (another_regno
, -1, false);
1241 if (hard_regno
== find_hard_regno_for (another_regno
, &cost
,
1243 assign_hard_regno (hard_regno
, another_regno
);
1245 assign_hard_regno (another_hard_regno
, another_regno
);
1246 bitmap_set_bit (changed_pseudos
, another_regno
);
1253 /* Bitmap finally containing all pseudos spilled on this assignment
1255 static bitmap_head all_spilled_pseudos
;
1256 /* All pseudos whose allocation was changed. */
1257 static bitmap_head changed_pseudo_bitmap
;
1260 /* Add to LIVE_RANGE_HARD_REG_PSEUDOS all pseudos conflicting with
1261 REGNO and whose hard regs can be assigned to REGNO. */
1263 find_all_spills_for (int regno
)
1269 enum reg_class rclass
;
1270 bool *rclass_intersect_p
;
1272 rclass
= regno_allocno_class_array
[regno
];
1273 rclass_intersect_p
= ira_reg_classes_intersect_p
[rclass
];
1274 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
1276 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos
[r
->start
], 0, k
, bi
)
1277 if (rclass_intersect_p
[regno_allocno_class_array
[k
]])
1278 sparseset_set_bit (live_range_hard_reg_pseudos
, k
);
1279 for (p
= r
->start
+ 1; p
<= r
->finish
; p
++)
1281 lra_live_range_t r2
;
1283 for (r2
= start_point_ranges
[p
];
1285 r2
= r2
->start_next
)
1287 if (live_pseudos_reg_renumber
[r2
->regno
] >= 0
1288 && rclass_intersect_p
[regno_allocno_class_array
[r2
->regno
]])
1289 sparseset_set_bit (live_range_hard_reg_pseudos
, r2
->regno
);
1295 /* Assign hard registers to reload pseudos and other pseudos. */
1297 assign_by_spills (void)
1299 int i
, n
, nfails
, iter
, regno
, hard_regno
, cost
, restore_regno
;
1301 bitmap_head changed_insns
, do_not_assign_nonreload_pseudos
;
1302 unsigned int u
, conflict_regno
;
1305 int max_regno
= max_reg_num ();
1307 for (n
= 0, i
= lra_constraint_new_regno_start
; i
< max_regno
; i
++)
1308 if (reg_renumber
[i
] < 0 && lra_reg_info
[i
].nrefs
!= 0
1309 && regno_allocno_class_array
[i
] != NO_REGS
)
1310 sorted_pseudos
[n
++] = i
;
1311 bitmap_initialize (&insn_conflict_pseudos
, ®_obstack
);
1312 bitmap_initialize (&spill_pseudos_bitmap
, ®_obstack
);
1313 bitmap_initialize (&best_spill_pseudos_bitmap
, ®_obstack
);
1314 update_hard_regno_preference_check
= XCNEWVEC (int, max_regno
);
1315 curr_update_hard_regno_preference_check
= 0;
1316 memset (try_hard_reg_pseudos_check
, 0, sizeof (try_hard_reg_pseudos_check
));
1317 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1318 bitmap_initialize (&try_hard_reg_pseudos
[i
], ®_obstack
);
1319 curr_pseudo_check
= 0;
1320 bitmap_initialize (&changed_insns
, ®_obstack
);
1321 bitmap_initialize (&non_reload_pseudos
, ®_obstack
);
1322 bitmap_ior (&non_reload_pseudos
, &lra_inheritance_pseudos
, &lra_split_regs
);
1323 bitmap_ior_into (&non_reload_pseudos
, &lra_subreg_reload_pseudos
);
1324 bitmap_ior_into (&non_reload_pseudos
, &lra_optional_reload_pseudos
);
1325 for (iter
= 0; iter
<= 1; iter
++)
1327 qsort (sorted_pseudos
, n
, sizeof (int), reload_pseudo_compare_func
);
1329 for (i
= 0; i
< n
; i
++)
1331 regno
= sorted_pseudos
[i
];
1332 if (lra_dump_file
!= NULL
)
1333 fprintf (lra_dump_file
, " Assigning to %d "
1334 "(cl=%s, orig=%d, freq=%d, tfirst=%d, tfreq=%d)...\n",
1335 regno
, reg_class_names
[regno_allocno_class_array
[regno
]],
1336 ORIGINAL_REGNO (regno_reg_rtx
[regno
]),
1337 lra_reg_info
[regno
].freq
, regno_assign_info
[regno
].first
,
1338 regno_assign_info
[regno_assign_info
[regno
].first
].freq
);
1339 hard_regno
= find_hard_regno_for (regno
, &cost
, -1, iter
== 1);
1340 reload_p
= ! bitmap_bit_p (&non_reload_pseudos
, regno
);
1341 if (hard_regno
< 0 && reload_p
)
1342 hard_regno
= spill_for (regno
, &all_spilled_pseudos
, iter
== 1);
1346 sorted_pseudos
[nfails
++] = regno
;
1350 /* This register might have been spilled by the previous
1351 pass. Indicate that it is no longer spilled. */
1352 bitmap_clear_bit (&all_spilled_pseudos
, regno
);
1353 assign_hard_regno (hard_regno
, regno
);
1355 /* As non-reload pseudo assignment is changed we
1356 should reconsider insns referring for the
1358 bitmap_set_bit (&changed_pseudo_bitmap
, regno
);
1365 /* We did not assign hard regs to reload pseudos after two iterations.
1366 Either it's an asm and something is wrong with the constraints, or
1367 we have run out of spill registers; error out in either case. */
1369 bitmap_head failed_reload_insns
;
1371 bitmap_initialize (&failed_reload_insns
, ®_obstack
);
1372 for (i
= 0; i
< nfails
; i
++)
1374 regno
= sorted_pseudos
[i
];
1375 bitmap_ior_into (&failed_reload_insns
,
1376 &lra_reg_info
[regno
].insn_bitmap
);
1377 /* Assign an arbitrary hard register of regno class to
1378 avoid further trouble with this insn. */
1379 bitmap_clear_bit (&all_spilled_pseudos
, regno
);
1381 (ira_class_hard_regs
[regno_allocno_class_array
[regno
]][0],
1384 EXECUTE_IF_SET_IN_BITMAP (&failed_reload_insns
, 0, u
, bi
)
1386 insn
= lra_insn_recog_data
[u
]->insn
;
1387 if (asm_noperands (PATTERN (insn
)) >= 0)
1390 error_for_asm (insn
,
1391 "%<asm%> operand has impossible constraints");
1392 /* Avoid further trouble with this insn.
1393 For asm goto, instead of fixing up all the edges
1394 just clear the template and clear input operands
1395 (asm goto doesn't have any output operands). */
1398 rtx asm_op
= extract_asm_operands (PATTERN (insn
));
1399 ASM_OPERANDS_TEMPLATE (asm_op
) = ggc_strdup ("");
1400 ASM_OPERANDS_INPUT_VEC (asm_op
) = rtvec_alloc (0);
1401 ASM_OPERANDS_INPUT_CONSTRAINT_VEC (asm_op
) = rtvec_alloc (0);
1402 lra_update_insn_regno_info (insn
);
1406 PATTERN (insn
) = gen_rtx_USE (VOIDmode
, const0_rtx
);
1407 lra_set_insn_deleted (insn
);
1412 error ("unable to find a register to spill");
1413 fatal_insn ("this is the insn:", insn
);
1418 /* This is a very rare event. We can not assign a hard register
1419 to reload pseudo because the hard register was assigned to
1420 another reload pseudo on a previous assignment pass. For x86
1421 example, on the 1st pass we assigned CX (although another
1422 hard register could be used for this) to reload pseudo in an
1423 insn, on the 2nd pass we need CX (and only this) hard
1424 register for a new reload pseudo in the same insn. Another
1425 possible situation may occur in assigning to multi-regs
1426 reload pseudos when hard regs pool is too fragmented even
1427 after spilling non-reload pseudos.
1429 We should do something radical here to succeed. Here we
1430 spill *all* conflicting pseudos and reassign them. */
1431 if (lra_dump_file
!= NULL
)
1432 fprintf (lra_dump_file
, " 2nd iter for reload pseudo assignments:\n");
1433 sparseset_clear (live_range_hard_reg_pseudos
);
1434 for (i
= 0; i
< nfails
; i
++)
1436 if (lra_dump_file
!= NULL
)
1437 fprintf (lra_dump_file
, " Reload r%d assignment failure\n",
1439 find_all_spills_for (sorted_pseudos
[i
]);
1441 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos
, conflict_regno
)
1443 if ((int) conflict_regno
>= lra_constraint_new_regno_start
)
1445 sorted_pseudos
[nfails
++] = conflict_regno
;
1446 former_reload_pseudo_spill_p
= true;
1448 if (lra_dump_file
!= NULL
)
1449 fprintf (lra_dump_file
, " Spill %s r%d(hr=%d, freq=%d)\n",
1450 pseudo_prefix_title (conflict_regno
), conflict_regno
,
1451 reg_renumber
[conflict_regno
],
1452 lra_reg_info
[conflict_regno
].freq
);
1453 update_lives (conflict_regno
, true);
1454 lra_setup_reg_renumber (conflict_regno
, -1, false);
1458 improve_inheritance (&changed_pseudo_bitmap
);
1459 bitmap_clear (&non_reload_pseudos
);
1460 bitmap_clear (&changed_insns
);
1463 /* We should not assign to original pseudos of inheritance
1464 pseudos or split pseudos if any its inheritance pseudo did
1465 not get hard register or any its split pseudo was not split
1466 because undo inheritance/split pass will extend live range of
1467 such inheritance or split pseudos. */
1468 bitmap_initialize (&do_not_assign_nonreload_pseudos
, ®_obstack
);
1469 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos
, 0, u
, bi
)
1470 if ((restore_regno
= lra_reg_info
[u
].restore_regno
) >= 0
1471 && reg_renumber
[u
] < 0
1472 && bitmap_bit_p (&lra_inheritance_pseudos
, u
))
1473 bitmap_set_bit (&do_not_assign_nonreload_pseudos
, restore_regno
);
1474 EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs
, 0, u
, bi
)
1475 if ((restore_regno
= lra_reg_info
[u
].restore_regno
) >= 0
1476 && reg_renumber
[u
] >= 0)
1477 bitmap_set_bit (&do_not_assign_nonreload_pseudos
, restore_regno
);
1478 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1479 if (((i
< lra_constraint_new_regno_start
1480 && ! bitmap_bit_p (&do_not_assign_nonreload_pseudos
, i
))
1481 || (bitmap_bit_p (&lra_inheritance_pseudos
, i
)
1482 && lra_reg_info
[i
].restore_regno
>= 0)
1483 || (bitmap_bit_p (&lra_split_regs
, i
)
1484 && lra_reg_info
[i
].restore_regno
>= 0)
1485 || bitmap_bit_p (&lra_subreg_reload_pseudos
, i
)
1486 || bitmap_bit_p (&lra_optional_reload_pseudos
, i
))
1487 && reg_renumber
[i
] < 0 && lra_reg_info
[i
].nrefs
!= 0
1488 && regno_allocno_class_array
[i
] != NO_REGS
)
1489 sorted_pseudos
[n
++] = i
;
1490 bitmap_clear (&do_not_assign_nonreload_pseudos
);
1491 if (n
!= 0 && lra_dump_file
!= NULL
)
1492 fprintf (lra_dump_file
, " Reassigning non-reload pseudos\n");
1493 qsort (sorted_pseudos
, n
, sizeof (int), pseudo_compare_func
);
1494 for (i
= 0; i
< n
; i
++)
1496 regno
= sorted_pseudos
[i
];
1497 hard_regno
= find_hard_regno_for (regno
, &cost
, -1, false);
1498 if (hard_regno
>= 0)
1500 assign_hard_regno (hard_regno
, regno
);
1501 /* We change allocation for non-reload pseudo on this
1502 iteration -- mark the pseudo for invalidation of used
1503 alternatives of insns containing the pseudo. */
1504 bitmap_set_bit (&changed_pseudo_bitmap
, regno
);
1508 enum reg_class rclass
= lra_get_allocno_class (regno
);
1509 enum reg_class spill_class
;
1511 if (targetm
.spill_class
== NULL
1512 || lra_reg_info
[regno
].restore_regno
< 0
1513 || ! bitmap_bit_p (&lra_inheritance_pseudos
, regno
)
1517 ((reg_class_t
) rclass
,
1518 PSEUDO_REGNO_MODE (regno
)))) == NO_REGS
)
1520 regno_allocno_class_array
[regno
] = spill_class
;
1521 hard_regno
= find_hard_regno_for (regno
, &cost
, -1, false);
1523 regno_allocno_class_array
[regno
] = rclass
;
1527 (regno
, spill_class
, spill_class
, spill_class
);
1528 assign_hard_regno (hard_regno
, regno
);
1529 bitmap_set_bit (&changed_pseudo_bitmap
, regno
);
1534 free (update_hard_regno_preference_check
);
1535 bitmap_clear (&best_spill_pseudos_bitmap
);
1536 bitmap_clear (&spill_pseudos_bitmap
);
1537 bitmap_clear (&insn_conflict_pseudos
);
1541 /* Entry function to assign hard registers to new reload pseudos
1542 starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling
1543 of old pseudos) and possibly to the old pseudos. The function adds
1544 what insns to process for the next constraint pass. Those are all
1545 insns who contains non-reload and non-inheritance pseudos with
1548 Return true if we did not spill any non-reload and non-inheritance
1556 bitmap_head insns_to_process
;
1558 int max_regno
= max_reg_num ();
1560 timevar_push (TV_LRA_ASSIGN
);
1561 lra_assignment_iter
++;
1562 if (lra_dump_file
!= NULL
)
1563 fprintf (lra_dump_file
, "\n********** Assignment #%d: **********\n\n",
1564 lra_assignment_iter
);
1566 sorted_pseudos
= XNEWVEC (int, max_regno
);
1567 sorted_reload_pseudos
= XNEWVEC (int, max_regno
);
1568 regno_allocno_class_array
= XNEWVEC (enum reg_class
, max_regno
);
1569 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1570 regno_allocno_class_array
[i
] = lra_get_allocno_class (i
);
1571 former_reload_pseudo_spill_p
= false;
1572 init_regno_assign_info ();
1573 bitmap_initialize (&all_spilled_pseudos
, ®_obstack
);
1574 create_live_range_start_chains ();
1575 setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos
);
1576 #ifdef ENABLE_CHECKING
1578 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1579 if (lra_reg_info
[i
].nrefs
!= 0 && reg_renumber
[i
] >= 0
1580 && lra_reg_info
[i
].call_p
1581 && overlaps_hard_reg_set_p (call_used_reg_set
,
1582 PSEUDO_REGNO_MODE (i
), reg_renumber
[i
]))
1585 /* Setup insns to process on the next constraint pass. */
1586 bitmap_initialize (&changed_pseudo_bitmap
, ®_obstack
);
1587 init_live_reload_and_inheritance_pseudos ();
1588 assign_by_spills ();
1589 finish_live_reload_and_inheritance_pseudos ();
1590 bitmap_ior_into (&changed_pseudo_bitmap
, &all_spilled_pseudos
);
1592 EXECUTE_IF_SET_IN_BITMAP (&all_spilled_pseudos
, 0, u
, bi
)
1593 /* We ignore spilled pseudos created on last inheritance pass
1594 because they will be removed. */
1595 if (lra_reg_info
[u
].restore_regno
< 0)
1597 no_spills_p
= false;
1600 finish_live_range_start_chains ();
1601 bitmap_clear (&all_spilled_pseudos
);
1602 bitmap_initialize (&insns_to_process
, ®_obstack
);
1603 EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap
, 0, u
, bi
)
1604 bitmap_ior_into (&insns_to_process
, &lra_reg_info
[u
].insn_bitmap
);
1605 bitmap_clear (&changed_pseudo_bitmap
);
1606 EXECUTE_IF_SET_IN_BITMAP (&insns_to_process
, 0, u
, bi
)
1608 lra_push_insn_by_uid (u
);
1609 /* Invalidate alternatives for insn should be processed. */
1610 lra_set_used_insn_alternative_by_uid (u
, -1);
1612 bitmap_clear (&insns_to_process
);
1613 finish_regno_assign_info ();
1614 free (regno_allocno_class_array
);
1615 free (sorted_pseudos
);
1616 free (sorted_reload_pseudos
);
1618 timevar_pop (TV_LRA_ASSIGN
);
1619 if (former_reload_pseudo_spill_p
)
1620 lra_assignment_iter_after_spill
++;
1621 if (lra_assignment_iter_after_spill
> LRA_MAX_ASSIGNMENT_ITERATION_NUMBER
)
1623 ("Maximum number of LRA assignment passes is achieved (%d)\n",
1624 LRA_MAX_ASSIGNMENT_ITERATION_NUMBER
);