xfail experimental/memory_resource/resource_adaptor.cc on 32-bit Solaris/x86 (PR...
[official-gcc.git] / gcc / lra-lives.c
blob588bc09cb8e61b2d33320990c7efa3d8ae8672a0
1 /* Build live ranges for pseudos.
2 Copyright (C) 2010-2018 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] || TEST_HARD_REG_BIT (hard_regs_spilled_into, 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] || TEST_HARD_REG_BIT (hard_regs_spilled_into, 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 == LRA_UNKNOWN_ALT
602 || (n_alt != LRA_NON_CLOBBERED_ALT
603 && TEST_BIT (reg->early_clobber_alts, n_alt))));
606 /* Process insns of the basic block BB to update pseudo live ranges,
607 pseudo hard register conflicts, and insn notes. We do it on
608 backward scan of BB insns. CURR_POINT is the program point where
609 BB ends. The function updates this counter and returns in
610 CURR_POINT the program point where BB starts. The function also
611 does local live info updates and can delete the dead insns if
612 DEAD_INSN_P. It returns true if pseudo live info was
613 changed at the BB start. */
614 static bool
615 process_bb_lives (basic_block bb, int &curr_point, bool dead_insn_p)
617 int i, regno, freq;
618 unsigned int j;
619 bitmap_iterator bi;
620 bitmap reg_live_out;
621 unsigned int px;
622 rtx_insn *next;
623 rtx link, *link_loc;
624 bool need_curr_point_incr;
625 HARD_REG_SET last_call_used_reg_set;
627 reg_live_out = df_get_live_out (bb);
628 sparseset_clear (pseudos_live);
629 sparseset_clear (pseudos_live_through_calls);
630 sparseset_clear (pseudos_live_through_setjumps);
631 CLEAR_HARD_REG_SET (last_call_used_reg_set);
632 REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
633 AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
634 EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
635 mark_pseudo_live (j, curr_point);
637 bb_gen_pseudos = &get_bb_data (bb)->gen_pseudos;
638 bb_killed_pseudos = &get_bb_data (bb)->killed_pseudos;
639 bitmap_clear (bb_gen_pseudos);
640 bitmap_clear (bb_killed_pseudos);
641 freq = REG_FREQ_FROM_BB (bb);
643 if (lra_dump_file != NULL)
644 fprintf (lra_dump_file, " BB %d\n", bb->index);
646 /* Scan the code of this basic block, noting which pseudos and hard
647 regs are born or die.
649 Note that this loop treats uninitialized values as live until the
650 beginning of the block. For example, if an instruction uses
651 (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
652 FOO will remain live until the beginning of the block. Likewise
653 if FOO is not set at all. This is unnecessarily pessimistic, but
654 it probably doesn't matter much in practice. */
655 FOR_BB_INSNS_REVERSE_SAFE (bb, curr_insn, next)
657 bool call_p;
658 int n_alt, dst_regno, src_regno;
659 rtx set;
660 struct lra_insn_reg *reg;
662 if (!NONDEBUG_INSN_P (curr_insn))
663 continue;
665 curr_id = lra_get_insn_recog_data (curr_insn);
666 curr_static_id = curr_id->insn_static_data;
667 n_alt = curr_id->used_insn_alternative;
668 if (lra_dump_file != NULL)
669 fprintf (lra_dump_file, " Insn %u: point = %d, n_alt = %d\n",
670 INSN_UID (curr_insn), curr_point, n_alt);
672 set = single_set (curr_insn);
674 if (dead_insn_p && set != NULL_RTX
675 && REG_P (SET_DEST (set)) && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
676 && find_reg_note (curr_insn, REG_EH_REGION, NULL_RTX) == NULL_RTX
677 && ! may_trap_p (PATTERN (curr_insn))
678 /* Don't do premature remove of pic offset pseudo as we can
679 start to use it after some reload generation. */
680 && (pic_offset_table_rtx == NULL_RTX
681 || pic_offset_table_rtx != SET_DEST (set)))
683 bool remove_p = true;
685 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
686 if (reg->type != OP_IN && sparseset_bit_p (pseudos_live, reg->regno))
688 remove_p = false;
689 break;
691 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
692 if (reg->type != OP_IN)
694 remove_p = false;
695 break;
697 if (remove_p && ! volatile_refs_p (PATTERN (curr_insn)))
699 dst_regno = REGNO (SET_DEST (set));
700 if (lra_dump_file != NULL)
701 fprintf (lra_dump_file, " Deleting dead insn %u\n",
702 INSN_UID (curr_insn));
703 lra_set_insn_deleted (curr_insn);
704 if (lra_reg_info[dst_regno].nrefs == 0)
706 /* There might be some debug insns with the pseudo. */
707 unsigned int uid;
708 rtx_insn *insn;
710 bitmap_copy (&temp_bitmap, &lra_reg_info[dst_regno].insn_bitmap);
711 EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap, 0, uid, bi)
713 insn = lra_insn_recog_data[uid]->insn;
714 lra_substitute_pseudo_within_insn (insn, dst_regno,
715 SET_SRC (set), true);
716 lra_update_insn_regno_info (insn);
719 continue;
723 /* Update max ref width and hard reg usage. */
724 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
726 int i, regno = reg->regno;
728 if (partial_subreg_p (lra_reg_info[regno].biggest_mode,
729 reg->biggest_mode))
730 lra_reg_info[regno].biggest_mode = reg->biggest_mode;
731 if (regno < FIRST_PSEUDO_REGISTER)
733 lra_hard_reg_usage[regno] += freq;
734 /* A hard register explicitly can be used in small mode,
735 but implicitly it can be used in natural mode as a
736 part of multi-register group. Process this case
737 here. */
738 for (i = 1; i < hard_regno_nregs (regno, reg->biggest_mode); i++)
739 if (partial_subreg_p (lra_reg_info[regno + i].biggest_mode,
740 GET_MODE (regno_reg_rtx[regno + i])))
741 lra_reg_info[regno + i].biggest_mode
742 = GET_MODE (regno_reg_rtx[regno + i]);
746 call_p = CALL_P (curr_insn);
747 src_regno = (set != NULL_RTX && REG_P (SET_SRC (set))
748 ? REGNO (SET_SRC (set)) : -1);
749 dst_regno = (set != NULL_RTX && REG_P (SET_DEST (set))
750 ? REGNO (SET_DEST (set)) : -1);
751 if (complete_info_p
752 && src_regno >= 0 && dst_regno >= 0
753 /* Check that source regno does not conflict with
754 destination regno to exclude most impossible
755 preferences. */
756 && (((src_regno >= FIRST_PSEUDO_REGISTER
757 && (! sparseset_bit_p (pseudos_live, src_regno)
758 || (dst_regno >= FIRST_PSEUDO_REGISTER
759 && lra_reg_val_equal_p (src_regno,
760 lra_reg_info[dst_regno].val,
761 lra_reg_info[dst_regno].offset))))
762 || (src_regno < FIRST_PSEUDO_REGISTER
763 && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno)))
764 /* It might be 'inheritance pseudo <- reload pseudo'. */
765 || (src_regno >= lra_constraint_new_regno_start
766 && dst_regno >= lra_constraint_new_regno_start
767 /* Remember to skip special cases where src/dest regnos are
768 the same, e.g. insn SET pattern has matching constraints
769 like =r,0. */
770 && src_regno != dst_regno)))
772 int hard_regno = -1, regno = -1;
774 if (dst_regno >= lra_constraint_new_regno_start
775 && src_regno >= lra_constraint_new_regno_start)
777 /* It might be still an original (non-reload) insn with
778 one unused output and a constraint requiring to use
779 the same reg for input/output operands. In this case
780 dst_regno and src_regno have the same value, we don't
781 need a misleading copy for this case. */
782 if (dst_regno != src_regno)
783 lra_create_copy (dst_regno, src_regno, freq);
785 else if (dst_regno >= lra_constraint_new_regno_start)
787 if ((hard_regno = src_regno) >= FIRST_PSEUDO_REGISTER)
788 hard_regno = reg_renumber[src_regno];
789 regno = dst_regno;
791 else if (src_regno >= lra_constraint_new_regno_start)
793 if ((hard_regno = dst_regno) >= FIRST_PSEUDO_REGISTER)
794 hard_regno = reg_renumber[dst_regno];
795 regno = src_regno;
797 if (regno >= 0 && hard_regno >= 0)
798 lra_setup_reload_pseudo_preferenced_hard_reg
799 (regno, hard_regno, freq);
802 sparseset_clear (start_living);
804 /* Try to avoid unnecessary program point increments, this saves
805 a lot of time in remove_some_program_points_and_update_live_ranges.
806 We only need an increment if something becomes live or dies at this
807 program point. */
808 need_curr_point_incr = false;
810 /* Mark each defined value as live. We need to do this for
811 unused values because they still conflict with quantities
812 that are live at the time of the definition. */
813 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
814 if (reg->type != OP_IN)
816 need_curr_point_incr
817 |= mark_regno_live (reg->regno, reg->biggest_mode,
818 curr_point);
819 check_pseudos_live_through_calls (reg->regno,
820 last_call_used_reg_set);
823 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
824 if (reg->type != OP_IN)
825 make_hard_regno_born (reg->regno, false);
827 if (curr_id->arg_hard_regs != NULL)
828 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
829 if (regno >= FIRST_PSEUDO_REGISTER)
830 /* It is a clobber. */
831 make_hard_regno_born (regno - FIRST_PSEUDO_REGISTER, false);
833 sparseset_copy (unused_set, start_living);
835 sparseset_clear (start_dying);
837 /* See which defined values die here. */
838 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
839 if (reg->type == OP_OUT
840 && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
841 need_curr_point_incr
842 |= mark_regno_dead (reg->regno, reg->biggest_mode,
843 curr_point);
845 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
846 if (reg->type == OP_OUT
847 && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
848 make_hard_regno_dead (reg->regno);
850 if (curr_id->arg_hard_regs != NULL)
851 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
852 if (regno >= FIRST_PSEUDO_REGISTER)
853 /* It is a clobber. */
854 make_hard_regno_dead (regno - FIRST_PSEUDO_REGISTER);
856 if (call_p)
858 if (! flag_ipa_ra)
859 COPY_HARD_REG_SET(last_call_used_reg_set, call_used_reg_set);
860 else
862 HARD_REG_SET this_call_used_reg_set;
863 get_call_reg_set_usage (curr_insn, &this_call_used_reg_set,
864 call_used_reg_set);
866 bool flush = (! hard_reg_set_empty_p (last_call_used_reg_set)
867 && ! hard_reg_set_equal_p (last_call_used_reg_set,
868 this_call_used_reg_set));
870 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
872 IOR_HARD_REG_SET (lra_reg_info[j].actual_call_used_reg_set,
873 this_call_used_reg_set);
874 if (flush)
875 check_pseudos_live_through_calls
876 (j, last_call_used_reg_set);
878 COPY_HARD_REG_SET(last_call_used_reg_set, this_call_used_reg_set);
881 sparseset_ior (pseudos_live_through_calls,
882 pseudos_live_through_calls, pseudos_live);
883 if (cfun->has_nonlocal_label
884 || find_reg_note (curr_insn, REG_SETJMP,
885 NULL_RTX) != NULL_RTX)
886 sparseset_ior (pseudos_live_through_setjumps,
887 pseudos_live_through_setjumps, pseudos_live);
890 /* Increment the current program point if we must. */
891 if (need_curr_point_incr)
892 next_program_point (curr_point, freq);
894 sparseset_clear (start_living);
896 need_curr_point_incr = false;
898 /* Mark each used value as live. */
899 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
900 if (reg->type == OP_IN)
902 need_curr_point_incr
903 |= mark_regno_live (reg->regno, reg->biggest_mode,
904 curr_point);
905 check_pseudos_live_through_calls (reg->regno,
906 last_call_used_reg_set);
909 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
910 if (reg->type == OP_IN)
911 make_hard_regno_born (reg->regno, false);
913 if (curr_id->arg_hard_regs != NULL)
914 /* Make argument hard registers live. Don't create conflict
915 of used REAL_PIC_OFFSET_TABLE_REGNUM and the pic pseudo. */
916 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
917 if (regno < FIRST_PSEUDO_REGISTER)
918 make_hard_regno_born (regno, true);
920 sparseset_and_compl (dead_set, start_living, start_dying);
922 /* Mark early clobber outputs dead. */
923 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
924 if (reg->type == OP_OUT
925 && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
926 need_curr_point_incr
927 |= mark_regno_dead (reg->regno, reg->biggest_mode,
928 curr_point);
930 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
931 if (reg->type == OP_OUT
932 && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
934 struct lra_insn_reg *reg2;
936 /* We can have early clobbered non-operand hard reg and
937 the same hard reg as an insn input. Don't make hard
938 reg dead before the insns. */
939 for (reg2 = curr_id->regs; reg2 != NULL; reg2 = reg2->next)
940 if (reg2->type != OP_OUT && reg2->regno == reg->regno)
941 break;
942 if (reg2 == NULL)
943 make_hard_regno_dead (reg->regno);
946 if (need_curr_point_incr)
947 next_program_point (curr_point, freq);
949 /* Update notes. */
950 for (link_loc = &REG_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
952 if (REG_NOTE_KIND (link) != REG_DEAD
953 && REG_NOTE_KIND (link) != REG_UNUSED)
955 else if (REG_P (XEXP (link, 0)))
957 regno = REGNO (XEXP (link, 0));
958 if ((REG_NOTE_KIND (link) == REG_DEAD
959 && ! sparseset_bit_p (dead_set, regno))
960 || (REG_NOTE_KIND (link) == REG_UNUSED
961 && ! sparseset_bit_p (unused_set, regno)))
963 *link_loc = XEXP (link, 1);
964 continue;
966 if (REG_NOTE_KIND (link) == REG_DEAD)
967 sparseset_clear_bit (dead_set, regno);
968 else if (REG_NOTE_KIND (link) == REG_UNUSED)
969 sparseset_clear_bit (unused_set, regno);
971 link_loc = &XEXP (link, 1);
973 EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
974 add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
975 EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
976 add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
979 if (bb_has_eh_pred (bb))
980 for (j = 0; ; ++j)
982 unsigned int regno = EH_RETURN_DATA_REGNO (j);
984 if (regno == INVALID_REGNUM)
985 break;
986 make_hard_regno_born (regno, false);
989 /* Pseudos can't go in stack regs at the start of a basic block that
990 is reached by an abnormal edge. Likewise for call clobbered regs,
991 because caller-save, fixup_abnormal_edges and possibly the table
992 driven EH machinery are not quite ready to handle such pseudos
993 live across such edges. */
994 if (bb_has_abnormal_pred (bb))
996 #ifdef STACK_REGS
997 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
998 lra_reg_info[px].no_stack_p = true;
999 for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1000 make_hard_regno_born (px, false);
1001 #endif
1002 /* No need to record conflicts for call clobbered regs if we
1003 have nonlocal labels around, as we don't ever try to
1004 allocate such regs in this case. */
1005 if (!cfun->has_nonlocal_label
1006 && has_abnormal_call_or_eh_pred_edge_p (bb))
1007 for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
1008 if (call_used_regs[px]
1009 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
1010 /* We should create a conflict of PIC pseudo with PIC
1011 hard reg as PIC hard reg can have a wrong value after
1012 jump described by the abnormal edge. In this case we
1013 can not allocate PIC hard reg to PIC pseudo as PIC
1014 pseudo will also have a wrong value. */
1015 || (px == REAL_PIC_OFFSET_TABLE_REGNUM
1016 && pic_offset_table_rtx != NULL_RTX
1017 && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
1018 #endif
1020 make_hard_regno_born (px, false);
1023 bool live_change_p = false;
1024 /* Check if bb border live info was changed. */
1025 unsigned int live_pseudos_num = 0;
1026 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb),
1027 FIRST_PSEUDO_REGISTER, j, bi)
1029 live_pseudos_num++;
1030 if (! sparseset_bit_p (pseudos_live, j))
1032 live_change_p = true;
1033 if (lra_dump_file != NULL)
1034 fprintf (lra_dump_file,
1035 " r%d is removed as live at bb%d start\n", j, bb->index);
1036 break;
1039 if (! live_change_p
1040 && sparseset_cardinality (pseudos_live) != live_pseudos_num)
1042 live_change_p = true;
1043 if (lra_dump_file != NULL)
1044 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
1045 if (! bitmap_bit_p (df_get_live_in (bb), j))
1046 fprintf (lra_dump_file,
1047 " r%d is added to live at bb%d start\n", j, bb->index);
1049 /* See if we'll need an increment at the end of this basic block.
1050 An increment is needed if the PSEUDOS_LIVE set is not empty,
1051 to make sure the finish points are set up correctly. */
1052 need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0);
1054 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
1055 mark_pseudo_dead (i, curr_point);
1057 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
1059 if (sparseset_cardinality (pseudos_live_through_calls) == 0)
1060 break;
1061 if (sparseset_bit_p (pseudos_live_through_calls, j))
1062 check_pseudos_live_through_calls (j, last_call_used_reg_set);
1065 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1067 if (!TEST_HARD_REG_BIT (hard_regs_live, i))
1068 continue;
1070 if (!TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
1071 continue;
1073 if (bitmap_bit_p (df_get_live_in (bb), i))
1074 continue;
1076 live_change_p = true;
1077 if (lra_dump_file)
1078 fprintf (lra_dump_file,
1079 " hard reg r%d is added to live at bb%d start\n", i,
1080 bb->index);
1081 bitmap_set_bit (df_get_live_in (bb), i);
1084 if (need_curr_point_incr)
1085 next_program_point (curr_point, freq);
1087 return live_change_p;
1090 /* Compress pseudo live ranges by removing program points where
1091 nothing happens. Complexity of many algorithms in LRA is linear
1092 function of program points number. To speed up the code we try to
1093 minimize the number of the program points here. */
1094 static void
1095 remove_some_program_points_and_update_live_ranges (void)
1097 unsigned i;
1098 int n, max_regno;
1099 int *map;
1100 lra_live_range_t r, prev_r, next_r;
1101 sbitmap_iterator sbi;
1102 bool born_p, dead_p, prev_born_p, prev_dead_p;
1104 auto_sbitmap born (lra_live_max_point);
1105 auto_sbitmap dead (lra_live_max_point);
1106 bitmap_clear (born);
1107 bitmap_clear (dead);
1108 max_regno = max_reg_num ();
1109 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1111 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1113 lra_assert (r->start <= r->finish);
1114 bitmap_set_bit (born, r->start);
1115 bitmap_set_bit (dead, r->finish);
1118 auto_sbitmap born_or_dead (lra_live_max_point);
1119 bitmap_ior (born_or_dead, born, dead);
1120 map = XCNEWVEC (int, lra_live_max_point);
1121 n = -1;
1122 prev_born_p = prev_dead_p = false;
1123 EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1125 born_p = bitmap_bit_p (born, i);
1126 dead_p = bitmap_bit_p (dead, i);
1127 if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1128 || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1130 map[i] = n;
1131 lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
1133 else
1135 map[i] = ++n;
1136 lra_point_freq[n] = lra_point_freq[i];
1138 prev_born_p = born_p;
1139 prev_dead_p = dead_p;
1141 n++;
1142 if (lra_dump_file != NULL)
1143 fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1144 lra_live_max_point, n, 100 * n / lra_live_max_point);
1145 if (n < lra_live_max_point)
1147 lra_live_max_point = n;
1148 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1150 for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
1151 r != NULL;
1152 r = next_r)
1154 next_r = r->next;
1155 r->start = map[r->start];
1156 r->finish = map[r->finish];
1157 if (prev_r == NULL || prev_r->start > r->finish + 1)
1159 prev_r = r;
1160 continue;
1162 prev_r->start = r->start;
1163 prev_r->next = next_r;
1164 lra_live_range_pool.remove (r);
1168 free (map);
1171 /* Print live ranges R to file F. */
1172 void
1173 lra_print_live_range_list (FILE *f, lra_live_range_t r)
1175 for (; r != NULL; r = r->next)
1176 fprintf (f, " [%d..%d]", r->start, r->finish);
1177 fprintf (f, "\n");
1180 DEBUG_FUNCTION void
1181 debug (lra_live_range &ref)
1183 lra_print_live_range_list (stderr, &ref);
1186 DEBUG_FUNCTION void
1187 debug (lra_live_range *ptr)
1189 if (ptr)
1190 debug (*ptr);
1191 else
1192 fprintf (stderr, "<nil>\n");
1195 /* Print live ranges R to stderr. */
1196 void
1197 lra_debug_live_range_list (lra_live_range_t r)
1199 lra_print_live_range_list (stderr, r);
1202 /* Print live ranges of pseudo REGNO to file F. */
1203 static void
1204 print_pseudo_live_ranges (FILE *f, int regno)
1206 if (lra_reg_info[regno].live_ranges == NULL)
1207 return;
1208 fprintf (f, " r%d:", regno);
1209 lra_print_live_range_list (f, lra_reg_info[regno].live_ranges);
1212 /* Print live ranges of pseudo REGNO to stderr. */
1213 void
1214 lra_debug_pseudo_live_ranges (int regno)
1216 print_pseudo_live_ranges (stderr, regno);
1219 /* Print live ranges of all pseudos to file F. */
1220 static void
1221 print_live_ranges (FILE *f)
1223 int i, max_regno;
1225 max_regno = max_reg_num ();
1226 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1227 print_pseudo_live_ranges (f, i);
1230 /* Print live ranges of all pseudos to stderr. */
1231 void
1232 lra_debug_live_ranges (void)
1234 print_live_ranges (stderr);
1237 /* Compress pseudo live ranges. */
1238 static void
1239 compress_live_ranges (void)
1241 remove_some_program_points_and_update_live_ranges ();
1242 if (lra_dump_file != NULL)
1244 fprintf (lra_dump_file, "Ranges after the compression:\n");
1245 print_live_ranges (lra_dump_file);
1251 /* The number of the current live range pass. */
1252 int lra_live_range_iter;
1254 /* The function creates live ranges only for memory pseudos (or for
1255 all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos. It
1256 also does dead insn elimination if DEAD_INSN_P and global live
1257 analysis only for pseudos and only if the pseudo live info was
1258 changed on a BB border. Return TRUE if the live info was
1259 changed. */
1260 static bool
1261 lra_create_live_ranges_1 (bool all_p, bool dead_insn_p)
1263 basic_block bb;
1264 int i, hard_regno, max_regno = max_reg_num ();
1265 int curr_point;
1266 bool bb_live_change_p, have_referenced_pseudos = false;
1268 timevar_push (TV_LRA_CREATE_LIVE_RANGES);
1270 complete_info_p = all_p;
1271 if (lra_dump_file != NULL)
1272 fprintf (lra_dump_file,
1273 "\n********** Pseudo live ranges #%d: **********\n\n",
1274 ++lra_live_range_iter);
1275 memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage));
1276 for (i = 0; i < max_regno; i++)
1278 lra_reg_info[i].live_ranges = NULL;
1279 CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1280 lra_reg_info[i].preferred_hard_regno1 = -1;
1281 lra_reg_info[i].preferred_hard_regno2 = -1;
1282 lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1283 lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1284 #ifdef STACK_REGS
1285 lra_reg_info[i].no_stack_p = false;
1286 #endif
1287 /* The biggest mode is already set but its value might be to
1288 conservative because of recent transformation. Here in this
1289 file we recalculate it again as it costs practically
1290 nothing. */
1291 if (i >= FIRST_PSEUDO_REGISTER && regno_reg_rtx[i] != NULL_RTX)
1292 lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
1293 else
1294 lra_reg_info[i].biggest_mode = VOIDmode;
1295 lra_reg_info[i].call_p = false;
1296 if (i >= FIRST_PSEUDO_REGISTER
1297 && lra_reg_info[i].nrefs != 0)
1299 if ((hard_regno = reg_renumber[i]) >= 0)
1300 lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
1301 have_referenced_pseudos = true;
1304 lra_free_copies ();
1306 /* Under some circumstances, we can have functions without pseudo
1307 registers. For such functions, lra_live_max_point will be 0,
1308 see e.g. PR55604, and there's nothing more to do for us here. */
1309 if (! have_referenced_pseudos)
1311 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1312 return false;
1315 pseudos_live = sparseset_alloc (max_regno);
1316 pseudos_live_through_calls = sparseset_alloc (max_regno);
1317 pseudos_live_through_setjumps = sparseset_alloc (max_regno);
1318 start_living = sparseset_alloc (max_regno);
1319 start_dying = sparseset_alloc (max_regno);
1320 dead_set = sparseset_alloc (max_regno);
1321 unused_set = sparseset_alloc (max_regno);
1322 curr_point = 0;
1323 unsigned new_length = get_max_uid () * 2;
1324 point_freq_vec.truncate (0);
1325 point_freq_vec.reserve_exact (new_length);
1326 lra_point_freq = point_freq_vec.address ();
1327 auto_vec<int, 20> post_order_rev_cfg;
1328 inverted_post_order_compute (&post_order_rev_cfg);
1329 lra_assert (post_order_rev_cfg.length () == (unsigned) n_basic_blocks_for_fn (cfun));
1330 bb_live_change_p = false;
1331 for (i = post_order_rev_cfg.length () - 1; i >= 0; --i)
1333 bb = BASIC_BLOCK_FOR_FN (cfun, post_order_rev_cfg[i]);
1334 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
1335 == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1336 continue;
1337 if (process_bb_lives (bb, curr_point, dead_insn_p))
1338 bb_live_change_p = true;
1340 if (bb_live_change_p)
1342 /* We need to clear pseudo live info as some pseudos can
1343 disappear, e.g. pseudos with used equivalences. */
1344 FOR_EACH_BB_FN (bb, cfun)
1346 bitmap_clear_range (df_get_live_in (bb), FIRST_PSEUDO_REGISTER,
1347 max_regno - FIRST_PSEUDO_REGISTER);
1348 bitmap_clear_range (df_get_live_out (bb), FIRST_PSEUDO_REGISTER,
1349 max_regno - FIRST_PSEUDO_REGISTER);
1351 /* As we did not change CFG since LRA start we can use
1352 DF-infrastructure solver to solve live data flow problem. */
1353 for (int i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1355 if (TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
1356 bitmap_clear_bit (&all_hard_regs_bitmap, i);
1358 df_simple_dataflow
1359 (DF_BACKWARD, NULL, live_con_fun_0, live_con_fun_n,
1360 live_trans_fun, &all_blocks,
1361 df_get_postorder (DF_BACKWARD), df_get_n_blocks (DF_BACKWARD));
1362 if (lra_dump_file != NULL)
1364 fprintf (lra_dump_file,
1365 "Global pseudo live data have been updated:\n");
1366 basic_block bb;
1367 FOR_EACH_BB_FN (bb, cfun)
1369 bb_data_t bb_info = get_bb_data (bb);
1370 bitmap bb_livein = df_get_live_in (bb);
1371 bitmap bb_liveout = df_get_live_out (bb);
1373 fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
1374 lra_dump_bitmap_with_title (" gen:",
1375 &bb_info->gen_pseudos, bb->index);
1376 lra_dump_bitmap_with_title (" killed:",
1377 &bb_info->killed_pseudos, bb->index);
1378 lra_dump_bitmap_with_title (" livein:", bb_livein, bb->index);
1379 lra_dump_bitmap_with_title (" liveout:", bb_liveout, bb->index);
1383 lra_live_max_point = curr_point;
1384 if (lra_dump_file != NULL)
1385 print_live_ranges (lra_dump_file);
1386 /* Clean up. */
1387 sparseset_free (unused_set);
1388 sparseset_free (dead_set);
1389 sparseset_free (start_dying);
1390 sparseset_free (start_living);
1391 sparseset_free (pseudos_live_through_calls);
1392 sparseset_free (pseudos_live_through_setjumps);
1393 sparseset_free (pseudos_live);
1394 compress_live_ranges ();
1395 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1396 return bb_live_change_p;
1399 /* The main entry function creates live-ranges and other live info
1400 necessary for the assignment sub-pass. It uses
1401 lra_creates_live_ranges_1 -- so read comments for the
1402 function. */
1403 void
1404 lra_create_live_ranges (bool all_p, bool dead_insn_p)
1406 if (! lra_create_live_ranges_1 (all_p, dead_insn_p))
1407 return;
1408 if (lra_dump_file != NULL)
1409 fprintf (lra_dump_file, "Live info was changed -- recalculate it\n");
1410 /* Live info was changed on a bb border. It means that some info,
1411 e.g. about conflict regs, calls crossed, and live ranges may be
1412 wrong. We need this info for allocation. So recalculate it
1413 again but without removing dead insns which can change live info
1414 again. Repetitive live range calculations are expensive therefore
1415 we stop here as we already have correct info although some
1416 improvement in rare cases could be possible on this sub-pass if
1417 we do dead insn elimination again (still the improvement may
1418 happen later). */
1419 lra_clear_live_ranges ();
1420 bool res = lra_create_live_ranges_1 (all_p, false);
1421 lra_assert (! res);
1424 /* Finish all live ranges. */
1425 void
1426 lra_clear_live_ranges (void)
1428 int i;
1430 for (i = 0; i < max_reg_num (); i++)
1431 free_live_range_list (lra_reg_info[i].live_ranges);
1432 point_freq_vec.release ();
1435 /* Initialize live ranges data once per function. */
1436 void
1437 lra_live_ranges_init (void)
1439 bitmap_initialize (&temp_bitmap, &reg_obstack);
1440 initiate_live_solver ();
1443 /* Finish live ranges data once per function. */
1444 void
1445 lra_live_ranges_finish (void)
1447 finish_live_solver ();
1448 bitmap_clear (&temp_bitmap);
1449 lra_live_range_pool.release ();