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"
99 /* Array containing corresponding values of function
100 lra_get_allocno_class. It is used to speed up the code. */
101 static enum reg_class
*regno_allocno_class_array
;
103 /* Information about the thread to which a pseudo belongs. Threads are
104 a set of connected reload and inheritance pseudos with the same set of
105 available hard registers. Lone registers belong to their own threads. */
106 struct regno_assign_info
108 /* First/next pseudo of the same thread. */
110 /* Frequency of the thread (execution frequency of only reload
111 pseudos in the thread when the thread contains a reload pseudo).
112 Defined only for the first thread pseudo. */
116 /* Map regno to the corresponding regno assignment info. */
117 static struct regno_assign_info
*regno_assign_info
;
119 /* All inherited, subreg or optional pseudos created before last spill
120 sub-pass. Such pseudos are permitted to get memory instead of hard
122 static bitmap_head non_reload_pseudos
;
124 /* Process a pseudo copy with execution frequency COPY_FREQ connecting
125 REGNO1 and REGNO2 to form threads. */
127 process_copy_to_form_thread (int regno1
, int regno2
, int copy_freq
)
129 int last
, regno1_first
, regno2_first
;
131 lra_assert (regno1
>= lra_constraint_new_regno_start
132 && regno2
>= lra_constraint_new_regno_start
);
133 regno1_first
= regno_assign_info
[regno1
].first
;
134 regno2_first
= regno_assign_info
[regno2
].first
;
135 if (regno1_first
!= regno2_first
)
137 for (last
= regno2_first
;
138 regno_assign_info
[last
].next
>= 0;
139 last
= regno_assign_info
[last
].next
)
140 regno_assign_info
[last
].first
= regno1_first
;
141 regno_assign_info
[last
].first
= regno1_first
;
142 regno_assign_info
[last
].next
= regno_assign_info
[regno1_first
].next
;
143 regno_assign_info
[regno1_first
].next
= regno2_first
;
144 regno_assign_info
[regno1_first
].freq
145 += regno_assign_info
[regno2_first
].freq
;
147 regno_assign_info
[regno1_first
].freq
-= 2 * copy_freq
;
148 lra_assert (regno_assign_info
[regno1_first
].freq
>= 0);
151 /* Initialize REGNO_ASSIGN_INFO and form threads. */
153 init_regno_assign_info (void)
155 int i
, regno1
, regno2
, max_regno
= max_reg_num ();
158 regno_assign_info
= XNEWVEC (struct regno_assign_info
, max_regno
);
159 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
161 regno_assign_info
[i
].first
= i
;
162 regno_assign_info
[i
].next
= -1;
163 regno_assign_info
[i
].freq
= lra_reg_info
[i
].freq
;
165 /* Form the threads. */
166 for (i
= 0; (cp
= lra_get_copy (i
)) != NULL
; i
++)
167 if ((regno1
= cp
->regno1
) >= lra_constraint_new_regno_start
168 && (regno2
= cp
->regno2
) >= lra_constraint_new_regno_start
169 && reg_renumber
[regno1
] < 0 && lra_reg_info
[regno1
].nrefs
!= 0
170 && reg_renumber
[regno2
] < 0 && lra_reg_info
[regno2
].nrefs
!= 0
171 && (ira_class_hard_regs_num
[regno_allocno_class_array
[regno1
]]
172 == ira_class_hard_regs_num
[regno_allocno_class_array
[regno2
]]))
173 process_copy_to_form_thread (regno1
, regno2
, cp
->freq
);
176 /* Free REGNO_ASSIGN_INFO. */
178 finish_regno_assign_info (void)
180 free (regno_assign_info
);
183 /* The function is used to sort *reload* and *inheritance* pseudos to
184 try to assign them hard registers. We put pseudos from the same
185 thread always nearby. */
187 reload_pseudo_compare_func (const void *v1p
, const void *v2p
)
189 int r1
= *(const int *) v1p
, r2
= *(const int *) v2p
;
190 enum reg_class cl1
= regno_allocno_class_array
[r1
];
191 enum reg_class cl2
= regno_allocno_class_array
[r2
];
194 lra_assert (r1
>= lra_constraint_new_regno_start
195 && r2
>= lra_constraint_new_regno_start
);
197 /* Prefer to assign reload registers with smaller classes first to
198 guarantee assignment to all reload registers. */
199 if ((diff
= (ira_class_hard_regs_num
[cl1
]
200 - ira_class_hard_regs_num
[cl2
])) != 0)
203 = (ira_reg_class_max_nregs
[cl2
][lra_reg_info
[r2
].biggest_mode
]
204 - ira_reg_class_max_nregs
[cl1
][lra_reg_info
[r1
].biggest_mode
])) != 0
205 /* The code below executes rarely as nregs == 1 in most cases.
206 So we should not worry about using faster data structures to
207 check reload pseudos. */
208 && ! bitmap_bit_p (&non_reload_pseudos
, r1
)
209 && ! bitmap_bit_p (&non_reload_pseudos
, r2
))
211 if ((diff
= (regno_assign_info
[regno_assign_info
[r2
].first
].freq
212 - regno_assign_info
[regno_assign_info
[r1
].first
].freq
)) != 0)
214 /* Allocate bigger pseudos first to avoid register file
217 = (ira_reg_class_max_nregs
[cl2
][lra_reg_info
[r2
].biggest_mode
]
218 - ira_reg_class_max_nregs
[cl1
][lra_reg_info
[r1
].biggest_mode
])) != 0)
220 /* Put pseudos from the thread nearby. */
221 if ((diff
= regno_assign_info
[r1
].first
- regno_assign_info
[r2
].first
) != 0)
223 /* If regs are equally good, sort by their numbers, so that the
224 results of qsort leave nothing to chance. */
228 /* The function is used to sort *non-reload* pseudos to try to assign
229 them hard registers. The order calculation is simpler than in the
230 previous function and based on the pseudo frequency usage. */
232 pseudo_compare_func (const void *v1p
, const void *v2p
)
234 int r1
= *(const int *) v1p
, r2
= *(const int *) v2p
;
237 /* Prefer to assign more frequently used registers first. */
238 if ((diff
= lra_reg_info
[r2
].freq
- lra_reg_info
[r1
].freq
) != 0)
241 /* If regs are equally good, sort by their numbers, so that the
242 results of qsort leave nothing to chance. */
246 /* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the
247 pseudo live ranges with given start point. We insert only live
248 ranges of pseudos interesting for assignment purposes. They are
249 reload pseudos and pseudos assigned to hard registers. */
250 static lra_live_range_t
*start_point_ranges
;
252 /* Used as a flag that a live range is not inserted in the start point
254 static struct lra_live_range not_in_chain_mark
;
256 /* Create and set up START_POINT_RANGES. */
258 create_live_range_start_chains (void)
263 start_point_ranges
= XCNEWVEC (lra_live_range_t
, lra_live_max_point
);
264 max_regno
= max_reg_num ();
265 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
266 if (i
>= lra_constraint_new_regno_start
|| reg_renumber
[i
] >= 0)
268 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
270 r
->start_next
= start_point_ranges
[r
->start
];
271 start_point_ranges
[r
->start
] = r
;
276 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
277 r
->start_next
= ¬_in_chain_mark
;
281 /* Insert live ranges of pseudo REGNO into start chains if they are
284 insert_in_live_range_start_chain (int regno
)
286 lra_live_range_t r
= lra_reg_info
[regno
].live_ranges
;
288 if (r
->start_next
!= ¬_in_chain_mark
)
290 for (; r
!= NULL
; r
= r
->next
)
292 r
->start_next
= start_point_ranges
[r
->start
];
293 start_point_ranges
[r
->start
] = r
;
297 /* Free START_POINT_RANGES. */
299 finish_live_range_start_chains (void)
301 gcc_assert (start_point_ranges
!= NULL
);
302 free (start_point_ranges
);
303 start_point_ranges
= NULL
;
306 /* Map: program point -> bitmap of all pseudos living at the point and
307 assigned to hard registers. */
308 static bitmap_head
*live_hard_reg_pseudos
;
309 static bitmap_obstack live_hard_reg_pseudos_bitmap_obstack
;
311 /* reg_renumber corresponding to pseudos marked in
312 live_hard_reg_pseudos. reg_renumber might be not matched to
313 live_hard_reg_pseudos but live_pseudos_reg_renumber always reflects
314 live_hard_reg_pseudos. */
315 static int *live_pseudos_reg_renumber
;
317 /* Sparseset used to calculate living hard reg pseudos for some program
319 static sparseset live_range_hard_reg_pseudos
;
321 /* Sparseset used to calculate living reload/inheritance pseudos for
322 some program point range. */
323 static sparseset live_range_reload_inheritance_pseudos
;
325 /* Allocate and initialize the data about living pseudos at program
330 int i
, max_regno
= max_reg_num ();
332 live_range_hard_reg_pseudos
= sparseset_alloc (max_regno
);
333 live_range_reload_inheritance_pseudos
= sparseset_alloc (max_regno
);
334 live_hard_reg_pseudos
= XNEWVEC (bitmap_head
, lra_live_max_point
);
335 bitmap_obstack_initialize (&live_hard_reg_pseudos_bitmap_obstack
);
336 for (i
= 0; i
< lra_live_max_point
; i
++)
337 bitmap_initialize (&live_hard_reg_pseudos
[i
],
338 &live_hard_reg_pseudos_bitmap_obstack
);
339 live_pseudos_reg_renumber
= XNEWVEC (int, max_regno
);
340 for (i
= 0; i
< max_regno
; i
++)
341 live_pseudos_reg_renumber
[i
] = -1;
344 /* Free the data about living pseudos at program points. */
348 sparseset_free (live_range_hard_reg_pseudos
);
349 sparseset_free (live_range_reload_inheritance_pseudos
);
350 free (live_hard_reg_pseudos
);
351 bitmap_obstack_release (&live_hard_reg_pseudos_bitmap_obstack
);
352 free (live_pseudos_reg_renumber
);
355 /* Update the LIVE_HARD_REG_PSEUDOS and LIVE_PSEUDOS_REG_RENUMBER
356 entries for pseudo REGNO. Assume that the register has been
357 spilled if FREE_P, otherwise assume that it has been assigned
358 reg_renumber[REGNO] (if >= 0). We also insert the pseudo live
359 ranges in the start chains when it is assumed to be assigned to a
360 hard register because we use the chains of pseudos assigned to hard
361 registers during allocation. */
363 update_lives (int regno
, bool free_p
)
368 if (reg_renumber
[regno
] < 0)
370 live_pseudos_reg_renumber
[regno
] = free_p
? -1 : reg_renumber
[regno
];
371 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
373 for (p
= r
->start
; p
<= r
->finish
; p
++)
375 bitmap_clear_bit (&live_hard_reg_pseudos
[p
], regno
);
378 bitmap_set_bit (&live_hard_reg_pseudos
[p
], regno
);
379 insert_in_live_range_start_chain (regno
);
384 /* Sparseset used to calculate reload pseudos conflicting with a given
385 pseudo when we are trying to find a hard register for the given
387 static sparseset conflict_reload_and_inheritance_pseudos
;
389 /* Map: program point -> bitmap of all reload and inheritance pseudos
390 living at the point. */
391 static bitmap_head
*live_reload_and_inheritance_pseudos
;
392 static bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack
;
394 /* Allocate and initialize data about living reload pseudos at any
395 given program point. */
397 init_live_reload_and_inheritance_pseudos (void)
399 int i
, p
, max_regno
= max_reg_num ();
402 conflict_reload_and_inheritance_pseudos
= sparseset_alloc (max_regno
);
403 live_reload_and_inheritance_pseudos
= XNEWVEC (bitmap_head
, lra_live_max_point
);
404 bitmap_obstack_initialize (&live_reload_and_inheritance_pseudos_bitmap_obstack
);
405 for (p
= 0; p
< lra_live_max_point
; p
++)
406 bitmap_initialize (&live_reload_and_inheritance_pseudos
[p
],
407 &live_reload_and_inheritance_pseudos_bitmap_obstack
);
408 for (i
= lra_constraint_new_regno_start
; i
< max_regno
; i
++)
410 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
411 for (p
= r
->start
; p
<= r
->finish
; p
++)
412 bitmap_set_bit (&live_reload_and_inheritance_pseudos
[p
], i
);
416 /* Finalize data about living reload pseudos at any given program
419 finish_live_reload_and_inheritance_pseudos (void)
421 sparseset_free (conflict_reload_and_inheritance_pseudos
);
422 free (live_reload_and_inheritance_pseudos
);
423 bitmap_obstack_release (&live_reload_and_inheritance_pseudos_bitmap_obstack
);
426 /* The value used to check that cost of given hard reg is really
427 defined currently. */
428 static int curr_hard_regno_costs_check
= 0;
429 /* Array used to check that cost of the corresponding hard reg (the
430 array element index) is really defined currently. */
431 static int hard_regno_costs_check
[FIRST_PSEUDO_REGISTER
];
432 /* The current costs of allocation of hard regs. Defined only if the
433 value of the corresponding element of the previous array is equal to
434 CURR_HARD_REGNO_COSTS_CHECK. */
435 static int hard_regno_costs
[FIRST_PSEUDO_REGISTER
];
437 /* Adjust cost of HARD_REGNO by INCR. Reset the cost first if it is
440 adjust_hard_regno_cost (int hard_regno
, int incr
)
442 if (hard_regno_costs_check
[hard_regno
] != curr_hard_regno_costs_check
)
443 hard_regno_costs
[hard_regno
] = 0;
444 hard_regno_costs_check
[hard_regno
] = curr_hard_regno_costs_check
;
445 hard_regno_costs
[hard_regno
] += incr
;
448 /* Try to find a free hard register for pseudo REGNO. Return the
449 hard register on success and set *COST to the cost of using
450 that register. (If several registers have equal cost, the one with
451 the highest priority wins.) Return -1 on failure.
453 If TRY_ONLY_HARD_REGNO >= 0, consider only that hard register,
454 otherwise consider all hard registers in REGNO's class. */
456 find_hard_regno_for (int regno
, int *cost
, int try_only_hard_regno
)
458 HARD_REG_SET conflict_set
;
459 int best_cost
= INT_MAX
, best_priority
= INT_MIN
, best_usage
= INT_MAX
;
461 int p
, i
, j
, rclass_size
, best_hard_regno
, priority
, hard_regno
;
462 int hr
, conflict_hr
, nregs
;
463 enum machine_mode biggest_mode
;
464 unsigned int k
, conflict_regno
;
465 int offset
, val
, biggest_nregs
, nregs_diff
;
466 enum reg_class rclass
;
468 bool *rclass_intersect_p
;
469 HARD_REG_SET impossible_start_hard_regs
;
471 COPY_HARD_REG_SET (conflict_set
, lra_no_alloc_regs
);
472 rclass
= regno_allocno_class_array
[regno
];
473 rclass_intersect_p
= ira_reg_classes_intersect_p
[rclass
];
474 curr_hard_regno_costs_check
++;
475 sparseset_clear (conflict_reload_and_inheritance_pseudos
);
476 sparseset_clear (live_range_hard_reg_pseudos
);
477 IOR_HARD_REG_SET (conflict_set
, lra_reg_info
[regno
].conflict_hard_regs
);
478 biggest_mode
= lra_reg_info
[regno
].biggest_mode
;
479 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
481 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos
[r
->start
], 0, k
, bi
)
482 if (rclass_intersect_p
[regno_allocno_class_array
[k
]])
483 sparseset_set_bit (live_range_hard_reg_pseudos
, k
);
484 EXECUTE_IF_SET_IN_BITMAP (&live_reload_and_inheritance_pseudos
[r
->start
],
486 if (lra_reg_info
[k
].preferred_hard_regno1
>= 0
487 && live_pseudos_reg_renumber
[k
] < 0
488 && rclass_intersect_p
[regno_allocno_class_array
[k
]])
489 sparseset_set_bit (conflict_reload_and_inheritance_pseudos
, k
);
490 for (p
= r
->start
+ 1; p
<= r
->finish
; p
++)
494 for (r2
= start_point_ranges
[p
];
498 if (r2
->regno
>= lra_constraint_new_regno_start
499 && lra_reg_info
[r2
->regno
].preferred_hard_regno1
>= 0
500 && live_pseudos_reg_renumber
[r2
->regno
] < 0
501 && rclass_intersect_p
[regno_allocno_class_array
[r2
->regno
]])
502 sparseset_set_bit (conflict_reload_and_inheritance_pseudos
,
504 if (live_pseudos_reg_renumber
[r2
->regno
] >= 0
505 && rclass_intersect_p
[regno_allocno_class_array
[r2
->regno
]])
506 sparseset_set_bit (live_range_hard_reg_pseudos
, r2
->regno
);
510 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno1
) >= 0)
512 adjust_hard_regno_cost
513 (hard_regno
, -lra_reg_info
[regno
].preferred_hard_regno_profit1
);
514 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno2
) >= 0)
515 adjust_hard_regno_cost
516 (hard_regno
, -lra_reg_info
[regno
].preferred_hard_regno_profit2
);
519 if (lra_reg_info
[regno
].no_stack_p
)
520 for (i
= FIRST_STACK_REG
; i
<= LAST_STACK_REG
; i
++)
521 SET_HARD_REG_BIT (conflict_set
, i
);
523 sparseset_clear_bit (conflict_reload_and_inheritance_pseudos
, regno
);
524 val
= lra_reg_info
[regno
].val
;
525 offset
= lra_reg_info
[regno
].offset
;
526 CLEAR_HARD_REG_SET (impossible_start_hard_regs
);
527 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos
, conflict_regno
)
528 if (lra_reg_val_equal_p (conflict_regno
, val
, offset
))
530 conflict_hr
= live_pseudos_reg_renumber
[conflict_regno
];
531 nregs
= (hard_regno_nregs
[conflict_hr
]
532 [lra_reg_info
[conflict_regno
].biggest_mode
]);
533 /* Remember about multi-register pseudos. For example, 2 hard
534 register pseudos can start on the same hard register but can
535 not start on HR and HR+1/HR-1. */
536 for (hr
= conflict_hr
+ 1;
537 hr
< FIRST_PSEUDO_REGISTER
&& hr
< conflict_hr
+ nregs
;
539 SET_HARD_REG_BIT (impossible_start_hard_regs
, hr
);
540 for (hr
= conflict_hr
- 1;
541 hr
>= 0 && hr
+ hard_regno_nregs
[hr
][biggest_mode
] > conflict_hr
;
543 SET_HARD_REG_BIT (impossible_start_hard_regs
, hr
);
547 add_to_hard_reg_set (&conflict_set
,
548 lra_reg_info
[conflict_regno
].biggest_mode
,
549 live_pseudos_reg_renumber
[conflict_regno
]);
550 if (hard_reg_set_subset_p (reg_class_contents
[rclass
],
554 EXECUTE_IF_SET_IN_SPARSESET (conflict_reload_and_inheritance_pseudos
,
556 if (!lra_reg_val_equal_p (conflict_regno
, val
, offset
))
558 lra_assert (live_pseudos_reg_renumber
[conflict_regno
] < 0);
560 = lra_reg_info
[conflict_regno
].preferred_hard_regno1
) >= 0)
562 adjust_hard_regno_cost
564 lra_reg_info
[conflict_regno
].preferred_hard_regno_profit1
);
566 = lra_reg_info
[conflict_regno
].preferred_hard_regno2
) >= 0)
567 adjust_hard_regno_cost
569 lra_reg_info
[conflict_regno
].preferred_hard_regno_profit2
);
572 /* Make sure that all registers in a multi-word pseudo belong to the
574 IOR_COMPL_HARD_REG_SET (conflict_set
, reg_class_contents
[rclass
]);
575 lra_assert (rclass
!= NO_REGS
);
576 rclass_size
= ira_class_hard_regs_num
[rclass
];
577 best_hard_regno
= -1;
578 hard_regno
= ira_class_hard_regs
[rclass
][0];
579 biggest_nregs
= hard_regno_nregs
[hard_regno
][biggest_mode
];
580 nregs_diff
= (biggest_nregs
581 - hard_regno_nregs
[hard_regno
][PSEUDO_REGNO_MODE (regno
)]);
582 for (i
= 0; i
< rclass_size
; i
++)
584 if (try_only_hard_regno
>= 0)
585 hard_regno
= try_only_hard_regno
;
587 hard_regno
= ira_class_hard_regs
[rclass
][i
];
588 if (! overlaps_hard_reg_set_p (conflict_set
,
589 PSEUDO_REGNO_MODE (regno
), hard_regno
)
590 /* We can not use prohibited_class_mode_regs because it is
591 not defined for all classes. */
592 && HARD_REGNO_MODE_OK (hard_regno
, PSEUDO_REGNO_MODE (regno
))
593 && ! TEST_HARD_REG_BIT (impossible_start_hard_regs
, hard_regno
)
596 ? (hard_regno
- nregs_diff
>= 0
597 && TEST_HARD_REG_BIT (reg_class_contents
[rclass
],
598 hard_regno
- nregs_diff
))
599 : TEST_HARD_REG_BIT (reg_class_contents
[rclass
],
600 hard_regno
+ nregs_diff
))))
602 if (hard_regno_costs_check
[hard_regno
]
603 != curr_hard_regno_costs_check
)
605 hard_regno_costs_check
[hard_regno
] = curr_hard_regno_costs_check
;
606 hard_regno_costs
[hard_regno
] = 0;
609 j
< hard_regno_nregs
[hard_regno
][PSEUDO_REGNO_MODE (regno
)];
611 if (! TEST_HARD_REG_BIT (call_used_reg_set
, hard_regno
+ j
)
612 && ! df_regs_ever_live_p (hard_regno
+ j
))
613 /* It needs save restore. */
614 hard_regno_costs
[hard_regno
]
616 * REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
)
618 priority
= targetm
.register_priority (hard_regno
);
619 if (best_hard_regno
< 0 || hard_regno_costs
[hard_regno
] < best_cost
620 || (hard_regno_costs
[hard_regno
] == best_cost
621 && (priority
> best_priority
622 || (targetm
.register_usage_leveling_p ()
623 && priority
== best_priority
624 && best_usage
> lra_hard_reg_usage
[hard_regno
]))))
626 best_hard_regno
= hard_regno
;
627 best_cost
= hard_regno_costs
[hard_regno
];
628 best_priority
= priority
;
629 best_usage
= lra_hard_reg_usage
[hard_regno
];
632 if (try_only_hard_regno
>= 0)
635 if (best_hard_regno
>= 0)
636 *cost
= best_cost
- lra_reg_info
[regno
].freq
;
637 return best_hard_regno
;
640 /* Current value used for checking elements in
641 update_hard_regno_preference_check. */
642 static int curr_update_hard_regno_preference_check
;
643 /* If an element value is equal to the above variable value, then the
644 corresponding regno has been processed for preference
646 static int *update_hard_regno_preference_check
;
648 /* Update the preference for using HARD_REGNO for pseudos that are
649 connected directly or indirectly with REGNO. Apply divisor DIV
650 to any preference adjustments.
652 The more indirectly a pseudo is connected, the smaller its effect
653 should be. We therefore increase DIV on each "hop". */
655 update_hard_regno_preference (int regno
, int hard_regno
, int div
)
657 int another_regno
, cost
;
658 lra_copy_t cp
, next_cp
;
660 /* Search depth 5 seems to be enough. */
663 for (cp
= lra_reg_info
[regno
].copies
; cp
!= NULL
; cp
= next_cp
)
665 if (cp
->regno1
== regno
)
667 next_cp
= cp
->regno1_next
;
668 another_regno
= cp
->regno2
;
670 else if (cp
->regno2
== regno
)
672 next_cp
= cp
->regno2_next
;
673 another_regno
= cp
->regno1
;
677 if (reg_renumber
[another_regno
] < 0
678 && (update_hard_regno_preference_check
[another_regno
]
679 != curr_update_hard_regno_preference_check
))
681 update_hard_regno_preference_check
[another_regno
]
682 = curr_update_hard_regno_preference_check
;
683 cost
= cp
->freq
< div
? 1 : cp
->freq
/ div
;
684 lra_setup_reload_pseudo_preferenced_hard_reg
685 (another_regno
, hard_regno
, cost
);
686 update_hard_regno_preference (another_regno
, hard_regno
, div
* 2);
691 /* Return prefix title for pseudo REGNO. */
693 pseudo_prefix_title (int regno
)
696 (regno
< lra_constraint_new_regno_start
? ""
697 : bitmap_bit_p (&lra_inheritance_pseudos
, regno
) ? "inheritance "
698 : bitmap_bit_p (&lra_split_regs
, regno
) ? "split "
699 : bitmap_bit_p (&lra_optional_reload_pseudos
, regno
) ? "optional reload "
700 : bitmap_bit_p (&lra_subreg_reload_pseudos
, regno
) ? "subreg reload "
704 /* Update REG_RENUMBER and other pseudo preferences by assignment of
705 HARD_REGNO to pseudo REGNO and print about it if PRINT_P. */
707 lra_setup_reg_renumber (int regno
, int hard_regno
, bool print_p
)
711 /* We can not just reassign hard register. */
712 lra_assert (hard_regno
< 0 || reg_renumber
[regno
] < 0);
713 if ((hr
= hard_regno
) < 0)
714 hr
= reg_renumber
[regno
];
715 reg_renumber
[regno
] = hard_regno
;
716 lra_assert (hr
>= 0);
717 for (i
= 0; i
< hard_regno_nregs
[hr
][PSEUDO_REGNO_MODE (regno
)]; i
++)
719 lra_hard_reg_usage
[hr
+ i
] -= lra_reg_info
[regno
].freq
;
721 lra_hard_reg_usage
[hr
+ i
] += lra_reg_info
[regno
].freq
;
722 if (print_p
&& lra_dump_file
!= NULL
)
723 fprintf (lra_dump_file
, " Assign %d to %sr%d (freq=%d)\n",
724 reg_renumber
[regno
], pseudo_prefix_title (regno
),
725 regno
, lra_reg_info
[regno
].freq
);
728 curr_update_hard_regno_preference_check
++;
729 update_hard_regno_preference (regno
, hard_regno
, 1);
733 /* Pseudos which occur in insns containing a particular pseudo. */
734 static bitmap_head insn_conflict_pseudos
;
736 /* Bitmaps used to contain spill pseudos for given pseudo hard regno
737 and best spill pseudos for given pseudo (and best hard regno). */
738 static bitmap_head spill_pseudos_bitmap
, best_spill_pseudos_bitmap
;
740 /* Current pseudo check for validity of elements in
741 TRY_HARD_REG_PSEUDOS. */
742 static int curr_pseudo_check
;
743 /* Array used for validity of elements in TRY_HARD_REG_PSEUDOS. */
744 static int try_hard_reg_pseudos_check
[FIRST_PSEUDO_REGISTER
];
745 /* Pseudos who hold given hard register at the considered points. */
746 static bitmap_head try_hard_reg_pseudos
[FIRST_PSEUDO_REGISTER
];
748 /* Set up try_hard_reg_pseudos for given program point P and class
749 RCLASS. Those are pseudos living at P and assigned to a hard
750 register of RCLASS. In other words, those are pseudos which can be
751 spilled to assign a hard register of RCLASS to a pseudo living at
754 setup_try_hard_regno_pseudos (int p
, enum reg_class rclass
)
757 enum machine_mode mode
;
758 unsigned int spill_regno
;
761 /* Find what pseudos could be spilled. */
762 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos
[p
], 0, spill_regno
, bi
)
764 mode
= PSEUDO_REGNO_MODE (spill_regno
);
765 hard_regno
= live_pseudos_reg_renumber
[spill_regno
];
766 if (overlaps_hard_reg_set_p (reg_class_contents
[rclass
],
769 for (i
= hard_regno_nregs
[hard_regno
][mode
] - 1; i
>= 0; i
--)
771 if (try_hard_reg_pseudos_check
[hard_regno
+ i
]
772 != curr_pseudo_check
)
774 try_hard_reg_pseudos_check
[hard_regno
+ i
]
776 bitmap_clear (&try_hard_reg_pseudos
[hard_regno
+ i
]);
778 bitmap_set_bit (&try_hard_reg_pseudos
[hard_regno
+ i
],
785 /* Assign temporarily HARD_REGNO to pseudo REGNO. Temporary
786 assignment means that we might undo the data change. */
788 assign_temporarily (int regno
, int hard_regno
)
793 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
795 for (p
= r
->start
; p
<= r
->finish
; p
++)
797 bitmap_clear_bit (&live_hard_reg_pseudos
[p
], regno
);
800 bitmap_set_bit (&live_hard_reg_pseudos
[p
], regno
);
801 insert_in_live_range_start_chain (regno
);
804 live_pseudos_reg_renumber
[regno
] = hard_regno
;
807 /* Array used for sorting reload pseudos for subsequent allocation
808 after spilling some pseudo. */
809 static int *sorted_reload_pseudos
;
811 /* Spill some pseudos for a reload pseudo REGNO and return hard
812 register which should be used for pseudo after spilling. The
813 function adds spilled pseudos to SPILLED_PSEUDO_BITMAP. When we
814 choose hard register (and pseudos occupying the hard registers and
815 to be spilled), we take into account not only how REGNO will
816 benefit from the spills but also how other reload pseudos not yet
817 assigned to hard registers benefit from the spills too. In very
818 rare cases, the function can fail and return -1. */
820 spill_for (int regno
, bitmap spilled_pseudo_bitmap
)
822 int i
, j
, n
, p
, hard_regno
, best_hard_regno
, cost
, best_cost
, rclass_size
;
823 int reload_hard_regno
, reload_cost
;
824 enum machine_mode mode
;
825 enum reg_class rclass
;
826 unsigned int spill_regno
, reload_regno
, uid
;
827 int insn_pseudos_num
, best_insn_pseudos_num
;
831 rclass
= regno_allocno_class_array
[regno
];
832 lra_assert (reg_renumber
[regno
] < 0 && rclass
!= NO_REGS
);
833 bitmap_clear (&insn_conflict_pseudos
);
834 bitmap_clear (&best_spill_pseudos_bitmap
);
835 EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info
[regno
].insn_bitmap
, 0, uid
, bi
)
837 struct lra_insn_reg
*ir
;
839 for (ir
= lra_get_insn_regs (uid
); ir
!= NULL
; ir
= ir
->next
)
840 if (ir
->regno
>= FIRST_PSEUDO_REGISTER
)
841 bitmap_set_bit (&insn_conflict_pseudos
, ir
->regno
);
843 best_hard_regno
= -1;
845 best_insn_pseudos_num
= INT_MAX
;
846 rclass_size
= ira_class_hard_regs_num
[rclass
];
847 mode
= PSEUDO_REGNO_MODE (regno
);
848 /* Invalidate try_hard_reg_pseudos elements. */
850 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
851 for (p
= r
->start
; p
<= r
->finish
; p
++)
852 setup_try_hard_regno_pseudos (p
, rclass
);
853 for (i
= 0; i
< rclass_size
; i
++)
855 hard_regno
= ira_class_hard_regs
[rclass
][i
];
856 bitmap_clear (&spill_pseudos_bitmap
);
857 for (j
= hard_regno_nregs
[hard_regno
][mode
] - 1; j
>= 0; j
--)
859 if (try_hard_reg_pseudos_check
[hard_regno
+ j
] != curr_pseudo_check
)
861 lra_assert (!bitmap_empty_p (&try_hard_reg_pseudos
[hard_regno
+ j
]));
862 bitmap_ior_into (&spill_pseudos_bitmap
,
863 &try_hard_reg_pseudos
[hard_regno
+ j
]);
866 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
867 if ((int) spill_regno
>= lra_constraint_new_regno_start
868 && ! bitmap_bit_p (&lra_inheritance_pseudos
, spill_regno
)
869 && ! bitmap_bit_p (&lra_split_regs
, spill_regno
)
870 && ! bitmap_bit_p (&lra_subreg_reload_pseudos
, spill_regno
)
871 && ! bitmap_bit_p (&lra_optional_reload_pseudos
, spill_regno
))
873 insn_pseudos_num
= 0;
874 if (lra_dump_file
!= NULL
)
875 fprintf (lra_dump_file
, " Trying %d:", hard_regno
);
876 sparseset_clear (live_range_reload_inheritance_pseudos
);
877 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
879 if (bitmap_bit_p (&insn_conflict_pseudos
, spill_regno
))
881 for (r
= lra_reg_info
[spill_regno
].live_ranges
;
885 for (p
= r
->start
; p
<= r
->finish
; p
++)
889 for (r2
= start_point_ranges
[p
];
892 if (r2
->regno
>= lra_constraint_new_regno_start
)
893 sparseset_set_bit (live_range_reload_inheritance_pseudos
,
899 EXECUTE_IF_SET_IN_SPARSESET (live_range_reload_inheritance_pseudos
,
901 if ((int) reload_regno
!= regno
902 && (ira_reg_classes_intersect_p
903 [rclass
][regno_allocno_class_array
[reload_regno
]])
904 && live_pseudos_reg_renumber
[reload_regno
] < 0
905 && find_hard_regno_for (reload_regno
, &cost
, -1) < 0)
906 sorted_reload_pseudos
[n
++] = reload_regno
;
907 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
909 update_lives (spill_regno
, true);
910 if (lra_dump_file
!= NULL
)
911 fprintf (lra_dump_file
, " spill %d(freq=%d)",
912 spill_regno
, lra_reg_info
[spill_regno
].freq
);
914 hard_regno
= find_hard_regno_for (regno
, &cost
, -1);
917 assign_temporarily (regno
, hard_regno
);
918 qsort (sorted_reload_pseudos
, n
, sizeof (int),
919 reload_pseudo_compare_func
);
920 for (j
= 0; j
< n
; j
++)
922 reload_regno
= sorted_reload_pseudos
[j
];
923 lra_assert (live_pseudos_reg_renumber
[reload_regno
] < 0);
924 if ((reload_hard_regno
925 = find_hard_regno_for (reload_regno
,
926 &reload_cost
, -1)) >= 0)
928 if (lra_dump_file
!= NULL
)
929 fprintf (lra_dump_file
, " assign %d(cost=%d)",
930 reload_regno
, reload_cost
);
931 assign_temporarily (reload_regno
, reload_hard_regno
);
935 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
939 cost
+= lra_reg_info
[spill_regno
].freq
;
940 if (ira_reg_equiv
[spill_regno
].memory
!= NULL
941 || ira_reg_equiv
[spill_regno
].constant
!= NULL
)
942 for (x
= ira_reg_equiv
[spill_regno
].init_insns
;
945 cost
-= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (XEXP (x
, 0)));
947 if (best_insn_pseudos_num
> insn_pseudos_num
948 || (best_insn_pseudos_num
== insn_pseudos_num
949 && best_cost
> cost
))
951 best_insn_pseudos_num
= insn_pseudos_num
;
953 best_hard_regno
= hard_regno
;
954 bitmap_copy (&best_spill_pseudos_bitmap
, &spill_pseudos_bitmap
);
955 if (lra_dump_file
!= NULL
)
956 fprintf (lra_dump_file
, " Now best %d(cost=%d)\n",
959 assign_temporarily (regno
, -1);
960 for (j
= 0; j
< n
; j
++)
962 reload_regno
= sorted_reload_pseudos
[j
];
963 if (live_pseudos_reg_renumber
[reload_regno
] >= 0)
964 assign_temporarily (reload_regno
, -1);
967 if (lra_dump_file
!= NULL
)
968 fprintf (lra_dump_file
, "\n");
969 /* Restore the live hard reg pseudo info for spilled pseudos. */
970 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
971 update_lives (spill_regno
, false);
976 EXECUTE_IF_SET_IN_BITMAP (&best_spill_pseudos_bitmap
, 0, spill_regno
, bi
)
978 if (lra_dump_file
!= NULL
)
979 fprintf (lra_dump_file
, " Spill %sr%d(hr=%d, freq=%d) for r%d\n",
980 pseudo_prefix_title (spill_regno
),
981 spill_regno
, reg_renumber
[spill_regno
],
982 lra_reg_info
[spill_regno
].freq
, regno
);
983 update_lives (spill_regno
, true);
984 lra_setup_reg_renumber (spill_regno
, -1, false);
986 bitmap_ior_into (spilled_pseudo_bitmap
, &best_spill_pseudos_bitmap
);
987 return best_hard_regno
;
990 /* Assign HARD_REGNO to REGNO. */
992 assign_hard_regno (int hard_regno
, int regno
)
996 lra_assert (hard_regno
>= 0);
997 lra_setup_reg_renumber (regno
, hard_regno
, true);
998 update_lives (regno
, false);
1000 i
< hard_regno_nregs
[hard_regno
][lra_reg_info
[regno
].biggest_mode
];
1002 df_set_regs_ever_live (hard_regno
+ i
, true);
1005 /* Array used for sorting different pseudos. */
1006 static int *sorted_pseudos
;
1008 /* The constraints pass is allowed to create equivalences between
1009 pseudos that make the current allocation "incorrect" (in the sense
1010 that pseudos are assigned to hard registers from their own conflict
1011 sets). The global variable lra_risky_transformations_p says
1012 whether this might have happened.
1014 Process pseudos assigned to hard registers (less frequently used
1015 first), spill if a conflict is found, and mark the spilled pseudos
1016 in SPILLED_PSEUDO_BITMAP. Set up LIVE_HARD_REG_PSEUDOS from
1017 pseudos, assigned to hard registers. */
1019 setup_live_pseudos_and_spill_after_risky_transforms (bitmap
1020 spilled_pseudo_bitmap
)
1022 int p
, i
, j
, n
, regno
, hard_regno
;
1023 unsigned int k
, conflict_regno
;
1025 HARD_REG_SET conflict_set
;
1026 enum machine_mode mode
;
1029 int max_regno
= max_reg_num ();
1031 if (! lra_risky_transformations_p
)
1033 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1034 if (reg_renumber
[i
] >= 0 && lra_reg_info
[i
].nrefs
> 0)
1035 update_lives (i
, false);
1038 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1039 if (reg_renumber
[i
] >= 0 && lra_reg_info
[i
].nrefs
> 0)
1040 sorted_pseudos
[n
++] = i
;
1041 qsort (sorted_pseudos
, n
, sizeof (int), pseudo_compare_func
);
1042 for (i
= n
- 1; i
>= 0; i
--)
1044 regno
= sorted_pseudos
[i
];
1045 hard_regno
= reg_renumber
[regno
];
1046 lra_assert (hard_regno
>= 0);
1047 mode
= lra_reg_info
[regno
].biggest_mode
;
1048 sparseset_clear (live_range_hard_reg_pseudos
);
1049 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
1051 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos
[r
->start
], 0, k
, bi
)
1052 sparseset_set_bit (live_range_hard_reg_pseudos
, k
);
1053 for (p
= r
->start
+ 1; p
<= r
->finish
; p
++)
1055 lra_live_range_t r2
;
1057 for (r2
= start_point_ranges
[p
];
1059 r2
= r2
->start_next
)
1060 if (live_pseudos_reg_renumber
[r2
->regno
] >= 0)
1061 sparseset_set_bit (live_range_hard_reg_pseudos
, r2
->regno
);
1064 COPY_HARD_REG_SET (conflict_set
, lra_no_alloc_regs
);
1065 IOR_HARD_REG_SET (conflict_set
, lra_reg_info
[regno
].conflict_hard_regs
);
1066 val
= lra_reg_info
[regno
].val
;
1067 offset
= lra_reg_info
[regno
].offset
;
1068 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos
, conflict_regno
)
1069 if (!lra_reg_val_equal_p (conflict_regno
, val
, offset
)
1070 /* If it is multi-register pseudos they should start on
1071 the same hard register. */
1072 || hard_regno
!= reg_renumber
[conflict_regno
])
1073 add_to_hard_reg_set (&conflict_set
,
1074 lra_reg_info
[conflict_regno
].biggest_mode
,
1075 reg_renumber
[conflict_regno
]);
1076 if (! overlaps_hard_reg_set_p (conflict_set
, mode
, hard_regno
))
1078 update_lives (regno
, false);
1081 bitmap_set_bit (spilled_pseudo_bitmap
, regno
);
1083 j
< hard_regno_nregs
[hard_regno
][PSEUDO_REGNO_MODE (regno
)];
1085 lra_hard_reg_usage
[hard_regno
+ j
] -= lra_reg_info
[regno
].freq
;
1086 reg_renumber
[regno
] = -1;
1087 if (lra_dump_file
!= NULL
)
1088 fprintf (lra_dump_file
, " Spill r%d after risky transformations\n",
1093 /* Improve allocation by assigning the same hard regno of inheritance
1094 pseudos to the connected pseudos. We need this because inheritance
1095 pseudos are allocated after reload pseudos in the thread and when
1096 we assign a hard register to a reload pseudo we don't know yet that
1097 the connected inheritance pseudos can get the same hard register.
1098 Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS. */
1100 improve_inheritance (bitmap changed_pseudos
)
1103 int regno
, another_regno
, hard_regno
, another_hard_regno
, cost
, i
, n
;
1104 lra_copy_t cp
, next_cp
;
1107 if (lra_inheritance_iter
> LRA_MAX_INHERITANCE_PASSES
)
1110 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos
, 0, k
, bi
)
1111 if (reg_renumber
[k
] >= 0 && lra_reg_info
[k
].nrefs
!= 0)
1112 sorted_pseudos
[n
++] = k
;
1113 qsort (sorted_pseudos
, n
, sizeof (int), pseudo_compare_func
);
1114 for (i
= 0; i
< n
; i
++)
1116 regno
= sorted_pseudos
[i
];
1117 hard_regno
= reg_renumber
[regno
];
1118 lra_assert (hard_regno
>= 0);
1119 for (cp
= lra_reg_info
[regno
].copies
; cp
!= NULL
; cp
= next_cp
)
1121 if (cp
->regno1
== regno
)
1123 next_cp
= cp
->regno1_next
;
1124 another_regno
= cp
->regno2
;
1126 else if (cp
->regno2
== regno
)
1128 next_cp
= cp
->regno2_next
;
1129 another_regno
= cp
->regno1
;
1133 /* Don't change reload pseudo allocation. It might have
1134 this allocation for a purpose and changing it can result
1136 if ((another_regno
< lra_constraint_new_regno_start
1137 || bitmap_bit_p (&lra_inheritance_pseudos
, another_regno
))
1138 && (another_hard_regno
= reg_renumber
[another_regno
]) >= 0
1139 && another_hard_regno
!= hard_regno
)
1141 if (lra_dump_file
!= NULL
)
1144 " Improving inheritance for %d(%d) and %d(%d)...\n",
1145 regno
, hard_regno
, another_regno
, another_hard_regno
);
1146 update_lives (another_regno
, true);
1147 lra_setup_reg_renumber (another_regno
, -1, false);
1149 == find_hard_regno_for (another_regno
, &cost
, hard_regno
))
1150 assign_hard_regno (hard_regno
, another_regno
);
1152 assign_hard_regno (another_hard_regno
, another_regno
);
1153 bitmap_set_bit (changed_pseudos
, another_regno
);
1160 /* Bitmap finally containing all pseudos spilled on this assignment
1162 static bitmap_head all_spilled_pseudos
;
1163 /* All pseudos whose allocation was changed. */
1164 static bitmap_head changed_pseudo_bitmap
;
1166 /* Assign hard registers to reload pseudos and other pseudos. */
1168 assign_by_spills (void)
1170 int i
, n
, nfails
, iter
, regno
, hard_regno
, cost
, restore_regno
;
1173 bitmap_head changed_insns
, do_not_assign_nonreload_pseudos
;
1177 int max_regno
= max_reg_num ();
1179 for (n
= 0, i
= lra_constraint_new_regno_start
; i
< max_regno
; i
++)
1180 if (reg_renumber
[i
] < 0 && lra_reg_info
[i
].nrefs
!= 0
1181 && regno_allocno_class_array
[i
] != NO_REGS
)
1182 sorted_pseudos
[n
++] = i
;
1183 bitmap_initialize (&insn_conflict_pseudos
, ®_obstack
);
1184 bitmap_initialize (&spill_pseudos_bitmap
, ®_obstack
);
1185 bitmap_initialize (&best_spill_pseudos_bitmap
, ®_obstack
);
1186 update_hard_regno_preference_check
= XCNEWVEC (int, max_regno
);
1187 curr_update_hard_regno_preference_check
= 0;
1188 memset (try_hard_reg_pseudos_check
, 0, sizeof (try_hard_reg_pseudos_check
));
1189 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1190 bitmap_initialize (&try_hard_reg_pseudos
[i
], ®_obstack
);
1191 curr_pseudo_check
= 0;
1192 bitmap_initialize (&changed_insns
, ®_obstack
);
1193 bitmap_initialize (&non_reload_pseudos
, ®_obstack
);
1194 bitmap_ior (&non_reload_pseudos
, &lra_inheritance_pseudos
, &lra_split_regs
);
1195 bitmap_ior_into (&non_reload_pseudos
, &lra_subreg_reload_pseudos
);
1196 bitmap_ior_into (&non_reload_pseudos
, &lra_optional_reload_pseudos
);
1197 for (iter
= 0; iter
<= 1; iter
++)
1199 qsort (sorted_pseudos
, n
, sizeof (int), reload_pseudo_compare_func
);
1201 for (i
= 0; i
< n
; i
++)
1203 regno
= sorted_pseudos
[i
];
1204 if (lra_dump_file
!= NULL
)
1205 fprintf (lra_dump_file
, " Assigning to %d "
1206 "(cl=%s, orig=%d, freq=%d, tfirst=%d, tfreq=%d)...\n",
1207 regno
, reg_class_names
[regno_allocno_class_array
[regno
]],
1208 ORIGINAL_REGNO (regno_reg_rtx
[regno
]),
1209 lra_reg_info
[regno
].freq
, regno_assign_info
[regno
].first
,
1210 regno_assign_info
[regno_assign_info
[regno
].first
].freq
);
1211 hard_regno
= find_hard_regno_for (regno
, &cost
, -1);
1212 reload_p
= ! bitmap_bit_p (&non_reload_pseudos
, regno
);
1213 if (hard_regno
< 0 && reload_p
)
1214 hard_regno
= spill_for (regno
, &all_spilled_pseudos
);
1218 sorted_pseudos
[nfails
++] = regno
;
1222 /* This register might have been spilled by the previous
1223 pass. Indicate that it is no longer spilled. */
1224 bitmap_clear_bit (&all_spilled_pseudos
, regno
);
1225 assign_hard_regno (hard_regno
, regno
);
1227 /* As non-reload pseudo assignment is changed we
1228 should reconsider insns referring for the
1230 bitmap_set_bit (&changed_pseudo_bitmap
, regno
);
1237 /* We did not assign hard regs to reload pseudos after two
1238 iteration. It means something is wrong with asm insn
1239 constraints. Report it. */
1241 bitmap_head failed_reload_insns
;
1243 bitmap_initialize (&failed_reload_insns
, ®_obstack
);
1244 for (i
= 0; i
< nfails
; i
++)
1246 regno
= sorted_pseudos
[i
];
1247 bitmap_ior_into (&failed_reload_insns
,
1248 &lra_reg_info
[regno
].insn_bitmap
);
1249 /* Assign an arbitrary hard register of regno class to
1250 avoid further trouble with the asm insns. */
1251 bitmap_clear_bit (&all_spilled_pseudos
, regno
);
1253 (ira_class_hard_regs
[regno_allocno_class_array
[regno
]][0],
1256 EXECUTE_IF_SET_IN_BITMAP (&failed_reload_insns
, 0, u
, bi
)
1258 insn
= lra_insn_recog_data
[u
]->insn
;
1259 if (asm_noperands (PATTERN (insn
)) >= 0)
1262 error_for_asm (insn
,
1263 "%<asm%> operand has impossible constraints");
1264 /* Avoid further trouble with this insn.
1265 For asm goto, instead of fixing up all the edges
1266 just clear the template and clear input operands
1267 (asm goto doesn't have any output operands). */
1270 rtx asm_op
= extract_asm_operands (PATTERN (insn
));
1271 ASM_OPERANDS_TEMPLATE (asm_op
) = ggc_strdup ("");
1272 ASM_OPERANDS_INPUT_VEC (asm_op
) = rtvec_alloc (0);
1273 ASM_OPERANDS_INPUT_CONSTRAINT_VEC (asm_op
) = rtvec_alloc (0);
1274 lra_update_insn_regno_info (insn
);
1278 PATTERN (insn
) = gen_rtx_USE (VOIDmode
, const0_rtx
);
1279 lra_set_insn_deleted (insn
);
1286 /* This is a very rare event. We can not assign a hard
1287 register to reload pseudo because the hard register was
1288 assigned to another reload pseudo on a previous
1289 assignment pass. For x86 example, on the 1st pass we
1290 assigned CX (although another hard register could be used
1291 for this) to reload pseudo in an insn, on the 2nd pass we
1292 need CX (and only this) hard register for a new reload
1293 pseudo in the same insn. */
1294 if (lra_dump_file
!= NULL
)
1295 fprintf (lra_dump_file
, " 2nd iter for reload pseudo assignments:\n");
1296 for (i
= 0; i
< nfails
; i
++)
1298 if (lra_dump_file
!= NULL
)
1299 fprintf (lra_dump_file
, " Reload r%d assignment failure\n",
1301 bitmap_ior_into (&changed_insns
,
1302 &lra_reg_info
[sorted_pseudos
[i
]].insn_bitmap
);
1305 /* FIXME: Look up the changed insns in the cached LRA insn data using
1306 an EXECUTE_IF_SET_IN_BITMAP over changed_insns. */
1307 FOR_EACH_BB_FN (bb
, cfun
)
1308 FOR_BB_INSNS (bb
, insn
)
1309 if (bitmap_bit_p (&changed_insns
, INSN_UID (insn
)))
1311 lra_insn_recog_data_t data
;
1312 struct lra_insn_reg
*r
;
1314 data
= lra_get_insn_recog_data (insn
);
1315 for (r
= data
->regs
; r
!= NULL
; r
= r
->next
)
1318 /* A reload pseudo did not get a hard register on the
1319 first iteration because of the conflict with
1320 another reload pseudos in the same insn. So we
1321 consider only reload pseudos assigned to hard
1322 registers. We shall exclude inheritance pseudos as
1323 they can occur in original insns (not reload ones).
1324 We can omit the check for split pseudos because
1325 they occur only in move insns containing non-reload
1327 if (regno
< lra_constraint_new_regno_start
1328 || bitmap_bit_p (&lra_inheritance_pseudos
, regno
)
1329 || reg_renumber
[regno
] < 0)
1331 sorted_pseudos
[nfails
++] = regno
;
1332 if (lra_dump_file
!= NULL
)
1333 fprintf (lra_dump_file
,
1334 " Spill reload r%d(hr=%d, freq=%d)\n",
1335 regno
, reg_renumber
[regno
],
1336 lra_reg_info
[regno
].freq
);
1337 update_lives (regno
, true);
1338 lra_setup_reg_renumber (regno
, -1, false);
1343 improve_inheritance (&changed_pseudo_bitmap
);
1344 bitmap_clear (&non_reload_pseudos
);
1345 bitmap_clear (&changed_insns
);
1348 /* We should not assign to original pseudos of inheritance
1349 pseudos or split pseudos if any its inheritance pseudo did
1350 not get hard register or any its split pseudo was not split
1351 because undo inheritance/split pass will extend live range of
1352 such inheritance or split pseudos. */
1353 bitmap_initialize (&do_not_assign_nonreload_pseudos
, ®_obstack
);
1354 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos
, 0, u
, bi
)
1355 if ((restore_regno
= lra_reg_info
[u
].restore_regno
) >= 0
1356 && reg_renumber
[u
] < 0
1357 && bitmap_bit_p (&lra_inheritance_pseudos
, u
))
1358 bitmap_set_bit (&do_not_assign_nonreload_pseudos
, restore_regno
);
1359 EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs
, 0, u
, bi
)
1360 if ((restore_regno
= lra_reg_info
[u
].restore_regno
) >= 0
1361 && reg_renumber
[u
] >= 0)
1362 bitmap_set_bit (&do_not_assign_nonreload_pseudos
, restore_regno
);
1363 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1364 if (((i
< lra_constraint_new_regno_start
1365 && ! bitmap_bit_p (&do_not_assign_nonreload_pseudos
, i
))
1366 || (bitmap_bit_p (&lra_inheritance_pseudos
, i
)
1367 && lra_reg_info
[i
].restore_regno
>= 0)
1368 || (bitmap_bit_p (&lra_split_regs
, i
)
1369 && lra_reg_info
[i
].restore_regno
>= 0)
1370 || bitmap_bit_p (&lra_subreg_reload_pseudos
, i
)
1371 || bitmap_bit_p (&lra_optional_reload_pseudos
, i
))
1372 && reg_renumber
[i
] < 0 && lra_reg_info
[i
].nrefs
!= 0
1373 && regno_allocno_class_array
[i
] != NO_REGS
)
1374 sorted_pseudos
[n
++] = i
;
1375 bitmap_clear (&do_not_assign_nonreload_pseudos
);
1376 if (n
!= 0 && lra_dump_file
!= NULL
)
1377 fprintf (lra_dump_file
, " Reassigning non-reload pseudos\n");
1378 qsort (sorted_pseudos
, n
, sizeof (int), pseudo_compare_func
);
1379 for (i
= 0; i
< n
; i
++)
1381 regno
= sorted_pseudos
[i
];
1382 hard_regno
= find_hard_regno_for (regno
, &cost
, -1);
1383 if (hard_regno
>= 0)
1385 assign_hard_regno (hard_regno
, regno
);
1386 /* We change allocation for non-reload pseudo on this
1387 iteration -- mark the pseudo for invalidation of used
1388 alternatives of insns containing the pseudo. */
1389 bitmap_set_bit (&changed_pseudo_bitmap
, regno
);
1393 free (update_hard_regno_preference_check
);
1394 bitmap_clear (&best_spill_pseudos_bitmap
);
1395 bitmap_clear (&spill_pseudos_bitmap
);
1396 bitmap_clear (&insn_conflict_pseudos
);
1400 /* Entry function to assign hard registers to new reload pseudos
1401 starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling
1402 of old pseudos) and possibly to the old pseudos. The function adds
1403 what insns to process for the next constraint pass. Those are all
1404 insns who contains non-reload and non-inheritance pseudos with
1407 Return true if we did not spill any non-reload and non-inheritance
1415 bitmap_head insns_to_process
;
1417 int max_regno
= max_reg_num ();
1419 timevar_push (TV_LRA_ASSIGN
);
1421 sorted_pseudos
= XNEWVEC (int, max_regno
);
1422 sorted_reload_pseudos
= XNEWVEC (int, max_regno
);
1423 regno_allocno_class_array
= XNEWVEC (enum reg_class
, max_regno
);
1424 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1425 regno_allocno_class_array
[i
] = lra_get_allocno_class (i
);
1426 init_regno_assign_info ();
1427 bitmap_initialize (&all_spilled_pseudos
, ®_obstack
);
1428 create_live_range_start_chains ();
1429 setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos
);
1430 #ifdef ENABLE_CHECKING
1431 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1432 if (lra_reg_info
[i
].nrefs
!= 0 && reg_renumber
[i
] >= 0
1433 && lra_reg_info
[i
].call_p
1434 && overlaps_hard_reg_set_p (call_used_reg_set
,
1435 PSEUDO_REGNO_MODE (i
), reg_renumber
[i
]))
1438 /* Setup insns to process on the next constraint pass. */
1439 bitmap_initialize (&changed_pseudo_bitmap
, ®_obstack
);
1440 init_live_reload_and_inheritance_pseudos ();
1441 assign_by_spills ();
1442 finish_live_reload_and_inheritance_pseudos ();
1443 bitmap_ior_into (&changed_pseudo_bitmap
, &all_spilled_pseudos
);
1445 EXECUTE_IF_SET_IN_BITMAP (&all_spilled_pseudos
, 0, u
, bi
)
1446 /* We ignore spilled pseudos created on last inheritance pass
1447 because they will be removed. */
1448 if (lra_reg_info
[u
].restore_regno
< 0)
1450 no_spills_p
= false;
1453 finish_live_range_start_chains ();
1454 bitmap_clear (&all_spilled_pseudos
);
1455 bitmap_initialize (&insns_to_process
, ®_obstack
);
1456 EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap
, 0, u
, bi
)
1457 bitmap_ior_into (&insns_to_process
, &lra_reg_info
[u
].insn_bitmap
);
1458 bitmap_clear (&changed_pseudo_bitmap
);
1459 EXECUTE_IF_SET_IN_BITMAP (&insns_to_process
, 0, u
, bi
)
1461 lra_push_insn_by_uid (u
);
1462 /* Invalidate alternatives for insn should be processed. */
1463 lra_set_used_insn_alternative_by_uid (u
, -1);
1465 bitmap_clear (&insns_to_process
);
1466 finish_regno_assign_info ();
1467 free (regno_allocno_class_array
);
1468 free (sorted_pseudos
);
1469 free (sorted_reload_pseudos
);
1471 timevar_pop (TV_LRA_ASSIGN
);