1 /* Assign reload pseudos.
2 Copyright (C) 2010-2013 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 /* Process a pseudo copy with execution frequency COPY_FREQ connecting
120 REGNO1 and REGNO2 to form threads. */
122 process_copy_to_form_thread (int regno1
, int regno2
, int copy_freq
)
124 int last
, regno1_first
, regno2_first
;
126 lra_assert (regno1
>= lra_constraint_new_regno_start
127 && regno2
>= lra_constraint_new_regno_start
);
128 regno1_first
= regno_assign_info
[regno1
].first
;
129 regno2_first
= regno_assign_info
[regno2
].first
;
130 if (regno1_first
!= regno2_first
)
132 for (last
= regno2_first
;
133 regno_assign_info
[last
].next
>= 0;
134 last
= regno_assign_info
[last
].next
)
135 regno_assign_info
[last
].first
= regno1_first
;
136 regno_assign_info
[last
].first
= regno1_first
;
137 regno_assign_info
[last
].next
= regno_assign_info
[regno1_first
].next
;
138 regno_assign_info
[regno1_first
].next
= regno2_first
;
139 regno_assign_info
[regno1_first
].freq
140 += regno_assign_info
[regno2_first
].freq
;
142 regno_assign_info
[regno1_first
].freq
-= 2 * copy_freq
;
143 lra_assert (regno_assign_info
[regno1_first
].freq
>= 0);
146 /* Initialize REGNO_ASSIGN_INFO and form threads. */
148 init_regno_assign_info (void)
150 int i
, regno1
, regno2
, max_regno
= max_reg_num ();
153 regno_assign_info
= XNEWVEC (struct regno_assign_info
, max_regno
);
154 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
156 regno_assign_info
[i
].first
= i
;
157 regno_assign_info
[i
].next
= -1;
158 regno_assign_info
[i
].freq
= lra_reg_info
[i
].freq
;
160 /* Form the threads. */
161 for (i
= 0; (cp
= lra_get_copy (i
)) != NULL
; i
++)
162 if ((regno1
= cp
->regno1
) >= lra_constraint_new_regno_start
163 && (regno2
= cp
->regno2
) >= lra_constraint_new_regno_start
164 && reg_renumber
[regno1
] < 0 && lra_reg_info
[regno1
].nrefs
!= 0
165 && reg_renumber
[regno2
] < 0 && lra_reg_info
[regno2
].nrefs
!= 0
166 && (ira_class_hard_regs_num
[regno_allocno_class_array
[regno1
]]
167 == ira_class_hard_regs_num
[regno_allocno_class_array
[regno2
]]))
168 process_copy_to_form_thread (regno1
, regno2
, cp
->freq
);
171 /* Free REGNO_ASSIGN_INFO. */
173 finish_regno_assign_info (void)
175 free (regno_assign_info
);
178 /* The function is used to sort *reload* and *inheritance* pseudos to
179 try to assign them hard registers. We put pseudos from the same
180 thread always nearby. */
182 reload_pseudo_compare_func (const void *v1p
, const void *v2p
)
184 int r1
= *(const int *) v1p
, r2
= *(const int *) v2p
;
185 enum reg_class cl1
= regno_allocno_class_array
[r1
];
186 enum reg_class cl2
= regno_allocno_class_array
[r2
];
189 lra_assert (r1
>= lra_constraint_new_regno_start
190 && r2
>= lra_constraint_new_regno_start
);
192 /* Prefer to assign reload registers with smaller classes first to
193 guarantee assignment to all reload registers. */
194 if ((diff
= (ira_class_hard_regs_num
[cl1
]
195 - ira_class_hard_regs_num
[cl2
])) != 0)
197 if ((diff
= (regno_assign_info
[regno_assign_info
[r2
].first
].freq
198 - regno_assign_info
[regno_assign_info
[r1
].first
].freq
)) != 0)
200 /* Allocate bigger pseudos first to avoid register file
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)
206 /* Put pseudos from the thread nearby. */
207 if ((diff
= regno_assign_info
[r1
].first
- regno_assign_info
[r2
].first
) != 0)
209 /* If regs are equally good, sort by their numbers, so that the
210 results of qsort leave nothing to chance. */
214 /* The function is used to sort *non-reload* pseudos to try to assign
215 them hard registers. The order calculation is simpler than in the
216 previous function and based on the pseudo frequency usage. */
218 pseudo_compare_func (const void *v1p
, const void *v2p
)
220 int r1
= *(const int *) v1p
, r2
= *(const int *) v2p
;
223 /* Prefer to assign more frequently used registers first. */
224 if ((diff
= lra_reg_info
[r2
].freq
- lra_reg_info
[r1
].freq
) != 0)
227 /* If regs are equally good, sort by their numbers, so that the
228 results of qsort leave nothing to chance. */
232 /* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the
233 pseudo live ranges with given start point. We insert only live
234 ranges of pseudos interesting for assignment purposes. They are
235 reload pseudos and pseudos assigned to hard registers. */
236 static lra_live_range_t
*start_point_ranges
;
238 /* Used as a flag that a live range is not inserted in the start point
240 static struct lra_live_range not_in_chain_mark
;
242 /* Create and set up START_POINT_RANGES. */
244 create_live_range_start_chains (void)
249 start_point_ranges
= XCNEWVEC (lra_live_range_t
, lra_live_max_point
);
250 max_regno
= max_reg_num ();
251 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
252 if (i
>= lra_constraint_new_regno_start
|| reg_renumber
[i
] >= 0)
254 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
256 r
->start_next
= start_point_ranges
[r
->start
];
257 start_point_ranges
[r
->start
] = r
;
262 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
263 r
->start_next
= ¬_in_chain_mark
;
267 /* Insert live ranges of pseudo REGNO into start chains if they are
270 insert_in_live_range_start_chain (int regno
)
272 lra_live_range_t r
= lra_reg_info
[regno
].live_ranges
;
274 if (r
->start_next
!= ¬_in_chain_mark
)
276 for (; r
!= NULL
; r
= r
->next
)
278 r
->start_next
= start_point_ranges
[r
->start
];
279 start_point_ranges
[r
->start
] = r
;
283 /* Free START_POINT_RANGES. */
285 finish_live_range_start_chains (void)
287 gcc_assert (start_point_ranges
!= NULL
);
288 free (start_point_ranges
);
289 start_point_ranges
= NULL
;
292 /* Map: program point -> bitmap of all pseudos living at the point and
293 assigned to hard registers. */
294 static bitmap_head
*live_hard_reg_pseudos
;
295 static bitmap_obstack live_hard_reg_pseudos_bitmap_obstack
;
297 /* reg_renumber corresponding to pseudos marked in
298 live_hard_reg_pseudos. reg_renumber might be not matched to
299 live_hard_reg_pseudos but live_pseudos_reg_renumber always reflects
300 live_hard_reg_pseudos. */
301 static int *live_pseudos_reg_renumber
;
303 /* Sparseset used to calculate living hard reg pseudos for some program
305 static sparseset live_range_hard_reg_pseudos
;
307 /* Sparseset used to calculate living reload/inheritance pseudos for
308 some program point range. */
309 static sparseset live_range_reload_inheritance_pseudos
;
311 /* Allocate and initialize the data about living pseudos at program
316 int i
, max_regno
= max_reg_num ();
318 live_range_hard_reg_pseudos
= sparseset_alloc (max_regno
);
319 live_range_reload_inheritance_pseudos
= sparseset_alloc (max_regno
);
320 live_hard_reg_pseudos
= XNEWVEC (bitmap_head
, lra_live_max_point
);
321 bitmap_obstack_initialize (&live_hard_reg_pseudos_bitmap_obstack
);
322 for (i
= 0; i
< lra_live_max_point
; i
++)
323 bitmap_initialize (&live_hard_reg_pseudos
[i
],
324 &live_hard_reg_pseudos_bitmap_obstack
);
325 live_pseudos_reg_renumber
= XNEWVEC (int, max_regno
);
326 for (i
= 0; i
< max_regno
; i
++)
327 live_pseudos_reg_renumber
[i
] = -1;
330 /* Free the data about living pseudos at program points. */
334 sparseset_free (live_range_hard_reg_pseudos
);
335 sparseset_free (live_range_reload_inheritance_pseudos
);
336 free (live_hard_reg_pseudos
);
337 bitmap_obstack_release (&live_hard_reg_pseudos_bitmap_obstack
);
338 free (live_pseudos_reg_renumber
);
341 /* Update the LIVE_HARD_REG_PSEUDOS and LIVE_PSEUDOS_REG_RENUMBER
342 entries for pseudo REGNO. Assume that the register has been
343 spilled if FREE_P, otherwise assume that it has been assigned
344 reg_renumber[REGNO] (if >= 0). We also insert the pseudo live
345 ranges in the start chains when it is assumed to be assigned to a
346 hard register because we use the chains of pseudos assigned to hard
347 registers during allocation. */
349 update_lives (int regno
, bool free_p
)
354 if (reg_renumber
[regno
] < 0)
356 live_pseudos_reg_renumber
[regno
] = free_p
? -1 : reg_renumber
[regno
];
357 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
359 for (p
= r
->start
; p
<= r
->finish
; p
++)
361 bitmap_clear_bit (&live_hard_reg_pseudos
[p
], regno
);
364 bitmap_set_bit (&live_hard_reg_pseudos
[p
], regno
);
365 insert_in_live_range_start_chain (regno
);
370 /* Sparseset used to calculate reload pseudos conflicting with a given
371 pseudo when we are trying to find a hard register for the given
373 static sparseset conflict_reload_and_inheritance_pseudos
;
375 /* Map: program point -> bitmap of all reload and inheritance pseudos
376 living at the point. */
377 static bitmap_head
*live_reload_and_inheritance_pseudos
;
378 static bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack
;
380 /* Allocate and initialize data about living reload pseudos at any
381 given program point. */
383 init_live_reload_and_inheritance_pseudos (void)
385 int i
, p
, max_regno
= max_reg_num ();
388 conflict_reload_and_inheritance_pseudos
= sparseset_alloc (max_regno
);
389 live_reload_and_inheritance_pseudos
= XNEWVEC (bitmap_head
, lra_live_max_point
);
390 bitmap_obstack_initialize (&live_reload_and_inheritance_pseudos_bitmap_obstack
);
391 for (p
= 0; p
< lra_live_max_point
; p
++)
392 bitmap_initialize (&live_reload_and_inheritance_pseudos
[p
],
393 &live_reload_and_inheritance_pseudos_bitmap_obstack
);
394 for (i
= lra_constraint_new_regno_start
; i
< max_regno
; i
++)
396 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
397 for (p
= r
->start
; p
<= r
->finish
; p
++)
398 bitmap_set_bit (&live_reload_and_inheritance_pseudos
[p
], i
);
402 /* Finalize data about living reload pseudos at any given program
405 finish_live_reload_and_inheritance_pseudos (void)
407 sparseset_free (conflict_reload_and_inheritance_pseudos
);
408 free (live_reload_and_inheritance_pseudos
);
409 bitmap_obstack_release (&live_reload_and_inheritance_pseudos_bitmap_obstack
);
412 /* The value used to check that cost of given hard reg is really
413 defined currently. */
414 static int curr_hard_regno_costs_check
= 0;
415 /* Array used to check that cost of the corresponding hard reg (the
416 array element index) is really defined currently. */
417 static int hard_regno_costs_check
[FIRST_PSEUDO_REGISTER
];
418 /* The current costs of allocation of hard regs. Defined only if the
419 value of the corresponding element of the previous array is equal to
420 CURR_HARD_REGNO_COSTS_CHECK. */
421 static int hard_regno_costs
[FIRST_PSEUDO_REGISTER
];
423 /* Adjust cost of HARD_REGNO by INCR. Reset the cost first if it is
426 adjust_hard_regno_cost (int hard_regno
, int incr
)
428 if (hard_regno_costs_check
[hard_regno
] != curr_hard_regno_costs_check
)
429 hard_regno_costs
[hard_regno
] = 0;
430 hard_regno_costs_check
[hard_regno
] = curr_hard_regno_costs_check
;
431 hard_regno_costs
[hard_regno
] += incr
;
434 /* Try to find a free hard register for pseudo REGNO. Return the
435 hard register on success and set *COST to the cost of using
436 that register. (If several registers have equal cost, the one with
437 the highest priority wins.) Return -1 on failure.
439 If TRY_ONLY_HARD_REGNO >= 0, consider only that hard register,
440 otherwise consider all hard registers in REGNO's class. */
442 find_hard_regno_for (int regno
, int *cost
, int try_only_hard_regno
)
444 HARD_REG_SET conflict_set
;
445 int best_cost
= INT_MAX
, best_priority
= INT_MIN
, best_usage
= INT_MAX
;
447 int p
, i
, j
, rclass_size
, best_hard_regno
, priority
, hard_regno
;
448 int hr
, conflict_hr
, nregs
;
449 enum machine_mode biggest_mode
;
450 unsigned int k
, conflict_regno
;
451 int val
, biggest_nregs
, nregs_diff
;
452 enum reg_class rclass
;
454 bool *rclass_intersect_p
;
455 HARD_REG_SET impossible_start_hard_regs
;
457 COPY_HARD_REG_SET (conflict_set
, lra_no_alloc_regs
);
458 rclass
= regno_allocno_class_array
[regno
];
459 rclass_intersect_p
= ira_reg_classes_intersect_p
[rclass
];
460 curr_hard_regno_costs_check
++;
461 sparseset_clear (conflict_reload_and_inheritance_pseudos
);
462 sparseset_clear (live_range_hard_reg_pseudos
);
463 IOR_HARD_REG_SET (conflict_set
, lra_reg_info
[regno
].conflict_hard_regs
);
464 biggest_mode
= lra_reg_info
[regno
].biggest_mode
;
465 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
467 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos
[r
->start
], 0, k
, bi
)
468 if (rclass_intersect_p
[regno_allocno_class_array
[k
]])
469 sparseset_set_bit (live_range_hard_reg_pseudos
, k
);
470 EXECUTE_IF_SET_IN_BITMAP (&live_reload_and_inheritance_pseudos
[r
->start
],
472 if (lra_reg_info
[k
].preferred_hard_regno1
>= 0
473 && live_pseudos_reg_renumber
[k
] < 0
474 && rclass_intersect_p
[regno_allocno_class_array
[k
]])
475 sparseset_set_bit (conflict_reload_and_inheritance_pseudos
, k
);
476 for (p
= r
->start
+ 1; p
<= r
->finish
; p
++)
480 for (r2
= start_point_ranges
[p
];
484 if (r2
->regno
>= lra_constraint_new_regno_start
485 && lra_reg_info
[r2
->regno
].preferred_hard_regno1
>= 0
486 && live_pseudos_reg_renumber
[r2
->regno
] < 0
487 && rclass_intersect_p
[regno_allocno_class_array
[r2
->regno
]])
488 sparseset_set_bit (conflict_reload_and_inheritance_pseudos
,
490 if (live_pseudos_reg_renumber
[r2
->regno
] >= 0
491 && rclass_intersect_p
[regno_allocno_class_array
[r2
->regno
]])
492 sparseset_set_bit (live_range_hard_reg_pseudos
, r2
->regno
);
496 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno1
) >= 0)
498 adjust_hard_regno_cost
499 (hard_regno
, -lra_reg_info
[regno
].preferred_hard_regno_profit1
);
500 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno2
) >= 0)
501 adjust_hard_regno_cost
502 (hard_regno
, -lra_reg_info
[regno
].preferred_hard_regno_profit2
);
505 if (lra_reg_info
[regno
].no_stack_p
)
506 for (i
= FIRST_STACK_REG
; i
<= LAST_STACK_REG
; i
++)
507 SET_HARD_REG_BIT (conflict_set
, i
);
509 sparseset_clear_bit (conflict_reload_and_inheritance_pseudos
, regno
);
510 val
= lra_reg_info
[regno
].val
;
511 CLEAR_HARD_REG_SET (impossible_start_hard_regs
);
512 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos
, conflict_regno
)
513 if (val
== lra_reg_info
[conflict_regno
].val
)
515 conflict_hr
= live_pseudos_reg_renumber
[conflict_regno
];
516 nregs
= (hard_regno_nregs
[conflict_hr
]
517 [lra_reg_info
[conflict_regno
].biggest_mode
]);
518 /* Remember about multi-register pseudos. For example, 2 hard
519 register pseudos can start on the same hard register but can
520 not start on HR and HR+1/HR-1. */
521 for (hr
= conflict_hr
+ 1;
522 hr
< FIRST_PSEUDO_REGISTER
&& hr
< conflict_hr
+ nregs
;
524 SET_HARD_REG_BIT (impossible_start_hard_regs
, hr
);
525 for (hr
= conflict_hr
- 1;
526 hr
>= 0 && hr
+ hard_regno_nregs
[hr
][biggest_mode
] > conflict_hr
;
528 SET_HARD_REG_BIT (impossible_start_hard_regs
, hr
);
532 add_to_hard_reg_set (&conflict_set
,
533 lra_reg_info
[conflict_regno
].biggest_mode
,
534 live_pseudos_reg_renumber
[conflict_regno
]);
535 if (hard_reg_set_subset_p (reg_class_contents
[rclass
],
539 EXECUTE_IF_SET_IN_SPARSESET (conflict_reload_and_inheritance_pseudos
,
541 if (val
!= lra_reg_info
[conflict_regno
].val
)
543 lra_assert (live_pseudos_reg_renumber
[conflict_regno
] < 0);
545 = lra_reg_info
[conflict_regno
].preferred_hard_regno1
) >= 0)
547 adjust_hard_regno_cost
549 lra_reg_info
[conflict_regno
].preferred_hard_regno_profit1
);
551 = lra_reg_info
[conflict_regno
].preferred_hard_regno2
) >= 0)
552 adjust_hard_regno_cost
554 lra_reg_info
[conflict_regno
].preferred_hard_regno_profit2
);
557 /* Make sure that all registers in a multi-word pseudo belong to the
559 IOR_COMPL_HARD_REG_SET (conflict_set
, reg_class_contents
[rclass
]);
560 lra_assert (rclass
!= NO_REGS
);
561 rclass_size
= ira_class_hard_regs_num
[rclass
];
562 best_hard_regno
= -1;
563 hard_regno
= ira_class_hard_regs
[rclass
][0];
564 biggest_nregs
= hard_regno_nregs
[hard_regno
][biggest_mode
];
565 nregs_diff
= (biggest_nregs
566 - hard_regno_nregs
[hard_regno
][PSEUDO_REGNO_MODE (regno
)]);
567 for (i
= 0; i
< rclass_size
; i
++)
569 if (try_only_hard_regno
>= 0)
570 hard_regno
= try_only_hard_regno
;
572 hard_regno
= ira_class_hard_regs
[rclass
][i
];
573 if (! overlaps_hard_reg_set_p (conflict_set
,
574 PSEUDO_REGNO_MODE (regno
), hard_regno
)
575 /* We can not use prohibited_class_mode_regs because it is
576 not defined for all classes. */
577 && HARD_REGNO_MODE_OK (hard_regno
, PSEUDO_REGNO_MODE (regno
))
578 && ! TEST_HARD_REG_BIT (impossible_start_hard_regs
, hard_regno
)
581 ? (hard_regno
- nregs_diff
>= 0
582 && TEST_HARD_REG_BIT (reg_class_contents
[rclass
],
583 hard_regno
- nregs_diff
))
584 : TEST_HARD_REG_BIT (reg_class_contents
[rclass
],
585 hard_regno
+ nregs_diff
))))
587 if (hard_regno_costs_check
[hard_regno
]
588 != curr_hard_regno_costs_check
)
590 hard_regno_costs_check
[hard_regno
] = curr_hard_regno_costs_check
;
591 hard_regno_costs
[hard_regno
] = 0;
594 j
< hard_regno_nregs
[hard_regno
][PSEUDO_REGNO_MODE (regno
)];
596 if (! TEST_HARD_REG_BIT (call_used_reg_set
, hard_regno
+ j
)
597 && ! df_regs_ever_live_p (hard_regno
+ j
))
598 /* It needs save restore. */
599 hard_regno_costs
[hard_regno
]
600 += 2 * ENTRY_BLOCK_PTR
->next_bb
->frequency
;
601 priority
= targetm
.register_priority (hard_regno
);
602 if (best_hard_regno
< 0 || hard_regno_costs
[hard_regno
] < best_cost
603 || (hard_regno_costs
[hard_regno
] == best_cost
604 && (priority
> best_priority
605 /* Hard register usage leveling actually results
606 in bigger code for targets with conditional
607 execution like ARM because it reduces chance
608 of if-conversion after LRA. */
609 || (! targetm
.have_conditional_execution ()
610 && priority
== best_priority
611 && best_usage
> lra_hard_reg_usage
[hard_regno
]))))
613 best_hard_regno
= hard_regno
;
614 best_cost
= hard_regno_costs
[hard_regno
];
615 best_priority
= priority
;
616 best_usage
= lra_hard_reg_usage
[hard_regno
];
619 if (try_only_hard_regno
>= 0)
622 if (best_hard_regno
>= 0)
623 *cost
= best_cost
- lra_reg_info
[regno
].freq
;
624 return best_hard_regno
;
627 /* Current value used for checking elements in
628 update_hard_regno_preference_check. */
629 static int curr_update_hard_regno_preference_check
;
630 /* If an element value is equal to the above variable value, then the
631 corresponding regno has been processed for preference
633 static int *update_hard_regno_preference_check
;
635 /* Update the preference for using HARD_REGNO for pseudos that are
636 connected directly or indirectly with REGNO. Apply divisor DIV
637 to any preference adjustments.
639 The more indirectly a pseudo is connected, the smaller its effect
640 should be. We therefore increase DIV on each "hop". */
642 update_hard_regno_preference (int regno
, int hard_regno
, int div
)
644 int another_regno
, cost
;
645 lra_copy_t cp
, next_cp
;
647 /* Search depth 5 seems to be enough. */
650 for (cp
= lra_reg_info
[regno
].copies
; cp
!= NULL
; cp
= next_cp
)
652 if (cp
->regno1
== regno
)
654 next_cp
= cp
->regno1_next
;
655 another_regno
= cp
->regno2
;
657 else if (cp
->regno2
== regno
)
659 next_cp
= cp
->regno2_next
;
660 another_regno
= cp
->regno1
;
664 if (reg_renumber
[another_regno
] < 0
665 && (update_hard_regno_preference_check
[another_regno
]
666 != curr_update_hard_regno_preference_check
))
668 update_hard_regno_preference_check
[another_regno
]
669 = curr_update_hard_regno_preference_check
;
670 cost
= cp
->freq
< div
? 1 : cp
->freq
/ div
;
671 lra_setup_reload_pseudo_preferenced_hard_reg
672 (another_regno
, hard_regno
, cost
);
673 update_hard_regno_preference (another_regno
, hard_regno
, div
* 2);
678 /* Update REG_RENUMBER and other pseudo preferences by assignment of
679 HARD_REGNO to pseudo REGNO and print about it if PRINT_P. */
681 lra_setup_reg_renumber (int regno
, int hard_regno
, bool print_p
)
685 /* We can not just reassign hard register. */
686 lra_assert (hard_regno
< 0 || reg_renumber
[regno
] < 0);
687 if ((hr
= hard_regno
) < 0)
688 hr
= reg_renumber
[regno
];
689 reg_renumber
[regno
] = hard_regno
;
690 lra_assert (hr
>= 0);
691 for (i
= 0; i
< hard_regno_nregs
[hr
][PSEUDO_REGNO_MODE (regno
)]; i
++)
693 lra_hard_reg_usage
[hr
+ i
] -= lra_reg_info
[regno
].freq
;
695 lra_hard_reg_usage
[hr
+ i
] += lra_reg_info
[regno
].freq
;
696 if (print_p
&& lra_dump_file
!= NULL
)
697 fprintf (lra_dump_file
, " Assign %d to %sr%d (freq=%d)\n",
699 regno
< lra_constraint_new_regno_start
701 : bitmap_bit_p (&lra_inheritance_pseudos
, regno
) ? "inheritance "
702 : bitmap_bit_p (&lra_split_regs
, regno
) ? "split "
703 : bitmap_bit_p (&lra_optional_reload_pseudos
, regno
)
704 ? "optional reload ": "reload ",
705 regno
, lra_reg_info
[regno
].freq
);
708 curr_update_hard_regno_preference_check
++;
709 update_hard_regno_preference (regno
, hard_regno
, 1);
713 /* Pseudos which occur in insns containing a particular pseudo. */
714 static bitmap_head insn_conflict_pseudos
;
716 /* Bitmaps used to contain spill pseudos for given pseudo hard regno
717 and best spill pseudos for given pseudo (and best hard regno). */
718 static bitmap_head spill_pseudos_bitmap
, best_spill_pseudos_bitmap
;
720 /* Current pseudo check for validity of elements in
721 TRY_HARD_REG_PSEUDOS. */
722 static int curr_pseudo_check
;
723 /* Array used for validity of elements in TRY_HARD_REG_PSEUDOS. */
724 static int try_hard_reg_pseudos_check
[FIRST_PSEUDO_REGISTER
];
725 /* Pseudos who hold given hard register at the considered points. */
726 static bitmap_head try_hard_reg_pseudos
[FIRST_PSEUDO_REGISTER
];
728 /* Set up try_hard_reg_pseudos for given program point P and class
729 RCLASS. Those are pseudos living at P and assigned to a hard
730 register of RCLASS. In other words, those are pseudos which can be
731 spilled to assign a hard register of RCLASS to a pseudo living at
734 setup_try_hard_regno_pseudos (int p
, enum reg_class rclass
)
737 enum machine_mode mode
;
738 unsigned int spill_regno
;
741 /* Find what pseudos could be spilled. */
742 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos
[p
], 0, spill_regno
, bi
)
744 mode
= PSEUDO_REGNO_MODE (spill_regno
);
745 hard_regno
= live_pseudos_reg_renumber
[spill_regno
];
746 if (overlaps_hard_reg_set_p (reg_class_contents
[rclass
],
749 for (i
= hard_regno_nregs
[hard_regno
][mode
] - 1; i
>= 0; i
--)
751 if (try_hard_reg_pseudos_check
[hard_regno
+ i
]
752 != curr_pseudo_check
)
754 try_hard_reg_pseudos_check
[hard_regno
+ i
]
756 bitmap_clear (&try_hard_reg_pseudos
[hard_regno
+ i
]);
758 bitmap_set_bit (&try_hard_reg_pseudos
[hard_regno
+ i
],
765 /* Assign temporarily HARD_REGNO to pseudo REGNO. Temporary
766 assignment means that we might undo the data change. */
768 assign_temporarily (int regno
, int hard_regno
)
773 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
775 for (p
= r
->start
; p
<= r
->finish
; p
++)
777 bitmap_clear_bit (&live_hard_reg_pseudos
[p
], regno
);
780 bitmap_set_bit (&live_hard_reg_pseudos
[p
], regno
);
781 insert_in_live_range_start_chain (regno
);
784 live_pseudos_reg_renumber
[regno
] = hard_regno
;
787 /* Array used for sorting reload pseudos for subsequent allocation
788 after spilling some pseudo. */
789 static int *sorted_reload_pseudos
;
791 /* Spill some pseudos for a reload pseudo REGNO and return hard
792 register which should be used for pseudo after spilling. The
793 function adds spilled pseudos to SPILLED_PSEUDO_BITMAP. When we
794 choose hard register (and pseudos occupying the hard registers and
795 to be spilled), we take into account not only how REGNO will
796 benefit from the spills but also how other reload pseudos not yet
797 assigned to hard registers benefit from the spills too. In very
798 rare cases, the function can fail and return -1. */
800 spill_for (int regno
, bitmap spilled_pseudo_bitmap
)
802 int i
, j
, n
, p
, hard_regno
, best_hard_regno
, cost
, best_cost
, rclass_size
;
803 int reload_hard_regno
, reload_cost
;
804 enum machine_mode mode
;
805 enum reg_class rclass
;
806 unsigned int spill_regno
, reload_regno
, uid
;
807 int insn_pseudos_num
, best_insn_pseudos_num
;
811 rclass
= regno_allocno_class_array
[regno
];
812 lra_assert (reg_renumber
[regno
] < 0 && rclass
!= NO_REGS
);
813 bitmap_clear (&insn_conflict_pseudos
);
814 bitmap_clear (&best_spill_pseudos_bitmap
);
815 EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info
[regno
].insn_bitmap
, 0, uid
, bi
)
817 struct lra_insn_reg
*ir
;
819 for (ir
= lra_get_insn_regs (uid
); ir
!= NULL
; ir
= ir
->next
)
820 if (ir
->regno
>= FIRST_PSEUDO_REGISTER
)
821 bitmap_set_bit (&insn_conflict_pseudos
, ir
->regno
);
823 best_hard_regno
= -1;
825 best_insn_pseudos_num
= INT_MAX
;
826 rclass_size
= ira_class_hard_regs_num
[rclass
];
827 mode
= PSEUDO_REGNO_MODE (regno
);
828 /* Invalidate try_hard_reg_pseudos elements. */
830 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
831 for (p
= r
->start
; p
<= r
->finish
; p
++)
832 setup_try_hard_regno_pseudos (p
, rclass
);
833 for (i
= 0; i
< rclass_size
; i
++)
835 hard_regno
= ira_class_hard_regs
[rclass
][i
];
836 bitmap_clear (&spill_pseudos_bitmap
);
837 for (j
= hard_regno_nregs
[hard_regno
][mode
] - 1; j
>= 0; j
--)
839 if (try_hard_reg_pseudos_check
[hard_regno
+ j
] != curr_pseudo_check
)
841 lra_assert (!bitmap_empty_p (&try_hard_reg_pseudos
[hard_regno
+ j
]));
842 bitmap_ior_into (&spill_pseudos_bitmap
,
843 &try_hard_reg_pseudos
[hard_regno
+ j
]);
846 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
847 if ((int) spill_regno
>= lra_constraint_new_regno_start
848 && ! bitmap_bit_p (&lra_inheritance_pseudos
, spill_regno
)
849 && ! bitmap_bit_p (&lra_split_regs
, spill_regno
)
850 && ! bitmap_bit_p (&lra_optional_reload_pseudos
, spill_regno
))
852 insn_pseudos_num
= 0;
853 if (lra_dump_file
!= NULL
)
854 fprintf (lra_dump_file
, " Trying %d:", hard_regno
);
855 sparseset_clear (live_range_reload_inheritance_pseudos
);
856 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
858 if (bitmap_bit_p (&insn_conflict_pseudos
, spill_regno
))
860 for (r
= lra_reg_info
[spill_regno
].live_ranges
;
864 for (p
= r
->start
; p
<= r
->finish
; p
++)
868 for (r2
= start_point_ranges
[p
];
871 if (r2
->regno
>= lra_constraint_new_regno_start
)
872 sparseset_set_bit (live_range_reload_inheritance_pseudos
,
878 EXECUTE_IF_SET_IN_SPARSESET (live_range_reload_inheritance_pseudos
,
880 if ((int) reload_regno
!= regno
881 && (ira_reg_classes_intersect_p
882 [rclass
][regno_allocno_class_array
[reload_regno
]])
883 && live_pseudos_reg_renumber
[reload_regno
] < 0
884 && find_hard_regno_for (reload_regno
, &cost
, -1) < 0)
885 sorted_reload_pseudos
[n
++] = reload_regno
;
886 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
888 update_lives (spill_regno
, true);
889 if (lra_dump_file
!= NULL
)
890 fprintf (lra_dump_file
, " spill %d(freq=%d)",
891 spill_regno
, lra_reg_info
[spill_regno
].freq
);
893 hard_regno
= find_hard_regno_for (regno
, &cost
, -1);
896 assign_temporarily (regno
, hard_regno
);
897 qsort (sorted_reload_pseudos
, n
, sizeof (int),
898 reload_pseudo_compare_func
);
899 for (j
= 0; j
< n
; j
++)
901 reload_regno
= sorted_reload_pseudos
[j
];
902 lra_assert (live_pseudos_reg_renumber
[reload_regno
] < 0);
903 if ((reload_hard_regno
904 = find_hard_regno_for (reload_regno
,
905 &reload_cost
, -1)) >= 0)
907 if (lra_dump_file
!= NULL
)
908 fprintf (lra_dump_file
, " assign %d(cost=%d)",
909 reload_regno
, reload_cost
);
910 assign_temporarily (reload_regno
, reload_hard_regno
);
914 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
918 cost
+= lra_reg_info
[spill_regno
].freq
;
919 if (ira_reg_equiv
[spill_regno
].memory
!= NULL
920 || ira_reg_equiv
[spill_regno
].constant
!= NULL
)
921 for (x
= ira_reg_equiv
[spill_regno
].init_insns
;
924 cost
-= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (XEXP (x
, 0)));
926 if (best_insn_pseudos_num
> insn_pseudos_num
927 || (best_insn_pseudos_num
== insn_pseudos_num
928 && best_cost
> cost
))
930 best_insn_pseudos_num
= insn_pseudos_num
;
932 best_hard_regno
= hard_regno
;
933 bitmap_copy (&best_spill_pseudos_bitmap
, &spill_pseudos_bitmap
);
934 if (lra_dump_file
!= NULL
)
935 fprintf (lra_dump_file
, " Now best %d(cost=%d)\n",
938 assign_temporarily (regno
, -1);
939 for (j
= 0; j
< n
; j
++)
941 reload_regno
= sorted_reload_pseudos
[j
];
942 if (live_pseudos_reg_renumber
[reload_regno
] >= 0)
943 assign_temporarily (reload_regno
, -1);
946 if (lra_dump_file
!= NULL
)
947 fprintf (lra_dump_file
, "\n");
948 /* Restore the live hard reg pseudo info for spilled pseudos. */
949 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap
, 0, spill_regno
, bi
)
950 update_lives (spill_regno
, false);
955 EXECUTE_IF_SET_IN_BITMAP (&best_spill_pseudos_bitmap
, 0, spill_regno
, bi
)
957 if (lra_dump_file
!= NULL
)
958 fprintf (lra_dump_file
, " Spill %sr%d(hr=%d, freq=%d) for r%d\n",
959 ((int) spill_regno
< lra_constraint_new_regno_start
961 : bitmap_bit_p (&lra_inheritance_pseudos
, spill_regno
)
963 : bitmap_bit_p (&lra_split_regs
, spill_regno
)
965 : bitmap_bit_p (&lra_optional_reload_pseudos
, spill_regno
)
966 ? "optional reload " : "reload "),
967 spill_regno
, reg_renumber
[spill_regno
],
968 lra_reg_info
[spill_regno
].freq
, regno
);
969 update_lives (spill_regno
, true);
970 lra_setup_reg_renumber (spill_regno
, -1, false);
972 bitmap_ior_into (spilled_pseudo_bitmap
, &best_spill_pseudos_bitmap
);
973 return best_hard_regno
;
976 /* Assign HARD_REGNO to REGNO. */
978 assign_hard_regno (int hard_regno
, int regno
)
982 lra_assert (hard_regno
>= 0);
983 lra_setup_reg_renumber (regno
, hard_regno
, true);
984 update_lives (regno
, false);
986 i
< hard_regno_nregs
[hard_regno
][lra_reg_info
[regno
].biggest_mode
];
988 df_set_regs_ever_live (hard_regno
+ i
, true);
991 /* Array used for sorting different pseudos. */
992 static int *sorted_pseudos
;
994 /* The constraints pass is allowed to create equivalences between
995 pseudos that make the current allocation "incorrect" (in the sense
996 that pseudos are assigned to hard registers from their own conflict
997 sets). The global variable lra_risky_transformations_p says
998 whether this might have happened.
1000 Process pseudos assigned to hard registers (less frequently used
1001 first), spill if a conflict is found, and mark the spilled pseudos
1002 in SPILLED_PSEUDO_BITMAP. Set up LIVE_HARD_REG_PSEUDOS from
1003 pseudos, assigned to hard registers. */
1005 setup_live_pseudos_and_spill_after_risky_transforms (bitmap
1006 spilled_pseudo_bitmap
)
1008 int p
, i
, j
, n
, regno
, hard_regno
;
1009 unsigned int k
, conflict_regno
;
1011 HARD_REG_SET conflict_set
;
1012 enum machine_mode mode
;
1015 int max_regno
= max_reg_num ();
1017 if (! lra_risky_transformations_p
)
1019 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1020 if (reg_renumber
[i
] >= 0 && lra_reg_info
[i
].nrefs
> 0)
1021 update_lives (i
, false);
1024 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1025 if (reg_renumber
[i
] >= 0 && lra_reg_info
[i
].nrefs
> 0)
1026 sorted_pseudos
[n
++] = i
;
1027 qsort (sorted_pseudos
, n
, sizeof (int), pseudo_compare_func
);
1028 for (i
= n
- 1; i
>= 0; i
--)
1030 regno
= sorted_pseudos
[i
];
1031 hard_regno
= reg_renumber
[regno
];
1032 lra_assert (hard_regno
>= 0);
1033 mode
= lra_reg_info
[regno
].biggest_mode
;
1034 sparseset_clear (live_range_hard_reg_pseudos
);
1035 for (r
= lra_reg_info
[regno
].live_ranges
; r
!= NULL
; r
= r
->next
)
1037 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos
[r
->start
], 0, k
, bi
)
1038 sparseset_set_bit (live_range_hard_reg_pseudos
, k
);
1039 for (p
= r
->start
+ 1; p
<= r
->finish
; p
++)
1041 lra_live_range_t r2
;
1043 for (r2
= start_point_ranges
[p
];
1045 r2
= r2
->start_next
)
1046 if (live_pseudos_reg_renumber
[r2
->regno
] >= 0)
1047 sparseset_set_bit (live_range_hard_reg_pseudos
, r2
->regno
);
1050 COPY_HARD_REG_SET (conflict_set
, lra_no_alloc_regs
);
1051 IOR_HARD_REG_SET (conflict_set
, lra_reg_info
[regno
].conflict_hard_regs
);
1052 val
= lra_reg_info
[regno
].val
;
1053 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos
, conflict_regno
)
1054 if (val
!= lra_reg_info
[conflict_regno
].val
1055 /* If it is multi-register pseudos they should start on
1056 the same hard register. */
1057 || hard_regno
!= reg_renumber
[conflict_regno
])
1058 add_to_hard_reg_set (&conflict_set
,
1059 lra_reg_info
[conflict_regno
].biggest_mode
,
1060 reg_renumber
[conflict_regno
]);
1061 if (! overlaps_hard_reg_set_p (conflict_set
, mode
, hard_regno
))
1063 update_lives (regno
, false);
1066 bitmap_set_bit (spilled_pseudo_bitmap
, regno
);
1068 j
< hard_regno_nregs
[hard_regno
][PSEUDO_REGNO_MODE (regno
)];
1070 lra_hard_reg_usage
[hard_regno
+ j
] -= lra_reg_info
[regno
].freq
;
1071 reg_renumber
[regno
] = -1;
1072 if (lra_dump_file
!= NULL
)
1073 fprintf (lra_dump_file
, " Spill r%d after risky transformations\n",
1078 /* Improve allocation by assigning the same hard regno of inheritance
1079 pseudos to the connected pseudos. We need this because inheritance
1080 pseudos are allocated after reload pseudos in the thread and when
1081 we assign a hard register to a reload pseudo we don't know yet that
1082 the connected inheritance pseudos can get the same hard register.
1083 Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS. */
1085 improve_inheritance (bitmap changed_pseudos
)
1088 int regno
, another_regno
, hard_regno
, another_hard_regno
, cost
, i
, n
;
1089 lra_copy_t cp
, next_cp
;
1092 if (lra_inheritance_iter
> LRA_MAX_INHERITANCE_PASSES
)
1095 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos
, 0, k
, bi
)
1096 if (reg_renumber
[k
] >= 0 && lra_reg_info
[k
].nrefs
!= 0)
1097 sorted_pseudos
[n
++] = k
;
1098 qsort (sorted_pseudos
, n
, sizeof (int), pseudo_compare_func
);
1099 for (i
= 0; i
< n
; i
++)
1101 regno
= sorted_pseudos
[i
];
1102 hard_regno
= reg_renumber
[regno
];
1103 lra_assert (hard_regno
>= 0);
1104 for (cp
= lra_reg_info
[regno
].copies
; cp
!= NULL
; cp
= next_cp
)
1106 if (cp
->regno1
== regno
)
1108 next_cp
= cp
->regno1_next
;
1109 another_regno
= cp
->regno2
;
1111 else if (cp
->regno2
== regno
)
1113 next_cp
= cp
->regno2_next
;
1114 another_regno
= cp
->regno1
;
1118 /* Don't change reload pseudo allocation. It might have
1119 this allocation for a purpose and changing it can result
1121 if ((another_regno
< lra_constraint_new_regno_start
1122 || bitmap_bit_p (&lra_inheritance_pseudos
, another_regno
))
1123 && (another_hard_regno
= reg_renumber
[another_regno
]) >= 0
1124 && another_hard_regno
!= hard_regno
)
1126 if (lra_dump_file
!= NULL
)
1129 " Improving inheritance for %d(%d) and %d(%d)...\n",
1130 regno
, hard_regno
, another_regno
, another_hard_regno
);
1131 update_lives (another_regno
, true);
1132 lra_setup_reg_renumber (another_regno
, -1, false);
1134 == find_hard_regno_for (another_regno
, &cost
, hard_regno
))
1135 assign_hard_regno (hard_regno
, another_regno
);
1137 assign_hard_regno (another_hard_regno
, another_regno
);
1138 bitmap_set_bit (changed_pseudos
, another_regno
);
1145 /* Bitmap finally containing all pseudos spilled on this assignment
1147 static bitmap_head all_spilled_pseudos
;
1148 /* All pseudos whose allocation was changed. */
1149 static bitmap_head changed_pseudo_bitmap
;
1151 /* Assign hard registers to reload pseudos and other pseudos. */
1153 assign_by_spills (void)
1155 int i
, n
, nfails
, iter
, regno
, hard_regno
, cost
, restore_regno
;
1158 bitmap_head changed_insns
, do_not_assign_nonreload_pseudos
;
1159 bitmap_head non_reload_pseudos
;
1163 int max_regno
= max_reg_num ();
1165 for (n
= 0, i
= lra_constraint_new_regno_start
; i
< max_regno
; i
++)
1166 if (reg_renumber
[i
] < 0 && lra_reg_info
[i
].nrefs
!= 0
1167 && regno_allocno_class_array
[i
] != NO_REGS
)
1168 sorted_pseudos
[n
++] = i
;
1169 bitmap_initialize (&insn_conflict_pseudos
, ®_obstack
);
1170 bitmap_initialize (&spill_pseudos_bitmap
, ®_obstack
);
1171 bitmap_initialize (&best_spill_pseudos_bitmap
, ®_obstack
);
1172 update_hard_regno_preference_check
= XCNEWVEC (int, max_regno
);
1173 curr_update_hard_regno_preference_check
= 0;
1174 memset (try_hard_reg_pseudos_check
, 0, sizeof (try_hard_reg_pseudos_check
));
1175 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1176 bitmap_initialize (&try_hard_reg_pseudos
[i
], ®_obstack
);
1177 curr_pseudo_check
= 0;
1178 bitmap_initialize (&changed_insns
, ®_obstack
);
1179 bitmap_initialize (&non_reload_pseudos
, ®_obstack
);
1180 bitmap_ior (&non_reload_pseudos
, &lra_inheritance_pseudos
, &lra_split_regs
);
1181 bitmap_ior_into (&non_reload_pseudos
, &lra_optional_reload_pseudos
);
1182 for (iter
= 0; iter
<= 1; iter
++)
1184 qsort (sorted_pseudos
, n
, sizeof (int), reload_pseudo_compare_func
);
1186 for (i
= 0; i
< n
; i
++)
1188 regno
= sorted_pseudos
[i
];
1189 if (lra_dump_file
!= NULL
)
1190 fprintf (lra_dump_file
, " Assigning to %d "
1191 "(cl=%s, orig=%d, freq=%d, tfirst=%d, tfreq=%d)...\n",
1192 regno
, reg_class_names
[regno_allocno_class_array
[regno
]],
1193 ORIGINAL_REGNO (regno_reg_rtx
[regno
]),
1194 lra_reg_info
[regno
].freq
, regno_assign_info
[regno
].first
,
1195 regno_assign_info
[regno_assign_info
[regno
].first
].freq
);
1196 hard_regno
= find_hard_regno_for (regno
, &cost
, -1);
1197 reload_p
= ! bitmap_bit_p (&non_reload_pseudos
, regno
);
1198 if (hard_regno
< 0 && reload_p
)
1199 hard_regno
= spill_for (regno
, &all_spilled_pseudos
);
1203 sorted_pseudos
[nfails
++] = regno
;
1207 /* This register might have been spilled by the previous
1208 pass. Indicate that it is no longer spilled. */
1209 bitmap_clear_bit (&all_spilled_pseudos
, regno
);
1210 assign_hard_regno (hard_regno
, regno
);
1212 /* As non-reload pseudo assignment is changed we
1213 should reconsider insns referring for the
1215 bitmap_set_bit (&changed_pseudo_bitmap
, regno
);
1222 /* We did not assign hard regs to reload pseudos after two
1223 iteration. It means something is wrong with asm insn
1224 constraints. Report it. */
1226 bitmap_head failed_reload_insns
;
1228 bitmap_initialize (&failed_reload_insns
, ®_obstack
);
1229 for (i
= 0; i
< nfails
; i
++)
1231 regno
= sorted_pseudos
[i
];
1232 bitmap_ior_into (&failed_reload_insns
,
1233 &lra_reg_info
[regno
].insn_bitmap
);
1234 /* Assign an arbitrary hard register of regno class to
1235 avoid further trouble with the asm insns. */
1236 bitmap_clear_bit (&all_spilled_pseudos
, regno
);
1238 (ira_class_hard_regs
[regno_allocno_class_array
[regno
]][0],
1241 EXECUTE_IF_SET_IN_BITMAP (&failed_reload_insns
, 0, u
, bi
)
1243 insn
= lra_insn_recog_data
[u
]->insn
;
1244 if (asm_noperands (PATTERN (insn
)) >= 0)
1247 error_for_asm (insn
,
1248 "%<asm%> operand has impossible constraints");
1249 /* Avoid further trouble with this insn.
1250 For asm goto, instead of fixing up all the edges
1251 just clear the template and clear input operands
1252 (asm goto doesn't have any output operands). */
1255 rtx asm_op
= extract_asm_operands (PATTERN (insn
));
1256 ASM_OPERANDS_TEMPLATE (asm_op
) = ggc_strdup ("");
1257 ASM_OPERANDS_INPUT_VEC (asm_op
) = rtvec_alloc (0);
1258 ASM_OPERANDS_INPUT_CONSTRAINT_VEC (asm_op
) = rtvec_alloc (0);
1259 lra_update_insn_regno_info (insn
);
1263 PATTERN (insn
) = gen_rtx_USE (VOIDmode
, const0_rtx
);
1264 lra_set_insn_deleted (insn
);
1271 /* This is a very rare event. We can not assign a hard
1272 register to reload pseudo because the hard register was
1273 assigned to another reload pseudo on a previous
1274 assignment pass. For x86 example, on the 1st pass we
1275 assigned CX (although another hard register could be used
1276 for this) to reload pseudo in an insn, on the 2nd pass we
1277 need CX (and only this) hard register for a new reload
1278 pseudo in the same insn. */
1279 if (lra_dump_file
!= NULL
)
1280 fprintf (lra_dump_file
, " 2nd iter for reload pseudo assignments:\n");
1281 for (i
= 0; i
< nfails
; i
++)
1283 if (lra_dump_file
!= NULL
)
1284 fprintf (lra_dump_file
, " Reload r%d assignment failure\n",
1286 bitmap_ior_into (&changed_insns
,
1287 &lra_reg_info
[sorted_pseudos
[i
]].insn_bitmap
);
1290 /* FIXME: Look up the changed insns in the cached LRA insn data using
1291 an EXECUTE_IF_SET_IN_BITMAP over changed_insns. */
1293 FOR_BB_INSNS (bb
, insn
)
1294 if (bitmap_bit_p (&changed_insns
, INSN_UID (insn
)))
1296 lra_insn_recog_data_t data
;
1297 struct lra_insn_reg
*r
;
1299 data
= lra_get_insn_recog_data (insn
);
1300 for (r
= data
->regs
; r
!= NULL
; r
= r
->next
)
1303 /* A reload pseudo did not get a hard register on the
1304 first iteration because of the conflict with
1305 another reload pseudos in the same insn. So we
1306 consider only reload pseudos assigned to hard
1307 registers. We shall exclude inheritance pseudos as
1308 they can occur in original insns (not reload ones).
1309 We can omit the check for split pseudos because
1310 they occur only in move insns containing non-reload
1312 if (regno
< lra_constraint_new_regno_start
1313 || bitmap_bit_p (&lra_inheritance_pseudos
, regno
)
1314 || reg_renumber
[regno
] < 0)
1316 sorted_pseudos
[nfails
++] = regno
;
1317 if (lra_dump_file
!= NULL
)
1318 fprintf (lra_dump_file
,
1319 " Spill reload r%d(hr=%d, freq=%d)\n",
1320 regno
, reg_renumber
[regno
],
1321 lra_reg_info
[regno
].freq
);
1322 update_lives (regno
, true);
1323 lra_setup_reg_renumber (regno
, -1, false);
1328 improve_inheritance (&changed_pseudo_bitmap
);
1329 bitmap_clear (&non_reload_pseudos
);
1330 bitmap_clear (&changed_insns
);
1333 /* We should not assign to original pseudos of inheritance
1334 pseudos or split pseudos if any its inheritance pseudo did
1335 not get hard register or any its split pseudo was not split
1336 because undo inheritance/split pass will extend live range of
1337 such inheritance or split pseudos. */
1338 bitmap_initialize (&do_not_assign_nonreload_pseudos
, ®_obstack
);
1339 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos
, 0, u
, bi
)
1340 if ((restore_regno
= lra_reg_info
[u
].restore_regno
) >= 0
1341 && reg_renumber
[u
] < 0
1342 && bitmap_bit_p (&lra_inheritance_pseudos
, u
))
1343 bitmap_set_bit (&do_not_assign_nonreload_pseudos
, restore_regno
);
1344 EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs
, 0, u
, bi
)
1345 if ((restore_regno
= lra_reg_info
[u
].restore_regno
) >= 0
1346 && reg_renumber
[u
] >= 0)
1347 bitmap_set_bit (&do_not_assign_nonreload_pseudos
, restore_regno
);
1348 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1349 if (((i
< lra_constraint_new_regno_start
1350 && ! bitmap_bit_p (&do_not_assign_nonreload_pseudos
, i
))
1351 || (bitmap_bit_p (&lra_inheritance_pseudos
, i
)
1352 && lra_reg_info
[i
].restore_regno
>= 0)
1353 || (bitmap_bit_p (&lra_split_regs
, i
)
1354 && lra_reg_info
[i
].restore_regno
>= 0)
1355 || bitmap_bit_p (&lra_optional_reload_pseudos
, i
))
1356 && reg_renumber
[i
] < 0 && lra_reg_info
[i
].nrefs
!= 0
1357 && regno_allocno_class_array
[i
] != NO_REGS
)
1358 sorted_pseudos
[n
++] = i
;
1359 bitmap_clear (&do_not_assign_nonreload_pseudos
);
1360 if (n
!= 0 && lra_dump_file
!= NULL
)
1361 fprintf (lra_dump_file
, " Reassigning non-reload pseudos\n");
1362 qsort (sorted_pseudos
, n
, sizeof (int), pseudo_compare_func
);
1363 for (i
= 0; i
< n
; i
++)
1365 regno
= sorted_pseudos
[i
];
1366 hard_regno
= find_hard_regno_for (regno
, &cost
, -1);
1367 if (hard_regno
>= 0)
1369 assign_hard_regno (hard_regno
, regno
);
1370 /* We change allocation for non-reload pseudo on this
1371 iteration -- mark the pseudo for invalidation of used
1372 alternatives of insns containing the pseudo. */
1373 bitmap_set_bit (&changed_pseudo_bitmap
, regno
);
1377 free (update_hard_regno_preference_check
);
1378 bitmap_clear (&best_spill_pseudos_bitmap
);
1379 bitmap_clear (&spill_pseudos_bitmap
);
1380 bitmap_clear (&insn_conflict_pseudos
);
1384 /* Entry function to assign hard registers to new reload pseudos
1385 starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling
1386 of old pseudos) and possibly to the old pseudos. The function adds
1387 what insns to process for the next constraint pass. Those are all
1388 insns who contains non-reload and non-inheritance pseudos with
1391 Return true if we did not spill any non-reload and non-inheritance
1399 bitmap_head insns_to_process
;
1401 int max_regno
= max_reg_num ();
1403 timevar_push (TV_LRA_ASSIGN
);
1405 sorted_pseudos
= XNEWVEC (int, max_regno
);
1406 sorted_reload_pseudos
= XNEWVEC (int, max_regno
);
1407 regno_allocno_class_array
= XNEWVEC (enum reg_class
, max_regno
);
1408 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1409 regno_allocno_class_array
[i
] = lra_get_allocno_class (i
);
1410 init_regno_assign_info ();
1411 bitmap_initialize (&all_spilled_pseudos
, ®_obstack
);
1412 create_live_range_start_chains ();
1413 setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos
);
1414 #ifdef ENABLE_CHECKING
1415 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1416 if (lra_reg_info
[i
].nrefs
!= 0 && reg_renumber
[i
] >= 0
1417 && lra_reg_info
[i
].call_p
1418 && overlaps_hard_reg_set_p (call_used_reg_set
,
1419 PSEUDO_REGNO_MODE (i
), reg_renumber
[i
]))
1422 /* Setup insns to process on the next constraint pass. */
1423 bitmap_initialize (&changed_pseudo_bitmap
, ®_obstack
);
1424 init_live_reload_and_inheritance_pseudos ();
1425 assign_by_spills ();
1426 finish_live_reload_and_inheritance_pseudos ();
1427 bitmap_ior_into (&changed_pseudo_bitmap
, &all_spilled_pseudos
);
1429 EXECUTE_IF_SET_IN_BITMAP (&all_spilled_pseudos
, 0, u
, bi
)
1430 /* We ignore spilled pseudos created on last inheritance pass
1431 because they will be removed. */
1432 if (lra_reg_info
[u
].restore_regno
< 0)
1434 no_spills_p
= false;
1437 finish_live_range_start_chains ();
1438 bitmap_clear (&all_spilled_pseudos
);
1439 bitmap_initialize (&insns_to_process
, ®_obstack
);
1440 EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap
, 0, u
, bi
)
1441 bitmap_ior_into (&insns_to_process
, &lra_reg_info
[u
].insn_bitmap
);
1442 bitmap_clear (&changed_pseudo_bitmap
);
1443 EXECUTE_IF_SET_IN_BITMAP (&insns_to_process
, 0, u
, bi
)
1445 lra_push_insn_by_uid (u
);
1446 /* Invalidate alternatives for insn should be processed. */
1447 lra_set_used_insn_alternative_by_uid (u
, -1);
1449 bitmap_clear (&insns_to_process
);
1450 finish_regno_assign_info ();
1451 free (regno_allocno_class_array
);
1452 free (sorted_pseudos
);
1453 free (sorted_reload_pseudos
);
1455 timevar_pop (TV_LRA_ASSIGN
);