1 /* Build live ranges for pseudos.
2 Copyright (C) 2010-2014 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 "dominance.h"
50 #include "basic-block.h"
54 #include "sparseset.h"
57 /* Program points are enumerated by numbers from range
58 0..LRA_LIVE_MAX_POINT-1. There are approximately two times more
59 program points than insns. Program points are places in the
60 program where liveness info can be changed. In most general case
61 (there are more complicated cases too) some program points
62 correspond to places where input operand dies and other ones
63 correspond to places where output operands are born. */
64 int lra_live_max_point
;
66 /* Accumulated execution frequency of all references for each hard
68 int lra_hard_reg_usage
[FIRST_PSEUDO_REGISTER
];
70 /* A global flag whose true value says to build live ranges for all
71 pseudos, otherwise the live ranges only for pseudos got memory is
72 build. True value means also building copies and setting up hard
73 register preferences. The complete info is necessary only for the
74 assignment pass. The complete info is not needed for the
75 coalescing and spill passes. */
76 static bool complete_info_p
;
78 /* Pseudos live at current point in the RTL scan. */
79 static sparseset pseudos_live
;
81 /* Pseudos probably living through calls and setjumps. As setjump is
82 a call too, if a bit in PSEUDOS_LIVE_THROUGH_SETJUMPS is set up
83 then the corresponding bit in PSEUDOS_LIVE_THROUGH_CALLS is set up
84 too. These data are necessary for cases when only one subreg of a
85 multi-reg pseudo is set up after a call. So we decide it is
86 probably live when traversing bb backward. We are sure about
87 living when we see its usage or definition of the pseudo. */
88 static sparseset pseudos_live_through_calls
;
89 static sparseset pseudos_live_through_setjumps
;
91 /* Set of hard regs (except eliminable ones) currently live. */
92 static HARD_REG_SET hard_regs_live
;
94 /* Set of pseudos and hard registers start living/dying in the current
95 insn. These sets are used to update REG_DEAD and REG_UNUSED notes
97 static sparseset start_living
, start_dying
;
99 /* Set of pseudos and hard regs dead and unused in the current
101 static sparseset unused_set
, dead_set
;
103 /* Bitmap used for holding intermediate bitmap operation results. */
104 static bitmap_head temp_bitmap
;
106 /* Pool for pseudo live ranges. */
107 static alloc_pool live_range_pool
;
109 /* Free live range LR. */
111 free_live_range (lra_live_range_t lr
)
113 pool_free (live_range_pool
, lr
);
116 /* Free live range list LR. */
118 free_live_range_list (lra_live_range_t lr
)
120 lra_live_range_t next
;
125 free_live_range (lr
);
130 /* Create and return pseudo live range with given attributes. */
131 static lra_live_range_t
132 create_live_range (int regno
, int start
, int finish
, lra_live_range_t next
)
136 p
= (lra_live_range_t
) pool_alloc (live_range_pool
);
144 /* Copy live range R and return the result. */
145 static lra_live_range_t
146 copy_live_range (lra_live_range_t r
)
150 p
= (lra_live_range_t
) pool_alloc (live_range_pool
);
155 /* Copy live range list given by its head R and return the result. */
157 lra_copy_live_range_list (lra_live_range_t r
)
159 lra_live_range_t p
, first
, *chain
;
162 for (chain
= &first
; r
!= NULL
; r
= r
->next
)
164 p
= copy_live_range (r
);
171 /* Merge *non-intersected* ranges R1 and R2 and returns the result.
172 The function maintains the order of ranges and tries to minimize
173 size of the result range list. Ranges R1 and R2 may not be used
176 lra_merge_live_ranges (lra_live_range_t r1
, lra_live_range_t r2
)
178 lra_live_range_t first
, last
, temp
;
184 for (first
= last
= NULL
; r1
!= NULL
&& r2
!= NULL
;)
186 if (r1
->start
< r2
->start
)
192 if (r1
->start
== r2
->finish
+ 1)
194 /* Joint ranges: merge r1 and r2 into r1. */
195 r1
->start
= r2
->start
;
198 pool_free (live_range_pool
, temp
);
202 gcc_assert (r2
->finish
+ 1 < r1
->start
);
203 /* Add r1 to the result. */
223 lra_assert (r2
!= NULL
);
232 /* Return TRUE if live ranges R1 and R2 intersect. */
234 lra_intersected_live_ranges_p (lra_live_range_t r1
, lra_live_range_t r2
)
236 /* Remember the live ranges are always kept ordered. */
237 while (r1
!= NULL
&& r2
!= NULL
)
239 if (r1
->start
> r2
->finish
)
241 else if (r2
->start
> r1
->finish
)
249 /* The function processing birth of hard register REGNO. It updates
250 living hard regs, conflict hard regs for living pseudos, and
253 make_hard_regno_born (int regno
)
257 lra_assert (regno
< FIRST_PSEUDO_REGISTER
);
258 if (TEST_HARD_REG_BIT (hard_regs_live
, regno
))
260 SET_HARD_REG_BIT (hard_regs_live
, regno
);
261 sparseset_set_bit (start_living
, regno
);
262 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, i
)
263 SET_HARD_REG_BIT (lra_reg_info
[i
].conflict_hard_regs
, regno
);
266 /* Process the death of hard register REGNO. This updates
267 hard_regs_live and START_DYING. */
269 make_hard_regno_dead (int regno
)
271 lra_assert (regno
< FIRST_PSEUDO_REGISTER
);
272 if (! TEST_HARD_REG_BIT (hard_regs_live
, regno
))
274 sparseset_set_bit (start_dying
, regno
);
275 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
278 /* Mark pseudo REGNO as living at program point POINT, update conflicting
279 hard registers of the pseudo and START_LIVING, and start a new live
280 range for the pseudo corresponding to REGNO if it is necessary. */
282 mark_pseudo_live (int regno
, int point
)
286 lra_assert (regno
>= FIRST_PSEUDO_REGISTER
);
287 lra_assert (! sparseset_bit_p (pseudos_live
, regno
));
288 sparseset_set_bit (pseudos_live
, regno
);
289 IOR_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
, hard_regs_live
);
291 if ((complete_info_p
|| lra_get_regno_hard_regno (regno
) < 0)
292 && ((p
= lra_reg_info
[regno
].live_ranges
) == NULL
293 || (p
->finish
!= point
&& p
->finish
+ 1 != point
)))
294 lra_reg_info
[regno
].live_ranges
295 = create_live_range (regno
, point
, -1, p
);
296 sparseset_set_bit (start_living
, regno
);
299 /* Mark pseudo REGNO as not living at program point POINT and update
301 This finishes the current live range for the pseudo corresponding
304 mark_pseudo_dead (int regno
, int point
)
308 lra_assert (regno
>= FIRST_PSEUDO_REGISTER
);
309 lra_assert (sparseset_bit_p (pseudos_live
, regno
));
310 sparseset_clear_bit (pseudos_live
, regno
);
311 sparseset_set_bit (start_dying
, regno
);
312 if (complete_info_p
|| lra_get_regno_hard_regno (regno
) < 0)
314 p
= lra_reg_info
[regno
].live_ranges
;
315 lra_assert (p
!= NULL
);
320 /* The corresponding bitmaps of BB currently being processed. */
321 static bitmap bb_killed_pseudos
, bb_gen_pseudos
;
323 /* Mark register REGNO (pseudo or hard register) in MODE as live at
324 program point POINT. Update BB_GEN_PSEUDOS if LOCAL_SETS_P.
325 Return TRUE if the liveness tracking sets were modified, or FALSE
326 if nothing changed. */
328 mark_regno_live (int regno
, machine_mode mode
, int point
, bool local_sets_p
)
331 bool changed
= false;
333 if (regno
< FIRST_PSEUDO_REGISTER
)
335 for (last
= regno
+ hard_regno_nregs
[regno
][mode
];
338 make_hard_regno_born (regno
);
342 if (! sparseset_bit_p (pseudos_live
, regno
))
344 mark_pseudo_live (regno
, point
);
348 bitmap_set_bit (bb_gen_pseudos
, regno
);
354 /* Mark register REGNO in MODE as dead at program point POINT. Update
355 BB_GEN_PSEUDOS and BB_KILLED_PSEUDOS if LOCAL_SETS_P. Return TRUE
356 if the liveness tracking sets were modified, or FALSE if nothing
359 mark_regno_dead (int regno
, machine_mode mode
, int point
, bool local_sets_p
)
362 bool changed
= false;
364 if (regno
< FIRST_PSEUDO_REGISTER
)
366 for (last
= regno
+ hard_regno_nregs
[regno
][mode
];
369 make_hard_regno_dead (regno
);
373 if (sparseset_bit_p (pseudos_live
, regno
))
375 mark_pseudo_dead (regno
, point
);
380 bitmap_clear_bit (bb_gen_pseudos
, regno
);
381 bitmap_set_bit (bb_killed_pseudos
, regno
);
389 /* This page contains code for making global live analysis of pseudos.
390 The code works only when pseudo live info is changed on a BB
391 border. That might be a consequence of some global transformations
392 in LRA, e.g. PIC pseudo reuse or rematerialization. */
394 /* Structure describing local BB data used for pseudo
396 struct bb_data_pseudos
398 /* Basic block about which the below data are. */
400 bitmap_head killed_pseudos
; /* pseudos killed in the BB. */
401 bitmap_head gen_pseudos
; /* pseudos generated in the BB. */
404 /* Array for all BB data. Indexed by the corresponding BB index. */
405 typedef struct bb_data_pseudos
*bb_data_t
;
407 /* All basic block data are referred through the following array. */
408 static bb_data_t bb_data
;
410 /* Two small functions for access to the bb data. */
411 static inline bb_data_t
412 get_bb_data (basic_block bb
)
414 return &bb_data
[(bb
)->index
];
417 static inline bb_data_t
418 get_bb_data_by_index (int index
)
420 return &bb_data
[index
];
423 /* Bitmap with all hard regs. */
424 static bitmap_head all_hard_regs_bitmap
;
426 /* The transfer function used by the DF equation solver to propagate
427 live info through block with BB_INDEX according to the following
430 bb.livein = (bb.liveout - bb.kill) OR bb.gen
433 live_trans_fun (int bb_index
)
435 basic_block bb
= get_bb_data_by_index (bb_index
)->bb
;
436 bitmap bb_liveout
= df_get_live_out (bb
);
437 bitmap bb_livein
= df_get_live_in (bb
);
438 bb_data_t bb_info
= get_bb_data (bb
);
440 bitmap_and_compl (&temp_bitmap
, bb_liveout
, &all_hard_regs_bitmap
);
441 return bitmap_ior_and_compl (bb_livein
, &bb_info
->gen_pseudos
,
442 &temp_bitmap
, &bb_info
->killed_pseudos
);
445 /* The confluence function used by the DF equation solver to set up
446 live info for a block BB without predecessor. */
448 live_con_fun_0 (basic_block bb
)
450 bitmap_and_into (df_get_live_out (bb
), &all_hard_regs_bitmap
);
453 /* The confluence function used by the DF equation solver to propagate
454 live info from successor to predecessor on edge E according to the
457 bb.liveout = 0 for entry block | OR (livein of successors)
460 live_con_fun_n (edge e
)
462 basic_block bb
= e
->src
;
463 basic_block dest
= e
->dest
;
464 bitmap bb_liveout
= df_get_live_out (bb
);
465 bitmap dest_livein
= df_get_live_in (dest
);
467 return bitmap_ior_and_compl_into (bb_liveout
,
468 dest_livein
, &all_hard_regs_bitmap
);
471 /* Indexes of all function blocks. */
472 static bitmap_head all_blocks
;
474 /* Allocate and initialize data needed for global pseudo live
477 initiate_live_solver (void)
479 bitmap_initialize (&all_hard_regs_bitmap
, ®_obstack
);
480 bitmap_set_range (&all_hard_regs_bitmap
, 0, FIRST_PSEUDO_REGISTER
);
481 bb_data
= XNEWVEC (struct bb_data_pseudos
, last_basic_block_for_fn (cfun
));
482 bitmap_initialize (&all_blocks
, ®_obstack
);
485 FOR_ALL_BB_FN (bb
, cfun
)
487 bb_data_t bb_info
= get_bb_data (bb
);
489 bitmap_initialize (&bb_info
->killed_pseudos
, ®_obstack
);
490 bitmap_initialize (&bb_info
->gen_pseudos
, ®_obstack
);
491 bitmap_set_bit (&all_blocks
, bb
->index
);
495 /* Free all data needed for global pseudo live analysis. */
497 finish_live_solver (void)
501 bitmap_clear (&all_blocks
);
502 FOR_ALL_BB_FN (bb
, cfun
)
504 bb_data_t bb_info
= get_bb_data (bb
);
505 bitmap_clear (&bb_info
->killed_pseudos
);
506 bitmap_clear (&bb_info
->gen_pseudos
);
509 bitmap_clear (&all_hard_regs_bitmap
);
514 /* Insn currently scanned. */
515 static rtx_insn
*curr_insn
;
517 static lra_insn_recog_data_t curr_id
;
518 /* The insn static data. */
519 static struct lra_static_insn_data
*curr_static_id
;
521 /* Return true when one of the predecessor edges of BB is marked with
522 EDGE_ABNORMAL_CALL or EDGE_EH. */
524 bb_has_abnormal_call_pred (basic_block bb
)
529 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
531 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
537 /* Vec containing execution frequencies of program points. */
538 static vec
<int> point_freq_vec
;
540 /* The start of the above vector elements. */
543 /* Increment the current program point POINT to the next point which has
544 execution frequency FREQ. */
546 next_program_point (int &point
, int freq
)
548 point_freq_vec
.safe_push (freq
);
549 lra_point_freq
= point_freq_vec
.address ();
553 /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
555 lra_setup_reload_pseudo_preferenced_hard_reg (int regno
,
556 int hard_regno
, int profit
)
558 lra_assert (regno
>= lra_constraint_new_regno_start
);
559 if (lra_reg_info
[regno
].preferred_hard_regno1
== hard_regno
)
560 lra_reg_info
[regno
].preferred_hard_regno_profit1
+= profit
;
561 else if (lra_reg_info
[regno
].preferred_hard_regno2
== hard_regno
)
562 lra_reg_info
[regno
].preferred_hard_regno_profit2
+= profit
;
563 else if (lra_reg_info
[regno
].preferred_hard_regno1
< 0)
565 lra_reg_info
[regno
].preferred_hard_regno1
= hard_regno
;
566 lra_reg_info
[regno
].preferred_hard_regno_profit1
= profit
;
568 else if (lra_reg_info
[regno
].preferred_hard_regno2
< 0
569 || profit
> lra_reg_info
[regno
].preferred_hard_regno_profit2
)
571 lra_reg_info
[regno
].preferred_hard_regno2
= hard_regno
;
572 lra_reg_info
[regno
].preferred_hard_regno_profit2
= profit
;
576 /* Keep the 1st hard regno as more profitable. */
577 if (lra_reg_info
[regno
].preferred_hard_regno1
>= 0
578 && lra_reg_info
[regno
].preferred_hard_regno2
>= 0
579 && (lra_reg_info
[regno
].preferred_hard_regno_profit2
580 > lra_reg_info
[regno
].preferred_hard_regno_profit1
))
584 temp
= lra_reg_info
[regno
].preferred_hard_regno1
;
585 lra_reg_info
[regno
].preferred_hard_regno1
586 = lra_reg_info
[regno
].preferred_hard_regno2
;
587 lra_reg_info
[regno
].preferred_hard_regno2
= temp
;
588 temp
= lra_reg_info
[regno
].preferred_hard_regno_profit1
;
589 lra_reg_info
[regno
].preferred_hard_regno_profit1
590 = lra_reg_info
[regno
].preferred_hard_regno_profit2
;
591 lra_reg_info
[regno
].preferred_hard_regno_profit2
= temp
;
593 if (lra_dump_file
!= NULL
)
595 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno1
) >= 0)
596 fprintf (lra_dump_file
,
597 " Hard reg %d is preferable by r%d with profit %d\n",
599 lra_reg_info
[regno
].preferred_hard_regno_profit1
);
600 if ((hard_regno
= lra_reg_info
[regno
].preferred_hard_regno2
) >= 0)
601 fprintf (lra_dump_file
,
602 " Hard reg %d is preferable by r%d with profit %d\n",
604 lra_reg_info
[regno
].preferred_hard_regno_profit2
);
608 /* Check that REGNO living through calls and setjumps, set up conflict
609 regs, and clear corresponding bits in PSEUDOS_LIVE_THROUGH_CALLS and
610 PSEUDOS_LIVE_THROUGH_SETJUMPS. */
612 check_pseudos_live_through_calls (int regno
)
616 if (! sparseset_bit_p (pseudos_live_through_calls
, regno
))
618 sparseset_clear_bit (pseudos_live_through_calls
, regno
);
619 IOR_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
,
622 for (hr
= 0; hr
< FIRST_PSEUDO_REGISTER
; hr
++)
623 if (HARD_REGNO_CALL_PART_CLOBBERED (hr
, PSEUDO_REGNO_MODE (regno
)))
624 SET_HARD_REG_BIT (lra_reg_info
[regno
].conflict_hard_regs
, hr
);
625 #ifdef ENABLE_CHECKING
626 lra_reg_info
[regno
].call_p
= true;
628 if (! sparseset_bit_p (pseudos_live_through_setjumps
, regno
))
630 sparseset_clear_bit (pseudos_live_through_setjumps
, regno
);
631 /* Don't allocate pseudos that cross setjmps or any call, if this
632 function receives a nonlocal goto. */
633 SET_HARD_REG_SET (lra_reg_info
[regno
].conflict_hard_regs
);
636 /* Process insns of the basic block BB to update pseudo live ranges,
637 pseudo hard register conflicts, and insn notes. We do it on
638 backward scan of BB insns. CURR_POINT is the program point where
639 BB ends. The function updates this counter and returns in
640 CURR_POINT the program point where BB starts. The function also
641 does local live info updates and can delete the dead insns if
642 GLOBAL_LIVE_INFO_P. It returns true if pseudo live info was
643 changed at the BB start. */
645 process_bb_lives (basic_block bb
, int &curr_point
, bool global_live_info_p
)
654 bool need_curr_point_incr
;
656 reg_live_out
= df_get_live_out (bb
);
657 sparseset_clear (pseudos_live
);
658 sparseset_clear (pseudos_live_through_calls
);
659 sparseset_clear (pseudos_live_through_setjumps
);
660 REG_SET_TO_HARD_REG_SET (hard_regs_live
, reg_live_out
);
661 AND_COMPL_HARD_REG_SET (hard_regs_live
, eliminable_regset
);
662 EXECUTE_IF_SET_IN_BITMAP (reg_live_out
, FIRST_PSEUDO_REGISTER
, j
, bi
)
663 mark_pseudo_live (j
, curr_point
);
665 if (global_live_info_p
)
667 bb_gen_pseudos
= &get_bb_data (bb
)->gen_pseudos
;
668 bb_killed_pseudos
= &get_bb_data (bb
)->killed_pseudos
;
669 bitmap_clear (bb_gen_pseudos
);
670 bitmap_clear (bb_killed_pseudos
);
672 freq
= REG_FREQ_FROM_BB (bb
);
674 if (lra_dump_file
!= NULL
)
675 fprintf (lra_dump_file
, " BB %d\n", bb
->index
);
677 /* Scan the code of this basic block, noting which pseudos and hard
678 regs are born or die.
680 Note that this loop treats uninitialized values as live until the
681 beginning of the block. For example, if an instruction uses
682 (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
683 FOO will remain live until the beginning of the block. Likewise
684 if FOO is not set at all. This is unnecessarily pessimistic, but
685 it probably doesn't matter much in practice. */
686 FOR_BB_INSNS_REVERSE_SAFE (bb
, curr_insn
, next
)
689 int dst_regno
, src_regno
;
691 struct lra_insn_reg
*reg
;
693 if (!NONDEBUG_INSN_P (curr_insn
))
696 curr_id
= lra_get_insn_recog_data (curr_insn
);
697 curr_static_id
= curr_id
->insn_static_data
;
698 if (lra_dump_file
!= NULL
)
699 fprintf (lra_dump_file
, " Insn %u: point = %d\n",
700 INSN_UID (curr_insn
), curr_point
);
702 set
= single_set (curr_insn
);
704 if (global_live_info_p
&& set
!= NULL_RTX
705 && REG_P (SET_DEST (set
)) && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
706 && find_reg_note (curr_insn
, REG_EH_REGION
, NULL_RTX
) == NULL_RTX
707 && ! may_trap_p (PATTERN (curr_insn
))
708 /* Don't do premature remove of pic offset pseudo as we can
709 start to use it after some reload generation. */
710 && (pic_offset_table_rtx
== NULL_RTX
711 || pic_offset_table_rtx
!= SET_DEST (set
)))
713 bool dead_insn_p
= true;
715 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
716 if (reg
->type
!= OP_IN
&& sparseset_bit_p (pseudos_live
, reg
->regno
))
721 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
722 if (reg
->type
!= OP_IN
)
727 if (dead_insn_p
&& ! volatile_refs_p (PATTERN (curr_insn
)))
729 dst_regno
= REGNO (SET_DEST (set
));
730 if (lra_dump_file
!= NULL
)
731 fprintf (lra_dump_file
, " Deleting dead insn %u\n",
732 INSN_UID (curr_insn
));
733 lra_set_insn_deleted (curr_insn
);
734 if (lra_reg_info
[dst_regno
].nrefs
== 0)
736 /* There might be some debug insns with the pseudo. */
740 bitmap_copy (&temp_bitmap
, &lra_reg_info
[dst_regno
].insn_bitmap
);
741 EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap
, 0, uid
, bi
)
743 insn
= lra_insn_recog_data
[uid
]->insn
;
744 lra_substitute_pseudo_within_insn (insn
, dst_regno
,
746 lra_update_insn_regno_info (insn
);
753 /* Update max ref width and hard reg usage. */
754 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
755 if (reg
->regno
>= FIRST_PSEUDO_REGISTER
756 && (GET_MODE_SIZE (reg
->biggest_mode
)
757 > GET_MODE_SIZE (lra_reg_info
[reg
->regno
].biggest_mode
)))
758 lra_reg_info
[reg
->regno
].biggest_mode
= reg
->biggest_mode
;
759 else if (reg
->regno
< FIRST_PSEUDO_REGISTER
)
760 lra_hard_reg_usage
[reg
->regno
] += freq
;
762 call_p
= CALL_P (curr_insn
);
765 && REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
))
766 /* Check that source regno does not conflict with
767 destination regno to exclude most impossible
769 && ((((src_regno
= REGNO (SET_SRC (set
))) >= FIRST_PSEUDO_REGISTER
770 && ! sparseset_bit_p (pseudos_live
, src_regno
))
771 || (src_regno
< FIRST_PSEUDO_REGISTER
772 && ! TEST_HARD_REG_BIT (hard_regs_live
, src_regno
)))
773 /* It might be 'inheritance pseudo <- reload pseudo'. */
774 || (src_regno
>= lra_constraint_new_regno_start
775 && ((int) REGNO (SET_DEST (set
))
776 >= lra_constraint_new_regno_start
)
777 /* Remember to skip special cases where src/dest regnos are
778 the same, e.g. insn SET pattern has matching constraints
780 && src_regno
!= (int) REGNO (SET_DEST (set
)))))
782 int hard_regno
= -1, regno
= -1;
784 dst_regno
= REGNO (SET_DEST (set
));
785 if (dst_regno
>= lra_constraint_new_regno_start
786 && src_regno
>= lra_constraint_new_regno_start
)
787 lra_create_copy (dst_regno
, src_regno
, freq
);
788 else if (dst_regno
>= lra_constraint_new_regno_start
)
790 if ((hard_regno
= src_regno
) >= FIRST_PSEUDO_REGISTER
)
791 hard_regno
= reg_renumber
[src_regno
];
794 else if (src_regno
>= lra_constraint_new_regno_start
)
796 if ((hard_regno
= dst_regno
) >= FIRST_PSEUDO_REGISTER
)
797 hard_regno
= reg_renumber
[dst_regno
];
800 if (regno
>= 0 && hard_regno
>= 0)
801 lra_setup_reload_pseudo_preferenced_hard_reg
802 (regno
, hard_regno
, freq
);
805 sparseset_clear (start_living
);
807 /* Try to avoid unnecessary program point increments, this saves
808 a lot of time in remove_some_program_points_and_update_live_ranges.
809 We only need an increment if something becomes live or dies at this
811 need_curr_point_incr
= false;
813 /* Mark each defined value as live. We need to do this for
814 unused values because they still conflict with quantities
815 that are live at the time of the definition. */
816 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
817 if (reg
->type
!= OP_IN
)
820 |= mark_regno_live (reg
->regno
, reg
->biggest_mode
,
821 curr_point
, global_live_info_p
);
822 check_pseudos_live_through_calls (reg
->regno
);
825 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
826 if (reg
->type
!= OP_IN
)
827 make_hard_regno_born (reg
->regno
);
829 sparseset_copy (unused_set
, start_living
);
831 sparseset_clear (start_dying
);
833 /* See which defined values die here. */
834 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
835 if (reg
->type
== OP_OUT
&& ! reg
->early_clobber
&& ! reg
->subreg_p
)
837 |= mark_regno_dead (reg
->regno
, reg
->biggest_mode
,
838 curr_point
, global_live_info_p
);
840 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
841 if (reg
->type
== OP_OUT
&& ! reg
->early_clobber
&& ! reg
->subreg_p
)
842 make_hard_regno_dead (reg
->regno
);
846 if (flag_use_caller_save
)
848 HARD_REG_SET this_call_used_reg_set
;
849 get_call_reg_set_usage (curr_insn
, &this_call_used_reg_set
,
852 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, j
)
853 IOR_HARD_REG_SET (lra_reg_info
[j
].actual_call_used_reg_set
,
854 this_call_used_reg_set
);
857 sparseset_ior (pseudos_live_through_calls
,
858 pseudos_live_through_calls
, pseudos_live
);
859 if (cfun
->has_nonlocal_label
860 || find_reg_note (curr_insn
, REG_SETJMP
,
861 NULL_RTX
) != NULL_RTX
)
862 sparseset_ior (pseudos_live_through_setjumps
,
863 pseudos_live_through_setjumps
, pseudos_live
);
866 /* Increment the current program point if we must. */
867 if (need_curr_point_incr
)
868 next_program_point (curr_point
, freq
);
870 sparseset_clear (start_living
);
872 need_curr_point_incr
= false;
874 /* Mark each used value as live. */
875 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
876 if (reg
->type
== OP_IN
)
879 |= mark_regno_live (reg
->regno
, reg
->biggest_mode
,
880 curr_point
, global_live_info_p
);
881 check_pseudos_live_through_calls (reg
->regno
);
884 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
885 if (reg
->type
== OP_IN
)
886 make_hard_regno_born (reg
->regno
);
888 if (curr_id
->arg_hard_regs
!= NULL
)
889 /* Make argument hard registers live. */
890 for (i
= 0; (regno
= curr_id
->arg_hard_regs
[i
]) >= 0; i
++)
891 make_hard_regno_born (regno
);
893 sparseset_and_compl (dead_set
, start_living
, start_dying
);
895 /* Mark early clobber outputs dead. */
896 for (reg
= curr_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
897 if (reg
->type
== OP_OUT
&& reg
->early_clobber
&& ! reg
->subreg_p
)
899 |= mark_regno_dead (reg
->regno
, reg
->biggest_mode
,
900 curr_point
, global_live_info_p
);
902 for (reg
= curr_static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
903 if (reg
->type
== OP_OUT
&& reg
->early_clobber
&& ! reg
->subreg_p
)
904 make_hard_regno_dead (reg
->regno
);
906 if (need_curr_point_incr
)
907 next_program_point (curr_point
, freq
);
910 for (link_loc
= ®_NOTES (curr_insn
); (link
= *link_loc
) != NULL_RTX
;)
912 if (REG_NOTE_KIND (link
) != REG_DEAD
913 && REG_NOTE_KIND (link
) != REG_UNUSED
)
915 else if (REG_P (XEXP (link
, 0)))
917 regno
= REGNO (XEXP (link
, 0));
918 if ((REG_NOTE_KIND (link
) == REG_DEAD
919 && ! sparseset_bit_p (dead_set
, regno
))
920 || (REG_NOTE_KIND (link
) == REG_UNUSED
921 && ! sparseset_bit_p (unused_set
, regno
)))
923 *link_loc
= XEXP (link
, 1);
926 if (REG_NOTE_KIND (link
) == REG_DEAD
)
927 sparseset_clear_bit (dead_set
, regno
);
928 else if (REG_NOTE_KIND (link
) == REG_UNUSED
)
929 sparseset_clear_bit (unused_set
, regno
);
931 link_loc
= &XEXP (link
, 1);
933 EXECUTE_IF_SET_IN_SPARSESET (dead_set
, j
)
934 add_reg_note (curr_insn
, REG_DEAD
, regno_reg_rtx
[j
]);
935 EXECUTE_IF_SET_IN_SPARSESET (unused_set
, j
)
936 add_reg_note (curr_insn
, REG_UNUSED
, regno_reg_rtx
[j
]);
939 #ifdef EH_RETURN_DATA_REGNO
940 if (bb_has_eh_pred (bb
))
943 unsigned int regno
= EH_RETURN_DATA_REGNO (j
);
945 if (regno
== INVALID_REGNUM
)
947 make_hard_regno_born (regno
);
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
);
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
);
973 bool live_change_p
= false;
974 if (global_live_info_p
)
976 /* Check if bb border live info was changed. */
977 unsigned int live_pseudos_num
= 0;
978 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb
),
979 FIRST_PSEUDO_REGISTER
, j
, bi
)
982 if (! sparseset_bit_p (pseudos_live
, j
))
984 live_change_p
= TRUE
;
990 || sparseset_cardinality (pseudos_live
) != live_pseudos_num
);
993 /* See if we'll need an increment at the end of this basic block.
994 An increment is needed if the PSEUDOS_LIVE set is not empty,
995 to make sure the finish points are set up correctly. */
996 need_curr_point_incr
= (sparseset_cardinality (pseudos_live
) > 0);
998 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live
, i
)
999 mark_pseudo_dead (i
, curr_point
);
1001 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb
), FIRST_PSEUDO_REGISTER
, j
, bi
)
1003 if (sparseset_cardinality (pseudos_live_through_calls
) == 0)
1005 if (sparseset_bit_p (pseudos_live_through_calls
, j
))
1006 check_pseudos_live_through_calls (j
);
1009 if (need_curr_point_incr
)
1010 next_program_point (curr_point
, freq
);
1012 return live_change_p
;
1015 /* Compress pseudo live ranges by removing program points where
1016 nothing happens. Complexity of many algorithms in LRA is linear
1017 function of program points number. To speed up the code we try to
1018 minimize the number of the program points here. */
1020 remove_some_program_points_and_update_live_ranges (void)
1025 lra_live_range_t r
, prev_r
, next_r
;
1026 sbitmap born_or_dead
, born
, dead
;
1027 sbitmap_iterator sbi
;
1028 bool born_p
, dead_p
, prev_born_p
, prev_dead_p
;
1030 born
= sbitmap_alloc (lra_live_max_point
);
1031 dead
= sbitmap_alloc (lra_live_max_point
);
1032 bitmap_clear (born
);
1033 bitmap_clear (dead
);
1034 max_regno
= max_reg_num ();
1035 for (i
= FIRST_PSEUDO_REGISTER
; i
< (unsigned) max_regno
; i
++)
1037 for (r
= lra_reg_info
[i
].live_ranges
; r
!= NULL
; r
= r
->next
)
1039 lra_assert (r
->start
<= r
->finish
);
1040 bitmap_set_bit (born
, r
->start
);
1041 bitmap_set_bit (dead
, r
->finish
);
1044 born_or_dead
= sbitmap_alloc (lra_live_max_point
);
1045 bitmap_ior (born_or_dead
, born
, dead
);
1046 map
= XCNEWVEC (int, lra_live_max_point
);
1048 prev_born_p
= prev_dead_p
= false;
1049 EXECUTE_IF_SET_IN_BITMAP (born_or_dead
, 0, i
, sbi
)
1051 born_p
= bitmap_bit_p (born
, i
);
1052 dead_p
= bitmap_bit_p (dead
, i
);
1053 if ((prev_born_p
&& ! prev_dead_p
&& born_p
&& ! dead_p
)
1054 || (prev_dead_p
&& ! prev_born_p
&& dead_p
&& ! born_p
))
1057 lra_point_freq
[n
] = MAX (lra_point_freq
[n
], lra_point_freq
[i
]);
1062 lra_point_freq
[n
] = lra_point_freq
[i
];
1064 prev_born_p
= born_p
;
1065 prev_dead_p
= dead_p
;
1067 sbitmap_free (born_or_dead
);
1068 sbitmap_free (born
);
1069 sbitmap_free (dead
);
1071 if (lra_dump_file
!= NULL
)
1072 fprintf (lra_dump_file
, "Compressing live ranges: from %d to %d - %d%%\n",
1073 lra_live_max_point
, n
, 100 * n
/ lra_live_max_point
);
1074 if (n
< lra_live_max_point
)
1076 lra_live_max_point
= n
;
1077 for (i
= FIRST_PSEUDO_REGISTER
; i
< (unsigned) max_regno
; i
++)
1079 for (prev_r
= NULL
, r
= lra_reg_info
[i
].live_ranges
;
1084 r
->start
= map
[r
->start
];
1085 r
->finish
= map
[r
->finish
];
1086 if (prev_r
== NULL
|| prev_r
->start
> r
->finish
+ 1)
1091 prev_r
->start
= r
->start
;
1092 prev_r
->next
= next_r
;
1093 free_live_range (r
);
1100 /* Print live ranges R to file F. */
1102 lra_print_live_range_list (FILE *f
, lra_live_range_t r
)
1104 for (; r
!= NULL
; r
= r
->next
)
1105 fprintf (f
, " [%d..%d]", r
->start
, r
->finish
);
1110 debug (lra_live_range
&ref
)
1112 lra_print_live_range_list (stderr
, &ref
);
1116 debug (lra_live_range
*ptr
)
1121 fprintf (stderr
, "<nil>\n");
1124 /* Print live ranges R to stderr. */
1126 lra_debug_live_range_list (lra_live_range_t r
)
1128 lra_print_live_range_list (stderr
, r
);
1131 /* Print live ranges of pseudo REGNO to file F. */
1133 print_pseudo_live_ranges (FILE *f
, int regno
)
1135 if (lra_reg_info
[regno
].live_ranges
== NULL
)
1137 fprintf (f
, " r%d:", regno
);
1138 lra_print_live_range_list (f
, lra_reg_info
[regno
].live_ranges
);
1141 /* Print live ranges of pseudo REGNO to stderr. */
1143 lra_debug_pseudo_live_ranges (int regno
)
1145 print_pseudo_live_ranges (stderr
, regno
);
1148 /* Print live ranges of all pseudos to file F. */
1150 print_live_ranges (FILE *f
)
1154 max_regno
= max_reg_num ();
1155 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
1156 print_pseudo_live_ranges (f
, i
);
1159 /* Print live ranges of all pseudos to stderr. */
1161 lra_debug_live_ranges (void)
1163 print_live_ranges (stderr
);
1166 /* Compress pseudo live ranges. */
1168 compress_live_ranges (void)
1170 remove_some_program_points_and_update_live_ranges ();
1171 if (lra_dump_file
!= NULL
)
1173 fprintf (lra_dump_file
, "Ranges after the compression:\n");
1174 print_live_ranges (lra_dump_file
);
1180 /* The number of the current live range pass. */
1181 int lra_live_range_iter
;
1183 /* The main entry function creates live ranges only for memory pseudos
1184 (or for all ones if ALL_P), set up CONFLICT_HARD_REGS for the
1185 pseudos. It also does dead insn elimination and global live
1186 analysis only for pseudos and only if GLOBAL_LIVE_INFO_P and the
1187 pseudo live info was changed on a BB border. */
1189 lra_create_live_ranges (bool all_p
, bool global_live_info_p
)
1192 int i
, hard_regno
, max_regno
= max_reg_num ();
1194 bool bb_live_change_p
, have_referenced_pseudos
= false;
1196 timevar_push (TV_LRA_CREATE_LIVE_RANGES
);
1198 complete_info_p
= all_p
;
1199 if (lra_dump_file
!= NULL
)
1200 fprintf (lra_dump_file
,
1201 "\n********** Pseudo live ranges #%d: **********\n\n",
1202 ++lra_live_range_iter
);
1203 memset (lra_hard_reg_usage
, 0, sizeof (lra_hard_reg_usage
));
1204 for (i
= 0; i
< max_regno
; i
++)
1206 lra_reg_info
[i
].live_ranges
= NULL
;
1207 CLEAR_HARD_REG_SET (lra_reg_info
[i
].conflict_hard_regs
);
1208 lra_reg_info
[i
].preferred_hard_regno1
= -1;
1209 lra_reg_info
[i
].preferred_hard_regno2
= -1;
1210 lra_reg_info
[i
].preferred_hard_regno_profit1
= 0;
1211 lra_reg_info
[i
].preferred_hard_regno_profit2
= 0;
1213 lra_reg_info
[i
].no_stack_p
= false;
1215 /* The biggest mode is already set but its value might be to
1216 conservative because of recent transformation. Here in this
1217 file we recalculate it again as it costs practically
1219 if (regno_reg_rtx
[i
] != NULL_RTX
)
1220 lra_reg_info
[i
].biggest_mode
= GET_MODE (regno_reg_rtx
[i
]);
1222 lra_reg_info
[i
].biggest_mode
= VOIDmode
;
1223 #ifdef ENABLE_CHECKING
1224 lra_reg_info
[i
].call_p
= false;
1226 if (i
>= FIRST_PSEUDO_REGISTER
1227 && lra_reg_info
[i
].nrefs
!= 0)
1229 if ((hard_regno
= reg_renumber
[i
]) >= 0)
1230 lra_hard_reg_usage
[hard_regno
] += lra_reg_info
[i
].freq
;
1231 have_referenced_pseudos
= true;
1236 /* Under some circumstances, we can have functions without pseudo
1237 registers. For such functions, lra_live_max_point will be 0,
1238 see e.g. PR55604, and there's nothing more to do for us here. */
1239 if (! have_referenced_pseudos
)
1241 timevar_pop (TV_LRA_CREATE_LIVE_RANGES
);
1245 pseudos_live
= sparseset_alloc (max_regno
);
1246 pseudos_live_through_calls
= sparseset_alloc (max_regno
);
1247 pseudos_live_through_setjumps
= sparseset_alloc (max_regno
);
1248 start_living
= sparseset_alloc (max_regno
);
1249 start_dying
= sparseset_alloc (max_regno
);
1250 dead_set
= sparseset_alloc (max_regno
);
1251 unused_set
= sparseset_alloc (max_regno
);
1253 point_freq_vec
.create (get_max_uid () * 2);
1254 lra_point_freq
= point_freq_vec
.address ();
1255 int *post_order_rev_cfg
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1256 int n_blocks_inverted
= inverted_post_order_compute (post_order_rev_cfg
);
1257 lra_assert (n_blocks_inverted
== n_basic_blocks_for_fn (cfun
));
1258 bb_live_change_p
= false;
1259 for (i
= n_blocks_inverted
- 1; i
>= 0; --i
)
1261 bb
= BASIC_BLOCK_FOR_FN (cfun
, post_order_rev_cfg
[i
]);
1262 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
1263 == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1265 if (process_bb_lives (bb
, curr_point
, global_live_info_p
))
1266 bb_live_change_p
= true;
1268 if (bb_live_change_p
)
1270 /* We need to clear pseudo live info as some pseudos can
1271 disappear, e.g. pseudos with used equivalences. */
1272 FOR_EACH_BB_FN (bb
, cfun
)
1274 bitmap_clear_range (df_get_live_in (bb
), FIRST_PSEUDO_REGISTER
,
1275 max_regno
- FIRST_PSEUDO_REGISTER
);
1276 bitmap_clear_range (df_get_live_out (bb
), FIRST_PSEUDO_REGISTER
,
1277 max_regno
- FIRST_PSEUDO_REGISTER
);
1279 /* As we did not change CFG since LRA start we can use
1280 DF-infrastructure solver to solve live data flow problem. */
1282 (DF_BACKWARD
, NULL
, live_con_fun_0
, live_con_fun_n
,
1283 live_trans_fun
, &all_blocks
,
1284 df_get_postorder (DF_BACKWARD
), df_get_n_blocks (DF_BACKWARD
));
1285 if (lra_dump_file
!= NULL
)
1287 fprintf (lra_dump_file
,
1288 "Global pseudo live data have been updated:\n");
1290 FOR_EACH_BB_FN (bb
, cfun
)
1292 bb_data_t bb_info
= get_bb_data (bb
);
1293 bitmap bb_livein
= df_get_live_in (bb
);
1294 bitmap bb_liveout
= df_get_live_out (bb
);
1296 fprintf (lra_dump_file
, "\nBB %d:\n", bb
->index
);
1297 lra_dump_bitmap_with_title (" gen:",
1298 &bb_info
->gen_pseudos
, bb
->index
);
1299 lra_dump_bitmap_with_title (" killed:",
1300 &bb_info
->killed_pseudos
, bb
->index
);
1301 lra_dump_bitmap_with_title (" livein:", bb_livein
, bb
->index
);
1302 lra_dump_bitmap_with_title (" liveout:", bb_liveout
, bb
->index
);
1306 free (post_order_rev_cfg
);
1307 lra_live_max_point
= curr_point
;
1308 if (lra_dump_file
!= NULL
)
1309 print_live_ranges (lra_dump_file
);
1311 sparseset_free (unused_set
);
1312 sparseset_free (dead_set
);
1313 sparseset_free (start_dying
);
1314 sparseset_free (start_living
);
1315 sparseset_free (pseudos_live_through_calls
);
1316 sparseset_free (pseudos_live_through_setjumps
);
1317 sparseset_free (pseudos_live
);
1318 compress_live_ranges ();
1319 timevar_pop (TV_LRA_CREATE_LIVE_RANGES
);
1322 /* Finish all live ranges. */
1324 lra_clear_live_ranges (void)
1328 for (i
= 0; i
< max_reg_num (); i
++)
1329 free_live_range_list (lra_reg_info
[i
].live_ranges
);
1330 point_freq_vec
.release ();
1333 /* Initialize live ranges data once per function. */
1335 lra_live_ranges_init (void)
1337 live_range_pool
= create_alloc_pool ("live ranges",
1338 sizeof (struct lra_live_range
), 100);
1339 bitmap_initialize (&temp_bitmap
, ®_obstack
);
1340 initiate_live_solver ();
1343 /* Finish live ranges data once per function. */
1345 lra_live_ranges_finish (void)
1347 finish_live_solver ();
1348 bitmap_clear (&temp_bitmap
);
1349 free_alloc_pool (live_range_pool
);