Daily bump.
[official-gcc.git] / gcc / lra-lives.c
blob8444adee6d8d3d11080c1a2b2fcad8c759f4a8df
1 /* Build live ranges for pseudos.
2 Copyright (C) 2010-2014 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
22 /* This file contains code to build pseudo live-ranges (analogous
23 structures used in IRA, so read comments about the live-ranges
24 there) and other info necessary for other passes to assign
25 hard-registers to pseudos, coalesce the spilled pseudos, and assign
26 stack memory slots to spilled pseudos. */
28 #include "config.h"
29 #include "system.h"
30 #include "coretypes.h"
31 #include "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"
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. */
55 int lra_live_max_point;
57 /* Accumulated execution frequency of all references for each hard
58 register. */
59 int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER];
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. */
67 static bool complete_info_p;
69 /* Pseudos live at current point in the RTL scan. */
70 static sparseset pseudos_live;
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. */
79 static sparseset pseudos_live_through_calls;
80 static sparseset pseudos_live_through_setjumps;
82 /* Set of hard regs (except eliminable ones) currently live. */
83 static HARD_REG_SET hard_regs_live;
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. */
88 static sparseset start_living, start_dying;
90 /* Set of pseudos and hard regs dead and unused in the current
91 insn. */
92 static sparseset unused_set, dead_set;
94 /* Pool for pseudo live ranges. */
95 static alloc_pool live_range_pool;
97 /* Free live range LR. */
98 static void
99 free_live_range (lra_live_range_t lr)
101 pool_free (live_range_pool, lr);
104 /* Free live range list LR. */
105 static void
106 free_live_range_list (lra_live_range_t lr)
108 lra_live_range_t next;
110 while (lr != NULL)
112 next = lr->next;
113 free_live_range (lr);
114 lr = next;
118 /* Create and return pseudo live range with given attributes. */
119 static lra_live_range_t
120 create_live_range (int regno, int start, int finish, lra_live_range_t next)
122 lra_live_range_t p;
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;
132 /* Copy live range R and return the result. */
133 static lra_live_range_t
134 copy_live_range (lra_live_range_t r)
136 lra_live_range_t p;
138 p = (lra_live_range_t) pool_alloc (live_range_pool);
139 *p = *r;
140 return p;
143 /* Copy live range list given by its head R and return the result. */
144 lra_live_range_t
145 lra_copy_live_range_list (lra_live_range_t r)
147 lra_live_range_t p, first, *chain;
149 first = NULL;
150 for (chain = &first; r != NULL; r = r->next)
152 p = copy_live_range (r);
153 *chain = p;
154 chain = &p->next;
156 return first;
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. */
163 lra_live_range_t
164 lra_merge_live_ranges (lra_live_range_t r1, lra_live_range_t r2)
166 lra_live_range_t first, last, temp;
168 if (r1 == NULL)
169 return r2;
170 if (r2 == NULL)
171 return r1;
172 for (first = last = NULL; r1 != NULL && r2 != NULL;)
174 if (r1->start < r2->start)
176 temp = r1;
177 r1 = r2;
178 r2 = temp;
180 if (r1->start == r2->finish + 1)
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);
188 else
190 gcc_assert (r2->finish + 1 < r1->start);
191 /* Add r1 to the result. */
192 if (first == NULL)
193 first = last = r1;
194 else
196 last->next = r1;
197 last = r1;
199 r1 = r1->next;
202 if (r1 != NULL)
204 if (first == NULL)
205 first = r1;
206 else
207 last->next = r1;
209 else
211 lra_assert (r2 != NULL);
212 if (first == NULL)
213 first = r2;
214 else
215 last->next = r2;
217 return first;
220 /* Return TRUE if live ranges R1 and R2 intersect. */
221 bool
222 lra_intersected_live_ranges_p (lra_live_range_t r1, lra_live_range_t r2)
224 /* Remember the live ranges are always kept ordered. */
225 while (r1 != NULL && r2 != NULL)
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;
234 return false;
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. */
240 static void
241 make_hard_regno_born (int regno)
243 unsigned int i;
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);
255 /* Process the death of hard register REGNO. This updates
256 hard_regs_live and START_DYING. */
257 static void
258 make_hard_regno_dead (int regno)
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);
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. */
271 static void
272 mark_pseudo_live (int regno, int point)
274 lra_live_range_t p;
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);
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);
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. */
293 static void
294 mark_pseudo_dead (int regno, int point)
296 lra_live_range_t p;
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)
304 p = lra_reg_info[regno].live_ranges;
305 lra_assert (p != NULL);
306 p->finish = point;
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. */
314 static bool
315 mark_regno_live (int regno, enum machine_mode mode, int point)
317 int last;
318 bool changed = false;
320 if (regno < FIRST_PSEUDO_REGISTER)
322 for (last = regno + hard_regno_nregs[regno][mode];
323 regno < last;
324 regno++)
325 make_hard_regno_born (regno);
327 else if (! sparseset_bit_p (pseudos_live, regno))
329 mark_pseudo_live (regno, point);
330 changed = true;
332 return changed;
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. */
339 static bool
340 mark_regno_dead (int regno, enum machine_mode mode, int point)
342 int last;
343 bool changed = false;
345 if (regno < FIRST_PSEUDO_REGISTER)
347 for (last = regno + hard_regno_nregs[regno][mode];
348 regno < last;
349 regno++)
350 make_hard_regno_dead (regno);
352 else if (sparseset_bit_p (pseudos_live, regno))
354 mark_pseudo_dead (regno, point);
355 changed = true;
357 return changed;
360 /* Insn currently scanned. */
361 static rtx curr_insn;
362 /* The insn data. */
363 static lra_insn_recog_data_t curr_id;
364 /* The insn static data. */
365 static struct lra_static_insn_data *curr_static_id;
367 /* Return true when one of the predecessor edges of BB is marked with
368 EDGE_ABNORMAL_CALL or EDGE_EH. */
369 static bool
370 bb_has_abnormal_call_pred (basic_block bb)
372 edge e;
373 edge_iterator ei;
375 FOR_EACH_EDGE (e, ei, bb->preds)
377 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
378 return true;
380 return false;
383 /* Vec containing execution frequencies of program points. */
384 static vec<int> point_freq_vec;
386 /* The start of the above vector elements. */
387 int *lra_point_freq;
389 /* Increment the current program point POINT to the next point which has
390 execution frequency FREQ. */
391 static void
392 next_program_point (int &point, int freq)
394 point_freq_vec.safe_push (freq);
395 lra_point_freq = point_freq_vec.address ();
396 point++;
399 /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
400 void
401 lra_setup_reload_pseudo_preferenced_hard_reg (int regno,
402 int hard_regno, int profit)
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)
411 lra_reg_info[regno].preferred_hard_regno1 = hard_regno;
412 lra_reg_info[regno].preferred_hard_regno_profit1 = profit;
414 else if (lra_reg_info[regno].preferred_hard_regno2 < 0
415 || profit > lra_reg_info[regno].preferred_hard_regno_profit2)
417 lra_reg_info[regno].preferred_hard_regno2 = hard_regno;
418 lra_reg_info[regno].preferred_hard_regno_profit2 = profit;
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))
428 int temp;
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;
439 if (lra_dump_file != NULL)
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);
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. */
457 static inline void
458 check_pseudos_live_through_calls (int regno)
460 int hr;
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);
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);
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);
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. */
487 static void
488 process_bb_lives (basic_block bb, int &curr_point)
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;
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);
508 freq = REG_FREQ_FROM_BB (bb);
510 if (lra_dump_file != NULL)
511 fprintf (lra_dump_file, " BB %d\n", bb->index);
513 /* Scan the code of this basic block, noting which pseudos and hard
514 regs are born or die.
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)
524 bool call_p;
525 int dst_regno, src_regno;
526 rtx set;
527 struct lra_insn_reg *reg;
529 if (!NONDEBUG_INSN_P (curr_insn))
530 continue;
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);
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;
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))))
563 int hard_regno = -1, regno = -1;
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)
571 if ((hard_regno = src_regno) >= FIRST_PSEUDO_REGISTER)
572 hard_regno = reg_renumber[src_regno];
573 regno = dst_regno;
575 else if (src_regno >= lra_constraint_new_regno_start)
577 if ((hard_regno = dst_regno) >= FIRST_PSEUDO_REGISTER)
578 hard_regno = reg_renumber[dst_regno];
579 regno = src_regno;
581 if (regno >= 0 && hard_regno >= 0)
582 lra_setup_reload_pseudo_preferenced_hard_reg
583 (regno, hard_regno, freq);
586 sparseset_clear (start_living);
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;
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)
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);
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);
610 sparseset_copy (unused_set, start_living);
612 sparseset_clear (start_dying);
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);
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);
625 if (call_p)
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);
636 /* Increment the current program point if we must. */
637 if (need_curr_point_incr)
638 next_program_point (curr_point, freq);
640 sparseset_clear (start_living);
642 need_curr_point_incr = false;
644 /* Mark each used value as live. */
645 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
646 if (reg->type == OP_IN)
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);
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);
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);
663 sparseset_and_compl (dead_set, start_living, start_dying);
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);
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);
676 if (need_curr_point_incr)
677 next_program_point (curr_point, freq);
679 /* Update notes. */
680 for (link_loc = &REG_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
682 if (REG_NOTE_KIND (link) != REG_DEAD
683 && REG_NOTE_KIND (link) != REG_UNUSED)
685 else if (REG_P (XEXP (link, 0)))
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)))
693 *link_loc = XEXP (link, 1);
694 continue;
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);
701 link_loc = &XEXP (link, 1);
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]);
709 #ifdef EH_RETURN_DATA_REGNO
710 if (bb_has_eh_pred (bb))
711 for (j = 0; ; ++j)
713 unsigned int regno = EH_RETURN_DATA_REGNO (j);
715 if (regno == INVALID_REGNUM)
716 break;
717 make_hard_regno_born (regno);
719 #endif
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))
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);
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);
748 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
749 mark_pseudo_dead (i, curr_point);
751 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
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);
759 if (need_curr_point_incr)
760 next_program_point (curr_point, freq);
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. */
767 static void
768 remove_some_program_points_and_update_live_ranges (void)
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;
778 born = sbitmap_alloc (lra_live_max_point);
779 dead = sbitmap_alloc (lra_live_max_point);
780 bitmap_clear (born);
781 bitmap_clear (dead);
782 max_regno = max_reg_num ();
783 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
785 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
787 lra_assert (r->start <= r->finish);
788 bitmap_set_bit (born, r->start);
789 bitmap_set_bit (dead, r->finish);
792 born_or_dead = sbitmap_alloc (lra_live_max_point);
793 bitmap_ior (born_or_dead, born, dead);
794 map = XCNEWVEC (int, lra_live_max_point);
795 n = -1;
796 prev_born_p = prev_dead_p = false;
797 EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
799 born_p = bitmap_bit_p (born, i);
800 dead_p = bitmap_bit_p (dead, i);
801 if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
802 || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
804 map[i] = n;
805 lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
807 else
809 map[i] = ++n;
810 lra_point_freq[n] = lra_point_freq[i];
812 prev_born_p = born_p;
813 prev_dead_p = dead_p;
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)
824 lra_live_max_point = n;
825 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
827 for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
828 r != NULL;
829 r = next_r)
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)
836 prev_r = r;
837 continue;
839 prev_r->start = r->start;
840 prev_r->next = next_r;
841 free_live_range (r);
845 free (map);
848 /* Print live ranges R to file F. */
849 void
850 lra_print_live_range_list (FILE *f, lra_live_range_t r)
852 for (; r != NULL; r = r->next)
853 fprintf (f, " [%d..%d]", r->start, r->finish);
854 fprintf (f, "\n");
857 DEBUG_FUNCTION void
858 debug (lra_live_range &ref)
860 lra_print_live_range_list (stderr, &ref);
863 DEBUG_FUNCTION void
864 debug (lra_live_range *ptr)
866 if (ptr)
867 debug (*ptr);
868 else
869 fprintf (stderr, "<nil>\n");
872 /* Print live ranges R to stderr. */
873 void
874 lra_debug_live_range_list (lra_live_range_t r)
876 lra_print_live_range_list (stderr, r);
879 /* Print live ranges of pseudo REGNO to file F. */
880 static void
881 print_pseudo_live_ranges (FILE *f, int regno)
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);
889 /* Print live ranges of pseudo REGNO to stderr. */
890 void
891 lra_debug_pseudo_live_ranges (int regno)
893 print_pseudo_live_ranges (stderr, regno);
896 /* Print live ranges of all pseudos to file F. */
897 static void
898 print_live_ranges (FILE *f)
900 int i, max_regno;
902 max_regno = max_reg_num ();
903 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
904 print_pseudo_live_ranges (f, i);
907 /* Print live ranges of all pseudos to stderr. */
908 void
909 lra_debug_live_ranges (void)
911 print_live_ranges (stderr);
914 /* Compress pseudo live ranges. */
915 static void
916 compress_live_ranges (void)
918 remove_some_program_points_and_update_live_ranges ();
919 if (lra_dump_file != NULL)
921 fprintf (lra_dump_file, "Ranges after the compression:\n");
922 print_live_ranges (lra_dump_file);
926 /* The number of the current live range pass. */
927 int lra_live_range_iter;
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. */
932 void
933 lra_create_live_ranges (bool all_p)
935 basic_block bb;
936 int i, hard_regno, max_regno = max_reg_num ();
937 int curr_point;
938 bool have_referenced_pseudos = false;
940 timevar_push (TV_LRA_CREATE_LIVE_RANGES);
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++)
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
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. */
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
971 && lra_reg_info[i].nrefs != 0)
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;
978 lra_free_copies ();
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)
985 timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
986 return;
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;
997 point_freq_vec.create (get_max_uid () * 2);
998 lra_point_freq = point_freq_vec.address ();
999 int *post_order_rev_cfg = XNEWVEC (int, last_basic_block_for_fn (cfun));
1000 int n_blocks_inverted = inverted_post_order_compute (post_order_rev_cfg);
1001 lra_assert (n_blocks_inverted == n_basic_blocks_for_fn (cfun));
1002 for (i = n_blocks_inverted - 1; i >= 0; --i)
1004 bb = BASIC_BLOCK_FOR_FN (cfun, post_order_rev_cfg[i]);
1005 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
1006 == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1007 continue;
1008 process_bb_lives (bb, curr_point);
1010 free (post_order_rev_cfg);
1011 lra_live_max_point = curr_point;
1012 gcc_checking_assert (lra_live_max_point > 0);
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);
1027 /* Finish all live ranges. */
1028 void
1029 lra_clear_live_ranges (void)
1031 int i;
1033 for (i = 0; i < max_reg_num (); i++)
1034 free_live_range_list (lra_reg_info[i].live_ranges);
1035 point_freq_vec.release ();
1038 /* Initialize live ranges data once per function. */
1039 void
1040 lra_live_ranges_init (void)
1042 live_range_pool = create_alloc_pool ("live ranges",
1043 sizeof (struct lra_live_range), 100);
1046 /* Finish live ranges data once per function. */
1047 void
1048 lra_live_ranges_finish (void)
1050 free_alloc_pool (live_range_pool);