1 /* IRA processing allocno lives to build allocno live ranges.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
34 #include "insn-config.h"
39 #include "sparseset.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. */
55 /* Arrays of size IRA_MAX_POINT mapping a program point to the allocno
56 live ranges with given start/finish point. */
57 allocno_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 cover
68 static int high_pressure_start_point[N_REG_CLASSES];
70 /* Allocnos live at current point in the scan. */
71 static sparseset allocnos_live;
73 /* Set of hard regs (except eliminable ones) currently live. */
74 static HARD_REG_SET hard_regs_live;
76 /* The loop tree node corresponding to the current basic block. */
77 static ira_loop_tree_node_t curr_bb_node;
79 /* The number of the last processed call. */
80 static int last_call_num;
81 /* The number of last call at which given allocno was saved. */
82 static int *allocno_saved_at_call;
84 /* The function processing birth of register REGNO. It updates living
85 hard regs and conflict hard regs for living allocnos or starts a
86 new live range for the allocno corresponding to REGNO if it is
89 make_regno_born (int regno)
93 allocno_live_range_t p;
95 if (regno < FIRST_PSEUDO_REGISTER)
97 SET_HARD_REG_BIT (hard_regs_live, regno);
98 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
100 SET_HARD_REG_BIT (ALLOCNO_CONFLICT_HARD_REGS (ira_allocnos[i]),
102 SET_HARD_REG_BIT (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (ira_allocnos[i]),
107 a = ira_curr_regno_allocno_map[regno];
110 if ((p = ALLOCNO_LIVE_RANGES (a)) == NULL
111 || (p->finish != curr_point && p->finish + 1 != curr_point))
112 ALLOCNO_LIVE_RANGES (a)
113 = ira_create_allocno_live_range (a, curr_point, -1,
114 ALLOCNO_LIVE_RANGES (a));
117 /* Update ALLOCNO_EXCESS_PRESSURE_POINTS_NUM for allocno A. */
119 update_allocno_pressure_excess_length (ira_allocno_t a)
122 enum reg_class cover_class, cl;
123 allocno_live_range_t p;
125 cover_class = ALLOCNO_COVER_CLASS (a);
127 (cl = ira_reg_class_super_classes[cover_class][i]) != LIM_REG_CLASSES;
130 if (high_pressure_start_point[cl] < 0)
132 p = ALLOCNO_LIVE_RANGES (a);
133 ira_assert (p != NULL);
134 start = (high_pressure_start_point[cl] > p->start
135 ? high_pressure_start_point[cl] : p->start);
136 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) += curr_point - start + 1;
140 /* Process the death of register REGNO. This updates hard_regs_live
141 or finishes the current live range for the allocno corresponding to
144 make_regno_dead (int regno)
147 allocno_live_range_t p;
149 if (regno < FIRST_PSEUDO_REGISTER)
151 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
154 a = ira_curr_regno_allocno_map[regno];
157 p = ALLOCNO_LIVE_RANGES (a);
158 ira_assert (p != NULL);
159 p->finish = curr_point;
160 update_allocno_pressure_excess_length (a);
163 /* The current register pressures for each cover class for the current
165 static int curr_reg_pressure[N_REG_CLASSES];
167 /* Mark allocno A as currently living and update current register
168 pressure, maximal register pressure for the current BB, start point
169 of the register pressure excess, and conflicting hard registers of
172 set_allocno_live (ira_allocno_t a)
175 enum reg_class cover_class, cl;
177 /* Invalidate because it is referenced. */
178 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
179 if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
181 sparseset_set_bit (allocnos_live, ALLOCNO_NUM (a));
182 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a), hard_regs_live);
183 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), hard_regs_live);
184 cover_class = ALLOCNO_COVER_CLASS (a);
186 (cl = ira_reg_class_super_classes[cover_class][i]) != LIM_REG_CLASSES;
189 curr_reg_pressure[cl] += ira_reg_class_nregs[cl][ALLOCNO_MODE (a)];
190 if (high_pressure_start_point[cl] < 0
191 && (curr_reg_pressure[cl] > ira_available_class_regs[cl]))
192 high_pressure_start_point[cl] = curr_point;
193 if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
194 curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
198 /* Mark allocno A as currently not living and update current register
199 pressure, start point of the register pressure excess, and register
200 pressure excess length for living allocnos. */
202 clear_allocno_live (ira_allocno_t a)
206 enum reg_class cover_class, cl;
209 /* Invalidate because it is referenced. */
210 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
211 if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
213 cover_class = ALLOCNO_COVER_CLASS (a);
216 (cl = ira_reg_class_super_classes[cover_class][i])
220 curr_reg_pressure[cl] -= ira_reg_class_nregs[cl][ALLOCNO_MODE (a)];
221 ira_assert (curr_reg_pressure[cl] >= 0);
222 if (high_pressure_start_point[cl] >= 0
223 && curr_reg_pressure[cl] <= ira_available_class_regs[cl])
228 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, j)
229 update_allocno_pressure_excess_length (ira_allocnos[j]);
231 (cl = ira_reg_class_super_classes[cover_class][i])
234 if (high_pressure_start_point[cl] >= 0
235 && curr_reg_pressure[cl] <= ira_available_class_regs[cl])
236 high_pressure_start_point[cl] = -1;
240 sparseset_clear_bit (allocnos_live, ALLOCNO_NUM (a));
243 /* Mark the register REG as live. Store a 1 in hard_regs_live or
244 allocnos_live for this register or the corresponding allocno,
245 record how many consecutive hardware registers it actually
248 mark_reg_live (rtx reg)
252 gcc_assert (REG_P (reg));
255 if (regno >= FIRST_PSEUDO_REGISTER)
257 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
261 if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
263 /* Invalidate because it is referenced. */
264 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
267 set_allocno_live (a);
269 make_regno_born (regno);
271 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
273 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
274 enum reg_class cover_class, cl;
278 if (! TEST_HARD_REG_BIT (hard_regs_live, regno)
279 && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
281 cover_class = ira_hard_regno_cover_class[regno];
283 (cl = ira_reg_class_super_classes[cover_class][i])
287 curr_reg_pressure[cl]++;
288 if (high_pressure_start_point[cl] < 0
289 && (curr_reg_pressure[cl]
290 > ira_available_class_regs[cl]))
291 high_pressure_start_point[cl] = curr_point;
293 make_regno_born (regno);
295 (cl = ira_reg_class_super_classes[cover_class][i])
299 if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
300 curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
308 /* Mark the register referenced by use or def REF as live. */
310 mark_ref_live (df_ref ref)
314 reg = DF_REF_REG (ref);
315 if (GET_CODE (reg) == SUBREG)
316 reg = SUBREG_REG (reg);
320 /* Mark the register REG as dead. Store a 0 in hard_regs_live or
321 allocnos_live for the register. */
323 mark_reg_dead (rtx reg)
327 gcc_assert (REG_P (reg));
330 if (regno >= FIRST_PSEUDO_REGISTER)
332 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
336 if (! sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
338 /* Invalidate because it is referenced. */
339 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
342 clear_allocno_live (a);
344 make_regno_dead (regno);
346 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
350 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
351 enum reg_class cover_class, cl;
356 if (TEST_HARD_REG_BIT (hard_regs_live, regno))
359 cover_class = ira_hard_regno_cover_class[regno];
361 (cl = ira_reg_class_super_classes[cover_class][i])
365 curr_reg_pressure[cl]--;
366 if (high_pressure_start_point[cl] >= 0
367 && curr_reg_pressure[cl] <= ira_available_class_regs[cl])
369 ira_assert (curr_reg_pressure[cl] >= 0);
373 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, j)
374 update_allocno_pressure_excess_length (ira_allocnos[j]);
376 (cl = ira_reg_class_super_classes[cover_class][i])
379 if (high_pressure_start_point[cl] >= 0
380 && (curr_reg_pressure[cl]
381 <= ira_available_class_regs[cl]))
382 high_pressure_start_point[cl] = -1;
384 make_regno_dead (regno);
391 /* Mark the register referenced by definition DEF as dead, if the
392 definition is a total one. */
394 mark_ref_dead (df_ref def)
398 if (DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL)
399 || DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL))
402 reg = DF_REF_REG (def);
403 if (GET_CODE (reg) == SUBREG)
404 reg = SUBREG_REG (reg);
408 /* Make pseudo REG conflicting with pseudo DREG, if the 1st pseudo
409 class is intersected with class CL. Advance the current program
410 point before making the conflict if ADVANCE_P. Return TRUE if we
411 will need to advance the current program point. */
413 make_pseudo_conflict (rtx reg, enum reg_class cl, rtx dreg, bool advance_p)
417 if (GET_CODE (reg) == SUBREG)
418 reg = SUBREG_REG (reg);
420 if (! REG_P (reg) || REGNO (reg) < FIRST_PSEUDO_REGISTER)
423 a = ira_curr_regno_allocno_map[REGNO (reg)];
424 if (! reg_classes_intersect_p (cl, ALLOCNO_COVER_CLASS (a)))
431 mark_reg_live (dreg);
433 mark_reg_dead (dreg);
438 /* Check and make if necessary conflicts for pseudo DREG of class
439 DEF_CL of the current insn with input operand USE of class USE_CL.
440 Advance the current program point before making the conflict if
441 ADVANCE_P. Return TRUE if we will need to advance the current
444 check_and_make_def_use_conflict (rtx dreg, enum reg_class def_cl,
445 int use, enum reg_class use_cl,
448 if (! reg_classes_intersect_p (def_cl, use_cl))
451 advance_p = make_pseudo_conflict (recog_data.operand[use],
452 use_cl, dreg, advance_p);
453 /* Reload may end up swapping commutative operands, so you
454 have to take both orderings into account. The
455 constraints for the two operands can be completely
456 different. (Indeed, if the constraints for the two
457 operands are the same for all alternatives, there's no
458 point marking them as commutative.) */
459 if (use < recog_data.n_operands - 1
460 && recog_data.constraints[use][0] == '%')
462 = make_pseudo_conflict (recog_data.operand[use + 1],
463 use_cl, dreg, advance_p);
465 && recog_data.constraints[use - 1][0] == '%')
467 = make_pseudo_conflict (recog_data.operand[use - 1],
468 use_cl, dreg, advance_p);
472 /* Check and make if necessary conflicts for definition DEF of class
473 DEF_CL of the current insn with input operands. Process only
474 constraints of alternative ALT. */
476 check_and_make_def_conflict (int alt, int def, enum reg_class def_cl)
480 enum reg_class use_cl, acl;
482 rtx dreg = recog_data.operand[def];
484 if (def_cl == NO_REGS)
487 if (GET_CODE (dreg) == SUBREG)
488 dreg = SUBREG_REG (dreg);
490 if (! REG_P (dreg) || REGNO (dreg) < FIRST_PSEUDO_REGISTER)
493 a = ira_curr_regno_allocno_map[REGNO (dreg)];
494 acl = ALLOCNO_COVER_CLASS (a);
495 if (! reg_classes_intersect_p (acl, def_cl))
500 for (use = 0; use < recog_data.n_operands; use++)
504 if (use == def || recog_data.operand_type[use] == OP_OUT)
507 if (recog_op_alt[use][alt].anything_ok)
510 use_cl = recog_op_alt[use][alt].cl;
512 /* If there's any alternative that allows USE to match DEF, do not
513 record a conflict. If that causes us to create an invalid
514 instruction due to the earlyclobber, reload must fix it up. */
515 for (alt1 = 0; alt1 < recog_data.n_alternatives; alt1++)
516 if (recog_op_alt[use][alt1].matches == def
517 || (use < recog_data.n_operands - 1
518 && recog_data.constraints[use][0] == '%'
519 && recog_op_alt[use + 1][alt1].matches == def)
521 && recog_data.constraints[use - 1][0] == '%'
522 && recog_op_alt[use - 1][alt1].matches == def))
525 if (alt1 < recog_data.n_alternatives)
528 advance_p = check_and_make_def_use_conflict (dreg, def_cl, use,
531 if ((use_match = recog_op_alt[use][alt].matches) >= 0)
533 if (use_match == def)
536 if (recog_op_alt[use_match][alt].anything_ok)
539 use_cl = recog_op_alt[use_match][alt].cl;
540 advance_p = check_and_make_def_use_conflict (dreg, def_cl, use,
546 /* Make conflicts of early clobber pseudo registers of the current
547 insn with its inputs. Avoid introducing unnecessary conflicts by
548 checking classes of the constraints and pseudos because otherwise
549 significant code degradation is possible for some targets. */
551 make_early_clobber_and_input_conflicts (void)
555 enum reg_class def_cl;
557 for (alt = 0; alt < recog_data.n_alternatives; alt++)
558 for (def = 0; def < recog_data.n_operands; def++)
561 if (recog_op_alt[def][alt].earlyclobber)
563 if (recog_op_alt[def][alt].anything_ok)
566 def_cl = recog_op_alt[def][alt].cl;
567 check_and_make_def_conflict (alt, def, def_cl);
569 if ((def_match = recog_op_alt[def][alt].matches) >= 0
570 && (recog_op_alt[def_match][alt].earlyclobber
571 || recog_op_alt[def][alt].earlyclobber))
573 if (recog_op_alt[def_match][alt].anything_ok)
576 def_cl = recog_op_alt[def_match][alt].cl;
577 check_and_make_def_conflict (alt, def, def_cl);
582 /* Mark early clobber hard registers of the current INSN as live (if
583 LIVE_P) or dead. Return true if there are such registers. */
585 mark_hard_reg_early_clobbers (rtx insn, bool live_p)
590 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
591 if (DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MUST_CLOBBER))
593 rtx dreg = DF_REF_REG (*def_rec);
595 if (GET_CODE (dreg) == SUBREG)
596 dreg = SUBREG_REG (dreg);
597 if (! REG_P (dreg) || REGNO (dreg) >= FIRST_PSEUDO_REGISTER)
600 /* Hard register clobbers are believed to be early clobber
601 because there is no way to say that non-operand hard
602 register clobbers are not early ones. */
604 mark_ref_live (*def_rec);
606 mark_ref_dead (*def_rec);
613 /* Checks that CONSTRAINTS permits to use only one hard register. If
614 it is so, the function returns the class of the hard register.
615 Otherwise it returns NO_REGS. */
616 static enum reg_class
617 single_reg_class (const char *constraints, rtx op, rtx equiv_const)
620 enum reg_class cl, next_cl;
624 for (ignore_p = false;
626 constraints += CONSTRAINT_LEN (c, constraints))
646 || (equiv_const != NULL_RTX && CONSTANT_P (equiv_const)))
652 || (GET_CODE (op) == CONST_DOUBLE && GET_MODE (op) == VOIDmode)
653 || (equiv_const != NULL_RTX
654 && (CONST_INT_P (equiv_const)
655 || (GET_CODE (equiv_const) == CONST_DOUBLE
656 && GET_MODE (equiv_const) == VOIDmode))))
661 if ((CONSTANT_P (op) && !CONST_INT_P (op)
662 && (GET_CODE (op) != CONST_DOUBLE || GET_MODE (op) != VOIDmode))
663 || (equiv_const != NULL_RTX
664 && CONSTANT_P (equiv_const)
665 && !CONST_INT_P (equiv_const)
666 && (GET_CODE (equiv_const) != CONST_DOUBLE
667 || GET_MODE (equiv_const) != VOIDmode)))
679 if ((CONST_INT_P (op)
680 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), c, constraints))
681 || (equiv_const != NULL_RTX
682 && CONST_INT_P (equiv_const)
683 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (equiv_const),
690 if (GET_CODE (op) == CONST_DOUBLE
691 || (GET_CODE (op) == CONST_VECTOR
692 && GET_MODE_CLASS (GET_MODE (op)) == MODE_VECTOR_FLOAT)
693 || (equiv_const != NULL_RTX
694 && (GET_CODE (equiv_const) == CONST_DOUBLE
695 || (GET_CODE (equiv_const) == CONST_VECTOR
696 && (GET_MODE_CLASS (GET_MODE (equiv_const))
697 == MODE_VECTOR_FLOAT)))))
703 if ((GET_CODE (op) == CONST_DOUBLE
704 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, c, constraints))
705 || (equiv_const != NULL_RTX
706 && GET_CODE (equiv_const) == CONST_DOUBLE
707 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (equiv_const,
710 /* ??? what about memory */
712 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
713 case 'h': case 'j': case 'k': case 'l':
714 case 'q': case 't': case 'u':
715 case 'v': case 'w': case 'x': case 'y': case 'z':
716 case 'A': case 'B': case 'C': case 'D':
717 case 'Q': case 'R': case 'S': case 'T': case 'U':
718 case 'W': case 'Y': case 'Z':
721 : REG_CLASS_FROM_CONSTRAINT (c, constraints));
722 if ((cl != NO_REGS && next_cl != cl)
723 || (ira_available_class_regs[next_cl]
724 > ira_reg_class_nregs[next_cl][GET_MODE (op)]))
729 case '0': case '1': case '2': case '3': case '4':
730 case '5': case '6': case '7': case '8': case '9':
732 = single_reg_class (recog_data.constraints[c - '0'],
733 recog_data.operand[c - '0'], NULL_RTX);
734 if ((cl != NO_REGS && next_cl != cl)
735 || next_cl == NO_REGS
736 || (ira_available_class_regs[next_cl]
737 > ira_reg_class_nregs[next_cl][GET_MODE (op)]))
748 /* The function checks that operand OP_NUM of the current insn can use
749 only one hard register. If it is so, the function returns the
750 class of the hard register. Otherwise it returns NO_REGS. */
751 static enum reg_class
752 single_reg_operand_class (int op_num)
754 if (op_num < 0 || recog_data.n_alternatives == 0)
756 return single_reg_class (recog_data.constraints[op_num],
757 recog_data.operand[op_num], NULL_RTX);
760 /* The function sets up hard register set *SET to hard registers which
761 might be used by insn reloads because the constraints are too
764 ira_implicitly_set_insn_hard_regs (HARD_REG_SET *set)
770 enum machine_mode mode;
772 CLEAR_HARD_REG_SET (*set);
773 for (i = 0; i < recog_data.n_operands; i++)
775 op = recog_data.operand[i];
777 if (GET_CODE (op) == SUBREG)
778 op = SUBREG_REG (op);
780 if (GET_CODE (op) == SCRATCH
781 || (REG_P (op) && (regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER))
783 const char *p = recog_data.constraints[i];
785 mode = (GET_CODE (op) == SCRATCH
786 ? GET_MODE (op) : PSEUDO_REGNO_MODE (regno));
788 for (ignore_p = false; (c = *p); p += CONSTRAINT_LEN (c, p))
797 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
798 case 'h': case 'j': case 'k': case 'l':
799 case 'q': case 't': case 'u':
800 case 'v': case 'w': case 'x': case 'y': case 'z':
801 case 'A': case 'B': case 'C': case 'D':
802 case 'Q': case 'R': case 'S': case 'T': case 'U':
803 case 'W': case 'Y': case 'Z':
806 : REG_CLASS_FROM_CONSTRAINT (c, p));
808 && (ira_available_class_regs[cl]
809 <= ira_reg_class_nregs[cl][mode]))
810 IOR_HARD_REG_SET (*set, reg_class_contents[cl]);
816 /* Processes input operands, if IN_P, or output operands otherwise of
817 the current insn with FREQ to find allocno which can use only one
818 hard register and makes other currently living allocnos conflicting
819 with the hard register. */
821 process_single_reg_class_operands (bool in_p, int freq)
827 ira_allocno_t operand_a, a;
829 for (i = 0; i < recog_data.n_operands; i++)
831 operand = recog_data.operand[i];
832 if (in_p && recog_data.operand_type[i] != OP_IN
833 && recog_data.operand_type[i] != OP_INOUT)
835 if (! in_p && recog_data.operand_type[i] != OP_OUT
836 && recog_data.operand_type[i] != OP_INOUT)
838 cl = single_reg_operand_class (i);
844 if (GET_CODE (operand) == SUBREG)
845 operand = SUBREG_REG (operand);
848 && (regno = REGNO (operand)) >= FIRST_PSEUDO_REGISTER)
850 enum machine_mode mode;
851 enum reg_class cover_class;
853 operand_a = ira_curr_regno_allocno_map[regno];
854 mode = ALLOCNO_MODE (operand_a);
855 cover_class = ALLOCNO_COVER_CLASS (operand_a);
856 if (ira_class_subset_p[cl][cover_class]
857 && ira_class_hard_regs_num[cl] != 0
858 && (ira_class_hard_reg_index[cover_class]
859 [ira_class_hard_regs[cl][0]]) >= 0
860 && reg_class_size[cl] <= (unsigned) CLASS_MAX_NREGS (cl, mode))
866 ? ira_get_register_move_cost (mode, cover_class, cl)
867 : ira_get_register_move_cost (mode, cl, cover_class)));
868 ira_allocate_and_set_costs
869 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a), cover_class, 0);
870 size = ira_reg_class_nregs[cover_class][mode];
871 for (i = 0; i < size; i++)
872 ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a)
873 [ira_class_hard_reg_index
874 [cover_class][ira_class_hard_regs[cl][i]]]
879 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, px)
881 a = ira_allocnos[px];
884 /* We could increase costs of A instead of making it
885 conflicting with the hard register. But it works worse
886 because it will be spilled in reload in anyway. */
887 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
888 reg_class_contents[cl]);
889 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
890 reg_class_contents[cl]);
896 /* Return true when one of the predecessor edges of BB is marked with
897 EDGE_ABNORMAL_CALL or EDGE_EH. */
899 bb_has_abnormal_call_pred (basic_block bb)
904 FOR_EACH_EDGE (e, ei, bb->preds)
906 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
912 /* Process insns of the basic block given by its LOOP_TREE_NODE to
913 update allocno live ranges, allocno hard register conflicts,
914 intersected calls, and register pressure info for allocnos for the
915 basic block for and regions containing the basic block. */
917 process_bb_node_lives (ira_loop_tree_node_t loop_tree_node)
928 bb = loop_tree_node->bb;
931 for (i = 0; i < ira_reg_class_cover_size; i++)
933 curr_reg_pressure[ira_reg_class_cover[i]] = 0;
934 high_pressure_start_point[ira_reg_class_cover[i]] = -1;
936 curr_bb_node = loop_tree_node;
937 reg_live_out = DF_LR_OUT (bb);
938 sparseset_clear (allocnos_live);
939 REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
940 AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
941 AND_COMPL_HARD_REG_SET (hard_regs_live, ira_no_alloc_regs);
942 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
943 if (TEST_HARD_REG_BIT (hard_regs_live, i))
945 enum reg_class cover_class, cl;
947 cover_class = ira_class_translate[REGNO_REG_CLASS (i)];
949 (cl = ira_reg_class_super_classes[cover_class][j])
953 curr_reg_pressure[cl]++;
954 if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
955 curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
956 ira_assert (curr_reg_pressure[cl]
957 <= ira_available_class_regs[cl]);
960 EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
962 ira_allocno_t a = ira_curr_regno_allocno_map[j];
966 ira_assert (! sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)));
967 set_allocno_live (a);
971 freq = REG_FREQ_FROM_BB (bb);
975 /* Invalidate all allocno_saved_at_call entries. */
978 /* Scan the code of this basic block, noting which allocnos and
979 hard regs are born or die.
981 Note that this loop treats uninitialized values as live until
982 the beginning of the block. For example, if an instruction
983 uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
984 set, FOO will remain live until the beginning of the block.
985 Likewise if FOO is not set at all. This is unnecessarily
986 pessimistic, but it probably doesn't matter much in practice. */
987 FOR_BB_INSNS_REVERSE (bb, insn)
989 df_ref *def_rec, *use_rec;
992 if (!NONDEBUG_INSN_P (insn))
995 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
996 fprintf (ira_dump_file, " Insn %u(l%d): point = %d\n",
997 INSN_UID (insn), loop_tree_node->parent->loop->num,
1000 /* Mark each defined value as live. We need to do this for
1001 unused values because they still conflict with quantities
1002 that are live at the time of the definition.
1004 Ignore DF_REF_MAY_CLOBBERs on a call instruction. Such
1005 references represent the effect of the called function
1006 on a call-clobbered register. Marking the register as
1007 live would stop us from allocating it to a call-crossing
1009 call_p = CALL_P (insn);
1010 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1011 if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
1012 mark_ref_live (*def_rec);
1014 /* If INSN has multiple outputs, then any value used in one
1015 of the outputs conflicts with the other outputs. Model this
1016 by making the used value live during the output phase.
1018 It is unsafe to use !single_set here since it will ignore
1019 an unused output. Just because an output is unused does
1020 not mean the compiler can assume the side effect will not
1021 occur. Consider if ALLOCNO appears in the address of an
1022 output and we reload the output. If we allocate ALLOCNO
1023 to the same hard register as an unused output we could
1024 set the hard register before the output reload insn. */
1025 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
1026 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1031 reg = DF_REF_REG (*use_rec);
1032 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
1036 set = XVECEXP (PATTERN (insn), 0, i);
1037 if (GET_CODE (set) == SET
1038 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
1040 /* After the previous loop, this is a no-op if
1041 REG is contained within SET_DEST (SET). */
1042 mark_ref_live (*use_rec);
1048 extract_insn (insn);
1049 preprocess_constraints ();
1050 process_single_reg_class_operands (false, freq);
1052 /* See which defined values die here. */
1053 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1054 if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
1055 mark_ref_dead (*def_rec);
1060 /* The current set of live allocnos are live across the call. */
1061 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
1063 ira_allocno_t a = ira_allocnos[i];
1065 if (allocno_saved_at_call[i] != last_call_num)
1066 /* Here we are mimicking caller-save.c behaviour
1067 which does not save hard register at a call if
1068 it was saved on previous call in the same basic
1069 block and the hard register was not mentioned
1070 between the two calls. */
1071 ALLOCNO_CALL_FREQ (a) += freq;
1072 /* Mark it as saved at the next call. */
1073 allocno_saved_at_call[i] = last_call_num + 1;
1074 ALLOCNO_CALLS_CROSSED_NUM (a)++;
1075 /* Don't allocate allocnos that cross setjmps or any
1076 call, if this function receives a nonlocal
1078 if (cfun->has_nonlocal_label
1079 || find_reg_note (insn, REG_SETJMP,
1080 NULL_RTX) != NULL_RTX)
1082 SET_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a));
1083 SET_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1085 if (can_throw_internal (insn))
1087 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
1089 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
1095 make_early_clobber_and_input_conflicts ();
1099 /* Mark each used value as live. */
1100 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1101 mark_ref_live (*use_rec);
1103 process_single_reg_class_operands (true, freq);
1105 set_p = mark_hard_reg_early_clobbers (insn, true);
1109 mark_hard_reg_early_clobbers (insn, false);
1111 /* Mark each hard reg as live again. For example, a
1112 hard register can be in clobber and in an insn
1114 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1116 rtx ureg = DF_REF_REG (*use_rec);
1118 if (GET_CODE (ureg) == SUBREG)
1119 ureg = SUBREG_REG (ureg);
1120 if (! REG_P (ureg) || REGNO (ureg) >= FIRST_PSEUDO_REGISTER)
1123 mark_ref_live (*use_rec);
1130 #ifdef EH_RETURN_DATA_REGNO
1131 if (bb_has_eh_pred (bb))
1134 unsigned int regno = EH_RETURN_DATA_REGNO (j);
1135 if (regno == INVALID_REGNUM)
1137 make_regno_born (regno);
1141 /* Allocnos can't go in stack regs at the start of a basic block
1142 that is reached by an abnormal edge. Likewise for call
1143 clobbered regs, because caller-save, fixup_abnormal_edges and
1144 possibly the table driven EH machinery are not quite ready to
1145 handle such allocnos live across such edges. */
1146 if (bb_has_abnormal_pred (bb))
1149 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, px)
1151 ALLOCNO_NO_STACK_REG_P (ira_allocnos[px]) = true;
1152 ALLOCNO_TOTAL_NO_STACK_REG_P (ira_allocnos[px]) = true;
1154 for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1155 make_regno_born (px);
1157 /* No need to record conflicts for call clobbered regs if we
1158 have nonlocal labels around, as we don't ever try to
1159 allocate such regs in this case. */
1160 if (!cfun->has_nonlocal_label && bb_has_abnormal_call_pred (bb))
1161 for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
1162 if (call_used_regs[px])
1163 make_regno_born (px);
1166 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
1168 make_regno_dead (ALLOCNO_REGNO (ira_allocnos[i]));
1174 /* Propagate register pressure to upper loop tree nodes: */
1175 if (loop_tree_node != ira_loop_tree_root)
1176 for (i = 0; i < ira_reg_class_cover_size; i++)
1178 enum reg_class cover_class;
1180 cover_class = ira_reg_class_cover[i];
1181 if (loop_tree_node->reg_pressure[cover_class]
1182 > loop_tree_node->parent->reg_pressure[cover_class])
1183 loop_tree_node->parent->reg_pressure[cover_class]
1184 = loop_tree_node->reg_pressure[cover_class];
1188 /* Create and set up IRA_START_POINT_RANGES and
1189 IRA_FINISH_POINT_RANGES. */
1191 create_start_finish_chains (void)
1194 ira_allocno_iterator ai;
1195 allocno_live_range_t r;
1197 ira_start_point_ranges
1198 = (allocno_live_range_t *) ira_allocate (ira_max_point
1199 * sizeof (allocno_live_range_t));
1200 memset (ira_start_point_ranges, 0,
1201 ira_max_point * sizeof (allocno_live_range_t));
1202 ira_finish_point_ranges
1203 = (allocno_live_range_t *) ira_allocate (ira_max_point
1204 * sizeof (allocno_live_range_t));
1205 memset (ira_finish_point_ranges, 0,
1206 ira_max_point * sizeof (allocno_live_range_t));
1207 FOR_EACH_ALLOCNO (a, ai)
1209 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1211 r->start_next = ira_start_point_ranges[r->start];
1212 ira_start_point_ranges[r->start] = r;
1213 r->finish_next = ira_finish_point_ranges[r->finish];
1214 ira_finish_point_ranges[r->finish] = r;
1219 /* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
1220 new live ranges and program points were added as a result if new
1223 ira_rebuild_start_finish_chains (void)
1225 ira_free (ira_finish_point_ranges);
1226 ira_free (ira_start_point_ranges);
1227 create_start_finish_chains ();
1230 /* Compress allocno live ranges by removing program points where
1233 remove_some_program_points_and_update_live_ranges (void)
1239 ira_allocno_iterator ai;
1240 allocno_live_range_t r;
1241 bitmap born_or_died;
1244 born_or_died = ira_allocate_bitmap ();
1245 FOR_EACH_ALLOCNO (a, ai)
1247 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1249 ira_assert (r->start <= r->finish);
1250 bitmap_set_bit (born_or_died, r->start);
1251 bitmap_set_bit (born_or_died, r->finish);
1254 map = (int *) ira_allocate (sizeof (int) * ira_max_point);
1256 EXECUTE_IF_SET_IN_BITMAP(born_or_died, 0, i, bi)
1260 ira_free_bitmap (born_or_died);
1261 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1262 fprintf (ira_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1263 ira_max_point, n, 100 * n / ira_max_point);
1265 FOR_EACH_ALLOCNO (a, ai)
1267 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1269 r->start = map[r->start];
1270 r->finish = map[r->finish];
1276 /* Print live ranges R to file F. */
1278 ira_print_live_range_list (FILE *f, allocno_live_range_t r)
1280 for (; r != NULL; r = r->next)
1281 fprintf (f, " [%d..%d]", r->start, r->finish);
1285 /* Print live ranges R to stderr. */
1287 ira_debug_live_range_list (allocno_live_range_t r)
1289 ira_print_live_range_list (stderr, r);
1292 /* Print live ranges of allocno A to file F. */
1294 print_allocno_live_ranges (FILE *f, ira_allocno_t a)
1296 fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1297 ira_print_live_range_list (f, ALLOCNO_LIVE_RANGES (a));
1300 /* Print live ranges of allocno A to stderr. */
1302 ira_debug_allocno_live_ranges (ira_allocno_t a)
1304 print_allocno_live_ranges (stderr, a);
1307 /* Print live ranges of all allocnos to file F. */
1309 print_live_ranges (FILE *f)
1312 ira_allocno_iterator ai;
1314 FOR_EACH_ALLOCNO (a, ai)
1315 print_allocno_live_ranges (f, a);
1318 /* Print live ranges of all allocnos to stderr. */
1320 ira_debug_live_ranges (void)
1322 print_live_ranges (stderr);
1325 /* The main entry function creates live ranges, set up
1326 CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for allocnos, and
1327 calculate register pressure info. */
1329 ira_create_allocno_live_ranges (void)
1331 allocnos_live = sparseset_alloc (ira_allocnos_num);
1334 allocno_saved_at_call
1335 = (int *) ira_allocate (ira_allocnos_num * sizeof (int));
1336 memset (allocno_saved_at_call, 0, ira_allocnos_num * sizeof (int));
1337 ira_traverse_loop_tree (true, ira_loop_tree_root, NULL,
1338 process_bb_node_lives);
1339 ira_max_point = curr_point;
1340 create_start_finish_chains ();
1341 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1342 print_live_ranges (ira_dump_file);
1344 ira_free (allocno_saved_at_call);
1345 sparseset_free (allocnos_live);
1348 /* Compress allocno live ranges. */
1350 ira_compress_allocno_live_ranges (void)
1352 remove_some_program_points_and_update_live_ranges ();
1353 ira_rebuild_start_finish_chains ();
1354 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1356 fprintf (ira_dump_file, "Ranges after the compression:\n");
1357 print_live_ranges (ira_dump_file);
1361 /* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES. */
1363 ira_finish_allocno_live_ranges (void)
1365 ira_free (ira_finish_point_ranges);
1366 ira_free (ira_start_point_ranges);