Improve max_insns_skipped logic
[official-gcc.git] / gcc / lra-lives.c
blobf29dd049bad0e7d55c7382fe62d7f59020a5e379
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 function processing birth of hard register REGNO. It updates
224 living hard regs, START_LIVING, and conflict hard regs for living
225 pseudos. Conflict hard regs for the pic pseudo is not updated if
226 REGNO is REAL_PIC_OFFSET_TABLE_REGNUM and CHECK_PIC_PSEUDO_P is
227 true. */
228 static void
229 make_hard_regno_born (int regno, bool check_pic_pseudo_p ATTRIBUTE_UNUSED)
231 unsigned int i;
233 lra_assert (regno < FIRST_PSEUDO_REGISTER);
234 if (TEST_HARD_REG_BIT (hard_regs_live, regno))
235 return;
236 SET_HARD_REG_BIT (hard_regs_live, regno);
237 sparseset_set_bit (start_living, regno);
238 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
239 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
240 if (! check_pic_pseudo_p
241 || regno != REAL_PIC_OFFSET_TABLE_REGNUM
242 || pic_offset_table_rtx == NULL
243 || i != REGNO (pic_offset_table_rtx))
244 #endif
245 SET_HARD_REG_BIT (lra_reg_info[i].conflict_hard_regs, regno);
248 /* Process the death of hard register REGNO. This updates
249 hard_regs_live and START_DYING. */
250 static void
251 make_hard_regno_dead (int regno)
253 lra_assert (regno < FIRST_PSEUDO_REGISTER);
254 if (! TEST_HARD_REG_BIT (hard_regs_live, regno))
255 return;
256 sparseset_set_bit (start_dying, regno);
257 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
260 /* Mark pseudo REGNO as living at program point POINT, update conflicting
261 hard registers of the pseudo and START_LIVING, and start a new live
262 range for the pseudo corresponding to REGNO if it is necessary. */
263 static void
264 mark_pseudo_live (int regno, int point)
266 lra_live_range_t p;
268 lra_assert (regno >= FIRST_PSEUDO_REGISTER);
269 lra_assert (! sparseset_bit_p (pseudos_live, regno));
270 sparseset_set_bit (pseudos_live, regno);
271 IOR_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs, hard_regs_live);
273 if ((complete_info_p || lra_get_regno_hard_regno (regno) < 0)
274 && ((p = lra_reg_info[regno].live_ranges) == NULL
275 || (p->finish != point && p->finish + 1 != point)))
276 lra_reg_info[regno].live_ranges
277 = create_live_range (regno, point, -1, p);
278 sparseset_set_bit (start_living, regno);
281 /* Mark pseudo REGNO as not living at program point POINT and update
282 START_DYING.
283 This finishes the current live range for the pseudo corresponding
284 to REGNO. */
285 static void
286 mark_pseudo_dead (int regno, int point)
288 lra_live_range_t p;
290 lra_assert (regno >= FIRST_PSEUDO_REGISTER);
291 lra_assert (sparseset_bit_p (pseudos_live, regno));
292 sparseset_clear_bit (pseudos_live, regno);
293 sparseset_set_bit (start_dying, regno);
294 if (complete_info_p || lra_get_regno_hard_regno (regno) < 0)
296 p = lra_reg_info[regno].live_ranges;
297 lra_assert (p != NULL);
298 p->finish = point;
302 /* The corresponding bitmaps of BB currently being processed. */
303 static bitmap bb_killed_pseudos, bb_gen_pseudos;
305 /* Mark register REGNO (pseudo or hard register) in MODE as live at
306 program point POINT. Update BB_GEN_PSEUDOS.
307 Return TRUE if the liveness tracking sets were modified, or FALSE
308 if nothing changed. */
309 static bool
310 mark_regno_live (int regno, machine_mode mode, int point)
312 int last;
313 bool changed = false;
315 if (regno < FIRST_PSEUDO_REGISTER)
317 for (last = regno + hard_regno_nregs[regno][mode];
318 regno < last;
319 regno++)
320 make_hard_regno_born (regno, false);
322 else
324 if (! sparseset_bit_p (pseudos_live, regno))
326 mark_pseudo_live (regno, point);
327 changed = true;
329 bitmap_set_bit (bb_gen_pseudos, regno);
331 return changed;
335 /* Mark register REGNO in MODE as dead at program point POINT. Update
336 BB_GEN_PSEUDOS and BB_KILLED_PSEUDOS. Return TRUE if the liveness
337 tracking sets were modified, or FALSE if nothing changed. */
338 static bool
339 mark_regno_dead (int regno, machine_mode mode, int point)
341 int last;
342 bool changed = false;
344 if (regno < FIRST_PSEUDO_REGISTER)
346 for (last = regno + hard_regno_nregs[regno][mode];
347 regno < last;
348 regno++)
349 make_hard_regno_dead (regno);
351 else
353 if (sparseset_bit_p (pseudos_live, regno))
355 mark_pseudo_dead (regno, point);
356 changed = true;
358 bitmap_clear_bit (bb_gen_pseudos, regno);
359 bitmap_set_bit (bb_killed_pseudos, regno);
361 return changed;
366 /* This page contains code for making global live analysis of pseudos.
367 The code works only when pseudo live info is changed on a BB
368 border. That might be a consequence of some global transformations
369 in LRA, e.g. PIC pseudo reuse or rematerialization. */
371 /* Structure describing local BB data used for pseudo
372 live-analysis. */
373 struct bb_data_pseudos
375 /* Basic block about which the below data are. */
376 basic_block bb;
377 bitmap_head killed_pseudos; /* pseudos killed in the BB. */
378 bitmap_head gen_pseudos; /* pseudos generated in the BB. */
381 /* Array for all BB data. Indexed by the corresponding BB index. */
382 typedef struct bb_data_pseudos *bb_data_t;
384 /* All basic block data are referred through the following array. */
385 static bb_data_t bb_data;
387 /* Two small functions for access to the bb data. */
388 static inline bb_data_t
389 get_bb_data (basic_block bb)
391 return &bb_data[(bb)->index];
394 static inline bb_data_t
395 get_bb_data_by_index (int index)
397 return &bb_data[index];
400 /* Bitmap with all hard regs. */
401 static bitmap_head all_hard_regs_bitmap;
403 /* The transfer function used by the DF equation solver to propagate
404 live info through block with BB_INDEX according to the following
405 equation:
407 bb.livein = (bb.liveout - bb.kill) OR bb.gen
409 static bool
410 live_trans_fun (int bb_index)
412 basic_block bb = get_bb_data_by_index (bb_index)->bb;
413 bitmap bb_liveout = df_get_live_out (bb);
414 bitmap bb_livein = df_get_live_in (bb);
415 bb_data_t bb_info = get_bb_data (bb);
417 bitmap_and_compl (&temp_bitmap, bb_liveout, &all_hard_regs_bitmap);
418 return bitmap_ior_and_compl (bb_livein, &bb_info->gen_pseudos,
419 &temp_bitmap, &bb_info->killed_pseudos);
422 /* The confluence function used by the DF equation solver to set up
423 live info for a block BB without predecessor. */
424 static void
425 live_con_fun_0 (basic_block bb)
427 bitmap_and_into (df_get_live_out (bb), &all_hard_regs_bitmap);
430 /* The confluence function used by the DF equation solver to propagate
431 live info from successor to predecessor on edge E according to the
432 following equation:
434 bb.liveout = 0 for entry block | OR (livein of successors)
436 static bool
437 live_con_fun_n (edge e)
439 basic_block bb = e->src;
440 basic_block dest = e->dest;
441 bitmap bb_liveout = df_get_live_out (bb);
442 bitmap dest_livein = df_get_live_in (dest);
444 return bitmap_ior_and_compl_into (bb_liveout,
445 dest_livein, &all_hard_regs_bitmap);
448 /* Indexes of all function blocks. */
449 static bitmap_head all_blocks;
451 /* Allocate and initialize data needed for global pseudo live
452 analysis. */
453 static void
454 initiate_live_solver (void)
456 bitmap_initialize (&all_hard_regs_bitmap, &reg_obstack);
457 bitmap_set_range (&all_hard_regs_bitmap, 0, FIRST_PSEUDO_REGISTER);
458 bb_data = XNEWVEC (struct bb_data_pseudos, last_basic_block_for_fn (cfun));
459 bitmap_initialize (&all_blocks, &reg_obstack);
461 basic_block bb;
462 FOR_ALL_BB_FN (bb, cfun)
464 bb_data_t bb_info = get_bb_data (bb);
465 bb_info->bb = bb;
466 bitmap_initialize (&bb_info->killed_pseudos, &reg_obstack);
467 bitmap_initialize (&bb_info->gen_pseudos, &reg_obstack);
468 bitmap_set_bit (&all_blocks, bb->index);
472 /* Free all data needed for global pseudo live analysis. */
473 static void
474 finish_live_solver (void)
476 basic_block bb;
478 bitmap_clear (&all_blocks);
479 FOR_ALL_BB_FN (bb, cfun)
481 bb_data_t bb_info = get_bb_data (bb);
482 bitmap_clear (&bb_info->killed_pseudos);
483 bitmap_clear (&bb_info->gen_pseudos);
485 free (bb_data);
486 bitmap_clear (&all_hard_regs_bitmap);
491 /* Insn currently scanned. */
492 static rtx_insn *curr_insn;
493 /* The insn data. */
494 static lra_insn_recog_data_t curr_id;
495 /* The insn static data. */
496 static struct lra_static_insn_data *curr_static_id;
498 /* Vec containing execution frequencies of program points. */
499 static vec<int> point_freq_vec;
501 /* The start of the above vector elements. */
502 int *lra_point_freq;
504 /* Increment the current program point POINT to the next point which has
505 execution frequency FREQ. */
506 static void
507 next_program_point (int &point, int freq)
509 point_freq_vec.safe_push (freq);
510 lra_point_freq = point_freq_vec.address ();
511 point++;
514 /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
515 void
516 lra_setup_reload_pseudo_preferenced_hard_reg (int regno,
517 int hard_regno, int profit)
519 lra_assert (regno >= lra_constraint_new_regno_start);
520 if (lra_reg_info[regno].preferred_hard_regno1 == hard_regno)
521 lra_reg_info[regno].preferred_hard_regno_profit1 += profit;
522 else if (lra_reg_info[regno].preferred_hard_regno2 == hard_regno)
523 lra_reg_info[regno].preferred_hard_regno_profit2 += profit;
524 else if (lra_reg_info[regno].preferred_hard_regno1 < 0)
526 lra_reg_info[regno].preferred_hard_regno1 = hard_regno;
527 lra_reg_info[regno].preferred_hard_regno_profit1 = profit;
529 else if (lra_reg_info[regno].preferred_hard_regno2 < 0
530 || profit > lra_reg_info[regno].preferred_hard_regno_profit2)
532 lra_reg_info[regno].preferred_hard_regno2 = hard_regno;
533 lra_reg_info[regno].preferred_hard_regno_profit2 = profit;
535 else
536 return;
537 /* Keep the 1st hard regno as more profitable. */
538 if (lra_reg_info[regno].preferred_hard_regno1 >= 0
539 && lra_reg_info[regno].preferred_hard_regno2 >= 0
540 && (lra_reg_info[regno].preferred_hard_regno_profit2
541 > lra_reg_info[regno].preferred_hard_regno_profit1))
543 std::swap (lra_reg_info[regno].preferred_hard_regno1,
544 lra_reg_info[regno].preferred_hard_regno2);
545 std::swap (lra_reg_info[regno].preferred_hard_regno_profit1,
546 lra_reg_info[regno].preferred_hard_regno_profit2);
548 if (lra_dump_file != NULL)
550 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
551 fprintf (lra_dump_file,
552 " Hard reg %d is preferable by r%d with profit %d\n",
553 hard_regno, regno,
554 lra_reg_info[regno].preferred_hard_regno_profit1);
555 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
556 fprintf (lra_dump_file,
557 " Hard reg %d is preferable by r%d with profit %d\n",
558 hard_regno, regno,
559 lra_reg_info[regno].preferred_hard_regno_profit2);
563 /* Check that REGNO living through calls and setjumps, set up conflict
564 regs using LAST_CALL_USED_REG_SET, and clear corresponding bits in
565 PSEUDOS_LIVE_THROUGH_CALLS and PSEUDOS_LIVE_THROUGH_SETJUMPS. */
566 static inline void
567 check_pseudos_live_through_calls (int regno,
568 HARD_REG_SET last_call_used_reg_set)
570 int hr;
572 if (! sparseset_bit_p (pseudos_live_through_calls, regno))
573 return;
574 sparseset_clear_bit (pseudos_live_through_calls, regno);
575 IOR_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs,
576 last_call_used_reg_set);
578 for (hr = 0; hr < FIRST_PSEUDO_REGISTER; hr++)
579 if (targetm.hard_regno_call_part_clobbered (hr,
580 PSEUDO_REGNO_MODE (regno)))
581 SET_HARD_REG_BIT (lra_reg_info[regno].conflict_hard_regs, hr);
582 lra_reg_info[regno].call_p = true;
583 if (! sparseset_bit_p (pseudos_live_through_setjumps, regno))
584 return;
585 sparseset_clear_bit (pseudos_live_through_setjumps, regno);
586 /* Don't allocate pseudos that cross setjmps or any call, if this
587 function receives a nonlocal goto. */
588 SET_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs);
591 /* Return true if insn REG is an early clobber operand in alternative
592 NALT. Negative NALT means that we don't know the current insn
593 alternative. So assume the worst. */
594 static inline bool
595 reg_early_clobber_p (const struct lra_insn_reg *reg, int n_alt)
597 return (reg->early_clobber
598 && (n_alt < 0 || TEST_BIT (reg->early_clobber_alts, n_alt)));
601 /* Process insns of the basic block BB to update pseudo live ranges,
602 pseudo hard register conflicts, and insn notes. We do it on
603 backward scan of BB insns. CURR_POINT is the program point where
604 BB ends. The function updates this counter and returns in
605 CURR_POINT the program point where BB starts. The function also
606 does local live info updates and can delete the dead insns if
607 DEAD_INSN_P. It returns true if pseudo live info was
608 changed at the BB start. */
609 static bool
610 process_bb_lives (basic_block bb, int &curr_point, bool dead_insn_p)
612 int i, regno, freq;
613 unsigned int j;
614 bitmap_iterator bi;
615 bitmap reg_live_out;
616 unsigned int px;
617 rtx_insn *next;
618 rtx link, *link_loc;
619 bool need_curr_point_incr;
620 HARD_REG_SET last_call_used_reg_set;
622 reg_live_out = df_get_live_out (bb);
623 sparseset_clear (pseudos_live);
624 sparseset_clear (pseudos_live_through_calls);
625 sparseset_clear (pseudos_live_through_setjumps);
626 CLEAR_HARD_REG_SET (last_call_used_reg_set);
627 REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
628 AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
629 EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
630 mark_pseudo_live (j, curr_point);
632 bb_gen_pseudos = &get_bb_data (bb)->gen_pseudos;
633 bb_killed_pseudos = &get_bb_data (bb)->killed_pseudos;
634 bitmap_clear (bb_gen_pseudos);
635 bitmap_clear (bb_killed_pseudos);
636 freq = REG_FREQ_FROM_BB (bb);
638 if (lra_dump_file != NULL)
639 fprintf (lra_dump_file, " BB %d\n", bb->index);
641 /* Scan the code of this basic block, noting which pseudos and hard
642 regs are born or die.
644 Note that this loop treats uninitialized values as live until the
645 beginning of the block. For example, if an instruction uses
646 (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
647 FOO will remain live until the beginning of the block. Likewise
648 if FOO is not set at all. This is unnecessarily pessimistic, but
649 it probably doesn't matter much in practice. */
650 FOR_BB_INSNS_REVERSE_SAFE (bb, curr_insn, next)
652 bool call_p;
653 int n_alt, dst_regno, src_regno;
654 rtx set;
655 struct lra_insn_reg *reg;
657 if (!NONDEBUG_INSN_P (curr_insn))
658 continue;
660 curr_id = lra_get_insn_recog_data (curr_insn);
661 curr_static_id = curr_id->insn_static_data;
662 n_alt = curr_id->used_insn_alternative;
663 if (lra_dump_file != NULL)
664 fprintf (lra_dump_file, " Insn %u: point = %d, n_alt = %d\n",
665 INSN_UID (curr_insn), curr_point, n_alt);
667 set = single_set (curr_insn);
669 if (dead_insn_p && set != NULL_RTX
670 && REG_P (SET_DEST (set)) && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
671 && find_reg_note (curr_insn, REG_EH_REGION, NULL_RTX) == NULL_RTX
672 && ! may_trap_p (PATTERN (curr_insn))
673 /* Don't do premature remove of pic offset pseudo as we can
674 start to use it after some reload generation. */
675 && (pic_offset_table_rtx == NULL_RTX
676 || pic_offset_table_rtx != SET_DEST (set)))
678 bool remove_p = true;
680 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
681 if (reg->type != OP_IN && sparseset_bit_p (pseudos_live, reg->regno))
683 remove_p = false;
684 break;
686 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
687 if (reg->type != OP_IN)
689 remove_p = false;
690 break;
692 if (remove_p && ! volatile_refs_p (PATTERN (curr_insn)))
694 dst_regno = REGNO (SET_DEST (set));
695 if (lra_dump_file != NULL)
696 fprintf (lra_dump_file, " Deleting dead insn %u\n",
697 INSN_UID (curr_insn));
698 lra_set_insn_deleted (curr_insn);
699 if (lra_reg_info[dst_regno].nrefs == 0)
701 /* There might be some debug insns with the pseudo. */
702 unsigned int uid;
703 rtx_insn *insn;
705 bitmap_copy (&temp_bitmap, &lra_reg_info[dst_regno].insn_bitmap);
706 EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap, 0, uid, bi)
708 insn = lra_insn_recog_data[uid]->insn;
709 lra_substitute_pseudo_within_insn (insn, dst_regno,
710 SET_SRC (set), true);
711 lra_update_insn_regno_info (insn);
714 continue;
718 /* Update max ref width and hard reg usage. */
719 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
721 int i, regno = reg->regno;
723 if (partial_subreg_p (lra_reg_info[regno].biggest_mode,
724 reg->biggest_mode))
725 lra_reg_info[regno].biggest_mode = reg->biggest_mode;
726 if (regno < FIRST_PSEUDO_REGISTER)
728 lra_hard_reg_usage[regno] += freq;
729 /* A hard register explicitly can be used in small mode,
730 but implicitly it can be used in natural mode as a
731 part of multi-register group. Process this case
732 here. */
733 for (i = 1; i < hard_regno_nregs[regno][reg->biggest_mode]; i++)
734 if (partial_subreg_p (lra_reg_info[regno + i].biggest_mode,
735 GET_MODE (regno_reg_rtx[regno + i])))
736 lra_reg_info[regno + i].biggest_mode
737 = GET_MODE (regno_reg_rtx[regno + i]);
741 call_p = CALL_P (curr_insn);
742 src_regno = (set != NULL_RTX && REG_P (SET_SRC (set))
743 ? REGNO (SET_SRC (set)) : -1);
744 dst_regno = (set != NULL_RTX && REG_P (SET_DEST (set))
745 ? REGNO (SET_DEST (set)) : -1);
746 if (complete_info_p
747 && src_regno >= 0 && dst_regno >= 0
748 /* Check that source regno does not conflict with
749 destination regno to exclude most impossible
750 preferences. */
751 && (((src_regno >= FIRST_PSEUDO_REGISTER
752 && (! sparseset_bit_p (pseudos_live, src_regno)
753 || (dst_regno >= FIRST_PSEUDO_REGISTER
754 && lra_reg_val_equal_p (src_regno,
755 lra_reg_info[dst_regno].val,
756 lra_reg_info[dst_regno].offset))))
757 || (src_regno < FIRST_PSEUDO_REGISTER
758 && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno)))
759 /* It might be 'inheritance pseudo <- reload pseudo'. */
760 || (src_regno >= lra_constraint_new_regno_start
761 && dst_regno >= lra_constraint_new_regno_start
762 /* Remember to skip special cases where src/dest regnos are
763 the same, e.g. insn SET pattern has matching constraints
764 like =r,0. */
765 && src_regno != dst_regno)))
767 int hard_regno = -1, regno = -1;
769 if (dst_regno >= lra_constraint_new_regno_start
770 && src_regno >= lra_constraint_new_regno_start)
772 /* It might be still an original (non-reload) insn with
773 one unused output and a constraint requiring to use
774 the same reg for input/output operands. In this case
775 dst_regno and src_regno have the same value, we don't
776 need a misleading copy for this case. */
777 if (dst_regno != src_regno)
778 lra_create_copy (dst_regno, src_regno, freq);
780 else if (dst_regno >= lra_constraint_new_regno_start)
782 if ((hard_regno = src_regno) >= FIRST_PSEUDO_REGISTER)
783 hard_regno = reg_renumber[src_regno];
784 regno = dst_regno;
786 else if (src_regno >= lra_constraint_new_regno_start)
788 if ((hard_regno = dst_regno) >= FIRST_PSEUDO_REGISTER)
789 hard_regno = reg_renumber[dst_regno];
790 regno = src_regno;
792 if (regno >= 0 && hard_regno >= 0)
793 lra_setup_reload_pseudo_preferenced_hard_reg
794 (regno, hard_regno, freq);
797 sparseset_clear (start_living);
799 /* Try to avoid unnecessary program point increments, this saves
800 a lot of time in remove_some_program_points_and_update_live_ranges.
801 We only need an increment if something becomes live or dies at this
802 program point. */
803 need_curr_point_incr = false;
805 /* Mark each defined value as live. We need to do this for
806 unused values because they still conflict with quantities
807 that are live at the time of the definition. */
808 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
809 if (reg->type != OP_IN)
811 need_curr_point_incr
812 |= mark_regno_live (reg->regno, reg->biggest_mode,
813 curr_point);
814 check_pseudos_live_through_calls (reg->regno,
815 last_call_used_reg_set);
818 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
819 if (reg->type != OP_IN)
820 make_hard_regno_born (reg->regno, false);
822 if (curr_id->arg_hard_regs != NULL)
823 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
824 if (regno >= FIRST_PSEUDO_REGISTER)
825 /* It is a clobber. */
826 make_hard_regno_born (regno - FIRST_PSEUDO_REGISTER, false);
828 sparseset_copy (unused_set, start_living);
830 sparseset_clear (start_dying);
832 /* See which defined values die here. */
833 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
834 if (reg->type == OP_OUT
835 && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
836 need_curr_point_incr
837 |= mark_regno_dead (reg->regno, reg->biggest_mode,
838 curr_point);
840 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
841 if (reg->type == OP_OUT
842 && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
843 make_hard_regno_dead (reg->regno);
845 if (curr_id->arg_hard_regs != NULL)
846 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
847 if (regno >= FIRST_PSEUDO_REGISTER)
848 /* It is a clobber. */
849 make_hard_regno_dead (regno - FIRST_PSEUDO_REGISTER);
851 if (call_p)
853 if (! flag_ipa_ra)
854 COPY_HARD_REG_SET(last_call_used_reg_set, call_used_reg_set);
855 else
857 HARD_REG_SET this_call_used_reg_set;
858 get_call_reg_set_usage (curr_insn, &this_call_used_reg_set,
859 call_used_reg_set);
861 bool flush = (! hard_reg_set_empty_p (last_call_used_reg_set)
862 && ! hard_reg_set_equal_p (last_call_used_reg_set,
863 this_call_used_reg_set));
865 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
867 IOR_HARD_REG_SET (lra_reg_info[j].actual_call_used_reg_set,
868 this_call_used_reg_set);
869 if (flush)
870 check_pseudos_live_through_calls
871 (j, last_call_used_reg_set);
873 COPY_HARD_REG_SET(last_call_used_reg_set, this_call_used_reg_set);
876 sparseset_ior (pseudos_live_through_calls,
877 pseudos_live_through_calls, pseudos_live);
878 if (cfun->has_nonlocal_label
879 || find_reg_note (curr_insn, REG_SETJMP,
880 NULL_RTX) != NULL_RTX)
881 sparseset_ior (pseudos_live_through_setjumps,
882 pseudos_live_through_setjumps, pseudos_live);
885 /* Increment the current program point if we must. */
886 if (need_curr_point_incr)
887 next_program_point (curr_point, freq);
889 sparseset_clear (start_living);
891 need_curr_point_incr = false;
893 /* Mark each used value as live. */
894 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
895 if (reg->type == OP_IN)
897 need_curr_point_incr
898 |= mark_regno_live (reg->regno, reg->biggest_mode,
899 curr_point);
900 check_pseudos_live_through_calls (reg->regno,
901 last_call_used_reg_set);
904 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
905 if (reg->type == OP_IN)
906 make_hard_regno_born (reg->regno, false);
908 if (curr_id->arg_hard_regs != NULL)
909 /* Make argument hard registers live. Don't create conflict
910 of used REAL_PIC_OFFSET_TABLE_REGNUM and the pic pseudo. */
911 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
912 if (regno < FIRST_PSEUDO_REGISTER)
913 make_hard_regno_born (regno, true);
915 sparseset_and_compl (dead_set, start_living, start_dying);
917 /* Mark early clobber outputs dead. */
918 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
919 if (reg->type == OP_OUT
920 && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
921 need_curr_point_incr
922 |= mark_regno_dead (reg->regno, reg->biggest_mode,
923 curr_point);
925 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
926 if (reg->type == OP_OUT
927 && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
928 make_hard_regno_dead (reg->regno);
930 if (need_curr_point_incr)
931 next_program_point (curr_point, freq);
933 /* Update notes. */
934 for (link_loc = &REG_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
936 if (REG_NOTE_KIND (link) != REG_DEAD
937 && REG_NOTE_KIND (link) != REG_UNUSED)
939 else if (REG_P (XEXP (link, 0)))
941 regno = REGNO (XEXP (link, 0));
942 if ((REG_NOTE_KIND (link) == REG_DEAD
943 && ! sparseset_bit_p (dead_set, regno))
944 || (REG_NOTE_KIND (link) == REG_UNUSED
945 && ! sparseset_bit_p (unused_set, regno)))
947 *link_loc = XEXP (link, 1);
948 continue;
950 if (REG_NOTE_KIND (link) == REG_DEAD)
951 sparseset_clear_bit (dead_set, regno);
952 else if (REG_NOTE_KIND (link) == REG_UNUSED)
953 sparseset_clear_bit (unused_set, regno);
955 link_loc = &XEXP (link, 1);
957 EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
958 add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
959 EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
960 add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
963 if (bb_has_eh_pred (bb))
964 for (j = 0; ; ++j)
966 unsigned int regno = EH_RETURN_DATA_REGNO (j);
968 if (regno == INVALID_REGNUM)
969 break;
970 make_hard_regno_born (regno, false);
973 /* Pseudos can't go in stack regs at the start of a basic block that
974 is reached by an abnormal edge. Likewise for call clobbered regs,
975 because caller-save, fixup_abnormal_edges and possibly the table
976 driven EH machinery are not quite ready to handle such pseudos
977 live across such edges. */
978 if (bb_has_abnormal_pred (bb))
980 #ifdef STACK_REGS
981 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
982 lra_reg_info[px].no_stack_p = true;
983 for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
984 make_hard_regno_born (px, false);
985 #endif
986 /* No need to record conflicts for call clobbered regs if we
987 have nonlocal labels around, as we don't ever try to
988 allocate such regs in this case. */
989 if (!cfun->has_nonlocal_label
990 && has_abnormal_call_or_eh_pred_edge_p (bb))
991 for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
992 if (call_used_regs[px]
993 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
994 /* We should create a conflict of PIC pseudo with PIC
995 hard reg as PIC hard reg can have a wrong value after
996 jump described by the abnormal edge. In this case we
997 can not allocate PIC hard reg to PIC pseudo as PIC
998 pseudo will also have a wrong value. */
999 || (px == REAL_PIC_OFFSET_TABLE_REGNUM
1000 && pic_offset_table_rtx != NULL_RTX
1001 && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
1002 #endif
1004 make_hard_regno_born (px, false);
1007 bool live_change_p = false;
1008 /* Check if bb border live info was changed. */
1009 unsigned int live_pseudos_num = 0;
1010 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb),
1011 FIRST_PSEUDO_REGISTER, j, bi)
1013 live_pseudos_num++;
1014 if (! sparseset_bit_p (pseudos_live, j))
1016 live_change_p = true;
1017 if (lra_dump_file != NULL)
1018 fprintf (lra_dump_file,
1019 " r%d is removed as live at bb%d start\n", j, bb->index);
1020 break;
1023 if (! live_change_p
1024 && sparseset_cardinality (pseudos_live) != live_pseudos_num)
1026 live_change_p = true;
1027 if (lra_dump_file != NULL)
1028 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
1029 if (! bitmap_bit_p (df_get_live_in (bb), j))
1030 fprintf (lra_dump_file,
1031 " r%d is added to live at bb%d start\n", j, bb->index);
1033 /* See if we'll need an increment at the end of this basic block.
1034 An increment is needed if the PSEUDOS_LIVE set is not empty,
1035 to make sure the finish points are set up correctly. */
1036 need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0);
1038 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
1039 mark_pseudo_dead (i, curr_point);
1041 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
1043 if (sparseset_cardinality (pseudos_live_through_calls) == 0)
1044 break;
1045 if (sparseset_bit_p (pseudos_live_through_calls, j))
1046 check_pseudos_live_through_calls (j, last_call_used_reg_set);
1049 if (need_curr_point_incr)
1050 next_program_point (curr_point, freq);
1052 return live_change_p;
1055 /* Compress pseudo live ranges by removing program points where
1056 nothing happens. Complexity of many algorithms in LRA is linear
1057 function of program points number. To speed up the code we try to
1058 minimize the number of the program points here. */
1059 static void
1060 remove_some_program_points_and_update_live_ranges (void)
1062 unsigned i;
1063 int n, max_regno;
1064 int *map;
1065 lra_live_range_t r, prev_r, next_r;
1066 sbitmap_iterator sbi;
1067 bool born_p, dead_p, prev_born_p, prev_dead_p;
1069 auto_sbitmap born (lra_live_max_point);
1070 auto_sbitmap dead (lra_live_max_point);
1071 bitmap_clear (born);
1072 bitmap_clear (dead);
1073 max_regno = max_reg_num ();
1074 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1076 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1078 lra_assert (r->start <= r->finish);
1079 bitmap_set_bit (born, r->start);
1080 bitmap_set_bit (dead, r->finish);
1083 auto_sbitmap born_or_dead (lra_live_max_point);
1084 bitmap_ior (born_or_dead, born, dead);
1085 map = XCNEWVEC (int, lra_live_max_point);
1086 n = -1;
1087 prev_born_p = prev_dead_p = false;
1088 EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1090 born_p = bitmap_bit_p (born, i);
1091 dead_p = bitmap_bit_p (dead, i);
1092 if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1093 || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1095 map[i] = n;
1096 lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
1098 else
1100 map[i] = ++n;
1101 lra_point_freq[n] = lra_point_freq[i];
1103 prev_born_p = born_p;
1104 prev_dead_p = dead_p;
1106 n++;
1107 if (lra_dump_file != NULL)
1108 fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1109 lra_live_max_point, n, 100 * n / lra_live_max_point);
1110 if (n < lra_live_max_point)
1112 lra_live_max_point = n;
1113 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1115 for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
1116 r != NULL;
1117 r = next_r)
1119 next_r = r->next;
1120 r->start = map[r->start];
1121 r->finish = map[r->finish];
1122 if (prev_r == NULL || prev_r->start > r->finish + 1)
1124 prev_r = r;
1125 continue;
1127 prev_r->start = r->start;
1128 prev_r->next = next_r;
1129 lra_live_range_pool.remove (r);
1133 free (map);
1136 /* Print live ranges R to file F. */
1137 void
1138 lra_print_live_range_list (FILE *f, lra_live_range_t r)
1140 for (; r != NULL; r = r->next)
1141 fprintf (f, " [%d..%d]", r->start, r->finish);
1142 fprintf (f, "\n");
1145 DEBUG_FUNCTION void
1146 debug (lra_live_range &ref)
1148 lra_print_live_range_list (stderr, &ref);
1151 DEBUG_FUNCTION void
1152 debug (lra_live_range *ptr)
1154 if (ptr)
1155 debug (*ptr);
1156 else
1157 fprintf (stderr, "<nil>\n");
1160 /* Print live ranges R to stderr. */
1161 void
1162 lra_debug_live_range_list (lra_live_range_t r)
1164 lra_print_live_range_list (stderr, r);
1167 /* Print live ranges of pseudo REGNO to file F. */
1168 static void
1169 print_pseudo_live_ranges (FILE *f, int regno)
1171 if (lra_reg_info[regno].live_ranges == NULL)
1172 return;
1173 fprintf (f, " r%d:", regno);
1174 lra_print_live_range_list (f, lra_reg_info[regno].live_ranges);
1177 /* Print live ranges of pseudo REGNO to stderr. */
1178 void
1179 lra_debug_pseudo_live_ranges (int regno)
1181 print_pseudo_live_ranges (stderr, regno);
1184 /* Print live ranges of all pseudos to file F. */
1185 static void
1186 print_live_ranges (FILE *f)
1188 int i, max_regno;
1190 max_regno = max_reg_num ();
1191 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1192 print_pseudo_live_ranges (f, i);
1195 /* Print live ranges of all pseudos to stderr. */
1196 void
1197 lra_debug_live_ranges (void)
1199 print_live_ranges (stderr);
1202 /* Compress pseudo live ranges. */
1203 static void
1204 compress_live_ranges (void)
1206 remove_some_program_points_and_update_live_ranges ();
1207 if (lra_dump_file != NULL)
1209 fprintf (lra_dump_file, "Ranges after the compression:\n");
1210 print_live_ranges (lra_dump_file);
1216 /* The number of the current live range pass. */
1217 int lra_live_range_iter;
1219 /* The function creates live ranges only for memory pseudos (or for
1220 all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos. It
1221 also does dead insn elimination if DEAD_INSN_P and global live
1222 analysis only for pseudos and only if the pseudo live info was
1223 changed on a BB border. Return TRUE if the live info was
1224 changed. */
1225 static bool
1226 lra_create_live_ranges_1 (bool all_p, bool dead_insn_p)
1228 basic_block bb;
1229 int i, hard_regno, max_regno = max_reg_num ();
1230 int curr_point;
1231 bool bb_live_change_p, have_referenced_pseudos = false;
1233 timevar_push (TV_LRA_CREATE_LIVE_RANGES);
1235 complete_info_p = all_p;
1236 if (lra_dump_file != NULL)
1237 fprintf (lra_dump_file,
1238 "\n********** Pseudo live ranges #%d: **********\n\n",
1239 ++lra_live_range_iter);
1240 memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage));
1241 for (i = 0; i < max_regno; i++)
1243 lra_reg_info[i].live_ranges = NULL;
1244 CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1245 lra_reg_info[i].preferred_hard_regno1 = -1;
1246 lra_reg_info[i].preferred_hard_regno2 = -1;
1247 lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1248 lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1249 #ifdef STACK_REGS
1250 lra_reg_info[i].no_stack_p = false;
1251 #endif
1252 /* The biggest mode is already set but its value might be to
1253 conservative because of recent transformation. Here in this
1254 file we recalculate it again as it costs practically
1255 nothing. */
1256 if (i >= FIRST_PSEUDO_REGISTER && regno_reg_rtx[i] != NULL_RTX)
1257 lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
1258 else
1259 lra_reg_info[i].biggest_mode = VOIDmode;
1260 lra_reg_info[i].call_p = false;
1261 if (i >= FIRST_PSEUDO_REGISTER
1262 && lra_reg_info[i].nrefs != 0)
1264 if ((hard_regno = reg_renumber[i]) >= 0)
1265 lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
1266 have_referenced_pseudos = true;
1269 lra_free_copies ();
1271 /* Under some circumstances, we can have functions without pseudo
1272 registers. For such functions, lra_live_max_point will be 0,
1273 see e.g. PR55604, and there's nothing more to do for us here. */
1274 if (! have_referenced_pseudos)
1276 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1277 return false;
1280 pseudos_live = sparseset_alloc (max_regno);
1281 pseudos_live_through_calls = sparseset_alloc (max_regno);
1282 pseudos_live_through_setjumps = sparseset_alloc (max_regno);
1283 start_living = sparseset_alloc (max_regno);
1284 start_dying = sparseset_alloc (max_regno);
1285 dead_set = sparseset_alloc (max_regno);
1286 unused_set = sparseset_alloc (max_regno);
1287 curr_point = 0;
1288 unsigned new_length = get_max_uid () * 2;
1289 point_freq_vec.truncate (0);
1290 point_freq_vec.reserve_exact (new_length);
1291 lra_point_freq = point_freq_vec.address ();
1292 auto_vec<int, 20> post_order_rev_cfg;
1293 inverted_post_order_compute (&post_order_rev_cfg);
1294 lra_assert (post_order_rev_cfg.length () == (unsigned) n_basic_blocks_for_fn (cfun));
1295 bb_live_change_p = false;
1296 for (i = post_order_rev_cfg.length () - 1; i >= 0; --i)
1298 bb = BASIC_BLOCK_FOR_FN (cfun, post_order_rev_cfg[i]);
1299 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
1300 == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1301 continue;
1302 if (process_bb_lives (bb, curr_point, dead_insn_p))
1303 bb_live_change_p = true;
1305 if (bb_live_change_p)
1307 /* We need to clear pseudo live info as some pseudos can
1308 disappear, e.g. pseudos with used equivalences. */
1309 FOR_EACH_BB_FN (bb, cfun)
1311 bitmap_clear_range (df_get_live_in (bb), FIRST_PSEUDO_REGISTER,
1312 max_regno - FIRST_PSEUDO_REGISTER);
1313 bitmap_clear_range (df_get_live_out (bb), FIRST_PSEUDO_REGISTER,
1314 max_regno - FIRST_PSEUDO_REGISTER);
1316 /* As we did not change CFG since LRA start we can use
1317 DF-infrastructure solver to solve live data flow problem. */
1318 df_simple_dataflow
1319 (DF_BACKWARD, NULL, live_con_fun_0, live_con_fun_n,
1320 live_trans_fun, &all_blocks,
1321 df_get_postorder (DF_BACKWARD), df_get_n_blocks (DF_BACKWARD));
1322 if (lra_dump_file != NULL)
1324 fprintf (lra_dump_file,
1325 "Global pseudo live data have been updated:\n");
1326 basic_block bb;
1327 FOR_EACH_BB_FN (bb, cfun)
1329 bb_data_t bb_info = get_bb_data (bb);
1330 bitmap bb_livein = df_get_live_in (bb);
1331 bitmap bb_liveout = df_get_live_out (bb);
1333 fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
1334 lra_dump_bitmap_with_title (" gen:",
1335 &bb_info->gen_pseudos, bb->index);
1336 lra_dump_bitmap_with_title (" killed:",
1337 &bb_info->killed_pseudos, bb->index);
1338 lra_dump_bitmap_with_title (" livein:", bb_livein, bb->index);
1339 lra_dump_bitmap_with_title (" liveout:", bb_liveout, bb->index);
1343 lra_live_max_point = curr_point;
1344 if (lra_dump_file != NULL)
1345 print_live_ranges (lra_dump_file);
1346 /* Clean up. */
1347 sparseset_free (unused_set);
1348 sparseset_free (dead_set);
1349 sparseset_free (start_dying);
1350 sparseset_free (start_living);
1351 sparseset_free (pseudos_live_through_calls);
1352 sparseset_free (pseudos_live_through_setjumps);
1353 sparseset_free (pseudos_live);
1354 compress_live_ranges ();
1355 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1356 return bb_live_change_p;
1359 /* The main entry function creates live-ranges and other live info
1360 necessary for the assignment sub-pass. It uses
1361 lra_creates_live_ranges_1 -- so read comments for the
1362 function. */
1363 void
1364 lra_create_live_ranges (bool all_p, bool dead_insn_p)
1366 if (! lra_create_live_ranges_1 (all_p, dead_insn_p))
1367 return;
1368 if (lra_dump_file != NULL)
1369 fprintf (lra_dump_file, "Live info was changed -- recalculate it\n");
1370 /* Live info was changed on a bb border. It means that some info,
1371 e.g. about conflict regs, calls crossed, and live ranges may be
1372 wrong. We need this info for allocation. So recalculate it
1373 again but without removing dead insns which can change live info
1374 again. Repetitive live range calculations are expensive therefore
1375 we stop here as we already have correct info although some
1376 improvement in rare cases could be possible on this sub-pass if
1377 we do dead insn elimination again (still the improvement may
1378 happen later). */
1379 lra_clear_live_ranges ();
1380 bool res = lra_create_live_ranges_1 (all_p, false);
1381 lra_assert (! res);
1384 /* Finish all live ranges. */
1385 void
1386 lra_clear_live_ranges (void)
1388 int i;
1390 for (i = 0; i < max_reg_num (); i++)
1391 free_live_range_list (lra_reg_info[i].live_ranges);
1392 point_freq_vec.release ();
1395 /* Initialize live ranges data once per function. */
1396 void
1397 lra_live_ranges_init (void)
1399 bitmap_initialize (&temp_bitmap, &reg_obstack);
1400 initiate_live_solver ();
1403 /* Finish live ranges data once per function. */
1404 void
1405 lra_live_ranges_finish (void)
1407 finish_live_solver ();
1408 bitmap_clear (&temp_bitmap);
1409 lra_live_range_pool.release ();