1 /* Build live ranges for pseudos.
2 Copyright (C) 2010-2015 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
22 /* This file contains code to build pseudo live-ranges (analogous
23 structures used in IRA, so read comments about the live-ranges
24 there) and other info necessary for other passes to assign
25 hard-registers to pseudos, coalesce the spilled pseudos, and assign
26 stack memory slots to spilled pseudos. */
30 #include "coretypes.h"
32 #include "hard-reg-set.h"
35 #include "insn-config.h"
47 #include "statistics.h"
48 #include "double-int.h"
50 #include "fixed-value.h"
64 #include "dominance.h"
67 #include "basic-block.h"
71 #include "sparseset.h"
74 /* Program points are enumerated by numbers from range
75 0..LRA_LIVE_MAX_POINT-1. There are approximately two times more
76 program points than insns. Program points are places in the
77 program where liveness info can be changed. In most general case
78 (there are more complicated cases too) some program points
79 correspond to places where input operand dies and other ones
80 correspond to places where output operands are born. */
81 int lra_live_max_point
;
83 /* Accumulated execution frequency of all references for each hard
85 int lra_hard_reg_usage
[FIRST_PSEUDO_REGISTER
];
87 /* A global flag whose true value says to build live ranges for all
88 pseudos, otherwise the live ranges only for pseudos got memory is
89 build. True value means also building copies and setting up hard
90 register preferences. The complete info is necessary only for the
91 assignment pass. The complete info is not needed for the
92 coalescing and spill passes. */
93 static bool complete_info_p
;
95 /* Pseudos live at current point in the RTL scan. */
96 static sparseset pseudos_live
;
98 /* Pseudos probably living through calls and setjumps. As setjump is
99 a call too, if a bit in PSEUDOS_LIVE_THROUGH_SETJUMPS is set up
100 then the corresponding bit in PSEUDOS_LIVE_THROUGH_CALLS is set up
101 too. These data are necessary for cases when only one subreg of a
102 multi-reg pseudo is set up after a call. So we decide it is
103 probably live when traversing bb backward. We are sure about
104 living when we see its usage or definition of the pseudo. */
105 static sparseset pseudos_live_through_calls
;
106 static sparseset pseudos_live_through_setjumps
;
108 /* Set of hard regs (except eliminable ones) currently live. */
109 static HARD_REG_SET hard_regs_live
;
111 /* Set of pseudos and hard registers start living/dying in the current
112 insn. These sets are used to update REG_DEAD and REG_UNUSED notes
114 static sparseset start_living
, start_dying
;
116 /* Set of pseudos and hard regs dead and unused in the current
118 static sparseset unused_set
, dead_set
;
120 /* Bitmap used for holding intermediate bitmap operation results. */
121 static bitmap_head temp_bitmap
;
123 /* Pool for pseudo live ranges. */
124 pool_allocator
<lra_live_range
> lra_live_range::pool ("live ranges", 100);
126 /* Free live range list LR. */
128 free_live_range_list (lra_live_range_t lr
)
130 lra_live_range_t next
;
140 /* Create and return pseudo live range with given attributes. */
141 static lra_live_range_t
142 create_live_range (int regno
, int start
, int finish
, lra_live_range_t next
)
144 lra_live_range_t p
= new lra_live_range
;
152 /* Copy live range R and return the result. */
153 static lra_live_range_t
154 copy_live_range (lra_live_range_t r
)
156 return new lra_live_range (*r
);
159 /* Copy live range list given by its head R and return the result. */
161 lra_copy_live_range_list (lra_live_range_t r
)
163 lra_live_range_t p
, first
, *chain
;
166 for (chain
= &first
; r
!= NULL
; r
= r
->next
)
168 p
= copy_live_range (r
);
175 /* Merge *non-intersected* ranges R1 and R2 and returns the result.
176 The function maintains the order of ranges and tries to minimize
177 size of the result range list. Ranges R1 and R2 may not be used
180 lra_merge_live_ranges (lra_live_range_t r1
, lra_live_range_t r2
)
182 lra_live_range_t first
, last
;
188 for (first
= last
= NULL
; r1
!= NULL
&& r2
!= NULL
;)
190 if (r1
->start
< r2
->start
)
193 if (r1
->start
== r2
->finish
+ 1)
195 /* Joint ranges: merge r1 and r2 into r1. */
196 r1
->start
= r2
->start
;
197 lra_live_range_t temp
= r2
;
203 gcc_assert (r2
->finish
+ 1 < r1
->start
);
204 /* Add r1 to the result. */
224 lra_assert (r2
!= NULL
);
233 /* Return TRUE if live ranges R1 and R2 intersect. */
235 lra_intersected_live_ranges_p (lra_live_range_t r1
, lra_live_range_t r2
)
237 /* Remember the live ranges are always kept ordered. */
238 while (r1
!= NULL
&& r2
!= NULL
)
240 if (r1
->start
> r2
->finish
)
242 else if (r2
->start
> r1
->finish
)
250 /* The function processing birth of hard register REGNO. It updates
251 living hard regs, START_LIVING, and conflict hard regs for living
252 pseudos. Conflict hard regs for the pic pseudo is not updated if
253 REGNO is REAL_PIC_OFFSET_TABLE_REGNUM and CHECK_PIC_PSEUDO_P is
256 make_hard_regno_born (int regno
, bool check_pic_pseudo_p ATTRIBUTE_UNUSED
)
260 lra_assert (regno
< FIRST_PSEUDO_REGISTER
);
261 if (TEST_HARD_REG_BIT (hard_regs_live
, regno
))
263 SET_HARD_REG_BIT (hard_regs_live
, regno
);
264 sparseset_set_bit (start_living
, regno
);
265 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, i
)
266 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
267 if (! check_pic_pseudo_p
268 || regno
!= REAL_PIC_OFFSET_TABLE_REGNUM
269 || pic_offset_table_rtx
== NULL
270 || i
!= REGNO (pic_offset_table_rtx
))
272 SET_HARD_REG_BIT (lra_reg_info
[i
].conflict_hard_regs
, regno
);
275 /* Process the death of hard register REGNO. This updates
276 hard_regs_live and START_DYING. */
278 make_hard_regno_dead (int regno
)
280 lra_assert (regno
< FIRST_PSEUDO_REGISTER
);
281 if (! TEST_HARD_REG_BIT (hard_regs_live
, regno
))
283 sparseset_set_bit (start_dying
, regno
);
284 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
287 /* Mark pseudo REGNO as living at program point POINT, update conflicting
288 hard registers of the pseudo and START_LIVING, and start a new live
289 range for the pseudo corresponding to REGNO if it is necessary. */
291 mark_pseudo_live (int regno
, int point
)
295 lra_assert (regno
>= FIRST_PSEUDO_REGISTER
);
296 lra_assert (! sparseset_bit_p (pseudos_live
, regno
));
297 sparseset_set_bit (pseudos_live
, regno
);
298 IOR_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
, hard_regs_live
);
300 if ((complete_info_p
|| lra_get_regno_hard_regno (regno
) < 0)
301 && ((p
= lra_reg_info
[regno
].live_ranges
) == NULL
302 || (p
->finish
!= point
&& p
->finish
+ 1 != point
)))
303 lra_reg_info
[regno
].live_ranges
304 = create_live_range (regno
, point
, -1, p
);
305 sparseset_set_bit (start_living
, regno
);
308 /* Mark pseudo REGNO as not living at program point POINT and update
310 This finishes the current live range for the pseudo corresponding
313 mark_pseudo_dead (int regno
, int point
)
317 lra_assert (regno
>= FIRST_PSEUDO_REGISTER
);
318 lra_assert (sparseset_bit_p (pseudos_live
, regno
));
319 sparseset_clear_bit (pseudos_live
, regno
);
320 sparseset_set_bit (start_dying
, regno
);
321 if (complete_info_p
|| lra_get_regno_hard_regno (regno
) < 0)
323 p
= lra_reg_info
[regno
].live_ranges
;
324 lra_assert (p
!= NULL
);
329 /* The corresponding bitmaps of BB currently being processed. */
330 static bitmap bb_killed_pseudos
, bb_gen_pseudos
;
332 /* Mark register REGNO (pseudo or hard register) in MODE as live at
333 program point POINT. Update BB_GEN_PSEUDOS.
334 Return TRUE if the liveness tracking sets were modified, or FALSE
335 if nothing changed. */
337 mark_regno_live (int regno
, machine_mode mode
, int point
)
340 bool changed
= false;
342 if (regno
< FIRST_PSEUDO_REGISTER
)
344 for (last
= regno
+ hard_regno_nregs
[regno
][mode
];
347 make_hard_regno_born (regno
, false);
351 if (! sparseset_bit_p (pseudos_live
, regno
))
353 mark_pseudo_live (regno
, point
);
356 bitmap_set_bit (bb_gen_pseudos
, regno
);
362 /* Mark register REGNO in MODE as dead at program point POINT. Update
363 BB_GEN_PSEUDOS and BB_KILLED_PSEUDOS. Return TRUE if the liveness
364 tracking sets were modified, or FALSE if nothing changed. */
366 mark_regno_dead (int regno
, machine_mode mode
, int point
)
369 bool changed
= false;
371 if (regno
< FIRST_PSEUDO_REGISTER
)
373 for (last
= regno
+ hard_regno_nregs
[regno
][mode
];
376 make_hard_regno_dead (regno
);
380 if (sparseset_bit_p (pseudos_live
, regno
))
382 mark_pseudo_dead (regno
, point
);
385 bitmap_clear_bit (bb_gen_pseudos
, regno
);
386 bitmap_set_bit (bb_killed_pseudos
, regno
);
393 /* This page contains code for making global live analysis of pseudos.
394 The code works only when pseudo live info is changed on a BB
395 border. That might be a consequence of some global transformations
396 in LRA, e.g. PIC pseudo reuse or rematerialization. */
398 /* Structure describing local BB data used for pseudo
400 struct bb_data_pseudos
402 /* Basic block about which the below data are. */
404 bitmap_head killed_pseudos
; /* pseudos killed in the BB. */
405 bitmap_head gen_pseudos
; /* pseudos generated in the BB. */
408 /* Array for all BB data. Indexed by the corresponding BB index. */
409 typedef struct bb_data_pseudos
*bb_data_t
;
411 /* All basic block data are referred through the following array. */
412 static bb_data_t bb_data
;
414 /* Two small functions for access to the bb data. */
415 static inline bb_data_t
416 get_bb_data (basic_block bb
)
418 return &bb_data
[(bb
)->index
];
421 static inline bb_data_t
422 get_bb_data_by_index (int index
)
424 return &bb_data
[index
];
427 /* Bitmap with all hard regs. */
428 static bitmap_head all_hard_regs_bitmap
;
430 /* The transfer function used by the DF equation solver to propagate
431 live info through block with BB_INDEX according to the following
434 bb.livein = (bb.liveout - bb.kill) OR bb.gen
437 live_trans_fun (int bb_index
)
439 basic_block bb
= get_bb_data_by_index (bb_index
)->bb
;
440 bitmap bb_liveout
= df_get_live_out (bb
);
441 bitmap bb_livein
= df_get_live_in (bb
);
442 bb_data_t bb_info
= get_bb_data (bb
);
444 bitmap_and_compl (&temp_bitmap
, bb_liveout
, &all_hard_regs_bitmap
);
445 return bitmap_ior_and_compl (bb_livein
, &bb_info
->gen_pseudos
,
446 &temp_bitmap
, &bb_info
->killed_pseudos
);
449 /* The confluence function used by the DF equation solver to set up
450 live info for a block BB without predecessor. */
452 live_con_fun_0 (basic_block bb
)
454 bitmap_and_into (df_get_live_out (bb
), &all_hard_regs_bitmap
);
457 /* The confluence function used by the DF equation solver to propagate
458 live info from successor to predecessor on edge E according to the
461 bb.liveout = 0 for entry block | OR (livein of successors)
464 live_con_fun_n (edge e
)
466 basic_block bb
= e
->src
;
467 basic_block dest
= e
->dest
;
468 bitmap bb_liveout
= df_get_live_out (bb
);
469 bitmap dest_livein
= df_get_live_in (dest
);
471 return bitmap_ior_and_compl_into (bb_liveout
,
472 dest_livein
, &all_hard_regs_bitmap
);
475 /* Indexes of all function blocks. */
476 static bitmap_head all_blocks
;
478 /* Allocate and initialize data needed for global pseudo live
481 initiate_live_solver (void)
483 bitmap_initialize (&all_hard_regs_bitmap
, ®_obstack
);
484 bitmap_set_range (&all_hard_regs_bitmap
, 0, FIRST_PSEUDO_REGISTER
);
485 bb_data
= XNEWVEC (struct bb_data_pseudos
, last_basic_block_for_fn (cfun
));
486 bitmap_initialize (&all_blocks
, ®_obstack
);
489 FOR_ALL_BB_FN (bb
, cfun
)
491 bb_data_t bb_info
= get_bb_data (bb
);
493 bitmap_initialize (&bb_info
->killed_pseudos
, ®_obstack
);
494 bitmap_initialize (&bb_info
->gen_pseudos
, ®_obstack
);
495 bitmap_set_bit (&all_blocks
, bb
->index
);
499 /* Free all data needed for global pseudo live analysis. */
501 finish_live_solver (void)
505 bitmap_clear (&all_blocks
);
506 FOR_ALL_BB_FN (bb
, cfun
)
508 bb_data_t bb_info
= get_bb_data (bb
);
509 bitmap_clear (&bb_info
->killed_pseudos
);
510 bitmap_clear (&bb_info
->gen_pseudos
);
513 bitmap_clear (&all_hard_regs_bitmap
);
518 /* Insn currently scanned. */
519 static rtx_insn
*curr_insn
;
521 static lra_insn_recog_data_t curr_id
;
522 /* The insn static data. */
523 static struct lra_static_insn_data
*curr_static_id
;
525 /* Return true when one of the predecessor edges of BB is marked with
526 EDGE_ABNORMAL_CALL or EDGE_EH. */
528 bb_has_abnormal_call_pred (basic_block bb
)
533 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
535 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
541 /* Vec containing execution frequencies of program points. */
542 static vec
<int> point_freq_vec
;
544 /* The start of the above vector elements. */
547 /* Increment the current program point POINT to the next point which has
548 execution frequency FREQ. */
550 next_program_point (int &point
, int freq
)
552 point_freq_vec
.safe_push (freq
);
553 lra_point_freq
= point_freq_vec
.address ();
557 /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
559 lra_setup_reload_pseudo_preferenced_hard_reg (int regno
,
560 int hard_regno
, int profit
)
562 lra_assert (regno
>= lra_constraint_new_regno_start
);
563 if (lra_reg_info
[regno
].preferred_hard_regno1
== hard_regno
)
564 lra_reg_info
[regno
].preferred_hard_regno_profit1
+= profit
;
565 else if (lra_reg_info
[regno
].preferred_hard_regno2
== hard_regno
)
566 lra_reg_info
[regno
].preferred_hard_regno_profit2
+= profit
;
567 else if (lra_reg_info
[regno
].preferred_hard_regno1
< 0)
569 lra_reg_info
[regno
].preferred_hard_regno1
= hard_regno
;
570 lra_reg_info
[regno
].preferred_hard_regno_profit1
= profit
;
572 else if (lra_reg_info
[regno
].preferred_hard_regno2
< 0
573 || profit
> lra_reg_info
[regno
].preferred_hard_regno_profit2
)
575 lra_reg_info
[regno
].preferred_hard_regno2
= hard_regno
;
576 lra_reg_info
[regno
].preferred_hard_regno_profit2
= profit
;
580 /* Keep the 1st hard regno as more profitable. */
581 if (lra_reg_info
[regno
].preferred_hard_regno1
>= 0
582 && lra_reg_info
[regno
].preferred_hard_regno2
>= 0
583 && (lra_reg_info
[regno
].preferred_hard_regno_profit2
584 > lra_reg_info
[regno
].preferred_hard_regno_profit1
))
588 temp
= lra_reg_info
[regno
].preferred_hard_regno1
;
589 lra_reg_info
[regno
].preferred_hard_regno1
590 = lra_reg_info
[regno
].preferred_hard_regno2
;
591 lra_reg_info
[regno
].preferred_hard_regno2
= temp
;
592 temp
= lra_reg_info
[regno
].preferred_hard_regno_profit1
;
593 lra_reg_info
[regno
].preferred_hard_regno_profit1
594 = lra_reg_info
[regno
].preferred_hard_regno_profit2
;
595 lra_reg_info
[regno
].preferred_hard_regno_profit2
= temp
;
597 if (lra_dump_file
!= NULL
)
599 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno1
) >= 0)
600 fprintf (lra_dump_file
,
601 " Hard reg %d is preferable by r%d with profit %d\n",
603 lra_reg_info
[regno
].preferred_hard_regno_profit1
);
604 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno2
) >= 0)
605 fprintf (lra_dump_file
,
606 " Hard reg %d is preferable by r%d with profit %d\n",
608 lra_reg_info
[regno
].preferred_hard_regno_profit2
);
612 /* Check that REGNO living through calls and setjumps, set up conflict
613 regs, and clear corresponding bits in PSEUDOS_LIVE_THROUGH_CALLS and
614 PSEUDOS_LIVE_THROUGH_SETJUMPS. */
616 check_pseudos_live_through_calls (int regno
)
620 if (! sparseset_bit_p (pseudos_live_through_calls
, regno
))
622 sparseset_clear_bit (pseudos_live_through_calls
, regno
);
623 IOR_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
,
626 for (hr
= 0; hr
< FIRST_PSEUDO_REGISTER
; hr
++)
627 if (HARD_REGNO_CALL_PART_CLOBBERED (hr
, PSEUDO_REGNO_MODE (regno
)))
628 SET_HARD_REG_BIT (lra_reg_info
[regno
].conflict_hard_regs
, hr
);
629 #ifdef ENABLE_CHECKING
630 lra_reg_info
[regno
].call_p
= true;
632 if (! sparseset_bit_p (pseudos_live_through_setjumps
, regno
))
634 sparseset_clear_bit (pseudos_live_through_setjumps
, regno
);
635 /* Don't allocate pseudos that cross setjmps or any call, if this
636 function receives a nonlocal goto. */
637 SET_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
);
640 /* Process insns of the basic block BB to update pseudo live ranges,
641 pseudo hard register conflicts, and insn notes. We do it on
642 backward scan of BB insns. CURR_POINT is the program point where
643 BB ends. The function updates this counter and returns in
644 CURR_POINT the program point where BB starts. The function also
645 does local live info updates and can delete the dead insns if
646 DEAD_INSN_P. It returns true if pseudo live info was
647 changed at the BB start. */
649 process_bb_lives (basic_block bb
, int &curr_point
, bool dead_insn_p
)
658 bool need_curr_point_incr
;
660 reg_live_out
= df_get_live_out (bb
);
661 sparseset_clear (pseudos_live
);
662 sparseset_clear (pseudos_live_through_calls
);
663 sparseset_clear (pseudos_live_through_setjumps
);
664 REG_SET_TO_HARD_REG_SET (hard_regs_live
, reg_live_out
);
665 AND_COMPL_HARD_REG_SET (hard_regs_live
, eliminable_regset
);
666 EXECUTE_IF_SET_IN_BITMAP (reg_live_out
, FIRST_PSEUDO_REGISTER
, j
, bi
)
667 mark_pseudo_live (j
, curr_point
);
669 bb_gen_pseudos
= &get_bb_data (bb
)->gen_pseudos
;
670 bb_killed_pseudos
= &get_bb_data (bb
)->killed_pseudos
;
671 bitmap_clear (bb_gen_pseudos
);
672 bitmap_clear (bb_killed_pseudos
);
673 freq
= REG_FREQ_FROM_BB (bb
);
675 if (lra_dump_file
!= NULL
)
676 fprintf (lra_dump_file
, " BB %d\n", bb
->index
);
678 /* Scan the code of this basic block, noting which pseudos and hard
679 regs are born or die.
681 Note that this loop treats uninitialized values as live until the
682 beginning of the block. For example, if an instruction uses
683 (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
684 FOO will remain live until the beginning of the block. Likewise
685 if FOO is not set at all. This is unnecessarily pessimistic, but
686 it probably doesn't matter much in practice. */
687 FOR_BB_INSNS_REVERSE_SAFE (bb
, curr_insn
, next
)
690 int dst_regno
, src_regno
;
692 struct lra_insn_reg
*reg
;
694 if (!NONDEBUG_INSN_P (curr_insn
))
697 curr_id
= lra_get_insn_recog_data (curr_insn
);
698 curr_static_id
= curr_id
->insn_static_data
;
699 if (lra_dump_file
!= NULL
)
700 fprintf (lra_dump_file
, " Insn %u: point = %d\n",
701 INSN_UID (curr_insn
), curr_point
);
703 set
= single_set (curr_insn
);
705 if (dead_insn_p
&& set
!= NULL_RTX
706 && REG_P (SET_DEST (set
)) && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
707 && find_reg_note (curr_insn
, REG_EH_REGION
, NULL_RTX
) == NULL_RTX
708 && ! may_trap_p (PATTERN (curr_insn
))
709 /* Don't do premature remove of pic offset pseudo as we can
710 start to use it after some reload generation. */
711 && (pic_offset_table_rtx
== NULL_RTX
712 || pic_offset_table_rtx
!= SET_DEST (set
)))
714 bool remove_p
= true;
716 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
717 if (reg
->type
!= OP_IN
&& sparseset_bit_p (pseudos_live
, reg
->regno
))
722 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
723 if (reg
->type
!= OP_IN
)
728 if (remove_p
&& ! volatile_refs_p (PATTERN (curr_insn
)))
730 dst_regno
= REGNO (SET_DEST (set
));
731 if (lra_dump_file
!= NULL
)
732 fprintf (lra_dump_file
, " Deleting dead insn %u\n",
733 INSN_UID (curr_insn
));
734 lra_set_insn_deleted (curr_insn
);
735 if (lra_reg_info
[dst_regno
].nrefs
== 0)
737 /* There might be some debug insns with the pseudo. */
741 bitmap_copy (&temp_bitmap
, &lra_reg_info
[dst_regno
].insn_bitmap
);
742 EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap
, 0, uid
, bi
)
744 insn
= lra_insn_recog_data
[uid
]->insn
;
745 lra_substitute_pseudo_within_insn (insn
, dst_regno
,
747 lra_update_insn_regno_info (insn
);
754 /* Update max ref width and hard reg usage. */
755 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
756 if (reg
->regno
>= FIRST_PSEUDO_REGISTER
757 && (GET_MODE_SIZE (reg
->biggest_mode
)
758 > GET_MODE_SIZE (lra_reg_info
[reg
->regno
].biggest_mode
)))
759 lra_reg_info
[reg
->regno
].biggest_mode
= reg
->biggest_mode
;
760 else if (reg
->regno
< FIRST_PSEUDO_REGISTER
)
761 lra_hard_reg_usage
[reg
->regno
] += freq
;
763 call_p
= CALL_P (curr_insn
);
766 && REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
))
767 /* Check that source regno does not conflict with
768 destination regno to exclude most impossible
770 && ((((src_regno
= REGNO (SET_SRC (set
))) >= FIRST_PSEUDO_REGISTER
771 && ! sparseset_bit_p (pseudos_live
, src_regno
))
772 || (src_regno
< FIRST_PSEUDO_REGISTER
773 && ! TEST_HARD_REG_BIT (hard_regs_live
, src_regno
)))
774 /* It might be 'inheritance pseudo <- reload pseudo'. */
775 || (src_regno
>= lra_constraint_new_regno_start
776 && ((int) REGNO (SET_DEST (set
))
777 >= lra_constraint_new_regno_start
)
778 /* Remember to skip special cases where src/dest regnos are
779 the same, e.g. insn SET pattern has matching constraints
781 && src_regno
!= (int) REGNO (SET_DEST (set
)))))
783 int hard_regno
= -1, regno
= -1;
785 dst_regno
= REGNO (SET_DEST (set
));
786 if (dst_regno
>= lra_constraint_new_regno_start
787 && src_regno
>= lra_constraint_new_regno_start
)
788 lra_create_copy (dst_regno
, src_regno
, freq
);
789 else if (dst_regno
>= lra_constraint_new_regno_start
)
791 if ((hard_regno
= src_regno
) >= FIRST_PSEUDO_REGISTER
)
792 hard_regno
= reg_renumber
[src_regno
];
795 else if (src_regno
>= lra_constraint_new_regno_start
)
797 if ((hard_regno
= dst_regno
) >= FIRST_PSEUDO_REGISTER
)
798 hard_regno
= reg_renumber
[dst_regno
];
801 if (regno
>= 0 && hard_regno
>= 0)
802 lra_setup_reload_pseudo_preferenced_hard_reg
803 (regno
, hard_regno
, freq
);
806 sparseset_clear (start_living
);
808 /* Try to avoid unnecessary program point increments, this saves
809 a lot of time in remove_some_program_points_and_update_live_ranges.
810 We only need an increment if something becomes live or dies at this
812 need_curr_point_incr
= false;
814 /* Mark each defined value as live. We need to do this for
815 unused values because they still conflict with quantities
816 that are live at the time of the definition. */
817 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
818 if (reg
->type
!= OP_IN
)
821 |= mark_regno_live (reg
->regno
, reg
->biggest_mode
,
823 check_pseudos_live_through_calls (reg
->regno
);
826 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
827 if (reg
->type
!= OP_IN
)
828 make_hard_regno_born (reg
->regno
, false);
830 sparseset_copy (unused_set
, start_living
);
832 sparseset_clear (start_dying
);
834 /* See which defined values die here. */
835 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
836 if (reg
->type
== OP_OUT
&& ! reg
->early_clobber
&& ! reg
->subreg_p
)
838 |= mark_regno_dead (reg
->regno
, reg
->biggest_mode
,
841 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
842 if (reg
->type
== OP_OUT
&& ! reg
->early_clobber
&& ! reg
->subreg_p
)
843 make_hard_regno_dead (reg
->regno
);
849 HARD_REG_SET this_call_used_reg_set
;
850 get_call_reg_set_usage (curr_insn
, &this_call_used_reg_set
,
853 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, j
)
854 IOR_HARD_REG_SET (lra_reg_info
[j
].actual_call_used_reg_set
,
855 this_call_used_reg_set
);
858 sparseset_ior (pseudos_live_through_calls
,
859 pseudos_live_through_calls
, pseudos_live
);
860 if (cfun
->has_nonlocal_label
861 || find_reg_note (curr_insn
, REG_SETJMP
,
862 NULL_RTX
) != NULL_RTX
)
863 sparseset_ior (pseudos_live_through_setjumps
,
864 pseudos_live_through_setjumps
, pseudos_live
);
867 /* Increment the current program point if we must. */
868 if (need_curr_point_incr
)
869 next_program_point (curr_point
, freq
);
871 sparseset_clear (start_living
);
873 need_curr_point_incr
= false;
875 /* Mark each used value as live. */
876 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
877 if (reg
->type
== OP_IN
)
880 |= mark_regno_live (reg
->regno
, reg
->biggest_mode
,
882 check_pseudos_live_through_calls (reg
->regno
);
885 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
886 if (reg
->type
== OP_IN
)
887 make_hard_regno_born (reg
->regno
, false);
889 if (curr_id
->arg_hard_regs
!= NULL
)
890 /* Make argument hard registers live. Don't create conflict
891 of used REAL_PIC_OFFSET_TABLE_REGNUM and the pic pseudo. */
892 for (i
= 0; (regno
= curr_id
->arg_hard_regs
[i
]) >= 0; i
++)
893 make_hard_regno_born (regno
, true);
895 sparseset_and_compl (dead_set
, start_living
, start_dying
);
897 /* Mark early clobber outputs dead. */
898 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
899 if (reg
->type
== OP_OUT
&& reg
->early_clobber
&& ! reg
->subreg_p
)
901 |= mark_regno_dead (reg
->regno
, reg
->biggest_mode
,
904 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
905 if (reg
->type
== OP_OUT
&& reg
->early_clobber
&& ! reg
->subreg_p
)
906 make_hard_regno_dead (reg
->regno
);
908 if (need_curr_point_incr
)
909 next_program_point (curr_point
, freq
);
912 for (link_loc
= ®_NOTES (curr_insn
); (link
= *link_loc
) != NULL_RTX
;)
914 if (REG_NOTE_KIND (link
) != REG_DEAD
915 && REG_NOTE_KIND (link
) != REG_UNUSED
)
917 else if (REG_P (XEXP (link
, 0)))
919 regno
= REGNO (XEXP (link
, 0));
920 if ((REG_NOTE_KIND (link
) == REG_DEAD
921 && ! sparseset_bit_p (dead_set
, regno
))
922 || (REG_NOTE_KIND (link
) == REG_UNUSED
923 && ! sparseset_bit_p (unused_set
, regno
)))
925 *link_loc
= XEXP (link
, 1);
928 if (REG_NOTE_KIND (link
) == REG_DEAD
)
929 sparseset_clear_bit (dead_set
, regno
);
930 else if (REG_NOTE_KIND (link
) == REG_UNUSED
)
931 sparseset_clear_bit (unused_set
, regno
);
933 link_loc
= &XEXP (link
, 1);
935 EXECUTE_IF_SET_IN_SPARSESET (dead_set
, j
)
936 add_reg_note (curr_insn
, REG_DEAD
, regno_reg_rtx
[j
]);
937 EXECUTE_IF_SET_IN_SPARSESET (unused_set
, j
)
938 add_reg_note (curr_insn
, REG_UNUSED
, regno_reg_rtx
[j
]);
941 if (bb_has_eh_pred (bb
))
944 unsigned int regno
= EH_RETURN_DATA_REGNO (j
);
946 if (regno
== INVALID_REGNUM
)
948 make_hard_regno_born (regno
, false);
951 /* Pseudos can't go in stack regs at the start of a basic block that
952 is reached by an abnormal edge. Likewise for call clobbered regs,
953 because caller-save, fixup_abnormal_edges and possibly the table
954 driven EH machinery are not quite ready to handle such pseudos
955 live across such edges. */
956 if (bb_has_abnormal_pred (bb
))
959 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, px
)
960 lra_reg_info
[px
].no_stack_p
= true;
961 for (px
= FIRST_STACK_REG
; px
<= LAST_STACK_REG
; px
++)
962 make_hard_regno_born (px
, false);
964 /* No need to record conflicts for call clobbered regs if we
965 have nonlocal labels around, as we don't ever try to
966 allocate such regs in this case. */
967 if (!cfun
->has_nonlocal_label
&& bb_has_abnormal_call_pred (bb
))
968 for (px
= 0; px
< FIRST_PSEUDO_REGISTER
; px
++)
969 if (call_used_regs
[px
])
970 make_hard_regno_born (px
, false);
973 bool live_change_p
= false;
974 /* Check if bb border live info was changed. */
975 unsigned int live_pseudos_num
= 0;
976 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb
),
977 FIRST_PSEUDO_REGISTER
, j
, bi
)
980 if (! sparseset_bit_p (pseudos_live
, j
))
982 live_change_p
= true;
983 if (lra_dump_file
!= NULL
)
984 fprintf (lra_dump_file
,
985 " r%d is removed as live at bb%d start\n", j
, bb
->index
);
990 && sparseset_cardinality (pseudos_live
) != live_pseudos_num
)
992 live_change_p
= true;
993 if (lra_dump_file
!= NULL
)
994 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, j
)
995 if (! bitmap_bit_p (df_get_live_in (bb
), j
))
996 fprintf (lra_dump_file
,
997 " r%d is added to live at bb%d start\n", j
, bb
->index
);
999 /* See if we'll need an increment at the end of this basic block.
1000 An increment is needed if the PSEUDOS_LIVE set is not empty,
1001 to make sure the finish points are set up correctly. */
1002 need_curr_point_incr
= (sparseset_cardinality (pseudos_live
) > 0);
1004 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, i
)
1005 mark_pseudo_dead (i
, curr_point
);
1007 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb
), FIRST_PSEUDO_REGISTER
, j
, bi
)
1009 if (sparseset_cardinality (pseudos_live_through_calls
) == 0)
1011 if (sparseset_bit_p (pseudos_live_through_calls
, j
))
1012 check_pseudos_live_through_calls (j
);
1015 if (need_curr_point_incr
)
1016 next_program_point (curr_point
, freq
);
1018 return live_change_p
;
1021 /* Compress pseudo live ranges by removing program points where
1022 nothing happens. Complexity of many algorithms in LRA is linear
1023 function of program points number. To speed up the code we try to
1024 minimize the number of the program points here. */
1026 remove_some_program_points_and_update_live_ranges (void)
1031 lra_live_range_t r
, prev_r
, next_r
;
1032 sbitmap born_or_dead
, born
, dead
;
1033 sbitmap_iterator sbi
;
1034 bool born_p
, dead_p
, prev_born_p
, prev_dead_p
;
1036 born
= sbitmap_alloc (lra_live_max_point
);
1037 dead
= sbitmap_alloc (lra_live_max_point
);
1038 bitmap_clear (born
);
1039 bitmap_clear (dead
);
1040 max_regno
= max_reg_num ();
1041 for (i
= FIRST_PSEUDO_REGISTER
; i
< (unsigned) max_regno
; i
++)
1043 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
1045 lra_assert (r
->start
<= r
->finish
);
1046 bitmap_set_bit (born
, r
->start
);
1047 bitmap_set_bit (dead
, r
->finish
);
1050 born_or_dead
= sbitmap_alloc (lra_live_max_point
);
1051 bitmap_ior (born_or_dead
, born
, dead
);
1052 map
= XCNEWVEC (int, lra_live_max_point
);
1054 prev_born_p
= prev_dead_p
= false;
1055 EXECUTE_IF_SET_IN_BITMAP (born_or_dead
, 0, i
, sbi
)
1057 born_p
= bitmap_bit_p (born
, i
);
1058 dead_p
= bitmap_bit_p (dead
, i
);
1059 if ((prev_born_p
&& ! prev_dead_p
&& born_p
&& ! dead_p
)
1060 || (prev_dead_p
&& ! prev_born_p
&& dead_p
&& ! born_p
))
1063 lra_point_freq
[n
] = MAX (lra_point_freq
[n
], lra_point_freq
[i
]);
1068 lra_point_freq
[n
] = lra_point_freq
[i
];
1070 prev_born_p
= born_p
;
1071 prev_dead_p
= dead_p
;
1073 sbitmap_free (born_or_dead
);
1074 sbitmap_free (born
);
1075 sbitmap_free (dead
);
1077 if (lra_dump_file
!= NULL
)
1078 fprintf (lra_dump_file
, "Compressing live ranges: from %d to %d - %d%%\n",
1079 lra_live_max_point
, n
, 100 * n
/ lra_live_max_point
);
1080 if (n
< lra_live_max_point
)
1082 lra_live_max_point
= n
;
1083 for (i
= FIRST_PSEUDO_REGISTER
; i
< (unsigned) max_regno
; i
++)
1085 for (prev_r
= NULL
, r
= lra_reg_info
[i
].live_ranges
;
1090 r
->start
= map
[r
->start
];
1091 r
->finish
= map
[r
->finish
];
1092 if (prev_r
== NULL
|| prev_r
->start
> r
->finish
+ 1)
1097 prev_r
->start
= r
->start
;
1098 prev_r
->next
= next_r
;
1106 /* Print live ranges R to file F. */
1108 lra_print_live_range_list (FILE *f
, lra_live_range_t r
)
1110 for (; r
!= NULL
; r
= r
->next
)
1111 fprintf (f
, " [%d..%d]", r
->start
, r
->finish
);
1116 debug (lra_live_range
&ref
)
1118 lra_print_live_range_list (stderr
, &ref
);
1122 debug (lra_live_range
*ptr
)
1127 fprintf (stderr
, "<nil>\n");
1130 /* Print live ranges R to stderr. */
1132 lra_debug_live_range_list (lra_live_range_t r
)
1134 lra_print_live_range_list (stderr
, r
);
1137 /* Print live ranges of pseudo REGNO to file F. */
1139 print_pseudo_live_ranges (FILE *f
, int regno
)
1141 if (lra_reg_info
[regno
].live_ranges
== NULL
)
1143 fprintf (f
, " r%d:", regno
);
1144 lra_print_live_range_list (f
, lra_reg_info
[regno
].live_ranges
);
1147 /* Print live ranges of pseudo REGNO to stderr. */
1149 lra_debug_pseudo_live_ranges (int regno
)
1151 print_pseudo_live_ranges (stderr
, regno
);
1154 /* Print live ranges of all pseudos to file F. */
1156 print_live_ranges (FILE *f
)
1160 max_regno
= max_reg_num ();
1161 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1162 print_pseudo_live_ranges (f
, i
);
1165 /* Print live ranges of all pseudos to stderr. */
1167 lra_debug_live_ranges (void)
1169 print_live_ranges (stderr
);
1172 /* Compress pseudo live ranges. */
1174 compress_live_ranges (void)
1176 remove_some_program_points_and_update_live_ranges ();
1177 if (lra_dump_file
!= NULL
)
1179 fprintf (lra_dump_file
, "Ranges after the compression:\n");
1180 print_live_ranges (lra_dump_file
);
1186 /* The number of the current live range pass. */
1187 int lra_live_range_iter
;
1189 /* The function creates live ranges only for memory pseudos (or for
1190 all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos. It
1191 also does dead insn elimination if DEAD_INSN_P and global live
1192 analysis only for pseudos and only if the pseudo live info was
1193 changed on a BB border. Return TRUE if the live info was
1196 lra_create_live_ranges_1 (bool all_p
, bool dead_insn_p
)
1199 int i
, hard_regno
, max_regno
= max_reg_num ();
1201 bool bb_live_change_p
, have_referenced_pseudos
= false;
1203 timevar_push (TV_LRA_CREATE_LIVE_RANGES
);
1205 complete_info_p
= all_p
;
1206 if (lra_dump_file
!= NULL
)
1207 fprintf (lra_dump_file
,
1208 "\n********** Pseudo live ranges #%d: **********\n\n",
1209 ++lra_live_range_iter
);
1210 memset (lra_hard_reg_usage
, 0, sizeof (lra_hard_reg_usage
));
1211 for (i
= 0; i
< max_regno
; i
++)
1213 lra_reg_info
[i
].live_ranges
= NULL
;
1214 CLEAR_HARD_REG_SET (lra_reg_info
[i
].conflict_hard_regs
);
1215 lra_reg_info
[i
].preferred_hard_regno1
= -1;
1216 lra_reg_info
[i
].preferred_hard_regno2
= -1;
1217 lra_reg_info
[i
].preferred_hard_regno_profit1
= 0;
1218 lra_reg_info
[i
].preferred_hard_regno_profit2
= 0;
1220 lra_reg_info
[i
].no_stack_p
= false;
1222 /* The biggest mode is already set but its value might be to
1223 conservative because of recent transformation. Here in this
1224 file we recalculate it again as it costs practically
1226 if (regno_reg_rtx
[i
] != NULL_RTX
)
1227 lra_reg_info
[i
].biggest_mode
= GET_MODE (regno_reg_rtx
[i
]);
1229 lra_reg_info
[i
].biggest_mode
= VOIDmode
;
1230 #ifdef ENABLE_CHECKING
1231 lra_reg_info
[i
].call_p
= false;
1233 if (i
>= FIRST_PSEUDO_REGISTER
1234 && lra_reg_info
[i
].nrefs
!= 0)
1236 if ((hard_regno
= reg_renumber
[i
]) >= 0)
1237 lra_hard_reg_usage
[hard_regno
] += lra_reg_info
[i
].freq
;
1238 have_referenced_pseudos
= true;
1243 /* Under some circumstances, we can have functions without pseudo
1244 registers. For such functions, lra_live_max_point will be 0,
1245 see e.g. PR55604, and there's nothing more to do for us here. */
1246 if (! have_referenced_pseudos
)
1248 timevar_pop (TV_LRA_CREATE_LIVE_RANGES
);
1252 pseudos_live
= sparseset_alloc (max_regno
);
1253 pseudos_live_through_calls
= sparseset_alloc (max_regno
);
1254 pseudos_live_through_setjumps
= sparseset_alloc (max_regno
);
1255 start_living
= sparseset_alloc (max_regno
);
1256 start_dying
= sparseset_alloc (max_regno
);
1257 dead_set
= sparseset_alloc (max_regno
);
1258 unused_set
= sparseset_alloc (max_regno
);
1260 point_freq_vec
.create (get_max_uid () * 2);
1261 lra_point_freq
= point_freq_vec
.address ();
1262 int *post_order_rev_cfg
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1263 int n_blocks_inverted
= inverted_post_order_compute (post_order_rev_cfg
);
1264 lra_assert (n_blocks_inverted
== n_basic_blocks_for_fn (cfun
));
1265 bb_live_change_p
= false;
1266 for (i
= n_blocks_inverted
- 1; i
>= 0; --i
)
1268 bb
= BASIC_BLOCK_FOR_FN (cfun
, post_order_rev_cfg
[i
]);
1269 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
1270 == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1272 if (process_bb_lives (bb
, curr_point
, dead_insn_p
))
1273 bb_live_change_p
= true;
1275 if (bb_live_change_p
)
1277 /* We need to clear pseudo live info as some pseudos can
1278 disappear, e.g. pseudos with used equivalences. */
1279 FOR_EACH_BB_FN (bb
, cfun
)
1281 bitmap_clear_range (df_get_live_in (bb
), FIRST_PSEUDO_REGISTER
,
1282 max_regno
- FIRST_PSEUDO_REGISTER
);
1283 bitmap_clear_range (df_get_live_out (bb
), FIRST_PSEUDO_REGISTER
,
1284 max_regno
- FIRST_PSEUDO_REGISTER
);
1286 /* As we did not change CFG since LRA start we can use
1287 DF-infrastructure solver to solve live data flow problem. */
1289 (DF_BACKWARD
, NULL
, live_con_fun_0
, live_con_fun_n
,
1290 live_trans_fun
, &all_blocks
,
1291 df_get_postorder (DF_BACKWARD
), df_get_n_blocks (DF_BACKWARD
));
1292 if (lra_dump_file
!= NULL
)
1294 fprintf (lra_dump_file
,
1295 "Global pseudo live data have been updated:\n");
1297 FOR_EACH_BB_FN (bb
, cfun
)
1299 bb_data_t bb_info
= get_bb_data (bb
);
1300 bitmap bb_livein
= df_get_live_in (bb
);
1301 bitmap bb_liveout
= df_get_live_out (bb
);
1303 fprintf (lra_dump_file
, "\nBB %d:\n", bb
->index
);
1304 lra_dump_bitmap_with_title (" gen:",
1305 &bb_info
->gen_pseudos
, bb
->index
);
1306 lra_dump_bitmap_with_title (" killed:",
1307 &bb_info
->killed_pseudos
, bb
->index
);
1308 lra_dump_bitmap_with_title (" livein:", bb_livein
, bb
->index
);
1309 lra_dump_bitmap_with_title (" liveout:", bb_liveout
, bb
->index
);
1313 free (post_order_rev_cfg
);
1314 lra_live_max_point
= curr_point
;
1315 if (lra_dump_file
!= NULL
)
1316 print_live_ranges (lra_dump_file
);
1318 sparseset_free (unused_set
);
1319 sparseset_free (dead_set
);
1320 sparseset_free (start_dying
);
1321 sparseset_free (start_living
);
1322 sparseset_free (pseudos_live_through_calls
);
1323 sparseset_free (pseudos_live_through_setjumps
);
1324 sparseset_free (pseudos_live
);
1325 compress_live_ranges ();
1326 timevar_pop (TV_LRA_CREATE_LIVE_RANGES
);
1327 return bb_live_change_p
;
1330 /* The main entry function creates live-ranges and other live info
1331 necessary for the assignment sub-pass. It uses
1332 lra_creates_live_ranges_1 -- so read comments for the
1335 lra_create_live_ranges (bool all_p
, bool dead_insn_p
)
1337 if (! lra_create_live_ranges_1 (all_p
, dead_insn_p
))
1339 if (lra_dump_file
!= NULL
)
1340 fprintf (lra_dump_file
, "Live info was changed -- recalculate it\n");
1341 /* Live info was changed on a bb border. It means that some info,
1342 e.g. about conflict regs, calls crossed, and live ranges may be
1343 wrong. We need this info for allocation. So recalculate it
1344 again but without removing dead insns which can change live info
1345 again. Repetitive live range calculations are expensive therefore
1346 we stop here as we already have correct info although some
1347 improvement in rare cases could be possible on this sub-pass if
1348 we do dead insn elimination again (still the improvement may
1350 lra_clear_live_ranges ();
1351 bool res
= lra_create_live_ranges_1 (all_p
, false);
1355 /* Finish all live ranges. */
1357 lra_clear_live_ranges (void)
1361 for (i
= 0; i
< max_reg_num (); i
++)
1362 free_live_range_list (lra_reg_info
[i
].live_ranges
);
1363 point_freq_vec
.release ();
1366 /* Initialize live ranges data once per function. */
1368 lra_live_ranges_init (void)
1370 bitmap_initialize (&temp_bitmap
, ®_obstack
);
1371 initiate_live_solver ();
1374 /* Finish live ranges data once per function. */
1376 lra_live_ranges_finish (void)
1378 finish_live_solver ();
1379 bitmap_clear (&temp_bitmap
);
1380 lra_live_range::pool
.release ();