1 /* Build live ranges for pseudos.
2 Copyright (C) 2010-2020 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"
38 #include "insn-config.h"
43 #include "sparseset.h"
46 #include "function-abi.h"
48 /* Program points are enumerated by numbers from range
49 0..LRA_LIVE_MAX_POINT-1. There are approximately two times more
50 program points than insns. Program points are places in the
51 program where liveness info can be changed. In most general case
52 (there are more complicated cases too) some program points
53 correspond to places where input operand dies and other ones
54 correspond to places where output operands are born. */
55 int lra_live_max_point
;
57 /* Accumulated execution frequency of all references for each hard
59 int lra_hard_reg_usage
[FIRST_PSEUDO_REGISTER
];
61 /* A global flag whose true value says to build live ranges for all
62 pseudos, otherwise the live ranges only for pseudos got memory is
63 build. True value means also building copies and setting up hard
64 register preferences. The complete info is necessary only for the
65 assignment pass. The complete info is not needed for the
66 coalescing and spill passes. */
67 static bool complete_info_p
;
69 /* Pseudos live at current point in the RTL scan. */
70 static sparseset pseudos_live
;
72 /* Pseudos probably living through calls and setjumps. As setjump is
73 a call too, if a bit in PSEUDOS_LIVE_THROUGH_SETJUMPS is set up
74 then the corresponding bit in PSEUDOS_LIVE_THROUGH_CALLS is set up
75 too. These data are necessary for cases when only one subreg of a
76 multi-reg pseudo is set up after a call. So we decide it is
77 probably live when traversing bb backward. We are sure about
78 living when we see its usage or definition of the pseudo. */
79 static sparseset pseudos_live_through_calls
;
80 static sparseset pseudos_live_through_setjumps
;
82 /* Set of hard regs (except eliminable ones) currently live. */
83 static HARD_REG_SET hard_regs_live
;
85 /* Set of pseudos and hard registers start living/dying in the current
86 insn. These sets are used to update REG_DEAD and REG_UNUSED notes
88 static sparseset start_living
, start_dying
;
90 /* Set of pseudos and hard regs dead and unused in the current
92 static sparseset unused_set
, dead_set
;
94 /* Bitmap used for holding intermediate bitmap operation results. */
95 static bitmap_head temp_bitmap
;
97 /* Pool for pseudo live ranges. */
98 static object_allocator
<lra_live_range
> lra_live_range_pool ("live ranges");
100 /* Free live range list LR. */
102 free_live_range_list (lra_live_range_t lr
)
104 lra_live_range_t next
;
109 lra_live_range_pool
.remove (lr
);
114 /* Create and return pseudo live range with given attributes. */
115 static lra_live_range_t
116 create_live_range (int regno
, int start
, int finish
, lra_live_range_t next
)
118 lra_live_range_t p
= lra_live_range_pool
.allocate ();
126 /* Copy live range R and return the result. */
127 static lra_live_range_t
128 copy_live_range (lra_live_range_t r
)
130 return new (lra_live_range_pool
) lra_live_range (*r
);
133 /* Copy live range list given by its head R and return the result. */
135 lra_copy_live_range_list (lra_live_range_t r
)
137 lra_live_range_t p
, first
, *chain
;
140 for (chain
= &first
; r
!= NULL
; r
= r
->next
)
142 p
= copy_live_range (r
);
149 /* Merge *non-intersected* ranges R1 and R2 and returns the result.
150 The function maintains the order of ranges and tries to minimize
151 size of the result range list. Ranges R1 and R2 may not be used
154 lra_merge_live_ranges (lra_live_range_t r1
, lra_live_range_t r2
)
156 lra_live_range_t first
, last
;
162 for (first
= last
= NULL
; r1
!= NULL
&& r2
!= NULL
;)
164 if (r1
->start
< r2
->start
)
167 if (r1
->start
== r2
->finish
+ 1)
169 /* Joint ranges: merge r1 and r2 into r1. */
170 r1
->start
= r2
->start
;
171 lra_live_range_t temp
= r2
;
173 lra_live_range_pool
.remove (temp
);
177 gcc_assert (r2
->finish
+ 1 < r1
->start
);
178 /* Add r1 to the result. */
198 lra_assert (r2
!= NULL
);
207 /* Return TRUE if live ranges R1 and R2 intersect. */
209 lra_intersected_live_ranges_p (lra_live_range_t r1
, lra_live_range_t r2
)
211 /* Remember the live ranges are always kept ordered. */
212 while (r1
!= NULL
&& r2
!= NULL
)
214 if (r1
->start
> r2
->finish
)
216 else if (r2
->start
> r1
->finish
)
229 /* Return TRUE if set A contains a pseudo register, otherwise, return FALSE. */
231 sparseset_contains_pseudos_p (sparseset a
)
234 EXECUTE_IF_SET_IN_SPARSESET (a
, regno
)
235 if (!HARD_REGISTER_NUM_P (regno
))
240 /* Mark pseudo REGNO as living or dying at program point POINT, depending on
241 whether TYPE is a definition or a use. If this is the first reference to
242 REGNO that we've encountered, then create a new live range for it. */
245 update_pseudo_point (int regno
, int point
, enum point_type type
)
249 /* Don't compute points for hard registers. */
250 if (HARD_REGISTER_NUM_P (regno
))
253 if (complete_info_p
|| lra_get_regno_hard_regno (regno
) < 0)
255 if (type
== DEF_POINT
)
257 if (sparseset_bit_p (pseudos_live
, regno
))
259 p
= lra_reg_info
[regno
].live_ranges
;
260 lra_assert (p
!= NULL
);
266 if (!sparseset_bit_p (pseudos_live
, regno
)
267 && ((p
= lra_reg_info
[regno
].live_ranges
) == NULL
268 || (p
->finish
!= point
&& p
->finish
+ 1 != point
)))
269 lra_reg_info
[regno
].live_ranges
270 = create_live_range (regno
, point
, -1, p
);
275 /* The corresponding bitmaps of BB currently being processed. */
276 static bitmap bb_killed_pseudos
, bb_gen_pseudos
;
278 /* Record hard register REGNO as now being live. It updates
279 living hard regs and START_LIVING. */
281 make_hard_regno_live (int regno
)
283 lra_assert (HARD_REGISTER_NUM_P (regno
));
284 if (TEST_HARD_REG_BIT (hard_regs_live
, regno
)
285 || TEST_HARD_REG_BIT (eliminable_regset
, regno
))
287 SET_HARD_REG_BIT (hard_regs_live
, regno
);
288 sparseset_set_bit (start_living
, regno
);
289 if (fixed_regs
[regno
] || TEST_HARD_REG_BIT (hard_regs_spilled_into
, regno
))
290 bitmap_set_bit (bb_gen_pseudos
, regno
);
293 /* Process the definition of hard register REGNO. This updates
294 hard_regs_live, START_DYING and conflict hard regs for living
297 make_hard_regno_dead (int regno
)
299 if (TEST_HARD_REG_BIT (eliminable_regset
, regno
))
302 lra_assert (HARD_REGISTER_NUM_P (regno
));
304 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, i
)
305 SET_HARD_REG_BIT (lra_reg_info
[i
].conflict_hard_regs
, regno
);
307 if (! TEST_HARD_REG_BIT (hard_regs_live
, regno
))
309 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
310 sparseset_set_bit (start_dying
, regno
);
311 if (fixed_regs
[regno
] || TEST_HARD_REG_BIT (hard_regs_spilled_into
, regno
))
313 bitmap_clear_bit (bb_gen_pseudos
, regno
);
314 bitmap_set_bit (bb_killed_pseudos
, regno
);
318 /* Mark pseudo REGNO as now being live and update START_LIVING. */
320 mark_pseudo_live (int regno
)
322 lra_assert (!HARD_REGISTER_NUM_P (regno
));
323 if (sparseset_bit_p (pseudos_live
, regno
))
326 sparseset_set_bit (pseudos_live
, regno
);
327 sparseset_set_bit (start_living
, regno
);
330 /* Mark pseudo REGNO as now being dead and update START_DYING. */
332 mark_pseudo_dead (int regno
)
334 lra_assert (!HARD_REGISTER_NUM_P (regno
));
335 lra_reg_info
[regno
].conflict_hard_regs
|= hard_regs_live
;
336 if (!sparseset_bit_p (pseudos_live
, regno
))
339 sparseset_clear_bit (pseudos_live
, regno
);
340 sparseset_set_bit (start_dying
, regno
);
343 /* Mark register REGNO (pseudo or hard register) in MODE as being live
344 and update BB_GEN_PSEUDOS. */
346 mark_regno_live (int regno
, machine_mode mode
)
350 if (HARD_REGISTER_NUM_P (regno
))
352 for (last
= end_hard_regno (mode
, regno
); regno
< last
; regno
++)
353 make_hard_regno_live (regno
);
357 mark_pseudo_live (regno
);
358 bitmap_set_bit (bb_gen_pseudos
, regno
);
363 /* Mark register REGNO (pseudo or hard register) in MODE as being dead
364 and update BB_GEN_PSEUDOS and BB_KILLED_PSEUDOS. */
366 mark_regno_dead (int regno
, machine_mode mode
)
370 if (HARD_REGISTER_NUM_P (regno
))
372 for (last
= end_hard_regno (mode
, regno
); regno
< last
; regno
++)
373 make_hard_regno_dead (regno
);
377 mark_pseudo_dead (regno
);
378 bitmap_clear_bit (bb_gen_pseudos
, regno
);
379 bitmap_set_bit (bb_killed_pseudos
, regno
);
385 /* This page contains code for making global live analysis of pseudos.
386 The code works only when pseudo live info is changed on a BB
387 border. That might be a consequence of some global transformations
388 in LRA, e.g. PIC pseudo reuse or rematerialization. */
390 /* Structure describing local BB data used for pseudo
392 class bb_data_pseudos
395 /* Basic block about which the below data are. */
397 bitmap_head killed_pseudos
; /* pseudos killed in the BB. */
398 bitmap_head gen_pseudos
; /* pseudos generated in the BB. */
401 /* Array for all BB data. Indexed by the corresponding BB index. */
402 typedef class bb_data_pseudos
*bb_data_t
;
404 /* All basic block data are referred through the following array. */
405 static bb_data_t bb_data
;
407 /* Two small functions for access to the bb data. */
408 static inline bb_data_t
409 get_bb_data (basic_block bb
)
411 return &bb_data
[(bb
)->index
];
414 static inline bb_data_t
415 get_bb_data_by_index (int index
)
417 return &bb_data
[index
];
420 /* Bitmap with all hard regs. */
421 static bitmap_head all_hard_regs_bitmap
;
423 /* The transfer function used by the DF equation solver to propagate
424 live info through block with BB_INDEX according to the following
427 bb.livein = (bb.liveout - bb.kill) OR bb.gen
430 live_trans_fun (int bb_index
)
432 basic_block bb
= get_bb_data_by_index (bb_index
)->bb
;
433 bitmap bb_liveout
= df_get_live_out (bb
);
434 bitmap bb_livein
= df_get_live_in (bb
);
435 bb_data_t bb_info
= get_bb_data (bb
);
437 bitmap_and_compl (&temp_bitmap
, bb_liveout
, &all_hard_regs_bitmap
);
438 return bitmap_ior_and_compl (bb_livein
, &bb_info
->gen_pseudos
,
439 &temp_bitmap
, &bb_info
->killed_pseudos
);
442 /* The confluence function used by the DF equation solver to set up
443 live info for a block BB without predecessor. */
445 live_con_fun_0 (basic_block bb
)
447 bitmap_and_into (df_get_live_out (bb
), &all_hard_regs_bitmap
);
450 /* The confluence function used by the DF equation solver to propagate
451 live info from successor to predecessor on edge E according to the
454 bb.liveout = 0 for entry block | OR (livein of successors)
457 live_con_fun_n (edge e
)
459 basic_block bb
= e
->src
;
460 basic_block dest
= e
->dest
;
461 bitmap bb_liveout
= df_get_live_out (bb
);
462 bitmap dest_livein
= df_get_live_in (dest
);
464 return bitmap_ior_and_compl_into (bb_liveout
,
465 dest_livein
, &all_hard_regs_bitmap
);
468 /* Indexes of all function blocks. */
469 static bitmap_head all_blocks
;
471 /* Allocate and initialize data needed for global pseudo live
474 initiate_live_solver (void)
476 bitmap_initialize (&all_hard_regs_bitmap
, ®_obstack
);
477 bitmap_set_range (&all_hard_regs_bitmap
, 0, FIRST_PSEUDO_REGISTER
);
478 bb_data
= XNEWVEC (class bb_data_pseudos
, last_basic_block_for_fn (cfun
));
479 bitmap_initialize (&all_blocks
, ®_obstack
);
482 FOR_ALL_BB_FN (bb
, cfun
)
484 bb_data_t bb_info
= get_bb_data (bb
);
486 bitmap_initialize (&bb_info
->killed_pseudos
, ®_obstack
);
487 bitmap_initialize (&bb_info
->gen_pseudos
, ®_obstack
);
488 bitmap_set_bit (&all_blocks
, bb
->index
);
492 /* Free all data needed for global pseudo live analysis. */
494 finish_live_solver (void)
498 bitmap_clear (&all_blocks
);
499 FOR_ALL_BB_FN (bb
, cfun
)
501 bb_data_t bb_info
= get_bb_data (bb
);
502 bitmap_clear (&bb_info
->killed_pseudos
);
503 bitmap_clear (&bb_info
->gen_pseudos
);
506 bitmap_clear (&all_hard_regs_bitmap
);
511 /* Insn currently scanned. */
512 static rtx_insn
*curr_insn
;
514 static lra_insn_recog_data_t curr_id
;
515 /* The insn static data. */
516 static struct lra_static_insn_data
*curr_static_id
;
518 /* Vec containing execution frequencies of program points. */
519 static vec
<int> point_freq_vec
;
521 /* The start of the above vector elements. */
524 /* Increment the current program point POINT to the next point which has
525 execution frequency FREQ. */
527 next_program_point (int &point
, int freq
)
529 point_freq_vec
.safe_push (freq
);
530 lra_point_freq
= point_freq_vec
.address ();
534 /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
536 lra_setup_reload_pseudo_preferenced_hard_reg (int regno
,
537 int hard_regno
, int profit
)
539 lra_assert (regno
>= lra_constraint_new_regno_start
);
540 if (lra_reg_info
[regno
].preferred_hard_regno1
== hard_regno
)
541 lra_reg_info
[regno
].preferred_hard_regno_profit1
+= profit
;
542 else if (lra_reg_info
[regno
].preferred_hard_regno2
== hard_regno
)
543 lra_reg_info
[regno
].preferred_hard_regno_profit2
+= profit
;
544 else if (lra_reg_info
[regno
].preferred_hard_regno1
< 0)
546 lra_reg_info
[regno
].preferred_hard_regno1
= hard_regno
;
547 lra_reg_info
[regno
].preferred_hard_regno_profit1
= profit
;
549 else if (lra_reg_info
[regno
].preferred_hard_regno2
< 0
550 || profit
> lra_reg_info
[regno
].preferred_hard_regno_profit2
)
552 lra_reg_info
[regno
].preferred_hard_regno2
= hard_regno
;
553 lra_reg_info
[regno
].preferred_hard_regno_profit2
= profit
;
557 /* Keep the 1st hard regno as more profitable. */
558 if (lra_reg_info
[regno
].preferred_hard_regno1
>= 0
559 && lra_reg_info
[regno
].preferred_hard_regno2
>= 0
560 && (lra_reg_info
[regno
].preferred_hard_regno_profit2
561 > lra_reg_info
[regno
].preferred_hard_regno_profit1
))
563 std::swap (lra_reg_info
[regno
].preferred_hard_regno1
,
564 lra_reg_info
[regno
].preferred_hard_regno2
);
565 std::swap (lra_reg_info
[regno
].preferred_hard_regno_profit1
,
566 lra_reg_info
[regno
].preferred_hard_regno_profit2
);
568 if (lra_dump_file
!= NULL
)
570 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno1
) >= 0)
571 fprintf (lra_dump_file
,
572 " Hard reg %d is preferable by r%d with profit %d\n",
574 lra_reg_info
[regno
].preferred_hard_regno_profit1
);
575 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno2
) >= 0)
576 fprintf (lra_dump_file
,
577 " Hard reg %d is preferable by r%d with profit %d\n",
579 lra_reg_info
[regno
].preferred_hard_regno_profit2
);
583 /* Check whether REGNO lives through calls and setjmps and clear
584 the corresponding bits in PSEUDOS_LIVE_THROUGH_CALLS and
585 PSEUDOS_LIVE_THROUGH_SETJUMPS. All calls in the region described
586 by PSEUDOS_LIVE_THROUGH_CALLS have the given ABI. */
589 check_pseudos_live_through_calls (int regno
, const function_abi
&abi
)
591 if (! sparseset_bit_p (pseudos_live_through_calls
, regno
))
594 machine_mode mode
= PSEUDO_REGNO_MODE (regno
);
596 sparseset_clear_bit (pseudos_live_through_calls
, regno
);
597 lra_reg_info
[regno
].conflict_hard_regs
|= abi
.mode_clobbers (mode
);
598 if (! sparseset_bit_p (pseudos_live_through_setjumps
, regno
))
600 sparseset_clear_bit (pseudos_live_through_setjumps
, regno
);
601 /* Don't allocate pseudos that cross setjmps or any call, if this
602 function receives a nonlocal goto. */
603 SET_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
);
606 /* Return true if insn REG is an early clobber operand in alternative
607 NALT. Negative NALT means that we don't know the current insn
608 alternative. So assume the worst. */
610 reg_early_clobber_p (const struct lra_insn_reg
*reg
, int n_alt
)
612 return (n_alt
== LRA_UNKNOWN_ALT
613 ? reg
->early_clobber_alts
!= 0
614 : (n_alt
!= LRA_NON_CLOBBERED_ALT
615 && TEST_BIT (reg
->early_clobber_alts
, n_alt
)));
618 /* Process insns of the basic block BB to update pseudo live ranges,
619 pseudo hard register conflicts, and insn notes. We do it on
620 backward scan of BB insns. CURR_POINT is the program point where
621 BB ends. The function updates this counter and returns in
622 CURR_POINT the program point where BB starts. The function also
623 does local live info updates and can delete the dead insns if
624 DEAD_INSN_P. It returns true if pseudo live info was
625 changed at the BB start. */
627 process_bb_lives (basic_block bb
, int &curr_point
, bool dead_insn_p
)
636 bool need_curr_point_incr
;
637 /* Only has a meaningful value once we've seen a call. */
638 function_abi last_call_abi
= default_function_abi
;
640 reg_live_out
= df_get_live_out (bb
);
641 sparseset_clear (pseudos_live
);
642 sparseset_clear (pseudos_live_through_calls
);
643 sparseset_clear (pseudos_live_through_setjumps
);
644 REG_SET_TO_HARD_REG_SET (hard_regs_live
, reg_live_out
);
645 hard_regs_live
&= ~eliminable_regset
;
646 EXECUTE_IF_SET_IN_BITMAP (reg_live_out
, FIRST_PSEUDO_REGISTER
, j
, bi
)
648 update_pseudo_point (j
, curr_point
, USE_POINT
);
649 mark_pseudo_live (j
);
652 bb_gen_pseudos
= &get_bb_data (bb
)->gen_pseudos
;
653 bb_killed_pseudos
= &get_bb_data (bb
)->killed_pseudos
;
654 bitmap_clear (bb_gen_pseudos
);
655 bitmap_clear (bb_killed_pseudos
);
656 freq
= REG_FREQ_FROM_BB (bb
);
658 if (lra_dump_file
!= NULL
)
659 fprintf (lra_dump_file
, " BB %d\n", bb
->index
);
661 /* Scan the code of this basic block, noting which pseudos and hard
662 regs are born or die.
664 Note that this loop treats uninitialized values as live until the
665 beginning of the block. For example, if an instruction uses
666 (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
667 FOO will remain live until the beginning of the block. Likewise
668 if FOO is not set at all. This is unnecessarily pessimistic, but
669 it probably doesn't matter much in practice. */
670 FOR_BB_INSNS_REVERSE_SAFE (bb
, curr_insn
, next
)
673 int n_alt
, dst_regno
, src_regno
;
675 struct lra_insn_reg
*reg
;
677 if (!NONDEBUG_INSN_P (curr_insn
))
680 curr_id
= lra_get_insn_recog_data (curr_insn
);
681 curr_static_id
= curr_id
->insn_static_data
;
682 n_alt
= curr_id
->used_insn_alternative
;
683 if (lra_dump_file
!= NULL
)
684 fprintf (lra_dump_file
, " Insn %u: point = %d, n_alt = %d\n",
685 INSN_UID (curr_insn
), curr_point
, n_alt
);
687 set
= single_set (curr_insn
);
689 if (dead_insn_p
&& set
!= NULL_RTX
690 && REG_P (SET_DEST (set
)) && !HARD_REGISTER_P (SET_DEST (set
))
691 && find_reg_note (curr_insn
, REG_EH_REGION
, NULL_RTX
) == NULL_RTX
692 && ! may_trap_p (PATTERN (curr_insn
))
693 /* Don't do premature remove of pic offset pseudo as we can
694 start to use it after some reload generation. */
695 && (pic_offset_table_rtx
== NULL_RTX
696 || pic_offset_table_rtx
!= SET_DEST (set
)))
698 bool remove_p
= true;
700 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
701 if (reg
->type
!= OP_IN
&& sparseset_bit_p (pseudos_live
, reg
->regno
))
706 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
707 if (reg
->type
!= OP_IN
)
713 if (remove_p
&& ! volatile_refs_p (PATTERN (curr_insn
)))
715 dst_regno
= REGNO (SET_DEST (set
));
716 if (lra_dump_file
!= NULL
)
717 fprintf (lra_dump_file
, " Deleting dead insn %u\n",
718 INSN_UID (curr_insn
));
719 lra_set_insn_deleted (curr_insn
);
720 if (lra_reg_info
[dst_regno
].nrefs
== 0)
722 /* There might be some debug insns with the pseudo. */
726 bitmap_copy (&temp_bitmap
, &lra_reg_info
[dst_regno
].insn_bitmap
);
727 EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap
, 0, uid
, bi
)
729 insn
= lra_insn_recog_data
[uid
]->insn
;
730 lra_substitute_pseudo_within_insn (insn
, dst_regno
,
731 SET_SRC (set
), true);
732 lra_update_insn_regno_info (insn
);
739 /* Update max ref width and hard reg usage. */
740 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
742 int i
, regno
= reg
->regno
;
744 if (partial_subreg_p (lra_reg_info
[regno
].biggest_mode
,
746 lra_reg_info
[regno
].biggest_mode
= reg
->biggest_mode
;
747 if (HARD_REGISTER_NUM_P (regno
))
749 lra_hard_reg_usage
[regno
] += freq
;
750 /* A hard register explicitly can be used in small mode,
751 but implicitly it can be used in natural mode as a
752 part of multi-register group. Process this case
754 for (i
= 1; i
< hard_regno_nregs (regno
, reg
->biggest_mode
); i
++)
755 if (partial_subreg_p (lra_reg_info
[regno
+ i
].biggest_mode
,
756 GET_MODE (regno_reg_rtx
[regno
+ i
])))
757 lra_reg_info
[regno
+ i
].biggest_mode
758 = GET_MODE (regno_reg_rtx
[regno
+ i
]);
762 call_p
= CALL_P (curr_insn
);
764 /* If we have a simple register copy and the source reg is live after
765 this instruction, then remove the source reg from the live set so
766 that it will not conflict with the destination reg. */
767 rtx ignore_reg
= non_conflicting_reg_copy_p (curr_insn
);
768 if (ignore_reg
!= NULL_RTX
)
770 int ignore_regno
= REGNO (ignore_reg
);
771 if (HARD_REGISTER_NUM_P (ignore_regno
)
772 && TEST_HARD_REG_BIT (hard_regs_live
, ignore_regno
))
773 CLEAR_HARD_REG_BIT (hard_regs_live
, ignore_regno
);
774 else if (!HARD_REGISTER_NUM_P (ignore_regno
)
775 && sparseset_bit_p (pseudos_live
, ignore_regno
))
776 sparseset_clear_bit (pseudos_live
, ignore_regno
);
778 /* We don't need any special handling of the source reg if
779 it is dead after this instruction. */
780 ignore_reg
= NULL_RTX
;
783 src_regno
= (set
!= NULL_RTX
&& REG_P (SET_SRC (set
))
784 ? REGNO (SET_SRC (set
)) : -1);
785 dst_regno
= (set
!= NULL_RTX
&& REG_P (SET_DEST (set
))
786 ? REGNO (SET_DEST (set
)) : -1);
788 && src_regno
>= 0 && dst_regno
>= 0
789 /* Check that source regno does not conflict with
790 destination regno to exclude most impossible
792 && (((!HARD_REGISTER_NUM_P (src_regno
)
793 && (! sparseset_bit_p (pseudos_live
, src_regno
)
794 || (!HARD_REGISTER_NUM_P (dst_regno
)
795 && lra_reg_val_equal_p (src_regno
,
796 lra_reg_info
[dst_regno
].val
,
797 lra_reg_info
[dst_regno
].offset
))))
798 || (HARD_REGISTER_NUM_P (src_regno
)
799 && ! TEST_HARD_REG_BIT (hard_regs_live
, src_regno
)))
800 /* It might be 'inheritance pseudo <- reload pseudo'. */
801 || (src_regno
>= lra_constraint_new_regno_start
802 && dst_regno
>= lra_constraint_new_regno_start
803 /* Remember to skip special cases where src/dest regnos are
804 the same, e.g. insn SET pattern has matching constraints
806 && src_regno
!= dst_regno
)))
808 int hard_regno
= -1, regno
= -1;
810 if (dst_regno
>= lra_constraint_new_regno_start
811 && src_regno
>= lra_constraint_new_regno_start
)
813 /* It might be still an original (non-reload) insn with
814 one unused output and a constraint requiring to use
815 the same reg for input/output operands. In this case
816 dst_regno and src_regno have the same value, we don't
817 need a misleading copy for this case. */
818 if (dst_regno
!= src_regno
)
819 lra_create_copy (dst_regno
, src_regno
, freq
);
821 else if (dst_regno
>= lra_constraint_new_regno_start
)
823 if (!HARD_REGISTER_NUM_P (hard_regno
= src_regno
))
824 hard_regno
= reg_renumber
[src_regno
];
827 else if (src_regno
>= lra_constraint_new_regno_start
)
829 if (!HARD_REGISTER_NUM_P (hard_regno
= dst_regno
))
830 hard_regno
= reg_renumber
[dst_regno
];
833 if (regno
>= 0 && hard_regno
>= 0)
834 lra_setup_reload_pseudo_preferenced_hard_reg
835 (regno
, hard_regno
, freq
);
838 sparseset_clear (start_living
);
840 /* Mark each defined value as live. We need to do this for
841 unused values because they still conflict with quantities
842 that are live at the time of the definition. */
843 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
844 if (reg
->type
!= OP_IN
)
846 update_pseudo_point (reg
->regno
, curr_point
, USE_POINT
);
847 mark_regno_live (reg
->regno
, reg
->biggest_mode
);
848 /* ??? Should be a no-op for unused registers. */
849 check_pseudos_live_through_calls (reg
->regno
, last_call_abi
);
852 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
853 if (reg
->type
!= OP_IN
)
854 make_hard_regno_live (reg
->regno
);
856 if (curr_id
->arg_hard_regs
!= NULL
)
857 for (i
= 0; (regno
= curr_id
->arg_hard_regs
[i
]) >= 0; i
++)
858 if (!HARD_REGISTER_NUM_P (regno
))
859 /* It is a clobber. */
860 make_hard_regno_live (regno
- FIRST_PSEUDO_REGISTER
);
862 sparseset_copy (unused_set
, start_living
);
864 sparseset_clear (start_dying
);
866 /* See which defined values die here. */
867 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
868 if (reg
->type
!= OP_IN
869 && ! reg_early_clobber_p (reg
, n_alt
) && ! reg
->subreg_p
)
871 if (reg
->type
== OP_OUT
)
872 update_pseudo_point (reg
->regno
, curr_point
, DEF_POINT
);
873 mark_regno_dead (reg
->regno
, reg
->biggest_mode
);
876 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
877 if (reg
->type
!= OP_IN
878 && ! reg_early_clobber_p (reg
, n_alt
) && ! reg
->subreg_p
)
879 make_hard_regno_dead (reg
->regno
);
881 if (curr_id
->arg_hard_regs
!= NULL
)
882 for (i
= 0; (regno
= curr_id
->arg_hard_regs
[i
]) >= 0; i
++)
883 if (!HARD_REGISTER_NUM_P (regno
))
884 /* It is a clobber. */
885 make_hard_regno_dead (regno
- FIRST_PSEUDO_REGISTER
);
889 function_abi call_abi
= insn_callee_abi (curr_insn
);
891 if (last_call_abi
!= call_abi
)
892 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, j
)
893 check_pseudos_live_through_calls (j
, last_call_abi
);
895 last_call_abi
= call_abi
;
897 sparseset_ior (pseudos_live_through_calls
,
898 pseudos_live_through_calls
, pseudos_live
);
899 if (cfun
->has_nonlocal_label
900 || (!targetm
.setjmp_preserves_nonvolatile_regs_p ()
901 && (find_reg_note (curr_insn
, REG_SETJMP
, NULL_RTX
)
903 sparseset_ior (pseudos_live_through_setjumps
,
904 pseudos_live_through_setjumps
, pseudos_live
);
907 /* Increment the current program point if we must. */
908 if (sparseset_contains_pseudos_p (unused_set
)
909 || sparseset_contains_pseudos_p (start_dying
))
910 next_program_point (curr_point
, freq
);
912 /* If we removed the source reg from a simple register copy from the
913 live set above, then add it back now so we don't accidentally add
914 it to the start_living set below. */
915 if (ignore_reg
!= NULL_RTX
)
917 int ignore_regno
= REGNO (ignore_reg
);
918 if (HARD_REGISTER_NUM_P (ignore_regno
))
919 SET_HARD_REG_BIT (hard_regs_live
, ignore_regno
);
921 sparseset_set_bit (pseudos_live
, ignore_regno
);
924 sparseset_clear (start_living
);
926 /* Mark each used value as live. */
927 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
928 if (reg
->type
!= OP_OUT
)
930 if (reg
->type
== OP_IN
)
931 update_pseudo_point (reg
->regno
, curr_point
, USE_POINT
);
932 mark_regno_live (reg
->regno
, reg
->biggest_mode
);
933 check_pseudos_live_through_calls (reg
->regno
, last_call_abi
);
936 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
937 if (reg
->type
!= OP_OUT
)
938 make_hard_regno_live (reg
->regno
);
940 if (curr_id
->arg_hard_regs
!= NULL
)
941 /* Make argument hard registers live. */
942 for (i
= 0; (regno
= curr_id
->arg_hard_regs
[i
]) >= 0; i
++)
943 if (HARD_REGISTER_NUM_P (regno
))
944 make_hard_regno_live (regno
);
946 sparseset_and_compl (dead_set
, start_living
, start_dying
);
948 sparseset_clear (start_dying
);
950 /* Mark early clobber outputs dead. */
951 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
952 if (reg
->type
!= OP_IN
953 && reg_early_clobber_p (reg
, n_alt
) && ! reg
->subreg_p
)
955 if (reg
->type
== OP_OUT
)
956 update_pseudo_point (reg
->regno
, curr_point
, DEF_POINT
);
957 mark_regno_dead (reg
->regno
, reg
->biggest_mode
);
959 /* We're done processing inputs, so make sure early clobber
960 operands that are both inputs and outputs are still live. */
961 if (reg
->type
== OP_INOUT
)
962 mark_regno_live (reg
->regno
, reg
->biggest_mode
);
965 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
966 if (reg
->type
!= OP_IN
967 && reg_early_clobber_p (reg
, n_alt
) && ! reg
->subreg_p
)
969 struct lra_insn_reg
*reg2
;
971 /* We can have early clobbered non-operand hard reg and
972 the same hard reg as an insn input. Don't make hard
973 reg dead before the insns. */
974 for (reg2
= curr_id
->regs
; reg2
!= NULL
; reg2
= reg2
->next
)
975 if (reg2
->type
!= OP_OUT
&& reg2
->regno
== reg
->regno
)
978 make_hard_regno_dead (reg
->regno
);
981 /* Increment the current program point if we must. */
982 if (sparseset_contains_pseudos_p (dead_set
)
983 || sparseset_contains_pseudos_p (start_dying
))
984 next_program_point (curr_point
, freq
);
987 for (link_loc
= ®_NOTES (curr_insn
); (link
= *link_loc
) != NULL_RTX
;)
989 if (REG_NOTE_KIND (link
) != REG_DEAD
990 && REG_NOTE_KIND (link
) != REG_UNUSED
)
992 else if (REG_P (XEXP (link
, 0)))
994 regno
= REGNO (XEXP (link
, 0));
995 if ((REG_NOTE_KIND (link
) == REG_DEAD
996 && ! sparseset_bit_p (dead_set
, regno
))
997 || (REG_NOTE_KIND (link
) == REG_UNUSED
998 && ! sparseset_bit_p (unused_set
, regno
)))
1000 *link_loc
= XEXP (link
, 1);
1003 if (REG_NOTE_KIND (link
) == REG_DEAD
)
1004 sparseset_clear_bit (dead_set
, regno
);
1005 else if (REG_NOTE_KIND (link
) == REG_UNUSED
)
1006 sparseset_clear_bit (unused_set
, regno
);
1008 link_loc
= &XEXP (link
, 1);
1010 EXECUTE_IF_SET_IN_SPARSESET (dead_set
, j
)
1011 add_reg_note (curr_insn
, REG_DEAD
, regno_reg_rtx
[j
]);
1012 EXECUTE_IF_SET_IN_SPARSESET (unused_set
, j
)
1013 add_reg_note (curr_insn
, REG_UNUSED
, regno_reg_rtx
[j
]);
1016 if (bb_has_eh_pred (bb
))
1019 unsigned int regno
= EH_RETURN_DATA_REGNO (j
);
1021 if (regno
== INVALID_REGNUM
)
1023 make_hard_regno_live (regno
);
1026 /* Pseudos can't go in stack regs at the start of a basic block that
1027 is reached by an abnormal edge. Likewise for registers that are at
1028 least partly call clobbered, because caller-save, fixup_abnormal_edges
1029 and possibly the table driven EH machinery are not quite ready to
1030 handle such pseudos live across such edges. */
1031 if (bb_has_abnormal_pred (bb
))
1033 HARD_REG_SET clobbers
;
1035 CLEAR_HARD_REG_SET (clobbers
);
1037 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, px
)
1038 lra_reg_info
[px
].no_stack_p
= true;
1039 for (px
= FIRST_STACK_REG
; px
<= LAST_STACK_REG
; px
++)
1040 SET_HARD_REG_BIT (clobbers
, px
);
1042 /* No need to record conflicts for call clobbered regs if we
1043 have nonlocal labels around, as we don't ever try to
1044 allocate such regs in this case. */
1045 if (!cfun
->has_nonlocal_label
1046 && has_abnormal_call_or_eh_pred_edge_p (bb
))
1047 for (px
= 0; HARD_REGISTER_NUM_P (px
); px
++)
1048 if (eh_edge_abi
.clobbers_at_least_part_of_reg_p (px
)
1049 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
1050 /* We should create a conflict of PIC pseudo with PIC
1051 hard reg as PIC hard reg can have a wrong value after
1052 jump described by the abnormal edge. In this case we
1053 cannot allocate PIC hard reg to PIC pseudo as PIC
1054 pseudo will also have a wrong value. */
1055 || (px
== REAL_PIC_OFFSET_TABLE_REGNUM
1056 && pic_offset_table_rtx
!= NULL_RTX
1057 && !HARD_REGISTER_P (pic_offset_table_rtx
))
1060 SET_HARD_REG_BIT (clobbers
, px
);
1062 clobbers
&= ~hard_regs_live
;
1063 for (px
= 0; HARD_REGISTER_NUM_P (px
); px
++)
1064 if (TEST_HARD_REG_BIT (clobbers
, px
))
1066 make_hard_regno_live (px
);
1067 make_hard_regno_dead (px
);
1071 bool live_change_p
= false;
1072 /* Check if bb border live info was changed. */
1073 unsigned int live_pseudos_num
= 0;
1074 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb
),
1075 FIRST_PSEUDO_REGISTER
, j
, bi
)
1078 if (! sparseset_bit_p (pseudos_live
, j
))
1080 live_change_p
= true;
1081 if (lra_dump_file
!= NULL
)
1082 fprintf (lra_dump_file
,
1083 " r%d is removed as live at bb%d start\n", j
, bb
->index
);
1088 && sparseset_cardinality (pseudos_live
) != live_pseudos_num
)
1090 live_change_p
= true;
1091 if (lra_dump_file
!= NULL
)
1092 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, j
)
1093 if (! bitmap_bit_p (df_get_live_in (bb
), j
))
1094 fprintf (lra_dump_file
,
1095 " r%d is added to live at bb%d start\n", j
, bb
->index
);
1097 /* See if we'll need an increment at the end of this basic block.
1098 An increment is needed if the PSEUDOS_LIVE set is not empty,
1099 to make sure the finish points are set up correctly. */
1100 need_curr_point_incr
= (sparseset_cardinality (pseudos_live
) > 0);
1102 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, i
)
1104 update_pseudo_point (i
, curr_point
, DEF_POINT
);
1105 mark_pseudo_dead (i
);
1108 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb
), FIRST_PSEUDO_REGISTER
, j
, bi
)
1110 if (sparseset_cardinality (pseudos_live_through_calls
) == 0)
1112 if (sparseset_bit_p (pseudos_live_through_calls
, j
))
1113 check_pseudos_live_through_calls (j
, last_call_abi
);
1116 for (i
= 0; HARD_REGISTER_NUM_P (i
); ++i
)
1118 if (!TEST_HARD_REG_BIT (hard_regs_live
, i
))
1121 if (!TEST_HARD_REG_BIT (hard_regs_spilled_into
, i
))
1124 if (bitmap_bit_p (df_get_live_in (bb
), i
))
1127 live_change_p
= true;
1129 fprintf (lra_dump_file
,
1130 " hard reg r%d is added to live at bb%d start\n", i
,
1132 bitmap_set_bit (df_get_live_in (bb
), i
);
1135 if (need_curr_point_incr
)
1136 next_program_point (curr_point
, freq
);
1138 return live_change_p
;
1141 /* Compress pseudo live ranges by removing program points where
1142 nothing happens. Complexity of many algorithms in LRA is linear
1143 function of program points number. To speed up the code we try to
1144 minimize the number of the program points here. */
1146 remove_some_program_points_and_update_live_ranges (void)
1151 lra_live_range_t r
, prev_r
, next_r
;
1152 sbitmap_iterator sbi
;
1153 bool born_p
, dead_p
, prev_born_p
, prev_dead_p
;
1155 auto_sbitmap
born (lra_live_max_point
);
1156 auto_sbitmap
dead (lra_live_max_point
);
1157 bitmap_clear (born
);
1158 bitmap_clear (dead
);
1159 max_regno
= max_reg_num ();
1160 for (i
= FIRST_PSEUDO_REGISTER
; i
< (unsigned) max_regno
; i
++)
1162 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
1164 lra_assert (r
->start
<= r
->finish
);
1165 bitmap_set_bit (born
, r
->start
);
1166 bitmap_set_bit (dead
, r
->finish
);
1169 auto_sbitmap
born_or_dead (lra_live_max_point
);
1170 bitmap_ior (born_or_dead
, born
, dead
);
1171 map
= XCNEWVEC (int, lra_live_max_point
);
1173 prev_born_p
= prev_dead_p
= false;
1174 EXECUTE_IF_SET_IN_BITMAP (born_or_dead
, 0, i
, sbi
)
1176 born_p
= bitmap_bit_p (born
, i
);
1177 dead_p
= bitmap_bit_p (dead
, i
);
1178 if ((prev_born_p
&& ! prev_dead_p
&& born_p
&& ! dead_p
)
1179 || (prev_dead_p
&& ! prev_born_p
&& dead_p
&& ! born_p
))
1182 lra_point_freq
[n
] = MAX (lra_point_freq
[n
], lra_point_freq
[i
]);
1187 lra_point_freq
[n
] = lra_point_freq
[i
];
1189 prev_born_p
= born_p
;
1190 prev_dead_p
= dead_p
;
1193 if (lra_dump_file
!= NULL
)
1194 fprintf (lra_dump_file
, "Compressing live ranges: from %d to %d - %d%%\n",
1195 lra_live_max_point
, n
,
1196 lra_live_max_point
? 100 * n
/ lra_live_max_point
: 100);
1197 if (n
< lra_live_max_point
)
1199 lra_live_max_point
= n
;
1200 for (i
= FIRST_PSEUDO_REGISTER
; i
< (unsigned) max_regno
; i
++)
1202 for (prev_r
= NULL
, r
= lra_reg_info
[i
].live_ranges
;
1207 r
->start
= map
[r
->start
];
1208 r
->finish
= map
[r
->finish
];
1209 if (prev_r
== NULL
|| prev_r
->start
> r
->finish
+ 1)
1214 prev_r
->start
= r
->start
;
1215 prev_r
->next
= next_r
;
1216 lra_live_range_pool
.remove (r
);
1223 /* Print live ranges R to file F. */
1225 lra_print_live_range_list (FILE *f
, lra_live_range_t r
)
1227 for (; r
!= NULL
; r
= r
->next
)
1228 fprintf (f
, " [%d..%d]", r
->start
, r
->finish
);
1233 debug (lra_live_range
&ref
)
1235 lra_print_live_range_list (stderr
, &ref
);
1239 debug (lra_live_range
*ptr
)
1244 fprintf (stderr
, "<nil>\n");
1247 /* Print live ranges R to stderr. */
1249 lra_debug_live_range_list (lra_live_range_t r
)
1251 lra_print_live_range_list (stderr
, r
);
1254 /* Print live ranges of pseudo REGNO to file F. */
1256 print_pseudo_live_ranges (FILE *f
, int regno
)
1258 if (lra_reg_info
[regno
].live_ranges
== NULL
)
1260 fprintf (f
, " r%d:", regno
);
1261 lra_print_live_range_list (f
, lra_reg_info
[regno
].live_ranges
);
1264 /* Print live ranges of pseudo REGNO to stderr. */
1266 lra_debug_pseudo_live_ranges (int regno
)
1268 print_pseudo_live_ranges (stderr
, regno
);
1271 /* Print live ranges of all pseudos to file F. */
1273 print_live_ranges (FILE *f
)
1277 max_regno
= max_reg_num ();
1278 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1279 print_pseudo_live_ranges (f
, i
);
1282 /* Print live ranges of all pseudos to stderr. */
1284 lra_debug_live_ranges (void)
1286 print_live_ranges (stderr
);
1289 /* Compress pseudo live ranges. */
1291 compress_live_ranges (void)
1293 remove_some_program_points_and_update_live_ranges ();
1294 if (lra_dump_file
!= NULL
)
1296 fprintf (lra_dump_file
, "Ranges after the compression:\n");
1297 print_live_ranges (lra_dump_file
);
1303 /* The number of the current live range pass. */
1304 int lra_live_range_iter
;
1306 /* The function creates live ranges only for memory pseudos (or for
1307 all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos. It
1308 also does dead insn elimination if DEAD_INSN_P and global live
1309 analysis only for pseudos and only if the pseudo live info was
1310 changed on a BB border. Return TRUE if the live info was
1313 lra_create_live_ranges_1 (bool all_p
, bool dead_insn_p
)
1316 int i
, hard_regno
, max_regno
= max_reg_num ();
1318 bool bb_live_change_p
, have_referenced_pseudos
= false;
1320 timevar_push (TV_LRA_CREATE_LIVE_RANGES
);
1322 complete_info_p
= all_p
;
1323 if (lra_dump_file
!= NULL
)
1324 fprintf (lra_dump_file
,
1325 "\n********** Pseudo live ranges #%d: **********\n\n",
1326 ++lra_live_range_iter
);
1327 memset (lra_hard_reg_usage
, 0, sizeof (lra_hard_reg_usage
));
1328 for (i
= 0; i
< max_regno
; i
++)
1330 lra_reg_info
[i
].live_ranges
= NULL
;
1331 CLEAR_HARD_REG_SET (lra_reg_info
[i
].conflict_hard_regs
);
1332 lra_reg_info
[i
].preferred_hard_regno1
= -1;
1333 lra_reg_info
[i
].preferred_hard_regno2
= -1;
1334 lra_reg_info
[i
].preferred_hard_regno_profit1
= 0;
1335 lra_reg_info
[i
].preferred_hard_regno_profit2
= 0;
1337 lra_reg_info
[i
].no_stack_p
= false;
1339 /* The biggest mode is already set but its value might be to
1340 conservative because of recent transformation. Here in this
1341 file we recalculate it again as it costs practically
1343 if (!HARD_REGISTER_NUM_P (i
) && regno_reg_rtx
[i
] != NULL_RTX
)
1344 lra_reg_info
[i
].biggest_mode
= GET_MODE (regno_reg_rtx
[i
]);
1346 lra_reg_info
[i
].biggest_mode
= VOIDmode
;
1347 if (!HARD_REGISTER_NUM_P (i
)
1348 && lra_reg_info
[i
].nrefs
!= 0)
1350 if ((hard_regno
= reg_renumber
[i
]) >= 0)
1351 lra_hard_reg_usage
[hard_regno
] += lra_reg_info
[i
].freq
;
1352 have_referenced_pseudos
= true;
1357 /* Under some circumstances, we can have functions without pseudo
1358 registers. For such functions, lra_live_max_point will be 0,
1359 see e.g. PR55604, and there's nothing more to do for us here. */
1360 if (! have_referenced_pseudos
)
1362 timevar_pop (TV_LRA_CREATE_LIVE_RANGES
);
1366 pseudos_live
= sparseset_alloc (max_regno
);
1367 pseudos_live_through_calls
= sparseset_alloc (max_regno
);
1368 pseudos_live_through_setjumps
= sparseset_alloc (max_regno
);
1369 start_living
= sparseset_alloc (max_regno
);
1370 start_dying
= sparseset_alloc (max_regno
);
1371 dead_set
= sparseset_alloc (max_regno
);
1372 unused_set
= sparseset_alloc (max_regno
);
1374 unsigned new_length
= get_max_uid () * 2;
1375 point_freq_vec
.truncate (0);
1376 point_freq_vec
.reserve_exact (new_length
);
1377 lra_point_freq
= point_freq_vec
.address ();
1378 auto_vec
<int, 20> post_order_rev_cfg
;
1379 inverted_post_order_compute (&post_order_rev_cfg
);
1380 lra_assert (post_order_rev_cfg
.length () == (unsigned) n_basic_blocks_for_fn (cfun
));
1381 bb_live_change_p
= false;
1382 for (i
= post_order_rev_cfg
.length () - 1; i
>= 0; --i
)
1384 bb
= BASIC_BLOCK_FOR_FN (cfun
, post_order_rev_cfg
[i
]);
1385 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
1386 == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1388 if (process_bb_lives (bb
, curr_point
, dead_insn_p
))
1389 bb_live_change_p
= true;
1391 if (bb_live_change_p
)
1393 /* We need to clear pseudo live info as some pseudos can
1394 disappear, e.g. pseudos with used equivalences. */
1395 FOR_EACH_BB_FN (bb
, cfun
)
1397 bitmap_clear_range (df_get_live_in (bb
), FIRST_PSEUDO_REGISTER
,
1398 max_regno
- FIRST_PSEUDO_REGISTER
);
1399 bitmap_clear_range (df_get_live_out (bb
), FIRST_PSEUDO_REGISTER
,
1400 max_regno
- FIRST_PSEUDO_REGISTER
);
1402 /* As we did not change CFG since LRA start we can use
1403 DF-infrastructure solver to solve live data flow problem. */
1404 for (int i
= 0; HARD_REGISTER_NUM_P (i
); ++i
)
1406 if (TEST_HARD_REG_BIT (hard_regs_spilled_into
, i
))
1407 bitmap_clear_bit (&all_hard_regs_bitmap
, i
);
1410 (DF_BACKWARD
, NULL
, live_con_fun_0
, live_con_fun_n
,
1411 live_trans_fun
, &all_blocks
,
1412 df_get_postorder (DF_BACKWARD
), df_get_n_blocks (DF_BACKWARD
));
1413 if (lra_dump_file
!= NULL
)
1415 fprintf (lra_dump_file
,
1416 "Global pseudo live data have been updated:\n");
1418 FOR_EACH_BB_FN (bb
, cfun
)
1420 bb_data_t bb_info
= get_bb_data (bb
);
1421 bitmap bb_livein
= df_get_live_in (bb
);
1422 bitmap bb_liveout
= df_get_live_out (bb
);
1424 fprintf (lra_dump_file
, "\nBB %d:\n", bb
->index
);
1425 lra_dump_bitmap_with_title (" gen:",
1426 &bb_info
->gen_pseudos
, bb
->index
);
1427 lra_dump_bitmap_with_title (" killed:",
1428 &bb_info
->killed_pseudos
, bb
->index
);
1429 lra_dump_bitmap_with_title (" livein:", bb_livein
, bb
->index
);
1430 lra_dump_bitmap_with_title (" liveout:", bb_liveout
, bb
->index
);
1434 lra_live_max_point
= curr_point
;
1435 if (lra_dump_file
!= NULL
)
1436 print_live_ranges (lra_dump_file
);
1438 sparseset_free (unused_set
);
1439 sparseset_free (dead_set
);
1440 sparseset_free (start_dying
);
1441 sparseset_free (start_living
);
1442 sparseset_free (pseudos_live_through_calls
);
1443 sparseset_free (pseudos_live_through_setjumps
);
1444 sparseset_free (pseudos_live
);
1445 compress_live_ranges ();
1446 timevar_pop (TV_LRA_CREATE_LIVE_RANGES
);
1447 return bb_live_change_p
;
1450 /* The main entry function creates live-ranges and other live info
1451 necessary for the assignment sub-pass. It uses
1452 lra_creates_live_ranges_1 -- so read comments for the
1455 lra_create_live_ranges (bool all_p
, bool dead_insn_p
)
1457 if (! lra_create_live_ranges_1 (all_p
, dead_insn_p
))
1459 if (lra_dump_file
!= NULL
)
1460 fprintf (lra_dump_file
, "Live info was changed -- recalculate it\n");
1461 /* Live info was changed on a bb border. It means that some info,
1462 e.g. about conflict regs, calls crossed, and live ranges may be
1463 wrong. We need this info for allocation. So recalculate it
1464 again but without removing dead insns which can change live info
1465 again. Repetitive live range calculations are expensive therefore
1466 we stop here as we already have correct info although some
1467 improvement in rare cases could be possible on this sub-pass if
1468 we do dead insn elimination again (still the improvement may
1470 lra_clear_live_ranges ();
1471 bool res
= lra_create_live_ranges_1 (all_p
, false);
1475 /* Finish all live ranges. */
1477 lra_clear_live_ranges (void)
1481 for (i
= 0; i
< max_reg_num (); i
++)
1482 free_live_range_list (lra_reg_info
[i
].live_ranges
);
1483 point_freq_vec
.release ();
1486 /* Initialize live ranges data once per function. */
1488 lra_live_ranges_init (void)
1490 bitmap_initialize (&temp_bitmap
, ®_obstack
);
1491 initiate_live_solver ();
1494 /* Finish live ranges data once per function. */
1496 lra_live_ranges_finish (void)
1498 finish_live_solver ();
1499 bitmap_clear (&temp_bitmap
);
1500 lra_live_range_pool
.release ();