Update gcc-50 to SVN version 221572
[dragonfly.git] / contrib / gcc-5.0 / gcc / lra-lives.c
CommitLineData
dda118e3
JM
1/* Build live ranges for pseudos.
2 Copyright (C) 2010-2015 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 "tm.h"
32#include "hard-reg-set.h"
33#include "rtl.h"
34#include "tm_p.h"
35#include "insn-config.h"
36#include "recog.h"
37#include "output.h"
38#include "regs.h"
39#include "hashtab.h"
40#include "hash-set.h"
41#include "vec.h"
42#include "machmode.h"
43#include "input.h"
44#include "function.h"
45#include "symtab.h"
46#include "flags.h"
47#include "statistics.h"
48#include "double-int.h"
49#include "real.h"
50#include "fixed-value.h"
51#include "alias.h"
52#include "wide-int.h"
53#include "inchash.h"
54#include "tree.h"
55#include "expmed.h"
56#include "dojump.h"
57#include "explow.h"
58#include "calls.h"
59#include "emit-rtl.h"
60#include "varasm.h"
61#include "stmt.h"
62#include "expr.h"
63#include "predict.h"
64#include "dominance.h"
65#include "cfg.h"
66#include "cfganal.h"
67#include "basic-block.h"
68#include "except.h"
69#include "df.h"
70#include "ira.h"
71#include "sparseset.h"
72#include "lra-int.h"
73
74/* Program points are enumerated by numbers from range
75 0..LRA_LIVE_MAX_POINT-1. There are approximately two times more
76 program points than insns. Program points are places in the
77 program where liveness info can be changed. In most general case
78 (there are more complicated cases too) some program points
79 correspond to places where input operand dies and other ones
80 correspond to places where output operands are born. */
81int lra_live_max_point;
82
83/* Accumulated execution frequency of all references for each hard
84 register. */
85int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER];
86
87/* A global flag whose true value says to build live ranges for all
88 pseudos, otherwise the live ranges only for pseudos got memory is
89 build. True value means also building copies and setting up hard
90 register preferences. The complete info is necessary only for the
91 assignment pass. The complete info is not needed for the
92 coalescing and spill passes. */
93static bool complete_info_p;
94
95/* Pseudos live at current point in the RTL scan. */
96static sparseset pseudos_live;
97
98/* Pseudos probably living through calls and setjumps. As setjump is
99 a call too, if a bit in PSEUDOS_LIVE_THROUGH_SETJUMPS is set up
100 then the corresponding bit in PSEUDOS_LIVE_THROUGH_CALLS is set up
101 too. These data are necessary for cases when only one subreg of a
102 multi-reg pseudo is set up after a call. So we decide it is
103 probably live when traversing bb backward. We are sure about
104 living when we see its usage or definition of the pseudo. */
105static sparseset pseudos_live_through_calls;
106static sparseset pseudos_live_through_setjumps;
107
108/* Set of hard regs (except eliminable ones) currently live. */
109static HARD_REG_SET hard_regs_live;
110
111/* Set of pseudos and hard registers start living/dying in the current
112 insn. These sets are used to update REG_DEAD and REG_UNUSED notes
113 in the insn. */
114static sparseset start_living, start_dying;
115
116/* Set of pseudos and hard regs dead and unused in the current
117 insn. */
118static sparseset unused_set, dead_set;
119
120/* Bitmap used for holding intermediate bitmap operation results. */
121static bitmap_head temp_bitmap;
122
123/* Pool for pseudo live ranges. */
124static alloc_pool live_range_pool;
125
126/* Free live range LR. */
127static void
128free_live_range (lra_live_range_t lr)
129{
130 pool_free (live_range_pool, lr);
131}
132
133/* Free live range list LR. */
134static void
135free_live_range_list (lra_live_range_t lr)
136{
137 lra_live_range_t next;
138
139 while (lr != NULL)
140 {
141 next = lr->next;
142 free_live_range (lr);
143 lr = next;
144 }
145}
146
147/* Create and return pseudo live range with given attributes. */
148static lra_live_range_t
149create_live_range (int regno, int start, int finish, lra_live_range_t next)
150{
151 lra_live_range_t p;
152
153 p = (lra_live_range_t) pool_alloc (live_range_pool);
154 p->regno = regno;
155 p->start = start;
156 p->finish = finish;
157 p->next = next;
158 return p;
159}
160
161/* Copy live range R and return the result. */
162static lra_live_range_t
163copy_live_range (lra_live_range_t r)
164{
165 lra_live_range_t p;
166
167 p = (lra_live_range_t) pool_alloc (live_range_pool);
168 *p = *r;
169 return p;
170}
171
172/* Copy live range list given by its head R and return the result. */
173lra_live_range_t
174lra_copy_live_range_list (lra_live_range_t r)
175{
176 lra_live_range_t p, first, *chain;
177
178 first = NULL;
179 for (chain = &first; r != NULL; r = r->next)
180 {
181 p = copy_live_range (r);
182 *chain = p;
183 chain = &p->next;
184 }
185 return first;
186}
187
188/* Merge *non-intersected* ranges R1 and R2 and returns the result.
189 The function maintains the order of ranges and tries to minimize
190 size of the result range list. Ranges R1 and R2 may not be used
191 after the call. */
192lra_live_range_t
193lra_merge_live_ranges (lra_live_range_t r1, lra_live_range_t r2)
194{
195 lra_live_range_t first, last, temp;
196
197 if (r1 == NULL)
198 return r2;
199 if (r2 == NULL)
200 return r1;
201 for (first = last = NULL; r1 != NULL && r2 != NULL;)
202 {
203 if (r1->start < r2->start)
204 {
205 temp = r1;
206 r1 = r2;
207 r2 = temp;
208 }
209 if (r1->start == r2->finish + 1)
210 {
211 /* Joint ranges: merge r1 and r2 into r1. */
212 r1->start = r2->start;
213 temp = r2;
214 r2 = r2->next;
215 pool_free (live_range_pool, temp);
216 }
217 else
218 {
219 gcc_assert (r2->finish + 1 < r1->start);
220 /* Add r1 to the result. */
221 if (first == NULL)
222 first = last = r1;
223 else
224 {
225 last->next = r1;
226 last = r1;
227 }
228 r1 = r1->next;
229 }
230 }
231 if (r1 != NULL)
232 {
233 if (first == NULL)
234 first = r1;
235 else
236 last->next = r1;
237 }
238 else
239 {
240 lra_assert (r2 != NULL);
241 if (first == NULL)
242 first = r2;
243 else
244 last->next = r2;
245 }
246 return first;
247}
248
249/* Return TRUE if live ranges R1 and R2 intersect. */
250bool
251lra_intersected_live_ranges_p (lra_live_range_t r1, lra_live_range_t r2)
252{
253 /* Remember the live ranges are always kept ordered. */
254 while (r1 != NULL && r2 != NULL)
255 {
256 if (r1->start > r2->finish)
257 r1 = r1->next;
258 else if (r2->start > r1->finish)
259 r2 = r2->next;
260 else
261 return true;
262 }
263 return false;
264}
265
266/* The function processing birth of hard register REGNO. It updates
267 living hard regs, START_LIVING, and conflict hard regs for living
268 pseudos. Conflict hard regs for the pic pseudo is not updated if
269 REGNO is REAL_PIC_OFFSET_TABLE_REGNUM and CHECK_PIC_PSEUDO_P is
270 true. */
271static void
272make_hard_regno_born (int regno, bool check_pic_pseudo_p ATTRIBUTE_UNUSED)
273{
274 unsigned int i;
275
276 lra_assert (regno < FIRST_PSEUDO_REGISTER);
277 if (TEST_HARD_REG_BIT (hard_regs_live, regno))
278 return;
279 SET_HARD_REG_BIT (hard_regs_live, regno);
280 sparseset_set_bit (start_living, regno);
281 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
282#ifdef REAL_PIC_OFFSET_TABLE_REGNUM
283 if (! check_pic_pseudo_p
284 || regno != REAL_PIC_OFFSET_TABLE_REGNUM
285 || pic_offset_table_rtx == NULL
286 || i != REGNO (pic_offset_table_rtx))
287#endif
288 SET_HARD_REG_BIT (lra_reg_info[i].conflict_hard_regs, regno);
289}
290
291/* Process the death of hard register REGNO. This updates
292 hard_regs_live and START_DYING. */
293static void
294make_hard_regno_dead (int regno)
295{
296 lra_assert (regno < FIRST_PSEUDO_REGISTER);
297 if (! TEST_HARD_REG_BIT (hard_regs_live, regno))
298 return;
299 sparseset_set_bit (start_dying, regno);
300 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
301}
302
303/* Mark pseudo REGNO as living at program point POINT, update conflicting
304 hard registers of the pseudo and START_LIVING, and start a new live
305 range for the pseudo corresponding to REGNO if it is necessary. */
306static void
307mark_pseudo_live (int regno, int point)
308{
309 lra_live_range_t p;
310
311 lra_assert (regno >= FIRST_PSEUDO_REGISTER);
312 lra_assert (! sparseset_bit_p (pseudos_live, regno));
313 sparseset_set_bit (pseudos_live, regno);
314 IOR_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs, hard_regs_live);
315
316 if ((complete_info_p || lra_get_regno_hard_regno (regno) < 0)
317 && ((p = lra_reg_info[regno].live_ranges) == NULL
318 || (p->finish != point && p->finish + 1 != point)))
319 lra_reg_info[regno].live_ranges
320 = create_live_range (regno, point, -1, p);
321 sparseset_set_bit (start_living, regno);
322}
323
324/* Mark pseudo REGNO as not living at program point POINT and update
325 START_DYING.
326 This finishes the current live range for the pseudo corresponding
327 to REGNO. */
328static void
329mark_pseudo_dead (int regno, int point)
330{
331 lra_live_range_t p;
332
333 lra_assert (regno >= FIRST_PSEUDO_REGISTER);
334 lra_assert (sparseset_bit_p (pseudos_live, regno));
335 sparseset_clear_bit (pseudos_live, regno);
336 sparseset_set_bit (start_dying, regno);
337 if (complete_info_p || lra_get_regno_hard_regno (regno) < 0)
338 {
339 p = lra_reg_info[regno].live_ranges;
340 lra_assert (p != NULL);
341 p->finish = point;
342 }
343}
344
345/* The corresponding bitmaps of BB currently being processed. */
346static bitmap bb_killed_pseudos, bb_gen_pseudos;
347
348/* Mark register REGNO (pseudo or hard register) in MODE as live at
349 program point POINT. Update BB_GEN_PSEUDOS.
350 Return TRUE if the liveness tracking sets were modified, or FALSE
351 if nothing changed. */
352static bool
353mark_regno_live (int regno, machine_mode mode, int point)
354{
355 int last;
356 bool changed = false;
357
358 if (regno < FIRST_PSEUDO_REGISTER)
359 {
360 for (last = regno + hard_regno_nregs[regno][mode];
361 regno < last;
362 regno++)
363 make_hard_regno_born (regno, false);
364 }
365 else
366 {
367 if (! sparseset_bit_p (pseudos_live, regno))
368 {
369 mark_pseudo_live (regno, point);
370 changed = true;
371 }
372 bitmap_set_bit (bb_gen_pseudos, regno);
373 }
374 return changed;
375}
376
377
378/* Mark register REGNO in MODE as dead at program point POINT. Update
379 BB_GEN_PSEUDOS and BB_KILLED_PSEUDOS. Return TRUE if the liveness
380 tracking sets were modified, or FALSE if nothing changed. */
381static bool
382mark_regno_dead (int regno, machine_mode mode, int point)
383{
384 int last;
385 bool changed = false;
386
387 if (regno < FIRST_PSEUDO_REGISTER)
388 {
389 for (last = regno + hard_regno_nregs[regno][mode];
390 regno < last;
391 regno++)
392 make_hard_regno_dead (regno);
393 }
394 else
395 {
396 if (sparseset_bit_p (pseudos_live, regno))
397 {
398 mark_pseudo_dead (regno, point);
399 changed = true;
400 }
401 bitmap_clear_bit (bb_gen_pseudos, regno);
402 bitmap_set_bit (bb_killed_pseudos, regno);
403 }
404 return changed;
405}
406
407\f
408
409/* This page contains code for making global live analysis of pseudos.
410 The code works only when pseudo live info is changed on a BB
411 border. That might be a consequence of some global transformations
412 in LRA, e.g. PIC pseudo reuse or rematerialization. */
413
414/* Structure describing local BB data used for pseudo
415 live-analysis. */
416struct bb_data_pseudos
417{
418 /* Basic block about which the below data are. */
419 basic_block bb;
420 bitmap_head killed_pseudos; /* pseudos killed in the BB. */
421 bitmap_head gen_pseudos; /* pseudos generated in the BB. */
422};
423
424/* Array for all BB data. Indexed by the corresponding BB index. */
425typedef struct bb_data_pseudos *bb_data_t;
426
427/* All basic block data are referred through the following array. */
428static bb_data_t bb_data;
429
430/* Two small functions for access to the bb data. */
431static inline bb_data_t
432get_bb_data (basic_block bb)
433{
434 return &bb_data[(bb)->index];
435}
436
437static inline bb_data_t
438get_bb_data_by_index (int index)
439{
440 return &bb_data[index];
441}
442
443/* Bitmap with all hard regs. */
444static bitmap_head all_hard_regs_bitmap;
445
446/* The transfer function used by the DF equation solver to propagate
447 live info through block with BB_INDEX according to the following
448 equation:
449
450 bb.livein = (bb.liveout - bb.kill) OR bb.gen
451*/
452static bool
453live_trans_fun (int bb_index)
454{
455 basic_block bb = get_bb_data_by_index (bb_index)->bb;
456 bitmap bb_liveout = df_get_live_out (bb);
457 bitmap bb_livein = df_get_live_in (bb);
458 bb_data_t bb_info = get_bb_data (bb);
459
460 bitmap_and_compl (&temp_bitmap, bb_liveout, &all_hard_regs_bitmap);
461 return bitmap_ior_and_compl (bb_livein, &bb_info->gen_pseudos,
462 &temp_bitmap, &bb_info->killed_pseudos);
463}
464
465/* The confluence function used by the DF equation solver to set up
466 live info for a block BB without predecessor. */
467static void
468live_con_fun_0 (basic_block bb)
469{
470 bitmap_and_into (df_get_live_out (bb), &all_hard_regs_bitmap);
471}
472
473/* The confluence function used by the DF equation solver to propagate
474 live info from successor to predecessor on edge E according to the
475 following equation:
476
477 bb.liveout = 0 for entry block | OR (livein of successors)
478 */
479static bool
480live_con_fun_n (edge e)
481{
482 basic_block bb = e->src;
483 basic_block dest = e->dest;
484 bitmap bb_liveout = df_get_live_out (bb);
485 bitmap dest_livein = df_get_live_in (dest);
486
487 return bitmap_ior_and_compl_into (bb_liveout,
488 dest_livein, &all_hard_regs_bitmap);
489}
490
491/* Indexes of all function blocks. */
492static bitmap_head all_blocks;
493
494/* Allocate and initialize data needed for global pseudo live
495 analysis. */
496static void
497initiate_live_solver (void)
498{
499 bitmap_initialize (&all_hard_regs_bitmap, &reg_obstack);
500 bitmap_set_range (&all_hard_regs_bitmap, 0, FIRST_PSEUDO_REGISTER);
501 bb_data = XNEWVEC (struct bb_data_pseudos, last_basic_block_for_fn (cfun));
502 bitmap_initialize (&all_blocks, &reg_obstack);
503
504 basic_block bb;
505 FOR_ALL_BB_FN (bb, cfun)
506 {
507 bb_data_t bb_info = get_bb_data (bb);
508 bb_info->bb = bb;
509 bitmap_initialize (&bb_info->killed_pseudos, &reg_obstack);
510 bitmap_initialize (&bb_info->gen_pseudos, &reg_obstack);
511 bitmap_set_bit (&all_blocks, bb->index);
512 }
513}
514
515/* Free all data needed for global pseudo live analysis. */
516static void
517finish_live_solver (void)
518{
519 basic_block bb;
520
521 bitmap_clear (&all_blocks);
522 FOR_ALL_BB_FN (bb, cfun)
523 {
524 bb_data_t bb_info = get_bb_data (bb);
525 bitmap_clear (&bb_info->killed_pseudos);
526 bitmap_clear (&bb_info->gen_pseudos);
527 }
528 free (bb_data);
529 bitmap_clear (&all_hard_regs_bitmap);
530}
531
532\f
533
534/* Insn currently scanned. */
535static rtx_insn *curr_insn;
536/* The insn data. */
537static lra_insn_recog_data_t curr_id;
538/* The insn static data. */
539static struct lra_static_insn_data *curr_static_id;
540
541/* Return true when one of the predecessor edges of BB is marked with
542 EDGE_ABNORMAL_CALL or EDGE_EH. */
543static bool
544bb_has_abnormal_call_pred (basic_block bb)
545{
546 edge e;
547 edge_iterator ei;
548
549 FOR_EACH_EDGE (e, ei, bb->preds)
550 {
551 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
552 return true;
553 }
554 return false;
555}
556
557/* Vec containing execution frequencies of program points. */
558static vec<int> point_freq_vec;
559
560/* The start of the above vector elements. */
561int *lra_point_freq;
562
563/* Increment the current program point POINT to the next point which has
564 execution frequency FREQ. */
565static void
566next_program_point (int &point, int freq)
567{
568 point_freq_vec.safe_push (freq);
569 lra_point_freq = point_freq_vec.address ();
570 point++;
571}
572
573/* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
574void
575lra_setup_reload_pseudo_preferenced_hard_reg (int regno,
576 int hard_regno, int profit)
577{
578 lra_assert (regno >= lra_constraint_new_regno_start);
579 if (lra_reg_info[regno].preferred_hard_regno1 == hard_regno)
580 lra_reg_info[regno].preferred_hard_regno_profit1 += profit;
581 else if (lra_reg_info[regno].preferred_hard_regno2 == hard_regno)
582 lra_reg_info[regno].preferred_hard_regno_profit2 += profit;
583 else if (lra_reg_info[regno].preferred_hard_regno1 < 0)
584 {
585 lra_reg_info[regno].preferred_hard_regno1 = hard_regno;
586 lra_reg_info[regno].preferred_hard_regno_profit1 = profit;
587 }
588 else if (lra_reg_info[regno].preferred_hard_regno2 < 0
589 || profit > lra_reg_info[regno].preferred_hard_regno_profit2)
590 {
591 lra_reg_info[regno].preferred_hard_regno2 = hard_regno;
592 lra_reg_info[regno].preferred_hard_regno_profit2 = profit;
593 }
594 else
595 return;
596 /* Keep the 1st hard regno as more profitable. */
597 if (lra_reg_info[regno].preferred_hard_regno1 >= 0
598 && lra_reg_info[regno].preferred_hard_regno2 >= 0
599 && (lra_reg_info[regno].preferred_hard_regno_profit2
600 > lra_reg_info[regno].preferred_hard_regno_profit1))
601 {
602 int temp;
603
604 temp = lra_reg_info[regno].preferred_hard_regno1;
605 lra_reg_info[regno].preferred_hard_regno1
606 = lra_reg_info[regno].preferred_hard_regno2;
607 lra_reg_info[regno].preferred_hard_regno2 = temp;
608 temp = lra_reg_info[regno].preferred_hard_regno_profit1;
609 lra_reg_info[regno].preferred_hard_regno_profit1
610 = lra_reg_info[regno].preferred_hard_regno_profit2;
611 lra_reg_info[regno].preferred_hard_regno_profit2 = temp;
612 }
613 if (lra_dump_file != NULL)
614 {
615 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
616 fprintf (lra_dump_file,
617 " Hard reg %d is preferable by r%d with profit %d\n",
618 hard_regno, regno,
619 lra_reg_info[regno].preferred_hard_regno_profit1);
620 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
621 fprintf (lra_dump_file,
622 " Hard reg %d is preferable by r%d with profit %d\n",
623 hard_regno, regno,
624 lra_reg_info[regno].preferred_hard_regno_profit2);
625 }
626}
627
628/* Check that REGNO living through calls and setjumps, set up conflict
629 regs, and clear corresponding bits in PSEUDOS_LIVE_THROUGH_CALLS and
630 PSEUDOS_LIVE_THROUGH_SETJUMPS. */
631static inline void
632check_pseudos_live_through_calls (int regno)
633{
634 int hr;
635
636 if (! sparseset_bit_p (pseudos_live_through_calls, regno))
637 return;
638 sparseset_clear_bit (pseudos_live_through_calls, regno);
639 IOR_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs,
38c0c85b 640 call_used_reg_set);
dda118e3
JM
641
642 for (hr = 0; hr < FIRST_PSEUDO_REGISTER; hr++)
643 if (HARD_REGNO_CALL_PART_CLOBBERED (hr, PSEUDO_REGNO_MODE (regno)))
644 SET_HARD_REG_BIT (lra_reg_info[regno].conflict_hard_regs, hr);
645#ifdef ENABLE_CHECKING
646 lra_reg_info[regno].call_p = true;
647#endif
648 if (! sparseset_bit_p (pseudos_live_through_setjumps, regno))
649 return;
650 sparseset_clear_bit (pseudos_live_through_setjumps, regno);
651 /* Don't allocate pseudos that cross setjmps or any call, if this
652 function receives a nonlocal goto. */
653 SET_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs);
654}
655
656/* Process insns of the basic block BB to update pseudo live ranges,
657 pseudo hard register conflicts, and insn notes. We do it on
658 backward scan of BB insns. CURR_POINT is the program point where
659 BB ends. The function updates this counter and returns in
660 CURR_POINT the program point where BB starts. The function also
661 does local live info updates and can delete the dead insns if
662 DEAD_INSN_P. It returns true if pseudo live info was
663 changed at the BB start. */
664static bool
665process_bb_lives (basic_block bb, int &curr_point, bool dead_insn_p)
666{
667 int i, regno, freq;
668 unsigned int j;
669 bitmap_iterator bi;
670 bitmap reg_live_out;
671 unsigned int px;
672 rtx_insn *next;
673 rtx link, *link_loc;
674 bool need_curr_point_incr;
675
676 reg_live_out = df_get_live_out (bb);
677 sparseset_clear (pseudos_live);
678 sparseset_clear (pseudos_live_through_calls);
679 sparseset_clear (pseudos_live_through_setjumps);
680 REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
681 AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
682 EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
683 mark_pseudo_live (j, curr_point);
684
685 bb_gen_pseudos = &get_bb_data (bb)->gen_pseudos;
686 bb_killed_pseudos = &get_bb_data (bb)->killed_pseudos;
687 bitmap_clear (bb_gen_pseudos);
688 bitmap_clear (bb_killed_pseudos);
689 freq = REG_FREQ_FROM_BB (bb);
690
691 if (lra_dump_file != NULL)
692 fprintf (lra_dump_file, " BB %d\n", bb->index);
693
694 /* Scan the code of this basic block, noting which pseudos and hard
695 regs are born or die.
696
697 Note that this loop treats uninitialized values as live until the
698 beginning of the block. For example, if an instruction uses
699 (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
700 FOO will remain live until the beginning of the block. Likewise
701 if FOO is not set at all. This is unnecessarily pessimistic, but
702 it probably doesn't matter much in practice. */
703 FOR_BB_INSNS_REVERSE_SAFE (bb, curr_insn, next)
704 {
705 bool call_p;
706 int dst_regno, src_regno;
707 rtx set;
708 struct lra_insn_reg *reg;
709
710 if (!NONDEBUG_INSN_P (curr_insn))
711 continue;
712
713 curr_id = lra_get_insn_recog_data (curr_insn);
714 curr_static_id = curr_id->insn_static_data;
715 if (lra_dump_file != NULL)
716 fprintf (lra_dump_file, " Insn %u: point = %d\n",
717 INSN_UID (curr_insn), curr_point);
718
719 set = single_set (curr_insn);
720
721 if (dead_insn_p && set != NULL_RTX
722 && REG_P (SET_DEST (set)) && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
723 && find_reg_note (curr_insn, REG_EH_REGION, NULL_RTX) == NULL_RTX
724 && ! may_trap_p (PATTERN (curr_insn))
725 /* Don't do premature remove of pic offset pseudo as we can
726 start to use it after some reload generation. */
727 && (pic_offset_table_rtx == NULL_RTX
728 || pic_offset_table_rtx != SET_DEST (set)))
729 {
730 bool remove_p = true;
731
732 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
733 if (reg->type != OP_IN && sparseset_bit_p (pseudos_live, reg->regno))
734 {
735 remove_p = false;
736 break;
737 }
738 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
739 if (reg->type != OP_IN)
740 {
741 remove_p = false;
742 break;
743 }
744 if (remove_p && ! volatile_refs_p (PATTERN (curr_insn)))
745 {
746 dst_regno = REGNO (SET_DEST (set));
747 if (lra_dump_file != NULL)
748 fprintf (lra_dump_file, " Deleting dead insn %u\n",
749 INSN_UID (curr_insn));
750 lra_set_insn_deleted (curr_insn);
751 if (lra_reg_info[dst_regno].nrefs == 0)
752 {
753 /* There might be some debug insns with the pseudo. */
754 unsigned int uid;
755 rtx_insn *insn;
756
757 bitmap_copy (&temp_bitmap, &lra_reg_info[dst_regno].insn_bitmap);
758 EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap, 0, uid, bi)
759 {
760 insn = lra_insn_recog_data[uid]->insn;
761 lra_substitute_pseudo_within_insn (insn, dst_regno,
762 SET_SRC (set));
763 lra_update_insn_regno_info (insn);
764 }
765 }
766 continue;
767 }
768 }
769
770 /* Update max ref width and hard reg usage. */
771 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
772 if (reg->regno >= FIRST_PSEUDO_REGISTER
773 && (GET_MODE_SIZE (reg->biggest_mode)
774 > GET_MODE_SIZE (lra_reg_info[reg->regno].biggest_mode)))
775 lra_reg_info[reg->regno].biggest_mode = reg->biggest_mode;
776 else if (reg->regno < FIRST_PSEUDO_REGISTER)
777 lra_hard_reg_usage[reg->regno] += freq;
778
779 call_p = CALL_P (curr_insn);
780 if (complete_info_p
781 && set != NULL_RTX
782 && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))
783 /* Check that source regno does not conflict with
784 destination regno to exclude most impossible
785 preferences. */
786 && ((((src_regno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
787 && ! sparseset_bit_p (pseudos_live, src_regno))
788 || (src_regno < FIRST_PSEUDO_REGISTER
789 && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno)))
790 /* It might be 'inheritance pseudo <- reload pseudo'. */
791 || (src_regno >= lra_constraint_new_regno_start
792 && ((int) REGNO (SET_DEST (set))
793 >= lra_constraint_new_regno_start)
794 /* Remember to skip special cases where src/dest regnos are
795 the same, e.g. insn SET pattern has matching constraints
796 like =r,0. */
797 && src_regno != (int) REGNO (SET_DEST (set)))))
798 {
799 int hard_regno = -1, regno = -1;
800
801 dst_regno = REGNO (SET_DEST (set));
802 if (dst_regno >= lra_constraint_new_regno_start
803 && src_regno >= lra_constraint_new_regno_start)
804 lra_create_copy (dst_regno, src_regno, freq);
805 else if (dst_regno >= lra_constraint_new_regno_start)
806 {
807 if ((hard_regno = src_regno) >= FIRST_PSEUDO_REGISTER)
808 hard_regno = reg_renumber[src_regno];
809 regno = dst_regno;
810 }
811 else if (src_regno >= lra_constraint_new_regno_start)
812 {
813 if ((hard_regno = dst_regno) >= FIRST_PSEUDO_REGISTER)
814 hard_regno = reg_renumber[dst_regno];
815 regno = src_regno;
816 }
817 if (regno >= 0 && hard_regno >= 0)
818 lra_setup_reload_pseudo_preferenced_hard_reg
819 (regno, hard_regno, freq);
820 }
821
822 sparseset_clear (start_living);
823
824 /* Try to avoid unnecessary program point increments, this saves
825 a lot of time in remove_some_program_points_and_update_live_ranges.
826 We only need an increment if something becomes live or dies at this
827 program point. */
828 need_curr_point_incr = false;
829
830 /* Mark each defined value as live. We need to do this for
831 unused values because they still conflict with quantities
832 that are live at the time of the definition. */
833 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
834 if (reg->type != OP_IN)
835 {
836 need_curr_point_incr
837 |= mark_regno_live (reg->regno, reg->biggest_mode,
838 curr_point);
839 check_pseudos_live_through_calls (reg->regno);
840 }
841
842 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
843 if (reg->type != OP_IN)
844 make_hard_regno_born (reg->regno, false);
845
846 sparseset_copy (unused_set, start_living);
847
848 sparseset_clear (start_dying);
849
850 /* See which defined values die here. */
851 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
852 if (reg->type == OP_OUT && ! reg->early_clobber && ! reg->subreg_p)
853 need_curr_point_incr
854 |= mark_regno_dead (reg->regno, reg->biggest_mode,
855 curr_point);
856
857 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
858 if (reg->type == OP_OUT && ! reg->early_clobber && ! reg->subreg_p)
859 make_hard_regno_dead (reg->regno);
860
861 if (call_p)
862 {
863 if (flag_ipa_ra)
864 {
865 HARD_REG_SET this_call_used_reg_set;
866 get_call_reg_set_usage (curr_insn, &this_call_used_reg_set,
867 call_used_reg_set);
868
869 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
870 IOR_HARD_REG_SET (lra_reg_info[j].actual_call_used_reg_set,
871 this_call_used_reg_set);
872 }
873
874 sparseset_ior (pseudos_live_through_calls,
875 pseudos_live_through_calls, pseudos_live);
876 if (cfun->has_nonlocal_label
877 || find_reg_note (curr_insn, REG_SETJMP,
878 NULL_RTX) != NULL_RTX)
879 sparseset_ior (pseudos_live_through_setjumps,
880 pseudos_live_through_setjumps, pseudos_live);
881 }
882
883 /* Increment the current program point if we must. */
884 if (need_curr_point_incr)
885 next_program_point (curr_point, freq);
886
887 sparseset_clear (start_living);
888
889 need_curr_point_incr = false;
890
891 /* Mark each used value as live. */
892 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
893 if (reg->type == OP_IN)
894 {
895 need_curr_point_incr
896 |= mark_regno_live (reg->regno, reg->biggest_mode,
897 curr_point);
898 check_pseudos_live_through_calls (reg->regno);
899 }
900
901 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
902 if (reg->type == OP_IN)
903 make_hard_regno_born (reg->regno, false);
904
905 if (curr_id->arg_hard_regs != NULL)
906 /* Make argument hard registers live. Don't create conflict
907 of used REAL_PIC_OFFSET_TABLE_REGNUM and the pic pseudo. */
908 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
909 make_hard_regno_born (regno, true);
910
911 sparseset_and_compl (dead_set, start_living, start_dying);
912
913 /* Mark early clobber outputs dead. */
914 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
915 if (reg->type == OP_OUT && reg->early_clobber && ! reg->subreg_p)
916 need_curr_point_incr
917 |= mark_regno_dead (reg->regno, reg->biggest_mode,
918 curr_point);
919
920 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
921 if (reg->type == OP_OUT && reg->early_clobber && ! reg->subreg_p)
922 make_hard_regno_dead (reg->regno);
923
924 if (need_curr_point_incr)
925 next_program_point (curr_point, freq);
926
927 /* Update notes. */
928 for (link_loc = &REG_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
929 {
930 if (REG_NOTE_KIND (link) != REG_DEAD
931 && REG_NOTE_KIND (link) != REG_UNUSED)
932 ;
933 else if (REG_P (XEXP (link, 0)))
934 {
935 regno = REGNO (XEXP (link, 0));
936 if ((REG_NOTE_KIND (link) == REG_DEAD
937 && ! sparseset_bit_p (dead_set, regno))
938 || (REG_NOTE_KIND (link) == REG_UNUSED
939 && ! sparseset_bit_p (unused_set, regno)))
940 {
941 *link_loc = XEXP (link, 1);
942 continue;
943 }
944 if (REG_NOTE_KIND (link) == REG_DEAD)
945 sparseset_clear_bit (dead_set, regno);
946 else if (REG_NOTE_KIND (link) == REG_UNUSED)
947 sparseset_clear_bit (unused_set, regno);
948 }
949 link_loc = &XEXP (link, 1);
950 }
951 EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
952 add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
953 EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
954 add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
955 }
956
957#ifdef EH_RETURN_DATA_REGNO
958 if (bb_has_eh_pred (bb))
959 for (j = 0; ; ++j)
960 {
961 unsigned int regno = EH_RETURN_DATA_REGNO (j);
962
963 if (regno == INVALID_REGNUM)
964 break;
965 make_hard_regno_born (regno, false);
966 }
967#endif
968
969 /* Pseudos can't go in stack regs at the start of a basic block that
970 is reached by an abnormal edge. Likewise for call clobbered regs,
971 because caller-save, fixup_abnormal_edges and possibly the table
972 driven EH machinery are not quite ready to handle such pseudos
973 live across such edges. */
974 if (bb_has_abnormal_pred (bb))
975 {
976#ifdef STACK_REGS
977 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
978 lra_reg_info[px].no_stack_p = true;
979 for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
980 make_hard_regno_born (px, false);
981#endif
982 /* No need to record conflicts for call clobbered regs if we
983 have nonlocal labels around, as we don't ever try to
984 allocate such regs in this case. */
985 if (!cfun->has_nonlocal_label && bb_has_abnormal_call_pred (bb))
986 for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
987 if (call_used_regs[px])
988 make_hard_regno_born (px, false);
989 }
990
991 bool live_change_p = false;
992 /* Check if bb border live info was changed. */
993 unsigned int live_pseudos_num = 0;
994 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb),
995 FIRST_PSEUDO_REGISTER, j, bi)
996 {
997 live_pseudos_num++;
998 if (! sparseset_bit_p (pseudos_live, j))
999 {
1000 live_change_p = true;
1001 if (lra_dump_file != NULL)
1002 fprintf (lra_dump_file,
1003 " r%d is removed as live at bb%d start\n", j, bb->index);
1004 break;
1005 }
1006 }
1007 if (! live_change_p
1008 && sparseset_cardinality (pseudos_live) != live_pseudos_num)
1009 {
1010 live_change_p = true;
1011 if (lra_dump_file != NULL)
1012 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
1013 if (! bitmap_bit_p (df_get_live_in (bb), j))
1014 fprintf (lra_dump_file,
1015 " r%d is added to live at bb%d start\n", j, bb->index);
1016 }
1017 /* See if we'll need an increment at the end of this basic block.
1018 An increment is needed if the PSEUDOS_LIVE set is not empty,
1019 to make sure the finish points are set up correctly. */
1020 need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0);
1021
1022 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
1023 mark_pseudo_dead (i, curr_point);
1024
1025 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
1026 {
1027 if (sparseset_cardinality (pseudos_live_through_calls) == 0)
1028 break;
1029 if (sparseset_bit_p (pseudos_live_through_calls, j))
1030 check_pseudos_live_through_calls (j);
1031 }
1032
1033 if (need_curr_point_incr)
1034 next_program_point (curr_point, freq);
1035
1036 return live_change_p;
1037}
1038
1039/* Compress pseudo live ranges by removing program points where
1040 nothing happens. Complexity of many algorithms in LRA is linear
1041 function of program points number. To speed up the code we try to
1042 minimize the number of the program points here. */
1043static void
1044remove_some_program_points_and_update_live_ranges (void)
1045{
1046 unsigned i;
1047 int n, max_regno;
1048 int *map;
1049 lra_live_range_t r, prev_r, next_r;
1050 sbitmap born_or_dead, born, dead;
1051 sbitmap_iterator sbi;
1052 bool born_p, dead_p, prev_born_p, prev_dead_p;
1053
1054 born = sbitmap_alloc (lra_live_max_point);
1055 dead = sbitmap_alloc (lra_live_max_point);
1056 bitmap_clear (born);
1057 bitmap_clear (dead);
1058 max_regno = max_reg_num ();
1059 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1060 {
1061 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1062 {
1063 lra_assert (r->start <= r->finish);
1064 bitmap_set_bit (born, r->start);
1065 bitmap_set_bit (dead, r->finish);
1066 }
1067 }
1068 born_or_dead = sbitmap_alloc (lra_live_max_point);
1069 bitmap_ior (born_or_dead, born, dead);
1070 map = XCNEWVEC (int, lra_live_max_point);
1071 n = -1;
1072 prev_born_p = prev_dead_p = false;
1073 EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1074 {
1075 born_p = bitmap_bit_p (born, i);
1076 dead_p = bitmap_bit_p (dead, i);
1077 if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1078 || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1079 {
1080 map[i] = n;
1081 lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
1082 }
1083 else
1084 {
1085 map[i] = ++n;
1086 lra_point_freq[n] = lra_point_freq[i];
1087 }
1088 prev_born_p = born_p;
1089 prev_dead_p = dead_p;
1090 }
1091 sbitmap_free (born_or_dead);
1092 sbitmap_free (born);
1093 sbitmap_free (dead);
1094 n++;
1095 if (lra_dump_file != NULL)
1096 fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1097 lra_live_max_point, n, 100 * n / lra_live_max_point);
1098 if (n < lra_live_max_point)
1099 {
1100 lra_live_max_point = n;
1101 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1102 {
1103 for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
1104 r != NULL;
1105 r = next_r)
1106 {
1107 next_r = r->next;
1108 r->start = map[r->start];
1109 r->finish = map[r->finish];
1110 if (prev_r == NULL || prev_r->start > r->finish + 1)
1111 {
1112 prev_r = r;
1113 continue;
1114 }
1115 prev_r->start = r->start;
1116 prev_r->next = next_r;
1117 free_live_range (r);
1118 }
1119 }
1120 }
1121 free (map);
1122}
1123
1124/* Print live ranges R to file F. */
1125void
1126lra_print_live_range_list (FILE *f, lra_live_range_t r)
1127{
1128 for (; r != NULL; r = r->next)
1129 fprintf (f, " [%d..%d]", r->start, r->finish);
1130 fprintf (f, "\n");
1131}
1132
1133DEBUG_FUNCTION void
1134debug (lra_live_range &ref)
1135{
1136 lra_print_live_range_list (stderr, &ref);
1137}
1138
1139DEBUG_FUNCTION void
1140debug (lra_live_range *ptr)
1141{
1142 if (ptr)
1143 debug (*ptr);
1144 else
1145 fprintf (stderr, "<nil>\n");
1146}
1147
1148/* Print live ranges R to stderr. */
1149void
1150lra_debug_live_range_list (lra_live_range_t r)
1151{
1152 lra_print_live_range_list (stderr, r);
1153}
1154
1155/* Print live ranges of pseudo REGNO to file F. */
1156static void
1157print_pseudo_live_ranges (FILE *f, int regno)
1158{
1159 if (lra_reg_info[regno].live_ranges == NULL)
1160 return;
1161 fprintf (f, " r%d:", regno);
1162 lra_print_live_range_list (f, lra_reg_info[regno].live_ranges);
1163}
1164
1165/* Print live ranges of pseudo REGNO to stderr. */
1166void
1167lra_debug_pseudo_live_ranges (int regno)
1168{
1169 print_pseudo_live_ranges (stderr, regno);
1170}
1171
1172/* Print live ranges of all pseudos to file F. */
1173static void
1174print_live_ranges (FILE *f)
1175{
1176 int i, max_regno;
1177
1178 max_regno = max_reg_num ();
1179 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1180 print_pseudo_live_ranges (f, i);
1181}
1182
1183/* Print live ranges of all pseudos to stderr. */
1184void
1185lra_debug_live_ranges (void)
1186{
1187 print_live_ranges (stderr);
1188}
1189
1190/* Compress pseudo live ranges. */
1191static void
1192compress_live_ranges (void)
1193{
1194 remove_some_program_points_and_update_live_ranges ();
1195 if (lra_dump_file != NULL)
1196 {
1197 fprintf (lra_dump_file, "Ranges after the compression:\n");
1198 print_live_ranges (lra_dump_file);
1199 }
1200}
1201
1202\f
1203
1204/* The number of the current live range pass. */
1205int lra_live_range_iter;
1206
1207/* The function creates live ranges only for memory pseudos (or for
1208 all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos. It
1209 also does dead insn elimination if DEAD_INSN_P and global live
1210 analysis only for pseudos and only if the pseudo live info was
1211 changed on a BB border. Return TRUE if the live info was
1212 changed. */
1213static bool
1214lra_create_live_ranges_1 (bool all_p, bool dead_insn_p)
1215{
1216 basic_block bb;
1217 int i, hard_regno, max_regno = max_reg_num ();
1218 int curr_point;
1219 bool bb_live_change_p, have_referenced_pseudos = false;
1220
1221 timevar_push (TV_LRA_CREATE_LIVE_RANGES);
1222
1223 complete_info_p = all_p;
1224 if (lra_dump_file != NULL)
1225 fprintf (lra_dump_file,
1226 "\n********** Pseudo live ranges #%d: **********\n\n",
1227 ++lra_live_range_iter);
1228 memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage));
1229 for (i = 0; i < max_regno; i++)
1230 {
1231 lra_reg_info[i].live_ranges = NULL;
1232 CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1233 lra_reg_info[i].preferred_hard_regno1 = -1;
1234 lra_reg_info[i].preferred_hard_regno2 = -1;
1235 lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1236 lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1237#ifdef STACK_REGS
1238 lra_reg_info[i].no_stack_p = false;
1239#endif
1240 /* The biggest mode is already set but its value might be to
1241 conservative because of recent transformation. Here in this
1242 file we recalculate it again as it costs practically
1243 nothing. */
1244 if (regno_reg_rtx[i] != NULL_RTX)
1245 lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
1246 else
1247 lra_reg_info[i].biggest_mode = VOIDmode;
1248#ifdef ENABLE_CHECKING
1249 lra_reg_info[i].call_p = false;
1250#endif
1251 if (i >= FIRST_PSEUDO_REGISTER
1252 && lra_reg_info[i].nrefs != 0)
1253 {
1254 if ((hard_regno = reg_renumber[i]) >= 0)
1255 lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
1256 have_referenced_pseudos = true;
1257 }
1258 }
1259 lra_free_copies ();
1260
1261 /* Under some circumstances, we can have functions without pseudo
1262 registers. For such functions, lra_live_max_point will be 0,
1263 see e.g. PR55604, and there's nothing more to do for us here. */
1264 if (! have_referenced_pseudos)
1265 {
1266 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1267 return false;
1268 }
1269
1270 pseudos_live = sparseset_alloc (max_regno);
1271 pseudos_live_through_calls = sparseset_alloc (max_regno);
1272 pseudos_live_through_setjumps = sparseset_alloc (max_regno);
1273 start_living = sparseset_alloc (max_regno);
1274 start_dying = sparseset_alloc (max_regno);
1275 dead_set = sparseset_alloc (max_regno);
1276 unused_set = sparseset_alloc (max_regno);
1277 curr_point = 0;
1278 point_freq_vec.create (get_max_uid () * 2);
1279 lra_point_freq = point_freq_vec.address ();
1280 int *post_order_rev_cfg = XNEWVEC (int, last_basic_block_for_fn (cfun));
1281 int n_blocks_inverted = inverted_post_order_compute (post_order_rev_cfg);
1282 lra_assert (n_blocks_inverted == n_basic_blocks_for_fn (cfun));
1283 bb_live_change_p = false;
1284 for (i = n_blocks_inverted - 1; i >= 0; --i)
1285 {
1286 bb = BASIC_BLOCK_FOR_FN (cfun, post_order_rev_cfg[i]);
1287 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
1288 == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1289 continue;
1290 if (process_bb_lives (bb, curr_point, dead_insn_p))
1291 bb_live_change_p = true;
1292 }
1293 if (bb_live_change_p)
1294 {
1295 /* We need to clear pseudo live info as some pseudos can
1296 disappear, e.g. pseudos with used equivalences. */
1297 FOR_EACH_BB_FN (bb, cfun)
1298 {
1299 bitmap_clear_range (df_get_live_in (bb), FIRST_PSEUDO_REGISTER,
1300 max_regno - FIRST_PSEUDO_REGISTER);
1301 bitmap_clear_range (df_get_live_out (bb), FIRST_PSEUDO_REGISTER,
1302 max_regno - FIRST_PSEUDO_REGISTER);
1303 }
1304 /* As we did not change CFG since LRA start we can use
1305 DF-infrastructure solver to solve live data flow problem. */
1306 df_simple_dataflow
1307 (DF_BACKWARD, NULL, live_con_fun_0, live_con_fun_n,
1308 live_trans_fun, &all_blocks,
1309 df_get_postorder (DF_BACKWARD), df_get_n_blocks (DF_BACKWARD));
1310 if (lra_dump_file != NULL)
1311 {
1312 fprintf (lra_dump_file,
1313 "Global pseudo live data have been updated:\n");
1314 basic_block bb;
1315 FOR_EACH_BB_FN (bb, cfun)
1316 {
1317 bb_data_t bb_info = get_bb_data (bb);
1318 bitmap bb_livein = df_get_live_in (bb);
1319 bitmap bb_liveout = df_get_live_out (bb);
1320
1321 fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
1322 lra_dump_bitmap_with_title (" gen:",
1323 &bb_info->gen_pseudos, bb->index);
1324 lra_dump_bitmap_with_title (" killed:",
1325 &bb_info->killed_pseudos, bb->index);
1326 lra_dump_bitmap_with_title (" livein:", bb_livein, bb->index);
1327 lra_dump_bitmap_with_title (" liveout:", bb_liveout, bb->index);
1328 }
1329 }
1330 }
1331 free (post_order_rev_cfg);
1332 lra_live_max_point = curr_point;
1333 if (lra_dump_file != NULL)
1334 print_live_ranges (lra_dump_file);
1335 /* Clean up. */
1336 sparseset_free (unused_set);
1337 sparseset_free (dead_set);
1338 sparseset_free (start_dying);
1339 sparseset_free (start_living);
1340 sparseset_free (pseudos_live_through_calls);
1341 sparseset_free (pseudos_live_through_setjumps);
1342 sparseset_free (pseudos_live);
1343 compress_live_ranges ();
1344 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1345 return bb_live_change_p;
1346}
1347
1348/* The main entry function creates live-ranges and other live info
1349 necessary for the assignment sub-pass. It uses
1350 lra_creates_live_ranges_1 -- so read comments for the
1351 function. */
1352void
1353lra_create_live_ranges (bool all_p, bool dead_insn_p)
1354{
1355 if (! lra_create_live_ranges_1 (all_p, dead_insn_p))
1356 return;
1357 if (lra_dump_file != NULL)
1358 fprintf (lra_dump_file, "Live info was changed -- recalculate it\n");
1359 /* Live info was changed on a bb border. It means that some info,
1360 e.g. about conflict regs, calls crossed, and live ranges may be
1361 wrong. We need this info for allocation. So recalculate it
1362 again but without removing dead insns which can change live info
1363 again. Repetitive live range calculations are expensive therefore
1364 we stop here as we already have correct info although some
1365 improvement in rare cases could be possible on this sub-pass if
1366 we do dead insn elimination again (still the improvement may
1367 happen later). */
1368 lra_clear_live_ranges ();
1369 bool res = lra_create_live_ranges_1 (all_p, false);
1370 lra_assert (! res);
1371}
1372
1373/* Finish all live ranges. */
1374void
1375lra_clear_live_ranges (void)
1376{
1377 int i;
1378
1379 for (i = 0; i < max_reg_num (); i++)
1380 free_live_range_list (lra_reg_info[i].live_ranges);
1381 point_freq_vec.release ();
1382}
1383
1384/* Initialize live ranges data once per function. */
1385void
1386lra_live_ranges_init (void)
1387{
1388 live_range_pool = create_alloc_pool ("live ranges",
1389 sizeof (struct lra_live_range), 100);
1390 bitmap_initialize (&temp_bitmap, &reg_obstack);
1391 initiate_live_solver ();
1392}
1393
1394/* Finish live ranges data once per function. */
1395void
1396lra_live_ranges_finish (void)
1397{
1398 finish_live_solver ();
1399 bitmap_clear (&temp_bitmap);
1400 free_alloc_pool (live_range_pool);
1401}