1 /* Build live ranges for pseudos.
2 Copyright (C) 2010-2019 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"
47 /* Program points are enumerated by numbers from range
48 0..LRA_LIVE_MAX_POINT-1. There are approximately two times more
49 program points than insns. Program points are places in the
50 program where liveness info can be changed. In most general case
51 (there are more complicated cases too) some program points
52 correspond to places where input operand dies and other ones
53 correspond to places where output operands are born. */
54 int lra_live_max_point
;
56 /* Accumulated execution frequency of all references for each hard
58 int lra_hard_reg_usage
[FIRST_PSEUDO_REGISTER
];
60 /* A global flag whose true value says to build live ranges for all
61 pseudos, otherwise the live ranges only for pseudos got memory is
62 build. True value means also building copies and setting up hard
63 register preferences. The complete info is necessary only for the
64 assignment pass. The complete info is not needed for the
65 coalescing and spill passes. */
66 static bool complete_info_p
;
68 /* Pseudos live at current point in the RTL scan. */
69 static sparseset pseudos_live
;
71 /* Pseudos probably living through calls and setjumps. As setjump is
72 a call too, if a bit in PSEUDOS_LIVE_THROUGH_SETJUMPS is set up
73 then the corresponding bit in PSEUDOS_LIVE_THROUGH_CALLS is set up
74 too. These data are necessary for cases when only one subreg of a
75 multi-reg pseudo is set up after a call. So we decide it is
76 probably live when traversing bb backward. We are sure about
77 living when we see its usage or definition of the pseudo. */
78 static sparseset pseudos_live_through_calls
;
79 static sparseset pseudos_live_through_setjumps
;
81 /* Set of hard regs (except eliminable ones) currently live. */
82 static HARD_REG_SET hard_regs_live
;
84 /* Set of pseudos and hard registers start living/dying in the current
85 insn. These sets are used to update REG_DEAD and REG_UNUSED notes
87 static sparseset start_living
, start_dying
;
89 /* Set of pseudos and hard regs dead and unused in the current
91 static sparseset unused_set
, dead_set
;
93 /* Bitmap used for holding intermediate bitmap operation results. */
94 static bitmap_head temp_bitmap
;
96 /* Pool for pseudo live ranges. */
97 static object_allocator
<lra_live_range
> lra_live_range_pool ("live ranges");
99 /* Free live range list LR. */
101 free_live_range_list (lra_live_range_t lr
)
103 lra_live_range_t next
;
108 lra_live_range_pool
.remove (lr
);
113 /* Create and return pseudo live range with given attributes. */
114 static lra_live_range_t
115 create_live_range (int regno
, int start
, int finish
, lra_live_range_t next
)
117 lra_live_range_t p
= lra_live_range_pool
.allocate ();
125 /* Copy live range R and return the result. */
126 static lra_live_range_t
127 copy_live_range (lra_live_range_t r
)
129 return new (lra_live_range_pool
) lra_live_range (*r
);
132 /* Copy live range list given by its head R and return the result. */
134 lra_copy_live_range_list (lra_live_range_t r
)
136 lra_live_range_t p
, first
, *chain
;
139 for (chain
= &first
; r
!= NULL
; r
= r
->next
)
141 p
= copy_live_range (r
);
148 /* Merge *non-intersected* ranges R1 and R2 and returns the result.
149 The function maintains the order of ranges and tries to minimize
150 size of the result range list. Ranges R1 and R2 may not be used
153 lra_merge_live_ranges (lra_live_range_t r1
, lra_live_range_t r2
)
155 lra_live_range_t first
, last
;
161 for (first
= last
= NULL
; r1
!= NULL
&& r2
!= NULL
;)
163 if (r1
->start
< r2
->start
)
166 if (r1
->start
== r2
->finish
+ 1)
168 /* Joint ranges: merge r1 and r2 into r1. */
169 r1
->start
= r2
->start
;
170 lra_live_range_t temp
= r2
;
172 lra_live_range_pool
.remove (temp
);
176 gcc_assert (r2
->finish
+ 1 < r1
->start
);
177 /* Add r1 to the result. */
197 lra_assert (r2
!= NULL
);
206 /* Return TRUE if live ranges R1 and R2 intersect. */
208 lra_intersected_live_ranges_p (lra_live_range_t r1
, lra_live_range_t r2
)
210 /* Remember the live ranges are always kept ordered. */
211 while (r1
!= NULL
&& r2
!= NULL
)
213 if (r1
->start
> r2
->finish
)
215 else if (r2
->start
> r1
->finish
)
228 /* Return TRUE if set A contains a pseudo register, otherwise, return FALSE. */
230 sparseset_contains_pseudos_p (sparseset a
)
233 EXECUTE_IF_SET_IN_SPARSESET (a
, regno
)
234 if (!HARD_REGISTER_NUM_P (regno
))
239 /* Mark pseudo REGNO as living or dying at program point POINT, depending on
240 whether TYPE is a definition or a use. If this is the first reference to
241 REGNO that we've encountered, then create a new live range for it. */
244 update_pseudo_point (int regno
, int point
, enum point_type type
)
248 /* Don't compute points for hard registers. */
249 if (HARD_REGISTER_NUM_P (regno
))
252 if (complete_info_p
|| lra_get_regno_hard_regno (regno
) < 0)
254 if (type
== DEF_POINT
)
256 if (sparseset_bit_p (pseudos_live
, regno
))
258 p
= lra_reg_info
[regno
].live_ranges
;
259 lra_assert (p
!= NULL
);
265 if (!sparseset_bit_p (pseudos_live
, regno
)
266 && ((p
= lra_reg_info
[regno
].live_ranges
) == NULL
267 || (p
->finish
!= point
&& p
->finish
+ 1 != point
)))
268 lra_reg_info
[regno
].live_ranges
269 = create_live_range (regno
, point
, -1, p
);
274 /* The corresponding bitmaps of BB currently being processed. */
275 static bitmap bb_killed_pseudos
, bb_gen_pseudos
;
277 /* Record hard register REGNO as now being live. It updates
278 living hard regs and START_LIVING. */
280 make_hard_regno_live (int regno
)
282 lra_assert (HARD_REGISTER_NUM_P (regno
));
283 if (TEST_HARD_REG_BIT (hard_regs_live
, regno
))
285 SET_HARD_REG_BIT (hard_regs_live
, regno
);
286 sparseset_set_bit (start_living
, regno
);
287 if (fixed_regs
[regno
] || TEST_HARD_REG_BIT (hard_regs_spilled_into
, regno
))
288 bitmap_set_bit (bb_gen_pseudos
, regno
);
291 /* Process the definition of hard register REGNO. This updates
292 hard_regs_live, START_DYING and conflict hard regs for living
295 make_hard_regno_dead (int regno
)
297 lra_assert (HARD_REGISTER_NUM_P (regno
));
299 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, i
)
300 SET_HARD_REG_BIT (lra_reg_info
[i
].conflict_hard_regs
, regno
);
302 if (! TEST_HARD_REG_BIT (hard_regs_live
, regno
))
304 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
305 sparseset_set_bit (start_dying
, regno
);
306 if (fixed_regs
[regno
] || TEST_HARD_REG_BIT (hard_regs_spilled_into
, regno
))
308 bitmap_clear_bit (bb_gen_pseudos
, regno
);
309 bitmap_set_bit (bb_killed_pseudos
, regno
);
313 /* Mark pseudo REGNO as now being live and update START_LIVING. */
315 mark_pseudo_live (int regno
)
317 lra_assert (!HARD_REGISTER_NUM_P (regno
));
318 if (sparseset_bit_p (pseudos_live
, regno
))
321 sparseset_set_bit (pseudos_live
, regno
);
322 sparseset_set_bit (start_living
, regno
);
325 /* Mark pseudo REGNO as now being dead and update START_DYING. */
327 mark_pseudo_dead (int regno
)
329 lra_assert (!HARD_REGISTER_NUM_P (regno
));
330 IOR_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
, hard_regs_live
);
331 if (!sparseset_bit_p (pseudos_live
, regno
))
334 sparseset_clear_bit (pseudos_live
, regno
);
335 sparseset_set_bit (start_dying
, regno
);
338 /* Mark register REGNO (pseudo or hard register) in MODE as being live
339 and update BB_GEN_PSEUDOS. */
341 mark_regno_live (int regno
, machine_mode mode
)
345 if (HARD_REGISTER_NUM_P (regno
))
347 for (last
= end_hard_regno (mode
, regno
); regno
< last
; regno
++)
348 make_hard_regno_live (regno
);
352 mark_pseudo_live (regno
);
353 bitmap_set_bit (bb_gen_pseudos
, regno
);
358 /* Mark register REGNO (pseudo or hard register) in MODE as being dead
359 and update BB_GEN_PSEUDOS and BB_KILLED_PSEUDOS. */
361 mark_regno_dead (int regno
, machine_mode mode
)
365 if (HARD_REGISTER_NUM_P (regno
))
367 for (last
= end_hard_regno (mode
, regno
); regno
< last
; regno
++)
368 make_hard_regno_dead (regno
);
372 mark_pseudo_dead (regno
);
373 bitmap_clear_bit (bb_gen_pseudos
, regno
);
374 bitmap_set_bit (bb_killed_pseudos
, regno
);
380 /* This page contains code for making global live analysis of pseudos.
381 The code works only when pseudo live info is changed on a BB
382 border. That might be a consequence of some global transformations
383 in LRA, e.g. PIC pseudo reuse or rematerialization. */
385 /* Structure describing local BB data used for pseudo
387 class bb_data_pseudos
390 /* Basic block about which the below data are. */
392 bitmap_head killed_pseudos
; /* pseudos killed in the BB. */
393 bitmap_head gen_pseudos
; /* pseudos generated in the BB. */
396 /* Array for all BB data. Indexed by the corresponding BB index. */
397 typedef class bb_data_pseudos
*bb_data_t
;
399 /* All basic block data are referred through the following array. */
400 static bb_data_t bb_data
;
402 /* Two small functions for access to the bb data. */
403 static inline bb_data_t
404 get_bb_data (basic_block bb
)
406 return &bb_data
[(bb
)->index
];
409 static inline bb_data_t
410 get_bb_data_by_index (int index
)
412 return &bb_data
[index
];
415 /* Bitmap with all hard regs. */
416 static bitmap_head all_hard_regs_bitmap
;
418 /* The transfer function used by the DF equation solver to propagate
419 live info through block with BB_INDEX according to the following
422 bb.livein = (bb.liveout - bb.kill) OR bb.gen
425 live_trans_fun (int bb_index
)
427 basic_block bb
= get_bb_data_by_index (bb_index
)->bb
;
428 bitmap bb_liveout
= df_get_live_out (bb
);
429 bitmap bb_livein
= df_get_live_in (bb
);
430 bb_data_t bb_info
= get_bb_data (bb
);
432 bitmap_and_compl (&temp_bitmap
, bb_liveout
, &all_hard_regs_bitmap
);
433 return bitmap_ior_and_compl (bb_livein
, &bb_info
->gen_pseudos
,
434 &temp_bitmap
, &bb_info
->killed_pseudos
);
437 /* The confluence function used by the DF equation solver to set up
438 live info for a block BB without predecessor. */
440 live_con_fun_0 (basic_block bb
)
442 bitmap_and_into (df_get_live_out (bb
), &all_hard_regs_bitmap
);
445 /* The confluence function used by the DF equation solver to propagate
446 live info from successor to predecessor on edge E according to the
449 bb.liveout = 0 for entry block | OR (livein of successors)
452 live_con_fun_n (edge e
)
454 basic_block bb
= e
->src
;
455 basic_block dest
= e
->dest
;
456 bitmap bb_liveout
= df_get_live_out (bb
);
457 bitmap dest_livein
= df_get_live_in (dest
);
459 return bitmap_ior_and_compl_into (bb_liveout
,
460 dest_livein
, &all_hard_regs_bitmap
);
463 /* Indexes of all function blocks. */
464 static bitmap_head all_blocks
;
466 /* Allocate and initialize data needed for global pseudo live
469 initiate_live_solver (void)
471 bitmap_initialize (&all_hard_regs_bitmap
, ®_obstack
);
472 bitmap_set_range (&all_hard_regs_bitmap
, 0, FIRST_PSEUDO_REGISTER
);
473 bb_data
= XNEWVEC (class bb_data_pseudos
, last_basic_block_for_fn (cfun
));
474 bitmap_initialize (&all_blocks
, ®_obstack
);
477 FOR_ALL_BB_FN (bb
, cfun
)
479 bb_data_t bb_info
= get_bb_data (bb
);
481 bitmap_initialize (&bb_info
->killed_pseudos
, ®_obstack
);
482 bitmap_initialize (&bb_info
->gen_pseudos
, ®_obstack
);
483 bitmap_set_bit (&all_blocks
, bb
->index
);
487 /* Free all data needed for global pseudo live analysis. */
489 finish_live_solver (void)
493 bitmap_clear (&all_blocks
);
494 FOR_ALL_BB_FN (bb
, cfun
)
496 bb_data_t bb_info
= get_bb_data (bb
);
497 bitmap_clear (&bb_info
->killed_pseudos
);
498 bitmap_clear (&bb_info
->gen_pseudos
);
501 bitmap_clear (&all_hard_regs_bitmap
);
506 /* Insn currently scanned. */
507 static rtx_insn
*curr_insn
;
509 static lra_insn_recog_data_t curr_id
;
510 /* The insn static data. */
511 static struct lra_static_insn_data
*curr_static_id
;
513 /* Vec containing execution frequencies of program points. */
514 static vec
<int> point_freq_vec
;
516 /* The start of the above vector elements. */
519 /* Increment the current program point POINT to the next point which has
520 execution frequency FREQ. */
522 next_program_point (int &point
, int freq
)
524 point_freq_vec
.safe_push (freq
);
525 lra_point_freq
= point_freq_vec
.address ();
529 /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
531 lra_setup_reload_pseudo_preferenced_hard_reg (int regno
,
532 int hard_regno
, int profit
)
534 lra_assert (regno
>= lra_constraint_new_regno_start
);
535 if (lra_reg_info
[regno
].preferred_hard_regno1
== hard_regno
)
536 lra_reg_info
[regno
].preferred_hard_regno_profit1
+= profit
;
537 else if (lra_reg_info
[regno
].preferred_hard_regno2
== hard_regno
)
538 lra_reg_info
[regno
].preferred_hard_regno_profit2
+= profit
;
539 else if (lra_reg_info
[regno
].preferred_hard_regno1
< 0)
541 lra_reg_info
[regno
].preferred_hard_regno1
= hard_regno
;
542 lra_reg_info
[regno
].preferred_hard_regno_profit1
= profit
;
544 else if (lra_reg_info
[regno
].preferred_hard_regno2
< 0
545 || profit
> lra_reg_info
[regno
].preferred_hard_regno_profit2
)
547 lra_reg_info
[regno
].preferred_hard_regno2
= hard_regno
;
548 lra_reg_info
[regno
].preferred_hard_regno_profit2
= profit
;
552 /* Keep the 1st hard regno as more profitable. */
553 if (lra_reg_info
[regno
].preferred_hard_regno1
>= 0
554 && lra_reg_info
[regno
].preferred_hard_regno2
>= 0
555 && (lra_reg_info
[regno
].preferred_hard_regno_profit2
556 > lra_reg_info
[regno
].preferred_hard_regno_profit1
))
558 std::swap (lra_reg_info
[regno
].preferred_hard_regno1
,
559 lra_reg_info
[regno
].preferred_hard_regno2
);
560 std::swap (lra_reg_info
[regno
].preferred_hard_regno_profit1
,
561 lra_reg_info
[regno
].preferred_hard_regno_profit2
);
563 if (lra_dump_file
!= NULL
)
565 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno1
) >= 0)
566 fprintf (lra_dump_file
,
567 " Hard reg %d is preferable by r%d with profit %d\n",
569 lra_reg_info
[regno
].preferred_hard_regno_profit1
);
570 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno2
) >= 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_profit2
);
578 /* Check that REGNO living through calls and setjumps, set up conflict
579 regs using LAST_CALL_USED_REG_SET, and clear corresponding bits in
580 PSEUDOS_LIVE_THROUGH_CALLS and PSEUDOS_LIVE_THROUGH_SETJUMPS.
581 CALL_INSN is a call that is representative of all calls in the region
582 described by the PSEUDOS_LIVE_THROUGH_* sets, in terms of the registers
583 that it preserves and clobbers. */
586 check_pseudos_live_through_calls (int regno
,
587 HARD_REG_SET last_call_used_reg_set
,
591 rtx_insn
*old_call_insn
;
593 if (! sparseset_bit_p (pseudos_live_through_calls
, regno
))
596 gcc_assert (call_insn
&& CALL_P (call_insn
));
597 old_call_insn
= lra_reg_info
[regno
].call_insn
;
599 || (targetm
.return_call_with_max_clobbers
600 && targetm
.return_call_with_max_clobbers (old_call_insn
, call_insn
)
602 lra_reg_info
[regno
].call_insn
= call_insn
;
604 sparseset_clear_bit (pseudos_live_through_calls
, regno
);
605 IOR_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
,
606 last_call_used_reg_set
);
608 for (hr
= 0; HARD_REGISTER_NUM_P (hr
); hr
++)
609 if (targetm
.hard_regno_call_part_clobbered (call_insn
, hr
,
610 PSEUDO_REGNO_MODE (regno
)))
611 add_to_hard_reg_set (&lra_reg_info
[regno
].conflict_hard_regs
,
612 PSEUDO_REGNO_MODE (regno
), hr
);
613 if (! sparseset_bit_p (pseudos_live_through_setjumps
, regno
))
615 sparseset_clear_bit (pseudos_live_through_setjumps
, regno
);
616 /* Don't allocate pseudos that cross setjmps or any call, if this
617 function receives a nonlocal goto. */
618 SET_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
);
621 /* Return true if insn REG is an early clobber operand in alternative
622 NALT. Negative NALT means that we don't know the current insn
623 alternative. So assume the worst. */
625 reg_early_clobber_p (const struct lra_insn_reg
*reg
, int n_alt
)
627 return (n_alt
== LRA_UNKNOWN_ALT
628 ? reg
->early_clobber_alts
!= 0
629 : (n_alt
!= LRA_NON_CLOBBERED_ALT
630 && TEST_BIT (reg
->early_clobber_alts
, n_alt
)));
633 /* Return true if call instructions CALL1 and CALL2 use ABIs that
634 preserve the same set of registers. */
637 calls_have_same_clobbers_p (rtx_insn
*call1
, rtx_insn
*call2
)
639 if (!targetm
.return_call_with_max_clobbers
)
642 return (targetm
.return_call_with_max_clobbers (call1
, call2
) == call1
643 && targetm
.return_call_with_max_clobbers (call2
, call1
) == call2
);
646 /* Process insns of the basic block BB to update pseudo live ranges,
647 pseudo hard register conflicts, and insn notes. We do it on
648 backward scan of BB insns. CURR_POINT is the program point where
649 BB ends. The function updates this counter and returns in
650 CURR_POINT the program point where BB starts. The function also
651 does local live info updates and can delete the dead insns if
652 DEAD_INSN_P. It returns true if pseudo live info was
653 changed at the BB start. */
655 process_bb_lives (basic_block bb
, int &curr_point
, bool dead_insn_p
)
664 bool need_curr_point_incr
;
665 HARD_REG_SET last_call_used_reg_set
;
666 rtx_insn
*call_insn
= NULL
;
667 rtx_insn
*last_call_insn
= NULL
;
669 reg_live_out
= df_get_live_out (bb
);
670 sparseset_clear (pseudos_live
);
671 sparseset_clear (pseudos_live_through_calls
);
672 sparseset_clear (pseudos_live_through_setjumps
);
673 CLEAR_HARD_REG_SET (last_call_used_reg_set
);
674 REG_SET_TO_HARD_REG_SET (hard_regs_live
, reg_live_out
);
675 AND_COMPL_HARD_REG_SET (hard_regs_live
, eliminable_regset
);
676 EXECUTE_IF_SET_IN_BITMAP (reg_live_out
, FIRST_PSEUDO_REGISTER
, j
, bi
)
678 update_pseudo_point (j
, curr_point
, USE_POINT
);
679 mark_pseudo_live (j
);
682 bb_gen_pseudos
= &get_bb_data (bb
)->gen_pseudos
;
683 bb_killed_pseudos
= &get_bb_data (bb
)->killed_pseudos
;
684 bitmap_clear (bb_gen_pseudos
);
685 bitmap_clear (bb_killed_pseudos
);
686 freq
= REG_FREQ_FROM_BB (bb
);
688 if (lra_dump_file
!= NULL
)
689 fprintf (lra_dump_file
, " BB %d\n", bb
->index
);
691 /* Scan the code of this basic block, noting which pseudos and hard
692 regs are born or die.
694 Note that this loop treats uninitialized values as live until the
695 beginning of the block. For example, if an instruction uses
696 (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
697 FOO will remain live until the beginning of the block. Likewise
698 if FOO is not set at all. This is unnecessarily pessimistic, but
699 it probably doesn't matter much in practice. */
700 FOR_BB_INSNS_REVERSE_SAFE (bb
, curr_insn
, next
)
703 int n_alt
, dst_regno
, src_regno
;
705 struct lra_insn_reg
*reg
, *hr
;
707 if (!NONDEBUG_INSN_P (curr_insn
))
710 curr_id
= lra_get_insn_recog_data (curr_insn
);
711 curr_static_id
= curr_id
->insn_static_data
;
712 n_alt
= curr_id
->used_insn_alternative
;
713 if (lra_dump_file
!= NULL
)
714 fprintf (lra_dump_file
, " Insn %u: point = %d, n_alt = %d\n",
715 INSN_UID (curr_insn
), curr_point
, n_alt
);
717 set
= single_set (curr_insn
);
719 if (dead_insn_p
&& set
!= NULL_RTX
720 && REG_P (SET_DEST (set
)) && !HARD_REGISTER_P (SET_DEST (set
))
721 && find_reg_note (curr_insn
, REG_EH_REGION
, NULL_RTX
) == NULL_RTX
722 && ! may_trap_p (PATTERN (curr_insn
))
723 /* Don't do premature remove of pic offset pseudo as we can
724 start to use it after some reload generation. */
725 && (pic_offset_table_rtx
== NULL_RTX
726 || pic_offset_table_rtx
!= SET_DEST (set
)))
728 bool remove_p
= true;
730 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
731 if (reg
->type
!= OP_IN
&& sparseset_bit_p (pseudos_live
, reg
->regno
))
736 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
737 if (reg
->type
!= OP_IN
&& !reg
->clobber_high
)
743 if (remove_p
&& ! volatile_refs_p (PATTERN (curr_insn
)))
745 dst_regno
= REGNO (SET_DEST (set
));
746 if (lra_dump_file
!= NULL
)
747 fprintf (lra_dump_file
, " Deleting dead insn %u\n",
748 INSN_UID (curr_insn
));
749 lra_set_insn_deleted (curr_insn
);
750 if (lra_reg_info
[dst_regno
].nrefs
== 0)
752 /* There might be some debug insns with the pseudo. */
756 bitmap_copy (&temp_bitmap
, &lra_reg_info
[dst_regno
].insn_bitmap
);
757 EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap
, 0, uid
, bi
)
759 insn
= lra_insn_recog_data
[uid
]->insn
;
760 lra_substitute_pseudo_within_insn (insn
, dst_regno
,
761 SET_SRC (set
), true);
762 lra_update_insn_regno_info (insn
);
769 /* Update max ref width and hard reg usage. */
770 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
772 int i
, regno
= reg
->regno
;
774 if (partial_subreg_p (lra_reg_info
[regno
].biggest_mode
,
776 lra_reg_info
[regno
].biggest_mode
= reg
->biggest_mode
;
777 if (HARD_REGISTER_NUM_P (regno
))
779 lra_hard_reg_usage
[regno
] += freq
;
780 /* A hard register explicitly can be used in small mode,
781 but implicitly it can be used in natural mode as a
782 part of multi-register group. Process this case
784 for (i
= 1; i
< hard_regno_nregs (regno
, reg
->biggest_mode
); i
++)
785 if (partial_subreg_p (lra_reg_info
[regno
+ i
].biggest_mode
,
786 GET_MODE (regno_reg_rtx
[regno
+ i
])))
787 lra_reg_info
[regno
+ i
].biggest_mode
788 = GET_MODE (regno_reg_rtx
[regno
+ i
]);
792 call_p
= CALL_P (curr_insn
);
794 /* If we have a simple register copy and the source reg is live after
795 this instruction, then remove the source reg from the live set so
796 that it will not conflict with the destination reg. */
797 rtx ignore_reg
= non_conflicting_reg_copy_p (curr_insn
);
798 if (ignore_reg
!= NULL_RTX
)
800 int ignore_regno
= REGNO (ignore_reg
);
801 if (HARD_REGISTER_NUM_P (ignore_regno
)
802 && TEST_HARD_REG_BIT (hard_regs_live
, ignore_regno
))
803 CLEAR_HARD_REG_BIT (hard_regs_live
, ignore_regno
);
804 else if (!HARD_REGISTER_NUM_P (ignore_regno
)
805 && sparseset_bit_p (pseudos_live
, ignore_regno
))
806 sparseset_clear_bit (pseudos_live
, ignore_regno
);
808 /* We don't need any special handling of the source reg if
809 it is dead after this instruction. */
810 ignore_reg
= NULL_RTX
;
813 src_regno
= (set
!= NULL_RTX
&& REG_P (SET_SRC (set
))
814 ? REGNO (SET_SRC (set
)) : -1);
815 dst_regno
= (set
!= NULL_RTX
&& REG_P (SET_DEST (set
))
816 ? REGNO (SET_DEST (set
)) : -1);
818 && src_regno
>= 0 && dst_regno
>= 0
819 /* Check that source regno does not conflict with
820 destination regno to exclude most impossible
822 && (((!HARD_REGISTER_NUM_P (src_regno
)
823 && (! sparseset_bit_p (pseudos_live
, src_regno
)
824 || (!HARD_REGISTER_NUM_P (dst_regno
)
825 && lra_reg_val_equal_p (src_regno
,
826 lra_reg_info
[dst_regno
].val
,
827 lra_reg_info
[dst_regno
].offset
))))
828 || (HARD_REGISTER_NUM_P (src_regno
)
829 && ! TEST_HARD_REG_BIT (hard_regs_live
, src_regno
)))
830 /* It might be 'inheritance pseudo <- reload pseudo'. */
831 || (src_regno
>= lra_constraint_new_regno_start
832 && dst_regno
>= lra_constraint_new_regno_start
833 /* Remember to skip special cases where src/dest regnos are
834 the same, e.g. insn SET pattern has matching constraints
836 && src_regno
!= dst_regno
)))
838 int hard_regno
= -1, regno
= -1;
840 if (dst_regno
>= lra_constraint_new_regno_start
841 && src_regno
>= lra_constraint_new_regno_start
)
843 /* It might be still an original (non-reload) insn with
844 one unused output and a constraint requiring to use
845 the same reg for input/output operands. In this case
846 dst_regno and src_regno have the same value, we don't
847 need a misleading copy for this case. */
848 if (dst_regno
!= src_regno
)
849 lra_create_copy (dst_regno
, src_regno
, freq
);
851 else if (dst_regno
>= lra_constraint_new_regno_start
)
853 if (!HARD_REGISTER_NUM_P (hard_regno
= src_regno
))
854 hard_regno
= reg_renumber
[src_regno
];
857 else if (src_regno
>= lra_constraint_new_regno_start
)
859 if (!HARD_REGISTER_NUM_P (hard_regno
= dst_regno
))
860 hard_regno
= reg_renumber
[dst_regno
];
863 if (regno
>= 0 && hard_regno
>= 0)
864 lra_setup_reload_pseudo_preferenced_hard_reg
865 (regno
, hard_regno
, freq
);
868 sparseset_clear (start_living
);
870 /* Mark each defined value as live. We need to do this for
871 unused values because they still conflict with quantities
872 that are live at the time of the definition. */
873 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
875 if (reg
->type
!= OP_IN
)
877 update_pseudo_point (reg
->regno
, curr_point
, USE_POINT
);
878 mark_regno_live (reg
->regno
, reg
->biggest_mode
);
879 check_pseudos_live_through_calls (reg
->regno
,
880 last_call_used_reg_set
,
884 if (!HARD_REGISTER_NUM_P (reg
->regno
))
885 for (hr
= curr_static_id
->hard_regs
; hr
!= NULL
; hr
= hr
->next
)
887 && maybe_gt (GET_MODE_SIZE (PSEUDO_REGNO_MODE (reg
->regno
)),
888 GET_MODE_SIZE (hr
->biggest_mode
)))
889 SET_HARD_REG_BIT (lra_reg_info
[reg
->regno
].conflict_hard_regs
,
893 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
894 if (reg
->type
!= OP_IN
)
895 make_hard_regno_live (reg
->regno
);
897 if (curr_id
->arg_hard_regs
!= NULL
)
898 for (i
= 0; (regno
= curr_id
->arg_hard_regs
[i
]) >= 0; i
++)
899 if (!HARD_REGISTER_NUM_P (regno
))
900 /* It is a clobber. */
901 make_hard_regno_live (regno
- FIRST_PSEUDO_REGISTER
);
903 sparseset_copy (unused_set
, start_living
);
905 sparseset_clear (start_dying
);
907 /* See which defined values die here. */
908 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
909 if (reg
->type
!= OP_IN
910 && ! reg_early_clobber_p (reg
, n_alt
) && ! reg
->subreg_p
)
912 if (reg
->type
== OP_OUT
)
913 update_pseudo_point (reg
->regno
, curr_point
, DEF_POINT
);
914 mark_regno_dead (reg
->regno
, reg
->biggest_mode
);
917 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
918 if (reg
->type
!= OP_IN
919 && ! reg_early_clobber_p (reg
, n_alt
) && ! reg
->subreg_p
)
920 make_hard_regno_dead (reg
->regno
);
922 if (curr_id
->arg_hard_regs
!= NULL
)
923 for (i
= 0; (regno
= curr_id
->arg_hard_regs
[i
]) >= 0; i
++)
924 if (!HARD_REGISTER_NUM_P (regno
))
925 /* It is a clobber. */
926 make_hard_regno_dead (regno
- FIRST_PSEUDO_REGISTER
);
930 call_insn
= curr_insn
;
931 if (! flag_ipa_ra
&& ! targetm
.return_call_with_max_clobbers
)
932 COPY_HARD_REG_SET(last_call_used_reg_set
, call_used_reg_set
);
935 HARD_REG_SET this_call_used_reg_set
;
936 get_call_reg_set_usage (curr_insn
, &this_call_used_reg_set
,
939 bool flush
= (! hard_reg_set_empty_p (last_call_used_reg_set
)
940 && ( ! hard_reg_set_equal_p (last_call_used_reg_set
,
941 this_call_used_reg_set
)))
942 || (last_call_insn
&& ! calls_have_same_clobbers_p
946 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, j
)
948 IOR_HARD_REG_SET (lra_reg_info
[j
].actual_call_used_reg_set
,
949 this_call_used_reg_set
);
952 check_pseudos_live_through_calls (j
,
953 last_call_used_reg_set
,
956 COPY_HARD_REG_SET(last_call_used_reg_set
, this_call_used_reg_set
);
957 last_call_insn
= call_insn
;
960 sparseset_ior (pseudos_live_through_calls
,
961 pseudos_live_through_calls
, pseudos_live
);
962 if (cfun
->has_nonlocal_label
963 || (!targetm
.setjmp_preserves_nonvolatile_regs_p ()
964 && (find_reg_note (curr_insn
, REG_SETJMP
, NULL_RTX
)
966 sparseset_ior (pseudos_live_through_setjumps
,
967 pseudos_live_through_setjumps
, pseudos_live
);
970 /* Increment the current program point if we must. */
971 if (sparseset_contains_pseudos_p (unused_set
)
972 || sparseset_contains_pseudos_p (start_dying
))
973 next_program_point (curr_point
, freq
);
975 /* If we removed the source reg from a simple register copy from the
976 live set above, then add it back now so we don't accidentally add
977 it to the start_living set below. */
978 if (ignore_reg
!= NULL_RTX
)
980 int ignore_regno
= REGNO (ignore_reg
);
981 if (HARD_REGISTER_NUM_P (ignore_regno
))
982 SET_HARD_REG_BIT (hard_regs_live
, ignore_regno
);
984 sparseset_set_bit (pseudos_live
, ignore_regno
);
987 sparseset_clear (start_living
);
989 /* Mark each used value as live. */
990 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
991 if (reg
->type
!= OP_OUT
)
993 if (reg
->type
== OP_IN
)
994 update_pseudo_point (reg
->regno
, curr_point
, USE_POINT
);
995 mark_regno_live (reg
->regno
, reg
->biggest_mode
);
996 check_pseudos_live_through_calls (reg
->regno
,
997 last_call_used_reg_set
,
1001 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1002 if (reg
->type
!= OP_OUT
)
1003 make_hard_regno_live (reg
->regno
);
1005 if (curr_id
->arg_hard_regs
!= NULL
)
1006 /* Make argument hard registers live. */
1007 for (i
= 0; (regno
= curr_id
->arg_hard_regs
[i
]) >= 0; i
++)
1008 if (HARD_REGISTER_NUM_P (regno
))
1009 make_hard_regno_live (regno
);
1011 sparseset_and_compl (dead_set
, start_living
, start_dying
);
1013 sparseset_clear (start_dying
);
1015 /* Mark early clobber outputs dead. */
1016 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1017 if (reg
->type
!= OP_IN
1018 && reg_early_clobber_p (reg
, n_alt
) && ! reg
->subreg_p
)
1020 if (reg
->type
== OP_OUT
)
1021 update_pseudo_point (reg
->regno
, curr_point
, DEF_POINT
);
1022 mark_regno_dead (reg
->regno
, reg
->biggest_mode
);
1024 /* We're done processing inputs, so make sure early clobber
1025 operands that are both inputs and outputs are still live. */
1026 if (reg
->type
== OP_INOUT
)
1027 mark_regno_live (reg
->regno
, reg
->biggest_mode
);
1030 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1031 if (reg
->type
!= OP_IN
1032 && reg_early_clobber_p (reg
, n_alt
) && ! reg
->subreg_p
)
1034 struct lra_insn_reg
*reg2
;
1036 /* We can have early clobbered non-operand hard reg and
1037 the same hard reg as an insn input. Don't make hard
1038 reg dead before the insns. */
1039 for (reg2
= curr_id
->regs
; reg2
!= NULL
; reg2
= reg2
->next
)
1040 if (reg2
->type
!= OP_OUT
&& reg2
->regno
== reg
->regno
)
1043 make_hard_regno_dead (reg
->regno
);
1046 /* Increment the current program point if we must. */
1047 if (sparseset_contains_pseudos_p (dead_set
)
1048 || sparseset_contains_pseudos_p (start_dying
))
1049 next_program_point (curr_point
, freq
);
1052 for (link_loc
= ®_NOTES (curr_insn
); (link
= *link_loc
) != NULL_RTX
;)
1054 if (REG_NOTE_KIND (link
) != REG_DEAD
1055 && REG_NOTE_KIND (link
) != REG_UNUSED
)
1057 else if (REG_P (XEXP (link
, 0)))
1059 regno
= REGNO (XEXP (link
, 0));
1060 if ((REG_NOTE_KIND (link
) == REG_DEAD
1061 && ! sparseset_bit_p (dead_set
, regno
))
1062 || (REG_NOTE_KIND (link
) == REG_UNUSED
1063 && ! sparseset_bit_p (unused_set
, regno
)))
1065 *link_loc
= XEXP (link
, 1);
1068 if (REG_NOTE_KIND (link
) == REG_DEAD
)
1069 sparseset_clear_bit (dead_set
, regno
);
1070 else if (REG_NOTE_KIND (link
) == REG_UNUSED
)
1071 sparseset_clear_bit (unused_set
, regno
);
1073 link_loc
= &XEXP (link
, 1);
1075 EXECUTE_IF_SET_IN_SPARSESET (dead_set
, j
)
1076 add_reg_note (curr_insn
, REG_DEAD
, regno_reg_rtx
[j
]);
1077 EXECUTE_IF_SET_IN_SPARSESET (unused_set
, j
)
1078 add_reg_note (curr_insn
, REG_UNUSED
, regno_reg_rtx
[j
]);
1081 if (bb_has_eh_pred (bb
))
1084 unsigned int regno
= EH_RETURN_DATA_REGNO (j
);
1086 if (regno
== INVALID_REGNUM
)
1088 make_hard_regno_live (regno
);
1091 /* Pseudos can't go in stack regs at the start of a basic block that
1092 is reached by an abnormal edge. Likewise for call clobbered regs,
1093 because caller-save, fixup_abnormal_edges and possibly the table
1094 driven EH machinery are not quite ready to handle such pseudos
1095 live across such edges. */
1096 if (bb_has_abnormal_pred (bb
))
1099 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, px
)
1100 lra_reg_info
[px
].no_stack_p
= true;
1101 for (px
= FIRST_STACK_REG
; px
<= LAST_STACK_REG
; px
++)
1102 make_hard_regno_live (px
);
1104 /* No need to record conflicts for call clobbered regs if we
1105 have nonlocal labels around, as we don't ever try to
1106 allocate such regs in this case. */
1107 if (!cfun
->has_nonlocal_label
1108 && has_abnormal_call_or_eh_pred_edge_p (bb
))
1109 for (px
= 0; HARD_REGISTER_NUM_P (px
); px
++)
1110 if (call_used_regs
[px
]
1111 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
1112 /* We should create a conflict of PIC pseudo with PIC
1113 hard reg as PIC hard reg can have a wrong value after
1114 jump described by the abnormal edge. In this case we
1115 cannot allocate PIC hard reg to PIC pseudo as PIC
1116 pseudo will also have a wrong value. */
1117 || (px
== REAL_PIC_OFFSET_TABLE_REGNUM
1118 && pic_offset_table_rtx
!= NULL_RTX
1119 && !HARD_REGISTER_P (pic_offset_table_rtx
))
1122 make_hard_regno_live (px
);
1125 bool live_change_p
= false;
1126 /* Check if bb border live info was changed. */
1127 unsigned int live_pseudos_num
= 0;
1128 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb
),
1129 FIRST_PSEUDO_REGISTER
, j
, bi
)
1132 if (! sparseset_bit_p (pseudos_live
, j
))
1134 live_change_p
= true;
1135 if (lra_dump_file
!= NULL
)
1136 fprintf (lra_dump_file
,
1137 " r%d is removed as live at bb%d start\n", j
, bb
->index
);
1142 && sparseset_cardinality (pseudos_live
) != live_pseudos_num
)
1144 live_change_p
= true;
1145 if (lra_dump_file
!= NULL
)
1146 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, j
)
1147 if (! bitmap_bit_p (df_get_live_in (bb
), j
))
1148 fprintf (lra_dump_file
,
1149 " r%d is added to live at bb%d start\n", j
, bb
->index
);
1151 /* See if we'll need an increment at the end of this basic block.
1152 An increment is needed if the PSEUDOS_LIVE set is not empty,
1153 to make sure the finish points are set up correctly. */
1154 need_curr_point_incr
= (sparseset_cardinality (pseudos_live
) > 0);
1156 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, i
)
1158 update_pseudo_point (i
, curr_point
, DEF_POINT
);
1159 mark_pseudo_dead (i
);
1162 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb
), FIRST_PSEUDO_REGISTER
, j
, bi
)
1164 if (sparseset_cardinality (pseudos_live_through_calls
) == 0)
1166 if (sparseset_bit_p (pseudos_live_through_calls
, j
))
1167 check_pseudos_live_through_calls (j
, last_call_used_reg_set
, call_insn
);
1170 for (i
= 0; HARD_REGISTER_NUM_P (i
); ++i
)
1172 if (!TEST_HARD_REG_BIT (hard_regs_live
, i
))
1175 if (!TEST_HARD_REG_BIT (hard_regs_spilled_into
, i
))
1178 if (bitmap_bit_p (df_get_live_in (bb
), i
))
1181 live_change_p
= true;
1183 fprintf (lra_dump_file
,
1184 " hard reg r%d is added to live at bb%d start\n", i
,
1186 bitmap_set_bit (df_get_live_in (bb
), i
);
1189 if (need_curr_point_incr
)
1190 next_program_point (curr_point
, freq
);
1192 return live_change_p
;
1195 /* Compress pseudo live ranges by removing program points where
1196 nothing happens. Complexity of many algorithms in LRA is linear
1197 function of program points number. To speed up the code we try to
1198 minimize the number of the program points here. */
1200 remove_some_program_points_and_update_live_ranges (void)
1205 lra_live_range_t r
, prev_r
, next_r
;
1206 sbitmap_iterator sbi
;
1207 bool born_p
, dead_p
, prev_born_p
, prev_dead_p
;
1209 auto_sbitmap
born (lra_live_max_point
);
1210 auto_sbitmap
dead (lra_live_max_point
);
1211 bitmap_clear (born
);
1212 bitmap_clear (dead
);
1213 max_regno
= max_reg_num ();
1214 for (i
= FIRST_PSEUDO_REGISTER
; i
< (unsigned) max_regno
; i
++)
1216 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
1218 lra_assert (r
->start
<= r
->finish
);
1219 bitmap_set_bit (born
, r
->start
);
1220 bitmap_set_bit (dead
, r
->finish
);
1223 auto_sbitmap
born_or_dead (lra_live_max_point
);
1224 bitmap_ior (born_or_dead
, born
, dead
);
1225 map
= XCNEWVEC (int, lra_live_max_point
);
1227 prev_born_p
= prev_dead_p
= false;
1228 EXECUTE_IF_SET_IN_BITMAP (born_or_dead
, 0, i
, sbi
)
1230 born_p
= bitmap_bit_p (born
, i
);
1231 dead_p
= bitmap_bit_p (dead
, i
);
1232 if ((prev_born_p
&& ! prev_dead_p
&& born_p
&& ! dead_p
)
1233 || (prev_dead_p
&& ! prev_born_p
&& dead_p
&& ! born_p
))
1236 lra_point_freq
[n
] = MAX (lra_point_freq
[n
], lra_point_freq
[i
]);
1241 lra_point_freq
[n
] = lra_point_freq
[i
];
1243 prev_born_p
= born_p
;
1244 prev_dead_p
= dead_p
;
1247 if (lra_dump_file
!= NULL
)
1248 fprintf (lra_dump_file
, "Compressing live ranges: from %d to %d - %d%%\n",
1249 lra_live_max_point
, n
,
1250 lra_live_max_point
? 100 * n
/ lra_live_max_point
: 100);
1251 if (n
< lra_live_max_point
)
1253 lra_live_max_point
= n
;
1254 for (i
= FIRST_PSEUDO_REGISTER
; i
< (unsigned) max_regno
; i
++)
1256 for (prev_r
= NULL
, r
= lra_reg_info
[i
].live_ranges
;
1261 r
->start
= map
[r
->start
];
1262 r
->finish
= map
[r
->finish
];
1263 if (prev_r
== NULL
|| prev_r
->start
> r
->finish
+ 1)
1268 prev_r
->start
= r
->start
;
1269 prev_r
->next
= next_r
;
1270 lra_live_range_pool
.remove (r
);
1277 /* Print live ranges R to file F. */
1279 lra_print_live_range_list (FILE *f
, lra_live_range_t r
)
1281 for (; r
!= NULL
; r
= r
->next
)
1282 fprintf (f
, " [%d..%d]", r
->start
, r
->finish
);
1287 debug (lra_live_range
&ref
)
1289 lra_print_live_range_list (stderr
, &ref
);
1293 debug (lra_live_range
*ptr
)
1298 fprintf (stderr
, "<nil>\n");
1301 /* Print live ranges R to stderr. */
1303 lra_debug_live_range_list (lra_live_range_t r
)
1305 lra_print_live_range_list (stderr
, r
);
1308 /* Print live ranges of pseudo REGNO to file F. */
1310 print_pseudo_live_ranges (FILE *f
, int regno
)
1312 if (lra_reg_info
[regno
].live_ranges
== NULL
)
1314 fprintf (f
, " r%d:", regno
);
1315 lra_print_live_range_list (f
, lra_reg_info
[regno
].live_ranges
);
1318 /* Print live ranges of pseudo REGNO to stderr. */
1320 lra_debug_pseudo_live_ranges (int regno
)
1322 print_pseudo_live_ranges (stderr
, regno
);
1325 /* Print live ranges of all pseudos to file F. */
1327 print_live_ranges (FILE *f
)
1331 max_regno
= max_reg_num ();
1332 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1333 print_pseudo_live_ranges (f
, i
);
1336 /* Print live ranges of all pseudos to stderr. */
1338 lra_debug_live_ranges (void)
1340 print_live_ranges (stderr
);
1343 /* Compress pseudo live ranges. */
1345 compress_live_ranges (void)
1347 remove_some_program_points_and_update_live_ranges ();
1348 if (lra_dump_file
!= NULL
)
1350 fprintf (lra_dump_file
, "Ranges after the compression:\n");
1351 print_live_ranges (lra_dump_file
);
1357 /* The number of the current live range pass. */
1358 int lra_live_range_iter
;
1360 /* The function creates live ranges only for memory pseudos (or for
1361 all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos. It
1362 also does dead insn elimination if DEAD_INSN_P and global live
1363 analysis only for pseudos and only if the pseudo live info was
1364 changed on a BB border. Return TRUE if the live info was
1367 lra_create_live_ranges_1 (bool all_p
, bool dead_insn_p
)
1370 int i
, hard_regno
, max_regno
= max_reg_num ();
1372 bool bb_live_change_p
, have_referenced_pseudos
= false;
1374 timevar_push (TV_LRA_CREATE_LIVE_RANGES
);
1376 complete_info_p
= all_p
;
1377 if (lra_dump_file
!= NULL
)
1378 fprintf (lra_dump_file
,
1379 "\n********** Pseudo live ranges #%d: **********\n\n",
1380 ++lra_live_range_iter
);
1381 memset (lra_hard_reg_usage
, 0, sizeof (lra_hard_reg_usage
));
1382 for (i
= 0; i
< max_regno
; i
++)
1384 lra_reg_info
[i
].live_ranges
= NULL
;
1385 CLEAR_HARD_REG_SET (lra_reg_info
[i
].conflict_hard_regs
);
1386 lra_reg_info
[i
].preferred_hard_regno1
= -1;
1387 lra_reg_info
[i
].preferred_hard_regno2
= -1;
1388 lra_reg_info
[i
].preferred_hard_regno_profit1
= 0;
1389 lra_reg_info
[i
].preferred_hard_regno_profit2
= 0;
1391 lra_reg_info
[i
].no_stack_p
= false;
1393 /* The biggest mode is already set but its value might be to
1394 conservative because of recent transformation. Here in this
1395 file we recalculate it again as it costs practically
1397 if (!HARD_REGISTER_NUM_P (i
) && regno_reg_rtx
[i
] != NULL_RTX
)
1398 lra_reg_info
[i
].biggest_mode
= GET_MODE (regno_reg_rtx
[i
]);
1400 lra_reg_info
[i
].biggest_mode
= VOIDmode
;
1401 lra_reg_info
[i
].call_insn
= NULL
;
1402 if (!HARD_REGISTER_NUM_P (i
)
1403 && lra_reg_info
[i
].nrefs
!= 0)
1405 if ((hard_regno
= reg_renumber
[i
]) >= 0)
1406 lra_hard_reg_usage
[hard_regno
] += lra_reg_info
[i
].freq
;
1407 have_referenced_pseudos
= true;
1412 /* Under some circumstances, we can have functions without pseudo
1413 registers. For such functions, lra_live_max_point will be 0,
1414 see e.g. PR55604, and there's nothing more to do for us here. */
1415 if (! have_referenced_pseudos
)
1417 timevar_pop (TV_LRA_CREATE_LIVE_RANGES
);
1421 pseudos_live
= sparseset_alloc (max_regno
);
1422 pseudos_live_through_calls
= sparseset_alloc (max_regno
);
1423 pseudos_live_through_setjumps
= sparseset_alloc (max_regno
);
1424 start_living
= sparseset_alloc (max_regno
);
1425 start_dying
= sparseset_alloc (max_regno
);
1426 dead_set
= sparseset_alloc (max_regno
);
1427 unused_set
= sparseset_alloc (max_regno
);
1429 unsigned new_length
= get_max_uid () * 2;
1430 point_freq_vec
.truncate (0);
1431 point_freq_vec
.reserve_exact (new_length
);
1432 lra_point_freq
= point_freq_vec
.address ();
1433 auto_vec
<int, 20> post_order_rev_cfg
;
1434 inverted_post_order_compute (&post_order_rev_cfg
);
1435 lra_assert (post_order_rev_cfg
.length () == (unsigned) n_basic_blocks_for_fn (cfun
));
1436 bb_live_change_p
= false;
1437 for (i
= post_order_rev_cfg
.length () - 1; i
>= 0; --i
)
1439 bb
= BASIC_BLOCK_FOR_FN (cfun
, post_order_rev_cfg
[i
]);
1440 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
1441 == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1443 if (process_bb_lives (bb
, curr_point
, dead_insn_p
))
1444 bb_live_change_p
= true;
1446 if (bb_live_change_p
)
1448 /* We need to clear pseudo live info as some pseudos can
1449 disappear, e.g. pseudos with used equivalences. */
1450 FOR_EACH_BB_FN (bb
, cfun
)
1452 bitmap_clear_range (df_get_live_in (bb
), FIRST_PSEUDO_REGISTER
,
1453 max_regno
- FIRST_PSEUDO_REGISTER
);
1454 bitmap_clear_range (df_get_live_out (bb
), FIRST_PSEUDO_REGISTER
,
1455 max_regno
- FIRST_PSEUDO_REGISTER
);
1457 /* As we did not change CFG since LRA start we can use
1458 DF-infrastructure solver to solve live data flow problem. */
1459 for (int i
= 0; HARD_REGISTER_NUM_P (i
); ++i
)
1461 if (TEST_HARD_REG_BIT (hard_regs_spilled_into
, i
))
1462 bitmap_clear_bit (&all_hard_regs_bitmap
, i
);
1465 (DF_BACKWARD
, NULL
, live_con_fun_0
, live_con_fun_n
,
1466 live_trans_fun
, &all_blocks
,
1467 df_get_postorder (DF_BACKWARD
), df_get_n_blocks (DF_BACKWARD
));
1468 if (lra_dump_file
!= NULL
)
1470 fprintf (lra_dump_file
,
1471 "Global pseudo live data have been updated:\n");
1473 FOR_EACH_BB_FN (bb
, cfun
)
1475 bb_data_t bb_info
= get_bb_data (bb
);
1476 bitmap bb_livein
= df_get_live_in (bb
);
1477 bitmap bb_liveout
= df_get_live_out (bb
);
1479 fprintf (lra_dump_file
, "\nBB %d:\n", bb
->index
);
1480 lra_dump_bitmap_with_title (" gen:",
1481 &bb_info
->gen_pseudos
, bb
->index
);
1482 lra_dump_bitmap_with_title (" killed:",
1483 &bb_info
->killed_pseudos
, bb
->index
);
1484 lra_dump_bitmap_with_title (" livein:", bb_livein
, bb
->index
);
1485 lra_dump_bitmap_with_title (" liveout:", bb_liveout
, bb
->index
);
1489 lra_live_max_point
= curr_point
;
1490 if (lra_dump_file
!= NULL
)
1491 print_live_ranges (lra_dump_file
);
1493 sparseset_free (unused_set
);
1494 sparseset_free (dead_set
);
1495 sparseset_free (start_dying
);
1496 sparseset_free (start_living
);
1497 sparseset_free (pseudos_live_through_calls
);
1498 sparseset_free (pseudos_live_through_setjumps
);
1499 sparseset_free (pseudos_live
);
1500 compress_live_ranges ();
1501 timevar_pop (TV_LRA_CREATE_LIVE_RANGES
);
1502 return bb_live_change_p
;
1505 /* The main entry function creates live-ranges and other live info
1506 necessary for the assignment sub-pass. It uses
1507 lra_creates_live_ranges_1 -- so read comments for the
1510 lra_create_live_ranges (bool all_p
, bool dead_insn_p
)
1512 if (! lra_create_live_ranges_1 (all_p
, dead_insn_p
))
1514 if (lra_dump_file
!= NULL
)
1515 fprintf (lra_dump_file
, "Live info was changed -- recalculate it\n");
1516 /* Live info was changed on a bb border. It means that some info,
1517 e.g. about conflict regs, calls crossed, and live ranges may be
1518 wrong. We need this info for allocation. So recalculate it
1519 again but without removing dead insns which can change live info
1520 again. Repetitive live range calculations are expensive therefore
1521 we stop here as we already have correct info although some
1522 improvement in rare cases could be possible on this sub-pass if
1523 we do dead insn elimination again (still the improvement may
1525 lra_clear_live_ranges ();
1526 bool res
= lra_create_live_ranges_1 (all_p
, false);
1530 /* Finish all live ranges. */
1532 lra_clear_live_ranges (void)
1536 for (i
= 0; i
< max_reg_num (); i
++)
1537 free_live_range_list (lra_reg_info
[i
].live_ranges
);
1538 point_freq_vec
.release ();
1541 /* Initialize live ranges data once per function. */
1543 lra_live_ranges_init (void)
1545 bitmap_initialize (&temp_bitmap
, ®_obstack
);
1546 initiate_live_solver ();
1549 /* Finish live ranges data once per function. */
1551 lra_live_ranges_finish (void)
1553 finish_live_solver ();
1554 bitmap_clear (&temp_bitmap
);
1555 lra_live_range_pool
.release ();