ada: Fix wrong finalization for call to BIP function in conditional expression
[official-gcc.git] / gcc / lra-lives.cc
blobf7a3ba8d76a3120164d93c92cd1ee1ba320c1469
1 /* Build live ranges for pseudos.
2 Copyright (C) 2010-2023 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
728 && (reg->regno < FIRST_PSEUDO_REGISTER
729 ? TEST_HARD_REG_BIT (hard_regs_live, reg->regno)
730 : sparseset_bit_p (pseudos_live, reg->regno)))
732 remove_p = false;
733 break;
735 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
736 if (reg->type != OP_IN)
738 remove_p = false;
739 break;
742 if (remove_p && ! volatile_refs_p (PATTERN (curr_insn)))
744 dst_regno = REGNO (SET_DEST (set));
745 if (lra_dump_file != NULL)
746 fprintf (lra_dump_file, " Deleting dead insn %u\n",
747 INSN_UID (curr_insn));
748 lra_set_insn_deleted (curr_insn);
749 if (lra_reg_info[dst_regno].nrefs == 0)
751 /* There might be some debug insns with the pseudo. */
752 unsigned int uid;
753 rtx_insn *insn;
755 bitmap_copy (&temp_bitmap, &lra_reg_info[dst_regno].insn_bitmap);
756 EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap, 0, uid, bi)
758 insn = lra_insn_recog_data[uid]->insn;
759 lra_substitute_pseudo_within_insn (insn, dst_regno,
760 SET_SRC (set), true);
761 lra_update_insn_regno_info (insn);
764 continue;
768 /* Update max ref width and hard reg usage. */
769 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
771 int regno = reg->regno;
773 if (partial_subreg_p (lra_reg_info[regno].biggest_mode,
774 reg->biggest_mode))
775 lra_reg_info[regno].biggest_mode = reg->biggest_mode;
776 if (HARD_REGISTER_NUM_P (regno))
777 lra_hard_reg_usage[regno] += freq;
780 call_p = CALL_P (curr_insn);
782 /* If we have a simple register copy and the source reg is live after
783 this instruction, then remove the source reg from the live set so
784 that it will not conflict with the destination reg. */
785 rtx ignore_reg = non_conflicting_reg_copy_p (curr_insn);
786 if (ignore_reg != NULL_RTX)
788 int ignore_regno = REGNO (ignore_reg);
789 if (HARD_REGISTER_NUM_P (ignore_regno)
790 && TEST_HARD_REG_BIT (hard_regs_live, ignore_regno))
791 CLEAR_HARD_REG_BIT (hard_regs_live, ignore_regno);
792 else if (!HARD_REGISTER_NUM_P (ignore_regno)
793 && sparseset_bit_p (pseudos_live, ignore_regno))
794 sparseset_clear_bit (pseudos_live, ignore_regno);
795 else
796 /* We don't need any special handling of the source reg if
797 it is dead after this instruction. */
798 ignore_reg = NULL_RTX;
801 src_regno = (set != NULL_RTX && REG_P (SET_SRC (set))
802 ? REGNO (SET_SRC (set)) : -1);
803 dst_regno = (set != NULL_RTX && REG_P (SET_DEST (set))
804 ? REGNO (SET_DEST (set)) : -1);
805 if (complete_info_p
806 && src_regno >= 0 && dst_regno >= 0
807 /* Check that source regno does not conflict with
808 destination regno to exclude most impossible
809 preferences. */
810 && (((!HARD_REGISTER_NUM_P (src_regno)
811 && (! sparseset_bit_p (pseudos_live, src_regno)
812 || (!HARD_REGISTER_NUM_P (dst_regno)
813 && lra_reg_val_equal_p (src_regno,
814 lra_reg_info[dst_regno].val,
815 lra_reg_info[dst_regno].offset))))
816 || (HARD_REGISTER_NUM_P (src_regno)
817 && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno)))
818 /* It might be 'inheritance pseudo <- reload pseudo'. */
819 || (src_regno >= lra_constraint_new_regno_start
820 && dst_regno >= lra_constraint_new_regno_start
821 /* Remember to skip special cases where src/dest regnos are
822 the same, e.g. insn SET pattern has matching constraints
823 like =r,0. */
824 && src_regno != dst_regno)))
826 int hard_regno = -1, regno = -1;
828 if (dst_regno >= lra_constraint_new_regno_start
829 && src_regno >= lra_constraint_new_regno_start)
831 /* It might be still an original (non-reload) insn with
832 one unused output and a constraint requiring to use
833 the same reg for input/output operands. In this case
834 dst_regno and src_regno have the same value, we don't
835 need a misleading copy for this case. */
836 if (dst_regno != src_regno)
837 lra_create_copy (dst_regno, src_regno, freq);
839 else if (dst_regno >= lra_constraint_new_regno_start)
841 if (!HARD_REGISTER_NUM_P (hard_regno = src_regno))
842 hard_regno = reg_renumber[src_regno];
843 regno = dst_regno;
845 else if (src_regno >= lra_constraint_new_regno_start)
847 if (!HARD_REGISTER_NUM_P (hard_regno = dst_regno))
848 hard_regno = reg_renumber[dst_regno];
849 regno = src_regno;
851 if (regno >= 0 && hard_regno >= 0)
852 lra_setup_reload_pseudo_preferenced_hard_reg
853 (regno, hard_regno, freq);
856 sparseset_clear (start_living);
858 /* Mark each defined value as live. We need to do this for
859 unused values because they still conflict with quantities
860 that are live at the time of the definition. */
861 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
862 if (reg->type != OP_IN)
864 update_pseudo_point (reg->regno, curr_point, USE_POINT);
865 mark_regno_live (reg->regno, reg->biggest_mode);
866 /* ??? Should be a no-op for unused registers. */
867 check_pseudos_live_through_calls (reg->regno, last_call_abi);
870 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
871 if (reg->type != OP_IN)
872 make_hard_regno_live (reg->regno);
874 if (curr_id->arg_hard_regs != NULL)
875 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
876 if (!HARD_REGISTER_NUM_P (regno))
877 /* It is a clobber. */
878 make_hard_regno_live (regno - FIRST_PSEUDO_REGISTER);
880 sparseset_copy (unused_set, start_living);
882 sparseset_clear (start_dying);
884 /* See which defined values die here. */
885 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
886 if (reg->type != OP_IN
887 && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
889 if (reg->type == OP_OUT)
890 update_pseudo_point (reg->regno, curr_point, DEF_POINT);
891 mark_regno_dead (reg->regno, reg->biggest_mode);
894 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
895 if (reg->type != OP_IN
896 && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
897 make_hard_regno_dead (reg->regno);
899 if (curr_id->arg_hard_regs != NULL)
900 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
901 if (!HARD_REGISTER_NUM_P (regno))
902 /* It is a clobber. */
903 make_hard_regno_dead (regno - FIRST_PSEUDO_REGISTER);
905 if (call_p)
907 function_abi call_abi = insn_callee_abi (curr_insn);
909 if (last_call_abi != call_abi)
910 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
911 check_pseudos_live_through_calls (j, last_call_abi);
913 last_call_abi = call_abi;
915 sparseset_ior (pseudos_live_through_calls,
916 pseudos_live_through_calls, pseudos_live);
917 if (cfun->has_nonlocal_label
918 || (!targetm.setjmp_preserves_nonvolatile_regs_p ()
919 && (find_reg_note (curr_insn, REG_SETJMP, NULL_RTX)
920 != NULL_RTX)))
921 sparseset_ior (pseudos_live_through_setjumps,
922 pseudos_live_through_setjumps, pseudos_live);
925 /* Increment the current program point if we must. */
926 if (sparseset_contains_pseudos_p (unused_set)
927 || sparseset_contains_pseudos_p (start_dying))
928 next_program_point (curr_point, freq);
930 /* If we removed the source reg from a simple register copy from the
931 live set above, then add it back now so we don't accidentally add
932 it to the start_living set below. */
933 if (ignore_reg != NULL_RTX)
935 int ignore_regno = REGNO (ignore_reg);
936 if (HARD_REGISTER_NUM_P (ignore_regno))
937 SET_HARD_REG_BIT (hard_regs_live, ignore_regno);
938 else
939 sparseset_set_bit (pseudos_live, ignore_regno);
942 sparseset_clear (start_living);
944 /* Mark each used value as live. */
945 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
946 if (reg->type != OP_OUT)
948 if (reg->type == OP_IN)
949 update_pseudo_point (reg->regno, curr_point, USE_POINT);
950 mark_regno_live (reg->regno, reg->biggest_mode);
951 check_pseudos_live_through_calls (reg->regno, last_call_abi);
954 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
955 if (reg->type != OP_OUT)
956 make_hard_regno_live (reg->regno);
958 if (curr_id->arg_hard_regs != NULL)
959 /* Make argument hard registers live. */
960 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
961 if (HARD_REGISTER_NUM_P (regno))
962 make_hard_regno_live (regno);
964 sparseset_and_compl (dead_set, start_living, start_dying);
966 sparseset_clear (start_dying);
968 /* Mark early clobber outputs dead. */
969 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
970 if (reg->type != OP_IN
971 && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
973 if (reg->type == OP_OUT)
974 update_pseudo_point (reg->regno, curr_point, DEF_POINT);
975 mark_regno_dead (reg->regno, reg->biggest_mode);
977 /* We're done processing inputs, so make sure early clobber
978 operands that are both inputs and outputs are still live. */
979 if (reg->type == OP_INOUT)
980 mark_regno_live (reg->regno, reg->biggest_mode);
983 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
984 if (reg->type != OP_IN
985 && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
987 struct lra_insn_reg *reg2;
989 /* We can have early clobbered non-operand hard reg and
990 the same hard reg as an insn input. Don't make hard
991 reg dead before the insns. */
992 for (reg2 = curr_id->regs; reg2 != NULL; reg2 = reg2->next)
993 if (reg2->type != OP_OUT && reg2->regno == reg->regno)
994 break;
995 if (reg2 == NULL)
996 make_hard_regno_dead (reg->regno);
999 /* Increment the current program point if we must. */
1000 if (sparseset_contains_pseudos_p (dead_set)
1001 || sparseset_contains_pseudos_p (start_dying))
1002 next_program_point (curr_point, freq);
1004 /* Update notes. */
1005 for (link_loc = &REG_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
1007 if (REG_NOTE_KIND (link) != REG_DEAD
1008 && REG_NOTE_KIND (link) != REG_UNUSED)
1010 else if (REG_P (XEXP (link, 0)))
1012 rtx note_reg = XEXP (link, 0);
1013 int note_regno = REGNO (note_reg);
1015 if ((REG_NOTE_KIND (link) == REG_DEAD
1016 && ! regnos_in_sparseset_p (dead_set, note_regno,
1017 GET_MODE (note_reg)))
1018 || (REG_NOTE_KIND (link) == REG_UNUSED
1019 && ! regnos_in_sparseset_p (unused_set, note_regno,
1020 GET_MODE (note_reg))))
1022 *link_loc = XEXP (link, 1);
1023 continue;
1025 if (REG_NOTE_KIND (link) == REG_DEAD)
1026 clear_sparseset_regnos (dead_set, note_regno,
1027 GET_MODE (note_reg));
1028 else if (REG_NOTE_KIND (link) == REG_UNUSED)
1029 clear_sparseset_regnos (unused_set, note_regno,
1030 GET_MODE (note_reg));
1032 link_loc = &XEXP (link, 1);
1034 EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
1035 add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
1036 EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
1037 add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
1040 if (bb_has_eh_pred (bb))
1041 /* Any pseudos that are currently live conflict with the eh_return
1042 data registers. For liveness purposes, these registers are set
1043 by artificial definitions at the start of the BB, so are not
1044 actually live on entry. */
1045 for (j = 0; ; ++j)
1047 unsigned int regno = EH_RETURN_DATA_REGNO (j);
1049 if (regno == INVALID_REGNUM)
1050 break;
1052 make_hard_regno_live (regno);
1053 make_hard_regno_dead (regno);
1056 /* Pseudos can't go in stack regs at the start of a basic block that
1057 is reached by an abnormal edge. Likewise for registers that are at
1058 least partly call clobbered, because caller-save, fixup_abnormal_edges
1059 and possibly the table driven EH machinery are not quite ready to
1060 handle such pseudos live across such edges. */
1061 if (bb_has_abnormal_pred (bb))
1063 HARD_REG_SET clobbers;
1065 CLEAR_HARD_REG_SET (clobbers);
1066 #ifdef STACK_REGS
1067 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
1068 lra_reg_info[px].no_stack_p = true;
1069 for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1070 SET_HARD_REG_BIT (clobbers, px);
1071 #endif
1072 /* No need to record conflicts for call clobbered regs if we
1073 have nonlocal labels around, as we don't ever try to
1074 allocate such regs in this case. */
1075 if (!cfun->has_nonlocal_label
1076 && has_abnormal_call_or_eh_pred_edge_p (bb))
1077 for (px = 0; HARD_REGISTER_NUM_P (px); px++)
1078 if (eh_edge_abi.clobbers_at_least_part_of_reg_p (px)
1079 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
1080 /* We should create a conflict of PIC pseudo with PIC
1081 hard reg as PIC hard reg can have a wrong value after
1082 jump described by the abnormal edge. In this case we
1083 cannot allocate PIC hard reg to PIC pseudo as PIC
1084 pseudo will also have a wrong value. */
1085 || (px == REAL_PIC_OFFSET_TABLE_REGNUM
1086 && pic_offset_table_rtx != NULL_RTX
1087 && !HARD_REGISTER_P (pic_offset_table_rtx))
1088 #endif
1090 SET_HARD_REG_BIT (clobbers, px);
1092 clobbers &= ~hard_regs_live;
1093 for (px = 0; HARD_REGISTER_NUM_P (px); px++)
1094 if (TEST_HARD_REG_BIT (clobbers, px))
1096 make_hard_regno_live (px);
1097 make_hard_regno_dead (px);
1101 bool live_change_p = false;
1102 /* Check if bb border live info was changed. */
1103 unsigned int live_pseudos_num = 0;
1104 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb),
1105 FIRST_PSEUDO_REGISTER, j, bi)
1107 live_pseudos_num++;
1108 if (! sparseset_bit_p (pseudos_live, j))
1110 live_change_p = true;
1111 if (lra_dump_file != NULL)
1112 fprintf (lra_dump_file,
1113 " r%d is removed as live at bb%d start\n", j, bb->index);
1114 break;
1117 if (! live_change_p
1118 && sparseset_cardinality (pseudos_live) != live_pseudos_num)
1120 live_change_p = true;
1121 if (lra_dump_file != NULL)
1122 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
1123 if (! bitmap_bit_p (df_get_live_in (bb), j))
1124 fprintf (lra_dump_file,
1125 " r%d is added to live at bb%d start\n", j, bb->index);
1127 /* See if we'll need an increment at the end of this basic block.
1128 An increment is needed if the PSEUDOS_LIVE set is not empty,
1129 to make sure the finish points are set up correctly. */
1130 need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0);
1132 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
1134 update_pseudo_point (i, curr_point, DEF_POINT);
1135 mark_pseudo_dead (i);
1138 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
1140 if (sparseset_cardinality (pseudos_live_through_calls) == 0)
1141 break;
1142 if (sparseset_bit_p (pseudos_live_through_calls, j))
1143 check_pseudos_live_through_calls (j, last_call_abi);
1146 for (i = 0; HARD_REGISTER_NUM_P (i); ++i)
1148 if (!TEST_HARD_REG_BIT (hard_regs_live, i))
1149 continue;
1151 if (!TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
1152 continue;
1154 if (bitmap_bit_p (df_get_live_in (bb), i))
1155 continue;
1157 live_change_p = true;
1158 if (lra_dump_file)
1159 fprintf (lra_dump_file,
1160 " hard reg r%d is added to live at bb%d start\n", i,
1161 bb->index);
1162 bitmap_set_bit (df_get_live_in (bb), i);
1165 if (need_curr_point_incr)
1166 next_program_point (curr_point, freq);
1168 return live_change_p;
1171 /* Compress pseudo live ranges by removing program points where
1172 nothing happens. Complexity of many algorithms in LRA is linear
1173 function of program points number. To speed up the code we try to
1174 minimize the number of the program points here. */
1175 static void
1176 remove_some_program_points_and_update_live_ranges (void)
1178 unsigned i;
1179 int n, max_regno;
1180 int *map;
1181 lra_live_range_t r, prev_r, next_r;
1182 sbitmap_iterator sbi;
1183 bool born_p, dead_p, prev_born_p, prev_dead_p;
1185 auto_sbitmap born (lra_live_max_point);
1186 auto_sbitmap dead (lra_live_max_point);
1187 bitmap_clear (born);
1188 bitmap_clear (dead);
1189 max_regno = max_reg_num ();
1190 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1192 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1194 lra_assert (r->start <= r->finish);
1195 bitmap_set_bit (born, r->start);
1196 bitmap_set_bit (dead, r->finish);
1199 auto_sbitmap born_or_dead (lra_live_max_point);
1200 bitmap_ior (born_or_dead, born, dead);
1201 map = XCNEWVEC (int, lra_live_max_point);
1202 n = -1;
1203 prev_born_p = prev_dead_p = false;
1204 EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1206 born_p = bitmap_bit_p (born, i);
1207 dead_p = bitmap_bit_p (dead, i);
1208 if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1209 || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1211 map[i] = n;
1212 lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
1214 else
1216 map[i] = ++n;
1217 lra_point_freq[n] = lra_point_freq[i];
1219 prev_born_p = born_p;
1220 prev_dead_p = dead_p;
1222 n++;
1223 if (lra_dump_file != NULL)
1224 fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1225 lra_live_max_point, n,
1226 lra_live_max_point ? 100 * n / lra_live_max_point : 100);
1227 if (n < lra_live_max_point)
1229 lra_live_max_point = n;
1230 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1232 for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
1233 r != NULL;
1234 r = next_r)
1236 next_r = r->next;
1237 r->start = map[r->start];
1238 r->finish = map[r->finish];
1239 if (prev_r == NULL || prev_r->start > r->finish + 1)
1241 prev_r = r;
1242 continue;
1244 prev_r->start = r->start;
1245 prev_r->next = next_r;
1246 lra_live_range_pool.remove (r);
1250 free (map);
1253 /* Print live ranges R to file F. */
1254 void
1255 lra_print_live_range_list (FILE *f, lra_live_range_t r)
1257 for (; r != NULL; r = r->next)
1258 fprintf (f, " [%d..%d]", r->start, r->finish);
1259 fprintf (f, "\n");
1262 DEBUG_FUNCTION void
1263 debug (lra_live_range &ref)
1265 lra_print_live_range_list (stderr, &ref);
1268 DEBUG_FUNCTION void
1269 debug (lra_live_range *ptr)
1271 if (ptr)
1272 debug (*ptr);
1273 else
1274 fprintf (stderr, "<nil>\n");
1277 /* Print live ranges R to stderr. */
1278 void
1279 lra_debug_live_range_list (lra_live_range_t r)
1281 lra_print_live_range_list (stderr, r);
1284 /* Print live ranges of pseudo REGNO to file F. */
1285 static void
1286 print_pseudo_live_ranges (FILE *f, int regno)
1288 if (lra_reg_info[regno].live_ranges == NULL)
1289 return;
1290 fprintf (f, " r%d:", regno);
1291 lra_print_live_range_list (f, lra_reg_info[regno].live_ranges);
1294 /* Print live ranges of pseudo REGNO to stderr. */
1295 void
1296 lra_debug_pseudo_live_ranges (int regno)
1298 print_pseudo_live_ranges (stderr, regno);
1301 /* Print live ranges of all pseudos to file F. */
1302 static void
1303 print_live_ranges (FILE *f)
1305 int i, max_regno;
1307 max_regno = max_reg_num ();
1308 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1309 print_pseudo_live_ranges (f, i);
1312 /* Print live ranges of all pseudos to stderr. */
1313 void
1314 lra_debug_live_ranges (void)
1316 print_live_ranges (stderr);
1319 /* Compress pseudo live ranges. */
1320 static void
1321 compress_live_ranges (void)
1323 remove_some_program_points_and_update_live_ranges ();
1324 if (lra_dump_file != NULL)
1326 fprintf (lra_dump_file, "Ranges after the compression:\n");
1327 print_live_ranges (lra_dump_file);
1333 /* The number of the current live range pass. */
1334 int lra_live_range_iter;
1336 /* The function creates live ranges only for memory pseudos (or for
1337 all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos. It
1338 also does dead insn elimination if DEAD_INSN_P and global live
1339 analysis only for pseudos and only if the pseudo live info was
1340 changed on a BB border. Return TRUE if the live info was
1341 changed. */
1342 static bool
1343 lra_create_live_ranges_1 (bool all_p, bool dead_insn_p)
1345 basic_block bb;
1346 int i, hard_regno, max_regno = max_reg_num ();
1347 int curr_point;
1348 bool bb_live_change_p, have_referenced_pseudos = false;
1350 timevar_push (TV_LRA_CREATE_LIVE_RANGES);
1352 complete_info_p = all_p;
1353 if (lra_dump_file != NULL)
1354 fprintf (lra_dump_file,
1355 "\n********** Pseudo live ranges #%d: **********\n\n",
1356 ++lra_live_range_iter);
1357 memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage));
1358 for (i = 0; i < max_regno; i++)
1360 lra_reg_info[i].live_ranges = NULL;
1361 CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1362 lra_reg_info[i].preferred_hard_regno1 = -1;
1363 lra_reg_info[i].preferred_hard_regno2 = -1;
1364 lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1365 lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1366 #ifdef STACK_REGS
1367 lra_reg_info[i].no_stack_p = false;
1368 #endif
1369 /* The biggest mode is already set but its value might be to
1370 conservative because of recent transformation. Here in this
1371 file we recalculate it again as it costs practically
1372 nothing. */
1373 if (!HARD_REGISTER_NUM_P (i) && regno_reg_rtx[i] != NULL_RTX)
1374 lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
1375 else
1376 lra_reg_info[i].biggest_mode = VOIDmode;
1377 if (!HARD_REGISTER_NUM_P (i)
1378 && lra_reg_info[i].nrefs != 0)
1380 if ((hard_regno = reg_renumber[i]) >= 0)
1381 lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
1382 have_referenced_pseudos = true;
1385 lra_free_copies ();
1387 /* Under some circumstances, we can have functions without pseudo
1388 registers. For such functions, lra_live_max_point will be 0,
1389 see e.g. PR55604, and there's nothing more to do for us here. */
1390 if (! have_referenced_pseudos)
1392 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1393 return false;
1396 pseudos_live = sparseset_alloc (max_regno);
1397 pseudos_live_through_calls = sparseset_alloc (max_regno);
1398 pseudos_live_through_setjumps = sparseset_alloc (max_regno);
1399 start_living = sparseset_alloc (max_regno);
1400 start_dying = sparseset_alloc (max_regno);
1401 dead_set = sparseset_alloc (max_regno);
1402 unused_set = sparseset_alloc (max_regno);
1403 curr_point = 0;
1404 unsigned new_length = get_max_uid () * 2;
1405 point_freq_vec.truncate (0);
1406 point_freq_vec.reserve_exact (new_length);
1407 lra_point_freq = point_freq_vec.address ();
1408 int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
1409 int n = inverted_rev_post_order_compute (cfun, rpo);
1410 lra_assert (n == n_basic_blocks_for_fn (cfun));
1411 bb_live_change_p = false;
1412 for (i = 0; i < n; ++i)
1414 bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
1415 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
1416 == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1417 continue;
1418 if (process_bb_lives (bb, curr_point, dead_insn_p))
1419 bb_live_change_p = true;
1421 free (rpo);
1422 if (bb_live_change_p)
1424 /* We need to clear pseudo live info as some pseudos can
1425 disappear, e.g. pseudos with used equivalences. */
1426 FOR_EACH_BB_FN (bb, cfun)
1428 bitmap_clear_range (df_get_live_in (bb), FIRST_PSEUDO_REGISTER,
1429 max_regno - FIRST_PSEUDO_REGISTER);
1430 bitmap_clear_range (df_get_live_out (bb), FIRST_PSEUDO_REGISTER,
1431 max_regno - FIRST_PSEUDO_REGISTER);
1433 /* As we did not change CFG since LRA start we can use
1434 DF-infrastructure solver to solve live data flow problem. */
1435 for (int i = 0; HARD_REGISTER_NUM_P (i); ++i)
1437 if (TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
1438 bitmap_clear_bit (&all_hard_regs_bitmap, i);
1440 df_simple_dataflow
1441 (DF_BACKWARD, NULL, live_con_fun_0, live_con_fun_n,
1442 live_trans_fun, &all_blocks,
1443 df_get_postorder (DF_BACKWARD), df_get_n_blocks (DF_BACKWARD));
1444 if (lra_dump_file != NULL)
1446 fprintf (lra_dump_file,
1447 "Global pseudo live data have been updated:\n");
1448 basic_block bb;
1449 FOR_EACH_BB_FN (bb, cfun)
1451 bb_data_t bb_info = get_bb_data (bb);
1452 bitmap bb_livein = df_get_live_in (bb);
1453 bitmap bb_liveout = df_get_live_out (bb);
1455 fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
1456 lra_dump_bitmap_with_title (" gen:",
1457 &bb_info->gen_pseudos, bb->index);
1458 lra_dump_bitmap_with_title (" killed:",
1459 &bb_info->killed_pseudos, bb->index);
1460 lra_dump_bitmap_with_title (" livein:", bb_livein, bb->index);
1461 lra_dump_bitmap_with_title (" liveout:", bb_liveout, bb->index);
1465 lra_live_max_point = curr_point;
1466 if (lra_dump_file != NULL)
1467 print_live_ranges (lra_dump_file);
1468 /* Clean up. */
1469 sparseset_free (unused_set);
1470 sparseset_free (dead_set);
1471 sparseset_free (start_dying);
1472 sparseset_free (start_living);
1473 sparseset_free (pseudos_live_through_calls);
1474 sparseset_free (pseudos_live_through_setjumps);
1475 sparseset_free (pseudos_live);
1476 compress_live_ranges ();
1477 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1478 return bb_live_change_p;
1481 /* The main entry function creates live-ranges and other live info
1482 necessary for the assignment sub-pass. It uses
1483 lra_creates_live_ranges_1 -- so read comments for the
1484 function. */
1485 void
1486 lra_create_live_ranges (bool all_p, bool dead_insn_p)
1488 if (! lra_create_live_ranges_1 (all_p, dead_insn_p))
1489 return;
1490 if (lra_dump_file != NULL)
1491 fprintf (lra_dump_file, "Live info was changed -- recalculate it\n");
1492 /* Live info was changed on a bb border. It means that some info,
1493 e.g. about conflict regs, calls crossed, and live ranges may be
1494 wrong. We need this info for allocation. So recalculate it
1495 again but without removing dead insns which can change live info
1496 again. Repetitive live range calculations are expensive therefore
1497 we stop here as we already have correct info although some
1498 improvement in rare cases could be possible on this sub-pass if
1499 we do dead insn elimination again (still the improvement may
1500 happen later). */
1501 lra_clear_live_ranges ();
1502 bool res = lra_create_live_ranges_1 (all_p, false);
1503 lra_assert (! res);
1506 /* Finish all live ranges. */
1507 void
1508 lra_clear_live_ranges (void)
1510 int i;
1512 for (i = 0; i < max_reg_num (); i++)
1513 free_live_range_list (lra_reg_info[i].live_ranges);
1514 point_freq_vec.release ();
1517 /* Initialize live ranges data once per function. */
1518 void
1519 lra_live_ranges_init (void)
1521 bitmap_initialize (&temp_bitmap, &reg_obstack);
1522 initiate_live_solver ();
1525 /* Finish live ranges data once per function. */
1526 void
1527 lra_live_ranges_finish (void)
1529 finish_live_solver ();
1530 bitmap_clear (&temp_bitmap);
1531 lra_live_range_pool.release ();