]> git.ipfire.org Git - thirdparty/gcc.git/blame - gcc/lra-lives.c
projects / thirdparty / gcc.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Eliminate BASIC_BLOCK macro.
[thirdparty/gcc.git] / gcc / lra-lives.c
CommitLineData
c6a6cdaa 1/* Build live ranges for pseudos.
711789cc 2 Copyright (C) 2010-2013 Free Software Foundation, Inc.
c6a6cdaa 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 "function.h"
40#include "expr.h"
41#include "basic-block.h"
42#include "except.h"
43#include "df.h"
44#include "ira.h"
45#include "sparseset.h"
46#include "lra-int.h"
47
48/* Program points are enumerated by numbers from range
49 0..LRA_LIVE_MAX_POINT-1. There are approximately two times more
50 program points than insns. Program points are places in the
51 program where liveness info can be changed. In most general case
52 (there are more complicated cases too) some program points
53 correspond to places where input operand dies and other ones
54 correspond to places where output operands are born. */
55int lra_live_max_point;
56
57/* Accumulated execution frequency of all references for each hard
58 register. */
59int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER];
60
61/* A global flag whose true value says to build live ranges for all
62 pseudos, otherwise the live ranges only for pseudos got memory is
63 build. True value means also building copies and setting up hard
64 register preferences. The complete info is necessary only for the
65 assignment pass. The complete info is not needed for the
66 coalescing and spill passes. */
67static bool complete_info_p;
68
69/* Pseudos live at current point in the RTL scan. */
70static sparseset pseudos_live;
71
72/* Pseudos probably living through calls and setjumps. As setjump is
73 a call too, if a bit in PSEUDOS_LIVE_THROUGH_SETJUMPS is set up
74 then the corresponding bit in PSEUDOS_LIVE_THROUGH_CALLS is set up
75 too. These data are necessary for cases when only one subreg of a
76 multi-reg pseudo is set up after a call. So we decide it is
77 probably live when traversing bb backward. We are sure about
78 living when we see its usage or definition of the pseudo. */
79static sparseset pseudos_live_through_calls;
80static sparseset pseudos_live_through_setjumps;
81
82/* Set of hard regs (except eliminable ones) currently live. */
83static HARD_REG_SET hard_regs_live;
84
85/* Set of pseudos and hard registers start living/dying in the current
86 insn. These sets are used to update REG_DEAD and REG_UNUSED notes
87 in the insn. */
88static sparseset start_living, start_dying;
89
90/* Set of pseudos and hard regs dead and unused in the current
91 insn. */
92static sparseset unused_set, dead_set;
93
94/* Pool for pseudo live ranges. */
95static alloc_pool live_range_pool;
96
97/* Free live range LR. */
98static void
99free_live_range (lra_live_range_t lr)
100{
101 pool_free (live_range_pool, lr);
102}
103
104/* Free live range list LR. */
105static void
106free_live_range_list (lra_live_range_t lr)
107{
108 lra_live_range_t next;
109
110 while (lr != NULL)
111 {
112 next = lr->next;
113 free_live_range (lr);
114 lr = next;
115 }
116}
117
118/* Create and return pseudo live range with given attributes. */
119static lra_live_range_t
120create_live_range (int regno, int start, int finish, lra_live_range_t next)
121{
122 lra_live_range_t p;
123
124 p = (lra_live_range_t) pool_alloc (live_range_pool);
125 p->regno = regno;
126 p->start = start;
127 p->finish = finish;
128 p->next = next;
129 return p;
130}
131
132/* Copy live range R and return the result. */
133static lra_live_range_t
134copy_live_range (lra_live_range_t r)
135{
136 lra_live_range_t p;
137
138 p = (lra_live_range_t) pool_alloc (live_range_pool);
139 *p = *r;
140 return p;
141}
142
143/* Copy live range list given by its head R and return the result. */
144lra_live_range_t
145lra_copy_live_range_list (lra_live_range_t r)
146{
147 lra_live_range_t p, first, *chain;
148
149 first = NULL;
150 for (chain = &first; r != NULL; r = r->next)
151 {
152 p = copy_live_range (r);
153 *chain = p;
154 chain = &p->next;
155 }
156 return first;
157}
158
159/* Merge *non-intersected* ranges R1 and R2 and returns the result.
160 The function maintains the order of ranges and tries to minimize
161 size of the result range list. Ranges R1 and R2 may not be used
162 after the call. */
163lra_live_range_t
164lra_merge_live_ranges (lra_live_range_t r1, lra_live_range_t r2)
165{
166 lra_live_range_t first, last, temp;
167
168 if (r1 == NULL)
169 return r2;
170 if (r2 == NULL)
171 return r1;
172 for (first = last = NULL; r1 != NULL && r2 != NULL;)
173 {
174 if (r1->start < r2->start)
175 {
176 temp = r1;
177 r1 = r2;
178 r2 = temp;
179 }
180 if (r1->start == r2->finish + 1)
181 {
182 /* Joint ranges: merge r1 and r2 into r1. */
183 r1->start = r2->start;
184 temp = r2;
185 r2 = r2->next;
186 pool_free (live_range_pool, temp);
187 }
188 else
189 {
190 gcc_assert (r2->finish + 1 < r1->start);
191 /* Add r1 to the result. */
192 if (first == NULL)
193 first = last = r1;
194 else
195 {
196 last->next = r1;
197 last = r1;
198 }
199 r1 = r1->next;
200 }
201 }
202 if (r1 != NULL)
203 {
204 if (first == NULL)
205 first = r1;
206 else
207 last->next = r1;
208 }
209 else
210 {
211 lra_assert (r2 != NULL);
212 if (first == NULL)
213 first = r2;
214 else
215 last->next = r2;
216 }
217 return first;
218}
219
220/* Return TRUE if live ranges R1 and R2 intersect. */
221bool
222lra_intersected_live_ranges_p (lra_live_range_t r1, lra_live_range_t r2)
223{
224 /* Remember the live ranges are always kept ordered. */
225 while (r1 != NULL && r2 != NULL)
226 {
227 if (r1->start > r2->finish)
228 r1 = r1->next;
229 else if (r2->start > r1->finish)
230 r2 = r2->next;
231 else
232 return true;
233 }
234 return false;
235}
236
237/* The function processing birth of hard register REGNO. It updates
238 living hard regs, conflict hard regs for living pseudos, and
239 START_LIVING. */
240static void
241make_hard_regno_born (int regno)
242{
243 unsigned int i;
244
245 lra_assert (regno < FIRST_PSEUDO_REGISTER);
246 if (TEST_HARD_REG_BIT (lra_no_alloc_regs, regno)
247 || TEST_HARD_REG_BIT (hard_regs_live, regno))
248 return;
249 SET_HARD_REG_BIT (hard_regs_live, regno);
250 sparseset_set_bit (start_living, regno);
251 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
252 SET_HARD_REG_BIT (lra_reg_info[i].conflict_hard_regs, regno);
253}
254
255/* Process the death of hard register REGNO. This updates
256 hard_regs_live and START_DYING. */
257static void
258make_hard_regno_dead (int regno)
259{
260 lra_assert (regno < FIRST_PSEUDO_REGISTER);
261 if (TEST_HARD_REG_BIT (lra_no_alloc_regs, regno)
262 || ! TEST_HARD_REG_BIT (hard_regs_live, regno))
263 return;
264 sparseset_set_bit (start_dying, regno);
265 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
266}
267
268/* Mark pseudo REGNO as living at program point POINT, update conflicting
269 hard registers of the pseudo and START_LIVING, and start a new live
270 range for the pseudo corresponding to REGNO if it is necessary. */
271static void
272mark_pseudo_live (int regno, int point)
273{
274 lra_live_range_t p;
275
276 lra_assert (regno >= FIRST_PSEUDO_REGISTER);
277 lra_assert (! sparseset_bit_p (pseudos_live, regno));
278 sparseset_set_bit (pseudos_live, regno);
279 IOR_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs, hard_regs_live);
280
281 if ((complete_info_p || lra_get_regno_hard_regno (regno) < 0)
282 && ((p = lra_reg_info[regno].live_ranges) == NULL
283 || (p->finish != point && p->finish + 1 != point)))
284 lra_reg_info[regno].live_ranges
285 = create_live_range (regno, point, -1, p);
286 sparseset_set_bit (start_living, regno);
287}
288
289/* Mark pseudo REGNO as not living at program point POINT and update
290 START_DYING.
291 This finishes the current live range for the pseudo corresponding
292 to REGNO. */
293static void
294mark_pseudo_dead (int regno, int point)
295{
296 lra_live_range_t p;
297
298 lra_assert (regno >= FIRST_PSEUDO_REGISTER);
299 lra_assert (sparseset_bit_p (pseudos_live, regno));
300 sparseset_clear_bit (pseudos_live, regno);
301 sparseset_set_bit (start_dying, regno);
302 if (complete_info_p || lra_get_regno_hard_regno (regno) < 0)
303 {
304 p = lra_reg_info[regno].live_ranges;
305 lra_assert (p != NULL);
306 p->finish = point;
307 }
308}
309
310/* Mark register REGNO (pseudo or hard register) in MODE as live
311 at program point POINT.
312 Return TRUE if the liveness tracking sets were modified,
313 or FALSE if nothing changed. */
314static bool
315mark_regno_live (int regno, enum machine_mode mode, int point)
316{
317 int last;
318 bool changed = false;
319
320 if (regno < FIRST_PSEUDO_REGISTER)
321 {
322 for (last = regno + hard_regno_nregs[regno][mode];
323 regno < last;
324 regno++)
325 make_hard_regno_born (regno);
326 }
327 else if (! sparseset_bit_p (pseudos_live, regno))
328 {
329 mark_pseudo_live (regno, point);
330 changed = true;
331 }
332 return changed;
333}
334
335
336/* Mark register REGNO in MODE as dead at program point POINT.
337 Return TRUE if the liveness tracking sets were modified,
338 or FALSE if nothing changed. */
339static bool
340mark_regno_dead (int regno, enum machine_mode mode, int point)
341{
342 int last;
343 bool changed = false;
344
345 if (regno < FIRST_PSEUDO_REGISTER)
346 {
347 for (last = regno + hard_regno_nregs[regno][mode];
348 regno < last;
349 regno++)
350 make_hard_regno_dead (regno);
351 }
352 else if (sparseset_bit_p (pseudos_live, regno))
353 {
354 mark_pseudo_dead (regno, point);
355 changed = true;
356 }
357 return changed;
358}
359
360/* Insn currently scanned. */
361static rtx curr_insn;
362/* The insn data. */
363static lra_insn_recog_data_t curr_id;
364/* The insn static data. */
365static struct lra_static_insn_data *curr_static_id;
366
367/* Return true when one of the predecessor edges of BB is marked with
368 EDGE_ABNORMAL_CALL or EDGE_EH. */
369static bool
370bb_has_abnormal_call_pred (basic_block bb)
371{
372 edge e;
373 edge_iterator ei;
374
375 FOR_EACH_EDGE (e, ei, bb->preds)
376 {
377 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
378 return true;
379 }
380 return false;
381}
382
383/* Vec containing execution frequencies of program points. */
f1f41a6c 384static vec<int> point_freq_vec;
c6a6cdaa 385
386/* The start of the above vector elements. */
387int *lra_point_freq;
388
389/* Increment the current program point POINT to the next point which has
390 execution frequency FREQ. */
391static void
392next_program_point (int &point, int freq)
393{
f1f41a6c 394 point_freq_vec.safe_push (freq);
395 lra_point_freq = point_freq_vec.address ();
c6a6cdaa 396 point++;
397}
398
399/* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
400void
401lra_setup_reload_pseudo_preferenced_hard_reg (int regno,
402 int hard_regno, int profit)
403{
404 lra_assert (regno >= lra_constraint_new_regno_start);
405 if (lra_reg_info[regno].preferred_hard_regno1 == hard_regno)
406 lra_reg_info[regno].preferred_hard_regno_profit1 += profit;
407 else if (lra_reg_info[regno].preferred_hard_regno2 == hard_regno)
408 lra_reg_info[regno].preferred_hard_regno_profit2 += profit;
409 else if (lra_reg_info[regno].preferred_hard_regno1 < 0)
410 {
411 lra_reg_info[regno].preferred_hard_regno1 = hard_regno;
412 lra_reg_info[regno].preferred_hard_regno_profit1 = profit;
413 }
414 else if (lra_reg_info[regno].preferred_hard_regno2 < 0
415 || profit > lra_reg_info[regno].preferred_hard_regno_profit2)
416 {
417 lra_reg_info[regno].preferred_hard_regno2 = hard_regno;
418 lra_reg_info[regno].preferred_hard_regno_profit2 = profit;
419 }
420 else
421 return;
422 /* Keep the 1st hard regno as more profitable. */
423 if (lra_reg_info[regno].preferred_hard_regno1 >= 0
424 && lra_reg_info[regno].preferred_hard_regno2 >= 0
425 && (lra_reg_info[regno].preferred_hard_regno_profit2
426 > lra_reg_info[regno].preferred_hard_regno_profit1))
427 {
428 int temp;
429
430 temp = lra_reg_info[regno].preferred_hard_regno1;
431 lra_reg_info[regno].preferred_hard_regno1
432 = lra_reg_info[regno].preferred_hard_regno2;
433 lra_reg_info[regno].preferred_hard_regno2 = temp;
434 temp = lra_reg_info[regno].preferred_hard_regno_profit1;
435 lra_reg_info[regno].preferred_hard_regno_profit1
436 = lra_reg_info[regno].preferred_hard_regno_profit2;
437 lra_reg_info[regno].preferred_hard_regno_profit2 = temp;
438 }
439 if (lra_dump_file != NULL)
440 {
441 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
442 fprintf (lra_dump_file,
443 " Hard reg %d is preferable by r%d with profit %d\n",
444 hard_regno, regno,
445 lra_reg_info[regno].preferred_hard_regno_profit1);
446 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
447 fprintf (lra_dump_file,
448 " Hard reg %d is preferable by r%d with profit %d\n",
449 hard_regno, regno,
450 lra_reg_info[regno].preferred_hard_regno_profit2);
451 }
452}
453
454/* Check that REGNO living through calls and setjumps, set up conflict
455 regs, and clear corresponding bits in PSEUDOS_LIVE_THROUGH_CALLS and
456 PSEUDOS_LIVE_THROUGH_SETJUMPS. */
457static inline void
458check_pseudos_live_through_calls (int regno)
459{
a766a8b0 460 int hr;
461
c6a6cdaa 462 if (! sparseset_bit_p (pseudos_live_through_calls, regno))
463 return;
464 sparseset_clear_bit (pseudos_live_through_calls, regno);
465 IOR_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs,
466 call_used_reg_set);
a766a8b0 467
468 for (hr = 0; hr < FIRST_PSEUDO_REGISTER; hr++)
469 if (HARD_REGNO_CALL_PART_CLOBBERED (hr, PSEUDO_REGNO_MODE (regno)))
470 SET_HARD_REG_BIT (lra_reg_info[regno].conflict_hard_regs, hr);
c6a6cdaa 471#ifdef ENABLE_CHECKING
472 lra_reg_info[regno].call_p = true;
473#endif
474 if (! sparseset_bit_p (pseudos_live_through_setjumps, regno))
475 return;
476 sparseset_clear_bit (pseudos_live_through_setjumps, regno);
477 /* Don't allocate pseudos that cross setjmps or any call, if this
478 function receives a nonlocal goto. */
479 SET_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs);
480}
481
482/* Process insns of the basic block BB to update pseudo live ranges,
483 pseudo hard register conflicts, and insn notes. We do it on
484 backward scan of BB insns. CURR_POINT is the program point where
485 BB ends. The function updates this counter and returns in
486 CURR_POINT the program point where BB starts. */
487static void
488process_bb_lives (basic_block bb, int &curr_point)
489{
490 int i, regno, freq;
491 unsigned int j;
492 bitmap_iterator bi;
493 bitmap reg_live_out;
494 unsigned int px;
495 rtx link, *link_loc;
496 bool need_curr_point_incr;
497
498 reg_live_out = df_get_live_out (bb);
499 sparseset_clear (pseudos_live);
500 sparseset_clear (pseudos_live_through_calls);
501 sparseset_clear (pseudos_live_through_setjumps);
502 REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
503 AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
504 AND_COMPL_HARD_REG_SET (hard_regs_live, lra_no_alloc_regs);
505 EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
506 mark_pseudo_live (j, curr_point);
507
508 freq = REG_FREQ_FROM_BB (bb);
509
510 if (lra_dump_file != NULL)
511 fprintf (lra_dump_file, " BB %d\n", bb->index);
512
513 /* Scan the code of this basic block, noting which pseudos and hard
514 regs are born or die.
515
516 Note that this loop treats uninitialized values as live until the
517 beginning of the block. For example, if an instruction uses
518 (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
519 FOO will remain live until the beginning of the block. Likewise
520 if FOO is not set at all. This is unnecessarily pessimistic, but
521 it probably doesn't matter much in practice. */
522 FOR_BB_INSNS_REVERSE (bb, curr_insn)
523 {
524 bool call_p;
525 int dst_regno, src_regno;
526 rtx set;
527 struct lra_insn_reg *reg;
528
529 if (!NONDEBUG_INSN_P (curr_insn))
530 continue;
531
532 curr_id = lra_get_insn_recog_data (curr_insn);
533 curr_static_id = curr_id->insn_static_data;
534 if (lra_dump_file != NULL)
535 fprintf (lra_dump_file, " Insn %u: point = %d\n",
536 INSN_UID (curr_insn), curr_point);
537
538 /* Update max ref width and hard reg usage. */
539 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
540 if (reg->regno >= FIRST_PSEUDO_REGISTER
541 && (GET_MODE_SIZE (reg->biggest_mode)
542 > GET_MODE_SIZE (lra_reg_info[reg->regno].biggest_mode)))
543 lra_reg_info[reg->regno].biggest_mode = reg->biggest_mode;
544 else if (reg->regno < FIRST_PSEUDO_REGISTER)
545 lra_hard_reg_usage[reg->regno] += freq;
546
547 call_p = CALL_P (curr_insn);
548 if (complete_info_p
549 && (set = single_set (curr_insn)) != NULL_RTX
550 && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))
551 /* Check that source regno does not conflict with
552 destination regno to exclude most impossible
553 preferences. */
554 && ((((src_regno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
555 && ! sparseset_bit_p (pseudos_live, src_regno))
556 || (src_regno < FIRST_PSEUDO_REGISTER
557 && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno)))
558 /* It might be 'inheritance pseudo <- reload pseudo'. */
559 || (src_regno >= lra_constraint_new_regno_start
560 && ((int) REGNO (SET_DEST (set))
561 >= lra_constraint_new_regno_start))))
562 {
563 int hard_regno = -1, regno = -1;
564
565 dst_regno = REGNO (SET_DEST (set));
566 if (dst_regno >= lra_constraint_new_regno_start
567 && src_regno >= lra_constraint_new_regno_start)
568 lra_create_copy (dst_regno, src_regno, freq);
569 else if (dst_regno >= lra_constraint_new_regno_start)
570 {
571 if ((hard_regno = src_regno) >= FIRST_PSEUDO_REGISTER)
572 hard_regno = reg_renumber[src_regno];
573 regno = dst_regno;
574 }
575 else if (src_regno >= lra_constraint_new_regno_start)
576 {
577 if ((hard_regno = dst_regno) >= FIRST_PSEUDO_REGISTER)
578 hard_regno = reg_renumber[dst_regno];
579 regno = src_regno;
580 }
581 if (regno >= 0 && hard_regno >= 0)
582 lra_setup_reload_pseudo_preferenced_hard_reg
583 (regno, hard_regno, freq);
584 }
585
586 sparseset_clear (start_living);
587
588 /* Try to avoid unnecessary program point increments, this saves
589 a lot of time in remove_some_program_points_and_update_live_ranges.
590 We only need an increment if something becomes live or dies at this
591 program point. */
592 need_curr_point_incr = false;
593
594 /* Mark each defined value as live. We need to do this for
595 unused values because they still conflict with quantities
596 that are live at the time of the definition. */
597 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
598 if (reg->type != OP_IN)
599 {
600 need_curr_point_incr |= mark_regno_live (reg->regno,
601 reg->biggest_mode,
602 curr_point);
603 check_pseudos_live_through_calls (reg->regno);
604 }
605
606 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
607 if (reg->type != OP_IN)
608 make_hard_regno_born (reg->regno);
609
610 sparseset_copy (unused_set, start_living);
611
612 sparseset_clear (start_dying);
613
614 /* See which defined values die here. */
615 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
616 if (reg->type == OP_OUT && ! reg->early_clobber && ! reg->subreg_p)
617 need_curr_point_incr |= mark_regno_dead (reg->regno,
618 reg->biggest_mode,
619 curr_point);
620
621 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
622 if (reg->type == OP_OUT && ! reg->early_clobber && ! reg->subreg_p)
623 make_hard_regno_dead (reg->regno);
624
625 if (call_p)
626 {
627 sparseset_ior (pseudos_live_through_calls,
628 pseudos_live_through_calls, pseudos_live);
629 if (cfun->has_nonlocal_label
630 || find_reg_note (curr_insn, REG_SETJMP,
631 NULL_RTX) != NULL_RTX)
632 sparseset_ior (pseudos_live_through_setjumps,
633 pseudos_live_through_setjumps, pseudos_live);
634 }
635
636 /* Increment the current program point if we must. */
637 if (need_curr_point_incr)
638 next_program_point (curr_point, freq);
639
640 sparseset_clear (start_living);
641
642 need_curr_point_incr = false;
643
644 /* Mark each used value as live. */
645 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
646 if (reg->type == OP_IN)
647 {
648 need_curr_point_incr |= mark_regno_live (reg->regno,
649 reg->biggest_mode,
650 curr_point);
651 check_pseudos_live_through_calls (reg->regno);
652 }
653
654 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
655 if (reg->type == OP_IN)
656 make_hard_regno_born (reg->regno);
657
658 if (curr_id->arg_hard_regs != NULL)
659 /* Make argument hard registers live. */
660 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
661 make_hard_regno_born (regno);
662
663 sparseset_and_compl (dead_set, start_living, start_dying);
664
665 /* Mark early clobber outputs dead. */
666 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
667 if (reg->type == OP_OUT && reg->early_clobber && ! reg->subreg_p)
668 need_curr_point_incr = mark_regno_dead (reg->regno,
669 reg->biggest_mode,
670 curr_point);
671
672 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
673 if (reg->type == OP_OUT && reg->early_clobber && ! reg->subreg_p)
674 make_hard_regno_dead (reg->regno);
675
676 if (need_curr_point_incr)
677 next_program_point (curr_point, freq);
678
679 /* Update notes. */
680 for (link_loc = &REG_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
681 {
682 if (REG_NOTE_KIND (link) != REG_DEAD
683 && REG_NOTE_KIND (link) != REG_UNUSED)
684 ;
685 else if (REG_P (XEXP (link, 0)))
686 {
687 regno = REGNO (XEXP (link, 0));
688 if ((REG_NOTE_KIND (link) == REG_DEAD
689 && ! sparseset_bit_p (dead_set, regno))
690 || (REG_NOTE_KIND (link) == REG_UNUSED
691 && ! sparseset_bit_p (unused_set, regno)))
692 {
693 *link_loc = XEXP (link, 1);
694 continue;
695 }
696 if (REG_NOTE_KIND (link) == REG_DEAD)
697 sparseset_clear_bit (dead_set, regno);
698 else if (REG_NOTE_KIND (link) == REG_UNUSED)
699 sparseset_clear_bit (unused_set, regno);
700 }
701 link_loc = &XEXP (link, 1);
702 }
703 EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
704 add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
705 EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
706 add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
707 }
708
709#ifdef EH_RETURN_DATA_REGNO
710 if (bb_has_eh_pred (bb))
711 for (j = 0; ; ++j)
712 {
713 unsigned int regno = EH_RETURN_DATA_REGNO (j);
714
715 if (regno == INVALID_REGNUM)
716 break;
717 make_hard_regno_born (regno);
718 }
719#endif
720
721 /* Pseudos can't go in stack regs at the start of a basic block that
722 is reached by an abnormal edge. Likewise for call clobbered regs,
723 because caller-save, fixup_abnormal_edges and possibly the table
724 driven EH machinery are not quite ready to handle such pseudos
725 live across such edges. */
726 if (bb_has_abnormal_pred (bb))
727 {
728#ifdef STACK_REGS
729 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
730 lra_reg_info[px].no_stack_p = true;
731 for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
732 make_hard_regno_born (px);
733#endif
734 /* No need to record conflicts for call clobbered regs if we
735 have nonlocal labels around, as we don't ever try to
736 allocate such regs in this case. */
737 if (!cfun->has_nonlocal_label && bb_has_abnormal_call_pred (bb))
738 for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
739 if (call_used_regs[px])
740 make_hard_regno_born (px);
741 }
742
743 /* See if we'll need an increment at the end of this basic block.
744 An increment is needed if the PSEUDOS_LIVE set is not empty,
745 to make sure the finish points are set up correctly. */
746 need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0);
747
748 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
749 mark_pseudo_dead (i, curr_point);
750
751 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
752 {
753 if (sparseset_cardinality (pseudos_live_through_calls) == 0)
754 break;
755 if (sparseset_bit_p (pseudos_live_through_calls, j))
756 check_pseudos_live_through_calls (j);
757 }
758
759 if (need_curr_point_incr)
760 next_program_point (curr_point, freq);
761}
762
763/* Compress pseudo live ranges by removing program points where
764 nothing happens. Complexity of many algorithms in LRA is linear
765 function of program points number. To speed up the code we try to
766 minimize the number of the program points here. */
767static void
768remove_some_program_points_and_update_live_ranges (void)
769{
770 unsigned i;
771 int n, max_regno;
772 int *map;
773 lra_live_range_t r, prev_r, next_r;
774 sbitmap born_or_dead, born, dead;
775 sbitmap_iterator sbi;
776 bool born_p, dead_p, prev_born_p, prev_dead_p;
777
778 born = sbitmap_alloc (lra_live_max_point);
779 dead = sbitmap_alloc (lra_live_max_point);
53c5d9d4 780 bitmap_clear (born);
781 bitmap_clear (dead);
c6a6cdaa 782 max_regno = max_reg_num ();
783 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
784 {
785 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
786 {
787 lra_assert (r->start <= r->finish);
08b7917c 788 bitmap_set_bit (born, r->start);
789 bitmap_set_bit (dead, r->finish);
c6a6cdaa 790 }
791 }
792 born_or_dead = sbitmap_alloc (lra_live_max_point);
53c5d9d4 793 bitmap_ior (born_or_dead, born, dead);
c6a6cdaa 794 map = XCNEWVEC (int, lra_live_max_point);
795 n = -1;
796 prev_born_p = prev_dead_p = false;
0d211963 797 EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
c6a6cdaa 798 {
08b7917c 799 born_p = bitmap_bit_p (born, i);
800 dead_p = bitmap_bit_p (dead, i);
c6a6cdaa 801 if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
802 || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
803 {
804 map[i] = n;
805 lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
806 }
807 else
808 {
809 map[i] = ++n;
810 lra_point_freq[n] = lra_point_freq[i];
811 }
812 prev_born_p = born_p;
813 prev_dead_p = dead_p;
814 }
815 sbitmap_free (born_or_dead);
816 sbitmap_free (born);
817 sbitmap_free (dead);
818 n++;
819 if (lra_dump_file != NULL)
820 fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
821 lra_live_max_point, n, 100 * n / lra_live_max_point);
822 if (n < lra_live_max_point)
823 {
824 lra_live_max_point = n;
825 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
826 {
827 for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
828 r != NULL;
829 r = next_r)
830 {
831 next_r = r->next;
832 r->start = map[r->start];
833 r->finish = map[r->finish];
834 if (prev_r == NULL || prev_r->start > r->finish + 1)
835 {
836 prev_r = r;
837 continue;
838 }
839 prev_r->start = r->start;
840 prev_r->next = next_r;
841 free_live_range (r);
842 }
843 }
844 }
845 free (map);
846}
847
848/* Print live ranges R to file F. */
849void
850lra_print_live_range_list (FILE *f, lra_live_range_t r)
851{
852 for (; r != NULL; r = r->next)
853 fprintf (f, " [%d..%d]", r->start, r->finish);
854 fprintf (f, "\n");
855}
856
c7d89805 857DEBUG_FUNCTION void
858debug (lra_live_range &ref)
859{
860 lra_print_live_range_list (stderr, &ref);
861}
862
863DEBUG_FUNCTION void
864debug (lra_live_range *ptr)
865{
866 if (ptr)
867 debug (*ptr);
868 else
869 fprintf (stderr, "<nil>\n");
870}
871
c6a6cdaa 872/* Print live ranges R to stderr. */
873void
874lra_debug_live_range_list (lra_live_range_t r)
875{
876 lra_print_live_range_list (stderr, r);
877}
878
879/* Print live ranges of pseudo REGNO to file F. */
880static void
881print_pseudo_live_ranges (FILE *f, int regno)
882{
883 if (lra_reg_info[regno].live_ranges == NULL)
884 return;
885 fprintf (f, " r%d:", regno);
886 lra_print_live_range_list (f, lra_reg_info[regno].live_ranges);
887}
888
889/* Print live ranges of pseudo REGNO to stderr. */
890void
891lra_debug_pseudo_live_ranges (int regno)
892{
893 print_pseudo_live_ranges (stderr, regno);
894}
895
896/* Print live ranges of all pseudos to file F. */
897static void
898print_live_ranges (FILE *f)
899{
900 int i, max_regno;
901
902 max_regno = max_reg_num ();
903 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
904 print_pseudo_live_ranges (f, i);
905}
906
907/* Print live ranges of all pseudos to stderr. */
908void
909lra_debug_live_ranges (void)
910{
911 print_live_ranges (stderr);
912}
913
914/* Compress pseudo live ranges. */
915static void
916compress_live_ranges (void)
917{
918 remove_some_program_points_and_update_live_ranges ();
919 if (lra_dump_file != NULL)
920 {
921 fprintf (lra_dump_file, "Ranges after the compression:\n");
922 print_live_ranges (lra_dump_file);
923 }
924}
925
926/* The number of the current live range pass. */
927int lra_live_range_iter;
928
929/* The main entry function creates live ranges only for memory pseudos
930 (or for all ones if ALL_P), set up CONFLICT_HARD_REGS for
931 the pseudos. */
932void
933lra_create_live_ranges (bool all_p)
934{
935 basic_block bb;
936 int i, hard_regno, max_regno = max_reg_num ();
937 int curr_point;
dbb9a07c 938 bool have_referenced_pseudos = false;
c6a6cdaa 939
940 timevar_push (TV_LRA_CREATE_LIVE_RANGES);
941
942 complete_info_p = all_p;
943 if (lra_dump_file != NULL)
944 fprintf (lra_dump_file,
945 "\n********** Pseudo live ranges #%d: **********\n\n",
946 ++lra_live_range_iter);
947 memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage));
948 for (i = 0; i < max_regno; i++)
949 {
950 lra_reg_info[i].live_ranges = NULL;
951 CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
952 lra_reg_info[i].preferred_hard_regno1 = -1;
953 lra_reg_info[i].preferred_hard_regno2 = -1;
954 lra_reg_info[i].preferred_hard_regno_profit1 = 0;
955 lra_reg_info[i].preferred_hard_regno_profit2 = 0;
956#ifdef STACK_REGS
957 lra_reg_info[i].no_stack_p = false;
958#endif
fc8a0f60 959 /* The biggest mode is already set but its value might be to
960 conservative because of recent transformation. Here in this
961 file we recalculate it again as it costs practically
962 nothing. */
c6a6cdaa 963 if (regno_reg_rtx[i] != NULL_RTX)
964 lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
965 else
966 lra_reg_info[i].biggest_mode = VOIDmode;
967#ifdef ENABLE_CHECKING
968 lra_reg_info[i].call_p = false;
969#endif
970 if (i >= FIRST_PSEUDO_REGISTER
dbb9a07c 971 && lra_reg_info[i].nrefs != 0)
972 {
973 if ((hard_regno = reg_renumber[i]) >= 0)
974 lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
975 have_referenced_pseudos = true;
976 }
c6a6cdaa 977 }
978 lra_free_copies ();
dbb9a07c 979
980 /* Under some circumstances, we can have functions without pseudo
981 registers. For such functions, lra_live_max_point will be 0,
982 see e.g. PR55604, and there's nothing more to do for us here. */
983 if (! have_referenced_pseudos)
984 {
985 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
986 return;
987 }
988
c6a6cdaa 989 pseudos_live = sparseset_alloc (max_regno);
990 pseudos_live_through_calls = sparseset_alloc (max_regno);
991 pseudos_live_through_setjumps = sparseset_alloc (max_regno);
992 start_living = sparseset_alloc (max_regno);
993 start_dying = sparseset_alloc (max_regno);
994 dead_set = sparseset_alloc (max_regno);
995 unused_set = sparseset_alloc (max_regno);
996 curr_point = 0;
f1f41a6c 997 point_freq_vec.create (get_max_uid () * 2);
998 lra_point_freq = point_freq_vec.address ();
c6a6cdaa 999 int *post_order_rev_cfg = XNEWVEC (int, last_basic_block);
1000 int n_blocks_inverted = inverted_post_order_compute (post_order_rev_cfg);
a28770e1 1001 lra_assert (n_blocks_inverted == n_basic_blocks_for_fn (cfun));
c6a6cdaa 1002 for (i = n_blocks_inverted - 1; i >= 0; --i)
1003 {
f5a6b05f 1004 bb = BASIC_BLOCK_FOR_FN (cfun, post_order_rev_cfg[i]);
34154e27 1005 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
1006 == ENTRY_BLOCK_PTR_FOR_FN (cfun))
c6a6cdaa 1007 continue;
1008 process_bb_lives (bb, curr_point);
1009 }
1010 free (post_order_rev_cfg);
1011 lra_live_max_point = curr_point;
dbb9a07c 1012 gcc_checking_assert (lra_live_max_point > 0);
c6a6cdaa 1013 if (lra_dump_file != NULL)
1014 print_live_ranges (lra_dump_file);
1015 /* Clean up. */
1016 sparseset_free (unused_set);
1017 sparseset_free (dead_set);
1018 sparseset_free (start_dying);
1019 sparseset_free (start_living);
1020 sparseset_free (pseudos_live_through_calls);
1021 sparseset_free (pseudos_live_through_setjumps);
1022 sparseset_free (pseudos_live);
1023 compress_live_ranges ();
1024 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1025}
1026
1027/* Finish all live ranges. */
1028void
1029lra_clear_live_ranges (void)
1030{
1031 int i;
1032
1033 for (i = 0; i < max_reg_num (); i++)
1034 free_live_range_list (lra_reg_info[i].live_ranges);
f1f41a6c 1035 point_freq_vec.release ();
c6a6cdaa 1036}
1037
1038/* Initialize live ranges data once per function. */
1039void
1040lra_live_ranges_init (void)
1041{
1042 live_range_pool = create_alloc_pool ("live ranges",
1043 sizeof (struct lra_live_range), 100);
1044}
1045
1046/* Finish live ranges data once per function. */
1047void
1048lra_live_ranges_finish (void)
1049{
1050 free_alloc_pool (live_range_pool);
1051}
Mirror of https://gcc.gnu.org/git/gcc.git