Daily bump.
[official-gcc.git] / gcc / lra-lives.c
blob29531843c633654583a21d06b8b9f9c707a7edf0
1 /* Build live ranges for pseudos.
2 Copyright (C) 2010-2021 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
10 version.
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
15 for more details.
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. */
28 #include "config.h"
29 #include "system.h"
30 #include "coretypes.h"
31 #include "backend.h"
32 #include "rtl.h"
33 #include "tree.h"
34 #include "predict.h"
35 #include "df.h"
36 #include "memmodel.h"
37 #include "tm_p.h"
38 #include "insn-config.h"
39 #include "regs.h"
40 #include "ira.h"
41 #include "recog.h"
42 #include "cfganal.h"
43 #include "sparseset.h"
44 #include "lra-int.h"
45 #include "target.h"
46 #include "function-abi.h"
48 /* Program points are enumerated by numbers from range
49 0..LRA_LIVE_MAX_POINT-1. There are approximately two times more
50 program points than insns. Program points are places in the
51 program where liveness info can be changed. In most general case
52 (there are more complicated cases too) some program points
53 correspond to places where input operand dies and other ones
54 correspond to places where output operands are born. */
55 int lra_live_max_point;
57 /* Accumulated execution frequency of all references for each hard
58 register. */
59 int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER];
61 /* A global flag whose true value says to build live ranges for all
62 pseudos, otherwise the live ranges only for pseudos got memory is
63 build. True value means also building copies and setting up hard
64 register preferences. The complete info is necessary only for the
65 assignment pass. The complete info is not needed for the
66 coalescing and spill passes. */
67 static bool complete_info_p;
69 /* Pseudos live at current point in the RTL scan. */
70 static sparseset pseudos_live;
72 /* Pseudos probably living through calls and setjumps. As setjump is
73 a call too, if a bit in PSEUDOS_LIVE_THROUGH_SETJUMPS is set up
74 then the corresponding bit in PSEUDOS_LIVE_THROUGH_CALLS is set up
75 too. These data are necessary for cases when only one subreg of a
76 multi-reg pseudo is set up after a call. So we decide it is
77 probably live when traversing bb backward. We are sure about
78 living when we see its usage or definition of the pseudo. */
79 static sparseset pseudos_live_through_calls;
80 static sparseset pseudos_live_through_setjumps;
82 /* Set of hard regs (except eliminable ones) currently live. */
83 static HARD_REG_SET hard_regs_live;
85 /* Set of pseudos and hard registers start living/dying in the current
86 insn. These sets are used to update REG_DEAD and REG_UNUSED notes
87 in the insn. */
88 static sparseset start_living, start_dying;
90 /* Set of pseudos and hard regs dead and unused in the current
91 insn. */
92 static sparseset unused_set, dead_set;
94 /* Bitmap used for holding intermediate bitmap operation results. */
95 static bitmap_head temp_bitmap;
97 /* Pool for pseudo live ranges. */
98 static object_allocator<lra_live_range> lra_live_range_pool ("live ranges");
100 /* Free live range list LR. */
101 static void
102 free_live_range_list (lra_live_range_t lr)
104 lra_live_range_t next;
106 while (lr != NULL)
108 next = lr->next;
109 lra_live_range_pool.remove (lr);
110 lr = next;
114 /* Create and return pseudo live range with given attributes. */
115 static lra_live_range_t
116 create_live_range (int regno, int start, int finish, lra_live_range_t next)
118 lra_live_range_t p = lra_live_range_pool.allocate ();
119 p->regno = regno;
120 p->start = start;
121 p->finish = finish;
122 p->next = next;
123 return p;
126 /* Copy live range R and return the result. */
127 static lra_live_range_t
128 copy_live_range (lra_live_range_t r)
130 return new (lra_live_range_pool) lra_live_range (*r);
133 /* Copy live range list given by its head R and return the result. */
134 lra_live_range_t
135 lra_copy_live_range_list (lra_live_range_t r)
137 lra_live_range_t p, first, *chain;
139 first = NULL;
140 for (chain = &first; r != NULL; r = r->next)
142 p = copy_live_range (r);
143 *chain = p;
144 chain = &p->next;
146 return first;
149 /* Merge *non-intersected* ranges R1 and R2 and returns the result.
150 The function maintains the order of ranges and tries to minimize
151 size of the result range list. Ranges R1 and R2 may not be used
152 after the call. */
153 lra_live_range_t
154 lra_merge_live_ranges (lra_live_range_t r1, lra_live_range_t r2)
156 lra_live_range_t first, last;
158 if (r1 == NULL)
159 return r2;
160 if (r2 == NULL)
161 return r1;
162 for (first = last = NULL; r1 != NULL && r2 != NULL;)
164 if (r1->start < r2->start)
165 std::swap (r1, r2);
167 if (r1->start == r2->finish + 1)
169 /* Joint ranges: merge r1 and r2 into r1. */
170 r1->start = r2->start;
171 lra_live_range_t temp = r2;
172 r2 = r2->next;
173 lra_live_range_pool.remove (temp);
175 else
177 gcc_assert (r2->finish + 1 < r1->start);
178 /* Add r1 to the result. */
179 if (first == NULL)
180 first = last = r1;
181 else
183 last->next = r1;
184 last = r1;
186 r1 = r1->next;
189 if (r1 != NULL)
191 if (first == NULL)
192 first = r1;
193 else
194 last->next = r1;
196 else
198 lra_assert (r2 != NULL);
199 if (first == NULL)
200 first = r2;
201 else
202 last->next = r2;
204 return first;
207 /* Return TRUE if live ranges R1 and R2 intersect. */
208 bool
209 lra_intersected_live_ranges_p (lra_live_range_t r1, lra_live_range_t r2)
211 /* Remember the live ranges are always kept ordered. */
212 while (r1 != NULL && r2 != NULL)
214 if (r1->start > r2->finish)
215 r1 = r1->next;
216 else if (r2->start > r1->finish)
217 r2 = r2->next;
218 else
219 return true;
221 return false;
224 enum point_type {
225 DEF_POINT,
226 USE_POINT
229 /* Return TRUE if set A contains a pseudo register, otherwise, return FALSE. */
230 static bool
231 sparseset_contains_pseudos_p (sparseset a)
233 int regno;
234 EXECUTE_IF_SET_IN_SPARSESET (a, regno)
235 if (!HARD_REGISTER_NUM_P (regno))
236 return true;
237 return false;
240 /* Mark pseudo REGNO as living or dying at program point POINT, depending on
241 whether TYPE is a definition or a use. If this is the first reference to
242 REGNO that we've encountered, then create a new live range for it. */
244 static void
245 update_pseudo_point (int regno, int point, enum point_type type)
247 lra_live_range_t p;
249 /* Don't compute points for hard registers. */
250 if (HARD_REGISTER_NUM_P (regno))
251 return;
253 if (complete_info_p || lra_get_regno_hard_regno (regno) < 0)
255 if (type == DEF_POINT)
257 if (sparseset_bit_p (pseudos_live, regno))
259 p = lra_reg_info[regno].live_ranges;
260 lra_assert (p != NULL);
261 p->finish = point;
264 else /* USE_POINT */
266 if (!sparseset_bit_p (pseudos_live, regno)
267 && ((p = lra_reg_info[regno].live_ranges) == NULL
268 || (p->finish != point && p->finish + 1 != point)))
269 lra_reg_info[regno].live_ranges
270 = create_live_range (regno, point, -1, p);
275 /* The corresponding bitmaps of BB currently being processed. */
276 static bitmap bb_killed_pseudos, bb_gen_pseudos;
278 /* Record hard register REGNO as now being live. It updates
279 living hard regs and START_LIVING. */
280 static void
281 make_hard_regno_live (int regno)
283 lra_assert (HARD_REGISTER_NUM_P (regno));
284 if (TEST_HARD_REG_BIT (hard_regs_live, regno)
285 || TEST_HARD_REG_BIT (eliminable_regset, regno))
286 return;
287 SET_HARD_REG_BIT (hard_regs_live, regno);
288 sparseset_set_bit (start_living, regno);
289 if (fixed_regs[regno] || TEST_HARD_REG_BIT (hard_regs_spilled_into, regno))
290 bitmap_set_bit (bb_gen_pseudos, regno);
293 /* Process the definition of hard register REGNO. This updates
294 hard_regs_live, START_DYING and conflict hard regs for living
295 pseudos. */
296 static void
297 make_hard_regno_dead (int regno)
299 if (TEST_HARD_REG_BIT (eliminable_regset, regno))
300 return;
302 lra_assert (HARD_REGISTER_NUM_P (regno));
303 unsigned int i;
304 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
305 SET_HARD_REG_BIT (lra_reg_info[i].conflict_hard_regs, regno);
307 if (! TEST_HARD_REG_BIT (hard_regs_live, regno))
308 return;
309 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
310 sparseset_set_bit (start_dying, regno);
311 if (fixed_regs[regno] || TEST_HARD_REG_BIT (hard_regs_spilled_into, regno))
313 bitmap_clear_bit (bb_gen_pseudos, regno);
314 bitmap_set_bit (bb_killed_pseudos, regno);
318 /* Mark pseudo REGNO as now being live and update START_LIVING. */
319 static void
320 mark_pseudo_live (int regno)
322 lra_assert (!HARD_REGISTER_NUM_P (regno));
323 if (sparseset_bit_p (pseudos_live, regno))
324 return;
326 sparseset_set_bit (pseudos_live, regno);
327 sparseset_set_bit (start_living, regno);
330 /* Mark pseudo REGNO as now being dead and update START_DYING. */
331 static void
332 mark_pseudo_dead (int regno)
334 lra_assert (!HARD_REGISTER_NUM_P (regno));
335 lra_reg_info[regno].conflict_hard_regs |= hard_regs_live;
336 if (!sparseset_bit_p (pseudos_live, regno))
337 return;
339 sparseset_clear_bit (pseudos_live, regno);
340 sparseset_set_bit (start_dying, regno);
343 /* Mark register REGNO (pseudo or hard register) in MODE as being live
344 and update BB_GEN_PSEUDOS. */
345 static void
346 mark_regno_live (int regno, machine_mode mode)
348 int last;
350 if (HARD_REGISTER_NUM_P (regno))
352 for (last = end_hard_regno (mode, regno); regno < last; regno++)
353 make_hard_regno_live (regno);
355 else
357 mark_pseudo_live (regno);
358 bitmap_set_bit (bb_gen_pseudos, regno);
363 /* Mark register REGNO (pseudo or hard register) in MODE as being dead
364 and update BB_GEN_PSEUDOS and BB_KILLED_PSEUDOS. */
365 static void
366 mark_regno_dead (int regno, machine_mode mode)
368 int last;
370 if (HARD_REGISTER_NUM_P (regno))
372 for (last = end_hard_regno (mode, regno); regno < last; regno++)
373 make_hard_regno_dead (regno);
375 else
377 mark_pseudo_dead (regno);
378 bitmap_clear_bit (bb_gen_pseudos, regno);
379 bitmap_set_bit (bb_killed_pseudos, regno);
385 /* This page contains code for making global live analysis of pseudos.
386 The code works only when pseudo live info is changed on a BB
387 border. That might be a consequence of some global transformations
388 in LRA, e.g. PIC pseudo reuse or rematerialization. */
390 /* Structure describing local BB data used for pseudo
391 live-analysis. */
392 class bb_data_pseudos
394 public:
395 /* Basic block about which the below data are. */
396 basic_block bb;
397 bitmap_head killed_pseudos; /* pseudos killed in the BB. */
398 bitmap_head gen_pseudos; /* pseudos generated in the BB. */
401 /* Array for all BB data. Indexed by the corresponding BB index. */
402 typedef class bb_data_pseudos *bb_data_t;
404 /* All basic block data are referred through the following array. */
405 static bb_data_t bb_data;
407 /* Two small functions for access to the bb data. */
408 static inline bb_data_t
409 get_bb_data (basic_block bb)
411 return &bb_data[(bb)->index];
414 static inline bb_data_t
415 get_bb_data_by_index (int index)
417 return &bb_data[index];
420 /* Bitmap with all hard regs. */
421 static bitmap_head all_hard_regs_bitmap;
423 /* The transfer function used by the DF equation solver to propagate
424 live info through block with BB_INDEX according to the following
425 equation:
427 bb.livein = (bb.liveout - bb.kill) OR bb.gen
429 static bool
430 live_trans_fun (int bb_index)
432 basic_block bb = get_bb_data_by_index (bb_index)->bb;
433 bitmap bb_liveout = df_get_live_out (bb);
434 bitmap bb_livein = df_get_live_in (bb);
435 bb_data_t bb_info = get_bb_data (bb);
437 bitmap_and_compl (&temp_bitmap, bb_liveout, &all_hard_regs_bitmap);
438 return bitmap_ior_and_compl (bb_livein, &bb_info->gen_pseudos,
439 &temp_bitmap, &bb_info->killed_pseudos);
442 /* The confluence function used by the DF equation solver to set up
443 live info for a block BB without predecessor. */
444 static void
445 live_con_fun_0 (basic_block bb)
447 bitmap_and_into (df_get_live_out (bb), &all_hard_regs_bitmap);
450 /* The confluence function used by the DF equation solver to propagate
451 live info from successor to predecessor on edge E according to the
452 following equation:
454 bb.liveout = 0 for entry block | OR (livein of successors)
456 static bool
457 live_con_fun_n (edge e)
459 basic_block bb = e->src;
460 basic_block dest = e->dest;
461 bitmap bb_liveout = df_get_live_out (bb);
462 bitmap dest_livein = df_get_live_in (dest);
464 return bitmap_ior_and_compl_into (bb_liveout,
465 dest_livein, &all_hard_regs_bitmap);
468 /* Indexes of all function blocks. */
469 static bitmap_head all_blocks;
471 /* Allocate and initialize data needed for global pseudo live
472 analysis. */
473 static void
474 initiate_live_solver (void)
476 bitmap_initialize (&all_hard_regs_bitmap, &reg_obstack);
477 bitmap_set_range (&all_hard_regs_bitmap, 0, FIRST_PSEUDO_REGISTER);
478 bb_data = XNEWVEC (class bb_data_pseudos, last_basic_block_for_fn (cfun));
479 bitmap_initialize (&all_blocks, &reg_obstack);
481 basic_block bb;
482 FOR_ALL_BB_FN (bb, cfun)
484 bb_data_t bb_info = get_bb_data (bb);
485 bb_info->bb = bb;
486 bitmap_initialize (&bb_info->killed_pseudos, &reg_obstack);
487 bitmap_initialize (&bb_info->gen_pseudos, &reg_obstack);
488 bitmap_set_bit (&all_blocks, bb->index);
492 /* Free all data needed for global pseudo live analysis. */
493 static void
494 finish_live_solver (void)
496 basic_block bb;
498 bitmap_clear (&all_blocks);
499 FOR_ALL_BB_FN (bb, cfun)
501 bb_data_t bb_info = get_bb_data (bb);
502 bitmap_clear (&bb_info->killed_pseudos);
503 bitmap_clear (&bb_info->gen_pseudos);
505 free (bb_data);
506 bitmap_clear (&all_hard_regs_bitmap);
511 /* Insn currently scanned. */
512 static rtx_insn *curr_insn;
513 /* The insn data. */
514 static lra_insn_recog_data_t curr_id;
515 /* The insn static data. */
516 static struct lra_static_insn_data *curr_static_id;
518 /* Vec containing execution frequencies of program points. */
519 static vec<int> point_freq_vec;
521 /* The start of the above vector elements. */
522 int *lra_point_freq;
524 /* Increment the current program point POINT to the next point which has
525 execution frequency FREQ. */
526 static void
527 next_program_point (int &point, int freq)
529 point_freq_vec.safe_push (freq);
530 lra_point_freq = point_freq_vec.address ();
531 point++;
534 /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
535 void
536 lra_setup_reload_pseudo_preferenced_hard_reg (int regno,
537 int hard_regno, int profit)
539 lra_assert (regno >= lra_constraint_new_regno_start);
540 if (lra_reg_info[regno].preferred_hard_regno1 == hard_regno)
541 lra_reg_info[regno].preferred_hard_regno_profit1 += profit;
542 else if (lra_reg_info[regno].preferred_hard_regno2 == hard_regno)
543 lra_reg_info[regno].preferred_hard_regno_profit2 += profit;
544 else if (lra_reg_info[regno].preferred_hard_regno1 < 0)
546 lra_reg_info[regno].preferred_hard_regno1 = hard_regno;
547 lra_reg_info[regno].preferred_hard_regno_profit1 = profit;
549 else if (lra_reg_info[regno].preferred_hard_regno2 < 0
550 || profit > lra_reg_info[regno].preferred_hard_regno_profit2)
552 lra_reg_info[regno].preferred_hard_regno2 = hard_regno;
553 lra_reg_info[regno].preferred_hard_regno_profit2 = profit;
555 else
556 return;
557 /* Keep the 1st hard regno as more profitable. */
558 if (lra_reg_info[regno].preferred_hard_regno1 >= 0
559 && lra_reg_info[regno].preferred_hard_regno2 >= 0
560 && (lra_reg_info[regno].preferred_hard_regno_profit2
561 > lra_reg_info[regno].preferred_hard_regno_profit1))
563 std::swap (lra_reg_info[regno].preferred_hard_regno1,
564 lra_reg_info[regno].preferred_hard_regno2);
565 std::swap (lra_reg_info[regno].preferred_hard_regno_profit1,
566 lra_reg_info[regno].preferred_hard_regno_profit2);
568 if (lra_dump_file != NULL)
570 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
571 fprintf (lra_dump_file,
572 " Hard reg %d is preferable by r%d with profit %d\n",
573 hard_regno, regno,
574 lra_reg_info[regno].preferred_hard_regno_profit1);
575 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
576 fprintf (lra_dump_file,
577 " Hard reg %d is preferable by r%d with profit %d\n",
578 hard_regno, regno,
579 lra_reg_info[regno].preferred_hard_regno_profit2);
583 /* Check whether REGNO lives through calls and setjmps and clear
584 the corresponding bits in PSEUDOS_LIVE_THROUGH_CALLS and
585 PSEUDOS_LIVE_THROUGH_SETJUMPS. All calls in the region described
586 by PSEUDOS_LIVE_THROUGH_CALLS have the given ABI. */
588 static inline void
589 check_pseudos_live_through_calls (int regno, const function_abi &abi)
591 if (! sparseset_bit_p (pseudos_live_through_calls, regno))
592 return;
594 machine_mode mode = PSEUDO_REGNO_MODE (regno);
596 sparseset_clear_bit (pseudos_live_through_calls, regno);
597 lra_reg_info[regno].conflict_hard_regs |= abi.mode_clobbers (mode);
598 if (! sparseset_bit_p (pseudos_live_through_setjumps, regno))
599 return;
600 sparseset_clear_bit (pseudos_live_through_setjumps, regno);
601 /* Don't allocate pseudos that cross setjmps or any call, if this
602 function receives a nonlocal goto. */
603 SET_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs);
606 /* Return true if insn REG is an early clobber operand in alternative
607 NALT. Negative NALT means that we don't know the current insn
608 alternative. So assume the worst. */
609 static inline bool
610 reg_early_clobber_p (const struct lra_insn_reg *reg, int n_alt)
612 return (n_alt == LRA_UNKNOWN_ALT
613 ? reg->early_clobber_alts != 0
614 : (n_alt != LRA_NON_CLOBBERED_ALT
615 && TEST_BIT (reg->early_clobber_alts, n_alt)));
618 /* Clear pseudo REGNO in SET or all hard registers of REGNO in MODE in SET. */
619 static void
620 clear_sparseset_regnos (sparseset set, int regno, enum machine_mode mode)
622 if (regno >= FIRST_PSEUDO_REGISTER)
624 sparseset_clear_bit (dead_set, regno);
625 return;
627 for (int last = end_hard_regno (mode, regno); regno < last; regno++)
628 sparseset_clear_bit (set, regno);
631 /* Return true if pseudo REGNO is in SET or all hard registers of REGNO in MODE
632 are in SET. */
633 static bool
634 regnos_in_sparseset_p (sparseset set, int regno, enum machine_mode mode)
636 if (regno >= FIRST_PSEUDO_REGISTER)
637 return sparseset_bit_p (dead_set, regno);
638 for (int last = end_hard_regno (mode, regno); regno < last; regno++)
639 if (!sparseset_bit_p (set, regno))
640 return false;
641 return true;
644 /* Process insns of the basic block BB to update pseudo live ranges,
645 pseudo hard register conflicts, and insn notes. We do it on
646 backward scan of BB insns. CURR_POINT is the program point where
647 BB ends. The function updates this counter and returns in
648 CURR_POINT the program point where BB starts. The function also
649 does local live info updates and can delete the dead insns if
650 DEAD_INSN_P. It returns true if pseudo live info was
651 changed at the BB start. */
652 static bool
653 process_bb_lives (basic_block bb, int &curr_point, bool dead_insn_p)
655 int i, regno, freq;
656 unsigned int j;
657 bitmap_iterator bi;
658 bitmap reg_live_out;
659 unsigned int px;
660 rtx_insn *next;
661 rtx link, *link_loc;
662 bool need_curr_point_incr;
663 /* Only has a meaningful value once we've seen a call. */
664 function_abi last_call_abi = default_function_abi;
666 reg_live_out = df_get_live_out (bb);
667 sparseset_clear (pseudos_live);
668 sparseset_clear (pseudos_live_through_calls);
669 sparseset_clear (pseudos_live_through_setjumps);
670 REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
671 hard_regs_live &= ~eliminable_regset;
672 EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
674 update_pseudo_point (j, curr_point, USE_POINT);
675 mark_pseudo_live (j);
678 bb_gen_pseudos = &get_bb_data (bb)->gen_pseudos;
679 bb_killed_pseudos = &get_bb_data (bb)->killed_pseudos;
680 bitmap_clear (bb_gen_pseudos);
681 bitmap_clear (bb_killed_pseudos);
682 freq = REG_FREQ_FROM_BB (bb);
684 if (lra_dump_file != NULL)
685 fprintf (lra_dump_file, " BB %d\n", bb->index);
687 /* Scan the code of this basic block, noting which pseudos and hard
688 regs are born or die.
690 Note that this loop treats uninitialized values as live until the
691 beginning of the block. For example, if an instruction uses
692 (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
693 FOO will remain live until the beginning of the block. Likewise
694 if FOO is not set at all. This is unnecessarily pessimistic, but
695 it probably doesn't matter much in practice. */
696 FOR_BB_INSNS_REVERSE_SAFE (bb, curr_insn, next)
698 bool call_p;
699 int n_alt, dst_regno, src_regno;
700 rtx set;
701 struct lra_insn_reg *reg;
703 if (!NONDEBUG_INSN_P (curr_insn))
704 continue;
706 curr_id = lra_get_insn_recog_data (curr_insn);
707 curr_static_id = curr_id->insn_static_data;
708 n_alt = curr_id->used_insn_alternative;
709 if (lra_dump_file != NULL)
710 fprintf (lra_dump_file, " Insn %u: point = %d, n_alt = %d\n",
711 INSN_UID (curr_insn), curr_point, n_alt);
713 set = single_set (curr_insn);
715 if (dead_insn_p && set != NULL_RTX
716 && REG_P (SET_DEST (set)) && !HARD_REGISTER_P (SET_DEST (set))
717 && find_reg_note (curr_insn, REG_EH_REGION, NULL_RTX) == NULL_RTX
718 && ! may_trap_p (PATTERN (curr_insn))
719 /* Don't do premature remove of pic offset pseudo as we can
720 start to use it after some reload generation. */
721 && (pic_offset_table_rtx == NULL_RTX
722 || pic_offset_table_rtx != SET_DEST (set)))
724 bool remove_p = true;
726 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
727 if (reg->type != OP_IN && sparseset_bit_p (pseudos_live, reg->regno))
729 remove_p = false;
730 break;
732 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
733 if (reg->type != OP_IN)
735 remove_p = false;
736 break;
739 if (remove_p && ! volatile_refs_p (PATTERN (curr_insn)))
741 dst_regno = REGNO (SET_DEST (set));
742 if (lra_dump_file != NULL)
743 fprintf (lra_dump_file, " Deleting dead insn %u\n",
744 INSN_UID (curr_insn));
745 lra_set_insn_deleted (curr_insn);
746 if (lra_reg_info[dst_regno].nrefs == 0)
748 /* There might be some debug insns with the pseudo. */
749 unsigned int uid;
750 rtx_insn *insn;
752 bitmap_copy (&temp_bitmap, &lra_reg_info[dst_regno].insn_bitmap);
753 EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap, 0, uid, bi)
755 insn = lra_insn_recog_data[uid]->insn;
756 lra_substitute_pseudo_within_insn (insn, dst_regno,
757 SET_SRC (set), true);
758 lra_update_insn_regno_info (insn);
761 continue;
765 /* Update max ref width and hard reg usage. */
766 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
768 int regno = reg->regno;
770 if (partial_subreg_p (lra_reg_info[regno].biggest_mode,
771 reg->biggest_mode))
772 lra_reg_info[regno].biggest_mode = reg->biggest_mode;
773 if (HARD_REGISTER_NUM_P (regno))
774 lra_hard_reg_usage[regno] += freq;
777 call_p = CALL_P (curr_insn);
779 /* If we have a simple register copy and the source reg is live after
780 this instruction, then remove the source reg from the live set so
781 that it will not conflict with the destination reg. */
782 rtx ignore_reg = non_conflicting_reg_copy_p (curr_insn);
783 if (ignore_reg != NULL_RTX)
785 int ignore_regno = REGNO (ignore_reg);
786 if (HARD_REGISTER_NUM_P (ignore_regno)
787 && TEST_HARD_REG_BIT (hard_regs_live, ignore_regno))
788 CLEAR_HARD_REG_BIT (hard_regs_live, ignore_regno);
789 else if (!HARD_REGISTER_NUM_P (ignore_regno)
790 && sparseset_bit_p (pseudos_live, ignore_regno))
791 sparseset_clear_bit (pseudos_live, ignore_regno);
792 else
793 /* We don't need any special handling of the source reg if
794 it is dead after this instruction. */
795 ignore_reg = NULL_RTX;
798 src_regno = (set != NULL_RTX && REG_P (SET_SRC (set))
799 ? REGNO (SET_SRC (set)) : -1);
800 dst_regno = (set != NULL_RTX && REG_P (SET_DEST (set))
801 ? REGNO (SET_DEST (set)) : -1);
802 if (complete_info_p
803 && src_regno >= 0 && dst_regno >= 0
804 /* Check that source regno does not conflict with
805 destination regno to exclude most impossible
806 preferences. */
807 && (((!HARD_REGISTER_NUM_P (src_regno)
808 && (! sparseset_bit_p (pseudos_live, src_regno)
809 || (!HARD_REGISTER_NUM_P (dst_regno)
810 && lra_reg_val_equal_p (src_regno,
811 lra_reg_info[dst_regno].val,
812 lra_reg_info[dst_regno].offset))))
813 || (HARD_REGISTER_NUM_P (src_regno)
814 && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno)))
815 /* It might be 'inheritance pseudo <- reload pseudo'. */
816 || (src_regno >= lra_constraint_new_regno_start
817 && dst_regno >= lra_constraint_new_regno_start
818 /* Remember to skip special cases where src/dest regnos are
819 the same, e.g. insn SET pattern has matching constraints
820 like =r,0. */
821 && src_regno != dst_regno)))
823 int hard_regno = -1, regno = -1;
825 if (dst_regno >= lra_constraint_new_regno_start
826 && src_regno >= lra_constraint_new_regno_start)
828 /* It might be still an original (non-reload) insn with
829 one unused output and a constraint requiring to use
830 the same reg for input/output operands. In this case
831 dst_regno and src_regno have the same value, we don't
832 need a misleading copy for this case. */
833 if (dst_regno != src_regno)
834 lra_create_copy (dst_regno, src_regno, freq);
836 else if (dst_regno >= lra_constraint_new_regno_start)
838 if (!HARD_REGISTER_NUM_P (hard_regno = src_regno))
839 hard_regno = reg_renumber[src_regno];
840 regno = dst_regno;
842 else if (src_regno >= lra_constraint_new_regno_start)
844 if (!HARD_REGISTER_NUM_P (hard_regno = dst_regno))
845 hard_regno = reg_renumber[dst_regno];
846 regno = src_regno;
848 if (regno >= 0 && hard_regno >= 0)
849 lra_setup_reload_pseudo_preferenced_hard_reg
850 (regno, hard_regno, freq);
853 sparseset_clear (start_living);
855 /* Mark each defined value as live. We need to do this for
856 unused values because they still conflict with quantities
857 that are live at the time of the definition. */
858 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
859 if (reg->type != OP_IN)
861 update_pseudo_point (reg->regno, curr_point, USE_POINT);
862 mark_regno_live (reg->regno, reg->biggest_mode);
863 /* ??? Should be a no-op for unused registers. */
864 check_pseudos_live_through_calls (reg->regno, last_call_abi);
867 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
868 if (reg->type != OP_IN)
869 make_hard_regno_live (reg->regno);
871 if (curr_id->arg_hard_regs != NULL)
872 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
873 if (!HARD_REGISTER_NUM_P (regno))
874 /* It is a clobber. */
875 make_hard_regno_live (regno - FIRST_PSEUDO_REGISTER);
877 sparseset_copy (unused_set, start_living);
879 sparseset_clear (start_dying);
881 /* See which defined values die here. */
882 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
883 if (reg->type != OP_IN
884 && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
886 if (reg->type == OP_OUT)
887 update_pseudo_point (reg->regno, curr_point, DEF_POINT);
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_IN
893 && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
894 make_hard_regno_dead (reg->regno);
896 if (curr_id->arg_hard_regs != NULL)
897 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
898 if (!HARD_REGISTER_NUM_P (regno))
899 /* It is a clobber. */
900 make_hard_regno_dead (regno - FIRST_PSEUDO_REGISTER);
902 if (call_p)
904 function_abi call_abi = insn_callee_abi (curr_insn);
906 if (last_call_abi != call_abi)
907 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
908 check_pseudos_live_through_calls (j, last_call_abi);
910 last_call_abi = call_abi;
912 sparseset_ior (pseudos_live_through_calls,
913 pseudos_live_through_calls, pseudos_live);
914 if (cfun->has_nonlocal_label
915 || (!targetm.setjmp_preserves_nonvolatile_regs_p ()
916 && (find_reg_note (curr_insn, REG_SETJMP, NULL_RTX)
917 != NULL_RTX)))
918 sparseset_ior (pseudos_live_through_setjumps,
919 pseudos_live_through_setjumps, pseudos_live);
922 /* Increment the current program point if we must. */
923 if (sparseset_contains_pseudos_p (unused_set)
924 || sparseset_contains_pseudos_p (start_dying))
925 next_program_point (curr_point, freq);
927 /* If we removed the source reg from a simple register copy from the
928 live set above, then add it back now so we don't accidentally add
929 it to the start_living set below. */
930 if (ignore_reg != NULL_RTX)
932 int ignore_regno = REGNO (ignore_reg);
933 if (HARD_REGISTER_NUM_P (ignore_regno))
934 SET_HARD_REG_BIT (hard_regs_live, ignore_regno);
935 else
936 sparseset_set_bit (pseudos_live, ignore_regno);
939 sparseset_clear (start_living);
941 /* Mark each used value as live. */
942 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
943 if (reg->type != OP_OUT)
945 if (reg->type == OP_IN)
946 update_pseudo_point (reg->regno, curr_point, USE_POINT);
947 mark_regno_live (reg->regno, reg->biggest_mode);
948 check_pseudos_live_through_calls (reg->regno, last_call_abi);
951 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
952 if (reg->type != OP_OUT)
953 make_hard_regno_live (reg->regno);
955 if (curr_id->arg_hard_regs != NULL)
956 /* Make argument hard registers live. */
957 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
958 if (HARD_REGISTER_NUM_P (regno))
959 make_hard_regno_live (regno);
961 sparseset_and_compl (dead_set, start_living, start_dying);
963 sparseset_clear (start_dying);
965 /* Mark early clobber outputs dead. */
966 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
967 if (reg->type != OP_IN
968 && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
970 if (reg->type == OP_OUT)
971 update_pseudo_point (reg->regno, curr_point, DEF_POINT);
972 mark_regno_dead (reg->regno, reg->biggest_mode);
974 /* We're done processing inputs, so make sure early clobber
975 operands that are both inputs and outputs are still live. */
976 if (reg->type == OP_INOUT)
977 mark_regno_live (reg->regno, reg->biggest_mode);
980 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
981 if (reg->type != OP_IN
982 && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
984 struct lra_insn_reg *reg2;
986 /* We can have early clobbered non-operand hard reg and
987 the same hard reg as an insn input. Don't make hard
988 reg dead before the insns. */
989 for (reg2 = curr_id->regs; reg2 != NULL; reg2 = reg2->next)
990 if (reg2->type != OP_OUT && reg2->regno == reg->regno)
991 break;
992 if (reg2 == NULL)
993 make_hard_regno_dead (reg->regno);
996 /* Increment the current program point if we must. */
997 if (sparseset_contains_pseudos_p (dead_set)
998 || sparseset_contains_pseudos_p (start_dying))
999 next_program_point (curr_point, freq);
1001 /* Update notes. */
1002 for (link_loc = &REG_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
1004 if (REG_NOTE_KIND (link) != REG_DEAD
1005 && REG_NOTE_KIND (link) != REG_UNUSED)
1007 else if (REG_P (XEXP (link, 0)))
1009 rtx note_reg = XEXP (link, 0);
1010 int note_regno = REGNO (note_reg);
1012 if ((REG_NOTE_KIND (link) == REG_DEAD
1013 && ! regnos_in_sparseset_p (dead_set, note_regno,
1014 GET_MODE (note_reg)))
1015 || (REG_NOTE_KIND (link) == REG_UNUSED
1016 && ! regnos_in_sparseset_p (unused_set, note_regno,
1017 GET_MODE (note_reg))))
1019 *link_loc = XEXP (link, 1);
1020 continue;
1022 if (REG_NOTE_KIND (link) == REG_DEAD)
1023 clear_sparseset_regnos (dead_set, note_regno,
1024 GET_MODE (note_reg));
1025 else if (REG_NOTE_KIND (link) == REG_UNUSED)
1026 clear_sparseset_regnos (unused_set, note_regno,
1027 GET_MODE (note_reg));
1029 link_loc = &XEXP (link, 1);
1031 EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
1032 add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
1033 EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
1034 add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
1037 if (bb_has_eh_pred (bb))
1038 /* Any pseudos that are currently live conflict with the eh_return
1039 data registers. For liveness purposes, these registers are set
1040 by artificial definitions at the start of the BB, so are not
1041 actually live on entry. */
1042 for (j = 0; ; ++j)
1044 unsigned int regno = EH_RETURN_DATA_REGNO (j);
1046 if (regno == INVALID_REGNUM)
1047 break;
1049 make_hard_regno_live (regno);
1050 make_hard_regno_dead (regno);
1053 /* Pseudos can't go in stack regs at the start of a basic block that
1054 is reached by an abnormal edge. Likewise for registers that are at
1055 least partly call clobbered, because caller-save, fixup_abnormal_edges
1056 and possibly the table driven EH machinery are not quite ready to
1057 handle such pseudos live across such edges. */
1058 if (bb_has_abnormal_pred (bb))
1060 HARD_REG_SET clobbers;
1062 CLEAR_HARD_REG_SET (clobbers);
1063 #ifdef STACK_REGS
1064 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
1065 lra_reg_info[px].no_stack_p = true;
1066 for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1067 SET_HARD_REG_BIT (clobbers, px);
1068 #endif
1069 /* No need to record conflicts for call clobbered regs if we
1070 have nonlocal labels around, as we don't ever try to
1071 allocate such regs in this case. */
1072 if (!cfun->has_nonlocal_label
1073 && has_abnormal_call_or_eh_pred_edge_p (bb))
1074 for (px = 0; HARD_REGISTER_NUM_P (px); px++)
1075 if (eh_edge_abi.clobbers_at_least_part_of_reg_p (px)
1076 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
1077 /* We should create a conflict of PIC pseudo with PIC
1078 hard reg as PIC hard reg can have a wrong value after
1079 jump described by the abnormal edge. In this case we
1080 cannot allocate PIC hard reg to PIC pseudo as PIC
1081 pseudo will also have a wrong value. */
1082 || (px == REAL_PIC_OFFSET_TABLE_REGNUM
1083 && pic_offset_table_rtx != NULL_RTX
1084 && !HARD_REGISTER_P (pic_offset_table_rtx))
1085 #endif
1087 SET_HARD_REG_BIT (clobbers, px);
1089 clobbers &= ~hard_regs_live;
1090 for (px = 0; HARD_REGISTER_NUM_P (px); px++)
1091 if (TEST_HARD_REG_BIT (clobbers, px))
1093 make_hard_regno_live (px);
1094 make_hard_regno_dead (px);
1098 bool live_change_p = false;
1099 /* Check if bb border live info was changed. */
1100 unsigned int live_pseudos_num = 0;
1101 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb),
1102 FIRST_PSEUDO_REGISTER, j, bi)
1104 live_pseudos_num++;
1105 if (! sparseset_bit_p (pseudos_live, j))
1107 live_change_p = true;
1108 if (lra_dump_file != NULL)
1109 fprintf (lra_dump_file,
1110 " r%d is removed as live at bb%d start\n", j, bb->index);
1111 break;
1114 if (! live_change_p
1115 && sparseset_cardinality (pseudos_live) != live_pseudos_num)
1117 live_change_p = true;
1118 if (lra_dump_file != NULL)
1119 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
1120 if (! bitmap_bit_p (df_get_live_in (bb), j))
1121 fprintf (lra_dump_file,
1122 " r%d is added to live at bb%d start\n", j, bb->index);
1124 /* See if we'll need an increment at the end of this basic block.
1125 An increment is needed if the PSEUDOS_LIVE set is not empty,
1126 to make sure the finish points are set up correctly. */
1127 need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0);
1129 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
1131 update_pseudo_point (i, curr_point, DEF_POINT);
1132 mark_pseudo_dead (i);
1135 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
1137 if (sparseset_cardinality (pseudos_live_through_calls) == 0)
1138 break;
1139 if (sparseset_bit_p (pseudos_live_through_calls, j))
1140 check_pseudos_live_through_calls (j, last_call_abi);
1143 for (i = 0; HARD_REGISTER_NUM_P (i); ++i)
1145 if (!TEST_HARD_REG_BIT (hard_regs_live, i))
1146 continue;
1148 if (!TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
1149 continue;
1151 if (bitmap_bit_p (df_get_live_in (bb), i))
1152 continue;
1154 live_change_p = true;
1155 if (lra_dump_file)
1156 fprintf (lra_dump_file,
1157 " hard reg r%d is added to live at bb%d start\n", i,
1158 bb->index);
1159 bitmap_set_bit (df_get_live_in (bb), i);
1162 if (need_curr_point_incr)
1163 next_program_point (curr_point, freq);
1165 return live_change_p;
1168 /* Compress pseudo live ranges by removing program points where
1169 nothing happens. Complexity of many algorithms in LRA is linear
1170 function of program points number. To speed up the code we try to
1171 minimize the number of the program points here. */
1172 static void
1173 remove_some_program_points_and_update_live_ranges (void)
1175 unsigned i;
1176 int n, max_regno;
1177 int *map;
1178 lra_live_range_t r, prev_r, next_r;
1179 sbitmap_iterator sbi;
1180 bool born_p, dead_p, prev_born_p, prev_dead_p;
1182 auto_sbitmap born (lra_live_max_point);
1183 auto_sbitmap dead (lra_live_max_point);
1184 bitmap_clear (born);
1185 bitmap_clear (dead);
1186 max_regno = max_reg_num ();
1187 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1189 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1191 lra_assert (r->start <= r->finish);
1192 bitmap_set_bit (born, r->start);
1193 bitmap_set_bit (dead, r->finish);
1196 auto_sbitmap born_or_dead (lra_live_max_point);
1197 bitmap_ior (born_or_dead, born, dead);
1198 map = XCNEWVEC (int, lra_live_max_point);
1199 n = -1;
1200 prev_born_p = prev_dead_p = false;
1201 EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1203 born_p = bitmap_bit_p (born, i);
1204 dead_p = bitmap_bit_p (dead, i);
1205 if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1206 || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1208 map[i] = n;
1209 lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
1211 else
1213 map[i] = ++n;
1214 lra_point_freq[n] = lra_point_freq[i];
1216 prev_born_p = born_p;
1217 prev_dead_p = dead_p;
1219 n++;
1220 if (lra_dump_file != NULL)
1221 fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1222 lra_live_max_point, n,
1223 lra_live_max_point ? 100 * n / lra_live_max_point : 100);
1224 if (n < lra_live_max_point)
1226 lra_live_max_point = n;
1227 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1229 for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
1230 r != NULL;
1231 r = next_r)
1233 next_r = r->next;
1234 r->start = map[r->start];
1235 r->finish = map[r->finish];
1236 if (prev_r == NULL || prev_r->start > r->finish + 1)
1238 prev_r = r;
1239 continue;
1241 prev_r->start = r->start;
1242 prev_r->next = next_r;
1243 lra_live_range_pool.remove (r);
1247 free (map);
1250 /* Print live ranges R to file F. */
1251 void
1252 lra_print_live_range_list (FILE *f, lra_live_range_t r)
1254 for (; r != NULL; r = r->next)
1255 fprintf (f, " [%d..%d]", r->start, r->finish);
1256 fprintf (f, "\n");
1259 DEBUG_FUNCTION void
1260 debug (lra_live_range &ref)
1262 lra_print_live_range_list (stderr, &ref);
1265 DEBUG_FUNCTION void
1266 debug (lra_live_range *ptr)
1268 if (ptr)
1269 debug (*ptr);
1270 else
1271 fprintf (stderr, "<nil>\n");
1274 /* Print live ranges R to stderr. */
1275 void
1276 lra_debug_live_range_list (lra_live_range_t r)
1278 lra_print_live_range_list (stderr, r);
1281 /* Print live ranges of pseudo REGNO to file F. */
1282 static void
1283 print_pseudo_live_ranges (FILE *f, int regno)
1285 if (lra_reg_info[regno].live_ranges == NULL)
1286 return;
1287 fprintf (f, " r%d:", regno);
1288 lra_print_live_range_list (f, lra_reg_info[regno].live_ranges);
1291 /* Print live ranges of pseudo REGNO to stderr. */
1292 void
1293 lra_debug_pseudo_live_ranges (int regno)
1295 print_pseudo_live_ranges (stderr, regno);
1298 /* Print live ranges of all pseudos to file F. */
1299 static void
1300 print_live_ranges (FILE *f)
1302 int i, max_regno;
1304 max_regno = max_reg_num ();
1305 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1306 print_pseudo_live_ranges (f, i);
1309 /* Print live ranges of all pseudos to stderr. */
1310 void
1311 lra_debug_live_ranges (void)
1313 print_live_ranges (stderr);
1316 /* Compress pseudo live ranges. */
1317 static void
1318 compress_live_ranges (void)
1320 remove_some_program_points_and_update_live_ranges ();
1321 if (lra_dump_file != NULL)
1323 fprintf (lra_dump_file, "Ranges after the compression:\n");
1324 print_live_ranges (lra_dump_file);
1330 /* The number of the current live range pass. */
1331 int lra_live_range_iter;
1333 /* The function creates live ranges only for memory pseudos (or for
1334 all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos. It
1335 also does dead insn elimination if DEAD_INSN_P and global live
1336 analysis only for pseudos and only if the pseudo live info was
1337 changed on a BB border. Return TRUE if the live info was
1338 changed. */
1339 static bool
1340 lra_create_live_ranges_1 (bool all_p, bool dead_insn_p)
1342 basic_block bb;
1343 int i, hard_regno, max_regno = max_reg_num ();
1344 int curr_point;
1345 bool bb_live_change_p, have_referenced_pseudos = false;
1347 timevar_push (TV_LRA_CREATE_LIVE_RANGES);
1349 complete_info_p = all_p;
1350 if (lra_dump_file != NULL)
1351 fprintf (lra_dump_file,
1352 "\n********** Pseudo live ranges #%d: **********\n\n",
1353 ++lra_live_range_iter);
1354 memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage));
1355 for (i = 0; i < max_regno; i++)
1357 lra_reg_info[i].live_ranges = NULL;
1358 CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1359 lra_reg_info[i].preferred_hard_regno1 = -1;
1360 lra_reg_info[i].preferred_hard_regno2 = -1;
1361 lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1362 lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1363 #ifdef STACK_REGS
1364 lra_reg_info[i].no_stack_p = false;
1365 #endif
1366 /* The biggest mode is already set but its value might be to
1367 conservative because of recent transformation. Here in this
1368 file we recalculate it again as it costs practically
1369 nothing. */
1370 if (!HARD_REGISTER_NUM_P (i) && regno_reg_rtx[i] != NULL_RTX)
1371 lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
1372 else
1373 lra_reg_info[i].biggest_mode = VOIDmode;
1374 if (!HARD_REGISTER_NUM_P (i)
1375 && lra_reg_info[i].nrefs != 0)
1377 if ((hard_regno = reg_renumber[i]) >= 0)
1378 lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
1379 have_referenced_pseudos = true;
1382 lra_free_copies ();
1384 /* Under some circumstances, we can have functions without pseudo
1385 registers. For such functions, lra_live_max_point will be 0,
1386 see e.g. PR55604, and there's nothing more to do for us here. */
1387 if (! have_referenced_pseudos)
1389 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1390 return false;
1393 pseudos_live = sparseset_alloc (max_regno);
1394 pseudos_live_through_calls = sparseset_alloc (max_regno);
1395 pseudos_live_through_setjumps = sparseset_alloc (max_regno);
1396 start_living = sparseset_alloc (max_regno);
1397 start_dying = sparseset_alloc (max_regno);
1398 dead_set = sparseset_alloc (max_regno);
1399 unused_set = sparseset_alloc (max_regno);
1400 curr_point = 0;
1401 unsigned new_length = get_max_uid () * 2;
1402 point_freq_vec.truncate (0);
1403 point_freq_vec.reserve_exact (new_length);
1404 lra_point_freq = point_freq_vec.address ();
1405 auto_vec<int, 20> post_order_rev_cfg;
1406 inverted_post_order_compute (&post_order_rev_cfg);
1407 lra_assert (post_order_rev_cfg.length () == (unsigned) n_basic_blocks_for_fn (cfun));
1408 bb_live_change_p = false;
1409 for (i = post_order_rev_cfg.length () - 1; i >= 0; --i)
1411 bb = BASIC_BLOCK_FOR_FN (cfun, post_order_rev_cfg[i]);
1412 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
1413 == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1414 continue;
1415 if (process_bb_lives (bb, curr_point, dead_insn_p))
1416 bb_live_change_p = true;
1418 if (bb_live_change_p)
1420 /* We need to clear pseudo live info as some pseudos can
1421 disappear, e.g. pseudos with used equivalences. */
1422 FOR_EACH_BB_FN (bb, cfun)
1424 bitmap_clear_range (df_get_live_in (bb), FIRST_PSEUDO_REGISTER,
1425 max_regno - FIRST_PSEUDO_REGISTER);
1426 bitmap_clear_range (df_get_live_out (bb), FIRST_PSEUDO_REGISTER,
1427 max_regno - FIRST_PSEUDO_REGISTER);
1429 /* As we did not change CFG since LRA start we can use
1430 DF-infrastructure solver to solve live data flow problem. */
1431 for (int i = 0; HARD_REGISTER_NUM_P (i); ++i)
1433 if (TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
1434 bitmap_clear_bit (&all_hard_regs_bitmap, i);
1436 df_simple_dataflow
1437 (DF_BACKWARD, NULL, live_con_fun_0, live_con_fun_n,
1438 live_trans_fun, &all_blocks,
1439 df_get_postorder (DF_BACKWARD), df_get_n_blocks (DF_BACKWARD));
1440 if (lra_dump_file != NULL)
1442 fprintf (lra_dump_file,
1443 "Global pseudo live data have been updated:\n");
1444 basic_block bb;
1445 FOR_EACH_BB_FN (bb, cfun)
1447 bb_data_t bb_info = get_bb_data (bb);
1448 bitmap bb_livein = df_get_live_in (bb);
1449 bitmap bb_liveout = df_get_live_out (bb);
1451 fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
1452 lra_dump_bitmap_with_title (" gen:",
1453 &bb_info->gen_pseudos, bb->index);
1454 lra_dump_bitmap_with_title (" killed:",
1455 &bb_info->killed_pseudos, bb->index);
1456 lra_dump_bitmap_with_title (" livein:", bb_livein, bb->index);
1457 lra_dump_bitmap_with_title (" liveout:", bb_liveout, bb->index);
1461 lra_live_max_point = curr_point;
1462 if (lra_dump_file != NULL)
1463 print_live_ranges (lra_dump_file);
1464 /* Clean up. */
1465 sparseset_free (unused_set);
1466 sparseset_free (dead_set);
1467 sparseset_free (start_dying);
1468 sparseset_free (start_living);
1469 sparseset_free (pseudos_live_through_calls);
1470 sparseset_free (pseudos_live_through_setjumps);
1471 sparseset_free (pseudos_live);
1472 compress_live_ranges ();
1473 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1474 return bb_live_change_p;
1477 /* The main entry function creates live-ranges and other live info
1478 necessary for the assignment sub-pass. It uses
1479 lra_creates_live_ranges_1 -- so read comments for the
1480 function. */
1481 void
1482 lra_create_live_ranges (bool all_p, bool dead_insn_p)
1484 if (! lra_create_live_ranges_1 (all_p, dead_insn_p))
1485 return;
1486 if (lra_dump_file != NULL)
1487 fprintf (lra_dump_file, "Live info was changed -- recalculate it\n");
1488 /* Live info was changed on a bb border. It means that some info,
1489 e.g. about conflict regs, calls crossed, and live ranges may be
1490 wrong. We need this info for allocation. So recalculate it
1491 again but without removing dead insns which can change live info
1492 again. Repetitive live range calculations are expensive therefore
1493 we stop here as we already have correct info although some
1494 improvement in rare cases could be possible on this sub-pass if
1495 we do dead insn elimination again (still the improvement may
1496 happen later). */
1497 lra_clear_live_ranges ();
1498 bool res = lra_create_live_ranges_1 (all_p, false);
1499 lra_assert (! res);
1502 /* Finish all live ranges. */
1503 void
1504 lra_clear_live_ranges (void)
1506 int i;
1508 for (i = 0; i < max_reg_num (); i++)
1509 free_live_range_list (lra_reg_info[i].live_ranges);
1510 point_freq_vec.release ();
1513 /* Initialize live ranges data once per function. */
1514 void
1515 lra_live_ranges_init (void)
1517 bitmap_initialize (&temp_bitmap, &reg_obstack);
1518 initiate_live_solver ();
1521 /* Finish live ranges data once per function. */
1522 void
1523 lra_live_ranges_finish (void)
1525 finish_live_solver ();
1526 bitmap_clear (&temp_bitmap);
1527 lra_live_range_pool.release ();