1/* Build live ranges for pseudos.
2 Copyright (C) 2010-2017 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21
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. */
27
28#include "config.h"
29#include "system.h"
30#include "coretypes.h"
31#include "backend.h"
32#include "rtl.h"
33#include "tree.h"
34#include "predict.h"
35#include "df.h"
36#include "memmodel.h"
37#include "tm_p.h"
38#include "insn-config.h"
39#include "regs.h"
40#include "ira.h"
41#include "recog.h"
42#include "cfganal.h"
43#include "sparseset.h"
44#include "lra-int.h"
45#include "target.h"
46
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. */
54int lra_live_max_point;
55
56/* Accumulated execution frequency of all references for each hard
57 register. */
58int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER];
59
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. */
66static bool complete_info_p;
67
68/* Pseudos live at current point in the RTL scan. */
69static sparseset pseudos_live;
70
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. */
78static sparseset pseudos_live_through_calls;
79static sparseset pseudos_live_through_setjumps;
80
81/* Set of hard regs (except eliminable ones) currently live. */
82static HARD_REG_SET hard_regs_live;
83
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. */
87static sparseset start_living, start_dying;
88
89/* Set of pseudos and hard regs dead and unused in the current
90 insn. */
91static sparseset unused_set, dead_set;
92
93/* Bitmap used for holding intermediate bitmap operation results. */
94static bitmap_head temp_bitmap;
95
96/* Pool for pseudo live ranges. */
97static object_allocator<lra_live_range> lra_live_range_pool ("live ranges");
98
99/* Free live range list LR. */
100static void
101free_live_range_list (lra_live_range_t lr)
102{
103 lra_live_range_t next;
104
105 while (lr != NULL)
106 {
107 next = lr->next;
108 lra_live_range_pool.remove (lr);
109 lr = next;
110 }
111}
112
113/* Create and return pseudo live range with given attributes. */
114static lra_live_range_t
115create_live_range (int regno, int start, int finish, lra_live_range_t next)
116{
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;
123}
124
125/* Copy live range R and return the result. */
126static lra_live_range_t
127copy_live_range (lra_live_range_t r)
128{
129 return new (lra_live_range_pool) lra_live_range (*r);
130}
131
132/* Copy live range list given by its head R and return the result. */
133lra_live_range_t
134lra_copy_live_range_list (lra_live_range_t r)
135{
136 lra_live_range_t p, first, *chain;
137
138 first = NULL;
139 for (chain = &first; r != NULL; r = r->next)
140 {
141 p = copy_live_range (r);
142 *chain = p;
143 chain = &p->next;
144 }
145 return first;
146}
147
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. */
152lra_live_range_t
153lra_merge_live_ranges (lra_live_range_t r1, lra_live_range_t r2)
154{
155 lra_live_range_t first, last;
156
157 if (r1 == NULL)
158 return r2;
159 if (r2 == NULL)
160 return r1;
161 for (first = last = NULL; r1 != NULL && r2 != NULL;)
162 {
163 if (r1->start < r2->start)
164 std::swap (r1, r2);
165
166 if (r1->start == r2->finish + 1)
167 {
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);
173 }
174 else
175 {
176 gcc_assert (r2->finish + 1 < r1->start);
177 /* Add r1 to the result. */
178 if (first == NULL)
179 first = last = r1;
180 else
181 {
182 last->next = r1;
183 last = r1;
184 }
185 r1 = r1->next;
186 }
187 }
188 if (r1 != NULL)
189 {
190 if (first == NULL)
191 first = r1;
192 else
193 last->next = r1;
194 }
195 else
196 {
197 lra_assert (r2 != NULL);
198 if (first == NULL)
199 first = r2;
200 else
201 last->next = r2;
202 }
203 return first;
204}
205
206/* Return TRUE if live ranges R1 and R2 intersect. */
207bool
208lra_intersected_live_ranges_p (lra_live_range_t r1, lra_live_range_t r2)
209{
210 /* Remember the live ranges are always kept ordered. */
211 while (r1 != NULL && r2 != NULL)
212 {
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;
219 }
220 return false;
221}
222
223/* The corresponding bitmaps of BB currently being processed. */
224static bitmap bb_killed_pseudos, bb_gen_pseudos;
225
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. */
231static void
232make_hard_regno_born (int regno, bool check_pic_pseudo_p ATTRIBUTE_UNUSED)
233{
234 unsigned int i;
235
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);
251}
252
253/* Process the death of hard register REGNO. This updates
254 hard_regs_live and START_DYING. */
255static void
256make_hard_regno_dead (int regno)
257{
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])
264 {
265 bitmap_clear_bit (bb_gen_pseudos, regno);
266 bitmap_set_bit (bb_killed_pseudos, regno);
267 }
268}
269
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. */
273static void
274mark_pseudo_live (int regno, int point)
275{
276 lra_live_range_t p;
277
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);
282
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);
289}
290
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. */
295static void
296mark_pseudo_dead (int regno, int point)
297{
298 lra_live_range_t p;
299
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)
305 {
306 p = lra_reg_info[regno].live_ranges;
307 lra_assert (p != NULL);
308 p->finish = point;
309 }
310}
311
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. */
316static bool
317mark_regno_live (int regno, machine_mode mode, int point)
318{
319 int last;
320 bool changed = false;
321
322 if (regno < FIRST_PSEUDO_REGISTER)
323 {
324 for (last = end_hard_regno (mode, regno); regno < last; regno++)
325 make_hard_regno_born (regno, false);
326 }
327 else
328 {
329 if (! sparseset_bit_p (pseudos_live, regno))
330 {
331 mark_pseudo_live (regno, point);
332 changed = true;
333 }
334 bitmap_set_bit (bb_gen_pseudos, regno);
335 }
336 return changed;
337}
338
339
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. */
343static bool
344mark_regno_dead (int regno, machine_mode mode, int point)
345{
346 int last;
347 bool changed = false;
348
349 if (regno < FIRST_PSEUDO_REGISTER)
350 {
351 for (last = end_hard_regno (mode, regno); regno < last; regno++)
352 make_hard_regno_dead (regno);
353 }
354 else
355 {
356 if (sparseset_bit_p (pseudos_live, regno))
357 {
358 mark_pseudo_dead (regno, point);
359 changed = true;
360 }
361 bitmap_clear_bit (bb_gen_pseudos, regno);
362 bitmap_set_bit (bb_killed_pseudos, regno);
363 }
364 return changed;
365}
366
367
368
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. */
373
374/* Structure describing local BB data used for pseudo
375 live-analysis. */
376struct bb_data_pseudos
377{
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. */
382};
383
384/* Array for all BB data. Indexed by the corresponding BB index. */
385typedef struct bb_data_pseudos *bb_data_t;
386
387/* All basic block data are referred through the following array. */
388static bb_data_t bb_data;
389
390/* Two small functions for access to the bb data. */
391static inline bb_data_t
392get_bb_data (basic_block bb)
393{
394 return &bb_data[(bb)->index];
395}
396
397static inline bb_data_t
398get_bb_data_by_index (int index)
399{
400 return &bb_data[index];
401}
402
403/* Bitmap with all hard regs. */
404static bitmap_head all_hard_regs_bitmap;
405
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:
409
410 bb.livein = (bb.liveout - bb.kill) OR bb.gen
411*/
412static bool
413live_trans_fun (int bb_index)
414{
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);
419
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);
423}
424
425/* The confluence function used by the DF equation solver to set up
426 live info for a block BB without predecessor. */
427static void
428live_con_fun_0 (basic_block bb)
429{
430 bitmap_and_into (df_get_live_out (bb), &all_hard_regs_bitmap);
431}
432
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:
436
437 bb.liveout = 0 for entry block | OR (livein of successors)
438 */
439static bool
440live_con_fun_n (edge e)
441{
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);
446
447 return bitmap_ior_and_compl_into (bb_liveout,
448 dest_livein, &all_hard_regs_bitmap);
449}
450
451/* Indexes of all function blocks. */
452static bitmap_head all_blocks;
453
454/* Allocate and initialize data needed for global pseudo live
455 analysis. */
456static void
457initiate_live_solver (void)
458{
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);
463
464 basic_block bb;
465 FOR_ALL_BB_FN (bb, cfun)
466 {
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);
472 }
473}
474
475/* Free all data needed for global pseudo live analysis. */
476static void
477finish_live_solver (void)
478{
479 basic_block bb;
480
481 bitmap_clear (&all_blocks);
482 FOR_ALL_BB_FN (bb, cfun)
483 {
484 bb_data_t bb_info = get_bb_data (bb);
485 bitmap_clear (&bb_info->killed_pseudos);
486 bitmap_clear (&bb_info->gen_pseudos);
487 }
488 free (bb_data);
489 bitmap_clear (&all_hard_regs_bitmap);
490}
491
492
493
494/* Insn currently scanned. */
495static rtx_insn *curr_insn;
496/* The insn data. */
497static lra_insn_recog_data_t curr_id;
498/* The insn static data. */
499static struct lra_static_insn_data *curr_static_id;
500
501/* Vec containing execution frequencies of program points. */
502static vec<int> point_freq_vec;
503
504/* The start of the above vector elements. */
505int *lra_point_freq;
506
507/* Increment the current program point POINT to the next point which has
508 execution frequency FREQ. */
509static void
510next_program_point (int &point, int freq)
511{
512 point_freq_vec.safe_push (freq);
513 lra_point_freq = point_freq_vec.address ();
514 point++;
515}
516
517/* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
518void
519lra_setup_reload_pseudo_preferenced_hard_reg (int regno,
520 int hard_regno, int profit)
521{
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)
528 {
529 lra_reg_info[regno].preferred_hard_regno1 = hard_regno;
530 lra_reg_info[regno].preferred_hard_regno_profit1 = profit;
531 }
532 else if (lra_reg_info[regno].preferred_hard_regno2 < 0
533 || profit > lra_reg_info[regno].preferred_hard_regno_profit2)
534 {
535 lra_reg_info[regno].preferred_hard_regno2 = hard_regno;
536 lra_reg_info[regno].preferred_hard_regno_profit2 = profit;
537 }
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))
545 {
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);
550 }
551 if (lra_dump_file != NULL)
552 {
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);
563 }
564}
565
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. */
569static inline void
570check_pseudos_live_through_calls (int regno,
571 HARD_REG_SET last_call_used_reg_set)
572{
573 int hr;
574
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);
580
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);
592}
593
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. */
597static inline bool
598reg_early_clobber_p (const struct lra_insn_reg *reg, int n_alt)
599{
600 return (reg->early_clobber
601 && (n_alt < 0 || TEST_BIT (reg->early_clobber_alts, n_alt)));
602}
603
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. */
612static bool
613process_bb_lives (basic_block bb, int &curr_point, bool dead_insn_p)
614{
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;
624
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);
634
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);
640
641 if (lra_dump_file != NULL)
642 fprintf (lra_dump_file, " BB %d\n", bb->index);
643
644 /* Scan the code of this basic block, noting which pseudos and hard
645 regs are born or die.
646
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)
654 {
655 bool call_p;
656 int n_alt, dst_regno, src_regno;
657 rtx set;
658 struct lra_insn_reg *reg;
659
660 if (!NONDEBUG_INSN_P (curr_insn))
661 continue;
662
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);
669
670 set = single_set (curr_insn);
671
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)))
680 {
681 bool remove_p = true;
682
683 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
684 if (reg->type != OP_IN && sparseset_bit_p (pseudos_live, reg->regno))
685 {
686 remove_p = false;
687 break;
688 }
689 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
690 if (reg->type != OP_IN)
691 {
692 remove_p = false;
693 break;
694 }
695 if (remove_p && ! volatile_refs_p (PATTERN (curr_insn)))
696 {
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)
703 {
704 /* There might be some debug insns with the pseudo. */
705 unsigned int uid;
706 rtx_insn *insn;
707
708 bitmap_copy (&temp_bitmap, &lra_reg_info[dst_regno].insn_bitmap);
709 EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap, 0, uid, bi)
710 {
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);
715 }
716 }
717 continue;
718 }
719 }
720
721 /* Update max ref width and hard reg usage. */
722 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
723 {
724 int i, regno = reg->regno;
725
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)
730 {
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]);
741 }
742 }
743
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)))
769 {
770 int hard_regno = -1, regno = -1;
771
772 if (dst_regno >= lra_constraint_new_regno_start
773 && src_regno >= lra_constraint_new_regno_start)
774 {
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);
782 }
783 else if (dst_regno >= lra_constraint_new_regno_start)
784 {
785 if ((hard_regno = src_regno) >= FIRST_PSEUDO_REGISTER)
786 hard_regno = reg_renumber[src_regno];
787 regno = dst_regno;
788 }
789 else if (src_regno >= lra_constraint_new_regno_start)
790 {
791 if ((hard_regno = dst_regno) >= FIRST_PSEUDO_REGISTER)
792 hard_regno = reg_renumber[dst_regno];
793 regno = src_regno;
794 }
795 if (regno >= 0 && hard_regno >= 0)
796 lra_setup_reload_pseudo_preferenced_hard_reg
797 (regno, hard_regno, freq);
798 }
799
800 sparseset_clear (start_living);
801
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;
807
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)
813 {
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);
819 }
820
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);
824
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);
830
831 sparseset_copy (unused_set, start_living);
832
833 sparseset_clear (start_dying);
834
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);
842
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);
847
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);
853
854 if (call_p)
855 {
856 if (! flag_ipa_ra)
857 COPY_HARD_REG_SET(last_call_used_reg_set, call_used_reg_set);
858 else
859 {
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);
863
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));
867
868 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
869 {
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);
875 }
876 COPY_HARD_REG_SET(last_call_used_reg_set, this_call_used_reg_set);
877 }
878
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);
886 }
887
888 /* Increment the current program point if we must. */
889 if (need_curr_point_incr)
890 next_program_point (curr_point, freq);
891
892 sparseset_clear (start_living);
893
894 need_curr_point_incr = false;
895
896 /* Mark each used value as live. */
897 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
898 if (reg->type == OP_IN)
899 {
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);
905 }
906
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);
910
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);
917
918 sparseset_and_compl (dead_set, start_living, start_dying);
919
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);
927
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 {
932 struct lra_insn_reg *reg2;
933
934 /* We can have early clobbered non-operand hard reg and
935 the same hard reg as an insn input. Don't make hard
936 reg dead before the insns. */
937 for (reg2 = curr_id->regs; reg2 != NULL; reg2 = reg2->next)
938 if (reg2->type != OP_OUT && reg2->regno == reg->regno)
939 break;
940 if (reg2 == NULL)
941 make_hard_regno_dead (reg->regno);
942 }
943
944 if (need_curr_point_incr)
945 next_program_point (curr_point, freq);
946
947 /* Update notes. */
948 for (link_loc = &REG_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
949 {
950 if (REG_NOTE_KIND (link) != REG_DEAD
951 && REG_NOTE_KIND (link) != REG_UNUSED)
952 ;
953 else if (REG_P (XEXP (link, 0)))
954 {
955 regno = REGNO (XEXP (link, 0));
956 if ((REG_NOTE_KIND (link) == REG_DEAD
957 && ! sparseset_bit_p (dead_set, regno))
958 || (REG_NOTE_KIND (link) == REG_UNUSED
959 && ! sparseset_bit_p (unused_set, regno)))
960 {
961 *link_loc = XEXP (link, 1);
962 continue;
963 }
964 if (REG_NOTE_KIND (link) == REG_DEAD)
965 sparseset_clear_bit (dead_set, regno);
966 else if (REG_NOTE_KIND (link) == REG_UNUSED)
967 sparseset_clear_bit (unused_set, regno);
968 }
969 link_loc = &XEXP (link, 1);
970 }
971 EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
972 add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
973 EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
974 add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
975 }
976
977 if (bb_has_eh_pred (bb))
978 for (j = 0; ; ++j)
979 {
980 unsigned int regno = EH_RETURN_DATA_REGNO (j);
981
982 if (regno == INVALID_REGNUM)
983 break;
984 make_hard_regno_born (regno, false);
985 }
986
987 /* Pseudos can't go in stack regs at the start of a basic block that
988 is reached by an abnormal edge. Likewise for call clobbered regs,
989 because caller-save, fixup_abnormal_edges and possibly the table
990 driven EH machinery are not quite ready to handle such pseudos
991 live across such edges. */
992 if (bb_has_abnormal_pred (bb))
993 {
994#ifdef STACK_REGS
995 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
996 lra_reg_info[px].no_stack_p = true;
997 for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
998 make_hard_regno_born (px, false);
999#endif
1000 /* No need to record conflicts for call clobbered regs if we
1001 have nonlocal labels around, as we don't ever try to
1002 allocate such regs in this case. */
1003 if (!cfun->has_nonlocal_label
1004 && has_abnormal_call_or_eh_pred_edge_p (bb))
1005 for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
1006 if (call_used_regs[px]
1007#ifdef REAL_PIC_OFFSET_TABLE_REGNUM
1008 /* We should create a conflict of PIC pseudo with PIC
1009 hard reg as PIC hard reg can have a wrong value after
1010 jump described by the abnormal edge. In this case we
1011 can not allocate PIC hard reg to PIC pseudo as PIC
1012 pseudo will also have a wrong value. */
1013 || (px == REAL_PIC_OFFSET_TABLE_REGNUM
1014 && pic_offset_table_rtx != NULL_RTX
1015 && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
1016#endif
1017 )
1018 make_hard_regno_born (px, false);
1019 }
1020
1021 bool live_change_p = false;
1022 /* Check if bb border live info was changed. */
1023 unsigned int live_pseudos_num = 0;
1024 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb),
1025 FIRST_PSEUDO_REGISTER, j, bi)
1026 {
1027 live_pseudos_num++;
1028 if (! sparseset_bit_p (pseudos_live, j))
1029 {
1030 live_change_p = true;
1031 if (lra_dump_file != NULL)
1032 fprintf (lra_dump_file,
1033 " r%d is removed as live at bb%d start\n", j, bb->index);
1034 break;
1035 }
1036 }
1037 if (! live_change_p
1038 && sparseset_cardinality (pseudos_live) != live_pseudos_num)
1039 {
1040 live_change_p = true;
1041 if (lra_dump_file != NULL)
1042 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
1043 if (! bitmap_bit_p (df_get_live_in (bb), j))
1044 fprintf (lra_dump_file,
1045 " r%d is added to live at bb%d start\n", j, bb->index);
1046 }
1047 /* See if we'll need an increment at the end of this basic block.
1048 An increment is needed if the PSEUDOS_LIVE set is not empty,
1049 to make sure the finish points are set up correctly. */
1050 need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0);
1051
1052 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
1053 mark_pseudo_dead (i, curr_point);
1054
1055 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
1056 {
1057 if (sparseset_cardinality (pseudos_live_through_calls) == 0)
1058 break;
1059 if (sparseset_bit_p (pseudos_live_through_calls, j))
1060 check_pseudos_live_through_calls (j, last_call_used_reg_set);
1061 }
1062
1063 if (need_curr_point_incr)
1064 next_program_point (curr_point, freq);
1065
1066 return live_change_p;
1067}
1068
1069/* Compress pseudo live ranges by removing program points where
1070 nothing happens. Complexity of many algorithms in LRA is linear
1071 function of program points number. To speed up the code we try to
1072 minimize the number of the program points here. */
1073static void
1074remove_some_program_points_and_update_live_ranges (void)
1075{
1076 unsigned i;
1077 int n, max_regno;
1078 int *map;
1079 lra_live_range_t r, prev_r, next_r;
1080 sbitmap_iterator sbi;
1081 bool born_p, dead_p, prev_born_p, prev_dead_p;
1082
1083 auto_sbitmap born (lra_live_max_point);
1084 auto_sbitmap dead (lra_live_max_point);
1085 bitmap_clear (born);
1086 bitmap_clear (dead);
1087 max_regno = max_reg_num ();
1088 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1089 {
1090 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1091 {
1092 lra_assert (r->start <= r->finish);
1093 bitmap_set_bit (born, r->start);
1094 bitmap_set_bit (dead, r->finish);
1095 }
1096 }
1097 auto_sbitmap born_or_dead (lra_live_max_point);
1098 bitmap_ior (born_or_dead, born, dead);
1099 map = XCNEWVEC (int, lra_live_max_point);
1100 n = -1;
1101 prev_born_p = prev_dead_p = false;
1102 EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1103 {
1104 born_p = bitmap_bit_p (born, i);
1105 dead_p = bitmap_bit_p (dead, i);
1106 if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1107 || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1108 {
1109 map[i] = n;
1110 lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
1111 }
1112 else
1113 {
1114 map[i] = ++n;
1115 lra_point_freq[n] = lra_point_freq[i];
1116 }
1117 prev_born_p = born_p;
1118 prev_dead_p = dead_p;
1119 }
1120 n++;
1121 if (lra_dump_file != NULL)
1122 fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1123 lra_live_max_point, n, 100 * n / lra_live_max_point);
1124 if (n < lra_live_max_point)
1125 {
1126 lra_live_max_point = n;
1127 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1128 {
1129 for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
1130 r != NULL;
1131 r = next_r)
1132 {
1133 next_r = r->next;
1134 r->start = map[r->start];
1135 r->finish = map[r->finish];
1136 if (prev_r == NULL || prev_r->start > r->finish + 1)
1137 {
1138 prev_r = r;
1139 continue;
1140 }
1141 prev_r->start = r->start;
1142 prev_r->next = next_r;
1143 lra_live_range_pool.remove (r);
1144 }
1145 }
1146 }
1147 free (map);
1148}
1149
1150/* Print live ranges R to file F. */
1151void
1152lra_print_live_range_list (FILE *f, lra_live_range_t r)
1153{
1154 for (; r != NULL; r = r->next)
1155 fprintf (f, " [%d..%d]", r->start, r->finish);
1156 fprintf (f, "\n");
1157}
1158
1159DEBUG_FUNCTION void
1160debug (lra_live_range &ref)
1161{
1162 lra_print_live_range_list (stderr, &ref);
1163}
1164
1165DEBUG_FUNCTION void
1166debug (lra_live_range *ptr)
1167{
1168 if (ptr)
1169 debug (*ptr);
1170 else
1171 fprintf (stderr, "<nil>\n");
1172}
1173
1174/* Print live ranges R to stderr. */
1175void
1176lra_debug_live_range_list (lra_live_range_t r)
1177{
1178 lra_print_live_range_list (stderr, r);
1179}
1180
1181/* Print live ranges of pseudo REGNO to file F. */
1182static void
1183print_pseudo_live_ranges (FILE *f, int regno)
1184{
1185 if (lra_reg_info[regno].live_ranges == NULL)
1186 return;
1187 fprintf (f, " r%d:", regno);
1188 lra_print_live_range_list (f, lra_reg_info[regno].live_ranges);
1189}
1190
1191/* Print live ranges of pseudo REGNO to stderr. */
1192void
1193lra_debug_pseudo_live_ranges (int regno)
1194{
1195 print_pseudo_live_ranges (stderr, regno);
1196}
1197
1198/* Print live ranges of all pseudos to file F. */
1199static void
1200print_live_ranges (FILE *f)
1201{
1202 int i, max_regno;
1203
1204 max_regno = max_reg_num ();
1205 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1206 print_pseudo_live_ranges (f, i);
1207}
1208
1209/* Print live ranges of all pseudos to stderr. */
1210void
1211lra_debug_live_ranges (void)
1212{
1213 print_live_ranges (stderr);
1214}
1215
1216/* Compress pseudo live ranges. */
1217static void
1218compress_live_ranges (void)
1219{
1220 remove_some_program_points_and_update_live_ranges ();
1221 if (lra_dump_file != NULL)
1222 {
1223 fprintf (lra_dump_file, "Ranges after the compression:\n");
1224 print_live_ranges (lra_dump_file);
1225 }
1226}
1227
1228
1229
1230/* The number of the current live range pass. */
1231int lra_live_range_iter;
1232
1233/* The function creates live ranges only for memory pseudos (or for
1234 all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos. It
1235 also does dead insn elimination if DEAD_INSN_P and global live
1236 analysis only for pseudos and only if the pseudo live info was
1237 changed on a BB border. Return TRUE if the live info was
1238 changed. */
1239static bool
1240lra_create_live_ranges_1 (bool all_p, bool dead_insn_p)
1241{
1242 basic_block bb;
1243 int i, hard_regno, max_regno = max_reg_num ();
1244 int curr_point;
1245 bool bb_live_change_p, have_referenced_pseudos = false;
1246
1247 timevar_push (TV_LRA_CREATE_LIVE_RANGES);
1248
1249 complete_info_p = all_p;
1250 if (lra_dump_file != NULL)
1251 fprintf (lra_dump_file,
1252 "\n********** Pseudo live ranges #%d: **********\n\n",
1253 ++lra_live_range_iter);
1254 memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage));
1255 for (i = 0; i < max_regno; i++)
1256 {
1257 lra_reg_info[i].live_ranges = NULL;
1258 CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1259 lra_reg_info[i].preferred_hard_regno1 = -1;
1260 lra_reg_info[i].preferred_hard_regno2 = -1;
1261 lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1262 lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1263#ifdef STACK_REGS
1264 lra_reg_info[i].no_stack_p = false;
1265#endif
1266 /* The biggest mode is already set but its value might be to
1267 conservative because of recent transformation. Here in this
1268 file we recalculate it again as it costs practically
1269 nothing. */
1270 if (i >= FIRST_PSEUDO_REGISTER && regno_reg_rtx[i] != NULL_RTX)
1271 lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
1272 else
1273 lra_reg_info[i].biggest_mode = VOIDmode;
1274 lra_reg_info[i].call_p = false;
1275 if (i >= FIRST_PSEUDO_REGISTER
1276 && lra_reg_info[i].nrefs != 0)
1277 {
1278 if ((hard_regno = reg_renumber[i]) >= 0)
1279 lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
1280 have_referenced_pseudos = true;
1281 }
1282 }
1283 lra_free_copies ();
1284
1285 /* Under some circumstances, we can have functions without pseudo
1286 registers. For such functions, lra_live_max_point will be 0,
1287 see e.g. PR55604, and there's nothing more to do for us here. */
1288 if (! have_referenced_pseudos)
1289 {
1290 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1291 return false;
1292 }
1293
1294 pseudos_live = sparseset_alloc (max_regno);
1295 pseudos_live_through_calls = sparseset_alloc (max_regno);
1296 pseudos_live_through_setjumps = sparseset_alloc (max_regno);
1297 start_living = sparseset_alloc (max_regno);
1298 start_dying = sparseset_alloc (max_regno);
1299 dead_set = sparseset_alloc (max_regno);
1300 unused_set = sparseset_alloc (max_regno);
1301 curr_point = 0;
1302 unsigned new_length = get_max_uid () * 2;
1303 point_freq_vec.truncate (0);
1304 point_freq_vec.reserve_exact (new_length);
1305 lra_point_freq = point_freq_vec.address ();
1306 auto_vec<int, 20> post_order_rev_cfg;
1307 inverted_post_order_compute (&post_order_rev_cfg);
1308 lra_assert (post_order_rev_cfg.length () == (unsigned) n_basic_blocks_for_fn (cfun));
1309 bb_live_change_p = false;
1310 for (i = post_order_rev_cfg.length () - 1; i >= 0; --i)
1311 {
1312 bb = BASIC_BLOCK_FOR_FN (cfun, post_order_rev_cfg[i]);
1313 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
1314 == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1315 continue;
1316 if (process_bb_lives (bb, curr_point, dead_insn_p))
1317 bb_live_change_p = true;
1318 }
1319 if (bb_live_change_p)
1320 {
1321 /* We need to clear pseudo live info as some pseudos can
1322 disappear, e.g. pseudos with used equivalences. */
1323 FOR_EACH_BB_FN (bb, cfun)
1324 {
1325 bitmap_clear_range (df_get_live_in (bb), FIRST_PSEUDO_REGISTER,
1326 max_regno - FIRST_PSEUDO_REGISTER);
1327 bitmap_clear_range (df_get_live_out (bb), FIRST_PSEUDO_REGISTER,
1328 max_regno - FIRST_PSEUDO_REGISTER);
1329 }
1330 /* As we did not change CFG since LRA start we can use
1331 DF-infrastructure solver to solve live data flow problem. */
1332 df_simple_dataflow
1333 (DF_BACKWARD, NULL, live_con_fun_0, live_con_fun_n,
1334 live_trans_fun, &all_blocks,
1335 df_get_postorder (DF_BACKWARD), df_get_n_blocks (DF_BACKWARD));
1336 if (lra_dump_file != NULL)
1337 {
1338 fprintf (lra_dump_file,
1339 "Global pseudo live data have been updated:\n");
1340 basic_block bb;
1341 FOR_EACH_BB_FN (bb, cfun)
1342 {
1343 bb_data_t bb_info = get_bb_data (bb);
1344 bitmap bb_livein = df_get_live_in (bb);
1345 bitmap bb_liveout = df_get_live_out (bb);
1346
1347 fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
1348 lra_dump_bitmap_with_title (" gen:",
1349 &bb_info->gen_pseudos, bb->index);
1350 lra_dump_bitmap_with_title (" killed:",
1351 &bb_info->killed_pseudos, bb->index);
1352 lra_dump_bitmap_with_title (" livein:", bb_livein, bb->index);
1353 lra_dump_bitmap_with_title (" liveout:", bb_liveout, bb->index);
1354 }
1355 }
1356 }
1357 lra_live_max_point = curr_point;
1358 if (lra_dump_file != NULL)
1359 print_live_ranges (lra_dump_file);
1360 /* Clean up. */
1361 sparseset_free (unused_set);
1362 sparseset_free (dead_set);
1363 sparseset_free (start_dying);
1364 sparseset_free (start_living);
1365 sparseset_free (pseudos_live_through_calls);
1366 sparseset_free (pseudos_live_through_setjumps);
1367 sparseset_free (pseudos_live);
1368 compress_live_ranges ();
1369 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1370 return bb_live_change_p;
1371}
1372
1373/* The main entry function creates live-ranges and other live info
1374 necessary for the assignment sub-pass. It uses
1375 lra_creates_live_ranges_1 -- so read comments for the
1376 function. */
1377void
1378lra_create_live_ranges (bool all_p, bool dead_insn_p)
1379{
1380 if (! lra_create_live_ranges_1 (all_p, dead_insn_p))
1381 return;
1382 if (lra_dump_file != NULL)
1383 fprintf (lra_dump_file, "Live info was changed -- recalculate it\n");
1384 /* Live info was changed on a bb border. It means that some info,
1385 e.g. about conflict regs, calls crossed, and live ranges may be
1386 wrong. We need this info for allocation. So recalculate it
1387 again but without removing dead insns which can change live info
1388 again. Repetitive live range calculations are expensive therefore
1389 we stop here as we already have correct info although some
1390 improvement in rare cases could be possible on this sub-pass if
1391 we do dead insn elimination again (still the improvement may
1392 happen later). */
1393 lra_clear_live_ranges ();
1394 bool res = lra_create_live_ranges_1 (all_p, false);
1395 lra_assert (! res);
1396}
1397
1398/* Finish all live ranges. */
1399void
1400lra_clear_live_ranges (void)
1401{
1402 int i;
1403
1404 for (i = 0; i < max_reg_num (); i++)
1405 free_live_range_list (lra_reg_info[i].live_ranges);
1406 point_freq_vec.release ();
1407}
1408
1409/* Initialize live ranges data once per function. */
1410void
1411lra_live_ranges_init (void)
1412{
1413 bitmap_initialize (&temp_bitmap, &reg_obstack);
1414 initiate_live_solver ();
1415}
1416
1417/* Finish live ranges data once per function. */
1418void
1419lra_live_ranges_finish (void)
1420{
1421 finish_live_solver ();
1422 bitmap_clear (&temp_bitmap);
1423 lra_live_range_pool.release ();
1424}
1425