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"
47 #include "dominance.h"
50 #include "basic-block.h"
54 #include "sparseset.h"
57 /* Program points are enumerated by numbers from range
58 0..LRA_LIVE_MAX_POINT-1. There are approximately two times more
59 program points than insns. Program points are places in the
60 program where liveness info can be changed. In most general case
61 (there are more complicated cases too) some program points
62 correspond to places where input operand dies and other ones
63 correspond to places where output operands are born. */
64 int lra_live_max_point
;
66 /* Accumulated execution frequency of all references for each hard
68 int lra_hard_reg_usage
[FIRST_PSEUDO_REGISTER
];
70 /* A global flag whose true value says to build live ranges for all
71 pseudos, otherwise the live ranges only for pseudos got memory is
72 build. True value means also building copies and setting up hard
73 register preferences. The complete info is necessary only for the
74 assignment pass. The complete info is not needed for the
75 coalescing and spill passes. */
76 static bool complete_info_p
;
78 /* Pseudos live at current point in the RTL scan. */
79 static sparseset pseudos_live
;
81 /* Pseudos probably living through calls and setjumps. As setjump is
82 a call too, if a bit in PSEUDOS_LIVE_THROUGH_SETJUMPS is set up
83 then the corresponding bit in PSEUDOS_LIVE_THROUGH_CALLS is set up
84 too. These data are necessary for cases when only one subreg of a
85 multi-reg pseudo is set up after a call. So we decide it is
86 probably live when traversing bb backward. We are sure about
87 living when we see its usage or definition of the pseudo. */
88 static sparseset pseudos_live_through_calls
;
89 static sparseset pseudos_live_through_setjumps
;
91 /* Set of hard regs (except eliminable ones) currently live. */
92 static HARD_REG_SET hard_regs_live
;
94 /* Set of pseudos and hard registers start living/dying in the current
95 insn. These sets are used to update REG_DEAD and REG_UNUSED notes
97 static sparseset start_living
, start_dying
;
99 /* Set of pseudos and hard regs dead and unused in the current
101 static sparseset unused_set
, dead_set
;
103 /* Pool for pseudo live ranges. */
104 static alloc_pool live_range_pool
;
106 /* Free live range LR. */
108 free_live_range (lra_live_range_t lr
)
110 pool_free (live_range_pool
, lr
);
113 /* Free live range list LR. */
115 free_live_range_list (lra_live_range_t lr
)
117 lra_live_range_t next
;
122 free_live_range (lr
);
127 /* Create and return pseudo live range with given attributes. */
128 static lra_live_range_t
129 create_live_range (int regno
, int start
, int finish
, lra_live_range_t next
)
133 p
= (lra_live_range_t
) pool_alloc (live_range_pool
);
141 /* Copy live range R and return the result. */
142 static lra_live_range_t
143 copy_live_range (lra_live_range_t r
)
147 p
= (lra_live_range_t
) pool_alloc (live_range_pool
);
152 /* Copy live range list given by its head R and return the result. */
154 lra_copy_live_range_list (lra_live_range_t r
)
156 lra_live_range_t p
, first
, *chain
;
159 for (chain
= &first
; r
!= NULL
; r
= r
->next
)
161 p
= copy_live_range (r
);
168 /* Merge *non-intersected* ranges R1 and R2 and returns the result.
169 The function maintains the order of ranges and tries to minimize
170 size of the result range list. Ranges R1 and R2 may not be used
173 lra_merge_live_ranges (lra_live_range_t r1
, lra_live_range_t r2
)
175 lra_live_range_t first
, last
, temp
;
181 for (first
= last
= NULL
; r1
!= NULL
&& r2
!= NULL
;)
183 if (r1
->start
< r2
->start
)
189 if (r1
->start
== r2
->finish
+ 1)
191 /* Joint ranges: merge r1 and r2 into r1. */
192 r1
->start
= r2
->start
;
195 pool_free (live_range_pool
, temp
);
199 gcc_assert (r2
->finish
+ 1 < r1
->start
);
200 /* Add r1 to the result. */
220 lra_assert (r2
!= NULL
);
229 /* Return TRUE if live ranges R1 and R2 intersect. */
231 lra_intersected_live_ranges_p (lra_live_range_t r1
, lra_live_range_t r2
)
233 /* Remember the live ranges are always kept ordered. */
234 while (r1
!= NULL
&& r2
!= NULL
)
236 if (r1
->start
> r2
->finish
)
238 else if (r2
->start
> r1
->finish
)
246 /* The function processing birth of hard register REGNO. It updates
247 living hard regs, conflict hard regs for living pseudos, and
250 make_hard_regno_born (int regno
)
254 lra_assert (regno
< FIRST_PSEUDO_REGISTER
);
255 if (TEST_HARD_REG_BIT (lra_no_alloc_regs
, regno
)
256 || TEST_HARD_REG_BIT (hard_regs_live
, regno
))
258 SET_HARD_REG_BIT (hard_regs_live
, regno
);
259 sparseset_set_bit (start_living
, regno
);
260 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, i
)
261 SET_HARD_REG_BIT (lra_reg_info
[i
].conflict_hard_regs
, regno
);
264 /* Process the death of hard register REGNO. This updates
265 hard_regs_live and START_DYING. */
267 make_hard_regno_dead (int regno
)
269 lra_assert (regno
< FIRST_PSEUDO_REGISTER
);
270 if (TEST_HARD_REG_BIT (lra_no_alloc_regs
, regno
)
271 || ! TEST_HARD_REG_BIT (hard_regs_live
, regno
))
273 sparseset_set_bit (start_dying
, regno
);
274 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
277 /* Mark pseudo REGNO as living at program point POINT, update conflicting
278 hard registers of the pseudo and START_LIVING, and start a new live
279 range for the pseudo corresponding to REGNO if it is necessary. */
281 mark_pseudo_live (int regno
, int point
)
285 lra_assert (regno
>= FIRST_PSEUDO_REGISTER
);
286 lra_assert (! sparseset_bit_p (pseudos_live
, regno
));
287 sparseset_set_bit (pseudos_live
, regno
);
288 IOR_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
, hard_regs_live
);
290 if ((complete_info_p
|| lra_get_regno_hard_regno (regno
) < 0)
291 && ((p
= lra_reg_info
[regno
].live_ranges
) == NULL
292 || (p
->finish
!= point
&& p
->finish
+ 1 != point
)))
293 lra_reg_info
[regno
].live_ranges
294 = create_live_range (regno
, point
, -1, p
);
295 sparseset_set_bit (start_living
, regno
);
298 /* Mark pseudo REGNO as not living at program point POINT and update
300 This finishes the current live range for the pseudo corresponding
303 mark_pseudo_dead (int regno
, int point
)
307 lra_assert (regno
>= FIRST_PSEUDO_REGISTER
);
308 lra_assert (sparseset_bit_p (pseudos_live
, regno
));
309 sparseset_clear_bit (pseudos_live
, regno
);
310 sparseset_set_bit (start_dying
, regno
);
311 if (complete_info_p
|| lra_get_regno_hard_regno (regno
) < 0)
313 p
= lra_reg_info
[regno
].live_ranges
;
314 lra_assert (p
!= NULL
);
319 /* Mark register REGNO (pseudo or hard register) in MODE as live
320 at program point POINT.
321 Return TRUE if the liveness tracking sets were modified,
322 or FALSE if nothing changed. */
324 mark_regno_live (int regno
, machine_mode mode
, int point
)
327 bool changed
= false;
329 if (regno
< FIRST_PSEUDO_REGISTER
)
331 for (last
= regno
+ hard_regno_nregs
[regno
][mode
];
334 make_hard_regno_born (regno
);
336 else if (! sparseset_bit_p (pseudos_live
, regno
))
338 mark_pseudo_live (regno
, point
);
345 /* Mark register REGNO in MODE as dead at program point POINT.
346 Return TRUE if the liveness tracking sets were modified,
347 or FALSE if nothing changed. */
349 mark_regno_dead (int regno
, machine_mode mode
, int point
)
352 bool changed
= false;
354 if (regno
< FIRST_PSEUDO_REGISTER
)
356 for (last
= regno
+ hard_regno_nregs
[regno
][mode
];
359 make_hard_regno_dead (regno
);
361 else if (sparseset_bit_p (pseudos_live
, regno
))
363 mark_pseudo_dead (regno
, point
);
369 /* Insn currently scanned. */
370 static rtx_insn
*curr_insn
;
372 static lra_insn_recog_data_t curr_id
;
373 /* The insn static data. */
374 static struct lra_static_insn_data
*curr_static_id
;
376 /* Return true when one of the predecessor edges of BB is marked with
377 EDGE_ABNORMAL_CALL or EDGE_EH. */
379 bb_has_abnormal_call_pred (basic_block bb
)
384 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
386 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
392 /* Vec containing execution frequencies of program points. */
393 static vec
<int> point_freq_vec
;
395 /* The start of the above vector elements. */
398 /* Increment the current program point POINT to the next point which has
399 execution frequency FREQ. */
401 next_program_point (int &point
, int freq
)
403 point_freq_vec
.safe_push (freq
);
404 lra_point_freq
= point_freq_vec
.address ();
408 /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
410 lra_setup_reload_pseudo_preferenced_hard_reg (int regno
,
411 int hard_regno
, int profit
)
413 lra_assert (regno
>= lra_constraint_new_regno_start
);
414 if (lra_reg_info
[regno
].preferred_hard_regno1
== hard_regno
)
415 lra_reg_info
[regno
].preferred_hard_regno_profit1
+= profit
;
416 else if (lra_reg_info
[regno
].preferred_hard_regno2
== hard_regno
)
417 lra_reg_info
[regno
].preferred_hard_regno_profit2
+= profit
;
418 else if (lra_reg_info
[regno
].preferred_hard_regno1
< 0)
420 lra_reg_info
[regno
].preferred_hard_regno1
= hard_regno
;
421 lra_reg_info
[regno
].preferred_hard_regno_profit1
= profit
;
423 else if (lra_reg_info
[regno
].preferred_hard_regno2
< 0
424 || profit
> lra_reg_info
[regno
].preferred_hard_regno_profit2
)
426 lra_reg_info
[regno
].preferred_hard_regno2
= hard_regno
;
427 lra_reg_info
[regno
].preferred_hard_regno_profit2
= profit
;
431 /* Keep the 1st hard regno as more profitable. */
432 if (lra_reg_info
[regno
].preferred_hard_regno1
>= 0
433 && lra_reg_info
[regno
].preferred_hard_regno2
>= 0
434 && (lra_reg_info
[regno
].preferred_hard_regno_profit2
435 > lra_reg_info
[regno
].preferred_hard_regno_profit1
))
439 temp
= lra_reg_info
[regno
].preferred_hard_regno1
;
440 lra_reg_info
[regno
].preferred_hard_regno1
441 = lra_reg_info
[regno
].preferred_hard_regno2
;
442 lra_reg_info
[regno
].preferred_hard_regno2
= temp
;
443 temp
= lra_reg_info
[regno
].preferred_hard_regno_profit1
;
444 lra_reg_info
[regno
].preferred_hard_regno_profit1
445 = lra_reg_info
[regno
].preferred_hard_regno_profit2
;
446 lra_reg_info
[regno
].preferred_hard_regno_profit2
= temp
;
448 if (lra_dump_file
!= NULL
)
450 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno1
) >= 0)
451 fprintf (lra_dump_file
,
452 " Hard reg %d is preferable by r%d with profit %d\n",
454 lra_reg_info
[regno
].preferred_hard_regno_profit1
);
455 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno2
) >= 0)
456 fprintf (lra_dump_file
,
457 " Hard reg %d is preferable by r%d with profit %d\n",
459 lra_reg_info
[regno
].preferred_hard_regno_profit2
);
463 /* Check that REGNO living through calls and setjumps, set up conflict
464 regs, and clear corresponding bits in PSEUDOS_LIVE_THROUGH_CALLS and
465 PSEUDOS_LIVE_THROUGH_SETJUMPS. */
467 check_pseudos_live_through_calls (int regno
)
471 if (! sparseset_bit_p (pseudos_live_through_calls
, regno
))
473 sparseset_clear_bit (pseudos_live_through_calls
, regno
);
474 IOR_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
,
477 for (hr
= 0; hr
< FIRST_PSEUDO_REGISTER
; hr
++)
478 if (HARD_REGNO_CALL_PART_CLOBBERED (hr
, PSEUDO_REGNO_MODE (regno
)))
479 SET_HARD_REG_BIT (lra_reg_info
[regno
].conflict_hard_regs
, hr
);
480 #ifdef ENABLE_CHECKING
481 lra_reg_info
[regno
].call_p
= true;
483 if (! sparseset_bit_p (pseudos_live_through_setjumps
, regno
))
485 sparseset_clear_bit (pseudos_live_through_setjumps
, regno
);
486 /* Don't allocate pseudos that cross setjmps or any call, if this
487 function receives a nonlocal goto. */
488 SET_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
);
491 /* Process insns of the basic block BB to update pseudo live ranges,
492 pseudo hard register conflicts, and insn notes. We do it on
493 backward scan of BB insns. CURR_POINT is the program point where
494 BB ends. The function updates this counter and returns in
495 CURR_POINT the program point where BB starts. */
497 process_bb_lives (basic_block bb
, int &curr_point
)
505 bool need_curr_point_incr
;
507 reg_live_out
= df_get_live_out (bb
);
508 sparseset_clear (pseudos_live
);
509 sparseset_clear (pseudos_live_through_calls
);
510 sparseset_clear (pseudos_live_through_setjumps
);
511 REG_SET_TO_HARD_REG_SET (hard_regs_live
, reg_live_out
);
512 AND_COMPL_HARD_REG_SET (hard_regs_live
, eliminable_regset
);
513 AND_COMPL_HARD_REG_SET (hard_regs_live
, lra_no_alloc_regs
);
514 EXECUTE_IF_SET_IN_BITMAP (reg_live_out
, FIRST_PSEUDO_REGISTER
, j
, bi
)
515 mark_pseudo_live (j
, curr_point
);
517 freq
= REG_FREQ_FROM_BB (bb
);
519 if (lra_dump_file
!= NULL
)
520 fprintf (lra_dump_file
, " BB %d\n", bb
->index
);
522 /* Scan the code of this basic block, noting which pseudos and hard
523 regs are born or die.
525 Note that this loop treats uninitialized values as live until the
526 beginning of the block. For example, if an instruction uses
527 (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
528 FOO will remain live until the beginning of the block. Likewise
529 if FOO is not set at all. This is unnecessarily pessimistic, but
530 it probably doesn't matter much in practice. */
531 FOR_BB_INSNS_REVERSE (bb
, curr_insn
)
534 int dst_regno
, src_regno
;
536 struct lra_insn_reg
*reg
;
538 if (!NONDEBUG_INSN_P (curr_insn
))
541 curr_id
= lra_get_insn_recog_data (curr_insn
);
542 curr_static_id
= curr_id
->insn_static_data
;
543 if (lra_dump_file
!= NULL
)
544 fprintf (lra_dump_file
, " Insn %u: point = %d\n",
545 INSN_UID (curr_insn
), curr_point
);
547 /* Update max ref width and hard reg usage. */
548 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
549 if (reg
->regno
>= FIRST_PSEUDO_REGISTER
550 && (GET_MODE_SIZE (reg
->biggest_mode
)
551 > GET_MODE_SIZE (lra_reg_info
[reg
->regno
].biggest_mode
)))
552 lra_reg_info
[reg
->regno
].biggest_mode
= reg
->biggest_mode
;
553 else if (reg
->regno
< FIRST_PSEUDO_REGISTER
)
554 lra_hard_reg_usage
[reg
->regno
] += freq
;
556 call_p
= CALL_P (curr_insn
);
558 && (set
= single_set (curr_insn
)) != NULL_RTX
559 && REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
))
560 /* Check that source regno does not conflict with
561 destination regno to exclude most impossible
563 && ((((src_regno
= REGNO (SET_SRC (set
))) >= FIRST_PSEUDO_REGISTER
564 && ! sparseset_bit_p (pseudos_live
, src_regno
))
565 || (src_regno
< FIRST_PSEUDO_REGISTER
566 && ! TEST_HARD_REG_BIT (hard_regs_live
, src_regno
)))
567 /* It might be 'inheritance pseudo <- reload pseudo'. */
568 || (src_regno
>= lra_constraint_new_regno_start
569 && ((int) REGNO (SET_DEST (set
))
570 >= lra_constraint_new_regno_start
)
571 /* Remember to skip special cases where src/dest regnos are
572 the same, e.g. insn SET pattern has matching constraints
574 && src_regno
!= (int) REGNO (SET_DEST (set
)))))
576 int hard_regno
= -1, regno
= -1;
578 dst_regno
= REGNO (SET_DEST (set
));
579 if (dst_regno
>= lra_constraint_new_regno_start
580 && src_regno
>= lra_constraint_new_regno_start
)
581 lra_create_copy (dst_regno
, src_regno
, freq
);
582 else if (dst_regno
>= lra_constraint_new_regno_start
)
584 if ((hard_regno
= src_regno
) >= FIRST_PSEUDO_REGISTER
)
585 hard_regno
= reg_renumber
[src_regno
];
588 else if (src_regno
>= lra_constraint_new_regno_start
)
590 if ((hard_regno
= dst_regno
) >= FIRST_PSEUDO_REGISTER
)
591 hard_regno
= reg_renumber
[dst_regno
];
594 if (regno
>= 0 && hard_regno
>= 0)
595 lra_setup_reload_pseudo_preferenced_hard_reg
596 (regno
, hard_regno
, freq
);
599 sparseset_clear (start_living
);
601 /* Try to avoid unnecessary program point increments, this saves
602 a lot of time in remove_some_program_points_and_update_live_ranges.
603 We only need an increment if something becomes live or dies at this
605 need_curr_point_incr
= false;
607 /* Mark each defined value as live. We need to do this for
608 unused values because they still conflict with quantities
609 that are live at the time of the definition. */
610 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
611 if (reg
->type
!= OP_IN
)
613 need_curr_point_incr
|= mark_regno_live (reg
->regno
,
616 check_pseudos_live_through_calls (reg
->regno
);
619 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
620 if (reg
->type
!= OP_IN
)
621 make_hard_regno_born (reg
->regno
);
623 sparseset_copy (unused_set
, start_living
);
625 sparseset_clear (start_dying
);
627 /* See which defined values die here. */
628 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
629 if (reg
->type
== OP_OUT
&& ! reg
->early_clobber
&& ! reg
->subreg_p
)
630 need_curr_point_incr
|= mark_regno_dead (reg
->regno
,
634 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
635 if (reg
->type
== OP_OUT
&& ! reg
->early_clobber
&& ! reg
->subreg_p
)
636 make_hard_regno_dead (reg
->regno
);
640 if (flag_use_caller_save
)
642 HARD_REG_SET this_call_used_reg_set
;
643 get_call_reg_set_usage (curr_insn
, &this_call_used_reg_set
,
646 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, j
)
647 IOR_HARD_REG_SET (lra_reg_info
[j
].actual_call_used_reg_set
,
648 this_call_used_reg_set
);
651 sparseset_ior (pseudos_live_through_calls
,
652 pseudos_live_through_calls
, pseudos_live
);
653 if (cfun
->has_nonlocal_label
654 || find_reg_note (curr_insn
, REG_SETJMP
,
655 NULL_RTX
) != NULL_RTX
)
656 sparseset_ior (pseudos_live_through_setjumps
,
657 pseudos_live_through_setjumps
, pseudos_live
);
660 /* Increment the current program point if we must. */
661 if (need_curr_point_incr
)
662 next_program_point (curr_point
, freq
);
664 sparseset_clear (start_living
);
666 need_curr_point_incr
= false;
668 /* Mark each used value as live. */
669 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
670 if (reg
->type
== OP_IN
)
672 need_curr_point_incr
|= mark_regno_live (reg
->regno
,
675 check_pseudos_live_through_calls (reg
->regno
);
678 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
679 if (reg
->type
== OP_IN
)
680 make_hard_regno_born (reg
->regno
);
682 if (curr_id
->arg_hard_regs
!= NULL
)
683 /* Make argument hard registers live. */
684 for (i
= 0; (regno
= curr_id
->arg_hard_regs
[i
]) >= 0; i
++)
685 make_hard_regno_born (regno
);
687 sparseset_and_compl (dead_set
, start_living
, start_dying
);
689 /* Mark early clobber outputs dead. */
690 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
691 if (reg
->type
== OP_OUT
&& reg
->early_clobber
&& ! reg
->subreg_p
)
692 need_curr_point_incr
|= mark_regno_dead (reg
->regno
,
696 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
697 if (reg
->type
== OP_OUT
&& reg
->early_clobber
&& ! reg
->subreg_p
)
698 make_hard_regno_dead (reg
->regno
);
700 if (need_curr_point_incr
)
701 next_program_point (curr_point
, freq
);
704 for (link_loc
= ®_NOTES (curr_insn
); (link
= *link_loc
) != NULL_RTX
;)
706 if (REG_NOTE_KIND (link
) != REG_DEAD
707 && REG_NOTE_KIND (link
) != REG_UNUSED
)
709 else if (REG_P (XEXP (link
, 0)))
711 regno
= REGNO (XEXP (link
, 0));
712 if ((REG_NOTE_KIND (link
) == REG_DEAD
713 && ! sparseset_bit_p (dead_set
, regno
))
714 || (REG_NOTE_KIND (link
) == REG_UNUSED
715 && ! sparseset_bit_p (unused_set
, regno
)))
717 *link_loc
= XEXP (link
, 1);
720 if (REG_NOTE_KIND (link
) == REG_DEAD
)
721 sparseset_clear_bit (dead_set
, regno
);
722 else if (REG_NOTE_KIND (link
) == REG_UNUSED
)
723 sparseset_clear_bit (unused_set
, regno
);
725 link_loc
= &XEXP (link
, 1);
727 EXECUTE_IF_SET_IN_SPARSESET (dead_set
, j
)
728 add_reg_note (curr_insn
, REG_DEAD
, regno_reg_rtx
[j
]);
729 EXECUTE_IF_SET_IN_SPARSESET (unused_set
, j
)
730 add_reg_note (curr_insn
, REG_UNUSED
, regno_reg_rtx
[j
]);
733 #ifdef EH_RETURN_DATA_REGNO
734 if (bb_has_eh_pred (bb
))
737 unsigned int regno
= EH_RETURN_DATA_REGNO (j
);
739 if (regno
== INVALID_REGNUM
)
741 make_hard_regno_born (regno
);
745 /* Pseudos can't go in stack regs at the start of a basic block that
746 is reached by an abnormal edge. Likewise for call clobbered regs,
747 because caller-save, fixup_abnormal_edges and possibly the table
748 driven EH machinery are not quite ready to handle such pseudos
749 live across such edges. */
750 if (bb_has_abnormal_pred (bb
))
753 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, px
)
754 lra_reg_info
[px
].no_stack_p
= true;
755 for (px
= FIRST_STACK_REG
; px
<= LAST_STACK_REG
; px
++)
756 make_hard_regno_born (px
);
758 /* No need to record conflicts for call clobbered regs if we
759 have nonlocal labels around, as we don't ever try to
760 allocate such regs in this case. */
761 if (!cfun
->has_nonlocal_label
&& bb_has_abnormal_call_pred (bb
))
762 for (px
= 0; px
< FIRST_PSEUDO_REGISTER
; px
++)
763 if (call_used_regs
[px
])
764 make_hard_regno_born (px
);
767 /* See if we'll need an increment at the end of this basic block.
768 An increment is needed if the PSEUDOS_LIVE set is not empty,
769 to make sure the finish points are set up correctly. */
770 need_curr_point_incr
= (sparseset_cardinality (pseudos_live
) > 0);
772 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, i
)
773 mark_pseudo_dead (i
, curr_point
);
775 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb
), FIRST_PSEUDO_REGISTER
, j
, bi
)
777 if (sparseset_cardinality (pseudos_live_through_calls
) == 0)
779 if (sparseset_bit_p (pseudos_live_through_calls
, j
))
780 check_pseudos_live_through_calls (j
);
783 if (need_curr_point_incr
)
784 next_program_point (curr_point
, freq
);
787 /* Compress pseudo live ranges by removing program points where
788 nothing happens. Complexity of many algorithms in LRA is linear
789 function of program points number. To speed up the code we try to
790 minimize the number of the program points here. */
792 remove_some_program_points_and_update_live_ranges (void)
797 lra_live_range_t r
, prev_r
, next_r
;
798 sbitmap born_or_dead
, born
, dead
;
799 sbitmap_iterator sbi
;
800 bool born_p
, dead_p
, prev_born_p
, prev_dead_p
;
802 born
= sbitmap_alloc (lra_live_max_point
);
803 dead
= sbitmap_alloc (lra_live_max_point
);
806 max_regno
= max_reg_num ();
807 for (i
= FIRST_PSEUDO_REGISTER
; i
< (unsigned) max_regno
; i
++)
809 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
811 lra_assert (r
->start
<= r
->finish
);
812 bitmap_set_bit (born
, r
->start
);
813 bitmap_set_bit (dead
, r
->finish
);
816 born_or_dead
= sbitmap_alloc (lra_live_max_point
);
817 bitmap_ior (born_or_dead
, born
, dead
);
818 map
= XCNEWVEC (int, lra_live_max_point
);
820 prev_born_p
= prev_dead_p
= false;
821 EXECUTE_IF_SET_IN_BITMAP (born_or_dead
, 0, i
, sbi
)
823 born_p
= bitmap_bit_p (born
, i
);
824 dead_p
= bitmap_bit_p (dead
, i
);
825 if ((prev_born_p
&& ! prev_dead_p
&& born_p
&& ! dead_p
)
826 || (prev_dead_p
&& ! prev_born_p
&& dead_p
&& ! born_p
))
829 lra_point_freq
[n
] = MAX (lra_point_freq
[n
], lra_point_freq
[i
]);
834 lra_point_freq
[n
] = lra_point_freq
[i
];
836 prev_born_p
= born_p
;
837 prev_dead_p
= dead_p
;
839 sbitmap_free (born_or_dead
);
843 if (lra_dump_file
!= NULL
)
844 fprintf (lra_dump_file
, "Compressing live ranges: from %d to %d - %d%%\n",
845 lra_live_max_point
, n
, 100 * n
/ lra_live_max_point
);
846 if (n
< lra_live_max_point
)
848 lra_live_max_point
= n
;
849 for (i
= FIRST_PSEUDO_REGISTER
; i
< (unsigned) max_regno
; i
++)
851 for (prev_r
= NULL
, r
= lra_reg_info
[i
].live_ranges
;
856 r
->start
= map
[r
->start
];
857 r
->finish
= map
[r
->finish
];
858 if (prev_r
== NULL
|| prev_r
->start
> r
->finish
+ 1)
863 prev_r
->start
= r
->start
;
864 prev_r
->next
= next_r
;
872 /* Print live ranges R to file F. */
874 lra_print_live_range_list (FILE *f
, lra_live_range_t r
)
876 for (; r
!= NULL
; r
= r
->next
)
877 fprintf (f
, " [%d..%d]", r
->start
, r
->finish
);
882 debug (lra_live_range
&ref
)
884 lra_print_live_range_list (stderr
, &ref
);
888 debug (lra_live_range
*ptr
)
893 fprintf (stderr
, "<nil>\n");
896 /* Print live ranges R to stderr. */
898 lra_debug_live_range_list (lra_live_range_t r
)
900 lra_print_live_range_list (stderr
, r
);
903 /* Print live ranges of pseudo REGNO to file F. */
905 print_pseudo_live_ranges (FILE *f
, int regno
)
907 if (lra_reg_info
[regno
].live_ranges
== NULL
)
909 fprintf (f
, " r%d:", regno
);
910 lra_print_live_range_list (f
, lra_reg_info
[regno
].live_ranges
);
913 /* Print live ranges of pseudo REGNO to stderr. */
915 lra_debug_pseudo_live_ranges (int regno
)
917 print_pseudo_live_ranges (stderr
, regno
);
920 /* Print live ranges of all pseudos to file F. */
922 print_live_ranges (FILE *f
)
926 max_regno
= max_reg_num ();
927 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
928 print_pseudo_live_ranges (f
, i
);
931 /* Print live ranges of all pseudos to stderr. */
933 lra_debug_live_ranges (void)
935 print_live_ranges (stderr
);
938 /* Compress pseudo live ranges. */
940 compress_live_ranges (void)
942 remove_some_program_points_and_update_live_ranges ();
943 if (lra_dump_file
!= NULL
)
945 fprintf (lra_dump_file
, "Ranges after the compression:\n");
946 print_live_ranges (lra_dump_file
);
950 /* The number of the current live range pass. */
951 int lra_live_range_iter
;
953 /* The main entry function creates live ranges only for memory pseudos
954 (or for all ones if ALL_P), set up CONFLICT_HARD_REGS for
957 lra_create_live_ranges (bool all_p
)
960 int i
, hard_regno
, max_regno
= max_reg_num ();
962 bool have_referenced_pseudos
= false;
964 timevar_push (TV_LRA_CREATE_LIVE_RANGES
);
966 complete_info_p
= all_p
;
967 if (lra_dump_file
!= NULL
)
968 fprintf (lra_dump_file
,
969 "\n********** Pseudo live ranges #%d: **********\n\n",
970 ++lra_live_range_iter
);
971 memset (lra_hard_reg_usage
, 0, sizeof (lra_hard_reg_usage
));
972 for (i
= 0; i
< max_regno
; i
++)
974 lra_reg_info
[i
].live_ranges
= NULL
;
975 CLEAR_HARD_REG_SET (lra_reg_info
[i
].conflict_hard_regs
);
976 lra_reg_info
[i
].preferred_hard_regno1
= -1;
977 lra_reg_info
[i
].preferred_hard_regno2
= -1;
978 lra_reg_info
[i
].preferred_hard_regno_profit1
= 0;
979 lra_reg_info
[i
].preferred_hard_regno_profit2
= 0;
981 lra_reg_info
[i
].no_stack_p
= false;
983 /* The biggest mode is already set but its value might be to
984 conservative because of recent transformation. Here in this
985 file we recalculate it again as it costs practically
987 if (regno_reg_rtx
[i
] != NULL_RTX
)
988 lra_reg_info
[i
].biggest_mode
= GET_MODE (regno_reg_rtx
[i
]);
990 lra_reg_info
[i
].biggest_mode
= VOIDmode
;
991 #ifdef ENABLE_CHECKING
992 lra_reg_info
[i
].call_p
= false;
994 if (i
>= FIRST_PSEUDO_REGISTER
995 && lra_reg_info
[i
].nrefs
!= 0)
997 if ((hard_regno
= reg_renumber
[i
]) >= 0)
998 lra_hard_reg_usage
[hard_regno
] += lra_reg_info
[i
].freq
;
999 have_referenced_pseudos
= true;
1004 /* Under some circumstances, we can have functions without pseudo
1005 registers. For such functions, lra_live_max_point will be 0,
1006 see e.g. PR55604, and there's nothing more to do for us here. */
1007 if (! have_referenced_pseudos
)
1009 timevar_pop (TV_LRA_CREATE_LIVE_RANGES
);
1013 pseudos_live
= sparseset_alloc (max_regno
);
1014 pseudos_live_through_calls
= sparseset_alloc (max_regno
);
1015 pseudos_live_through_setjumps
= sparseset_alloc (max_regno
);
1016 start_living
= sparseset_alloc (max_regno
);
1017 start_dying
= sparseset_alloc (max_regno
);
1018 dead_set
= sparseset_alloc (max_regno
);
1019 unused_set
= sparseset_alloc (max_regno
);
1021 point_freq_vec
.create (get_max_uid () * 2);
1022 lra_point_freq
= point_freq_vec
.address ();
1023 int *post_order_rev_cfg
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1024 int n_blocks_inverted
= inverted_post_order_compute (post_order_rev_cfg
);
1025 lra_assert (n_blocks_inverted
== n_basic_blocks_for_fn (cfun
));
1026 for (i
= n_blocks_inverted
- 1; i
>= 0; --i
)
1028 bb
= BASIC_BLOCK_FOR_FN (cfun
, post_order_rev_cfg
[i
]);
1029 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
1030 == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1032 process_bb_lives (bb
, curr_point
);
1034 free (post_order_rev_cfg
);
1035 lra_live_max_point
= curr_point
;
1036 gcc_checking_assert (lra_live_max_point
> 0);
1037 if (lra_dump_file
!= NULL
)
1038 print_live_ranges (lra_dump_file
);
1040 sparseset_free (unused_set
);
1041 sparseset_free (dead_set
);
1042 sparseset_free (start_dying
);
1043 sparseset_free (start_living
);
1044 sparseset_free (pseudos_live_through_calls
);
1045 sparseset_free (pseudos_live_through_setjumps
);
1046 sparseset_free (pseudos_live
);
1047 compress_live_ranges ();
1048 timevar_pop (TV_LRA_CREATE_LIVE_RANGES
);
1051 /* Finish all live ranges. */
1053 lra_clear_live_ranges (void)
1057 for (i
= 0; i
< max_reg_num (); i
++)
1058 free_live_range_list (lra_reg_info
[i
].live_ranges
);
1059 point_freq_vec
.release ();
1062 /* Initialize live ranges data once per function. */
1064 lra_live_ranges_init (void)
1066 live_range_pool
= create_alloc_pool ("live ranges",
1067 sizeof (struct lra_live_range
), 100);
1070 /* Finish live ranges data once per function. */
1072 lra_live_ranges_finish (void)
1074 free_alloc_pool (live_range_pool
);