1 /* Build live ranges for 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 contains code to build pseudo live-ranges (analogous
23 structures used in IRA, so read comments about the live-ranges
24 there) and other info necessary for other passes to assign
25 hard-registers to pseudos, coalesce the spilled pseudos, and assign
26 stack memory slots to spilled pseudos. */
30 #include "coretypes.h"
32 #include "hard-reg-set.h"
35 #include "insn-config.h"
46 #include "basic-block.h"
50 #include "sparseset.h"
53 /* Program points are enumerated by numbers from range
54 0..LRA_LIVE_MAX_POINT-1. There are approximately two times more
55 program points than insns. Program points are places in the
56 program where liveness info can be changed. In most general case
57 (there are more complicated cases too) some program points
58 correspond to places where input operand dies and other ones
59 correspond to places where output operands are born. */
60 int lra_live_max_point
;
62 /* Accumulated execution frequency of all references for each hard
64 int lra_hard_reg_usage
[FIRST_PSEUDO_REGISTER
];
66 /* A global flag whose true value says to build live ranges for all
67 pseudos, otherwise the live ranges only for pseudos got memory is
68 build. True value means also building copies and setting up hard
69 register preferences. The complete info is necessary only for the
70 assignment pass. The complete info is not needed for the
71 coalescing and spill passes. */
72 static bool complete_info_p
;
74 /* Pseudos live at current point in the RTL scan. */
75 static sparseset pseudos_live
;
77 /* Pseudos probably living through calls and setjumps. As setjump is
78 a call too, if a bit in PSEUDOS_LIVE_THROUGH_SETJUMPS is set up
79 then the corresponding bit in PSEUDOS_LIVE_THROUGH_CALLS is set up
80 too. These data are necessary for cases when only one subreg of a
81 multi-reg pseudo is set up after a call. So we decide it is
82 probably live when traversing bb backward. We are sure about
83 living when we see its usage or definition of the pseudo. */
84 static sparseset pseudos_live_through_calls
;
85 static sparseset pseudos_live_through_setjumps
;
87 /* Set of hard regs (except eliminable ones) currently live. */
88 static HARD_REG_SET hard_regs_live
;
90 /* Set of pseudos and hard registers start living/dying in the current
91 insn. These sets are used to update REG_DEAD and REG_UNUSED notes
93 static sparseset start_living
, start_dying
;
95 /* Set of pseudos and hard regs dead and unused in the current
97 static sparseset unused_set
, dead_set
;
99 /* Pool for pseudo live ranges. */
100 static alloc_pool live_range_pool
;
102 /* Free live range LR. */
104 free_live_range (lra_live_range_t lr
)
106 pool_free (live_range_pool
, lr
);
109 /* Free live range list LR. */
111 free_live_range_list (lra_live_range_t lr
)
113 lra_live_range_t next
;
118 free_live_range (lr
);
123 /* Create and return pseudo live range with given attributes. */
124 static lra_live_range_t
125 create_live_range (int regno
, int start
, int finish
, lra_live_range_t next
)
129 p
= (lra_live_range_t
) pool_alloc (live_range_pool
);
137 /* Copy live range R and return the result. */
138 static lra_live_range_t
139 copy_live_range (lra_live_range_t r
)
143 p
= (lra_live_range_t
) pool_alloc (live_range_pool
);
148 /* Copy live range list given by its head R and return the result. */
150 lra_copy_live_range_list (lra_live_range_t r
)
152 lra_live_range_t p
, first
, *chain
;
155 for (chain
= &first
; r
!= NULL
; r
= r
->next
)
157 p
= copy_live_range (r
);
164 /* Merge *non-intersected* ranges R1 and R2 and returns the result.
165 The function maintains the order of ranges and tries to minimize
166 size of the result range list. Ranges R1 and R2 may not be used
169 lra_merge_live_ranges (lra_live_range_t r1
, lra_live_range_t r2
)
171 lra_live_range_t first
, last
, temp
;
177 for (first
= last
= NULL
; r1
!= NULL
&& r2
!= NULL
;)
179 if (r1
->start
< r2
->start
)
185 if (r1
->start
== r2
->finish
+ 1)
187 /* Joint ranges: merge r1 and r2 into r1. */
188 r1
->start
= r2
->start
;
191 pool_free (live_range_pool
, temp
);
195 gcc_assert (r2
->finish
+ 1 < r1
->start
);
196 /* Add r1 to the result. */
216 lra_assert (r2
!= NULL
);
225 /* Return TRUE if live ranges R1 and R2 intersect. */
227 lra_intersected_live_ranges_p (lra_live_range_t r1
, lra_live_range_t r2
)
229 /* Remember the live ranges are always kept ordered. */
230 while (r1
!= NULL
&& r2
!= NULL
)
232 if (r1
->start
> r2
->finish
)
234 else if (r2
->start
> r1
->finish
)
242 /* The function processing birth of hard register REGNO. It updates
243 living hard regs, conflict hard regs for living pseudos, and
246 make_hard_regno_born (int regno
)
250 lra_assert (regno
< FIRST_PSEUDO_REGISTER
);
251 if (TEST_HARD_REG_BIT (lra_no_alloc_regs
, regno
)
252 || TEST_HARD_REG_BIT (hard_regs_live
, regno
))
254 SET_HARD_REG_BIT (hard_regs_live
, regno
);
255 sparseset_set_bit (start_living
, regno
);
256 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, i
)
257 SET_HARD_REG_BIT (lra_reg_info
[i
].conflict_hard_regs
, regno
);
260 /* Process the death of hard register REGNO. This updates
261 hard_regs_live and START_DYING. */
263 make_hard_regno_dead (int regno
)
265 lra_assert (regno
< FIRST_PSEUDO_REGISTER
);
266 if (TEST_HARD_REG_BIT (lra_no_alloc_regs
, regno
)
267 || ! TEST_HARD_REG_BIT (hard_regs_live
, regno
))
269 sparseset_set_bit (start_dying
, regno
);
270 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
273 /* Mark pseudo REGNO as living at program point POINT, update conflicting
274 hard registers of the pseudo and START_LIVING, and start a new live
275 range for the pseudo corresponding to REGNO if it is necessary. */
277 mark_pseudo_live (int regno
, int point
)
281 lra_assert (regno
>= FIRST_PSEUDO_REGISTER
);
282 lra_assert (! sparseset_bit_p (pseudos_live
, regno
));
283 sparseset_set_bit (pseudos_live
, regno
);
284 IOR_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
, hard_regs_live
);
286 if ((complete_info_p
|| lra_get_regno_hard_regno (regno
) < 0)
287 && ((p
= lra_reg_info
[regno
].live_ranges
) == NULL
288 || (p
->finish
!= point
&& p
->finish
+ 1 != point
)))
289 lra_reg_info
[regno
].live_ranges
290 = create_live_range (regno
, point
, -1, p
);
291 sparseset_set_bit (start_living
, regno
);
294 /* Mark pseudo REGNO as not living at program point POINT and update
296 This finishes the current live range for the pseudo corresponding
299 mark_pseudo_dead (int regno
, int point
)
303 lra_assert (regno
>= FIRST_PSEUDO_REGISTER
);
304 lra_assert (sparseset_bit_p (pseudos_live
, regno
));
305 sparseset_clear_bit (pseudos_live
, regno
);
306 sparseset_set_bit (start_dying
, regno
);
307 if (complete_info_p
|| lra_get_regno_hard_regno (regno
) < 0)
309 p
= lra_reg_info
[regno
].live_ranges
;
310 lra_assert (p
!= NULL
);
315 /* Mark register REGNO (pseudo or hard register) in MODE as live
316 at program point POINT.
317 Return TRUE if the liveness tracking sets were modified,
318 or FALSE if nothing changed. */
320 mark_regno_live (int regno
, enum machine_mode mode
, int point
)
323 bool changed
= false;
325 if (regno
< FIRST_PSEUDO_REGISTER
)
327 for (last
= regno
+ hard_regno_nregs
[regno
][mode
];
330 make_hard_regno_born (regno
);
332 else if (! sparseset_bit_p (pseudos_live
, regno
))
334 mark_pseudo_live (regno
, point
);
341 /* Mark register REGNO in MODE as dead at program point POINT.
342 Return TRUE if the liveness tracking sets were modified,
343 or FALSE if nothing changed. */
345 mark_regno_dead (int regno
, enum machine_mode mode
, int point
)
348 bool changed
= false;
350 if (regno
< FIRST_PSEUDO_REGISTER
)
352 for (last
= regno
+ hard_regno_nregs
[regno
][mode
];
355 make_hard_regno_dead (regno
);
357 else if (sparseset_bit_p (pseudos_live
, regno
))
359 mark_pseudo_dead (regno
, point
);
365 /* Insn currently scanned. */
366 static rtx_insn
*curr_insn
;
368 static lra_insn_recog_data_t curr_id
;
369 /* The insn static data. */
370 static struct lra_static_insn_data
*curr_static_id
;
372 /* Return true when one of the predecessor edges of BB is marked with
373 EDGE_ABNORMAL_CALL or EDGE_EH. */
375 bb_has_abnormal_call_pred (basic_block bb
)
380 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
382 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
388 /* Vec containing execution frequencies of program points. */
389 static vec
<int> point_freq_vec
;
391 /* The start of the above vector elements. */
394 /* Increment the current program point POINT to the next point which has
395 execution frequency FREQ. */
397 next_program_point (int &point
, int freq
)
399 point_freq_vec
.safe_push (freq
);
400 lra_point_freq
= point_freq_vec
.address ();
404 /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
406 lra_setup_reload_pseudo_preferenced_hard_reg (int regno
,
407 int hard_regno
, int profit
)
409 lra_assert (regno
>= lra_constraint_new_regno_start
);
410 if (lra_reg_info
[regno
].preferred_hard_regno1
== hard_regno
)
411 lra_reg_info
[regno
].preferred_hard_regno_profit1
+= profit
;
412 else if (lra_reg_info
[regno
].preferred_hard_regno2
== hard_regno
)
413 lra_reg_info
[regno
].preferred_hard_regno_profit2
+= profit
;
414 else if (lra_reg_info
[regno
].preferred_hard_regno1
< 0)
416 lra_reg_info
[regno
].preferred_hard_regno1
= hard_regno
;
417 lra_reg_info
[regno
].preferred_hard_regno_profit1
= profit
;
419 else if (lra_reg_info
[regno
].preferred_hard_regno2
< 0
420 || profit
> lra_reg_info
[regno
].preferred_hard_regno_profit2
)
422 lra_reg_info
[regno
].preferred_hard_regno2
= hard_regno
;
423 lra_reg_info
[regno
].preferred_hard_regno_profit2
= profit
;
427 /* Keep the 1st hard regno as more profitable. */
428 if (lra_reg_info
[regno
].preferred_hard_regno1
>= 0
429 && lra_reg_info
[regno
].preferred_hard_regno2
>= 0
430 && (lra_reg_info
[regno
].preferred_hard_regno_profit2
431 > lra_reg_info
[regno
].preferred_hard_regno_profit1
))
435 temp
= lra_reg_info
[regno
].preferred_hard_regno1
;
436 lra_reg_info
[regno
].preferred_hard_regno1
437 = lra_reg_info
[regno
].preferred_hard_regno2
;
438 lra_reg_info
[regno
].preferred_hard_regno2
= temp
;
439 temp
= lra_reg_info
[regno
].preferred_hard_regno_profit1
;
440 lra_reg_info
[regno
].preferred_hard_regno_profit1
441 = lra_reg_info
[regno
].preferred_hard_regno_profit2
;
442 lra_reg_info
[regno
].preferred_hard_regno_profit2
= temp
;
444 if (lra_dump_file
!= NULL
)
446 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno1
) >= 0)
447 fprintf (lra_dump_file
,
448 " Hard reg %d is preferable by r%d with profit %d\n",
450 lra_reg_info
[regno
].preferred_hard_regno_profit1
);
451 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno2
) >= 0)
452 fprintf (lra_dump_file
,
453 " Hard reg %d is preferable by r%d with profit %d\n",
455 lra_reg_info
[regno
].preferred_hard_regno_profit2
);
459 /* Check that REGNO living through calls and setjumps, set up conflict
460 regs, and clear corresponding bits in PSEUDOS_LIVE_THROUGH_CALLS and
461 PSEUDOS_LIVE_THROUGH_SETJUMPS. */
463 check_pseudos_live_through_calls (int regno
)
467 if (! sparseset_bit_p (pseudos_live_through_calls
, regno
))
469 sparseset_clear_bit (pseudos_live_through_calls
, regno
);
470 IOR_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
,
473 for (hr
= 0; hr
< FIRST_PSEUDO_REGISTER
; hr
++)
474 if (HARD_REGNO_CALL_PART_CLOBBERED (hr
, PSEUDO_REGNO_MODE (regno
)))
475 SET_HARD_REG_BIT (lra_reg_info
[regno
].conflict_hard_regs
, hr
);
476 #ifdef ENABLE_CHECKING
477 lra_reg_info
[regno
].call_p
= true;
479 if (! sparseset_bit_p (pseudos_live_through_setjumps
, regno
))
481 sparseset_clear_bit (pseudos_live_through_setjumps
, regno
);
482 /* Don't allocate pseudos that cross setjmps or any call, if this
483 function receives a nonlocal goto. */
484 SET_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
);
487 /* Process insns of the basic block BB to update pseudo live ranges,
488 pseudo hard register conflicts, and insn notes. We do it on
489 backward scan of BB insns. CURR_POINT is the program point where
490 BB ends. The function updates this counter and returns in
491 CURR_POINT the program point where BB starts. */
493 process_bb_lives (basic_block bb
, int &curr_point
)
501 bool need_curr_point_incr
;
503 reg_live_out
= df_get_live_out (bb
);
504 sparseset_clear (pseudos_live
);
505 sparseset_clear (pseudos_live_through_calls
);
506 sparseset_clear (pseudos_live_through_setjumps
);
507 REG_SET_TO_HARD_REG_SET (hard_regs_live
, reg_live_out
);
508 AND_COMPL_HARD_REG_SET (hard_regs_live
, eliminable_regset
);
509 AND_COMPL_HARD_REG_SET (hard_regs_live
, lra_no_alloc_regs
);
510 EXECUTE_IF_SET_IN_BITMAP (reg_live_out
, FIRST_PSEUDO_REGISTER
, j
, bi
)
511 mark_pseudo_live (j
, curr_point
);
513 freq
= REG_FREQ_FROM_BB (bb
);
515 if (lra_dump_file
!= NULL
)
516 fprintf (lra_dump_file
, " BB %d\n", bb
->index
);
518 /* Scan the code of this basic block, noting which pseudos and hard
519 regs are born or die.
521 Note that this loop treats uninitialized values as live until the
522 beginning of the block. For example, if an instruction uses
523 (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
524 FOO will remain live until the beginning of the block. Likewise
525 if FOO is not set at all. This is unnecessarily pessimistic, but
526 it probably doesn't matter much in practice. */
527 FOR_BB_INSNS_REVERSE (bb
, curr_insn
)
530 int dst_regno
, src_regno
;
532 struct lra_insn_reg
*reg
;
534 if (!NONDEBUG_INSN_P (curr_insn
))
537 curr_id
= lra_get_insn_recog_data (curr_insn
);
538 curr_static_id
= curr_id
->insn_static_data
;
539 if (lra_dump_file
!= NULL
)
540 fprintf (lra_dump_file
, " Insn %u: point = %d\n",
541 INSN_UID (curr_insn
), curr_point
);
543 /* Update max ref width and hard reg usage. */
544 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
545 if (reg
->regno
>= FIRST_PSEUDO_REGISTER
546 && (GET_MODE_SIZE (reg
->biggest_mode
)
547 > GET_MODE_SIZE (lra_reg_info
[reg
->regno
].biggest_mode
)))
548 lra_reg_info
[reg
->regno
].biggest_mode
= reg
->biggest_mode
;
549 else if (reg
->regno
< FIRST_PSEUDO_REGISTER
)
550 lra_hard_reg_usage
[reg
->regno
] += freq
;
552 call_p
= CALL_P (curr_insn
);
554 && (set
= single_set (curr_insn
)) != NULL_RTX
555 && REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
))
556 /* Check that source regno does not conflict with
557 destination regno to exclude most impossible
559 && ((((src_regno
= REGNO (SET_SRC (set
))) >= FIRST_PSEUDO_REGISTER
560 && ! sparseset_bit_p (pseudos_live
, src_regno
))
561 || (src_regno
< FIRST_PSEUDO_REGISTER
562 && ! TEST_HARD_REG_BIT (hard_regs_live
, src_regno
)))
563 /* It might be 'inheritance pseudo <- reload pseudo'. */
564 || (src_regno
>= lra_constraint_new_regno_start
565 && ((int) REGNO (SET_DEST (set
))
566 >= lra_constraint_new_regno_start
)
567 /* Remember to skip special cases where src/dest regnos are
568 the same, e.g. insn SET pattern has matching constraints
570 && src_regno
!= (int) REGNO (SET_DEST (set
)))))
572 int hard_regno
= -1, regno
= -1;
574 dst_regno
= REGNO (SET_DEST (set
));
575 if (dst_regno
>= lra_constraint_new_regno_start
576 && src_regno
>= lra_constraint_new_regno_start
)
577 lra_create_copy (dst_regno
, src_regno
, freq
);
578 else if (dst_regno
>= lra_constraint_new_regno_start
)
580 if ((hard_regno
= src_regno
) >= FIRST_PSEUDO_REGISTER
)
581 hard_regno
= reg_renumber
[src_regno
];
584 else if (src_regno
>= lra_constraint_new_regno_start
)
586 if ((hard_regno
= dst_regno
) >= FIRST_PSEUDO_REGISTER
)
587 hard_regno
= reg_renumber
[dst_regno
];
590 if (regno
>= 0 && hard_regno
>= 0)
591 lra_setup_reload_pseudo_preferenced_hard_reg
592 (regno
, hard_regno
, freq
);
595 sparseset_clear (start_living
);
597 /* Try to avoid unnecessary program point increments, this saves
598 a lot of time in remove_some_program_points_and_update_live_ranges.
599 We only need an increment if something becomes live or dies at this
601 need_curr_point_incr
= false;
603 /* Mark each defined value as live. We need to do this for
604 unused values because they still conflict with quantities
605 that are live at the time of the definition. */
606 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
607 if (reg
->type
!= OP_IN
)
609 need_curr_point_incr
|= mark_regno_live (reg
->regno
,
612 check_pseudos_live_through_calls (reg
->regno
);
615 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
616 if (reg
->type
!= OP_IN
)
617 make_hard_regno_born (reg
->regno
);
619 sparseset_copy (unused_set
, start_living
);
621 sparseset_clear (start_dying
);
623 /* See which defined values die here. */
624 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
625 if (reg
->type
== OP_OUT
&& ! reg
->early_clobber
&& ! reg
->subreg_p
)
626 need_curr_point_incr
|= mark_regno_dead (reg
->regno
,
630 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
631 if (reg
->type
== OP_OUT
&& ! reg
->early_clobber
&& ! reg
->subreg_p
)
632 make_hard_regno_dead (reg
->regno
);
636 if (flag_use_caller_save
)
638 HARD_REG_SET this_call_used_reg_set
;
639 get_call_reg_set_usage (curr_insn
, &this_call_used_reg_set
,
642 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, j
)
643 IOR_HARD_REG_SET (lra_reg_info
[j
].actual_call_used_reg_set
,
644 this_call_used_reg_set
);
647 sparseset_ior (pseudos_live_through_calls
,
648 pseudos_live_through_calls
, pseudos_live
);
649 if (cfun
->has_nonlocal_label
650 || find_reg_note (curr_insn
, REG_SETJMP
,
651 NULL_RTX
) != NULL_RTX
)
652 sparseset_ior (pseudos_live_through_setjumps
,
653 pseudos_live_through_setjumps
, pseudos_live
);
656 /* Increment the current program point if we must. */
657 if (need_curr_point_incr
)
658 next_program_point (curr_point
, freq
);
660 sparseset_clear (start_living
);
662 need_curr_point_incr
= false;
664 /* Mark each used value as live. */
665 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
666 if (reg
->type
== OP_IN
)
668 need_curr_point_incr
|= mark_regno_live (reg
->regno
,
671 check_pseudos_live_through_calls (reg
->regno
);
674 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
675 if (reg
->type
== OP_IN
)
676 make_hard_regno_born (reg
->regno
);
678 if (curr_id
->arg_hard_regs
!= NULL
)
679 /* Make argument hard registers live. */
680 for (i
= 0; (regno
= curr_id
->arg_hard_regs
[i
]) >= 0; i
++)
681 make_hard_regno_born (regno
);
683 sparseset_and_compl (dead_set
, start_living
, start_dying
);
685 /* Mark early clobber outputs dead. */
686 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
687 if (reg
->type
== OP_OUT
&& reg
->early_clobber
&& ! reg
->subreg_p
)
688 need_curr_point_incr
|= mark_regno_dead (reg
->regno
,
692 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
693 if (reg
->type
== OP_OUT
&& reg
->early_clobber
&& ! reg
->subreg_p
)
694 make_hard_regno_dead (reg
->regno
);
696 if (need_curr_point_incr
)
697 next_program_point (curr_point
, freq
);
700 for (link_loc
= ®_NOTES (curr_insn
); (link
= *link_loc
) != NULL_RTX
;)
702 if (REG_NOTE_KIND (link
) != REG_DEAD
703 && REG_NOTE_KIND (link
) != REG_UNUSED
)
705 else if (REG_P (XEXP (link
, 0)))
707 regno
= REGNO (XEXP (link
, 0));
708 if ((REG_NOTE_KIND (link
) == REG_DEAD
709 && ! sparseset_bit_p (dead_set
, regno
))
710 || (REG_NOTE_KIND (link
) == REG_UNUSED
711 && ! sparseset_bit_p (unused_set
, regno
)))
713 *link_loc
= XEXP (link
, 1);
716 if (REG_NOTE_KIND (link
) == REG_DEAD
)
717 sparseset_clear_bit (dead_set
, regno
);
718 else if (REG_NOTE_KIND (link
) == REG_UNUSED
)
719 sparseset_clear_bit (unused_set
, regno
);
721 link_loc
= &XEXP (link
, 1);
723 EXECUTE_IF_SET_IN_SPARSESET (dead_set
, j
)
724 add_reg_note (curr_insn
, REG_DEAD
, regno_reg_rtx
[j
]);
725 EXECUTE_IF_SET_IN_SPARSESET (unused_set
, j
)
726 add_reg_note (curr_insn
, REG_UNUSED
, regno_reg_rtx
[j
]);
729 #ifdef EH_RETURN_DATA_REGNO
730 if (bb_has_eh_pred (bb
))
733 unsigned int regno
= EH_RETURN_DATA_REGNO (j
);
735 if (regno
== INVALID_REGNUM
)
737 make_hard_regno_born (regno
);
741 /* Pseudos can't go in stack regs at the start of a basic block that
742 is reached by an abnormal edge. Likewise for call clobbered regs,
743 because caller-save, fixup_abnormal_edges and possibly the table
744 driven EH machinery are not quite ready to handle such pseudos
745 live across such edges. */
746 if (bb_has_abnormal_pred (bb
))
749 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, px
)
750 lra_reg_info
[px
].no_stack_p
= true;
751 for (px
= FIRST_STACK_REG
; px
<= LAST_STACK_REG
; px
++)
752 make_hard_regno_born (px
);
754 /* No need to record conflicts for call clobbered regs if we
755 have nonlocal labels around, as we don't ever try to
756 allocate such regs in this case. */
757 if (!cfun
->has_nonlocal_label
&& bb_has_abnormal_call_pred (bb
))
758 for (px
= 0; px
< FIRST_PSEUDO_REGISTER
; px
++)
759 if (call_used_regs
[px
])
760 make_hard_regno_born (px
);
763 /* See if we'll need an increment at the end of this basic block.
764 An increment is needed if the PSEUDOS_LIVE set is not empty,
765 to make sure the finish points are set up correctly. */
766 need_curr_point_incr
= (sparseset_cardinality (pseudos_live
) > 0);
768 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, i
)
769 mark_pseudo_dead (i
, curr_point
);
771 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb
), FIRST_PSEUDO_REGISTER
, j
, bi
)
773 if (sparseset_cardinality (pseudos_live_through_calls
) == 0)
775 if (sparseset_bit_p (pseudos_live_through_calls
, j
))
776 check_pseudos_live_through_calls (j
);
779 if (need_curr_point_incr
)
780 next_program_point (curr_point
, freq
);
783 /* Compress pseudo live ranges by removing program points where
784 nothing happens. Complexity of many algorithms in LRA is linear
785 function of program points number. To speed up the code we try to
786 minimize the number of the program points here. */
788 remove_some_program_points_and_update_live_ranges (void)
793 lra_live_range_t r
, prev_r
, next_r
;
794 sbitmap born_or_dead
, born
, dead
;
795 sbitmap_iterator sbi
;
796 bool born_p
, dead_p
, prev_born_p
, prev_dead_p
;
798 born
= sbitmap_alloc (lra_live_max_point
);
799 dead
= sbitmap_alloc (lra_live_max_point
);
802 max_regno
= max_reg_num ();
803 for (i
= FIRST_PSEUDO_REGISTER
; i
< (unsigned) max_regno
; i
++)
805 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
807 lra_assert (r
->start
<= r
->finish
);
808 bitmap_set_bit (born
, r
->start
);
809 bitmap_set_bit (dead
, r
->finish
);
812 born_or_dead
= sbitmap_alloc (lra_live_max_point
);
813 bitmap_ior (born_or_dead
, born
, dead
);
814 map
= XCNEWVEC (int, lra_live_max_point
);
816 prev_born_p
= prev_dead_p
= false;
817 EXECUTE_IF_SET_IN_BITMAP (born_or_dead
, 0, i
, sbi
)
819 born_p
= bitmap_bit_p (born
, i
);
820 dead_p
= bitmap_bit_p (dead
, i
);
821 if ((prev_born_p
&& ! prev_dead_p
&& born_p
&& ! dead_p
)
822 || (prev_dead_p
&& ! prev_born_p
&& dead_p
&& ! born_p
))
825 lra_point_freq
[n
] = MAX (lra_point_freq
[n
], lra_point_freq
[i
]);
830 lra_point_freq
[n
] = lra_point_freq
[i
];
832 prev_born_p
= born_p
;
833 prev_dead_p
= dead_p
;
835 sbitmap_free (born_or_dead
);
839 if (lra_dump_file
!= NULL
)
840 fprintf (lra_dump_file
, "Compressing live ranges: from %d to %d - %d%%\n",
841 lra_live_max_point
, n
, 100 * n
/ lra_live_max_point
);
842 if (n
< lra_live_max_point
)
844 lra_live_max_point
= n
;
845 for (i
= FIRST_PSEUDO_REGISTER
; i
< (unsigned) max_regno
; i
++)
847 for (prev_r
= NULL
, r
= lra_reg_info
[i
].live_ranges
;
852 r
->start
= map
[r
->start
];
853 r
->finish
= map
[r
->finish
];
854 if (prev_r
== NULL
|| prev_r
->start
> r
->finish
+ 1)
859 prev_r
->start
= r
->start
;
860 prev_r
->next
= next_r
;
868 /* Print live ranges R to file F. */
870 lra_print_live_range_list (FILE *f
, lra_live_range_t r
)
872 for (; r
!= NULL
; r
= r
->next
)
873 fprintf (f
, " [%d..%d]", r
->start
, r
->finish
);
878 debug (lra_live_range
&ref
)
880 lra_print_live_range_list (stderr
, &ref
);
884 debug (lra_live_range
*ptr
)
889 fprintf (stderr
, "<nil>\n");
892 /* Print live ranges R to stderr. */
894 lra_debug_live_range_list (lra_live_range_t r
)
896 lra_print_live_range_list (stderr
, r
);
899 /* Print live ranges of pseudo REGNO to file F. */
901 print_pseudo_live_ranges (FILE *f
, int regno
)
903 if (lra_reg_info
[regno
].live_ranges
== NULL
)
905 fprintf (f
, " r%d:", regno
);
906 lra_print_live_range_list (f
, lra_reg_info
[regno
].live_ranges
);
909 /* Print live ranges of pseudo REGNO to stderr. */
911 lra_debug_pseudo_live_ranges (int regno
)
913 print_pseudo_live_ranges (stderr
, regno
);
916 /* Print live ranges of all pseudos to file F. */
918 print_live_ranges (FILE *f
)
922 max_regno
= max_reg_num ();
923 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
924 print_pseudo_live_ranges (f
, i
);
927 /* Print live ranges of all pseudos to stderr. */
929 lra_debug_live_ranges (void)
931 print_live_ranges (stderr
);
934 /* Compress pseudo live ranges. */
936 compress_live_ranges (void)
938 remove_some_program_points_and_update_live_ranges ();
939 if (lra_dump_file
!= NULL
)
941 fprintf (lra_dump_file
, "Ranges after the compression:\n");
942 print_live_ranges (lra_dump_file
);
946 /* The number of the current live range pass. */
947 int lra_live_range_iter
;
949 /* The main entry function creates live ranges only for memory pseudos
950 (or for all ones if ALL_P), set up CONFLICT_HARD_REGS for
953 lra_create_live_ranges (bool all_p
)
956 int i
, hard_regno
, max_regno
= max_reg_num ();
958 bool have_referenced_pseudos
= false;
960 timevar_push (TV_LRA_CREATE_LIVE_RANGES
);
962 complete_info_p
= all_p
;
963 if (lra_dump_file
!= NULL
)
964 fprintf (lra_dump_file
,
965 "\n********** Pseudo live ranges #%d: **********\n\n",
966 ++lra_live_range_iter
);
967 memset (lra_hard_reg_usage
, 0, sizeof (lra_hard_reg_usage
));
968 for (i
= 0; i
< max_regno
; i
++)
970 lra_reg_info
[i
].live_ranges
= NULL
;
971 CLEAR_HARD_REG_SET (lra_reg_info
[i
].conflict_hard_regs
);
972 lra_reg_info
[i
].preferred_hard_regno1
= -1;
973 lra_reg_info
[i
].preferred_hard_regno2
= -1;
974 lra_reg_info
[i
].preferred_hard_regno_profit1
= 0;
975 lra_reg_info
[i
].preferred_hard_regno_profit2
= 0;
977 lra_reg_info
[i
].no_stack_p
= false;
979 /* The biggest mode is already set but its value might be to
980 conservative because of recent transformation. Here in this
981 file we recalculate it again as it costs practically
983 if (regno_reg_rtx
[i
] != NULL_RTX
)
984 lra_reg_info
[i
].biggest_mode
= GET_MODE (regno_reg_rtx
[i
]);
986 lra_reg_info
[i
].biggest_mode
= VOIDmode
;
987 #ifdef ENABLE_CHECKING
988 lra_reg_info
[i
].call_p
= false;
990 if (i
>= FIRST_PSEUDO_REGISTER
991 && lra_reg_info
[i
].nrefs
!= 0)
993 if ((hard_regno
= reg_renumber
[i
]) >= 0)
994 lra_hard_reg_usage
[hard_regno
] += lra_reg_info
[i
].freq
;
995 have_referenced_pseudos
= true;
1000 /* Under some circumstances, we can have functions without pseudo
1001 registers. For such functions, lra_live_max_point will be 0,
1002 see e.g. PR55604, and there's nothing more to do for us here. */
1003 if (! have_referenced_pseudos
)
1005 timevar_pop (TV_LRA_CREATE_LIVE_RANGES
);
1009 pseudos_live
= sparseset_alloc (max_regno
);
1010 pseudos_live_through_calls
= sparseset_alloc (max_regno
);
1011 pseudos_live_through_setjumps
= sparseset_alloc (max_regno
);
1012 start_living
= sparseset_alloc (max_regno
);
1013 start_dying
= sparseset_alloc (max_regno
);
1014 dead_set
= sparseset_alloc (max_regno
);
1015 unused_set
= sparseset_alloc (max_regno
);
1017 point_freq_vec
.create (get_max_uid () * 2);
1018 lra_point_freq
= point_freq_vec
.address ();
1019 int *post_order_rev_cfg
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1020 int n_blocks_inverted
= inverted_post_order_compute (post_order_rev_cfg
);
1021 lra_assert (n_blocks_inverted
== n_basic_blocks_for_fn (cfun
));
1022 for (i
= n_blocks_inverted
- 1; i
>= 0; --i
)
1024 bb
= BASIC_BLOCK_FOR_FN (cfun
, post_order_rev_cfg
[i
]);
1025 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
1026 == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1028 process_bb_lives (bb
, curr_point
);
1030 free (post_order_rev_cfg
);
1031 lra_live_max_point
= curr_point
;
1032 gcc_checking_assert (lra_live_max_point
> 0);
1033 if (lra_dump_file
!= NULL
)
1034 print_live_ranges (lra_dump_file
);
1036 sparseset_free (unused_set
);
1037 sparseset_free (dead_set
);
1038 sparseset_free (start_dying
);
1039 sparseset_free (start_living
);
1040 sparseset_free (pseudos_live_through_calls
);
1041 sparseset_free (pseudos_live_through_setjumps
);
1042 sparseset_free (pseudos_live
);
1043 compress_live_ranges ();
1044 timevar_pop (TV_LRA_CREATE_LIVE_RANGES
);
1047 /* Finish all live ranges. */
1049 lra_clear_live_ranges (void)
1053 for (i
= 0; i
< max_reg_num (); i
++)
1054 free_live_range_list (lra_reg_info
[i
].live_ranges
);
1055 point_freq_vec
.release ();
1058 /* Initialize live ranges data once per function. */
1060 lra_live_ranges_init (void)
1062 live_range_pool
= create_alloc_pool ("live ranges",
1063 sizeof (struct lra_live_range
), 100);
1066 /* Finish live ranges data once per function. */
1068 lra_live_ranges_finish (void)
1070 free_alloc_pool (live_range_pool
);