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"
36 #include "insn-config.h"
53 #include "sparseset.h"
55 #include "insn-attr.h"
56 #include "insn-codes.h"
59 /* Program points are enumerated by numbers from range
60 0..LRA_LIVE_MAX_POINT-1. There are approximately two times more
61 program points than insns. Program points are places in the
62 program where liveness info can be changed. In most general case
63 (there are more complicated cases too) some program points
64 correspond to places where input operand dies and other ones
65 correspond to places where output operands are born. */
66 int lra_live_max_point
;
68 /* Accumulated execution frequency of all references for each hard
70 int lra_hard_reg_usage
[FIRST_PSEUDO_REGISTER
];
72 /* A global flag whose true value says to build live ranges for all
73 pseudos, otherwise the live ranges only for pseudos got memory is
74 build. True value means also building copies and setting up hard
75 register preferences. The complete info is necessary only for the
76 assignment pass. The complete info is not needed for the
77 coalescing and spill passes. */
78 static bool complete_info_p
;
80 /* Pseudos live at current point in the RTL scan. */
81 static sparseset pseudos_live
;
83 /* Pseudos probably living through calls and setjumps. As setjump is
84 a call too, if a bit in PSEUDOS_LIVE_THROUGH_SETJUMPS is set up
85 then the corresponding bit in PSEUDOS_LIVE_THROUGH_CALLS is set up
86 too. These data are necessary for cases when only one subreg of a
87 multi-reg pseudo is set up after a call. So we decide it is
88 probably live when traversing bb backward. We are sure about
89 living when we see its usage or definition of the pseudo. */
90 static sparseset pseudos_live_through_calls
;
91 static sparseset pseudos_live_through_setjumps
;
93 /* Set of hard regs (except eliminable ones) currently live. */
94 static HARD_REG_SET hard_regs_live
;
96 /* Set of pseudos and hard registers start living/dying in the current
97 insn. These sets are used to update REG_DEAD and REG_UNUSED notes
99 static sparseset start_living
, start_dying
;
101 /* Set of pseudos and hard regs dead and unused in the current
103 static sparseset unused_set
, dead_set
;
105 /* Bitmap used for holding intermediate bitmap operation results. */
106 static bitmap_head temp_bitmap
;
108 /* Pool for pseudo live ranges. */
109 pool_allocator
<lra_live_range
> lra_live_range::pool ("live ranges", 100);
111 /* Free live range list LR. */
113 free_live_range_list (lra_live_range_t lr
)
115 lra_live_range_t next
;
125 /* Create and return pseudo live range with given attributes. */
126 static lra_live_range_t
127 create_live_range (int regno
, int start
, int finish
, lra_live_range_t next
)
129 lra_live_range_t p
= new lra_live_range
;
137 /* Copy live range R and return the result. */
138 static lra_live_range_t
139 copy_live_range (lra_live_range_t r
)
141 return new lra_live_range (*r
);
144 /* Copy live range list given by its head R and return the result. */
146 lra_copy_live_range_list (lra_live_range_t r
)
148 lra_live_range_t p
, first
, *chain
;
151 for (chain
= &first
; r
!= NULL
; r
= r
->next
)
153 p
= copy_live_range (r
);
160 /* Merge *non-intersected* ranges R1 and R2 and returns the result.
161 The function maintains the order of ranges and tries to minimize
162 size of the result range list. Ranges R1 and R2 may not be used
165 lra_merge_live_ranges (lra_live_range_t r1
, lra_live_range_t r2
)
167 lra_live_range_t first
, last
;
173 for (first
= last
= NULL
; r1
!= NULL
&& r2
!= NULL
;)
175 if (r1
->start
< r2
->start
)
178 if (r1
->start
== r2
->finish
+ 1)
180 /* Joint ranges: merge r1 and r2 into r1. */
181 r1
->start
= r2
->start
;
182 lra_live_range_t temp
= r2
;
188 gcc_assert (r2
->finish
+ 1 < r1
->start
);
189 /* Add r1 to the result. */
209 lra_assert (r2
!= NULL
);
218 /* Return TRUE if live ranges R1 and R2 intersect. */
220 lra_intersected_live_ranges_p (lra_live_range_t r1
, lra_live_range_t r2
)
222 /* Remember the live ranges are always kept ordered. */
223 while (r1
!= NULL
&& r2
!= NULL
)
225 if (r1
->start
> r2
->finish
)
227 else if (r2
->start
> r1
->finish
)
235 /* The function processing birth of hard register REGNO. It updates
236 living hard regs, START_LIVING, and conflict hard regs for living
237 pseudos. Conflict hard regs for the pic pseudo is not updated if
238 REGNO is REAL_PIC_OFFSET_TABLE_REGNUM and CHECK_PIC_PSEUDO_P is
241 make_hard_regno_born (int regno
, bool check_pic_pseudo_p ATTRIBUTE_UNUSED
)
245 lra_assert (regno
< FIRST_PSEUDO_REGISTER
);
246 if (TEST_HARD_REG_BIT (hard_regs_live
, regno
))
248 SET_HARD_REG_BIT (hard_regs_live
, regno
);
249 sparseset_set_bit (start_living
, regno
);
250 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, i
)
251 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
252 if (! check_pic_pseudo_p
253 || regno
!= REAL_PIC_OFFSET_TABLE_REGNUM
254 || pic_offset_table_rtx
== NULL
255 || i
!= REGNO (pic_offset_table_rtx
))
257 SET_HARD_REG_BIT (lra_reg_info
[i
].conflict_hard_regs
, regno
);
260 /* Process the death of hard register REGNO. This updates
261 hard_regs_live and START_DYING. */
263 make_hard_regno_dead (int regno
)
265 lra_assert (regno
< FIRST_PSEUDO_REGISTER
);
266 if (! TEST_HARD_REG_BIT (hard_regs_live
, regno
))
268 sparseset_set_bit (start_dying
, regno
);
269 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
272 /* Mark pseudo REGNO as living at program point POINT, update conflicting
273 hard registers of the pseudo and START_LIVING, and start a new live
274 range for the pseudo corresponding to REGNO if it is necessary. */
276 mark_pseudo_live (int regno
, int point
)
280 lra_assert (regno
>= FIRST_PSEUDO_REGISTER
);
281 lra_assert (! sparseset_bit_p (pseudos_live
, regno
));
282 sparseset_set_bit (pseudos_live
, regno
);
283 IOR_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
, hard_regs_live
);
285 if ((complete_info_p
|| lra_get_regno_hard_regno (regno
) < 0)
286 && ((p
= lra_reg_info
[regno
].live_ranges
) == NULL
287 || (p
->finish
!= point
&& p
->finish
+ 1 != point
)))
288 lra_reg_info
[regno
].live_ranges
289 = create_live_range (regno
, point
, -1, p
);
290 sparseset_set_bit (start_living
, regno
);
293 /* Mark pseudo REGNO as not living at program point POINT and update
295 This finishes the current live range for the pseudo corresponding
298 mark_pseudo_dead (int regno
, int point
)
302 lra_assert (regno
>= FIRST_PSEUDO_REGISTER
);
303 lra_assert (sparseset_bit_p (pseudos_live
, regno
));
304 sparseset_clear_bit (pseudos_live
, regno
);
305 sparseset_set_bit (start_dying
, regno
);
306 if (complete_info_p
|| lra_get_regno_hard_regno (regno
) < 0)
308 p
= lra_reg_info
[regno
].live_ranges
;
309 lra_assert (p
!= NULL
);
314 /* The corresponding bitmaps of BB currently being processed. */
315 static bitmap bb_killed_pseudos
, bb_gen_pseudos
;
317 /* Mark register REGNO (pseudo or hard register) in MODE as live at
318 program point POINT. Update BB_GEN_PSEUDOS.
319 Return TRUE if the liveness tracking sets were modified, or FALSE
320 if nothing changed. */
322 mark_regno_live (int regno
, machine_mode mode
, int point
)
325 bool changed
= false;
327 if (regno
< FIRST_PSEUDO_REGISTER
)
329 for (last
= regno
+ hard_regno_nregs
[regno
][mode
];
332 make_hard_regno_born (regno
, false);
336 if (! sparseset_bit_p (pseudos_live
, regno
))
338 mark_pseudo_live (regno
, point
);
341 bitmap_set_bit (bb_gen_pseudos
, regno
);
347 /* Mark register REGNO in MODE as dead at program point POINT. Update
348 BB_GEN_PSEUDOS and BB_KILLED_PSEUDOS. Return TRUE if the liveness
349 tracking sets were modified, or FALSE if nothing changed. */
351 mark_regno_dead (int regno
, machine_mode mode
, int point
)
354 bool changed
= false;
356 if (regno
< FIRST_PSEUDO_REGISTER
)
358 for (last
= regno
+ hard_regno_nregs
[regno
][mode
];
361 make_hard_regno_dead (regno
);
365 if (sparseset_bit_p (pseudos_live
, regno
))
367 mark_pseudo_dead (regno
, point
);
370 bitmap_clear_bit (bb_gen_pseudos
, regno
);
371 bitmap_set_bit (bb_killed_pseudos
, regno
);
378 /* This page contains code for making global live analysis of pseudos.
379 The code works only when pseudo live info is changed on a BB
380 border. That might be a consequence of some global transformations
381 in LRA, e.g. PIC pseudo reuse or rematerialization. */
383 /* Structure describing local BB data used for pseudo
385 struct bb_data_pseudos
387 /* Basic block about which the below data are. */
389 bitmap_head killed_pseudos
; /* pseudos killed in the BB. */
390 bitmap_head gen_pseudos
; /* pseudos generated in the BB. */
393 /* Array for all BB data. Indexed by the corresponding BB index. */
394 typedef struct bb_data_pseudos
*bb_data_t
;
396 /* All basic block data are referred through the following array. */
397 static bb_data_t bb_data
;
399 /* Two small functions for access to the bb data. */
400 static inline bb_data_t
401 get_bb_data (basic_block bb
)
403 return &bb_data
[(bb
)->index
];
406 static inline bb_data_t
407 get_bb_data_by_index (int index
)
409 return &bb_data
[index
];
412 /* Bitmap with all hard regs. */
413 static bitmap_head all_hard_regs_bitmap
;
415 /* The transfer function used by the DF equation solver to propagate
416 live info through block with BB_INDEX according to the following
419 bb.livein = (bb.liveout - bb.kill) OR bb.gen
422 live_trans_fun (int bb_index
)
424 basic_block bb
= get_bb_data_by_index (bb_index
)->bb
;
425 bitmap bb_liveout
= df_get_live_out (bb
);
426 bitmap bb_livein
= df_get_live_in (bb
);
427 bb_data_t bb_info
= get_bb_data (bb
);
429 bitmap_and_compl (&temp_bitmap
, bb_liveout
, &all_hard_regs_bitmap
);
430 return bitmap_ior_and_compl (bb_livein
, &bb_info
->gen_pseudos
,
431 &temp_bitmap
, &bb_info
->killed_pseudos
);
434 /* The confluence function used by the DF equation solver to set up
435 live info for a block BB without predecessor. */
437 live_con_fun_0 (basic_block bb
)
439 bitmap_and_into (df_get_live_out (bb
), &all_hard_regs_bitmap
);
442 /* The confluence function used by the DF equation solver to propagate
443 live info from successor to predecessor on edge E according to the
446 bb.liveout = 0 for entry block | OR (livein of successors)
449 live_con_fun_n (edge e
)
451 basic_block bb
= e
->src
;
452 basic_block dest
= e
->dest
;
453 bitmap bb_liveout
= df_get_live_out (bb
);
454 bitmap dest_livein
= df_get_live_in (dest
);
456 return bitmap_ior_and_compl_into (bb_liveout
,
457 dest_livein
, &all_hard_regs_bitmap
);
460 /* Indexes of all function blocks. */
461 static bitmap_head all_blocks
;
463 /* Allocate and initialize data needed for global pseudo live
466 initiate_live_solver (void)
468 bitmap_initialize (&all_hard_regs_bitmap
, ®_obstack
);
469 bitmap_set_range (&all_hard_regs_bitmap
, 0, FIRST_PSEUDO_REGISTER
);
470 bb_data
= XNEWVEC (struct bb_data_pseudos
, last_basic_block_for_fn (cfun
));
471 bitmap_initialize (&all_blocks
, ®_obstack
);
474 FOR_ALL_BB_FN (bb
, cfun
)
476 bb_data_t bb_info
= get_bb_data (bb
);
478 bitmap_initialize (&bb_info
->killed_pseudos
, ®_obstack
);
479 bitmap_initialize (&bb_info
->gen_pseudos
, ®_obstack
);
480 bitmap_set_bit (&all_blocks
, bb
->index
);
484 /* Free all data needed for global pseudo live analysis. */
486 finish_live_solver (void)
490 bitmap_clear (&all_blocks
);
491 FOR_ALL_BB_FN (bb
, cfun
)
493 bb_data_t bb_info
= get_bb_data (bb
);
494 bitmap_clear (&bb_info
->killed_pseudos
);
495 bitmap_clear (&bb_info
->gen_pseudos
);
498 bitmap_clear (&all_hard_regs_bitmap
);
503 /* Insn currently scanned. */
504 static rtx_insn
*curr_insn
;
506 static lra_insn_recog_data_t curr_id
;
507 /* The insn static data. */
508 static struct lra_static_insn_data
*curr_static_id
;
510 /* Return true when one of the predecessor edges of BB is marked with
511 EDGE_ABNORMAL_CALL or EDGE_EH. */
513 bb_has_abnormal_call_pred (basic_block bb
)
518 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
520 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
526 /* Vec containing execution frequencies of program points. */
527 static vec
<int> point_freq_vec
;
529 /* The start of the above vector elements. */
532 /* Increment the current program point POINT to the next point which has
533 execution frequency FREQ. */
535 next_program_point (int &point
, int freq
)
537 point_freq_vec
.safe_push (freq
);
538 lra_point_freq
= point_freq_vec
.address ();
542 /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
544 lra_setup_reload_pseudo_preferenced_hard_reg (int regno
,
545 int hard_regno
, int profit
)
547 lra_assert (regno
>= lra_constraint_new_regno_start
);
548 if (lra_reg_info
[regno
].preferred_hard_regno1
== hard_regno
)
549 lra_reg_info
[regno
].preferred_hard_regno_profit1
+= profit
;
550 else if (lra_reg_info
[regno
].preferred_hard_regno2
== hard_regno
)
551 lra_reg_info
[regno
].preferred_hard_regno_profit2
+= profit
;
552 else if (lra_reg_info
[regno
].preferred_hard_regno1
< 0)
554 lra_reg_info
[regno
].preferred_hard_regno1
= hard_regno
;
555 lra_reg_info
[regno
].preferred_hard_regno_profit1
= profit
;
557 else if (lra_reg_info
[regno
].preferred_hard_regno2
< 0
558 || profit
> lra_reg_info
[regno
].preferred_hard_regno_profit2
)
560 lra_reg_info
[regno
].preferred_hard_regno2
= hard_regno
;
561 lra_reg_info
[regno
].preferred_hard_regno_profit2
= profit
;
565 /* Keep the 1st hard regno as more profitable. */
566 if (lra_reg_info
[regno
].preferred_hard_regno1
>= 0
567 && lra_reg_info
[regno
].preferred_hard_regno2
>= 0
568 && (lra_reg_info
[regno
].preferred_hard_regno_profit2
569 > lra_reg_info
[regno
].preferred_hard_regno_profit1
))
571 std::swap (lra_reg_info
[regno
].preferred_hard_regno1
,
572 lra_reg_info
[regno
].preferred_hard_regno2
);
573 std::swap (lra_reg_info
[regno
].preferred_hard_regno_profit1
,
574 lra_reg_info
[regno
].preferred_hard_regno_profit2
);
576 if (lra_dump_file
!= NULL
)
578 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno1
) >= 0)
579 fprintf (lra_dump_file
,
580 " Hard reg %d is preferable by r%d with profit %d\n",
582 lra_reg_info
[regno
].preferred_hard_regno_profit1
);
583 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno2
) >= 0)
584 fprintf (lra_dump_file
,
585 " Hard reg %d is preferable by r%d with profit %d\n",
587 lra_reg_info
[regno
].preferred_hard_regno_profit2
);
591 /* Check that REGNO living through calls and setjumps, set up conflict
592 regs, and clear corresponding bits in PSEUDOS_LIVE_THROUGH_CALLS and
593 PSEUDOS_LIVE_THROUGH_SETJUMPS. */
595 check_pseudos_live_through_calls (int regno
)
599 if (! sparseset_bit_p (pseudos_live_through_calls
, regno
))
601 sparseset_clear_bit (pseudos_live_through_calls
, regno
);
602 IOR_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
,
605 for (hr
= 0; hr
< FIRST_PSEUDO_REGISTER
; hr
++)
606 if (HARD_REGNO_CALL_PART_CLOBBERED (hr
, PSEUDO_REGNO_MODE (regno
)))
607 SET_HARD_REG_BIT (lra_reg_info
[regno
].conflict_hard_regs
, hr
);
608 #ifdef ENABLE_CHECKING
609 lra_reg_info
[regno
].call_p
= true;
611 if (! sparseset_bit_p (pseudos_live_through_setjumps
, regno
))
613 sparseset_clear_bit (pseudos_live_through_setjumps
, regno
);
614 /* Don't allocate pseudos that cross setjmps or any call, if this
615 function receives a nonlocal goto. */
616 SET_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
);
619 /* Process insns of the basic block BB to update pseudo live ranges,
620 pseudo hard register conflicts, and insn notes. We do it on
621 backward scan of BB insns. CURR_POINT is the program point where
622 BB ends. The function updates this counter and returns in
623 CURR_POINT the program point where BB starts. The function also
624 does local live info updates and can delete the dead insns if
625 DEAD_INSN_P. It returns true if pseudo live info was
626 changed at the BB start. */
628 process_bb_lives (basic_block bb
, int &curr_point
, bool dead_insn_p
)
637 bool need_curr_point_incr
;
639 reg_live_out
= df_get_live_out (bb
);
640 sparseset_clear (pseudos_live
);
641 sparseset_clear (pseudos_live_through_calls
);
642 sparseset_clear (pseudos_live_through_setjumps
);
643 REG_SET_TO_HARD_REG_SET (hard_regs_live
, reg_live_out
);
644 AND_COMPL_HARD_REG_SET (hard_regs_live
, eliminable_regset
);
645 EXECUTE_IF_SET_IN_BITMAP (reg_live_out
, FIRST_PSEUDO_REGISTER
, j
, bi
)
646 mark_pseudo_live (j
, curr_point
);
648 bb_gen_pseudos
= &get_bb_data (bb
)->gen_pseudos
;
649 bb_killed_pseudos
= &get_bb_data (bb
)->killed_pseudos
;
650 bitmap_clear (bb_gen_pseudos
);
651 bitmap_clear (bb_killed_pseudos
);
652 freq
= REG_FREQ_FROM_BB (bb
);
654 if (lra_dump_file
!= NULL
)
655 fprintf (lra_dump_file
, " BB %d\n", bb
->index
);
657 /* Scan the code of this basic block, noting which pseudos and hard
658 regs are born or die.
660 Note that this loop treats uninitialized values as live until the
661 beginning of the block. For example, if an instruction uses
662 (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
663 FOO will remain live until the beginning of the block. Likewise
664 if FOO is not set at all. This is unnecessarily pessimistic, but
665 it probably doesn't matter much in practice. */
666 FOR_BB_INSNS_REVERSE_SAFE (bb
, curr_insn
, next
)
669 int dst_regno
, src_regno
;
671 struct lra_insn_reg
*reg
;
673 if (!NONDEBUG_INSN_P (curr_insn
))
676 curr_id
= lra_get_insn_recog_data (curr_insn
);
677 curr_static_id
= curr_id
->insn_static_data
;
678 if (lra_dump_file
!= NULL
)
679 fprintf (lra_dump_file
, " Insn %u: point = %d\n",
680 INSN_UID (curr_insn
), curr_point
);
682 set
= single_set (curr_insn
);
684 if (dead_insn_p
&& set
!= NULL_RTX
685 && REG_P (SET_DEST (set
)) && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
686 && find_reg_note (curr_insn
, REG_EH_REGION
, NULL_RTX
) == NULL_RTX
687 && ! may_trap_p (PATTERN (curr_insn
))
688 /* Don't do premature remove of pic offset pseudo as we can
689 start to use it after some reload generation. */
690 && (pic_offset_table_rtx
== NULL_RTX
691 || pic_offset_table_rtx
!= SET_DEST (set
)))
693 bool remove_p
= true;
695 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
696 if (reg
->type
!= OP_IN
&& sparseset_bit_p (pseudos_live
, reg
->regno
))
701 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
702 if (reg
->type
!= OP_IN
)
707 if (remove_p
&& ! volatile_refs_p (PATTERN (curr_insn
)))
709 dst_regno
= REGNO (SET_DEST (set
));
710 if (lra_dump_file
!= NULL
)
711 fprintf (lra_dump_file
, " Deleting dead insn %u\n",
712 INSN_UID (curr_insn
));
713 lra_set_insn_deleted (curr_insn
);
714 if (lra_reg_info
[dst_regno
].nrefs
== 0)
716 /* There might be some debug insns with the pseudo. */
720 bitmap_copy (&temp_bitmap
, &lra_reg_info
[dst_regno
].insn_bitmap
);
721 EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap
, 0, uid
, bi
)
723 insn
= lra_insn_recog_data
[uid
]->insn
;
724 lra_substitute_pseudo_within_insn (insn
, dst_regno
,
725 SET_SRC (set
), true);
726 lra_update_insn_regno_info (insn
);
733 /* Update max ref width and hard reg usage. */
734 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
735 if (reg
->regno
>= FIRST_PSEUDO_REGISTER
736 && (GET_MODE_SIZE (reg
->biggest_mode
)
737 > GET_MODE_SIZE (lra_reg_info
[reg
->regno
].biggest_mode
)))
738 lra_reg_info
[reg
->regno
].biggest_mode
= reg
->biggest_mode
;
739 else if (reg
->regno
< FIRST_PSEUDO_REGISTER
)
740 lra_hard_reg_usage
[reg
->regno
] += freq
;
742 call_p
= CALL_P (curr_insn
);
745 && REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
))
746 /* Check that source regno does not conflict with
747 destination regno to exclude most impossible
749 && ((((src_regno
= REGNO (SET_SRC (set
))) >= FIRST_PSEUDO_REGISTER
750 && ! sparseset_bit_p (pseudos_live
, src_regno
))
751 || (src_regno
< FIRST_PSEUDO_REGISTER
752 && ! TEST_HARD_REG_BIT (hard_regs_live
, src_regno
)))
753 /* It might be 'inheritance pseudo <- reload pseudo'. */
754 || (src_regno
>= lra_constraint_new_regno_start
755 && ((int) REGNO (SET_DEST (set
))
756 >= lra_constraint_new_regno_start
)
757 /* Remember to skip special cases where src/dest regnos are
758 the same, e.g. insn SET pattern has matching constraints
760 && src_regno
!= (int) REGNO (SET_DEST (set
)))))
762 int hard_regno
= -1, regno
= -1;
764 dst_regno
= REGNO (SET_DEST (set
));
765 if (dst_regno
>= lra_constraint_new_regno_start
766 && src_regno
>= lra_constraint_new_regno_start
)
768 /* It might be still an original (non-reload) insn with
769 one unused output and a constraint requiring to use
770 the same reg for input/output operands. In this case
771 dst_regno and src_regno have the same value, we don't
772 need a misleading copy for this case. */
773 if (dst_regno
!= src_regno
)
774 lra_create_copy (dst_regno
, src_regno
, freq
);
776 else if (dst_regno
>= lra_constraint_new_regno_start
)
778 if ((hard_regno
= src_regno
) >= FIRST_PSEUDO_REGISTER
)
779 hard_regno
= reg_renumber
[src_regno
];
782 else if (src_regno
>= lra_constraint_new_regno_start
)
784 if ((hard_regno
= dst_regno
) >= FIRST_PSEUDO_REGISTER
)
785 hard_regno
= reg_renumber
[dst_regno
];
788 if (regno
>= 0 && hard_regno
>= 0)
789 lra_setup_reload_pseudo_preferenced_hard_reg
790 (regno
, hard_regno
, freq
);
793 sparseset_clear (start_living
);
795 /* Try to avoid unnecessary program point increments, this saves
796 a lot of time in remove_some_program_points_and_update_live_ranges.
797 We only need an increment if something becomes live or dies at this
799 need_curr_point_incr
= false;
801 /* Mark each defined value as live. We need to do this for
802 unused values because they still conflict with quantities
803 that are live at the time of the definition. */
804 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
805 if (reg
->type
!= OP_IN
)
808 |= mark_regno_live (reg
->regno
, reg
->biggest_mode
,
810 check_pseudos_live_through_calls (reg
->regno
);
813 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
814 if (reg
->type
!= OP_IN
)
815 make_hard_regno_born (reg
->regno
, false);
817 sparseset_copy (unused_set
, start_living
);
819 sparseset_clear (start_dying
);
821 /* See which defined values die here. */
822 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
823 if (reg
->type
== OP_OUT
&& ! reg
->early_clobber
&& ! reg
->subreg_p
)
825 |= mark_regno_dead (reg
->regno
, reg
->biggest_mode
,
828 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
829 if (reg
->type
== OP_OUT
&& ! reg
->early_clobber
&& ! reg
->subreg_p
)
830 make_hard_regno_dead (reg
->regno
);
836 HARD_REG_SET this_call_used_reg_set
;
837 get_call_reg_set_usage (curr_insn
, &this_call_used_reg_set
,
840 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, j
)
841 IOR_HARD_REG_SET (lra_reg_info
[j
].actual_call_used_reg_set
,
842 this_call_used_reg_set
);
845 sparseset_ior (pseudos_live_through_calls
,
846 pseudos_live_through_calls
, pseudos_live
);
847 if (cfun
->has_nonlocal_label
848 || find_reg_note (curr_insn
, REG_SETJMP
,
849 NULL_RTX
) != NULL_RTX
)
850 sparseset_ior (pseudos_live_through_setjumps
,
851 pseudos_live_through_setjumps
, pseudos_live
);
854 /* Increment the current program point if we must. */
855 if (need_curr_point_incr
)
856 next_program_point (curr_point
, freq
);
858 sparseset_clear (start_living
);
860 need_curr_point_incr
= false;
862 /* Mark each used value as live. */
863 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
864 if (reg
->type
== OP_IN
)
867 |= mark_regno_live (reg
->regno
, reg
->biggest_mode
,
869 check_pseudos_live_through_calls (reg
->regno
);
872 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
873 if (reg
->type
== OP_IN
)
874 make_hard_regno_born (reg
->regno
, false);
876 if (curr_id
->arg_hard_regs
!= NULL
)
877 /* Make argument hard registers live. Don't create conflict
878 of used REAL_PIC_OFFSET_TABLE_REGNUM and the pic pseudo. */
879 for (i
= 0; (regno
= curr_id
->arg_hard_regs
[i
]) >= 0; i
++)
880 make_hard_regno_born (regno
, true);
882 sparseset_and_compl (dead_set
, start_living
, start_dying
);
884 /* Mark early clobber outputs dead. */
885 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
886 if (reg
->type
== OP_OUT
&& reg
->early_clobber
&& ! reg
->subreg_p
)
888 |= mark_regno_dead (reg
->regno
, reg
->biggest_mode
,
891 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
892 if (reg
->type
== OP_OUT
&& reg
->early_clobber
&& ! reg
->subreg_p
)
893 make_hard_regno_dead (reg
->regno
);
895 if (need_curr_point_incr
)
896 next_program_point (curr_point
, freq
);
899 for (link_loc
= ®_NOTES (curr_insn
); (link
= *link_loc
) != NULL_RTX
;)
901 if (REG_NOTE_KIND (link
) != REG_DEAD
902 && REG_NOTE_KIND (link
) != REG_UNUSED
)
904 else if (REG_P (XEXP (link
, 0)))
906 regno
= REGNO (XEXP (link
, 0));
907 if ((REG_NOTE_KIND (link
) == REG_DEAD
908 && ! sparseset_bit_p (dead_set
, regno
))
909 || (REG_NOTE_KIND (link
) == REG_UNUSED
910 && ! sparseset_bit_p (unused_set
, regno
)))
912 *link_loc
= XEXP (link
, 1);
915 if (REG_NOTE_KIND (link
) == REG_DEAD
)
916 sparseset_clear_bit (dead_set
, regno
);
917 else if (REG_NOTE_KIND (link
) == REG_UNUSED
)
918 sparseset_clear_bit (unused_set
, regno
);
920 link_loc
= &XEXP (link
, 1);
922 EXECUTE_IF_SET_IN_SPARSESET (dead_set
, j
)
923 add_reg_note (curr_insn
, REG_DEAD
, regno_reg_rtx
[j
]);
924 EXECUTE_IF_SET_IN_SPARSESET (unused_set
, j
)
925 add_reg_note (curr_insn
, REG_UNUSED
, regno_reg_rtx
[j
]);
928 if (bb_has_eh_pred (bb
))
931 unsigned int regno
= EH_RETURN_DATA_REGNO (j
);
933 if (regno
== INVALID_REGNUM
)
935 make_hard_regno_born (regno
, false);
938 /* Pseudos can't go in stack regs at the start of a basic block that
939 is reached by an abnormal edge. Likewise for call clobbered regs,
940 because caller-save, fixup_abnormal_edges and possibly the table
941 driven EH machinery are not quite ready to handle such pseudos
942 live across such edges. */
943 if (bb_has_abnormal_pred (bb
))
946 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, px
)
947 lra_reg_info
[px
].no_stack_p
= true;
948 for (px
= FIRST_STACK_REG
; px
<= LAST_STACK_REG
; px
++)
949 make_hard_regno_born (px
, false);
951 /* No need to record conflicts for call clobbered regs if we
952 have nonlocal labels around, as we don't ever try to
953 allocate such regs in this case. */
954 if (!cfun
->has_nonlocal_label
&& bb_has_abnormal_call_pred (bb
))
955 for (px
= 0; px
< FIRST_PSEUDO_REGISTER
; px
++)
956 if (call_used_regs
[px
])
957 make_hard_regno_born (px
, false);
960 bool live_change_p
= false;
961 /* Check if bb border live info was changed. */
962 unsigned int live_pseudos_num
= 0;
963 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb
),
964 FIRST_PSEUDO_REGISTER
, j
, bi
)
967 if (! sparseset_bit_p (pseudos_live
, j
))
969 live_change_p
= true;
970 if (lra_dump_file
!= NULL
)
971 fprintf (lra_dump_file
,
972 " r%d is removed as live at bb%d start\n", j
, bb
->index
);
977 && sparseset_cardinality (pseudos_live
) != live_pseudos_num
)
979 live_change_p
= true;
980 if (lra_dump_file
!= NULL
)
981 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, j
)
982 if (! bitmap_bit_p (df_get_live_in (bb
), j
))
983 fprintf (lra_dump_file
,
984 " r%d is added to live at bb%d start\n", j
, bb
->index
);
986 /* See if we'll need an increment at the end of this basic block.
987 An increment is needed if the PSEUDOS_LIVE set is not empty,
988 to make sure the finish points are set up correctly. */
989 need_curr_point_incr
= (sparseset_cardinality (pseudos_live
) > 0);
991 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, i
)
992 mark_pseudo_dead (i
, curr_point
);
994 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb
), FIRST_PSEUDO_REGISTER
, j
, bi
)
996 if (sparseset_cardinality (pseudos_live_through_calls
) == 0)
998 if (sparseset_bit_p (pseudos_live_through_calls
, j
))
999 check_pseudos_live_through_calls (j
);
1002 if (need_curr_point_incr
)
1003 next_program_point (curr_point
, freq
);
1005 return live_change_p
;
1008 /* Compress pseudo live ranges by removing program points where
1009 nothing happens. Complexity of many algorithms in LRA is linear
1010 function of program points number. To speed up the code we try to
1011 minimize the number of the program points here. */
1013 remove_some_program_points_and_update_live_ranges (void)
1018 lra_live_range_t r
, prev_r
, next_r
;
1019 sbitmap born_or_dead
, born
, dead
;
1020 sbitmap_iterator sbi
;
1021 bool born_p
, dead_p
, prev_born_p
, prev_dead_p
;
1023 born
= sbitmap_alloc (lra_live_max_point
);
1024 dead
= sbitmap_alloc (lra_live_max_point
);
1025 bitmap_clear (born
);
1026 bitmap_clear (dead
);
1027 max_regno
= max_reg_num ();
1028 for (i
= FIRST_PSEUDO_REGISTER
; i
< (unsigned) max_regno
; i
++)
1030 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
1032 lra_assert (r
->start
<= r
->finish
);
1033 bitmap_set_bit (born
, r
->start
);
1034 bitmap_set_bit (dead
, r
->finish
);
1037 born_or_dead
= sbitmap_alloc (lra_live_max_point
);
1038 bitmap_ior (born_or_dead
, born
, dead
);
1039 map
= XCNEWVEC (int, lra_live_max_point
);
1041 prev_born_p
= prev_dead_p
= false;
1042 EXECUTE_IF_SET_IN_BITMAP (born_or_dead
, 0, i
, sbi
)
1044 born_p
= bitmap_bit_p (born
, i
);
1045 dead_p
= bitmap_bit_p (dead
, i
);
1046 if ((prev_born_p
&& ! prev_dead_p
&& born_p
&& ! dead_p
)
1047 || (prev_dead_p
&& ! prev_born_p
&& dead_p
&& ! born_p
))
1050 lra_point_freq
[n
] = MAX (lra_point_freq
[n
], lra_point_freq
[i
]);
1055 lra_point_freq
[n
] = lra_point_freq
[i
];
1057 prev_born_p
= born_p
;
1058 prev_dead_p
= dead_p
;
1060 sbitmap_free (born_or_dead
);
1061 sbitmap_free (born
);
1062 sbitmap_free (dead
);
1064 if (lra_dump_file
!= NULL
)
1065 fprintf (lra_dump_file
, "Compressing live ranges: from %d to %d - %d%%\n",
1066 lra_live_max_point
, n
, 100 * n
/ lra_live_max_point
);
1067 if (n
< lra_live_max_point
)
1069 lra_live_max_point
= n
;
1070 for (i
= FIRST_PSEUDO_REGISTER
; i
< (unsigned) max_regno
; i
++)
1072 for (prev_r
= NULL
, r
= lra_reg_info
[i
].live_ranges
;
1077 r
->start
= map
[r
->start
];
1078 r
->finish
= map
[r
->finish
];
1079 if (prev_r
== NULL
|| prev_r
->start
> r
->finish
+ 1)
1084 prev_r
->start
= r
->start
;
1085 prev_r
->next
= next_r
;
1093 /* Print live ranges R to file F. */
1095 lra_print_live_range_list (FILE *f
, lra_live_range_t r
)
1097 for (; r
!= NULL
; r
= r
->next
)
1098 fprintf (f
, " [%d..%d]", r
->start
, r
->finish
);
1103 debug (lra_live_range
&ref
)
1105 lra_print_live_range_list (stderr
, &ref
);
1109 debug (lra_live_range
*ptr
)
1114 fprintf (stderr
, "<nil>\n");
1117 /* Print live ranges R to stderr. */
1119 lra_debug_live_range_list (lra_live_range_t r
)
1121 lra_print_live_range_list (stderr
, r
);
1124 /* Print live ranges of pseudo REGNO to file F. */
1126 print_pseudo_live_ranges (FILE *f
, int regno
)
1128 if (lra_reg_info
[regno
].live_ranges
== NULL
)
1130 fprintf (f
, " r%d:", regno
);
1131 lra_print_live_range_list (f
, lra_reg_info
[regno
].live_ranges
);
1134 /* Print live ranges of pseudo REGNO to stderr. */
1136 lra_debug_pseudo_live_ranges (int regno
)
1138 print_pseudo_live_ranges (stderr
, regno
);
1141 /* Print live ranges of all pseudos to file F. */
1143 print_live_ranges (FILE *f
)
1147 max_regno
= max_reg_num ();
1148 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1149 print_pseudo_live_ranges (f
, i
);
1152 /* Print live ranges of all pseudos to stderr. */
1154 lra_debug_live_ranges (void)
1156 print_live_ranges (stderr
);
1159 /* Compress pseudo live ranges. */
1161 compress_live_ranges (void)
1163 remove_some_program_points_and_update_live_ranges ();
1164 if (lra_dump_file
!= NULL
)
1166 fprintf (lra_dump_file
, "Ranges after the compression:\n");
1167 print_live_ranges (lra_dump_file
);
1173 /* The number of the current live range pass. */
1174 int lra_live_range_iter
;
1176 /* The function creates live ranges only for memory pseudos (or for
1177 all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos. It
1178 also does dead insn elimination if DEAD_INSN_P and global live
1179 analysis only for pseudos and only if the pseudo live info was
1180 changed on a BB border. Return TRUE if the live info was
1183 lra_create_live_ranges_1 (bool all_p
, bool dead_insn_p
)
1186 int i
, hard_regno
, max_regno
= max_reg_num ();
1188 bool bb_live_change_p
, have_referenced_pseudos
= false;
1190 timevar_push (TV_LRA_CREATE_LIVE_RANGES
);
1192 complete_info_p
= all_p
;
1193 if (lra_dump_file
!= NULL
)
1194 fprintf (lra_dump_file
,
1195 "\n********** Pseudo live ranges #%d: **********\n\n",
1196 ++lra_live_range_iter
);
1197 memset (lra_hard_reg_usage
, 0, sizeof (lra_hard_reg_usage
));
1198 for (i
= 0; i
< max_regno
; i
++)
1200 lra_reg_info
[i
].live_ranges
= NULL
;
1201 CLEAR_HARD_REG_SET (lra_reg_info
[i
].conflict_hard_regs
);
1202 lra_reg_info
[i
].preferred_hard_regno1
= -1;
1203 lra_reg_info
[i
].preferred_hard_regno2
= -1;
1204 lra_reg_info
[i
].preferred_hard_regno_profit1
= 0;
1205 lra_reg_info
[i
].preferred_hard_regno_profit2
= 0;
1207 lra_reg_info
[i
].no_stack_p
= false;
1209 /* The biggest mode is already set but its value might be to
1210 conservative because of recent transformation. Here in this
1211 file we recalculate it again as it costs practically
1213 if (regno_reg_rtx
[i
] != NULL_RTX
)
1214 lra_reg_info
[i
].biggest_mode
= GET_MODE (regno_reg_rtx
[i
]);
1216 lra_reg_info
[i
].biggest_mode
= VOIDmode
;
1217 #ifdef ENABLE_CHECKING
1218 lra_reg_info
[i
].call_p
= false;
1220 if (i
>= FIRST_PSEUDO_REGISTER
1221 && lra_reg_info
[i
].nrefs
!= 0)
1223 if ((hard_regno
= reg_renumber
[i
]) >= 0)
1224 lra_hard_reg_usage
[hard_regno
] += lra_reg_info
[i
].freq
;
1225 have_referenced_pseudos
= true;
1230 /* Under some circumstances, we can have functions without pseudo
1231 registers. For such functions, lra_live_max_point will be 0,
1232 see e.g. PR55604, and there's nothing more to do for us here. */
1233 if (! have_referenced_pseudos
)
1235 timevar_pop (TV_LRA_CREATE_LIVE_RANGES
);
1239 pseudos_live
= sparseset_alloc (max_regno
);
1240 pseudos_live_through_calls
= sparseset_alloc (max_regno
);
1241 pseudos_live_through_setjumps
= sparseset_alloc (max_regno
);
1242 start_living
= sparseset_alloc (max_regno
);
1243 start_dying
= sparseset_alloc (max_regno
);
1244 dead_set
= sparseset_alloc (max_regno
);
1245 unused_set
= sparseset_alloc (max_regno
);
1247 point_freq_vec
.create (get_max_uid () * 2);
1248 lra_point_freq
= point_freq_vec
.address ();
1249 int *post_order_rev_cfg
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1250 int n_blocks_inverted
= inverted_post_order_compute (post_order_rev_cfg
);
1251 lra_assert (n_blocks_inverted
== n_basic_blocks_for_fn (cfun
));
1252 bb_live_change_p
= false;
1253 for (i
= n_blocks_inverted
- 1; i
>= 0; --i
)
1255 bb
= BASIC_BLOCK_FOR_FN (cfun
, post_order_rev_cfg
[i
]);
1256 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
1257 == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1259 if (process_bb_lives (bb
, curr_point
, dead_insn_p
))
1260 bb_live_change_p
= true;
1262 if (bb_live_change_p
)
1264 /* We need to clear pseudo live info as some pseudos can
1265 disappear, e.g. pseudos with used equivalences. */
1266 FOR_EACH_BB_FN (bb
, cfun
)
1268 bitmap_clear_range (df_get_live_in (bb
), FIRST_PSEUDO_REGISTER
,
1269 max_regno
- FIRST_PSEUDO_REGISTER
);
1270 bitmap_clear_range (df_get_live_out (bb
), FIRST_PSEUDO_REGISTER
,
1271 max_regno
- FIRST_PSEUDO_REGISTER
);
1273 /* As we did not change CFG since LRA start we can use
1274 DF-infrastructure solver to solve live data flow problem. */
1276 (DF_BACKWARD
, NULL
, live_con_fun_0
, live_con_fun_n
,
1277 live_trans_fun
, &all_blocks
,
1278 df_get_postorder (DF_BACKWARD
), df_get_n_blocks (DF_BACKWARD
));
1279 if (lra_dump_file
!= NULL
)
1281 fprintf (lra_dump_file
,
1282 "Global pseudo live data have been updated:\n");
1284 FOR_EACH_BB_FN (bb
, cfun
)
1286 bb_data_t bb_info
= get_bb_data (bb
);
1287 bitmap bb_livein
= df_get_live_in (bb
);
1288 bitmap bb_liveout
= df_get_live_out (bb
);
1290 fprintf (lra_dump_file
, "\nBB %d:\n", bb
->index
);
1291 lra_dump_bitmap_with_title (" gen:",
1292 &bb_info
->gen_pseudos
, bb
->index
);
1293 lra_dump_bitmap_with_title (" killed:",
1294 &bb_info
->killed_pseudos
, bb
->index
);
1295 lra_dump_bitmap_with_title (" livein:", bb_livein
, bb
->index
);
1296 lra_dump_bitmap_with_title (" liveout:", bb_liveout
, bb
->index
);
1300 free (post_order_rev_cfg
);
1301 lra_live_max_point
= curr_point
;
1302 if (lra_dump_file
!= NULL
)
1303 print_live_ranges (lra_dump_file
);
1305 sparseset_free (unused_set
);
1306 sparseset_free (dead_set
);
1307 sparseset_free (start_dying
);
1308 sparseset_free (start_living
);
1309 sparseset_free (pseudos_live_through_calls
);
1310 sparseset_free (pseudos_live_through_setjumps
);
1311 sparseset_free (pseudos_live
);
1312 compress_live_ranges ();
1313 timevar_pop (TV_LRA_CREATE_LIVE_RANGES
);
1314 return bb_live_change_p
;
1317 /* The main entry function creates live-ranges and other live info
1318 necessary for the assignment sub-pass. It uses
1319 lra_creates_live_ranges_1 -- so read comments for the
1322 lra_create_live_ranges (bool all_p
, bool dead_insn_p
)
1324 if (! lra_create_live_ranges_1 (all_p
, dead_insn_p
))
1326 if (lra_dump_file
!= NULL
)
1327 fprintf (lra_dump_file
, "Live info was changed -- recalculate it\n");
1328 /* Live info was changed on a bb border. It means that some info,
1329 e.g. about conflict regs, calls crossed, and live ranges may be
1330 wrong. We need this info for allocation. So recalculate it
1331 again but without removing dead insns which can change live info
1332 again. Repetitive live range calculations are expensive therefore
1333 we stop here as we already have correct info although some
1334 improvement in rare cases could be possible on this sub-pass if
1335 we do dead insn elimination again (still the improvement may
1337 lra_clear_live_ranges ();
1338 bool res
= lra_create_live_ranges_1 (all_p
, false);
1342 /* Finish all live ranges. */
1344 lra_clear_live_ranges (void)
1348 for (i
= 0; i
< max_reg_num (); i
++)
1349 free_live_range_list (lra_reg_info
[i
].live_ranges
);
1350 point_freq_vec
.release ();
1353 /* Initialize live ranges data once per function. */
1355 lra_live_ranges_init (void)
1357 bitmap_initialize (&temp_bitmap
, ®_obstack
);
1358 initiate_live_solver ();
1361 /* Finish live ranges data once per function. */
1363 lra_live_ranges_finish (void)
1365 finish_live_solver ();
1366 bitmap_clear (&temp_bitmap
);
1367 lra_live_range::pool
.release ();