[ARM] Fix ICE in Armv8-M Security Extensions code
[official-gcc.git] / gcc / lra-lives.c
blobdf7e2537dd09a4abd5ce517f4bb556cc32000fa0
1 /* Build live ranges for pseudos.
2 Copyright (C) 2010-2017 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"
47 /* Program points are enumerated by numbers from range
48 0..LRA_LIVE_MAX_POINT-1. There are approximately two times more
49 program points than insns. Program points are places in the
50 program where liveness info can be changed. In most general case
51 (there are more complicated cases too) some program points
52 correspond to places where input operand dies and other ones
53 correspond to places where output operands are born. */
54 int lra_live_max_point;
56 /* Accumulated execution frequency of all references for each hard
57 register. */
58 int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER];
60 /* A global flag whose true value says to build live ranges for all
61 pseudos, otherwise the live ranges only for pseudos got memory is
62 build. True value means also building copies and setting up hard
63 register preferences. The complete info is necessary only for the
64 assignment pass. The complete info is not needed for the
65 coalescing and spill passes. */
66 static bool complete_info_p;
68 /* Pseudos live at current point in the RTL scan. */
69 static sparseset pseudos_live;
71 /* Pseudos probably living through calls and setjumps. As setjump is
72 a call too, if a bit in PSEUDOS_LIVE_THROUGH_SETJUMPS is set up
73 then the corresponding bit in PSEUDOS_LIVE_THROUGH_CALLS is set up
74 too. These data are necessary for cases when only one subreg of a
75 multi-reg pseudo is set up after a call. So we decide it is
76 probably live when traversing bb backward. We are sure about
77 living when we see its usage or definition of the pseudo. */
78 static sparseset pseudos_live_through_calls;
79 static sparseset pseudos_live_through_setjumps;
81 /* Set of hard regs (except eliminable ones) currently live. */
82 static HARD_REG_SET hard_regs_live;
84 /* Set of pseudos and hard registers start living/dying in the current
85 insn. These sets are used to update REG_DEAD and REG_UNUSED notes
86 in the insn. */
87 static sparseset start_living, start_dying;
89 /* Set of pseudos and hard regs dead and unused in the current
90 insn. */
91 static sparseset unused_set, dead_set;
93 /* Bitmap used for holding intermediate bitmap operation results. */
94 static bitmap_head temp_bitmap;
96 /* Pool for pseudo live ranges. */
97 static object_allocator<lra_live_range> lra_live_range_pool ("live ranges");
99 /* Free live range list LR. */
100 static void
101 free_live_range_list (lra_live_range_t lr)
103 lra_live_range_t next;
105 while (lr != NULL)
107 next = lr->next;
108 lra_live_range_pool.remove (lr);
109 lr = next;
113 /* Create and return pseudo live range with given attributes. */
114 static lra_live_range_t
115 create_live_range (int regno, int start, int finish, lra_live_range_t next)
117 lra_live_range_t p = lra_live_range_pool.allocate ();
118 p->regno = regno;
119 p->start = start;
120 p->finish = finish;
121 p->next = next;
122 return p;
125 /* Copy live range R and return the result. */
126 static lra_live_range_t
127 copy_live_range (lra_live_range_t r)
129 return new (lra_live_range_pool) lra_live_range (*r);
132 /* Copy live range list given by its head R and return the result. */
133 lra_live_range_t
134 lra_copy_live_range_list (lra_live_range_t r)
136 lra_live_range_t p, first, *chain;
138 first = NULL;
139 for (chain = &first; r != NULL; r = r->next)
141 p = copy_live_range (r);
142 *chain = p;
143 chain = &p->next;
145 return first;
148 /* Merge *non-intersected* ranges R1 and R2 and returns the result.
149 The function maintains the order of ranges and tries to minimize
150 size of the result range list. Ranges R1 and R2 may not be used
151 after the call. */
152 lra_live_range_t
153 lra_merge_live_ranges (lra_live_range_t r1, lra_live_range_t r2)
155 lra_live_range_t first, last;
157 if (r1 == NULL)
158 return r2;
159 if (r2 == NULL)
160 return r1;
161 for (first = last = NULL; r1 != NULL && r2 != NULL;)
163 if (r1->start < r2->start)
164 std::swap (r1, r2);
166 if (r1->start == r2->finish + 1)
168 /* Joint ranges: merge r1 and r2 into r1. */
169 r1->start = r2->start;
170 lra_live_range_t temp = r2;
171 r2 = r2->next;
172 lra_live_range_pool.remove (temp);
174 else
176 gcc_assert (r2->finish + 1 < r1->start);
177 /* Add r1 to the result. */
178 if (first == NULL)
179 first = last = r1;
180 else
182 last->next = r1;
183 last = r1;
185 r1 = r1->next;
188 if (r1 != NULL)
190 if (first == NULL)
191 first = r1;
192 else
193 last->next = r1;
195 else
197 lra_assert (r2 != NULL);
198 if (first == NULL)
199 first = r2;
200 else
201 last->next = r2;
203 return first;
206 /* Return TRUE if live ranges R1 and R2 intersect. */
207 bool
208 lra_intersected_live_ranges_p (lra_live_range_t r1, lra_live_range_t r2)
210 /* Remember the live ranges are always kept ordered. */
211 while (r1 != NULL && r2 != NULL)
213 if (r1->start > r2->finish)
214 r1 = r1->next;
215 else if (r2->start > r1->finish)
216 r2 = r2->next;
217 else
218 return true;
220 return false;
223 /* The corresponding bitmaps of BB currently being processed. */
224 static bitmap bb_killed_pseudos, bb_gen_pseudos;
226 /* The function processing birth of hard register REGNO. It updates
227 living hard regs, START_LIVING, and conflict hard regs for living
228 pseudos. Conflict hard regs for the pic pseudo is not updated if
229 REGNO is REAL_PIC_OFFSET_TABLE_REGNUM and CHECK_PIC_PSEUDO_P is
230 true. */
231 static void
232 make_hard_regno_born (int regno, bool check_pic_pseudo_p ATTRIBUTE_UNUSED)
234 unsigned int i;
236 lra_assert (regno < FIRST_PSEUDO_REGISTER);
237 if (TEST_HARD_REG_BIT (hard_regs_live, regno))
238 return;
239 SET_HARD_REG_BIT (hard_regs_live, regno);
240 sparseset_set_bit (start_living, regno);
241 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
242 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
243 if (! check_pic_pseudo_p
244 || regno != REAL_PIC_OFFSET_TABLE_REGNUM
245 || pic_offset_table_rtx == NULL
246 || i != REGNO (pic_offset_table_rtx))
247 #endif
248 SET_HARD_REG_BIT (lra_reg_info[i].conflict_hard_regs, regno);
249 if (fixed_regs[regno])
250 bitmap_set_bit (bb_gen_pseudos, regno);
253 /* Process the death of hard register REGNO. This updates
254 hard_regs_live and START_DYING. */
255 static void
256 make_hard_regno_dead (int regno)
258 lra_assert (regno < FIRST_PSEUDO_REGISTER);
259 if (! TEST_HARD_REG_BIT (hard_regs_live, regno))
260 return;
261 sparseset_set_bit (start_dying, regno);
262 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
263 if (fixed_regs[regno])
265 bitmap_clear_bit (bb_gen_pseudos, regno);
266 bitmap_set_bit (bb_killed_pseudos, regno);
270 /* Mark pseudo REGNO as living at program point POINT, update conflicting
271 hard registers of the pseudo and START_LIVING, and start a new live
272 range for the pseudo corresponding to REGNO if it is necessary. */
273 static void
274 mark_pseudo_live (int regno, int point)
276 lra_live_range_t p;
278 lra_assert (regno >= FIRST_PSEUDO_REGISTER);
279 lra_assert (! sparseset_bit_p (pseudos_live, regno));
280 sparseset_set_bit (pseudos_live, regno);
281 IOR_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs, hard_regs_live);
283 if ((complete_info_p || lra_get_regno_hard_regno (regno) < 0)
284 && ((p = lra_reg_info[regno].live_ranges) == NULL
285 || (p->finish != point && p->finish + 1 != point)))
286 lra_reg_info[regno].live_ranges
287 = create_live_range (regno, point, -1, p);
288 sparseset_set_bit (start_living, regno);
291 /* Mark pseudo REGNO as not living at program point POINT and update
292 START_DYING.
293 This finishes the current live range for the pseudo corresponding
294 to REGNO. */
295 static void
296 mark_pseudo_dead (int regno, int point)
298 lra_live_range_t p;
300 lra_assert (regno >= FIRST_PSEUDO_REGISTER);
301 lra_assert (sparseset_bit_p (pseudos_live, regno));
302 sparseset_clear_bit (pseudos_live, regno);
303 sparseset_set_bit (start_dying, regno);
304 if (complete_info_p || lra_get_regno_hard_regno (regno) < 0)
306 p = lra_reg_info[regno].live_ranges;
307 lra_assert (p != NULL);
308 p->finish = point;
312 /* Mark register REGNO (pseudo or hard register) in MODE as live at
313 program point POINT. Update BB_GEN_PSEUDOS.
314 Return TRUE if the liveness tracking sets were modified, or FALSE
315 if nothing changed. */
316 static bool
317 mark_regno_live (int regno, machine_mode mode, int point)
319 int last;
320 bool changed = false;
322 if (regno < FIRST_PSEUDO_REGISTER)
324 for (last = end_hard_regno (mode, regno); regno < last; regno++)
325 make_hard_regno_born (regno, false);
327 else
329 if (! sparseset_bit_p (pseudos_live, regno))
331 mark_pseudo_live (regno, point);
332 changed = true;
334 bitmap_set_bit (bb_gen_pseudos, regno);
336 return changed;
340 /* Mark register REGNO in MODE as dead at program point POINT. Update
341 BB_GEN_PSEUDOS and BB_KILLED_PSEUDOS. Return TRUE if the liveness
342 tracking sets were modified, or FALSE if nothing changed. */
343 static bool
344 mark_regno_dead (int regno, machine_mode mode, int point)
346 int last;
347 bool changed = false;
349 if (regno < FIRST_PSEUDO_REGISTER)
351 for (last = end_hard_regno (mode, regno); regno < last; regno++)
352 make_hard_regno_dead (regno);
354 else
356 if (sparseset_bit_p (pseudos_live, regno))
358 mark_pseudo_dead (regno, point);
359 changed = true;
361 bitmap_clear_bit (bb_gen_pseudos, regno);
362 bitmap_set_bit (bb_killed_pseudos, regno);
364 return changed;
369 /* This page contains code for making global live analysis of pseudos.
370 The code works only when pseudo live info is changed on a BB
371 border. That might be a consequence of some global transformations
372 in LRA, e.g. PIC pseudo reuse or rematerialization. */
374 /* Structure describing local BB data used for pseudo
375 live-analysis. */
376 struct bb_data_pseudos
378 /* Basic block about which the below data are. */
379 basic_block bb;
380 bitmap_head killed_pseudos; /* pseudos killed in the BB. */
381 bitmap_head gen_pseudos; /* pseudos generated in the BB. */
384 /* Array for all BB data. Indexed by the corresponding BB index. */
385 typedef struct bb_data_pseudos *bb_data_t;
387 /* All basic block data are referred through the following array. */
388 static bb_data_t bb_data;
390 /* Two small functions for access to the bb data. */
391 static inline bb_data_t
392 get_bb_data (basic_block bb)
394 return &bb_data[(bb)->index];
397 static inline bb_data_t
398 get_bb_data_by_index (int index)
400 return &bb_data[index];
403 /* Bitmap with all hard regs. */
404 static bitmap_head all_hard_regs_bitmap;
406 /* The transfer function used by the DF equation solver to propagate
407 live info through block with BB_INDEX according to the following
408 equation:
410 bb.livein = (bb.liveout - bb.kill) OR bb.gen
412 static bool
413 live_trans_fun (int bb_index)
415 basic_block bb = get_bb_data_by_index (bb_index)->bb;
416 bitmap bb_liveout = df_get_live_out (bb);
417 bitmap bb_livein = df_get_live_in (bb);
418 bb_data_t bb_info = get_bb_data (bb);
420 bitmap_and_compl (&temp_bitmap, bb_liveout, &all_hard_regs_bitmap);
421 return bitmap_ior_and_compl (bb_livein, &bb_info->gen_pseudos,
422 &temp_bitmap, &bb_info->killed_pseudos);
425 /* The confluence function used by the DF equation solver to set up
426 live info for a block BB without predecessor. */
427 static void
428 live_con_fun_0 (basic_block bb)
430 bitmap_and_into (df_get_live_out (bb), &all_hard_regs_bitmap);
433 /* The confluence function used by the DF equation solver to propagate
434 live info from successor to predecessor on edge E according to the
435 following equation:
437 bb.liveout = 0 for entry block | OR (livein of successors)
439 static bool
440 live_con_fun_n (edge e)
442 basic_block bb = e->src;
443 basic_block dest = e->dest;
444 bitmap bb_liveout = df_get_live_out (bb);
445 bitmap dest_livein = df_get_live_in (dest);
447 return bitmap_ior_and_compl_into (bb_liveout,
448 dest_livein, &all_hard_regs_bitmap);
451 /* Indexes of all function blocks. */
452 static bitmap_head all_blocks;
454 /* Allocate and initialize data needed for global pseudo live
455 analysis. */
456 static void
457 initiate_live_solver (void)
459 bitmap_initialize (&all_hard_regs_bitmap, &reg_obstack);
460 bitmap_set_range (&all_hard_regs_bitmap, 0, FIRST_PSEUDO_REGISTER);
461 bb_data = XNEWVEC (struct bb_data_pseudos, last_basic_block_for_fn (cfun));
462 bitmap_initialize (&all_blocks, &reg_obstack);
464 basic_block bb;
465 FOR_ALL_BB_FN (bb, cfun)
467 bb_data_t bb_info = get_bb_data (bb);
468 bb_info->bb = bb;
469 bitmap_initialize (&bb_info->killed_pseudos, &reg_obstack);
470 bitmap_initialize (&bb_info->gen_pseudos, &reg_obstack);
471 bitmap_set_bit (&all_blocks, bb->index);
475 /* Free all data needed for global pseudo live analysis. */
476 static void
477 finish_live_solver (void)
479 basic_block bb;
481 bitmap_clear (&all_blocks);
482 FOR_ALL_BB_FN (bb, cfun)
484 bb_data_t bb_info = get_bb_data (bb);
485 bitmap_clear (&bb_info->killed_pseudos);
486 bitmap_clear (&bb_info->gen_pseudos);
488 free (bb_data);
489 bitmap_clear (&all_hard_regs_bitmap);
494 /* Insn currently scanned. */
495 static rtx_insn *curr_insn;
496 /* The insn data. */
497 static lra_insn_recog_data_t curr_id;
498 /* The insn static data. */
499 static struct lra_static_insn_data *curr_static_id;
501 /* Vec containing execution frequencies of program points. */
502 static vec<int> point_freq_vec;
504 /* The start of the above vector elements. */
505 int *lra_point_freq;
507 /* Increment the current program point POINT to the next point which has
508 execution frequency FREQ. */
509 static void
510 next_program_point (int &point, int freq)
512 point_freq_vec.safe_push (freq);
513 lra_point_freq = point_freq_vec.address ();
514 point++;
517 /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
518 void
519 lra_setup_reload_pseudo_preferenced_hard_reg (int regno,
520 int hard_regno, int profit)
522 lra_assert (regno >= lra_constraint_new_regno_start);
523 if (lra_reg_info[regno].preferred_hard_regno1 == hard_regno)
524 lra_reg_info[regno].preferred_hard_regno_profit1 += profit;
525 else if (lra_reg_info[regno].preferred_hard_regno2 == hard_regno)
526 lra_reg_info[regno].preferred_hard_regno_profit2 += profit;
527 else if (lra_reg_info[regno].preferred_hard_regno1 < 0)
529 lra_reg_info[regno].preferred_hard_regno1 = hard_regno;
530 lra_reg_info[regno].preferred_hard_regno_profit1 = profit;
532 else if (lra_reg_info[regno].preferred_hard_regno2 < 0
533 || profit > lra_reg_info[regno].preferred_hard_regno_profit2)
535 lra_reg_info[regno].preferred_hard_regno2 = hard_regno;
536 lra_reg_info[regno].preferred_hard_regno_profit2 = profit;
538 else
539 return;
540 /* Keep the 1st hard regno as more profitable. */
541 if (lra_reg_info[regno].preferred_hard_regno1 >= 0
542 && lra_reg_info[regno].preferred_hard_regno2 >= 0
543 && (lra_reg_info[regno].preferred_hard_regno_profit2
544 > lra_reg_info[regno].preferred_hard_regno_profit1))
546 std::swap (lra_reg_info[regno].preferred_hard_regno1,
547 lra_reg_info[regno].preferred_hard_regno2);
548 std::swap (lra_reg_info[regno].preferred_hard_regno_profit1,
549 lra_reg_info[regno].preferred_hard_regno_profit2);
551 if (lra_dump_file != NULL)
553 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
554 fprintf (lra_dump_file,
555 " Hard reg %d is preferable by r%d with profit %d\n",
556 hard_regno, regno,
557 lra_reg_info[regno].preferred_hard_regno_profit1);
558 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
559 fprintf (lra_dump_file,
560 " Hard reg %d is preferable by r%d with profit %d\n",
561 hard_regno, regno,
562 lra_reg_info[regno].preferred_hard_regno_profit2);
566 /* Check that REGNO living through calls and setjumps, set up conflict
567 regs using LAST_CALL_USED_REG_SET, and clear corresponding bits in
568 PSEUDOS_LIVE_THROUGH_CALLS and PSEUDOS_LIVE_THROUGH_SETJUMPS. */
569 static inline void
570 check_pseudos_live_through_calls (int regno,
571 HARD_REG_SET last_call_used_reg_set)
573 int hr;
575 if (! sparseset_bit_p (pseudos_live_through_calls, regno))
576 return;
577 sparseset_clear_bit (pseudos_live_through_calls, regno);
578 IOR_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs,
579 last_call_used_reg_set);
581 for (hr = 0; hr < FIRST_PSEUDO_REGISTER; hr++)
582 if (targetm.hard_regno_call_part_clobbered (hr,
583 PSEUDO_REGNO_MODE (regno)))
584 SET_HARD_REG_BIT (lra_reg_info[regno].conflict_hard_regs, hr);
585 lra_reg_info[regno].call_p = true;
586 if (! sparseset_bit_p (pseudos_live_through_setjumps, regno))
587 return;
588 sparseset_clear_bit (pseudos_live_through_setjumps, regno);
589 /* Don't allocate pseudos that cross setjmps or any call, if this
590 function receives a nonlocal goto. */
591 SET_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs);
594 /* Return true if insn REG is an early clobber operand in alternative
595 NALT. Negative NALT means that we don't know the current insn
596 alternative. So assume the worst. */
597 static inline bool
598 reg_early_clobber_p (const struct lra_insn_reg *reg, int n_alt)
600 return (reg->early_clobber
601 && (n_alt < 0 || TEST_BIT (reg->early_clobber_alts, n_alt)));
604 /* Process insns of the basic block BB to update pseudo live ranges,
605 pseudo hard register conflicts, and insn notes. We do it on
606 backward scan of BB insns. CURR_POINT is the program point where
607 BB ends. The function updates this counter and returns in
608 CURR_POINT the program point where BB starts. The function also
609 does local live info updates and can delete the dead insns if
610 DEAD_INSN_P. It returns true if pseudo live info was
611 changed at the BB start. */
612 static bool
613 process_bb_lives (basic_block bb, int &curr_point, bool dead_insn_p)
615 int i, regno, freq;
616 unsigned int j;
617 bitmap_iterator bi;
618 bitmap reg_live_out;
619 unsigned int px;
620 rtx_insn *next;
621 rtx link, *link_loc;
622 bool need_curr_point_incr;
623 HARD_REG_SET last_call_used_reg_set;
625 reg_live_out = df_get_live_out (bb);
626 sparseset_clear (pseudos_live);
627 sparseset_clear (pseudos_live_through_calls);
628 sparseset_clear (pseudos_live_through_setjumps);
629 CLEAR_HARD_REG_SET (last_call_used_reg_set);
630 REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
631 AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
632 EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
633 mark_pseudo_live (j, curr_point);
635 bb_gen_pseudos = &get_bb_data (bb)->gen_pseudos;
636 bb_killed_pseudos = &get_bb_data (bb)->killed_pseudos;
637 bitmap_clear (bb_gen_pseudos);
638 bitmap_clear (bb_killed_pseudos);
639 freq = REG_FREQ_FROM_BB (bb);
641 if (lra_dump_file != NULL)
642 fprintf (lra_dump_file, " BB %d\n", bb->index);
644 /* Scan the code of this basic block, noting which pseudos and hard
645 regs are born or die.
647 Note that this loop treats uninitialized values as live until the
648 beginning of the block. For example, if an instruction uses
649 (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
650 FOO will remain live until the beginning of the block. Likewise
651 if FOO is not set at all. This is unnecessarily pessimistic, but
652 it probably doesn't matter much in practice. */
653 FOR_BB_INSNS_REVERSE_SAFE (bb, curr_insn, next)
655 bool call_p;
656 int n_alt, dst_regno, src_regno;
657 rtx set;
658 struct lra_insn_reg *reg;
660 if (!NONDEBUG_INSN_P (curr_insn))
661 continue;
663 curr_id = lra_get_insn_recog_data (curr_insn);
664 curr_static_id = curr_id->insn_static_data;
665 n_alt = curr_id->used_insn_alternative;
666 if (lra_dump_file != NULL)
667 fprintf (lra_dump_file, " Insn %u: point = %d, n_alt = %d\n",
668 INSN_UID (curr_insn), curr_point, n_alt);
670 set = single_set (curr_insn);
672 if (dead_insn_p && set != NULL_RTX
673 && REG_P (SET_DEST (set)) && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
674 && find_reg_note (curr_insn, REG_EH_REGION, NULL_RTX) == NULL_RTX
675 && ! may_trap_p (PATTERN (curr_insn))
676 /* Don't do premature remove of pic offset pseudo as we can
677 start to use it after some reload generation. */
678 && (pic_offset_table_rtx == NULL_RTX
679 || pic_offset_table_rtx != SET_DEST (set)))
681 bool remove_p = true;
683 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
684 if (reg->type != OP_IN && sparseset_bit_p (pseudos_live, reg->regno))
686 remove_p = false;
687 break;
689 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
690 if (reg->type != OP_IN)
692 remove_p = false;
693 break;
695 if (remove_p && ! volatile_refs_p (PATTERN (curr_insn)))
697 dst_regno = REGNO (SET_DEST (set));
698 if (lra_dump_file != NULL)
699 fprintf (lra_dump_file, " Deleting dead insn %u\n",
700 INSN_UID (curr_insn));
701 lra_set_insn_deleted (curr_insn);
702 if (lra_reg_info[dst_regno].nrefs == 0)
704 /* There might be some debug insns with the pseudo. */
705 unsigned int uid;
706 rtx_insn *insn;
708 bitmap_copy (&temp_bitmap, &lra_reg_info[dst_regno].insn_bitmap);
709 EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap, 0, uid, bi)
711 insn = lra_insn_recog_data[uid]->insn;
712 lra_substitute_pseudo_within_insn (insn, dst_regno,
713 SET_SRC (set), true);
714 lra_update_insn_regno_info (insn);
717 continue;
721 /* Update max ref width and hard reg usage. */
722 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
724 int i, regno = reg->regno;
726 if (partial_subreg_p (lra_reg_info[regno].biggest_mode,
727 reg->biggest_mode))
728 lra_reg_info[regno].biggest_mode = reg->biggest_mode;
729 if (regno < FIRST_PSEUDO_REGISTER)
731 lra_hard_reg_usage[regno] += freq;
732 /* A hard register explicitly can be used in small mode,
733 but implicitly it can be used in natural mode as a
734 part of multi-register group. Process this case
735 here. */
736 for (i = 1; i < hard_regno_nregs (regno, reg->biggest_mode); i++)
737 if (partial_subreg_p (lra_reg_info[regno + i].biggest_mode,
738 GET_MODE (regno_reg_rtx[regno + i])))
739 lra_reg_info[regno + i].biggest_mode
740 = GET_MODE (regno_reg_rtx[regno + i]);
744 call_p = CALL_P (curr_insn);
745 src_regno = (set != NULL_RTX && REG_P (SET_SRC (set))
746 ? REGNO (SET_SRC (set)) : -1);
747 dst_regno = (set != NULL_RTX && REG_P (SET_DEST (set))
748 ? REGNO (SET_DEST (set)) : -1);
749 if (complete_info_p
750 && src_regno >= 0 && dst_regno >= 0
751 /* Check that source regno does not conflict with
752 destination regno to exclude most impossible
753 preferences. */
754 && (((src_regno >= FIRST_PSEUDO_REGISTER
755 && (! sparseset_bit_p (pseudos_live, src_regno)
756 || (dst_regno >= FIRST_PSEUDO_REGISTER
757 && lra_reg_val_equal_p (src_regno,
758 lra_reg_info[dst_regno].val,
759 lra_reg_info[dst_regno].offset))))
760 || (src_regno < FIRST_PSEUDO_REGISTER
761 && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno)))
762 /* It might be 'inheritance pseudo <- reload pseudo'. */
763 || (src_regno >= lra_constraint_new_regno_start
764 && dst_regno >= lra_constraint_new_regno_start
765 /* Remember to skip special cases where src/dest regnos are
766 the same, e.g. insn SET pattern has matching constraints
767 like =r,0. */
768 && src_regno != dst_regno)))
770 int hard_regno = -1, regno = -1;
772 if (dst_regno >= lra_constraint_new_regno_start
773 && src_regno >= lra_constraint_new_regno_start)
775 /* It might be still an original (non-reload) insn with
776 one unused output and a constraint requiring to use
777 the same reg for input/output operands. In this case
778 dst_regno and src_regno have the same value, we don't
779 need a misleading copy for this case. */
780 if (dst_regno != src_regno)
781 lra_create_copy (dst_regno, src_regno, freq);
783 else if (dst_regno >= lra_constraint_new_regno_start)
785 if ((hard_regno = src_regno) >= FIRST_PSEUDO_REGISTER)
786 hard_regno = reg_renumber[src_regno];
787 regno = dst_regno;
789 else if (src_regno >= lra_constraint_new_regno_start)
791 if ((hard_regno = dst_regno) >= FIRST_PSEUDO_REGISTER)
792 hard_regno = reg_renumber[dst_regno];
793 regno = src_regno;
795 if (regno >= 0 && hard_regno >= 0)
796 lra_setup_reload_pseudo_preferenced_hard_reg
797 (regno, hard_regno, freq);
800 sparseset_clear (start_living);
802 /* Try to avoid unnecessary program point increments, this saves
803 a lot of time in remove_some_program_points_and_update_live_ranges.
804 We only need an increment if something becomes live or dies at this
805 program point. */
806 need_curr_point_incr = false;
808 /* Mark each defined value as live. We need to do this for
809 unused values because they still conflict with quantities
810 that are live at the time of the definition. */
811 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
812 if (reg->type != OP_IN)
814 need_curr_point_incr
815 |= mark_regno_live (reg->regno, reg->biggest_mode,
816 curr_point);
817 check_pseudos_live_through_calls (reg->regno,
818 last_call_used_reg_set);
821 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
822 if (reg->type != OP_IN)
823 make_hard_regno_born (reg->regno, false);
825 if (curr_id->arg_hard_regs != NULL)
826 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
827 if (regno >= FIRST_PSEUDO_REGISTER)
828 /* It is a clobber. */
829 make_hard_regno_born (regno - FIRST_PSEUDO_REGISTER, false);
831 sparseset_copy (unused_set, start_living);
833 sparseset_clear (start_dying);
835 /* See which defined values die here. */
836 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
837 if (reg->type == OP_OUT
838 && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
839 need_curr_point_incr
840 |= mark_regno_dead (reg->regno, reg->biggest_mode,
841 curr_point);
843 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
844 if (reg->type == OP_OUT
845 && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
846 make_hard_regno_dead (reg->regno);
848 if (curr_id->arg_hard_regs != NULL)
849 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
850 if (regno >= FIRST_PSEUDO_REGISTER)
851 /* It is a clobber. */
852 make_hard_regno_dead (regno - FIRST_PSEUDO_REGISTER);
854 if (call_p)
856 if (! flag_ipa_ra)
857 COPY_HARD_REG_SET(last_call_used_reg_set, call_used_reg_set);
858 else
860 HARD_REG_SET this_call_used_reg_set;
861 get_call_reg_set_usage (curr_insn, &this_call_used_reg_set,
862 call_used_reg_set);
864 bool flush = (! hard_reg_set_empty_p (last_call_used_reg_set)
865 && ! hard_reg_set_equal_p (last_call_used_reg_set,
866 this_call_used_reg_set));
868 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
870 IOR_HARD_REG_SET (lra_reg_info[j].actual_call_used_reg_set,
871 this_call_used_reg_set);
872 if (flush)
873 check_pseudos_live_through_calls
874 (j, last_call_used_reg_set);
876 COPY_HARD_REG_SET(last_call_used_reg_set, this_call_used_reg_set);
879 sparseset_ior (pseudos_live_through_calls,
880 pseudos_live_through_calls, pseudos_live);
881 if (cfun->has_nonlocal_label
882 || find_reg_note (curr_insn, REG_SETJMP,
883 NULL_RTX) != NULL_RTX)
884 sparseset_ior (pseudos_live_through_setjumps,
885 pseudos_live_through_setjumps, pseudos_live);
888 /* Increment the current program point if we must. */
889 if (need_curr_point_incr)
890 next_program_point (curr_point, freq);
892 sparseset_clear (start_living);
894 need_curr_point_incr = false;
896 /* Mark each used value as live. */
897 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
898 if (reg->type == OP_IN)
900 need_curr_point_incr
901 |= mark_regno_live (reg->regno, reg->biggest_mode,
902 curr_point);
903 check_pseudos_live_through_calls (reg->regno,
904 last_call_used_reg_set);
907 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
908 if (reg->type == OP_IN)
909 make_hard_regno_born (reg->regno, false);
911 if (curr_id->arg_hard_regs != NULL)
912 /* Make argument hard registers live. Don't create conflict
913 of used REAL_PIC_OFFSET_TABLE_REGNUM and the pic pseudo. */
914 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
915 if (regno < FIRST_PSEUDO_REGISTER)
916 make_hard_regno_born (regno, true);
918 sparseset_and_compl (dead_set, start_living, start_dying);
920 /* Mark early clobber outputs dead. */
921 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
922 if (reg->type == OP_OUT
923 && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
924 need_curr_point_incr
925 |= mark_regno_dead (reg->regno, reg->biggest_mode,
926 curr_point);
928 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
929 if (reg->type == OP_OUT
930 && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
931 make_hard_regno_dead (reg->regno);
933 if (need_curr_point_incr)
934 next_program_point (curr_point, freq);
936 /* Update notes. */
937 for (link_loc = &REG_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
939 if (REG_NOTE_KIND (link) != REG_DEAD
940 && REG_NOTE_KIND (link) != REG_UNUSED)
942 else if (REG_P (XEXP (link, 0)))
944 regno = REGNO (XEXP (link, 0));
945 if ((REG_NOTE_KIND (link) == REG_DEAD
946 && ! sparseset_bit_p (dead_set, regno))
947 || (REG_NOTE_KIND (link) == REG_UNUSED
948 && ! sparseset_bit_p (unused_set, regno)))
950 *link_loc = XEXP (link, 1);
951 continue;
953 if (REG_NOTE_KIND (link) == REG_DEAD)
954 sparseset_clear_bit (dead_set, regno);
955 else if (REG_NOTE_KIND (link) == REG_UNUSED)
956 sparseset_clear_bit (unused_set, regno);
958 link_loc = &XEXP (link, 1);
960 EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
961 add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
962 EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
963 add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
966 if (bb_has_eh_pred (bb))
967 for (j = 0; ; ++j)
969 unsigned int regno = EH_RETURN_DATA_REGNO (j);
971 if (regno == INVALID_REGNUM)
972 break;
973 make_hard_regno_born (regno, false);
976 /* Pseudos can't go in stack regs at the start of a basic block that
977 is reached by an abnormal edge. Likewise for call clobbered regs,
978 because caller-save, fixup_abnormal_edges and possibly the table
979 driven EH machinery are not quite ready to handle such pseudos
980 live across such edges. */
981 if (bb_has_abnormal_pred (bb))
983 #ifdef STACK_REGS
984 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
985 lra_reg_info[px].no_stack_p = true;
986 for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
987 make_hard_regno_born (px, false);
988 #endif
989 /* No need to record conflicts for call clobbered regs if we
990 have nonlocal labels around, as we don't ever try to
991 allocate such regs in this case. */
992 if (!cfun->has_nonlocal_label
993 && has_abnormal_call_or_eh_pred_edge_p (bb))
994 for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
995 if (call_used_regs[px]
996 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
997 /* We should create a conflict of PIC pseudo with PIC
998 hard reg as PIC hard reg can have a wrong value after
999 jump described by the abnormal edge. In this case we
1000 can not allocate PIC hard reg to PIC pseudo as PIC
1001 pseudo will also have a wrong value. */
1002 || (px == REAL_PIC_OFFSET_TABLE_REGNUM
1003 && pic_offset_table_rtx != NULL_RTX
1004 && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
1005 #endif
1007 make_hard_regno_born (px, false);
1010 bool live_change_p = false;
1011 /* Check if bb border live info was changed. */
1012 unsigned int live_pseudos_num = 0;
1013 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb),
1014 FIRST_PSEUDO_REGISTER, j, bi)
1016 live_pseudos_num++;
1017 if (! sparseset_bit_p (pseudos_live, j))
1019 live_change_p = true;
1020 if (lra_dump_file != NULL)
1021 fprintf (lra_dump_file,
1022 " r%d is removed as live at bb%d start\n", j, bb->index);
1023 break;
1026 if (! live_change_p
1027 && sparseset_cardinality (pseudos_live) != live_pseudos_num)
1029 live_change_p = true;
1030 if (lra_dump_file != NULL)
1031 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
1032 if (! bitmap_bit_p (df_get_live_in (bb), j))
1033 fprintf (lra_dump_file,
1034 " r%d is added to live at bb%d start\n", j, bb->index);
1036 /* See if we'll need an increment at the end of this basic block.
1037 An increment is needed if the PSEUDOS_LIVE set is not empty,
1038 to make sure the finish points are set up correctly. */
1039 need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0);
1041 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
1042 mark_pseudo_dead (i, curr_point);
1044 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
1046 if (sparseset_cardinality (pseudos_live_through_calls) == 0)
1047 break;
1048 if (sparseset_bit_p (pseudos_live_through_calls, j))
1049 check_pseudos_live_through_calls (j, last_call_used_reg_set);
1052 if (need_curr_point_incr)
1053 next_program_point (curr_point, freq);
1055 return live_change_p;
1058 /* Compress pseudo live ranges by removing program points where
1059 nothing happens. Complexity of many algorithms in LRA is linear
1060 function of program points number. To speed up the code we try to
1061 minimize the number of the program points here. */
1062 static void
1063 remove_some_program_points_and_update_live_ranges (void)
1065 unsigned i;
1066 int n, max_regno;
1067 int *map;
1068 lra_live_range_t r, prev_r, next_r;
1069 sbitmap_iterator sbi;
1070 bool born_p, dead_p, prev_born_p, prev_dead_p;
1072 auto_sbitmap born (lra_live_max_point);
1073 auto_sbitmap dead (lra_live_max_point);
1074 bitmap_clear (born);
1075 bitmap_clear (dead);
1076 max_regno = max_reg_num ();
1077 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1079 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1081 lra_assert (r->start <= r->finish);
1082 bitmap_set_bit (born, r->start);
1083 bitmap_set_bit (dead, r->finish);
1086 auto_sbitmap born_or_dead (lra_live_max_point);
1087 bitmap_ior (born_or_dead, born, dead);
1088 map = XCNEWVEC (int, lra_live_max_point);
1089 n = -1;
1090 prev_born_p = prev_dead_p = false;
1091 EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1093 born_p = bitmap_bit_p (born, i);
1094 dead_p = bitmap_bit_p (dead, i);
1095 if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1096 || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1098 map[i] = n;
1099 lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
1101 else
1103 map[i] = ++n;
1104 lra_point_freq[n] = lra_point_freq[i];
1106 prev_born_p = born_p;
1107 prev_dead_p = dead_p;
1109 n++;
1110 if (lra_dump_file != NULL)
1111 fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1112 lra_live_max_point, n, 100 * n / lra_live_max_point);
1113 if (n < lra_live_max_point)
1115 lra_live_max_point = n;
1116 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1118 for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
1119 r != NULL;
1120 r = next_r)
1122 next_r = r->next;
1123 r->start = map[r->start];
1124 r->finish = map[r->finish];
1125 if (prev_r == NULL || prev_r->start > r->finish + 1)
1127 prev_r = r;
1128 continue;
1130 prev_r->start = r->start;
1131 prev_r->next = next_r;
1132 lra_live_range_pool.remove (r);
1136 free (map);
1139 /* Print live ranges R to file F. */
1140 void
1141 lra_print_live_range_list (FILE *f, lra_live_range_t r)
1143 for (; r != NULL; r = r->next)
1144 fprintf (f, " [%d..%d]", r->start, r->finish);
1145 fprintf (f, "\n");
1148 DEBUG_FUNCTION void
1149 debug (lra_live_range &ref)
1151 lra_print_live_range_list (stderr, &ref);
1154 DEBUG_FUNCTION void
1155 debug (lra_live_range *ptr)
1157 if (ptr)
1158 debug (*ptr);
1159 else
1160 fprintf (stderr, "<nil>\n");
1163 /* Print live ranges R to stderr. */
1164 void
1165 lra_debug_live_range_list (lra_live_range_t r)
1167 lra_print_live_range_list (stderr, r);
1170 /* Print live ranges of pseudo REGNO to file F. */
1171 static void
1172 print_pseudo_live_ranges (FILE *f, int regno)
1174 if (lra_reg_info[regno].live_ranges == NULL)
1175 return;
1176 fprintf (f, " r%d:", regno);
1177 lra_print_live_range_list (f, lra_reg_info[regno].live_ranges);
1180 /* Print live ranges of pseudo REGNO to stderr. */
1181 void
1182 lra_debug_pseudo_live_ranges (int regno)
1184 print_pseudo_live_ranges (stderr, regno);
1187 /* Print live ranges of all pseudos to file F. */
1188 static void
1189 print_live_ranges (FILE *f)
1191 int i, max_regno;
1193 max_regno = max_reg_num ();
1194 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1195 print_pseudo_live_ranges (f, i);
1198 /* Print live ranges of all pseudos to stderr. */
1199 void
1200 lra_debug_live_ranges (void)
1202 print_live_ranges (stderr);
1205 /* Compress pseudo live ranges. */
1206 static void
1207 compress_live_ranges (void)
1209 remove_some_program_points_and_update_live_ranges ();
1210 if (lra_dump_file != NULL)
1212 fprintf (lra_dump_file, "Ranges after the compression:\n");
1213 print_live_ranges (lra_dump_file);
1219 /* The number of the current live range pass. */
1220 int lra_live_range_iter;
1222 /* The function creates live ranges only for memory pseudos (or for
1223 all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos. It
1224 also does dead insn elimination if DEAD_INSN_P and global live
1225 analysis only for pseudos and only if the pseudo live info was
1226 changed on a BB border. Return TRUE if the live info was
1227 changed. */
1228 static bool
1229 lra_create_live_ranges_1 (bool all_p, bool dead_insn_p)
1231 basic_block bb;
1232 int i, hard_regno, max_regno = max_reg_num ();
1233 int curr_point;
1234 bool bb_live_change_p, have_referenced_pseudos = false;
1236 timevar_push (TV_LRA_CREATE_LIVE_RANGES);
1238 complete_info_p = all_p;
1239 if (lra_dump_file != NULL)
1240 fprintf (lra_dump_file,
1241 "\n********** Pseudo live ranges #%d: **********\n\n",
1242 ++lra_live_range_iter);
1243 memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage));
1244 for (i = 0; i < max_regno; i++)
1246 lra_reg_info[i].live_ranges = NULL;
1247 CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1248 lra_reg_info[i].preferred_hard_regno1 = -1;
1249 lra_reg_info[i].preferred_hard_regno2 = -1;
1250 lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1251 lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1252 #ifdef STACK_REGS
1253 lra_reg_info[i].no_stack_p = false;
1254 #endif
1255 /* The biggest mode is already set but its value might be to
1256 conservative because of recent transformation. Here in this
1257 file we recalculate it again as it costs practically
1258 nothing. */
1259 if (i >= FIRST_PSEUDO_REGISTER && regno_reg_rtx[i] != NULL_RTX)
1260 lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
1261 else
1262 lra_reg_info[i].biggest_mode = VOIDmode;
1263 lra_reg_info[i].call_p = false;
1264 if (i >= FIRST_PSEUDO_REGISTER
1265 && lra_reg_info[i].nrefs != 0)
1267 if ((hard_regno = reg_renumber[i]) >= 0)
1268 lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
1269 have_referenced_pseudos = true;
1272 lra_free_copies ();
1274 /* Under some circumstances, we can have functions without pseudo
1275 registers. For such functions, lra_live_max_point will be 0,
1276 see e.g. PR55604, and there's nothing more to do for us here. */
1277 if (! have_referenced_pseudos)
1279 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1280 return false;
1283 pseudos_live = sparseset_alloc (max_regno);
1284 pseudos_live_through_calls = sparseset_alloc (max_regno);
1285 pseudos_live_through_setjumps = sparseset_alloc (max_regno);
1286 start_living = sparseset_alloc (max_regno);
1287 start_dying = sparseset_alloc (max_regno);
1288 dead_set = sparseset_alloc (max_regno);
1289 unused_set = sparseset_alloc (max_regno);
1290 curr_point = 0;
1291 unsigned new_length = get_max_uid () * 2;
1292 point_freq_vec.truncate (0);
1293 point_freq_vec.reserve_exact (new_length);
1294 lra_point_freq = point_freq_vec.address ();
1295 auto_vec<int, 20> post_order_rev_cfg;
1296 inverted_post_order_compute (&post_order_rev_cfg);
1297 lra_assert (post_order_rev_cfg.length () == (unsigned) n_basic_blocks_for_fn (cfun));
1298 bb_live_change_p = false;
1299 for (i = post_order_rev_cfg.length () - 1; i >= 0; --i)
1301 bb = BASIC_BLOCK_FOR_FN (cfun, post_order_rev_cfg[i]);
1302 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
1303 == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1304 continue;
1305 if (process_bb_lives (bb, curr_point, dead_insn_p))
1306 bb_live_change_p = true;
1308 if (bb_live_change_p)
1310 /* We need to clear pseudo live info as some pseudos can
1311 disappear, e.g. pseudos with used equivalences. */
1312 FOR_EACH_BB_FN (bb, cfun)
1314 bitmap_clear_range (df_get_live_in (bb), FIRST_PSEUDO_REGISTER,
1315 max_regno - FIRST_PSEUDO_REGISTER);
1316 bitmap_clear_range (df_get_live_out (bb), FIRST_PSEUDO_REGISTER,
1317 max_regno - FIRST_PSEUDO_REGISTER);
1319 /* As we did not change CFG since LRA start we can use
1320 DF-infrastructure solver to solve live data flow problem. */
1321 df_simple_dataflow
1322 (DF_BACKWARD, NULL, live_con_fun_0, live_con_fun_n,
1323 live_trans_fun, &all_blocks,
1324 df_get_postorder (DF_BACKWARD), df_get_n_blocks (DF_BACKWARD));
1325 if (lra_dump_file != NULL)
1327 fprintf (lra_dump_file,
1328 "Global pseudo live data have been updated:\n");
1329 basic_block bb;
1330 FOR_EACH_BB_FN (bb, cfun)
1332 bb_data_t bb_info = get_bb_data (bb);
1333 bitmap bb_livein = df_get_live_in (bb);
1334 bitmap bb_liveout = df_get_live_out (bb);
1336 fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
1337 lra_dump_bitmap_with_title (" gen:",
1338 &bb_info->gen_pseudos, bb->index);
1339 lra_dump_bitmap_with_title (" killed:",
1340 &bb_info->killed_pseudos, bb->index);
1341 lra_dump_bitmap_with_title (" livein:", bb_livein, bb->index);
1342 lra_dump_bitmap_with_title (" liveout:", bb_liveout, bb->index);
1346 lra_live_max_point = curr_point;
1347 if (lra_dump_file != NULL)
1348 print_live_ranges (lra_dump_file);
1349 /* Clean up. */
1350 sparseset_free (unused_set);
1351 sparseset_free (dead_set);
1352 sparseset_free (start_dying);
1353 sparseset_free (start_living);
1354 sparseset_free (pseudos_live_through_calls);
1355 sparseset_free (pseudos_live_through_setjumps);
1356 sparseset_free (pseudos_live);
1357 compress_live_ranges ();
1358 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1359 return bb_live_change_p;
1362 /* The main entry function creates live-ranges and other live info
1363 necessary for the assignment sub-pass. It uses
1364 lra_creates_live_ranges_1 -- so read comments for the
1365 function. */
1366 void
1367 lra_create_live_ranges (bool all_p, bool dead_insn_p)
1369 if (! lra_create_live_ranges_1 (all_p, dead_insn_p))
1370 return;
1371 if (lra_dump_file != NULL)
1372 fprintf (lra_dump_file, "Live info was changed -- recalculate it\n");
1373 /* Live info was changed on a bb border. It means that some info,
1374 e.g. about conflict regs, calls crossed, and live ranges may be
1375 wrong. We need this info for allocation. So recalculate it
1376 again but without removing dead insns which can change live info
1377 again. Repetitive live range calculations are expensive therefore
1378 we stop here as we already have correct info although some
1379 improvement in rare cases could be possible on this sub-pass if
1380 we do dead insn elimination again (still the improvement may
1381 happen later). */
1382 lra_clear_live_ranges ();
1383 bool res = lra_create_live_ranges_1 (all_p, false);
1384 lra_assert (! res);
1387 /* Finish all live ranges. */
1388 void
1389 lra_clear_live_ranges (void)
1391 int i;
1393 for (i = 0; i < max_reg_num (); i++)
1394 free_live_range_list (lra_reg_info[i].live_ranges);
1395 point_freq_vec.release ();
1398 /* Initialize live ranges data once per function. */
1399 void
1400 lra_live_ranges_init (void)
1402 bitmap_initialize (&temp_bitmap, &reg_obstack);
1403 initiate_live_solver ();
1406 /* Finish live ranges data once per function. */
1407 void
1408 lra_live_ranges_finish (void)
1410 finish_live_solver ();
1411 bitmap_clear (&temp_bitmap);
1412 lra_live_range_pool.release ();