1 /* Build live ranges for pseudos.
2 Copyright (C) 2010-2022 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 /* Clear pseudo REGNO in SET or all hard registers of REGNO in MODE in SET. */
620 clear_sparseset_regnos (sparseset set, int regno, enum machine_mode mode)
622 if (regno >= FIRST_PSEUDO_REGISTER)
624 sparseset_clear_bit (dead_set, regno);
627 for (int last = end_hard_regno (mode, regno); regno < last; regno++)
628 sparseset_clear_bit (set, regno);
631 /* Return true if pseudo REGNO is in SET or all hard registers of REGNO in MODE
634 regnos_in_sparseset_p (sparseset set, int regno, enum machine_mode mode)
636 if (regno >= FIRST_PSEUDO_REGISTER)
637 return sparseset_bit_p (dead_set, regno);
638 for (int last = end_hard_regno (mode, regno); regno < last; regno++)
639 if (!sparseset_bit_p (set, regno))
644 /* Process insns of the basic block BB to update pseudo live ranges,
645 pseudo hard register conflicts, and insn notes. We do it on
646 backward scan of BB insns. CURR_POINT is the program point where
647 BB ends. The function updates this counter and returns in
648 CURR_POINT the program point where BB starts. The function also
649 does local live info updates and can delete the dead insns if
650 DEAD_INSN_P. It returns true if pseudo live info was
651 changed at the BB start. */
653 process_bb_lives (basic_block bb, int &curr_point, bool dead_insn_p)
662 bool need_curr_point_incr;
663 /* Only has a meaningful value once we've seen a call. */
664 function_abi last_call_abi = default_function_abi;
666 reg_live_out = df_get_live_out (bb);
667 sparseset_clear (pseudos_live);
668 sparseset_clear (pseudos_live_through_calls);
669 sparseset_clear (pseudos_live_through_setjumps);
670 REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
671 hard_regs_live &= ~eliminable_regset;
672 EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
674 update_pseudo_point (j, curr_point, USE_POINT);
675 mark_pseudo_live (j);
678 bb_gen_pseudos = &get_bb_data (bb)->gen_pseudos;
679 bb_killed_pseudos = &get_bb_data (bb)->killed_pseudos;
680 bitmap_clear (bb_gen_pseudos);
681 bitmap_clear (bb_killed_pseudos);
682 freq = REG_FREQ_FROM_BB (bb);
684 if (lra_dump_file != NULL)
685 fprintf (lra_dump_file, " BB %d\n", bb->index);
687 /* Scan the code of this basic block, noting which pseudos and hard
688 regs are born or die.
690 Note that this loop treats uninitialized values as live until the
691 beginning of the block. For example, if an instruction uses
692 (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
693 FOO will remain live until the beginning of the block. Likewise
694 if FOO is not set at all. This is unnecessarily pessimistic, but
695 it probably doesn't matter much in practice. */
696 FOR_BB_INSNS_REVERSE_SAFE (bb, curr_insn, next)
699 int n_alt, dst_regno, src_regno;
701 struct lra_insn_reg *reg;
703 if (!NONDEBUG_INSN_P (curr_insn))
706 curr_id = lra_get_insn_recog_data (curr_insn);
707 curr_static_id = curr_id->insn_static_data;
708 n_alt = curr_id->used_insn_alternative;
709 if (lra_dump_file != NULL)
710 fprintf (lra_dump_file, " Insn %u: point = %d, n_alt = %d\n",
711 INSN_UID (curr_insn), curr_point, n_alt);
713 set = single_set (curr_insn);
715 if (dead_insn_p && set != NULL_RTX
716 && REG_P (SET_DEST (set)) && !HARD_REGISTER_P (SET_DEST (set))
717 && find_reg_note (curr_insn, REG_EH_REGION, NULL_RTX) == NULL_RTX
718 && ! may_trap_p (PATTERN (curr_insn))
719 /* Don't do premature remove of pic offset pseudo as we can
720 start to use it after some reload generation. */
721 && (pic_offset_table_rtx == NULL_RTX
722 || pic_offset_table_rtx != SET_DEST (set)))
724 bool remove_p = true;
726 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
727 if (reg->type != OP_IN
728 && (reg->regno < FIRST_PSEUDO_REGISTER
729 ? TEST_HARD_REG_BIT (hard_regs_live, reg->regno)
730 : sparseset_bit_p (pseudos_live, reg->regno)))
735 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
736 if (reg->type != OP_IN)
742 if (remove_p && ! volatile_refs_p (PATTERN (curr_insn)))
744 dst_regno = REGNO (SET_DEST (set));
745 if (lra_dump_file != NULL)
746 fprintf (lra_dump_file, " Deleting dead insn %u\n",
747 INSN_UID (curr_insn));
748 lra_set_insn_deleted (curr_insn);
749 if (lra_reg_info[dst_regno].nrefs == 0)
751 /* There might be some debug insns with the pseudo. */
755 bitmap_copy (&temp_bitmap, &lra_reg_info[dst_regno].insn_bitmap);
756 EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap, 0, uid, bi)
758 insn = lra_insn_recog_data[uid]->insn;
759 lra_substitute_pseudo_within_insn (insn, dst_regno,
760 SET_SRC (set), true);
761 lra_update_insn_regno_info (insn);
768 /* Update max ref width and hard reg usage. */
769 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
771 int regno = reg->regno;
773 if (partial_subreg_p (lra_reg_info[regno].biggest_mode,
775 lra_reg_info[regno].biggest_mode = reg->biggest_mode;
776 if (HARD_REGISTER_NUM_P (regno))
777 lra_hard_reg_usage[regno] += freq;
780 call_p = CALL_P (curr_insn);
782 /* If we have a simple register copy and the source reg is live after
783 this instruction, then remove the source reg from the live set so
784 that it will not conflict with the destination reg. */
785 rtx ignore_reg = non_conflicting_reg_copy_p (curr_insn);
786 if (ignore_reg != NULL_RTX)
788 int ignore_regno = REGNO (ignore_reg);
789 if (HARD_REGISTER_NUM_P (ignore_regno)
790 && TEST_HARD_REG_BIT (hard_regs_live, ignore_regno))
791 CLEAR_HARD_REG_BIT (hard_regs_live, ignore_regno);
792 else if (!HARD_REGISTER_NUM_P (ignore_regno)
793 && sparseset_bit_p (pseudos_live, ignore_regno))
794 sparseset_clear_bit (pseudos_live, ignore_regno);
796 /* We don't need any special handling of the source reg if
797 it is dead after this instruction. */
798 ignore_reg = NULL_RTX;
801 src_regno = (set != NULL_RTX && REG_P (SET_SRC (set))
802 ? REGNO (SET_SRC (set)) : -1);
803 dst_regno = (set != NULL_RTX && REG_P (SET_DEST (set))
804 ? REGNO (SET_DEST (set)) : -1);
806 && src_regno >= 0 && dst_regno >= 0
807 /* Check that source regno does not conflict with
808 destination regno to exclude most impossible
810 && (((!HARD_REGISTER_NUM_P (src_regno)
811 && (! sparseset_bit_p (pseudos_live, src_regno)
812 || (!HARD_REGISTER_NUM_P (dst_regno)
813 && lra_reg_val_equal_p (src_regno,
814 lra_reg_info[dst_regno].val,
815 lra_reg_info[dst_regno].offset))))
816 || (HARD_REGISTER_NUM_P (src_regno)
817 && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno)))
818 /* It might be 'inheritance pseudo <- reload pseudo'. */
819 || (src_regno >= lra_constraint_new_regno_start
820 && dst_regno >= lra_constraint_new_regno_start
821 /* Remember to skip special cases where src/dest regnos are
822 the same, e.g. insn SET pattern has matching constraints
824 && src_regno != dst_regno)))
826 int hard_regno = -1, regno = -1;
828 if (dst_regno >= lra_constraint_new_regno_start
829 && src_regno >= lra_constraint_new_regno_start)
831 /* It might be still an original (non-reload) insn with
832 one unused output and a constraint requiring to use
833 the same reg for input/output operands. In this case
834 dst_regno and src_regno have the same value, we don't
835 need a misleading copy for this case. */
836 if (dst_regno != src_regno)
837 lra_create_copy (dst_regno, src_regno, freq);
839 else if (dst_regno >= lra_constraint_new_regno_start)
841 if (!HARD_REGISTER_NUM_P (hard_regno = src_regno))
842 hard_regno = reg_renumber[src_regno];
845 else if (src_regno >= lra_constraint_new_regno_start)
847 if (!HARD_REGISTER_NUM_P (hard_regno = dst_regno))
848 hard_regno = reg_renumber[dst_regno];
851 if (regno >= 0 && hard_regno >= 0)
852 lra_setup_reload_pseudo_preferenced_hard_reg
853 (regno, hard_regno, freq);
856 sparseset_clear (start_living);
858 /* Mark each defined value as live. We need to do this for
859 unused values because they still conflict with quantities
860 that are live at the time of the definition. */
861 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
862 if (reg->type != OP_IN)
864 update_pseudo_point (reg->regno, curr_point, USE_POINT);
865 mark_regno_live (reg->regno, reg->biggest_mode);
866 /* ??? Should be a no-op for unused registers. */
867 check_pseudos_live_through_calls (reg->regno, last_call_abi);
870 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
871 if (reg->type != OP_IN)
872 make_hard_regno_live (reg->regno);
874 if (curr_id->arg_hard_regs != NULL)
875 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
876 if (!HARD_REGISTER_NUM_P (regno))
877 /* It is a clobber. */
878 make_hard_regno_live (regno - FIRST_PSEUDO_REGISTER);
880 sparseset_copy (unused_set, start_living);
882 sparseset_clear (start_dying);
884 /* See which defined values die here. */
885 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
886 if (reg->type != OP_IN
887 && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
889 if (reg->type == OP_OUT)
890 update_pseudo_point (reg->regno, curr_point, DEF_POINT);
891 mark_regno_dead (reg->regno, reg->biggest_mode);
894 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
895 if (reg->type != OP_IN
896 && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
897 make_hard_regno_dead (reg->regno);
899 if (curr_id->arg_hard_regs != NULL)
900 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
901 if (!HARD_REGISTER_NUM_P (regno))
902 /* It is a clobber. */
903 make_hard_regno_dead (regno - FIRST_PSEUDO_REGISTER);
907 function_abi call_abi = insn_callee_abi (curr_insn);
909 if (last_call_abi != call_abi)
910 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
911 check_pseudos_live_through_calls (j, last_call_abi);
913 last_call_abi = call_abi;
915 sparseset_ior (pseudos_live_through_calls,
916 pseudos_live_through_calls, pseudos_live);
917 if (cfun->has_nonlocal_label
918 || (!targetm.setjmp_preserves_nonvolatile_regs_p ()
919 && (find_reg_note (curr_insn, REG_SETJMP, NULL_RTX)
921 sparseset_ior (pseudos_live_through_setjumps,
922 pseudos_live_through_setjumps, pseudos_live);
925 /* Increment the current program point if we must. */
926 if (sparseset_contains_pseudos_p (unused_set)
927 || sparseset_contains_pseudos_p (start_dying))
928 next_program_point (curr_point, freq);
930 /* If we removed the source reg from a simple register copy from the
931 live set above, then add it back now so we don't accidentally add
932 it to the start_living set below. */
933 if (ignore_reg != NULL_RTX)
935 int ignore_regno = REGNO (ignore_reg);
936 if (HARD_REGISTER_NUM_P (ignore_regno))
937 SET_HARD_REG_BIT (hard_regs_live, ignore_regno);
939 sparseset_set_bit (pseudos_live, ignore_regno);
942 sparseset_clear (start_living);
944 /* Mark each used value as live. */
945 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
946 if (reg->type != OP_OUT)
948 if (reg->type == OP_IN)
949 update_pseudo_point (reg->regno, curr_point, USE_POINT);
950 mark_regno_live (reg->regno, reg->biggest_mode);
951 check_pseudos_live_through_calls (reg->regno, last_call_abi);
954 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
955 if (reg->type != OP_OUT)
956 make_hard_regno_live (reg->regno);
958 if (curr_id->arg_hard_regs != NULL)
959 /* Make argument hard registers live. */
960 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
961 if (HARD_REGISTER_NUM_P (regno))
962 make_hard_regno_live (regno);
964 sparseset_and_compl (dead_set, start_living, start_dying);
966 sparseset_clear (start_dying);
968 /* Mark early clobber outputs dead. */
969 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
970 if (reg->type != OP_IN
971 && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
973 if (reg->type == OP_OUT)
974 update_pseudo_point (reg->regno, curr_point, DEF_POINT);
975 mark_regno_dead (reg->regno, reg->biggest_mode);
977 /* We're done processing inputs, so make sure early clobber
978 operands that are both inputs and outputs are still live. */
979 if (reg->type == OP_INOUT)
980 mark_regno_live (reg->regno, reg->biggest_mode);
983 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
984 if (reg->type != OP_IN
985 && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
987 struct lra_insn_reg *reg2;
989 /* We can have early clobbered non-operand hard reg and
990 the same hard reg as an insn input. Don't make hard
991 reg dead before the insns. */
992 for (reg2 = curr_id->regs; reg2 != NULL; reg2 = reg2->next)
993 if (reg2->type != OP_OUT && reg2->regno == reg->regno)
996 make_hard_regno_dead (reg->regno);
999 /* Increment the current program point if we must. */
1000 if (sparseset_contains_pseudos_p (dead_set)
1001 || sparseset_contains_pseudos_p (start_dying))
1002 next_program_point (curr_point, freq);
1005 for (link_loc = ®_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
1007 if (REG_NOTE_KIND (link) != REG_DEAD
1008 && REG_NOTE_KIND (link) != REG_UNUSED)
1010 else if (REG_P (XEXP (link, 0)))
1012 rtx note_reg = XEXP (link, 0);
1013 int note_regno = REGNO (note_reg);
1015 if ((REG_NOTE_KIND (link) == REG_DEAD
1016 && ! regnos_in_sparseset_p (dead_set, note_regno,
1017 GET_MODE (note_reg)))
1018 || (REG_NOTE_KIND (link) == REG_UNUSED
1019 && ! regnos_in_sparseset_p (unused_set, note_regno,
1020 GET_MODE (note_reg))))
1022 *link_loc = XEXP (link, 1);
1025 if (REG_NOTE_KIND (link) == REG_DEAD)
1026 clear_sparseset_regnos (dead_set, note_regno,
1027 GET_MODE (note_reg));
1028 else if (REG_NOTE_KIND (link) == REG_UNUSED)
1029 clear_sparseset_regnos (unused_set, note_regno,
1030 GET_MODE (note_reg));
1032 link_loc = &XEXP (link, 1);
1034 EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
1035 add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
1036 EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
1037 add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
1040 if (bb_has_eh_pred (bb))
1041 /* Any pseudos that are currently live conflict with the eh_return
1042 data registers. For liveness purposes, these registers are set
1043 by artificial definitions at the start of the BB, so are not
1044 actually live on entry. */
1047 unsigned int regno = EH_RETURN_DATA_REGNO (j);
1049 if (regno == INVALID_REGNUM)
1052 make_hard_regno_live (regno);
1053 make_hard_regno_dead (regno);
1056 /* Pseudos can't go in stack regs at the start of a basic block that
1057 is reached by an abnormal edge. Likewise for registers that are at
1058 least partly call clobbered, because caller-save, fixup_abnormal_edges
1059 and possibly the table driven EH machinery are not quite ready to
1060 handle such pseudos live across such edges. */
1061 if (bb_has_abnormal_pred (bb))
1063 HARD_REG_SET clobbers;
1065 CLEAR_HARD_REG_SET (clobbers);
1067 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
1068 lra_reg_info[px].no_stack_p = true;
1069 for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1070 SET_HARD_REG_BIT (clobbers, px);
1072 /* No need to record conflicts for call clobbered regs if we
1073 have nonlocal labels around, as we don't ever try to
1074 allocate such regs in this case. */
1075 if (!cfun->has_nonlocal_label
1076 && has_abnormal_call_or_eh_pred_edge_p (bb))
1077 for (px = 0; HARD_REGISTER_NUM_P (px); px++)
1078 if (eh_edge_abi.clobbers_at_least_part_of_reg_p (px)
1079 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
1080 /* We should create a conflict of PIC pseudo with PIC
1081 hard reg as PIC hard reg can have a wrong value after
1082 jump described by the abnormal edge. In this case we
1083 cannot allocate PIC hard reg to PIC pseudo as PIC
1084 pseudo will also have a wrong value. */
1085 || (px == REAL_PIC_OFFSET_TABLE_REGNUM
1086 && pic_offset_table_rtx != NULL_RTX
1087 && !HARD_REGISTER_P (pic_offset_table_rtx))
1090 SET_HARD_REG_BIT (clobbers, px);
1092 clobbers &= ~hard_regs_live;
1093 for (px = 0; HARD_REGISTER_NUM_P (px); px++)
1094 if (TEST_HARD_REG_BIT (clobbers, px))
1096 make_hard_regno_live (px);
1097 make_hard_regno_dead (px);
1101 bool live_change_p = false;
1102 /* Check if bb border live info was changed. */
1103 unsigned int live_pseudos_num = 0;
1104 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb),
1105 FIRST_PSEUDO_REGISTER, j, bi)
1108 if (! sparseset_bit_p (pseudos_live, j))
1110 live_change_p = true;
1111 if (lra_dump_file != NULL)
1112 fprintf (lra_dump_file,
1113 " r%d is removed as live at bb%d start\n", j, bb->index);
1118 && sparseset_cardinality (pseudos_live) != live_pseudos_num)
1120 live_change_p = true;
1121 if (lra_dump_file != NULL)
1122 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
1123 if (! bitmap_bit_p (df_get_live_in (bb), j))
1124 fprintf (lra_dump_file,
1125 " r%d is added to live at bb%d start\n", j, bb->index);
1127 /* See if we'll need an increment at the end of this basic block.
1128 An increment is needed if the PSEUDOS_LIVE set is not empty,
1129 to make sure the finish points are set up correctly. */
1130 need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0);
1132 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
1134 update_pseudo_point (i, curr_point, DEF_POINT);
1135 mark_pseudo_dead (i);
1138 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
1140 if (sparseset_cardinality (pseudos_live_through_calls) == 0)
1142 if (sparseset_bit_p (pseudos_live_through_calls, j))
1143 check_pseudos_live_through_calls (j, last_call_abi);
1146 for (i = 0; HARD_REGISTER_NUM_P (i); ++i)
1148 if (!TEST_HARD_REG_BIT (hard_regs_live, i))
1151 if (!TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
1154 if (bitmap_bit_p (df_get_live_in (bb), i))
1157 live_change_p = true;
1159 fprintf (lra_dump_file,
1160 " hard reg r%d is added to live at bb%d start\n", i,
1162 bitmap_set_bit (df_get_live_in (bb), i);
1165 if (need_curr_point_incr)
1166 next_program_point (curr_point, freq);
1168 return live_change_p;
1171 /* Compress pseudo live ranges by removing program points where
1172 nothing happens. Complexity of many algorithms in LRA is linear
1173 function of program points number. To speed up the code we try to
1174 minimize the number of the program points here. */
1176 remove_some_program_points_and_update_live_ranges (void)
1181 lra_live_range_t r, prev_r, next_r;
1182 sbitmap_iterator sbi;
1183 bool born_p, dead_p, prev_born_p, prev_dead_p;
1185 auto_sbitmap born (lra_live_max_point);
1186 auto_sbitmap dead (lra_live_max_point);
1187 bitmap_clear (born);
1188 bitmap_clear (dead);
1189 max_regno = max_reg_num ();
1190 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1192 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1194 lra_assert (r->start <= r->finish);
1195 bitmap_set_bit (born, r->start);
1196 bitmap_set_bit (dead, r->finish);
1199 auto_sbitmap born_or_dead (lra_live_max_point);
1200 bitmap_ior (born_or_dead, born, dead);
1201 map = XCNEWVEC (int, lra_live_max_point);
1203 prev_born_p = prev_dead_p = false;
1204 EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1206 born_p = bitmap_bit_p (born, i);
1207 dead_p = bitmap_bit_p (dead, i);
1208 if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1209 || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1212 lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
1217 lra_point_freq[n] = lra_point_freq[i];
1219 prev_born_p = born_p;
1220 prev_dead_p = dead_p;
1223 if (lra_dump_file != NULL)
1224 fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1225 lra_live_max_point, n,
1226 lra_live_max_point ? 100 * n / lra_live_max_point : 100);
1227 if (n < lra_live_max_point)
1229 lra_live_max_point = n;
1230 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1232 for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
1237 r->start = map[r->start];
1238 r->finish = map[r->finish];
1239 if (prev_r == NULL || prev_r->start > r->finish + 1)
1244 prev_r->start = r->start;
1245 prev_r->next = next_r;
1246 lra_live_range_pool.remove (r);
1253 /* Print live ranges R to file F. */
1255 lra_print_live_range_list (FILE *f, lra_live_range_t r)
1257 for (; r != NULL; r = r->next)
1258 fprintf (f, " [%d..%d]", r->start, r->finish);
1263 debug (lra_live_range &ref)
1265 lra_print_live_range_list (stderr, &ref);
1269 debug (lra_live_range *ptr)
1274 fprintf (stderr, "<nil>\n");
1277 /* Print live ranges R to stderr. */
1279 lra_debug_live_range_list (lra_live_range_t r)
1281 lra_print_live_range_list (stderr, r);
1284 /* Print live ranges of pseudo REGNO to file F. */
1286 print_pseudo_live_ranges (FILE *f, int regno)
1288 if (lra_reg_info[regno].live_ranges == NULL)
1290 fprintf (f, " r%d:", regno);
1291 lra_print_live_range_list (f, lra_reg_info[regno].live_ranges);
1294 /* Print live ranges of pseudo REGNO to stderr. */
1296 lra_debug_pseudo_live_ranges (int regno)
1298 print_pseudo_live_ranges (stderr, regno);
1301 /* Print live ranges of all pseudos to file F. */
1303 print_live_ranges (FILE *f)
1307 max_regno = max_reg_num ();
1308 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1309 print_pseudo_live_ranges (f, i);
1312 /* Print live ranges of all pseudos to stderr. */
1314 lra_debug_live_ranges (void)
1316 print_live_ranges (stderr);
1319 /* Compress pseudo live ranges. */
1321 compress_live_ranges (void)
1323 remove_some_program_points_and_update_live_ranges ();
1324 if (lra_dump_file != NULL)
1326 fprintf (lra_dump_file, "Ranges after the compression:\n");
1327 print_live_ranges (lra_dump_file);
1333 /* The number of the current live range pass. */
1334 int lra_live_range_iter;
1336 /* The function creates live ranges only for memory pseudos (or for
1337 all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos. It
1338 also does dead insn elimination if DEAD_INSN_P and global live
1339 analysis only for pseudos and only if the pseudo live info was
1340 changed on a BB border. Return TRUE if the live info was
1343 lra_create_live_ranges_1 (bool all_p, bool dead_insn_p)
1346 int i, hard_regno, max_regno = max_reg_num ();
1348 bool bb_live_change_p, have_referenced_pseudos = false;
1350 timevar_push (TV_LRA_CREATE_LIVE_RANGES);
1352 complete_info_p = all_p;
1353 if (lra_dump_file != NULL)
1354 fprintf (lra_dump_file,
1355 "\n********** Pseudo live ranges #%d: **********\n\n",
1356 ++lra_live_range_iter);
1357 memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage));
1358 for (i = 0; i < max_regno; i++)
1360 lra_reg_info[i].live_ranges = NULL;
1361 CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1362 lra_reg_info[i].preferred_hard_regno1 = -1;
1363 lra_reg_info[i].preferred_hard_regno2 = -1;
1364 lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1365 lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1367 lra_reg_info[i].no_stack_p = false;
1369 /* The biggest mode is already set but its value might be to
1370 conservative because of recent transformation. Here in this
1371 file we recalculate it again as it costs practically
1373 if (!HARD_REGISTER_NUM_P (i) && regno_reg_rtx[i] != NULL_RTX)
1374 lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
1376 lra_reg_info[i].biggest_mode = VOIDmode;
1377 if (!HARD_REGISTER_NUM_P (i)
1378 && lra_reg_info[i].nrefs != 0)
1380 if ((hard_regno = reg_renumber[i]) >= 0)
1381 lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
1382 have_referenced_pseudos = true;
1387 /* Under some circumstances, we can have functions without pseudo
1388 registers. For such functions, lra_live_max_point will be 0,
1389 see e.g. PR55604, and there's nothing more to do for us here. */
1390 if (! have_referenced_pseudos)
1392 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1396 pseudos_live = sparseset_alloc (max_regno);
1397 pseudos_live_through_calls = sparseset_alloc (max_regno);
1398 pseudos_live_through_setjumps = sparseset_alloc (max_regno);
1399 start_living = sparseset_alloc (max_regno);
1400 start_dying = sparseset_alloc (max_regno);
1401 dead_set = sparseset_alloc (max_regno);
1402 unused_set = sparseset_alloc (max_regno);
1404 unsigned new_length = get_max_uid () * 2;
1405 point_freq_vec.truncate (0);
1406 point_freq_vec.reserve_exact (new_length);
1407 lra_point_freq = point_freq_vec.address ();
1408 auto_vec<int, 20> post_order_rev_cfg;
1409 inverted_post_order_compute (&post_order_rev_cfg);
1410 lra_assert (post_order_rev_cfg.length () == (unsigned) n_basic_blocks_for_fn (cfun));
1411 bb_live_change_p = false;
1412 for (i = post_order_rev_cfg.length () - 1; i >= 0; --i)
1414 bb = BASIC_BLOCK_FOR_FN (cfun, post_order_rev_cfg[i]);
1415 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
1416 == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1418 if (process_bb_lives (bb, curr_point, dead_insn_p))
1419 bb_live_change_p = true;
1421 if (bb_live_change_p)
1423 /* We need to clear pseudo live info as some pseudos can
1424 disappear, e.g. pseudos with used equivalences. */
1425 FOR_EACH_BB_FN (bb, cfun)
1427 bitmap_clear_range (df_get_live_in (bb), FIRST_PSEUDO_REGISTER,
1428 max_regno - FIRST_PSEUDO_REGISTER);
1429 bitmap_clear_range (df_get_live_out (bb), FIRST_PSEUDO_REGISTER,
1430 max_regno - FIRST_PSEUDO_REGISTER);
1432 /* As we did not change CFG since LRA start we can use
1433 DF-infrastructure solver to solve live data flow problem. */
1434 for (int i = 0; HARD_REGISTER_NUM_P (i); ++i)
1436 if (TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
1437 bitmap_clear_bit (&all_hard_regs_bitmap, i);
1440 (DF_BACKWARD, NULL, live_con_fun_0, live_con_fun_n,
1441 live_trans_fun, &all_blocks,
1442 df_get_postorder (DF_BACKWARD), df_get_n_blocks (DF_BACKWARD));
1443 if (lra_dump_file != NULL)
1445 fprintf (lra_dump_file,
1446 "Global pseudo live data have been updated:\n");
1448 FOR_EACH_BB_FN (bb, cfun)
1450 bb_data_t bb_info = get_bb_data (bb);
1451 bitmap bb_livein = df_get_live_in (bb);
1452 bitmap bb_liveout = df_get_live_out (bb);
1454 fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
1455 lra_dump_bitmap_with_title (" gen:",
1456 &bb_info->gen_pseudos, bb->index);
1457 lra_dump_bitmap_with_title (" killed:",
1458 &bb_info->killed_pseudos, bb->index);
1459 lra_dump_bitmap_with_title (" livein:", bb_livein, bb->index);
1460 lra_dump_bitmap_with_title (" liveout:", bb_liveout, bb->index);
1464 lra_live_max_point = curr_point;
1465 if (lra_dump_file != NULL)
1466 print_live_ranges (lra_dump_file);
1468 sparseset_free (unused_set);
1469 sparseset_free (dead_set);
1470 sparseset_free (start_dying);
1471 sparseset_free (start_living);
1472 sparseset_free (pseudos_live_through_calls);
1473 sparseset_free (pseudos_live_through_setjumps);
1474 sparseset_free (pseudos_live);
1475 compress_live_ranges ();
1476 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1477 return bb_live_change_p;
1480 /* The main entry function creates live-ranges and other live info
1481 necessary for the assignment sub-pass. It uses
1482 lra_creates_live_ranges_1 -- so read comments for the
1485 lra_create_live_ranges (bool all_p, bool dead_insn_p)
1487 if (! lra_create_live_ranges_1 (all_p, dead_insn_p))
1489 if (lra_dump_file != NULL)
1490 fprintf (lra_dump_file, "Live info was changed -- recalculate it\n");
1491 /* Live info was changed on a bb border. It means that some info,
1492 e.g. about conflict regs, calls crossed, and live ranges may be
1493 wrong. We need this info for allocation. So recalculate it
1494 again but without removing dead insns which can change live info
1495 again. Repetitive live range calculations are expensive therefore
1496 we stop here as we already have correct info although some
1497 improvement in rare cases could be possible on this sub-pass if
1498 we do dead insn elimination again (still the improvement may
1500 lra_clear_live_ranges ();
1501 bool res = lra_create_live_ranges_1 (all_p, false);
1505 /* Finish all live ranges. */
1507 lra_clear_live_ranges (void)
1511 for (i = 0; i < max_reg_num (); i++)
1512 free_live_range_list (lra_reg_info[i].live_ranges);
1513 point_freq_vec.release ();
1516 /* Initialize live ranges data once per function. */
1518 lra_live_ranges_init (void)
1520 bitmap_initialize (&temp_bitmap, ®_obstack);
1521 initiate_live_solver ();
1524 /* Finish live ranges data once per function. */
1526 lra_live_ranges_finish (void)
1528 finish_live_solver ();
1529 bitmap_clear (&temp_bitmap);
1530 lra_live_range_pool.release ();