2014-03-25 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / ira-lives.c
blob906d6db58f6c3ad42ceaea538c5db984949ee5ca
1 /* IRA processing allocno lives to build allocno live ranges.
2 Copyright (C) 2006-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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "regs.h"
26 #include "rtl.h"
27 #include "tm_p.h"
28 #include "target.h"
29 #include "flags.h"
30 #include "except.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
33 #include "insn-config.h"
34 #include "recog.h"
35 #include "diagnostic-core.h"
36 #include "params.h"
37 #include "df.h"
38 #include "sbitmap.h"
39 #include "sparseset.h"
40 #include "ira-int.h"
42 /* The code in this file is similar to one in global but the code
43 works on the allocno basis and creates live ranges instead of
44 pseudo-register conflicts. */
46 /* Program points are enumerated by numbers from range
47 0..IRA_MAX_POINT-1. There are approximately two times more program
48 points than insns. Program points are places in the program where
49 liveness info can be changed. In most general case (there are more
50 complicated cases too) some program points correspond to places
51 where input operand dies and other ones correspond to places where
52 output operands are born. */
53 int ira_max_point;
55 /* Arrays of size IRA_MAX_POINT mapping a program point to the allocno
56 live ranges with given start/finish point. */
57 live_range_t *ira_start_point_ranges, *ira_finish_point_ranges;
59 /* Number of the current program point. */
60 static int curr_point;
62 /* Point where register pressure excess started or -1 if there is no
63 register pressure excess. Excess pressure for a register class at
64 some point means that there are more allocnos of given register
65 class living at the point than number of hard-registers of the
66 class available for the allocation. It is defined only for
67 pressure classes. */
68 static int high_pressure_start_point[N_REG_CLASSES];
70 /* Objects live at current point in the scan. */
71 static sparseset objects_live;
73 /* A temporary bitmap used in functions that wish to avoid visiting an allocno
74 multiple times. */
75 static sparseset allocnos_processed;
77 /* Set of hard regs (except eliminable ones) currently live. */
78 static HARD_REG_SET hard_regs_live;
80 /* The loop tree node corresponding to the current basic block. */
81 static ira_loop_tree_node_t curr_bb_node;
83 /* The number of the last processed call. */
84 static int last_call_num;
85 /* The number of last call at which given allocno was saved. */
86 static int *allocno_saved_at_call;
88 /* Record the birth of hard register REGNO, updating hard_regs_live and
89 hard reg conflict information for living allocnos. */
90 static void
91 make_hard_regno_born (int regno)
93 unsigned int i;
95 SET_HARD_REG_BIT (hard_regs_live, regno);
96 EXECUTE_IF_SET_IN_SPARSESET (objects_live, i)
98 ira_object_t obj = ira_object_id_map[i];
100 SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), regno);
101 SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), regno);
105 /* Process the death of hard register REGNO. This updates
106 hard_regs_live. */
107 static void
108 make_hard_regno_dead (int regno)
110 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
113 /* Record the birth of object OBJ. Set a bit for it in objects_live,
114 start a new live range for it if necessary and update hard register
115 conflicts. */
116 static void
117 make_object_born (ira_object_t obj)
119 live_range_t lr = OBJECT_LIVE_RANGES (obj);
121 sparseset_set_bit (objects_live, OBJECT_CONFLICT_ID (obj));
122 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), hard_regs_live);
123 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), hard_regs_live);
125 if (lr == NULL
126 || (lr->finish != curr_point && lr->finish + 1 != curr_point))
127 ira_add_live_range_to_object (obj, curr_point, -1);
130 /* Update ALLOCNO_EXCESS_PRESSURE_POINTS_NUM for the allocno
131 associated with object OBJ. */
132 static void
133 update_allocno_pressure_excess_length (ira_object_t obj)
135 ira_allocno_t a = OBJECT_ALLOCNO (obj);
136 int start, i;
137 enum reg_class aclass, pclass, cl;
138 live_range_t p;
140 aclass = ALLOCNO_CLASS (a);
141 pclass = ira_pressure_class_translate[aclass];
142 for (i = 0;
143 (cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES;
144 i++)
146 if (! ira_reg_pressure_class_p[cl])
147 continue;
148 if (high_pressure_start_point[cl] < 0)
149 continue;
150 p = OBJECT_LIVE_RANGES (obj);
151 ira_assert (p != NULL);
152 start = (high_pressure_start_point[cl] > p->start
153 ? high_pressure_start_point[cl] : p->start);
154 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) += curr_point - start + 1;
158 /* Process the death of object OBJ, which is associated with allocno
159 A. This finishes the current live range for it. */
160 static void
161 make_object_dead (ira_object_t obj)
163 live_range_t lr;
165 sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (obj));
166 lr = OBJECT_LIVE_RANGES (obj);
167 ira_assert (lr != NULL);
168 lr->finish = curr_point;
169 update_allocno_pressure_excess_length (obj);
172 /* The current register pressures for each pressure class for the current
173 basic block. */
174 static int curr_reg_pressure[N_REG_CLASSES];
176 /* Record that register pressure for PCLASS increased by N registers.
177 Update the current register pressure, maximal register pressure for
178 the current BB and the start point of the register pressure
179 excess. */
180 static void
181 inc_register_pressure (enum reg_class pclass, int n)
183 int i;
184 enum reg_class cl;
186 for (i = 0;
187 (cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES;
188 i++)
190 if (! ira_reg_pressure_class_p[cl])
191 continue;
192 curr_reg_pressure[cl] += n;
193 if (high_pressure_start_point[cl] < 0
194 && (curr_reg_pressure[cl] > ira_class_hard_regs_num[cl]))
195 high_pressure_start_point[cl] = curr_point;
196 if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
197 curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
201 /* Record that register pressure for PCLASS has decreased by NREGS
202 registers; update current register pressure, start point of the
203 register pressure excess, and register pressure excess length for
204 living allocnos. */
206 static void
207 dec_register_pressure (enum reg_class pclass, int nregs)
209 int i;
210 unsigned int j;
211 enum reg_class cl;
212 bool set_p = false;
214 for (i = 0;
215 (cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES;
216 i++)
218 if (! ira_reg_pressure_class_p[cl])
219 continue;
220 curr_reg_pressure[cl] -= nregs;
221 ira_assert (curr_reg_pressure[cl] >= 0);
222 if (high_pressure_start_point[cl] >= 0
223 && curr_reg_pressure[cl] <= ira_class_hard_regs_num[cl])
224 set_p = true;
226 if (set_p)
228 EXECUTE_IF_SET_IN_SPARSESET (objects_live, j)
229 update_allocno_pressure_excess_length (ira_object_id_map[j]);
230 for (i = 0;
231 (cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES;
232 i++)
234 if (! ira_reg_pressure_class_p[cl])
235 continue;
236 if (high_pressure_start_point[cl] >= 0
237 && curr_reg_pressure[cl] <= ira_class_hard_regs_num[cl])
238 high_pressure_start_point[cl] = -1;
243 /* Determine from the objects_live bitmap whether REGNO is currently live,
244 and occupies only one object. Return false if we have no information. */
245 static bool
246 pseudo_regno_single_word_and_live_p (int regno)
248 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
249 ira_object_t obj;
251 if (a == NULL)
252 return false;
253 if (ALLOCNO_NUM_OBJECTS (a) > 1)
254 return false;
256 obj = ALLOCNO_OBJECT (a, 0);
258 return sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj));
261 /* Mark the pseudo register REGNO as live. Update all information about
262 live ranges and register pressure. */
263 static void
264 mark_pseudo_regno_live (int regno)
266 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
267 enum reg_class pclass;
268 int i, n, nregs;
270 if (a == NULL)
271 return;
273 /* Invalidate because it is referenced. */
274 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
276 n = ALLOCNO_NUM_OBJECTS (a);
277 pclass = ira_pressure_class_translate[ALLOCNO_CLASS (a)];
278 nregs = ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
279 if (n > 1)
281 /* We track every subobject separately. */
282 gcc_assert (nregs == n);
283 nregs = 1;
286 for (i = 0; i < n; i++)
288 ira_object_t obj = ALLOCNO_OBJECT (a, i);
290 if (sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj)))
291 continue;
293 inc_register_pressure (pclass, nregs);
294 make_object_born (obj);
298 /* Like mark_pseudo_regno_live, but try to only mark one subword of
299 the pseudo as live. SUBWORD indicates which; a value of 0
300 indicates the low part. */
301 static void
302 mark_pseudo_regno_subword_live (int regno, int subword)
304 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
305 int n;
306 enum reg_class pclass;
307 ira_object_t obj;
309 if (a == NULL)
310 return;
312 /* Invalidate because it is referenced. */
313 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
315 n = ALLOCNO_NUM_OBJECTS (a);
316 if (n == 1)
318 mark_pseudo_regno_live (regno);
319 return;
322 pclass = ira_pressure_class_translate[ALLOCNO_CLASS (a)];
323 gcc_assert
324 (n == ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
325 obj = ALLOCNO_OBJECT (a, subword);
327 if (sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj)))
328 return;
330 inc_register_pressure (pclass, 1);
331 make_object_born (obj);
334 /* Mark the register REG as live. Store a 1 in hard_regs_live for
335 this register, record how many consecutive hardware registers it
336 actually needs. */
337 static void
338 mark_hard_reg_live (rtx reg)
340 int regno = REGNO (reg);
342 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
344 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
345 enum reg_class aclass, pclass;
347 while (regno < last)
349 if (! TEST_HARD_REG_BIT (hard_regs_live, regno)
350 && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
352 aclass = ira_hard_regno_allocno_class[regno];
353 pclass = ira_pressure_class_translate[aclass];
354 inc_register_pressure (pclass, 1);
355 make_hard_regno_born (regno);
357 regno++;
362 /* Mark a pseudo, or one of its subwords, as live. REGNO is the pseudo's
363 register number; ORIG_REG is the access in the insn, which may be a
364 subreg. */
365 static void
366 mark_pseudo_reg_live (rtx orig_reg, unsigned regno)
368 if (df_read_modify_subreg_p (orig_reg))
370 mark_pseudo_regno_subword_live (regno,
371 subreg_lowpart_p (orig_reg) ? 0 : 1);
373 else
374 mark_pseudo_regno_live (regno);
377 /* Mark the register referenced by use or def REF as live. */
378 static void
379 mark_ref_live (df_ref ref)
381 rtx reg = DF_REF_REG (ref);
382 rtx orig_reg = reg;
384 if (GET_CODE (reg) == SUBREG)
385 reg = SUBREG_REG (reg);
387 if (REGNO (reg) >= FIRST_PSEUDO_REGISTER)
388 mark_pseudo_reg_live (orig_reg, REGNO (reg));
389 else
390 mark_hard_reg_live (reg);
393 /* Mark the pseudo register REGNO as dead. Update all information about
394 live ranges and register pressure. */
395 static void
396 mark_pseudo_regno_dead (int regno)
398 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
399 int n, i, nregs;
400 enum reg_class cl;
402 if (a == NULL)
403 return;
405 /* Invalidate because it is referenced. */
406 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
408 n = ALLOCNO_NUM_OBJECTS (a);
409 cl = ira_pressure_class_translate[ALLOCNO_CLASS (a)];
410 nregs = ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
411 if (n > 1)
413 /* We track every subobject separately. */
414 gcc_assert (nregs == n);
415 nregs = 1;
417 for (i = 0; i < n; i++)
419 ira_object_t obj = ALLOCNO_OBJECT (a, i);
420 if (!sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj)))
421 continue;
423 dec_register_pressure (cl, nregs);
424 make_object_dead (obj);
428 /* Like mark_pseudo_regno_dead, but called when we know that only part of the
429 register dies. SUBWORD indicates which; a value of 0 indicates the low part. */
430 static void
431 mark_pseudo_regno_subword_dead (int regno, int subword)
433 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
434 int n;
435 enum reg_class cl;
436 ira_object_t obj;
438 if (a == NULL)
439 return;
441 /* Invalidate because it is referenced. */
442 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
444 n = ALLOCNO_NUM_OBJECTS (a);
445 if (n == 1)
446 /* The allocno as a whole doesn't die in this case. */
447 return;
449 cl = ira_pressure_class_translate[ALLOCNO_CLASS (a)];
450 gcc_assert
451 (n == ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
453 obj = ALLOCNO_OBJECT (a, subword);
454 if (!sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj)))
455 return;
457 dec_register_pressure (cl, 1);
458 make_object_dead (obj);
461 /* Mark the hard register REG as dead. Store a 0 in hard_regs_live for the
462 register. */
463 static void
464 mark_hard_reg_dead (rtx reg)
466 int regno = REGNO (reg);
468 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
470 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
471 enum reg_class aclass, pclass;
473 while (regno < last)
475 if (TEST_HARD_REG_BIT (hard_regs_live, regno))
477 aclass = ira_hard_regno_allocno_class[regno];
478 pclass = ira_pressure_class_translate[aclass];
479 dec_register_pressure (pclass, 1);
480 make_hard_regno_dead (regno);
482 regno++;
487 /* Mark a pseudo, or one of its subwords, as dead. REGNO is the pseudo's
488 register number; ORIG_REG is the access in the insn, which may be a
489 subreg. */
490 static void
491 mark_pseudo_reg_dead (rtx orig_reg, unsigned regno)
493 if (df_read_modify_subreg_p (orig_reg))
495 mark_pseudo_regno_subword_dead (regno,
496 subreg_lowpart_p (orig_reg) ? 0 : 1);
498 else
499 mark_pseudo_regno_dead (regno);
502 /* Mark the register referenced by definition DEF as dead, if the
503 definition is a total one. */
504 static void
505 mark_ref_dead (df_ref def)
507 rtx reg = DF_REF_REG (def);
508 rtx orig_reg = reg;
510 if (DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL))
511 return;
513 if (GET_CODE (reg) == SUBREG)
514 reg = SUBREG_REG (reg);
516 if (DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL)
517 && (GET_CODE (orig_reg) != SUBREG
518 || REGNO (reg) < FIRST_PSEUDO_REGISTER
519 || !df_read_modify_subreg_p (orig_reg)))
520 return;
522 if (REGNO (reg) >= FIRST_PSEUDO_REGISTER)
523 mark_pseudo_reg_dead (orig_reg, REGNO (reg));
524 else
525 mark_hard_reg_dead (reg);
528 /* If REG is a pseudo or a subreg of it, and the class of its allocno
529 intersects CL, make a conflict with pseudo DREG. ORIG_DREG is the
530 rtx actually accessed, it may be identical to DREG or a subreg of it.
531 Advance the current program point before making the conflict if
532 ADVANCE_P. Return TRUE if we will need to advance the current
533 program point. */
534 static bool
535 make_pseudo_conflict (rtx reg, enum reg_class cl, rtx dreg, rtx orig_dreg,
536 bool advance_p)
538 rtx orig_reg = reg;
539 ira_allocno_t a;
541 if (GET_CODE (reg) == SUBREG)
542 reg = SUBREG_REG (reg);
544 if (! REG_P (reg) || REGNO (reg) < FIRST_PSEUDO_REGISTER)
545 return advance_p;
547 a = ira_curr_regno_allocno_map[REGNO (reg)];
548 if (! reg_classes_intersect_p (cl, ALLOCNO_CLASS (a)))
549 return advance_p;
551 if (advance_p)
552 curr_point++;
554 mark_pseudo_reg_live (orig_reg, REGNO (reg));
555 mark_pseudo_reg_live (orig_dreg, REGNO (dreg));
556 mark_pseudo_reg_dead (orig_reg, REGNO (reg));
557 mark_pseudo_reg_dead (orig_dreg, REGNO (dreg));
559 return false;
562 /* Check and make if necessary conflicts for pseudo DREG of class
563 DEF_CL of the current insn with input operand USE of class USE_CL.
564 ORIG_DREG is the rtx actually accessed, it may be identical to
565 DREG or a subreg of it. Advance the current program point before
566 making the conflict if ADVANCE_P. Return TRUE if we will need to
567 advance the current program point. */
568 static bool
569 check_and_make_def_use_conflict (rtx dreg, rtx orig_dreg,
570 enum reg_class def_cl, int use,
571 enum reg_class use_cl, bool advance_p)
573 if (! reg_classes_intersect_p (def_cl, use_cl))
574 return advance_p;
576 advance_p = make_pseudo_conflict (recog_data.operand[use],
577 use_cl, dreg, orig_dreg, advance_p);
579 /* Reload may end up swapping commutative operands, so you
580 have to take both orderings into account. The
581 constraints for the two operands can be completely
582 different. (Indeed, if the constraints for the two
583 operands are the same for all alternatives, there's no
584 point marking them as commutative.) */
585 if (use < recog_data.n_operands - 1
586 && recog_data.constraints[use][0] == '%')
587 advance_p
588 = make_pseudo_conflict (recog_data.operand[use + 1],
589 use_cl, dreg, orig_dreg, advance_p);
590 if (use >= 1
591 && recog_data.constraints[use - 1][0] == '%')
592 advance_p
593 = make_pseudo_conflict (recog_data.operand[use - 1],
594 use_cl, dreg, orig_dreg, advance_p);
595 return advance_p;
598 /* Check and make if necessary conflicts for definition DEF of class
599 DEF_CL of the current insn with input operands. Process only
600 constraints of alternative ALT. */
601 static void
602 check_and_make_def_conflict (int alt, int def, enum reg_class def_cl)
604 int use, use_match;
605 ira_allocno_t a;
606 enum reg_class use_cl, acl;
607 bool advance_p;
608 rtx dreg = recog_data.operand[def];
609 rtx orig_dreg = dreg;
611 if (def_cl == NO_REGS)
612 return;
614 if (GET_CODE (dreg) == SUBREG)
615 dreg = SUBREG_REG (dreg);
617 if (! REG_P (dreg) || REGNO (dreg) < FIRST_PSEUDO_REGISTER)
618 return;
620 a = ira_curr_regno_allocno_map[REGNO (dreg)];
621 acl = ALLOCNO_CLASS (a);
622 if (! reg_classes_intersect_p (acl, def_cl))
623 return;
625 advance_p = true;
627 for (use = 0; use < recog_data.n_operands; use++)
629 int alt1;
631 if (use == def || recog_data.operand_type[use] == OP_OUT)
632 continue;
634 if (recog_op_alt[use][alt].anything_ok)
635 use_cl = ALL_REGS;
636 else
637 use_cl = recog_op_alt[use][alt].cl;
639 /* If there's any alternative that allows USE to match DEF, do not
640 record a conflict. If that causes us to create an invalid
641 instruction due to the earlyclobber, reload must fix it up. */
642 for (alt1 = 0; alt1 < recog_data.n_alternatives; alt1++)
643 if (recog_op_alt[use][alt1].matches == def
644 || (use < recog_data.n_operands - 1
645 && recog_data.constraints[use][0] == '%'
646 && recog_op_alt[use + 1][alt1].matches == def)
647 || (use >= 1
648 && recog_data.constraints[use - 1][0] == '%'
649 && recog_op_alt[use - 1][alt1].matches == def))
650 break;
652 if (alt1 < recog_data.n_alternatives)
653 continue;
655 advance_p = check_and_make_def_use_conflict (dreg, orig_dreg, def_cl,
656 use, use_cl, advance_p);
658 if ((use_match = recog_op_alt[use][alt].matches) >= 0)
660 if (use_match == def)
661 continue;
663 if (recog_op_alt[use_match][alt].anything_ok)
664 use_cl = ALL_REGS;
665 else
666 use_cl = recog_op_alt[use_match][alt].cl;
667 advance_p = check_and_make_def_use_conflict (dreg, orig_dreg, def_cl,
668 use, use_cl, advance_p);
673 /* Make conflicts of early clobber pseudo registers of the current
674 insn with its inputs. Avoid introducing unnecessary conflicts by
675 checking classes of the constraints and pseudos because otherwise
676 significant code degradation is possible for some targets. */
677 static void
678 make_early_clobber_and_input_conflicts (void)
680 int alt;
681 int def, def_match;
682 enum reg_class def_cl;
684 for (alt = 0; alt < recog_data.n_alternatives; alt++)
685 for (def = 0; def < recog_data.n_operands; def++)
687 def_cl = NO_REGS;
688 if (recog_op_alt[def][alt].earlyclobber)
690 if (recog_op_alt[def][alt].anything_ok)
691 def_cl = ALL_REGS;
692 else
693 def_cl = recog_op_alt[def][alt].cl;
694 check_and_make_def_conflict (alt, def, def_cl);
696 if ((def_match = recog_op_alt[def][alt].matches) >= 0
697 && (recog_op_alt[def_match][alt].earlyclobber
698 || recog_op_alt[def][alt].earlyclobber))
700 if (recog_op_alt[def_match][alt].anything_ok)
701 def_cl = ALL_REGS;
702 else
703 def_cl = recog_op_alt[def_match][alt].cl;
704 check_and_make_def_conflict (alt, def, def_cl);
709 /* Mark early clobber hard registers of the current INSN as live (if
710 LIVE_P) or dead. Return true if there are such registers. */
711 static bool
712 mark_hard_reg_early_clobbers (rtx insn, bool live_p)
714 df_ref *def_rec;
715 bool set_p = false;
717 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
718 if (DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MUST_CLOBBER))
720 rtx dreg = DF_REF_REG (*def_rec);
722 if (GET_CODE (dreg) == SUBREG)
723 dreg = SUBREG_REG (dreg);
724 if (! REG_P (dreg) || REGNO (dreg) >= FIRST_PSEUDO_REGISTER)
725 continue;
727 /* Hard register clobbers are believed to be early clobber
728 because there is no way to say that non-operand hard
729 register clobbers are not early ones. */
730 if (live_p)
731 mark_ref_live (*def_rec);
732 else
733 mark_ref_dead (*def_rec);
734 set_p = true;
737 return set_p;
740 /* Checks that CONSTRAINTS permits to use only one hard register. If
741 it is so, the function returns the class of the hard register.
742 Otherwise it returns NO_REGS. */
743 static enum reg_class
744 single_reg_class (const char *constraints, rtx op, rtx equiv_const)
746 int curr_alt, c;
747 bool ignore_p;
748 enum reg_class cl, next_cl;
750 cl = NO_REGS;
751 for (ignore_p = false, curr_alt = 0;
752 (c = *constraints);
753 constraints += CONSTRAINT_LEN (c, constraints))
754 if (c == '#' || !recog_data.alternative_enabled_p[curr_alt])
755 ignore_p = true;
756 else if (c == ',')
758 curr_alt++;
759 ignore_p = false;
761 else if (! ignore_p)
762 switch (c)
764 case ' ':
765 case '\t':
766 case '=':
767 case '+':
768 case '*':
769 case '&':
770 case '%':
771 case '!':
772 case '?':
773 break;
774 case 'i':
775 if (CONSTANT_P (op)
776 || (equiv_const != NULL_RTX && CONSTANT_P (equiv_const)))
777 return NO_REGS;
778 break;
780 case 'n':
781 if (CONST_SCALAR_INT_P (op)
782 || (equiv_const != NULL_RTX && CONST_SCALAR_INT_P (equiv_const)))
783 return NO_REGS;
784 break;
786 case 's':
787 if ((CONSTANT_P (op) && !CONST_SCALAR_INT_P (op))
788 || (equiv_const != NULL_RTX
789 && CONSTANT_P (equiv_const)
790 && !CONST_SCALAR_INT_P (equiv_const)))
791 return NO_REGS;
792 break;
794 case 'I':
795 case 'J':
796 case 'K':
797 case 'L':
798 case 'M':
799 case 'N':
800 case 'O':
801 case 'P':
802 if ((CONST_INT_P (op)
803 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), c, constraints))
804 || (equiv_const != NULL_RTX
805 && CONST_INT_P (equiv_const)
806 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (equiv_const),
807 c, constraints)))
808 return NO_REGS;
809 break;
811 case 'E':
812 case 'F':
813 if (CONST_DOUBLE_AS_FLOAT_P (op)
814 || (GET_CODE (op) == CONST_VECTOR
815 && GET_MODE_CLASS (GET_MODE (op)) == MODE_VECTOR_FLOAT)
816 || (equiv_const != NULL_RTX
817 && (CONST_DOUBLE_AS_FLOAT_P (equiv_const)
818 || (GET_CODE (equiv_const) == CONST_VECTOR
819 && (GET_MODE_CLASS (GET_MODE (equiv_const))
820 == MODE_VECTOR_FLOAT)))))
821 return NO_REGS;
822 break;
824 case 'G':
825 case 'H':
826 if ((CONST_DOUBLE_AS_FLOAT_P (op)
827 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, c, constraints))
828 || (equiv_const != NULL_RTX
829 && CONST_DOUBLE_AS_FLOAT_P (equiv_const)
830 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (equiv_const,
831 c, constraints)))
832 return NO_REGS;
833 /* ??? what about memory */
834 case 'r':
835 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
836 case 'h': case 'j': case 'k': case 'l':
837 case 'q': case 't': case 'u':
838 case 'v': case 'w': case 'x': case 'y': case 'z':
839 case 'A': case 'B': case 'C': case 'D':
840 case 'Q': case 'R': case 'S': case 'T': case 'U':
841 case 'W': case 'Y': case 'Z':
842 next_cl = (c == 'r'
843 ? GENERAL_REGS
844 : REG_CLASS_FROM_CONSTRAINT (c, constraints));
845 if (cl == NO_REGS
846 ? ira_class_singleton[next_cl][GET_MODE (op)] < 0
847 : (ira_class_singleton[cl][GET_MODE (op)]
848 != ira_class_singleton[next_cl][GET_MODE (op)]))
849 return NO_REGS;
850 cl = next_cl;
851 break;
853 case '0': case '1': case '2': case '3': case '4':
854 case '5': case '6': case '7': case '8': case '9':
855 next_cl
856 = single_reg_class (recog_data.constraints[c - '0'],
857 recog_data.operand[c - '0'], NULL_RTX);
858 if (cl == NO_REGS
859 ? ira_class_singleton[next_cl][GET_MODE (op)] < 0
860 : (ira_class_singleton[cl][GET_MODE (op)]
861 != ira_class_singleton[next_cl][GET_MODE (op)]))
862 return NO_REGS;
863 cl = next_cl;
864 break;
866 default:
867 return NO_REGS;
869 return cl;
872 /* The function checks that operand OP_NUM of the current insn can use
873 only one hard register. If it is so, the function returns the
874 class of the hard register. Otherwise it returns NO_REGS. */
875 static enum reg_class
876 single_reg_operand_class (int op_num)
878 if (op_num < 0 || recog_data.n_alternatives == 0)
879 return NO_REGS;
880 return single_reg_class (recog_data.constraints[op_num],
881 recog_data.operand[op_num], NULL_RTX);
884 /* The function sets up hard register set *SET to hard registers which
885 might be used by insn reloads because the constraints are too
886 strict. */
887 void
888 ira_implicitly_set_insn_hard_regs (HARD_REG_SET *set)
890 int i, curr_alt, c, regno = 0;
891 bool ignore_p;
892 enum reg_class cl;
893 rtx op;
894 enum machine_mode mode;
896 CLEAR_HARD_REG_SET (*set);
897 for (i = 0; i < recog_data.n_operands; i++)
899 op = recog_data.operand[i];
901 if (GET_CODE (op) == SUBREG)
902 op = SUBREG_REG (op);
904 if (GET_CODE (op) == SCRATCH
905 || (REG_P (op) && (regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER))
907 const char *p = recog_data.constraints[i];
909 mode = (GET_CODE (op) == SCRATCH
910 ? GET_MODE (op) : PSEUDO_REGNO_MODE (regno));
911 cl = NO_REGS;
912 for (ignore_p = false, curr_alt = 0;
913 (c = *p);
914 p += CONSTRAINT_LEN (c, p))
915 if (c == '#' || !recog_data.alternative_enabled_p[curr_alt])
916 ignore_p = true;
917 else if (c == ',')
919 curr_alt++;
920 ignore_p = false;
922 else if (! ignore_p)
923 switch (c)
925 case 'r':
926 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
927 case 'h': case 'j': case 'k': case 'l':
928 case 'q': case 't': case 'u':
929 case 'v': case 'w': case 'x': case 'y': case 'z':
930 case 'A': case 'B': case 'C': case 'D':
931 case 'Q': case 'R': case 'S': case 'T': case 'U':
932 case 'W': case 'Y': case 'Z':
933 cl = (c == 'r'
934 ? GENERAL_REGS
935 : REG_CLASS_FROM_CONSTRAINT (c, p));
936 if (cl != NO_REGS)
938 /* There is no register pressure problem if all of the
939 regs in this class are fixed. */
940 int regno = ira_class_singleton[cl][mode];
941 if (regno >= 0)
942 add_to_hard_reg_set (set, mode, regno);
944 break;
949 /* Processes input operands, if IN_P, or output operands otherwise of
950 the current insn with FREQ to find allocno which can use only one
951 hard register and makes other currently living allocnos conflicting
952 with the hard register. */
953 static void
954 process_single_reg_class_operands (bool in_p, int freq)
956 int i, regno;
957 unsigned int px;
958 enum reg_class cl;
959 rtx operand;
960 ira_allocno_t operand_a, a;
962 for (i = 0; i < recog_data.n_operands; i++)
964 operand = recog_data.operand[i];
965 if (in_p && recog_data.operand_type[i] != OP_IN
966 && recog_data.operand_type[i] != OP_INOUT)
967 continue;
968 if (! in_p && recog_data.operand_type[i] != OP_OUT
969 && recog_data.operand_type[i] != OP_INOUT)
970 continue;
971 cl = single_reg_operand_class (i);
972 if (cl == NO_REGS)
973 continue;
975 operand_a = NULL;
977 if (GET_CODE (operand) == SUBREG)
978 operand = SUBREG_REG (operand);
980 if (REG_P (operand)
981 && (regno = REGNO (operand)) >= FIRST_PSEUDO_REGISTER)
983 enum reg_class aclass;
985 operand_a = ira_curr_regno_allocno_map[regno];
986 aclass = ALLOCNO_CLASS (operand_a);
987 if (ira_class_subset_p[cl][aclass])
989 /* View the desired allocation of OPERAND as:
991 (REG:YMODE YREGNO),
993 a simplification of:
995 (subreg:YMODE (reg:XMODE XREGNO) OFFSET). */
996 enum machine_mode ymode, xmode;
997 int xregno, yregno;
998 HOST_WIDE_INT offset;
1000 xmode = recog_data.operand_mode[i];
1001 xregno = ira_class_singleton[cl][xmode];
1002 gcc_assert (xregno >= 0);
1003 ymode = ALLOCNO_MODE (operand_a);
1004 offset = subreg_lowpart_offset (ymode, xmode);
1005 yregno = simplify_subreg_regno (xregno, xmode, offset, ymode);
1006 if (yregno >= 0
1007 && ira_class_hard_reg_index[aclass][yregno] >= 0)
1009 int cost;
1011 ira_allocate_and_set_costs
1012 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a),
1013 aclass, 0);
1014 ira_init_register_move_cost_if_necessary (xmode);
1015 cost = freq * (in_p
1016 ? ira_register_move_cost[xmode][aclass][cl]
1017 : ira_register_move_cost[xmode][cl][aclass]);
1018 ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a)
1019 [ira_class_hard_reg_index[aclass][yregno]] -= cost;
1024 EXECUTE_IF_SET_IN_SPARSESET (objects_live, px)
1026 ira_object_t obj = ira_object_id_map[px];
1027 a = OBJECT_ALLOCNO (obj);
1028 if (a != operand_a)
1030 /* We could increase costs of A instead of making it
1031 conflicting with the hard register. But it works worse
1032 because it will be spilled in reload in anyway. */
1033 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
1034 reg_class_contents[cl]);
1035 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
1036 reg_class_contents[cl]);
1042 /* Return true when one of the predecessor edges of BB is marked with
1043 EDGE_ABNORMAL_CALL or EDGE_EH. */
1044 static bool
1045 bb_has_abnormal_call_pred (basic_block bb)
1047 edge e;
1048 edge_iterator ei;
1050 FOR_EACH_EDGE (e, ei, bb->preds)
1052 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1053 return true;
1055 return false;
1058 /* Look through the CALL_INSN_FUNCTION_USAGE of a call insn INSN, and see if
1059 we find a SET rtx that we can use to deduce that a register can be cheaply
1060 caller-saved. Return such a register, or NULL_RTX if none is found. */
1061 static rtx
1062 find_call_crossed_cheap_reg (rtx insn)
1064 rtx cheap_reg = NULL_RTX;
1065 rtx exp = CALL_INSN_FUNCTION_USAGE (insn);
1067 while (exp != NULL)
1069 rtx x = XEXP (exp, 0);
1070 if (GET_CODE (x) == SET)
1072 exp = x;
1073 break;
1075 exp = XEXP (exp, 1);
1077 if (exp != NULL)
1079 basic_block bb = BLOCK_FOR_INSN (insn);
1080 rtx reg = SET_SRC (exp);
1081 rtx prev = PREV_INSN (insn);
1082 while (prev && !(INSN_P (prev)
1083 && BLOCK_FOR_INSN (prev) != bb))
1085 if (NONDEBUG_INSN_P (prev))
1087 rtx set = single_set (prev);
1089 if (set && rtx_equal_p (SET_DEST (set), reg))
1091 rtx src = SET_SRC (set);
1092 if (!REG_P (src) || HARD_REGISTER_P (src)
1093 || !pseudo_regno_single_word_and_live_p (REGNO (src)))
1094 break;
1095 if (!modified_between_p (src, prev, insn))
1096 cheap_reg = src;
1097 break;
1099 if (set && rtx_equal_p (SET_SRC (set), reg))
1101 rtx dest = SET_DEST (set);
1102 if (!REG_P (dest) || HARD_REGISTER_P (dest)
1103 || !pseudo_regno_single_word_and_live_p (REGNO (dest)))
1104 break;
1105 if (!modified_between_p (dest, prev, insn))
1106 cheap_reg = dest;
1107 break;
1110 if (reg_overlap_mentioned_p (reg, PATTERN (prev)))
1111 break;
1113 prev = PREV_INSN (prev);
1116 return cheap_reg;
1119 /* Process insns of the basic block given by its LOOP_TREE_NODE to
1120 update allocno live ranges, allocno hard register conflicts,
1121 intersected calls, and register pressure info for allocnos for the
1122 basic block for and regions containing the basic block. */
1123 static void
1124 process_bb_node_lives (ira_loop_tree_node_t loop_tree_node)
1126 int i, freq;
1127 unsigned int j;
1128 basic_block bb;
1129 rtx insn;
1130 bitmap_iterator bi;
1131 bitmap reg_live_out;
1132 unsigned int px;
1133 bool set_p;
1135 bb = loop_tree_node->bb;
1136 if (bb != NULL)
1138 for (i = 0; i < ira_pressure_classes_num; i++)
1140 curr_reg_pressure[ira_pressure_classes[i]] = 0;
1141 high_pressure_start_point[ira_pressure_classes[i]] = -1;
1143 curr_bb_node = loop_tree_node;
1144 reg_live_out = df_get_live_out (bb);
1145 sparseset_clear (objects_live);
1146 REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
1147 AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
1148 AND_COMPL_HARD_REG_SET (hard_regs_live, ira_no_alloc_regs);
1149 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1150 if (TEST_HARD_REG_BIT (hard_regs_live, i))
1152 enum reg_class aclass, pclass, cl;
1154 aclass = ira_allocno_class_translate[REGNO_REG_CLASS (i)];
1155 pclass = ira_pressure_class_translate[aclass];
1156 for (j = 0;
1157 (cl = ira_reg_class_super_classes[pclass][j])
1158 != LIM_REG_CLASSES;
1159 j++)
1161 if (! ira_reg_pressure_class_p[cl])
1162 continue;
1163 curr_reg_pressure[cl]++;
1164 if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
1165 curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
1166 ira_assert (curr_reg_pressure[cl]
1167 <= ira_class_hard_regs_num[cl]);
1170 EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
1171 mark_pseudo_regno_live (j);
1173 freq = REG_FREQ_FROM_BB (bb);
1174 if (freq == 0)
1175 freq = 1;
1177 /* Invalidate all allocno_saved_at_call entries. */
1178 last_call_num++;
1180 /* Scan the code of this basic block, noting which allocnos and
1181 hard regs are born or die.
1183 Note that this loop treats uninitialized values as live until
1184 the beginning of the block. For example, if an instruction
1185 uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
1186 set, FOO will remain live until the beginning of the block.
1187 Likewise if FOO is not set at all. This is unnecessarily
1188 pessimistic, but it probably doesn't matter much in practice. */
1189 FOR_BB_INSNS_REVERSE (bb, insn)
1191 df_ref *def_rec, *use_rec;
1192 bool call_p;
1194 if (!NONDEBUG_INSN_P (insn))
1195 continue;
1197 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1198 fprintf (ira_dump_file, " Insn %u(l%d): point = %d\n",
1199 INSN_UID (insn), loop_tree_node->parent->loop_num,
1200 curr_point);
1202 /* Mark each defined value as live. We need to do this for
1203 unused values because they still conflict with quantities
1204 that are live at the time of the definition.
1206 Ignore DF_REF_MAY_CLOBBERs on a call instruction. Such
1207 references represent the effect of the called function
1208 on a call-clobbered register. Marking the register as
1209 live would stop us from allocating it to a call-crossing
1210 allocno. */
1211 call_p = CALL_P (insn);
1212 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1213 if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
1214 mark_ref_live (*def_rec);
1216 /* If INSN has multiple outputs, then any value used in one
1217 of the outputs conflicts with the other outputs. Model this
1218 by making the used value live during the output phase.
1220 It is unsafe to use !single_set here since it will ignore
1221 an unused output. Just because an output is unused does
1222 not mean the compiler can assume the side effect will not
1223 occur. Consider if ALLOCNO appears in the address of an
1224 output and we reload the output. If we allocate ALLOCNO
1225 to the same hard register as an unused output we could
1226 set the hard register before the output reload insn. */
1227 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
1228 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1230 int i;
1231 rtx reg;
1233 reg = DF_REF_REG (*use_rec);
1234 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
1236 rtx set;
1238 set = XVECEXP (PATTERN (insn), 0, i);
1239 if (GET_CODE (set) == SET
1240 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
1242 /* After the previous loop, this is a no-op if
1243 REG is contained within SET_DEST (SET). */
1244 mark_ref_live (*use_rec);
1245 break;
1250 extract_insn (insn);
1251 preprocess_constraints ();
1252 process_single_reg_class_operands (false, freq);
1254 /* See which defined values die here. */
1255 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1256 if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
1257 mark_ref_dead (*def_rec);
1259 if (call_p)
1261 /* Try to find a SET in the CALL_INSN_FUNCTION_USAGE, and from
1262 there, try to find a pseudo that is live across the call but
1263 can be cheaply reconstructed from the return value. */
1264 rtx cheap_reg = find_call_crossed_cheap_reg (insn);
1265 if (cheap_reg != NULL_RTX)
1266 add_reg_note (insn, REG_RETURNED, cheap_reg);
1268 last_call_num++;
1269 sparseset_clear (allocnos_processed);
1270 /* The current set of live allocnos are live across the call. */
1271 EXECUTE_IF_SET_IN_SPARSESET (objects_live, i)
1273 ira_object_t obj = ira_object_id_map[i];
1274 ira_allocno_t a = OBJECT_ALLOCNO (obj);
1275 int num = ALLOCNO_NUM (a);
1277 /* Don't allocate allocnos that cross setjmps or any
1278 call, if this function receives a nonlocal
1279 goto. */
1280 if (cfun->has_nonlocal_label
1281 || find_reg_note (insn, REG_SETJMP,
1282 NULL_RTX) != NULL_RTX)
1284 SET_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj));
1285 SET_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1287 if (can_throw_internal (insn))
1289 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
1290 call_used_reg_set);
1291 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
1292 call_used_reg_set);
1295 if (sparseset_bit_p (allocnos_processed, num))
1296 continue;
1297 sparseset_set_bit (allocnos_processed, num);
1299 if (allocno_saved_at_call[num] != last_call_num)
1300 /* Here we are mimicking caller-save.c behaviour
1301 which does not save hard register at a call if
1302 it was saved on previous call in the same basic
1303 block and the hard register was not mentioned
1304 between the two calls. */
1305 ALLOCNO_CALL_FREQ (a) += freq;
1306 /* Mark it as saved at the next call. */
1307 allocno_saved_at_call[num] = last_call_num + 1;
1308 ALLOCNO_CALLS_CROSSED_NUM (a)++;
1309 if (cheap_reg != NULL_RTX
1310 && ALLOCNO_REGNO (a) == (int) REGNO (cheap_reg))
1311 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)++;
1315 make_early_clobber_and_input_conflicts ();
1317 curr_point++;
1319 /* Mark each used value as live. */
1320 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1321 mark_ref_live (*use_rec);
1323 process_single_reg_class_operands (true, freq);
1325 set_p = mark_hard_reg_early_clobbers (insn, true);
1327 if (set_p)
1329 mark_hard_reg_early_clobbers (insn, false);
1331 /* Mark each hard reg as live again. For example, a
1332 hard register can be in clobber and in an insn
1333 input. */
1334 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1336 rtx ureg = DF_REF_REG (*use_rec);
1338 if (GET_CODE (ureg) == SUBREG)
1339 ureg = SUBREG_REG (ureg);
1340 if (! REG_P (ureg) || REGNO (ureg) >= FIRST_PSEUDO_REGISTER)
1341 continue;
1343 mark_ref_live (*use_rec);
1347 curr_point++;
1350 #ifdef EH_RETURN_DATA_REGNO
1351 if (bb_has_eh_pred (bb))
1352 for (j = 0; ; ++j)
1354 unsigned int regno = EH_RETURN_DATA_REGNO (j);
1355 if (regno == INVALID_REGNUM)
1356 break;
1357 make_hard_regno_born (regno);
1359 #endif
1361 /* Allocnos can't go in stack regs at the start of a basic block
1362 that is reached by an abnormal edge. Likewise for call
1363 clobbered regs, because caller-save, fixup_abnormal_edges and
1364 possibly the table driven EH machinery are not quite ready to
1365 handle such allocnos live across such edges. */
1366 if (bb_has_abnormal_pred (bb))
1368 #ifdef STACK_REGS
1369 EXECUTE_IF_SET_IN_SPARSESET (objects_live, px)
1371 ira_allocno_t a = OBJECT_ALLOCNO (ira_object_id_map[px]);
1373 ALLOCNO_NO_STACK_REG_P (a) = true;
1374 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = true;
1376 for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1377 make_hard_regno_born (px);
1378 #endif
1379 /* No need to record conflicts for call clobbered regs if we
1380 have nonlocal labels around, as we don't ever try to
1381 allocate such regs in this case. */
1382 if (!cfun->has_nonlocal_label && bb_has_abnormal_call_pred (bb))
1383 for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
1384 if (call_used_regs[px])
1385 make_hard_regno_born (px);
1388 EXECUTE_IF_SET_IN_SPARSESET (objects_live, i)
1389 make_object_dead (ira_object_id_map[i]);
1391 curr_point++;
1394 /* Propagate register pressure to upper loop tree nodes: */
1395 if (loop_tree_node != ira_loop_tree_root)
1396 for (i = 0; i < ira_pressure_classes_num; i++)
1398 enum reg_class pclass;
1400 pclass = ira_pressure_classes[i];
1401 if (loop_tree_node->reg_pressure[pclass]
1402 > loop_tree_node->parent->reg_pressure[pclass])
1403 loop_tree_node->parent->reg_pressure[pclass]
1404 = loop_tree_node->reg_pressure[pclass];
1408 /* Create and set up IRA_START_POINT_RANGES and
1409 IRA_FINISH_POINT_RANGES. */
1410 static void
1411 create_start_finish_chains (void)
1413 ira_object_t obj;
1414 ira_object_iterator oi;
1415 live_range_t r;
1417 ira_start_point_ranges
1418 = (live_range_t *) ira_allocate (ira_max_point * sizeof (live_range_t));
1419 memset (ira_start_point_ranges, 0, ira_max_point * sizeof (live_range_t));
1420 ira_finish_point_ranges
1421 = (live_range_t *) ira_allocate (ira_max_point * sizeof (live_range_t));
1422 memset (ira_finish_point_ranges, 0, ira_max_point * sizeof (live_range_t));
1423 FOR_EACH_OBJECT (obj, oi)
1424 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
1426 r->start_next = ira_start_point_ranges[r->start];
1427 ira_start_point_ranges[r->start] = r;
1428 r->finish_next = ira_finish_point_ranges[r->finish];
1429 ira_finish_point_ranges[r->finish] = r;
1433 /* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
1434 new live ranges and program points were added as a result if new
1435 insn generation. */
1436 void
1437 ira_rebuild_start_finish_chains (void)
1439 ira_free (ira_finish_point_ranges);
1440 ira_free (ira_start_point_ranges);
1441 create_start_finish_chains ();
1444 /* Compress allocno live ranges by removing program points where
1445 nothing happens. */
1446 static void
1447 remove_some_program_points_and_update_live_ranges (void)
1449 unsigned i;
1450 int n;
1451 int *map;
1452 ira_object_t obj;
1453 ira_object_iterator oi;
1454 live_range_t r, prev_r, next_r;
1455 sbitmap born_or_dead, born, dead;
1456 sbitmap_iterator sbi;
1457 bool born_p, dead_p, prev_born_p, prev_dead_p;
1459 born = sbitmap_alloc (ira_max_point);
1460 dead = sbitmap_alloc (ira_max_point);
1461 bitmap_clear (born);
1462 bitmap_clear (dead);
1463 FOR_EACH_OBJECT (obj, oi)
1464 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
1466 ira_assert (r->start <= r->finish);
1467 bitmap_set_bit (born, r->start);
1468 bitmap_set_bit (dead, r->finish);
1471 born_or_dead = sbitmap_alloc (ira_max_point);
1472 bitmap_ior (born_or_dead, born, dead);
1473 map = (int *) ira_allocate (sizeof (int) * ira_max_point);
1474 n = -1;
1475 prev_born_p = prev_dead_p = false;
1476 EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1478 born_p = bitmap_bit_p (born, i);
1479 dead_p = bitmap_bit_p (dead, i);
1480 if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1481 || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1482 map[i] = n;
1483 else
1484 map[i] = ++n;
1485 prev_born_p = born_p;
1486 prev_dead_p = dead_p;
1488 sbitmap_free (born_or_dead);
1489 sbitmap_free (born);
1490 sbitmap_free (dead);
1491 n++;
1492 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1493 fprintf (ira_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1494 ira_max_point, n, 100 * n / ira_max_point);
1495 ira_max_point = n;
1497 FOR_EACH_OBJECT (obj, oi)
1498 for (r = OBJECT_LIVE_RANGES (obj), prev_r = NULL; r != NULL; r = next_r)
1500 next_r = r->next;
1501 r->start = map[r->start];
1502 r->finish = map[r->finish];
1503 if (prev_r == NULL || prev_r->start > r->finish + 1)
1505 prev_r = r;
1506 continue;
1508 prev_r->start = r->start;
1509 prev_r->next = next_r;
1510 ira_finish_live_range (r);
1513 ira_free (map);
1516 /* Print live ranges R to file F. */
1517 void
1518 ira_print_live_range_list (FILE *f, live_range_t r)
1520 for (; r != NULL; r = r->next)
1521 fprintf (f, " [%d..%d]", r->start, r->finish);
1522 fprintf (f, "\n");
1525 DEBUG_FUNCTION void
1526 debug (live_range &ref)
1528 ira_print_live_range_list (stderr, &ref);
1531 DEBUG_FUNCTION void
1532 debug (live_range *ptr)
1534 if (ptr)
1535 debug (*ptr);
1536 else
1537 fprintf (stderr, "<nil>\n");
1540 /* Print live ranges R to stderr. */
1541 void
1542 ira_debug_live_range_list (live_range_t r)
1544 ira_print_live_range_list (stderr, r);
1547 /* Print live ranges of object OBJ to file F. */
1548 static void
1549 print_object_live_ranges (FILE *f, ira_object_t obj)
1551 ira_print_live_range_list (f, OBJECT_LIVE_RANGES (obj));
1554 /* Print live ranges of allocno A to file F. */
1555 static void
1556 print_allocno_live_ranges (FILE *f, ira_allocno_t a)
1558 int n = ALLOCNO_NUM_OBJECTS (a);
1559 int i;
1561 for (i = 0; i < n; i++)
1563 fprintf (f, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1564 if (n > 1)
1565 fprintf (f, " [%d]", i);
1566 fprintf (f, "):");
1567 print_object_live_ranges (f, ALLOCNO_OBJECT (a, i));
1571 /* Print live ranges of allocno A to stderr. */
1572 void
1573 ira_debug_allocno_live_ranges (ira_allocno_t a)
1575 print_allocno_live_ranges (stderr, a);
1578 /* Print live ranges of all allocnos to file F. */
1579 static void
1580 print_live_ranges (FILE *f)
1582 ira_allocno_t a;
1583 ira_allocno_iterator ai;
1585 FOR_EACH_ALLOCNO (a, ai)
1586 print_allocno_live_ranges (f, a);
1589 /* Print live ranges of all allocnos to stderr. */
1590 void
1591 ira_debug_live_ranges (void)
1593 print_live_ranges (stderr);
1596 /* The main entry function creates live ranges, set up
1597 CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for objects, and
1598 calculate register pressure info. */
1599 void
1600 ira_create_allocno_live_ranges (void)
1602 objects_live = sparseset_alloc (ira_objects_num);
1603 allocnos_processed = sparseset_alloc (ira_allocnos_num);
1604 curr_point = 0;
1605 last_call_num = 0;
1606 allocno_saved_at_call
1607 = (int *) ira_allocate (ira_allocnos_num * sizeof (int));
1608 memset (allocno_saved_at_call, 0, ira_allocnos_num * sizeof (int));
1609 ira_traverse_loop_tree (true, ira_loop_tree_root, NULL,
1610 process_bb_node_lives);
1611 ira_max_point = curr_point;
1612 create_start_finish_chains ();
1613 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1614 print_live_ranges (ira_dump_file);
1615 /* Clean up. */
1616 ira_free (allocno_saved_at_call);
1617 sparseset_free (objects_live);
1618 sparseset_free (allocnos_processed);
1621 /* Compress allocno live ranges. */
1622 void
1623 ira_compress_allocno_live_ranges (void)
1625 remove_some_program_points_and_update_live_ranges ();
1626 ira_rebuild_start_finish_chains ();
1627 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1629 fprintf (ira_dump_file, "Ranges after the compression:\n");
1630 print_live_ranges (ira_dump_file);
1634 /* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES. */
1635 void
1636 ira_finish_allocno_live_ranges (void)
1638 ira_free (ira_finish_point_ranges);
1639 ira_free (ira_start_point_ranges);